diff: changes for function mode inference

Fergus Henderson fjh at cs.mu.oz.au
Tue Jul 8 16:10:23 AEST 1997


Hi,

Andrew, can you please review this change?

Estimated hours: 40

Two changes:
1. When flattening goals to superhomogeneous form, make sure that
   we order unifications bottom-up, rather than top-down.
2. Convert in-in unifications against variables whose
   top-level inst is known into deconstructions, so that they
   are candidates for switch detection.  (Necessary to prevent
   change #1 from breaking existing code.)

make_hlds.m:
	When flattening goals to superhomogeneous form, make sure that
	we order unifications bottom-up, rather than top-down.  This is
	necessary for several reasons:
	- The ordering affects the operational semantics,
	  if using the strict-sequential operational semantics.
	  The Semantics chapter of the Mercury Language
	  Reference Manual says that function calls are
	  executed "depth-first left-to-right", which (although
	  a bit unclear) is supposed to imply bottom-up
	  rather than top-down.
	- When doing mode inference for functions,
	  the bottom-up ordering is almost always right, and
	  the top-down ordering is almost always wrong.
	  Since mode inference doesn't do reordering,
	  it is important to pick the right ordering in the
	  first place.

modecheck_unify.m:
	For in-in unifications against variables whose top-level
	inst is known, split such unifications into deconstructions and
	argument unifications, so that the the deconstruction parts
	become candidates for switch detection.  This is necessary
	because otherwise the above ordering change would break deep
	indexing.  For example, code such as `p(f(a)).' becomes
	`p(H1) :- V1 = a, H1 = f(V1)', and then in `H1 = f(V1)', the
	argument unification against `V1' is a complicated sub-unify
	that will get split out as a complicated unify; the unification
	`V1 = a' becomes a construction, not a deconstruction, and so
	there would be no deconstruction for switch detection to find.

	(Note that the alternative of making switch detection also
	check for these sort of complicated unifies is unappealing,
	since it is easy enough for switch detection to hoist a
	deconstruction out, but it would be quite difficult for
	switch detection to hoist just the deconstruction part of
	a complicated unify out.)

modes.m:
	Change the representation of extra_goals from just a pair
	of lists of goals (goals to insert before & after the main
	goal, respectively) so that it includes an instmap, which
	is the instmap after the main goal.  This change is required
	because without it it was incorrectly computing the instmap
	delta for the main goal, if the after-goals list was non-empty.
	Also, delete the before-goals list, because it is not used
	and because getting the instmap deltas right for before-goals
	would be tricky.

unique_modes.m, modecheck_call.m:
	Very minor changes to use the new representation of extra_goals.


cvs diff: Diffing .
Index: make_hlds.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/make_hlds.m,v
retrieving revision 1.234
diff -u -r1.234 make_hlds.m
--- make_hlds.m	1997/06/29 23:10:57	1.234
+++ make_hlds.m	1997/07/04 14:08:20
@@ -2896,7 +2896,7 @@
 				MainContext, SubContext, Goal0) },
 			{ ArgContext = functor(ConsId,
 				MainContext, SubContext) },
-			append_arg_unifications(HeadVars, FunctorArgs,
+			insert_arg_unifications(HeadVars, FunctorArgs,
 				FunctorContext, ArgContext, Goal0,
 				VarSet1, Goal, VarSet, Info0, Info)
 		)
Index: modecheck_call.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/modecheck_call.m,v
retrieving revision 1.12
diff -u -r1.12 modecheck_call.m
--- modecheck_call.m	1997/07/02 08:04:08	1.12
+++ modecheck_call.m	1997/07/04 14:08:24
@@ -25,13 +25,13 @@
 :- import_module term.
 
 :- pred modecheck_call_pred(pred_id, list(var), proc_id, list(var),
-				pair(list(hlds_goal)), mode_info, mode_info).
+				extra_goals, mode_info, mode_info).
 :- mode modecheck_call_pred(in, in, out, out, out,
 				mode_info_di, mode_info_uo) is det.
 
 :- pred modecheck_higher_order_call(pred_or_func, var, list(var),
 				list(type), list(mode), determinism, list(var),
-				pair(list(hlds_goal)), mode_info, mode_info).
+				extra_goals, mode_info, mode_info).
 :- mode modecheck_higher_order_call(in, in, in, out, out, out, out, out,
 				mode_info_di, mode_info_uo) is det.
 
@@ -123,7 +123,7 @@
 		Modes = [],
 		Det = erroneous,
 		Args = Args0,
-		ExtraGoals = [] - []
+		ExtraGoals = no_extra_goals
 	).
 
 modecheck_call_pred(PredId, ArgVars0, TheProcId, ArgVars, ExtraGoals,
@@ -151,7 +151,7 @@
 			ModeInfo0, ModeInfo),
 		invalid_proc_id(TheProcId),
 		ArgVars = ArgVars0,
-		ExtraGoals = [] - []
+		ExtraGoals = no_extra_goals
 	;
 		ProcIds = [ProcId],
 		\+ list__member(request(infer_modes), Markers)
@@ -206,13 +206,13 @@
 	).
 
 :- pred modecheck_call_pred_2(list(proc_id), pred_id, proc_table, list(var),
-			set(var), proc_id, list(var), pair(list(hlds_goal)),
+			set(var), proc_id, list(var), extra_goals,
 			mode_info, mode_info).
 :- mode modecheck_call_pred_2(in, in, in, in, in, out, out, out,
 			mode_info_di, mode_info_uo) is det.
 
 modecheck_call_pred_2([], PredId, _Procs, ArgVars, WaitingVars,
-			TheProcId, ArgVars, [] - [], ModeInfo0, ModeInfo) :-
+		TheProcId, ArgVars, no_extra_goals, ModeInfo0, ModeInfo) :-
 	%
 	% There were no matching modes.
 	% If we're inferring modes for this called predicate, then
Index: modecheck_unify.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/modecheck_unify.m,v
retrieving revision 1.17
diff -u -r1.17 modecheck_unify.m
--- modecheck_unify.m	1997/07/02 08:06:17	1.17
+++ modecheck_unify.m	1997/07/08 04:15:36
@@ -31,11 +31,21 @@
 			mode_info_di, mode_info_uo) is det.
 
 	% Work out what kind of unification a var-var unification is.
