Stabilize alloca slices sort in SROA

[rampitec]

Summary

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.

[efriedma]

I haven't looked at the code changes deeply, but would it be simpler to use std::stable_sort?

[rampitec]

In D81310#2078610, @efriedma wrote:

I haven't looked at the code changes deeply, but would it be simpler to use std::stable_sort?

std::stable_sort is C++17, we are still at C++14. It should be sufficient to use stable_sort here, but it will also require to remove -sroa-random-shuffle-slices option.

[rampitec]

Top up Ordinal to full dword along with the bool flag. It was supposed to be 31 bits from the beginning.

[rampitec]

In D81310#2079887, @rampitec wrote:

In D81310#2078610, @efriedma wrote:

I haven't looked at the code changes deeply, but would it be simpler to use std::stable_sort?

std::stable_sort is C++17, we are still at C++14. It should be sufficient to use stable_sort here, but it will also require to remove -sroa-random-shuffle-slices option.

I stand corrected, in C++17 it only added some versions. Yes, I can change it to stable_sort, I seems to be sufficient.

[rampitec]

Just switched to std::stable_sort().

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/SROA.cpp

 #include <cstdint>
 #include <cstring>
 #include <iterator>
 #include <string>
 #include <tuple>
 #include <utility>
 #include <vector>
 
-#ifndef NDEBUG
-// We only use this for a debug check.
-#include <random>
-#endif
-
 using namespace llvm;
 using namespace llvm::sroa;
 
 #define DEBUG_TYPE "sroa"
 
 STATISTIC(NumAllocasAnalyzed, "Number of allocas analyzed for replacement");
 STATISTIC(NumAllocaPartitions, "Number of alloca partitions formed");
 STATISTIC(MaxPartitionsPerAlloca, "Maximum number of partitions per alloca");
 STATISTIC(NumAllocaPartitionUses, "Number of alloca partition uses rewritten");
 STATISTIC(MaxUsesPerAllocaPartition, "Maximum number of uses of a partition");
 STATISTIC(NumNewAllocas, "Number of new, smaller allocas introduced");
 STATISTIC(NumPromoted, "Number of allocas promoted to SSA values");
 STATISTIC(NumLoadsSpeculated, "Number of loads speculated to allow promotion");
 STATISTIC(NumDeleted, "Number of instructions deleted");
 STATISTIC(NumVectorized, "Number of vectorized aggregates");
 
