diff options
| author | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2017-09-21 01:46:00 +0100 |
|---|---|---|
| committer | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2018-07-01 00:18:44 +0200 |
| commit | 91d965db0a601de4f565cb590cb2943accfcf171 (patch) | |
| tree | c234a240af55b86d7cb02d9c34c9824ebf72b774 /flowgraph.c | |
| parent | 242d55dba4a831b35e6f127f3b6aca3c00534426 (diff) | |
| download | sparse-dev-91d965db0a601de4f565cb590cb2943accfcf171.tar.gz | |
dom: add support for dominance queries
The dominance tree is useless as such, what's matter
is to be able to make queries, to ask if such BB dominates
this other BB.
This patch add an API (domtree_dominates()) to do this.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Diffstat (limited to 'flowgraph.c')
| -rw-r--r-- | flowgraph.c | 24 |
1 files changed, 24 insertions, 0 deletions
diff --git a/flowgraph.c b/flowgraph.c index b2d95893..8fc22dcf 100644 --- a/flowgraph.c +++ b/flowgraph.c @@ -193,3 +193,27 @@ void domtree_build(struct entrypoint *ep) if (dbg_domtree) debug_domtree(ep); } + +// dt_dominates - does BB a dominates BB b? +bool domtree_dominates(struct basic_block *a, struct basic_block *b) +{ + if (a == b) // dominance is reflexive + return true; + if (a == b->idom) + return true; + if (b == a->idom) + return false; + + // can't dominate if deeper in the DT + if (a->dom_level >= b->dom_level) + return false; + + // FIXME: can be faster if we have the DFS in-out numbers + + // walk up the dominator tree + for (b = b->idom; b; b = b->idom) { + if (b == a) + return true; + } + return false; +} |