[Bug c/114052] New: Wrong code at -O2 for well-defined infinite loop

[Bug c/114052] New: Wrong code at -O2 for well-defined infinite loop

[maxdamantus at gmail dot com]

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

            Bug ID: 114052
           Summary: Wrong code at -O2 for well-defined infinite loop
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: maxdamantus at gmail dot com
  Target Milestone: ---

int foo(void) {
        int counter = 0;
        while (1) {
                if(counter >= 2)
                        continue;
                printf("%i\n", counter++);
        }
        return 0;
}

This is actually from a reddit post I came across:
https://www.reddit.com/r/C_Programming/comments/yugk1y/gcc_optimization_behavior/

There are theories in the comments above about UB due to integer overflow or
non-terminating loops, but I'm pretty sure they don't apply (correct me if I'm
wrong).

The controlling expression of the loop is a constant expression, so it can't be
assumed to terminate, and the loop should repeat infinitely with `counter ==
2`, so no overflow should occur. Instead, part of the loop is presumably DCEd,
so control continues outside of the function.

Versions before gcc-13 had slightly different incorrect behaviours occur when
replacing `2` in the condition with `3`, `4`, `5`, etc. These larger numbers
appear to behave correctly now.

godbolt link:
https://godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAMzwBtMA7AQwFtMQByARg9KtQYEAysib0QXACx8BBAKoBnTAAUAHpwAMvAFYTStJg1AB9U8lJL6yAngGVG6AMKpaAVxYMQAJlIOAMngMmABy7gBGmMQSAJykAA6oCoS2DM5uHnoJSTYCAUGhLBFRXFwWmFY5DEIETMQEae6ePpaY1inVtQR5IeGRMRY1dQ0ZpQqDXYE9hX0lAJQWqK7EyOwcAKReAMyByG5YANRrm45j%2BKgAdAhH2GsaAIIb2wy7rgdHJwTotHhhl9e3D3ugQI%2B34qAgADdUHh0LMjgAhAEA4H7FhMQKQ6Gww4AdkR932hKJhKUBAhYVcVAgp0WBFI%2B2Ccj8fnpxgAkgB5YLwgBi9I0cM2%2BLuxOJxEwBCWDFBqHBguFaxxABEkUDBDLwVCYbNccLRUSUWhXIJIodNkr9hoEQD9YSAO4IOiYfYQLg6xV621evBUo0m4hmm7m/ZeOEEr0R/VoQSBVyYa3hyPEuLEYFUjZeDYAVjwayzjgYGfpfoIkQ2iK88PlNttipVidF4slxGlVqFSOVqruKKCEMixlEtHo6Ex2t1Nf1cVcBAUEAzeBYWSSYXoYDAGerDbFEql%2B0kmfb9zrAI481onCzvE8HC0pFQnEc%2BwUi2WzsePFIBE0p/mAGsQJsmznIBIGgWBABs%2BicJIV7fnenC8AoIAaJ%2B37zHAsBIGgi5OmQFAQNhcS4SgwBcJsPg0LQpbEEhEBhHBYSBLUACenAfoxzDEMxHJhNorRftwvDYWwggcgwtCsTevBYBSwCOGItBIYJpBYGiRjiFJKl4OKbR9kpt6YKorTTqst7AuUcHfGExAsc4WBwQQqYsGxp58AYwAKAAangmB2hycSMC5MiCCIYjsFIwXyEoahwbopQGEYICmAO%2Bg/EhkDzKgcSVEpAC0HJeLwqB9sQqZYOlEDzC0bR2BADjDJ4pT%2BJMBRFJkiTJAIDXtdkKTdK1MxlBU7TjN1ozlPxI2dP1vTFAMnRjfNdQzdMxRVS%2BKwSGeF6wZp94cPsqgABzgbl4GSPswDIMg%2BxkecXgurghAkIcWxurwAlaLMf4AUBYH/SBkHnhwMGkNet77YhyGoVJ6EwIgIC0lOdL4YRuHBKwqzHad52Xddt1AYVvj4EQZV6PwIWDuF0gU1FKjqJpcWkHaNlxC520cJeYNwftHLTsj%2ByoFQh0nWdF1XTdd0PRAzg4fQAbvrMH1oT9gHAQD/1QSDu0QwhFjQ59P5a0T4NFXrhvfaQJVJHYkhAA

