LLVM  16.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 ScalarEvolution;
27 class SCEV;
28 class IVUsers;
29 
30 /// IVStrideUse - Keep track of one use of a strided induction variable.
31 /// The Expr member keeps track of the expression, User is the actual user
32 /// instruction of the operand, and 'OperandValToReplace' is the operand of
33 /// the User that is the use.
34 class IVStrideUse final : public CallbackVH, public ilist_node<IVStrideUse> {
35  friend class IVUsers;
36 public:
38  : CallbackVH(U), Parent(P), OperandValToReplace(O) {
39  }
40 
41  /// getUser - Return the user instruction for this use.
42  Instruction *getUser() const {
43  return cast<Instruction>(getValPtr());
44  }
45 
46  /// setUser - Assign a new user instruction for this use.
47  void setUser(Instruction *NewUser) {
48  setValPtr(NewUser);
49  }
50 
51  /// getOperandValToReplace - Return the Value of the operand in the user
52  /// instruction that this IVStrideUse is representing.
54  return OperandValToReplace;
55  }
56 
57  /// setOperandValToReplace - Assign a new Value as the operand value
58  /// to replace.
60  OperandValToReplace = Op;
61  }
62 
63  /// getPostIncLoops - Return the set of loops for which the expression has
64  /// been adjusted to use post-inc mode.
66  return PostIncLoops;
67  }
68 
69  /// transformToPostInc - Transform the expression to post-inc form for the
70  /// given loop.
71  void transformToPostInc(const Loop *L);
72 
73 private:
74  /// Parent - a pointer to the IVUsers that owns this IVStrideUse.
75  IVUsers *Parent;
76 
77  /// OperandValToReplace - The Value of the operand in the user instruction
78  /// that this IVStrideUse is representing.
79  WeakTrackingVH OperandValToReplace;
80 
81  /// PostIncLoops - The set of loops for which Expr has been adjusted to
82  /// use post-inc mode. This corresponds with SCEVExpander's post-inc concept.
83  PostIncLoopSet PostIncLoops;
84 
85  /// Deleted - Implementation of CallbackVH virtual function to
86  /// receive notification when the User is deleted.
87  void deleted() override;
88 };
89 
90 class IVUsers {
91  friend class IVStrideUse;
92  Loop *L;
93  AssumptionCache *AC;
94  LoopInfo *LI;
95  DominatorTree *DT;
96  ScalarEvolution *SE;
98 
99  /// IVUses - A list of all tracked IV uses of induction variable expressions
100  /// we are interested in.
101  ilist<IVStrideUse> IVUses;
102 
103  // Ephemeral values used by @llvm.assume in this function.
105 
106 public:
108  ScalarEvolution *SE);
109 
111  : L(std::move(X.L)), AC(std::move(X.AC)), DT(std::move(X.DT)),
112  SE(std::move(X.SE)), Processed(std::move(X.Processed)),
113  IVUses(std::move(X.IVUses)), EphValues(std::move(X.EphValues)) {
114  for (IVStrideUse &U : IVUses)
115  U.Parent = this;
116  }
117  IVUsers(const IVUsers &) = delete;
118  IVUsers &operator=(IVUsers &&) = delete;
119  IVUsers &operator=(const IVUsers &) = delete;
120 
121  Loop *getLoop() const { return L; }
122 
123  /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a
124  /// reducible SCEV, recursively add its users to the IVUsesByStride set and
125  /// return true. Otherwise, return false.
127 
129 
130  /// getReplacementExpr - Return a SCEV expression which computes the
131  /// value of the OperandValToReplace of the given IVStrideUse.
132  const SCEV *getReplacementExpr(const IVStrideUse &IU) const;
133 
134  /// getExpr - Return the expression for the use.
135  const SCEV *getExpr(const IVStrideUse &IU) const;
136 
137  const SCEV *getStride(const IVStrideUse &IU, const Loop *L) const;
138 
141  iterator begin() { return IVUses.begin(); }
142  iterator end() { return IVUses.end(); }
143  const_iterator begin() const { return IVUses.begin(); }
144  const_iterator end() const { return IVUses.end(); }
145  bool empty() const { return IVUses.empty(); }
146 
147  bool isIVUserOrOperand(Instruction *Inst) const {
148  return Processed.count(Inst);
149  }
150 
151  void releaseMemory();
152 
153  void print(raw_ostream &OS, const Module * = nullptr) const;
154 
155  /// dump - This method is used for debugging.
156  void dump() const;
157 };
158 
160 
161 class IVUsersWrapperPass : public LoopPass {
162  std::unique_ptr<IVUsers> IU;
163 
164 public:
165  static char ID;
166 
168 
169  IVUsers &getIU() { return *IU; }
170  const IVUsers &getIU() const { return *IU; }
171 
172  void getAnalysisUsage(AnalysisUsage &AU) const override;
173 
174  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
175 
176  void releaseMemory() override;
177 
178  void print(raw_ostream &OS, const Module * = nullptr) const override;
179 };
180 
181 /// Analysis pass that exposes the \c IVUsers for a loop.
182 class IVUsersAnalysis : public AnalysisInfoMixin<IVUsersAnalysis> {
184  static AnalysisKey Key;
185 
186 public:
187  typedef IVUsers Result;
188 
191 };
192 
193 }
194 
195 #endif
llvm::IVStrideUse::setOperandValToReplace
void setOperandValToReplace(Value *Op)
setOperandValToReplace - Assign a new Value as the operand value to replace.
Definition: IVUsers.h:59
llvm::IVUsersAnalysis
Analysis pass that exposes the IVUsers for a loop.
Definition: IVUsers.h:182
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Pass
print lazy value Lazy Value Info Printer Pass
Definition: LazyValueInfo.cpp:1979
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:546
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:449
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::IVUsers::const_iterator
ilist< IVStrideUse >::const_iterator const_iterator
Definition: IVUsers.h:140
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::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:34
llvm::IVUsersWrapperPass::ID
static char ID
Definition: IVUsers.h:165
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::iplist
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
Definition: ilist.h:391
llvm::IVUsersWrapperPass::IVUsersWrapperPass
IVUsersWrapperPass()
Definition: IVUsers.cpp:300
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::IVUsers::end
const_iterator end() const
Definition: IVUsers.h:144
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:47
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::IVUsers::iterator
ilist< IVStrideUse >::iterator iterator
Definition: IVUsers.h:139
llvm::IVUsers::isIVUserOrOperand
bool isIVUserOrOperand(Instruction *Inst) const
Definition: IVUsers.h:147
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::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
llvm::IVUsers::releaseMemory
void releaseMemory()
Definition: IVUsers.cpp:295
llvm::IVUsers::begin
iterator begin()
Definition: IVUsers.h:141
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
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::IVUsers::getLoop
Loop * getLoop() const
Definition: IVUsers.h:121
llvm::IVUsersWrapperPass::getIU
IVUsers & getIU()
Definition: IVUsers.h:169
llvm::IVUsers::print
void print(raw_ostream &OS, const Module *=nullptr) const
Definition: IVUsers.cpp:265
llvm::IVUsers::IVUsers
IVUsers(IVUsers &&X)
Definition: IVUsers.h:110
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::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:264
llvm::IVUsers::operator=
IVUsers & operator=(IVUsers &&)=delete
llvm::IVUsersWrapperPass::getIU
const IVUsers & getIU() const
Definition: IVUsers.h:170
llvm::LoopPass
Definition: LoopPass.h:28
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::IVUsers
Definition: IVUsers.h:90
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::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:1666
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
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:383
llvm::IVUsers::empty
bool empty() const
Definition: IVUsers.h:145
llvm::LoopInfo
Definition: LoopInfo.h:1105
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
LoopPass.h
llvm::IVUsersWrapperPass
Definition: IVUsers.h:161
llvm::IVUsers::begin
const_iterator begin() const
Definition: IVUsers.h:143
ValueHandle.h
llvm::IVUsers::getExpr
const SCEV * getExpr(const IVStrideUse &IU) const
getExpr - Return the expression for the use.
Definition: IVUsers.cpp:336
llvm::IVUsersWrapperPass::runOnLoop
bool runOnLoop(Loop *L, LPPassManager &LPM) override
Definition: IVUsers.cpp:312
llvm::ilist_node
Definition: ilist_node.h:149
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
std
Definition: BitVector.h:851
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::IVUsers::end
iterator end()
Definition: IVUsers.h:142
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:37
llvm::IVUsers::AddUsersIfInteresting
bool AddUsersIfInteresting(Instruction *I)
AddUsersIfInteresting - Inspect the specified Instruction.
Definition: IVUsers.cpp:136
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::IVUsersAnalysis::Result
IVUsers Result
Definition: IVUsers.h:187
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::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