This is an archive of the discontinued LLVM Phabricator instance.

Ensure that InstructionCost actually implements a total ordering
ClosedPublic

Authored by ctetreau on Feb 1 2021, 10:52 AM.

Details

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.

Diff Detail

Event Timeline

ctetreau created this revision.Feb 1 2021, 10:52 AM
ctetreau requested review of this revision.Feb 1 2021, 10:52 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 1 2021, 10:52 AM

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
152

nit: s/ / to /

155–158

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

164

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
55

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

ctetreau added inline comments.Feb 1 2021, 1:01 PM
llvm/unittests/Support/InstructionCostTest.cpp
55

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 updated this revision to Diff 320574.Feb 1 2021, 1:14 PM

address code review issues

ctetreau marked 4 inline comments as done.Feb 1 2021, 1:16 PM
ctetreau added inline comments.
llvm/unittests/Support/InstructionCostTest.cpp
55

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 accepted this revision.Feb 1 2021, 1:18 PM

Thanks for the changes, LGTM!

This revision is now accepted and ready to land.Feb 1 2021, 1:18 PM
This revision was landed with ongoing or failed builds.Feb 2 2021, 11:49 AM
This revision was automatically updated to reflect the committed changes.

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.

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 added a subscriber: nikic.Feb 2 2021, 3:21 PM

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

llvm/include/llvm/Support/InstructionCost.h
156

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 added inline comments.Feb 2 2021, 4:56 PM
llvm/include/llvm/Support/InstructionCost.h
156

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 reopened this revision.Feb 2 2021, 4:56 PM
This revision is now accepted and ready to land.Feb 2 2021, 4:56 PM
ctetreau planned changes to this revision.Feb 2 2021, 4:56 PM
ctetreau updated this revision to Diff 321094.Feb 3 2021, 6:59 AM

Fix operator<

This revision is now accepted and ready to land.Feb 3 2021, 6:59 AM
ctetreau added inline comments.Feb 3 2021, 7:00 AM
llvm/unittests/Support/InstructionCostTest.cpp
46

This test catches the previous bug

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

sdesmalen added inline comments.Feb 4 2021, 7:05 AM
llvm/include/llvm/Support/InstructionCost.h
38–40

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

ctetreau updated this revision to Diff 321500.Feb 4 2021, 9:56 AM

address code review issues

ctetreau updated this revision to Diff 321503.Feb 4 2021, 10:01 AM

Fix test, add comment

llvm/include/llvm/Support/InstructionCost.h
38–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 added inline comments.Feb 4 2021, 10:24 AM
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 added inline comments.Feb 4 2021, 11:37 AM
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
ctetreau marked an inline comment as done.Feb 4 2021, 11:38 AM
sdesmalen added inline comments.Feb 4 2021, 1:24 PM
llvm/unittests/Support/InstructionCostTest.cpp
25

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

ctetreau closed this revision.Feb 5 2021, 1:56 PM

the reland has landed