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 
163 
164 class IVUsersWrapperPass : public LoopPass {
165  std::unique_ptr<IVUsers> IU;
166 
167 public:
168  static char ID;
169 
171 
172  IVUsers &getIU() { return *IU; }
173  const IVUsers &getIU() const { return *IU; }
174 
175  void getAnalysisUsage(AnalysisUsage &AU) const override;
176 
177  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
178 
179  void releaseMemory() override;
180 
181  void print(raw_ostream &OS, const Module * = nullptr) const override;
182 };
183 
184 /// Analysis pass that exposes the \c IVUsers for a loop.
185 class IVUsersAnalysis : public AnalysisInfoMixin<IVUsersAnalysis> {
187  static AnalysisKey Key;
188 
189 public:
190  typedef IVUsers Result;
191 
194 };
195 
196 }
197 
198 #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:185
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
Pass
print lazy value Lazy Value Info Printer Pass
Definition: LazyValueInfo.cpp:1976
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:460
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:168
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::iplist
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
Definition: ilist.h:390
llvm::IVUsersWrapperPass::IVUsersWrapperPass
IVUsersWrapperPass()
Definition: IVUsers.cpp:304
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:299
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: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
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:172
llvm::IVUsers::print
void print(raw_ostream &OS, const Module *=nullptr) const
Definition: IVUsers.cpp:269
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:77
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:206
llvm::IVUsers::operator=
IVUsers & operator=(IVUsers &&)=delete
llvm::IVUsersWrapperPass::getIU
const IVUsers & getIU() const
Definition: IVUsers.h:173
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:250
llvm::IVUsers::getStride
const SCEV * getStride(const IVStrideUse &IU, const Loop *L) const
Definition: IVUsers.cpp:362
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:1658
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::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:42
LoopPass.h
llvm::IVUsersWrapperPass
Definition: IVUsers.h:164
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:340
llvm::IVUsersWrapperPass::runOnLoop
bool runOnLoop(Loop *L, LPPassManager &LPM) override
Definition: IVUsers.cpp:316
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:368
std
Definition: BitVector.h:838
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:325
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:140
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::IVUsersAnalysis::Result
IVUsers Result
Definition: IVUsers.h:190
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::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