Introdução à Teoria dos Compiladores/Geração e Otimização de Código

Geração de Código

A tradução do código de alto nível para o código do processador está associada a traduzir para a linguagem-alvo a representação da árvore gramatical obtida para as diversas expressões do programa. Embora tal atividade possa ser realizada para a árvore completa após a conclusão da análise sintática, em geral ela é efetivada através das ações semânticas associadas à aplicação das regras de reconhecimento do analisador sintático. Este procedimento é denominado tradução dirigida pela sintaxe.

Em geral, a geração de código não se dá diretamente para a linguagem assembly do processador-alvo. Por conveniência, o analisador sintático gera código para uma máquina abstrata, com uma linguagem próxima ao assembly, porém independente de processadores específicos. Em uma segunda etapa da geração de código, esse código intermediário é traduzido para a linguagem assembly desejada. Dessa forma, grande parte do compilador é reaproveitada para trabalhar com diferentes tipos de processadores.

Várias técnicas e várias tarefas se reúnem sob o nome de Otimização. Alguns autores da literatura consideram que, para qualquer critério de qualidade razoável, é impossível construir um programa “otimizador”, isto é, um programa que recebe como entrada um programa P e constrói um programa P’ equivalente que é o melhor possível, segundo o critério considerado. O que se pode construir são programas que melhoram outros programas, de maneira que o programa P’ é, na maioria das vezes, melhor, segundo o critério especificado do que o programa P original. A razão para essa impossibilidade é a mesma que se encontra quando se estuda, por exemplo em LFA (Linguagens Formais e Autômatos), o “problema da parada”: um programa (procedimento, máquina de Turing, etc.) não pode obter informação suficiente sobre todas as possíveis formas de execução de outro programa (procedimento, máquina de Turing, etc.).

Normalmente, é muito fácil fazer uma otimização em um programa, ou seja, uma transformação que o transforma em outro melhor. O difícil é sempre obter a informação necessária que garante que a otimização pode realmente ser aplicada, sem modificar em nenhum caso o funcionamento do programa.

Não é prático tentar otimizar um programa tentando sucessivamente eliminar todos os seus comandos, um de cada vez. Note que as condições para cada eliminação dependem do comando, de sua posição, e, de certa maneira, de todos os comandos restantes do programa. Para construir um otimizador de utilidade na prática, faz-se necessário identificar oportunidades para otimização que sejam produtivas em situações correntes.

Outro exemplo de otimização que é citado freqüentemente é a retirada de comandos de um comando de repetição (um loop). Por exemplo, um comando cujo efeito é independente do loop, pode valer a pena retirá-lo do loop, para que ele seja executado apenas uma vez, em vez das muitas vezes que se presume que será executado o código de dentro do loop.

Depende muito da finalidade de um compilador o conjunto de otimizações que ele deve oferecer. Um compilador usado em um curso introdutório de programação não precisa de otimização, porque os programas são executados quase sempre apenas uma vez. (Em vez de otimização, este compilador deveria dar boas mensagens de erro, que pudessem auxiliar os principiantes na linguagem.) Por outro lado, um programa que vai ser compilado uma vez e executado muitas vezes deve ser otimizado tanto quanto possível. Neste caso estão programas de simulação, de previsão do tempo, e a maioria das aplicações numéricas.

Um outro problema na otimização de código para um compilador é a quantidade de informação que se deseja manipular. Pode-se examinar otimizações locais (em trechos pequenos de programas, por exemplo trechos sem desvios, ou seja, trechos em linha reta), otimizações em um nível intermediário (as otimizações são consideradas apenas em funções, módulos, ou classes, dependendo da linguagem) e otimizações globais (que consideram as inter-relações de todas as partes de um programa). A maioria dos compiladores oferece algumas otimizações do primeiro tipo, possivelmente combinadas com a fase de geração de código, e quando muito algumas otimizações de nível intermediário.

A maneira de tratar a otimização pode ser extremamente pragmática. Em um programa grande, a execução gasta 90% em 10% do código, e 10% do tempo nos 90% do código restantes (A literatura menciona valores de 90%-10% até 70%-30%.). Isto acontece porque em geral um programa é constituído de inicializações e finalizações, entre as quais se encontra um conjunto de vários loops aninhados. O tempo maior de execução (“os 90%”) é gasto no loop mais interno (“os 10%”). Existem ferramentas que registram o perfil de execução do programa (profilers), permitindo a identificação dos trechos mais executados, e a otimização pode se concentrar nestes trechos, ignorando para fins de otimização o restante do programa. Por essa razão muitos compiladores oferecem opções de compilação que podem ser ligadas e desligadas no código fonte, indicando para o compilador os trechos que o programador considera importantes o suficiente para serem otimizados. Por estas razões, muito do trabalho no desenvolvimento de técnicas de otimização é dedicado aos loops.

