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(CounterName: 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 GetArgOr1 = [&](unsigned Idx) -> uint64_t {
110 if (auto *ConstInt = dyn_cast<ConstantInt>(
111 Val: getValueFromBundleOpInfo(Assume, BOI, Idx: 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 if (Result.AttrKind == Attribute::Alignment)
118 if (BOI.End - BOI.Begin > ABA_Argument + 1)
119 Result.ArgValue = MinAlign(A: Result.ArgValue, B: GetArgOr1(1));
120 return Result;
121}
122
123RetainedKnowledge llvm::getKnowledgeFromOperandInAssume(AssumeInst &Assume,
124 unsigned Idx) {
125 CallBase::BundleOpInfo BOI = Assume.getBundleOpInfoForOperand(OpIdx: Idx);
126 return getKnowledgeFromBundle(Assume, BOI);
127}
128
129bool llvm::isAssumeWithEmptyBundle(const AssumeInst &Assume) {
130 return none_of(Range: Assume.bundle_op_infos(),
131 P: [](const CallBase::BundleOpInfo &BOI) {
132 return BOI.Tag->getKey() != IgnoreBundleTag;
133 });
134}
135
136static CallInst::BundleOpInfo *getBundleFromUse(const Use *U) {
137 if (!match(V: U->getUser(),
138 P: m_Intrinsic<Intrinsic::assume>(Op0: m_Unless(M: m_Specific(V: U->get())))))
139 return nullptr;
140 auto *Intr = cast<IntrinsicInst>(Val: U->getUser());
141 return &Intr->getBundleOpInfoForOperand(OpIdx: U->getOperandNo());
142}
143
144RetainedKnowledge
145llvm::getKnowledgeFromUse(const Use *U,
146 ArrayRef<Attribute::AttrKind> AttrKinds) {
147 CallInst::BundleOpInfo* Bundle = getBundleFromUse(U);
148 if (!Bundle)
149 return RetainedKnowledge::none();
150 RetainedKnowledge RK =
151 getKnowledgeFromBundle(Assume&: *cast<AssumeInst>(Val: U->getUser()), BOI: *Bundle);
152 if (llvm::is_contained(Range&: AttrKinds, Element: RK.AttrKind))
153 return RK;
154 return RetainedKnowledge::none();
155}
156
157RetainedKnowledge
158llvm::getKnowledgeForValue(const Value *V,
159 ArrayRef<Attribute::AttrKind> AttrKinds,
160 AssumptionCache &AC,
161 function_ref<bool(RetainedKnowledge, Instruction *,
162 const CallBase::BundleOpInfo *)>
163 Filter) {
164 NumAssumeQueries++;
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
181 return RetainedKnowledge::none();
182}
183
184RetainedKnowledge llvm::getKnowledgeValidInContext(
185 const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
186 AssumptionCache &AC, const Instruction *CtxI, const DominatorTree *DT) {
187 return getKnowledgeForValue(V, AttrKinds, AC,
188 Filter: [&](auto, Instruction *I, auto) {
189 return isValidAssumeForContext(I, CxtI: CtxI, DT);
190 });
191}
192