[m-rev.] for post-commit review: implement lookup switches on string for MLDS

Zoltan Somogyi zs at csse.unimelb.edu.au
Tue Aug 9 15:32:21 AEST 2011


With this diff, the compiler finds 41 hashed and 66 binary lookup switches
in the browser, compiler, library etc directories. This compares to what are
now 19 hashed and 22 binary jump-based (i.e. non-lookup) switches on strings.
All of the switches we now translate to lookup tables would have been jump
switches before.

Since the compiler does not spend significant amounts of time switching
on strings, this diff has negligible impact on the compiler's speed.

Zoltan.

Implement lookup table versions of hash and binary search switches for strings
in the MLDS backend (those versions already exist in the LLDS backend).

compiler/ml_string_switch.m:
	Make the above change.

	Where possible, factor out and reuse existing code.

compiler/ml_lookup_switch.m:
	Break up the predicate that used to both test a switch whether it is a
	lookup switch and also generate code for it if it was, into two parts,
	each doing just one job. The first part is now useful for switches on
	strings as well.

	Group auxiliary predicates with the main predicates they support.

	Factor out some code into new predicates, and export them for use
	by the new code in ml_string_switch.m.

	Make some predicates tail recursive.

	Remove some predicates made unnecessary by changes to lookup_switch.m.

compiler/ml_switch_gen.m:
	Invoke the new code when appropriate, and conform to the updated
	interface of ml_lookup_switch.m.

compiler/switch_util.m:
	Change some types, and the predicates that operate on them, to make
	them useful for lookup switches for the MLDS backend as well the LLDS
	backend.

	Add some utility predicates.

compiler/lookup_switch.m:
	Change the interface of some of the predicates in this module to allow
	us to factor out some common code from the higher order values passed
	by callers.

	Conform to the changes in switch_util.m.

compiler/string_switch.m:
	Conform to changes in switch_util.m.

compiler/switch_gen.m:
	Conform to changes in lookup_switch.m.

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.93
diff -u -b -r1.93 lookup_switch.m
--- compiler/lookup_switch.m	26 Jul 2011 00:25:22 -0000	1.93
+++ compiler/lookup_switch.m	5 Aug 2011 03:12:51 -0000
@@ -55,7 +55,6 @@
 :- import_module parse_tree.set_of_var.
 
 :- import_module list.
-:- import_module map.
 
 %-----------------------------------------------------------------------------%
 
@@ -63,36 +62,22 @@
     --->    lookup_switch_info(
                 % The map from the switched-on value to the values of the
                 % variables in each solution.
-                lsi_cases               :: case_consts(Key, rval),
+                lsi_cases               ::  case_consts(Key, rval,
+                                                case_consts_several_llds),
 
-                % The output variables.
-                lsi_variables           :: list(prog_var),
+                % The output variables, which become (some of) the fields
+                % in each row of a lookup table.
+                lsi_out_variables       ::  list(prog_var),
 
-                % The types of the fields in the C structure we generate
-                % for each case.
-                lsi_field_types         :: list(llds_type),
+                % The types of the fields holding output variables.
+                lsi_out_types           ::  list(llds_type),
 
                 lsi_liveness            :: set_of_progvar
             ).
 
-:- pred record_lookup_for_tagged_cons_id_int(soln_consts(rval)::in,
-    tagged_cons_id::in,
-    map(int, soln_consts(rval))::in, map(int, soln_consts(rval))::out) is det.
-
-:- pred record_lookup_for_tagged_cons_id_string(soln_consts(rval)::in,
-    tagged_cons_id::in,
-    map(string, soln_consts(rval))::in, map(string, soln_consts(rval))::out)
-    is det.
-
-:- type record_switch_lookup(Key) ==
-    pred(soln_consts(rval), tagged_cons_id,
-    map(Key, soln_consts(rval)), map(Key, soln_consts(rval))).
-:- inst record_switch_lookup ==
-    (pred(in, in, in, out) is det).
-
     % Decide whether we can generate code for this switch using a lookup table.
     %
-:- pred is_lookup_switch(record_switch_lookup(Key)::in(record_switch_lookup),
+:- pred is_lookup_switch(pred(cons_tag, Key)::in(pred(in, out) is det),
     list(tagged_case)::in, hlds_goal_info::in, abs_store_map::in,
     branch_end::in, branch_end::out, lookup_switch_info(Key)::out,
     code_info::in, code_info::out) is semidet.
@@ -180,6 +165,7 @@
 :- import_module bool.
 :- import_module cord.
 :- import_module int.
+:- import_module map.
 :- import_module maybe.
 :- import_module pair.
 :- import_module require.
@@ -189,8 +175,8 @@
 
 %-----------------------------------------------------------------------------%
 
-is_lookup_switch(RecordLookupForTaggedConsId, TaggedCases, GoalInfo, StoreMap,
-        !MaybeEnd, LookupSwitchInfo, !CI) :-
+is_lookup_switch(GetTag, TaggedCases, GoalInfo, StoreMap, !MaybeEnd,
+        LookupSwitchInfo, !CI) :-
     % Most of this predicate is taken from dense_switch.m.
 
     % We need the code_info structure to generate code for the cases to
@@ -200,10 +186,9 @@
     figure_out_output_vars(!.CI, GoalInfo, OutVars),
     set.list_to_set(OutVars, ArmNonLocals),
     remember_position(!.CI, CurPos),
-    generate_constants_for_lookup_switch(RecordLookupForTaggedConsId,
-        TaggedCases, OutVars, ArmNonLocals, StoreMap, Liveness,
-        map.init, CaseSolnMap, !MaybeEnd, set_of_var.init, ResumeVars,
-        no, GoalsMayModifyTrail, !CI),
+    generate_constants_for_lookup_switch(GetTag, TaggedCases,
+        OutVars, ArmNonLocals, StoreMap, Liveness, map.init, CaseSolnMap,
+        !MaybeEnd, set_of_var.init, ResumeVars, no, GoalsMayModifyTrail, !CI),
     map.to_assoc_list(CaseSolnMap, CaseSolns),
     reset_to_position(CurPos, !CI),
     VarTypes = get_var_types(!.CI),
@@ -212,8 +197,8 @@
         CaseConsts = all_one_soln(CaseValuePairs),
         assoc_list.values(CaseValuePairs, CaseValues)
     ;
-        CaseConsts = some_several_solns(CaseSolns, ResumeVars,
-            GoalsMayModifyTrail),
+        CaseConsts = some_several_solns(CaseSolns,
+            case_consts_several_llds(ResumeVars, GoalsMayModifyTrail)),
         % This generates CaseValues in reverse order of index, but given that
         % we only use CaseValues to find out the right OutLLDSTypes,
         % this is OK.
@@ -228,19 +213,19 @@
 %---------------------------------------------------------------------------%
 
 :- pred generate_constants_for_lookup_switch(
-    record_switch_lookup(Key)::in(record_switch_lookup),
+    pred(cons_tag, Key)::in(pred(in, out) is det),
     list(tagged_case)::in, list(prog_var)::in, set(prog_var)::in,
     abs_store_map::in, set_of_progvar::out,
     map(Key, soln_consts(rval))::in, map(Key, soln_consts(rval))::out,
     branch_end::in, branch_end::out, set_of_progvar::in, set_of_progvar::out,
     bool::in, bool::out, code_info::in, code_info::out) is semidet.
 
-generate_constants_for_lookup_switch(_RecordLookupForTaggedConsId,
-        [], _Vars, _ArmNonLocals, _StoreMap, set_of_var.init, !IndexMap,
+generate_constants_for_lookup_switch(_GetTag, [],
+        _Vars, _ArmNonLocals, _StoreMap, set_of_var.init, !IndexMap,
         !MaybeEnd, !ResumeVars, !GoalsMayModifyTrail, !CI).
-generate_constants_for_lookup_switch(RecordLookupForTaggedConsId,
-        [TaggedCase | TaggedCases], Vars, ArmNonLocals, StoreMap, Liveness,
-        !IndexMap, !MaybeEnd, !ResumeVars, !GoalsMayModifyTrail, !CI) :-
+generate_constants_for_lookup_switch(GetTag, [TaggedCase | TaggedCases],
+        Vars, ArmNonLocals, StoreMap, Liveness, !IndexMap,
+        !MaybeEnd, !ResumeVars, !GoalsMayModifyTrail, !CI) :-
     TaggedCase = tagged_case(TaggedMainConsId, TaggedOtherConsIds, _, Goal),
     Goal = hlds_goal(GoalExpr, GoalInfo),
 
@@ -294,41 +279,37 @@
             !MaybeEnd, Liveness, !CI),
         SolnConsts = one_soln(Soln)
     ),
