[Bug tree-optimization/46316] New: [4.6 regression] incorrect loop optimization

[Bug tree-optimization/46316] New: [4.6 regression] incorrect loop optimization

[ebotcazou at gcc dot gnu.org]

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

           Summary: [4.6 regression] incorrect loop optimization
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: ebotcazou@gcc.gnu.org


The Ada runtime (a-calend.adb) is miscompiled at -O2 on x86 at revision 166350.
An infinite loop is generated by the compiler in the UTC_Time_Offset function.

The reduced C testcase is just:

extern void abort (void);

long long __attribute__((noinline,noclone))
foo (long long t)
{
  while (t > -4)
    t -= 2;

  return t;
}

int main(void)
{
  if (foo (0) != -4)
    abort ();
  return 0;
}

eric@atlantis:~/build/gcc/native32> gcc/xgcc -Bgcc -o t t.c -O2
eric@atlantis:~/build/gcc/native32> ./t
^C
eric@atlantis:~/build/gcc/native32>

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[hjl.tools at gmail dot com]

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

--- Comment #1 from H.J. Lu <hjl.tools at gmail dot com> 2010-11-05 18:12:25 UTC ---
Please show command line passed to cc1.

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[hjl.tools at gmail dot com]

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

H.J. Lu <hjl.tools at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2010.11.05 18:16:45
     Ever Confirmed|0                           |1

--- Comment #2 from H.J. Lu <hjl.tools at gmail dot com> 2010-11-05 18:16:45 UTC ---
It only happens on 32bit host. It doesn't happen with -m32
on Linux/x86-64.

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[ebotcazou at gcc dot gnu.org]

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

--- Comment #3 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2010-11-05 18:42:38 UTC ---
> It only happens on 32bit host. It doesn't happen with -m32
> on Linux/x86-64.

Ah, interesting, thanks.  The wrong transformation is done by VRP2 but I fail
to see which recent change has triggered this exactly.  According to our
internal daily tester, this was introduced on 11/03.

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[hjl.tools at gmail dot com]

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

--- Comment #4 from H.J. Lu <hjl.tools at gmail dot com> 2010-11-05 18:53:25 UTC ---
Revision 166265 is OK.

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[hjl.tools at gmail dot com]

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

H.J. Lu <hjl.tools at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |davidxl at gcc dot gnu.org

--- Comment #5 from H.J. Lu <hjl.tools at gmail dot com> 2010-11-05 20:29:46 UTC ---
It is very likely caused by revision 166280:

http://gcc.gnu.org/ml/gcc-cvs/2010-11/msg00166.html

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[ebotcazou at gcc dot gnu.org]

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

--- Comment #6 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2010-11-06 10:05:21 UTC ---
> It is very likely caused by revision 166280:
> 
> http://gcc.gnu.org/ml/gcc-cvs/2010-11/msg00166.html

Indeed, this apparently exposed a bug in the scalar evolution analysis invoked
during the 2nd VRP pass.  This stuff always causes me headaches. :-)

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
   Target Milestone|---                         |4.6.0

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[xinliangli at gmail dot com]

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

davidxl <xinliangli at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|davidxl at gcc dot gnu.org  |xinliangli at gmail dot com

--- Comment #7 from davidxl <xinliangli at gmail dot com> 2010-11-07 21:12:12 UTC ---
It looks to me the problem is caused by double_int arithmetic (mul) overflow
which is not properly checked. This results in wrong value range and VRP
happily removes the cmp/jmp.

Why double_int does not use the widest int type for low/high part on the host?

David

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[ebotcazou at gcc dot gnu.org]

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

--- Comment #8 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2010-11-07 21:32:12 UTC ---
> Why double_int does not use the widest int type for low/high part on the host?

Not clear what you mean; it uses HOST_WIDE_INT like the rest of the compiler.

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[xinliangli at gmail dot com]

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

--- Comment #9 from davidxl <xinliangli at gmail dot com> 2010-11-07 23:22:30 UTC ---
For i686 target, the HOST_WIDE_INT is 'long int' -- not 'long long'.

David

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[xinliangli at gmail dot com]

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

--- Comment #10 from davidxl <xinliangli at gmail dot com> 2010-11-08 00:08:38 UTC ---
Need define need_64bit_host_wide_int in configuration which is not done by
default.

