[m-dev.] for review: MLDS switch optimization
Fergus Henderson
fjh at cs.mu.OZ.AU
Tue Nov 7 01:04:59 AEDT 2000
This change breaks the IL back-end, but the work-around is easy
(compile with `--no-smart-indexing'). I'm hoping Tyson will review
fix the following XXX in ilasm.m, which is the cause of that problem,
% XXX we really should implement this since we will use it
% eventually.
output_instr(switch(_)) --> { error("output not implemented") }.
since "eventually" has now arrived ;-)
I'm also hoping that Tyson and/or Zoltan will review this change.
Note that this change still doesn't optimize tag switches, string
switches, or lookup switches.
----------
Estimated hours taken: 12
Get the MLDS back-end to generate better code for switches.
It now compiles Mercury switches on int/char/enums into C switches.
compiler/mlds.m:
Add `switch' as a new alternative in the `mlds__stmt' type.
compiler/ml_elim_nested.m:
compiler/ml_optimize.m:
compiler/ml_tailcall.m:
Minor changes to handle the new `switch' statement.
compiler/ml_code_gen.m:
Move the code for handling switches to ml_switch_gen.m.
Export `ml_gen_goal', for use in ml_switch_gen.m.
compiler/ml_switch_gen.m:
compiler/ml_dense_switch.m:
New files, adapted from switch_gen.m and dense_switch.m, but
with significant changes. These now handle three forms of switch:
- dense switches, implemented as computed gotos;
- "direct mapped" switches, which get implemented using the
MLDS switch statement, which in turn gets mapped to the
target language's switch statement;
- if-then-else chains
compiler/ml_code_util.m:
Add a label counter to the ml_gen_info, and define predicates
for allocating new labels.
compiler/mlds_to_c.m:
Output switch statements. Also fix a layout bug in the output:
make sure we output newlines at the end of comments.
compiler/mlds_to_il.m:
Call error/1 for MLDS switch statements. The code generator
will generate MLDS computed_gotos (which map to IL `switch'
instructions) rather than MLDS switch statements, so we should
never get MLDS switch statements here.
compiler/options.m:
Add a new option `--prefer-switch', defaulting to enabled,
which says to generate switches rather than computed gotos
where possible.
Workspace: /home/pgrad/fjh/ws/hg
Index: compiler/ml_code_gen.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_code_gen.m,v
retrieving revision 1.63
diff -u -d -r1.63 ml_code_gen.m
--- compiler/ml_code_gen.m 2000/10/30 07:09:01 1.63
+++ compiler/ml_code_gen.m 2000/11/06 03:04:23
@@ -683,7 +683,9 @@
:- interface.
-:- import_module hlds_module, mlds.
+:- import_module hlds_module, hlds_goal.
+:- import_module mlds, ml_code_util.
+:- import_module llds. % XXX needed for `code_model'.
:- import_module io.
%-----------------------------------------------------------------------------%
@@ -694,13 +696,30 @@
:- pred ml_code_gen(module_info, mlds, io__state, io__state).
:- mode ml_code_gen(in, out, di, uo) is det.
+ % Generate MLDS code for the specified goal in the
+ % specified code model. Return the result as a single statement
+ % (which may be a block statement containing nested declarations).
+ %
+:- pred ml_gen_goal(code_model, hlds_goal, mlds__statement,
+ ml_gen_info, ml_gen_info).
+:- mode ml_gen_goal(in, in, out, in, out) is det.
+
+ % Generate MLDS code for the specified goal in the
+ % specified code model. Return the result as two lists,
+ % one containing the necessary declarations and the other
+ % containing the generated statements.
+ %
+:- pred ml_gen_goal(code_model, hlds_goal, mlds__defns, mlds__statements,
+ ml_gen_info, ml_gen_info).
+:- mode ml_gen_goal(in, in, out, out, in, out) is det.
+
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
:- implementation.
-:- import_module ml_type_gen, ml_call_gen, ml_unify_gen, ml_code_util.
-:- import_module llds. % XXX needed for `code_model'.
+:- import_module ml_type_gen, ml_call_gen, ml_unify_gen, ml_switch_gen.
+:- import_module ml_code_util.
:- import_module arg_info, export, llds_out. % XXX needed for pragma C code
:- import_module hlds_pred, hlds_goal, hlds_data, prog_data.
:- import_module goal_util, type_util, mode_util, builtin_ops.
@@ -1263,10 +1282,6 @@
% specified code model. Return the result as a single statement
% (which may be a block statement containing nested declarations).
%
-:- pred ml_gen_goal(code_model, hlds_goal, mlds__statement,
- ml_gen_info, ml_gen_info).
-:- mode ml_gen_goal(in, in, out, in, out) is det.
-
ml_gen_goal(CodeModel, Goal, MLDS_Statement) -->
ml_gen_goal(CodeModel, Goal, MLDS_Decls, MLDS_Statements),
{ Goal = _ - GoalInfo },
@@ -1279,10 +1294,6 @@
% one containing the necessary declarations and the other
% containing the generated statements.
%
-:- pred ml_gen_goal(code_model, hlds_goal, mlds__defns, mlds__statements,
- ml_gen_info, ml_gen_info).
-:- mode ml_gen_goal(in, in, out, out, in, out) is det.
-
ml_gen_goal(CodeModel, Goal, MLDS_Decls, MLDS_Statements) -->
{ Goal = GoalExpr - GoalInfo },
%
@@ -2440,123 +2451,6 @@
{ AssignOutput = [] },
{ ConvDecls = [] },
{ ConvOutputStatements = [] }
- ).
-
-%-----------------------------------------------------------------------------%
-%
-% Code for switches
-%
-
- % Generate MLDS code for a switch.
- %
-:- pred ml_gen_switch(prog_var, can_fail, list(case), code_model, prog_context,
- mlds__defns, mlds__statements,
- ml_gen_info, ml_gen_info).
-:- mode ml_gen_switch(in, in, in, in, in, out, out, in, out) is det.
-
-
-:- type extended_case ---> case(int, cons_tag, cons_id, hlds_goal).
-:- type cases_list == list(extended_case).
-
- % TODO: optimize various different special kinds of switches,
- % such as string switches, dense switches, lookup switches,
- % etc. (see switch_gen.m, etc.).
- % TODO: optimize switches so that the recursive case comes
- % first (see switch_gen.m).
-
-ml_gen_switch(Var, CanFail, Cases, CodeModel, Context,
- MLDS_Decls, MLDS_Statements) -->
- %
- % Lookup the representation of the constructors for the tag tests
- % and their corresponding priorities.
- %
- ml_switch_lookup_tags(Cases, Var, TaggedCases0),
- %
- % Sort the cases according to the priority of their tag tests.
- %
- { list__sort_and_remove_dups(TaggedCases0, TaggedCases) },
- %
- % Generate an if-then-else chain which tests each of the cases
- % in turn.
- %
- ml_switch_generate_cases(TaggedCases, Var,
- CodeModel, CanFail, Context,
- MLDS_Decls, MLDS_Statements).
-
- % Look up the representation (tag) for the cons_id in each case.
- % Also look up the priority of each tag test.
- %
-:- pred ml_switch_lookup_tags(list(case), prog_var, cases_list,
- ml_gen_info, ml_gen_info).
-:- mode ml_switch_lookup_tags(in, in, out, in, out) is det.
-
-ml_switch_lookup_tags([], _, []) --> [].
-ml_switch_lookup_tags([Case | Cases], Var, [TaggedCase | TaggedCases]) -->
- { Case = case(ConsId, Goal) },
- ml_variable_type(Var, Type),
- ml_cons_id_to_tag(ConsId, Type, Tag),
- { ml_switch_priority(Tag, Priority) },
- { TaggedCase = case(Priority, Tag, ConsId, Goal) },
- ml_switch_lookup_tags(Cases, Var, TaggedCases).
-
- % Return the priority of a tag test.
- % A low number here indicates a high priority.
- % We prioritize the tag tests so that the cheapest
- % (most efficient) ones come first.
- %
-:- pred ml_switch_priority(cons_tag, int).
-:- mode ml_switch_priority(in, out) is det.
-
-ml_switch_priority(no_tag, 0). % should never occur
-ml_switch_priority(int_constant(_), 1).
-ml_switch_priority(shared_local_tag(_, _), 1).
-ml_switch_priority(unshared_tag(_), 2).
-ml_switch_priority(float_constant(_), 3).
-ml_switch_priority(shared_remote_tag(_, _), 4).
-ml_switch_priority(string_constant(_), 5).
- % The following tags should all never occur in switches.
-ml_switch_priority(pred_closure_tag(_, _, _), 6).
-ml_switch_priority(code_addr_constant(_, _), 6).
-ml_switch_priority(type_ctor_info_constant(_, _, _), 6).
-ml_switch_priority(base_typeclass_info_constant(_, _, _), 6).
-ml_switch_priority(tabling_pointer_constant(_, _), 6).
-
- % Generate a chain of if-then-elses to test each case in turn.
- %
-:- pred ml_switch_generate_cases(list(extended_case), prog_var,
- code_model, can_fail, prog_context, mlds__defns, mlds__statements,
- ml_gen_info, ml_gen_info).
-:- mode ml_switch_generate_cases(in, in, in, in, in, out, out,
- in, out) is det.
-
-ml_switch_generate_cases([], _Var, CodeModel, CanFail, Context,
- [], MLDS_Statements) -->
- ( { CanFail = can_fail } ->
- ml_gen_failure(CodeModel, Context, MLDS_Statements)
- ;
- { error("switch failure") }
- ).
-ml_switch_generate_cases([Case | Cases], Var, CodeModel, CanFail, Context,
- MLDS_Decls, MLDS_Statements) -->
- { Case = case(_, _Tag, ConsId, Goal) },
- (
- { Cases = [], CanFail = cannot_fail }
- ->
- ml_gen_goal(CodeModel, Goal, MLDS_Decls, MLDS_Statements)
- ;
- ml_gen_tag_test(Var, ConsId, TagTestDecls, TagTestStatements,
- TagTestExpression),
- ml_gen_goal(CodeModel, Goal, GoalStatement),
- ml_switch_generate_cases(Cases, Var, CodeModel, CanFail,
- Context, RestDecls, RestStatements),
- { Rest = ml_gen_block(RestDecls, RestStatements, Context) },
- { IfStmt = if_then_else(TagTestExpression,
- GoalStatement, yes(Rest)) },
- { IfStatement = mlds__statement(IfStmt,
- mlds__make_context(Context)) },
- { MLDS_Decls = TagTestDecls },
- { MLDS_Statements = list__append(TagTestStatements,
- [IfStatement]) }
).
%-----------------------------------------------------------------------------%
Index: compiler/ml_code_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_code_util.m,v
retrieving revision 1.27
diff -u -d -r1.27 ml_code_util.m
--- compiler/ml_code_util.m 2000/10/30 07:09:02 1.27
+++ compiler/ml_code_util.m 2000/11/06 09:47:08
@@ -173,6 +173,11 @@
mlds__pred_label, mlds_module_name).
:- mode ml_gen_pred_label_from_rtti(in, out, out) is det.
+ % Allocate a new label name, for use in label statements.
+ %
+:- pred ml_gen_new_label(mlds__label, ml_gen_info, ml_gen_info).
+:- mode ml_gen_new_label(out, in, out) is det.
+
%-----------------------------------------------------------------------------%
%
% Routines for dealing with variables
@@ -477,6 +482,14 @@
:- pred ml_gen_info_use_gcc_nested_functions(bool, ml_gen_info, ml_gen_info).
:- mode ml_gen_info_use_gcc_nested_functions(out, in, out) is det.
+
+ % Generate a new label number for use in label statements.
+ % This is used to give unique names to the case labels generated
+ % for dense switch statements.
+:- type label_num == int.
+:- pred ml_gen_info_new_label(label_num, ml_gen_info, ml_gen_info).
+:- mode ml_gen_info_new_label(out, in, out) is det.
+
% A number corresponding to an MLDS nested function which serves as a
% label (i.e. a continuation function).
:- type ml_label_func == mlds__func_sequence_num.
@@ -1200,6 +1213,10 @@
),
MLDS_Module = mercury_module_name_to_mlds(DefiningModule).
+ml_gen_new_label(Label) -->
+ ml_gen_info_new_label(LabelNum),
+ { string__format("label_%d", [i(LabelNum)], Label) }.
+
%-----------------------------------------------------------------------------%
%
% Code for dealing with variables
@@ -1679,6 +1696,7 @@
func_label :: mlds__func_sequence_num,
commit_label :: commit_sequence_num,
+ label :: label_num,
cond_var :: cond_seq,
conv_var :: conv_seq,
const_num :: const_seq,
@@ -1705,6 +1723,7 @@
ByRefOutputVars = select_output_vars(ModuleInfo, HeadVars, HeadModes,
VarTypes),
+ CaseLabelCounter = 0,
FuncLabelCounter = 0,
CommitLabelCounter = 0,
CondVarCounter = 0,
@@ -1722,6 +1741,7 @@
VarSet,
VarTypes,
ByRefOutputVars,
+ CaseLabelCounter,
FuncLabelCounter,
CommitLabelCounter,
CondVarCounter,
@@ -1756,6 +1776,9 @@
=(Info),
{ ml_gen_info_get_module_info(Info, ModuleInfo) },
{ module_info_globals(ModuleInfo, Globals) }.
+
+ml_gen_info_new_label(Label, Info, Info^label := Label) :-
+ Label = Info^label + 1.
ml_gen_info_new_func_label(Label, Info, Info^func_label := Label) :-
Label = Info^func_label + 1.
Index: compiler/ml_dense_switch.m
===================================================================
RCS file: ml_dense_switch.m
diff -N ml_dense_switch.m
--- /dev/null Thu Mar 30 14:06:13 2000
+++ ml_dense_switch.m Mon Nov 6 21:29:22 2000
@@ -0,0 +1,283 @@
+%-----------------------------------------------------------------------------%
+% Copyright (C) 1994-1999 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, type_util.
+:- import_module mlds, ml_switch_gen, 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, ml_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(ml_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(ml_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(ml_cases_list::in, int::in,
+ code_model::in, prog_context::in, mlds__label::in,
+ ml_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(ml_cases_list::in, int::in,
+ code_model::in, prog_context::in, ml_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.38
diff -u -d -r1.38 mlds.m
--- compiler/mlds.m 2000/11/01 05:12:04 1.38
+++ compiler/mlds.m 2000/11/05 22:31:49
@@ -554,6 +554,9 @@
:- type mlds__interface_id == mlds__type.
%-----------------------------------------------------------------------------%
+%
+% Declaration flags
+%
:- type mlds__decl_flags.
@@ -605,6 +608,9 @@
constness, abstractness) = mlds__decl_flags.
%-----------------------------------------------------------------------------%
+%
+% Foreign code interfacing
+%
%
% Foreign code required for the foreign language interface.
@@ -633,6 +639,9 @@
%-----------------------------------------------------------------------------%
+%
+% Contexts (i.e. source code locations)
+%
% mlds__context is probably == prog_context,
% but might also contain goal_path or other information.
@@ -643,6 +652,9 @@
:- func mlds__get_prog_context(mlds__context) = prog_context.
%-----------------------------------------------------------------------------%
+%
+% Statements
+%
:- type mlds__statements == list(mlds__statement).
@@ -672,19 +684,30 @@
%
% selection (see also computed_goto)
%
+
; if_then_else(mlds__rval, mlds__statement,
maybe(mlds__statement))
-/******
- % Is it worth including this? We already have `computed_goto'...
+ % This representation for switches is very general:
+ % it allows switching on any type, and cases can match
+ % on ranges as well as on values.
+ % Many target languages only allow switches on ints or enums.
+ % Some (e.g. C#) also allow switches on strings.
+ % Most target languages only allow matching on values;
+ % only some (e.g. GNU C) allow matching on ranges.
+ % Note that unlike C, MLDS cases do NOT fall through; if you
+ % want to achieve that effect, you need to use an explicit goto.
; switch(
+ % The value to switch on
+ mlds__type,
mlds__rval,
- % other representations might be better...
- assoc_list(mlds__rval, mlds__statement),
- mlds__statement % the default case
+ % The different cases
+ list(mlds__switch_case),
+
+ % What to do if none of the cases match
+ mlds__switch_default
)
-******/
%
% transfer of control
@@ -786,14 +809,67 @@
.
+%-----------------------------------------------------------------------------%
+%
+% Extra info for switches
+%
+
+ % 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_case == pair(mlds__case_match_conds, mlds__statement).
+ % case_match_conds should be a _non-empty_ list of conditions;
+ % if _any_ of the conditions match, this case will be selected.
+:- type mlds__case_match_conds == list(mlds__case_match_cond).
+
+ % A case_match_cond specifies when a switch case will be selected
+:- type mlds__case_match_cond
+ ---> match_value(mlds__rval) % match_value(Val) matches if
+ % the switch value is equal to
+ % the specified Val
+
+ ; match_range(mlds__rval, mlds__rval). % match_range(Min, Max)
+ % matches if the switch value
+ % is between Min and Max,
+ % inclusive
+
+ % The switch_default specifies what to do if none of the switch
+ % conditions match.
+:- type mlds__switch_default
+ ---> default_is_unreachable % The switch is exhaustive,
+ % so the default case should
+ % never be reached.
+
+ ; default_do_nothing % The default action is to
+ % just fall through to the
+ % statement after the switch.
+
+ ; default_case(mlds__statement). % The default is to execute
+ % the specified statement.
+
+%-----------------------------------------------------------------------------%
+%
+% Extra info for labels
+%
+
:- type mlds__label == string.
+%-----------------------------------------------------------------------------%
+%
+% Extra info for calls
+%
+
:- type is_tail_call
---> tail_call % a tail call
; call % just an ordinary call
.
+%-----------------------------------------------------------------------------%
+%
+% Extra info for exception handling
+%
% XXX This is tentative -- the current definition may be
% a bit too specific to C++-style exceptions.
@@ -810,6 +886,7 @@
% if `no', then exception value will not be used
).
+%-----------------------------------------------------------------------------%
%
% atomic statements
Index: compiler/mlds_to_c.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mlds_to_c.m,v
retrieving revision 1.63
diff -u -d -r1.63 mlds_to_c.m
--- compiler/mlds_to_c.m 2000/11/03 15:51:28 1.63
+++ compiler/mlds_to_c.m 2000/11/06 10:07:12
@@ -1872,6 +1872,17 @@
;
[]
).
+mlds_output_stmt(Indent, FuncInfo, switch(_Type, Val, Cases, Default),
+ Context) -->
+ mlds_indent(Context, Indent),
+ io__write_string("switch ("),
+ mlds_output_rval(Val),
+ io__write_string(") {\n"),
+ list__foldl(mlds_output_switch_case(Indent + 1, FuncInfo, Context),
+ Cases),
+ mlds_output_switch_default(Indent + 1, FuncInfo, Context, Default),
+ mlds_indent(Context, Indent),
+ io__write_string("}\n").
%
% transfer of control
@@ -1897,7 +1908,7 @@
mlds_indent(Indent),
io__write_string("switch ("),
mlds_output_rval(Expr),
- io__write_string(") {"),
+ io__write_string(") {\n"),
{ OutputLabel =
(pred(Label::in, Count0::in, Count::out, di, uo) is det -->
mlds_indent(Context, Indent + 1),
@@ -2053,8 +2064,8 @@
% <Handler>
%
- % XXX do we need to declare the local variables as volatile,
- % because of the setjmp()?
+ % XXX we need to declare the local variables as volatile,
+ % because of the setjmp()!
%
%
@@ -2082,6 +2093,56 @@
mlds_output_statement(Indent + 1, FuncInfo, Handler)
).
+%-----------------------------------------------------------------------------%
+
+%
+% Extra code for outputting switch statements
+%
+
+:- pred mlds_output_switch_case(indent, func_info, mlds__context,
+ mlds__switch_case, io__state, io__state).
+:- mode mlds_output_switch_case(in, in, in, in, di, uo) is det.
+
+mlds_output_switch_case(Indent, FuncInfo, Context, Case) -->
+ { Case = (Conds - Statement) },
+ list__foldl(mlds_output_case_cond(Indent, Context), Conds),
+ mlds_output_statement(Indent + 1, FuncInfo, Statement),
+ mlds_indent(Context, Indent + 1),
+ io__write_string("break;\n").
+
+:- pred mlds_output_case_cond(indent, mlds__context,
+ mlds__case_match_cond, io__state, io__state).
+:- mode mlds_output_case_cond(in, in, in, di, uo) is det.
+
+mlds_output_case_cond(Indent, Context, match_value(Val)) -->
+ mlds_indent(Context, Indent),
+ io__write_string("case "),
+ mlds_output_rval(Val),
+ io__write_string(":\n").
+mlds_output_case_cond(Indent, Context, match_range(Low, High)) -->
+ % This uses the GNU C extension `case <Low> ... <High>:'.
+ mlds_indent(Context, Indent),
+ io__write_string("case "),
+ mlds_output_rval(Low),
+ io__write_string(" ... "),
+ mlds_output_rval(High),
+ io__write_string(":\n").
+
+:- pred mlds_output_switch_default(indent, func_info, mlds__context,
+ mlds__switch_default, io__state, io__state).
+:- mode mlds_output_switch_default(in, in, in, in, di, uo) is det.
+
+mlds_output_switch_default(Indent, _FuncInfo, Context, default_is_unreachable) -->
+ mlds_indent(Context, Indent),
+ io__write_string("default: /*NOTREACHED*/ assert(0);\n").
+mlds_output_switch_default(_Indent, _FuncInfo, _Context, default_do_nothing) --> [].
+mlds_output_switch_default(Indent, FuncInfo, Context, default_case(Statement)) -->
+ mlds_indent(Context, Indent),
+ io__write_string("default:\n"),
+ mlds_output_statement(Indent + 1, FuncInfo, Statement).
+
+%-----------------------------------------------------------------------------%
+
%
% If memory profiling is turned on output an instruction to
% record the heap allocation.
@@ -2215,7 +2276,7 @@
mlds_indent(Indent),
io__write_string("/* "),
io__write_string(Comment),
- io__write_string(" */").
+ io__write_string(" */\n").
%
% assignment
Index: compiler/mlds_to_il.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mlds_to_il.m,v
retrieving revision 1.3
diff -u -d -r1.3 mlds_to_il.m
--- compiler/mlds_to_il.m 2000/10/22 07:27:20 1.3
+++ compiler/mlds_to_il.m 2000/11/06 00:42:10
@@ -758,6 +758,12 @@
instr_node(label(DoneLabel))
]) }.
+statement_to_il(statement(switch(_Type, _Val, _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.
+ { error("mlds_to_il.m: `switch' not supported") }.
+
statement_to_il(statement(while(Condition, Body, AtLeastOnce),
_Context), Instrs) -->
generate_condition(Condition, ConditionInstrs, EndLabel),
@@ -2166,7 +2172,7 @@
mangle_mlds_var(qual(ModuleName, MangledDataName), Id),
MLDSType0 = MLDSType
;
- error("definintion name was not data/1")
+ error("definition name was not data/1")
).
%-----------------------------------------------------------------------------%
Index: compiler/ml_elim_nested.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_elim_nested.m,v
retrieving revision 1.15
diff -u -d -r1.15 ml_elim_nested.m
--- compiler/ml_elim_nested.m 2000/10/22 13:57:38 1.15
+++ compiler/ml_elim_nested.m 2000/11/06 01:36:46
@@ -670,6 +670,12 @@
flatten_maybe_statement(MaybeElse0, MaybeElse),
{ Stmt = if_then_else(Cond, Then, MaybeElse) }
;
+ { Stmt0 = switch(Type, Val0, Cases0, Default0) },
+ fixup_rval(Val0, Val),
+ list__map_foldl(flatten_case, Cases0, Cases),
+ flatten_default(Default0, Default),
+ { Stmt = switch(Type, Val, Cases, Default) }
+ ;
{ Stmt0 = label(_) },
{ Stmt = Stmt0 }
;
@@ -706,6 +712,23 @@
{ Stmt = atomic(AtomicStmt) }
).
+:- pred flatten_case(mlds__switch_case, mlds__switch_case,
+ elim_info, elim_info).
+:- mode flatten_case(in, out, in, out) is det.
+
+flatten_case(Conds0 - Statement0, Conds - Statement) -->
+ list__map_foldl(fixup_case_cond, Conds0, Conds),
+ flatten_statement(Statement0, Statement).
+
+:- pred flatten_default(mlds__switch_default, mlds__switch_default,
+ elim_info, elim_info).
+:- mode flatten_default(in, out, in, out) is det.
+
+flatten_default(default_is_unreachable, default_is_unreachable) --> [].
+flatten_default(default_do_nothing, default_do_nothing) --> [].
+flatten_default(default_case(Statement0), default_case(Statement)) -->
+ flatten_statement(Statement0, Statement).
+
%-----------------------------------------------------------------------------%
%
@@ -837,10 +860,11 @@
%
% fixup_atomic_stmt:
+% fixup_case_cond:
+% fixup_trail_op:
% fixup_rvals:
% fixup_maybe_rval:
% fixup_rval:
-% fixup_trail_op:
% fixup_lvals:
% fixup_lval:
% Recursively process the specified construct, calling fixup_var on
@@ -873,6 +897,16 @@
target_code(Lang, Components)) -->
list__map_foldl(fixup_target_code_component,
Components0, Components).
+
+:- pred fixup_case_cond(mlds__case_match_cond, mlds__case_match_cond,
+ elim_info, elim_info).
+:- mode fixup_case_cond(in, out, in, out) is det.
+
+fixup_case_cond(match_value(Rval0), match_value(Rval)) -->
+ fixup_rval(Rval0, Rval).
+fixup_case_cond(match_range(Low0, High0), match_range(Low, High)) -->
+ fixup_rval(Low0, Low),
+ fixup_rval(High0, High).
:- pred fixup_target_code_component(target_code_component,
target_code_component, elim_info, elim_info).
Index: compiler/ml_optimize.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_optimize.m,v
retrieving revision 1.2
diff -u -d -r1.2 ml_optimize.m
--- compiler/ml_optimize.m 2000/09/17 09:18:57 1.2
+++ compiler/ml_optimize.m 2000/11/06 01:34:42
@@ -134,6 +134,11 @@
optimize_in_statement(OptInfo, Then),
maybe_apply(optimize_in_statement(OptInfo), MaybeElse))
;
+ Stmt0 = switch(Type, Rval, Cases0, Default0),
+ Stmt = switch(Type, Rval,
+ list__map(optimize_in_case(OptInfo), Cases0),
+ optimize_in_default(OptInfo, Default0))
+ ;
Stmt0 = do_commit(_),
Stmt = Stmt0
;
@@ -157,6 +162,19 @@
Stmt0 = atomic(_Atomic),
Stmt = Stmt0
).
+
+:- func optimize_in_case(opt_info, mlds__switch_case) = mlds__switch_case.
+
+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.
+
+optimize_in_default(_OptInfo, default_is_unreachable) = default_is_unreachable.
+optimize_in_default(_OptInfo, default_do_nothing) = default_do_nothing.
+optimize_in_default(OptInfo, default_case(Statement0)) =
+ default_case(Statement) :-
+ Statement = optimize_in_statement(OptInfo, Statement0).
:- func optimize_in_call_stmt(opt_info, mlds__stmt) = mlds__stmt.
Index: compiler/ml_switch_gen.m
===================================================================
RCS file: ml_switch_gen.m
diff -N ml_switch_gen.m
--- /dev/null Thu Mar 30 14:06:13 2000
+++ ml_switch_gen.m Tue Nov 7 00:43:58 2000
@@ -0,0 +1,454 @@
+%-----------------------------------------------------------------------------%
+% 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_switch_gen.m
+% Author: fjh (adapted from switch_gen.m)
+%
+% This module handles the generation of code for switches for the MLDS back-end.
+% Switches are disjunctions that do not require backtracking. They are
+% detected in switch_detection.m. This is the module that determines what
+% sort of indexing to use for each switch and then actually generates the
+% code. The code here is quite similar to the code in switch_gen.m, which
+% does the same thing for the LLDS back-end.
+%
+% The following describes the different forms of indexing that we could use.
+% Note that currently most of these are not implemented!
+% The ones that are not are marked NYI (for "not yet implemented").
+%
+% 1. For switches on atomic data types (int, char, enums), there are
+% several possibilities.
+% a) If all the alternative goals for a switch on an atomic data type
+% contain only construction unifications of constants, then we
+% should generate a dense lookup table (an array) for each output
+% variable of the switch, rather than computed goto, so that
+% executing the switch becomes a matter of doing an array index for
+% each output variable. (NYI)
+% b) If the cases are not sparse, and the target supports computed
+% gotos, we should use a computed_goto, unless the target supports
+% switch statements and the `--prefer-switch' option is set. (NYI)
+% c) If the target supports switch statements,
+% we generate an MLDS switch statement.
+%
+% 2. For switches on strings, there are several possibilities.
+% a) If the target supports indirect gotos, we should we lookup the
+% address to jump to in a hash table (e.g. using open addressing to
+% resolve hash collisions), and then jump to it using an indirect
+% goto, unless the target supports string switch statements and
+% the `--prefer-switch' option is set. (NYI)
+% c) If the target supports string switches,
+% we generate an MLDS switch statement.
+%
+% 3. For switches on discriminated union types, we generate code that does
+% indexing first on the primary tag, and then on the secondary tag (if
+% the primary tag is shared between several function symbols). The
+% indexing code for switches on both primary and secondary tags can be
+% in the form of a try-me-else chain, a try chain, a dense jump table
+% or a binary search. (NYI)
+%
+% For all other cases (or if the --smart-indexing option was
+% disabled), we just generate a chain of if-then-elses.
+%
+% TODO:
+% - implement the things marked NYI above
+% - optimize switches so that the recursive case comes first
+% (see switch_gen.m).
+%
+%-----------------------------------------------------------------------------%
+
+:- module ml_switch_gen.
+
+:- interface.
+
+:- import_module prog_data, hlds_goal, hlds_data, mlds, ml_code_util.
+:- import_module llds. % XXX for code_model
+
+:- import_module list.
+
+ % Generate MLDS code for a switch.
+ %
+:- pred ml_gen_switch(prog_var, can_fail, list(case), code_model, prog_context,
+ mlds__defns, mlds__statements,
+ ml_gen_info, ml_gen_info).
+:- mode ml_gen_switch(in, in, in, in, in, out, out, in, out) is det.
+
+% The following types are exported to the modules that implement
+% specialized kinds of switches.
+
+% An ml_extended_case is an HLDS case annotated with some additional info.
+:- type ml_extended_case ---> case(int, cons_tag, cons_id, hlds_goal).
+:- type ml_cases_list == list(ml_extended_case).
+
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+% These ones are not yet implemented yet:
+% :- import_module ml_string_switch, ml_tag_switch, ml_lookup_switch.
+:- import_module ml_dense_switch.
+:- import_module ml_code_gen, ml_unify_gen, ml_code_util, type_util.
+:- import_module globals, options.
+
+:- import_module bool, int, string, map, tree, std_util, require.
+
+:- type ml_switch_category
+ ---> atomic_switch % a switch on int/char/enum
+ ; string_switch
+ ; tag_switch
+ ; other_switch.
+
+%-----------------------------------------------------------------------------%
+
+ % Choose which method to use to generate the switch.
+ % CanFail says whether the switch covers all cases.
+
+ml_gen_switch(CaseVar, CanFail, Cases, CodeModel, Context,
+ MLDS_Decls, MLDS_Statements) -->
+ %
+ % Lookup the representation of the constructors for the tag tests
+ % and their corresponding priorities.
+ %
+ ml_switch_lookup_tags(Cases, CaseVar, TaggedCases0),
+ %
+ % Sort the cases according to the priority of their tag tests.
+ %
+ { list__sort_and_remove_dups(TaggedCases0, TaggedCases) },
+
+ %
+ % Figure out what kind of switch this is
+ %
+ ml_switch_gen__determine_category(CaseVar, SwitchCategory),
+ ml_gen_info_get_globals(Globals),
+ { globals__lookup_bool_option(Globals, smart_indexing, Indexing) },
+ (
+/**************
+XXX Lookup switches are NYI
+ { Indexing = yes },
+ { SwitchCategory = atomic_switch },
+ % Note that if/when the MLDS back-end supports execution
+ % tracing, we would also need to check that tracing is not
+ % enabled.
+ { list__length(TaggedCases, NumCases) },
+ { globals__lookup_int_option(Globals, lookup_switch_size,
+ LookupSize) },
+ { NumCases >= LookupSize },
+ { globals__lookup_int_option(Globals, lookup_switch_req_density,
+ ReqDensity) },
+ lookup_switch__is_lookup_switch(CaseVar, TaggedCases, GoalInfo,
+ CanFail, ReqDensity,
+ CodeModel, FirstVal, LastVal, NeedRangeCheck,
+ NeedBitVecCheck, OutVars, CaseVals)
+ ->
+ { MaybeEnd = MaybeEndPrime },
+ ml_lookup_switch__generate(CaseVar, OutVars, CaseVals,
+ FirstVal, LastVal, NeedRangeCheck, NeedBitVecCheck,
+ MLDS_Decls, MLDS_Statements)
+ ;
+**************/
+ %
+ % 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)
+ ;
+/**********
+XXX String hash switches are NYI
+ %
+ % Try using a string hash switch
+ %
+ { Indexing = yes },
+ { SwitchCategory = string_switch },
+ { list__length(TaggedCases, NumCases) },
+ { globals__lookup_int_option(Globals, string_switch_size,
+ StringSize) },
+ { NumCases >= StringSize }
+ ->
+ ml_string_switch__generate(TaggedCases, CaseVar, CodeModel,
+ CanFail, Context, MLDS_Decls, MLDS_Statements)
+ ;
+**********/
+/**********
+XXX Tag switches are NYI
+ %
+ % Try using a tag switch
+ %
+ { Indexing = yes },
+ { SwitchCategory = tag_switch },
+ { list__length(TaggedCases, NumCases) },
+ { globals__lookup_int_option(Globals, tag_switch_size,
+ TagSize) },
+ { NumCases >= TagSize }
+ ->
+ ml_tag_switch__generate(TaggedCases, CaseVar, CodeModel, CanFail,
+ Context, MLDS_Decls, MLDS_Statements)
+ ;
+**********/
+ %
+ % Try using a "direct-mapped" switch
+ %
+ { Indexing = yes },
+ { target_supports_switch(SwitchCategory, Globals) }
+ ->
+ ml_switch_generate_mlds_switch(TaggedCases, CaseVar,
+ CodeModel, CanFail, Context,
+ MLDS_Decls, MLDS_Statements)
+ ;
+ %
+ % The fallback method: if all else fails, generate an
+ % if-then-else chain which tests each of the cases in turn.
+ %
+ ml_switch_generate_if_else_chain(TaggedCases, CaseVar,
+ CodeModel, CanFail, Context,
+ MLDS_Decls, MLDS_Statements)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+:- pred target_supports_switch(ml_switch_category::in, globals::in)
+ is semidet.
+target_supports_switch(SwitchCategory, Globals) :-
+ (
+ SwitchCategory = atomic_switch,
+ target_supports_int_switch(Globals)
+ ;
+ SwitchCategory = string_switch,
+ target_supports_string_switch(Globals)
+ ).
+
+:- pred target_supports_int_switch(globals::in) is semidet.
+:- pred target_supports_string_switch(globals::in) is semidet.
+:- pred target_supports_computed_goto(globals::in) is semidet.
+
+target_supports_int_switch(Globals) :-
+ globals__get_target(Globals, Target),
+ target_supports_int_switch_2(Target) = yes.
+
+target_supports_string_switch(Globals) :-
+ globals__get_target(Globals, Target),
+ target_supports_string_switch_2(Target) = yes.
+
+target_supports_computed_goto(Globals) :-
+ globals__get_target(Globals, Target),
+ target_supports_computed_goto_2(Target) = yes.
+
+:- func target_supports_int_switch_2(compilation_target) = bool.
+:- func target_supports_string_switch_2(compilation_target) = bool.
+:- func target_supports_computed_goto_2(compilation_target) = bool.
+
+target_supports_int_switch_2(c) = yes.
+target_supports_int_switch_2(il) = no.
+target_supports_int_switch_2(java) = yes.
+% target_supports_int_switch_2(c_sharp) = yes.
+
+target_supports_string_switch_2(c) = no.
+target_supports_string_switch_2(il) = no.
+target_supports_string_switch_2(java) = no.
+% target_supports_string_switch_2(c_sharp) = yes.
+
+target_supports_computed_goto_2(c) = yes.
+target_supports_computed_goto_2(il) = yes.
+target_supports_computed_goto_2(java) = no.
+% target_supports_computed_goto_2(c_sharp) = yes.
+
+%-----------------------------------------------------------------------------%
+
+ % We categorize switches according to whether the value
+ % being switched on is an atomic type, a string, or
+ % something more complicated.
+
+:- pred ml_switch_gen__determine_category(prog_var, ml_switch_category,
+ ml_gen_info, ml_gen_info).
+:- mode ml_switch_gen__determine_category(in, out, in, out) is det.
+
+ml_switch_gen__determine_category(CaseVar, SwitchCategory) -->
+ ml_variable_type(CaseVar, Type),
+ =(MLGenInfo),
+ { ml_gen_info_get_module_info(MLGenInfo, ModuleInfo) },
+ { type_util__classify_type(Type, ModuleInfo, TypeCategory) },
+ { ml_switch_gen__type_cat_to_switch_cat(TypeCategory, SwitchCategory) }.
+
+:- pred ml_switch_gen__type_cat_to_switch_cat(builtin_type, ml_switch_category).
+:- mode ml_switch_gen__type_cat_to_switch_cat(in, out) is det.
+
+ml_switch_gen__type_cat_to_switch_cat(enum_type, atomic_switch).
+ml_switch_gen__type_cat_to_switch_cat(int_type, atomic_switch).
+ml_switch_gen__type_cat_to_switch_cat(char_type, atomic_switch).
+ml_switch_gen__type_cat_to_switch_cat(float_type, other_switch).
+ml_switch_gen__type_cat_to_switch_cat(str_type, string_switch).
+ml_switch_gen__type_cat_to_switch_cat(pred_type, other_switch).
+ml_switch_gen__type_cat_to_switch_cat(user_type, tag_switch).
+ml_switch_gen__type_cat_to_switch_cat(polymorphic_type, other_switch).
+ml_switch_gen__type_cat_to_switch_cat(tuple_type, other_switch).
+
+%-----------------------------------------------------------------------------%
+
+ % Look up the representation (tag) for the cons_id in each case.
+ % Also look up the priority of each tag test.
+ %
+:- pred ml_switch_lookup_tags(list(case), prog_var, ml_cases_list,
+ ml_gen_info, ml_gen_info).
+:- mode ml_switch_lookup_tags(in, in, out, in, out) is det.
+
+ml_switch_lookup_tags([], _, []) --> [].
+ml_switch_lookup_tags([Case | Cases], Var, [TaggedCase | TaggedCases]) -->
+ { Case = case(ConsId, Goal) },
+ ml_variable_type(Var, Type),
+ ml_cons_id_to_tag(ConsId, Type, Tag),
+ { ml_switch_priority(Tag, Priority) },
+ { TaggedCase = case(Priority, Tag, ConsId, Goal) },
+ ml_switch_lookup_tags(Cases, Var, TaggedCases).
+
+ % Return the priority of a tag test.
+ % A low number here indicates a high priority.
+ % We prioritize the tag tests so that the cheapest
+ % (most efficient) ones come first.
+ %
+:- pred ml_switch_priority(cons_tag, int).
+:- mode ml_switch_priority(in, out) is det.
+
+ml_switch_priority(no_tag, 0). % should never occur
+ml_switch_priority(int_constant(_), 1).
+ml_switch_priority(shared_local_tag(_, _), 1).
+ml_switch_priority(unshared_tag(_), 2).
+ml_switch_priority(float_constant(_), 3).
+ml_switch_priority(shared_remote_tag(_, _), 4).
+ml_switch_priority(string_constant(_), 5).
+ % The following tags should all never occur in switches.
+ml_switch_priority(pred_closure_tag(_, _, _), 6).
+ml_switch_priority(code_addr_constant(_, _), 6).
+ml_switch_priority(type_ctor_info_constant(_, _, _), 6).
+ml_switch_priority(base_typeclass_info_constant(_, _, _), 6).
+ml_switch_priority(tabling_pointer_constant(_, _), 6).
+
+%-----------------------------------------------------------------------------%
+
+ % Generate a chain of if-then-elses to test each case in turn.
+ %
+:- pred ml_switch_generate_if_else_chain(list(ml_extended_case), prog_var,
+ code_model, can_fail, prog_context, mlds__defns, mlds__statements,
+ ml_gen_info, ml_gen_info).
+:- mode ml_switch_generate_if_else_chain(in, in, in, in, in, out, out,
+ in, out) is det.
+
+ml_switch_generate_if_else_chain([], _Var, CodeModel, CanFail, Context,
+ [], MLDS_Statements) -->
+ ( { CanFail = can_fail } ->
+ ml_gen_failure(CodeModel, Context, MLDS_Statements)
+ ;
+ { error("switch failure") }
+ ).
+ml_switch_generate_if_else_chain([Case | Cases], Var, CodeModel, CanFail,
+ Context, MLDS_Decls, MLDS_Statements) -->
+ { Case = case(_, _Tag, ConsId, Goal) },
+ (
+ { Cases = [], CanFail = cannot_fail }
+ ->
+ ml_gen_goal(CodeModel, Goal, MLDS_Decls, MLDS_Statements)
+ ;
+ ml_gen_tag_test(Var, ConsId, TagTestDecls, TagTestStatements,
+ TagTestExpression),
+ ml_gen_goal(CodeModel, Goal, GoalStatement),
+ ml_switch_generate_if_else_chain(Cases, Var, CodeModel,
+ CanFail, Context, RestDecls, RestStatements),
+ { Rest = ml_gen_block(RestDecls, RestStatements, Context) },
+ { IfStmt = if_then_else(TagTestExpression,
+ GoalStatement, yes(Rest)) },
+ { IfStatement = mlds__statement(IfStmt,
+ mlds__make_context(Context)) },
+ { MLDS_Decls = TagTestDecls },
+ { MLDS_Statements = list__append(TagTestStatements,
+ [IfStatement]) }
+ ).
+
+%-----------------------------------------------------------------------------%
+
+ % Generate an MLDS switch.
+ % This is used for "direct-mapped" switches, where we map a
+ % Mercury switch directly to a switch in the target language.
+ %
+:- pred ml_switch_generate_mlds_switch(list(ml_extended_case), prog_var,
+ code_model, can_fail, prog_context, mlds__defns, mlds__statements,
+ ml_gen_info, ml_gen_info).
+:- mode ml_switch_generate_mlds_switch(in, in, in, in, in, out, out,
+ in, out) is det.
+
+ml_switch_generate_mlds_switch(Cases, Var, CodeModel, CanFail,
+ Context, MLDS_Decls, MLDS_Statements) -->
+ ml_variable_type(Var, Type),
+ ml_gen_type(Type, MLDS_Type),
+ ml_gen_var(Var, Lval),
+ { Rval = mlds__lval(Lval) },
+ 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)) },
+ { MLDS_Decls = [] },
+ { MLDS_Statements = [SwitchStatement] }.
+
+:- pred ml_switch_generate_mlds_cases(list(ml_extended_case),
+ code_model, list(mlds__switch_case), ml_gen_info, ml_gen_info).
+:- mode ml_switch_generate_mlds_cases(in, in, out, in, out) is det.
+
+ml_switch_generate_mlds_cases([], _, []) --> [].
+ml_switch_generate_mlds_cases([Case | Cases], CodeModel,
+ [MLDS_Case | MLDS_Cases]) -->
+ ml_switch_generate_mlds_case(Case, CodeModel, MLDS_Case),
+ ml_switch_generate_mlds_cases(Cases, CodeModel, MLDS_Cases).
+
+:- pred ml_switch_generate_mlds_case(ml_extended_case, code_model,
+ mlds__switch_case, ml_gen_info, ml_gen_info).
+:- mode ml_switch_generate_mlds_case(in, in, out, in, out) is det.
+
+ml_switch_generate_mlds_case(Case, CodeModel, MLDS_Case) -->
+ { Case = case(_Priority, Tag, _ConsId, Goal) },
+ ( { Tag = int_constant(Int) } ->
+ { Rval = const(int_const(Int)) }
+ ; { Tag = string_constant(String) } ->
+ { Rval = const(string_const(String)) }
+ ;
+ { error("ml_switch_gen.m: invalid tag type") }
+ ),
+ ml_gen_goal(CodeModel, Goal, MLDS_Statement),
+ { MLDS_Case = [match_value(Rval)] - MLDS_Statement }.
+
+:- pred ml_switch_generate_default(can_fail::in, code_model::in,
+ prog_context::in, switch_default::out,
+ ml_gen_info::in, ml_gen_info::out) is det.
+
+ml_switch_generate_default(CanFail, CodeModel, Context, Default) -->
+ (
+ { CanFail = can_fail },
+ ml_gen_failure(CodeModel, Context, FailStatements),
+ ( { FailStatements = [] } ->
+ { Default = default_do_nothing }
+ ;
+ { Fail = ml_gen_block([], FailStatements, Context) },
+ { Default = default_case(Fail) }
+ )
+ ;
+ { CanFail = cannot_fail },
+ { Default = default_is_unreachable }
+ ).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
Index: compiler/ml_tailcall.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_tailcall.m,v
retrieving revision 1.3
diff -u -d -r1.3 ml_tailcall.m
--- compiler/ml_tailcall.m 2000/08/31 03:00:21 1.3
+++ compiler/ml_tailcall.m 2000/11/06 01:38:19
@@ -96,7 +96,8 @@
% mark_tailcalls_in_statements:
% mark_tailcalls_in_statement:
% mark_tailcalls_in_stmt:
-% mark_tailcalls_in_atomic_stmt:
+% mark_tailcalls_in_case:
+% mark_tailcalls_in_default:
% Recursively process the statement(s),
% marking each optimizable tail call in them as a tail call.
% The `AtTail' argument indicates whether or not this
@@ -228,6 +229,16 @@
AtTail, Locals),
Stmt = if_then_else(Cond, Then, MaybeElse)
;
+ %
+ % All of the cases of a switch (including the default)
+ % are in a tail position iff the switch is in a
+ % tail position.
+ %
+ Stmt0 = switch(Type, Val, Cases0, Default0),
+ Cases = mark_tailcalls_in_cases(Cases0, AtTail, Locals),
+ Default = mark_tailcalls_in_default(Default0, AtTail, Locals),
+ Stmt = switch(Type, Val, Cases, Default)
+ ;
Stmt0 = label(_),
Stmt = Stmt0
;
@@ -288,6 +299,32 @@
Stmt0 = atomic(_),
Stmt = Stmt0
).
+
+:- func mark_tailcalls_in_cases(list(mlds__switch_case), at_tail, locals) =
+ list(mlds__switch_case).
+
+mark_tailcalls_in_cases([], _, _) = [].
+mark_tailcalls_in_cases([Case0 | Cases0], AtTail, Locals) =
+ [Case | Cases] :-
+ Case = mark_tailcalls_in_case(Case0, AtTail, Locals),
+ Cases = mark_tailcalls_in_cases(Cases0, AtTail, Locals).
+
+:- func mark_tailcalls_in_case(mlds__switch_case, at_tail, locals) =
+ mlds__switch_case.
+
+mark_tailcalls_in_case(Cond - Statement0, AtTail, Locals) =
+ Cond - Statement :-
+ Statement = mark_tailcalls_in_statement(Statement0, AtTail, Locals).
+
+:- func mark_tailcalls_in_default(mlds__switch_default, at_tail, locals) =
+ mlds__switch_default.
+
+mark_tailcalls_in_default(default_do_nothing, _, _) = default_do_nothing.
+mark_tailcalls_in_default(default_is_unreachable, _, _) =
+ default_is_unreachable.
+mark_tailcalls_in_default(default_case(Statement0), AtTail, Locals) =
+ default_case(Statement) :-
+ Statement = mark_tailcalls_in_statement(Statement0, AtTail, Locals).
%-----------------------------------------------------------------------------%
Index: compiler/options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/options.m,v
retrieving revision 1.296
diff -u -d -r1.296 options.m
--- compiler/options.m 2000/11/03 06:12:20 1.296
+++ compiler/options.m 2000/11/06 13:35:00
@@ -281,6 +281,7 @@
% percentage.
; gcc_local_labels
+ ; prefer_switch
% Optimization Options
; opt_level
@@ -631,7 +632,8 @@
% 0 indicates any size.
fact_table_max_array_size - int(1024),
fact_table_hash_percent_full - int(90),
- gcc_local_labels - bool(no)
+ gcc_local_labels - bool(no),
+ prefer_switch - bool(yes)
]).
option_defaults_2(special_optimization_option, [
% Special optimization options.
@@ -1006,6 +1008,7 @@
long_option("fact-table-hash-percent-full",
fact_table_hash_percent_full).
long_option("gcc-local-labels", gcc_local_labels).
+long_option("prefer-switch", prefer_switch).
% optimization options
@@ -2118,6 +2121,17 @@
% "\tvia a `goto'.",
% "\tIf this option is not enabled, the default behaviour is to",
% "\tuse the standard ANSI/ISO C setjmp() and longjmp() functions."
+
+% This option is not yet documented because it is not yet useful -- currently
+% we don't take advantage of GNU C's computed gotos extension.
+% "--no-prefer-switch",
+% "\tGenerate code using computed gotos rather than switches.",
+% "\tThis makes the generated code less readable, but potentially",
+% "\tslightly more efficient.",
+% "\tThis option has no effect unless the `--high-level-code' option",
+% "\tis enabled. It also has no effect if the `--target' option is",
+% "\tset to `il'.",
+
]),
io__write_string("\n Code generation target options:\n"),
--
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