Miasm2
 All Classes Namespaces Files Functions Variables Typedefs Properties Macros
Public Member Functions | Static Public Member Functions | List of all members
miasm2.expression.expression.DiGraphExpr Class Reference
+ Inheritance diagram for miasm2.expression.expression.DiGraphExpr:
+ Collaboration diagram for miasm2.expression.expression.DiGraphExpr:

Public Member Functions

def node2str
 
def edge2str
 
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
 

Detailed Description

Enhanced graph for Expression diplay
Expression are displayed as a tree with node and edge labeled
with only relevant information

Definition at line 74 of file expression.py.

Member Function Documentation

def miasm2.core.graph.DiGraph.__repr__ (   self)
inherited

Definition at line 14 of file graph.py.

14 
15  def __repr__(self):
16  out = []
17  for node in self._nodes:
18  out.append(str(node))
19  for src, dst in self._edges:
20  out.append("%s -> %s" % (src, dst))
21  return '\n'.join(out)
def miasm2.core.graph.DiGraph.add_edge (   self,
  src,
  dst 
)
inherited

Definition at line 46 of file graph.py.

46 
47  def add_edge(self, src, dst):
48  if not src in self._nodes:
49  self.add_node(src)
50  if not dst in self._nodes:
51  self.add_node(dst)
52  self._edges.append((src, dst))
53  self._nodes_succ[src].append(dst)
54  self._nodes_pred[dst].append(src)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.add_node (   self,
  node 
)
inherited

Definition at line 28 of file graph.py.

28 
29  def add_node(self, node):
30  if node in self._nodes:
31  return
32  self._nodes.add(node)
33  self._nodes_succ[node] = []
34  self._nodes_pred[node] = []

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.add_uniq_edge (   self,
  src,
  dst 
)
inherited
Add an edge from @src to @dst if it doesn't already exist

Definition at line 55 of file graph.py.

55 
56  def add_uniq_edge(self, src, dst):
57  """Add an edge from @src to @dst if it doesn't already exist"""
58  if (src not in self._nodes_succ or
59  dst not in self._nodes_succ[src]):
60  self.add_edge(src, dst)

+ Here is the call graph for this function:

def miasm2.core.graph.DiGraph.compute_back_edges (   self,
  head 
)
inherited
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.

397  def compute_back_edges(self, head):
398  """
399  Computes all back edges from a node to a
400  dominator in the graph.
401  :param head: head of graph
402  :return: yield a back edge
403  """
404  dominators = self.compute_dominators(head)
405 
406  # traverse graph
407  for node in self.walk_depth_first_forward(head):
408  for successor in self.successors_iter(node):
409  # check for a back edge to a dominator
410  if successor in dominators[node]:
411  edge = (node, successor)
412  yield edge

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.compute_dominance_frontier (   self,
  head 
)
inherited
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.

319  def compute_dominance_frontier(self, head):
320  """
321  Compute the dominance frontier of the graph
322 
323  Source: Cooper, Keith D., Timothy J. Harvey, and Ken Kennedy.
324  "A simple, fast dominance algorithm."
325  Software Practice & Experience 4 (2001), p. 9
326  """
327  idoms = self.compute_immediate_dominators(head)
328  frontier = {}
329 
330  for node in idoms:
331  if self._nodes_pred[node] >= 2:
332  for predecessor in self.predecessors_iter(node):
333  runner = predecessor
334  if runner not in idoms:
335  continue
336  while runner != idoms[node]:
337  if runner not in frontier:
338  frontier[runner] = set()
339 
340  frontier[runner].add(node)
341  runner = idoms[runner]
342  return frontier
def compute_immediate_dominators
Definition: graph.py:306

+ Here is the call graph for this function:

def miasm2.core.graph.DiGraph.compute_dominators (   self,
  head 
)
inherited
Compute the dominators of the graph

Definition at line 221 of file graph.py.

222  def compute_dominators(self, head):
223  """Compute the dominators of the graph"""
224  return self._compute_generic_dominators(head,
225  self.reachable_sons,
226  self.predecessors_iter,
227  self.successors_iter)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.compute_immediate_dominators (   self,
  head 
)
inherited
Compute the immediate dominators of the graph

Definition at line 306 of file graph.py.

