[m-rev.] for review: Make type_range also succeed for discontiguous range of enum values.
Peter Wang
novalazy at gmail.com
Tue Apr 13 14:41:24 AEST 2021
compiler/switch_util.m:
Make type_range succeed for a subtype where the constructors are
assigned enum values in a discontiguous range. I checked that its
callers do not expect all values in the range to necessarily
be used by the type.
Clarify find_int_lookup_switch_params a bit.
Clarify comments.
compiler/dense_switch.m:
Use need_range_check type instead of can_fail in dense_switch_info,
as that is what the field actually means.
compiler/ml_simplify_switch.m:
Use need_range_check type instead of bool.
tests/hard_coded/dense_lookup_switch_non2.m:
Delete obsoleted XXX.
diff --git a/compiler/dense_switch.m b/compiler/dense_switch.m
index 75bb516e9..3b0633d07 100644
--- a/compiler/dense_switch.m
+++ b/compiler/dense_switch.m
@@ -76,13 +76,13 @@
:- type dense_switch_info
---> dense_switch_info(
- first_value :: int,
- last_value :: int,
- new_can_fail :: can_fail
+ first_value :: int,
+ last_value :: int,
+ need_range_check :: need_range_check
).
tagged_case_list_is_dense_switch(CI, VarType, TaggedCases,
- LowerLimit, UpperLimit, NumValues, ReqDensity, CanFail0,
+ LowerLimit, UpperLimit, NumValues, ReqDensity, CanFail,
DenseSwitchInfo) :-
list.length(TaggedCases, NumCases),
NumCases > 2,
@@ -92,7 +92,7 @@ tagged_case_list_is_dense_switch(CI, VarType, TaggedCases,
Density = switch_density(NumValues, Range),
Density > ReqDensity,
(
- CanFail0 = can_fail,
+ CanFail = can_fail,
% For semidet switches, we normally need to check that the variable
% is in range before we index into the jump table. However, if the
% range of the type is sufficiently small, we can make the jump table
@@ -105,21 +105,21 @@ tagged_case_list_is_dense_switch(CI, VarType, TaggedCases,
DetDensity = switch_density(NumValues, TypeRange),
DetDensity > ReqDensity
then
- CanFail = cannot_fail,
+ NeedRangeCheck = dont_need_range_check,
FirstVal = TypeMin,
LastVal = TypeMax
else
- CanFail = CanFail0,
+ NeedRangeCheck = need_range_check,
FirstVal = LowerLimit,
LastVal = UpperLimit
)
;
- CanFail0 = cannot_fail,
CanFail = cannot_fail,
+ NeedRangeCheck = dont_need_range_check,
FirstVal = LowerLimit,
LastVal = UpperLimit
),
- DenseSwitchInfo = dense_switch_info(FirstVal, LastVal, CanFail).
+ DenseSwitchInfo = dense_switch_info(FirstVal, LastVal, NeedRangeCheck).
%---------------------------------------------------------------------------%
@@ -128,23 +128,23 @@ generate_dense_switch(TaggedCases, VarRval, VarName, CodeModel, SwitchGoalInfo,
% Evaluate the variable which we are going to be switching on.
% If the case values start at some number other than 0,
% then subtract that number to give us a zero-based index.
- DenseSwitchInfo = dense_switch_info(FirstVal, LastVal, CanFail),
+ DenseSwitchInfo = dense_switch_info(FirstVal, LastVal, NeedRangeCheck),
( if FirstVal = 0 then
IndexRval = VarRval
else
IndexRval = binop(int_sub(int_type_int), VarRval,
const(llconst_int(FirstVal)))
),
- % If the switch is not locally deterministic, we need to check that
- % the value of the variable lies within the appropriate range.
+ % Check that the value of the variable lies within the appropriate range
+ % if necessary.
(
- CanFail = can_fail,
+ NeedRangeCheck = need_range_check,
Difference = LastVal - FirstVal,
fail_if_rval_is_false(
binop(unsigned_le, IndexRval, const(llconst_int(Difference))),
RangeCheckCode, !CI, !CLD)
;
- CanFail = cannot_fail,
+ NeedRangeCheck = dont_need_range_check,
RangeCheckCode = empty
),
diff --git a/compiler/ml_simplify_switch.m b/compiler/ml_simplify_switch.m
index ecf8af818..3b0710be9 100644
--- a/compiler/ml_simplify_switch.m
+++ b/compiler/ml_simplify_switch.m
@@ -206,7 +206,7 @@ is_dense_switch(Cases, ReqDensity) :-
%
:- pred maybe_eliminate_default(mlds_switch_range::in,
list(mlds_switch_case)::in, mlds_switch_default::in, int::in,
- int::out, int::out, bool::out) is det.
+ int::out, int::out, need_range_check::out) is det.
maybe_eliminate_default(Range, Cases, Default, ReqDensity,
FirstVal, LastVal, NeedRangeCheck) :-
@@ -218,18 +218,18 @@ maybe_eliminate_default(Range, Cases, Default, ReqDensity,
NoDefaultDensity = switch_density(NumCases, TypeRange),
NoDefaultDensity > ReqDensity
then
- NeedRangeCheck = no,
+ NeedRangeCheck = dont_need_range_check,
FirstVal = Min,
LastVal = Max
else
(
Default = default_is_unreachable,
- NeedRangeCheck = no
+ NeedRangeCheck = dont_need_range_check
;
( Default = default_do_nothing
; Default = default_case(_)
),
- NeedRangeCheck = yes
+ NeedRangeCheck = need_range_check
),
find_min_and_max_in_cases(Cases, FirstCaseVal, LastCaseVal),
FirstVal = FirstCaseVal,
@@ -283,7 +283,7 @@ find_min_and_max_in_case_cond(match_range(MinRval, MaxRval), !Min, !Max) :-
% Generate code for a switch using a dense jump table.
%
:- pred generate_dense_switch(list(mlds_switch_case)::in,
- mlds_switch_default::in, int::in, int::in, bool::in,
+ mlds_switch_default::in, int::in, int::in, need_range_check::in,
mlds_type::in, mlds_rval::in, prog_context::in, list(mlds_stmt)::out,
ml_gen_info::in, ml_gen_info::out) is det.
@@ -329,7 +329,7 @@ generate_dense_switch(Cases, Default, FirstVal, LastVal, NeedRangeCheck,
% We may need to check that the value of the variable lies within the
% appropriate range.
(
- NeedRangeCheck = yes,
+ NeedRangeCheck = need_range_check,
Difference = LastVal - FirstVal,
InRange = ml_binop(unsigned_le,
Index, ml_const(mlconst_int(Difference))),
@@ -338,7 +338,7 @@ generate_dense_switch(Cases, Default, FirstVal, LastVal, NeedRangeCheck,
DoSwitch = ml_stmt_if_then_else(InRange, SwitchBody, Else, Context),
Stmts = [StartComment, DoSwitch, EndLabelStmt, EndComment]
;
- NeedRangeCheck = no,
+ NeedRangeCheck = dont_need_range_check,
Stmts =
[StartComment, DoJump | CasesCode] ++
DefaultStmts ++
diff --git a/compiler/switch_util.m b/compiler/switch_util.m
index 899467f02..5a281d822 100644
--- a/compiler/switch_util.m
+++ b/compiler/switch_util.m
@@ -126,16 +126,20 @@
% Stuff for dense switches.
%
- % type_range(ModuleInfo, TypeCtorCategory, Type, Min, Max, NumValues):
+ % type_range(ModuleInfo, TypeCtorCategory, Type, Min, Max,
+ % NumValuesInRange):
%
% Determine the range [Min..Max] of an atomic type, and the number of
- % values in that range (including both endpoints).
+ % values in that range (including both endpoints). Values within the range
+ % are not necessarily used by the type.
% Fail if the type isn't the sort of type that has a range
% or if the type's range is too big to switch on (e.g. int).
%
:- pred type_range(module_info::in, type_ctor_category::in, mer_type::in,
int::out, int::out, int::out) is semidet.
+ % switch_density(NumCases, NumValuesInRange):
+ %
% Calculate the percentage density given the range and the number of cases.
%
:- func switch_density(int, int) = int.
@@ -406,7 +410,6 @@
:- import_module io.
:- import_module maybe.
:- import_module one_or_more.
-:- import_module ranges.
:- import_module require.
:- import_module string.
:- import_module uint.
@@ -922,7 +925,7 @@ is_smart_indexing_allowed_for_category(Globals, SwitchCategory) = Allowed :-
% Stuff for dense switches.
%
-type_range(ModuleInfo, TypeCtorCat, Type, Min, Max, NumValues) :-
+type_range(ModuleInfo, TypeCtorCat, Type, Min, Max, NumValuesInRange) :-
(
TypeCtorCat = ctor_cat_builtin(cat_builtin_char),
% Note also that some code in both dense_switch.m and in
@@ -957,10 +960,7 @@ type_range(ModuleInfo, TypeCtorCat, Type, Min, Max, NumValues) :-
% 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)
+ ctor_repns_int_tag_range(CtorRepns, Min, Max)
)
;
( TypeBody = hlds_eqv_type(_)
@@ -971,18 +971,27 @@ type_range(ModuleInfo, TypeCtorCat, Type, Min, Max, NumValues) :-
unexpected($pred, "enum type is not d.u. type?")
)
),
- NumValues = Max - Min + 1.
+ NumValuesInRange = Max - Min + 1.
-:- pred insert_enum_cons_tag(constructor_repn::in, ranges::in, ranges::out)
- is det.
+:- pred ctor_repns_int_tag_range(list(constructor_repn)::in,
+ int::out, int::out) is semidet.
+
+ctor_repns_int_tag_range([CtorRepn | CtorRepns], Min, Max) :-
+ ConsTag = CtorRepn ^ cr_tag,
+ get_int_tag(ConsTag, Int),
+ list.foldl2(extend_ctor_repn_int_tag_range, CtorRepns, Int, Min, Int, Max).
+
+:- pred extend_ctor_repn_int_tag_range(constructor_repn::in,
+ int::in, int::out, int::in, int::out) is det.
-insert_enum_cons_tag(CtorRepn, !Ranges) :-
+extend_ctor_repn_int_tag_range(CtorRepn, !Min, !Max) :-
ConsTag = CtorRepn ^ cr_tag,
get_int_tag(ConsTag, Int),
- ranges.insert(Int, !Ranges).
+ int.min(Int, !Min),
+ int.max(Int, !Max).
-switch_density(NumCases, Range) = Density :-
- Density = (NumCases * 100) // Range.
+switch_density(NumCases, NumValuesInRange) = Density :-
+ Density = (NumCases * 100) // NumValuesInRange.
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
@@ -1041,17 +1050,9 @@ find_int_lookup_switch_params(ModuleInfo, SwitchVarType, SwitchCanFail,
% For can_fail switches, we normally need to check that the variable
% is in range before we index into the jump table. However, if the
% range of the type is sufficiently small, we can make the jump table
- % large enough to hold all of the values for the type, but then we
- % will need to do the bitvector test.
+ % large enough to hold all of the values for the type (with gaps),
+ % but then we will need to do the bitvector test.
classify_type(ModuleInfo, SwitchVarType) = TypeCategory,
- % If there are going to be no gaps in the lookup table, then we
- % 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_no_gaps
- else
- NeedBitVecCheck0 = need_bit_vec_check
- ),
( if
type_range(ModuleInfo, TypeCategory, SwitchVarType,
TypeMin, TypeMax, TypeRange),
@@ -1063,8 +1064,15 @@ find_int_lookup_switch_params(ModuleInfo, SwitchVarType, SwitchCanFail,
FirstVal = TypeMin,
LastVal = TypeMax
else
+ % First check the variable is in range.
NeedRangeCheck = need_range_check,
- NeedBitVecCheck = NeedBitVecCheck0,
+ % We will need to perform the bitvector test if the lookup table
+ % is going to contain any gaps.
+ ( if NumValues = Range then
+ NeedBitVecCheck = dont_need_bit_vec_check_no_gaps
+ else
+ NeedBitVecCheck = need_bit_vec_check
+ ),
FirstVal = LowerLimit,
LastVal = UpperLimit
)
@@ -1074,8 +1082,7 @@ find_int_lookup_switch_params(ModuleInfo, SwitchVarType, SwitchCanFail,
% but are not covered by any of the cases won't actually be reached.
NeedRangeCheck = dont_need_range_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.
+ % a subtype which does not use some values in the range.
( if NumValues = Range then
NeedBitVecCheck = dont_need_bit_vec_check_no_gaps
else
diff --git a/tests/hard_coded/dense_lookup_switch_non2.m b/tests/hard_coded/dense_lookup_switch_non2.m
index 0538bdc75..4cda926cc 100644
--- a/tests/hard_coded/dense_lookup_switch_non2.m
+++ b/tests/hard_coded/dense_lookup_switch_non2.m
@@ -127,9 +127,6 @@ p1(h, "p1_eight", f1, 8.0).
:- 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).
--
2.30.0
More information about the reviews
mailing list