miasm.core.graph.DiGraph Class Reference

Inheritance diagram for miasm.core.graph.DiGraph:

Collaboration diagram for miasm.core.graph.DiGraph:

Public Member Functions
def	__init__ (self)
def	__repr__ (self)
def	nodes (self)
def	edges (self)
def	merge (self, graph)
def	__add__ (self, graph)
def	copy (self)
def	__eq__ (self, graph)
def	__ne__ (self, other)
def	add_node (self, node)
def	del_node (self, node)
def	add_edge (self, src, dst)
def	add_uniq_edge (self, src, dst)
def	del_edge (self, src, dst)
def	discard_edge (self, src, dst)
def	predecessors_iter (self, node)
def	predecessors (self, node)
def	successors_iter (self, node)
def	successors (self, node)
def	leaves_iter (self)
def	leaves (self)
def	heads_iter (self)
def	heads (self)
def	find_path (self, src, dst, cycles_count=0, done=None)
def	find_path_from_src (self, src, dst, cycles_count=0, done=None)
def	nodeid (self, node)
def	node2lines (self, node)
def	node_attr (self, node)
def	edge_attr (self, src, dst)
def	dot (self)
def	predecessors_stop_node_iter (self, node, head)
def	reachable_sons (self, head)
def	reachable_parents (self, leaf)
def	reachable_parents_stop_node (self, leaf, head)
def	compute_dominators (self, head)
def	compute_postdominators (self, leaf)
def	compute_dominator_tree (self, head)
def	walk_dominators (self, node, dominators)
def	walk_postdominators (self, node, postdominators)
def	compute_immediate_dominators (self, head)
def	compute_immediate_postdominators (self, tail)
def	compute_dominance_frontier (self, head)
def	walk_breadth_first_forward (self, head)
def	walk_depth_first_forward (self, head)
def	walk_breadth_first_backward (self, head)
def	walk_depth_first_backward (self, head)
def	has_loop (self)
def	compute_natural_loops (self, head)
def	compute_back_edges (self, head)
def	compute_strongly_connected_components (self)
def	compute_weakly_connected_components (self)
def	replace_node (self, node, new_node)

Static Public Attributes
	DotCellDescription

Detailed Description

Implementation of directed graph

Constructor & Destructor Documentation

__init__()

def miasm.core.graph.DiGraph.__init__

(

self

)

Member Function Documentation

__add__()

def miasm.core.graph.DiGraph.__add__	(		self,
			graph
	)

Wrapper on `.merge`

Reimplemented in miasm.core.graph.MatchGraph.

Here is the call graph for this function:

Here is the caller graph for this function:

__eq__()

def miasm.core.graph.DiGraph.__eq__	(		self,
			graph
	)

Here is the caller graph for this function:

__ne__()

def miasm.core.graph.DiGraph.__ne__	(		self,
			other
	)

Here is the call graph for this function:

__repr__()

def miasm.core.graph.DiGraph.__repr__

(

self

)

Reimplemented in miasm.core.asmblock.AsmCFG.

add_edge()

def miasm.core.graph.DiGraph.add_edge	(		self,
			src,
			dst
	)

Here is the call graph for this function:

Here is the caller graph for this function:

add_node()

def miasm.core.graph.DiGraph.add_node	(		self,
			node
	)

Add the node @node to the graph.
If the node was already present, return False.
Otherwise, return True

Reimplemented in miasm.core.asmblock.AsmCFG.

Here is the call graph for this function:

Here is the caller graph for this function:

add_uniq_edge()

def miasm.core.graph.DiGraph.add_uniq_edge	(		self,
			src,
			dst
	)

Add an edge from @src to @dst if it doesn't already exist

Here is the call graph for this function:

Here is the caller graph for this function:

compute_back_edges()

def miasm.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

Here is the call graph for this function:

Here is the caller graph for this function:

compute_dominance_frontier()

def miasm.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

Here is the call graph for this function:

compute_dominator_tree()

def miasm.core.graph.DiGraph.compute_dominator_tree	(		self,
			head
	)

Computes the dominator tree of a graph
:param head: head of graph
:return: DiGraph

Here is the call graph for this function:

compute_dominators()

def miasm.core.graph.DiGraph.compute_dominators	(		self,
			head
	)

Compute the dominators of the graph

