gcc: is there no tail recursion if I return std::s

2019-05-22 22:57发布

As per my answer in Write a recursive function that reverses the input string, I've tried seeing whether clang++ -O3 or g++ -O3 would make a tail-recursion optimisation, using some of the suggestions from How do I check if gcc is performing tail-recursion optimization?, but it doesn't look like any tail recursion optimisation is taking place. Any idea why?

Does this have to do with the way C++ objects are created and destroyed? Is there any way to make it work?

The programme:

% cat t2.cpp
#include <iostream>
#include <string>

std::string
rerev1(std::string s)
{
        if (s.empty())
                return s;
        return rerev1(s.substr(1)) + s[0];
}

std::string
rerev2(std::string s, std::string b = "")
{
        if (s.empty())
                return b;
        return rerev2(s.substr(1), s[0] + b);
}

int
main()
{
        std::cout << rerev1("testing") << std::endl;
        std::cout << rerev2("testing") << std::endl;
}

The testing (if the tail recursion optimisation would have been taking place, I'd expect there'd only be one call to each version of the function, not two):

% clang++ -Wall -O3 t2.cpp
% objdump --disassemble a.out | fgrep rerev | fgrep callq
  400d8f:       e8 ac ff ff ff          callq  400d40 <_Z6rerev1Ss>
  400fd1:       e8 5a ff ff ff          callq  400f30 <_Z6rerev2SsSs>
  401168:       e8 d3 fb ff ff          callq  400d40 <_Z6rerev1Ss>
  40128d:       e8 9e fc ff ff          callq  400f30 <_Z6rerev2SsSs>

% g++ -O3 t2.cpp
% objdump --disassemble a.out | fgrep rerev | fgrep callq
  400c93:       e8 28 02 00 00          callq  400ec0 <_Z6rerev1Ss>
  400cfa:       e8 11 03 00 00          callq  401010 <_Z6rerev2SsSs>
  400f25:       e8 96 ff ff ff          callq  400ec0 <_Z6rerev1Ss>
  4010ca:       e8 41 ff ff ff          callq  401010 <_Z6rerev2SsSs>

% clang++ -v
Debian clang version 3.0-6.2 (tags/RELEASE_30/final) (based on LLVM 3.0)
Target: x86_64-pc-linux-gnu
Thread model: posix

% g++ --version
g++ (Debian 4.7.2-5) 4.7.2
Copyright (C) 2012 Free Software Foundation, Inc.

0条回答
登录 后发表回答