dominance_frontiers: Dominance Frontiers of a Graph

In nick-ulle/ast: Low-level Static Analysis Tools for R Code

Dominance Frontiers of a Graph

Description

This function computes the dominance frontiers for a graph.

Usage

dominance_frontiers(g, dom_t = dominator_tree(g))

Arguments

g	(igraph) The graph.
dom_t	(igraph) The dominator tree for the graph.

Details

The dominance frontier for a block b is the set of all blocks y such that b dominates a predecessor of y but does not strictly dominate y. In other words, the dominance frontier for b is the set of blocks immediately beyond the blocks dominated by b, where control-flow merges from a separate part of the program.

Value

A graph with a vertex for each vertex in the original graph. Each vertex has edges to all vertices in its dominance frontier.

References

Cooper, K. D., Harvey T. J., and Kennedy, K. (2001) A simple, fast dominance algorithm. Software Practice & Experience 4, 1-10.

Cooper, K. D. and Torczon, L. (2012) Engineering a Compiler. Elsevier.

nick-ulle/ast documentation built on May 14, 2024, 7:40 p.m.