O que acontece com o uso de registros em chamadas de funções profundamente aninhadas (em teoria)?

Question

Estou longe de ser capaz de construir um teste significativo para isso usando raio divino ou alguma ferramenta de compilação C.Mas basicamente estou me perguntando como seria ter chamadas de função profundamente aninhadas, onde cada função tivesse, digamos, uma dúzia de variáveis ​​temporárias.O que acontece com o uso do registro?Parece que tudo teria que ser armazenado na memória e o uso do registrador seria quase insignificante.Como é na realidade?Onde eu estou errando?

Answer 1

Ignore a recursão por enquanto e finja que uma chamada recursiva é igual a qualquer outra chamada.

Então a solução é fácil:todas as variáveis ​​locais são espalhadas na pilha entre chamadas, incluindo a chamada recursiva.Então, sim, se houver recursão profunda, a maioria das variáveis ​​locais residirá na pilha a maior parte do tempo.

Cada plataforma (sistema operacional + família de CPU) define um protocolo chamado interface binária do aplicativo, ou ABI, para abreviar.Especifica como os parâmetros são passados ​​para uma função, como os valores são retornados, como a pilha deve ser gerenciada e assim por diante.Se você quiser ver como é uma ABI do mundo real, consulte o SysV ABI para Intel x86-64/AMD64.Quase todos os sistemas operacionais seguem esta ABI nessa família de CPUs, sendo o Windows a exceção mais notável.

A ABI especificará que alguns registros não são preservados nas chamadas de função (ou seja,eles são salvar chamador) e alguns são preservados (ou seja,eles são chamado-salvar).Um registro callee-save deve ser preservado por uma função se ela quiser usar esse registro, e um registro caller-save deve ser explicitamente espalhado por uma chamada se o chamador precisar do valor.

Também é possível otimizar a recursão, desde que a função se apresente ao resto do sistema como se obedecesse à ABI.É onde as coisas começam a ficar interessantes.

A otimização da chamada final é o cenário mais comum.Se a última coisa que uma função faz em algum caminho de código é chamar outra função, às vezes é possível transformar a última chamada em um salto.E se for uma chamada recursiva, ela poderá ser transformada em um loop.

Então, é isso:

foo(args)
{
    if (the base case applies) {
        return something();
    }
    before_the_recursive_call();
    foo(recursive_args);
}

pode ser transformado nisso:

foo(args)
{
    while (the base case doesn't apply) {
        before_the_recursive_call();
        args = recursive_args;
    }
    return something();
}

Mas, nesse caso, nenhuma variável local precisa ser salva na chamada final.Portanto, nada, pelo menos em teoria, precisa ser jogado na pilha ali.

Além disso, em C++, a semântica do RAII e o tratamento de exceções geralmente impossibilitam a otimização da chamada final, portanto, você não verá isso com frequência em compiladores para a família de linguagens C.

Existe uma otimização relacionada chamada "otimização de recursão intermediária", que é usada para o cenário recursivo mais familiar, onde há uma única chamada recursiva no meio de uma função:

foo(args)
{
    if (the base case applies) {
        return something();
    }
    before_the_recursive_call();
    foo(recursive_args);
    return after_the_recursive_call();
}

Isso pode ser transformado em algo assim:

foo(args)
{
    while (the base case does not apply) {
        before_the_recursive_call();
        push_anything_to_the_stack_that_the_last_part_needs();
        args = recursive_args;
    }

    return_value = something();  // base case

    while (pop_the_stack()) {
        return_value = after_the_recursive_call();
    }
    return return_value;
}

Novamente, isso é raro em linguagens do tipo C.Você normalmente o encontraria em linguagens funcionais ou lógicas que não possuem construções de loop e possuem apenas recursão.Em uma linguagem como essa, muitas vezes vale a pena se esforçar muito para otimizar a recursão em loops.