Geração de Código em Compiladores

Prévia do material em texto

Editado por Aleardo Manacero Jr.
Capítulo 5 - Geração de código
1. Implicações do hardware 
2. Geração de código, como faze-la 
3. Tratamento das variáveis 
4. Tratamento de precedências e associatividade 
5. Tratamento de estruturas de programação 
6. Tratamento de subrotinas 
7. Geração de código através da gramática de atributos 
Após termos examinado os módulos que compõe o front-end de um compilador podemos passar ao estudo de como é gerado o código
executável a partir do resultado obtido nos módulos de entrada. O back-end do compilador pode envolver mais do que uma etapa,
sendo que necessariamente temos uma etapa de geração do código, que pode ou não ser acompanhada por etapas de otimização do
código. 
Neste capítulo nos ocuparemos da geração do código, que obviamente vai depender do hardware em que se vá aplicar o programa
executável gerado. Entretanto, esta dependência do hardware acaba por não ser sentida quando se discute os aspectos essenciais do
processo de geração de código. 
A seguir faremos uma breve descrição das diferenças de hardware que devem ser levadas em conta na implementação do gerador de
código, para então passarmos ao estudo dos problemas envolvidos na geração de código, independente da máquina em que se
executará a compilação. 
5.1 Implicações do hardware
Como o hardware tem uma evolução constante, temos a existência de conjuntos de instruções diferentes para cada tipo de máquina.
Assim, no momento de gerar código o compilador tem que ter conhecimento da máquina para a qual ele se destina, isto é, cada
máquina alvo vai ter um conjunto diferente de instruções para executar uma determinada tarefa. 
Com isso surgem dois problemas. O primeiro está relacionado com o fato de que nem sempre uma máquina possui a instrução desejada
para uma determinada função. Assim, temos que executar esta função através de um conjunto de várias instruções. Deste fato nasce
nosso segundo problema, pois pode-se ter vários conjuntos diferentes de instruções que executem a mesma tarefa, o que nos coloca na
posição de termos que escolher entre estes conjuntos por aquele que execute esta funcionalidade com a maior eficiência. Isto implica
num primeiro nível de otimização, que seria feito ainda antes de se compilar qualquer coisa. 
Uma outra diferença associada aos aspectos acima é que cada CPU vai apresentar, em geral, conjuntos diferentes de registradores, isto
é, teremos diferentes manipulações entre memória e registradores segundo a disponibilidade dos mesmos na CPU em uso. Otimizar o
número de acessos à memória fica sendo então um novo aspecto a ser considerado, muito embora isto possa ser feito em tempo-real
durante a compilação. 
O problema maior entretanto é quanto a forma em que são feitos os acessos (endereçamentos) aos dados usados no programa.
Dependendo do número e do tipo de acesso feito, temos máquinas que precisam de maior ou menor número de bits para representar
uma mesma instrução, o que vai dificultar ou facilitar a geração do código. 
A primeira destas máquinas é a que endereça duas posições na memória, conhecida como máquina de 2-endereços. Neste caso, em
cada instrução temos que ter presentes o código da instrução (indicando o que vai ser feito) e um par de endereços na memória. A
desvantagem clara desta abordagem é que o tamanho da instrução amarra o número máximo de posições endereçaveis na memória. 
Uma primeira evolução foi através da substituição de um dos endereços em memória por um registrador interno da CPU. Assim,
apesar de ainda termos que acessar dois endereços, tinhamos que um deles poderia ser identificado com um número menor de bits e
acessado num tempo menor, agilizando o processo e possibilitando um aumento no número de posições endereçaveis para um mesmo
tamanho de instrução. 
Substituindo-se agora o registrador pelo próprio acumulador da CPU vamos conseguir uma máquina com apenas um endereço. Assim,
cada instrução passa a ter apenas dois campos, um contendo seu código e outro contendo o único endereço a ser acessado na memória.
Isto leva a uma máquina mais eficiente em termos de velocidade e tamanho de memória. 
Outras melhorias foram obtidas permitindo-se uma maior variação no que poderia ser endereçado. Assim, em máquinas mais recentes
temos instruções acessando pares de registradores, ou mesmo posições de memória através de endereçamento indireto via
registradores. Por último, uma vez que uma máquina de 1-endereço funciona melhor do que uma de 2-endereços, por que não tentar
trabalhar totalmente sem endereços, isto é, criar uma máquina com instruções de 0-endereços. 
Isso é feito através do uso de uma pilha, cujo topo seria então automaticamente apontado por algum registrador pré-definido dentro da
CPU. Então, cada instrução teria apenas um campo, que seria o seu código. Os operandos a serem usados pela instrução seriam
encontrados na pilha, cuja operação seria idêntica a de um autômato a pilha. 
A vantagem no uso de tal máquina é que quando fazemos a análise sintática bottom-up acabamos por gerar estruturas de operação
semelhantes a notação reversa-polonesa, criada por Lukasiewicz, que pode ser aplicada de forma direta ao modo de operação da pilha
numa máquina de 0-endereços. É desnecessário perdermos tempo aqui para ilustrar como o método de Lukasiewicz pode ser executado
através da operação sobre pilhas. 
Nas figuras a seguir temos uma descrição visual de como essas diferentes máquinas fazem acesso aos dados na memória do
computador: 
 Figura 5.1 - Acesso