+	% Also, split complicated unifies into deconstructions,
+	% if the top-level functor is known.
 :- pred categorize_unify_var_var(mode, mode, is_live, is_live, var, var,
 			determinism, unify_context, map(var, type), mode_info,
-			hlds_goal_expr, mode_info).
+			hlds_goal_expr, extra_goals, mode_info).
 :- mode categorize_unify_var_var(in, in, in, in, in, in, in, in, in,
-			mode_info_di, out, mode_info_uo) is det.
+			mode_info_di, out, out, mode_info_uo) is det.
+
+	% Given a unification goal, which must be something that can be
+	% returned from categorize_unify_var_var (i.e.  a unification
+	% of two vars, a unification of a var and a functor, or an
+	% empty conjunction), return a list of all the variables in the
+	% goal.
+:- pred unify_vars(hlds_goal_expr, list(var)).
+:- mode unify_vars(in, out) is det.
 
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
@@ -45,14 +55,15 @@
 :- import_module hlds_module, hlds_goal, hlds_pred, hlds_data, hlds_out.
 :- import_module mode_debug, mode_util, mode_info, modes, mode_errors.
 :- import_module inst_match, unify_proc, code_util, unique_modes.
-:- import_module typecheck, modecheck_call.
+:- import_module typecheck, modecheck_call, instmap.
+
 :- import_module bool, list, std_util, int, map, set, require, varset.
 :- import_module string, assoc_list.
 
 %-----------------------------------------------------------------------------%
 
-modecheck_unification(X, var(Y), _Unification0, UnifyContext, _GoalInfo, _,
-			Unify, ModeInfo0, ModeInfo) :-
+modecheck_unification(X, var(Y), _Unification0, UnifyContext, GoalInfo0, _,
+			Goal, ModeInfo0, ModeInfo) :-
 	mode_info_get_module_info(ModeInfo0, ModuleInfo0),
 	mode_info_get_instmap(ModeInfo0, InstMap0),
 	instmap__lookup_var(InstMap0, X, InstOfX),
@@ -71,13 +82,18 @@
 		Inst = UnifyInst,
 		Det = Det1,
 		mode_info_set_module_info(ModeInfo0, ModuleInfo1, ModeInfo1),
-		modecheck_set_var_inst(X, Inst, ModeInfo1, ModeInfo2),
-		modecheck_set_var_inst(Y, Inst, ModeInfo2, ModeInfo3),
 		ModeOfX = (InstOfX -> Inst),
 		ModeOfY = (InstOfY -> Inst),
