1 | //===- PredicateInfo.h - Build PredicateInfo ----------------------*-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 | /// \file |
10 | /// This file implements the PredicateInfo analysis, which creates an Extended |
11 | /// SSA form for operations used in branch comparisons and llvm.assume |
12 | /// comparisons. |
13 | /// |
14 | /// Copies of these operations are inserted into the true/false edge (and after |
15 | /// assumes), and information attached to the copies. All uses of the original |
16 | /// operation in blocks dominated by the true/false edge (and assume), are |
17 | /// replaced with uses of the copies. This enables passes to easily and sparsely |
18 | /// propagate condition based info into the operations that may be affected. |
19 | /// |
20 | /// Example: |
21 | /// %cmp = icmp eq i32 %x, 50 |
22 | /// br i1 %cmp, label %true, label %false |
23 | /// true: |
24 | /// ret i32 %x |
25 | /// false: |
26 | /// ret i32 1 |
27 | /// |
28 | /// will become |
29 | /// |
30 | /// %cmp = icmp eq i32, %x, 50 |
31 | /// br i1 %cmp, label %true, label %false |
32 | /// true: |
33 | /// %x.0 = call \@llvm.ssa_copy.i32(i32 %x) |
34 | /// ret i32 %x.0 |
35 | /// false: |
36 | /// ret i32 1 |
37 | /// |
38 | /// Using getPredicateInfoFor on x.0 will give you the comparison it is |
39 | /// dominated by (the icmp), and that you are located in the true edge of that |
40 | /// comparison, which tells you x.0 is 50. |
41 | /// |
42 | /// In order to reduce the number of copies inserted, predicateinfo is only |
43 | /// inserted where it would actually be live. This means if there are no uses of |
44 | /// an operation dominated by the branch edges, or by an assume, the associated |
45 | /// predicate info is never inserted. |
46 | /// |
47 | /// |
48 | //===----------------------------------------------------------------------===// |
49 | |
50 | #ifndef LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H |
51 | #define LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H |
52 | |
53 | #include "llvm/ADT/DenseMap.h" |
54 | #include "llvm/ADT/SmallSet.h" |
55 | #include "llvm/ADT/ilist.h" |
56 | #include "llvm/ADT/ilist_node.h" |
57 | #include "llvm/IR/Instructions.h" |
58 | #include "llvm/IR/PassManager.h" |
59 | #include "llvm/IR/ValueHandle.h" |
60 | |
61 | namespace llvm { |
62 | |
63 | class AssumptionCache; |
64 | class DominatorTree; |
65 | class Function; |
66 | class Value; |
67 | class IntrinsicInst; |
68 | class raw_ostream; |
69 | |
70 | enum PredicateType { PT_Branch, PT_Assume, PT_Switch }; |
71 | |
72 | /// Constraint for a predicate of the form "cmp Pred Op, OtherOp", where Op |
73 | /// is the value the constraint applies to (the ssa.copy result). |
74 | struct PredicateConstraint { |
75 | CmpInst::Predicate Predicate; |
76 | Value *OtherOp; |
77 | }; |
78 | |
79 | // Base class for all predicate information we provide. |
80 | // All of our predicate information has at least a comparison. |
81 | class PredicateBase : public ilist_node<PredicateBase> { |
82 | public: |
83 | PredicateType Type; |
84 | // The original operand before we renamed it. |
85 | // This can be use by passes, when destroying predicateinfo, to know |
86 | // whether they can just drop the intrinsic, or have to merge metadata. |
87 | Value *OriginalOp; |
88 | // The renamed operand in the condition used for this predicate. For nested |
89 | // predicates, this is different to OriginalOp which refers to the initial |
90 | // operand. |
91 | Value *RenamedOp; |
92 | // The condition associated with this predicate. |
93 | Value *Condition; |
94 | |
95 | PredicateBase(const PredicateBase &) = delete; |
96 | PredicateBase &operator=(const PredicateBase &) = delete; |
97 | PredicateBase() = delete; |
98 | virtual ~PredicateBase() = default; |
99 | static bool classof(const PredicateBase *PB) { |
100 | return PB->Type == PT_Assume || PB->Type == PT_Branch || |
101 | PB->Type == PT_Switch; |
102 | } |
103 | |
104 | /// Fetch condition in the form of PredicateConstraint, if possible. |
105 | std::optional<PredicateConstraint> getConstraint() const; |
106 | |
107 | protected: |
108 | PredicateBase(PredicateType PT, Value *Op, Value *Condition) |
109 | : Type(PT), OriginalOp(Op), Condition(Condition) {} |
110 | }; |
111 | |
112 | // Provides predicate information for assumes. Since assumes are always true, |
113 | // we simply provide the assume instruction, so you can tell your relative |
114 | // position to it. |
115 | class PredicateAssume : public PredicateBase { |
116 | public: |
117 | IntrinsicInst *AssumeInst; |
118 | PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition) |
119 | : PredicateBase(PT_Assume, Op, Condition), AssumeInst(AssumeInst) {} |
120 | PredicateAssume() = delete; |
121 | static bool classof(const PredicateBase *PB) { |
122 | return PB->Type == PT_Assume; |
123 | } |
124 | }; |
125 | |
126 | // Mixin class for edge predicates. The FROM block is the block where the |
127 | // predicate originates, and the TO block is the block where the predicate is |
128 | // valid. |
129 | class PredicateWithEdge : public PredicateBase { |
130 | public: |
131 | BasicBlock *From; |
132 | BasicBlock *To; |
133 | PredicateWithEdge() = delete; |
134 | static bool classof(const PredicateBase *PB) { |
135 | return PB->Type == PT_Branch || PB->Type == PT_Switch; |
136 | } |
137 | |
138 | protected: |
139 | PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From, |
140 | BasicBlock *To, Value *Cond) |
141 | : PredicateBase(PType, Op, Cond), From(From), To(To) {} |
142 | }; |
143 | |
144 | // Provides predicate information for branches. |
145 | class PredicateBranch : public PredicateWithEdge { |
146 | public: |
147 | // If true, SplitBB is the true successor, otherwise it's the false successor. |
148 | bool TrueEdge; |
149 | PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB, |
150 | Value *Condition, bool TakenEdge) |
151 | : PredicateWithEdge(PT_Branch, Op, BranchBB, SplitBB, Condition), |
152 | TrueEdge(TakenEdge) {} |
153 | PredicateBranch() = delete; |
154 | static bool classof(const PredicateBase *PB) { |
155 | return PB->Type == PT_Branch; |
156 | } |
157 | }; |
158 | |
159 | class PredicateSwitch : public PredicateWithEdge { |
160 | public: |
161 | Value *CaseValue; |
162 | // This is the switch instruction. |
163 | SwitchInst *Switch; |
164 | PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB, |
165 | Value *CaseValue, SwitchInst *SI) |
166 | : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB, |
167 | SI->getCondition()), |
168 | CaseValue(CaseValue), Switch(SI) {} |
169 | PredicateSwitch() = delete; |
170 | static bool classof(const PredicateBase *PB) { |
171 | return PB->Type == PT_Switch; |
172 | } |
173 | }; |
174 | |
175 | /// Encapsulates PredicateInfo, including all data associated with memory |
176 | /// accesses. |
177 | class PredicateInfo { |
178 | public: |
179 | PredicateInfo(Function &, DominatorTree &, AssumptionCache &); |
180 | ~PredicateInfo(); |
181 | |
182 | void verifyPredicateInfo() const; |
183 | |
184 | void dump() const; |
185 | void print(raw_ostream &) const; |
186 | |
187 | const PredicateBase *getPredicateInfoFor(const Value *V) const { |
188 | return PredicateMap.lookup(Val: V); |
189 | } |
190 | |
191 | protected: |
192 | // Used by PredicateInfo annotater, dumpers, and wrapper pass. |
193 | friend class PredicateInfoAnnotatedWriter; |
194 | friend class PredicateInfoBuilder; |
195 | |
196 | private: |
197 | Function &F; |
198 | |
199 | // This owns the all the predicate infos in the function, placed or not. |
200 | iplist<PredicateBase> AllInfos; |
201 | |
202 | // This maps from copy operands to Predicate Info. Note that it does not own |
203 | // the Predicate Info, they belong to the ValueInfo structs in the ValueInfos |
204 | // vector. |
205 | DenseMap<const Value *, const PredicateBase *> PredicateMap; |
206 | // The set of ssa_copy declarations we created with our custom mangling. |
207 | SmallSet<AssertingVH<Function>, 20> CreatedDeclarations; |
208 | }; |
209 | |
210 | /// Printer pass for \c PredicateInfo. |
211 | class PredicateInfoPrinterPass |
212 | : public PassInfoMixin<PredicateInfoPrinterPass> { |
213 | raw_ostream &OS; |
214 | |
215 | public: |
216 | explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {} |
217 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
218 | static bool isRequired() { return true; } |
219 | }; |
220 | |
221 | /// Verifier pass for \c PredicateInfo. |
222 | struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> { |
223 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
224 | static bool isRequired() { return true; } |
225 | }; |
226 | |
227 | } // end namespace llvm |
228 | |
229 | #endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H |
230 | |