aos dados pelos vários tipos de máquinas.
5.1.1 - A máquina de 0-endereços:
Para o restante deste capítulo estaremos trabalhando com o conjunto de instruções apresentado a seguir, que representa de forma geral
uma máquina de 0-endereços. 
CÓDIGO MNEMÔNICO FUNÇÃO 
30 Zero push the constant zero
28 LoadCon
<value>
push <value>
27 Load pop address; push memory(address)
26 Store pop value; pop address; store value in memory
(address)
11 Multiply pop A; pop B; push B*A
12 Add pop A; pop B; push B+A
14 Or pop A; pop B; push (B or A)
15 And pop A; pop B; push (B ad A)
16 Equal pop A; pop B; push 1 if (B=A); push 0 otherwise
17 Less pop A; pop B; push 1 if (B<A); push 0 otherwise
18 Greater pop A; pop B; push 1 if (B>A); push 0 otherwise
20 Negate pop A; push -A
1 BranchFalse pop offset; pop value; if value = 0 then add offsetto
PC
3 Call pop address; push return address; go to subroutine
4 Enter pop number; allocate space for that many variables
5 Exit to caller pop number; deallocate that many parameters
andreturn
8 Dupe push a copy of the stack top
9 Swap pop two values; push them back in the reverse order
24 Stop stop run 
25 Global subtract frame pointer from top of stack
Tabela 5.1 - Códigos de instruções do processador de 0-endereços
5.2 - Geração de código, como fazê-la.
O que se faz para gerar código é criar regras para a aplicação de conjuntos de instruções que cumpram funcionalidades declaradas nas
instruções do código fonte. Isto é conhecido como geração dirigida sintaticamente, uma vez que usamos a própria árvore de derivação
sintática para definir qual será a sequência de operações desejada. A seguir temos alguns exemplos de como fazer isso. 
Exemplo 1: Obter o resultado para 3*4+5*2: 
A introdução dos valores na pilha deve ser feita através da instrução LoadCon, onde <value> será o valor imediato das constantes da
expressão. Além disso temos que executar duas multiplicações e uma soma, através dos comandos Multiply e Add respectivamente.
Entretanto, temos ainda que alterar a expressão dada para a notação posfixa, que é a que se adequa ao uso da pilha e a estrutura do
analisador sintático. Assim, temos: 
 3*4+5*2 --> 3 4 * 5 2 * + 
Código: 
Instrução Conteúdo da pilha (topo a esquerda)
LoadCon 3 3
LoadCon 4 4 3
Multiply 12
LoadCon 5 5 12
LoadCon 2 2 5 12
Multiply 10 12
Add 22
Exemplo 2: Uso de variáveis. 
Apesar de que o conjuntode operações dado acima funciona bastante bem, temos que na maioria das vezes os operandos são variáveis,
cujos valores reais devem ser buscados na memória. Para fazer isso lançamos mão das instruções Load e Store, que trabalham sobre
endereços indexados através da pilha. Por exemplo, se quizermos fazer a atribuição a = b temos que fazer: 
 
Instrução Conteúdo da pilha (topo a esquerda)
LoadCon <value> endereço da variável a
LoadCon <value> endereço de b; endereço de a
Load valor de b; endereço de a
Store (vazia)
Exemplo 3: Uso de endereços e códigos. 
A partir do conjunto de instruções da seção 5.1.1 pode-se observar que a cada instrução temos associado um mnemônico (que é o que
temos usado até aqui) e um código. Na realidade, o computador entende apenas o código, logo o mesmo é que vai estar presente após a
geração do executável. 
Por outro lado, o exemplo anterior introduziu o problema de como localizar endereços das variáveis presentes em cada instrução. Este
problema é resolvido mais adiante, através da tabela de símbolos, assim nos concentraremos neste exemplo a mostrar como poderia
seria o código sem o uso dos mnemônicos. Para tanto considere a resolução da atribuição a = a-1 
 
