llvm/lib/Analysis/AssumeBundleQueries.cpp

//===- AssumeBundleQueries.cpp - tool to query assume bundles ---*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/AssumeBundleQueries.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/DebugCounter.h"

#define DEBUG_TYPE "assume-queries"

using namespace llvm;
using namespace llvm::PatternMatch;

STATISTIC(NumAssumeQueries, "Number of Queries into an assume assume bundles");
STATISTIC(
    NumUsefullAssumeQueries,
    "Number of Queries into an assume assume bundles that were satisfied");

DEBUG_COUNTER(AssumeQueryCounter, "assume-queries-counter",
              "Controls which assumes gets created");

static bool bundleHasArgument(const CallBase::BundleOpInfo &BOI, unsigned Idx) {
  return BOI.End - BOI.Begin > Idx;
}

static Value *getValueFromBundleOpInfo(AssumeInst &Assume,
                                       const CallBase::BundleOpInfo &BOI,
                                       unsigned Idx) {
  assert(bundleHasArgument(BOI, Idx) && "index out of range");
  return (Assume.op_begin() + BOI.Begin + Idx)->get();
}

void llvm::fillMapFromAssume(AssumeInst &Assume, RetainedKnowledgeMap &Result) {
  for (auto &Bundles : Assume.bundle_op_infos()) {
    std::pair<Value *, Attribute::AttrKind> Key{
        nullptr, Attribute::getAttrKindFromName(Bundles.Tag->getKey())};
    if (bundleHasArgument(Bundles, ABA_WasOn))
      Key.first = getValueFromBundleOpInfo(Assume, Bundles, ABA_WasOn);

    if (Key.first == nullptr && Key.second == Attribute::None)
      continue;
    if (!bundleHasArgument(Bundles, ABA_Argument)) {
      Result[Key][&Assume] = {0, 0};
      continue;
    }
    auto *CI = dyn_cast<ConstantInt>(
        getValueFromBundleOpInfo(Assume, Bundles, ABA_Argument));
    if (!CI)
      continue;
    uint64_t Val = CI->getZExtValue();
    auto [It, Inserted] = Result[Key].try_emplace(&Assume);
    if (Inserted) {
      It->second = {Val, Val};
      continue;
    }
    auto &MinMax = It->second;
    MinMax.Min = std::min(Val, MinMax.Min);
    MinMax.Max = std::max(Val, MinMax.Max);
  }
}

RetainedKnowledge
llvm::getKnowledgeFromBundle(AssumeInst &Assume,
                             const CallBase::BundleOpInfo &BOI) {
  RetainedKnowledge Result;
  if (!DebugCounter::shouldExecute(AssumeQueryCounter))
    return Result;

  Result.AttrKind = Attribute::getAttrKindFromName(BOI.Tag->getKey());
  if (bundleHasArgument(BOI, ABA_WasOn))
    Result.WasOn = getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn);
  auto GetArgOr = [&](unsigned Idx, uint64_t Default) -> uint64_t {
    if (auto *ConstInt = dyn_cast<ConstantInt>(
            getValueFromBundleOpInfo(Assume, BOI, ABA_Argument + Idx)))
      return ConstInt->getZExtValue();
    return Default;
  };
  if (BOI.End - BOI.Begin > ABA_Argument) {
    switch (Result.AttrKind) {
    case Attribute::Alignment:
      Result.ArgValue = GetArgOr(0, 1);
      break;
    case Attribute::Dereferenceable:
    case Attribute::DereferenceableOrNull:
      Result.ArgValue = GetArgOr(0, 0);
      break;
    case Attribute::None:
      Result.ArgValue = 0;
      break;
    default:
      llvm_unreachable("Attribute kind does not support argument");
    }
  }
  Result.IRArgValue = bundleHasArgument(BOI, ABA_Argument)
                          ? getValueFromBundleOpInfo(Assume, BOI, ABA_Argument)
                          : nullptr;
  if (Result.AttrKind == Attribute::Alignment)
    if (BOI.End - BOI.Begin > ABA_Argument + 1)
      Result.ArgValue = MinAlign(Result.ArgValue, GetArgOr(1, 1));
  return Result;
}

bool llvm::isAssumeWithEmptyBundle(const AssumeInst &Assume) {
  return none_of(Assume.bundle_op_infos(),
                 [](const CallBase::BundleOpInfo &BOI) {
                   return BOI.Tag->getKey() != IgnoreBundleTag;
                 });
}

static CallInst::BundleOpInfo *getBundleFromUse(const Use *U) {
  if (!match(U->getUser(),
             m_Intrinsic<Intrinsic::assume>(m_Unless(m_Specific(U->get())))))
    return nullptr;
  auto *Intr = cast<IntrinsicInst>(U->getUser());
  return &Intr->getBundleOpInfoForOperand(U->getOperandNo());
}

RetainedKnowledge
llvm::getKnowledgeFromUse(const Use *U,
                          ArrayRef<Attribute::AttrKind> AttrKinds) {
  CallInst::BundleOpInfo* Bundle = getBundleFromUse(U);
  if (!Bundle)
    return RetainedKnowledge::none();
  RetainedKnowledge RK =
      getKnowledgeFromBundle(*cast<AssumeInst>(U->getUser()), *Bundle);
  if (llvm::is_contained(AttrKinds, RK.AttrKind))
    return RK;
  return RetainedKnowledge::none();
}

RetainedKnowledge
llvm::getKnowledgeForValue(const Value *V,
                           ArrayRef<Attribute::AttrKind> AttrKinds,
                           AssumptionCache &AC,
                           function_ref<bool(RetainedKnowledge, Instruction *,
                                             const CallBase::BundleOpInfo *)>
                               Filter) {
  NumAssumeQueries++;
  for (AssumptionCache::ResultElem &Elem : AC.assumptionsFor(V)) {
    auto *II = cast_or_null<AssumeInst>(Elem.Assume);
    if (!II || Elem.Index == AssumptionCache::ExprResultIdx)
      continue;
    if (RetainedKnowledge RK = getKnowledgeFromBundle(
            *II, II->bundle_op_info_begin()[Elem.Index])) {
      if (V != RK.WasOn)
        continue;
      if (is_contained(AttrKinds, RK.AttrKind) &&
          Filter(RK, II, &II->bundle_op_info_begin()[Elem.Index])) {
        NumUsefullAssumeQueries++;
        return RK;
      }
    }
  }

  return RetainedKnowledge::none();
}

RetainedKnowledge llvm::getKnowledgeValidInContext(
    const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
    AssumptionCache &AC, const Instruction *CtxI, const DominatorTree *DT) {
  return getKnowledgeForValue(V, AttrKinds, AC,
                              [&](auto, Instruction *I, auto) {
                                return isValidAssumeForContext(I, CtxI, DT);
                              });
}