LLVM  8.0.0svn
PredicateInfo.h
Go to the documentation of this file.
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"
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"
77 #include "llvm/Support/Casting.h"
78 #include "llvm/Support/Compiler.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 
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:
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.
107  PredicateBase(const PredicateBase &) = delete;
108  PredicateBase &operator=(const PredicateBase &) = delete;
109  PredicateBase() = delete;
110  virtual ~PredicateBase() = default;
111 
112 protected:
113  PredicateBase(PredicateType PT, Value *Op) : Type(PT), OriginalOp(Op) {}
114 };
115 
117 public:
119  static bool classof(const PredicateBase *PB) {
120  return PB->Type == PT_Assume || PB->Type == PT_Branch ||
121  PB->Type == PT_Switch;
122  }
123 
124 protected:
126  : 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.
133 public:
135  PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition)
136  : PredicateWithCondition(PT_Assume, Op, Condition),
137  AssumeInst(AssumeInst) {}
138  PredicateAssume() = delete;
139  static bool classof(const PredicateBase *PB) {
140  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.
148 public:
151  PredicateWithEdge() = delete;
152  static bool classof(const PredicateBase *PB) {
153  return PB->Type == PT_Branch || PB->Type == PT_Switch;
154  }
155 
156 protected:
158  BasicBlock *To, Value *Cond)
159  : PredicateWithCondition(PType, Op, Cond), From(From), To(To) {}
160 };
161 
162 // Provides predicate information for branches.
164 public:
165  // If true, SplitBB is the true successor, otherwise it's the false successor.
166  bool TrueEdge;
168  Value *Condition, bool TakenEdge)
169  : PredicateWithEdge(PT_Branch, Op, BranchBB, SplitBB, Condition),
170  TrueEdge(TakenEdge) {}
171  PredicateBranch() = delete;
172  static bool classof(const PredicateBase *PB) {
173  return PB->Type == PT_Branch;
174  }
175 };
176 
178 public:
180  // This is the switch instruction.
182  PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB,
183  Value *CaseValue, SwitchInst *SI)
184  : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB,
185  SI->getCondition()),
186  CaseValue(CaseValue), Switch(SI) {}
187  PredicateSwitch() = delete;
188  static bool classof(const PredicateBase *PB) {
189  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.
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.
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:
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  return PredicateMap.lookup(V);
224  }
225 
226 protected:
227  // Used by PredicateInfo annotater, dumpers, and wrapper pass.
230 
231 private:
232  void buildPredicateInfo();
233  void processAssume(IntrinsicInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
234  void processBranch(BranchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
236  void renameUses(SmallPtrSetImpl<Value *> &);
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;
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.
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.
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.
274 public:
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.
284  : public PassInfoMixin<PredicateInfoPrinterPass> {
285  raw_ostream &OS;
286 
287 public:
288  explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
290 };
291 
292 /// Verifier pass for \c PredicateInfo.
293 struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> {
295 };
296 
297 } // end namespace llvm
298 
299 #endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
static bool processSwitch(SwitchInst *SI, LazyValueInfo *LVI, DominatorTree *DT)
Simplify a switch instruction by removing cases which can never fire.
static bool classof(const PredicateBase *PB)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Implements a dense probed hash-table based set.
Definition: DenseSet.h:250
PredicateWithCondition(PredicateType PT, Value *Op, Value *Condition)
PredicateBase & operator=(const PredicateBase &)=delete
A cache of @llvm.assume calls within a function.
F(f)
This defines the Use class.
Verifier pass for PredicateInfo.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB, Value *Condition, bool TakenEdge)
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:366
static bool classof(const PredicateBase *PB)
PredicateType
Definition: PredicateInfo.h:96
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
PredicateInfoPrinterPass(raw_ostream &OS)
PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition)
PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB, Value *CaseValue, SwitchInst *SI)
static bool classof(const PredicateBase *PB)
static bool runOnFunction(Function &F, bool PostInlining)
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Conditional or Unconditional Branch instruction.
virtual ~PredicateBase()=default
PredicateBase(PredicateType PT, Value *Op)
Printer pass for PredicateInfo.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
An intrusive list with ownership and callbacks specified/controlled by ilist_traits, only with API safe for polymorphic types.
Definition: ilist.h:390
static bool classof(const PredicateBase *PB)
PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From, BasicBlock *To, Value *Cond)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Module.h This file contains the declarations for the Module class.
Encapsulates PredicateInfo, including all data associated with memory accesses.
const PredicateBase * getPredicateInfoFor(const Value *V) const
An assembly annotator class to print PredicateInfo information in comments.
Multiway switch.
LLVM Value Representation.
Definition: Value.h:73
PredicateType Type
static bool classof(const PredicateBase *PB)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
A container for analyses that lazily runs them and caches their results.
IntrinsicInst * AssumeInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44