df.c and partial writes/REG_EQUAL notes

df.c and partial writes/REG_EQUAL notes

[Jan Hubicka]

Hi,
yesterday I wanted to make myself familiar with the dataflow module and write
simple code to construct webs early and split each pseudo consisting of multiple
webs to assist CSE and other optimizations.  What I am shooting for is to replace
some of logic of unroll.c to make it more rewritable for CFG.  For instance code like
*a++=0;
*a++=0;
*a++=0;
*a++=0;
*a++=0;
Will currently use 5 increments, but if the various copies of A are split, the
CSE/combine takes care to construct multiple moves.

Problem 1
=========

I've run into problems with dataflow analyzis and partial writes.  For instance following
code:

1: (set (reg:DI x) (const_int 0))

2: (set (subreg:SI (reg:DI x) 0) (const_int 1))

3: (use somewhere reg:DI x)

As currently impleemnted in df.c, there will be no depdendancy between insn 1 and insn 3,
as the store in insn 2 is believed to kill whole value of X.
The semantic of insn 2 is to overwruite just first word of the value so the insn 3 uses
values of both instructions.

I am attaching an work-in-progress patch, that changes the behaviour to represent the
depdendancy between insn 1 and insn 2 and mark the definition in insn 2 as read/write,
as well as the use in insn 2, so my web code can realize the fact that the register
must be equal and I can merge webs for X in insns 1-2 and X in insns 2-3 otherwise
disjunct.

In same way I get read/write for strict_low_part

There are number of hacks around the code, as I understand designed to cooperate somehow
with register allocator, but I am not 100% sure how.  Would be the approach described good
enought?

Alternativly we may want to make dataflow more smart and realize that insn 2 does not
use value of insn 1, but insn 3 uses both, but I am not quite sure it is wortwhile,
as pass who wants to be aware of this should also know that insn 1 can't be placed
after insn 2, even when the insn 2 does not use the value nor does kill the value
defined by insn 1.

What do you think is the most suitable behaviour?

Problem 2
=========

Another problem I've run into are the REG_EQUAL/EQUIV notes.  Currently dataflow
ignores them, but attempts to update them when register is replaced, but this is quite
wrong, as the insn may not mention the register in the pattern, but still may contain
it in the REG_EQUIV note.  This is common in libcall sequences and similar stuff.

I've added an option to build dataflow with REG_EQUIV/EQUAL notes reprezented as
ordinally uses.

Does that sound sane?
With my new "flags" field I've introduced for the problem 1, I can even mark them,
so the eventual passes may ignore them in some cases - does that make sense for
register allocator (as it is probably only one who will do so).

I am attaching the patch as well as the webizer code, both kind of work-in-progress.

Honza

Re: df.c and partial writes/REG_EQUAL notes

[Daniel Berlin]

On Tuesday, September 25, 2001, at 10:16  AM, Jan Hubicka wrote:

> Hi,
> yesterday I wanted to make myself familiar with the dataflow module and 
> write
> simple code to construct webs early and split each pseudo consisting of 
> multiple
> webs to assist CSE and other optimizations.  What I am shooting for is 
> to replace
> some of logic of unroll.c to make it more rewritable for CFG.  For 
> instance code like
> *a++=0;
> *a++=0;
> *a++=0;
> *a++=0;
> *a++=0;
> Will currently use 5 increments, but if the various copies of A are 
> split, the
> CSE/combine takes care to construct multiple moves.
>
> Problem 1
> =========
>
> I've run into problems with dataflow analyzis and partial writes.  For 
> instance following
> code:
>
> 1: (set (reg:DI x) (const_int 0))
>
> 2: (set (subreg:SI (reg:DI x) 0) (const_int 1))
>
> 3: (use somewhere reg:DI x)
>
> As currently impleemnted in df.c, there will be no depdendancy between 
> insn 1 and insn 3,
> as the store in insn 2 is believed to kill whole value of X.
> The semantic of insn 2 is to overwruite just first word of the value so 
> the insn 3 uses
> values of both instructions.
>
> I am attaching an work-in-progress patch, that changes the behaviour to 
> represent the
> depdendancy between insn 1 and insn 2 and mark the definition in insn 2 
> as read/write,
> as well as the use in insn 2, so my web code can realize the fact that 
> the register
> must be equal and I can merge webs for X in insns 1-2 and X in insns 
> 2-3 otherwise
> disjunct.
>
> In same way I get read/write for strict_low_part
>
> There are number of hacks around the code, as I understand designed to 
> cooperate somehow
> with register allocator, but I am not 100% sure how.

Don't worry about the interactions, as the register allocator branch
A. has it's own version of df.c
B. only uses df.c for reg defs and uses.  All dataflow is done without 
df.c routines, because Michael doesn't want to use global liveness.

I.E. It only cares about noticing all of the reg defs and uses, it 
doesn't care whether df.c really knows what they do.


>   Would be the approach described good
> enought?

> Alternativly we may want to make dataflow more smart and realize that 
> insn 2 does not
> use value of insn 1, but insn 3 uses both, but I am not quite sure it 
> is wortwhile,
> as pass who wants to be aware of this should also know that insn 1 
> can't be placed
> after insn 2, even when the insn 2 does not use the value nor does kill 
> the value
> defined by insn 1.
>
> What do you think is the most suitable behaviour?
>
> Problem 2
> =========
>
> Another problem I've run into are the REG_EQUAL/EQUIV notes.  Currently 
> dataflow
> ignores them, but attempts to update them when register is replaced, 
> but this is quite
> wrong, as the insn may not mention the register in the pattern, but 
> still may contain
> it in the REG_EQUIV note.  This is common in libcall sequences and 
> similar stuff.
>
> I've added an option to build dataflow with REG_EQUIV/EQUAL notes 
> reprezented as
> ordinally uses.
>
> Does that sound sane?
> With my new "flags" field I've introduced for the problem 1, I can even 
> mark them,
> so the eventual passes may ignore them in some cases - does that make 
> sense for
> register allocator (as it is probably only one who will do so).
>
> I am attaching the patch as well as the webizer code, both kind of 
> work-in-progress.
>
> Honza
>

Re: df.c and partial writes/REG_EQUAL notes

[Jan Hubicka]

> 
> Don't worry about the interactions, as the register allocator branch
> A. has it's own version of df.c

But once you will attempt to merge allocator in, you probably would not want
to have df1.c and df2.c right?

> B. only uses df.c for reg defs and uses.  All dataflow is done without 
> df.c routines, because Michael doesn't want to use global liveness.

As I've described, it misses one use at least, that should affect the reg-alloc
branch too.

What exactly do you mean by global liveness?
If you do some extra analyzis, you should make as much of the as possible available
to other passes - we already do have too many stuff doing analyzis "just for myself"
> 
> I.E. It only cares about noticing all of the reg defs and uses, it 
> doesn't care whether df.c really knows what they do.
My web code too..

