llvm/lib/Analysis/AssumeBundleQueries.cpp

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