[m-dev.] for review: MLDS switch simplification
Fergus Henderson
fjh at cs.mu.OZ.AU
Sat Nov 18 00:36:00 AEDT 2000
Estimated hours taken: 12
Add an MLDS to MLDS transformation that converts MLDS switches
into computed gotos or if-then-else chains. (Eventually we
should make this code also handle binary searches.)
This transformation should allow tag switch optimization to work for
the IL back-end. It also replaces ml_dense_switch.m and lets us
simplify ml_string_switch.m.
compiler/mlds.m:
Add a new `switch_range' field to the `switch' stmt.
compiler/ml_simplify_switch.m:
The new transformation. This converts MLDS switches into
computed gotos or if-then-else chains.
It uses the new `switch_range' field to determine how big
it would need to make the jump table to cover all cases.
compiler/ml_switch_gen.m:
compiler/ml_string_switch.m:
compiler/ml_tag_switch.m:
compiler/ml_dense_switch.m:
Generate the new field.
Change the places that generate switches so that after
generating the switch they invoke the new transformation.
Delete ml_dense_switch.m, since it is now redundant,
and significantly simplify ml_string_switch.m.
compiler/ml_elim_nested.m:
compiler/ml_optimize.m:
compiler/ml_tailcall.m:
compiler/ml_util.m:
compiler/mlds_to_c.m:
compiler/mlds_to_il.m:
Trivial changes to handle the new field.
compiler/switch_util.m:
compiler/dense_switch.m:
Move most of the code from the `type_range' procedure from
dense_switch.m to switch_util.m, so we can use it in
ml_switch_gen.m for computing the switch range.
Workspace: /home/pgrad/fjh/ws/hg
Index: compiler/dense_switch.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/dense_switch.m,v
retrieving revision 1.37
diff -u -d -r1.37 dense_switch.m
--- compiler/dense_switch.m 2000/11/16 10:48:41 1.37
+++ compiler/dense_switch.m 2000/11/16 10:48:52
@@ -80,7 +80,8 @@
{ classify_type(Type, ModuleInfo, TypeCategory) },
(
dense_switch__type_range(TypeCategory, Type, TypeRange),
- { dense_switch__calc_density(NumCases, TypeRange, DetDensity) },
+ { dense_switch__calc_density(NumCases, TypeRange,
+ DetDensity) },
{ DetDensity > ReqDensity }
->
{ CanFail = cannot_fail },
@@ -112,30 +113,11 @@
% Fail if the type isn't the sort of type that has a range
% or if the type's range is to big to switch on (e.g. int).
-dense_switch__type_range(char_type, _, CharRange) -->
- % XXX the following code uses the host's character size,
- % not the target's, so it won't work if cross-compiling
- % to a machine with a different character size.
- % Note also that the code above in dense_switch.m and the code
- % in lookup_switch.m assume that char__min_char_value is 0.
- { char__max_char_value(MaxChar) },
- { char__min_char_value(MinChar) },
- { CharRange is MaxChar - MinChar + 1 }.
-dense_switch__type_range(enum_type, Type, TypeRange) -->
- { type_to_type_id(Type, TypeId0, _) ->
- TypeId = TypeId0
- ;
- error("dense_switch__type_range: invalid enum type?")
- },
+dense_switch__type_range(TypeCategory, Type, Range) -->
code_info__get_module_info(ModuleInfo),
- { module_info_types(ModuleInfo, TypeTable) },
- { map__lookup(TypeTable, TypeId, TypeDefn) },
- { hlds_data__get_type_defn_body(TypeDefn, TypeBody) },
- { TypeBody = du_type(_, ConsTable, _, _) ->
- map__count(ConsTable, TypeRange)
- ;
- error("dense_switch__type_range: enum type is not d.u. type?")
- }.
+ { switch_util__type_range(TypeCategory, Type, ModuleInfo,
+ Min, Max) },
+ { Range = Max - Min + 1 }.
%---------------------------------------------------------------------------%
Index: compiler/ml_dense_switch.m
===================================================================
RCS file: ml_dense_switch.m
diff -N ml_dense_switch.m
--- /tmp/cvswFY6c9 Sat Nov 18 00:28:04 2000
+++ /dev/null Thu Mar 30 14:06:13 2000
@@ -1,283 +0,0 @@
-%-----------------------------------------------------------------------------%
-% Copyright (C) 1994-2000 The University of Melbourne.
-% This file may only be copied under the terms of the GNU General
-% Public License - see the file COPYING in the Mercury distribution.
-%-----------------------------------------------------------------------------%
-
-% file: ml_dense_switch.m
-% author: fjh
-
-% For switches on atomic types, generate code using a computed_goto
-% dense jump table.
-
-% The code here is quite similar to the code in dense_switch.m.
-
-%-----------------------------------------------------------------------------%
-
-:- module ml_dense_switch.
-
-:- interface.
-
-:- import_module prog_data.
-:- import_module hlds_data, switch_util, type_util.
-:- import_module mlds, ml_code_util.
-:- import_module llds. % XXX for code_model
-
- % Should this switch be implemented as a dense jump table?
- % If so, we return the starting and ending values for the table,
- % and whether the switch is not covers all cases or not
- % (we may convert locally semidet switches into locally det
- % switches by adding extra cases whose body is just `fail').
-
-:- pred ml_dense_switch__is_dense_switch(prog_var::in, cases_list::in,
- can_fail::in, int::in, int::out, int::out, can_fail::out,
- ml_gen_info::in, ml_gen_info::out) is semidet.
-
- % Generate code for a switch using a dense jump table.
-
-:- pred ml_dense_switch__generate(cases_list::in, int::in, int::in,
- prog_var::in, code_model::in, can_fail::in,
- prog_context::in, mlds__defns::out, mlds__statements::out,
- ml_gen_info::in, ml_gen_info::out) is det.
-
- % also used by ml_lookup_switch
-:- pred ml_dense_switch__calc_density(int, int, int).
-:- mode ml_dense_switch__calc_density(in, in, out) is det.
-
- % also used by ml_lookup_switch
-:- pred ml_dense_switch__type_range(builtin_type, prog_type, int,
- ml_gen_info, ml_gen_info).
-:- mode ml_dense_switch__type_range(in, in, out, in, out) is semidet.
-
-%-----------------------------------------------------------------------------%
-
-:- implementation.
-
-:- import_module hlds_module, ml_code_gen, builtin_ops.
-:- import_module char, map, int, std_util, require, list.
-
-ml_dense_switch__is_dense_switch(CaseVar, TaggedCases, CanFail0, ReqDensity,
- FirstVal, LastVal, CanFail) -->
- {
- list__length(TaggedCases, NumCases),
- NumCases > 2,
- TaggedCases = [FirstCase | _],
- FirstCase = case(_, int_constant(FirstCaseVal), _, _),
- list__index1_det(TaggedCases, NumCases, LastCase),
- LastCase = case(_, int_constant(LastCaseVal), _, _),
- Span is LastCaseVal - FirstCaseVal,
- Range is Span + 1,
- ml_dense_switch__calc_density(NumCases, Range, Density),
- Density > ReqDensity
- },
- ( { CanFail0 = 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 large enough to hold all
- % of the values for the type.
- ml_variable_type(CaseVar, Type),
- =(MLGenInfo),
- { ml_gen_info_get_module_info(MLGenInfo, ModuleInfo) },
- { type_util__classify_type(Type, ModuleInfo, TypeCategory) },
- (
- ml_dense_switch__type_range(TypeCategory, Type,
- TypeRange),
- { ml_dense_switch__calc_density(NumCases, TypeRange,
- DetDensity) },
- { DetDensity > ReqDensity }
- ->
- { CanFail = cannot_fail },
- { FirstVal = 0 },
- { LastVal is TypeRange - 1 }
- ;
- { CanFail = CanFail0 },
- { FirstVal = FirstCaseVal },
- { LastVal = LastCaseVal }
- )
- ;
- { CanFail = CanFail0 },
- { FirstVal = FirstCaseVal },
- { LastVal = LastCaseVal }
- ).
-
-%-----------------------------------------------------------------------------%
-
- % Calculate the percentage density given the range
- % and the number of cases.
-
-ml_dense_switch__calc_density(NumCases, Range, Density) :-
- N1 is NumCases * 100,
- Density is N1 // Range.
-
-%-----------------------------------------------------------------------------%
-
- % Determine the range of an atomic type.
- % Fail if the type isn't the sort of type that has a range
- % or if the type's range is to big to switch on (e.g. int).
-
-ml_dense_switch__type_range(char_type, _, CharRange) -->
- % XXX the following code uses the host's character size,
- % not the target's, so it won't work if cross-compiling
- % to a machine with a different character size.
- % Note also that the code above in dense_switch.m and the code
- % in lookup_switch.m assume that char__min_char_value is 0.
- { char__max_char_value(MaxChar) },
- { char__min_char_value(MinChar) },
- { CharRange is MaxChar - MinChar + 1 }.
-ml_dense_switch__type_range(enum_type, Type, TypeRange) -->
- { type_to_type_id(Type, TypeId0, _) ->
- TypeId = TypeId0
- ;
- error("dense_switch__type_range: invalid enum type?")
- },
- =(MLGenInfo),
- { ml_gen_info_get_module_info(MLGenInfo, ModuleInfo) },
- { module_info_types(ModuleInfo, TypeTable) },
- { map__lookup(TypeTable, TypeId, TypeDefn) },
- { hlds_data__get_type_defn_body(TypeDefn, TypeBody) },
- { TypeBody = du_type(_, ConsTable, _, _) ->
- map__count(ConsTable, TypeRange)
- ;
- error("dense_switch__type_range: enum type is not d.u. type?")
- }.
-
-%-----------------------------------------------------------------------------%
-
-ml_dense_switch__generate(Cases, StartVal, EndVal, Var, CodeModel, CanFail,
- Context, MLDS_Decls, MLDS_Statements) -->
- % Evaluate the variable which we are going to be switching on
- ml_gen_var(Var, Lval),
- { Rval = lval(Lval) },
- % If the case values start at some number other than 0,
- % then subtract that number to give us a zero-based index
- { StartVal = 0 ->
- Index = Rval
- ;
- Index = binop(-, Rval, const(int_const(StartVal)))
- },
- % Now generate the jump table and the cases
- ml_gen_new_label(EndLabel),
- ml_dense_switch__generate_cases(Cases, StartVal, EndVal, CodeModel,
- Context, EndLabel, CaseLabels, CasesDecls, CasesCode),
-
- { Comment = mlds__statement(
- atomic(comment("switch (using dense jump table)")),
- mlds__make_context(Context)) },
- { DoJump = mlds__statement(
- computed_goto(Index, CaseLabels),
- mlds__make_context(Context)) },
- { EndLabelStatement = mlds__statement(label(EndLabel),
- mlds__make_context(Context)) },
-
- % If the switch is not locally deterministic, we need to
- % check that the value of the variable lies within the
- % appropriate range
- (
- { CanFail = can_fail },
- { Difference is EndVal - StartVal },
- { InRange = binop(<=, unop(std_unop(cast_to_unsigned), Index),
- const(int_const(Difference))) },
- ml_gen_failure(CodeModel, Context, DoFailStatements),
- { DoFailStatements = [] ->
- Else = no
- ;
- Else = yes(ml_gen_block([], DoFailStatements, Context))
- },
- { SwitchBody = ml_gen_block([], [DoJump | CasesCode],
- Context) },
- { DoSwitch = mlds__statement(
- if_then_else(InRange, SwitchBody, Else),
- mlds__make_context(Context)) },
- { MLDS_Statements = [Comment, DoSwitch] ++
- [EndLabelStatement] }
- ;
- { CanFail = cannot_fail },
- { MLDS_Statements = [Comment, DoJump | CasesCode] ++
- [EndLabelStatement] }
- ),
- { MLDS_Decls = CasesDecls }.
-
-:- pred ml_dense_switch__generate_cases(cases_list::in, int::in, int::in,
- code_model::in, prog_context::in,
- mlds__label::in, list(mlds__label)::out,
- mlds__defns::out, mlds__statements::out,
- ml_gen_info::in, ml_gen_info::out) is det.
-
-ml_dense_switch__generate_cases(Cases0, NextVal, EndVal, CodeModel, Context,
- EndLabel, CaseLabels, MLDS_Decls, MLDS_Statements) -->
- (
- { NextVal > EndVal }
- ->
- { EndComment = mlds__statement(
- atomic(comment("End of dense switch")),
- mlds__make_context(Context)) },
- { CaseLabels = [] },
- { MLDS_Decls = [] },
- { MLDS_Statements = [EndComment] }
- ;
- % generate the next case
- ml_dense_switch__generate_case(Cases0, NextVal,
- CodeModel, Context, EndLabel,
- Cases1, ThisLabel, CaseStatements),
- % generate the rest of the cases.
- ml_dense_switch__generate_cases(Cases1, NextVal + 1, EndVal,
- CodeModel, Context, EndLabel,
- CaseLabels1, MLDS_Decls, MLDS_Statements1),
- % package it all up together
- { CaseLabels = [ThisLabel | CaseLabels1] },
- { MLDS_Statements = list__append(CaseStatements,
- MLDS_Statements1) }
- ).
-
-%-----------------------------------------------------------------------------%
-
-:- pred ml_dense_switch__generate_case(cases_list::in, int::in,
- code_model::in, prog_context::in, mlds__label::in,
- cases_list::out, mlds__label::out, mlds__statements::out,
- ml_gen_info::in, ml_gen_info::out) is det.
-
-ml_dense_switch__generate_case(Cases0, NextVal, CodeModel, Context,
- EndLabel, Cases1, ThisLabel, MLDS_Statements) -->
- ml_gen_new_label(ThisLabel),
- { LabelComment = mlds__statement(
- atomic(comment(Comment)),
- mlds__make_context(Context)) },
- { LabelCode = mlds__statement(
- label(ThisLabel),
- mlds__make_context(Context)) },
- ml_dense_switch__generate_case_body(Cases0, NextVal, CodeModel,
- Context, Cases1, Comment, CaseStatement),
- { JumpComment = mlds__statement(
- atomic(comment("branch to end of dense switch")),
- mlds__make_context(Context)) },
- { JumpCode = mlds__statement(
- goto(EndLabel),
- mlds__make_context(Context)) },
- { MLDS_Statements = [LabelComment, LabelCode, CaseStatement,
- JumpComment, JumpCode] }.
-
-:- pred ml_dense_switch__generate_case_body(cases_list::in, int::in,
- code_model::in, prog_context::in, cases_list::out,
- string::out, mlds__statement::out,
- ml_gen_info::in, ml_gen_info::out) is det.
-
-ml_dense_switch__generate_case_body(Cases0, NextVal, CodeModel, Context,
- Cases, Comment, MLDS_Statement) -->
- (
- { Cases0 = [Case | Cases1] },
- { Case = case(_, int_constant(NextVal), _, Goal) }
- ->
- { Comment = "case of dense switch" },
- ml_gen_goal(CodeModel, Goal, MLDS_Statement),
- { Cases = Cases1 }
- ;
- % This case didn't occur in the original case list
- % - just generate a `fail' for it.
- { Comment = "compiler-introduced `fail' case of dense switch" },
- ml_gen_failure(CodeModel, Context, FailStatements),
- { MLDS_Statement = ml_gen_block([], FailStatements, Context) },
- { Cases = Cases0 }
- ).
-
-%-----------------------------------------------------------------------------%
Index: compiler/mlds.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mlds.m,v
retrieving revision 1.40
diff -u -d -r1.40 mlds.m
--- compiler/mlds.m 2000/11/14 07:40:51 1.40
+++ compiler/mlds.m 2000/11/17 12:39:58
@@ -705,8 +705,12 @@
mlds__type,
mlds__rval,
+ % The range of possible values which the
+ % value might take (if known)
+ mlds__switch_range,
+
% The different cases
- list(mlds__switch_case),
+ mlds__switch_cases,
% What to do if none of the cases match
mlds__switch_default
@@ -816,11 +820,18 @@
%
% Extra info for switches
%
+ % The range of possible values which the
+ % switch variable might take (if known)
+:- type mlds__switch_range
+ ---> range_unknown
+ ; range(range_min::int, range_max::int).
+ % From range_min to range_max, inclusive.
% Each switch case consists of the conditions to match against,
% and the statement to execute if the match succeeds.
% Unlike C, cases do NOT fall through; if you want to achieve that
% effect, you need to use an explicit goto.
+:- type mlds__switch_cases == list(mlds__switch_case).
:- type mlds__switch_case == pair(mlds__case_match_conds, mlds__statement).
% case_match_conds should be a _non-empty_ list of conditions;
Index: compiler/mlds_to_c.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mlds_to_c.m,v
retrieving revision 1.66
diff -u -d -r1.66 mlds_to_c.m
--- compiler/mlds_to_c.m 2000/11/13 04:25:55 1.66
+++ compiler/mlds_to_c.m 2000/11/16 09:47:10
@@ -1913,7 +1913,7 @@
;
[]
).
-mlds_output_stmt(Indent, FuncInfo, switch(_Type, Val, Cases, Default),
+mlds_output_stmt(Indent, FuncInfo, switch(_Type, Val, _Range, Cases, Default),
Context) -->
mlds_indent(Context, Indent),
io__write_string("switch ("),
Index: compiler/mlds_to_il.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mlds_to_il.m,v
retrieving revision 1.6
diff -u -d -r1.6 mlds_to_il.m
--- compiler/mlds_to_il.m 2000/11/09 07:47:03 1.6
+++ compiler/mlds_to_il.m 2000/11/16 09:48:15
@@ -760,10 +760,11 @@
instr_node(label(DoneLabel))
]) }.
-statement_to_il(statement(switch(_Type, _Val, _Cases, _Default),
+statement_to_il(statement(switch(_Type, _Val, _Range, _Cases, _Default),
_Context), _Instrs) -->
% The IL back-end only supports computed_gotos and if-then-else chains;
- % the MLDS code generator should avoid generating MLDS switches.
+ % the MLDS code generator should either avoid generating MLDS switches,
+ % or should transform them into computed_gotos or if-then-else chains.
{ error("mlds_to_il.m: `switch' not supported") }.
statement_to_il(statement(while(Condition, Body, AtLeastOnce),
Index: compiler/ml_elim_nested.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_elim_nested.m,v
retrieving revision 1.16
diff -u -d -r1.16 ml_elim_nested.m
--- compiler/ml_elim_nested.m 2000/11/08 07:23:10 1.16
+++ compiler/ml_elim_nested.m 2000/11/16 09:40:39
@@ -670,11 +670,11 @@
flatten_maybe_statement(MaybeElse0, MaybeElse),
{ Stmt = if_then_else(Cond, Then, MaybeElse) }
;
- { Stmt0 = switch(Type, Val0, Cases0, Default0) },
+ { Stmt0 = switch(Type, Val0, Range, Cases0, Default0) },
fixup_rval(Val0, Val),
list__map_foldl(flatten_case, Cases0, Cases),
flatten_default(Default0, Default),
- { Stmt = switch(Type, Val, Cases, Default) }
+ { Stmt = switch(Type, Val, Range, Cases, Default) }
;
{ Stmt0 = label(_) },
{ Stmt = Stmt0 }
@@ -1190,7 +1190,7 @@
; maybe_statement_contains_defn(MaybeElse, Defn)
)
;
- Stmt = switch(_Type, _Val, Cases, Default),
+ Stmt = switch(_Type, _Val, _Range, Cases, Default),
( cases_contains_defn(Cases, Defn)
; default_contains_defn(Default, Defn)
)
@@ -1339,7 +1339,7 @@
; maybe_statement_contains_var(MaybeElse, Name)
)
;
- Stmt = switch(_Type, Val, Cases, Default),
+ Stmt = switch(_Type, Val, _Range, Cases, Default),
( rval_contains_var(Val, Name)
; cases_contains_var(Cases, Name)
; default_contains_var(Default, Name)
Index: compiler/ml_optimize.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_optimize.m,v
retrieving revision 1.3
diff -u -d -r1.3 ml_optimize.m
--- compiler/ml_optimize.m 2000/11/08 07:23:10 1.3
+++ compiler/ml_optimize.m 2000/11/17 08:00:55
@@ -134,8 +134,8 @@
optimize_in_statement(OptInfo, Then),
maybe_apply(optimize_in_statement(OptInfo), MaybeElse))
;
- Stmt0 = switch(Type, Rval, Cases0, Default0),
- Stmt = switch(Type, Rval,
+ Stmt0 = switch(Type, Rval, Range, Cases0, Default0),
+ Stmt = switch(Type, Rval, Range,
list__map(optimize_in_case(OptInfo), Cases0),
optimize_in_default(OptInfo, Default0))
;
@@ -168,7 +168,8 @@
optimize_in_case(OptInfo, Conds - Statement0) = Conds - Statement :-
Statement = optimize_in_statement(OptInfo, Statement0).
-:- func optimize_in_default(opt_info, mlds__switch_default) = mlds__switch_default.
+:- func optimize_in_default(opt_info, mlds__switch_default) =
+ mlds__switch_default.
optimize_in_default(_OptInfo, default_is_unreachable) = default_is_unreachable.
optimize_in_default(_OptInfo, default_do_nothing) = default_do_nothing.
@@ -176,6 +177,8 @@
default_case(Statement) :-
Statement = optimize_in_statement(OptInfo, Statement0).
+%-----------------------------------------------------------------------------%
+
:- func optimize_in_call_stmt(opt_info, mlds__stmt) = mlds__stmt.
optimize_in_call_stmt(OptInfo, Stmt0) = Stmt :-
@@ -310,7 +313,7 @@
Stmt = Stmt0
).
-
+%-----------------------------------------------------------------------------%
% Maps T into V, inside a maybe .
:- func maybe_apply(func(T) = V, maybe(T)) = maybe(V).
@@ -318,5 +321,4 @@
maybe_apply(_, no) = no.
maybe_apply(F, yes(T)) = yes(F(T)).
-
-
+%-----------------------------------------------------------------------------%
Index: compiler/ml_simplify_switch.m
===================================================================
RCS file: ml_simplify_switch.m
diff -N ml_simplify_switch.m
--- /dev/null Thu Mar 30 14:06:13 2000
+++ ml_simplify_switch.m Sat Nov 18 00:02:08 2000
@@ -0,0 +1,468 @@
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2000 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+
+% File: ml_simplify_switch.m
+% Main author: fjh
+
+% This module, which is invoked by the various parts of the MLDS code generator
+% that generate switches, converts MLDS switches into computed gotos
+% or if-then-else chains.
+
+% We should eventually also handle lookup switches and binary search switches
+% here too.
+
+% The choice of which exactly which simplifications will get
+% performed depends on the target (e.g. whether it understands
+% switches) and the --prefer-switch option.
+
+%-----------------------------------------------------------------------------%
+
+:- module ml_simplify_switch.
+:- interface.
+
+:- import_module mlds, ml_code_util.
+
+:- pred ml_simplify_switch(mlds__stmt::in, mlds__context::in,
+ mlds__statement::out,
+ ml_gen_info::in, ml_gen_info::out) is det.
+
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module ml_switch_gen, builtin_ops, type_util.
+:- import_module globals, options.
+
+:- import_module bool, int, list, map, require, std_util.
+
+%-----------------------------------------------------------------------------%
+
+ml_simplify_switch(Stmt0, MLDS_Context, Statement) -->
+ ml_gen_info_get_globals(Globals),
+ (
+ %
+ % Convert dense int switches into computed gotos,
+ % unless the target prefers switches.
+ %
+ % is this an int switch?
+ { Stmt0 = switch(Type, Rval, Range, Cases, Default) },
+ { is_integral_type(Type) },
+
+ % does the target want us to convert dense int
+ % switches into computed gotos?
+ { target_supports_computed_goto(Globals) },
+ \+ {
+ target_supports_int_switch(Globals),
+ globals__lookup_bool_option(Globals, prefer_switch, yes)
+ },
+
+ % is the switch big enough?
+ { list__length(Cases, NumCases) },
+ { globals__lookup_int_option(Globals, dense_switch_size,
+ DenseSize) },
+ { NumCases >= DenseSize },
+
+ % ... and dense enough?
+ { globals__lookup_int_option(Globals, dense_switch_req_density,
+ ReqDensity) },
+ { is_dense_switch(Cases, ReqDensity) }
+ ->
+ { maybe_eliminate_default(Range, Cases, Default, ReqDensity,
+ FirstVal, LastVal, NeedRangeCheck) },
+ generate_dense_switch(Cases, Default,
+ FirstVal, LastVal, NeedRangeCheck,
+ Type, Rval, MLDS_Context,
+ MLDS_Decls, MLDS_Statements),
+ { Stmt = block(MLDS_Decls, MLDS_Statements) },
+ { Statement = mlds__statement(Stmt, MLDS_Context) }
+ ;
+ %
+ % Convert the remaining (sparse) int switches into if-then-else chains,
+ % unless the target prefers switches.
+ %
+ { Stmt0 = switch(Type, Rval, _Range, Cases, Default) },
+ { is_integral_type(Type) },
+ \+ {
+ target_supports_int_switch(Globals),
+ globals__lookup_bool_option(Globals, prefer_switch, yes)
+ }
+ ->
+ { Statement = ml_switch_to_if_else_chain(Cases, Default, Rval,
+ MLDS_Context) }
+ ;
+ { Stmt = Stmt0 },
+ { Statement = mlds__statement(Stmt, MLDS_Context) }
+ ).
+
+:- pred is_integral_type(mlds__type::in) is semidet.
+is_integral_type(mlds__native_int_type).
+is_integral_type(mlds__native_char_type).
+is_integral_type(mlds__mercury_type(_, int_type)).
+is_integral_type(mlds__mercury_type(_, char_type)).
+is_integral_type(mlds__mercury_type(_, enum_type)).
+
+:- pred is_dense_switch(list(mlds__switch_case)::in, int::in) is semidet.
+is_dense_switch(Cases, ReqDensity) :-
+ % Need at least two cases
+ NumCases = list__length(Cases),
+ NumCases > 2,
+
+ % The switch needs to be dense enough
+ find_first_and_last_case(Cases, FirstCaseVal, LastCaseVal),
+ CasesRange = LastCaseVal - FirstCaseVal + 1,
+ Density = calc_density(NumCases, CasesRange),
+ Density > 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.
+
+maybe_eliminate_default(Range, Cases, Default, ReqDensity,
+ FirstVal, LastVal, NeedRangeCheck) :-
+ % For switches with a default, 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.
+ (
+ Default \= default_is_unreachable,
+ Range = range(Min, Max),
+ TypeRange = Max - Min + 1,
+ NumCases = list__length(Cases),
+ NoDefaultDensity = calc_density(NumCases, TypeRange),
+ NoDefaultDensity > ReqDensity
+ ->
+ NeedRangeCheck = no,
+ FirstVal = Min,
+ LastVal = Max
+ ;
+ ( Default = default_is_unreachable ->
+ NeedRangeCheck = no
+ ;
+ NeedRangeCheck = yes
+ ),
+ find_first_and_last_case(Cases, FirstCaseVal, LastCaseVal),
+ FirstVal = FirstCaseVal,
+ LastVal = LastCaseVal
+ ).
+
+ % Calculate the percentage density given the range
+ % and the number of cases.
+
+:- func calc_density(int, int) = int.
+calc_density(NumCases, Range) = Density :-
+ Density is (NumCases * 100) // Range.
+
+%-----------------------------------------------------------------------------%
+
+% Find the highest and lowest case values in a list of cases.
+
+:- pred find_first_and_last_case(list(mlds__switch_case)::in,
+ int::out, int::out) is det.
+
+find_first_and_last_case(Cases, Min, Max) :-
+ list__foldl2(find_first_and_last_case_2, Cases, 0, Min, 0, Max).
+
+:- pred find_first_and_last_case_2(mlds__switch_case::in,
+ int::in, int::out, int::in, int::out) is det.
+
+find_first_and_last_case_2(Case, Min0, Min, Max0, Max) :-
+ Case = CaseConds - _CaseStatement,
+ list__foldl2(find_first_and_last_case_3, CaseConds,
+ Min0, Min, Max0, Max).
+
+:- pred find_first_and_last_case_3(mlds__case_match_cond::in,
+ int::in, int::out, int::in, int::out) is det.
+
+find_first_and_last_case_3(match_value(Rval), Min0, Min, Max0, Max) :-
+ (
+ Rval = const(int_const(Val))
+ ->
+ int__min(Min0, Val, Min),
+ int__max(Max0, Val, Max)
+ ;
+ error("find_first_and_last_case_3: non-int case")
+ ).
+find_first_and_last_case_3(match_range(MinRval, MaxRval),
+ Min0, Min, Max0, Max) :-
+ (
+ MinRval = const(int_const(Min1)),
+ MaxRval = const(int_const(Max1))
+ ->
+ int__min(Min0, Min1, Min),
+ int__max(Max0, Max1, Max)
+ ;
+ error("find_first_and_last_case_3: non-int case")
+ ).
+
+%-----------------------------------------------------------------------------%
+
+ % 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__type::in, mlds__rval::in, mlds__context::in,
+ mlds__defns::out, mlds__statements::out,
+ ml_gen_info::in, ml_gen_info::out) is det.
+
+generate_dense_switch(Cases, Default, FirstVal, LastVal, NeedRangeCheck,
+ _Type, Rval, MLDS_Context, MLDS_Decls, MLDS_Statements) -->
+ %
+ % If the case values start at some number other than 0,
+ % then subtract that number to give us a zero-based index
+ %
+ { FirstVal = 0 ->
+ Index = Rval
+ ;
+ Index = binop(-, Rval, const(int_const(FirstVal)))
+ },
+
+ %
+ % Now generate the jump table
+ %
+ ml_gen_new_label(EndLabel),
+ { map__init(CaseLabelsMap0) },
+ generate_cases(Cases, EndLabel, CaseLabelsMap0,
+ CaseLabelsMap, CasesDecls, CasesCode),
+ ml_gen_new_label(DefaultLabel),
+ { CaseLabels = get_case_labels(FirstVal, LastVal,
+ CaseLabelsMap, DefaultLabel) },
+ { DefaultLabelStatement = mlds__statement(
+ label(DefaultLabel),
+ MLDS_Context) },
+ (
+ { Default = default_is_unreachable },
+ % we still need the label, in case we inserted
+ % references to it into (unreachable) slots in the
+ % jump table
+ { DefaultStatements = [DefaultLabelStatement] }
+ ;
+ { Default = default_do_nothing },
+ { DefaultStatements = [DefaultLabelStatement] }
+ ;
+ { Default = default_case(DefaultCase) },
+ { DefaultStatements = [DefaultLabelStatement, DefaultCase] }
+ ),
+
+ { StartComment = mlds__statement(
+ atomic(comment("switch (using dense jump table)")),
+ MLDS_Context) },
+ { DoJump = mlds__statement(
+ computed_goto(Index, CaseLabels),
+ MLDS_Context) },
+ { EndLabelStatement = mlds__statement(
+ label(EndLabel),
+ MLDS_Context) },
+ { EndComment = mlds__statement(
+ atomic(comment("End of dense switch")),
+ MLDS_Context) },
+
+ % We may need to check that the value of the variable lies within the
+ % appropriate range
+ (
+ { NeedRangeCheck = yes }
+ ->
+ { Difference is LastVal - FirstVal },
+ { InRange = binop(<=, unop(std_unop(cast_to_unsigned), Index),
+ const(int_const(Difference))) },
+ { Else = yes(mlds__statement(
+ block([], DefaultStatements),
+ MLDS_Context)) },
+ { SwitchBody = mlds__statement(
+ block([], [DoJump | CasesCode]),
+ MLDS_Context) },
+ { DoSwitch = mlds__statement(
+ if_then_else(InRange, SwitchBody, Else),
+ MLDS_Context) },
+ { MLDS_Statements = [StartComment, DoSwitch] ++
+ [EndLabelStatement, EndComment] }
+ ;
+ { MLDS_Statements = [StartComment, DoJump | CasesCode] ++
+ DefaultStatements ++
+ [EndLabelStatement, EndComment] }
+ ),
+ { MLDS_Decls = CasesDecls }.
+
+:- pred generate_cases(list(mlds__switch_case)::in, mlds__label::in,
+ case_labels_map::in, case_labels_map::out,
+ mlds__defns::out, mlds__statements::out,
+ ml_gen_info::in, ml_gen_info::out) is det.
+
+generate_cases([], _EndLabel, CaseLabelsMap, CaseLabelsMap, [], []) --> [].
+generate_cases([Case | Cases], EndLabel, CaseLabelsMap0,
+ CaseLabelsMap, MLDS_Decls, MLDS_Statements) -->
+ generate_case(Case, EndLabel, CaseLabelsMap0, CaseLabelsMap1,
+ CaseDecls, CaseStatements),
+ generate_cases(Cases, EndLabel,
+ CaseLabelsMap1, CaseLabelsMap,
+ MLDS_Decls1, MLDS_Statements1),
+ { MLDS_Decls = CaseDecls ++ MLDS_Decls1 },
+ { MLDS_Statements = CaseStatements ++ MLDS_Statements1 }.
+
+:- pred generate_case(mlds__switch_case::in, mlds__label::in,
+ case_labels_map::in, case_labels_map::out,
+ mlds__defns::out, mlds__statements::out,
+ ml_gen_info::in, ml_gen_info::out) is det.
+
+% This converts an MLDS switch case into code for a dense switch case,
+% by adding a label at the front and a `goto <EndLabel>' at the end.
+% It also inserts the label for this case into the CaseLabelsMap.
+
+generate_case(Case, EndLabel, CaseLabelsMap0, CaseLabelsMap,
+ MLDS_Decls, MLDS_Statements) -->
+ { Case = MatchCondition - CaseStatement },
+ ml_gen_new_label(ThisLabel),
+ { insert_cases_into_map(MatchCondition, ThisLabel,
+ CaseLabelsMap0, CaseLabelsMap) },
+ { CaseStatement = mlds__statement(_, MLDS_Context) },
+ { LabelComment = mlds__statement(
+ atomic(comment("case of dense switch")),
+ MLDS_Context) },
+ { LabelCode = mlds__statement(
+ label(ThisLabel),
+ MLDS_Context) },
+ { JumpComment = mlds__statement(
+ atomic(comment("branch to end of dense switch")),
+ MLDS_Context) },
+ { JumpCode = mlds__statement(
+ goto(EndLabel),
+ MLDS_Context) },
+ { MLDS_Decls = [] },
+ { MLDS_Statements = [LabelComment, LabelCode, CaseStatement,
+ JumpComment, JumpCode] }.
+
+%-----------------------------------------------------------------------------%
+
+%
+% We build up a map which records which label should be used for
+% each case value.
+%
+:- type case_labels_map == map(int, mlds__label).
+
+:- pred insert_cases_into_map(mlds__case_match_conds::in, mlds__label::in,
+ case_labels_map::in, case_labels_map::out) is det.
+
+insert_cases_into_map([], _ThisLabel, CaseLabelsMap, CaseLabelsMap).
+insert_cases_into_map([Cond|Conds], ThisLabel, CaseLabelsMap0, CaseLabelsMap) :-
+ insert_case_into_map(Cond, ThisLabel, CaseLabelsMap0, CaseLabelsMap1),
+ insert_cases_into_map(Conds, ThisLabel, CaseLabelsMap1, CaseLabelsMap).
+
+:- pred insert_case_into_map(mlds__case_match_cond::in, mlds__label::in,
+ case_labels_map::in, case_labels_map::out) is det.
+
+insert_case_into_map(match_value(Rval), ThisLabel,
+ CaseLabelsMap0, CaseLabelsMap) :-
+ ( Rval = const(int_const(Val)) ->
+ map__det_insert(CaseLabelsMap0, Val, ThisLabel, CaseLabelsMap)
+ ;
+ error("insert_case_into_map: non-int case")
+ ).
+insert_case_into_map(match_range(MinRval, MaxRval), ThisLabel,
+ CaseLabelsMap0, CaseLabelsMap) :-
+ (
+ MinRval = const(int_const(Min)),
+ MaxRval = const(int_const(Max))
+ ->
+ insert_range_into_map(Min, Max, ThisLabel,
+ CaseLabelsMap0, CaseLabelsMap)
+ ;
+ error("insert_case_into_map: non-int case")
+ ).
+
+:- pred insert_range_into_map(int::in, int::in, mlds__label::in,
+ case_labels_map::in, case_labels_map::out) is det.
+
+insert_range_into_map(Min, Max, ThisLabel, CaseLabelsMap0, CaseLabelsMap) :-
+ ( Min > Max ->
+ CaseLabelsMap = CaseLabelsMap0
+ ;
+ map__det_insert(CaseLabelsMap0, Min, ThisLabel,
+ CaseLabelsMap1),
+ insert_range_into_map(Min + 1, Max, ThisLabel,
+ CaseLabelsMap1, CaseLabelsMap)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+% Given the starting and ending case values, the mapping from case values
+% to labels, and the default label to use for case values which aren't in
+% the map, this function returns the list of labels to use for the case
+% values.
+
+:- func get_case_labels(int, int, map(int, mlds__label), mlds__label) =
+ list(mlds__label).
+
+get_case_labels(ThisVal, LastVal, CaseLabelsMap, DefaultLabel) = CaseLabels :-
+ ( ThisVal > LastVal ->
+ CaseLabels = []
+ ;
+ ( map__search(CaseLabelsMap, ThisVal, CaseLabel0) ->
+ CaseLabel = CaseLabel0
+ ;
+ CaseLabel = DefaultLabel
+ ),
+ CaseLabels1 = get_case_labels(ThisVal + 1, LastVal,
+ CaseLabelsMap, DefaultLabel),
+ CaseLabels = [CaseLabel | CaseLabels1]
+ ).
+
+%-----------------------------------------------------------------------------%
+
+ % Convert a switch to a chain of if-then-elses
+ % that test each case in turn.
+ %
+:- func ml_switch_to_if_else_chain(mlds__switch_cases, mlds__switch_default,
+ mlds__rval, mlds__context) = mlds__statement.
+ml_switch_to_if_else_chain([], Default, _Rval, MLDS_Context) =
+ MLDS_Statement :-
+ (
+ Default = default_do_nothing,
+ MLDS_Statement = mlds__statement(block([],[]), MLDS_Context)
+ ;
+ Default = default_is_unreachable,
+ MLDS_Statement = mlds__statement(block([],[]), MLDS_Context)
+ ;
+ Default = default_case(MLDS_Statement)
+ ).
+ml_switch_to_if_else_chain([Case | Cases], Default, SwitchRval, MLDS_Context) =
+ MLDS_Statement :-
+ Case = MatchConditions - CaseStatement,
+ (
+ Cases = [], Default = default_is_unreachable
+ ->
+ MLDS_Statement = CaseStatement
+ ;
+ CaseMatchedRval = ml_gen_case_match_conds(MatchConditions,
+ SwitchRval),
+ RestStatement = ml_switch_to_if_else_chain(Cases, Default,
+ SwitchRval, MLDS_Context),
+ IfStmt = if_then_else(CaseMatchedRval,
+ CaseStatement, yes(RestStatement)),
+ MLDS_Statement = mlds__statement(IfStmt, MLDS_Context)
+ ).
+
+ % Generate an rval which will be true iff any of the specified
+ % list of case conditions matches the specified rval.
+:- func ml_gen_case_match_conds(mlds__case_match_conds, rval) = rval.
+ml_gen_case_match_conds([], _) = const(false).
+ml_gen_case_match_conds([Cond], SwitchRval) =
+ ml_gen_case_match_cond(Cond, SwitchRval).
+ml_gen_case_match_conds([Cond1, Cond2 | Conds], SwitchRval) =
+ binop(or,
+ ml_gen_case_match_cond(Cond1, SwitchRval),
+ ml_gen_case_match_conds([Cond2 | Conds], SwitchRval)).
+
+ % Generate an rval which will be true iff the specified
+ % case condition matches the specified rval.
+:- func ml_gen_case_match_cond(mlds__case_match_cond, rval) = rval.
+ml_gen_case_match_cond(match_value(CaseRval), SwitchRval) =
+ % XXX is `eq' the right operator to use here?
+ binop(eq, CaseRval, SwitchRval).
+ml_gen_case_match_cond(match_range(MinRval, MaxRval), SwitchRval) =
+ binop(and, binop(>=, SwitchRval, MinRval),
+ binop(<=, SwitchRval, MaxRval)).
+
+%-----------------------------------------------------------------------------%
Index: compiler/ml_string_switch.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_string_switch.m,v
retrieving revision 1.2
diff -u -d -r1.2 ml_string_switch.m
--- compiler/ml_string_switch.m 2000/11/16 08:45:40 1.2
+++ compiler/ml_string_switch.m 2000/11/17 12:48:43
@@ -33,7 +33,8 @@
:- implementation.
-:- import_module ml_code_gen, ml_switch_gen, builtin_ops, type_util.
+:- import_module ml_code_gen, ml_switch_gen, ml_simplify_switch.
+:- import_module builtin_ops, type_util.
:- import_module globals, options.
:- import_module bool, int, string, list, map, std_util, assoc_list, require.
@@ -67,7 +68,6 @@
%
% Generate new labels
%
- ml_gen_new_label(FailLabel),
ml_gen_new_label(EndLabel),
{ GotoEndStatement = mlds__statement(
goto(EndLabel),
@@ -100,8 +100,7 @@
% Generate the code etc. for the hash table
%
ml_string_switch__gen_hash_slots(0, TableSize, HashSlotsMap, CodeModel,
- Context, FailLabel, EndLabel, Strings, Labels, NextSlots,
- SlotsStatements, SlotsCases),
+ Context, Strings, NextSlots, SlotsCases),
%
% Generate the following local constant declarations:
@@ -126,61 +125,35 @@
ml_qualify_var(StringTableName, StringTableLval),
%
- % Generate code which does the hash table lookup
- % Note that we generate both the switch version and the
- % computed goto version, and then use whichever one is
- % appropriate for the target.
+ % Generate code which does the hash table lookup.
%
- ml_gen_info_get_globals(Globals),
- { globals__lookup_bool_option(Globals, prefer_switch, PreferSwitch) },
- (
- { target_supports_computed_goto(Globals) },
- \+ {
- PreferSwitch = yes,
- target_supports_int_switch(Globals)
- }
- ->
- { UseComputedGoto = yes },
- {
- FoundMatch = mlds__statement(
- block([], [
- mlds__statement(atomic(comment(
- "we found a match")),
- MLDS_Context),
- mlds__statement(atomic(comment(
- "jump to the corresponding code")),
- MLDS_Context),
- mlds__statement(
- computed_goto(lval(SlotVarLval),
- Labels),
- MLDS_Context)
- ]),
- MLDS_Context)
- }
- ;
- { UseComputedGoto = no },
- {
- FoundMatch = mlds__statement(
- block([], [
- mlds__statement(atomic(comment(
- "we found a match")),
- MLDS_Context),
- mlds__statement(atomic(comment(
- "dispatch to the corresponding code")),
- MLDS_Context),
- mlds__statement(
- switch(mlds__native_int_type,
- lval(SlotVarLval),
- SlotsCases,
- default_is_unreachable),
- MLDS_Context),
- GotoEndStatement
- ]),
- MLDS_Context)
- }
- ),
+ { SwitchStmt0 = switch(mlds__native_int_type, lval(SlotVarLval),
+ range(0, TableSize - 1),
+ SlotsCases, default_is_unreachable) },
+ ml_simplify_switch(SwitchStmt0, MLDS_Context, SwitchStatement),
{
+ FoundMatchCond =
+ binop(and,
+ binop(ne,
+ lval(StringVarLval),
+ const(null(ml_string_type))),
+ binop(str_eq,
+ lval(StringVarLval),
+ VarRval)
+ ),
+ FoundMatchCode = mlds__statement(
+ block([], [
+ mlds__statement(atomic(comment(
+ "we found a match")),
+ MLDS_Context),
+ mlds__statement(atomic(comment(
+ "dispatch to the corresponding code")),
+ MLDS_Context),
+ SwitchStatement,
+ GotoEndStatement
+ ]),
+ MLDS_Context),
LoopBody = ml_gen_block([], [
mlds__statement(atomic(comment(
"lookup the string for this hash slot")),
@@ -195,19 +168,8 @@
"did we find a match?")),
MLDS_Context),
mlds__statement(
- if_then_else(
- binop(and,
- binop(ne,
- lval(StringVarLval),
- const(null(
- ml_string_type))),
- binop(str_eq,
- lval(StringVarLval),
- VarRval)
- ),
- FoundMatch,
- no
- ),
+ if_then_else(FoundMatchCond, FoundMatchCode,
+ no),
MLDS_Context),
mlds__statement(atomic(comment(
"no match yet, so get next slot in hash chain")),
@@ -242,10 +204,6 @@
yes), % this is a do...while loop
MLDS_Context)
],
- FailLabelStatement =
- mlds__statement(
- label(FailLabel),
- MLDS_Context),
FailComment =
mlds__statement(
atomic(comment("no match, so fail")),
@@ -266,69 +224,43 @@
%
{ MLDS_Decls = [NextSlotsDefn, StringTableDefn,
SlotVarDefn, StringVarDefn] },
- { UseComputedGoto = yes ->
- MLDS_Statements =
- HashLookupStatements ++
- [FailLabelStatement, FailComment | FailStatements] ++
- [GotoEndStatement] ++
- SlotsStatements ++
- [EndLabelStatement, EndComment]
- ;
- MLDS_Statements = HashLookupStatements ++
+ { MLDS_Statements = HashLookupStatements ++
[FailComment | FailStatements] ++
- [EndLabelStatement, EndComment]
- }.
+ [EndLabelStatement, EndComment] }.
%-----------------------------------------------------------------------------%
:- pred ml_string_switch__gen_hash_slots(int::in, int::in,
map(int, hash_slot)::in, code_model::in, prog_context::in,
- mlds__label::in, mlds__label::in,
- list(mlds__initializer)::out, list(mlds__label)::out,
- list(mlds__initializer)::out, mlds__statements::out,
+ list(mlds__initializer)::out, list(mlds__initializer)::out,
list(mlds__switch_case)::out,
ml_gen_info::in, ml_gen_info::out) is det.
ml_string_switch__gen_hash_slots(Slot, TableSize, HashSlotMap, CodeModel,
- Context, FailLabel, EndLabel, Strings, Labels, NextSlots,
- MLDS_Statements, MLDS_Cases) -->
- { MLDS_Context = mlds__make_context(Context) },
+ Context, Strings, NextSlots, MLDS_Cases) -->
( { Slot = TableSize } ->
- {
- Strings = [],
- Labels = [],
- NextSlots = [],
- MLDS_Statements = [],
- MLDS_Cases = []
- }
+ { Strings = [] },
+ { NextSlots = [] },
+ { MLDS_Cases = [] }
;
+ { MLDS_Context = mlds__make_context(Context) },
ml_string_switch__gen_hash_slot(Slot, HashSlotMap,
- CodeModel, MLDS_Context, FailLabel, EndLabel,
- String, Label, NextSlot, SlotStatements, SlotCases),
- { Slot1 is Slot + 1 },
- {
- Strings = [String | Strings0],
- Labels = [Label | Labels0],
- NextSlots = [NextSlot | NextSlots0],
- MLDS_Statements = SlotStatements ++ MLDS_Statements0,
- MLDS_Cases = SlotCases ++ MLDS_Cases0
- },
- ml_string_switch__gen_hash_slots(Slot1, TableSize, HashSlotMap,
- CodeModel, Context, FailLabel, EndLabel,
- Strings0, Labels0, NextSlots0, MLDS_Statements0,
- MLDS_Cases0)
+ CodeModel, MLDS_Context, String, NextSlot, SlotCases),
+ ml_string_switch__gen_hash_slots(Slot + 1, TableSize,
+ HashSlotMap, CodeModel, Context,
+ Strings0, NextSlots0, MLDS_Cases0),
+ { Strings = [String | Strings0] },
+ { NextSlots = [NextSlot | NextSlots0] },
+ { MLDS_Cases = SlotCases ++ MLDS_Cases0 }
).
:- pred ml_string_switch__gen_hash_slot(int::in, map(int, hash_slot)::in,
- code_model::in, mlds__context::in, mlds__label::in,
- mlds__label::in, mlds__initializer::out,
- mlds__label::out, mlds__initializer::out,
- mlds__statements::out, list(mlds__switch_case)::out,
+ code_model::in, mlds__context::in, mlds__initializer::out,
+ mlds__initializer::out, list(mlds__switch_case)::out,
ml_gen_info::in, ml_gen_info::out) is det.
ml_string_switch__gen_hash_slot(Slot, HashSlotMap, CodeModel, MLDS_Context,
- FailLabel, EndLabel, init_obj(StringRval), Label,
- init_obj(NextSlotRval), MLDS_Statements, MLDS_Cases) -->
+ init_obj(StringRval), init_obj(NextSlotRval), MLDS_Cases) -->
(
{ map__search(HashSlotMap, Slot, hash_slot(Case, Next)) }
->
@@ -340,31 +272,21 @@
error("ml_string_switch__gen_hash_slots: string expected")
},
{ StringRval = const(string_const(String)) },
- ml_gen_new_label(Label),
+ ml_gen_goal(CodeModel, Goal, GoalStatement),
+
{ string__append_list(["case """, String, """"],
CommentString) },
- { LabelComment = mlds__statement(
+ { Comment = mlds__statement(
atomic(comment(CommentString)),
MLDS_Context) },
- { LabelStatement = mlds__statement(
- label(Label),
- MLDS_Context) },
- ml_gen_goal(CodeModel, Goal, GoalStatement),
- { JumpComment = mlds__statement(
- atomic(comment("jump to end of switch")),
- MLDS_Context) },
- { JumpStatement = mlds__statement(
- goto(EndLabel),
+ { CaseStatement = mlds__statement(
+ block([], [Comment, GoalStatement]),
MLDS_Context) },
- { MLDS_Statements = [LabelComment, LabelStatement,
- GoalStatement, JumpComment, JumpStatement] },
{ MLDS_Cases = [[match_value(const(int_const(Slot)))] -
- GoalStatement] }
+ CaseStatement] }
;
{ StringRval = const(null(ml_string_type)) },
- { Label = FailLabel },
{ NextSlotRval = const(int_const(-2)) },
- { MLDS_Statements = [] },
{ MLDS_Cases = [] }
).
Index: compiler/ml_switch_gen.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_switch_gen.m,v
retrieving revision 1.4
diff -u -d -r1.4 ml_switch_gen.m
--- compiler/ml_switch_gen.m 2000/11/16 08:45:41 1.4
+++ compiler/ml_switch_gen.m 2000/11/17 13:19:24
@@ -94,10 +94,8 @@
:- implementation.
-% These ones are not yet implemented yet:
-% :- import_module ml_lookup_switch.
-:- import_module ml_tag_switch, ml_dense_switch, ml_string_switch.
-:- import_module ml_code_gen, ml_unify_gen, ml_code_util.
+:- import_module ml_tag_switch, ml_string_switch.
+:- import_module ml_code_gen, ml_unify_gen, ml_code_util, ml_simplify_switch.
:- import_module switch_util, type_util.
:- import_module options.
@@ -129,6 +127,8 @@
(
/**************
XXX Lookup switches are NYI
+When we do get around to implementing them,
+they should probably be handled in ml_simplify_switch rather than here.
{ Indexing = yes },
{ SwitchCategory = atomic_switch },
% Note that if/when the MLDS back-end supports execution
@@ -152,29 +152,6 @@
;
**************/
%
- % Try using a "dense" (computed goto) switch
- %
- { Indexing = yes },
- { SwitchCategory = atomic_switch },
- { target_supports_computed_goto(Globals) },
- \+ {
- target_supports_int_switch(Globals),
- globals__lookup_bool_option(Globals, prefer_switch, yes)
- },
- { list__length(TaggedCases, NumCases) },
- { globals__lookup_int_option(Globals, dense_switch_size,
- DenseSize) },
- { NumCases >= DenseSize },
- { globals__lookup_int_option(Globals, dense_switch_req_density,
- ReqDensity) },
- ml_dense_switch__is_dense_switch(CaseVar, TaggedCases, CanFail,
- ReqDensity, FirstVal, LastVal, CanFail1)
- ->
- ml_dense_switch__generate(TaggedCases, FirstVal, LastVal,
- CaseVar, CodeModel, CanFail1, Context,
- MLDS_Decls, MLDS_Statements)
- ;
- %
% Try using a string hash switch
%
{ Indexing = yes },
@@ -190,7 +167,8 @@
;
{ target_supports_int_switch(Globals) }
),
- % XXX Currently string hash switches always use gotos.
+ % XXX Currently string hash switches always use gotos
+ % (to break out of the hash chain loop).
% We should change that, so that we can use string hash
% switches for the Java back-end too.
{ target_supports_goto(Globals) },
@@ -219,10 +197,19 @@
CanFail, Context, MLDS_Decls, MLDS_Statements)
;
%
- % Try using a "direct-mapped" switch
+ % Try using a "direct-mapped" switch.
+ % This also handles dense (computed goto) switches --
+ % for those, we first generate a direct-mapped switch,
+ % and then convert it into a computed goto switch
+ % in ml_simplify_switch.
%
{ Indexing = yes },
- { target_supports_switch(SwitchCategory, Globals) }
+ (
+ { target_supports_switch(SwitchCategory, Globals) }
+ ;
+ { SwitchCategory = atomic_switch },
+ { target_supports_computed_goto(Globals) }
+ )
->
ml_switch_generate_mlds_switch(TaggedCases, CaseVar,
CodeModel, CanFail, Context,
@@ -384,13 +371,31 @@
ml_gen_type(Type, MLDS_Type),
ml_gen_var(Var, Lval),
{ Rval = mlds__lval(Lval) },
+ ml_switch_gen_range(MLDS_Type, Range),
ml_switch_generate_mlds_cases(Cases, CodeModel, MLDS_Cases),
ml_switch_generate_default(CanFail, CodeModel, Context, Default),
- { SwitchStmt = switch(MLDS_Type, Rval, MLDS_Cases, Default) },
- { SwitchStatement = mlds__statement(SwitchStmt,
- mlds__make_context(Context)) },
+ { SwitchStmt0 = switch(MLDS_Type, Rval, Range, MLDS_Cases, Default) },
+ { MLDS_Context = mlds__make_context(Context) },
+ ml_simplify_switch(SwitchStmt0, MLDS_Context, SwitchStatement),
{ MLDS_Decls = [] },
{ MLDS_Statements = [SwitchStatement] }.
+
+:- pred ml_switch_gen_range(mlds__type, mlds__switch_range,
+ ml_gen_info, ml_gen_info).
+:- mode ml_switch_gen_range(in, out, in, out) is det.
+
+ml_switch_gen_range(MLDS_Type, Range) -->
+ =(MLGenInfo),
+ {
+ MLDS_Type = mercury_type(Type, TypeCategory),
+ ml_gen_info_get_module_info(MLGenInfo, ModuleInfo),
+ switch_util__type_range(TypeCategory, Type, ModuleInfo,
+ MinRange, MaxRange)
+ ->
+ Range = range(MinRange, MaxRange)
+ ;
+ Range = range_unknown
+ }.
:- pred ml_switch_generate_mlds_cases(list(extended_case),
code_model, list(mlds__switch_case), ml_gen_info, ml_gen_info).
Index: compiler/ml_tag_switch.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_tag_switch.m,v
retrieving revision 1.2
diff -u -d -r1.2 ml_tag_switch.m
--- compiler/ml_tag_switch.m 2000/11/16 08:45:41 1.2
+++ compiler/ml_tag_switch.m 2000/11/17 12:47:48
@@ -32,7 +32,7 @@
:- implementation.
:- import_module hlds_goal, hlds_module.
-:- import_module ml_code_gen, ml_switch_gen, ml_unify_gen.
+:- import_module ml_code_gen, ml_switch_gen, ml_unify_gen, ml_simplify_switch.
:- import_module builtin_ops, type_util.
:- import_module assoc_list, map, int, string, require, std_util.
@@ -56,7 +56,7 @@
{ ml_gen_info_get_module_info(Info, ModuleInfo) },
ml_variable_type(Var, Type),
{ switch_util__get_ptag_counts(Type, ModuleInfo,
- _MaxPrimary, PtagCountMap) },
+ MaxPrimary, PtagCountMap) },
{ map__to_assoc_list(PtagCountMap, PtagCountList) },
{ map__init(PtagCaseMap0) },
{ switch_util__group_cases_by_ptag(Cases, PtagCaseMap0,
@@ -72,10 +72,11 @@
% package up the results into a switch statement
- { SwitchStmt = switch(mlds__native_int_type, PTagRval, MLDS_Cases,
- Default) },
- { SwitchStatement = mlds__statement(SwitchStmt,
- mlds__make_context(Context)) },
+ { Range = range(0, MaxPrimary) },
+ { SwitchStmt0 = switch(mlds__native_int_type, PTagRval, Range,
+ MLDS_Cases, Default) },
+ { MLDS_Context = mlds__make_context(Context) },
+ ml_simplify_switch(SwitchStmt0, MLDS_Context, SwitchStatement),
{ MLDS_Decls = [] },
{ MLDS_Statements = [SwitchStatement] }.
@@ -180,11 +181,11 @@
% package up the results into a switch statement
- { SwitchStmt = switch(mlds__native_int_type, STagRval, MLDS_Cases,
- Default) },
- { SwitchStatement = mlds__statement(SwitchStmt,
- mlds__make_context(Context)) },
- { MLDS_Statement = SwitchStatement }.
+ { Range = range_unknown }, % XXX could do better
+ { SwitchStmt = switch(mlds__native_int_type, STagRval, Range,
+ MLDS_Cases, Default) },
+ { MLDS_Context = mlds__make_context(Context) },
+ ml_simplify_switch(SwitchStmt, MLDS_Context, MLDS_Statement).
:- pred ml_tag_switch__gen_stag_cases(stag_goal_list, code_model,
list(mlds__switch_case), ml_gen_info, ml_gen_info).
Index: compiler/ml_tailcall.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_tailcall.m,v
retrieving revision 1.4
diff -u -d -r1.4 ml_tailcall.m
--- compiler/ml_tailcall.m 2000/11/08 07:23:11 1.4
+++ compiler/ml_tailcall.m 2000/11/16 09:46:16
@@ -234,10 +234,10 @@
% are in a tail position iff the switch is in a
% tail position.
%
- Stmt0 = switch(Type, Val, Cases0, Default0),
+ Stmt0 = switch(Type, Val, Range, Cases0, Default0),
Cases = mark_tailcalls_in_cases(Cases0, AtTail, Locals),
Default = mark_tailcalls_in_default(Default0, AtTail, Locals),
- Stmt = switch(Type, Val, Cases, Default)
+ Stmt = switch(Type, Val, Range, Cases, Default)
;
Stmt0 = label(_),
Stmt = Stmt0
Index: compiler/ml_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_util.m,v
retrieving revision 1.2
diff -u -d -r1.2 ml_util.m
--- compiler/ml_util.m 2000/11/08 07:23:11 1.2
+++ compiler/ml_util.m 2000/11/16 09:46:26
@@ -111,7 +111,7 @@
; maybe_statement_contains_statement(MaybeElse, SubStatement)
)
;
- Stmt = switch(_Type, _Val, Cases, Default),
+ Stmt = switch(_Type, _Val, _Range, Cases, Default),
( cases_contains_statement(Cases, SubStatement)
; default_contains_statement(Default, SubStatement)
)
Index: compiler/switch_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/switch_util.m,v
retrieving revision 1.1
diff -u -d -r1.1 switch_util.m
--- compiler/switch_util.m 2000/11/16 08:45:42 1.1
+++ compiler/switch_util.m 2000/11/16 10:26:06
@@ -44,6 +44,14 @@
:- pred switch_util__switch_priority(cons_tag, int).
:- mode switch_util__switch_priority(in, out) is det.
+ % switch_util__type_range(TypeCategory, Type, ModuleInfo, Min, Max):
+ % Determine the range [Min..Max] of an atomic 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 switch_util__type_range(builtin_type, type, module_info, int, int).
+:- mode switch_util__type_range(in, in, in, out, out) is semidet.
+
%-----------------------------------------------------------------------------%
%
% Stuff for string hash switches
@@ -134,7 +142,7 @@
%-----------------------------------------------------------------------------%
:- implementation.
-:- import_module int, string, require.
+:- import_module char, int, string, require.
%-----------------------------------------------------------------------------%
@@ -250,6 +258,7 @@
% Stuff for categorizing switches
%
+ % Convert a type category to a switch category
switch_util__type_cat_to_switch_cat(enum_type, atomic_switch).
switch_util__type_cat_to_switch_cat(int_type, atomic_switch).
switch_util__type_cat_to_switch_cat(char_type, atomic_switch).
@@ -278,6 +287,34 @@
switch_util__switch_priority(type_ctor_info_constant(_, _, _), 6).
switch_util__switch_priority(base_typeclass_info_constant(_, _, _), 6).
switch_util__switch_priority(tabling_pointer_constant(_, _), 6).
+
+ % Determine the range of an atomic type.
+ % Fail if the type isn't the sort of type that has a range
+ % or if the type's range is to big to switch on (e.g. int).
+ %
+switch_util__type_range(char_type, _, _, MinChar, MaxChar) :-
+ % XXX the following code uses the host's character size,
+ % not the target's, so it won't work if cross-compiling
+ % to a machine with a different character size.
+ % Note also that the code in dense_switch.m and the code
+ % in lookup_switch.m assume that char__min_char_value is 0.
+ char__min_char_value(MinChar),
+ char__max_char_value(MaxChar).
+switch_util__type_range(enum_type, Type, ModuleInfo, 0, MaxEnum) :-
+ ( type_to_type_id(Type, TypeId0, _) ->
+ TypeId = TypeId0
+ ;
+ error("dense_switch__type_range: invalid enum type?")
+ ),
+ module_info_types(ModuleInfo, TypeTable),
+ map__lookup(TypeTable, TypeId, TypeDefn),
+ hlds_data__get_type_defn_body(TypeDefn, TypeBody),
+ ( TypeBody = du_type(_, ConsTable, _, _) ->
+ map__count(ConsTable, TypeRange),
+ MaxEnum = TypeRange - 1
+ ;
+ error("dense_switch__type_range: enum type is not d.u. type?")
+ ).
%-----------------------------------------------------------------------------%
--
Fergus Henderson <fjh at cs.mu.oz.au> | "I have always known that the pursuit
| of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to: mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions: mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------
More information about the developers
mailing list