Post-register-allocation opportunitistic optimizer?

Post-register-allocation opportunitistic optimizer?

[tm]

I'm looking through H8/300h code, and I realize I want a
post-register-allocation opportunitistic optimizer.

To explain, I need to backtrack a bit. In the past, I've mentioned that
GCC handles high register pressure badly, and it should rerun the
optimizer over the original RTX with flags set to avoid generating new
pseudos.

I think this situation may be better handled by some sort of
post-register-allocation opportunitistic optimizer.

To explain simply, we would initially generate code which uses minial
scratch registers, then PRAOO would run after register allocation and
opportunistically replace slow code sequence which require no scratch
register with faster code sequences which require a scratch
register ONLY IF an unused hard register is available.

For example, GCC generates this code for a right shift by 8 on the
H8/300H:

        mov.w   e0,r2
        mov.b   r0h,r0l
        mov.b   r2l,r0h
        mov.b   r2h,r2l
        exts.w  r2
        mov.w   r2,e0

This is fast code but it uses an extra register (r2). It is undesirable if
the compiled function is complex and the register pressure is already
high. In a high register pressure case, we would probably want:

	shar.l	er0
	shar.l	er0
	shar.l	er0
	shar.l	er0
	shar.l	er0
	shar.l	er0
	shar.l	er0
	shar.l	er0

which is slower but avoids using a scratch register, and thus avoids
spilling a register.

I know the Hitachi SH has the same problem, because the earlier
implementations (SH1 and SH2) lack a barrel shifter and have only
instructions with fixed shift counts.

My first question is: are there other processors which must choose between
code which is "faster and uses scratch register" vs. "slower and no
scratch register"? 

I'm assuming other processors have the same problem. If so, it sounds
better to implement a generic solution rather than hack a 
MACHINE_DEPENDENT_REORG.

The second question is the appropriate implementation of such a feature.
I can think of a few different implementations:

1. Hack register allocation to handle this. This sounds ugly.

2. Hack combine to understand register pressure and rerun after
   reload. This also sounds ugly.

3. New optimizer pass which runs after global alloc which 
   opportunistically replaces slow sequences with fast sequences if hard
   registers are available.

Is #3 the right solution, or are there better solutions available?

Toshi

Re: Post-register-allocation opportunitistic optimizer?

[Richard Henderson]

On Fri, May 03, 2002 at 01:12:47PM -0700, tm wrote:
> 3. New optimizer pass which runs after global alloc which 
>    opportunistically replaces slow sequences with fast sequences if hard
>    registers are available.

See -frename-registers and/or the documentation for define_peephole2.


r~

Re: Post-register-allocation opportunitistic optimizer?

[tm]

On Fri, 3 May 2002, Richard Henderson wrote:

> On Fri, May 03, 2002 at 01:12:47PM -0700, tm wrote:
> > 3. New optimizer pass which runs after global alloc which 
> >    opportunistically replaces slow sequences with fast sequences if hard
> >    registers are available.
> 
> See -frename-registers and/or the documentation for define_peephole2.

define_peephole2 comes close, but doesn't quite solve the problem.

Consider a basic block contains multiple opportunistically optimizable
sequences, and two free hard registers.

If I understand correctly, define_peephole2 will optimize the first two
sequences (assuming they both use one hard reg apiece) and fail to
optimize the rest of the cases.

Ideally, the optimizer would sort the opportunities by benefit and only
perform the best N optimizations rather than simply optimize the first N
sequences.

Could peephole2 be modified to accomodate this, or is it better
implemented as a separate pass?

Toshi

Re: Post-register-allocation opportunitistic optimizer?

[Peter Barada]

>If I understand correctly, define_peephole2 will optimize the first two
>sequences (assuming they both use one hard reg apiece) and fail to
>optimize the rest of the cases.

I think peephole2 works backwards from the end of the function to the
front, so it would optimize the last two sequences...

-- 
Peter Barada                                   Peter.Barada@motorola.com
Wizard                                         781-852-2768 (direct)
WaveMark Solutions(wholly owned by Motorola)   781-270-0193 (fax)

Re: Post-register-allocation opportunitistic optimizer?

[Richard Henderson]

On Fri, May 03, 2002 at 02:42:02PM -0700, tm wrote:
> If I understand correctly, define_peephole2 will optimize the first two
> sequences (assuming they both use one hard reg apiece) and fail to
> optimize the rest of the cases.

Why do you think this?  The set of live registers is recomputed
for every independent peep2 optimization.  Thus they should all
be optimized.


r~

Re: Post-register-allocation opportunitistic optimizer?

[tm]

On Fri, 3 May 2002, Richard Henderson wrote:

> On Fri, May 03, 2002 at 02:42:02PM -0700, tm wrote:
> > If I understand correctly, define_peephole2 will optimize the first two
> > sequences (assuming they both use one hard reg apiece) and fail to
> > optimize the rest of the cases.
> 
> Why do you think this?  The set of live registers is recomputed
> for every independent peep2 optimization.  Thus they should all
> be optimized.

