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   // See if any jump tables have become mergable or dead as the code generator
 102   // did its thing.
 103   MachineJumpTableInfo *JTI = MF.getJumpTableInfo();
 104   const std::vector<MachineJumpTableEntry> &JTs = JTI->getJumpTables();
 105   if (!JTs.empty()) {
 106     // Figure out how these jump tables should be merged.
 107     std::vector<unsigned> JTMapping;
 108     JTMapping.reserve(JTs.size());
 109
 110     // We always keep the 0th jump table.
 111     JTMapping.push_back(0);
 112
 113     // Scan the jump tables, seeing if there are any duplicates.  Note that this
 114     // is N^2, which should be fixed someday.
 115     for (unsigned i = 1, e = JTs.size(); i != e; ++i)
 116       JTMapping.push_back(JTI->getJumpTableIndex(JTs[i].MBBs));
 117
 118     // If a jump table was merge with another one, walk the function rewriting
 119     // references to jump tables to reference the new JT ID's.  Keep track of
 120     // whether we see a jump table idx, if not, we can delete the JT.
 121     std::vector<bool> JTIsLive;
 122     JTIsLive.resize(JTs.size());
 123     for (MachineFunction::iterator BB = MF.begin(), E = MF.end();
 124          BB != E; ++BB) {
 125       for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end();
 126            I != E; ++I)
 127         for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) {
 128           MachineOperand &Op = I->getOperand(op);
 129           if (!Op.isJumpTableIndex()) continue;
 130           unsigned NewIdx = JTMapping[Op.getJumpTableIndex()];
 131           Op.setJumpTableIndex(NewIdx);
 132
 133           // Remember that this JT is live.
 134           JTIsLive[NewIdx] = true;
 135         }
 136     }
 137
 138     // Finally, remove dead jump tables.  This happens either because the
 139     // indirect jump was unreachable (and thus deleted) or because the jump
 140     // table was merged with some other one.
 141     for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i)
 142       if (!JTIsLive[i]) {
 143         JTI->RemoveJumpTable(i);
 144         EverMadeChange = true;
 145       }
 146   }
 147
 148   return EverMadeChange;
 149 }
 150
 151 //===----------------------------------------------------------------------===//
 152 //  Tail Merging of Blocks
 153 //===----------------------------------------------------------------------===//
 154
 155 /// HashMachineInstr - Compute a hash value for MI and its operands.
 156 static unsigned HashMachineInstr(const MachineInstr *MI) {
 157   unsigned Hash = MI->getOpcode();
 158   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 159     const MachineOperand &Op = MI->getOperand(i);
 160
 161     // Merge in bits from the operand if easy.
 162     unsigned OperandHash = 0;
 163     switch (Op.getType()) {
 164     case MachineOperand::MO_Register:          OperandHash = Op.getReg(); break;
 165     case MachineOperand::MO_Immediate:         OperandHash = Op.getImm(); break;
 166     case MachineOperand::MO_MachineBasicBlock:
 167       OperandHash = Op.getMachineBasicBlock()->getNumber();
 168       break;
 169     case MachineOperand::MO_FrameIndex: OperandHash = Op.getFrameIndex(); break;
 170     case MachineOperand::MO_ConstantPoolIndex:
 171       OperandHash = Op.getConstantPoolIndex();
 172       break;
 173     case MachineOperand::MO_JumpTableIndex:
 174       OperandHash = Op.getJumpTableIndex();
 175       break;
 176     case MachineOperand::MO_GlobalAddress:
 177     case MachineOperand::MO_ExternalSymbol:
 178       // Global address / external symbol are too hard, don't bother, but do
 179       // pull in the offset.
 180       OperandHash = Op.getOffset();
 181       break;
 182     default: break;
 183     }
 184
 185     Hash += ((OperandHash << 3) | Op.getType()) << (i&31);
 186   }
 187   return Hash;
 188 }
 189
 190 /// HashEndOfMBB - Hash the last two instructions in the MBB.  We hash two
 191 /// instructions, because cross-jumping only saves code when at least two
 192 /// instructions are removed (since a branch must be inserted).
 193 static unsigned HashEndOfMBB(const MachineBasicBlock *MBB) {
 194   MachineBasicBlock::const_iterator I = MBB->end();
 195   if (I == MBB->begin())
 196     return 0;   // Empty MBB.
 197
 198   --I;
 199   unsigned Hash = HashMachineInstr(I);
 200
 201   if (I == MBB->begin())
 202     return Hash;   // Single instr MBB.
 203
 204   --I;
 205   // Hash in the second-to-last instruction.
 206   Hash ^= HashMachineInstr(I) << 2;
 207   return Hash;
 208 }
 209
 210 /// ComputeCommonTailLength - Given two machine basic blocks, compute the number
 211 /// of instructions they actually have in common together at their end.  Return
 212 /// iterators for the first shared instruction in each block.
 213 static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1,
 214                                         MachineBasicBlock *MBB2,
 215                                         MachineBasicBlock::iterator &I1,
 216                                         MachineBasicBlock::iterator &I2) {
 217   I1 = MBB1->end();
 218   I2 = MBB2->end();
 219
 220   unsigned TailLen = 0;
 221   while (I1 != MBB1->begin() && I2 != MBB2->begin()) {
 222     --I1; --I2;
 223     if (!I1->isIdenticalTo(I2)) {
 224       ++I1; ++I2;
 225       break;
 226     }
 227     ++TailLen;
 228   }
 229   return TailLen;
 230 }
 231
 232 /// ReplaceTailWithBranchTo - Delete the instruction OldInst and everything
 233 /// after it, replacing it with an unconditional branch to NewDest.  This
 234 /// returns true if OldInst's block is modified, false if NewDest is modified.
 235 void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
 236                                            MachineBasicBlock *NewDest) {
 237   MachineBasicBlock *OldBB = OldInst->getParent();
 238
 239   // Remove all the old successors of OldBB from the CFG.
 240   while (!OldBB->succ_empty())
 241     OldBB->removeSuccessor(OldBB->succ_begin());
 242
 243   // Remove all the dead instructions from the end of OldBB.
 244   OldBB->erase(OldInst, OldBB->end());
 245
 246   // If OldBB isn't immediately before OldBB, insert a branch to it.
 247   if (++MachineFunction::iterator(OldBB) != MachineFunction::iterator(NewDest))
 248     TII->InsertBranch(*OldBB, NewDest, 0, std::vector<MachineOperand>());
 249   OldBB->addSuccessor(NewDest);
 250   ++NumTailMerge;
 251 }
 252
 253 bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
 254   MadeChange = false;
 255
 256   return false;
 257
 258   // Find blocks with no successors.
 259   std::vector<std::pair<unsigned,MachineBasicBlock*> > MergePotentials;
 260   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
 261     if (I->succ_empty())
 262       MergePotentials.push_back(std::make_pair(HashEndOfMBB(I), I));
 263   }
 264
 265   // Sort by hash value so that blocks with identical end sequences sort
 266   // together.
 267   std::stable_sort(MergePotentials.begin(), MergePotentials.end());
 268
 269   // Walk through equivalence sets looking for actual exact matches.
 270   while (MergePotentials.size() > 1) {
 271     unsigned CurHash  = (MergePotentials.end()-1)->first;
 272     unsigned PrevHash = (MergePotentials.end()-2)->first;
 273     MachineBasicBlock *CurMBB = (MergePotentials.end()-1)->second;
 274
 275     // If there is nothing that matches the hash of the current basic block,
 276     // give up.
 277     if (CurHash != PrevHash) {
 278       MergePotentials.pop_back();
 279       continue;
 280     }
 281
 282     // Determine the actual length of the shared tail between these two basic
 283     // blocks.  Because the hash can have collisions, it's possible that this is
 284     // less than 2.
 285     MachineBasicBlock::iterator BBI1, BBI2;
 286     unsigned CommonTailLen =
 287       ComputeCommonTailLength(CurMBB, (MergePotentials.end()-2)->second,
 288                               BBI1, BBI2);
 289
 290     // If the tails don't have at least two instructions in common, see if there
 291     // is anything else in the equivalence class that does match.
 292     if (CommonTailLen < 2) {
 293       unsigned FoundMatch = ~0U;
 294       for (int i = MergePotentials.size()-2;
 295            i != -1 && MergePotentials[i].first == CurHash; --i) {
 296         CommonTailLen = ComputeCommonTailLength(CurMBB,
 297                                                 MergePotentials[i].second,
 298                                                 BBI1, BBI2);
 299         if (CommonTailLen >= 2) {
 300           FoundMatch = i;
 301           break;
 302         }
 303       }
 304
 305       // If we didn't find anything that has at least two instructions matching
 306       // this one, bail out.
 307       if (FoundMatch == ~0U) {
 308         MergePotentials.pop_back();
 309         continue;
 310       }
 311
 312       // Otherwise, move the matching block to the right position.
 313       std::swap(MergePotentials[FoundMatch], *(MergePotentials.end()-2));
 314     }
 315
 316     // If either block is the entire common tail, make the longer one branch to
 317     // the shorter one.
 318     MachineBasicBlock *MBB2 = (MergePotentials.end()-2)->second;
 319     if (CurMBB->begin() == BBI1) {
 320       // Hack the end off MBB2, making it jump to CurMBB instead.
 321       ReplaceTailWithBranchTo(BBI2, CurMBB);
 322       // This modifies MBB2, so remove it from the worklist.
 323       MergePotentials.erase(MergePotentials.end()-2);
 324       MadeChange = true;
 325       continue;
 326     } else if (MBB2->begin() == BBI2) {
 327       // Hack the end off CurMBB, making it jump to MBBI@ instead.
 328       ReplaceTailWithBranchTo(BBI1, MBB2);
 329       // This modifies CurMBB, so remove it from the worklist.
 330       MergePotentials.pop_back();
 331       MadeChange = true;
 332       continue;
 333     }
 334
 335     MergePotentials.pop_back();
 336   }
 337
 338   return MadeChange;
 339 }
 340
 341
 342 //===----------------------------------------------------------------------===//
 343 //  Branch Optimization
 344 //===----------------------------------------------------------------------===//
 345
 346 bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
 347   MadeChange = false;
 348
 349   for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
 350     MachineBasicBlock *MBB = I++;
 351     OptimizeBlock(MBB);
 352
 353     // If it is dead, remove it.
 354     if (MBB->pred_empty()) {
 355       RemoveDeadBlock(MBB);
 356       MadeChange = true;
 357       ++NumDeadBlocks;
 358     }
 359   }
 360   return MadeChange;
 361 }
 362
 363
 364 /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the
 365 /// CFG to be inserted.  If we have proven that MBB can only branch to DestA and
 366 /// DestB, remove any other MBB successors from the CFG.  DestA and DestB can
 367 /// be null.
 368 static bool CorrectExtraCFGEdges(MachineBasicBlock &MBB,
 369                                  MachineBasicBlock *DestA,
 370                                  MachineBasicBlock *DestB,
 371                                  bool isCond,
 372                                  MachineFunction::iterator FallThru) {
 373   bool MadeChange = false;
 374   bool AddedFallThrough = false;
 375
 376   // If this block ends with a conditional branch that falls through to its
 377   // successor, set DestB as the successor.
 378   if (isCond) {
 379     if (DestB == 0 && FallThru != MBB.getParent()->end()) {
 380       DestB = FallThru;
 381       AddedFallThrough = true;
 382     }
 383   } else {
 384     // If this is an unconditional branch with no explicit dest, it must just be
 385     // a fallthrough into DestB.
 386     if (DestA == 0 && FallThru != MBB.getParent()->end()) {
 387       DestA = FallThru;
 388       AddedFallThrough = true;
 389     }
 390   }
 391
 392   MachineBasicBlock::pred_iterator SI = MBB.succ_begin();
 393   while (SI != MBB.succ_end()) {
 394     if (*SI == DestA) {
 395       DestA = 0;
 396       ++SI;
 397     } else if (*SI == DestB) {
 398       DestB = 0;
 399       ++SI;
 400     } else {
 401       // Otherwise, this is a superfluous edge, remove it.
 402       MBB.removeSuccessor(SI);
 403       MadeChange = true;
 404     }
 405   }
 406   if (!AddedFallThrough) {
 407     assert(DestA == 0 && DestB == 0 &&
 408            "MachineCFG is missing edges!");
 409   } else if (isCond) {
 410     assert(DestA == 0 && "MachineCFG is missing edges!");
 411   }
 412   return MadeChange;
 413 }
 414
 415
 416 /// ReplaceUsesOfBlockWith - Given a machine basic block 'BB' that branched to
 417 /// 'Old', change the code and CFG so that it branches to 'New' instead.
 418 static void ReplaceUsesOfBlockWith(MachineBasicBlock *BB,
 419                                    MachineBasicBlock *Old,
 420                                    MachineBasicBlock *New,
 421                                    const TargetInstrInfo *TII) {
 422   assert(Old != New && "Cannot replace self with self!");
 423
 424   MachineBasicBlock::iterator I = BB->end();
 425   while (I != BB->begin()) {
 426     --I;
 427     if (!TII->isTerminatorInstr(I->getOpcode())) break;
 428
 429     // Scan the operands of this machine instruction, replacing any uses of Old
 430     // with New.
 431     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 432       if (I->getOperand(i).isMachineBasicBlock() &&
 433           I->getOperand(i).getMachineBasicBlock() == Old)
 434         I->getOperand(i).setMachineBasicBlock(New);
 435   }
 436
 437   // Update the successor information.
 438   std::vector<MachineBasicBlock*> Succs(BB->succ_begin(), BB->succ_end());
 439   for (int i = Succs.size()-1; i >= 0; --i)
 440     if (Succs[i] == Old) {
 441       BB->removeSuccessor(Old);
 442       BB->addSuccessor(New);
 443     }
 444 }
 445
 446 /// CanFallThrough - Return true of the specified branch condition can transfer
 447 /// control to FallthroughBlock, the block immediately after the branch.
 448 static bool CanFallThrough(MachineBasicBlock *TBB,
 449                            MachineBasicBlock *FBB,
 450                            const std::vector<MachineOperand> &Cond,
 451                            MachineFunction::iterator FallthroughBlock) {
 452   // If there is no branch, control always falls through.
 453   if (TBB == 0) return true;
 454
 455   // If there is some explicit branch to the fallthrough block, it can obviously
 456   // reach, even though the branch should get folded to fall through implicitly.
 457   if (MachineFunction::iterator(TBB) == FallthroughBlock ||
 458       MachineFunction::iterator(FBB) == FallthroughBlock)
 459     return true;
 460
 461   // If it's an unconditional branch to some block not the fall through, it
 462   // doesn't fall through.
 463   if (Cond.empty()) return false;
 464
 465   // Otherwise, if it is conditional and has no explicit false block, it falls
 466   // through.
 467   return FBB == 0;
 468 }
 469
 470 /// OptimizeBlock - Analyze and optimize control flow related to the specified
 471 /// block.  This is never called on the entry block.
 472 void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
 473   MachineFunction::iterator FallThrough = MBB;
 474   ++FallThrough;
 475
 476   // If this block is empty, make everyone use its fall-through, not the block
 477   // explicitly.
 478   if (MBB->empty()) {
 479     // Dead block?  Leave for cleanup later.
 480     if (MBB->pred_empty()) return;
 481
 482     if (FallThrough == MBB->getParent()->end()) {
 483       // TODO: Simplify preds to not branch here if possible!
 484     } else {
 485       // Rewrite all predecessors of the old block to go to the fallthrough
 486       // instead.
 487       while (!MBB->pred_empty()) {
 488         MachineBasicBlock *Pred = *(MBB->pred_end()-1);
 489         ReplaceUsesOfBlockWith(Pred, MBB, FallThrough, TII);
 490       }
 491
 492       // If MBB was the target of a jump table, update jump tables to go to the
 493       // fallthrough instead.
 494       MBB->getParent()->getJumpTableInfo()->
 495         ReplaceMBBInJumpTables(MBB, FallThrough);
 496       MadeChange = true;
 497     }
 498     return;
 499   }
 500
 501   // Check to see if we can simplify the terminator of the block before this
 502   // one.
 503   MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB));
 504
 505   MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
 506   std::vector<MachineOperand> PriorCond;
 507   bool PriorUnAnalyzable = false;
 508   PriorUnAnalyzable = TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond);
 509   if (!PriorUnAnalyzable) {
 510     // If the CFG for the prior block has extra edges, remove them.
 511     MadeChange |= CorrectExtraCFGEdges(PrevBB, PriorTBB, PriorFBB,
 512                                        !PriorCond.empty(), MBB);
 513
 514     // If the previous branch is conditional and both conditions go to the same
 515     // destination, remove the branch, replacing it with an unconditional one or
 516     // a fall-through.
 517     if (PriorTBB && PriorTBB == PriorFBB) {
 518       TII->RemoveBranch(PrevBB);
 519       PriorCond.clear();
 520       if (PriorTBB != MBB)
 521         TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond);
 522       MadeChange = true;
 523       ++NumBranchOpts;
 524       return OptimizeBlock(MBB);
 525     }
 526
 527     // If the previous branch *only* branches to *this* block (conditional or
 528     // not) remove the branch.
 529     if (PriorTBB == MBB && PriorFBB == 0) {
 530       TII->RemoveBranch(PrevBB);
 531       MadeChange = true;
 532       ++NumBranchOpts;
 533       return OptimizeBlock(MBB);
 534     }
 535
 536     // If the prior block branches somewhere else on the condition and here if
 537     // the condition is false, remove the uncond second branch.
 538     if (PriorFBB == MBB) {
 539       TII->RemoveBranch(PrevBB);
 540       TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond);
 541       MadeChange = true;
 542       ++NumBranchOpts;
 543       return OptimizeBlock(MBB);
 544     }
 545
 546     // If the prior block branches here on true and somewhere else on false, and
 547     // if the branch condition is reversible, reverse the branch to create a
 548     // fall-through.
 549     if (PriorTBB == MBB) {
 550       std::vector<MachineOperand> NewPriorCond(PriorCond);
 551       if (!TII->ReverseBranchCondition(NewPriorCond)) {
 552         TII->RemoveBranch(PrevBB);
 553         TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond);
 554         MadeChange = true;
 555         ++NumBranchOpts;
 556         return OptimizeBlock(MBB);
 557       }
 558     }
 559   }
 560
 561   // Analyze the branch in the current block.
 562   MachineBasicBlock *CurTBB = 0, *CurFBB = 0;
 563   std::vector<MachineOperand> CurCond;
 564   if (!TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond)) {
 565     // If the CFG for the prior block has extra edges, remove them.
 566     MadeChange |= CorrectExtraCFGEdges(*MBB, CurTBB, CurFBB,
 567                                        !CurCond.empty(),
 568                                        ++MachineFunction::iterator(MBB));
 569
 570     // If this branch is the only thing in its block, see if we can forward
 571     // other blocks across it.
 572     if (CurTBB && CurCond.empty() && CurFBB == 0 &&
 573         TII->isBranch(MBB->begin()->getOpcode()) && CurTBB != MBB) {
 574       // This block may contain just an unconditional branch.  Because there can
 575       // be 'non-branch terminators' in the block, try removing the branch and
 576       // then seeing if the block is empty.
 577       TII->RemoveBranch(*MBB);
 578
 579       // If this block is just an unconditional branch to CurTBB, we can
 580       // usually completely eliminate the block.  The only case we cannot
 581       // completely eliminate the block is when the block before this one
 582       // falls through into MBB and we can't understand the prior block's branch
 583       // condition.
 584       if (MBB->empty()) {
 585         bool PredHasNoFallThrough = TII->BlockHasNoFallThrough(PrevBB);
 586         if (PredHasNoFallThrough || !PriorUnAnalyzable ||
 587             !PrevBB.isSuccessor(MBB)) {
 588           // If the prior block falls through into us, turn it into an
 589           // explicit branch to us to make updates simpler.
 590           if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) &&
 591               PriorTBB != MBB && PriorFBB != MBB) {
 592             if (PriorTBB == 0) {
 593               assert(PriorCond.empty() && PriorFBB == 0 &&
 594                      "Bad branch analysis");
 595               PriorTBB = MBB;
 596             } else {
 597               assert(PriorFBB == 0 && "Machine CFG out of date!");
 598               PriorFBB = MBB;
 599             }
 600             TII->RemoveBranch(PrevBB);
 601             TII->InsertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond);
 602           }
 603
 604           // Iterate through all the predecessors, revectoring each in-turn.
 605           MachineBasicBlock::pred_iterator PI = MBB->pred_begin();
 606           bool DidChange = false;
 607           bool HasBranchToSelf = false;
 608           while (PI != MBB->pred_end()) {
 609             if (*PI == MBB) {
 610               // If this block has an uncond branch to itself, leave it.
 611               ++PI;
 612               HasBranchToSelf = true;
 613             } else {
 614               DidChange = true;
 615               ReplaceUsesOfBlockWith(*PI, MBB, CurTBB, TII);
 616             }
 617           }
 618
 619           // Change any jumptables to go to the new MBB.
 620           MBB->getParent()->getJumpTableInfo()->
 621             ReplaceMBBInJumpTables(MBB, CurTBB);
 622           if (DidChange) {
 623             ++NumBranchOpts;
 624             MadeChange = true;
 625             if (!HasBranchToSelf) return;
 626           }
 627         }
 628       }
 629
 630       // Add the branch back if the block is more than just an uncond branch.
 631       TII->InsertBranch(*MBB, CurTBB, 0, CurCond);
 632     }
 633
 634     // If the prior block doesn't fall through into this block, and if this
 635     // block doesn't fall through into some other block, see if we can find a
 636     // place to move this block where a fall-through will happen.
 637     if (!PriorUnAnalyzable && !CanFallThrough(PriorTBB, PriorFBB,
 638                                               PriorCond, MBB)) {
 639       // Now we know that there was no fall-through into this block, check to
 640       // see if it has fall-throughs.
 641       if (!CanFallThrough(CurTBB, CurFBB, CurCond, FallThrough)) {
 642
 643         // Check all the predecessors of this block.  If one of them has no fall
 644         // throughs, move this block right after it.
 645         for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
 646              E = MBB->pred_end(); PI != E; ++PI) {
 647           // Analyze the branch at the end of the pred.
 648           MachineBasicBlock *PredBB = *PI;
 649           MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough;
 650           MachineBasicBlock *PredTBB = 0, *PredFBB = 0;
 651           std::vector<MachineOperand> PredCond;
 652           if (PredBB != MBB &&
 653               !TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond) &&
 654               !CanFallThrough(PredTBB, PredFBB, PredCond, PredFallthrough)) {
 655             MBB->moveAfter(PredBB);
 656             MadeChange = true;
 657             return OptimizeBlock(MBB);
 658           }
 659         }
 660
 661         // Check all successors to see if we can move this block before it.
 662         for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 663              E = MBB->succ_end(); SI != E; ++SI) {
 664           // Analyze the branch at the end of the block before the succ.
 665           MachineBasicBlock *SuccBB = *SI;
 666           MachineFunction::iterator SuccPrev = SuccBB; --SuccPrev;
 667           MachineBasicBlock *SuccPrevTBB = 0, *SuccPrevFBB = 0;
 668           std::vector<MachineOperand> SuccPrevCond;
 669           if (SuccBB != MBB &&
 670               !TII->AnalyzeBranch(*SuccPrev, SuccPrevTBB, SuccPrevFBB,
 671                                   SuccPrevCond) &&
 672               !CanFallThrough(SuccPrevTBB, SuccPrevFBB, SuccPrevCond, SuccBB)) {
 673             MBB->moveBefore(SuccBB);
 674             MadeChange = true;
 675             return OptimizeBlock(MBB);
 676           }
 677         }
 678
 679         // Okay, there is no really great place to put this block.  If, however,
 680         // the block before this one would be a fall-through if this block were
 681         // removed, move this block to the end of the function.
 682         if (FallThrough != MBB->getParent()->end() &&
 683             CanFallThrough(PriorTBB, PriorFBB, PriorCond, FallThrough)) {
 684           MBB->moveAfter(--MBB->getParent()->end());
 685           MadeChange = true;
 686           return;
 687         }
 688       }
 689     }
 690   }
 691 }