-		mode_info_get_var_types(ModeInfo3, VarTypes),
+		mode_info_get_var_types(ModeInfo1, VarTypes),
 		categorize_unify_var_var(ModeOfX, ModeOfY, LiveX, LiveY, X, Y,
-			Det, UnifyContext, VarTypes, ModeInfo3, Unify, ModeInfo)
+			Det, UnifyContext, VarTypes, ModeInfo1,
+			Unify, ExtraGoals, ModeInfo2),
+		modecheck_set_var_inst(X, Inst, ModeInfo2, ModeInfo3),
+		modecheck_set_var_inst(Y, Inst, ModeInfo3, ModeInfo),
+		unify_vars(Unify, UnifyVars),
+		handle_extra_goals(Unify, ExtraGoals, GoalInfo0,
+					[X, Y], UnifyVars,
+					InstMap0, ModeInfo, Goal)
 	;
 		set__list_to_set([X, Y], WaitingVars),
 		mode_info_error(WaitingVars, mode_error_unify_var_var(X, Y,
@@ -95,7 +111,7 @@
 		ModeOfX = (InstOfX -> Inst),
 		ModeOfY = (InstOfY -> Inst),
 		Modes = ModeOfX - ModeOfY,
-		Unify = unify(X, var(Y), Modes, Unification, UnifyContext)
+		Goal = unify(X, var(Y), Modes, Unification, UnifyContext)
 	).
 
 modecheck_unification(X0, functor(ConsId0, ArgVars0), Unification0,
@@ -337,7 +353,7 @@
 			%
 			(
 				HowToCheckGoal = check_unique_modes,
-				ExtraGoals \= [] - []
+				ExtraGoals \= no_extra_goals
 			->
 				error("unique_modes.m: re-modecheck of unification encountered complicated sub-unifies")
 			;
@@ -488,7 +504,7 @@
 	).
 
 :- pred modecheck_unify_functor(var, (type), cons_id, list(var), unification,
-			pair(list(hlds_goal)), pair(mode), cons_id, list(var),
+			extra_goals, pair(mode), cons_id, list(var),
 			unification, mode_info, mode_info).
 :- mode modecheck_unify_functor(in, in, in, in, in, out, out, out, out, out,
 			mode_info_di, mode_info_uo) is det.
@@ -548,7 +564,7 @@
 			% return any old garbage
 		Unification = Unification0,
 		ArgVars = ArgVars0,
-		ExtraGoals = [] - []
+		ExtraGoals = no_extra_goals
 	;
 		abstractly_unify_inst_functor(LiveX, InstOfX, ConsId,
 			InstArgs, LiveArgs, real_unify, ModuleInfo0,
@@ -579,8 +595,8 @@
 				Unification0, ModeInfo1,
 				Unification1, ModeInfo2),
 		split_complicated_subunifies(Unification1, ArgVars0,
-					Unification, ArgVars, ExtraGoals,
-					ModeInfo2, ModeInfo3),
+				Unification, ArgVars, ExtraGoals,
+				ModeInfo2, ModeInfo3),
 		modecheck_set_var_inst(X, Inst, ModeInfo3, ModeInfo4),
 		( bind_args(Inst, ArgVars, ModeInfo4, ModeInfo5) ->
 			ModeInfo = ModeInfo5
@@ -612,7 +628,7 @@
 			% return any old garbage
 		Unification = Unification0,
 		ArgVars = ArgVars0,
-		ExtraGoals = [] - []
+		ExtraGoals = no_extra_goals
 	).
 
 %-----------------------------------------------------------------------------%
@@ -650,12 +666,12 @@
 	% into separate unifications by introducing fresh variables here.
 
 :- pred split_complicated_subunifies(unification, list(var),
-			unification, list(var), pair(list(hlds_goal)),
+			unification, list(var), extra_goals,
 			mode_info, mode_info).
 :- mode split_complicated_subunifies(in, in, out, out, out,
 			mode_info_di, mode_info_uo) is det.
 
-split_complicated_subunifies(Unification0, ArgVars0,
+split_complicated_subunifies(Unification0, ArgVars0, 
 				Unification, ArgVars, ExtraGoals) -->
 	(
 		{ Unification0 = deconstruct(X, ConsId, ArgVars0, ArgModes0,
@@ -675,16 +691,16 @@
 	;
 		{ Unification = Unification0 },
 		{ ArgVars = ArgVars0 },
-		{ ExtraGoals = [] - [] }
+		{ ExtraGoals = no_extra_goals }
 	).
 
 :- pred split_complicated_subunifies_2(list(var), list(uni_mode),
-			list(var), list(uni_mode), pair(list(hlds_goal)),
+			list(var), list(uni_mode), extra_goals,
 			mode_info, mode_info).
 :- mode split_complicated_subunifies_2(in, in, out, out, out,
-		mode_info_di, mode_info_uo) is semidet.
+			mode_info_di, mode_info_uo) is semidet.
 
-split_complicated_subunifies_2([], [], [], [], [] - []) --> [].
+split_complicated_subunifies_2([], [], [], [], no_extra_goals) --> [].
 split_complicated_subunifies_2([Var0 | Vars0], [UniMode0 | UniModes0],
 			Vars, UniModes, ExtraGoals, ModeInfo0, ModeInfo) :-
 	mode_info_get_module_info(ModeInfo0, ModuleInfo),
@@ -697,23 +713,22 @@
 		mode_to_arg_mode(ModuleInfo, ModeX, VarType, top_in),
 		mode_to_arg_mode(ModuleInfo, ModeY, VarType, top_in)
 	->
-		split_complicated_subunifies_2(Vars0, UniModes0,
-				Vars1, UniModes1, ExtraGoals0,
-				ModeInfo0, ModeInfo1),
-		ExtraGoals0 = BeforeGoals - AfterGoals0,
-
 		% introduce a new variable `Var'
-		mode_info_get_varset(ModeInfo1, VarSet1),
-		mode_info_get_var_types(ModeInfo1, VarTypes1),
-		varset__new_var(VarSet1, Var, VarSet),
-		map__set(VarTypes1, Var, VarType, VarTypes),
-		mode_info_set_varset(VarSet, ModeInfo1, ModeInfo2),
-		mode_info_set_var_types(VarTypes, ModeInfo2, ModeInfo3),
+		mode_info_get_varset(ModeInfo0, VarSet0),
+		mode_info_get_var_types(ModeInfo0, VarTypes0),
+		varset__new_var(VarSet0, Var, VarSet),
+		map__set(VarTypes0, Var, VarType, VarTypes),
+		mode_info_set_varset(VarSet, ModeInfo0, ModeInfo1),
+		mode_info_set_var_types(VarTypes, ModeInfo1, ModeInfo2),
 
 		% change the main unification to use `Var' instead of Var0
 		UniMode = (InitialInstX - free -> InitialInstX - InitialInstX),
-		UniModes = [UniMode | UniModes1],
-		Vars = [Var | Vars1],
+
+		% Compute the instmap that results after the main unification.
+		% We just need to set the inst of `Var'.
+		mode_info_get_instmap(ModeInfo2, OrigInstMap),
+		instmap__set(OrigInstMap, Var, InitialInstX, InstMapAfterMain),
+		mode_info_set_instmap(InstMapAfterMain, ModeInfo2, ModeInfo3),
 
 		% create code to do a unification between `Var' and `Var0'
 		ModeVar0 = (InitialInstY -> FinalInstY),
@@ -739,32 +754,52 @@
 						UnifyContext),
 		categorize_unify_var_var(ModeVar0, ModeVar,
 			live, dead, Var0, Var, Det, UnifyContext,
-			VarTypes, ModeInfo4, AfterGoal, ModeInfo),
+			VarTypes, ModeInfo4,
+			NewUnifyGoal, NewUnifyExtraGoals, ModeInfo5),
+		unify_vars(NewUnifyGoal, NewUnifyGoalVars),
 
 		% compute the goal_info nonlocal vars & instmap delta
 		% for the newly created goal
-		set__list_to_set([Var0, Var], NonLocals),
-		( InitialInstY = FinalInstY ->
-			InstMapAL0 = []
+		% N.B. This may overestimate the set of non-locals,
+		% but that shouldn't cause any problems.
+		set__list_to_set(NewUnifyGoalVars, NonLocals),
+		( NewUnifyExtraGoals = extra_goals(InstMapAfterNewUnify, _) ->
+			compute_instmap_delta(InstMapAfterMain,
+				InstMapAfterNewUnify, NonLocals, InstMapDelta)
 		;
-			InstMapAL0 = [Var0 - FinalInstY]
+			( InitialInstY = FinalInstY ->
+				InstMapDeltaAL0 = []
+			;
+				InstMapDeltaAL0 = [Var0 - FinalInstY]
+			),
+			InstMapDeltaAL = [Var - FinalInstX | InstMapDeltaAL0],
+			instmap_delta_from_assoc_list(InstMapDeltaAL,
+				InstMapDelta)
 		),
-		InstMapAL = [Var - FinalInstX | InstMapAL0],
-		instmap_delta_from_assoc_list(InstMapAL, InstMapDelta),
 		goal_info_init(GoalInfo0),
-		goal_info_set_nonlocals(GoalInfo0, NonLocals,
-			GoalInfo1),
+		goal_info_set_nonlocals(GoalInfo0, NonLocals, GoalInfo1),
 		goal_info_set_instmap_delta(GoalInfo1, InstMapDelta, GoalInfo),
 
-		% insert the unification between `Var' and `Var0' at
-		% the start of the AfterGoals
-		AfterGoals = [AfterGoal - GoalInfo | AfterGoals0],
-		ExtraGoals = BeforeGoals - AfterGoals
+		% insert the new unification at
+		% the start of the extra goals
+		NewUnifyExtraGoal = extra_goals(InstMapAfterMain,
+					[NewUnifyGoal - GoalInfo]),
+		append_extra_goals(NewUnifyExtraGoal, NewUnifyExtraGoals,
+			ExtraGoals0),
+
+		% recursive call to handle the remaining variables...
+		split_complicated_subunifies_2(Vars0, UniModes0,
+				Vars1, UniModes1, ExtraGoals1,
+				ModeInfo5, ModeInfo),
+		Vars = [Var | Vars1],
+		UniModes = [UniMode | UniModes1],
+		append_extra_goals(ExtraGoals0, ExtraGoals1, ExtraGoals)
 	;
-		Vars = [Var0 | Vars1],
-		UniModes = [UniMode0 | UniModes1],
 		split_complicated_subunifies_2(Vars0, UniModes0,
-			Vars1, UniModes1, ExtraGoals, ModeInfo0, ModeInfo)
+				Vars1, UniModes1, ExtraGoals,
+				ModeInfo0, ModeInfo),
+		Vars = [Var0 | Vars1],
+		UniModes = [UniMode0 | UniModes1]
 	).
 
 %-----------------------------------------------------------------------------%
