TailDuplication.cpp revision 199989
168673Sobrien//===-- TailDuplication.cpp - Duplicate blocks into predecessors' tails ---===// 2218822Sdim// 368673Sobrien// The LLVM Compiler Infrastructure 4130561Sobrien// 568673Sobrien// This file is distributed under the University of Illinois Open Source 6130561Sobrien// License. See LICENSE.TXT for details. 7130561Sobrien// 8130561Sobrien//===----------------------------------------------------------------------===// 9130561Sobrien// 1068673Sobrien// This pass duplicates basic blocks ending in unconditional branches into 11130561Sobrien// the tails of their predecessors. 12130561Sobrien// 13130561Sobrien//===----------------------------------------------------------------------===// 14130561Sobrien 1568673Sobrien#define DEBUG_TYPE "tailduplication" 16130561Sobrien#include "llvm/Function.h" 17130561Sobrien#include "llvm/CodeGen/Passes.h" 18218822Sdim#include "llvm/CodeGen/MachineModuleInfo.h" 1968673Sobrien#include "llvm/CodeGen/MachineFunctionPass.h" 2068673Sobrien#include "llvm/Target/TargetInstrInfo.h" 2168673Sobrien#include "llvm/Support/CommandLine.h" 2268673Sobrien#include "llvm/Support/Debug.h" 2368673Sobrien#include "llvm/Support/raw_ostream.h" 2468673Sobrien#include "llvm/ADT/SmallSet.h" 2568673Sobrien#include "llvm/ADT/SetVector.h" 2668673Sobrien#include "llvm/ADT/Statistic.h" 2768673Sobrienusing namespace llvm; 28130561Sobrien 29130561SobrienSTATISTIC(NumTailDups , "Number of tail duplicated blocks"); 30130561SobrienSTATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); 31130561SobrienSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 32130561Sobrien 33130561Sobrien// Heuristic for tail duplication. 34130561Sobrienstatic cl::opt<unsigned> 35130561SobrienTailDuplicateSize("tail-dup-size", 36130561Sobrien cl::desc("Maximum instructions to consider tail duplicating"), 37130561Sobrien cl::init(2), cl::Hidden); 38130561Sobrien 39130561Sobriennamespace { 40130561Sobrien /// TailDuplicatePass - Perform tail duplication. 41130561Sobrien class TailDuplicatePass : public MachineFunctionPass { 42130561Sobrien const TargetInstrInfo *TII; 43130561Sobrien MachineModuleInfo *MMI; 44130561Sobrien 45130561Sobrien public: 46130561Sobrien static char ID; 47130561Sobrien explicit TailDuplicatePass() : MachineFunctionPass(&ID) {} 48130561Sobrien 49130561Sobrien virtual bool runOnMachineFunction(MachineFunction &MF); 50130561Sobrien virtual const char *getPassName() const { return "Tail Duplication"; } 51130561Sobrien 52130561Sobrien private: 53130561Sobrien bool TailDuplicateBlocks(MachineFunction &MF); 54130561Sobrien bool TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF); 55218822Sdim void RemoveDeadBlock(MachineBasicBlock *MBB); 56218822Sdim }; 57130561Sobrien 58130561Sobrien char TailDuplicatePass::ID = 0; 59130561Sobrien} 60130561Sobrien 61130561SobrienFunctionPass *llvm::createTailDuplicatePass() { 62130561Sobrien return new TailDuplicatePass(); 63130561Sobrien} 64130561Sobrien 65130561Sobrienbool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { 66130561Sobrien TII = MF.getTarget().getInstrInfo(); 67130561Sobrien MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 68130561Sobrien 69130561Sobrien bool MadeChange = false; 70130561Sobrien bool MadeChangeThisIteration = true; 71130561Sobrien while (MadeChangeThisIteration) { 72218822Sdim MadeChangeThisIteration = false; 73218822Sdim MadeChangeThisIteration |= TailDuplicateBlocks(MF); 74218822Sdim MadeChange |= MadeChangeThisIteration; 75218822Sdim } 7677298Sobrien 7768673Sobrien return MadeChange; 7868673Sobrien} 7968673Sobrien 8068673Sobrien/// TailDuplicateBlocks - Look for small blocks that are unconditionally 8168673Sobrien/// branched to and do not fall through. Tail-duplicate their instructions 8268673Sobrien/// into their predecessors to eliminate (dynamic) branches. 8368673Sobrienbool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { 8468673Sobrien bool MadeChange = false; 8568673Sobrien 8668673Sobrien for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 8768673Sobrien MachineBasicBlock *MBB = I++; 8868673Sobrien 8968673Sobrien // Only duplicate blocks that end with unconditional branches. 9068673Sobrien if (MBB->canFallThrough()) 9168673Sobrien continue; 9268673Sobrien 9368673Sobrien MadeChange |= TailDuplicate(MBB, MF); 9468673Sobrien 9568673Sobrien // If it is dead, remove it. 9668673Sobrien if (MBB->pred_empty()) { 9768673Sobrien NumInstrDups -= MBB->size(); 9868673Sobrien RemoveDeadBlock(MBB); 9968673Sobrien MadeChange = true; 10068673Sobrien ++NumDeadBlocks; 101130561Sobrien } 102130561Sobrien } 103130561Sobrien return MadeChange; 10468673Sobrien} 105130561Sobrien 106130561Sobrien/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 107130561Sobrien/// of its predecessors. 108130561Sobrienbool TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, 109130561Sobrien MachineFunction &MF) { 110130561Sobrien // Don't try to tail-duplicate single-block loops. 111130561Sobrien if (TailBB->isSuccessor(TailBB)) 112130561Sobrien return false; 113130561Sobrien 114130561Sobrien // Set the limit on the number of instructions to duplicate, with a default 115130561Sobrien // of one less than the tail-merge threshold. When optimizing for size, 116130561Sobrien // duplicate only one, because one branch instruction can be eliminated to 117130561Sobrien // compensate for the duplication. 118130561Sobrien unsigned MaxDuplicateCount; 119130561Sobrien if (!TailBB->empty() && TailBB->back().getDesc().isIndirectBranch()) 120130561Sobrien // If the target has hardware branch prediction that can handle indirect 121130561Sobrien // branches, duplicating them can often make them predictable when there 12268673Sobrien // 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