1 //===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This pass transforms loops by placing phi nodes at the end of the loops for 10 // all values that are live across the loop boundary. For example, it turns 11 // the left into the right code: 12 // 13 // for (...) for (...) 14 // if (c) if (c) 15 // X1 = ... X1 = ... 16 // else else 17 // X2 = ... X2 = ... 18 // X3 = phi(X1, X2) X3 = phi(X1, X2) 19 // ... = X3 + 4 X4 = phi(X3) 20 // ... = X4 + 4 21 // 22 // This is still valid LLVM; the extra phi nodes are purely redundant, and will 23 // be trivially eliminated by InstCombine. The major benefit of this 24 // transformation is that it makes many other loop optimizations, such as 25 // LoopUnswitching, simpler. 26 // 27 //===----------------------------------------------------------------------===// 28 29 #include "llvm/Transforms/Utils/LCSSA.h" 30 #include "llvm/ADT/STLExtras.h" 31 #include "llvm/ADT/Statistic.h" 32 #include "llvm/Analysis/AliasAnalysis.h" 33 #include "llvm/Analysis/BasicAliasAnalysis.h" 34 #include "llvm/Analysis/GlobalsModRef.h" 35 #include "llvm/Analysis/LoopPass.h" 36 #include "llvm/Analysis/ScalarEvolution.h" 37 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" 38 #include "llvm/Transforms/Utils/Local.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/IntrinsicInst.h" 44 #include "llvm/IR/PredIteratorCache.h" 45 #include "llvm/Pass.h" 46 #include "llvm/Transforms/Utils.h" 47 #include "llvm/Transforms/Utils/LoopUtils.h" 48 #include "llvm/Transforms/Utils/SSAUpdater.h" 49 using namespace llvm; 50 51 #define DEBUG_TYPE "lcssa" 52 53 STATISTIC(NumLCSSA, "Number of live out of a loop variables"); 54 55 #ifdef EXPENSIVE_CHECKS 56 static bool VerifyLoopLCSSA = true; 57 #else 58 static bool VerifyLoopLCSSA = false; 59 #endif 60 static cl::opt<bool, true> 61 VerifyLoopLCSSAFlag("verify-loop-lcssa", cl::location(VerifyLoopLCSSA), 62 cl::Hidden, 63 cl::desc("Verify loop lcssa form (time consuming)")); 64 65 /// Return true if the specified block is in the list. 66 static bool isExitBlock(BasicBlock *BB, 67 const SmallVectorImpl<BasicBlock *> &ExitBlocks) { 68 return is_contained(ExitBlocks, BB); 69 } 70 71 /// For every instruction from the worklist, check to see if it has any uses 72 /// that are outside the current loop. If so, insert LCSSA PHI nodes and 73 /// rewrite the uses. 74 bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist, 75 DominatorTree &DT, LoopInfo &LI) { 76 SmallVector<Use *, 16> UsesToRewrite; 77 SmallSetVector<PHINode *, 16> PHIsToRemove; 78 PredIteratorCache PredCache; 79 bool Changed = false; 80 81 // Cache the Loop ExitBlocks across this loop. We expect to get a lot of 82 // instructions within the same loops, computing the exit blocks is 83 // expensive, and we're not mutating the loop structure. 84 SmallDenseMap<Loop*, SmallVector<BasicBlock *,1>> LoopExitBlocks; 85 86 while (!Worklist.empty()) { 87 UsesToRewrite.clear(); 88 89 Instruction *I = Worklist.pop_back_val(); 90 assert(!I->getType()->isTokenTy() && "Tokens shouldn't be in the worklist"); 91 BasicBlock *InstBB = I->getParent(); 92 Loop *L = LI.getLoopFor(InstBB); 93 assert(L && "Instruction belongs to a BB that's not part of a loop"); 94 if (!LoopExitBlocks.count(L)) 95 L->getExitBlocks(LoopExitBlocks[L]); 96 assert(LoopExitBlocks.count(L)); 97 const SmallVectorImpl<BasicBlock *> &ExitBlocks = LoopExitBlocks[L]; 98 99 if (ExitBlocks.empty()) 100 continue; 101 102 for (Use &U : I->uses()) { 103 Instruction *User = cast<Instruction>(U.getUser()); 104 BasicBlock *UserBB = User->getParent(); 105 if (auto *PN = dyn_cast<PHINode>(User)) 106 UserBB = PN->getIncomingBlock(U); 107 108 if (InstBB != UserBB && !L->contains(UserBB)) 109 UsesToRewrite.push_back(&U); 110 } 111 112 // If there are no uses outside the loop, exit with no change. 113 if (UsesToRewrite.empty()) 114 continue; 115 116 ++NumLCSSA; // We are applying the transformation 117 118 // Invoke instructions are special in that their result value is not 119 // available along their unwind edge. The code below tests to see whether 120 // DomBB dominates the value, so adjust DomBB to the normal destination 121 // block, which is effectively where the value is first usable. 122 BasicBlock *DomBB = InstBB; 123 if (auto *Inv = dyn_cast<InvokeInst>(I)) 124 DomBB = Inv->getNormalDest(); 125 126 DomTreeNode *DomNode = DT.getNode(DomBB); 127 128 SmallVector<PHINode *, 16> AddedPHIs; 129 SmallVector<PHINode *, 8> PostProcessPHIs; 130 131 SmallVector<PHINode *, 4> InsertedPHIs; 132 SSAUpdater SSAUpdate(&InsertedPHIs); 133 SSAUpdate.Initialize(I->getType(), I->getName()); 134 135 // Insert the LCSSA phi's into all of the exit blocks dominated by the 136 // value, and add them to the Phi's map. 137 for (BasicBlock *ExitBB : ExitBlocks) { 138 if (!DT.dominates(DomNode, DT.getNode(ExitBB))) 139 continue; 140 141 // If we already inserted something for this BB, don't reprocess it. 142 if (SSAUpdate.HasValueForBlock(ExitBB)) 143 continue; 144 145 PHINode *PN = PHINode::Create(I->getType(), PredCache.size(ExitBB), 146 I->getName() + ".lcssa", &ExitBB->front()); 147 // Get the debug location from the original instruction. 148 PN->setDebugLoc(I->getDebugLoc()); 149 // Add inputs from inside the loop for this PHI. 150 for (BasicBlock *Pred : PredCache.get(ExitBB)) { 151 PN->addIncoming(I, Pred); 152 153 // If the exit block has a predecessor not within the loop, arrange for 154 // the incoming value use corresponding to that predecessor to be 155 // rewritten in terms of a different LCSSA PHI. 156 if (!L->contains(Pred)) 157 UsesToRewrite.push_back( 158 &PN->getOperandUse(PN->getOperandNumForIncomingValue( 159 PN->getNumIncomingValues() - 1))); 160 } 161 162 AddedPHIs.push_back(PN); 163 164 // Remember that this phi makes the value alive in this block. 165 SSAUpdate.AddAvailableValue(ExitBB, PN); 166 167 // LoopSimplify might fail to simplify some loops (e.g. when indirect 168 // branches are involved). In such situations, it might happen that an 169 // exit for Loop L1 is the header of a disjoint Loop L2. Thus, when we 170 // create PHIs in such an exit block, we are also inserting PHIs into L2's 171 // header. This could break LCSSA form for L2 because these inserted PHIs 172 // can also have uses outside of L2. Remember all PHIs in such situation 173 // as to revisit than later on. FIXME: Remove this if indirectbr support 174 // into LoopSimplify gets improved. 175 if (auto *OtherLoop = LI.getLoopFor(ExitBB)) 176 if (!L->contains(OtherLoop)) 177 PostProcessPHIs.push_back(PN); 178 } 179 180 // Rewrite all uses outside the loop in terms of the new PHIs we just 181 // inserted. 182 for (Use *UseToRewrite : UsesToRewrite) { 183 // If this use is in an exit block, rewrite to use the newly inserted PHI. 184 // This is required for correctness because SSAUpdate doesn't handle uses 185 // in the same block. It assumes the PHI we inserted is at the end of the 186 // block. 187 Instruction *User = cast<Instruction>(UseToRewrite->getUser()); 188 BasicBlock *UserBB = User->getParent(); 189 if (auto *PN = dyn_cast<PHINode>(User)) 190 UserBB = PN->getIncomingBlock(*UseToRewrite); 191 192 if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) { 193 // Tell the VHs that the uses changed. This updates SCEV's caches. 194 if (UseToRewrite->get()->hasValueHandle()) 195 ValueHandleBase::ValueIsRAUWd(*UseToRewrite, &UserBB->front()); 196 UseToRewrite->set(&UserBB->front()); 197 continue; 198 } 199 200 // Otherwise, do full PHI insertion. 201 SSAUpdate.RewriteUse(*UseToRewrite); 202 } 203 204 SmallVector<DbgValueInst *, 4> DbgValues; 205 llvm::findDbgValues(DbgValues, I); 206 207 // Update pre-existing debug value uses that reside outside the loop. 208 auto &Ctx = I->getContext(); 209 for (auto DVI : DbgValues) { 210 BasicBlock *UserBB = DVI->getParent(); 211 if (InstBB == UserBB || L->contains(UserBB)) 212 continue; 213 // We currently only handle debug values residing in blocks where we have 214 // inserted a PHI instruction. 215 if (Value *V = SSAUpdate.FindValueForBlock(UserBB)) 216 DVI->setOperand(0, MetadataAsValue::get(Ctx, ValueAsMetadata::get(V))); 217 } 218 219 // SSAUpdater might have inserted phi-nodes inside other loops. We'll need 220 // to post-process them to keep LCSSA form. 221 for (PHINode *InsertedPN : InsertedPHIs) { 222 if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent())) 223 if (!L->contains(OtherLoop)) 224 PostProcessPHIs.push_back(InsertedPN); 225 } 226 227 // Post process PHI instructions that were inserted into another disjoint 228 // loop and update their exits properly. 229 for (auto *PostProcessPN : PostProcessPHIs) 230 if (!PostProcessPN->use_empty()) 231 Worklist.push_back(PostProcessPN); 232 233 // Keep track of PHI nodes that we want to remove because they did not have 234 // any uses rewritten. If the new PHI is used, store it so that we can 235 // try to propagate dbg.value intrinsics to it. 236 SmallVector<PHINode *, 2> NeedDbgValues; 237 for (PHINode *PN : AddedPHIs) 238 if (PN->use_empty()) 239 PHIsToRemove.insert(PN); 240 else 241 NeedDbgValues.push_back(PN); 242 insertDebugValuesForPHIs(InstBB, NeedDbgValues); 243 Changed = true; 244 } 245 // Remove PHI nodes that did not have any uses rewritten. We need to redo the 246 // use_empty() check here, because even if the PHI node wasn't used when added 247 // to PHIsToRemove, later added PHI nodes can be using it. This cleanup is 248 // not guaranteed to handle trees/cycles of PHI nodes that only are used by 249 // each other. Such situations has only been noticed when the input IR 250 // contains unreachable code, and leaving some extra redundant PHI nodes in 251 // such situations is considered a minor problem. 252 for (PHINode *PN : PHIsToRemove) 253 if (PN->use_empty()) 254 PN->eraseFromParent(); 255 return Changed; 256 } 257 258 // Compute the set of BasicBlocks in the loop `L` dominating at least one exit. 259 static void computeBlocksDominatingExits( 260 Loop &L, DominatorTree &DT, SmallVector<BasicBlock *, 8> &ExitBlocks, 261 SmallSetVector<BasicBlock *, 8> &BlocksDominatingExits) { 262 SmallVector<BasicBlock *, 8> BBWorklist; 263 264 // We start from the exit blocks, as every block trivially dominates itself 265 // (not strictly). 266 for (BasicBlock *BB : ExitBlocks) 267 BBWorklist.push_back(BB); 268 269 while (!BBWorklist.empty()) { 270 BasicBlock *BB = BBWorklist.pop_back_val(); 271 272 // Check if this is a loop header. If this is the case, we're done. 273 if (L.getHeader() == BB) 274 continue; 275 276 // Otherwise, add its immediate predecessor in the dominator tree to the 277 // worklist, unless we visited it already. 278 BasicBlock *IDomBB = DT.getNode(BB)->getIDom()->getBlock(); 279 280 // Exit blocks can have an immediate dominator not beloinging to the 281 // loop. For an exit block to be immediately dominated by another block 282 // outside the loop, it implies not all paths from that dominator, to the 283 // exit block, go through the loop. 284 // Example: 285 // 286 // |---- A 287 // | | 288 // | B<-- 289 // | | | 290 // |---> C -- 291 // | 292 // D 293 // 294 // C is the exit block of the loop and it's immediately dominated by A, 295 // which doesn't belong to the loop. 296 if (!L.contains(IDomBB)) 297 continue; 298 299 if (BlocksDominatingExits.insert(IDomBB)) 300 BBWorklist.push_back(IDomBB); 301 } 302 } 303 304 bool llvm::formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, 305 ScalarEvolution *SE) { 306 bool Changed = false; 307 308 #ifdef EXPENSIVE_CHECKS 309 // Verify all sub-loops are in LCSSA form already. 310 for (Loop *SubLoop: L) 311 assert(SubLoop->isRecursivelyLCSSAForm(DT, *LI) && "Subloop not in LCSSA!"); 312 #endif 313 314 SmallVector<BasicBlock *, 8> ExitBlocks; 315 L.getExitBlocks(ExitBlocks); 316 if (ExitBlocks.empty()) 317 return false; 318 319 SmallSetVector<BasicBlock *, 8> BlocksDominatingExits; 320 321 // We want to avoid use-scanning leveraging dominance informations. 322 // If a block doesn't dominate any of the loop exits, the none of the values 323 // defined in the loop can be used outside. 324 // We compute the set of blocks fullfilling the conditions in advance 325 // walking the dominator tree upwards until we hit a loop header. 326 computeBlocksDominatingExits(L, DT, ExitBlocks, BlocksDominatingExits); 327 328 SmallVector<Instruction *, 8> Worklist; 329 330 // Look at all the instructions in the loop, checking to see if they have uses 331 // outside the loop. If so, put them into the worklist to rewrite those uses. 332 for (BasicBlock *BB : BlocksDominatingExits) { 333 // Skip blocks that are part of any sub-loops, they must be in LCSSA 334 // already. 335 if (LI->getLoopFor(BB) != &L) 336 continue; 337 for (Instruction &I : *BB) { 338 // Reject two common cases fast: instructions with no uses (like stores) 339 // and instructions with one use that is in the same block as this. 340 if (I.use_empty() || 341 (I.hasOneUse() && I.user_back()->getParent() == BB && 342 !isa<PHINode>(I.user_back()))) 343 continue; 344 345 // Tokens cannot be used in PHI nodes, so we skip over them. 346 // We can run into tokens which are live out of a loop with catchswitch 347 // instructions in Windows EH if the catchswitch has one catchpad which 348 // is inside the loop and another which is not. 349 if (I.getType()->isTokenTy()) 350 continue; 351 352 Worklist.push_back(&I); 353 } 354 } 355 Changed = formLCSSAForInstructions(Worklist, DT, *LI); 356 357 // If we modified the code, remove any caches about the loop from SCEV to 358 // avoid dangling entries. 359 // FIXME: This is a big hammer, can we clear the cache more selectively? 360 if (SE && Changed) 361 SE->forgetLoop(&L); 362 363 assert(L.isLCSSAForm(DT)); 364 365 return Changed; 366 } 367 368 /// Process a loop nest depth first. 369 bool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, 370 ScalarEvolution *SE) { 371 bool Changed = false; 372 373 // Recurse depth-first through inner loops. 374 for (Loop *SubLoop : L.getSubLoops()) 375 Changed |= formLCSSARecursively(*SubLoop, DT, LI, SE); 376 377 Changed |= formLCSSA(L, DT, LI, SE); 378 return Changed; 379 } 380 381 /// Process all loops in the function, inner-most out. 382 static bool formLCSSAOnAllLoops(LoopInfo *LI, DominatorTree &DT, 383 ScalarEvolution *SE) { 384 bool Changed = false; 385 for (auto &L : *LI) 386 Changed |= formLCSSARecursively(*L, DT, LI, SE); 387 return Changed; 388 } 389 390 namespace { 391 struct LCSSAWrapperPass : public FunctionPass { 392 static char ID; // Pass identification, replacement for typeid 393 LCSSAWrapperPass() : FunctionPass(ID) { 394 initializeLCSSAWrapperPassPass(*PassRegistry::getPassRegistry()); 395 } 396 397 // Cached analysis information for the current function. 398 DominatorTree *DT; 399 LoopInfo *LI; 400 ScalarEvolution *SE; 401 402 bool runOnFunction(Function &F) override; 403 void verifyAnalysis() const override { 404 // This check is very expensive. On the loop intensive compiles it may cause 405 // up to 10x slowdown. Currently it's disabled by default. LPPassManager 406 // always does limited form of the LCSSA verification. Similar reasoning 407 // was used for the LoopInfo verifier. 408 if (VerifyLoopLCSSA) { 409 assert(all_of(*LI, 410 [&](Loop *L) { 411 return L->isRecursivelyLCSSAForm(*DT, *LI); 412 }) && 413 "LCSSA form is broken!"); 414 } 415 }; 416 417 /// This transformation requires natural loop information & requires that 418 /// loop preheaders be inserted into the CFG. It maintains both of these, 419 /// as well as the CFG. It also requires dominator information. 420 void getAnalysisUsage(AnalysisUsage &AU) const override { 421 AU.setPreservesCFG(); 422 423 AU.addRequired<DominatorTreeWrapperPass>(); 424 AU.addRequired<LoopInfoWrapperPass>(); 425 AU.addPreservedID(LoopSimplifyID); 426 AU.addPreserved<AAResultsWrapperPass>(); 427 AU.addPreserved<BasicAAWrapperPass>(); 428 AU.addPreserved<GlobalsAAWrapperPass>(); 429 AU.addPreserved<ScalarEvolutionWrapperPass>(); 430 AU.addPreserved<SCEVAAWrapperPass>(); 431 432 // This is needed to perform LCSSA verification inside LPPassManager 433 AU.addRequired<LCSSAVerificationPass>(); 434 AU.addPreserved<LCSSAVerificationPass>(); 435 } 436 }; 437 } 438 439 char LCSSAWrapperPass::ID = 0; 440 INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass", 441 false, false) 442 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 443 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 444 INITIALIZE_PASS_DEPENDENCY(LCSSAVerificationPass) 445 INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass", 446 false, false) 447 448 Pass *llvm::createLCSSAPass() { return new LCSSAWrapperPass(); } 449 char &llvm::LCSSAID = LCSSAWrapperPass::ID; 450 451 /// Transform \p F into loop-closed SSA form. 452 bool LCSSAWrapperPass::runOnFunction(Function &F) { 453 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 454 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 455 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>(); 456 SE = SEWP ? &SEWP->getSE() : nullptr; 457 458 return formLCSSAOnAllLoops(LI, *DT, SE); 459 } 460 461 PreservedAnalyses LCSSAPass::run(Function &F, FunctionAnalysisManager &AM) { 462 auto &LI = AM.getResult<LoopAnalysis>(F); 463 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 464 auto *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F); 465 if (!formLCSSAOnAllLoops(&LI, DT, SE)) 466 return PreservedAnalyses::all(); 467 468 PreservedAnalyses PA; 469 PA.preserveSet<CFGAnalyses>(); 470 PA.preserve<BasicAA>(); 471 PA.preserve<GlobalsAA>(); 472 PA.preserve<SCEVAA>(); 473 PA.preserve<ScalarEvolutionAnalysis>(); 474 return PA; 475 } 476