LLVM  13.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 /// Constraint for a predicate of the form "cmp Pred Op, OtherOp", where Op
74 /// is the value the constraint applies to (the ssa.copy result).
78 };
79 
80 // Base class for all predicate information we provide.
81 // All of our predicate information has at least a comparison.
82 class PredicateBase : public ilist_node<PredicateBase> {
83 public:
85  // The original operand before we renamed it.
86  // This can be use by passes, when destroying predicateinfo, to know
87  // whether they can just drop the intrinsic, or have to merge metadata.
89  // The renamed operand in the condition used for this predicate. For nested
90  // predicates, this is different to OriginalOp which refers to the initial
91  // operand.
93  // The condition associated with this predicate.
95 
96  PredicateBase(const PredicateBase &) = delete;
97  PredicateBase &operator=(const PredicateBase &) = delete;
98  PredicateBase() = delete;
99  virtual ~PredicateBase() = default;
100  static bool classof(const PredicateBase *PB) {
101  return PB->Type == PT_Assume || PB->Type == PT_Branch ||
102  PB->Type == PT_Switch;
103  }
104 
105  /// Fetch condition in the form of PredicateConstraint, if possible.
107 
108 protected:
110  : Type(PT), OriginalOp(Op), Condition(Condition) {}
111 };
112 
113 // Provides predicate information for assumes. Since assumes are always true,
114 // we simply provide the assume instruction, so you can tell your relative
115 // position to it.
117 public:
121  PredicateAssume() = delete;
122  static bool classof(const PredicateBase *PB) {
123  return PB->Type == PT_Assume;
124  }
125 };
126 
127 // Mixin class for edge predicates. The FROM block is the block where the
128 // predicate originates, and the TO block is the block where the predicate is
129 // valid.
131 public:
134  PredicateWithEdge() = delete;
135  static bool classof(const PredicateBase *PB) {
136  return PB->Type == PT_Branch || PB->Type == PT_Switch;
137  }
138 
139 protected:
141  BasicBlock *To, Value *Cond)
142  : PredicateBase(PType, Op, Cond), From(From), To(To) {}
143 };
144 
145 // Provides predicate information for branches.
147 public:
148  // If true, SplitBB is the true successor, otherwise it's the false successor.
149  bool TrueEdge;
151  Value *Condition, bool TakenEdge)
152  : PredicateWithEdge(PT_Branch, Op, BranchBB, SplitBB, Condition),
153  TrueEdge(TakenEdge) {}
154  PredicateBranch() = delete;
155  static bool classof(const PredicateBase *PB) {
156  return PB->Type == PT_Branch;
157  }
158 };
159 
161 public:
163  // This is the switch instruction.
165  PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB,
167  : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB,
168  SI->getCondition()),
170  PredicateSwitch() = delete;
171  static bool classof(const PredicateBase *PB) {
172  return PB->Type == PT_Switch;
173  }
174 };
175 
176 /// Encapsulates PredicateInfo, including all data associated with memory
177 /// accesses.
179 public:
181  ~PredicateInfo();
182 
183  void verifyPredicateInfo() const;
184 
185  void dump() const;
186  void print(raw_ostream &) const;
187 
188  const PredicateBase *getPredicateInfoFor(const Value *V) const {
189  return PredicateMap.lookup(V);
190  }
191 
192 protected:
193  // Used by PredicateInfo annotater, dumpers, and wrapper pass.
196  friend class PredicateInfoBuilder;
197 
198 private:
199  Function &F;
200 
201  // This owns the all the predicate infos in the function, placed or not.
202  iplist<PredicateBase> AllInfos;
203 
204  // This maps from copy operands to Predicate Info. Note that it does not own
205  // the Predicate Info, they belong to the ValueInfo structs in the ValueInfos
206  // vector.
208  // The set of ssa_copy declarations we created with our custom mangling.
209  SmallSet<AssertingVH<Function>, 20> CreatedDeclarations;
210 };
211 
212 // This pass does eager building and then printing of PredicateInfo. It is used
213 // by
214 // the tests to be able to build, dump, and verify PredicateInfo.
216 public:
218 
219  static char ID;
220  bool runOnFunction(Function &) override;
221  void getAnalysisUsage(AnalysisUsage &AU) const override;
222 };
223 
224 /// Printer pass for \c PredicateInfo.
226  : public PassInfoMixin<PredicateInfoPrinterPass> {
227  raw_ostream &OS;
228 
229 public:
230  explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
232 };
233 
234 /// Verifier pass for \c PredicateInfo.
235 struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> {
237 };
238 
239 } // end namespace llvm
240 
241 #endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
This class represents lattice values for constants.
Definition: AllocatorList.h:23
llvm::PredicateInfoPrinterLegacyPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: PredicateInfo.cpp:860
llvm::PredicateAssume::PredicateAssume
PredicateAssume()=delete
llvm::PredicateSwitch::CaseValue
Value * CaseValue
Definition: PredicateInfo.h:162
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:61
Pass.h
llvm::PT_Branch
@ PT_Branch
Definition: PredicateInfo.h:71
ilist.h
llvm::PT_Assume
@ PT_Assume
Definition: PredicateInfo.h:71
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::PredicateWithEdge::PredicateWithEdge
PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From, BasicBlock *To, Value *Cond)
Definition: PredicateInfo.h:140
llvm::PredicateInfo::verifyPredicateInfo
void verifyPredicateInfo() const
Definition: PredicateInfo.cpp:850
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
DenseMap.h
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
llvm::PredicateBranch
Definition: PredicateInfo.h:146
llvm::Optional
Definition: APInt.h:33
llvm::PredicateSwitch::PredicateSwitch
PredicateSwitch()=delete
llvm::PredicateBranch::classof
static bool classof(const PredicateBase *PB)
Definition: PredicateInfo.h:155
llvm::iplist
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
Definition: ilist.h:390
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::PredicateInfoBuilder
Definition: PredicateInfo.cpp:251
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::PredicateAssume::PredicateAssume
PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition)
Definition: PredicateInfo.h:119
llvm::PredicateConstraint::OtherOp
Value * OtherOp
Definition: PredicateInfo.h:77
SI
@ SI
Definition: SIInstrInfo.cpp:7358
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::PredicateSwitch::PredicateSwitch
PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB, Value *CaseValue, SwitchInst *SI)
Definition: PredicateInfo.h:165
llvm::PredicateBranch::PredicateBranch
PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB, Value *Condition, bool TakenEdge)
Definition: PredicateInfo.h:150
llvm::PredicateSwitch::Switch
SwitchInst * Switch
Definition: PredicateInfo.h:164
llvm::PredicateInfoPrinterLegacyPass::runOnFunction
bool runOnFunction(Function &) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: PredicateInfo.cpp:880
llvm::PredicateBase::operator=
PredicateBase & operator=(const PredicateBase &)=delete
llvm::PredicateInfoPrinterLegacyPass
Definition: PredicateInfo.h:215
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::PredicateBranch::TrueEdge
bool TrueEdge
Definition: PredicateInfo.h:149
llvm::PredicateSwitch
Definition: PredicateInfo.h:160
llvm::PredicateInfo
Encapsulates PredicateInfo, including all data associated with memory accesses.
Definition: PredicateInfo.h:178
llvm::PredicateConstraint::Predicate
CmpInst::Predicate Predicate
Definition: PredicateInfo.h:76
llvm::PredicateInfo::dump
void dump() const
Definition: PredicateInfo.cpp:950
llvm::PredicateInfoPrinterLegacyPass::PredicateInfoPrinterLegacyPass
PredicateInfoPrinterLegacyPass()
Definition: PredicateInfo.cpp:854
llvm::PredicateInfoPrinterLegacyPass::ID
static char ID
Definition: PredicateInfo.h:219
llvm::PredicateBase::PredicateBase
PredicateBase(PredicateType PT, Value *Op, Value *Condition)
Definition: PredicateInfo.h:109
llvm::PT_Switch
@ PT_Switch
Definition: PredicateInfo.h:71
llvm::PredicateBase
Definition: PredicateInfo.h:82
llvm::PredicateWithEdge::classof
static bool classof(const PredicateBase *PB)
Definition: PredicateInfo.h:135
llvm::PredicateAssume::AssumeInst
IntrinsicInst * AssumeInst
Definition: PredicateInfo.h:118
llvm::PredicateBase::RenamedOp
Value * RenamedOp
Definition: PredicateInfo.h:92
llvm::DenseMap
Definition: DenseMap.h:714
llvm::PredicateWithEdge
Definition: PredicateInfo.h:130
llvm::PredicateInfoVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: PredicateInfo.cpp:955
llvm::PredicateInfoVerifierPass
Verifier pass for PredicateInfo.
Definition: PredicateInfo.h:235
llvm::PredicateSwitch::classof
static bool classof(const PredicateBase *PB)
Definition: PredicateInfo.h:171
llvm::PredicateBase::Condition
Value * Condition
Definition: PredicateInfo.h:94
llvm::PredicateConstraint
Constraint for a predicate of the form "cmp Pred Op, OtherOp", where Op is the value the constraint a...
Definition: PredicateInfo.h:75
llvm::PredicateInfo::getPredicateInfoFor
const PredicateBase * getPredicateInfoFor(const Value *V) const
Definition: PredicateInfo.h:188
llvm::PredicateType
PredicateType
Definition: PredicateInfo.h:71
llvm::PredicateInfoAnnotatedWriter
An assembly annotator class to print PredicateInfo information in comments.
Definition: PredicateInfo.cpp:906
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:167
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::PredicateBranch::PredicateBranch
PredicateBranch()=delete
llvm::PredicateBase::Type
PredicateType Type
Definition: PredicateInfo.h:84
ValueHandle.h
llvm::PredicateAssume::classof
static bool classof(const PredicateBase *PB)
Definition: PredicateInfo.h:122
llvm::PredicateInfoPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: PredicateInfo.cpp:892
llvm::ilist_node
Definition: ilist_node.h:148
llvm::PredicateBase::classof
static bool classof(const PredicateBase *PB)
Definition: PredicateInfo.h:100
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:302
llvm::PredicateInfoPrinterPass::PredicateInfoPrinterPass
PredicateInfoPrinterPass(raw_ostream &OS)
Definition: PredicateInfo.h:230
PassManager.h
llvm::PredicateInfo::print
void print(raw_ostream &) const
Definition: PredicateInfo.cpp:945
llvm::PredicateBase::PredicateBase
PredicateBase()=delete
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
llvm::PredicateWithEdge::From
BasicBlock * From
Definition: PredicateInfo.h:132
llvm::PredicateBase::OriginalOp
Value * OriginalOp
Definition: PredicateInfo.h:88
llvm::PredicateWithEdge::PredicateWithEdge
PredicateWithEdge()=delete
Instructions.h
llvm::PredicateInfoPrinterPass
Printer pass for PredicateInfo.
Definition: PredicateInfo.h:225
llvm::PredicateInfo::~PredicateInfo
~PredicateInfo()
Definition: PredicateInfo.cpp:785
ilist_node.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:43
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::PredicateBase::~PredicateBase
virtual ~PredicateBase()=default
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3159
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::PredicateBase::getConstraint
Optional< PredicateConstraint > getConstraint() const
Fetch condition in the form of PredicateConstraint, if possible.
Definition: PredicateInfo.cpp:800
llvm::PredicateInfo::PredicateInfo
PredicateInfo(Function &, DominatorTree &, AssumptionCache &)
Definition: PredicateInfo.cpp:776
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::PredicateAssume
Definition: PredicateInfo.h:116
SmallSet.h
llvm::PredicateWithEdge::To
BasicBlock * To
Definition: PredicateInfo.h:133