xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/AssumeBundleQueries.cpp (revision c66ec88fed842fbaad62c30d510644ceb7bd2d71)
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   if (BOI.End - BOI.Begin > ABA_Argument)
112     Result.ArgValue =
113         cast<ConstantInt>(getValueFromBundleOpInfo(Assume, BOI, ABA_Argument))
114             ->getZExtValue();
115   return Result;
116 }
117 
118 RetainedKnowledge llvm::getKnowledgeFromOperandInAssume(CallInst &AssumeCI,
119                                                         unsigned Idx) {
120   IntrinsicInst &Assume = cast<IntrinsicInst>(AssumeCI);
121   assert(Assume.getIntrinsicID() == Intrinsic::assume &&
122          "this function is intended to be used on llvm.assume");
123   CallBase::BundleOpInfo BOI = Assume.getBundleOpInfoForOperand(Idx);
124   return getKnowledgeFromBundle(AssumeCI, BOI);
125 }
126 
127 bool llvm::isAssumeWithEmptyBundle(CallInst &CI) {
128   IntrinsicInst &Assume = cast<IntrinsicInst>(CI);
129   assert(Assume.getIntrinsicID() == Intrinsic::assume &&
130          "this function is intended to be used on llvm.assume");
131   return none_of(Assume.bundle_op_infos(),
132                  [](const CallBase::BundleOpInfo &BOI) {
133                    return BOI.Tag->getKey() != IgnoreBundleTag;
134                  });
135 }
136 
137 static CallInst::BundleOpInfo *getBundleFromUse(const Use *U) {
138   auto *Intr = dyn_cast<IntrinsicInst>(U->getUser());
139   if (!match(U->getUser(),
140              m_Intrinsic<Intrinsic::assume>(m_Unless(m_Specific(U->get())))))
141     return nullptr;
142   return &Intr->getBundleOpInfoForOperand(U->getOperandNo());
143 }
144 
145 RetainedKnowledge
146 llvm::getKnowledgeFromUse(const Use *U,
147                           ArrayRef<Attribute::AttrKind> AttrKinds) {
148   CallInst::BundleOpInfo* Bundle = getBundleFromUse(U);
149   if (!Bundle)
150     return RetainedKnowledge::none();
151   RetainedKnowledge RK =
152       getKnowledgeFromBundle(*cast<CallInst>(U->getUser()), *Bundle);
153   for (auto Attr : AttrKinds)
154     if (Attr == RK.AttrKind)
155       return RK;
156   return RetainedKnowledge::none();
157 }
158 
159 RetainedKnowledge
160 llvm::getKnowledgeForValue(const Value *V,
161                            ArrayRef<Attribute::AttrKind> AttrKinds,
162                            AssumptionCache *AC,
163                            function_ref<bool(RetainedKnowledge, Instruction *,
164                                              const CallBase::BundleOpInfo *)>
165                                Filter) {
166   NumAssumeQueries++;
167   if (!DebugCounter::shouldExecute(AssumeQueryCounter))
168     return RetainedKnowledge::none();
169   if (AC) {
170     for (AssumptionCache::ResultElem &Elem : AC->assumptionsFor(V)) {
171       IntrinsicInst *II = cast_or_null<IntrinsicInst>(Elem.Assume);
172       if (!II || Elem.Index == AssumptionCache::ExprResultIdx)
173         continue;
174       if (RetainedKnowledge RK = getKnowledgeFromBundle(
175               *II, II->bundle_op_info_begin()[Elem.Index]))
176         if (is_contained(AttrKinds, RK.AttrKind) &&
177             Filter(RK, II, &II->bundle_op_info_begin()[Elem.Index])) {
178           NumUsefullAssumeQueries++;
179           return RK;
180         }
181     }
182     return RetainedKnowledge::none();
183   }
184   for (const auto &U : V->uses()) {
185     CallInst::BundleOpInfo* Bundle = getBundleFromUse(&U);
186     if (!Bundle)
187       continue;
188     if (RetainedKnowledge RK =
189             getKnowledgeFromBundle(*cast<CallInst>(U.getUser()), *Bundle))
190       if (is_contained(AttrKinds, RK.AttrKind) &&
191           Filter(RK, cast<Instruction>(U.getUser()), Bundle)) {
192         NumUsefullAssumeQueries++;
193         return RK;
194       }
195   }
196   return RetainedKnowledge::none();
197 }
198 
199 RetainedKnowledge llvm::getKnowledgeValidInContext(
200     const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
201     const Instruction *CtxI, const DominatorTree *DT, AssumptionCache *AC) {
202   return getKnowledgeForValue(V, AttrKinds, AC,
203                               [&](auto, Instruction *I, auto) {
204                                 return isValidAssumeForContext(I, CtxI, DT);
205                               });
206 }
207