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