LLVM  14.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/LoopPass.h"
40 #include "llvm/IR/Constants.h"
41 #include "llvm/IR/DebugInfo.h"
42 #include "llvm/IR/Dominators.h"
43 #include "llvm/IR/Function.h"
44 #include "llvm/IR/IRBuilder.h"
45 #include "llvm/IR/Instructions.h"
46 #include "llvm/IR/IntrinsicInst.h"
48 #include "llvm/InitializePasses.h"
49 #include "llvm/Pass.h"
51 #include "llvm/Transforms/Utils.h"
54 using namespace llvm;
55 
56 #define DEBUG_TYPE "lcssa"
57 
58 STATISTIC(NumLCSSA, "Number of live out of a loop variables");
59 
60 #ifdef EXPENSIVE_CHECKS
61 static bool VerifyLoopLCSSA = true;
62 #else
63 static bool VerifyLoopLCSSA = false;
64 #endif
66  VerifyLoopLCSSAFlag("verify-loop-lcssa", cl::location(VerifyLoopLCSSA),
67  cl::Hidden,
68  cl::desc("Verify loop lcssa form (time consuming)"));
69 
70 /// Return true if the specified block is in the list.
71 static bool isExitBlock(BasicBlock *BB,
72  const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
73  return is_contained(ExitBlocks, BB);
74 }
75 
76 /// For every instruction from the worklist, check to see if it has any uses
77 /// that are outside the current loop. If so, insert LCSSA PHI nodes and
78 /// rewrite the uses.
80  const DominatorTree &DT, const LoopInfo &LI,
82  SmallVectorImpl<PHINode *> *PHIsToRemove) {
83  SmallVector<Use *, 16> UsesToRewrite;
84  SmallSetVector<PHINode *, 16> LocalPHIsToRemove;
85  PredIteratorCache PredCache;
86  bool Changed = false;
87 
89 
90  // Cache the Loop ExitBlocks across this loop. We expect to get a lot of
91  // instructions within the same loops, computing the exit blocks is
92  // expensive, and we're not mutating the loop structure.
94 
95  while (!Worklist.empty()) {
96  UsesToRewrite.clear();
97 
98  Instruction *I = Worklist.pop_back_val();
99  assert(!I->getType()->isTokenTy() && "Tokens shouldn't be in the worklist");
100  BasicBlock *InstBB = I->getParent();
101  Loop *L = LI.getLoopFor(InstBB);
102  assert(L && "Instruction belongs to a BB that's not part of a loop");
103  if (!LoopExitBlocks.count(L))
104  L->getExitBlocks(LoopExitBlocks[L]);
105  assert(LoopExitBlocks.count(L));
106  const SmallVectorImpl<BasicBlock *> &ExitBlocks = LoopExitBlocks[L];
107 
108  if (ExitBlocks.empty())
109  continue;
110 
111  for (Use &U : I->uses()) {
112  Instruction *User = cast<Instruction>(U.getUser());
113  BasicBlock *UserBB = User->getParent();
114 
115  // For practical purposes, we consider that the use in a PHI
116  // occurs in the respective predecessor block. For more info,
117  // see the `phi` doc in LangRef and the LCSSA doc.
118  if (auto *PN = dyn_cast<PHINode>(User))
119  UserBB = PN->getIncomingBlock(U);
120 
121  if (InstBB != UserBB && !L->contains(UserBB))
122  UsesToRewrite.push_back(&U);
123  }
124 
125  // If there are no uses outside the loop, exit with no change.
126  if (UsesToRewrite.empty())
127  continue;
128 
129  ++NumLCSSA; // We are applying the transformation
130 
131  // Invoke instructions are special in that their result value is not
132  // available along their unwind edge. The code below tests to see whether
133  // DomBB dominates the value, so adjust DomBB to the normal destination
134  // block, which is effectively where the value is first usable.
135  BasicBlock *DomBB = InstBB;
136  if (auto *Inv = dyn_cast<InvokeInst>(I))
137  DomBB = Inv->getNormalDest();
138 
139  const DomTreeNode *DomNode = DT.getNode(DomBB);
140 
141  SmallVector<PHINode *, 16> AddedPHIs;
142  SmallVector<PHINode *, 8> PostProcessPHIs;
143 
144  SmallVector<PHINode *, 4> InsertedPHIs;
145  SSAUpdater SSAUpdate(&InsertedPHIs);
146  SSAUpdate.Initialize(I->getType(), I->getName());
147 
148  // Force re-computation of I, as some users now need to use the new PHI
149  // node.
150  if (SE)
151  SE->forgetValue(I);
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  for (BasicBlock *ExitBB : ExitBlocks) {
156  if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
157  continue;
158 
159  // If we already inserted something for this BB, don't reprocess it.
160  if (SSAUpdate.HasValueForBlock(ExitBB))
161  continue;
162  Builder.SetInsertPoint(&ExitBB->front());
163  PHINode *PN = Builder.CreatePHI(I->getType(), PredCache.size(ExitBB),
164  I->getName() + ".lcssa");
165  // Get the debug location from the original instruction.
166  PN->setDebugLoc(I->getDebugLoc());
167 
168  // Add inputs from inside the loop for this PHI. This is valid
169  // because `I` dominates `ExitBB` (checked above). This implies
170  // that every incoming block/edge is dominated by `I` as well,
171  // i.e. we can add uses of `I` to those incoming edges/append to the incoming
172  // blocks without violating the SSA dominance property.
173  for (BasicBlock *Pred : PredCache.get(ExitBB)) {
174  PN->addIncoming(I, Pred);
175 
176  // If the exit block has a predecessor not within the loop, arrange for
177  // the incoming value use corresponding to that predecessor to be
178  // rewritten in terms of a different LCSSA PHI.
179  if (!L->contains(Pred))
180  UsesToRewrite.push_back(
182  PN->getNumIncomingValues() - 1)));
183  }
184 
185  AddedPHIs.push_back(PN);
186 
187  // Remember that this phi makes the value alive in this block.
188  SSAUpdate.AddAvailableValue(ExitBB, PN);
189 
190  // LoopSimplify might fail to simplify some loops (e.g. when indirect
191  // branches are involved). In such situations, it might happen that an
192  // exit for Loop L1 is the header of a disjoint Loop L2. Thus, when we
193  // create PHIs in such an exit block, we are also inserting PHIs into L2's
194  // header. This could break LCSSA form for L2 because these inserted PHIs
195  // can also have uses outside of L2. Remember all PHIs in such situation
196  // as to revisit than later on. FIXME: Remove this if indirectbr support
197  // into LoopSimplify gets improved.
198  if (auto *OtherLoop = LI.getLoopFor(ExitBB))
199  if (!L->contains(OtherLoop))
200  PostProcessPHIs.push_back(PN);
201  }
202 
203  // Rewrite all uses outside the loop in terms of the new PHIs we just
204  // inserted.
205  for (Use *UseToRewrite : UsesToRewrite) {
206  Instruction *User = cast<Instruction>(UseToRewrite->getUser());
207  BasicBlock *UserBB = User->getParent();
208 
209  // For practical purposes, we consider that the use in a PHI
210  // occurs in the respective predecessor block. For more info,
211  // see the `phi` doc in LangRef and the LCSSA doc.
212  if (auto *PN = dyn_cast<PHINode>(User))
213  UserBB = PN->getIncomingBlock(*UseToRewrite);
214 
215  // If this use is in an exit block, rewrite to use the newly inserted PHI.
216  // This is required for correctness because SSAUpdate doesn't handle uses
217  // in the same block. It assumes the PHI we inserted is at the end of the
218  // block.
219  if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) {
220  UseToRewrite->set(&UserBB->front());
221  continue;
222  }
223 
224  // If we added a single PHI, it must dominate all uses and we can directly
225  // rename it.
226  if (AddedPHIs.size() == 1) {
227  UseToRewrite->set(AddedPHIs[0]);
228  continue;
229  }
230 
231  // Otherwise, do full PHI insertion.
232  SSAUpdate.RewriteUse(*UseToRewrite);
233  }
234 
236  llvm::findDbgValues(DbgValues, I);
237 
238  // Update pre-existing debug value uses that reside outside the loop.
239  for (auto DVI : DbgValues) {
240  BasicBlock *UserBB = DVI->getParent();
241  if (InstBB == UserBB || L->contains(UserBB))
242  continue;
243  // We currently only handle debug values residing in blocks that were
244  // traversed while rewriting the uses. If we inserted just a single PHI,
245  // we will handle all relevant debug values.
246  Value *V = AddedPHIs.size() == 1 ? AddedPHIs[0]
247  : SSAUpdate.FindValueForBlock(UserBB);
248  if (V)
249  DVI->replaceVariableLocationOp(I, V);
250  }
251 
252  // SSAUpdater might have inserted phi-nodes inside other loops. We'll need
253  // to post-process them to keep LCSSA form.
254  for (PHINode *InsertedPN : InsertedPHIs) {
255  if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent()))
256  if (!L->contains(OtherLoop))
257  PostProcessPHIs.push_back(InsertedPN);
258  }
259 
260  // Post process PHI instructions that were inserted into another disjoint
261  // loop and update their exits properly.
262  for (auto *PostProcessPN : PostProcessPHIs)
263  if (!PostProcessPN->use_empty())
264  Worklist.push_back(PostProcessPN);
265 
266  // Keep track of PHI nodes that we want to remove because they did not have
267  // any uses rewritten.
268  for (PHINode *PN : AddedPHIs)
269  if (PN->use_empty())
270  LocalPHIsToRemove.insert(PN);
271 
272  Changed = true;
273  }
274 
275  // Remove PHI nodes that did not have any uses rewritten or add them to
276  // PHIsToRemove, so the caller can remove them after some additional cleanup.
277  // We need to redo the use_empty() check here, because even if the PHI node
278  // wasn't used when added to LocalPHIsToRemove, later added PHI nodes can be
279  // using it. This cleanup is not guaranteed to handle trees/cycles of PHI
280  // nodes that only are used by each other. Such situations has only been
281  // noticed when the input IR contains unreachable code, and leaving some extra
282  // redundant PHI nodes in such situations is considered a minor problem.
283  if (PHIsToRemove) {
284  PHIsToRemove->append(LocalPHIsToRemove.begin(), LocalPHIsToRemove.end());
285  } else {
286  for (PHINode *PN : LocalPHIsToRemove)
287  if (PN->use_empty())
288  PN->eraseFromParent();
289  }
290  return Changed;
291 }
292 
293 // Compute the set of BasicBlocks in the loop `L` dominating at least one exit.
295  Loop &L, const DominatorTree &DT, SmallVector<BasicBlock *, 8> &ExitBlocks,
296  SmallSetVector<BasicBlock *, 8> &BlocksDominatingExits) {
297  // We start from the exit blocks, as every block trivially dominates itself
298  // (not strictly).
299  SmallVector<BasicBlock *, 8> BBWorklist(ExitBlocks);
300 
301  while (!BBWorklist.empty()) {
302  BasicBlock *BB = BBWorklist.pop_back_val();
303 
304  // Check if this is a loop header. If this is the case, we're done.
305  if (L.getHeader() == BB)
306  continue;
307 
308  // Otherwise, add its immediate predecessor in the dominator tree to the
309  // worklist, unless we visited it already.
310  BasicBlock *IDomBB = DT.getNode(BB)->getIDom()->getBlock();
311 
312  // Exit blocks can have an immediate dominator not belonging to the
313  // loop. For an exit block to be immediately dominated by another block
314  // outside the loop, it implies not all paths from that dominator, to the
315  // exit block, go through the loop.
316  // Example:
317  //
318  // |---- A
319  // | |
320  // | B<--
321  // | | |
322  // |---> C --
323  // |
324  // D
325  //
326  // C is the exit block of the loop and it's immediately dominated by A,
327  // which doesn't belong to the loop.
328  if (!L.contains(IDomBB))
329  continue;
330 
331  if (BlocksDominatingExits.insert(IDomBB))
332  BBWorklist.push_back(IDomBB);
333  }
334 }
335 
336 bool llvm::formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
337  ScalarEvolution *SE) {
338  bool Changed = false;
339 
340 #ifdef EXPENSIVE_CHECKS
341  // Verify all sub-loops are in LCSSA form already.
342  for (Loop *SubLoop: L)
343  assert(SubLoop->isRecursivelyLCSSAForm(DT, *LI) && "Subloop not in LCSSA!");
344 #endif
345 
346  SmallVector<BasicBlock *, 8> ExitBlocks;
347  L.getExitBlocks(ExitBlocks);
348  if (ExitBlocks.empty())
349  return false;
350 
351  SmallSetVector<BasicBlock *, 8> BlocksDominatingExits;
352 
353  // We want to avoid use-scanning leveraging dominance informations.
354  // If a block doesn't dominate any of the loop exits, the none of the values
355  // defined in the loop can be used outside.
356  // We compute the set of blocks fullfilling the conditions in advance
357  // walking the dominator tree upwards until we hit a loop header.
358  computeBlocksDominatingExits(L, DT, ExitBlocks, BlocksDominatingExits);
359 
361 
362  // Look at all the instructions in the loop, checking to see if they have uses
363  // outside the loop. If so, put them into the worklist to rewrite those uses.
364  for (BasicBlock *BB : BlocksDominatingExits) {
365  // Skip blocks that are part of any sub-loops, they must be in LCSSA
366  // already.
367  if (LI->getLoopFor(BB) != &L)
368  continue;
369  for (Instruction &I : *BB) {
370  // Reject two common cases fast: instructions with no uses (like stores)
371  // and instructions with one use that is in the same block as this.
372  if (I.use_empty() ||
373  (I.hasOneUse() && I.user_back()->getParent() == BB &&
374  !isa<PHINode>(I.user_back())))
375  continue;
376 
377  // Tokens cannot be used in PHI nodes, so we skip over them.
378  // We can run into tokens which are live out of a loop with catchswitch
379  // instructions in Windows EH if the catchswitch has one catchpad which
380  // is inside the loop and another which is not.
381  if (I.getType()->isTokenTy())
382  continue;
383 
384  Worklist.push_back(&I);
385  }
386  }
387 
388  IRBuilder<> Builder(L.getHeader()->getContext());
389  Changed = formLCSSAForInstructions(Worklist, DT, *LI, SE, Builder);
390 
391  // If we modified the code, remove any caches about the loop from SCEV to
392  // avoid dangling entries.
393  // FIXME: This is a big hammer, can we clear the cache more selectively?
394  if (SE && Changed)
395  SE->forgetLoop(&L);
396 
397  assert(L.isLCSSAForm(DT));
398 
399  return Changed;
400 }
401 
402 /// Process a loop nest depth first.
404  const LoopInfo *LI, ScalarEvolution *SE) {
405  bool Changed = false;
406 
407  // Recurse depth-first through inner loops.
408  for (Loop *SubLoop : L.getSubLoops())
409  Changed |= formLCSSARecursively(*SubLoop, DT, LI, SE);
410 
411  Changed |= formLCSSA(L, DT, LI, SE);
412  return Changed;
413 }
414 
415 /// Process all loops in the function, inner-most out.
416 static bool formLCSSAOnAllLoops(const LoopInfo *LI, const DominatorTree &DT,
417  ScalarEvolution *SE) {
418  bool Changed = false;
419  for (auto &L : *LI)
420  Changed |= formLCSSARecursively(*L, DT, LI, SE);
421  return Changed;
422 }
423 
424 namespace {
425 struct LCSSAWrapperPass : public FunctionPass {
426  static char ID; // Pass identification, replacement for typeid
427  LCSSAWrapperPass() : FunctionPass(ID) {
429  }
430 
431  // Cached analysis information for the current function.
432  DominatorTree *DT;
433  LoopInfo *LI;
434  ScalarEvolution *SE;
435 
436  bool runOnFunction(Function &F) override;
437  void verifyAnalysis() const override {
438  // This check is very expensive. On the loop intensive compiles it may cause
439  // up to 10x slowdown. Currently it's disabled by default. LPPassManager
440  // always does limited form of the LCSSA verification. Similar reasoning
441  // was used for the LoopInfo verifier.
442  if (VerifyLoopLCSSA) {
443  assert(all_of(*LI,
444  [&](Loop *L) {
445  return L->isRecursivelyLCSSAForm(*DT, *LI);
446  }) &&
447  "LCSSA form is broken!");
448  }
449  };
450 
451  /// This transformation requires natural loop information & requires that
452  /// loop preheaders be inserted into the CFG. It maintains both of these,
453  /// as well as the CFG. It also requires dominator information.
454  void getAnalysisUsage(AnalysisUsage &AU) const override {
455  AU.setPreservesCFG();
456 
467 
468  // This is needed to perform LCSSA verification inside LPPassManager
471  }
472 };
473 }
474 
475 char LCSSAWrapperPass::ID = 0;
476 INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
477  false, false)
481 INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
483 
484 Pass *llvm::createLCSSAPass() { return new LCSSAWrapperPass(); }
486 
487 /// Transform \p F into loop-closed SSA form.
489  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
490  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
491  auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
492  SE = SEWP ? &SEWP->getSE() : nullptr;
493 
494  return formLCSSAOnAllLoops(LI, *DT, SE);
495 }
496 
498  auto &LI = AM.getResult<LoopAnalysis>(F);
499  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
500  auto *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F);
501  if (!formLCSSAOnAllLoops(&LI, DT, SE))
502  return PreservedAnalyses::all();
503 
505  PA.preserveSet<CFGAnalyses>();
507  // BPI maps terminators to probabilities, since we don't modify the CFG, no
508  // updates are needed to preserve it.
511  return PA;
512 }
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:53
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::formLCSSA
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Definition: LCSSA.cpp:336
computeBlocksDominatingExits
static void computeBlocksDominatingExits(Loop &L, const DominatorTree &DT, SmallVector< BasicBlock *, 8 > &ExitBlocks, SmallSetVector< BasicBlock *, 8 > &BlocksDominatingExits)
Definition: LCSSA.cpp:294
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2061
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::LoopBase::getExitBlocks
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:62
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
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:783
llvm::Function
Definition: Function.h:62
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:457
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:1168
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:416
llvm::PHINode::getOperandNumForIncomingValue
static unsigned getOperandNumForIncomingValue(unsigned i)
Definition: Instructions.h:2739
llvm::dwarf::Form
Form
Definition: Dwarf.h:131
llvm::IRBuilder<>
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
GlobalsModRef.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
ScalarEvolution.h
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1268
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:403
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::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
BasicAliasAnalysis.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:115
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:414
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:1551
llvm::LCSSAPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LCSSA.cpp:497
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:981
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
Constants.h
llvm::BranchProbabilityInfoWrapperPass
Legacy analysis pass which computes BranchProbabilityInfo.
Definition: BranchProbabilityInfo.h:440
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:648
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:296
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:142
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
LoopUtils.h
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2091
Utils.h
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2725
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::cl::opt
Definition: CommandLine.h:1432
llvm::createLCSSAPass
Pass * createLCSSAPass()
Definition: LCSSA.cpp:484
SSA
Memory SSA
Definition: MemorySSA.cpp:73
BranchProbabilityInfo.h
llvm::SCEVAAWrapperPass
Legacy wrapper pass to provide the SCEVAAResult object.
Definition: ScalarEvolutionAliasAnalysis.h:55
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
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:176
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2783
DebugInfo.h
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:967
I
#define I(x, y, z)
Definition: MD5.cpp:59
PredIteratorCache.h
llvm::findDbgValues
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: DebugInfo.cpp:76
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:1616
llvm::LCSSAVerificationPass
Definition: LoopPass.h:123
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:367
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:7583
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:931
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
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:63
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
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:116
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:66
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:367
llvm::IRBuilderBase
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:95
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:62
lcssa
lcssa
Definition: LCSSA.cpp:481
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:308
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::LCSSAID
char & LCSSAID
Definition: LCSSA.cpp:485
llvm::LoopSimplifyID
char & LoopSimplifyID
Definition: LoopSimplify.cpp:800
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:7520
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
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:802
Function.h
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:468
ScalarEvolutionAliasAnalysis.h
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
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:79
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:191
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:71
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1336
llvm::SSAUpdater::RewriteUse
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
Definition: SSAUpdater.cpp:187
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
llvm::PHINode
Definition: Instructions.h:2633
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:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
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:70
llvm::cl::desc
Definition: CommandLine.h:412
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:1243
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
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