Re: GC changes

Re: GC changes

[Mike Stump]

> From: Joern Rennecke <amylaar@cambridge.redhat.com>
> To: egcs@tantalophile.demon.co.uk (Jamie Lokier)
> Date: Sun, 14 Jan 2001 23:03:51 +0000 (GMT)

> That is not safe.  You can't predict what kind of address arithmetic
> the compiler will make.  For example, strength reduction could cause
> a pointer to be pointing into the middle of an array, or worse,
> somewhere beyond it (incorporating some constant adjustments).

We already need a switch to disable GC unfriendly optimizations.

Re: GC changes

[Jamie Lokier]

Mike Stump wrote:
> > That is not safe.  You can't predict what kind of address arithmetic
> > the compiler will make.  For example, strength reduction could cause
> > a pointer to be pointing into the middle of an array, or worse,
> > somewhere beyond it (incorporating some constant adjustments).
> 
> We already need a switch to disable GC unfriendly optimizations.

Or two -- some GCs can handle interior pointers but some cannot.

Perhaps GC-safety should be a type attribute, rather than a
compile time flag.

-- Jamie

Re: GC changes

[Bernd Schmidt]

On Mon, 15 Jan 2001, Jamie Lokier wrote:

> Mike Stump wrote:
> > > That is not safe.  You can't predict what kind of address arithmetic
> > > the compiler will make.  For example, strength reduction could cause
> > > a pointer to be pointing into the middle of an array, or worse,
> > > somewhere beyond it (incorporating some constant adjustments).
> >
> > We already need a switch to disable GC unfriendly optimizations.

Which ones would that be?
And how can we verify that the generated code is indeed GC friendly?  If it
can't be verified with a testsuite, such a switch might as well not be there,
since it won't work in practice.


Bernd

Re: GC changes

[Jamie Lokier]

Bernd Schmidt wrote:
> > > We already need a switch to disable GC unfriendly optimizations.
> 
> Which ones would that be?

The rule is: if a memory object may be accessed after an insn, a pointer
to the object(*) must be present in a register or on the stack.

(*) or a more relaxed rule if the GC can handle it: a pointer into the
object must be present.

All optimisations must guarantee this.  In practice, there probably
aren't many optimisations that break.  Only those that offset addresses
(cse, loop, reload?).  It's conceivable that some machine descriptions
might temporarily offset an address unknown to the main compiler code.
E.g. "sub REG,REG,4, jump to REG+4" I can imagine on some hypothetical
RISC chip (Sparc?).

Even a jump to an address _might_ count as a use, if we're dealing with
systems that load code dynamically, but that's getting a bit far fetched.

Making the optimisations safe may amount to lots of extra USE notes.  In
practice the code change should be small.  At worst, you can simply
store the non-offset addresses on the stack before killing them from
registers.

> And how can we verify that the generated code is indeed GC friendly?  If it
> can't be verified with a testsuite, such a switch might as well not be there,
> since it won't work in practice.

Unfortunately you have to have test cases which can trigger the wrong
optimisation.  Quite difficult and the failures will be platform
specific.  Checking the registers and stack is quite portable using
setjmp, so a test can use that to ask "do the registers/stack contain a
pointer to OBJECT at this point in the code?".

-- Jamie

Re: GC changes

[Jamie Lokier]

Jamie Lokier wrote:
> > > > We already need a switch to disable GC unfriendly optimizations.
> > 
> > Which ones would that be?
> 
> The rule is: if a memory object may be accessed after an insn, a pointer
> to the object(*) must be present in a register or on the stack.

Actually there is another approach.  You could generate unwind stubs
similar to exception handling, with a table indexed by program counter
to the stubs.  For most program addresses the stub would be empty, but
for certain places where only an offset address is present, the stub
would generate the non-offset address.

This has the advantage that no optimisation is penalised.  It's quite
complex to implement though.

-- Jamie

Re: GC changes

[Fergus Henderson]

On 15-Jan-2001, Jamie Lokier <egcs@tantalophile.demon.co.uk> wrote:
> Mike Stump wrote:
> > > That is not safe.  You can't predict what kind of address arithmetic
> > > the compiler will make.  For example, strength reduction could cause
> > > a pointer to be pointing into the middle of an array, or worse,
> > > somewhere beyond it (incorporating some constant adjustments).
> > 
> > We already need a switch to disable GC unfriendly optimizations.
> 
> Or two -- some GCs can handle interior pointers but some cannot.

And some GCs can handle some interior pointers but not others.
E.g. the Boehm GC can be configured to handle

	- no interior pointers
	- interior pointers with an offset up to N
	- all interior pointers but not the one-past-the-end pointers
	- all interior pointers plus one-past-the-end pointers

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

