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 86namespace llvm { 87 88class DominatorTree; 89class Function; 90class Instruction; 91class MemoryAccess; 92class LLVMContext; 93class raw_ostream; 94 95enum 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. 99class PredicateBase : public ilist_node<PredicateBase> { 100public: 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 111protected: 112 PredicateBase(PredicateType PT, Value *Op) : Type(PT), OriginalOp(Op) {} 113}; 114 115class PredicateWithCondition : public PredicateBase { 116public: 117 Value *Condition; 118 static bool classof(const PredicateBase *PB) { 119 return PB->Type == PT_Assume || PB->Type == PT_Branch || 120 PB->Type == PT_Switch; 121 } 122 123protected: 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. 131class PredicateAssume : public PredicateWithCondition { 132public: 133 IntrinsicInst *AssumeInst; 134 PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition) 135 : PredicateWithCondition(PT_Assume, Op, Condition), 136 AssumeInst(AssumeInst) {} 137 PredicateAssume() = delete; 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. 146class PredicateWithEdge : public PredicateWithCondition { 147public: 148 BasicBlock *From; 149 BasicBlock *To; 150 PredicateWithEdge() = delete; 151 static bool classof(const PredicateBase *PB) { 152 return PB->Type == PT_Branch || PB->Type == PT_Switch; 153 } 154 155protected: 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. 162class PredicateBranch : public PredicateWithEdge { 163public: 164 // If true, SplitBB is the true successor, otherwise it's the false successor. 165 bool TrueEdge; 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; 171 static bool classof(const PredicateBase *PB) { 172 return PB->Type == PT_Branch; 173 } 174}; 175 176class PredicateSwitch : public PredicateWithEdge { 177public: 178 Value *CaseValue; 179 // This is the switch instruction. 180 SwitchInst *Switch; 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; 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 193namespace PredicateInfoClasses { 194struct ValueDFS; 195} 196 197/// Encapsulates PredicateInfo, including all data associated with memory 198/// accesses. 199class PredicateInfo { 200private: 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 212public: 213 PredicateInfo(Function &, DominatorTree &, AssumptionCache &); 214 ~PredicateInfo(); 215 216 void verifyPredicateInfo() const; 217 218 void dump() const; 219 void print(raw_ostream &) const; 220 221 const PredicateBase *getPredicateInfoFor(const Value *V) const { 222 return PredicateMap.lookup(V); 223 } 224 225protected: 226 // Used by PredicateInfo annotater, dumpers, and wrapper pass. 227 friend class PredicateInfoAnnotatedWriter; 228 friend class PredicateInfoPrinterLegacyPass; 229 230private: 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. 272class PredicateInfoPrinterLegacyPass : public FunctionPass { 273public: 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. 282class PredicateInfoPrinterPass 283 : public PassInfoMixin<PredicateInfoPrinterPass> { 284 raw_ostream &OS; 285 286public: 287 explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {} 288 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 289}; 290 291/// Verifier pass for \c PredicateInfo. 292struct 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