lib/CodeGen/BranchFolding.cpp

   1 //===-- BranchFolding.cpp - Fold machine code branch instructions ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass forwards branches to unconditional branches to make them branch
  11 // directly to the target block.  This pass often results in dead MBB's, which
  12 // it then removes.
  13 //
  14 // Note that this pass must be run after register allocation, it cannot handle
  15 // SSA form.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "llvm/CodeGen/Passes.h"
  20 #include "llvm/CodeGen/MachineDebugInfo.h"
  21 #include "llvm/CodeGen/MachineFunctionPass.h"
  22 #include "llvm/CodeGen/MachineJumpTableInfo.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/Support/CommandLine.h"
  26 #include "llvm/ADT/Statistic.h"
  27 #include "llvm/ADT/STLExtras.h"
  28 using namespace llvm;
  29
  30 static Statistic<> NumDeadBlocks("branchfold", "Number of dead blocks removed");
  31 static Statistic<> NumBranchOpts("branchfold", "Number of branches optimized");
  32 static Statistic<> NumTailMerge ("branchfold", "Number of block tails merged");
  33
  34 namespace {
  35   struct BranchFolder : public MachineFunctionPass {
  36     virtual bool runOnMachineFunction(MachineFunction &MF);
  37     virtual const char *getPassName() const { return "Control Flow Optimizer"; }
  38     const TargetInstrInfo *TII;
  39     MachineDebugInfo *MDI;
  40     bool MadeChange;
  41   private:
  42     // Tail Merging.
  43     bool TailMergeBlocks(MachineFunction &MF);
  44     void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
  45                                  MachineBasicBlock *NewDest);
  46
  47     // Branch optzn.
  48     bool OptimizeBranches(MachineFunction &MF);
  49     void OptimizeBlock(MachineBasicBlock *MBB);
  50     void RemoveDeadBlock(MachineBasicBlock *MBB);
  51   };
  52 }
  53
  54 FunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); }
  55
  56 /// RemoveDeadBlock - Remove the specified dead machine basic block from the
  57 /// function, updating the CFG.
  58 void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
  59   assert(MBB->pred_empty() && "MBB must be dead!");
  60
  61   MachineFunction *MF = MBB->getParent();
  62   // drop all successors.
  63   while (!MBB->succ_empty())
  64     MBB->removeSuccessor(MBB->succ_end()-1);
  65
  66   // If there is DWARF info to active, check to see if there are any DWARF_LABEL
  67   // records in the basic block.  If so, unregister them from MachineDebugInfo.
  68   if (MDI && !MBB->empty()) {
  69     unsigned DWARF_LABELOpc = TII->getDWARF_LABELOpcode();
  70     assert(DWARF_LABELOpc &&
  71            "Target supports dwarf but didn't implement getDWARF_LABELOpcode!");
  72
  73     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
  74          I != E; ++I) {
  75       if ((unsigned)I->getOpcode() == DWARF_LABELOpc) {
  76         // The label ID # is always operand #0, an immediate.
  77         MDI->InvalidateLabel(I->getOperand(0).getImm());
  78       }
  79     }
  80   }
  81
  82   // Remove the block.
  83   MF->getBasicBlockList().erase(MBB);
  84 }
  85
  86 bool BranchFolder::runOnMachineFunction(MachineFunction &MF) {
  87   TII = MF.getTarget().getInstrInfo();
  88   if (!TII) return false;
  89
  90   MDI = getAnalysisToUpdate<MachineDebugInfo>();
  91
  92   bool EverMadeChange = false;
  93   bool MadeChangeThisIteration = true;
  94   while (MadeChangeThisIteration) {
  95     MadeChangeThisIteration = false;
  96     MadeChangeThisIteration |= TailMergeBlocks(MF);
  97     MadeChangeThisIteration |= OptimizeBranches(MF);
  98     EverMadeChange |= MadeChangeThisIteration;
  99   }
 100
 101   return EverMadeChange;
 102 }
 103
 104 //===----------------------------------------------------------------------===//
 105 //  Tail Merging of Blocks
 106 //===----------------------------------------------------------------------===//
 107
 108 /// HashMachineInstr - Compute a hash value for MI and its operands.
 109 static unsigned HashMachineInstr(const MachineInstr *MI) {
 110   unsigned Hash = MI->getOpcode();
 111   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 112     const MachineOperand &Op = MI->getOperand(i);
 113
 114     // Merge in bits from the operand if easy.
 115     unsigned OperandHash = 0;
 116     switch (Op.getType()) {
 117     case MachineOperand::MO_Register:          OperandHash = Op.getReg(); break;
 118     case MachineOperand::MO_Immediate:         OperandHash = Op.getImm(); break;
 119     case MachineOperand::MO_MachineBasicBlock:
 120       OperandHash = Op.getMachineBasicBlock()->getNumber();
 121       break;
 122     case MachineOperand::MO_FrameIndex: OperandHash = Op.getFrameIndex(); break;
 123     case MachineOperand::MO_ConstantPoolIndex:
 124       OperandHash = Op.getConstantPoolIndex();
 125       break;
 126     case MachineOperand::MO_JumpTableIndex:
 127       OperandHash = Op.getJumpTableIndex();
 128       break;
 129     case MachineOperand::MO_GlobalAddress:
 130     case MachineOperand::MO_ExternalSymbol:
 131       // Global address / external symbol are too hard, don't bother, but do
 132       // pull in the offset.
 133       OperandHash = Op.getOffset();
 134       break;
 135     default: break;
 136     }
 137
 138     Hash += ((OperandHash << 3) | Op.getType()) << (i&31);
 139   }
 140   return Hash;
 141 }
 142
 143 /// HashEndOfMBB - Hash the last two instructions in the MBB.  We hash two
 144 /// instructions, because cross-jumping only saves code when at least two
 145 /// instructions are removed (since a branch must be inserted).
 146 static unsigned HashEndOfMBB(const MachineBasicBlock *MBB) {
 147   MachineBasicBlock::const_iterator I = MBB->end();
 148   if (I == MBB->begin())
 149     return 0;   // Empty MBB.
 150
 151   --I;
 152   unsigned Hash = HashMachineInstr(I);
 153
 154   if (I == MBB->begin())
 155     return Hash;   // Single instr MBB.
 156
 157   --I;
 158   // Hash in the second-to-last instruction.
 159   Hash ^= HashMachineInstr(I) << 2;
 160   return Hash;
 161 }
 162
 163 /// ComputeCommonTailLength - Given two machine basic blocks, compute the number
 164 /// of instructions they actually have in common together at their end.  Return
 165 /// iterators for the first shared instruction in each block.
 166 static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1,
 167                                         MachineBasicBlock *MBB2,
 168                                         MachineBasicBlock::iterator &I1,
 169                                         MachineBasicBlock::iterator &I2) {
 170   I1 = MBB1->end();
 171   I2 = MBB2->end();
 172
 173   unsigned TailLen = 0;
 174   while (I1 != MBB1->begin() && I2 != MBB2->begin()) {
 175     --I1; --I2;
 176     if (!I1->isIdenticalTo(I2)) {
 177       ++I1; ++I2;
 178       break;
 179     }
 180     ++TailLen;
 181   }
 182   return TailLen;
 183 }
 184
 185 /// ReplaceTailWithBranchTo - Delete the instruction OldInst and everything
 186 /// after it, replacing it with an unconditional branch to NewDest.  This
 187 /// returns true if OldInst's block is modified, false if NewDest is modified.
 188 void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
 189                                            MachineBasicBlock *NewDest) {
 190   MachineBasicBlock *OldBB = OldInst->getParent();
 191
 192   // Remove all the old successors of OldBB from the CFG.
 193   while (!OldBB->succ_empty())
 194     OldBB->removeSuccessor(OldBB->succ_begin());
 195
 196   // Remove all the dead instructions from the end of OldBB.
 197   OldBB->erase(OldInst, OldBB->end());
 198
 199   // If OldBB isn't immediately before OldBB, insert a branch to it.
 200   if (++MachineFunction::iterator(OldBB) != MachineFunction::iterator(NewDest))
 201     TII->InsertBranch(*OldBB, NewDest, 0, std::vector<MachineOperand>());
 202   OldBB->addSuccessor(NewDest);
 203   ++NumTailMerge;
 204 }
 205
 206 bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
 207   MadeChange = false;
 208
 209   return false;
 210
 211   // Find blocks with no successors.
 212   std::vector<std::pair<unsigned,MachineBasicBlock*> > MergePotentials;
 213   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
 214     if (I->succ_empty())
 215       MergePotentials.push_back(std::make_pair(HashEndOfMBB(I), I));
 216   }
 217
 218   // Sort by hash value so that blocks with identical end sequences sort
 219   // together.
 220   std::stable_sort(MergePotentials.begin(), MergePotentials.end());
 221
 222   // Walk through equivalence sets looking for actual exact matches.
 223   while (MergePotentials.size() > 1) {
 224     unsigned CurHash  = (MergePotentials.end()-1)->first;
 225     unsigned PrevHash = (MergePotentials.end()-2)->first;
 226     MachineBasicBlock *CurMBB = (MergePotentials.end()-1)->second;
 227
 228     // If there is nothing that matches the hash of the current basic block,
 229     // give up.
 230     if (CurHash != PrevHash) {
 231       MergePotentials.pop_back();
 232       continue;
 233     }
 234
 235     // Determine the actual length of the shared tail between these two basic
 236     // blocks.  Because the hash can have collisions, it's possible that this is
 237     // less than 2.
 238     MachineBasicBlock::iterator BBI1, BBI2;
 239     unsigned CommonTailLen =
 240       ComputeCommonTailLength(CurMBB, (MergePotentials.end()-2)->second,
 241                               BBI1, BBI2);
 242
 243     // If the tails don't have at least two instructions in common, see if there
 244     // is anything else in the equivalence class that does match.
 245     if (CommonTailLen < 2) {
 246       unsigned FoundMatch = ~0U;
 247       for (int i = MergePotentials.size()-2;
 248            i != -1 && MergePotentials[i].first == CurHash; --i) {
 249         CommonTailLen = ComputeCommonTailLength(CurMBB,
 250                                                 MergePotentials[i].second,
 251                                                 BBI1, BBI2);
 252         if (CommonTailLen >= 2) {
 253           FoundMatch = i;
 254           break;
 255         }
 256       }
 257
 258       // If we didn't find anything that has at least two instructions matching
 259       // this one, bail out.
 260       if (FoundMatch == ~0U) {
 261         MergePotentials.pop_back();
 262         continue;
 263       }
 264
 265       // Otherwise, move the matching block to the right position.
 266       std::swap(MergePotentials[FoundMatch], *(MergePotentials.end()-2));
 267     }
 268
 269     // If either block is the entire common tail, make the longer one branch to
 270     // the shorter one.
 271     MachineBasicBlock *MBB2 = (MergePotentials.end()-2)->second;
 272     if (CurMBB->begin() == BBI1) {
 273       // Hack the end off MBB2, making it jump to CurMBB instead.
 274       ReplaceTailWithBranchTo(BBI2, CurMBB);
 275       // This modifies MBB2, so remove it from the worklist.
 276       MergePotentials.erase(MergePotentials.end()-2);
 277       MadeChange = true;
 278       continue;
 279     } else if (MBB2->begin() == BBI2) {
 280       // Hack the end off CurMBB, making it jump to MBBI@ instead.
 281       ReplaceTailWithBranchTo(BBI1, MBB2);
 282       // This modifies CurMBB, so remove it from the worklist.
 283       MergePotentials.pop_back();
 284       MadeChange = true;
 285       continue;
 286     }
 287
 288     MergePotentials.pop_back();
 289   }
 290
 291   return MadeChange;
 292 }
 293
 294
 295 //===----------------------------------------------------------------------===//
 296 //  Branch Optimization
 297 //===----------------------------------------------------------------------===//
 298
 299 bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
 300   MadeChange = false;
 301
 302   for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
 303     MachineBasicBlock *MBB = I++;
 304     OptimizeBlock(MBB);
 305
 306     // If it is dead, remove it.
 307     if (MBB->pred_empty()) {
 308       RemoveDeadBlock(MBB);
 309       MadeChange = true;
 310       ++NumDeadBlocks;
 311     }
 312   }
 313   return MadeChange;
 314 }
 315
 316
 317 /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the
 318 /// CFG to be inserted.  If we have proven that MBB can only branch to DestA and
 319 /// DestB, remove any other MBB successors from the CFG.  DestA and DestB can
 320 /// be null.
 321 static bool CorrectExtraCFGEdges(MachineBasicBlock &MBB,
 322                                  MachineBasicBlock *DestA,
 323                                  MachineBasicBlock *DestB,
 324                                  bool isCond,
 325                                  MachineFunction::iterator FallThru) {
 326   bool MadeChange = false;
 327   bool AddedFallThrough = false;
 328
 329   // If this block ends with a conditional branch that falls through to its
 330   // successor, set DestB as the successor.
 331   if (isCond) {
 332     if (DestB == 0 && FallThru != MBB.getParent()->end()) {
 333       DestB = FallThru;
 334       AddedFallThrough = true;
 335     }
 336   } else {
 337     // If this is an unconditional branch with no explicit dest, it must just be
 338     // a fallthrough into DestB.
 339     if (DestA == 0 && FallThru != MBB.getParent()->end()) {
 340       DestA = FallThru;
 341       AddedFallThrough = true;
 342     }
 343   }
 344
 345   MachineBasicBlock::pred_iterator SI = MBB.succ_begin();
 346   while (SI != MBB.succ_end()) {
 347     if (*SI == DestA) {
 348       DestA = 0;
 349       ++SI;
 350     } else if (*SI == DestB) {
 351       DestB = 0;
 352       ++SI;
 353     } else {
 354       // Otherwise, this is a superfluous edge, remove it.
 355       MBB.removeSuccessor(SI);
 356       MadeChange = true;
 357     }
 358   }
 359   if (!AddedFallThrough) {
 360     assert(DestA == 0 && DestB == 0 &&
 361            "MachineCFG is missing edges!");
 362   } else if (isCond) {
 363     assert(DestA == 0 && "MachineCFG is missing edges!");
 364   }
 365   return MadeChange;
 366 }
 367
 368
 369 /// ReplaceUsesOfBlockWith - Given a machine basic block 'BB' that branched to
 370 /// 'Old', change the code and CFG so that it branches to 'New' instead.
 371 static void ReplaceUsesOfBlockWith(MachineBasicBlock *BB,
 372                                    MachineBasicBlock *Old,
 373                                    MachineBasicBlock *New,
 374                                    const TargetInstrInfo *TII) {
 375   assert(Old != New && "Cannot replace self with self!");
 376
 377   MachineBasicBlock::iterator I = BB->end();
 378   while (I != BB->begin()) {
 379     --I;
 380     if (!TII->isTerminatorInstr(I->getOpcode())) break;
 381
 382     // Scan the operands of this machine instruction, replacing any uses of Old
 383     // with New.
 384     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 385       if (I->getOperand(i).isMachineBasicBlock() &&
 386           I->getOperand(i).getMachineBasicBlock() == Old)
 387         I->getOperand(i).setMachineBasicBlock(New);
 388   }
 389
 390   // Update the successor information.
 391   std::vector<MachineBasicBlock*> Succs(BB->succ_begin(), BB->succ_end());
 392   for (int i = Succs.size()-1; i >= 0; --i)
 393     if (Succs[i] == Old) {
 394       BB->removeSuccessor(Old);
 395       BB->addSuccessor(New);
 396     }
 397 }
 398
 399 /// CanFallThrough - Return true of the specified branch condition can transfer
 400 /// control to FallthroughBlock, the block immediately after the branch.
 401 static bool CanFallThrough(MachineBasicBlock *TBB,
 402                            MachineBasicBlock *FBB,
 403                            const std::vector<MachineOperand> &Cond,
 404                            MachineFunction::iterator FallthroughBlock) {
 405   // If there is no branch, control always falls through.
 406   if (TBB == 0) return true;
 407
 408   // If there is some explicit branch to the fallthrough block, it can obviously
 409   // reach, even though the branch should get folded to fall through implicitly.
 410   if (MachineFunction::iterator(TBB) == FallthroughBlock ||
 411       MachineFunction::iterator(FBB) == FallthroughBlock)
 412     return true;
 413
 414   // If it's an unconditional branch to some block not the fall through, it
 415   // doesn't fall through.
 416   if (Cond.empty()) return false;
 417
 418   // Otherwise, if it is conditional and has no explicit false block, it falls
 419   // through.
 420   return FBB == 0;
 421 }
 422
 423 /// OptimizeBlock - Analyze and optimize control flow related to the specified
 424 /// block.  This is never called on the entry block.
 425 void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
 426   MachineFunction::iterator FallThrough = MBB;
 427   ++FallThrough;
 428
 429   // If this block is empty, make everyone use its fall-through, not the block
 430   // explicitly.
 431   if (MBB->empty()) {
 432     // Dead block?  Leave for cleanup later.
 433     if (MBB->pred_empty()) return;
 434
 435     if (FallThrough == MBB->getParent()->end()) {
 436       // TODO: Simplify preds to not branch here if possible!
 437     } else {
 438       // Rewrite all predecessors of the old block to go to the fallthrough
 439       // instead.
 440       while (!MBB->pred_empty()) {
 441         MachineBasicBlock *Pred = *(MBB->pred_end()-1);
 442         ReplaceUsesOfBlockWith(Pred, MBB, FallThrough, TII);
 443       }
 444
 445       // If MBB was the target of a jump table, update jump tables to go to the
 446       // fallthrough instead.
 447       MBB->getParent()->getJumpTableInfo()->ReplaceMBBInJumpTables(MBB,
 448                                                                    FallThrough);
 449       MadeChange = true;
 450     }
 451     return;
 452   }
 453
 454   // Check to see if we can simplify the terminator of the block before this
 455   // one.
 456   MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB));
 457
 458   MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
 459   std::vector<MachineOperand> PriorCond;
 460   bool PriorUnAnalyzable = false;
 461   PriorUnAnalyzable = TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond);
 462   if (!PriorUnAnalyzable) {
 463     // If the CFG for the prior block has extra edges, remove them.
 464     MadeChange |= CorrectExtraCFGEdges(PrevBB, PriorTBB, PriorFBB,
 465                                        !PriorCond.empty(), MBB);
 466
 467     // If the previous branch is conditional and both conditions go to the same
 468     // destination, remove the branch, replacing it with an unconditional one or
 469     // a fall-through.
 470     if (PriorTBB && PriorTBB == PriorFBB) {
 471       TII->RemoveBranch(PrevBB);
 472       PriorCond.clear();
 473       if (PriorTBB != MBB)
 474         TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond);
 475       MadeChange = true;
 476       ++NumBranchOpts;
 477       return OptimizeBlock(MBB);
 478     }
 479
 480     // If the previous branch *only* branches to *this* block (conditional or
 481     // not) remove the branch.
 482     if (PriorTBB == MBB && PriorFBB == 0) {
 483       TII->RemoveBranch(PrevBB);
 484       MadeChange = true;
 485       ++NumBranchOpts;
 486       return OptimizeBlock(MBB);
 487     }
 488
 489     // If the prior block branches somewhere else on the condition and here if
 490     // the condition is false, remove the uncond second branch.
 491     if (PriorFBB == MBB) {
 492       TII->RemoveBranch(PrevBB);
 493       TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond);
 494       MadeChange = true;
 495       ++NumBranchOpts;
 496       return OptimizeBlock(MBB);
 497     }
 498
 499     // If the prior block branches here on true and somewhere else on false, and
 500     // if the branch condition is reversible, reverse the branch to create a
 501     // fall-through.
 502     if (PriorTBB == MBB) {
 503       std::vector<MachineOperand> NewPriorCond(PriorCond);
 504       if (!TII->ReverseBranchCondition(NewPriorCond)) {
 505         TII->RemoveBranch(PrevBB);
 506         TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond);
 507         MadeChange = true;
 508         ++NumBranchOpts;
 509         return OptimizeBlock(MBB);
 510       }
 511     }
 512   }
 513
 514   // Analyze the branch in the current block.
 515   MachineBasicBlock *CurTBB = 0, *CurFBB = 0;
 516   std::vector<MachineOperand> CurCond;
 517   if (!TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond)) {
 518     // If the CFG for the prior block has extra edges, remove them.
 519     MadeChange |= CorrectExtraCFGEdges(*MBB, CurTBB, CurFBB,
 520                                        !CurCond.empty(),
 521                                        ++MachineFunction::iterator(MBB));
 522
 523     // If this branch is the only thing in its block, see if we can forward
 524     // other blocks across it.
 525     if (CurTBB && CurCond.empty() && CurFBB == 0 &&
 526         TII->isBranch(MBB->begin()->getOpcode()) && CurTBB != MBB) {
 527       // This block may contain just an unconditional branch.  Because there can
 528       // be 'non-branch terminators' in the block, try removing the branch and
 529       // then seeing if the block is empty.
 530       TII->RemoveBranch(*MBB);
 531
 532       // If this block is just an unconditional branch to CurTBB, we can
 533       // usually completely eliminate the block.  The only case we cannot
 534       // completely eliminate the block is when the block before this one
 535       // falls through into MBB and we can't understand the prior block's branch
 536       // condition.
 537       if (MBB->empty() && (!PriorUnAnalyzable || !PrevBB.isSuccessor(MBB))) {
 538         // If the prior block falls through into us, turn it into an
 539         // explicit branch to us to make updates simpler.
 540         if (PrevBB.isSuccessor(MBB) && PriorTBB != MBB && PriorFBB != MBB) {
 541           if (PriorTBB == 0) {
 542             assert(PriorCond.empty() && PriorFBB == 0 && "Bad branch analysis");
 543             PriorTBB = MBB;
 544           } else {
 545             assert(PriorFBB == 0 && "Machine CFG out of date!");
 546             PriorFBB = MBB;
 547           }
 548           TII->RemoveBranch(PrevBB);
 549           TII->InsertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond);
 550         }
 551
 552         // Iterate through all the predecessors, revectoring each in-turn.
 553         MachineBasicBlock::pred_iterator PI = MBB->pred_begin();
 554         bool DidChange = false;
 555         bool HasBranchToSelf = false;
 556         while (PI != MBB->pred_end()) {
 557           if (*PI == MBB) {
 558             // If this block has an uncond branch to itself, leave it.
 559             ++PI;
 560             HasBranchToSelf = true;
 561           } else {
 562             DidChange = true;
 563             ReplaceUsesOfBlockWith(*PI, MBB, CurTBB, TII);
 564           }
 565         }
 566
 567         // Change any jumptables to go to the new MBB.
 568         MBB->getParent()->getJumpTableInfo()->ReplaceMBBInJumpTables(MBB,
 569                                                                      CurTBB);
 570         if (DidChange) {
 571           ++NumBranchOpts;
 572           MadeChange = true;
 573           if (!HasBranchToSelf) return;
 574         }
 575       }
 576
 577       // Add the branch back if the block is more than just an uncond branch.
 578       TII->InsertBranch(*MBB, CurTBB, 0, CurCond);
 579     }
 580
 581     // If the prior block doesn't fall through into this block, and if this
 582     // block doesn't fall through into some other block, see if we can find a
 583     // place to move this block where a fall-through will happen.
 584     if (!PriorUnAnalyzable && !CanFallThrough(PriorTBB, PriorFBB,
 585                                               PriorCond, MBB)) {
 586       // Now we know that there was no fall-through into this block, check to
 587       // see if it has fall-throughs.
 588       if (!CanFallThrough(CurTBB, CurFBB, CurCond, FallThrough)) {
 589
 590         // Check all the predecessors of this block.  If one of them has no fall
 591         // throughs, move this block right after it.
 592         for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
 593              E = MBB->pred_end(); PI != E; ++PI) {
 594           // Analyze the branch at the end of the pred.
 595           MachineBasicBlock *PredBB = *PI;
 596           MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough;
 597           MachineBasicBlock *PredTBB = 0, *PredFBB = 0;
 598           std::vector<MachineOperand> PredCond;
 599           if (PredBB != MBB &&
 600               !TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond) &&
 601               !CanFallThrough(PredTBB, PredFBB, PredCond, PredFallthrough)) {
 602             MBB->moveAfter(PredBB);
 603             MadeChange = true;
 604             return OptimizeBlock(MBB);
 605           }
 606         }
 607
 608         // Check all successors to see if we can move this block before it.
 609         for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 610              E = MBB->succ_end(); SI != E; ++SI) {
 611           // Analyze the branch at the end of the block before the succ.
 612           MachineBasicBlock *SuccBB = *SI;
 613           MachineFunction::iterator SuccPrev = SuccBB; --SuccPrev;
 614           MachineBasicBlock *SuccPrevTBB = 0, *SuccPrevFBB = 0;
 615           std::vector<MachineOperand> SuccPrevCond;
 616           if (SuccBB != MBB &&
 617               !TII->AnalyzeBranch(*SuccPrev, SuccPrevTBB, SuccPrevFBB,
 618                                   SuccPrevCond) &&
 619               !CanFallThrough(SuccPrevTBB, SuccPrevFBB, SuccPrevCond, SuccBB)) {
 620             MBB->moveBefore(SuccBB);
 621             MadeChange = true;
 622             return OptimizeBlock(MBB);
 623           }
 624         }
 625
 626         // Okay, there is no really great place to put this block.  If, however,
 627         // the block before this one would be a fall-through if this block were
 628         // removed, move this block to the end of the function.
 629         if (FallThrough != MBB->getParent()->end() &&
 630             CanFallThrough(PriorTBB, PriorFBB, PriorCond, FallThrough)) {
 631           MBB->moveAfter(--MBB->getParent()->end());
 632           MadeChange = true;
 633           return;
 634         }
 635       }
 636     }
 637   }
 638 }