LLVM 17.0.0git
LCSSA.cpp
Go to the documentation of this file.
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
30#include "llvm/ADT/STLExtras.h"
31#include "llvm/ADT/Statistic.h"
41#include "llvm/IR/DebugInfo.h"
42#include "llvm/IR/Dominators.h"
43#include "llvm/IR/IRBuilder.h"
48#include "llvm/Pass.h"
53using namespace llvm;
54
55#define DEBUG_TYPE "lcssa"
56
57STATISTIC(NumLCSSA, "Number of live out of a loop variables");
58
59#ifdef EXPENSIVE_CHECKS
60static bool VerifyLoopLCSSA = true;
61#else
62static bool VerifyLoopLCSSA = false;
63#endif
67 cl::desc("Verify loop lcssa form (time consuming)"));
68
69/// Return true if the specified block is in the list.
70static bool isExitBlock(BasicBlock *BB,
71 const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
72 return is_contained(ExitBlocks, BB);
73}
74
75/// For every instruction from the worklist, check to see if it has any uses
76/// that are outside the current loop. If so, insert LCSSA PHI nodes and
77/// rewrite the uses.
79 const DominatorTree &DT, const LoopInfo &LI,
80 ScalarEvolution *SE, IRBuilderBase &Builder,
81 SmallVectorImpl<PHINode *> *PHIsToRemove) {
82 SmallVector<Use *, 16> UsesToRewrite;
83 SmallSetVector<PHINode *, 16> LocalPHIsToRemove;
84 PredIteratorCache PredCache;
85 bool Changed = false;
86
88
89 // Cache the Loop ExitBlocks across this loop. We expect to get a lot of
90 // instructions within the same loops, computing the exit blocks is
91 // expensive, and we're not mutating the loop structure.
93
94 while (!Worklist.empty()) {
95 UsesToRewrite.clear();
96
97 Instruction *I = Worklist.pop_back_val();
98 assert(!I->getType()->isTokenTy() && "Tokens shouldn't be in the worklist");
99 BasicBlock *InstBB = I->getParent();
100 Loop *L = LI.getLoopFor(InstBB);
101 assert(L && "Instruction belongs to a BB that's not part of a loop");
102 if (!LoopExitBlocks.count(L))
103 L->getExitBlocks(LoopExitBlocks[L]);
104 assert(LoopExitBlocks.count(L));
105 const SmallVectorImpl<BasicBlock *> &ExitBlocks = LoopExitBlocks[L];
106
107 if (ExitBlocks.empty())
108 continue;
109
110 for (Use &U : make_early_inc_range(I->uses())) {
111 Instruction *User = cast<Instruction>(U.getUser());
112 BasicBlock *UserBB = User->getParent();
113
114 // Skip uses in unreachable blocks.
115 if (!DT.isReachableFromEntry(UserBB)) {
116 U.set(PoisonValue::get(I->getType()));
117 continue;
118 }
119
120 // For practical purposes, we consider that the use in a PHI
121 // occurs in the respective predecessor block. For more info,
122 // see the `phi` doc in LangRef and the LCSSA doc.
123 if (auto *PN = dyn_cast<PHINode>(User))
124 UserBB = PN->getIncomingBlock(U);
125
126 if (InstBB != UserBB && !L->contains(UserBB))
127 UsesToRewrite.push_back(&U);
128 }
129
130 // If there are no uses outside the loop, exit with no change.
131 if (UsesToRewrite.empty())
132 continue;
133
134 ++NumLCSSA; // We are applying the transformation
135
136 // Invoke instructions are special in that their result value is not
137 // available along their unwind edge. The code below tests to see whether
138 // DomBB dominates the value, so adjust DomBB to the normal destination
139 // block, which is effectively where the value is first usable.
140 BasicBlock *DomBB = InstBB;
141 if (auto *Inv = dyn_cast<InvokeInst>(I))
142 DomBB = Inv->getNormalDest();
143
144 const DomTreeNode *DomNode = DT.getNode(DomBB);
145
147 SmallVector<PHINode *, 8> PostProcessPHIs;
148
149 SmallVector<PHINode *, 4> InsertedPHIs;
150 SSAUpdater SSAUpdate(&InsertedPHIs);
151 SSAUpdate.Initialize(I->getType(), I->getName());
152
153 // Force re-computation of I, as some users now need to use the new PHI
154 // node.
155 if (SE)
156 SE->forgetValue(I);
157
158 // Insert the LCSSA phi's into all of the exit blocks dominated by the
159 // value, and add them to the Phi's map.
160 for (BasicBlock *ExitBB : ExitBlocks) {
161 if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
162 continue;
163
164 // If we already inserted something for this BB, don't reprocess it.
165 if (SSAUpdate.HasValueForBlock(ExitBB))
166 continue;
167 Builder.SetInsertPoint(&ExitBB->front());
168 PHINode *PN = Builder.CreatePHI(I->getType(), PredCache.size(ExitBB),
169 I->getName() + ".lcssa");
170 // Get the debug location from the original instruction.
171 PN->setDebugLoc(I->getDebugLoc());
172
173 // Add inputs from inside the loop for this PHI. This is valid
174 // because `I` dominates `ExitBB` (checked above). This implies
175 // that every incoming block/edge is dominated by `I` as well,
176 // i.e. we can add uses of `I` to those incoming edges/append to the incoming
177 // blocks without violating the SSA dominance property.
178 for (BasicBlock *Pred : PredCache.get(ExitBB)) {
179 PN->addIncoming(I, Pred);
180
181 // If the exit block has a predecessor not within the loop, arrange for
182 // the incoming value use corresponding to that predecessor to be
183 // rewritten in terms of a different LCSSA PHI.
184 if (!L->contains(Pred))
185 UsesToRewrite.push_back(
187 PN->getNumIncomingValues() - 1)));
188 }
189
190 AddedPHIs.push_back(PN);
191
192 // Remember that this phi makes the value alive in this block.
193 SSAUpdate.AddAvailableValue(ExitBB, PN);
194
195 // LoopSimplify might fail to simplify some loops (e.g. when indirect
196 // branches are involved). In such situations, it might happen that an
197 // exit for Loop L1 is the header of a disjoint Loop L2. Thus, when we
198 // create PHIs in such an exit block, we are also inserting PHIs into L2's
199 // header. This could break LCSSA form for L2 because these inserted PHIs
200 // can also have uses outside of L2. Remember all PHIs in such situation
201 // as to revisit than later on. FIXME: Remove this if indirectbr support
202 // into LoopSimplify gets improved.
203 if (auto *OtherLoop = LI.getLoopFor(ExitBB))
204 if (!L->contains(OtherLoop))
205 PostProcessPHIs.push_back(PN);
206 }
207
208 // Rewrite all uses outside the loop in terms of the new PHIs we just
209 // inserted.
210 for (Use *UseToRewrite : UsesToRewrite) {
211 Instruction *User = cast<Instruction>(UseToRewrite->getUser());
212 BasicBlock *UserBB = User->getParent();
213
214 // For practical purposes, we consider that the use in a PHI
215 // occurs in the respective predecessor block. For more info,
216 // see the `phi` doc in LangRef and the LCSSA doc.
217 if (auto *PN = dyn_cast<PHINode>(User))
218 UserBB = PN->getIncomingBlock(*UseToRewrite);
219
220 // If this use is in an exit block, rewrite to use the newly inserted PHI.
221 // This is required for correctness because SSAUpdate doesn't handle uses
222 // in the same block. It assumes the PHI we inserted is at the end of the
223 // block.
224 if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) {
225 UseToRewrite->set(&UserBB->front());
226 continue;
227 }
228
229 // If we added a single PHI, it must dominate all uses and we can directly
230 // rename it.
231 if (AddedPHIs.size() == 1) {
232 UseToRewrite->set(AddedPHIs[0]);
233 continue;
234 }
235
236 // Otherwise, do full PHI insertion.
237 SSAUpdate.RewriteUse(*UseToRewrite);
238 }
239
241 llvm::findDbgValues(DbgValues, I);
242
243 // Update pre-existing debug value uses that reside outside the loop.
244 for (auto *DVI : DbgValues) {
245 BasicBlock *UserBB = DVI->getParent();
246 if (InstBB == UserBB || L->contains(UserBB))
247 continue;
248 // We currently only handle debug values residing in blocks that were
249 // traversed while rewriting the uses. If we inserted just a single PHI,
250 // we will handle all relevant debug values.
251 Value *V = AddedPHIs.size() == 1 ? AddedPHIs[0]
252 : SSAUpdate.FindValueForBlock(UserBB);
253 if (V)
254 DVI->replaceVariableLocationOp(I, V);
255 }
256
257 // SSAUpdater might have inserted phi-nodes inside other loops. We'll need
258 // to post-process them to keep LCSSA form.
259 for (PHINode *InsertedPN : InsertedPHIs) {
260 if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent()))
261 if (!L->contains(OtherLoop))
262 PostProcessPHIs.push_back(InsertedPN);
263 }
264
265 // Post process PHI instructions that were inserted into another disjoint
266 // loop and update their exits properly.
267 for (auto *PostProcessPN : PostProcessPHIs)
268 if (!PostProcessPN->use_empty())
269 Worklist.push_back(PostProcessPN);
270
271 // Keep track of PHI nodes that we want to remove because they did not have
272 // any uses rewritten.
273 for (PHINode *PN : AddedPHIs)
274 if (PN->use_empty())
275 LocalPHIsToRemove.insert(PN);
276
277 Changed = true;
278 }
279
280 // Remove PHI nodes that did not have any uses rewritten or add them to
281 // PHIsToRemove, so the caller can remove them after some additional cleanup.
282 // We need to redo the use_empty() check here, because even if the PHI node
283 // wasn't used when added to LocalPHIsToRemove, later added PHI nodes can be
284 // using it. This cleanup is not guaranteed to handle trees/cycles of PHI
285 // nodes that only are used by each other. Such situations has only been
286 // noticed when the input IR contains unreachable code, and leaving some extra
287 // redundant PHI nodes in such situations is considered a minor problem.
288 if (PHIsToRemove) {
289 PHIsToRemove->append(LocalPHIsToRemove.begin(), LocalPHIsToRemove.end());
290 } else {
291 for (PHINode *PN : LocalPHIsToRemove)
292 if (PN->use_empty())
293 PN->eraseFromParent();
294 }
295 return Changed;
296}
297
298// Compute the set of BasicBlocks in the loop `L` dominating at least one exit.
300 Loop &L, const DominatorTree &DT, SmallVector<BasicBlock *, 8> &ExitBlocks,
301 SmallSetVector<BasicBlock *, 8> &BlocksDominatingExits) {
302 // We start from the exit blocks, as every block trivially dominates itself
303 // (not strictly).
304 SmallVector<BasicBlock *, 8> BBWorklist(ExitBlocks);
305
306 while (!BBWorklist.empty()) {
307 BasicBlock *BB = BBWorklist.pop_back_val();
308
309 // Check if this is a loop header. If this is the case, we're done.
310 if (L.getHeader() == BB)
311 continue;
312
313 // Otherwise, add its immediate predecessor in the dominator tree to the
314 // worklist, unless we visited it already.
315 BasicBlock *IDomBB = DT.getNode(BB)->getIDom()->getBlock();
316
317 // Exit blocks can have an immediate dominator not belonging to the
318 // loop. For an exit block to be immediately dominated by another block
319 // outside the loop, it implies not all paths from that dominator, to the
320 // exit block, go through the loop.
321 // Example:
322 //
323 // |---- A
324 // | |
325 // | B<--
326 // | | |
327 // |---> C --
328 // |
329 // D
330 //
331 // C is the exit block of the loop and it's immediately dominated by A,
332 // which doesn't belong to the loop.
333 if (!L.contains(IDomBB))
334 continue;
335
336 if (BlocksDominatingExits.insert(IDomBB))
337 BBWorklist.push_back(IDomBB);
338 }
339}
340
341bool llvm::formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
342 ScalarEvolution *SE) {
343 bool Changed = false;
344
345#ifdef EXPENSIVE_CHECKS
346 // Verify all sub-loops are in LCSSA form already.
347 for (Loop *SubLoop: L) {
348 (void)SubLoop; // Silence unused variable warning.
349 assert(SubLoop->isRecursivelyLCSSAForm(DT, *LI) && "Subloop not in LCSSA!");
350 }
351#endif
352
354 L.getExitBlocks(ExitBlocks);
355 if (ExitBlocks.empty())
356 return false;
357
358 SmallSetVector<BasicBlock *, 8> BlocksDominatingExits;
359
360 // We want to avoid use-scanning leveraging dominance informations.
361 // If a block doesn't dominate any of the loop exits, the none of the values
362 // defined in the loop can be used outside.
363 // We compute the set of blocks fullfilling the conditions in advance
364 // walking the dominator tree upwards until we hit a loop header.
365 computeBlocksDominatingExits(L, DT, ExitBlocks, BlocksDominatingExits);
366
368
369 // Look at all the instructions in the loop, checking to see if they have uses
370 // outside the loop. If so, put them into the worklist to rewrite those uses.
371 for (BasicBlock *BB : BlocksDominatingExits) {
372 // Skip blocks that are part of any sub-loops, they must be in LCSSA
373 // already.
374 if (LI->getLoopFor(BB) != &L)
375 continue;
376 for (Instruction &I : *BB) {
377 // Reject two common cases fast: instructions with no uses (like stores)
378 // and instructions with one use that is in the same block as this.
379 if (I.use_empty() ||
380 (I.hasOneUse() && I.user_back()->getParent() == BB &&
381 !isa<PHINode>(I.user_back())))
382 continue;
383
384 // Tokens cannot be used in PHI nodes, so we skip over them.
385 // We can run into tokens which are live out of a loop with catchswitch
386 // instructions in Windows EH if the catchswitch has one catchpad which
387 // is inside the loop and another which is not.
388 if (I.getType()->isTokenTy())
389 continue;
390
391 Worklist.push_back(&I);
392 }
393 }
394
396 Changed = formLCSSAForInstructions(Worklist, DT, *LI, SE, Builder);
397
398 // If we modified the code, remove any caches about the loop from SCEV to
399 // avoid dangling entries.
400 // FIXME: This is a big hammer, can we clear the cache more selectively?
401 if (SE && Changed)
402 SE->forgetLoop(&L);
403
404 assert(L.isLCSSAForm(DT));
405
406 return Changed;
407}
408
409/// Process a loop nest depth first.
411 const LoopInfo *LI, ScalarEvolution *SE) {
412 bool Changed = false;
413
414 // Recurse depth-first through inner loops.
415 for (Loop *SubLoop : L.getSubLoops())
416 Changed |= formLCSSARecursively(*SubLoop, DT, LI, SE);
417
418 Changed |= formLCSSA(L, DT, LI, SE);
419 return Changed;
420}
421
422/// Process all loops in the function, inner-most out.
423static bool formLCSSAOnAllLoops(const LoopInfo *LI, const DominatorTree &DT,
424 ScalarEvolution *SE) {
425 bool Changed = false;
426 for (const auto &L : *LI)
427 Changed |= formLCSSARecursively(*L, DT, LI, SE);
428 return Changed;
429}
430
431namespace {
432struct LCSSAWrapperPass : public FunctionPass {
433 static char ID; // Pass identification, replacement for typeid
434 LCSSAWrapperPass() : FunctionPass(ID) {
436 }
437
438 // Cached analysis information for the current function.
439 DominatorTree *DT;
440 LoopInfo *LI;
441 ScalarEvolution *SE;
442
443 bool runOnFunction(Function &F) override;
444 void verifyAnalysis() const override {
445 // This check is very expensive. On the loop intensive compiles it may cause
446 // up to 10x slowdown. Currently it's disabled by default. LPPassManager
447 // always does limited form of the LCSSA verification. Similar reasoning
448 // was used for the LoopInfo verifier.
449 if (VerifyLoopLCSSA) {
450 assert(all_of(*LI,
451 [&](Loop *L) {
452 return L->isRecursivelyLCSSAForm(*DT, *LI);
453 }) &&
454 "LCSSA form is broken!");
455 }
456 };
457
458 /// This transformation requires natural loop information & requires that
459 /// loop preheaders be inserted into the CFG. It maintains both of these,
460 /// as well as the CFG. It also requires dominator information.
461 void getAnalysisUsage(AnalysisUsage &AU) const override {
462 AU.setPreservesCFG();
463
474
475 // This is needed to perform LCSSA verification inside LPPassManager
478 }
479};
480}
481
482char LCSSAWrapperPass::ID = 0;
483INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
484 false, false)
488INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
490
491Pass *llvm::createLCSSAPass() { return new LCSSAWrapperPass(); }
492char &llvm::LCSSAID = LCSSAWrapperPass::ID;
493
494/// Transform \p F into loop-closed SSA form.
495bool LCSSAWrapperPass::runOnFunction(Function &F) {
496 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
497 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
498 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
499 SE = SEWP ? &SEWP->getSE() : nullptr;
500
501 return formLCSSAOnAllLoops(LI, *DT, SE);
502}
503
505 auto &LI = AM.getResult<LoopAnalysis>(F);
506 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
508 if (!formLCSSAOnAllLoops(&LI, DT, SE))
509 return PreservedAnalyses::all();
510
514 // BPI maps terminators to probabilities, since we don't modify the CFG, no
515 // updates are needed to preserve it.
518 return PA;
519}
assume Assume Builder
This is the interface for LLVM's primary stateless and local alias analysis.
This is the interface for a simple mod/ref and alias analysis over globals.
lcssa
Definition: LCSSA.cpp:488
static bool isExitBlock(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &ExitBlocks)
Return true if the specified block is in the list.
Definition: LCSSA.cpp:70
static bool VerifyLoopLCSSA
Definition: LCSSA.cpp:62
static bool formLCSSAOnAllLoops(const LoopInfo *LI, const DominatorTree &DT, ScalarEvolution *SE)
Process all loops in the function, inner-most out.
Definition: LCSSA.cpp:423
static void computeBlocksDominatingExits(Loop &L, const DominatorTree &DT, SmallVector< BasicBlock *, 8 > &ExitBlocks, SmallSetVector< BasicBlock *, 8 > &BlocksDominatingExits)
Definition: LCSSA.cpp:299
static cl::opt< bool, true > VerifyLoopLCSSAFlag("verify-loop-lcssa", cl::location(VerifyLoopLCSSA), cl::Hidden, cl::desc("Verify loop lcssa form (time consuming)"))
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Memory SSA
Definition: MemorySSA.cpp:71
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This is the interface for a SCEV-based alias analysis.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:793
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Represent the analysis usage information of a pass.
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
Legacy wrapper pass to provide the BasicAAResult object.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:314
const Instruction & front() const
Definition: BasicBlock.h:326
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
Analysis pass which computes BranchProbabilityInfo.
Legacy analysis pass which computes BranchProbabilityInfo.
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
DomTreeNodeBase * getIDom() const
NodeT * getBlock() const
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:314
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Legacy wrapper pass to provide the GlobalsAAResult object.
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:94
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2550
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:355
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LCSSA.cpp:504
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1268
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:139
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:64
const std::vector< LoopT * > & getSubLoops() const
Return the loops contained entirely within this loop.
Definition: LoopInfo.h:160
BlockT * getHeader() const
Definition: LoopInfo.h:105
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1293
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens=true) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:462
bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI, bool IgnoreTokens=true) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:469
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:936
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:986
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static unsigned getOperandNumForIncomingValue(unsigned i)
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
virtual void verifyAnalysis() const
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: Pass.cpp:106
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1759
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.
size_t size(BasicBlock *BB) const
ArrayRef< BasicBlock * > get(BasicBlock *BB)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
Legacy wrapper pass to provide the SCEVAAResult object.
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:38
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
Definition: SSAUpdater.cpp:186
Value * FindValueForBlock(BasicBlock *BB) const
Return the value for the specified block if the SSAUpdater has one, otherwise return nullptr.
Definition: SSAUpdater.cpp:65
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
Definition: SSAUpdater.cpp:52
bool HasValueForBlock(BasicBlock *BB) const
Return true if the SSAUpdater already has a value for the specified block.
Definition: SSAUpdater.cpp:61
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Definition: SSAUpdater.cpp:69
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:92
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:301
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
const Use & getOperandUse(unsigned i) const
Definition: User.h:182
LLVM Value Representation.
Definition: Value.h:74
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:465
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1735
Pass * createLCSSAPass()
Definition: LCSSA.cpp:491
void initializeLCSSAWrapperPassPass(PassRegistry &)
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:410
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:721
char & LCSSAID
Definition: LCSSA.cpp:492
char & LoopSimplifyID
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: DebugInfo.cpp:79
bool formLCSSAForInstructions(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, IRBuilderBase &Builder, SmallVectorImpl< PHINode * > *PHIsToRemove=nullptr)
Ensures LCSSA form for every instruction from the Worklist in the scope of innermost containing loop.
Definition: LCSSA.cpp:78
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1869
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Definition: LCSSA.cpp:341