[RFC] Using equivalences to help eliminate_regs_in_insn

I've found a case of suboptimal code coming from LRA when we have a large
frame and have the frame grow downwards with MIPS. A good testcase for
this is the qsort benchmark from the automotive section of mibench[1].

Any frame access where the offset is not supported as an add-immediate
should benefit from this fix. It will probably have little or no effect
when frames grow upwards.  The patch is just prototype for now as it
has had very little testing beyond it looking like it does the right
thing.

@Vladimir: The affected code is in eliminate_regs_in_insn where
there is a comment (history suggests you wrote it) that says:

  /* We allow one special case which happens to work on all machines we
     currently support: a single set with the source or a REG_EQUAL
     note being a PLUS of an eliminable register and a constant.  */

There is an implementation that optimises a single set but not one for
a REG_EQUAL. Do you have any recollection of this code and do you think
there was a reason you didn't implement the REG_EQUAL case? Either way
any advice on my approach is welcome.

Below is an example of RTL pre/post LRA both without and with my patch
applied:

== RTL after IRA ==
(insn 96 95 97 4 (set (reg:SI 299)
        (const_int -1441792 [0xffffffffffea0000])) 310 {*movsi_internal}
     (expr_list:REG_EQUIV (const_int -1441792 [0xffffffffffea0000])
        (nil)))
(insn 97 96 98 4 (set (reg:SI 298)
        (plus:SI (reg:SI 299)
            (const_int 1792 [0x700]))) 13 {*addsi3}
     (expr_list:REG_DEAD (reg:SI 299)
        (expr_list:REG_EQUIV (const_int -1440000 [0xffffffffffea0700])
            (nil))))
(insn 98 97 71 4 (set (reg:SI 282 [ ivtmp.21 ])
        (plus:SI (reg/f:SI 78 $frame)
            (reg:SI 298))) 13 {*addsi3}
     (expr_list:REG_DEAD (reg:SI 298)
        (nil)))

== RTL after LRA ==

(insn 96 95 97 4 (set (reg:SI 16 $16 [299])
        (const_int -1441792 [0xffffffffffea0000])) 310 {*movsi_internal}
     (expr_list:REG_EQUIV (const_int -1441792 [0xffffffffffea0000])
        (nil)))
(insn 97 96 249 4 (set (reg:SI 16 $16 [298])
        (plus:SI (reg:SI 16 $16 [299])
            (const_int 1792 [0x700]))) 13 {*addsi3}
     (expr_list:REG_EQUIV (const_int -1440000 [0xffffffffffea0700])
        (nil)))
(insn 249 97 250 4 (set (reg:SI 3 $3 [342])
        (const_int 1376256 [0x150000])) 310 {*movsi_internal}
     (nil))
(insn 250 249 289 4 (set (reg:SI 2 $2 [341])
        (ior:SI (reg:SI 3 $3 [342])
            (const_int 63776 [0xf920]))) 185 {*iorsi3}
     (expr_list:REG_EQUAL (const_int 1440032 [0x15f920])
        (nil)))
(insn 289 250 251 4 (set (reg:SI 4 $4 [363])
        (plus:SI (reg/f:SI 29 $sp)
            (const_int 24 [0x18]))) 13 {*addsi3}
     (nil))
(insn 251 289 98 4 (set (reg:SI 2 $2 [341])
        (plus:SI (reg:SI 2 $2 [341])
            (reg:SI 4 $4 [363]))) 13 {*addsi3}
     (nil))
(insn 98 251 71 4 (set (reg:SI 16 $16 [orig:282 ivtmp.21 ] [282])
        (plus:SI (reg:SI 2 $2 [341])
            (reg:SI 16 $16 [298]))) 13 {*addsi3}
     (nil))

== new RTL after LRA ==

(note 96 95 97 4 NOTE_INSN_DELETED)
(note 97 96 98 4 NOTE_INSN_DELETED)
(insn 98 97 71 4 (set (reg:SI 16 $16 [orig:282 ivtmp.21 ] [282])
        (plus:SI (reg/f:SI 29 $sp)
            (const_int 48 [0x30]))) 13 {*addsi3}
     (nil))

The frame is 8 bytes smaller due to one less spill which is why
32+24 != 48.  Obviously the code size improvement when this triggers
is quite good. Build options: mips-mti-elf-gcc -Os -mmicromips
-mabi=32 -msoft-float -EL -mips32r2 -fstack-protector

The -fstack-protector forces the frame to grow downwards.

Any advice/comments welcome...

Thanks,
Matthew

[1] http://vhosts.eecs.umich.edu/mibench//source.html

gcc/

	* lra-eliminations.c (remove_reg_equal_offset_note): Use
	ira_reg_equiv to optimise offsets when eliminating the
	frame pointer.

On 09/06/2016 11:22 AM, Matthew Fortune wrote:
> There is an implementation that optimises a single set but not one for
> a REG_EQUAL. Do you have any recollection of this code and do you think
> there was a reason you didn't implement the REG_EQUAL case? Either way
> any advice on my approach is welcome.
Matt, sorry for delay with the answer.  I had a long vacation.

I did not write the code.  I mostly took it from the old register 
allocator practically without any changes.
Looking at your prototype patch, I think you are doing an optimization 
which can be important for many targets.  Moreover, the optimization 
probably will be frequently applied for these targets.

I believe you should produce a final patch, test it well and submit it.

Thank you for finding the optimization opportunity and working on 
implementing it.

Vladimir N Makarov <vmakarov@redhat.com> writes:
> On 09/06/2016 11:22 AM, Matthew Fortune wrote:
> > There is an implementation that optimises a single set but not one for
> > a REG_EQUAL. Do you have any recollection of this code and do you
> > think there was a reason you didn't implement the REG_EQUAL case?
> > Either way any advice on my approach is welcome.
> Matt, sorry for delay with the answer.  I had a long vacation.
> 
> I did not write the code.  I mostly took it from the old register
> allocator practically without any changes.
> Looking at your prototype patch, I think you are doing an optimization
> which can be important for many targets.  Moreover, the optimization
> probably will be frequently applied for these targets.
> 
> I believe you should produce a final patch, test it well and submit it.
> 
> Thank you for finding the optimization opportunity and working on
> implementing it.

Thanks, I'll keep working on it and get a patch submitted. It may take a
little while but it will get done.

Matthew