[Bug target/45980] New: Use not in stead of add to generate new constant

[Bug target/45980] New: Use not in stead of add to generate new constant

[carrot at google dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45980

           Summary: Use not in stead of add to generate new constant
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: target
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: carrot@google.com
                CC: carrot@google.com
              Host: i686-linux
            Target: arm-eabi
             Build: i686-linux


Compile the following code:

typedef struct {
      unsigned long state[5];
      unsigned long count[2];
} SHA1_CTX;

void SHA1Init(SHA1_CTX* context)
{
      /* SHA1 initialization constants */
      context->state[0] = 0x67452301;
      context->state[1] = 0xEFCDAB89;
      context->state[2] = 0x98BADCFE;
      context->state[3] = 0x10325476;
      context->state[4] = 0xC3D2E1F0;
      context->count[0] = context->count[1] = 0;
}

With options -march=armv7-a -mthumb -Os, gcc generates:

SHA1Init:
        ldr     r3, .L2
        str     r3, [r0, #0]
        add     r3, r3, #-2004318072    
        str     r3, [r0, #4]
        ldr     r3, .L2+4
        str     r3, [r0, #8]
        sub     r3, r3, #-2004318072     
        str     r3, [r0, #12]
        ldr     r3, .L2+8
        str     r3, [r0, #16]
        movs    r3, #0
        str     r3, [r0, #24]
        str     r3, [r0, #20]
        bx      lr
.L3:
        .align  2
.L2:
        .word   1732584193
        .word   -1732584194
        .word   -1009589776

This function needs to store 5 large constants to memory. Instead of load the 5
constants from constant pool, gcc found two of them can be computed out by a
single add/sub constant instruction. But we can do better, notice that

0x67452301 + 0x98BADCFE = 0xFFFFFFFF
0xEFCDAB89 + 0x10325476 = 0xFFFFFFFF

So if we have one such constant, the other one can be computed out by bitwise
not. So a shorter result could be:

SHA1Init:
        ldr     r3, .L2
        str     r3, [r0, #0]
        add     r2, r3, #-2004318072    
        str     r2, [r0, #4]
        movns     r3, r3
        str     r3, [r0, #8]
        movns     r2, r2
        str     r2, [r0, #12]
        ldr     r3, .L2+4
        str     r3, [r0, #16]
        movs    r3, #0
        str     r3, [r0, #24]
        str     r3, [r0, #20]
        bx      lr
.L3:
        .align  2
.L2:
        .word   1732584193
        .word   -1009589776

[Bug target/45980] Use not in stead of add to generate new constant

[ramana at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45980

Ramana Radhakrishnan <ramana at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2010.10.14 02:14:48
                 CC|                            |ramana at gcc dot gnu.org
     Ever Confirmed|0                           |1

[Bug target/45980] Use not in stead of add to generate new constant

[carrot at google dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45980

--- Comment #1 from Carrot <carrot at google dot com> 2010-10-18 06:24:04 UTC ---
The replacement of constant loading with add operations is occurred at pass
postreload in function reload_cse_move2add. It is straight forward to extend
that to other ALU operations, such as not, and, or, xor, shift ...

But there is a problem as shown in this example. 

      context->state[0] = 0x67452301;    // r3
      context->state[1] = 0xEFCDAB89;
      context->state[2] = 0x98BADCFE;
      context->state[3] = 0x10325476;

After the first statement, value 0x67452301 is in register r3, and after the
second statement, value 0xEFCDAB89 is in r3, and the original value 0x67452301
is lost, so we can't get the third value by simple "movns r3, r3". We need some
form of register renaming at the same time.

[Bug target/45980] Use not in stead of add to generate new constant

[rearnsha at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45980

Richard Earnshaw <rearnsha at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

[Bug target/45980] Use not in stead of add to generate new constant

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=45980

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
For the original testcase on the trunk we get:
        ldr     r3, .L2
        str     r3, [r0]
        add     r3, r3, #-2004318072
        str     r3, [r0, #4]
        add     r3, r3, #-1459617792
        sub     r3, r3, #1228800
        subw    r3, r3, #3723
        str     r3, [r0, #8]
        sub     r3, r3, #-2004318072
        str     r3, [r0, #12]
        ldr     r3, .L2+4
        str     r3, [r0, #16]
        movs    r3, #0
        strd    r3, r3, [r0, #20]
        bx      lr
.L3:
        .align  2
.L2:
        .word   1732584193
        .word   -1009589776