307  def compute_immediate_dominators(self, head):
308  """Compute the immediate dominators of the graph"""
309  dominators = self.compute_dominators(head)
310  idoms = {}
311 
312  for node in dominators:
313  for predecessor in self.walk_dominators(node, dominators):
314  if predecessor in dominators[node] and node != predecessor:
315  idoms[node] = predecessor
316  break
317  return idoms
def compute_immediate_dominators
Definition: graph.py:306

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.compute_natural_loops (   self,
  head 
)
inherited
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.

383  def compute_natural_loops(self, head):
384  """
385  Computes all natural loops in the graph.
386 
387  Source: Aho, Alfred V., Lam, Monica S., Sethi, R. and Jeffrey Ullman.
388  "Compilers: Principles, Techniques, & Tools, Second Edition"
389  Pearson/Addison Wesley (2007), Chapter 9.6.6
390  :param head: head of the graph
391  :return: yield a tuple of the form (back edge, loop body)
392  """
393  for a, b in self.compute_back_edges(head):
394  body = self._compute_natural_loop_body(b, a)
395  yield ((b, a), body)

+ Here is the call graph for this function:

def miasm2.core.graph.DiGraph.compute_postdominators (   self,
  leaf 
)
inherited
Compute the postdominators of the graph

Definition at line 228 of file graph.py.

229  def compute_postdominators(self, leaf):
230  """Compute the postdominators of the graph"""
231  return self._compute_generic_dominators(leaf,
232  self.reachable_parents,
233  self.successors_iter,
234  self.predecessors_iter)

+ Here is the call graph for this function:

def miasm2.core.graph.DiGraph.compute_strongly_connected_components (   self)
inherited
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.

436  """
437  Partitions the graph into strongly connected components.
438 
439  Iterative implementation of Gabow's path-based SCC algorithm.
440  Source: Gabow, Harold N.
441  "Path-based depth-first search for strong and biconnected components."
442  Information Processing Letters 74.3 (2000), pp. 109--110
443 
444  The iterative implementation is inspired by Mark Dickinson's
445  code:
446  http://code.activestate.com/recipes/
447  578507-strongly-connected-components-of-a-directed-graph/
448  :return: yield a strongly connected component
449  """
450  stack = []
451  boundaries = []
452  counter = len(self.nodes())
453 
454  # init index with 0
455  index = {v: 0 for v in self.nodes()}
456 
457  # state machine for worklist algorithm
458  VISIT, HANDLE_RECURSION, MERGE = 0, 1, 2
459  NodeState = namedtuple('NodeState', ['state', 'node'])
460 
461  for node in self.nodes():
462  # next node if node was already visited
463  if index[node]:
464  continue
465 
466  todo = [NodeState(VISIT, node)]
467  done = set()
468 
469  while todo:
470  current = todo.pop()
471 
472  if current.node in done:
473  continue
474 
475  # node is unvisited
476  if current.state == VISIT:
477  stack.append(current.node)
478  index[current.node] = len(stack)
479  boundaries.append(index[current.node])
480 
481  todo.append(NodeState(MERGE, current.node))
482  # follow successors
483  for successor in self.successors_iter(current.node):
484  todo.append(NodeState(HANDLE_RECURSION, successor))
485 
486  # iterative handling of recursion algorithm
487  elif current.state == HANDLE_RECURSION:
488  # visit unvisited successor
489  if index[current.node] == 0:
490  todo.append(NodeState(VISIT, current.node))
491  else:
492  # contract cycle if necessary
493  while index[current.node] < boundaries[-1]:
494  boundaries.pop()
495 
496  # merge strongly connected component
497  else:
498  if index[current.node] == boundaries[-1]:
499  boundaries.pop()
500  counter += 1
501  scc = set()
502 
503  while index[current.node] <= len(stack):
504  popped = stack.pop()
505  index[popped] = counter
506  scc.add(popped)
507 
508  done.add(current.node)
509 
510  yield scc
def compute_strongly_connected_components
Definition: graph.py:434

+ Here is the call graph for this function:

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

Definition at line 61 of file graph.py.

61 
62  def del_edge(self, src, dst):
63  self._edges.remove((src, dst))
64  self._nodes_succ[src].remove(dst)
65  self._nodes_pred[dst].remove(src)

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.del_node (   self,
  node 
)
inherited
Delete the @node of the graph; Also delete every edge to/from this
@node

Definition at line 35 of file graph.py.

