[m-rev.] for review: better lookup switches

[Julien Fischer]

On Wed, 29 Mar 2006, Zoltan Somogyi wrote:

> Implement a more cache-friendly translation of lookup switches. Previously,
> for a switch such as the one in
>
> 	:- pred p(foo::in, string::out, bar::out, float::out) is semidet.
>
> 	p(d, "four", f1, 4.4).
> 	p(e, "five", f2, 5.5).
> 	p(f, "six", f4("hex"), 6.6).
> 	p(g, "seven", f5(77.7), 7.7).
>
> we generated three static cells, one for each argument, and then indexed
> into each one in turn to get the values of HeadVar__2, HeadVar__3 and
> HeadVar__4. The different static cells each represent a column here.
> Each of the loads accessing the columns will access a different cache block,
> so with this technique we expect to get as many cache misses as there are
> output variables.
>
> This diff changes the code we generate to use a vector of static cells
> where each cell represents a row. The assignments to the output variables
> will now access the different fields of a row, which will be next to each
> other. We thus expect only one cache miss irrespective of the number of output
> variables, at least up to the number of variables that actually fit into one
> cache block.
>
> compiler/global_data.m:
> 	Provide a mechanism for creating not just single (scalar) static cells,
> 	but arrays (vectors) of them.
>
> compiler/lookup_switch.m:
> 	Use the new mechanism to generate code along the lines described above.
>
> 	Put the information passed between the two halves of the lookup switch
> 	implementation (detection and code generation) into an opaque data
> 	structure.
>
> compiler/switch_gen.m:
> 	Conform to the new interface of lookup_switch.m.
>
> compiler/ll_pseudo_type_info.m:
> compiler/stack_layout.m:
> compiler/string_switch.m:
> compiler/unify_gen.m:
> compiler/var_locn.m:
> 	Conform to the change to global_data.m.
>
> compiler/llds.m:
> 	Define the data structures for holding vectors of static cells. Rename
> 	the function symbols we used to use to refer to static cells to make
> 	clear that they apply to scalar cells only. Provide similar mechanisms
> 	for representing static cell vectors and references to them.
>
> 	Generalize heap_ref heap references to allow the index to be computed
> 	at runtime, not compile time. For symmetry's sake, do likewise
> 	for stack references.
>
> compiler/llds_out.m:
> 	Add the code required to write out static cell vectors.
>
> 	Rename decl_ids to increase clarity and avoid ambiguity.
>
> compiler/code_util.m:
> compiler/exprn_aux.m:
> 	Modify code that traverses rvals to now also traverse the new rvals
> 	inside memory references.
>
> compiler/name_mangle.m:
> 	Provide the prefix for static cell vectors.
>
> compiler/layout_out.m:
> compiler/rtti_out.m:
> compiler/opt_debug.m:
> 	Conform to the change to data_addrs and decl_ids.
>
> compiler/code_info.m:
> 	Provide access to the new functionality in global_data.m, and conform
> 	to the change to llds.m.
>
> 	Provide a utility predicate needed by lookup_switch.m.
>
> compiler/hlds_llds.m:
> 	Fix the formatting of some comments.
>
> tests/hard_coded/dense_lookup_switch2.{m,exp}:
> tests/hard_coded/dense_lookup_switch3.{m,exp}:
> 	New test cases to exercise the new algorithm.
>
> tests/hard_coded/Mmakefile:
> 	Enable the new test cases, as well as an old one (from 1997!)
> 	that seems never to have been enabled.
>

You've modified some scripts in the tools directory as well, but this
isn't mentioned in the log message (presumambly it's just indentation
changes?).

...

> Index: compiler/global_data.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/compiler/global_data.m,v
> retrieving revision 1.15
> diff -u -b -r1.15 global_data.m
> --- compiler/global_data.m	21 Mar 2006 02:33:34 -0000	1.15
> +++ compiler/global_data.m	27 Mar 2006 15:02:30 -0000

...