David

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[ebotcazou at gcc dot gnu.org]

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

--- Comment #11 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2010-11-08 00:53:17 UTC ---
> For i686 target, the HOST_WIDE_INT is 'long int' -- not 'long long'.

Yes, this is the default.  By default we don't require a 64-bit type on the
host for a 32-bit target, only for a 64-bit target.

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> 2010-11-08 07:03:37 UTC ---
Won't there be similar problem when using TImode IVs on 64-bit targets (e.g.
__int128 or int __attribute__((mode (TI)))) ?
Normally overflows are detected when doing computations on trees rather than
just in double_int.

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[xinliangli at gmail dot com]

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

--- Comment #13 from davidxl <xinliangli at gmail dot com> 2010-11-08 07:13:03 UTC ---
(In reply to comment #12)
> Won't there be similar problem when using TImode IVs on 64-bit targets (e.g.
> __int128 or int __attribute__((mode (TI)))) ?
> Normally overflows are detected when doing computations on trees rather than
> just in double_int.


yes. The following is the fix to this particular problem.


Index: tree-vrp.c
===================================================================
--- tree-vrp.c    (revision 166426)
+++ tree-vrp.c    (working copy)
@@ -3402,24 +3402,34 @@ adjust_range_with_scev (value_range_t *v
       || get_value_range (init)->type == VR_RANGE))
     {
       value_range_t maxvr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
-      double_int dtmp;
-      dtmp = double_int_mul (tree_to_double_int (step),
-                 double_int_sub (loop->nb_iterations_upper_bound,
-                         double_int_one));
-      tem = double_int_to_tree (TREE_TYPE (init), dtmp);
-      /* If the multiplication overflowed we can't do a meaningful
-     adjustment.  */
-      if (double_int_equal_p (dtmp, tree_to_double_int (tem)))
-    {
-      extract_range_from_binary_expr (&maxvr, PLUS_EXPR,
-                      TREE_TYPE (init), init, tem);
-      /* Likewise if the addition did.  */
-      if (maxvr.type == VR_RANGE)
-        {
-          tmin = maxvr.min;
-          tmax = maxvr.max;
-        }
-    }
+      double_int upper_bound_m1, step_int, dtmp;
+      bool unsigned_p;
+
+      upper_bound_m1 = double_int_sub (loop->nb_iterations_upper_bound,
+                                       double_int_one);
+      step_int = tree_to_double_int (step);
+      dtmp = double_int_mul (step_int, upper_bound_m1);
+      unsigned_p = TYPE_UNSIGNED (TREE_TYPE (step));
+      /* Check overflow.  */
+      if (double_int_equal_p (upper_bound_m1,
+                              double_int_div (dtmp, step_int,
+                                              unsigned_p, ROUND_DIV_EXPR)))
+        {
+          tem = double_int_to_tree (TREE_TYPE (init), dtmp);
+          /* If the multiplication overflowed we can't do a meaningful
+             adjustment.  */
+          if (double_int_equal_p (dtmp, tree_to_double_int (tem)))
+            {
+              extract_range_from_binary_expr (&maxvr, PLUS_EXPR,
+                                              TREE_TYPE (init), init, tem);
+              /* Likewise if the addition did.  */
+              if (maxvr.type == VR_RANGE)
+                {
+                  tmin = maxvr.min;
+                  tmax = maxvr.max;
+                }
+            }
+        }
     }

   if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[jakub at gcc dot gnu.org]

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

--- Comment #14 from Jakub Jelinek <jakub at gcc dot gnu.org> 2010-11-08 07:34:48 UTC ---
Instead of multiplication followed by division, it would be faster to just use
mul_double_with_sign which returns whether there was an overflow or not.

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[xinliangli at gmail dot com]

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

