for review: deforestation [2/4]

[Fergus Henderson]

On 19-Feb-1998, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> 
> +	% XXX Since this is now called from several places, rework this
> +	% interface to avoid the booleans.
>  :- type simplify
>  	---> 	simplify(
>  			bool,	% --warn-simple-code
>  			bool,	% --warn-duplicate-calls
>  			bool,	% run things that should be done once only
> -			bool,	% attempt to merge adjacent switches 
>  			bool,	% common subexpression elimination
>  			bool,	% remove excess assignment unifications
>  			bool,	% optimize duplicate calls
> -			bool	% partially evaluate calls
> +			bool,	% partially evaluate calls
> +			bool	% do common structure elimination even
> +				% when it might increase stack usage (used
> +				% by deforestation).
>  		).	

I don't quite understand the XXX comment.
Could you elaborate and/or rephrase it?

> +	( Common = yes ->
> +		% On the first pass do common structure elimination and
> +		% branch merging.
> +		simplify_info_set_simplify(Info0,
> +			simplify(Warn, WarnCalls, no, Common, no, 
> +				Calls, Prop, MoreCommon), 
> +			Info1),
> +		
> +		simplify__do_process_goal(Goal0, Goal1, Info1, Info2),
> +
> +		simplify_info_reinit(
> +			simplify(no, no, Once, no, Excess, no, Prop, no),
> +			InstMap0, Info2, Info3)

Hmm, maybe I understand the XXX comment now ;-)

I think it would be a good idea to use variables to name the arguments here,
e.g.

		WarnSimple = no,
		WarnDuplicate = no,
		simplify_info_reinit(
			simplify(WarnSimple, WarnDumplicate, Once, ...

> +simplify__disj([], RevGoals, Goals, InstMaps, InstMaps, _, Info, Info) :-
> +	list__reverse(RevGoals, Goals).
> +simplify__disj([Goal0 | Goals0], RevGoals0, Goals,  PostBranchInstMaps0,
>  		PostBranchInstMaps, Info0, Info1, Info) :-
>  	simplify__goal(Goal0, Goal, Info1, Info2),
> -	simplify_info_post_branch_update(Info0, Info2, Info3),
> -	Goal0 = _ - GoalInfo,
> -	goal_info_get_instmap_delta(GoalInfo, InstMapDelta),
> -	simplify__disj(Goals0, Goals, [InstMapDelta | PostBranchInstMaps0],
> -			PostBranchInstMaps, Info0, Info3, Info4),
> +	Goal = _ - GoalInfo,
> +
>  	(
> -		simplify_do_warn(Info4),
> -		Goal = _ - GoalInfo,
> -		% don't warn about impure disjuncts that can't succeed
> +		% Don't prune or warn about impure disjuncts 
> +		% that can't succeed.
>  		\+ goal_info_is_impure(GoalInfo),
>  		goal_info_get_determinism(GoalInfo, Detism),
> -		determinism_components(Detism, _, MaxSolns),
> +		determinism_components(Detism, CanFail, MaxSolns),
>  		MaxSolns = at_most_zero
>  	->
> -		goal_info_get_context(GoalInfo, Context),
> -		simplify_info_add_msg(Info4, zero_soln_disjunct(Context),
> -			Info)
> +		( 
> +			simplify_do_warn(Info2),
> +			% Don't warn where the initial goal was fail,
> +			% since that can result from mode analysis
> +			% pruning away cases in a switch which cannot
> +			% succeed due to sub-typing in the modes.
> +			Goal0 \= disj([], _) - _
> +		->
> +			goal_info_get_context(GoalInfo, Context),
> +			simplify_info_add_msg(Info2, 
> +				zero_soln_disjunct(Context), Info3)
> +		;
> +			Info3 = Info2
> +		),
> +
> +		%
> +		% Prune away non-succeeding disjuncts where possible.
> +		%
> +
> +		( 
> +			( 
> +				CanFail = can_fail
> +			;	
> +				% Only remove erroneous disjuncts
> +				% if --no-fully-strict.
> +				CanFail = cannot_fail,
> +				simplify_info_get_det_info(Info3, DetInfo),
> +				det_info_get_fully_strict(DetInfo, no)
> +			)

This test is wrong, I'm pretty sure.  It is not valid to prune away a
disjunct with determinism `failure' unless `--no-fully-strict' is set.

To abide by the language semantics, the code would have to be
something like

			( 
				WillFail = will_fail
			;	
				% Only remove disjuncts that might call
				% loop or call error/1 if --no-fully-strict.
				WillFail = might_not_fail,
				simplify_info_get_det_info(Info3, DetInfo),
				det_info_get_fully_strict(DetInfo, no)
			)

except that won't work because we don't have `WillFail' information here.

Actually on second thoughts I guess you do: if the goal starts with
`fail', then it will definitely fail.  So you can write it like this:

			( 
				Goal0 = disj([], _) - _
			;	
				% Only remove disjuncts that might call
				% loop or call error/1 if --no-fully-strict.
				simplify_info_get_det_info(Info3, DetInfo),
				det_info_get_fully_strict(DetInfo, no)
			)

> + at item --deforestation
> +Enable deforestation. The aim of deforestation is to avoid
> +the construction of intermediate data structures and to avoid
> +repeated traversals over data structures within a conjunction.

I suggest

   Enable deforestation.  Deforestation is a program transformation
   whose aim is to avoid ...

> +	% Given a varset and a set of variables, return another varset
> +	% containing only those variables.
> +:- pred varset__select(varset, set(var), varset).
> +:- mode varset__select(in, in, out) is det.

That's a user-visible change, so it should be mentioned in the NEWS file.

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