LLVM  15.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 : I->uses()) {
111  Instruction *User = cast<Instruction>(U.getUser());
112  BasicBlock *UserBB = User->getParent();
113 
114  // For practical purposes, we consider that the use in a PHI
115  // occurs in the respective predecessor block. For more info,
116  // see the `phi` doc in LangRef and the LCSSA doc.
117  if (auto *PN = dyn_cast<PHINode>(User))
118  UserBB = PN->getIncomingBlock(U);
119 
120  if (InstBB != UserBB && !L->contains(UserBB))
121  UsesToRewrite.push_back(&U);
122  }
123 
124  // If there are no uses outside the loop, exit with no change.
125  if (UsesToRewrite.empty())
126  continue;
127 
128  ++NumLCSSA; // We are applying the transformation
129 
130  // Invoke instructions are special in that their result value is not
131  // available along their unwind edge. The code below tests to see whether
132  // DomBB dominates the value, so adjust DomBB to the normal destination
133  // block, which is effectively where the value is first usable.
134  BasicBlock *DomBB = InstBB;
135  if (auto *Inv = dyn_cast<InvokeInst>(I))
136  DomBB = Inv->getNormalDest();
137 
138  const DomTreeNode *DomNode = DT.getNode(DomBB);
139 
140  SmallVector<PHINode *, 16> AddedPHIs;
141  SmallVector<PHINode *, 8> PostProcessPHIs;
142 
143  SmallVector<PHINode *, 4> InsertedPHIs;
144  SSAUpdater SSAUpdate(&InsertedPHIs);
145  SSAUpdate.Initialize(I->getType(), I->getName());
146 
147  // Force re-computation of I, as some users now need to use the new PHI
148  // node.
149  if (SE)
150  SE->forgetValue(I);
151 
152  // Insert the LCSSA phi's into all of the exit blocks dominated by the
153  // value, and add them to the Phi's map.
154  for (BasicBlock *ExitBB : ExitBlocks) {
155  if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
156  continue;
157 
158  // If we already inserted something for this BB, don't reprocess it.
159  if (SSAUpdate.HasValueForBlock(ExitBB))
160  continue;
161  Builder.SetInsertPoint(&ExitBB->front());
162  PHINode *PN = Builder.CreatePHI(I->getType(), PredCache.size(ExitBB),
163  I->getName() + ".lcssa");
164  // Get the debug location from the original instruction.
165  PN->setDebugLoc(I->getDebugLoc());
166 
167  // Add inputs from inside the loop for this PHI. This is valid
168  // because `I` dominates `ExitBB` (checked above). This implies
169  // that every incoming block/edge is dominated by `I` as well,
170  // i.e. we can add uses of `I` to those incoming edges/append to the incoming
171  // blocks without violating the SSA dominance property.
172  for (BasicBlock *Pred : PredCache.get(ExitBB)) {
173  PN->addIncoming(I, Pred);
174 
175  // If the exit block has a predecessor not within the loop, arrange for
176  // the incoming value use corresponding to that predecessor to be
177  // rewritten in terms of a different LCSSA PHI.
178  if (!L->contains(Pred))
179  UsesToRewrite.push_back(
181  PN->getNumIncomingValues() - 1)));
182  }
183 
184  AddedPHIs.push_back(PN);
185 
186  // Remember that this phi makes the value alive in this block.
187  SSAUpdate.AddAvailableValue(ExitBB, PN);
188 
189  // LoopSimplify might fail to simplify some loops (e.g. when indirect
190  // branches are involved). In such situations, it might happen that an
191  // exit for Loop L1 is the header of a disjoint Loop L2. Thus, when we
192  // create PHIs in such an exit block, we are also inserting PHIs into L2's
193  // header. This could break LCSSA form for L2 because these inserted PHIs
194  // can also have uses outside of L2. Remember all PHIs in such situation
195  // as to revisit than later on. FIXME: Remove this if indirectbr support
196  // into LoopSimplify gets improved.
197  if (auto *OtherLoop = LI.getLoopFor(ExitBB))
198  if (!L->contains(OtherLoop))
199  PostProcessPHIs.push_back(PN);
200  }
201 
202  // Rewrite all uses outside the loop in terms of the new PHIs we just
203  // inserted.
204  for (Use *UseToRewrite : UsesToRewrite) {
205  Instruction *User = cast<Instruction>(UseToRewrite->getUser());
206  BasicBlock *UserBB = User->getParent();
207 
208  // For practical purposes, we consider that the use in a PHI
209  // occurs in the respective predecessor block. For more info,
210  // see the `phi` doc in LangRef and the LCSSA doc.
211  if (auto *PN = dyn_cast<PHINode>(User))
212  UserBB = PN->getIncomingBlock(*UseToRewrite);
213 
214  // If this use is in an exit block, rewrite to use the newly inserted PHI.
215  // This is required for correctness because SSAUpdate doesn't handle uses
216  // in the same block. It assumes the PHI we inserted is at the end of the
217  // block.
218  if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) {
219  UseToRewrite->set(&UserBB->front());
220  continue;
221  }
222 
223  // If we added a single PHI, it must dominate all uses and we can directly
224  // rename it.
225  if (AddedPHIs.size() == 1) {
226  UseToRewrite->set(AddedPHIs[0]);
227  continue;
228  }
229 
230  // Otherwise, do full PHI insertion.
231  SSAUpdate.RewriteUse(*UseToRewrite);
232  }
233 
235  llvm::findDbgValues(DbgValues, I);
236 
237  // Update pre-existing debug value uses that reside outside the loop.
238  for (auto DVI : DbgValues) {
239  BasicBlock *UserBB = DVI->getParent();
240  if (InstBB == UserBB || L->contains(UserBB))
241  continue;
242  // We currently only handle debug values residing in blocks that were
243  // traversed while rewriting the uses. If we inserted just a single PHI,
244  // we will handle all relevant debug values.
245  Value *V = AddedPHIs.size() == 1 ? AddedPHIs[0]
246  : SSAUpdate.FindValueForBlock(UserBB);
247  if (V)
248  DVI->replaceVariableLocationOp(I, V);
249  }
250 
251  // SSAUpdater might have inserted phi-nodes inside other loops. We'll need
252  // to post-process them to keep LCSSA form.
253  for (PHINode *InsertedPN : InsertedPHIs) {
254  if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent()))
255  if (!L->contains(OtherLoop))
256  PostProcessPHIs.push_back(InsertedPN);
257  }
258 
259  // Post process PHI instructions that were inserted into another disjoint
260  // loop and update their exits properly.
261  for (auto *PostProcessPN : PostProcessPHIs)
262  if (!PostProcessPN->use_empty())
263  Worklist.push_back(PostProcessPN);
264 
265  // Keep track of PHI nodes that we want to remove because they did not have
266  // any uses rewritten.
267  for (PHINode *PN : AddedPHIs)
268  if (PN->use_empty())
269  LocalPHIsToRemove.insert(PN);
270 
271  Changed = true;
272  }
273 
274  // Remove PHI nodes that did not have any uses rewritten or add them to
275  // PHIsToRemove, so the caller can remove them after some additional cleanup.
276  // We need to redo the use_empty() check here, because even if the PHI node
277  // wasn't used when added to LocalPHIsToRemove, later added PHI nodes can be
278  // using it. This cleanup is not guaranteed to handle trees/cycles of PHI
279  // nodes that only are used by each other. Such situations has only been
280  // noticed when the input IR contains unreachable code, and leaving some extra
281  // redundant PHI nodes in such situations is considered a minor problem.
282  if (PHIsToRemove) {
283  PHIsToRemove->append(LocalPHIsToRemove.begin(), LocalPHIsToRemove.end());
284  } else {
285  for (PHINode *PN : LocalPHIsToRemove)
286  if (PN->use_empty())
287  PN->eraseFromParent();
288  }
289  return Changed;
290 }
291 
292 // Compute the set of BasicBlocks in the loop `L` dominating at least one exit.
294  Loop &L, const DominatorTree &DT, SmallVector<BasicBlock *, 8> &ExitBlocks,
295  SmallSetVector<BasicBlock *, 8> &BlocksDominatingExits) {
296  // We start from the exit blocks, as every block trivially dominates itself
297  // (not strictly).
298  SmallVector<BasicBlock *, 8> BBWorklist(ExitBlocks);
299 
300  while (!BBWorklist.empty()) {
301  BasicBlock *BB = BBWorklist.pop_back_val();
302 
303  // Check if this is a loop header. If this is the case, we're done.
304  if (L.getHeader() == BB)
305  continue;
306 
307  // Otherwise, add its immediate predecessor in the dominator tree to the
308  // worklist, unless we visited it already.
309  BasicBlock *IDomBB = DT.getNode(BB)->getIDom()->getBlock();
310 
311  // Exit blocks can have an immediate dominator not belonging to the
312  // loop. For an exit block to be immediately dominated by another block
313  // outside the loop, it implies not all paths from that dominator, to the
314  // exit block, go through the loop.
315  // Example:
316  //
317  // |---- A
318  // | |
319  // | B<--
320  // | | |
321  // |---> C --
322  // |
323  // D
324  //
325  // C is the exit block of the loop and it's immediately dominated by A,
326  // which doesn't belong to the loop.
327  if (!L.contains(IDomBB))
328  continue;
329 
330  if (BlocksDominatingExits.insert(IDomBB))
331  BBWorklist.push_back(IDomBB);
332  }
333 }
334 
335 bool llvm::formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
336  ScalarEvolution *SE) {
337  bool Changed = false;
338 
339 #ifdef EXPENSIVE_CHECKS
340  // Verify all sub-loops are in LCSSA form already.
341  for (Loop *SubLoop: L) {
342  (void)SubLoop; // Silence unused variable warning.
343  assert(SubLoop->isRecursivelyLCSSAForm(DT, *LI) && "Subloop not in LCSSA!");
344  }
345 #endif
346 
347  SmallVector<BasicBlock *, 8> ExitBlocks;
348  L.getExitBlocks(ExitBlocks);
349  if (ExitBlocks.empty())
350  return false;
351 
352  SmallSetVector<BasicBlock *, 8> BlocksDominatingExits;
353 
354  // We want to avoid use-scanning leveraging dominance informations.
355  // If a block doesn't dominate any of the loop exits, the none of the values
356  // defined in the loop can be used outside.
357  // We compute the set of blocks fullfilling the conditions in advance
358  // walking the dominator tree upwards until we hit a loop header.
359  computeBlocksDominatingExits(L, DT, ExitBlocks, BlocksDominatingExits);
360 
362 
363  // Look at all the instructions in the loop, checking to see if they have uses
364  // outside the loop. If so, put them into the worklist to rewrite those uses.
365  for (BasicBlock *BB : BlocksDominatingExits) {
366  // Skip blocks that are part of any sub-loops, they must be in LCSSA
367  // already.
368  if (LI->getLoopFor(BB) != &L)
369  continue;
370  for (Instruction &I : *BB) {
371  // Reject two common cases fast: instructions with no uses (like stores)
372  // and instructions with one use that is in the same block as this.
373  if (I.use_empty() ||
374  (I.hasOneUse() && I.user_back()->getParent() == BB &&
375  !isa<PHINode>(I.user_back())))
376  continue;
377 
378  // Tokens cannot be used in PHI nodes, so we skip over them.
379  // We can run into tokens which are live out of a loop with catchswitch
380  // instructions in Windows EH if the catchswitch has one catchpad which
381  // is inside the loop and another which is not.
382  if (I.getType()->isTokenTy())
383  continue;
384 
385  Worklist.push_back(&I);
386  }
387  }
388 
389  IRBuilder<> Builder(L.getHeader()->getContext());
390  Changed = formLCSSAForInstructions(Worklist, DT, *LI, SE, Builder);
391 
392  // If we modified the code, remove any caches about the loop from SCEV to
393  // avoid dangling entries.
394  // FIXME: This is a big hammer, can we clear the cache more selectively?
395  if (SE && Changed)
396  SE->forgetLoop(&L);
397 
398  assert(L.isLCSSAForm(DT));
399 
400  return Changed;
401 }
402 
403 /// Process a loop nest depth first.
405  const LoopInfo *LI, ScalarEvolution *SE) {
406  bool Changed = false;
407 
408  // Recurse depth-first through inner loops.
409  for (Loop *SubLoop : L.getSubLoops())
410  Changed |= formLCSSARecursively(*SubLoop, DT, LI, SE);
411 
412  Changed |= formLCSSA(L, DT, LI, SE);
413  return Changed;
414 }
415 
416 /// Process all loops in the function, inner-most out.
417 static bool formLCSSAOnAllLoops(const LoopInfo *LI, const DominatorTree &DT,
418  ScalarEvolution *SE) {
419  bool Changed = false;
420  for (auto &L : *LI)
421  Changed |= formLCSSARecursively(*L, DT, LI, SE);
422  return Changed;
423 }
424 
425 namespace {
426 struct LCSSAWrapperPass : public FunctionPass {
427  static char ID; // Pass identification, replacement for typeid
428  LCSSAWrapperPass() : FunctionPass(ID) {
430  }
431 
432  // Cached analysis information for the current function.
433  DominatorTree *DT;
434  LoopInfo *LI;
435  ScalarEvolution *SE;
436 
437  bool runOnFunction(Function &F) override;
438  void verifyAnalysis() const override {
439  // This check is very expensive. On the loop intensive compiles it may cause
440  // up to 10x slowdown. Currently it's disabled by default. LPPassManager
441  // always does limited form of the LCSSA verification. Similar reasoning
442  // was used for the LoopInfo verifier.
443  if (VerifyLoopLCSSA) {
444  assert(all_of(*LI,
445  [&](Loop *L) {
446  return L->isRecursivelyLCSSAForm(*DT, *LI);
447  }) &&
448  "LCSSA form is broken!");
449  }
450  };
451 
452  /// This transformation requires natural loop information & requires that
453  /// loop preheaders be inserted into the CFG. It maintains both of these,
454  /// as well as the CFG. It also requires dominator information.
455  void getAnalysisUsage(AnalysisUsage &AU) const override {
456  AU.setPreservesCFG();
457 
468 
469  // This is needed to perform LCSSA verification inside LPPassManager
472  }
473 };
474 }
475 
476 char LCSSAWrapperPass::ID = 0;
477 INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
478  false, false)
482 INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
484 
485 Pass *llvm::createLCSSAPass() { return new LCSSAWrapperPass(); }
487 
488 /// Transform \p F into loop-closed SSA form.
490  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
491  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
492  auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
493  SE = SEWP ? &SEWP->getSE() : nullptr;
494 
495  return formLCSSAOnAllLoops(LI, *DT, SE);
496 }
497 
499  auto &LI = AM.getResult<LoopAnalysis>(F);
500  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
501  auto *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F);
502  if (!formLCSSAOnAllLoops(&LI, DT, SE))
503  return PreservedAnalyses::all();
504 
506  PA.preserveSet<CFGAnalyses>();
508  // BPI maps terminators to probabilities, since we don't modify the CFG, no
509  // updates are needed to preserve it.
512  return PA;
513 }
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:335
computeBlocksDominatingExits
static void computeBlocksDominatingExits(Loop &L, const DominatorTree &DT, SmallVector< BasicBlock *, 8 > &ExitBlocks, SmallSetVector< BasicBlock *, 8 > &BlocksDominatingExits)
Definition: LCSSA.cpp:293
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2115
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:780
llvm::Function
Definition: Function.h:60
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:447
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
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:122
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:1185
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:417
llvm::PHINode::getOperandNumForIncomingValue
static unsigned getOperandNumForIncomingValue(unsigned i)
Definition: Instructions.h:2770
llvm::dwarf::Form
Form
Definition: Dwarf.h:132
llvm::IRBuilder<>
llvm::SmallDenseMap
Definition: DenseMap.h:882
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:139
ScalarEvolution.h
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1271
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:404
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:147
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
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:143
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:1607
llvm::LCSSAPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LCSSA.cpp:498
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:998
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:31
llvm::BranchProbabilityInfoWrapperPass
Legacy analysis pass which computes BranchProbabilityInfo.
Definition: BranchProbabilityInfo.h:438
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:667
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:297
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:2145
Utils.h
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2756
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:1392
llvm::createLCSSAPass
Pass * createLCSSAPass()
Definition: LCSSA.cpp:485
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:2814
DebugInfo.h
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:970
I
#define I(x, y, z)
Definition: MD5.cpp:58
PredIteratorCache.h
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:1672
llvm::LCSSAVerificationPass
Definition: LoopPass.h:124
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:364
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:8099
llvm::initializeLCSSAWrapperPassPass
void initializeLCSSAWrapperPassPass(PassRegistry &)
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:948
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:1086
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:350
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:482
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:309
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::LCSSAID
char & LCSSAID
Definition: LCSSA.cpp:486
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:8037
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:799
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::Loop::isRecursivelyLCSSAForm
bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:465
ScalarEvolutionAliasAnalysis.h
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
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:1347
llvm::SSAUpdater::RewriteUse
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
Definition: SSAUpdater.cpp:186
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:148
llvm::PHINode
Definition: Instructions.h:2664
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:405
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:1246
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:37