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 #define DEBUG_TYPE "assume-queries"
10 
11 #include "llvm/Analysis/AssumeBundleQueries.h"
12 #include "llvm/ADT/Statistic.h"
13 #include "llvm/Analysis/AssumptionCache.h"
14 #include "llvm/Analysis/ValueTracking.h"
15 #include "llvm/IR/Function.h"
16 #include "llvm/IR/InstIterator.h"
17 #include "llvm/IR/IntrinsicInst.h"
18 #include "llvm/IR/PatternMatch.h"
19 #include "llvm/Support/DebugCounter.h"
20 
21 using namespace llvm;
22 using namespace llvm::PatternMatch;
23 
24 STATISTIC(NumAssumeQueries, "Number of Queries into an assume assume bundles");
25 STATISTIC(
26     NumUsefullAssumeQueries,
27     "Number of Queries into an assume assume bundles that were satisfied");
28 
29 DEBUG_COUNTER(AssumeQueryCounter, "assume-queries-counter",
30               "Controls which assumes gets created");
31 
32 static bool bundleHasArgument(const CallBase::BundleOpInfo &BOI, unsigned Idx) {
33   return BOI.End - BOI.Begin > Idx;
34 }
35 
36 static Value *getValueFromBundleOpInfo(CallInst &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 
43 bool llvm::hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn,
44                                 StringRef AttrName, uint64_t *ArgVal) {
45   assert(isa<IntrinsicInst>(AssumeCI) &&
46          "this function is intended to be used on llvm.assume");
47   IntrinsicInst &Assume = cast<IntrinsicInst>(AssumeCI);
48   assert(Assume.getIntrinsicID() == Intrinsic::assume &&
49          "this function is intended to be used on llvm.assume");
50   assert(Attribute::isExistingAttribute(AttrName) &&
51          "this attribute doesn't exist");
52   assert((ArgVal == nullptr || Attribute::doesAttrKindHaveArgument(
53                                    Attribute::getAttrKindFromName(AttrName))) &&
54          "requested value for an attribute that has no argument");
55   if (Assume.bundle_op_infos().empty())
56     return false;
57 
58   for (auto &BOI : Assume.bundle_op_infos()) {
59     if (BOI.Tag->getKey() != AttrName)
60       continue;
61     if (IsOn && (BOI.End - BOI.Begin <= ABA_WasOn ||
62                  IsOn != getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn)))
63       continue;
64     if (ArgVal) {
65       assert(BOI.End - BOI.Begin > ABA_Argument);
66       *ArgVal =
67           cast<ConstantInt>(getValueFromBundleOpInfo(Assume, BOI, ABA_Argument))
68               ->getZExtValue();
69     }
70     return true;
71   }
72   return false;
73 }
74 
75 void llvm::fillMapFromAssume(CallInst &AssumeCI, RetainedKnowledgeMap &Result) {
76   IntrinsicInst &Assume = cast<IntrinsicInst>(AssumeCI);
77   assert(Assume.getIntrinsicID() == Intrinsic::assume &&
78          "this function is intended to be used on llvm.assume");
79   for (auto &Bundles : Assume.bundle_op_infos()) {
80     std::pair<Value *, Attribute::AttrKind> Key{
81         nullptr, Attribute::getAttrKindFromName(Bundles.Tag->getKey())};
82     if (bundleHasArgument(Bundles, ABA_WasOn))
83       Key.first = getValueFromBundleOpInfo(Assume, Bundles, ABA_WasOn);
84 
85     if (Key.first == nullptr && Key.second == Attribute::None)
86       continue;
87     if (!bundleHasArgument(Bundles, ABA_Argument)) {
88       Result[Key][&Assume] = {0, 0};
89       continue;
90     }
91     unsigned Val = cast<ConstantInt>(
92                        getValueFromBundleOpInfo(Assume, Bundles, ABA_Argument))
93                        ->getZExtValue();
94     auto Lookup = Result.find(Key);
95     if (Lookup == Result.end() || !Lookup->second.count(&Assume)) {
96       Result[Key][&Assume] = {Val, Val};
97       continue;
98     }
99     Lookup->second[&Assume].Min = std::min(Val, Lookup->second[&Assume].Min);
100     Lookup->second[&Assume].Max = std::max(Val, Lookup->second[&Assume].Max);
101   }
102 }
103 
104 RetainedKnowledge
105 llvm::getKnowledgeFromBundle(CallInst &Assume,
106                              const CallBase::BundleOpInfo &BOI) {
107   RetainedKnowledge Result;
108   Result.AttrKind = Attribute::getAttrKindFromName(BOI.Tag->getKey());
109   if (bundleHasArgument(BOI, ABA_WasOn))
110     Result.WasOn = getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn);
111   auto GetArgOr1 = [&](unsigned Idx) -> unsigned {
112     if (auto *ConstInt = dyn_cast<ConstantInt>(
113             getValueFromBundleOpInfo(Assume, BOI, ABA_Argument + Idx)))
114       return ConstInt->getZExtValue();
115     return 1;
116   };
117   if (BOI.End - BOI.Begin > ABA_Argument)
118     Result.ArgValue = GetArgOr1(0);
119   if (Result.AttrKind == Attribute::Alignment)
120     if (BOI.End - BOI.Begin > ABA_Argument + 1)
121       Result.ArgValue = MinAlign(Result.ArgValue, GetArgOr1(1));
122   return Result;
123 }
124 
125 RetainedKnowledge llvm::getKnowledgeFromOperandInAssume(CallInst &AssumeCI,
126                                                         unsigned Idx) {
127   IntrinsicInst &Assume = cast<IntrinsicInst>(AssumeCI);
128   assert(Assume.getIntrinsicID() == Intrinsic::assume &&
129          "this function is intended to be used on llvm.assume");
130   CallBase::BundleOpInfo BOI = Assume.getBundleOpInfoForOperand(Idx);
131   return getKnowledgeFromBundle(AssumeCI, BOI);
132 }
133 
134 bool llvm::isAssumeWithEmptyBundle(CallInst &CI) {
135   IntrinsicInst &Assume = cast<IntrinsicInst>(CI);
136   assert(Assume.getIntrinsicID() == Intrinsic::assume &&
137          "this function is intended to be used on llvm.assume");
138   return none_of(Assume.bundle_op_infos(),
139                  [](const CallBase::BundleOpInfo &BOI) {
140                    return BOI.Tag->getKey() != IgnoreBundleTag;
141                  });
142 }
143 
144 static CallInst::BundleOpInfo *getBundleFromUse(const Use *U) {
145   auto *Intr = dyn_cast<IntrinsicInst>(U->getUser());
146   if (!match(U->getUser(),
147              m_Intrinsic<Intrinsic::assume>(m_Unless(m_Specific(U->get())))))
148     return nullptr;
149   return &Intr->getBundleOpInfoForOperand(U->getOperandNo());
150 }
151 
152 RetainedKnowledge
153 llvm::getKnowledgeFromUse(const Use *U,
154                           ArrayRef<Attribute::AttrKind> AttrKinds) {
155   CallInst::BundleOpInfo* Bundle = getBundleFromUse(U);
156   if (!Bundle)
157     return RetainedKnowledge::none();
158   RetainedKnowledge RK =
159       getKnowledgeFromBundle(*cast<CallInst>(U->getUser()), *Bundle);
160   for (auto Attr : AttrKinds)
161     if (Attr == RK.AttrKind)
162       return RK;
163   return RetainedKnowledge::none();
164 }
165 
166 RetainedKnowledge
167 llvm::getKnowledgeForValue(const Value *V,
168                            ArrayRef<Attribute::AttrKind> AttrKinds,
169                            AssumptionCache *AC,
170                            function_ref<bool(RetainedKnowledge, Instruction *,
171                                              const CallBase::BundleOpInfo *)>
172                                Filter) {
173   NumAssumeQueries++;
174   if (!DebugCounter::shouldExecute(AssumeQueryCounter))
175     return RetainedKnowledge::none();
176   if (AC) {
177     for (AssumptionCache::ResultElem &Elem : AC->assumptionsFor(V)) {
178       IntrinsicInst *II = cast_or_null<IntrinsicInst>(Elem.Assume);
179       if (!II || Elem.Index == AssumptionCache::ExprResultIdx)
180         continue;
181       if (RetainedKnowledge RK = getKnowledgeFromBundle(
182               *II, II->bundle_op_info_begin()[Elem.Index])) {
183         if (V != RK.WasOn)
184           continue;
185         if (is_contained(AttrKinds, RK.AttrKind) &&
186             Filter(RK, II, &II->bundle_op_info_begin()[Elem.Index])) {
187           NumUsefullAssumeQueries++;
188           return RK;
189         }
190       }
191     }
192     return RetainedKnowledge::none();
193   }
194   for (const auto &U : V->uses()) {
195     CallInst::BundleOpInfo* Bundle = getBundleFromUse(&U);
196     if (!Bundle)
197       continue;
198     if (RetainedKnowledge RK =
199             getKnowledgeFromBundle(*cast<CallInst>(U.getUser()), *Bundle))
200       if (is_contained(AttrKinds, RK.AttrKind) &&
201           Filter(RK, cast<Instruction>(U.getUser()), Bundle)) {
202         NumUsefullAssumeQueries++;
203         return RK;
204       }
205   }
206   return RetainedKnowledge::none();
207 }
208 
209 RetainedKnowledge llvm::getKnowledgeValidInContext(
210     const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
211     const Instruction *CtxI, const DominatorTree *DT, AssumptionCache *AC) {
212   return getKnowledgeForValue(V, AttrKinds, AC,
213                               [&](auto, Instruction *I, auto) {
214                                 return isValidAssumeForContext(I, CtxI, DT);
215                               });
216 }
217