[m-rev.] for review: fix bug in higher order specialization

Ian MacLarty maclarty at csse.unimelb.edu.au
Tue Oct 11 17:28:03 AEDT 2011


I'm unsure this is the right fix, but it passes bootcheck, so I'm posting it
for review by anyone familar with higher_order.m.

Branches: main

Fix a bug in higher order specialization where it incorrectly specialized a
call to a variable after a switch if the variable was constructed in the switch
and its value was known in one switch arm, but not the others.

higher_order.m uses a map to track the possible values of higher order
variables.  The map maps variables to either a constant value, or a
'multiple_values' functor to indicate that the variable can contain multiple
values (and is therefore not specializable).  The problem was there was
some confusion about what it meant if a variable did not appear in this map.

merge_post_branch_infos was expecting the post_branch_info maps it was merging
to contain all the higher order variables in the arms, when in fact it only
contained variables that the goal traversal routines had deemed specializable.
Any entries it found in one post_branch_info but not the other, would be
copied verbatim to the resulting post_branch_info.  This was incorrect, because
if a variable did not occur in one post_branch_info its value might simply be
unknown.

The fix is to remove the multiple_values functor altogether.  A variable now
only appears in the post_branch_info if its value is known and unique.
merge_post_branch_infos has been changed so that it drops variables that
don't appear in both post_branch_infos.

compiler/higher_order.m:
    As above.

    Also remove some comments about the complexity of the
    merge_post_branch_infos algorithm, as the current algorithm is the obvious
    one given the new meaning of the post_branch_infos.

tests/valid/Mercury.options:
tests/valid/Mmakefile:
tests/valid/ho_spec_branch_bug.exp:
tests/valid/ho_spec_branch_bug.m:
    Add a regression test.

