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

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

[petschy at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723

            Bug ID: 57723
           Summary: Missed optimization: recursion around empty function
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: minor
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: petschy at gmail dot com

Background: freeing nodes of a tree allocated with custom allocators. One of
the allocators can't free individual pointers, so free() is NOP in that case
(the whole pool will be freed at once when the allocator is destroyed). With
this allocator, the whole recursive traversal can be eliminated in theory.

Examining the disasm of the generated code revealed that gcc unfolds the
recursion many levels, just to do the unneeded node traversal; the actual call
to the empty free() fn is eliminated.

In the test case, loop() does a simple linear traversal of the linked nodes.
The pointers are not volatile, and are only read, so there should not be any
side effects. Why can't the compiler optimize away the whole loop?

Clang does a somewhat better job, the recursion is optimized away, and one
function is completely reduced to NOP (free_all2()), but the others still have
the node traversal loop.

Tried with gcc 4.6, 4.7.3, 4.9.0 with the same results.

g++-4.9.0 -v:
Using built-in specs.
COLLECT_GCC=g++-4.9.0
COLLECT_LTO_WRAPPER=/home/usr-local/bin/../libexec/gcc/x86_64-unknown-linux-gnu/4.9.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: ./configure --enable-languages=c,c++ --program-suffix=-4.9.0
Thread model: posix
gcc version 4.9.0 20130626 (experimental) (GCC) 
commit 944f42fc29289812416f34d7b0c497ee79065396

command line:
g++-4.9.0 -std=c++11 -O3 -Wall 20130626-free_node.cpp

Regards, Peter

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

[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

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

[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

[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

[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

[matz at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723

Michael Matz <matz at gcc dot gnu.org> changed:

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

--- Comment #6 from Michael Matz <matz at gcc dot gnu.org> ---
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

[mikpe at it dot uu.se]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57723

--- Comment #9 from Mikael Pettersson <mikpe at it dot uu.se> ---
(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

[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