Honza
> 
> 
> >  Would be the approach described good
> >enought?
> 
> >Alternativly we may want to make dataflow more smart and realize that 
> >insn 2 does not
> >use value of insn 1, but insn 3 uses both, but I am not quite sure it 
> >is wortwhile,
> >as pass who wants to be aware of this should also know that insn 1 
> >can't be placed
> >after insn 2, even when the insn 2 does not use the value nor does kill 
> >the value
> >defined by insn 1.
> >
> >What do you think is the most suitable behaviour?
> >
> >Problem 2
> >=========
> >
> >Another problem I've run into are the REG_EQUAL/EQUIV notes.  Currently 
> >dataflow
> >ignores them, but attempts to update them when register is replaced, 
> >but this is quite
> >wrong, as the insn may not mention the register in the pattern, but 
> >still may contain
> >it in the REG_EQUIV note.  This is common in libcall sequences and 
> >similar stuff.
> >
> >I've added an option to build dataflow with REG_EQUIV/EQUAL notes 
> >reprezented as
> >ordinally uses.
> >
> >Does that sound sane?
> >With my new "flags" field I've introduced for the problem 1, I can even 
> >mark them,
> >so the eventual passes may ignore them in some cases - does that make 
> >sense for
> >register allocator (as it is probably only one who will do so).
> >
> >I am attaching the patch as well as the webizer code, both kind of 
> >work-in-progress.
> >
> >Honza
> >

Re: df.c and partial writes/REG_EQUAL notes

[Daniel Berlin]

On Tuesday, September 25, 2001, at 10:59  AM, Jan Hubicka wrote:

>>
>> Don't worry about the interactions, as the register allocator branch
>> A. has it's own version of df.c
>
> But once you will attempt to merge allocator in, you probably would not 
> want
> to have df1.c and df2.c right?
Yeah, but you shouldn't have to worry about the new-register allocator 
when working on the mainline. Currently, df.c on the new-regalloc branch 
and the mainline are in sync.
I do merges often enough to keep this true.  So if you break something, 
we'll just fix the allocator (assuming that's what is doing the wrong 
thing).

>
>> B. only uses df.c for reg defs and uses.  All dataflow is done without
>> df.c routines, because Michael doesn't want to use global liveness.
>
> As I've described, it misses one use at least, that should affect the 
> reg-alloc
> branch too.
>
> What exactly do you mean by global liveness?

> If you do some extra analyzis, you should make as much of the as 
> possible available
> to other passes - we already do have too many stuff doing analyzis 
> "just for myself"
Don't look at meef, I tried this argument on Michael, and it didn't work.
I don't like it either.
>>
>> I.E. It only cares about noticing all of the reg defs and uses, it
>> doesn't care whether df.c really knows what they do.
> My web code too..
Yeah.
Your web code must be pretty slow on large test cases, since my ebitmap 
patch *still* hasn't been reviewed.

>
> Honza

Re: df.c and partial writes/REG_EQUAL notes

[Jan Hubicka]

> 
> On Tuesday, September 25, 2001, at 10:59  AM, Jan Hubicka wrote:
> 
> >>
> >>Don't worry about the interactions, as the register allocator branch
> >>A. has it's own version of df.c
> >
> >But once you will attempt to merge allocator in, you probably would not 
> >want
> >to have df1.c and df2.c right?
> Yeah, but you shouldn't have to worry about the new-register allocator 
> when working on the mainline. Currently, df.c on the new-regalloc branch 
> and the mainline are in sync.
> I do merges often enough to keep this true.  So if you break something, 
> we'll just fix the allocator (assuming that's what is doing the wrong 
> thing).
OK,
I just wanted to ensyre that the idea of read/write entries is compatible with
the regalloc design, so it is not side step or that someone won't come with better
idea.

I will clean it up and try to submit today.

Honza

Re: df.c and partial writes/REG_EQUAL notes

[Richard Henderson]

On Tue, Sep 25, 2001 at 11:32:40AM -0400, Daniel Berlin wrote:
> Your web code must be pretty slow on large test cases, since my ebitmap 
> patch *still* hasn't been reviewed.

Um, no, it *has* been reviewed.  I told you how I wanted
it changed.


r~

Re: df.c and partial writes/REG_EQUAL notes

[Daniel Berlin]

Richard Henderson <rth@redhat.com> writes:

> On Tue, Sep 25, 2001 at 11:32:40AM -0400, Daniel Berlin wrote:
> > Your web code must be pretty slow on large test cases, since my ebitmap 
>> patch *still* hasn't been reviewed.
>
> Um, no, it *has* been reviewed.  I told you how I wanted
> it changed.
>
Ah, yes.
You want no more than 2 bitmap implementations in the compiler,
and want it replaced all at once, which is another questionable idea.

This was your "review".

>
> r~

-- 
"When I was five years old I was on a merry go round.  There was
a gunshot nearby.  The horses stampeded.  There I was running
down the street on a purple wooden horse.
"-Steven Wright

Re: df.c and partial writes/REG_EQUAL notes

[Gerald Pfeifer]

On Thu, 27 Sep 2001, Daniel Berlin wrote:
> You want no more than 2 bitmap implementations in the compiler,
> and want it replaced all at once, which is another questionable idea.
>
> This was your "review".

Please.  As a user and co-developer (even though I mostly do web pages,
not optimizations) I'd really like to see GCC improve.