Re: GC changes

[Fergus Henderson]

On 15-Jan-2001, Bernd Schmidt <bernds@redhat.com> wrote:
> On Mon, 15 Jan 2001, Jamie Lokier wrote:
> 
> > Mike Stump wrote:
> > > > That is not safe.  You can't predict what kind of address arithmetic
> > > > the compiler will make.  For example, strength reduction could cause
> > > > a pointer to be pointing into the middle of an array, or worse,
> > > > somewhere beyond it (incorporating some constant adjustments).
> > >
> > > We already need a switch to disable GC unfriendly optimizations.
> 
> Which ones would that be?
> And how can we verify that the generated code is indeed GC friendly?

One way is to run lots of programs with the Boehm (et al) conservative
collector.  The Java and Mercury front-ends may prove to be good
sources of such test cases, since they both use that collector.
But it would also be possible to obtain test cases from code in other
languages by linking with a version of the Boehm collector compiled
with REDIRECT_MALLOC enabled.

> If it can't be verified with a testsuite, such a switch might as well
> not be there, since it won't work in practice.

In general a test suite can show never prove correctness.
A test suite can only ever show the presence of errors.

The empirical evidence seems to be that the vast majority of the time
it does work in practice, even without the switch.  The point of
adding the switch would be to increase the likelihood that
conservative GC continues to work in the future, and to make it clear
that optimizations which are not GC-friendly are bugs if the switch is
enabled.

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

Re: GC changes

[Bernd Schmidt]

> > > > We already need a switch to disable GC unfriendly optimizations.
> >
> > Which ones would that be?
> > And how can we verify that the generated code is indeed GC friendly?

On Tue, 16 Jan 2001, Fergus Henderson wrote:
> One way is to run lots of programs with the Boehm (et al) conservative
> collector.  The Java and Mercury front-ends may prove to be good
> sources of such test cases, since they both use that collector.
> But it would also be possible to obtain test cases from code in other
> languages by linking with a version of the Boehm collector compiled
> with REDIRECT_MALLOC enabled.
>
> > If it can't be verified with a testsuite, such a switch might as well
> > not be there, since it won't work in practice.
>
> In general a test suite can show never prove correctness.
> A test suite can only ever show the presence of errors.

Which would go a long way.  Ideally we'd need some way to compile a
program with "-fgc-safe" and then single-step through it with a simulator
while verifying that at each point all the assumptions we make for GC
still hold.

> The empirical evidence seems to be that the vast majority of the time
> it does work in practice, even without the switch.  The point of
> adding the switch would be to increase the likelihood that
> conservative GC continues to work in the future, and to make it clear
> that optimizations which are not GC-friendly are bugs if the switch is
> enabled.

That doesn't sound like a very good design.  The problem I see is that
no part of gcc was written with GC in mind.  I don't think anyone will
bother going through every line of code to verify that it does the right
thing, so, as you say, we'll only be able to talk about likelihoods.
From what I've seen people keep saying "loop might be unsafe, possibly
other passes as well" - no one really knows for sure as far as I can tell.

A switch "-fgc-safe" is a promise to the user, and we shouldn't make
promises we can't keep.

It's also an additional maintenance burden since it adds more requirements
that must be kept in mind when adding new code.  If we have no automated
way of testing it, people will break it all the time.


Bernd

Re: GC changes

[Fergus Henderson]

On 16-Jan-2001, Bernd Schmidt <bernds@redhat.com> wrote:
> 
> > The empirical evidence seems to be that the vast majority of the time
> > it does work in practice, even without the switch.  The point of
> > adding the switch would be to increase the likelihood that
> > conservative GC continues to work in the future, and to make it clear
> > that optimizations which are not GC-friendly are bugs if the switch is
> > enabled.
> 
> That doesn't sound like a very good design.  The problem I see is that
> no part of gcc was written with GC in mind.

It's certainly not an ideal design.  But unfortunately compilers that
support garbage collection and have the same advantages as GCC are
hard to find.  When push comes to shove, many people will choose to
use GCC in conjunction with a conservative garbage collector,
accepting the risks that this involves, since even with those risks
overall this combination has many advantages over the competitors.

The Mercury and Java front-ends to GCC are examples of this.

> I don't think anyone will
> bother going through every line of code to verify that it does the right
> thing, so, as you say, we'll only be able to talk about likelihoods.
> From what I've seen people keep saying "loop might be unsafe, possibly
> other passes as well" - no one really knows for sure as far as I can tell.
> 
> A switch "-fgc-safe" is a promise to the user, and we shouldn't make
> promises we can't keep.

