Ensure that InstructionCost actually implements a total ordering

[ctetreau]

Summary

Previously, operator== would consider the actual equality of the pairs
(lhs.Value, lhs.State) == (rhs.Value, rhs.State). However, if an invalid
cost was involved in a call to operator<, only the state would be
compared. Thus, it was not the case that ({2, Invalid} < {3, Invalid} ||
{2, Invalid} > {3, Invalid} || {2, Invalid} == {3, Invalid}).

This patch implements a true total ordering, where cost state is
considered first, then value. While it's not really imporant that
{2, Invalid} be considered to be less than {3, Invalid}, it's not a
problem either. This patch also implements operator== in terms of
operator<, so the two definitions will be kept in sync.

[sdesmalen]

Thanks for fixing this @ctetreau, I guess this becomes more important when InstructionCosts are used in sets that rely on a total ordering in order to get bit-reproducability between builds.
Just added a few nits, but looks fine to me otherwise.

llvm/include/llvm/Support/InstructionCost.h

151

nit: s/ / to /

154–157

nit: return State < RHS.State || Value < RHS.Value; ?

161

nit: Is it worth adding a comment why this is implement in such an unusual way, so that the reason for that doesn't get lost in the future (it is mentioned in the commit message, but that's easily ignored)

llvm/unittests/Support/InstructionCostTest.cpp

45

Is there value in this test, if all three subexpressions have their expected value tested below?

[ctetreau]

llvm/unittests/Support/InstructionCostTest.cpp

45

I left this test here because this is "the" failure. The next three lines just test the specific implementation that we have today, but if 42 fails then that means that there is not a total ordering of any sort.

[ctetreau]

address code review issues

[ctetreau]

llvm/unittests/Support/InstructionCostTest.cpp

45

I guess the value is pretty low (and this isn't even correct, we'd need 4 comparisons to ensure that exactly one of those returns true)

[sdesmalen]

Thanks for the changes, LGTM!

[ctetreau]

Unfortunately, this breaks the build. Apparently several crashes and test failures result from this with the expensive checks. Unfortunately, things are very busy at work, so I don't have time to look into this for the time being.

[ctetreau]

A reasonable way ahead would be to just take the change to operator==, but not the change to operator<. We could explicitly codify "all invalid costs are considered to be equal", and this would basically be equivalent to Optional<int>.

[nikic]

FWIW, this patch also made the compiler non-deterministic in a major way.

llvm/include/llvm/Support/InstructionCost.h

155

Shouldn't this be?

if (State != RHS.State)
  return State < RHS.State;
return Value < RHS.Value;

If State is Invalid and RHS.State is Valid, then the Value comparison shouldn't be coming into it. (I assume the Value is not even initialized in that case, which is why this patch caused major compiler non-determinism.)

[ctetreau]

llvm/include/llvm/Support/InstructionCost.h

155

Ugh, yeah, I believe you are correct. With this definition, (invalid, 10) < (valid, 5) ==> true

I believe the value is always initialized, so this should be deterministic. It just gives the wrong answer.

[ctetreau]

Fix operator<

[ctetreau]

llvm/unittests/Support/InstructionCostTest.cpp

38

This test catches the previous bug

[ctetreau]

I just checked that this passes the expensive checks on my machine, so I think it should be good to go now.

[sdesmalen]

llvm/include/llvm/Support/InstructionCost.h

39–40

Would it be an idea to explicitly initialize these values with 0 and Valid, respectively?

[ctetreau]

address code review issues

[sdesmalen]

Thanks @ctetreau!

[ctetreau]

Fix test, add comment

llvm/include/llvm/Support/InstructionCost.h

39–40

Sure, why not? I went ahead and added a test for this so (0, Valid) is the official behavior of the default constructor.

[sdesmalen]

llvm/unittests/Support/InstructionCostTest.cpp

25

is there a reason you're preferring ASSERT over EXPECT in this test, and not the one below (getValue() == 0). I would think EXPECT is sufficient.

[ctetreau]

llvm/unittests/Support/InstructionCostTest.cpp

25

if the DefaultCost is invalid, then the dereference of the getValue below will cause a crash, preventing the rest of the tests from running.

If I change the default to Invalid then run the test:

with ASSERT_TRUE:

[----------] 2 tests from CostTest
[ RUN      ] CostTest.DefaultCtor
[redacted]\llvm\unittests\Support\InstructionCostTest.cpp(25): error: Value of: DefaultCost.isValid()
  Actual: false
Expected: true
[  FAILED  ] CostTest.DefaultCtor (1 ms)
[ RUN      ] CostTest.Operators
[       OK ] CostTest.Operators (0 ms)
[----------] 2 tests from CostTest (3 ms total)

