[Bug tree-optimization/68008] New: Pessimization of simple non-tail-recursive functions

[Bug tree-optimization/68008] New: Pessimization of simple non-tail-recursive functions

[gcc-bugzilla at mkarcher dot dialup.fu-berlin.de]

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

            Bug ID: 68008
           Summary: Pessimization of simple non-tail-recursive functions
           Product: gcc
           Version: 5.1.1
               URL: http://stackoverflow.com/questions/32974625
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gcc-bugzilla at mkarcher dot dialup.fu-berlin.de
  Target Milestone: ---

Created attachment 36537
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36537&action=edit
preprocessed source code

As discussed on Stack Overflow in http://stackoverflow.com/questions/32974625
(Misleading title: "Is gcc's asm volatile equivalent to the gfortran default
setting for recursions?"), gcc pessimizes the example fibonacci function, which
can be avoided by "-fno-optimize-sibling-calls" (which is the reason I assigned
the bug to tree-optimization)

The non-optimal code is generated at least by
  gcc 4.5.3 (Debian 4.5.3-12)
  gcc version 4.9.2 (Debian 4.9.2-10)
  gcc version 5.1.1 20150507 (Debian 5.1.1-5)

I will focus on gcc 5.1.1 in the remaining report.

Configured with: ../src/configure -v --with-pkgversion='Debian 5.1.1-5'
--with-bugurl=file:///usr/share/doc/gcc-5/README.Bugs
--enable-languages=c,ada,c++,java,go,d,fortran,objc,obj-c++ --prefix=/usr
--program-suffix=-5 --enable-shared --enable-linker-build-id
--libexecdir=/usr/lib --without-included-gettext --enable-threads=posix
--libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu
--enable-libstdcxx-debug --enable-libstdcxx-time=yes
--with-default-libstdcxx-abi=c++98 --disable-libstdcxx-dual-abi
--enable-gnu-unique-object --disable-vtable-verify --enable-libmpx
--enable-plugin --with-system-zlib --disable-browser-plugin
--enable-java-awt=gtk --enable-gtk-cairo
--with-java-home=/usr/lib/jvm/java-1.5.0-gcj-5-amd64/jre --enable-java-home
--with-jvm-root-dir=/usr/lib/jvm/java-1.5.0-gcj-5-amd64
--with-jvm-jar-dir=/usr/lib/jvm-exports/java-1.5.0-gcj-5-amd64
--with-arch-directory=amd64 --with-ecj-jar=/usr/share/java/eclipse-ecj.jar
--enable-objc-gc --enable-multiarch --with-arch-32=i586 --with-abi=m64
--with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic
--enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu
--target=x86_64-linux-gnu

gcc is invoked as: g++-5 -O3 -march=core2 -std=c++0x
stack-overflow-32974625.cc; ./a.out
compared to g++-5 -O3 -march=core2 -std=c++0x -fno-optimize-sibling-calls
stack-overflow-32974625.cc; ./a.out


There are no error or warning messages printed by the compiler or linker (even
if warning would be enabled by -Wall -Wextra)

The file stack-overflow-32974625.ii is attached.

Timing with g++ 5.1.1 on a Core2Duo T7200 under 64-bit linux (cpu frequency
scaling set to "performance"):
With -fno-optimize-sibling-calls: 34.5us/iteration
Without -fno-optimize-sibling-calls: 68us/iteration

[Bug tree-optimization/68008] Pessimization of simple non-tail-recursive functions

[glisse at gcc dot gnu.org]

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

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
Probably not related, but at -O2, I notice that sccp produces the
"interesting":

  _3 = n_4(D) + -2;
  _12 = (unsigned int) n_4(D);
  _10 = _12 + 4294967294;
  _2 = _10 / 2;
  _11 = (int) _2;
  _9 = _11 * -2;
  _17 = _3 + _9;

(n is of type int)
which we don't simplify at gimple level (looks like we do in RTL).

Even with the X+(X/Y)*-Y thing that is in review (and assuming it supports
convert in the right places, which may not be the case), it would require at
least CSE-ing _10 to (unsigned int) _3. Well, maybe since 2 is a power of 2, we
could simplify _9 = _10 & -2; and depending on which representation is
preferred, (n-2)&-2 might become (n&-2)-2 and we might eventually get there,
but that would be very fragile.