[InstructionCost] Add saturation support.

[sdesmalen]

Summary

This patch makes the operations on InstructionCost saturate, so that when
costs are accumulated they saturate to <max value>.

One of the compelling reasons for wanting to have saturation support
is because in various places, arbitrary values are used to represent
a 'high' cost, but when accumulating the cost of some set of operations
or a loop, overflow is not taken into account, which may lead to unexpected
results. By defining the operations to saturate, we can express the cost
of something 'very expensive' as InstructionCost::getMax().

[kparzysz]

Should the max/min values be treated as infinity? With this implementation, (max+1)-1 = max-1. Is that what we want?

[dmgreen]

Looking at the documentation of invalid costs, it says

/// These states can currently be used to indicate whether a cost is valid or
/// invalid. Examples of an invalid cost might be where the cost is
/// prohibitively expensive and the user wants to prevent certain
/// optimizations being performed. Or perhaps the cost is simply unknown
/// because the operation makes no sense in certain circumstances. These
/// states can be expanded in future to support other cases if necessary.

Do we have any examples of "Or perhaps the cost is simply unknown because the operation makes no sense in certain circumstances"? Where it wouldn't mean the same as an infinite cost.

[sdesmalen]

In D105108#2847011, @kparzysz wrote:

Should the max/min values be treated as infinity? With this implementation, (max+1)-1 = max-1. Is that what we want?

Yes. It wasn't really the intention of this patch to implement a proper 'infinity', because that makes things a lot more complicated (e.g. having to define what "0 * infinity" means). Simple saturation arithmetic is sufficient for practical uses of InstructionCost which are often about accumulating (possibly scaled) costs, where currently wrapping may occur if large numbers are used.

[sdesmalen]

In D105108#2847068, @dmgreen wrote:

Looking at the documentation of invalid costs, it says

/// These states can currently be used to indicate whether a cost is valid or
/// invalid. Examples of an invalid cost might be where the cost is
/// prohibitively expensive and the user wants to prevent certain
/// optimizations being performed. Or perhaps the cost is simply unknown
/// because the operation makes no sense in certain circumstances. These
/// states can be expanded in future to support other cases if necessary.

Do we have any examples of "Or perhaps the cost is simply unknown because the operation makes no sense in certain circumstances"? Where it wouldn't mean the same as an infinite cost.

If the IR has an operation with Invalid cost that would be considered a bug. That's because Invalid represents that an operation has no cost because it cannot be code-generated. If the cost is <very high>, that's fine although it suggests very inefficient. The former (Invalid) is true for scalable-vector operations that are not natively supported by the target and can only be lowered by scalarizing. SelectionDAG currently has no mechanism to do that, so any operation that requires scalarizing is considered to have an Invalid cost. Types like <vscale x 1 x i128> would be such an example for AArch64 SVE.

[kparzysz]

If hitting either one of the saturation boundaries was realistic enough to warrant this change, then why having both, large positive and large negative costs wouldn't be? If cost1 > 0 and cost2 < 0, and they both exceed the bounds, then cost1+cost2 in the saturating arithmetic may be a finite number, reasonably close to 0, and yet completely meaningless.

Edit: clarified the saturated arithmetic

[dmgreen]

Do we have any examples of "Or perhaps the cost is simply unknown because the operation makes no sense in certain circumstances"? Where it wouldn't mean the same as an infinite cost.

If the IR has an operation with Invalid cost that would be considered a bug. That's because Invalid represents that an operation has no cost because it cannot be code-generated. If the cost is <very high>, that's fine although it suggests very inefficient. The former (Invalid) is true for scalable-vector operations that are not natively supported by the target and can only be lowered by scalarizing. SelectionDAG currently has no mechanism to do that, so any operation that requires scalarizing is considered to have an Invalid cost. Types like <vscale x 1 x i128> would be such an example for AArch64 SVE.

OK that matches my expectation of an invalid cost. Synonymous with an infinite cost. It's not intended for something with a high cost, or something that we just haven't bothered to assign a cost to.
It may be worth updating the documentation to be more explicit about that, if we don't have any other ways we generate "invalid" costs.

As for this patch, I have no objections to adding saturation, but would not usually expect them to get that high (especially if the underlying type is an i64), except for some of the place in the vectorizer where we are multiplying by max tripcounts.

[sdesmalen]

In D105108#2848042, @kparzysz wrote:

If hitting either one of the saturation boundaries was realistic enough to warrant this change, then why having both, large positive and large negative costs wouldn't be? If cost1 > 0 and cost2 < 0, and they both exceed the bounds, then cost1+cost2 in the saturating arithmetic may be a finite number, reasonably close to 0, and yet completely meaningless.

