[mercury-users] mmc --optimize-constructor-last-call

[Michael Day]

Okay, things start to get interesting if I combine the --structure-reuse 
and --optimize-constructor-last-call options. I start with this code, 
which is almost tail-recursive but not quite:

filter_neg([], []).
filter_neg([X|Xs], Ys) :-
     ( if X < 0 then
         Y = 0
     else
         Y = X
     ),
     filter_neg(Xs, Ys0),
     Ys = [Y|Ys0].

run Mercury with the following options:

  --grade=hlc.gc -O5 --structure-reuse --optimize-constructor-last-call

and get four procedures for the predicate:

  ctgc__pred__LCMCpr_filter_neg_1__0__0_2_p_0
  ctgc__pred__filter_neg__0__0_2_p_0
  LCMCpr_filter_neg_1_2_p_0
  filter_neg_2_p_0

It's duplicating ctgc and non-ctgc procedures again, even though based 
on their being only one mode for the predicate I can't see when you 
would want to call the non-ctgc one, which is the only one actually 
getting called by the test program.

Looking at the generated code, the ctgc combined with constructor last 
call optimisation seems to be getting closer to ideal:

void filter_neg(Word Xs, Word * Ys)
{
     if (Xs == 0)
     {
         *Ys = 0;
     }
     else
     {
         Integer X = (Integer) field(tag(1), Xs, 0);
         Word Xs0 = (Word) field(tag(1), Xs, 1);
         Integer Y;
         Word * AddrYs0;

         if (X < 0)
           Y = 0;
         else
           Y = X;

         *Ys = (Word) Xs;
         field(tag(1), *Ys, 0) = Y;
         field(tag(1), *Ys, 1) = AddrYs0;

         filter_neg_LCMC(Xs0, AddrYs0);
     }
}

void filter_neg_LCMC(Word Xs, Word * AddrOfPrevYs0)
{
     while (TRUE)
     {
         if (Xs == 0)
         {
             *AddrOfHeadVar__2_10 = 0;
             break;
         }
         else
         {
             Integer X = (Integer) field(tag(1), Xs, 0);
             Word Xs0 = (Word) field(tag(1), Xs, 1);
             Integer Y;
             Word * AddrYs0;

             if (X < 0)
               Y = 0;
             else
               Y = X;

             field(tag(1), Xs, 0) = Y;
             field(tag(1), Xs, 1) = AddrYs0;

             *AddrOfPrevYs0 = Xs;
             AddrOfPrevYs0 = AddrYs0;
             Xs = Xs0;
         }
     }
}

No allocations, and it's a tail-recursive loop. There are still some 
unnecessary copies, but it's looking pretty good.

However, I don't understand how the last call optimisation is works, in 
particular these three lines of filter_neg:

         Word * AddrYs0;

         field(tag(1), *Ys, 1) = AddrYs0;

         filter_neg_LCMC(Xs0, AddrYs0);

That would seem to be assigning an unset variable to the tail of the Ys 
cons cell, then passing in that random value to the loop procedure.

Shouldn't it be doing the assignment the other way around, passing in 
the address of the second field of Ys0, something like this:

         AddrYs0 = &(field(tag(1), *Ys, 1);

I really can't see how the current code could work, but since it's not 
being called in practice perhaps it doesn't matter (?) Oh hang on, this 
dodgy code is only generated for the ctgc versions of the procedure, the 
non-ctgc versions have the assignment the right way around.

So that's a bug report, these two optimisations do not appear to play 
nicely with each other in rotd-2008-01-30. I'll copy to mercury-bugs.

Cheers,

Michael

-- 
Print XML with Prince!
http://www.princexml.com
--------------------------------------------------------------------------
mercury-users mailing list
Post messages to:       mercury-users at csse.unimelb.edu.au
Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
Subscriptions:          mercury-users-request at csse.unimelb.edu.au
--------------------------------------------------------------------------