[gc-improv] Copy current trunk to branch

[gc-improv] Copy current trunk to branch

[Laurynas Biveinis]

I am re-using my merged gc-improv branch for my next memory management
project, which is moving RTL out of GC and, time permitting, better GC
implementation. I hope to merge it during 4.7 stage 1.

I will update svn.html#branches shortly.

$ svn cp svn+ssh://lauras@gcc.gnu.org/svn/gcc/trunk
svn+ssh://lauras@gcc.gnu.org/svn/gcc/branches/gc-improv -m "Rebase
gc-improv branch on current trunk"

Committed revision 168993.


-- 
Laurynas

Re: [gc-improv] Copy current trunk to branch

[Basile Starynkevitch]

On Wed, 19 Jan 2011 15:29:47 +0200
Laurynas Biveinis <laurynas.biveinis@gmail.com> wrote:

> I am re-using my merged gc-improv branch for my next memory management
> project, which is moving RTL out of GC and, time permitting, better GC
> implementation. I hope to merge it during 4.7 stage 1.


Could you explain more about better GC implementation ideas. I strongly hope that major data structures like Gimple, Edge, Cfg, Tree will remain garbage collected (but I also know that the current GC is a pity).

And what about C++ & GC, or simply C++ & gengtype & ggc?

Cheers.

-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mine, sont seulement les miennes} ***

Re: [gc-improv] Copy current trunk to branch

[Nathan Froyd]

On Wed, Jan 19, 2011 at 03:29:47PM +0200, Laurynas Biveinis wrote:
> I am re-using my merged gc-improv branch for my next memory management
> project, which is moving RTL out of GC and, time permitting, better GC
> implementation. I hope to merge it during 4.7 stage 1.

This is excellent!  Would you mind explaining what your plan is?

-Nathan

Re: [gc-improv] Copy current trunk to branch

[Laurynas Biveinis]

2011/1/19 Basile Starynkevitch <basile@starynkevitch.net>:
>> I am re-using my merged gc-improv branch for my next memory management
>> project, which is moving RTL out of GC and, time permitting, better GC
>> implementation. I hope to merge it during 4.7 stage 1.
>
>
> Could you explain more about better GC implementation ideas. I strongly hope that major data structures like Gimple, Edge, Cfg, Tree will remain garbage collected (but I also know that the current GC is a pity).

Besides RTL, I have no plans to move anything else out of GC.

> And what about C++ & GC, or simply C++ & gengtype & ggc?

No definite ideas here. I am going to discuss this once GCC actually
switches to C++, time permitting.

-- 
Laurynas

Re: [gc-improv] Copy current trunk to branch

[Laurynas Biveinis]

2011/1/20 Nathan Froyd <froydnj@codesourcery.com>:
> On Wed, Jan 19, 2011 at 03:29:47PM +0200, Laurynas Biveinis wrote:
>> I am re-using my merged gc-improv branch for my next memory management
>> project, which is moving RTL out of GC and, time permitting, better GC
>> implementation. I hope to merge it during 4.7 stage 1.
>
> This is excellent!  Would you mind explaining what your plan is?
>

- Move RTL back to obstacks: global, per-function, scratch, maybe a
few per-pass obstacks too. My work so far is based on Bernd Schmidt's
patch [1]. Also this will enable quite a few cleanups: in gengtype,
removal a lot of GTY markers in backends that only serve PCH.
- Merge to trunk.
- Add an object type tag to all GC allocated objects, this should be
trivial now that GC allocation is type-strict.
- Then the "normal" GC implementation techniques: incremental,
copying, generational etc. all become doable. Implement, measure
performance, merge, repeat.

Currently I do not plan to remove the limitation that collection
happens only when invoked explicitly with ggc_collect(). That would
require solving the issue of GC roots on stack in one way or another.

[1] - http://gcc.gnu.org/ml/gcc-patches/2010-08/msg00655.html

-- 
Laurynas

Re: [gc-improv] Copy current trunk to branch

[Basile Starynkevitch]

On Thu, 20 Jan 2011 06:07:45 +0200
Laurynas Biveinis <laurynas.biveinis@gmail.com> wrote:

> 2011/1/19 Basile Starynkevitch <basile@starynkevitch.net>:
> >> I am re-using my merged gc-improv branch for my next memory management
> >> project, which is moving RTL out of GC and, time permitting, better GC
> >> implementation. I hope to merge it during 4.7 stage 1.
> >
> >
> > Could you explain more about better GC implementation ideas. I strongly hope that major data structures like Gimple, Edge, Cfg, Tree will remain garbage collected (but I also know that the current GC is a pity).
> 
> Besides RTL, I have no plans to move anything else out of GC.
> 
> > And what about C++ & GC, or simply C++ & gengtype & ggc?
> 
> No definite ideas here. I am going to discuss this once GCC actually
> switches to C++, time permitting.

With C++, we could practically at last have local pointers which will be handled by the GC.

(I will explain tomorrow, have a train to catch now).

Cheers.

-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mine, sont seulement les miennes} ***

Re: [gc-improv] Copy current trunk to branch

[Laurynas Biveinis]

