[m-dev.] for review: fixing cse_detection for existential types

[Zoltan Somogyi]

On 06-Dec-2000, David Glen JEFFERY <dgj at cs.mu.OZ.AU> wrote:
> > compiler/cse_detection.m:
> > 	Fix common subexpression elimination so that it works when the
> > 	deconstruction it hoists out of a branched control structure
> > 	involves a functor with existentially typed arguments.
> > 
> > compiler/options.m:
> > 	Put the default value of --compare-specialization back to 4, now
> > 	that the bug that prevented it from working at levels above 1 has
> > 	been fixed.
> 
> This basically looks pretty good. A couple of comments, though.

I followed your comments, and fixed the bug that caused the stage 3 mode
errors. Here is the log message and diff I am committing.

compiler/cse_detection.m:
	Put back the earlier clarification of cse_detection code, but without
	the bug this time :-( The bug was that cse_detection did not insist
	on all branches of the branched control structure containing a copy
	of the "common" deconstruction unification. By hoisting that
	unification before the branched control structure, cse_detection
	was effectively adding a test into some computation paths.

	Fix common subexpression elimination so that it works when the
	deconstruction it hoists out of a branched control structure
	involves a functor with existentially typed arguments.

compiler/switch_detection.m:
	Modify the code called by cse_detection to look for deconstruction
	unifications to make it explicit whether the search was successful.

compiler/options.m:
	Put the default value of --compare-specialization back to 4, now
	that the bug that prevented it from working at levels above 1 (in the
	presence of existentially typed arguments) has been fixed.

Zoltan.

cvs diff: Diffing .
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/cse_detection.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/cse_detection.m,v
retrieving revision 1.67
diff -u -b -r1.67 cse_detection.m
--- compiler/cse_detection.m	2000/12/06 16:48:24	1.67
+++ compiler/cse_detection.m	2000/12/07 07:59:55
@@ -20,13 +20,12 @@
 
 :- import_module hlds_module, hlds_pred, io.
 
-:- pred detect_cse(module_info, module_info, io__state, io__state).
-:- mode detect_cse(in, out, di, uo) is det.
+:- pred detect_cse(module_info::in, module_info::out,
+	io__state::di, io__state::uo) is det.
 
-:- pred detect_cse_in_proc(proc_id, pred_id, module_info, module_info,
-			io__state, io__state).
-% :- mode detect_cse_in_proc(in, in, di, uo, di, uo) is det.
-:- mode detect_cse_in_proc(in, in, in, out, di, uo) is det.
+:- pred detect_cse_in_proc(proc_id::in, pred_id::in,
+	module_info::in, module_info::out, io__state::di, io__state::uo)
+	is det.
 
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
@@ -34,11 +33,12 @@
 :- implementation.
 
 :- import_module hlds_goal, hlds_data, options, globals, goal_util, hlds_out.
-:- import_module modes, mode_util, quantification, instmap.
+:- import_module type_util, modes, mode_util, quantification, instmap.
 :- import_module prog_data, switch_detection, det_util, inst_match.
 :- import_module switch_detection, term, varset.
 
-:- import_module int, bool, list, map, set, std_util, require.
+:- import_module int, bool, list, assoc_list, map, multi_map.
+:- import_module set, std_util, require.
 
 %-----------------------------------------------------------------------------%
 
@@ -49,9 +49,9 @@
 	{ module_info_predids(ModuleInfo0, PredIds) },
 	detect_cse_in_preds(PredIds, ModuleInfo0, ModuleInfo).
 
-:- pred detect_cse_in_preds(list(pred_id), module_info, module_info,
-	io__state, io__state).
-:- mode detect_cse_in_preds(in, in, out, di, uo) is det.
+:- pred detect_cse_in_preds(list(pred_id)::in,
+	module_info::in, module_info::out, io__state::di, io__state::uo)
+	is det.
 
 detect_cse_in_preds([], ModuleInfo, ModuleInfo) --> [].
 detect_cse_in_preds([PredId | PredIds], ModuleInfo0, ModuleInfo) -->
@@ -60,18 +60,17 @@
 	detect_cse_in_pred(PredId, PredInfo, ModuleInfo0, ModuleInfo1),
 	detect_cse_in_preds(PredIds, ModuleInfo1, ModuleInfo).
 
-:- pred detect_cse_in_pred(pred_id, pred_info, module_info, module_info,
-	io__state, io__state).
-:- mode detect_cse_in_pred(in, in, in, out, di, uo) is det.
+:- pred detect_cse_in_pred(pred_id::in, pred_info::in,
+	module_info::in, module_info::out, io__state::di, io__state::uo)
+	is det.
 
 detect_cse_in_pred(PredId, PredInfo0, ModuleInfo0, ModuleInfo) -->
 	{ pred_info_non_imported_procids(PredInfo0, ProcIds) },
 	detect_cse_in_procs(ProcIds, PredId, ModuleInfo0, ModuleInfo).
 
-:- pred detect_cse_in_procs(list(proc_id), pred_id, module_info, module_info,
-			io__state, io__state).
-% :- mode detect_cse_in_procs(in, in, di, uo, di, uo) is det.
-:- mode detect_cse_in_procs(in, in, in, out, di, uo) is det.
+:- pred detect_cse_in_procs(list(proc_id)::in, pred_id::in,
+	module_info::in, module_info::out, io__state::di, io__state::uo)
+	is det.
 
 detect_cse_in_procs([], _PredId, ModuleInfo, ModuleInfo) --> [].
 detect_cse_in_procs([ProcId | ProcIds], PredId, ModuleInfo0, ModuleInfo) -->
@@ -120,11 +119,16 @@
 	).
 
 :- type cse_info
-	--->	cse_info(prog_varset, map(prog_var, type), module_info).
+	--->	cse_info(
+			varset			:: prog_varset,
+			vartypes		:: vartypes,
+			type_info_varmap	:: type_info_varmap,
+			typeclass_info_varmap	:: typeclass_info_varmap,
+			module_info		:: module_info
+		).
 
-:- pred detect_cse_in_proc_2(proc_id, pred_id, bool, module_info, module_info).
-% :- mode detect_cse_in_proc_2(in, in, out, di, uo) is det.
-:- mode detect_cse_in_proc_2(in, in, out, in, out) is det.
+:- pred detect_cse_in_proc_2(proc_id::in, pred_id::in, bool::out,
+	module_info::in, module_info::out) is det.
 
 detect_cse_in_proc_2(ProcId, PredId, Redo, ModuleInfo0, ModuleInfo) :-
 	module_info_preds(ModuleInfo0, PredTable0),
@@ -140,7 +144,10 @@
 	proc_info_get_initial_instmap(ProcInfo0, ModuleInfo0, InstMap0),
 	proc_info_varset(ProcInfo0, Varset0),
 	proc_info_vartypes(ProcInfo0, VarTypes0),