Código intermediário

A linguagem utilizada para a geração de um código em formato intermediário entre a linguagem de alto nível e a linguagem assembly deve representar, de forma independente do processador para o qual o programa será gerado, todas as expressões do programa original. Duas formas usuais para esse tipo de representação são a notação posfixa e o código de três endereços.

Código de três endereços

O código de três endereços é composto por uma seqüência de instruções envolvendo operações binárias ou unárias e uma atribuição. O nome "três endereços está associado à especificação, em uma instrução, de no máximo três variáveis: duas para os operadores binários e uma para o resultado. Assim, expressões envolvendo diversas operações são decompostas nesse código em uma série de instruções, eventualmente com a utilização de variáveis temporárias introduzidas na tradução. Dessa forma, obtém-se um código mais próximo da estrutura da linguagem assembly e, conseqüentemente, de mais fácil conversão para a linguagem-alvo.

Uma possível especificação de uma linguagem de três endereços envolve quatro tipos básicos de instruções: expressões com atribuição, desvios, invocação de rotinas e acesso indexado e indireto.

Instruções de atribuição são aquelas nas quais o resultado de uma operação é armazenado na variável especificada à esquerda do operador de atribuição, aqui denotado por :=. Há três formas para esse tipo de instrução. Na primeira, a variável recebe o resultado de uma operação binária:

    x := y op z

O resultado pode ser também obtido a partir da aplicação de um operador unário:

    x := op y

Na terceira forma, pode ocorrer uma simples cópia de valores de uma variável para outra:

    x := y

Por exemplo, a expressão em C

a = b + c * d;

seria traduzida nesse formato para as instruções:

    _t1 := c * d
      a := b + _t1

As instruções de desvio podem assumir duas formas básicas. Uma instrução de desvio incondicional tem o formato

    goto L

onde L é um rótulo simbólico que identifica uma linha do código. A outra forma de desvio é o desvio condicional, com o formato

    if x opr y goto L

onde opr é um operador relacional de comparação e L é o rótulo da linha que deve ser executada se o resultado da aplicação do operador relacional for verdadeiro; caso contrário, a linha seguinte é executada.

Por exemplo, a seguinte iteração em C

while (i++ <= k) 
  x[i] = 0;
x[0] = 0;

poderia ser traduzida para

_L1: if i > k goto _L2

    i := i + 1
    x[i] := 0 
    goto _L1

_L2: x[0] := 0

A invocação de rotinas ocorre em duas etapas. Inicialmente, os argumentos do procedimento são "registrados com a instrução param; após a definição dos argumentos, a instrução call completa a invocação da rotina. A instrução return indica o fim de execução de uma rotina. Opcionalmente, esta instrução pode especificar um valor de retorno, que pode ser atribuído na linguagem intermediária a uma variável como resultado de call.

Por exemplo, considere a chamada de uma função f que recebe três argumentos e retorna um valor:

f(a, b, c);

Neste exemplo em C, esse valor de retorno não é utilizado. De qualquer modo, a expressão acima seria traduzida para

    param a
    param b
    param c
    _t1 := call f,3

onde o número após a vírgula indica o número de argumentos utilizados pelo procedimento f. Com o uso desse argumento adicional é possível expressar sem dificuldades as chamadas aninhadas de procedimentos.

O último tipo de instrução para códigos de três endereços refere-se aos modos de endereçamento indexado e indireto. Para atribuições indexadas, as duas formas básicas são

    x := y[i]
    x[i] := y

As atribuições associadas ao modo indireto permitem a manipulação de endereços e seus conteúdos. As instruções em formato intermediário também utilizam um formato próximo àquele da linguagem C:

    x := &y
    w := *x
    *x := z

A representação interna das instruções em códigos de três endereços dá-se na forma de armazenamento em tabelas com quatro ou três colunas. Na abordagem que utiliza quádruplas (as tabelas com quatro colunas), cada instrução é representada por uma linha na tabela com a especificação do operador, do primeiro argumento, do segundo argumento e do resultado

