xform_bblock.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 basic blocks"""
  19
  20 from core import *
  21 from xform_expr import expr_subst
  22
  23
  24 def remove_sfunc(bblock, name):
  25     for i, inst in enumerate(bblock.items):
  26         if inst.op == "SFUNC" and inst.args[0].args[0].name == name:
  27             dead = Inst(None, "DEAD", [])
  28             dead.addr = inst.addr
  29             bblock.items[i] = dead
  30             bblock.items[i].comments["org_inst"] = inst
  31
  32
  33 def remove_trailing_jumps_bblock(bblock, remove_returns=False):
  34     """Trailing jumps are encoded as out edges of basic block, and
  35     superfluous for most deeper transformations (but useful for
  36     surface transformations which should maintain instruction
  37     correspondence to the original input). This pass removes them.
  38     """
  39     to_remove = ["goto", "if"]
  40     if remove_returns:
  41         to_remove.append("return")
  42
  43     last_jump = None
  44     for i in range(len(bblock.items) -1, -1, -1):
  45         if bblock.items[i].op in to_remove:
  46             last_jump = i
  47         else:
  48             break
  49     if last_jump is not None:
  50         #print("Removing: ", bblock.items[last_jump:])
  51         del bblock.items[last_jump:]
  52
  53
  54 def bblock_propagation(bblock, propagated_types, subst_insts=True):
  55
  56     def kill_subst_uses(subst, kill_var):
  57         "Remove from subst dict any expressions involving kill_var"
  58         def not_used(var, expr):
  59             # Here we assume that expression can be at most reference to a var,
  60             # which is true for at most copy propagation, but to handle expr
  61             # propagation, need to do better
  62             return var not in expr
  63         subst = dict((k, v) for k, v in subst.items() if not_used(kill_var, v))
  64         # We of course should kill state for var itself
  65         subst.pop(kill_var, None)
  66         return subst
  67
  68     state = bblock.props.get("state_in", {})
  69     for i, inst in enumerate(bblock.items):
  70
  71         n_dest = inst.dest
  72         kill_n_dest = False
  73         if isinstance(n_dest, MEM):
  74             new = expr_subst(n_dest, state)
  75             if new:
  76                 n_dest = new
  77                 kill_n_dest = True
  78
  79         args = copy.deepcopy(inst.args)
  80
  81         for arg_no, arg in enumerate(args):
  82             repl = expr_subst(arg, state)
  83             if repl:
  84                 args[arg_no] = repl
  85
  86         for dest in inst.defs():
  87             # Calling kill_subst_uses isn't really needed for const propagation
  88             # (as variables aren't propagated), but needed for copy propagation
  89             # and higher.
  90             state = kill_subst_uses(state, dest)
  91
  92         if kill_n_dest:
  93             # Need to kill n_dest, which was MEM and could have been substituted
  94             # TODO: Propagating MEM references is in general not safe
  95             state = kill_subst_uses(state, n_dest)
  96
  97         if inst.op == "=" and isinstance(args[0], propagated_types):
  98             # Don't propagate expressions with side effects
  99             if not inst.side_effect():
 100                 assert n_dest
 101                 state[n_dest] = args[0]
 102
 103         if subst_insts:
 104             if inst.op == "if":
 105                 # Replace in-place because of if statement/out-edges label shared COND
 106                 inst.args[0].expr = args[0].expr
 107             else:
 108                 inst.args = args
 109             inst.dest = n_dest
 110
 111     bblock.props["state_out"] = state
 112
 113
 114 def bblock_const_propagation(bblock, subst_insts=True):
 115     "Propagate only constant values"
 116     bblock_propagation(bblock, (VALUE, ADDR), subst_insts)
 117
 118 def bblock_copy_propagation(bblock, subst_insts=True):
 119     "Propagate constants and register copies"
 120     bblock_propagation(bblock, (VALUE, ADDR, REG), subst_insts)
 121
 122 def bblock_mem_propagation(bblock, subst_insts=True):
 123     "Propagate constants and register copies"
 124     bblock_propagation(bblock, (VALUE, ADDR, REG, MEM), subst_insts)
 125
 126 def bblock_expr_propagation(bblock, subst_insts=True):
 127     "Propagate constants and register copies"
 128     bblock_propagation(bblock, (VALUE, ADDR, REG, MEM, EXPR), subst_insts)