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

 /// or not when forming partitions of the alloca.
 class Slice {
   /// The beginning offset of the range.
   uint64_t BeginOffset = 0;
 
   /// The ending offset, not included in the range.
   uint64_t EndOffset = 0;
 
-  /// Storage for both the use of this slice and whether it can be
-  /// split.
-  PointerIntPair<Use *, 1, bool> UseAndIsSplittable;
+  // Slice use.
+  Use *U;
+
+  /// True if this slice can be split.
+  bool IsSplittable : 1;
+
+  /// A sequentially growing number to make sure sort is stable if all the
+  /// rest compares are equal.
+  unsigned Ordinal : 31;
 
 public:
   Slice() = default;
 
-  Slice(uint64_t BeginOffset, uint64_t EndOffset, Use *U, bool IsSplittable)
+  Slice(uint64_t BeginOffset, uint64_t EndOffset, Use *U, bool IsSplittable,
+        unsigned Ordinal)
       : BeginOffset(BeginOffset), EndOffset(EndOffset),
-        UseAndIsSplittable(U, IsSplittable) {}
+        U(U), IsSplittable(IsSplittable), Ordinal(Ordinal) {}
 
   uint64_t beginOffset() const { return BeginOffset; }
   uint64_t endOffset() const { return EndOffset; }
 
-  bool isSplittable() const { return UseAndIsSplittable.getInt(); }
-  void makeUnsplittable() { UseAndIsSplittable.setInt(false); }
+  bool isSplittable() const { return IsSplittable; }
+  void makeUnsplittable() { IsSplittable = false; }
 
-  Use *getUse() const { return UseAndIsSplittable.getPointer(); }
+  Use *getUse() const { return U; }
 
   bool isDead() const { return getUse() == nullptr; }
-  void kill() { UseAndIsSplittable.setPointer(nullptr); }
+  void kill() { U = nullptr; }
 
   /// Support for ordering ranges.
   ///
   /// This provides an ordering over ranges such that start offsets are
   /// always increasing, and within equal start offsets, the end offsets are
   /// decreasing. Thus the spanning range comes first in a cluster with the
   /// same start position.
   bool operator<(const Slice &RHS) const {
     if (beginOffset() < RHS.beginOffset())
       return true;
     if (beginOffset() > RHS.beginOffset())
       return false;
     if (isSplittable() != RHS.isSplittable())
       return !isSplittable();
     if (endOffset() > RHS.endOffset())
       return true;
+    if (endOffset() < RHS.endOffset())
       return false;
+    return Ordinal < RHS.Ordinal;
   }
 
   /// Support comparison with a single offset to allow binary searches.
   friend LLVM_ATTRIBUTE_UNUSED bool operator<(const Slice &LHS,
                                               uint64_t RHSOffset) {
     return LHS.beginOffset() < RHSOffset;
   }
   friend LLVM_ATTRIBUTE_UNUSED bool operator<(uint64_t LHSOffset,
public:
   /// Access the dead operands referring to this alloca.
   ///
   /// These are operands which have cannot actually be used to refer to the
   /// alloca as they are outside its range and the user doesn't correct for
   /// that. These mostly consist of PHI node inputs and the like which we just
   /// need to replace with undef.
   ArrayRef<Use *> getDeadOperands() const { return DeadOperands; }
 
+  /// Return and increment ordinal to be used for Slices sorting on tie.
+  unsigned getOrdinal() { return Ordinal++; }
+
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   void print(raw_ostream &OS, const_iterator I, StringRef Indent = "  ") const;
   void printSlice(raw_ostream &OS, const_iterator I,
                   StringRef Indent = "  ") const;
   void printUse(raw_ostream &OS, const_iterator I,
                 StringRef Indent = "  ") const;
   void print(raw_ostream &OS) const;
   void dump(const_iterator I) const;
#endif
   ///
   /// These are operands that in their particular use can be replaced with
   /// undef when we rewrite the alloca. These show up in out-of-bounds inputs
   /// to PHI nodes and the like. They aren't entirely dead (there might be
   /// a GEP back into the bounds using it elsewhere) and nor is the PHI, but we
   /// want to swap this particular input for undef to simplify the use lists of
   /// the alloca.
   SmallVector<Use *, 8> DeadOperands;
+
+  /// Incrementing ordinal to be used for Slices sorting on tie.
+  unsigned Ordinal;
 };
 
 /// A partition of the slices.
 ///
 /// An ephemeral representation for a range of slices which can be viewed as
 /// a partition of the alloca. This range represents a span of the alloca's
 /// memory which cannot be split, and provides access to all of the slices
 /// overlapping some part of the partition.
if (Size > AllocSize - BeginOffset) {
       LLVM_DEBUG(dbgs() << "WARNING: Clamping a " << Size << " byte use @"
                         << Offset << " to remain within the " << AllocSize
                         << " byte alloca:\n"
                         << "    alloca: " << AS.AI << "\n"
                         << "       use: " << I << "\n");
       EndOffset = AllocSize;
     }
 
-    AS.Slices.push_back(Slice(BeginOffset, EndOffset, U, IsSplittable));
+    AS.Slices.push_back(Slice(BeginOffset, EndOffset, U, IsSplittable,
+                              AS.getOrdinal()));
   }
 
   void visitBitCastInst(BitCastInst &BC) {
     if (BC.use_empty())
       return markAsDead(BC);
 
     return Base::visitBitCastInst(BC);
   }
