Quais, se houver, compiladores C ++ fazem otimização de recursão de cauda?

Parece-me que funcionaria perfeitamente bem na otimização da recursão de cauda em C e C ++, mas durante a depuração, nunca pareço ver uma pilha de quadros que indica essa otimização. Isso é bom, porque a pilha me diz o quão profunda é a recursão. No entanto, a otimização também seria agradável.

Algum compilador C ++ faz essa otimização? Por quê? Por que não?

Como instruo o compilador a fazer isso?

• Para MSVC: /O2ou/Ox
• Para o GCC: -O2ou-O3

Que tal verificar se o compilador fez isso em um determinado caso?

• Para MSVC, habilite a saída PDB para rastrear o código e, em seguida, inspecione o código
• Para o GCC ..?

Eu ainda aceitaria sugestões de como determinar se uma determinada função é otimizada assim pelo compilador (embora eu ache reconfortante que o Konrad me diga para assumi-la)

Sempre é possível verificar se o compilador faz isso fazendo uma recursão infinita e verificando se isso resulta em um loop infinito ou em um estouro de pilha (fiz isso com o GCC e descobri que -O2é suficiente), mas quero ser capaz de verificar uma determinada função que eu sei que terminará de qualquer maneira. Eu adoraria ter uma maneira fácil de verificar isso :)

Após alguns testes, descobri que os destruidores arruinam a possibilidade de fazer essa otimização. Às vezes, pode valer a pena alterar o escopo de determinadas variáveis ​​e temporários para garantir que elas fiquem fora do escopo antes do início da instrução de retorno.

Se qualquer destruidor precisar ser executado após a chamada final, a otimização da chamada final não poderá ser realizada.

Todos os compiladores mainstream atuais realizam a otimização de chamada de cauda razoavelmente bem (e o fazem há mais de uma década), mesmo para chamadas recursivas mutuamente , como:

int bar(int, int);

int foo(int n, int acc) {
    return (n == 0) ? acc : bar(n - 1, acc + 2);
}

int bar(int n, int acc) {
    return (n == 0) ? acc : foo(n - 1, acc + 1);
}

Deixar o compilador fazer a otimização é simples: basta ativar a otimização para obter velocidade:

• Para MSVC, use /O2ou /Ox.
• Para GCC, Clang e ICC, use -O3

Uma maneira fácil de verificar se o compilador fez a otimização é executar uma chamada que de outra forma resultaria em um estouro de pilha - ou observando a saída do assembly.

Como uma nota histórica interessante, a otimização da chamada de cauda para C foi adicionada ao GCC no curso de uma tese de diploma por Mark Probst. A tese descreve algumas advertências interessantes na implementação. Vale a pena ler.

O gcc 4.3.2 destaca completamente esta função ( atoi()implementação ruim / trivial ) main(). O nível de otimização é -O1. Percebo que, se eu brincar com ele (mesmo mudando de staticpara extern, a recursão da cauda desaparece muito rápido, então eu não dependeria disso para a correção do programa.

#include <stdio.h>
static int atoi(const char *str, int n)
{
    if (str == 0 || *str == 0)
        return n;
    return atoi(str+1, n*10 + *str-'0');
}
int main(int argc, char **argv)
{
    for (int i = 1; i != argc; ++i)
        printf("%s -> %d\n", argv[i], atoi(argv[i], 0));
    return 0;
}

Assim como o óbvio (os compiladores não fazem esse tipo de otimização, a menos que você solicite), há uma complexidade sobre a otimização de chamada de cauda em C ++: destruidores.

Dado algo como:

   int fn(int j, int i)
   {
      if (i <= 0) return j;
      Funky cls(j,i);
      return fn(j, i-1);
   }

O compilador não pode (em geral) a chamada de cauda otimizar isso porque precisa chamar o destruidor cls após o retorno da chamada recursiva.

Às vezes, o compilador pode ver que o destruidor não tem efeitos colaterais visíveis externamente (portanto, isso pode ser feito mais cedo), mas geralmente não pode.

Uma forma particularmente comum disso é onde Funkyé realmente um std::vectorou similar.

A maioria dos compiladores não faz nenhum tipo de otimização em uma compilação de depuração.

Se estiver usando o VC, tente uma versão compilada com as informações do PDB ativadas - isso permitirá que você rastreie o aplicativo otimizado e, esperançosamente, deverá ver o que deseja. Observe, no entanto, que a depuração e o rastreamento de uma compilação otimizada o guiarão por todo o lado, e muitas vezes você não poderá inspecionar as variáveis ​​diretamente, pois elas acabam nos registros ou são totalmente otimizadas. É uma experiência "interessante" ...

Como Greg menciona, os compiladores não farão isso no modo de depuração. Não há problema em compilações de depuração serem mais lentas do que uma compilação de prod, mas elas não devem travar com mais frequência: e se você depende de uma otimização de chamada de cauda, ​​elas podem fazer exatamente isso. Por esse motivo, geralmente é melhor reescrever a chamada final como um loop normal. :-(