Para algumas instruções, como aquelas envolvendo operadores unários ou desvio incondicional, algumas das colunas estariam vazias.

Na outra forma de representação, por triplas, evita a necessidade de manter nomes de variáveis temporárias ao fazer referência às linhas da própria tabela no lugar dos argumentos. Nesse caso, apenas três colunas são necessárias, uma vez que o resultado está sempre implicitamente associado à linha da tabela.

Notação posfixa

A notação tradicional para expressões aritméticas, que representa uma operação binária na forma x+y, ou seja, com o operador entre seus dois operandos, é conhecida como notação infixa. Uma notação alternativa para esse tipo de expressão é a notação posfixa, também conhecida como notação polonesa, na qual o operador é expresso após seus operandos.

O atrativo da notação posfixa é que ela dispensa o uso de parênteses. Por exemplo, as expressões

 a*b+c;
 a*(b+c);
 (a+b)*c;
 (a+b)*(c+d);

seriam representadas nesse tipo de notação respectivamente como

 a b * c +
 a b c + *
 a b + c *
 a b + c d + *

Instruções de desvio em código intermediário usando a notação posfixa assumem a forma

  L jump
  x y L jcc

para desvios incondicionais e condicionais, respectivamente. No caso de um desvio condicional, a condição a ser avaliada envolvendo x e y é expressa na parte cc da própria instrução. Assim, jcc pode ser uma instrução entre jeq (desvio ocorre se x e y forem iguais), jne (se diferentes), jlt (se x menor que y), jle (se x menor ou igual a y), jgt (se x maior que y) ou jge (se x maior ou igual a y).

Expressões em formato intermediário usando a notação posfixa podem ser eficientemente avaliadas em máquinas baseadas em pilhas, também conhecidas como máquinas de zero endereços. Nesse tipo de máquinas, operandos são explicitamente introduzidos e retirados do topo da pilha por instruções push e pop, respectivamente. Além disso, a aplicação de um operador retira do topo da pilha seus operandos e retorna ao topo da pilha o resultado de sua aplicação.

Por exemplo, a avaliação da expressão a*(b+c) em uma máquina baseada em pilha poderia ser traduzida para o código

  push a
  push b
  push c
  add
  mult

Otimização de código

A etapa final na geração de código pelo compilador é a fase de otimização. Como o código gerado através da tradução orientada pela sintaxe contempla expressões independentes, diversas situações contendo seqüências de código ineficiente podem ocorrer. O objeto da etapa de otimização de código é aplicar um conjunto de heurísticas para detectar tais seqüências e substituí-las por outras que removam as situações de ineficiência.

As técnicas de otimização que são usadas em compiladores devem, além de manter o significado do programa original, ser capazes de capturar a maior parte das possibilidades de melhoria do código dentro de limites razoáveis de esforço gasto para tal fim. Em geral, os compiladores usualmente permitem especificar qual o grau de esforço desejado no processo de otimização. Por exemplo, em gcc há opções na forma -O... que dão essa indicação, desde O0 (nenhuma otimização) até -O3 (máxima otimização, aumentando o tempo de compilação), incluindo também uma opção -Os, indicando que o objetivo é reduzir a ocupação de espaço em memória.

Algumas heurísticas de otimização são sempre aplicadas pelos compiladores. Por exemplo, se a concatenação de código gerado por duas expressões no programa original gerou uma situação de desvio incondicional para a linha seguinte, como em

    (a)
    goto _L1

_L1: (b)

esse código pode ser seguramente reduzido com a aplicação da técnica de eliminação de desvios desnecessários, resultando em

    (a)

_L1: (b)

Outra estratégia de otimização elimina os rótulos não referenciados por outras instruções do programa. Assim, se o rótulo _L1 estivesse sendo referenciado exclusivamente por essa instrução de desvio, ele poderia ser eliminado em uma próxima aplicação das estratégias de otimização.

As técnicas de otimização podem ser classificadas como independentes de máquina, quando podem ser aplicadas antes da geração do código na linguagem assembly, ou dependentes de máquina, quando aplicadas na geração do código assembly.

