contrib/llvm-project/llvm/include/llvm/Analysis/AssumeBundleQueries.h

   1 //===- AssumeBundleQueries.h - utilities 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 // This file contain tools to query into assume bundles. assume bundles can be
  10 // built using utilities from Transform/Utils/AssumeBundleBuilder.h
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_TRANSFORMS_UTILS_ASSUMEBUNDLEQUERIES_H
  15 #define LLVM_TRANSFORMS_UTILS_ASSUMEBUNDLEQUERIES_H
  16
  17 #include "llvm/IR/Attributes.h"
  18 #include "llvm/IR/Instructions.h"
  19 #include "llvm/ADT/DenseMap.h"
  20
  21 namespace llvm {
  22 class IntrinsicInst;
  23 class AssumptionCache;
  24 class DominatorTree;
  25
  26 /// Index of elements in the operand bundle.
  27 /// If the element exist it is guaranteed to be what is specified in this enum
  28 /// but it may not exist.
  29 enum AssumeBundleArg {
  30   ABA_WasOn = 0,
  31   ABA_Argument = 1,
  32 };
  33
  34 /// Query the operand bundle of an llvm.assume to find a single attribute of
  35 /// the specified kind applied on a specified Value.
  36 ///
  37 /// This has a non-constant complexity. It should only be used when a single
  38 /// attribute is going to be queried.
  39 ///
  40 /// Return true iff the queried attribute was found.
  41 /// If ArgVal is set. the argument will be stored to ArgVal.
  42 bool hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn, StringRef AttrName,
  43                           uint64_t *ArgVal = nullptr);
  44 inline bool hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn,
  45                                  Attribute::AttrKind Kind,
  46                                  uint64_t *ArgVal = nullptr) {
  47   return hasAttributeInAssume(AssumeCI, IsOn,
  48                               Attribute::getNameFromAttrKind(Kind), ArgVal);
  49 }
  50
  51 template<> struct DenseMapInfo<Attribute::AttrKind> {
  52   static Attribute::AttrKind getEmptyKey() {
  53     return Attribute::EmptyKey;
  54   }
  55   static Attribute::AttrKind getTombstoneKey() {
  56     return Attribute::TombstoneKey;
  57   }
  58   static unsigned getHashValue(Attribute::AttrKind AK) {
  59     return hash_combine(AK);
  60   }
  61   static bool isEqual(Attribute::AttrKind LHS, Attribute::AttrKind RHS) {
  62     return LHS == RHS;
  63   }
  64 };
  65
  66 /// The map Key contains the Value on for which the attribute is valid and
  67 /// the Attribute that is valid for that value.
  68 /// If the Attribute is not on any value, the Value is nullptr.
  69 using RetainedKnowledgeKey = std::pair<Value *, Attribute::AttrKind>;
  70
  71 struct MinMax {
  72   unsigned Min;
  73   unsigned Max;
  74 };
  75
  76 /// A mapping from intrinsics (=`llvm.assume` calls) to a value range
  77 /// (=knowledge) that is encoded in them. How the value range is interpreted
  78 /// depends on the RetainedKnowledgeKey that was used to get this out of the
  79 /// RetainedKnowledgeMap.
  80 using Assume2KnowledgeMap = DenseMap<IntrinsicInst *, MinMax>;
  81
  82 using RetainedKnowledgeMap =
  83     DenseMap<RetainedKnowledgeKey, Assume2KnowledgeMap>;
  84
  85 /// Insert into the map all the informations contained in the operand bundles of
  86 /// the llvm.assume. This should be used instead of hasAttributeInAssume when
  87 /// many queries are going to be made on the same llvm.assume.
  88 /// String attributes are not inserted in the map.
  89 /// If the IR changes the map will be outdated.
  90 void fillMapFromAssume(CallInst &AssumeCI, RetainedKnowledgeMap &Result);
  91
  92 /// Represent one information held inside an operand bundle of an llvm.assume.
  93 /// AttrKind is the property that holds.
  94 /// WasOn if not null is that Value for which AttrKind holds.
  95 /// ArgValue is optionally an argument of the attribute.
  96 /// For example if we know that %P has an alignment of at least four:
  97 ///  - AttrKind will be Attribute::Alignment.
  98 ///  - WasOn will be %P.
  99 ///  - ArgValue will be 4.
 100 struct RetainedKnowledge {
 101   Attribute::AttrKind AttrKind = Attribute::None;
 102   unsigned ArgValue = 0;
 103   Value *WasOn = nullptr;
 104   bool operator==(RetainedKnowledge Other) const {
 105     return AttrKind == Other.AttrKind && WasOn == Other.WasOn &&
 106            ArgValue == Other.ArgValue;
 107   }
 108   bool operator!=(RetainedKnowledge Other) const { return !(*this == Other); }
 109   operator bool() const { return AttrKind != Attribute::None; }
 110   static RetainedKnowledge none() { return RetainedKnowledge{}; }
 111 };
 112
 113 /// Retreive the information help by Assume on the operand at index Idx.
 114 /// Assume should be an llvm.assume and Idx should be in the operand bundle.
 115 RetainedKnowledge getKnowledgeFromOperandInAssume(CallInst &Assume,
 116                                                   unsigned Idx);
 117
 118 /// Retreive the information help by the Use U of an llvm.assume. the use should
 119 /// be in the operand bundle.
 120 inline RetainedKnowledge getKnowledgeFromUseInAssume(const Use *U) {
 121   return getKnowledgeFromOperandInAssume(*cast<CallInst>(U->getUser()),
 122                                          U->getOperandNo());
 123 }
 124
 125 /// Tag in operand bundle indicating that this bundle should be ignored.
 126 constexpr StringRef IgnoreBundleTag = "ignore";
 127
 128 /// Return true iff the operand bundles of the provided llvm.assume doesn't
 129 /// contain any valuable information. This is true when:
 130 ///  - The operand bundle is empty
 131 ///  - The operand bundle only contains information about dropped values or
 132 ///    constant folded values.
 133 ///
 134 /// the argument to the call of llvm.assume may still be useful even if the
 135 /// function returned true.
 136 bool isAssumeWithEmptyBundle(CallInst &Assume);
 137
 138 /// Return a valid Knowledge associated to the Use U if its Attribute kind is
 139 /// in AttrKinds.
 140 RetainedKnowledge getKnowledgeFromUse(const Use *U,
 141                                       ArrayRef<Attribute::AttrKind> AttrKinds);
 142
 143 /// Return a valid Knowledge associated to the Value V if its Attribute kind is
 144 /// in AttrKinds and it matches the Filter.
 145 RetainedKnowledge getKnowledgeForValue(
 146     const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
 147     AssumptionCache *AC = nullptr,
 148     function_ref<bool(RetainedKnowledge, Instruction *,
 149                             const CallBase::BundleOpInfo *)>
 150         Filter = [](auto...) { return true; });
 151
 152 /// Return a valid Knowledge associated to the Value V if its Attribute kind is
 153 /// in AttrKinds and the knowledge is suitable to be used in the context of
 154 /// CtxI.
 155 RetainedKnowledge getKnowledgeValidInContext(
 156     const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
 157     const Instruction *CtxI, const DominatorTree *DT = nullptr,
 158     AssumptionCache *AC = nullptr);
 159
 160 /// This extracts the Knowledge from an element of an operand bundle.
 161 /// This is mostly for use in the assume builder.
 162 RetainedKnowledge getKnowledgeFromBundle(CallInst &Assume,
 163                                          const CallBase::BundleOpInfo &BOI);
 164
 165 } // namespace llvm
 166
 167 #endif