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