Sun, 9 Oct 1994 23:33:59 GMT

Related articles |
---|

tail recursion, common sub-expressions, Sisal graham@maths.su.oz.au (1994-10-09) |

Newsgroups: | comp.compilers |

From: | graham@maths.su.oz.au (Graham Matthews) |

Keywords: | optimize, question |

Organization: | School of Mathematics and Statistics, University of Sydney |

Date: | Sun, 9 Oct 1994 23:33:59 GMT |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.