[PostDom] document the current handling of infinite loops and unreachables

[grosser]

Summary

As we are in the process of changing the behavior of how the post-dominator tree
is computed, make sure we have some more test coverage in this area.

Current inconsistencies:

• Newly unreachable nodes are not added as new roots, in case the PDT is updated but not rebuilt.
• Newly unreachable loops are not added to the CFG at all (neither when building from scratch nor when updating the CFG). This is inconsistent with the fact that unreachables are added to the PDT, but unreachable loops not. On the other side, PDT relationships are not loosened at the moment in cases where new unreachable loops are built.

This commit is providing additional test coverage for
https://reviews.llvm.org/D35851

[grosser]

@kuhar, @dberlin : I came up with these test cases while reviewing D35851.

I understand that these test cases will be changed in the future. However, I think these test cases are useful to understand the problem D35851 intends to resolve and the impact the chosen solution has. While we already have quite some test coverage thanks to @kuhar, we have little tests that verify
the update behavior of PDT after changes that introduce/remove virtual nodes. This is shown by the fact, that the first test case (construction of unreachables) illustrates a bug where we forget to add a new virtual exit node.

I would like to commit this change, to have some more test coverage for D35851 and especially to make the impact of D35851 more clear.

[kuhar]

In D36107#826573, @grosser wrote:

we have little tests that verify the update behavior of PDT after changes that introduce/remove virtual nodes. This is shown by the fact, that the first test case (construction of unreachables) illustrates a bug where we forget to add a new virtual exit node.

I would like to commit this change, to have some more test coverage for D36107 and especially to make the impact of D36017 more clear.

Just to clarify a bit: the current behavior posdominator updates is just broken when it comes to root handling -- it just happens that the verifier is broken in an analogous way and blindly trusts the set of roots inside a dominator tree. If for some reason we wanted keep not including infinite loops in postdominators, then it would be still possible to fix the root-finding behavior on updates. I mean, this issue is a bit orthogonal to what D36017 tries to do.

[kuhar]

unittests/IR/DominatorTreeTest.cpp

330 ↗

(On Diff #108983)

s/node/CFG node?

417 ↗

(On Diff #108983)

Doesn't this test case start with two infinite loops and breaks one of them?
Maybe it would be better to show a case when there used to be an exit which got disconnected?
(Eg. additional initial edge C -> E which gets deleted in an update.)

434 ↗

(On Diff #108983)

The comments in GenericDomTreeConstruction use reverse-unreachable instead of backwards unreachable. I think it would be better to stick with one name for it everywhere.

[grosser]

Address kuhar's comments:

node -> CFG node

Add the second suggested test case

Use reverse unreachable

[kuhar]

Two nitpicks, looks good otherwise.

unittests/IR/DominatorTreeTest.cpp

453 ↗

(On Diff #109062)

reverse-unreachable

540 ↗

(On Diff #109062)

reverse -unreachable

[kuhar]

@grosser

I've just realized that I didn't notice the TODOs in this patch when I did a code review for it.

// TODO: Can we change the PDT definition such that C remains part of the
//       CFG, at best without loosing the dominance relation D postdom B.

I don't think we reached an agreement on the second part of the TODO, as the "at best" might imply. Could you reword the second part of the comment to be less ambiguous and not to suggest that?

And a very minor nitpick: isn't it supposed to be s/loosing/losing? :)

llvm/trunk/unittests/IR/DominatorTreeTest.cpp

runWithDomTree(
         EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB1));
         EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB1));
 
         EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB2));
         EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB2));
       });
 }
 
