[Bug c/20532] New: Bad code for DImode left shifts by 31 and then 1

[Bug c/20532] New: Bad code for DImode left shifts by 31 and then 1

[macro at linux-mips dot org]

gcc (GCC) 4.0.0 20050316 (prerelease) (from the gcc-4_0-branch branch) emits
bad code for DImode left shifts by 31 and then 1 (foo << 31 <<1).  Instead of
doing the shifts, both the lowpart (correctly) and the highpart (incorrectly)
word get zeroed.  If the shifts are replaced by ones by 30 and then 2 or by one
by 32, then the resulting code is correct.

 GCC has been built with the following configure and make options:

$ CC=i386-linux-gcc \
CXX=i386-linux-g++ \
F77=i386-linux-gfortran \
CFLAGS="-pipe -O2 -fomit-frame-pointer -mtune=i486" \
CXXFLAGS="-pipe -O2 -fomit-frame-pointer -mtune=i486" \
FCFLAGS="-pipe -O2 -fomit-frame-pointer -mtune=i486" \
CC_FOR_BUILD=i386-linux-gcc \
CFLAGS_FOR_BUILD="-pipe -O2 -fomit-frame-pointer -mtune=i486" \
CFLAGS_FOR_TARGET="-pipe -O2 -fomit-frame-pointer -mtune=i486" \
CXXFLAGS_FOR_TARGET="-pipe -O2 -fomit-frame-pointer -mtune=i486" \
FCFLAGS_FOR_TARGET="-pipe -O2 -fomit-frame-pointer -mtune=i486" \
INSTALL_PROGRAM='${INSTALL} -s' \
../configure --prefix=/usr --mandir='${datadir}/man' \
--with-local-prefix='${prefix}/local' \
--enable-shared \
--with-slibdir=/lib \
--enable-static \
--with-system-zlib \
--enable-threads \
--cache-file=config.cache \
--build=i386-linux --host=i386-linux --target=i386-linux
$ make 'BOOT_CFLAGS=-pipe -O2 -fomit-frame-pointer -mtune=i486' \
'STAGE1_CFLAGS=-pipe -O2 -fomit-frame-pointer -mtune=i486' \
'GCJFLAGS=-pipe -O2 -fomit-frame-pointer -mtune=i486' \
CXX_FOR_BUILD=i386-linux-g++ \
'CXXFLAGS_FOR_BUILD=-pipe -O2 -fomit-frame-pointer -mtune=i486' bootstrap

 Here is a simple test case that fails for me (the source C file only as you
seem not to want to receive *.s files):

unsigned long long int badshift(unsigned long long int v)
{
        return v << 31 << 1;
}

 The problem was originally discovered with a 4.0.0 snapshot from the trunk
dated 20050225, therefore it likely applies to 4.1.0, too.

-- 
           Summary: Bad code for DImode left shifts by 31 and then 1
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P1
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: macro at linux-mips dot org
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: i386-pc-linux-gnu
  GCC host triplet: i386-pc-linux-gnu
GCC target triplet: i386-pc-linux-gnu


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

[Bug c/20532] Bad code for DImode left shifts by 31 and then 1

[macro at linux-mips dot org]

------- Additional Comments From macro at linux-mips dot org  2005-03-18 13:50 -------
You need to pass at least -O1 when building this program to trigger the bug.

-- 


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

[Bug rtl-optimization/20532] [4.0/4.1 Regression] Bad code for DImode left shifts by 31 and then 1

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-03-18 13:55 -------
Confirmed with the following options on i686-pc-linux-gnu:
-O1  -march=i386

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
          Component|c                           |rtl-optimization
     Ever Confirmed|                            |1
           Keywords|                            |wrong-code
      Known to fail|                            |4.0.0
      Known to work|                            |3.4.0
   Last reconfirmed|0000-00-00 00:00:00         |2005-03-18 13:55:22
               date|                            |
            Summary|Bad code for DImode left    |[4.0/4.1 Regression] Bad
                   |shifts by 31 and then 1     |code for DImode left shifts
                   |                            |by 31 and then 1
   Target Milestone|---                         |4.0.0


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

[Bug rtl-optimization/20532] [4.0/4.1 Regression] Bad code for DImode left shifts by 31 and then 1

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-03-18 14:03 -------
This was introduced between 20040630 and 20040702.

-- 


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

[Bug rtl-optimization/20532] [4.0/4.1 Regression] Bad code for DImode left shifts by 31 and then 1

[aoliva at gcc dot gnu dot org]

------- Additional Comments From aoliva at gcc dot gnu dot org  2005-03-22 19:41 -------
Interesting...  This bug doesn't occur on a x86_64-linux-gnu-hosted native
compiler, even if you compile with -m32 in addition to the options in comment #2.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |aoliva at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2005-03-18 13:55:22         |2005-03-22 19:41:38
               date|                            |


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

[Bug rtl-optimization/20532] [4.0/4.1 Regression] Bad code for DImode left shifts by 31 and then 1

[aoliva at redhat dot com]

------- Additional Comments From aoliva at gcc dot gnu dot org  2005-03-23 02:41 -------
Subject: [PR rtl-optimization/20532] plus(ashift,ashift) -> mult may overflow

In the sample testcase, if HOST_WIDE_INT is 32-bits wide, we ended up
trying to simplify the two shifts into a single multiply.  The shift
by one was already represented as an add-to-itself.  In combine, we
turned the shifts by 31 substed into both operands of the plus into
multiply by ((HOST_WIDE_INT)1 << 31), and then added the two
coefficients, resulting zero.  Oops.

This patch arranges for us to represent coefficients as CONST_DOUBLEs
when needed, avoiding overflows in all cases, since the two
coefficients added are in the range
[HOST_WIDE_INT_MIN,2*HOST_WIDE_INT_MAX+1].

In order to generate the optimal code that we generate on a 64-bit
HOST_WIDE_INT host, I had to also get multiply simplification to apply
to CONST_DOUBLE exact log2 constants, such as those produced after the
patch.

Bootstrapping on amd64-linux-gnu.  Ok to install if it passes
regtesting?

Index: gcc/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	PR rtl-optimization/20532
	* simplify-rtx.c (simplify_binary_operation_1): Protect from
	overflow when adding coefficients for PLUS or MINUS.
	(simplify_binary_operation_1): Handle CONST_DOUBLE exact power of
	two as multiplier.

Index: gcc/simplify-rtx.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/simplify-rtx.c,v
retrieving revision 1.234
diff -u -p -r1.234 simplify-rtx.c
--- gcc/simplify-rtx.c 21 Mar 2005 14:30:51 -0000 1.234
+++ gcc/simplify-rtx.c 23 Mar 2005 02:30:15 -0000
@@ -1257,44 +1257,67 @@ simplify_binary_operation_1 (enum rtx_co
 
       if (! FLOAT_MODE_P (mode))
 	{
-	  HOST_WIDE_INT coeff0 = 1, coeff1 = 1;
+	  HOST_WIDE_INT coeff0h = 0, coeff1h = 0;
+	  unsigned HOST_WIDE_INT coeff0l = 1, coeff1l = 1;
 	  rtx lhs = op0, rhs = op1;
 
 	  if (GET_CODE (lhs) == NEG)
-	    coeff0 = -1, lhs = XEXP (lhs, 0);
+	    {
+	      coeff0l = -1;
+	      coeff0h = -1;
+	      lhs = XEXP (lhs, 0);
+	    }
 	  else if (GET_CODE (lhs) == MULT
 		   && GET_CODE (XEXP (lhs, 1)) == CONST_INT)
-	    coeff0 = INTVAL (XEXP (lhs, 1)), lhs = XEXP (lhs, 0);
+	    {
+	      coeff0l = INTVAL (XEXP (lhs, 1));
+	      coeff0h = INTVAL (XEXP (lhs, 1)) < 0 ? -1 : 0;
+	      lhs = XEXP (lhs, 0);
+	    }
 	  else if (GET_CODE (lhs) == ASHIFT
 		   && GET_CODE (XEXP (lhs, 1)) == CONST_INT
 		   && INTVAL (XEXP (lhs, 1)) >= 0
 		   && INTVAL (XEXP (lhs, 1)) < HOST_BITS_PER_WIDE_INT)
 	    {
-	      coeff0 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (lhs, 1));
+	      coeff0l = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (lhs, 1));
+	      coeff0h = 0;
 	      lhs = XEXP (lhs, 0);
 	    }
 
 	  if (GET_CODE (rhs) == NEG)
