AST Manipulation and Common Subexpression Elimination

[Duncan Booth]

Robert Kern <kern at ugcs.caltech.edu> wrote in
news:bmqovv$o2f$1 at naig.caltech.edu: 

> 
> 1. Can I do better than brute-force traversing the AST and trying to
> match each subtree to the other subtrees (using something like the
> match() function given in the parser module example)?

Use a dictionary.

If you convert the AST to nested tuples, then a code fragment such as the 
one below will suffice to make all common subexpressions share the same 
tuples. It fills 'info' with exactly one entry for each unique tuple in the 
original ast and counts the number of times it occurs. It should be easy 
enough then to go through the dictionary in order of increasing tuple 
length) and if an expression occurs more than once create a new AST to 
precalculate the value and assign to a temporary.

import parser

def optimise(ast, info):
    new = []
    for t in ast:
        if isinstance(t, tuple):
            new.append(optimise(t, info))
        else:
            new.append(t)
        
    new = tuple(new)
    new, oldcount = info.get(new, (new, 0))
    info[new] = (new, oldcount+1)
    return new

t = parser.ast2tuple(parser.expr("(1-x)*(1-x)/(1-x)"))
t_info = {}
t1 = optimise(t, t_info)
for node,v in t_info.values():
    print v,repr(node)[:50]

            


-- 
Duncan Booth                                             duncan at rcp.co.uk
int month(char *p){return(124864/((p[0]+p[1]-p[2]&0x1f)+1)%12)["\5\x8\3"
"\6\7\xb\1\x9\xa\2\0\4"];} // Who said my code was obscure?