[Bug tree-optimization/104519] New: wrong code at -Os on x86_64-linux-gnu

[Bug tree-optimization/104519] New: wrong code at -Os on x86_64-linux-gnu

[zhendong.su at inf dot ethz.ch]

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

            Bug ID: 104519
           Summary: wrong code at -Os on x86_64-linux-gnu
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: zhendong.su at inf dot ethz.ch
  Target Milestone: ---

This appears to be a recent regression.

[682] % gcctk -v
Using built-in specs.
COLLECT_GCC=gcctk
COLLECT_LTO_WRAPPER=/local/suz-local/software/local/gcc-trunk/libexec/gcc/x86_64-pc-linux-gnu/12.0.1/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: ../gcc-trunk/configure --disable-bootstrap
--prefix=/local/suz-local/software/local/gcc-trunk --enable-languages=c,c++
--disable-werror --enable-multilib --with-system-zlib
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 12.0.1 20220213 (experimental) [master r12-7216-g7e204bd2f18] (GCC) 
[683] % 
[683] % gcctk -O1 small.c; ./a.out
[684] % 
[684] % gcctk -Os small.c
[685] % ./a.out
Aborted
[686] % 
[686] % cat small.c
char a, b;
int main() {
  for (b = -7; b; b += 3)
    if (a)
      __builtin_abort();
  return 0;
}

[Bug tree-optimization/104519] wrong code at -Os on x86_64-linux-gnu

[zhendong.su at inf dot ethz.ch]

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

--- Comment #1 from Zhendong Su <zhendong.su at inf dot ethz.ch> ---
>From Compiler Explorer: https://godbolt.org/z/s7Eco5EGb

[Bug tree-optimization/104519] [12 Regression] wrong code at -Os on x86_64-linux-gnu

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |12.0
           Keywords|                            |wrong-code
            Summary|wrong code at -Os on        |[12 Regression] wrong code
                   |x86_64-linux-gnu            |at -Os on x86_64-linux-gnu

[Bug tree-optimization/104519] [12 Regression] wrong code at -Os on x86_64-linux-gnu

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 104521 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/104519] [12 Regression] wrong code at -Os on x86_64-linux-gnu and char as induction variable

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
            Summary|[12 Regression] wrong code  |[12 Regression] wrong code
                   |at -Os on x86_64-linux-gnu  |at -Os on x86_64-linux-gnu
                   |                            |and char as induction
                   |                            |variable
   Last reconfirmed|                            |2022-02-13

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I suspect it was introduced by r12-6844-gf1af8528d3 .


Confirmed.

[Bug tree-optimization/104519] [12 Regression] wrong code at -Os on x86_64-linux-gnu and char as induction variable

[guojiufu at gcc dot gnu.org]

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

Jiu Fu Guo <guojiufu at gcc dot gnu.org> changed:

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

--- Comment #4 from Jiu Fu Guo <guojiufu at gcc dot gnu.org> ---
Had a quick bisect and test,  this PR and 104521 seems caused by 
r12-7052-g0898049ad9bf6c46e510b18aaafca4946802749f.

[Bug tree-optimization/104519] [12 Regression] wrong code at -Os on x86_64-linux-gnu and char as induction variable

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Priority|P3                          |P1
            Version|unknown                     |12.0
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

[Bug tree-optimization/104519] [12 Regression] wrong code at -Os on x86_64-linux-gnu and char as induction variable

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Hmm, for

b.2_2 = (unsigned char) b_lsm.6_13;
_3 = b.2_2 + 3;
_4 = (char) _3;

we analyze the evolution of _4 to {-4, +, 3}_1 (we're using an existing
upper bound for niter of 2).  Eventually the bound we derive for this exit
causes us to disregard the other exit.

That upper bound of niter is from the main loop exit test at CD-DCE time.

Specifically multiple_of_p computes 249 % 3 is 0 and 0 % 3 is 0.  It passes
wrong 'type', which doesn't end up mattering because the code seems
to look for mismatched type & type top/bottom(!?)

    case INTEGER_CST:
      if (TREE_CODE (bottom) != INTEGER_CST
          || integer_zerop (bottom)
          || (TYPE_UNSIGNED (type)
              && (tree_int_cst_sgn (top) < 0
                  || tree_int_cst_sgn (bottom) < 0)))
        return 0;
      return wi::multiple_of_p (wi::to_widest (top), wi::to_widest (bottom),
                                SIGNED);

