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/Support/DebugCounter.h"
17
18#define DEBUG_TYPE "assume-queries"
19
20using namespace llvm;
21
22STATISTIC(NumAssumeQueries, "Number of Queries into an assume assume bundles");
23STATISTIC(
24 NumUsefullAssumeQueries,
25 "Number of Queries into an assume assume bundles that were satisfied");
26
27DEBUG_COUNTER(AssumeQueryCounter, "assume-queries-counter",
28 "Controls which assumes gets created");
29
30static bool bundleHasArgument(const CallBase::BundleOpInfo &BOI, unsigned Idx) {
31 return BOI.End - BOI.Begin > Idx;
32}
33
34static Value *getValueFromBundleOpInfo(AssumeInst &Assume,
35 const CallBase::BundleOpInfo &BOI,
36 unsigned Idx) {
37 assert(bundleHasArgument(BOI, Idx) && "index out of range");
38 return (Assume.op_begin() + BOI.Begin + Idx)->get();
39}
40
41void llvm::fillMapFromAssume(AssumeInst &Assume, RetainedKnowledgeMap &Result) {
42 for (auto &Bundles : Assume.bundle_op_infos()) {
43 std::pair<Value *, Attribute::AttrKind> Key{
44 nullptr, Attribute::getAttrKindFromName(AttrName: Bundles.Tag->getKey())};
45 if (bundleHasArgument(BOI: Bundles, Idx: ABA_WasOn))
46 Key.first = getValueFromBundleOpInfo(Assume, BOI: Bundles, Idx: ABA_WasOn);
47
48 if (Key.first == nullptr && Key.second == Attribute::None)
49 continue;
50 if (!bundleHasArgument(BOI: Bundles, Idx: ABA_Argument)) {
51 Result[Key][&Assume] = {.Min: 0, .Max: 0};
52 continue;
53 }
54 auto *CI = dyn_cast<ConstantInt>(
55 Val: getValueFromBundleOpInfo(Assume, BOI: Bundles, Idx: ABA_Argument));
56 if (!CI)
57 continue;
58 uint64_t Val = CI->getZExtValue();
59 auto [It, Inserted] = Result[Key].try_emplace(Key: &Assume);
60 if (Inserted) {
61 It->second = {.Min: Val, .Max: Val};
62 continue;
63 }
64 auto &MinMax = It->second;
65 MinMax.Min = std::min(a: Val, b: MinMax.Min);
66 MinMax.Max = std::max(a: Val, b: MinMax.Max);
67 }
68}
69
70RetainedKnowledge
71llvm::getKnowledgeFromBundle(AssumeInst &Assume,
72 const CallBase::BundleOpInfo &BOI) {
73 RetainedKnowledge Result;
74 if (!DebugCounter::shouldExecute(Counter&: AssumeQueryCounter))
75 return Result;
76
77 Result.AttrKind = Attribute::getAttrKindFromName(AttrName: BOI.Tag->getKey());
78 if (bundleHasArgument(BOI, Idx: ABA_WasOn))
79 Result.WasOn = getValueFromBundleOpInfo(Assume, BOI, Idx: ABA_WasOn);
80 auto GetArgOr = [&](unsigned Idx, uint64_t Default) -> uint64_t {
81 if (auto *ConstInt = dyn_cast<ConstantInt>(
82 Val: getValueFromBundleOpInfo(Assume, BOI, Idx: ABA_Argument + Idx)))
83 return ConstInt->getZExtValue();
84 return Default;
85 };
86 if (BOI.End - BOI.Begin > ABA_Argument) {
87 switch (Result.AttrKind) {
88 case Attribute::Alignment:
89 Result.ArgValue = GetArgOr(0, 1);
90 break;
91 case Attribute::Dereferenceable:
92 case Attribute::DereferenceableOrNull:
93 Result.ArgValue = GetArgOr(0, 0);
94 break;
95 case Attribute::None:
96 Result.ArgValue = 0;
97 break;
98 default:
99 llvm_unreachable("Attribute kind does not support argument");
100 }
101 }
102 Result.IRArgValue = bundleHasArgument(BOI, Idx: ABA_Argument)
103 ? getValueFromBundleOpInfo(Assume, BOI, Idx: ABA_Argument)
104 : nullptr;
105 if (Result.AttrKind == Attribute::Alignment)
106 if (BOI.End - BOI.Begin > ABA_Argument + 1)
107 Result.ArgValue = MinAlign(A: Result.ArgValue, B: GetArgOr(1, 1));
108 return Result;
109}
110
111bool llvm::isAssumeWithEmptyBundle(const AssumeInst &Assume) {
112 return none_of(Range: Assume.bundle_op_infos(),
113 P: [](const CallBase::BundleOpInfo &BOI) {
114 return BOI.Tag->getKey() != IgnoreBundleTag;
115 });
116}
117
118RetainedKnowledge
119llvm::getKnowledgeForValue(const Value *V,
120 ArrayRef<Attribute::AttrKind> AttrKinds,
121 AssumptionCache &AC,
122 function_ref<bool(RetainedKnowledge, Instruction *,
123 const CallBase::BundleOpInfo *)>
124 Filter) {
125 NumAssumeQueries++;
126 for (AssumptionCache::ResultElem &Elem : AC.assumptionsFor(V)) {
127 auto *II = cast_or_null<AssumeInst>(Val&: Elem.Assume);
128 if (!II || Elem.Index == AssumptionCache::ExprResultIdx)
129 continue;
130 if (RetainedKnowledge RK = getKnowledgeFromBundle(
131 Assume&: *II, BOI: II->bundle_op_info_begin()[Elem.Index])) {
132 if (V != RK.WasOn)
133 continue;
134 if (is_contained(Range&: AttrKinds, Element: RK.AttrKind) &&
135 Filter(RK, II, &II->bundle_op_info_begin()[Elem.Index])) {
136 NumUsefullAssumeQueries++;
137 return RK;
138 }
139 }
140 }
141
142 return RetainedKnowledge::none();
143}
144
145RetainedKnowledge llvm::getKnowledgeValidInContext(
146 const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
147 AssumptionCache &AC, const Instruction *CtxI, const DominatorTree *DT) {
148 return getKnowledgeForValue(V, AttrKinds, AC,
149 Filter: [&](auto, Instruction *I, auto) {
150 return isValidAssumeForContext(I, CtxI, DT);
151 });
152}
153