35 
36  def del_node(self, node):
37  """Delete the @node of the graph; Also delete every edge to/from this
38  @node"""
39 
40  if node in self._nodes:
41  self._nodes.remove(node)
42  for pred in self.predecessors(node):
43  self.del_edge(pred, node)
44  for succ in self.successors(node):
45  self.del_edge(node, succ)

+ Here is the call graph for this function:

def miasm2.core.graph.DiGraph.dot (   self)
inherited

Definition at line 124 of file graph.py.

125  def dot(self):
126  out = """
127 digraph asm_graph {
128 graph [
129 splines=polyline,
130 ];
131 node [
132 fontsize = "16",
133 shape = "box"
134 ];
135 """
136  for node in self.nodes():
137  out += '%s [label="%s"];\n' % (
138  hash(node) & 0xFFFFFFFFFFFFFFFF, self.node2str(node))
139 
140  for src, dst in self.edges():
141  out += '%s -> %s [label="%s"]\n' % (hash(src) & 0xFFFFFFFFFFFFFFFF,
142  hash(dst) & 0xFFFFFFFFFFFFFFFF,
143  self.edge2str(src, dst))
144  out += "}"
145  return out

+ Here is the call graph for this function:

def miasm2.expression.expression.DiGraphExpr.edge2str (   self,
  nfrom,
  nto 
)

Definition at line 95 of file expression.py.

95 
96  def edge2str(self, nfrom, nto):
97  if isinstance(nfrom, ExprCompose):
98  for i in nfrom.args:
99  if i[0] == nto:
100  return "[%s, %s]" % (i[1], i[2])
101  elif isinstance(nfrom, ExprCond):
102  if nfrom.cond == nto:
103  return "?"
104  elif nfrom.src1 == nto:
105  return "True"
106  elif nfrom.src2 == nto:
107  return "False"
108 
109  return ""
110 
111 
112 # IR definitions
def miasm2.core.graph.DiGraph.edge2str (   src,
  dst 
)
staticinherited

Definition at line 121 of file graph.py.

122  def edge2str(src, dst):
123  return ""

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.edges (   self)
inherited

Definition at line 25 of file graph.py.

25 
26  def edges(self):
27  return self._edges

+ Here is the caller graph for this function:

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

Definition at line 100 of file graph.py.

101  def find_path(self, src, dst, cycles_count=0, done=None):
102  if done is None:
103  done = {}
104  if dst in done and done[dst] > cycles_count:
105  return [[]]
106  if src == dst:
107  return [[src]]
108  out = []
109  for node in self.predecessors(dst):
110  done_n = dict(done)
111  done_n[dst] = done_n.get(dst, 0) + 1
112  for path in self.find_path(src, node, cycles_count, done_n):
113  if path and path[0] == src:
114  out.append(path + [dst])
115  return out

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.heads (   self)
inherited

Definition at line 97 of file graph.py.

97 
98  def heads(self):
99  return [x for x in self.heads_iter()]

+ Here is the call graph for this function:

def miasm2.core.graph.DiGraph.heads_iter (   self)
inherited

Definition at line 92 of file graph.py.

92 
93  def heads_iter(self):
94  for node in self._nodes:
95  if not self._nodes_pred[node]:
96  yield node

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.leaves (   self)
inherited

Definition at line 89 of file graph.py.

89 
90  def leaves(self):
91  return [x for x in self.leaves_iter()]

+ Here is the call graph for this function:

def miasm2.core.graph.DiGraph.leaves_iter (   self)
inherited

Definition at line 84 of file graph.py.

84 
85  def leaves_iter(self):
86  for node in self._nodes:
87  if not self._nodes_succ[node]:
88  yield node

+ Here is the caller graph for this function:

def miasm2.expression.expression.DiGraphExpr.node2str (   self,
  node 
)

Definition at line 80 of file expression.py.

80 
81  def node2str(self, node):
82  if isinstance(node, ExprOp):
83  return node.op
84  elif isinstance(node, ExprId):
85  return node.name
86  elif isinstance(node, ExprMem):
87  return "@%d" % node.size
88  elif isinstance(node, ExprCompose):
89  return "{ %d }" % node.size
90  elif isinstance(node, ExprCond):
91  return "? %d" % node.size
92  elif isinstance(node, ExprSlice):
93  return "[%d:%d]" % (node.start, node.stop)
94  return str(node)
def miasm2.core.graph.DiGraph.node2str (   node)
staticinherited

