[Bug tree-optimization/57343] wrong code on x86_64-linux at -Os and above

[Bug tree-optimization/57343] wrong code on x86_64-linux at -Os and above

[glisse at gcc dot gnu.org]

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

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
          Component|rtl-optimization            |tree-optimization

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
Reduced a bit:

int printf (const char *, ...);
int c = 0;

int main ()
{
  int i;
  int f = 1;
  for (i = 0; i < 5; i++)
  {
    --c;
    unsigned char h = c * 100;
    if (h == 0)
    {
      f = 0;
      break;
    }
  }

  printf ("%d\n", f);

  return 0;
}

-O1 is enough. Disabling cunroll seems to help.

[Bug tree-optimization/57343] [4.8/4.9 Regression] wrong code on x86_64-linux at -Os and above

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-05-21
                 CC|                            |jakub at gcc dot gnu.org
   Target Milestone|---                         |4.8.1
            Summary|wrong code on x86_64-linux  |[4.8/4.9 Regression] wrong
                   |at -Os and above            |code on x86_64-linux at -Os
                   |                            |and above
     Ever confirmed|0                           |1

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r193098 .

int c = 0;

int
main ()
{
  int i, f = 1;
  for (i = 0; i < 5; i++)
    {
      --c;
      unsigned char h = c * 100;
      if (h == 0)
        {
          f = 0;
          break;
        }
    }
  if (f != 1)
    __builtin_abort ();
  return 0;
}

[Bug tree-optimization/57343] [4.8/4.9 Regression] wrong code on x86_64-linux at -Os and above

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
I'll have a look.

[Bug tree-optimization/57343] [4.8/4.9 Regression] wrong code on x86_64-linux at -Os and above

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
   The value C is equal to final - base, where final and base are the final and
   initial value of the actual induction variable in the analysed loop.  BNDS
   bounds the value of this difference when computed in signed type with
   unbounded range, while the computation of C is performed in an unsigned
   type with the range matching the range of the type of the induction
variable.
   In particular, BNDS.up contains an upper bound on C in the following cases:
   -- if the iv must reach its final value without overflow, i.e., if
      NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
   -- if final >= base, which we know to hold when BNDS.below >= 0.  */

