1 //===- AssumeBundleQueries.h - utilities to query assume bundles *- 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 // This file contain tools to query into assume bundles. assume bundles can be 10 // built using utilities from Transform/Utils/AssumeBundleBuilder.h 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_TRANSFORMS_UTILS_ASSUMEBUNDLEQUERIES_H 15 #define LLVM_TRANSFORMS_UTILS_ASSUMEBUNDLEQUERIES_H 16 17 #include "llvm/IR/Attributes.h" 18 #include "llvm/IR/Instructions.h" 19 #include "llvm/ADT/DenseMap.h" 20 21 namespace llvm { 22 class IntrinsicInst; 23 class AssumptionCache; 24 class DominatorTree; 25 26 /// Index of elements in the operand bundle. 27 /// If the element exist it is guaranteed to be what is specified in this enum 28 /// but it may not exist. 29 enum AssumeBundleArg { 30 ABA_WasOn = 0, 31 ABA_Argument = 1, 32 }; 33 34 /// Query the operand bundle of an llvm.assume to find a single attribute of 35 /// the specified kind applied on a specified Value. 36 /// 37 /// This has a non-constant complexity. It should only be used when a single 38 /// attribute is going to be queried. 39 /// 40 /// Return true iff the queried attribute was found. 41 /// If ArgVal is set. the argument will be stored to ArgVal. 42 bool hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn, StringRef AttrName, 43 uint64_t *ArgVal = nullptr); 44 inline bool hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn, 45 Attribute::AttrKind Kind, 46 uint64_t *ArgVal = nullptr) { 47 return hasAttributeInAssume(AssumeCI, IsOn, 48 Attribute::getNameFromAttrKind(Kind), ArgVal); 49 } 50 51 template<> struct DenseMapInfo<Attribute::AttrKind> { 52 static Attribute::AttrKind getEmptyKey() { 53 return Attribute::EmptyKey; 54 } 55 static Attribute::AttrKind getTombstoneKey() { 56 return Attribute::TombstoneKey; 57 } 58 static unsigned getHashValue(Attribute::AttrKind AK) { 59 return hash_combine(AK); 60 } 61 static bool isEqual(Attribute::AttrKind LHS, Attribute::AttrKind RHS) { 62 return LHS == RHS; 63 } 64 }; 65 66 /// The map Key contains the Value on for which the attribute is valid and 67 /// the Attribute that is valid for that value. 68 /// If the Attribute is not on any value, the Value is nullptr. 69 using RetainedKnowledgeKey = std::pair<Value *, Attribute::AttrKind>; 70 71 struct MinMax { 72 unsigned Min; 73 unsigned Max; 74 }; 75 76 /// A mapping from intrinsics (=`llvm.assume` calls) to a value range 77 /// (=knowledge) that is encoded in them. How the value range is interpreted 78 /// depends on the RetainedKnowledgeKey that was used to get this out of the 79 /// RetainedKnowledgeMap. 80 using Assume2KnowledgeMap = DenseMap<IntrinsicInst *, MinMax>; 81 82 using RetainedKnowledgeMap = 83 DenseMap<RetainedKnowledgeKey, Assume2KnowledgeMap>; 84 85 /// Insert into the map all the informations contained in the operand bundles of 86 /// the llvm.assume. This should be used instead of hasAttributeInAssume when 87 /// many queries are going to be made on the same llvm.assume. 88 /// String attributes are not inserted in the map. 89 /// If the IR changes the map will be outdated. 90 void fillMapFromAssume(CallInst &AssumeCI, RetainedKnowledgeMap &Result); 91 92 /// Represent one information held inside an operand bundle of an llvm.assume. 93 /// AttrKind is the property that holds. 94 /// WasOn if not null is that Value for which AttrKind holds. 95 /// ArgValue is optionally an argument of the attribute. 96 /// For example if we know that %P has an alignment of at least four: 97 /// - AttrKind will be Attribute::Alignment. 98 /// - WasOn will be %P. 99 /// - ArgValue will be 4. 100 struct RetainedKnowledge { 101 Attribute::AttrKind AttrKind = Attribute::None; 102 unsigned ArgValue = 0; 103 Value *WasOn = nullptr; 104 bool operator==(RetainedKnowledge Other) const { 105 return AttrKind == Other.AttrKind && WasOn == Other.WasOn && 106 ArgValue == Other.ArgValue; 107 } 108 bool operator!=(RetainedKnowledge Other) const { return !(*this == Other); } 109 operator bool() const { return AttrKind != Attribute::None; } 110 static RetainedKnowledge none() { return RetainedKnowledge{}; } 111 }; 112 113 /// Retreive the information help by Assume on the operand at index Idx. 114 /// Assume should be an llvm.assume and Idx should be in the operand bundle. 115 RetainedKnowledge getKnowledgeFromOperandInAssume(CallInst &Assume, 116 unsigned Idx); 117 118 /// Retreive the information help by the Use U of an llvm.assume. the use should 119 /// be in the operand bundle. 120 inline RetainedKnowledge getKnowledgeFromUseInAssume(const Use *U) { 121 return getKnowledgeFromOperandInAssume(*cast<CallInst>(U->getUser()), 122 U->getOperandNo()); 123 } 124 125 /// Tag in operand bundle indicating that this bundle should be ignored. 126 constexpr StringRef IgnoreBundleTag = "ignore"; 127 128 /// Return true iff the operand bundles of the provided llvm.assume doesn't 129 /// contain any valuable information. This is true when: 130 /// - The operand bundle is empty 131 /// - The operand bundle only contains information about dropped values or 132 /// constant folded values. 133 /// 134 /// the argument to the call of llvm.assume may still be useful even if the 135 /// function returned true. 136 bool isAssumeWithEmptyBundle(CallInst &Assume); 137 138 /// Return a valid Knowledge associated to the Use U if its Attribute kind is 139 /// in AttrKinds. 140 RetainedKnowledge getKnowledgeFromUse(const Use *U, 141 ArrayRef<Attribute::AttrKind> AttrKinds); 142 143 /// Return a valid Knowledge associated to the Value V if its Attribute kind is 144 /// in AttrKinds and it matches the Filter. 145 RetainedKnowledge getKnowledgeForValue( 146 const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds, 147 AssumptionCache *AC = nullptr, 148 function_ref<bool(RetainedKnowledge, Instruction *, 149 const CallBase::BundleOpInfo *)> 150 Filter = [](auto...) { return true; }); 151 152 /// Return a valid Knowledge associated to the Value V if its Attribute kind is 153 /// in AttrKinds and the knowledge is suitable to be used in the context of 154 /// CtxI. 155 RetainedKnowledge getKnowledgeValidInContext( 156 const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds, 157 const Instruction *CtxI, const DominatorTree *DT = nullptr, 158 AssumptionCache *AC = nullptr); 159 160 /// This extracts the Knowledge from an element of an operand bundle. 161 /// This is mostly for use in the assume builder. 162 RetainedKnowledge getKnowledgeFromBundle(CallInst &Assume, 163 const CallBase::BundleOpInfo &BOI); 164 165 } // namespace llvm 166 167 #endif 168