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