llvm/Support/InstructionCost.h

0001 //===- InstructionCost.h ----------------------------------------*- 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 /// \file
0009 /// This file defines an InstructionCost class that is used when calculating
0010 /// the cost of an instruction, or a group of instructions. In addition to a
0011 /// numeric value representing the cost the class also contains a state that
0012 /// can be used to encode particular properties, such as a cost being invalid.
0013 /// Operations on InstructionCost implement saturation arithmetic, so that
0014 /// accumulating costs on large cost-values don't overflow.
0015 ///
0016 //===----------------------------------------------------------------------===//
0017
0018 #ifndef LLVM_SUPPORT_INSTRUCTIONCOST_H
0019 #define LLVM_SUPPORT_INSTRUCTIONCOST_H
0020
0021 #include "llvm/Support/MathExtras.h"
0022 #include <limits>
0023 #include <optional>
0024
0025 namespace llvm {
0026
0027 class raw_ostream;
0028
0029 class InstructionCost {
0030 public:
0031   using CostType = int64_t;
0032
0033   /// CostState describes the state of a cost.
0034   enum CostState {
0035     Valid,  /// < The cost value represents a valid cost, even when the
0036             /// cost-value is large.
0037     Invalid /// < Invalid indicates there is no way to represent the cost as a
0038             /// numeric value. This state exists to represent a possible issue,
0039             /// e.g. if the cost-model knows the operation cannot be expanded
0040             /// into a valid code-sequence by the code-generator.  While some
0041             /// passes may assert that the calculated cost must be valid, it is
0042             /// up to individual passes how to interpret an Invalid cost. For
0043             /// example, a transformation pass could choose not to perform a
0044             /// transformation if the resulting cost would end up Invalid.
0045             /// Because some passes may assert a cost is Valid, it is not
0046             /// recommended to use Invalid costs to model 'Unknown'.
0047             /// Note that Invalid is semantically different from a (very) high,
0048             /// but valid cost, which intentionally indicates no issue, but
0049             /// rather a strong preference not to select a certain operation.
0050   };
0051
0052 private:
0053   CostType Value = 0;
0054   CostState State = Valid;
0055
0056   void propagateState(const InstructionCost &RHS) {
0057     if (RHS.State == Invalid)
0058       State = Invalid;
0059   }
0060
0061   static CostType getMaxValue() { return std::numeric_limits<CostType>::max(); }
0062   static CostType getMinValue() { return std::numeric_limits<CostType>::min(); }
0063
0064 public:
0065   // A default constructed InstructionCost is a valid zero cost
0066   InstructionCost() = default;
0067
0068   InstructionCost(CostState) = delete;
0069   InstructionCost(CostType Val) : Value(Val), State(Valid) {}
0070
0071   static InstructionCost getMax() { return getMaxValue(); }
0072   static InstructionCost getMin() { return getMinValue(); }
0073   static InstructionCost getInvalid(CostType Val = 0) {
0074     InstructionCost Tmp(Val);
0075     Tmp.setInvalid();
0076     return Tmp;
0077   }
0078
0079   bool isValid() const { return State == Valid; }
0080   void setValid() { State = Valid; }
0081   void setInvalid() { State = Invalid; }
0082   CostState getState() const { return State; }
0083
0084   /// This function is intended to be used as sparingly as possible, since the
0085   /// class provides the full range of operator support required for arithmetic
0086   /// and comparisons.
0087   std::optional<CostType> getValue() const {
0088     if (isValid())
0089       return Value;
0090     return std::nullopt;
0091   }
0092
0093   /// For all of the arithmetic operators provided here any invalid state is
0094   /// perpetuated and cannot be removed. Once a cost becomes invalid it stays
0095   /// invalid, and it also inherits any invalid state from the RHS.
0096   /// Arithmetic work on the actual values is implemented with saturation,
0097   /// to avoid overflow when using more extreme cost values.
0098
0099   InstructionCost &operator+=(const InstructionCost &RHS) {
0100     propagateState(RHS);
0101
0102     // Saturating addition.
0103     InstructionCost::CostType Result;
0104     if (AddOverflow(Value, RHS.Value, Result))
0105       Result = RHS.Value > 0 ? getMaxValue() : getMinValue();
0106
0107     Value = Result;
0108     return *this;
0109   }
0110
0111   InstructionCost &operator+=(const CostType RHS) {
0112     InstructionCost RHS2(RHS);
0113     *this += RHS2;
0114     return *this;
0115   }
0116
0117   InstructionCost &operator-=(const InstructionCost &RHS) {
0118     propagateState(RHS);
0119
0120     // Saturating subtract.
0121     InstructionCost::CostType Result;
0122     if (SubOverflow(Value, RHS.Value, Result))
0123       Result = RHS.Value > 0 ? getMinValue() : getMaxValue();
0124     Value = Result;
0125     return *this;
0126   }
0127
0128   InstructionCost &operator-=(const CostType RHS) {
0129     InstructionCost RHS2(RHS);
0130     *this -= RHS2;
0131     return *this;
0132   }
0133
0134   InstructionCost &operator*=(const InstructionCost &RHS) {
0135     propagateState(RHS);
0136
0137     // Saturating multiply.
0138     InstructionCost::CostType Result;
0139     if (MulOverflow(Value, RHS.Value, Result)) {
0140       if ((Value > 0 && RHS.Value > 0) || (Value < 0 && RHS.Value < 0))
0141         Result = getMaxValue();
0142       else
0143         Result = getMinValue();
0144     }
0145
0146     Value = Result;
0147     return *this;
0148   }
0149
0150   InstructionCost &operator*=(const CostType RHS) {
0151     InstructionCost RHS2(RHS);
0152     *this *= RHS2;
0153     return *this;
0154   }
0155
0156   InstructionCost &operator/=(const InstructionCost &RHS) {
0157     propagateState(RHS);
0158     Value /= RHS.Value;
0159     return *this;
0160   }
0161
0162   InstructionCost &operator/=(const CostType RHS) {
0163     InstructionCost RHS2(RHS);
0164     *this /= RHS2;
0165     return *this;
0166   }
0167
0168   InstructionCost &operator++() {
0169     *this += 1;
0170     return *this;
0171   }
0172
0173   InstructionCost operator++(int) {
0174     InstructionCost Copy = *this;
0175     ++*this;
0176     return Copy;
0177   }
0178
0179   InstructionCost &operator--() {
0180     *this -= 1;
0181     return *this;
0182   }
0183
0184   InstructionCost operator--(int) {
0185     InstructionCost Copy = *this;
0186     --*this;
0187     return Copy;
0188   }
0189
0190   /// For the comparison operators we have chosen to use lexicographical
0191   /// ordering where valid costs are always considered to be less than invalid
0192   /// costs. This avoids having to add asserts to the comparison operators that
0193   /// the states are valid and users can test for validity of the cost
0194   /// explicitly.
0195   bool operator<(const InstructionCost &RHS) const {
0196     if (State != RHS.State)
0197       return State < RHS.State;
0198     return Value < RHS.Value;
0199   }
0200
0201   bool operator==(const InstructionCost &RHS) const {
0202     return State == RHS.State && Value == RHS.Value;
0203   }
0204
0205   bool operator!=(const InstructionCost &RHS) const { return !(*this == RHS); }
0206
0207   bool operator==(const CostType RHS) const {
0208     InstructionCost RHS2(RHS);
0209     return *this == RHS2;
0210   }
0211
0212   bool operator!=(const CostType RHS) const { return !(*this == RHS); }
0213
0214   bool operator>(const InstructionCost &RHS) const { return RHS < *this; }
0215
0216   bool operator<=(const InstructionCost &RHS) const { return !(RHS < *this); }
0217
0218   bool operator>=(const InstructionCost &RHS) const { return !(*this < RHS); }
0219
0220   bool operator<(const CostType RHS) const {
0221     InstructionCost RHS2(RHS);
0222     return *this < RHS2;
0223   }
0224
0225   bool operator>(const CostType RHS) const {
0226     InstructionCost RHS2(RHS);
0227     return *this > RHS2;
0228   }
0229
0230   bool operator<=(const CostType RHS) const {
0231     InstructionCost RHS2(RHS);
0232     return *this <= RHS2;
0233   }
0234
0235   bool operator>=(const CostType RHS) const {
0236     InstructionCost RHS2(RHS);
0237     return *this >= RHS2;
0238   }
0239
0240   void print(raw_ostream &OS) const;
0241
0242   template <class Function>
0243   auto map(const Function &F) const -> InstructionCost {
0244     if (isValid())
0245       return F(Value);
0246     return getInvalid();
0247   }
0248 };
0249
0250 inline InstructionCost operator+(const InstructionCost &LHS,
0251                                  const InstructionCost &RHS) {
0252   InstructionCost LHS2(LHS);
0253   LHS2 += RHS;
0254   return LHS2;
0255 }
0256
0257 inline InstructionCost operator-(const InstructionCost &LHS,
0258                                  const InstructionCost &RHS) {
0259   InstructionCost LHS2(LHS);
0260   LHS2 -= RHS;
0261   return LHS2;
0262 }
0263
0264 inline InstructionCost operator*(const InstructionCost &LHS,
0265                                  const InstructionCost &RHS) {
0266   InstructionCost LHS2(LHS);
0267   LHS2 *= RHS;
0268   return LHS2;
0269 }
0270
0271 inline InstructionCost operator/(const InstructionCost &LHS,
0272                                  const InstructionCost &RHS) {
0273   InstructionCost LHS2(LHS);
0274   LHS2 /= RHS;
0275   return LHS2;
0276 }
0277
0278 inline raw_ostream &operator<<(raw_ostream &OS, const InstructionCost &V) {
0279   V.print(OS);
0280   return OS;
0281 }
0282
0283 } // namespace llvm
0284
0285 #endif