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