Projeto do compilador - Otimização de código

Otimização é uma técnica de transformação de programa, que tenta melhorar o código fazendo-o consumir menos recursos (ou seja, CPU, memória) e entregar alta velocidade.

Na otimização, construções de programação geral de alto nível são substituídas por códigos de programação de baixo nível muito eficientes. Um processo de otimização de código deve seguir as três regras fornecidas abaixo:

O código de saída não deve, de forma alguma, alterar o significado do programa.
A otimização deve aumentar a velocidade do programa e, se possível, o programa deve demandar menos número de recursos.
A otimização em si deve ser rápida e não deve atrasar o processo geral de compilação.

Esforços para um código otimizado podem ser feitos em vários níveis de compilação do processo.

No início, os usuários podem alterar / reorganizar o código ou usar algoritmos melhores para escrever o código.
Depois de gerar o código intermediário, o compilador pode modificar o código intermediário por meio de cálculos de endereço e melhoria de loops.
Ao produzir o código da máquina de destino, o compilador pode fazer uso da hierarquia da memória e dos registros da CPU.

A otimização pode ser categorizada amplamente em dois tipos: independente da máquina e dependente da máquina.

Otimização independente da máquina

Nessa otimização, o compilador pega o código intermediário e transforma uma parte do código que não envolve nenhum registro da CPU e / ou locais de memória absolutos. Por exemplo:

do
{
   item = 10;
   value = value + item; 
} while(value<100);

Este código envolve a atribuição repetida do item identificador, que se colocarmos desta forma:

Item = 10;
do
{
   value = value + item; 
} while(value<100);

não deve apenas salvar os ciclos da CPU, mas pode ser usado em qualquer processador.

Otimização dependente da máquina

A otimização dependente da máquina é feita depois que o código de destino foi gerado e quando o código é transformado de acordo com a arquitetura da máquina de destino. Envolve registros de CPU e pode ter referências de memória absolutas em vez de referências relativas. Os otimizadores dependentes de máquina se esforçam para tirar o máximo proveito da hierarquia de memória.

Blocos Básicos

Os códigos-fonte geralmente possuem uma série de instruções, que são sempre executadas em sequência e são consideradas os blocos básicos do código. Estes blocos básicos não possuem nenhuma instrução de salto entre eles, ou seja, quando a primeira instrução for executada, todas as instruções do mesmo bloco básico serão executadas em sua seqüência de aparecimento sem perder o controle de fluxo do programa.

Um programa pode ter várias construções como blocos básicos, como instruções condicionais IF-THEN-ELSE, SWITCH-CASE e loops como DO-WHILE, FOR e REPEAT-UNTIL, etc.

Identificação de bloco básico

Podemos usar o seguinte algoritmo para encontrar os blocos básicos em um programa:

Pesquisar declarações de cabeçalho de todos os blocos básicos de onde um bloco básico começa:
- Primeira declaração de um programa.
- Declarações que são alvo de qualquer ramificação (condicional / incondicional).
- Declarações que seguem qualquer declaração de ramo.
As instruções de cabeçalho e as instruções que as seguem formam um bloco básico.
Um bloco básico não inclui nenhuma declaração de cabeçalho de qualquer outro bloco básico.

Os blocos básicos são conceitos importantes do ponto de vista de geração e otimização de código.

Os blocos básicos desempenham um papel importante na identificação de variáveis, que estão sendo usadas mais de uma vez em um único bloco básico. Se alguma variável estiver sendo usada mais de uma vez, a memória do registro alocada para aquela variável não precisa ser esvaziada, a menos que o bloco termine a execução.

Gráfico de fluxo de controle

Os blocos básicos de um programa podem ser representados por meio de gráficos de fluxo de controle. Um gráfico de fluxo de controle mostra como o controle do programa está sendo passado entre os blocos. É uma ferramenta útil que ajuda na otimização, ajudando a localizar quaisquer loops indesejados no programa.

Otimização de Loop

A maioria dos programas é executada como um loop no sistema. Torna-se necessário otimizar os loops para economizar ciclos de CPU e memória. Os loops podem ser otimizados pelas seguintes técnicas:

Invariant code: Um fragmento de código que reside no loop e calcula o mesmo valor em cada iteração é chamado de código invariante do loop. Esse código pode ser movido para fora do loop salvando-o para ser calculado apenas uma vez, em vez de a cada iteração.
Induction analysis : Uma variável é chamada de variável de indução se seu valor for alterado dentro do loop por um valor invariante do loop.
Strength reduction: Existem expressões que consomem mais ciclos de CPU, tempo e memória. Essas expressões devem ser substituídas por expressões mais baratas sem comprometer a saída da expressão. Por exemplo, a multiplicação (x * 2) é mais cara em termos de ciclos de CPU do que (x << 1) e produz o mesmo resultado.

Eliminação de código morto

Código morto é uma ou mais declarações de código, que são:

Nunca executado ou inacessível,
Ou, se executado, sua saída nunca é usada.

Assim, o código morto não desempenha nenhum papel em qualquer operação do programa e, portanto, pode ser simplesmente eliminado.

Código parcialmente morto

Existem algumas instruções de código cujos valores calculados são usados apenas em certas circunstâncias, ou seja, às vezes os valores são usados e às vezes não. Esses códigos são conhecidos como código parcialmente morto.

O gráfico de fluxo de controle acima representa um pedaço do programa onde a variável 'a' é usada para atribuir a saída da expressão 'x * y'. Vamos supor que o valor atribuído a 'a' nunca seja usado dentro do loop. Imediatamente após o controle sair do loop, 'a' recebe o valor da variável 'z', que seria usada posteriormente no programa. Concluímos aqui que o código de atribuição de 'a' nunca é usado em qualquer lugar, portanto, pode ser eliminado.

Da mesma forma, a imagem acima mostra que a declaração condicional é sempre falsa, o que implica que o código, escrito no caso verdadeiro, nunca será executado, portanto, pode ser removido.

Redundância Parcial

Expressões redundantes são calculadas mais de uma vez no caminho paralelo, sem qualquer mudança nos operandos. Ao passo que as expressões redundantes parciais são calculadas mais de uma vez em um caminho, sem qualquer mudança nos operandos. Por exemplo,

[expressão redundante]	[expressão parcialmente redundante]

O código invariante de loop é parcialmente redundante e pode ser eliminado usando uma técnica de movimento de código.

Outro exemplo de código parcialmente redundante pode ser:

If (condition)
{
   a = y OP z;
}
else
{
   ...
}
c = y OP z;

Assumimos que os valores dos operandos (y e z) não são alterados a partir da atribuição de variável a para variável c. Aqui, se a declaração da condição for verdadeira, y OP z é calculado duas vezes, caso contrário, uma vez. O movimento do código pode ser usado para eliminar essa redundância, conforme mostrado abaixo:

If (condition)
{
   ...
   tmp = y OP z;
   a = tmp;
   ...
}
else
{
   ...
   tmp = y OP z;
}
c = tmp;

Aqui, se a condição é verdadeira ou falsa; y OP z deve ser calculado apenas uma vez.

↰ Previous page