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
43void llvm::fillMapFromAssume(AssumeInst &Assume, RetainedKnowledgeMap &Result) {
44 for (auto &Bundles : Assume.bundle_op_infos()) {
45 std::pair<Value *, Attribute::AttrKind> Key{
46 nullptr, Attribute::getAttrKindFromName(AttrName: Bundles.Tag->getKey())};
47 if (bundleHasArgument(BOI: Bundles, Idx: ABA_WasOn))
48 Key.first = getValueFromBundleOpInfo(Assume, BOI: Bundles, Idx: ABA_WasOn);
49
50 if (Key.first == nullptr && Key.second == Attribute::None)
51 continue;
52 if (!bundleHasArgument(BOI: Bundles, Idx: ABA_Argument)) {
53 Result[Key][&Assume] = {.Min: 0, .Max: 0};
54 continue;
55 }
56 auto *CI = dyn_cast<ConstantInt>(
57 Val: getValueFromBundleOpInfo(Assume, BOI: Bundles, Idx: ABA_Argument));
58 if (!CI)
59 continue;
60 uint64_t Val = CI->getZExtValue();
61 auto [It, Inserted] = Result[Key].try_emplace(Key: &Assume);
62 if (Inserted) {
63 It->second = {.Min: Val, .Max: Val};
64 continue;
65 }
66 auto &MinMax = It->second;
67 MinMax.Min = std::min(a: Val, b: MinMax.Min);
68 MinMax.Max = std::max(a: Val, b: MinMax.Max);
69 }
70}
71
72RetainedKnowledge
73llvm::getKnowledgeFromBundle(AssumeInst &Assume,
74 const CallBase::BundleOpInfo &BOI) {
75 RetainedKnowledge Result;
76 if (!DebugCounter::shouldExecute(Counter&: AssumeQueryCounter))
77 return Result;
78
79 Result.AttrKind = Attribute::getAttrKindFromName(AttrName: BOI.Tag->getKey());
80 if (bundleHasArgument(BOI, Idx: ABA_WasOn))
81 Result.WasOn = getValueFromBundleOpInfo(Assume, BOI, Idx: ABA_WasOn);
82 auto GetArgOr = [&](unsigned Idx, uint64_t Default) -> uint64_t {
83 if (auto *ConstInt = dyn_cast<ConstantInt>(
84 Val: getValueFromBundleOpInfo(Assume, BOI, Idx: ABA_Argument + Idx)))
85 return ConstInt->getZExtValue();
86 return Default;
87 };
88 if (BOI.End - BOI.Begin > ABA_Argument) {
89 switch (Result.AttrKind) {
90 case Attribute::Alignment:
91 Result.ArgValue = GetArgOr(0, 1);
92 break;
93 case Attribute::Dereferenceable:
94 case Attribute::DereferenceableOrNull:
95 Result.ArgValue = GetArgOr(0, 0);
96 break;
97 case Attribute::None:
98 Result.ArgValue = 0;
99 break;
100 default:
101 llvm_unreachable("Attribute kind does not support argument");
102 }
103 }
104 Result.IRArgValue = bundleHasArgument(BOI, Idx: ABA_Argument)
105 ? getValueFromBundleOpInfo(Assume, BOI, Idx: ABA_Argument)
106 : nullptr;
107 if (Result.AttrKind == Attribute::Alignment)
108 if (BOI.End - BOI.Begin > ABA_Argument + 1)
109 Result.ArgValue = MinAlign(A: Result.ArgValue, B: GetArgOr(1, 1));
110 return Result;
111}
112
113bool llvm::isAssumeWithEmptyBundle(const AssumeInst &Assume) {
114 return none_of(Range: Assume.bundle_op_infos(),
115 P: [](const CallBase::BundleOpInfo &BOI) {
116 return BOI.Tag->getKey() != IgnoreBundleTag;
117 });
118}
119
120static CallInst::BundleOpInfo *getBundleFromUse(const Use *U) {
121 if (!match(V: U->getUser(),
122 P: m_Intrinsic<Intrinsic::assume>(Ops: m_Unless(M: m_Specific(V: U->get())))))
123 return nullptr;
124 auto *Intr = cast<IntrinsicInst>(Val: U->getUser());
125 return &Intr->getBundleOpInfoForOperand(OpIdx: U->getOperandNo());
126}
127
128RetainedKnowledge
129llvm::getKnowledgeFromUse(const Use *U,
130 ArrayRef<Attribute::AttrKind> AttrKinds) {
131 CallInst::BundleOpInfo* Bundle = getBundleFromUse(U);
132 if (!Bundle)
133 return RetainedKnowledge::none();
134 RetainedKnowledge RK =
135 getKnowledgeFromBundle(Assume&: *cast<AssumeInst>(Val: U->getUser()), BOI: *Bundle);
136 if (llvm::is_contained(Range&: AttrKinds, Element: RK.AttrKind))
137 return RK;
138 return RetainedKnowledge::none();
139}
140
141RetainedKnowledge
142llvm::getKnowledgeForValue(const Value *V,
143 ArrayRef<Attribute::AttrKind> AttrKinds,
144 AssumptionCache &AC,
145 function_ref<bool(RetainedKnowledge, Instruction *,
146 const CallBase::BundleOpInfo *)>
147 Filter) {
148 NumAssumeQueries++;
149 for (AssumptionCache::ResultElem &Elem : AC.assumptionsFor(V)) {
150 auto *II = cast_or_null<AssumeInst>(Val&: Elem.Assume);
151 if (!II || Elem.Index == AssumptionCache::ExprResultIdx)
152 continue;
153 if (RetainedKnowledge RK = getKnowledgeFromBundle(
154 Assume&: *II, BOI: II->bundle_op_info_begin()[Elem.Index])) {
155 if (V != RK.WasOn)
156 continue;
157 if (is_contained(Range&: AttrKinds, Element: RK.AttrKind) &&
158 Filter(RK, II, &II->bundle_op_info_begin()[Elem.Index])) {
159 NumUsefullAssumeQueries++;
160 return RK;
161 }
162 }
163 }
164
165 return RetainedKnowledge::none();
166}
167
168RetainedKnowledge llvm::getKnowledgeValidInContext(
169 const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
170 AssumptionCache &AC, const Instruction *CtxI, const DominatorTree *DT) {
171 return getKnowledgeForValue(V, AttrKinds, AC,
172 Filter: [&](auto, Instruction *I, auto) {
173 return isValidAssumeForContext(I, CxtI: CtxI, DT);
174 });
175}
176