LLVM 18.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"
47#include "llvm/Pass.h"
52using namespace llvm;
53
54#define DEBUG_TYPE "lcssa"
55
56STATISTIC(NumLCSSA, "Number of live out of a loop variables");
57
58#ifdef EXPENSIVE_CHECKS
59static bool VerifyLoopLCSSA = true;
60#else
61static bool VerifyLoopLCSSA = false;
62#endif
66 cl::desc("Verify loop lcssa form (time consuming)"));
67
68/// Return true if the specified block is in the list.
69static 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.
78 const DominatorTree &DT, const LoopInfo &LI,
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.
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
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", &ExitBB->front());
164 if (InsertedPHIs)
165 InsertedPHIs->push_back(PN);
166 // Get the debug location from the original instruction.
167 PN->setDebugLoc(I->getDebugLoc());
168
169 // Add inputs from inside the loop for this PHI. This is valid
170 // because `I` dominates `ExitBB` (checked above). This implies
171 // that every incoming block/edge is dominated by `I` as well,
172 // i.e. we can add uses of `I` to those incoming edges/append to the incoming
173 // blocks without violating the SSA dominance property.
174 for (BasicBlock *Pred : PredCache.get(ExitBB)) {
175 PN->addIncoming(I, Pred);
176
177 // If the exit block has a predecessor not within the loop, arrange for
178 // the incoming value use corresponding to that predecessor to be
179 // rewritten in terms of a different LCSSA PHI.
180 if (!L->contains(Pred))
181 UsesToRewrite.push_back(
183 PN->getNumIncomingValues() - 1)));
184 }
185
186 AddedPHIs.push_back(PN);
187
188 // Remember that this phi makes the value alive in this block.
189 SSAUpdate.AddAvailableValue(ExitBB, PN);
190
191 // LoopSimplify might fail to simplify some loops (e.g. when indirect
192 // branches are involved). In such situations, it might happen that an
193 // exit for Loop L1 is the header of a disjoint Loop L2. Thus, when we
194 // create PHIs in such an exit block, we are also inserting PHIs into L2's
195 // header. This could break LCSSA form for L2 because these inserted PHIs
196 // can also have uses outside of L2. Remember all PHIs in such situation
197 // as to revisit than later on. FIXME: Remove this if indirectbr support
198 // into LoopSimplify gets improved.
199 if (auto *OtherLoop = LI.getLoopFor(ExitBB))
200 if (!L->contains(OtherLoop))
201 PostProcessPHIs.push_back(PN);
202
203 // If we have a cached SCEV for the original instruction, make sure the
204 // new LCSSA phi node is also cached. This makes sures that BECounts
205 // based on it will be invalidated when the LCSSA phi node is invalidated,
206 // which some passes rely on.
207 if (HasSCEV)
208 SE->getSCEV(PN);
209 }
210
211 // Rewrite all uses outside the loop in terms of the new PHIs we just
212 // inserted.
213 for (Use *UseToRewrite : UsesToRewrite) {
214 Instruction *User = cast<Instruction>(UseToRewrite->getUser());
215 BasicBlock *UserBB = User->getParent();
216
217 // For practical purposes, we consider that the use in a PHI
218 // occurs in the respective predecessor block. For more info,
219 // see the `phi` doc in LangRef and the LCSSA doc.
220 if (auto *PN = dyn_cast<PHINode>(User))
221 UserBB = PN->getIncomingBlock(*UseToRewrite);
222
223 // If this use is in an exit block, rewrite to use the newly inserted PHI.
224 // This is required for correctness because SSAUpdate doesn't handle uses
225 // in the same block. It assumes the PHI we inserted is at the end of the
226 // block.
227 if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) {
228 UseToRewrite->set(&UserBB->front());
229 continue;
230 }
231
232 // If we added a single PHI, it must dominate all uses and we can directly
233 // rename it.
234 if (AddedPHIs.size() == 1) {
235 UseToRewrite->set(AddedPHIs[0]);
236 continue;
237 }
238
239 // Otherwise, do full PHI insertion.
240 SSAUpdate.RewriteUse(*UseToRewrite);
241 }
242
244 llvm::findDbgValues(DbgValues, I);
245
246 // Update pre-existing debug value uses that reside outside the loop.
247 for (auto *DVI : DbgValues) {
248 BasicBlock *UserBB = DVI->getParent();
249 if (InstBB == UserBB || L->contains(UserBB))
250 continue;
251 // We currently only handle debug values residing in blocks that were
252 // traversed while rewriting the uses. If we inserted just a single PHI,
253 // we will handle all relevant debug values.
254 Value *V = AddedPHIs.size() == 1 ? AddedPHIs[0]
255 : SSAUpdate.FindValueForBlock(UserBB);
256 if (V)
257 DVI->replaceVariableLocationOp(I, V);
258 }
259
260 // SSAUpdater might have inserted phi-nodes inside other loops. We'll need
261 // to post-process them to keep LCSSA form.
262 for (PHINode *InsertedPN : LocalInsertedPHIs) {
263 if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent()))
264 if (!L->contains(OtherLoop))
265 PostProcessPHIs.push_back(InsertedPN);
266 if (InsertedPHIs)
267 InsertedPHIs->push_back(InsertedPN);
268 }
269
270 // Post process PHI instructions that were inserted into another disjoint
271 // loop and update their exits properly.
272 for (auto *PostProcessPN : PostProcessPHIs)
273 if (!PostProcessPN->use_empty())
274 Worklist.push_back(PostProcessPN);
275
276 // Keep track of PHI nodes that we want to remove because they did not have
277 // any uses rewritten.
278 for (PHINode *PN : AddedPHIs)
279 if (PN->use_empty())
280 LocalPHIsToRemove.insert(PN);
281
282 Changed = true;
283 }
284
285 // Remove PHI nodes that did not have any uses rewritten or add them to
286 // PHIsToRemove, so the caller can remove them after some additional cleanup.
287 // We need to redo the use_empty() check here, because even if the PHI node
288 // wasn't used when added to LocalPHIsToRemove, later added PHI nodes can be
289 // using it. This cleanup is not guaranteed to handle trees/cycles of PHI
290 // nodes that only are used by each other. Such situations has only been
291 // noticed when the input IR contains unreachable code, and leaving some extra
292 // redundant PHI nodes in such situations is considered a minor problem.
293 if (PHIsToRemove) {
294 PHIsToRemove->append(LocalPHIsToRemove.begin(), LocalPHIsToRemove.end());
295 } else {
296 for (PHINode *PN : LocalPHIsToRemove)
297 if (PN->use_empty())
298 PN->eraseFromParent();
299 }
300 return Changed;
301}
302
303// Compute the set of BasicBlocks in the loop `L` dominating at least one exit.
305 Loop &L, const DominatorTree &DT, SmallVector<BasicBlock *, 8> &ExitBlocks,
306 SmallSetVector<BasicBlock *, 8> &BlocksDominatingExits) {
307 // We start from the exit blocks, as every block trivially dominates itself
308 // (not strictly).
309 SmallVector<BasicBlock *, 8> BBWorklist(ExitBlocks);
310
311 while (!BBWorklist.empty()) {
312 BasicBlock *BB = BBWorklist.pop_back_val();
313
314 // Check if this is a loop header. If this is the case, we're done.
315 if (L.getHeader() == BB)
316 continue;
317
318 // Otherwise, add its immediate predecessor in the dominator tree to the
319 // worklist, unless we visited it already.
320 BasicBlock *IDomBB = DT.getNode(BB)->getIDom()->getBlock();
321
322 // Exit blocks can have an immediate dominator not belonging to the
323 // loop. For an exit block to be immediately dominated by another block
324 // outside the loop, it implies not all paths from that dominator, to the
325 // exit block, go through the loop.
326 // Example:
327 //
328 // |---- A
329 // | |
330 // | B<--
331 // | | |
332 // |---> C --
333 // |
334 // D
335 //
336 // C is the exit block of the loop and it's immediately dominated by A,
337 // which doesn't belong to the loop.
338 if (!L.contains(IDomBB))
339 continue;
340
341 if (BlocksDominatingExits.insert(IDomBB))
342 BBWorklist.push_back(IDomBB);
343 }
344}
345
346bool llvm::formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
347 ScalarEvolution *SE) {
348 bool Changed = false;
349
350#ifdef EXPENSIVE_CHECKS
351 // Verify all sub-loops are in LCSSA form already.
352 for (Loop *SubLoop: L) {
353 (void)SubLoop; // Silence unused variable warning.
354 assert(SubLoop->isRecursivelyLCSSAForm(DT, *LI) && "Subloop not in LCSSA!");
355 }
356#endif
357
359 L.getExitBlocks(ExitBlocks);
360 if (ExitBlocks.empty())
361 return false;
362
363 SmallSetVector<BasicBlock *, 8> BlocksDominatingExits;
364
365 // We want to avoid use-scanning leveraging dominance informations.
366 // If a block doesn't dominate any of the loop exits, the none of the values
367 // defined in the loop can be used outside.
368 // We compute the set of blocks fullfilling the conditions in advance
369 // walking the dominator tree upwards until we hit a loop header.
370 computeBlocksDominatingExits(L, DT, ExitBlocks, BlocksDominatingExits);
371
373
374 // Look at all the instructions in the loop, checking to see if they have uses
375 // outside the loop. If so, put them into the worklist to rewrite those uses.
376 for (BasicBlock *BB : BlocksDominatingExits) {
377 // Skip blocks that are part of any sub-loops, they must be in LCSSA
378 // already.
379 if (LI->getLoopFor(BB) != &L)
380 continue;
381 for (Instruction &I : *BB) {
382 // Reject two common cases fast: instructions with no uses (like stores)
383 // and instructions with one use that is in the same block as this.
384 if (I.use_empty() ||
385 (I.hasOneUse() && I.user_back()->getParent() == BB &&
386 !isa<PHINode>(I.user_back())))
387 continue;
388
389 // Tokens cannot be used in PHI nodes, so we skip over them.
390 // We can run into tokens which are live out of a loop with catchswitch
391 // instructions in Windows EH if the catchswitch has one catchpad which
392 // is inside the loop and another which is not.
393 if (I.getType()->isTokenTy())
394 continue;
395
396 Worklist.push_back(&I);
397 }
398 }
399
400 Changed = formLCSSAForInstructions(Worklist, DT, *LI, SE);
401
402 assert(L.isLCSSAForm(DT));
403
404 return Changed;
405}
406
407/// Process a loop nest depth first.
409 const LoopInfo *LI, ScalarEvolution *SE) {
410 bool Changed = false;
411
412 // Recurse depth-first through inner loops.
413 for (Loop *SubLoop : L.getSubLoops())
414 Changed |= formLCSSARecursively(*SubLoop, DT, LI, SE);
415
416 Changed |= formLCSSA(L, DT, LI, SE);
417 return Changed;
418}
419
420/// Process all loops in the function, inner-most out.
421static bool formLCSSAOnAllLoops(const LoopInfo *LI, const DominatorTree &DT,
422 ScalarEvolution *SE) {
423 bool Changed = false;
424 for (const auto &L : *LI)
425 Changed |= formLCSSARecursively(*L, DT, LI, SE);
426 return Changed;
427}
428
429namespace {
430struct LCSSAWrapperPass : public FunctionPass {
431 static char ID; // Pass identification, replacement for typeid
432 LCSSAWrapperPass() : FunctionPass(ID) {
434 }
435
436 // Cached analysis information for the current function.
437 DominatorTree *DT;
438 LoopInfo *LI;
439 ScalarEvolution *SE;
440
441 bool runOnFunction(Function &F) override;
442 void verifyAnalysis() const override {
443 // This check is very expensive. On the loop intensive compiles it may cause
444 // up to 10x slowdown. Currently it's disabled by default. LPPassManager
445 // always does limited form of the LCSSA verification. Similar reasoning
446 // was used for the LoopInfo verifier.
447 if (VerifyLoopLCSSA) {
448 assert(all_of(*LI,
449 [&](Loop *L) {
450 return L->isRecursivelyLCSSAForm(*DT, *LI);
451 }) &&
452 "LCSSA form is broken!");
453 }
454 };
455
456 /// This transformation requires natural loop information & requires that
457 /// loop preheaders be inserted into the CFG. It maintains both of these,
458 /// as well as the CFG. It also requires dominator information.
459 void getAnalysisUsage(AnalysisUsage &AU) const override {
460 AU.setPreservesCFG();
461
472
473 // This is needed to perform LCSSA verification inside LPPassManager
476 }
477};
478}
479
480char LCSSAWrapperPass::ID = 0;
481INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
482 false, false)
486INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
488
489Pass *llvm::createLCSSAPass() { return new LCSSAWrapperPass(); }
490char &llvm::LCSSAID = LCSSAWrapperPass::ID;
491
492/// Transform \p F into loop-closed SSA form.
493bool LCSSAWrapperPass::runOnFunction(Function &F) {
494 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
495 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
496 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
497 SE = SEWP ? &SEWP->getSE() : nullptr;
498
499 return formLCSSAOnAllLoops(LI, *DT, SE);
500}
501
503 auto &LI = AM.getResult<LoopAnalysis>(F);
504 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
506 if (!formLCSSAOnAllLoops(&LI, DT, SE))
507 return PreservedAnalyses::all();
508
512 // BPI maps terminators to probabilities, since we don't modify the CFG, no
513 // updates are needed to preserve it.
516 return PA;
517}
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:486
static bool isExitBlock(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &ExitBlocks)
Return true if the specified block is in the list.
Definition: LCSSA.cpp:69
static bool VerifyLoopLCSSA
Definition: LCSSA.cpp:61
static bool formLCSSAOnAllLoops(const LoopInfo *LI, const DominatorTree &DT, ScalarEvolution *SE)
Process all loops in the function, inner-most out.
Definition: LCSSA.cpp:421
static void computeBlocksDominatingExits(Loop &L, const DominatorTree &DT, SmallVector< BasicBlock *, 8 > &ExitBlocks, SmallSetVector< BasicBlock *, 8 > &BlocksDominatingExits)
Definition: LCSSA.cpp:304
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:269
Legacy wrapper pass to provide the BasicAAResult object.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:335
const Instruction & front() const
Definition: BasicBlock.h:347
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
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:151
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:321
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:311
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.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:389
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LCSSA.cpp:502
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:569
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:594
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:47
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:923
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:975
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
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:94
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:1743
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:39
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
Definition: SSAUpdater.cpp:188
Value * FindValueForBlock(BasicBlock *BB) const
Return the value for the specified block if the SSAUpdater has one, otherwise return nullptr.
Definition: SSAUpdater.cpp:66
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:53
bool HasValueForBlock(BasicBlock *BB) const
Return true if the SSAUpdater already has a value for the specified block.
Definition: SSAUpdater.cpp:62
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Definition: SSAUpdater.cpp:70
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:113
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:103
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
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:1727
Pass * createLCSSAPass()
Definition: LCSSA.cpp:489
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:408
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:666
char & LCSSAID
Definition: LCSSA.cpp:490
char & LoopSimplifyID
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: DebugInfo.cpp:99
bool formLCSSAForInstructions(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *PHIsToRemove=nullptr, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)
Ensures LCSSA form for every instruction from the Worklist in the scope of innermost containing loop.
Definition: LCSSA.cpp:77
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1884
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Definition: LCSSA.cpp:346