Page MenuHomePhabricator

[SLP] Avoid std::stable_sort(properlyDominates()).
ClosedPublic

Authored by hvdijk on Tue, Jun 1, 1:42 AM.

Details

Summary

As noticed by NAKAMURA Takumi back in 2017, we cannot use
properlyDominates for std::stable_sort as properlyDominates only
partially orders blocks. That is, for blocks A, B, C, D, where A
dominates B and C dominates D, we have A == C, B == C, but A < B. This
is not a valid comparison function for std::stable_sort and causes
different results between libstdc++ and libc++. This change uses DFS
numbering to give deterministic results for all reachable blocks.
Unreachable blocks are ignored already, so do not need special
consideration.

Diff Detail

Event Timeline

hvdijk created this revision.Tue, Jun 1, 1:42 AM
hvdijk requested review of this revision.Tue, Jun 1, 1:42 AM
Herald added a project: Restricted Project. · View Herald TranscriptTue, Jun 1, 1:42 AM

Can this be separated into two changes: ignoring unreachable blocks and changing sorting?

hvdijk added a comment.Tue, Jun 1, 1:55 AM

Can this be separated into two changes: ignoring unreachable blocks and changing sorting?

If this is approved I can push it as two separate commits, if preferred, but the change to the sorting cannot be done without the ignoring of unreachable blocks, and Phabricator cannot handle changes that depend on other changes as far as I know.

Can this be separated into two changes: ignoring unreachable blocks and changing sorting?

If this is approved I can push it as two separate commits, if preferred, but the change to the sorting cannot be done without the ignoring of unreachable blocks, and Phabricator cannot handle changes that depend on other changes as far as I know.

See Edit related revisions

hvdijk added a comment.Tue, Jun 1, 2:12 AM

See Edit related revisions

Ah, thanks. Will update once I'm able to re-run tests to also test the change to handling of unreachable blocks in isolation.

RKSimon added inline comments.Tue, Jun 1, 9:23 AM
llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
4327

(style) missing assert message

5723

(style) missing assert message

hvdijk updated this revision to Diff 349042.Tue, Jun 1, 11:49 AM
hvdijk edited the summary of this revision. (Show Details)
hvdijk marked 2 inline comments as done.
RKSimon added inline comments.Wed, Jun 2, 2:28 AM
llvm/test/Transforms/SLPVectorizer/X86/ordering-bug.ll
2

Self generated checks are a pain to maintain (especially in an actively changing component like SLP) - what does it look like if you use the llvm\utils\update_test_checks.py script?

hvdijk updated this revision to Diff 349331.Wed, Jun 2, 11:16 AM

Use update_test_checks.

hvdijk added inline comments.Wed, Jun 2, 11:17 AM
llvm/test/Transforms/SLPVectorizer/X86/ordering-bug.ll
2

It's weird in how it handles block labels, see update. If that makes it much easier to maintain though, it may still be worth it.

RKSimon accepted this revision.Thu, Jun 3, 4:16 AM

LGTM - cheers

This revision is now accepted and ready to land.Thu, Jun 3, 4:16 AM
This revision was landed with ongoing or failed builds.Thu, Jun 3, 9:52 AM
This revision was automatically updated to reflect the committed changes.