llvm/Analysis/AssumeBundleQueries.h

0001 //===- AssumeBundleQueries.h - utilis to query assume bundles ---*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file contain tools to query into assume bundles. assume bundles can be
0010 // built using utilities from Transform/Utils/AssumeBundleBuilder.h
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_ANALYSIS_ASSUMEBUNDLEQUERIES_H
0015 #define LLVM_ANALYSIS_ASSUMEBUNDLEQUERIES_H
0016
0017 #include "llvm/ADT/DenseMap.h"
0018 #include "llvm/IR/IntrinsicInst.h"
0019
0020 namespace llvm {
0021 class AssumptionCache;
0022 class DominatorTree;
0023 class Instruction;
0024
0025 /// Index of elements in the operand bundle.
0026 /// If the element exist it is guaranteed to be what is specified in this enum
0027 /// but it may not exist.
0028 enum AssumeBundleArg {
0029   ABA_WasOn = 0,
0030   ABA_Argument = 1,
0031 };
0032
0033 /// Query the operand bundle of an llvm.assume to find a single attribute of
0034 /// the specified kind applied on a specified Value.
0035 ///
0036 /// This has a non-constant complexity. It should only be used when a single
0037 /// attribute is going to be queried.
0038 ///
0039 /// Return true iff the queried attribute was found.
0040 /// If ArgVal is set. the argument will be stored to ArgVal.
0041 bool hasAttributeInAssume(AssumeInst &Assume, Value *IsOn, StringRef AttrName,
0042                           uint64_t *ArgVal = nullptr);
0043 inline bool hasAttributeInAssume(AssumeInst &Assume, Value *IsOn,
0044                                  Attribute::AttrKind Kind,
0045                                  uint64_t *ArgVal = nullptr) {
0046   return hasAttributeInAssume(Assume, IsOn,
0047                               Attribute::getNameFromAttrKind(Kind), ArgVal);
0048 }
0049
0050 template<> struct DenseMapInfo<Attribute::AttrKind> {
0051   static Attribute::AttrKind getEmptyKey() {
0052     return Attribute::EmptyKey;
0053   }
0054   static Attribute::AttrKind getTombstoneKey() {
0055     return Attribute::TombstoneKey;
0056   }
0057   static unsigned getHashValue(Attribute::AttrKind AK) {
0058     return hash_combine(AK);
0059   }
0060   static bool isEqual(Attribute::AttrKind LHS, Attribute::AttrKind RHS) {
0061     return LHS == RHS;
0062   }
0063 };
0064
0065 /// The map Key contains the Value on for which the attribute is valid and
0066 /// the Attribute that is valid for that value.
0067 /// If the Attribute is not on any value, the Value is nullptr.
0068 using RetainedKnowledgeKey = std::pair<Value *, Attribute::AttrKind>;
0069
0070 struct MinMax {
0071   uint64_t Min;
0072   uint64_t Max;
0073 };
0074
0075 /// A mapping from intrinsics (=`llvm.assume` calls) to a value range
0076 /// (=knowledge) that is encoded in them. How the value range is interpreted
0077 /// depends on the RetainedKnowledgeKey that was used to get this out of the
0078 /// RetainedKnowledgeMap.
0079 using Assume2KnowledgeMap = DenseMap<AssumeInst *, MinMax>;
0080
0081 using RetainedKnowledgeMap =
0082     DenseMap<RetainedKnowledgeKey, Assume2KnowledgeMap>;
0083
0084 /// Insert into the map all the informations contained in the operand bundles of
0085 /// the llvm.assume. This should be used instead of hasAttributeInAssume when
0086 /// many queries are going to be made on the same llvm.assume.
0087 /// String attributes are not inserted in the map.
0088 /// If the IR changes the map will be outdated.
0089 void fillMapFromAssume(AssumeInst &Assume, RetainedKnowledgeMap &Result);
0090
0091 /// Represent one information held inside an operand bundle of an llvm.assume.
0092 /// AttrKind is the property that holds.
0093 /// WasOn if not null is that Value for which AttrKind holds.
0094 /// ArgValue is optionally an argument of the attribute.
0095 /// For example if we know that %P has an alignment of at least four:
0096 ///  - AttrKind will be Attribute::Alignment.
0097 ///  - WasOn will be %P.
0098 ///  - ArgValue will be 4.
0099 struct RetainedKnowledge {
0100   Attribute::AttrKind AttrKind = Attribute::None;
0101   uint64_t ArgValue = 0;
0102   Value *WasOn = nullptr;
0103   bool operator==(RetainedKnowledge Other) const {
0104     return AttrKind == Other.AttrKind && WasOn == Other.WasOn &&
0105            ArgValue == Other.ArgValue;
0106   }
0107   bool operator!=(RetainedKnowledge Other) const { return !(*this == Other); }
0108   /// This is only intended for use in std::min/std::max between attribute that
0109   /// only differ in ArgValue.
0110   bool operator<(RetainedKnowledge Other) const {
0111     assert(((AttrKind == Other.AttrKind && WasOn == Other.WasOn) ||
0112             AttrKind == Attribute::None || Other.AttrKind == Attribute::None) &&
0113            "This is only intend for use in min/max to select the best for "
0114            "RetainedKnowledge that is otherwise equal");
0115     return ArgValue < Other.ArgValue;
0116   }
0117   operator bool() const { return AttrKind != Attribute::None; }
0118   static RetainedKnowledge none() { return RetainedKnowledge{}; }
0119 };
0120
0121 /// Retreive the information help by Assume on the operand at index Idx.
0122 /// Assume should be an llvm.assume and Idx should be in the operand bundle.
0123 RetainedKnowledge getKnowledgeFromOperandInAssume(AssumeInst &Assume,
0124                                                   unsigned Idx);
0125
0126 /// Retreive the information help by the Use U of an llvm.assume. the use should
0127 /// be in the operand bundle.
0128 inline RetainedKnowledge getKnowledgeFromUseInAssume(const Use *U) {
0129   return getKnowledgeFromOperandInAssume(*cast<AssumeInst>(U->getUser()),
0130                                          U->getOperandNo());
0131 }
0132
0133 /// Tag in operand bundle indicating that this bundle should be ignored.
0134 constexpr StringRef IgnoreBundleTag = "ignore";
0135
0136 /// Return true iff the operand bundles of the provided llvm.assume doesn't
0137 /// contain any valuable information. This is true when:
0138 ///  - The operand bundle is empty
0139 ///  - The operand bundle only contains information about dropped values or
0140 ///    constant folded values.
0141 ///
0142 /// the argument to the call of llvm.assume may still be useful even if the
0143 /// function returned true.
0144 bool isAssumeWithEmptyBundle(const AssumeInst &Assume);
0145
0146 /// Return a valid Knowledge associated to the Use U if its Attribute kind is
0147 /// in AttrKinds.
0148 RetainedKnowledge getKnowledgeFromUse(const Use *U,
0149                                       ArrayRef<Attribute::AttrKind> AttrKinds);
0150
0151 /// Return a valid Knowledge associated to the Value V if its Attribute kind is
0152 /// in AttrKinds and it matches the Filter.
0153 RetainedKnowledge getKnowledgeForValue(
0154     const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
0155     AssumptionCache *AC = nullptr,
0156     function_ref<bool(RetainedKnowledge, Instruction *,
0157                             const CallBase::BundleOpInfo *)>
0158         Filter = [](auto...) { return true; });
0159
0160 /// Return a valid Knowledge associated to the Value V if its Attribute kind is
0161 /// in AttrKinds and the knowledge is suitable to be used in the context of
0162 /// CtxI.
0163 RetainedKnowledge getKnowledgeValidInContext(
0164     const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
0165     const Instruction *CtxI, const DominatorTree *DT = nullptr,
0166     AssumptionCache *AC = nullptr);
0167
0168 /// This extracts the Knowledge from an element of an operand bundle.
0169 /// This is mostly for use in the assume builder.
0170 RetainedKnowledge getKnowledgeFromBundle(AssumeInst &Assume,
0171                                          const CallBase::BundleOpInfo &BOI);
0172
0173 } // namespace llvm
0174
0175 #endif