cfg.py

This module provides elements to define control flow graphs (CFG). It is based essentially on classes provided by the grandalf package.

class cfg.node(acode)

A node is a graph vertex that embeds a code object. It extends the Vertex class in order to compare nodes by their data blocks rather than their id.

Parameters:acode – an instance of block, func or xfunc.

data

the reference to the acode argument above.

e

inherited from grandalf, the list of edges with this node. In amoco, edges and vertices are called links and nodes.

Type:list[link]

c

reference to the connected component that contains this node.

Type:graph_core

view

the block or func view object associated with our data.

map

the map object associated with out data.

Type:mapper

cut(address)

reduce the block size up to given address if data is block.

deg()

returns the degree of this node (number of its links).

N(dir=0)

provides a list of neighbor nodes, all if dir parameter is 0, parent nodes if dir<0, children nodes if dir>0.

e_dir(dir=0)

provides a list of links, all if dir parameter is 0, incoming links if dir<0, outgoing links if dir>0.

e_in()

a shortcut for e_dir(-1).

e_out()

a shortcut for e_dir(+1).

e_with(v)

provides a link to or from v. Should be used with caution: if there is several links between current node and v this method gives the first one listed only, independently of the direction.

e_to(v)

provides the link from current node to node v.

e_from(v)

provides the link to current node from node v.

view

view property of the node’s code object.

Type:view

class cfg.link(x, y, w=1, data=None, connect=False)

A directed edge between two nodes. It extends Edge class in order to compare edges based on their data rather than id.

Parameters:

• x (node) – the source node.
• y (node) – the destination node.
• w (int) – an optional weight value, default 1.
• data – a list of conditional expressions associated with the link.
• connect – a flag to indicate that a new node should be automatically added to the connected component of its parent/child if it is defined (default False).

name

the name property returns the string composed of source and destination node’s addresses.

deg

1 if source and destination are the same node, 0 otherwise.

Type:int

v

inherited from grandalf, the 2-tuple (source,dest) nodes of the link.

Type:tuple[node]

feedback

a flag indicating that this link is involved in a loop, used internally by grandalf layout algorithm.

attach()

add current link to its node.e attribute list.

detach()

remove current link from its node.e attribute list.

class cfg.graph(*args, **kargs)

a <grandalf:Graph> that represents a set of functions as its individual connected components.

Parameters:

• V (iterable[node]) – the set of (possibly detached) nodes.
• E (iterable[link]) – the set of links of this graph.

C

the list of graph_core connected components of the graph.

support

the abstract memory zone holding all nodes contained in this graph.

Type:MemoryZone

overlay

defaults to None, another instance of MemoryZone with nodes of the graph that overlap other nodes already mapped in support.

get_by_name(name)

get the node with the given name (as string).

get_with_address(vaddr)

get the node that contains the given vaddr cst expression.

add_vertex(v[, support=None])

add node v to the graph and declare node support in the default MemoryZone or the overlay zone if provided as support argument. This method deals with a node v that cuts or swallows a previously added node.

remove_vertex(v)

remove node v from the graph.

add_edge(e)

add link to the graph as well as possible new nodes.

remove_edge(e)

remove the provided link.

get_vertices_count()

a synonym for order().

V()

generator of all nodes of the graph.

E()

generator of all links of the graph.

N(v, f_io=0)

returns the neighbors of node v in direction f_io.

path(x, y, f_io=0, hook=None)

order()

number of nodes in the graph.

norm()

number of links in the graph.

deg_min()

minimum degree of nodes.

deg_max()

maximum degree of nodes.

deg_avg()

average degree of nodes.

eps()

ratio of links over nodes (norm/order).

connected()

boolean flag indicating that the graph as only one connected component.

components()

synonym for attribute C.