@@ -772,19 +807,28 @@
 % categorize_unify_var_var works out which category a unification
 % between a variable and another variable expression is - whether it is
 % an assignment, a simple test or a complicated unify.
+% It also splits complicated unifies and simple tests
+% in the case where the top-level functor is bound to a known functor.
 
 categorize_unify_var_var(ModeOfX, ModeOfY, LiveX, LiveY, X, Y, Det,
-		UnifyContext, VarTypes, ModeInfo0, Unify, ModeInfo) :-
+		UnifyContext, VarTypes, ModeInfo0,
+		Unify, ExtraGoals, ModeInfo) :-
 	mode_info_get_module_info(ModeInfo0, ModuleInfo0),
 	(
 		mode_is_output(ModuleInfo0, ModeOfX)
 	->
 		Unification = assign(X, Y),
+		optimize_unify(Unification, X, Y, ModeOfX, ModeOfY,
+			Det, UnifyContext, ModeInfo0, Unify),
+		ExtraGoals = no_extra_goals,
 		ModeInfo = ModeInfo0
 	;
 		mode_is_output(ModuleInfo0, ModeOfY)
 	->
 		Unification = assign(Y, X),
+		optimize_unify(Unification, X, Y, ModeOfX, ModeOfY, Det,
+			UnifyContext, ModeInfo0, Unify),
+		ExtraGoals = no_extra_goals,
 		ModeInfo = ModeInfo0
 	;
 		mode_is_unused(ModuleInfo0, ModeOfX),
@@ -800,51 +844,82 @@
 		;
 			error("categorize_unify_var_var: free-free unify!")
 		),
+		optimize_unify(Unification, X, Y, ModeOfX, ModeOfY,
+			Det, UnifyContext, ModeInfo0, Unify),
+		ExtraGoals = no_extra_goals,
 		ModeInfo = ModeInfo0
 	;
+		%
+		% Check for in-in unifications that are unifying
+		% with a variable whose top-level functor is known.
+		% For such unifications, split out the functor check
+		% as a separate deconstruction unification, so that
+		% it will be a candidate for switch detection.
+		%
+		% For example, given X::ground and Y::bound(f(ground, ground)),
+		% we replace
+		%	X = Y		% complicated unification
+		% with
+		%	X = f(T1, T2), 	% can_fail deconstruction
+		%	Y = f(T1, T2)	% deconstruction, possibly with
+		%			% complicated argument sub-unifies
+		% where T1 and T2 are fresh variables.
+		%
+		% XXX due to the current lack of support for
+		% aliasing, this is done only if X is ground.
+		%
 		map__lookup(VarTypes, X, Type),
+		mode_get_insts(ModuleInfo0, ModeOfX, InitialInstX, _),
+		mode_get_insts(ModuleInfo0, ModeOfY, InitialInstY, _),
 		(
-			type_is_atomic(Type, ModuleInfo0)
+			% check for known functor on the right hand side
+			InitialInstY = bound(_Uniq,
+					[functor(ConsId, ArgInsts)]),
+			inst_is_ground(ModuleInfo0, InitialInstX) % see above
 		->
-			Unification = simple_test(X, Y),
-			ModeInfo = ModeInfo0
+			split_complicated_unify(X, Y, ConsId,
+				Type, ArgInsts, UnifyContext, ModeInfo0,
+				Unify, ExtraGoals, ModeInfo)
 		;
-			mode_get_insts(ModuleInfo0, ModeOfX, IX, FX),
-			mode_get_insts(ModuleInfo0, ModeOfY, IY, FY),
-			determinism_components(Det, CanFail, _),
-			UniMode = ((IX - IY) -> (FX - FY)),
-			Unification = complicated_unify(UniMode, CanFail),
+			% check for known functor on the left hand side
+			InitialInstX = bound(_Uniq,
+					[functor(ConsId, ArgInsts)]),
+			inst_is_ground(ModuleInfo0, InitialInstY) % see above
+		->
+			split_complicated_unify(Y, X, ConsId,
+				Type, ArgInsts, UnifyContext, ModeInfo0,
+				Unify, ExtraGoals, ModeInfo)
+		;
+			%
+			% This is the ordinary case of an in-in unification.
+			% Check whether it is a simple_test or a
+			% complicated_unify.
+			%
 			(
-				type_is_higher_order(Type, PredOrFunc, _)
+				type_is_atomic(Type, ModuleInfo0)
 			->
-				% we do not want to report this as an error
-				% if it occurs in a compiler-generated
-				% predicate - instead, we delay the error
-				% until runtime so that it only occurs if
-				% the compiler-generated predicate gets called
-				mode_info_get_predid(ModeInfo0, PredId),
-				module_info_pred_info(ModuleInfo0, PredId,
-						PredInfo),
-				( code_util__compiler_generated(PredInfo) ->
-					ModeInfo = ModeInfo0
-				;
-					set__init(WaitingVars),
-					mode_info_error(WaitingVars,
-			mode_error_unify_pred(X, error_at_var(Y), Type, PredOrFunc),
-						ModeInfo0, ModeInfo)
-				)
-			;
-				type_to_type_id(Type, TypeId, _)
-			->
-				unify_proc__request_unify(TypeId - UniMode, Det,
-					ModuleInfo0, ModuleInfo),
-				mode_info_set_module_info(ModeInfo0, ModuleInfo,
-					ModeInfo)
-			;
+				Unification = simple_test(X, Y),
+				optimize_unify(Unification, X, Y,
+					ModeOfX, ModeOfY,
+					Det, UnifyContext, ModeInfo0,
+					Unify),
+				ExtraGoals = no_extra_goals,
 				ModeInfo = ModeInfo0
+			;
+				handle_complicated_unify(X, Y,
+					ModeOfX, ModeOfY,
+					Det, UnifyContext, ModeInfo0,
+					Unify, ExtraGoals, ModeInfo)
 			)
 		)
