Registrar alocação e derramamento, o caminho mais fácil?

https://stackoverflow.com/questions/1960888

21-09-2019
|

Pergunta

Estou procurando uma maneira de alocar variáveis locais para registros.Estou ciente de alguns métodos sérios para fazer isso (ou seja, aqueles mencionados na Wikipédia), mas não sei como o "derramamento" é realizado.Além disso, a literatura relevante é bastante intimidante.Espero que haja algo mais simples que satisfaça minhas prioridades:

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

Traduzir uma operação x = y # z para:

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

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

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

Existem três etapas pelas quais o compilador passa no momento:

i386ificação:todas as operações são convertidas para um formulário a = a # b (ou a = #a para operações unárias).
Análise de vivacidade:os conjuntos de variáveis ativas 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 lápis de cor 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 gráfico de interferência bastante bonito para a função e o CFG com informações de vivacidade.A imagem CFG requer alguma rolagem vertical, infelizmente.

Sete cores foram usadas.Gostaria de revelar um deles (ou o conjunto de variáveis atribuídas a essa cor).O método de escolha que não é muito importante.O que fica complicado é como lidar com as variáveis espalhadas.

Digamos que eu derrame "rosa", que é o conjunto de variáveis t, $t4, $t7.Isso significa que aquelas operações referentes a uma dessas variáveis irão acessá-la a partir de sua posição no quadro da pilha, e não através de um registro.Isso deve funcionar para este exemplo.

Mas e se o programa fosse:

...
a = a + b
...

e ambos a e b teve que ser derramado?Não consigo emitir uma instrução addl b, a com dois endereços de memória.Eu precisaria de outro registro sobressalente para reter temporariamente um dos operandos, e isso significa derramar outra cor.Isso sugere um método geral de:

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

Neste ponto, eu suspeitaria que muito mais coisas estão sendo derramadas do que o necessário, e me pergunto se existe alguma maneira mais inteligente de derramar as coisas, como derramar parte do tempo de vida de uma variável, em vez de toda a variável em si.Existem algumas técnicas simples (ish) que eu poderia usar aqui?Mais uma vez, não estou almejando algo particularmente alto – certamente não o suficiente para exigir uma leitura muito profunda.;-)

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 usam essa variável precisam acessá-la diretamente na memória (a partir de sua posição na pilha)?Como isso funcionará se uma operação usar duas variáveis derramadas?(A arquitetura não permite que instruções acessem dois locais de memória distintos.)

Os problemas secundários são:

Como determino onde inserir instruções de carregamento/armazenamento, para correção (e menos importante, eficiência)?
Posso derramar uma variável apenas durante aquela parte de sua vida útil quando ela não estiver em uso imediato e descartá-la mais tarde?Para que todas as instruções atuem em registradores não derramados.Uma variável pode residir em registros diferentes em momentos diferentes.
Posso ser um pouco mais eficiente com casos especiais.Por exemplo, %eax é usado para o valor de retorno, então seria bom se a variável a ser retornada estivesse alocada para aquele registro no momento em que o retorno fosse encontrado.Da mesma forma, alguns registros são "salvos por chamada", portanto, se menos variáveis estivessem ativas no momento de uma chamada de função, alocá-las para registros não salvos por chamada significaria que posso evitar o armazenamento desses registros.
O formulário SSA ajudaria muito (se é que ajudaria)?Ser capaz de eliminar subexpressões comuns e avaliar constantes pode reduzir (?) a pressão do registro, mas caso contrário teria algum efeito?

Os aspectos com os quais não estou preocupado (no momento) são:

Alocação e otimização de pilha:ele já foi implementado de forma ingênua e pode ser otimizado usando o gráfico de interferência, se necessário.
Eficiência em tempo de compilação, desde que termine.(NP-completude não implica que um determinado algoritmo deva ser evitado.)

Atualizar

Desculpe pelo 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 sincero, estou procrastinando...:-\

Achei a apresentação muito legal (PPT, infelizmente):

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

O que responde à questão sobre como lidar com necessidades operacionais específicas (como usar o mesmo registro para origem e destino;ou necessitando de um determinado registro para algumas operações).O que não tenho certeza é se o ciclo Liveness-Coloring-Allocation termina.

Tentarei fazer algum trabalho real em breve e espero encerrar a questão.

