LLVM 18.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"
58#include "llvm/IR/PassManager.h"
59#include "llvm/IR/ValueHandle.h"
60#include "llvm/Pass.h"
61
62namespace llvm {
63
64class AssumptionCache;
65class DominatorTree;
66class Function;
67class Value;
68class IntrinsicInst;
69class 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.
82class PredicateBase : public ilist_node<PredicateBase> {
83public:
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;
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.
106 std::optional<PredicateConstraint> getConstraint() const;
107
108protected:
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.
117public:
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.
131public:
135 static bool classof(const PredicateBase *PB) {
136 return PB->Type == PT_Branch || PB->Type == PT_Switch;
137 }
138
139protected:
142 : PredicateBase(PType, Op, Cond), From(From), To(To) {}
143};
144
145// Provides predicate information for branches.
147public:
148 // If true, SplitBB is the true successor, otherwise it's the false successor.
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
161public:
163 // This is the switch instruction.
167 : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB,
168 SI->getCondition()),
169 CaseValue(CaseValue), Switch(SI) {}
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.
179public:
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
192protected:
193 // Used by PredicateInfo annotater, dumpers, and wrapper pass.
197
198private:
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.
216public:
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
229public:
232};
233
234/// Verifier pass for \c PredicateInfo.
235struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> {
237};
238
239} // end namespace llvm
240
241#endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
This file defines the DenseMap class.
#define F(x, y, z)
Definition: MD5.cpp:55
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
This header defines various interfaces for pass management in LLVM.
const SmallVectorImpl< MachineOperand > & Cond
raw_pwrite_stream & OS
This file defines the SmallSet class.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
Represent the analysis usage information of a pass.
This represents the llvm.assume intrinsic.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:711
This class represents an Operation in the Expression.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition)
IntrinsicInst * AssumeInst
static bool classof(const PredicateBase *PB)
PredicateType Type
Definition: PredicateInfo.h:84
PredicateBase(const PredicateBase &)=delete
PredicateBase & operator=(const PredicateBase &)=delete
std::optional< PredicateConstraint > getConstraint() const
Fetch condition in the form of PredicateConstraint, if possible.
PredicateBase(PredicateType PT, Value *Op, Value *Condition)
static bool classof(const PredicateBase *PB)
virtual ~PredicateBase()=default
static bool classof(const PredicateBase *PB)
PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB, Value *Condition, bool TakenEdge)
An assembly annotator class to print PredicateInfo information in comments.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool runOnFunction(Function &) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Printer pass for PredicateInfo.
PredicateInfoPrinterPass(raw_ostream &OS)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Encapsulates PredicateInfo, including all data associated with memory accesses.
void verifyPredicateInfo() const
void print(raw_ostream &) const
const PredicateBase * getPredicateInfoFor(const Value *V) const
PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB, Value *CaseValue, SwitchInst *SI)
static bool classof(const PredicateBase *PB)
PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From, BasicBlock *To, Value *Cond)
static bool classof(const PredicateBase *PB)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
Multiway switch.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
LLVM Value Representation.
Definition: Value.h:74
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
Definition: ilist.h:328
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This file defines classes to implement an intrusive doubly linked list class (i.e.
This file defines the ilist_node class template, which is a convenient base class for creating classe...
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
PredicateType
Definition: PredicateInfo.h:71
@ PT_Switch
Definition: PredicateInfo.h:71
@ PT_Assume
Definition: PredicateInfo.h:71
@ PT_Branch
Definition: PredicateInfo.h:71
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
Constraint for a predicate of the form "cmp Pred Op, OtherOp", where Op is the value the constraint a...
Definition: PredicateInfo.h:75
CmpInst::Predicate Predicate
Definition: PredicateInfo.h:76
Verifier pass for PredicateInfo.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)