Perguntas sobre otimizações do compilador

Question

1. Quais são algumas das maneiras pelas quais um compilador elimina recomputações repetidas de subexpressões?Como você controla as subexpressões?E como você identifica os repetidos?
2. Além do uso de operadores bit a bit, quais são algumas das técnicas de redução de força usadas pelos compiladores comuns?

Answer 1

1. Acredito que muitos compiladores usam Ssapre (eliminação de redundância parcial de atribuição estática) para eliminar expressões repetidas. Isso exige que o código esteja em SSA Form, permitindo muito mais otimizações.

2. Não tenho muita certeza sobre este, mas olhe para Esta lista de passes de LLVM. Llvm é um IR de otimização para compiladores que geralmente é mais rápido que o GCC. Há uma pequena explicação de cada passe. Se você precisar de mais informações, consulte a fonte LLVM para esses passes. Está escrito em C ++, mas é bastante limpo e compreensível.

EDIT: A propósito, se você estiver desenvolvendo um compilador, eu recomendo o LLVM, é muito fácil de usar e gera código altamente otimizado.

Answer 2

Para 1, o nome da otimização que você está procurando é a eliminação comum da subexpressão (CSE). Dependendo da sua representação, isso pode ser bastante fácil. Geralmente, um compilador terá alguma representação intermediária de um programa em que as operações são divididas o máximo possível e linearizadas. Por exemplo, a expressão c = a * b + a * b pode ser quebrado como:

v1 = a * b
v2 = a * b
c = v1 + v2

Assim, você pode fazer o CSE em um nível muito baixo, procurando operações com o mesmo operador e operando. Quando você encontra uma duplicata (V2 neste caso), você substitui todas as instâncias pelo original. Para que pudéssemos simplificar o código acima para ser:

v1 = a * b
c = v1 + v1

Isso geralmente assume que você atribui apenas cada variável uma vez (formulário de atribuição estática única), mas pode implementar algo assim sem essa restrição. Isso fica mais complicado quando você tenta executar essa otimização entre as filiais. Como Zifre menciona, procure eliminação parcial de redundância.

De qualquer forma, você obtém algumas melhorias básicas e tudo o que você precisa acompanhar são expressões básicas. Você pode dar um passo adiante e procurar identidades aritméticas. Por exemplo, a * b é o mesmo que b * a. Também, x * (y + z) = x * y + x * z. Isso torna sua otimização mais complicada e não está claro que isso lhe daria tanta melhoria de desempenho. Curiosamente, a maior parte do benefício de uma otimização de CSE vem de cálculos de endereço, como acessos de matriz, e você não precisará de identidades complicadas como as acima.

Para 2, quais reduções de força são úteis realmente depende da arquitetura para a qual você compila. Geralmente, isso envolve apenas a transformação de multiplicações e divisões em turnos, adições e subtrações.

Answer 3

Eu recomendo duas referências impressas sobre esses assuntos:

1. Projeto e implementação avançada do compilador Por Steven S. Muchnick
2. Construindo um compilador de otimização por Robert Morgan

O Livro Muchnick está do lado formal, mas é muito legível e possui boas descrições de todas as importantes técnicas de otimização. O livro Morgan tem uma sensação muito mais prática e seria uma ótima base para um projeto do compilador focado nas técnicas de otimização. Nenhum dos livros tem muito a dizer sobre análise lexical ou análise, o conhecimento desses assuntos é assumido.

Answer 4

Para adicionar mais um livro à lista de recomendações, confira "Delight's Hacker" por Henry S. Warren. É um ótimo compêndio de técnicas para otimizar operações comuns, como transformar divisões inteiras em multiplicações.

Answer 5

Você está procurando eliminação de redundância parcial (PRE).Tanto o CSE (das outras respostas) quanto o movimento de código invariante em loop são incluídos no PRE.(Uma variação do PRE é Lazy Code Motion, que acredito ser ideal).

Confira Notas de aula de Keith Cooper, que parecem descrever muito bem as técnicas.

Fazer NÃO use SSAPRE.AFAIK, isso requer uma forma específica de SSA conhecida como HSSA, que tem algumas desvantagens:

• É bem complicado
• Requer numeração de valor global (e portanto o SSAPRE não fornece numeração de valor, pois já se espera que exista).
• Ele não fornece nada se sua linguagem não suportar ponteiros para empilhar variáveis ​​(e se suportar, pare de escrever sua própria análise e use LLVM ou gcc).
• O gcc usou o HSSA por um tempo, mas eles se afastaram dele.
• O LLVM fez experiências com isso, mas AFAIK eles não usam mais.

EDITAR:

O livro de Muchnick tem uma descrição detalhada, vinculada a outra resposta.