Compiler Design-Code Optimization

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

em 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 abaixo indicadas:

• o código de saída não deve, de forma alguma, alterar o significado do programa.

• otimização deve aumentar a velocidade do programa e, se possível, o programa deve exigir menos número de recursos.

• a otimização deve ser rápida e não deve atrasar o processo global 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 mudar/reorganizar o código ou usar algoritmos melhores para escrever o código.

• depois de gerar código intermediário, o compilador pode modificar o código intermediário através de cálculos de endereços e aprimoramento de loops.

• ao produzir o código da máquina-alvo, o compilador pode fazer uso da hierarquia de memória e registros de CPU.

Optimization can be categorized genericamente into two types: machine independent and machine dependent.

otimização independente da máquina

nesta otimização, o compilador toma o código intermediário e transforma uma parte do código que não envolve quaisquer registros de CPU e/ou localizações absolutas de memória. Por exemplo:

do{ item = 10; value = value + item; } while(value
This code involves repeated assignment of the identifier item, which if we put this way:
Item = 10;do{ value = value + item; } while(value
should not only save the CPU cycles, but can be used on any processor.
Machine-dependent Optimization
Machine-dependent optimization is done after the target code has been generated and when the code is transformed according to the target machine architecture. It involves CPU registers and may have absolute memory references rather than relative references. Machine-dependent optimizers put efforts to take maximum advantage of memory hierarchy.
Basic Blocks
Source codes generally have a number of instructions, which are always executed in sequence and are considered as the basic blocks of the code. These basic blocks do not have any jump statements among them, i.e., when the first instruction is executed, all the instructions in the same basic block will be executed in their sequence of appearance without losing the flow control of the program.
A program can have various constructs as basic blocks, like IF-THEN-ELSE, SWITCH-CASE conditional statements and loops such as DO-WHILE, FOR, and REPEAT-UNTIL, etc.
Basic block identification
We may use the following algorithm to find the basic blocks in a program:



procurar as indicações do cabeçalho de todos os blocos básicos a partir dos quais um bloco básico começa:

primeira declaração de um programa.
declarações que são alvo de qualquer sucursal (condicional/incondicional).
declarações que seguem qualquer declaração de ramo.



as declarações de cabeçalho e as declaraçõ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.


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

blocos Básicos desempenham um papel importante na identificação de variáveis, que estão sendo utilizados mais de uma vez em um único bloco básico. Se alguma variável estiver a ser utilizada mais de uma vez, a memória de Registo atribuída a essa variável não precisa de ser esvaziada a menos que o bloco termine a execução.
Gráfico De Fluxo De Controle 
blocos básicos em um programa pode ser representado 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 são executados como um loop no sistema. Torna-se necessário otimizar os loops, a fim de salvar ciclos de CPU e memória. Loops podem ser otimizados pelas seguintes técnicas:


Invariantes de código : Um fragmento de código que reside no loop e calcula o mesmo valor em cada iteração é chamado de um loop invariável de código. Este código pode ser movido para fora do loop, salvando-o para ser computado apenas uma vez, em vez de com cada iteração.


Induction analysis : a variable is called an induction variable if its value is altered within the loop by a loop-invariant value.


redução de força: há expressões que consomem mais ciclos de CPU, tempo e memória. Estas 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) é caro em termos de ciclos de CPU que (x 


Mortos-código de Eliminação
código Morto é um ou mais de um código de instruções, que são:

nunca executado ou inacessível,
Ou se o executado, a sua saída nunca é usado.

 assim, código morto não desempenha nenhum papel em qualquer operação do programa e, portanto, pode simplesmente ser eliminado.
 código parcialmente morto
 existem algumas declarações de código cujos valores calculados são utilizados apenas em certas circunstâncias, ou seja, às vezes os valores são usados e às vezes não são. Tais códigos são conhecidos como parcialmente código morto.

 o gráfico de fluxo de controlo acima mostra um pedaço de programa onde a variável ” A “é usada para atribuir a saída da expressão “x * y”. Vamos assumir que o valor atribuído a ‘a’ nunca é usado dentro do laço.Imediatamente após o controle deixar o loop, ‘A’ é atribuído o valor da variável ‘z’, que seria usado mais tarde no programa. Concluímos aqui que o código de atribuição de ” a ” nunca é usado em nenhum lugar, portanto, é elegível para ser eliminado.

 da mesma forma, a imagem acima mostra que a afirmação condicional é sempre falsa, implicando que o código, escrito em caso verdadeiro, nunca será executado, portanto, pode ser removido.
redundância parcial 
 expressões redundantes são computadas mais de uma vez em caminho paralelo, sem qualquer alteração em operandos.enquanto expressões parciais redundantes são computadas mais de uma vez em um caminho, sem qualquer alteração em operandos. Por exemplo,

Loop-invariantes código é parcialmente redundante e pode ser eliminada com a utilização de um código de movimento técnica.
outro exemplo de um 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 da atribuição da variável A para a variável C. aqui, se a condição é verdadeira, então y OP z é calculado duas vezes, caso contrário uma vez.  O movimento do código pode ser usado para eliminar esta redundância, como 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.


Anúncios