Work on gc-improv branch

Work on gc-improv branch

[Laurynas Biveinis]

Hi all,

I saw that folks on IRC were wondering about branch commits that were
not posted to gcc-patches. I was planning to emerge from stealth mode
once the branch had something that could be useful for trunk, but
since there is interest I will post status and plans now.

Right now there are three things ongoing on gc-improv branch:

1) Stop abusing current GC by allocating structures there that GC
knows nothing about, i.e. there is never a path from GC roots to any
variables of that type and so gengtype does not produce markers it.
With current GC implementation, doing such allocation has an effect of
doing scratch allocation because it will get collected on next
ggc_collect. Which means: 1) you have to be careful where you put your
ggc_collect calls (quite nasty IMHO) 2) the lifetime of such objects
is usually very clear, so they should be in some obstack or pool,
hopefully increasing data access locality as well.
So I am moving such data from GC memory to obstacks. IMHO this is
immediately useful for trunk too and so I will post patches as soon as
I am done with them.
BTW, it does not deal with types that in some instances have variables
allocated in proper GC way (with a path from GC root) and in some
instances not. Fixing these is going to be hard.

2) Make GC allocation interface aware of types it allocates. This
means replacing
foo * x = ggc_alloc (sizeof (foo))
to
foo * x = ggc_alloc_foo();
and patching gengtype to produce all those ggc_alloc_foo() allocators,
also with options for cleared, vector, and variable size type
allocation and with some kludges for splay trees where allocator has
to be passed as a callback.

This is a prerequisite for my future GC plans of advanced GC
implementation that will need to know type of object given its
address. Also it has a nice side effect of enforcing that GC is used
only with types that it knows something about (see 1) above).

I'd love to see this merged to trunk in near future too but I expect
that right now it would be seen as an arbitrary and annoying change by
developers, especially since nothing in GC implementation right now
makes use of it.

3) gengtype type information dump support, extremely useful for
gengtype debugging IMHO. I already posted it on August 2nd but
surprisingly I cannot find it in archives, so I will repost it in a
moment.

Also, on IRC someone mentioned the project of using Boehm's GC as a GC
implementation for GCC proper. That was mostly done three years ago in
my GSoC project. The status of it was that simple drop-in replacement
without any tuning resulted in about one third slower GC. With
simple-to-intermediate tuning I was able to get it to roughly the same
speed as ggc-page but slightly worse memory usage. There was room for
some advanced tuning and I have tried to take advantage of Boehm's GC
custom marker support. And got stuck there.

Any feedback is most welcome,
-- 
Laurynas

Re: Work on gc-improv branch

[Paolo Bonzini]

> 1) Stop abusing current GC by allocating structures there that GC
> knows nothing about, i.e. there is never a path from GC roots to any
> variables of that type and so gengtype does not produce markers it.

That's good.

> BTW, it does not deal with types that in some instances have variables
> allocated in proper GC way (with a path from GC root) and in some
> instances not. Fixing these is going to be hard.

Do you have some examples?

> This is a prerequisite for my future GC plans of advanced GC
> implementation that will need to know type of object given its
> address. Also it has a nice side effect of enforcing that GC is used
> only with types that it knows something about (see 1) above).

Makes a lot of sense.

> I'd love to see this merged to trunk in near future too but I expect
> that right now it would be seen as an arbitrary and annoying change by
> developers, especially since nothing in GC implementation right now
> makes use of it.

Actually, now is a perfect time to do it (more precisely, after LTO is 
merged and before people start hacking on branches for 4.6).  The only 
really active branch now is trans-mem.

Paolo

Re: Work on gc-improv branch

[Laurynas Biveinis]

>> BTW, it does not deal with types that in some instances have variables
>> allocated in proper GC way (with a path from GC root) and in some
>> instances not. Fixing these is going to be hard.
>
> Do you have some examples?

Trees and rtxes mostly. I haven't got around to taking a closer look,
but for example folders love allocating temporary trees. For example,
in tree-ssa-ccp.c:fold_gimple_assign,

	    if (COMPARISON_CLASS_P (op0))
	      {
		fold_defer_overflow_warnings ();
		tem = fold_binary_loc (cond_loc,
				   TREE_CODE (op0), TREE_TYPE (op0),
				   TREE_OPERAND (op0, 0),
				   TREE_OPERAND (op0, 1));
		/* This is actually a conditional expression, not a GIMPLE
		   conditional statement, however, the valid_gimple_rhs_p
		   test still applies.  */
		set = (tem && is_gimple_condexpr (tem)
		       && valid_gimple_rhs_p (tem));
		fold_undefer_overflow_warnings (set, stmt, 0);
	      }

Here tem should not be allocated on GC memory.

>> I'd love to see this merged to trunk in near future too but I expect
>> that right now it would be seen as an arbitrary and annoying change by
>> developers, especially since nothing in GC implementation right now
>> makes use of it.
>
> Actually, now is a perfect time to do it (more precisely, after LTO is
> merged and before people start hacking on branches for 4.6).  The only
> really active branch now is trans-mem.

In any case I am not done with it right now and it remains to be seen
if I can make it during current stage 1...

Thanks,
-- 
Laurynas

Re: Work on gc-improv branch

[Paolo Bonzini]

