Construção de compiladores/Geração de código intermediário

Tomando um compilador como um modelo de análise-e-síntese, podemos considerar que seus módulos iniciais ("front-end modules") traduzem um programa fonte em uma representação (linguagem) intermediária, a partir da qual seus módulos finais ("back-end modules") geram o código objeto final.

A geração de um código intermediário requer um passo a mais para a tradução, tornando o processo um pouco mais lento. Embora um programa fonte possa ser traduzido diretamente para a linguagem objeto, o uso de uma representação intermediária, independente de máquina, tem as seguintes vantagens:

1. Reaproveitamento de código, facilitando o transporte de um compilador para diversas plataformas de hardware; somente os módulos finais precisam ser refeitos a cada transporte.
2. Um otimizador de código independente de máquina pode ser usado no código intermediário.

Pode-se pensar nessa representação intermediária como um programa para uma máquina abstrata. A representação intermediária deve possuir duas propriedades importantes: ser fácil de produzir e fácil de traduzir no programa alvo.

A diferença básica entre o código intermediário e o código objeto final é que não são especificados detalhes da máquina alvo, tais como quais registradores serão usados, quais endereços de memória serão referenciados, etc.

Tipos de código intermediário

• HIR – High Intermediate Representation
  • Usada nos primeiros estágios do compilador
  • Simplificação de construções gramaticais para somente o essencial para otimização/geração de código

• MIR – Medium Intermediate Representation
  • Boa base para geração de código eficiente
  • Pode expressar todas características de linguagens de programação de forma independente da linguagem
  • Representação de variáveis, temporários, registradores

• LIR – Low Intermediate Representation
  • Quase 1-1 para linguagem de máquina
  • Dependente da arquitetura

Representação

As formas de representação mais comuns dos tipos de códigos intermediários são:

• HIR
  • Árvore e grafo de sintaxe
  • Notações Pós-fixada e Pré-fixada
  • Representações linearizadas

• MIR
  • Árvore e grafo de sintaxe
  • Notações Pós-fixada e Pré-fixada:
  • Representações linearizadas
  • Código de três endereços:
    • Quádruplas
    • Triplas
    • Grafos acíclicos dirigidos (DAG)

• LIR
  • Instruções assembler

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