28 a % armazena a posição de a na memóriapara o retorno de seu valor
final
28 a % armazena a posição de a na memóriapara obter seu valor inicial
27 % obtém o valor de a
28 1 % coloca 1 na pilha
20 % nega o valor no topo da pilha (obtém -1)
12 % soma a + (-1)
26 % armazena o novo valor de a
Destes exemplos já podemos vislumbrar algumas rotinas a serem seguidas sempre. Uma delas é o fato de que se existir uma atribuição,
temos que construir um preâmbulo em que será armazenado na pilha o endereço de retorno e um desfecho, fazendo de fato esta
operação, deixando então a pilha vazia. A expressão cujo resultado vai ser atribuído fica então entre estas duas instruções. 
Além disso, como não existe a operação de subtração, sempre que quizermos executá-la teremos que executar a operação de Negate
sobre o subtrator, para então somá-lo ao subtraendo. Da mesma forma, a operação de divisão não pode ser executada com apenas uma
única instrução, aliás, neste caso nem podemos fazê-la com poucas instruções, pois o único método disponível passa a ser o das
subtrações sucessivas. 
5.3 - Tratamento das variáveis
Como já apontamos na seção anterior, temos que cada variável na memória tem o seu endereço tratado através da tabela de símbolos.
Porém, deixamos de indicar como isso seria feito. Aqui passamos a descrever a forma na qual trataremos os endereços de uma variável
durante a compilação. 
O primeiro passo é alterar a tabela de símbolos para acrescentar nela a informação sobre o endereço em que uma determinada variável
(que é representada por um símbolo) vai ser armazenada na memória. Este endereço ainda vai ser lógico, uma vez que endereços
físicos só surgem quando o programa está carregado na memória. 
Passa a ser necessário então um mecanismo que controle quais posições da memória estão livres para uso pelas variáveis. Isto pode ser
feito simplesmente através de um apontador para uma região da memória em que estarão armazenadas as variáveis. 
Assim, cada vez que fosse inserido um novo símbolo na tabela de símbolos, reservariamos o número de posições de memória
necessários para armazenar o conteúdo de tal símbolo (recebendo esta informação através da análise semântica), e retornariamos ao
scanner o endereço base das posições alocadas, que seria então armazenado na tabela de símbolos. 
5.4 - Tratamento de precedências e associatividade
Como a entrada para o gerador de código não contém sinais que regulem a precedência ou associatividade dos operandos, temos que
saber se a construção das operações vai ou não ser feita na ordem desejada. Nos dois casos temos que o tratamento é feito durante a
análise sintática, ou mais precisamente, na geração da árvore de derivação para o programa em compilação. 
Temos que quanto mais baixo na árvore estiver uma operação, maior será a sua precedência no momento de execução, isto devido a
própria estruturação da gramática, em que fazemos com que a partir das produções em que apareçam os símbolos terminais que
representem operandos, passamos primeiro pelas produções sobre operações de maior precedência. Assim, no momento da criação da
árvore de derivação teremos automaticamente as operações de maior precedência próximas das folhas da árvore. 
Já o problema da associatividade, que surge em operações do tipo 5-2-7 que tem resultados diferentes se executamos primeiro 5-2 ou
primeiro 2-7, temos também uma solução relativamente trivial através da construção cuidadosa da gramática, quando teriamos que
deixar definida qual seria a ordem para a associação de operandos. Por exemplo, as duas gramáticas a seguir representam a mesma
linguagem, porém temos que a primeira é associativa a esquerda enquanto a última é associativa a direita. 
Obs: O símbolo [+] indica o momento em que o predicado tem seu valor calculado 
 
G1 G4 
E -> E + T [+] E -> T + E [+]
E -> T E -> T 
T -> a [+] E -> a [+]
A diferença entre as duas pode ser sentida na construção da árvore de derivação. Por exemplo, a Figura 5.2 apresenta as árvores para a
expressão a+a+a. 
 
