LLVM 19.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");
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(
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
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.
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
363bool 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
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
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.
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.
438static 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
446namespace {
447struct LCSSAWrapperPass : public FunctionPass {
448 static char ID; // Pass identification, replacement for typeid
449 LCSSAWrapperPass() : FunctionPass(ID) {
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
489
490 // This is needed to perform LCSSA verification inside LPPassManager
493 }
494};
495}
496
497char LCSSAWrapperPass::ID = 0;
498INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
499 false, false)
503INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
505
506Pass *llvm::createLCSSAPass() { return new LCSSAWrapperPass(); }
507char &llvm::LCSSAID = LCSSAWrapperPass::ID;
508
509/// Transform \p F into loop-closed SSA form.
510bool 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
520 auto &LI = AM.getResult<LoopAnalysis>(F);
521 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
523 if (!formLCSSAOnAllLoops(&LI, DT, SE))
524 return PreservedAnalyses::all();
525
529 // BPI maps terminators to probabilities, since we don't modify the CFG, no
530 // updates are needed to preserve it.
533 return PA;
534}
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:503
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:438
static void computeBlocksDominatingExits(Loop &L, const DominatorTree &DT, SmallVector< BasicBlock *, 8 > &ExitBlocks, SmallSetVector< BasicBlock *, 8 > &BlocksDominatingExits)
Definition: LCSSA.cpp:321
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:348
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:519
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
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:60
DPMarker * getMarker(InstListType::iterator It)
Return the DPMarker for the position given by It, so that DPValues can be inserted there.
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:429
const Instruction & front() const
Definition: BasicBlock.h:452
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:205
Analysis pass which computes BranchProbabilityInfo.
Legacy analysis pass which computes BranchProbabilityInfo.
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
const BasicBlock * getParent() const
Record of a variable value-assignment, aka a non instruction representation of the dbg....
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:275
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:313
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
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 insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:449
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LCSSA.cpp:519
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:566
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:593
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:923
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:980
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, BasicBlock::iterator InsertBefore)
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:1827
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: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:144
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:129
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:40
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:586
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:696
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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:470
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:1731
Pass * createLCSSAPass()
Definition: LCSSA.cpp:506
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:425
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:665
char & LCSSAID
Definition: LCSSA.cpp:507
char & LoopSimplifyID
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DPValue * > *DPValues=nullptr)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: DebugInfo.cpp:137
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:1888
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Definition: LCSSA.cpp:363