Edit: clarified the saturated arithmetic

You're right that if values are both positive and negative that the resulting value is meaningless if these values are both exceeding their bounds. It's not the common use-case though, since most places just accumulate costs and expect all instruction costs to be positive values (the same holds for places that subtract (all positive) costs from some budget). I think the only exception is the SLPVectorizer, which does both addition/subtraction.

One the motivations for this patch was the overflow in the LoopVectorizer when applying D105113. This tries to implement the cost-comparison on InstructionCost, rather than doing it on InstructionCost::CostTy and then extending the values to int64_t before multiplication. The starting cost is set to std::numeric_limits<InstructionCost::CostTy>::max() which when multiplied by the vector element-count overflows. This could practically be resolved by setting that value to some lower value, but there may be other places where multiplication with e.g. MaxTripCounts could lead to overflow.

The common case for InstructionCost is asking "what is the cost of <operation> or <set of operations>?", which should always be a positive number. Conceptually it makes little sense to have negative costs to begin with, so at some point I'd like to see InstructionCost become unsigned to avoid such complications. Perhaps a feasible route would be to make InstructionCost unsigned and saturating by default and have a separate SignedWrappingInstructionCost class for any exceptions where signedness and wrapping may be required? If so, that would be a bigger piece of work than what this patch tried to achieve.

[kparzysz]

Sounds good to me.

[sdesmalen]

Updated comments to clarify meaning of Invalid vs high-but-valid costs.

[dmgreen]

Thanks for updating the wording. Sounds good to me

llvm/include/llvm/Support/InstructionCost.h

 //===- InstructionCost.h ----------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 /// \file
 /// This file defines an InstructionCost class that is used when calculating
 /// the cost of an instruction, or a group of instructions. In addition to a
 /// numeric value representing the cost the class also contains a state that
-/// can be used to encode particular properties, i.e. a cost being invalid or
-/// unknown.
+/// can be used to encode particular properties, such as a cost being invalid.
+/// Operations on InstructionCost implement saturation arithmetic, so that
+/// accumulating costs on large cost-values don't overflow.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_INSTRUCTIONCOST_H
 #define LLVM_SUPPORT_INSTRUCTIONCOST_H
 
 #include "llvm/ADT/Optional.h"
