]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===- llvm/Analysis/IVUsers.h - Induction Variable Users -------*- C++ -*-===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
9 | // | |
10 | // This file implements bookkeeping for "interesting" users of expressions | |
11 | // computed from induction variables. | |
12 | // | |
13 | //===----------------------------------------------------------------------===// | |
14 | ||
15 | #ifndef LLVM_ANALYSIS_IVUSERS_H | |
16 | #define LLVM_ANALYSIS_IVUSERS_H | |
17 | ||
18 | #include "llvm/Analysis/LoopPass.h" | |
19 | #include "llvm/Analysis/ScalarEvolutionNormalization.h" | |
20 | #include "llvm/Support/ValueHandle.h" | |
21 | ||
22 | namespace llvm { | |
23 | ||
24 | class DominatorTree; | |
25 | class Instruction; | |
26 | class Value; | |
223e47cc LB |
27 | class ScalarEvolution; |
28 | class SCEV; | |
29 | class IVUsers; | |
970d7e83 | 30 | class DataLayout; |
223e47cc LB |
31 | |
32 | /// IVStrideUse - Keep track of one use of a strided induction variable. | |
33 | /// The Expr member keeps track of the expression, User is the actual user | |
34 | /// instruction of the operand, and 'OperandValToReplace' is the operand of | |
35 | /// the User that is the use. | |
36 | class IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> { | |
37 | friend class IVUsers; | |
38 | public: | |
39 | IVStrideUse(IVUsers *P, Instruction* U, Value *O) | |
40 | : CallbackVH(U), Parent(P), OperandValToReplace(O) { | |
41 | } | |
42 | ||
43 | /// getUser - Return the user instruction for this use. | |
44 | Instruction *getUser() const { | |
45 | return cast<Instruction>(getValPtr()); | |
46 | } | |
47 | ||
48 | /// setUser - Assign a new user instruction for this use. | |
49 | void setUser(Instruction *NewUser) { | |
50 | setValPtr(NewUser); | |
51 | } | |
52 | ||
53 | /// getOperandValToReplace - Return the Value of the operand in the user | |
54 | /// instruction that this IVStrideUse is representing. | |
55 | Value *getOperandValToReplace() const { | |
56 | return OperandValToReplace; | |
57 | } | |
58 | ||
59 | /// setOperandValToReplace - Assign a new Value as the operand value | |
60 | /// to replace. | |
61 | void setOperandValToReplace(Value *Op) { | |
62 | OperandValToReplace = Op; | |
63 | } | |
64 | ||
65 | /// getPostIncLoops - Return the set of loops for which the expression has | |
66 | /// been adjusted to use post-inc mode. | |
67 | const PostIncLoopSet &getPostIncLoops() const { | |
68 | return PostIncLoops; | |
69 | } | |
70 | ||
71 | /// transformToPostInc - Transform the expression to post-inc form for the | |
72 | /// given loop. | |
73 | void transformToPostInc(const Loop *L); | |
74 | ||
75 | private: | |
76 | /// Parent - a pointer to the IVUsers that owns this IVStrideUse. | |
77 | IVUsers *Parent; | |
78 | ||
79 | /// OperandValToReplace - The Value of the operand in the user instruction | |
80 | /// that this IVStrideUse is representing. | |
81 | WeakVH OperandValToReplace; | |
82 | ||
83 | /// PostIncLoops - The set of loops for which Expr has been adjusted to | |
84 | /// use post-inc mode. This corresponds with SCEVExpander's post-inc concept. | |
85 | PostIncLoopSet PostIncLoops; | |
86 | ||
87 | /// Deleted - Implementation of CallbackVH virtual function to | |
88 | /// receive notification when the User is deleted. | |
89 | virtual void deleted(); | |
90 | }; | |
91 | ||
92 | template<> struct ilist_traits<IVStrideUse> | |
93 | : public ilist_default_traits<IVStrideUse> { | |
94 | // createSentinel is used to get hold of a node that marks the end of | |
95 | // the list... | |
96 | // The sentinel is relative to this instance, so we use a non-static | |
97 | // method. | |
98 | IVStrideUse *createSentinel() const { | |
99 | // since i(p)lists always publicly derive from the corresponding | |
100 | // traits, placing a data member in this class will augment i(p)list. | |
101 | // But since the NodeTy is expected to publicly derive from | |
102 | // ilist_node<NodeTy>, there is a legal viable downcast from it | |
103 | // to NodeTy. We use this trick to superpose i(p)list with a "ghostly" | |
104 | // NodeTy, which becomes the sentinel. Dereferencing the sentinel is | |
105 | // forbidden (save the ilist_node<NodeTy>) so no one will ever notice | |
106 | // the superposition. | |
107 | return static_cast<IVStrideUse*>(&Sentinel); | |
108 | } | |
109 | static void destroySentinel(IVStrideUse*) {} | |
110 | ||
111 | IVStrideUse *provideInitialHead() const { return createSentinel(); } | |
112 | IVStrideUse *ensureHead(IVStrideUse*) const { return createSentinel(); } | |
113 | static void noteHead(IVStrideUse*, IVStrideUse*) {} | |
114 | ||
115 | private: | |
116 | mutable ilist_node<IVStrideUse> Sentinel; | |
117 | }; | |
118 | ||
119 | class IVUsers : public LoopPass { | |
120 | friend class IVStrideUse; | |
121 | Loop *L; | |
122 | LoopInfo *LI; | |
123 | DominatorTree *DT; | |
124 | ScalarEvolution *SE; | |
970d7e83 | 125 | DataLayout *TD; |
223e47cc LB |
126 | SmallPtrSet<Instruction*,16> Processed; |
127 | ||
128 | /// IVUses - A list of all tracked IV uses of induction variable expressions | |
129 | /// we are interested in. | |
130 | ilist<IVStrideUse> IVUses; | |
131 | ||
132 | virtual void getAnalysisUsage(AnalysisUsage &AU) const; | |
133 | ||
134 | virtual bool runOnLoop(Loop *L, LPPassManager &LPM); | |
135 | ||
136 | virtual void releaseMemory(); | |
137 | ||
138 | public: | |
139 | static char ID; // Pass ID, replacement for typeid | |
140 | IVUsers(); | |
141 | ||
142 | Loop *getLoop() const { return L; } | |
143 | ||
144 | /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a | |
145 | /// reducible SCEV, recursively add its users to the IVUsesByStride set and | |
146 | /// return true. Otherwise, return false. | |
147 | bool AddUsersIfInteresting(Instruction *I); | |
148 | ||
149 | IVStrideUse &AddUser(Instruction *User, Value *Operand); | |
150 | ||
151 | /// getReplacementExpr - Return a SCEV expression which computes the | |
152 | /// value of the OperandValToReplace of the given IVStrideUse. | |
153 | const SCEV *getReplacementExpr(const IVStrideUse &IU) const; | |
154 | ||
155 | /// getExpr - Return the expression for the use. | |
156 | const SCEV *getExpr(const IVStrideUse &IU) const; | |
157 | ||
158 | const SCEV *getStride(const IVStrideUse &IU, const Loop *L) const; | |
159 | ||
160 | typedef ilist<IVStrideUse>::iterator iterator; | |
161 | typedef ilist<IVStrideUse>::const_iterator const_iterator; | |
162 | iterator begin() { return IVUses.begin(); } | |
163 | iterator end() { return IVUses.end(); } | |
164 | const_iterator begin() const { return IVUses.begin(); } | |
165 | const_iterator end() const { return IVUses.end(); } | |
166 | bool empty() const { return IVUses.empty(); } | |
167 | ||
168 | bool isIVUserOrOperand(Instruction *Inst) const { | |
169 | return Processed.count(Inst); | |
170 | } | |
171 | ||
172 | void print(raw_ostream &OS, const Module* = 0) const; | |
173 | ||
174 | /// dump - This method is used for debugging. | |
175 | void dump() const; | |
176 | protected: | |
177 | bool AddUsersImpl(Instruction *I, SmallPtrSet<Loop*,16> &SimpleLoopNests); | |
178 | }; | |
179 | ||
180 | Pass *createIVUsersPass(); | |
181 | ||
182 | } | |
183 | ||
184 | #endif |