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

[Fergus Henderson]

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.
> > 
> > Passing the same type_info multiple types is inefficient and is quite
> > likely to cause problems in later stages of the compiler.  So I think
> > higher_order.m should be modified to not pass the same type_info as
> > two separate arguments.
> > 
> > Simon, could you please fix this?
> 
> 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 be
a pretty major change, and IMHO it is better to just ensure that
no pass produces code which contains more than one type_info variable
for each type variable.

Inlining preserves the invariant that there is only one type_info variable
for each type variable, I'm pretty sure.  I don't know off-hand if type
specialization and deforestation preserve it, but you're welcome to check it.

Anyway, I don't mind too much how you fix it.
If you really think that the best way to fix it is
to change the type_info_varmap to keep a set of type_info vars,
and changing the MLDS back-end's accurate GC code to handle
the possibility that a type var is represented by multiple type_info vars,
that's OK with me.  But your change has introduced a regression,
so please fix it, or back out your change.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------