-	CseInfo0 = cse_info(Varset0, VarTypes0, ModuleInfo0),
+	proc_info_typeinfo_varmap(ProcInfo0, TypeInfoVarMap0),
+	proc_info_typeclass_info_varmap(ProcInfo0, TypeClassInfoVarMap0),
+	CseInfo0 = cse_info(Varset0, VarTypes0,
+		TypeInfoVarMap0, TypeClassInfoVarMap0, ModuleInfo0),
 	detect_cse_in_goal(Goal0, InstMap0, CseInfo0, CseInfo, Redo, Goal1),
 
 	(
@@ -150,15 +157,20 @@
 		Redo = yes,
 
 		% ModuleInfo should not be changed by detect_cse_in_goal
-		CseInfo = cse_info(Varset1, VarTypes1, _),
+		CseInfo = cse_info(VarSet1, VarTypes1,
+			TypeInfoVarMap, TypeClassInfoVarMap, _),
 		proc_info_headvars(ProcInfo0, HeadVars),
 
-		implicitly_quantify_clause_body(HeadVars, Goal1, Varset1,
-			VarTypes1, Goal, Varset, VarTypes, _Warnings),
+		implicitly_quantify_clause_body(HeadVars, Goal1, VarSet1,
+			VarTypes1, Goal, VarSet, VarTypes, _Warnings),
 
 		proc_info_set_goal(ProcInfo0, Goal, ProcInfo1),
-		proc_info_set_varset(ProcInfo1, Varset, ProcInfo2),
-		proc_info_set_vartypes(ProcInfo2, VarTypes, ProcInfo),
+		proc_info_set_varset(ProcInfo1, VarSet, ProcInfo2),
+		proc_info_set_vartypes(ProcInfo2, VarTypes, ProcInfo3),
+		proc_info_set_typeinfo_varmap(ProcInfo3,
+			TypeInfoVarMap, ProcInfo4),
+		proc_info_set_typeclass_info_varmap(ProcInfo4,
+			TypeClassInfoVarMap, ProcInfo),
 
 		map__det_update(ProcTable0, ProcId, ProcInfo, ProcTable),
 		pred_info_set_procedures(PredInfo0, ProcTable, PredInfo),
@@ -173,9 +185,8 @@
 	% and hoist these out of the disjunction. At the moment
 	% we only look for cses that are deconstruction unifications.
 
-:- pred detect_cse_in_goal(hlds_goal, instmap, cse_info, cse_info,
-	bool, hlds_goal).
-:- mode detect_cse_in_goal(in, in, in, out, out, out) is det.
+:- pred detect_cse_in_goal(hlds_goal::in, instmap::in, cse_info::in,
+	cse_info::out, bool::out, hlds_goal::out) is det.
 
 detect_cse_in_goal(Goal0, InstMap0, CseInfo0, CseInfo, Redo, Goal) :-
 	detect_cse_in_goal_1(Goal0, InstMap0, CseInfo0, CseInfo,
@@ -186,9 +197,8 @@
 	% computed by applying the instmap delta specified in the
 	% goal's goalinfo.
 
-:- pred detect_cse_in_goal_1(hlds_goal, instmap, cse_info, cse_info, bool,
-	hlds_goal, instmap).
-:- mode detect_cse_in_goal_1(in, in, in, out, out, out, out) is det.
+:- pred detect_cse_in_goal_1(hlds_goal::in, instmap::in, cse_info::in,
+	cse_info::out, bool::out, hlds_goal::out, instmap::out) is det.
 
 detect_cse_in_goal_1(Goal0 - GoalInfo, InstMap0, CseInfo0, CseInfo, Redo,
 		Goal - GoalInfo, InstMap) :-
@@ -199,9 +209,9 @@
 
 	% Here we process each of the different sorts of goals.
 
-:- pred detect_cse_in_goal_2(hlds_goal_expr, hlds_goal_info, instmap,
-	cse_info, cse_info, bool, hlds_goal_expr).
-:- mode detect_cse_in_goal_2(in, in, in, in, out, out, out) is det.
+:- pred detect_cse_in_goal_2(hlds_goal_expr::in, hlds_goal_info::in,
+	instmap::in, cse_info::in, cse_info::out, bool::out,
+	hlds_goal_expr::out) is det.
 
 detect_cse_in_goal_2(pragma_foreign_code(A,B,C,D,E,F,G), _, _, CseInfo,
 	CseInfo, no, pragma_foreign_code(A,B,C,D,E,F,G)).
@@ -218,7 +228,7 @@
 		B0 = lambda_goal(PredOrFunc, EvalMethod, FixModes,
 			NonLocalVars, Vars, Modes, Det, Goal0)
 	->
-		CseInfo0 = cse_info(_, _, ModuleInfo),
+		ModuleInfo = CseInfo0 ^ module_info,
 		instmap__pre_lambda_update(ModuleInfo, 
 			Vars, Modes, InstMap0, InstMap),
 		detect_cse_in_goal(Goal0, InstMap, CseInfo0, CseInfo, Redo,
@@ -245,7 +255,8 @@
 
 detect_cse_in_goal_2(par_conj(Goals0, SM), _, InstMap, CseInfo0, CseInfo, Redo,
 		par_conj(Goals, SM)) :-
-	detect_cse_in_par_conj(Goals0, InstMap, CseInfo0, CseInfo, Redo, Goals).
+	detect_cse_in_par_conj(Goals0, InstMap, CseInfo0, CseInfo,
+		Redo, Goals).
 
 detect_cse_in_goal_2(disj(Goals0, SM), GoalInfo, InstMap, CseInfo0, CseInfo,
 		Redo, Goal) :-
@@ -280,9 +291,8 @@
 
 %-----------------------------------------------------------------------------%
 
-:- pred detect_cse_in_conj(list(hlds_goal), instmap, cse_info, cse_info,
-	bool, list(hlds_goal)).
-:- mode detect_cse_in_conj(in, in, in, out, out, out) is det.
+:- pred detect_cse_in_conj(list(hlds_goal)::in, instmap::in, cse_info::in,
+	cse_info::out, bool::out, list(hlds_goal)::out) is det.
 
 detect_cse_in_conj([], _InstMap, CseInfo, CseInfo, no, []).
 detect_cse_in_conj([Goal0 | Goals0], InstMap0, CseInfo0, CseInfo,
@@ -299,9 +309,8 @@
 
 %-----------------------------------------------------------------------------%
 
-:- pred detect_cse_in_par_conj(list(hlds_goal), instmap, cse_info, cse_info,
-	bool, list(hlds_goal)).
-:- mode detect_cse_in_par_conj(in, in, in, out, out, out) is det.
+:- pred detect_cse_in_par_conj(list(hlds_goal)::in, instmap::in, cse_info::in,
+	cse_info::out, bool::out, list(hlds_goal)::out) is det.
 
 detect_cse_in_par_conj([], _InstMap, CseInfo, CseInfo, no, []).
 detect_cse_in_par_conj([Goal0 | Goals0], InstMap0, CseInfo0, CseInfo,
@@ -318,9 +327,9 @@
 	% structure. Now for each non-local variable, we check whether each
 	% branch matches that variable against the same functor.
 
-:- pred detect_cse_in_disj(list(prog_var), list(hlds_goal), hlds_goal_info,
-	store_map, instmap, cse_info, cse_info, bool, hlds_goal_expr).
-:- mode detect_cse_in_disj(in, in, in, in, in, in, out, out, out) is det.
+:- pred detect_cse_in_disj(list(prog_var)::in, list(hlds_goal)::in,
+	hlds_goal_info::in, store_map::in, instmap::in, cse_info::in,
+	cse_info::out, bool::out, hlds_goal_expr::out) is det.
 
 detect_cse_in_disj([], Goals0, _, SM, InstMap, CseInfo0, CseInfo,
 		Redo, disj(Goals, SM)) :-
@@ -329,15 +338,16 @@
 		CseInfo0, CseInfo, Redo, Goal) :-
 	(
 		instmap__lookup_var(InstMap, Var, VarInst0),
-		CseInfo0 = cse_info(_, _, ModuleInfo),
+		ModuleInfo = CseInfo0 ^ module_info,
 		% XXX we only need inst_is_bound, but leave this as it is
 		% until mode analysis can handle aliasing between free
 		% variables.
 		inst_is_ground_or_any(ModuleInfo, VarInst0),
 		common_deconstruct(Goals0, Var, CseInfo0, CseInfo1,
-			Unify, Goals)
+			Unify, FirstOldNew, LaterOldNew, Goals)
 	->
-		CseInfo = CseInfo1,
+		maybe_update_existential_data_structures(Unify,
+			FirstOldNew, LaterOldNew, CseInfo1, CseInfo),
 		Goal = conj([Unify, disj(Goals, SM) - GoalInfo0]),
 		Redo = yes
 	;
@@ -345,22 +355,20 @@
 			CseInfo0, CseInfo, Redo, Goal)
 	).
 
-:- pred detect_cse_in_disj_2(list(hlds_goal), instmap, cse_info, cse_info,
-	bool, list(hlds_goal)).
-:- mode detect_cse_in_disj_2(in, in, in, out, out, out) is det.
+:- pred detect_cse_in_disj_2(list(hlds_goal)::in, instmap::in, cse_info::in,
+	cse_info::out, bool::out, list(hlds_goal)::out) is det.
 
 detect_cse_in_disj_2([], _InstMap, CseInfo, CseInfo, no, []).
 detect_cse_in_disj_2([Goal0 | Goals0], InstMap0, CseInfo0, CseInfo, Redo,
 		[Goal | Goals]) :-
 	detect_cse_in_goal(Goal0, InstMap0, CseInfo0, CseInfo1, Redo1, Goal),
-	detect_cse_in_disj_2(Goals0, InstMap0, CseInfo1, CseInfo, Redo2, Goals),
+	detect_cse_in_disj_2(Goals0, InstMap0, CseInfo1, CseInfo,
+		Redo2, Goals),
 	bool__or(Redo1, Redo2, Redo).
 
-:- pred detect_cse_in_cases(list(prog_var), prog_var, can_fail, list(case),
-	hlds_goal_info, store_map, instmap, cse_info, cse_info, bool,
-	hlds_goal_expr).
-:- mode detect_cse_in_cases(in, in, in, in, in, in, in, in, out, out, out)
-	is det.
+:- pred detect_cse_in_cases(list(prog_var)::in, prog_var::in, can_fail::in,
+	list(case)::in, hlds_goal_info::in, store_map::in, instmap::in,
+	cse_info::in, cse_info::out, bool::out, hlds_goal_expr::out) is det.
 
 detect_cse_in_cases([], SwitchVar, CanFail, Cases0, _GoalInfo, SM, InstMap,
 		CseInfo0, CseInfo, Redo,
@@ -371,15 +379,16 @@
 	(
 		Var \= SwitchVar,
 		instmap__lookup_var(InstMap, Var, VarInst0),
-		CseInfo0 = cse_info(_, _, ModuleInfo),
+		ModuleInfo = CseInfo0 ^ module_info,
 		% XXX we only need inst_is_bound, but leave this as it is
 		% until mode analysis can handle aliasing between free
 		% variables.
 		inst_is_ground_or_any(ModuleInfo, VarInst0),
 		common_deconstruct_cases(Cases0, Var, CseInfo0, CseInfo1,
-			Unify, Cases)
+			Unify, FirstOldNew, LaterOldNew, Cases)
 	->
-		CseInfo = CseInfo1,
+		maybe_update_existential_data_structures(Unify,
+			FirstOldNew, LaterOldNew, CseInfo1, CseInfo),
 		Goal = conj([Unify, switch(SwitchVar, CanFail, Cases, SM)
 			- GoalInfo]),
 		Redo = yes
@@ -388,9 +397,8 @@
 			SM, InstMap, CseInfo0, CseInfo, Redo, Goal)
 	).
 
-:- pred detect_cse_in_cases_2(list(case), instmap, cse_info, cse_info,
-	bool, list(case)).
-:- mode detect_cse_in_cases_2(in, in, in, out, out, out) is det.
+:- pred detect_cse_in_cases_2(list(case)::in, instmap::in, cse_info::in,
+	cse_info::out, bool::out, list(case)::out) is det.
 
 detect_cse_in_cases_2([], _, CseInfo, CseInfo, no, []).
 detect_cse_in_cases_2([Case0 | Cases0], InstMap, CseInfo0, CseInfo, Redo,
@@ -398,14 +406,14 @@
 	Case0 = case(Functor, Goal0),
 	detect_cse_in_goal(Goal0, InstMap, CseInfo0, CseInfo1, Redo1, Goal),
 	Case = case(Functor, Goal),
-	detect_cse_in_cases_2(Cases0, InstMap, CseInfo1, CseInfo, Redo2, Cases),
+	detect_cse_in_cases_2(Cases0, InstMap, CseInfo1, CseInfo,
+		Redo2, Cases),
 	bool__or(Redo1, Redo2, Redo).
 
-:- pred detect_cse_in_ite(list(prog_var), list(prog_var),
-	hlds_goal, hlds_goal, hlds_goal, hlds_goal_info,
-	store_map, instmap, cse_info, cse_info, bool, hlds_goal_expr).
-:- mode detect_cse_in_ite(in, in, in, in, in, in, in, in, in, out, out, out)
-	is det.
+:- pred detect_cse_in_ite(list(prog_var)::in, list(prog_var)::in,
+	hlds_goal::in, hlds_goal::in, hlds_goal::in, hlds_goal_info::in,
+	store_map::in, instmap::in, cse_info::in,
+	cse_info::out, bool::out, hlds_goal_expr::out) is det.
 
 detect_cse_in_ite([], IfVars, Cond0, Then0, Else0, _, SM, InstMap, CseInfo0,
 		CseInfo, Redo, if_then_else(IfVars, Cond, Then, Else, SM)) :-
@@ -414,17 +422,18 @@
 detect_cse_in_ite([Var | Vars], IfVars, Cond0, Then0, Else0, GoalInfo,
 		SM, InstMap, CseInfo0, CseInfo, Redo, Goal) :-
 	(
-		CseInfo0 = cse_info(_, _, ModuleInfo),
+		ModuleInfo = CseInfo0 ^ module_info,
 		instmap__lookup_var(InstMap, Var, VarInst0),
 		% XXX we only need inst_is_bound, but leave this as it is
 		% until mode analysis can handle aliasing between free
 		% variables.
 		inst_is_ground_or_any(ModuleInfo, VarInst0),
 		common_deconstruct([Then0, Else0], Var, CseInfo0, CseInfo1,
-			Unify, Goals),
+			Unify, FirstOldNew, LaterOldNew, Goals),
 		Goals = [Then, Else]
 	->
-		CseInfo = CseInfo1,
+		maybe_update_existential_data_structures(Unify,
+			FirstOldNew, LaterOldNew, CseInfo1, CseInfo),
 		Goal = conj([Unify, if_then_else(IfVars, Cond0, Then, Else, SM)
 			- GoalInfo]),
 		Redo = yes
@@ -433,9 +442,9 @@
 			SM, InstMap, CseInfo0, CseInfo, Redo, Goal)
 	).
 
