Eu estou procurando uma maneira de alocar variáveis ​​locais para registradores. Estou ciente de alguns métodos sérios para fazer isso (ou seja, aqueles mencionadosna Wikipedia), mas eu estou preso em como "derramar" é realizado. Além disso, a literatura relevante é bastante intimidante. Eu espero que haja algo mais simples que satisfaça minhas prioridades:

Correção - um algoritmo que irá gerar o código correto, independentemente de quantas variáveis ​​locais existem.Simplicidade - algo que eu posso entender sem ter que ler muita literatura.Eficiência - precisa ser melhor que o método atual, que é:

Traduzir uma operaçãox = y # z para:

movl y, %eax
movl z, %ebx
op %ebx, %eax
movl %eax, x

Como estou visando a Intel 386, algumas restrições relevantes são:

As operações binárias aceitam dois argumentos, um dos quais é uma origem e um destino. Operações unárias levam um único argumento.As operações só podem acessar um local de memória; operações binárias, portanto, precisam de pelo menos um argumento em um registrador.Há no máximo seis registros disponíveis:%eax %ebx %ecx %edx %esi %edi. (%ebp também pode ser incluído como último recurso.)Existem casos especiais, como para registros de divisão e retorno de números inteiros, mas posso ignorá-los por enquanto.

Existem três etapas que o compilador realiza no momento:

i386ification: todas as operações são convertidas em um formulárioa = a # b (oua = #a para operações unárias).Análise de vivacidade: os conjuntos de variáveis ​​ao vivo antes e depois de cada operação são determinados.Alocação de registro: um gráfico de interferência é construído e colorido.

E então o compilador joga seus crayons no ar e não sabe o que fazer a seguir.

Exemplo

public int mf(int cr, int ci) {
    int i = 0;
    int zr = 0;
    int zi = 0;

    while (i < 100 && zr*zr + zi*zi < 4) {
        int t = zr * zr - zi * zi + cr;
        zi = 2 * zr * zi + ci;
        zr = t;

        i = i + 1;
    }
    return i;
}

Aqui está o bonito gráfico de interferência para a função, e o CFG com informações de vivacidade. A imagem CFG requer alguma rolagem vertical, infelizmente.

Gráfico de interferência para uma função em 14 variáveisGráfico de fluxo de controle para uma função, com informações de atividade

Sete cores foram usadas. Eu gostaria de derramar um deles (ou o conjunto de variáveis ​​atribuído a essa cor). O método de escolha que não é muito importante. O que é complicado é como lidar com as variáveis ​​derramadas.

Vamos dizer que eu derrame "rosa", que é o conjunto de variáveist, $t4, $t7. Isso significa que as operações referentes a uma dessas variáveis ​​irão acessá-lo a partir de sua posição no quadro da pilha, em vez de através de um registro. Isso deve funcionar para este exemplo.

Mas e se o programa fosse:

...
a = a + b
...

e ambosa eb teve que ser derramado? Não consigo emitir uma instruçãoaddl b, a com dois endereços de memória. Eu precisaria de outro registrador de reserva para manter temporariamente um dos operandos, e isso significa derramar outra cor. Isto sugere um método geral de:

Se todas as variáveis ​​puderem ser coloridas comr cores, ótimo!Caso contrário, derrame algumas cores e suas variáveis ​​associadas.Se existir uma operação que acesse duas variáveis ​​derramadas, derramar outra cor e usar o registrador sobressalente para armazenamento temporário para todas essas operações.

Neste ponto, suspeito que muito mais coisas estão sendo derramadas do que o necessário, e me pergunto se existe uma maneira mais inteligente de derramar coisas, como derramar parte da vida útil de uma variável, em vez de toda a própria variável. Existem algumas técnicas simples (ish) que eu poderia usar aqui? Novamente, eu não estou apontando particularmente alto - certamente não alto o suficiente para exigir a leitura de algo muito profundo. ;-)

Problemas específicos

O principal problema específico é: quando uma variável é derramada, como isso afeta as instruções geradas? Todas as instruções que utilizam essa variável precisam acessá-la diretamente na memória (a partir de sua posição de pilha)? Como isso funcionará se uma operação usar duas variáveis ​​derramadas? (A arquitetura não permite instruções para acessar dois locais de memória distintos.)

Problemas secundários são:

Como faço para determinar onde inserir instruções de carga / armazenamento, para correção (e, menos importante, eficiência)?Posso derramar uma variável apenas para essa parte de sua vida útil quando ela não estiver em uso imediato e não a usar mais tarde? De modo que todas as instruções atuem em registros não ganhos. Uma variável pode viver em registros diferentes em momentos diferentes.Posso ser um pouco mais eficiente com casos especiais? Por exemplo,%eax é usado para o valor de retorno, portanto, seria bom se a variável a ser retornada fosse alocada para aquele registro no momento em que o retorno foi encontrado. Da mesma forma, alguns registradores são "callee-save", portanto, se menos variáveis ​​estivessem ativas no momento de uma chamada de função, tê-las alocadas em registros que não salvam callee significaria evitar o armazenamento desses registros.O formulário SSA ajudaria muito (se for o caso)? Ser capaz de eliminar subexpressões comuns e avaliar constantes poderia reduzir a pressão de registro, mas, de outra forma, teria algum efeito?

Os aspectos que não estou preocupado (agora) são:

Alocação e otimização de pilha: ela é implementada de forma ingenua e pode ser otimizada usando o gráfico de interferência, se necessário.Eficiência de tempo de compilação, contanto que termine. (NP-completude não implica que um dado algoritmo deva ser evitado.)Atualizar

Desculpe o tempo de inatividade - estive pensando nas respostas dadas e tentando encontrar uma abordagem fácil para começar a implementar algumas das ideias. Para ser honesto, eu tenho procrastinado ...: \ Eu encontrei a apresentação muito legal (PPT, infelizmente):

http://www.cs.princeton.edu/courses/archive/spr05/cos320/notes/Register%20Allocation.ppt

O que responde à pergunta sobre como lidar com necessidades de operação específicas (como usar o mesmo registro para origem e destino; ou precisar de um certo registro para algumas operações). O que eu não tenho certeza é se o ciclo de Coloração-Aliviar-Alocação termina.

Vou tentar fazer um trabalho real em breve e espero fechar a questão.

Você está correto: você estará derramando registros que não estão atualmente em uso para fornecer espaço para aqueles que serão usados. Então, todas as operações podem estar em registros. Para soltar isso e fazer algumas operações diretamente em registradores derramados, altere seu algoritmo de alocação de registro para permitir que no máximo um registro permaneça derramado durante as instruções de registro para registro ... mas não é necessário.