[IDF] Enforce the returned blocks to be sorted.

[mzolotukhin]

Summary

Currently the order of blocks returned by IDF::calculate can be
non-deterministic. This was discovered in several attempts to enable
SSAUpdaterBulk for JumpThreading (which led to miscompare in bootstrap between
stage 3 and stage4). Originally, the blocks were put into a priority queue with
a depth level as their key, and this patch adds a DFSIn number as a second key
to specify a deterministic order across blocks from one level.

The solution was suggested by Daniel Berlin.

[• dberlin]

Looks good to me. You may want to make a unit test for this.
It should only require three blocks.

[mzolotukhin]

Thanks!

llvm/trunk/lib/Analysis/IteratedDominanceFrontier.cpp

 #include "llvm/IR/Dominators.h"
 #include <queue>
 
 namespace llvm {
 template <class NodeTy, bool IsPostDom>
 void IDFCalculator<NodeTy, IsPostDom>::calculate(
     SmallVectorImpl<BasicBlock *> &PHIBlocks) {
   // Use a priority queue keyed on dominator tree level so that inserted nodes
-  // are handled from the bottom of the dominator tree upwards.
-  typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
+  // are handled from the bottom of the dominator tree upwards. We also augment
+  // the level with a DFS number to ensure that the blocks are ordered in a
+  // deterministic way.
+  typedef std::pair<DomTreeNode *, std::pair<unsigned, unsigned>>
+      DomTreeNodePair;
   typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
                               less_second> IDFPriorityQueue;
   IDFPriorityQueue PQ;
 
+  DT.updateDFSNumbers();
+
   for (BasicBlock *BB : *DefBlocks) {
     if (DomTreeNode *Node = DT.getNode(BB))
-      PQ.push({Node, Node->getLevel()});
+      PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
   }
 
   SmallVector<DomTreeNode *, 32> Worklist;
   SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
   SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
 
   while (!PQ.empty()) {
     DomTreeNodePair RootPair = PQ.top();
     PQ.pop();
     DomTreeNode *Root = RootPair.first;
-    unsigned RootLevel = RootPair.second;
+    unsigned RootLevel = RootPair.second.first;
 
     // Walk all dominator tree children of Root, inspecting their CFG edges with
     // targets elsewhere on the dominator tree. Only targets whose level is at
     // most Root's level are added to the iterated dominance frontier of the
     // definition set.
 
     Worklist.clear();
     Worklist.push_back(Root);
while (!Worklist.empty()) {
           continue;
 
         BasicBlock *SuccBB = SuccNode->getBlock();
         if (useLiveIn && !LiveInBlocks->count(SuccBB))
           continue;
 
         PHIBlocks.emplace_back(SuccBB);
         if (!DefBlocks->count(SuccBB))
-          PQ.push(std::make_pair(SuccNode, SuccLevel));
+          PQ.push(std::make_pair(
+              SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
       }
 
       for (auto DomChild : *Node) {
         if (VisitedWorklist.insert(DomChild).second)
           Worklist.push_back(DomChild);
       }
     }
   }
 }
 
 template class IDFCalculator<BasicBlock *, false>;
 template class IDFCalculator<Inverse<BasicBlock *>, true>;
 }

llvm/trunk/unittests/IR/DominatorTreeTest.cpp

 //===- llvm/unittests/IR/DominatorTreeTest.cpp - Constants unit tests -----===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include <random>
 #include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/IteratedDominanceFrontier.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/SourceMgr.h"
 #include "CFGBuilder.h"
runWithDomTree(
         DominatorTree NDT(F);
         EXPECT_EQ(DT->compare(NDT), 0);
 
         PostDomTree NPDT(F);
         EXPECT_EQ(PDT->compare(NPDT), 0);
       });
 }
 
+// Verify that the IDF returns blocks in a deterministic way.
+//
+// Test case:
+//
+//          CFG
+//
+//          (A)
+//          / \
+//         /   \
+//       (B)   (C)
+//        |\   /|
+//        |  X  |
+//        |/   \|
+//       (D)   (E)
+//
+// IDF for block B is {D, E}, and the order of blocks in this list is defined by
+// their 1) level in dom-tree and 2) DFSIn number if the level is the same.
+//
+TEST(DominatorTree, IDFDeterminismTest) {
+  StringRef ModuleString =
+      "define void @f() {\n"
+      "A:\n"
+      "  br i1 undef, label %B, label %C\n"
+      "B:\n"
+      "  br i1 undef, label %D, label %E\n"
+      "C:\n"
+      "  br i1 undef, label %D, label %E\n"
+      "D:\n"
+      "  ret void\n"
+      "E:\n"
+      "  ret void\n"
+      "}\n";
+
+  // Parse the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+
+  runWithDomTree(
+      *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) {
+        Function::iterator FI = F.begin();
+
+        BasicBlock *A = &*FI++;
+        BasicBlock *B = &*FI++;
+        BasicBlock *C = &*FI++;
+        BasicBlock *D = &*FI++;
+        BasicBlock *E = &*FI++;
+        (void)C;
+
+        DT->updateDFSNumbers();
+        ForwardIDFCalculator IDF(*DT);
+        SmallPtrSet<BasicBlock *, 1> DefBlocks;
+        DefBlocks.insert(B);
+        IDF.setDefiningBlocks(DefBlocks);
+
+        SmallVector<BasicBlock *, 32> IDFBlocks;
+        SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
+        IDF.resetLiveInBlocks();
+        IDF.calculate(IDFBlocks);
+
+
+        EXPECT_EQ(IDFBlocks.size(), 2UL);
+        EXPECT_EQ(DT->getNode(A)->getDFSNumIn(), 0UL);
+        EXPECT_EQ(IDFBlocks[0], D);
+        EXPECT_EQ(IDFBlocks[1], E);
+        EXPECT_TRUE(DT->getNode(IDFBlocks[0])->getDFSNumIn() <
+                    DT->getNode(IDFBlocks[1])->getDFSNumIn());
+      });
+}
+
 namespace {
 const auto Insert = CFGBuilder::ActionKind::Insert;
 const auto Delete = CFGBuilder::ActionKind::Delete;
 
 bool CompUpdates(const CFGBuilder::Update &A, const CFGBuilder::Update &B) {
   return std::tie(A.Action, A.Edge.From, A.Edge.To) <
          std::tie(B.Action, B.Edge.From, B.Edge.To);
 }