You're right that we shouldn't make promises that we can't keep.  So
you could make a reasonable argument that the documentation for this
switch should explicitly say that it might not work, since no-one has
fully analyzed all of the GCC source code to ensure that it is
respects the switch.

However, people are making such assumptions anyway.  And the emperical
evidence is that such assumptions are not unreasonable.  My personal
practical experience, based on having tested millions of lines of C
code with GCC, is that bugs in GC safety are much rarer than ordinary
bugs in other parts of GCC, even though GCC does not explicitly
support GC safety.  I have discovered and reported many bugs in GCC.
I have not yet discovered any problems due to optimizations breaking
GC safety.

> It's also an additional maintenance burden since it adds more requirements
> that must be kept in mind when adding new code.

That's true, but I think the burden is well worth it.  Garbage
collection is undoubtably the way of the future.  If GCC doesn't
support garbage collection then it will slowly but surely lose market
share.

> If we have no automated way of testing it, people will break it all the time.

People break GCC all the time.  GCC is always broken.
What really matters is whether the bugs show up in practice.
If the bugs show up in practice, then they can be tested for and fixed.

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

Re: GC changes

[Jamie Lokier]

Fergus Henderson wrote:
> > If we have no automated way of testing it, people will break it all
> > the time.
> 
> People break GCC all the time.  GCC is always broken.
> What really matters is whether the bugs show up in practice.
> If the bugs show up in practice, then they can be tested for and fixed.

Bear in mind that GC bugs due to misoptimisation are _extremely_ rare
to trigger both at compile time and at run time, even compared with
normal optimisation bugs.

A GC must be triggered at exactly the wrong moment.

Therefore merely testing that code works at run time does not give the
same level of confidence as it does with normal optimisations.

You would need to trigger a GC at every possible instruction, and mark
all unreached objects such that later attempts to access them trap.

-- Jamie

Re: GC changes

[Mike Stump]

> Date: Mon, 15 Jan 2001 12:32:34 +0000 (GMT)
> From: Bernd Schmidt <bernds@redhat.com>

> On Mon, 15 Jan 2001, Jamie Lokier wrote:

> > Mike Stump wrote:
> > > > That is not safe.  You can't predict what kind of address arithmetic
> > > > the compiler will make.  For example, strength reduction could cause
> > > > a pointer to be pointing into the middle of an array, or worse,
> > > > somewhere beyond it (incorporating some constant adjustments).
> > >
> > > We already need a switch to disable GC unfriendly optimizations.

> Which ones would that be?

-mgc-safe, -fgc-safe or something along those lines.  I don't know why
 you ask, unless someone has the patches, picking the name is
a bit  premature.

> And how can we verify that the generated code is indeed GC friendly?

When all the GC applications verify that they work 100% all the time
and they never report any bugs, we can know that the code is
reasonably GC friendly.  When the experts conditionalize all the known
optimizations on this flag, we can be obtain more comfort that it is.

``Given enough eyeballs, all bugs are shallow''
http://www.tuxedo.org/~esr/writings/cathedral-bazaar/cathedral-bazaar/ .

> If it can't be verified with a testsuite, such a switch might as
> well not be there, since it won't work in practice.

Sounds kinda defeatist to me.  The software already doesn't work in
practice, why should we bother to work on it?  Answer, because the
level that it works at today is good enough for some, and those that
work on it, only need it to work a little bit better, not perfection,
but just a tad bit better.  This is easy enough to achieve.

Also, there are tons of features in the compiler that don't have
testsuites, that work on a routine basis.  Are you saying that we
should rip out all features that haven't been put through a testsuite
in the past 30 days?

Re: GC changes

[Jamie Lokier]

dewar@gnat.com wrote:
> <<Actually there is another approach.  You could generate unwind stubs
> similar to exception handling, with a table indexed by program counter
> to the stubs.  For most program addresses the stub would be empty, but
> for certain places where only an offset address is present, the stub
> would generate the non-offset address.
> 
> This has the advantage that no optimisation is penalised.  It's quite
> complex to implement though.
> >>
> 
> Well it's a step along the route to type accurate GC, and really if you
> even contemplate going this far, you may as well go all the way.

Sometimes you don't have accurate types.  E.g. you may still want a
Boehm-style conservative GC to emulate malloc() for C programs, and the
type information in those C programs is not accurate enough for typed GC.

However I agree it would be very nice to do full type accurate GC.
_Much_ more stub code & tables though.

-- Jamie

Re: GC changes

[dewar]

<<Actually there is another approach.  You could generate unwind stubs
similar to exception handling, with a table indexed by program counter
to the stubs.  For most program addresses the stub would be empty, but
for certain places where only an offset address is present, the stub
would generate the non-offset address.

