Stepanov, PowerPC, life_analysis

Stepanov, PowerPC, life_analysis

[Mark Mitchell]

I've figured out why are Stepanov abstraction numbers (which basically
exercise ADDRESSOF in different ways) are worse on PowerPC than they
were for GCC 2.95.

The bottom line is that GCC 2.95 got lucky.  (There are simple
transformations to the source that will cause us to generate lousy
code with 2.95 as well.)

  In the code stream for 3.0, after CSE, we end up with:

  (insn 206 11 229 (set (reg:SI 126)
	  (addressof:SI (reg/v:SI 83) 82 0x403464e0)) 282 {*movsi_internal1} (nil)
      (nil))

  (insn 229 206 210 (set (reg/s/v/f:SI 91)
	  (reg:SI 126)) -1 (nil)
      (nil))

  ...

  (insn 82 80 85 (set (reg/v/f:SI 106)
        (reg/s/v/f:SI 91)) 282 {*movsi_internal1} (nil)
    (nil))

  ...

  (insn 35 223 43 (set (reg/s/v/f:SI 91)
          (reg/v/f:SI 106)) 282 {*movsi_internal1} (nil)
      (expr_list:REG_EQUAL (addressof:SI (reg/v:SI 83) 82 0x403464e0)
          (nil)))

The important thing to notice is that all of these instructions are
dead: nothing here actually does anything, and these are the uses of
the REGs mentioned.

In 2.95, we had the first instruction, but not all of the other ones.
This is partly due to an artifact of the tree-based inliner, which
generates a few more register->register copies to express argument
passing, and partly perhaps due to changes in CSE.  

In any case, in 2.95, delete_trivially_dead_insns blows away the
equivalent of insn 206 and in 3.0 it doesn't because the instruction
is dead, but not trivially dead.

We purge_addressof after this point -- and the existence of insn 206
causes us to dump register 83 to the stack, and that's the performance
lossage.

This really points up how important it is to rework our global
optimizers to not commit to code shape up front.  The real solution
here is to keep ADDRESSOF until much later in the compilation, or some
such.  However, we're not going to do that now.

So, what can we do?  Well, the following patch (untested except on
this test case) fixes the problem by blowing away the silly register
copies before purging ADDRESSOF.  I don't know whether the basic-block
graph is in good shape at this point; the call to find_basic_blocks
may not be necessary.  And, I don't know if there's are other flags
that we should pass to life_analysis at this point.

But, I think this is the right approach.  And, I don't see what the
point in having delete_trivially_dead_insns around is when we have
this much better hammer -- we could probably eliminate the call to
that as well.

In any case, I'm looking for input as to people think that:

  - This is the right idea, and if so, whether the details are
    right.

  - Whether or not we need to fix this for GCC 3.0.

In the meantime, I'll run tests on i686-pc-linux-gnu to validate.

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

Re: Stepanov, PowerPC, life_analysis

[Scott A Crosby]

On Fri, 8 Jun 2001, Mark Mitchell wrote:

>
> I've figured out why are Stepanov abstraction numbers (which basically
> exercise ADDRESSOF in different ways) are worse on PowerPC than they
> were for GCC 2.95.
>

I've got some code. PR/2399, which shows some pretty nasty assembly.

On 2.95.2, it reserves 120 bytes of stack, and performs 18 trivially dead
stores, and 6 other (superflous?) stores. The correct code is one single
store (the 'movb $0xa,0x345(%eax)' at the end), for an abstraction penalty
of about 20x.

The code is to implement multidimensional subscripting for an compile-time
fixed-size arrays.

    SmartFixedArray<16,16,16> x;
    x[1][2][3] = 19;

I bring it up because of the comments on whether or not this was important
for 3.0 in the email. As this is a short and extremely severe example, I
offer it now.

The bug report PR/2399 is currently unassigned and open.

Scott

--
No DVD movie will ever enter the public domain, nor will any CD. The last CD
and the last DVD will have moldered away decades before they leave copyright.
This is not encouraging the creation of knowledge in the public domain.

Re: Stepanov, PowerPC, life_analysis

[Bernd Schmidt]

On Fri, 8 Jun 2001, Mark Mitchell wrote:
>
> In any case, I'm looking for input as to people think that:
>
>   - This is the right idea, and if so, whether the details are
>     right.

Seems to be.

>   - Whether or not we need to fix this for GCC 3.0.

That's your call :)


Bernd

Re: Stepanov, PowerPC, life_analysis

[Mark Mitchell]

>>>>> "Bernd" == Bernd Schmidt <bernds@redhat.com> writes:

    Bernd> On Fri, 8 Jun 2001, Mark Mitchell wrote:
    >>  In any case, I'm looking for input as to people think that:
    >> 
    >> - This is the right idea, and if so, whether the details are
    >> right.

    Bernd> Seems to be.

Good.  Including the call to find_basic_blocks and the flags to
life_analysis?

I've tested this, and all looks good.  Richard, do you have any
thoughts?

Thanks,

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

Re: Stepanov, PowerPC, life_analysis