-:- pred detect_cse_in_ite_2(hlds_goal, hlds_goal, hlds_goal,
-	instmap, cse_info, cse_info, bool, hlds_goal, hlds_goal, hlds_goal).
-:- mode detect_cse_in_ite_2(in, in, in, in, in, out, out, out, out, out) is det.
+:- pred detect_cse_in_ite_2(hlds_goal::in, hlds_goal::in, hlds_goal::in,
+	instmap::in, cse_info::in, cse_info::out, bool::out,
+	hlds_goal::out, hlds_goal::out, hlds_goal::out) is det.
 
 detect_cse_in_ite_2(Cond0, Then0, Else0, InstMap0, CseInfo0, CseInfo, Redo,
 		Cond, Then, Else) :-
@@ -461,189 +470,406 @@
 %	has been hoisted out, with the new variables as the functor arguments.
 %	Unify is the unification that was hoisted out.
 
-:- pred common_deconstruct(list(hlds_goal), prog_var, cse_info, cse_info,
-	hlds_goal, list(hlds_goal)).
-:- mode common_deconstruct(in, in, in, out, out, out) is semidet.
-
-common_deconstruct(Goals0, Var, CseInfo0, CseInfo, Unify, Goals) :-
-	common_deconstruct_2(Goals0, Var, no, CseInfo0, CseInfo,
-		Goals, MaybeUnifyGoal),
-	MaybeUnifyGoal = yes(Unify).
-
-:- pred common_deconstruct_2(list(hlds_goal), prog_var, maybe(hlds_goal),
-	cse_info, cse_info, list(hlds_goal), maybe(hlds_goal)).
-:- mode common_deconstruct_2(in, in, in, in, out, out, out) is semidet.
-
-common_deconstruct_2([], _Var, MaybeUnify, CseInfo, CseInfo, [], MaybeUnify).
-common_deconstruct_2([Goal0 | Goals0], Var, MaybeUnify0,
-		CseInfo0, CseInfo, [Goal | Goals], MaybeUnify) :-
+:- pred common_deconstruct(list(hlds_goal)::in, prog_var::in, cse_info::in,
+	cse_info::out, hlds_goal::out, assoc_list(prog_var)::out,
+	list(assoc_list(prog_var))::out, list(hlds_goal)::out) is semidet.
+
+common_deconstruct(Goals0, Var, CseInfo0, CseInfo, Unify,
+		FirstOldNew, LaterOldNew, Goals) :-
+	common_deconstruct_2(Goals0, Var, before_candidate,
+		have_candidate(Unify, FirstOldNew, LaterOldNew),
+		CseInfo0, CseInfo, Goals),
+	LaterOldNew = [_ | _].
+
+:- pred common_deconstruct_2(list(hlds_goal)::in, prog_var::in,
+	cse_state::in, cse_state::out, cse_info::in, cse_info::out,
+	list(hlds_goal)::out) is semidet.
+
+common_deconstruct_2([], _Var, CseState, CseState, CseInfo, CseInfo, []).
+common_deconstruct_2([Goal0 | Goals0], Var, CseState0, CseState,
+		CseInfo0, CseInfo, [Goal | Goals]) :-
 	find_bind_var(Var, find_bind_var_for_cse_in_deconstruct, Goal0, Goal,
-		MaybeUnify0 - no, MaybeUnify1 - yes, CseInfo0, CseInfo1),
-	MaybeUnify1 = yes(_),
-	common_deconstruct_2(Goals0, Var, MaybeUnify1, CseInfo1, CseInfo,
-		Goals, MaybeUnify).
+		CseState0, CseState1, CseInfo0, CseInfo1, yes),
+	CseState1 = have_candidate(_, _, _),
+	common_deconstruct_2(Goals0, Var, CseState1, CseState,
+		CseInfo1, CseInfo, Goals).
 
 %-----------------------------------------------------------------------------%
 
