diff options
| author | Alon Zakai <azakai@google.com> | 2021-08-26 08:04:03 -0700 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2021-08-26 08:04:03 -0700 |
| commit | 94cf0c2801f784209755d1527d3eda78a38b8034 (patch) | |
| tree | 7589985dd84b1cee4975b1ae222dba93fbfa5a5a /test/example/domtree.cpp | |
| parent | 89626faa2d81cec9f27137fe902bf7530bc06532 (diff) | |
| download | binaryen-94cf0c2801f784209755d1527d3eda78a38b8034.tar.gz binaryen-94cf0c2801f784209755d1527d3eda78a38b8034.tar.bz2 binaryen-94cf0c2801f784209755d1527d3eda78a38b8034.zip | |
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.
Diffstat (limited to 'test/example/domtree.cpp')
| -rw-r--r-- | test/example/domtree.cpp | 163 |
1 files changed, 163 insertions, 0 deletions
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"; +} |