Otimização de Código

Uma otimização é uma reescrita do código já gerado que reduz custo — tempo, memória ou instruções — sem mudar o comportamento observável. Duas versões p e p′ são equivalentes observáveis quando, para toda entrada, coincidem valor devolvido, falhas e efeitos visíveis; escreve-se [[p]] = [[p′]].

Código morto, dobramento, análise de vida e movimentação deste tópico — e a coloração de temporários na geração de código — partem dessa equivalência.

As páginas se agrupam em três blocos. O primeiro decide quando a reescrita é legal — [[p]] = [[p′]] e custo menor — e em qual grafo o fato fica visível.

O segundo reescreve só a sequência linear de um bloco: remove a atribuição cujo destino não é lido e avalia contas feitas só de literais.

O terceiro percorre o CFG de um procedimento: calcula o que ainda será lido, reutiliza a expressão disponível em todo caminho e move o cálculo ao predecessor comum.

Classificar a passagem pelo grafo que ela enxerga está em Princípios de Otimização. Aplicar a reescrita dentro de um bloco, sem cruzar desvio, está em Otimização Local.

Remover y := 20 quando só z ainda é lido no mesmo bloco está em Otimização Local. Decidir se y está viva depois de um desvio, pelo live-in do CFG, está em Otimização Global.

Trocar 3 + 5 por 8 na sequência sem desvio está em Otimização Local. Reutilizar a+b nos dois ramos, ou movê-lo ao predecessor comum, está em Otimização Global.

Calcular live-in = use ∪ (live-out ∖ def) no CFG de um procedimento está em Otimização Global. Substituir a chamada pelo corpo do chamado, no grafo de chamadas, está em Princípios de Otimização.