-:- pred common_deconstruct_cases(list(case), prog_var, cse_info, cse_info,
-	hlds_goal, list(case)).
-:- mode common_deconstruct_cases(in, in, in, out, out, out) is semidet.
+:- pred common_deconstruct_cases(list(case)::in, prog_var::in,
+	cse_info::in, cse_info::out, hlds_goal::out, assoc_list(prog_var)::out,
+	list(assoc_list(prog_var))::out, list(case)::out) is semidet.
 
 common_deconstruct_cases(Cases0, Var, CseInfo0, CseInfo,
-		Unify, Cases) :-
-	common_deconstruct_cases_2(Cases0, Var, no, CseInfo0, CseInfo,
-		Cases, MaybeUnifyGoal),
-	MaybeUnifyGoal = yes(Unify).
-
-:- pred common_deconstruct_cases_2(list(case), prog_var, maybe(hlds_goal),
-	cse_info, cse_info, list(case), maybe(hlds_goal)).
-:- mode common_deconstruct_cases_2(in, in, in, in, out, out, out) is semidet.
-
-common_deconstruct_cases_2([], _Var, MaybeUnify, CseInfo, CseInfo,
-	[], MaybeUnify).
-common_deconstruct_cases_2([case(ConsId, Goal0) | Cases0], Var, MaybeUnify0,
-		CseInfo0, CseInfo, [case(ConsId, Goal) | Cases], MaybeUnify) :-
+		Unify, FirstOldNew, LaterOldNew, Cases) :-
+	common_deconstruct_cases_2(Cases0, Var, before_candidate,
+		have_candidate(Unify, FirstOldNew, LaterOldNew),
+		CseInfo0, CseInfo, Cases),
+	LaterOldNew = [_ | _].
+
+:- pred common_deconstruct_cases_2(list(case)::in, prog_var::in,
+	cse_state::in, cse_state::out, cse_info::in, cse_info::out,
+	list(case)::out) is semidet.
+
+common_deconstruct_cases_2([], _Var, CseState, CseState, CseInfo, CseInfo, []).
+common_deconstruct_cases_2([case(ConsId, Goal0) | Cases0], Var,
+		CseState0, CseState, CseInfo0, CseInfo,
+		[case(ConsId, Goal) | Cases]) :-
 	find_bind_var(Var, find_bind_var_for_cse_in_deconstruct, Goal0, Goal,
-		MaybeUnify0 - no, MaybeUnify1 - yes, CseInfo0, CseInfo1),
-	MaybeUnify1 = yes(_),
-	common_deconstruct_cases_2(Cases0, Var, MaybeUnify1, CseInfo1, CseInfo,
-		Cases, MaybeUnify).
+		CseState0, CseState1, CseInfo0, CseInfo1, yes),
+	CseState1 = have_candidate(_, _, _),
+	common_deconstruct_cases_2(Cases0, Var, CseState1, CseState,
+		CseInfo1, CseInfo, Cases).
 
 %-----------------------------------------------------------------------------%
+
+	% This data structure represents the state of the search for
+	% deconstructions in all the branches of a branched control structure
+	% that deconstruct a given variable with the same functor.
+	% Initially, we don't know what unification we will hoist out, so the
+	% state is before_candidate. When we find a unification we want to
+	% hoist out, this fixes the functor, and the state is have_candidate.
+	% If we find that some branches unify that variable with some other
+	% functor, we have multiple_candidates, which means that we don't hoist
+	% out any of them. (Although our caller may try again with another
+	% variable.)
+	%
+	% The goal field contains the unification we are proposing to put
+	% before the branched control structure. The first_old_new field
+	% gives the mapping from argument variables in the old unification
+	% in the first branch to the freshly created variables in the goal
+	% being hoisted before the branched control structure. The
+	% later_old_new field contains the same information for the second
+	% and later branches.
+:- type cse_state
+	--->	before_candidate
+	;	have_candidate(
+			goal		::	hlds_goal,
+			first_old_new	::	assoc_list(prog_var),
+			later_old_new	::	list(assoc_list(prog_var))
+		)
+	;	multiple_candidates.
 
-	% The hlds_goal is the common unification we are attemping to hoist.
-	% The boolean states whether such a deconstruction has been seen in
-	% this branch.
-:- type cse_result == pair(maybe(hlds_goal), bool).
-
-:- pred find_bind_var_for_cse_in_deconstruct(prog_var, hlds_goal,
-		list(hlds_goal), cse_result, cse_result, cse_info, cse_info).
-:- mode find_bind_var_for_cse_in_deconstruct(in, in, out,
-	in, out, in, out) is det.
+:- pred find_bind_var_for_cse_in_deconstruct(prog_var::in, hlds_goal::in,
+	list(hlds_goal)::out, cse_state::in, cse_state::out,
+	cse_info::in, cse_info::out) is det.
 
 find_bind_var_for_cse_in_deconstruct(Var, Goal0, Goals,
-		CseResult0, CseResult, CseInfo0, CseInfo) :-
-	CseResult0 = MaybeUnify0 - _,
+		CseState0, CseState, CseInfo0, CseInfo) :-
 	(
-		MaybeUnify0 = no,
-		CseInfo0 = cse_info(Varset0, Typemap0, ModuleInfo),
-		construct_common_unify(Var, Goal0, Goal,
-			Varset0, Varset, Typemap0, Typemap, Goals),
-		CseInfo = cse_info(Varset, Typemap, ModuleInfo),
-		MaybeUnify = yes(Goal),
-		Seen = yes
+		CseState0 = before_candidate,
+		construct_common_unify(Var, Goal0, CseInfo0, CseInfo,
+			OldNewVars, HoistedGoal, Goals),
+		CseState = have_candidate(HoistedGoal, OldNewVars, [])
 	;
-		MaybeUnify0 = yes(OldUnifyGoal),
+		CseState0 = have_candidate(HoistedGoal,
+			FirstOldNewVars, LaterOldNewVars0),
 		CseInfo = CseInfo0,
 		Goal0 = _ - GoalInfo,
 		goal_info_get_context(GoalInfo, Context),
 		(
-			find_similar_deconstruct(OldUnifyGoal,
-				Goal0, Context, Goals0)
+			find_similar_deconstruct(HoistedGoal,
+				Goal0, Context, OldNewVars, Goals0)
 		->
 			Goals = Goals0,
-			MaybeUnify = MaybeUnify0,
-			Seen = yes
+			LaterOldNewVars = [OldNewVars | LaterOldNewVars0],
+			CseState = have_candidate(HoistedGoal,
+				FirstOldNewVars, LaterOldNewVars)
 		;	
 			Goals = [Goal0],
-			MaybeUnify = no,
-			Seen = no
+			CseState = multiple_candidates
 		)
-	),
-	CseResult = MaybeUnify - Seen.
+	;
+		CseState0 = multiple_candidates,
+		Goals = [Goal0],
+		CseState = multiple_candidates,
+		CseInfo = CseInfo0
+	).
 