Definition at line 117 of file graph.py.

118  def node2str(node):
119  return str(node)

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.nodes (   self)
inherited

Definition at line 22 of file graph.py.

22 
23  def nodes(self):
24  return self._nodes

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.predecessors (   self,
  node 
)
inherited

Definition at line 72 of file graph.py.

72 
73  def predecessors(self, node):
74  return [x for x in self.predecessors_iter(node)]

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.predecessors_iter (   self,
  node 
)
inherited

Definition at line 66 of file graph.py.

66 
67  def predecessors_iter(self, node):
68  if not node in self._nodes_pred:
69  raise StopIteration
70  for n_pred in self._nodes_pred[node]:
71  yield n_pred

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.reachable_parents (   self,
  leaf 
)
inherited
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.

168  def reachable_parents(self, leaf):
169  """Compute all parents of node @leaf. Each parent is an immediate
170  predecessor of an arbitrary, already yielded parent of @leaf"""
171  return self._reachable_nodes(leaf, self.predecessors_iter)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.reachable_sons (   self,
  head 
)
inherited
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.

163  def reachable_sons(self, head):
164  """Compute all nodes reachable from node @head. Each son is an
165  immediate successor of an arbitrary, already yielded son of @head"""
166  return self._reachable_nodes(head, self.successors_iter)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.successors (   self,
  node 
)
inherited

Definition at line 81 of file graph.py.

81 
82  def successors(self, node):
83  return [x for x in self.successors_iter(node)]

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.successors_iter (   self,
  node 
)
inherited

Definition at line 75 of file graph.py.

75 
76  def successors_iter(self, node):
77  if not node in self._nodes_succ:
78  raise StopIteration
79  for n_suc in self._nodes_succ[node]:
80  yield n_suc

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.walk_breadth_first_backward (   self,
  head 
)
inherited
Performs a breadth first search on the reversed graph from @head

Definition at line 374 of file graph.py.

375  def walk_breadth_first_backward(self, head):
376  """Performs a breadth first search on the reversed graph from @head"""
377  return self._walk_generic_first(head, 0, self.predecessors_iter)

+ Here is the call graph for this function:

def miasm2.core.graph.DiGraph.walk_breadth_first_forward (   self,
  head 
)
inherited
Performs a breadth first search on the graph from @head

Definition at line 366 of file graph.py.

367  def walk_breadth_first_forward(self, head):
368  """Performs a breadth first search on the graph from @head"""
369  return self._walk_generic_first(head, 0, self.successors_iter)

+ Here is the call graph for this function:

def miasm2.core.graph.DiGraph.walk_depth_first_backward (   self,
  head 
)
inherited
Performs a depth first search on the reversed graph from @head

Definition at line 378 of file graph.py.

379  def walk_depth_first_backward(self, head):
380  """Performs a depth first search on the reversed graph from @head"""
381  return self._walk_generic_first(head, -1, self.predecessors_iter)

+ Here is the call graph for this function:

def miasm2.core.graph.DiGraph.walk_depth_first_forward (   self,
  head 
)
inherited
Performs a depth first search on the graph from @head

Definition at line 370 of file graph.py.

371  def walk_depth_first_forward(self, head):
372  """Performs a depth first search on the graph from @head"""
373  return self._walk_generic_first(head, -1, self.successors_iter)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.walk_dominators (   self,
  node,
  dominators 
)
inherited
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.

285  def walk_dominators(self, node, dominators):
286  """Return an iterator of the ordered list of @node's dominators
287  The function doesn't return the self reference in dominators.
288  @node: The start node
289  @dominators: The dictionnary containing at least node's dominators
290  """
291  return self._walk_generic_dominator(node,
292  dominators,
293  self.predecessors_iter)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.core.graph.DiGraph.walk_postdominators (   self,
  node,
  postdominators 
)
inherited
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.

295  def walk_postdominators(self, node, postdominators):
296  """Return an iterator of the ordered list of @node's postdominators
297  The function doesn't return the self reference in postdominators.
298  @node: The start node
299  @postdominators: The dictionnary containing at least node's
300  postdominators
301 
302  """
303  return self._walk_generic_dominator(node,
304  postdominators,
305  self.successors_iter)

+ Here is the call graph for this function:


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