LLVM  11.0.0git
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/SmallSet.h"
55 #include "llvm/ADT/ilist.h"
56 #include "llvm/ADT/ilist_node.h"
57 #include "llvm/IR/Instructions.h"
58 #include "llvm/IR/PassManager.h"
59 #include "llvm/IR/Value.h"
60 #include "llvm/IR/ValueHandle.h"
61 #include "llvm/Pass.h"
62 
63 namespace llvm {
64 
65 class AssumptionCache;
66 class DominatorTree;
67 class Function;
68 class IntrinsicInst;
69 class raw_ostream;
70 
72 
73 // Base class for all predicate information we provide.
74 // All of our predicate information has at least a comparison.
75 class PredicateBase : public ilist_node<PredicateBase> {
76 public:
78  // The original operand before we renamed it.
79  // This can be use by passes, when destroying predicateinfo, to know
80  // whether they can just drop the intrinsic, or have to merge metadata.
82  // The renamed operand in the condition used for this predicate. For nested
83  // predicates, this is different to OriginalOp which refers to the initial
84  // operand.
86  PredicateBase(const PredicateBase &) = delete;
87  PredicateBase &operator=(const PredicateBase &) = delete;
88  PredicateBase() = delete;
89  virtual ~PredicateBase() = default;
90 
91 protected:
92  PredicateBase(PredicateType PT, Value *Op) : Type(PT), OriginalOp(Op) {}
93 };
94 
96 public:
98  static bool classof(const PredicateBase *PB) {
99  return PB->Type == PT_Assume || PB->Type == PT_Branch ||
100  PB->Type == PT_Switch;
101  }
102 
103 protected:
105  : PredicateBase(PT, Op), Condition(Condition) {}
106 };
107 
108 // Provides predicate information for assumes. Since assumes are always true,
109 // we simply provide the assume instruction, so you can tell your relative
110 // position to it.
112 public:
114  PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition)
115  : PredicateWithCondition(PT_Assume, Op, Condition),
116  AssumeInst(AssumeInst) {}
117  PredicateAssume() = delete;
118  static bool classof(const PredicateBase *PB) {
119  return PB->Type == PT_Assume;
120  }
121 };
122 
123 // Mixin class for edge predicates. The FROM block is the block where the
124 // predicate originates, and the TO block is the block where the predicate is
125 // valid.
127 public:
130  PredicateWithEdge() = delete;
131  static bool classof(const PredicateBase *PB) {
132  return PB->Type == PT_Branch || PB->Type == PT_Switch;
133  }
134 
135 protected:
137  BasicBlock *To, Value *Cond)
138  : PredicateWithCondition(PType, Op, Cond), From(From), To(To) {}
139 };
140 
141 // Provides predicate information for branches.
143 public:
144  // If true, SplitBB is the true successor, otherwise it's the false successor.
145  bool TrueEdge;
147  Value *Condition, bool TakenEdge)
148  : PredicateWithEdge(PT_Branch, Op, BranchBB, SplitBB, Condition),
149  TrueEdge(TakenEdge) {}
150  PredicateBranch() = delete;
151  static bool classof(const PredicateBase *PB) {
152  return PB->Type == PT_Branch;
153  }
154 };
155 
157 public:
159  // This is the switch instruction.
161  PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB,
162  Value *CaseValue, SwitchInst *SI)
163  : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB,
164  SI->getCondition()),
165  CaseValue(CaseValue), Switch(SI) {}
166  PredicateSwitch() = delete;
167  static bool classof(const PredicateBase *PB) {
168  return PB->Type == PT_Switch;
169  }
170 };
171 
172 /// Encapsulates PredicateInfo, including all data associated with memory
173 /// accesses.
175 public:
177  ~PredicateInfo();
178 
179  void verifyPredicateInfo() const;
180 
181  void dump() const;
182  void print(raw_ostream &) const;
183 
184  const PredicateBase *getPredicateInfoFor(const Value *V) const {
185  return PredicateMap.lookup(V);
186  }
187 
188 protected:
189  // Used by PredicateInfo annotater, dumpers, and wrapper pass.
192  friend class PredicateInfoBuilder;
193 
194 private:
195  Function &F;
196 
197  // This owns the all the predicate infos in the function, placed or not.
198  iplist<PredicateBase> AllInfos;
199 
200  // This maps from copy operands to Predicate Info. Note that it does not own
201  // the Predicate Info, they belong to the ValueInfo structs in the ValueInfos
202  // vector.
204  // The set of ssa_copy declarations we created with our custom mangling.
205  SmallSet<AssertingVH<Function>, 20> CreatedDeclarations;
206 };
207 
208 // This pass does eager building and then printing of PredicateInfo. It is used
209 // by
210 // the tests to be able to build, dump, and verify PredicateInfo.
212 public:
214 
215  static char ID;
216  bool runOnFunction(Function &) override;
217  void getAnalysisUsage(AnalysisUsage &AU) const override;
218 };
219 
220 /// Printer pass for \c PredicateInfo.
222  : public PassInfoMixin<PredicateInfoPrinterPass> {
223  raw_ostream &OS;
224 
225 public:
226  explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
228 };
229 
230 /// Verifier pass for \c PredicateInfo.
231 struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> {
233 };
234 
235 } // end namespace llvm
236 
237 #endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
static bool classof(const PredicateBase *PB)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
PredicateWithCondition(PredicateType PT, Value *Op, Value *Condition)
PredicateBase & operator=(const PredicateBase &)=delete
A cache of @llvm.assume calls within a function.
F(f)
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)
Definition: PredicateInfo.h:98
PredicateType
Definition: PredicateInfo.h:71
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
PredicateInfoPrinterPass(raw_ostream &OS)
SmallVector< MachineOperand, 4 > Cond
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
virtual ~PredicateBase()=default
PredicateBase(PredicateType PT, Value *Op)
Definition: PredicateInfo.h:92
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)
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)
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
Definition: PredicateInfo.h:77
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.
This header defines various interfaces for pass management in LLVM.
IntrinsicInst * AssumeInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44