[Joe Buck]

> [ blow away some register copies before removing ADDRESSOF ]
> In any case, I'm looking for input as to people think that:
> 
>   - This is the right idea, and if so, whether the details are
>     right.

Internals experts like Richard will have to tell us whether it's safe
and the details are right.  Conceptually, it seems OK, but that might
just reflect my ignorance.

>   - Whether or not we need to fix this for GCC 3.0.

By our original release criteria, it fixes an important performance
regression, so it would have been required for the release.  We've relaxed
requirements on that, but this kind of poor Stepanov performance is likely
to mean poor C++ performance across the board, so I'd like to see it go in
unless the gurus consider it unsafe.  Of course, I'm assuming no
regressions on primary release platforms.

Re: Stepanov, PowerPC, life_analysis

[Richard Henderson]

On Sat, Jun 09, 2001 at 11:17:05AM -0700, Mark Mitchell wrote:
> Good.  Including the call to find_basic_blocks and the flags to
> life_analysis?

Yep.  CSE doesn't maintain the CFG while simplifying or eliminating
branches, so rebuilding it is necessary.  You do want to add a call
to cleanup_cfg though.  The flags to life_analysis are right.

I do suggest that we move this a bit earlier -- before the call to
renumber_insns.


r~

Re: Stepanov, PowerPC, life_analysis

[Mark Mitchell]

>>>>> "Joe" == Joe Buck <jbuck@synopsys.com> writes:

    Joe> Internals experts like Richard will have to tell us whether
    Joe> it's safe and the details are right.  Conceptually, it seems
    Joe> OK, but that might just reflect my ignorance.

Right.  I really want to get Richard's instinctive reaction before
doing anything, since he knows the code in question best.

    >> - Whether or not we need to fix this for GCC 3.0.

    Joe> performance across the board, so I'd like to see it go in
    Joe> unless the gurus consider it unsafe.  Of course, I'm assuming
    Joe> no regressions on primary release platforms.

My thoughts as well.  The good news is that we're just reusing
functionality that we use elsewhere in the compiler -- it's not like I
dreamed up a new optimization.  The life_analysis code has been beaten
on very heavily at this point, and it's pretty stable, so I don't
anticipate problems -- as long as I used it correctly.  

It would be very helpful if Richard (or someone else who knows) could
add documentation for the following two things:

  - In rest_of_compilation, indicate where the basic-block graph is 
    known to be valid and where it is known to be invalid. 

  - Explain more clearly the caveats about calling life_analysis.
    When do you need which flags?  Not just what do they do, but 
    when do we need what.  Do I need to worry about LOG_LINKS here,
    etc.?

Thanks for the feedback,

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

Re: Stepanov, PowerPC, life_analysis

[Mark Mitchell]

>>>>> "Richard" == Richard Henderson <rth@redhat.com> writes:

    Richard> Yep.  CSE doesn't maintain the CFG while simplifying or
    Richard> eliminating branches, so rebuilding it is necessary.  You
    Richard> do want to add a call to cleanup_cfg though.  The flags
    Richard> to life_analysis are right.

Great.  To make sure I'm clear: I call cleanup_cfg right after
find_basic_blocks to blow away unreachable blocks entirely, right?

    Richard> I do suggest that we move this a bit earlier -- before
    Richard> the call to renumber_insns.

Yes, that makes sense.

I feel much better that you've confirmed the rightness here.  I'll
make the changes, retest the patch, and check it in.

Thanks,

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

Re: Stepanov, PowerPC, life_analysis

[Richard Henderson]

On Sat, Jun 09, 2001 at 11:50:15AM -0700, Mark Mitchell wrote:
> Great.  To make sure I'm clear: I call cleanup_cfg right after
> find_basic_blocks to blow away unreachable blocks entirely, right?

Exactly.


r~

Re: Stepanov, PowerPC, life_analysis

[Richard Henderson]

On Sat, Jun 09, 2001 at 11:48:05AM -0700, Mark Mitchell wrote:
>   - In rest_of_compilation, indicate where the basic-block graph is 
>     known to be valid and where it is known to be invalid. 

Unfortunately, very few of our optimizations preserve the CFG.
But it would certainly be possible to note which do.

>   - Explain more clearly the caveats about calling life_analysis.
>     When do you need which flags?  Not just what do they do, but 
>     when do we need what.  Do I need to worry about LOG_LINKS here,
>     etc.?

Hmm.  I'll see what I can come up with.


r~

Re: Stepanov, PowerPC, life_analysis

[Mark Mitchell]

>>>>> "Richard" == Richard Henderson <rth@redhat.com> writes:

    Richard> On Sat, Jun 09, 2001 at 11:48:05AM -0700, Mark Mitchell
    Richard> wrote:
    >> - In rest_of_compilation, indicate where the basic-block graph
    >> is known to be valid and where it is known to be invalid.

    Richard> Unfortunately, very few of our optimizations preserve the
    Richard> CFG. 

Bummer, that's what I thought.   One of these days, we should make
them dynamically update the CFG as they go.

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