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