LLVM  6.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 /// \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"
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"
74 #include "llvm/Support/Casting.h"
75 #include "llvm/Support/Compiler.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 
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:
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.
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 
115 public:
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:
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.
131 public:
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.
146 public:
149  PredicateWithEdge() = delete;
150  static bool classof(const PredicateBase *PB) {
151  return PB->Type == PT_Branch || PB->Type == PT_Switch;
152  }
153 
154 protected:
156  BasicBlock *To, Value *Cond)
157  : PredicateWithCondition(PType, Op, Cond), From(From), To(To) {}
158 };
159 
160 // Provides predicate information for branches.
162 public:
163  // If true, SplitBB is the true successor, otherwise it's the false successor.
164  bool TrueEdge;
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 
176 public:
178  // This is the switch instruction.
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.
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.
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:
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.
228 
229 private:
230  void buildPredicateInfo();
231  void processAssume(IntrinsicInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
232  void processBranch(BranchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
234  void renameUses(SmallPtrSetImpl<Value *> &);
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;
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.
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.
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.
270 public:
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.
280  : public PassInfoMixin<PredicateInfoPrinterPass> {
281  raw_ostream &OS;
282 
283 public:
284  explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
286 };
287 
288 /// \brief Verifier pass for \c PredicateInfo.
289 struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> {
291 };
292 
293 } // end namespace llvm
294 
295 #endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
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:221
PredicateWithCondition(PredicateType PT, Value *Op, Value *Condition)
PredicateBase & operator=(const PredicateBase &)=delete
A cache of .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:365
static bool classof(const PredicateBase *PB)
PredicateType
Definition: PredicateInfo.h:94
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
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:153
static bool processSwitch(SwitchInst *SI, LazyValueInfo *LVI)
Simplify a switch instruction by removing cases which can never fire.
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
Conditional or Unconditional Branch instruction.
virtual ~PredicateBase()=default
PredicateBase(PredicateType PT, Value *Op)
Printer pass for PredicateInfo.
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:403
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:864
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:44
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