1 //===- AssumeBundleQueries.cpp - tool 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 #define DEBUG_TYPE "assume-queries" 10 11 #include "llvm/Analysis/AssumeBundleQueries.h" 12 #include "llvm/ADT/Statistic.h" 13 #include "llvm/Analysis/AssumptionCache.h" 14 #include "llvm/Analysis/ValueTracking.h" 15 #include "llvm/IR/Function.h" 16 #include "llvm/IR/InstIterator.h" 17 #include "llvm/IR/IntrinsicInst.h" 18 #include "llvm/IR/PatternMatch.h" 19 #include "llvm/Support/DebugCounter.h" 20 21 using namespace llvm; 22 using namespace llvm::PatternMatch; 23 24 STATISTIC(NumAssumeQueries, "Number of Queries into an assume assume bundles"); 25 STATISTIC( 26 NumUsefullAssumeQueries, 27 "Number of Queries into an assume assume bundles that were satisfied"); 28 29 DEBUG_COUNTER(AssumeQueryCounter, "assume-queries-counter", 30 "Controls which assumes gets created"); 31 32 static bool bundleHasArgument(const CallBase::BundleOpInfo &BOI, unsigned Idx) { 33 return BOI.End - BOI.Begin > Idx; 34 } 35 36 static Value *getValueFromBundleOpInfo(CallInst &Assume, 37 const CallBase::BundleOpInfo &BOI, 38 unsigned Idx) { 39 assert(bundleHasArgument(BOI, Idx) && "index out of range"); 40 return (Assume.op_begin() + BOI.Begin + Idx)->get(); 41 } 42 43 bool llvm::hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn, 44 StringRef AttrName, uint64_t *ArgVal) { 45 assert(isa<IntrinsicInst>(AssumeCI) && 46 "this function is intended to be used on llvm.assume"); 47 IntrinsicInst &Assume = cast<IntrinsicInst>(AssumeCI); 48 assert(Assume.getIntrinsicID() == Intrinsic::assume && 49 "this function is intended to be used on llvm.assume"); 50 assert(Attribute::isExistingAttribute(AttrName) && 51 "this attribute doesn't exist"); 52 assert((ArgVal == nullptr || Attribute::doesAttrKindHaveArgument( 53 Attribute::getAttrKindFromName(AttrName))) && 54 "requested value for an attribute that has no argument"); 55 if (Assume.bundle_op_infos().empty()) 56 return false; 57 58 for (auto &BOI : Assume.bundle_op_infos()) { 59 if (BOI.Tag->getKey() != AttrName) 60 continue; 61 if (IsOn && (BOI.End - BOI.Begin <= ABA_WasOn || 62 IsOn != getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn))) 63 continue; 64 if (ArgVal) { 65 assert(BOI.End - BOI.Begin > ABA_Argument); 66 *ArgVal = 67 cast<ConstantInt>(getValueFromBundleOpInfo(Assume, BOI, ABA_Argument)) 68 ->getZExtValue(); 69 } 70 return true; 71 } 72 return false; 73 } 74 75 void llvm::fillMapFromAssume(CallInst &AssumeCI, RetainedKnowledgeMap &Result) { 76 IntrinsicInst &Assume = cast<IntrinsicInst>(AssumeCI); 77 assert(Assume.getIntrinsicID() == Intrinsic::assume && 78 "this function is intended to be used on llvm.assume"); 79 for (auto &Bundles : Assume.bundle_op_infos()) { 80 std::pair<Value *, Attribute::AttrKind> Key{ 81 nullptr, Attribute::getAttrKindFromName(Bundles.Tag->getKey())}; 82 if (bundleHasArgument(Bundles, ABA_WasOn)) 83 Key.first = getValueFromBundleOpInfo(Assume, Bundles, ABA_WasOn); 84 85 if (Key.first == nullptr && Key.second == Attribute::None) 86 continue; 87 if (!bundleHasArgument(Bundles, ABA_Argument)) { 88 Result[Key][&Assume] = {0, 0}; 89 continue; 90 } 91 unsigned Val = cast<ConstantInt>( 92 getValueFromBundleOpInfo(Assume, Bundles, ABA_Argument)) 93 ->getZExtValue(); 94 auto Lookup = Result.find(Key); 95 if (Lookup == Result.end() || !Lookup->second.count(&Assume)) { 96 Result[Key][&Assume] = {Val, Val}; 97 continue; 98 } 99 Lookup->second[&Assume].Min = std::min(Val, Lookup->second[&Assume].Min); 100 Lookup->second[&Assume].Max = std::max(Val, Lookup->second[&Assume].Max); 101 } 102 } 103 104 RetainedKnowledge 105 llvm::getKnowledgeFromBundle(CallInst &Assume, 106 const CallBase::BundleOpInfo &BOI) { 107 RetainedKnowledge Result; 108 Result.AttrKind = Attribute::getAttrKindFromName(BOI.Tag->getKey()); 109 if (bundleHasArgument(BOI, ABA_WasOn)) 110 Result.WasOn = getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn); 111 auto GetArgOr1 = [&](unsigned Idx) -> unsigned { 112 if (auto *ConstInt = dyn_cast<ConstantInt>( 113 getValueFromBundleOpInfo(Assume, BOI, ABA_Argument + Idx))) 114 return ConstInt->getZExtValue(); 115 return 1; 116 }; 117 if (BOI.End - BOI.Begin > ABA_Argument) 118 Result.ArgValue = GetArgOr1(0); 119 if (Result.AttrKind == Attribute::Alignment) 120 if (BOI.End - BOI.Begin > ABA_Argument + 1) 121 Result.ArgValue = MinAlign(Result.ArgValue, GetArgOr1(1)); 122 return Result; 123 } 124 125 RetainedKnowledge llvm::getKnowledgeFromOperandInAssume(CallInst &AssumeCI, 126 unsigned Idx) { 127 IntrinsicInst &Assume = cast<IntrinsicInst>(AssumeCI); 128 assert(Assume.getIntrinsicID() == Intrinsic::assume && 129 "this function is intended to be used on llvm.assume"); 130 CallBase::BundleOpInfo BOI = Assume.getBundleOpInfoForOperand(Idx); 131 return getKnowledgeFromBundle(AssumeCI, BOI); 132 } 133 134 bool llvm::isAssumeWithEmptyBundle(CallInst &CI) { 135 IntrinsicInst &Assume = cast<IntrinsicInst>(CI); 136 assert(Assume.getIntrinsicID() == Intrinsic::assume && 137 "this function is intended to be used on llvm.assume"); 138 return none_of(Assume.bundle_op_infos(), 139 [](const CallBase::BundleOpInfo &BOI) { 140 return BOI.Tag->getKey() != IgnoreBundleTag; 141 }); 142 } 143 144 static CallInst::BundleOpInfo *getBundleFromUse(const Use *U) { 145 auto *Intr = dyn_cast<IntrinsicInst>(U->getUser()); 146 if (!match(U->getUser(), 147 m_Intrinsic<Intrinsic::assume>(m_Unless(m_Specific(U->get()))))) 148 return nullptr; 149 return &Intr->getBundleOpInfoForOperand(U->getOperandNo()); 150 } 151 152 RetainedKnowledge 153 llvm::getKnowledgeFromUse(const Use *U, 154 ArrayRef<Attribute::AttrKind> AttrKinds) { 155 CallInst::BundleOpInfo* Bundle = getBundleFromUse(U); 156 if (!Bundle) 157 return RetainedKnowledge::none(); 158 RetainedKnowledge RK = 159 getKnowledgeFromBundle(*cast<CallInst>(U->getUser()), *Bundle); 160 for (auto Attr : AttrKinds) 161 if (Attr == RK.AttrKind) 162 return RK; 163 return RetainedKnowledge::none(); 164 } 165 166 RetainedKnowledge 167 llvm::getKnowledgeForValue(const Value *V, 168 ArrayRef<Attribute::AttrKind> AttrKinds, 169 AssumptionCache *AC, 170 function_ref<bool(RetainedKnowledge, Instruction *, 171 const CallBase::BundleOpInfo *)> 172 Filter) { 173 NumAssumeQueries++; 174 if (!DebugCounter::shouldExecute(AssumeQueryCounter)) 175 return RetainedKnowledge::none(); 176 if (AC) { 177 for (AssumptionCache::ResultElem &Elem : AC->assumptionsFor(V)) { 178 IntrinsicInst *II = cast_or_null<IntrinsicInst>(Elem.Assume); 179 if (!II || Elem.Index == AssumptionCache::ExprResultIdx) 180 continue; 181 if (RetainedKnowledge RK = getKnowledgeFromBundle( 182 *II, II->bundle_op_info_begin()[Elem.Index])) { 183 if (V != RK.WasOn) 184 continue; 185 if (is_contained(AttrKinds, RK.AttrKind) && 186 Filter(RK, II, &II->bundle_op_info_begin()[Elem.Index])) { 187 NumUsefullAssumeQueries++; 188 return RK; 189 } 190 } 191 } 192 return RetainedKnowledge::none(); 193 } 194 for (const auto &U : V->uses()) { 195 CallInst::BundleOpInfo* Bundle = getBundleFromUse(&U); 196 if (!Bundle) 197 continue; 198 if (RetainedKnowledge RK = 199 getKnowledgeFromBundle(*cast<CallInst>(U.getUser()), *Bundle)) 200 if (is_contained(AttrKinds, RK.AttrKind) && 201 Filter(RK, cast<Instruction>(U.getUser()), Bundle)) { 202 NumUsefullAssumeQueries++; 203 return RK; 204 } 205 } 206 return RetainedKnowledge::none(); 207 } 208 209 RetainedKnowledge llvm::getKnowledgeValidInContext( 210 const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds, 211 const Instruction *CtxI, const DominatorTree *DT, AssumptionCache *AC) { 212 return getKnowledgeForValue(V, AttrKinds, AC, 213 [&](auto, Instruction *I, auto) { 214 return isValidAssumeForContext(I, CtxI, DT); 215 }); 216 } 217