X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FBranchFolding.cpp;h=3b30423c52b078fe46e28ced3a327c4a1624343c;hb=f9410141f703f4e8a6aba717617ef958249f6d13;hp=a13fd607a5a3537748315fcd9c802662720c82bf;hpb=6ae83faadf715c398e637424a764f6b02f0b6df2;p=oota-llvm.git diff --git a/lib/CodeGen/BranchFolding.cpp b/lib/CodeGen/BranchFolding.cpp index a13fd607a5a..3b30423c52b 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(100), 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); @@ -71,10 +71,18 @@ namespace { MachineBasicBlock *NewDest); MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB, MachineBasicBlock::iterator BBI1); + unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength); + void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB, + MachineBasicBlock* PredBB); + unsigned CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB, + unsigned maxCommonTailLength); typedef std::pair MergePotentialsElt; - std::vector MergePotentials; typedef std::vector::iterator MPIterator; + std::vector MergePotentials; + + typedef std::pair SameTailElt; + std::vector SameTails; const TargetRegisterInfo *RegInfo; RegScavenger *RS; @@ -87,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; } @@ -106,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 @@ -183,7 +190,7 @@ 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; + SmallVector Cond; if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond)) EverMadeChange |= MBB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty()); EverMadeChange |= OptimizeImpDefsBlock(MBB); @@ -221,20 +228,19 @@ bool BranchFolder::runOnMachineFunction(MachineFunction &MF) { // 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. - std::vector JTIsLive; - JTIsLive.resize(JTs.size()); + 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.isJumpTableIndex()) continue; + if (!Op.isJTI()) continue; unsigned NewIdx = JTMapping[Op.getIndex()]; Op.setIndex(NewIdx); // Remember that this JT is live. - JTIsLive[NewIdx] = true; + JTIsLive.set(NewIdx); } } @@ -242,7 +248,7 @@ bool BranchFolder::runOnMachineFunction(MachineFunction &MF) { // 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[i]) { + if (!JTIsLive.test(i)) { JTI->RemoveJumpTable(i); EverMadeChange = true; } @@ -358,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; } @@ -368,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); @@ -418,42 +422,6 @@ static unsigned EstimateRuntime(MachineBasicBlock::iterator I, return Time; } -/// ShouldSplitFirstBlock - We need to either split MBB1 at MBB1I or MBB2 at -/// MBB2I and then insert an unconditional branch in the other block. Determine -/// which is the best to split -static bool ShouldSplitFirstBlock(MachineBasicBlock *MBB1, - MachineBasicBlock::iterator MBB1I, - MachineBasicBlock *MBB2, - MachineBasicBlock::iterator MBB2I, - MachineBasicBlock *PredBB) { - // If one block is the entry block, split the other one; we can't generate - // a branch to the entry block, as its label is not emitted. - MachineBasicBlock *Entry = MBB1->getParent()->begin(); - if (MBB1 == Entry) - return false; - if (MBB2 == Entry) - return true; - - // If one block falls through into the common successor, choose that - // one to split; it is one instruction less to do that. - if (PredBB) { - if (MBB1 == PredBB) - return true; - else if (MBB2 == PredBB) - return false; - } - // TODO: if we had some notion of which block was hotter, we could split - // the hot block, so it is the fall-through. Since we don't have profile info - // make a decision based on which will hurt most to split. - unsigned MBB1Time = EstimateRuntime(MBB1->begin(), MBB1I); - unsigned MBB2Time = EstimateRuntime(MBB2->begin(), MBB2I); - - // If the MBB1 prefix takes "less time" to run than the MBB2 prefix, split the - // MBB1 block so it falls through. This will penalize the MBB2 path, but will - // have a lower overall impact on the program execution. - return MBB1Time < MBB2Time; -} - // CurMBB needs to add an unconditional branch to SuccMBB (we removed these // branches temporarily for tail merging). In the case where CurMBB ends // with a conditional branch to the next block, optimize by reversing the @@ -464,11 +432,11 @@ 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)) { MachineBasicBlock *NextBB = I; - if (TBB == NextBB && Cond.size() && !FBB) { + if (TBB == NextBB && !Cond.empty() && !FBB) { if (!TII->ReverseBranchCondition(Cond)) { TII->RemoveBranch(*CurMBB); TII->InsertBranch(*CurMBB, SuccBB, NULL, Cond); @@ -476,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, @@ -499,6 +467,119 @@ static bool MergeCompare(const std::pair &p, } } +/// ComputeSameTails - Look through all the blocks in MergePotentials that have +/// hash CurHash (guaranteed to match the last element). Build the vector +/// SameTails of all those that have the (same) largest number of instructions +/// in common of any pair of these blocks. SameTails entries contain an +/// iterator into MergePotentials (from which the MachineBasicBlock can be +/// found) and a MachineBasicBlock::iterator into that MBB indicating the +/// instruction where the matching code sequence begins. +/// Order of elements in SameTails is the reverse of the order in which +/// those blocks appear in MergePotentials (where they are not necessarily +/// consecutive). +unsigned BranchFolder::ComputeSameTails(unsigned CurHash, + unsigned minCommonTailLength) { + unsigned maxCommonTailLength = 0U; + SameTails.clear(); + MachineBasicBlock::iterator TrialBBI1, TrialBBI2; + MPIterator HighestMPIter = prior(MergePotentials.end()); + for (MPIterator CurMPIter = prior(MergePotentials.end()), + B = MergePotentials.begin(); + CurMPIter!=B && CurMPIter->first==CurHash; + --CurMPIter) { + for (MPIterator I = prior(CurMPIter); I->first==CurHash ; --I) { + unsigned CommonTailLen = ComputeCommonTailLength( + CurMPIter->second, + I->second, + TrialBBI1, TrialBBI2); + // 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; + HighestMPIter = CurMPIter; + SameTails.push_back(std::make_pair(CurMPIter, TrialBBI1)); + } + if (HighestMPIter == CurMPIter && + CommonTailLen == maxCommonTailLength) + SameTails.push_back(std::make_pair(I, TrialBBI2)); + } + if (I==B) + break; + } + } + return maxCommonTailLength; +} + +/// RemoveBlocksWithHash - Remove all blocks with hash CurHash from +/// MergePotentials, restoring branches at ends of blocks as appropriate. +void BranchFolder::RemoveBlocksWithHash(unsigned CurHash, + MachineBasicBlock* SuccBB, + MachineBasicBlock* PredBB) { + 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); + if (CurMPIter==B) + break; + } + if (CurMPIter->first!=CurHash) + CurMPIter++; + MergePotentials.erase(CurMPIter, MergePotentials.end()); +} + +/// CreateCommonTailOnlyBlock - None of the blocks to be tail-merged consist +/// only of the common tail. Create a block that does by splitting one. +unsigned BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB, + unsigned maxCommonTailLength) { + unsigned i, commonTailIndex; + unsigned TimeEstimate = ~0U; + for (i=0, commonTailIndex=0; isecond==PredBB) { + commonTailIndex = i; + break; + } + // Otherwise, make a (fairly bogus) choice based on estimate of + // how long it will take the various blocks to execute. + unsigned t = EstimateRuntime(SameTails[i].first->second->begin(), + SameTails[i].second); + if (t<=TimeEstimate) { + TimeEstimate = t; + commonTailIndex = i; + } + } + + MachineBasicBlock::iterator BBI = SameTails[commonTailIndex].second; + MachineBasicBlock *MBB = SameTails[commonTailIndex].first->second; + + DOUT << "\nSplitting " << MBB->getNumber() << ", size " << + maxCommonTailLength; + + MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI); + SameTails[commonTailIndex].first->second = newMBB; + SameTails[commonTailIndex].second = newMBB->begin(); + // If we split PredBB, newMBB is the new predecessor. + if (PredBB==MBB) + PredBB = newMBB; + + return commonTailIndex; +} + // See if any of the blocks in MergePotentials (which all have a common single // successor, or all have no successor) can be tail-merged. If there is a // successor, any blocks in MergePotentials that are not tail-merged and @@ -509,10 +590,6 @@ static bool MergeCompare(const std::pair &p, bool BranchFolder::TryMergeBlocks(MachineBasicBlock *SuccBB, MachineBasicBlock* PredBB) { - // We cannot jump to the entry block, which affects various choices below. - MachineBasicBlock *Entry = MergePotentials.begin()->second-> - getParent()->begin(); - // It doesn't make sense to save a single instruction since tail merging // will add a jump. // FIXME: Ask the target to provide the threshold? @@ -520,143 +597,65 @@ bool BranchFolder::TryMergeBlocks(MachineBasicBlock *SuccBB, MadeChange = false; DOUT << "\nTryMergeBlocks " << MergePotentials.size(); + // Sort by hash value so that blocks with identical end sequences sort // together. - std::stable_sort(MergePotentials.begin(), MergePotentials.end(), MergeCompare); + std::stable_sort(MergePotentials.begin(), MergePotentials.end(),MergeCompare); // Walk through equivalence sets looking for actual exact matches. while (MergePotentials.size() > 1) { unsigned CurHash = prior(MergePotentials.end())->first; - // Look through all the other blocks that have the same hash as this - // one, and build a vector of all those that have the (same) largest number - // of instructions in common. - // Order of elements in SameTails is the reverse of the order in which - // those blocks appear in MergePotentials (where they are not necessarily - // consecutive). - typedef std::pair SameTailElt; - std::vector SameTails; - - unsigned maxCommonTailLength = 0U; - SameTails.clear(); - MachineBasicBlock::iterator TrialBBI1, TrialBBI2; - MPIterator HighestMPIter = prior(MergePotentials.end()); - for (MPIterator CurMPIter = prior(MergePotentials.end()), - B = MergePotentials.begin(); - CurMPIter!=B && CurMPIter->first==CurHash; - --CurMPIter) { - for (MPIterator I = prior(CurMPIter); I->first==CurHash ; --I) { - unsigned CommonTailLen = ComputeCommonTailLength( - CurMPIter->second, - I->second, - TrialBBI1, TrialBBI2); - if (CommonTailLen >= minCommonTailLength) { - if (CommonTailLen > maxCommonTailLength) { - SameTails.clear(); - maxCommonTailLength = CommonTailLen; - HighestMPIter = CurMPIter; - SameTails.push_back(std::make_pair(CurMPIter, TrialBBI1)); - } - if (HighestMPIter == CurMPIter && - CommonTailLen == maxCommonTailLength) - SameTails.push_back(std::make_pair(I, TrialBBI2)); - } - if (I==B) - break; - } - } + // Build SameTails, identifying the set of blocks with this hash code + // and with the maximum number of instructions in common. + unsigned maxCommonTailLength = ComputeSameTails(CurHash, + minCommonTailLength); // If we didn't find any pair that has at least minCommonTailLength // instructions in common, remove all blocks with this hash code and retry. if (SameTails.empty()) { - for (MPIterator 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) - break; - } + RemoveBlocksWithHash(CurHash, SuccBB, PredBB); continue; } // If one of the blocks is the entire common tail (and not the entry - // block, which we can't jump to), treat all blocks with this same - // tail at once. - unsigned int i; - for (i=0; isecond; - if (MBB->begin() == SameTails[i].second && MBB != Entry) - break; - } - if (i!=SameTails.size()) { + // block, which we can't jump to), we can treat all blocks with this same + // tail at once. Use PredBB if that is one of the possibilities, as that + // will not introduce any extra branches. + MachineBasicBlock *EntryBB = MergePotentials.begin()->second-> + getParent()->begin(); + unsigned int commonTailIndex, i; + for (commonTailIndex=SameTails.size(), i=0; isecond; - // MBB is common tail. Adjust all other BB's to jump to this one. - // Traversal must be forwards so erases work. - DOUT << "\nUsing common tail " << MBB->getNumber() << " for "; - for (unsigned int j=0; jsecond->getNumber() << ","; - // Hack the end off BB j, making it jump to BB i instead. - ReplaceTailWithBranchTo(SameTails[j].second, MBB); - // This modifies BB j, so remove it from the worklist. - MergePotentials.erase(SameTails[j].first); + if (MBB->begin() == SameTails[i].second && MBB != EntryBB) { + commonTailIndex = i; + if (MBB==PredBB) + break; } - DOUT << "\n"; - // We leave i in the worklist in case there are other blocks that - // match it with a smaller number of instructions. - MadeChange = true; - continue; } - // Otherwise, merge the 2 blocks in SameTails that are latest in - // MergePotentials; these are at indices 0 and 1 in SameTails. - MachineBasicBlock::iterator BBI1 = (SameTails[0]).second; - MachineBasicBlock::iterator BBI2 = (SameTails[1]).second; - MachineBasicBlock *MBB1 = (SameTails[0]).first->second; - MachineBasicBlock *MBB2 = (SameTails[1]).first->second; - - DOUT << "\nMerging " << MBB1->getNumber() << "," << - MBB2->getNumber() << ", size " << maxCommonTailLength; - - // Neither block is the entire common tail; split the tail of one block - // to make it redundant with the other tail. We cannot jump to the - // entry block, so if one block is the entry block, split the other one. - - // The second half of the split block will remain in SameTails, and will - // consist entirely of common code. Thus in the case where there are multiple - // blocks that would all need to be split, the next iteration of the - // outer loop will handle all the rest of them. - - // Decide whether we want to split MBB1 or MBB2. - if (ShouldSplitFirstBlock(MBB1, BBI1, MBB2, BBI2, PredBB)) { - MBB1 = SplitMBBAt(*MBB1, BBI1); - BBI1 = MBB1->begin(); - SameTails[0].first->second = MBB1; - } else { - MBB2 = SplitMBBAt(*MBB2, BBI2); - BBI2 = MBB2->begin(); - SameTails[1].first->second = MBB2; + if (commonTailIndex==SameTails.size()) { + // None of the blocks consist entirely of the common tail. + // Split a block so that one does. + commonTailIndex = CreateCommonTailOnlyBlock(PredBB, maxCommonTailLength); } - - if (MBB2->begin() == BBI2 && MBB2 != Entry) { - // Hack the end off MBB1, making it jump to MBB2 instead. - ReplaceTailWithBranchTo(BBI1, MBB2); - // This modifies MBB1, so remove it from the worklist. - MergePotentials.erase(SameTails[0].first); - } else { - assert(MBB1->begin() == BBI1 && MBB1 != Entry && - "Didn't split block correctly?"); - // Hack the end off MBB2, making it jump to MBB1 instead. - ReplaceTailWithBranchTo(BBI2, MBB1); - // This modifies MBB2, so remove it from the worklist. - MergePotentials.erase(SameTails[1].first); + + MachineBasicBlock *MBB = SameTails[commonTailIndex].first->second; + // MBB is common tail. Adjust all other BB's to jump to this one. + // Traversal must be forwards so erases work. + DOUT << "\nUsing common tail " << MBB->getNumber() << " for "; + for (unsigned int i=0; isecond->getNumber() << ","; + // Hack the end off BB i, making it jump to BB commonTailIndex instead. + ReplaceTailWithBranchTo(SameTails[i].second, MBB); + // BB i is no longer a predecessor of SuccBB; remove it from the worklist. + MergePotentials.erase(SameTails[i].first); } + DOUT << "\n"; + // We leave commonTailIndex in the worklist in case there are other blocks + // that match it with a smaller number of instructions. MadeChange = true; } return MadeChange; @@ -699,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(); @@ -712,12 +710,12 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { if (PBB==IBB) continue; MachineBasicBlock *TBB = 0, *FBB = 0; - std::vector Cond; + SmallVector Cond; if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond)) { // Failing case: IBB is the target of a cbr, and // we cannot reverse the branch. - std::vector NewCond(Cond); - if (Cond.size() && TBB==IBB) { + SmallVector NewCond(Cond); + if (!Cond.empty() && TBB==IBB) { if (TII->ReverseBranchCondition(NewCond)) continue; // This is the QBB case described above @@ -747,9 +745,9 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { } } // Remove the unconditional branch at the end, if any. - if (TBB && (Cond.size()==0 || FBB)) { + if (TBB && (Cond.empty() || FBB)) { TII->RemoveBranch(*PBB); - if (Cond.size()) + if (!Cond.empty()) // reinsert conditional branch only, for now TII->InsertBranch(*PBB, (TBB==IBB) ? FBB : TBB, 0, NewCond); } @@ -759,12 +757,11 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { if (MergePotentials.size() >= 2) MadeChange |= TryMergeBlocks(I, PredBB); // Reinsert an unconditional branch if needed. - // The 1 below can be either an original single predecessor, or a result - // of removing blocks in TryMergeBlocks. + // The 1 below can occur as a result of removing blocks in TryMergeBlocks. PredBB = prior(I); // this may have been changed in TryMergeBlocks if (MergePotentials.size()==1 && - (MergePotentials.begin())->second != PredBB) - FixTail((MergePotentials.begin())->second, I, TII); + MergePotentials.begin()->second != PredBB) + FixTail(MergePotentials.begin()->second, I, TII); } } return MadeChange; @@ -804,8 +801,9 @@ bool BranchFolder::OptimizeBranches(MachineFunction &MF) { /// bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB, bool BranchUnAnalyzable, - MachineBasicBlock *TBB, MachineBasicBlock *FBB, - const std::vector &Cond) { + MachineBasicBlock *TBB, + MachineBasicBlock *FBB, + const SmallVectorImpl &Cond) { MachineFunction::iterator Fallthrough = CurBB; ++Fallthrough; // If FallthroughBlock is off the end of the function, it can't fall through. @@ -846,7 +844,7 @@ bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB, /// bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB) { MachineBasicBlock *TBB = 0, *FBB = 0; - std::vector Cond; + SmallVector Cond; bool CurUnAnalyzable = TII->AnalyzeBranch(*CurBB, TBB, FBB, Cond); return CanFallThrough(CurBB, CurUnAnalyzable, TBB, FBB, Cond); } @@ -910,7 +908,7 @@ 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); if (!PriorUnAnalyzable) { @@ -954,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); @@ -1004,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"; @@ -1024,7 +1022,7 @@ void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { // Analyze the branch in the current block. MachineBasicBlock *CurTBB = 0, *CurFBB = 0; - std::vector CurCond; + SmallVector CurCond; bool CurUnAnalyzable = TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond); if (!CurUnAnalyzable) { // If the CFG for the prior block has extra edges, remove them. @@ -1036,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);