xform_graph.py

   1 # ScratchABlock - Program analysis and decompilation framework
   2 #
   3 # Copyright (c) 2015-2018 Paul Sokolovsky
   4 #
   5 # This program is free software: you can redistribute it and/or modify
   6 # it under the terms of the GNU General Public License as published by
   7 # the Free Software Foundation, either version 3 of the License, or
   8 # (at your option) any later version.
   9 #
  10 # This program is distributed in the hope that it will be useful,
  11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 # GNU General Public License for more details.
  14 #
  15 # You should have received a copy of the GNU General Public License
  16 # along with this program. If not, see <http://www.gnu.org/licenses/>.
  17
  18 """Transformation passes on generic graphs (not CFGs)"""
  19
  20 from dom import compute_idom
  21 from utils import make_set
  22 import dot
  23
  24
  25 def t1_transform(g, node):
  26     if g.has_edge(node, node):
  27         print("t1: yes", node)
  28         g.remove_edge(node, node)
  29         dot.debug_dot(g)
  30         return True
  31     return False
  32
  33
  34 def t2_transform(g, node):
  35     if g.degree_in(node) == 1:
  36         print("t2: yes", node)
  37         pred = g.pred(node)[0]
  38         g.remove_edge(pred, node)
  39         g.move_succ(node, pred)
  40         g[pred].setdefault("folded", []).append(node)
  41         g.remove_node(node)
  42         dot.debug_dot(g)
  43         return True
  44     print("t2: no", node)
  45     return False
  46
  47
  48 def reduce_graph(g):
  49     changed = True
  50     while changed:
  51         print("!iter")
  52         changed = False
  53         for node in list(g.nodes()):
  54             # Might have been deleted by previous iteration
  55             if node in g:
  56                 changed |= t1_transform(g, node)
  57                 changed |= t2_transform(g, node)
  58
  59
  60 def recursive_relation(g, n, in_prop, out_prop, is_reflexive=False):
  61     "Helper function to compute relation closures, don't use directly."
  62     if out_prop in g[n]:
  63         return g[n][out_prop]
  64     if in_prop not in g[n]:
  65         return
  66
  67     val = g[n][in_prop]
  68     if val is None:
  69         val = set()
  70     else:
  71         val = make_set(val)
  72     res = set()
  73
  74     for rel_n in val:
  75         res |= recursive_relation(g, rel_n, in_prop, out_prop, is_reflexive)
  76
  77     res |= val
  78     if is_reflexive:
  79         res |= {n}
  80
  81     g[n][out_prop] = res
  82     return res
  83
  84
  85 def transitive_closure(g, in_prop, out_prop):
  86     """Compute a transitive closure of some graph relation.
  87
  88     in_prop: Name of node property storing relation (i.e.
  89              value of property should be id of another node).
  90     out_prop: Name of node property to store transitive closure
  91               of the relation.
  92     """
  93
  94     for n in g.nodes():
  95         recursive_relation(g, n, in_prop, out_prop, False)
  96
  97
  98 def reflexive_transitive_closure(g, in_prop, out_prop):
  99     """Compute a reflexive-transitive closure of some graph relation.
 100
 101     in_prop: Name of node property storing relation (i.e.
 102              value of property should be id of another node).
 103     out_prop: Name of node property to store transitive closure
 104               of the relation.
 105     """
 106
 107     for n in g.nodes():
 108         recursive_relation(g, n, in_prop, out_prop, True)
 109
 110
 111 def idom_to_sdom(g):
 112     transitive_closure(g, "idom", "sdom")
 113
 114
 115 def idom_to_dom(g):
 116     reflexive_transitive_closure(g, "idom", "dom")
 117
 118
 119 def idom_children(g, node):
 120     """Return children of idom node.
 121
 122     The implementation here is very inefficient.
 123     """
 124
 125     res = []
 126     for n, info in g.nodes_props():
 127         if info["idom"] == node:
 128             res.append(n)
 129     return res
 130
 131
 132 def idom_transitive_dom(g, node1, node2):
 133     "Check whether node1 dominates node2, by walking idom chain."
 134     while node2 is not None:
 135         if node1 == node2:
 136             return True
 137         node2 = g[node2]["idom"]
 138     return False
 139
 140
 141 def compute_dom_frontier_cytron(g, node=None):
 142     """Compute dominance frontier of each node.
 143
 144     Intuitively, dominance frontier of a node X is a set of
 145     successors of "last" nodes which X dominates. I.e., if
 146     X dominates A, but not its successor B, then B is in X's
 147     dominance frontier.
 148
 149     Ref: Efficiently Computing Static Single Assignment Form and the Control
 150     Dependence Graph, Cytron, Ferrante, Rosen, Wegman, Zedeck
 151     Ref: Appel p.406.
 152     """
 153
 154     if node is None:
 155         node = g.entry()
 156
 157     df = set()
 158
 159     for y in g.succ(node):
 160         if g[y]["idom"] != node:
 161             df.add(y)
 162
 163     for z in idom_children(g, node):
 164         compute_dom_frontier_cytron(g, z)
 165         for y in g[z]["dom_front"]:
 166             if g[y]["idom"] != node:
 167                 df.add(y)
 168
 169     g[node]["dom_front"] = df
 170
 171
 172 def compute_dom_frontier_cooper(g):
 173     """Compute dominance frontier of each node.
 174
 175     Ref: A Simple, Fast Dominance Algorithm, Cooper, Harvey, Kennedy
 176     """
 177     for n, info in g.nodes_props():
 178         info["dom_front"] = set()
 179
 180     for n, info in g.nodes_props():
 181         preds = g.pred(n)
 182         if len(preds) > 1:
 183             for p in preds:
 184                 runner = p
 185                 while runner != info["idom"]:
 186                     g[runner]["dom_front"].add(n)
 187                     runner = g[runner]["idom"]