diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/cfg/domtree.h | 178 |
1 files changed, 178 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 |