/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/Analysis/IVUsers.h
Line | Count | Source (jump to first uncovered line) |
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/LoopAnalysisManager.h" |
19 | | #include "llvm/Analysis/LoopPass.h" |
20 | | #include "llvm/Analysis/ScalarEvolutionNormalization.h" |
21 | | #include "llvm/IR/ValueHandle.h" |
22 | | |
23 | | namespace llvm { |
24 | | |
25 | | class AssumptionCache; |
26 | | class DominatorTree; |
27 | | class Instruction; |
28 | | class Value; |
29 | | class ScalarEvolution; |
30 | | class SCEV; |
31 | | class IVUsers; |
32 | | class DataLayout; |
33 | | |
34 | | /// IVStrideUse - Keep track of one use of a strided induction variable. |
35 | | /// The Expr member keeps track of the expression, User is the actual user |
36 | | /// instruction of the operand, and 'OperandValToReplace' is the operand of |
37 | | /// the User that is the use. |
38 | | class IVStrideUse final : public CallbackVH, public ilist_node<IVStrideUse> { |
39 | | friend class IVUsers; |
40 | | public: |
41 | | IVStrideUse(IVUsers *P, Instruction* U, Value *O) |
42 | 899k | : CallbackVH(U), Parent(P), OperandValToReplace(O) { |
43 | 899k | } |
44 | | |
45 | | /// getUser - Return the user instruction for this use. |
46 | 3.95M | Instruction *getUser() const { |
47 | 3.95M | return cast<Instruction>(getValPtr()); |
48 | 3.95M | } |
49 | | |
50 | | /// setUser - Assign a new user instruction for this use. |
51 | 17 | void setUser(Instruction *NewUser) { |
52 | 17 | setValPtr(NewUser); |
53 | 17 | } |
54 | | |
55 | | /// getOperandValToReplace - Return the Value of the operand in the user |
56 | | /// instruction that this IVStrideUse is representing. |
57 | 3.75M | Value *getOperandValToReplace() const { |
58 | 3.75M | return OperandValToReplace; |
59 | 3.75M | } |
60 | | |
61 | | /// setOperandValToReplace - Assign a new Value as the operand value |
62 | | /// to replace. |
63 | 0 | void setOperandValToReplace(Value *Op) { |
64 | 0 | OperandValToReplace = Op; |
65 | 0 | } |
66 | | |
67 | | /// getPostIncLoops - Return the set of loops for which the expression has |
68 | | /// been adjusted to use post-inc mode. |
69 | 2.20M | const PostIncLoopSet &getPostIncLoops() const { |
70 | 2.20M | return PostIncLoops; |
71 | 2.20M | } |
72 | | |
73 | | /// transformToPostInc - Transform the expression to post-inc form for the |
74 | | /// given loop. |
75 | | void transformToPostInc(const Loop *L); |
76 | | |
77 | | private: |
78 | | /// Parent - a pointer to the IVUsers that owns this IVStrideUse. |
79 | | IVUsers *Parent; |
80 | | |
81 | | /// OperandValToReplace - The Value of the operand in the user instruction |
82 | | /// that this IVStrideUse is representing. |
83 | | WeakTrackingVH OperandValToReplace; |
84 | | |
85 | | /// PostIncLoops - The set of loops for which Expr has been adjusted to |
86 | | /// use post-inc mode. This corresponds with SCEVExpander's post-inc concept. |
87 | | PostIncLoopSet PostIncLoops; |
88 | | |
89 | | /// Deleted - Implementation of CallbackVH virtual function to |
90 | | /// receive notification when the User is deleted. |
91 | | void deleted() override; |
92 | | }; |
93 | | |
94 | | class IVUsers { |
95 | | friend class IVStrideUse; |
96 | | Loop *L; |
97 | | AssumptionCache *AC; |
98 | | LoopInfo *LI; |
99 | | DominatorTree *DT; |
100 | | ScalarEvolution *SE; |
101 | | SmallPtrSet<Instruction*, 16> Processed; |
102 | | |
103 | | /// IVUses - A list of all tracked IV uses of induction variable expressions |
104 | | /// we are interested in. |
105 | | ilist<IVStrideUse> IVUses; |
106 | | |
107 | | // Ephemeral values used by @llvm.assume in this function. |
108 | | SmallPtrSet<const Value *, 32> EphValues; |
109 | | |
110 | | public: |
111 | | IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT, |
112 | | ScalarEvolution *SE); |
113 | | |
114 | | IVUsers(IVUsers &&X) |
115 | | : L(std::move(X.L)), AC(std::move(X.AC)), DT(std::move(X.DT)), |
116 | | SE(std::move(X.SE)), Processed(std::move(X.Processed)), |
117 | 24 | IVUses(std::move(X.IVUses)), EphValues(std::move(X.EphValues)) { |
118 | 24 | for (IVStrideUse &U : IVUses) |
119 | 16 | U.Parent = this; |
120 | 24 | } |
121 | | IVUsers(const IVUsers &) = delete; |
122 | | IVUsers &operator=(IVUsers &&) = delete; |
123 | | IVUsers &operator=(const IVUsers &) = delete; |
124 | | |
125 | 0 | Loop *getLoop() const { return L; } |
126 | | |
127 | | /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a |
128 | | /// reducible SCEV, recursively add its users to the IVUsesByStride set and |
129 | | /// return true. Otherwise, return false. |
130 | | bool AddUsersIfInteresting(Instruction *I); |
131 | | |
132 | | IVStrideUse &AddUser(Instruction *User, Value *Operand); |
133 | | |
134 | | /// getReplacementExpr - Return a SCEV expression which computes the |
135 | | /// value of the OperandValToReplace of the given IVStrideUse. |
136 | | const SCEV *getReplacementExpr(const IVStrideUse &IU) const; |
137 | | |
138 | | /// getExpr - Return the expression for the use. |
139 | | const SCEV *getExpr(const IVStrideUse &IU) const; |
140 | | |
141 | | const SCEV *getStride(const IVStrideUse &IU, const Loop *L) const; |
142 | | |
143 | | typedef ilist<IVStrideUse>::iterator iterator; |
144 | | typedef ilist<IVStrideUse>::const_iterator const_iterator; |
145 | 851k | iterator begin() { return IVUses.begin(); } |
146 | 851k | iterator end() { return IVUses.end(); } |
147 | 0 | const_iterator begin() const { return IVUses.begin(); } |
148 | 0 | const_iterator end() const { return IVUses.end(); } |
149 | 564k | bool empty() const { return IVUses.empty(); } |
150 | | |
151 | 2.83M | bool isIVUserOrOperand(Instruction *Inst) const { |
152 | 2.83M | return Processed.count(Inst); |
153 | 2.83M | } |
154 | | |
155 | | void releaseMemory(); |
156 | | |
157 | | void print(raw_ostream &OS, const Module * = nullptr) const; |
158 | | |
159 | | /// dump - This method is used for debugging. |
160 | | void dump() const; |
161 | | |
162 | | protected: |
163 | | bool AddUsersImpl(Instruction *I, SmallPtrSetImpl<Loop*> &SimpleLoopNests); |
164 | | }; |
165 | | |
166 | | Pass *createIVUsersPass(); |
167 | | |
168 | | class IVUsersWrapperPass : public LoopPass { |
169 | | std::unique_ptr<IVUsers> IU; |
170 | | |
171 | | public: |
172 | | static char ID; |
173 | | |
174 | | IVUsersWrapperPass(); |
175 | | |
176 | 363k | IVUsers &getIU() { return *IU; } |
177 | 0 | const IVUsers &getIU() const { return *IU; } |
178 | | |
179 | | void getAnalysisUsage(AnalysisUsage &AU) const override; |
180 | | |
181 | | bool runOnLoop(Loop *L, LPPassManager &LPM) override; |
182 | | |
183 | | void releaseMemory() override; |
184 | | |
185 | | void print(raw_ostream &OS, const Module * = nullptr) const override; |
186 | | }; |
187 | | |
188 | | /// Analysis pass that exposes the \c IVUsers for a loop. |
189 | | class IVUsersAnalysis : public AnalysisInfoMixin<IVUsersAnalysis> { |
190 | | friend AnalysisInfoMixin<IVUsersAnalysis>; |
191 | | static AnalysisKey Key; |
192 | | |
193 | | public: |
194 | | typedef IVUsers Result; |
195 | | |
196 | | IVUsers run(Loop &L, LoopAnalysisManager &AM, |
197 | | LoopStandardAnalysisResults &AR); |
198 | | }; |
199 | | |
200 | | } |
201 | | |
202 | | #endif |