From 94cf0c2801f784209755d1527d3eda78a38b8034 Mon Sep 17 00:00:00 2001
From: Alon Zakai <azakai@google.com>
Date: Thu, 26 Aug 2021 08:04:03 -0700
Subject: Dominator Tree (#4100)

Add a class to compute the dominator tree for a CFG consisting
of a list of basic blocks assumed to be in reverse postorder.

This will be useful once cfg-walker emits blocks in reverse-postorder
(which it almost does, another PR will handle that). Then we can write
optimization passes that use block dominance.
---
 test/example/domtree.cpp | 163 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 163 insertions(+)
 create mode 100644 test/example/domtree.cpp

(limited to 'test/example/domtree.cpp')

diff --git a/test/example/domtree.cpp b/test/example/domtree.cpp
new file mode 100644
index 000000000..e1b93ccc4
--- /dev/null
+++ b/test/example/domtree.cpp
@@ -0,0 +1,163 @@
+#include <cassert>
+#include <iostream>
+
+#include <cfg/domtree.h>
+#include <wasm.h>
+
+using namespace wasm;
+
+struct BasicBlock {
+  std::vector<BasicBlock*> in;
+
+  void addPred(BasicBlock* pred) { in.push_back(pred); }
+};
+
+struct CFG : public std::vector<std::unique_ptr<BasicBlock>> {
+  BasicBlock* add() {
+    emplace_back(std::make_unique<BasicBlock>());
+    return back().get();
+  }
+
+  void connect(BasicBlock* pred, BasicBlock* succ) { succ->addPred(pred); }
+};
+
+int main() {
+  // An empty CFG.
+  {
+    CFG cfg;
+
+    DomTree<BasicBlock> domTree(cfg);
+    assert(domTree.iDoms.empty());
+  }
+
+  // An CFG with just an entry.
+  {
+    CFG cfg;
+    cfg.add();
+
+    DomTree<BasicBlock> domTree(cfg);
+    assert(domTree.iDoms.size() == 1);
+    assert(domTree.iDoms[0] == Index(-1)); // the entry has no parent.
+  }
+
+  // entry -> a.
+  {
+    CFG cfg;
+    auto* entry = cfg.add();
+    auto* a = cfg.add();
+    cfg.connect(entry, a);
+
+    DomTree<BasicBlock> domTree(cfg);
+    assert(domTree.iDoms.size() == 2);
+    assert(domTree.iDoms[0] == Index(-1));
+    assert(domTree.iDoms[1] == 0); // a is dominated by the entry.
+  }
+
+  // entry and a non-connected (unreachable) block.
+  {
+    CFG cfg;
+    auto* entry = cfg.add();
+    auto* a = cfg.add();
+
+    DomTree<BasicBlock> domTree(cfg);
+    assert(domTree.iDoms.size() == 2);
+    assert(domTree.iDoms[0] == Index(-1));
+    assert(domTree.iDoms[1] == Index(-1)); // unreachables have no parent.
+  }
+
+  // entry -> a -> b -> c.
+  {
+    CFG cfg;
+    auto* entry = cfg.add();
+    auto* a = cfg.add();
+    auto* b = cfg.add();
+    auto* c = cfg.add();
+    cfg.connect(entry, a);
+    cfg.connect(a, b);
+    cfg.connect(b, c);
+
+    DomTree<BasicBlock> domTree(cfg);
+    assert(domTree.iDoms.size() == 4);
+    assert(domTree.iDoms[0] == Index(-1));
+    assert(domTree.iDoms[1] == 0);
+    assert(domTree.iDoms[2] == 1);
+    assert(domTree.iDoms[3] == 2);
+  }
+
+  // An if:
+  //            b
+  //           / \
+  // entry -> a   d
+  //           \ /
+  //            c
+  {
+    CFG cfg;
+    auto* entry = cfg.add();
+    auto* a = cfg.add();
+    auto* b = cfg.add();
+    auto* c = cfg.add();
+    auto* d = cfg.add();
+    cfg.connect(entry, a);
+    cfg.connect(a, b);
+    cfg.connect(a, c);
+    cfg.connect(b, d);
+    cfg.connect(c, d);
+
+    DomTree<BasicBlock> domTree(cfg);
+    assert(domTree.iDoms.size() == 5);
+    assert(domTree.iDoms[0] == Index(-1));
+    assert(domTree.iDoms[1] == 0); // a
+    assert(domTree.iDoms[2] == 1); // b
+    assert(domTree.iDoms[3] == 1); // c
+    assert(domTree.iDoms[4] == 1); // d is also dominated by a.
+  }
+
+  // A loop:
+  //
+  // entry -> a -> b -> c -> d
+  //               ^         |
+  //               |         |
+  //               \---------/
+  {
+    CFG cfg;
+    auto* entry = cfg.add();
+    auto* a = cfg.add();
+    auto* b = cfg.add();
+    auto* c = cfg.add();
+    auto* d = cfg.add();
+    cfg.connect(entry, a);
+    cfg.connect(a, b);
+    cfg.connect(b, c);
+    cfg.connect(c, d);
+    cfg.connect(d, b);
+
+    DomTree<BasicBlock> domTree(cfg);
+    assert(domTree.iDoms.size() == 5);
+    assert(domTree.iDoms[0] == Index(-1));
+    assert(domTree.iDoms[1] == 0); // a
+    assert(domTree.iDoms[2] == 1); // b, the loop entry, is dominated by a
+    assert(domTree.iDoms[3] == 2); // c, the loop "middle", is dominated by b
+    assert(domTree.iDoms[4] == 3); // d, the loop "end", is dominated by c
+  }
+
+  // Subsequent blocks after an unreachable one.
+  //
+  // entry   a -> b
+  //
+  // (a is unreachable, and b is reached by a, but in unreachable code)
+  {
+    CFG cfg;
+    auto* entry = cfg.add();
+    auto* a = cfg.add();
+    auto* b = cfg.add();
+    cfg.connect(a, b);
+
+    DomTree<BasicBlock> domTree(cfg);
+    assert(domTree.iDoms.size() == 3);
+    assert(domTree.iDoms[0] == Index(-1));
+    assert(domTree.iDoms[1] == Index(-1)); // a
+    assert(domTree.iDoms[2] == Index(-1)); // b
+  }
+
+  std::cout << "success.\n";
+}
-- 
cgit v1.2.3