Stabilize alloca slices sort in SROA
authorStanislav Mekhanoshin <Stanislav.Mekhanoshin@amd.com>
Mon, 8 Jun 2020 15:27:07 +0000 (08:27 -0700)
committerStanislav Mekhanoshin <Stanislav.Mekhanoshin@amd.com>
Mon, 8 Jun 2020 21:25:27 +0000 (14:25 -0700)
commit87ff3401eb103d8dbb632466fd9a9762d698f223
treeb22df5c1c5ed7e8aa53e8b422a51f6a7df8d090d
parent56a872947acca7635ca969f39f50062f2f779af0
Stabilize alloca slices sort in SROA

Slice::operator<() has a non-deterministic behavior. If we have
identical slices comparison will depend on the order or operands.
Normally that does not result in unstable compilation results
because the order in which slices are inserted into the vector
is deterministic and llvm::sort() normally behaves as a stable
sort, although that is not guaranteed.

However, there is test option -sroa-random-shuffle-slices which
is used to check exactly this aspect. The vector is first randomly
shuffled and then sorted. The same shuffling happens without this
option under expensive llvm checks.

I have managed to write a test which has hit this problem.

There are no fields in the Slice class to resolve the instability.
We only have offsets, IsSplittable and Use, but neither Use nor
User have anything suitable for predictable comparison.

I have switched to stable_sort which has to be sufficient and
removed that randon shuffle option.

Differential Revision: https://reviews.llvm.org/D81310
llvm/lib/Transforms/Scalar/SROA.cpp
llvm/test/Transforms/SROA/phi-gep.ll