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/DenseSet.h" 55 #include "llvm/ADT/SmallPtrSet.h" 56 #include "llvm/ADT/SmallSet.h" 57 #include "llvm/ADT/SmallVector.h" 58 #include "llvm/ADT/ilist.h" 59 #include "llvm/ADT/ilist_node.h" 60 #include "llvm/ADT/iterator.h" 61 #include "llvm/Analysis/AssumptionCache.h" 62 #include "llvm/Analysis/OrderedInstructions.h" 63 #include "llvm/IR/BasicBlock.h" 64 #include "llvm/IR/Dominators.h" 65 #include "llvm/IR/Instructions.h" 66 #include "llvm/IR/IntrinsicInst.h" 67 #include "llvm/IR/Module.h" 68 #include "llvm/IR/OperandTraits.h" 69 #include "llvm/IR/Type.h" 70 #include "llvm/IR/Use.h" 71 #include "llvm/IR/User.h" 72 #include "llvm/IR/Value.h" 73 #include "llvm/IR/ValueHandle.h" 74 #include "llvm/Pass.h" 75 #include "llvm/PassAnalysisSupport.h" 76 #include "llvm/Support/Casting.h" 77 #include "llvm/Support/Compiler.h" 78 #include "llvm/Support/ErrorHandling.h" 79 #include <algorithm> 80 #include <cassert> 81 #include <cstddef> 82 #include <iterator> 83 #include <memory> 84 #include <utility> 85 86 namespace llvm { 87 88 class DominatorTree; 89 class Function; 90 class Instruction; 91 class MemoryAccess; 92 class LLVMContext; 93 class raw_ostream; 94 95 enum PredicateType { PT_Branch, PT_Assume, PT_Switch }; 96 97 // Base class for all predicate information we provide. 98 // All of our predicate information has at least a comparison. 99 class PredicateBase : public ilist_node<PredicateBase> { 100 public: 101 PredicateType Type; 102 // The original operand before we renamed it. 103 // This can be use by passes, when destroying predicateinfo, to know 104 // whether they can just drop the intrinsic, or have to merge metadata. 105 Value *OriginalOp; 106 PredicateBase(const PredicateBase &) = delete; 107 PredicateBase &operator=(const PredicateBase &) = delete; 108 PredicateBase() = delete; 109 virtual ~PredicateBase() = default; 110 111 protected: PredicateBase(PredicateType PT,Value * Op)112 PredicateBase(PredicateType PT, Value *Op) : Type(PT), OriginalOp(Op) {} 113 }; 114 115 class PredicateWithCondition : public PredicateBase { 116 public: 117 Value *Condition; classof(const PredicateBase * PB)118 static bool classof(const PredicateBase *PB) { 119 return PB->Type == PT_Assume || PB->Type == PT_Branch || 120 PB->Type == PT_Switch; 121 } 122 123 protected: PredicateWithCondition(PredicateType PT,Value * Op,Value * Condition)124 PredicateWithCondition(PredicateType PT, Value *Op, Value *Condition) 125 : PredicateBase(PT, Op), Condition(Condition) {} 126 }; 127 128 // Provides predicate information for assumes. Since assumes are always true, 129 // we simply provide the assume instruction, so you can tell your relative 130 // position to it. 131 class PredicateAssume : public PredicateWithCondition { 132 public: 133 IntrinsicInst *AssumeInst; PredicateAssume(Value * Op,IntrinsicInst * AssumeInst,Value * Condition)134 PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition) 135 : PredicateWithCondition(PT_Assume, Op, Condition), 136 AssumeInst(AssumeInst) {} 137 PredicateAssume() = delete; classof(const PredicateBase * PB)138 static bool classof(const PredicateBase *PB) { 139 return PB->Type == PT_Assume; 140 } 141 }; 142 143 // Mixin class for edge predicates. The FROM block is the block where the 144 // predicate originates, and the TO block is the block where the predicate is 145 // valid. 146 class PredicateWithEdge : public PredicateWithCondition { 147 public: 148 BasicBlock *From; 149 BasicBlock *To; 150 PredicateWithEdge() = delete; classof(const PredicateBase * PB)151 static bool classof(const PredicateBase *PB) { 152 return PB->Type == PT_Branch || PB->Type == PT_Switch; 153 } 154 155 protected: PredicateWithEdge(PredicateType PType,Value * Op,BasicBlock * From,BasicBlock * To,Value * Cond)156 PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From, 157 BasicBlock *To, Value *Cond) 158 : PredicateWithCondition(PType, Op, Cond), From(From), To(To) {} 159 }; 160 161 // Provides predicate information for branches. 162 class PredicateBranch : public PredicateWithEdge { 163 public: 164 // If true, SplitBB is the true successor, otherwise it's the false successor. 165 bool TrueEdge; PredicateBranch(Value * Op,BasicBlock * BranchBB,BasicBlock * SplitBB,Value * Condition,bool TakenEdge)166 PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB, 167 Value *Condition, bool TakenEdge) 168 : PredicateWithEdge(PT_Branch, Op, BranchBB, SplitBB, Condition), 169 TrueEdge(TakenEdge) {} 170 PredicateBranch() = delete; classof(const PredicateBase * PB)171 static bool classof(const PredicateBase *PB) { 172 return PB->Type == PT_Branch; 173 } 174 }; 175 176 class PredicateSwitch : public PredicateWithEdge { 177 public: 178 Value *CaseValue; 179 // This is the switch instruction. 180 SwitchInst *Switch; PredicateSwitch(Value * Op,BasicBlock * SwitchBB,BasicBlock * TargetBB,Value * CaseValue,SwitchInst * SI)181 PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB, 182 Value *CaseValue, SwitchInst *SI) 183 : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB, 184 SI->getCondition()), 185 CaseValue(CaseValue), Switch(SI) {} 186 PredicateSwitch() = delete; classof(const PredicateBase * PB)187 static bool classof(const PredicateBase *PB) { 188 return PB->Type == PT_Switch; 189 } 190 }; 191 192 // This name is used in a few places, so kick it into their own namespace 193 namespace PredicateInfoClasses { 194 struct ValueDFS; 195 } 196 197 /// Encapsulates PredicateInfo, including all data associated with memory 198 /// accesses. 199 class PredicateInfo { 200 private: 201 // Used to store information about each value we might rename. 202 struct ValueInfo { 203 // Information about each possible copy. During processing, this is each 204 // inserted info. After processing, we move the uninserted ones to the 205 // uninserted vector. 206 SmallVector<PredicateBase *, 4> Infos; 207 SmallVector<PredicateBase *, 4> UninsertedInfos; 208 }; 209 // This owns the all the predicate infos in the function, placed or not. 210 iplist<PredicateBase> AllInfos; 211 212 public: 213 PredicateInfo(Function &, DominatorTree &, AssumptionCache &); 214 ~PredicateInfo(); 215 216 void verifyPredicateInfo() const; 217 218 void dump() const; 219 void print(raw_ostream &) const; 220 getPredicateInfoFor(const Value * V)221 const PredicateBase *getPredicateInfoFor(const Value *V) const { 222 return PredicateMap.lookup(V); 223 } 224 225 protected: 226 // Used by PredicateInfo annotater, dumpers, and wrapper pass. 227 friend class PredicateInfoAnnotatedWriter; 228 friend class PredicateInfoPrinterLegacyPass; 229 230 private: 231 void buildPredicateInfo(); 232 void processAssume(IntrinsicInst *, BasicBlock *, SmallVectorImpl<Value *> &); 233 void processBranch(BranchInst *, BasicBlock *, SmallVectorImpl<Value *> &); 234 void processSwitch(SwitchInst *, BasicBlock *, SmallVectorImpl<Value *> &); 235 void renameUses(SmallVectorImpl<Value *> &); 236 using ValueDFS = PredicateInfoClasses::ValueDFS; 237 typedef SmallVectorImpl<ValueDFS> ValueDFSStack; 238 void convertUsesToDFSOrdered(Value *, SmallVectorImpl<ValueDFS> &); 239 Value *materializeStack(unsigned int &, ValueDFSStack &, Value *); 240 bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const; 241 void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &); 242 ValueInfo &getOrCreateValueInfo(Value *); 243 void addInfoFor(SmallVectorImpl<Value *> &OpsToRename, Value *Op, 244 PredicateBase *PB); 245 const ValueInfo &getValueInfo(Value *) const; 246 Function &F; 247 DominatorTree &DT; 248 AssumptionCache &AC; 249 OrderedInstructions OI; 250 // This maps from copy operands to Predicate Info. Note that it does not own 251 // the Predicate Info, they belong to the ValueInfo structs in the ValueInfos 252 // vector. 253 DenseMap<const Value *, const PredicateBase *> PredicateMap; 254 // This stores info about each operand or comparison result we make copies 255 // of. The real ValueInfos start at index 1, index 0 is unused so that we can 256 // more easily detect invalid indexing. 257 SmallVector<ValueInfo, 32> ValueInfos; 258 // This gives the index into the ValueInfos array for a given Value. Because 259 // 0 is not a valid Value Info index, you can use DenseMap::lookup and tell 260 // whether it returned a valid result. 261 DenseMap<Value *, unsigned int> ValueInfoNums; 262 // The set of edges along which we can only handle phi uses, due to critical 263 // edges. 264 DenseSet<std::pair<BasicBlock *, BasicBlock *>> EdgeUsesOnly; 265 // The set of ssa_copy declarations we created with our custom mangling. 266 SmallSet<AssertingVH<Function>, 20> CreatedDeclarations; 267 }; 268 269 // This pass does eager building and then printing of PredicateInfo. It is used 270 // by 271 // the tests to be able to build, dump, and verify PredicateInfo. 272 class PredicateInfoPrinterLegacyPass : public FunctionPass { 273 public: 274 PredicateInfoPrinterLegacyPass(); 275 276 static char ID; 277 bool runOnFunction(Function &) override; 278 void getAnalysisUsage(AnalysisUsage &AU) const override; 279 }; 280 281 /// Printer pass for \c PredicateInfo. 282 class PredicateInfoPrinterPass 283 : public PassInfoMixin<PredicateInfoPrinterPass> { 284 raw_ostream &OS; 285 286 public: PredicateInfoPrinterPass(raw_ostream & OS)287 explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {} 288 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 289 }; 290 291 /// Verifier pass for \c PredicateInfo. 292 struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> { 293 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 294 }; 295 296 } // end namespace llvm 297 298 #endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H 299