BranchFolding.cpp revision 2d47bd937c13556ace07b2b2daf4dfe75f4e1e90 
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"
28using namespace llvm;
29
30static Statistic<> NumDeadBlocks("branchfold", "Number of dead blocks removed");
31static Statistic<> NumBranchOpts("branchfold", "Number of branches optimized");
32static Statistic<> NumTailMerge ("branchfold", "Number of block tails merged");
33static cl::opt<bool> EnableTailMerge("enable-tail-merge", cl::init(false));
34
35namespace {
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
55FunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); }
56
57/// RemoveDeadBlock - Remove the specified dead machine basic block from the
58/// function, updating the CFG.
59void 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
87bool 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.
110static 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).
147static 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.
167static 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.
189void 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
207bool 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
301bool 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.
323static 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.
373static 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.
403void 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}
531