xform_expr_infer.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 """Expression transformations using Prolog-style inferences"""
  19
  20 from core import *
  21 from xform_expr_basic import expr_neg
  22
  23
  24 # Capturing var
  25 class V:
  26
  27     def __init__(self, name):
  28         self.name = name
  29
  30     def __str__(self):
  31         return "V(%r)" % self.name
  32
  33     def __repr__(self):
  34         return self.__str__()
  35
  36
  37 class Failed(Exception):
  38     pass
  39
  40
  41 def _uni(ex, pat, ctx):
  42 #    print("_uni: %r vs %r" % (ex, pat))
  43
  44     if isinstance(pat, V):
  45         if pat.name in ctx and ctx[pat.name] != ex:
  46             raise Failed
  47         ctx[pat.name] = ex
  48
  49     elif type(ex) is type(pat):
  50         if isinstance(ex, EXPR):
  51             if len(ex.args) == len(pat.args):
  52                 _uni(ex.op, pat.op, ctx)
  53                 for i in range(len(ex.args)):
  54                     _uni(ex.args[i], pat.args[i], ctx)
  55             else:
  56                 raise Failed
  57         elif isinstance(ex, MEM):
  58             if ex.type == pat.type:
  59                 _uni(ex.expr, pat.expr, ctx)
  60             else:
  61                 raise Failed
  62         elif isinstance(ex, REG):
  63             _uni(ex.name, pat.name, ctx)
  64         elif isinstance(ex, ADDR):
  65             _uni(ex.addr, pat.addr, ctx)
  66         elif isinstance(ex, VALUE):
  67             _uni(ex.val, pat.val, ctx)
  68         else:
  69             if ex == pat:
  70                 return True
  71             raise Failed(str((ex, pat)))
  72
  73     else:
  74         raise Failed
  75
  76
  77 def uni(ex, pat):
  78     ctx = {}
  79     _uni(ex, pat, ctx)
  80     return ctx
  81
  82 RULES = []
  83
  84 RULES.append((
  85     EXPR("-", V("x"), V("x")),
  86     lambda W: VALUE(0)
  87 ))
  88
  89 RULES.append((
  90     EXPR("^", V("x"), V("x")),
  91     lambda W: VALUE(0)
  92 ))
  93
  94 RULES.append((
  95     EXPR("+", V("x"), VALUE(0)),
  96     lambda W: W["x"]
  97 ))
  98
  99 RULES.append((
 100     EXPR("^", V("x"), VALUE(0)),
 101     lambda W: W["x"]
 102 ))
 103
 104 RULES.append((
 105     EXPR("&", VALUE(V("x1")), VALUE(V("x2"))),
 106     lambda W: VALUE(W["x1"] & W["x2"])
 107 ))
 108
 109 RULES.append((
 110     EXPR("-", VALUE(V("x1")), VALUE(V("x2"))),
 111     lambda W: VALUE(W["x1"] - W["x2"])
 112 ))
 113
 114 RULES.append((
 115     EXPR(V("rel_op"), EXPR("+", V("x1"), V("x2")), VALUE(0)),
 116     lambda W: W["rel_op"] in ("==", "!=", "<", "<=", ">=", ">"),
 117     lambda W: EXPR(W["rel_op"], W["x1"], expr_neg(W["x2"]))
 118 ))
 119
 120 RULES.append((
 121     EXPR("!", EXPR(V("rel_op"), V("x1"), V("x2"))),
 122     lambda W: W["rel_op"] in ("==", "!=", "<", "<=", ">=", ">"),
 123     lambda W: EXPR(COND.NEG[W["rel_op"]], W["x1"], W["x2"])
 124 ))
 125
 126 RULES.append((
 127     EXPR("!=", EXPR(V("rel_op"), V("x1"), V("x2")), VALUE(0)),
 128     lambda W: W["rel_op"] in ("==", "!=", "<", "<=", ">=", ">"),
 129     lambda W: EXPR(W["rel_op"], W["x1"], W["x2"])
 130 ))
 131
 132 RULES.append((
 133     EXPR("==", EXPR(V("rel_op"), V("x1"), V("x2")), VALUE(0)),
 134     lambda W: W["rel_op"] in ("==", "!=", "<", "<=", ">=", ">"),
 135     lambda W: EXPR(COND.NEG[W["rel_op"]], W["x1"], W["x2"])
 136 ))
 137
 138
 139 def simplify(ex):
 140     for r in RULES:
 141         pat = r[0]
 142         if len(r) == 2:
 143             test = None
 144             prod = r[1]
 145         else:
 146             test = r[1]
 147             prod = r[2]
 148         #print("Trying", repr(pat))
 149         try:
 150             ctx = uni(ex, pat)
 151             #print("Matched")
 152             if test:
 153                 if not test(ctx):
 154                     continue
 155                 #print("Test passed")
 156         except Failed:
 157             #print("Failed")
 158             continue
 159         return prod(ctx)
 160
 161
 162 if __name__ == "__main__":
 163     ex = EXPR("-", REG("a1"), REG("a1"))
 164     ex = EXPR("^", REG("a1"), REG("a1"))
 165     ex = EXPR("^", REG("a1"), VALUE(1))
 166     ex = EXPR("==", EXPR("+", REG("a1"), EXPR("NEG", REG("a2"))), VALUE(0))
 167     ex = EXPR("!=", EXPR("+", REG("a1"), EXPR("NEG", REG("a2"))), VALUE(0))
 168     ex = EXPR("<", EXPR("+", REG("a1"), EXPR("NEG", REG("a2"))), VALUE(0))
 169     print(ex, repr(ex))
 170     print(simplify(ex))