And your (Daniel's, RTH's, Jan's,...) work all has the same common goal.

Not all of us agree all of the time, whether on technical or procedural
grounds, but please let's not forget that overall goal and let's try
working *together*.


I'd really like to see you/Daniel's improvements that you/he mentioned
when we discussed the inlining issue (and that has the potential to
greatly help code like the one I'm working on in my day job) become
part of GCC.

I hope this bitmap issue doesn't become a stumbling stone on our way
towards our common goal of improving GCC.

Gerald

Re: df.c and partial writes/REG_EQUAL notes

[Jan Hubicka]

> Richard Henderson <rth@redhat.com> writes:
> 
> > On Tue, Sep 25, 2001 at 11:32:40AM -0400, Daniel Berlin wrote:
> > > Your web code must be pretty slow on large test cases, since my ebitmap 
> >> patch *still* hasn't been reviewed.
> >
> > Um, no, it *has* been reviewed.  I told you how I wanted
> > it changed.
> >
> Ah, yes.
> You want no more than 2 bitmap implementations in the compiler,
> and want it replaced all at once, which is another questionable idea.
It IMO makes sense.
As the current bitmap can have advantage possibly only in extremly large and
sparse bitmaps we don't have currently (and that should be better handled by
tripple indirection or more fiting underlying datastructure than linked lists
are) and most of users to my best knowledge will benefit from the
implementation, it is wortwhile to do it.  All our bitmpas I am aware of are
maximally quadratic (regsXinstructions) or so, that should be always small
enought for ebitmap implementation.

Or do I miss something important?

In case you don't have motivation to do the step, I may try next week, as
working (and fast) dataflow is good and bitmap.c is one of top CPU hogs of
current compiler and we really need to get dataflow module working and used.
> 
> This was your "review".
Please lets work together to get gcc better, not fight.

Honza
> 
> >
> > r~
> 
> -- 
> "When I was five years old I was on a merry go round.  There was
> a gunshot nearby.  The horses stampeded.  There I was running
> down the street on a purple wooden horse.
> "-Steven Wright

Re: df.c and partial writes/REG_EQUAL notes

[Daniel Berlin]

Gerald Pfeifer <pfeifer@dbai.tuwien.ac.at> writes:

> On Thu, 27 Sep 2001, Daniel Berlin wrote:
> > You want no more than 2 bitmap implementations in the compiler,
>> and want it replaced all at once, which is another questionable idea.
>>
>> This was your "review".
>
> Please.  As a user and co-developer (even though I mostly do web pages,
> not optimizations) I'd really like to see GCC improve.
>
> And your (Daniel's, RTH's, Jan's,...) work all has the same common goal.
>
> Not all of us agree all of the time, whether on technical or procedural
> grounds, but please let's not forget that overall goal and let's try
> working *together*.

I disagree that his approach is the correct one, that is all.
I also disagree that he really provided a review of the patch.  As others
have pointed out in private mail, it lacked some documentation.
Had he really provided a review of the patch, I would know this,and
also would have a good idea what would
probably be necessary  to make it acceptable to someone else who also
felt richard's approach is incorrect (of which there are a few).
In other words, his review was in no way helpful to making the patch
better.
Saying "I don't think we need 3  bitmap implemenations" is not a
review of a patch.
It is a statement of his opinion on a related issue.
Same with "I will take your work and fashion it into a replacement for
bitmap.c some day".

Overall direction and whatnot of the compiler is not controlled by
richard, it's controlled by the steering committee.

The above was not written in spite, or sarcasticly.
I'm simply stating what he claims was a review of the patch, which i
respectfully disagree it was.
He commented on no specific part of the patch.
--Dan

>
>
> I'd really like to see you/Daniel's improvements that you/he mentioned
> when we discussed the inlining issue (and that has the potential to
> greatly help code like the one I'm working on in my day job) become
> part of GCC.
>
> I hope this bitmap issue doesn't become a stumbling stone on our way
> towards our common goal of improving GCC.
>
> Gerald

-- 
"I decided to leave and go to California, so I packed up my
Salvador Dali print of two blindfolded dental hygienists trying
to make a circle on an Etch-a-Sketch, and I headed for the
highway and began hitching.  Within three minutes I got picked
up by one of those huge trailer trucks carrying 20 brand new
cars.  I climbed up the side of the cab and opened the door.
The guy said, "I don't have much room up here, why don't you get
into one of the cars out back."  So I did.  And he was really
into picking people up because he picked up 19 more.  We all had
our own cars.  Then he went 90 miles per hour and we all got
speeding tickets.
"-Steven Wright

Re: df.c and partial writes/REG_EQUAL notes

[Daniel Berlin]

Jan Hubicka <jh@suse.cz> writes:

>> Richard Henderson <rth@redhat.com> writes:
>> 
>> > On Tue, Sep 25, 2001 at 11:32:40AM -0400, Daniel Berlin wrote:
>> > > Your web code must be pretty slow on large test cases, since my ebitmap 
>> >> patch *still* hasn't been reviewed.
>> >
>> > Um, no, it *has* been reviewed.  I told you how I wanted
>> > it changed.
>> >
>> Ah, yes.
>> You want no more than 2 bitmap implementations in the compiler,
>> and want it replaced all at once, which is another questionable idea.
> It IMO makes sense.
> As the current bitmap can have advantage possibly only in extremly large and
> sparse bitmaps we don't have currently (and that should be better handled by
> tripple indirection or more fiting underlying datastructure than linked lists
> are) and most of users to my best knowledge will benefit from the
> implementation, it is wortwhile to do it.  All our bitmpas I am aware of are
> maximally quadratic (regsXinstructions) or so, that should be always small
> enought for ebitmap implementation.
>
> Or do I miss something important?
That making a change that affects basically every single part of the
compiler, wholesale, is generally a bad idea to do in one single step,
since it makes it harder to track down where the real problem is.
In this case, having *done* it, I can say this was definitely true.

>
> In case you don't have motivation to do the step, I may try next week, as
> working (and fast) dataflow is good and bitmap.c is one of top CPU hogs of
> current compiler and we really need to get dataflow module working
> and used.

Don't bother, i already did it.
You'll note that reload makes too many bitmaps, and the 16-24 bytes
more overhead + the empty array pointers that the ebitmap takes causes
100-150 meg more memory.
Just another point that we shouldn't up and replace them wholesale,
rather do it incrementally.

I have resolved this problem by reworking the internals to
not need to store empty words at all (ie not even pointers to them).

I also replaced bitmaps with them already.  The new internal storage
mechanism requires changes to sbitmaps so you can properly
and/or/copy/etc bitmaps of differing bit sizes.
I.E. it'll do the right thing, as long as the destination is big
enough to hold the right result. sbitmap_a_or_b (350 bit sbitmap, 25
bit sbitmap, 200 bit sbitmap) will work properly.
It would and/or/etc random memory before.

However, experience in doing this just helps prove my point. I tried
doing it all at once, and it made finding the real cause of the bugs
impossible.

> > 
>> This was your "review".
> Please lets work together to get gcc better, not fight.
Who is fighting?
I put review in quotes because i do not believe he reviewed the patch
itself, as i stated in my message to Gerald.

I should also note that there was a bug in ebitmap.h in
EXECUTE_IF_SET_IN_EBITMAP that a meaningful review of the patch would
have caught. 

>
> Honza
> > 
>> >
>> > r~
>> 
>> -- 
>> "When I was five years old I was on a merry go round.  There was
>> a gunshot nearby.  The horses stampeded.  There I was running
>> down the street on a purple wooden horse.
>> "-Steven Wright

-- 
"Last time I went skiing, I had to get up at 5:00 in the morning.
I knew I couldn't do that, so I slept with my skis on.  My ride
came at 5:30 in the morning, couldn't wake me up so he carried
me out of the house, put my skis on the roof rack of the car,
and drove to the mountain.  Seventeen miles later, I woke up out
of this incredibly bizarre dream that I was skydiving
horizontally.  I'm sure this has happened to you.
"-Steven Wright

Re: df.c and partial writes/REG_EQUAL notes

[David Edelsohn]

	If the feedback was a philisophical argument that should have been
addressed by the GCC Steering Committee, then this issue should have been
escalated to the GCC SC long before it got out of control on the patches
and general mailinglist.  The current discussion is not productive.

	The Steering Committee has been working on a way to improve the
patch review and tracking process.  Hopefully that will allow some
frustrated and disaffected developers to return.  We need more specific
information about requirements for the content of patches and the content
of reviews.

	It would be a shame for others to have to replicate Daniel's work
when he already has a complete re-write of bitmap usage implemented as
requested by RTH.

David

Re: df.c and partial writes/REG_EQUAL notes

[Jan Hubicka]

> Don't bother, i already did it.
> You'll note that reload makes too many bitmaps, and the 16-24 bytes
> more overhead + the empty array pointers that the ebitmap takes causes
> 100-150 meg more memory.
> Just another point that we shouldn't up and replace them wholesale,
> rather do it incrementally.
> 
> I have resolved this problem by reworking the internals to
> not need to store empty words at all (ie not even pointers to them).

How did you accomplished that?
Is that contained in the updated ebitmap patch?
> 
> I also replaced bitmaps with them already.  The new internal storage
> mechanism requires changes to sbitmaps so you can properly
> and/or/copy/etc bitmaps of differing bit sizes.
> I.E. it'll do the right thing, as long as the destination is big
> enough to hold the right result. sbitmap_a_or_b (350 bit sbitmap, 25
> bit sbitmap, 200 bit sbitmap) will work properly.
> It would and/or/etc random memory before.
> 
> However, experience in doing this just helps prove my point. I tried
> doing it all at once, and it made finding the real cause of the bugs
> impossible.

Thats understandable - it happends in gcc commonly :(
> 
> > > 
> >> This was your "review".
> > Please lets work together to get gcc better, not fight.
> Who is fighting?
> I put review in quotes because i do not believe he reviewed the patch
> itself, as i stated in my message to Gerald.
> 
> I should also note that there was a bug in ebitmap.h in
> EXECUTE_IF_SET_IN_EBITMAP that a meaningful review of the patch would
> have caught. 
> 
> >
> > Honza
> > > 
> >> >
> >> > r~
> >> 
> >> -- 
> >> "When I was five years old I was on a merry go round.  There was
> >> a gunshot nearby.  The horses stampeded.  There I was running
> >> down the street on a purple wooden horse.
> >> "-Steven Wright
> 
> -- 
> "Last time I went skiing, I had to get up at 5:00 in the morning.
> I knew I couldn't do that, so I slept with my skis on.  My ride
> came at 5:30 in the morning, couldn't wake me up so he carried
> me out of the house, put my skis on the roof rack of the car,
> and drove to the mountain.  Seventeen miles later, I woke up out
> of this incredibly bizarre dream that I was skydiving
> horizontally.  I'm sure this has happened to you.
> "-Steven Wright

Re: df.c and partial writes/REG_EQUAL notes

[Daniel Berlin]

Jan Hubicka <jh@suse.cz> writes:

>> Don't bother, i already did it.
>> You'll note that reload makes too many bitmaps, and the 16-24 bytes
>> more overhead + the empty array pointers that the ebitmap takes causes
>> 100-150 meg more memory.
>> Just another point that we shouldn't up and replace them wholesale,
>> rather do it incrementally.
>> 
>> I have resolved this problem by reworking the internals to
>> not need to store empty words at all (ie not even pointers to them).
>
> How did you accomplished that?
You can keep an array only containing the set words (where words in
this whole email means whatever size cluster of real words we actually
use as the array element, it's currently 256 bits)

It requires possible memory moving for setting/clearing bits,
unfortunately.
However, it seems single bits are set/clear generally within given clusters
of 256 bits (at least for regsets), so i make the block size 256 bits
to account for this (so that, in general, we only move memory for the
first set of a bunch of regs, causing the rest to get lost in the
noise).

The worst case memory is N + N/256, where N is the number of *bits*,
for a completely full vector. 
Which isn't too bad, since you shouldn't be using them for completely
full vectors anyway.
Current bitmaps are N + (pointer size * 2 * (N/128)) (I'm in the
middle of Torts, so i'm not positive about this, i'm calculating based
on a first and next pointer and a block of 128 bits)

In order to set or clear a bit in a word that was zero
before, or becomes zero, requires memcpying a contiguous set of
blocks.

This word mask is why i needed to make sbitmaps work properly for
different size 
sbitmaps, because the word masks could be different sizes, but the
destination word mask will always be big enough to hold the result (we
make sure of it).
Before, it would always choose the size of the destination sbitmap,
and assume the input sbitmaps were the exact same size, and end up
performing the logical operation or whatever on random memory, and
storing that into the result, if either of the inputs were smaller
than the destination.

> Is that contained in the updated ebitmap patch?
Not a submitted one.


-- 
"Everywhere is walking distance if you have the time.
"-Steven Wright

Re: df.c and partial writes/REG_EQUAL notes

[Richard Henderson]

On Thu, Sep 27, 2001 at 09:29:44AM -0400, Daniel Berlin wrote:
> You want no more than 2 bitmap implementations in the compiler,

Yes.  And if we introduce a third, there will be significant
inertia for there to _remain_ three implementations.

> and want it replaced all at once, which is another questionable idea.

Did I say that?  I don't think I did.  If replacing the bitmap
implementation requires changes elsewhere wrt memory management,
then it should be possible to make those changes elsewhere before
actually replacing the bitmap implementation.

> This was your "review".

There are, unfortunately, only 24 hours in a day.

If I think I'd rather see the patch function in a completely
different way, I'll stop looking at it.  If you'd said "Ok, but
what do you think about the guts of the implementation?" I'd
have gone back and looked at it.  But otherwise I was planning
to wait until the next patch.


r~

Re: df.c and partial writes/REG_EQUAL notes

[Daniel Berlin]

Richard Henderson <rth@redhat.com> writes:

> On Thu, Sep 27, 2001 at 09:29:44AM -0400, Daniel Berlin wrote:
> > You want no more than 2 bitmap implementations in the compiler,
>
> Yes.  And if we introduce a third, there will be significant
> inertia for there to _remain_ three implementations.
>
>> and want it replaced all at once, which is another questionable idea.
>
> Did I say that?  I don't think I did. 
How would one keep two bitmap implementations, yet not change it all
at once?
It's not possible, since regsets *are* bitmaps.


>  If replacing the bitmap
> implementation requires changes elsewhere wrt memory management,
They don't, anymore.
It was simply an optimization anyway.

>
>
> r~

-- 
"He asked me if I knew what time it was.  I said, "Yes, but not
right now."
"-Steven Wright

Re: df.c and partial writes/REG_EQUAL notes

[law]

  In message < 87pu8cbw3b.fsf@cgsoftware.com >you write:
  > > Um, no, it *has* been reviewed.  I told you how I wanted
  > > it changed.
  > >
  > Ah, yes.
  > You want no more than 2 bitmap implementations in the compiler,
  > and want it replaced all at once, which is another questionable idea.
  > 
  > This was your "review".
Yes.  And I for one agree with Richard.

jeff

Re: df.c and partial writes/REG_EQUAL notes

[Michael Matz]

Hi,

Sorry for being late again:

On Tue, 25 Sep 2001, Jan Hubicka wrote:

> > Don't worry about the interactions, as the register allocator branch
> > A. has it's own version of df.c
>
> But once you will attempt to merge allocator in, you probably would not want
> to have df1.c and df2.c right?

Right.  But I'm nearly sure, that I'll not use df.c at all.  One reason
is, that the allocator also must collect the constraints for all reg
references (or better said for all operands), which would need a second
pass over all insns if I would use df.* for collecting the references
itself.  Note that even currently df.* is only used for collecting all
register references by the allocator.  Esp. it's not used for building the
use/def-chains.  (But, Daniels rematerialization uses the chains from
df.*)

If you want to know how I dealt with subregs and webs, look at ra.c, which
contains a fairly complete implementation of creating webs in a lazy
manner (although tailored to register allocation, i.e. also noting
conflicts and other things), including subwebs for subreg references.
The data structures there are not yet in their final state, but still.
(<self-praise> Btw. it's faster than df.* building of use/def chains on
CFG's of measurable size and can be relatively easy made to work
incrementally </self-praise>)

> > B. only uses df.c for reg defs and uses.  All dataflow is done without
> > df.c routines, because Michael doesn't want to use global liveness.
>
> As I've described, it misses one use at least, that should affect the
> reg-alloc branch too.

No, as described I don't rely on df.* to build any connections between
defs and uses.

> What exactly do you mean by global liveness?

I think he meant the usage of the DU_CHAIN or UD_CHAIN flags and
additionally bb->global_live_at_{start,end}, which also isn't used by
ra.c.

> If you do some extra analyzis, you should make as much of the as
> possible available to other passes - we already do have too many stuff
> doing analyzis "just for myself"

Right, and generally I agree.  From my p.o.v. the regalloc has a special
usage pattern of register references and their connection, which justifies
an own implementation.  But of course I may be biased ;-)

> > I.E. It only cares about noticing all of the reg defs and uses, it
> > doesn't care whether df.c really knows what they do.
> My web code too..

No, you rely on df.* to build the chains, which is exactly where you saw
the problems.  I suppose this is because initially Michael (Hayes) wrote
df.* to work only on REGs (i.e. recursing into SUBREGs when noting
references), and for that the chain builder worked.  For the allocator I
hacked more or less around it, and also offered the SUBREG references to
outside code, without actually making changes to the chain builder.  I.e.
if df.c compiles with HANDLE_SUBREG defined, it may very well be, that
that part of df.c gets everything wrong, if presented with df-tables which
contain subreg references.


Ciao,
Michael.

Re: df.c and partial writes/REG_EQUAL notes

[Jan Hubicka]

> Right.  But I'm nearly sure, that I'll not use df.c at all.  One reason
> is, that the allocator also must collect the constraints for all reg
> references (or better said for all operands), which would need a second
> pass over all insns if I would use df.* for collecting the references
> itself.  Note that even currently df.* is only used for collecting all
> register references by the allocator.  Esp. it's not used for building the
> use/def-chains.  (But, Daniels rematerialization uses the chains from
> df.*)
Can't you actually use the df.c framework, but just different method to note
the defs/refs (by browsing the operands)?
I guess the code to propagate the chains and datastructures still can be
shared with some care..

Honza

Re: df.c and partial writes/REG_EQUAL notes

[Mark Mitchell]

> There are, unfortunately, only 24 hours in a day.

And, unfortunately, only one of you.

Richard has been reviewing a ton of patches lately, a lot more than
anyone else.  If the rest of us can help out, we should try.
(Unfortunately, sometimes the number of free hours I have in the day
is about -3.)

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com

Re: df.c and partial writes/REG_EQUAL notes

[law]

  In message <20010925161602.C13734@atrey.karlin.mff.cuni.cz>you write:
  > yesterday I wanted to make myself familiar with the dataflow module and
  > write simple code to construct webs early and split each pseudo consisting
  > of multiple webs to assist CSE and other optimizations.
Don't bother.  SSA will do this for you in a much more sane way and will
probably be faster and generate better code anyway.

  > What I am shootingfor is to replace some of logic of unroll.c to make it
  > more rewritable for CFG.
Having the unroller using the CFG would definitely be an improvement. 

  > For instance
  >  code like
  > *a++=0;
  > *a++=0;
  > *a++=0;
  > *a++=0;
  > *a++=0;
  > Will currently use 5 increments, but if the various copies of A are
  > split, the CSE/combine takes care to construct multiple moves.
Err, so what is really looks like you want to do is splitting variables
during unrolling.  I recommend you look at Morgan/Muchnik as they discuss
variable expansion in this context.


  > Problem 1
  > =========
  > 
  > I've run into problems with dataflow analyzis and partial writes.  For inst
  > ance following
  > code:
  > 
  > 1: (set (reg:DI x) (const_int 0))
  > 
  > 2: (set (subreg:SI (reg:DI x) 0) (const_int 1))
  > 
  > 3: (use somewhere reg:DI x)
  > 
  > As currently impleemnted in df.c, there will be no depdendancy between
  > insn 1 and insn 3,
Right.  Review the movxx section in the Machine Descriptions part of the
manual.  Quoting:

@cindex @code{mov@var{m}} instruction pattern
@item @samp{mov@var{m}}
Here @var{m} stands for a two-letter machine mode name, in lower case.
This instruction pattern moves data with that machine mode from operand
1 to operand 0.  For example, @samp{movsi} moves full-word data.

If operand 0 is a @code{subreg} with mode @var{m} of a register whose
own mode is wider than @var{m}, the effect of this instruction is
to store the specified value in the part of the register that corresponds
to mode @var{m}.  The effect on the rest of the register is undefined.

Based on that I believe there should be no dependency since insn #2
leaves the rest of the DI register undefined.


  > as the store in insn 2 is believed to kill whole value of X.
As it should.

  > The semantic of insn 2 is to overwruite just first word of the value so
  > the insn 3 uses values of both instructions.
No.  See above.


  > Problem 2
  > =========
  > 
  > Another problem I've run into are the REG_EQUAL/EQUIV notes.  Currently
  > dataflow ignores them, but attempts to update them when register is
  > replaced, but this is quite wrong, as the insn may not mention the
  > register in the pattern, but still may contain it in the REG_EQUIV note. 
Yes.  This is an issue.

jeff

Re: df.c and partial writes/REG_EQUAL notes

[Richard Henderson]

On Wed, Oct 24, 2001 at 01:37:57PM -0600, law@redhat.com wrote:
> Right.  Review the movxx section in the Machine Descriptions part of the
> manual.  Quoting:
[...]
> If operand 0 is a @code{subreg} with mode @var{m} of a register whose
> own mode is wider than @var{m}, the effect of this instruction is
> to store the specified value in the part of the register that corresponds
> to mode @var{m}.  The effect on the rest of the register is undefined.
> 
> Based on that I believe there should be no dependency since insn #2
> leaves the rest of the DI register undefined.

The documentation is incomplete.  The rest of the register up to
BITS_PER_WORD are undefined.  Other words of a multi-word pseudo
are no undefined.


r~

Re: df.c and partial writes/REG_EQUAL notes

[Michael Matz]

Hi,

On Wed, 24 Oct 2001 law@redhat.com wrote:

> Right.  Review the movxx section in the Machine Descriptions part of the
> manual.  Quoting:
>
> @cindex @code{mov@var{m}} instruction pattern
> @item @samp{mov@var{m}}
> Here @var{m} stands for a two-letter machine mode name, in lower case.
> This instruction pattern moves data with that machine mode from operand
> 1 to operand 0.  For example, @samp{movsi} moves full-word data.
>
> If operand 0 is a @code{subreg} with mode @var{m} of a register whose
> own mode is wider than @var{m}, the effect of this instruction is
> to store the specified value in the part of the register that corresponds
> to mode @var{m}.  The effect on the rest of the register is undefined.
>
> Based on that I believe there should be no dependency since insn #2
> leaves the rest of the DI register undefined.

No, that's exactly the problem I was asking some months before about this
documentation.  Only the _word_ containing the subreg is touched by such a
move, i.e. if the subreg describes a complete word, it leaves no bits
undefined.  Depending on the machine a (set (subreg:SI (reg:DI x) 0))
clobbers the complete (reg:DI x) (if it only takes one hardreg), or only
the lower half.


Ciao,
Michael.

Re: df.c and partial writes/REG_EQUAL notes

[Jan Hubicka]

>   In message <20010925161602.C13734@atrey.karlin.mff.cuni.cz>you write:
>   > yesterday I wanted to make myself familiar with the dataflow module and
>   > write simple code to construct webs early and split each pseudo consisting
>   > of multiple webs to assist CSE and other optimizations.
> Don't bother.  SSA will do this for you in a much more sane way and will
> probably be faster and generate better code anyway.

Hmm, I understand that you may get the renaming of pseudos as side effect
of SSA/deSSA converison, but why it will be faster/generate better code?

>   > Will currently use 5 increments, but if the various copies of A are
>   > split, the CSE/combine takes care to construct multiple moves.
> Err, so what is really looks like you want to do is splitting variables
> during unrolling.  I recommend you look at Morgan/Muchnik as they discuss
> variable expansion in this context.

I did.  What I wanted is to do in general - not only for loops unrolled by gcc.
> 
> 
>   > Problem 1
>   > =========
>   > 
>   > I've run into problems with dataflow analyzis and partial writes.  For inst
>   > ance following
>   > code:
>   > 
>   > 1: (set (reg:DI x) (const_int 0))
>   > 
>   > 2: (set (subreg:SI (reg:DI x) 0) (const_int 1))
>   > 
>   > 3: (use somewhere reg:DI x)
>   > 
>   > As currently impleemnted in df.c, there will be no depdendancy between
>   > insn 1 and insn 3,
> Right.  Review the movxx section in the Machine Descriptions part of the
> manual.  Quoting:
> 
> @cindex @code{mov@var{m}} instruction pattern
> @item @samp{mov@var{m}}
> Here @var{m} stands for a two-letter machine mode name, in lower case.
> This instruction pattern moves data with that machine mode from operand
> 1 to operand 0.  For example, @samp{movsi} moves full-word data.
> 
> If operand 0 is a @code{subreg} with mode @var{m} of a register whose
> own mode is wider than @var{m}, the effect of this instruction is
> to store the specified value in the part of the register that corresponds
> to mode @var{m}.  The effect on the rest of the register is undefined.
> 
> Based on that I believe there should be no dependency since insn #2
> leaves the rest of the DI register undefined.

Then the documentation is wrong - most ports use subreg in a way that it
clobbers the specified word only.

Honza

Re: df.c and partial writes/REG_EQUAL notes

[Daniel Berlin]

Jan Hubicka <jh@suse.cz> writes:

>>   In message <20010925161602.C13734@atrey.karlin.mff.cuni.cz>you write:
>>   > yesterday I wanted to make myself familiar with the dataflow module and
>>   > write simple code to construct webs early and split each pseudo consisting
>>   > of multiple webs to assist CSE and other optimizations.
>> Don't bother.  SSA will do this for you in a much more sane way and will
>> probably be faster and generate better code anyway.
> 
> Hmm, I understand that you may get the renaming of pseudos as side effect
> of SSA/deSSA converison, but why it will be faster/generate better
> code?
It won't be, assuming you are using my patches to df.c to change the
iteration order/etc.
It'll be O(n+2).

-- 
"I play the harmonica.  The only way I can play is if I get my
car going really fast, and stick it out the window.  I've been
arrested three times for practicing.
"-Steven Wright

Re: df.c and partial writes/REG_EQUAL notes

[law]

  In message < Pine.GSO.4.33.0110242215060.17229-100000@platon >you write:
  > Hi,
  > 
  > On Wed, 24 Oct 2001 law@redhat.com wrote:
  > 
  > > Right.  Review the movxx section in the Machine Descriptions part of the
  > > manual.  Quoting:
  > >
  > > @cindex @code{mov@var{m}} instruction pattern
  > > @item @samp{mov@var{m}}
  > > Here @var{m} stands for a two-letter machine mode name, in lower case.
  > > This instruction pattern moves data with that machine mode from operand
  > > 1 to operand 0.  For example, @samp{movsi} moves full-word data.
  > >
  > > If operand 0 is a @code{subreg} with mode @var{m} of a register whose
  > > own mode is wider than @var{m}, the effect of this instruction is
  > > to store the specified value in the part of the register that corresponds
  > > to mode @var{m}.  The effect on the rest of the register is undefined.
  > >
  > > Based on that I believe there should be no dependency since insn #2
  > > leaves the rest of the DI register undefined.
  > 
  > No, that's exactly the problem I was asking some months before about this
  > documentation.  Only the _word_ containing the subreg is touched by such a
  > move, i.e. if the subreg describes a complete word, it leaves no bits
  > undefined.  Depending on the machine a (set (subreg:SI (reg:DI x) 0))
  > clobbers the complete (reg:DI x) (if it only takes one hardreg), or only
  > the lower half.
Several folks have pointed out the documentation problem.  Too bad we
didn't fix the documentation the first time this came up :-)

Anyway, I believe this patch should make the documentation clearer.

	* doc/md.texi (movMM): Clarify semantics of storing into a 
	non-paradoxical SUBREG.

Index: md.texi
===================================================================
RCS file: /cvs/gcc/egcs/gcc/doc/md.texi,v
retrieving revision 1.25
diff -c -3 -p -r1.25 md.texi
*** md.texi	2001/10/11 07:07:30	1.25
--- md.texi	2001/10/25 18:17:46
*************** This instruction pattern moves data with
*** 2024,2030 ****
  If operand 0 is a @code{subreg} with mode @var{m} of a register whose
  own mode is wider than @var{m}, the effect of this instruction is
  to store the specified value in the part of the register that corresponds
! to mode @var{m}.  The effect on the rest of the register is undefined.
  
  This class of patterns is special in several ways.  First of all, each
  of these names up to and including full word size @emph{must} be defined,
--- 2024,2032 ----
  If operand 0 is a @code{subreg} with mode @var{m} of a register whose
  own mode is wider than @var{m}, the effect of this instruction is
  to store the specified value in the part of the register that corresponds
! to mode @var{m}.  Bits outside of @var{m}, but which are within the
! same target word as the @code{subreg} are undefined.  Bits which are
! outside the target word are left unchanged.
  
  This class of patterns is special in several ways.  First of all, each
  of these names up to and including full word size @emph{must} be defined,

Re: df.c and partial writes/REG_EQUAL notes

[Daniel Berlin]

Jan Hubicka <jh@suse.cz> writes:

>> As to my opinion of the underlying issue, I'll say first that I have not
>> looked at the patch.  However, I agree with RTH that we don't need *three*
>> bitmap implementations.  That being said, however, I could be convinced that
> This is my intuition too.
> I've looked at the code and after some thinking, Daniel's approach seems
> to make more sense. To sumarize my conclusion:
>
> The problem Daniel run into, and that sounds understandable is that we have
> different needs for the bitmap reprezentation:
>
> 1) we need lightweight fast small bitmaps (as hard-reg-sets) where sbitmap is
>    very good choice. For instance it can be nice to use them even in combine
>    for the "nonzero" bits and similar cases where we artificaly limit our
>    implementation for HOST_WIDE_INT.  This would be a must to get good
>    optimizations on packed types in future probably.
> 2) we need fast and unavoidingly large, sparse bitmaps (such as those used
>    by dataflow or LCM).  The ebitmap framework sounds sane here.
>    It can be nice to make fast path of bit set/test functions macro, as
>    our profiles keeps these functions at the top in the ammount of function
>    calls.
I did this as well (including a define to outline them, for profiling
purposes/debugability).  There are a few cases where it's not inlined,
but the compiler seems to make the right choice here.

> 3) we need sparse and space efecient bitmaps in some cases.
>    (Daniel claims he run into space problems with ebitmap in reload, probably
>     because of relativly small and numberous bitmaps used by life analyzis
>     for reg_sets).