-	    coeff1 = -1, rhs = XEXP (rhs, 0);
+	    {
+	      coeff1l = -1;
+	      coeff1h = -1;
+	      rhs = XEXP (rhs, 0);
+	    }
 	  else if (GET_CODE (rhs) == MULT
 		   && GET_CODE (XEXP (rhs, 1)) == CONST_INT)
 	    {
-	      coeff1 = INTVAL (XEXP (rhs, 1)), rhs = XEXP (rhs, 0);
+	      coeff1l = INTVAL (XEXP (rhs, 1));
+	      coeff1h = INTVAL (XEXP (rhs, 1)) < 0 ? -1 : 0;
+	      rhs = XEXP (rhs, 0);
 	    }
 	  else if (GET_CODE (rhs) == ASHIFT
 		   && GET_CODE (XEXP (rhs, 1)) == CONST_INT
 		   && INTVAL (XEXP (rhs, 1)) >= 0
 		   && INTVAL (XEXP (rhs, 1)) < HOST_BITS_PER_WIDE_INT)
 	    {
-	      coeff1 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (rhs, 1));
+	      coeff1l = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (rhs, 1));
+	      coeff1h = 0;
 	      rhs = XEXP (rhs, 0);
 	    }
 
 	  if (rtx_equal_p (lhs, rhs))
 	    {
 	      rtx orig = gen_rtx_PLUS (mode, op0, op1);
-	      tem = simplify_gen_binary (MULT, mode, lhs,
-					 GEN_INT (coeff0 + coeff1));
+	      rtx coeff;
+	      unsigned HOST_WIDE_INT l;
+	      HOST_WIDE_INT h;
+
+	      add_double (coeff0l, coeff0h, coeff1l, coeff1h, &l, &h);
+	      coeff = immed_double_const (l, h, mode);
+
+	      tem = simplify_gen_binary (MULT, mode, lhs, coeff);
 	      return rtx_cost (tem, SET) <= rtx_cost (orig, SET)
 		? tem : 0;
 	    }
@@ -1405,46 +1428,67 @@ simplify_binary_operation_1 (enum rtx_co
 
       if (! FLOAT_MODE_P (mode))
 	{
-	  HOST_WIDE_INT coeff0 = 1, coeff1 = 1;
+	  HOST_WIDE_INT coeff0h = 0, negcoeff1h = -1;
+	  unsigned HOST_WIDE_INT coeff0l = 1, negcoeff1l = -1;
 	  rtx lhs = op0, rhs = op1;
 
 	  if (GET_CODE (lhs) == NEG)
-	    coeff0 = -1, lhs = XEXP (lhs, 0);
+	    {
+	      coeff0l = -1;
+	      coeff0h = -1;
+	      lhs = XEXP (lhs, 0);
+	    }
 	  else if (GET_CODE (lhs) == MULT
 		   && GET_CODE (XEXP (lhs, 1)) == CONST_INT)
 	    {
-	      coeff0 = INTVAL (XEXP (lhs, 1)), lhs = XEXP (lhs, 0);
+	      coeff0l = INTVAL (XEXP (lhs, 1));
+	      coeff0h = INTVAL (XEXP (lhs, 1)) < 0 ? -1 : 0;
+	      lhs = XEXP (lhs, 0);
 	    }
 	  else if (GET_CODE (lhs) == ASHIFT
 		   && GET_CODE (XEXP (lhs, 1)) == CONST_INT
 		   && INTVAL (XEXP (lhs, 1)) >= 0
 		   && INTVAL (XEXP (lhs, 1)) < HOST_BITS_PER_WIDE_INT)
 	    {
-	      coeff0 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (lhs, 1));
+	      coeff0l = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (lhs, 1));
+	      coeff0h = 0;
 	      lhs = XEXP (lhs, 0);
 	    }
 
 	  if (GET_CODE (rhs) == NEG)
