X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FBranchFolding.cpp;h=583009c74a3b6375175801a9eab558478ff0f642;hb=236aa8a5032282d8793b537c0f3f7ffb381a83d4;hp=a8fee1c9ac360f6ca51720c0db37a86c9c8472ad;hpb=51b2b9e29e4fa828ffd83d36f548bc44a4007822;p=oota-llvm.git diff --git a/lib/CodeGen/BranchFolding.cpp b/lib/CodeGen/BranchFolding.cpp index a8fee1c9ac3..583009c74a3 100644 --- a/lib/CodeGen/BranchFolding.cpp +++ b/lib/CodeGen/BranchFolding.cpp @@ -38,22 +38,22 @@ STATISTIC(NumBranchOpts, "Number of branches optimized"); STATISTIC(NumTailMerge , "Number of block tails merged"); static cl::opt FlagEnableTailMerge("enable-tail-merge", cl::init(cl::BOU_UNSET), cl::Hidden); -namespace { - // Throttle for huge numbers of predecessors (compile speed problems) - static cl::opt - TailMergeThreshold("tail-merge-threshold", - cl::desc("Max number of predecessors to consider tail merging"), - cl::init(100), cl::Hidden); +// Throttle for huge numbers of predecessors (compile speed problems) +static cl::opt +TailMergeThreshold("tail-merge-threshold", + cl::desc("Max number of predecessors to consider tail merging"), + cl::init(150), cl::Hidden); +namespace { struct VISIBILITY_HIDDEN BranchFolder : public MachineFunctionPass { static char ID; explicit BranchFolder(bool defaultEnableTailMerge) : - MachineFunctionPass((intptr_t)&ID) { - switch (FlagEnableTailMerge) { - case cl::BOU_UNSET: EnableTailMerge = defaultEnableTailMerge; break; - case cl::BOU_TRUE: EnableTailMerge = true; break; - case cl::BOU_FALSE: EnableTailMerge = false; break; - } + MachineFunctionPass(&ID) { + switch (FlagEnableTailMerge) { + case cl::BOU_UNSET: EnableTailMerge = defaultEnableTailMerge; break; + case cl::BOU_TRUE: EnableTailMerge = true; break; + case cl::BOU_FALSE: EnableTailMerge = false; break; + } } virtual bool runOnMachineFunction(MachineFunction &MF); @@ -95,7 +95,7 @@ namespace { bool CanFallThrough(MachineBasicBlock *CurBB); bool CanFallThrough(MachineBasicBlock *CurBB, bool BranchUnAnalyzable, MachineBasicBlock *TBB, MachineBasicBlock *FBB, - const std::vector &Cond); + const SmallVectorImpl &Cond); }; char BranchFolder::ID = 0; } @@ -114,20 +114,19 @@ void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) { while (!MBB->succ_empty()) MBB->removeSuccessor(MBB->succ_end()-1); - // If there is DWARF info to active, check to see if there are any LABEL - // records in the basic block. If so, unregister them from MachineModuleInfo. + // 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 ((unsigned)I->getOpcode() == TargetInstrInfo::LABEL) { + if (I->isLabel()) // The label ID # is always operand #0, an immediate. MMI->InvalidateLabel(I->getOperand(0).getImm()); - } } } // Remove the block. - MF->getBasicBlockList().erase(MBB); + MF->erase(MBB); } /// OptimizeImpDefsBlock - If a basic block is just a bunch of implicit_def @@ -191,15 +190,15 @@ bool BranchFolder::runOnMachineFunction(MachineFunction &MF) { bool EverMadeChange = false; for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; I++) { MachineBasicBlock *MBB = I, *TBB = 0, *FBB = 0; - std::vector Cond; - if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond)) + SmallVector Cond; + if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, true)) EverMadeChange |= MBB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty()); EverMadeChange |= OptimizeImpDefsBlock(MBB); } RS = RegInfo->requiresRegisterScavenging(MF) ? new RegScavenger() : NULL; - MMI = getAnalysisToUpdate(); + MMI = getAnalysisIfAvailable(); bool MadeChangeThisIteration = true; while (MadeChangeThisIteration) { @@ -236,7 +235,7 @@ bool BranchFolder::runOnMachineFunction(MachineFunction &MF) { I != E; ++I) for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) { MachineOperand &Op = I->getOperand(op); - if (!Op.isJumpTableIndex()) continue; + if (!Op.isJTI()) continue; unsigned NewIdx = JTMapping[Op.getIndex()]; Op.setIndex(NewIdx); @@ -365,7 +364,7 @@ void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, // If OldBB isn't immediately before OldBB, insert a branch to it. if (++MachineFunction::iterator(OldBB) != MachineFunction::iterator(NewDest)) - TII->InsertBranch(*OldBB, NewDest, 0, std::vector()); + TII->InsertBranch(*OldBB, NewDest, 0, SmallVector()); OldBB->addSuccessor(NewDest); ++NumTailMerge; } @@ -375,17 +374,15 @@ void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, /// iterator. This returns the new MBB. MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB, MachineBasicBlock::iterator BBI1) { + MachineFunction &MF = *CurMBB.getParent(); + // Create the fall-through block. MachineFunction::iterator MBBI = &CurMBB; - MachineBasicBlock *NewMBB = new MachineBasicBlock(CurMBB.getBasicBlock()); - CurMBB.getParent()->getBasicBlockList().insert(++MBBI, NewMBB); + MachineBasicBlock *NewMBB =MF.CreateMachineBasicBlock(CurMBB.getBasicBlock()); + CurMBB.getParent()->insert(++MBBI, NewMBB); // Move all the successors of this block to the specified block. - while (!CurMBB.succ_empty()) { - MachineBasicBlock *S = *(CurMBB.succ_end()-1); - NewMBB->addSuccessor(S); - CurMBB.removeSuccessor(S); - } + NewMBB->transferSuccessors(&CurMBB); // Add an edge from CurMBB to NewMBB for the fall-through. CurMBB.addSuccessor(NewMBB); @@ -417,7 +414,7 @@ static unsigned EstimateRuntime(MachineBasicBlock::iterator I, const TargetInstrDesc &TID = I->getDesc(); if (TID.isCall()) Time += 10; - else if (TID.isSimpleLoad() || TID.mayStore()) + else if (TID.mayLoad() || TID.mayStore()) Time += 2; else ++Time; @@ -435,9 +432,9 @@ static void FixTail(MachineBasicBlock* CurMBB, MachineBasicBlock *SuccBB, MachineFunction *MF = CurMBB->getParent(); MachineFunction::iterator I = next(MachineFunction::iterator(CurMBB)); MachineBasicBlock *TBB = 0, *FBB = 0; - std::vector Cond; + SmallVector Cond; if (I != MF->end() && - !TII->AnalyzeBranch(*CurMBB, TBB, FBB, Cond)) { + !TII->AnalyzeBranch(*CurMBB, TBB, FBB, Cond, true)) { MachineBasicBlock *NextBB = I; if (TBB == NextBB && !Cond.empty() && !FBB) { if (!TII->ReverseBranchCondition(Cond)) { @@ -447,7 +444,7 @@ static void FixTail(MachineBasicBlock* CurMBB, MachineBasicBlock *SuccBB, } } } - TII->InsertBranch(*CurMBB, SuccBB, NULL, std::vector()); + TII->InsertBranch(*CurMBB, SuccBB, NULL, SmallVector()); } static bool MergeCompare(const std::pair &p, @@ -466,7 +463,7 @@ static bool MergeCompare(const std::pair &p, #ifndef _GLIBCXX_DEBUG assert(0 && "Predecessor appears twice"); #endif - return(false); + return false; } } @@ -495,7 +492,18 @@ unsigned BranchFolder::ComputeSameTails(unsigned CurHash, CurMPIter->second, I->second, TrialBBI1, TrialBBI2); - if (CommonTailLen >= minCommonTailLength) { + // If we will have to split a block, there should be at least + // minCommonTailLength instructions in common; if not, at worst + // we will be replacing a fallthrough into the common tail with a + // branch, which at worst breaks even with falling through into + // the duplicated common tail, so 1 instruction in common is enough. + // We will always pick a block we do not have to split as the common + // tail if there is one. + // (Empty blocks will get forwarded and need not be considered.) + if (CommonTailLen >= minCommonTailLength || + (CommonTailLen > 0 && + (TrialBBI1==CurMPIter->second->begin() || + TrialBBI2==I->second->begin()))) { if (CommonTailLen > maxCommonTailLength) { SameTails.clear(); maxCommonTailLength = CommonTailLen; @@ -518,18 +526,20 @@ unsigned BranchFolder::ComputeSameTails(unsigned CurHash, void BranchFolder::RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB, MachineBasicBlock* PredBB) { - for (MPIterator CurMPIter = prior(MergePotentials.end()), - B = MergePotentials.begin(); + MPIterator CurMPIter, B; + for (CurMPIter = prior(MergePotentials.end()), B = MergePotentials.begin(); CurMPIter->first==CurHash; --CurMPIter) { // Put the unconditional branch back, if we need one. MachineBasicBlock *CurMBB = CurMPIter->second; if (SuccBB && CurMBB != PredBB) FixTail(CurMBB, SuccBB, TII); - MergePotentials.erase(CurMPIter); - if (CurMPIter==B) + if (CurMPIter==B) break; } + if (CurMPIter->first!=CurHash) + CurMPIter++; + MergePotentials.erase(CurMPIter, MergePotentials.end()); } /// CreateCommonTailOnlyBlock - None of the blocks to be tail-merged consist @@ -586,7 +596,7 @@ bool BranchFolder::TryMergeBlocks(MachineBasicBlock *SuccBB, unsigned minCommonTailLength = (SuccBB ? 1 : 2) + 1; MadeChange = false; - DOUT << "\nTryMergeBlocks " << MergePotentials.size(); + DOUT << "\nTryMergeBlocks " << MergePotentials.size() << '\n'; // Sort by hash value so that blocks with identical end sequences sort // together. @@ -688,8 +698,7 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { // transformations.) for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { - if (!I->succ_empty() && I->pred_size() >= 2 && - I->pred_size() < TailMergeThreshold) { + if (I->pred_size() >= 2 && I->pred_size() < TailMergeThreshold) { MachineBasicBlock *IBB = I; MachineBasicBlock *PredBB = prior(I); MergePotentials.clear(); @@ -701,11 +710,11 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { if (PBB==IBB) continue; MachineBasicBlock *TBB = 0, *FBB = 0; - std::vector Cond; - if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond)) { + SmallVector Cond; + if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond, true)) { // Failing case: IBB is the target of a cbr, and // we cannot reverse the branch. - std::vector NewCond(Cond); + SmallVector NewCond(Cond); if (!Cond.empty() && TBB==IBB) { if (TII->ReverseBranchCondition(NewCond)) continue; @@ -794,7 +803,7 @@ bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB, bool BranchUnAnalyzable, MachineBasicBlock *TBB, MachineBasicBlock *FBB, - const std::vector &Cond) { + const SmallVectorImpl &Cond) { MachineFunction::iterator Fallthrough = CurBB; ++Fallthrough; // If FallthroughBlock is off the end of the function, it can't fall through. @@ -835,8 +844,8 @@ bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB, /// bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB) { MachineBasicBlock *TBB = 0, *FBB = 0; - std::vector Cond; - bool CurUnAnalyzable = TII->AnalyzeBranch(*CurBB, TBB, FBB, Cond); + SmallVector Cond; + bool CurUnAnalyzable = TII->AnalyzeBranch(*CurBB, TBB, FBB, Cond, true); return CanFallThrough(CurBB, CurUnAnalyzable, TBB, FBB, Cond); } @@ -899,9 +908,9 @@ void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB)); MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; - std::vector PriorCond; + SmallVector PriorCond; bool PriorUnAnalyzable = - TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond); + TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true); if (!PriorUnAnalyzable) { // If the CFG for the prior block has extra edges, remove them. MadeChange |= PrevBB.CorrectExtraCFGEdges(PriorTBB, PriorFBB, @@ -943,7 +952,7 @@ void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { // if the branch condition is reversible, reverse the branch to create a // fall-through. if (PriorTBB == MBB) { - std::vector NewPriorCond(PriorCond); + SmallVector NewPriorCond(PriorCond); if (!TII->ReverseBranchCondition(NewPriorCond)) { TII->RemoveBranch(PrevBB); TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond); @@ -993,7 +1002,7 @@ void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { if (DoTransform) { // Reverse the branch so we will fall through on the previous true cond. - std::vector NewPriorCond(PriorCond); + SmallVector NewPriorCond(PriorCond); if (!TII->ReverseBranchCondition(NewPriorCond)) { DOUT << "\nMoving MBB: " << *MBB; DOUT << "To make fallthrough to: " << *PriorTBB << "\n"; @@ -1013,8 +1022,8 @@ void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { // Analyze the branch in the current block. MachineBasicBlock *CurTBB = 0, *CurFBB = 0; - std::vector CurCond; - bool CurUnAnalyzable = TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond); + SmallVector CurCond; + bool CurUnAnalyzable= TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true); if (!CurUnAnalyzable) { // If the CFG for the prior block has extra edges, remove them. MadeChange |= MBB->CorrectExtraCFGEdges(CurTBB, CurFBB, !CurCond.empty()); @@ -1025,7 +1034,7 @@ void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { // we want: // Loop: xxx; jncc Loop; jmp Out if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) { - std::vector NewCond(CurCond); + SmallVector NewCond(CurCond); if (!TII->ReverseBranchCondition(NewCond)) { TII->RemoveBranch(*MBB); TII->InsertBranch(*MBB, CurFBB, CurTBB, NewCond);