195 lines · 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-exception6//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 21using namespace llvm;22using namespace llvm::PatternMatch;23 24STATISTIC(NumAssumeQueries, "Number of Queries into an assume assume bundles");25STATISTIC(26 NumUsefullAssumeQueries,27 "Number of Queries into an assume assume bundles that were satisfied");28 29DEBUG_COUNTER(AssumeQueryCounter, "assume-queries-counter",30 "Controls which assumes gets created");31 32static bool bundleHasArgument(const CallBase::BundleOpInfo &BOI, unsigned Idx) {33 return BOI.End - BOI.Begin > Idx;34}35 36static 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 43bool 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 70void 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 [It, Inserted] = Result[Key].try_emplace(&Assume);89 if (Inserted) {90 It->second = {Val, Val};91 continue;92 }93 auto &MinMax = It->second;94 MinMax.Min = std::min(Val, MinMax.Min);95 MinMax.Max = std::max(Val, MinMax.Max);96 }97}98 99RetainedKnowledge100llvm::getKnowledgeFromBundle(AssumeInst &Assume,101 const CallBase::BundleOpInfo &BOI) {102 RetainedKnowledge Result;103 if (!DebugCounter::shouldExecute(AssumeQueryCounter))104 return Result;105 106 Result.AttrKind = Attribute::getAttrKindFromName(BOI.Tag->getKey());107 if (bundleHasArgument(BOI, ABA_WasOn))108 Result.WasOn = getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn);109 auto GetArgOr1 = [&](unsigned Idx) -> uint64_t {110 if (auto *ConstInt = dyn_cast<ConstantInt>(111 getValueFromBundleOpInfo(Assume, BOI, ABA_Argument + Idx)))112 return ConstInt->getZExtValue();113 return 1;114 };115 if (BOI.End - BOI.Begin > ABA_Argument)116 Result.ArgValue = GetArgOr1(0);117 Result.IRArgValue = bundleHasArgument(BOI, ABA_Argument)118 ? getValueFromBundleOpInfo(Assume, BOI, ABA_Argument)119 : nullptr;120 if (Result.AttrKind == Attribute::Alignment)121 if (BOI.End - BOI.Begin > ABA_Argument + 1)122 Result.ArgValue = MinAlign(Result.ArgValue, GetArgOr1(1));123 return Result;124}125 126RetainedKnowledge llvm::getKnowledgeFromOperandInAssume(AssumeInst &Assume,127 unsigned Idx) {128 CallBase::BundleOpInfo BOI = Assume.getBundleOpInfoForOperand(Idx);129 return getKnowledgeFromBundle(Assume, BOI);130}131 132bool llvm::isAssumeWithEmptyBundle(const AssumeInst &Assume) {133 return none_of(Assume.bundle_op_infos(),134 [](const CallBase::BundleOpInfo &BOI) {135 return BOI.Tag->getKey() != IgnoreBundleTag;136 });137}138 139static CallInst::BundleOpInfo *getBundleFromUse(const Use *U) {140 if (!match(U->getUser(),141 m_Intrinsic<Intrinsic::assume>(m_Unless(m_Specific(U->get())))))142 return nullptr;143 auto *Intr = cast<IntrinsicInst>(U->getUser());144 return &Intr->getBundleOpInfoForOperand(U->getOperandNo());145}146 147RetainedKnowledge148llvm::getKnowledgeFromUse(const Use *U,149 ArrayRef<Attribute::AttrKind> AttrKinds) {150 CallInst::BundleOpInfo* Bundle = getBundleFromUse(U);151 if (!Bundle)152 return RetainedKnowledge::none();153 RetainedKnowledge RK =154 getKnowledgeFromBundle(*cast<AssumeInst>(U->getUser()), *Bundle);155 if (llvm::is_contained(AttrKinds, RK.AttrKind))156 return RK;157 return RetainedKnowledge::none();158}159 160RetainedKnowledge161llvm::getKnowledgeForValue(const Value *V,162 ArrayRef<Attribute::AttrKind> AttrKinds,163 AssumptionCache &AC,164 function_ref<bool(RetainedKnowledge, Instruction *,165 const CallBase::BundleOpInfo *)>166 Filter) {167 NumAssumeQueries++;168 for (AssumptionCache::ResultElem &Elem : AC.assumptionsFor(V)) {169 auto *II = cast_or_null<AssumeInst>(Elem.Assume);170 if (!II || Elem.Index == AssumptionCache::ExprResultIdx)171 continue;172 if (RetainedKnowledge RK = getKnowledgeFromBundle(173 *II, II->bundle_op_info_begin()[Elem.Index])) {174 if (V != RK.WasOn)175 continue;176 if (is_contained(AttrKinds, RK.AttrKind) &&177 Filter(RK, II, &II->bundle_op_info_begin()[Elem.Index])) {178 NumUsefullAssumeQueries++;179 return RK;180 }181 }182 }183 184 return RetainedKnowledge::none();185}186 187RetainedKnowledge llvm::getKnowledgeValidInContext(188 const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,189 AssumptionCache &AC, const Instruction *CtxI, const DominatorTree *DT) {190 return getKnowledgeForValue(V, AttrKinds, AC,191 [&](auto, Instruction *I, auto) {192 return isValidAssumeForContext(I, CtxI, DT);193 });194}195