Public Member Functions | |
def | __init__ |
def | __repr__ |
def | nodes |
def | edges |
def | add_node |
def | del_node |
def | add_edge |
def | add_uniq_edge |
def | del_edge |
def | predecessors_iter |
def | predecessors |
def | successors_iter |
def | successors |
def | leaves_iter |
def | leaves |
def | heads_iter |
def | heads |
def | find_path |
def | dot |
def | reachable_sons |
def | reachable_parents |
def | compute_dominators |
def | compute_postdominators |
def | walk_dominators |
def | walk_postdominators |
def | compute_immediate_dominators |
def | compute_dominance_frontier |
def | walk_breadth_first_forward |
def | walk_depth_first_forward |
def | walk_breadth_first_backward |
def | walk_depth_first_backward |
def | compute_natural_loops |
def | compute_back_edges |
def | compute_strongly_connected_components |
Static Public Member Functions | |
def | node2str |
def | edge2str |
Private Member Functions | |
def | _walk_generic_first |
def | _compute_natural_loop_body |
Static Private Member Functions | |
def | _reachable_nodes |
def | _compute_generic_dominators |
def | _walk_generic_dominator |
Private Attributes | |
_nodes | |
_edges | |
_nodes_succ | |
_nodes_pred | |
|
staticprivate |
Generic algorithm to compute either the dominators or postdominators of the graph. @head: the head/leaf of the graph @reachable_cb: sons/parents of the head/leaf @prev_cb: return predecessors/succesors of a node @next_cb: return succesors/predecessors of a node
Definition at line 173 of file graph.py.
|
private |
Computes the body of a natural loop by a depth-first search on the reversed control flow graph. :param head: leaf of the loop :param leaf: header of the loop :return: set containing loop body
Definition at line 413 of file graph.py.
|
staticprivate |
Generic algorithm to compute all nodes reachable from/to node @head
Definition at line 147 of file graph.py.
|
staticprivate |
Generic algorithm to return an iterator of the ordered list of @node's dominators/post_dominator. The function doesn't return the self reference in dominators. @node: The start node @gen_dominators: The dictionnary containing at least node's dominators/post_dominators @succ_cb: return predecessors/succesors of a node
Definition at line 236 of file graph.py.
|
private |
Generic algorithm to compute breadth or depth first search for a node. @head: the head of the graph @flag: denotes if @todo is used as queue or stack @succ_cb: returns a node's predecessors/successors :return: next node
Definition at line 343 of file graph.py.
def miasm2.core.graph.DiGraph.add_edge | ( | self, | |
src, | |||
dst | |||
) |
def miasm2.core.graph.DiGraph.add_node | ( | self, | |
node | |||
) |
def miasm2.core.graph.DiGraph.add_uniq_edge | ( | self, | |
src, | |||
dst | |||
) |
def miasm2.core.graph.DiGraph.compute_back_edges | ( | self, | |
head | |||
) |
Computes all back edges from a node to a dominator in the graph. :param head: head of graph :return: yield a back edge
Definition at line 396 of file graph.py.
def miasm2.core.graph.DiGraph.compute_dominance_frontier | ( | self, | |
head | |||
) |
Compute the dominance frontier of the graph Source: Cooper, Keith D., Timothy J. Harvey, and Ken Kennedy. "A simple, fast dominance algorithm." Software Practice & Experience 4 (2001), p. 9
Definition at line 318 of file graph.py.
def miasm2.core.graph.DiGraph.compute_dominators | ( | self, | |
head | |||
) |
Compute the dominators of the graph
Definition at line 221 of file graph.py.
def miasm2.core.graph.DiGraph.compute_immediate_dominators | ( | self, | |
head | |||
) |
Compute the immediate dominators of the graph
Definition at line 306 of file graph.py.
def miasm2.core.graph.DiGraph.compute_natural_loops | ( | self, | |
head | |||
) |
Computes all natural loops in the graph. Source: Aho, Alfred V., Lam, Monica S., Sethi, R. and Jeffrey Ullman. "Compilers: Principles, Techniques, & Tools, Second Edition" Pearson/Addison Wesley (2007), Chapter 9.6.6 :param head: head of the graph :return: yield a tuple of the form (back edge, loop body)
Definition at line 382 of file graph.py.
def miasm2.core.graph.DiGraph.compute_postdominators | ( | self, | |
leaf | |||
) |
Compute the postdominators of the graph
Definition at line 228 of file graph.py.
def miasm2.core.graph.DiGraph.compute_strongly_connected_components | ( | self | ) |
Partitions the graph into strongly connected components. Iterative implementation of Gabow's path-based SCC algorithm. Source: Gabow, Harold N. "Path-based depth-first search for strong and biconnected components." Information Processing Letters 74.3 (2000), pp. 109--110 The iterative implementation is inspired by Mark Dickinson's code: http://code.activestate.com/recipes/ 578507-strongly-connected-components-of-a-directed-graph/ :return: yield a strongly connected component
Definition at line 434 of file graph.py.
def miasm2.core.graph.DiGraph.del_edge | ( | self, | |
src, | |||
dst | |||
) |
def miasm2.core.graph.DiGraph.del_node | ( | self, | |
node | |||
) |
Delete the @node of the graph; Also delete every edge to/from this @node
Definition at line 35 of file graph.py.
def miasm2.core.graph.DiGraph.dot | ( | self | ) |
|
static |
def miasm2.core.graph.DiGraph.edges | ( | self | ) |
def miasm2.core.graph.DiGraph.find_path | ( | self, | |
src, | |||
dst, | |||
cycles_count = 0 , |
|||
done = None |
|||
) |
def miasm2.core.graph.DiGraph.heads | ( | self | ) |
def miasm2.core.graph.DiGraph.heads_iter | ( | self | ) |
def miasm2.core.graph.DiGraph.leaves | ( | self | ) |
def miasm2.core.graph.DiGraph.leaves_iter | ( | self | ) |
|
static |
def miasm2.core.graph.DiGraph.nodes | ( | self | ) |
def miasm2.core.graph.DiGraph.predecessors | ( | self, | |
node | |||
) |
def miasm2.core.graph.DiGraph.predecessors_iter | ( | self, | |
node | |||
) |
def miasm2.core.graph.DiGraph.reachable_parents | ( | self, | |
leaf | |||
) |
Compute all parents of node @leaf. Each parent is an immediate predecessor of an arbitrary, already yielded parent of @leaf
Definition at line 167 of file graph.py.
def miasm2.core.graph.DiGraph.reachable_sons | ( | self, | |
head | |||
) |
Compute all nodes reachable from node @head. Each son is an immediate successor of an arbitrary, already yielded son of @head
Definition at line 162 of file graph.py.
def miasm2.core.graph.DiGraph.successors | ( | self, | |
node | |||
) |
def miasm2.core.graph.DiGraph.successors_iter | ( | self, | |
node | |||
) |
def miasm2.core.graph.DiGraph.walk_breadth_first_backward | ( | self, | |
head | |||
) |
Performs a breadth first search on the reversed graph from @head
Definition at line 374 of file graph.py.
def miasm2.core.graph.DiGraph.walk_breadth_first_forward | ( | self, | |
head | |||
) |
Performs a breadth first search on the graph from @head
Definition at line 366 of file graph.py.
def miasm2.core.graph.DiGraph.walk_depth_first_backward | ( | self, | |
head | |||
) |
Performs a depth first search on the reversed graph from @head
Definition at line 378 of file graph.py.
def miasm2.core.graph.DiGraph.walk_depth_first_forward | ( | self, | |
head | |||
) |
Performs a depth first search on the graph from @head
Definition at line 370 of file graph.py.
def miasm2.core.graph.DiGraph.walk_dominators | ( | self, | |
node, | |||
dominators | |||
) |
Return an iterator of the ordered list of @node's dominators The function doesn't return the self reference in dominators. @node: The start node @dominators: The dictionnary containing at least node's dominators
Definition at line 284 of file graph.py.
def miasm2.core.graph.DiGraph.walk_postdominators | ( | self, | |
node, | |||
postdominators | |||
) |
Return an iterator of the ordered list of @node's postdominators The function doesn't return the self reference in postdominators. @node: The start node @postdominators: The dictionnary containing at least node's postdominators
Definition at line 294 of file graph.py.