2011/1/20 Basile Starynkevitch <basile@starynkevitch.net>:
> With C++, we could practically at last have local pointers which will be handled by the GC.
>
> (I will explain tomorrow, have a train to catch now).

Sure, with some sort of smart pointer facility.

-- 
Laurynas

Re: [gc-improv] Copy current trunk to branch

[Laurynas Biveinis]

2011/1/19 Laurynas Biveinis <laurynas.biveinis@gmail.com>:
> $ svn cp svn+ssh://lauras@gcc.gnu.org/svn/gcc/trunk
> svn+ssh://lauras@gcc.gnu.org/svn/gcc/branches/gc-improv -m "Rebase
> gc-improv branch on current trunk"

Apparently this copying of the trunk to the branch didn't do what I
wanted it to do, so after some searching I did what Ian did for gccgo
- deleted the branch then copied.

$ svn rm svn+ssh://lauras@gcc.gnu.org/svn/gcc/branches/gc-improv -m
"Temporarily remove the branch before re-creating it"
Committed revision 169048.
$ svn cp svn+ssh://lauras@gcc.gnu.org/svn/gcc/trunk
svn+ssh://lauras@gcc.gnu.org/svn/gcc/branches/gc-improv -m "Rebase
gc-improv branch on current trunk"

Committed revision 169049.


-- 
Laurynas

Re: [gc-improv] Copy current trunk to branch

[Paolo Bonzini]

On 01/20/2011 05:18 AM, Laurynas Biveinis wrote:
> - Move RTL back to obstacks: global, per-function, scratch, maybe a
> few per-pass obstacks too. My work so far is based on Bernd Schmidt's
> patch [1]. Also this will enable quite a few cleanups: in gengtype,
> removal a lot of GTY markers in backends that only serve PCH.

Maybe we can find something better than obstacks?  There are two 
possible benefits of obstacks: space locality (i.e. hope that parts of 
an rtx are in the same cache line) and easily defined lifetimes.

If we use a different interface than obstacks for RTL allocation, we can 
try to separate the two.  For example, the primitives could be:

(1) start allocating global
(2) stop allocating global
(3) start allocating per-function
(4) discard per-function
(5) start allocating scratch
(6) discard scratch up to last call to (5)
(7) move scratch to per-function

With obstacks, (7) is not easily implemented.  The fwprop.c changes in 
Bernd's patch that emulate it, for example, are quite hard to follow and 
not very idiomatic.  A different interface could support it and at the 
same time allow us to try different backends: some examples are

- malloc

- alloc-pools

- consecutive allocation like obstacks, but allowing implementation of 
all seven items above

- GGC

My two cents,

Paolo

Re: [gc-improv] Copy current trunk to branch

[Laurynas Biveinis]

2011/1/20 Paolo Bonzini <bonzini@gnu.org>:
>> - Move RTL back to obstacks: global, per-function, scratch, maybe a
>> few per-pass obstacks too. My work so far is based on Bernd Schmidt's
>> patch [1]. Also this will enable quite a few cleanups: in gengtype,
>> removal a lot of GTY markers in backends that only serve PCH.
>
> Maybe we can find something better than obstacks?  There are two possible
> benefits of obstacks: space locality (i.e. hope that parts of an rtx are in
> the same cache line) and easily defined lifetimes.

I agree.

> If we use a different interface than obstacks for RTL allocation, we can try
> to separate the two.  For example, the primitives could be:
>
> (1) start allocating global
[...]
> (7) move scratch to per-function

> With obstacks, (7) is not easily implemented.  The fwprop.c changes in
> Bernd's patch that emulate it, for example, are quite hard to follow and not
> very idiomatic.  A different interface could support it and at the same time
> allow us to try different backends: some examples are [...]

I agree that defining such allocation interface is a good idea. I also
think that with obstacks (1)-(6) abstract very easily and (7) is
doable. So I will introduce an abstraction layer here.

-- 
Laurynas

Re: [gc-improv] Copy current trunk to branch

[Paolo Bonzini]

On 01/20/2011 11:01 AM, Laurynas Biveinis wrote:
> I also think that with obstacks (1)-(6) abstract very easily and (7)
> is doable.

You're right, (7) as I defined it is a nop with obstacks.  You can just 
have two obstacks (per-function and per-function-scratch) and free both 
of them when you discard the per-function memory.

The same trick can be applied basically for all backends since they also 
need to use some kind of stack; I'd still leave it in the abstraction 
layer, if only for documentation purposes.

Paolo

Re: [gc-improv] Copy current trunk to branch

[Richard Kenner]

> - Move RTL back to obstacks: global, per-function, scratch, maybe a
> few per-pass obstacks too. 

What are you planning on doing about combine.c?  It generates and throws
away lots of RTL.  Are you going back to the original implementation?

Re: [gc-improv] Copy current trunk to branch

[NightStrike]

