[m-dev.] for review: accumulator introduction

[Simon Taylor]

> Add a new pass to the compiler, that attempts to introduce accumulators
> into a procedure so as to make that procedure tail recursive.
 
A test case or two in tests/general would be nice.

> Index: compiler/accumulator.m
> ===================================================================

> +	% Given a dynamic variable, from which dynamic variable was it
> +	% descended (ie which variable in Y0s).
> +:- type orig_dynvar_map == map(prog_var, prog_var).

What does it mean for a variable to be descended from another?

I think you need to explain here what is important about the distinction
between static and dynamic variables.

> +%-----------------------------------------------------------------------------%
> +
> +	%
> +	% This predicate is meant to take the original goal and
> +	% rearrange it into a standard form that can be used in the rest
> +	% of module.
> +	%
> +:- pred accumulator__rearrange_goal(pred_id::in, proc_id::in,
> +		hlds_goal::in, instmap::in, module_info::in,
> +		top_level::out, base_goal::out, rec_goal::out) is semidet.
> +
> +accumulator__rearrange_goal(PredId, ProcId, Goal, InitialInstMap, ModuleInfo,
> +		Type, Base, Rec) :-
> +	(
> +		Goal = switch(_Var, _CanFail, Cases, _StoreMap) - _GoalInfo,
> +		Cases = [case(_IdA, GoalA), case(_IdB, GoalB)],
> +		goal_to_conj_list(GoalA, GoalAList),
> +		goal_to_conj_list(GoalB, GoalBList)
> +	->
> +		(
> +			accumulator__split_recursive_case(PredId, ProcId,
> +					InitialInstMap, ModuleInfo,
> +					GoalAList, Rec0)
> +		->
> +			Type = switch_rec_base,
> +			Base = base(GoalBList),
> +			Rec = Rec0
> +		;
> +			accumulator__split_recursive_case(PredId, ProcId,
> +					InitialInstMap, ModuleInfo,
> +					GoalBList, Rec0)
> +		->
> +			Type = switch_base_rec,
> +			Base = base(GoalAList),
> +			Rec = Rec0
> +		;
> +			fail
> +		)
> +	;
> +		fail
> +	).

Do you need to check that the goal identified as the base case
by this predicate does not contain a recursive call?

> +
> +	%
> +	% accumulator__split_recursive_case(Gs, DP, P, C)
> +	%
> +	% Split the goals, Gs, which make up the recursive case into the
> +	% decompose and process list of goals, DP, and the compose
> +	% goals, C, and the recursive goal P.
> +	%
> +:- pred accumulator__split_recursive_case(pred_id::in, proc_id::in,
> +		instmap::in, module_info::in,
> +		hlds_goals::in, rec_goal::out) is semidet.
> +
> +accumulator__split_recursive_case(PredId, ProcId,
> +		InitialInstMap, ModuleInfo, Goals, RecGoal) :-

The argument list in the comment looks a bit out of date.

> +:- pred accumulator__split_goals(hlds_goals::in, pred_id::in, proc_id::in,
> +		split_result::out) is nondet.
> +
> +accumulator__split_goals(Goals, PredId, ProcId, RecGoal) :-
> +	list__append(DecomposeProcess, [RecursiveCall | Compose], Goals),
> +	RecursiveCall = call(PredId, ProcId, _, _, _, _) - _,
> +
> +		% An empty compose means the predicate is already tail
> +		% recursive.
> +	Compose \= [],
> +	RecGoal = recursive(DecomposeProcess, RecursiveCall, Compose).

Does it make sense to do the transformation if the conjunction
contains a disjunction containing a recursive call?

> +	%
> +	% Given a list of goals and an instmap before the list of goals,
> +	% work out what the instmap at the end of the goals is.
> +	%
> +:- pred calculate_instmap(hlds_goals::in, instmap::in, instmap::out) is det.
> +
> +calculate_instmap(Goals, InstMap0, InstMap) :-
> +	GetGoalInfos = (pred(Goal::in, GoalInfo::out) is det :-
> +			Goal = _ - GoalInfo),
> +	list__map(GetGoalInfos, Goals, GoalInfos),
> +	list__map(goal_info_get_instmap_delta, GoalInfos, InstMapDeltas),
> +	ApplyInstMapDelta = (pred(Delta::in, Map0::in, Map::out) is det :-
> +			instmap__apply_instmap_delta(Map0, Delta, Map)),
> +	list__foldl(ApplyInstMapDelta, InstMapDeltas, InstMap0, InstMap).

You could do this as:
	goal_list_instmap_delta(Goals, InstMapDelta),
	instmap__apply_instmap_delta(InstMap0, InstMapDelta, InstMap).

> +	%
> +	% wrapper to test my code.
> +	%
> +:- pred checked_goal_depends_on_earlier_goal(hlds_goal::in,
> +		hlds_goal::in, instmap::in, module_info::in) is semidet.