> @@ -295,12 +337,210 @@
>                  % be useful when comparing the LLDS and MLDS backends.
>              ),
>              map.set(CellGroupMap0, TypeNum, !.CellGroup, CellGroupMap),
> -            !:Info = !.Info ^ cell_group_map := CellGroupMap
> +            !:Info = !.Info ^ scalar_cell_group_map := CellGroupMap
>          )
>      ),
>      ModuleName = !.Info ^ sub_info ^ module_name,
>      DataAddr = data_addr(ModuleName, DataName).
>
> +:- func init_scalar_cell_group = scalar_cell_group.
> +
> +init_scalar_cell_group = scalar_cell_group(counter.init(0), bimap.init, []).
> +
> +search_scalar_static_cell_offset(Info, DataAddr, Offset, Rval) :-
> +    DataAddr = data_addr(Info ^ sub_info ^ module_name, DataName),
> +    DataName = scalar_common_ref(TypeNum, _CellNum),
> +    CellGroupMap = Info ^ scalar_cell_group_map,
> +    map.lookup(CellGroupMap, TypeNum, CellGroup),
> +    CellGroupMembers = CellGroup ^ scalar_cell_group_members,
> +    bimap.reverse_lookup(CellGroupMembers, Rvals, DataName),
> +    list.index0_det(Rvals, Offset, Rval).
> +
> +%-----------------------------------------------------------------------------%
> +
> +find_general_llds_types(UnboxFloat, Types, [Vector | Vectors], LLDSTypes) :-
> +    list.map(natural_type(UnboxFloat), Vector, LLDSTypes0),
> +    find_general_llds_types_2(UnboxFloat, Types, Vectors,
> +        LLDSTypes0, LLDSTypes).
> +
> +:- pred find_general_llds_types_2(bool::in, list(mer_type)::in,
> +    list(list(rval))::in, list(llds_type)::in, list(llds_type)::out)
> +    is semidet.
> +
> +find_general_llds_types_2(_UnboxFloat, _Types, [], !LLDSTypes).
> +find_general_llds_types_2(UnboxFloat, Types, [Vector | Vectors], !LLDSTypes) :-
> +    find_general_llds_types_in_cell(UnboxFloat, Types, Vector, !LLDSTypes),
> +    find_general_llds_types_2(UnboxFloat, Types, Vectors, !LLDSTypes).
> +
> +:- pred find_general_llds_types_in_cell(bool::in, list(mer_type)::in,
> +    list(rval)::in, list(llds_type)::in, list(llds_type)::out) is semidet.
> +
> +find_general_llds_types_in_cell(_UnboxFloat, [], [], [], []).
> +find_general_llds_types_in_cell(UnboxFloat, [_Type | Types], [Rval | Rvals],
> +        [LLDSType0 | LLDSTypes0], [LLDSType | LLDSTypes]) :-
> +    natural_type(UnboxFloat, Rval, NaturalType),
> +    % For user-defined types, some function symbols may be constants
> +    % (whose representations yield integer rvals) while others may be
> +    % non-constants (whose representations yield data_ptr rvals).
> +    % We need to be able to handle switches in which a variable of such a type
> +    % has a value of one kind in one switch arm and a value of the other kind
> +    % in another switch arm. We can mix the two because it is OK to initialize
> +    % a field declared to be a data_ptr with an integer rval.
> +    %
> +    % If there are any other similar cases, they should be added here.
> +    % The value of Type may be useful in such code.
> +    (
> +        NaturalType = LLDSType0
> +    ->
> +        LLDSType = LLDSType0
> +    ;
> +        NaturalType = integer,
> +        LLDSType0 = data_ptr
> +    ->
> +        LLDSType = data_ptr
> +    ;
> +        NaturalType = data_ptr,
> +        LLDSType0 = integer
> +    ->
> +        LLDSType = data_ptr
> +    ;
> +        fail
> +    ),
> +    find_general_llds_types_in_cell(UnboxFloat, Types, Rvals,
> +        LLDSTypes0, LLDSTypes).
> +
> +%-----------------------------------------------------------------------------%
> +
> +add_vector_static_cell(LLDSTypes, VectorData, DataAddr, !Info) :-
> +    require(list.is_not_empty(LLDSTypes), "add_vector_static_cell: no types"),
> +    require(list.is_not_empty(VectorData), "add_vector_static_cell: no data"),

Use expect/3 instead of require/2 there.

I've had a quick look at the rest and it all seems okay.

Julien.


--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------