Figura 5.2 - Árvores de derivação para G1 e G2
Logo vemos que ordem em que serão executadas as somas depende de como a gramática foi arranjada. 
5.5 Tratamento de estruturas de programação
Até o momento nos preocupamos apenas com a geração de código estritamente linear, isto é, código em que a instrução i é seguida
imediatamente pela instrução i=1, sem desvios, condicionais ou não. Entretanto sabemos que grande parte do tempo de um programa é
gasto em estruturas da linguagem, tais como if-then-else, while, do-repeat, etc.. 
Nestes casos temos que prover ao gerador de código mecanismos para o tratamento de tais eventos. O mais básico deles é prover uma
instrução que lhe permita testar o valor de uma condição qualquer. O outro mecanismo, em geral associado a este, é o de prover uma
instrução que faça um salto condicional de uma posição da memória para outra, deixando então de executar o conjunto de instruções
que seguia linearmente a instrução atual. 
Na máquina definida em 5.1.1 temos que estas instruções são Equal, Less, Greater e BranchFalse. O funcionamento destas
instruções e o seu uso para a geração de códigos também é bastante simples, exceto quanto ao aspecto da determinação dos endereços
para desvio. 
O problema do desvio surge quando tentamos determinar o endereço para o qual estamos saltando. Este endereço é determinado (em
nossa máquina) através do valor de offset usado na instrução BranchFalse. Acontece que na maior parte das vezes o endereço destino
está localizado numa posição mais adiante da posição atual. Como o compilador ainda não passou por esta posição (e não temos como
determinar o número exato de instruções contidas entre a origem e o destino deste salto), ficamos sem saber que valor adotar para
offset. 
Para solucionar o problema do salto a frente temos duas abordagens. A primeira delas percorre o texto todo duas vezes, sendo que na
segunda passagem é que serão determinados os valores de offset para todos os pontos em que isto for necessário. Já a segunda
abordagem percorre o texto apenas uma vez, mas mantém um mapa dos endereços ainda não determinados, que é atualizado
continuamente, voltando-se atrás no programa e acertando-se os offsets cada vez que um endereço puder ser determinado. 
A primeira técnica tem a vantagem de ser mais simples, muito embora acabe tornando a compilação mais lenta pelo passo extra na
obtenção de endereços. Além disso, em linguagens em que não seja necessário fazer pré-declaração de variáveis, temos que o
compilador de dois passos é necessário por permitir a realização da análise semântica apenas no segundo passo, quando
obrigatoriamente todas as variáveis e endereços destino já estariam com seus valores definidos. 
A segunda técnica tenta corrigir o problema de tempo a mais gasto coma segunda passagem pelo código. Entretanto a necessidade da
execução do backpatching (volta atrás para corrigir os valores de offset que estavam indicados nas operações de salto) faz com que o
sistema se torne um pouco mais complexo do que o compilador de dois passos. Este método é preferível se a linguagem for estruturada
e não permitir a declaração de variáveis posterior ao uso, tais como pascal e/ou C. 
De qualquer forma, o problema de determinar endereços que estão adiante no fluxo linear de instruções é o maior complicador no
momento de se gerar código que represente estruturas que tenham saltos e ou ciclos de repetição. 
5.6 Tratamento de subrotinas
Não existe muita diferença entre o tratamento de uma subrotina daquele dado a uma estrutura condicional. Na realidade, podemos
considerar uma chamada de subrotina como sendo um desvio incondicional a uma região mais distante do código, da qual haverá num
determinado momento o retôrno para a posição seguinte à posição de onde ocorreu o desvio. 
Isto implica na necessidade do uso de uma instrução que permita o armazenamento na pilha de um endereço de retôrno, o que é feito
pela instrução Call na nossa máquina em particular. Com este tipo de instrução, durante o desvio temos que armazenar na pilha o
endereço de retorno, o que nos permite então chamar a subrotina de qualquer ponto do programa, podendo retornar ao ponto de
chamada sem maiores problemas. 
OBS-- A seção abaixo é apenas para referência futura 
5.7 Geração de código através da gramática de atributos
Podemos automatizar o processo de geração de código usando para isso a estrutura de gramática de atributos, introduzida no capítulo
anterior. O processo é bastante simples, pois basta criar um novo símbolo não-terminal Z, representando o endereço de uma instrução,
que vai ser anexado às demais produções da gramática, de forma a poder transferir o atributo endereço (sintetizado a partir de uma
função predicado associada à produção Z -> \lambda). 
Como Z apenas vai aparecer do lado esquerdo na produção dada acima, temos que a gramática não é alterada. Em compensação
ganhamos a possibilidade de sintetizar os endereços de forma automática na gramática, o que nos permite também a geração de código
de forma automática, sem tediosa manipulação de código manualmente.