[m-dev.] Deforestation question

[Ralph Becket]

>From Simon Taylor on 12/02/2001 23:42:01
> 
> What Ralph wants is the unboxing optimization that we've
> discussed many times but have never implemented because we
> couldn't come up with a decent heuristic.

The following example illustrates a common idiom (particularly
so with higher order code):

:- func fib_2(int, {int, int}) = int.

fib_2(N, {A, B}) =
	( if N =< 1 then A else
	  if N =  2 then B else
	    fib_2(N - 1, {B, A + B})
	).

Ideally we would like the compiler to turn this into the
following:

fib_2(N, {A, B}) = fib_2a(N, A, B).

fib_2a(N, A, B) =
	( if N =< 1 then A else
	  if N =  2 then B else
	    fib_2a(N - 1, B, A + B)
	).

and do away with the need to worry about allocating {}/2
cells on the heap etc. etc.

[I believe that in a loop unrolled n times the compiler will
not allocate the intervening n - 1 {}/2 cells, but will
allocate the last before doing the tail call.]

[I think that structure reuse may do much of what I'm asking
for here, but I'd like to hear from Peter and Nancy on that
one.]

The transformation is straightforward and extends to cover
cases where we have multiple possible constructors.  What we
end up with is one `wrapper' function that has the same
interface as the original which calls one or more
`expanded' versions (one for each constructor) which, in turn,
call each other whenever possible.

[In the example, fib_2 becomes the wrapper function and
fib_2a the expanded function.]

Where it is not possible/cheap enough to prove that a fast-path
call can be made (e.g. the new structured object is computed by
some `huge' or opaque computation) then a call is simply made
to the wrapper instead.

A structured argument to a function is expandable if it appears
in a recursive call (or if a call to another expanded function
is possible).  The question now becomes when and how far do we
expand these things?  It seems to me that a good first cut would
be to simply apply it to arguments that are always deconstructed.
That would cover a large number of the cases I can think of.

That said, it sounds like other people have thought harder about
this than I have and I'd very much like to hear their conclusions.

--
Ralph Becket      |      MSR Cambridge      |      rbeck at microsoft.com 
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------