Add a pass for computing dominator trees (#541)

This code is currently not used by anything, but I wanted to check in a first pass at an implementation of dominator tree construction so that we don't have to keep avoiding implementing algorithms that rely on having dominator information available.

The algorithm used to construct the dominator tree is taken from "A Simple, Fast Dominance Algorithm" by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy.
This is not the "best" algorithm in terms of asymptotic performance, but it is among the simplest algorithms for computing a dominator tree that still outperforms naive iterative set-based methods.

The actual data structure and API for the dominator tree has a bit of "cleverness" in it to try to make the common queries reasonably fast (e.g., you can check whether A dominates B in constant time).
My hope is that even if we implement a more advanced algorithm for constructing the dominator tree, we can retain compatibility with passes that might make use of this API.

Because no code is currently using this logic, I have done only minimal testing by stepping through this code and validating the results on paper for some very small CFGs.
More serious testing/debugging may need to wait until we have an optimization pass that needs the dominator tree we compute here.
One open question I have is how best to introduce traditional unit testing into Slang, since this is an example of code that would benefit greatly from being unit tested.

5 files changed, 887 insertions, 1 deletions

diff --git a/source/slang/ir-dominators.cpp b/source/slang/ir-dominators.cpp
new file mode 100644
index 000000000..3760beeca
--- /dev/null
+++ b/source/slang/ir-dominators.cpp
@@ -0,0 +1,720 @@
+// ir-dominators.cpp
+#include "ir-dominators.h"
+
+//
+// This file implements the public interface of the `IRDominatorTree` type,
+// to enable queries on dominance relationships in a control-flow graph.
+//
+// It also implements computation of the dominator tree for a CFG using
+// the algorithm presented in "A Simple, Fast Dominance Algorithm" by
+// Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy.
+//
+// The algorithm is *not* the most efficinet one, asymptotically, but
+// it is one that is easy to implement and explain, and so we favor it
+// in order to get something up and running with a reasonable level of
+// confidence that the results are correct.
+//
+
+#include "ir.h"
+
+namespace Slang {
+
+//
+// Let's start with the implementation of the public API for `IRDominatorTree`
+//
+
+// IRDominatorTree
+
+bool IRDominatorTree::immediatelyDominates(IRBlock* dominator, IRBlock* dominated)
+{
+    // To test if block A immediately dominates block B, we just
+    // check if A is the (one and only) immediate dominator of B.
+    return dominator == getImmediateDominator(dominated);
+}
+
+bool IRDominatorTree::properlyDominates(IRBlock* dominator, IRBlock* dominated)
+{
+    // Because of how we laid out the tree, we can test if one node
+    // properly dominates another in constant time.
+    //
+    // We simply need to test if the node index for `dominated` falls
+    // in the range of indices for the descendents of `dominator`.
+    //
+
+    Int dominatorIndex = getBlockIndex(dominator);
+    Int dominatedIndex = getBlockIndex(dominated);
+    Node& dominatorNode = nodes[dominatorIndex];
+
+    return (dominatedIndex >= dominatorNode.beginDescendents)
+        && (dominatedIndex < dominatorNode.endDescendents);
+}
+
+bool IRDominatorTree::dominates(IRBlock* dominator, IRBlock* dominated)
+{
+    // We need to check two cases here.
+    //
+    // First, a node always dominated itself, so if the blocks are
+    // the the same, then we are done:
+    //
+    if(dominator == dominated)
+        return true;
+    //
+    // Otherwise, for distinct blocks we just check for
+    // proper dominance:
+    //
+    return properlyDominates(dominator, dominated);
+}
+
+IRBlock* IRDominatorTree::getImmediateDominator(IRBlock* block)
+{
+    // The immediate dominator of a block is its parent
+    // in the dominator tree. Looking this up is straightforward,
+    // and we just need to be a bit careful to deal with
+    // invalid node indices.
+
+    Int blockIndex = getBlockIndex(block);
+    if(blockIndex == kInvalidIndex) return nullptr;
+
+    Int parentIndex = nodes[blockIndex].parent;
+    if(parentIndex == kInvalidIndex) return nullptr;
+
+    return nodes[parentIndex].block;
+}
+
+IRDominatorTree::DominatedList IRDominatorTree::getImmediatelyDominatedBlocks(IRBlock* block)
+{
+    // Because of our representation, the immediately dominated blocks
+    // for a node are contiguous, and we store their range in the
+    // node already.
+
+    Int blockIndex = getBlockIndex(block);
+    if(blockIndex == kInvalidIndex) return DominatedList();
+
+    Node& node = nodes[blockIndex];
+    return DominatedList(
+        this,
+        node.beginDescendents,
+        node.endChildren);
+}
+
+IRDominatorTree::DominatedList IRDominatorTree::getProperlyDominatedBlocks(IRBlock* block)
+{
+    // Because of our representation, the properly dominated blocks
+    // for a node are contiguous, and we store their range in the
+    // node already.
+
+    Int blockIndex = getBlockIndex(block);
+    if(blockIndex == kInvalidIndex) return DominatedList();
+
+    Node& node = nodes[blockIndex];
+    return DominatedList(
+        this,
+        node.beginDescendents,
+        node.endDescendents);
+}
+
+Int IRDominatorTree::getBlockIndex(IRBlock* block)
+{
+    Int index = kInvalidIndex;
+    if(!mapBlockToIndex.TryGetValue(block, index))
+    {
+        SLANG_UNEXPECTED("block was not present in dominator tree");
+    }
+    return index;
+}
+
+// IRDominatorTree::DominatedList
+
+IRDominatorTree::DominatedList::DominatedList()
+    : mTree(nullptr)
+    , mBegin(0)
+    , mEnd(0)
+{}
+
+IRDominatorTree::DominatedList::DominatedList(
+    IRDominatorTree* tree,
+    Int begin,
+    Int end)
+    : mTree(tree)
+    , mBegin(begin)
+    , mEnd(end)
+{}
+
+IRDominatorTree::DominatedList::Iterator IRDominatorTree::DominatedList::begin() const
+{
+    return Iterator(mTree, mBegin);
+}
+
+IRDominatorTree::DominatedList::Iterator IRDominatorTree::DominatedList::end() const
+{
+    return Iterator(mTree, mBegin);
+}
+
+
+// IRDominatorTree::DominatedList::Iterator
+
+IRDominatorTree::DominatedList::Iterator::Iterator()
+    : mTree(nullptr)
+    , mIndex(0)
+{}
+
+IRDominatorTree::DominatedList::Iterator::Iterator(
+    IRDominatorTree* tree,
+    Int index)
+    : mTree(tree)
+    , mIndex(index)
+{}
+
+IRBlock* IRDominatorTree::DominatedList::Iterator::operator*() const
+{
+    return mTree->nodes[mIndex].block;
+}
+
+void IRDominatorTree::DominatedList::Iterator::operator++()
+{
+    mIndex++;
+}
+
+bool IRDominatorTree::DominatedList::Iterator::operator==(Iterator const& that) const
+{
+    SLANG_ASSERT(mTree == that.mTree);
+    return mIndex == that.mIndex;
+}
+
+//
+// The dominance computation algorithm we are using relies on being able to compute
+// a reverse postorder traversal of the nodes in the CFG, which is done using a depth-first
+// search (DFS). We don't currently have infrastructure for DFS in the compiler, so
+// we will implement it here for now, and plan to move it into its own file once
+// we have a second use case.
+//
+
+/// A base "visitor" class for use in depth-first search algorithms on an IR CFG.
+struct DepthFirstSearchContext
+{
+    /// The blocks in the CFG that we've already visited.
+    HashSet<IRBlock*> visited;
+
+    /// Walk a (previously unvisited) block.
+    ///
+    /// This will perform any pre-order actions on the block,
+    /// then recursively visit its (unvisited) successors, and
+    /// then perform any post-actions.
+    ///
+    void walk(IRBlock* block)
+    {
+        visited.Add(block);
+        preVisit(block);
+        for(auto succ : block->getSuccessors())
+        {
+            if(!visited.Contains(succ))
+            {
+                walk(succ);
+            }
+        }
+        postVisit(block);
+    }
+
+    /// Walk the blocks in a function (or other code-bearing value).
+    void walk(IRGlobalValueWithCode* code)
+    {
+        auto root = code->getFirstBlock();
+        if(!root)
+            return;
+        walk(root);
+    }
+
+    /// Overridable action to perform on first entering a CFG node.
+    virtual void preVisit(IRBlock* /*block*/) {}
+
+    /// Overridable action to perform on exiting a CFG node
+    virtual void postVisit(IRBlock* /*block*/) {}
+};
+
+//
+// With DFS traversal factored out, computing a post-order walk
+// of the CFG is a simple matter of defining a visitor that appends
+// to an order as a post-action:
+//
+
+/// A visitor that computes a postorder traversal for a CFG.
+struct PostorderComputationContext : public DepthFirstSearchContext
+{
+    /// List to append the computed order onto
+    List<IRBlock*>* order;
+
+    virtual void postVisit(IRBlock* block) SLANG_OVERRIDE
+    {
+        order->Add(block);
+    }
+};
+
+/// Compute a postorder traversal of the blocks in `code`, writing the resulting order to `outOrder`.
+void computePostorder(IRGlobalValueWithCode* code, List<IRBlock*>& outOrder)
+{
+    PostorderComputationContext context;
+    context.order = &outOrder;
+    context.walk(code);
+}
+
+//
+// With the preliminaries out of the way, we are ready to implement
+// the dominator tree construction algorithm as described by Cooper, Harvey, and Kennedy.
+// The actual code for the algorithm is given in Figure 3 of the paper.
+//
+// We will wrap the subroutines of their algorithm in a `struct` type
+// to allow the temporary structures to be shared.
+//
+struct DominatorTreeComputationContext
+{
+    // We will use signed integers to represent the "name" of a block.
+    // The integers will reflect the a postorder traversal, and this
+    // property will be exploited in the `intersect()` function.
+    //
+    typedef Int BlockName;
+    //
+    // An invalid/undefined block name will be represented as -1.
+    //
+    static const BlockName kUndefined = BlockName(-1);
+    //
+    // We will explicitly store the blocks visited in the postorder
+    // traversal, so that we can look up a block based on its "name"
+    //
+    List<IRBlock*> postorder;
+
+    //
+    // We need a way to map our actual IR blocks to their names for
+    // the purpose of this algorithm. This mapping step adds overhead,
+    // but it seems unavoidable unless we also translate the CFG itself
+    // to an index-based representation.
+    //
+    Dictionary<IRBlock*, BlockName> mapBlockToName;
+    BlockName getBlockName(IRBlock* block)
+    {
+        return mapBlockToName[block];
+    }
+
+    //
+    // The algorithm iteratively builds up an array `doms` that upon
+    // completion will directly encode the immediate dominator for each
+    // node. During the iterative steps it is used to implicitly encode
+    // a representation of the set of dominators for each node.
+    //
+    List<BlockName> doms;
+
+
+    //
+    // Here we get to the meat of the algorithm presented in Cooper et al.
+    // Figure 3:
+    //
+    void iterativelyComputeImmediateDominators(IRGlobalValueWithCode* code)
+    {
+        // First we compute the postorder traversal order for the blocks in the CFG.
+        computePostorder(code, postorder);
+
+        // We will initialize our map from the block objects to their "name"
+        // (index in the traversal order), before moving on.
+        BlockName blockCount = BlockName(postorder.Count());
+        for(BlockName bb = 0; bb < blockCount; ++bb)
+        {
+            mapBlockToName[postorder[bb]] = bb;
+        }
+
+        // Next we initialize the `doms` array that we will iteratively turn
+        // into an encoding of the dominator tree.
+        doms.SetSize(blockCount);
+        for(BlockName bb = 0; bb < blockCount; ++bb)
+        {
+            doms[bb] = kUndefined;
+        }
+
+        // The start node is special, since it is the root of the dominator tree.
+        // Technically it doesn't have an immediate dominator, but we will set
+        // its entry in `doms` to refer to itself, to indicate that we are done
+        // processing the given node.
+        //
+        BlockName startNode = getBlockName(code->getFirstBlock());
+        doms[startNode] = startNode;
+
+        // Given that we computed a postorder traversal of the graph, we know
+        // that the start node should be the last one in the computed order.
+        //
+        SLANG_ASSERT(startNode == blockCount - 1);
+
+        // We are using an iterative algorithm, so we will detect that we
+        // have reached a fixed point when we hit an iteration where nothing
+        // changes.
+        //
+        bool changed = true;
+        while(changed)
+        {
+            changed = false;
+
+            // The algorithm specifies that we should walk through the blocks
+            // in *reverse* postorder, since this speeds up convergence.
+            // Because we've numbered the blocks in postorder, walking them
+            // in reverse numerical order will do the trick.
+            //
+            // We don't want to include the start node in our iteration
+            // (since we already know its dominators), and because we know
+            // that the start node is always the last in the order (`blockCount - 1`)
+            // we can just start at the next node after it (`blockCount - 2`).
+            //
+            // Note: it is important that we are using signed integers for
+            // block numbers here, since we will drop below zero before exiting
+            // the loop, and if the CFG had only a single block, then our *starting*
+            // block index would be `-1`.
+            //
+            for(auto b = blockCount - 2; b >= 0; --b)
+            {
+                // We are walking through block indices, but the predecessor
+                // lists are encoded in the IR blocks themselves.
+                //
+                IRBlock* block = postorder[b];
+
+                // The algorithm description in the paper says to pick the
+                // initial value for the `new_idom` variable from the "first
+                // (processed) predecessor of b (pick one)".
+                // After that step, the algorithm walks over the remaining
+                // predecessors, and for the ones that have a valid entry
+                // in the `doms` array, performs an intersection of their
+                // implicitly-represented dominator sets.
+                //
+                // The paper doesn't precisely clarify what they mean by
+                // a "processed" predecessor, but it seems to mean one that
+                // has a valid value in the `doms` array, which is what
+                // the subsequent loop is already checking.
+                //
+                // We are going to fold this logic together into a single loop.
+                // We will start with an invalid/undefined value for
+                // `new_idom`, which represents our best guess at the
+                // immediate dominator for block `b`:
+                //
+                BlockName new_idom = kUndefined;
+
+                // Now we will loop over *all* of the predecessors, ...
+                for(auto pred : block->getPredecessors())
+                {
+                    // ... and skip those that haven't been "processed".
+                    BlockName p = getBlockName(pred);
+                    BlockName dominatorOfPredecessor = doms[p];
+                    if(dominatorOfPredecessor == kUndefined)
+                        continue;
+
+                    // When we encounter the first "processed" predecessor,
+                    // we can initialize the variable tracking our best
+                    // guess at the immediate dominator.
+                    //
+                    if(new_idom == kUndefined)
+                    {
+                        new_idom = p;
+                    }
+                    //
+                    // Otherwise, we need to merge information between
+                    // the predecessor `p` and our best-guess immediate
+                    // dominator `new_idom`. We need a node that dominates
+                    // both of them to be the immediate dominator of `b`.
+                    //
+                    else
+                    {
+                        new_idom = intersect(p, new_idom);
+                    }
+                }
+
+                // After we've computed a new best guess at the immediate
+                // dominator for `b`, we need to see if the computed
+                // value differs from what we'd previously stored in the
+                // `doms` array. If anything changed, then we haven't
+                // converged yet, and we need to keep going.
+                //
+                BlockName oldDominator = doms[b];
+                if(oldDominator != new_idom)
+                {
+                    doms[b] = new_idom;
+                    changed = true;
+                }
+            }
+        }
+
+        // Upon exiting the loop, things should have converged with
+        // the `doms` array being an explicit encoding of the immediate
+        // dominator for each node, with one small error: there is no
+        // immediate dominator for the start node:
+        doms[startNode] = kUndefined;
+    }
+
+    //
+    // The algorithm above relied on a utility routine `intersect()` that
+    // is implicitly used to compute intersections between sets of nodes,
+    // but explicitly takes the form of a routine that computes a common
+    // parent in the dominator tree for two nodes.
+    //
+    // We present that subroutine here, almost identical to how it
+    // is presented in Cooper et al. Figure 3:
+    //
+    BlockName intersect(BlockName b1, BlockName b2)
+    {
+        // We need to find a common ancestor of both `b1` and `b2`,
+        // and will do this by tracking two "fingers," each initially
+        // pointing at one node, and then iteratively move the finger
+        // that is furthest to the "left" (earlier in the postorder
+        // traversal to the left until) to the "right" (by moving
+        // the immediate dominator of the node we are pointing at),
+        // until the two fingers are pointing at the same place.
+        //
+        // Termination is guaranteed because we are always moving the
+        // fingers from a node to its immediate dominator, and the
+        // entry node is guaranteed to be at the root of the dominator
+        // tree.
+        //
+        // The use of the postorder here relies on the (subtle) fact
+        // that the immediate dominator of a node must come later
+        // in a postorder traversal.
+        //
+        BlockName finger1 = b1;
+        BlockName finger2 = b2;
+
+        while(finger1 != finger2)
+        {
+            while(finger1 < finger2)
+                finger1 = doms[finger1];
+            while(finger2 < finger1)
+                finger2 = doms[finger2];
+        }
+        return finger1;
+    }
+
+    //
+    // Now that we've implemented Cooper et al. fairly close to how
+    // it was presented, we can build an array encoding the immediate
+    // dominator relationship. We still need to expand that array
+    // into an encoding that lets us efficiently answer queries
+    // about dominance.
+    //
+    // In order to do that, we need to expand the information we
+    // have built on each block (currently just an immediate dominator)
+    // into a bit more detail:
+    //
+    struct BlockInfo
+    {
+        // How many children does this node/block have in the dominator tree?
+        Int childCount = 0;
+
+        // How many indirect (non-child) descendents?
+        Int indirectDescendentCount = 0;
+
+        // What is the 0-based offset of this node among all the children of its parent?
+        Int childOffsetInParent = 0;
+
+        // What is the 0-based offset for this node's descendent list,
+        // among all the children in its parent?
+        Int descendentOffsetInParent = 0;
+
+        Int nodeIndex = 0;
+        Int firstDescendentIndex = 0;
+    };
+    //
+
+    RefPtr<IRDominatorTree> createDominatorTree(IRGlobalValueWithCode* code)
+    {
+        // We first run the Cooper et al. algorithm to compute the `doms` array
+        // which encodes immediate dominators.
+        //
+        iterativelyComputeImmediateDominators(code);
+
+        // We will build some intermediate information on each
+        // block to help us fill out the tree.
+        BlockName blockCount = BlockName(doms.Count());
+        List<BlockInfo> blockInfos;
+        for(BlockName bb = 0; bb < blockCount; ++bb)
+        {
+            blockInfos.Add(BlockInfo());
+        }
+
+        // We will propagate layout information in two passes over the tree.
+        //
+        // First we will perform a "bottom up" pass that will accumulate
+        // the number of children and the total number of descendents for
+        // each node, and also assign each child its relative offsets within
+        // the storage for its parent.
+        //
+        // Because our blocks are ordered in postorder, we can do this
+        // bottom-up walk just by iterating over them in the given order.
+        //
+        for(BlockName bb = 0; bb < blockCount; ++bb)
+        {
+            BlockName parent = doms[bb];
+            if(parent == kUndefined)
+                continue;
+
+            // For our iteration order to make sense, we need to be certain
+            // that parent nodes come after their child nodes in the postorder traversal.
+            SLANG_ASSERT(parent > bb);
+
+            // Compute the 0-based index of this child among all the children
+            // with the same parent, and increment its child count.
+            blockInfos[bb].childOffsetInParent = blockInfos[parent].childCount;
+            blockInfos[parent].childCount++;
+
+            // Our layout for the descendents of a node will put all the immediate
+            // child nodes contiguously first, followed by their descendents (in contiguous blocks).
+            //
+            // We need to compute an offset for where the descendents of this node will
+            // be stored, within the overall space carved out for the "indirect" descendents
+            // of the parent node.
+            //
+            blockInfos[bb].descendentOffsetInParent = blockInfos[parent].indirectDescendentCount;
+            //
+            // When adding up the indirect descendents of `parent`, we need to include both
+            // the direct and indirect descendents of our node `bb`.
+            blockInfos[parent].indirectDescendentCount += blockInfos[bb].childCount
+                + blockInfos[bb].indirectDescendentCount;
+        }
+        //
+        // The next pass is a top-down pass that uses the accumulated
+        // information to assign absolute indices to each node.
+        //
+        // For each node, we want to compute its absolute index in
+        // the overall array of nodes, and then we also want to compute
+        // the index where its first descendent node will be placed
+        // (which can then be used by child nodes to compute their
+        // index).
+        //
+        // The start node in the CFG is special, and will always get
+        // index zero, with its first desecendent at index 1.
+        //
+        BlockName startBlock = getBlockName(code->getFirstBlock());
+        blockInfos[startBlock].nodeIndex = 0;
+        blockInfos[startBlock].firstDescendentIndex = 1;
+        //
+        // For the remaining nodes, we'll compute them in a top-down
+        // pass (using reverse postorder).
+        //
+        for(BlockName bb = blockCount-1; bb >= 0; --bb)
+        {
+            // We will skip nodes without a parent in the dominator tree.
+            // This should really only be the start node, but it might
+            // happen that we have some unreachable nodes that shouldn't
+            // appear in the dominator tree at all.
+            //
+            // TODO: make sure we either handle those correctly, or
+            // else add a pass to eliminate unreachable blocks first.
+            //
+            BlockName parent = doms[bb];
+            if(parent == kUndefined)
+                continue;
+
+            // The absolute index of a node is the absolute index for its
+            // parent's descendent list, plus the relative offset of this
+            // child node in its parent.
+            //
+            blockInfos[bb].nodeIndex = blockInfos[parent].firstDescendentIndex
+                + blockInfos[bb].childOffsetInParent;
+
+            // The other descendents of a node are always laid out in the space
+            // after its immediate children. Thus, the index for where this node
+            // will place its descendents (direct + indirect) must come after
+            // the storage for the children of the parent.
+            //
+            blockInfos[bb].firstDescendentIndex = blockInfos[parent].firstDescendentIndex
+                + blockInfos[parent].childCount
+                + blockInfos[bb].descendentOffsetInParent;
+        }
+
+        // We now have all the information we need, and can start to fill in
+        // the actual `IRDominatorTree` structure with the encoded information.
+        //
+        RefPtr<IRDominatorTree> dominatorTree = new IRDominatorTree();
+        dominatorTree->code = code;
+        dominatorTree->nodes.SetSize(blockCount);
+
+        // We will iterate over all of the blocks, and fill in the corresponding
+        // dominator tree node for each.
+        //
+        // Note that the number of the blocks (in postorder) and the numbering
+        // of the nodes (in breadth-first order) will not match, so we have
+        // to be careful around whehter we are working with a block index/name,
+        // or a node index.
+        //
+        for(BlockName bb = 0; bb < blockCount; ++bb)
+        {
+            // Find the IR block, look up our pre-computed information,
+            // and find the corresponding node in the dominator tree.
+            //
+            IRBlock* block = postorder[bb];
+            BlockInfo const& blockInfo = blockInfos[bb];
+            Int nodeIndex = blockInfo.nodeIndex;
+            IRDominatorTree::Node& node = dominatorTree->nodes[nodeIndex];
+
+            // We will now start filling in the node. Filling in the block is
+            // trial, and while we are at it we can add an entry to the mapping
+            // from the block to  the node index.
+            //
+            node.block = block;
+            dominatorTree->mapBlockToIndex.Add(block, nodeIndex);
+
+            // Filling in the parent is easy enough, just with the detail that
+            // we need to handle the invalid case explicitly (for a node with
+            // no parent), and need to carefully map the block index `parent`
+            // over to its corresponding node index.
+            //
+            BlockName parent = doms[bb];
+            node.parent = parent == kUndefined ? IRDominatorTree::kInvalidIndex : blockInfos[parent].nodeIndex;
+
+            // Finally we need to compute the range information to use for the
+            // descendents (both immediate children and indirect descendents).
+            //
+            // All of the relevant information was computed in our two passes
+            // above, so all that has to happen here is adding together the
+            // absolute start index for the descendent range with the counts
+            // we accumulated.
+            //
+            Int beginDescendents = blockInfo.firstDescendentIndex;
+            Int endChildren = beginDescendents + blockInfo.childCount;
+            //
+            // The indirect descendents of a node will always come after
+            // its direct descenents.
+            //
+            Int endDescendents = endChildren + blockInfo.indirectDescendentCount;
+            node.beginDescendents = beginDescendents;
+            node.endChildren = endChildren;
+            node.endDescendents = endDescendents;
+        }
+
+#if 0
+        // Let's do some ad hoc validation here, just to be sure we built the
+        // data structure reasonably.
+        for(BlockName ii = 0; ii < blockCount; ++ii)
+        {
+            for(BlockName jj = 0; jj < blockCount; ++jj)
+            {
+                IRBlock* i = postorder[ii];
+                IRBlock* j = postorder[jj];
+
+                SLANG_RELEASE_ASSERT(dominatorTree->immediatelyDominates(i, j) == (ii == doms[jj]));
+
+                Int dd = jj;
+                while(dd != kUndefined)
+                {
+                    if(dd == ii)
+                        break;
+                    dd = doms[dd];
+                }
+                SLANG_RELEASE_ASSERT(dominatorTree->dominates(i, j) == (dd != kUndefined));
+
+            }
+        }
+#endif
+
+        return dominatorTree;
+    }
+};
+
+
+RefPtr<IRDominatorTree> computeDominatorTree(IRGlobalValueWithCode* code)
+{
+    DominatorTreeComputationContext context;
+    return context.createDominatorTree(code);
+}
+
+}
diff --git a/source/slang/ir-dominators.h b/source/slang/ir-dominators.h
new file mode 100644
index 000000000..936e9780a
--- /dev/null
+++ b/source/slang/ir-dominators.h
@@ -0,0 +1,162 @@
+// ir-dominators.h
+#pragma once
+
+#include "../core/basic.h"
+
+namespace Slang
+{
+    struct IRBlock;
+    struct IRGlobalValueWithCode;
+
+    /// The computed dominator tree for an IR control flow graph.
+    struct IRDominatorTree : public RefObject
+    {
+        /// The function or other code-bearing value for which the dominator tree was computed.
+        IRGlobalValueWithCode*  code;
+
+        /// Does the first block dominate the second?
+        ///
+        /// A block A dominates block B iff every control-flow path
+        /// that starts at the entry block of the CFG and passes
+        /// through B must first pass through A.
+        ///
+        bool dominates(IRBlock* dominator, IRBlock* dominated);
+
+        /// Does the first block properly dominate the second?
+        ///
+        /// Block A properly dominates block B iff A dominates B
+        /// and A != B.
+        ///
+        bool properlyDominates(IRBlock* dominator, IRBlock* dominated);
+
+        /// Does the first block immediately dominate the second?
+        ///
+        /// Block A immediately dominates block B iff A dominates B
+        /// and for any block X that dominates B, X also dominates A.
+        ///
+        bool immediatelyDominates(IRBlock* dominator, IRBlock* dominated);
+
+        /// Get the immediate dominator (idom) of a block.
+        ///
+        /// This is the parent of `block` in the dominator tree.
+        IRBlock* getImmediateDominator(IRBlock* block);
+
+        /// An iterable collection of the blocks dominated by a specific block
+        struct DominatedList;
+
+        /// Get the blocks that a block immediately dominates.
+        ///
+        /// These are the children of the block in the dominator tree.
+        DominatedList getImmediatelyDominatedBlocks(IRBlock* block);
+
+        /// Get the blocks that a block properly dominates.
+        ///
+        /// These are the descendents of the block in the dominator tree.
+        DominatedList getProperlyDominatedBlocks(IRBlock* block);
+
+        struct DominatedList
+        {
+        public:
+            DominatedList();
+
+            struct Iterator
+            {
+            public:
+                Iterator();
+
+                IRBlock* operator*() const;
+                void operator++();
+                bool operator==(Iterator const& that) const;
+
+            private:
+                friend struct DominatedList;
+                Iterator(
+                    IRDominatorTree* tree,
+                    Int index);
+
+                IRDominatorTree*    mTree;
+                Int                 mIndex;
+            };
+
+            Iterator begin() const;
+            Iterator end() const;
+
+        private:
+            friend struct IRDominatorTree;
+            DominatedList(
+                IRDominatorTree* tree,
+                Int begin,
+                Int end);
+
+            IRDominatorTree*    mTree;
+            Int                 mBegin;
+            Int                 mEnd;
+        };
+
+    private:
+        //
+        // The layout of an `IRDominatorTree` uses a dense array for all of the nodes in the CFG.
+        // We therefore need a way to map an `IRBlock*` pointer over to an index in this array:
+        //
+
+        /// Map a block to its index in the `nodes` array
+        Int getBlockIndex(IRBlock* block);
+
+        /// Dictionary used to accelerate `getBlockIndex`
+        Dictionary<IRBlock*, Int>   mapBlockToIndex;
+
+        //
+        // In order to accelerate queries on the tree structure, we will order the tree nodes
+        // carefully, so that all of the descendants of a node are contiguous, with all of
+        // the immediate children coming first.
+        //
+        // Each node thus needs to remember its parent (immediate dominator), and the range
+        // of indices that represent children and descendents (respectively), with the knowledge
+        // that the first child and first descendent share the same index.
+        //
+
+        /// Information about one node in the dominator tree
+        struct Node
+        {
+            /// The block associated with this tree node
+            IRBlock* block;
+
+            /// Index of the parent node or -1 if no parent
+            Int parent;
+
+            /// Index of first descendent
+            Int beginDescendents;
+
+            /// "One after the end" value for range of child node indices.
+            Int endChildren;
+
+            /// "One after the end" value for range of descendent node indices.
+            Int endDescendents;
+        };
+
+        /// Storage for the dominator tree itself
+        List<Node>                  nodes;
+
+        /// Value to use for invalid node indices (e.g.,
+        /// when a node has no parent).
+        static const Int kInvalidIndex = -1;
+
+        //
+        // The `DominatedList` type needs direct access to all of this
+        // data in order to provide iteration.
+        //
+        friend struct DominatedList;
+        friend struct DominatedList::Iterator;
+        //
+        // The context type we will use to compute the dominator tree
+        // also needs to be able to access all the fields to initialze
+        // an `IRDominatorTree`
+        //
+        friend struct DominatorTreeComputationContext;
+
+        // TODO: we should probably build/store a postdominator
+        // tree in the same structure, just to make life simpler.
+    };
+
+    RefPtr<IRDominatorTree> computeDominatorTree(IRGlobalValueWithCode* code);
+}
diff --git a/source/slang/ir-ssa.cpp b/source/slang/ir-ssa.cpp
index 6c4cfa8ff..b2d336507 100644
--- a/source/slang/ir-ssa.cpp
+++ b/source/slang/ir-ssa.cpp
@@ -595,7 +595,7 @@ IRInst* readVarRec(
         // it predecessor list, and use that to decide what to do.
         auto predecessors = blockInfo->block->getPredecessors();
 
-        // 
+        //
         IRBlock* firstPred = nullptr;
         bool multiplePreds = false;
         for (auto pp : predecessors)
diff --git a/source/slang/slang.vcxproj b/source/slang/slang.vcxproj
index 83a8a167c..fa75d7378 100644
--- a/source/slang/slang.vcxproj
+++ b/source/slang/slang.vcxproj
@@ -178,6 +178,7 @@
     <ClInclude Include="emit.h" />
     <ClInclude Include="expr-defs.h" />
     <ClInclude Include="ir-constexpr.h" />
+    <ClInclude Include="ir-dominators.h" />
     <ClInclude Include="ir-inst-defs.h" />
     <ClInclude Include="ir-insts.h" />
     <ClInclude Include="ir-ssa.h" />
@@ -222,6 +223,7 @@
     <ClCompile Include="dxc-support.cpp" />
     <ClCompile Include="emit.cpp" />
     <ClCompile Include="ir-constexpr.cpp" />
+    <ClCompile Include="ir-dominators.cpp" />
     <ClCompile Include="ir-legalize-types.cpp" />
     <ClCompile Include="ir-ssa.cpp" />
     <ClCompile Include="ir-validate.cpp" />
diff --git a/source/slang/slang.vcxproj.filters b/source/slang/slang.vcxproj.filters
index 0c522b921..90b542551 100644
--- a/source/slang/slang.vcxproj.filters
+++ b/source/slang/slang.vcxproj.filters
@@ -49,6 +49,7 @@
     <ClInclude Include="ir-constexpr.h" />
     <ClInclude Include="type-system-shared.h" />
     <ClInclude Include="ir-validate.h" />
+    <ClInclude Include="ir-dominators.h" />
   </ItemGroup>
   <ItemGroup>
     <ClCompile Include="check.cpp" />
@@ -83,6 +84,7 @@
     <ClCompile Include="ir-constexpr.cpp" />
     <ClCompile Include="type-system-shared.cpp" />
     <ClCompile Include="ir-validate.cpp" />
+    <ClCompile Include="ir-dominators.cpp" />
   </ItemGroup>
   <ItemGroup>
     <CustomBuild Include="core.meta.slang" />