HomePhabricator

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

Authored by hvdijk on Jun 3 2021, 9:51 AM.

Description

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

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.

Reviewed By: RKSimon

Differential Revision: https://reviews.llvm.org/D103441

Details

Committed
hvdijkJun 3 2021, 9:51 AM
Reviewer
RKSimon
Differential Revision
D103441: [SLP] Avoid std::stable_sort(properlyDominates()).
Parents
rGb0ab79ee2dfa: [MC] Add missing include (NFC)
Branches
Unknown
Tags
Unknown