Re: Some questions about pass web

[Carrot Wei]

It is indeed caused by wrong DF information, which is caused by a
wrong fix for bug PR32339.
More discussion is at https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63156.

thanks a lot
Guozhi Wei

On Tue, Sep 9, 2014 at 5:31 PM, Jan Hubicka  wrote:
>> On 09/03/14 02:35, Steven Bosscher wrote:
>> >On Wed, Sep 3, 2014 at 9:17 AM, Bin.Cheng wrote:
>> >>Last time I tried, there are several passes after loop_done and before
>> >>auto-inc-dec can't handle auto-increment addressing mode, including
>> >>fweb.
>> >
>> >It surprises me that pass_web can't handle AUTOINC. Perhaps I'm off my
>> >rocker, but it's always been my understanding that almost all passes
>> >handle AUTOINC just fine (or at least conservatively: punt if you see
>> >an AUTOINC), and that only CSE really doesn't know about AUTOINC at
>> >all.
>> In the past autoinc instructions didn't appear until flow (just
>> prior to combine) and that was documented behaviour.  So anything
>> which was run strictly prior to flow/combine wasn't autoinc aware.
>> That may have changed somewhat with the autoinc rewrite.
>
> It is long time since I looked at web, but it should understand read/write 
> refs
> and that those must remain unified.  how does DF refs look like for autoinc?
>
> Honza
>>
>> jeff

Re: Some questions about pass web

[Jan Hubicka]

> On 09/03/14 02:35, Steven Bosscher wrote:
> >On Wed, Sep 3, 2014 at 9:17 AM, Bin.Cheng wrote:
> >>Last time I tried, there are several passes after loop_done and before
> >>auto-inc-dec can't handle auto-increment addressing mode, including
> >>fweb.
> >
> >It surprises me that pass_web can't handle AUTOINC. Perhaps I'm off my
> >rocker, but it's always been my understanding that almost all passes
> >handle AUTOINC just fine (or at least conservatively: punt if you see
> >an AUTOINC), and that only CSE really doesn't know about AUTOINC at
> >all.
> In the past autoinc instructions didn't appear until flow (just
> prior to combine) and that was documented behaviour.  So anything
> which was run strictly prior to flow/combine wasn't autoinc aware.
> That may have changed somewhat with the autoinc rewrite.

It is long time since I looked at web, but it should understand read/write refs
and that those must remain unified.  how does DF refs look like for autoinc?

Honza
> 
> jeff

Re: Some questions about pass web

[Carrot Wei]

On Wed, Sep 3, 2014 at 1:29 AM, Steven Bosscher  wrote:
> On Wed, Sep 3, 2014 at 1:35 AM, Carrot Wei wrote:
>> 1. It is well known that register renaming is a big help to register
>> allocation, but in gcc's backend, the web pass is far before RA, there
>> are about 20 passes between them. Does it mean register renaming can
>> also heavily benefit other optimizations?
>
> Yes - sometimes anyway. Most non-SSA data flow analyses can't look
> through pseudos that have multiple non-overlapping live ranges. Think
> constant/copy propagation, value numbering, etc. After passes that
> duplicate basic blocks, and not renaming registers, you get false
> dependencies that hide RA and scheduling opportunities. This is why
> pass_web is after code-duplication transformations like (RTL) loop
> unrolling but before the last RTL CPROP pass. The old RA couldn't do
> register renaming, so something before RA had to take care of it.
> Enter pass_web.
>
> But this is less relevant in GCC today, where RTL code transformations
> basically should be limited to simple local transformations, with the
> more difficult global transformations already done on GIMPLE
> (including live range splitting, part of out-of-SSA). On top of that,
> IRA knows how to do some forms of live range splitting (but not within
> loops, AFAIU, because a loop is a single region in IRA). If someone
> would give some TLC to the RTL loop-unroll.c code for
> IV-splitting/accumulator-expanding and make them enabled by default, I
> doubt pass_web would be doing much at all.
>
>
>> And the passes between them
>> usually don't generate more register renaming chances?
>
> Usually not. Most of them create new pseudos for newly inserted expressions.
>
> Some passes are actually harmed by pass_web. auto_inc_dec is one of those.
>
>
>> 2. It looks current web pass can't handle AUTOINC expressions, a reg
>> operand is used as both use and def reference in an AUTOINC
>> expression, so this def side should not be renamed. Pass web doesn't
>> explicitly check this case, may rename the reg operand of AUTOINC
>> expression. Is this expected because it is before auto_inc_dec pass?
>
> You already found the DF_REF_READ_WRITE bits. pass_web also handles
> match_dup constraints. That should be enough. If it is not, then
> please file a bug report (and feel free to assign it to me).
>
Bug entry filed https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63156.
Debugging shows that DF_REF_READ_WRITE is not set for the operand of
post_inc, may be a dataflow problem?

