/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/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 | | // 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 | | |
17 | | #include "llvm/Analysis/LoopAnalysisManager.h" |
18 | | #include "llvm/Analysis/LoopPass.h" |
19 | | #include "llvm/Analysis/ScalarEvolutionNormalization.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: |
40 | | IVStrideUse(IVUsers *P, Instruction* U, Value *O) |
41 | 599k | : CallbackVH(U), Parent(P), OperandValToReplace(O) { |
42 | 599k | } |
43 | | |
44 | | /// getUser - Return the user instruction for this use. |
45 | 2.72M | Instruction *getUser() const { |
46 | 2.72M | return cast<Instruction>(getValPtr()); |
47 | 2.72M | } |
48 | | |
49 | | /// setUser - Assign a new user instruction for this use. |
50 | 17 | void setUser(Instruction *NewUser) { |
51 | 17 | setValPtr(NewUser); |
52 | 17 | } |
53 | | |
54 | | /// getOperandValToReplace - Return the Value of the operand in the user |
55 | | /// instruction that this IVStrideUse is representing. |
56 | 2.90M | Value *getOperandValToReplace() const { |
57 | 2.90M | return OperandValToReplace; |
58 | 2.90M | } |
59 | | |
60 | | /// setOperandValToReplace - Assign a new Value as the operand value |
61 | | /// to replace. |
62 | 0 | void setOperandValToReplace(Value *Op) { |
63 | 0 | OperandValToReplace = Op; |
64 | 0 | } |
65 | | |
66 | | /// getPostIncLoops - Return the set of loops for which the expression has |
67 | | /// been adjusted to use post-inc mode. |
68 | 1.49M | const PostIncLoopSet &getPostIncLoops() const { |
69 | 1.49M | return PostIncLoops; |
70 | 1.49M | } |
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; |
100 | | SmallPtrSet<Instruction*, 16> Processed; |
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. |
107 | | SmallPtrSet<const Value *, 32> EphValues; |
108 | | |
109 | | public: |
110 | | IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT, |
111 | | ScalarEvolution *SE); |
112 | | |
113 | | IVUsers(IVUsers &&X) |
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 | 24 | IVUses(std::move(X.IVUses)), EphValues(std::move(X.EphValues)) { |
117 | 24 | for (IVStrideUse &U : IVUses) |
118 | 16 | U.Parent = this; |
119 | 24 | } |
120 | | IVUsers(const IVUsers &) = delete; |
121 | | IVUsers &operator=(IVUsers &&) = delete; |
122 | | IVUsers &operator=(const IVUsers &) = delete; |
123 | | |
124 | 0 | 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. |
129 | | bool AddUsersIfInteresting(Instruction *I); |
130 | | |
131 | | IVStrideUse &AddUser(Instruction *User, Value *Operand); |
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 | | |
142 | | typedef ilist<IVStrideUse>::iterator iterator; |
143 | | typedef ilist<IVStrideUse>::const_iterator const_iterator; |
144 | 536k | iterator begin() { return IVUses.begin(); } |
145 | 536k | iterator end() { return IVUses.end(); } |
146 | 0 | const_iterator begin() const { return IVUses.begin(); } |
147 | 0 | const_iterator end() const { return IVUses.end(); } |
148 | 333k | bool empty() const { return IVUses.empty(); } |
149 | | |
150 | 1.94M | bool isIVUserOrOperand(Instruction *Inst) const { |
151 | 1.94M | return Processed.count(Inst); |
152 | 1.94M | } |
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 | | protected: |
162 | | bool AddUsersImpl(Instruction *I, SmallPtrSetImpl<Loop*> &SimpleLoopNests); |
163 | | }; |
164 | | |
165 | | Pass *createIVUsersPass(); |
166 | | |
167 | | class IVUsersWrapperPass : public LoopPass { |
168 | | std::unique_ptr<IVUsers> IU; |
169 | | |
170 | | public: |
171 | | static char ID; |
172 | | |
173 | | IVUsersWrapperPass(); |
174 | | |
175 | 208k | IVUsers &getIU() { return *IU; } |
176 | 0 | const IVUsers &getIU() const { return *IU; } |
177 | | |
178 | | void getAnalysisUsage(AnalysisUsage &AU) const override; |
179 | | |
180 | | bool runOnLoop(Loop *L, LPPassManager &LPM) override; |
181 | | |
182 | | void releaseMemory() override; |
183 | | |
184 | | void print(raw_ostream &OS, const Module * = nullptr) const override; |
185 | | }; |
186 | | |
187 | | /// Analysis pass that exposes the \c IVUsers for a loop. |
188 | | class IVUsersAnalysis : public AnalysisInfoMixin<IVUsersAnalysis> { |
189 | | friend AnalysisInfoMixin<IVUsersAnalysis>; |
190 | | static AnalysisKey Key; |
191 | | |
192 | | public: |
193 | | typedef IVUsers Result; |
194 | | |
195 | | IVUsers run(Loop &L, LoopAnalysisManager &AM, |
196 | | LoopStandardAnalysisResults &AR); |
197 | | }; |
198 | | |
199 | | } |
200 | | |
201 | | #endif |