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", cl::init(false));
  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.  This
 188 /// returns true if OldInst's block is modified, false if NewDest is modified.
 189 void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
 190                                            MachineBasicBlock *NewDest) {
 191   MachineBasicBlock *OldBB = OldInst->getParent();
 192
 193   // Remove all the old successors of OldBB from the CFG.
 194   while (!OldBB->succ_empty())
 195     OldBB->removeSuccessor(OldBB->succ_begin());
 196
 197   // Remove all the dead instructions from the end of OldBB.
 198   OldBB->erase(OldInst, OldBB->end());
 199
 200   // If OldBB isn't immediately before OldBB, insert a branch to it.
 201   if (++MachineFunction::iterator(OldBB) != MachineFunction::iterator(NewDest))
 202     TII->InsertBranch(*OldBB, NewDest, 0, std::vector<MachineOperand>());
 203   OldBB->addSuccessor(NewDest);
 204   ++NumTailMerge;
 205 }
 206
 207 bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
 208   MadeChange = false;
 209
 210   if (!EnableTailMerge)
 211     return false;
 212
 213   // Find blocks with no successors.
 214   std::vector<std::pair<unsigned,MachineBasicBlock*> > MergePotentials;
 215   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
 216     if (I->succ_empty())
 217       MergePotentials.push_back(std::make_pair(HashEndOfMBB(I), I));
 218   }
 219
 220   // Sort by hash value so that blocks with identical end sequences sort
 221   // together.
 222   std::stable_sort(MergePotentials.begin(), MergePotentials.end());
 223
 224   // Walk through equivalence sets looking for actual exact matches.
 225   while (MergePotentials.size() > 1) {
 226     unsigned CurHash  = (MergePotentials.end()-1)->first;
 227     unsigned PrevHash = (MergePotentials.end()-2)->first;
 228     MachineBasicBlock *CurMBB = (MergePotentials.end()-1)->second;
 229
 230     // If there is nothing that matches the hash of the current basic block,
 231     // give up.
 232     if (CurHash != PrevHash) {
 233       MergePotentials.pop_back();
 234       continue;
 235     }
 236
 237     // Determine the actual length of the shared tail between these two basic
 238     // blocks.  Because the hash can have collisions, it's possible that this is
 239     // less than 2.
 240     MachineBasicBlock::iterator BBI1, BBI2;
 241     unsigned CommonTailLen =
 242       ComputeCommonTailLength(CurMBB, (MergePotentials.end()-2)->second,
 243                               BBI1, BBI2);
 244
 245     // If the tails don't have at least two instructions in common, see if there
 246     // is anything else in the equivalence class that does match.
 247     if (CommonTailLen < 2) {
 248       unsigned FoundMatch = ~0U;
 249       for (int i = MergePotentials.size()-2;
 250            i != -1 && MergePotentials[i].first == CurHash; --i) {
 251         CommonTailLen = ComputeCommonTailLength(CurMBB,
 252                                                 MergePotentials[i].second,
 253                                                 BBI1, BBI2);
 254         if (CommonTailLen >= 2) {
 255           FoundMatch = i;
 256           break;
 257         }
 258       }
 259
 260       // If we didn't find anything that has at least two instructions matching
 261       // this one, bail out.
 262       if (FoundMatch == ~0U) {
 263         MergePotentials.pop_back();
 264         continue;
 265       }
 266
 267       // Otherwise, move the matching block to the right position.
 268       std::swap(MergePotentials[FoundMatch], *(MergePotentials.end()-2));
 269     }
 270
 271     // If either block is the entire common tail, make the longer one branch to
 272     // the shorter one.
 273     MachineBasicBlock *MBB2 = (MergePotentials.end()-2)->second;
 274     if (CurMBB->begin() == BBI1) {
 275       // Hack the end off MBB2, making it jump to CurMBB instead.
 276       ReplaceTailWithBranchTo(BBI2, CurMBB);
 277       // This modifies MBB2, so remove it from the worklist.
 278       MergePotentials.erase(MergePotentials.end()-2);
 279       MadeChange = true;
 280       continue;
 281     } else if (MBB2->begin() == BBI2) {
 282       // Hack the end off CurMBB, making it jump to MBBI@ instead.
 283       ReplaceTailWithBranchTo(BBI1, MBB2);
 284       // This modifies CurMBB, so remove it from the worklist.
 285       MergePotentials.pop_back();
 286       MadeChange = true;
 287       continue;
 288     }
 289
 290     MergePotentials.pop_back();
 291   }
 292
 293   return MadeChange;
 294 }
 295
 296
 297 //===----------------------------------------------------------------------===//
 298 //  Branch Optimization
 299 //===----------------------------------------------------------------------===//
 300
 301 bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
 302   MadeChange = false;
 303
 304   for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
 305     MachineBasicBlock *MBB = I++;
 306     OptimizeBlock(MBB);
 307
 308     // If it is dead, remove it.
 309     if (MBB->pred_empty()) {
 310       RemoveDeadBlock(MBB);
 311       MadeChange = true;
 312       ++NumDeadBlocks;
 313     }
 314   }
 315   return MadeChange;
 316 }
 317
 318
 319 /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the
 320 /// CFG to be inserted.  If we have proven that MBB can only branch to DestA and
 321 /// DestB, remove any other MBB successors from the CFG.  DestA and DestB can
 322 /// be null.
 323 static bool CorrectExtraCFGEdges(MachineBasicBlock &MBB,
 324                                  MachineBasicBlock *DestA,
 325                                  MachineBasicBlock *DestB,
 326                                  bool isCond,
 327                                  MachineFunction::iterator FallThru) {
 328   bool MadeChange = false;
 329   bool AddedFallThrough = false;
 330
 331   // If this block ends with a conditional branch that falls through to its
 332   // successor, set DestB as the successor.
 333   if (isCond) {
 334     if (DestB == 0 && FallThru != MBB.getParent()->end()) {
 335       DestB = FallThru;
 336       AddedFallThrough = true;
 337     }
 338   } else {
 339     // If this is an unconditional branch with no explicit dest, it must just be
 340     // a fallthrough into DestB.
 341     if (DestA == 0 && FallThru != MBB.getParent()->end()) {
 342       DestA = FallThru;
 343       AddedFallThrough = true;
 344     }
 345   }
 346
 347   MachineBasicBlock::pred_iterator SI = MBB.succ_begin();
 348   while (SI != MBB.succ_end()) {
 349     if (*SI == DestA) {
 350       DestA = 0;
 351       ++SI;
 352     } else if (*SI == DestB) {
 353       DestB = 0;
 354       ++SI;
 355     } else {
 356       // Otherwise, this is a superfluous edge, remove it.
 357       MBB.removeSuccessor(SI);
 358       MadeChange = true;
 359     }
 360   }
 361   if (!AddedFallThrough) {
 362     assert(DestA == 0 && DestB == 0 &&
 363            "MachineCFG is missing edges!");
 364   } else if (isCond) {
 365     assert(DestA == 0 && "MachineCFG is missing edges!");
 366   }
 367   return MadeChange;
 368 }
 369
 370
 371 /// ReplaceUsesOfBlockWith - Given a machine basic block 'BB' that branched to
 372 /// 'Old', change the code and CFG so that it branches to 'New' instead.
 373 static void ReplaceUsesOfBlockWith(MachineBasicBlock *BB,
 374                                    MachineBasicBlock *Old,
 375                                    MachineBasicBlock *New,
 376                                    const TargetInstrInfo *TII) {
 377   assert(Old != New && "Cannot replace self with self!");
 378
 379   MachineBasicBlock::iterator I = BB->end();
 380   while (I != BB->begin()) {
 381     --I;
 382     if (!TII->isTerminatorInstr(I->getOpcode())) break;
 383
 384     // Scan the operands of this machine instruction, replacing any uses of Old
 385     // with New.
 386     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 387       if (I->getOperand(i).isMachineBasicBlock() &&
 388           I->getOperand(i).getMachineBasicBlock() == Old)
 389         I->getOperand(i).setMachineBasicBlock(New);
 390   }
 391
 392   // Update the successor information.
 393   std::vector<MachineBasicBlock*> Succs(BB->succ_begin(), BB->succ_end());
 394   for (int i = Succs.size()-1; i >= 0; --i)
 395     if (Succs[i] == Old) {
 396       BB->removeSuccessor(Old);
 397       BB->addSuccessor(New);
 398     }
 399 }
 400
 401 /// OptimizeBlock - Analyze and optimize control flow related to the specified
 402 /// block.  This is never called on the entry block.
 403 void BranchFolder::OptimizeBlock(MachineFunction::iterator MBB) {
 404   // If this block is empty, make everyone use its fall-through, not the block
 405   // explicitly.
 406   if (MBB->empty()) {
 407     // Dead block?  Leave for cleanup later.
 408     if (MBB->pred_empty()) return;
 409
 410     MachineFunction::iterator FallThrough = next(MBB);
 411
 412     if (FallThrough == MBB->getParent()->end()) {
 413       // TODO: Simplify preds to not branch here if possible!
 414     } else {
 415       // Rewrite all predecessors of the old block to go to the fallthrough
 416       // instead.
 417       while (!MBB->pred_empty()) {
 418         MachineBasicBlock *Pred = *(MBB->pred_end()-1);
 419         ReplaceUsesOfBlockWith(Pred, MBB, FallThrough, TII);
 420       }
 421
 422       // If MBB was the target of a jump table, update jump tables to go to the
 423       // fallthrough instead.
 424       MBB->getParent()->getJumpTableInfo()->ReplaceMBBInJumpTables(MBB,
 425                                                                    FallThrough);
 426       MadeChange = true;
 427     }
 428     return;
 429   }
 430
 431   // Check to see if we can simplify the terminator of the block before this
 432   // one.
 433   MachineBasicBlock &PrevBB = *prior(MBB);
 434
 435   MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
 436   std::vector<MachineOperand> PriorCond;
 437   bool PriorUnAnalyzable = false;
 438   PriorUnAnalyzable = TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond);
 439   if (!PriorUnAnalyzable) {
 440     // If the CFG for the prior block has extra edges, remove them.
 441     MadeChange |= CorrectExtraCFGEdges(PrevBB, PriorTBB, PriorFBB,
 442                                        !PriorCond.empty(), MBB);
 443
 444     // If the previous branch is conditional and both conditions go to the same
 445     // destination, remove the branch, replacing it with an unconditional one or
 446     // a fall-through.
 447     if (PriorTBB && PriorTBB == PriorFBB) {
 448       TII->RemoveBranch(PrevBB);
 449       PriorCond.clear();
 450       if (PriorTBB != &*MBB)
 451         TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond);
 452       MadeChange = true;
 453       ++NumBranchOpts;
 454       return OptimizeBlock(MBB);
 455     }
 456
 457     // If the previous branch *only* branches to *this* block (conditional or
 458     // not) remove the branch.
 459     if (PriorTBB == &*MBB && PriorFBB == 0) {
 460       TII->RemoveBranch(PrevBB);
 461       MadeChange = true;
 462       ++NumBranchOpts;
 463       return OptimizeBlock(MBB);
 464     }
 465
 466     // If the prior block branches somewhere else on the condition and here if
 467     // the condition is false, remove the uncond second branch.
 468     if (PriorFBB == &*MBB) {
 469       TII->RemoveBranch(PrevBB);
 470       TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond);
 471       MadeChange = true;
 472       ++NumBranchOpts;
 473       return OptimizeBlock(MBB);
 474     }
 475   }
 476
 477   // Analyze the branch in the current block.
 478   MachineBasicBlock *CurTBB = 0, *CurFBB = 0;
 479   std::vector<MachineOperand> CurCond;
 480   if (!TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond)) {
 481     // If the CFG for the prior block has extra edges, remove them.
 482     MadeChange |= CorrectExtraCFGEdges(*MBB, CurTBB, CurFBB,
 483                                        !CurCond.empty(), next(MBB));
 484
 485     // If this branch is the only thing in its block, see if we can forward
 486     // other blocks across it.
 487     if (CurTBB && CurCond.empty() && CurFBB == 0 &&
 488         TII->isBranch(MBB->begin()->getOpcode())) {
 489       // This block may contain just an unconditional branch.  Because there can
 490       // be 'non-branch terminators' in the block, try removing the branch and
 491       // then seeing if the block is empty.
 492       TII->RemoveBranch(*MBB);
 493
 494       // If this block is just an unconditional branch to CurTBB, we can
 495       // usually completely eliminate the block.  The only case we cannot
 496       // completely eliminate the block is when the block before this one
 497       // falls through into MBB and we can't understand the prior block's branch
 498       // condition.
 499       if (MBB->empty() && (!PriorUnAnalyzable || !PrevBB.isSuccessor(MBB))) {
 500         // If the prior block falls through into us, turn it into an
 501         // explicit branch to us to make updates simpler.
 502         if (PrevBB.isSuccessor(MBB) && PriorTBB != &*MBB && PriorFBB != &*MBB) {
 503           if (PriorTBB == 0) {
 504             assert(PriorCond.empty() && PriorFBB == 0 && "Bad branch analysis");
 505             PriorTBB = MBB;
 506           } else {
 507             assert(PriorFBB == 0 && "Machine CFG out of date!");
 508             PriorFBB = MBB;
 509           }
 510           TII->RemoveBranch(PrevBB);
 511           TII->InsertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond);
 512         }
 513
 514         // Iterate through all the predecessors, revectoring each in-turn.
 515         while (!MBB->pred_empty())
 516           ReplaceUsesOfBlockWith(*(MBB->pred_end()-1), MBB, CurTBB, TII);
 517
 518         // Change any jumptables to go to the new MBB.
 519         MBB->getParent()->getJumpTableInfo()->ReplaceMBBInJumpTables(MBB,
 520                                                                      CurTBB);
 521         ++NumBranchOpts;
 522         MadeChange = true;
 523         return;
 524       }
 525
 526       // Add the branch back if the block is more than just an uncond branch.
 527       TII->InsertBranch(*MBB, CurTBB, 0, CurCond);
 528     }
 529   }
 530 }