On 08/21/2009 10:52 AM, Laurynas Biveinis wrote:
> Trees and rtxes mostly. I haven't got around to taking a closer look,
> but for example folders love allocating temporary trees. For example,
> in tree-ssa-ccp.c:fold_gimple_assign,
>
> 	    if (COMPARISON_CLASS_P (op0))
> 	      {
> 		fold_defer_overflow_warnings ();
> 		tem = fold_binary_loc (cond_loc,
> 				   TREE_CODE (op0), TREE_TYPE (op0),
> 				   TREE_OPERAND (op0, 0),
> 				   TREE_OPERAND (op0, 1));
> 		/* This is actually a conditional expression, not a GIMPLE
> 		   conditional statement, however, the valid_gimple_rhs_p
> 		   test still applies.  */
> 		set = (tem&&  is_gimple_condexpr (tem)
> 		&&  valid_gimple_rhs_p (tem));
> 		fold_undefer_overflow_warnings (set, stmt, 0);
> 	      }
>
> Here tem should not be allocated on GC memory.

I disagree, as this would not apply to tem only but also to anything 
allocated to fold it.  This is not going to be maintainable (what if 
fold create temporary types, which need to be in GC memory definitely?).

Not having to deal with the lifetime of "temporary" stuff is part of 
having a GC, isn't it?

At most, you may want to add more ggc_free calls, but I don't think this 
is necessary either.  Actually, it would anyway miss any trees that are 
not toplevel and are created by the call to fold_binary_loc, so it would 
even be wrong in some sense.

Paolo

Re: Work on gc-improv branch

[Steven Bosscher]

On Fri, Aug 21, 2009 at 10:52 AM, Laurynas
Biveinis<laurynas.biveinis@gmail.com> wrote:
>>> BTW, it does not deal with types that in some instances have variables
>>> allocated in proper GC way (with a path from GC root) and in some
>>> instances not. Fixing these is going to be hard.
>>
>> Do you have some examples?
>
> Trees and rtxes mostly.

Not to discourage you, but, eh... -- wouldn't it be a much more useful
project to move RTL out of GC space completely instead of improving GC
for rtxes?  The life time of RTL is pretty well defined by now and
much of the unwieldly GC / GTY (and, in fact PCH) code would go away
if RTL would just live on obstacks again.

(See for example all the GTY markers in the back ends.  Most of them
are there only for PCH to get a consistent memory snap-shot, but PCHs
should be written out before any RTL is generated...)

Ciao!
Steven

Re: Work on gc-improv branch

[Laurynas Biveinis]

2009/8/21 Paolo Bonzini <bonzini@gnu.org>:
>> Here tem should not be allocated on GC memory.
>
> I disagree, as this would not apply to tem only but also to anything
> allocated to fold it.  This is not going to be maintainable (what if fold
> create temporary types, which need to be in GC memory definitely?).

I see. I never investigated what is going on here in detail. If tem
were allocated in some obstack, I wouldn't see a problem with
allocating its subparts in the obstack too. However I know nothing
about those temp types that definitely should be in GC memory. Maybe I
will come up with something once I investigate this thoroughly. Maybe
this really has to stay as it is.

> Not having to deal with the lifetime of "temporary" stuff is part of having
> a GC, isn't it?

Yes - if you don't know the lifetime or if the lifetime varies. If
stuff has a fixed and short lifetime, then I guess non-GC allocation
is the best for it. Of course the goal is to have as simple and as
maintainable code as possible.

Maybe http://gcc.gnu.org/wiki/Memory_management needs some updates.

> At most, you may want to add more ggc_free calls, but I don't think this is
> necessary either.

I agree.

Anyway, right now I am not planning to see what can be done about
those types that are sometimes allocated in "a proper GC way" and
sometimes for scratch only. For the time being, I am working only on
those types that are allocated in GC while GC knows nothing about
them.

-- 
Laurynas

Re: Work on gc-improv branch

[Laurynas Biveinis]

2009/8/21 Steven Bosscher <stevenb.gcc@gmail.com>:
> Not to discourage you, but, eh... --

On the contrary, I think this is a very interesting idea.

> wouldn't it be a much more useful
> project to move RTL out of GC space completely instead of improving GC
> for rtxes?  The life time of RTL is pretty well defined by now and

I will take a look at this. I am not too familiar with RTL passes though.

> much of the unwieldly GC / GTY (and, in fact PCH) code would go away
> if RTL would just live on obstacks again.

Actually, unless I am missing something, there is not so much code in
GC/GTY that it is there only because of RTL. The annoying features of
RTL that require special care from gengtype, for example, are mostly
shared with trees too.

> (See for example all the GTY markers in the back ends.  Most of them
> are there only for PCH to get a consistent memory snap-shot, but PCHs
> should be written out before any RTL is generated...)

Noted.

-- 
Laurynas

Re: Work on gc-improv branch

[Daniel Berlin]

On Fri, Aug 21, 2009 at 5:37 AM, Steven Bosscher<stevenb.gcc@gmail.com> wrote:
> On Fri, Aug 21, 2009 at 10:52 AM, Laurynas
> Biveinis<laurynas.biveinis@gmail.com> wrote:
>>>> BTW, it does not deal with types that in some instances have variables
>>>> allocated in proper GC way (with a path from GC root) and in some
>>>> instances not. Fixing these is going to be hard.
>>>
>>> Do you have some examples?
>>
>> Trees and rtxes mostly.
>
> Not to discourage you, but, eh... -- wouldn't it be a much more useful
> project to move RTL out of GC space completely instead of improving GC
> for rtxes?  The life time of RTL is pretty well defined by now and
> much of the unwieldly GC / GTY (and, in fact PCH) code would go away
> if RTL would just live on obstacks again.
>

One problem with obstacks was that it didn't allow freeing of stuff in
the middle, so the high watermark for passes could be quite high
unless you used many obstacks.
It would be trivial to make an arena-style allocator that took care of
this problem, however.