[m-dev.] making .trans_opt files in parallel

[Zoltan Somogyi]

2022-12-13 20:46 GMT+11:00 "Zoltan Somogyi" <zoltan.somogyi at runbox.com>:
> I suppose the first problem could be addressed by breaking the job
> into two parts: computing the strongly connected components
> of the imports graph, and then generating a separate dot file for each scc.
> It would be better if you could do this interactively, but statically would do.

A somewhat detailed proposal for the above follows.
When given a new auxiliary output option, named maybe --output-import-info,
the compiler would generate a file, named maybe modulename.import_info,
containing a single term of this type:

:- type module_imports
    --->    module_imports(
                % This module ...
                module_name,

                % ... imports entities from these modules.
                % Each imported-from module should have one entry.
                list(module_imports_from)
            ).

:- type module_imports_from
    --->    module_imports_from(
                % The name of the module from which ...
                module_name,

                % ... these entities are imported.
                % Each kind of entity should have only one entry.
                list(imported_entity_list)
            ).

:- type import_entity_list
    --->    imported_types(list(name_arity))
    ;       imported_insts(list(name_arity))
    ;       imported_modes(list(name_arity))
    ;       imported_preds(list(name_arity))
    ;       imported_funcs(list(name_arity))
    ;       imported_typeclasses(name_arity).
    % possibly other entities, such as instances, promises and includes.

It would generate the data to put into this file just after the end
of semantic analysis, mostly by traversing the HLDS at that time,
building up a map from module names to sets of the different kinds
of imported entities. I say *mostly*, because it would also get info
from equiv_type.m and equiv_type_hlds.m about which equivalence types
were actually expanded, and include the expanded equivalence types
to be imported entities as well.

The contents of the file would be designed to be read with just io.read,
for use by the tool described next, but would be formatted to be easily
readable by humans as well.

--------------------------

We could then have a separate program which, when given a command-line list
of .import_info files, which could be e.g. all the .import_info files
of a directory or of a program, it would do the following.

- Build the dag containing an edge from module A to module B if module A
  imports anything from module B. Call this the "module dag".

- Compute the reduced version of that dag, i.e. the dag in which each node
  represents an SCC of the original dag. Call this the "scc dag".

- For each node in the scc dag, pick a module in the scc (call it module C),
  maybe the one whose name is first in lexicograph order, and create a file
  named e.g. imports_C.dot, maybe in a separate directory, containing a dot
  description of the imports among the modules in the scc. Imports from
  any modules that are not in the scc would be ignored. If possible, the
  edges would be labelled either with the list of the entities that are
  imported along that edge, or with a file:/// URL to (the relevant part of)
  the .import_info file containing that list. Additionally, the tool could
  convert this .dot file to a .svg file, or whatever format we end up
  preferring.

  If the scc contained modules C, D and E, we *could* name the file
  imports_C_D_E.dot, but when the scc has ten modules, each of which has
  names such as transform_hlds.ctgc.structure_reuse.direct.detect_garbage,
  the files would end up being far too long. It may therefore be useful
  to also generate an index file, which says, for each module in the graph,
  which .dot file contains its scc.

  Note that having a separate .dot file for each scc, instead of a single
  .dot file for the whole system, should prevent the make the generated
  graphs small enough to be easily explored in most cases. (An scc that
  contains dozens of modules would probably still yield a hard-to-grasp
  graph.)

- The tool could also output a .trans_opt_order file. This file would
  contain a list of entries, each of which would be a list of one or more
  module names:

    module_z    module_y module_x
    module_y    module_u
    module_x    module_u module_t
    ...

  These lines implicitly describe a directed graph, by stating that there is
  an edge from the first module on the line (the target), to each of the
  following modules on the line (the sources).

  The meaning of each graph would be: the compiler invocation writing the
  .trans_opt file of each module, e.g. module_z, is allowed to read
  
  - the .trans_opt files of the modules reachable from it directly
    (for module_z, this means module_y and module_x), and
  - the .trans_opt files of the modules reachable from it indirectly
    (for module_z, this means at least module_u and module_t,
    and maybe more).

  This graph, call it the trans_opt order graph,  would of course
  not allow any cycles.

  This graph would be computed via a top-down traversal of the scc graph.
  Within each scc, the algorithm would pick an order among the modules
  of the scc. Then, for each module in the scc, it would output a line

  - the target module being the current module,
  - the source modules being the modules, if any, following the current
    module in the within-the-scc order, plus the modules in lower sccs
    from which the current module imports any entities.

  If we give mmc --make access to this file, then, when it builds .trans_opt
  files, it could build the .trans_opt files in bottom-up order. Given
  an entry such as

    module_x    module_u module_t

  it could start building module_x.trans_opt as soon as module_u.trans_opt
  and module_t.trans_opt are complete.

  To optimize these checks, if there are two source modules, call them
  module_r and module_s, and module_s.trans_opt depends on module_r.trans_opt,
  then you can delete module_r from the set of listed sources, because
  even in its absence, the target depends on module_r.trans_opt through
  module_s.trans_opt.

  We could modify the make rules for .trans_opt files we put into .dep files
  to reflect these dependencies as well.

  This should allow significant parallelism when building e.g. the standard
  library, since many modules depend on no other modules, and some others
  depend on only a few.

Opinions?

Zoltan.