Index: compiler/higher_order.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/higher_order.m,v
retrieving revision 1.197
diff -u -r1.197 higher_order.m
--- compiler/higher_order.m	31 Aug 2011 07:59:32 -0000	1.197
+++ compiler/higher_order.m	11 Oct 2011 05:44:13 -0000
@@ -224,7 +224,7 @@
     --->    higher_order_info(
                 hoi_global_info         :: higher_order_global_info,
 
-                % Higher_order variables.
+                % Higher order variables with unique known values.
                 hoi_pred_vars           :: pred_vars,
 
                 % The pred_proc_id, pred_info and proc_info of the procedure
@@ -307,9 +307,9 @@
 :- type goal_sizes == map(pred_id, int).
 
     % Used to hold the value of known higher order variables.
-    % If a variable is not in the map, it does not have a value yet.
+    % If a variable is not in the map, it does not have a unique known value.
     %
-:- type pred_vars == map(prog_var, maybe_const).
+:- type pred_vars == map(prog_var, ho_const).
 
 :- type new_preds == map(pred_proc_id, set(new_pred)).
 
@@ -319,12 +319,8 @@
     % must be constants. For pred_consts and type_infos, non-constant
     % arguments are passed through to any specialised version.
     %
-:- type maybe_const
-    --->    constant(cons_id, list(prog_var))
-                                    % Unique possible value.
-
-    ;       multiple_values.        % Multiple possible values,
-                                    % cannot specialise.
+:- type ho_const
+    --->    constant(cons_id, list(prog_var)).
 
 :- type ho_params
     --->    ho_params(
@@ -768,11 +764,6 @@
 
     % Merge a bunch of post_branch_infos into one.
     %
-    % The algorithm we use has a complexity of N log N, whereas the obvious
-    % algorithm is quadratic. Since N can be very large for predicates defined
-    % lots of facts, this can be the difference between being able to compile
-    % them and having the compiler exhaust available memory in the attempt.
-    %
 :- pred merge_post_branch_infos_into_one(list(post_branch_info)::in,
     post_branch_info::out) is det.
 
@@ -796,16 +787,12 @@
 
     % Merge two post_branch_infos.
     %
-    % The algorithm we use is designed to minimize worst case complexity,
-    % to minimize compilation time for predicates defined by clauses in which
-    % each clause contains lots of variables. This will happen e.g. when the
-    % clause contains some large ground terms.
-    %
-    % We separate out the variables that occur in only one post_branch_info
-    % to avoid having to process them at all, while allowing the variables
-    % occur in both post_branch_infos to be processed using a linear algorithm.
-    % The algorithm here is mostly linear, with an extra log N factor coming in
-    % from the operations on maps.
+    % If a variable appears in one post_branch_info, but not the
+    % other, it is dropped.  Such a variable is either local to
+    % the branch arm, in which case no subsequent specialization
+    % opportunities exist, or it does not have a unique constant
+    % value in one of the branch arms, so we can't specialize it
+    % outside the branch anyway.
     %
 :- pred merge_post_branch_infos(post_branch_info::in,
     post_branch_info::in, post_branch_info::out) is det.
@@ -824,20 +811,13 @@
     map.to_assoc_list(VarConstCommonMapB, VarConstCommonListB),
     merge_common_var_const_list(VarConstCommonListA, VarConstCommonListB,
         [], VarConstCommonList),
-    set.difference(VarsA, CommonVars, OnlyVarsA),
-    set.difference(VarsB, CommonVars, OnlyVarsB),
-    VarConstOnlyMapA = map.select(VarConstMapA, OnlyVarsA),
-    VarConstOnlyMapB = map.select(VarConstMapB, OnlyVarsB),
-    map.to_assoc_list(VarConstOnlyMapA, VarConstOnlyListA),
-    map.to_assoc_list(VarConstOnlyMapB, VarConstOnlyListB),
-    FinalList = VarConstOnlyListA ++ VarConstOnlyListB ++ VarConstCommonList,
-    map.from_assoc_list(FinalList, FinalVarConstMap),
+    map.from_assoc_list(VarConstCommonList, FinalVarConstMap),
     Post = post_branch_info(FinalVarConstMap).
 
-:- pred merge_common_var_const_list(assoc_list(prog_var, maybe_const)::in,
-    assoc_list(prog_var, maybe_const)::in,
-    assoc_list(prog_var, maybe_const)::in,
-    assoc_list(prog_var, maybe_const)::out) is det.
+:- pred merge_common_var_const_list(assoc_list(prog_var, ho_const)::in,
+    assoc_list(prog_var, ho_const)::in,
+    assoc_list(prog_var, ho_const)::in,
+    assoc_list(prog_var, ho_const)::out) is det.
 
 merge_common_var_const_list([], [], !List).
 merge_common_var_const_list([], [_ | _], !MergedList) :-
@@ -848,17 +828,10 @@
         !MergedList) :-
     expect(unify(VarA, VarB), $module, $pred, "var mismatch"),
     ( ValueA = ValueB ->
-        % It does not matter whether ValueA is bound to constant(_, _)
-        % or to multiple_values, in both cases, if ValueA = ValueB, the
-        % right value for Value is ValueA.
-        Value = ValueA
-    ;
-        % Either ValueA and ValueB are both bound to different constants,
-        % or one is constant and the other is multiple_values. In both cases,
-        % the right value for Value is multiple_values.
-        Value = multiple_values
+        !:MergedList = [VarA - ValueA | !.MergedList]
+    ;
+        !:MergedList = !.MergedList
     ),
-    !:MergedList = [VarA - Value | !.MergedList],
     merge_common_var_const_list(ListA, ListB, !MergedList).
 
 :- pred check_unify(unification::in,
@@ -881,18 +854,9 @@
         (
             IsInteresting = yes,
             PredVars0 = !.Info ^ hoi_pred_vars,
-            ( map.search(PredVars0, LVar, Specializable) ->
-                (
-                    % We cannot specialize calls involving a variable with
-                    % more than one possible value.
-                    Specializable = constant(_, _),
-                    map.det_update(LVar, multiple_values, PredVars0, PredVars),
-                    !Info ^ hoi_pred_vars := PredVars
-                ;
-                    % If a variable is already non-specializable, it can't
-                    % become specializable.
-                    Specializable = multiple_values
-                )
+            ( map.search(PredVars0, LVar, _) ->
+                % A variable cannot be constructed twice.
+                unexpected($module, $pred, "variable constructed twice")
             ;
                 map.det_insert(LVar, constant(ConsId, Args),
                     PredVars0, PredVars),
Index: tests/valid/Mercury.options
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/valid/Mercury.options,v
retrieving revision 1.74
diff -u -r1.74 Mercury.options
--- tests/valid/Mercury.options	9 May 2011 03:24:39 -0000	1.74
+++ tests/valid/Mercury.options	11 Oct 2011 05:44:16 -0000
@@ -66,6 +66,7 @@
 MCFLAGS-higher_order_implied_mode = -O-1
 MCFLAGS-ho_and_type_spec_bug = -O4
 MCFLAGS-ho_and_type_spec_bug2 = -O3 --no-inlining
+MCFLAGS-ho_spec_branch_bug      = --optimize-higher-order
 MCFLAGS-impure_detism           = -O5 --deep-profiling --no-intermodule-optimization
 MCFLAGS-inhibit_warn_test       = --inhibit-warnings --halt-at-warn
 MCFLAGS-instmap_generic_failure	= --local-constraint-propagation
Index: tests/valid/Mmakefile
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/valid/Mmakefile,v
retrieving revision 1.248
diff -u -r1.248 Mmakefile
--- tests/valid/Mmakefile	9 May 2011 03:24:39 -0000	1.248
+++ tests/valid/Mmakefile	11 Oct 2011 05:44:16 -0000
@@ -127,6 +127,7 @@
 	ho_and_type_spec_bug2 \
 	ho_func_call \
 	ho_inst \
+	ho_spec_branch_bug \
 	ho_unify \
 	id_type_bug \
 	implied_mode \
Index: tests/valid/ho_spec_branch_bug.exp
===================================================================
RCS file: tests/valid/ho_spec_branch_bug.exp
diff -N tests/valid/ho_spec_branch_bug.exp
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/valid/ho_spec_branch_bug.exp	11 Oct 2011 05:44:16 -0000
@@ -0,0 +1 @@
+ho2
Index: tests/valid/ho_spec_branch_bug.m
===================================================================
RCS file: tests/valid/ho_spec_branch_bug.m
diff -N tests/valid/ho_spec_branch_bug.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/valid/ho_spec_branch_bug.m	11 Oct 2011 05:44:16 -0000
@@ -0,0 +1,41 @@
+% Regression test for a bug where the compiler would incorrectly specialize
+% the call to P in do_stuff.
+:- module ho_spec_branch_bug.
+
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+:- implementation.
+
+:- import_module maybe.
+
+main(!IO) :-
+    do_stuff(yes(1), !IO).
+
+:- pred ho1(io::di, io::uo) is det.
+
+ho1(!IO) :- io.write_string("ho1\n", !IO).
+
+:- pred ho2(io::di, io::uo) is det.
+
+ho2(!IO) :- io.write_string("ho2\n", !IO).
+
+:- func get_ho2 = (pred(io, io)).
+:- mode get_ho2 = out(pred(di, uo) is det) is det.
+
+get_ho2 = ho2.
+
+:- pred do_stuff(maybe(int)::in, io::di, io::uo) is det.
+
+do_stuff(Maybe, !IO) :-
+    (
+        Maybe = no,
+        P = ho1
+    ;
+        Maybe = yes(_),
+        P = get_ho2
+    ),
+    P(!IO).
Index: compiler/higher_order.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/higher_order.m,v
retrieving revision 1.197
diff -u -r1.197 higher_order.m
--- compiler/higher_order.m	31 Aug 2011 07:59:32 -0000	1.197
+++ compiler/higher_order.m	11 Oct 2011 05:44:13 -0000
@@ -224,7 +224,7 @@
     --->    higher_order_info(
                 hoi_global_info         :: higher_order_global_info,
 
-                % Higher_order variables.
+                % Higher order variables with unique known values.
                 hoi_pred_vars           :: pred_vars,
 
                 % The pred_proc_id, pred_info and proc_info of the procedure
@@ -307,9 +307,9 @@
 :- type goal_sizes == map(pred_id, int).
 
     % Used to hold the value of known higher order variables.
-    % If a variable is not in the map, it does not have a value yet.
+    % If a variable is not in the map, it does not have a unique known value.
     %
-:- type pred_vars == map(prog_var, maybe_const).
+:- type pred_vars == map(prog_var, ho_const).
 
 :- type new_preds == map(pred_proc_id, set(new_pred)).
 
@@ -319,12 +319,8 @@
     % must be constants. For pred_consts and type_infos, non-constant
     % arguments are passed through to any specialised version.
     %
-:- type maybe_const
-    --->    constant(cons_id, list(prog_var))
-                                    % Unique possible value.
-
-    ;       multiple_values.        % Multiple possible values,
-                                    % cannot specialise.
+:- type ho_const
+    --->    constant(cons_id, list(prog_var)).
 
 :- type ho_params
     --->    ho_params(
@@ -768,11 +764,6 @@
 
     % Merge a bunch of post_branch_infos into one.
     %
-    % The algorithm we use has a complexity of N log N, whereas the obvious
-    % algorithm is quadratic. Since N can be very large for predicates defined
-    % lots of facts, this can be the difference between being able to compile
-    % them and having the compiler exhaust available memory in the attempt.
-    %
 :- pred merge_post_branch_infos_into_one(list(post_branch_info)::in,
     post_branch_info::out) is det.
 
@@ -796,16 +787,12 @@
 
     % Merge two post_branch_infos.
     %
-    % The algorithm we use is designed to minimize worst case complexity,
-    % to minimize compilation time for predicates defined by clauses in which
-    % each clause contains lots of variables. This will happen e.g. when the
-    % clause contains some large ground terms.
-    %
-    % We separate out the variables that occur in only one post_branch_info
-    % to avoid having to process them at all, while allowing the variables
-    % occur in both post_branch_infos to be processed using a linear algorithm.
-    % The algorithm here is mostly linear, with an extra log N factor coming in
-    % from the operations on maps.
+    % If a variable appears in one post_branch_info, but not the
+    % other, it is dropped.  Such a variable is either local to
+    % the branch arm, in which case no subsequent specialization
+    % opportunities exist, or it does not have a unique constant
+    % value in one of the branch arms, so we can't specialize it
+    % outside the branch anyway.
     %
 :- pred merge_post_branch_infos(post_branch_info::in,
     post_branch_info::in, post_branch_info::out) is det.
@@ -824,20 +811,13 @@
     map.to_assoc_list(VarConstCommonMapB, VarConstCommonListB),
     merge_common_var_const_list(VarConstCommonListA, VarConstCommonListB,
         [], VarConstCommonList),
-    set.difference(VarsA, CommonVars, OnlyVarsA),
-    set.difference(VarsB, CommonVars, OnlyVarsB),
-    VarConstOnlyMapA = map.select(VarConstMapA, OnlyVarsA),
-    VarConstOnlyMapB = map.select(VarConstMapB, OnlyVarsB),
-    map.to_assoc_list(VarConstOnlyMapA, VarConstOnlyListA),
-    map.to_assoc_list(VarConstOnlyMapB, VarConstOnlyListB),
-    FinalList = VarConstOnlyListA ++ VarConstOnlyListB ++ VarConstCommonList,
-    map.from_assoc_list(FinalList, FinalVarConstMap),
+    map.from_assoc_list(VarConstCommonList, FinalVarConstMap),
     Post = post_branch_info(FinalVarConstMap).
 
-:- pred merge_common_var_const_list(assoc_list(prog_var, maybe_const)::in,
-    assoc_list(prog_var, maybe_const)::in,
-    assoc_list(prog_var, maybe_const)::in,
-    assoc_list(prog_var, maybe_const)::out) is det.
+:- pred merge_common_var_const_list(assoc_list(prog_var, ho_const)::in,
+    assoc_list(prog_var, ho_const)::in,
+    assoc_list(prog_var, ho_const)::in,
+    assoc_list(prog_var, ho_const)::out) is det.
 
 merge_common_var_const_list([], [], !List).
 merge_common_var_const_list([], [_ | _], !MergedList) :-
@@ -848,17 +828,10 @@
         !MergedList) :-
     expect(unify(VarA, VarB), $module, $pred, "var mismatch"),
     ( ValueA = ValueB ->
-        % It does not matter whether ValueA is bound to constant(_, _)
-        % or to multiple_values, in both cases, if ValueA = ValueB, the
-        % right value for Value is ValueA.
-        Value = ValueA
-    ;
-        % Either ValueA and ValueB are both bound to different constants,
-        % or one is constant and the other is multiple_values. In both cases,
-        % the right value for Value is multiple_values.
-        Value = multiple_values
+        !:MergedList = [VarA - ValueA | !.MergedList]
+    ;
+        !:MergedList = !.MergedList
     ),
-    !:MergedList = [VarA - Value | !.MergedList],
     merge_common_var_const_list(ListA, ListB, !MergedList).
 
 :- pred check_unify(unification::in,
@@ -881,18 +854,9 @@
         (
             IsInteresting = yes,
             PredVars0 = !.Info ^ hoi_pred_vars,
-            ( map.search(PredVars0, LVar, Specializable) ->
-                (
-                    % We cannot specialize calls involving a variable with
-                    % more than one possible value.
-                    Specializable = constant(_, _),
-                    map.det_update(LVar, multiple_values, PredVars0, PredVars),
-                    !Info ^ hoi_pred_vars := PredVars
-                ;
-                    % If a variable is already non-specializable, it can't
-                    % become specializable.
-                    Specializable = multiple_values
-                )
+            ( map.search(PredVars0, LVar, _) ->
+                % A variable cannot be constructed twice.
+                unexpected($module, $pred, "variable constructed twice")
             ;
                 map.det_insert(LVar, constant(ConsId, Args),
                     PredVars0, PredVars),
Index: tests/valid/Mercury.options
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/valid/Mercury.options,v
retrieving revision 1.74
diff -u -r1.74 Mercury.options
--- tests/valid/Mercury.options	9 May 2011 03:24:39 -0000	1.74
+++ tests/valid/Mercury.options	11 Oct 2011 05:44:16 -0000
@@ -66,6 +66,7 @@
 MCFLAGS-higher_order_implied_mode = -O-1
 MCFLAGS-ho_and_type_spec_bug = -O4
 MCFLAGS-ho_and_type_spec_bug2 = -O3 --no-inlining
+MCFLAGS-ho_spec_branch_bug      = --optimize-higher-order
 MCFLAGS-impure_detism           = -O5 --deep-profiling --no-intermodule-optimization
 MCFLAGS-inhibit_warn_test       = --inhibit-warnings --halt-at-warn
 MCFLAGS-instmap_generic_failure	= --local-constraint-propagation
Index: tests/valid/Mmakefile
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/valid/Mmakefile,v
retrieving revision 1.248
diff -u -r1.248 Mmakefile
--- tests/valid/Mmakefile	9 May 2011 03:24:39 -0000	1.248
+++ tests/valid/Mmakefile	11 Oct 2011 05:44:16 -0000
@@ -127,6 +127,7 @@
 	ho_and_type_spec_bug2 \
 	ho_func_call \
 	ho_inst \
+	ho_spec_branch_bug \
 	ho_unify \
 	id_type_bug \
 	implied_mode \
Index: tests/valid/ho_spec_branch_bug.exp
===================================================================
RCS file: tests/valid/ho_spec_branch_bug.exp
diff -N tests/valid/ho_spec_branch_bug.exp
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/valid/ho_spec_branch_bug.exp	11 Oct 2011 05:44:16 -0000
@@ -0,0 +1 @@
+ho2
Index: tests/valid/ho_spec_branch_bug.m
===================================================================
RCS file: tests/valid/ho_spec_branch_bug.m
diff -N tests/valid/ho_spec_branch_bug.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/valid/ho_spec_branch_bug.m	11 Oct 2011 05:44:16 -0000
@@ -0,0 +1,41 @@
+% Regression test for a bug where the compiler would incorrectly specialize
+% the call to P in do_stuff.
+:- module ho_spec_branch_bug.
+
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+:- implementation.
+
+:- import_module maybe.
+
+main(!IO) :-
+    do_stuff(yes(1), !IO).
+
+:- pred ho1(io::di, io::uo) is det.
+
+ho1(!IO) :- io.write_string("ho1\n", !IO).
+
+:- pred ho2(io::di, io::uo) is det.
+
+ho2(!IO) :- io.write_string("ho2\n", !IO).
+
+:- func get_ho2 = (pred(io, io)).
+:- mode get_ho2 = out(pred(di, uo) is det) is det.
+
+get_ho2 = ho2.
+
+:- pred do_stuff(maybe(int)::in, io::di, io::uo) is det.
+
+do_stuff(Maybe, !IO) :-
+    (
+        Maybe = no,
+        P = ho1
+    ;
+        Maybe = yes(_),
+        P = get_ho2
+    ),
+    P(!IO).
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------



More information about the reviews mailing list