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     auto *CI = dyn_cast<ConstantInt>(
92         getValueFromBundleOpInfo(Assume, Bundles, ABA_Argument));
93     if (!CI)
94       continue;
95     unsigned Val = CI->getZExtValue();
96     auto Lookup = Result.find(Key);
97     if (Lookup == Result.end() || !Lookup->second.count(&Assume)) {
98       Result[Key][&Assume] = {Val, Val};
99       continue;
100     }
101     Lookup->second[&Assume].Min = std::min(Val, Lookup->second[&Assume].Min);
102     Lookup->second[&Assume].Max = std::max(Val, Lookup->second[&Assume].Max);
103   }
104 }
105 
106 RetainedKnowledge
107 llvm::getKnowledgeFromBundle(CallInst &Assume,
108                              const CallBase::BundleOpInfo &BOI) {
109   RetainedKnowledge Result;
110   Result.AttrKind = Attribute::getAttrKindFromName(BOI.Tag->getKey());
111   if (bundleHasArgument(BOI, ABA_WasOn))
112     Result.WasOn = getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn);
113   auto GetArgOr1 = [&](unsigned Idx) -> unsigned {
114     if (auto *ConstInt = dyn_cast<ConstantInt>(
115             getValueFromBundleOpInfo(Assume, BOI, ABA_Argument + Idx)))
116       return ConstInt->getZExtValue();
117     return 1;
118   };
119   if (BOI.End - BOI.Begin > ABA_Argument)
120     Result.ArgValue = GetArgOr1(0);
121   if (Result.AttrKind == Attribute::Alignment)
122     if (BOI.End - BOI.Begin > ABA_Argument + 1)
123       Result.ArgValue = MinAlign(Result.ArgValue, GetArgOr1(1));
124   return Result;
125 }
126 
127 RetainedKnowledge llvm::getKnowledgeFromOperandInAssume(CallInst &AssumeCI,
128                                                         unsigned Idx) {
129   IntrinsicInst &Assume = cast<IntrinsicInst>(AssumeCI);
130   assert(Assume.getIntrinsicID() == Intrinsic::assume &&
131          "this function is intended to be used on llvm.assume");
132   CallBase::BundleOpInfo BOI = Assume.getBundleOpInfoForOperand(Idx);
133   return getKnowledgeFromBundle(AssumeCI, BOI);
134 }
135 
136 bool llvm::isAssumeWithEmptyBundle(CallInst &CI) {
137   IntrinsicInst &Assume = cast<IntrinsicInst>(CI);
138   assert(Assume.getIntrinsicID() == Intrinsic::assume &&
139          "this function is intended to be used on llvm.assume");
140   return none_of(Assume.bundle_op_infos(),
141                  [](const CallBase::BundleOpInfo &BOI) {
142                    return BOI.Tag->getKey() != IgnoreBundleTag;
143                  });
144 }
145 
146 static CallInst::BundleOpInfo *getBundleFromUse(const Use *U) {
147   auto *Intr = dyn_cast<IntrinsicInst>(U->getUser());
148   if (!match(U->getUser(),
149              m_Intrinsic<Intrinsic::assume>(m_Unless(m_Specific(U->get())))))
150     return nullptr;
151   return &Intr->getBundleOpInfoForOperand(U->getOperandNo());
152 }
153 
154 RetainedKnowledge
155 llvm::getKnowledgeFromUse(const Use *U,
156                           ArrayRef<Attribute::AttrKind> AttrKinds) {
157   CallInst::BundleOpInfo* Bundle = getBundleFromUse(U);
158   if (!Bundle)
159     return RetainedKnowledge::none();
160   RetainedKnowledge RK =
161       getKnowledgeFromBundle(*cast<CallInst>(U->getUser()), *Bundle);
162   if (llvm::is_contained(AttrKinds, RK.AttrKind))
163     return RK;
164   return RetainedKnowledge::none();
165 }
166 
167 RetainedKnowledge
168 llvm::getKnowledgeForValue(const Value *V,
169                            ArrayRef<Attribute::AttrKind> AttrKinds,
170                            AssumptionCache *AC,
171                            function_ref<bool(RetainedKnowledge, Instruction *,
172                                              const CallBase::BundleOpInfo *)>
173                                Filter) {
174   NumAssumeQueries++;
175   if (!DebugCounter::shouldExecute(AssumeQueryCounter))
176     return RetainedKnowledge::none();
177   if (AC) {
178     for (AssumptionCache::ResultElem &Elem : AC->assumptionsFor(V)) {
179       IntrinsicInst *II = cast_or_null<IntrinsicInst>(Elem.Assume);
180       if (!II || Elem.Index == AssumptionCache::ExprResultIdx)
181         continue;
182       if (RetainedKnowledge RK = getKnowledgeFromBundle(
183               *II, II->bundle_op_info_begin()[Elem.Index])) {
184         if (V != RK.WasOn)
185           continue;
186         if (is_contained(AttrKinds, RK.AttrKind) &&
187             Filter(RK, II, &II->bundle_op_info_begin()[Elem.Index])) {
188           NumUsefullAssumeQueries++;
189           return RK;
190         }
191       }
192     }
193     return RetainedKnowledge::none();
194   }
195   for (const auto &U : V->uses()) {
196     CallInst::BundleOpInfo* Bundle = getBundleFromUse(&U);
197     if (!Bundle)
198       continue;
199     if (RetainedKnowledge RK =
200             getKnowledgeFromBundle(*cast<CallInst>(U.getUser()), *Bundle))
201       if (is_contained(AttrKinds, RK.AttrKind) &&
202           Filter(RK, cast<Instruction>(U.getUser()), Bundle)) {
203         NumUsefullAssumeQueries++;
204         return RK;
205       }
206   }
207   return RetainedKnowledge::none();
208 }
209 
210 RetainedKnowledge llvm::getKnowledgeValidInContext(
211     const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
212     const Instruction *CtxI, const DominatorTree *DT, AssumptionCache *AC) {
213   return getKnowledgeForValue(V, AttrKinds, AC,
214                               [&](auto, Instruction *I, auto) {
215                                 return isValidAssumeForContext(I, CtxI, DT);
216                               });
217 }
218