Here is the call graph for this function:

Here is the caller graph for this function:

compute_immediate_dominators()

def miasm.core.graph.DiGraph.compute_immediate_dominators	(		self,
			head
	)

Compute the immediate dominators of the graph

Here is the call graph for this function:

Here is the caller graph for this function:

compute_immediate_postdominators()

def miasm.core.graph.DiGraph.compute_immediate_postdominators	(		self,
			tail
	)

Compute the immediate postdominators of the graph

Here is the call graph for this function:

compute_natural_loops()

def miasm.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)

Here is the call graph for this function:

compute_postdominators()

def miasm.core.graph.DiGraph.compute_postdominators	(		self,
			leaf
	)

Compute the postdominators of the graph

Here is the call graph for this function:

Here is the caller graph for this function:

compute_strongly_connected_components()

def miasm.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

Here is the call graph for this function:

compute_weakly_connected_components()

def miasm.core.graph.DiGraph.compute_weakly_connected_components

(

self

)

Return the weakly connected components

Here is the call graph for this function:

copy()

def miasm.core.graph.DiGraph.copy

(

self

)

Copy the current graph instance

Reimplemented in miasm.core.asmblock.AsmCFG.

Here is the caller graph for this function:

del_edge()

def miasm.core.graph.DiGraph.del_edge	(		self,
			src,
			dst
	)

Reimplemented in miasm.core.asmblock.AsmCFG, and miasm.analysis.data_flow.DiGraphDefUse.

Here is the caller graph for this function:

del_node()

def miasm.core.graph.DiGraph.del_node	(		self,
			node
	)

Delete the @node of the graph; Also delete every edge to/from this
@node

Here is the call graph for this function:

Here is the caller graph for this function:

discard_edge()

def miasm.core.graph.DiGraph.discard_edge	(		self,
			src,
			dst
	)

Remove edge between @src and @dst if it exits

Here is the call graph for this function:

dot()

def miasm.core.graph.DiGraph.dot

(

self

)

Render dot graph with HTML

Here is the call graph for this function:

edge_attr()

def miasm.core.graph.DiGraph.edge_attr	(		self,
			src,
			dst
	)

Return a dictionary of attributes for the edge between @src and @dst
@src: the source node of the edge
@dst: the destination node of the edge

Reimplemented in miasm.ir.ir.IRCFG, miasm.core.asmblock.AsmCFG, and miasm.analysis.data_flow.DiGraphDefUse.

Here is the caller graph for this function:

edges()

def miasm.core.graph.DiGraph.edges

(

self

)

Here is the caller graph for this function:

find_path()

def miasm.core.graph.DiGraph.find_path	(		self,
			src,
			dst,
			cycles_count = 0,
			done = None
	)

Searches for paths from @src to @dst
@src: loc_key of basic block from which it should start
@dst: loc_key of basic block where it should stop
@cycles_count: maximum number of times a basic block can be processed
@done: dictionary of already processed loc_keys, it's value is number of times it was processed
@out: list of paths from @src to @dst

Here is the call graph for this function:

Here is the caller graph for this function:

find_path_from_src()

def miasm.core.graph.DiGraph.find_path_from_src	(		self,
			src,
			dst,
			cycles_count = 0,
			done = None
	)

This function does the same as function find_path.
But it searches the paths from src to dst, not vice versa like find_path.
This approach might be more efficient in some cases.
@src: loc_key of basic block from which it should start
@dst: loc_key of basic block where it should stop
@cycles_count: maximum number of times a basic block can be processed
@done: dictionary of already processed loc_keys, it's value is number of times it was processed
@out: list of paths from @src to @dst

Here is the call graph for this function:

Here is the caller graph for this function:

has_loop()

def miasm.core.graph.DiGraph.has_loop

(

self

)

Return True if the graph contains at least a cycle

Here is the call graph for this function:

heads()

def miasm.core.graph.DiGraph.heads

(

self

)

Here is the call graph for this function:

heads_iter()

def miasm.core.graph.DiGraph.heads_iter

(

self

)

Here is the caller graph for this function:

leaves()

def miasm.core.graph.DiGraph.leaves

(

self

)

Here is the call graph for this function:

Here is the caller graph for this function:

leaves_iter()

def miasm.core.graph.DiGraph.leaves_iter

