[m-rev.] diff: optimize string hash lookups in the absence of collisions
Zoltan Somogyi
zs at csse.unimelb.edu.au
Tue Jul 26 10:24:28 AEST 2011
When doing hash table lookup as part of the implementation of switches on
strings, we use open addressing to handle collisions. However, if the chosen
hash function does not yield any collisions for the strings in the switch arms,
then open addressing is unnecessary: if a lookup does not find the string bound
to the switch variable in its home bucket, it won't be in the hash table
at all.
This diff optimizes such cases, by not generating for them the loop we would
otherwise use for open addressing, and optimizing away the table column
telling that loop where to check next.
compiler/string_switch.m:
Implement the above optimization both for ordinary switches on strings,
and for lookup table switches (both one_soln and several_soln) on
strings.
compiler/ml_string_switch.m:
Implement the above optimization for ordinary switches on strings.
This module does not (yet) implement lookup table switches on strings.
compiler/switch_util.m:
When deciding what hash function to use, return the number of
collisions for string_switch and ml_string_switch to use.
Rename the other_switch category to float_switch, since the only
type category it covers is switches on floats.
compiler/switch_gen.m:
compiler/ml_switch_gen.m:
Make the module header comments more organized, and use the same
template for both, so one can see the differences more easily.
Put the switch arms for the smart indexing methods into the same
order in both files.
Fix an old problem in ml_switch_gen.m: the test to see whether we can
apply a smart indexing method that uses switches on integers was
testing not the availability of int switches in the target, but
the availability of computed gotos. While ml_simplify_switch
would transform the int-switch-using code to computed-goto-using
code or an if-then-else chain in *some* cases, it would not do so
in *all* cases.
In ml_switch_gen.m, remove a test that could not succeed, and
a procedure that was used only in that test.
Conform to the changes in switch_util.m.
compiler/lookup_switch.m:
compiler/ml_simplify_switch.m:
Update comments.
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/lookup_switch.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/lookup_switch.m,v
retrieving revision 1.92
diff -u -b -r1.92 lookup_switch.m
--- compiler/lookup_switch.m 21 Jul 2011 06:58:25 -0000 1.92
+++ compiler/lookup_switch.m 25 Jul 2011 03:41:29 -0000
@@ -133,8 +133,9 @@
% predicate.
% - For int switches, there will be no previous columns.
% - For binary string switches, there is one containing the string.
- % - For hash string switches, there are two, containing the string,
- % and the number of the next slot in the open addressing sequence.
+ % - For hash string switches, there are one or two, the first containing
+ % the string, and the second (if it is needed) the number of the next
+ % slot in the open addressing sequence.
%
% - The second group contains two columns, which contain respectively
% the offsets of the first and last later solutions in the later
Index: compiler/ml_simplify_switch.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/ml_simplify_switch.m,v
retrieving revision 1.34
diff -u -b -r1.34 ml_simplify_switch.m
--- compiler/ml_simplify_switch.m 23 May 2011 05:08:06 -0000 1.34
+++ compiler/ml_simplify_switch.m 25 Jul 2011 04:10:37 -0000
@@ -16,9 +16,9 @@
% 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.
+% 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.
%
%-----------------------------------------------------------------------------%
Index: compiler/ml_string_switch.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/ml_string_switch.m,v
retrieving revision 1.50
diff -u -b -r1.50 ml_string_switch.m
--- compiler/ml_string_switch.m 23 May 2011 05:08:07 -0000 1.50
+++ compiler/ml_string_switch.m 25 Jul 2011 01:52:50 -0000
@@ -80,9 +80,9 @@
ml_gen_info_new_aux_var_name("str", StringVar, !Info),
StringVarType = ml_string_type,
- % This variable always points to an element of the string_table array,
- % which are all static constants; it can never point into the heap.
- % So the GC never needs to trace it
+ % StringVar always points to an element of the string_table array.
+ % All those elements are static constants; they can never point into
+ % the heap. So GC never needs to trace StringVar.
StringVarGCStatement = gc_no_stmt,
StringVarDefn = ml_gen_mlds_var_decl(mlds_data_var(StringVar),
StringVarType, StringVarGCStatement, MLDS_Context),
@@ -105,7 +105,8 @@
% Compute the hash table.
construct_string_hash_jump_cases(Cases, TableSize, HashMask,
gen_tagged_case_code_for_string_switch(CodeModel),
- map.init, CodeMap, unit, _, !Info, HashSlotsMap, HashOp),
+ map.init, CodeMap, unit, _, !Info, HashSlotsMap,
+ HashOp, NumCollisions),
% Generate the code for when the hash lookup fails.
(
@@ -133,7 +134,12 @@
MLDS_StringType = mercury_type_to_mlds_type(ModuleInfo, string_type),
MLDS_NextSlotType = mlds_native_int_type,
- MLDS_ArgTypes = [MLDS_StringType, MLDS_NextSlotType],
+
+ ( NumCollisions = 0 ->
+ MLDS_ArgTypes = [MLDS_StringType]
+ ;
+ MLDS_ArgTypes = [MLDS_StringType, MLDS_NextSlotType]
+ ),
ml_gen_info_get_global_data(!.Info, GlobalData0),
ml_gen_static_vector_type(MLDS_ModuleName, MLDS_Context, Target,
@@ -142,14 +148,17 @@
( FieldIds = [StringFieldIdPrime, NextSlotFieldIdPrime] ->
StringFieldId = StringFieldIdPrime,
- NextSlotFieldId = NextSlotFieldIdPrime
+ MaybeNextSlotFieldId = yes(NextSlotFieldIdPrime)
+ ; FieldIds = [StringFieldIdPrime] ->
+ StringFieldId = StringFieldIdPrime,
+ MaybeNextSlotFieldId = no
;
unexpected($module, $pred, "bad FieldIds")
),
% Generate the rows of the hash table.
ml_gen_string_hash_slots(0, TableSize, StructType, HashSlotsMap,
- RowInitializers, map.init, RevMap),
+ MaybeNextSlotFieldId, RowInitializers, map.init, RevMap),
% Generate the hash table. The hash table is indexed by slot number,
% and each element has two fields: the matched string, and the next slot
@@ -187,7 +196,20 @@
GotoEndStatement
]),
MLDS_Context),
- LoopBody = statement(ml_stmt_block([], [
+
+ PrepareForMatchStatements = [
+ statement(ml_stmt_atomic(comment("hashed string switch")),
+ MLDS_Context),
+ statement(ml_stmt_atomic(comment(
+ "compute the hash value of the input string")), MLDS_Context),
+ statement(
+ ml_stmt_atomic(assign(SlotVarLval,
+ ml_binop(bitwise_and,
+ ml_unop(std_unop(HashOp), VarRval),
+ ml_const(mlconst_int(HashMask))))),
+ MLDS_Context)
+ ],
+ LookForMatchStatements = [
statement(ml_stmt_atomic(comment(
"lookup the string for this hash slot")), MLDS_Context),
statement(
@@ -199,7 +221,11 @@
statement(ml_stmt_atomic(comment("did we find a match?")),
MLDS_Context),
statement(ml_stmt_if_then_else(FoundMatchCond, FoundMatchCode, no),
- MLDS_Context),
+ MLDS_Context)
+ ],
+ (
+ MaybeNextSlotFieldId = yes(NextSlotFieldId),
+ NoMatchStatements = [
statement(ml_stmt_atomic(comment(
"no match yet, so get next slot in hash chain")), MLDS_Context),
statement(
@@ -208,19 +234,12 @@
ml_vector_common_row(VectorCommon, SlotVarRval),
NextSlotFieldId, MLDS_NextSlotType, StructType)))),
MLDS_Context)
- ]),
- MLDS_Context),
- HashLookupStatements = [
- statement(ml_stmt_atomic(comment("hashed string switch")),
- MLDS_Context),
- statement(ml_stmt_atomic(comment(
- "compute the hash value of the input string")), MLDS_Context),
- statement(
- ml_stmt_atomic(assign(SlotVarLval,
- ml_binop(bitwise_and,
- ml_unop(std_unop(HashOp), VarRval),
- ml_const(mlconst_int(HashMask))))),
- MLDS_Context),
+ ],
+
+ LoopBody = statement(ml_stmt_block([],
+ LookForMatchStatements ++ NoMatchStatements), MLDS_Context),
+
+ LoopStatements = [
statement(ml_stmt_atomic(comment("hash chain loop")), MLDS_Context),
statement(
ml_stmt_while(
@@ -231,6 +250,21 @@
LoopBody),
MLDS_Context)
],
+
+ HashLookupStatements =
+ PrepareForMatchStatements ++ LoopStatements
+ ;
+ MaybeNextSlotFieldId = no,
+ NoLoopStatements = [
+ statement(ml_stmt_atomic(
+ comment("no collisions; no hash chain loop")), MLDS_Context)
+ ],
+
+ HashLookupStatements =
+ PrepareForMatchStatements ++ LookForMatchStatements ++
+ NoLoopStatements
+ ),
+
EndLabelStatement = statement(ml_stmt_label(EndLabel), MLDS_Context),
EndComment =
statement(ml_stmt_atomic(comment("end of hashed string switch")),
@@ -301,27 +335,29 @@
:- type hash_slot_rev_map == map(int, hash_slots).
:- pred ml_gen_string_hash_slots(int::in, int::in, mlds_type::in,
- map(int, string_hash_slot(int))::in, list(mlds_initializer)::out,
+ map(int, string_hash_slot(int))::in, maybe(mlds_field_id)::in,
+ list(mlds_initializer)::out,
hash_slot_rev_map::in, hash_slot_rev_map::out) is det.
ml_gen_string_hash_slots(Slot, TableSize, RowType, HashSlotMap,
- RowInitializers, !RevMap) :-
+ MaybeNextSlotId, RowInitializers, !RevMap) :-
( Slot = TableSize ->
RowInitializers = []
;
- ml_gen_string_hash_slot(Slot, RowType, HashSlotMap, HeadRowInitializer,
- !RevMap),
+ ml_gen_string_hash_slot(Slot, RowType, HashSlotMap,
+ MaybeNextSlotId, HeadRowInitializer, !RevMap),
ml_gen_string_hash_slots(Slot + 1, TableSize, RowType, HashSlotMap,
- TailRowInitializers, !RevMap),
+ MaybeNextSlotId, TailRowInitializers, !RevMap),
RowInitializers = [HeadRowInitializer | TailRowInitializers]
).
:- pred ml_gen_string_hash_slot(int::in, mlds_type::in,
- map(int, string_hash_slot(int))::in, mlds_initializer::out,
+ map(int, string_hash_slot(int))::in, maybe(mlds_field_id)::in,
+ mlds_initializer::out,
hash_slot_rev_map::in, hash_slot_rev_map::out) is det.
-ml_gen_string_hash_slot(Slot, StructType, HashSlotMap, RowInitializer,
- !RevMap) :-
+ml_gen_string_hash_slot(Slot, StructType, HashSlotMap,
+ MaybeNextSlotId, RowInitializer, !RevMap) :-
( map.search(HashSlotMap, Slot, string_hash_slot(String, Next, CaseNum)) ->
StringRval = ml_const(mlconst_string(String)),
NextSlotRval = ml_const(mlconst_int(Next)),
@@ -337,8 +373,15 @@
StringRval = ml_const(mlconst_null(ml_string_type)),
NextSlotRval = ml_const(mlconst_int(-2))
),
+ (
+ MaybeNextSlotId = yes(_),
RowInitializer = init_struct(StructType,
- [init_obj(StringRval), init_obj(NextSlotRval)]).
+ [init_obj(StringRval), init_obj(NextSlotRval)])
+ ;
+ MaybeNextSlotId = no,
+ RowInitializer = init_struct(StructType,
+ [init_obj(StringRval)])
+ ).
:- pred generate_string_switch_arms(map(int, statement)::in,
assoc_list(int, hash_slots)::in,
Index: compiler/ml_switch_gen.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/ml_switch_gen.m,v
retrieving revision 1.55
diff -u -b -r1.55 ml_switch_gen.m
--- compiler/ml_switch_gen.m 16 Jun 2011 06:42:14 -0000 1.55
+++ compiler/ml_switch_gen.m 25 Jul 2011 04:17:34 -0000
@@ -7,56 +7,92 @@
%-----------------------------------------------------------------------------%
%
% File: ml_switch_gen.m
-% Author: fjh (adapted from switch_gen.m)
+% Authors: fjh, zs.
%
-% 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").
+% This module determines how we should generate code for a switch, primarily
+% by deciding what sort of indexing, if any, we should use.
+% NOTE The code here is quite similar to the code in switch_gen.m,
+% which does the same thing for the LLDS back-end. Any changes here
+% probably also require similar changes there.
%
-% 1 For switches on atomic data types (int, char, enums), there are
-% several possibilities.
+% The following describes the different forms of indexing that we can use.
+% Note that currently some of these are not implemented; these are marked
+% NYI (for "not yet implemented").
+%
+% 1 For switches on atomic data types (int, char, enums), we can use
+% three smart indexing strategies.
%
% 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) in which we can look up
+% contain only construction unifications of constants, then we
+% generate a dense lookup table (an array) in which we look up
% the values of the output variables.
+% Implemented by ml_lookup_switch.m
+%
% 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 look up 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)
-% b) If the target supports string switches,
-% we generate an MLDS switch statement.
+% switch statements and the `--prefer-switch' option is set.
+% NYI.
+%
+% c) If the target supports switch statements, we generate an MLDS
+% switch statement.
+% Implemented by this module.
+%
+% 2 For switches on strings, we can use five smart indexing strategies,
+% four of which are the possible combinations of two possible implementation
+% strategies of each of two aspects on the switch.
+%
+% a) One basic implementation strategy is the use of a hash table with
+% open addressing. Since the contents of the hash table is fixed,
+% the open addressing can select buckets that are not the home bucket
+% of any string in the table. And if we know that no two strings in
+% the table share the same home address, we can dispense with open
+% addressing altogether.
+%
+% This strategy requires the target to support either computed gotos
+% or int switches. We prefer computed gotos, in which case table entries
+% contain the address to jump to, but we can also use it switches,
+% in which case entries contain an integer to give to a switch.
+% We don't use this strategy if the target supports string switch
+% statements and the `--prefer-switch' option is set.
+%
+% b) The second basic implementation approach is the use of binary search.
+% We generate a table containing all the strings in the switch cases in
+% order, and search it using binary search. Again, we don't use this
+% strategy if the target supports string switch statements and the
+% `--prefer-switch' option is set.
+%
+% c) If the target supports string switches, we generate an MLDS switch
+% statement directly on the string variable.
+%
+% The second aspect is whether we use a lookup table. If all the switch arms
+% contain only construction unifications of constants, and we are using
+% approach (a) or (b), we extend can each row in either the hash table or the
+% binary search table with extra columns containing the values of the output
+% variables.
+%
+% The use of a lookup table and the use of binary searches is NYI.
+% All the other indexing strategies are implemented by ml_string_switch.m.
%
% 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)
+% or a binary search.
+% At the moment, ml_tag_switch implements only try-me-else chains;
+% the other indexing forms are NYI.
%
-% For all other cases (or if the --smart-indexing option was disabled),
-% we just generate a chain of if-then-elses.
+% 4 For switches on floats, we could generate code that does binary search.
+% However, this is not yet implemented.
+%
+% If we cannot apply any of the above smart indexing strategies, or if the
+% --smart-indexing option was disabled, then this module just generates
+% 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).
+% - optimize if-then-else chain switches so that the recursive case
+% comes first (see switch_gen.m).
%
%-----------------------------------------------------------------------------%
@@ -162,6 +198,43 @@
Decls = []
;
(
+ SwitchCategory = atomic_switch,
+ num_cons_ids_in_tagged_cases(TaggedCases, NumConsIds, NumArms),
+ (
+ ml_gen_info_get_high_level_data(!.Info, no),
+ MaybeIntSwitchInfo = int_switch(LowerLimit, UpperLimit,
+ NumValues),
+ globals.lookup_bool_option(Globals, static_ground_cells, yes),
+ globals.lookup_int_option(Globals, lookup_switch_size,
+ LookupSize),
+ NumConsIds >= LookupSize,
+ NumArms > 1,
+ globals.lookup_int_option(Globals, lookup_switch_req_density,
+ ReqDensity),
+ filter_out_failing_cases_if_needed(CodeModel,
+ TaggedCases, FilteredTaggedCases,
+ CanFail, FilteredCanFail),
+ find_int_lookup_switch_params(ModuleInfo, SwitchVarType,
+ FilteredCanFail, LowerLimit, UpperLimit, NumValues,
+ ReqDensity, NeedBitVecCheck, NeedRangeCheck,
+ FirstVal, LastVal),
+ NonLocals = goal_info_get_nonlocals(GoalInfo),
+ ml_gen_lookup_switch(SwitchVar, FilteredTaggedCases,
+ NonLocals, CodeModel, Context, FirstVal, LastVal,
+ NeedBitVecCheck, NeedRangeCheck, LookupStatement, !Info)
+ ->
+ Statements = [LookupStatement]
+ ;
+ target_supports_int_switch(Globals)
+ ->
+ ml_switch_generate_mlds_switch(TaggedCases, SwitchVar,
+ CodeModel, CanFail, Context, Statements, !Info)
+ ;
+ ml_switch_generate_if_then_else_chain(TaggedCases,
+ SwitchVar, CodeModel, CanFail, Context, Statements, !Info)
+ ),
+ Decls = []
+ ;
SwitchCategory = string_switch,
num_cons_ids_in_tagged_cases(TaggedCases, NumConsIds, NumArms),
globals.lookup_int_option(Globals, string_hash_switch_size,
@@ -218,74 +291,15 @@
),
Decls = []
;
- SwitchCategory = atomic_switch,
- num_cons_ids_in_tagged_cases(TaggedCases, NumConsIds, NumArms),
- (
- ml_gen_info_get_high_level_data(!.Info, no),
- MaybeIntSwitchInfo = int_switch(LowerLimit, UpperLimit,
- NumValues),
- globals.lookup_bool_option(Globals, static_ground_cells, yes),
- globals.lookup_int_option(Globals, lookup_switch_size,
- LookupSize),
- NumConsIds >= LookupSize,
- NumArms > 1,
- globals.lookup_int_option(Globals, lookup_switch_req_density,
- ReqDensity),
- filter_out_failing_cases_if_needed(CodeModel,
- TaggedCases, FilteredTaggedCases,
- CanFail, FilteredCanFail),
- find_int_lookup_switch_params(ModuleInfo, SwitchVarType,
- FilteredCanFail, LowerLimit, UpperLimit, NumValues,
- ReqDensity, NeedBitVecCheck, NeedRangeCheck,
- FirstVal, LastVal),
- NonLocals = goal_info_get_nonlocals(GoalInfo),
- ml_gen_lookup_switch(SwitchVar, FilteredTaggedCases,
- NonLocals, CodeModel, Context, FirstVal, LastVal,
- NeedBitVecCheck, NeedRangeCheck, LookupStatement, !Info)
- ->
- Statements = [LookupStatement]
- ;
- target_supports_computed_goto(Globals)
- ->
- ml_switch_generate_mlds_switch(TaggedCases, SwitchVar,
- CodeModel, CanFail, Context, Statements, !Info)
- ;
- ml_switch_generate_if_then_else_chain(TaggedCases,
- SwitchVar, CodeModel, CanFail, Context, Statements, !Info)
- ),
- Decls = []
- ;
- SwitchCategory = other_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.
- target_supports_switch(SwitchCategory, Globals)
- ->
- ml_switch_generate_mlds_switch(TaggedCases, SwitchVar,
- CodeModel, CanFail, Context, Statements, !Info)
- ;
+ SwitchCategory = float_switch,
ml_switch_generate_if_then_else_chain(TaggedCases,
- SwitchVar, CodeModel, CanFail, Context, Statements, !Info)
- ),
+ SwitchVar, CodeModel, CanFail, Context, Statements, !Info),
Decls = []
)
).
%-----------------------------------------------------------------------------%
-:- pred target_supports_switch(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)
- ).
-
target_supports_int_switch(Globals) :-
globals.get_target(Globals, Target),
target_supports_int_switch_2(Target) = yes.
@@ -490,7 +504,7 @@
% 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.
+ % language. (But see the post-processing done by ml_simplify_switch.)
%
:- pred ml_switch_generate_mlds_switch(list(tagged_case)::in,
prog_var::in, code_model::in, can_fail::in, prog_context::in,
Index: compiler/string_switch.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/string_switch.m,v
retrieving revision 1.73
diff -u -b -r1.73 string_switch.m
--- compiler/string_switch.m 21 Jul 2011 06:58:27 -0000 1.73
+++ compiler/string_switch.m 24 Jul 2011 23:38:29 -0000
@@ -106,7 +106,6 @@
% of cases up to the nearest power of two, and then double it.
% This should hopefully ensure that we don't get too many hash collisions.
- NumColumns = 2,
list.length(Cases, NumCases),
int.log2(NumCases, LogNumCases),
int.pow(2, LogNumCases, RoundedNumCases),
@@ -117,19 +116,27 @@
map.init(CaseLabelMap0),
construct_string_hash_jump_cases(Cases, TableSize, HashMask,
represent_tagged_case_for_llds(Params),
- CaseLabelMap0, CaseLabelMap, no, MaybeEnd, !CI, HashSlotsMap, HashOp),
+ CaseLabelMap0, CaseLabelMap, no, MaybeEnd, !CI, HashSlotsMap,
+ HashOp, NumCollisions),
% Generate the data structures for the hash table.
FailLabel = HashSwitchInfo ^ shsi_fail_label,
construct_string_hash_jump_vectors(0, TableSize, HashSlotsMap, FailLabel,
- [], RevTableRows, [], RevTargets),
+ NumCollisions, [], RevTableRows, [], RevTargets),
list.reverse(RevTableRows, TableRows),
list.reverse(RevTargets, Targets),
% Generate the code for the hash table lookup.
+ ( NumCollisions = 0 ->
+ NumColumns = 1,
+ RowElemTypes = [lt_string],
+ ArrayElemTypes = [scalar_elem_string]
+ ;
+ NumColumns = 2,
RowElemTypes = [lt_string, lt_integer],
+ ArrayElemTypes = [scalar_elem_string, scalar_elem_int]
+ ),
add_vector_static_cell(RowElemTypes, TableRows, TableAddr, !CI),
- ArrayElemTypes = [scalar_elem_string, scalar_elem_int],
ArrayElemType = array_elem_struct(ArrayElemTypes),
TableAddrRval = const(llconst_data_addr(TableAddr, no)),
@@ -141,8 +148,8 @@
]),
generate_string_hash_switch_search(HashSwitchInfo, VarRval, TableAddrRval,
- ArrayElemType, NumColumns, HashOp, HashMask, MatchCode,
- HashLookupCode),
+ ArrayElemType, NumColumns, HashOp, HashMask, NumCollisions,
+ MatchCode, HashLookupCode),
% Generate the code for the cases.
map.foldl(add_remaining_case, CaseLabelMap, empty, CasesCode),
@@ -153,12 +160,12 @@
Code = CommentCode ++ HashLookupCode ++ CasesCode ++ EndLabelCode.
:- pred construct_string_hash_jump_vectors(int::in, int::in,
- map(int, string_hash_slot(label))::in, label::in,
+ map(int, string_hash_slot(label))::in, label::in, int::in,
list(list(rval))::in, list(list(rval))::out,
list(maybe(label))::in, list(maybe(label))::out) is det.
construct_string_hash_jump_vectors(Slot, TableSize, HashSlotMap, FailLabel,
- !RevTableRows, !RevMaybeTargets) :-
+ NumCollisions, !RevTableRows, !RevMaybeTargets) :-
( Slot = TableSize ->
true
;
@@ -172,11 +179,15 @@
NextSlotRval = const(llconst_int(-2)),
Target = FailLabel
),
- TableRow = [StringRval, NextSlotRval],
+ ( NumCollisions = 0 ->
+ TableRow = [StringRval]
+ ;
+ TableRow = [StringRval, NextSlotRval]
+ ),
!:RevTableRows = [TableRow | !.RevTableRows],
!:RevMaybeTargets = [yes(Target) | !.RevMaybeTargets],
construct_string_hash_jump_vectors(Slot + 1, TableSize, HashSlotMap,
- FailLabel, !RevTableRows, !RevMaybeTargets)
+ FailLabel, NumCollisions, !RevTableRows, !RevMaybeTargets)
).
%-----------------------------------------------------------------------------%
@@ -227,24 +238,30 @@
TableSize = 2 * RoundedNumCases,
HashMask = TableSize - 1,
+ % Compute the hash table.
+ construct_string_hash_lookup_cases(CaseValues, TableSize, HashMask,
+ HashSlotsMap, HashOp, NumCollisions),
+
list.length(OutVars, NumOutVars),
- NumColumns = 2 + NumOutVars,
% For the LLDS backend, array indexing ops don't need the element
- % types, so it is ok to lie here.
+ % types, so it is ok to lie for OutElemTypes.
list.duplicate(NumOutVars, scalar_elem_generic, OutElemTypes),
+ DummyOutRvals = list.map(default_value_for_type, OutTypes),
+ ( NumCollisions = 0 ->
+ NumColumns = 1 + NumOutVars,
+ ArrayElemTypes = [scalar_elem_string | OutElemTypes],
+ RowElemTypes = [lt_string | OutTypes]
+ ;
+ NumColumns = 2 + NumOutVars,
ArrayElemTypes = [scalar_elem_string, scalar_elem_int | OutElemTypes],
+ RowElemTypes = [lt_string, lt_integer | OutTypes]
+ ),
ArrayElemType = array_elem_struct(ArrayElemTypes),
- % Compute the hash table.
- construct_string_hash_lookup_cases(CaseValues, TableSize, HashMask,
- HashSlotsMap, HashOp),
-
% Generate the static lookup table for this switch.
- DummyOutRvals = list.map(default_value_for_type, OutTypes),
construct_string_hash_simple_lookup_vector(0, TableSize, HashSlotsMap,
- DummyOutRvals, [], RevVectorRvals),
+ NumCollisions, DummyOutRvals, [], RevVectorRvals),
list.reverse(RevVectorRvals, VectorRvals),
- RowElemTypes = [lt_string, lt_integer | OutTypes],
add_vector_static_cell(RowElemTypes, VectorRvals, VectorAddr, !CI),
VectorAddrRval = const(llconst_data_addr(VectorAddr, no)),
@@ -292,7 +309,7 @@
MatchCode = SetBaseRegCode ++ BranchEndCode ++ GotoEndLabelCode,
generate_string_hash_switch_search(HashSwitchInfo,
VarRval, VectorAddrRval, ArrayElemType, NumColumns, HashOp, HashMask,
- MatchCode, HashSearchCode),
+ NumCollisions, MatchCode, HashSearchCode),
EndLabelCode = singleton(
llds_instr(label(EndLabel),
@@ -302,11 +319,11 @@
Code = CommentCode ++ HashSearchCode ++ EndLabelCode.
:- pred construct_string_hash_simple_lookup_vector(int::in, int::in,
- map(int, string_hash_slot(list(rval)))::in, list(rval)::in,
+ map(int, string_hash_slot(list(rval)))::in, int::in, list(rval)::in,
list(list(rval))::in, list(list(rval))::out) is det.
construct_string_hash_simple_lookup_vector(Slot, TableSize, HashSlotMap,
- DummyOutRvals, !RevRows) :-
+ NumCollisions, DummyOutRvals, !RevRows) :-
( Slot = TableSize ->
true
;
@@ -319,10 +336,14 @@
NextSlotRval = const(llconst_int(-2)),
OutVarRvals = DummyOutRvals
),
- Row = [StringRval, NextSlotRval | OutVarRvals],
+ ( NumCollisions = 0 ->
+ Row = [StringRval | OutVarRvals]
+ ;
+ Row = [StringRval, NextSlotRval | OutVarRvals]
+ ),
!:RevRows = [Row | !.RevRows],
construct_string_hash_simple_lookup_vector(Slot + 1, TableSize,
- HashSlotMap, DummyOutRvals, !RevRows)
+ HashSlotMap, NumCollisions, DummyOutRvals, !RevRows)
).
%-----------------------------------------------------------------------------%
@@ -353,13 +374,28 @@
TableSize = 2 * RoundedNumCases,
HashMask = TableSize - 1,
+ % Compute the hash table.
+ construct_string_hash_lookup_cases(CaseSolns, TableSize, HashMask,
+ HashSlotsMap, HashOp, NumCollisions),
+
list.length(OutVars, NumOutVars),
- NumColumns = 4 + NumOutVars,
% For the LLDS backend, array indexing ops don't need the element
- % types, so it is ok to lie here.
+ % types, so it is ok to lie for OutElemTypes.
list.duplicate(NumOutVars, scalar_elem_generic, OutElemTypes),
+ ( NumCollisions = 0 ->
+ NumColumns = 3 + NumOutVars,
+ NumPrevColumns = 1,
+ ArrayElemTypes = [scalar_elem_string,
+ scalar_elem_int, scalar_elem_int | OutElemTypes],
+ MainRowTypes = [lt_string, lt_integer, lt_integer | OutTypes]
+ ;
+ NumColumns = 4 + NumOutVars,
+ NumPrevColumns = 2,
ArrayElemTypes = [scalar_elem_string, scalar_elem_int,
scalar_elem_int, scalar_elem_int | OutElemTypes],
+ MainRowTypes = [lt_string, lt_integer, lt_integer, lt_integer
+ | OutTypes]
+ ),
ArrayElemType = array_elem_struct(ArrayElemTypes),
% If there are no output variables, then how can the individual solutions
@@ -374,10 +410,6 @@
AddTrailOps = do_not_add_trail_ops
),
- % Compute the hash table.
- construct_string_hash_lookup_cases(CaseSolns, TableSize, HashMask,
- HashSlotsMap, HashOp),
-
% Generate the static lookup table for this switch.
InitLaterSolnRowNumber = 1,
DummyOutRvals = list.map(default_value_for_type, OutTypes),
@@ -395,7 +427,6 @@
list.reverse(AscendingSortedCountKinds, DescendingSortedCountKinds),
assoc_list.values(DescendingSortedCountKinds, DescendingSortedKinds),
- MainRowTypes = [lt_string, lt_integer, lt_integer, lt_integer | OutTypes],
add_vector_static_cell(MainRowTypes, MainRows, MainVectorAddr, !CI),
MainVectorAddrRval = const(llconst_data_addr(MainVectorAddr, no)),
add_vector_static_cell(OutTypes, LaterSolnArray, LaterVectorAddr, !CI),
@@ -416,14 +447,14 @@
mem_addr(heap_ref(MainVectorAddrRval, 0, lval(RowStartReg)))),
"set up base reg")
),
- generate_code_for_all_kinds(DescendingSortedKinds, 2, OutVars, ResumeVars,
- EndLabel, StoreMap, Liveness, AddTrailOps,
+ generate_code_for_all_kinds(DescendingSortedKinds, NumPrevColumns,
+ OutVars, ResumeVars, EndLabel, StoreMap, Liveness, AddTrailOps,
BaseReg, LaterVectorAddrRval, !MaybeEnd, LookupResultsCode, !CI),
MatchCode = SetBaseRegCode ++ LookupResultsCode,
generate_string_hash_switch_search(HashSwitchInfo,
VarRval, MainVectorAddrRval, ArrayElemType, NumColumns,
- HashOp, HashMask, MatchCode, HashSearchCode),
+ HashOp, HashMask, NumCollisions, MatchCode, HashSearchCode),
EndLabelCode = singleton(
llds_instr(label(EndLabel),
"end of simple hash string lookup switch")
@@ -536,10 +567,11 @@
:- pred generate_string_hash_switch_search(string_hash_switch_info::in,
rval::in, rval::in, array_elem_type::in, int::in, unary_op::in, int::in,
- llds_code::in, llds_code::out) is det.
+ int::in, llds_code::in, llds_code::out) is det.
generate_string_hash_switch_search(Info, VarRval, TableAddrRval,
- ArrayElemType, NumColumns, HashOp, HashMask, MatchCode, Code) :-
+ ArrayElemType, NumColumns, HashOp, HashMask, NumCollisions,
+ MatchCode, Code) :-
SlotReg = Info ^ shsi_slot_reg,
RowStartReg = Info ^ shsi_row_start_reg,
StringReg = Info ^ shsi_string_reg,
@@ -548,6 +580,41 @@
FailLabel = Info ^ shsi_fail_label,
FailCode = Info ^ shsi_fail_code,
+ ( NumCollisions = 0 ->
+ ( NumColumns = 1 ->
+ BaseReg = SlotReg,
+ MultiplyInstrs = []
+ ;
+ BaseReg = RowStartReg,
+ MultiplyInstrs = [
+ llds_instr(assign(RowStartReg,
+ binop(int_mul, lval(SlotReg),
+ const(llconst_int(NumColumns)))),
+ "find the start of the row")
+ ]
+ ),
+ Code = from_list([
+ llds_instr(assign(SlotReg,
+ binop(bitwise_and, unop(HashOp, VarRval),
+ const(llconst_int(HashMask)))),
+ "compute the hash value of the input string") |
+ MultiplyInstrs]) ++
+ from_list([
+ llds_instr(assign(StringReg,
+ binop(array_index(ArrayElemType), TableAddrRval,
+ lval(BaseReg))),
+ "lookup the string for this hash slot"),
+ llds_instr(if_val(
+ binop(logical_or,
+ binop(eq, lval(StringReg), const(llconst_int(0))),
+ binop(str_ne, lval(StringReg), VarRval)),
+ code_label(FailLabel)),
+ "did we find a match? nofulljump")
+ ]) ++ MatchCode ++ from_list([
+ llds_instr(label(FailLabel),
+ "handle the failure of the table search")
+ ]) ++ FailCode
+ ;
Code = from_list([
llds_instr(assign(SlotReg,
binop(bitwise_and, unop(HashOp, VarRval),
@@ -578,10 +645,11 @@
llds_instr(
if_val(binop(int_ge, lval(SlotReg), const(llconst_int(0))),
code_label(LoopStartLabel)),
- "if we have not yet reached the end of the chain, keep searching"),
+ "if we have not reached the end of the chain, keep searching"),
llds_instr(label(FailLabel),
"handle the failure of the table search")
- ]) ++ FailCode.
+ ]) ++ FailCode
+ ).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
Index: compiler/switch_gen.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/switch_gen.m,v
retrieving revision 1.118
diff -u -b -r1.118 switch_gen.m
--- compiler/switch_gen.m 16 Jun 2011 06:42:15 -0000 1.118
+++ compiler/switch_gen.m 25 Jul 2011 04:17:33 -0000
@@ -9,36 +9,67 @@
% File: switch_gen.m.
% Authors: conway, fjh, zs.
%
-% This module handles the generation of code for switches, which are
-% disjunctions that do not require backtracking. Switches are detected
-% in switch_detection.m. This module determines what sort of indexing to use
-% for each switch and then actually generates the code.
-%
-% Currently the following forms of indexing are used:
-%
-% For switches on atomic data types (int, char, enums), if the cases are not
-% sparse, we use the value of the switch variable to index into a jump table.
-%
-% If all the alternative goals for a switch on an atomic data type or a string
-% contain only constructions of constant data structures, then we generate
-% a dense lookup table (an array) for the output variables of the switch,
-% rather than a jump table, so that executing the switch becomes
-% a matter of doing an array lookup for each output variable, avoiding
-% the branch overhead of the jump table.
-%
-% For switches on strings, we can use binary search in a table, or we can
-% look up the address to jump to in a hash table, using open addressing
-% to resolve hash collisions.
+% This module determines how we should generate code for a switch, primarily
+% by deciding what sort of indexing, if any, we should use.
+% NOTE The code here is quite similar to the code in ml_switch_gen.m,
+% which does the same thing for the MLDS back-end. Any changes here
+% probably also require similar changes there.
%
-% For switches on discriminated union types, we generate code that does
+% The following describes the different forms of indexing that we can use.
+%
+% 1 For switches on atomic data types (int, char, enums), we can use two
+% smart indexing strategies.
+%
+% a) If all the switch arms contain only construction unifications of
+% constants, then we generate a dense lookup table (an array) in which
+% we look up the values of the output variables.
+% Implemented by lookup_switch.m.
+%
+% b) If the cases are not sparse, we use a computed_goto.
+% Implemented by dense_switch.m.
+%
+% 2 For switches on strings, we can use four smart indexing strategies,
+% which are the possible combinations of two possible implementations
+% of each of two aspects of the switch.
+%
+% The first aspect is the implementation of the lookup.
+%
+% a) One basic implementation approach is the use of a hash table with
+% open addressing. Since the contents of the hash table is fixed,
+% the open addressing can select buckets that are not the home bucket
+% of any string in the table. And if we know that no two strings in
+% the table share the same home address, we can dispense with open
+% addressing altogether.
+%
+% b) The other basic implementation approach is the use of binary search.
+% We generate a table containing all the strings in the switch cases in
+% order, and search it using binary search.
+%
+% The second aspect is whether we use a lookup table. If all the switch arms
+% contain only construction unifications of constants, then we extend each
+% row in either the hash table or the binary search table with extra columns
+% containing the values of the output variables.
+%
+% All these indexing strategies are implemented by string_switch.m, with
+% some help from utility predicates in lookup_switch.m.
+%
+% 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.
+% Implemented by tag_switch.m.
+%
+% XXX We should implement lookup switches on secondary tags, and (if the
+% switched-on type does not use any secondary tags) on primary tags as well.
+%
+% 4 For switches on floats, we could generate code that does binary search.
+% However, this is not yet implemented.
%
-% For all other cases (or if the --smart-indexing option was disabled),
-% we just generate a chain of if-then-elses.
+% If we cannot apply any of the above smart indexing strategies, or if the
+% --smart-indexing option was disabled, then this module just generates
+% a chain of if-then-elses.
%
%-----------------------------------------------------------------------------%
@@ -249,7 +280,7 @@
MaybeEnd, SwitchCode, !CI)
)
;
- SwitchCategory = other_switch,
+ SwitchCategory = float_switch,
order_and_generate_cases(TaggedCases, VarRval, VarType,
VarName, CodeModel, CanFail, GoalInfo, EndLabel,
MaybeEnd, SwitchCode, !CI)
@@ -276,23 +307,22 @@
% Generate a switch as a chain of if-then-elses.
%
- % To generate a case for a switch we generate
- % code to do a tag-test and fall through to the next case in
- % the event of failure.
+ % To generate a case for a switch, we generate code to do a tag-test,
+ % and fall through to the next case in the event of failure.
%
% Each case except the last consists of
%
- % a tag test, jumping to the next case if it fails
- % the goal for that case
- % code to move variables to where the store map says they ought to be
- % a branch to the end of the switch.
+ % - a tag test, jumping to the next case if it fails;
+ % - the goal for that case;
+ % - code to move variables to where the store map says they ought to be;
+ % - a branch to the end of the switch.
%
% For the last case, if the switch covers all cases that can occur,
- % we don't need to generate the tag test, and we never need to
- % generate the branch to the end of the switch.
+ % we don't need to generate the tag test, and we never need to generate
+ % the branch to the end of the switch.
%
- % After the last case, we put the end-of-switch label which other
- % cases branch to after their case goals.
+ % After the last case, we put the end-of-switch label which other cases
+ % branch to after their case goals.
%
% In the important special case of a det switch with two cases,
% we try to find out which case will be executed more frequently,
Index: compiler/switch_util.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/switch_util.m,v
retrieving revision 1.57
diff -u -b -r1.57 switch_util.m
--- compiler/switch_util.m 21 Jul 2011 06:58:27 -0000 1.57
+++ compiler/switch_util.m 25 Jul 2011 04:06:25 -0000
@@ -78,7 +78,7 @@
---> atomic_switch % a switch on int/char/enum
; string_switch
; tag_switch
- ; other_switch.
+ ; float_switch.
% Convert a type constructor category to a switch category.
%
@@ -192,14 +192,14 @@
pred(tagged_case, CaseRep, StateA, StateA, StateB, StateB, StateC, StateC)
::in(pred(in, out, in, out, in, out, in, out) is det),
StateA::in, StateA::out, StateB::in, StateB::out, StateC::in, StateC::out,
- map(int, string_hash_slot(CaseRep))::out, unary_op::out) is det.
+ map(int, string_hash_slot(CaseRep))::out, unary_op::out, int::out) is det.
% For a string lookup switch, compute the hash value for each string,
% and store the associated data in a map from the hash values.
%
:- pred construct_string_hash_lookup_cases(assoc_list(string, CaseRep)::in,
- int::in, int::in, map(int, string_hash_slot(CaseRep))::out, unary_op::out)
- is det.
+ int::in, int::in, map(int, string_hash_slot(CaseRep))::out,
+ unary_op::out, int::out) is det.
%-----------------------------------------------------------------------------%
%
@@ -491,7 +491,7 @@
SwitchCat = string_switch
;
CtorCat = ctor_cat_builtin(cat_builtin_float),
- SwitchCat = other_switch
+ SwitchCat = float_switch
;
CtorCat = ctor_cat_user(cat_user_general),
SwitchCat = tag_switch
@@ -743,7 +743,8 @@
%
construct_string_hash_jump_cases(TaggedCases, TableSize, HashMask,
- RepresentCase, !StateA, !StateB, !StateC, HashSlotsMap, HashOp) :-
+ RepresentCase, !StateA, !StateB, !StateC, HashSlotsMap,
+ HashOp, NumCollisions) :-
string_hash_jump_cases(TaggedCases, HashMask, RepresentCase,
!StateA, !StateB, !StateC,
map.init, HashValsMap1, map.init, HashValsMap2, map.init, HashValsMap3,
@@ -754,13 +755,16 @@
),
( NumCollisions1 =< NumCollisions2, NumCollisions1 =< NumCollisions3 ->
HashValsMap = HashValsMap1,
- HashOp = hash_string
+ HashOp = hash_string,
+ NumCollisions = NumCollisions1
; NumCollisions2 =< NumCollisions3 ->
HashValsMap = HashValsMap2,
- HashOp = hash_string2
+ HashOp = hash_string2,
+ NumCollisions = NumCollisions2
;
HashValsMap = HashValsMap3,
- HashOp = hash_string3
+ HashOp = hash_string3,
+ NumCollisions = NumCollisions3
),
map.to_assoc_list(HashValsMap, HashValsList),
calc_string_hash_slots(TableSize, HashValsList, HashValsMap, HashSlotsMap).
@@ -839,7 +843,7 @@
%-----------------------------------------------------------------------------%
construct_string_hash_lookup_cases(StrsDatas, TableSize, HashMask,
- HashSlotsMap, HashOp) :-
+ HashSlotsMap, HashOp, NumCollisions) :-
string_hash_lookup_cases(StrsDatas, HashMask,
map.init, HashValsMap1, map.init, HashValsMap2, map.init, HashValsMap3,
0, NumCollisions1, 0, NumCollisions2, 0, NumCollisions3),
@@ -849,13 +853,16 @@
),
( NumCollisions1 =< NumCollisions2, NumCollisions1 =< NumCollisions3 ->
HashValsMap = HashValsMap1,
- HashOp = hash_string
+ HashOp = hash_string,
+ NumCollisions = NumCollisions1
; NumCollisions2 =< NumCollisions3 ->
HashValsMap = HashValsMap2,
- HashOp = hash_string2
+ HashOp = hash_string2,
+ NumCollisions = NumCollisions2
;
HashValsMap = HashValsMap3,
- HashOp = hash_string3
+ HashOp = hash_string3,
+ NumCollisions = NumCollisions3
),
map.to_assoc_list(HashValsMap, HashValsList),
calc_string_hash_slots(TableSize, HashValsList, HashValsMap, HashSlotsMap).
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