[m-rev.] for review: constant structures for typeinfos and typeclass infos

[Julien Fischer]

Hi Zoltan,

On Thu, 7 Jun 2012, Zoltan Somogyi wrote:

> This diff has been tested not just with bootcheck, but also by make test
> on g12. It gets the same number of test case failures on g12 as a g12
> workspace compiled with a current, unchanged Mercury compiler.

> It is a big diff. Does anyone volunteer to review it? I would like to
> commit it tomorrow, since I plan to work on extensions of this change
> (such as removing the drawback mentioned below) on the weekend.

I have had a look over the diff -- with the exception of the new
const_struct.m module which I think you forgot to cvs add -- and in
principle it looks fine.  I don't have time to do a detailed review of
it before the weekend, but I'm happy for you go ahead and commit it.
(There are a couple of minor issues noted below.)

Julien.

> ------------------------------------------
>
> Heavily polymorphic code, such as that generated by g12, often builds the same
> typeinfos and typeclass infos over and over again. We have long had caches
> that avoid building a new typeinfo or typeclass info if some variable in the
> current scope already contains the right value, but a program that has many
> scopes may still build the same typeinfo or typeclass info many times.
> If that typeinfo or typeclass info is a ground term, the code generators
> will recognize that fact, and will turn all the constructions of that ground
> term in different scopes into referencess to the same constant structure.
> However, in the meantime, the program can be much bigger than necessary.
> In the motivating test case for this change, a single call to fdic_post
> is preceded by 133 goals that build the four typeclass infos it needs.
>
> The main idea of this diff is to construct constant typeinfos and typeclass
> infos out of line, in a separate data structure. Polymorphism then binds
> variables representing typeinfo and typeclass infos to reference to these
> constant structures. In the motivating example, this allows polymorphism.m
> to insert just four goals before the call to fdic_post, the minimal possible
> number: one for each typeclass info that predicate needs.
>
> On Leslie's bug344 program, this change speeds up the compiler by a factor
> of five to eight (reducing compile time from about 80 or 85 seconds to
> 10 or 15).
>
> There is a drawback to this scheme, but it is minor. That drawback is that
> once a constant structure is entered into our database of constant structures,
> it cannot (yet) be removed. Even if all the references to a constant structure
> are eliminated by optimizations, the structure will remain.
>
> ------------------------------------------
>
> CHANGES IN THE FRONT END
>
> compiler/const_struct.m:
> 	A new module to look after our new database of constant structures.
> 	Currently, its use is enable only on the LLDS and MLDS C backends.

s/enable/enabled/

>
> compiler/hlds.m:
> compiler/notes/compiler_design.html:
> 	Add the new module to the HLDS package.
>
> compiler/hlds_module.m:
> 	Include the constant structure database in the module_info.
>
> compiler/hlds_data.m:
> 	Add two new cons_ids, which refer to typeinfos and typeclass infos
> 	implemented as constant structures.
>
> 	Move the code for calculating the number of extra instance args
> 	in base_typeclass_infos here from base_typeclass_info.m, since
> 	polymorphism.m now needs it too. We can now also eliminate the
> 	duplicate copy of that code in higher_order.m.
>
> 	Make an independent optimization: make the restrict_list_elements
> 	function more efficient by avoiding redundant tests.
>
> compiler/polymorphism.m:
> 	When building typeinfo and typeclass infos, keep track of whether
> 	the structure being built is constant. If it is, then put it in the
> 	database of constant structures, and replace the code building it
> 	with a simple reference to that new entry.
>
> 	Since I now expect most goal sequences inserted before goals to be
> 	short, consistent use lists of goals to represent these, since the

s/consistent/consistently/

> 	costs of conversions to and from cord form are unlikely to be paid back
> 	by the higher efficiency of cord operations on longer sequences.
>
> 	When we want to get the typeclass info of a superclass out of the
> 	typeclass info of a subclass, if the typeclass info of the subclass
> 	is known, do the extraction here. We used to do this optimization
> 	only in higher_order.m, but doing so here reduces the size of the HLDS
> 	between polymorphism.m and higher_order.m, and thus improves
> 	compilation time.
>
> 	Reorganize some of the structure of this module to make the above
> 	changes possible. In particular, our new approach requires making
> 	snapshots of the varsets and vartypes, and later restoring those
> 	snapshots if the variables allocated turn out to be unnecessary,
> 	due to all of them describing the components of a constant structure.
> 	The correctness of such code is much easier to check if the taking
> 	and restoring of each snapshot takes places in a single predicate.
>
> 	Remove the code moved to higher_order.m.
>
> 	Add some debugging code for now. If no issues arise in the next few
> 	weeks, it can be deleted.
>

...

> Index: compiler/higher_order.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/compiler/higher_order.m,v
> retrieving revision 1.202
> diff -u -b -r1.202 higher_order.m
> --- compiler/higher_order.m	5 Jun 2012 15:14:26 -0000	1.202
> +++ compiler/higher_order.m	7 Jun 2012 05:32:26 -0000

...

> @@ -925,16 +920,17 @@
>         ),
>         IsInteresting = no
>     ;
> -        ConsId = int_const(_),
>         % We need to keep track of int_consts so we can interpret
> -        % superclass_info_from_typeclass_info and
> -        % typeinfo_from_typeclass_info.  We don't specialize based on them.
> -        IsInteresting = Params ^ param_do_user_type_spec
> -    ;
> -        ( ConsId = type_ctor_info_const(_, _, _)
> +        % calls to the buildins superclass_info_from_typeclass_info and

s/calls/Calls/ and s/buildins/builtins/

> +        % typeinfo_from_typeclass_info. We do not specialize based on
> +        % integers alone.
> +        ( ConsId = int_const(_)
> +        ; ConsId = type_ctor_info_const(_, _, _)
>         ; ConsId = base_typeclass_info_const(_, _, _, _)
>         ; ConsId = type_info_cell_constructor(_)
>         ; ConsId = typeclass_info_cell_constructor
> +        ; ConsId = type_info_const(_)
> +        ; ConsId = typeclass_info_const(_)
>         ),
>         IsInteresting = Params ^ param_do_user_type_spec
>     ;
...

> Index: compiler/hlds_module.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/compiler/hlds_module.m,v
> retrieving revision 1.174
> diff -u -b -r1.174 hlds_module.m
> --- compiler/hlds_module.m	22 Aug 2011 04:23:13 -0000	1.174
> +++ compiler/hlds_module.m	7 Jun 2012 05:32:26 -0000

...

> @@ -835,6 +842,11 @@
>
>                 msi_event_set                   :: event_set,
>
> +                % The database of constant structures the code generator
> +                % will generate independently, outside all the procedures
> +                % of the program.

I suggest s/program/module/ there.

> +                msi_const_struct_db             :: const_struct_db,
> +
>                 % A table of strings used by some threadscope events.
>                 % Currently threadscope events are introduced for each future
>                 % in dep_par_conj.m which is why we need to record the table
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------