LLVM  14.0.0git
IVUsers.h
Go to the documentation of this file.
1 //===- llvm/Analysis/IVUsers.h - 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 #ifndef LLVM_ANALYSIS_IVUSERS_H
15 #define LLVM_ANALYSIS_IVUSERS_H
16 
18 #include "llvm/Analysis/LoopPass.h"
20 #include "llvm/IR/ValueHandle.h"
21 
22 namespace llvm {
23 
24 class AssumptionCache;
25 class DominatorTree;
26 class Instruction;
27 class Value;
28 class ScalarEvolution;
29 class SCEV;
30 class IVUsers;
31 class DataLayout;
32 
33 /// IVStrideUse - Keep track of one use of a strided induction variable.
34 /// The Expr member keeps track of the expression, User is the actual user
35 /// instruction of the operand, and 'OperandValToReplace' is the operand of
36 /// the User that is the use.
37 class IVStrideUse final : public CallbackVH, public ilist_node<IVStrideUse> {
38  friend class IVUsers;
39 public:
41  : CallbackVH(U), Parent(P), OperandValToReplace(O) {
42  }
43 
44  /// getUser - Return the user instruction for this use.
45  Instruction *getUser() const {
46  return cast<Instruction>(getValPtr());
47  }
48 
49  /// setUser - Assign a new user instruction for this use.
50  void setUser(Instruction *NewUser) {
51  setValPtr(NewUser);
52  }
53 
54  /// getOperandValToReplace - Return the Value of the operand in the user
55  /// instruction that this IVStrideUse is representing.
57  return OperandValToReplace;
58  }
59 
60  /// setOperandValToReplace - Assign a new Value as the operand value
61  /// to replace.
63  OperandValToReplace = Op;
64  }
65 
66  /// getPostIncLoops - Return the set of loops for which the expression has
67  /// been adjusted to use post-inc mode.
69  return PostIncLoops;
70  }
71 
72  /// transformToPostInc - Transform the expression to post-inc form for the
73  /// given loop.
74  void transformToPostInc(const Loop *L);
75 
76 private:
77  /// Parent - a pointer to the IVUsers that owns this IVStrideUse.
78  IVUsers *Parent;
79 
80  /// OperandValToReplace - The Value of the operand in the user instruction
81  /// that this IVStrideUse is representing.
82  WeakTrackingVH OperandValToReplace;
83 
84  /// PostIncLoops - The set of loops for which Expr has been adjusted to
85  /// use post-inc mode. This corresponds with SCEVExpander's post-inc concept.
86  PostIncLoopSet PostIncLoops;
87 
88  /// Deleted - Implementation of CallbackVH virtual function to
89  /// receive notification when the User is deleted.
90  void deleted() override;
91 };
92 
93 class IVUsers {
94  friend class IVStrideUse;
95  Loop *L;
96  AssumptionCache *AC;
97  LoopInfo *LI;
98  DominatorTree *DT;
99  ScalarEvolution *SE;
101 
102  /// IVUses - A list of all tracked IV uses of induction variable expressions
103  /// we are interested in.
104  ilist<IVStrideUse> IVUses;
105 
106  // Ephemeral values used by @llvm.assume in this function.
108 
109 public:
111  ScalarEvolution *SE);
112 
114  : L(std::move(X.L)), AC(std::move(X.AC)), DT(std::move(X.DT)),
115  SE(std::move(X.SE)), Processed(std::move(X.Processed)),
116  IVUses(std::move(X.IVUses)), EphValues(std::move(X.EphValues)) {
117  for (IVStrideUse &U : IVUses)
118  U.Parent = this;
119  }
120  IVUsers(const IVUsers &) = delete;
121  IVUsers &operator=(IVUsers &&) = delete;
122  IVUsers &operator=(const IVUsers &) = delete;
123 
124  Loop *getLoop() const { return L; }
125 
126  /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a
127  /// reducible SCEV, recursively add its users to the IVUsesByStride set and
128  /// return true. Otherwise, return false.
130 
132 
133  /// getReplacementExpr - Return a SCEV expression which computes the
134  /// value of the OperandValToReplace of the given IVStrideUse.
135  const SCEV *getReplacementExpr(const IVStrideUse &IU) const;
136 
137  /// getExpr - Return the expression for the use.
138  const SCEV *getExpr(const IVStrideUse &IU) const;
139 
140  const SCEV *getStride(const IVStrideUse &IU, const Loop *L) const;
141 
144  iterator begin() { return IVUses.begin(); }
145  iterator end() { return IVUses.end(); }
146  const_iterator begin() const { return IVUses.begin(); }
147  const_iterator end() const { return IVUses.end(); }
148  bool empty() const { return IVUses.empty(); }
149 
150  bool isIVUserOrOperand(Instruction *Inst) const {
151  return Processed.count(Inst);
152  }
153 
154  void releaseMemory();
155 
156  void print(raw_ostream &OS, const Module * = nullptr) const;
157 
158  /// dump - This method is used for debugging.
159  void dump() const;
160 
161 protected:
162  bool AddUsersImpl(Instruction *I, SmallPtrSetImpl<Loop*> &SimpleLoopNests);
163 };
164 
166 
167 class IVUsersWrapperPass : public LoopPass {
168  std::unique_ptr<IVUsers> IU;
169 
170 public:
171  static char ID;
172 
174 
175  IVUsers &getIU() { return *IU; }
176  const IVUsers &getIU() const { return *IU; }
177 
178  void getAnalysisUsage(AnalysisUsage &AU) const override;
179 
180  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
181 
182  void releaseMemory() override;
183 
184  void print(raw_ostream &OS, const Module * = nullptr) const override;
185 };
186 
187 /// Analysis pass that exposes the \c IVUsers for a loop.
188 class IVUsersAnalysis : public AnalysisInfoMixin<IVUsersAnalysis> {
190  static AnalysisKey Key;
191 
192 public:
193  typedef IVUsers Result;
194 
197 };
198 
199 }
200 
201 #endif
llvm::IVStrideUse::setOperandValToReplace
void setOperandValToReplace(Value *Op)
setOperandValToReplace - Assign a new Value as the operand value to replace.
Definition: IVUsers.h:62
llvm::IVUsersAnalysis
Analysis pass that exposes the IVUsers for a loop.
Definition: IVUsers.h:188
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
Pass
print lazy value Lazy Value Info Printer Pass
Definition: LazyValueInfo.cpp:1966
llvm::WeakTrackingVH
Value handle that is nullable, but tries to track the Value.
Definition: ValueHandle.h:204
ScalarEvolutionNormalization.h
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:461
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::IVUsers::const_iterator
ilist< IVStrideUse >::const_iterator const_iterator
Definition: IVUsers.h:143
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::ValueHandleBase::getValPtr
Value * getValPtr() const
Definition: ValueHandle.h:99
llvm::SmallPtrSet< const Loop *, 2 >
llvm::IVStrideUse
IVStrideUse - Keep track of one use of a strided induction variable.
Definition: IVUsers.h:37
llvm::IVUsersWrapperPass::ID
static char ID
Definition: IVUsers.h:171
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::iplist
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
Definition: ilist.h:390
llvm::IVUsersWrapperPass::IVUsersWrapperPass
IVUsersWrapperPass()
Definition: IVUsers.cpp:354
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::IVUsers::end
const_iterator end() const
Definition: IVUsers.h:147
llvm::User
Definition: User.h:44
llvm::IVStrideUse::setUser
void setUser(Instruction *NewUser)
setUser - Assign a new user instruction for this use.
Definition: IVUsers.h:50
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::IVUsers::iterator
ilist< IVStrideUse >::iterator iterator
Definition: IVUsers.h:142
llvm::IVUsers::isIVUserOrOperand
bool isIVUserOrOperand(Instruction *Inst) const
Definition: IVUsers.h:150
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::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::IVUsers::releaseMemory
void releaseMemory()
Definition: IVUsers.cpp:349
llvm::IVUsers::begin
iterator begin()
Definition: IVUsers.h:144
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
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::IVUsers::getLoop
Loop * getLoop() const
Definition: IVUsers.h:124
llvm::IVUsersWrapperPass::getIU
IVUsers & getIU()
Definition: IVUsers.h:175
llvm::IVUsers::print
void print(raw_ostream &OS, const Module *=nullptr) const
Definition: IVUsers.cpp:319
llvm::IVUsers::IVUsers
IVUsers(IVUsers &&X)
Definition: IVUsers.h:113
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::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:192
llvm::IVUsers::operator=
IVUsers & operator=(IVUsers &&)=delete
llvm::IVUsersWrapperPass::getIU
const IVUsers & getIU() const
Definition: IVUsers.h:176
llvm::LoopPass
Definition: LoopPass.h:27
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::IVUsers
Definition: IVUsers.h:93
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::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1609
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:397
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::IVUsers::empty
bool empty() const
Definition: IVUsers.h:148
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
LoopPass.h
llvm::IVUsersWrapperPass
Definition: IVUsers.h:167
llvm::IVUsers::begin
const_iterator begin() const
Definition: IVUsers.h:146
ValueHandle.h
llvm::IVUsers::getExpr
const SCEV * getExpr(const IVStrideUse &IU) const
getExpr - Return the expression for the use.
Definition: IVUsers.cpp:390
llvm::IVUsersWrapperPass::runOnLoop
bool runOnLoop(Loop *L, LPPassManager &LPM) override
Definition: IVUsers.cpp:366
llvm::ilist_node
Definition: ilist_node.h:148
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
std
Definition: BitVector.h:838
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::IVUsers::end
iterator end()
Definition: IVUsers.h:145
llvm::CallbackVH
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:383
llvm::CallbackVH::setValPtr
void setValPtr(Value *P)
Definition: ValueHandle.h:390
llvm::IVStrideUse::IVStrideUse
IVStrideUse(IVUsers *P, Instruction *U, Value *O)
Definition: IVUsers.h:40
llvm::IVUsers::AddUsersIfInteresting
bool AddUsersIfInteresting(Instruction *I)
AddUsersIfInteresting - Inspect the specified Instruction.
Definition: IVUsers.cpp:291
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::IVUsersAnalysis::Result
IVUsers Result
Definition: IVUsers.h:193
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
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