TailDuplication.cpp revision 810ced7daebe78a8d84b94fac07e320a02cecb71
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 /// TailDuplicationPass - Perform tail duplication. 41 class TailDuplicationPass : public MachineFunctionPass { 42 const TargetInstrInfo *TII; 43 MachineModuleInfo *MMI; 44 45 public: 46 static char ID; 47 explicit TailDuplicationPass() : 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 TailDuplicationPass::ID = 0; 59} 60 61FunctionPass *llvm::createTailDuplicationPass() { 62 return new TailDuplicationPass(); 63} 64 65bool TailDuplicationPass::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 TailDuplicationPass::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 TailDuplicationPass::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 (MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 120 MaxDuplicateCount = 1; 121 else if (TII->isProfitableToDuplicateIndirectBranch() && 122 !TailBB->empty() && TailBB->back().getDesc().isIndirectBranch()) 123 // If the target has hardware branch prediction that can handle indirect 124 // branches, duplicating them can often make them predictable when there 125 // are common paths through the code. The limit needs to be high enough 126 // to allow undoing the effects of tail merging. 127 MaxDuplicateCount = 20; 128 else 129 MaxDuplicateCount = TailDuplicateSize; 130 131 // Check the instructions in the block to determine whether tail-duplication 132 // is invalid or unlikely to be profitable. 133 unsigned i = 0; 134 bool HasCall = false; 135 for (MachineBasicBlock::iterator I = TailBB->begin(); 136 I != TailBB->end(); ++I, ++i) { 137 // Non-duplicable things shouldn't be tail-duplicated. 138 if (I->getDesc().isNotDuplicable()) return false; 139 // Don't duplicate more than the threshold. 140 if (i == MaxDuplicateCount) return false; 141 // Remember if we saw a call. 142 if (I->getDesc().isCall()) HasCall = true; 143 } 144 // Heuristically, don't tail-duplicate calls if it would expand code size, 145 // as it's less likely to be worth the extra cost. 146 if (i > 1 && HasCall) 147 return false; 148 149 // Iterate through all the unique predecessors and tail-duplicate this 150 // block into them, if possible. Copying the list ahead of time also 151 // avoids trouble with the predecessor list reallocating. 152 bool Changed = false; 153 SmallSetVector<MachineBasicBlock *, 8> Preds(TailBB->pred_begin(), 154 TailBB->pred_end()); 155 for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 156 PE = Preds.end(); PI != PE; ++PI) { 157 MachineBasicBlock *PredBB = *PI; 158 159 assert(TailBB != PredBB && 160 "Single-block loop should have been rejected earlier!"); 161 if (PredBB->succ_size() > 1) continue; 162 163 MachineBasicBlock *PredTBB, *PredFBB; 164 SmallVector<MachineOperand, 4> PredCond; 165 if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 166 continue; 167 if (!PredCond.empty()) 168 continue; 169 // EH edges are ignored by AnalyzeBranch. 170 if (PredBB->succ_size() != 1) 171 continue; 172 // Don't duplicate into a fall-through predecessor (at least for now). 173 if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 174 continue; 175 176 DEBUG(errs() << "\nTail-duplicating into PredBB: " << *PredBB 177 << "From Succ: " << *TailBB); 178 179 // Remove PredBB's unconditional branch. 180 TII->RemoveBranch(*PredBB); 181 // Clone the contents of TailBB into PredBB. 182 for (MachineBasicBlock::iterator I = TailBB->begin(), E = TailBB->end(); 183 I != E; ++I) { 184 MachineInstr *NewMI = MF.CloneMachineInstr(I); 185 PredBB->insert(PredBB->end(), NewMI); 186 } 187 NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 188 189 // Update the CFG. 190 PredBB->removeSuccessor(PredBB->succ_begin()); 191 assert(PredBB->succ_empty() && 192 "TailDuplicate called on block with multiple successors!"); 193 for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 194 E = TailBB->succ_end(); I != E; ++I) 195 PredBB->addSuccessor(*I); 196 197 Changed = true; 198 ++NumTailDups; 199 } 200 201 // If TailBB was duplicated into all its predecessors except for the prior 202 // block, which falls through unconditionally, move the contents of this 203 // block into the prior block. 204 MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(TailBB)); 205 MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 206 SmallVector<MachineOperand, 4> PriorCond; 207 bool PriorUnAnalyzable = 208 TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true); 209 // This has to check PrevBB->succ_size() because EH edges are ignored by 210 // AnalyzeBranch. 211 if (!PriorUnAnalyzable && PriorCond.empty() && !PriorTBB && 212 TailBB->pred_size() == 1 && PrevBB.succ_size() == 1 && 213 !TailBB->hasAddressTaken()) { 214 DEBUG(errs() << "\nMerging into block: " << PrevBB 215 << "From MBB: " << *TailBB); 216 PrevBB.splice(PrevBB.end(), TailBB, TailBB->begin(), TailBB->end()); 217 PrevBB.removeSuccessor(PrevBB.succ_begin());; 218 assert(PrevBB.succ_empty()); 219 PrevBB.transferSuccessors(TailBB); 220 Changed = true; 221 } 222 223 return Changed; 224} 225 226/// RemoveDeadBlock - Remove the specified dead machine basic block from the 227/// function, updating the CFG. 228void TailDuplicationPass::RemoveDeadBlock(MachineBasicBlock *MBB) { 229 assert(MBB->pred_empty() && "MBB must be dead!"); 230 DEBUG(errs() << "\nRemoving MBB: " << *MBB); 231 232 // Remove all successors. 233 while (!MBB->succ_empty()) 234 MBB->removeSuccessor(MBB->succ_end()-1); 235 236 // If there are any labels in the basic block, unregister them from 237 // MachineModuleInfo. 238 if (MMI && !MBB->empty()) { 239 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 240 I != E; ++I) { 241 if (I->isLabel()) 242 // The label ID # is always operand #0, an immediate. 243 MMI->InvalidateLabel(I->getOperand(0).getImm()); 244 } 245 } 246 247 // Remove the block. 248 MBB->eraseFromParent(); 249} 250 251