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
245 SmallVector<DbgVariableRecord *, 4> DbgVariableRecords;
246 llvm::findDbgValues(DbgValues, I, &DbgVariableRecords);
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 (DbgVariableRecord *DVR : DbgVariableRecords) {
265 BasicBlock *UserBB = DVR->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 DVR->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:72
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:321
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:492
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:473
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
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:430
const Instruction & front() const
Definition: BasicBlock.h:453
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:206
DbgMarker * getMarker(InstListType::iterator It)
Return the DbgMarker for the position given by It, so that DbgRecords can be inserted there.
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: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:317
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:451
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:928
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:985
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:1814
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:1722
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:656
char & LCSSAID
Definition: LCSSA.cpp:507
char & LoopSimplifyID
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: DebugInfo.cpp:138
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:1879
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Definition: LCSSA.cpp:363