1 //===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===// 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 transforms loops by placing phi nodes at the end of the loops for 11 // all values that are live across the loop boundary. For example, it turns 12 // the left into the right code: 13 // 14 // for (...) for (...) 15 // if (c) if (c) 16 // X1 = ... X1 = ... 17 // else else 18 // X2 = ... X2 = ... 19 // X3 = phi(X1, X2) X3 = phi(X1, X2) 20 // ... = X3 + 4 X4 = phi(X3) 21 // ... = X4 + 4 22 // 23 // This is still valid LLVM; the extra phi nodes are purely redundant, and will 24 // be trivially eliminated by InstCombine. The major benefit of this 25 // transformation is that it makes many other loop optimizations, such as 26 // LoopUnswitching, simpler. 27 // 28 //===----------------------------------------------------------------------===// 29 30 #include "llvm/Transforms/Utils/LCSSA.h" 31 #include "llvm/ADT/STLExtras.h" 32 #include "llvm/ADT/Statistic.h" 33 #include "llvm/Analysis/AliasAnalysis.h" 34 #include "llvm/Analysis/BasicAliasAnalysis.h" 35 #include "llvm/Analysis/GlobalsModRef.h" 36 #include "llvm/Analysis/LoopPass.h" 37 #include "llvm/Analysis/ScalarEvolution.h" 38 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" 39 #include "llvm/IR/Constants.h" 40 #include "llvm/IR/Dominators.h" 41 #include "llvm/IR/Function.h" 42 #include "llvm/IR/Instructions.h" 43 #include "llvm/IR/PredIteratorCache.h" 44 #include "llvm/Pass.h" 45 #include "llvm/Transforms/Scalar.h" 46 #include "llvm/Transforms/Utils/LoopUtils.h" 47 #include "llvm/Transforms/Utils/SSAUpdater.h" 48 using namespace llvm; 49 50 #define DEBUG_TYPE "lcssa" 51 52 STATISTIC(NumLCSSA, "Number of live out of a loop variables"); 53 54 /// Return true if the specified block is in the list. 55 static bool isExitBlock(BasicBlock *BB, 56 const SmallVectorImpl<BasicBlock *> &ExitBlocks) { 57 return find(ExitBlocks, BB) != ExitBlocks.end(); 58 } 59 60 /// For every instruction from the worklist, check to see if it has any uses 61 /// that are outside the current loop. If so, insert LCSSA PHI nodes and 62 /// rewrite the uses. 63 bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist, 64 DominatorTree &DT, LoopInfo &LI) { 65 SmallVector<Use *, 16> UsesToRewrite; 66 SmallVector<BasicBlock *, 8> ExitBlocks; 67 SmallSetVector<PHINode *, 16> PHIsToRemove; 68 PredIteratorCache PredCache; 69 bool Changed = false; 70 71 while (!Worklist.empty()) { 72 UsesToRewrite.clear(); 73 ExitBlocks.clear(); 74 75 Instruction *I = Worklist.pop_back_val(); 76 BasicBlock *InstBB = I->getParent(); 77 Loop *L = LI.getLoopFor(InstBB); 78 L->getExitBlocks(ExitBlocks); 79 80 if (ExitBlocks.empty()) 81 continue; 82 83 // Tokens cannot be used in PHI nodes, so we skip over them. 84 // We can run into tokens which are live out of a loop with catchswitch 85 // instructions in Windows EH if the catchswitch has one catchpad which 86 // is inside the loop and another which is not. 87 if (I->getType()->isTokenTy()) 88 continue; 89 90 for (Use &U : I->uses()) { 91 Instruction *User = cast<Instruction>(U.getUser()); 92 BasicBlock *UserBB = User->getParent(); 93 if (PHINode *PN = dyn_cast<PHINode>(User)) 94 UserBB = PN->getIncomingBlock(U); 95 96 if (InstBB != UserBB && !L->contains(UserBB)) 97 UsesToRewrite.push_back(&U); 98 } 99 100 // If there are no uses outside the loop, exit with no change. 101 if (UsesToRewrite.empty()) 102 continue; 103 104 ++NumLCSSA; // We are applying the transformation 105 106 // Invoke instructions are special in that their result value is not 107 // available along their unwind edge. The code below tests to see whether 108 // DomBB dominates the value, so adjust DomBB to the normal destination 109 // block, which is effectively where the value is first usable. 110 BasicBlock *DomBB = InstBB; 111 if (InvokeInst *Inv = dyn_cast<InvokeInst>(I)) 112 DomBB = Inv->getNormalDest(); 113 114 DomTreeNode *DomNode = DT.getNode(DomBB); 115 116 SmallVector<PHINode *, 16> AddedPHIs; 117 SmallVector<PHINode *, 8> PostProcessPHIs; 118 119 SmallVector<PHINode *, 4> InsertedPHIs; 120 SSAUpdater SSAUpdate(&InsertedPHIs); 121 SSAUpdate.Initialize(I->getType(), I->getName()); 122 123 // Insert the LCSSA phi's into all of the exit blocks dominated by the 124 // value, and add them to the Phi's map. 125 for (BasicBlock *ExitBB : ExitBlocks) { 126 if (!DT.dominates(DomNode, DT.getNode(ExitBB))) 127 continue; 128 129 // If we already inserted something for this BB, don't reprocess it. 130 if (SSAUpdate.HasValueForBlock(ExitBB)) 131 continue; 132 133 PHINode *PN = PHINode::Create(I->getType(), PredCache.size(ExitBB), 134 I->getName() + ".lcssa", &ExitBB->front()); 135 136 // Add inputs from inside the loop for this PHI. 137 for (BasicBlock *Pred : PredCache.get(ExitBB)) { 138 PN->addIncoming(I, Pred); 139 140 // If the exit block has a predecessor not within the loop, arrange for 141 // the incoming value use corresponding to that predecessor to be 142 // rewritten in terms of a different LCSSA PHI. 143 if (!L->contains(Pred)) 144 UsesToRewrite.push_back( 145 &PN->getOperandUse(PN->getOperandNumForIncomingValue( 146 PN->getNumIncomingValues() - 1))); 147 } 148 149 AddedPHIs.push_back(PN); 150 151 // Remember that this phi makes the value alive in this block. 152 SSAUpdate.AddAvailableValue(ExitBB, PN); 153 154 // LoopSimplify might fail to simplify some loops (e.g. when indirect 155 // branches are involved). In such situations, it might happen that an 156 // exit for Loop L1 is the header of a disjoint Loop L2. Thus, when we 157 // create PHIs in such an exit block, we are also inserting PHIs into L2's 158 // header. This could break LCSSA form for L2 because these inserted PHIs 159 // can also have uses outside of L2. Remember all PHIs in such situation 160 // as to revisit than later on. FIXME: Remove this if indirectbr support 161 // into LoopSimplify gets improved. 162 if (auto *OtherLoop = LI.getLoopFor(ExitBB)) 163 if (!L->contains(OtherLoop)) 164 PostProcessPHIs.push_back(PN); 165 } 166 167 // Rewrite all uses outside the loop in terms of the new PHIs we just 168 // inserted. 169 for (Use *UseToRewrite : UsesToRewrite) { 170 // If this use is in an exit block, rewrite to use the newly inserted PHI. 171 // This is required for correctness because SSAUpdate doesn't handle uses 172 // in the same block. It assumes the PHI we inserted is at the end of the 173 // block. 174 Instruction *User = cast<Instruction>(UseToRewrite->getUser()); 175 BasicBlock *UserBB = User->getParent(); 176 if (PHINode *PN = dyn_cast<PHINode>(User)) 177 UserBB = PN->getIncomingBlock(*UseToRewrite); 178 179 if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) { 180 // Tell the VHs that the uses changed. This updates SCEV's caches. 181 if (UseToRewrite->get()->hasValueHandle()) 182 ValueHandleBase::ValueIsRAUWd(*UseToRewrite, &UserBB->front()); 183 UseToRewrite->set(&UserBB->front()); 184 continue; 185 } 186 187 // Otherwise, do full PHI insertion. 188 SSAUpdate.RewriteUse(*UseToRewrite); 189 } 190 191 // SSAUpdater might have inserted phi-nodes inside other loops. We'll need 192 // to post-process them to keep LCSSA form. 193 for (PHINode *InsertedPN : InsertedPHIs) { 194 if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent())) 195 if (!L->contains(OtherLoop)) 196 PostProcessPHIs.push_back(InsertedPN); 197 } 198 199 // Post process PHI instructions that were inserted into another disjoint 200 // loop and update their exits properly. 201 for (auto *PostProcessPN : PostProcessPHIs) { 202 if (PostProcessPN->use_empty()) 203 continue; 204 205 // Reprocess each PHI instruction. 206 Worklist.push_back(PostProcessPN); 207 } 208 209 // Keep track of PHI nodes that we want to remove because they did not have 210 // any uses rewritten. 211 for (PHINode *PN : AddedPHIs) 212 if (PN->use_empty()) 213 PHIsToRemove.insert(PN); 214 215 Changed = true; 216 } 217 // Remove PHI nodes that did not have any uses rewritten. 218 for (PHINode *PN : PHIsToRemove) { 219 assert (PN->use_empty() && "Trying to remove a phi with uses."); 220 PN->eraseFromParent(); 221 } 222 return Changed; 223 } 224 225 /// Return true if the specified block dominates at least 226 /// one of the blocks in the specified list. 227 static bool 228 blockDominatesAnExit(BasicBlock *BB, 229 DominatorTree &DT, 230 const SmallVectorImpl<BasicBlock *> &ExitBlocks) { 231 DomTreeNode *DomNode = DT.getNode(BB); 232 return llvm::any_of(ExitBlocks, [&](BasicBlock * EB) { 233 return DT.dominates(DomNode, DT.getNode(EB)); 234 }); 235 } 236 237 bool llvm::formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, 238 ScalarEvolution *SE) { 239 bool Changed = false; 240 241 // Get the set of exiting blocks. 242 SmallVector<BasicBlock *, 8> ExitBlocks; 243 L.getExitBlocks(ExitBlocks); 244 245 if (ExitBlocks.empty()) 246 return false; 247 248 SmallVector<Instruction *, 8> Worklist; 249 250 // Look at all the instructions in the loop, checking to see if they have uses 251 // outside the loop. If so, put them into the worklist to rewrite those uses. 252 for (BasicBlock *BB : L.blocks()) { 253 // For large loops, avoid use-scanning by using dominance information: In 254 // particular, if a block does not dominate any of the loop exits, then none 255 // of the values defined in the block could be used outside the loop. 256 if (!blockDominatesAnExit(BB, DT, ExitBlocks)) 257 continue; 258 259 for (Instruction &I : *BB) { 260 // Reject two common cases fast: instructions with no uses (like stores) 261 // and instructions with one use that is in the same block as this. 262 if (I.use_empty() || 263 (I.hasOneUse() && I.user_back()->getParent() == BB && 264 !isa<PHINode>(I.user_back()))) 265 continue; 266 267 Worklist.push_back(&I); 268 } 269 } 270 Changed = formLCSSAForInstructions(Worklist, DT, *LI); 271 272 // If we modified the code, remove any caches about the loop from SCEV to 273 // avoid dangling entries. 274 // FIXME: This is a big hammer, can we clear the cache more selectively? 275 if (SE && Changed) 276 SE->forgetLoop(&L); 277 278 assert(L.isLCSSAForm(DT)); 279 280 return Changed; 281 } 282 283 /// Process a loop nest depth first. 284 bool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, 285 ScalarEvolution *SE) { 286 bool Changed = false; 287 288 // Recurse depth-first through inner loops. 289 for (Loop *SubLoop : L.getSubLoops()) 290 Changed |= formLCSSARecursively(*SubLoop, DT, LI, SE); 291 292 Changed |= formLCSSA(L, DT, LI, SE); 293 return Changed; 294 } 295 296 /// Process all loops in the function, inner-most out. 297 static bool formLCSSAOnAllLoops(LoopInfo *LI, DominatorTree &DT, 298 ScalarEvolution *SE) { 299 bool Changed = false; 300 for (auto &L : *LI) 301 Changed |= formLCSSARecursively(*L, DT, LI, SE); 302 return Changed; 303 } 304 305 namespace { 306 struct LCSSAWrapperPass : public FunctionPass { 307 static char ID; // Pass identification, replacement for typeid 308 LCSSAWrapperPass() : FunctionPass(ID) { 309 initializeLCSSAWrapperPassPass(*PassRegistry::getPassRegistry()); 310 } 311 312 // Cached analysis information for the current function. 313 DominatorTree *DT; 314 LoopInfo *LI; 315 ScalarEvolution *SE; 316 317 bool runOnFunction(Function &F) override; 318 void verifyAnalysis() const override { 319 assert( 320 all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); }) && 321 "LCSSA form is broken!"); 322 }; 323 324 /// This transformation requires natural loop information & requires that 325 /// loop preheaders be inserted into the CFG. It maintains both of these, 326 /// as well as the CFG. It also requires dominator information. 327 void getAnalysisUsage(AnalysisUsage &AU) const override { 328 AU.setPreservesCFG(); 329 330 AU.addRequired<DominatorTreeWrapperPass>(); 331 AU.addRequired<LoopInfoWrapperPass>(); 332 AU.addPreservedID(LoopSimplifyID); 333 AU.addPreserved<AAResultsWrapperPass>(); 334 AU.addPreserved<BasicAAWrapperPass>(); 335 AU.addPreserved<GlobalsAAWrapperPass>(); 336 AU.addPreserved<ScalarEvolutionWrapperPass>(); 337 AU.addPreserved<SCEVAAWrapperPass>(); 338 } 339 }; 340 } 341 342 char LCSSAWrapperPass::ID = 0; 343 INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass", 344 false, false) 345 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 346 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 347 INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass", 348 false, false) 349 350 Pass *llvm::createLCSSAPass() { return new LCSSAWrapperPass(); } 351 char &llvm::LCSSAID = LCSSAWrapperPass::ID; 352 353 /// Transform \p F into loop-closed SSA form. 354 bool LCSSAWrapperPass::runOnFunction(Function &F) { 355 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 356 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 357 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>(); 358 SE = SEWP ? &SEWP->getSE() : nullptr; 359 360 return formLCSSAOnAllLoops(LI, *DT, SE); 361 } 362 363 PreservedAnalyses LCSSAPass::run(Function &F, FunctionAnalysisManager &AM) { 364 auto &LI = AM.getResult<LoopAnalysis>(F); 365 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 366 auto *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F); 367 if (!formLCSSAOnAllLoops(&LI, DT, SE)) 368 return PreservedAnalyses::all(); 369 370 // FIXME: This should also 'preserve the CFG'. 371 PreservedAnalyses PA; 372 PA.preserve<BasicAA>(); 373 PA.preserve<GlobalsAA>(); 374 PA.preserve<SCEVAA>(); 375 PA.preserve<ScalarEvolutionAnalysis>(); 376 return PA; 377 } 378