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