-:- pred construct_common_unify(prog_var, hlds_goal, hlds_goal, prog_varset,
-	prog_varset, map(prog_var, type), map(prog_var, type), list(hlds_goal)).
-:- mode construct_common_unify(in, in, out, in, out, in, out, out) is det.
+:- pred construct_common_unify(prog_var::in, hlds_goal::in,
+	cse_info::in, cse_info::out, assoc_list(prog_var)::out,
+	hlds_goal::out, list(hlds_goal)::out) is det.
 
-construct_common_unify(Var, GoalExpr0 - GoalInfo, Goal, Varset0, Varset,
-		Typemap0, Typemap, Replacements) :-
+construct_common_unify(Var, GoalExpr0 - GoalInfo, CseInfo0, CseInfo,
+		OldNewVars, HoistedGoal, Replacements) :-
 	(
 		GoalExpr0 = unify(_, Term, Umode, Unif0, Ucontext),
 		Unif0 = deconstruct(_, Consid, Args, Submodes, CanFail, CanCGC)
 	->
-		Unif = deconstruct(Var, Consid, Args,
-				Submodes, CanFail, CanCGC),
+		Unif = deconstruct(Var, Consid, Args, Submodes, CanFail,
+			CanCGC),
 		( Term = functor(_, _) ->
 			GoalExpr1 = unify(Var, Term, Umode, Unif, Ucontext)
 		;
-			error("unexpected unify structure in construct_common_unify")
+			error("non-functor unify in construct_common_unify")
 		),
 		goal_info_get_context(GoalInfo, Context),
 		create_parallel_subterms(Args, Context, Ucontext,
-			Varset0, Varset, Typemap0, Typemap, Sub, Replacements),
-		goal_util__rename_vars_in_goal(GoalExpr1 - GoalInfo, Sub, Goal)
+			CseInfo0, CseInfo, OldNewVars, Replacements),
+		map__from_assoc_list(OldNewVars, Sub),
+		goal_util__rename_vars_in_goal(GoalExpr1 - GoalInfo, Sub,
+			HoistedGoal)
 	;
-		error("unexpected goal in construct_common_unify")
+		error("non-unify goal in construct_common_unify")
 	).
+
+:- pred create_parallel_subterms(list(prog_var)::in, prog_context::in,
+	unify_context::in, cse_info::in, cse_info::out,
+	assoc_list(prog_var)::out, list(hlds_goal)::out) is det.
+
+create_parallel_subterms([], _, _, CseInfo, CseInfo, [], []).
+create_parallel_subterms([OFV | OFV0], Context, UnifyContext,
+		CseInfo0, CseInfo, OldNewVars, Replacements) :-
+	create_parallel_subterms(OFV0, Context, UnifyContext,
+		CseInfo0, CseInfo1, OldNewVars1, Replacements1),
+	create_parallel_subterm(OFV, Context, UnifyContext,
+		CseInfo1, CseInfo, OldNewVars1, OldNewVars, Goal),
+	Replacements = [Goal | Replacements1].
 
-:- pred create_parallel_subterms(list(prog_var), prog_context, unify_context,
-	prog_varset, prog_varset, map(prog_var, type), map(prog_var, type),
-	map(prog_var, prog_var), list(hlds_goal)).
-:- mode create_parallel_subterms(in, in, in, in, out, in, out, out, out) is det.
-
-create_parallel_subterms([], _, _, Varset, Varset, Typemap, Typemap, Sub, []) :-
-	map__init(Sub).
-create_parallel_subterms([OFV | OFV0], Context, UnifyContext, Varset0, Varset,
-		Typemap0, Typemap, Sub, Replacements) :-
-	create_parallel_subterms(OFV0, Context, UnifyContext, Varset0, Varset1,
-		Typemap0, Typemap1, Sub1, Replacements1),
-	varset__new_var(Varset1, NFV, Varset),
-	map__lookup(Typemap1, OFV, Type),
-	map__det_insert(Typemap1, NFV, Type, Typemap),
-	map__det_insert(Sub1, OFV, NFV, Sub),
+:- pred create_parallel_subterm(prog_var::in, prog_context::in,
+	unify_context::in, cse_info::in, cse_info::out,
+	assoc_list(prog_var)::in, assoc_list(prog_var)::out,
+	hlds_goal::out) is det.
+
+create_parallel_subterm(OFV, Context, UnifyContext,
+		CseInfo0, CseInfo, OldNewVar0, OldNewVar, Goal) :-
+	VarSet0 = CseInfo0 ^ varset,
+	VarTypes0 = CseInfo0 ^ vartypes,
+	varset__new_var(VarSet0, NFV, VarSet),
+	map__lookup(VarTypes0, OFV, Type),
+	map__det_insert(VarTypes0, NFV, Type, VarTypes),
+	OldNewVar = [OFV - NFV | OldNewVar0],
 	UnifyContext = unify_context(MainCtxt, SubCtxt),
 	create_atomic_unification(OFV, var(NFV),
 		Context, MainCtxt, SubCtxt, Goal),
-	Replacements = [Goal | Replacements1].
+	CseInfo = (CseInfo0 ^ varset := VarSet) ^ vartypes := VarTypes.
 
 %-----------------------------------------------------------------------------%
 
-:- pred find_similar_deconstruct(hlds_goal, hlds_goal, prog_context,
-		list(hlds_goal)).
-:- mode find_similar_deconstruct(in, in, in, out) is semidet.
+:- pred find_similar_deconstruct(hlds_goal::in, hlds_goal::in,
+	prog_context::in, assoc_list(prog_var)::out, list(hlds_goal)::out)
+	is semidet.
 
