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