Compiladores
Geração de Código Intermédio
versão α − 0.002
Simão Melo de Sousa
Este documento é a adaptação duma tradução do capı́tulo ”Génération de Code Intermédiaire”da sebenta ”Cours de Compilation” de Christine Paulin-Morhing
(http://www.lri.fr/~paulin).
1
Introdução
Antes de gerar um código/programa particular, é necessário apresentar os problemas que
se colocam ao organizar os dados e as instruções dentro dum programa.
1.1
Modelos de execução
Aquando da execução de código, uma parte da memória é reservada para as instruções
do programa com um apontador para indicar em que ponto (do programa) se encontra
a execução. O tamanho do código é conhecido na altura da compilação. Supõe-se que
existe um controlo sequencial da execução dum programa. Isto é, que todas as instruções
dum programa, excepto instruções de salto, são executadas sequencialmente umas após a
outra. Os dados são guardados na memória ou nos registos da máquina (que executa). A
memória está organizada em palavras. Esta é acedida via um endereço que é representado
por um inteiro.
Os valores simples são guardados numa unidade de memória, os valores complexos ou
compostos (vectores, estruturas) são guardados em células contı́guas da memória ou em
estruturas encadeadas (uma lista poderá ser representada por um elementos associado a
um apontador contendo o endereço memória do próximo elemento).
Os registos permitam o acesso rápido a dados simples. O número de registos depende
da arquitectura alvo e é em geral relativamente pequeno.
1.2
Alocação
Certos dados são explicitamente manipulados pelo programa fontes pelo intermédio de
variáveis. Outro são criados pelo compilador, por exemplo para conservar os valores de
cálculos intermédios ou para guardar ambientes associados a valores funcionais.
Alguns dados tem uma duração de vida conhecida na altura da compilação. É assim
possı́vel, e até desejável, reutilizar o espaço utilizado. A análise da duração de vida
1
de variáveis deve pelo menos ter em conta das regras de alcance (variable scope) da
linguagem fonte. De facto uma variável que deixa de ser visı́vel corresponde em geral a
um espaço memória (um dado) inacessı́vel. Esta análise pode igualmente utilisar técnicas
de análise de fluxo de controlo (control flow analysis) que permitam detectar variáveis
não utilizadas. As variáveis globais do programa compilado podem ser alocadas para
endereços fixos pelo compilador, na condição de conhecer o tamanho de cada uma delas.
A gestão das variáveis locais, dos blocos e dos procedimentos, ou ainda do armazenamento dos valores intermédios prestam-se bem a uma gestão de alocação da memória
baseada em pilhas.
Outros dados, pelo contrário, não tem uma duração de vida conhecida na fase de
compilação. É o caso por exemplo quando se manipula apontadores. Alguns objectos
alocados não corresponderão directamente a um valor, mas serão acessı́veis pelo intermédio do seu endereço, podendo este estar associado a uma variável. Estes dados serão
alocados, em geral, numa outra parte da memória, designada de heap. Para não desperdiçar este espaço, o programador necessitará recorrer a (a) comandos que permitam
uma gestão explı́cita da memória (como libertar espaço) ou (b) um programa de recuperação de memória designado geralmente de GC (para Garbage Collector ).
1.3
Variáveis
Uma variável é um identificador que aparece num programa e que está associada a um
objeto manipulado pelo programa, em geral arquivado na memória.
Distingue-se o valor esquerdo da variável que representa o endereço memória a partir do qual é arquivada o valor do objecto, do valor direito, que representa o valor do
objecto. Algumas linguagens como o ML distiguam explicitamente os dois tipos de objectos. A linguagem PASCAL é a posição sintáctica da variável que determina se deve
ser interpretada como um valor esquerdo ou valor direito. A passagem de parâmetro
nas funções e procedimentos podem ser feitos com base no valor direito ou esquerdo dos
objecto manipulados.
Ambiente e estado. É designado por ambiente a associação de nomes a endereços
memória. Esta ligação pode ser representada por um conjunto finito de pares formados
por um identificador e por um endereço. Um ambiente define uma função parcial que
associa um endereço a um identificador. Designa-se por estado uma função parcial dos
endereços memória para valores.
Quando se atribui um valor a uma variável só o estado se altera. Quando se invoca
uma função ou a um procedimento possuindo parâmetros, o ambiente muda. A variável
introduzida corresponde a uma noção ligação entre um nome e um endereço.
1.4
Semântica
Para construir uma tradução correcta é essencial conhecer as regras de avaliação da
linguagem fonte, ou seja a sua semântica. Estas regras são frequentemente apresentadas
em termos de transformadores de estado e/ou de ambiente.
2
1.5
Procedimentos e funções
Um procedimento tem um nome, parâmetros, contêm declarações de variáveis ou de
procedimentos locais e possui um corpo. Uma função é um procedimento que retorna um
valor.
Os parâmetros formais são variáveis locais ao procedimento que serão instanciados
pelos parâmetros efectivos quando o procedimento for invocado. O procedimento pode
declarar variáveis locais que serão inicializadas no corpo do procedimento. O espaço
memória alocado para os parâmetros pode em geral ser libertado quando a execução sai
do procedimento. No entanto não se pode, em geral, controlar o número de vezes que um
procedimento será invocado nem quando. Por isso não se pode em geral estabelecer estaticamente o endereço das variáveis contidas num procedimento. Estes endereços poderão
ser calculadas relativamente ao estado da pilha de operandas na altura da invocação.
Por exemplo:
program main
var j : int;
procedure p(i,j:int);
{print(i,j);if i+j>0 then j:=j-1; p(i-2,j); print(i,j);p(j,i)}
{read(j); p(j,j); print(j)}
O número de execução de p depende do valor lido em entrada. Em cada entrada no
procedimento p, duas novas variáveis i e j são alocadas. No esquema seguinte representase a execução deste programa tendo em conta a leitura de o valor 1. Os objectos da pilha
são representados após cada instrução que modifica o estado. A pilha cresce aqui de
cima para baixo, os valores correntes de i e j são separados. A execução realiza-se da
esquerda para a direita e de baixo para cima. As pilhas são numeradas seguindo ordem
da execução (ver figura 1).
1.6
Organização do Ambiente
A organização do ambiente de execução depende do que a linguagem autorisa:
• procedimentos recursivos
• processamento de variáveis locais
• referências para nomes locais
• modos de passagem de parâmetros
• existência de dados de tamanhos variáveis
• capacidade em devolver procedimentos ou aceitar procedimentos como parâmetros
• alocação/desalocação dinâmica de dados pelo programador
3
Figura 1: Chamadas a funções e procedimento, um exemplo.
4
2
Tabelas de Activação
Um dos aspectos importantes na organização da memória é a gestão das chamadas aos
procedimentos (ou funções). Estas são efectuadas pelo intermédio duma tabela de activação (frame ou activation records em inglês). Esta tabela é um pedaço de memória
que está atribuida à chamada do procedimento e devolvida à saı́da deste. A tabela contém toda a informação necessária a execução do programa e arquiva todos os dados que
deverão ser restabelecidos a saı́da do procedimento.
Para facilitar a comunicação entre os diferentes tipos de códigos compilados a partir
de linguagens fontes diferentes (por exemplo para poder chamar procedimentos de baixo
nı́vel a partir de linguagens de alto nı́vel), não é raro que seja recomendado a existência
dum formato particular de tabela de activação para uma dada arquitectura.
2.1
Dados por conservar
Quando um procedimento é invocado, o fluxo de controlo do código é modificado. No
caso de o retorno normal do procedimento (a execução do procedimento não provocou
levantamento de excepção, nenhuma instrução de salto (de tipo goto) levou a execução
a sair do procedimento), a execução continua na instrução que segue a chamada ao procedimento. O program counter na altura da chamada deve então ser arquivado de forma
a que a execução possa continuar normalmente após o retorno.
Sabe-se que os dados locais ao procedimento organizam-se na pilha de operandos a
partir de um endereço que é determinada na execução e em geral salvaguardado num
registo. Quando um novo procedimento é chamado, este valor muda. É assim igualmente necessário guardar este valor que poderá ser restaurado ao fim da execução do
procedimento invocado.
2.2
Passagem de parâmetros
Os parâmetros formais dum procedimento são variáveis que são inicializadas aquando da
chamada ao procedimento. Existem várias maneiras de efectuar esta inicialização.
Imaginemos o procedimento p com um parâmetro formal x que é invocado com o
parâmetro efectivo e. Vamos explorar aqui as diferentes formas de efectuar esta passagem.
Passagem por valor: Neste tipo de passagem, x é uma nova variável alocada localmente pelo procedimento cujo valor é o resultado da avaliação de e. Após o fim
do procedimento, as modificações a que x foi submetida deixam de ser visı́veis. Na
ausência de apontadores, as únicas variáveis modificadas são as variáveis não locais
ao procedimento em questão e que constam explicitamente nas instruções deste último. É necessário reservar um espaço proporcional ao tamanho dos parâmetros o
que pode ser custoso no caso dos vectores.
Passagem por referência: Calcula-se o valor esquerdo da expressão e (se e não tem
valor esquerdo, então cria-se uma variável que se inicializa com o valor direito de
e e utiliza-se o valor esquerdo desta variável). O procedimento aloca uma variável
x que é inicializada pelo valor esquerdo de e. Qualquer referência a x no corpo
do procedimento é interpretada como uma operação sobre o objecto situado no
5
endereço guardado em x. Este tipo de passagem ocupa um espaço independente do
tamanho do parâmetro.
Passagem por nome: Trata-se duma substituição textual dentro do corpo do procedimento dos parâmetros formais pelos parâmetros efectivos. Este tipo de passagem,
baseado num mecanismo de macro, pode provocar problemas de captura de variáveis.
Exemplo:
swap(x,y:int)
var z:int
{z:=x; x:=y; y:=z}
Se z e t são variáveis globais do programa, swap(z,t) não tera o comportamento
esperado.
Pode-se renomear as variáveis locais por forma a não interagir com as variáveis que
aparecem nos argumentos. De facto o nome da variável local z, desde que seja
diferente de x e de y, não tem influência sobre o código do procedimento.
Mas isto não chega, por exemplo a passagem por nome de swap(i,a[i]) não retorna o resultado esperado. Este método é no entanto útil para a compilação de
procedimentos de pequeno tamanho onde o custo da gestão de chamadas a procedimentos é importante.
Passagem por Copy-Restore Durante a chamada ao procedimento, o valor direito de
e serve para inicializar a variável x. À saı́da do procedimento, o valor direito de x
serve para a actualização do valor esquerdo de e.
Este método pode ter, em casos particulares, comportamentos diferentes do passagem por referência, como o ilustra o exemplo seguinte:
program main;
var a : integer;
procedure p(x:integer);
{x:=2; a:=0}
{a:=1;p(a);write(a)}
Avaliação pregiçosa (lazy evaluation - call by need ) Nas linguagens funcionais, distinguese as linguagens estritas das linguagens ditas preguiçosas. Numa linguagem estrita
os valores dos argumentos são avaliados antes de serem passadas em parâmetros duma função. É o caso de linguagens como OCaml e SML. Nas linguagens
preguiçosas, a expressão passada em parâmetro à função f só será avaliada se f
realmente precisa do valor da expressão (origem do nome call by need ).
Imaginemos que a função f (x) = t esteja declarada e que se pretende calcular f (e).
Desde que se precise do valor de x então o calculo de e é realizado. Apesar de
t utilizar várias vezes x, é importante que o cálculo de e se faça uma única vez.
A expressão e é passada em parâmetro com o seu ambiente (estrutura arquivando
6
todas as variáveis utilizadas por e), o que evita os fenómenos de captura de variáveis.
Este mecanismo é assim diferente do mecanismo de substituição textual utilizado no
esquema de passagem de parâmetro anteriormente descrito. A linguagem Haskell
utiliza a avaliação preguiçosa. Este tem a vantagem de só realizar os cálculos úteis.
No entanto, a necessidade de passar ambientes associados aos parâmetros induz um
custo. Mais, é difı́cil neste tipo de linguagem de prever o momento onde efeitos
lateral eventuais presentes nas expressões passadas terão lugar (o que induz vários
comportamentos possı́veis para os programas, o que é indesejável). Por isso Haskell
é uma linguagem funcional pura sem efeitos laterais, o que não impede a linguagem
de ser eficaz e de utilização a escala industrial.
2.3
Acesso às variáveis locais
Um procedimento pode aceder às suas variáveis locais que se encontram na sua tabela
de activação, e às variáveis globais que se encontram num endereço conhecido na altura
da compilação. Nas linguagens funcionais ou de tipo Pascal, os procedimentos podem
ser aninhados e o corpo dum procedimento p pode aceder a variáveis declaradas num
procedimento q que englobe p. É assim necessário aceder à tabela de activação de q que
adequadamente se encontra na pilha de chamadas por baixo da tabela de activação de p.
Infelizmente não é possı́vel determinar estaticamente (sem executar) a posição da tabela
de activação de q em relação a de p. É assim necessária a utilização de mecanismos de
encadeamentos de tabelas de activação para encontrar a variável adequada.
Árvore de nı́vel das declarações Supõe-se que se tem uma linguagem funcional
ou imperativo no qual os procedimentos, funções e variáveis podem ser arbitrariamente
aninhados. O porte das variáveis (variable scope) pode ser calculada de forma estática
seguindo as regras habituais de visibilidade. O nı́vel duma declaração (procedimentos,
funções ou variáveis) é o número de procedimentos ou funções debaixo dos quais esta é
definida. O programa principal tem um nı́vel 0, as variáveis globais definidas no programa
principal terão o nı́vel 1. Por exemplo:
program main
var t:int
procedure p(x,y:int);
var z : int
procedure q(i:int)
var u : int
begin u:=z+t+i;
if x=u or y=u then x
else if u < x then p(u,x)
else if y < u then p(y,u)
else q(i+1)
end
begin read(z); q(z) end
begin read(t);p(t,t) end
7
Podemos calcular de forma estática os nı́veis de cada identificador. Introduz-se um
certo número de definição ligadas às declarações, um identificador designa indiferentemente um procedimento, uma função ou uma variável: dir-se-á que p é o pai dum identificador de y se y é declarada dentro de p. Dir-se-á que p é ancião de y se p é y ou pai
dum ancião de y. Dir-se-á de dois identificadores que são irmãos se têm o mesmo pai. Se
o corpo dum procedimento p faz referência a um identificador então as regras de porte
são tais que este é (a) ou uma declaração local e p (b) ou um ancião de p (por exemplo
o próprio p) (c) ou um irmão dum ancião de p.
Árvore de Activação Interessamo-nos agora pelas execuções possı́veis dum programa.
Para tal introduzimos a noção de árvore de activação.
Os nodos desta árvore representam as chamadas aos procedimentos p(e1 , · · · , en ). Um
nodo tem k filhos q1 · · · qk se a execução do procedimento em causa invoca directamente
os procedimentos q1 · · · qk (este procedimentos podem eles próprios chamar outros procedimentos...). A raı́z da árvore é a execução do programa principal.
Exemplo: Dar as árvores de activação do programa anterior no caso das variáveis lidas
valerem sucessivamente 1, 1 e 0.
Durante uma execução dir-se-á dum procedimento que este é activo se a execução se
encontra entre o inı́cio e o fim do corpo do dito procedimento.
Nota-se assim que a ordem de chamada não corresponde necessariamente a ordem das
declarações. No entanto demonstra-se que quando um procedimento está activo então
todos os seus anciões são igualmente activos (demonstração por indução sobre a árvore
de activação). A execução do programa principal define a raı́z da árvore e este é ancião
dele próprio. Seja p um procedimento activo, esta foi activada por um procedimento q na
árvore de activação cujo todos os anciões são activos (hipótese de indução). Agora, por
razões de visibilidade, sabemos que ou q é o pai de p ou ou p é o irmão dum ancião de q.
Nos dois casos todos os anciões de p estão activos.
Todos os procedimentos activos têm as suas tabelas de activação reservadas em memória
com todas as suas variáveis locais. Se um procedimento activa se refere a uma variável y,
esta foi declarada localmente por um dos seus anciões (potencialmente por ele próprio).
O grau de parentesco deste ancião é conhecido na altura da compilação. Encadeando
cada tabela de activação dum procedimento p com a tabela de activação do seu pai,
encontra-se facilmente seguindo o número de vezes adequadas de indirecções o local onde
a variável se encontra arquivada.
Exemplo: No exemplo anterior o programa pode chamar p mas não q. p pode invocar
q mas q não pode invocar p.
2.4
Organização da tabela de activação
Se, por suposição, o endereço do bloco de activação local é dado por um registo f p e
o contador de instrução (program counter ) é designado por pc então uma organização
possı́vel da tabela de activação pode ser a seguinte:
8
valores intermédios
..
.
fp →
var. loc. k
..
.
fp + k − 1
param 1
val. retorno
..
.
fp − n − 3
fp − n − 4
} Variáveis locais
var. loc. 1
fp + 0
fp do procedimento pai
fp-1
fp do procedimento invocador fp-2
pc na altura da chamada
fp − 3
param n
fp − 4
..
} Argumentos
.
De facto, certos valores como o valor de retorno (no caso de funções), ou até mesmo
os parâmetros, são frequentemente arquivados nos registos.
Passagem de parâmetros de tamanho variável Algumas linguagens, como o Pascal, autorizam a passagem por valor d’argumentos de tipo vector cujo tamanho é igualmente um parâmetro. O tamanho não é então conhecido na altura da compilação. Para
compilar o corpo do procedimento, decide-se de arquivar num local particular o endereço
do vector. Os dados de tamanho variável podem então ser alocados no topo da pilha.
Invocador-Invocado As operações por efectuar durante a invocação dum procedimento estão partilhados entre o procedimento que invoca e o procedimento invocado.
O código gerado pelo invocador deve ser escrito para cada invocação enquanto o código
escrito no invocado só aparece uma só vez.
O invocador efectua a reserva para o valor de retorno no caso das funções e avalia
os parâmetros efectivos do procedimento. Também pode se encarregar de salvaguardar
o valor dos registos correntes (program counter, endereço do bloco de activação) e de
calcular o endereço do bloco de activação do pai do procedimento invocador.
O invocado inicializa os seus dados locais e começa a execução. Na altura do retorno,
o invocado pode eventualmente colocar o resultado da avaliação num local reservado pelo
invocador e restaura os registos.
3
3.1
Código Intermédio
Introdução
Utiliza-se frequentemente um código intermédio independente da máquina/arquitectura
alvo. Isto permite factorizar grande parte da tarefa de compilação e de tornar o compilador mais facilmente adaptável.
A escolha duma linguagem intermédia é muito importante. Este deve ser suficientemente rico para permitir uma codificação confortável das operações da linguagem fonte
9
sem criar demasiadas longas sequências de código. Este deve ser igualmente relativamente
limitado para que a implementação final não seja demasiada custosa.
Vamos descrever agora as operações duma máquina com pilhas (stack based machine)
particular e explicaremos a seguir como gerar o código associado a construções particulares
da linguagens em questão.
Notação: Descreveremos a linguagem a partir de regras gramaticais. Especificaremos uma função code que aceita como parâmetro uma árvore de sintaxe abstracta da
linguagem e devolve uma sequência de instruções de código intermédio (da máquina de
pilhas).
Para clarificar a apresentação utilizaremos notações em sintaxe concreta para representar a sintaxe abstracta.
Por exemplo se E ::= E1 + E2 é uma regra gramatical, escreveremos code(E1 + E2) =
· · · code(E1 ) · · · code(E2 ) para especificar o valor da função code sobre a árvore de sintaxe
abstracta que corresponde a soma de duas expressões.
Se C1 e C2 representam duas sequências de instruções então C1 |C2 representam a
sequência de instrução obtida concatenando C2 no fim de C1 . A lista vazia de instruções
é representada por [].
3.2
Princı́pios de base duma máquina de pilhas particular
Dispomos duma máquina que contém uma zona de código C, um registo pc (program
counter ) que contém o endereço da próxima instrução por executar. as instruções têm
um nome seguido eventualmente de um ou dois argumentos. Estes argumentos serão em
geral inteiros ou etiquetas (label ) simbólicas indicando as instruções do código que serão
traduzidas em inteiros numa fase de pre-análise.
A máquina contém uma pilha P que permite arquivar valores, um registo sp (stack
pointer ) que aponta para para a primeira célula livre da pilha. Um outro registo gp
(global pointer ) aponta para para a base da pilha (local onde serão arquivados as variáveis globais). Esta pilha pode conter inteiros, flutuantes, ou endereços. Por convenção
guardaremos dados de grande tamanho como as strings ou vectores num espaço suplementar. Neste caso a pilha só arquivará o endereço destes dados no referido espaço.
Apresentamos, para cada instrução da máquina, as modificações por considerar no
estado da pilha e dos diferentes registos. Por exemplo:
Código
PUSHI n
Pilha
P [sp] := n
sp
pc
Condição
sp + 1 pc + 1 n inteiro
Significa que a linguagem intermédia possui um comando PUSHI que espera um argumento inteiro n. Se a execução deste comando tem lugar num estado em que a pilha vale
P , em que o registo que aponta para o topo da pilha vale sp e o contador de instrução
vale pc então a execução do referido comando resulta num estado em que o endereço sp
da pilha tem o valor n e os contadores sp e pc foram incrementados de um. Esta instrução
só se executa correctamente se a condições anunciadas são verificadas. No caso contrário
verifica-se o despoletar de um erro de execução.
10
3.3
Expressões aritméticas
A máquina só permite a execução de uma operação aritmética sobre os dois valores
presentes no topo da pilha. Estes dois valores são, durante a execução, retiradas da pilha
e o resultado da operação é colocado no topo da pilha.
Código Pilha
sp
pc
Condição
ADD
P [sp − 2] := P [sp − 2] + P [sp − 1] sp − 1 pc + 1 P [sp − 2], P [sp − 1]
inteiros
SUB
P [sp − 2] := P [sp − 2] − P [sp − 1] sp − 1 pc + 1 P [sp − 2], P [sp − 1]
inteiros
MUL
P [sp − 2] := P [sp − 2] × P [sp − 1] sp − 1 pc + 1 P [sp − 2], P [sp − 1]
inteiros
DIV
P [sp − 2] := P [sp − 2]/P [sp − 1]
sp − 1 pc + 1 P [sp − 2], P [sp − 1]
inteiros, se divisor
nulo então erro
De forma similar existe um conjunto de instruções dedicadas à aritmética de flutuantes: FADD, FSUB, FMUL, FDIV e PUSHF.
Comparações O valores booleanos para o resultado de comparações podem ser representados por inteiros. O inteiro 1 representará o valor verdade e 0 o falso. A igualdade
corresponderá a mesma instrução, quer se fale de comparar inteiros, flutuantes ou endereços.
Código Pilha
sp
pc
Condição
INF
P [sp − 2] := (P [sp − 2] < P [sp − 1])?1 : 0
sp − 1 pc + 1 P [sp − 2], P [sp − 1]
inteiros
INFEQ P [sp − 2] := (P [sp − 2] ≤ P [sp − 1])?1 : 0
sp − 1 pc + 1 P [sp − 2], P [sp − 1]
inteiros
SUP
P [sp − 2] := (P [sp − 2] > P [sp − 1])?1 : 0) sp − 1 pc + 1 P [sp − 2], P [sp − 1]
inteiros
SUPEQ (P [sp − 2] := (P [sp − 2] ≥ P [sp − 1])?1 : 0) sp − 1 pc + 1 P [sp − 2], P [sp − 1]
inteiros
EQUAL P [sp − 2] := (P [sp − 2] = P [sp − 1])?1 : 0) sp − 1 pc + 1 P [sp − 2], P [sp −
1] simultaneamente
inteiros, flutuantes,
endereços
De forma similar a máquina disponibiliza um conjunto de instruções para flutuantes:
FINF, FINFEQ, FSUP, FSUPEQ.
Geração de código A representação de expressões aritméticas sob a forma binária
permite gerar de forma simples código permitindo o cálculo de expressões aritméticas.
O invariante por preservar descreve-se da seguinte forma: após a execução de code(E)
(E expressão aritmética) a partir dum estado onde sp = n, os valores de P [m] onde
m < n não foram modificados, o valor da expressão E é calculada e encontra-se em P [n]
e sp = n + 1.
Se supomos que as expressões aritméticas são geradas pela gramática:
11
E ::= inteiro|E1 + E2 |E1 − E2 |E1 × E2 |E1 /E2
O código correspondente é dado por:
code(inteiro)
code(E1 + E2 )
code(E1 − E2 )
code(E1 × E2 )
code(E1 /E2 )
3.4
= P U SHI inteiro
= code(E1 )|code(E2 )|ADD
= code(E1 )|code(E2 )|SU B
= code(E1 )|code(E2 )|M U L
= code(E1 )|code(E2 )|DIV
Variáveis
Variáveis globais Se a linguagem fonte permite a memorisação determinados valores
em variáveis então será necessário recorrer mecanismos que permitam, na máquina, o
arquivo e o acesso a valores. Estes mecanismso assentam em duas instruções que permitam
(a) a atribuição dum valor calculado na pilha para um espaço reservado para as variáveis
globais; (b) colocar no topo da pilha de operandos um valor contida numa variável global.
Se a é um endereço na pilha e n um inteiro então a + n designa o endereço localizado
n céliulas acima de a. Estes dois comandos são:
Código
Pilha
sp
pc
Condição
PUSHG n
P [sp] := P [gp + n]
sp + 1 pc + 1 n inteiro, gp + n < sp
STOREG n P [gp + n] := P [sp − 1] sp − 1 pc + 1 n inteiro, gp + n < sp
O inteiro associado a cada variável id atribuı́do será calculado na altura da análise
sintáctica ou semântica e associada ao identificador, por exemplo, dentro da tabela de
sı́mbolos e designada por adr(id).
É preciso cuidar que os cálculos intermédios não removam os valores arquivados. É
assim importante reservar atempadamente o espaço para todas as variáveis globais antes
de iniciar os primeiros cálculos. O apontador de topo de pilha deverá inicialmente apontar
para a primeira célula livre que está a seguir ao espaço reservado para as variáveis globais.
Para este efeito utilizaremos uma instrução que arquiva n valores nulos (iguais a 0)
na pilha. Introduz-se igualmente a instrução dual que permite fazer recuar o apontador
para a pilha de n espaços para baixo, o que equivale de facto em apagar n valores da
pilha.
Código Pilha
sp
pc
Condição
PUSHN n P [sp + i] := 0, ∀i.sp ≤ i < sp + n sp + n pc + 1 n inteiro
POPN n
sp − n pc + 1 n inteiro
Admitimos agora que a nossa gramática de expressões é enriquecida da seguinte forma
para poder acceder às variáveis globais:
E ::= id
O código correspondente é definido por:
code(id) = PUSHG adr(id)
no caso de uma variável de tamanho unitário. Senão, se representa uma dado arquivado sobre k palavras, por:
12
code(id) = PUSHG adr(id) PUSHG adr(id) + 1 · · · PUSHG adr(id) + (k − 1)
Consideremos agora uma linguagem cujas únicas instruções são sequências de atribuições.
A análise semântica deve determinar para cada variável global id um espaço (relativamente a gp) designado por adr(id) onde o valor correspondente será arquivado.
Acrescentamos um sı́mbolo não-terminal à gramática para representar as instruções
da linguagem. Extendemos a seguir a função code em conformidade. Assim, temos a
gramática:
I ::= I ::= I1 A;
A ::= id := E
e a geração de código seguinte:
code()
= []
code(I1 A; )
= code(I1 )|code(A)
code(id := E) = code(E)|STOREG adr(id)
No caso dum dado codificado sobre k palavras, utilizaremos para codificar id := E as
instrucções:
code(E)|STOREG adr(id) + (k − 1)| · · · |STOREG adr(id)
O invariante por conservar é que o código associado a uma sequência de instruções
começa e termina com um apontador de pilha por cima do conjunto dos valores globais.
Vectores Em geral, o número de células da pilha nos quais um dado é representado
depende do tipo do dado ( inteiro, real, vector, estrutura). Supõe-se que este tamanho é
conhecido na fase de compilação e é designada por tamanho(id).
Os vectores são representados por sequências de células adjacentes na pilha. Se o
vector t tem ı́ndices entre m e M , começa no endereço a e contém valores de tamanho k,
então este ocupa um espaço de tamanho (M − m + 1) × k.
Para calcular o endereço correspondente a uma expressão t[E] é necessário calcular
o valor de n de E e aceder ao endereço a + (n − m) × k. Se conhecemos o valor de m
na fase de compilação então podemos avaliar parcialmente esta expressão pre-calculando
a − m × k e arquivar este valor em t.val. Precisar-se-á posterior e simplesmente calcular
t.val + n × k.
Os comandos PUSHG, STOREG não permitam aceder a um endereço conhecida na altura
da compilação. Assim para aceder a vectores precisaremos de um acesso parametrizado
por um valor calculada durante a execução.
Em regra geral, o endereço ao qual precisamos de aceder depende dum endereço de
base a que não é necessariamente conhecido estaticamente (caso dos vectores de tamanho
variável) e dum salto (offset) n que é igualmente calculado durante a execução. Extendemos assim os comandos PUSHG, STOREG, que operavam a partir dum endereço fixo gp e
dum salto estático n em argumento, em comandos LOADN e STOREN que procuram estas
informações dinamicamente na pilha.
13
Figura 2: LOADN e STOREN
Código Pilha
sp
pc
Condição
LOADN
P [sp − 1] := P [P [sp − 2] + P [sp − 1]] sp − 1 pc + 1
STOREN P [P [sp − 3] + P [sp − 2]] := P [sp − 1] sp − 3 pc + 1
Podemos representar graficamente o comportamento destes dois comandos concretizando
a pilha e numerando as células por inteiros k, k + 1, · · ·: ver figura 2
Podemos notar que estas instruções poderiam ser decompostas num comando que
permita o acesso a um elemento da pilha via um endereço arquivado na pilha, e num
comando que permita realizar cálculos sobre os endereços.
Acrescentamos à nossa linguagem os vectores que supomos serem de uma só dimensão.
Temos assim as duas novas produções seguintes:
E ::= id[E]
I ::= id[E1 ] := E2
Para gerar código, devemos poder colocar na pilha um endereço. Definimos assim a
instrucção PUSHGP que permite arquivar o endereço do apontador global na pilha.
Código Pilha
sp
pc
Condição
PUSHGP P [sp] := gp sp + 1 pc + 1
Supondo que o endereço de base onde é arquivado cada vector é conhecido, o código
gerado é:
code(id[E])
= PUSHGP|PUSHI adr(id)|code(E)|ADD|LOADN
code(id[E1 ] := E2 ) = PUSHGP|PUSHI adr(id)|code(E1 )|ADD|code(E2 )|STOREN
Os vectores bi-dimensionais podem ser arquivados via linearização em linha ou ainda
em coluna. Se cada dimensão tem por ı́ndice minimal mi , ı́ndice maximal Mi e por
tamanho ni = Mi − mi + 1, então se o arquivo é realizado em linha então teremos em
primeiro o vector t[1, i] seguido de t[2, i], . . .
O elemento t[i1 , i2 ] é arquivado no endereço a + ((i1 − m1 ) × n2 + (i2 − m2 )) × k
Aqui também podemos pre-calcular parte da expressão re-escrevendo-a em:
((i1 × n2 + i2 ) × k + a − (m1 × n2 + m2 ) × k
14
Quando encontramos uma expressão id[E1 , E2 ] será necessário calcular o offset por
aplicar a partir da base onde está arquivado id para poder aceder ao elemento designado.
Podemos generalizar este processo aos vectores de dimensão p.
No caso de vectores cujo tamanho não é conhecido na altura da compilação, não será
possı́vel realizar este processo de pre-compilação.
Outros comandos de acesso Podemos igualmente precisar de ter acesso a um dado
na pilha referenciado de forma estática, a partir dum endereço arquivado na pilha. Tal
processo é possı́vel com os comandos LOAD e STORE seguintes:
Código Pilha
sp
pc
Condição
LOAD n
P [sp − 1] := P [P [sp − 1] + n] sp
pc + 1 n inteiro
STORE n P [P [sp − 2] + n] := P [sp − 1] sp − 2 pc + 1 n inteiro
3.5
Instrucções condicionais
Para compilar expressões condicionais e ciclos iremos precisar de comandos de salto na
zona de instrucções. As instrucções serão designadas por endereços simbólicos inseridos
no código.
Código
Pilha sp
pc
Condição
JUMP label
sp
label
JZ label
sp − 1 (P [sp − 1] = 0)?label : pc + 1
Para compilar expressões, é necessário adoptar uma convenção para a representação
dos boleanos. Existem diferentes opções, podemos representar o falso por 0 e o valor
verdade por qualquer inteiro positivo ou utilizar somente o valor 1.
Vamos a seguir ver como gerar código para expressões condicionais e ciclos:
I ::= if E then I endif
I ::= if E then I1 else I2 endif
I ::= while E do I done
Introduz-se um comando suplementar na linguagem intermédio LABEL label que introduz um endereço simbólico label correspondente ao número da instrução, sem modificar
o estado da pilha. Só o program counter é incrementado.
Exercı́cio: Dar um sistema de atributo para a linguagem intermédia que permite a
remoção das instruções LABEL e de substituir os endereços simbólicos por endereços
inteiros.
code(if E then I endif )
= code(E) | JZ new next | code(I) | LABEL new next
code(if E then I1 else I2 endif ) = code(E) | JZ new f alse | code(I1 ) | JUMP new next |
LABEL new f alse | code(I2 ) | LABEL new next
code(while E do I done)
= LABEL new loop | code(E) | JZ new next | code(I) |
JUMP new loop | LABEL new next
Para esta compilação, é necessário criar de cada vez novas etiquetas new f alse,
new next e new loop.
15
Compilação de expressões boleanas As expressões booleanas, digamos por exemplo E, servem frequentemente para operações de controlo. Podemos assim considerar
sistematicamente duas etiquetas E true e E f alse e compilar a expressão boleana E sem
calcular o seu valor mas decidindo que o resultado da execução de E deve se concluir em
pc = E true quando E é verdade, ou em pc = E f alse caso contrário. Definimos então
uma função code bool que aceita em parâmetro uma expressão boleana e duas etiquetas
e que devolve o código de controlo.
Começemos por uma gramática de expressões booleanas:
B
B
B
B
B
B
::=
::=
::=
::=
::=
::=
B1 or B2
B1 and B2
not B1
verdade
f also
E1 relop E2
O código gerado correspondente é:
code bool(B1 or B2 , ev , ef )
code
code
code
code
code
= code bool(B1 , ev , new e)|LABEL new e|
code bool(B2 , ev , ef )
bool(B1 and B2 , ev , ef ) = code bool(B1 , new e, ef )|LABEL new e|
code bool(B2 , ev , ef )
bool(not B1 , ev , ef )
= code bool(B1 , ef , ev )
bool(verdade, ev , ef )
= JUMP ev
bool(f also, ev , ef )
= JUMP ef
bool(E1 relopE2 , ev , ef ) = code(E1 )|code(E2 )|code(relop)|JZ ef |JUMP ev
Neste código, new e representa uma etiqueta criada para o efeito. code(relop) representa o operador relacional utilizado.
Nota: Numa linguagem que possibilita os efeitos laterais nas expressões, calcular
ou não as sub-expressões duma expressão booleana pode resultar em comportamentos
radicalmente diferentes.
Compilação de expressões com branching múltiplo Tratam-se de expressões de
tipo switch, case ou match que permitam o branching múltiplo consoante os diferentes
valores duma expressão parâmetro. Estes valores são geralmente de tipo numérico e
conhecidos na fase de compilação.
switch E begin case V1 : S1
case V2 : S2
..
.
case Vn : Sn
end
Antes de mais devemos nos assegurar da semântica duma tal expressão. Uma semân-
16
tica natural é:
if
E = V1 then S1
else if E = V2 then S2
..
.
else if E = Vn then Sn
Não é, no entanto, a semântica da instrução switch da linguagem C. Nesta linguagem
executa-se todas as instruções Si ; . . . ; Sn a partir do primeiro i tal que E = Vi . É a
presença duma instrução break num Si que permite a saı́da do switch.
if
elseif
..
.
E = V1 then goto l1
E = V2 then goto l2
elseif
l1 :
..
.
E = Vn then goto ln
S1
ln :
break :
Sn
Podemos optimizar a compilação se os valores dos vi são todos distintos num intervalo
[k + 1, k + n]. Cria-se então no código uma tabela de branching que se inicia por LABEL
inicio e que integra sucessivamente as instruções JUMP l1 , . . ., JUMP ln . Seguem-se então o
código de cada ramo da estrutura condicional LABEL li | code(Si ), seguida eventualmente
duma instrucção JUMP f im. É desta forma necessário dispor duma instrução de salto
indexado que notaremos JUMPI. Esta instrução aceita uma etiqueta e devolve o controlo
à instrução cujo número é o valor numérico da etiqueta mais o valor do topo da pilha.
Código
Pilha sp
pc
Condição
JUMPI label
sp − 1 label + P [sp − 1]
Insere-se então o código de E : code(E) do qual é necessário subtrair a constante
k : PUSHI k|SU B.
Testa-se se o valor obtido está entre 1 e n e efectua-se o branching indexado correspondente, senão a instrução é ignorada. Como o valor no topo da pilha deve ser utilizada para
duas comparações e o salto indexado, é preciso utilizá-la 3 vezes e, por isso, duplicá-lo
deu as vezes com a ajuda da instrução DUP. Obtém-se o código seguinte:
DUP|DUP
|PUSHI n|INFEQ|JZ f im
|PUSHI 1|SUPEQ|JZ f im
|JUMPI inicio
|LABEL f im
Exercı́cio: Modificar o esquema para o caso em que a intrucção switch inclua um caso
por defeito.
3.6
Invocar procedimentos
A invocação de procedimentos tem dois efeitos. O primeiro é de modificar o decorrer
sequencial da execução, o segundo é de criar um espaço para os dados locais.
17
Sub-rotinas Imaginemos que queremos reutilizar em vários locais a mesma porção de
código I. Para tal isola-se I e atribuimo-lhe uma etiqueta. Podemos então substituir
todas as cópias de I por uma instrução de salto para I. O problema é conseguir voltar de
I para o bom local (a instrução que segue o salto para I) e proceder ao resto da execução.
Se temos várias utilizações da rotina então não podemos colocar simplesmente uma
instrução de salto estático. É assim necessário, antes do salto para I, arquivar o valor do
apontador de programa ( o valor do registo pc, program counter ) e restaura-lo no fim da
execução de I.
Como as chamadas a sub-rotinas podem ser aninhadas, é necessário tornar possı́vel
o arquivo dum número arbitrário de tais valores. Esta informação poderia ser guardada
na pilha de operandos, mas a máquina que utilizamos aqui tem uma pilha especialmente
dirigida ao processamento deste tipo de informação.
As instruções CALL e RETURN permitam o correcto processamento do apontador de
programa. A instrução CALL toma em parâmetro um endereço no código. O contador de
instrução coloca-se então na posição especificada sendo o seu antigo valor arquivado.
A instrução RETURN descobre o antigo valor do apontador de programa e atribuı́-lhe
o valor seguinte (isto é, aponta agora para a instrucção que segue).
Acrescenta-se então à linguagem definições e invocação de sub-rotinas:
D ::= proc p; begin I end
I ::= call p
code(proc p; begin I end) = LABEL label p|code(I)|RETURNcode(call p) = CALL label p
label p é uma etiqueta única associada ao pocedimento p.
Procedimentos com parâmetros Se o procedimento tem parâmetros então o papel
deste procedimento é permitir a gestão na pilha do espaço necessário para estes parâmetros (reserva e acesso). Como só se consegue fazer referência a células da pilha a partir do
endereço de base, é necessário dispor dum registo suplementar f p que será actualizado
ao inı́cio da invocação do procedimento e que permitirá referenciar os valores locais. Na
saı́da do procedimento este espaço deverá ser liberto.
A chamada e o retorno dos procedimentos pode ser percebido como uma modificação
do valor de pc e da atribuição dum endereço de base para as variáveis locais.
No momento do retorno do procedimento, o valor de pc deve ser incrementado de 1 e o
valor de f p restituı́da ao valor que tinha antes da invocação, visto as chamadas poderem
ser aninhadas. A pilha ficará truncada de toda a parte alocada a seguir à chamada do
procedimento.
O papel dos comandos CALL e RETURN será exactamente assegurar o correcto
arquivo de f p e pc.
Instrucções de manipulação de dados locais A linguagem contém instruções para
manipular dados referenciadas a partir do apontador f p. Às instruções PUSHGP, STOREG,
PUSHG correspondem as instruções PUSHFP, STOREL, PUSHL que têm o mesmo comportamento só que sobre f p e não sobre gp.
18
Tabela de activação No caso de uma alocação estática, a tabela de activação será
constituı́do (a) dos parâmetros do procedimento que serão instanciados no momento da
chamada (b) do endereço da tabela de activação do procedimento chamadora (c) do local
para as variáveis locais.
A gramática para as declarações tem a forma seguinte:
Ds ::= Ds D; |
D ::= var id : T |proc id(Ds ) Ds begin I end|
f un id(Ds) : T Ds E
Podemos calcular, por exemplo, por atributos, o nı́vel de cada sı́mbolos de procedimentos, função ou variável, que é o número de procedimentos ou funções sob o qual este
se encontra definido. Este valor corresponde a profundidade do sı́mbolo na árvore de
declarações. O programa principal tem um nı́vel igual a 0.
O offset associada a uma variável é o inteiro que se deve adicionar a f p para obter o
endereço de base da variável.
Exercı́cio: Definir um sistema de atributos para calcular os nı́veis e offset das declarações.
No momento duma chamada por valor de q(e1 , . . . , en ), temos de calcular o código
de e1 , . . ., en que serão empilhados, como também temos de calcular o endereço da
tabela de activação do invocador. Para tal olhamos para os nı́veis respectivos de q e do
procedimento p que chamou q. O dado importante aqui é o nı́vel relativo n que é igual
ao nı́vel de p menos o nı́vel de q e que é sempre maior ou igual a −1 (= −1 quando q é
declarado dentro de p).
Calculo do endereço do vector de activação pai Quando p chama q então o cálculo
do endereço do pai de q faz-se pela sequencial de instrução seguinte:
PUSHFP | |LOAD{z − 1}
n+1 vezes
Podemos notar que a sequência de instrução PUSHFP | LOAD n é equivalente a PUSHL n
Quando este registo é actualizado, podemos executar a invocação com o comando CALL
q. O inı́cio deste procedimento deve reservar o espaço para as variáveis locais seguida da
execução do código. No fim da execução do procedimento, o comando RETURN é invocada.
Esta removerá da pilha os valores locais mas não os parâmetros. O invocador poderá então
retirar da pilha os parâmetros assim como o endereço do pai. Se o procedimento é uma
função que retorna um valor, então a localização deste último deverá ser devidamente
reservado antes da chamada do procedimento. Escolhe-se normalmente a utilização do
primeiro espaço livre da pilha.
Cálculo do acesso a uma variável Se dentro dum procedimento p se pretende aceder
a uma variável x calcula-se ainda uma diferença n entre o nı́vel np de p e nx, o nı́vel de x,
que é superior a −1. Conhece-se a offset dx de x. O código para aceder ao valor direito
de x é assim parametrizado pelo nı́vel np do procedimento dentro do qual se está:
code var(x, np) = PUSHFP| |LOAD{z − 1} |LOAD dx
np−nx+1 vezes
19
Passagem de parâmetros por valor No modo de passagem por valor teremos a
compilação de corpos de procedimentos seguinte:
code(proc id(Ds1 ) Ds2 begin I end) = LABEL label id | PUSHN tamanho(Ds2 ) |
code(I) | RETURN
A invocação faz-se pelos comandos seguintes:
LE ::= E | LE, E
A
::= call id(LE)
A geração de código duma sequência de expressão é assim somente a concatenação
dos diferentes códigos.
O código associado à invocação dum procedimento q de nı́vel pq é parametrizada pelo
nı́vel np do procedimento invocador:
code call(call q(LE), np) = code(LE) | PUSHFP | LOAD
| {z − 1} |
np−nq+1 vezes
CALL label id | POP tamanho(LE) + 1
Exercı́cio: Escrever o código de compilação e de invocação duma função.
Passagem de parâmetros por referência No lugar de empilhar os valores das expressões, empilha-se os seus valores esquerdos (isto é endereços). Os acessos às variáveis
fazem-se então via uma indirecção.
Passagem duma função em parâmetro Para compilar um procedimento que aceita
uma função em parâmetro, são necessários duas informações: o endereço da função e o
endereço do vector de activação do pai do procedimento.
Exemplo
program main
procedure b(function h(n:int):inte);
begin print(h(2)) end
procedure c;
var m:int;
function f(n:int) : int; begin f:=m+n end
begin m:=0; b(f) end
begin c end
Para executar o código do procedimento é necessário conhecer o endereço do código
deste procedimento assim como o endereço da tabela de activação do procedimento.
Quando c deve executar b(f ), este calcula a ligação de activação du pai estático de f
(aqui c) como se este o chamasse e passa-o a b que poderá o utilizar na altura da invocação
de f .
20
Retornar uma função como valor Algumas linguagens permitam devolver funções
como valores. No entanto se a linguagem autoriza o acesso a variáveis não locais, o
problema que se coloca é o da persistência dos valores assim manipulados.
Exemplo
let f(x) = let g(y) = x+y in g
let h = f(3)
let j = f(4)
h(5)+j(7)
O valor duma função é designado de fecho (closure) e é formada por um apontador
para o seu código assim como por um ambiente que associa valores a todas as variáveis
utilizadas no corpo da função e que não são locais na altura da definição da função.
4
Utilização de registos
Os registos permitan arquivar informações e manipula-las de forma rápida. No entanto
estes registos existam normalmente em número pequeno. Convêm assim geri-los da melhor forma.
Uma forma de o fazer é de introduzir para cada valor intermédio uma nova variável e
de construir um grafo de interferência: os nodos são as variáveis e temos um arco entre
x e y se x e y não podem ser arquivados no mesmo registo (i.e. as duas variáveis estão
vivas na mesma altura).
Podemos igualmente considerar os registos como os nodos deste grafo e ligar a existência dos arcos como o facto de certos valores não poderem ser arquivados no registo
particular.
Assim, determinar uma repartição das variáveis sobre k registos resume-se em encontrar uma k-coloração do grafo. Visto este problema ser NP-Completo em geral, utiliza-se
uma aproximação. Se este grafo é vazio, então a coloração é evidente. Se o grafo contempla um nodo x de grau estritamente inferior a k então constroi-se um novo grafo G0
removendo este nodo e as arestas correspondentes. Se G0 pode ser colorido então podemos
encontrar uma cor para x, diferente de todos os seus vizinhos e acrescenta-lo. Nota-se
que remover x de G pode diminuir o grau de outros nodos e tornar assim a coloração
possı́vel. Se o grafo só comporta nodos de grau superior a k então escolhe-se e remove-se
um nodo x e procura-se colorir o grafo resultante. Se for possı́vel, olha-se para o número
de cores utilizadas para colorir os vizinhos de x. Se existe uma cor disponı́vel então é
possı́vel colorir x e este é de novo acrescentado ao grafo, senão a coloração não é possı́vel
e x tem de ser arquivado na memória. Para tal escolhe-se um espaço mx para arquivar
x e introduz-se para cada utilização de x uma nova variável xi . Se o valor de x é utilizado numa expressão, começamos por colocar em xi o valor arquivado no endereço mx
da memória. Se x é actualizada então substitua-se x por xi e propaga-se esta instrução
de actualização de mx na memória pelo valor de xi . A duração de vida das variáveis xi
é pequena, estas não interfiram com as outras variáveis.
É necessário modificar o grafo de interferência e recomeçar a coloração. O grafo de
interferência pode igualmente ser utilizado para remover as instruções move entre registos
21
associadas a instruções x := y. Podemos identificar x e y desde que x e y não são vivas
simultaneamente. No entanto, esta identificação terá como resultados o aumento do
grau do nodo xy (resultado da identificação entre x e y), o que poderá fazer com que a
colorização falhe. Efectuar uma deslocação nos registos é menos custoso do que um acesso
à memória. Assim far-se-á a identificação só em alturas em que se consegue guarantir a
preservação da colorização. É o caso quando o conjunto de vizinhos de xy contempla têm
estritamente menos de k nodos de grau inferior a k.
Exemplo (A. Appel) Considere-se o programa seguinte formado de atribuições simples e de acessos à memória. Indicamos na segunda coluna o conjunto de variáveis simultaneamente vivas no ponto de programa anterior, sabendo que após a execução deste
código as variáveis d, k e j são vivas.
g
h
f
e
m
b
c
d
k
j
Instrucções
:= mem [j+12]
:= k - 1
:= g * h
:= mem[j+8]
:= mem[j+16]
:= mem[f]
:= e+8
:= c
:= m+4
:= b
Variáveis Vivas
k, j
j, g, k
j, g, h
j, f
j, f, e
m, f, e
m, b, e
m, b, c
m, b, d
b, d, k
d, k, j
Podemos olhar para os nodos do grafo nesta ordem: m, c, b, f , e, j, d, k, h e g. e
constatamos que em cada instante cada nodo tem um grau inferior ou igual a 3. Podemos
assim realizar uma colorização com 4 cores e obtemos por exemplo a atribuição de cores
seguintes: m = 1, c = 2, b = 34,f = 24, e = 4, j = 3, d = 4, k = 1, h = 1 e g = 2.
Se dispúnhamos só de 3 registos, poderı́amos recomeçar a análise com os nodos na
ordem seguinte (os nodos em negrito são os que tem um grau superior a 3 e que podem
assim colocar problemas): b, d, j, e, f, m, k, g, c e h. Uma tentativa ed coloração pode
ser: b = 1, d = 2, j = 1, e = 2, f = 3 , m, k, g, c e h não permitam a coloração de
m. Podemos então escolher arquivar m na memória no endereço M . Devemos assim
transformar o programa:
22
Instrucções
g
:= mem [j+12]
h
:= k - 1
f
:= g * h
e
:= mem[j+8]
m1
:= mem[j+16]
mem[M] := m1
b
:= mem[f]
c
:= e+8
d
:= c
m2
:= mem[M]
k
:= m2 +4
j
:= b
Variáveis Vivas
k, j
j, g, k
j, g, h
j, f
j, f, e
m1 , f, e
f, e
b, e
b, c
b, d
m2 , b, d
b, d, k
d, k, j
O nodo m de grau 5 transformou-se em dois nodos m1 e m2 de grau 2. Podemos
examinar de novo os nodos do novo grafo na ordem seguinte: h, c, m2 , m1 , f , e, b, d, k,
ge j e não permanecem mais dificuldades.
Este tipo de mecanismo de colorização pode igualmente ser utilizado para minimizar o
número de espaços memória utilizados no arquivo em memória das variáveis. O objectivo
será assim a minimização do número de move mesmo se isto aumente o número de células
memória utilizada.
5
Alocação na Heap
Na codificação que acabamos de abordar, os novos valores por calcular ao longo da execução são alocados na pilha. Este princı́pio funciona porque o que é alocado durante a
invocação deixa de ser acessı́vel no fim do procedimento.
Este princı́pio não consegue cobrir todos os casos possı́veis. Por exemplo, se a linguagem permite retornar valores funcionais, então vimos que o valor devolvido deve conter
uma representação do ambiente no qual a função se encontra definida.
Este ambiente que deve sobreviver ao fim do procedimento que a define incluı́ no
entanto valores alocados na tabela de activação do procedimento ”definidor”.
5.1
Representação de Dados Estruturados
No exemplos anteriores, alocamos para cada variável um espaço correspondente ao tamanho
do referido dado. Assim a passagem de vectores em parâmetros necessita que sejam alvos
de cópia. Seria mais eficiente manipular os objectos de tamanho importante pelo intermédio dos seus endereços. No caso dos vectores em OCaml, por exemplo, existe um
momento em que o vector é criado (por exemplo, explicitamente por [|1; 2; 3|] ou via o
comando Array.create) e um valor do tipo vector é simplesmente o endereço dum vector. Naturalmente o vector pode ser alocado no corpo duma função e ser devolvido como
resultado da função. Neste caso é necessário que este seja alocado numa zona de dados
persistente. Alocar tais dados na zona das variáveis globais não é de todo uma boa ideia.
23
Pois a duração de vida de tais objectos é em geral limitada, é assim inútil reservar espaço
memória durante toda a execução do programa.
5.2
Alocação dinámica
Trata-se de criar dinamicamente novos espaços memória durante a execução do programa,
espaços que ficarão acessı́veis pelo programa sem, no entanto, ficarem directamente ligados
a variáveis. A duração de vida destes objectos não é forçosamente ligada a duração de
vida dos procedimentos. Reserva-se assim espaços para esses objectos preferencialmente
num local designado de heap. É possı́vel que células memórias reservadas desta forma
deixam de ser acessı́veis durante a execução do programa. Distingue-se nas linguagens os
dados directos tais como os inteiros que serão alocados e manipulados na pilha de dados
dos dados cuja manipulação se faz pelo intermédio dum endereço na memória. Uma tal
manipulação é necessária quando a linguagem contêm funções polimórficas que podem
manipular dados de tamanho variável durante a execução.
5.3
Alocação / Desalocação explı́cita
Linguagens como Pascal ou C oferecem primitivas para alocar ou desalocar partes de
memória (new/dispose em Pascal, malloc/free em C). Se todos os dados por alocar têm
o mesmo tamanho então é possı́vel criar uma lista encadeada na qual se poderá procurar
um novo espaço ou ao contrário liberar uma célula. Reserva-se o espaço que engloba o
espaço necessário para o dado por alocar mais o espaço para o endereço do dado seguinte
na pilha dos espaços disponı́veis. Se é preciso alocar objectos de tamanho diferente então
deve-se usar a heap. A desalocação dum dado não liberta necessariamente um espaço
em memória suficiente para os dados seguintes, a heap transforma-se em gruyère. Isto é,
mesmo se o espaço livre total é suficiente, este pode estar de tal forma fraccionado que a
alocação pode falhar.
A alocação/desalocação explı́cita torna a programação mais pesada e faz correr o risco
(a) de utilizar desnecessariamente espaço para dados inacessı́veis; ou (b) ao contrário
remover dados acessı́veis. Os erros de comportamento e de execução resultantes são,
além disso, de difı́cil diagnóstico.
5.4
Alocação / Desalocação implı́cita
Linguagens como o LISP, ML ou JAVA escolheram a via da alocação dinâmica. A execução
será levada a alocar memória e encarregar-se-á da sua recuperação. É o mecanismo de
”recuperação de lixo”: Garbage collector.
Vários métodos para a recuperação de memória existam.
Contador de referências Cada célula dinamicamente alocada incluı́ um contador que
indica quantos referencias estão a apontar para ela. Quando se faz um new(p), a célula em
questão vê o seu contador inicializado a um. Uma atribuição entre apontadores da forma
t:=u onde t é uma expressão que deve se avaliar num valor esquerdo x que representa
um apontador e cujo valor direito é um endereço para uma célula m. A expressão u
representa igualmente um apontador que se avalia num valor ditreito que é um endereço
24
para a célula n. A célula m que era previamente acessı́vel por x deixou de o ser, logo o
seu contador é decrementado de um. Por outro lado, a célula n é agora acessı́vel a partir
de x logo o seu contador é incrementado de 1. as células cujo contador é nulo podem
ser recuperadas (libertas). No entanto existem situações em que duas células apontam
uma para a outra e ficam assim ambas os seus contadores com o valor 1 mesmo se ambas
ficaram inacessı́veis.
Este método, além desta situação, é igualmente guloso em termos de tempo de execução.
Exemplo
type list = Nil | Cons of int * list ref
let x = Cons(7,ref Nil)
in let y = Cons(9,ref x)
in let t = Cons(10,ref y)
in let Cons(_,z)=x in z:=y;;
Mark and Sweep Trata-se aqui de partir das variáveis da pilha que são acessı́veis pelo
programa e de marcar todas as células assim utilizadas, e isso de forma recursiva. Quando
o processo termina, uma segunda execução permite libertar todos os espaços inacessı́veis.
Esta recuperação é custosa em termos de tempo, o que é problemático para as aplicações em tempo real. Tem também o inconveniente de fragmentar a memória. Por outro
lado utiliza um processo recursivo para marcar a memória que pode conduzir a um memory overflow. Para evitar utilizar espaço memória suplementar para gear as chamadas
recursivas pode-se efectuar um percurso em profundidade das ligações da memória e
inverter as ligações entre células memórias para memorizar as zonas que restam por percorrer.
Stop and copy Para evitar os problemas de fragmentação podemos decidir de sempre
alocar linearmente os dados. quando uma zona se encontra cheia, para-se e copia-se
toda a parte útil numa segunda zona de forma contı́gua. Liberta-se a seguir toda a zona
previamente ocupada. Este método tem o inconveniente de só poder efectivamente ocupar
metade do espaço reservado.
Métodos mixtos Os GCs modernos utilizam um compromisso entre estas diferentes
métodos. Por exemplo caml-light utiliza um GC (elaborado por Damien Doligez) deste
tipo. O espaço memória é separado em duas zonas. a primeira é designada de velha é
organizada com a ajuda duma lista de locais acessı́veis. Esta zona poderá ser extendida
dinamicamente se necessário. A outra zona, designada de nova está organizada como um
vector linear de tamanho fixo. As células são alocadas linearmente no vector. Quando este
vector se encontra cheio. Parde tamanho fixo-se o processo e copia-se todos os objectos
úteis (os que são acessı́veis a partir das variáveis da pilha, dos registos, dos objectos da
zona velha, estes estando referenciados numa tabela de referências) na zona velha. Esta
etapa chama-se um GC menor. Faz-se em seguida uma fase de GC maior. Esta consiste
num mark and sweep incremental da zona velha. Para marcar estes objectos utiliza-se
uma colorização. Os nodos são brancos quando não foram visitados, cinzentos quando
25
foram visitados mas não os seus filhos, pretos quando foram visitados e os filhos também.
Guarda-se uma pilha de nodos cinzentos, quando não resta nenhum nodo cinzento a
marcação/coloração terminou.
Os nodos que ficaram com a cor branca podem ser libertos para a lista de células
livres da zona velha. Para gerir o GC, a representação de CAML reserva um bit sobre
cada palavra para distinguir os endereços (que o GC deve seguir) dos inteiros. A heap
é organizada em zonas correspondentes às diferentes estruturas alocadas (vectores, tipo
de dados estruturados, fecho, etc.). O cabeçalho de cada zona reserva-se dois bits para a
marcação (branco, cinzento e preto) do GC.
26