[m-dev.] Deforestation question

[Fergus Henderson]

On 12-Feb-2001, Ralph Becket <rbeck at microsoft.com> wrote:
> Say I write something like
> 
> 	{X, Y} = list__foldl(func(A, {X, Y}) = {X + A, Y + A}, As, {X0, Y0})
> 
> and compile under -O6 (or whatever), can I expect the compiler to
> spot that it is unnecessary to create a new {}/2 cell on every
> iteration?

Well, that would certainly be a nice optimization for the compiler to
do, and with intermodule optimization and deforestation, we have
most of the machinery to do it.  But currently the compiler does
not do that optimization.  Nor does it do it if you replace the
pair type with

	:- type mypair ---> mypair(int, int).

However, it *does* do the optimization if you replace the
pair type with

	:- type mypair ---> mypair(int, int) ; other.

and add some bogus code for the `other' case!
The basic reason is that deforestation only occurs for types with more
than one constructor, where you have a switch statement.

Perhaps it would not be hard to change the deforestation heuristics
so that the deforestation pass will optimize cases like this...
Simon, what do you think?

%-----------------------------------------------------------------------------%

:- module x.

:- interface.
:- import_module io, list.

:- pred main(io__state, io__state).
:- mode main(di, uo) is det.

:- pred foo(list(int), int, int, int, int).
:- mode foo(in, in, in, out, out) is det.

:- implementation.
:- import_module int, integer, std_util.

main -->
	{ foo([1,2,3],10,20,X,Y) },
	print("X = "), print(X), nl,
	print("Y = "), print(Y), nl.

foo(As, X0, Y0, X1, Y1) :-
        {X1, Y1} = list__foldl(func(A, {X, Y}) = {X + A, Y + A}, As, {X0, Y0}).

%-----------------------------------------------------------------------------%

:- module y.

:- interface.
:- import_module io, list.

:- pred main(io__state, io__state).
:- mode main(di, uo) is det.

:- pred foo(list(int), int, int, int, int).
:- mode foo(in, in, in, out, out) is semidet.

:- implementation.
:- import_module int, integer, std_util.

main -->
	( { foo([1,2,3],10,20,X,Y) } ->
		print("X = "), print(X), nl,
		print("Y = "), print(Y), nl
	;
		[]
	).

:- type mypair ---> mypair(int, int) ; other.

foo(As, X0, Y0, X1, Y1) :-
        mypair(X1, Y1) = list__foldl((func(A, P) = R :-
			( P = mypair(X, Y), R = mypair(X + A, Y + A)
			; P = other, R = mypair(0, 0)
			)), As, mypair(X0, Y0)).

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------