X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FBranchFolding.cpp;h=9dec22ec78a36de0a7fb8f3abf976815cf035a8a;hb=343735288798bbd1cd2ed2750fa6cd323f12c26c;hp=6c8e09141bd71d666f71328ccb8df6568f997318;hpb=408e9d166a66c8891637975921de2980c1940c3f;p=oota-llvm.git diff --git a/lib/CodeGen/BranchFolding.cpp b/lib/CodeGen/BranchFolding.cpp index 6c8e09141bd..9dec22ec78a 100644 --- a/lib/CodeGen/BranchFolding.cpp +++ b/lib/CodeGen/BranchFolding.cpp @@ -98,24 +98,13 @@ BranchFolder::BranchFolder(bool defaultEnableTailMerge) { /// function, updating the CFG. void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) { assert(MBB->pred_empty() && "MBB must be dead!"); - DEBUG(errs() << "\nRemoving MBB: " << *MBB); + DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); MachineFunction *MF = MBB->getParent(); // drop all successors. while (!MBB->succ_empty()) MBB->removeSuccessor(MBB->succ_end()-1); - // If there are any labels in the basic block, unregister them from - // MachineModuleInfo. - if (MMI && !MBB->empty()) { - for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); - I != E; ++I) { - if (I->isLabel()) - // The label ID # is always operand #0, an immediate. - MMI->InvalidateLabel(I->getOperand(0).getImm()); - } - } - // Remove the block. MF->erase(MBB); } @@ -133,7 +122,7 @@ bool BranchFolder::OptimizeImpDefsBlock(MachineBasicBlock *MBB) { SmallSet ImpDefRegs; MachineBasicBlock::iterator I = MBB->begin(); while (I != MBB->end()) { - if (I->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) + if (!I->isImplicitDef()) break; unsigned Reg = I->getOperand(0).getReg(); ImpDefRegs.insert(Reg); @@ -203,56 +192,37 @@ bool BranchFolder::OptimizeFunction(MachineFunction &MF, MadeChange |= MadeChangeThisIteration; } - // See if any jump tables have become mergable or dead as the code generator + // See if any jump tables have become dead as the code generator // did its thing. MachineJumpTableInfo *JTI = MF.getJumpTableInfo(); - const std::vector &JTs = JTI->getJumpTables(); - if (!JTs.empty()) { - // Figure out how these jump tables should be merged. - std::vector JTMapping; - JTMapping.reserve(JTs.size()); - - // We always keep the 0th jump table. - JTMapping.push_back(0); - - // Scan the jump tables, seeing if there are any duplicates. Note that this - // is N^2, which should be fixed someday. - for (unsigned i = 1, e = JTs.size(); i != e; ++i) { - if (JTs[i].MBBs.empty()) - JTMapping.push_back(i); - else - JTMapping.push_back(JTI->getJumpTableIndex(JTs[i].MBBs)); - } - - // If a jump table was merge with another one, walk the function rewriting - // references to jump tables to reference the new JT ID's. Keep track of - // whether we see a jump table idx, if not, we can delete the JT. - BitVector JTIsLive(JTs.size()); - for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); - BB != E; ++BB) { - for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end(); - I != E; ++I) - for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) { - MachineOperand &Op = I->getOperand(op); - if (!Op.isJTI()) continue; - unsigned NewIdx = JTMapping[Op.getIndex()]; - Op.setIndex(NewIdx); - - // Remember that this JT is live. - JTIsLive.set(NewIdx); - } - } - - // Finally, remove dead jump tables. This happens either because the - // indirect jump was unreachable (and thus deleted) or because the jump - // table was merged with some other one. - for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i) - if (!JTIsLive.test(i)) { - JTI->RemoveJumpTable(i); - MadeChange = true; + if (JTI == 0) { + delete RS; + return MadeChange; + } + + // Walk the function to find jump tables that are live. + BitVector JTIsLive(JTI->getJumpTables().size()); + for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); + BB != E; ++BB) { + for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end(); + I != E; ++I) + for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) { + MachineOperand &Op = I->getOperand(op); + if (!Op.isJTI()) continue; + + // Remember that this JT is live. + JTIsLive.set(Op.getIndex()); } } + // Finally, remove dead jump tables. This happens when the + // indirect jump was unreachable (and thus deleted). + for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i) + if (!JTIsLive.test(i)) { + JTI->RemoveJumpTable(i); + MadeChange = true; + } + delete RS; return MadeChange; } @@ -294,28 +264,21 @@ static unsigned HashMachineInstr(const MachineInstr *MI) { return Hash; } -/// HashEndOfMBB - Hash the last few instructions in the MBB. For blocks -/// with no successors, we hash two instructions, because cross-jumping -/// only saves code when at least two instructions are removed (since a -/// branch must be inserted). For blocks with a successor, one of the -/// two blocks to be tail-merged will end with a branch already, so -/// it gains to cross-jump even for one instruction. -static unsigned HashEndOfMBB(const MachineBasicBlock *MBB, - unsigned minCommonTailLength) { +/// HashEndOfMBB - Hash the last instruction in the MBB. +static unsigned HashEndOfMBB(const MachineBasicBlock *MBB) { MachineBasicBlock::const_iterator I = MBB->end(); if (I == MBB->begin()) return 0; // Empty MBB. --I; - unsigned Hash = HashMachineInstr(I); - - if (I == MBB->begin() || minCommonTailLength == 1) - return Hash; // Single instr MBB. + // Skip debug info so it will not affect codegen. + while (I->isDebugValue()) { + if (I==MBB->begin()) + return 0; // MBB empty except for debug info. + --I; + } - --I; - // Hash in the second-to-last instruction. - Hash ^= HashMachineInstr(I) << 2; - return Hash; + return HashMachineInstr(I); } /// ComputeCommonTailLength - Given two machine basic blocks, compute the number @@ -331,18 +294,66 @@ static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1, unsigned TailLen = 0; while (I1 != MBB1->begin() && I2 != MBB2->begin()) { --I1; --I2; + // Skip debugging pseudos; necessary to avoid changing the code. + while (I1->isDebugValue()) { + if (I1==MBB1->begin()) { + while (I2->isDebugValue()) { + if (I2==MBB2->begin()) + // I1==DBG at begin; I2==DBG at begin + return TailLen; + --I2; + } + ++I2; + // I1==DBG at begin; I2==non-DBG, or first of DBGs not at begin + return TailLen; + } + --I1; + } + // I1==first (untested) non-DBG preceding known match + while (I2->isDebugValue()) { + if (I2==MBB2->begin()) { + ++I1; + // I1==non-DBG, or first of DBGs not at begin; I2==DBG at begin + return TailLen; + } + --I2; + } + // I1, I2==first (untested) non-DBGs preceding known match if (!I1->isIdenticalTo(I2) || // FIXME: This check is dubious. It's used to get around a problem where // people incorrectly expect inline asm directives to remain in the same // relative order. This is untenable because normal compiler // optimizations (like this one) may reorder and/or merge these // directives. - I1->getOpcode() == TargetInstrInfo::INLINEASM) { + I1->isInlineAsm()) { ++I1; ++I2; break; } ++TailLen; } + // Back past possible debugging pseudos at beginning of block. This matters + // when one block differs from the other only by whether debugging pseudos + // are present at the beginning. (This way, the various checks later for + // I1==MBB1->begin() work as expected.) + if (I1 == MBB1->begin() && I2 != MBB2->begin()) { + --I2; + while (I2->isDebugValue()) { + if (I2 == MBB2->begin()) { + return TailLen; + } + --I2; + } + ++I2; + } + if (I2 == MBB2->begin() && I1 != MBB1->begin()) { + --I1; + while (I1->isDebugValue()) { + if (I1 == MBB1->begin()) + return TailLen; + --I1; + } + ++I1; + } return TailLen; } @@ -409,6 +420,8 @@ static unsigned EstimateRuntime(MachineBasicBlock::iterator I, MachineBasicBlock::iterator E) { unsigned Time = 0; for (; I != E; ++I) { + if (I->isDebugValue()) + continue; const TargetInstrDesc &TID = I->getDesc(); if (TID.isCall()) Time += 10; @@ -636,7 +649,9 @@ unsigned BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB, SameTails[commonTailIndex].getTailStartPos(); MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock(); - DEBUG(errs() << "\nSplitting BB#" << MBB->getNumber() << ", size " + // If the common tail includes any debug info we will take it pretty + // randomly from one of the inputs. Might be better to remove it? + DEBUG(dbgs() << "\nSplitting BB#" << MBB->getNumber() << ", size " << maxCommonTailLength); MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI); @@ -666,18 +681,18 @@ bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB, // this many instructions in common. unsigned minCommonTailLength = TailMergeSize; - DEBUG(errs() << "\nTryTailMergeBlocks: "; + DEBUG(dbgs() << "\nTryTailMergeBlocks: "; for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) - errs() << "BB#" << MergePotentials[i].getBlock()->getNumber() + dbgs() << "BB#" << MergePotentials[i].getBlock()->getNumber() << (i == e-1 ? "" : ", "); - errs() << "\n"; + dbgs() << "\n"; if (SuccBB) { - errs() << " with successor BB#" << SuccBB->getNumber() << '\n'; + dbgs() << " with successor BB#" << SuccBB->getNumber() << '\n'; if (PredBB) - errs() << " which has fall-through from BB#" + dbgs() << " which has fall-through from BB#" << PredBB->getNumber() << "\n"; } - errs() << "Looking for common tails of at least " + dbgs() << "Looking for common tails of at least " << minCommonTailLength << " instruction" << (minCommonTailLength == 1 ? "" : "s") << '\n'; ); @@ -748,19 +763,19 @@ bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB, MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock(); // MBB is common tail. Adjust all other BB's to jump to this one. // Traversal must be forwards so erases work. - DEBUG(errs() << "\nUsing common tail in BB#" << MBB->getNumber() + DEBUG(dbgs() << "\nUsing common tail in BB#" << MBB->getNumber() << " for "); for (unsigned int i=0, e = SameTails.size(); i != e; ++i) { if (commonTailIndex == i) continue; - DEBUG(errs() << "BB#" << SameTails[i].getBlock()->getNumber() + DEBUG(dbgs() << "BB#" << SameTails[i].getBlock()->getNumber() << (i == e-1 ? "" : ", ")); // Hack the end off BB i, making it jump to BB commonTailIndex instead. ReplaceTailWithBranchTo(SameTails[i].getTailStartPos(), MBB); // BB i is no longer a predecessor of SuccBB; remove it from the worklist. MergePotentials.erase(SameTails[i].getMPIter()); } - DEBUG(errs() << "\n"); + DEBUG(dbgs() << "\n"); // We leave commonTailIndex in the worklist in case there are other blocks // that match it with a smaller number of instructions. MadeChange = true; @@ -778,7 +793,7 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { MergePotentials.clear(); for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { if (I->succ_empty()) - MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(I, 2U), I)); + MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(I), I)); } // See if we can do any tail merging on those. @@ -864,8 +879,7 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { // reinsert conditional branch only, for now TII->InsertBranch(*PBB, (TBB == IBB) ? FBB : TBB, 0, NewCond); } - MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(PBB, 1U), - *P)); + MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(PBB), *P)); } } if (MergePotentials.size() >= 2) @@ -905,6 +919,29 @@ bool BranchFolder::OptimizeBranches(MachineFunction &MF) { return MadeChange; } +// Blocks should be considered empty if they contain only debug info; +// else the debug info would affect codegen. +static bool IsEmptyBlock(MachineBasicBlock *MBB) { + if (MBB->empty()) + return true; + for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end(); + MBBI!=MBBE; ++MBBI) { + if (!MBBI->isDebugValue()) + return false; + } + return true; +} + +// Blocks with only debug info and branches should be considered the same +// as blocks with only branches. +static bool IsBranchOnlyBlock(MachineBasicBlock *MBB) { + MachineBasicBlock::iterator MBBI, MBBE; + for (MBBI = MBB->begin(), MBBE = MBB->end(); MBBI!=MBBE; ++MBBI) { + if (!MBBI->isDebugValue()) + break; + } + return (MBBI->getDesc().isBranch()); +} /// IsBetterFallthrough - Return true if it would be clearly better to /// fall-through to MBB1 than to fall through into MBB2. This has to return @@ -916,15 +953,21 @@ static bool IsBetterFallthrough(MachineBasicBlock *MBB1, // MBB1 doesn't, we prefer to fall through into MBB1. This allows us to // optimize branches that branch to either a return block or an assert block // into a fallthrough to the return. - if (MBB1->empty() || MBB2->empty()) return false; + if (IsEmptyBlock(MBB1) || IsEmptyBlock(MBB2)) return false; // If there is a clear successor ordering we make sure that one block // will fall through to the next if (MBB1->isSuccessor(MBB2)) return true; if (MBB2->isSuccessor(MBB1)) return false; - MachineInstr *MBB1I = --MBB1->end(); - MachineInstr *MBB2I = --MBB2->end(); + // Neither block consists entirely of debug info (per IsEmptyBlock check), + // so we needn't test for falling off the beginning here. + MachineBasicBlock::iterator MBB1I = --MBB1->end(); + while (MBB1I->isDebugValue()) + --MBB1I; + MachineBasicBlock::iterator MBB2I = --MBB2->end(); + while (MBB2I->isDebugValue()) + --MBB2I; return MBB2I->getDesc().isCall() && !MBB1I->getDesc().isCall(); } @@ -942,7 +985,7 @@ ReoptimizeBlock: // explicitly. Landing pads should not do this since the landing-pad table // points to this block. Blocks with their addresses taken shouldn't be // optimized away. - if (MBB->empty() && !MBB->isLandingPad() && !MBB->hasAddressTaken()) { + if (IsEmptyBlock(MBB) && !MBB->isLandingPad() && !MBB->hasAddressTaken()) { // Dead block? Leave for cleanup later. if (MBB->pred_empty()) return MadeChange; @@ -957,7 +1000,8 @@ ReoptimizeBlock: } // If MBB was the target of a jump table, update jump tables to go to the // fallthrough instead. - MF.getJumpTableInfo()->ReplaceMBBInJumpTables(MBB, FallThrough); + if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo()) + MJTI->ReplaceMBBInJumpTables(MBB, FallThrough); MadeChange = true; } return MadeChange; @@ -999,7 +1043,7 @@ ReoptimizeBlock: if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 && PrevBB.succ_size() == 1 && !MBB->hasAddressTaken()) { - DEBUG(errs() << "\nMerging into block: " << PrevBB + DEBUG(dbgs() << "\nMerging into block: " << PrevBB << "From MBB: " << *MBB); PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end()); PrevBB.removeSuccessor(PrevBB.succ_begin());; @@ -1064,27 +1108,11 @@ ReoptimizeBlock: !IsBetterFallthrough(PriorTBB, MBB)) DoTransform = false; - // We don't want to do this transformation if we have control flow like: - // br cond BB2 - // BB1: - // .. - // jmp BBX - // BB2: - // .. - // ret - // - // In this case, we could actually be moving the return block *into* a - // loop! - if (DoTransform && !MBB->succ_empty() && - (!PriorTBB->canFallThrough() || PriorTBB->empty())) - DoTransform = false; - - if (DoTransform) { // Reverse the branch so we will fall through on the previous true cond. SmallVector NewPriorCond(PriorCond); if (!TII->ReverseBranchCondition(NewPriorCond)) { - DEBUG(errs() << "\nMoving MBB: " << *MBB + DEBUG(dbgs() << "\nMoving MBB: " << *MBB << "To make fallthrough to: " << *PriorTBB << "\n"); TII->RemoveBranch(PrevBB); @@ -1127,13 +1155,29 @@ ReoptimizeBlock: // If this branch is the only thing in its block, see if we can forward // other blocks across it. if (CurTBB && CurCond.empty() && CurFBB == 0 && - MBB->begin()->getDesc().isBranch() && CurTBB != MBB && + IsBranchOnlyBlock(MBB) && CurTBB != MBB && !MBB->hasAddressTaken()) { // This block may contain just an unconditional branch. Because there can // be 'non-branch terminators' in the block, try removing the branch and // then seeing if the block is empty. TII->RemoveBranch(*MBB); - + // If the only things remaining in the block are debug info, remove these + // as well, so this will behave the same as an empty block in non-debug + // mode. + if (!MBB->empty()) { + bool NonDebugInfoFound = false; + for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); + I != E; ++I) { + if (!I->isDebugValue()) { + NonDebugInfoFound = true; + break; + } + } + if (!NonDebugInfoFound) + // Make the block empty, losing the debug info (we could probably + // improve this in some cases.) + MBB->erase(MBB->begin(), MBB->end()); + } // If this block is just an unconditional branch to CurTBB, we can // usually completely eliminate the block. The only case we cannot // completely eliminate the block is when the block before this one @@ -1191,7 +1235,8 @@ ReoptimizeBlock: } // Change any jumptables to go to the new MBB. - MF.getJumpTableInfo()->ReplaceMBBInJumpTables(MBB, CurTBB); + if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo()) + MJTI->ReplaceMBBInJumpTables(MBB, CurTBB); if (DidChange) { ++NumBranchOpts; MadeChange = true; @@ -1274,7 +1319,7 @@ ReoptimizeBlock: // Okay, there is no really great place to put this block. If, however, // the block before this one would be a fall-through if this block were // removed, move this block to the end of the function. - MachineBasicBlock *PrevTBB, *PrevFBB; + MachineBasicBlock *PrevTBB = 0, *PrevFBB = 0; SmallVector PrevCond; if (FallThrough != MF.end() && !TII->AnalyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&