X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FBranchFolding.cpp;h=d25152b1e436ca5ccd62dd36d1267a48172b40ba;hb=08ada178b8a9f2b380fb6c2bc2693c615532278e;hp=f629ae75f3aee9bf0eb2e163529b1960039e8235;hpb=04478e56f736325d3567e7c0efe2bb5c2766c63b;p=oota-llvm.git diff --git a/lib/CodeGen/BranchFolding.cpp b/lib/CodeGen/BranchFolding.cpp index f629ae75f3a..d25152b1e43 100644 --- a/lib/CodeGen/BranchFolding.cpp +++ b/lib/CodeGen/BranchFolding.cpp @@ -27,6 +27,7 @@ #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/STLExtras.h" @@ -42,18 +43,18 @@ static cl::opt FlagEnableTailMerge("enable-tail-merge", static cl::opt TailMergeThreshold("tail-merge-threshold", cl::desc("Max number of predecessors to consider tail merging"), - cl::init(100), cl::Hidden); + 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 +96,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 +115,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 +191,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 +236,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 +365,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,10 +375,12 @@ 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. NewMBB->transferSuccessors(&CurMBB); @@ -413,7 +415,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; @@ -431,9 +433,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)) { @@ -443,7 +445,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, @@ -460,9 +462,9 @@ static bool MergeCompare(const std::pair &p, // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing // an object with itself. #ifndef _GLIBCXX_DEBUG - assert(0 && "Predecessor appears twice"); + llvm_unreachable("Predecessor appears twice"); #endif - return(false); + return false; } } @@ -595,7 +597,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. @@ -697,8 +699,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(); @@ -710,11 +711,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; @@ -803,7 +804,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. @@ -844,8 +845,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); } @@ -892,8 +893,24 @@ void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { while (!MBB->pred_empty()) { MachineBasicBlock *Pred = *(MBB->pred_end()-1); Pred->ReplaceUsesOfBlockWith(MBB, FallThrough); + // If this resulted in a predecessor with true and false edges + // both going to the fallthrough block, clean up; + // BranchFolding doesn't like this. + MachineBasicBlock::succ_iterator SI = Pred->succ_begin(); + bool found = false; + while (SI != Pred->succ_end()) { + if (*SI == FallThrough) { + if (!found) { + found = true; + ++SI; + } else { + SI = Pred->removeSuccessor(SI); + } + } else { + ++SI; + } + } } - // If MBB was the target of a jump table, update jump tables to go to the // fallthrough instead. MBB->getParent()->getJumpTableInfo()-> @@ -908,9 +925,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, @@ -952,7 +969,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); @@ -1002,7 +1019,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"; @@ -1022,8 +1039,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()); @@ -1034,7 +1051,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); @@ -1092,6 +1109,21 @@ void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { } else { DidChange = true; PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB); + // If this change resulted in PMBB ending in a conditional + // branch where both conditions go to the same destination, + // change this to an unconditional branch (and fix the CFG). + MachineBasicBlock *NewCurTBB = 0, *NewCurFBB = 0; + SmallVector NewCurCond; + bool NewCurUnAnalyzable = TII->AnalyzeBranch(*PMBB, NewCurTBB, + NewCurFBB, NewCurCond, true); + if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) { + TII->RemoveBranch(*PMBB); + NewCurCond.clear(); + TII->InsertBranch(*PMBB, NewCurTBB, 0, NewCurCond); + MadeChange = true; + ++NumBranchOpts; + PMBB->CorrectExtraCFGEdges(NewCurTBB, NewCurFBB, false); + } } }