[m-rev.] Improve scheduling for solver types

[Ralph Becket]

This change makes a huge improvement to the scheduling of solver type
goals.  I'm only presenting the interdiff change from the earlier diff.
If this is accepted then I will check in all the work on solver types so
far, bar that affecting name (de)mangling.

-- Ralph


Estimated hours taken: 24
Branches: main

Improve the scheduling of solver type goals by preferring deconstructions
over constructions followed by unifications.  This is arranged by allowing
solver type initialisation calls to be inserted only when all else fails.

XXX This implementation is O(n^2).  I will fix things if this becomes an
issue in practice.

compiler/modecheck_call.m:
compiler/modes.m:
compiler/mode_info.m:
	Added a new field to mode_info to indicate whether solver type
	initialisation calls can be inserted by modecheck_conj_list_2.

	Added modecheck_conj_list_3 which allows modecheck_conj_list_2
	to insert initialisation calls for a single goal, then repeats
	if this succeeded in scheduling some delayed goals.

diff -u compiler/modecheck_call.m compiler/modecheck_call.m
--- compiler/modecheck_call.m	2 Jul 2004 04:00:18 -0000
+++ compiler/modecheck_call.m	20 Aug 2004 06:54:35 -0000
@@ -450,7 +450,11 @@
 		mode_info_set_instmap(Instmap, !ModeInfo)
 	;
 		true
