[PredicateInfo] Order instructions in different BBs by DFSNumIn.

[fhahn]

Summary

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.

[efriedma]

because values have slightly different labels

Not sure you're diagnosing the issue correctly; IR optimizations shouldn't care about the names of instructions/basic blocks, as far as I know. But in any case, we need to fix this because a bad sort predicate causes undefined behavior.

Can you think of any way to write a testcase for this?

lib/Transforms/Utils/PredicateInfo.cpp

110

Please fix this comment to note that this only works for instructions in the same BB.

557

There shouldn't be null values in OpSet; you can use dyn_cast instead of dyn_cast_or_null.

[fhahn]

In D48230#1134015, @efriedma wrote:

because values have slightly different labels

Not sure you're diagnosing the issue correctly; IR optimizations shouldn't care about the names of instructions/basic blocks, as far as I know. But in any case, we need to fix this because a bad sort predicate causes undefined behavior.

Yep I think the issue I hit because of this was not related to IR optimization, but something in the strtab generation in codegen.

Can you think of any way to write a testcase for this?

I suppose I could add a test case which would visit ops in different orders without this patch and add checks to make sure they are visited in the expected order?

[klimek]

Florian: did you manually add Danny on this (the account is disabled and I'm trying to figure out where / how folks are added).

[efriedma]

@klimek I think he just replied to the llvm-commits email.

[efriedma]

Oh, wait, you mean in the "Reviewers" field; nevermind.

[fhahn]

In D48230#1134350, @klimek wrote:

Florian: did you manually add Danny on this (the account is disabled and I'm trying to figure out where / how folks are added).

Yes I think I added his account as reviewer when creating this patch. I did not realize that the account was slightly grey compared to the others in the search drop down. Sorry about that.

[fhahn]

I moved the logic to OrderedInstructions::comesBefore, because I think it makes sense there and has potential to be useful in other places too. I've also added a test case where the collected values are visited in non-deterministic order without this patch and added a debug line to easily check the order.

If that is not desirable, I think I could come up with a larger test case, which also exposes the problem, but might not fail as reliable without this patch.

[efriedma]

lib/Transforms/Utils/OrderedInstructions.cpp

17

localDominates.

41

Maybe rename this dfsBefore, so it's more clear what it means by "before"?

test/Transforms/Util/PredicateInfo/ordering.ll

1

Need a REQUIRES line to use -debug.

Instead of checking debug output, could we check the use-list order? (-preserve-ll-uselistorder)

[fhahn]

Renamed functions and added REQUIRES: assert

I had a look at verify-uselistorder, but I am not sure how it would help with the test unfortunately. The order of OpsToRename is unrelated to the use-list order I think. But I am probably missing something about using uselistorder when testing.

[efriedma]

LGTM

Maybe the use list order isn't affected in this exact testcase. In general, the order ssa.copy intrinsics are inserted matters, though.

include/llvm/Transforms/Utils/OrderedInstructions.h

 class OrderedInstructions {
   /// Used to check dominance for instructions in same basic block.
   mutable DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>>
       OBBMap;
 
   /// 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 localComesBefore(const Instruction *, const Instruction *) const;
+
 public:
   /// Constructor.
   OrderedInstructions(DominatorTree *DT) : DT(DT) {}
 
   /// 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 comesBefore(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
   /// this basic block.
   void invalidateBlock(const BasicBlock *BB) { OBBMap.erase(BB); }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H

lib/Transforms/Utils/OrderedInstructions.cpp

 //===-- OrderedInstructions.cpp - Instruction dominance function ---------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines utility to check dominance relation of 2 instructions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/OrderedInstructions.h"
 using namespace llvm;
 
-/// 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,
+bool OrderedInstructions::localComesBefore(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();
-  // 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);
-  }
+
+/// 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 {
+  // Use ordered basic block to do dominance check in case the 2 instructions
+  // are in the same basic block.
+  if (InstA->getParent() == InstB->getParent())
+    return localComesBefore(InstA, InstB);
   return DT->dominates(InstA->getParent(), InstB->getParent());
 }
+
+bool OrderedInstructions::comesBefore(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 localComesBefore(InstA, InstB);
+
+  DomTreeNode *DA = DT->getNode(InstA->getParent());
+  DomTreeNode *DB = DT->getNode(InstB->getParent());
+  return DA->getDFSNumIn() < DB->getDFSNumIn();
+}

lib/Transforms/Utils/PredicateInfo.cpp

struct ValueDFS {
   // Only one of Def or Use will be set.
   Value *Def = nullptr;
   Use *U = nullptr;
   // Neither PInfo nor EdgeOnly participate in the ordering
   PredicateBase *PInfo = nullptr;
   bool EdgeOnly = false;
 };
 
 // Perform a strict weak ordering on instructions and arguments.
 static bool valueComesBefore(OrderedInstructions &OI, const Value *A,
                              const Value *B) {
   auto *ArgA = dyn_cast_or_null<Argument>(A);
   auto *ArgB = dyn_cast_or_null<Argument>(B);
   if (ArgA && !ArgB)
     return true;
   if (ArgB && !ArgA)
     return false;
   if (ArgA && ArgB)
     return ArgA->getArgNo() < ArgB->getArgNo();
-  return OI.dominates(cast<Instruction>(A), cast<Instruction>(B));
+  return OI.comesBefore(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 {
   OrderedInstructions &OI;
   ValueDFS_Compare(OrderedInstructions &OI) : OI(OI) {}

 // promotememtoreg and memoryssa.
 void PredicateInfo::renameUses(SmallPtrSetImpl<Value *> &OpSet) {
   // Sort OpsToRename since we are going to iterate it.
   SmallVector<Value *, 8> OpsToRename(OpSet.begin(), OpSet.end());
   auto Comparator = [&](const Value *A, const Value *B) {
     return valueComesBefore(OI, A, B);
   };
   llvm::sort(OpsToRename.begin(), OpsToRename.end(), Comparator);
   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);
     // Insert the possible copies into the def/use list.
     // They will become real copies if we find a real use for them, and never
     // created otherwise.
     for (auto &PossibleCopy : ValueInfo.Infos) {
       ValueDFS VD;

test/Transforms/Util/PredicateInfo/ordering.ll

+; 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
+}