[Bug tree-optimization/104931] New: wrong-code with number_of_iterations_lt_to_ne

[Bug tree-optimization/104931] New: wrong-code with number_of_iterations_lt_to_ne

[rguenth at gcc dot gnu.org]

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

            Bug ID: 104931
           Summary: wrong-code with number_of_iterations_lt_to_ne
           Product: gcc
           Version: 11.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rguenth at gcc dot gnu.org
  Target Milestone: ---

The premake tool is miscompiled when building it with LTO on i586-linux,
resulting in it immediately segfaulting via

==9912== Invalid read of size 4
==9912==    at 0x8162378: UnknownInlinedFun (lapi.c:197)
==9912==    by 0x8162378: lua_rotate.constprop.0 (lapi.c:217)
==9912==    by 0x8063881: luaL_requiref (lauxlib.c:983)
==9912==    by 0x807DF76: luaL_openlibs (linit.c:64)
==9912==    by 0x8061128: main (premake_main.c:15)
==9912==  Address 0x43816dc is 12 bytes before a block of size 408 alloc'd
==9912==    at 0x4035EDB: realloc (in
/usr/lib64/valgrind/vgpreload_memcheck-x86-linux.so)
==9912==    by 0x80806A3: luaM_realloc_ (lmem.c:86)
==9912==    by 0x807727E: luaD_reallocstack (ldo.c:182)

this can be reproduced with GCC 10 and GCC 11 but not on trunk.  After checking
out https://github.com/premake/premake-core.git do

make -f Bootstrap.mak linux CC="gcc-11 -m32" CFLAGS="-O2 -flto -g"

and ./bin/release/premake will then segfault.

I've narrowed this down to the first IPA CP clone of lua_rotate being
miscompiled, we enter number_of_iterations_lt_to_ne for

  exit condition [(struct TValue *) (_2 + 4294967272) + 12, + ,
24](no_overflow) < _2 + 4294967272

with delta being 4294967284, the step type is unsigned int.  The problem
is that for pointer IVs the step type has to be interpreted as signed, but
the code uses an unsigned FLOOR_MOD to compute the condition under which
the loop will not iterate which it computes to

  result:
    zero if (struct TValue *) (_2 + 4294967272) + 12 > _2 + 4294967292
    # of iterations 178956971, bounded by 0

which is always false (but not folded).  When making sure to use a signed
type to compute the modulo the miscompile is gone and we manage to
compute the correct

  result:
    zero if (struct TValue *) (_2 + 4294967272) + 12 > _2 + 4294967284(OVF)
    # of iterations 0(OVF), bounded by 0

I've failed to create a small testcase - there seem to be special circumstances
required that make us enter niter analysis with exactly this SCEV.  The
simplified testcase

struct X { int x[3]; };
static void reverse (struct X *from, struct X *to)
{
  do
    {
      struct X temp = *from;
      *from = *to;
      *to = temp;
      from++;
      to--;
    }
  while (from < to);
}
void
lua_rotate (struct X **L)
{
  struct X *y = *L;
  struct X *to = y - 1;
  struct X *from = y - 2;
  reverse (from, to);
} 

does not exhibit this problem.

[Bug tree-optimization/104931] wrong-code with number_of_iterations_lt_to_ne

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2022-03-15
      Known to fail|                            |10.3.1, 11.2.1
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
     Ever confirmed|0                           |1
           Keywords|                            |wrong-code
      Known to work|                            |12.0
             Status|UNCONFIRMED                 |ASSIGNED

[Bug tree-optimization/104931] wrong-code with number_of_iterations_lt_to_ne

[rguenth at gcc dot gnu.org]

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

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
I think the issue is latent on trunk.  The fix should be

diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index b767056aeb0..21e25cabbd2 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -1171,7 +1171,17 @@ number_of_iterations_lt_to_ne (tree type, affine_iv
*iv0, affine_iv *iv1,
                               bool exit_must_be_taken, bounds *bnds)
 {
   tree niter_type = TREE_TYPE (step);
-  tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
+  tree mod;
+  if (POINTER_TYPE_P (type))
+    {
+      /* For pointers both step and delta have to be interpreted signed.  */
+      mod = fold_build2 (FLOOR_MOD_EXPR, ssizetype,
+                        fold_convert (ssizetype, *delta),
+                        fold_convert (ssizetype, step));
+      mod = fold_convert (niter_type, mod);
+    }
+  else
+    mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
   tree tmod;
   mpz_t mmod;
   tree assumption = boolean_true_node, bound, noloop;

[Bug tree-optimization/104931] wrong-code with number_of_iterations_lt_to_ne

[rguenth at gcc dot gnu.org]

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

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
But maybe the code relies on a positive 'delta' - after all the same issue must
exist for integer typed IVs.  Probably most interesting cases get folded early
in the correct way if they do not iterate.

Given niter_type is unsigned_type_for (type) the use of FLOOR_MOD_EXPR seems
pointless but would be required when doing a signed floor-mod as in the fix.

Note there's


  tree niter_type = TREE_TYPE (step);
  tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
..
  if (integer_nonzerop (mod))
    mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
..
  mpz_init (mmod);
  wi::to_mpz (wi::to_wide (mod), mmod, UNSIGNED);
  mpz_neg (mmod, mmod);

so there's evidence that 'mod' is assumed to be positive in the end but
'delta' can be effectively signed here.  Note 'step' is the absolute
value of step, it's always (made) positive.

The code has been this way since Zdenek wrote it.

The proposed patch has passed bootstrap & testing (but I believe it's
incomplete).

[Bug tree-optimization/104931] wrong-code with number_of_iterations_lt_to_ne

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
The bug was made latent by g:51d464b608b38b9e2007948d10b1e0f1dcec142c which
ensured that

  /* If the loop exits immediately, there is nothing to do.  */
  tree tem = fold_binary (code, boolean_type_node, iv0->base, iv1->base);
  if (tem && integer_zerop (tem))
    {
      if (!every_iteration)
        return false;
      niter->niter = build_int_cst (unsigned_type_for (type), 0);
      niter->max = 0;
      return true;
    }

triggered, folding (_2 + 4294967272) + 12 < _2 + 4294967272 to false.  That's
the following part of the revision, and it probably triggers when doing
expand_simple_operations.

diff --git a/gcc/match.pd b/gcc/match.pd
index 84c9b918041..f5dcbf32bc7 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -2143,6 +2143,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 (simplify
   (pointer_plus (pointer_plus:s @0 @1) @3)
   (pointer_plus @0 (plus @1 @3)))
+#if GENERIC
+(simplify
+  (pointer_plus (convert:s (pointer_plus:s @0 @1)) @3)
+  (convert:type (pointer_plus @0 (plus @1 @3))))
+#endif

 /* Pattern match

It does seem to me that niter analysis relies on statically detecting
not rolling loops, at least for the cases we assume no overflow happens
and we use number_of_iterations_lt_to_ne.  I can't convince myself that
only INTEGER_CST appearant negative delta are problematic for
pointer types (which we always assume to have no overflow), but that would
be the most simplistic solution here.  Still "negative" delta values should
be problematic for all cases, and since we only restrict us to constant
modulo, delta can also be non-constant.

[Bug tree-optimization/104931] wrong-code with number_of_iterations_lt_to_ne

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #3)
> The bug was made latent by g:51d464b608b38b9e2007948d10b1e0f1dcec142c which
> ensured that
> 
>   /* If the loop exits immediately, there is nothing to do.  */
>   tree tem = fold_binary (code, boolean_type_node, iv0->base, iv1->base);
>   if (tem && integer_zerop (tem))
>     {
>       if (!every_iteration)
>         return false;
>       niter->niter = build_int_cst (unsigned_type_for (type), 0);
>       niter->max = 0;
>       return true;
>     }
> 
> triggered, folding (_2 + 4294967272) + 12 < _2 + 4294967272 to false.  That's
> the following part of the revision, and it probably triggers when doing
> expand_simple_operations.
> 
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 84c9b918041..f5dcbf32bc7 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -2143,6 +2143,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>  (simplify
>    (pointer_plus (pointer_plus:s @0 @1) @3)
>    (pointer_plus @0 (plus @1 @3)))
> +#if GENERIC
> +(simplify
> +  (pointer_plus (convert:s (pointer_plus:s @0 @1)) @3)
> +  (convert:type (pointer_plus @0 (plus @1 @3))))
> +#endif
>  
>  /* Pattern match
> 
> It does seem to me that niter analysis relies on statically detecting
> not rolling loops, at least for the cases we assume no overflow happens
> and we use number_of_iterations_lt_to_ne.  I can't convince myself that
> only INTEGER_CST appearant negative delta are problematic for
> pointer types (which we always assume to have no overflow), but that would
> be the most simplistic solution here.  Still "negative" delta values should
> be problematic for all cases, and since we only restrict us to constant
> modulo, delta can also be non-constant.

I verified backporting the above fixes the issue.  That's really the patch
I'm most comfortable with at this point ... :/

[Bug tree-optimization/104931] [9/10/11 Regression] wrong-code with number_of_iterations_lt_to_ne

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|wrong-code with             |[9/10/11 Regression]
                   |number_of_iterations_lt_to_ |wrong-code with
                   |ne                          |number_of_iterations_lt_to_
                   |                            |ne
           Priority|P3                          |P2
   Target Milestone|---                         |9.5
      Known to fail|                            |9.3.1
      Known to work|                            |7.5.0

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Verified the issue also happens with GCC 9, it doesn't happen with GCC 7.

[Bug tree-optimization/104931] [9/10/11 Regression] wrong-code with number_of_iterations_lt_to_ne

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Also confirmed the issue still happens on trunk when we revert this match.pd
pattern.

[Bug tree-optimization/104931] [9/10/11 Regression] wrong-code with number_of_iterations_lt_to_ne

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 52644
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52644&action=edit
GIMPLE testcase

This is a GIMPLE testcase created from the cddce2 IL of the respective ltrans
unit from trunk with the match.pd hunk reverted.  It does not exhibit the bug.
The reason is likely different pre-caching in SCEV and/or niter estimates.

[Bug tree-optimization/104931] [9/10/11 Regression] wrong-code with number_of_iterations_lt_to_ne

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 52645
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52645&action=edit
ivcanon dump as seen from LTO (with bug)

[Bug tree-optimization/104931] [9/10/11 Regression] wrong-code with number_of_iterations_lt_to_ne

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 52646
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52646&action=edit
ivcanon dump from the GIMPLE testcase (without bug)

The difference is that with LTO we have expanded expressions to

Analyzing # of iterations of loop 1
  exit condition [(struct TValue *) (_2 + 4294967272) + 12, + ,
24](no_overflow) < _2 + 4294967272

while with the GIMPLE testcase we immediately get to

Statement (exit)if (from_26 < to_27)
 is executed at most 0 (bounded by 0) + 1 times in loop 1.
...
Loop 1 iterates 0 times.


Note the GIMPLE FE doesn't yet support parsing CLOBBER stmts (but I'm quite
sure this doesn't matter here) and for the loops() support you need to
commit a pending patch.

[Bug tree-optimization/104931] [9/10/11 Regression] wrong-code with number_of_iterations_lt_to_ne

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
The bug also shows in a -flto-partition=max build where the offending function
ends up in ltrans unit 23 (and only this function) which might enable
side-by-side debugging if desired.

[Bug tree-optimization/104931] [9/10/11 Regression] wrong-code with number_of_iterations_lt_to_ne

[cvs-commit at gcc dot gnu.org]

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

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

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

commit r11-9688-gd1f4dfd409dedf4d00ca7be001cf757d0d6e82f4
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Mar 16 14:53:06 2022 +0100

    tree-optimization/104931 - mitigate niter analysis issue

    The following backports a pointer associating pattern from trunk
    that mitigates an issue with number_of_iterations_lt_to_ne in
    which context we fail to fold a comparison but succeed in folding
    a related subtraction.  In the failure mode this results in
    a loop wrongly assumed looping with a bogus number of iterations,
    resulting in crashing of the premake application on start.

    With the backported simplification we are able to fold the
    comparison and correctly compute the loop as not iterating.

    I have failed to create a standalone testcase.  I belive part
    of the issue is still latent but I have failed to nail down
    the issue exactly.  Still I believe the backporting of the
    mitigation patch is the most sensible and safe thing at this
    point.

    2022-03-16  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/104931
            * match.pd ((ptr) (x p+ y) p+ z -> (ptr) (x p+ (y + z))): New
GENERIC
            simplification.

[Bug tree-optimization/104931] [10 Regression] wrong-code with number_of_iterations_lt_to_ne

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.5                         |10.4

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9 branch is being closed

[Bug tree-optimization/104931] [10 Regression] wrong-code with number_of_iterations_lt_to_ne

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.4                        |10.5

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 10.4 is being released, retargeting bugs to GCC 10.5.

[Bug tree-optimization/104931] [10 Regression] wrong-code with number_of_iterations_lt_to_ne

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED
      Known to fail|                            |10.5.0
   Target Milestone|10.5                        |11.3

--- Comment #14 from Richard Biener <rguenth at gcc dot gnu.org> ---
fixed in 11.3.