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/Value.h" 60 #include "llvm/IR/ValueHandle.h" 61 #include "llvm/Pass.h" 62 63 namespace llvm { 64 65 class AssumptionCache; 66 class DominatorTree; 67 class Function; 68 class IntrinsicInst; 69 class raw_ostream; 70 71 enum PredicateType { PT_Branch, PT_Assume, PT_Switch }; 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). 75 struct PredicateConstraint { 76 CmpInst::Predicate Predicate; 77 Value *OtherOp; 78 }; 79 80 // Base class for all predicate information we provide. 81 // All of our predicate information has at least a comparison. 82 class PredicateBase : public ilist_node<PredicateBase> { 83 public: 84 PredicateType Type; 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. 88 Value *OriginalOp; 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. 92 Value *RenamedOp; 93 // The condition associated with this predicate. 94 Value *Condition; 95 96 PredicateBase(const PredicateBase &) = delete; 97 PredicateBase &operator=(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 Optional<PredicateConstraint> getConstraint() const; 107 108 protected: 109 PredicateBase(PredicateType PT, Value *Op, Value *Condition) 110 : Type(PT), OriginalOp(Op), Condition(Condition) {} 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. 116 class PredicateAssume : public PredicateBase { 117 public: 118 IntrinsicInst *AssumeInst; 119 PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition) 120 : PredicateBase(PT_Assume, Op, Condition), AssumeInst(AssumeInst) {} 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. 130 class PredicateWithEdge : public PredicateBase { 131 public: 132 BasicBlock *From; 133 BasicBlock *To; 134 PredicateWithEdge() = delete; 135 static bool classof(const PredicateBase *PB) { 136 return PB->Type == PT_Branch || PB->Type == PT_Switch; 137 } 138 139 protected: 140 PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From, 141 BasicBlock *To, Value *Cond) 142 : PredicateBase(PType, Op, Cond), From(From), To(To) {} 143 }; 144 145 // Provides predicate information for branches. 146 class PredicateBranch : public PredicateWithEdge { 147 public: 148 // If true, SplitBB is the true successor, otherwise it's the false successor. 149 bool TrueEdge; 150 PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB, 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 160 class PredicateSwitch : public PredicateWithEdge { 161 public: 162 Value *CaseValue; 163 // This is the switch instruction. 164 SwitchInst *Switch; 165 PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB, 166 Value *CaseValue, SwitchInst *SI) 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. 178 class PredicateInfo { 179 public: 180 PredicateInfo(Function &, DominatorTree &, AssumptionCache &); 181 ~PredicateInfo(); 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 192 protected: 193 // Used by PredicateInfo annotater, dumpers, and wrapper pass. 194 friend class PredicateInfoAnnotatedWriter; 195 friend class PredicateInfoPrinterLegacyPass; 196 friend class PredicateInfoBuilder; 197 198 private: 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. 207 DenseMap<const Value *, const PredicateBase *> PredicateMap; 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. 215 class PredicateInfoPrinterLegacyPass : public FunctionPass { 216 public: 217 PredicateInfoPrinterLegacyPass(); 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. 225 class PredicateInfoPrinterPass 226 : public PassInfoMixin<PredicateInfoPrinterPass> { 227 raw_ostream &OS; 228 229 public: 230 explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {} 231 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 232 }; 233 234 /// Verifier pass for \c PredicateInfo. 235 struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> { 236 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 237 }; 238 239 } // end namespace llvm 240 241 #endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H 242