Re: Decompiler, Expression Propagation, Intermediate Representation problems

On May 11, 5:11 pm, Jeremy Singer <jsin...@cs.man.ac.uk> wrote:
> > (1) Expression Propagation Problem
> > c = a + b
> > e = c + d
>
> > they will be the following after expression propagation
>
> > c = a + b
> > e = a + b + d
>
> Cristina Cifuentes [1] refers to this as the "forward substitution"
> method. She restricts its application to temporary variables that are
> defined then used only once. Cifuentes' thesis [2] has lots of
> nitty-gritty detail.
>
> Regards,
> Jeremy
>
> [1]
>
> @article{cifuentes1995decompilation,
> title={Decompilation of binary programs},
> author={Cifuentes, C. and Gough, K.J.},
> journal={Software: Practice and Experience},
> volume={25},
> number={7},
> pages={811--829},
> year={1995},
> doi = "10.1002/spe.4380250706",
>
> }
>
> [2] C Cifuentes, Reverse Compilation Techniques, PhD thesis, Faculty of
> Information Technology, Queensland University of Technology, July
1994.ftp://ftp.it.uq.edu.au/pub/CSM/dcc/decompilation_thesis.ps.gz
>
> > in a situation it's not safe:
>
> > c = a + b
> > e = c + d
> > a = 1
> > some_use(e) ; we must forbid the propagation of e = c+d since a = 1
> > kills c = a + b so does e = c + d
>
> > Now is the question: How to efficently/correctly implement this
> > propagation? What's the analysis' name in theory?


Thanks a lot for the hint.


I come up with a naive algorithm here, in python:


a, b, c, d, e, f = Var('a'), Var('b'), Var('c'), Var('d'), Var('e'),
Var('f')
block = [
        Assign(e, Add(Add(b, d), c)),
        Assign(c, Const(1)),
        Assign(f, e),
]


@trace
def killed(expr, i, j):
        return any(stmt.left == expr for stmt in block[i:j])


@trace
def define(expr, i):
        for i, stmt in reversed(list(enumerate(block[:i]))):
                if stmt.left == expr:
                        return i


def contains(expr):
        if isinstance(expr, SimpleExpr):
                yield expr
        else:
                for x in expr:
                        for y in contains(x):
                                yield y
@trace
def reach(i, j):
        s = block[i]
        if killed(s.left, i+1, j):
                return False
        for x in contains(s.right):
                d = define(x, i)
                if d is None:
                        if killed(x, i, j):
                                return False
                else:
                        if not reach(d, j):
                                return False
        return True


reach(0, 2)

Return to the comp.compilers page.
Search the comp.compilers archives again.