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   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(const 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 = 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 }