[SelectionDAG] Make sorting predicate stronger to remove non-deterministic ordering
ClosedPublic

Authored by mgrang on Mon, Nov 13, 6:17 PM.

Details

Summary

This fixes failures in the following tests uncovered by D39245:

LLVM :: CodeGen/ARM/ifcvt3.ll
LLVM :: CodeGen/ARM/switch-minsize.ll
LLVM :: CodeGen/X86/switch.ll

Diff Detail

Repository
rL LLVM
mgrang created this revision.Mon, Nov 13, 6:17 PM
fhahn added a subscriber: fhahn.Tue, Nov 14, 3:44 AM
fhahn added inline comments.
lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
9551 ↗(On Diff #122761)

I might be missing something but could we still end up with multiple clusters where a.Prob == b.Prob && a.Low == b.Low ? Then the order of those nodes would still be non-deterministic, no?

mgrang added inline comments.Tue, Nov 14, 10:03 AM
lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
9551 ↗(On Diff #122761)

@fhahn Thanks! I am not sure if we two clusters can have the same Low. How about I add another predicate a.High < b.High?

The fallback option is to simply change this to use std::stable_sort but I wanted to avoid this if we can simply get by adding stronger predicates.

hans added inline comments.Tue, Nov 14, 10:11 AM
lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
9551 ↗(On Diff #122761)

The CaseClusters can't overlap, so having the same Low should not be possible.

I like this fix. Please expand the "Order cases by probability" comment to explain what's going on here. It would also be nice to have a test for this.

fhahn added inline comments.Tue, Nov 14, 11:08 AM
lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
9551 ↗(On Diff #122761)

The CaseClusters can't overlap, so having the same Low should not be possible

Ok great, thanks for confirming

mgrang updated this revision to Diff 123464.Sat, Nov 18, 10:50 AM

Added comment to explain what's going on.

mgrang marked an inline comment as done.Sat, Nov 18, 10:54 AM
mgrang added inline comments.
lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
9551 ↗(On Diff #122761)

I believe writing individual test cases for such scenarios is difficult as well as an overkill.

Once all failures uncovered by shuffling std::sort containers are fixed, I will push patches to change all std:sort to llvm::sort, which will shuffle containers by default in a +asserts build. Once that is done, the existing tests will automatically become test cases to uncover such non-determinism.

mgrang updated this revision to Diff 123466.Sat, Nov 18, 10:58 AM
mgrang updated this revision to Diff 123545.Mon, Nov 20, 12:03 AM
mgrang edited the summary of this revision. (Show Details)

Fixed another instance of non-deterministic ordering causing failure in CodeGen/X86/switch.ll.

hans accepted this revision.Mon, Nov 20, 10:24 AM
This revision is now accepted and ready to land.Mon, Nov 20, 10:24 AM
This revision was automatically updated to reflect the committed changes.