thanks
Guozhi Wei

Re: Some questions about pass web

[Jeff Law]

On 09/03/14 02:35, Steven Bosscher wrote:

On Wed, Sep 3, 2014 at 9:17 AM, Bin.Cheng wrote:

Last time I tried, there are several passes after loop_done and before
auto-inc-dec can't handle auto-increment addressing mode, including
fweb.


It surprises me that pass_web can't handle AUTOINC. Perhaps I'm off my
rocker, but it's always been my understanding that almost all passes
handle AUTOINC just fine (or at least conservatively: punt if you see
an AUTOINC), and that only CSE really doesn't know about AUTOINC at
all.
In the past autoinc instructions didn't appear until flow (just prior to 
combine) and that was documented behaviour.  So anything which was run 
strictly prior to flow/combine wasn't autoinc aware.  That may have 
changed somewhat with the autoinc rewrite.


jeff

Re: Some questions about pass web

[Steven Bosscher]

On Wed, Sep 3, 2014 at 9:17 AM, Bin.Cheng wrote:
> Last time I tried, there are several passes after loop_done and before
> auto-inc-dec can't handle auto-increment addressing mode, including
> fweb.

It surprises me that pass_web can't handle AUTOINC. Perhaps I'm off my
rocker, but it's always been my understanding that almost all passes
handle AUTOINC just fine (or at least conservatively: punt if you see
an AUTOINC), and that only CSE really doesn't know about AUTOINC at
all.

Ciao!
Steven

Re: Some questions about pass web

[Steven Bosscher]

On Wed, Sep 3, 2014 at 1:35 AM, Carrot Wei wrote:
> 1. It is well known that register renaming is a big help to register
> allocation, but in gcc's backend, the web pass is far before RA, there
> are about 20 passes between them. Does it mean register renaming can
> also heavily benefit other optimizations?

Yes - sometimes anyway. Most non-SSA data flow analyses can't look
through pseudos that have multiple non-overlapping live ranges. Think
constant/copy propagation, value numbering, etc. After passes that
duplicate basic blocks, and not renaming registers, you get false
dependencies that hide RA and scheduling opportunities. This is why
pass_web is after code-duplication transformations like (RTL) loop
unrolling but before the last RTL CPROP pass. The old RA couldn't do
register renaming, so something before RA had to take care of it.
Enter pass_web.

But this is less relevant in GCC today, where RTL code transformations
basically should be limited to simple local transformations, with the
more difficult global transformations already done on GIMPLE
(including live range splitting, part of out-of-SSA). On top of that,
IRA knows how to do some forms of live range splitting (but not within
loops, AFAIU, because a loop is a single region in IRA). If someone
would give some TLC to the RTL loop-unroll.c code for
IV-splitting/accumulator-expanding and make them enabled by default, I
doubt pass_web would be doing much at all.


> And the passes between them
> usually don't generate more register renaming chances?

Usually not. Most of them create new pseudos for newly inserted expressions.

Some passes are actually harmed by pass_web. auto_inc_dec is one of those.


> 2. It looks current web pass can't handle AUTOINC expressions, a reg
> operand is used as both use and def reference in an AUTOINC
> expression, so this def side should not be renamed. Pass web doesn't
> explicitly check this case, may rename the reg operand of AUTOINC
> expression. Is this expected because it is before auto_inc_dec pass?

You already found the DF_REF_READ_WRITE bits. pass_web also handles
match_dup constraints. That should be enough. If it is not, then
please file a bug report (and feel free to assign it to me).


> 3. Are AUTOINC expressions only generated by auto_inc_dec pass? All
> passes before auto_inc_dec including expand should not generate
> AUTOINC expressions, otherwise it will break web.

