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
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(AssumeInst & Assume,const CallBase::BundleOpInfo & BOI,unsigned Idx)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
hasAttributeInAssume(AssumeInst & Assume,Value * IsOn,StringRef AttrName,uint64_t * ArgVal)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
fillMapFromAssume(AssumeInst & Assume,RetainedKnowledgeMap & Result)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 [It, Inserted] = Result[Key].try_emplace(&Assume);
89 if (Inserted) {
90 It->second = {Val, Val};
91 continue;
92 }
93 auto &MinMax = It->second;
94 MinMax.Min = std::min(Val, MinMax.Min);
95 MinMax.Max = std::max(Val, MinMax.Max);
96 }
97 }
98
99 RetainedKnowledge
getKnowledgeFromBundle(AssumeInst & Assume,const CallBase::BundleOpInfo & BOI)100 llvm::getKnowledgeFromBundle(AssumeInst &Assume,
101 const CallBase::BundleOpInfo &BOI) {
102 RetainedKnowledge Result;
103 if (!DebugCounter::shouldExecute(AssumeQueryCounter))
104 return Result;
105
106 Result.AttrKind = Attribute::getAttrKindFromName(BOI.Tag->getKey());
107 if (bundleHasArgument(BOI, ABA_WasOn))
108 Result.WasOn = getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn);
109 auto GetArgOr1 = [&](unsigned Idx) -> uint64_t {
110 if (auto *ConstInt = dyn_cast<ConstantInt>(
111 getValueFromBundleOpInfo(Assume, BOI, ABA_Argument + Idx)))
112 return ConstInt->getZExtValue();
113 return 1;
114 };
115 if (BOI.End - BOI.Begin > ABA_Argument)
116 Result.ArgValue = GetArgOr1(0);
117 Result.IRArgValue = bundleHasArgument(BOI, ABA_Argument)
118 ? getValueFromBundleOpInfo(Assume, BOI, ABA_Argument)
119 : nullptr;
120 if (Result.AttrKind == Attribute::Alignment)
121 if (BOI.End - BOI.Begin > ABA_Argument + 1)
122 Result.ArgValue = MinAlign(Result.ArgValue, GetArgOr1(1));
123 return Result;
124 }
125
getKnowledgeFromOperandInAssume(AssumeInst & Assume,unsigned Idx)126 RetainedKnowledge llvm::getKnowledgeFromOperandInAssume(AssumeInst &Assume,
127 unsigned Idx) {
128 CallBase::BundleOpInfo BOI = Assume.getBundleOpInfoForOperand(Idx);
129 return getKnowledgeFromBundle(Assume, BOI);
130 }
131
isAssumeWithEmptyBundle(const AssumeInst & Assume)132 bool llvm::isAssumeWithEmptyBundle(const AssumeInst &Assume) {
133 return none_of(Assume.bundle_op_infos(),
134 [](const CallBase::BundleOpInfo &BOI) {
135 return BOI.Tag->getKey() != IgnoreBundleTag;
136 });
137 }
138
getBundleFromUse(const Use * U)139 static CallInst::BundleOpInfo *getBundleFromUse(const Use *U) {
140 if (!match(U->getUser(),
141 m_Intrinsic<Intrinsic::assume>(m_Unless(m_Specific(U->get())))))
142 return nullptr;
143 auto *Intr = cast<IntrinsicInst>(U->getUser());
144 return &Intr->getBundleOpInfoForOperand(U->getOperandNo());
145 }
146
147 RetainedKnowledge
getKnowledgeFromUse(const Use * U,ArrayRef<Attribute::AttrKind> AttrKinds)148 llvm::getKnowledgeFromUse(const Use *U,
149 ArrayRef<Attribute::AttrKind> AttrKinds) {
150 CallInst::BundleOpInfo* Bundle = getBundleFromUse(U);
151 if (!Bundle)
152 return RetainedKnowledge::none();
153 RetainedKnowledge RK =
154 getKnowledgeFromBundle(*cast<AssumeInst>(U->getUser()), *Bundle);
155 if (llvm::is_contained(AttrKinds, RK.AttrKind))
156 return RK;
157 return RetainedKnowledge::none();
158 }
159
160 RetainedKnowledge
getKnowledgeForValue(const Value * V,ArrayRef<Attribute::AttrKind> AttrKinds,AssumptionCache & AC,function_ref<bool (RetainedKnowledge,Instruction *,const CallBase::BundleOpInfo *)> Filter)161 llvm::getKnowledgeForValue(const Value *V,
162 ArrayRef<Attribute::AttrKind> AttrKinds,
163 AssumptionCache &AC,
164 function_ref<bool(RetainedKnowledge, Instruction *,
165 const CallBase::BundleOpInfo *)>
166 Filter) {
167 NumAssumeQueries++;
168 for (AssumptionCache::ResultElem &Elem : AC.assumptionsFor(V)) {
169 auto *II = cast_or_null<AssumeInst>(Elem.Assume);
170 if (!II || Elem.Index == AssumptionCache::ExprResultIdx)
171 continue;
172 if (RetainedKnowledge RK = getKnowledgeFromBundle(
173 *II, II->bundle_op_info_begin()[Elem.Index])) {
174 if (V != RK.WasOn)
175 continue;
176 if (is_contained(AttrKinds, RK.AttrKind) &&
177 Filter(RK, II, &II->bundle_op_info_begin()[Elem.Index])) {
178 NumUsefullAssumeQueries++;
179 return RK;
180 }
181 }
182 }
183
184 return RetainedKnowledge::none();
185 }
186
getKnowledgeValidInContext(const Value * V,ArrayRef<Attribute::AttrKind> AttrKinds,AssumptionCache & AC,const Instruction * CtxI,const DominatorTree * DT)187 RetainedKnowledge llvm::getKnowledgeValidInContext(
188 const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
189 AssumptionCache &AC, const Instruction *CtxI, const DominatorTree *DT) {
190 return getKnowledgeForValue(V, AttrKinds, AC,
191 [&](auto, Instruction *I, auto) {
192 return isValidAssumeForContext(I, CtxI, DT);
193 });
194 }
195