tail recursion, common sub-expressions, Sisal

I have two queries.


First can someone point me to treatments (preferably available at an ftp
site) of tail recursion elimination (TRE). Specifically I am looking for a
treatment that talks about TRE, and about transforming a linearly
recursive function into tail recursive form, to which TRE could then be
applied. I would also be interested in any techniques for doubly (and
above) recursive functions (I gather that in the general case this is
theoretically not possible). The context I will be doing such
transformations in is that of a functional language, but treatments which
look at TRE in the imperative setting are fine too.


My second query concerns the treatment of common sub-expressions (and loop
invariants). In a "traditional" compiler model common sub-expressions are
represented by shared nodes in a DAG. The approach taken is that the first
time we encounter a common sub-expression, E, we will compute E into some
temporary, T, and then when we subsequently encounter E, we will simply use
T, rather than recompute E. The assumption behind this model is that all uses
of E can be represented by the information in a single shared node, since the
information needed to use E is the same for all uses of it. I was wondering
if anyone had any experience with handling common sub-expressions where this
assumption did not hold. To see how this could arise consider a compiler for
a functional language which transforms functional array constructions into
imperative array constructions (the Sisal compiler is a good example here).
Now consider the following piece of code (assume that all array sizes are
"known" at compile time),


    let
        A = some_array_construction
    in
        (if some_condition then (A cat B) else (B cat A)) cat A;


Here A is a common sub-expression for the 'in' clause. Using the traditional
model of common sub-expressions the compiler would emit code of the following
form (here SA=size(A), SB=size(B)),


    allocate a temporary T of size SA
    compute A into T // common sub-expression
    allocate result R of size 2*SA+SB
    if some_condition // A cat B
        copy T into R[1..SA]
        copy B into R[SA+1..SA+SB]
    else // B cat A
        copy B into R[1..SA]
        copy A into R[SA+1..SA+SB]
    endif;
    copy T into R[SA+SB+1..2*SA+SB] // the final cat of A


While this code is a lot better than the naive compilation, it is not optimal.
An "optimal" compilation is,


    allocate result R of size 2*SA+SB
    if some_condition // A cat B cat A
        compute A into both R[1..SA] and R[SA+SB+1..2*SA+SB]
        copy B into R[SA+1..SA+SB]
    else // B cat A cat A
        copy B into R[1..SA]
        compute A into both R[SA+1..SA+SB] and R[SA+SB+1..2*SA+SB]
    endif;


where "compute ... into both" means that we do two stores of computed array
elements, one store per target address.


The interesting thing about the optimal code is that while A is a common
sub-expression, it cannot be represented using the traditional DAG model,
because the information we need to use A differs according to each use. In
the above case for example we need to store 1..SA, SA+SB+1..2*SA+SB, SA+1..
SA+SB, and SA+SB+1..2*SA+SB to use A. I was wondering if anyone had any
experience of, or suggestions on, how to deal with this kind of common sub
expression. Someone familiar with the compilation of Sisal might be able to
suggest something, as I know that this problem was present in early versions
of the Sisal compiler - it essentially produced the non-optimal compilation
above when the value of an array expression was used more than once in a
block.


graham
--

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