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