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.

3 files changed, 342 insertions, 0 deletions

diff --git a/src/cfg/domtree.h b/src/cfg/domtree.h
new file mode 100644
index 000000000..5e54f7c32
--- /dev/null
+++ b/src/cfg/domtree.h
@@ -0,0 +1,178 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+//
+// Computes a dominator tree for a CFG graph, that is, for each block x we find
+// the blocks y_i that must be reached before x on any path from the entry. Each
+// block x has a single immediate dominator, the one closest to it, which forms
+// a tree structure.
+//
+// This assumes the input is reducible.
+//
+
+#ifndef domtree_h
+#define domtree_h
+
+#include "cfg-traversal.h"
+#include "wasm.h"
+
+namespace wasm {
+
+//
+// DomTree receives an input CFG which has a list of basic blocks in reverse
+// postorder. It generates the dominator tree by representing it as a vector of
+// indexes, for each block giving the index of its parent (the immediate
+// dominator) in the tree, that is,
+//
+//  iDoms[0] = a nonsense value, as the entry node has no immediate dominator
+//  iDoms[1] = the index of the immediate dominator of CFG.blocks[1]
+//  iDoms[2] = the index of the immediate dominator of CFG.blocks[2]
+//  etc.
+//
+// The BasicBlock type is assumed to have a ".in" property which declares a
+// vector of pointers to the incoming blocks, that is, the predecessors.
+template<typename BasicBlock> struct DomTree {
+  std::vector<Index> iDoms;
+
+  DomTree(std::vector<std::unique_ptr<BasicBlock>>& blocks);
+};
+
+template<typename BasicBlock>
+DomTree<BasicBlock>::DomTree(std::vector<std::unique_ptr<BasicBlock>>& blocks) {
+  // Compute the dominator tree using the "engineered algorithm" in [1]. Minor
+  // differences in notation from the source include:
+  //
+  //  * doms => iDoms. The final structure we emit is the vector of parents in
+  //    the dominator tree, and that is our public interface, so name it
+  //    explicitly as the immediate dominators.
+  //  * Indexes are reversed. The paper uses postorder indexes, i.e., the entry
+  //    node has the highest index, while we have a natural indexing since we
+  //    traverse in reverse postorder anyhow (see cfg-traversal.h), that, is,
+  //    the entry has the lowest index.
+  //  * finger1, finger2 => left, right.
+  //  * We assume the input is reducible, since wasm and Binaryen IR have that
+  //    property. This simplifies some things, see below.
+  //
+  // Otherwise this is basically a direct implementation.
+  //
+  // [1] Cooper, Keith D.; Harvey, Timothy J; Kennedy, Ken (2001). "A Simple,
+  //       Fast Dominance Algorithm" (PDF).
+  //       http://www.hipersoft.rice.edu/grads/publications/dom14.pdf
+
+  // If there are no blocks, we have nothing to do.
+  Index numBlocks = blocks.size();
+  if (numBlocks == 0) {
+    return;
+  }
+
+  // Map basic blocks to their indices.
+  std::unordered_map<BasicBlock*, Index> blockIndices;
+  for (Index i = 0; i < numBlocks; i++) {
+    blockIndices[blocks[i].get()] = i;
+  }
+
+  // Use a nonsense value to indicate what has yet to be initialized.
+  const Index nonsense = -1;
+
+  // Initialize the iDoms array. The entry starts with its own index, which is
+  // used as a guard value in effect (we will never process it, and we will fix
+  // up this value at the very end). All other nodes start with a nonsense value
+  // that indicates they have yet to be processed.
+  iDoms.resize(numBlocks, nonsense);
+  iDoms[0] = 0;
+
+  // Process the (non-entry) blocks in reverse postorder, computing the
+  // immediate dominators as we go. This returns whether we made any changes,
+  // which is used in an assertion later down.
+  auto processBlocks = [&]() {
+    bool changed = false;
+    for (Index index = 1; index < numBlocks; index++) {
+      // Loop over the predecessors. Our new parent is basically the
+      // intersection of all of theirs: our immediate dominator must precede all
+      // of them.
+      auto& preds = blocks[index]->in;
+      Index newParent = nonsense;
+      for (auto* pred : preds) {
+        auto predIndex = blockIndices[pred];
+
+        // In a reducible graph, we only need to care about the predecessors
+        // that appear before us in the reverse postorder numbering. The only
+        // predecessor that can appear *after* us is a loop backedge, but that
+        // will never dominate the loop - the loop is dominated by its single
+        // entry (since it is reducible, it has just one entry).
+        if (predIndex > index) {
+          continue;
+        }
+
+        // All of our predecessors will have been processed before us, except
+        // if they are unreachable from the entry, in which case, we can ignore
+        // them.
+        if (iDoms[predIndex] == nonsense) {
+          continue;
+        }
+
+        if (newParent == nonsense) {
+          // This is the first processed predecessor.
+          newParent = predIndex;
+          continue;
+        }
+
+        // This is an additional predecessor. Intersect it, by going back to a
+        // node that definitely dominates both possibilities. Effectively, we
+        // keep decreasing the index backwards in the reverse postorder
+        // indexing until we stop (at the latest, in the entry).
+        auto left = newParent;
+        auto right = predIndex;
+        while (left != right) {
+          while (left > right) {
+            left = iDoms[left];
+          }
+          while (right > left) {
+            right = iDoms[right];
+          }
+        }
+        newParent = left;
+      }
+
+      // Check if we found a new value here, and apply it. (We will normally
+      // always find a new value in the single pass that we run, but we also
+      // assert lower down that running another pass causes no further changes.)
+      if (newParent != iDoms[index]) {
+        iDoms[index] = newParent;
+        changed = true;
+
+        // In reverse postorder the dominator cannot appear later.
+        assert(newParent <= index);
+      }
+    }
+
+    return changed;
+  };
+
+  processBlocks();
+
+  // We must have finished all the work in a single traversal, since our input
+  // is reducible.
+  assert(!processBlocks());
+
+  // Finish up. The entry node has no dominator; mark that with a nonsense value
+  // which no one should use.
+  iDoms[0] = nonsense;
+}
+
+} // namespace wasm
+
+#endif // domtree_h
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";
+}
diff --git a/test/example/domtree.txt b/test/example/domtree.txt
new file mode 100644
index 000000000..b32bb74d2
--- /dev/null
+++ b/test/example/domtree.txt
@@ -0,0 +1 @@
+success.