Maybe I didn't communicate well.

Imagine a situation in a basic block with two hard registers free.
An analysis of the code reveals the following possible optimizations:

optimization    scratch hard regs       RTX_COST
opportunity         required            benefit
-----------------------------------------------
   #1                 1                   3
   #2                 1                   5
   #3                 2                  11

In this case, if you perform optimization #1 first, then there is only
one hard register free, and only optimization #2 can be performed for a
total benefit of 3 + 5 = 8.

However, better heuristics should decide to spend the two hard registers
on optimization #3 which yields a net benefit of 11, which is better than
optimizations #1 and #2 combined.

Toshi

Re: Post-register-allocation opportunitistic optimizer?

[Richard Henderson]

On Fri, May 03, 2002 at 03:49:58PM -0700, tm wrote:
> Imagine a situation in a basic block with two hard registers free.
> An analysis of the code reveals the following possible optimizations:
> 
> optimization    scratch hard regs       RTX_COST
> opportunity         required            benefit
> -----------------------------------------------
>    #1                 1                   3
>    #2                 1                   5
>    #3                 2                  11
> 
> In this case, if you perform optimization #1 first, then there is only
> one hard register free,

Stop.  You are already incorrect.

The register used in a peep2 will _only_ be used within that single
peephole pattern, thus it is dead after the matched sequence, thus
there are two free registers for _every_ matched sequence.

If you're thinking of this in combination with some post-reload CSE
pass, peep2 won't do.  In fact it sounds like nothing but a better
register allocator will do.


r~

Re: Post-register-allocation opportunitistic optimizer?

[tm]

On Fri, 3 May 2002, Richard Henderson wrote:

> On Fri, May 03, 2002 at 03:49:58PM -0700, tm wrote:
> > Imagine a situation in a basic block with two hard registers free.
> > An analysis of the code reveals the following possible optimizations:
> > 
> > optimization    scratch hard regs       RTX_COST
> > opportunity         required            benefit
> > -----------------------------------------------
> >    #1                 1                   3
> >    #2                 1                   5
> >    #3                 2                  11
> > 
> > In this case, if you perform optimization #1 first, then there is only
> > one hard register free,
> 
> Stop.  You are already incorrect.
> 
> The register used in a peep2 will _only_ be used within that single
> peephole pattern, thus it is dead after the matched sequence, thus
> there are two free registers for _every_ matched sequence.

Ah, I made a bad assumption. I understand this now.

So we can naively emit long sequences of single shifts, and have peep2
clean it up for us later if hard registers are available. Nice!

Toshi

Re: Post-register-allocation opportunitistic optimizer?

[Richard Henderson]

On Fri, May 03, 2002 at 04:46:03PM -0700, tm wrote:
> So we can naively emit long sequences of single shifts, and have peep2
> clean it up for us later if hard registers are available. Nice!

Um, except that peep2 only works with adjacent instructions.
You're probably better off modeling these as a single insn
through reload and splitting them with peep2.


r~

Re: Post-register-allocation opportunitistic optimizer?

[Kazu Hirata]

Hi Toshi,

> For example, GCC generates this code for a right shift by 8 on the
> H8/300H:
> 
>         mov.w   e0,r2
>         mov.b   r0h,r0l
>         mov.b   r2l,r0h
>         mov.b   r2h,r2l
>         exts.w  r2
>         mov.w   r2,e0

I was thinking about the same thing.  Shifts that require loops are in
the same situation.  Also, if you want to use stw.l for argument push
on H8/S, you need to know what registers are available, but this might
require MACHINE_DEPENDENT_REORG.

> 3. New optimizer pass which runs after global alloc which 
>    opportunistically replaces slow sequences with fast sequences if hard
>    registers are available.

This sounds very reasonable to me.

Kazu Hirata

Re: Post-register-allocation opportunitistic optimizer?

[law]

In message <20020503.172316.55515951.kazu@cs.umass.edu>, Kazu Hirata writes:
 > Hi Toshi,
 > 
 > > For example, GCC generates this code for a right shift by 8 on the
 > > H8/300H:
 > > 
 > >         mov.w   e0,r2
 > >         mov.b   r0h,r0l
 > >         mov.b   r2l,r0h
 > >         mov.b   r2h,r2l
 > >         exts.w  r2
 > >         mov.w   r2,e0
 > 
 > I was thinking about the same thing.  Shifts that require loops are in
 > the same situation.  Also, if you want to use stw.l for argument push
 > on H8/S, you need to know what registers are available, but this might
 > require MACHINE_DEPENDENT_REORG.
 > 
 > > 3. New optimizer pass which runs after global alloc which 
 > >    opportunistically replaces slow sequences with fast sequences if hard
 > >    registers are available.
 > 
 > This sounds very reasonable to me.
Look at how peephole2 works.  It's designed to be able to replace one sequence
with another (possibly faster, smaller, whatever) when hard registers are
available.

jeff