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
21using namespace llvm;
22using namespace llvm::PatternMatch;
23
24STATISTIC(NumAssumeQueries, "Number of Queries into an assume assume bundles");
25STATISTIC(
26 NumUsefullAssumeQueries,
27 "Number of Queries into an assume assume bundles that were satisfied");
28
29DEBUG_COUNTER(AssumeQueryCounter, "assume-queries-counter",
30 "Controls which assumes gets created");
31
32static bool bundleHasArgument(const CallBase::BundleOpInfo &BOI, unsigned Idx) {
33 return BOI.End - BOI.Begin > Idx;
34}
35
36static 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
43bool 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, Idx: ABA_WasOn)))
58 continue;
59 if (ArgVal) {
60 assert(BOI.End - BOI.Begin > ABA_Argument);
61 *ArgVal =
62 cast<ConstantInt>(Val: getValueFromBundleOpInfo(Assume, BOI, Idx: ABA_Argument))
63 ->getZExtValue();
64 }
65 return true;
66 }
67 return false;
68}
69
70void 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(AttrName: Bundles.Tag->getKey())};
74 if (bundleHasArgument(BOI: Bundles, Idx: ABA_WasOn))
75 Key.first = getValueFromBundleOpInfo(Assume, BOI: Bundles, Idx: ABA_WasOn);
76
77 if (Key.first == nullptr && Key.second == Attribute::None)
78 continue;
79 if (!bundleHasArgument(BOI: Bundles, Idx: ABA_Argument)) {
80 Result[Key][&Assume] = {.Min: 0, .Max: 0};
81 continue;
82 }
83 auto *CI = dyn_cast<ConstantInt>(
84 Val: getValueFromBundleOpInfo(Assume, BOI: Bundles, Idx: ABA_Argument));
85 if (!CI)
86 continue;
87 uint64_t Val = CI->getZExtValue();
88 auto Lookup = Result.find(Val: Key);
89 if (Lookup == Result.end() || !Lookup->second.count(Val: &Assume)) {
90 Result[Key][&Assume] = {.Min: Val, .Max: Val};
91 continue;
92 }
93 Lookup->second[&Assume].Min = std::min(a: Val, b: Lookup->second[&Assume].Min);
94 Lookup->second[&Assume].Max = std::max(a: Val, b: Lookup->second[&Assume].Max);
95 }
96}
97
98RetainedKnowledge
99llvm::getKnowledgeFromBundle(AssumeInst &Assume,
100 const CallBase::BundleOpInfo &BOI) {
101 RetainedKnowledge Result;
102 if (!DebugCounter::shouldExecute(CounterName: AssumeQueryCounter))
103 return Result;
104
105 Result.AttrKind = Attribute::getAttrKindFromName(AttrName: BOI.Tag->getKey());
106 if (bundleHasArgument(BOI, Idx: ABA_WasOn))
107 Result.WasOn = getValueFromBundleOpInfo(Assume, BOI, Idx: ABA_WasOn);
108 auto GetArgOr1 = [&](unsigned Idx) -> uint64_t {
109 if (auto *ConstInt = dyn_cast<ConstantInt>(
110 Val: getValueFromBundleOpInfo(Assume, BOI, Idx: ABA_Argument + Idx)))
111 return ConstInt->getZExtValue();
112 return 1;
113 };
114 if (BOI.End - BOI.Begin > ABA_Argument)
115 Result.ArgValue = GetArgOr1(0);
116 if (Result.AttrKind == Attribute::Alignment)
117 if (BOI.End - BOI.Begin > ABA_Argument + 1)
118 Result.ArgValue = MinAlign(A: Result.ArgValue, B: GetArgOr1(1));
119 return Result;
120}
121
122RetainedKnowledge llvm::getKnowledgeFromOperandInAssume(AssumeInst &Assume,
123 unsigned Idx) {
124 CallBase::BundleOpInfo BOI = Assume.getBundleOpInfoForOperand(OpIdx: Idx);
125 return getKnowledgeFromBundle(Assume, BOI);
126}
127
128bool llvm::isAssumeWithEmptyBundle(const AssumeInst &Assume) {
129 return none_of(Range: Assume.bundle_op_infos(),
130 P: [](const CallBase::BundleOpInfo &BOI) {
131 return BOI.Tag->getKey() != IgnoreBundleTag;
132 });
133}
134
135static CallInst::BundleOpInfo *getBundleFromUse(const Use *U) {
136 if (!match(V: U->getUser(),
137 P: m_Intrinsic<Intrinsic::assume>(Op0: m_Unless(M: m_Specific(V: U->get())))))
138 return nullptr;
139 auto *Intr = cast<IntrinsicInst>(Val: U->getUser());
140 return &Intr->getBundleOpInfoForOperand(OpIdx: U->getOperandNo());
141}
142
143RetainedKnowledge
144llvm::getKnowledgeFromUse(const Use *U,
145 ArrayRef<Attribute::AttrKind> AttrKinds) {
146 CallInst::BundleOpInfo* Bundle = getBundleFromUse(U);
147 if (!Bundle)
148 return RetainedKnowledge::none();
149 RetainedKnowledge RK =
150 getKnowledgeFromBundle(Assume&: *cast<AssumeInst>(Val: U->getUser()), BOI: *Bundle);
151 if (llvm::is_contained(Range&: AttrKinds, Element: RK.AttrKind))
152 return RK;
153 return RetainedKnowledge::none();
154}
155
156RetainedKnowledge
157llvm::getKnowledgeForValue(const Value *V,
158 ArrayRef<Attribute::AttrKind> AttrKinds,
159 AssumptionCache *AC,
160 function_ref<bool(RetainedKnowledge, Instruction *,
161 const CallBase::BundleOpInfo *)>
162 Filter) {
163 NumAssumeQueries++;
164 if (AC) {
165 for (AssumptionCache::ResultElem &Elem : AC->assumptionsFor(V)) {
166 auto *II = cast_or_null<AssumeInst>(Val&: Elem.Assume);
167 if (!II || Elem.Index == AssumptionCache::ExprResultIdx)
168 continue;
169 if (RetainedKnowledge RK = getKnowledgeFromBundle(
170 Assume&: *II, BOI: II->bundle_op_info_begin()[Elem.Index])) {
171 if (V != RK.WasOn)
172 continue;
173 if (is_contained(Range&: AttrKinds, Element: RK.AttrKind) &&
174 Filter(RK, II, &II->bundle_op_info_begin()[Elem.Index])) {
175 NumUsefullAssumeQueries++;
176 return RK;
177 }
178 }
179 }
180 return RetainedKnowledge::none();
181 }
182 for (const auto &U : V->uses()) {
183 CallInst::BundleOpInfo* Bundle = getBundleFromUse(U: &U);
184 if (!Bundle)
185 continue;
186 if (RetainedKnowledge RK =
187 getKnowledgeFromBundle(Assume&: *cast<AssumeInst>(Val: U.getUser()), BOI: *Bundle))
188 if (is_contained(Range&: AttrKinds, Element: RK.AttrKind) &&
189 Filter(RK, cast<Instruction>(Val: U.getUser()), Bundle)) {
190 NumUsefullAssumeQueries++;
191 return RK;
192 }
193 }
194 return RetainedKnowledge::none();
195}
196
197RetainedKnowledge llvm::getKnowledgeValidInContext(
198 const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
199 const Instruction *CtxI, const DominatorTree *DT, AssumptionCache *AC) {
200 return getKnowledgeForValue(V, AttrKinds, AC,
201 Filter: [&](auto, Instruction *I, auto) {
202 return isValidAssumeForContext(I, CxtI: CtxI, DT);
203 });
204}
205