-/// Hidden option to enable randomly shuffling the slices to help uncover
-/// instability in their order.
-static cl::opt<bool> SROARandomShuffleSlices("sroa-random-shuffle-slices",
-                                             cl::init(false), cl::Hidden);
-
 /// Hidden option to experiment with completely strict handling of inbounds
 /// GEPs.
 static cl::opt<bool> SROAStrictInbounds("sroa-strict-inbounds", cl::init(false),
                                         cl::Hidden);
 
 namespace {
 
 /// A custom IRBuilder inserter which prefixes all names, but only in
if (PtrI.isEscaped() || PtrI.isAborted()) {
     assert(PointerEscapingInstr && "Did not track a bad instruction");
     return;
   }
 
   Slices.erase(
       llvm::remove_if(Slices, [](const Slice &S) { return S.isDead(); }),
       Slices.end());
 
-#ifndef NDEBUG
-  if (SROARandomShuffleSlices) {
-    std::mt19937 MT(static_cast<unsigned>(
-        std::chrono::system_clock::now().time_since_epoch().count()));
-    std::shuffle(Slices.begin(), Slices.end(), MT);
-  }
-#endif
-
   // Sort the uses. This arranges for the offsets to be in ascending order,
   // and the sizes to be in descending order.
-  llvm::sort(Slices);
+  std::stable_sort(Slices.begin(), Slices.end());
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 
 void AllocaSlices::print(raw_ostream &OS, const_iterator I,
                          StringRef Indent) const {
   printSlice(OS, I, Indent);
   OS << "\n";

llvm/test/Transforms/SROA/phi-gep.ll

while.body:
   %select = select i1 undef, %pair* %phi, %pair* undef
   %gep = getelementptr inbounds %pair, %pair* %select, i64 1
   br i1 undef, label %exit, label %while.body
 
 exit:
   unreachable
 }
 
+define i32 @test_sroa_gep_cast_phi_gep(i1 %cond) {
+; CHECK-LABEL: @test_sroa_gep_cast_phi_gep(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A_SROA_0:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[A_SROA_0_0_GEP_A_CAST_TO_I32_SROA_CAST:%.*]] = bitcast i32* [[A_SROA_0]] to float*
+; CHECK-NEXT:    [[A_SROA_0_0_GEP_A_CAST_TO_I32_SROA_CAST2:%.*]] = bitcast i32* [[A_SROA_0]] to float*
+; CHECK-NEXT:    [[A_SROA_0_0_GEP_SROA_CAST:%.*]] = bitcast i32* [[A_SROA_0]] to float*
+; CHECK-NEXT:    store i32 1065353216, i32* [[A_SROA_0]], align 4
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[FOR:%.*]], label [[END:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    [[PHI_I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR]] ]
+; CHECK-NEXT:    [[PHI:%.*]] = phi float* [ [[A_SROA_0_0_GEP_A_CAST_TO_I32_SROA_CAST]], [[ENTRY]] ], [ [[GEP_FOR_CAST_TO_I32:%.*]], [[FOR]] ]
+; CHECK-NEXT:    [[PHI_SROA_PHI:%.*]] = phi float* [ [[A_SROA_0_0_GEP_SROA_CAST]], [[ENTRY]] ], [ [[GEP_FOR_CAST_TO_I32_SROA_GEP:%.*]], [[FOR]] ]
+; CHECK-NEXT:    [[I]] = add i32 [[PHI_I]], 1
+; CHECK-NEXT:    [[GEP_FOR_CAST:%.*]] = bitcast float* [[PHI_SROA_PHI]] to i32*
+; CHECK-NEXT:    [[GEP_FOR_CAST_TO_I32]] = bitcast i32* [[GEP_FOR_CAST]] to float*
+; CHECK-NEXT:    [[GEP_FOR_CAST_TO_I32_SROA_GEP]] = getelementptr inbounds float, float* [[GEP_FOR_CAST_TO_I32]], i32 0
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[I]], 10
+; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[FOR]], label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    [[PHI_END:%.*]] = phi float* [ [[A_SROA_0_0_GEP_A_CAST_TO_I32_SROA_CAST2]], [[ENTRY]] ], [ [[PHI]], [[FOR]] ]
+; CHECK-NEXT:    [[PHI_END_1:%.*]] = bitcast float* [[PHI_END]] to i32*
+; CHECK-NEXT:    [[LOAD:%.*]] = load i32, i32* [[PHI_END_1]], align 4
+; CHECK-NEXT:    ret i32 [[LOAD]]
+;
+entry:
+  %a = alloca %pair, align 4
+  %gep_a = getelementptr inbounds %pair, %pair* %a, i32 0, i32 1
+  %gep_a_cast_to_float = bitcast i32* %gep_a to float*
+  store float 1.0, float* %gep_a_cast_to_float, align 4
+  br i1 %cond, label %for, label %end
+
+for:
+  %phi_i = phi i32 [ 0, %entry ], [ %i, %for ]
+  %phi = phi float* [ %gep_a_cast_to_float, %entry], [ %gep_for_cast_to_float, %for ]
+  %i = add i32 %phi_i, 1
+  %gep_for = getelementptr inbounds float, float* %phi, i32 0
+  %gep_for_cast = bitcast float* %gep_for to i32*
+  %gep_for_cast_to_float = bitcast i32* %gep_for_cast to float*
+  %loop.cond = icmp ult i32 %i, 10
+  br i1 %loop.cond, label %for, label %end
+
+end:
+  %phi_end = phi float* [ %gep_a_cast_to_float, %entry], [ %phi, %for ]
+  %phi_end.1 = bitcast float* %phi_end to i32*
+  %load = load i32, i32* %phi_end.1, align 4
+  ret i32 %load
+}
+
 declare %pair* @foo()
 
 declare i32 @__gxx_personality_v0(...)