Seems to have started happening in gcc 8.1, still reproducible from git
version, `basepoints/gcc-14-9077-g52490278466`.

[Bug c/114052] [11/12/13/14 Regression] Wrong code at -O2 for well-defined infinite loop

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org
   Target Milestone|---                         |11.5
             Status|UNCONFIRMED                 |NEW
            Summary|Wrong code at -O2 for       |[11/12/13/14 Regression]
                   |well-defined infinite loop  |Wrong code at -O2 for
                   |                            |well-defined infinite loop
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2024-02-22

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r8-5245-g5b0c69ae65b713ab68202af20dae9dca533d39cf

[Bug c/114052] [11/12/13/14 Regression] Wrong code at -O2 for well-defined infinite loop

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2
                 CC|                            |rguenth at gcc dot gnu.org

[Bug c/114052] [11/12/13/14 Regression] Wrong code at -O2 for well-defined infinite loop

[sjames at gcc dot gnu.org]

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

--- Comment #2 from Sam James <sjames at gcc dot gnu.org> ---
Created attachment 57494
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=57494&action=edit
test.c

Attaching godbolt testcase.

[Bug tree-optimization/114052] [11/12/13/14 Regression] Wrong code at -O2 for well-defined infinite loop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c                           |tree-optimization
             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 will have a look.

[Bug tree-optimization/114052] [11/12/13/14 Regression] Wrong code at -O2 for well-defined infinite loop

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
We enter cunroll with

  <bb 2> [local count: 10631108]:

  <bb 3> [local count: 284435276]:
  # RANGE [irange] int [0, 2]
  # counter_4 = PHI <counter_6(5), 0(2)>

  <bb 4> [local count: 1073741823]:
  if (counter_4 == 2)
    goto <bb 6>; [74.50%]
  else
    goto <bb 5>; [25.50%]

  <bb 6> [local count: 799937655]:
  goto <bb 4>; [100.00%]

  <bb 5> [local count: 273804168]:
  # RANGE [irange] int [1, 2]
  counter_6 = counter_4 + 1;
  # USE = nonlocal escaped null 
  # CLB = nonlocal escaped null 
  printf ("%i\n", counter_4);
  goto <bb 3>; [100.00%]

and then we do

Estimating # of iterations of loop 2
Loop 1 iterates at most 1 times.
Loop 1 likely iterates at most 1 times.

which is wrong.  I think the issue is in record_nonwrapping_iv which in
r6-7091-ge53d562a36ead2 got a fix not using ranges from not always executing
stmts (but oddly enough gating only one end, and seemingly the wrong one?).
In this case the inner endless loops makes the apparent post-dominated
block with the increment actually _not_ execute.

So that "always executed" thing is not properly implemented (we also expect
the caller to pass "upper" as false).

Similar case could be constructed by accessing an array with fixed bounds
in the latch, the "simple" case

int a[3];
int foo(void) {
    unsigned counter = 0;
    while (1) {
        if (counter >= 2) continue;
        printf("%i\n", a[++counter]);
    }
    return 0;
}

works because with -O2 we refuse unrolling due to code size growth:

Loop 1 iterates at most 1 times.
Loop 1 likely iterates at most 1 times.
...
Not unrolling loop 1: it is not innermost and code would grow.

That said, we do not handle possibly infinite subloops or calls that might
not return as properly blocking any of the
number-of-iteration-because-of-undefined-behavior heuristics.

Interestingly enough the following also "works" (unrolling also increases
code size, but we compute two iterations for this).

void __attribute__((noipa)) bar (int i)
{
  if (i == __INT_MAX__)
    while (1);
}

int a[3];
int foo(void) {
    int counter = __INT_MAX__ - 2;
    while (1) {
        bar (counter);
        printf("%i\n", counter++);
    }
    return 0;
}

this needs some investigation more in detail but the underlying issue is that
we do not model inner loops or calls correctly here.

Probably best done in infer_loop_bounds_from_undefined itself which walks
BBs and stmts.  I'll note it's tricky as even

  if (foo)
    bar ();
  ++counter;