It's actually the insn chains reload uses + life analysis.
Reload *seems* creates 2 bitmaps per insn, at least. I'm just going by
the insn chain structure here.

>
>From this point of view the 3 implementations appears to make sense.
> Daniel, in other email described his attempt to make ebitmaps space efecient,
> if that will work, we will end up with 2 bitmap reprezentations and this
> appears to make sense, given the fact above.
Correct.
However, it's at the expense of more memory traffic.
They do work, and do bootstrap/make check, i'm just tuning the block
size and whatnot.


>
> So lets turn into techincal issues now and try to figure out whether we can
> bring data reprezentation that fits 2) and 3).

BTW, if the logical operations start to appear at the top of the
profile, we could just vectorize it for various platforms.
This is one reason i use auxiliary static inline functions for the
actual blocks.


>
> Honza

-- 
"I was trying to daydream, but my mind kept wandering.
"-Steven Wright

Re: df.c and partial writes/REG_EQUAL notes

[mike stump]

> To: kenner@vlsi1.ultra.nyu.edu (Richard Kenner)
> Cc: dan@cgsoftware.com, gcc@gcc.gnu.org
> From: Daniel Berlin <dan@cgsoftware.com>
> Date: Thu, 27 Sep 2001 14:41:38 -0400

> A review of a patch tells you what is necessary to make it acceptable
> for gcc. Not whether a particular person with global write access
> likes it.

