for review: fix switch_detection bug

Simon Taylor stayl at cs.mu.OZ.AU
Wed Aug 26 17:03:44 AEST 1998


Estimated hours taken: 5

Fix a bug which resulted from switch_detection and cse_detection differing
on what they considered to be a common deconstruction. The code to handle
complete one-arm switches leaves them alone, expecting cse_detection to move
the deconstruction out of the disjunction and rerun switch_detection. The
symptom is that a complete multi-arm switch is not found and a determinism
error is reported.

compiler/switch_detection.m
	Generalise the find_bind_var predicates so that they can be used
	by cse_detection.m. 

compiler/cse_detection.m
	Use switch_detection:find_bind_var rather than similar code
	in cse_detection.m.

tests/valid/switch_detection_bug2.m
	Test case.

Index: cse_detection.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/cse_detection.m,v
retrieving revision 1.54
diff -u -t -u -r1.54 cse_detection.m
--- cse_detection.m	1998/06/09 02:12:15	1.54
+++ cse_detection.m	1998/08/23 05:31:29
@@ -36,6 +36,7 @@
 :- import_module hlds_goal, hlds_data, options, globals, goal_util, hlds_out.
 :- import_module modes, mode_util, make_hlds, quantification, instmap.
 :- import_module prog_data, switch_detection, det_util, inst_match.
+:- import_module switch_detection.
 
 :- import_module int, bool, list, map, set, std_util, require, term, varset.
 
@@ -474,13 +475,9 @@
 common_deconstruct_2([], _Var, MaybeUnify, CseInfo, CseInfo, [], MaybeUnify).
 common_deconstruct_2([Goal0 | Goals0], Var, MaybeUnify0,
                 CseInfo0, CseInfo, [Goal | Goals], MaybeUnify) :-
-        goal_to_conj_list(Goal0, ConjList0),
-        Goal0 = _ - GoalInfo,
-        map__init(Substitution),
-        find_bind_var_for_cse(ConjList0, Substitution, Var, MaybeUnify0,
-                CseInfo0, CseInfo1, ConjList, _NewSubstitution, MaybeUnify1),
+        find_bind_var(Var, find_bind_var_for_cse_in_deconstruct, Goal0, Goal,
+                MaybeUnify0 - no, MaybeUnify1 - yes, CseInfo0, CseInfo1),
         MaybeUnify1 = yes(_),
-        conj_list_to_goal(ConjList, GoalInfo, Goal),
         common_deconstruct_2(Goals0, Var, MaybeUnify1, CseInfo1, CseInfo,
                 Goals, MaybeUnify).
 
@@ -504,125 +501,54 @@
         [], MaybeUnify).
 common_deconstruct_cases_2([case(ConsId, Goal0) | Cases0], Var, MaybeUnify0,
                 CseInfo0, CseInfo, [case(ConsId, Goal) | Cases], MaybeUnify) :-
-        goal_to_conj_list(Goal0, ConjList0),
-        Goal0 = _ - GoalInfo,
-        map__init(Substitution),
-        find_bind_var_for_cse(ConjList0, Substitution, Var, MaybeUnify0,
-                CseInfo0, CseInfo1, ConjList, _NewSubstitution, MaybeUnify1),
+        find_bind_var(Var, find_bind_var_for_cse_in_deconstruct, Goal0, Goal,
+                MaybeUnify0 - no, MaybeUnify1 - yes, CseInfo0, CseInfo1),
         MaybeUnify1 = yes(_),
-        conj_list_to_goal(ConjList, GoalInfo, Goal),
         common_deconstruct_cases_2(Cases0, Var, MaybeUnify1, CseInfo1, CseInfo,
                 Cases, MaybeUnify).
 
 %-----------------------------------------------------------------------------%
 
