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