I don't see anything evidence that what was done was wrong.  I can't
help but wonder if your expectations of what the process is is flawed
or deficient.  I think you have many unreasonable expectations.

I don't see it as wrong for a maintainer to offer a partial review of
a patch instead of a complete review of the patch.  I don't see it as
wrong if a maintainer only states what you consider is just his
opinion of a patch.  I don't see it as wrong if a maintainer misses a
deficiency of a patch.  I don't see it as wrong if a maintainer uses
different definitions of patch, review, code, correct, or compiler
from you...  I don't see it as wrong if a maintainer doesn't review
a patch.

> Note that a review of the patch would have noticed the documentation
> was deficient.  This is what would make the patch acceptable, for
> the most part, (at least in this case), to other global write
> people.

If that is the case, why are we having this discussion?  Fix the
documentation and have have it accepted.  We can be sure this is the
case, after you do it.

> It is a statement that gives you some indication as to whether
> or not they will review that patch. It is not a review in and of
> itself.

Sounds like a semantic game.  Feel free to submit changes to the web
site that desribe what you discover the process is, so that you will
believe the words are accurate.

Re: df.c and partial writes/REG_EQUAL notes

[Richard Kenner]

    A review of a patch tells you what is necessary to make it acceptable
    for gcc. Not whether a particular person with global write access
    likes it.

