[Bug tree-optimization/57723] Missed optimization: recursion around empty function

2025-01-10 Thread pinskia at gcc dot gnu.org via Gcc-bugs
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

2025-01-10 Thread pinskia at gcc dot gnu.org via Gcc-bugs
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

2025-01-10 Thread pinskia at gcc dot gnu.org via Gcc-bugs
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

2013-06-27 Thread petschy at gmail dot com
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

2013-06-27 Thread mikpe at it dot uu.se
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

2013-06-27 Thread matz at gcc dot gnu.org
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

2013-06-27 Thread petschy at gmail dot com
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

2013-06-26 Thread matz at gcc dot gnu.org
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

2013-06-26 Thread petschy at gmail dot com
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

2013-06-26 Thread petschy at gmail dot com
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

2013-06-26 Thread petschy at gmail dot com
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

2013-06-26 Thread petschy at gmail dot com
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

2013-06-26 Thread petschy at gmail dot com
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