LLVM API Documentation
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 }