[m-rev.] diff: fix --optimize-higher-order bug

[Simon Taylor]

On 16-Jan-2003, Fergus Henderson <fjh at cs.mu.OZ.AU> wrote:
> On 16-Jan-2003, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> > On 16-Jan-2003, Fergus Henderson <fjh at cs.mu.OZ.AU> wrote:
> > > On 15-Jan-2003, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> > > > 
> > > > Estimated hours taken: 5
> > > > Branches: main, release
> > > > 
> > > > compiler/higher_order.m:
> > > > 	Fix a bug in `--optimize-higher-order' which caused compilation of 
> > > > 	analysis/analysis.file.m to fail with inter-module optimization.
> > > > 	The problem was that type-infos for curried arguments of a higher-order
> > > > 	term were not being added to the typeinfo_varmap for the specialized
> > > > 	procedure.
> > > 
> > > This change seems to have broken the hlc.agc grade.
> > > 
> > > The compiler now generates invalid C code for library/relation.m in grade
> > > hlc.agc at -O3 or higher.  The generated C code refers to an undeclared
> > > type_info variable.
> > > 
> > > The problem seems to be that the HLDS generated by higher_order.m is no
> > > longer meeting an invariant which the accurate GC code is assuming.
> > > In particular, the invariant that it assumes is this: for every
> > > polymorphically typed variable which occurs in a procedure call,
> > > the corresponding type_info variable for that type will also be
> > > an argument of the procedure call.
> > > 
> > > The reason that this invariant is being broken is that the higher order
> > > specialization pass is introducing a procedure that has *more than one
> > > type_info argument corresponding to the same type variable*, and in the
> > > body of the procedure there is a call which passes a variable of type
> > > T, and a type_info that is a type_info for T, but the type_info passed
> > > is not the type_info for T that was recorded in the type_info varmap.
> >
> > I think any code that relies on an invariant as subtle as this
> > is broken anyway, and should be fixed.  I couldn't give a guarantee
> > that other optimization passes don't introduce the same sort of code.
> > It could happen for any optimization which causes types to be substituted
> > (type specialization, inlining, deforestation, any others?).
> 
> The invariant is basically just that for each variable X whose type
> contains a polymorphic type variable T, the type_info variable for T
> is around whenever X is around.  IMHO that is not an unreasonable thing
> to assume!  That's basically the definition of type-info liveness,
> which is used extensively throughout the compiler.
> 
> The only time that maintaining this invariant would be difficult is if 
> there is more than one type_info variable for a single type variable.
> I don't think there is *ever* a good reason to have that.
> If type specialization, inlining, or deforestation don't maintain
> the invariant that there is only one type_info variable for each
> type variable, then IMHO they should be fixed too.
> 
> Furthermore, the definition of the type_info_varmap type assumes that
> there is only one type_info for each type variable.  If you're going to
> break that assumption, then type_info_varmap would need to be changed
> to map each type variable to a set of type_info vars.

That would not be necessary. At the point where accurate garbage
collection needs the type-info, the type-info in the typeinfo_varmap
is guaranteed to be live, and it is also guaranteed that you are
passed a type-info for the type variable (not necessarily the
one in the typeinfo_varmap). It should be trivial to substitute
so that the variable in the typeinfo_varmap is passed.

It's more robust to do this once where the invariant is needed,
rather than in every place where invariant could possibly be broken.

> Inlining preserves the invariant that there is only one type_info variable
> for each type variable, I'm pretty sure. 

It doesn't (although for some reason this example compiles without problems).

:- module agcbug.

:- interface.

:- pred p(T::in) is semidet.

:- implementation.

:- import_module std_util.

p(A) :-
	q(A, B, C),
	r(B),
	r(C).

:- some [U, V] pred q(T::in, U::out, V::out) is det.
:- pragma inline(q/3).

q(X, X, X).

:- pred r(U::in) is semidet.
:- pragma no_inline(r/1).

r(_) :- semidet_succeed.

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