scalpel.SSA.alg

module documentation

(source)

In this code we include a lightweight adaption algorithm for dominating relationships computing. The code is adapted from Networkx Please see the original one at https://networkx.org/documentation/stable/_modules/networkx/algorithms/dominance.html#dominance_frontiers TODO: implement a datastructure such as G from networkx for control flow graph. so that networkx is not required in this library.

Function	`dominance_frontiers`	Returns the dominance frontiers of all nodes of a directed graph.
Function	`immediate_dominators`	Returns the immediate dominators of all nodes of a directed graph.
Function	`main`	Undocumented

def dominance_frontiers(G, start): (source) ¶

Returns the dominance frontiers of all nodes of a directed graph.

Examples

>>> G = nx.DiGraph([(1, 2), (1, 3), (2, 5), (3, 4), (4, 5)])
>>> sorted((u, sorted(df)) for u, df in nx.dominance_frontiers(G, 1).items())
[(1, []), (2, [5]), (3, [5]), (4, [5]), (5, [])]

References

[1]	K. D. Cooper, T. J. Harvey, and K. Kennedy. A simple, fast dominance algorithm. Software Practice & Experience, 4:110, 2001.

Parameters
G:a DiGraph or `MultiDiGraph`	The graph where dominance is to be computed.
start:`node`	The start node of dominance computation.
Returns
dict keyed by nodes	df - A dict containing the dominance frontiers of each node reachable from `start` as lists.
Raises
`NetworkXNotImplemented`	If `G` is undirected.
`NetworkXError`	If `start` is not in `G`.

def immediate_dominators(G, start): (source) ¶

Returns the immediate dominators of all nodes of a directed graph.

Notes

Except for start, the immediate dominators are the parents of their corresponding nodes in the dominator tree.

Examples

>>> G = nx.DiGraph([(1, 2), (1, 3), (2, 5), (3, 4), (4, 5)])
>>> sorted(nx.immediate_dominators(G, 1).items())
[(1, 1), (2, 1), (3, 1), (4, 3), (5, 1)]

References

[1]	K. D. Cooper, T. J. Harvey, and K. Kennedy. A simple, fast dominance algorithm. Software Practice & Experience, 4:110, 2001.

Parameters
G:a DiGraph or `MultiDiGraph`	The graph where dominance is to be computed.
start:`node`	The start node of dominance computation.
Returns
dict keyed by nodes	idom - A dict containing the immediate dominators of each node reachable from `start`.
Raises
`NetworkXNotImplemented`	If `G` is undirected.
`NetworkXError`	If `start` is not in `G`.

def main(): (source) ¶

Undocumented