A otimização independente de máquina tem como requisito o levantamento dos blocos de comandos que compõem o programa. Essa etapa da otimização é conhecida como a análise de fluxo, que por sua vez contempla a análise de fluxo de controle e a análise de fluxo de dados. Estratégias que podem ser aplicadas, analisando um único bloco de comandos são denominadas estratégias de otimização local, enquanto aquelas que envolvem a análise simultânea de dois ou mais blocos são denominadas estratégias de otimização global.

Algumas estratégias básicas de otimização, além da já apresentada eliminação de desvios desnecessários, são apresentadas a seguir.

A estratégia de eliminação de código redundante busca detectar situações onde a tradução de duas expressões gera instruções cuja execução repetida não tem efeito. Por exemplo, em

    x := y
      ...
    x := y

se não há nenhuma mudança no valor de y entre as duas instruções, então a segunda instrução poderia ser eliminada. O mesmo aconteceria se a segunda instrução fosse

    y := x

e o valor de x não fosse alterado entre as duas instruções.

Outra estratégia básica é a eliminação de código não-alcançável, ou “código morto”. Por exemplo, se a seguinte seqüência de código fosse gerada por um conjunto de expressões

      ...
    goto _L1
    x := y

_L1: ...

a instrução contendo a atribuição de y a x nunca poderia ser executada, pois é precedida de um desvio incondicional e não é o destino de nenhum desvio, pois não contém um rótulo na linha. Assim, essa linha poderia ser eliminada e provocar posteriormente a aplicação da estratégia de eliminação de desvios desnecessários.

O uso de propriedades algébricas é outra estratégia de otimização usualmente aplicada. Nesse caso, quando o compilador identifica que uma expressão aritmética foi reduzida a x=0 ou 0=x ou x-0 ou x*1 ou 1*x ou x/1, então ele substitui a expressão simplesmente por x. Outra classe de propriedades algébricas que é utilizada tem por objetivo substituir operações de alto custo de execução por operações mais simples, como

2.0*x = x+x x2 = x*x x/2 = 0.5*x

Particularmente no último caso, se x for uma variável inteira a divisão por dois pode ser substituída por um deslocamento da representação binária à direita de um bit. Genericamente, a divisão inteira por 2n equivale ao deslocamento à direita de n bits na representação binária do dividendo. Da mesma forma, a multiplicação inteira por potências de dois pode ser substituída por deslocamento de bits à esquerda.

A utilização de propriedades algébricas permite também o reuso de subexpressões já computadas. Por exemplo, a tradução direta das expressões

  a = b + c;
  e = c + d + b;

geraria o seguinte código intermediário:

    a := b + c
  _t1 := c + d
    e := _t1 + b

No entanto, o uso da comutatividade e associatividade da adição permite que o código gerado seja reduzido usando a eliminação de expressões comuns, resultando em

    a := b + c
    e := a + d

Diversas oportunidades de otimização estão associadas à análise de comandos iterativos. Uma estratégia é a movimentação de código, aplicado quando um cálculo realizado dentro do laço na verdade envolve valores invariantes na iteração. Por exemplo, o comando

  while (i < 10*j) {
    a[i] = i + 2*j;
    ++i;
  }

estaria gerando um código intermediário equivalente a

_L1:  _t1 := 10 * j
      if i >= _t1 goto _L2
      _t2 := 2 * j
      a[i] := i + _t2
      i := i + 1
      goto _L1
_L2:   ...

No entanto, a análise de fluxo de dados mostra que o valor de j não varia entre iterações. Assim, o compilador poderia mover as expressões que envolvem exclusivamente constantes na iteração para fora do laço, substituindo esse código por

_t1 := 10 * j

      _t2 := 2 * j
_L1:  if i >= _t1 goto _L2
      a[i] := i + _t2
      i := i + 1
      goto _L1
_L2:   ...

Um exemplo de otimização dependente de máquina pode ser apresentado para a expressão

    x := y + K

onde K é alguma constante inteira. Na tradução para o código assembly de um processador da família 68K, a forma genérica poderia ser algo como

     MOVE.L  y,D0
     ADDI.L #K,D0
     MOVE.L D0,x

No entanto, se o compilador verificasse que o valor de K fosse uma constante entre 1 e 8, então a segunda instrução assembly poderia ser substituída por ADDQ.L, que utilizaria em sua codificação apenas dois bytes ao invés dos seis bytes que seriam requeridos pela instrução ADDI.L.

Esta página é somente um esboço. Ampliando-a você ajudará a melhorar a Wikiversidade.