static void
number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
                             bounds *bnds, bool exit_must_be_taken)
{
  double_int max;
  mpz_t d;
  bool bnds_u_valid = ((no_overflow && exit_must_be_taken)
                       || mpz_sgn (bnds->below) >= 0);

for the case in question (IV of unsigned char type, base
((unsigned char) (c_lsm.4_12 + -1)) * 100 and step 100 (negated 156))
the bnds values (below 0, up 255 - full range of unsigned char) the
fact that the IV overflows cannot be simply ignored - and I don't see
how we can derive from below >= 0 that final (which is zero!) is
>= base.

We then fall to

  if (multiple_of_p (TREE_TYPE (c), c, s))
    {
      /* If C is an exact multiple of S, then its value will be reached before
         the induction variable overflows (unless the loop is exited in some
         other way before).  Note that the actual induction variable in the
         loop (which ranges from base to final instead of from 0 to C) may
         overflow, in which case BNDS.up will not be giving a correct upper
         bound on C; thus, BNDS_U_VALID had to be computed in advance.  */
      no_overflow = true;
      exit_must_be_taken = true;

which ends up with no_overflow = true and things going downhill from here.

Note that the original, non-negated bnds would _not_ have mpz_sgn (bnds->below)
>= 0 (but -255):

  /* Rearrange the terms so that we get inequality S * i <> C, with S
     positive.  Also cast everything to the unsigned type.  If IV does
     not overflow, BNDS bounds the value of C.  Also, this is the
     case if the computation |FINAL - IV->base| does not overflow, i.e.,
     if BNDS->below in the result is nonnegative.  */
  if (tree_int_cst_sign_bit (iv->step))
    {
      s = fold_convert (niter_type,
                        fold_build1 (NEGATE_EXPR, type, iv->step));
      c = fold_build2 (MINUS_EXPR, niter_type,
                       fold_convert (niter_type, iv->base),
                       fold_convert (niter_type, final));
      bounds_negate (bnds);

Here |FINAL - IV->base| does overflow, but bounds_negate shadows this.


But even before that we have IVCANON remove the pointless exit

Removed pointless exit: if (i_11 <= 4)
Added canonical iv to loop 1, 3 iterations.

then it adds back the canonical IV, but that's pointless in the next
analysis run done by cunroll and removed there.

The bogus upper bound is determined from local_pure_const via finite_loop_p ()
on the non-header-copied form and the estimate from the h == 0 test.

Analyzing # of iterations of loop 1
  exit condition [(unsigned char) (c_6 + -1) * 100, + , 156] != 0
  bounds on difference of bases: -255 ... 0
  result:
    # of iterations (((unsigned char) (c_6 + -1) * 100) /[ex] 4) * 41 & 63,
bounded by 2

In the end I think that number_of_iterations_ne_max does not properly
honor the case where for

  if (multiple_of_p (TREE_TYPE (c), c, s))
    {
      /* If C is an exact multiple of S, then its value will be reached before
         the induction variable overflows (unless the loop is exited in some
         other way before).  Note that the actual induction variable in the
         loop (which ranges from base to final instead of from 0 to C) may
         overflow, in which case BNDS.up will not be giving a correct upper
         bound on C; thus, BNDS_U_VALID had to be computed in advance.  */
      no_overflow = true;

that multiply overflows.  At least the IV does not range from 0 to C
for (unsigned char) (c_6 + -1) * 100.

I have a hard time following the logic that this all is correct for
wrapping IVs ... that said,

Index: gcc/tree-ssa-loop-niter.c
===================================================================
--- gcc/tree-ssa-loop-niter.c   (revision 199137)
+++ gcc/tree-ssa-loop-niter.c   (working copy)
@@ -627,7 +627,7 @@ number_of_iterations_ne (tree type, affi
      not overflow, BNDS bounds the value of C.  Also, this is the
      case if the computation |FINAL - IV->base| does not overflow, i.e.,
      if BNDS->below in the result is nonnegative.  */
-  if (tree_int_cst_sign_bit (iv->step))
+  if (tree_int_cst_sgn (iv->step) == -1)
     {
       s = fold_convert (niter_type,
                        fold_build1 (NEGATE_EXPR, type, iv->step));

fixes the testcase (otherwise untested).

[Bug tree-optimization/57343] [4.8/4.9 Regression] wrong code on x86_64-linux at -Os and above

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #4)
> Index: gcc/tree-ssa-loop-niter.c
> ===================================================================
> --- gcc/tree-ssa-loop-niter.c   (revision 199137)
> +++ gcc/tree-ssa-loop-niter.c   (working copy)
> @@ -627,7 +627,7 @@ number_of_iterations_ne (tree type, affi
>       not overflow, BNDS bounds the value of C.  Also, this is the
>       case if the computation |FINAL - IV->base| does not overflow, i.e.,
>       if BNDS->below in the result is nonnegative.  */
> -  if (tree_int_cst_sign_bit (iv->step))
> +  if (tree_int_cst_sgn (iv->step) == -1)
>      {
>        s = fold_convert (niter_type,
>                         fold_build1 (NEGATE_EXPR, type, iv->step));
> 
> fixes the testcase (otherwise untested).

Doesn't work and fails bootstrap.

[Bug tree-optimization/57343] [4.8/4.9 Regression] wrong code on x86_64-linux at -Os and above

[rakdver at gcc dot gnu.org]

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

--- Comment #6 from Zdenek Dvorak <rakdver at gcc dot gnu.org> ---
I will have a look.

[Bug tree-optimization/57343] [4.8/4.9 Regression] wrong code on x86_64-linux at -Os and above

[rguenther at suse dot de]

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

--- Comment #8 from rguenther at suse dot de <rguenther at suse dot de> ---
On Fri, 24 May 2013, rakdver at gcc dot gnu.org wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57343
> 
> --- Comment #7 from Zdenek Dvorak <rakdver at gcc dot gnu.org> ---
> (In reply to Richard Biener from comment #4)
> > We then fall to
> > 
> >   if (multiple_of_p (TREE_TYPE (c), c, s))
> >     {
> >       /* If C is an exact multiple of S, then its value will be reached
> > before
> >          the induction variable overflows (unless the loop is exited in some
> >          other way before).  Note that the actual induction variable in the
> >          loop (which ranges from base to final instead of from 0 to C) may
> >          overflow, in which case BNDS.up will not be giving a correct upper
> >          bound on C; thus, BNDS_U_VALID had to be computed in advance.  */
> >       no_overflow = true;
> >       exit_must_be_taken = true;
> > 
> > which ends up with no_overflow = true and things going downhill from here.
> 
> This is the problem -- multiple_of_p claims that (var * 100) is a multiple of
> 100, which is not the case if the multiplication overflows.  I am not sure
> whether this is an expected behavior of multiple_of_p, or whether this could
> cause problems in its other uses.
> 
> A conservative fix here would be to replace the multiple_of_p test here by some
> safer tests -- important special cases are:
> 1) both c and s are constants and c is a multiple of s
> 2) s = 1

Thanks.  I'll audit other uses of multiple_of_p to see whether the
current behavior is desired or a bug.

[Bug tree-optimization/57343] [4.8/4.9 Regression] wrong code on x86_64-linux at -Os and above

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to rguenther@suse.de from comment #8)
> On Fri, 24 May 2013, rakdver at gcc dot gnu.org wrote:
> 
> > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57343
> > 
> > --- Comment #7 from Zdenek Dvorak <rakdver at gcc dot gnu.org> ---
> > (In reply to Richard Biener from comment #4)
> > > We then fall to
> > > 
> > >   if (multiple_of_p (TREE_TYPE (c), c, s))
> > >     {
> > >       /* If C is an exact multiple of S, then its value will be reached
> > > before
> > >          the induction variable overflows (unless the loop is exited in some
> > >          other way before).  Note that the actual induction variable in the
> > >          loop (which ranges from base to final instead of from 0 to C) may
> > >          overflow, in which case BNDS.up will not be giving a correct upper
> > >          bound on C; thus, BNDS_U_VALID had to be computed in advance.  */
> > >       no_overflow = true;
> > >       exit_must_be_taken = true;
> > > 
> > > which ends up with no_overflow = true and things going downhill from here.
> > 
> > This is the problem -- multiple_of_p claims that (var * 100) is a multiple of
> > 100, which is not the case if the multiplication overflows.  I am not sure
> > whether this is an expected behavior of multiple_of_p, or whether this could
> > cause problems in its other uses.
> > 
> > A conservative fix here would be to replace the multiple_of_p test here by some
> > safer tests -- important special cases are:
> > 1) both c and s are constants and c is a multiple of s
> > 2) s = 1
> 
> Thanks.  I'll audit other uses of multiple_of_p to see whether the
> current behavior is desired or a bug.

Most uses are ok, the extract_muldiv_1 use is questionable.  I'll fixup
the use in niter analysis like the following:

-  if (multiple_of_p (TREE_TYPE (c), c, s))
+  if (integer_onep (s)
+      || (TREE_CODE (c) == INTEGER_CST
+         && TREE_CODE (s) == INTEGER_CST
+         && tree_to_double_int (c).mod (tree_to_double_int (s),
+                                        TYPE_UNSIGNED (type),
+                                        EXACT_DIV_EXPR).is_zero ())
+      || (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (c))
+         && multiple_of_p (type, c, s)))
     {

[Bug tree-optimization/57343] [4.8 Regression] wrong code on x86_64-linux at -Os and above

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.9.0
   Target Milestone|4.8.1                       |4.8.2
            Summary|[4.8/4.9 Regression] wrong  |[4.8 Regression] wrong code
                   |code on x86_64-linux at -Os |on x86_64-linux at -Os and
                   |and above                   |above
      Known to fail|                            |4.8.1

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Mon May 27 13:02:24 2013
New Revision: 199357

URL: http://gcc.gnu.org/viewcvs?rev=199357&root=gcc&view=rev
Log:
2013-05-27  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/57343
    * tree-ssa-loop-niter.c (number_of_iterations_ne_max): Do not
    use multiple_of_p if not TYPE_OVERFLOW_UNDEFINED.
    (number_of_iterations_cond): Do not build the folded tree.

    * gcc.dg/torture/pr57343.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr57343.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-loop-niter.c

[Bug tree-optimization/57343] [4.8 Regression] wrong code on x86_64-linux at -Os and above

[jakub at gcc dot gnu.org]

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

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Thu Aug 29 13:09:26 2013
New Revision: 202072

URL: http://gcc.gnu.org/viewcvs?rev=202072&root=gcc&view=rev
Log:
    Backported from mainline
    2013-05-27  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/57343
    * tree-ssa-loop-niter.c (number_of_iterations_ne_max): Do not
    use multiple_of_p if not TYPE_OVERFLOW_UNDEFINED.
    (number_of_iterations_cond): Do not build the folded tree.

    * gcc.dg/torture/pr57343.c: New testcase.

Added:
    branches/gcc-4_8-branch/gcc/testsuite/gcc.dg/torture/pr57343.c
Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_8-branch/gcc/tree-ssa-loop-niter.c

[Bug tree-optimization/57343] [4.8 Regression] wrong code on x86_64-linux at -Os and above

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed.