[PredicateInfo] Replace pointer comparisons with deterministic compares.

[fhahn]

Summary

Currently there are a few pointer comparisons in ValueDFS_Compare, which
can cause non-deterministic ordering when materializing values. There
are 2 cases this patch fixes:

1. Order defs before uses used to compare pointers, which guarantees defs before uses, but causes non-deterministic ordering between 2 uses or 2 defs, depending on the allocation order. By converting the pointers to booleans, we can circumvent that problem.

2. comparePHIRelated was comparing the basic block pointers of edges, which also results in a non-deterministic order and is also not really meaningful for ordering. By ordering by their destination DFS numbers we guarantee a deterministic order.

For the example below, we can end up with 2 different uselist orderings,
when running opt -mem2reg -ipsccp hundreds of times. Because the
non-determinism is caused by allocation ordering, we cannot reproduce it
with ipsccp alone.

declare i32 @hoge() local_unnamed_addr #0

define dso_local i32 @ham(i8* %arg, i8* %arg1) #0 {
bb:
  %tmp = alloca i32
  %tmp2 = alloca i32, align 4
  br label %bb19

bb4:                                              ; preds = %bb20
  br label %bb6

bb6:                                              ; preds = %bb4
  %tmp7 = call i32 @hoge()
  store i32 %tmp7, i32* %tmp
  %tmp8 = load i32, i32* %tmp
  %tmp9 = icmp eq i32 %tmp8, 912730082
  %tmp10 = load i32, i32* %tmp
  br i1 %tmp9, label %bb11, label %bb16

bb11:                                             ; preds = %bb6
  unreachable

bb13:                                             ; preds = %bb20
  br label %bb14

bb14:                                             ; preds = %bb13
  %tmp15 = load i32, i32* %tmp
  br label %bb16

bb16:                                             ; preds = %bb14, %bb6
  %tmp17 = phi i32 [ %tmp10, %bb6 ], [ 0, %bb14 ]
  br label %bb19

bb18:                                             ; preds = %bb20
  unreachable

bb19:                                             ; preds = %bb16, %bb
  br label %bb20

bb20:                                             ; preds = %bb19
  indirectbr i8* null, [label %bb4, label %bb13, label %bb18]
}

[fhahn]

Fix wording in assert messages.

[fhahn]

ping

[efriedma]

llvm/lib/Transforms/Utils/PredicateInfo.cpp

151 ↗