On Thu, Jan 20, 2011 at 1:10 AM, Laurynas Biveinis
<laurynas.biveinis@gmail.com> wrote:
> 2011/1/19 Laurynas Biveinis <laurynas.biveinis@gmail.com>:
>> $ svn cp svn+ssh://lauras@gcc.gnu.org/svn/gcc/trunk
>> svn+ssh://lauras@gcc.gnu.org/svn/gcc/branches/gc-improv -m "Rebase
>> gc-improv branch on current trunk"
>
> Apparently this copying of the trunk to the branch didn't do what I
> wanted it to do, so after some searching I did what Ian did for gccgo
> - deleted the branch then copied.
>
> $ svn rm svn+ssh://lauras@gcc.gnu.org/svn/gcc/branches/gc-improv -m
> "Temporarily remove the branch before re-creating it"
> Committed revision 169048.
> $ svn cp svn+ssh://lauras@gcc.gnu.org/svn/gcc/trunk
> svn+ssh://lauras@gcc.gnu.org/svn/gcc/branches/gc-improv -m "Rebase
> gc-improv branch on current trunk"
>
> Committed revision 169049.
>
>
> --
> Laurynas
>

For reference:

"In Subversion 1.5, once a --reintegrate merge is done from branch to
trunk, the branch is no longer usable for further work. It's not able
to correctly absorb new trunk changes, nor can it be properly
reintegrated to trunk again. For this reason, if you want to keep
working on your feature branch, we recommend destroying it and then
re-creating it from the trunk:"

Bottom of this section:
http://svnbook.red-bean.com/en/1.5/svn.branchmerge.basicmerging.html#svn.branchemerge.basicmerging.stayinsync

Now in the 1.6 version, the text later on describes how to actually do
it if you really wanted to:
http://svnbook.red-bean.com/nightly/en/svn.branchmerge.advanced.html#svn.branchmerge.advanced.reintegratetwice

Re: [gc-improv] Copy current trunk to branch

[Laurynas Biveinis]

2011/1/20 Richard Kenner <kenner@vlsi1.ultra.nyu.edu>:
>> - Move RTL back to obstacks: global, per-function, scratch, maybe a
>> few per-pass obstacks too.
>
> What are you planning on doing about combine.c?  It generates and throws
> away lots of RTL.  Are you going back to the original implementation?

The plan is to start using scratch allocation at the start of
try_combine, discard everything at try_combine failure (undo_all
call). On success promote lifetime. I haven't reached combine.c yet,
so of course this is still not a very informed plan at this point.

I don't know what the original implementation was.

-- 
Laurynas

Re: [gc-improv] Copy current trunk to branch

[Laurynas Biveinis]

2011/1/20 NightStrike <nightstrike@gmail.com>:
> Bottom of this section:
> http://svnbook.red-bean.com/en/1.5/svn.branchmerge.basicmerging.html#svn.branchemerge.basicmerging.stayinsync
>
> Now in the 1.6 version, the text later on describes how to actually do
> it if you really wanted to:
> http://svnbook.red-bean.com/nightly/en/svn.branchmerge.advanced.html#svn.branchmerge.advanced.reintegratetwice

Thanks for the pointers. I have updated
http://gcc.gnu.org/wiki/SvnMerge for future.

-- 
Laurynas

Re: [gc-improv] Copy current trunk to branch

[Richard Kenner]

> The plan is to start using scratch allocation at the start of
> try_combine, discard everything at try_combine failure (undo_all
> call). On success promote lifetime. I haven't reached combine.c yet,
> so of course this is still not a very informed plan at this point.
> 
> I don't know what the original implementation was.

Pretty close to the above.  If I recall correctly, there was a way to
mark a position in an obstack and roll back to it.  It was marked at the
start of combine and rolled back on a failure.  If there was a success,
then the new allocations were made permanent.

Re: [gc-improv] Copy current trunk to branch

[Basile Starynkevitch]

On Thu, 20 Jan 2011 06:18:43 +0200
Laurynas Biveinis <laurynas.biveinis@gmail.com> wrote:
> 
> Currently I do not plan to remove the limitation that collection
> happens only when invoked explicitly with ggc_collect(). That would
> require solving the issue of GC roots on stack in one way or another.

In practical terms, C++ and perhaps a new feature of gengtype could help on that. And I believe that local GC-ed pointer is a major feature to add into GCC. (FYI, MELT has it since its very start; the MELT runtime is mostly a copying GC able to handle local MELT values on the stack).

Also, local GC variables will in practice -hopefully- change the mind of people, since it is the best way to illustrate that a good GC (better than current gengtype+ggc implementation) is useful inside a compiler. But that is a holy grail...

And C++ (with probably the help of gengtype) should really help. I suspect that we could without huge pain improve gengtype & ggc with what you might call a smart pointer class so that declaring a local pointer p to a C++ garbaged class -hypothetically Gimple- could become as simple 
   GTYLOC(Gimple*) p;

and then gengtype & C++ template magic will do the tricks

Regards.
-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mine, sont seulement les miennes} ***

Re: [gc-improv] Copy current trunk to branch

[Bernd Schmidt]

On 01/20/2011 05:18 AM, Laurynas Biveinis wrote:

> - Move RTL back to obstacks: global, per-function, scratch, maybe a
> few per-pass obstacks too. My work so far is based on Bernd Schmidt's
> patch [1].

Whee. Thanks for picking this up.


Bernd