--- Comment #15 from davidxl <xinliangli at gmail dot com> 2010-11-08 07:38:17 UTC ---
(In reply to comment #14)
> Instead of multiplication followed by division, it would be faster to just use
> mul_double_with_sign which returns whether there was an overflow or not.

Good idea.

Thanks,

David

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[xinliangli at gmail dot com]

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

--- Comment #16 from davidxl <xinliangli at gmail dot com> 2010-11-08 08:18:31 UTC ---
The revised patch:


Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c    (revision 166426)
+++ gcc/tree-vrp.c    (working copy)
@@ -3403,13 +3403,18 @@ adjust_range_with_scev (value_range_t *v
     {
       value_range_t maxvr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
       double_int dtmp;
-      dtmp = double_int_mul (tree_to_double_int (step),
-                 double_int_sub (loop->nb_iterations_upper_bound,
-                         double_int_one));
+      bool unsigned_p = TYPE_UNSIGNED (TREE_TYPE (step));
+      int overflow = 0;
+
+      dtmp = double_int_mul_with_sign (tree_to_double_int (step),
+                                       double_int_sub (
+                                           loop->nb_iterations_upper_bound,
+                                           double_int_one),
+                                       unsigned_p, &overflow);
       tem = double_int_to_tree (TREE_TYPE (init), dtmp);
       /* If the multiplication overflowed we can't do a meaningful
      adjustment.  */
-      if (double_int_equal_p (dtmp, tree_to_double_int (tem)))
+      if (!overflow && double_int_equal_p (dtmp, tree_to_double_int (tem)))
     {
       extract_range_from_binary_expr (&maxvr, PLUS_EXPR,
                       TREE_TYPE (init), init, tem);
Index: gcc/double-int.c
===================================================================
--- gcc/double-int.c    (revision 166426)
+++ gcc/double-int.c    (working copy)
@@ -718,6 +718,19 @@ double_int_mul (double_int a, double_int
   return ret;
 }

+/* Returns A * B. If the operation overflows according to UNSIGNED_P,
+   *OVERFLOW is set to nonzero.  */
+
+double_int
+double_int_mul_with_sign (double_int a, double_int b,
+                          bool unsigned_p, int *overflow)
+{
+  double_int ret;
+  *overflow = mul_double_with_sign (a.low, a.high, b.low, b.high,
+                                    &ret.low, &ret.high, unsigned_p);
+  return ret;
+}
+
 /* Returns A + B.  */

 double_int
Index: gcc/double-int.h
===================================================================
--- gcc/double-int.h    (revision 166426)
+++ gcc/double-int.h    (working copy)
@@ -132,6 +132,7 @@ double_int_fits_in_uhwi_p (double_int cs
    2 * HOST_BITS_PER_WIDE_INT bits.  */

 double_int double_int_mul (double_int, double_int);
+double_int double_int_mul_with_sign (double_int, double_int, bool, int *);
 double_int double_int_add (double_int, double_int);
 double_int double_int_sub (double_int, double_int);
 double_int double_int_neg (double_int);

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[ebotcazou at gcc dot gnu.org]

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

--- Comment #17 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2010-11-09 07:01:26 UTC ---
The PR reference in the ChangeLog is wrong so no cross-link to this audit trail
has been generated.  Please look at the numerous examples in the ChangeLog.

The testcase should have been added to gcc.c-torture/execute instead.

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[xinliangli at gmail dot com]

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

--- Comment #18 from davidxl <xinliangli at gmail dot com> 2010-11-09 07:22:43 UTC ---
PR tree-optimization/46316?  I will make the change.

Thanks,

David

On Mon, Nov 8, 2010 at 11:01 PM, ebotcazou at gcc dot gnu.org <
gcc-bugzilla@gcc.gnu.org> wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=46316
>
> --- Comment #17 from Eric Botcazou <ebotcazou at gcc dot gnu.org>
> 2010-11-09 07:01:26 UTC ---
> The PR reference in the ChangeLog is wrong so no cross-link to this audit
> trail
> has been generated.  Please look at the numerous examples in the ChangeLog.
>
> The testcase should have been added to gcc.c-torture/execute instead.
>
> --
> Configure bugmail: http://gcc.gnu.org/bugzilla/userprefs.cgi?tab=email
> ------- You are receiving this mail because: -------
> You are on the CC list for the bug.
>

[Bug tree-optimization/46316] [4.6 regression] incorrect loop optimization

[ebotcazou at gcc dot gnu.org]

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

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

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

--- Comment #19 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2010-11-09 07:59:27 UTC ---
> PR tree-optimization/46316?  I will make the change.

Yes, this is the expected format.  Thanks for quickly fixing the bug.