This has the advantage that no optimisation is penalised.  It's quite
complex to implement though.
>>

Well it's a step along the route to type accurate GC, and really if you
even contemplate going this far, you may as well go all the way.

Re: GC changes

[Joern Rennecke]

> TREE and RTL objects aren't accessed in arrays though, are they?

Well, for RTL, we have RTVECs.  And when we loop over them, ther might
be optimizations in the described class.

Re: GC changes

[Jamie Lokier]

Joern Rennecke wrote:
> > > 2. What is a good way to make things GC proof for a while until
> > > they get into the main tree structure? At the moment I define
> > > various roots to handle the intermediate allocations. 
> > 
> > You might try implementing conservative roots.  I think it's quite easy
> > to get access to all the pointers stored in registers and on the stack:
> > just call setjmp.  As a comment in some code says, "Callee-saved
> > registers are recorded in buf [setjmp(buf)]; caller-saved registers are
> > on the stack already.".
> 
> That is not safe.  You can't predict what kind of address arithmetic the
> compiler will make.  For example, strength reduction could cause a pointer
> to be pointing into the middle of an array, or worse, somewhere beyond it
> (incorporating some constant adjustments).

Pointers into the middle of an array aren't a problem; you can make the
GC handle that.  Pointers outside the array are a real problem with all
kinds of conservative GC, but only when the pointer into the array is
not also available.  We've had a thread here before asking for a switch
to make GCC GC-safe in this regard.

TREE and RTL objects aren't accessed in arrays though, are they?
(Arrays of pointers to them are used, but not arrays of the objects
themselves).  So I would think that in practice, address arithmetic on
these objects will not result in a pointer outside the object existing
without a pointer to or into the object.

-- Jamie

Re: GC changes

[Joern Rennecke]

> 
> Tim Josling wrote:
> > 2. What is a good way to make things GC proof for a while until
> > they get into the main tree structure? At the moment I define
> > various roots to handle the intermediate allocations. 
> 
> You might try implementing conservative roots.  I think it's quite easy
> to get access to all the pointers stored in registers and on the stack:
> just call setjmp.  As a comment in some code says, "Callee-saved
> registers are recorded in buf [setjmp(buf)]; caller-saved registers are
> on the stack already.".

That is not safe.  You can't predict what kind of address arithmetic the
compiler will make.  For example, strength reduction could cause a pointer
to be pointing into the middle of an array, or worse, somewhere beyond it
(incorporating some constant adjustments).

Re: GC changes

[Jamie Lokier]

Tim Josling wrote:
> 2. What is a good way to make things GC proof for a while until
> they get into the main tree structure? At the moment I define
> various roots to handle the intermediate allocations. 

You might try implementing conservative roots.  I think it's quite easy
to get access to all the pointers stored in registers and on the stack:
just call setjmp.  As a comment in some code says, "Callee-saved
registers are recorded in buf [setjmp(buf)]; caller-saved registers are
on the stack already.".

-- Jamie

Re: GC changes

[Geoff Keating]

> Date: Fri, 12 Jan 2001 07:34:09 +1100
> From: Tim Josling <tej@melbpc.org.au>

> Here we are building a GCable structure. Once it is all linked
> into the main trees under the roots and visible to the mark
> routines, it will not disappear during GC. But until then, it is
> vulnerable to GC, which can be triggered on any memory
> allocation. Here there seem to be several memory allocations and
> the early ones are unprotected.

I believe that at present GC is triggered only when ggc_collect() is called.

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: GC changes

[Tim Josling]

Geoff,

Hopefully you will provide good documentation on the changes. I
had a lot of unnecessary work due to the paucity of documentation
on the GC when I originally implemented it.

By the way, a question on gc...

I see a lot of code like this:

maintree->x=build_x(build_y(build_z("foo")));

Here is a real example in c-decl.c:
  array_domain_type = build_index_type (build_int_2 (200, 0));

Another:
  ptr_ftype_ptr
    = build_function_type (ptr_type_node,
                           tree_cons (NULL_TREE, ptr_type_node,
endlink));

Here we are building a GCable structure. Once it is all linked
into the main trees under the roots and visible to the mark
routines, it will not disappear during GC. But until then, it is
vulnerable to GC, which can be triggered on any memory
allocation. Here there seem to be several memory allocations and
the early ones are unprotected.

Two things:

1. Have I missed something here? If I have and it is OK this
makes life easier but I would like to understand how it works.

2. What is a good way to make things GC proof for a while until
they get into the main tree structure? At the moment I define
various roots to handle the intermediate allocations. 
  
Thanks,
Tim Josling