-	    coeff1 = - 1, rhs = XEXP (rhs, 0);
+	    {
+	      negcoeff1l = 1;
+	      negcoeff1h = 0;
+	      rhs = XEXP (rhs, 0);
+	    }
 	  else if (GET_CODE (rhs) == MULT
 		   && GET_CODE (XEXP (rhs, 1)) == CONST_INT)
 	    {
-	      coeff1 = INTVAL (XEXP (rhs, 1)), rhs = XEXP (rhs, 0);
+	      negcoeff1l = -INTVAL (XEXP (rhs, 1));
+	      negcoeff1h = INTVAL (XEXP (rhs, 1)) <= 0 ? 0 : -1;
+	      rhs = XEXP (rhs, 0);
 	    }
 	  else if (GET_CODE (rhs) == ASHIFT
 		   && GET_CODE (XEXP (rhs, 1)) == CONST_INT
 		   && INTVAL (XEXP (rhs, 1)) >= 0
 		   && INTVAL (XEXP (rhs, 1)) < HOST_BITS_PER_WIDE_INT)
 	    {
-	      coeff1 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (rhs, 1));
+	      negcoeff1l = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (rhs, 1));
+	      negcoeff1h = -1;
 	      rhs = XEXP (rhs, 0);
 	    }
 
 	  if (rtx_equal_p (lhs, rhs))
 	    {
 	      rtx orig = gen_rtx_MINUS (mode, op0, op1);
-	      tem = simplify_gen_binary (MULT, mode, lhs,
-					 GEN_INT (coeff0 - coeff1));
+	      rtx coeff;
+	      unsigned HOST_WIDE_INT l;
+	      HOST_WIDE_INT h;
+
+	      add_double (coeff0l, coeff0h, negcoeff1l, negcoeff1h, &l, &h);
+	      coeff = immed_double_const (l, h, mode);
+
+	      tem = simplify_gen_binary (MULT, mode, lhs, coeff);
 	      return rtx_cost (tem, SET) <= rtx_cost (orig, SET)
 		? tem : 0;
 	    }
@@ -1531,6 +1575,16 @@ simplify_binary_operation_1 (enum rtx_co
 	      || val != HOST_BITS_PER_WIDE_INT - 1))
 	return simplify_gen_binary (ASHIFT, mode, op0, GEN_INT (val));
 
