1 //===- PredicateInfo.h - Build PredicateInfo ----------------------*-C++-*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 /// 10 /// \file 11 /// \brief This file implements the PredicateInfo analysis, which creates an Extended 12 /// SSA form for operations used in branch comparisons and llvm.assume 13 /// comparisons. 14 /// 15 /// Copies of these operations are inserted into the true/false edge (and after 16 /// assumes), and information attached to the copies. All uses of the original 17 /// operation in blocks dominated by the true/false edge (and assume), are 18 /// replaced with uses of the copies. This enables passes to easily and sparsely 19 /// propagate condition based info into the operations that may be affected. 20 /// 21 /// Example: 22 /// %cmp = icmp eq i32 %x, 50 23 /// br i1 %cmp, label %true, label %false 24 /// true: 25 /// ret i32 %x 26 /// false: 27 /// ret i32 1 28 /// 29 /// will become 30 /// 31 /// %cmp = icmp eq i32, %x, 50 32 /// br i1 %cmp, label %true, label %false 33 /// true: 34 /// %x.0 = call @llvm.ssa_copy.i32(i32 %x) 35 /// ret i32 %x.0 36 /// false: 37 /// ret i32 1 38 /// 39 /// Using getPredicateInfoFor on x.0 will give you the comparison it is 40 /// dominated by (the icmp), and that you are located in the true edge of that 41 /// comparison, which tells you x.0 is 50. 42 /// 43 /// In order to reduce the number of copies inserted, predicateinfo is only 44 /// inserted where it would actually be live. This means if there are no uses of 45 /// an operation dominated by the branch edges, or by an assume, the associated 46 /// predicate info is never inserted. 47 /// 48 /// 49 //===----------------------------------------------------------------------===// 50 51 #ifndef LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H 52 #define LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H 53 54 #include "llvm/ADT/DenseMap.h" 55 #include "llvm/ADT/DenseSet.h" 56 #include "llvm/ADT/SmallPtrSet.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/IR/BasicBlock.h" 63 #include "llvm/IR/Dominators.h" 64 #include "llvm/IR/Instructions.h" 65 #include "llvm/IR/IntrinsicInst.h" 66 #include "llvm/IR/Module.h" 67 #include "llvm/IR/OperandTraits.h" 68 #include "llvm/IR/Type.h" 69 #include "llvm/IR/Use.h" 70 #include "llvm/IR/User.h" 71 #include "llvm/IR/Value.h" 72 #include "llvm/Pass.h" 73 #include "llvm/PassAnalysisSupport.h" 74 #include "llvm/Support/Casting.h" 75 #include "llvm/Support/Compiler.h" 76 #include "llvm/Support/ErrorHandling.h" 77 #include <algorithm> 78 #include <cassert> 79 #include <cstddef> 80 #include <iterator> 81 #include <memory> 82 #include <utility> 83 84 namespace llvm { 85 86 class DominatorTree; 87 class Function; 88 class Instruction; 89 class MemoryAccess; 90 class LLVMContext; 91 class raw_ostream; 92 class OrderedBasicBlock; 93 94 enum PredicateType { PT_Branch, PT_Assume, PT_Switch }; 95 96 // Base class for all predicate information we provide. 97 // All of our predicate information has at least a comparison. 98 class PredicateBase : public ilist_node<PredicateBase> { 99 public: 100 PredicateType Type; 101 // The original operand before we renamed it. 102 // This can be use by passes, when destroying predicateinfo, to know 103 // whether they can just drop the intrinsic, or have to merge metadata. 104 Value *OriginalOp; 105 PredicateBase(const PredicateBase &) = delete; 106 PredicateBase &operator=(const PredicateBase &) = delete; 107 PredicateBase() = delete; 108 virtual ~PredicateBase() = default; 109 110 protected: 111 PredicateBase(PredicateType PT, Value *Op) : Type(PT), OriginalOp(Op) {} 112 }; 113 114 class PredicateWithCondition : public PredicateBase { 115 public: 116 Value *Condition; 117 static inline bool classof(const PredicateBase *PB) { 118 return PB->Type == PT_Assume || PB->Type == PT_Branch || PB->Type == PT_Switch; 119 } 120 121 protected: 122 PredicateWithCondition(PredicateType PT, Value *Op, Value *Condition) 123 : PredicateBase(PT, Op), Condition(Condition) {} 124 }; 125 126 // Provides predicate information for assumes. Since assumes are always true, 127 // we simply provide the assume instruction, so you can tell your relative 128 // position to it. 129 class PredicateAssume : public PredicateWithCondition { 130 public: 131 IntrinsicInst *AssumeInst; 132 PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition) 133 : PredicateWithCondition(PT_Assume, Op, Condition), 134 AssumeInst(AssumeInst) {} 135 PredicateAssume() = delete; 136 static inline bool classof(const PredicateBase *PB) { 137 return PB->Type == PT_Assume; 138 } 139 }; 140 141 // Mixin class for edge predicates. The FROM block is the block where the 142 // predicate originates, and the TO block is the block where the predicate is 143 // valid. 144 class PredicateWithEdge : public PredicateWithCondition { 145 public: 146 BasicBlock *From; 147 BasicBlock *To; 148 PredicateWithEdge() = delete; 149 static inline bool classof(const PredicateBase *PB) { 150 return PB->Type == PT_Branch || PB->Type == PT_Switch; 151 } 152 153 protected: 154 PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From, 155 BasicBlock *To, Value *Cond) 156 : PredicateWithCondition(PType, Op, Cond), From(From), To(To) {} 157 }; 158 159 // Provides predicate information for branches. 160 class PredicateBranch : public PredicateWithEdge { 161 public: 162 // If true, SplitBB is the true successor, otherwise it's the false successor. 163 bool TrueEdge; 164 PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB, 165 Value *Condition, bool TakenEdge) 166 : PredicateWithEdge(PT_Branch, Op, BranchBB, SplitBB, Condition), 167 TrueEdge(TakenEdge) {} 168 PredicateBranch() = delete; 169 static inline bool classof(const PredicateBase *PB) { 170 return PB->Type == PT_Branch; 171 } 172 }; 173 174 class PredicateSwitch : public PredicateWithEdge { 175 public: 176 Value *CaseValue; 177 // This is the switch instruction. 178 SwitchInst *Switch; 179 PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB, 180 Value *CaseValue, SwitchInst *SI) 181 : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB, 182 SI->getCondition()), 183 CaseValue(CaseValue), Switch(SI) {} 184 PredicateSwitch() = delete; 185 static inline bool classof(const PredicateBase *PB) { 186 return PB->Type == PT_Switch; 187 } 188 }; 189 190 // This name is used in a few places, so kick it into their own namespace 191 namespace PredicateInfoClasses { 192 struct ValueDFS; 193 } 194 195 /// \brief Encapsulates PredicateInfo, including all data associated with memory 196 /// accesses. 197 class PredicateInfo { 198 private: 199 // Used to store information about each value we might rename. 200 struct ValueInfo { 201 // Information about each possible copy. During processing, this is each 202 // inserted info. After processing, we move the uninserted ones to the 203 // uninserted vector. 204 SmallVector<PredicateBase *, 4> Infos; 205 SmallVector<PredicateBase *, 4> UninsertedInfos; 206 }; 207 // This owns the all the predicate infos in the function, placed or not. 208 iplist<PredicateBase> AllInfos; 209 210 public: 211 PredicateInfo(Function &, DominatorTree &, AssumptionCache &); 212 ~PredicateInfo(); 213 214 void verifyPredicateInfo() const; 215 216 void dump() const; 217 void print(raw_ostream &) const; 218 219 const PredicateBase *getPredicateInfoFor(const Value *V) const { 220 return PredicateMap.lookup(V); 221 } 222 223 protected: 224 // Used by PredicateInfo annotater, dumpers, and wrapper pass. 225 friend class PredicateInfoAnnotatedWriter; 226 friend class PredicateInfoPrinterLegacyPass; 227 228 private: 229 void buildPredicateInfo(); 230 void processAssume(IntrinsicInst *, BasicBlock *, SmallPtrSetImpl<Value *> &); 231 void processBranch(BranchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &); 232 void processSwitch(SwitchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &); 233 void renameUses(SmallPtrSetImpl<Value *> &); 234 using ValueDFS = PredicateInfoClasses::ValueDFS; 235 typedef SmallVectorImpl<ValueDFS> ValueDFSStack; 236 void convertUsesToDFSOrdered(Value *, SmallVectorImpl<ValueDFS> &); 237 Value *materializeStack(unsigned int &, ValueDFSStack &, Value *); 238 bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const; 239 void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &); 240 ValueInfo &getOrCreateValueInfo(Value *); 241 void addInfoFor(SmallPtrSetImpl<Value *> &OpsToRename, Value *Op, 242 PredicateBase *PB); 243 const ValueInfo &getValueInfo(Value *) const; 244 Function &F; 245 DominatorTree &DT; 246 AssumptionCache &AC; 247 // This maps from copy operands to Predicate Info. Note that it does not own 248 // the Predicate Info, they belong to the ValueInfo structs in the ValueInfos 249 // vector. 250 DenseMap<const Value *, const PredicateBase *> PredicateMap; 251 // This stores info about each operand or comparison result we make copies 252 // of. The real ValueInfos start at index 1, index 0 is unused so that we can 253 // more easily detect invalid indexing. 254 SmallVector<ValueInfo, 32> ValueInfos; 255 // This gives the index into the ValueInfos array for a given Value. Because 256 // 0 is not a valid Value Info index, you can use DenseMap::lookup and tell 257 // whether it returned a valid result. 258 DenseMap<Value *, unsigned int> ValueInfoNums; 259 // OrderedBasicBlocks used during sorting uses 260 DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> OBBMap; 261 // The set of edges along which we can only handle phi uses, due to critical 262 // edges. 263 DenseSet<std::pair<BasicBlock *, BasicBlock *>> EdgeUsesOnly; 264 }; 265 266 // This pass does eager building and then printing of PredicateInfo. It is used 267 // by 268 // the tests to be able to build, dump, and verify PredicateInfo. 269 class PredicateInfoPrinterLegacyPass : public FunctionPass { 270 public: 271 PredicateInfoPrinterLegacyPass(); 272 273 static char ID; 274 bool runOnFunction(Function &) override; 275 void getAnalysisUsage(AnalysisUsage &AU) const override; 276 }; 277 278 /// \brief Printer pass for \c PredicateInfo. 279 class PredicateInfoPrinterPass 280 : public PassInfoMixin<PredicateInfoPrinterPass> { 281 raw_ostream &OS; 282 283 public: 284 explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {} 285 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 286 }; 287 288 /// \brief Verifier pass for \c PredicateInfo. 289 struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> { 290 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 291 }; 292 293 } // end namespace llvm 294 295 #endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H 296