[PredicateInfo] Order instructions in different BBs by DFSNumIn.

Using OrderedInstructions::dominates as comparator for instructions in
BBs without dominance relation can cause a non-deterministic order
between such instructions. That in turn can cause us to materialize
copies in a non-deterministic order. While this does not effect
correctness, it causes some minor non-determinism in the final generated
code, because values have slightly different labels.

Without this patch, running -print-predicateinfo on a reasonably large
module produces slightly different output on each run.

This patch uses the dominator trees DFSInNum to order instruction from
different BBs, which should enforce a deterministic ordering and
guarantee that dominated instructions come after the instructions that
dominate them.

Reviewers: dberlin, efriedma, davide

Reviewed By: efriedma

Differential Revision: https://reviews.llvm.org/D48230

llvm-svn: 335150

4 files changed, 118 insertions, 8 deletions

diff --git a/llvm/include/llvm/Transforms/Utils/OrderedInstructions.h b/llvm/include/llvm/Transforms/Utils/OrderedInstructions.h
index 165d4bdaa6d..7f57fde638b 100644
--- a/llvm/include/llvm/Transforms/Utils/OrderedInstructions.h
+++ b/llvm/include/llvm/Transforms/Utils/OrderedInstructions.h
@@ -35,6 +35,11 @@ class OrderedInstructions {
   /// The dominator tree of the parent function.
   DominatorTree *DT;
 
+  /// Return true if the first instruction comes before the second in the
+  /// same basic block. It will create an ordered basic block, if it does
+  /// not yet exist in OBBMap.
+  bool localDominates(const Instruction *, const Instruction *) const;
+
 public:
   /// Constructor.
   OrderedInstructions(DominatorTree *DT) : DT(DT) {}
@@ -42,6 +47,12 @@ public:
   /// Return true if first instruction dominates the second.
   bool dominates(const Instruction *, const Instruction *) const;
 
+  /// Return true if the first instruction comes before the second in the
+  /// dominator tree DFS traversal if they are in different basic blocks,
+  /// or if the first instruction comes before the second in the same basic
+  /// block.
+  bool dfsBefore(const Instruction *, const Instruction *) const;
+
   /// Invalidate the OrderedBasicBlock cache when its basic block changes.
   /// i.e. If an instruction is deleted or added to the basic block, the user
   /// should call this function to invalidate the OrderedBasicBlock cache for
diff --git a/llvm/lib/Transforms/Utils/OrderedInstructions.cpp b/llvm/lib/Transforms/Utils/OrderedInstructions.cpp
index dc780542ce6..6d0b96f6aa8 100644
--- a/llvm/lib/Transforms/Utils/OrderedInstructions.cpp
+++ b/llvm/lib/Transforms/Utils/OrderedInstructions.cpp
@@ -14,19 +14,38 @@
 #include "llvm/Transforms/Utils/OrderedInstructions.h"
 using namespace llvm;
 
+bool OrderedInstructions::localDominates(const Instruction *InstA,
+                                         const Instruction *InstB) const {
+  assert(InstA->getParent() == InstB->getParent() &&
+         "Instructions must be in the same basic block");
+
+  const BasicBlock *IBB = InstA->getParent();
+  auto OBB = OBBMap.find(IBB);
+  if (OBB == OBBMap.end())
+    OBB = OBBMap.insert({IBB, make_unique<OrderedBasicBlock>(IBB)}).first;
+  return OBB->second->dominates(InstA, InstB);
+}
+
 /// Given 2 instructions, use OrderedBasicBlock to check for dominance relation
 /// if the instructions are in the same basic block, Otherwise, use dominator
 /// tree.
 bool OrderedInstructions::dominates(const Instruction *InstA,
                                     const Instruction *InstB) const {
-  const BasicBlock *IBB = InstA->getParent();
   // Use ordered basic block to do dominance check in case the 2 instructions
   // are in the same basic block.
-  if (IBB == InstB->getParent()) {
-    auto OBB = OBBMap.find(IBB);
-    if (OBB == OBBMap.end())
-      OBB = OBBMap.insert({IBB, make_unique<OrderedBasicBlock>(IBB)}).first;
-    return OBB->second->dominates(InstA, InstB);
-  }
+  if (InstA->getParent() == InstB->getParent())
+    return localDominates(InstA, InstB);
   return DT->dominates(InstA->getParent(), InstB->getParent());
 }
+
+bool OrderedInstructions::dfsBefore(const Instruction *InstA,
+                                    const Instruction *InstB) const {
+  // Use ordered basic block in case the 2 instructions are in the same basic
+  // block.
+  if (InstA->getParent() == InstB->getParent())
+    return localDominates(InstA, InstB);
+
+  DomTreeNode *DA = DT->getNode(InstA->getParent());
+  DomTreeNode *DB = DT->getNode(InstB->getParent());
+  return DA->getDFSNumIn() < DB->getDFSNumIn();
+}
diff --git a/llvm/lib/Transforms/Utils/PredicateInfo.cpp b/llvm/lib/Transforms/Utils/PredicateInfo.cpp
index 6da3c7a90b6..38cada8cb06 100644
--- a/llvm/lib/Transforms/Utils/PredicateInfo.cpp
+++ b/llvm/lib/Transforms/Utils/PredicateInfo.cpp
@@ -118,7 +118,7 @@ static bool valueComesBefore(OrderedInstructions &OI, const Value *A,
     return false;
   if (ArgA && ArgB)
     return ArgA->getArgNo() < ArgB->getArgNo();
-  return OI.dominates(cast<Instruction>(A), cast<Instruction>(B));
+  return OI.dfsBefore(cast<Instruction>(A), cast<Instruction>(B));
 }
 
 // This compares ValueDFS structures, creating OrderedBasicBlocks where
@@ -557,6 +557,7 @@ void PredicateInfo::renameUses(SmallPtrSetImpl<Value *> &OpSet) {
   ValueDFS_Compare Compare(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);
diff --git a/llvm/test/Transforms/Util/PredicateInfo/ordering.ll b/llvm/test/Transforms/Util/PredicateInfo/ordering.ll
new file mode 100644
index 00000000000..519168a58b4
--- /dev/null
+++ b/llvm/test/Transforms/Util/PredicateInfo/ordering.ll
@@ -0,0 +1,79 @@
+; REQUIRES: assert
+; RUN: opt -print-predicateinfo -analyze -debug < %s 2>&1 | FileCheck %s
+
+declare void @use(i32)
+
+; Make sure we are visiting the values to build predicate infos for in a
+; deterministic order.
+define i32 @test12(i32 %x, i32 %y) {
+; CHECK: Visiting i32 %x
+; CHECK: Visiting i32 %y
+; CHECK: Visiting   %lcmp = icmp eq i32 %x, 0
+; CHECK: Visiting   %lcmp2 = icmp slt i32 %y, 1000
+; CHECK: Visiting   %lcmp3 = icmp slt i32 %y.0, 900
+; CHECK: Visiting   %lcmp4 = icmp slt i32 %y.0.1, 700
+; CHECK: Visiting   %lcmp5 = icmp slt i32 %y.0.1.2, 700
+; CHECK: Visiting   %lcmp6 = icmp slt i32 %y.0.1.2.3, 700
+; CHECK: Visiting   %lcmp7 = icmp slt i32 %y.0.1.2.3.4, 700
+; CHECK: Visiting   %rcmp = icmp eq i32 %x, 0
+entry:
+  br i1 undef, label %left, label %right
+
+left:
+  %lcmp = icmp eq i32 %x, 0
+  br i1 %lcmp, label %left_cond_true, label %left_cond_false
+
+left_cond_true:
+  %lcmp2 = icmp slt i32 %y, 1000
+  br i1 %lcmp2, label %left_cond_true2, label %left_ret
+
+left_cond_true2:
+  call void @use(i32 %y)
+  %lcmp3 = icmp slt i32 %y, 900
+  br i1 %lcmp3, label %left_cond_true3, label %left_ret
+
+left_cond_true3:
+  call void @use(i32 %y)
+  %lcmp4 = icmp slt i32 %y, 700
+  br i1 %lcmp4, label %left_cond_true4, label %left_ret
+
+left_cond_true4:
+  call void @use(i32 %y)
+  %lcmp5 = icmp slt i32 %y, 700
+  br i1 %lcmp5, label %left_cond_true5, label %left_ret
+
+left_cond_true5:
+  call void @use(i32 %y)
+  %lcmp6 = icmp slt i32 %y, 700
+  br i1 %lcmp6, label %left_cond_true6, label %left_ret
+
+left_cond_true6:
+  call void @use(i32 %y)
+  %lcmp7 = icmp slt i32 %y, 700
+  br i1 %lcmp7, label %left_cond_true7, label %left_ret
+
+left_cond_true7:
+  ret i32 %y
+
+left_cond_false:
+  br label %left_ret
+
+left_ret:
+  %lres = phi i32 [ %x, %left_cond_true ], [ %x, %left_cond_false ], [ %x, %left_cond_true2 ], [ %x, %left_cond_true3 ], [ %x, %left_cond_true4 ], [ %x, %left_cond_true5 ], [ %x, %left_cond_true6 ]
+
+  ret i32 %lres
+
+right:
+  %rcmp = icmp eq i32 %x, 0
+  br i1 %rcmp, label %right_cond_true, label %right_cond_false
+
+right_cond_true:
+  br label %right_ret
+
+right_cond_false:
+  br label %right_ret
+
+right_ret:
+  %rres = phi i32 [ %x, %right_cond_true ], [ %x, %right_cond_false ]
+  ret i32 %rres
+}