-        %       Searches through Goals0 looking for a deconstruction
-        %       unification with `Var'.
-        %
-        %       If MaybeUnify0 is no, a unification with any functor
-        %       is acceptable; if it is yes(Unify), only a unification
-        %       involving the same variable and function symbol is OK.
-        %
-        %       If we do find an acceptable deconstruction, we replace it
-        %       in the goal with pairwise equalities between the arguments
-        %       of the functor in that unification and the arguments of the
-        %       functor in Unify, where in Maybeunify = yes(Unify).
-        %       If MaybeUnify0 was no, we have to create the variables in Unify.
-        %
-        %       If we do not find an acceptable deconstruction, we set
-        %       MaybeUnify to no and set `Subst' to the substitution resulting
-        %       from interpreting through the goal.
-
-:- pred find_bind_var_for_cse(list(hlds_goal), substitution, var,
-        maybe(hlds_goal), cse_info, cse_info, list(hlds_goal), 
-        substitution, maybe(hlds_goal)).
-:- mode find_bind_var_for_cse(in, in, in, in, in, out, out, out, out) is det.
-
-find_bind_var_for_cse([], Substitution, _Var, _MaybeUnify0, CseInfo, CseInfo,
-        [], Substitution, no).
-find_bind_var_for_cse([GoalPair0 | Goals0], Substitution0, Var, MaybeUnify0,
-                CseInfo0, CseInfo, Goals, Substitution, MaybeUnify) :-
-        GoalPair0 = Goal0 - GoalInfo,
-        ( Goal0 = conj(SubGoals0) ->
-                find_bind_var_for_cse(SubGoals0, Substitution0, Var,
-                        MaybeUnify0, CseInfo0, CseInfo1,
-                        SubGoals, Substitution1, MaybeUnify1),
-                Goal = conj(SubGoals),
-                ( MaybeUnify1 = yes(_) ->
-                        Goals = [Goal - GoalInfo | Goals0],
-                        Substitution = Substitution1,
-                        MaybeUnify = MaybeUnify1,
-                        CseInfo = CseInfo1
-                ;
-                        find_bind_var_for_cse(Goals0, Substitution1, Var,
-                                MaybeUnify0, CseInfo1, CseInfo,
-                                Goals1, Substitution, MaybeUnify),
-                        Goals = [Goal0 - GoalInfo | Goals1]
-                )
-        ; Goal0 = unify(A, B, _, UnifyInfo0, _) ->
-                term__apply_rec_substitution(term__variable(Var),
-                        Substitution0, Term),
+        % 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(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.
+
+find_bind_var_for_cse_in_deconstruct(Var, Goal0, Goals,
+                CseResult0, CseResult, CseInfo0, CseInfo) :-
+        CseResult0 = MaybeUnify0 - _,
+        (
+                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
+        ;
+                MaybeUnify0 = yes(OldUnifyGoal),
+                CseInfo = CseInfo0,
+                Goal0 = _ - GoalInfo,
+                goal_info_get_context(GoalInfo, Context),
                 (
-                        Term = term__variable(Var1),
-                        UnifyInfo0 = deconstruct(UnifyVar, _, _, _, _),
-                        term__apply_rec_substitution(term__variable(UnifyVar),
-                                Substitution0, term__variable(UnifyVar1)),
-                        Var1 = UnifyVar1,
-                        MaybeUnify0 = no
-                ->
-                        CseInfo0 = cse_info(Varset0, Typemap0, ModuleInfo),
-                        construct_common_unify(Var, Goal0 - GoalInfo, Goal,
-                                Varset0, Varset, Typemap0, Typemap,
-                                Replacements),
-                        CseInfo = cse_info(Varset, Typemap, ModuleInfo),
-                        MaybeUnify = yes(Goal),
-                        list__append(Replacements, Goals0, Goals),
-                        Substitution = Substitution0
-                ;
-                        Term = term__variable(Var1),
-                        UnifyInfo0 = deconstruct(UnifyVar, _, _, _, _),
-                        term__apply_rec_substitution(term__variable(UnifyVar),
-                                Substitution0, term__variable(UnifyVar1)),
-                        Var1 = UnifyVar1,
-                        UnifyInfo0 = deconstruct(_, _, _, _, _),
-                        MaybeUnify0 = yes(OldUnifyGoal),
-                        goal_info_get_context(GoalInfo, Context),
-                        find_similar_deconstruct(OldUnifyGoal, UnifyInfo0,
-                                Context, Replacements)
+                        find_similar_deconstruct(OldUnifyGoal,
+                                Goal0, Context, Goals0)
                 ->
-                        list__append(Replacements, Goals0, Goals),
-                        Substitution = Substitution0,
-                        CseInfo = CseInfo0,
-                        MaybeUnify = MaybeUnify0
-                ;
-                %
-                % if the variable was bound, but the deconstruction wasn't
-                % similar, then stop searching
-                %
-                        Term = term__functor(_, _, _)
-                ->
-                        Goals = [Goal0 - GoalInfo | Goals0],
-                        Substitution = Substitution0,
-                        CseInfo = CseInfo0,
-                        MaybeUnify = no
-                ;
-                        ( interpret_unify(A, B, Substitution0, Substitution1) ->
-                                Substitution2 = Substitution1
-                        ;
-                                % the unification must fail - just ignore it
-                                Substitution2 = Substitution0
-                        ),
-                        find_bind_var_for_cse(Goals0, Substitution2, Var,
-                                MaybeUnify0, CseInfo0, CseInfo,
-                                Goals1, Substitution, MaybeUnify),
-                        Goals = [Goal0 - GoalInfo | Goals1]
+                        Goals = Goals0,
+                        MaybeUnify = MaybeUnify0,
+                        Seen = yes
+                ;       
+                        Goals = [Goal0],
+                        MaybeUnify = no,
+                        Seen = no
                 )
-        ;
-                Goals = [Goal0 - GoalInfo | Goals0],
-                Substitution = Substitution0,
-                CseInfo = CseInfo0,
-                MaybeUnify = no
-        ).
+        ),
+        CseResult = MaybeUnify - Seen.
 
 :- pred construct_common_unify(var, hlds_goal, hlds_goal, varset, varset,
         map(var, type), map(var, type), list(hlds_goal)).
@@ -670,14 +596,15 @@
 
 %-----------------------------------------------------------------------------%
 
-:- pred find_similar_deconstruct(hlds_goal, unification, term__context,
+:- pred find_similar_deconstruct(hlds_goal, hlds_goal, term__context,
         list(hlds_goal)).
 :- mode find_similar_deconstruct(in, in, in, out) is semidet.
 
-find_similar_deconstruct(OldUnifyGoal, NewUnifyInfo, Context, Replacements) :-
+find_similar_deconstruct(OldUnifyGoal, NewUnifyGoal, Context, Replacements) :-
         (
                 OldUnifyGoal = unify(_OT1, _OT2, _OM, OldUnifyInfo, OC) - _,
                 OldUnifyInfo = deconstruct(_OV, OF, OFV, _OUM, _OCF),
+                NewUnifyGoal = unify(_NT1, _NT2, _NM, NewUnifyInfo, _NC) - _,
                 NewUnifyInfo = deconstruct(_NV, NF, NFV, _NUM, _NCF)
         ->
                 OF = NF,
Index: switch_detection.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/switch_detection.m,v
retrieving revision 1.83
diff -u -t -u -r1.83 switch_detection.m
--- switch_detection.m	1998/06/09 02:14:48	1.83
+++ switch_detection.m	1998/08/23 05:36:42
@@ -16,7 +16,8 @@
 
 :- interface.
 
-:- import_module hlds_module, hlds_pred.
+:- import_module hlds_goal, hlds_module, hlds_pred.
+:- import_module io, list, term.
 
 :- pred detect_switches(module_info, module_info, io__state, io__state).
 :- mode detect_switches(in, out, di, uo) is det.
@@ -24,6 +25,25 @@
 :- pred detect_switches_in_proc(proc_id, pred_id, module_info, module_info).
 :- mode detect_switches_in_proc(in, in, in, out) is det.
 
+        % find_bind_var(Var, ProcessUnify, Goal0, Goals, Subst0, Subst,
+        %               Result0, Result, Continue):
+        %       Used by both switch_detection and cse_detection.
+        %       Searches through `Goal0' looking for the first deconstruction
+        %       unification with `Var' or an alias of `Var'.
+        %       `ProcessUnify' is called if a deconstruction unification with
+        %       `Var' is found, returning either the cons_id for
+        %       switch_detection or the common deconstruction for cse_detection.
+        %       If a deconstruction uniication 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(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.
+
+:- type process_unify(Result, Info) ==
+        pred(var, hlds_goal, list(hlds_goal), Result, Result, Info, Info).
+:- inst process_unify = (pred(in, in, out, in, out, in, out) is det).
+
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
@@ -32,7 +52,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.
-:- import_module char, int, list, assoc_list, map, set, std_util, term, require.
+:- import_module bool, char, int, assoc_list, map, set, std_util, require.
 
 %-----------------------------------------------------------------------------%
 
@@ -385,9 +405,8 @@
 
 partition_disj_trial([], _Var, Left, Left, Cases, Cases).
 partition_disj_trial([Goal0 | Goals], Var, Left0, Left, Cases0, Cases) :-
-        map__init(Substitution),
-        find_bind_var_for_switch(Goal0, Substitution, Var,
-                        Goal, _NewSubstitution, MaybeFunctor),
+        find_bind_var(Var, find_bind_var_for_switch_in_deconstruct,
+                Goal0, Goal, no, MaybeFunctor, unit, _),
         (
                 MaybeFunctor = yes(Functor),
                 Left1 = Left0,
@@ -405,56 +424,75 @@
         ),
         partition_disj_trial(Goals, Var, Left1, Left, Cases1, Cases).
 
-        % find_bind_var_for_switch(Goal0, Subst0, Var, Goal, Subst,
-        %               MaybeFunctor):
-        % conj_find_bind_var_for_switch(Goals0, Subst0, Var, Goals, Subst,
-        %               MaybeFunctor):
-        %       Searches through Goals0 looking for a deconstruction
-        %       unification with `Var'. If found, sets `MaybeFunctor'
-        %       to `yes(Functor)', where Functor is the
-        %       functor which `Var' gets unified, and
-        %       sets `Goals' to be `Goals0' with that deconstruction
-        %       unification made deterministic. If not found, sets
-        %       `MaybeFunctor' to `no', and computes `Subst' as the
-        %       resulting substitution from interpreting through the goal.
-
-:- pred find_bind_var_for_switch(hlds_goal, substitution, var,
-        hlds_goal, substitution, maybe(cons_id)).
-:- mode find_bind_var_for_switch(in, in, in, out, out, out) is det.
+:- pred find_bind_var_for_switch_in_deconstruct(var, hlds_goal,
+                list(hlds_goal), maybe(cons_id), maybe(cons_id), unit, unit).
+:- mode find_bind_var_for_switch_in_deconstruct(in, in, out,
+                in, out, in, out) is det.
+
+find_bind_var_for_switch_in_deconstruct(_UnifyVar, Goal0, Goals, 
+                _Result0, Result, _, unit) :-
+        (
+                Goal0 = unify(A, B, C, UnifyInfo0, E) - GoalInfo,
+                UnifyInfo0 = deconstruct(A, Functor, F, G, _)
+        ->
+                Result = yes(Functor),
+                        % The deconstruction unification now becomes
+                        % deterministic, since the test will get
+                        % carried out in the switch.
+                UnifyInfo = deconstruct(A, Functor, F, G,
+                        cannot_fail),
+                Goals = [unify(A, B, C, UnifyInfo, E) - GoalInfo]
+        ;
+                error("find_bind_var_for_switch_in_deconstruct")
+        ).
+
+%-----------------------------------------------------------------------------%
+
+find_bind_var(Var, ProcessUnify, Goal0, Goal,
+                Result0, Result, Info0, Info) :-
+        map__init(Substitution),
+        find_bind_var(Var, ProcessUnify, Goal0, Goal, Substitution,
+                _, Result0, Result, Info0, Info, _).
+
+:- pred find_bind_var(var, process_unify(Result, Info), hlds_goal, hlds_goal,
+        substitution, 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.
 
-find_bind_var_for_switch(Goal0 - GoalInfo, Substitution0, Var,
-                Goal - GoalInfo, Substitution, MaybeFunctor) :-
+find_bind_var(Var, ProcessUnify, Goal0 - GoalInfo, Goal, Substitution0,
+                Substitution, Result0, Result, Info0, Info, Continue) :-
         ( Goal0 = some(Vars, SubGoal0) ->
-                find_bind_var_for_switch(SubGoal0, Substitution0, Var,
-                        SubGoal, Substitution, MaybeFunctor),
-                Goal = some(Vars, SubGoal)
+                find_bind_var(Var, ProcessUnify, SubGoal0, SubGoal,
+                        Substitution0, Substitution, Result0, Result,
+                        Info0, Info, Continue),
+                Goal = some(Vars, SubGoal) - GoalInfo
         ; Goal0 = conj(SubGoals0) ->
-                conj_find_bind_var_for_switch(SubGoals0, Substitution0, Var,
-                        SubGoals, Substitution, MaybeFunctor),
-                Goal = conj(SubGoals)
-        ; Goal0 = unify(A, B, C, UnifyInfo0, E) ->
+                conj_find_bind_var(Var, ProcessUnify, SubGoals0, SubGoals,
+                        Substitution0, Substitution, Result0, Result,
+                        Info0, Info, Continue),
+                Goal = conj(SubGoals) - GoalInfo
+        ; Goal0 = unify(A, B, _, UnifyInfo0, _) ->
+                (
                         % check whether the unification is a deconstruction
                         % unification on Var or a variable aliased to Var
-                (
-                        UnifyInfo0 = deconstruct(UnifyVar, Functor, F, G, _),
+                        UnifyInfo0 = deconstruct(UnifyVar, _, _, _, _),
                         term__apply_rec_substitution(term__variable(Var),
                                 Substitution0, term__variable(Var1)),
                         term__apply_rec_substitution(term__variable(UnifyVar),
                                 Substitution0, term__variable(UnifyVar1)),
                         Var1 = UnifyVar1
                 ->
-                        MaybeFunctor = yes(Functor),
-                                % The deconstruction unification now becomes
-                                % deterministic, since the test will get
-                                % carried out in the switch.
-                        UnifyInfo = deconstruct(UnifyVar, Functor, F, G,
-                                cannot_fail),
-                        Goal = unify(A, B, C, UnifyInfo, E),
+                        call(ProcessUnify, Var, Goal0 - GoalInfo, Goals,
+                                Result0, Result, Info0, Info),
+                        conj_list_to_goal(Goals, GoalInfo, Goal),
+                        Continue = no,
                         Substitution = Substitution0
                 ;
+                        Goal = Goal0 - GoalInfo,
+                        Continue = yes,
                         % otherwise abstractly interpret the unification
-                        MaybeFunctor = no,
-                        Goal = Goal0,
+                        Result = Result0,
+                        Info = Info0,
                         ( interpret_unify(A, B, Substitution0, Substitution1) ->
                                 Substitution = Substitution1
                         ;
@@ -463,29 +501,40 @@
                         )
                 )
         ;
-                Goal = Goal0,
+                Goal = Goal0 - GoalInfo,
                 Substitution = Substitution0,
-                MaybeFunctor = no
+                Result = Result0,
+                Info = Info0,
+                Continue = yes
         ).
 
-:- pred conj_find_bind_var_for_switch(list(hlds_goal), substitution, var,
-        list(hlds_goal), substitution, maybe(cons_id)).
-:- mode conj_find_bind_var_for_switch(in, in, in, out, out, out) is det.
-
-conj_find_bind_var_for_switch([], Substitution, _Var, [], Substitution, no).
-conj_find_bind_var_for_switch([Goal0 | Goals0], Substitution0, Var,
-                [Goal | Goals], Substitution, MaybeFunctor) :-
-        find_bind_var_for_switch(Goal0,
-                Substitution0, Var,
-                Goal, Substitution1, MaybeFunctor1),
-        ( MaybeFunctor1 = yes(_) ->
+:- pred conj_find_bind_var(var, process_unify(Result, Info), 
+        list(hlds_goal), list(hlds_goal), substitution, 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.
+
+conj_find_bind_var(_Var, _, [], [], Substitution, Substitution,
+                Result, Result, Info, Info, yes).
+conj_find_bind_var(Var, ProcessUnify, [Goal0 | Goals0], [Goal | Goals],
+                Substitution0, Substitution, Result0, Result,
+                Info0, Info, Continue) :-
+        find_bind_var(Var, ProcessUnify, Goal0, Goal, Substitution0,
+                Substitution1, Result0, Result1,
+                Info0, Info1, Continue1),
+        ( Continue1 = no ->
+                Continue = no,
                 Goals = Goals0,
                 Substitution = Substitution1,
-                MaybeFunctor = MaybeFunctor1
+                Result = Result1,
+                Info = Info1
         ;
-                conj_find_bind_var_for_switch(Goals0, Substitution1, Var,
-                        Goals, Substitution, MaybeFunctor)
+                conj_find_bind_var(Var, ProcessUnify, Goals0, Goals,
+                        Substitution1, Substitution, Result1, Result,
+                        Info1, Info, Continue)
         ).
+
+%-----------------------------------------------------------------------------%
 
 :- pred cases_to_switch(sorted_case_list, var, map(var, type), hlds_goal_info,
         store_map, instmap, module_info, hlds_goal_expr).

%-----------------------------------------------------------------------------%
% Fix a bug where cse_detection wasn't hoisting the common deconstruction
% for a one-arm switch on argument 2 of display_diff_side_by_side_2.
% The symptom was a determinism error.
:- module switch_detection_bug2.

:- interface.
:- import_module io, int, list, string, std_util.

%-----------------------------------------------------------------------------%

:- type pos == int.

:- type segment == pair(pos,pos).

:- type edit --->
		add(pos,segment)
	;	delete(segment,pos)
	;	change(segment,segment).

:- type diff == list(edit).


:- pred display_diff_side_by_side_2(int, side_by_side_info, diff,
		io__state, io__state).
:- mode display_diff_side_by_side_2(in, in, in, di, uo) is det.

%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%

:- implementation.
:- import_module require, std_util, int, list, char, string, bool.

%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%

	% Parameters to pass around.
:- type side_by_side_info
	--->	side_by_side_info(
			int,		% Half width
			int,		% Column 2 offset
			bool,		% Left column only
			bool,		% Suppress common lines
			bool		% Help sdiff
	).

display_diff_side_by_side_2(_Prev, SBS, []) -->
	{ SBS = side_by_side_info(_, _, _, Suppress, _) },
	( { Suppress = no } ->
		[]
	;
		[]
	).
display_diff_side_by_side_2(Prev, SBS, [Edit | Diff]) -->
	{ first_mentioned_positions(Edit, _, _) },
	{ SBS = side_by_side_info(_, _, _, Suppress, _) },
	( { Suppress = no } ->
		[]
	;
		[]
	),
	display_diff_side_by_side_2(Prev, SBS, Diff).

:- pred first_mentioned_positions(edit :: in, pos :: out, pos :: out) is det.
:- external(first_mentioned_positions/3).

%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%




More information about the developers mailing list