Solução

Já usei uma abordagem gananciosa em um alocador JVM, que funcionou muito bem.Basicamente comece no topo de um bloco básico com todos os valores armazenados na pilha.Em seguida, basta verificar as instruções adiante, mantendo uma lista de registros que contêm um valor e se o valor está sujo (precisa ser escrito de volta).Se uma instrução usa um valor que não está em um registrador (ou não está no registrador correto), emita um load (ou move) para colocá-lo em um registrador livre antes da instrução.Se uma instrução escreve um valor, certifique-se de que ele esteja em um registrador e marque-o como sujo após a instrução.

Se você precisar de um registro, descarte um registro usado, desalocando o valor dele e gravando-o na pilha se estiver sujo e ativo.No final do bloco básico, escreva de volta quaisquer registros sujos e ativos.

Este esquema deixa claro exatamente para onde vão todas as cargas/armazenamentos, você as gera à medida que avança.É facilmente adaptável a instruções que recebem um valor na memória ou que podem receber qualquer um dos dois argumentos na memória, mas não ambos.

Se você concorda em ter todos os dados na pilha em cada limite básico de bloco, esse esquema funciona muito bem.Deve fornecer resultados semelhantes à varredura linear dentro de um bloco básico, pois basicamente faz coisas muito semelhantes.

Você pode ficar arbitrariamente complicado sobre como decidir quais valores distribuir e quais registros alocar.Algumas antecipações podem ser úteis, por exemplo, marcando cada valor com um registro específico que ele precisa estar em algum ponto do bloco básico (por exemplo,eax para um valor de retorno, ou ecx para um valor de deslocamento) e preferindo esse registro quando o valor é alocado pela primeira vez (e evitando esse registro para outras alocações).Mas é fácil separar a correção do algoritmo da heurística de melhoria.

Usei esse alocador em um compilador SSA, YMMV.

Outras dicas

Primeiro:Não existe uma maneira inteligente de fazer isso.O problema é NP-completo ;-)

Como é feito o derramamento:

Você executa seu algoritmo de alocação de registro e obtém uma lista de variáveis que precisa distribuir.Agora você pode alocar algum espaço na pilha no início da sua função.Vincule cada variável derramada a um lugar na pilha.Se você deseja ser inteligente, agrupe a memória com faixas ativas não sobrepostas.Sempre que precisar derramar um registro salve-o na memória e carregue-o quando for necessário novamente.

Como lidar com eax:

Marcar o cadastro como preenchido, mas não armazenar nenhuma variável nele (pré-alocação).Isso fará com que o gerador de código limpe esse registro.Para ser inteligente, armazene o valor em outro registro, se for benéfico.

Maneiras fáceis e corretas de lidar com derramamentos:

Apenas derrame tudo.Isso pressupõe que o intervalo ativo de cada variável é o programa inteiro.Isso pode ser aumentado usando coisas como LRU ou contagem de uso para escolher quais registros devem ser liberados.

A próxima melhor coisa a fazer é provavelmente alocação de registro de varredura linear.Deve ser bastante fácil de implementar, mesmo ao usar a pré-alocação.Eu sugiro que você dê uma olhada no artigo vinculado.

Respostas Específicas

O que correção significa para você?Mesmo algoritmos de alocação simples estão corretos se você não cometer um erro de programação.A correção (matemática) da prova é muito mais difícil.Tanto as cargas quanto os armazenamentos precisam ser inseridos antes que o valor/registro seja necessário novamente.Ambos precisam ser inseridos após o valor ser armazenado/criado.
Sim.Se você programar dessa forma.Se o seu algoritmo puder lidar com um valor em vários registros durante o tempo de atividade, você poderá usar essas otimizações.
Cabe novamente a você implementar certas melhorias.Uma possibilidade seria bloquear eax apenas quando necessário, não para todo o programa.
Sob certas condições, o SSA ajuda.Os gráficos de inferência do código SSA são sempre cordal, o que significa que não há ciclo com mais de 3 nós.Este é um caso especial de coloração de grafos, no qual uma coloração mínima pode ser encontrada em tempo polinomial.A conversão para SSA não significa necessariamente mais ou menos pressão registradora.Embora o formulário SSA geralmente tenha mais variáveis, estes tendem a ter tempos de vida menores.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow