LLVM  14.0.0git
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/InitializePasses.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",
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 /// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression
94 /// and now we need to decide whether the user should use the preinc or post-inc
95 /// value. If this user should use the post-inc version of the IV, return true.
96 ///
97 /// Choosing wrong here can break dominance properties (if we choose to use the
98 /// post-inc value when we cannot) or it can end up adding extra live-ranges to
99 /// the loop, resulting in reg-reg copies (if we use the pre-inc value when we
100 /// should use the post-inc value).
102  const Loop *L, DominatorTree *DT) {
103  // If the user is in the loop, use the preinc value.
104  if (L->contains(User))
105  return false;
106 
107  BasicBlock *LatchBlock = L->getLoopLatch();
108  if (!LatchBlock)
109  return false;
110 
111  // Ok, the user is outside of the loop. If it is dominated by the latch
112  // block, use the post-inc value.
113  if (DT->dominates(LatchBlock, User->getParent()))
114  return true;
115 
116  // There is one case we have to be careful of: PHI nodes. These little guys
117  // can live in blocks that are not dominated by the latch block, but (since
118  // their uses occur in the predecessor block, not the block the PHI lives in)
119  // should still use the post-inc value. Check for this case now.
120  PHINode *PN = dyn_cast<PHINode>(User);
121  if (!PN || !Operand)
122  return false; // not a phi, not dominated by latch block.
123 
124  // Look at all of the uses of Operand by the PHI node. If any use corresponds
125  // to a block that is not dominated by the latch block, give up and use the
126  // preincremented value.
127  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
128  if (PN->getIncomingValue(i) == Operand &&
129  !DT->dominates(LatchBlock, PN->getIncomingBlock(i)))
130  return false;
131 
132  // Okay, all uses of Operand by PN are in predecessor blocks that really are
133  // dominated by the latch block. Use the post-incremented value.
134  return true;
135 }
136 
137 /// Inspect the specified instruction. If it is a reducible SCEV, recursively
138 /// add its users to the IVUsesByStride set and return true. Otherwise, return
139 /// false.
141  const DataLayout &DL = I->getModule()->getDataLayout();
142 
143  // Add this IV user to the Processed set before returning false to ensure that
144  // all IV users are members of the set. See IVUsers::isIVUserOrOperand.
145  if (!Processed.insert(I).second)
146  return true; // Instruction already handled.
147 
148  if (!SE->isSCEVable(I->getType()))
149  return false; // Void and FP expressions cannot be reduced.
150 
151  // IVUsers is used by LSR which assumes that all SCEV expressions are safe to
152  // pass to SCEVExpander. Expressions are not safe to expand if they represent
153  // operations that are not safe to speculate, namely integer division.
154  if (!isa<PHINode>(I) && !isSafeToSpeculativelyExecute(I))
155  return false;
156 
157  // LSR is not APInt clean, do not touch integers bigger than 64-bits.
158  // Also avoid creating IVs of non-native types. For example, we don't want a
159  // 64-bit IV in 32-bit code just because the loop has one 64-bit cast.
160  uint64_t Width = SE->getTypeSizeInBits(I->getType());
161  if (Width > 64 || !DL.isLegalInteger(Width))
162  return false;
163 
164  // Don't attempt to promote ephemeral values to indvars. They will be removed
165  // later anyway.
166  if (EphValues.count(I))
167  return false;
168 
169  // Get the symbolic expression for this instruction.
170  const SCEV *ISE = SE->getSCEV(I);
171 
172  // If we've come to an uninteresting expression, stop the traversal and
173  // call this a user.
174  if (!isInteresting(ISE, I, L, SE, LI))
175  return false;
176 
177  SmallPtrSet<Instruction *, 4> UniqueUsers;
178  for (Use &U : I->uses()) {
179  Instruction *User = cast<Instruction>(U.getUser());
180  if (!UniqueUsers.insert(User).second)
181  continue;
182 
183  // Do not infinitely recurse on PHI nodes.
184  if (isa<PHINode>(User) && Processed.count(User))
185  continue;
186 
187  // Descend recursively, but not into PHI nodes outside the current loop.
188  // It's important to see the entire expression outside the loop to get
189  // choices that depend on addressing mode use right, although we won't
190  // consider references outside the loop in all cases.
191  // If User is already in Processed, we don't want to recurse into it again,
192  // but do want to record a second reference in the same instruction.
193  bool AddUserToIVUsers = false;
194  if (LI->getLoopFor(User->getParent()) != L) {
195  if (isa<PHINode>(User) || Processed.count(User) ||
197  LLVM_DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
198  << " OF SCEV: " << *ISE << '\n');
199  AddUserToIVUsers = true;
200  }
201  } else if (Processed.count(User) || !AddUsersIfInteresting(User)) {
202  LLVM_DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
203  << " OF SCEV: " << *ISE << '\n');
204  AddUserToIVUsers = true;
205  }
206 
207  if (AddUserToIVUsers) {
208  // Okay, we found a user that we cannot reduce.
209  IVStrideUse &NewUse = AddUser(User, I);
210  // Autodetect the post-inc loop set, populating NewUse.PostIncLoops.
211  // The regular return value here is discarded; instead of recording
212  // it, we just recompute it when we need it.
213  const SCEV *OriginalISE = ISE;
214 
215  auto NormalizePred = [&](const SCEVAddRecExpr *AR) {
216  auto *L = AR->getLoop();
217  bool Result = IVUseShouldUsePostIncValue(User, I, L, DT);
218  if (Result)
219  NewUse.PostIncLoops.insert(L);
220  return Result;
221  };
222 
223  ISE = normalizeForPostIncUseIf(ISE, NormalizePred, *SE);
224 
225  // PostIncNormalization effectively simplifies the expression under
226  // pre-increment assumptions. Those assumptions (no wrapping) might not
227  // hold for the post-inc value. Catch such cases by making sure the
228  // transformation is invertible.
229  if (OriginalISE != ISE) {
230  const SCEV *DenormalizedISE =
231  denormalizeForPostIncUse(ISE, NewUse.PostIncLoops, *SE);
232 
233  // If we normalized the expression, but denormalization doesn't give the
234  // original one, discard this user.
235  if (OriginalISE != DenormalizedISE) {
236  LLVM_DEBUG(dbgs()
237  << " DISCARDING (NORMALIZATION ISN'T INVERTIBLE): "
238  << *ISE << '\n');
239  IVUses.pop_back();
240  return false;
241  }
242  }
243  LLVM_DEBUG(if (SE->getSCEV(I) != ISE) dbgs()
244  << " NORMALIZED TO: " << *ISE << '\n');
245  }
246  }
247  return true;
248 }
249 
251  IVUses.push_back(new IVStrideUse(this, User, Operand));
252  return IVUses.back();
253 }
254 
256  ScalarEvolution *SE)
257  : L(L), AC(AC), LI(LI), DT(DT), SE(SE), IVUses() {
258  // Collect ephemeral values so that AddUsersIfInteresting skips them.
259  EphValues.clear();
260  CodeMetrics::collectEphemeralValues(L, AC, EphValues);
261 
262  // Find all uses of induction variables in this loop, and categorize
263  // them by stride. Start by finding all of the PHI nodes in the header for
264  // this loop. If they are induction variables, inspect their uses.
265  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
266  (void)AddUsersIfInteresting(&*I);
267 }
268 
269 void IVUsers::print(raw_ostream &OS, const Module *M) const {
270  OS << "IV Users for loop ";
271  L->getHeader()->printAsOperand(OS, false);
273  OS << " with backedge-taken count " << *SE->getBackedgeTakenCount(L);
274  }
275  OS << ":\n";
276 
277  for (const IVStrideUse &IVUse : IVUses) {
278  OS << " ";
279  IVUse.getOperandValToReplace()->printAsOperand(OS, false);
280  OS << " = " << *getReplacementExpr(IVUse);
281  for (auto PostIncLoop : IVUse.PostIncLoops) {
282  OS << " (post-inc with loop ";
283  PostIncLoop->getHeader()->printAsOperand(OS, false);
284  OS << ")";
285  }
286  OS << " in ";
287  if (IVUse.getUser())
288  IVUse.getUser()->print(OS);
289  else
290  OS << "Printing <null> User";
291  OS << '\n';
292  }
293 }
294 
295 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
297 #endif
298 
300  Processed.clear();
301  IVUses.clear();
302 }
303 
306 }
307 
313  AU.setPreservesAll();
314 }
315 
317  auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
318  *L->getHeader()->getParent());
319  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
320  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
321  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
322 
323  IU.reset(new IVUsers(L, AC, LI, DT, SE));
324  return false;
325 }
326 
327 void IVUsersWrapperPass::print(raw_ostream &OS, const Module *M) const {
328  IU->print(OS, M);
329 }
330 
331 void IVUsersWrapperPass::releaseMemory() { IU->releaseMemory(); }
332 
333 /// getReplacementExpr - Return a SCEV expression which computes the
334 /// value of the OperandValToReplace.
336  return SE->getSCEV(IU.getOperandValToReplace());
337 }
338 
339 /// getExpr - Return the expression for the use.
340 const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {
342  *SE);
343 }
344 
345 static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {
346  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
347  if (AR->getLoop() == L)
348  return AR;
349  return findAddRecForLoop(AR->getStart(), L);
350  }
351 
352  if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
353  for (const auto *Op : Add->operands())
354  if (const SCEVAddRecExpr *AR = findAddRecForLoop(Op, L))
355  return AR;
356  return nullptr;
357  }
358 
359  return nullptr;
360 }
361 
362 const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const {
363  if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L))
364  return AR->getStepRecurrence(*SE);
365  return nullptr;
366 }
367 
369  PostIncLoops.insert(L);
370 }
371 
372 void IVStrideUse::deleted() {
373  // Remove this user from the list.
374  Parent->Processed.erase(this->getUser());
375  Parent->IVUses.erase(this);
376  // this now dangles!
377 }
i
i
Definition: README.txt:29
AssumptionCache.h
llvm::ScalarEvolution::hasLoopInvariantBackedgeTakenCount
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
Definition: ScalarEvolution.cpp:12365
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:506
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::LoopStandardAnalysisResults::AC
AssumptionCache & AC
Definition: LoopAnalysisManager.h:54
llvm::SmallPtrSetImpl::erase
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:378
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Definition: ValueTracking.cpp:4622
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
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
llvm::denormalizeForPostIncUse
const SCEV * denormalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)
Denormalize S to be post-increment for all loops present in Loops.
Definition: ScalarEvolutionNormalization.cpp:110
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::ScalarEvolution::getTypeSizeInBits
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
Definition: ScalarEvolution.cpp:3973
Module.h
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1268
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:52
llvm::SmallPtrSet< Instruction *, 4 >
llvm::IVStrideUse
IVStrideUse - Keep track of one use of a strided induction variable.
Definition: IVUsers.h:37
STLExtras.h
llvm::IVUsersWrapperPass::ID
static char ID
Definition: IVUsers.h:168
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:55
llvm::IVUsersWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: IVUsers.cpp:308
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::IVUsersWrapperPass::IVUsersWrapperPass
IVUsersWrapperPass()
Definition: IVUsers.cpp:304
llvm::initializeIVUsersWrapperPassPass
void initializeIVUsersWrapperPassPass(PassRegistry &)
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
LoopAnalysisManager.h
llvm::IVStrideUse::getOperandValToReplace
Value * getOperandValToReplace() const
getOperandValToReplace - Return the Value of the operand in the user instruction that this IVStrideUs...
Definition: IVUsers.h:56
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
llvm::normalizeForPostIncUseIf
const SCEV * normalizeForPostIncUseIf(const SCEV *S, NormalizePredTy Pred, ScalarEvolution &SE)
Normalize S for all add recurrence sub-expressions for which Pred returns true.
Definition: ScalarEvolutionNormalization.cpp:105
CodeMetrics.h
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::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2729
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::IVStrideUse::getUser
Instruction * getUser() const
getUser - Return the user instruction for this use.
Definition: IVUsers.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::IVUsers::releaseMemory
void releaseMemory()
Definition: IVUsers.cpp:299
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
findAddRecForLoop
static const SCEVAddRecExpr * findAddRecForLoop(const SCEV *S, const Loop *L)
Definition: IVUsers.cpp:345
llvm::CodeMetrics::collectEphemeralValues
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
Definition: CodeMetrics.cpp:71
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2091
llvm::LPPassManager
Definition: LoopPass.h:75
llvm::IVUsers::IVUsers
IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)
Definition: IVUsers.cpp:255
llvm::IVUsers::getReplacementExpr
const SCEV * getReplacementExpr(const IVStrideUse &IU) const
getReplacementExpr - Return a SCEV expression which computes the value of the OperandValToReplace of ...
Definition: IVUsers.cpp:335
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2725
Type.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::IVUsers::print
void print(raw_ostream &OS, const Module *=nullptr) const
Definition: IVUsers.cpp:269
llvm::IVStrideUse::getPostIncLoops
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
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4082
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:77
uint64_t
llvm::LoopPass
Definition: LoopPass.h:27
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(IVUsersWrapperPass, "iv-users", "Induction Variable Users", false, true) INITIALIZE_PASS_END(IVUsersWrapperPass
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
isInteresting
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
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:967
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::IVUsers
Definition: IVUsers.h:93
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
llvm::IVUsers::AddUser
IVStrideUse & AddUser(Instruction *User, Value *Operand)
Definition: IVUsers.cpp:250
llvm::IVUsers::getStride
const SCEV * getStride(const IVStrideUse &IU, const Loop *L) const
Definition: IVUsers.cpp:362
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::Value::printAsOperand
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:4676
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:200
llvm::LoopInfo
Definition: LoopInfo.h:1083
DataLayout.h
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
LoopPass.h
llvm::IVUsersWrapperPass
Definition: IVUsers.h:164
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::LoopStandardAnalysisResults::LI
LoopInfo & LI
Definition: LoopAnalysisManager.h:56
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::IVUsers::getExpr
const SCEV * getExpr(const IVStrideUse &IU) const
getExpr - Return the expression for the use.
Definition: IVUsers.cpp:340
users
iv users
Definition: IVUsers.cpp:52
llvm::IVUsersWrapperPass::runOnLoop
bool runOnLoop(Loop *L, LPPassManager &LPM) override
Definition: IVUsers.cpp:316
llvm::IVUsersAnalysis::run
IVUsers run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
Definition: IVUsers.cpp:40
llvm::IVStrideUse::transformToPostInc
void transformToPostInc(const Loop *L)
transformToPostInc - Transform the expression to post-inc form for the given loop.
Definition: IVUsers.cpp:368
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::normalizeForPostIncUse
const SCEV * normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)
Normalize S to be post-increment for all loops present in Loops.
Definition: ScalarEvolutionNormalization.cpp:96
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:324
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:352
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::ScalarEvolution::isSCEVable
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Definition: ScalarEvolution.cpp:3966
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:57
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:413
ScalarEvolutionExpressions.h
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
Instructions.h
llvm::SCEVAddExpr
This node represents an addition of some number of SCEVs.
Definition: ScalarEvolutionExpressions.h:260
IVUsers.h
llvm::IVUsers::AddUsersIfInteresting
bool AddUsersIfInteresting(Instruction *I)
AddUsersIfInteresting - Inspect the specified Instruction.
Definition: IVUsers.cpp:140
Dominators.h
llvm::createIVUsersPass
Pass * createIVUsersPass()
Definition: IVUsers.cpp:55
llvm::IVUsersWrapperPass::print
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
Definition: IVUsers.cpp:327
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2749
Users
iv Induction Variable Users
Definition: IVUsers.cpp:52
llvm::PHINode
Definition: Instructions.h:2633
DerivedTypes.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::IVUsersWrapperPass::releaseMemory
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:331
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
IVUseShouldUsePostIncValue
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:101
raw_ostream.h
llvm::ScalarEvolution::getBackedgeTakenCount
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
Definition: ScalarEvolution.cpp:7349
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1925
InitializePasses.h
llvm::IVUsers::IVStrideUse
friend class IVStrideUse
Definition: IVUsers.h:94
llvm::ScalarEvolution::getSCEVAtScope
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
Definition: ScalarEvolution.cpp:8707
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::IVUsers::dump
void dump() const
dump - This method is used for debugging.
Definition: IVUsers.cpp:296
Debug.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SmallPtrSetImpl::insert
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:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37