This is an archive of the discontinued LLVM Phabricator instance.

[EarlyCSE] Avoid a poorly defined instruction comparison
AbandonedPublic

Authored by jmorse on May 15 2018, 3:12 AM.

Details

Summary

EarlyCSE currently attempts to eliminate equivalent comparisons like this:

fcmp ugt %a, %b
fcmp ult %b, %a

where the operands are swapped, by using getSwappedPredicate() to find what the equivalent predicate would be. However, it does not take account of comparisons between identical operands, like "fcmp ugt %a, %a". For identical operands getSwappedPredicate() is poorly defined as there is no other predicate that computes the same result. The net effect is that some instruction pairs hash differently, but compare equally, using hasher DenseMapInfo<SimpleValue>::getHashValue and equality DenseMapInfo<SimpleValue>::isEqual. For example:

fcmp ugt %a, %a
fcmp ult %a, %a

have different predicates as inputs to the hash, but then compare equal because one of the predicates gets flipped in the equality function.

DenseMap doesn't expect inconsistent hash/equality, which has tripped assertion failures in online fuzzers [0] as least once. However because EarlyCSE (legitimately) uses pointer values in its hash, that doesn't happen often, instead it usually causes nondeterministic behaviour. Running the test in this patch results in a different output to the auto-generated one about 50% of the time on Ubuntu 18.04 and LLVM compiled with clang / libstdc++.

The functional change in this patch filters out the edge case of identical operands. The regression test reproduces the problem with reasonable frequency, however it's not clear how useful it is in general: because the broken behaviour depends on pointer values, it's hard to test.

[0] https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=7892

Diff Detail

Event Timeline

jmorse created this revision.May 15 2018, 3:12 AM
reames requested changes to this revision.May 17 2018, 10:06 AM
reames added inline comments.
lib/Transforms/Scalar/EarlyCSE.cpp
266

If I'm reading this correctly, the problem only exists for fcmps not icmps right? If so, please restrict the early return to fcmps.

This revision now requires changes to proceed.May 17 2018, 10:06 AM
dberlin requested changes to this revision.May 17 2018, 11:24 AM
dberlin added a subscriber: dberlin.

So, IMHO, the swapping should not be *determined* as part of the equality function, and that is your underlying problem.
This feels like a workaround instead of fixing that problem.

If you look at GVN and NewGVN, they take care of this the same way - the commutativeness/etc is taken care of by canonicalizing the expression prior to putting it in the hashtable.
The hashtable hashes and does equality based only on the contents of that structure as it exists in the table (IE they don't run around swapping operands in equality).

Admittedly, they have a different expression structure than EarlyCSE which makes this easier.

A couple paths forward i could see:

  1. Determine what should be swapped or not swapped outside of hashing and equality functions, even if the equality function does the swapping.

IE add a flag to SimpleValue stating whether operands/predicate should be swapped, and that flag is set in the constructor.
Both hashing and equality do what that flag says prior to hashing/comparing.
Then you can make actual decisions about canonicalization outside of hashing and equality, even if hashing and equality have to do a little of the work.

This is kind of ugly but IMHO, still better than what we're doing now.

  1. Create a CmpValue structure that works similar to how GVN/NewGVN (IE actually contains the operands and predicate).

All swapping/etc is taken care of by the things creating these structures, and hashing/equality of CmpValue is simply hashing of operands+predicate and equality comparison of structure members.

jmorse updated this revision to Diff 147525.May 18 2018, 8:57 AM

Hi, Thanks all for reviewing,

So, IMHO, the swapping should not be *determined* as part of the equality function, and that is your underlying problem.
This feels like a workaround instead of fixing that problem.

True, the patch only fixes a symptom,

A couple paths forward i could see: [...]

I've taken a shot at the second option, which seems cleaner and reduces a reasonable amount of code duplication -- see updated patch. The downside is the more invasive patch, additional memory usage, and as I'm an LLVM newbie a risk that I've missed something (although the tests all pass on x86 Ubuntu 18.04).

Describing the logic of the revised patch:

  • The opcode, main operands and flags get localised into SimpleValue
  • During construction, the three replicated canonicalisations from the existing hash/equality functions are performed:
    • Commutative binary operations are ordered
    • Comparison operand swapping (the motivation for this patch)
    • Select pattern detection and operand ordering
  • During hashing, the potentially canonicalised information is hashed in from the local storage (plus some non-canonicalised material for other instructions)
  • Similarly for equality, if the instructions aren't already identical, we only examine the canonicalised local information

Which I think achieves the main aim: ensuring ordering decisions are only performed in one place (now the SimpleValue constructor). There's good coverage of these canonicalisation steps in test/Transforms/EarlyCSE/commute.ll.

dberlin accepted this revision.EditedMay 24 2018, 10:34 AM

Thanks.
This makes me wonder if there should be a real class hierarchy here, but i think this is something we can worry about in the future because it will be a larger change.

jmorse updated this revision to Diff 149927.Jun 5 2018, 3:45 AM

Rebase on top of r332865:

https://reviews.llvm.org/rL332865

matchSelectPattern now canonicalises operand order itself: for this patch lines 168-173 take that into account by not trying to order them. Equality and hashing functions are unchanged (which is desirable), tests pass.

Also pseudo-ping: it's not clear to me whether one LGTM overrides another persons earlier needs-review, but the phab interface seems to think so. (My phab-foo is new).

Ping, partially for rebase, mostly because the phab-workflow is unclear to me (see immediately previous comment).

Add review response which (I think) clears up some confusion.

Note that dberlin replied to my procedure-ping above, but the message seemed to get attached to https://reviews.llvm.org/rL332865 (presumably a case of mistaken identity).

lib/Transforms/Scalar/EarlyCSE.cpp
266

Hmm, I think here you're referring to the fact that fcmps can have an "unordered" result if one operand is a NaN, is that right?

If so, I think this is based on some legitimate confusion: the "poorly defined comparison" I'm referring to in this patch is the call to getSwappedPredicate() which doesn't have a well defined result if both operands are the same; wheras I see now that you might read the review message as referring to "poorly defined comparisons" in the LLVM IR being processed, which isn't the case.

I didn't notice that that phrase could equally apply to both things, curses. If I've barked up the wrong tree here though, please do elaborate.

ping @reames , does the inline comment clear up the question?

reames resigned from this revision.Sep 28 2020, 11:07 AM

Removing self from old stale review.

This revision is now accepted and ready to land.Sep 28 2020, 11:07 AM
jmorse abandoned this revision.Feb 4 2021, 7:04 AM

Abandoning an ancient patch; EarlyCSE has been substantially refactored since then, in D62644