(

self

)

Here is the caller graph for this function:

merge()

def miasm.core.graph.DiGraph.merge	(		self,
			graph
	)

Merge the current graph with @graph
@graph: DiGraph instance

Reimplemented in miasm.core.asmblock.AsmCFG.

Here is the call graph for this function:

Here is the caller graph for this function:

node2lines()

def miasm.core.graph.DiGraph.node2lines	(		self,
			node
	)

Returns an iterator on cells of the dot @node.
A DotCellDescription or a list of DotCellDescription are accepted
@node: a node of the graph

Reimplemented in miasm.ir.ir.IRCFG, miasm.core.asmblock.AsmCFG, miasm.analysis.data_flow.DiGraphLiveness, and miasm.analysis.data_flow.DiGraphDefUse.

Here is the caller graph for this function:

node_attr()

def miasm.core.graph.DiGraph.node_attr	(		self,
			node
	)

Returns a dictionary of the @node's attributes
@node: a node of the graph

Reimplemented in miasm.ir.ir.IRCFG, and miasm.core.asmblock.AsmCFG.

Here is the caller graph for this function:

nodeid()

def miasm.core.graph.DiGraph.nodeid	(		self,
			node
	)

Returns uniq id for a @node
@node: a node of the graph

Here is the caller graph for this function:

nodes()

def miasm.core.graph.DiGraph.nodes

(

self

)

Here is the caller graph for this function:

predecessors()

def miasm.core.graph.DiGraph.predecessors	(		self,
			node
	)

Here is the call graph for this function:

Here is the caller graph for this function:

predecessors_iter()

def miasm.core.graph.DiGraph.predecessors_iter	(		self,
			node
	)

Here is the caller graph for this function:

predecessors_stop_node_iter()

def miasm.core.graph.DiGraph.predecessors_stop_node_iter	(		self,
			node,
			head
	)

Here is the call graph for this function:

Here is the caller graph for this function:

reachable_parents()

def miasm.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

Here is the call graph for this function:

Here is the caller graph for this function:

reachable_parents_stop_node()

def miasm.core.graph.DiGraph.reachable_parents_stop_node	(		self,
			leaf,
			head
	)

Compute all parents of node @leaf. Each parent is an immediate
predecessor of an arbitrary, already yielded parent of @leaf.
Do not compute reachables past @head node

Here is the call graph for this function:

reachable_sons()

def miasm.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

Here is the call graph for this function:

Here is the caller graph for this function:

replace_node()

def miasm.core.graph.DiGraph.replace_node	(		self,
			node,
			new_node
	)

Replace @node by @new_node

Here is the call graph for this function:

successors()

def miasm.core.graph.DiGraph.successors	(		self,
			node
	)

Here is the call graph for this function:

Here is the caller graph for this function:

successors_iter()

def miasm.core.graph.DiGraph.successors_iter	(		self,
			node
	)

Here is the caller graph for this function:

walk_breadth_first_backward()

def miasm.core.graph.DiGraph.walk_breadth_first_backward	(		self,
			head
	)

Performs a breadth first search on the reversed graph from @head

Here is the call graph for this function:

walk_breadth_first_forward()

def miasm.core.graph.DiGraph.walk_breadth_first_forward	(		self,
			head
	)

Performs a breadth first search on the graph from @head

Here is the call graph for this function:

walk_depth_first_backward()

def miasm.core.graph.DiGraph.walk_depth_first_backward	(		self,
			head
	)

Performs a depth first search on the reversed graph from @head

Here is the call graph for this function:

walk_depth_first_forward()

def miasm.core.graph.DiGraph.walk_depth_first_forward	(		self,
			head
	)

Performs a depth first search on the graph from @head

Here is the call graph for this function:

Here is the caller graph for this function:

walk_dominators()

def miasm.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 dictionary containing at least node's dominators

Here is the call graph for this function:

Here is the caller graph for this function:

walk_postdominators()

def miasm.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 dictionary containing at least node's
postdominators

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

DotCellDescription

miasm.core.graph.DiGraph.DotCellDescription

static

Initial value:

=  namedtuple("DotCellDescription",
                                    ["text", "attr"])

---

The documentation for this class was generated from the following file:

• /home/serpilliere/projet/test_doc_miasm/miasm/miasm/core/graph.py