[m-users.] Stackoverflow from --intermodule-optimisation

[Paul Bone]

On Mon, Sep 23, 2013 at 02:44:56PM +0200, Ludovic Langevine wrote:
> Here is the method which seems to trigger the stack overflow in Hedwig.
> 
>  jmercury.hedwig__stages.map__ho20_2_f_in__list_0(Unknown Source)
> 

I can explain in more detail what's happening and why this has been affected
by --intermodule-optimisation.  I'm going to cross-post to the Mercury list
as this is probably generally relevant.

Firstly, I'll explain some background for the Mercury list.

Hedwig is an application we've developed at Mission Critical IT.  Lately
we've been using Mercury's Java backend, hence the name of the _java_
function above in the package jmercury (meaning that it's code generated by
mmc).  We've recently added --intermodule-optimisation to our MCFLAGS for
the whole ODASE platform which provides a significant performance boost.
However several tools including hedwig have been running out of stack space.
Which can be fixed by using --optimise-constructor-last-call, but we did not
previously need this setting.  To understand the cause we have to understand
--intermodule-optimisation.

What we wanted to know is why does --intermodule-optimisation seem to cause
our programs to run out of stack space when this should not normally be
affected, especially since we havn't changed any settings relevant to
--optimise-constructor-last-call.  This behaviour breaks the principal of
least surprise
(See: http://en.wikipedia.org/wiki/Principle_of_least_astonishment), I'm
CC'ing the Mercury community because of this, there may be a technical
solution but not an easy one.

Intermodule optimisation does two things. 1) it builds .opt files for every
.m file it compiles.  These .opt files contain definitions that are not part
of the module's interface, they're usually definitions of some of the
predicates that are exported in the interface.  For example, when list.m
from the standard library is compiled with --intermodule-optimisation it
writes out a list.opt file which contains the definition of the predicate
map/3.

The second thing --intermodule-optimisation does is read in .opt
files from modules imported by the current module, for example if you're
compiling hedwig.stages which imports list, then list.opt is read, including
the definition of map/3.  The compiler, at certain optimisation levels,
performs higher order specialisation and inlining.  Which is why the Java
function in our example's name "map__ho20_2_f_in__list_0" contains the
string "ho20".  Somewhere in hedwig.stages map/3 is called and the compiler
has access to the definition of map/3 and its higher order argument, so it
generates a new predicate similar to map, but with the definition of the
higher order argument inlined within it.  This predicate has the same
structure as map, but the higher order call has been optimised away (which
is why this is a powerful optimisation for us on the Java backend).

list.m

    map(_ [], [])
    map(P, [X | Xs], [Y | Ys]) :-
        P(X, Y),
        map(P, Xs, Ys).

hedwig.stages.m

        map(ho_arg, Input, Output)

hedwig.stages.m after intermodule and higher order specialisation
optimisations

        map_ho20(Input, Output)

    map_ho20([], []).
    map_ho20([X | Xs], [Y | Ys]) :-
        ho_arg(X, Y),           % inlining not shown, it's optional anyway
        map_ho20(Xs, Ys).

The higher order call is replaced with a direct call, which may be further
inlined.

If hedwig.stages is built without --optimise-constructor-last-call then
map_ho20 will not be tail recursive (the construction of [Y | Ys] occurs
after the recursive call).  This can happen even when list.m in the Mercury
standard library is built with --optimise-constructor-last-call during
Mercury's installation (I don't know if this is actually the case).

So in this case, by performing intermodule optimisation, we've prevented the
standard library's compilation options form affecting the compilation of a
predicate whose definition comes from the standard library.



-- 
Paul Bone
Mission Critical