[Bug c/21970] New: Inline keyword causes computation to erroneously reduce to a constant

[Bug c/21970] New: Inline keyword causes computation to erroneously reduce to a constant

[para at cfl dot rr dot com]

I have a function which evaluates the SHA-1 cryptographic hash function. It 
takes as parameters the 160-bit state and 64 bytes to hash and produces an 
output 160-bit state. When compiling at -O0, it is horrendously slow, but it 
(as far as I know) produces correct behavior. For quick reference, a (brief) 
function definition follows:


typedef unsigned long UINT32;

typedef struct
{
	UINT32 a, b, c, d, e;
} SHA1_STATE;

void sha1(SHA1_STATE *pState, void const *pvBuf);


At -O1 and above, the SHA-1 function is reduced to the following code:


_sha1:
	pushl	%ebp
	movl	%esp, %ebp
	movl	8(%ebp), %eax
	movl	$0, (%eax)
	movl	$0, 4(%eax)
	movl	$0, 8(%eax)
	movl	$0, 12(%eax)
	movl	$0, 16(%eax)
	popl	%ebp
	ret


Because this file is autogenerated, I generate function calls to do trivial 
operations such as addition and rely on function inlining to preserve 
performance. If these functions are not marked with the inline keyword, then 
this bug does not trigger. Also, I tried removing roughly half of the code from 
the function, and it cause the bug to no longer trigger. I removed all code 
below line 316 and simply copied the final 5 keys from the key schedule (w75, 
w76, w77, w78, w79) to the output state.

I have observed the same behavior on MinGW GCC versions 3.3.1 and 3.4.2. The 
output of gcc -v for the version I am reporting against is as follows:

Reading specs from /usr/lib/gcc/i686-pc-linux-gnu/3.4.4/specs
Configured with: /var/tmp/portage/gcc-3.4.4/work/gcc-3.4.4/configure --enable-
version-specific-runtime-libs --prefix=/usr --bindir=/usr/i686-pc-linux-gnu/gcc-
bin/3.4.4 --includedir=/usr/lib/gcc/i686-pc-linux-gnu/3.4.4/include --
datadir=/usr/share/gcc-data/i686-pc-linux-gnu/3.4.4 --mandir=/usr/share/gcc-
data/i686-pc-linux-gnu/3.4.4/man --infodir=/usr/share/gcc-data/i686-pc-linux-
gnu/3.4.4/info --with-gxx-include-dir=/usr/lib/gcc/i686-pc-linux-
gnu/3.4.4/include/g++-v3 --host=i686-pc-linux-gnu --disable-altivec --enable-
nls --without-included-gettext --with-system-zlib --disable-checking --disable-
werror --disable-libunwind-exceptions --disable-multilib --disable-libgcj --
enable-languages=c,c++ --enable-shared --enable-threads=posix --enable-
__cxa_atexit --enable-clocale=gnu
Thread model: posix
gcc version 3.4.4 (Gentoo Hardened 3.4.4, ssp-3.4.4-1.0, pie-8.7.8)

-- 
           Summary: Inline keyword causes computation to erroneously reduce
                    to a constant
           Product: gcc
           Version: 3.4.4
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: para at cfl dot rr dot com
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu


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

[Bug c/21970] Inline keyword causes computation to erroneously reduce to a constant

[para at cfl dot rr dot com]

------- Additional Comments From para at cfl dot rr dot com  2005-06-08 23:01 -------
Created an attachment (id=9047)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=9047&action=view)
The stand-alone source file


-- 


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

[Bug rtl-optimization/21970] Inline keyword causes computation to erroneously reduce to a constant

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c                           |rtl-optimization
           Keywords|                            |wrong-code
      Known to work|                            |4.1.0


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

[Bug rtl-optimization/21970] [3.4 only] Inline keyword causes computation to erroneously reduce to a constant

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-06-08 23:14 -------
Confirmed, but this looks like only a bug in 3.4.x and before.  It might be a latent bug on the mainline 
still I don't know for sure.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
      Known to fail|                            |2.95.3 3.4.0 3.3.3 3.2.3
                   |                            |3.0.4
      Known to work|4.1.0                       |4.1.0 4.0.0
   Last reconfirmed|0000-00-00 00:00:00         |2005-06-08 23:14:27
               date|                            |
            Summary|Inline keyword causes       |[3.4 only] Inline keyword
                   |computation to erroneously  |causes computation to
                   |reduce to a constant        |erroneously reduce to a
                   |                            |constant
   Target Milestone|---                         |3.4.5


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

[Bug rtl-optimization/21970] [3.4 only] Inline keyword causes computation to erroneously reduce to a constant

[rsandifo at gcc dot gnu dot org]

------- Additional Comments From rsandifo at gcc dot gnu dot org  2005-07-04 13:49 -------
Are you sure this reduced testcase is an accurate reflection of the
real one?  The transformation performed by gcc appears to be correct.
For example, r00450DB4 evaluates to 0, so anything ANDed with it
does too.

Here's an attempt to show why.  I've snipped part of the code and
annotated it with comments of the form:

    <rhs> = op (<lhs>) :<nonzero bits>

where <lhs> uses "_" for "don't care" values.  <nonzero bits> is the
mask of bits that _might_ be nonzero.  In other words, zero bits
mean "known to be zero" and one bits mean "value unknown".