+#include "llvm/Support/MathExtras.h"
+#include <limits>
 
 namespace llvm {
 
 class raw_ostream;
 
 class InstructionCost {
 public:
   using CostType = int;
 
-  /// These states can currently be used to indicate whether a cost is valid or
-  /// invalid. Examples of an invalid cost might be where the cost is
-  /// prohibitively expensive and the user wants to prevent certain
-  /// optimizations being performed. Or perhaps the cost is simply unknown
-  /// because the operation makes no sense in certain circumstances. These
-  /// states can be expanded in future to support other cases if necessary.
-  enum CostState { Valid, Invalid };
+  /// CostState describes the state of a cost.
+  enum CostState {
+    Valid,  /// < The cost value represents a valid cost, even when the
+            /// cost-value is large.
+    Invalid /// < Invalid indicates there is no way to represent the cost as a
+            /// numeric value. This state exists to represent a possible issue,
+            /// e.g. if the cost-model knows the operation cannot be expanded
+            /// into a valid code-sequence by the code-generator.  While some
+            /// passes may assert that the calculated cost must be valid, it is
+            /// up to individual passes how to interpret an Invalid cost. For
+            /// example, a transformation pass could choose not to perform a
+            /// transformation if the resulting cost would end up Invalid.
+            /// Because some passes may assert a cost is Valid, it is not
+            /// recommended to use Invalid costs to model 'Unknown'.
+            /// Note that Invalid is semantically different from a (very) high,
+            /// but valid cost, which intentionally indicates no issue, but
+            /// rather a strong preference not to select a certain operation.
+  };
 
 private:
   CostType Value = 0;
   CostState State = Valid;
 
   void propagateState(const InstructionCost &RHS) {
     if (RHS.State == Invalid)
       State = Invalid;
   }
 
+  static CostType getMaxValue() { return std::numeric_limits<CostType>::max(); }
+  static CostType getMinValue() { return std::numeric_limits<CostType>::min(); }
+
 public:
   // A default constructed InstructionCost is a valid zero cost
   InstructionCost() = default;
 
   InstructionCost(CostState) = delete;
   InstructionCost(CostType Val) : Value(Val), State(Valid) {}
 
+  static InstructionCost getMax() { return getMaxValue(); }
+  static InstructionCost getMin() { return getMinValue(); }
   static InstructionCost getInvalid(CostType Val = 0) {
     InstructionCost Tmp(Val);
     Tmp.setInvalid();
     return Tmp;
   }
 
   bool isValid() const { return State == Valid; }
   void setValid() { State = Valid; }
   void setInvalid() { State = Invalid; }
   CostState getState() const { return State; }
 
   /// This function is intended to be used as sparingly as possible, since the
   /// class provides the full range of operator support required for arithmetic
   /// and comparisons.
   Optional<CostType> getValue() const {
     if (isValid())
       return Value;
     return None;
   }
 
   /// For all of the arithmetic operators provided here any invalid state is
   /// perpetuated and cannot be removed. Once a cost becomes invalid it stays
-  /// invalid, and it also inherits any invalid state from the RHS. Regardless
-  /// of the state, arithmetic work on the actual values in the same way as they
-  /// would on a basic type, such as integer.
+  /// invalid, and it also inherits any invalid state from the RHS.
+  /// Arithmetic work on the actual values is implemented with saturation,
+  /// to avoid overflow when using more extreme cost values.
 
   InstructionCost &operator+=(const InstructionCost &RHS) {
     propagateState(RHS);
-    Value += RHS.Value;
+
+    // Saturating addition.
+    InstructionCost::CostType Result;
+    if (AddOverflow(Value, RHS.Value, Result))
+      Result = RHS.Value > 0 ? getMaxValue() : getMinValue();
+
+    Value = Result;
     return *this;
   }
 
   InstructionCost &operator+=(const CostType RHS) {
     InstructionCost RHS2(RHS);
     *this += RHS2;
     return *this;
   }
 
   InstructionCost &operator-=(const InstructionCost &RHS) {
     propagateState(RHS);
-    Value -= RHS.Value;
+
+    // Saturating subtract.
+    InstructionCost::CostType Result;
+    if (SubOverflow(Value, RHS.Value, Result))
+      Result = RHS.Value > 0 ? getMinValue() : getMaxValue();
+    Value = Result;
     return *this;
   }
 
   InstructionCost &operator-=(const CostType RHS) {
     InstructionCost RHS2(RHS);
     *this -= RHS2;
     return *this;
   }
 
   InstructionCost &operator*=(const InstructionCost &RHS) {
     propagateState(RHS);
-    Value *= RHS.Value;
+
+    // Saturating multiply.
+    InstructionCost::CostType Result;
+    if (MulOverflow(Value, RHS.Value, Result)) {
+      if ((Value > 0 && RHS.Value > 0) || (Value < 0 && RHS.Value < 0))
+        Result = getMaxValue();
+      else
+        Result = getMinValue();
+    }
+
+    Value = Result;
     return *this;
   }
 
   InstructionCost &operator*=(const CostType RHS) {
     InstructionCost RHS2(RHS);
     *this *= RHS2;
     return *this;
   }

llvm/unittests/Support/InstructionCostTest.cpp

 //===- InstructionCostTest.cpp - InstructionCost tests --------------------===//
 //
 // 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/Support/InstructionCost.h"
 #include "gtest/gtest.h"
+#include <limits>
 
 using namespace llvm;
 
 namespace {
 
 struct CostTest : public testing::Test {
   CostTest() {}
 };
TEST_F(CostTest, Operators) {
   EXPECT_FALSE(TmpCost.isValid());
 
   // Test value extraction
   EXPECT_EQ(*(VThree.getValue()), 3);
   EXPECT_EQ(IThreeA.getValue(), None);
 
   EXPECT_EQ(std::min(VThree, VNegTwo), -2);
   EXPECT_EQ(std::max(VThree, VSix), 6);
+
+  // Test saturation
+  auto Max = InstructionCost::getMax();
+  auto Min = InstructionCost::getMin();
+  auto MinusOne = InstructionCost(-1);
+  auto MinusTwo = InstructionCost(-2);
+  auto One = InstructionCost(1);
+  auto Two = InstructionCost(2);
+  EXPECT_EQ(Max + One, Max);
+  EXPECT_EQ(Min + MinusOne, Min);
+  EXPECT_EQ(Min - One, Min);
+  EXPECT_EQ(Max - MinusOne, Max);
+  EXPECT_EQ(Max * Two, Max);
+  EXPECT_EQ(Min * Two, Min);
+  EXPECT_EQ(Max * MinusTwo, Min);
+  EXPECT_EQ(Min * MinusTwo, Max);
 }