(On Diff #210317)

Isn't isAU always equal to !isADef?

198 ↗

(On Diff #210317)

Do you really need to compare AOut? getDFSNumIn() should be unique for every domtree node.

[fhahn]

Address Eli's comments.

[fhahn]

Remove some unnecessary comparisons of DSF out numbers.

[fhahn]

llvm/lib/Transforms/Utils/PredicateInfo.cpp

151 ↗

(On Diff #210317)

For edge only entries, both are null, but we still only need one.

198 ↗

(On Diff #210317)

Thanks, I was going with the existing code to start with, but only comparing in numbers should be fine here (and a few other places I also adjusted)

[efriedma]

LGTM with one nit.

llvm/test/Transforms/SCCP/ipsccp-predinfo-uselists.ll

2 ↗

(On Diff #211784)

Is there any reason to add "preserve-ll-uselistorder" if you aren't actually going to CHECK it?

[fhahn]

llvm/test/Transforms/SCCP/ipsccp-predinfo-uselists.ll

2 ↗

(On Diff #211784)

Nope, when starting to look at this issue, I suspected uselists to cause the problem, but it's not related and I'll drop it before committing,

[fhahn]

Thanks Eli!

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

if (ArgA && ArgB)
     return ArgA->getArgNo() < ArgB->getArgNo();
   return OI.dfsBefore(cast<Instruction>(A), cast<Instruction>(B));
 }
 
 // This compares ValueDFS structures, creating OrderedBasicBlocks where
 // necessary to compare uses/defs in the same block.  Doing so allows us to walk
 // the minimum number of instructions necessary to compute our def/use ordering.
 struct ValueDFS_Compare {
+  DominatorTree &DT;
   OrderedInstructions &OI;
-  ValueDFS_Compare(OrderedInstructions &OI) : OI(OI) {}
+  ValueDFS_Compare(DominatorTree &DT, OrderedInstructions &OI)
+      : DT(DT), OI(OI) {}
 
   bool operator()(const ValueDFS &A, const ValueDFS &B) const {
     if (&A == &B)
       return false;
     // The only case we can't directly compare them is when they in the same
     // block, and both have localnum == middle.  In that case, we have to use
     // comesbefore to see what the real ordering is, because they are in the
     // same basic block.
 
-    bool SameBlock = std::tie(A.DFSIn, A.DFSOut) == std::tie(B.DFSIn, B.DFSOut);
+    assert((A.DFSIn != B.DFSIn || A.DFSOut == B.DFSOut) &&
+           "Equal DFS-in numbers imply equal out numbers");
+    bool SameBlock = A.DFSIn == B.DFSIn;
 
     // We want to put the def that will get used for a given set of phi uses,
     // before those phi uses.
     // So we sort by edge, then by def.
     // Note that only phi nodes uses and defs can come last.
     if (SameBlock && A.LocalNum == LN_Last && B.LocalNum == LN_Last)
       return comparePHIRelated(A, B);
 
+    bool isADef = A.Def;
+    bool isBDef = B.Def;
     if (!SameBlock || A.LocalNum != LN_Middle || B.LocalNum != LN_Middle)
-      return std::tie(A.DFSIn, A.DFSOut, A.LocalNum, A.Def, A.U) <
-             std::tie(B.DFSIn, B.DFSOut, B.LocalNum, B.Def, B.U);
+      return std::tie(A.DFSIn, A.LocalNum, isADef) <
+             std::tie(B.DFSIn, B.LocalNum, isBDef);
     return localComesBefore(A, B);
   }
 
   // For a phi use, or a non-materialized def, return the edge it represents.
   const std::pair<BasicBlock *, BasicBlock *>
   getBlockEdge(const ValueDFS &VD) const {
     if (!VD.Def && VD.U) {
       auto *PHI = cast<PHINode>(VD.U->getUser());
       return std::make_pair(PHI->getIncomingBlock(*VD.U), PHI->getParent());
     }
     // This is really a non-materialized def.
     return ::getBlockEdge(VD.PInfo);
   }
 
   // For two phi related values, return the ordering.
   bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const {
-    auto &ABlockEdge = getBlockEdge(A);
-    auto &BBlockEdge = getBlockEdge(B);
-    // Now sort by block edge and then defs before uses.
-    return std::tie(ABlockEdge, A.Def, A.U) < std::tie(BBlockEdge, B.Def, B.U);
+    BasicBlock *ASrc, *ADest, *BSrc, *BDest;
+    std::tie(ASrc, ADest) = getBlockEdge(A);
+    std::tie(BSrc, BDest) = getBlockEdge(B);
+
+#ifndef NDEBUG
+    // This function should only be used for values in the same BB, check that.
+    DomTreeNode *DomASrc = DT.getNode(ASrc);
+    DomTreeNode *DomBSrc = DT.getNode(BSrc);
+    assert(DomASrc->getDFSNumIn() == (unsigned)A.DFSIn &&
+           "DFS numbers for A should match the ones of the source block");
+    assert(DomBSrc->getDFSNumIn() == (unsigned)B.DFSIn &&
+           "DFS numbers for B should match the ones of the source block");
+    assert(A.DFSIn == B.DFSIn && "Values must be in the same block");
+#endif
+    (void)ASrc;
+    (void)BSrc;
+
+    // Use DFS numbers to compare destination blocks, to guarantee a
+    // deterministic order.
+    DomTreeNode *DomADest = DT.getNode(ADest);
+    DomTreeNode *DomBDest = DT.getNode(BDest);
+    unsigned AIn = DomADest->getDFSNumIn();
+    unsigned BIn = DomBDest->getDFSNumIn();
+    bool isADef = A.Def;
+    bool isBDef = B.Def;
+    assert((!A.Def || !A.U) && (!B.Def || !B.U) &&
+           "Def and U cannot be set at the same time");
+    // Now sort by edge destination and then defs before uses.
+    return std::tie(AIn, isADef) < std::tie(BIn, isBDef);
   }
 
   // Get the definition of an instruction that occurs in the middle of a block.
   Value *getMiddleDef(const ValueDFS &VD) const {
     if (VD.Def)
       return VD.Def;
     // It's possible for the defs and uses to be null.  For branches, the local
     // numbering will say the placed predicaeinfos should go first (IE

 // 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(SmallVectorImpl<Value *> &OpsToRename) {
-  ValueDFS_Compare Compare(OI);
+  ValueDFS_Compare Compare(DT, OI);
   // Compute liveness, and rename in O(uses) per Op.
   for (auto *Op : OpsToRename) {
     LLVM_DEBUG(dbgs() << "Visiting " << *Op << "\n");
     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/SCCP/ipsccp-predinfo-order.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -ipsccp -S %s | FileCheck %s
+
+declare i32 @hoge()
+
+define dso_local i32 @ham(i8* %arg, i8* %arg1) {
+; CHECK-LABEL: @ham(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[TMP:%.*]] = alloca i32
+; CHECK-NEXT:    [[TMP2:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    br label [[BB19:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br label [[BB6:%.*]]
+; CHECK:       bb6:
+; CHECK-NEXT:    [[TMP7:%.*]] = call i32 @hoge()
+; CHECK-NEXT:    store i32 [[TMP7]], i32* [[TMP]]
+; CHECK-NEXT:    [[TMP8:%.*]] = load i32, i32* [[TMP]]
+; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], 912730082
+; CHECK-NEXT:    [[TMP10:%.*]] = load i32, i32* [[TMP]]
+; CHECK-NEXT:    br i1 [[TMP9]], label [[BB11:%.*]], label [[BB16:%.*]]
+; CHECK:       bb11:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb13:
+; CHECK-NEXT:    br label [[BB14:%.*]]
+; CHECK:       bb14:
+; CHECK-NEXT:    [[TMP15:%.*]] = load i32, i32* [[TMP]]
+; CHECK-NEXT:    br label [[BB16]]
+; CHECK:       bb16:
+; CHECK-NEXT:    [[TMP17:%.*]] = phi i32 [ [[TMP10]], [[BB6]] ], [ 0, [[BB14]] ]
+; CHECK-NEXT:    br label [[BB19]]
+; CHECK:       bb18:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb19:
+; CHECK-NEXT:    br label [[BB20:%.*]]
+; CHECK:       bb20:
+; CHECK-NEXT:    indirectbr i8* null, [label [[BB4:%.*]], label [[BB13:%.*]], label %bb18]
+;
+bb:
+  %tmp = alloca i32
+  %tmp2 = alloca i32, align 4
+  br label %bb19
+
+bb4:                                              ; preds = %bb20
+  br label %bb6
+
+bb6:                                              ; preds = %bb4
+  %tmp7 = call i32 @hoge()
+  store i32 %tmp7, i32* %tmp
+  %tmp8 = load i32, i32* %tmp
+  %tmp9 = icmp eq i32 %tmp8, 912730082
+  %tmp10 = load i32, i32* %tmp
+  br i1 %tmp9, label %bb11, label %bb16
+
+bb11:                                             ; preds = %bb6
+  unreachable
+
+bb13:                                             ; preds = %bb20
+  br label %bb14
+
+bb14:                                             ; preds = %bb13
+  %tmp15 = load i32, i32* %tmp
+  br label %bb16
+
+bb16:                                             ; preds = %bb14, %bb6
+  %tmp17 = phi i32 [ %tmp10, %bb6 ], [ 0, %bb14 ]
+  br label %bb19
+
+bb18:                                             ; preds = %bb20
+  unreachable
+
+bb19:                                             ; preds = %bb16, %bb
+  br label %bb20
+
+bb20:                                             ; preds = %bb19
+  indirectbr i8* null, [label %bb4, label %bb13, label %bb18]
+}