/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/Transforms/Utils/PredicateInfo.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- PredicateInfo.h - Build PredicateInfo ----------------------*-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 | | /// \file |
11 | | /// \brief This file implements the PredicateInfo analysis, which creates an Extended |
12 | | /// SSA form for operations used in branch comparisons and llvm.assume |
13 | | /// comparisons. |
14 | | /// |
15 | | /// Copies of these operations are inserted into the true/false edge (and after |
16 | | /// assumes), and information attached to the copies. All uses of the original |
17 | | /// operation in blocks dominated by the true/false edge (and assume), are |
18 | | /// replaced with uses of the copies. This enables passes to easily and sparsely |
19 | | /// propagate condition based info into the operations that may be affected. |
20 | | /// |
21 | | /// Example: |
22 | | /// %cmp = icmp eq i32 %x, 50 |
23 | | /// br i1 %cmp, label %true, label %false |
24 | | /// true: |
25 | | /// ret i32 %x |
26 | | /// false: |
27 | | /// ret i32 1 |
28 | | /// |
29 | | /// will become |
30 | | /// |
31 | | /// %cmp = icmp eq i32, %x, 50 |
32 | | /// br i1 %cmp, label %true, label %false |
33 | | /// true: |
34 | | /// %x.0 = call @llvm.ssa_copy.i32(i32 %x) |
35 | | /// ret i32 %x.0 |
36 | | /// false: |
37 | | /// ret i32 1 |
38 | | /// |
39 | | /// Using getPredicateInfoFor on x.0 will give you the comparison it is |
40 | | /// dominated by (the icmp), and that you are located in the true edge of that |
41 | | /// comparison, which tells you x.0 is 50. |
42 | | /// |
43 | | /// In order to reduce the number of copies inserted, predicateinfo is only |
44 | | /// inserted where it would actually be live. This means if there are no uses of |
45 | | /// an operation dominated by the branch edges, or by an assume, the associated |
46 | | /// predicate info is never inserted. |
47 | | /// |
48 | | /// |
49 | | //===----------------------------------------------------------------------===// |
50 | | |
51 | | #ifndef LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H |
52 | | #define LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H |
53 | | |
54 | | #include "llvm/ADT/DenseMap.h" |
55 | | #include "llvm/ADT/DenseSet.h" |
56 | | #include "llvm/ADT/SmallPtrSet.h" |
57 | | #include "llvm/ADT/SmallVector.h" |
58 | | #include "llvm/ADT/ilist.h" |
59 | | #include "llvm/ADT/ilist_node.h" |
60 | | #include "llvm/ADT/iterator.h" |
61 | | #include "llvm/Analysis/AssumptionCache.h" |
62 | | #include "llvm/IR/BasicBlock.h" |
63 | | #include "llvm/IR/Dominators.h" |
64 | | #include "llvm/IR/Instructions.h" |
65 | | #include "llvm/IR/IntrinsicInst.h" |
66 | | #include "llvm/IR/Module.h" |
67 | | #include "llvm/IR/OperandTraits.h" |
68 | | #include "llvm/IR/Type.h" |
69 | | #include "llvm/IR/Use.h" |
70 | | #include "llvm/IR/User.h" |
71 | | #include "llvm/IR/Value.h" |
72 | | #include "llvm/Pass.h" |
73 | | #include "llvm/PassAnalysisSupport.h" |
74 | | #include "llvm/Support/Casting.h" |
75 | | #include "llvm/Support/Compiler.h" |
76 | | #include "llvm/Support/ErrorHandling.h" |
77 | | #include "llvm/Transforms/Utils/OrderedInstructions.h" |
78 | | #include <algorithm> |
79 | | #include <cassert> |
80 | | #include <cstddef> |
81 | | #include <iterator> |
82 | | #include <memory> |
83 | | #include <utility> |
84 | | |
85 | | namespace llvm { |
86 | | |
87 | | class DominatorTree; |
88 | | class Function; |
89 | | class Instruction; |
90 | | class MemoryAccess; |
91 | | class LLVMContext; |
92 | | class raw_ostream; |
93 | | |
94 | | enum PredicateType { PT_Branch, PT_Assume, PT_Switch }; |
95 | | |
96 | | // Base class for all predicate information we provide. |
97 | | // All of our predicate information has at least a comparison. |
98 | | class PredicateBase : public ilist_node<PredicateBase> { |
99 | | public: |
100 | | PredicateType Type; |
101 | | // The original operand before we renamed it. |
102 | | // This can be use by passes, when destroying predicateinfo, to know |
103 | | // whether they can just drop the intrinsic, or have to merge metadata. |
104 | | Value *OriginalOp; |
105 | | PredicateBase(const PredicateBase &) = delete; |
106 | | PredicateBase &operator=(const PredicateBase &) = delete; |
107 | | PredicateBase() = delete; |
108 | 706 | virtual ~PredicateBase() = default; |
109 | | |
110 | | protected: |
111 | 706 | PredicateBase(PredicateType PT, Value *Op) : Type(PT), OriginalOp(Op) {} |
112 | | }; |
113 | | |
114 | | class PredicateWithCondition : public PredicateBase { |
115 | | public: |
116 | | Value *Condition; |
117 | 123 | static bool classof(const PredicateBase *PB) { |
118 | 103 | return PB->Type == PT_Assume || PB->Type == PT_Branch || |
119 | 2 | PB->Type == PT_Switch; |
120 | 123 | } |
121 | | |
122 | | protected: |
123 | | PredicateWithCondition(PredicateType PT, Value *Op, Value *Condition) |
124 | 706 | : PredicateBase(PT, Op), Condition(Condition) {} |
125 | | }; |
126 | | |
127 | | // Provides predicate information for assumes. Since assumes are always true, |
128 | | // we simply provide the assume instruction, so you can tell your relative |
129 | | // position to it. |
130 | | class PredicateAssume : public PredicateWithCondition { |
131 | | public: |
132 | | IntrinsicInst *AssumeInst; |
133 | | PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition) |
134 | | : PredicateWithCondition(PT_Assume, Op, Condition), |
135 | 28 | AssumeInst(AssumeInst) {} |
136 | | PredicateAssume() = delete; |
137 | 857 | static bool classof(const PredicateBase *PB) { |
138 | 857 | return PB->Type == PT_Assume; |
139 | 857 | } |
140 | | }; |
141 | | |
142 | | // Mixin class for edge predicates. The FROM block is the block where the |
143 | | // predicate originates, and the TO block is the block where the predicate is |
144 | | // valid. |
145 | | class PredicateWithEdge : public PredicateWithCondition { |
146 | | public: |
147 | | BasicBlock *From; |
148 | | BasicBlock *To; |
149 | | PredicateWithEdge() = delete; |
150 | 847 | static bool classof(const PredicateBase *PB) { |
151 | 37 | return PB->Type == PT_Branch || PB->Type == PT_Switch; |
152 | 847 | } |
153 | | |
154 | | protected: |
155 | | PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From, |
156 | | BasicBlock *To, Value *Cond) |
157 | 678 | : PredicateWithCondition(PType, Op, Cond), From(From), To(To) {} |
158 | | }; |
159 | | |
160 | | // Provides predicate information for branches. |
161 | | class PredicateBranch : public PredicateWithEdge { |
162 | | public: |
163 | | // If true, SplitBB is the true successor, otherwise it's the false successor. |
164 | | bool TrueEdge; |
165 | | PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB, |
166 | | Value *Condition, bool TakenEdge) |
167 | | : PredicateWithEdge(PT_Branch, Op, BranchBB, SplitBB, Condition), |
168 | 670 | TrueEdge(TakenEdge) {} |
169 | | PredicateBranch() = delete; |
170 | 249 | static bool classof(const PredicateBase *PB) { |
171 | 249 | return PB->Type == PT_Branch; |
172 | 249 | } |
173 | | }; |
174 | | |
175 | | class PredicateSwitch : public PredicateWithEdge { |
176 | | public: |
177 | | Value *CaseValue; |
178 | | // This is the switch instruction. |
179 | | SwitchInst *Switch; |
180 | | PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB, |
181 | | Value *CaseValue, SwitchInst *SI) |
182 | | : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB, |
183 | | SI->getCondition()), |
184 | 8 | CaseValue(CaseValue), Switch(SI) {} |
185 | | PredicateSwitch() = delete; |
186 | 9 | static bool classof(const PredicateBase *PB) { |
187 | 9 | return PB->Type == PT_Switch; |
188 | 9 | } |
189 | | }; |
190 | | |
191 | | // This name is used in a few places, so kick it into their own namespace |
192 | | namespace PredicateInfoClasses { |
193 | | struct ValueDFS; |
194 | | } |
195 | | |
196 | | /// \brief Encapsulates PredicateInfo, including all data associated with memory |
197 | | /// accesses. |
198 | | class PredicateInfo { |
199 | | private: |
200 | | // Used to store information about each value we might rename. |
201 | | struct ValueInfo { |
202 | | // Information about each possible copy. During processing, this is each |
203 | | // inserted info. After processing, we move the uninserted ones to the |
204 | | // uninserted vector. |
205 | | SmallVector<PredicateBase *, 4> Infos; |
206 | | SmallVector<PredicateBase *, 4> UninsertedInfos; |
207 | | }; |
208 | | // This owns the all the predicate infos in the function, placed or not. |
209 | | iplist<PredicateBase> AllInfos; |
210 | | |
211 | | public: |
212 | | PredicateInfo(Function &, DominatorTree &, AssumptionCache &); |
213 | | ~PredicateInfo(); |
214 | | |
215 | | void verifyPredicateInfo() const; |
216 | | |
217 | | void dump() const; |
218 | | void print(raw_ostream &) const; |
219 | | |
220 | 1.63k | const PredicateBase *getPredicateInfoFor(const Value *V) const { |
221 | 1.63k | return PredicateMap.lookup(V); |
222 | 1.63k | } |
223 | | |
224 | | protected: |
225 | | // Used by PredicateInfo annotater, dumpers, and wrapper pass. |
226 | | friend class PredicateInfoAnnotatedWriter; |
227 | | friend class PredicateInfoPrinterLegacyPass; |
228 | | |
229 | | private: |
230 | | void buildPredicateInfo(); |
231 | | void processAssume(IntrinsicInst *, BasicBlock *, SmallPtrSetImpl<Value *> &); |
232 | | void processBranch(BranchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &); |
233 | | void processSwitch(SwitchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &); |
234 | | void renameUses(SmallPtrSetImpl<Value *> &); |
235 | | using ValueDFS = PredicateInfoClasses::ValueDFS; |
236 | | typedef SmallVectorImpl<ValueDFS> ValueDFSStack; |
237 | | void convertUsesToDFSOrdered(Value *, SmallVectorImpl<ValueDFS> &); |
238 | | Value *materializeStack(unsigned int &, ValueDFSStack &, Value *); |
239 | | bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const; |
240 | | void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &); |
241 | | ValueInfo &getOrCreateValueInfo(Value *); |
242 | | void addInfoFor(SmallPtrSetImpl<Value *> &OpsToRename, Value *Op, |
243 | | PredicateBase *PB); |
244 | | const ValueInfo &getValueInfo(Value *) const; |
245 | | Function &F; |
246 | | DominatorTree &DT; |
247 | | AssumptionCache &AC; |
248 | | OrderedInstructions OI; |
249 | | // This maps from copy operands to Predicate Info. Note that it does not own |
250 | | // the Predicate Info, they belong to the ValueInfo structs in the ValueInfos |
251 | | // vector. |
252 | | DenseMap<const Value *, const PredicateBase *> PredicateMap; |
253 | | // This stores info about each operand or comparison result we make copies |
254 | | // of. The real ValueInfos start at index 1, index 0 is unused so that we can |
255 | | // more easily detect invalid indexing. |
256 | | SmallVector<ValueInfo, 32> ValueInfos; |
257 | | // This gives the index into the ValueInfos array for a given Value. Because |
258 | | // 0 is not a valid Value Info index, you can use DenseMap::lookup and tell |
259 | | // whether it returned a valid result. |
260 | | DenseMap<Value *, unsigned int> ValueInfoNums; |
261 | | // The set of edges along which we can only handle phi uses, due to critical |
262 | | // edges. |
263 | | DenseSet<std::pair<BasicBlock *, BasicBlock *>> EdgeUsesOnly; |
264 | | }; |
265 | | |
266 | | // This pass does eager building and then printing of PredicateInfo. It is used |
267 | | // by |
268 | | // the tests to be able to build, dump, and verify PredicateInfo. |
269 | | class PredicateInfoPrinterLegacyPass : public FunctionPass { |
270 | | public: |
271 | | PredicateInfoPrinterLegacyPass(); |
272 | | |
273 | | static char ID; |
274 | | bool runOnFunction(Function &) override; |
275 | | void getAnalysisUsage(AnalysisUsage &AU) const override; |
276 | | }; |
277 | | |
278 | | /// \brief Printer pass for \c PredicateInfo. |
279 | | class PredicateInfoPrinterPass |
280 | | : public PassInfoMixin<PredicateInfoPrinterPass> { |
281 | | raw_ostream &OS; |
282 | | |
283 | | public: |
284 | 0 | explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {} |
285 | | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
286 | | }; |
287 | | |
288 | | /// \brief Verifier pass for \c PredicateInfo. |
289 | | struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> { |
290 | | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
291 | | }; |
292 | | |
293 | | } // end namespace llvm |
294 | | |
295 | | #endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H |