with EXPECT_TRUE:

[----------] 2 tests from CostTest
[ RUN      ] CostTest.DefaultCtor
[redacted]\llvm\unittests\Support\InstructionCostTest.cpp(25): error: Value of: DefaultCost.isValid()
  Actual: false
Expected: true
Assertion failed: hasVal, file [redacted]\llvm\include\llvm/ADT/Optional.h, line 197

[sdesmalen]

llvm/unittests/Support/InstructionCostTest.cpp

25

Thanks for explaining, I didn't realise that was how ASSERT_TRUE worked.

[ctetreau]

the reland has landed

llvm/include/llvm/Support/InstructionCost.h

public:
   /// 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 };
 
 private:
   CostType Value;
   CostState State;
 
   void propagateState(const InstructionCost &RHS) {
     if (RHS.State == Invalid)
       State = Invalid;
   }
 
 public:
   InstructionCost() = default;
public:
   }
 
   InstructionCost operator--(int) {
     InstructionCost Copy = *this;
     --*this;
     return Copy;
   }
 
+  /// For the comparison operators we have chosen to use lexicographical
+  /// ordering where valid costs are always considered to be less than invalid
+  /// costs. This avoids having to add asserts to the comparison operators that
+  /// the states are valid and users can test for validity of the cost
+  /// explicitly.
+  bool operator<(const InstructionCost &RHS) const {
+    return State < RHS.State || Value < RHS.Value;
+  }
+
+  // Implement in terms of operator< to ensure that the two comparisons stay in
+  // sync
   bool operator==(const InstructionCost &RHS) const {
-    return State == RHS.State && Value == RHS.Value;
+    return !(*this < RHS) && !(RHS < *this);
   }
 
   bool operator!=(const InstructionCost &RHS) const { return !(*this == RHS); }
 
   bool operator==(const CostType RHS) const {
-    return State == Valid && Value == RHS;
+    InstructionCost RHS2(RHS);
+    return *this == RHS2;
   }
 
   bool operator!=(const CostType RHS) const { return !(*this == RHS); }
 
-  /// For the comparison operators we have chosen to use total ordering with
-  /// the following rules:
-  ///  1. If either of the states != Valid then a lexicographical order is
-  ///     applied based upon the state.
-  ///  2. If both states are valid then order based upon value.
-  /// This avoids having to add asserts the comparison operators that the states
-  /// are valid and users can test for validity of the cost explicitly.
-  bool operator<(const InstructionCost &RHS) const {
-    if (State != Valid || RHS.State != Valid)
-      return State < RHS.State;
-    return Value < RHS.Value;
-  }
-
   bool operator>(const InstructionCost &RHS) const { return RHS < *this; }
 
   bool operator<=(const InstructionCost &RHS) const { return !(RHS < *this); }
 
   bool operator>=(const InstructionCost &RHS) const { return !(*this < RHS); }
 
   bool operator<(const CostType RHS) const {
     InstructionCost RHS2(RHS);

llvm/unittests/Support/InstructionCostTest.cpp

struct CostTest : public testing::Test {
   CostTest() {}
 };
 
 } // namespace
 
 TEST_F(CostTest, Operators) {
   InstructionCost VThree = 3;
   InstructionCost VNegTwo = -2;
   InstructionCost VSix = 6;
   InstructionCost IThreeA = InstructionCost::getInvalid(3);
   InstructionCost IThreeB = InstructionCost::getInvalid(3);
+  InstructionCost ITwo = InstructionCost::getInvalid(2);
   InstructionCost TmpCost;
 
   EXPECT_NE(VThree, VNegTwo);
   EXPECT_GT(VThree, VNegTwo);
   EXPECT_NE(VThree, IThreeA);
   EXPECT_EQ(IThreeA, IThreeB);
   EXPECT_GE(IThreeA, VNegTwo);
   EXPECT_LT(VSix, IThreeA);
   EXPECT_EQ(VSix - IThreeA, IThreeB);
   EXPECT_EQ(VThree - VNegTwo, 5);
   EXPECT_EQ(VThree * VNegTwo, -6);
   EXPECT_EQ(VSix / VThree, 2);
+  EXPECT_NE(IThreeA, ITwo);
+  EXPECT_LT(ITwo, IThreeA);
+  EXPECT_GT(IThreeA, ITwo);
 
   EXPECT_FALSE(IThreeA.isValid());
   EXPECT_EQ(IThreeA.getState(), InstructionCost::Invalid);
 
   TmpCost = VThree + IThreeA;
   EXPECT_FALSE(TmpCost.isValid());
 
   // Test increments, decrements
   EXPECT_EQ(++VThree, 4);
   EXPECT_EQ(VThree++, 4);