IIRC, it used to be that only push/pop could be AUTOINC before
auto_inc_dec. I'm not sure if this is still true today.

Ciao!
Steven

Re: Some questions about pass web

[Bin.Cheng]

On Wed, Sep 3, 2014 at 7:35 AM, Carrot Wei  wrote:
> Hi
>
> I have following questions about web (pseudo register renaming) pass:
>
> 1. It is well known that register renaming is a big help to register
> allocation, but in gcc's backend, the web pass is far before RA, there
> are about 20 passes between them. Does it mean register renaming can
> also heavily benefit other optimizations? And the passes between them
> usually don't generate more register renaming chances?
I think one purpose is to break long dependency chain into short ones.
For example, with below code

   use(i)
   i = i + 1;
   ...
   use(i)
   i = i + 1;
   ...
   use(i)
   i = i + 1;
   ...

Pass fweb could change it into below form

   use(i)
   i0 = i + 1
   ...
   use(i0)
   i1 = i0 + 1
   ...
   use(i1)
   i = i0 + 2
   ...

Apparently, latter form has shorter chains, which makes df stuff more efficient.

>
> 2. It looks current web pass can't handle AUTOINC expressions, a reg
> operand is used as both use and def reference in an AUTOINC
> expression, so this def side should not be renamed. Pass web doesn't
> explicitly check this case, may rename the reg operand of AUTOINC
> expression. Is this expected because it is before auto_inc_dec pass?

Last time I tried, there are several passes after loop_done and before
auto-inc-dec can't handle auto-increment addressing mode, including
fweb.
>
> 3. Are AUTOINC expressions only generated by auto_inc_dec pass? All
> passes before auto_inc_dec including expand should not generate
> AUTOINC expressions, otherwise it will break web.
Yes.  Yet other passes may generate auto-inc friendly instruction
patterns thus auto-inc-dec can capture more opportunities.  IVOPT is a
typical example.

Thanks,
bin

>
> Could anybody help to answer these questions?
>
> thanks a lot
> Guozhi Wei

Re: Some questions about pass web

[Carrot Wei]

For the relation between web and AUTOINC, I found the code in union_defs:

if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
  {
...
  }

So web should handle AUTOINC in theory, but in an experiment, I added
a second web pass just before RA, web generated wrong code in the
presence of AUTOINC expressions. I will debug it more.

thanks
Guozhi Wei

On Tue, Sep 2, 2014 at 4:35 PM, Carrot Wei  wrote:
> Hi
>
> I have following questions about web (pseudo register renaming) pass:
>
> 1. It is well known that register renaming is a big help to register
> allocation, but in gcc's backend, the web pass is far before RA, there
> are about 20 passes between them. Does it mean register renaming can
> also heavily benefit other optimizations? And the passes between them
> usually don't generate more register renaming chances?
>
> 2. It looks current web pass can't handle AUTOINC expressions, a reg
> operand is used as both use and def reference in an AUTOINC
> expression, so this def side should not be renamed. Pass web doesn't
> explicitly check this case, may rename the reg operand of AUTOINC
> expression. Is this expected because it is before auto_inc_dec pass?
>
> 3. Are AUTOINC expressions only generated by auto_inc_dec pass? All
> passes before auto_inc_dec including expand should not generate
> AUTOINC expressions, otherwise it will break web.
>
> Could anybody help to answer these questions?
>
> thanks a lot
> Guozhi Wei

Some questions about pass web

[Carrot Wei]

Hi

I have following questions about web (pseudo register renaming) pass:

1. It is well known that register renaming is a big help to register
allocation, but in gcc's backend, the web pass is far before RA, there
are about 20 passes between them. Does it mean register renaming can
also heavily benefit other optimizations? And the passes between them
usually don't generate more register renaming chances?

2. It looks current web pass can't handle AUTOINC expressions, a reg
operand is used as both use and def reference in an AUTOINC
expression, so this def side should not be renamed. Pass web doesn't
explicitly check this case, may rename the reg operand of AUTOINC
expression. Is this expected because it is before auto_inc_dec pass?

3. Are AUTOINC expressions only generated by auto_inc_dec pass? All
passes before auto_inc_dec including expand should not generate
AUTOINC expressions, otherwise it will break web.

Could anybody help to answer these questions?

thanks a lot
Guozhi Wei