[Bug tree-optimization/57723] Missed optimization: recursion around empty function
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723 Andrew Pinski changed: What|Removed |Added Known to work|12.2.0, 15.0| Keywords|needs-bisection,| |needs-testcase | --- Comment #12 from Andrew Pinski --- (In reply to Andrew Pinski from comment #11) > Fixed in GCC 12. Actually that is only for the original testcase in comment #1. The one in comment #5 is still not fixed. Note in C++, there is a forward progress requirement so possible empty infinite loops can be removed (well except for trival ones but this is not a trivial one).
[Bug tree-optimization/57723] Missed optimization: recursion around empty function
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723 Andrew Pinski changed: What|Removed |Added Keywords||needs-testcase Ever confirmed|0 |1 Status|RESOLVED|NEW Last reconfirmed||2025-01-11 Target Milestone|12.0|--- Resolution|FIXED |---
[Bug tree-optimization/57723] Missed optimization: recursion around empty function
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723 Andrew Pinski changed: What|Removed |Added Target Milestone|--- |12.0 Resolution|--- |FIXED Known to work||12.2.0, 15.0 Status|UNCONFIRMED |RESOLVED Known to fail||10.2.0, 11.4.0, 9.5.0 --- Comment #11 from Andrew Pinski --- Fixed in GCC 12.
[Bug tree-optimization/57723] Missed optimization: recursion around empty function
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723 --- Comment #10 from petschy at gmail dot com --- Thanks for the explanation. The multithreaded argument is sound, but then, on second thought, even in single threaded programs the state might be altered by a signal handler, or another process if the memory is shared, so the optimization might break the program. The bottom line is that the compiler doesn't have enough information, so it must be conservative, hence the loop stays in. Adding a new fn attribute probably wouldn't be enough, since in general there might be more than one potentially infinite loop inside the fn, with different semantics, so optimizing all of them away still could be improper. Hence the attribute should apply to a given loop only ('finite'), but implementing it is probably too much trouble for this rare case, and the compiler still needs to eliminate the recursion, too, which might be more complex, eg multiple functions calling each other in the general case. For my specific case, I can solve the problem by providing a trait for the allocator which says 'free() is NOP, so don't bother', then the top level function can decide what to do, traverse & free or do nothing. Mikael: could you please provide some info on the ptrace() wizardy you mentioned, if it's not confidental? I got curious. Based on the discussion so far, do you think that clang is overly smart in this case, producing potentially broken code? free_all2() was compiled into a single ret, and the other two functions lack the recursion, only have the node traversal of the current level, which seems to be an error to me, because if there is an infinite loop on one of the levels, the program's behaviour will be different when compiled with optimizations. If I set n_->down to null before the recursive call, it generated the expected code, which is interesting, since then the loop is more likely on the 'finite side'. Thanks, Peter
[Bug tree-optimization/57723] Missed optimization: recursion around empty function
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723 --- Comment #9 from Mikael Pettersson --- (In reply to Michael Matz from comment #8) > (the > argument being that an infinite loop is in itself a side-effect observable > from > outside). Exactly. > A function containing > an infinite loop could be stopped from a different thread. We have production code which does that, except the stopping (and redirection to another context) is done from a separate monitor process via ptrace(). GCC "optimizing" away infinite loops is just plain wrong, at least for ordinary systems programming languages.
[Bug tree-optimization/57723] Missed optimization: recursion around empty function
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723 --- Comment #8 from Michael Matz --- (In reply to petschy from comment #7) > Is it a plausible assumption that if a function is not marked as 'noreturn' > and the loop doesn't change the program's state then the loop could be > optimized away? It's not unplausible, but still wrong, see below. GCC optimizes empty loops only away if the functions containing them are marked pure or const (the argument being that an infinite loop is in itself a side-effect observable from outside). This could be extended to also do that for functions without the noreturn attribute. But it would be a relatively large change in semantics. That is because noreturn attributes are optional; functions that don't return aren't required to be so marked, so in practice a missing noreturn attribute doesn't mean anything. So, when GCC starts to remove infinite loops in functions missing it (in practice most functions) this might change behaviour (which you already can have with the unsafe-loop-optimization flag). The problem lies with multi-threaded programs. A function containing an infinite loop could be stopped from a different thread. While I'll happily admit that this is a quite unlikely behaviour, you can construct a valid program that will break with infinite-loop removal. So it seems that if any other attribute should trigger this in addition to const/pure (which have other effects of course), it would have to be a new one, with positive meaning, ala "this-function-does-return". I'm not aware of anyone sufficiently motivated to work on this. Perhaps you are, if so, look for finite_loop_p() in tree-ssa-loop-niter.c for the place to lookup the new attribute, and builtin-attrs.def for the place to define a new attribute. > Cases: > - the loop terminates, but the state is not changed, NOP > - the loop does not terminate (in this case a cycle of the Node's), but the > function should return (no noreturn attr), so this is probably a bug in the > prg > > I can't think of any cases right now for the second point where that would > be the desired behaviour of the program, instead of a bug. Please comment on > this. See the multi-threading example.
[Bug tree-optimization/57723] Missed optimization: recursion around empty function
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723 --- Comment #7 from petschy at gmail dot com --- Is it a plausible assumption that if a function is not marked as 'noreturn' and the loop doesn't change the program's state then the loop could be optimized away? Cases: - the loop terminates, but the state is not changed, NOP - the loop does not terminate (in this case a cycle of the Node's), but the function should return (no noreturn attr), so this is probably a bug in the prg I can't think of any cases right now for the second point where that would be the desired behaviour of the program, instead of a bug. Please comment on this.
[Bug tree-optimization/57723] Missed optimization: recursion around empty function
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723 Michael Matz changed: What|Removed |Added CC||matz at gcc dot gnu.org --- Comment #6 from Michael Matz --- The loop in loop() isn't removed because it's potentially infinite, and GCC doesn't remove infinite loops by default. Add -funsafe-loop-optimizations to do that (loop() will then become an empty function). The recursion isn't removed because all calls to non-const non-pure functions are deemed necessary. dead code removal could be made to handle this with some trickery. We'd need to not mark recursive calls as inherently necessary at first, but only later if we mark anything in the function except the return statement necessary.
[Bug tree-optimization/57723] Missed optimization: recursion around empty function
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723 --- Comment #5 from petschy at gmail dot com --- Created attachment 30368 --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30368&action=edit fixed test case (correct recursive traversal)
[Bug tree-optimization/57723] Missed optimization: recursion around empty function
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723 --- Comment #4 from petschy at gmail dot com --- Ooops, the test case won't perform the freeing completely, since the recursive call is not inside the 'down' traversal loop, so only the first node on the given level would be recursively freed, but this doesn't affect the missed optimization.
[Bug tree-optimization/57723] Missed optimization: recursion around empty function
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723 --- Comment #3 from petschy at gmail dot com --- Created attachment 30367 --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30367&action=edit clang amd64 disassembly
[Bug tree-optimization/57723] Missed optimization: recursion around empty function
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723 --- Comment #2 from petschy at gmail dot com --- Created attachment 30366 --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30366&action=edit gcc amd64 disassembly
[Bug tree-optimization/57723] Missed optimization: recursion around empty function
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723 --- Comment #1 from petschy at gmail dot com --- Created attachment 30365 --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30365&action=edit test case source