"Whether a particular person with global write access likes it" is supposed
to be equivalent to whether "it's acceptable for GCC".

    This is not a review of the patch itself. It is a statement about the
    approach to the problem the patch takes.

Of course, but if that approach is deemed wrong, the patch itself is
irrelevant and it's a waste of time to go into details with it.

    Everyone agrees the approach to the actual problem the patch
    implements is wrong, regardless of the implementation details or
    quality of the patch.
    This is not one of those cases.

It sounded like it was to me. 

    Somebody should, of course, review each patch.  Unless *everyone*
    agrees the actual approach to solving the problem is wrong.

No, that's not the way it works.  Saying the approach is wrong *is* a
review.  Indeed, the first part of a review is to check the approach.
If the approach is wrong, then there's no point in going further.

    It all goes back to whether a statement like "we shouldn't have 3
    bitmap implementations" is a review of the patch.  

I believe it is.

    > However, I agree with RTH that we don't need *three* bitmap
    > implementations.

    Not that i disagree, i'm just curious why?

Essentially because it makes the compiler more complicated.  There are the
opportunities for bugs, three implementations to understand, and three to
choose from when somebody needs a bitmap.

    What is it about bitmaps that makes you think two is enough?
    The right representation for a given set of problems is more important
    than the number of representations.
    In fact, it's often vital.