-------------------------------------------------------------------------------
UINT32 r004458AC = opt_and(w00, 0x5A827999);	  // A = and (_, cst) :5a827999
UINT32 r00445934 = opt_and(r004457EC, r004458AC); // B = and (_, A)   :5a827999
UINT32 r004459BC = opt_and(r0044572C, r00445934); // C = and (_, B)   :5a827999
...
UINT32 r0044F67C = opt_and(ie, r004459BC);	  // D = and (_, C)   :5a827999
...
UINT32 r0044FA14 = opt_rotl(r0044F67C, 5);	  // E = rotl (D, 5)  :504f332b
UINT32 r0044FAD4 = opt_and(w01, 0x5A827999);	  // F = and (_, cst) :5a827999
UINT32 r0044FB5C = opt_and(r0044FA14, r0044FAD4); // G = and (E, F)   :50023109
UINT32 r0044FBE4 = opt_and(r0044F954, r0044FB5C); // H = and (_, G)   :50023109
UINT32 r0044FC6C = opt_and(id, r0044FBE4);	  // I = and (_, H)   :50023109
...
UINT32 r00450004 = opt_rotl(r0044FC6C, 5);	  // J = rotl (I, 5)  :0046212a
UINT32 r004500C4 = opt_and(w02, 0x5A827999);	  // K = and (_, cst) :5a827999
UINT32 r0045014C = opt_and(r00450004, r004500C4); // L = and (J, K)   :00022108
UINT32 r004501D4 = opt_and(r0044FF44, r0045014C); // M = and (_, L)   :00022108
UINT32 r0045025C = opt_and(ic, r004501D4);	  // N = and (_, M)   :00022108
...
UINT32 r0045031C = opt_rotl(r0044F67C, 30);	  // a = rotl (D, 30) :56a09e66
...
UINT32 r004505F4 = opt_rotl(r0045025C, 5);	  // O = rotl (N, 5)  :00442100
UINT32 r004506B4 = opt_and(w03, 0x5A827999);	  // P = and (_, cst) :5a827999
UINT32 r0045073C = opt_and(r004505F4, r004506B4); // Q = and (O, P)   :00002100
UINT32 r004507C4 = opt_and(r00450534, r0045073C); // R = and (_, Q)   :00002100
UINT32 r0045084C = opt_and(r0044F73C, r004507C4); // S = and (_, R)   :00002100
UINT32 r0045090C = opt_rotl(r0044FC6C, 30);	  // T = rotl (I, 30) :54008c42
UINT32 r00450994 = opt_not(r0045025C);		  // b = not (N)      :fffddef7
UINT32 r00450A14 = opt_and(r00450994, r0045031C); // c = and (b, a)   :56a09e66
...
UINT32 r00450A9C = opt_and(r0045025C, r0045090C); // U = and (N, T)   :00000000
UINT32 r00450B24 = opt_or(r00450A14, r00450A9C);  // V = or (c, U)    :56a09e66
UINT32 r00450BE4 = opt_rotl(r0045084C, 5);	  // W = rotl (S, 5)  :00042000
UINT32 r00450CA4 = opt_and(w04, 0x5A827999);	  // X = and (_, cst) :5a827999
UINT32 r00450D2C = opt_and(r00450BE4, r00450CA4); // Y = and (W, X)   :00002000
UINT32 r00450DB4 = opt_and(r00450B24, r00450D2C); // Z = and (V, Y)   :00000000
-------------------------------------------------------------------------------

PS. Not that it matters for the code quoted above, but your opt_xor
function uses "+" instead of "^".


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rsandifo at gcc dot gnu dot
                   |                            |org
             Status|NEW                         |WAITING


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

[Bug rtl-optimization/21970] [3.4 only] Inline keyword causes computation to erroneously reduce to a constant

[rsandifo at gcc dot gnu dot org]

------- Additional Comments From rsandifo at gcc dot gnu dot org  2005-07-04 13:52 -------
Oops, the following line was bogus:

UINT32 r00450994 = opt_not(r0045025C);		  // b = not (N)      :fffddef7

the value should be ffffffff.  It doesn't affect the analysis though.


-- 


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

[Bug rtl-optimization/21970] [3.4 only] Inline keyword causes computation to erroneously reduce to a constant

[para at cfl dot rr dot com]

------- Additional Comments From para at cfl dot rr dot com  2005-07-05 14:40 -------
The analysis is slightly flawed. For example:

UINT32 r0045025C = opt_and(ic, r004501D4);	  // N = and (_, M)   :00022108
UINT32 r00450994 = opt_not(r0045025C);		  // b = not (N)      :fffddef7

Since you are using 1s to represent bits that are known to be 0 and 0s to 
represent bits whose value are completely unknown, b should be 00000000. All 
known 0s flip to 1s, and you can say nothing about the other bits because their 
values are all unknown.

However, I ran my own analysis and came to the same conclusion. It seems that 
the mistake was mine as I was using and (&) instead of add (+) for the round 
key. My appologies. Interestingly, GCC 4.0 does *not* catch this optimization 
opportunity.

-- 


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

[Bug rtl-optimization/21970] [3.4 only] Inline keyword causes computation to erroneously reduce to a constant

[rsandifo at gcc dot gnu dot org]

------- Additional Comments From rsandifo at gcc dot gnu dot org  2005-07-05 14:51 -------
> The analysis is slightly flawed. For example:
> 
> UINT32 r0045025C = opt_and(ic, r004501D4);	  // N = and (_, M)   :00022108
> UINT32 r00450994 = opt_not(r0045025C);		  // b = not (N)      :fffddef7
> 
> Since you are using 1s to represent bits that are known to be 0 and 0s
> to represent bits whose value are completely unknown, b should be
> 00000000. All known 0s flip to 1s, and you can say nothing about the
> other bits because their values are all unknown.

Yup.  I guess you didn't read comment #4 ;)

Anyway, thanks for the confirmation.  I'll close this as invalid.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |RESOLVED
         Resolution|                            |INVALID


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