LLVM  9.0.0svn
IVUsers.cpp
Go to the documentation of this file.
1 //===- IVUsers.cpp - Induction Variable Users -------------------*- C++ -*-===//
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 file implements bookkeeping for "interesting" users of expressions
10 // computed from induction variables.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/Analysis/IVUsers.h"
15 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/Analysis/LoopPass.h"
22 #include "llvm/Config/llvm-config.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  LLVM_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  LLVM_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  LLVM_DEBUG(dbgs()
277  << " DISCARDING (NORMALIZATION ISN'T INVERTIBLE): "
278  << *ISE << '\n');
279  IVUses.pop_back();
280  return false;
281  }
282  }
283  LLVM_DEBUG(if (SE->getSCEV(I) != ISE) dbgs()
284  << " NORMALIZED TO: " << *ISE << '\n');
285  }
286  }
287  return true;
288 }
289 
291  // SCEVExpander can only handle users that are dominated by simplified loop
292  // entries. Keep track of all loops that are only dominated by other simple
293  // loops so we don't traverse the domtree for each user.
294  SmallPtrSet<Loop*,16> SimpleLoopNests;
295 
296  return AddUsersImpl(I, SimpleLoopNests);
297 }
298 
300  IVUses.push_back(new IVStrideUse(this, User, Operand));
301  return IVUses.back();
302 }
303 
305  ScalarEvolution *SE)
306  : L(L), AC(AC), LI(LI), DT(DT), SE(SE), IVUses() {
307  // Collect ephemeral values so that AddUsersIfInteresting skips them.
308  EphValues.clear();
309  CodeMetrics::collectEphemeralValues(L, AC, EphValues);
310 
311  // Find all uses of induction variables in this loop, and categorize
312  // them by stride. Start by finding all of the PHI nodes in the header for
313  // this loop. If they are induction variables, inspect their uses.
314  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
315  (void)AddUsersIfInteresting(&*I);
316 }
317 
318 void IVUsers::print(raw_ostream &OS, const Module *M) const {
319  OS << "IV Users for loop ";
320  L->getHeader()->printAsOperand(OS, false);
322  OS << " with backedge-taken count " << *SE->getBackedgeTakenCount(L);
323  }
324  OS << ":\n";
325 
326  for (const IVStrideUse &IVUse : IVUses) {
327  OS << " ";
328  IVUse.getOperandValToReplace()->printAsOperand(OS, false);
329  OS << " = " << *getReplacementExpr(IVUse);
330  for (auto PostIncLoop : IVUse.PostIncLoops) {
331  OS << " (post-inc with loop ";
332  PostIncLoop->getHeader()->printAsOperand(OS, false);
333  OS << ")";
334  }
335  OS << " in ";
336  if (IVUse.getUser())
337  IVUse.getUser()->print(OS);
338  else
339  OS << "Printing <null> User";
340  OS << '\n';
341  }
342 }
343 
344 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
346 #endif
347 
349  Processed.clear();
350  IVUses.clear();
351 }
352 
355 }
356 
362  AU.setPreservesAll();
363 }
364 
366  auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
367  *L->getHeader()->getParent());
368  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
369  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
370  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
371 
372  IU.reset(new IVUsers(L, AC, LI, DT, SE));
373  return false;
374 }
375 
376 void IVUsersWrapperPass::print(raw_ostream &OS, const Module *M) const {
377  IU->print(OS, M);
378 }
379 
380 void IVUsersWrapperPass::releaseMemory() { IU->releaseMemory(); }
381 
382 /// getReplacementExpr - Return a SCEV expression which computes the
383 /// value of the OperandValToReplace.
385  return SE->getSCEV(IU.getOperandValToReplace());
386 }
387 
388 /// getExpr - Return the expression for the use.
389 const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {
390  return normalizeForPostIncUse(getReplacementExpr(IU), IU.getPostIncLoops(),
391  *SE);
392 }
393 
394 static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {
395  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
396  if (AR->getLoop() == L)
397  return AR;
398  return findAddRecForLoop(AR->getStart(), L);
399  }
400 
401  if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
402  for (const auto *Op : Add->operands())
403  if (const SCEVAddRecExpr *AR = findAddRecForLoop(Op, L))
404  return AR;
405  return nullptr;
406  }
407 
408  return nullptr;
409 }
410 
411 const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const {
412  if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L))
413  return AR->getStepRecurrence(*SE);
414  return nullptr;
415 }
416 
418  PostIncLoops.insert(L);
419 }
420 
421 void IVStrideUse::deleted() {
422  // Remove this user from the list.
423  Parent->Processed.erase(this->getUser());
424  Parent->IVUses.erase(this);
425  // this now dangles!
426 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
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:70
bool runOnLoop(Loop *L, LPPassManager &LPM) override
Definition: IVUsers.cpp:365
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
void releaseMemory()
Definition: IVUsers.cpp:348
bool AddUsersImpl(Instruction *I, SmallPtrSetImpl< Loop *> &SimpleLoopNests)
AddUsersImpl - Inspect the specified instruction.
Definition: IVUsers.cpp:167
iterator_range< use_iterator > uses()
Definition: Value.h:354
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:211
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:384
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
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 @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:51
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
bool AddUsersIfInteresting(Instruction *I)
AddUsersIfInteresting - Inspect the specified Instruction.
Definition: IVUsers.cpp:290
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
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:369
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:897
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: IVUsers.cpp:357
BlockT * getHeader() const
Definition: LoopInfo.h:102
void print(raw_ostream &OS, const Module *=nullptr) const
Definition: IVUsers.cpp:318
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
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:380
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
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:411
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
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:370
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:381
const PostIncLoopSet & getPostIncLoops() const
getPostIncLoops - Return the set of loops for which the expression has been adjusted to use post-inc ...
Definition: IVUsers.h:68
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:4351
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:112
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:248
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:254
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:55
This node represents an addition of some number of SCEVs.
void setPreservesAll()
Set by analyses that do not transform their input at all.
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:425
iv users
Definition: IVUsers.cpp:51
IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)
Definition: IVUsers.cpp:304
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:506
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:56
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#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:332
void dump() const
dump - This method is used for debugging.
Definition: IVUsers.cpp:345
const SCEV * getExpr(const IVStrideUse &IU) const
getExpr - Return the expression for the use.
Definition: IVUsers.cpp:389
void transformToPostInc(const Loop *L)
transformToPostInc - Transform the expression to post-inc form for the given loop.
Definition: IVUsers.cpp:417
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:394
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:72
IVStrideUse - Keep track of one use of a strided induction variable.
Definition: IVUsers.h:37
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:1177
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
IVStrideUse & AddUser(Instruction *User, Value *Operand)
Definition: IVUsers.cpp:299
#define LLVM_DEBUG(X)
Definition: Debug.h:122
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:376
const BasicBlock * getParent() const
Definition: Instruction.h:66