If you can explain where there are three different sets of properties of the
data that hence require three different implementations, then I'd consider
that three may be the right number.

Re: df.c and partial writes/REG_EQUAL notes

[Daniel Berlin]

kenner@vlsi1.ultra.nyu.edu (Richard Kenner) writes:

>     Saying "I don't think we need 3 bitmap implemenations" is not a
>     review of a patch.
>
> If the patch in question adds a third bitmap implementation, it *is* a review
> of the patch.
No, it's not.

A review of a patch tells you what is necessary to make it acceptable
for gcc. Not whether a particular person with global write access
likes it.
Often, these things are orthogonal.
Sometimes, they are not.

>
> If somebody submits a patch based on a concept with which I disagree and I
> review the patch, I'll just say that I don't think the concept behind the
> patch is reasonable. 
This is not a review of the patch itself. It is a statement about the
approach to the problem the patch takes.
That is, there are cases where review is not necessary.
Everyone agrees the approach to the actual problem the patch
implements is wrong, regardless of the implementation details or
quality of the patch.
This is not one of those cases.
If I asked someone to review a case or document for me, that i was
planning to submit to a court, and they handed it back with no marks,
comments, or anything else, and just said "I disagree", i wouldn't
feel they had reviewed it, only 
presented their opinion on the overall point of the document.
Whether they agree or not is not the point of a review. I might
disagree with the overall point as well (it all depends on who your
client is)
Nor would it change whether *others* agree with the overall point or
not.
And I would still have a document to submit.
I just wouldn't know what the heck is wrong with it.