-find_similar_deconstruct(OldUnifyGoal, NewUnifyGoal, Context, Replacements) :-
+find_similar_deconstruct(HoistedUnifyGoal, OldUnifyGoal, Context,
+		OldHoistedVars, Replacements) :-
 	(
-		OldUnifyGoal = unify(_OT1, _OT2, _OM, OldUnifyInfo, OC) - _,
-		OldUnifyInfo = deconstruct(_OV, OF, OFV, _OUM, _OCF, _OCGC),
-		NewUnifyGoal = unify(_NT1, _NT2, _NM, NewUnifyInfo, _NC) - _,
-		NewUnifyInfo = deconstruct(_NV, NF, NFV, _NUM, _NCF, _NCGC)
+		HoistedUnifyGoal = unify(_, _, _, HoistedUnifyInfo, OC) - _,
+		HoistedUnifyInfo = deconstruct(_, HoistedFunctor,
+			HoistedVars, _, _, _),
+		OldUnifyGoal = unify(_, _, _, OldUnifyInfo, _NC) - _,
+		OldUnifyInfo = deconstruct(_, OldFunctor, OldVars, _, _, _)
 	->
-		OF = NF,
-		list__length(OFV, OFVC),
-		list__length(NFV, NFVC),
-		OFVC = NFVC,
-		pair_subterms(OFV, NFV, Context, OC, Replacements)
+		HoistedFunctor = OldFunctor,
+		list__length(HoistedVars, HoistedVarsCount),
+		list__length(OldVars, OldVarsCount),
+		HoistedVarsCount = OldVarsCount,
+		assoc_list__from_corresponding_lists(OldVars, HoistedVars,
+			OldHoistedVars),
+		pair_subterms(OldHoistedVars, Context, OC, Replacements)
 	;
 		error("find_similar_deconstruct: non-deconstruct unify")
 	).
 
-:- pred pair_subterms(list(prog_var), list(prog_var), prog_context,
-		unify_context, list(hlds_goal)).
-:- mode pair_subterms(in, in, in, in, out) is det.
+:- pred pair_subterms(assoc_list(prog_var)::in, prog_context::in,
+	unify_context::in, list(hlds_goal)::out) is det.
 
