LLVM 20.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// Cache the Loop ExitBlocks computed during the analysis. We expect to get a
75// lot of instructions within the same loops, computing the exit blocks is
76// expensive, and we're not mutating the loop structure.
78
79/// For every instruction from the worklist, check to see if it has any uses
80/// that are outside the current loop. If so, insert LCSSA PHI nodes and
81/// rewrite the uses.
82static bool
84 const DominatorTree &DT, const LoopInfo &LI,
86 SmallVectorImpl<PHINode *> *PHIsToRemove,
87 SmallVectorImpl<PHINode *> *InsertedPHIs,
88 LoopExitBlocksTy &LoopExitBlocks) {
89 SmallVector<Use *, 16> UsesToRewrite;
90 SmallSetVector<PHINode *, 16> LocalPHIsToRemove;
91 PredIteratorCache PredCache;
92 bool Changed = false;
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> LocalInsertedPHIs;
150 SSAUpdater SSAUpdate(&LocalInsertedPHIs);
151 SSAUpdate.Initialize(I->getType(), I->getName());
152
153 // Insert the LCSSA phi's into all of the exit blocks dominated by the
154 // value, and add them to the Phi's map.
155 bool HasSCEV = SE && SE->isSCEVable(I->getType()) &&
156 SE->getExistingSCEV(I) != nullptr;
157 for (BasicBlock *ExitBB : ExitBlocks) {
158 if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
159 continue;
160
161 // If we already inserted something for this BB, don't reprocess it.
162 if (SSAUpdate.HasValueForBlock(ExitBB))
163 continue;
164 PHINode *PN = PHINode::Create(I->getType(), PredCache.size(ExitBB),
165 I->getName() + ".lcssa");
166 PN->insertBefore(ExitBB->begin());
167 if (InsertedPHIs)
168 InsertedPHIs->push_back(PN);
169 // Get the debug location from the original instruction.
170 PN->setDebugLoc(I->getDebugLoc());
171
172 // Add inputs from inside the loop for this PHI. This is valid
173 // because `I` dominates `ExitBB` (checked above). This implies
174 // that every incoming block/edge is dominated by `I` as well,
175 // i.e. we can add uses of `I` to those incoming edges/append to the incoming
176 // blocks without violating the SSA dominance property.
177 for (BasicBlock *Pred : PredCache.get(ExitBB)) {
178 PN->addIncoming(I, Pred);
179
180 // If the exit block has a predecessor not within the loop, arrange for
181 // the incoming value use corresponding to that predecessor to be
182 // rewritten in terms of a different LCSSA PHI.
183 if (!L->contains(Pred))
184 UsesToRewrite.push_back(
186 PN->getNumIncomingValues() - 1)));
187 }
188
189 AddedPHIs.push_back(PN);
190
191 // Remember that this phi makes the value alive in this block.
192 SSAUpdate.AddAvailableValue(ExitBB, PN);
193
194 // LoopSimplify might fail to simplify some loops (e.g. when indirect
195 // branches are involved). In such situations, it might happen that an
196 // exit for Loop L1 is the header of a disjoint Loop L2. Thus, when we
197 // create PHIs in such an exit block, we are also inserting PHIs into L2's
198 // header. This could break LCSSA form for L2 because these inserted PHIs
199 // can also have uses outside of L2. Remember all PHIs in such situation
200 // as to revisit than later on. FIXME: Remove this if indirectbr support
201 // into LoopSimplify gets improved.
202 if (auto *OtherLoop = LI.getLoopFor(ExitBB))
203 if (!L->contains(OtherLoop))
204 PostProcessPHIs.push_back(PN);
205
206 // If we have a cached SCEV for the original instruction, make sure the
207 // new LCSSA phi node is also cached. This makes sures that BECounts
208 // based on it will be invalidated when the LCSSA phi node is invalidated,
209 // which some passes rely on.
210 if (HasSCEV)
211 SE->getSCEV(PN);
212 }
213
214 // Rewrite all uses outside the loop in terms of the new PHIs we just
215 // inserted.
216 for (Use *UseToRewrite : UsesToRewrite) {
217 Instruction *User = cast<Instruction>(UseToRewrite->getUser());
218 BasicBlock *UserBB = User->getParent();
219
220 // For practical purposes, we consider that the use in a PHI
221 // occurs in the respective predecessor block. For more info,
222 // see the `phi` doc in LangRef and the LCSSA doc.
223 if (auto *PN = dyn_cast<PHINode>(User))
224 UserBB = PN->getIncomingBlock(*UseToRewrite);
225
226 // If this use is in an exit block, rewrite to use the newly inserted PHI.
227 // This is required for correctness because SSAUpdate doesn't handle uses
228 // in the same block. It assumes the PHI we inserted is at the end of the
229 // block.
230 if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) {
231 UseToRewrite->set(&UserBB->front());
232 continue;
233 }
234
235 // If we added a single PHI, it must dominate all uses and we can directly
236 // rename it.
237 if (AddedPHIs.size() == 1) {
238 UseToRewrite->set(AddedPHIs[0]);
239 continue;
240 }
241
242 // Otherwise, do full PHI insertion.
243 SSAUpdate.RewriteUse(*UseToRewrite);
244 }
245
247 SmallVector<DbgVariableRecord *, 4> DbgVariableRecords;
248 llvm::findDbgValues(DbgValues, I, &DbgVariableRecords);
249
250 // Update pre-existing debug value uses that reside outside the loop.
251 for (auto *DVI : DbgValues) {
252 BasicBlock *UserBB = DVI->getParent();
253 if (InstBB == UserBB || L->contains(UserBB))
254 continue;
255 // We currently only handle debug values residing in blocks that were
256 // traversed while rewriting the uses. If we inserted just a single PHI,
257 // we will handle all relevant debug values.
258 Value *V = AddedPHIs.size() == 1 ? AddedPHIs[0]
259 : SSAUpdate.FindValueForBlock(UserBB);
260 if (V)
261 DVI->replaceVariableLocationOp(I, V);
262 }
263
264 // RemoveDIs: copy-paste of block above, using non-instruction debug-info
265 // records.
266 for (DbgVariableRecord *DVR : DbgVariableRecords) {
267 BasicBlock *UserBB = DVR->getMarker()->getParent();
268 if (InstBB == UserBB || L->contains(UserBB))
269 continue;
270 // We currently only handle debug values residing in blocks that were
271 // traversed while rewriting the uses. If we inserted just a single PHI,
272 // we will handle all relevant debug values.
273 Value *V = AddedPHIs.size() == 1 ? AddedPHIs[0]
274 : SSAUpdate.FindValueForBlock(UserBB);
275 if (V)
276 DVR->replaceVariableLocationOp(I, V);
277 }
278
279 // SSAUpdater might have inserted phi-nodes inside other loops. We'll need
280 // to post-process them to keep LCSSA form.
281 for (PHINode *InsertedPN : LocalInsertedPHIs) {
282 if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent()))
283 if (!L->contains(OtherLoop))
284 PostProcessPHIs.push_back(InsertedPN);
285 if (InsertedPHIs)
286 InsertedPHIs->push_back(InsertedPN);
287 }
288
289 // Post process PHI instructions that were inserted into another disjoint
290 // loop and update their exits properly.
291 for (auto *PostProcessPN : PostProcessPHIs)
292 if (!PostProcessPN->use_empty())
293 Worklist.push_back(PostProcessPN);
294
295 // Keep track of PHI nodes that we want to remove because they did not have
296 // any uses rewritten.
297 for (PHINode *PN : AddedPHIs)
298 if (PN->use_empty())
299 LocalPHIsToRemove.insert(PN);
300
301 Changed = true;
302 }
303
304 // Remove PHI nodes that did not have any uses rewritten or add them to
305 // PHIsToRemove, so the caller can remove them after some additional cleanup.
306 // We need to redo the use_empty() check here, because even if the PHI node
307 // wasn't used when added to LocalPHIsToRemove, later added PHI nodes can be
308 // using it. This cleanup is not guaranteed to handle trees/cycles of PHI
309 // nodes that only are used by each other. Such situations has only been
310 // noticed when the input IR contains unreachable code, and leaving some extra
311 // redundant PHI nodes in such situations is considered a minor problem.
312 if (PHIsToRemove) {
313 PHIsToRemove->append(LocalPHIsToRemove.begin(), LocalPHIsToRemove.end());
314 } else {
315 for (PHINode *PN : LocalPHIsToRemove)
316 if (PN->use_empty())
317 PN->eraseFromParent();
318 }
319 return Changed;
320}
321
322/// For every instruction from the worklist, check to see if it has any uses
323/// that are outside the current loop. If so, insert LCSSA PHI nodes and
324/// rewrite the uses.
326 const DominatorTree &DT, const LoopInfo &LI,
327 ScalarEvolution *SE,
328 SmallVectorImpl<PHINode *> *PHIsToRemove,
329 SmallVectorImpl<PHINode *> *InsertedPHIs) {
330 LoopExitBlocksTy LoopExitBlocks;
331
332 return formLCSSAForInstructionsImpl(Worklist, DT, LI, SE, PHIsToRemove,
333 InsertedPHIs, LoopExitBlocks);
334}
335
336// Compute the set of BasicBlocks in the loop `L` dominating at least one exit.
338 Loop &L, const DominatorTree &DT, ArrayRef<BasicBlock *> ExitBlocks,
339 SmallSetVector<BasicBlock *, 8> &BlocksDominatingExits) {
340 // We start from the exit blocks, as every block trivially dominates itself
341 // (not strictly).
342 SmallVector<BasicBlock *, 8> BBWorklist(ExitBlocks);
343
344 while (!BBWorklist.empty()) {
345 BasicBlock *BB = BBWorklist.pop_back_val();
346
347 // Check if this is a loop header. If this is the case, we're done.
348 if (L.getHeader() == BB)
349 continue;
350
351 // Otherwise, add its immediate predecessor in the dominator tree to the
352 // worklist, unless we visited it already.
353 BasicBlock *IDomBB = DT.getNode(BB)->getIDom()->getBlock();
354
355 // Exit blocks can have an immediate dominator not belonging to the
356 // loop. For an exit block to be immediately dominated by another block
357 // outside the loop, it implies not all paths from that dominator, to the
358 // exit block, go through the loop.
359 // Example:
360 //
361 // |---- A
362 // | |
363 // | B<--
364 // | | |
365 // |---> C --
366 // |
367 // D
368 //
369 // C is the exit block of the loop and it's immediately dominated by A,
370 // which doesn't belong to the loop.
371 if (!L.contains(IDomBB))
372 continue;
373
374 if (BlocksDominatingExits.insert(IDomBB))
375 BBWorklist.push_back(IDomBB);
376 }
377}
378
379static bool formLCSSAImpl(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
380 ScalarEvolution *SE,
381 LoopExitBlocksTy &LoopExitBlocks) {
382 bool Changed = false;
383
384#ifdef EXPENSIVE_CHECKS
385 // Verify all sub-loops are in LCSSA form already.
386 for (Loop *SubLoop: L) {
387 (void)SubLoop; // Silence unused variable warning.
388 assert(SubLoop->isRecursivelyLCSSAForm(DT, *LI) && "Subloop not in LCSSA!");
389 }
390#endif
391
392 if (!LoopExitBlocks.count(&L))
393 L.getExitBlocks(LoopExitBlocks[&L]);
394 const SmallVectorImpl<BasicBlock *> &ExitBlocks = LoopExitBlocks[&L];
395 if (ExitBlocks.empty())
396 return false;
397
398 SmallSetVector<BasicBlock *, 8> BlocksDominatingExits;
399
400 // We want to avoid use-scanning leveraging dominance informations.
401 // If a block doesn't dominate any of the loop exits, the none of the values
402 // defined in the loop can be used outside.
403 // We compute the set of blocks fullfilling the conditions in advance
404 // walking the dominator tree upwards until we hit a loop header.
405 computeBlocksDominatingExits(L, DT, ExitBlocks, BlocksDominatingExits);
406
408
409 // Look at all the instructions in the loop, checking to see if they have uses
410 // outside the loop. If so, put them into the worklist to rewrite those uses.
411 for (BasicBlock *BB : BlocksDominatingExits) {
412 // Skip blocks that are part of any sub-loops, they must be in LCSSA
413 // already.
414 if (LI->getLoopFor(BB) != &L)
415 continue;
416 for (Instruction &I : *BB) {
417 // Reject two common cases fast: instructions with no uses (like stores)
418 // and instructions with one use that is in the same block as this.
419 if (I.use_empty() ||
420 (I.hasOneUse() && I.user_back()->getParent() == BB &&
421 !isa<PHINode>(I.user_back())))
422 continue;
423
424 // Tokens cannot be used in PHI nodes, so we skip over them.
425 // We can run into tokens which are live out of a loop with catchswitch
426 // instructions in Windows EH if the catchswitch has one catchpad which
427 // is inside the loop and another which is not.
428 if (I.getType()->isTokenTy())
429 continue;
430
431 Worklist.push_back(&I);
432 }
433 }
434
435 Changed = formLCSSAForInstructionsImpl(Worklist, DT, *LI, SE, nullptr,
436 nullptr, LoopExitBlocks);
437
438 assert(L.isLCSSAForm(DT));
439
440 return Changed;
441}
442
443bool llvm::formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
444 ScalarEvolution *SE) {
445 LoopExitBlocksTy LoopExitBlocks;
446
447 return formLCSSAImpl(L, DT, LI, SE, LoopExitBlocks);
448}
449
450/// Process a loop nest depth first.
452 const LoopInfo *LI, ScalarEvolution *SE,
453 LoopExitBlocksTy &LoopExitBlocks) {
454 bool Changed = false;
455
456 // Recurse depth-first through inner loops.
457 for (Loop *SubLoop : L.getSubLoops())
458 Changed |= formLCSSARecursivelyImpl(*SubLoop, DT, LI, SE, LoopExitBlocks);
459
460 Changed |= formLCSSAImpl(L, DT, LI, SE, LoopExitBlocks);
461 return Changed;
462}
463
464/// Process a loop nest depth first.
466 const LoopInfo *LI, ScalarEvolution *SE) {
467 LoopExitBlocksTy LoopExitBlocks;
468
469 return formLCSSARecursivelyImpl(L, DT, LI, SE, LoopExitBlocks);
470}
471
472/// Process all loops in the function, inner-most out.
473static bool formLCSSAOnAllLoops(const LoopInfo *LI, const DominatorTree &DT,
474 ScalarEvolution *SE) {
475 bool Changed = false;
476 for (const auto &L : *LI)
477 Changed |= formLCSSARecursively(*L, DT, LI, SE);
478 return Changed;
479}
480
481namespace {
482struct LCSSAWrapperPass : public FunctionPass {
483 static char ID; // Pass identification, replacement for typeid
484 LCSSAWrapperPass() : FunctionPass(ID) {
486 }
487
488 // Cached analysis information for the current function.
489 DominatorTree *DT;
490 LoopInfo *LI;
491 ScalarEvolution *SE;
492
493 bool runOnFunction(Function &F) override;
494 void verifyAnalysis() const override {
495 // This check is very expensive. On the loop intensive compiles it may cause
496 // up to 10x slowdown. Currently it's disabled by default. LPPassManager
497 // always does limited form of the LCSSA verification. Similar reasoning
498 // was used for the LoopInfo verifier.
499 if (VerifyLoopLCSSA) {
500 assert(all_of(*LI,
501 [&](Loop *L) {
502 return L->isRecursivelyLCSSAForm(*DT, *LI);
503 }) &&
504 "LCSSA form is broken!");
505 }
506 };
507
508 /// This transformation requires natural loop information & requires that
509 /// loop preheaders be inserted into the CFG. It maintains both of these,
510 /// as well as the CFG. It also requires dominator information.
511 void getAnalysisUsage(AnalysisUsage &AU) const override {
512 AU.setPreservesCFG();
513
524
525 // This is needed to perform LCSSA verification inside LPPassManager
528 }
529};
530}
531
532char LCSSAWrapperPass::ID = 0;
533INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
534 false, false)
538INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
540
541Pass *llvm::createLCSSAPass() { return new LCSSAWrapperPass(); }
542char &llvm::LCSSAID = LCSSAWrapperPass::ID;
543
544/// Transform \p F into loop-closed SSA form.
545bool LCSSAWrapperPass::runOnFunction(Function &F) {
546 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
547 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
548 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
549 SE = SEWP ? &SEWP->getSE() : nullptr;
550
551 return formLCSSAOnAllLoops(LI, *DT, SE);
552}
553
555 auto &LI = AM.getResult<LoopAnalysis>(F);
556 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
558 if (!formLCSSAOnAllLoops(&LI, DT, SE))
559 return PreservedAnalyses::all();
560
564 // BPI maps terminators to probabilities, since we don't modify the CFG, no
565 // updates are needed to preserve it.
568 return PA;
569}
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.
static bool formLCSSAForInstructionsImpl(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *PHIsToRemove, SmallVectorImpl< PHINode * > *InsertedPHIs, LoopExitBlocksTy &LoopExitBlocks)
For every instruction from the worklist, check to see if it has any uses that are outside the current...
Definition: LCSSA.cpp:83
lcssa
Definition: LCSSA.cpp:538
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 formLCSSAImpl(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE, LoopExitBlocksTy &LoopExitBlocks)
Definition: LCSSA.cpp:379
static bool formLCSSAOnAllLoops(const LoopInfo *LI, const DominatorTree &DT, ScalarEvolution *SE)
Process all loops in the function, inner-most out.
Definition: LCSSA.cpp:473
static void computeBlocksDominatingExits(Loop &L, const DominatorTree &DT, ArrayRef< BasicBlock * > ExitBlocks, SmallSetVector< BasicBlock *, 8 > &BlocksDominatingExits)
Definition: LCSSA.cpp:337
static bool formLCSSARecursivelyImpl(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE, LoopExitBlocksTy &LoopExitBlocks)
Process a loop nest depth first.
Definition: LCSSA.cpp:451
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:57
#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:253
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:424
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:405
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:256
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
Legacy wrapper pass to provide the BasicAAResult object.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:448
const Instruction & front() const
Definition: BasicBlock.h:471
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:219
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:72
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:310
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.
Definition: Instruction.cpp:97
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:463
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LCSSA.cpp:554
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:571
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:598
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 unsigned getOperandNumForIncomingValue(unsigned i)
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
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:1852
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.
size_t size(BasicBlock *BB)
ArrayRef< BasicBlock * > get(BasicBlock *BB)
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:146
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:131
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:95
size_t size() const
Definition: SmallVector.h:92
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:587
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:697
void push_back(const T &Elt)
Definition: SmallVector.h:427
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
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:463
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:541
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:465
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:542
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:325
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:443