+      /* Likewise for multipliers wider than a word.  */
+      else if (GET_CODE (trueop1) == CONST_DOUBLE
+	       && (GET_MODE (trueop1) == VOIDmode
+		   || GET_MODE_CLASS (GET_MODE (trueop1)) == MODE_INT)
+	       && GET_MODE (op0) == mode
+	       && CONST_DOUBLE_LOW (trueop1) == 0
+	       && (val = exact_log2 (CONST_DOUBLE_HIGH (trueop1))) >= 0)
+	return simplify_gen_binary (ASHIFT, mode, op0,
+				    GEN_INT (val + HOST_BITS_PER_WIDE_INT));
+
       /* x*2 is x+x and x*(-1) is -x */
       if (GET_CODE (trueop1) == CONST_DOUBLE
 	  && GET_MODE_CLASS (GET_MODE (trueop1)) == MODE_FLOAT
Index: gcc/testsuite/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	PR rtl-optimization/20532
	* gcc.target/i386/badshift.c: New.

Index: gcc/testsuite/gcc.target/i386/badshift.c
===================================================================
RCS file: gcc/testsuite/gcc.target/i386/badshift.c
diff -N gcc/testsuite/gcc.target/i386/badshift.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ gcc/testsuite/gcc.target/i386/badshift.c 23 Mar 2005 02:30:29 -0000
@@ -0,0 +1,28 @@
+/* PR rtl-optimization/20532 */
+
+/* { dg-do run } */
+/* { dg-options "-m32 -march=i386 -O1" } */
+
+/* We used to optimize the DImode shift-by-32 to zero because in combine
+   we turned:
+
+     (v << 31) * (v << 31)
+
+   into:
+
+     (v * (((HOST_WIDE_ITN)1 << 31) + ((HOST_WIDE_INT)1 << 31)))
+
+   With a 32-bit HOST_WIDE_INT, the coefficient overflowed to zero.  */
+
+unsigned long long int badshift(unsigned long long int v)
+{
+        return v << 31 << 1;
+}
+
+extern void abort ();
+
+int main() {
+  if (badshift (1) == 0)
+    abort ();
+  return 0;
+}

-- 
Alexandre Oliva             http://www.ic.unicamp.br/~oliva/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}


-- 


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

[Bug rtl-optimization/20532] [4.0/4.1 Regression] Bad code for DImode left shifts by 31 and then 1

[macro at linux-mips dot org]

------- Additional Comments From macro at linux-mips dot org  2005-03-23 12:15 -------
> +     (v * (((HOST_WIDE_ITN)1 << 31) + ((HOST_WIDE_INT)1 << 31)))
                          ^^^
 There is a typo above. Thanks for your fix.

-- 


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

[Bug rtl-optimization/20532] [4.0/4.1 Regression] Bad code for DImode left shifts by 31 and then 1

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-03-24 05:58 -------
Subject: Bug 20532

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	aoliva@gcc.gnu.org	2005-03-24 05:57:52

Modified files:
	gcc            : ChangeLog simplify-rtx.c 
	gcc/testsuite  : ChangeLog 
Added files:
	gcc/testsuite/gcc.target/i386: badshift.c 

Log message:
	gcc/ChangeLog:
	PR rtl-optimization/20532
	* simplify-rtx.c (simplify_binary_operation_1): Protect from
	overflow when adding coefficients for PLUS or MINUS.
	(simplify_binary_operation_1): Handle CONST_DOUBLE exact power of
	two as multiplier.
	gcc/testsuite/ChangeLog:
	PR rtl-optimization/20532
	* gcc.target/i386/badshift.c: New.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.7981&r2=2.7982
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/simplify-rtx.c.diff?cvsroot=gcc&r1=1.234&r2=1.235
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&r1=1.5205&r2=1.5206
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.target/i386/badshift.c.diff?cvsroot=gcc&r1=NONE&r2=1.1



-- 


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

[Bug rtl-optimization/20532] [4.0 Regression] Bad code for DImode left shifts by 31 and then 1

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-03-30 02:41 -------
Subject: Bug 20532

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	gcc-4_0-branch
Changes by:	aoliva@gcc.gnu.org	2005-03-30 02:41:35

Modified files:
	gcc            : ChangeLog simplify-rtx.c 
	gcc/testsuite  : ChangeLog 
Added files:
	gcc/testsuite/gcc.dg/torture: badshift.c 

Log message:
	gcc/ChangeLog:
	PR rtl-optimization/20532
	* simplify-rtx.c (simplify_binary_operation): Protect from
	overflow when adding coefficients for PLUS or MINUS.  Handle
	CONST_DOUBLE exact power of two as multiplier.
	gcc/testsuite/ChangeLog:
	PR rtl-optimization/20532
	* gcc.dg/torture/badshift.c: New.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=2.7592.2.91&r2=2.7592.2.92
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/simplify-rtx.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=1.230.2.1&r2=1.230.2.2
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=1.5084.2.76&r2=1.5084.2.77
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/torture/badshift.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=NONE&r2=1.1.2.1



-- 


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

[Bug rtl-optimization/20532] [4.0 Regression] Bad code for DImode left shifts by 31 and then 1

[aoliva at gcc dot gnu dot org]

------- Additional Comments From aoliva at gcc dot gnu dot org  2005-03-30 02:43 -------
Fixed in mainline and 4.0 branch.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


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