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