TailDuplication.cpp revision 3858225afc2a7f1027dce34dc72de5686b636c2d
1//===-- TailDuplication.cpp - Duplicate blocks into predecessors' tails ---===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass duplicates basic blocks ending in unconditional branches into 11// the tails of their predecessors. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "tailduplication" 16#include "llvm/Function.h" 17#include "llvm/CodeGen/Passes.h" 18#include "llvm/CodeGen/MachineModuleInfo.h" 19#include "llvm/CodeGen/MachineFunctionPass.h" 20#include "llvm/Target/TargetInstrInfo.h" 21#include "llvm/Support/CommandLine.h" 22#include "llvm/Support/Debug.h" 23#include "llvm/Support/raw_ostream.h" 24#include "llvm/ADT/SmallSet.h" 25#include "llvm/ADT/SetVector.h" 26#include "llvm/ADT/Statistic.h" 27using namespace llvm; 28 29STATISTIC(NumTailDups , "Number of tail duplicated blocks"); 30STATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); 31STATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 32 33// Heuristic for tail duplication. 34static cl::opt<unsigned> 35TailDuplicateSize("tail-dup-size", 36 cl::desc("Maximum instructions to consider tail duplicating"), 37 cl::init(2), cl::Hidden); 38 39namespace { 40 /// TailDuplicatePass - Perform tail duplication. 41 class TailDuplicatePass : public MachineFunctionPass { 42 const TargetInstrInfo *TII; 43 MachineModuleInfo *MMI; 44 45 public: 46 static char ID; 47 explicit TailDuplicatePass() : MachineFunctionPass(&ID) {} 48 49 virtual bool runOnMachineFunction(MachineFunction &MF); 50 virtual const char *getPassName() const { return "Tail Duplication"; } 51 52 private: 53 bool TailDuplicateBlocks(MachineFunction &MF); 54 bool TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF); 55 void RemoveDeadBlock(MachineBasicBlock *MBB); 56 }; 57 58 char TailDuplicatePass::ID = 0; 59} 60 61FunctionPass *llvm::createTailDuplicatePass() { 62 return new TailDuplicatePass(); 63} 64 65bool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { 66 TII = MF.getTarget().getInstrInfo(); 67 MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 68 69 bool MadeChange = false; 70 bool MadeChangeThisIteration = true; 71 while (MadeChangeThisIteration) { 72 MadeChangeThisIteration = false; 73 MadeChangeThisIteration |= TailDuplicateBlocks(MF); 74 MadeChange |= MadeChangeThisIteration; 75 } 76 77 return MadeChange; 78} 79 80/// TailDuplicateBlocks - Look for small blocks that are unconditionally 81/// branched to and do not fall through. Tail-duplicate their instructions 82/// into their predecessors to eliminate (dynamic) branches. 83bool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { 84 bool MadeChange = false; 85 86 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 87 MachineBasicBlock *MBB = I++; 88 89 // Only duplicate blocks that end with unconditional branches. 90 if (MBB->canFallThrough()) 91 continue; 92 93 MadeChange |= TailDuplicate(MBB, MF); 94 95 // If it is dead, remove it. 96 if (MBB->pred_empty()) { 97 NumInstrDups -= MBB->size(); 98 RemoveDeadBlock(MBB); 99 MadeChange = true; 100 ++NumDeadBlocks; 101 } 102 } 103 return MadeChange; 104} 105 106/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 107/// of its predecessors. 108bool TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, 109 MachineFunction &MF) { 110 // Don't try to tail-duplicate single-block loops. 111 if (TailBB->isSuccessor(TailBB)) 112 return false; 113 114 // Set the limit on the number of instructions to duplicate, with a default 115 // of one less than the tail-merge threshold. When optimizing for size, 116 // duplicate only one, because one branch instruction can be eliminated to 117 // compensate for the duplication. 118 unsigned MaxDuplicateCount; 119 if (!TailBB->empty() && TailBB->back().getDesc().isIndirectBranch()) 120 // If the target has hardware branch prediction that can handle indirect 121 // branches, duplicating them can often make them predictable when there 122 // are common paths through the code. The limit needs to be high enough 123 // to allow undoing the effects of tail merging. 124 MaxDuplicateCount = 20; 125 else if (MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 126 MaxDuplicateCount = 1; 127 else 128 MaxDuplicateCount = TailDuplicateSize; 129 130 // Check the instructions in the block to determine whether tail-duplication 131 // is invalid or unlikely to be profitable. 132 unsigned i = 0; 133 bool HasCall = false; 134 for (MachineBasicBlock::iterator I = TailBB->begin(); 135 I != TailBB->end(); ++I, ++i) { 136 // Non-duplicable things shouldn't be tail-duplicated. 137 if (I->getDesc().isNotDuplicable()) return false; 138 // Don't duplicate more than the threshold. 139 if (i == MaxDuplicateCount) return false; 140 // Remember if we saw a call. 141 if (I->getDesc().isCall()) HasCall = true; 142 } 143 // Heuristically, don't tail-duplicate calls if it would expand code size, 144 // as it's less likely to be worth the extra cost. 145 if (i > 1 && HasCall) 146 return false; 147 148 // Iterate through all the unique predecessors and tail-duplicate this 149 // block into them, if possible. Copying the list ahead of time also 150 // avoids trouble with the predecessor list reallocating. 151 bool Changed = false; 152 SmallSetVector<MachineBasicBlock *, 8> Preds(TailBB->pred_begin(), 153 TailBB->pred_end()); 154 for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 155 PE = Preds.end(); PI != PE; ++PI) { 156 MachineBasicBlock *PredBB = *PI; 157 158 assert(TailBB != PredBB && 159 "Single-block loop should have been rejected earlier!"); 160 if (PredBB->succ_size() > 1) continue; 161 162 MachineBasicBlock *PredTBB, *PredFBB; 163 SmallVector<MachineOperand, 4> PredCond; 164 if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 165 continue; 166 if (!PredCond.empty()) 167 continue; 168 // EH edges are ignored by AnalyzeBranch. 169 if (PredBB->succ_size() != 1) 170 continue; 171 // Don't duplicate into a fall-through predecessor (at least for now). 172 if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 173 continue; 174 175 DEBUG(errs() << "\nTail-duplicating into PredBB: " << *PredBB 176 << "From Succ: " << *TailBB); 177 178 // Remove PredBB's unconditional branch. 179 TII->RemoveBranch(*PredBB); 180 // Clone the contents of TailBB into PredBB. 181 for (MachineBasicBlock::iterator I = TailBB->begin(), E = TailBB->end(); 182 I != E; ++I) { 183 MachineInstr *NewMI = MF.CloneMachineInstr(I); 184 PredBB->insert(PredBB->end(), NewMI); 185 } 186 NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 187 188 // Update the CFG. 189 PredBB->removeSuccessor(PredBB->succ_begin()); 190 assert(PredBB->succ_empty() && 191 "TailDuplicate called on block with multiple successors!"); 192 for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 193 E = TailBB->succ_end(); I != E; ++I) 194 PredBB->addSuccessor(*I); 195 196 Changed = true; 197 ++NumTailDups; 198 } 199 200 // If TailBB was duplicated into all its predecessors except for the prior 201 // block, which falls through unconditionally, move the contents of this 202 // block into the prior block. 203 MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(TailBB)); 204 MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 205 SmallVector<MachineOperand, 4> PriorCond; 206 bool PriorUnAnalyzable = 207 TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true); 208 // This has to check PrevBB->succ_size() because EH edges are ignored by 209 // AnalyzeBranch. 210 if (!PriorUnAnalyzable && PriorCond.empty() && !PriorTBB && 211 TailBB->pred_size() == 1 && PrevBB.succ_size() == 1 && 212 !TailBB->hasAddressTaken()) { 213 DEBUG(errs() << "\nMerging into block: " << PrevBB 214 << "From MBB: " << *TailBB); 215 PrevBB.splice(PrevBB.end(), TailBB, TailBB->begin(), TailBB->end()); 216 PrevBB.removeSuccessor(PrevBB.succ_begin());; 217 assert(PrevBB.succ_empty()); 218 PrevBB.transferSuccessors(TailBB); 219 Changed = true; 220 } 221 222 return Changed; 223} 224 225/// RemoveDeadBlock - Remove the specified dead machine basic block from the 226/// function, updating the CFG. 227void TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 228 assert(MBB->pred_empty() && "MBB must be dead!"); 229 DEBUG(errs() << "\nRemoving MBB: " << *MBB); 230 231 // Remove all successors. 232 while (!MBB->succ_empty()) 233 MBB->removeSuccessor(MBB->succ_end()-1); 234 235 // If there are any labels in the basic block, unregister them from 236 // MachineModuleInfo. 237 if (MMI && !MBB->empty()) { 238 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 239 I != E; ++I) { 240 if (I->isLabel()) 241 // The label ID # is always operand #0, an immediate. 242 MMI->InvalidateLabel(I->getOperand(0).getImm()); 243 } 244 } 245 246 // Remove the block. 247 MBB->eraseFromParent(); 248} 249 250