[m-dev.] deforestation optimization regression

[Fergus Henderson]

I just noticed that in 0.11 and the main branch, the deforestation
optimization is not working properly -- for the test case that I just
tried (see below), the Mercury compiler optimizes the two traversals into
a single traversal, avoiding the unnecessary traversal of the intermediate
data structure, but it fails to optimize away the *construction* of the
intermediate data structure.  This problem appears to be a regression in
Mercury release 0.11 -- it seems to work correctly in 0.10.

Simon, would you mind taking a look at this one?

	:- module t2l.
	:- interface.
	:- import_module list.

	:- type tree(T) --->  nil ; node(tree(T), T, tree(T)).

	:- func tree2list(tree(T)) = list(T).
	:- func list2tree(list(T)) = tree(T).
	:- func list2list(list(T)) = list(T).

	:- implementation.

	tree2list(nil) = [].
	tree2list(node(Left, A, Right)) =
		tree2list(Left) ++ [A] ++ tree2list(Right).

	list2tree([]) = nil.
	list2tree([X|Xs]) = node(nil, X, list2tree(Xs)).

	% Deforestation optimization ought to be able to optimize away
	% the intermediate tree here.
	list2list(L) = tree2list(list2tree(L)).

The final HLDS dump shows that list2list has been subject
to deforestation optimization, but the construction of the
tree node is still present:

	:- mode list2list((builtin.in), (builtin.in)) = (builtin.out) is det.
	t2l.list2list(TypeInfo_for_T, L) = HeadVar__2 :-
		t2l.'DeforestationIn__pred__list2list__16__0'(HeadVar__2,
			L, V_4, TypeInfo_for_T).
>--------------------------^^^
why is the extra output argument here?

		% pred id 1603
		% mode number 0 of predicate
		%	`t2l.DeforestationIn__pred__list2list__16__0/4' (det):
	:- mode 'DeforestationIn__pred__list2list__16__0'((free -> ground),
		(ground -> bound((list.[]) ; list.'[|]'(ground, ground))),
		(free -> unique((t2l.nil) ;
			t2l.node(unique((t2l.nil)), ground, ground))),
		(ground -> ground)).
	t2l.'DeforestationIn__pred__list2list__16__0'(HeadVar__2, L, V_4,
			TypeInfo_for_T) :-
		( % cannot_fail switch on `L'
			% L has functor list.[]/0
			V_4 = t2l.nil,
			HeadVar__2 = list.[]
		;
			% L has functor list.[|]/2
			L = list.[A | Xs],
			V_37 = list.[],
			V_35 = list.[A | V_37],
			t2l.'DeforestationIn__pred__list2list__16__0'(V_36,
				Xs, Right, TypeInfo_for_T),
why is this here?	V_70 = t2l.nil,
>------------------>	V_4 = t2l.node(V_70, A, Right),
			list.append(TypeInfo_for_T, V_35, V_36, V_34),
			V_71 = list.[],
			list.append(TypeInfo_for_T, V_71, V_34, HeadVar__2)
		).

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  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
--------------------------------------------------------------------------