-    RecordLookupForTaggedConsId(SolnConsts, TaggedMainConsId, !IndexMap),
-    record_lookup_for_tagged_cons_ids(RecordLookupForTaggedConsId, SolnConsts,
+    record_lookup_for_tagged_cons_id(GetTag, SolnConsts,
+        TaggedMainConsId, !IndexMap),
+    record_lookup_for_tagged_cons_ids(GetTag, SolnConsts,
         TaggedOtherConsIds, !IndexMap),
-    generate_constants_for_lookup_switch(RecordLookupForTaggedConsId,
+    generate_constants_for_lookup_switch(GetTag,
         TaggedCases, Vars, ArmNonLocals, StoreMap, _LivenessRest,
         !IndexMap, !MaybeEnd, !ResumeVars, !GoalsMayModifyTrail, !CI).
 
 :- pred record_lookup_for_tagged_cons_ids(
-    record_switch_lookup(Key)::in(record_switch_lookup),
+    pred(cons_tag, Key)::in(pred(in, out) is det),
     soln_consts(rval)::in, list(tagged_cons_id)::in,
     map(Key, soln_consts(rval))::in, map(Key, soln_consts(rval))::out) is det.
 
-record_lookup_for_tagged_cons_ids(_RecordLookupForTaggedConsId, _SolnConsts,
-        [], !IndexMap).
-record_lookup_for_tagged_cons_ids(RecordLookupForTaggedConsId, SolnConsts,
+record_lookup_for_tagged_cons_ids(_GetTag, _SolnConsts, [], !IndexMap).
+record_lookup_for_tagged_cons_ids(GetTag, SolnConsts,
         [TaggedConsId | TaggedConsIds], !IndexMap) :-
-    RecordLookupForTaggedConsId(SolnConsts, TaggedConsId, !IndexMap),
-    record_lookup_for_tagged_cons_ids(RecordLookupForTaggedConsId, SolnConsts,
+    record_lookup_for_tagged_cons_id(GetTag, SolnConsts,
+        TaggedConsId, !IndexMap),
+    record_lookup_for_tagged_cons_ids(GetTag, SolnConsts,
         TaggedConsIds, !IndexMap).
 
-record_lookup_for_tagged_cons_id_int(SolnConsts, TaggedConsId, !IndexMap) :-
-    TaggedConsId = tagged_cons_id(_ConsId, ConsTag),
-    ( ConsTag = int_tag(Index) ->
-        map.det_insert(Index, SolnConsts, !IndexMap)
-    ;
-        unexpected($module, $pred, "not int_tag")
-    ).
+:- pred record_lookup_for_tagged_cons_id(
+    pred(cons_tag, Key)::in(pred(in, out) is det),
+    soln_consts(rval)::in, tagged_cons_id::in,
+    map(Key, soln_consts(rval))::in, map(Key, soln_consts(rval))::out) is det.
 
-record_lookup_for_tagged_cons_id_string(SolnConsts, TaggedConsId, !IndexMap) :-
+record_lookup_for_tagged_cons_id(GetTag, SolnConsts, TaggedConsId,
+        !IndexMap) :-
     TaggedConsId = tagged_cons_id(_ConsId, ConsTag),
-    ( ConsTag = string_tag(Index) ->
-        map.det_insert(Index, SolnConsts, !IndexMap)
-    ;
-        unexpected($module, $pred, "not int_tag")
-    ).
+    GetTag(ConsTag, Index),
+    map.det_insert(Index, SolnConsts, !IndexMap).
 
 %---------------------------------------------------------------------------%
 
@@ -368,8 +349,8 @@
             StartVal, EndVal, CaseValues, OutVars, OutTypes,
             NeedBitVecCheck, Liveness, RestCode, !CI)
     ;
-        CaseConsts = some_several_solns(CaseSolns, ResumeVars,
-            GoalsMayModifyTrail),
+        CaseConsts = some_several_solns(CaseSolns,
+            case_consts_several_llds(ResumeVars, GoalsMayModifyTrail)),
         (
             GoalsMayModifyTrail = yes,
             get_emit_trail_ops(!.CI, EmitTrailOps),
Index: compiler/ml_lookup_switch.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/ml_lookup_switch.m,v
retrieving revision 1.10
diff -u -b -r1.10 ml_lookup_switch.m
--- compiler/ml_lookup_switch.m	23 May 2011 05:08:06 -0000	1.10
+++ compiler/ml_lookup_switch.m	8 Aug 2011 12:27:40 -0000
@@ -23,6 +23,7 @@
 
 :- import_module backend_libs.switch_util.
 :- import_module hlds.code_model.
+:- import_module hlds.hlds_data.
 :- import_module hlds.hlds_goal.
 :- import_module ml_backend.ml_gen_info.
 :- import_module ml_backend.mlds.
@@ -30,15 +31,64 @@
 
 :- import_module list.
 :- import_module set.
+:- import_module unit.
 
 %-----------------------------------------------------------------------------%
 
-    % Generate MLDS code for a lookup switch, if possible.
+:- type ml_lookup_switch_info(Key)
+    --->    ml_lookup_switch_info(
+                % The map from the switched-on value to the values of the
+                % variables in each solution.
+                mllsi_cases             ::  case_consts(Key, mlds_rval, unit),
+
+                % The output variables, which become (some of) the fields
+                % in each row of a lookup table.
+                mllsi_out_variables     ::  list(prog_var),
+
+                % The types of the fields holding output variables.
+                mllsi_out_types         ::  list(mlds_type)
+            ).
+
+    % Is the given list of cases implementable as a lookup switch?
     %
-:- pred ml_gen_lookup_switch(prog_var::in, list(tagged_case)::in,
-    set(prog_var)::in, code_model::in, prog_context::in,
-    int::in, int::in, need_bit_vec_check::in, need_range_check::in,
-    statement::out, ml_gen_info::in, ml_gen_info::out) is semidet.
+:- pred ml_is_lookup_switch(pred(cons_tag, Key)::in(pred(in, out) is det),
+    prog_var::in, list(tagged_case)::in, set(prog_var)::in, code_model::in,
+    ml_lookup_switch_info(Key)::out,
+    ml_gen_info::in, ml_gen_info::out) is semidet.
+
+%-----------------------------------------------------------------------------%
+
+    % Generate MLDS code for the lookup switch.
+    %
+:- pred ml_gen_lookup_switch(prog_var::in, ml_lookup_switch_info(int)::in,
+    code_model::in, prog_context::in, int::in, int::in,
+    need_bit_vec_check::in, need_range_check::in,
+    statement::out, ml_gen_info::in, ml_gen_info::out) is det.
+
+%-----------------------------------------------------------------------------%
+%
+% These types and predicates are exported because they are useful in the
+% implementation of string lookup switches.
+%
+
+:- type ml_several_soln_lookup_vars
+    --->    ml_several_soln_lookup_vars(
+                msslv_num_later_solns_var       :: mlds_lval,
+                msslv_later_slot_var            :: mlds_lval,
+                msslv_limit_var                 :: mlds_lval,
+                msslv_limit_assign_statement    :: statement,
+                msslv_incr_later_slot_statement :: statement,
+                msslv_denfs                     :: list(mlds_defn)
+            ).
+
+:- pred make_several_soln_lookup_vars(mlds_context::in,
+    ml_several_soln_lookup_vars::out,
+    ml_gen_info::in, ml_gen_info::out) is det.
+
+:- func ml_construct_later_soln_row(mlds_type, list(mlds_rval)) =
+    mlds_initializer.
+
+:- func ml_default_value_for_type(mlds_type) = mlds_rval.
 
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
@@ -47,7 +97,6 @@
 
 :- import_module backend_libs.builtin_ops.
 :- import_module hlds.goal_form.
-:- import_module hlds.hlds_data.
 :- import_module hlds.hlds_module.
 :- import_module ml_backend.ml_code_util.
 :- import_module ml_backend.ml_global_data.
@@ -55,6 +104,7 @@
 
 :- import_module assoc_list.
 :- import_module bool.
+:- import_module cord.
 :- import_module int.
 :- import_module map.
 :- import_module maybe.
@@ -63,18 +113,92 @@
 
 %-----------------------------------------------------------------------------%
 
-ml_gen_lookup_switch(SwitchVar, TaggedCases, NonLocals, CodeModel, Context,
-        StartVal, EndVal, NeedBitVecCheck, NeedRangeCheck, Statement, !Info) :-
+ml_is_lookup_switch(GetTag, SwitchVar, TaggedCases, NonLocals, CodeModel,
+        LookupSwitchInfo, !Info) :-
     set.remove(SwitchVar, NonLocals, OtherNonLocals),
     set.to_sorted_list(OtherNonLocals, OutVars),
-    ml_generate_constants_for_lookup_switch(CodeModel, OutVars, OtherNonLocals,
-        TaggedCases, map.init, CaseSolnMap, !Info),
     % While the LLDS backend has to worry about about implementing trailing
     % for model_non lookup switches, we do not. The MLDS backend implements
     % trailing by a HLDS-to-HLDS transform (which is in add_trail_ops.m),
     % so we can get here only if trailing is not enabled, since otherwise
     % the calls or foreign_procs inserted into all non-first disjuncts
-    % would have caused ml_generate_constants_for_lookup_switch to fail.
+    % would cause ml_generate_constants_for_lookup_switch to fail.
+    ml_generate_constants_for_lookup_switch(GetTag, CodeModel,
+        OutVars, OtherNonLocals, TaggedCases, map.init, CaseSolnMap, !Info),
+    map.to_assoc_list(CaseSolnMap, CaseSolns),
+    ( project_all_to_one_solution(CaseSolns, CaseValuePairs) ->
+        CaseConsts = all_one_soln(CaseValuePairs)
+    ;
+        CaseConsts = some_several_solns(CaseSolns, unit)
+    ),
+    ml_gen_info_get_module_info(!.Info, ModuleInfo),
+    ml_gen_info_get_var_types(!.Info, VarTypes),
+    list.map(map.lookup(VarTypes), OutVars, OutTypes),
+    FieldTypes =
+        list.map(mercury_type_to_mlds_type(ModuleInfo), OutTypes),
+    LookupSwitchInfo = ml_lookup_switch_info(CaseConsts, OutVars, FieldTypes).
+
+:- pred ml_generate_constants_for_lookup_switch(
+    pred(cons_tag, T)::in(pred(in, out) is det),
+    code_model::in, list(prog_var)::in, set(prog_var)::in,
+    list(tagged_case)::in,
+    map(T, soln_consts(mlds_rval))::in,
+    map(T, soln_consts(mlds_rval))::out,
+    ml_gen_info::in, ml_gen_info::out) is semidet.
+
+ml_generate_constants_for_lookup_switch(_GetTag, _CodeModel,
+        _OutVars, _ArmNonLocals, [], !IndexMap, !Info).
+ml_generate_constants_for_lookup_switch(GetTag, CodeModel,
+        OutVars, ArmNonLocals, [TaggedCase | TaggedCases], !IndexMap, !Info) :-
+    TaggedCase = tagged_case(TaggedMainConsId, TaggedOtherConsIds, _, Goal),
+    Goal = hlds_goal(GoalExpr, _GoalInfo),
+    ( GoalExpr = disj(Disjuncts) ->
+        (
+            Disjuncts = []
+        ;
+            Disjuncts = [FirstDisjunct | LaterDisjuncts],
+            goal_is_conj_of_unify(ArmNonLocals, FirstDisjunct),
+            all_disjuncts_are_conj_of_unify(ArmNonLocals, LaterDisjuncts),
+            ml_generate_constants_for_arm(OutVars, FirstDisjunct, FirstSoln,
+                !Info),
+            ml_generate_constants_for_arms(OutVars, LaterDisjuncts, LaterSolns,
+                !Info),
+            SolnConsts = several_solns(FirstSoln, LaterSolns),
+            ml_record_lookup_for_tagged_cons_id(GetTag, SolnConsts,
+                TaggedMainConsId, !IndexMap),
+            list.foldl(
+                ml_record_lookup_for_tagged_cons_id(GetTag, SolnConsts),
+                TaggedOtherConsIds, !IndexMap)
+        )
+    ;
+        goal_is_conj_of_unify(ArmNonLocals, Goal),
+        ml_generate_constants_for_arm(OutVars, Goal, Soln, !Info),
+        SolnConsts = one_soln(Soln),
+        ml_record_lookup_for_tagged_cons_id(GetTag, SolnConsts,
+            TaggedMainConsId, !IndexMap),
+        list.foldl(ml_record_lookup_for_tagged_cons_id(GetTag, SolnConsts),
+            TaggedOtherConsIds, !IndexMap)
+    ),
+    ml_generate_constants_for_lookup_switch(GetTag, CodeModel,
+        OutVars, ArmNonLocals, TaggedCases, !IndexMap, !Info).
+
+:- pred ml_record_lookup_for_tagged_cons_id(
+    pred(cons_tag, T)::in(pred(in, out) is det),
+    soln_consts(mlds_rval)::in, tagged_cons_id::in,
+    map(T, soln_consts(mlds_rval))::in,
+    map(T, soln_consts(mlds_rval))::out) is det.
+
+ml_record_lookup_for_tagged_cons_id(GetTag, SolnConsts, TaggedConsId,
+        !IndexMap) :-
+    TaggedConsId = tagged_cons_id(_ConsId, ConsTag),
+    GetTag(ConsTag, Index),
+    map.det_insert(Index, SolnConsts, !IndexMap).
+
+%-----------------------------------------------------------------------------%
+
+ml_gen_lookup_switch(SwitchVar, LookupSwitchInfo, CodeModel, Context,
+        StartVal, EndVal, NeedBitVecCheck, NeedRangeCheck, Statement, !Info) :-
+    LookupSwitchInfo = ml_lookup_switch_info(CaseConsts, OutVars, FieldTypes),
 
     ml_gen_var(!.Info, SwitchVar, SwitchVarLval),
     SwitchVarRval = ml_lval(SwitchVarLval),
@@ -84,55 +208,51 @@
         StartRval = ml_const(mlconst_int(StartVal)),
         IndexRval = ml_binop(int_sub, SwitchVarRval, StartRval)
     ),
-
-    map.to_assoc_list(CaseSolnMap, CaseSolns),
-    ( project_all_to_one_solution(CaseSolns, CaseValuePairs) ->
-        ml_gen_simple_lookup_switch(IndexRval, OutVars, CaseValuePairs,
-            CodeModel, Context, StartVal, EndVal,
+    (
+        CaseConsts = all_one_soln(CaseValuePairs),
+        ml_gen_simple_lookup_switch(IndexRval, OutVars, FieldTypes,
+            CaseValuePairs, CodeModel, Context, StartVal, EndVal,
             NeedBitVecCheck, NeedRangeCheck, Statement, !Info)
     ;
+        CaseConsts = some_several_solns(CaseSolns, _Unit),
         expect(unify(CodeModel, model_non), $module, $pred,
             "CodeModel != model_non"),
-        ml_gen_model_non_lookup_switch(IndexRval, OutVars, CaseSolns,
-            Context, StartVal, EndVal, NeedBitVecCheck, NeedRangeCheck,
-            Statement, !Info)
+        ml_gen_several_soln_lookup_switch(IndexRval, OutVars, FieldTypes,
+            CaseSolns, Context, StartVal, EndVal,
+            NeedBitVecCheck, NeedRangeCheck, Statement, !Info)
     ).
 
 %-----------------------------------------------------------------------------%
 
 :- pred ml_gen_simple_lookup_switch(mlds_rval::in, list(prog_var)::in,
-    assoc_list(int, list(mlds_rval))::in, code_model::in, prog_context::in,
-    int::in, int::in, need_bit_vec_check::in, need_range_check::in,
+    list(mlds_type)::in, assoc_list(int, list(mlds_rval))::in, code_model::in,
+    prog_context::in, int::in, int::in,
+    need_bit_vec_check::in, need_range_check::in,
     statement::out, ml_gen_info::in, ml_gen_info::out) is det.
 
-ml_gen_simple_lookup_switch(IndexRval, OutVars, CaseValues, CodeModel, Context,
-        StartVal, EndVal, NeedBitVecCheck, NeedRangeCheck, Statement, !Info) :-
+ml_gen_simple_lookup_switch(IndexRval, OutVars, OutTypes, CaseValues,
+        CodeModel, Context, StartVal, EndVal, NeedBitVecCheck, NeedRangeCheck,
+        Statement, !Info) :-
     ml_gen_info_get_module_info(!.Info, ModuleInfo),
     module_info_get_name(ModuleInfo, ModuleName),
     MLDS_ModuleName = mercury_module_name_to_mlds(ModuleName),
     MLDS_Context = mlds_make_context(Context),
     ml_gen_info_get_target(!.Info, Target),
 
-    ml_gen_info_get_var_types(!.Info, VarTypes),
-    list.map(map.lookup(VarTypes), OutVars, FieldTypes),
-    MLDS_FieldTypes =
-        list.map(mercury_type_to_mlds_type(ModuleInfo), FieldTypes),
-
     ml_gen_info_get_global_data(!.Info, GlobalData0),
     ml_gen_static_vector_type(MLDS_ModuleName, MLDS_Context, Target,
-        MLDS_FieldTypes, StructTypeNum, StructType, FieldIds,
+        OutTypes, StructTypeNum, StructType, FieldIds,
         GlobalData0, GlobalData1),
 
     ml_construct_simple_switch_vector(ModuleInfo, StructType,
-        MLDS_FieldTypes, StartVal, CaseValues, RowInitializers),
+        OutTypes, StartVal, CaseValues, RowInitializers),
 
     ml_gen_static_vector_defn(MLDS_ModuleName, StructTypeNum, RowInitializers,
         VectorCommon, GlobalData1, GlobalData),
     ml_gen_info_set_global_data(GlobalData, !Info),
 
-    ml_generate_field_assigns(OutVars, MLDS_FieldTypes, FieldIds,
-        VectorCommon, StructType, IndexRval, MLDS_Context, LookupStatements,
-        !Info),
+    ml_generate_field_assigns(OutVars, OutTypes, FieldIds, VectorCommon,
+        StructType, IndexRval, MLDS_Context, LookupStatements, !Info),
 
     (
         CodeModel = model_det,
@@ -203,50 +323,32 @@
 
 %-----------------------------------------------------------------------------%
 
-:- pred ml_gen_model_non_lookup_switch(mlds_rval::in, list(prog_var)::in,
-    assoc_list(int, soln_consts(mlds_rval))::in, prog_context::in,
-    int::in, int::in, need_bit_vec_check::in, need_range_check::in,
+:- pred ml_gen_several_soln_lookup_switch(mlds_rval::in, list(prog_var)::in,
+    list(mlds_type)::in, assoc_list(int, soln_consts(mlds_rval))::in,
+    prog_context::in, int::in, int::in,
+    need_bit_vec_check::in, need_range_check::in,
     statement::out, ml_gen_info::in, ml_gen_info::out) is det.
 
-ml_gen_model_non_lookup_switch(IndexRval, OutVars, CaseSolns, Context,
-        StartVal, EndVal, NeedBitVecCheck, NeedRangeCheck, Statement,
-        !Info) :-
+ml_gen_several_soln_lookup_switch(IndexRval, OutVars, OutTypes,
+        CaseSolns, Context, StartVal, EndVal, NeedBitVecCheck, NeedRangeCheck,
+        Statement, !Info) :-
     ml_gen_info_get_module_info(!.Info, ModuleInfo),
     module_info_get_name(ModuleInfo, ModuleName),
     MLDS_ModuleName = mercury_module_name_to_mlds(ModuleName),
     MLDS_Context = mlds_make_context(Context),
     ml_gen_info_get_target(!.Info, Target),
 
-    MLDS_IntType = mlds_native_int_type,
+    make_several_soln_lookup_vars(MLDS_Context, SeveralSolnLookupVars, !Info),
+    SeveralSolnLookupVars = ml_several_soln_lookup_vars(NumLaterSolnsVarLval,
+        LaterSlotVarLval, LimitVarLval,
+        LimitAssignStatement, IncrLaterSlotVarStatement, Defns),
 
-    ml_gen_info_new_aux_var_name("num_later_solns", NumLaterSolnsVar, !Info),
-    % We never need to trace ints.
-    NumLaterSolnsVarDefn = ml_gen_mlds_var_decl(mlds_data_var(NumLaterSolnsVar),
-        MLDS_IntType, gc_no_stmt, MLDS_Context),
-    ml_gen_var_lval(!.Info, NumLaterSolnsVar, MLDS_IntType,
-        NumLaterSolnsVarLval),
     NumLaterSolnsVarRval = ml_lval(NumLaterSolnsVarLval),
-
-    ml_gen_info_new_aux_var_name("later_slot", LaterSlotVar, !Info),
-    % We never need to trace ints.
-    LaterSlotVarDefn = ml_gen_mlds_var_decl(mlds_data_var(LaterSlotVar),
-        MLDS_IntType, gc_no_stmt, MLDS_Context),
-    ml_gen_var_lval(!.Info, LaterSlotVar, MLDS_IntType, LaterSlotVarLval),
     LaterSlotVarRval = ml_lval(LaterSlotVarLval),
-
-    ml_gen_info_new_aux_var_name("limit", LimitVar, !Info),
-    % We never need to trace ints.
-    LimitVarDefn = ml_gen_mlds_var_decl(mlds_data_var(LimitVar),
-        MLDS_IntType, gc_no_stmt, MLDS_Context),
-    ml_gen_var_lval(!.Info, LimitVar, MLDS_IntType, LimitVarLval),
     LimitVarRval = ml_lval(LimitVarLval),
 
-    ml_gen_info_get_var_types(!.Info, VarTypes),
-    list.map(map.lookup(VarTypes), OutVars, FieldTypes),
-    MLDS_FieldTypes =
-        list.map(mercury_type_to_mlds_type(ModuleInfo), FieldTypes),
-    FirstSolnFieldTypes = [MLDS_IntType, MLDS_IntType | MLDS_FieldTypes],
-    LaterSolnFieldTypes = MLDS_FieldTypes,
+    MLDS_IntType = mlds_native_int_type,
+    FirstSolnFieldTypes = [MLDS_IntType, MLDS_IntType | OutTypes],
 
     ml_gen_call_current_success_cont(Context, CallContStatement, !Info),
 
@@ -255,7 +357,7 @@
         FirstSolnFieldTypes, FirstSolnStructTypeNum, FirstSolnStructType,
         FirstSolnTableFieldIds, GlobalData0, GlobalData1),
     ml_gen_static_vector_type(MLDS_ModuleName, MLDS_Context, Target,
-        LaterSolnFieldTypes, LaterSolnStructTypeNum, LaterSolnStructType,
+        OutTypes, LaterSolnStructTypeNum, LaterSolnStructType,
         LaterSolnFieldIds, GlobalData1, GlobalData2),
     (
         ( FirstSolnTableFieldIds = []
@@ -266,13 +368,12 @@
         FirstSolnTableFieldIds =
             [NumLaterSolnsFieldId, FirstLaterRowFieldId | FirstSolnFieldIds]
     ),
-
     ml_construct_model_non_switch_vector(ModuleInfo, StartVal, EndVal,
-        0, CaseSolns,
-        FirstSolnStructType, LaterSolnStructType, LaterSolnFieldTypes,
-        FirstSolnRowInitializers, LaterSolnRowInitializers,
-        no, HadDummyRows),
-
+        0, CaseSolns, FirstSolnStructType, LaterSolnStructType, OutTypes,
+        [], RevFirstSolnRowInitializers,
+        cord.init, LaterSolnRowInitializersCord, no, HadDummyRows),
+    list.reverse(RevFirstSolnRowInitializers, FirstSolnRowInitializers),
+    LaterSolnRowInitializers = cord.list(LaterSolnRowInitializersCord),
     ml_gen_static_vector_defn(MLDS_ModuleName, FirstSolnStructTypeNum,
         FirstSolnRowInitializers, FirstSolnVectorCommon,
         GlobalData2, GlobalData3),
@@ -289,23 +390,13 @@
         FirstLaterRowFieldId,
         FirstSolnVectorCommon, FirstSolnStructType, IndexRval,
         MLDS_Context, LaterSlotVarLookupStatement, !Info),
-    % We must use LaterSolnFieldTypes here, since we handle the assignments
-    % from the first two fields separately.
-    ml_generate_field_assigns(OutVars, LaterSolnFieldTypes, FirstSolnFieldIds,
+    ml_generate_field_assigns(OutVars, OutTypes, FirstSolnFieldIds,
         FirstSolnVectorCommon, FirstSolnStructType, IndexRval,
         MLDS_Context, FirstSolnLookupStatements, !Info),
-    ml_generate_field_assigns(OutVars, LaterSolnFieldTypes, LaterSolnFieldIds,
+    ml_generate_field_assigns(OutVars, OutTypes, LaterSolnFieldIds,
         LaterSolnVectorCommon, LaterSolnStructType, LaterSlotVarRval,
         MLDS_Context, LaterSolnLookupStatements, !Info),
 
-    LimitAssignStmt = ml_stmt_atomic(assign(LimitVarLval, 
-        ml_binop(int_add, LaterSlotVarRval, NumLaterSolnsVarRval))),
-    LimitAssignStatement = statement(LimitAssignStmt, MLDS_Context),
-
-    IncrLaterSlotVarStmt = ml_stmt_atomic(assign(LaterSlotVarLval,
-        ml_binop(int_add, LaterSlotVarRval, ml_const(mlconst_int(1))))),
-    IncrLaterSlotVarStatement = statement(IncrLaterSlotVarStmt, MLDS_Context),
-
     FirstLookupSucceedStmt = ml_stmt_block([],
         FirstSolnLookupStatements ++ [CallContStatement]),
     FirstLookupSucceedStatement =
@@ -330,8 +421,7 @@
         NeedBitVecCheck = dont_need_bit_vec_check,
         expect(unify(HadDummyRows, no), $module, $pred,
             "bad dont_need_bit_vec_check"),
-        InRangeStmt = ml_stmt_block(
-            [NumLaterSolnsVarDefn, LaterSlotVarDefn, LimitVarDefn],
+        InRangeStmt = ml_stmt_block(Defns,
             [NumLaterSolnsLookupStatement | OneOrMoreSolnsStatements]),
         InRangeStatement = statement(InRangeStmt, MLDS_Context)
     ;
@@ -350,8 +440,7 @@
         ZeroOrMoreSolnsStatement =
             statement(ZeroOrMoreSolnsStmt, MLDS_Context),
 
-        InRangeStmt = ml_stmt_block(
-            [NumLaterSolnsVarDefn, LaterSlotVarDefn, LimitVarDefn],
+        InRangeStmt = ml_stmt_block(Defns,
             [NumLaterSolnsLookupStatement, ZeroOrMoreSolnsStatement]),
         InRangeStatement = statement(InRangeStmt, MLDS_Context)
     ),
@@ -369,6 +458,43 @@
         Statement = statement(Stmt, MLDS_Context)
     ).
 
+make_several_soln_lookup_vars(MLDS_Context, SeveralSolnLookupVars, !Info) :-
+    ml_gen_info_new_aux_var_name("num_later_solns", NumLaterSolnsVar, !Info),
+    % We never need to trace ints.
+    NumLaterSolnsVarDefn = ml_gen_mlds_var_decl(
+        mlds_data_var(NumLaterSolnsVar), mlds_native_int_type, gc_no_stmt,
+        MLDS_Context),
+    ml_gen_var_lval(!.Info, NumLaterSolnsVar, mlds_native_int_type,
+        NumLaterSolnsVarLval),
+
+    ml_gen_info_new_aux_var_name("later_slot", LaterSlotVar, !Info),
+    % We never need to trace ints.
+    LaterSlotVarDefn = ml_gen_mlds_var_decl(mlds_data_var(LaterSlotVar),
+        mlds_native_int_type, gc_no_stmt, MLDS_Context),
+    ml_gen_var_lval(!.Info, LaterSlotVar, mlds_native_int_type,
+        LaterSlotVarLval),
+
+    ml_gen_info_new_aux_var_name("limit", LimitVar, !Info),
+    % We never need to trace ints.
+    LimitVarDefn = ml_gen_mlds_var_decl(mlds_data_var(LimitVar),
+        mlds_native_int_type, gc_no_stmt, MLDS_Context),
+    ml_gen_var_lval(!.Info, LimitVar, mlds_native_int_type, LimitVarLval),
+
+    Defns = [NumLaterSolnsVarDefn, LaterSlotVarDefn, LimitVarDefn],
+
+    LaterSlotVarRval = ml_lval(LaterSlotVarLval),
+    NumLaterSolnsVarRval = ml_lval(NumLaterSolnsVarLval),
+    LimitAssignStmt = ml_stmt_atomic(assign(LimitVarLval, 
+        ml_binop(int_add, LaterSlotVarRval, NumLaterSolnsVarRval))),
+    LimitAssignStatement = statement(LimitAssignStmt, MLDS_Context),
+    IncrLaterSlotVarStmt = ml_stmt_atomic(assign(LaterSlotVarLval,
+        ml_binop(int_add, LaterSlotVarRval, ml_const(mlconst_int(1))))),
+    IncrLaterSlotVarStatement = statement(IncrLaterSlotVarStmt, MLDS_Context),
+
+    SeveralSolnLookupVars = ml_several_soln_lookup_vars(NumLaterSolnsVarLval,
+        LaterSlotVarLval, LimitVarLval,
+        LimitAssignStatement, IncrLaterSlotVarStatement, Defns).
+
 %-----------------------------------------------------------------------------%
 
     % The bitvector is an array of words (where we use the first 32 bits
@@ -448,33 +574,33 @@
 ml_generate_bit_vec_2([], _, _, !BitMap).
 ml_generate_bit_vec_2([Tag - _ | Rest], Start, WordBits, !BitMap) :-
     Val = Tag - Start,
-    Word = Val // WordBits,
+    WordNum = Val // WordBits,
     Offset = Val mod WordBits,
-    ( map.search(!.BitMap, Word, X0) ->
+    ( map.search(!.BitMap, WordNum, X0) ->
         X1 = X0 \/ (1 << Offset)
     ;
         X1 = (1 << Offset)
     ),
-    map.set(Word, X1, !BitMap),
+    map.set(WordNum, X1, !BitMap),
     ml_generate_bit_vec_2(Rest, Start, WordBits, !BitMap).
 
 :- pred ml_generate_bit_vec_initializers(list(pair(int))::in, int::in,
     list(mlds_rval)::out, list(mlds_initializer)::out) is det.
 
 ml_generate_bit_vec_initializers([], _, [], []).
-ml_generate_bit_vec_initializers([Word - Bits | Rest], Count,
+ml_generate_bit_vec_initializers(All @ [WordNum - Bits | Rest], Count,
         [Rval | Rvals], [Initializer | Initializers]) :-
-    ( Count < Word ->
+    ( Count < WordNum ->
         WordVal = 0,
-        Remainder = [Word - Bits | Rest]
+        Remainder = All
     ;
         WordVal = Bits,
         Remainder = Rest
     ),
     Rval = ml_const(mlconst_int(WordVal)),
     Initializer = init_obj(Rval),
-    Count1 = Count + 1,
-    ml_generate_bit_vec_initializers(Remainder, Count1, Rvals, Initializers).
+    ml_generate_bit_vec_initializers(Remainder, Count + 1,
+        Rvals, Initializers).
 
 %-----------------------------------------------------------------------------%
 
@@ -501,58 +627,38 @@
 :- pred ml_construct_model_non_switch_vector(module_info::in,
     int::in, int::in, int::in, assoc_list(int, soln_consts(mlds_rval))::in,
     mlds_type::in, mlds_type::in, list(mlds_type)::in,
-    list(mlds_initializer)::out, list(mlds_initializer)::out,
+    list(mlds_initializer)::in, list(mlds_initializer)::out,
+    cord(mlds_initializer)::in, cord(mlds_initializer)::out,
     bool::in, bool::out) is det.
 
 ml_construct_model_non_switch_vector(ModuleInfo, CurIndex, EndVal,
-        NextLaterSolnRow, [],
+        !.NextLaterSolnRow, [],
         FirstSolnStructType, LaterSolnStructType, FieldTypes,
-        FirstSolnRowInitializers, LaterSolnRowInitializers, !HadDummyRows) :-
+        !RevFirstSolnRowInitializers, !LaterSolnRowInitializersCord,
+        !HadDummyRows) :-
     ( CurIndex > EndVal ->
-        FirstSolnRowInitializers = [],
-        LaterSolnRowInitializers = []
+        true
     ;
+        make_dummy_first_soln_row(FirstSolnStructType, FieldTypes,
+            !RevFirstSolnRowInitializers),
         !:HadDummyRows = yes,
-        FieldRvals = list.map(ml_default_value_for_type, FieldTypes),
-        FieldInitializers = list.map(wrap_init_obj, FieldRvals),
-        NumLaterSolnsInitializer = gen_init_int(-1),
-        FirstLaterSlotInitializer = gen_init_int(-1),
-        FirstSolnFieldInitializers =
-            [NumLaterSolnsInitializer, FirstLaterSlotInitializer
-                | FieldInitializers],
-        FirstSolnRowInitializer =
-            init_struct(FirstSolnStructType, FirstSolnFieldInitializers),
         ml_construct_model_non_switch_vector(ModuleInfo, CurIndex + 1, EndVal,
-            NextLaterSolnRow, [],
+            !.NextLaterSolnRow, [],
             FirstSolnStructType, LaterSolnStructType, FieldTypes,
-            FirstSolnRowInitializersTail, LaterSolnRowInitializers,
-            !HadDummyRows),
-        FirstSolnRowInitializers =
-            [FirstSolnRowInitializer | FirstSolnRowInitializersTail]
+            !RevFirstSolnRowInitializers, !LaterSolnRowInitializersCord,
+            !HadDummyRows)
     ).
 ml_construct_model_non_switch_vector(ModuleInfo, CurIndex, EndVal,
-        NextLaterSolnRow, [Pair | Pairs],
+        !.NextLaterSolnRow, [Pair | Pairs],
         FirstSolnStructType, LaterSolnStructType, FieldTypes,
-        FirstSolnRowInitializers, LaterSolnRowInitializers, !HadDummyRows) :-
+        !RevFirstSolnRowInitializers, !LaterSolnRowInitializersCord,
+        !HadDummyRows) :-
     Pair = Index - Soln,
     ( CurIndex < Index ->
+        make_dummy_first_soln_row(FirstSolnStructType, FieldTypes,
+            !RevFirstSolnRowInitializers),
         !:HadDummyRows = yes,
-        FieldRvals = list.map(ml_default_value_for_type, FieldTypes),
-        FieldInitializers = list.map(wrap_init_obj, FieldRvals),
-        NumLaterSolnsInitializer = gen_init_int(-1),
-        FirstLaterSlotInitializer = gen_init_int(-1),
-        FirstSolnFieldInitializers =
-            [NumLaterSolnsInitializer, FirstLaterSlotInitializer
-                | FieldInitializers],
-        FirstSolnRowInitializer =
-            init_struct(FirstSolnStructType, FirstSolnFieldInitializers),
-        ml_construct_model_non_switch_vector(ModuleInfo, CurIndex + 1, EndVal,
-            NextLaterSolnRow, [Pair | Pairs],
-            FirstSolnStructType, LaterSolnStructType, FieldTypes,
-            FirstSolnRowInitializersTail, LaterSolnRowInitializers,
-            !HadDummyRows),
-        FirstSolnRowInitializers =
-            [FirstSolnRowInitializer | FirstSolnRowInitializersTail]
+        NextPairs = [Pair | Pairs]
     ;
         (
             Soln = one_soln(FieldRvals),
@@ -564,47 +670,59 @@
                     | FieldInitializers],
             FirstSolnRowInitializer =
                 init_struct(FirstSolnStructType, FirstSolnFieldInitializers),
-            ml_construct_model_non_switch_vector(ModuleInfo,
-                CurIndex + 1, EndVal, NextLaterSolnRow, Pairs,
-                FirstSolnStructType, LaterSolnStructType, FieldTypes,
-                FirstSolnRowInitializersTail, LaterSolnRowInitializers,
-                !HadDummyRows),
-            FirstSolnRowInitializers =
-                [FirstSolnRowInitializer | FirstSolnRowInitializersTail]
+            !:RevFirstSolnRowInitializers =
+                [FirstSolnRowInitializer | !.RevFirstSolnRowInitializers]
         ;
             Soln = several_solns(FirstSolnRvals, LaterSolns),
             FieldInitializers = list.map(wrap_init_obj, FirstSolnRvals),
             list.length(LaterSolns, NumLaterSolns),
             NumLaterSolnsInitializer = gen_init_int(NumLaterSolns),
-            FirstLaterSlotInitializer = gen_init_int(NextLaterSolnRow),
+            FirstLaterSlotInitializer = gen_init_int(!.NextLaterSolnRow),
             FirstSolnFieldInitializers =
                 [NumLaterSolnsInitializer, FirstLaterSlotInitializer
                     | FieldInitializers],
-            HeadLaterSolnRowInitializers = list.map(
-                ml_construct_later_soln_row(LaterSolnStructType),
-                LaterSolns),
             FirstSolnRowInitializer =
                 init_struct(FirstSolnStructType, FirstSolnFieldInitializers),
-            ml_construct_model_non_switch_vector(ModuleInfo,
-                CurIndex + 1, EndVal, NextLaterSolnRow + NumLaterSolns, Pairs,
-                FirstSolnStructType, LaterSolnStructType, FieldTypes,
-                FirstSolnRowInitializersTail, LaterSolnRowInitializersTail,
-                !HadDummyRows),
-            FirstSolnRowInitializers =
-                [FirstSolnRowInitializer | FirstSolnRowInitializersTail],
-            LaterSolnRowInitializers =
-                HeadLaterSolnRowInitializers ++ LaterSolnRowInitializersTail
-        )
-    ).
+            !:RevFirstSolnRowInitializers =
+                [FirstSolnRowInitializer | !.RevFirstSolnRowInitializers],
 
-:- func ml_construct_later_soln_row(mlds_type, list(mlds_rval)) =
-    mlds_initializer.
+            LaterSolnRowInitializers = list.map(
+                ml_construct_later_soln_row(LaterSolnStructType),
+                LaterSolns),
+            !:LaterSolnRowInitializersCord = !.LaterSolnRowInitializersCord ++
+                from_list(LaterSolnRowInitializers),
+            !:NextLaterSolnRow = !.NextLaterSolnRow + NumLaterSolns
+        ),
+        NextPairs = Pairs
+    ),
+    ml_construct_model_non_switch_vector(ModuleInfo, CurIndex + 1, EndVal,
+        !.NextLaterSolnRow, NextPairs,
+        FirstSolnStructType, LaterSolnStructType, FieldTypes,
+        !RevFirstSolnRowInitializers, !LaterSolnRowInitializersCord,
+        !HadDummyRows).
 
 ml_construct_later_soln_row(StructType, Rvals) = RowInitializer :-
     FieldInitializers = list.map(wrap_init_obj, Rvals),
     RowInitializer = init_struct(StructType, FieldInitializers).
 
-:- func ml_default_value_for_type(mlds_type) = mlds_rval.
+%-----------------------------------------------------------------------------%
+
+:- pred make_dummy_first_soln_row(mlds_type::in, list(mlds_type)::in,
+    list(mlds_initializer)::in, list(mlds_initializer)::out) is det.
+
+make_dummy_first_soln_row(FirstSolnStructType, FieldTypes,
+        !RevFirstSolnRowInitializers) :-
+    FieldRvals = list.map(ml_default_value_for_type, FieldTypes),
+    FieldInitializers = list.map(wrap_init_obj, FieldRvals),
+    NumLaterSolnsInitializer = gen_init_int(-1),
+    FirstLaterSlotInitializer = gen_init_int(-1),
+    FirstSolnFieldInitializers =
+        [NumLaterSolnsInitializer, FirstLaterSlotInitializer
+            | FieldInitializers],
+    FirstSolnRowInitializer =
+        init_struct(FirstSolnStructType, FirstSolnFieldInitializers),
+    !:RevFirstSolnRowInitializers =
+        [FirstSolnRowInitializer | !.RevFirstSolnRowInitializers].
 
 ml_default_value_for_type(MLDS_Type) = DefaultRval :-
     (
@@ -644,61 +762,5 @@
     ).
 
 %-----------------------------------------------------------------------------%
-
-:- pred ml_generate_constants_for_lookup_switch(code_model::in,
-    list(prog_var)::in, set(prog_var)::in, list(tagged_case)::in,
-    map(int, soln_consts(mlds_rval))::in,
-    map(int, soln_consts(mlds_rval))::out,
-    ml_gen_info::in, ml_gen_info::out) is semidet.
-
-ml_generate_constants_for_lookup_switch(_CodeModel, _OutVars, _ArmNonLocals,
-        [], !IndexMap, !Info).
-ml_generate_constants_for_lookup_switch(CodeModel, OutVars, ArmNonLocals,
-        [TaggedCase | TaggedCases], !IndexMap, !Info) :-
-    TaggedCase = tagged_case(TaggedMainConsId, TaggedOtherConsIds, _, Goal),
-    Goal = hlds_goal(GoalExpr, _GoalInfo),
-    ( GoalExpr = disj(Disjuncts) ->
-        (
-            Disjuncts = []
-        ;
-            Disjuncts = [FirstDisjunct | LaterDisjuncts],
-            goal_is_conj_of_unify(ArmNonLocals, FirstDisjunct),
-            all_disjuncts_are_conj_of_unify(ArmNonLocals, LaterDisjuncts),
-            ml_generate_constants_for_arm(OutVars, FirstDisjunct, FirstSoln,
-                !Info),
-            ml_generate_constants_for_arms(OutVars, LaterDisjuncts, LaterSolns,
-                !Info),
-            SolnConsts = several_solns(FirstSoln, LaterSolns),
-            ml_record_lookup_for_tagged_cons_id(SolnConsts,
-                TaggedMainConsId, !IndexMap),
-            list.foldl(ml_record_lookup_for_tagged_cons_id(SolnConsts),
-                TaggedOtherConsIds, !IndexMap)
-        )
-    ;
-        goal_is_conj_of_unify(ArmNonLocals, Goal),
-        ml_generate_constants_for_arm(OutVars, Goal, Soln, !Info),
-        SolnConsts = one_soln(Soln),
-        ml_record_lookup_for_tagged_cons_id(SolnConsts,
-            TaggedMainConsId, !IndexMap),
-        list.foldl(ml_record_lookup_for_tagged_cons_id(SolnConsts),
-            TaggedOtherConsIds, !IndexMap)
-    ),
-    ml_generate_constants_for_lookup_switch(CodeModel, OutVars, ArmNonLocals,
-        TaggedCases, !IndexMap, !Info).
-
-:- pred ml_record_lookup_for_tagged_cons_id(soln_consts(mlds_rval)::in,
-    tagged_cons_id::in,
-    map(int, soln_consts(mlds_rval))::in,
-    map(int, soln_consts(mlds_rval))::out) is det.
-
-ml_record_lookup_for_tagged_cons_id(SolnConsts, TaggedConsId, !IndexMap) :-
-    TaggedConsId = tagged_cons_id(_ConsId, ConsTag),
-    ( ConsTag = int_tag(Index) ->
-        map.det_insert(Index, SolnConsts, !IndexMap)
-    ;
-        unexpected($module, $pred, "not int_tag")
-    ).
-
-%-----------------------------------------------------------------------------%
 :- end_module ml_backend.ml_lookup_switch.
 %-----------------------------------------------------------------------------%
Index: compiler/ml_string_switch.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/ml_string_switch.m,v
retrieving revision 1.54
diff -u -b -r1.54 ml_string_switch.m
--- compiler/ml_string_switch.m	2 Aug 2011 03:02:04 -0000	1.54
+++ compiler/ml_string_switch.m	9 Aug 2011 03:12:41 -0000
@@ -27,17 +27,30 @@
 :- import_module hlds.code_model.
 :- import_module hlds.hlds_goal.
 :- import_module ml_backend.ml_gen_info.
+:- import_module ml_backend.ml_lookup_switch.
 :- import_module ml_backend.mlds.
 :- import_module parse_tree.prog_data.
 
 :- import_module list.
 
-:- pred ml_generate_string_hash_switch(list(tagged_case)::in, prog_var::in,
+:- pred ml_generate_string_hash_jump_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_hash_lookup_switch(prog_var::in,
+    ml_lookup_switch_info(string)::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,
+:- pred ml_generate_string_binary_jump_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_lookup_switch(prog_var::in,
+    ml_lookup_switch_info(string)::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.
@@ -51,53 +64,32 @@
 :- import_module backend_libs.switch_util.
 :- import_module hlds.hlds_data.
 :- import_module hlds.hlds_module.
+:- import_module libs.globals.
 :- import_module ml_backend.ml_code_gen.
 :- import_module ml_backend.ml_code_util.
 :- import_module ml_backend.ml_global_data.
 :- import_module ml_backend.ml_simplify_switch.
+:- import_module ml_backend.ml_util.
 :- import_module parse_tree.builtin_lib_types.
 
 :- import_module assoc_list.
+:- import_module cord.
 :- import_module int.
 :- import_module map.
 :- import_module maybe.
 :- import_module pair.
 :- import_module require.
 :- import_module string.
-:- import_module term.
 :- import_module unit.
 
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
-ml_generate_string_hash_switch(Cases, Var, CodeModel, CanFail, Context,
+ml_generate_string_hash_jump_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),
-
-    % Generate the following local variable declarations:
-    %   int         slot_N;
-    %   MR_String   str_M;
-
-    ml_gen_info_new_aux_var_name("slot", SlotVar, !Info),
-    SlotVarType = mlds_native_int_type,
-    % We never need to trace ints.
-    SlotVarGCStatement = gc_no_stmt,
-    SlotVarDefn = ml_gen_mlds_var_decl(mlds_data_var(SlotVar), SlotVarType,
-        SlotVarGCStatement, MLDS_Context),
-    ml_gen_var_lval(!.Info, SlotVar, SlotVarType, SlotVarLval),
-    SlotVarRval = ml_lval(SlotVarLval),
-
-    ml_gen_info_new_aux_var_name("str", StringVar, !Info),
-    StringVarType = ml_string_type,
-    % 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),
-    ml_gen_var_lval(!.Info, StringVar, StringVarType, StringVarLval),
+    ml_gen_string_hash_switch_search_vars(Context, Var, HashSearchInfo, !Info),
+    HashSearchInfo = ml_hash_search_info(MLDS_Context, _VarRval,
+        SlotVarLval, _StringVarLval, Defns),
 
     ml_gen_new_label(EndLabel, !Info),
     GotoEndStatement =
@@ -108,7 +100,7 @@
 
     % Compute the hash table.
     construct_string_hash_cases(StrsCaseNums, allow_doubling,
-        TableSize, HashSlotsMap, HashOp, NumCollisions),
+        TableSize, HashSlotMap, HashOp, NumCollisions),
     HashMask = TableSize - 1,
 
     % Generate the code for when the hash lookup fails.
@@ -121,60 +113,55 @@
     ml_gen_info_get_target(!.Info, Target),
 
     MLDS_StringType = mercury_type_to_mlds_type(ModuleInfo, string_type),
-    MLDS_NextSlotType = mlds_native_int_type,
+    MLDS_IntType = mlds_native_int_type,
 
     ( NumCollisions = 0 ->
         MLDS_ArgTypes = [MLDS_StringType]
     ;
-        MLDS_ArgTypes = [MLDS_StringType, MLDS_NextSlotType]
+        MLDS_ArgTypes = [MLDS_StringType, MLDS_IntType]
     ),
 
     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),
-
+    ( NumCollisions = 0 ->
+        ( FieldIds = [StringFieldIdPrime] ->
+            StringFieldId = StringFieldIdPrime,
+            MaybeNextSlotFieldId = no
+        ;
+            unexpected($module, $pred, "bad FieldIds")
+        )
+    ;
     ( FieldIds = [StringFieldIdPrime, NextSlotFieldIdPrime] ->
         StringFieldId = StringFieldIdPrime,
         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,
-        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
-    % indication.
+    ml_gen_string_hash_jump_slots(0, TableSize, HashSlotMap, StructType,
+        MaybeNextSlotFieldId, [], RevRowInitializers, map.init, RevMap),
+    list.reverse(RevRowInitializers, RowInitializers),
+    % Generate the hash table.
     ml_gen_static_vector_defn(MLDS_ModuleName, StructTypeNum, RowInitializers,
         VectorCommon, GlobalData1, GlobalData),
     ml_gen_info_set_global_data(GlobalData, !Info),
 
     % Generate code which does the hash table lookup.
     map.to_assoc_list(RevMap, RevList),
-    generate_string_switch_arms(CodeMap, RevList, [], SlotsCases0),
+    generate_string_jump_switch_arms(CodeMap, RevList, [], SlotsCases0),
     list.sort(SlotsCases0, SlotsCases),
+    SlotVarType = mlds_native_int_type,
+
     SwitchStmt0 = ml_stmt_switch(SlotVarType, ml_lval(SlotVarLval),
         mlds_switch_range(0, TableSize - 1), SlotsCases,
         default_is_unreachable),
     ml_simplify_switch(SwitchStmt0, MLDS_Context, SwitchStatement, !Info),
 
-    FoundMatchCond =
-        ml_binop(logical_and,
-            ml_binop(ne,
-                ml_lval(StringVarLval),
-                ml_const(mlconst_null(StringVarType))),
-            ml_binop(str_eq,
-                ml_lval(StringVarLval),
-                VarRval)
-        ),
     FoundMatchComment = "we found a match; dispatch to the corresponding code",
-    FoundMatchCode = statement(
+    FoundMatchStatement = statement(
         ml_stmt_block([], [
             statement(ml_stmt_atomic(comment(FoundMatchComment)),
                 MLDS_Context),
@@ -183,84 +170,18 @@
         ]),
         MLDS_Context),
 
-    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(
-            ml_stmt_atomic(assign(StringVarLval,
-                ml_lval(ml_field(yes(0),
-                    ml_vector_common_row(VectorCommon, SlotVarRval),
-                    StringFieldId, MLDS_StringType, StructType)))),
-            MLDS_Context),
-        statement(ml_stmt_atomic(comment("did we find a match?")),
-            MLDS_Context),
-        statement(ml_stmt_if_then_else(FoundMatchCond, FoundMatchCode, no),
-            MLDS_Context)
-        ],
-    (
-        MaybeNextSlotFieldId = yes(NextSlotFieldId),
-        NoMatchStatements = [
-            statement(ml_stmt_atomic(comment(
-                "no match yet, so get next slot in hash chain")), MLDS_Context),
-            statement(
-                ml_stmt_atomic(assign(SlotVarLval,
-                    ml_lval(ml_field(yes(0),
-                        ml_vector_common_row(VectorCommon, SlotVarRval),
-                        NextSlotFieldId, MLDS_NextSlotType, StructType)))),
-                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(
-                    loop_at_least_once,
-                    ml_binop(int_ge,
-                        ml_lval(SlotVarLval),
-                        ml_const(mlconst_int(0))),
-                    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
-    ),
+    InitialComment = "hashed string jump switch",
+    ml_gen_string_hash_switch_search(InitialComment, HashSearchInfo, HashOp,
+        VectorCommon, StructType, StringFieldId, MaybeNextSlotFieldId,
+        HashMask, FoundMatchStatement, HashLookupStatements),
 
     EndLabelStatement = statement(ml_stmt_label(EndLabel), MLDS_Context),
     EndComment =
         statement(ml_stmt_atomic(comment("end of hashed string switch")),
             MLDS_Context),
 
-    % Collect all the generated variable declarations and code fragments
-    % together.
-    Defns = [SlotVarDefn, StringVarDefn],
-    Statements =
-        HashLookupStatements ++ FailStatements ++
+    % Collect all the generated code fragments together.
+    Statements = HashLookupStatements ++ FailStatements ++
         [EndLabelStatement, EndComment].
 
 %-----------------------------------------------------------------------------%
@@ -357,31 +278,33 @@
     %
 :- 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, maybe(mlds_field_id)::in,
-    list(mlds_initializer)::out,
+:- pred ml_gen_string_hash_jump_slots(int::in, int::in,
+    map(int, string_hash_slot(int))::in,
+    mlds_type::in, maybe(mlds_field_id)::in,
+    list(mlds_initializer)::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,
-        MaybeNextSlotId, RowInitializers, !RevMap) :-
+ml_gen_string_hash_jump_slots(Slot, TableSize, HashSlotMap, StructType,
+        MaybeNextSlotId, !RevRowInitializers, !RevMap) :-
     ( Slot = TableSize ->
-        RowInitializers = []
+        true
     ;
-        ml_gen_string_hash_slot(Slot, RowType, HashSlotMap,
-            MaybeNextSlotId, HeadRowInitializer, !RevMap),
-        ml_gen_string_hash_slots(Slot + 1, TableSize, RowType, HashSlotMap,
-            MaybeNextSlotId, TailRowInitializers, !RevMap),
-        RowInitializers = [HeadRowInitializer | TailRowInitializers]
+        ml_gen_string_hash_jump_slot(Slot, HashSlotMap,
+            StructType, MaybeNextSlotId, RowInitializer, !RevMap),
+        !:RevRowInitializers = [RowInitializer | !.RevRowInitializers],
+        ml_gen_string_hash_jump_slots(Slot + 1, TableSize, HashSlotMap,
+            StructType, MaybeNextSlotId, !RevRowInitializers, !RevMap)
     ).
 
-:- pred ml_gen_string_hash_slot(int::in, mlds_type::in,
-    map(int, string_hash_slot(int))::in, maybe(mlds_field_id)::in,
-    mlds_initializer::out,
+:- pred ml_gen_string_hash_jump_slot(int::in,
+    map(int, string_hash_slot(int))::in,
+    mlds_type::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,
+ml_gen_string_hash_jump_slot(Slot, HashSlotMap, StructType,
         MaybeNextSlotId, RowInitializer, !RevMap) :-
-    ( map.search(HashSlotMap, Slot, string_hash_slot(String, Next, CaseNum)) ->
+    ( map.search(HashSlotMap, Slot, HashSlotMapEntry) ->
+        HashSlotMapEntry = string_hash_slot(String, Next, CaseNum),
         StringRval = ml_const(mlconst_string(String)),
         NextSlotRval = ml_const(mlconst_int(Next)),
         ( map.search(!.RevMap, CaseNum, OldEntry) ->
@@ -406,12 +329,12 @@
             [init_obj(StringRval)])
     ).
 
-:- pred generate_string_switch_arms(map(int, statement)::in,
+:- pred generate_string_jump_switch_arms(map(int, statement)::in,
     assoc_list(int, hash_slots)::in,
     list(mlds_switch_case)::in, list(mlds_switch_case)::out) is det.
 
-generate_string_switch_arms(_, [], !Cases).
-generate_string_switch_arms(CodeMap, [Entry | Entries], !Cases) :-
+generate_string_jump_switch_arms(_, [], !Cases).
+generate_string_jump_switch_arms(CodeMap, [Entry | Entries], !Cases) :-
     Entry = CaseNum - HashSlots,
     HashSlots = hash_slots(FirstHashSlot, RevLaterHashSlots),
     list.reverse(RevLaterHashSlots, LaterHashSlots),
@@ -420,7 +343,7 @@
     map.lookup(CodeMap, CaseNum, CaseStatement),
     Case = mlds_switch_case(FirstMatchCond, LaterMatchConds, CaseStatement),
     !:Cases = [Case | !.Cases],
-    generate_string_switch_arms(CodeMap, Entries, !Cases).
+    generate_string_jump_switch_arms(CodeMap, Entries, !Cases).
 
 :- func make_hash_match(int) = mlds_case_match_cond.
 
@@ -429,16 +352,573 @@
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
-ml_generate_string_binary_switch(Cases, Var, CodeModel, CanFail, Context,
-        Defns, Statements, !Info) :-
+ml_generate_string_hash_lookup_switch(Var, LookupSwitchInfo, CodeModel,
+        CanFail, Context, Defns, Statements, !Info) :-
+    ml_gen_string_hash_switch_search_vars(Context, Var, HashSearchInfo, !Info),
+    Defns = HashSearchInfo ^ mhsi_defns,
+    MLDS_Context = HashSearchInfo ^ mhsi_mlds_context,
+
+    % Generate the code for when the lookup fails.
+    ml_gen_maybe_switch_failure(CodeModel, CanFail, Context, MLDS_Context,
+        FailStatements, !Info),
+
+    LookupSwitchInfo = ml_lookup_switch_info(CaseConsts, OutVars, OutTypes),
+    (
+        CaseConsts = all_one_soln(CaseValuePairs),
+        ml_generate_string_hash_simple_lookup_switch(CodeModel, CaseValuePairs,
+            OutVars, OutTypes, Context, HashSearchInfo,
+            FailStatements, Statements, !Info)
+    ;
+        CaseConsts = some_several_solns(CaseSolns, _Unit),
+        expect(unify(CodeModel, model_non), $module, $pred,
+            "CodeModel != model_non"),
+        ml_generate_string_hash_several_soln_lookup_switch(CaseSolns,
+            OutVars, OutTypes, Context, HashSearchInfo,
+            FailStatements, Statements, !Info)
+    ).
+
+%-----------------------------------------------------------------------------%
+
+:- pred ml_generate_string_hash_simple_lookup_switch(code_model::in,
+    assoc_list(string, list(mlds_rval))::in,
+    list(prog_var)::in, list(mlds_type)::in,
+    prog_context::in, ml_hash_search_info::in,
+    list(statement)::in, list(statement)::out,
+    ml_gen_info::in, ml_gen_info::out) is det.
+
+ml_generate_string_hash_simple_lookup_switch(CodeModel, CaseValuePairs,
+        OutVars, OutTypes, Context, HashSearchInfo,
+        FailStatements, Statements, !Info) :-
+    HashSearchInfo = ml_hash_search_info(MLDS_Context, _VarRval,
+        SlotVarLval, _StringVarLval, _Defns),
+    SlotVarRval = ml_lval(SlotVarLval),
+
+    ml_gen_new_label(EndLabel, !Info),
+    GotoEndStatement =
+        statement(ml_stmt_goto(goto_label(EndLabel)), MLDS_Context),
+
+    % Compute the hash table.
+    construct_string_hash_cases(CaseValuePairs, allow_doubling,
+        TableSize, HashSlotMap, HashOp, NumCollisions),
+    HashMask = TableSize - 1,
+
+    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_IntType = mlds_native_int_type,
+
+    ( NumCollisions = 0 ->
+        MLDS_ArgTypes = [MLDS_StringType | OutTypes]
+    ;
+        MLDS_ArgTypes = [MLDS_StringType, MLDS_IntType | OutTypes]
+    ),
+
+    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),
+    ( NumCollisions = 0 ->
+        ( FieldIds = [StringFieldIdPrime | OutFieldIdsPrime] ->
+            StringFieldId = StringFieldIdPrime,
+            OutFieldIds = OutFieldIdsPrime,
+            MaybeNextSlotFieldId = no
+        ;
+            unexpected($module, $pred, "bad FieldIds")
+        )
+    ;
+        (
+            FieldIds =
+                [StringFieldIdPrime, NextSlotFieldIdPrime | OutFieldIdsPrime]
+        ->
+            StringFieldId = StringFieldIdPrime,
+            OutFieldIds = OutFieldIdsPrime,
+            MaybeNextSlotFieldId = yes(NextSlotFieldIdPrime)
+        ;
+            unexpected($module, $pred, "bad FieldIds")
+        )
+    ),
+    % Generate the rows of the hash table.
+    DummyOutRvals = list.map(ml_default_value_for_type, OutTypes),
+    DummyOutInitializers = list.map(wrap_init_obj, DummyOutRvals),
+    ml_gen_string_hash_simple_lookup_slots(0, TableSize, StructType,
+        HashSlotMap, MaybeNextSlotFieldId, DummyOutInitializers,
+        [], RevRowInitializers),
+    list.reverse(RevRowInitializers, RowInitializers),
+    % Generate the hash table.
+    ml_gen_static_vector_defn(MLDS_ModuleName, StructTypeNum, RowInitializers,
+        VectorCommon, GlobalData1, GlobalData),
+    ml_gen_info_set_global_data(GlobalData, !Info),
+
+    ml_generate_field_assigns(OutVars, OutTypes, OutFieldIds, VectorCommon,
+        StructType, SlotVarRval, MLDS_Context, LookupStatements, !Info),
+
+    FoundMatchComment = "we found a match; look up the results",
+    FoundMatchCommentStatement = statement(
+        ml_stmt_atomic(comment(FoundMatchComment)), MLDS_Context),
+
+    (
+        CodeModel = model_det,
+        FoundMatchStatement = statement(
+            ml_stmt_block([],
+                [FoundMatchCommentStatement | LookupStatements] ++
+                [GotoEndStatement]
+            ),
+            MLDS_Context)
+    ;
+        CodeModel = model_semi,
+        ml_gen_set_success(!.Info, ml_const(mlconst_true), Context,
+            SetSuccessTrueStatement),
+        FoundMatchStatement = statement(
+            ml_stmt_block([],
+                [FoundMatchCommentStatement | LookupStatements] ++
+                [SetSuccessTrueStatement, GotoEndStatement]
+            ),
+            MLDS_Context)
+    ;
+        CodeModel = model_non,
+        unexpected($module, $pred, "model_non")
+    ),
+
+    InitialComment = "hashed string simple lookup switch",
+    ml_gen_string_hash_switch_search(InitialComment, HashSearchInfo, HashOp,
+        VectorCommon, StructType, StringFieldId, MaybeNextSlotFieldId,
+        HashMask, FoundMatchStatement, HashLookupStatements),
+
+    EndLabelStatement = statement(ml_stmt_label(EndLabel), MLDS_Context),
+    EndComment =
+        statement(ml_stmt_atomic(comment("end of hashed string switch")),
+            MLDS_Context),
+
+    % Collect all the generated code fragments together.
+    Statements = HashLookupStatements ++ FailStatements ++
+        [EndLabelStatement, EndComment].
+
+:- pred ml_gen_string_hash_simple_lookup_slots(int::in, int::in, mlds_type::in,
+    map(int, string_hash_slot(list(mlds_rval)))::in, maybe(mlds_field_id)::in,
+    list(mlds_initializer)::in,
+    list(mlds_initializer)::in, list(mlds_initializer)::out) is det.
+
+ml_gen_string_hash_simple_lookup_slots(Slot, TableSize, StructType,
+        HashSlotMap, MaybeNextSlotId, DummyOutInitializers,
+        !RevRowInitializers) :-
+    ( Slot = TableSize ->
+        true
+    ;
+        ml_gen_string_hash_simple_lookup_slot(Slot, StructType, HashSlotMap,
+            MaybeNextSlotId, DummyOutInitializers, RowInitializer),
+        !:RevRowInitializers = [RowInitializer | !.RevRowInitializers],
+        ml_gen_string_hash_simple_lookup_slots(Slot + 1, TableSize,
+            StructType, HashSlotMap, MaybeNextSlotId,
+            DummyOutInitializers, !RevRowInitializers)
+    ).
+
+:- pred ml_gen_string_hash_simple_lookup_slot(int::in, mlds_type::in,
+    map(int, string_hash_slot(list(mlds_rval)))::in,
+    maybe(mlds_field_id)::in,
+    list(mlds_initializer)::in, mlds_initializer::out) is det.
+
+ml_gen_string_hash_simple_lookup_slot(Slot, StructType, HashSlotMap,
+        MaybeNextSlotId, DummyOutInitializers, RowInitializer) :-
+    ( map.search(HashSlotMap, Slot, HashSlotMapEntry) ->
+        HashSlotMapEntry = string_hash_slot(String, Next, OutRvals),
+        StringRval = ml_const(mlconst_string(String)),
+        NextSlotRval = ml_const(mlconst_int(Next)),
+        OutInitializers = list.map(wrap_init_obj, OutRvals)
+    ;
+        StringRval = ml_const(mlconst_null(ml_string_type)),
+        NextSlotRval = ml_const(mlconst_int(-2)),
+        OutInitializers = DummyOutInitializers
+    ),
+    (
+        MaybeNextSlotId = yes(_),
+        RowInitializer = init_struct(StructType,
+            [init_obj(StringRval), init_obj(NextSlotRval) | OutInitializers])
+    ;
+        MaybeNextSlotId = no,
+        RowInitializer = init_struct(StructType,
+            [init_obj(StringRval) | OutInitializers])
+    ).
+
+%-----------------------------------------------------------------------------%
+
+:- pred ml_generate_string_hash_several_soln_lookup_switch(
+    assoc_list(string, soln_consts(mlds_rval))::in,
+    list(prog_var)::in, list(mlds_type)::in,
+    prog_context::in, ml_hash_search_info::in,
+    list(statement)::in, list(statement)::out,
+    ml_gen_info::in, ml_gen_info::out) is det.
+
+ml_generate_string_hash_several_soln_lookup_switch(CaseSolns,
+        OutVars, OutTypes, Context, HashSearchInfo,
+        FailStatements, Statements, !Info) :-
+    HashSearchInfo = ml_hash_search_info(MLDS_Context, _VarRval,
+        SlotVarLval, _StringVarLval, _Defns),
+    SlotVarRval = ml_lval(SlotVarLval),
+
+    make_several_soln_lookup_vars(MLDS_Context, SeveralSolnLookupVars, !Info),
+    SeveralSolnLookupVars = ml_several_soln_lookup_vars(NumLaterSolnsVarLval,
+        LaterSlotVarLval, LimitVarLval,
+        LimitAssignStatement, IncrLaterSlotVarStatement, Defns),
+    LaterSlotVarRval = ml_lval(LaterSlotVarLval),
+    LimitVarRval = ml_lval(LimitVarLval),
+
+    % Compute the hash table.
+    construct_string_hash_cases(CaseSolns, allow_doubling,
+        TableSize, HashSlotMap, HashOp, NumCollisions),
+    HashMask = TableSize - 1,
+
+    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_IntType = mlds_native_int_type,
+
+    ( NumCollisions = 0 ->
+        FirstSolnFieldTypes = [MLDS_StringType,
+            MLDS_IntType, MLDS_IntType | OutTypes]
+    ;
+        FirstSolnFieldTypes = [MLDS_StringType, MLDS_IntType,
+            MLDS_IntType, MLDS_IntType | OutTypes]
+    ),
+
+    ml_gen_info_get_global_data(!.Info, GlobalData0),
+    ml_gen_static_vector_type(MLDS_ModuleName, MLDS_Context, Target,
+        FirstSolnFieldTypes, FirstSolnStructTypeNum, FirstSolnStructType,
+        FirstSolnFieldIds, GlobalData0, GlobalData1),
+    ml_gen_static_vector_type(MLDS_ModuleName, MLDS_Context, Target,
+        OutTypes, LaterSolnStructTypeNum, LaterSolnStructType,
+        LaterSolnFieldIds, GlobalData1, GlobalData2),
+    ( NumCollisions = 0 ->
+        (
+            FirstSolnFieldIds = [StringFieldIdPrime,
+                NumLaterSolnsFieldIdPrime, FirstLaterSolnRowFieldIdPrime
+                | OutFieldIdsPrime]
+        ->
+            StringFieldId = StringFieldIdPrime,
+            NumLaterSolnsFieldId = NumLaterSolnsFieldIdPrime,
+            FirstLaterSolnRowFieldId = FirstLaterSolnRowFieldIdPrime,
+            OutFieldIds = OutFieldIdsPrime,
+            MaybeNextSlotFieldId = no
+        ;
+            unexpected($module, $pred, "bad FieldIds")
+        )
+    ;
+        (
+            FirstSolnFieldIds =
+                [StringFieldIdPrime, NextSlotFieldIdPrime,
+                NumLaterSolnsFieldIdPrime, FirstLaterSolnRowFieldIdPrime
+                | OutFieldIdsPrime]
+        ->
+            StringFieldId = StringFieldIdPrime,
+            NumLaterSolnsFieldId = NumLaterSolnsFieldIdPrime,
+            FirstLaterSolnRowFieldId = FirstLaterSolnRowFieldIdPrime,
+            OutFieldIds = OutFieldIdsPrime,
+            MaybeNextSlotFieldId = yes(NextSlotFieldIdPrime)
+        ;
+            unexpected($module, $pred, "bad FieldIds")
+        )
+    ),
+
+    % Generate the rows of the first soln hash table.
+    DummyOutRvals = list.map(ml_default_value_for_type, OutTypes),
+    DummyOutInitializers = list.map(wrap_init_obj, DummyOutRvals),
+    ml_gen_string_hash_several_soln_lookup_slots(0, TableSize, HashSlotMap,
+        FirstSolnStructType, LaterSolnStructType,
+        MaybeNextSlotFieldId, DummyOutInitializers,
+        [], RevFirstSolnRowInitializers,
+        cord.init, LaterSolnRowInitializersCord, 0),
+    list.reverse(RevFirstSolnRowInitializers, FirstSolnRowInitializers),
+    LaterSolnRowInitializers = cord.list(LaterSolnRowInitializersCord),
+    % Generate the hash table.
+    ml_gen_static_vector_defn(MLDS_ModuleName, FirstSolnStructTypeNum,
+        FirstSolnRowInitializers, FirstSolnVectorCommon,
+        GlobalData2, GlobalData3),
+    ml_gen_static_vector_defn(MLDS_ModuleName, LaterSolnStructTypeNum,
+        LaterSolnRowInitializers, LaterSolnVectorCommon,
+        GlobalData3, GlobalData),
+    ml_gen_info_set_global_data(GlobalData, !Info),
+
+    ml_generate_field_assign(NumLaterSolnsVarLval, MLDS_IntType,
+        NumLaterSolnsFieldId, FirstSolnVectorCommon, FirstSolnStructType,
+        SlotVarRval, MLDS_Context, NumLaterSolnsAssignStatement, !Info),
+    ml_generate_field_assign(LaterSlotVarLval, MLDS_IntType,
+        FirstLaterSolnRowFieldId, FirstSolnVectorCommon, FirstSolnStructType,
+        SlotVarRval, MLDS_Context, LaterSlotVarAssignStatement, !Info),
+    ml_generate_field_assigns(OutVars, OutTypes, OutFieldIds,
+        FirstSolnVectorCommon, FirstSolnStructType,
+        SlotVarRval, MLDS_Context, FirstSolnLookupStatements, !Info),
+    ml_generate_field_assigns(OutVars, OutTypes, LaterSolnFieldIds,
+        LaterSolnVectorCommon, LaterSolnStructType,
+        LaterSlotVarRval, MLDS_Context, LaterSolnLookupStatements, !Info),
+
+    ml_gen_call_current_success_cont(Context, CallContStatement, !Info),
+    FirstLookupSucceedStmt = ml_stmt_block([],
+        FirstSolnLookupStatements ++ [CallContStatement]),
+    FirstLookupSucceedStatement =
+        statement(FirstLookupSucceedStmt, MLDS_Context),
+
+    LaterLookupSucceedStmt = ml_stmt_block([],
+        LaterSolnLookupStatements ++
+        [CallContStatement, IncrLaterSlotVarStatement]),
+    LaterLookupSucceedStatement =
+        statement(LaterLookupSucceedStmt, MLDS_Context),
+
+    MoreSolnsLoopCond = ml_binop(int_lt, LaterSlotVarRval, LimitVarRval),
+    MoreSolnsLoopStmt = ml_stmt_while(may_loop_zero_times, MoreSolnsLoopCond,
+        LaterLookupSucceedStatement),
+    MoreSolnsLoopStatement = statement(MoreSolnsLoopStmt, MLDS_Context),
+
+    ml_gen_new_label(FailLabel, !Info),
+    GotoFailStatement =
+        statement(ml_stmt_goto(goto_label(FailLabel)), MLDS_Context),
+    SuccessStmt = ml_stmt_block(Defns, [
+        NumLaterSolnsAssignStatement, FirstLookupSucceedStatement,
+        LaterSlotVarAssignStatement, LimitAssignStatement,
+        MoreSolnsLoopStatement, GotoFailStatement
+    ]),
+    SuccessStatement = statement(SuccessStmt, MLDS_Context),
+
+    InitialComment = "hashed string several_soln lookup switch",
+    ml_gen_string_hash_switch_search(InitialComment, HashSearchInfo, HashOp,
+        FirstSolnVectorCommon, FirstSolnStructType, StringFieldId,
+        MaybeNextSlotFieldId, HashMask,
+        SuccessStatement, LookupStatements),
+    FailLabelStatement = statement(ml_stmt_label(FailLabel), MLDS_Context),
+    Statements = LookupStatements ++ [FailLabelStatement | FailStatements].
+
+:- pred ml_gen_string_hash_several_soln_lookup_slots(int::in, int::in,
+    map(int, string_hash_slot(soln_consts(mlds_rval)))::in,
+    mlds_type::in, mlds_type::in,
+    maybe(mlds_field_id)::in, list(mlds_initializer)::in,
+    list(mlds_initializer)::in, list(mlds_initializer)::out,
+    cord(mlds_initializer)::in, cord(mlds_initializer)::out, int::in) is det.
+
+ml_gen_string_hash_several_soln_lookup_slots(Slot, TableSize,
+        HashSlotMap, FirstSolnStructType, LaterSolnStructType,
+        MaybeNextSlotId, DummyOutInitializers,
+        !RevFirstSolnRowInitializers, !LaterSolnRowInitializersCord,
+        !.CurLaterSolnIndex) :-
+    ( Slot = TableSize ->
+        true
+    ;
+        ml_gen_string_hash_several_soln_lookup_slot(Slot, HashSlotMap,
+            FirstSolnStructType, LaterSolnStructType, MaybeNextSlotId,
+            DummyOutInitializers, FirstSolnsRowInitializer,
+            !LaterSolnRowInitializersCord, !CurLaterSolnIndex),
+        !:RevFirstSolnRowInitializers =
+            [FirstSolnsRowInitializer | !.RevFirstSolnRowInitializers],
+        ml_gen_string_hash_several_soln_lookup_slots(Slot + 1, TableSize,
+            HashSlotMap, FirstSolnStructType, LaterSolnStructType,
+            MaybeNextSlotId,
+            DummyOutInitializers, !RevFirstSolnRowInitializers,
+            !LaterSolnRowInitializersCord, !.CurLaterSolnIndex)
+    ).
+
+:- pred ml_gen_string_hash_several_soln_lookup_slot(int::in,
+    map(int, string_hash_slot(soln_consts(mlds_rval)))::in,
+    mlds_type::in, mlds_type::in, maybe(mlds_field_id)::in,
+    list(mlds_initializer)::in, mlds_initializer::out,
+    cord(mlds_initializer)::in, cord(mlds_initializer)::out,
+    int::in, int::out) is det.
+
+ml_gen_string_hash_several_soln_lookup_slot(Slot, HashSlotMap,
+        FirstSolnStructType, LaterSolnStructType, MaybeNextSlotId,
+        DummyOutInitializers, FirstSolnsRowInitializer,
+        !LaterSolnRowInitializersCord, !CurLaterSolnIndex) :-
+    ( map.search(HashSlotMap, Slot, HashSlotMapEntry) ->
+        HashSlotMapEntry = string_hash_slot(String, Next, Solns),
+        StringRval = ml_const(mlconst_string(String)),
+        NextSlotRval = ml_const(mlconst_int(Next)),
+        (
+            Solns = one_soln(FirstSolnRvals),
+            NumLaterSolnsRval = ml_const(mlconst_int(0)),
+            FirstLaterSlotRval = ml_const(mlconst_int(-1)),
+            FirstSolnOutInitializers = list.map(wrap_init_obj, FirstSolnRvals)
+        ;
+            Solns = several_solns(FirstSolnRvals, LaterSolns),
+            list.length(LaterSolns, NumLaterSolns),
+            NumLaterSolnsRval = ml_const(mlconst_int(NumLaterSolns)),
+            FirstLaterSlotRval = ml_const(mlconst_int(!.CurLaterSolnIndex)),
+            FirstSolnOutInitializers = list.map(wrap_init_obj, FirstSolnRvals),
+            LaterSolnRowInitializers = list.map(
+                ml_construct_later_soln_row(LaterSolnStructType),
+                LaterSolns),
+            !:LaterSolnRowInitializersCord = !.LaterSolnRowInitializersCord ++
+                from_list(LaterSolnRowInitializers),
+            !:CurLaterSolnIndex = !.CurLaterSolnIndex + NumLaterSolns
+        )
+    ;
+        StringRval = ml_const(mlconst_null(ml_string_type)),
+        NextSlotRval = ml_const(mlconst_int(-2)),
+        NumLaterSolnsRval = ml_const(mlconst_int(-1)),
+        FirstLaterSlotRval = ml_const(mlconst_int(-1)),
+        FirstSolnOutInitializers = DummyOutInitializers
+    ),
+    (
+        MaybeNextSlotId = yes(_),
+        FirstSolnsRowInitializer = init_struct(FirstSolnStructType,
+            [init_obj(StringRval), init_obj(NextSlotRval),
+            init_obj(NumLaterSolnsRval), init_obj(FirstLaterSlotRval)
+            | FirstSolnOutInitializers])
+    ;
+        MaybeNextSlotId = no,
+        FirstSolnsRowInitializer = init_struct(FirstSolnStructType,
+            [init_obj(StringRval),
+            init_obj(NumLaterSolnsRval), init_obj(FirstLaterSlotRval)
+            | FirstSolnOutInitializers])
+    ).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+%
+% Code useful for both jump and lookup hash string switches.
+%
+
+:- type ml_hash_search_info
+    --->    ml_hash_search_info(
+                mhsi_mlds_context               :: mlds_context,
+                mhsi_switch_var                 :: mlds_rval,
+                mhsi_slot_var                   :: mlds_lval,
+                mhsi_string_var                 :: mlds_lval,
+                mhsi_defns                      :: list(mlds_defn)
+            ).
+
+:- pred ml_gen_string_hash_switch_search_vars(prog_context::in, prog_var::in,
+    ml_hash_search_info::out, ml_gen_info::in, ml_gen_info::out) is det.
+
+ml_gen_string_hash_switch_search_vars(Context, Var, HashSearchInfo, !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 following local variable declarations:
+    %   int         slot;
+    %   MR_String   str;
 
-    % Generate the code for when the hash lookup fails.
+    ml_gen_info_new_aux_var_name("slot", SlotVar, !Info),
+    SlotVarType = mlds_native_int_type,
+    % We never need to trace ints.
+    SlotVarDefn = ml_gen_mlds_var_decl(mlds_data_var(SlotVar), SlotVarType,
+        gc_no_stmt, MLDS_Context),
+    ml_gen_var_lval(!.Info, SlotVar, SlotVarType, SlotVarLval),
+
+    ml_gen_info_new_aux_var_name("str", StringVar, !Info),
+    StringVarType = ml_string_type,
+    % 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.
+    StringVarDefn = ml_gen_mlds_var_decl(mlds_data_var(StringVar),
+        StringVarType, gc_no_stmt, MLDS_Context),
+    ml_gen_var_lval(!.Info, StringVar, StringVarType, StringVarLval),
+
+    Defns = [SlotVarDefn, StringVarDefn],
+    HashSearchInfo = ml_hash_search_info(MLDS_Context, VarRval,
+        SlotVarLval, StringVarLval, Defns).
+
+:- pred ml_gen_string_hash_switch_search(string::in, ml_hash_search_info::in,
+    unary_op::in, mlds_vector_common::in, mlds_type::in,
+    mlds_field_id::in, maybe(mlds_field_id)::in, int::in,
+    statement::in, list(statement)::out) is det.
+
+ml_gen_string_hash_switch_search(InitialComment, HashSearchInfo, HashOp,
+        VectorCommon, StructType, StringFieldId, MaybeNextSlotFieldId,
+        HashMask, FoundMatchStatement, HashLookupStatements) :-
+    HashSearchInfo = ml_hash_search_info(MLDS_Context, VarRval,
+        SlotVarLval, StringVarLval, _Defns),
+    SlotVarRval = ml_lval(SlotVarLval),
+    StringVarRval = ml_lval(StringVarLval),
+    SlotVarType = mlds_native_int_type,
+    StringVarType = ml_string_type,
+
+    PrepareForMatchStatements = [
+        statement(ml_stmt_atomic(comment(InitialComment)), 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)
+        ],
+    FoundMatchCond =
+        ml_binop(logical_and,
+            ml_binop(ne, StringVarRval,
+                ml_const(mlconst_null(StringVarType))),
+            ml_binop(str_eq, StringVarRval, VarRval)
+        ),
+    LookForMatchStatements = [
+        statement(ml_stmt_atomic(comment(
+            "lookup the string for this hash slot")), MLDS_Context),
+        statement(
+            ml_stmt_atomic(assign(StringVarLval,
+                ml_lval(ml_field(yes(0),
+                    ml_vector_common_row(VectorCommon, SlotVarRval),
+                    StringFieldId, StringVarType, StructType)))),
+            MLDS_Context),
+        statement(ml_stmt_atomic(comment("did we find a match?")),
+            MLDS_Context),
+        statement(ml_stmt_if_then_else(FoundMatchCond,
+            FoundMatchStatement, no),
+            MLDS_Context)
+    ],
+    (
+        MaybeNextSlotFieldId = yes(NextSlotFieldId),
+        NoMatchStatements = [
+            statement(ml_stmt_atomic(comment(
+                "no match yet, so get next slot in hash chain")),
+                MLDS_Context),
+            statement(
+                ml_stmt_atomic(assign(SlotVarLval,
+                    ml_lval(ml_field(yes(0),
+                        ml_vector_common_row(VectorCommon, SlotVarRval),
+                        NextSlotFieldId, SlotVarType, StructType)))),
+                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(loop_at_least_once,
+                    ml_binop(int_ge, SlotVarRval, ml_const(mlconst_int(0))),
+                    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
+    ).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+ml_generate_string_binary_jump_switch(Cases, Var, CodeModel, CanFail, Context,
+        Defns, Statements, !Info) :-
+    ml_gen_string_binary_switch_search_vars(Context, Var, BinarySearchInfo,
+        !Info),
+    BinarySearchInfo = ml_binary_search_info(MLDS_Context, _VarRval,
+        _LoVarLval, _HiVarLval, MidVarLval, _ResultVarLval, Defns),
+
+    % Generate the code for when the lookup fails.
     ml_gen_maybe_switch_failure(CodeModel, CanFail, Context, MLDS_Context,
         FailStatements, !Info),
 
@@ -500,13 +980,15 @@
             MLDS_Context),
 
     % Generate the code that searches the table.
-    ml_gen_string_binary_switch_search(MLDS_Context, VarRval,
-        LoVarLval, HiVarLval, MidVarLval, ResultVarLval, VectorCommon,
+    ml_gen_string_binary_switch_search(BinarySearchInfo, VectorCommon,
         TableSize, StructType, StringFieldId,
         SuccessStatement, LookupStatements, !.Info),
-    EndLabelStatement =
-        statement(ml_stmt_label(EndLabel), MLDS_Context),
-    Statements = LookupStatements ++ FailStatements ++ [EndLabelStatement].
+    InitialComment = "binary string jump switch",
+    CommentStatement = statement(ml_stmt_atomic(comment(InitialComment)),
+        MLDS_Context),
+    EndLabelStatement = statement(ml_stmt_label(EndLabel), MLDS_Context),
+    Statements = [CommentStatement | LookupStatements] ++
+        FailStatements ++ [EndLabelStatement].
 
 :- pred ml_gen_string_binary_jump_initializers(assoc_list(string, int)::in,
     mlds_type::in,
@@ -538,12 +1020,325 @@
     !: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_generate_string_binary_lookup_switch(Var, LookupSwitchInfo, CodeModel,
+        CanFail, Context, Defns, Statements, !Info) :-
+    ml_gen_string_binary_switch_search_vars(Context, Var, BinarySearchInfo,
+        !Info),
+    Defns = BinarySearchInfo ^ mbsi_defns,
+    MLDS_Context = BinarySearchInfo ^ mbsi_mlds_context,
+
+    % Generate the code for when the lookup fails.
+    ml_gen_maybe_switch_failure(CodeModel, CanFail, Context, MLDS_Context,
+        FailStatements, !Info),
+
+    LookupSwitchInfo = ml_lookup_switch_info(CaseConsts, OutVars, OutTypes),
+    (
+        CaseConsts = all_one_soln(CaseValuePairs),
+        ml_generate_string_binary_simple_lookup_switch(CodeModel,
+            CaseValuePairs, OutVars, OutTypes, Context,
+            BinarySearchInfo, FailStatements, Statements, !Info)
+    ;
+        CaseConsts = some_several_solns(CaseSolns, _Unit),
+        expect(unify(CodeModel, model_non), $module, $pred,
+            "CodeModel != model_non"),
+        ml_generate_string_binary_several_soln_lookup_switch(CaseSolns,
+            OutVars, OutTypes, Context, BinarySearchInfo,
+            FailStatements, Statements, !Info)
+    ).
+
+%-----------------------------------------------------------------------------%
+
+:- pred ml_generate_string_binary_simple_lookup_switch(code_model::in,
+    assoc_list(string, list(mlds_rval))::in,
+    list(prog_var)::in, list(mlds_type)::in,
+    prog_context::in, ml_binary_search_info::in,
+    list(statement)::in, list(statement)::out,
+    ml_gen_info::in, ml_gen_info::out) is det.
+
+ml_generate_string_binary_simple_lookup_switch(CodeModel, CaseValuePairs0,
+        OutVars, OutTypes, Context, BinarySearchInfo,
+        FailStatements, Statements, !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_Context = BinarySearchInfo ^ mbsi_mlds_context,
+
+    MLDS_StringType = mercury_type_to_mlds_type(ModuleInfo, string_type),
+    MLDS_ArgTypes = [MLDS_StringType | OutTypes],
+
+    % Generate the binary search table.
+    list.sort(CaseValuePairs0, CaseValuePairs),
+    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),
+    ( FieldIds = [StringFieldIdPrime | OutFieldIdsPrime] ->
+        StringFieldId = StringFieldIdPrime,
+        OutFieldIds = OutFieldIdsPrime
+    ;
+        unexpected($module, $pred, "bad FieldIds")
+    ),
+    ml_gen_string_binary_simple_lookup_initializers(CaseValuePairs, StructType,
+        [], RevRowInitializers, 0, TableSize),
+    list.reverse(RevRowInitializers, RowInitializers),
+    ml_gen_static_vector_defn(MLDS_ModuleName, StructTypeNum, RowInitializers,
+        VectorCommon, GlobalData1, GlobalData),
+    ml_gen_info_set_global_data(GlobalData, !Info),
+
+    MidVarLval = BinarySearchInfo ^ mbsi_mid_var,
+    ml_generate_field_assigns(OutVars, OutTypes, OutFieldIds,
+        VectorCommon, StructType, ml_lval(MidVarLval), MLDS_Context,
+        GetArgStatements, !Info),
+
+    ml_gen_new_label(EndLabel, !Info),
+    GotoEndStatement =
+        statement(ml_stmt_goto(goto_label(EndLabel)), MLDS_Context),
+    (
+        CodeModel = model_det,
+        SuccessStatement = statement(
+            ml_stmt_block([], GetArgStatements ++ [GotoEndStatement]),
+            MLDS_Context)
+    ;
+        CodeModel = model_semi,
+        ml_gen_set_success(!.Info, ml_const(mlconst_true), Context,
+            SetSuccessTrueStatement),
+        SuccessStatement = statement(
+            ml_stmt_block([],
+                GetArgStatements ++
+                [SetSuccessTrueStatement, GotoEndStatement]),
+            MLDS_Context)
+    ;
+        CodeModel = model_non,
+        unexpected($module, $pred, "model_non")
+    ),
+
+    % Generate the code that searches the table.
+    ml_gen_string_binary_switch_search(BinarySearchInfo, VectorCommon,
+        TableSize, StructType, StringFieldId,
+        SuccessStatement, LookupStatements, !.Info),
+    InitialComment = "binary string simple lookup switch",
+    CommentStatement = statement(ml_stmt_atomic(comment(InitialComment)),
+        MLDS_Context),
+    EndLabelStatement = statement(ml_stmt_label(EndLabel), MLDS_Context),
+    Statements = [CommentStatement | LookupStatements] ++
+        FailStatements ++ [EndLabelStatement].
+
+:- pred ml_gen_string_binary_simple_lookup_initializers(
+    assoc_list(string, list(mlds_rval))::in, mlds_type::in,
+    list(mlds_initializer)::in, list(mlds_initializer)::out,
+    int::in, int::out) is det.
+
+ml_gen_string_binary_simple_lookup_initializers([],
+        _StructType, !RevRowInitializers, !CurIndex).
+ml_gen_string_binary_simple_lookup_initializers([Str - Rvals | StrRvals],
+        StructType, !RevRowInitializers, !CurIndex) :-
+    StrRval = ml_const(mlconst_string(Str)),
+    RowInitializer = init_struct(StructType,
+        [init_obj(StrRval) | list.map(wrap_init_obj, Rvals)]),
+    !:RevRowInitializers = [RowInitializer | !.RevRowInitializers],
+    !:CurIndex = !.CurIndex + 1,
+    ml_gen_string_binary_simple_lookup_initializers(StrRvals,
+        StructType, !RevRowInitializers, !CurIndex).
+
+%-----------------------------------------------------------------------------%
+
+:- pred ml_generate_string_binary_several_soln_lookup_switch(
+    assoc_list(string, soln_consts(mlds_rval))::in,
+    list(prog_var)::in, list(mlds_type)::in,
+    prog_context::in, ml_binary_search_info::in,
+    list(statement)::in, list(statement)::out,
+    ml_gen_info::in, ml_gen_info::out) is det.
+
+ml_generate_string_binary_several_soln_lookup_switch(CaseSolns0,
+        OutVars, OutTypes, Context, BinarySearchInfo,
+        FailStatements, Statements, !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_Context = BinarySearchInfo ^ mbsi_mlds_context,
+
+    make_several_soln_lookup_vars(MLDS_Context, SeveralSolnLookupVars, !Info),
+    SeveralSolnLookupVars = ml_several_soln_lookup_vars(NumLaterSolnsVarLval,
+        LaterSlotVarLval, LimitVarLval,
+        LimitAssignStatement, IncrLaterSlotVarStatement, Defns),
+    LaterSlotVarRval = ml_lval(LaterSlotVarLval),
+    LimitVarRval = ml_lval(LimitVarLval),
+
+    MLDS_StringType = mercury_type_to_mlds_type(ModuleInfo, string_type),
+    MLDS_IntType = mlds_native_int_type,
+    FirstSolnFieldTypes =
+        [MLDS_StringType, MLDS_IntType, MLDS_IntType | OutTypes],
+    LaterSolnFieldTypes = OutTypes,
+
+    % Generate the binary search table.
+    list.sort(CaseSolns0, CaseSolns),
+    ml_gen_info_get_global_data(!.Info, GlobalData0),
+    ml_gen_static_vector_type(MLDS_ModuleName, MLDS_Context, Target,
+        FirstSolnFieldTypes, FirstSolnStructTypeNum, FirstSolnStructType,
+        FirstSolnFieldIds, GlobalData0, GlobalData1),
+    ml_gen_static_vector_type(MLDS_ModuleName, MLDS_Context, Target,
+        LaterSolnFieldTypes, LaterSolnStructTypeNum, LaterSolnStructType,
+        LaterSolnFieldIds, GlobalData1, GlobalData2),
+    (
+        FirstSolnFieldIds = [StringFieldIdPrime, NumLaterSolnsFieldIdPrime,
+            FirstLaterRowFieldIdPrime | FirstSolnArgIdsPrime]
+    ->
+        StringFieldId = StringFieldIdPrime,
+        NumLaterSolnsFieldId = NumLaterSolnsFieldIdPrime,
+        FirstLaterRowFieldId = FirstLaterRowFieldIdPrime,
+        FirstSolnArgIds = FirstSolnArgIdsPrime
+    ;
+        unexpected($module, $pred, "bad FieldIds")
+    ),
+    ml_gen_string_binary_several_lookup_initializers(CaseSolns,
+        FirstSolnStructType, LaterSolnStructType,
+        [], RevFirstSolnRowInitializers,
+        cord.init, LaterSolnRowInitializersCord,
+        0, FirstSolnTableSize, 0),
+    list.reverse(RevFirstSolnRowInitializers, FirstSolnRowInitializers),
+    LaterSolnRowInitializers = cord.list(LaterSolnRowInitializersCord),
+    ml_gen_static_vector_defn(MLDS_ModuleName, FirstSolnStructTypeNum,
+        FirstSolnRowInitializers, FirstSolnVectorCommon,
+        GlobalData2, GlobalData3),
+    ml_gen_static_vector_defn(MLDS_ModuleName, LaterSolnStructTypeNum,
+        LaterSolnRowInitializers, LaterSolnVectorCommon,
+        GlobalData3, GlobalData),
+    ml_gen_info_set_global_data(GlobalData, !Info),
+
+    MidVarLval = BinarySearchInfo ^ mbsi_mid_var,
+    MidVarRval = ml_lval(MidVarLval),
+    ml_generate_field_assign(NumLaterSolnsVarLval, MLDS_IntType,
+        NumLaterSolnsFieldId,
+        FirstSolnVectorCommon, FirstSolnStructType, MidVarRval,
+        MLDS_Context, NumLaterSolnsAssignStatement, !Info),
+    ml_generate_field_assign(LaterSlotVarLval, MLDS_IntType,
+        FirstLaterRowFieldId,
+        FirstSolnVectorCommon, FirstSolnStructType, MidVarRval,
+        MLDS_Context, LaterSlotVarAssignStatement, !Info),
+    ml_generate_field_assigns(OutVars, OutTypes, FirstSolnArgIds,
+        FirstSolnVectorCommon, FirstSolnStructType, MidVarRval,
+        MLDS_Context, FirstSolnLookupStatements, !Info),
+    ml_generate_field_assigns(OutVars, OutTypes, LaterSolnFieldIds,
+        LaterSolnVectorCommon, LaterSolnStructType, LaterSlotVarRval,
+        MLDS_Context, LaterSolnLookupStatements, !Info),
+
+    ml_gen_call_current_success_cont(Context, CallContStatement, !Info),
+    FirstLookupSucceedStmt = ml_stmt_block([],
+        FirstSolnLookupStatements ++ [CallContStatement]),
+    FirstLookupSucceedStatement =
+        statement(FirstLookupSucceedStmt, MLDS_Context),
+
+    LaterLookupSucceedStmt = ml_stmt_block([],
+        LaterSolnLookupStatements ++
+        [CallContStatement, IncrLaterSlotVarStatement]),
+    LaterLookupSucceedStatement =
+        statement(LaterLookupSucceedStmt, MLDS_Context),
+
+    MoreSolnsLoopCond = ml_binop(int_lt, LaterSlotVarRval, LimitVarRval),
+    MoreSolnsLoopStmt = ml_stmt_while(may_loop_zero_times, MoreSolnsLoopCond,
+        LaterLookupSucceedStatement),
+    MoreSolnsLoopStatement = statement(MoreSolnsLoopStmt, MLDS_Context),
+
+    ml_gen_new_label(FailLabel, !Info),
+    GotoFailStatement =
+        statement(ml_stmt_goto(goto_label(FailLabel)), MLDS_Context),
+    SuccessStmt = ml_stmt_block(Defns, [
+        NumLaterSolnsAssignStatement, FirstLookupSucceedStatement,
+        LaterSlotVarAssignStatement, LimitAssignStatement,
+        MoreSolnsLoopStatement, GotoFailStatement
+    ]),
+    SuccessStatement = statement(SuccessStmt, MLDS_Context),
+
+    % Generate the code that searches the table.
+    ml_gen_string_binary_switch_search(BinarySearchInfo, FirstSolnVectorCommon,
+        FirstSolnTableSize, FirstSolnStructType, StringFieldId,
+        SuccessStatement, LookupStatements, !.Info),
+    InitialComment = "binary string several soln lookup switch",
+    CommentStatement = statement(ml_stmt_atomic(comment(InitialComment)),
+        MLDS_Context),
+    FailLabelStatement = statement(ml_stmt_label(FailLabel), MLDS_Context),
+    Statements = [CommentStatement | LookupStatements] ++
+        [FailLabelStatement | FailStatements].
+
+:- pred ml_gen_string_binary_several_lookup_initializers(
+    assoc_list(string, soln_consts(mlds_rval))::in,
+    mlds_type::in, mlds_type::in,
+    list(mlds_initializer)::in, list(mlds_initializer)::out,
+    cord(mlds_initializer)::in, cord(mlds_initializer)::out,
+    int::in, int::out, int::in) is det.
+
+ml_gen_string_binary_several_lookup_initializers([],
+        _FirstSolnStructType, _LaterSolnStructType,
+        !RevFirstSolnRowInitializers, !LaterSolnRowInitializersCord,
+        !CurFirstSolnIndex, _CurLaterSolnIndex).
+ml_gen_string_binary_several_lookup_initializers([Str - Solns | StrSolns],
+        FirstSolnStructType, LaterSolnStructType,
+        !RevFirstSolnRowInitializers, !LaterSolnRowInitializersCord,
+        !CurFirstSolnIndex, !.CurLaterSolnIndex) :-
+    StrRval = ml_const(mlconst_string(Str)),
+    (
+        Solns = one_soln(FirstSolnRvals),
+        NumLaterSolnsInitializer = gen_init_int(0),
+        FirstLaterSlotInitializer = gen_init_int(-1),
+        FirstSolnRowInitializer = init_struct(FirstSolnStructType,
+            [init_obj(StrRval),
+                NumLaterSolnsInitializer, FirstLaterSlotInitializer
+                | list.map(wrap_init_obj, FirstSolnRvals)])
+    ;
+        Solns = several_solns(FirstSolnRvals, LaterSolns),
+        list.length(LaterSolns, NumLaterSolns),
+        NumLaterSolnsInitializer = gen_init_int(NumLaterSolns),
+        FirstLaterSlotInitializer = gen_init_int(!.CurLaterSolnIndex),
+        FirstSolnRowInitializer = init_struct(FirstSolnStructType,
+            [init_obj(StrRval),
+                NumLaterSolnsInitializer, FirstLaterSlotInitializer
+                | list.map(wrap_init_obj, FirstSolnRvals)]),
+        LaterSolnRowInitializers = list.map(
+            ml_construct_later_soln_row(LaterSolnStructType),
+            LaterSolns),
+        !:LaterSolnRowInitializersCord = !.LaterSolnRowInitializersCord ++
+            from_list(LaterSolnRowInitializers),
+        !:CurLaterSolnIndex = !.CurLaterSolnIndex + NumLaterSolns
+    ),
+    !:RevFirstSolnRowInitializers =
+        [FirstSolnRowInitializer | !.RevFirstSolnRowInitializers],
+    !:CurFirstSolnIndex = !.CurFirstSolnIndex + 1,
+    ml_gen_string_binary_several_lookup_initializers(StrSolns,
+        FirstSolnStructType, LaterSolnStructType,
+        !RevFirstSolnRowInitializers, !LaterSolnRowInitializersCord,
+        !CurFirstSolnIndex, !.CurLaterSolnIndex).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+%
+% Code useful for both jump and lookup binary string switches.
+%
+
+:- type ml_binary_search_info
+    --->    ml_binary_search_info(
+                mbsi_mlds_context           :: mlds_context,
+                mbsi_switch_var             :: mlds_rval,
+                mbsi_lo_var                 :: mlds_lval,
+                mbsi_hi_var                 :: mlds_lval,
+                mbsi_mid_var                :: mlds_lval,
+                mbsi_result_var             :: mlds_lval,
+                mbsi_defns                  :: list(mlds_defn)
+            ).
+
+:- pred ml_gen_string_binary_switch_search_vars(prog_context::in, prog_var::in,
+    ml_binary_search_info::out, ml_gen_info::in, ml_gen_info::out) is det.
+
+ml_gen_string_binary_switch_search_vars(Context, Var, BinarySearchInfo,
+        !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 following local variable declarations:
     %   int         lo;
     %   int         hi;
@@ -576,17 +1371,19 @@
         ResultGCStatement, MLDS_Context),
     ml_gen_var_lval(!.Info, ResultVar, ResultType, ResultVarLval),
 
-    Defns = [LoVarDefn, HiVarDefn, MidVarDefn, ResultVarDefn].
+    Defns = [LoVarDefn, HiVarDefn, MidVarDefn, ResultVarDefn],
+    BinarySearchInfo = ml_binary_search_info(MLDS_Context, VarRval,
+        LoVarLval, HiVarLval, MidVarLval, ResultVarLval, Defns).
 
-:- 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,
+:- pred ml_gen_string_binary_switch_search(ml_binary_search_info::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.
+    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_string_binary_switch_search(BinarySearchInfo,
+        VectorCommon, TableSize, StructType, StringFieldId,
+        SuccessStatement, Statements, Info) :-
+    BinarySearchInfo = ml_binary_search_info(MLDS_Context, VarRval,
+        LoVarLval, HiVarLval, MidVarLval, ResultVarLval, _Defns),
     ml_gen_info_get_module_info(Info, ModuleInfo),
     MLDS_StringType = mercury_type_to_mlds_type(ModuleInfo, string_type),
 
@@ -613,7 +1410,7 @@
             SuccessStatement,
             yes(statement(
                 ml_stmt_if_then_else(
-                    ml_binop(int_le,
+                    ml_binop(int_lt,
                         ml_lval(ResultVarLval),
                         ml_const(mlconst_int(0))),
                     statement(ml_stmt_atomic(
@@ -649,9 +1446,12 @@
 
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
+%
+% Code useful for all kinds of string switches.
+%
 
 :- pred ml_gen_maybe_switch_failure(code_model::in, can_fail::in,
-    term.context::in, mlds_context::in, list(statement)::out,
+    prog_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, 
Index: compiler/ml_switch_gen.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/ml_switch_gen.m,v
retrieving revision 1.58
diff -u -b -r1.58 ml_switch_gen.m
--- compiler/ml_switch_gen.m	3 Aug 2011 01:20:12 -0000	1.58
+++ compiler/ml_switch_gen.m	8 Aug 2011 13:48:06 -0000
@@ -219,10 +219,13 @@
                     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)
+                ml_is_lookup_switch(get_int_tag, SwitchVar,
+                    FilteredTaggedCases, NonLocals, CodeModel,
+                    LookupSwitchInfo, !Info)
             ->
+                ml_gen_lookup_switch(SwitchVar, LookupSwitchInfo,
+                    CodeModel, Context, FirstVal, LastVal,
+                    NeedBitVecCheck, NeedRangeCheck, LookupStatement, !Info),
                 Statements = [LookupStatement]
             ;
                 target_supports_int_switch(Globals)
@@ -272,9 +275,23 @@
                     % switches for the Java back-end too.
                     target_supports_goto(Globals)
                 ->
-                    ml_generate_string_hash_switch(FilteredTaggedCases,
-                        SwitchVar, CodeModel, FilteredCanFail, Context,
-                        Decls, Statements, !Info)
+                    (
+                        ml_gen_info_get_high_level_data(!.Info, no),
+                        globals.lookup_bool_option(Globals,
+                            static_ground_cells, yes),
+                        NonLocals = goal_info_get_nonlocals(GoalInfo),
+                        ml_is_lookup_switch(get_string_tag, SwitchVar,
+                            FilteredTaggedCases, NonLocals, CodeModel,
+                            LookupSwitchInfo, !Info)
+                    ->
+                        ml_generate_string_hash_lookup_switch(SwitchVar,
+                            LookupSwitchInfo, CodeModel, FilteredCanFail,
+                            Context, Decls, Statements, !Info)
+                    ;
+                        ml_generate_string_hash_jump_switch(
+                            FilteredTaggedCases, SwitchVar, CodeModel,
+                            FilteredCanFail, Context, Decls, Statements, !Info)
+                    )
                 ;
                     NumConsIds >= StringBinarySwitchSize,
                     % We can implement string binary switches using either
@@ -289,9 +306,23 @@
                     % switches for the Java back-end too.
                     target_supports_goto(Globals)
                 ->
-                    ml_generate_string_binary_switch(FilteredTaggedCases,
-                        SwitchVar, CodeModel, FilteredCanFail, Context,
-                        Decls, Statements, !Info)
+                    (
+                        ml_gen_info_get_high_level_data(!.Info, no),
+                        globals.lookup_bool_option(Globals,
+                            static_ground_cells, yes),
+                        NonLocals = goal_info_get_nonlocals(GoalInfo),
+                        ml_is_lookup_switch(get_string_tag, SwitchVar,
+                            FilteredTaggedCases, NonLocals, CodeModel,
+                            LookupSwitchInfo, !Info)
+                    ->
+                        ml_generate_string_binary_lookup_switch(SwitchVar,
+                            LookupSwitchInfo, CodeModel, FilteredCanFail,
+                            Context, Decls, Statements, !Info)
+                    ;
+                        ml_generate_string_binary_jump_switch(
+                            FilteredTaggedCases, SwitchVar, CodeModel,
+                            FilteredCanFail, Context, Decls, Statements, !Info)
+                    )
                 ;
                     ml_switch_generate_if_then_else_chain(FilteredTaggedCases,
                         SwitchVar, CodeModel, FilteredCanFail, Context,
Index: compiler/string_switch.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/string_switch.m,v
retrieving revision 1.76
diff -u -b -r1.76 string_switch.m
--- compiler/string_switch.m	2 Aug 2011 03:02:05 -0000	1.76
+++ compiler/string_switch.m	5 Aug 2011 03:12:51 -0000
@@ -230,8 +230,8 @@
             OutVars, OutTypes, Liveness, CanFail, EndLabel, StoreMap,
             !MaybeEnd, Code, !CI)
     ;
-        CaseConsts = some_several_solns(CaseSolns, ResumeVars,
-            GoalsMayModifyTrail),
+        CaseConsts = some_several_solns(CaseSolns,
+            case_consts_several_llds(ResumeVars, GoalsMayModifyTrail)),
         generate_string_hash_several_soln_lookup_switch(VarRval, CaseSolns,
             ResumeVars, GoalsMayModifyTrail, OutVars, OutTypes, Liveness,
             CanFail, EndLabel, StoreMap, !MaybeEnd, Code, !CI)
@@ -770,8 +770,8 @@
             OutVars, OutTypes, Liveness, CanFail, EndLabel, StoreMap,
             !MaybeEnd, Code, !CI)
     ;
-        CaseConsts = some_several_solns(CaseSolns, ResumeVars,
-            GoalsMayModifyTrail),
+        CaseConsts = some_several_solns(CaseSolns,
+            case_consts_several_llds(ResumeVars, GoalsMayModifyTrail)),
         generate_string_binary_several_soln_lookup_switch(VarRval, CaseSolns,
             ResumeVars, GoalsMayModifyTrail, OutVars, OutTypes, Liveness,
             CanFail, EndLabel, StoreMap, !MaybeEnd, Code, !CI)
Index: compiler/switch_gen.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/switch_gen.m,v
retrieving revision 1.120
diff -u -b -r1.120 switch_gen.m
--- compiler/switch_gen.m	2 Aug 2011 03:02:05 -0000	1.120
+++ compiler/switch_gen.m	5 Aug 2011 03:12:51 -0000
@@ -188,9 +188,8 @@
                     FilteredCanFail, LowerLimit, UpperLimit, NumValues,
                     ReqDensity, NeedBitVecCheck, NeedRangeCheck,
                     FirstVal, LastVal),
-                is_lookup_switch(record_lookup_for_tagged_cons_id_int,
-                    FilteredTaggedCases, GoalInfo, StoreMap,
-                    no, MaybeEnd1, LookupSwitchInfo, !CI)
+                is_lookup_switch(get_int_tag, FilteredTaggedCases, GoalInfo,
+                    StoreMap, no, MaybeEnd1, LookupSwitchInfo, !CI)
             ->
                 % We update MaybeEnd1 to MaybeEnd to account for the possible
                 % reservation of temp slots for nondet switches.
@@ -232,10 +231,9 @@
                     StringBinarySwitchSize),
                 ( NumConsIds >= StringHashSwitchSize ->
                     (
-                        is_lookup_switch(
-                            record_lookup_for_tagged_cons_id_string,
-                            FilteredTaggedCases, GoalInfo, StoreMap,
-                            no, MaybeEnd1, LookupSwitchInfo, !CI)
+                        is_lookup_switch(get_string_tag, FilteredTaggedCases,
+                            GoalInfo, StoreMap, no, MaybeEnd1,
+                            LookupSwitchInfo, !CI)
                     ->
                         % We update MaybeEnd1 to MaybeEnd to account for the
                         % possible reservation of temp slots for nondet
@@ -250,10 +248,9 @@
                     )
                 ; NumConsIds >= StringBinarySwitchSize ->
                     (
-                        is_lookup_switch(
-                            record_lookup_for_tagged_cons_id_string,
-                            FilteredTaggedCases, GoalInfo, StoreMap,
-                            no, MaybeEnd1, LookupSwitchInfo, !CI)
+                        is_lookup_switch(get_string_tag, FilteredTaggedCases,
+                            GoalInfo, StoreMap, no, MaybeEnd1,
+                            LookupSwitchInfo, !CI)
                     ->
                         % We update MaybeEnd1 to MaybeEnd to account for the
                         % possible reservation of temp slots for nondet
Index: compiler/switch_util.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/switch_util.m,v
retrieving revision 1.59
diff -u -b -r1.59 switch_util.m
--- compiler/switch_util.m	2 Aug 2011 00:05:40 -0000	1.59
+++ compiler/switch_util.m	5 Aug 2011 03:12:51 -0000
@@ -115,12 +115,17 @@
 % Stuff for lookup switches.
 %
 
-:- type case_consts(Key, Rval)
+:- type case_consts(Key, Rval, SeveralInfo)
     --->    all_one_soln(
                 assoc_list(Key, list(Rval))
             )
     ;       some_several_solns(
                 assoc_list(Key, soln_consts(Rval)),
+                SeveralInfo
+            ).
+
+:- type case_consts_several_llds
+    --->    case_consts_several_llds(
                 % The resume vars.
                 set_of_progvar,
 
@@ -204,8 +209,9 @@
 % Stuff for string binary switches.
 %
 
-    % For a string switch, compute the hash value for each case in the list
-    % of cases, and store the cases in a map from hash values to cases.
+    % Given a list of cases, represent each case using the supplied predicate,
+    % map each string to the representation of its corresponding case,
+    % and return a sorted assoc_list version of that map.
     %
 :- pred string_binary_cases(list(tagged_case)::in,
     pred(tagged_case, CaseRep, StateA, StateA, StateB, StateB, StateC, StateC)
@@ -337,6 +343,18 @@
 
 %-----------------------------------------------------------------------------%
 
+    % If the cons_tag specifies an int_tag, return the int;
+    % otherwise abort.
+    %
+:- pred get_int_tag(cons_tag::in, int::out) is det.
+
+    % If the cons_tag specifies a string_tag, return the string;
+    % otherwise abort.
+    %
+:- pred get_string_tag(cons_tag::in, string::out) is det.
+
+%-----------------------------------------------------------------------------%
+
 :- implementation.
 
 :- import_module check_hlds.
@@ -1363,5 +1381,22 @@
     ).
 
 %-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+get_int_tag(ConsTag, Int) :-
+    ( ConsTag = int_tag(IntPrime) ->
+        Int = IntPrime
+    ;
+        unexpected($module, $pred, "not int_tag")
+    ).
+
+get_string_tag(ConsTag, Str) :-
+    ( ConsTag = string_tag(StrPrime) ->
+        Str = StrPrime
+    ;
+        unexpected($module, $pred, "not string_tag")
+    ).
+
+%-----------------------------------------------------------------------------%
 :- end_module backend_libs.switch_util.
 %-----------------------------------------------------------------------------%
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