[m-rev.] diff: implement binary search switches for string in the MLDS
Zoltan Somogyi
zs at csse.unimelb.edu.au
Tue Aug 2 13:01:07 AEST 2011
Implement binary search switches for strings in the MLDS backend (they already
exist in the LLDS backend). Binary search switches have higher big-O
complexity than hash table search switches, but lower startup costs,
and so are appropriate for switches involving a smaller tables of strings.
compiler/ml_string_switch.m:
Implement binary search switches.
Where possible, factor out and reuse code that already existed for
implementing hash switches.
compiler/ml_switch_gen.m:
Invoke the new code when appropriate.
compiler/switch_gen.m:
Avoid executing the same test (NumArms > 1) more than once.
compiler/mlds.m:
Fix a typo in a comment.
compiler/string_switch.m:
Delete stray text from a comment.
Zoltan.
cvs diff: Diffing .
cvs diff: Diffing analysis
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/doc
cvs diff: Diffing boehm_gc/extra
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/extra
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing boehm_gc/libatomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops/doc
cvs diff: Diffing boehm_gc/libatomic_ops/src
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/armcc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/gcc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/hpc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/ibmc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/icc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/msftc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/sunc
cvs diff: Diffing boehm_gc/libatomic_ops/tests
cvs diff: Diffing boehm_gc/libatomic_ops-1.2
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/doc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/tests
cvs diff: Diffing boehm_gc/m4
cvs diff: Diffing boehm_gc/tests
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/ml_string_switch.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/ml_string_switch.m,v
retrieving revision 1.53
diff -u -b -r1.53 ml_string_switch.m
--- compiler/ml_string_switch.m 2 Aug 2011 00:05:40 -0000 1.53
+++ compiler/ml_string_switch.m 2 Aug 2011 00:06:52 -0000
@@ -7,10 +7,14 @@
%-----------------------------------------------------------------------------%
%
% File: ml_string_switch.m.
-% Author: fjh (adapted from string_switch.m)
+% Authors: fjh, zs.
%
-% For switches on strings, we generate a hash table using open addressing
-% to resolve hash conflicts.
+% For switches on strings, we can generate either
+% - a hash table using open addressing to resolve hash conflicts, or
+% - a sorted table for binary search.
+%
+% The hash table has a higher startup cost, but should use fewer comparisons,
+% so it is preferred for bigger tables.
%
% WARNING: the code here is quite similar to the code in string_switch.m.
% Any changes here may require similar changes there and vice versa.
@@ -28,7 +32,12 @@
:- import_module list.
-:- pred ml_generate_string_switch(list(tagged_case)::in, prog_var::in,
+:- pred ml_generate_string_hash_switch(list(tagged_case)::in, prog_var::in,
+ code_model::in, can_fail::in, prog_context::in,
+ list(mlds_defn)::out, list(statement)::out,
+ ml_gen_info::in, ml_gen_info::out) is det.
+
+:- pred ml_generate_string_binary_switch(list(tagged_case)::in, prog_var::in,
code_model::in, can_fail::in, prog_context::in,
list(mlds_defn)::out, list(statement)::out,
ml_gen_info::in, ml_gen_info::out) is det.
@@ -55,12 +64,14 @@
:- import_module pair.
:- import_module require.
:- import_module string.
+:- import_module term.
:- import_module unit.
%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
-ml_generate_string_switch(Cases, Var, CodeModel, _CanFail, Context,
- Decls, Statements, !Info) :-
+ml_generate_string_hash_switch(Cases, Var, CodeModel, CanFail, Context,
+ Defns, Statements, !Info) :-
MLDS_Context = mlds_make_context(Context),
ml_gen_var(!.Info, Var, VarLval),
VarRval = ml_lval(VarLval),
@@ -88,7 +99,6 @@
StringVarType, StringVarGCStatement, MLDS_Context),
ml_gen_var_lval(!.Info, StringVar, StringVarType, StringVarLval),
- % Generate new labels.
ml_gen_new_label(EndLabel, !Info),
GotoEndStatement =
statement(ml_stmt_goto(goto_label(EndLabel)), MLDS_Context),
@@ -102,23 +112,8 @@
HashMask = TableSize - 1,
% Generate the code for when the hash lookup fails.
- (
- CodeModel = model_det,
- % This can happen if the initial inst of the switched-on variable
- % shows that we know a finite set of strings that the variable can be
- % bound to.
- FailComment =
- statement(ml_stmt_atomic(comment("switch cannot fail")),
- MLDS_Context),
- FailStatements = []
- ;
- ( CodeModel = model_semi
- ; CodeModel = model_non
- ),
- FailComment = statement(ml_stmt_atomic(comment("no match, so fail")),
- MLDS_Context),
- ml_gen_failure(CodeModel, Context, FailStatements, !Info)
- ),
+ ml_gen_maybe_switch_failure(CodeModel, CanFail, Context, MLDS_Context,
+ FailStatements, !Info),
ml_gen_info_get_module_info(!.Info, ModuleInfo),
module_info_get_name(ModuleInfo, ModuleName),
@@ -263,10 +258,9 @@
% Collect all the generated variable declarations and code fragments
% together.
- Decls = [SlotVarDefn, StringVarDefn],
+ Defns = [SlotVarDefn, StringVarDefn],
Statements =
- HashLookupStatements ++
- [FailComment | FailStatements] ++
+ HashLookupStatements ++ FailStatements ++
[EndLabelStatement, EndComment].
%-----------------------------------------------------------------------------%
@@ -300,6 +294,16 @@
unexpected($module, $pred, "non-string tag")
).
+:- pred gen_tagged_case_code_for_string_switch_dummy(code_model::in,
+ tagged_case::in, int::out,
+ map(int, statement)::in, map(int, statement)::out,
+ ml_gen_info::in, ml_gen_info::out, unit::in, unit::out) is det.
+
+gen_tagged_case_code_for_string_switch_dummy(CodeModel, TaggedCase, CaseNum,
+ !CodeMap, !Info, !Dummy) :-
+ gen_tagged_case_code_for_string_switch(CodeModel, TaggedCase, CaseNum,
+ !CodeMap, !Info).
+
:- pred gen_tagged_case_code_for_string_switch(code_model::in, tagged_case::in,
int::out, map(int, statement)::in, map(int, statement)::out,
ml_gen_info::in, ml_gen_info::out) is det.
@@ -423,5 +427,252 @@
make_hash_match(Slot) = match_value(ml_const(mlconst_int(Slot))).
%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+ml_generate_string_binary_switch(Cases, Var, CodeModel, CanFail, Context,
+ Defns, Statements, !Info) :-
+ MLDS_Context = mlds_make_context(Context),
+ ml_gen_var(!.Info, Var, VarLval),
+ VarRval = ml_lval(VarLval),
+
+ ml_gen_string_binary_switch_search_vars(MLDS_Context, LoVarLval, HiVarLval,
+ MidVarLval, ResultVarLval, Defns, !Info),
+
+ % Generate the code for when the hash lookup fails.
+ ml_gen_maybe_switch_failure(CodeModel, CanFail, Context, MLDS_Context,
+ FailStatements, !Info),
+
+ ml_gen_info_get_module_info(!.Info, ModuleInfo),
+ module_info_get_name(ModuleInfo, ModuleName),
+ MLDS_ModuleName = mercury_module_name_to_mlds(ModuleName),
+ ml_gen_info_get_target(!.Info, Target),
+
+ MLDS_StringType = mercury_type_to_mlds_type(ModuleInfo, string_type),
+ MLDS_CaseNumType = mlds_native_int_type,
+ MLDS_ArgTypes = [MLDS_StringType, MLDS_CaseNumType],
+
+ % Generate the binary search table.
+ ml_gen_info_get_global_data(!.Info, GlobalData0),
+ ml_gen_static_vector_type(MLDS_ModuleName, MLDS_Context, Target,
+ MLDS_ArgTypes, StructTypeNum, StructType, FieldIds,
+ GlobalData0, GlobalData1),
+ ml_gen_info_set_global_data(GlobalData1, !Info),
+ ( FieldIds = [StringFieldIdPrime, CaseNumFieldIdPrime] ->
+ StringFieldId = StringFieldIdPrime,
+ CaseNumFieldId = CaseNumFieldIdPrime
+ ;
+ unexpected($module, $pred, "bad FieldIds")
+ ),
+ map.init(CaseLabelMap0),
+ switch_util.string_binary_cases(Cases,
+ gen_tagged_case_code_for_string_switch_dummy(CodeModel),
+ CaseLabelMap0, CaseLabelMap, !Info, unit, _, SortedTable),
+ ml_gen_string_binary_jump_initializers(SortedTable, StructType,
+ [], RevRowInitializers, 0, TableSize),
+ list.reverse(RevRowInitializers, RowInitializers),
+ % We need to get the globaldata out of !Info again, since the generation
+ % of code for the switch arms can generate global data.
+ ml_gen_info_get_global_data(!.Info, GlobalData2),
+ ml_gen_static_vector_defn(MLDS_ModuleName, StructTypeNum, RowInitializers,
+ VectorCommon, GlobalData2, GlobalData),
+ ml_gen_info_set_global_data(GlobalData, !Info),
+
+ % Generate the switch that uses the final value of MidVar (the one that,
+ % when used as an index into the binary search table, matches the current
+ % value of the switched-on variable) to select the piece of code to
+ % execute.
+ map.to_assoc_list(CaseLabelMap, CaseLabelList),
+ ml_gen_string_binary_jump_switch_arms(CaseLabelList, [], SwitchCases0),
+ list.sort(SwitchCases0, SwitchCases),
+ SwitchStmt0 = ml_stmt_switch(mlds_native_int_type,
+ ml_lval(ml_field(yes(0),
+ ml_vector_common_row(VectorCommon, ml_lval(MidVarLval)),
+ CaseNumFieldId, MLDS_StringType, StructType)),
+ mlds_switch_range(0, TableSize - 1), SwitchCases,
+ default_is_unreachable),
+ ml_simplify_switch(SwitchStmt0, MLDS_Context, SwitchStatement, !Info),
+
+ ml_gen_new_label(EndLabel, !Info),
+ GotoEndStatement =
+ statement(ml_stmt_goto(goto_label(EndLabel)), MLDS_Context),
+ SuccessStatement =
+ statement(ml_stmt_block([], [SwitchStatement, GotoEndStatement]),
+ MLDS_Context),
+
+ % Generate the code that searches the table.
+ ml_gen_string_binary_switch_search(MLDS_Context, VarRval,
+ LoVarLval, HiVarLval, MidVarLval, ResultVarLval, VectorCommon,
+ TableSize, StructType, StringFieldId,
+ SuccessStatement, LookupStatements, !.Info),
+ EndLabelStatement =
+ statement(ml_stmt_label(EndLabel), MLDS_Context),
+ Statements = LookupStatements ++ FailStatements ++ [EndLabelStatement].
+
+:- pred ml_gen_string_binary_jump_initializers(assoc_list(string, int)::in,
+ mlds_type::in,
+ list(mlds_initializer)::in, list(mlds_initializer)::out,
+ int::in, int::out) is det.
+
+ml_gen_string_binary_jump_initializers([],
+ _StructType, !RevRowInitializers, !CurIndex).
+ml_gen_string_binary_jump_initializers([Str - CaseNum | StrCaseNums],
+ StructType, !RevRowInitializers, !CurIndex) :-
+ StrRval = ml_const(mlconst_string(Str)),
+ CaseNumRval = ml_const(mlconst_int(CaseNum)),
+ RowInitializer = init_struct(StructType,
+ [init_obj(StrRval), init_obj(CaseNumRval)]),
+ !:RevRowInitializers = [RowInitializer | !.RevRowInitializers],
+ !:CurIndex = !.CurIndex + 1,
+ ml_gen_string_binary_jump_initializers(StrCaseNums,
+ StructType, !RevRowInitializers, !CurIndex).
+
+:- pred ml_gen_string_binary_jump_switch_arms(assoc_list(int, statement)::in,
+ list(mlds_switch_case)::in, list(mlds_switch_case)::out) is det.
+
+ml_gen_string_binary_jump_switch_arms([], !SwitchCases).
+ml_gen_string_binary_jump_switch_arms([CaseNumStmt | CaseNumsStmts],
+ !SwitchCases) :-
+ CaseNumStmt = CaseNum - Statement,
+ MatchCond = match_value(ml_const(mlconst_int(CaseNum))),
+ SwitchCase = mlds_switch_case(MatchCond, [], Statement),
+ !:SwitchCases = [SwitchCase | !.SwitchCases],
+ ml_gen_string_binary_jump_switch_arms(CaseNumsStmts, !SwitchCases).
+
+:- pred ml_gen_string_binary_switch_search_vars(mlds_context::in,
+ mlds_lval::out, mlds_lval::out, mlds_lval::out, mlds_lval::out,
+ list(mlds_defn)::out, ml_gen_info::in, ml_gen_info::out) is det.
+
+ml_gen_string_binary_switch_search_vars(MLDS_Context, LoVarLval, HiVarLval,
+ MidVarLval, ResultVarLval, Defns, !Info) :-
+ % Generate the following local variable declarations:
+ % int lo;
+ % int hi;
+ % int mid;
+ % MR_String str;
+
+ IndexType = mlds_native_int_type,
+ ResultType = mlds_native_int_type,
+ % We never need to trace ints.
+ IndexGCStatement = gc_no_stmt,
+ ResultGCStatement = gc_no_stmt,
+
+ ml_gen_info_new_aux_var_name("lo", LoVar, !Info),
+ LoVarDefn = ml_gen_mlds_var_decl(mlds_data_var(LoVar), IndexType,
+ IndexGCStatement, MLDS_Context),
+ ml_gen_var_lval(!.Info, LoVar, IndexType, LoVarLval),
+
+ ml_gen_info_new_aux_var_name("hi", HiVar, !Info),
+ HiVarDefn = ml_gen_mlds_var_decl(mlds_data_var(HiVar), IndexType,
+ IndexGCStatement, MLDS_Context),
+ ml_gen_var_lval(!.Info, HiVar, IndexType, HiVarLval),
+
+ ml_gen_info_new_aux_var_name("mid", MidVar, !Info),
+ MidVarDefn = ml_gen_mlds_var_decl(mlds_data_var(MidVar), IndexType,
+ IndexGCStatement, MLDS_Context),
+ ml_gen_var_lval(!.Info, MidVar, IndexType, MidVarLval),
+
+ ml_gen_info_new_aux_var_name("result", ResultVar, !Info),
+ ResultVarDefn = ml_gen_mlds_var_decl(mlds_data_var(ResultVar), ResultType,
+ ResultGCStatement, MLDS_Context),
+ ml_gen_var_lval(!.Info, ResultVar, ResultType, ResultVarLval),
+
+ Defns = [LoVarDefn, HiVarDefn, MidVarDefn, ResultVarDefn].
+
+:- pred ml_gen_string_binary_switch_search(mlds_context::in, mlds_rval::in,
+ mlds_lval::in, mlds_lval::in, mlds_lval::in, mlds_lval::in,
+ mlds_vector_common::in, int::in, mlds_type::in, mlds_field_id::in,
+ statement::in, list(statement)::out,
+ ml_gen_info::in) is det.
+
+ml_gen_string_binary_switch_search(MLDS_Context, VarRval, LoVarLval, HiVarLval,
+ MidVarLval, ResultVarLval, VectorCommon, TableSize,
+ StructType, StringFieldId, SuccessStatement, Statements, Info) :-
+ ml_gen_info_get_module_info(Info, ModuleInfo),
+ MLDS_StringType = mercury_type_to_mlds_type(ModuleInfo, string_type),
+
+ LoopBodyStatements = [
+ statement(ml_stmt_atomic(
+ assign(MidVarLval,
+ ml_binop(int_div,
+ ml_binop(int_add, ml_lval(LoVarLval), ml_lval(HiVarLval)),
+ ml_const(mlconst_int(2))))),
+ MLDS_Context),
+ statement(ml_stmt_atomic(
+ assign(ResultVarLval,
+ ml_binop(str_cmp,
+ VarRval,
+ ml_lval(ml_field(yes(0),
+ ml_vector_common_row(VectorCommon,
+ ml_lval(MidVarLval)),
+ StringFieldId, MLDS_StringType, StructType))))),
+ MLDS_Context),
+ statement(ml_stmt_if_then_else(
+ ml_binop(eq,
+ ml_lval(ResultVarLval),
+ ml_const(mlconst_int(0))),
+ SuccessStatement,
+ yes(statement(
+ ml_stmt_if_then_else(
+ ml_binop(int_le,
+ ml_lval(ResultVarLval),
+ ml_const(mlconst_int(0))),
+ statement(ml_stmt_atomic(
+ assign(HiVarLval,
+ ml_binop(int_sub,
+ ml_lval(MidVarLval),
+ ml_const(mlconst_int(1))))),
+ MLDS_Context),
+ yes(statement(ml_stmt_atomic(
+ assign(LoVarLval,
+ ml_binop(int_add,
+ ml_lval(MidVarLval),
+ ml_const(mlconst_int(1))))),
+ MLDS_Context))),
+ MLDS_Context))),
+ MLDS_Context)
+ ],
+ Statements = [
+ statement(ml_stmt_atomic(
+ assign(LoVarLval, ml_const(mlconst_int(0)))),
+ MLDS_Context),
+ statement(ml_stmt_atomic(
+ assign(HiVarLval, ml_const(mlconst_int(TableSize - 1)))),
+ MLDS_Context),
+ statement(ml_stmt_while(may_loop_zero_times,
+ ml_binop(int_le,
+ ml_lval(LoVarLval),
+ ml_lval(HiVarLval)),
+ statement(ml_stmt_block([], LoopBodyStatements),
+ MLDS_Context)),
+ MLDS_Context)
+ ].
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- pred ml_gen_maybe_switch_failure(code_model::in, can_fail::in,
+ term.context::in, mlds_context::in, list(statement)::out,
+ ml_gen_info::in, ml_gen_info::out) is det.
+
+ml_gen_maybe_switch_failure(CodeModel, CanFail, Context, MLDS_Context,
+ FailStatements, !Info) :-
+ (
+ CanFail = cannot_fail,
+ % This can happen if the initial inst of the switched-on variable
+ % shows that we know a finite set of strings that the variable can be
+ % bound to.
+ FailComment =
+ statement(ml_stmt_atomic(comment("switch cannot fail")),
+ MLDS_Context),
+ FailStatements = [FailComment]
+ ;
+ CanFail = can_fail,
+ FailComment = statement(ml_stmt_atomic(comment("no match, so fail")),
+ MLDS_Context),
+ ml_gen_failure(CodeModel, Context, FailStatements0, !Info),
+ FailStatements = [FailComment | FailStatements0]
+ ).
+
+%-----------------------------------------------------------------------------%
:- end_module ml_backend.ml_string_switch.
%-----------------------------------------------------------------------------%
Index: compiler/ml_switch_gen.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/ml_switch_gen.m,v
retrieving revision 1.56
diff -u -b -r1.56 ml_switch_gen.m
--- compiler/ml_switch_gen.m 26 Jul 2011 00:25:22 -0000 1.56
+++ compiler/ml_switch_gen.m 31 Jul 2011 11:26:02 -0000
@@ -236,12 +236,29 @@
Decls = []
;
SwitchCategory = string_switch,
- num_cons_ids_in_tagged_cases(TaggedCases, NumConsIds, NumArms),
+ filter_out_failing_cases_if_needed(CodeModel,
+ TaggedCases, FilteredTaggedCases, CanFail, FilteredCanFail),
+ num_cons_ids_in_tagged_cases(FilteredTaggedCases,
+ NumConsIds, NumArms),
+ ( NumArms > 1 ->
globals.lookup_int_option(Globals, string_hash_switch_size,
- StringSize),
+ StringHashSwitchSize),
+ globals.lookup_int_option(Globals, string_binary_switch_size,
+ StringBinarySwitchSize),
+ globals.lookup_bool_option(Globals, prefer_switch,
+ PreferSwitch),
(
- NumConsIds >= StringSize,
- NumArms > 1,
+ target_supports_string_switch(Globals),
+ % Even if we could use a hash or binary switch,
+ % we may prefer to do a direct-mapped string switch.
+ PreferSwitch = yes
+ ->
+ ml_switch_generate_mlds_switch(FilteredTaggedCases,
+ SwitchVar, CodeModel, FilteredCanFail, Context,
+ Statements, !Info),
+ Decls = []
+ ;
+ NumConsIds >= StringHashSwitchSize,
% We can implement string hash switches using either
% computed gotos or int switches.
(
@@ -253,25 +270,34 @@
% (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),
- % OK, we could use a string hash switch. But should we?
- % We may prefer to do a direct-mapped string switch.
- \+ (
- target_supports_string_switch(Globals),
- globals.lookup_bool_option(Globals, prefer_switch, yes)
- )
+ target_supports_goto(Globals)
->
- ml_generate_string_switch(TaggedCases, SwitchVar,
- CodeModel, CanFail, Context, Decls, Statements, !Info)
+ ml_generate_string_hash_switch(FilteredTaggedCases,
+ SwitchVar, CodeModel, FilteredCanFail, Context,
+ Decls, Statements, !Info)
;
- target_supports_string_switch(Globals)
+ NumConsIds >= StringBinarySwitchSize,
+ % We can implement string binary switches using either
+ % computed gotos or int switches.
+ (
+ target_supports_computed_goto(Globals)
+ ;
+ target_supports_int_switch(Globals)
+ )
->
- ml_switch_generate_mlds_switch(TaggedCases, SwitchVar,
- CodeModel, CanFail, Context, Statements, !Info),
+ ml_generate_string_binary_switch(FilteredTaggedCases,
+ SwitchVar, CodeModel, FilteredCanFail, Context,
+ Decls, Statements, !Info)
+ ;
+ ml_switch_generate_if_then_else_chain(FilteredTaggedCases,
+ SwitchVar, CodeModel, FilteredCanFail, Context,
+ Statements, !Info),
Decls = []
+ )
;
- ml_switch_generate_if_then_else_chain(TaggedCases,
- SwitchVar, CodeModel, CanFail, Context, Statements, !Info),
+ ml_switch_generate_if_then_else_chain(FilteredTaggedCases,
+ SwitchVar, CodeModel, FilteredCanFail, Context,
+ Statements, !Info),
Decls = []
)
;
Index: compiler/mlds.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/mlds.m,v
retrieving revision 1.193
diff -u -b -r1.193 mlds.m
--- compiler/mlds.m 5 Jul 2011 03:34:32 -0000 1.193
+++ compiler/mlds.m 1 Aug 2011 04:10:52 -0000
@@ -1557,7 +1557,7 @@
)
% Values somewhere in memory.
- % This is the deference operator (e.g. unary `*' in C).
+ % This is the dereference operator (e.g. unary `*' in C).
; ml_mem_ref(
% The rval should have originally come from a mem_addr rval.
Index: compiler/string_switch.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/string_switch.m,v
retrieving revision 1.75
diff -u -b -r1.75 string_switch.m
--- compiler/string_switch.m 2 Aug 2011 00:05:40 -0000 1.75
+++ compiler/string_switch.m 2 Aug 2011 00:05:55 -0000
@@ -7,7 +7,7 @@
%-----------------------------------------------------------------------------%
%
% File: string_switch.m.
-% Author: fjh.
+% Authors: fjh, zs.
%
% For switches on strings, we can generate either
% - a hash table using open addressing to resolve hash conflicts, or
@@ -1041,7 +1041,6 @@
string_binary_switch_info::out, code_info::in, code_info::out) is det.
init_string_binary_switch_info(CanFail, Info, !CI) :-
- % Much but not all of the code of this predicate is common
% We get the registers we use as working storage in the hash table lookup
% code now, before we generate the code of the switch arms, since the set
% of free registers will in general be different before and after that
Index: compiler/switch_gen.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/switch_gen.m,v
retrieving revision 1.119
diff -u -b -r1.119 switch_gen.m
--- compiler/switch_gen.m 26 Jul 2011 00:25:22 -0000 1.119
+++ compiler/switch_gen.m 31 Jul 2011 11:24:46 -0000
@@ -225,37 +225,42 @@
TaggedCases, FilteredTaggedCases, CanFail, FilteredCanFail),
num_cons_ids_in_tagged_cases(FilteredTaggedCases,
NumConsIds, NumArms),
+ ( NumArms > 1 ->
globals.lookup_int_option(Globals, string_hash_switch_size,
StringHashSwitchSize),
globals.lookup_int_option(Globals, string_binary_switch_size,
StringBinarySwitchSize),
- ( NumConsIds >= StringHashSwitchSize, NumArms > 1 ->
+ ( NumConsIds >= StringHashSwitchSize ->
(
- is_lookup_switch(record_lookup_for_tagged_cons_id_string,
+ is_lookup_switch(
+ record_lookup_for_tagged_cons_id_string,
FilteredTaggedCases, GoalInfo, StoreMap,
no, MaybeEnd1, LookupSwitchInfo, !CI)
->
% We update MaybeEnd1 to MaybeEnd to account for the
- % possible reservation of temp slots for nondet switches.
+ % possible reservation of temp slots for nondet
+ % switches.
generate_string_hash_lookup_switch(VarRval,
- LookupSwitchInfo, FilteredCanFail, EndLabel, StoreMap,
- MaybeEnd1, MaybeEnd, SwitchCode, !CI)
+ LookupSwitchInfo, FilteredCanFail, EndLabel,
+ StoreMap, MaybeEnd1, MaybeEnd, SwitchCode, !CI)
;
generate_string_hash_switch(TaggedCases, VarRval,
VarName, CodeModel, CanFail, GoalInfo, EndLabel,
MaybeEnd, SwitchCode, !CI)
)
- ; NumConsIds >= StringBinarySwitchSize, NumArms > 1 ->
+ ; NumConsIds >= StringBinarySwitchSize ->
(
- is_lookup_switch(record_lookup_for_tagged_cons_id_string,
+ is_lookup_switch(
+ record_lookup_for_tagged_cons_id_string,
FilteredTaggedCases, GoalInfo, StoreMap,
no, MaybeEnd1, LookupSwitchInfo, !CI)
->
% We update MaybeEnd1 to MaybeEnd to account for the
- % possible reservation of temp slots for nondet switches.
+ % possible reservation of temp slots for nondet
+ % switches.
generate_string_binary_lookup_switch(VarRval,
- LookupSwitchInfo, FilteredCanFail, EndLabel, StoreMap,
- MaybeEnd1, MaybeEnd, SwitchCode, !CI)
+ LookupSwitchInfo, FilteredCanFail, EndLabel,
+ StoreMap, MaybeEnd1, MaybeEnd, SwitchCode, !CI)
;
generate_string_binary_switch(TaggedCases, VarRval,
VarName, CodeModel, CanFail, GoalInfo, EndLabel,
@@ -267,6 +272,11 @@
MaybeEnd, SwitchCode, !CI)
)
;
+ order_and_generate_cases(TaggedCases, VarRval, VarType,
+ VarName, CodeModel, CanFail, GoalInfo, EndLabel,
+ MaybeEnd, SwitchCode, !CI)
+ )
+ ;
SwitchCategory = tag_switch,
num_cons_ids_in_tagged_cases(TaggedCases, NumConsIds, NumArms),
globals.lookup_int_option(Globals, tag_switch_size, TagSize),
cvs diff: Diffing compiler/notes
cvs diff: Diffing deep_profiler
cvs diff: Diffing deep_profiler/notes
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/base64
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing extras/curs
cvs diff: Diffing extras/curs/samples
cvs diff: Diffing extras/curses
cvs diff: Diffing extras/curses/sample
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/error
cvs diff: Diffing extras/fixed
cvs diff: Diffing extras/gator
cvs diff: Diffing extras/gator/generations
cvs diff: Diffing extras/gator/generations/1
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/easyx
cvs diff: Diffing extras/graphics/easyx/samples
cvs diff: Diffing extras/graphics/mercury_allegro
cvs diff: Diffing extras/graphics/mercury_allegro/examples
cvs diff: Diffing extras/graphics/mercury_allegro/samples
cvs diff: Diffing extras/graphics/mercury_allegro/samples/demo
cvs diff: Diffing extras/graphics/mercury_allegro/samples/mandel
cvs diff: Diffing extras/graphics/mercury_allegro/samples/pendulum2
cvs diff: Diffing extras/graphics/mercury_allegro/samples/speed
cvs diff: Diffing extras/graphics/mercury_cairo
cvs diff: Diffing extras/graphics/mercury_cairo/samples
cvs diff: Diffing extras/graphics/mercury_cairo/samples/data
cvs diff: Diffing extras/graphics/mercury_cairo/tutorial
cvs diff: Diffing extras/graphics/mercury_glut
cvs diff: Diffing extras/graphics/mercury_opengl
cvs diff: Diffing extras/graphics/mercury_tcltk
cvs diff: Diffing extras/graphics/samples
cvs diff: Diffing extras/graphics/samples/calc
cvs diff: Diffing extras/graphics/samples/gears
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/lex
cvs diff: Diffing extras/lex/samples
cvs diff: Diffing extras/lex/tests
cvs diff: Diffing extras/log4m
cvs diff: Diffing extras/logged_output
cvs diff: Diffing extras/monte
cvs diff: Diffing extras/moose
cvs diff: Diffing extras/moose/samples
cvs diff: Diffing extras/moose/tests
cvs diff: Diffing extras/mopenssl
cvs diff: Diffing extras/morphine
cvs diff: Diffing extras/morphine/non-regression-tests
cvs diff: Diffing extras/morphine/scripts
cvs diff: Diffing extras/morphine/source
cvs diff: Diffing extras/net
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/posix
cvs diff: Diffing extras/posix/samples
cvs diff: Diffing extras/quickcheck
cvs diff: Diffing extras/quickcheck/tutes
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/solver_types
cvs diff: Diffing extras/solver_types/library
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing extras/windows_installer_generator
cvs diff: Diffing extras/windows_installer_generator/sample
cvs diff: Diffing extras/windows_installer_generator/sample/images
cvs diff: Diffing extras/xml
cvs diff: Diffing extras/xml/samples
cvs diff: Diffing extras/xml_stylesheets
cvs diff: Diffing java
cvs diff: Diffing java/runtime
cvs diff: Diffing library
cvs diff: Diffing mdbcomp
cvs diff: Diffing profiler
cvs diff: Diffing robdd
cvs diff: Diffing runtime
cvs diff: Diffing runtime/GETOPT
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/appengine
cvs diff: Diffing samples/appengine/war
cvs diff: Diffing samples/appengine/war/WEB-INF
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/standalone_c
cvs diff: Diffing samples/concurrency
cvs diff: Diffing samples/concurrency/dining_philosophers
cvs diff: Diffing samples/concurrency/midimon
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/java_interface
cvs diff: Diffing samples/java_interface/java_calls_mercury
cvs diff: Diffing samples/java_interface/mercury_calls_java
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing samples/solutions
cvs diff: Diffing samples/solver_types
cvs diff: Diffing samples/tests
cvs diff: Diffing samples/tests/c_interface
cvs diff: Diffing samples/tests/c_interface/c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/tests/c_interface/mercury_calls_c
cvs diff: Diffing samples/tests/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/tests/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/tests/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/tests/diff
cvs diff: Diffing samples/tests/muz
cvs diff: Diffing samples/tests/rot13
cvs diff: Diffing samples/tests/solutions
cvs diff: Diffing samples/tests/toplevel
cvs diff: Diffing scripts
cvs diff: Diffing slice
cvs diff: Diffing ssdb
cvs diff: Diffing tests
cvs diff: Diffing tests/analysis
cvs diff: Diffing tests/analysis/ctgc
cvs diff: Diffing tests/analysis/excp
cvs diff: Diffing tests/analysis/ext
cvs diff: Diffing tests/analysis/sharing
cvs diff: Diffing tests/analysis/table
cvs diff: Diffing tests/analysis/trail
cvs diff: Diffing tests/analysis/unused_args
cvs diff: Diffing tests/benchmarks
cvs diff: Diffing tests/debugger
cvs diff: Diffing tests/debugger/declarative
cvs diff: Diffing tests/dppd
cvs diff: Diffing tests/general
cvs diff: Diffing tests/general/accumulator
cvs diff: Diffing tests/general/string_format
cvs diff: Diffing tests/general/structure_reuse
cvs diff: Diffing tests/grade_subdirs
cvs diff: Diffing tests/hard_coded
cvs diff: Diffing tests/hard_coded/exceptions
cvs diff: Diffing tests/hard_coded/purity
cvs diff: Diffing tests/hard_coded/sub-modules
cvs diff: Diffing tests/hard_coded/typeclasses
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/invalid/purity
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/mmc_make
cvs diff: Diffing tests/mmc_make/lib
cvs diff: Diffing tests/par_conj
cvs diff: Diffing tests/recompilation
cvs diff: Diffing tests/stm
cvs diff: Diffing tests/stm/orig
cvs diff: Diffing tests/stm/orig/stm-compiler
cvs diff: Diffing tests/stm/orig/stm-compiler/test1
cvs diff: Diffing tests/stm/orig/stm-compiler/test10
cvs diff: Diffing tests/stm/orig/stm-compiler/test2
cvs diff: Diffing tests/stm/orig/stm-compiler/test3
cvs diff: Diffing tests/stm/orig/stm-compiler/test4
cvs diff: Diffing tests/stm/orig/stm-compiler/test5
cvs diff: Diffing tests/stm/orig/stm-compiler/test6
cvs diff: Diffing tests/stm/orig/stm-compiler/test7
cvs diff: Diffing tests/stm/orig/stm-compiler/test8
cvs diff: Diffing tests/stm/orig/stm-compiler/test9
cvs diff: Diffing tests/stm/orig/stm-compiler-par
cvs diff: Diffing tests/stm/orig/stm-compiler-par/bm1
cvs diff: Diffing tests/stm/orig/stm-compiler-par/bm2
cvs diff: Diffing tests/stm/orig/stm-compiler-par/stmqueue
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test1
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test10
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test11
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test2
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test3
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test4
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test5
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test6
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test7
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test8
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test9
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test1
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test2
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test3
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test4
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test5
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test6
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test7
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test8
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test9
cvs diff: Diffing tests/tabling
cvs diff: Diffing tests/term
cvs diff: Diffing tests/trailing
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing util
cvs diff: Diffing vim
cvs diff: Diffing vim/after
cvs diff: Diffing vim/ftplugin
cvs diff: Diffing vim/syntax
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to: mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions: mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------
More information about the reviews
mailing list