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
bundleHasArgument(const CallBase::BundleOpInfo & BOI,unsigned Idx)32 static bool bundleHasArgument(const CallBase::BundleOpInfo &BOI, unsigned Idx) {
33 return BOI.End - BOI.Begin > Idx;
34 }
35
getValueFromBundleOpInfo(CallInst & Assume,const CallBase::BundleOpInfo & BOI,unsigned Idx)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
hasAttributeInAssume(CallInst & AssumeCI,Value * IsOn,StringRef AttrName,uint64_t * ArgVal)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
fillMapFromAssume(CallInst & AssumeCI,RetainedKnowledgeMap & Result)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
getKnowledgeFromBundle(CallInst & Assume,const CallBase::BundleOpInfo & BOI)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
getKnowledgeFromOperandInAssume(CallInst & AssumeCI,unsigned Idx)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
isAssumeWithEmptyBundle(CallInst & CI)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
getBundleFromUse(const Use * U)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
getKnowledgeFromUse(const Use * U,ArrayRef<Attribute::AttrKind> AttrKinds)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
getKnowledgeForValue(const Value * V,ArrayRef<Attribute::AttrKind> AttrKinds,AssumptionCache * AC,function_ref<bool (RetainedKnowledge,Instruction *,const CallBase::BundleOpInfo *)> Filter)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
getKnowledgeValidInContext(const Value * V,ArrayRef<Attribute::AttrKind> AttrKinds,const Instruction * CtxI,const DominatorTree * DT,AssumptionCache * AC)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