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/ilist.h"
55 #include "llvm/ADT/ilist_node.h"
56 #include "llvm/IR/Instructions.h"
57 #include "llvm/IR/PassManager.h"
58 #include "llvm/IR/Value.h"
59 #include "llvm/Pass.h"
60 
61 namespace llvm {
62 
63 class AssumptionCache;
64 class DominatorTree;
65 class Function;
66 class IntrinsicInst;
67 class raw_ostream;
68 
70 
71 /// Constraint for a predicate of the form "cmp Pred Op, OtherOp", where Op
72 /// is the value the constraint applies to (the ssa.copy result).
76 };
77 
78 // Base class for all predicate information we provide.
79 // All of our predicate information has at least a comparison.
80 class PredicateBase : public ilist_node<PredicateBase> {
81 public:
83  // The original operand before we renamed it.
84  // This can be use by passes, when destroying predicateinfo, to know
85  // whether they can just drop the intrinsic, or have to merge metadata.
87  // The renamed operand in the condition used for this predicate. For nested
88  // predicates, this is different to OriginalOp which refers to the initial
89  // operand.
91  // The condition associated with this predicate.
93 
94  PredicateBase(const PredicateBase &) = delete;
95  PredicateBase &operator=(const PredicateBase &) = delete;
96  PredicateBase() = delete;
97  virtual ~PredicateBase() = default;
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  /// Fetch condition in the form of PredicateConstraint, if possible.
105 
106 protected:
108  : Type(PT), OriginalOp(Op), Condition(Condition) {}
109 };
110 
111 // Provides predicate information for assumes. Since assumes are always true,
112 // we simply provide the assume instruction, so you can tell your relative
113 // position to it.
115 public:
119  PredicateAssume() = delete;
120  static bool classof(const PredicateBase *PB) {
121  return PB->Type == PT_Assume;
122  }
123 };
124 
125 // Mixin class for edge predicates. The FROM block is the block where the
126 // predicate originates, and the TO block is the block where the predicate is
127 // valid.
129 public:
132  PredicateWithEdge() = delete;
133  static bool classof(const PredicateBase *PB) {
134  return PB->Type == PT_Branch || PB->Type == PT_Switch;
135  }
136 
137 protected:
139  BasicBlock *To, Value *Cond)
140  : PredicateBase(PType, Op, Cond), From(From), To(To) {}
141 };
142 
143 // Provides predicate information for branches.
145 public:
146  // If true, SplitBB is the true successor, otherwise it's the false successor.
147  bool TrueEdge;
149  Value *Condition, bool TakenEdge)
150  : PredicateWithEdge(PT_Branch, Op, BranchBB, SplitBB, Condition),
151  TrueEdge(TakenEdge) {}
152  PredicateBranch() = delete;
153  static bool classof(const PredicateBase *PB) {
154  return PB->Type == PT_Branch;
155  }
156 };
157 
159 public:
161  // This is the switch instruction.
163  PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB,
165  : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB,
166  SI->getCondition()),
168  PredicateSwitch() = delete;
169  static bool classof(const PredicateBase *PB) {
170  return PB->Type == PT_Switch;
171  }
172 };
173 
174 /// Encapsulates PredicateInfo, including all data associated with memory
175 /// accesses.
177 public:
179  ~PredicateInfo() = default;
180 
181  void verifyPredicateInfo() const;
182 
183  void dump() const;
184  void print(raw_ostream &) const;
185 
186  const PredicateBase *getPredicateInfoFor(const Value *V) const {
187  return PredicateMap.lookup(V);
188  }
189 
190 protected:
191  // Used by PredicateInfo annotater, dumpers, and wrapper pass.
194  friend class PredicateInfoBuilder;
195 
196 private:
197  Function &F;
198 
199  // This owns the all the predicate infos in the function, placed or not.
200  iplist<PredicateBase> AllInfos;
201 
202  // This maps from copy operands to Predicate Info. Note that it does not own
203  // the Predicate Info, they belong to the ValueInfo structs in the ValueInfos
204  // vector.
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
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
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:824
llvm::PredicateAssume::PredicateAssume
PredicateAssume()=delete
llvm::PredicateSwitch::CaseValue
Value * CaseValue
Definition: PredicateInfo.h:160
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:69
ilist.h
llvm::PT_Assume
@ PT_Assume
Definition: PredicateInfo.h:69
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::AssumeInst
This represents the llvm.assume intrinsic.
Definition: IntrinsicInst.h:1272
llvm::PredicateWithEdge::PredicateWithEdge
PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From, BasicBlock *To, Value *Cond)
Definition: PredicateInfo.h:138
llvm::PredicateInfo::verifyPredicateInfo
void verifyPredicateInfo() const
Definition: PredicateInfo.cpp:814
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::PredicateBranch
Definition: PredicateInfo.h:144
llvm::Optional
Definition: APInt.h:33
llvm::PredicateSwitch::PredicateSwitch
PredicateSwitch()=delete
llvm::PredicateBranch::classof
static bool classof(const PredicateBase *PB)
Definition: PredicateInfo.h:153
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:249
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::PredicateAssume::PredicateAssume
PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition)
Definition: PredicateInfo.h:117
llvm::PredicateConstraint::OtherOp
Value * OtherOp
Definition: PredicateInfo.h:75
SI
@ SI
Definition: SIInstrInfo.cpp:7411
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:163
llvm::PredicateBranch::PredicateBranch
PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB, Value *Condition, bool TakenEdge)
Definition: PredicateInfo.h:148
llvm::PredicateSwitch::Switch
SwitchInst * Switch
Definition: PredicateInfo.h:162
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:830
llvm::PredicateBase::operator=
PredicateBase & operator=(const PredicateBase &)=delete
llvm::PredicateInfoPrinterLegacyPass
Definition: PredicateInfo.h:211
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:147
llvm::PredicateSwitch
Definition: PredicateInfo.h:158
llvm::PredicateInfo::~PredicateInfo
~PredicateInfo()=default
llvm::PredicateInfo
Encapsulates PredicateInfo, including all data associated with memory accesses.
Definition: PredicateInfo.h:176
llvm::PredicateConstraint::Predicate
CmpInst::Predicate Predicate
Definition: PredicateInfo.h:74
llvm::PredicateInfo::dump
void dump() const
Definition: PredicateInfo.cpp:897
llvm::PredicateInfoPrinterLegacyPass::PredicateInfoPrinterLegacyPass
PredicateInfoPrinterLegacyPass()
Definition: PredicateInfo.cpp:818
llvm::PredicateInfoPrinterLegacyPass::ID
static char ID
Definition: PredicateInfo.h:215
llvm::PredicateBase::PredicateBase
PredicateBase(PredicateType PT, Value *Op, Value *Condition)
Definition: PredicateInfo.h:107
llvm::PT_Switch
@ PT_Switch
Definition: PredicateInfo.h:69
llvm::PredicateBase
Definition: PredicateInfo.h:80
llvm::PredicateWithEdge::classof
static bool classof(const PredicateBase *PB)
Definition: PredicateInfo.h:133
llvm::PredicateAssume::AssumeInst
IntrinsicInst * AssumeInst
Definition: PredicateInfo.h:116
llvm::PredicateBase::RenamedOp
Value * RenamedOp
Definition: PredicateInfo.h:90
llvm::DenseMap
Definition: DenseMap.h:714
llvm::PredicateWithEdge
Definition: PredicateInfo.h:128
llvm::PredicateInfoVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: PredicateInfo.cpp:902
llvm::PredicateInfoVerifierPass
Verifier pass for PredicateInfo.
Definition: PredicateInfo.h:231
llvm::PredicateSwitch::classof
static bool classof(const PredicateBase *PB)
Definition: PredicateInfo.h:169
llvm::PredicateBase::Condition
Value * Condition
Definition: PredicateInfo.h:92
llvm::PredicateConstraint
Constraint for a predicate of the form "cmp Pred Op, OtherOp", where Op is the value the constraint a...
Definition: PredicateInfo.h:73
llvm::PredicateInfo::getPredicateInfoFor
const PredicateBase * getPredicateInfoFor(const Value *V) const
Definition: PredicateInfo.h:186
llvm::PredicateType
PredicateType
Definition: PredicateInfo.h:69
llvm::PredicateInfoAnnotatedWriter
An assembly annotator class to print PredicateInfo information in comments.
Definition: PredicateInfo.cpp:853
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:82
llvm::PredicateAssume::classof
static bool classof(const PredicateBase *PB)
Definition: PredicateInfo.h:120
llvm::PredicateInfoPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: PredicateInfo.cpp:840
llvm::ilist_node
Definition: ilist_node.h:148
llvm::PredicateBase::classof
static bool classof(const PredicateBase *PB)
Definition: PredicateInfo.h:98
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::PredicateInfoPrinterPass::PredicateInfoPrinterPass
PredicateInfoPrinterPass(raw_ostream &OS)
Definition: PredicateInfo.h:226
PassManager.h
llvm::PredicateInfo::print
void print(raw_ostream &) const
Definition: PredicateInfo.cpp:892
llvm::PredicateBase::PredicateBase
PredicateBase()=delete
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
llvm::PredicateWithEdge::From
BasicBlock * From
Definition: PredicateInfo.h:130
llvm::PredicateBase::OriginalOp
Value * OriginalOp
Definition: PredicateInfo.h:86
llvm::PredicateWithEdge::PredicateWithEdge
PredicateWithEdge()=delete
Instructions.h
llvm::PredicateInfoPrinterPass
Printer pass for PredicateInfo.
Definition: PredicateInfo.h:221
ilist_node.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
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:3151
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:764
llvm::PredicateInfo::PredicateInfo
PredicateInfo(Function &, DominatorTree &, AssumptionCache &)
Definition: PredicateInfo.cpp:757
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::PredicateAssume
Definition: PredicateInfo.h:114
llvm::PredicateWithEdge::To
BasicBlock * To
Definition: PredicateInfo.h:131