LLVM 20.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
61namespace llvm {
62
63class AssumptionCache;
64class DominatorTree;
65class Function;
66class Value;
67class IntrinsicInst;
68class raw_ostream;
69
71
72/// Constraint for a predicate of the form "cmp Pred Op, OtherOp", where Op
73/// is the value the constraint applies to (the ssa.copy result).
77};
78
79// Base class for all predicate information we provide.
80// All of our predicate information has at least a comparison.
81class PredicateBase : public ilist_node<PredicateBase> {
82public:
84 // The original operand before we renamed it.
85 // This can be use by passes, when destroying predicateinfo, to know
86 // whether they can just drop the intrinsic, or have to merge metadata.
88 // The renamed operand in the condition used for this predicate. For nested
89 // predicates, this is different to OriginalOp which refers to the initial
90 // operand.
92 // The condition associated with this predicate.
94
95 PredicateBase(const PredicateBase &) = delete;
97 PredicateBase() = delete;
98 virtual ~PredicateBase() = default;
99 static bool classof(const PredicateBase *PB) {
100 return PB->Type == PT_Assume || PB->Type == PT_Branch ||
101 PB->Type == PT_Switch;
102 }
103
104 /// Fetch condition in the form of PredicateConstraint, if possible.
105 std::optional<PredicateConstraint> getConstraint() const;
106
107protected:
110};
111
112// Provides predicate information for assumes. Since assumes are always true,
113// we simply provide the assume instruction, so you can tell your relative
114// position to it.
116public:
120 PredicateAssume() = delete;
121 static bool classof(const PredicateBase *PB) {
122 return PB->Type == PT_Assume;
123 }
124};
125
126// Mixin class for edge predicates. The FROM block is the block where the
127// predicate originates, and the TO block is the block where the predicate is
128// valid.
130public:
134 static bool classof(const PredicateBase *PB) {
135 return PB->Type == PT_Branch || PB->Type == PT_Switch;
136 }
137
138protected:
141 : PredicateBase(PType, Op, Cond), From(From), To(To) {}
142};
143
144// Provides predicate information for branches.
146public:
147 // If true, SplitBB is the true successor, otherwise it's the false successor.
150 Value *Condition, bool TakenEdge)
151 : PredicateWithEdge(PT_Branch, Op, BranchBB, SplitBB, Condition),
152 TrueEdge(TakenEdge) {}
153 PredicateBranch() = delete;
154 static bool classof(const PredicateBase *PB) {
155 return PB->Type == PT_Branch;
156 }
157};
158
160public:
162 // This is the switch instruction.
166 : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB,
167 SI->getCondition()),
168 CaseValue(CaseValue), Switch(SI) {}
169 PredicateSwitch() = delete;
170 static bool classof(const PredicateBase *PB) {
171 return PB->Type == PT_Switch;
172 }
173};
174
175/// Encapsulates PredicateInfo, including all data associated with memory
176/// accesses.
178public:
181
182 void verifyPredicateInfo() const;
183
184 void dump() const;
185 void print(raw_ostream &) const;
186
187 const PredicateBase *getPredicateInfoFor(const Value *V) const {
188 return PredicateMap.lookup(V);
189 }
190
191protected:
192 // Used by PredicateInfo annotater, dumpers, and wrapper pass.
195
196private:
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 // The set of ssa_copy declarations we created with our custom mangling.
207 SmallSet<AssertingVH<Function>, 20> CreatedDeclarations;
208};
209
210/// Printer pass for \c PredicateInfo.
212 : public PassInfoMixin<PredicateInfoPrinterPass> {
213 raw_ostream &OS;
214
215public:
218 static bool isRequired() { return true; }
219};
220
221/// Verifier pass for \c PredicateInfo.
222struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> {
224 static bool isRequired() { return true; }
225};
226
227} // end namespace llvm
228
229#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:253
This represents the llvm.assume intrinsic.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:757
This class represents an Operation in the Expression.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:48
PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition)
IntrinsicInst * AssumeInst
static bool classof(const PredicateBase *PB)
PredicateType Type
Definition: PredicateInfo.h:83
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)
Definition: PredicateInfo.h:99
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.
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: Analysis.h:111
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:70
@ PT_Switch
Definition: PredicateInfo.h:70
@ PT_Assume
Definition: PredicateInfo.h:70
@ PT_Branch
Definition: PredicateInfo.h:70
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:69
Constraint for a predicate of the form "cmp Pred Op, OtherOp", where Op is the value the constraint a...
Definition: PredicateInfo.h:74
CmpInst::Predicate Predicate
Definition: PredicateInfo.h:75
Verifier pass for PredicateInfo.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)