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