-	),
+	).
+
+:- pred optimize_unify(unification, var, var, mode, mode, determinism,
+		unify_context, mode_info, hlds_goal_expr).
+:- mode optimize_unify(in, in, in, in, in, in, in, mode_info_ui, out) is det.
+
+optimize_unify(Unification, X, Y, ModeOfX, ModeOfY, Det, UnifyContext, ModeInfo,
+		Unify) :-
 	%
 	% Optimize away unifications with dead variables
 	% and simple tests that cannot fail
@@ -869,6 +944,151 @@
 				UnifyContext)
 	).
 
+:- pred handle_complicated_unify(var, var, mode, mode,
+			determinism, unify_context, mode_info,
+			hlds_goal_expr, extra_goals, mode_info).
+:- mode handle_complicated_unify(in, in, in, in, in, in, mode_info_di,
+			out, out, mode_info_uo) is det.
+
+handle_complicated_unify(X, Y, ModeOfX, ModeOfY, Det, UnifyContext, ModeInfo0,
+			Unify, ExtraGoals, ModeInfo) :-
+	mode_get_insts(ModuleInfo0, ModeOfX, InitialInstX, FinalInstX),
+	mode_get_insts(ModuleInfo0, ModeOfY, InitialInstY, FinalInstY),
+	UniMode = ((InitialInstX - InitialInstY) -> (FinalInstX - FinalInstY)),
+	determinism_components(Det, CanFail, _),
+
+	%
+	% report an error for unification of higher-order types
+	%
+	mode_info_get_module_info(ModeInfo0, ModuleInfo0),
+	mode_info_get_var_types(ModeInfo0, VarTypes),
+	map__lookup(VarTypes, X, Type),
+	(
+		type_is_higher_order(Type, PredOrFunc, _)
+	->
+		% we do not want to report this as an error
+		% if it occurs in a compiler-generated
+		% predicate - instead, we delay the error
+		% until runtime so that it only occurs if
+		% the compiler-generated predicate gets called
+		mode_info_get_predid(ModeInfo0, PredId),
+		module_info_pred_info(ModuleInfo0, PredId, PredInfo),
+		( code_util__compiler_generated(PredInfo) ->
+			ModeInfo = ModeInfo0
+		;
+			set__init(WaitingVars),
+			mode_info_error(WaitingVars,
+				mode_error_unify_pred(X, error_at_var(Y),
+						Type, PredOrFunc),
+				ModeInfo0, ModeInfo)
+		),
+		Unification = complicated_unify(UniMode, CanFail),
+		Unify = unify(X, var(Y), ModeOfX - ModeOfY,
+				Unification, UnifyContext),
+		ExtraGoals = no_extra_goals
+	;
+		%
+		% It's a genuine complicated unification --
+		% we need to insert it into the unify_proc request queue.
+		%
+		(
+			type_to_type_id(Type, TypeId, _)
+		->
+			unify_proc__request_unify(TypeId - UniMode, Det,
+				ModuleInfo0, ModuleInfo),
+			mode_info_set_module_info(ModeInfo0, ModuleInfo,
+				ModeInfo)
+		;
+			ModeInfo = ModeInfo0
+		),
+		Unification = complicated_unify(UniMode, CanFail),
+		Unify = unify(X, var(Y), ModeOfX - ModeOfY,
+				Unification, UnifyContext),
+		ExtraGoals = no_extra_goals
+	).
+
+:- pred split_complicated_unify(var, var, cons_id,
+			type, list(inst), unify_context, mode_info,
+			hlds_goal_expr, extra_goals, mode_info).
+:- mode split_complicated_unify(in, in, in, in, in, in, mode_info_di,
+			out, out, mode_info_uo) is det.
+
+split_complicated_unify(X, Y, ConsId, Type, ArgInsts, UnifyContext,
+			ModeInfo0, MainGoal, ExtraGoals, ModeInfo) :-
+	% Hmm... would it be worthwhile to special-case things
+	% for the case where ArgInsts = []?
+
+	%
+	% figure out the types of the functor's arguments
+	%
+	mode_info_get_module_info(ModeInfo0, ModuleInfo0),
+	type_util__get_cons_id_arg_types(ModuleInfo0, Type, ConsId, ArgTypes),
+	( list__same_length(ArgInsts, ArgTypes) ->
+		true
+	;
+		error("split_complicated_unify: length mismatch")
+	),
+
+	%
+	% construct the list of fresh argument variables ArgVars
+	% whose types we computed above
+	%
+	mode_info_get_var_types(ModeInfo0, VarTypes0),
+	mode_info_get_varset(ModeInfo0, VarSet0),
+	make_fresh_vars(ArgTypes, VarSet0, VarTypes0,
+			ArgVars, VarSet, VarTypes),
+	mode_info_set_varset(VarSet, ModeInfo0, ModeInfo1),
+	mode_info_set_var_types(VarTypes, ModeInfo1, ModeInfo2),
+
+	%
+	% modecheck the unifications `X = Functor(ArgVars)'
+	% and `Y = Functor(ArgVars)'.
+	%
+	DummyMode = ((free - free) -> (free - free)),
+	DummyUnify = complicated_unify(DummyMode, can_fail),
+	modecheck_unify_functor(X, Type, ConsId, ArgVars, DummyUnify,
+				ExtraGoalsX, ModeX, _ConsIdX, ArgVarsX,
+				DeconstructX1, ModeInfo2, ModeInfo3),
+	mode_info_get_instmap(ModeInfo3, InstMapBeforeY),
+	modecheck_unify_functor(Y, Type, ConsId, ArgVars, DummyUnify,
+				ExtraGoalsY, ModeY, _ConsIdY, ArgVarsY,
+				DeconstructY1, ModeInfo3, ModeInfo),
+	DeconstructX = unify(X, functor(ConsId, ArgVarsX),
+				ModeX, DeconstructX1, UnifyContext),
+	DeconstructY = unify(Y, functor(ConsId, ArgVarsY),
+				ModeY, DeconstructY1, UnifyContext),
+
+	%
+	% Compute the goal_info, with nonlocal vars & instmap delta,
+	% for the newly created goal DeconstructY.
+	% (We don't need to do that for DeconstructX, since we'll
+	% return DeconstructX as the main unification, and this stuff
+	% gets done for it automatically, in `handle_extra_goals'.)
+	%
+	set__list_to_set([Y|ArgVarsY], NonLocalsY),
+	( ExtraGoalsY = extra_goals(InstMapAfterY0, _) ->
+		InstMapAfterY = InstMapAfterY0
+	;
+		mode_info_get_instmap(ModeInfo, InstMapAfterY)
+	),
+	compute_instmap_delta(InstMapBeforeY, InstMapAfterY, NonLocalsY,
+		InstMapDeltaY),
+	goal_info_init(GoalInfoY0),
+	goal_info_set_nonlocals(GoalInfoY0, NonLocalsY, GoalInfoY1),
+	goal_info_set_instmap_delta(GoalInfoY1, InstMapDeltaY, GoalInfoY),
+
+	%
+	% Now return the unifications we've constructed.
+	% We treat `DeconstructX' as the main unification,
+	% and put `ExtraGoalsX', `DeconstructY' and `ExtraGoalsY'
+	% into the `AfterGoals' list (in that order).
+	%
+	MainGoal = DeconstructX,
+	DeconstructYGoal = extra_goals(InstMapBeforeY,
+				[DeconstructY - GoalInfoY]),
+	append_extra_goals(ExtraGoalsX, DeconstructYGoal, ExtraGoals0),
+	append_extra_goals(ExtraGoals0, ExtraGoalsY, ExtraGoals).
+
 % categorize_unify_var_lambda works out which category a unification
 % between a variable and a lambda expression is - whether it is a construction
 % unification or a deconstruction.  It also works out whether it will
@@ -1080,6 +1300,24 @@
 	varset__new_var(VarSet0, Var, VarSet1),
 	map__det_insert(VarTypes0, Var, Type, VarTypes1),
 	make_fresh_vars(Types, VarSet1, VarTypes1, Vars, VarSet, VarTypes).
+
+%-----------------------------------------------------------------------------%
+
+	% Given a unification goal, which must be something that can be
+	% returned from categorize_unify_var_var (i.e.  a unification
+	% of two vars, a unification of a var and a functor, or an
+	% empty conjunction), return a list of all the variables in the
+	% goal.
+unify_vars(Unify, UnifyVars) :-
+	( Unify = unify(LHS, RHS, _, _, _), RHS = var(RHS_Var) ->
+		UnifyVars = [LHS, RHS_Var]
+	; Unify = unify(LHS, RHS, _, _, _), RHS = functor(_, RHS_ArgVars) ->
+		UnifyVars = [LHS | RHS_ArgVars]
+	; Unify = conj([]) ->
+		UnifyVars = []
+	;
+		error("modecheck_unify: unify_vars")
+	).
 
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
Index: modes.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/modes.m,v
retrieving revision 1.200
diff -u -r1.200 modes.m
--- modes.m	1997/05/21 02:13:39	1.200
+++ modes.m	1997/07/07 17:44:38
@@ -208,7 +208,7 @@
 :- mode modecheck_set_var_inst(in, in, mode_info_di, mode_info_uo) is det.
 
 :- pred modecheck_set_var_inst_list(list(var), list(inst), list(inst),
-					list(var), pair(list(hlds_goal)),
+					list(var), extra_goals,
 					mode_info, mode_info).
 :- mode modecheck_set_var_inst_list(in, in, in, out, out,
 					mode_info_di, mode_info_uo) is det.
@@ -239,10 +239,25 @@
 			mode_info, mode_info).
 :- mode modecheck_goal_expr(in, in, out, mode_info_di, mode_info_uo) is det.
 
+
+:- type extra_goals
+	--->	no_extra_goals
+	;	extra_goals(
+			instmap,		% instmap at end of main goal
+			list(hlds_goal)		% goals to append after
+						% the main goal
+		).
+
+	% append_extra_goals inserts adds some goals to the
+	% list of goals to insert before/after the main goal.
+	%
+:- pred append_extra_goals(extra_goals, extra_goals, extra_goals).
+:- mode append_extra_goals(in, in, out) is det.
+
 	% handle_extra_goals combines MainGoal and ExtraGoals into a single
 	% hlds_goal_expr.
 	%
-:- pred handle_extra_goals(hlds_goal_expr, pair(list(hlds_goal)),
+:- pred handle_extra_goals(hlds_goal_expr, extra_goals,
 		hlds_goal_info, list(var), list(var),
 		instmap, mode_info, hlds_goal_expr).
 :- mode handle_extra_goals(in, in, in, in, in, in, mode_info_ui, out)
@@ -825,12 +840,36 @@
 	set__delete_list(NonLocals0, LambdaVars, NonLocals),
 	set__to_sorted_list(NonLocals, Vars).
 
+append_extra_goals(no_extra_goals, ExtraGoals, ExtraGoals).
+append_extra_goals(extra_goals(InstMap, AfterGoals),
+		no_extra_goals, extra_goals(InstMap, AfterGoals)).
+append_extra_goals(extra_goals(_InstMap0, AfterGoals0),
+			extra_goals(InstMap1, AfterGoals1),
+			extra_goals(InstMap, AfterGoals)) :-
+	InstMap = InstMap1,
+	list__append(AfterGoals0, AfterGoals1, AfterGoals).
+
 handle_extra_goals(MainGoal, ExtraGoals, GoalInfo0, Args0, Args,
-		InstMap0, ModeInfo, Goal) :-
+		InstMapAtStart, _ModeInfo, Goal) :-
 	% did we introduced any extra variables (and code)?
-	( ExtraGoals = [] - [] ->
+	(
+		ExtraGoals = no_extra_goals,
 		Goal = MainGoal	% no
 	;
+		ExtraGoals = extra_goals(InstMapAfterMain, AfterGoals0),
+
+		%
+		% We need to be careful to update the delta-instmaps
+		% correctly, using the appropriate instmaps:
+		%
+		%		% InstMapAtStart is here
+		%	 main goal,
+		%		% InstMapAfterMain is here
+		%	 AfterGoals
+		%		% _InstMapAtEnd (= the instmap from _ModeInfo)
+		%		% is here, but as it happens we don't need it
+		%
+
 		% recompute the new set of non-local variables for the main goal
 		goal_info_get_nonlocals(GoalInfo0, NonLocals0),
 		set__list_to_set(Args0, OldArgVars),
@@ -841,18 +880,15 @@
 		goal_info_set_nonlocals(GoalInfo0, NonLocals, GoalInfo1),
 
 		% compute the instmap delta for the main goal
-		mode_info_get_instmap(ModeInfo, InstMap),
-		compute_instmap_delta(InstMap0, InstMap, NonLocals,
-			DeltaInstMap),
+		compute_instmap_delta(InstMapAtStart, InstMapAfterMain,
+			NonLocals, DeltaInstMap),
 		goal_info_set_instmap_delta(GoalInfo1, DeltaInstMap, GoalInfo),
 
 		% combine the main goal and the extra goals into a conjunction
 		Goal0 = MainGoal - GoalInfo,
-		ExtraGoals = BeforeGoals0 - AfterGoals0,
 		goal_info_get_context(GoalInfo0, Context),
-		handle_extra_goals_contexts(BeforeGoals0, Context, BeforeGoals),
 		handle_extra_goals_contexts(AfterGoals0, Context, AfterGoals),
-		list__append(BeforeGoals, [Goal0 | AfterGoals], GoalList),
+		GoalList = [Goal0 | AfterGoals],
 		Goal = conj(GoalList)
 	).
 
@@ -1126,7 +1162,7 @@
 modecheck_set_var_inst_list(Vars0, InitialInsts, FinalInsts, Vars, Goals) -->
 	(
 		modecheck_set_var_inst_list_2(Vars0, InitialInsts, FinalInsts,
-			Vars1, Goals1)
+			no_extra_goals, Vars1, Goals1)
 	->
 		{ Vars = Vars1, Goals = Goals1 }
 	;
@@ -1134,30 +1170,27 @@
 	).
 
 :- pred modecheck_set_var_inst_list_2(list(var), list(inst), list(inst),
-					list(var), pair(list(hlds_goal)),
+					extra_goals, list(var), extra_goals,
 					mode_info, mode_info).
-:- mode modecheck_set_var_inst_list_2(in, in, in, out, out,
+:- mode modecheck_set_var_inst_list_2(in, in, in, in, out, out,
 					mode_info_di, mode_info_uo) is semidet.
 
-modecheck_set_var_inst_list_2([], [], [], [], [] - []) --> [].
+modecheck_set_var_inst_list_2([], [], [], ExtraGoals, [], ExtraGoals) --> [].
 modecheck_set_var_inst_list_2([Var0 | Vars0], [InitialInst | InitialInsts],
-			[FinalInst | FinalInsts], [Var | Vars], Goals) -->
+			[FinalInst | FinalInsts], ExtraGoals0,
+			[Var | Vars], ExtraGoals) -->
 	modecheck_set_var_inst(Var0, InitialInst, FinalInst,
-				Var, BeforeGoals0 - AfterGoals0),
+				Var, ExtraGoals0, ExtraGoals1),
 	modecheck_set_var_inst_list_2(Vars0, InitialInsts, FinalInsts,
-				Vars, BeforeGoals1 - AfterGoals1),
-	{ list__append(BeforeGoals0, BeforeGoals1, BeforeGoals) },
-	{ list__append(AfterGoals0, AfterGoals1, AfterGoals) },
-	{ Goals = BeforeGoals - AfterGoals }.
-
-% XXX this might need to be revisited to handle unique modes
+				ExtraGoals1, Vars, ExtraGoals).
 
-:- pred modecheck_set_var_inst(var, inst, inst, var, pair(list(hlds_goal)),
+:- pred modecheck_set_var_inst(var, inst, inst, var, extra_goals, extra_goals,
 				mode_info, mode_info).
-:- mode modecheck_set_var_inst(in, in, in, out, out,
+:- mode modecheck_set_var_inst(in, in, in, out, in, out,
 				mode_info_di, mode_info_uo) is det.
 
-modecheck_set_var_inst(Var0, InitialInst, FinalInst, Var, Goals,
+modecheck_set_var_inst(Var0, InitialInst, FinalInst, Var,
+			ExtraGoals0, ExtraGoals,
 			ModeInfo0, ModeInfo) :-
 	mode_info_get_instmap(ModeInfo0, InstMap0),
 	( instmap__is_reachable(InstMap0) ->
@@ -1179,12 +1212,12 @@
 		mode_info_set_module_info(ModeInfo0, ModuleInfo, ModeInfo1),
 		handle_implied_mode(Var0,
 			VarInst0, VarInst, InitialInst, FinalInst, Det,
-		 	Var, Goals, ModeInfo1, ModeInfo2),
+		 	Var, ExtraGoals0, ExtraGoals, ModeInfo1, ModeInfo2),
 		modecheck_set_var_inst(Var0, FinalInst, ModeInfo2, ModeInfo3),
 		modecheck_set_var_inst(Var, FinalInst, ModeInfo3, ModeInfo)
 	;
 		Var = Var0,
-		Goals = [] - [],
+		ExtraGoals = ExtraGoals0,
 		ModeInfo = ModeInfo0
 	).
 
@@ -1193,8 +1226,6 @@
 	% The former is used for predicate calls, where we may need
 	% to introduce unifications to handle calls to implied modes.
 
-% XXX this might need to be revisited to handle unique modes
-
 modecheck_set_var_inst(Var0, FinalInst, ModeInfo0, ModeInfo) :-
 	mode_info_get_instmap(ModeInfo0, InstMap0),
 	( instmap__is_reachable(InstMap0) ->
@@ -1268,13 +1299,13 @@
 % introduce a fresh variable.
 
 :- pred handle_implied_mode(var, inst, inst, inst, inst, determinism,
-				var, pair(list(hlds_goal)),
+				var, extra_goals, extra_goals,
 				mode_info, mode_info).
-:- mode handle_implied_mode(in, in, in, in, in, in, out, out,
+:- mode handle_implied_mode(in, in, in, in, in, in, out, in, out,
 				mode_info_di, mode_info_uo) is det.
 
 handle_implied_mode(Var0, VarInst0, VarInst, InitialInst, FinalInst, Det,
-		Var, Goals, ModeInfo0, ModeInfo) :-
+		Var, ExtraGoals0, ExtraGoals, ModeInfo0, ModeInfo) :-
 	mode_info_get_module_info(ModeInfo0, ModuleInfo0),
 	(
 		% If the initial inst of the variable matches_final
@@ -1284,7 +1315,7 @@
 		inst_matches_final(VarInst0, InitialInst, ModuleInfo0)
 	->
 		Var = Var0,
-		Goals = [] - [],
+		ExtraGoals = ExtraGoals0,
 		ModeInfo = ModeInfo0
 	;
 		% This is the implied mode case.
@@ -1294,7 +1325,7 @@
 		( inst_is_bound(ModuleInfo0, InitialInst) ->
 			% This is the case we can't handle
 			Var = Var0,
-			Goals = [] - [],
+			ExtraGoals = ExtraGoals0,
 			set__singleton_set(WaitingVars, Var0),
 			mode_info_error(WaitingVars,
 				mode_error_implied_mode(Var0, VarInst0,
@@ -1314,34 +1345,65 @@
 			mode_info_set_varset(VarSet, ModeInfo0, ModeInfo1),
 			mode_info_set_var_types(VarTypes, ModeInfo1, ModeInfo2),
 
+			% Calculate the instmap after the main goal.
+			% We just need to set the inst of the newly
+			% introduced variable Var to the procedure
+			% argument's final inst.
+			mode_info_get_instmap(ModeInfo2, OrigInstMap),
+			instmap__set(OrigInstMap, Var, FinalInst,
+				InstMapAfterMain),
+			mode_info_set_instmap(InstMapAfterMain,
+				ModeInfo2, ModeInfo3),
+
 			% Construct the code to do the unification
 			ModeVar0 = (VarInst0 -> VarInst),
 			ModeVar = (FinalInst -> VarInst),
-			mode_info_get_mode_context(ModeInfo2, ModeContext),
-			mode_context_to_unify_context(ModeContext, ModeInfo2,
+			mode_info_get_mode_context(ModeInfo3, ModeContext),
+			mode_context_to_unify_context(ModeContext, ModeInfo3,
 				UnifyContext),
+
 			categorize_unify_var_var(ModeVar0, ModeVar,
 				live, dead, Var0, Var, Det, UnifyContext,
-				VarTypes, ModeInfo2,
-				AfterGoal, ModeInfo),
+				VarTypes, ModeInfo3,
+				NewUnifyGoal, NewUnifyExtraGoals, ModeInfo),
+			unify_vars(NewUnifyGoal, NewUnifyGoalVars),
 
 			% compute the goal_info nonlocal vars & instmap delta
-			set__list_to_set([Var0, Var], NonLocals),
-			( VarInst = VarInst0 ->
-				InstMapDeltaAL0 = []
+			% N.B.  This may overestimate the set of nonlocal vars,
+			% but that should not cause any problems.
+			set__list_to_set(NewUnifyGoalVars, NonLocals),
+			(
+				NewUnifyExtraGoals = extra_goals(
+					InstMapAfterNewUnify, _)
+			->
+				compute_instmap_delta(OrigInstMap,
+					InstMapAfterNewUnify, NonLocals,
+					InstMapDelta)
 			;
-				InstMapDeltaAL0 = [Var0 - VarInst]
+				( VarInst = VarInst0 ->
+					InstMapDeltaAL0 = []
+				;
+					InstMapDeltaAL0 = [Var0 - VarInst]
+				),
+				InstMapDeltaAL = [Var - VarInst |
+						InstMapDeltaAL0],
+				instmap_delta_from_assoc_list(InstMapDeltaAL,
+					InstMapDelta)
 			),
-			
-			InstMapDeltaAL = [Var - VarInst | InstMapDeltaAL0],
 			goal_info_init(GoalInfo0),
 			goal_info_set_nonlocals(GoalInfo0, NonLocals,
 				GoalInfo1),
-			instmap_delta_from_assoc_list(InstMapDeltaAL,
-				InstMapDelta),
 			goal_info_set_instmap_delta(GoalInfo1, InstMapDelta,
 				GoalInfo),
-			Goals = [] - [AfterGoal - GoalInfo]
+
+			% append the goals together in the appropriate order:
+			% ExtraGoals0, then NewUnify, then NewUnifyExtraGoals
+			NewUnifyExtraGoal = extra_goals(InstMapAfterMain,
+						[NewUnifyGoal - GoalInfo]),
+			append_extra_goals(ExtraGoals0, NewUnifyExtraGoal,
+				ExtraGoals1),
+			append_extra_goals(ExtraGoals1, NewUnifyExtraGoals,
+				ExtraGoals)
 		)
 	).
 
Index: unique_modes.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/unique_modes.m,v
retrieving revision 1.36
diff -u -r1.36 unique_modes.m
--- unique_modes.m	1997/05/05 11:17:39	1.36
+++ unique_modes.m	1997/05/07 11:01:47
@@ -20,6 +20,10 @@
 % called predicate (e.g. if a predicate is overloaded with both
 % `ui' and `in' modes)?
 
+% Variables can become nondet live in several places:
+% in negations, in the conditions of if-then-elses,
+% and in disjunctions, and at nondet calls.
+
 % XXX we currently make the conservative assumption that
 % any non-local variable in a disjunction or nondet call
 % is nondet-live - and stays nondet-live.
@@ -570,7 +574,7 @@
 	mode_list_get_final_insts(ProcArgModes, ModuleInfo, FinalInsts),
 	modecheck_set_var_inst_list(ArgVars, InitialInsts, FinalInsts,
 		NewArgVars, ExtraGoals, ModeInfo1, ModeInfo2),
-	( NewArgVars = ArgVars, ExtraGoals = [] - [] ->
+	( NewArgVars = ArgVars, ExtraGoals = no_extra_goals ->
 		true
 	;	
 		% this shouldn't happen, since modes.m should do
cvs diff: Diffing notes

-- 
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.



More information about the developers mailing list