-pair_subterms(OFV0, NFV0, Context, UnifyContext, Replacements) :-
-	(
-		OFV0 = [OFV | OFV1],
-		NFV0 = [NFV | NFV1]
-	->
-		pair_subterms(OFV1, NFV1, Context, UnifyContext, Replacements1),
-		( OFV = NFV ->
+pair_subterms([], _Context, _UnifyContext, []).
+pair_subterms([OldVar - HoistedVar | OldHoistedVars], Context, UnifyContext,
+		Replacements) :-
+	pair_subterms(OldHoistedVars, Context, UnifyContext, Replacements1),
+	( OldVar = HoistedVar ->
 			Replacements = Replacements1
 		;
 			UnifyContext = unify_context(MainCtxt, SubCtxt),
-			create_atomic_unification(OFV, var(NFV),
+		create_atomic_unification(HoistedVar, var(OldVar),
 				Context, MainCtxt, SubCtxt, Goal),
 			Replacements = [Goal | Replacements1]
+	).
+
+%-----------------------------------------------------------------------------%
+
+% This section handles the case where the functor involved in the
+% common subexpression contains existentially typed arguments,
+% whether or not they are constrained to belong to a typeclass.
+% In such cases, what the compiler used to consider several distinct
+% types (the types of say the first the existentially typed argument
+% in the deconstructions in the different branches) become one (in this
+% case, the type of the first existentially typed argument in the
+% hoisted out deconstruction). The prog_vars describing the types
+% of the existentially typed arguments (i.e. containing their
+% typeinfos) change as well, from being some of the variables in
+% in the original deconstructions to being the corresponding variables
+% in the hoisted out deconstruction.
+%
+% As an example, consider a disjunction such as
+%
+%	(
+%		HeadVar__2_2 = x:u(TypeClassInfo_for_v_8, V_4),
+%		...
+%	;
+%		HeadVar__2_2 = x:u(TypeClassInfo_for_v_14, V_6)
+%		...
+%	)
+%	
+% The main part of cse_detection will replace this with
+%	
+%	HeadVar__2_2 = x:u(V_17, V_16)
+%	(
+%		TypeClassInfo_for_v_8 = V_17,
+%		V_4 = V_16,
+%		...
+%	;
+%		TypeClassInfo_for_v_14 = V_17,
+%		V_6 = V_16,
+%		...
+%	)
+%
+% However, this is not enough. Since TypeClassInfo_for_v_8 and
+% TypeClassInfo_for_v_14 may (and probably will) be eliminated later,
+% it is imperative that the data structures in the proc_info that refer
+% to them be updated to eliminate references to those variables.
+% Those data structures may originally contain something like this:
+%	
+% type_info varmap:
+% T_1 (number 1) -> typeclass_info(TypeClassInfo_for_v_8, 1)
+% T_3 (number 3) -> typeclass_info(TypeClassInfo_for_v_14, 1)
+% typeclass_info varmap:
+% x:v(T_1) -> TypeClassInfo_for_v_8
+% x:v(T_3) -> TypeClassInfo_for_v_14
+% variable types map:
+% V_4 (number 4) :: T_1
+% V_6 (number 6) :: T_3
+%
+% They must be updated like this:
+%	
+% type_info varmap:
+% T_1 (number 1) -> typeclass_info(V_17, 1)
+% typeclass_info varmap:
+% x:v(T_1) -> V_17
+% variable types map:
+% V_4 (number 4) :: T_1
+% V_6 (number 6) :: T_1
+
+:- pred maybe_update_existential_data_structures(hlds_goal::in,
+	assoc_list(prog_var)::in, list(assoc_list(prog_var))::in,
+	cse_info::in, cse_info::out) is det.
+
+maybe_update_existential_data_structures(Unify, FirstOldNew, LaterOldNew,
+		CseInfo0, CseInfo) :-
+	(
+		Unify = unify(_, _, _, UnifyInfo, _) - _,
+		UnifyInfo = deconstruct(Var, ConsId, _, _, _, _),
+		ModuleInfo = CseInfo0 ^ module_info,
+		VarTypes = CseInfo0 ^ vartypes,
+		map__lookup(VarTypes, Var, Type),
+		type_util__is_existq_cons(ModuleInfo, Type, ConsId)
+	->
+		update_existential_data_structures(FirstOldNew, LaterOldNew,
+			CseInfo0, CseInfo)
+	;
+		CseInfo = CseInfo0
+	).
+
+:- pred update_existential_data_structures(
+	assoc_list(prog_var)::in, list(assoc_list(prog_var))::in,
+	cse_info::in, cse_info::out) is det.
+
+update_existential_data_structures(FirstOldNew, LaterOldNews,
+		CseInfo0, CseInfo) :-
+	list__condense(LaterOldNews, LaterOldNew),
+	list__append(FirstOldNew, LaterOldNew, OldNew),
+	map__from_assoc_list(OldNew, OldNewMap),
+	map__from_assoc_list(FirstOldNew, FirstOldNewMap),
+
+	TypeInfoVarMap0 = CseInfo0 ^ type_info_varmap,
+	TypeClassInfoVarMap0 = CseInfo0 ^ typeclass_info_varmap,
+	VarTypes0 = CseInfo0 ^ vartypes,
+
+	map__to_assoc_list(TypeInfoVarMap0, TypeInfoVarList0),
+	list__foldl(find_type_info_locn_tvar_map(FirstOldNewMap),
+		TypeInfoVarList0, map__init, NewTvarMap),
+
+	list__foldl2(reconstruct_type_info_varmap(OldNewMap, NewTvarMap),
+		TypeInfoVarList0, map__init, TypeInfoVarMap1,
+		map__init, TvarSub),
+	map__keys(TvarSub, ElimTvars),
+	map__delete_list(TypeInfoVarMap1, ElimTvars, TypeInfoVarMap),
+
+	map__to_assoc_list(TypeClassInfoVarMap0, TypeClassInfoVarList0),
+	list__foldl(reconstruct_typeclass_info_varmap(OldNewMap, TvarSub),
+		TypeClassInfoVarList0, map__init, TypeClassInfoVarMap),
+
+	map__map_values(apply_tvar_rename(TvarSub), VarTypes0, VarTypes),
+
+	CseInfo1 = CseInfo0 ^ type_info_varmap := TypeInfoVarMap,
+	CseInfo2 = CseInfo1 ^ typeclass_info_varmap := TypeClassInfoVarMap,
+	CseInfo = CseInfo2 ^ vartypes := VarTypes.
+
+:- pred apply_tvar_rename(map(tvar, tvar)::in, prog_var::in,
+	(type)::in, (type)::out) is det.
+
+apply_tvar_rename(TvarSub, _Var, Type0, Type) :-
+	Type = term__apply_variable_renaming(Type0, TvarSub).
+
+:- pred find_type_info_locn_tvar_map(map(prog_var, prog_var)::in,
+	pair(tvar, type_info_locn)::in,
+ 	map(type_info_locn, tvar)::in, map(type_info_locn, tvar)::out) is det.
+ 
+find_type_info_locn_tvar_map(FirstOldNewMap, Tvar - TypeInfoLocn0,
+		NewTvarMap0, NewTvarMap) :-
+ 	type_info_locn_var(TypeInfoLocn0, Old),
+ 	( map__search(FirstOldNewMap, Old, New) ->
+  		type_info_locn_set_var(TypeInfoLocn0, New, TypeInfoLocn),
+ 		map__det_insert(NewTvarMap0, TypeInfoLocn, Tvar, NewTvarMap)
+ 	;
+ 		NewTvarMap = NewTvarMap0
+ 	).
+
+:- pred reconstruct_type_info_varmap(map(prog_var, prog_var)::in,
+	map(type_info_locn, tvar)::in, pair(tvar, type_info_locn)::in,
+ 	map(tvar, type_info_locn)::in, map(tvar, type_info_locn)::out,
+	map(tvar, tvar)::in, map(tvar, tvar)::out) is det.
+ 
+reconstruct_type_info_varmap(FirstOldNewMap, NewTvarMap, Tvar - TypeInfoLocn0,
+		TypeInfoVarMap0, TypeInfoVarMap, TvarSub0, TvarSub) :-
+ 	type_info_locn_var(TypeInfoLocn0, Old),
+ 	( map__search(FirstOldNewMap, Old, New) ->
+  		type_info_locn_set_var(TypeInfoLocn0, New, TypeInfoLocn),
+ 		map__det_insert(TypeInfoVarMap0, Tvar, TypeInfoLocn,
+			TypeInfoVarMap),
+		map__lookup(NewTvarMap, TypeInfoLocn, NewTvar),
+		( Tvar = NewTvar ->
+			TvarSub = TvarSub0
+		;
+			map__det_insert(TvarSub0, Tvar, NewTvar, TvarSub)
 		)
 	;
-		OFV0 = [],
-		NFV0 = []
-	->
-		Replacements = []
+		map__det_insert(TypeInfoVarMap0, Tvar, TypeInfoLocn0,
+			TypeInfoVarMap),
+		TvarSub = TvarSub0
+ 	).
+
+:- pred reconstruct_typeclass_info_varmap(map(prog_var, prog_var)::in,
+	map(tvar, tvar)::in, pair(class_constraint, prog_var)::in,
+	typeclass_info_varmap::in, typeclass_info_varmap::out) is det.
+
+reconstruct_typeclass_info_varmap(OldNewMap, TvarSub,
+		Constraint0 - TypeClassInfoVar0,
+		TypeClassInfoVarMap0, TypeClassInfoVarMap) :-
+	type_util__apply_variable_renaming_to_constraint(TvarSub,
+		Constraint0, Constraint),
+	( map__search(OldNewMap, TypeClassInfoVar0, TypeClassInfoVar1) ->
+		TypeClassInfoVar = TypeClassInfoVar1
+	;
+		TypeClassInfoVar = TypeClassInfoVar0
+	),
+	( map__search(TypeClassInfoVarMap0, Constraint, OldTypeClassInfoVar) ->
+		require(unify(OldTypeClassInfoVar, TypeClassInfoVar),
+			"reconstruct_typeclass_info_varmap: mismatch"),
+		TypeClassInfoVarMap = TypeClassInfoVarMap0
 	;
-		error("mismatched length lists in pair_subterms")
+		map__det_insert(TypeClassInfoVarMap0, Constraint,
+			TypeClassInfoVar, TypeClassInfoVarMap)
 	).
 
 %-----------------------------------------------------------------------------%
Index: compiler/options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/options.m,v
retrieving revision 1.302
diff -u -b -r1.302 options.m
--- compiler/options.m	2000/12/06 06:05:11	1.302
+++ compiler/options.m	2000/12/06 06:06:42
@@ -649,7 +649,7 @@
 					% above default with a value determined
 					% at configuration time
 	max_jump_table_size	-	int(0),
-	compare_specialization	-	int(1),
+	compare_specialization	-	int(4),
 					% 0 indicates any size.
 	fact_table_max_array_size -	int(1024),
 	fact_table_hash_percent_full - 	int(90),
Index: compiler/switch_detection.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/switch_detection.m,v
retrieving revision 1.93
diff -u -b -r1.93 switch_detection.m
--- compiler/switch_detection.m	2000/12/05 02:03:45	1.93
+++ compiler/switch_detection.m	2000/12/07 04:55:48
@@ -17,25 +17,26 @@
 :- interface.
 
 :- import_module hlds_goal, hlds_module, hlds_pred, prog_data.
-:- import_module io, list.
+:- import_module bool, io, list.
 
-:- pred detect_switches(module_info, module_info, io__state, io__state).
-:- mode detect_switches(in, out, di, uo) is det.
+:- pred detect_switches(module_info::in, module_info::out,
+	io__state::di, io__state::uo) is det.
 
-:- pred detect_switches_in_proc(proc_id, pred_id, module_info, module_info).
-:- mode detect_switches_in_proc(in, in, in, out) is det.
+:- pred detect_switches_in_proc(proc_id::in, pred_id::in,
+	module_info::in, module_info::out) is det.
 
 	% find_bind_var(Var, ProcessUnify, Goal0, Goals, Subst0, Subst,
-	%		Result0, Result, Continue):
+	%		Result0, Result, FoundDeconstruct):
 	% 	Used by both switch_detection and cse_detection.
 	%	Searches through `Goal0' looking for the first deconstruction
 	%	unification with `Var' or an alias of `Var'.
 	%	If a deconstruction unification of the variable is found,
 	%	`ProcessUnify' is called to handle it and searching is stopped.
 	%	If not, `Result' is set to `Result0'.
-:- pred find_bind_var(prog_var, process_unify(Result, Info), hlds_goal,
-		hlds_goal, Result, Result, Info, Info).
-:- mode find_bind_var(in, in(process_unify), in, out, in, out, in, out) is det.
+:- pred find_bind_var(prog_var::in,
+	process_unify(Result, Info)::in(process_unify),
+	hlds_goal::in, hlds_goal::out, Result::in, Result::out,
+	Info::in, Info::out, bool::out) is det.
 
 :- type process_unify(Result, Info) ==
 	pred(prog_var, hlds_goal, list(hlds_goal), Result, Result, Info, Info).
@@ -49,7 +50,7 @@
 :- import_module hlds_goal, hlds_data, prog_data, instmap, inst_match.
 :- import_module modes, mode_util, type_util, det_util.
 :- import_module passes_aux, term.
-:- import_module bool, char, int, assoc_list, map, set, std_util, require.
+:- import_module char, int, assoc_list, map, set, std_util, require.
 
 %-----------------------------------------------------------------------------%
 
@@ -406,7 +407,7 @@
 partition_disj_trial([], _Var, Left, Left, Cases, Cases).
 partition_disj_trial([Goal0 | Goals], Var, Left0, Left, Cases0, Cases) :-
 	find_bind_var(Var, find_bind_var_for_switch_in_deconstruct,
-		Goal0, Goal, no, MaybeFunctor, unit, _),
+		Goal0, Goal, no, MaybeFunctor, unit, _, _),
 	(
 		MaybeFunctor = yes(Functor),
 		Left1 = Left0,
@@ -449,28 +450,44 @@
 %-----------------------------------------------------------------------------%
 
 find_bind_var(Var, ProcessUnify, Goal0, Goal,
-		Result0, Result, Info0, Info) :-
+		Result0, Result, Info0, Info, FoundDeconstruct) :-
 	map__init(Substitution),
 	find_bind_var(Var, ProcessUnify, Goal0, Goal, Substitution,
-		_, Result0, Result, Info0, Info, _).
-
-:- pred find_bind_var(prog_var, process_unify(Result, Info), hlds_goal,
-		hlds_goal, prog_substitution, prog_substitution, Result, Result,
-		Info, Info, bool).
-:- mode find_bind_var(in, in(process_unify), in, out, in,
-	out, in, out, in, out, out) is det.
+		_, Result0, Result, Info0, Info, DeconstructSearch),
+	(
+		DeconstructSearch = before_deconstruct,
+		FoundDeconstruct = no
+	;
+		DeconstructSearch = found_deconstruct,
+		FoundDeconstruct = yes
+	;
+		DeconstructSearch = given_up_search,
+		FoundDeconstruct = no
+	).
 
