xref: /llvm-project/llvm/lib/Transforms/Utils/LCSSA.cpp (revision 509b48a64a1baf497a85a2a1f86d9141b18cb1e1)
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