LLVM API Documentation

BranchFolding.cpp

Go to the documentation of this file.
00001 //===-- BranchFolding.cpp - Fold machine code branch instructions ---------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass forwards branches to unconditional branches to make them branch
00011 // directly to the target block.  This pass often results in dead MBB's, which
00012 // it then removes.
00013 //
00014 // Note that this pass must be run after register allocation, it cannot handle
00015 // SSA form.
00016 //
00017 //===----------------------------------------------------------------------===//
00018 
00019 #define DEBUG_TYPE "branchfolding"
00020 #include "llvm/CodeGen/Passes.h"
00021 #include "llvm/CodeGen/MachineModuleInfo.h"
00022 #include "llvm/CodeGen/MachineFunctionPass.h"
00023 #include "llvm/CodeGen/MachineJumpTableInfo.h"
00024 #include "llvm/CodeGen/RegisterScavenging.h"
00025 #include "llvm/Target/TargetInstrInfo.h"
00026 #include "llvm/Target/TargetMachine.h"
00027 #include "llvm/Target/TargetRegisterInfo.h"
00028 #include "llvm/Support/CommandLine.h"
00029 #include "llvm/Support/Debug.h"
00030 #include "llvm/Support/ErrorHandling.h"
00031 #include "llvm/ADT/SmallSet.h"
00032 #include "llvm/ADT/Statistic.h"
00033 #include "llvm/ADT/STLExtras.h"
00034 #include <algorithm>
00035 using namespace llvm;
00036 
00037 STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
00038 STATISTIC(NumBranchOpts, "Number of branches optimized");
00039 STATISTIC(NumTailMerge , "Number of block tails merged");
00040 static cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge", 
00041                               cl::init(cl::BOU_UNSET), cl::Hidden);
00042 // Throttle for huge numbers of predecessors (compile speed problems)
00043 static cl::opt<unsigned>
00044 TailMergeThreshold("tail-merge-threshold", 
00045           cl::desc("Max number of predecessors to consider tail merging"),
00046           cl::init(150), cl::Hidden);
00047 
00048 namespace {
00049   struct VISIBILITY_HIDDEN BranchFolder : public MachineFunctionPass {
00050     static char ID;
00051     explicit BranchFolder(bool defaultEnableTailMerge) : 
00052       MachineFunctionPass(&ID) {
00053       switch (FlagEnableTailMerge) {
00054         case cl::BOU_UNSET: EnableTailMerge = defaultEnableTailMerge; break;
00055         case cl::BOU_TRUE: EnableTailMerge = true; break;
00056         case cl::BOU_FALSE: EnableTailMerge = false; break;
00057       }
00058     }
00059 
00060     virtual bool runOnMachineFunction(MachineFunction &MF);
00061     virtual const char *getPassName() const { return "Control Flow Optimizer"; }
00062     const TargetInstrInfo *TII;
00063     MachineModuleInfo *MMI;
00064     bool MadeChange;
00065   private:
00066     // Tail Merging.
00067     bool EnableTailMerge;
00068     bool TailMergeBlocks(MachineFunction &MF);
00069     bool TryMergeBlocks(MachineBasicBlock* SuccBB,
00070                         MachineBasicBlock* PredBB);
00071     void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
00072                                  MachineBasicBlock *NewDest);
00073     MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
00074                                   MachineBasicBlock::iterator BBI1);
00075     unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength);
00076     void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
00077                                                 MachineBasicBlock* PredBB);
00078     unsigned CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
00079                                        unsigned maxCommonTailLength);
00080 
00081     typedef std::pair<unsigned,MachineBasicBlock*> MergePotentialsElt;
00082     typedef std::vector<MergePotentialsElt>::iterator MPIterator;
00083     std::vector<MergePotentialsElt> MergePotentials;
00084 
00085     typedef std::pair<MPIterator, MachineBasicBlock::iterator> SameTailElt;
00086     std::vector<SameTailElt> SameTails;
00087 
00088     const TargetRegisterInfo *RegInfo;
00089     RegScavenger *RS;
00090     // Branch optzn.
00091     bool OptimizeBranches(MachineFunction &MF);
00092     void OptimizeBlock(MachineBasicBlock *MBB);
00093     void RemoveDeadBlock(MachineBasicBlock *MBB);
00094     bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
00095     
00096     bool CanFallThrough(MachineBasicBlock *CurBB);
00097     bool CanFallThrough(MachineBasicBlock *CurBB, bool BranchUnAnalyzable,
00098                         MachineBasicBlock *TBB, MachineBasicBlock *FBB,
00099                         const SmallVectorImpl<MachineOperand> &Cond);
00100   };
00101   char BranchFolder::ID = 0;
00102 }
00103 
00104 FunctionPass *llvm::createBranchFoldingPass(bool DefaultEnableTailMerge) { 
00105       return new BranchFolder(DefaultEnableTailMerge); }
00106 
00107 /// RemoveDeadBlock - Remove the specified dead machine basic block from the
00108 /// function, updating the CFG.
00109 void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
00110   assert(MBB->pred_empty() && "MBB must be dead!");
00111   DOUT << "\nRemoving MBB: " << *MBB;
00112   
00113   MachineFunction *MF = MBB->getParent();
00114   // drop all successors.
00115   while (!MBB->succ_empty())
00116     MBB->removeSuccessor(MBB->succ_end()-1);
00117   
00118   // If there are any labels in the basic block, unregister them from
00119   // MachineModuleInfo.
00120   if (MMI && !MBB->empty()) {
00121     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
00122          I != E; ++I) {
00123       if (I->isLabel())
00124         // The label ID # is always operand #0, an immediate.
00125         MMI->InvalidateLabel(I->getOperand(0).getImm());
00126     }
00127   }
00128   
00129   // Remove the block.
00130   MF->erase(MBB);
00131 }
00132 
00133 /// OptimizeImpDefsBlock - If a basic block is just a bunch of implicit_def
00134 /// followed by terminators, and if the implicitly defined registers are not
00135 /// used by the terminators, remove those implicit_def's. e.g.
00136 /// BB1:
00137 ///   r0 = implicit_def
00138 ///   r1 = implicit_def
00139 ///   br
00140 /// This block can be optimized away later if the implicit instructions are
00141 /// removed.
00142 bool BranchFolder::OptimizeImpDefsBlock(MachineBasicBlock *MBB) {
00143   SmallSet<unsigned, 4> ImpDefRegs;
00144   MachineBasicBlock::iterator I = MBB->begin();
00145   while (I != MBB->end()) {
00146     if (I->getOpcode() != TargetInstrInfo::IMPLICIT_DEF)
00147       break;
00148     unsigned Reg = I->getOperand(0).getReg();
00149     ImpDefRegs.insert(Reg);
00150     for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg);
00151          unsigned SubReg = *SubRegs; ++SubRegs)
00152       ImpDefRegs.insert(SubReg);
00153     ++I;
00154   }
00155   if (ImpDefRegs.empty())
00156     return false;
00157 
00158   MachineBasicBlock::iterator FirstTerm = I;
00159   while (I != MBB->end()) {
00160     if (!TII->isUnpredicatedTerminator(I))
00161       return false;
00162     // See if it uses any of the implicitly defined registers.
00163     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
00164       MachineOperand &MO = I->getOperand(i);
00165       if (!MO.isReg() || !MO.isUse())
00166         continue;
00167       unsigned Reg = MO.getReg();
00168       if (ImpDefRegs.count(Reg))
00169         return false;
00170     }
00171     ++I;
00172   }
00173 
00174   I = MBB->begin();
00175   while (I != FirstTerm) {
00176     MachineInstr *ImpDefMI = &*I;
00177     ++I;
00178     MBB->erase(ImpDefMI);
00179   }
00180 
00181   return true;
00182 }
00183 
00184 bool BranchFolder::runOnMachineFunction(MachineFunction &MF) {
00185   TII = MF.getTarget().getInstrInfo();
00186   if (!TII) return false;
00187 
00188   RegInfo = MF.getTarget().getRegisterInfo();
00189 
00190   // Fix CFG.  The later algorithms expect it to be right.
00191   bool EverMadeChange = false;
00192   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; I++) {
00193     MachineBasicBlock *MBB = I, *TBB = 0, *FBB = 0;
00194     SmallVector<MachineOperand, 4> Cond;
00195     if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, true))
00196       EverMadeChange |= MBB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
00197     EverMadeChange |= OptimizeImpDefsBlock(MBB);
00198   }
00199 
00200   RS = RegInfo->requiresRegisterScavenging(MF) ? new RegScavenger() : NULL;
00201 
00202   MMI = getAnalysisIfAvailable<MachineModuleInfo>();
00203 
00204   bool MadeChangeThisIteration = true;
00205   while (MadeChangeThisIteration) {
00206     MadeChangeThisIteration = false;
00207     MadeChangeThisIteration |= TailMergeBlocks(MF);
00208     MadeChangeThisIteration |= OptimizeBranches(MF);
00209     EverMadeChange |= MadeChangeThisIteration;
00210   }
00211 
00212   // See if any jump tables have become mergable or dead as the code generator
00213   // did its thing.
00214   MachineJumpTableInfo *JTI = MF.getJumpTableInfo();
00215   const std::vector<MachineJumpTableEntry> &JTs = JTI->getJumpTables();
00216   if (!JTs.empty()) {
00217     // Figure out how these jump tables should be merged.
00218     std::vector<unsigned> JTMapping;
00219     JTMapping.reserve(JTs.size());
00220     
00221     // We always keep the 0th jump table.
00222     JTMapping.push_back(0);
00223 
00224     // Scan the jump tables, seeing if there are any duplicates.  Note that this
00225     // is N^2, which should be fixed someday.
00226     for (unsigned i = 1, e = JTs.size(); i != e; ++i)
00227       JTMapping.push_back(JTI->getJumpTableIndex(JTs[i].MBBs));
00228     
00229     // If a jump table was merge with another one, walk the function rewriting
00230     // references to jump tables to reference the new JT ID's.  Keep track of
00231     // whether we see a jump table idx, if not, we can delete the JT.
00232     BitVector JTIsLive(JTs.size());
00233     for (MachineFunction::iterator BB = MF.begin(), E = MF.end();
00234          BB != E; ++BB) {
00235       for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end();
00236            I != E; ++I)
00237         for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) {
00238           MachineOperand &Op = I->getOperand(op);
00239           if (!Op.isJTI()) continue;
00240           unsigned NewIdx = JTMapping[Op.getIndex()];
00241           Op.setIndex(NewIdx);
00242 
00243           // Remember that this JT is live.
00244           JTIsLive.set(NewIdx);
00245         }
00246     }
00247    
00248     // Finally, remove dead jump tables.  This happens either because the
00249     // indirect jump was unreachable (and thus deleted) or because the jump
00250     // table was merged with some other one.
00251     for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i)
00252       if (!JTIsLive.test(i)) {
00253         JTI->RemoveJumpTable(i);
00254         EverMadeChange = true;
00255       }
00256   }
00257   
00258   delete RS;
00259   return EverMadeChange;
00260 }
00261 
00262 //===----------------------------------------------------------------------===//
00263 //  Tail Merging of Blocks
00264 //===----------------------------------------------------------------------===//
00265 
00266 /// HashMachineInstr - Compute a hash value for MI and its operands.
00267 static unsigned HashMachineInstr(const MachineInstr *MI) {
00268   unsigned Hash = MI->getOpcode();
00269   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
00270     const MachineOperand &Op = MI->getOperand(i);
00271     
00272     // Merge in bits from the operand if easy.
00273     unsigned OperandHash = 0;
00274     switch (Op.getType()) {
00275     case MachineOperand::MO_Register:          OperandHash = Op.getReg(); break;
00276     case MachineOperand::MO_Immediate:         OperandHash = Op.getImm(); break;
00277     case MachineOperand::MO_MachineBasicBlock:
00278       OperandHash = Op.getMBB()->getNumber();
00279       break;
00280     case MachineOperand::MO_FrameIndex:
00281     case MachineOperand::MO_ConstantPoolIndex:
00282     case MachineOperand::MO_JumpTableIndex:
00283       OperandHash = Op.getIndex();
00284       break;
00285     case MachineOperand::MO_GlobalAddress:
00286     case MachineOperand::MO_ExternalSymbol:
00287       // Global address / external symbol are too hard, don't bother, but do
00288       // pull in the offset.
00289       OperandHash = Op.getOffset();
00290       break;
00291     default: break;
00292     }
00293     
00294     Hash += ((OperandHash << 3) | Op.getType()) << (i&31);
00295   }
00296   return Hash;
00297 }
00298 
00299 /// HashEndOfMBB - Hash the last few instructions in the MBB.  For blocks
00300 /// with no successors, we hash two instructions, because cross-jumping 
00301 /// only saves code when at least two instructions are removed (since a 
00302 /// branch must be inserted).  For blocks with a successor, one of the
00303 /// two blocks to be tail-merged will end with a branch already, so
00304 /// it gains to cross-jump even for one instruction.
00305 
00306 static unsigned HashEndOfMBB(const MachineBasicBlock *MBB,
00307                              unsigned minCommonTailLength) {
00308   MachineBasicBlock::const_iterator I = MBB->end();
00309   if (I == MBB->begin())
00310     return 0;   // Empty MBB.
00311   
00312   --I;
00313   unsigned Hash = HashMachineInstr(I);
00314     
00315   if (I == MBB->begin() || minCommonTailLength == 1)
00316     return Hash;   // Single instr MBB.
00317   
00318   --I;
00319   // Hash in the second-to-last instruction.
00320   Hash ^= HashMachineInstr(I) << 2;
00321   return Hash;
00322 }
00323 
00324 /// ComputeCommonTailLength - Given two machine basic blocks, compute the number
00325 /// of instructions they actually have in common together at their end.  Return
00326 /// iterators for the first shared instruction in each block.
00327 static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1,
00328                                         MachineBasicBlock *MBB2,
00329                                         MachineBasicBlock::iterator &I1,
00330                                         MachineBasicBlock::iterator &I2) {
00331   I1 = MBB1->end();
00332   I2 = MBB2->end();
00333   
00334   unsigned TailLen = 0;
00335   while (I1 != MBB1->begin() && I2 != MBB2->begin()) {
00336     --I1; --I2;
00337     if (!I1->isIdenticalTo(I2) || 
00338         // FIXME: This check is dubious. It's used to get around a problem where
00339         // people incorrectly expect inline asm directives to remain in the same
00340         // relative order. This is untenable because normal compiler
00341         // optimizations (like this one) may reorder and/or merge these
00342         // directives.
00343         I1->getOpcode() == TargetInstrInfo::INLINEASM) {
00344       ++I1; ++I2;
00345       break;
00346     }
00347     ++TailLen;
00348   }
00349   return TailLen;
00350 }
00351 
00352 /// ReplaceTailWithBranchTo - Delete the instruction OldInst and everything
00353 /// after it, replacing it with an unconditional branch to NewDest.  This
00354 /// returns true if OldInst's block is modified, false if NewDest is modified.
00355 void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
00356                                            MachineBasicBlock *NewDest) {
00357   MachineBasicBlock *OldBB = OldInst->getParent();
00358   
00359   // Remove all the old successors of OldBB from the CFG.
00360   while (!OldBB->succ_empty())
00361     OldBB->removeSuccessor(OldBB->succ_begin());
00362   
00363   // Remove all the dead instructions from the end of OldBB.
00364   OldBB->erase(OldInst, OldBB->end());
00365 
00366   // If OldBB isn't immediately before OldBB, insert a branch to it.
00367   if (++MachineFunction::iterator(OldBB) != MachineFunction::iterator(NewDest))
00368     TII->InsertBranch(*OldBB, NewDest, 0, SmallVector<MachineOperand, 0>());
00369   OldBB->addSuccessor(NewDest);
00370   ++NumTailMerge;
00371 }
00372 
00373 /// SplitMBBAt - Given a machine basic block and an iterator into it, split the
00374 /// MBB so that the part before the iterator falls into the part starting at the
00375 /// iterator.  This returns the new MBB.
00376 MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
00377                                             MachineBasicBlock::iterator BBI1) {
00378   MachineFunction &MF = *CurMBB.getParent();
00379 
00380   // Create the fall-through block.
00381   MachineFunction::iterator MBBI = &CurMBB;
00382   MachineBasicBlock *NewMBB =MF.CreateMachineBasicBlock(CurMBB.getBasicBlock());
00383   CurMBB.getParent()->insert(++MBBI, NewMBB);
00384 
00385   // Move all the successors of this block to the specified block.
00386   NewMBB->transferSuccessors(&CurMBB);
00387  
00388   // Add an edge from CurMBB to NewMBB for the fall-through.
00389   CurMBB.addSuccessor(NewMBB);
00390   
00391   // Splice the code over.
00392   NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end());
00393 
00394   // For targets that use the register scavenger, we must maintain LiveIns.
00395   if (RS) {
00396     RS->enterBasicBlock(&CurMBB);
00397     if (!CurMBB.empty())
00398       RS->forward(prior(CurMBB.end()));
00399     BitVector RegsLiveAtExit(RegInfo->getNumRegs());
00400     RS->getRegsUsed(RegsLiveAtExit, false);
00401     for (unsigned int i=0, e=RegInfo->getNumRegs(); i!=e; i++)
00402       if (RegsLiveAtExit[i])
00403         NewMBB->addLiveIn(i);
00404   }
00405 
00406   return NewMBB;
00407 }
00408 
00409 /// EstimateRuntime - Make a rough estimate for how long it will take to run
00410 /// the specified code.
00411 static unsigned EstimateRuntime(MachineBasicBlock::iterator I,
00412                                 MachineBasicBlock::iterator E) {
00413   unsigned Time = 0;
00414   for (; I != E; ++I) {
00415     const TargetInstrDesc &TID = I->getDesc();
00416     if (TID.isCall())
00417       Time += 10;
00418     else if (TID.mayLoad() || TID.mayStore())
00419       Time += 2;
00420     else
00421       ++Time;
00422   }
00423   return Time;
00424 }
00425 
00426 // CurMBB needs to add an unconditional branch to SuccMBB (we removed these
00427 // branches temporarily for tail merging).  In the case where CurMBB ends
00428 // with a conditional branch to the next block, optimize by reversing the
00429 // test and conditionally branching to SuccMBB instead.
00430 
00431 static void FixTail(MachineBasicBlock* CurMBB, MachineBasicBlock *SuccBB,
00432                     const TargetInstrInfo *TII) {
00433   MachineFunction *MF = CurMBB->getParent();
00434   MachineFunction::iterator I = next(MachineFunction::iterator(CurMBB));
00435   MachineBasicBlock *TBB = 0, *FBB = 0;
00436   SmallVector<MachineOperand, 4> Cond;
00437   if (I != MF->end() &&
00438       !TII->AnalyzeBranch(*CurMBB, TBB, FBB, Cond, true)) {
00439     MachineBasicBlock *NextBB = I;
00440     if (TBB == NextBB && !Cond.empty() && !FBB) {
00441       if (!TII->ReverseBranchCondition(Cond)) {
00442         TII->RemoveBranch(*CurMBB);
00443         TII->InsertBranch(*CurMBB, SuccBB, NULL, Cond);
00444         return;
00445       }
00446     }
00447   }
00448   TII->InsertBranch(*CurMBB, SuccBB, NULL, SmallVector<MachineOperand, 0>());
00449 }
00450 
00451 static bool MergeCompare(const std::pair<unsigned,MachineBasicBlock*> &p,
00452                          const std::pair<unsigned,MachineBasicBlock*> &q) {
00453     if (p.first < q.first)
00454       return true;
00455      else if (p.first > q.first)
00456       return false;
00457     else if (p.second->getNumber() < q.second->getNumber())
00458       return true;
00459     else if (p.second->getNumber() > q.second->getNumber())
00460       return false;
00461     else {
00462       // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing
00463       // an object with itself.
00464 #ifndef _GLIBCXX_DEBUG
00465       llvm_unreachable("Predecessor appears twice");
00466 #endif
00467       return false;
00468     }
00469 }
00470 
00471 /// ComputeSameTails - Look through all the blocks in MergePotentials that have
00472 /// hash CurHash (guaranteed to match the last element).   Build the vector 
00473 /// SameTails of all those that have the (same) largest number of instructions
00474 /// in common of any pair of these blocks.  SameTails entries contain an
00475 /// iterator into MergePotentials (from which the MachineBasicBlock can be 
00476 /// found) and a MachineBasicBlock::iterator into that MBB indicating the 
00477 /// instruction where the matching code sequence begins.
00478 /// Order of elements in SameTails is the reverse of the order in which
00479 /// those blocks appear in MergePotentials (where they are not necessarily
00480 /// consecutive).
00481 unsigned BranchFolder::ComputeSameTails(unsigned CurHash, 
00482                                         unsigned minCommonTailLength) {
00483   unsigned maxCommonTailLength = 0U;
00484   SameTails.clear();
00485   MachineBasicBlock::iterator TrialBBI1, TrialBBI2;
00486   MPIterator HighestMPIter = prior(MergePotentials.end());
00487   for (MPIterator CurMPIter = prior(MergePotentials.end()),
00488                   B = MergePotentials.begin(); 
00489        CurMPIter!=B && CurMPIter->first==CurHash;
00490        --CurMPIter) {
00491     for (MPIterator I = prior(CurMPIter); I->first==CurHash ; --I) {
00492       unsigned CommonTailLen = ComputeCommonTailLength(
00493                                         CurMPIter->second,
00494                                         I->second,
00495                                         TrialBBI1, TrialBBI2);
00496       // If we will have to split a block, there should be at least
00497       // minCommonTailLength instructions in common; if not, at worst
00498       // we will be replacing a fallthrough into the common tail with a
00499       // branch, which at worst breaks even with falling through into
00500       // the duplicated common tail, so 1 instruction in common is enough.
00501       // We will always pick a block we do not have to split as the common
00502       // tail if there is one.
00503       // (Empty blocks will get forwarded and need not be considered.)
00504       if (CommonTailLen >= minCommonTailLength ||
00505           (CommonTailLen > 0 &&
00506            (TrialBBI1==CurMPIter->second->begin() ||
00507             TrialBBI2==I->second->begin()))) {
00508         if (CommonTailLen > maxCommonTailLength) {
00509           SameTails.clear();
00510           maxCommonTailLength = CommonTailLen;
00511           HighestMPIter = CurMPIter;
00512           SameTails.push_back(std::make_pair(CurMPIter, TrialBBI1));
00513         }
00514         if (HighestMPIter == CurMPIter &&
00515             CommonTailLen == maxCommonTailLength)
00516           SameTails.push_back(std::make_pair(I, TrialBBI2));
00517       }
00518       if (I==B)
00519         break;
00520     }
00521   }
00522   return maxCommonTailLength;
00523 }
00524 
00525 /// RemoveBlocksWithHash - Remove all blocks with hash CurHash from
00526 /// MergePotentials, restoring branches at ends of blocks as appropriate.
00527 void BranchFolder::RemoveBlocksWithHash(unsigned CurHash, 
00528                                         MachineBasicBlock* SuccBB,
00529                                         MachineBasicBlock* PredBB) {
00530   MPIterator CurMPIter, B;
00531   for (CurMPIter = prior(MergePotentials.end()), B = MergePotentials.begin(); 
00532        CurMPIter->first==CurHash;
00533        --CurMPIter) {
00534     // Put the unconditional branch back, if we need one.
00535     MachineBasicBlock *CurMBB = CurMPIter->second;
00536     if (SuccBB && CurMBB != PredBB)
00537       FixTail(CurMBB, SuccBB, TII);
00538     if (CurMPIter==B)
00539       break;
00540   }
00541   if (CurMPIter->first!=CurHash)
00542     CurMPIter++;
00543   MergePotentials.erase(CurMPIter, MergePotentials.end());
00544 }
00545 
00546 /// CreateCommonTailOnlyBlock - None of the blocks to be tail-merged consist
00547 /// only of the common tail.  Create a block that does by splitting one.
00548 unsigned BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
00549                                              unsigned maxCommonTailLength) {
00550   unsigned i, commonTailIndex;
00551   unsigned TimeEstimate = ~0U;
00552   for (i=0, commonTailIndex=0; i<SameTails.size(); i++) {
00553     // Use PredBB if possible; that doesn't require a new branch.
00554     if (SameTails[i].first->second==PredBB) {
00555       commonTailIndex = i;
00556       break;
00557     }
00558     // Otherwise, make a (fairly bogus) choice based on estimate of
00559     // how long it will take the various blocks to execute.
00560     unsigned t = EstimateRuntime(SameTails[i].first->second->begin(), 
00561                                  SameTails[i].second);
00562     if (t<=TimeEstimate) {
00563       TimeEstimate = t;
00564       commonTailIndex = i;
00565     }
00566   }
00567 
00568   MachineBasicBlock::iterator BBI = SameTails[commonTailIndex].second;
00569   MachineBasicBlock *MBB = SameTails[commonTailIndex].first->second;
00570 
00571   DOUT << "\nSplitting " << MBB->getNumber() << ", size " << 
00572           maxCommonTailLength;
00573 
00574   MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI);
00575   SameTails[commonTailIndex].first->second = newMBB;
00576   SameTails[commonTailIndex].second = newMBB->begin();
00577   // If we split PredBB, newMBB is the new predecessor.
00578   if (PredBB==MBB)
00579     PredBB = newMBB;
00580 
00581   return commonTailIndex;
00582 }
00583 
00584 // See if any of the blocks in MergePotentials (which all have a common single
00585 // successor, or all have no successor) can be tail-merged.  If there is a
00586 // successor, any blocks in MergePotentials that are not tail-merged and
00587 // are not immediately before Succ must have an unconditional branch to
00588 // Succ added (but the predecessor/successor lists need no adjustment).  
00589 // The lone predecessor of Succ that falls through into Succ,
00590 // if any, is given in PredBB.
00591 
00592 bool BranchFolder::TryMergeBlocks(MachineBasicBlock *SuccBB,
00593                                   MachineBasicBlock* PredBB) {
00594   // It doesn't make sense to save a single instruction since tail merging
00595   // will add a jump.
00596   // FIXME: Ask the target to provide the threshold?
00597   unsigned minCommonTailLength = (SuccBB ? 1 : 2) + 1;
00598   MadeChange = false;
00599   
00600   DOUT << "\nTryMergeBlocks " << MergePotentials.size() << '\n';
00601 
00602   // Sort by hash value so that blocks with identical end sequences sort
00603   // together.
00604   std::stable_sort(MergePotentials.begin(), MergePotentials.end(),MergeCompare);
00605 
00606   // Walk through equivalence sets looking for actual exact matches.
00607   while (MergePotentials.size() > 1) {
00608     unsigned CurHash  = prior(MergePotentials.end())->first;
00609     
00610     // Build SameTails, identifying the set of blocks with this hash code
00611     // and with the maximum number of instructions in common.
00612     unsigned maxCommonTailLength = ComputeSameTails(CurHash, 
00613                                                     minCommonTailLength);
00614 
00615     // If we didn't find any pair that has at least minCommonTailLength 
00616     // instructions in common, remove all blocks with this hash code and retry.
00617     if (SameTails.empty()) {
00618       RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
00619       continue;
00620     }
00621 
00622     // If one of the blocks is the entire common tail (and not the entry
00623     // block, which we can't jump to), we can treat all blocks with this same
00624     // tail at once.  Use PredBB if that is one of the possibilities, as that
00625     // will not introduce any extra branches.
00626     MachineBasicBlock *EntryBB = MergePotentials.begin()->second->
00627                                 getParent()->begin();
00628     unsigned int commonTailIndex, i;
00629     for (commonTailIndex=SameTails.size(), i=0; i<SameTails.size(); i++) {
00630       MachineBasicBlock *MBB = SameTails[i].first->second;
00631       if (MBB->begin() == SameTails[i].second && MBB != EntryBB) {
00632         commonTailIndex = i;
00633         if (MBB==PredBB)
00634           break;
00635       }
00636     }
00637 
00638     if (commonTailIndex==SameTails.size()) {
00639       // None of the blocks consist entirely of the common tail.
00640       // Split a block so that one does.
00641       commonTailIndex = CreateCommonTailOnlyBlock(PredBB,  maxCommonTailLength);
00642     }
00643 
00644     MachineBasicBlock *MBB = SameTails[commonTailIndex].first->second;
00645     // MBB is common tail.  Adjust all other BB's to jump to this one.
00646     // Traversal must be forwards so erases work.
00647     DOUT << "\nUsing common tail " << MBB->getNumber() << " for ";
00648     for (unsigned int i=0; i<SameTails.size(); ++i) {
00649       if (commonTailIndex==i)
00650         continue;
00651       DOUT << SameTails[i].first->second->getNumber() << ",";
00652       // Hack the end off BB i, making it jump to BB commonTailIndex instead.
00653       ReplaceTailWithBranchTo(SameTails[i].second, MBB);
00654       // BB i is no longer a predecessor of SuccBB; remove it from the worklist.
00655       MergePotentials.erase(SameTails[i].first);
00656     }
00657     DOUT << "\n";
00658     // We leave commonTailIndex in the worklist in case there are other blocks
00659     // that match it with a smaller number of instructions.
00660     MadeChange = true;
00661   }
00662   return MadeChange;
00663 }
00664 
00665 bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
00666 
00667   if (!EnableTailMerge) return false;
00668  
00669   MadeChange = false;
00670 
00671   // First find blocks with no successors.
00672   MergePotentials.clear();
00673   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
00674     if (I->succ_empty())
00675       MergePotentials.push_back(std::make_pair(HashEndOfMBB(I, 2U), I));
00676   }
00677   // See if we can do any tail merging on those.
00678   if (MergePotentials.size() < TailMergeThreshold &&
00679       MergePotentials.size() >= 2)
00680     MadeChange |= TryMergeBlocks(NULL, NULL);
00681 
00682   // Look at blocks (IBB) with multiple predecessors (PBB).
00683   // We change each predecessor to a canonical form, by
00684   // (1) temporarily removing any unconditional branch from the predecessor
00685   // to IBB, and
00686   // (2) alter conditional branches so they branch to the other block
00687   // not IBB; this may require adding back an unconditional branch to IBB 
00688   // later, where there wasn't one coming in.  E.g.
00689   //   Bcc IBB
00690   //   fallthrough to QBB
00691   // here becomes
00692   //   Bncc QBB
00693   // with a conceptual B to IBB after that, which never actually exists.
00694   // With those changes, we see whether the predecessors' tails match,
00695   // and merge them if so.  We change things out of canonical form and
00696   // back to the way they were later in the process.  (OptimizeBranches
00697   // would undo some of this, but we can't use it, because we'd get into
00698   // a compile-time infinite loop repeatedly doing and undoing the same
00699   // transformations.)
00700 
00701   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
00702     if (I->pred_size() >= 2 && I->pred_size() < TailMergeThreshold) {
00703       SmallPtrSet<MachineBasicBlock *, 8> UniquePreds;
00704       MachineBasicBlock *IBB = I;
00705       MachineBasicBlock *PredBB = prior(I);
00706       MergePotentials.clear();
00707       for (MachineBasicBlock::pred_iterator P = I->pred_begin(), 
00708                                             E2 = I->pred_end();
00709            P != E2; ++P) {
00710         MachineBasicBlock* PBB = *P;
00711         // Skip blocks that loop to themselves, can't tail merge these.
00712         if (PBB==IBB)
00713           continue;
00714         // Visit each predecessor only once.
00715         if (!UniquePreds.insert(PBB))
00716           continue;
00717         MachineBasicBlock *TBB = 0, *FBB = 0;
00718         SmallVector<MachineOperand, 4> Cond;
00719         if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond, true)) {
00720           // Failing case:  IBB is the target of a cbr, and
00721           // we cannot reverse the branch.
00722           SmallVector<MachineOperand, 4> NewCond(Cond);
00723           if (!Cond.empty() && TBB==IBB) {
00724             if (TII->ReverseBranchCondition(NewCond))
00725               continue;
00726             // This is the QBB case described above
00727             if (!FBB)
00728               FBB = next(MachineFunction::iterator(PBB));
00729           }
00730           // Failing case:  the only way IBB can be reached from PBB is via
00731           // exception handling.  Happens for landing pads.  Would be nice
00732           // to have a bit in the edge so we didn't have to do all this.
00733           if (IBB->isLandingPad()) {
00734             MachineFunction::iterator IP = PBB;  IP++;
00735             MachineBasicBlock* PredNextBB = NULL;
00736             if (IP!=MF.end())
00737               PredNextBB = IP;
00738             if (TBB==NULL) {
00739               if (IBB!=PredNextBB)      // fallthrough
00740                 continue;
00741             } else if (FBB) {
00742               if (TBB!=IBB && FBB!=IBB)   // cbr then ubr
00743                 continue;
00744             } else if (Cond.empty()) {
00745               if (TBB!=IBB)               // ubr
00746                 continue;
00747             } else {
00748               if (TBB!=IBB && IBB!=PredNextBB)  // cbr
00749                 continue;
00750             }
00751           }
00752           // Remove the unconditional branch at the end, if any.
00753           if (TBB && (Cond.empty() || FBB)) {
00754             TII->RemoveBranch(*PBB);
00755             if (!Cond.empty())
00756               // reinsert conditional branch only, for now
00757               TII->InsertBranch(*PBB, (TBB==IBB) ? FBB : TBB, 0, NewCond);
00758           }
00759           MergePotentials.push_back(std::make_pair(HashEndOfMBB(PBB, 1U), *P));
00760         }
00761       }
00762     if (MergePotentials.size() >= 2)
00763       MadeChange |= TryMergeBlocks(I, PredBB);
00764     // Reinsert an unconditional branch if needed.
00765     // The 1 below can occur as a result of removing blocks in TryMergeBlocks.
00766     PredBB = prior(I);      // this may have been changed in TryMergeBlocks
00767     if (MergePotentials.size()==1 && 
00768         MergePotentials.begin()->second != PredBB)
00769       FixTail(MergePotentials.begin()->second, I, TII);
00770     }
00771   }
00772   return MadeChange;
00773 }
00774 
00775 //===----------------------------------------------------------------------===//
00776 //  Branch Optimization
00777 //===----------------------------------------------------------------------===//
00778 
00779 bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
00780   MadeChange = false;
00781   
00782   // Make sure blocks are numbered in order
00783   MF.RenumberBlocks();
00784 
00785   for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
00786     MachineBasicBlock *MBB = I++;
00787     OptimizeBlock(MBB);
00788     
00789     // If it is dead, remove it.
00790     if (MBB->pred_empty()) {
00791       RemoveDeadBlock(MBB);
00792       MadeChange = true;
00793       ++NumDeadBlocks;
00794     }
00795   }
00796   return MadeChange;
00797 }
00798 
00799 
00800 /// CanFallThrough - Return true if the specified block (with the specified
00801 /// branch condition) can implicitly transfer control to the block after it by
00802 /// falling off the end of it.  This should return false if it can reach the
00803 /// block after it, but it uses an explicit branch to do so (e.g. a table jump).
00804 ///
00805 /// True is a conservative answer.
00806 ///
00807 bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB,
00808                                   bool BranchUnAnalyzable,
00809                                   MachineBasicBlock *TBB, 
00810                                   MachineBasicBlock *FBB,
00811                                   const SmallVectorImpl<MachineOperand> &Cond) {
00812   MachineFunction::iterator Fallthrough = CurBB;
00813   ++Fallthrough;
00814   // If FallthroughBlock is off the end of the function, it can't fall through.
00815   if (Fallthrough == CurBB->getParent()->end())
00816     return false;
00817   
00818   // If FallthroughBlock isn't a successor of CurBB, no fallthrough is possible.
00819   if (!CurBB->isSuccessor(Fallthrough))
00820     return false;
00821   
00822   // If we couldn't analyze the branch, assume it could fall through.
00823   if (BranchUnAnalyzable) return true;
00824   
00825   // If there is no branch, control always falls through.
00826   if (TBB == 0) return true;
00827 
00828   // If there is some explicit branch to the fallthrough block, it can obviously
00829   // reach, even though the branch should get folded to fall through implicitly.
00830   if (MachineFunction::iterator(TBB) == Fallthrough ||
00831       MachineFunction::iterator(FBB) == Fallthrough)
00832     return true;
00833   
00834   // If it's an unconditional branch to some block not the fall through, it 
00835   // doesn't fall through.
00836   if (Cond.empty()) return false;
00837   
00838   // Otherwise, if it is conditional and has no explicit false block, it falls
00839   // through.
00840   return FBB == 0;
00841 }
00842 
00843 /// CanFallThrough - Return true if the specified can implicitly transfer
00844 /// control to the block after it by falling off the end of it.  This should
00845 /// return false if it can reach the block after it, but it uses an explicit
00846 /// branch to do so (e.g. a table jump).
00847 ///
00848 /// True is a conservative answer.
00849 ///
00850 bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB) {
00851   MachineBasicBlock *TBB = 0, *FBB = 0;
00852   SmallVector<MachineOperand, 4> Cond;
00853   bool CurUnAnalyzable = TII->AnalyzeBranch(*CurBB, TBB, FBB, Cond, true);
00854   return CanFallThrough(CurBB, CurUnAnalyzable, TBB, FBB, Cond);
00855 }
00856 
00857 /// IsBetterFallthrough - Return true if it would be clearly better to
00858 /// fall-through to MBB1 than to fall through into MBB2.  This has to return
00859 /// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will
00860 /// result in infinite loops.
00861 static bool IsBetterFallthrough(MachineBasicBlock *MBB1, 
00862                                 MachineBasicBlock *MBB2) {
00863   // Right now, we use a simple heuristic.  If MBB2 ends with a call, and
00864   // MBB1 doesn't, we prefer to fall through into MBB1.  This allows us to
00865   // optimize branches that branch to either a return block or an assert block
00866   // into a fallthrough to the return.
00867   if (MBB1->empty() || MBB2->empty()) return false;
00868  
00869   // If there is a clear successor ordering we make sure that one block
00870   // will fall through to the next
00871   if (MBB1->isSuccessor(MBB2)) return true;
00872   if (MBB2->isSuccessor(MBB1)) return false;
00873 
00874   MachineInstr *MBB1I = --MBB1->end();
00875   MachineInstr *MBB2I = --MBB2->end();
00876   return MBB2I->getDesc().isCall() && !MBB1I->getDesc().isCall();
00877 }
00878 
00879 /// OptimizeBlock - Analyze and optimize control flow related to the specified
00880 /// block.  This is never called on the entry block.
00881 void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
00882   MachineFunction::iterator FallThrough = MBB;
00883   ++FallThrough;
00884   
00885   // If this block is empty, make everyone use its fall-through, not the block
00886   // explicitly.  Landing pads should not do this since the landing-pad table
00887   // points to this block.
00888   if (MBB->empty() && !MBB->isLandingPad()) {
00889     // Dead block?  Leave for cleanup later.
00890     if (MBB->pred_empty()) return;
00891     
00892     if (FallThrough == MBB->getParent()->end()) {
00893       // TODO: Simplify preds to not branch here if possible!
00894     } else {
00895       // Rewrite all predecessors of the old block to go to the fallthrough
00896       // instead.
00897       while (!MBB->pred_empty()) {
00898         MachineBasicBlock *Pred = *(MBB->pred_end()-1);
00899         Pred->ReplaceUsesOfBlockWith(MBB, FallThrough);
00900       }
00901       // If MBB was the target of a jump table, update jump tables to go to the
00902       // fallthrough instead.
00903       MBB->getParent()->getJumpTableInfo()->
00904         ReplaceMBBInJumpTables(MBB, FallThrough);
00905       MadeChange = true;
00906     }
00907     return;
00908   }
00909 
00910   // Check to see if we can simplify the terminator of the block before this
00911   // one.
00912   MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB));
00913 
00914   MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
00915   SmallVector<MachineOperand, 4> PriorCond;
00916   bool PriorUnAnalyzable =
00917     TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);
00918   if (!PriorUnAnalyzable) {
00919     // If the CFG for the prior block has extra edges, remove them.
00920     MadeChange |= PrevBB.CorrectExtraCFGEdges(PriorTBB, PriorFBB,
00921                                               !PriorCond.empty());
00922     
00923     // If the previous branch is conditional and both conditions go to the same
00924     // destination, remove the branch, replacing it with an unconditional one or
00925     // a fall-through.
00926     if (PriorTBB && PriorTBB == PriorFBB) {
00927       TII->RemoveBranch(PrevBB);
00928       PriorCond.clear(); 
00929       if (PriorTBB != MBB)
00930         TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond);
00931       MadeChange = true;
00932       ++NumBranchOpts;
00933       return OptimizeBlock(MBB);
00934     }
00935     
00936     // If the previous branch *only* branches to *this* block (conditional or
00937     // not) remove the branch.
00938     if (PriorTBB == MBB && PriorFBB == 0) {
00939       TII->RemoveBranch(PrevBB);
00940       MadeChange = true;
00941       ++NumBranchOpts;
00942       return OptimizeBlock(MBB);
00943     }
00944     
00945     // If the prior block branches somewhere else on the condition and here if
00946     // the condition is false, remove the uncond second branch.
00947     if (PriorFBB == MBB) {
00948       TII->RemoveBranch(PrevBB);
00949       TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond);
00950       MadeChange = true;
00951       ++NumBranchOpts;
00952       return OptimizeBlock(MBB);
00953     }
00954     
00955     // If the prior block branches here on true and somewhere else on false, and
00956     // if the branch condition is reversible, reverse the branch to create a
00957     // fall-through.
00958     if (PriorTBB == MBB) {
00959       SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
00960       if (!TII->ReverseBranchCondition(NewPriorCond)) {
00961         TII->RemoveBranch(PrevBB);
00962         TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond);
00963         MadeChange = true;
00964         ++NumBranchOpts;
00965         return OptimizeBlock(MBB);
00966       }
00967     }
00968     
00969     // If this block doesn't fall through (e.g. it ends with an uncond branch or
00970     // has no successors) and if the pred falls through into this block, and if
00971     // it would otherwise fall through into the block after this, move this
00972     // block to the end of the function.
00973     //
00974     // We consider it more likely that execution will stay in the function (e.g.
00975     // due to loops) than it is to exit it.  This asserts in loops etc, moving
00976     // the assert condition out of the loop body.
00977     if (!PriorCond.empty() && PriorFBB == 0 &&
00978         MachineFunction::iterator(PriorTBB) == FallThrough &&
00979         !CanFallThrough(MBB)) {
00980       bool DoTransform = true;
00981       
00982       // We have to be careful that the succs of PredBB aren't both no-successor
00983       // blocks.  If neither have successors and if PredBB is the second from
00984       // last block in the function, we'd just keep swapping the two blocks for
00985       // last.  Only do the swap if one is clearly better to fall through than
00986       // the other.
00987       if (FallThrough == --MBB->getParent()->end() &&
00988           !IsBetterFallthrough(PriorTBB, MBB))
00989         DoTransform = false;
00990 
00991       // We don't want to do this transformation if we have control flow like:
00992       //   br cond BB2
00993       // BB1:
00994       //   ..
00995       //   jmp BBX
00996       // BB2:
00997       //   ..
00998       //   ret
00999       //
01000       // In this case, we could actually be moving the return block *into* a
01001       // loop!
01002       if (DoTransform && !MBB->succ_empty() &&
01003           (!CanFallThrough(PriorTBB) || PriorTBB->empty()))
01004         DoTransform = false;
01005       
01006       
01007       if (DoTransform) {
01008         // Reverse the branch so we will fall through on the previous true cond.
01009         SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
01010         if (!TII->ReverseBranchCondition(NewPriorCond)) {
01011           DOUT << "\nMoving MBB: " << *MBB;
01012           DOUT << "To make fallthrough to: " << *PriorTBB << "\n";
01013           
01014           TII->RemoveBranch(PrevBB);
01015           TII->InsertBranch(PrevBB, MBB, 0, NewPriorCond);
01016 
01017           // Move this block to the end of the function.
01018           MBB->moveAfter(--MBB->getParent()->end());
01019           MadeChange = true;
01020           ++NumBranchOpts;
01021           return;
01022         }
01023       }
01024     }
01025   }
01026   
01027   // Analyze the branch in the current block.
01028   MachineBasicBlock *CurTBB = 0, *CurFBB = 0;
01029   SmallVector<MachineOperand, 4> CurCond;
01030   bool CurUnAnalyzable= TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
01031   if (!CurUnAnalyzable) {
01032     // If the CFG for the prior block has extra edges, remove them.
01033     MadeChange |= MBB->CorrectExtraCFGEdges(CurTBB, CurFBB, !CurCond.empty());
01034 
01035     // If this is a two-way branch, and the FBB branches to this block, reverse 
01036     // the condition so the single-basic-block loop is faster.  Instead of:
01037     //    Loop: xxx; jcc Out; jmp Loop
01038     // we want:
01039     //    Loop: xxx; jncc Loop; jmp Out
01040     if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) {
01041       SmallVector<MachineOperand, 4> NewCond(CurCond);
01042       if (!TII->ReverseBranchCondition(NewCond)) {
01043         TII->RemoveBranch(*MBB);
01044         TII->InsertBranch(*MBB, CurFBB, CurTBB, NewCond);
01045         MadeChange = true;
01046         ++NumBranchOpts;
01047         return OptimizeBlock(MBB);
01048       }
01049     }
01050     
01051     
01052     // If this branch is the only thing in its block, see if we can forward
01053     // other blocks across it.
01054     if (CurTBB && CurCond.empty() && CurFBB == 0 && 
01055         MBB->begin()->getDesc().isBranch() && CurTBB != MBB) {
01056       // This block may contain just an unconditional branch.  Because there can
01057       // be 'non-branch terminators' in the block, try removing the branch and
01058       // then seeing if the block is empty.
01059       TII->RemoveBranch(*MBB);
01060 
01061       // If this block is just an unconditional branch to CurTBB, we can
01062       // usually completely eliminate the block.  The only case we cannot
01063       // completely eliminate the block is when the block before this one
01064       // falls through into MBB and we can't understand the prior block's branch
01065       // condition.
01066       if (MBB->empty()) {
01067         bool PredHasNoFallThrough = TII->BlockHasNoFallThrough(PrevBB);
01068         if (PredHasNoFallThrough || !PriorUnAnalyzable ||
01069             !PrevBB.isSuccessor(MBB)) {
01070           // If the prior block falls through into us, turn it into an
01071           // explicit branch to us to make updates simpler.
01072           if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) && 
01073               PriorTBB != MBB && PriorFBB != MBB) {
01074             if (PriorTBB == 0) {
01075               assert(PriorCond.empty() && PriorFBB == 0 &&
01076                      "Bad branch analysis");
01077               PriorTBB = MBB;
01078             } else {
01079               assert(PriorFBB == 0 && "Machine CFG out of date!");
01080               PriorFBB = MBB;
01081             }
01082             TII->RemoveBranch(PrevBB);
01083             TII->InsertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond);
01084           }
01085 
01086           // Iterate through all the predecessors, revectoring each in-turn.
01087           size_t PI = 0;
01088           bool DidChange = false;
01089           bool HasBranchToSelf = false;
01090           while(PI != MBB->pred_size()) {
01091             MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI);
01092             if (PMBB == MBB) {
01093               // If this block has an uncond branch to itself, leave it.
01094               ++PI;
01095               HasBranchToSelf = true;
01096             } else {
01097               DidChange = true;
01098               PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB);
01099               // If this change resulted in PMBB ending in a conditional
01100               // branch where both conditions go to the same destination,
01101               // change this to an unconditional branch (and fix the CFG).
01102               MachineBasicBlock *NewCurTBB = 0, *NewCurFBB = 0;
01103               SmallVector<MachineOperand, 4> NewCurCond;
01104               bool NewCurUnAnalyzable = TII->AnalyzeBranch(*PMBB, NewCurTBB,
01105                       NewCurFBB, NewCurCond, true);
01106               if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) {
01107                 TII->RemoveBranch(*PMBB);
01108                 NewCurCond.clear(); 
01109                 TII->InsertBranch(*PMBB, NewCurTBB, 0, NewCurCond);
01110                 MadeChange = true;
01111                 ++NumBranchOpts;
01112                 PMBB->CorrectExtraCFGEdges(NewCurTBB, NewCurFBB, false);
01113               }
01114             }
01115           }
01116 
01117           // Change any jumptables to go to the new MBB.
01118           MBB->getParent()->getJumpTableInfo()->
01119             ReplaceMBBInJumpTables(MBB, CurTBB);
01120           if (DidChange) {
01121             ++NumBranchOpts;
01122             MadeChange = true;
01123             if (!HasBranchToSelf) return;
01124           }
01125         }
01126       }
01127       
01128       // Add the branch back if the block is more than just an uncond branch.
01129       TII->InsertBranch(*MBB, CurTBB, 0, CurCond);
01130     }
01131   }
01132 
01133   // If the prior block doesn't fall through into this block, and if this
01134   // block doesn't fall through into some other block, see if we can find a
01135   // place to move this block where a fall-through will happen.
01136   if (!CanFallThrough(&PrevBB, PriorUnAnalyzable,
01137                       PriorTBB, PriorFBB, PriorCond)) {
01138     // Now we know that there was no fall-through into this block, check to
01139     // see if it has a fall-through into its successor.
01140     bool CurFallsThru = CanFallThrough(MBB, CurUnAnalyzable, CurTBB, CurFBB, 
01141                                        CurCond);
01142 
01143     if (!MBB->isLandingPad()) {
01144       // Check all the predecessors of this block.  If one of them has no fall
01145       // throughs, move this block right after it.
01146       for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
01147            E = MBB->pred_end(); PI != E; ++PI) {
01148         // Analyze the branch at the end of the pred.
01149         MachineBasicBlock *PredBB = *PI;
01150         MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough;
01151         if (PredBB != MBB && !CanFallThrough(PredBB)
01152             && (!CurFallsThru || !CurTBB || !CurFBB)
01153             && (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
01154           // If the current block doesn't fall through, just move it.
01155           // If the current block can fall through and does not end with a
01156           // conditional branch, we need to append an unconditional jump to 
01157           // the (current) next block.  To avoid a possible compile-time
01158           // infinite loop, move blocks only backward in this case.
01159           // Also, if there are already 2 branches here, we cannot add a third;
01160           // this means we have the case
01161           // Bcc next
01162           // B elsewhere
01163           // next:
01164           if (CurFallsThru) {
01165             MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB));
01166             CurCond.clear();
01167             TII->InsertBranch(*MBB, NextBB, 0, CurCond);
01168           }
01169           MBB->moveAfter(PredBB);
01170           MadeChange = true;
01171           return OptimizeBlock(MBB);
01172         }
01173       }
01174     }
01175         
01176     if (!CurFallsThru) {
01177       // Check all successors to see if we can move this block before it.
01178       for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
01179            E = MBB->succ_end(); SI != E; ++SI) {
01180         // Analyze the branch at the end of the block before the succ.
01181         MachineBasicBlock *SuccBB = *SI;
01182         MachineFunction::iterator SuccPrev = SuccBB; --SuccPrev;
01183         std::vector<MachineOperand> SuccPrevCond;
01184         
01185         // If this block doesn't already fall-through to that successor, and if
01186         // the succ doesn't already have a block that can fall through into it,
01187         // and if the successor isn't an EH destination, we can arrange for the
01188         // fallthrough to happen.
01189         if (SuccBB != MBB && !CanFallThrough(SuccPrev) &&
01190             !SuccBB->isLandingPad()) {
01191           MBB->moveBefore(SuccBB);
01192           MadeChange = true;
01193           return OptimizeBlock(MBB);
01194         }
01195       }
01196       
01197       // Okay, there is no really great place to put this block.  If, however,
01198       // the block before this one would be a fall-through if this block were
01199       // removed, move this block to the end of the function.
01200       if (FallThrough != MBB->getParent()->end() &&
01201           PrevBB.isSuccessor(FallThrough)) {
01202         MBB->moveAfter(--MBB->getParent()->end());
01203         MadeChange = true;
01204         return;
01205       }
01206     }
01207   }
01208 }