[m-rev.] for review: Fix lookup switches on subtype enums.
Peter Wang
novalazy at gmail.com
Thu Apr 8 17:31:08 AEST 2021
compiler/switch_util.m:
Rename dont_need_bit_vec_check variant of need_bit_vec_check to
dont_need_bit_vec_check_no_gaps.
Add dont_need_bit_vec_check_with_gaps (see below).
Make type_range return the correct min and max values used by a
subtype enum type. For now, it fails unless the range of values
is contiguous.
Make find_int_lookup_switch_params use the min and max values for a
type returned by type_range, not assuming 0 to the max value.
Make find_int_lookup_switch_params return
dont_need_bit_vec_check_with_gaps when a bit vector check is not
required before a table lookup, yet the table is expected to contain
dummy rows. This is the case for a cannot_fail switch on a subtype
enum type type, where the subtype does not use some values between
the min and max values.
compiler/dense_switch.m:
Make tagged_case_list_is_dense_switch use the min and max values for
a type returned by type_range, not assuming 0 to the max value.
compiler/ml_lookup_switch.m:
Expect generated lookup table to contain dummy rows or not
depending on on dont_need_bit_vec_check_{with_gaps,no_gaps}.
Conform to change to need_bit_vec_check.
compiler/lookup_switch.m:
compiler/ml_string_switch.m:
Conform to change to need_bit_vec_check.
tests/hard_coded/Mmakefile:
tests/hard_coded/dense_lookup_switch4.exp:
tests/hard_coded/dense_lookup_switch4.m:
tests/hard_coded/dense_lookup_switch_non2.exp:
tests/hard_coded/dense_lookup_switch_non2.m:
Add test cases.
diff --git a/compiler/dense_switch.m b/compiler/dense_switch.m
index c321b4754..75bb516e9 100644
--- a/compiler/dense_switch.m
+++ b/compiler/dense_switch.m
@@ -100,14 +100,14 @@ tagged_case_list_is_dense_switch(CI, VarType, TaggedCases,
get_module_info(CI, ModuleInfo),
classify_type(ModuleInfo, VarType) = TypeCategory,
( if
- type_range(ModuleInfo, TypeCategory, VarType, _Min, _Max,
- TypeRange),
+ type_range(ModuleInfo, TypeCategory, VarType,
+ TypeMin, TypeMax, TypeRange),
DetDensity = switch_density(NumValues, TypeRange),
DetDensity > ReqDensity
then
CanFail = cannot_fail,
- FirstVal = 0,
- LastVal = TypeRange - 1
+ FirstVal = TypeMin,
+ LastVal = TypeMax
else
CanFail = CanFail0,
FirstVal = LowerLimit,
diff --git a/compiler/lookup_switch.m b/compiler/lookup_switch.m
index 1231cfe49..4f14acf7d 100644
--- a/compiler/lookup_switch.m
+++ b/compiler/lookup_switch.m
@@ -400,7 +400,9 @@ generate_simple_int_lookup_switch(IndexRval, StoreMap, StartVal, EndVal,
generate_bitvec_test(IndexRval, CaseValues, StartVal, EndVal,
CheckBitVecCode, !CI, !CLD)
;
- NeedBitVecCheck = dont_need_bit_vec_check,
+ ( NeedBitVecCheck = dont_need_bit_vec_check_no_gaps
+ ; NeedBitVecCheck = dont_need_bit_vec_check_with_gaps
+ ),
CheckBitVecCode = empty
),
diff --git a/compiler/ml_lookup_switch.m b/compiler/ml_lookup_switch.m
index 20e030281..3aab8da6e 100644
--- a/compiler/ml_lookup_switch.m
+++ b/compiler/ml_lookup_switch.m
@@ -334,8 +334,14 @@ ml_gen_simple_atomic_lookup_switch(IndexRval, OutVars, OutTypes, CaseValues,
CodeModel = model_det,
expect(unify(NeedRangeCheck, dont_need_range_check), $pred,
"model_det need_range_check"),
- expect(unify(NeedBitVecCheck, dont_need_bit_vec_check), $pred,
- "model_det need_bit_vec_check"),
+ (
+ NeedBitVecCheck = need_bit_vec_check,
+ unexpected($pred, "model_det need_bit_vec_check")
+ ;
+ ( NeedBitVecCheck = dont_need_bit_vec_check_no_gaps
+ ; NeedBitVecCheck = dont_need_bit_vec_check_with_gaps
+ )
+ ),
Stmt = ml_stmt_block([], [], LookupStmts, Context)
;
CodeModel = model_semi,
@@ -346,7 +352,9 @@ ml_gen_simple_atomic_lookup_switch(IndexRval, OutVars, OutTypes, CaseValues,
(
NeedRangeCheck = dont_need_range_check,
(
- NeedBitVecCheck = dont_need_bit_vec_check,
+ ( NeedBitVecCheck = dont_need_bit_vec_check_no_gaps
+ ; NeedBitVecCheck = dont_need_bit_vec_check_with_gaps
+ ),
Stmt = LookupSucceedStmt
;
NeedBitVecCheck = need_bit_vec_check,
@@ -367,7 +375,9 @@ ml_gen_simple_atomic_lookup_switch(IndexRval, OutVars, OutTypes, CaseValues,
ml_gen_set_success(ml_const(mlconst_false), Context,
SetSuccessFalseStmt, !Info),
(
- NeedBitVecCheck = dont_need_bit_vec_check,
+ ( NeedBitVecCheck = dont_need_bit_vec_check_no_gaps
+ ; NeedBitVecCheck = dont_need_bit_vec_check_with_gaps
+ ),
RangeCheckSuccessStmt = LookupSucceedStmt
;
NeedBitVecCheck = need_bit_vec_check,
@@ -442,8 +452,13 @@ ml_gen_several_soln_atomic_lookup_switch(IndexRval, OutVars, OutTypes,
ml_gen_info_set_global_data(GlobalData, !Info),
(
- NeedBitVecCheck = dont_need_bit_vec_check,
- expect(unify(HadDummyRows, no), $pred, "bad dont_need_bit_vec_check")
+ NeedBitVecCheck = dont_need_bit_vec_check_no_gaps,
+ expect(unify(HadDummyRows, no), $pred,
+ "bad dont_need_bit_vec_check_no_gaps")
+ ;
+ NeedBitVecCheck = dont_need_bit_vec_check_with_gaps,
+ expect(unify(HadDummyRows, yes), $pred,
+ "bad dont_need_bit_vec_check_with_gaps")
;
NeedBitVecCheck = need_bit_vec_check,
expect(unify(HadDummyRows, yes), $pred, "bad need_bit_vec_check")
@@ -527,7 +542,9 @@ ml_gen_several_soln_lookup_code(Context, SlotVarRval,
OneOrMoreSolnsStmts = [FirstLookupSucceedStmt, LaterSlotVarAssignStmt,
LimitAssignStmt, MoreSolnsLoopStmt],
(
- NeedBitVecCheck = dont_need_bit_vec_check,
+ ( NeedBitVecCheck = dont_need_bit_vec_check_no_gaps
+ ; NeedBitVecCheck = dont_need_bit_vec_check_with_gaps
+ ),
Stmts = [NumLaterSolnsAssignStmt | OneOrMoreSolnsStmts]
;
NeedBitVecCheck = need_bit_vec_check,
diff --git a/compiler/ml_string_switch.m b/compiler/ml_string_switch.m
index 0c94337ba..542e30635 100644
--- a/compiler/ml_string_switch.m
+++ b/compiler/ml_string_switch.m
@@ -355,7 +355,8 @@ ml_generate_string_trie_several_soln_lookup_switch(MaxCaseNum,
OutVars, OutTypes, FirstSolnStructType, LaterSolnStructType,
NumLaterSolnsFieldId, FirstLaterSolnRowFieldId,
FirstSolnOutFieldIds, LaterSolnOutFieldIds,
- FirstSolnVectorCommon, LaterSolnVectorCommon, dont_need_bit_vec_check,
+ FirstSolnVectorCommon, LaterSolnVectorCommon,
+ dont_need_bit_vec_check_no_gaps,
MatchDefns, SuccessStmts, !Info),
SuccessBlockStmt = ml_stmt_block(MatchDefns, [], SuccessStmts, Context),
(
@@ -1289,7 +1290,8 @@ ml_generate_string_hash_several_soln_lookup_switch(VarRval, CaseSolns,
FirstSolnStructType, LaterSolnStructType,
NumLaterSolnsFieldId, FirstLaterSolnRowFieldId,
FirstSolnOutFieldIds, LaterSolnOutFieldIds,
- FirstSolnVectorCommon, LaterSolnVectorCommon, dont_need_bit_vec_check,
+ FirstSolnVectorCommon, LaterSolnVectorCommon,
+ dont_need_bit_vec_check_no_gaps,
MatchDefns, SuccessStmts, !Info),
InitialComment = "hashed string several_soln lookup switch",
@@ -1868,7 +1870,8 @@ ml_generate_string_binary_several_soln_lookup_switch(VarRval, CaseSolns0,
FirstSolnStructType, LaterSolnStructType,
NumLaterSolnsFieldId, FirstLaterSolnRowFieldId,
FirstSolnOutFieldIds, LaterSolnOutFieldIds,
- FirstSolnVectorCommon, LaterSolnVectorCommon, dont_need_bit_vec_check,
+ FirstSolnVectorCommon, LaterSolnVectorCommon,
+ dont_need_bit_vec_check_no_gaps,
MatchDefns, SuccessStmts, !Info),
% Generate the code that searches the table.
diff --git a/compiler/switch_util.m b/compiler/switch_util.m
index 720fc9241..85cb53cb8 100644
--- a/compiler/switch_util.m
+++ b/compiler/switch_util.m
@@ -176,7 +176,8 @@
:- type need_bit_vec_check
---> need_bit_vec_check
- ; dont_need_bit_vec_check.
+ ; dont_need_bit_vec_check_no_gaps
+ ; dont_need_bit_vec_check_with_gaps.
:- pred filter_out_failing_cases_if_needed(code_model::in,
list(tagged_case)::in, list(tagged_case)::out,
@@ -401,6 +402,7 @@
:- import_module io.
:- import_module maybe.
:- import_module one_or_more.
+:- import_module ranges.
:- import_module require.
:- import_module string.
:- import_module uint.
@@ -926,18 +928,36 @@ type_range(ModuleInfo, TypeCtorCat, Type, Min, Max, NumValues) :-
target_char_range(Target, Min, Max)
;
TypeCtorCat = ctor_cat_enum(cat_enum_mercury),
- Min = 0,
type_to_ctor_det(Type, TypeCtor),
module_info_get_type_table(ModuleInfo, TypeTable),
lookup_type_ctor_defn(TypeTable, TypeCtor, TypeDefn),
hlds_data.get_type_defn_body(TypeDefn, TypeBody),
(
- TypeBody = hlds_du_type(Constructors, _, _, _, _),
- Constructors = one_or_more(_HeadCtor, TailCtors),
- list.length(TailCtors, NumTailConstructors),
- % NumConstructors = 1 + NumTailConstructors
- % Max = NumConstructors - 1
- Max = NumTailConstructors
+ TypeBody = hlds_du_type(OoMCtors, MaybeSuperType, _, MaybeRepn, _),
+ (
+ MaybeRepn = yes(Repn)
+ ;
+ MaybeRepn = no,
+ unexpected($pred, "MaybeRepn = no")
+ ),
+ (
+ MaybeSuperType = no,
+ Min = 0,
+ OoMCtors = one_or_more(_HeadCtor, TailCtors),
+ list.length(TailCtors, NumTailConstructors),
+ % NumConstructors = 1 + NumTailConstructors
+ % Max = NumConstructors - 1
+ Max = NumTailConstructors
+ ;
+ MaybeSuperType = yes(_),
+ % A subtype enum does not necessarily use all values from 0 to
+ % the max.
+ CtorRepns = Repn ^ dur_ctor_repns,
+ Ranges0 = ranges.empty,
+ list.foldl(insert_enum_cons_tag, CtorRepns, Ranges0, Ranges),
+ % XXX SUBTYPE make callers not expect one contiguous range
+ ranges.is_contiguous(Ranges, Min, Max)
+ )
;
( TypeBody = hlds_eqv_type(_)
; TypeBody = hlds_foreign_type(_)
@@ -949,6 +969,14 @@ type_range(ModuleInfo, TypeCtorCat, Type, Min, Max, NumValues) :-
),
NumValues = Max - Min + 1.
+:- pred insert_enum_cons_tag(constructor_repn::in, ranges::in, ranges::out)
+ is det.
+
+insert_enum_cons_tag(CtorRepn, !Ranges) :-
+ ConsTag = CtorRepn ^ cr_tag,
+ get_int_tag(ConsTag, Int),
+ ranges.insert(Int, !Ranges).
+
switch_density(NumCases, Range) = Density :-
Density = (NumCases * 100) // Range.
@@ -1016,20 +1044,20 @@ find_int_lookup_switch_params(ModuleInfo, SwitchVarType, SwitchCanFail,
% won't need a bitvector test to see if this switch has a value
% for this case.
( if NumValues = Range then
- NeedBitVecCheck0 = dont_need_bit_vec_check
+ NeedBitVecCheck0 = dont_need_bit_vec_check_no_gaps
else
NeedBitVecCheck0 = need_bit_vec_check
),
( if
- type_range(ModuleInfo, TypeCategory, SwitchVarType, _, _,
- TypeRange),
+ type_range(ModuleInfo, TypeCategory, SwitchVarType,
+ TypeMin, TypeMax, TypeRange),
DetDensity = switch_density(NumValues, TypeRange),
DetDensity > ReqDensity
then
NeedRangeCheck = dont_need_range_check,
NeedBitVecCheck = need_bit_vec_check,
- FirstVal = 0,
- LastVal = TypeRange - 1
+ FirstVal = TypeMin,
+ LastVal = TypeMax
else
NeedRangeCheck = need_range_check,
NeedBitVecCheck = NeedBitVecCheck0,
@@ -1038,11 +1066,17 @@ find_int_lookup_switch_params(ModuleInfo, SwitchVarType, SwitchCanFail,
)
;
SwitchCanFail = cannot_fail,
- % Even if NumValues \= Range, the cannot_fail guarantees that
- % the values that are in range but are not covered by any of the cases
- % won't actually be reached.
+ % The cannot_fail guarantees that the values that are in range
+ % but are not covered by any of the cases won't actually be reached.
NeedRangeCheck = dont_need_range_check,
- NeedBitVecCheck = dont_need_bit_vec_check,
+ % There may be gaps in the lookup table if switching on a variable of
+ % a subtype which does not use some values between the min and max
+ % values.
+ ( if NumValues = Range then
+ NeedBitVecCheck = dont_need_bit_vec_check_no_gaps
+ else
+ NeedBitVecCheck = dont_need_bit_vec_check_with_gaps
+ ),
FirstVal = LowerLimit,
LastVal = UpperLimit
).
diff --git a/tests/hard_coded/Mmakefile b/tests/hard_coded/Mmakefile
index a925da9d3..c0ac6f7ae 100644
--- a/tests/hard_coded/Mmakefile
+++ b/tests/hard_coded/Mmakefile
@@ -91,7 +91,9 @@ ORDINARY_PROGS = \
dense_lookup_switch \
dense_lookup_switch2 \
dense_lookup_switch3 \
+ dense_lookup_switch4 \
dense_lookup_switch_non \
+ dense_lookup_switch_non2 \
det_in_semidet_cntxt \
dir_fold \
direct_arg_partial_inst \
diff --git a/tests/hard_coded/dense_lookup_switch4.exp b/tests/hard_coded/dense_lookup_switch4.exp
new file mode 100644
index 000000000..77cd445f2
--- /dev/null
+++ b/tests/hard_coded/dense_lookup_switch4.exp
@@ -0,0 +1,7 @@
+b: 2 -
+c: 3 c
+d: 4 d
+e: 5 -
+f: 6 f
+g: 7 g
+h: 8 -
diff --git a/tests/hard_coded/dense_lookup_switch4.m b/tests/hard_coded/dense_lookup_switch4.m
new file mode 100644
index 000000000..ee350981b
--- /dev/null
+++ b/tests/hard_coded/dense_lookup_switch4.m
@@ -0,0 +1,62 @@
+%---------------------------------------------------------------------------%
+% vim: ts=4 sw=4 et ft=mercury
+%---------------------------------------------------------------------------%
+%
+:- module dense_lookup_switch4.
+
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+:- implementation.
+
+:- import_module char.
+:- import_module list.
+
+:- type foo
+ ---> a ; b ; c ; d ; e ; f ; g ; h ; i ; j.
+
+:- type bar =< foo
+ ---> g ; c ; e ; f ; b ; d ; h.
+ % One contiguous range, deliberately misordered.
+
+main(!IO) :-
+ Xs = [b, c, d, e, f, g, h],
+ list.foldl(test, Xs, !IO).
+
+:- pred test(bar::in, io::di, io::uo) is det.
+
+test(Bar, !IO) :-
+ io.write(Bar, !IO),
+ io.write_string(": ", !IO),
+ p1(Bar, Int),
+ io.write_int(Int, !IO),
+ io.write_string(" ", !IO),
+ ( if p2(Bar, Char) then
+ io.write_char(Char, !IO)
+ else
+ io.write_string("-", !IO)
+ ),
+ io.nl(!IO).
+
+:- pred p1(bar::in, int::out) is det.
+
+p1(b, 2).
+p1(c, 3).
+p1(d, 4).
+p1(e, 5).
+p1(f, 6).
+p1(g, 7).
+p1(h, 8).
+
+:- pred p2(bar::in, char::out) is semidet.
+
+% p2(b, 'b').
+p2(c, 'c').
+p2(d, 'd').
+% p2(e, 'e').
+p2(f, 'f').
+p2(g, 'g').
+% p2(h, 'h').
diff --git a/tests/hard_coded/dense_lookup_switch_non2.exp b/tests/hard_coded/dense_lookup_switch_non2.exp
new file mode 100644
index 000000000..4d3fe7e09
--- /dev/null
+++ b/tests/hard_coded/dense_lookup_switch_non2.exp
@@ -0,0 +1,68 @@
+p1 a ->
+p1_one f1 1.1
+end
+
+p1 b ->
+p1_two f2 2.2
+end
+
+p1 c ->
+p1_three f1 3.3
+end
+
+p1 d ->
+p1_four f1 4.4
+end
+
+p1 e ->
+p1_five f2 5.5
+p1_five2 f3(5) 55.5
+end
+
+p1 f ->
+p1_six f4("hex") 6.6
+end
+
+p1 g ->
+p1_seven f5(77.7) 7.7
+p1_seven2 f1 777.7
+p1_seven3 f2 7777.7
+end
+
+p1 h ->
+p1_eight f1 8.0
+end
+
+p2 a ->
+p2_one f1 1.1
+end
+
+p2 b ->
+end
+
+p2 c ->
+p2_three f1 3.3
+end
+
+p2 d ->
+p2_four f1 4.4
+end
+
+p2 e ->
+p2_five f2 5.5
+p2_five2 f3(5) 55.5
+end
+
+p2 f ->
+p2_six f4("hex") 6.6
+end
+
+p2 g ->
+p2_seven f5(77.7) 7.7
+p2_seven2 f1 777.7
+p2_seven3 f2 7777.7
+end
+
+p2 h ->
+end
+
diff --git a/tests/hard_coded/dense_lookup_switch_non2.m b/tests/hard_coded/dense_lookup_switch_non2.m
new file mode 100644
index 000000000..0538bdc75
--- /dev/null
+++ b/tests/hard_coded/dense_lookup_switch_non2.m
@@ -0,0 +1,141 @@
+% vim: ts=4 sw=4 et ft=mercury
+
+:- module dense_lookup_switch_non2.
+
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+:- implementation.
+
+:- import_module solutions.
+
+:- type base_foo
+ ---> base_only_1
+ ; a
+ ; b
+ ; c
+ ; d
+ ; base_only_2
+ ; e
+ ; f
+ ; g
+ ; h
+ ; base_only_3.
+
+:- type foo =< base_foo
+ ---> a
+ ; b
+ ; c
+ ; d
+ ; e
+ ; f
+ ; g
+ ; h.
+
+:- type test_id
+ ---> test_p1(foo)
+ ; test_p2(foo).
+
+:- type bar
+ ---> f1
+ ; f2
+ ; f3(int)
+ ; f4(string)
+ ; f5(float).
+
+main(!IO) :-
+ test(test_p1(a), !IO),
+ test(test_p1(b), !IO),
+ test(test_p1(c), !IO),
+ test(test_p1(d), !IO),
+ test(test_p1(e), !IO),
+ test(test_p1(f), !IO),
+ test(test_p1(g), !IO),
+ test(test_p1(h), !IO),
+
+ test(test_p2(a), !IO),
+ test(test_p2(b), !IO),
+ test(test_p2(c), !IO),
+ test(test_p2(d), !IO),
+ test(test_p2(e), !IO),
+ test(test_p2(f), !IO),
+ test(test_p2(g), !IO),
+ test(test_p2(h), !IO).
+
+:- pred test(test_id::in, io::di, io::uo) is det.
+
+test(FooOrInt, !IO) :-
+ solutions(p_tuple(FooOrInt), Solns),
+ (
+ FooOrInt = test_p1(Foo),
+ io.write_string("p1 ", !IO),
+ io.write(Foo, !IO)
+ ;
+ FooOrInt = test_p2(Foo),
+ io.write_string("p2 ", !IO),
+ io.write(Foo, !IO)
+ ),
+ io.write_string(" ->\n", !IO),
+ io.write_list(Solns, "", write_tp, !IO),
+ io.write_string("end\n\n", !IO).
+
+:- type tp
+ ---> tp(string, bar, float).
+
+:- pred write_tp(tp::in, io::di, io::uo) is det.
+
+write_tp(tp(Str, Bar, Float), !IO) :-
+ io.write_string(Str, !IO),
+ io.write_string(" ", !IO),
+ io.write(Bar, !IO),
+ io.write_string(" ", !IO),
+ io.write_float(Float, !IO),
+ io.nl(!IO).
+
+:- pred p_tuple(test_id::in, tp::out) is nondet.
+
+p_tuple(FooOrInt, Tuple) :-
+ (
+ FooOrInt = test_p1(Foo),
+ p1(Foo, Str, Bar, Float)
+ ;
+ FooOrInt = test_p2(Foo),
+ p2(Foo, Str, Bar, Float)
+ ),
+ Tuple = tp(Str, Bar, Float).
+
+:- pred p1(foo::in, string::out, bar::out, float::out) is multi.
+:- pragma no_inline(p1/4).
+
+% This predicate needs neither range check nor bitvec check.
+p1(a, "p1_one", f1, 1.1).
+p1(b, "p1_two", f2, 2.2).
+p1(c, "p1_three", f1, 3.3).
+p1(d, "p1_four", f1, 4.4).
+p1(e, "p1_five", f2, 5.5).
+p1(e, "p1_five2", f3(5), 55.5).
+p1(f, "p1_six", f4("hex"), 6.6).
+p1(g, "p1_seven", f5(77.7), 7.7).
+p1(g, "p1_seven2", f1, 777.7).
+p1(g, "p1_seven3", f2, 7777.7).
+p1(h, "p1_eight", f1, 8.0).
+
+:- pred p2(foo::in, string::out, bar::out, float::out) is nondet.
+:- pragma no_inline(p2/4).
+
+% This predicate needs a bitvec check but not a range check.
+% XXX SUBTYPE But a range check will be be generated because the presence of
+% base_only_2 breaks the values of foo into two ranges, and currently
+% type_range will only succeed of a single contiguous range.
+p2(a, "p2_one", f1, 1.1).
+p2(c, "p2_three", f1, 3.3).
+p2(d, "p2_four", f1, 4.4).
+p2(e, "p2_five", f2, 5.5).
+p2(e, "p2_five2", f3(5), 55.5).
+p2(f, "p2_six", f4("hex"), 6.6).
+p2(g, "p2_seven", f5(77.7), 7.7).
+p2(g, "p2_seven2", f1, 777.7).
+p2(g, "p2_seven3", f2, 7777.7).
--
2.30.0
More information about the reviews
mailing list