>  In that case, there's no reason to delve further into
> the details of the patch, including the quality of the
> documentation.
If you aren't going to review it, don't review it.
That's fine.
Somebody should, of course, review each patch.  Unless *everyone*
agrees the actual approach to solving the problem is wrong.
In that case, someone should tell the contributor, too.
This is not what happened here.


>
>     Overall direction and whatnot of the compiler is not controlled by
>     [a specific global-write privilege maintainer], it's controlled by the
>     steering committee.
>
> True, but the SC has made it clear they do not want to get involved in the
> review process of individual patches, only in setting that process, which is
> that *somebody* with global write privileges must be convinced to approve the
> patch.  In the case of a *major* issue, I agree it's appropriate to raise it
> with the SC, but I doubt the SC wants to get involved at this level of
> technical detail.
Sure.
However, how can I convince *somebody* with global write access that
it's a good patch to approve, if it hasn't really been reviewed. You
can't very well do the review yourself.
It all goes back to whether a statement like "we shouldn't have 3
bitmap implementations" is a review of the patch.
Note that a review of the patch would have noticed the documentation
was deficient.
This is what would make the patch acceptable, for the most part, (at
least in this case), to other global write people.
A single global write person's opinion about a patch is not a review
of it. It is a statement that gives you some indication as to whether
or not they will review that patch. It is not a review in and of
itself.
If nobody thinks a patch is acceptable, regardless of the actual code
in the patch, then the patch is not acceptable, but it also has not
been reviewed.

>
> As to my opinion of the underlying issue, I'll say first that I have not
> looked at the patch.  However, I agree with RTH that we don't need *three*
> bitmap implementations.
Not that i disagree, i'm just curious why?
What is it about bitmaps that makes you think two is enough?
The right representation for a given set of problems is more important
than the number of representations.
In fact, it's often vital.

-- 
"If you're not part of the solution, you're part of the
precipitate.
"-Steven Wright

Re: df.c and partial writes/REG_EQUAL notes

[Jan Hubicka]

> As to my opinion of the underlying issue, I'll say first that I have not
> looked at the patch.  However, I agree with RTH that we don't need *three*
> bitmap implementations.  That being said, however, I could be convinced that
This is my intuition too.
I've looked at the code and after some thinking, Daniel's approach seems
to make more sense. To sumarize my conclusion:

The problem Daniel run into, and that sounds understandable is that we have
different needs for the bitmap reprezentation:

1) we need lightweight fast small bitmaps (as hard-reg-sets) where sbitmap is
   very good choice. For instance it can be nice to use them even in combine
   for the "nonzero" bits and similar cases where we artificaly limit our
   implementation for HOST_WIDE_INT.  This would be a must to get good
   optimizations on packed types in future probably.
2) we need fast and unavoidingly large, sparse bitmaps (such as those used
   by dataflow or LCM).  The ebitmap framework sounds sane here.
   It can be nice to make fast path of bit set/test functions macro, as
   our profiles keeps these functions at the top in the ammount of function
   calls.
3) we need sparse and space efecient bitmaps in some cases.
   (Daniel claims he run into space problems with ebitmap in reload, probably
    because of relativly small and numberous bitmaps used by life analyzis
    for reg_sets).

From this point of view the 3 implementations appears to make sense.
Daniel, in other email described his attempt to make ebitmaps space efecient,
if that will work, we will end up with 2 bitmap reprezentations and this
appears to make sense, given the fact above.

So lets turn into techincal issues now and try to figure out whether we can
bring data reprezentation that fits 2) and 3).

Honza

Re: df.c and partial writes/REG_EQUAL notes

[Richard Kenner]

    Saying "I don't think we need 3 bitmap implemenations" is not a
    review of a patch.

If the patch in question adds a third bitmap implementation, it *is* a review
of the patch.

If somebody submits a patch based on a concept with which I disagree and I
review the patch, I'll just say that I don't think the concept behind the
patch is reasonable.  In that case, there's no reason to delve further into
the details of the patch, including the quality of the documentation.

    Overall direction and whatnot of the compiler is not controlled by
    [a specific global-write privilege maintainer], it's controlled by the
    steering committee.

True, but the SC has made it clear they do not want to get involved in the
review process of individual patches, only in setting that process, which is
that *somebody* with global write privileges must be convinced to approve the
patch.  In the case of a *major* issue, I agree it's appropriate to raise it
with the SC, but I doubt the SC wants to get involved at this level of
technical detail.

As to my opinion of the underlying issue, I'll say first that I have not
looked at the patch.  However, I agree with RTH that we don't need *three*
bitmap implementations.  That being said, however, I could be convinced that
a patch that added one was reasonable *if* I was convinced that this
implementation was vastly superior in some way *and* that there was a clear
path towards going back to two (or, better yet, one) such implmentation and I
trusted the submitter to do that.  Note that the last criteria means that I
(and presumably others) would have different opinions on the issue based on
the GCC development history of the submitter.