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   virtual ~PredicateBase() = default;
109 
110 protected:
111   PredicateBase(PredicateType PT, Value *Op) : Type(PT), OriginalOp(Op) {}
112 };
113 
114 class PredicateWithCondition : public PredicateBase {
115 public:
116   Value *Condition;
117   static bool classof(const PredicateBase *PB) {
118     return PB->Type == PT_Assume || PB->Type == PT_Branch ||
119            PB->Type == PT_Switch;
120   }
121 
122 protected:
123   PredicateWithCondition(PredicateType PT, Value *Op, Value *Condition)
124       : 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         AssumeInst(AssumeInst) {}
136   PredicateAssume() = delete;
137   static bool classof(const PredicateBase *PB) {
138     return PB->Type == PT_Assume;
139   }
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   static bool classof(const PredicateBase *PB) {
151     return PB->Type == PT_Branch || PB->Type == PT_Switch;
152   }
153 
154 protected:
155   PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From,
156                     BasicBlock *To, Value *Cond)
157       : 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         TrueEdge(TakenEdge) {}
169   PredicateBranch() = delete;
170   static bool classof(const PredicateBase *PB) {
171     return PB->Type == PT_Branch;
172   }
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         CaseValue(CaseValue), Switch(SI) {}
185   PredicateSwitch() = delete;
186   static bool classof(const PredicateBase *PB) {
187     return PB->Type == PT_Switch;
188   }
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   const PredicateBase *getPredicateInfoFor(const Value *V) const {
221     return PredicateMap.lookup(V);
222   }
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   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
296