[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 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:
> > > > 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.

Sorry, that was incorrect.  I saw something in the HLDS dump which
looked a bit odd, and leapt to some conclusions which were not justified.
After looking a bit more closely, I don't think the hlc.agc back-end does
rely on that invariant.  Sorry for the confusion.

However, having done some more analysis, I think I do know what is going
on now.

The two invariants which I now think are actually causing the problem are
these:

    Invariant 1.  "strong type-info liveness".

	For every polymorphically typed variable V whose type contains
	a type variable T, the type_info specified in the type_info_varmap
	for T will be in scope whenever V is in scope, and live whenever
	V is live.

	I call this the "strong type-info liveness" invariant.
	The alternative invariant which we could use when type-info
	liveness is needed is what I call the "weak type-info liveness"
	invariant:

		For every polymorphically typed variable V whose type
		contains a type variable T, some type_info for T will be
		in scope whenever V is in scope, and live whenever V
		is live.  However, the type_info which is in scope
		need not be the same as the type_info for T in the
		type_info_varmap.

	The debugger and the accurate garbage collector both rely on
	strong type-info liveness, I believe.  Changing them to only
	assume the weak type-info liveness invariant would be a lot of
	work, I think.  So I think we should stick with the strong
	type-info liveness invariant.  (Agreed?)

	As far as I know, the higher-order specialization pass and inlining
	both preserve strong type-info liveness, although I could be wrong
	on this (I've been known to be wrong before ;-).

    Invariant 2.  "head variables scope left-to-right".

	For the strong type-info liveness invariant (Invariant 1),
	each head variable is considered to scope over those to
	the right of it, but does not scope over those to its left.

	That is, for each type variable T occurring in the procedure
	signature, the type-info specified for T in the type_info_varmap
	must come before any variables whose type contains T.

	The corresponding invariant for the MLDS is that the scoping
	rules for the code in the mlds__maybe_gc_trace_code attached
	to each function parameter are just the usual (C,C++,Java,C#,etc.)
	scoping rules: variables declared to the left of that code are
	in scope, variables declared to the right of that code are not
	yet in scope.

	The alternative to left-to-right scoping of head variables
	would be that all head variables in a procedure scope over
	each other for the purpose of Invariant 1 (strong type-info
	liveness).  However, this HLDS invariant would lead to a
	more complicated corresponding MLDS invariant, which would
	significantly complicate some parts of the MLDS back-end,
	such as ml_elim_nested.m.


Fixing the MLDS back-end's implementation to not rely on these
invariants looks to me like a difficult task.

I don't know how difficult it would be to modify the higher-order
specialization pass to preserve them.  However, in the mean time,
I will go for the quick fix: just disable higher-order specialization
when accurate GC is enabled.  Note that deforestation and constraint
propagation are already disabled when type_info_body_liveness
(i.e. debugging or accurate GC) is enabled, since they don't
preserve Invariant 1.

So how about the following patch?

----------

Estimated hours taken: 8
Branches: main

compiler/handle_options.m:
	Disable higher-order specialization if accurate GC is enabled,
	since the higher-order specialization pass doesn't preserve
	the invariants required by the implementation of accurate GC
	in the MLDS back-end; in particular it doesn't preserve
	strong type-info liveness with left-to-right parameter scoping.
	(For details, see mail in mercury-reviews for details.)

Workspace: /home/ceres/fjh/mercury
Index: compiler/handle_options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/handle_options.m,v
retrieving revision 1.161
diff -u -d -r1.161 handle_options.m
--- compiler/handle_options.m	20 Dec 2002 09:46:18 -0000	1.161
+++ compiler/handle_options.m	16 Jan 2003 16:52:45 -0000
@@ -787,13 +787,25 @@
 	% `trace' stack layouts need `procid' stack layouts
 	option_implies(trace_stack_layout, procid_stack_layout, bool(yes)),
 
-	% --gc accurate requires `agc' stack layouts, typeinfo liveness,
-	% and needs hijacks and frameopt to be switched off.
+	% --gc accurate for the LLDS back-end (not yet implemented...)
+	% requires `agc' stack layouts, typeinfo liveness, and
+	% needs hijacks and frameopt to be switched off.
+	% For the MLDS back-end, `--gc accurate' requires just typeinfo
+	% liveness.
+	%
+	% XXX currently accurate GC also requires disabling the higher-order
+	% specialization pass, since that pass creates procedures
+	% which don't respect left-to-right scoping of type_info parameters,
+	% i.e. in which a parameter X may have a type whose type_info var
+	% (in the type_info_varmap) occurs to the right of X in the
+	% procedure's parameter list.
+	% 
 	( { GC_Method = accurate } ->
 		globals__io_set_option(agc_stack_layout, bool(yes)),
 		globals__io_set_option(body_typeinfo_liveness, bool(yes)),
 		globals__io_set_option(allow_hijacks, bool(no)),
-		globals__io_set_option(optimize_frames, bool(no))
+		globals__io_set_option(optimize_frames, bool(no)),
+		globals__io_set_option(optimize_higher_order, bool(no))
 	;
 		[]
 	),

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