Transitive Intermodule Optimization

[Christopher Rodd SPEIRS]

Hi All,
	When I committed termination analysis, it included code to
handle transitive intermodule optimization.  Unfortunatly, the code is
not finished.  As it stands, the code correctly creates the .trans_opt
file and correctly reads it back.  However, the code does not guarantee
correctness, as circular dependencies can be created. (for details, see
the beginning of trans_opt.m). There are a number of possible solutions
to the problems, but none of them are perfect, so I thought I would
explain the possibilities so we can discuss which is the best solution.

	Firstly, reasons to have transitive intermodule optimization.  
The main benefit that it provides is to allow more accurate information
about imported modules to be used when compiling.  Its use is not
limited to termination analysis, for example it would be very useful
with inlining, where predicates could be inlined transitively.  For
termination analysis, the accuracy of the information is particularly
important.  To prove the termination of a predicate, we must be able to
prove the termination of every predicate that that predicate depends on,
transitively.

Possible Solutions:
Using a .order file.
    The idea behind this solution is to create a <module>.order file
    when mmake <module>.depend is run.  This file would store a
    topological ordering of the modules in the program.  When compiling
    a given module, x, which imports module y, y.trans_opt could only be
    read if y is lower in the ordering than x.  This guarantees that no
    circular dependencies can occur.  Note that the information does not
    necessarily need to reside in a file, it could be stored in the
    mmakefile, and passed to mmc through an environment variable.  

    Problems:
     - The information in the .order file would only be updated when
       mmake <module>.depend is run, which is not very often.
     - When circular dependencies exist between modules (x imports y,
       and y imports x), it would be difficult to break these
       circularities in an optimal way. (currently our best solution is
       to impose alphabetical ordering to break cycles).  In particular,
       when x imports y for types only, then it would be preferable if y
       appeared above x in the ordering.
     - When there are 2 seperate programs which both use some common
       modules, there are problems ensuring correctness. Suppose program
       A and program B both use modules x, y and z.  When mmake A.depend
       is run, z depends on y, y depends on x, so the ordering is z,y,x.
       when B.depend is run, an additional dependency of x depends on z
       has been added, so the ordering is x,y,z.  This problem would
       need to be considered when deciding upon a solution. 

.opt2 .opt3 ... files.
    This solution would store transitive intermodule information in a
    series of files, such that each file could only depend on files
    which come earlier in the series. (so, m.opt3 could depend on
    m.opt2, but not the other way round). 

    Problems:
     - Too many files would be created, and too many compilations
       would be required.  Perhaps it would be possible to store all the
       information in one file, maintaining the dependency internally,
       but this introduces other difficulties.
     - For a line of n dependencies (A depends on B depends on C ...), n
       opt files would be required.

Track and update dependencies locally, ensuring that circularities
cannot develop.
    This would be implemented by storing the names of all .trans_opt
    files that any particular .trans_opt file depends on in the file.
    Other .trans opt files may then depend on that file if it does not
    introduce a circularity.  For example, X.trans_opt depends on
    Y.trans_opt and Z.trans_opt.  When making Z.trans_opt, X.trans_opt
    could not be used, as this would create a circularity.

    Problems:
     - Parallel makes.  With simultaneous compilations, it is difficult
       to ensure that circularities cannot develop.  Perhaps it can be
       avoided:

        - Store actual dependencies in .d files.  Therefore, the
	  dependencies are properly handled by make, and files are
	  recreated when they are out of date.  
        - Store `would like to depend on' in .trans_opt files.
	- Algorithm is:
	  - Suppose that when creating A.trans_opt, we would like to use
	    the information in B.trans_opt.  
	  - If B.trans_opt does not list a dependency on A.trans_opt and
	    B.d does not list a dependency of B.trans_opt on A.trans_opt
	    then add a 'would like to depend on' to A.trans_opt, but the
	    information in B.trans_opt cannot be read yet.
	  - The next time A.trans_opt is created, if there is still no
	    dependency of B.trans_opt on A.trans_opt, then add
	    B.trans_opt to A.d.  Question: Can B.trans_opt be read at
	    this stage, or do we need to wait till the next compilation?
	    If there is a dependency, then remove the 'would like to
	    depend on' if the file you want to depend on is higher (in
	    alphabetical ordering) than the current file.  This ensures
	    that the dependency is removed from one file.
     - It takes quite a few recompilations to get each dependency
       correct.
     - It is unclear how to set up the dependencies initially, but using
       the ordering produced for the .order file would seem logical.
     - Do we need to do anything special when removing dependencies, or
       can we just delete the dependencies from the .d and .trans_opt
       files?


Also, it is possible to use the .opt2 .opt3 solution in conjunction with
either the first or last solution.  Such a solution would not need many
files, I believe that in practice 3 files would be sufficient.  Note
that the .opt2 file would only be useful when there is a circularity in
the dependencies.

Chris