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/Analysis/AssumptionCache.h"
11 #include "llvm/Analysis/ValueTracking.h"
12 #include "llvm/IR/Function.h"
13 #include "llvm/IR/InstIterator.h"
14 #include "llvm/IR/IntrinsicInst.h"
15 #include "llvm/IR/PatternMatch.h"
16 
17 using namespace llvm;
18 using namespace llvm::PatternMatch;
19 
20 static bool bundleHasArgument(const CallBase::BundleOpInfo &BOI, unsigned Idx) {
21   return BOI.End - BOI.Begin > Idx;
22 }
23 
24 static Value *getValueFromBundleOpInfo(CallInst &Assume,
25                                        const CallBase::BundleOpInfo &BOI,
26                                        unsigned Idx) {
27   assert(bundleHasArgument(BOI, Idx) && "index out of range");
28   return (Assume.op_begin() + BOI.Begin + Idx)->get();
29 }
30 
31 bool llvm::hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn,
32                                 StringRef AttrName, uint64_t *ArgVal) {
33   assert(isa<IntrinsicInst>(AssumeCI) &&
34          "this function is intended to be used on llvm.assume");
35   IntrinsicInst &Assume = cast<IntrinsicInst>(AssumeCI);
36   assert(Assume.getIntrinsicID() == Intrinsic::assume &&
37          "this function is intended to be used on llvm.assume");
38   assert(Attribute::isExistingAttribute(AttrName) &&
39          "this attribute doesn't exist");
40   assert((ArgVal == nullptr || Attribute::doesAttrKindHaveArgument(
41                                    Attribute::getAttrKindFromName(AttrName))) &&
42          "requested value for an attribute that has no argument");
43   if (Assume.bundle_op_infos().empty())
44     return false;
45 
46   for (auto &BOI : Assume.bundle_op_infos()) {
47     if (BOI.Tag->getKey() != AttrName)
48       continue;
49     if (IsOn && (BOI.End - BOI.Begin <= ABA_WasOn ||
50                  IsOn != getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn)))
51       continue;
52     if (ArgVal) {
53       assert(BOI.End - BOI.Begin > ABA_Argument);
54       *ArgVal =
55           cast<ConstantInt>(getValueFromBundleOpInfo(Assume, BOI, ABA_Argument))
56               ->getZExtValue();
57     }
58     return true;
59   }
60   return false;
61 }
62 
63 void llvm::fillMapFromAssume(CallInst &AssumeCI, RetainedKnowledgeMap &Result) {
64   IntrinsicInst &Assume = cast<IntrinsicInst>(AssumeCI);
65   assert(Assume.getIntrinsicID() == Intrinsic::assume &&
66          "this function is intended to be used on llvm.assume");
67   for (auto &Bundles : Assume.bundle_op_infos()) {
68     std::pair<Value *, Attribute::AttrKind> Key{
69         nullptr, Attribute::getAttrKindFromName(Bundles.Tag->getKey())};
70     if (bundleHasArgument(Bundles, ABA_WasOn))
71       Key.first = getValueFromBundleOpInfo(Assume, Bundles, ABA_WasOn);
72 
73     if (Key.first == nullptr && Key.second == Attribute::None)
74       continue;
75     if (!bundleHasArgument(Bundles, ABA_Argument)) {
76       Result[Key][&Assume] = {0, 0};
77       continue;
78     }
79     unsigned Val = cast<ConstantInt>(
80                        getValueFromBundleOpInfo(Assume, Bundles, ABA_Argument))
81                        ->getZExtValue();
82     auto Lookup = Result.find(Key);
83     if (Lookup == Result.end() || !Lookup->second.count(&Assume)) {
84       Result[Key][&Assume] = {Val, Val};
85       continue;
86     }
87     Lookup->second[&Assume].Min = std::min(Val, Lookup->second[&Assume].Min);
88     Lookup->second[&Assume].Max = std::max(Val, Lookup->second[&Assume].Max);
89   }
90 }
91 
92 static RetainedKnowledge
93 getKnowledgeFromBundle(CallInst &Assume, const CallBase::BundleOpInfo &BOI) {
94   RetainedKnowledge Result;
95   Result.AttrKind = Attribute::getAttrKindFromName(BOI.Tag->getKey());
96   Result.WasOn = getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn);
97   if (BOI.End - BOI.Begin > ABA_Argument)
98     Result.ArgValue =
99         cast<ConstantInt>(getValueFromBundleOpInfo(Assume, BOI, ABA_Argument))
100             ->getZExtValue();
101   return Result;
102 }
103 
104 RetainedKnowledge llvm::getKnowledgeFromOperandInAssume(CallInst &AssumeCI,
105                                                         unsigned Idx) {
106   IntrinsicInst &Assume = cast<IntrinsicInst>(AssumeCI);
107   assert(Assume.getIntrinsicID() == Intrinsic::assume &&
108          "this function is intended to be used on llvm.assume");
109   CallBase::BundleOpInfo BOI = Assume.getBundleOpInfoForOperand(Idx);
110   return getKnowledgeFromBundle(AssumeCI, BOI);
111 }
112 
113 bool llvm::isAssumeWithEmptyBundle(CallInst &CI) {
114   IntrinsicInst &Assume = cast<IntrinsicInst>(CI);
115   assert(Assume.getIntrinsicID() == Intrinsic::assume &&
116          "this function is intended to be used on llvm.assume");
117   return none_of(Assume.bundle_op_infos(),
118                  [](const CallBase::BundleOpInfo &BOI) {
119                    return BOI.Tag->getKey() != "ignore";
120                  });
121 }
122 
123 RetainedKnowledge
124 llvm::getKnowledgeFromUse(const Use *U,
125                           ArrayRef<Attribute::AttrKind> AttrKinds) {
126   if (!match(U->getUser(),
127              m_Intrinsic<Intrinsic::assume>(m_Unless(m_Specific(U->get())))))
128     return RetainedKnowledge::none();
129   auto *Intr = cast<IntrinsicInst>(U->getUser());
130   RetainedKnowledge RK =
131       getKnowledgeFromOperandInAssume(*Intr, U->getOperandNo());
132   for (auto Attr : AttrKinds)
133     if (Attr == RK.AttrKind)
134       return RK;
135   return RetainedKnowledge::none();
136 }
137 
138 RetainedKnowledge llvm::getKnowledgeForValue(
139     const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
140     AssumptionCache *AC,
141     function_ref<bool(RetainedKnowledge, Instruction *)> Filter) {
142   if (AC) {
143 #ifndef NDEBUG
144     RetainedKnowledge RKCheck =
145         getKnowledgeForValue(V, AttrKinds, nullptr, Filter);
146 #endif
147     for (AssumptionCache::ResultElem &Elem : AC->assumptionsFor(V)) {
148       IntrinsicInst *II = cast_or_null<IntrinsicInst>(Elem.Assume);
149       if (!II || Elem.Index == AssumptionCache::ExprResultIdx)
150         continue;
151       if (RetainedKnowledge RK = getKnowledgeFromBundle(
152               *II, II->bundle_op_info_begin()[Elem.Index]))
153         if (is_contained(AttrKinds, RK.AttrKind) && Filter(RK, II)) {
154           assert(!!RKCheck && "invalid Assumption cache");
155           return RK;
156         }
157     }
158     assert(!RKCheck && "invalid Assumption cache");
159     return RetainedKnowledge::none();
160   }
161   for (auto &U : V->uses()) {
162     if (RetainedKnowledge RK = getKnowledgeFromUse(&U, AttrKinds))
163       if (Filter(RK, cast<Instruction>(U.getUser())))
164         return RK;
165   }
166   return RetainedKnowledge::none();
167 }
168 
169 RetainedKnowledge llvm::getKnowledgeValidInContext(
170     const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
171     const Instruction *CtxI, const DominatorTree *DT, AssumptionCache *AC) {
172   return getKnowledgeForValue(V, AttrKinds, AC,
173                               [&](RetainedKnowledge, Instruction *I) {
174                                 return isValidAssumeForContext(I, CtxI, DT);
175                               });
176 }
177