+// Verify that the PDT is correctly updated in case an edge removal results
+// in a new unreachable CFG node.
+//
+// For the following input code and initial PDT:
+//
+//          CFG                   PDT
+//
+//           A                    Exit
+//           |                     |
+//          _B                     D
+//         / | \                   |
+//        ^  v  \                  B
+//        \ /    D                / \
+//         C      \              C   A
+//                v
+//                Exit
+//
+// we verify that CFG' and PDT-updated is obtained after removal of edge C -> B.
+//
+//          CFG'               PDT-updated
+//
+//           A                    Exit
+//           |                     |
+//           B                     D
+//           | \                   |
+//           v  \                  B
+//          /    D                  \
+//         C      \                  A
+//        |       v
+// unreachable    Exit
+//
+// WARNING: PDT-updated is inconsistent with PDT-recalculated, which is
+//          constructed from CFG' when recalculating the PDT from scratch.
+//
+//         PDT-recalculated
+//
+//            Exit
+//           / | \
+//          C  B  D
+//             |
+//             A
+//
+// TODO: document the wanted behavior after resolving this inconsistency.
+TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) {
+  StringRef ModuleString =
+      "define void @f() {\n"
+      "A:\n"
+      "  br label %B\n"
+      "B:\n"
+      "  br i1 undef, label %D, label %C\n"
+      "C:\n"
+      "  br label %B\n"
+      "D:\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();
+
+        FI++;
+        BasicBlock *B = &*FI++;
+        BasicBlock *C = &*FI++;
+        BasicBlock *D = &*FI++;
+
+        assert(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+
+        C->getTerminator()->eraseFromParent();
+        new UnreachableInst(C->getContext(), C);
+
+        DT->deleteEdge(C, B);
+        PDT->deleteEdge(C, B);
+
+        EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+        EXPECT_EQ(PDT->getNode(C), nullptr);
+
+        PDT->recalculate(F);
+
+        EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+        EXPECT_NE(PDT->getNode(C), nullptr);
+      });
+}
+
+// Verify that the PDT is correctly updated in case an edge removal results
+// in an infinite loop.
+//
+// Test case:
+//
+//          CFG                   PDT
+//
+//           A                    Exit
+//           |                     |
+//          _B                     D
+//         / | \                   |
+//        ^  v  \                  B
+//        \ /    D                / \
+//         C      \              C   A
+//        / \      v
+//       ^  v      Exit
+//        \_/
+//
+// After deleting the edge C->B, C is part of an infinite reverse-unreachable
+// loop:
+//
+//          CFG'                   PDT'
+//
+//           A                    Exit
+//           |                     |
+//           B                     D
+//           | \                   |
+//           v  \                  B
+//          /    D                  \
+//         C      \                  A
+//        / \      v
+//       ^  v      Exit
+//        \_/
+//
+// In PDT, D post-dominates B. We verify that this post-dominance
+// relation is preserved _after_ deleting the edge C->B from CFG.
+//
+// As C now becomes reverse-unreachable, it is not anymore part of the
+// PDT. We also verify this property.
+//
+// TODO: Can we change the PDT definition such that C remains part of the
+//       CFG, at best without loosing the dominance relation D postdom B.
+TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop) {
+  StringRef ModuleString =
+      "define void @f() {\n"
+      "A:\n"
+      "  br label %B\n"
+      "B:\n"
+      "  br i1 undef, label %D, label %C\n"
+      "C:\n"
+      "  switch i32 undef, label %C [\n"
+      "    i32 0, label %B\n"
+      "  ]\n"
+      "D:\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();
+
+        FI++;
+        BasicBlock *B = &*FI++;
+        BasicBlock *C = &*FI++;
+        BasicBlock *D = &*FI++;
+
+        assert(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+
+        auto SwitchC = cast<SwitchInst>(C->getTerminator());
+        SwitchC->removeCase(SwitchC->case_begin());
+        DT->deleteEdge(C, B);
+        PDT->deleteEdge(C, B);
+
+        EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+        EXPECT_EQ(PDT->getNode(C), nullptr);
+
+        PDT->recalculate(F);
+
+        EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+        EXPECT_EQ(PDT->getNode(C), nullptr);
+      });
+}
+
+// Verify that the PDT is correctly updated in case an edge removal results
+// in an infinite loop.
+//
+// Test case:
+//
+//          CFG                   PDT
+//
+//           A                    Exit
+//           |                   / | \
+//           B--                C  B  D
+//           |  \                  |
+//           v   \                 A
+//          /     D
+//         C--C2   \
+//        / \  \    v
+//       ^  v  --Exit
+//        \_/
+//
+// After deleting the edge C->E, C is part of an infinite reverse-unreachable
+// loop:
+//
+//          CFG'                   PDT'
+//
+//           A                    Exit
+//           |                     |
+//           B                     D
+//           | \                   |
+//           v  \                  B
+//          /    D                  \
+//         C      \                  A
+//        / \      v
+//       ^  v      Exit
+//        \_/
+//
+// In PDT, D does not post-dominate B. After the edge C->E is removed, a new
+// post-dominance relation is introduced.
+//
+// As C now becomes reverse-unreachable, it is not anymore part of the
+// PDT. We also verify this property.
+//
+// TODO: Can we change the PDT definition such that C remains part of the
+//       CFG, at best without loosing the dominance relation D postdom B.
+TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop2) {
+  StringRef ModuleString =
+      "define void @f() {\n"
+      "A:\n"
+      "  br label %B\n"
+      "B:\n"
+      "  br i1 undef, label %D, label %C\n"
+      "C:\n"
+      "  switch i32 undef, label %C [\n"
+      "    i32 0, label %C2\n"
+      "  ]\n"
+      "C2:\n"
+      "  ret void\n"
+      "D:\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();
+
+        FI++;
+        BasicBlock *B = &*FI++;
+        BasicBlock *C = &*FI++;
+        BasicBlock *C2 = &*FI++;
+        BasicBlock *D = &*FI++;
+
+        auto SwitchC = cast<SwitchInst>(C->getTerminator());
+        SwitchC->removeCase(SwitchC->case_begin());
+        DT->deleteEdge(C, C2);
+        PDT->deleteEdge(C, C2);
+        C2->eraseFromParent();
+
+        EXPECT_EQ(DT->getNode(C2), nullptr);
+        PDT->eraseNode(C2);
+
+        EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+        EXPECT_EQ(PDT->getNode(C), nullptr);
+        EXPECT_EQ(PDT->getNode(C2), nullptr);
+
+        PDT->recalculate(F);
+
+        EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+        EXPECT_EQ(PDT->getNode(C), nullptr);
+        EXPECT_EQ(PDT->getNode(C2), nullptr);
+      });
+}
+
 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);
 }