[m-rev.] for review: new termination analyser (part 6 of 6)

[Julien Fischer]

On Wed, 30 Mar 2005, Mark Brown wrote:

> On 24-Mar-2005, Julien Fischer <juliensf at cs.mu.OZ.AU> wrote:
> > Index: compiler/termination2.m
> > ===================================================================
> > RCS file: compiler/termination2.m
> > diff -N compiler/termination2.m
> > --- /dev/null	1 Jan 1970 00:00:00 -0000
> > +++ compiler/termination2.m	24 Mar 2005 04:17:13 -0000
> > @@ -0,0 +1,736 @@
> > +%-----------------------------------------------------------------------------%
> > +% vim: ft=mercury ts=4 sw=4 et
> > +%-----------------------------------------------------------------------------%
> > +% Copyright (C) 1997,2002-2005 The University of Melbourne.
>
> The copyright years are wrong.
>
How so?

> > +%   (b) Perform fixpoint calculation to derive IR information.
> > +%       ( See term_constr_fixpoint.m.)
>
> There's an extra space.
>
So there is - it's gone.

> > +:- interface.
> > +
> > +:- import_module hlds.hlds_module.
> > +:- import_module hlds.hlds_pred.
> > +
> > +:- import_module parse_tree.prog_data.
> > +
> > +:- import_module libs.polyhedron.
> > +
> > +:- import_module mdbcomp.prim_data.
> > +
> > +:- import_module transform_hlds.term_constr_data.
> > +:- import_module transform_hlds.term_constr_errors.
>
> According to the current coding standards, you should remove the above
> blank lines (and similarly elsewhere).
>
This diff dates from before that change to the coding standard.
I'll make sure that I incorporate any recent changes to the coding
standard before it's committed.

> > +    % Why does the termination analyser think that a procedure is
> > +    % terminating?  This is useful for debugging purposes.
> > +    %
> > +:- type term_reason
> > +    --->    builtin             % procedure was a builtin.
> > +
> > +    ;       pragma_supplied     % procedure has pramga terminates decl.
> > +
> > +    ;       foreign_supplied    % procedure has foreign code attribute.
> > +
> > +    ;       import_supplied     % This procedure was imported and it's
>
> s/it's/its/
>
Done.

> > +                                % termination info. was read in from a .opt
>
> Probably should s/info./info/ (and elsewhere).
>
In that particular case it should be s/info./status/.

> > +                                % or .trans_opt file.
> > +
> > +    ;       analysis.           % Termination info. was derived via analysis.
> > +
>
> > +%------------------------------------------------------------------------------%
> > +%
> > +% The termination2_info structure.
> > +%
> > +
> > +:- type termination2_info
> > +    --->    term2_info(
> > +            size_var_map :: size_var_map,
> > +                % Map between prog_vars and size_vars.
> > +                % Each procedure should have one of these.
>
> That second sentence applies to the whole termination2_info structure,
> so is redundant here.
>
I've deleted the second part.

> (Upon further inspection, perhaps you mean that this field should be filled
> in for each procedure, regardless of whether other fields are.  If so, you
> should make that clearer.)
>
All of the fields should be filled in - those that are optional are
already have maybe types.  (That part of the comment is out of date - it
had some relevance when the size_varset, which is a per-SCC data
structure, was stored there).

> > +
> > +            head_vars :: list(size_var),
> > +                % These are the size variables that occur in argument
> > +                % size constraints.  For procedures that are imported
> > +                % via a `.opt' or `.trans_opt' file we set these during
> > +                % the initial pass, for procedures in the module we are
> > +                % analysing, pass 1 sets it.
> > +
> > +            import_headvarids :: maybe(list(int)),
> > +            import_success   :: maybe(pragma_constr_arg_size_info),
> > +            import_failure   :: maybe(pragma_constr_arg_size_info),
> > +                % Arg size info. imported from another module via a
> > +                % `.opt' or `.trans_opt' file.  The preprocessing pass
> > +                % needs to convert these to the proper form.  These
> > +                % particular fields are of no use after that.
>
> By the "preprocessing" pass I take it you mean the initial pass, aka pass 0.
> If so, you should stick to one of those names.
>
Fixed.  It now reads that: Pass 0 needs to convert these to the proper
form.

> > +
> > +            success_constrs :: maybe(constr_arg_size_info),
> > +                % The interargument size relationships
> > +                % (expressed as convex constraints)
> > +                % obtained during pass 1.
> > +
> > +            failure_constrs :: maybe(constr_arg_size_info),
> > +                % Failure constraints for predicates that
> > +                % can fail (set by pass 1).
> > +
> > +            term_status :: maybe(constr_termination_info),
> > +                % The termination status of the procedure as determined
> > +                % by pass 2.
> > +
> > +            intermod_status :: maybe(intermod_status),
> > +                % Is this procedure (possibly) involved in mutual
> > +                % recursion across module boundaries. Set by pass 1.
>
> s/boundaries/boundaries?/

Fixed.

>
> > +
> > +            abstract_rep :: maybe(abstract_proc)
> > +                % The abstract representation of this
> > +                % proc. Set by term_constr_build.m.
> > +        ).
> > +
> > +term2_info_init = term2_info(map.init, [], no, no, no, no, no, no, no, no).
> > +
> > +%----------------------------------------------------------------------------%
> > +%
> > +% Main pass.
> > +%
> > +
> > +% The analysis proceeds as follows:
> > +%
> > +% * Preprocess the module:
> > +%   - setup information from termination pragmas
> > +%   - setup information from foreign proc attributes
> > +%   - setup information about imported procedures
> > +%   - setup termination information for builtin predicates
> > +%
> > +% * Analyse the module - process SCCs bottom-up.
> > +%
> > +% * Optionally write out termination information to the `.opt' and
> > +%   `.trans_opt' files.
> > +%
>
> You should refer to these stages by the pass names mentioned above.
> Providing more detail would also be good, eg breaking pass 1 into build pass
> and whatever else, since the build pass is mentioned just below.
>

On reflection, I'm just going to delete that comment; it just duplicates
the one at the overview at the beginning of the module.

> > +analyse_scc(DepOrder, BuildOpts, FixpointOpts, Pass2Opts, SCC, !ModuleInfo,
> > +        !IO) :-
> > +    %
> > +    % Since all of the passes are potentially optional we need to
> > +    % initialise the size_var_maps separately.  If they are left
> > +    % uninitialised intermodule optimization will not work.
> > +    %
> > +    NeedsAR = list.filter(proc_needs_ar_built(!.ModuleInfo), SCC),
> > +    %
> > +    % Build the abstract representation for those procedures that
> > +    % require it. (those that do not already have both arg_size_info and
> > +    % termination info).
> > +    %
> > +    term_constr_build.build_abstract_scc(DepOrder, NeedsAR, BuildOpts,
> > +        BuildErrors, !ModuleInfo, !IO),
> > +    %
> > +    % We only perform the fixpoint computation for those procedures
> > +    % where we can gain meaningful information from it.  We do not
> > +    % do it when:
> > +    % - the information is already known.
>
> s/./, or/
>
> (or maybe that should be "and".)
>
Fixed - s/./, or/

> > +%------------------------------------------------------------------------------%
> > +
> > +:- func this_file = string.
> > +
> > +this_file = "termination2.m".
>
> Do you still need this?  It isn't used at the moment.
>

No but it doesn't hurt that as it is, and it's useful if any calls
to unexpected/2  or sorry/2 are added at a later date.

Thanks for that Mark.

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
--------------------------------------------------------------------------