[m-rev.] for review: use nested lists when building the HLDS

[Julien Fischer]

On Mon, 17 May 2021, Zoltan Somogyi wrote:

> For review by anyone.

> Record section info with lists of items.
> 
> compiler/make_hlds.m:
>     Make the representation of sec_lists and ims_lists more efficient.
>
>     The old definition of sec_list(T), where T is item_X_info for some X, was
>
>     :- type sec_list(T) == list(sec_item(T)).
>     :- type sec_item(T)
>         --->    sec_item(sec_info, T).
>
>     while the new definition is
>
>     :- type sec_list(T) == list(sec_sub_list(T)).
>     :- type sec_sub_list(T)
>         --->    sec_sub_list(sec_info, list(T)).
>
>     The change to the ims_list type is analogous.
>
>     The new definition has sevaral advantages.
>
>     - There is no need to allocate a sec_item cell for each item_X_info.
>     - The parse trees from which we take the item_X_infos already have them
>       in a list. The old representation had to rebuild this list around the
>       sec_items, while the new representation does not: it allocates just
>       one cell for each list in each parse_tree.
>     - To ensure that the predicate built the list of sec_infos in the old
>       approach, built this list accumulator style by appending to the front
>       in order to guarantee tail recursion. Preserving the original order
>       in the final result thus requires a list reversal with yet more
>       memory allocation.
>
>     The one disadvantage of the new type definition is that it requires
>     a two level traversal: first of the sublists, then of the items within
>     them. However, this minor disadvantage is offset by the fact that
>     it allows for a simple form of loop invariant optimization. Specifically,
>     for some item kinds, computations on the sec_info can be done once
>     per sublist, and do not have to be repeated once per item.
> 
> compiler/make_hlds_separate_items.m:
>     Accumulate item_X_infos in the form of cords of sublists. Being able
>     to append to these cords in constant time means that we never have to
>     reverse or re-reverse lists of items, and the cords are trivial to
>     transform to sec_lists and ims_lists at the end.
> 
> compiler/make_hlds_passes.m:
>     Add the list of each kind of item to the HLDS using the two level loop
>     described above.
> 
> compiler/add_class.m:
> compiler/add_mode.m:
> compiler/add_mutable_aux_preds.m:
> compiler/add_pragma.m:
> compiler/add_pred.m:
>     Export predicates that add whole two level lists of items, not just
>     predicates that add a single item. Move computations from the inner loop
>     to the outer loop whenever possible.

That looks fine.

Julien