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/ValueHandle.h"
60
61namespace llvm {
62
63class AssumptionCache;
64class DominatorTree;
65class Function;
66class Value;
67class IntrinsicInst;
68class raw_ostream;
69
70enum PredicateType { PT_Branch, PT_Assume, PT_Switch };
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).
74struct PredicateConstraint {
75 CmpInst::Predicate Predicate;
76 Value *OtherOp;
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:
83 PredicateType Type;
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.
87 Value *OriginalOp;
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.
91 Value *RenamedOp;
92 // The condition associated with this predicate.
93 Value *Condition;
94
95 PredicateBase(const PredicateBase &) = delete;
96 PredicateBase &operator=(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:
108 PredicateBase(PredicateType PT, Value *Op, Value *Condition)
109 : Type(PT), OriginalOp(Op), Condition(Condition) {}
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.
115class PredicateAssume : public PredicateBase {
116public:
117 IntrinsicInst *AssumeInst;
118 PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition)
119 : PredicateBase(PT_Assume, Op, Condition), AssumeInst(AssumeInst) {}
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.
129class PredicateWithEdge : public PredicateBase {
130public:
131 BasicBlock *From;
132 BasicBlock *To;
133 PredicateWithEdge() = delete;
134 static bool classof(const PredicateBase *PB) {
135 return PB->Type == PT_Branch || PB->Type == PT_Switch;
136 }
137
138protected:
139 PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From,
140 BasicBlock *To, Value *Cond)
141 : PredicateBase(PType, Op, Cond), From(From), To(To) {}
142};
143
144// Provides predicate information for branches.
145class PredicateBranch : public PredicateWithEdge {
146public:
147 // If true, SplitBB is the true successor, otherwise it's the false successor.
148 bool TrueEdge;
149 PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB,
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
159class PredicateSwitch : public PredicateWithEdge {
160public:
161 Value *CaseValue;
162 // This is the switch instruction.
163 SwitchInst *Switch;
164 PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB,
165 Value *CaseValue, SwitchInst *SI)
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.
177class PredicateInfo {
178public:
179 PredicateInfo(Function &, DominatorTree &, AssumptionCache &);
180 ~PredicateInfo();
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(Val: V);
189 }
190
191protected:
192 // Used by PredicateInfo annotater, dumpers, and wrapper pass.
193 friend class PredicateInfoAnnotatedWriter;
194 friend class PredicateInfoBuilder;
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.
205 DenseMap<const Value *, const PredicateBase *> PredicateMap;
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.
211class PredicateInfoPrinterPass
212 : public PassInfoMixin<PredicateInfoPrinterPass> {
213 raw_ostream &OS;
214
215public:
216 explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
217 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
218 static bool isRequired() { return true; }
219};
220
221/// Verifier pass for \c PredicateInfo.
222struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> {
223 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
224 static bool isRequired() { return true; }
225};
226
227} // end namespace llvm
228
229#endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
230

source code of llvm/include/llvm/Transforms/Utils/PredicateInfo.h