[m-dev.] Deforestation question

[Peter Ross]

On Tue, Feb 13, 2001 at 09:34:29AM -0800, Ralph Becket wrote:
> >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.]
> 
Yes, structure reuse would detect that the {}/2 cell was never used
after the deconstruction (locally).  So it is a canditate for reuse and
a reuse version of the function would be generated.

However it may be used globally.

    C = {1, 0}
    X = fib_2(5, C},
    process(C)

The call to process(C) requires that C still be live after the call to
fib_2 so we couldn't call the reuse version of fib_2.

This suggests that one optimization that could be done for structure
reuse is trying to determine when it is worthwhile to make a copy of a
data structure (ie C) so that the copy can be reused.  Just needs a good
heuristic!

> 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.
> 
Yes the recursive call heuristic would be a good one for determining
whether or not to make a copy of some argument so that it could be
reused.

Hmm need to think about it some more.

Pete
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------