1 //===- llvm/Analysis/IVUsers.h - Induction Variable Users -------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements bookkeeping for "interesting" users of expressions
11 // computed from induction variables.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_ANALYSIS_IVUSERS_H
16 #define LLVM_ANALYSIS_IVUSERS_H
18 #include "llvm/Analysis/LoopPass.h"
19 #include "llvm/Analysis/ScalarEvolution.h"
20 #include <llvm/ADT/SmallVector.h>
28 class IVUsersOfOneStride;
30 /// IVStrideUse - Keep track of one use of a strided induction variable, where
31 /// the stride is stored externally. The Offset member keeps track of the
32 /// offset from the IV, User is the actual user of the operand, and
33 /// 'OperandValToReplace' is the operand of the User that is the use.
34 class IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> {
36 IVStrideUse(IVUsersOfOneStride *parent,
37 const SCEVHandle &offset,
38 Instruction* U, Value *O, bool issigned)
39 : CallbackVH(U), Parent(parent), Offset(offset),
40 OperandValToReplace(O), IsSigned(issigned),
41 IsUseOfPostIncrementedValue(false) {
44 /// getUser - Return the user instruction for this use.
45 Instruction *getUser() const {
46 return cast<Instruction>(getValPtr());
49 /// setUser - Assign a new user instruction for this use.
50 void setUser(Instruction *NewUser) {
54 /// getParent - Return a pointer to the IVUsersOfOneStride that owns
56 IVUsersOfOneStride *getParent() const { return Parent; }
58 /// getOffset - Return the offset to add to a theoeretical induction
59 /// variable that starts at zero and counts up by the stride to compute
60 /// the value for the use. This always has the same type as the stride,
61 /// which may need to be casted to match the type of the use.
62 SCEVHandle getOffset() const { return Offset; }
64 /// setOffset - Assign a new offset to this use.
65 void setOffset(SCEVHandle Val) {
69 /// getOperandValToReplace - Return the Value of the operand in the user
70 /// instruction that this IVStrideUse is representing.
71 Value *getOperandValToReplace() const {
72 return OperandValToReplace;
75 /// setOperandValToReplace - Assign a new Value as the operand value
77 void setOperandValToReplace(Value *Op) {
78 OperandValToReplace = Op;
81 /// isSigned - The stride (and thus also the Offset) of this use may be in
82 /// a narrower type than the use itself (OperandValToReplace->getType()).
83 /// When this is the case, isSigned() indicates whether the IV expression
84 /// should be signed-extended instead of zero-extended to fit the type of
86 bool isSigned() const { return IsSigned; }
88 /// isUseOfPostIncrementedValue - True if this should use the
89 /// post-incremented version of this IV, not the preincremented version.
90 /// This can only be set in special cases, such as the terminating setcc
91 /// instruction for a loop or uses dominated by the loop.
92 bool isUseOfPostIncrementedValue() const {
93 return IsUseOfPostIncrementedValue;
96 /// setIsUseOfPostIncrmentedValue - set the flag that indicates whether
97 /// this is a post-increment use.
98 void setIsUseOfPostIncrementedValue(bool Val) {
99 IsUseOfPostIncrementedValue = Val;
103 /// Parent - a pointer to the IVUsersOfOneStride that owns this IVStrideUse.
104 IVUsersOfOneStride *Parent;
106 /// Offset - The offset to add to the base induction expression.
109 /// OperandValToReplace - The Value of the operand in the user instruction
110 /// that this IVStrideUse is representing.
111 WeakVH OperandValToReplace;
113 /// IsSigned - Determines whether the replacement value is sign or
114 /// zero extended to the type of the use.
117 /// IsUseOfPostIncrementedValue - True if this should use the
118 /// post-incremented version of this IV, not the preincremented version.
119 bool IsUseOfPostIncrementedValue;
121 /// Deleted - Implementation of CallbackVH virtual function to
122 /// recieve notification when the User is deleted.
123 virtual void deleted();
126 template<> struct ilist_traits<IVStrideUse>
127 : public ilist_default_traits<IVStrideUse> {
128 // createSentinel is used to get hold of a node that marks the end of
130 // The sentinel is relative to this instance, so we use a non-static
132 IVStrideUse *createSentinel() const {
133 // since i(p)lists always publicly derive from the corresponding
134 // traits, placing a data member in this class will augment i(p)list.
135 // But since the NodeTy is expected to publicly derive from
136 // ilist_node<NodeTy>, there is a legal viable downcast from it
137 // to NodeTy. We use this trick to superpose i(p)list with a "ghostly"
138 // NodeTy, which becomes the sentinel. Dereferencing the sentinel is
139 // forbidden (save the ilist_node<NodeTy>) so no one will ever notice
140 // the superposition.
141 return static_cast<IVStrideUse*>(&Sentinel);
143 static void destroySentinel(IVStrideUse*) {}
145 IVStrideUse *provideInitialHead() const { return createSentinel(); }
146 IVStrideUse *ensureHead(IVStrideUse*) const { return createSentinel(); }
147 static void noteHead(IVStrideUse*, IVStrideUse*) {}
150 mutable ilist_node<IVStrideUse> Sentinel;
153 /// IVUsersOfOneStride - This structure keeps track of all instructions that
154 /// have an operand that is based on the trip count multiplied by some stride.
155 struct IVUsersOfOneStride : public ilist_node<IVUsersOfOneStride> {
157 IVUsersOfOneStride(const IVUsersOfOneStride &I); // do not implement
158 void operator=(const IVUsersOfOneStride &I); // do not implement
161 IVUsersOfOneStride() : Stride(0) {}
163 explicit IVUsersOfOneStride(const SCEV *stride) : Stride(stride) {}
165 /// Stride - The stride for all the contained IVStrideUses. This is
166 /// a constant for affine strides.
169 /// Users - Keep track of all of the users of this stride as well as the
170 /// initial value and the operand that uses the IV.
171 ilist<IVStrideUse> Users;
173 void addUser(const SCEVHandle &Offset,Instruction *User, Value *Operand,
175 Users.push_back(new IVStrideUse(this, Offset, User, Operand, isSigned));
179 class IVUsers : public LoopPass {
180 friend class IVStrideUserVH;
185 SmallPtrSet<Instruction*,16> Processed;
188 /// IVUses - A list of all tracked IV uses of induction variable expressions
189 /// we are interested in.
190 ilist<IVUsersOfOneStride> IVUses;
192 /// IVUsesByStride - A mapping from the strides in StrideOrder to the
194 std::map<SCEVHandle, IVUsersOfOneStride*> IVUsesByStride;
196 /// StrideOrder - An ordering of the keys in IVUsesByStride that is stable:
197 /// We use this to iterate over the IVUsesByStride collection without being
198 /// dependent on random ordering of pointers in the process.
199 SmallVector<SCEVHandle, 16> StrideOrder;
202 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
204 virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
206 virtual void releaseMemory();
209 static char ID; // Pass ID, replacement for typeid
212 /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a
213 /// reducible SCEV, recursively add its users to the IVUsesByStride set and
214 /// return true. Otherwise, return false.
215 bool AddUsersIfInteresting(Instruction *I);
217 /// getReplacementExpr - Return a SCEV expression which computes the
218 /// value of the OperandValToReplace of the given IVStrideUse.
219 SCEVHandle getReplacementExpr(const IVStrideUse &U) const;
221 void print(raw_ostream &OS, const Module* = 0) const;
222 virtual void print(std::ostream &OS, const Module* = 0) const;
223 void print(std::ostream *OS, const Module* M = 0) const {
224 if (OS) print(*OS, M);
227 /// dump - This method is used for debugging.
231 Pass *createIVUsersPass();