[Bug tree-optimization/101291] New: turns infinite loop into finite

[Bug tree-optimization/101291] New: turns infinite loop into finite

[guojiufu at gcc dot gnu.org]

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

            Bug ID: 101291
           Summary: turns infinite loop into finite
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: guojiufu at gcc dot gnu.org
  Target Milestone: ---

For the below code, it should run infinite, but it terminates quickly.

#include <limits.h>
__attribute__ ((noinline))
unsigned foo(unsigned val, unsigned start)
{
  unsigned cnt = 0;
  for (unsigned i = start; i <= val; i+=16)
    cnt++;
  return cnt;
}

int main()
{
  return foo (UINT_MAX-7, 8);
}

[Bug tree-optimization/101291] turns infinite loop into finite

[linkw at gcc dot gnu.org]

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

Kewen Lin <linkw at gcc dot gnu.org> changed:

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

--- Comment #1 from Kewen Lin <linkw at gcc dot gnu.org> ---
Hi Jeff, what's the option and stanza?

[Bug tree-optimization/101291] turns infinite loop into finite

[linkw at gcc dot gnu.org]

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

--- Comment #2 from Kewen Lin <linkw at gcc dot gnu.org> ---
(In reply to Kewen Lin from comment #1)
> Hi Jeff, what's the option and stanza?

The reason why I asked is that I can't simply reproduce it locally at O2, with
C compiler it likely runs forever.  I guess what you tested is the C++ stanza,
so it turns on -ffinite-loops by default as the doc and the loop can stop.

[Bug tree-optimization/101291] turns infinite loop into finite

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-07-02
                 CC|                            |amker at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
           Keywords|                            |wrong-code

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed with -O3 -fno-finite-loops (both C and C++ FE).

[Bug tree-optimization/101291] turns infinite loop into finite

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
The trigger is the vectorizer versioning on niter->assumptions and that being
wrong.  That feature is new in GCC 10 thus GCC 9 appears to be fine (but likely
niter->assumptions is still wrong).

[Bug tree-optimization/101291] turns infinite loop into finite

[marxin at gcc dot gnu.org]

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

--- Comment #5 from Martin Liška <marxin at gcc dot gnu.org> ---
Likely started with r10-1057-g2778a719bebf7a32.

[Bug tree-optimization/101291] turns infinite loop into finite

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Hmm, the support is in GCC 9 as well and the niter analysis is the same so
there's sth else going on.  Btw, the assumptions are

Analyzing # of iterations of loop 1
  exit condition [start_3(D) + 16, + , 16] <= val_4(D)
  bounds on difference of bases: -16 ... 4294967295
  result:
    under assumptions val_4(D) <= 4294967279 && start_3(D) + 16 > 14
    # of iterations (val_4(D) - start_3(D)) / 16, bounded by 268435456

on trunk and

Analyzing # of iterations of loop 1
  exit condition [start_3(D) + 16, + , 16] <= val_4(D)
  bounds on difference of bases: -16 ... 4294967295
  result:
    under assumptions val_4(D) <= 4294967279 && start_3(D) + 16 > 14
    # of iterations (val_4(D) - start_3(D)) / 16, bounded by 268435456

on the GCC 9 branch.  On trunk the scalar loop fallback is misoptimized
by IVOPTs I think.  -fno-ivopts makes it work on trunk at least.  That said,
->assumptions is likely still at fault here.

[Bug tree-optimization/101291] turns infinite loop into finite

[guojiufu at gcc dot gnu.org]

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

--- Comment #7 from Jiu Fu Guo <guojiufu at gcc dot gnu.org> ---
When generates doloop.xxx in ivopts, gimple looks like:

  <bb 13> [local count: 21023864]:
  _38 = val_4(D) - start_3(D);
  _29 = _38 / 16;
  doloop.15_35 = _29 + 1;

  <bb 9> [local count: 191126041]:
  # cnt_17 = PHI <0(13), cnt_19(10)>
  # doloop.15_28 = PHI <doloop.15_35(13), doloop.15_23(10)>
  cnt_19 = cnt_17 + 1;
  doloop.15_23 = doloop.15_28 - 1;
  if (doloop.15_23 != 0)
    goto <bb 10>; [89.00%]
  else
    goto <bb 8>; [11.00%]

  <bb 10> [local count: 170102176]:
  goto <bb 9>; [100.00%]


Before it 
  <bb 13> [local count: 21023864]:

  <bb 9> [local count: 191126041]:
  # cnt_17 = PHI <0(13), cnt_19(10)>
  # i_18 = PHI <start_3(D)(13), i_20(10)>
  cnt_19 = cnt_17 + 1;
  i_20 = i_18 + 16;
  if (val_4(D) >= i_20)
    goto <bb 10>; [89.00%]
  else
    goto <bb 8>; [11.00%]

  <bb 10> [local count: 170102176]:
  goto <bb 9>; [100.00%]

  <bb 4> [local count: 118111600]:
  # cnt_11 = PHI <cnt_2(8), 0(2)>
  return cnt_11;


-------
In number_of_iterations_exit_assumptions, there is code: 
   if (!integer_zerop (niter->assumptions)
        && loop_constraint_set_p (loop, LOOP_C_FINITE))
      niter->assumptions = boolean_true_node;

At here niter->assumptions was reset to true. And then doloop.xx is generated
as if niter is always ok.

[Bug tree-optimization/101291] turns infinite loop into finite

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
The vectorizer sets loop constraints, looks like we forget to clear it in the
versioning code.  I'll have a look next week unless somebody beats me to it.

[Bug tree-optimization/101291] [10/11/12 Regression] turns infinite loop into finite

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|turns infinite loop into    |[10/11/12 Regression] turns
                   |finite                      |infinite loop into finite
   Target Milestone|---                         |10.4
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
           Priority|P3                          |P2

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
Testing a patch.  No testcase, not sure how to test for "infinite loop".

[Bug tree-optimization/101291] [10/11/12 Regression] turns infinite loop into finite

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 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:38872c6c0db1b10b17d3913b277c499913208d0b

commit r12-2003-g38872c6c0db1b10b17d3913b277c499913208d0b
Author: Richard Biener <rguenther@suse.de>
Date:   Mon Jul 5 11:53:07 2021 +0200

    middle-end/101291 - set loop copy of versioned loop

    This fixes the vectorizer loop versioning code failing to clear
    niter related info on the scalar loop as it assumed get_loop_copy
    would work even for the outermost loop.  The patch makes that
    assumption hold by adjusting the loop versioning code.

    2021-07-05  Richard Biener  <rguenther@suse.de>

            PR middle-end/101291
            * cfgloopmanip.c (loop_version): Set the loop copy of the
            versioned loop to the new loop.

[Bug tree-optimization/101291] [10/11 Regression] turns infinite loop into finite

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |12.0
            Summary|[10/11/12 Regression] turns |[10/11 Regression] turns
                   |infinite loop into finite   |infinite loop into finite

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk sofar.

[Bug tree-optimization/101291] [10/11 Regression] turns infinite loop into finite

[cvs-commit at gcc dot gnu.org]

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

--- Comment #12 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:5df86357becfc5c3a676b9f506bf2c1c625306f2

commit r11-8725-g5df86357becfc5c3a676b9f506bf2c1c625306f2
Author: Richard Biener <rguenther@suse.de>
Date:   Mon Jul 5 11:53:07 2021 +0200

    middle-end/101291 - set loop copy of versioned loop

    This fixes the vectorizer loop versioning code failing to clear
    niter related info on the scalar loop as it assumed get_loop_copy
    would work even for the outermost loop.  The patch makes that
    assumption hold by adjusting the loop versioning code.

    2021-07-05  Richard Biener  <rguenther@suse.de>

            PR middle-end/101291
            * cfgloopmanip.c (loop_version): Set the loop copy of the
            versioned loop to the new loop.

    (cherry picked from commit 38872c6c0db1b10b17d3913b277c499913208d0b)

[Bug tree-optimization/101291] [10 Regression] turns infinite loop into finite

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:1a4075c0a43fff9fac9df91c3e83e3a1949b69ff

commit r10-10098-g1a4075c0a43fff9fac9df91c3e83e3a1949b69ff
Author: Richard Biener <rguenther@suse.de>
Date:   Mon Jul 5 11:53:07 2021 +0200

    middle-end/101291 - set loop copy of versioned loop

    This fixes the vectorizer loop versioning code failing to clear
    niter related info on the scalar loop as it assumed get_loop_copy
    would work even for the outermost loop.  The patch makes that
    assumption hold by adjusting the loop versioning code.

    2021-07-05  Richard Biener  <rguenther@suse.de>

            PR middle-end/101291
            * cfgloopmanip.c (loop_version): Set the loop copy of the
            versioned loop to the new loop.

    (cherry picked from commit 38872c6c0db1b10b17d3913b277c499913208d0b)

[Bug tree-optimization/101291] [10 Regression] turns infinite loop into finite

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |10.3.0
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED
      Known to work|                            |10.3.1

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