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

[Julien Fischer]

On Sat, 2 Apr 2005, Mark Brown wrote:

> On 24-Mar-2005, Julien Fischer <juliensf at cs.mu.OZ.AU> wrote:
> > Index: compiler/term_constr_pass2.m
> > ===================================================================
> > RCS file: compiler/term_constr_pass2.m
> > diff -N compiler/term_constr_pass2.m
> > --- /dev/null	1 Jan 1970 00:00:00 -0000
> > +++ compiler/term_constr_pass2.m	23 Mar 2005 23:35:19 -0000
>
> +:- func pass2_options_init(int) = pass2_options.
>
> You should document the argument to this.
>
Done.

> > +:- type cycle
> > +	---> cycle(
> > +		nodes :: list(abstract_ppid),
> > +			% A list of every procedure involved in
> > +			% this cycle.
> > +
> > +		edges :: list(edge)
> > +			% A list of edges involved in this cycle.
> > +			% Note: It is not ordered.  This allows
> > +			% us to decide (later) on where we want
> > +			% the cycle to start.
> > +	).
> > +
> > +:- type cycles == list(cycle).
> > +
> > +	% A c_cycle is a collapsed cycle; where equalities have replaced
> > +	% calls between corresponding edges.
> > +
> > +%
> > +% A little clarification on this:  Each `c_cycles' field is list of
> > +% elementary cycles that start and end at `start'.
> > +%
>
> I don't really understand these comments.  Could you clarify?
>
It's an elementary cycle in the call-graph where a vertex has been
picked and we've gone around the cycle conjoining all the labels
(constraints) as we go.  (I've modified the comment accordingly).

> > +
> > +:- type cycle_set
> > +	---> c_set(
> > +		start    :: abstract_ppid,
> > +		c_cycles :: list(edge)
> > +	).
> > +
>
> > +%-----------------------------------------------------------------------------%
> > +%
> > +% Cycle detection.
> > +%
> > +
> > +% To find the elementary cycles of this SCC we perform a DFS of the call-graph.
> > +% Since the call-graph is technically a psuedograph (ie. it admits parallel
>
> s/psuedograph/pseudograph/
>
> and also below.
Fixed.

> You should check this file for lines exceeding 79 chars.
>
Done.

> > Index: compiler/term_constr_util.m
> > ===================================================================
> > RCS file: compiler/term_constr_util.m
> > diff -N compiler/term_constr_util.m
> > --- /dev/null	1 Jan 1970 00:00:00 -0000
> > +++ compiler/term_constr_util.m	23 Mar 2005 23:37:14 -0000
>
> > +	% Give a list of prog_vars, allocate one size_var per prog_var.
>
> s/Give/Given/
>
Done.

> > +	% Allocate the size_vars from the provided size_varset.  Return
> > +	% a map between prog_vars and size_vars.
> > +	%
> > +:- pred make_size_var_map(list(prog_var)::in,
> > +	size_varset::in, size_varset::out, size_var_map::out) is det.
>
> > +	% compose_bijections:
> > +	% Takes two lists of vars of equal length, each list
> > +	% with a corresponding map from the vars in the list to size_vars.
> > +	% There is an implicit bijection between the two lists
> > +	% (based on the order of the lists).
> > +	% This predicate composes all three maps to produce a map
> > +	% from sizevar to sizevar (keys are the elements of the first list,
> > +	% values the values in the first map).
> > +	%
> > +:- func compose_bijections(size_vars, size_vars) = var_substitution.
>
> I don't really understand the comment here.  Looking at the code I see
> that this is very similar to map__from_corresponding_lists, although
> the keys come from the second list rather than the first.
>
> Note that there is only an implicit bijection if the lists do not contain
> duplicates (which presumably is an invariant of size_vars).
>
That comment is wrong, the relationship should be a many-one mapping.
I've renamed the predicate create_var_substitution and updated the
description.

> > +
> > +:- pred update_arg_size_info(pred_proc_id::in, polyhedron::in, module_info::in,
> > +	module_info::out) is det.
> > +
> > +	% If Override is yes, then this predicate overrides any existing
> > +	% termination information. If Override is no, then it leaves the
> > +	% proc_info of a procedure unchanged unless the proc_info had no
> > +	% termination information (i.e. the maybe(termination_info)
> > +	% field was set to "no").
>
> s/Override/the bool/g
>
> in the above paragraph, or else mention that Override is the second argument.
>
Fixed.

> > +	%
> > +:- pred change_procs_constr_termination_info(list(proc_id)::in, bool::in,
> > +	constr_termination_info::in, proc_table::in, proc_table::out) is det.
> > +
> > +	% This predicate sets the arg_size_info property of the given
> > +	% list of procedures.  If Override is yes, then this predicate
> > +	% overrides any existing arg_size information. If Override is
> > +	% no, then it leaves the proc_info of a procedure unchanged
> > +	% unless the proc_info had no arg_size information (i.e. the
> > +	% maybe(arg_size_info) field was set to "no").
> > +	%
>
> Likewise here.
>
Fixed.

> > +:- pred change_procs_constr_arg_size_info(list(proc_id)::in, bool::in,
> > +	constr_arg_size_info::in, proc_table::in, proc_table::out) is det.
>
> > +	% derive_nonneg_eqns(SizeVarMap, Zeros).
> > +	% Returns a list of constraints of the form "x >= 0" for every size_var
> > +	% x that is is in `SizeVarMap' and is not in the set `Zeros'.
> > +	%
> > +derive_nonneg_eqns(SizeVarMap, Zeros) = Eqns :-
> > +	derive_nonneg_eqns(SizeVarMap, Zeros, Eqns).
>
> This comment belongs in the interface with the declaration.
>
I've moved it there; I've also renamed that predicate
create_nonneg_constraints (that one seemed to be following
the naming scheme on the termination2 branch which was replaced
some time ago).

> > Index: compiler/term_norm.m
> > ===================================================================
> > RCS file: /home/mercury1/repository/mercury/compiler/term_norm.m,v
> > retrieving revision 1.7
> > diff -u -r1.7 term_norm.m
> > --- compiler/term_norm.m	22 Mar 2005 06:40:28 -0000	1.7
> > +++ compiler/term_norm.m	22 Mar 2005 22:04:36 -0000
>
> >  % This predicate will fail if the length of the input lists are not matched.
> > -
> >  :- pred functor_norm_filter_args(list(bool)::in, list(prog_var)::in,
> >  	list(prog_var)::out, list(uni_mode)::in, list(uni_mode)::out)
> >  	is semidet.
>
> You might as well format this comment properly.
>
Done.

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