LLVM  13.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 /// Return true if all loop headers that dominate this block are in simplified
94 /// form.
96  const LoopInfo *LI,
97  SmallPtrSetImpl<Loop*> &SimpleLoopNests) {
98  Loop *NearestLoop = nullptr;
99  for (DomTreeNode *Rung = DT->getNode(BB);
100  Rung; Rung = Rung->getIDom()) {
101  BasicBlock *DomBB = Rung->getBlock();
102  Loop *DomLoop = LI->getLoopFor(DomBB);
103  if (DomLoop && DomLoop->getHeader() == DomBB) {
104  // If we have already checked this loop nest, stop checking.
105  if (SimpleLoopNests.count(DomLoop))
106  break;
107  // If the domtree walk reaches a loop with no preheader, return false.
108  if (!DomLoop->isLoopSimplifyForm())
109  return false;
110  // If we have not already checked this loop nest, remember the loop
111  // header nearest to BB. The nearest loop may not contain BB.
112  if (!NearestLoop)
113  NearestLoop = DomLoop;
114  }
115  }
116  if (NearestLoop)
117  SimpleLoopNests.insert(NearestLoop);
118  return true;
119 }
120 
121 /// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression
122 /// and now we need to decide whether the user should use the preinc or post-inc
123 /// value. If this user should use the post-inc version of the IV, return true.
124 ///
125 /// Choosing wrong here can break dominance properties (if we choose to use the
126 /// post-inc value when we cannot) or it can end up adding extra live-ranges to
127 /// the loop, resulting in reg-reg copies (if we use the pre-inc value when we
128 /// should use the post-inc value).
130  const Loop *L, DominatorTree *DT) {
131  // If the user is in the loop, use the preinc value.
132  if (L->contains(User))
133  return false;
134 
135  BasicBlock *LatchBlock = L->getLoopLatch();
136  if (!LatchBlock)
137  return false;
138 
139  // Ok, the user is outside of the loop. If it is dominated by the latch
140  // block, use the post-inc value.
141  if (DT->dominates(LatchBlock, User->getParent()))
142  return true;
143 
144  // There is one case we have to be careful of: PHI nodes. These little guys
145  // can live in blocks that are not dominated by the latch block, but (since
146  // their uses occur in the predecessor block, not the block the PHI lives in)
147  // should still use the post-inc value. Check for this case now.
148  PHINode *PN = dyn_cast<PHINode>(User);
149  if (!PN || !Operand)
150  return false; // not a phi, not dominated by latch block.
151 
152  // Look at all of the uses of Operand by the PHI node. If any use corresponds
153  // to a block that is not dominated by the latch block, give up and use the
154  // preincremented value.
155  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
156  if (PN->getIncomingValue(i) == Operand &&
157  !DT->dominates(LatchBlock, PN->getIncomingBlock(i)))
158  return false;
159 
160  // Okay, all uses of Operand by PN are in predecessor blocks that really are
161  // dominated by the latch block. Use the post-incremented value.
162  return true;
163 }
164 
165 /// AddUsersImpl - Inspect the specified instruction. If it is a
166 /// reducible SCEV, recursively add its users to the IVUsesByStride set and
167 /// return true. Otherwise, return false.
169  SmallPtrSetImpl<Loop*> &SimpleLoopNests) {
170  const DataLayout &DL = I->getModule()->getDataLayout();
171 
172  // Add this IV user to the Processed set before returning false to ensure that
173  // all IV users are members of the set. See IVUsers::isIVUserOrOperand.
174  if (!Processed.insert(I).second)
175  return true; // Instruction already handled.
176 
177  if (!SE->isSCEVable(I->getType()))
178  return false; // Void and FP expressions cannot be reduced.
179 
180  // IVUsers is used by LSR which assumes that all SCEV expressions are safe to
181  // pass to SCEVExpander. Expressions are not safe to expand if they represent
182  // operations that are not safe to speculate, namely integer division.
183  if (!isa<PHINode>(I) && !isSafeToSpeculativelyExecute(I))
184  return false;
185 
186  // LSR is not APInt clean, do not touch integers bigger than 64-bits.
187  // Also avoid creating IVs of non-native types. For example, we don't want a
188  // 64-bit IV in 32-bit code just because the loop has one 64-bit cast.
189  uint64_t Width = SE->getTypeSizeInBits(I->getType());
190  if (Width > 64 || !DL.isLegalInteger(Width))
191  return false;
192 
193  // Don't attempt to promote ephemeral values to indvars. They will be removed
194  // later anyway.
195  if (EphValues.count(I))
196  return false;
197 
198  // Get the symbolic expression for this instruction.
199  const SCEV *ISE = SE->getSCEV(I);
200 
201  // If we've come to an uninteresting expression, stop the traversal and
202  // call this a user.
203  if (!isInteresting(ISE, I, L, SE, LI))
204  return false;
205 
206  SmallPtrSet<Instruction *, 4> UniqueUsers;
207  for (Use &U : I->uses()) {
208  Instruction *User = cast<Instruction>(U.getUser());
209  if (!UniqueUsers.insert(User).second)
210  continue;
211 
212  // Do not infinitely recurse on PHI nodes.
213  if (isa<PHINode>(User) && Processed.count(User))
214  continue;
215 
216  // Only consider IVUsers that are dominated by simplified loop
217  // headers. Otherwise, SCEVExpander will crash.
218  BasicBlock *UseBB = User->getParent();
219  // A phi's use is live out of its predecessor block.
220  if (PHINode *PHI = dyn_cast<PHINode>(User)) {
221  unsigned OperandNo = U.getOperandNo();
222  unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
223  UseBB = PHI->getIncomingBlock(ValNo);
224  }
225  if (!isSimplifiedLoopNest(UseBB, DT, LI, SimpleLoopNests))
226  return false;
227 
228  // Descend recursively, but not into PHI nodes outside the current loop.
229  // It's important to see the entire expression outside the loop to get
230  // choices that depend on addressing mode use right, although we won't
231  // consider references outside the loop in all cases.
232  // If User is already in Processed, we don't want to recurse into it again,
233  // but do want to record a second reference in the same instruction.
234  bool AddUserToIVUsers = false;
235  if (LI->getLoopFor(User->getParent()) != L) {
236  if (isa<PHINode>(User) || Processed.count(User) ||
237  !AddUsersImpl(User, SimpleLoopNests)) {
238  LLVM_DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
239  << " OF SCEV: " << *ISE << '\n');
240  AddUserToIVUsers = true;
241  }
242  } else if (Processed.count(User) || !AddUsersImpl(User, SimpleLoopNests)) {
243  LLVM_DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
244  << " OF SCEV: " << *ISE << '\n');
245  AddUserToIVUsers = true;
246  }
247 
248  if (AddUserToIVUsers) {
249  // Okay, we found a user that we cannot reduce.
250  IVStrideUse &NewUse = AddUser(User, I);
251  // Autodetect the post-inc loop set, populating NewUse.PostIncLoops.
252  // The regular return value here is discarded; instead of recording
253  // it, we just recompute it when we need it.
254  const SCEV *OriginalISE = ISE;
255 
256  auto NormalizePred = [&](const SCEVAddRecExpr *AR) {
257  auto *L = AR->getLoop();
258  bool Result = IVUseShouldUsePostIncValue(User, I, L, DT);
259  if (Result)
260  NewUse.PostIncLoops.insert(L);
261  return Result;
262  };
263 
264  ISE = normalizeForPostIncUseIf(ISE, NormalizePred, *SE);
265 
266  // PostIncNormalization effectively simplifies the expression under
267  // pre-increment assumptions. Those assumptions (no wrapping) might not
268  // hold for the post-inc value. Catch such cases by making sure the
269  // transformation is invertible.
270  if (OriginalISE != ISE) {
271  const SCEV *DenormalizedISE =
272  denormalizeForPostIncUse(ISE, NewUse.PostIncLoops, *SE);
273 
274  // If we normalized the expression, but denormalization doesn't give the
275  // original one, discard this user.
276  if (OriginalISE != DenormalizedISE) {
277  LLVM_DEBUG(dbgs()
278  << " DISCARDING (NORMALIZATION ISN'T INVERTIBLE): "
279  << *ISE << '\n');
280  IVUses.pop_back();
281  return false;
282  }
283  }
284  LLVM_DEBUG(if (SE->getSCEV(I) != ISE) dbgs()
285  << " NORMALIZED TO: " << *ISE << '\n');
286  }
287  }
288  return true;
289 }
290 
292  // SCEVExpander can only handle users that are dominated by simplified loop
293  // entries. Keep track of all loops that are only dominated by other simple
294  // loops so we don't traverse the domtree for each user.
295  SmallPtrSet<Loop*,16> SimpleLoopNests;
296 
297  return AddUsersImpl(I, SimpleLoopNests);
298 }
299 
301  IVUses.push_back(new IVStrideUse(this, User, Operand));
302  return IVUses.back();
303 }
304 
306  ScalarEvolution *SE)
307  : L(L), AC(AC), LI(LI), DT(DT), SE(SE), IVUses() {
308  // Collect ephemeral values so that AddUsersIfInteresting skips them.
309  EphValues.clear();
310  CodeMetrics::collectEphemeralValues(L, AC, EphValues);
311 
312  // Find all uses of induction variables in this loop, and categorize
313  // them by stride. Start by finding all of the PHI nodes in the header for
314  // this loop. If they are induction variables, inspect their uses.
315  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
316  (void)AddUsersIfInteresting(&*I);
317 }
318 
319 void IVUsers::print(raw_ostream &OS, const Module *M) const {
320  OS << "IV Users for loop ";
321  L->getHeader()->printAsOperand(OS, false);
323  OS << " with backedge-taken count " << *SE->getBackedgeTakenCount(L);
324  }
325  OS << ":\n";
326 
327  for (const IVStrideUse &IVUse : IVUses) {
328  OS << " ";
329  IVUse.getOperandValToReplace()->printAsOperand(OS, false);
330  OS << " = " << *getReplacementExpr(IVUse);
331  for (auto PostIncLoop : IVUse.PostIncLoops) {
332  OS << " (post-inc with loop ";
333  PostIncLoop->getHeader()->printAsOperand(OS, false);
334  OS << ")";
335  }
336  OS << " in ";
337  if (IVUse.getUser())
338  IVUse.getUser()->print(OS);
339  else
340  OS << "Printing <null> User";
341  OS << '\n';
342  }
343 }
344 
345 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
347 #endif
348 
350  Processed.clear();
351  IVUses.clear();
352 }
353 
356 }
357 
363  AU.setPreservesAll();
364 }
365 
367  auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
368  *L->getHeader()->getParent());
369  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
370  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
371  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
372 
373  IU.reset(new IVUsers(L, AC, LI, DT, SE));
374  return false;
375 }
376 
377 void IVUsersWrapperPass::print(raw_ostream &OS, const Module *M) const {
378  IU->print(OS, M);
379 }
380 
381 void IVUsersWrapperPass::releaseMemory() { IU->releaseMemory(); }
382 
383 /// getReplacementExpr - Return a SCEV expression which computes the
384 /// value of the OperandValToReplace.
386  return SE->getSCEV(IU.getOperandValToReplace());
387 }
388 
389 /// getExpr - Return the expression for the use.
390 const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {
392  *SE);
393 }
394 
395 static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {
396  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
397  if (AR->getLoop() == L)
398  return AR;
399  return findAddRecForLoop(AR->getStart(), L);
400  }
401 
402  if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
403  for (const auto *Op : Add->operands())
404  if (const SCEVAddRecExpr *AR = findAddRecForLoop(Op, L))
405  return AR;
406  return nullptr;
407  }
408 
409  return nullptr;
410 }
411 
412 const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const {
413  if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L))
414  return AR->getStepRecurrence(*SE);
415  return nullptr;
416 }
417 
419  PostIncLoops.insert(L);
420 }
421 
422 void IVStrideUse::deleted() {
423  // Remove this user from the list.
424  Parent->Processed.erase(this->getUser());
425  Parent->IVUses.erase(this);
426  // this now dangles!
427 }
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:12230
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:499
llvm
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:112
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:4541
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:443
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:3766
Module.h
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1258
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::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
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:171
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
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:358
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
llvm::IVUsersWrapperPass::IVUsersWrapperPass
IVUsersWrapperPass()
Definition: IVUsers.cpp:354
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:132
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
isSimplifiedLoopNest
static bool isSimplifiedLoopNest(BasicBlock *BB, const DominatorTree *DT, const LoopInfo *LI, SmallPtrSetImpl< Loop * > &SimpleLoopNests)
Return true if all loop headers that dominate this block are in simplified form.
Definition: IVUsers.cpp:95
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:2668
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:281
llvm::IVUsers::releaseMemory
void releaseMemory()
Definition: IVUsers.cpp:349
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
findAddRecForLoop
static const SCEVAddRecExpr * findAddRecForLoop(const SCEV *S, const Loop *L)
Definition: IVUsers.cpp:395
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:2104
llvm::LPPassManager
Definition: LoopPass.h:75
llvm::IVUsers::IVUsers
IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)
Definition: IVUsers.cpp:305
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:385
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2664
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:319
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:3893
llvm::PHINode::getIncomingValueNumForOperand
static unsigned getIncomingValueNumForOperand(unsigned i)
Definition: Instructions.h:2682
llvm::Loop::isLoopSimplifyForm
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:478
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
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:964
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:300
llvm::IVUsers::getStride
const SCEV * getStride(const IVStrideUse &IU, const Loop *L) const
Definition: IVUsers.cpp:412
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::IVUsers::AddUsersImpl
bool AddUsersImpl(Instruction *I, SmallPtrSetImpl< Loop * > &SimpleLoopNests)
AddUsersImpl - Inspect the specified instruction.
Definition: IVUsers.cpp:168
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:4691
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:1080
DataLayout.h
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
LoopPass.h
llvm::IVUsersWrapperPass
Definition: IVUsers.h:167
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::DomTreeNodeBase< BasicBlock >
llvm::IVUsers::getExpr
const SCEV * getExpr(const IVStrideUse &IU) const
getExpr - Return the expression for the use.
Definition: IVUsers.cpp:390
users
iv users
Definition: IVUsers.cpp:52
llvm::IVUsersWrapperPass::runOnLoop
bool runOnLoop(Loop *L, LPPassManager &LPM) override
Definition: IVUsers.cpp:366
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:418
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:314
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:3759
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:57
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:403
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:262
IVUsers.h
llvm::IVUsers::AddUsersIfInteresting
bool AddUsersIfInteresting(Instruction *I)
AddUsersIfInteresting - Inspect the specified Instruction.
Definition: IVUsers.cpp:291
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:377
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2688
Users
iv Induction Variable Users
Definition: IVUsers.cpp:52
llvm::PHINode
Definition: Instructions.h:2572
DerivedTypes.h
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
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:381
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
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:129
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:7041
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1797
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:8452
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::IVUsers::dump
void dump() const
dump - This method is used for debugging.
Definition: IVUsers.cpp:346
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:38