-find_bind_var(Var, ProcessUnify, Goal0 - GoalInfo, Goal, Substitution0,
-		Substitution, Result0, Result, Info0, Info, Continue) :-
+:- type deconstruct_search
+	--->	before_deconstruct
+	;	found_deconstruct
+	;	given_up_search.
+
+:- pred find_bind_var(prog_var::in,
+	process_unify(Result, Info)::in(process_unify),
+	hlds_goal::in, hlds_goal::out,
+	prog_substitution::in, prog_substitution::out, Result::in, Result::out,
+	Info::in, Info::out, deconstruct_search::out) is det.
+
+find_bind_var(Var, ProcessUnify, Goal0 - GoalInfo, Goal,
+		Substitution0, Substitution, Result0, Result, Info0, Info,
+		FoundDeconstruct) :-
 	( Goal0 = some(Vars, CanRemove, SubGoal0) ->
 		find_bind_var(Var, ProcessUnify, SubGoal0, SubGoal,
 			Substitution0, Substitution, Result0, Result,
-			Info0, Info, Continue),
+			Info0, Info, FoundDeconstruct),
 		Goal = some(Vars, CanRemove, SubGoal) - GoalInfo
 	; Goal0 = conj(SubGoals0) ->
 		conj_find_bind_var(Var, ProcessUnify, SubGoals0, SubGoals,
 			Substitution0, Substitution, Result0, Result,
-			Info0, Info, Continue),
+			Info0, Info, FoundDeconstruct),
 		Goal = conj(SubGoals) - GoalInfo
 	; Goal0 = unify(A, B, _, UnifyInfo0, _) ->
 		(
@@ -488,11 +505,11 @@
 			call(ProcessUnify, Var, Goal0 - GoalInfo, Goals,
 				Result0, Result, Info0, Info),
 			conj_list_to_goal(Goals, GoalInfo, Goal),
-			Continue = no,
+			FoundDeconstruct = found_deconstruct,
 			Substitution = Substitution0
 		;
 			Goal = Goal0 - GoalInfo,
-			Continue = yes,
+			FoundDeconstruct = before_deconstruct,
 			% otherwise abstractly interpret the unification
 			Result = Result0,
 			Info = Info0,
@@ -508,33 +525,33 @@
 		Substitution = Substitution0,
 		Result = Result0,
 		Info = Info0,
-		Continue = no
+		FoundDeconstruct = given_up_search
 	).
 
-:- pred conj_find_bind_var(prog_var, process_unify(Result, Info), 
-		list(hlds_goal), list(hlds_goal), prog_substitution,
-		prog_substitution, Result, Result, Info, Info, bool).
-:- mode conj_find_bind_var(in, in(process_unify), in, out,
-	in, out, in, out, in, out, out) is det.
+:- pred conj_find_bind_var(prog_var::in,
+	process_unify(Result, Info)::in(process_unify), 
+	list(hlds_goal)::in, list(hlds_goal)::out,
+	prog_substitution::in, prog_substitution::out, Result::in, Result::out,
+	Info::in, Info::out, deconstruct_search::out) is det.
 
 conj_find_bind_var(_Var, _, [], [], Substitution, Substitution,
-		Result, Result, Info, Info, yes).
+		Result, Result, Info, Info, before_deconstruct).
 conj_find_bind_var(Var, ProcessUnify, [Goal0 | Goals0], [Goal | Goals],
 		Substitution0, Substitution, Result0, Result,
-		Info0, Info, Continue) :-
+		Info0, Info, FoundDeconstruct) :-
 	find_bind_var(Var, ProcessUnify, Goal0, Goal, Substitution0,
 		Substitution1, Result0, Result1,
-		Info0, Info1, Continue1),
-	( Continue1 = no ->
-		Continue = no,
+		Info0, Info1, FoundDeconstruct1),
+	( FoundDeconstruct1 = before_deconstruct ->
+		conj_find_bind_var(Var, ProcessUnify, Goals0, Goals,
+			Substitution1, Substitution, Result1, Result,
+			Info1, Info, FoundDeconstruct)
+	;
+		FoundDeconstruct = FoundDeconstruct1,
 		Goals = Goals0,
 		Substitution = Substitution1,
 		Result = Result1,
 		Info = Info1
-	;
-		conj_find_bind_var(Var, ProcessUnify, Goals0, Goals,
-			Substitution1, Substitution, Result1, Result,
-			Info1, Info, Continue)
 	).
 
 %-----------------------------------------------------------------------------%
cvs diff: Diffing compiler/notes
cvs diff: Diffing debian
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/aditi
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing extras/concurrency
cvs diff: Diffing extras/curses
cvs diff: Diffing extras/curses/sample
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/mercury_opengl
cvs diff: Diffing extras/graphics/mercury_tcltk
cvs diff: Diffing extras/graphics/samples
cvs diff: Diffing extras/graphics/samples/calc
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/logged_output
cvs diff: Diffing extras/moose
cvs diff: Diffing extras/moose/samples
cvs diff: Diffing extras/morphine
cvs diff: Diffing extras/morphine/non-regression-tests
cvs diff: Diffing extras/morphine/scripts
cvs diff: Diffing extras/morphine/source
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/posix
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/stream
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing extras/xml
cvs diff: Diffing extras/xml/samples
cvs diff: Diffing library
cvs diff: Diffing profiler
cvs diff: Diffing robdd
cvs diff: Diffing runtime
cvs diff: Diffing runtime/GETOPT
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/c_interface/mercury_calls_fortran
cvs diff: [17:45:38] waiting for zs's lock in /home/mercury1/repository/mercury/samples/c_interface/mercury_calls_fortran
cvs diff: [17:46:08] obtained lock in /home/mercury1/repository/mercury/samples/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing samples/solutions
cvs diff: Diffing samples/tests
cvs diff: Diffing samples/tests/c_interface
cvs diff: Diffing samples/tests/c_interface/c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/tests/c_interface/mercury_calls_c
cvs diff: Diffing samples/tests/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/tests/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/tests/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/tests/diff
cvs diff: Diffing samples/tests/muz
cvs diff: Diffing samples/tests/rot13
cvs diff: Diffing samples/tests/solutions
cvs diff: Diffing samples/tests/toplevel
cvs diff: Diffing scripts
cvs diff: Diffing tests
cvs diff: Diffing tests/benchmarks
cvs diff: Diffing tests/debugger
cvs diff: Diffing tests/debugger/declarative
cvs diff: Diffing tests/dppd
cvs diff: Diffing tests/general
cvs diff: Diffing tests/general/accumulator
cvs diff: Diffing tests/hard_coded
cvs diff: Diffing tests/hard_coded/exceptions
cvs diff: Diffing tests/hard_coded/purity
cvs diff: Diffing tests/hard_coded/sub-modules
cvs diff: Diffing tests/hard_coded/typeclasses
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/invalid/purity
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/tabling
cvs diff: Diffing tests/term
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing trial
cvs diff: Diffing util
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------