thus a conditional call should be a blocker for this.  Honza - I guess
IPA modref has done this kind of "walking" already, is there a place
to copy / factor for this?

[Bug tree-optimization/114052] [11/12/13/14 Regression] Wrong code at -O2 for well-defined infinite loop

[hubicka at gcc dot gnu.org]

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

--- Comment #5 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
So if I understand it right, you want to determine the property that if the
loop header is executed then BB containing undefined behavior at that iteration
will be executed, too.

modref tracks if function will always return and if it can not determine it, it
will set the side_effect flag. So you can check for that in modref summary.
It uses finite_function_p which was originally done for pure/const detection
and  is implemented by looking at loop nest if all loops are known to be finite
and also by checking for irreducible loops.

In your setup you probably also want to check for volatile asms that are also
possibly infinite. In mod-ref we get around by considering them to be
side-effects anyway.


There is also determine_unlikely_bbs which is trying to set profile_count to
zero to as many basic blocks as possible by propagating from basic blocks
containing undefined behaviour or cold noreturn call backward & forward.

The backward walk can be used to determine the property hat executing header
implies UB.  It stops on all loops though. In this case it would be nice to
walk through loops known to be finite...

[Bug tree-optimization/114052] [11/12/13/14 Regression] Wrong code at -O2 for well-defined infinite loop

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jan Hubicka from comment #5)
> So if I understand it right, you want to determine the property that if the
> loop header is executed then BB containing undefined behavior at that
> iteration will be executed, too.
> 
> modref tracks if function will always return and if it can not determine it,
> it will set the side_effect flag. So you can check for that in modref
> summary.
> It uses finite_function_p which was originally done for pure/const detection
> and  is implemented by looking at loop nest if all loops are known to be
> finite and also by checking for irreducible loops.

I see it doesn't do anything if mark_dfs_back_edges returns false, so it
will claim the function is finite even when it calls a non-finite function?
So I assume this is local analysis only and call edges will be handled
elsewhere?

I found another similar compute, fill_always_executed_in in LIM
(that considers all non-PURE calls as eventually looping, relying
solely on gimple_has_side_effects here).

In the end I want to have this on a stmt granularity (stmts before
calls are OK, stmts after not).

I guess greedily walking loop blocks along edges or walking in RPO oder
and tracking whether there's no possible exit on the way to X would be
the way to go.

[Bug tree-optimization/114052] [11/12/13/14 Regression] Wrong code at -O2 for well-defined infinite loop

[hubicka at ucw dot cz]

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

--- Comment #7 from Jan Hubicka <hubicka at ucw dot cz> ---
> I see it doesn't do anything if mark_dfs_back_edges returns false, so it
> will claim the function is finite even when it calls a non-finite function?
> So I assume this is local analysis only and call edges will be handled
> elsewhere?

Yes, the side effects flags are transitively closed in callgraph at the
IPA propagation stage.
> 
> I found another similar compute, fill_always_executed_in in LIM
> (that considers all non-PURE calls as eventually looping, relying
> solely on gimple_has_side_effects here).
There are stmts with side effects that are always finite.
There is stmt_may_terminate_bb_p and stmt_may_terminate_function_p
which does more careful checking (and most of it should be unified I
guess).

I also had patches (never pushed) to track whether given callgraph edge
is always executed.  This is useful, for example, to bypass inliner
heuristics bounds on stack frame size.  It is also useful for profile
propagation.

So having this analysis factored out would be useful here, too.
> 
> In the end I want to have this on a stmt granularity (stmts before
> calls are OK, stmts after not).
Yep, if you have info whether BB is always executed, you still need to
walk its statements.
> 
> I guess greedily walking loop blocks along edges or walking in RPO oder
> and tracking whether there's no possible exit on the way to X would be
> the way to go.

That is what I would do. Maybe it would be nice to see though loops
known to be finite, so I guess if you check that it contains no stmts
that can terminate execution, then one can consider them safe....

[Bug tree-optimization/114052] [11/12/13/14 Regression] Wrong code at -O2 for well-defined infinite loop

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
So in principle we'd need to adjust the bound by one only instead of not using
range info at all as the increment is executed in each loop iteration but
the loop may "stop" before it is reached.

We fail to "thread" the endless loop iteration check btw.

I'm testing a patch.