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