but then, we do

  if (!niter->control.no_overflow
      && (integer_onep (s)
          || (multiple_of_p (niter_type, fold_convert (niter_type, iv->base),
s,
                             false)
              && multiple_of_p (niter_type, fold_convert (niter_type, final),
s,
                                false))))

so look for the multiple in unsigned arithmetic but then assume overflow
does not happen in signed arithmetic.  That means the changes to
number_of_iterations_ne were wrong.  Note the simplistic fix for
PR100499 regressed some testcases.

diff --git a/gcc/fold-const.cc b/gcc/fold-const.cc
index 386d5732ea0..cdf34d81d90 100644
--- a/gcc/fold-const.cc
+++ b/gcc/fold-const.cc
@@ -14211,8 +14211,8 @@ multiple_of_p (tree type, const_tree top, const_tree
bottom, bool nowrap)
       if (TREE_CODE (bottom) != INTEGER_CST
          || integer_zerop (bottom)
          || (TYPE_UNSIGNED (type)
-             && (tree_int_cst_sgn (top) < 0
-                 || tree_int_cst_sgn (bottom) < 0)))
+             && (tree_int_cst_sign_bit (top)
+                 || tree_int_cst_sign_bit (bottom))))
        return 0;
       return wi::multiple_of_p (wi::to_widest (top), wi::to_widest (bottom),
                                SIGNED);
diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
index 318d10c8fac..b8a628ea829 100644
--- a/gcc/tree-ssa-loop-niter.cc
+++ b/gcc/tree-ssa-loop-niter.cc
@@ -1051,9 +1051,9 @@ number_of_iterations_ne (class loop *loop, tree type,
affine_iv *iv,
      along with condition 1) or 1').  */
   if (!niter->control.no_overflow
       && (integer_onep (s)
-         || (multiple_of_p (type, fold_convert (niter_type, iv->base), s,
+         || (multiple_of_p (niter_type, fold_convert (niter_type, iv->base),
s,
                             false)
-             && multiple_of_p (type, fold_convert (niter_type, final), s,
+             && multiple_of_p (niter_type, fold_convert (niter_type, final),
s,
                                false))))
     {
       tree t, cond, relaxed_cond = boolean_false_node;

fixes this PR but I need to understand what multiple_of_p is doing here ...

[Bug tree-optimization/104519] [12 Regression] wrong code at -Os on x86_64-linux-gnu and char as induction variable

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
diff --git a/gcc/fold-const.cc b/gcc/fold-const.cc
index 386d5732ea0..9d9939642f6 100644
--- a/gcc/fold-const.cc
+++ b/gcc/fold-const.cc
@@ -14208,11 +14208,7 @@ multiple_of_p (tree type, const_tree top, const_tree
bo
ttom, bool nowrap)
              && multiple_of_p (type, TREE_OPERAND (top, 2), bottom, nowrap));

     case INTEGER_CST:
-      if (TREE_CODE (bottom) != INTEGER_CST
-         || integer_zerop (bottom)
-         || (TYPE_UNSIGNED (type)
-             && (tree_int_cst_sgn (top) < 0
-                 || tree_int_cst_sgn (bottom) < 0)))
+      if (TREE_CODE (bottom) != INTEGER_CST || integer_zerop (bottom))
        return 0;
       return wi::multiple_of_p (wi::to_widest (top), wi::to_widest (bottom),
                                SIGNED);

of course makes most sense there.  I'm evaluating what

diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
index 318d10c8fac..2305e1d53f6 100644
--- a/gcc/tree-ssa-loop-niter.cc
+++ b/gcc/tree-ssa-loop-niter.cc
@@ -986,6 +986,7 @@ number_of_iterations_ne (class loop *loop, tree type,
affine_iv *iv,
                         bool exit_must_be_taken, bounds *bnds)
 {
   tree niter_type = unsigned_type_for (type);
+  tree stype = signed_type_for (niter_type);
   tree s, c, d, bits, assumption, tmp, bound;
   mpz_t max;

@@ -1051,10 +1052,8 @@ number_of_iterations_ne (class loop *loop, tree type,
affine_iv *iv,
      along with condition 1) or 1').  */
   if (!niter->control.no_overflow
       && (integer_onep (s)
-         || (multiple_of_p (type, fold_convert (niter_type, iv->base), s,
-                            false)
-             && multiple_of_p (type, fold_convert (niter_type, final), s,
-                               false))))
+         || multiple_of_p (stype, fold_convert (stype, c),
+                           fold_convert (stype, iv->step))))
     {
       tree t, cond, relaxed_cond = boolean_false_node;


will yield since we are interpreting iv->step as signed.  Pointers are
what makes this all a bit awkward since for those iv->base is a pointer
but iv->step is (unsigned) sizetype to be interpreted as signed.

Anyway, I do appreciate the extended test coverage we are getting from
the auto-generation of valid code people!

[Bug tree-optimization/104519] [12 Regression] wrong code at -Os on x86_64-linux-gnu and char as induction variable

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Btw, to me it seems that since we are resolving condition 1) statically we know
that the difference of iv->base and final is positive with infinite
precision and fits the unsigned niter_type.  To avoid going to the unsigned
type we can then indeed check multiple_of_p on each component, but we need
to use the original signedness here (or rather always signed?).

Using unsigned arithmetic for the

          niter->niter = fold_build2 (EXACT_DIV_EXPR, niter_type, c, s);

in the end is consistent with the conditions we checked.  So to preserve the
gist of Bins change I included it should probably read

diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
index 318d10c8fac..3ddc3a5c3a6 100644
--- a/gcc/tree-ssa-loop-niter.cc
+++ b/gcc/tree-ssa-loop-niter.cc
@@ -986,6 +986,7 @@ number_of_iterations_ne (class loop *loop, tree type,
affine_iv *iv,
                         bool exit_must_be_taken, bounds *bnds)
 {
   tree niter_type = unsigned_type_for (type);
+  tree stype = signed_type_for (niter_type);
   tree s, c, d, bits, assumption, tmp, bound;
   mpz_t max;

@@ -1051,10 +1052,10 @@ number_of_iterations_ne (class loop *loop, tree type,
affine_iv *iv,
      along with condition 1) or 1').  */
   if (!niter->control.no_overflow
       && (integer_onep (s)
-         || (multiple_of_p (type, fold_convert (niter_type, iv->base), s,
-                            false)
-             && multiple_of_p (type, fold_convert (niter_type, final), s,
-                               false))))
+         || (multiple_of_p (stype, fold_convert (stype, iv->base),
+                            fold_convert (stype, iv->step))
+             && multiple_of_p (stype, fold_convert (stype, final),
+                               fold_convert (stype, iv->step)))))
     {
       tree t, cond, relaxed_cond = boolean_false_node;

[Bug tree-optimization/104519] [12 Regression] wrong code at -Os on x86_64-linux-gnu and char as induction variable

[cvs-commit at gcc dot gnu.org]

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

--- Comment #8 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:d8b6da8dd15240849e00d46f3aef40cb8eeb1dc5

commit r12-7239-gd8b6da8dd15240849e00d46f3aef40cb8eeb1dc5
Author: Richard Biener <rguenther@suse.de>
Date:   Tue Feb 15 09:40:59 2022 +0100

    tree-optimization/104519 - adjust PR100499 niter fix

    The following adjusts the PR100499 niter fix to use the appropriate
    types when checking whether the difference between the final and base
    values of the IV are a multiple of the step.  It also gets rid of
    an always false condition in multiple_of_p which lead me to a
    wrong solution first.

    2022-02-15  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/104519
            * fold-const.cc (multiple_of_p): Remove never true condition.
            * tree-ssa-loop-niter.cc (number_of_iterations_ne): Use
            the appropriate types for determining whether the difference
            of final and base is a multiple of the step.

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

[Bug tree-optimization/104519] [12 Regression] wrong code at -Os on x86_64-linux-gnu and char as induction variable

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.  Keep more cases coming please!