diff options
Diffstat (limited to 'source')
| -rw-r--r-- | source/slang/ir-dominators.cpp | 720 | ||||
| -rw-r--r-- | source/slang/ir-dominators.h | 162 | ||||
| -rw-r--r-- | source/slang/ir-ssa.cpp | 2 | ||||
| -rw-r--r-- | source/slang/slang.vcxproj | 2 | ||||
| -rw-r--r-- | source/slang/slang.vcxproj.filters | 2 |
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" /> |