LLVM  8.0.0svn
IVUsers.cpp
Go to the documentation of this file.
1 //===- IVUsers.cpp - Induction Variable Users -------------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements bookkeeping for "interesting" users of expressions
11 // computed from induction variables.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/Analysis/IVUsers.h"
16 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/Analysis/LoopPass.h"
23 #include "llvm/Config/llvm-config.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/DataLayout.h"
26 #include "llvm/IR/DerivedTypes.h"
27 #include "llvm/IR/Dominators.h"
28 #include "llvm/IR/Instructions.h"
29 #include "llvm/IR/Module.h"
30 #include "llvm/IR/Type.h"
31 #include "llvm/Support/Debug.h"
33 #include <algorithm>
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "iv-users"
37 
38 AnalysisKey IVUsersAnalysis::Key;
39 
42  return IVUsers(&L, &AR.AC, &AR.LI, &AR.DT, &AR.SE);
43 }
44 
45 char IVUsersWrapperPass::ID = 0;
47  "Induction Variable Users", false, true)
52 INITIALIZE_PASS_END(IVUsersWrapperPass, "iv-users", "Induction Variable Users",
53  false, true)
54 
56 
57 /// isInteresting - Test whether the given expression is "interesting" when
58 /// used by the given expression, within the context of analyzing the
59 /// given loop.
60 static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L,
61  ScalarEvolution *SE, LoopInfo *LI) {
62  // An addrec is interesting if it's affine or if it has an interesting start.
63  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
64  // Keep things simple. Don't touch loop-variant strides unless they're
65  // only used outside the loop and we can simplify them.
66  if (AR->getLoop() == L)
67  return AR->isAffine() ||
68  (!L->contains(I) &&
69  SE->getSCEVAtScope(AR, LI->getLoopFor(I->getParent())) != AR);
70  // Otherwise recurse to see if the start value is interesting, and that
71  // the step value is not interesting, since we don't yet know how to
72  // do effective SCEV expansions for addrecs with interesting steps.
73  return isInteresting(AR->getStart(), I, L, SE, LI) &&
74  !isInteresting(AR->getStepRecurrence(*SE), I, L, SE, LI);
75  }
76 
77  // An add is interesting if exactly one of its operands is interesting.
78  if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
79  bool AnyInterestingYet = false;
80  for (const auto *Op : Add->operands())
81  if (isInteresting(Op, I, L, SE, LI)) {
82  if (AnyInterestingYet)
83  return false;
84  AnyInterestingYet = true;
85  }
86  return AnyInterestingYet;
87  }
88 
89  // Nothing else is interesting here.
90  return false;
91 }
92 
93 /// Return true if all loop headers that dominate this block are in simplified
94 /// form.
95 static bool isSimplifiedLoopNest(BasicBlock *BB, const DominatorTree *DT,
96  const LoopInfo *LI,
97  SmallPtrSetImpl<Loop*> &SimpleLoopNests) {
98  Loop *NearestLoop = nullptr;
99  for (DomTreeNode *Rung = DT->getNode(BB);
100  Rung; Rung = Rung->getIDom()) {
101  BasicBlock *DomBB = Rung->getBlock();
102  Loop *DomLoop = LI->getLoopFor(DomBB);
103  if (DomLoop && DomLoop->getHeader() == DomBB) {
104  // If the domtree walk reaches a loop with no preheader, return false.
105  if (!DomLoop->isLoopSimplifyForm())
106  return false;
107  // If we have already checked this loop nest, stop checking.
108  if (SimpleLoopNests.count(DomLoop))
109  break;
110  // If we have not already checked this loop nest, remember the loop
111  // header nearest to BB. The nearest loop may not contain BB.
112  if (!NearestLoop)
113  NearestLoop = DomLoop;
114  }
115  }
116  if (NearestLoop)
117  SimpleLoopNests.insert(NearestLoop);
118  return true;
119 }
120 
121 /// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression
122 /// and now we need to decide whether the user should use the preinc or post-inc
123 /// value. If this user should use the post-inc version of the IV, return true.
124 ///
125 /// Choosing wrong here can break dominance properties (if we choose to use the
126 /// post-inc value when we cannot) or it can end up adding extra live-ranges to
127 /// the loop, resulting in reg-reg copies (if we use the pre-inc value when we
128 /// should use the post-inc value).
130  const Loop *L, DominatorTree *DT) {
131  // If the user is in the loop, use the preinc value.
132  if (L->contains(User))
133  return false;
134 
135  BasicBlock *LatchBlock = L->getLoopLatch();
136  if (!LatchBlock)
137  return false;
138 
139  // Ok, the user is outside of the loop. If it is dominated by the latch
140  // block, use the post-inc value.
141  if (DT->dominates(LatchBlock, User->getParent()))
142  return true;
143 
144  // There is one case we have to be careful of: PHI nodes. These little guys
145  // can live in blocks that are not dominated by the latch block, but (since
146  // their uses occur in the predecessor block, not the block the PHI lives in)
147  // should still use the post-inc value. Check for this case now.
148  PHINode *PN = dyn_cast<PHINode>(User);
149  if (!PN || !Operand)
150  return false; // not a phi, not dominated by latch block.
151 
152  // Look at all of the uses of Operand by the PHI node. If any use corresponds
153  // to a block that is not dominated by the latch block, give up and use the
154  // preincremented value.
155  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
156  if (PN->getIncomingValue(i) == Operand &&
157  !DT->dominates(LatchBlock, PN->getIncomingBlock(i)))
158  return false;
159 
160  // Okay, all uses of Operand by PN are in predecessor blocks that really are
161  // dominated by the latch block. Use the post-incremented value.
162  return true;
163 }
164 
165 /// AddUsersImpl - Inspect the specified instruction. If it is a
166 /// reducible SCEV, recursively add its users to the IVUsesByStride set and
167 /// return true. Otherwise, return false.
169  SmallPtrSetImpl<Loop*> &SimpleLoopNests) {
170  const DataLayout &DL = I->getModule()->getDataLayout();
171 
172  // Add this IV user to the Processed set before returning false to ensure that
173  // all IV users are members of the set. See IVUsers::isIVUserOrOperand.
174  if (!Processed.insert(I).second)
175  return true; // Instruction already handled.
176 
177  if (!SE->isSCEVable(I->getType()))
178  return false; // Void and FP expressions cannot be reduced.
179 
180  // IVUsers is used by LSR which assumes that all SCEV expressions are safe to
181  // pass to SCEVExpander. Expressions are not safe to expand if they represent
182  // operations that are not safe to speculate, namely integer division.
183  if (!isa<PHINode>(I) && !isSafeToSpeculativelyExecute(I))
184  return false;
185 
186  // LSR is not APInt clean, do not touch integers bigger than 64-bits.
187  // Also avoid creating IVs of non-native types. For example, we don't want a
188  // 64-bit IV in 32-bit code just because the loop has one 64-bit cast.
189  uint64_t Width = SE->getTypeSizeInBits(I->getType());
190  if (Width > 64 || !DL.isLegalInteger(Width))
191  return false;
192 
193  // Don't attempt to promote ephemeral values to indvars. They will be removed
194  // later anyway.
195  if (EphValues.count(I))
196  return false;
197 
198  // Get the symbolic expression for this instruction.
199  const SCEV *ISE = SE->getSCEV(I);
200 
201  // If we've come to an uninteresting expression, stop the traversal and
202  // call this a user.
203  if (!isInteresting(ISE, I, L, SE, LI))
204  return false;
205 
206  SmallPtrSet<Instruction *, 4> UniqueUsers;
207  for (Use &U : I->uses()) {
208  Instruction *User = cast<Instruction>(U.getUser());
209  if (!UniqueUsers.insert(User).second)
210  continue;
211 
212  // Do not infinitely recurse on PHI nodes.
213  if (isa<PHINode>(User) && Processed.count(User))
214  continue;
215 
216  // Only consider IVUsers that are dominated by simplified loop
217  // headers. Otherwise, SCEVExpander will crash.
218  BasicBlock *UseBB = User->getParent();
219  // A phi's use is live out of its predecessor block.
220  if (PHINode *PHI = dyn_cast<PHINode>(User)) {
221  unsigned OperandNo = U.getOperandNo();
222  unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
223  UseBB = PHI->getIncomingBlock(ValNo);
224  }
225  if (!isSimplifiedLoopNest(UseBB, DT, LI, SimpleLoopNests))
226  return false;
227 
228  // Descend recursively, but not into PHI nodes outside the current loop.
229  // It's important to see the entire expression outside the loop to get
230  // choices that depend on addressing mode use right, although we won't
231  // consider references outside the loop in all cases.
232  // If User is already in Processed, we don't want to recurse into it again,
233  // but do want to record a second reference in the same instruction.
234  bool AddUserToIVUsers = false;
235  if (LI->getLoopFor(User->getParent()) != L) {
236  if (isa<PHINode>(User) || Processed.count(User) ||
237  !AddUsersImpl(User, SimpleLoopNests)) {
238  LLVM_DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
239  << " OF SCEV: " << *ISE << '\n');
240  AddUserToIVUsers = true;
241  }
242  } else if (Processed.count(User) || !AddUsersImpl(User, SimpleLoopNests)) {
243  LLVM_DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
244  << " OF SCEV: " << *ISE << '\n');
245  AddUserToIVUsers = true;
246  }
247 
248  if (AddUserToIVUsers) {
249  // Okay, we found a user that we cannot reduce.
250  IVStrideUse &NewUse = AddUser(User, I);
251  // Autodetect the post-inc loop set, populating NewUse.PostIncLoops.
252  // The regular return value here is discarded; instead of recording
253  // it, we just recompute it when we need it.
254  const SCEV *OriginalISE = ISE;
255 
256  auto NormalizePred = [&](const SCEVAddRecExpr *AR) {
257  auto *L = AR->getLoop();
258  bool Result = IVUseShouldUsePostIncValue(User, I, L, DT);
259  if (Result)
260  NewUse.PostIncLoops.insert(L);
261  return Result;
262  };
263 
264  ISE = normalizeForPostIncUseIf(ISE, NormalizePred, *SE);
265 
266  // PostIncNormalization effectively simplifies the expression under
267  // pre-increment assumptions. Those assumptions (no wrapping) might not
268  // hold for the post-inc value. Catch such cases by making sure the
269  // transformation is invertible.
270  if (OriginalISE != ISE) {
271  const SCEV *DenormalizedISE =
272  denormalizeForPostIncUse(ISE, NewUse.PostIncLoops, *SE);
273 
274  // If we normalized the expression, but denormalization doesn't give the
275  // original one, discard this user.
276  if (OriginalISE != DenormalizedISE) {
277  LLVM_DEBUG(dbgs()
278  << " DISCARDING (NORMALIZATION ISN'T INVERTIBLE): "
279  << *ISE << '\n');
280  IVUses.pop_back();
281  return false;
282  }
283  }
284  LLVM_DEBUG(if (SE->getSCEV(I) != ISE) dbgs()
285  << " NORMALIZED TO: " << *ISE << '\n');
286  }
287  }
288  return true;
289 }
290 
292  // SCEVExpander can only handle users that are dominated by simplified loop
293  // entries. Keep track of all loops that are only dominated by other simple
294  // loops so we don't traverse the domtree for each user.
295  SmallPtrSet<Loop*,16> SimpleLoopNests;
296 
297  return AddUsersImpl(I, SimpleLoopNests);
298 }
299 
301  IVUses.push_back(new IVStrideUse(this, User, Operand));
302  return IVUses.back();
303 }
304 
306  ScalarEvolution *SE)
307  : L(L), AC(AC), LI(LI), DT(DT), SE(SE), IVUses() {
308  // Collect ephemeral values so that AddUsersIfInteresting skips them.
309  EphValues.clear();
310  CodeMetrics::collectEphemeralValues(L, AC, EphValues);
311 
312  // Find all uses of induction variables in this loop, and categorize
313  // them by stride. Start by finding all of the PHI nodes in the header for
314  // this loop. If they are induction variables, inspect their uses.
315  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
316  (void)AddUsersIfInteresting(&*I);
317 }
318 
319 void IVUsers::print(raw_ostream &OS, const Module *M) const {
320  OS << "IV Users for loop ";
321  L->getHeader()->printAsOperand(OS, false);
323  OS << " with backedge-taken count " << *SE->getBackedgeTakenCount(L);
324  }
325  OS << ":\n";
326 
327  for (const IVStrideUse &IVUse : IVUses) {
328  OS << " ";
329  IVUse.getOperandValToReplace()->printAsOperand(OS, false);
330  OS << " = " << *getReplacementExpr(IVUse);
331  for (auto PostIncLoop : IVUse.PostIncLoops) {
332  OS << " (post-inc with loop ";
333  PostIncLoop->getHeader()->printAsOperand(OS, false);
334  OS << ")";
335  }
336  OS << " in ";
337  if (IVUse.getUser())
338  IVUse.getUser()->print(OS);
339  else
340  OS << "Printing <null> User";
341  OS << '\n';
342  }
343 }
344 
345 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
347 #endif
348 
350  Processed.clear();
351  IVUses.clear();
352 }
353 
356 }
357 
363  AU.setPreservesAll();
364 }
365 
367  auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
368  *L->getHeader()->getParent());
369  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
370  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
371  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
372 
373  IU.reset(new IVUsers(L, AC, LI, DT, SE));
374  return false;
375 }
376 
377 void IVUsersWrapperPass::print(raw_ostream &OS, const Module *M) const {
378  IU->print(OS, M);
379 }
380 
381 void IVUsersWrapperPass::releaseMemory() { IU->releaseMemory(); }
382 
383 /// getReplacementExpr - Return a SCEV expression which computes the
384 /// value of the OperandValToReplace.
386  return SE->getSCEV(IU.getOperandValToReplace());
387 }
388 
389 /// getExpr - Return the expression for the use.
390 const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {
391  return normalizeForPostIncUse(getReplacementExpr(IU), IU.getPostIncLoops(),
392  *SE);
393 }
394 
395 static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {
396  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
397  if (AR->getLoop() == L)
398  return AR;
399  return findAddRecForLoop(AR->getStart(), L);
400  }
401 
402  if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
403  for (const auto *Op : Add->operands())
404  if (const SCEVAddRecExpr *AR = findAddRecForLoop(Op, L))
405  return AR;
406  return nullptr;
407  }
408 
409  return nullptr;
410 }
411 
412 const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const {
413  if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L))
414  return AR->getStepRecurrence(*SE);
415  return nullptr;
416 }
417 
419  PostIncLoops.insert(L);
420 }
421 
422 void IVStrideUse::deleted() {
423  // Remove this user from the list.
424  Parent->Processed.erase(this->getUser());
425  Parent->IVUses.erase(this);
426  // this now dangles!
427 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value *> &EphValues)
Collect a loop&#39;s ephemeral values (those used only by an assume or similar intrinsics in the loop)...
Definition: CodeMetrics.cpp:72
bool runOnLoop(Loop *L, LPPassManager &LPM) override
Definition: IVUsers.cpp:366
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
void releaseMemory()
Definition: IVUsers.cpp:349
bool AddUsersImpl(Instruction *I, SmallPtrSetImpl< Loop *> &SimpleLoopNests)
AddUsersImpl - Inspect the specified instruction.
Definition: IVUsers.cpp:168
iterator_range< use_iterator > uses()
Definition: Value.h:355
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:225
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static bool IVUseShouldUsePostIncValue(Instruction *User, Value *Operand, const Loop *L, DominatorTree *DT)
IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression and now we need to decid...
Definition: IVUsers.cpp:129
const SCEV * getReplacementExpr(const IVStrideUse &IU) const
getReplacementExpr - Return a SCEV expression which computes the value of the OperandValToReplace of ...
Definition: IVUsers.cpp:385
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
const SCEV * normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)
Normalize S to be post-increment for all loops present in Loops.
Pass * createIVUsersPass()
Definition: IVUsers.cpp:55
The main scalar evolution driver.
void initializeIVUsersWrapperPassPass(PassRegistry &)
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
block Block Frequency true
iv Induction Variable Users
Definition: IVUsers.cpp:52
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:264
bool AddUsersIfInteresting(Instruction *I)
AddUsersIfInteresting - Inspect the specified Instruction.
Definition: IVUsers.cpp:291
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
static bool isSimplifiedLoopNest(BasicBlock *BB, const DominatorTree *DT, const LoopInfo *LI, SmallPtrSetImpl< Loop *> &SimpleLoopNests)
Return true if all loop headers that dominate this block are in simplified form.
Definition: IVUsers.cpp:95
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:364
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:684
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: IVUsers.cpp:358
#define LLVM_DUMP_METHOD
Definition: Compiler.h:74
BlockT * getHeader() const
Definition: LoopInfo.h:100
void print(raw_ostream &OS, const Module *=nullptr) const
Definition: IVUsers.cpp:319
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
This node represents a polynomial recurrence on the trip count of the specified loop.
This header provides classes for managing per-loop analyses.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: IVUsers.cpp:381
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
const SCEV * normalizeForPostIncUseIf(const SCEV *S, NormalizePredTy Pred, ScalarEvolution &SE)
Normalize S for all add recurrence sub-expressions for which Pred returns true.
const SCEV * getStride(const IVStrideUse &IU, const Loop *L) const
Definition: IVUsers.cpp:412
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
IVUsers run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
Definition: IVUsers.cpp:40
DomTreeNodeBase * getIDom() const
This file contains the declarations for the subclasses of Constant, which represent the different fla...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
Represent the analysis usage information of a pass.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
const PostIncLoopSet & getPostIncLoops() const
getPostIncLoops - Return the set of loops for which the expression has been adjusted to use post-inc ...
Definition: IVUsers.h:69
static unsigned getIncomingValueNumForOperand(unsigned i)
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
Definition: AsmWriter.cpp:4197
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L, ScalarEvolution *SE, LoopInfo *LI)
isInteresting - Test whether the given expression is "interesting" when used by the given expression...
Definition: IVUsers.cpp:60
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
Iterator for intrusive lists based on ilist_node.
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:249
Module.h This file contains the declarations for the Module class.
bool isLegalInteger(uint64_t Width) const
Returns true if the specified type is known to be a native integer type supported by the CPU...
Definition: DataLayout.h:243
unsigned getNumIncomingValues() const
Return the number of incoming edges.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:56
This node represents an addition of some number of SCEVs.
void setPreservesAll()
Set by analyses that do not transform their input at all.
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:560
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:193
iv users
Definition: IVUsers.cpp:52
IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)
Definition: IVUsers.cpp:305
MCExpr const & getExpr(MCExpr const &Expr)
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getOperandValToReplace() const
getOperandValToReplace - Return the Value of the operand in the user instruction that this IVStrideUs...
Definition: IVUsers.h:57
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
void dump() const
dump - This method is used for debugging.
Definition: IVUsers.cpp:346
const SCEV * getExpr(const IVStrideUse &IU) const
getExpr - Return the expression for the use.
Definition: IVUsers.cpp:390
void transformToPostInc(const Loop *L)
transformToPostInc - Transform the expression to post-inc form for the given loop.
Definition: IVUsers.cpp:418
INITIALIZE_PASS_BEGIN(IVUsersWrapperPass, "iv-users", "Induction Variable Users", false, true) INITIALIZE_PASS_END(IVUsersWrapperPass
const SCEV * getBackedgeTakenCount(const Loop *L)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
static const SCEVAddRecExpr * findAddRecForLoop(const SCEV *S, const Loop *L)
Definition: IVUsers.cpp:395
const SCEV * denormalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)
Denormalize S to be post-increment for all loops present in Loops.
LLVM Value Representation.
Definition: Value.h:73
IVStrideUse - Keep track of one use of a strided induction variable.
Definition: IVUsers.h:38
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:964
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
IVStrideUse & AddUser(Instruction *User, Value *Operand)
Definition: IVUsers.cpp:300
#define LLVM_DEBUG(X)
Definition: Debug.h:123
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count...
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:71
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
Definition: IVUsers.cpp:377
const BasicBlock * getParent() const
Definition: Instruction.h:67