xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/AssumeBundleQueries.cpp (revision 7ef62cebc2f965b0f640263e179276928885e33d)
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 
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(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 
43 bool llvm::hasAttributeInAssume(AssumeInst &Assume, Value *IsOn,
44                                 StringRef AttrName, uint64_t *ArgVal) {
45   assert(Attribute::isExistingAttribute(AttrName) &&
46          "this attribute doesn't exist");
47   assert((ArgVal == nullptr || Attribute::isIntAttrKind(
48                                    Attribute::getAttrKindFromName(AttrName))) &&
49          "requested value for an attribute that has no argument");
50   if (Assume.bundle_op_infos().empty())
51     return false;
52 
53   for (auto &BOI : Assume.bundle_op_infos()) {
54     if (BOI.Tag->getKey() != AttrName)
55       continue;
56     if (IsOn && (BOI.End - BOI.Begin <= ABA_WasOn ||
57                  IsOn != getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn)))
58       continue;
59     if (ArgVal) {
60       assert(BOI.End - BOI.Begin > ABA_Argument);
61       *ArgVal =
62           cast<ConstantInt>(getValueFromBundleOpInfo(Assume, BOI, ABA_Argument))
63               ->getZExtValue();
64     }
65     return true;
66   }
67   return false;
68 }
69 
70 void llvm::fillMapFromAssume(AssumeInst &Assume, RetainedKnowledgeMap &Result) {
71   for (auto &Bundles : Assume.bundle_op_infos()) {
72     std::pair<Value *, Attribute::AttrKind> Key{
73         nullptr, Attribute::getAttrKindFromName(Bundles.Tag->getKey())};
74     if (bundleHasArgument(Bundles, ABA_WasOn))
75       Key.first = getValueFromBundleOpInfo(Assume, Bundles, ABA_WasOn);
76 
77     if (Key.first == nullptr && Key.second == Attribute::None)
78       continue;
79     if (!bundleHasArgument(Bundles, ABA_Argument)) {
80       Result[Key][&Assume] = {0, 0};
81       continue;
82     }
83     auto *CI = dyn_cast<ConstantInt>(
84         getValueFromBundleOpInfo(Assume, Bundles, ABA_Argument));
85     if (!CI)
86       continue;
87     uint64_t Val = CI->getZExtValue();
88     auto Lookup = Result.find(Key);
89     if (Lookup == Result.end() || !Lookup->second.count(&Assume)) {
90       Result[Key][&Assume] = {Val, Val};
91       continue;
92     }
93     Lookup->second[&Assume].Min = std::min(Val, Lookup->second[&Assume].Min);
94     Lookup->second[&Assume].Max = std::max(Val, Lookup->second[&Assume].Max);
95   }
96 }
97 
98 RetainedKnowledge
99 llvm::getKnowledgeFromBundle(AssumeInst &Assume,
100                              const CallBase::BundleOpInfo &BOI) {
101   RetainedKnowledge Result;
102   Result.AttrKind = Attribute::getAttrKindFromName(BOI.Tag->getKey());
103   if (bundleHasArgument(BOI, ABA_WasOn))
104     Result.WasOn = getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn);
105   auto GetArgOr1 = [&](unsigned Idx) -> uint64_t {
106     if (auto *ConstInt = dyn_cast<ConstantInt>(
107             getValueFromBundleOpInfo(Assume, BOI, ABA_Argument + Idx)))
108       return ConstInt->getZExtValue();
109     return 1;
110   };
111   if (BOI.End - BOI.Begin > ABA_Argument)
112     Result.ArgValue = GetArgOr1(0);
113   if (Result.AttrKind == Attribute::Alignment)
114     if (BOI.End - BOI.Begin > ABA_Argument + 1)
115       Result.ArgValue = MinAlign(Result.ArgValue, GetArgOr1(1));
116   return Result;
117 }
118 
119 RetainedKnowledge llvm::getKnowledgeFromOperandInAssume(AssumeInst &Assume,
120                                                         unsigned Idx) {
121   CallBase::BundleOpInfo BOI = Assume.getBundleOpInfoForOperand(Idx);
122   return getKnowledgeFromBundle(Assume, BOI);
123 }
124 
125 bool llvm::isAssumeWithEmptyBundle(AssumeInst &Assume) {
126   return none_of(Assume.bundle_op_infos(),
127                  [](const CallBase::BundleOpInfo &BOI) {
128                    return BOI.Tag->getKey() != IgnoreBundleTag;
129                  });
130 }
131 
132 static CallInst::BundleOpInfo *getBundleFromUse(const Use *U) {
133   if (!match(U->getUser(),
134              m_Intrinsic<Intrinsic::assume>(m_Unless(m_Specific(U->get())))))
135     return nullptr;
136   auto *Intr = cast<IntrinsicInst>(U->getUser());
137   return &Intr->getBundleOpInfoForOperand(U->getOperandNo());
138 }
139 
140 RetainedKnowledge
141 llvm::getKnowledgeFromUse(const Use *U,
142                           ArrayRef<Attribute::AttrKind> AttrKinds) {
143   CallInst::BundleOpInfo* Bundle = getBundleFromUse(U);
144   if (!Bundle)
145     return RetainedKnowledge::none();
146   RetainedKnowledge RK =
147       getKnowledgeFromBundle(*cast<AssumeInst>(U->getUser()), *Bundle);
148   if (llvm::is_contained(AttrKinds, RK.AttrKind))
149     return RK;
150   return RetainedKnowledge::none();
151 }
152 
153 RetainedKnowledge
154 llvm::getKnowledgeForValue(const Value *V,
155                            ArrayRef<Attribute::AttrKind> AttrKinds,
156                            AssumptionCache *AC,
157                            function_ref<bool(RetainedKnowledge, Instruction *,
158                                              const CallBase::BundleOpInfo *)>
159                                Filter) {
160   NumAssumeQueries++;
161   if (!DebugCounter::shouldExecute(AssumeQueryCounter))
162     return RetainedKnowledge::none();
163   if (AC) {
164     for (AssumptionCache::ResultElem &Elem : AC->assumptionsFor(V)) {
165       auto *II = dyn_cast_or_null<AssumeInst>(Elem.Assume);
166       if (!II || Elem.Index == AssumptionCache::ExprResultIdx)
167         continue;
168       if (RetainedKnowledge RK = getKnowledgeFromBundle(
169               *II, II->bundle_op_info_begin()[Elem.Index])) {
170         if (V != RK.WasOn)
171           continue;
172         if (is_contained(AttrKinds, RK.AttrKind) &&
173             Filter(RK, II, &II->bundle_op_info_begin()[Elem.Index])) {
174           NumUsefullAssumeQueries++;
175           return RK;
176         }
177       }
178     }
179     return RetainedKnowledge::none();
180   }
181   for (const auto &U : V->uses()) {
182     CallInst::BundleOpInfo* Bundle = getBundleFromUse(&U);
183     if (!Bundle)
184       continue;
185     if (RetainedKnowledge RK =
186             getKnowledgeFromBundle(*cast<AssumeInst>(U.getUser()), *Bundle))
187       if (is_contained(AttrKinds, RK.AttrKind) &&
188           Filter(RK, cast<Instruction>(U.getUser()), Bundle)) {
189         NumUsefullAssumeQueries++;
190         return RK;
191       }
192   }
193   return RetainedKnowledge::none();
194 }
195 
196 RetainedKnowledge llvm::getKnowledgeValidInContext(
197     const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
198     const Instruction *CtxI, const DominatorTree *DT, AssumptionCache *AC) {
199   return getKnowledgeForValue(V, AttrKinds, AC,
200                               [&](auto, Instruction *I, auto) {
201                                 return isValidAssumeForContext(I, CtxI, DT);
202                               });
203 }
204