[PredicateInfo] Fix non-determinism in codegen uncovered by reverse iterating SmallPtrSet

[mgrang]

Summary

Sort OpsToRename before iterating to make iteration order deterministic.

Thanks to Daniel Berlin for the sorting logic.

[mgrang]

Added more context for the patch.

[davide]

Where did you encounter this?

[mgrang]

In D33265#756952, @davide wrote:

Where did you encounter this?

@davide The following two unit tests fail if run with -reverse-iterate :

test/Transforms/Util/PredicateInfo/condprop.ll
test/Transforms/Util/PredicateInfo/testandor.ll

The cause of the failure is the difference in codegen due to iteration of OpsToRename:

void PredicateInfo::renameUses(SmallSetVector<Value *, 8> &OpsToRename) {
  ValueDFS_Compare Compare(OBBMap);
  // Compute liveness, and rename in O(uses) per Op.
  for (auto *Op : OpsToRename) {

[• dberlin]

Actually, please don't land this.
This actually significantly slows down predicateinfo on large files.
The generated differences don't actually matter, either.

If you want to make a SmallPtrSetVector, i'd be more willing to do this, otherwise, i'll just convert the relevant parts.

(FWIW, i think running around the compiler and converting things from SmallPtrSet to to setvector is generally going to be a bad plan, and i'd be pretty opposed. We use SmallPtrSet because it's small and fast. SetVector is neither of these things. SmallSetVector is not *that much* better. )

[davide]

uh, I'm very confused at this point, I thought this was resulting in non-deterministic output?

[davide]

Nevermind, we always remove the copy so that shouldn't matter.

[davide]

As we did in NewGVN I think it's important to add a comment explaining why this doesn't matter, so, @mgrang, you might want to do that instead.

[• dberlin]

(and in this case, the only place that needs any ordering is in renameUses, where we can just sort the input set of ops into a deterministic order, which we do for the uses anyway)

[• dberlin]

https://reviews.llvm.org/differential/diff/99233/?revisionID=33265
has a diff that touches one routine, and makes this deterministic.
It could use refactoring (it can share most code with the ValueDFS_Compare), but if you really want to make this deterministic, that's how to do it.

[mgrang]

Thanks @davide and @dberlin for your comments.

Just wanted to confirm I understand this: In order to reuse the comparison function from ValueDFS_Compare in our case, we would have to move the localComesBefore function (or parts of it) out of ValueDFS_Compare so that both OBBMap and OpsToRename can use it as a comparator? ValueDFS_Compare constructor accepts BBs, so unless we first convert OpsToRename into ValueDFS (by calling our version of convertUsesToDFSOrdered) we cannot directly use it for sorting OpsToRename.
Or would it be simpler to just keep the comparator inline as you do in your code?

Also is it OK to add -reverse-iterate to the two unit tests as I have done in my patch (so that we catch any future non-determinism arising out of this piece of code)?

[mgrang]

Ping for reviews please. (I know it's not been a week since I posted this patch, but it would be great if we could get this patch reviewed for an upcoming internal toolchain release).

Thanks!

[RKSimon]

lib/Transforms/Utils/PredicateInfo.cpp

552 ↗

(On Diff #99624)

A few descriptive comments in this lambda would be useful.

[mgrang]

Added comments for the comparator.

[RKSimon]

In D33265#768364, @mgrang wrote:

Added comments for the comparator.

Thanks no more comments from me.

@dberlin @davide anything to add?

[• dberlin]

Sorry, this was marked as accepted because davide accepted the last version.
This looks fine for now, i'll fix it up when D33380 goes in

llvm/trunk/lib/Transforms/Utils/PredicateInfo.cpp

 // with top of stack if it exists.  In order to handle liveness without
 // propagating liveness info, we don't actually insert the predicateinfo
 // instruction def until we see a use that it would dominate.  Once we see such
 // a use, we materialize the predicateinfo instruction in the right place and
 // use it.
 //
 // TODO: Use this algorithm to perform fast single-variable renaming in
 // promotememtoreg and memoryssa.
-void PredicateInfo::renameUses(SmallPtrSetImpl<Value *> &OpsToRename) {
+void PredicateInfo::renameUses(SmallPtrSetImpl<Value *> &OpSet) {
+  // Sort OpsToRename since we are going to iterate it.
+  SmallVector<Value *, 8> OpsToRename(OpSet.begin(), OpSet.end());
+  std::sort(OpsToRename.begin(), OpsToRename.end(), [&](const Value *A,
+                                                        const Value *B) {
+    auto *ArgA = dyn_cast_or_null<Argument>(A);
+    auto *ArgB = dyn_cast_or_null<Argument>(B);
+
+    // If A and B are args, order them based on their arg no.
+    if (ArgA && !ArgB)
+      return true;
+    if (ArgB && !ArgA)
+      return false;
+    if (ArgA && ArgB)
+      return ArgA->getArgNo() < ArgB->getArgNo();
+
+    // Else, A are B are instructions.
+    // If they belong to different BBs, order them by the dominance of BBs.
+    auto *AInst = cast<Instruction>(A);
+    auto *BInst = cast<Instruction>(B);
+    if (AInst->getParent() != BInst->getParent())
+      return DT.dominates(AInst->getParent(), BInst->getParent());
+
+    // Else, A and B belong to the same BB.
+    // Order A and B by their dominance.
+    auto *BB = AInst->getParent();
+    auto LookupResult = OBBMap.find(BB);
+    if (LookupResult != OBBMap.end())
+      return LookupResult->second->dominates(AInst, BInst);
+
+    auto Result = OBBMap.insert({BB, make_unique<OrderedBasicBlock>(BB)});
+    return Result.first->second->dominates(AInst, BInst);
+  });
+
   ValueDFS_Compare Compare(OBBMap);
   // Compute liveness, and rename in O(uses) per Op.
   for (auto *Op : OpsToRename) {
     unsigned Counter = 0;
     SmallVector<ValueDFS, 16> OrderedUses;
     const auto &ValueInfo = getValueInfo(Op);
     // Insert the possible copies into the def/use list.
     // They will become real copies if we find a real use for them, and never

llvm/trunk/test/Transforms/Util/PredicateInfo/condprop.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -print-predicateinfo -analyze  < %s 2>&1 | FileCheck %s
+; RUN: opt -print-predicateinfo -analyze -reverse-iterate  < %s 2>&1 | FileCheck %s
 
 @a = external global i32    ; <i32*> [#uses=7]
 
 define i32 @test1() nounwind {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* @a, align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 4

 declare void @foo(i1)
 declare void @bar(i32)
 
 define void @test3(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
 ; CHECK-NEXT:    [[Z:%.*]] = and i1 [[XZ]], [[YZ]]
-; CHECK:         [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
 ; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
-; CHECK:         [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
 ; CHECK:         [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
+; CHECK:         [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
+; CHECK:         [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
 ; CHECK:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[Z]])
 ; CHECK-NEXT:    br i1 [[Z]], label [[BOTH_ZERO:%.*]], label [[NOPE:%.*]]
 ; CHECK:       both_zero:
 ; CHECK-NEXT:    call void @foo(i1 [[XZ_0]])
 ; CHECK-NEXT:    call void @foo(i1 [[YZ_0]])
 ; CHECK-NEXT:    call void @bar(i32 [[X_0]])
 ; CHECK-NEXT:    call void @bar(i32 [[Y_0]])
 ; CHECK-NEXT:    ret void

 
 ret:
   ret i32 5
 }
 
 define i32 @test10(i32 %j, i32 %i) {
 ; CHECK-LABEL: @test10(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[I:%.*]], [[J:%.*]]
-; CHECK:         [[I_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[I]])
 ; CHECK:         [[J_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[J]])
+; CHECK:         [[I_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[I]])
 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[RET:%.*]]
 ; CHECK:       cond_true:
 ; CHECK-NEXT:    [[DIFF:%.*]] = sub i32 [[I_0]], [[J_0]]
 ; CHECK-NEXT:    ret i32 [[DIFF]]
 ; CHECK:       ret:
 ; CHECK-NEXT:    ret i32 5
 ;
   %cmp = icmp eq i32 %i, %j

llvm/trunk/test/Transforms/Util/PredicateInfo/testandor.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -print-predicateinfo < %s 2>&1 | FileCheck %s
+; RUN: opt -print-predicateinfo -reverse-iterate < %s 2>&1 | FileCheck %s
 
 declare void @foo(i1)
 declare void @bar(i32)
 declare void @llvm.assume(i1)
 
 define void @testor(i32 %x, i32 %y) {
 ; CHECK-LABEL: @testor(
 ; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
 ; CHECK-NEXT:    [[Z:%.*]] = or i1 [[XZ]], [[YZ]]
-; CHECK:         [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
 ; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
-; CHECK:         [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
 ; CHECK:         [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
+; CHECK:         [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
+; CHECK:         [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
 ; CHECK:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[Z]])
 ; CHECK-NEXT:    br i1 [[Z]], label [[ONEOF:%.*]], label [[NEITHER:%.*]]
 ; CHECK:       oneof:
 ; CHECK-NEXT:    call void @foo(i1 [[XZ]])
 ; CHECK-NEXT:    call void @foo(i1 [[YZ]])
 ; CHECK-NEXT:    call void @bar(i32 [[X]])
 ; CHECK-NEXT:    call void @bar(i32 [[Y]])
 ; CHECK-NEXT:    ret void
neither:
   call void @foo(i1 %z)
   ret void
 }
 define void @testand(i32 %x, i32 %y) {
 ; CHECK-LABEL: @testand(
 ; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
 ; CHECK-NEXT:    [[Z:%.*]] = and i1 [[XZ]], [[YZ]]
-; CHECK:         [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
 ; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
-; CHECK:         [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
 ; CHECK:         [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
+; CHECK:         [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
+; CHECK:         [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
 ; CHECK:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[Z]])
 ; CHECK-NEXT:    br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]]
 ; CHECK:       both:
 ; CHECK-NEXT:    call void @foo(i1 [[XZ_0]])
 ; CHECK-NEXT:    call void @foo(i1 [[YZ_0]])
 ; CHECK-NEXT:    call void @bar(i32 [[X_0]])
 ; CHECK-NEXT:    call void @bar(i32 [[Y_0]])
 ; CHECK-NEXT:    ret void
;; Should not insert on the false edge for and
   call void @foo(i1 %z)
   ret void
 }
 define void @testandsame(i32 %x, i32 %y) {
 ; CHECK-LABEL: @testandsame(
 ; CHECK-NEXT:    [[XGT:%.*]] = icmp sgt i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[XLT:%.*]] = icmp slt i32 [[X]], 100
 ; CHECK-NEXT:    [[Z:%.*]] = and i1 [[XGT]], [[XLT]]
-; CHECK:         [[XGT_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XGT]])
 ; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
 ; CHECK:         [[X_0_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X_0]])
+; CHECK:         [[XGT_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XGT]])
 ; CHECK:         [[XLT_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XLT]])
 ; CHECK:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[Z]])
 ; CHECK-NEXT:    br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]]
 ; CHECK:       both:
 ; CHECK-NEXT:    call void @foo(i1 [[XGT_0]])
 ; CHECK-NEXT:    call void @foo(i1 [[XLT_0]])
 ; CHECK-NEXT:    call void @bar(i32 [[X_0_1]])
 ; CHECK-NEXT:    ret void
nope:
   ret void
 }
 
 define void @testandassume(i32 %x, i32 %y) {
 ; CHECK-LABEL: @testandassume(
 ; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
 ; CHECK-NEXT:    [[Z:%.*]] = and i1 [[XZ]], [[YZ]]
-; CHECK:         [[TMP1:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
-; CHECK:         [[TMP2:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
-; CHECK:         [[TMP3:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
-; CHECK:         [[TMP4:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
+; CHECK:         [[TMP1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
+; CHECK:         [[TMP2:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
+; CHECK:         [[TMP3:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
+; CHECK:         [[TMP4:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
 ; CHECK:         [[TMP5:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[Z]])
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP5]])
-; CHECK:         [[DOT0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[TMP1]])
+; CHECK:         [[DOT0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[TMP1]])
 ; CHECK:         [[DOT01:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[TMP2]])
 ; CHECK:         [[DOT02:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[TMP3]])
-; CHECK:         [[DOT03:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[TMP4]])
+; CHECK:         [[DOT03:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[TMP4]])
 ; CHECK:         [[DOT04:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[TMP5]])
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[BOTH:%.*]], label [[NOPE:%.*]]
 ; CHECK:       both:
-; CHECK-NEXT:    call void @foo(i1 [[DOT0]])
 ; CHECK-NEXT:    call void @foo(i1 [[DOT02]])
+; CHECK-NEXT:    call void @foo(i1 [[DOT03]])
+; CHECK-NEXT:    call void @bar(i32 [[DOT0]])
 ; CHECK-NEXT:    call void @bar(i32 [[DOT01]])
-; CHECK-NEXT:    call void @bar(i32 [[DOT03]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       nope:
 ; CHECK-NEXT:    call void @foo(i1 [[DOT04]])
 ; CHECK-NEXT:    ret void
 ;
   %xz = icmp eq i32 %x, 0
   %yz = icmp eq i32 %y, 0
   %z = and i1 %xz, %yz