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