LLVM  13.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/Dominators.h"
42 #include "llvm/IR/Function.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"
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  auto &Ctx = I->getContext();
240  for (auto DVI : DbgValues) {
241  BasicBlock *UserBB = DVI->getParent();
242  if (InstBB == UserBB || L->contains(UserBB))
243  continue;
244  // We currently only handle debug values residing in blocks that were
245  // traversed while rewriting the uses. If we inserted just a single PHI,
246  // we will handle all relevant debug values.
247  Value *V = AddedPHIs.size() == 1 ? AddedPHIs[0]
248  : SSAUpdate.FindValueForBlock(UserBB);
249  if (V)
250  DVI->setOperand(0, MetadataAsValue::get(Ctx, ValueAsMetadata::get(V)));
251  }
252 
253  // SSAUpdater might have inserted phi-nodes inside other loops. We'll need
254  // to post-process them to keep LCSSA form.
255  for (PHINode *InsertedPN : InsertedPHIs) {
256  if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent()))
257  if (!L->contains(OtherLoop))
258  PostProcessPHIs.push_back(InsertedPN);
259  }
260 
261  // Post process PHI instructions that were inserted into another disjoint
262  // loop and update their exits properly.
263  for (auto *PostProcessPN : PostProcessPHIs)
264  if (!PostProcessPN->use_empty())
265  Worklist.push_back(PostProcessPN);
266 
267  // Keep track of PHI nodes that we want to remove because they did not have
268  // any uses rewritten.
269  for (PHINode *PN : AddedPHIs)
270  if (PN->use_empty())
271  LocalPHIsToRemove.insert(PN);
272 
273  Changed = true;
274  }
275 
276  // Remove PHI nodes that did not have any uses rewritten or add them to
277  // PHIsToRemove, so the caller can remove them after some additional cleanup.
278  // We need to redo the use_empty() check here, because even if the PHI node
279  // wasn't used when added to LocalPHIsToRemove, later added PHI nodes can be
280  // using it. This cleanup is not guaranteed to handle trees/cycles of PHI
281  // nodes that only are used by each other. Such situations has only been
282  // noticed when the input IR contains unreachable code, and leaving some extra
283  // redundant PHI nodes in such situations is considered a minor problem.
284  if (PHIsToRemove) {
285  PHIsToRemove->append(LocalPHIsToRemove.begin(), LocalPHIsToRemove.end());
286  } else {
287  for (PHINode *PN : LocalPHIsToRemove)
288  if (PN->use_empty())
289  PN->eraseFromParent();
290  }
291  return Changed;
292 }
293 
294 // Compute the set of BasicBlocks in the loop `L` dominating at least one exit.
296  Loop &L, const DominatorTree &DT, SmallVector<BasicBlock *, 8> &ExitBlocks,
297  SmallSetVector<BasicBlock *, 8> &BlocksDominatingExits) {
298  // We start from the exit blocks, as every block trivially dominates itself
299  // (not strictly).
300  SmallVector<BasicBlock *, 8> BBWorklist(ExitBlocks);
301 
302  while (!BBWorklist.empty()) {
303  BasicBlock *BB = BBWorklist.pop_back_val();
304 
305  // Check if this is a loop header. If this is the case, we're done.
306  if (L.getHeader() == BB)
307  continue;
308 
309  // Otherwise, add its immediate predecessor in the dominator tree to the
310  // worklist, unless we visited it already.
311  BasicBlock *IDomBB = DT.getNode(BB)->getIDom()->getBlock();
312 
313  // Exit blocks can have an immediate dominator not beloinging to the
314  // loop. For an exit block to be immediately dominated by another block
315  // outside the loop, it implies not all paths from that dominator, to the
316  // exit block, go through the loop.
317  // Example:
318  //
319  // |---- A
320  // | |
321  // | B<--
322  // | | |
323  // |---> C --
324  // |
325  // D
326  //
327  // C is the exit block of the loop and it's immediately dominated by A,
328  // which doesn't belong to the loop.
329  if (!L.contains(IDomBB))
330  continue;
331 
332  if (BlocksDominatingExits.insert(IDomBB))
333  BBWorklist.push_back(IDomBB);
334  }
335 }
336 
337 bool llvm::formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
338  ScalarEvolution *SE) {
339  bool Changed = false;
340 
341 #ifdef EXPENSIVE_CHECKS
342  // Verify all sub-loops are in LCSSA form already.
343  for (Loop *SubLoop: L)
344  assert(SubLoop->isRecursivelyLCSSAForm(DT, *LI) && "Subloop not in LCSSA!");
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>();
507  PA.preserve<BasicAA>();
508  PA.preserve<GlobalsAA>();
509  PA.preserve<SCEVAA>();
511  // BPI maps terminators to probabilities, since we don't modify the CFG, no
512  // updates are needed to preserve it.
515  return PA;
516 }
llvm::GlobalsAA
Analysis pass providing a never-invalidated alias analysis result.
Definition: GlobalsModRef.h:132
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:337
llvm::BasicAA
Analysis pass providing a never-invalidated alias analysis result.
Definition: BasicAliasAnalysis.h:246
computeBlocksDominatingExits
static void computeBlocksDominatingExits(Loop &L, const DominatorTree &DT, SmallVector< BasicBlock *, 8 > &ExitBlocks, SmallSetVector< BasicBlock *, 8 > &BlocksDominatingExits)
Definition: LCSSA.cpp:295
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2058
llvm::SCEVAA
Analysis pass providing a never-invalidated alias analysis result.
Definition: ScalarEvolutionAliasAnalysis.h:41
llvm
This class represents lattice values for constants.
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:61
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:785
llvm::Function
Definition: Function.h:61
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:456
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:529
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:417
llvm::PHINode::getOperandNumForIncomingValue
static unsigned getOperandNumForIncomingValue(unsigned i)
Definition: Instructions.h:2686
llvm::dwarf::Form
Form
Definition: Dwarf.h:112
llvm::IRBuilder<>
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
Local.h
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:140
llvm::DominatorTree::dominates
bool dominates(const Value *Def, const Use &U) const
Return true if value Def dominates use U, in the sense that Def is available at U,...
Definition: Dominators.cpp:260
ScalarEvolution.h
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1249
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:145
llvm::ValueAsMetadata::get
static ValueAsMetadata * get(Value *V)
Definition: Metadata.cpp:349
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
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
AliasAnalysis.h
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:420
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:1498
llvm::LCSSAPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LCSSA.cpp:498
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:960
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:446
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:278
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
LoopUtils.h
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2088
Utils.h
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2672
llvm::cl::opt
Definition: CommandLine.h:1419
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:52
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:258
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2730
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:963
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: Local.cpp:1635
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:1563
llvm::LCSSAVerificationPass
Definition: LoopPass.h:123
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:362
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:7156
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:921
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:643
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:1079
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:482
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:486
llvm::LoopSimplifyID
char & LoopSimplifyID
Definition: LoopSimplify.cpp:801
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:7084
llvm::MetadataAsValue::get
static MetadataAsValue * get(LLVMContext &Context, Metadata *MD)
Definition: Metadata.cpp:106
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:804
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:461
ScalarEvolutionAliasAnalysis.h
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:249
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:1200
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:2582
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:43
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:411
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:75
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1224
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