| /********************************************************************** |
| // @@@ START COPYRIGHT @@@ |
| // |
| // Licensed to the Apache Software Foundation (ASF) under one |
| // or more contributor license agreements. See the NOTICE file |
| // distributed with this work for additional information |
| // regarding copyright ownership. The ASF licenses this file |
| // to you under the Apache License, Version 2.0 (the |
| // "License"); you may not use this file except in compliance |
| // with the License. You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, |
| // software distributed under the License is distributed on an |
| // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| // KIND, either express or implied. See the License for the |
| // specific language governing permissions and limitations |
| // under the License. |
| // |
| // @@@ END COPYRIGHT @@@ |
| **********************************************************************/ |
| |
| #include "ExpPCodeOptimizations.h" |
| |
| #define HASH_ALL TRUE |
| #define REORDER_HASH TRUE |
| |
| // |
| // This is a recursive function that attempts to find a hash inst whose write |
| // operand is equivalent to the provided def operand. Begin the search at the |
| // provided start inst. |
| // |
| PCodeInst* PCodeCfg::findHashInst(PCodeOperand* def, PCodeInst* start) |
| { |
| CollIndex defIndex = def->getBvIndex(); |
| PCodeBlock* block; |
| |
| if (start == NULL) |
| return NULL; |
| |
| block = start->block; |
| |
| // Walk each inst backwards from start in search for an inst that defines |
| // "def". If that inst is not a hash or a bulk hash combined inst, then |
| // return NULL. |
| |
| FOREACH_INST_IN_BLOCK_BACKWARDS_AT(block, inst, start) { |
| for (CollIndex i=0; i < inst->getWOps().entries(); i++) { |
| if (defIndex == inst->getWOps()[i]->getBvIndex()) { |
| if (inst->isHash() || |
| inst->getOpcode() == PCIT::HASHCOMB_BULK_MBIN32U) |
| return inst; |
| |
| return NULL; |
| } |
| } |
| } ENDFE_INST_IN_BLOCK_BACKWARDS_AT |
| |
| // At this point, we could not find the instruction which defined def. Now |
| // if the definition reaches this block, then all paths to this block must |
| // have the definition of this def operand. So, only check the first pred |
| // via a recursive call. |
| |
| if (block->reachingDefsTab_->find(defIndex, TRUE /* In */)) |
| if (block->getPreds().entries() > 0) |
| return findHashInst(def, block->getPreds()[0]->getLastInst()); |
| |
| // Definition could not be found - return NULL. |
| return NULL; |
| } |
| |
| // |
| // Create bulk hash combined instructions from multiple hash and hashcomb |
| // instructions. |
| // |
| void PCodeCfg::bulkHashComb() |
| { |
| CollIndex i, j, length, idx; |
| |
| FOREACH_BLOCK(block, firstInst, lastInst, index) { |
| FOREACH_INST_IN_BLOCK(block, inst) { |
| if (inst->getOpcode() == PCIT::HASHCOMB_MBIN32U_MBIN32U_MBIN32U) |
| { |
| PCodeInst* newInst; |
| |
| // Find the hash instruction which defines the source operands of this |
| // hashcomb instruction. |
| PCodeInst* src1 = findHashInst(inst->getROps()[0], inst); |
| PCodeInst* src2 = findHashInst(inst->getROps()[1], inst); |
| |
| // Unless HASH_ALL is set, continue if either src1 or src2 is NULL. |
| // HASH_ALL is used when the definition found does not need to be |
| // hashed again - this is often the case when no hash instruction |
| // exists (e.g., OPDATA/CLAUSE_EVAL is used). |
| |
| if (!HASH_ALL && (!src1 || !src2)) |
| continue; |
| |
| NABoolean topOpOnlySrc1 = FALSE, topOpOnlySrc2 = FALSE; |
| CollIndex max = MAX_HASHCOMB_BULK_OPERANDS; |
| |
| // Set length taken by operands (index,offset,size,pos = 4 ints / oper) |
| // If src1 is null (i.e. no proper HASH found) or the number of ops |
| // is greater than the max allowed, just use the final result for the |
| // new HASHCOMB_BULK instruction. Otherwise read in all operands. |
| |
| if (src1 && (src1->getROps().entries() < max)) |
| length = src1->getROps().entries(); |
| else { |
| topOpOnlySrc1 = TRUE; |
| length = 1; |
| } |
| |
| if (src2 && ((length+src2->getROps().entries()) <= max)) |
| length += src2->getROps().entries(); |
| else { |
| topOpOnlySrc2 = TRUE; |
| length += 1; |
| } |
| |
| // Add length of write operand, length field, and opcode itself |
| length = 4*(length+1); |
| |
| // Set up pcode byte stream with what we know |
| newInst = createInst(PCIT::HASHCOMB_BULK_MBIN32U, length); |
| newInst->code[1] = length; |
| newInst->code[2] = inst->code[1]; |
| newInst->code[3] = inst->code[2]; |
| |
| // Create one list with all the source operands |
| OPLIST list(heap_); |
| |
| // If the source inst found is not null (i.e. HASH or HASHCOMB_BULK) |
| // then include its operands. Otherwise, we can't hash the source, but |
| // we can still combine it, while hashing everything else. This |
| // requires a small hack of resetting the size of the operand to 0. |
| // A zero length tells the hashing algoritm to return the value as is, |
| // unhashed. |
| |
| if (!topOpOnlySrc1) |
| list.insert(src1->getROps()); |
| else { |
| inst->getROps()[0]->setLen(0); |
| list.insert(inst->getROps()[0]); |
| } |
| |
| if (!topOpOnlySrc2) |
| list.insert(src2->getROps()); |
| else { |
| inst->getROps()[1]->setLen(0); |
| list.insert(inst->getROps()[1]); |
| } |
| |
| for (i=0; i < list.entries(); i++) { |
| newInst->code[(4*i) + 4] = list[i]->getStackIndex(); |
| newInst->code[(4*i) + 5] = list[i]->getOffset(); |
| newInst->code[(4*i) + 6] = list[i]->getLen(); |
| newInst->code[(4*i) + 7] = i; |
| } |
| |
| loadOperandsOfInst(newInst); |
| |
| block->insertInstAfter(inst, newInst); |
| block->deleteInst(inst); |
| } |
| } ENDFE_INST_IN_BLOCK |
| } ENDFE_BLOCK |
| |
| |
| // Now reorder operands in hash for better parallel hashing. |
| if (!REORDER_HASH) |
| return; |
| |
| FOREACH_BLOCK(block, firstInst, lastInst, index) { |
| FOREACH_INST_IN_BLOCK(block, inst) { |
| if (inst->getOpcode() == PCIT::HASHCOMB_BULK_MBIN32U) { |
| |
| // Create one list with all the source operands |
| OPLIST list(heap_); |
| |
| list.insert(inst->getROps()); |
| |
| // Go through the list of operands and find pairs with minimal |
| // differences in lengths. These pairs are more suitable for parallel |
| // hashing. Unfortunately, however, because the need to be combined in |
| // the same order as was generated, we need to also keep track of each |
| // operands position (a.k.a combined order index). |
| |
| for (idx = 0; idx != list.entries();) |
| { |
| CollIndex op1=0, op2=0; // Operand positions of ideal hash pairs |
| UInt32 len1, len2; // Lengths of operands 1 and 2 |
| UInt32 min = UINT_MAX; // Init min diff between operand lengths |
| |
| // Go through each operand in list |
| for (i=0; i < list.entries(); i++) { |
| |
| // If operand was already inserted, continue to next operand |
| if (list[i] == NULL) continue; |
| |
| // Initialize op1 and op2 if this is the first legit operand seen |
| if (min == UINT_MAX) { |
| op1 = op2 = i; |
| } |
| |
| // Length of operand 1 |
| len1 = (list[i]->getLen() == 0) ? -1 : list[i]->getLen(); |
| |
| // Now go through the operand list again, but this time starting |
| // with the operand after op1. The difference in lengths will be |
| // calculated here, and then compared to the least difference found |
| // so far. |
| |
| for (j=i+1; j < list.entries(); j++) { |
| |
| // If operand was already inserted, continue to next operand |
| if (list[j] == NULL) continue; |
| |
| // Length of operand 2 |
| len2 = (list[j]->getLen() == 0) ? -1 : list[j]->getLen(); |
| |
| // Difference calculated must be absolute for comparison purposes |
| UInt32 diff = (len1 > len2) ? len1 - len2 : len2 - len1; |
| |
| // If diff is lowest found so far, we found a new hash candidate |
| if (diff < min) { |
| min = diff; |
| |
| // Always make op1 the smaller of the two, since parallel hash |
| // requires this order |
| op1 = (len1 > len2) ? j : i; |
| op2 = (len1 > len2) ? i : j; |
| } |
| } |
| } |
| |
| // At this point, it is only possible that we either found a pair or |
| // we have but one operand left. In either case, we're inserting at |
| // least one operand. Note that we move the index up in the last |
| // store |
| |
| inst->code[(4*idx) + 4] = list[op1]->getStackIndex(); |
| inst->code[(4*idx) + 5] = list[op1]->getOffset(); |
| inst->code[(4*idx) + 6] = list[op1]->getLen(); |
| inst->code[(4*idx++) + 7] = op1; |
| |
| // Since removing entry out of list will mess up the position info of |
| // each operand, replace with NULL, so that entry is side-stepped in |
| // algorithm |
| |
| list.removeAt(op1); |
| list.insertAt(op1, NULL); |
| |
| // If not a pair, then break out |
| if (op1 == op2) |
| break; |
| |
| // Add op2 and then effectively remove it from list |
| |
| inst->code[(4*idx) + 4] = list[op2]->getStackIndex(); |
| inst->code[(4*idx) + 5] = list[op2]->getOffset(); |
| inst->code[(4*idx) + 6] = list[op2]->getLen(); |
| inst->code[(4*idx++) + 7] = op2; |
| |
| list.removeAt(op2); |
| list.insertAt(op2, NULL); |
| } |
| |
| inst->reloadOperands(this); |
| } |
| } ENDFE_INST_IN_BLOCK |
| } ENDFE_BLOCK |
| } |
| |
| // |
| // Performs code motion and instruction grouping across all blocks |
| // |
| void PCodeCfg::codeMotion() |
| { |
| FOREACH_BLOCK(block, firstInst, lastInst, index) { |
| localCodeMotion(block); |
| } ENDFE_BLOCK |
| } |
| |
| // |
| // This function has two purposes. The first is to group like instructions |
| // together so that 1) they can be later combined into "bulk" forms and 2) to |
| // remove any unnecessary dependencies on execution order. The second |
| // purpose of this function is to find and generate genuine bulk moves where |
| // moves of two adjacent columns can be done in one shot. This comes as an |
| // artifact from the NOT_NULL_BRANCH_BULK instruction |
| // |
| void PCodeCfg::localCodeMotion(PCodeBlock* block) |
| { |
| FOREACH_INST_IN_BLOCK(block, inst) { |
| // Group certain instructions as close together as possible |
| if ((inst->getOpcode() == PCIT::RANGE_MFLT64) || |
| (inst->isNullBitmap()) || |
| (inst->isCopyMove() || inst->isConstMove())) |
| { |
| PCodeInst* insertInst = NULL; |
| |
| // Given inst, walk backwards from inst and try to find a spot to move |
| // inst into, taking consideration of waw/raw/war dependency violations |
| FOREACH_INST_IN_BLOCK_BACKWARDS_AT(block, prev, inst->prev) { |
| |
| CollIndex i, j; |
| NABoolean found = FALSE; |
| PCodeInst* nInst; |
| |
| // Moves are grouped in a more intricate way. If both operands are |
| // same-size moves, then we attempt to order them relative to each |
| // other in a way which would expose adjacent/bulk moves. |
| if (inst->isCopyMove() && prev->isCopyMove()) { |
| Int32 pWOff = prev->getWOps()[0]->getOffset(); |
| Int32 pROff = prev->getROps()[0]->getOffset(); |
| Int32 iWOff = inst->getWOps()[0]->getOffset(); |
| Int32 iROff = inst->getROps()[0]->getOffset(); |
| |
| // First group by writes |
| if ((inst->getWOps()[0]->getStackIndex() == |
| prev->getWOps()[0]->getStackIndex()) && |
| (inst->getWOps()[0]->getOffset() >= |
| prev->getWOps()[0]->getOffset())) { |
| |
| // Next group by reads |
| if ((inst->getROps()[0]->getStackIndex() == |
| prev->getROps()[0]->getStackIndex()) && |
| (inst->getROps()[0]->getOffset() >= |
| prev->getROps()[0]->getOffset())) { |
| |
| // Moves are now in order. Check to see if any overlap exists. |
| // Note, overlapping moves should not involve the same tuple for |
| // both source and target, *unless* we're dealing with different |
| // ranges. Since that's unlikely, just check for same tuple. |
| if ((prev->getWOps()[0]->getStackIndex() != |
| prev->getROps()[0]->getStackIndex()) && |
| ((pWOff + prev->getWOps()[0]->getLen()) == iWOff) && |
| ((pROff + prev->getROps()[0]->getLen()) == iROff)) { |
| |
| Int32 len = prev->getROps()[0]->getLen() + |
| inst->getROps()[0]->getLen(); |
| |
| PCIType::Instruction opc; |
| |
| switch (len) { |
| case 2: |
| opc = PCIT::MOVE_MBIN16U_MBIN16U; |
| break; |
| case 4: |
| opc = PCIT::MOVE_MBIN32U_MBIN32U; |
| break; |
| case 8: |
| opc = PCIT::MOVE_MBIN64S_MBIN64S; |
| break; |
| default: |
| opc = PCIT::MOVE_MBIN8_MBIN8_IBIN32S; |
| break; |
| } |
| |
| // Create a move by combining the two moves together |
| nInst = block->insertNewInstBefore(prev, opc); |
| |
| nInst->code[1] = prev->getWOps()[0]->getStackIndex(); |
| nInst->code[2] = pWOff; |
| nInst->code[3] = prev->getROps()[0]->getStackIndex(); |
| nInst->code[4] = pROff; |
| |
| if (opc == PCIT::MOVE_MBIN8_MBIN8_IBIN32S) |
| nInst->code[5] = len; |
| |
| loadOperandsOfInst(nInst); |
| |
| block->deleteInst(inst); |
| block->deleteInst(prev); |
| |
| // We're no longer trying to insert the inst |
| insertInst = NULL; |
| } |
| break; |
| } |
| } |
| } |
| else { |
| // Check moves first |
| if (inst->isConstMove() && |
| (prev->isConstMove() || prev->isCopyMove()) && |
| (inst->getWOps()[0]->getStackIndex() == |
| prev->getWOps()[0]->getStackIndex())) |
| break; |
| |
| // Check all other instructions next |
| if (prev->getOpcode() == inst->getOpcode()) |
| // If prev is the same type of instr as inst, then already grouped. |
| break; |
| } |
| |
| // First check for write-after-write hazards |
| // I.e. inst writes operand that prev writes to. |
| |
| for (i=0; !found && (i < prev->getWOps().entries()); i++) |
| for (j=0; !found && (j < inst->getWOps().entries()); j++) |
| if (inst->getWOps()[j]->canOverlap(prev->getWOps()[i])) |
| found = TRUE; |
| |
| // Now check for read-after-write hazards |
| // I.e. inst reads operand that prev writes to. |
| |
| for (i=0; !found && (i < prev->getWOps().entries()); i++) |
| for (j=0; !found && (j < inst->getROps().entries()); j++) |
| if (inst->getROps()[j]->canOverlap(prev->getWOps()[i])) |
| found = TRUE; |
| |
| // Lastly, check for write-after-read hazards |
| // I.e. prev reads operand that inst writes to. |
| |
| for (i=0; !found && (i < prev->getROps().entries()); i++) |
| for (j=0; !found && (j < inst->getWOps().entries()); j++) |
| if (inst->getWOps()[j]->canOverlap(prev->getROps()[i])) |
| found = TRUE; |
| |
| // If found is true, or then we can't perform the code motion. |
| if (found) |
| break; |
| |
| // It is safe to move the instruction before prev. |
| insertInst = prev; |
| |
| } ENDFE_INST_IN_BLOCK_BACKWARDS_AT |
| |
| // Move the instruction before insertInst |
| if (insertInst != NULL) { |
| |
| // Don't move inst up if no like instruction was found, and is not a |
| // copy move |
| if ((insertInst->prev == NULL) && (!inst->isCopyMove())) |
| continue; |
| |
| block->deleteInst(inst); |
| |
| // Careful inserting since code motion must be done correctly when |
| // thinking about inserting in between opdata/clause-eval pairs |
| if (insertInst->prev) |
| block->insertInstAfter(insertInst->prev, inst); |
| else |
| block->insertInstBefore(insertInst, inst); |
| } |
| } |
| } ENDFE_INST_IN_BLOCK |
| } |
| |
| NABoolean PCodeCfg::removeBulkNullBranch() |
| { |
| Int32 numOfNB = 0; |
| |
| if (!entryBlock_->getLastInst()->isBulkNullBranch()) |
| return FALSE; |
| |
| PCodeBlock* start = entryBlock_->getFallThroughBlock(); |
| |
| FOREACH_BLOCK_REV_DFO_AT(start, block, firstInst, lastInst, index) { |
| if (lastInst && lastInst->isNullBranch()) { |
| // Don't support bulk null checking for indirect varchars |
| if (lastInst->isVarcharNullBranch() && |
| lastInst->containsIndirectVarcharOperand()) |
| continue; |
| |
| numOfNB++; |
| } |
| } ENDFE_BLOCK_REV_DFO |
| |
| if (numOfNB < 2) { |
| deleteBlock(entryBlock_); |
| entryBlock_ = start; |
| |
| return TRUE; |
| } |
| |
| return FALSE; |
| } |
| |
| NABoolean PCodeCfg::bulkNullBranch() |
| { |
| CollIndex i; |
| PCodeBlock* newBlock; |
| PCodeBlock* copyBlocks; |
| PCodeInst* newInst; |
| Int32 length; |
| OPLIST list(heap_); |
| PCodeBlock** map; |
| NABitVector defs(heap_); |
| |
| NABoolean alignedFormat = FALSE; |
| NABoolean packedFormat = FALSE; |
| NABoolean differentRowsFound = FALSE; |
| Int32 bitmapIdx = 0; |
| Int32 bitmapOff = 0; |
| Int32 bitmapMaxNullBitIndex = -1; |
| |
| Int32 numOfNB = 0; // Number of null branch insts in cfg |
| Int32 numOfProcessedNB = 0; // Num of nb insts we can eval early |
| PCodeBlock* startBlock = entryBlock_; |
| |
| FOREACH_BLOCK_REV_DFO(block, firstInst, lastInst, index) { |
| |
| // Add all defs - the purpose of which is described later. |
| FOREACH_INST_IN_BLOCK(block, inst) { |
| for (i=0; i < inst->getWOps().entries(); i++) |
| defs += inst->getWOps()[i]->getBvIndex(); |
| } ENDFE_INST_IN_BLOCK |
| |
| if (lastInst && lastInst->isNullBranch()) { |
| NABoolean checked = FALSE; |
| |
| // Don't support bulk null checking for indirect varchars |
| if (lastInst->isVarcharNullBranch() && |
| lastInst->containsIndirectVarcharOperand()) |
| continue; |
| |
| // Found a null branch |
| numOfNB++; |
| |
| for (i=0; i < lastInst->getROps().entries(); i++) { |
| PCodeOperand* read = lastInst->getROps()[i]; |
| CollIndex rd = read->getBvIndex(); |
| |
| // Only variable read operands should be considered, since those are the |
| // only ones that can be defined upon entry. If this optimization were |
| // to ever change such that the bulk null branch instruction could be |
| // placed somewhere other than the entry block, revisit this. |
| if (!read->isVar()) |
| continue; |
| |
| #if 0 |
| // Old way of doing this using reaching defs |
| |
| PCodeInst* defI = startBlock->reachingDefsTab_->find(rd, TRUE /* In */); |
| PCodeInst* defO = block->reachingDefsTab_->find(rd); |
| |
| // If the read operand of the null branch has a known def that reaches |
| // it from the start block, and that def is not overwritten in the |
| // block containing the null branch, then it serves as a candidate for |
| // code motion for early null detection. Also, don't add the operand |
| // if it already exists in the list |
| |
| if ((defI != NULL) && (defI == defO)) |
| #else |
| // Instead of using costly reaching defs analysis, use the "defs" bit |
| // vector that has been computed up to this point. The idea being that |
| // if this read operand has been written to at any point in this expr, |
| // than it doesn't qualify for this opt. In almost every situation, a |
| // use of var operand in a null-branch check is done without a previous |
| // write to it in the same expr. |
| |
| if (!defs.contains(rd)) |
| #endif |
| { |
| CollIndex j; |
| |
| // Set checked flag indicating that this is a NULL branch to process |
| checked = TRUE; |
| |
| // Don't add operand if it already exists in list |
| for (j=0; j < list.entries(); j++) |
| if (rd == list[j]->getBvIndex()) |
| break; |
| |
| // If operand does not already exist in the list, add it. |
| if (j == list.entries()) |
| list.insert(read); |
| } |
| } |
| |
| if (checked) |
| numOfProcessedNB++; |
| |
| // If there are too many null branches, return. |
| if (numOfNB > 1000) |
| return FALSE; |
| } |
| } ENDFE_BLOCK_REV_DFO |
| |
| // Heuristic - don't do optimization if less than two null branches were found |
| // or if more than 50 unique nulls must be examined. Why the latter? Because |
| // not all 50 nullable columns will likely be NULL for a given row. |
| if ((numOfProcessedNB < 2) || (list.entries() > 50)) |
| return FALSE; |
| |
| // Mark all blocks as unvisited - used in copyCfg() |
| clearVisitedFlags(); |
| |
| // Create a map table used to map copy blocks to original blocks. Make a copy // of the cfg starting from startBlock. |
| |
| map = (PCodeBlock**) new(heap_) PCodeBlock*[maxBlockNum_ + 1]; |
| copyBlocks = copyCfg(startBlock, NULL, map); |
| NADELETEBASIC(map, heap_); |
| |
| // Create new entry block for not-null-branch-bulk |
| newBlock = createBlock(); |
| |
| // Analyze the not-nulls collected to see if and how we should process |
| for (i=0; i < list.entries(); i++) { |
| Int32 nullBitIndex = list[i]->getNullBitIndex(); |
| if (nullBitIndex == -1) |
| packedFormat = TRUE; |
| else |
| alignedFormat = TRUE; |
| |
| bitmapMaxNullBitIndex = ((nullBitIndex > bitmapMaxNullBitIndex) |
| ? nullBitIndex : bitmapMaxNullBitIndex); |
| |
| if (i == 0) { |
| bitmapIdx = list[i]->getStackIndex(); |
| bitmapOff = list[i]->getOffset(); |
| bitmapMaxNullBitIndex = nullBitIndex; |
| } |
| |
| // A different row representing different null indicators for either |
| // formats must show a different stack index - i.e. no need to compare |
| // offsets as well for aligned format bitmaps. |
| if (bitmapIdx != list[i]->getStackIndex()) |
| differentRowsFound = TRUE; |
| } |
| |
| // As a potential pcode bytecode bloat problem, we want to make sure that if |
| // we're dealing with the alignedFormat, then expect to see at least 1 bit |
| // check per byte in the bitmask (i.e. equivalent to a non-parallel check) |
| if (alignedFormat && !packedFormat) { |
| float real = ((float)list.entries() / (float)bitmapMaxNullBitIndex); |
| float limit = (float)1/(float)8; |
| |
| // If limit reached, generate longer NOT-NULL_BRANCH check |
| if (real < limit) |
| differentRowsFound = TRUE; |
| } |
| |
| if (packedFormat && !alignedFormat) { |
| if (differentRowsFound) { |
| // Length of inst is (opc + len + sub-opc + 2*#operands + branch) |
| length = 3 + 2*list.entries() + 1; |
| newInst = createInst(PCIT::NOT_NULL_BRANCH_BULK, length); |
| newInst->code[1] = length; |
| |
| newInst->code[2] = (differentRowsFound) ? 1 : 0; |
| |
| for (i=0; i < list.entries(); i++) { |
| newInst->code[2*i + 3] = list[i]->getStackIndex(); |
| newInst->code[2*i + 4] = list[i]->getOffset(); |
| } |
| } |
| else { |
| // Length of inst is (opc + len + sub-opc + idx + #operands + branch) |
| length = 4 + list.entries() + 1; |
| newInst = createInst(PCIT::NOT_NULL_BRANCH_BULK, length); |
| newInst->code[1] = length; |
| |
| newInst->code[2] = (differentRowsFound) ? 1 : 0; |
| |
| newInst->code[3] = list[0]->getStackIndex(); |
| for (i=0; i < list.entries(); i++) { |
| newInst->code[4+i] = list[i]->getOffset(); |
| } |
| } |
| } |
| else if ((alignedFormat && !packedFormat) && (!differentRowsFound)) { |
| // Length of inst is (opc + len + sub-opc + bitmap-idx + bitmap-off + |
| // bitmap-len + bitmap-mask + branch) |
| length = 6 + ((bitmapMaxNullBitIndex >> 5) + 1) + 1; |
| newInst = createInst(PCIT::NULL_BITMAP_BULK, length); |
| newInst->code[1] = length; |
| |
| newInst->code[2] = (differentRowsFound) ? 1 : 0; |
| |
| newInst->code[3] = bitmapIdx; |
| newInst->code[4] = bitmapOff; |
| newInst->code[5] = (bitmapMaxNullBitIndex >> 3) + 1; |
| |
| // Null out bitmap mask |
| for (i=0; i < (CollIndex)((bitmapMaxNullBitIndex >> 5) + 1); i++) |
| newInst->code[6+i] = 0; |
| |
| for (i=0; i < list.entries(); i++) { |
| Int32 bitIdx = list[i]->getNullBitIndex(); |
| |
| ((char*)(&newInst->code[6]))[bitIdx >> 3] |= |
| ((UInt32)0x1 << (7 - (bitIdx & 7))); |
| } |
| } |
| else { |
| // Length of inst is (opc + len + sub-opc + (3 * #operands) + branch) |
| length = 3 + 3*list.entries() + 1; |
| newInst = createInst(PCIT::NULL_BITMAP_BULK, length); |
| newInst->code[1] = length; |
| |
| newInst->code[2] = (differentRowsFound) ? 1 : 0; |
| |
| for (i=0; i < list.entries(); i++) { |
| newInst->code[3*i + 3] = list[i]->getStackIndex(); |
| newInst->code[3*i + 4] = list[i]->getOffset(); |
| newInst->code[3*i + 5] = list[i]->getNullBitIndex(); |
| } |
| } |
| |
| |
| loadOperandsOfInst(newInst); |
| |
| // Add the bulk not null branch to the end of the new block. Add the |
| // fall-through edge to the startBlock, and add an target edge to the |
| // copy blocks. |
| |
| newBlock->insertInstBefore(NULL, newInst); |
| newBlock->addEdge(startBlock); |
| newBlock->addEdge(copyBlocks); |
| |
| if (startBlock == entryBlock_) |
| entryBlock_ = newBlock; |
| |
| return TRUE; |
| } |
| |
| // |
| // Create bulk move instructions for adjacent moves. |
| // |
| void PCodeCfg::bulkMove(NABoolean sameSizeMoves) |
| { |
| CollIndex i, j, srcStackIndex; |
| PCodeInst* newInst; |
| INSTLIST list(heap_); |
| PCodeInst* lastMoveInst = NULL; |
| |
| FOREACH_BLOCK(block, firstInst, lastInst, index) { |
| |
| // Since we're finding groups of candidate instructions for the bulk move, |
| // we need to restart at the end of each group. Begin at first inst |
| for (PCodeInst* start = firstInst; start; ) { |
| |
| Int32 length = 0; |
| |
| // Clear the bulk move group list; |
| list.clear(); |
| |
| srcStackIndex = 0; |
| |
| // Given a start inst, traverse down the block in search of adjacent |
| // move inst with similar source and target operands. |
| FOREACH_INST_IN_BLOCK_AT(block, inst, start) { |
| |
| // Reset start inst in prep for next group |
| start = inst->next; |
| |
| // Since sameSizeMoves should always be TRUE for now, we only allow |
| // copy moves. |
| assert (sameSizeMoves == TRUE); |
| if (inst->isCopyMove() || inst->isConstMove()) { |
| |
| if (list.isEmpty()) { |
| // This inst will begin the bulk move group. Record the stack |
| // index used for the source, if one exists |
| |
| list.insert(inst); |
| if (inst->getROps().entries() > 0) |
| srcStackIndex = inst->getROps()[0]->getStackIndex(); |
| |
| if (inst->getOpcode() == PCIT::MOVE_MBIN8_MBIN8_IBIN32S) |
| length++; |
| } |
| else if (inst->getWOps()[0]->getStackIndex() == |
| list[0]->getWOps()[0]->getStackIndex()) |
| { |
| // Target operands match, now we just need to make sure that source |
| // operands match, if one exists |
| |
| if (inst->getROps().entries() > 0) { |
| if (srcStackIndex != 0) { |
| if (srcStackIndex != inst->getROps()[0]->getStackIndex()) { |
| start = inst; |
| break; |
| } |
| } |
| else |
| srcStackIndex = inst->getROps()[0]->getStackIndex(); |
| } |
| |
| lastMoveInst = inst; |
| |
| // Insert this inst in the list by grouping them with like instrs. |
| for (i=list.entries()-1; i >= 0; i--) { |
| CollIndex instWIdx, prevWIdx; |
| |
| if (list[i]->getOpcode() == inst->getOpcode()) { |
| list.insertAt(i+1, inst); |
| break; |
| } |
| |
| instWIdx = inst->getWOps()[0]->getBvIndex(); |
| prevWIdx = list[i]->getWOps()[0]->getBvIndex(); |
| |
| if ((i == 0) || |
| (inst->getROps().entries() && |
| (inst->getROps()[0]->getBvIndex() == prevWIdx)) || |
| (list[i]->getROps().entries() && |
| (instWIdx == list[i]->getROps()[0]->getBvIndex())) || |
| (instWIdx == prevWIdx)) |
| { |
| // If no match was found or a dependency violation exists |
| // which prevents the rearrangement, just insert at the end |
| list.insert(inst); |
| break; |
| } |
| } |
| |
| if (inst->getOpcode() == PCIT::MOVE_MBIN8_MBIN8_IBIN32S) |
| length++; |
| } |
| else { |
| start = inst; |
| break; |
| } |
| } |
| else if (!list.isEmpty()) { |
| // If we arrived at a non-move inst and the group has already been |
| // formed, break out |
| break; |
| } |
| } ENDFE_INST_IN_BLOCK |
| |
| // Here we generate the bulk move inst for the group found if a group of |
| // more than 1 moves were found. |
| if (list.entries() > 1) { |
| |
| // Length of inst is (3 * #operands) + opc + len + tgt-idx + src-idx |
| // Each operand will be (opc, tgt-off, src-off), and may include |
| // len of move as well if dealing with PCIT::MOVE_MBIN8_MBIN8_IBIN32S. |
| // Also, we do a "+=" because length is previously incremented while |
| // searching for groups for the car string moves |
| |
| length += 3*list.entries() + 4; |
| |
| // Format of bulk move instruction is this: |
| // |
| // Opc, length, wrt stk idx, src stk idx, [opc1, tgt-off1, src-off1] |
| // [opc2, tgt-off2, src-off2] |
| // .... |
| // |
| // And if we're dealing with a fast move instruction, that will be: |
| // |
| // [opc3, tgt-off3, src-off3, sz] |
| // |
| newInst = createInst(PCIT::MOVE_BULK, length); |
| newInst->code[1] = length; |
| newInst->code[2] = list[0]->getWOps()[0]->getStackIndex(); |
| newInst->code[3] = srcStackIndex; |
| |
| // Record the last inst before we should insert the buld move inst. |
| PCodeInst* indicatorInst = lastMoveInst->next; |
| |
| // Walk through each read operand in the list and insert the appropriate |
| // fields in the pcode byte stream for the bulk move instruction. |
| for (i=0, j=4; i < list.entries(); i++, j+=3) { |
| // Source offset will either be a *real* source offset, or it is the |
| // constant for a constant move |
| Int32 srcOffset = ((list[i]->getROps().entries()) |
| ? list[i]->getROps()[0]->getOffset() |
| : list[i]->code[3]); |
| |
| // Target offset |
| Int32 tgtOffset = list[i]->getWOps()[0]->getOffset(); |
| |
| newInst->code[j] = list[i]->getOpcode(); |
| newInst->code[j+1] = list[i]->getWOps()[0]->getOffset(); |
| newInst->code[j+2] = srcOffset; |
| |
| if (list[i]->getOpcode() == PCIT::MOVE_MBIN8_MBIN8_IBIN32S) { |
| newInst->code[j+3] = list[i]->code[5]; |
| j++; |
| } |
| |
| block->deleteInst(list[i]); |
| } |
| |
| loadOperandsOfInst(newInst); |
| |
| // If indicatorInst is null, that means we want to insert the bulk move |
| // inst at the end of the block. |
| if (indicatorInst) |
| block->insertInstBefore(indicatorInst, newInst); |
| else |
| block->insertInstAfter(NULL, newInst); |
| } |
| } |
| } ENDFE_BLOCK |
| } |