The name of this predicate is a little ambiguous (does `checked' apply
to the goal or to `goal_depends_on_earlier_goal').
Maybe `goal_depends_on_earlier_goal_with_error_check'.

> +	%
> +	% If the earlier goal changes the instatiatedness of a variable
> +	% that is used in the later goal, then the later goal depends on
> +	% the earlier goal.
> +	%
> +	% This code doesn't work on the alias branch.
> +	%
> +:- pred goal_depends_on_earlier_goal(hlds_goal::in, hlds_goal::in) is semidet.

> +	%
> +	% If the earlier goal changes the instatiatedness of a variable
> +	% that is used in the later goal, then the later goal depends on
> +	% the earlier goal.
> +	%
> +	% This code does work on the alias branch.
> +	%
> +:- pred goal_depends_on_earlier_goal_2(hlds_goal::in,
> +		hlds_goal::in, instmap::in, module_info::in) is semidet.

pd_util__can_reorder_goals does something similar to this.
Could you use that instead? Do you need to check whether the
termination behaviour of the goal can change if reordering is done?

> +	%
> +	% accumulator__vars_to_accumulate(HV, C, VA)
> +	%
> +	% Given the list of goals, C, which represent the compose
> +	% goal and the list of the head variables, HV, determine the
> +	% head variables that will need to be accumulated, VA.
> +	%
> +	% The variables that will need to be accumulated are simply
> +	% those which instantiatedness change in the compose goals and
> +	% that are headvars.

Grammar - "those which instantiatedeness change"

> +	%
> +:- pred accumulator__vars_to_accumulate(prog_vars::in, a_goals::in,
> +		module_info::in, prog_vars::out) is det.
> +
> +accumulator__vars_to_accumulate(HeadVars, C, ModuleInfo, VarsToAccumulate) :-
> +	C = goal(ComposeGoals, InstMapBeforeCompose),
> +		
> +		% Determine the instmap-delta of the goal list.
> +	GetGoalInfos = (pred(Goal::in, GoalInfo::out) is det :-
> +				Goal = _ - GoalInfo),
> +	list__map(GetGoalInfos, ComposeGoals, GoalInfos),
> +	list__map(goal_info_get_instmap_delta, GoalInfos, InstMapDeltas),
> +	instmap_delta_init_reachable(EmptyInstMapDelta),
> +	list__foldl(instmap_delta_apply_instmap_delta,
> +			InstMapDeltas, EmptyInstMapDelta, InstMapDelta),

Use `goal_list_instmap_delta(ComposeGoals, InstMapDelta)'.

 +	%
> +	% accumulator__extra_vars_for_recursive_call(DP, C, Hs)
> +	%
> +	% If the decompose/process list of goals, DP, produce a value
> +	% that is needed in the compose list of goals, C, then that
> +	% value will need to be passed via the introduced recursive
> +	% call.  This predicate identifies these variables, Hs.
> +	%
> +:- pred accumulator__extra_vars_for_recursive_call(a_goals::in,
> +		a_goals::in, prog_vars::out) is det.
> +
> +accumulator__extra_vars_for_recursive_call(
> +		goal(DecomposeProcess, _InstMapBeforeDecomposeProcess),
> +		goal(Compose, _InstMapBeforeCompose), Vars) :-
> +	GetGoalInfos = (pred(Goal::in, GoalInfo::out) is det :-
> +				Goal = _ - GoalInfo),
> +	list__map(GetGoalInfos, DecomposeProcess, DPGoalInfos),
> +	list__map(goal_info_get_nonlocals, DPGoalInfos, DPNonLocals),
> +	set__list_to_set(DPNonLocals, DPNonLocalsPowerSet),
> +	set__power_union(DPNonLocalsPowerSet, DPNonLocalsSet),

This can be done as `goal_list_nonlocals(DecomposeProcess, DPNonLocalsSet)'.

> +
> +	list__map(GetGoalInfos, Compose, CGoalInfos),
> +	list__map(goal_info_get_nonlocals, CGoalInfos, CNonLocals),
> +	set__list_to_set(CNonLocals, CNonLocalsPowerSet),
> +	set__power_union(CNonLocalsPowerSet, CNonLocalsSet),

Ditto.

> +%-----------------------------------------------------------------------------%
> +
> +	%
> +	% accumulator__static_vars_in_recursive_call
> +	%
> +	% Identify the variables which are static only appear in the
> +	% recursive call.

Word missing.

> +	%
> +	% This predicate is currently unused.
> +	%
> +:- pred accumulator__static_vars_in_recursive_call(a_goal::in,
> +		a_goals::in, module_info::in, prog_vars::out) is det.
> +
> +accumulator__static_vars_in_recursive_call(Recursive, Compose,
> +		ModuleInfo, Vars) :-
> +
> +	Recursive = goal(_RecGoalExpr - RecGoalInfo, InstMapBeforeRec),
> +	Compose = goal(ComposeGoals, _InstMapBeforeCompose),
> +
> +	goal_info_get_instmap_delta(RecGoalInfo, RecInstMapDelta),
> +	goal_info_get_nonlocals(RecGoalInfo, RecNonLocals),
> +	instmap__apply_instmap_delta(InstMapBeforeRec, RecInstMapDelta,
> +			InstMapAfterRec),
> +	changed_vars(InstMapBeforeRec, InstMapAfterRec,
> +			ModuleInfo, ChangedVars),
> +
> +	set__difference(RecNonLocals, ChangedVars, PossibleStaticVars),
> +
> +	GetGoalInfos = (pred(Goal::in, GoalInfo::out) is det :-
> +				Goal = _ - GoalInfo),
> +	list__map(GetGoalInfos, ComposeGoals, CGoalInfos),
> +	list__map(goal_info_get_nonlocals, CGoalInfos, CNonLocals),
> +	set__list_to_set(CNonLocals, CNonLocalsPowerSet),
> +	set__power_union(CNonLocalsPowerSet, CNonLocalsSet),

goal_list_nonlocals.

> +	%
> +	% accumulator__orig_base_case
> +	%
> +	% Determine the base case of the original goal.
> +	%
> +:- pred accumulator__orig_base_case(hlds_goals::in, hlds_goal::out) is det.
> +
> +accumulator__orig_base_case(BaseGoalList, BaseGoal) :-
> +	calculate_goal_info(conj(BaseGoalList), BaseGoal).


Will the computed goal_info be any different to that from the original
goal? If not, it would be clearer to just use the old one.

> +
> +%-----------------------------------------------------------------------------%
> +
> +	%
> +	% accumulator__orig_recursive_case
> +	%
> +	% Determine the recursive case of the original goal.
> +	%

This might be clearer as:
	% Work out a new recursive case for the original predicate
	% which replaces the recursive call with a call to the new
	% predicate.

> +accumulator__new_recursive_case(DP, C, R0, DoLCO,
> +		ModuleInfo, PredId, ProcId, Name, Hs, HeadVars,
> +		Y0stoYs_Subst, HstoAs_Subst, Goal) :-
> +	DP = goal(DecomposeProcess, _InstMapBeforeDecomposeProcess),
> +	C  = goal(Compose, InstMapBeforeCompose),
> +	R0 = goal(Recursive0, _InstMapBeforeRecursive0),
> +
> +	assoc_info_init(ModuleInfo, HeadVars, DP, C, R0,
> +		Y0stoYs_Subst, HstoAs_Subst, AssocInfo0),
> +        accumulator__check_assoc(Compose, InstMapBeforeCompose, ModuleInfo,
> +			PreRecGoal0, PostRecGoal0, AssocInfo0, AssocInfo),

Replace the spaces with a tab.

> +	%
> +	% accumulator__check_post_rec_goals
> +	%
> +	% Ensure that each goal which is to be placed after the
> +	% recursive goal is construction unification.

is _a_ construction unification


> +:- pred calculate_goal_info(hlds_goal_expr::in, hlds_goal::out) is det.
> +
> +calculate_goal_info(GoalExpr, GoalExpr - GoalInfo) :-
> +	(
> +		GoalExpr = conj(GoalList)
> +	->
> +		goal_list_nonlocals(GoalList, NonLocals),
> +		goal_list_instmap_delta(GoalList, InstMapDelta),
> +		goal_list_determinism(GoalList, Determinism),
> +
> +		goal_info_init(NonLocals, InstMapDelta, Determinism, GoalInfo)
> +	;
> +		error("calculate_goal_info: not a conj.")
> +	).


All the uses of this predicate pass in a conj(Goals).
Would it be better just to pass in Goals, and avoid the error check.
This should probably go in hlds_goal.m.

> +/*
> +	XXX this no longer works.  We need to go back to my original code for
> +	this to work.
> +assoc_fact(unqualified("set"), "insert", 3, [TypeInfoIn, In, In, Out], 
> +		Moduleinfo, [TypeInfo, A, B, C], 
> +		[TypeInfo, A, B, C], PossibleStaticVars, no) :-

The comment should include some explanation of what the original code did,
and why it doesn't work now.

> +
> +	% 
> +	% accumulator__obey_heuristic
> +	%
> +	% for calls which rearrange the order of variables ensure that
> +	% the call obeys the heuristic that the static variables are in 
> +	% certain positions.
> +	%
> +:- pred accumulator__obey_heuristic(pred_id::in, module_info::in,
> +		prog_vars::in, set(prog_var)::in) is semidet.

I think this needs more explanation. 

> Index: compiler/options.m
> ===================================================================
> @@ -942,6 +944,7 @@
> @@ -2009,6 +2012,9 @@
>  		"\t`--optimize-higher-order' and `--type-specialization'.",
>  		"\tGoal size is measured as the number of calls, unifications",
>  		"\tand branched goals.",
> +		"--introduce-accumulators",
> +		"\tAttempt to introduce accumulating variables into",
> +		"\tprocedures, so as to make the procedure tail recursive.",
>  		"--optimize-constructor-last-call",

"Attempt to make predicates tail recursive by transforming them
to use accumulator arguments."?

I'd like to see some test cases and a relative diff.

Thanks,
Simon.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------