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
61namespace llvm {
62
63class AssumptionCache;
64class DominatorTree;
65class Function;
66class IntrinsicInst;
67class raw_ostream;
68
69enum PredicateType { PT_Branch, PT_Assume, PT_Switch };
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).
73struct PredicateConstraint {
74 CmpInst::Predicate Predicate;
75 Value *OtherOp;
76};
77
78// Base class for all predicate information we provide.
79// All of our predicate information has at least a comparison.
80class PredicateBase : public ilist_node<PredicateBase> {
81public:
82 PredicateType Type;
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.
86 Value *OriginalOp;
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.
90 Value *RenamedOp;
91 // The condition associated with this predicate.
92 Value *Condition;
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.
104 Optional<PredicateConstraint> getConstraint() const;
105
106protected:
107 PredicateBase(PredicateType PT, Value *Op, Value *Condition)
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.
114class PredicateAssume : public PredicateBase {
115public:
116 IntrinsicInst *AssumeInst;
117 PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition)
118 : PredicateBase(PT_Assume, Op, Condition), AssumeInst(AssumeInst) {}
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.
128class PredicateWithEdge : public PredicateBase {
129public:
130 BasicBlock *From;
131 BasicBlock *To;
132 PredicateWithEdge() = delete;
133 static bool classof(const PredicateBase *PB) {
134 return PB->Type == PT_Branch || PB->Type == PT_Switch;
135 }
136
137protected:
138 PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From,
139 BasicBlock *To, Value *Cond)
140 : PredicateBase(PType, Op, Cond), From(From), To(To) {}
141};
142
143// Provides predicate information for branches.
144class PredicateBranch : public PredicateWithEdge {
145public:
146 // If true, SplitBB is the true successor, otherwise it's the false successor.
147 bool TrueEdge;
148 PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB,
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
158class PredicateSwitch : public PredicateWithEdge {
159public:
160 Value *CaseValue;
161 // This is the switch instruction.
162 SwitchInst *Switch;
163 PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB,
164 Value *CaseValue, SwitchInst *SI)
165 : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB,
166 SI->getCondition()),
167 CaseValue(CaseValue), Switch(SI) {}
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.
176class PredicateInfo {
177public:
178 PredicateInfo(Function &, DominatorTree &, AssumptionCache &);
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
190protected:
191 // Used by PredicateInfo annotater, dumpers, and wrapper pass.
192 friend class PredicateInfoAnnotatedWriter;
193 friend class PredicateInfoPrinterLegacyPass;
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};
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.
211class PredicateInfoPrinterLegacyPass : public FunctionPass {
212public:
213 PredicateInfoPrinterLegacyPass();
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.
221class PredicateInfoPrinterPass
222 : public PassInfoMixin<PredicateInfoPrinterPass> {
223 raw_ostream &OS;
224
225public:
226 explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
227 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
228};
229
230/// Verifier pass for \c PredicateInfo.
231struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> {
232 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
233};
234
235} // end namespace llvm
236
237#endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
238