-	).
+	),
+		% We only allow one call at any given time to be made
+		% schedulable by inserting initialisation calls.
+		%
+	mode_info_set_may_initialise_solver_vars(no, !ModeInfo).
 
 :- pred insert_new_mode(pred_id::in, list(prog_var)::in,
 	maybe(determinism)::in, proc_id::out,
diff -u compiler/modes.m compiler/modes.m
--- compiler/modes.m	19 Aug 2004 00:15:49 -0000
+++ compiler/modes.m	31 Aug 2004 03:54:58 -0000
@@ -1467,23 +1467,43 @@
 	mode_info_get_errors(!.ModeInfo, OldErrors),
 	mode_info_set_errors([], !ModeInfo),
 
+	mode_info_get_delay_info(!.ModeInfo, DelayInfo0),
+	delay_info__enter_conj(DelayInfo0, DelayInfo1),
+	mode_info_set_delay_info(DelayInfo1, !ModeInfo),
+
 	mode_info_get_live_vars(!.ModeInfo, LiveVars1),
-	mode_info_get_delay_info(!.ModeInfo, DelayInfo1),
-	delay_info__enter_conj(DelayInfo1, DelayInfo2),
-	mode_info_set_delay_info(DelayInfo2, !ModeInfo),
 	mode_info_add_goals_live_vars(Goals0, !ModeInfo),
 
-	modecheck_conj_list_2(Goals0, Goals, [], RevImpurityErrors,
-		!ModeInfo, !IO),
+		% Schedule goals without inserting any solver initialisation
+		% calls (the flag `may_initialise_solver_vars' is initialised
+		% to `no' by mode_info_init and reset to `no' after a
+		% call has been scheduled using initialisation and after
+		% modecheck_conj_list_3).
+		%
+		% We ignore any impurity errors generated here by delaying
+		% impure goals since these problems might be resolved in
+		% modecheck_conj_list_3 by inserting solver type
+		% initialisation calls.
+		%
+	modecheck_conj_list_2(Goals0, Goals1,
+		[], _PrematureRevImpurityErrors, !ModeInfo, !IO),
+
+		% Try to handle any unscheduled goals by inserting solver
+		% initialisation calls.  We do things this way because we
+		% prefer deconstruction over construct-and-unify.
+		%
+	mode_info_get_delay_info(!.ModeInfo, DelayInfo2),
+	delay_info__leave_conj(DelayInfo2, DelayedGoals0, DelayInfo3),
+	mode_info_set_delay_info(DelayInfo3, !ModeInfo),
+	modecheck_conj_list_3(DelayedGoals0, DelayedGoals, Goals2,
+		[], RevImpurityErrors, !ModeInfo, !IO),
+
+	Goals = Goals1 ++ Goals2,
 
 	mode_info_get_errors(!.ModeInfo, NewErrors),
 	list__append(OldErrors, NewErrors, Errors),
 	mode_info_set_errors(Errors, !ModeInfo),
 
-	mode_info_get_delay_info(!.ModeInfo, DelayInfo4),
-	delay_info__leave_conj(DelayInfo4, DelayedGoals, DelayInfo5),
-	mode_info_set_delay_info(DelayInfo5, !ModeInfo),
-
 	( DelayedGoals \= [] ->
 		% the variables in the delayed goals should not longer
 		% be considered live (the conjunction itself will
@@ -1629,6 +1649,68 @@
 		Goals = Goals2
 	).
 
+:- pred modecheck_conj_list_3(list(delayed_goal)::in, list(delayed_goal)::out,
+	list(hlds_goal)::out, impurity_errors::in, impurity_errors::out,
+	mode_info::in, mode_info::out, io::di, io::uo) is det.
+
+modecheck_conj_list_3(DelayedGoals0, DelayedGoals, Goals,
+		!ImpurityErrors, !ModeInfo, !IO) :-
+	(
+			% There are no unscheduled goals, so we don't
+			% need to do anything.
+			%
+		DelayedGoals0 = [],
+		DelayedGoals  = [],
+		Goals = []
+	;
+			% There are some unscheduled goals.  See if
+			% allowing extra initialisation calls (for
+			% a single goal) makes a difference.
+			%
+		DelayedGoals0 = [_ | _],
+
+		Goals0 = map(hlds_goal_from_delayed_goal, DelayedGoals0),
+
+		mode_info_get_delay_info(!.ModeInfo, DelayInfo0),
+		delay_info__enter_conj(DelayInfo0, DelayInfo1),
+		mode_info_set_delay_info(DelayInfo1, !ModeInfo),
+
+		mode_info_set_may_initialise_solver_vars(yes, !ModeInfo),
+		modecheck_conj_list_2(Goals0, Goals1,
+			!ImpurityErrors, !ModeInfo, !IO),
+		mode_info_set_may_initialise_solver_vars(no, !ModeInfo),
+
+		mode_info_get_delay_info(!.ModeInfo, DelayInfo2),
+		delay_info__leave_conj(DelayInfo2, DelayedGoals1, DelayInfo3),
+		mode_info_set_delay_info(DelayInfo3, !ModeInfo),
+
+			% See if we scheduled any goals.
+			%
+		(
+			length(DelayedGoals1) < length(DelayedGoals0)
+		->
+				% We scheduled some goals.  Keep going
+				% until we flounder or succeed.
+				%
+			modecheck_conj_list_3(DelayedGoals1, DelayedGoals,
+				Goals2, !ImpurityErrors, !ModeInfo, !IO),
+			Goals = Goals1 ++ Goals2
+		;
+				% We've floundered; there's nothing
+				% more we can do.
+				%
+			DelayedGoals = DelayedGoals1,
+			Goals = Goals1
+		)
+	).
+
+
+:- func hlds_goal_from_delayed_goal(delayed_goal) = hlds_goal.
+
+hlds_goal_from_delayed_goal(delayed_goal(_WaitingVars, _ModeError, Goal)) =
+	Goal.
+
+
 %  check whether there are any delayed goals (other than headvar unifications)
 %  at the point where we are about to schedule an impure goal.  If so, that is
 %  an error.  Headvar unifications are allowed to be delayed because in the
@@ -2129,16 +2211,17 @@
 			UnifyContext),
 		CallUnifyContext = yes(call_unify_context(Var, var(Var),
 						UnifyContext)),
-		(
-			type_util__type_is_solver_type(ModuleInfo0, VarType)
-		->
-			% Create code to initialize the variable to
-			% inst `any', by calling the solver type's
-			% initialisation predicate.
-			insert_extra_initialisation_call(ModuleInfo0, Var,
-				VarType, InitialInst, Context,
-				CallUnifyContext, !ExtraGoals)
-		;
+ 		(
+			mode_info_may_initialise_solver_vars(!.ModeInfo),
+ 			type_util__type_is_solver_type(ModuleInfo0, VarType)
+ 		->
+ 			% Create code to initialize the variable to
+ 			% inst `any', by calling the solver type's
+ 			% initialisation predicate.
+ 			insert_extra_initialisation_call(ModuleInfo0, Var,
+ 				VarType, InitialInst, Context,
+ 				CallUnifyContext, !ExtraGoals)
+ 		;
 			% If the type is a type variable,
 			% or isn't a solver type then give up.
 			set__singleton_set(WaitingVars, Var0),
@@ -2146,7 +2229,7 @@
 				mode_error_implied_mode(Var0, VarInst0,
 					InitialInst),
 				!ModeInfo)
-		)
+ 		)
 	;
 		inst_is_bound(ModuleInfo0, InitialInst)
 	->
