[Dominators] Fix some edge cases for PostDomTree updating

[dmgreen]

Summary

These fix some odd cfg cases where batch-updating the post dom tree fails. Usually around infinite loops and roots ending up being different.

[kuhar]

Looks good overall, thanks for catching and fixing that.

unittests/IR/DominatorTreeBatchUpdatesTest.cpp

295

I think it's easier to read these tests when you order them by left nodes -- then it reads like IR, where for each BB you have some number of successors.
I'd even make sense to have them one line per each block, like:

1 3
3 4, 3 4
4 14
6 7, 6 9
...

[dmgreen]

Thanks. Nice idea.

I've updated the tests. I managed to manually simplify the longest one a bit too.

[kuhar]

Thanks.

I think that this patch should be also merged into the 6.0 branch before the release.

[dmgreen]

Thanks.

No objections from me. I don't know of any way that current in-tree passes will trigger these, they mostly come from batch updating post dom trees, which is not something I think happens just yet. They should be safe to go into the branch, if you think thats best.

[kuhar]

In D42247#982869, @dmgreen wrote:

Thanks.

No objections from me. I don't know of any way that current in-tree passes will trigger these, they mostly come from batch updating post dom trees, which is not something I think happens just yet. They should be safe to go into the branch, if you think thats best.

ADCE uses the batch updater to update postdominators as well, ans it's used in 6.0.

include/llvm/Support/GenericDomTreeConstruction.h

static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) {
     DT.Roots = FindRoots(DT, BUI);
     for (const NodePtr R : DT.Roots) {
       const TreeNodePtr TN = DT.getNode(R);
       // A CFG node was selected as a tree root, but the corresponding tree node
       // is not connected to the virtual root. This is because the incremental
       // algorithm does not really know or use the set of roots and can make a
       // different (implicit) decision about which nodes within an infinite loop
       // becomes a root.
-      if (DT.isVirtualRoot(TN->getIDom())) {
+      if (TN && !DT.isVirtualRoot(TN->getIDom())) {
         DEBUG(dbgs() << "Root " << BlockNamePrinter(R)
                      << " is not virtual root's child\n"
                      << "The entire tree needs to be rebuilt\n");
         // It should be possible to rotate the subtree instead of recalculating
         // the whole tree, but this situation happens extremely rarely in
         // practice.
         CalculateFromScratch(DT, BUI);
         return;
if (!ToTN) {
       DEBUG(dbgs() << "\tTo (" << BlockNamePrinter(To)
                    << ") already unreachable -- there is no edge to delete\n");
       return;
     }
 
     const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
     const TreeNodePtr NCD = DT.getNode(NCDBlock);
 
-    // To dominates From -- nothing to do.
-    if (ToTN == NCD) return;
-
+    // If To dominates From -- nothing to do.
+    if (ToTN != NCD) {
       DT.DFSInfoValid = false;
 
       const TreeNodePtr ToIDom = ToTN->getIDom();
       DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
                    << BlockNamePrinter(ToIDom) << "\n");
 
       // To remains reachable after deletion.
       // (Based on the caption under Figure 4. from the second paper.)
       if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN))
         DeleteReachable(DT, BUI, FromTN, ToTN);
       else
         DeleteUnreachable(DT, BUI, ToTN);
+    }
 
     if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
   }
 
   // Handles deletions that leave destination nodes reachable.
   static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
                               const TreeNodePtr FromTN,
                               const TreeNodePtr ToTN) {

unittests/IR/DominatorTreeBatchUpdatesTest.cpp

for (unsigned i = 0; i < 16; ++i) {
 
     auto DomUpdates = ToDomUpdates(B, Updates);
     DT.applyUpdates(DomUpdates);
     EXPECT_TRUE(DT.verify());
     PDT.applyUpdates(DomUpdates);
     EXPECT_TRUE(PDT.verify());
   }
 }
+
+// These are some odd flowgraphs, usually generated from csmith cases,
+// which are difficult on post dom trees.
+TEST(DominatorTreeBatchUpdates, InfiniteLoop) {
+  std::vector<CFGBuilder::Arc> Arcs = {
+      {"1", "2"}, {"2", "3"}, {"3", "6"}, {"3", "5"}, {"4", "5"}, {"5", "2"},
+      {"6", "3"}, {"6", "4"}};
+
+  // SplitBlock on 3 -> 5
+  std::vector<CFGBuilder::Update> Updates = {
+      {CFGInsert, {"7", "5"}},  {CFGInsert, {"3", "7"}},
+      {CFGDelete, {"3", "5"}}};
+
+  CFGHolder Holder;
+  CFGBuilder B(Holder.F, Arcs, Updates);
+  DominatorTree DT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+  PostDomTree PDT(*Holder.F);
+  EXPECT_TRUE(PDT.verify());
+
+  while (B.applyUpdate())
+    ;
+
+  auto DomUpdates = ToDomUpdates(B, Updates);
+  DT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(DT.verify());
+  PDT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(PDT.verify());
+}
+
+TEST(DominatorTreeBatchUpdates, DeadBlocks) {
+  std::vector<CFGBuilder::Arc> Arcs = {
+      {"1", "3"}, {"3", "4"}, {"3", "5"}, {"5", "6"}, {"6", "7"}, {"6", "9"}, {"4", "14"},
+      {"7", "8"}, {"8", "8"}, {"9", "10"}, {"9", "11"}, {"10", "13"}, {"11", "13"},
+      {"12", "15"}, {"12", "13"}, {"15", "13"}, {"13", "2"}, {"2", "3"}, {"13", "14"}};
+
+  // Remove dead 12 and 13,
+  // plus SplitBlock on 13 -> 14
+  std::vector<CFGBuilder::Update> Updates = {
+      {CFGDelete, {"15", "13"}},  {CFGDelete, {"12", "13"}}, {CFGDelete, {"12", "15"}},
+      {CFGInsert, {"N", "14"}},  {CFGInsert, {"13", "N"}}, {CFGDelete, {"13", "14"}}};
+
+  CFGHolder Holder;
+  CFGBuilder B(Holder.F, Arcs, Updates);
+  DominatorTree DT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+  PostDomTree PDT(*Holder.F);
+  EXPECT_TRUE(PDT.verify());
+
+  while (B.applyUpdate())
+    ;
+
+  auto DomUpdates = ToDomUpdates(B, Updates);
+  DT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(DT.verify());
+  PDT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(PDT.verify());
+}
+
+TEST(DominatorTreeBatchUpdates, InfiniteLoop2) {
+  std::vector<CFGBuilder::Arc> Arcs = {
+      {"1", "2"}, {"2", "6"}, {"2", "3"}, {"3", "4"},
+      {"4", "5"}, {"4", "6"}, {"5", "4"}, {"6", "2"}};
+
+  // SplitBlock on 4 -> 6
+  std::vector<CFGBuilder::Update> Updates = {
+      {CFGInsert, {"N", "6"}},  {CFGInsert, {"4", "N"}}, {CFGDelete, {"4", "6"}}};
+
+  CFGHolder Holder;
+  CFGBuilder B(Holder.F, Arcs, Updates);
+  DominatorTree DT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+  PostDomTree PDT(*Holder.F);
+  EXPECT_TRUE(PDT.verify());
+
+  while (B.applyUpdate())
+    ;
+
+  auto DomUpdates = ToDomUpdates(B, Updates);
+  DT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(DT.verify());
+  PDT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(PDT.verify());
+}