LLVM  16.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"
18 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/Analysis/LoopPass.h"
22 #include "llvm/Config/llvm-config.h"
23 #include "llvm/IR/DataLayout.h"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/IR/Instructions.h"
26 #include "llvm/IR/Module.h"
27 #include "llvm/InitializePasses.h"
28 #include "llvm/Support/Debug.h"
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "iv-users"
33 
34 AnalysisKey IVUsersAnalysis::Key;
35 
38  return IVUsers(&L, &AR.AC, &AR.LI, &AR.DT, &AR.SE);
39 }
40 
41 char IVUsersWrapperPass::ID = 0;
43  "Induction Variable Users", false, true)
48 INITIALIZE_PASS_END(IVUsersWrapperPass, "iv-users", "Induction Variable Users",
50 
52 
53 /// isInteresting - Test whether the given expression is "interesting" when
54 /// used by the given expression, within the context of analyzing the
55 /// given loop.
56 static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L,
57  ScalarEvolution *SE, LoopInfo *LI) {
58  // An addrec is interesting if it's affine or if it has an interesting start.
59  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
60  // Keep things simple. Don't touch loop-variant strides unless they're
61  // only used outside the loop and we can simplify them.
62  if (AR->getLoop() == L)
63  return AR->isAffine() ||
64  (!L->contains(I) &&
65  SE->getSCEVAtScope(AR, LI->getLoopFor(I->getParent())) != AR);
66  // Otherwise recurse to see if the start value is interesting, and that
67  // the step value is not interesting, since we don't yet know how to
68  // do effective SCEV expansions for addrecs with interesting steps.
69  return isInteresting(AR->getStart(), I, L, SE, LI) &&
70  !isInteresting(AR->getStepRecurrence(*SE), I, L, SE, LI);
71  }
72 
73  // An add is interesting if exactly one of its operands is interesting.
74  if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
75  bool AnyInterestingYet = false;
76  for (const auto *Op : Add->operands())
77  if (isInteresting(Op, I, L, SE, LI)) {
78  if (AnyInterestingYet)
79  return false;
80  AnyInterestingYet = true;
81  }
82  return AnyInterestingYet;
83  }
84 
85  // Nothing else is interesting here.
86  return false;
87 }
88 
89 /// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression
90 /// and now we need to decide whether the user should use the preinc or post-inc
91 /// value. If this user should use the post-inc version of the IV, return true.
92 ///
93 /// Choosing wrong here can break dominance properties (if we choose to use the
94 /// post-inc value when we cannot) or it can end up adding extra live-ranges to
95 /// the loop, resulting in reg-reg copies (if we use the pre-inc value when we
96 /// should use the post-inc value).
98  const Loop *L, DominatorTree *DT) {
99  // If the user is in the loop, use the preinc value.
100  if (L->contains(User))
101  return false;
102 
103  BasicBlock *LatchBlock = L->getLoopLatch();
104  if (!LatchBlock)
105  return false;
106 
107  // Ok, the user is outside of the loop. If it is dominated by the latch
108  // block, use the post-inc value.
109  if (DT->dominates(LatchBlock, User->getParent()))
110  return true;
111 
112  // There is one case we have to be careful of: PHI nodes. These little guys
113  // can live in blocks that are not dominated by the latch block, but (since
114  // their uses occur in the predecessor block, not the block the PHI lives in)
115  // should still use the post-inc value. Check for this case now.
116  PHINode *PN = dyn_cast<PHINode>(User);
117  if (!PN || !Operand)
118  return false; // not a phi, not dominated by latch block.
119 
120  // Look at all of the uses of Operand by the PHI node. If any use corresponds
121  // to a block that is not dominated by the latch block, give up and use the
122  // preincremented value.
123  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
124  if (PN->getIncomingValue(i) == Operand &&
125  !DT->dominates(LatchBlock, PN->getIncomingBlock(i)))
126  return false;
127 
128  // Okay, all uses of Operand by PN are in predecessor blocks that really are
129  // dominated by the latch block. Use the post-incremented value.
130  return true;
131 }
132 
133 /// Inspect the specified instruction. If it is a reducible SCEV, recursively
134 /// add its users to the IVUsesByStride set and return true. Otherwise, return
135 /// false.
137  const DataLayout &DL = I->getModule()->getDataLayout();
138 
139  // Add this IV user to the Processed set before returning false to ensure that
140  // all IV users are members of the set. See IVUsers::isIVUserOrOperand.
141  if (!Processed.insert(I).second)
142  return true; // Instruction already handled.
143 
144  if (!SE->isSCEVable(I->getType()))
145  return false; // Void and FP expressions cannot be reduced.
146 
147  // IVUsers is used by LSR which assumes that all SCEV expressions are safe to
148  // pass to SCEVExpander. Expressions are not safe to expand if they represent
149  // operations that are not safe to speculate, namely integer division.
150  if (!isa<PHINode>(I) && !isSafeToSpeculativelyExecute(I))
151  return false;
152 
153  // LSR is not APInt clean, do not touch integers bigger than 64-bits.
154  // Also avoid creating IVs of non-native types. For example, we don't want a
155  // 64-bit IV in 32-bit code just because the loop has one 64-bit cast.
156  uint64_t Width = SE->getTypeSizeInBits(I->getType());
157  if (Width > 64 || !DL.isLegalInteger(Width))
158  return false;
159 
160  // Don't attempt to promote ephemeral values to indvars. They will be removed
161  // later anyway.
162  if (EphValues.count(I))
163  return false;
164 
165  // Get the symbolic expression for this instruction.
166  const SCEV *ISE = SE->getSCEV(I);
167 
168  // If we've come to an uninteresting expression, stop the traversal and
169  // call this a user.
170  if (!isInteresting(ISE, I, L, SE, LI))
171  return false;
172 
173  SmallPtrSet<Instruction *, 4> UniqueUsers;
174  for (Use &U : I->uses()) {
175  Instruction *User = cast<Instruction>(U.getUser());
176  if (!UniqueUsers.insert(User).second)
177  continue;
178 
179  // Do not infinitely recurse on PHI nodes.
180  if (isa<PHINode>(User) && Processed.count(User))
181  continue;
182 
183  // Descend recursively, but not into PHI nodes outside the current loop.
184  // It's important to see the entire expression outside the loop to get
185  // choices that depend on addressing mode use right, although we won't
186  // consider references outside the loop in all cases.
187  // If User is already in Processed, we don't want to recurse into it again,
188  // but do want to record a second reference in the same instruction.
189  bool AddUserToIVUsers = false;
190  if (LI->getLoopFor(User->getParent()) != L) {
191  if (isa<PHINode>(User) || Processed.count(User) ||
193  LLVM_DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
194  << " OF SCEV: " << *ISE << '\n');
195  AddUserToIVUsers = true;
196  }
197  } else if (Processed.count(User) || !AddUsersIfInteresting(User)) {
198  LLVM_DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
199  << " OF SCEV: " << *ISE << '\n');
200  AddUserToIVUsers = true;
201  }
202 
203  if (AddUserToIVUsers) {
204  // Okay, we found a user that we cannot reduce.
205  IVStrideUse &NewUse = AddUser(User, I);
206  // Autodetect the post-inc loop set, populating NewUse.PostIncLoops.
207  // The regular return value here is discarded; instead of recording
208  // it, we just recompute it when we need it.
209  const SCEV *OriginalISE = ISE;
210 
211  auto NormalizePred = [&](const SCEVAddRecExpr *AR) {
212  auto *L = AR->getLoop();
213  bool Result = IVUseShouldUsePostIncValue(User, I, L, DT);
214  if (Result)
215  NewUse.PostIncLoops.insert(L);
216  return Result;
217  };
218 
219  ISE = normalizeForPostIncUseIf(ISE, NormalizePred, *SE);
220 
221  // PostIncNormalization effectively simplifies the expression under
222  // pre-increment assumptions. Those assumptions (no wrapping) might not
223  // hold for the post-inc value. Catch such cases by making sure the
224  // transformation is invertible.
225  if (OriginalISE != ISE) {
226  const SCEV *DenormalizedISE =
227  denormalizeForPostIncUse(ISE, NewUse.PostIncLoops, *SE);
228 
229  // If we normalized the expression, but denormalization doesn't give the
230  // original one, discard this user.
231  if (OriginalISE != DenormalizedISE) {
232  LLVM_DEBUG(dbgs()
233  << " DISCARDING (NORMALIZATION ISN'T INVERTIBLE): "
234  << *ISE << '\n');
235  IVUses.pop_back();
236  return false;
237  }
238  }
239  LLVM_DEBUG(if (SE->getSCEV(I) != ISE) dbgs()
240  << " NORMALIZED TO: " << *ISE << '\n');
241  }
242  }
243  return true;
244 }
245 
247  IVUses.push_back(new IVStrideUse(this, User, Operand));
248  return IVUses.back();
249 }
250 
252  ScalarEvolution *SE)
253  : L(L), AC(AC), LI(LI), DT(DT), SE(SE) {
254  // Collect ephemeral values so that AddUsersIfInteresting skips them.
255  EphValues.clear();
256  CodeMetrics::collectEphemeralValues(L, AC, EphValues);
257 
258  // Find all uses of induction variables in this loop, and categorize
259  // them by stride. Start by finding all of the PHI nodes in the header for
260  // this loop. If they are induction variables, inspect their uses.
261  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
262  (void)AddUsersIfInteresting(&*I);
263 }
264 
265 void IVUsers::print(raw_ostream &OS, const Module *M) const {
266  OS << "IV Users for loop ";
267  L->getHeader()->printAsOperand(OS, false);
269  OS << " with backedge-taken count " << *SE->getBackedgeTakenCount(L);
270  }
271  OS << ":\n";
272 
273  for (const IVStrideUse &IVUse : IVUses) {
274  OS << " ";
275  IVUse.getOperandValToReplace()->printAsOperand(OS, false);
276  OS << " = " << *getReplacementExpr(IVUse);
277  for (const auto *PostIncLoop : IVUse.PostIncLoops) {
278  OS << " (post-inc with loop ";
279  PostIncLoop->getHeader()->printAsOperand(OS, false);
280  OS << ")";
281  }
282  OS << " in ";
283  if (IVUse.getUser())
284  IVUse.getUser()->print(OS);
285  else
286  OS << "Printing <null> User";
287  OS << '\n';
288  }
289 }
290 
291 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
293 #endif
294 
296  Processed.clear();
297  IVUses.clear();
298 }
299 
302 }
303 
309  AU.setPreservesAll();
310 }
311 
313  auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
314  *L->getHeader()->getParent());
315  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
316  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
317  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
318 
319  IU.reset(new IVUsers(L, AC, LI, DT, SE));
320  return false;
321 }
322 
323 void IVUsersWrapperPass::print(raw_ostream &OS, const Module *M) const {
324  IU->print(OS, M);
325 }
326 
327 void IVUsersWrapperPass::releaseMemory() { IU->releaseMemory(); }
328 
329 /// getReplacementExpr - Return a SCEV expression which computes the
330 /// value of the OperandValToReplace.
332  return SE->getSCEV(IU.getOperandValToReplace());
333 }
334 
335 /// getExpr - Return the expression for the use.
336 const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {
338  *SE);
339 }
340 
341 static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {
342  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
343  if (AR->getLoop() == L)
344  return AR;
345  return findAddRecForLoop(AR->getStart(), L);
346  }
347 
348  if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
349  for (const auto *Op : Add->operands())
350  if (const SCEVAddRecExpr *AR = findAddRecForLoop(Op, L))
351  return AR;
352  return nullptr;
353  }
354 
355  return nullptr;
356 }
357 
358 const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const {
359  if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L))
360  return AR->getStepRecurrence(*SE);
361  return nullptr;
362 }
363 
365  PostIncLoops.insert(L);
366 }
367 
368 void IVStrideUse::deleted() {
369  // Remove this user from the list.
370  Parent->Processed.erase(this->getUser());
371  Parent->IVUses.erase(this);
372  // this now dangles!
373 }
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:13231
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:492
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:53
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:87
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:138
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:111
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
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:4329
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1835
Module.h
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1290
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:51
llvm::SmallPtrSet< Instruction *, 4 >
llvm::IVStrideUse
IVStrideUse - Keep track of one use of a strided induction variable.
Definition: IVUsers.h:34
llvm::IVUsersWrapperPass::ID
static char ID
Definition: IVUsers.h:165
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:54
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:304
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::IVUsersWrapperPass::IVUsersWrapperPass
IVUsersWrapperPass()
Definition: IVUsers.cpp:300
llvm::initializeIVUsersWrapperPassPass
void initializeIVUsersWrapperPassPass(PassRegistry &)
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
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:53
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:122
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:106
CodeMetrics.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2795
llvm::User
Definition: User.h:44
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:306
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:141
llvm::Instruction
Definition: Instruction.h:42
llvm::IVStrideUse::getUser
Instruction * getUser() const
getUser - Return the user instruction for this use.
Definition: IVUsers.h:42
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::IVUsers::releaseMemory
void releaseMemory()
Definition: IVUsers.cpp:295
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
findAddRecForLoop
static const SCEVAddRecExpr * findAddRecForLoop(const SCEV *S, const Loop *L)
Definition: IVUsers.cpp:341
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:70
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2173
llvm::LPPassManager
Definition: LoopPass.h:76
llvm::IVUsers::IVUsers
IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)
Definition: IVUsers.cpp:251
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:331
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2791
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
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:265
LoopInfo.h
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:65
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4436
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
uint64_t
llvm::LoopPass
Definition: LoopPass.h:28
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:56
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:989
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::IVUsers
Definition: IVUsers.h:90
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:215
llvm::IVUsers::AddUser
IVStrideUse & AddUser(Instruction *User, Value *Operand)
Definition: IVUsers.cpp:246
llvm::IVUsers::getStride
const SCEV * getStride(const IVStrideUse &IU, const Loop *L) const
Definition: IVUsers.cpp:358
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
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:4677
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::LoopInfo
Definition: LoopInfo.h:1105
DataLayout.h
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
LoopPass.h
llvm::IVUsersWrapperPass
Definition: IVUsers.h:161
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::LoopStandardAnalysisResults::LI
LoopInfo & LI
Definition: LoopAnalysisManager.h:55
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:336
users
iv users
Definition: IVUsers.cpp:48
llvm::IVUsersWrapperPass::runOnLoop
bool runOnLoop(Loop *L, LPPassManager &LPM) override
Definition: IVUsers.cpp:312
llvm::IVUsersAnalysis::run
IVUsers run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
Definition: IVUsers.cpp:36
llvm::IVStrideUse::transformToPostInc
void transformToPostInc(const Loop *L)
transformToPostInc - Transform the expression to post-inc form for the given loop.
Definition: IVUsers.cpp:364
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:97
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:342
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:4322
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:56
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:439
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:257
IVUsers.h
llvm::IVUsers::AddUsersIfInteresting
bool AddUsersIfInteresting(Instruction *I)
AddUsersIfInteresting - Inspect the specified Instruction.
Definition: IVUsers.cpp:136
Dominators.h
llvm::createIVUsersPass
Pass * createIVUsersPass()
Definition: IVUsers.cpp:51
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:323
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2815
Users
iv Induction Variable Users
Definition: IVUsers.cpp:48
llvm::PHINode
Definition: Instructions.h:2699
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
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:327
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:97
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:8168
InitializePasses.h
llvm::IVUsers::IVStrideUse
friend class IVStrideUse
Definition: IVUsers.h:91
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:9500
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=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:4733
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:292
Debug.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
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:365