LICM.cpp revision 065a616adad624152618b1b0084ff074e5b03bbb
1//===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===// 2// 3// This pass is a simple loop invariant code motion pass. An interesting aspect 4// of this pass is that it uses alias analysis for two purposes: 5// 6// 1. Moving loop invariant loads out of loops. If we can determine that a 7// load inside of a loop never aliases anything stored to, we can hoist it 8// like any other instruction. 9// 2. Scalar Promotion of Memory - If there is a store instruction inside of 10// the loop, we try to move the store to happen AFTER the loop instead of 11// inside of the loop. This can only happen if a few conditions are true: 12// A. The pointer stored through is loop invariant 13// B. There are no stores or loads in the loop which _may_ alias the 14// pointer. There are no calls in the loop which mod/ref the pointer. 15// If these conditions are true, we can promote the loads and stores in the 16// loop of the pointer to use a temporary alloca'd variable. We then use 17// the mem2reg functionality to construct the appropriate SSA form for the 18// variable. 19// 20//===----------------------------------------------------------------------===// 21 22#include "llvm/Transforms/Scalar.h" 23#include "llvm/Transforms/Utils/PromoteMemToReg.h" 24#include "llvm/Transforms/Utils/Local.h" 25#include "llvm/Analysis/LoopInfo.h" 26#include "llvm/Analysis/AliasAnalysis.h" 27#include "llvm/Analysis/AliasSetTracker.h" 28#include "llvm/Analysis/Dominators.h" 29#include "llvm/Instructions.h" 30#include "llvm/DerivedTypes.h" 31#include "llvm/Target/TargetData.h" 32#include "llvm/Support/InstVisitor.h" 33#include "llvm/Support/CFG.h" 34#include "Support/CommandLine.h" 35#include "Support/Debug.h" 36#include "Support/Statistic.h" 37#include "llvm/Assembly/Writer.h" 38#include <algorithm> 39 40namespace { 41 cl::opt<bool> DisablePromotion("disable-licm-promotion", cl::Hidden, 42 cl::desc("Disable memory promotion in LICM pass")); 43 44 Statistic<> NumHoisted("licm", "Number of instructions hoisted out of loop"); 45 Statistic<> NumHoistedLoads("licm", "Number of load insts hoisted"); 46 Statistic<> NumPromoted("licm", "Number of memory locations promoted to registers"); 47 48 struct LICM : public FunctionPass, public InstVisitor<LICM> { 49 virtual bool runOnFunction(Function &F); 50 51 /// This transformation requires natural loop information & requires that 52 /// loop preheaders be inserted into the CFG... 53 /// 54 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 55 AU.setPreservesCFG(); 56 AU.addRequiredID(LoopPreheadersID); 57 AU.addRequired<LoopInfo>(); 58 AU.addRequired<DominatorTree>(); 59 AU.addRequired<DominanceFrontier>(); // For scalar promotion (mem2reg) 60 AU.addRequired<AliasAnalysis>(); 61 } 62 63 private: 64 LoopInfo *LI; // Current LoopInfo 65 AliasAnalysis *AA; // Current AliasAnalysis information 66 bool Changed; // Set to true when we change anything. 67 BasicBlock *Preheader; // The preheader block of the current loop... 68 Loop *CurLoop; // The current loop we are working on... 69 AliasSetTracker *CurAST; // AliasSet information for the current loop... 70 DominatorTree *DT; // Dominator Tree for the current Loop... 71 72 /// visitLoop - Hoist expressions out of the specified loop... 73 /// 74 void visitLoop(Loop *L, AliasSetTracker &AST); 75 76 /// HoistRegion - Walk the specified region of the CFG (defined by all 77 /// blocks dominated by the specified block, and that are in the current 78 /// loop) in depth first order w.r.t the DominatorTree. This allows us to 79 /// visit defintions before uses, allowing us to hoist a loop body in one 80 /// pass without iteration. 81 /// 82 void HoistRegion(DominatorTree::Node *N); 83 84 /// inSubLoop - Little predicate that returns true if the specified basic 85 /// block is in a subloop of the current one, not the current one itself. 86 /// 87 bool inSubLoop(BasicBlock *BB) { 88 assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); 89 for (unsigned i = 0, e = CurLoop->getSubLoops().size(); i != e; ++i) 90 if (CurLoop->getSubLoops()[i]->contains(BB)) 91 return true; // A subloop actually contains this block! 92 return false; 93 } 94 95 /// hoist - When an instruction is found to only use loop invariant operands 96 /// that is safe to hoist, this instruction is called to do the dirty work. 97 /// 98 void hoist(Instruction &I); 99 100 /// SafeToHoist - Only hoist an instruction if it is not a trapping instruction 101 /// or if it is a trapping instruction and is guaranteed to execute 102 /// 103 bool SafeToHoist(Instruction &I); 104 105 /// pointerInvalidatedByLoop - Return true if the body of this loop may 106 /// store into the memory location pointed to by V. 107 /// 108 bool pointerInvalidatedByLoop(Value *V) { 109 // Check to see if any of the basic blocks in CurLoop invalidate *V. 110 return CurAST->getAliasSetForPointer(V, 0).isMod(); 111 } 112 113 /// isLoopInvariant - Return true if the specified value is loop invariant 114 /// 115 inline bool isLoopInvariant(Value *V) { 116 if (Instruction *I = dyn_cast<Instruction>(V)) 117 return !CurLoop->contains(I->getParent()); 118 return true; // All non-instructions are loop invariant 119 } 120 121 /// PromoteValuesInLoop - Look at the stores in the loop and promote as many 122 /// to scalars as we can. 123 /// 124 void PromoteValuesInLoop(); 125 126 /// findPromotableValuesInLoop - Check the current loop for stores to 127 /// definate pointers, which are not loaded and stored through may aliases. 128 /// If these are found, create an alloca for the value, add it to the 129 /// PromotedValues list, and keep track of the mapping from value to 130 /// alloca... 131 /// 132 void findPromotableValuesInLoop( 133 std::vector<std::pair<AllocaInst*, Value*> > &PromotedValues, 134 std::map<Value*, AllocaInst*> &Val2AlMap); 135 136 137 /// Instruction visitation handlers... these basically control whether or 138 /// not the specified instruction types are hoisted. 139 /// 140 friend class InstVisitor<LICM>; 141 void visitBinaryOperator(Instruction &I) { 142 if (isLoopInvariant(I.getOperand(0)) && isLoopInvariant(I.getOperand(1)) && SafeToHoist(I)) 143 hoist(I); 144 } 145 void visitCastInst(CastInst &CI) { 146 Instruction &I = (Instruction&)CI; 147 if (isLoopInvariant(I.getOperand(0)) && SafeToHoist(CI)) hoist(I); 148 } 149 void visitShiftInst(ShiftInst &I) { visitBinaryOperator((Instruction&)I); } 150 151 void visitLoadInst(LoadInst &LI); 152 153 void visitGetElementPtrInst(GetElementPtrInst &GEPI) { 154 Instruction &I = (Instruction&)GEPI; 155 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) 156 if (!isLoopInvariant(I.getOperand(i))) return; 157 if(SafeToHoist(GEPI)) 158 hoist(I); 159 } 160 }; 161 162 RegisterOpt<LICM> X("licm", "Loop Invariant Code Motion"); 163} 164 165Pass *createLICMPass() { return new LICM(); } 166 167/// runOnFunction - For LICM, this simply traverses the loop structure of the 168/// function, hoisting expressions out of loops if possible. 169/// 170bool LICM::runOnFunction(Function &) { 171 Changed = false; 172 173 // Get our Loop and Alias Analysis information... 174 LI = &getAnalysis<LoopInfo>(); 175 AA = &getAnalysis<AliasAnalysis>(); 176 DT = &getAnalysis<DominatorTree>(); 177 178 // Hoist expressions out of all of the top-level loops. 179 const std::vector<Loop*> &TopLevelLoops = LI->getTopLevelLoops(); 180 for (std::vector<Loop*>::const_iterator I = TopLevelLoops.begin(), 181 E = TopLevelLoops.end(); I != E; ++I) { 182 AliasSetTracker AST(*AA); 183 LICM::visitLoop(*I, AST); 184 } 185 return Changed; 186} 187 188 189/// visitLoop - Hoist expressions out of the specified loop... 190/// 191void LICM::visitLoop(Loop *L, AliasSetTracker &AST) { 192 // Recurse through all subloops before we process this loop... 193 for (std::vector<Loop*>::const_iterator I = L->getSubLoops().begin(), 194 E = L->getSubLoops().end(); I != E; ++I) { 195 AliasSetTracker SubAST(*AA); 196 LICM::visitLoop(*I, SubAST); 197 198 // Incorporate information about the subloops into this loop... 199 AST.add(SubAST); 200 } 201 CurLoop = L; 202 CurAST = &AST; 203 204 // Get the preheader block to move instructions into... 205 Preheader = L->getLoopPreheader(); 206 assert(Preheader&&"Preheader insertion pass guarantees we have a preheader!"); 207 208 // Loop over the body of this loop, looking for calls, invokes, and stores. 209 // Because subloops have already been incorporated into AST, we skip blocks in 210 // subloops. 211 // 212 const std::vector<BasicBlock*> &LoopBBs = L->getBlocks(); 213 for (std::vector<BasicBlock*>::const_iterator I = LoopBBs.begin(), 214 E = LoopBBs.end(); I != E; ++I) 215 if (LI->getLoopFor(*I) == L) // Ignore blocks in subloops... 216 AST.add(**I); // Incorporate the specified basic block 217 218 // We want to visit all of the instructions in this loop... that are not parts 219 // of our subloops (they have already had their invariants hoisted out of 220 // their loop, into this loop, so there is no need to process the BODIES of 221 // the subloops). 222 // 223 // Traverse the body of the loop in depth first order on the dominator tree so 224 // that we are guaranteed to see definitions before we see uses. This allows 225 // us to perform the LICM transformation in one pass, without iteration. 226 // 227 HoistRegion(DT->getNode(L->getHeader())); 228 229 // Now that all loop invariants have been removed from the loop, promote any 230 // memory references to scalars that we can... 231 if (!DisablePromotion) 232 PromoteValuesInLoop(); 233 234 // Clear out loops state information for the next iteration 235 CurLoop = 0; 236 Preheader = 0; 237} 238 239/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 240/// dominated by the specified block, and that are in the current loop) in depth 241/// first order w.r.t the DominatorTree. This allows us to visit defintions 242/// before uses, allowing us to hoist a loop body in one pass without iteration. 243/// 244void LICM::HoistRegion(DominatorTree::Node *N) { 245 assert(N != 0 && "Null dominator tree node?"); 246 247 // If this subregion is not in the top level loop at all, exit. 248 if (!CurLoop->contains(N->getNode())) return; 249 250 // Only need to hoist the contents of this block if it is not part of a 251 // subloop (which would already have been hoisted) 252 if (!inSubLoop(N->getNode())) 253 visit(*N->getNode()); 254 255 const std::vector<DominatorTree::Node*> &Children = N->getChildren(); 256 for (unsigned i = 0, e = Children.size(); i != e; ++i) 257 HoistRegion(Children[i]); 258} 259 260 261/// hoist - When an instruction is found to only use loop invariant operands 262/// that is safe to hoist, this instruction is called to do the dirty work. 263/// 264void LICM::hoist(Instruction &Inst) { 265 DEBUG(std::cerr << "LICM hoisting to"; 266 WriteAsOperand(std::cerr, Preheader, false); 267 std::cerr << ": " << Inst); 268 269 // Remove the instruction from its current basic block... but don't delete the 270 // instruction. 271 Inst.getParent()->getInstList().remove(&Inst); 272 273 // Insert the new node in Preheader, before the terminator. 274 Preheader->getInstList().insert(Preheader->getTerminator(), &Inst); 275 276 ++NumHoisted; 277 Changed = true; 278} 279 280/// SafeToHoist - Only hoist an instruction if it is not a trapping instruction 281/// or if it is a trapping instruction and is guaranteed to execute 282/// 283bool LICM::SafeToHoist(Instruction &Inst) { 284 285 //If it is a trapping instruction, then check if its guaranteed to execute. 286 if(Inst.isTrapping()) { 287 288 //Get the instruction's basic block. 289 BasicBlock *InstBB = Inst.getParent(); 290 291 //Get the Dominator Tree Node for the instruction's basic block/ 292 DominatorTree::Node *InstDTNode = DT->getNode(InstBB); 293 294 //Get the exit blocks for the current loop. 295 const std::vector<BasicBlock* > &ExitBlocks = CurLoop->getExitBlocks(); 296 297 //For each exit block, get the DT node and walk up the DT until 298 //the instruction's basic block is found or we exit the loop. 299 for(unsigned i=0; i < ExitBlocks.size(); ++i) { 300 DominatorTree::Node *IDom = DT->getNode(ExitBlocks[i]); 301 302 while(IDom != InstDTNode) { 303 304 //Get next Immediate Dominator. 305 IDom = IDom->getIDom(); 306 307 //See if we exited the loop. 308 if(!CurLoop->contains(IDom->getNode())) 309 return false; 310 } 311 } 312 } 313 314 return true; 315} 316 317 318void LICM::visitLoadInst(LoadInst &LI) { 319 if (isLoopInvariant(LI.getOperand(0)) && !LI.isVolatile() && 320 !pointerInvalidatedByLoop(LI.getOperand(0)) && SafeToHoist(LI)) { 321 hoist(LI); 322 ++NumHoistedLoads; 323 } 324} 325 326/// PromoteValuesInLoop - Try to promote memory values to scalars by sinking 327/// stores out of the loop and moving loads to before the loop. We do this by 328/// looping over the stores in the loop, looking for stores to Must pointers 329/// which are loop invariant. We promote these memory locations to use allocas 330/// instead. These allocas can easily be raised to register values by the 331/// PromoteMem2Reg functionality. 332/// 333void LICM::PromoteValuesInLoop() { 334 // PromotedValues - List of values that are promoted out of the loop. Each 335 // value has an alloca instruction for it, and a canonical version of the 336 // pointer. 337 std::vector<std::pair<AllocaInst*, Value*> > PromotedValues; 338 std::map<Value*, AllocaInst*> ValueToAllocaMap; // Map of ptr to alloca 339 340 findPromotableValuesInLoop(PromotedValues, ValueToAllocaMap); 341 if (ValueToAllocaMap.empty()) return; // If there are values to promote... 342 343 Changed = true; 344 NumPromoted += PromotedValues.size(); 345 346 // Emit a copy from the value into the alloca'd value in the loop preheader 347 TerminatorInst *LoopPredInst = Preheader->getTerminator(); 348 for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) { 349 // Load from the memory we are promoting... 350 LoadInst *LI = new LoadInst(PromotedValues[i].second, 351 PromotedValues[i].second->getName()+".promoted", 352 LoopPredInst); 353 // Store into the temporary alloca... 354 new StoreInst(LI, PromotedValues[i].first, LoopPredInst); 355 } 356 357 // Scan the basic blocks in the loop, replacing uses of our pointers with 358 // uses of the allocas in question. If we find a branch that exits the 359 // loop, make sure to put reload code into all of the successors of the 360 // loop. 361 // 362 const std::vector<BasicBlock*> &LoopBBs = CurLoop->getBlocks(); 363 for (std::vector<BasicBlock*>::const_iterator I = LoopBBs.begin(), 364 E = LoopBBs.end(); I != E; ++I) { 365 // Rewrite all loads and stores in the block of the pointer... 366 for (BasicBlock::iterator II = (*I)->begin(), E = (*I)->end(); 367 II != E; ++II) { 368 if (LoadInst *L = dyn_cast<LoadInst>(II)) { 369 std::map<Value*, AllocaInst*>::iterator 370 I = ValueToAllocaMap.find(L->getOperand(0)); 371 if (I != ValueToAllocaMap.end()) 372 L->setOperand(0, I->second); // Rewrite load instruction... 373 } else if (StoreInst *S = dyn_cast<StoreInst>(II)) { 374 std::map<Value*, AllocaInst*>::iterator 375 I = ValueToAllocaMap.find(S->getOperand(1)); 376 if (I != ValueToAllocaMap.end()) 377 S->setOperand(1, I->second); // Rewrite store instruction... 378 } 379 } 380 381 // Check to see if any successors of this block are outside of the loop. 382 // If so, we need to copy the value from the alloca back into the memory 383 // location... 384 // 385 for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI) 386 if (!CurLoop->contains(*SI)) { 387 // Copy all of the allocas into their memory locations... 388 BasicBlock::iterator BI = (*SI)->begin(); 389 while (isa<PHINode>(*BI)) 390 ++BI; // Skip over all of the phi nodes in the block... 391 Instruction *InsertPos = BI; 392 for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) { 393 // Load from the alloca... 394 LoadInst *LI = new LoadInst(PromotedValues[i].first, "", InsertPos); 395 // Store into the memory we promoted... 396 new StoreInst(LI, PromotedValues[i].second, InsertPos); 397 } 398 } 399 } 400 401 // Now that we have done the deed, use the mem2reg functionality to promote 402 // all of the new allocas we just created into real SSA registers... 403 // 404 std::vector<AllocaInst*> PromotedAllocas; 405 PromotedAllocas.reserve(PromotedValues.size()); 406 for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) 407 PromotedAllocas.push_back(PromotedValues[i].first); 408 PromoteMemToReg(PromotedAllocas, getAnalysis<DominanceFrontier>(), 409 AA->getTargetData()); 410} 411 412/// findPromotableValuesInLoop - Check the current loop for stores to definate 413/// pointers, which are not loaded and stored through may aliases. If these are 414/// found, create an alloca for the value, add it to the PromotedValues list, 415/// and keep track of the mapping from value to alloca... 416/// 417void LICM::findPromotableValuesInLoop( 418 std::vector<std::pair<AllocaInst*, Value*> > &PromotedValues, 419 std::map<Value*, AllocaInst*> &ValueToAllocaMap) { 420 Instruction *FnStart = CurLoop->getHeader()->getParent()->begin()->begin(); 421 422 // Loop over all of the alias sets in the tracker object... 423 for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); 424 I != E; ++I) { 425 AliasSet &AS = *I; 426 // We can promote this alias set if it has a store, if it is a "Must" alias 427 // set, and if the pointer is loop invariant. 428 if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias() && 429 isLoopInvariant(AS.begin()->first)) { 430 assert(AS.begin() != AS.end() && 431 "Must alias set should have at least one pointer element in it!"); 432 Value *V = AS.begin()->first; 433 434 // Check that all of the pointers in the alias set have the same type. We 435 // cannot (yet) promote a memory location that is loaded and stored in 436 // different sizes. 437 bool PointerOk = true; 438 for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) 439 if (V->getType() != I->first->getType()) { 440 PointerOk = false; 441 break; 442 } 443 444 if (PointerOk) { 445 const Type *Ty = cast<PointerType>(V->getType())->getElementType(); 446 AllocaInst *AI = new AllocaInst(Ty, 0, V->getName()+".tmp", FnStart); 447 PromotedValues.push_back(std::make_pair(AI, V)); 448 449 for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) 450 ValueToAllocaMap.insert(std::make_pair(I->first, AI)); 451 452 DEBUG(std::cerr << "LICM: Promoting value: " << *V << "\n"); 453 } 454 } 455 } 456} 457