only in patch2:
--- compiler/mode_info.m	14 Jun 2004 04:16:21 -0000	1.65
+++ compiler/mode_info.m	20 Aug 2004 07:37:24 -0000
@@ -216,6 +216,18 @@
 	mode_info::in, mode_info::out) is det.
 
 %-----------------------------------------------------------------------------%
+
+	% The mode_info contains a flag indicating whether initialisation
+	% calls, converting a solver variable from `free' to `any', may be
+	% inserted during mode analysis.
+
+:- pred mode_info_may_initialise_solver_vars(mode_info::in)
+		is semidet.
+
+:- pred mode_info_set_may_initialise_solver_vars(bool::in,
+		mode_info::in, mode_info::out) is det.
+
+%-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
 :- implementation.
@@ -318,7 +330,7 @@
 				% to change which procedure
 				% is called?
 
-		checking_extra_goals :: bool
+		checking_extra_goals :: bool,
 				% Are we rechecking a goal after
 				% introducing unifications for
 				% complicated sub-unifications
@@ -326,6 +338,12 @@
 				% If so, redoing the mode check
 				% should not introduce more
 				% extra unifications.
+
+		may_initialise_solver_vars :: bool
+				% `yes' if calls to the initialisation
+				% predicates for solver vars can be
+				% inserted during mode analysis in order
+				% to make goals schedulable.
 	).
 
 %-----------------------------------------------------------------------------%
@@ -352,11 +370,13 @@
 
 	Changed = no,
 	CheckingExtraGoals = no,
+	MayInitSolverVars = no,
 
 	ModeInfo = mode_info(ModuleInfo, PredId, ProcId, VarSet, VarTypes,
 		Context, ModeContext, InstMapping0, LockedVars, DelayInfo,
 		ErrorList, LiveVarsList, NondetLiveVarsList, InstVarSet,
-		[], [], Changed, HowToCheck, MayChangeProc, CheckingExtraGoals
+		[], [], Changed, HowToCheck, MayChangeProc,
+		CheckingExtraGoals, MayInitSolverVars
 	).
 
 %-----------------------------------------------------------------------------%
@@ -622,4 +642,13 @@
         list__append(Errors0, [ModeErrorInfo], Errors),
         mode_info_set_errors(Errors, !ModeInfo).
 
+%-----------------------------------------------------------------------------%
+
+mode_info_may_initialise_solver_vars(ModeInfo) :-
+	ModeInfo ^ may_initialise_solver_vars = yes.
+
+mode_info_set_may_initialise_solver_vars(MayInit, !ModeInfo) :-
+	!:ModeInfo = !.ModeInfo ^ may_initialise_solver_vars := MayInit.
+
+%-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------