[Bug tree-optimization/114052] [11/12/13/14 Regression] Wrong code at -O2 for well-defined infinite loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114052 --- Comment #8 from Richard Biener --- 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.
[Bug tree-optimization/114052] [11/12/13/14 Regression] Wrong code at -O2 for well-defined infinite loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114052 --- Comment #7 from Jan Hubicka --- > 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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114052 --- Comment #6 from Richard Biener --- (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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114052 --- Comment #5 from Jan Hubicka --- 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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114052
Richard Biener changed:
What|Removed |Added
CC||hubicka at gcc dot gnu.org
--- Comment #4 from Richard Biener ---
We enter cunroll with
[local count: 10631108]:
[local count: 284435276]:
# RANGE [irange] int [0, 2]
# counter_4 = PHI
[local count: 1073741823]:
if (counter_4 == 2)
goto ; [74.50%]
else
goto ; [25.50%]
[local count: 799937655]:
goto ; [100.00%]
[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 ; [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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114052 Richard Biener 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 --- I will have a look.