private:
   void visitInstruction(Instruction &I) { PI.setAborted(&I); }
 };
 
 AllocaSlices::AllocaSlices(const DataLayout &DL, AllocaInst &AI)
     :
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
       AI(AI),
 #endif
-      PointerEscapingInstr(nullptr) {
+      PointerEscapingInstr(nullptr), Ordinal(0) {
   SliceBuilder PB(DL, AI, *this);
   SliceBuilder::PtrInfo PtrI = PB.visitPtr(AI);
   if (PtrI.isEscaped() || PtrI.isAborted()) {
     // FIXME: We should sink the escape vs. abort info into the caller nicely,
     // possibly by just storing the PtrInfo in the AllocaSlices.
     PointerEscapingInstr = PtrI.getEscapingInst() ? PtrI.getEscapingInst()
                                                   : PtrI.getAbortingInst();
     assert(PointerEscapingInstr && "Did not track a bad instruction");
for (LoadInst *LI : Loads) {
     IRB.SetInsertPoint(LI);
 
     LLVM_DEBUG(dbgs() << "  Splitting load: " << *LI << "\n");
 
     uint64_t PartOffset = 0, PartSize = Offsets.Splits.front();
     int Idx = 0, Size = Offsets.Splits.size();
     for (;;) {
       auto *PartTy = Type::getIntNTy(Ty->getContext(), PartSize * 8);
-      auto AS = LI->getPointerAddressSpace();
-      auto *PartPtrTy = PartTy->getPointerTo(AS);
+      auto PtrAS = LI->getPointerAddressSpace();
+      auto *PartPtrTy = PartTy->getPointerTo(PtrAS);
       LoadInst *PLoad = IRB.CreateAlignedLoad(
           PartTy,
           getAdjustedPtr(IRB, DL, BasePtr,
-                         APInt(DL.getIndexSizeInBits(AS), PartOffset),
+                         APInt(DL.getIndexSizeInBits(PtrAS), PartOffset),
                          PartPtrTy, BasePtr->getName() + "."),
           getAdjustedAlignment(LI, PartOffset),
           /*IsVolatile*/ false, LI->getName());
       PLoad->copyMetadata(*LI, {LLVMContext::MD_mem_parallel_loop_access,
                                 LLVMContext::MD_access_group});
 
       // Append this load onto the list of split loads so we can find it later
       // to rewrite the stores.
       SplitLoads.push_back(PLoad);
 
       // Now build a new slice for the alloca.
       NewSlices.push_back(
           Slice(BaseOffset + PartOffset, BaseOffset + PartOffset + PartSize,
                 &PLoad->getOperandUse(PLoad->getPointerOperandIndex()),
-                /*IsSplittable*/ false));
+                /*IsSplittable*/ false, AS.getOrdinal()));
       LLVM_DEBUG(dbgs() << "    new slice [" << NewSlices.back().beginOffset()
                         << ", " << NewSlices.back().endOffset()
                         << "): " << *PLoad << "\n");
 
       // See if we've handled all the splits.
       if (Idx >= Size)
         break;
 
for (;;) {
                            APInt(DL.getIndexSizeInBits(AS), PartOffset),
                            LoadPartPtrTy, LoadBasePtr->getName() + "."),
             getAdjustedAlignment(LI, PartOffset),
             /*IsVolatile*/ false, LI->getName());
       }
 
       // And store this partition.
       IRB.SetInsertPoint(SI);
-      auto AS = SI->getPointerAddressSpace();
+      auto PtrAS = SI->getPointerAddressSpace();
       StoreInst *PStore = IRB.CreateAlignedStore(
           PLoad,
           getAdjustedPtr(IRB, DL, StoreBasePtr,
-                         APInt(DL.getIndexSizeInBits(AS), PartOffset),
+                         APInt(DL.getIndexSizeInBits(PtrAS), PartOffset),
                          StorePartPtrTy, StoreBasePtr->getName() + "."),
           getAdjustedAlignment(SI, PartOffset),
           /*IsVolatile*/ false);
 
       // Now build a new slice for the alloca.
       NewSlices.push_back(
           Slice(BaseOffset + PartOffset, BaseOffset + PartOffset + PartSize,
                 &PStore->getOperandUse(PStore->getPointerOperandIndex()),
-                /*IsSplittable*/ false));
+                /*IsSplittable*/ false, AS.getOrdinal()));
       LLVM_DEBUG(dbgs() << "    new slice [" << NewSlices.back().beginOffset()
                         << ", " << NewSlices.back().endOffset()
                         << "): " << *PStore << "\n");
       if (!SplitLoads) {
         LLVM_DEBUG(dbgs() << "      of split load: " << *PLoad << "\n");
       }
 
       // See if we've finished all the splits.

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(...)