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 static cl::opt<bool> EnableTailMerge("enable-tail-merge");
  34
  35 namespace {
  36   struct BranchFolder : public MachineFunctionPass {
  37     virtual bool runOnMachineFunction(MachineFunction &MF);
  38     virtual const char *getPassName() const { return "Control Flow Optimizer"; }
  39     const TargetInstrInfo *TII;
  40     MachineDebugInfo *MDI;
  41     bool MadeChange;
  42   private:
  43     // Tail Merging.
  44     bool TailMergeBlocks(MachineFunction &MF);
  45     void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
  46                                  MachineBasicBlock *NewDest);
  47
  48     // Branch optzn.
  49     bool OptimizeBranches(MachineFunction &MF);
  50     void OptimizeBlock(MachineFunction::iterator MBB);
  51     void RemoveDeadBlock(MachineBasicBlock *MBB);
  52   };
  53 }
  54
  55 FunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); }
  56
  57 /// RemoveDeadBlock - Remove the specified dead machine basic block from the
  58 /// function, updating the CFG.
  59 void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
  60   assert(MBB->pred_empty() && "MBB must be dead!");
  61
  62   MachineFunction *MF = MBB->getParent();
  63   // drop all successors.
  64   while (!MBB->succ_empty())
  65     MBB->removeSuccessor(MBB->succ_end()-1);
  66
  67   // If there is DWARF info to active, check to see if there are any DWARF_LABEL
  68   // records in the basic block.  If so, unregister them from MachineDebugInfo.
  69   if (MDI && !MBB->empty()) {
  70     unsigned DWARF_LABELOpc = TII->getDWARF_LABELOpcode();
  71     assert(DWARF_LABELOpc &&
  72            "Target supports dwarf but didn't implement getDWARF_LABELOpcode!");
  73
  74     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
  75          I != E; ++I) {
  76       if ((unsigned)I->getOpcode() == DWARF_LABELOpc) {
  77         // The label ID # is always operand #0, an immediate.
  78         MDI->RemoveLabelInfo(I->getOperand(0).getImm());
  79       }
  80     }
  81   }
  82
  83   // Remove the block.
  84   MF->getBasicBlockList().erase(MBB);
  85 }
  86
  87 bool BranchFolder::runOnMachineFunction(MachineFunction &MF) {
  88   TII = MF.getTarget().getInstrInfo();
  89   if (!TII) return false;
  90
  91   MDI = getAnalysisToUpdate<MachineDebugInfo>();
  92
  93   bool EverMadeChange = false;
  94   bool MadeChangeThisIteration = true;
  95   while (MadeChangeThisIteration) {
  96     MadeChangeThisIteration = false;
  97     MadeChangeThisIteration |= TailMergeBlocks(MF);
  98     MadeChangeThisIteration |= OptimizeBranches(MF);
  99     EverMadeChange |= MadeChangeThisIteration;
 100   }
 101
 102   return EverMadeChange;
 103 }
 104
 105 //===----------------------------------------------------------------------===//
 106 //  Tail Merging of Blocks
 107 //===----------------------------------------------------------------------===//
 108
 109 /// HashMachineInstr - Compute a hash value for MI and its operands.
 110 static unsigned HashMachineInstr(const MachineInstr *MI) {
 111   unsigned Hash = MI->getOpcode();
 112   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 113     const MachineOperand &Op = MI->getOperand(i);
 114
 115     // Merge in bits from the operand if easy.
 116     unsigned OperandHash = 0;
 117     switch (Op.getType()) {
 118     case MachineOperand::MO_Register:          OperandHash = Op.getReg(); break;
 119     case MachineOperand::MO_Immediate:         OperandHash = Op.getImm(); break;
 120     case MachineOperand::MO_MachineBasicBlock:
 121       OperandHash = Op.getMachineBasicBlock()->getNumber();
 122       break;
 123     case MachineOperand::MO_FrameIndex: OperandHash = Op.getFrameIndex(); break;
 124     case MachineOperand::MO_ConstantPoolIndex:
 125       OperandHash = Op.getConstantPoolIndex();
 126       break;
 127     case MachineOperand::MO_JumpTableIndex:
 128       OperandHash = Op.getJumpTableIndex();
 129       break;
 130     case MachineOperand::MO_GlobalAddress:
 131     case MachineOperand::MO_ExternalSymbol:
 132       // Global address / external symbol are too hard, don't bother, but do
 133       // pull in the offset.
 134       OperandHash = Op.getOffset();
 135       break;
 136     default: break;
 137     }
 138
 139     Hash += ((OperandHash << 3) | Op.getType()) << (i&31);
 140   }
 141   return Hash;
 142 }
 143
 144 /// HashEndOfMBB - Hash the last two instructions in the MBB.  We hash two
 145 /// instructions, because cross-jumping only saves code when at least two
 146 /// instructions are removed (since a branch must be inserted).
 147 static unsigned HashEndOfMBB(const MachineBasicBlock *MBB) {
 148   MachineBasicBlock::const_iterator I = MBB->end();
 149   if (I == MBB->begin())
 150     return 0;   // Empty MBB.
 151
 152   --I;
 153   unsigned Hash = HashMachineInstr(I);
 154
 155   if (I == MBB->begin())
 156     return Hash;   // Single instr MBB.
 157
 158   --I;
 159   // Hash in the second-to-last instruction.
 160   Hash ^= HashMachineInstr(I) << 2;
 161   return Hash;
 162 }
 163
 164 /// ComputeCommonTailLength - Given two machine basic blocks, compute the number
 165 /// of instructions they actually have in common together at their end.  Return
 166 /// iterators for the first shared instruction in each block.
 167 static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1,
 168                                         MachineBasicBlock *MBB2,
 169                                         MachineBasicBlock::iterator &I1,
 170                                         MachineBasicBlock::iterator &I2) {
 171   I1 = MBB1->end();
 172   I2 = MBB2->end();
 173
 174   unsigned TailLen = 0;
 175   while (I1 != MBB1->begin() && I2 != MBB2->begin()) {
 176     --I1; --I2;
 177     if (!I1->isIdenticalTo(I2)) {
 178       ++I1; ++I2;
 179       break;
 180     }
 181     ++TailLen;
 182   }
 183   return TailLen;
 184 }
 185
 186 /// ReplaceTailWithBranchTo - Delete the instruction OldInst and everything
 187 /// after it, replacing it with an unconditional branch to NewDest.
 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   TII->InsertBranch(*OldBB, NewDest, 0, std::vector<MachineOperand>());
 200   OldBB->addSuccessor(NewDest);
 201   ++NumTailMerge;
 202 }
 203
 204 bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
 205   MadeChange = false;
 206
 207   if (!EnableTailMerge)
 208     return false;
 209
 210   // Find blocks with no successors.
 211   std::vector<std::pair<unsigned,MachineBasicBlock*> > MergePotentials;
 212   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
 213     if (I->succ_empty())
 214       MergePotentials.push_back(std::make_pair(HashEndOfMBB(I), I));
 215   }
 216
 217   // Sort by hash value so that blocks with identical end sequences sort
 218   // together.
 219   std::stable_sort(MergePotentials.begin(), MergePotentials.end());
 220
 221   // Walk through equivalence sets looking for actual exact matches.
 222   while (MergePotentials.size() > 1) {
 223     unsigned CurHash  = (MergePotentials.end()-1)->first;
 224     unsigned PrevHash = (MergePotentials.end()-2)->first;
 225     MachineBasicBlock *CurMBB = (MergePotentials.end()-1)->second;
 226
 227     // If there is nothing that matches the hash of the current basic block,
 228     // give up.
 229     if (CurHash != PrevHash) {
 230       MergePotentials.pop_back();
 231       continue;
 232     }
 233
 234     // Determine the actual length of the shared tail between these two basic
 235     // blocks.  Because the hash can have collisions, it's possible that this is
 236     // less than 2.
 237     MachineBasicBlock::iterator BBI1, BBI2;
 238     unsigned CommonTailLen =
 239       ComputeCommonTailLength(CurMBB, (MergePotentials.end()-2)->second,
 240                               BBI1, BBI2);
 241
 242     // If the tails don't have at least two instructions in common, see if there
 243     // is anything else in the equivalence class that does match.
 244     if (CommonTailLen < 2) {
 245       unsigned FoundMatch = ~0U;
 246       for (int i = MergePotentials.size()-2;
 247            i != -1 && MergePotentials[i].first == CurHash; --i) {
 248         CommonTailLen = ComputeCommonTailLength(CurMBB,
 249                                                 MergePotentials[i].second,
 250                                                 BBI1, BBI2);
 251         if (CommonTailLen >= 2) {
 252           FoundMatch = i;
 253           break;
 254         }
 255       }
 256
 257       // If we didn't find anything that has at least two instructions matching
 258       // this one, bail out.
 259       if (FoundMatch == ~0U) {
 260         MergePotentials.pop_back();
 261         continue;
 262       }
 263
 264       // Otherwise, move the matching block to the right position.
 265       std::swap(MergePotentials[FoundMatch], *(MergePotentials.end()-2));
 266     }
 267
 268     // If either block is the entire common tail, make the longer one branch to
 269     // the shorter one.
 270     MachineBasicBlock *MBB2 = (MergePotentials.end()-2)->second;
 271     if (CurMBB->begin() == BBI1) {
 272       // Hack the end off MBB2, making it jump to CurMBB instead.
 273       ReplaceTailWithBranchTo(BBI2, CurMBB);
 274       // This modifies MBB2, so remove it from the worklist.
 275       MergePotentials.erase(MergePotentials.end()-2);
 276       MadeChange = true;
 277       continue;
 278     } else if (MBB2->begin() == BBI2) {
 279       // Hack the end off CurMBB, making it jump to MBBI@ instead.
 280       ReplaceTailWithBranchTo(BBI1, MBB2);
 281       // This modifies CurMBB, so remove it from the worklist.
 282       MergePotentials.pop_back();
 283       MadeChange = true;
 284       continue;
 285     }
 286
 287     MergePotentials.pop_back();
 288   }
 289
 290   return MadeChange;
 291 }
 292
 293
 294 //===----------------------------------------------------------------------===//
 295 //  Branch Optimization
 296 //===----------------------------------------------------------------------===//
 297
 298 bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
 299   MadeChange = false;
 300
 301   for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
 302     MachineBasicBlock *MBB = I++;
 303     OptimizeBlock(MBB);
 304
 305     // If it is dead, remove it.
 306     if (MBB->pred_empty()) {
 307       RemoveDeadBlock(MBB);
 308       MadeChange = true;
 309       ++NumDeadBlocks;
 310     }
 311   }
 312   return MadeChange;
 313 }
 314
 315
 316 /// ReplaceUsesOfBlockWith - Given a machine basic block 'BB' that branched to
 317 /// 'Old', change the code and CFG so that it branches to 'New' instead.
 318 static void ReplaceUsesOfBlockWith(MachineBasicBlock *BB,
 319                                    MachineBasicBlock *Old,
 320                                    MachineBasicBlock *New,
 321                                    const TargetInstrInfo *TII) {
 322   assert(Old != New && "Cannot replace self with self!");
 323
 324   MachineBasicBlock::iterator I = BB->end();
 325   while (I != BB->begin()) {
 326     --I;
 327     if (!TII->isTerminatorInstr(I->getOpcode())) break;
 328
 329     // Scan the operands of this machine instruction, replacing any uses of Old
 330     // with New.
 331     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 332       if (I->getOperand(i).isMachineBasicBlock() &&
 333           I->getOperand(i).getMachineBasicBlock() == Old)
 334         I->getOperand(i).setMachineBasicBlock(New);
 335   }
 336
 337   // Update the successor information.
 338   std::vector<MachineBasicBlock*> Succs(BB->succ_begin(), BB->succ_end());
 339   for (int i = Succs.size()-1; i >= 0; --i)
 340     if (Succs[i] == Old) {
 341       BB->removeSuccessor(Old);
 342       BB->addSuccessor(New);
 343     }
 344 }
 345
 346 /// OptimizeBlock - Analyze and optimize control flow related to the specified
 347 /// block.  This is never called on the entry block.
 348 void BranchFolder::OptimizeBlock(MachineFunction::iterator MBB) {
 349   // If this block is empty, make everyone use its fall-through, not the block
 350   // explicitly.
 351   if (MBB->empty()) {
 352     if (MBB->pred_empty()) return;  // dead block?  Leave for cleanup later.
 353
 354     MachineFunction::iterator FallThrough = next(MBB);
 355
 356     if (FallThrough == MBB->getParent()->end()) {
 357       // TODO: Simplify preds to not branch here if possible!
 358     } else {
 359       // Rewrite all predecessors of the old block to go to the fallthrough
 360       // instead.
 361       while (!MBB->pred_empty()) {
 362         MachineBasicBlock *Pred = *(MBB->pred_end()-1);
 363         ReplaceUsesOfBlockWith(Pred, MBB, FallThrough, TII);
 364       }
 365
 366       // If MBB was the target of a jump table, update jump tables to go to the
 367       // fallthrough instead.
 368       MBB->getParent()->getJumpTableInfo()->ReplaceMBBInJumpTables(MBB,
 369                                                                    FallThrough);
 370       MadeChange = true;
 371     }
 372     return;
 373   }
 374
 375   // Check to see if we can simplify the terminator of the block before this
 376   // one.
 377   MachineBasicBlock &PrevBB = *prior(MBB);
 378
 379   MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
 380   std::vector<MachineOperand> PriorCond;
 381   if (!TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond)) {
 382     // If the previous branch is conditional and both conditions go to the same
 383     // destination, remove the branch, replacing it with an unconditional one.
 384     if (PriorTBB && PriorTBB == PriorFBB) {
 385       TII->RemoveBranch(*prior(MBB));
 386       PriorCond.clear();
 387       if (PriorTBB != &*MBB)
 388         TII->InsertBranch(*prior(MBB), PriorTBB, 0, PriorCond);
 389       MadeChange = true;
 390       ++NumBranchOpts;
 391       return OptimizeBlock(MBB);
 392     }
 393
 394     // If the previous branch *only* branches to *this* block (conditional or
 395     // not) remove the branch.
 396     if (PriorTBB == &*MBB && PriorFBB == 0) {
 397       TII->RemoveBranch(*prior(MBB));
 398       MadeChange = true;
 399       ++NumBranchOpts;
 400       return OptimizeBlock(MBB);
 401     }
 402   }
 403
 404 #if 0
 405
 406   if (MBB->pred_size() == 1) {
 407     // If this block has a single predecessor, and if that block has a single
 408     // successor, merge this block into that block.
 409     MachineBasicBlock *Pred = *MBB->pred_begin();
 410     if (Pred->succ_size() == 1) {
 411       // Delete all of the terminators from end of the pred block.  NOTE, this
 412       // assumes that terminators do not have side effects!
 413       // FIXME: This doesn't work for FP_REG_KILL.
 414
 415       while (!Pred->empty() && TII.isTerminatorInstr(Pred->back().getOpcode()))
 416         Pred->pop_back();
 417
 418       // Splice the instructions over.
 419       Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end());
 420
 421       // If MBB does not end with a barrier, add a goto instruction to the end.
 422       if (Pred->empty() || !TII.isBarrier(Pred->back().getOpcode()))
 423         TII.insertGoto(*Pred, *next(MBB));
 424
 425       // Update the CFG now.
 426       Pred->removeSuccessor(Pred->succ_begin());
 427       while (!MBB->succ_empty()) {
 428         Pred->addSuccessor(*(MBB->succ_end()-1));
 429         MBB->removeSuccessor(MBB->succ_end()-1);
 430       }
 431       return true;
 432     }
 433   }
 434
 435   // If BB falls through into Old, insert an unconditional branch to New.
 436   MachineFunction::iterator BBSucc = BB; ++BBSucc;
 437   if (BBSucc != BB->getParent()->end() && &*BBSucc == Old)
 438     TII.insertGoto(*BB, *New);
 439
 440
 441   if (MBB->pred_size() == 1) {
 442     // If this block has a single predecessor, and if that block has a single
 443     // successor, merge this block into that block.
 444     MachineBasicBlock *Pred = *MBB->pred_begin();
 445     if (Pred->succ_size() == 1) {
 446       // Delete all of the terminators from end of the pred block.  NOTE, this
 447       // assumes that terminators do not have side effects!
 448       // FIXME: This doesn't work for FP_REG_KILL.
 449
 450       while (!Pred->empty() && TII.isTerminatorInstr(Pred->back().getOpcode()))
 451         Pred->pop_back();
 452
 453       // Splice the instructions over.
 454       Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end());
 455
 456       // If MBB does not end with a barrier, add a goto instruction to the end.
 457       if (Pred->empty() || !TII.isBarrier(Pred->back().getOpcode()))
 458         TII.insertGoto(*Pred, *next(MBB));
 459
 460       // Update the CFG now.
 461       Pred->removeSuccessor(Pred->succ_begin());
 462       while (!MBB->succ_empty()) {
 463         Pred->addSuccessor(*(MBB->succ_end()-1));
 464         MBB->removeSuccessor(MBB->succ_end()-1);
 465       }
 466       return true;
 467     }
 468   }
 469
 470   // If the first instruction in this block is an unconditional branch, and if
 471   // there are predecessors, fold the branch into the predecessors.
 472   if (!MBB->pred_empty() && isUncondBranch(MBB->begin(), TII)) {
 473     MachineInstr *Br = MBB->begin();
 474     assert(Br->getNumOperands() == 1 && Br->getOperand(0).isMachineBasicBlock()
 475            && "Uncond branch should take one MBB argument!");
 476     MachineBasicBlock *Dest = Br->getOperand(0).getMachineBasicBlock();
 477
 478     while (!MBB->pred_empty()) {
 479       MachineBasicBlock *Pred = *(MBB->pred_end()-1);
 480       ReplaceUsesOfBlockWith(Pred, MBB, Dest, TII);
 481     }
 482     return true;
 483   }
 484
 485   // If the last instruction is an unconditional branch and the fall through
 486   // block is the destination, just delete the branch.
 487   if (isUncondBranch(--MBB->end(), TII)) {
 488     MachineBasicBlock::iterator MI = --MBB->end();
 489     MachineInstr *UncondBr = MI;
 490     MachineFunction::iterator FallThrough = next(MBB);
 491
 492     MachineFunction::iterator UncondDest =
 493       MI->getOperand(0).getMachineBasicBlock();
 494     if (UncondDest == FallThrough) {
 495       // Just delete the branch.  This does not effect the CFG.
 496       MBB->erase(UncondBr);
 497       return true;
 498     }
 499
 500     // Okay, so we don't have a fall-through.  Check to see if we have an
 501     // conditional branch that would be a fall through if we reversed it.  If
 502     // so, invert the condition and delete the uncond branch.
 503     if (MI != MBB->begin() && isCondBranch(--MI, TII)) {
 504       // We assume that conditional branches always have the branch dest as the
 505       // last operand.  This could be generalized in the future if needed.
 506       unsigned LastOpnd = MI->getNumOperands()-1;
 507       if (MachineFunction::iterator(
 508             MI->getOperand(LastOpnd).getMachineBasicBlock()) == FallThrough) {
 509         // Change the cond branch to go to the uncond dest, nuke the uncond,
 510         // then reverse the condition.
 511         MI->getOperand(LastOpnd).setMachineBasicBlock(UncondDest);
 512         MBB->erase(UncondBr);
 513         TII.reverseBranchCondition(MI);
 514         return true;
 515       }
 516     }
 517   }
 518 #endif
 519 }