Tese Mestrado
Tese Mestrado
Tese Mestrado
Estudo e desenvolvimento de
sistemas de geração de back-ends
do processo de compilação
DEPARTAMENTO DE INFORMÁTICA
UNIVERSIDADE DO MINHO
Maio, 1999
I
Resumo
Abstract
Agradecimentos
Um voto de gratidão ao Doutor Pedro Henriques pela confiança, pelo tempo e pela
paciência que teve de despender comigo. Julgo que, o melhor agradecimento que lhe
posso mostrar é afirmar que, sem a sua ajuda, o trabalho desenvolvido ao longo desta
dissertação nunca teria sido possível, pelo que a ele lhe devo a sua conclusão.
Um grande pedido de desculpa à Paula, pelo tempo que não tive para estar com ela,
pelos fins de semana que não existiram, pelas férias que foram adiadas e por tudo mais,
um grande obrigado.
Aos meus pais e irmãos pelo apoio que sempre disponibilizaram, pelos sacrifícios
que fizeram e o encorajamento que me deram para prosseguir com os meus estudos, a
eles dedico esta tese.
Pelo tempo que não tive, pela disponibilidade que não demonstrei, pelo apoio que
não dei, aqui ficam as minhas desculpas a todos aqueles que fazem parte da minha
família, amigos e colegas, e que merecem todo o meu respeito e admiração. A todos
eles os meus mais sinceros agradecimentos e uma promessa de que tentarei de alguma
forma compensar os momentos em que não estive presente.
Índice
1 INTRODUÇÃO ................................................................................................................................ 1
1.1 OBJECTIVOS .................................................................................................................................. 2
1.2 PANORAMA ACTUAL ..................................................................................................................... 2
1.3 ESTRUTURA DA TESE .................................................................................................................... 4
2 ESTRUTURA DE UM COMPILADOR ........................................................................................ 5
2.1 FRONT-END .................................................................................................................................. 6
2.1.1 Análise --------------------------------------------------------------------------------------------------7
2.1.2 Síntese --------------------------------------------------------------------------------------------------8
2.1.3 Tratamento dos Identificadores ---------------------------------------------------------------------9
2.1.4 Tratamento de Erros----------------------------------------------------------------------------------9
2.1.5 Optimização -------------------------------------------------------------------------------------------9
2.2 INTERFACE ENTRE FRONT-END E BACK-END ............................................................................. 10
2.2.1 Geração do Código Intermédio ------------------------------------------------------------------- 17
2.3 BACK-END.................................................................................................................................. 23
2.3.1 Considerações sobre a Geração de Código ----------------------------------------------------- 23
2.3.2 Tratamento das Expressões da R.I. --------------------------------------------------------------- 32
2.3.3 Alocação de Registos ------------------------------------------------------------------------------- 39
2.3.4 Geração do Código Máquina --------------------------------------------------------------------- 45
3 BEDS – SISTEMA DE APOIO AO DESENVOLVIMENTO DE BACK-ENDS ...................... 47
3.1 O BACK-END DEVELOPMENT SYSTEM ....................................................................................... 50
3.2 COMPILADOR COM ALOCAÇÃO LOCAL ........................................................................................ 56
3.3 COMPILADOR COM ALOCAÇÃO GLOBAL...................................................................................... 57
4 MY INTERMEDIATE REPRESENTATION ............................................................................. 61
4.1 ESTRUTURAÇÃO DA MIR ............................................................................................................ 61
4.2 SINGLE STATIC ASSIGNMENT ..................................................................................................... 62
4.3 CLASSES DA MIR ....................................................................................................................... 64
4.3.1 Classe Genérica ------------------------------------------------------------------------------------- 64
4.3.2 Classe Expressions --------------------------------------------------------------------------------- 66
4.3.3 Classe DataTransfer -------------------------------------------------------------------------------- 67
4.3.4 Classe FlowNode ----------------------------------------------------------------------------------- 74
5 OPTIMIZAÇÃO............................................................................................................................. 79
5.1 ANÁLISE DO FLUXO DE CONTROLO ............................................................................................. 79
5.1.1 Árvore do fluxo de controlo ----------------------------------------------------------------------- 81
5.1.2 Análise de intervalos ------------------------------------------------------------------------------- 81
5.1.3 Análise Estrutural ----------------------------------------------------------------------------------- 83
5.2 ANÁLISE DO FLUXO DE DADOS.................................................................................................... 87
5.2.1 Listas de definições --------------------------------------------------------------------------------- 87
5.2.2 DU-Chain e UD-Chain ----------------------------------------------------------------------------- 89
5.2.3 Iterative Data Flow Analysis ---------------------------------------------------------------------- 89
5.3 SINGLE STATIC ASSIGNMENT – IMPLEMENTAÇÃO ...................................................................... 96
5.3.1 Dominance Frontiers ------------------------------------------------------------------------------- 96
5.3.2 Inserção das Funções Φ(...) ----------------------------------------------------------------------100
5.3.3 Actualização das referências ---------------------------------------------------------------------101
5.3.4 De SSA para a Forma Normal -------------------------------------------------------------------101
5.4 OPTIMIZAÇÕES INTERMÉDIAS ................................................................................................... 103
5.5 OPTIMIZAÇÕES DO CÓDIGO FINAL ............................................................................................ 107
Lista de Figuras
FIG. 2.1 – UTILIZAÇÃO DE VÁRIOS FRONT-ENDS SOBRE UM BACK-END. ------------------------------------------- 5
FIG. 2.2 – UTILIZAÇÃO DE UM FRONT-END SOBRE VÁRIOS BACK-ENDS. ------------------------------------------- 6
FIG. 2.3 – ESTRUTURA DE UM COMPILADOR. ------------------------------------------------------------------------------- 7
FIG. 2.4 – ÁRVORE DE SINTAXE DA EQ. 2.2. -------------------------------------------------------------------------------- 11
FIG. 2.5 – PROCESSAMENTO DE EXPRESSÕES POSTFIX NUMA MÁQUINA DE STACK. ------------------------- 12
FIG. 2.6 – REPRESENTAÇÃO EM ÁRVORE E EM DAG DA EXPRESSÃO A=(B+3)*(B+3). ------------------------- 14
FIG. 2.7 – DIAGRAMA DE FLUXO DE DADOS DO EXEMPLO 2.1. ------------------------------------------------------ 16
FIG. 2.8 – REPRESENTAÇÃO DA ÁRVORE DE SINTAXE E ÁRVORES INTERMÉDIAS DA EQ. 2.6. --------------- 18
FIG. 2.9 – EXEMPLO DA ESTRUTURAÇÃO DO CÓDIGO PARA EXPRESSÕES TIPO A DA EQ. 2.8. ------------- 20
FIG. 2.10 – CONVERSÃO DE UMA OPERAÇÃO DE TRÊS OPERANDOS EM DUAS DE DOIS
OPERANDOS. --------------------------------------------------------------------------------------------------------- 21
FIG. 2.11 – DECOMPOSIÇÃO DA ÁRVORE BINÁRIA NUMA FLORESTA DE ÁRVORES. --------------------------- 21
FIG. 2.12 – ESTRUTURA DAS ÁRVORES DE REPRESENTAÇÃO INTERMÉDIA PARA UMA FUNÇÃO. ---------- 22
FIG. 2.13 – ESTRUTURA DO REGISTO DE ACTIVAÇÃO. ------------------------------------------------------------------ 25
FIG. 2.14 – ORGANIZAÇÃO DA MEMÓRIA DE EXECUÇÃO DE UM PROGRAMA, SEGUNDO AS
DIFERENTES ESTRATÉGIAS DE ALOCAÇÃO.----------------------------------------------------------------- 26
FIG. 2.15 – EXEMPLO DA ORGANIZAÇÃO DOS REGISTOS DE ACTIVAÇÃO NA STACK. ------------------------- 27
FIG. 2.16 – REPRESENTAÇÃO DA ESTRUTURA DO COMPILADOR YC.----------------------------------------------- 33
FIG. 2.17 – REPRESENTAÇÃO DA ÁRVORE DA EQ. 2.10, COM OS RESPECTIVOS VECTORES DE
CUSTO. ----------------------------------------------------------------------------------------------------------------- 37
FIG. 2.18 – ESTRUTURA DE UM SISTEMA DE ALOCAÇÃO DE REGISTOS.------------------------------------------- 40
FIG. 3.1 – DIAGRAMA ESTRUTURAL DO BEDS ----------------------------------------------------------------------------- 51
FIG. 3.2 – MODELO DE COMPILADOR COM ALOCAÇÃO LOCAL.----------------------------------------------------- 55
FIG. 3.3 – MODELO DE UM COMPILADOR COM ALOCAÇÃO GLOBAL. --------------------------------------------- 58
FIG. 4.1 – CLASSE ASSIGNMENT. ---------------------------------------------------------------------------------------------- 69
FIG. 4.2 – CLASSES ATTRIBASSIGNMENT E ASGNEXPRESSION. ------------------------------------------------------- 70
FIG. 4.3 – CLASSES LABELASSIGNMENT E LABEL. ------------------------------------------------------------------------ 71
FIG. 4.4 – CLASSES JUMPASSIGNMENT E JUMP. -------------------------------------------------------------------------- 71
FIG. 4.5 – CLASSES CONDJUMPASSIGNMENT, CONDJUMP E ARGEXPRESSION.--------------------------------- 72
FIG. 4.6 – CLASSES CALLASSIGNMENT E CALL. --------------------------------------------------------------------------- 73
FIG. 4.7 – CLASSES RETURNASSIGNMENT E RETURN. ------------------------------------------------------------------- 74
FIG. 4.8 – CLASSE JUMPNODE. ------------------------------------------------------------------------------------------------ 75
FIG. 5.1 – EXEMPLO DE UM CFG E DA RESPECTIVA LISTA DE ADJACÊNCIAS. ---------------------------------- 80
FIG. 5.2 – REPRESENTAÇÃO DA LISTA DE ADJACÊNCIAS DOS 3 PRIMEIROS NODOS DO GRAFO DA
FIG. 5.1. ---------------------------------------------------------------------------------------------------------------- 80
FIG. 5.3 – REDUÇÃO DO GRAFO DA FIG. 5.1, SEGUNDO A ANÁLISE T1-T2. --------------------------------------- 82
FIG. 5.4 – ÁRVORE DE CONTROLO RESULTANTE DA ANÁLISE T1-T2 PARA O GRAFO DA FIG. 5.1.---------- 83
FIG. 5.5 – EXEMPLOS DE REGIÕES ACÍCLICAS. --------------------------------------------------------------------------- 84
FIG. 5.6 – EXEMPLOS DE REGIÕES CÍCLICAS. ----------------------------------------------------------------------------- 85
FIG. 5.7 – EXEMPLOS DE POSSÍVEIS REGIÕES IMPRÓPRIAS. --------------------------------------------------------- 85
FIG. 5.8 – ORDENAÇÃO PREORDER DO GRAFO. -------------------------------------------------------------------------- 85
FIG. 5.9 – RESULTADO DA PRIMEIRA ITERAÇÃO DA ANÁLISE ESTRUTURAL. ------------------------------------ 86
FIG. 5.10 – RESTANTES FASES DO PROCESSO DE REDUÇÃO DO GRAFO. ----------------------------------------- 86
FIG. 5.11 – ÁRVORE DE CONTROLO DO GRAFO DA FIG. 5.1. ---------------------------------------------------------- 87
FIG. 5.12 – EXEMPLO DA REPRESENTAÇÃO MIR DA EXPRESSÃO A = A+1.---------------------------------------- 88
FIG. 5.13 – ALGORITMO PARA DETERMINAR O ALCANCE DAS VARIÁVEIS. --------------------------------------- 94
FIG. 5.14 – ALGORITMO PARA DETERMINAR O PERÍODO DE VIDA DAS VARIÁVEIS. --------------------------- 95
FIG. 5.15 – ALGORITMO PARA DETERMINAR AS DF ATRAVÉS DA ÁRVORE DE DOMINADORES. ------------ 98
FIG. 5.16 – ALGORITMO PARA DETERMINAR AS DF SEM A ÁRVORE DE DOMINADORES. --------------------- 99
FIG. 5.17 – ALGORITMO PARA INSERIR AS FUNÇÕES Φ(...). ---------------------------------------------------------- 100
FIG. 5.18 – EXEMPLO DE UMA FUNÇÃO Φ(...) APÓS O PROCESSO DE ALOCAÇÃO. ---------------------------- 102
FIG. 5.19 – EXEMPLO DE COMO SE PODE RESOLVER A ALOCAÇÃO PARA AS FUNÇÕES Φ(...). ------------ 102
FIG. 6.1 – REPRESENTAÇÃO ESQUEMÁTICA DA LISTA DE ADJACÊNCIAS. --------------------------------------- 113
FIG. 6.2 – ESTRUTURA DA MATRIZ DE INTERFERÊNCIAS. ------------------------------------------------------------ 114
FIG. 6.3 – EXEMPLO COM DUAS VARIÁVEIS SIMULTANEAMENTE VIVAS, MAS QUE
APARENTEMENTE NÃO INTERFEREM UMA COM A OUTRA. -------------------------------------------- 115
FIG. 6.4 – EXEMPLO DE COMO É POSSÍVEL COLORIR UM GRAFO COM N=3 E TODOS OS K ≥ 3. --------- 118
FIG. 6.5 – FASES DO PROCESSO DE COLORAÇÃO DO GRAFO. ------------------------------------------------------ 118
FIG. 7.1 – PADRÕES E MÁQUINA DE ESTADOS DO TOP-DOWN PATTERN MATCHING. ----------------------- 127
FIG. 7.2 – EXEMPLO DE UMA ÁRVORE DE EXPRESSÕES APÓS O LABELLING.---------------------------------- 130
FIG. 7.3 – REPRESENTAÇÃO DA TABELA DE TRANSIÇÕES DO OPERADOR ADD. ------------------------------ 132
FIG. 7.4 – ESTRUTURA DA FUNÇÃO DE LABELLING. ------------------------------------------------------------------- 132
FIG. 7.5 – ALGORITMO DA FUNÇÃO PRINCIPAL, PARA GERAÇÃO DO BURS. ----------------------------------- 133
FIG. 7.6 – ALGORITMO DE NORMALIZAÇÃO DE CUSTOS. ------------------------------------------------------------ 134
FIG. 7.7 – ALGORITMO PARA DETERMINAR OS ESTADOS DO SÍMBOLOS TERMINAIS. ------------------------ 134
FIG. 7.8 – ALGORITMO PARA APLICAR AS REGRAS EM CADEIA. ---------------------------------------------------- 135
FIG. 7.9 – ALGORITMO PARA DETERMINAR OS ESTADOS DOS NÃO-TERMINAIS. ------------------------------ 136
FIG. 7.10 – ALGORITMO DE CHAIN RULE TRIMMING. ----------------------------------------------------------------- 138
FIG. 7.11 – COMPACTAÇÃO DAS TABELAS, RECORRENDO A VECTORES DE INDEXAÇÃO. ------------------ 139
FIG. 7.12 – ESQUEMA DE DECOMPOSIÇÃO DE TABELAS. ------------------------------------------------------------ 140
FIG. 7.13 – ESQUEMA DA ORGANIZAÇÃO DOS MAPAS DE INDEXAÇÃO.------------------------------------------ 141
FIG. 7.14 – MACROS PARA DETERMINAR O LABELLING. -------------------------------------------------------------- 141
FIG. 8.1 – MODELO COM OS VÁRIOS INTERVENIENTES NO DESENVOLVIMENTO DE UM
COMPILADOR. ------------------------------------------------------------------------------------------------------ 148
FIG. 8.2 – SEQUÊNCIA DAS OPERAÇÕES PARA UM BACK-END COM ALOCAÇÃO LOCAL. ------------------- 163
Lista de Abreviaturas
1 Introdução
linguagens em diversas fases com funções bem definidas, a saber: análise, geração do
código intermédio e geração de código final.
O passo seguinte na evolução desta área da informática consistiu em elevar o nível
de concepção, desenvolvendo programas capazes de eles próprios gerarem
automaticamente rotinas para a execução de algumas das fases típicas de um
processador de linguagens. Este tipo de programas passou-se a designar por Gerador de
Processadores de Linguagens.
Muitas destas tarefas foram alvo de intensos estudos, atingindo actualmente níveis de
automatização muito satisfatórios, permitindo a sua geração de modo eficiente e rápido,
através de uma simples especificação das suas características.
Infelizmente a automatização das diversas fases não foi uniforme, talvez pelas
dificuldades encontradas, ou por dependerem de factores externos de grande
variabilidade.
1.1 Objectivos
1
Todo o pacote de software do LCC é freeware.
2
GCC – GNU C Compiler.
3
FSF – Free Sotware Foundation, Inc.
2 Estrutura de um Compilador
Back End
Alfa
Front End
C
2.1 Front-End
2.1.1 Análise
Analisa Léxica
Sempre que o código fonte se encontra representado sob a forma de um texto, é
necessário proceder ao reconhecimento dos símbolos que o compõem. É exactamente
esta a função da primeira fase, a do analisador léxico ou scanner, que considera o texto
fonte como uma stream de caracteres, a qual é processada da esquerda para a direita,
procedendo à eliminação de caracteres nulos, tal como espaços e caracteres do
tabulador, bem como de comentários, agrupando os restantes de forma a obter símbolos,
designados por tokens.
Código Fonte
Caracteres
Análise Léxica
Tokens F
R
Gestão da Tabela O
de Símbolos N
Análise Sintáctica
T
Árvore de
Tratamento de Sintaxe E
Erros N
D
Análise Semântica
Optimização de
Código Árvore
Decorada
Gerador de Código
Intermédio
Representação
Intermédia
B
Gerador de Código A
C
Código Binário K
ou Assembly E
N
Código Final D
Análise Sintáctica
Na fase seguinte, o analisador sintáctico ou parser, requisita os tokens ao analisador
léxico agrupando-os sob a forma de uma árvore de sintaxe, de acordo com a gramática
da linguagem em causa. Essa árvore, que traduz a estrutura do texto fonte, indica quais
as regras de derivação da gramática, que foram usadas na construção da frase,
contribuindo assim para se conhecer o seu significado.
Análise Semântica
Na terceira fase, encontra-se o analisador semântico. A cada símbolo detectado no
código fonte está associado um conjunto de atributos, que podem representar diversos
tipos de informação e cujo objectivo é fornecer os conhecimentos necessários à
determinação do significado exacto desse texto fonte ( o que é determinante para se
fazer a geração de código).
Conhecendo o conjunto de regras que permitem determinar o valor dos atributos e
tomando em consideração o valor associado aos tokens, o analisador semântico procede
ao cálculo do significado exacto de cada símbolo gramatical.
O processo consiste em pegar na árvore de sintaxe abstracta e decorá-la com os
atributos, calculando o seu valor e testando se estes cumprem às condições de contexto.
2.1.2 Síntese
2.1.5 Optimização
Como se disse atrás, a escolha duma boa representação intermédia para exprimir o
significado do texto fonte (reconhecido na fase de análise) é fundamental para a
implementação dum compilador.
Assim, a representação intermédia deve ser facilmente adaptável, quer ao front-end
ou ao back-end; deve permitir representar qualquer tipo de estrutura que possa surgir no
código fonte, quer esta seja de dados ou de controlo; e ser facilmente manipulável pelos
procedimentos que se executam a este nível de representação.
A notação postfix, three-address code, árvores binárias, grafos e a linguagem de
transferência de registos (RTL) são algumas das formas utilizadas para a representação
intermédia.
Notação Postfix
A representação em notação postfix obtém-se a partir da “linearização” da árvore de
sintaxe, convertendo-a numa representação recursiva do tipo:
a b 3 + c * = Eq. 2.3
Este tipo de representação é ideal para o caso dos interpretadores, em que o código
intermédio é executado por máquinas virtuais baseadas em stack; o front-end vai
passando os elementos das expressões em postfix, da esquerda para a direita ao
interpretador, os quais são inseridos na stack, através de instruções de push. No entanto,
sempre que se detecta um operador (opn), este ao invés de ser inserido na stack, é
executado de imediato. A utilização da notação postfix garante que os operandos
necessários à execução de opn se encontram no topo da stack, bastando para tal retira-
los através de simples operações de pop.
Após a execução de opn, o resultado é inserido na stack, servindo de operando para a
instrução seguinte. O processo repete-se até se executar a última operação da expressão.
=
a *
+ c
b 3
3 c (b+3)*c
b b+3 a
a a
x := y op z Eq. 2.4
t1 := b + 3
a := t1 * c
x := op y //Operador unário.
x := y //Atribuição de y a x.
goto l //Salto incondicional para label l.
if x cond y goto label l //Salto condicional para label l,
// se (x cond y) é verdadeiro.
Árvores e DAG’s
A representação em forma de árvore binária, passa por considerar que cada nodo
interno da árvore representa um operador, cujos operandos resultam das operações dos
nodos descendentes.
A árvore de representação intermédia possui uma estrutura semelhante à da árvore de
sintaxe, diferindo no entanto no conteúdo, o qual traduz o conhecimento obtido pela
análise semântica e a pela própria sintaxe da representação intermédia.
Neste caso a expressão da Eq. 2.2, corresponde à árvore binária da Eq. 2.5.
a * a *
+ + +
b 3 b 3 b 3
Exemplo 2.1
No exemplo que se apresenta abaixo, onde se faz a tradução de um bloco de
código em linguagem C para RTL, pode-se confirmar o detalhe de uma descrição
feita com este tipo de representação.
Código C RTL
r[1] = &b //Carrega o endereço de b
if( b>max) r[2] = *r[1] //Carrega o valor de b
max = b; r[3] = &max //Carrega o endereço de max
else r[4] = *r[3] //Carrega o valor de max
max = a; r[2] ≤ r[4] ↑ L1 //Se b ≤ max salta L1
r[5] = &max //Carrega o endereço de max
r[6] = &b //Carrega o endereço de b
r[7] = *r[6] //Carrega o valor de b
*r[5] = r[7] //Carrega max com o valor de b
↑ L2 //Salto incondicional para L2
L1: r[8] = &max //Carrega o endereço de max
r[9] = &a //Carrega o endereço de a
r[10] = *r[9] //Carrega o valor de a
*r[8] = r[10] //Carrega max com o valor de a
L2: //Fim da função
♦
r[1] = &b
r[2] = *r [1]
r[3] = &max
r[4] = * r[3]
RTLJumpNode
N
r[2]<r[4]
RTLConditionNode
RTLJumpNode RTLJumpNode
RTLReturnNode
Tratamento de Tipos
Na generalidade dos processadores as instruções realizam-se sobre o mesmo tipo de
operandos, por exemplo, a adição é feita sobre valores inteiros ou reais, mas raramente
sobre um inteiro e um real. É função do analisador semântico detectar se os operandos
são compatíveis entre si, cabe no entanto ao GCI inserir na representação intermédia os
mecanismos necessários à conversão dos operandos, bem como decidir o tipo específico
de operador a utilizar.
Todos os símbolos terminais, que sejam identificadores, possuem um tipo
estabelecido implicitamente através do formato com que surgem no texto fonte ou então
explicitamente através das declarações.
Depois para cada operação, é necessário verificar se todos os operandos possuem o
mesmo tipo ou se são compatíveis. Se tal não acontecer é fundamental proceder à
conversão para um tipo comum, o qual também representará o tipo do resultado da
operação.
O processo de converter os operandos para um mesmo tipo comum, implica
normalmente a inserção de novos nodos na árvore de sintaxe, que representem as
operações de conversão.
Exemplo 2.2
Este exemplo demonstra como se processa o tratamento de tipos, para a situação
em que se pretende somar uma constante e uma variável, ambos do tipo inteiro, e
depois atribuir o resultado a uma variável do tipo real.
Código em C
int a;
float b;
ASGN
b ADD
a 10
ASGNF ASGNF
b ADDF b CIF
a 10 a 10
type: int type: int type: int type: int
Para que seja possível realizar a operação da Eq. 2.6, é necessário converter a
constante de valor 10 e a variável a para valores do tipo real (CIF) e aplicar o
operador de adição para reais (ADDF), ou então, aplicar o operador de adição para
inteiros (ADDI) sobre os dois operandos e converter o resultado para o tipo real. Em
ambos os casos é ainda necessário realizar a atribuição da adição à variável b
(ASGNF). A Fig. 2.8 representa a árvore de sintaxe e as árvores de representação
intermédia para as duas soluções anteriores.
♦
Visto que as expressões que utilizam operadores relacionais, como as da Eq. 2.11,
têm como resultado verdadeiro ou falso, que são conceitos abstractos para o GCI, é
necessário que este resolva as expressões de forma a obter um resultado numérico
possível de ser quantificado. Na prática, esta operação consiste em testar se a expressão
b < c é verdadeira, e nesse caso, atribuir à variável a o respectivo valor numérico
convencionado para representar o valor lógico verdadeiro, procedendo-se de forma
semelhante para o caso da expressão ser falsa. Como exemplo, a Eq. 2.11 seria reescrita
segundo a instrução condicional da Eq. 2.12.
Uma situação mais complexa ocorre quando a expressão condicional é composta por
diversas sub-expressões, relacionadas por operadores do tipo or ou and. Nestas
situações é necessário hierarquizar a sequência das operações e utilizar algumas
optimizações que aproveitando as propriedades algébricas destes operadores,
simplifiquem as expressões.
Exemplo 2.3
A Eq. 2.13 permite exemplificar o tratamento deste tipo de expressões.
De notar que no caso de b ser inferior a 20, já é condição suficiente para que a
seja verdadeiro, caso contrário é necessário determinar o valor da sub-expressão b >
40.
Uma vez certificado que não ocorrem conflitos na representação dos resultados, pode
então o GCI tratar de resolver as estruturas de controlo. Apenas como exemplo analise-
se o comportamento do GCI para a Eq. 2.8.
E.jump:
//Código correspondente ao símbolo A2
Salto incondicional para
a operação posterior
S.next: //Código posterior à estrutura de controlo
Fig. 2.9 – Exemplo da estruturação do código para expressões tipo a da Eq. 2.8.
Para este tipo de expressão pode-se convencionar que caso a condição resulte no
valor lógico verdadeiro, então a execução continua através de A1 e uma vez concluída a
execução deste bloco, prossegue na instrução seguinte à expressão condicional. Caso a
condição seja falsa, então a execução continua no princípio do bloco de código formado
por A2.
OPCOND OPCOND
Acção1
Acção1 Acção2
Fig. 2.10 – Conversão de uma operação de três operandos em duas de dois operandos.
Para tal, e uma vez que o GCI é implementado utilizando gramáticas de atributos,
associa-se ao símbolo E (que representa a expressão condicional) um atributo (jump) no
qual se armazena a posição onde o código continua a ser executado caso a expressão
assuma determinado valor lógico (neste caso o valor falso). É ainda necessário associar
ao símbolo S um segundo atributo (next) que identifica a instrução seguinte à expressão
condicional, o qual permite conhecer a posição onde continua a execução do código
após a conclusão de A1. A Fig. 2.9, representa a organização da sequência do código que
o GCI deve produzir para este tipo de expressão.
Se E Falso
Se E Verdadeiro
OPACÇÃO1 OPACÇÃO2
(LJUMP)
Tratamento de funções
O tratamento de chamada e retorno de funções é uma das tarefas de maior
complexidade com que o GCI se depara. Isto porque para invocar uma função, é
necessário guardar o contexto de execução da função origem, passar os argumentos da
função invocada, guardar o endereço de regresso e “saltar” para a posição inicial da
função. No fim da função, é ainda necessário guardar o seu resultado, restaurar o
contexto de execução da função origem e “saltar” para o endereço de regresso.
É função do GCI passar através da representação intermédia este conjunto de tarefas
ao back-end, o que nem sempre é fácil de fazer devido às limitações da própria
representação intermédia.
OPAUX resultado
ARG f
Lista das árvores da função f
... RET ...
an ARG
resultado
... ARG
a1
Fig. 2.12 – Estrutura das árvores de representação intermédia para uma função.
É imprescindível identificar duas fases bem distintas: uma primeira que corresponde
à invocação da função, onde é necessário que a árvore represente o endereço e os
A segunda lista (da função invocada) termina com a operação de retorno (RET), a
qual possui pelo menos um operando, que é o valor a devolver. Pode no entanto, existir
um segundo operando para representar o endereço (referência) da função origem.
2.3 Back-End
Para além destas fases, cabe também ao back-end tratar de organizar o espaço de
memória para a execução do programa ou então providenciar os mecanismos para tal.
É ainda habitual existir uma fase de optimização, normalmente designada por
peephole optimization, que tanto se pode colocar antes ou depois da selecção das
instruções. Esta tarefa é apresentada na secção 5.5.
Nesta secção e após uma breve descrição das diversas representações do código final,
apresentam-se algumas das soluções utilizadas para a alocação do espaço de memória
necessário à execução do programa, explicando o tratamento realizado pelo gerador de
código final sobre a informação contida na tabela de símbolos. A secção continua com a
descrição do tratamento das expressões da representação intermédia, com a alocação
dos registos e termina com uma pequena abordagem à geração de código máquina.
determine serem úteis à sua execução. No caso das sub-rotinas, serve ainda para
armazenar os parâmetros de entrada, os resultados a devolver pelas funções, a
informação de status da máquina (tal como o valor dos diversos registos e o endereço de
retorno) e, eventualmente, alguns apontadores para outros registos de activação
necessários à execução da sub-rotina (por exemplo o registo de activação da função
origem). A Fig. 2.13 apresenta um exemplo da estrutura de um registo de activação.
Valor a
Devolver
Endereço de
Retorno
Apontadores para
Registos Externos
Parâmetros
Variáveis
Locais
Variáveis
Temporárias
Estratégias de Alocação
São duas as principais estratégias de alocação do espaço para os registos de
activação, uma designada por alocação estática e outra por alocação de stack.
A alocação estática reserva o espaço em memória para os registos de activação
durante a compilação, mais concretamente durante a geração de código. Tal solução, só
é possível se as variáveis utilizadas são do tipo estático, condição essencial para se
determinar o seu tamanho no momento da geração do código, de forma a que o
compilador conheça o montante de memória a reservar para cada um dos registos de
activação.
Desta forma, a estrutura exigida à organização dum programa em execução, consiste
num bloco de código e num bloco para as variáveis estáticas, tais como os próprios
registos de activação. Esta estrutura encontra-se representada na Fig. 2.14 a).
A alocação por stack, reserva o espaço necessário aos registos de activação em run
time, ou seja durante a execução do programa e não durante a compilação. Para tal,
utiliza uma stack, onde armazena os registos de activação conforme as respectivas
rotinas (funções, procedimentos ou blocos de código) são invocadas. No fim da
execução de cada uma, o respectivo registo é removido da stack.
Neste tipo de alocação a memória organiza-se em três blocos, um para o código das
instruções, um para as variáveis estáticas, como por exemplo variáveis globais e um
terceiro bloco onde se aloca dinamicamente o espaço para os registos de activação da
stack. A estrutura encontra-se representada na Fig. 2.14 b).
Stack Stack
Heap
a) b) c)
É exactamente nesta última vantagem, que reside a sua principal desvantagem. Como
existe apenas um único registo para cada rotina, torna impraticável a utilização de
recursividade. A tentativa de invocar uma rotina que já se encontre em execução,
provoca a alteração dos campos do registo de activação, como é o caso do endereço de
retorno ou o conteúdo dos registos, danificando assim a informação referente à primeira
instância da rotina, causando danos irreparáveis na execução do próprio programa.
No caso da alocação por stack este problema já não se verifica, pois sempre que se
invoca uma rotina, cria-se um novo registo de activação para armazenar a informação da
nova instância. Desta forma existem tantos registos quantas as funções em execução.
A Fig. 2.15, apresenta um extracto de código em linguagem C, organizado segundo
uma estrutura em árvore, em que a root representa o corpo principal do programa, (ex:
main( ) em C), e onde cada nodo descendente representa, da esquerda para a direita, a
sequência das funções invocadas a partir do corpo principal.
Apesar da alocação por stack permitir trabalhar com variáveis do tipo dinâmico, é
fundamental para isso, ter em conta determinados aspectos. Como a stack, é o único
meio para passar e armazenar a informação necessária à execução do programa, também
é necessário que lá fiquem armazenadas as variáveis dinâmicas. No entanto, estas não
podem simplesmente ser guardadas nos registos de activação, pois nesse caso não seria
possível definir uma estrutura de tamanho fixo, o que por si só, complicaria todo o
sistema de referências. A solução encontrada consiste em guardar nos registos de
activação apenas os endereços, ficando as variáveis propriamente ditas, colocadas na
stack mas fora dos registos de activação. Os endereços utilizados são relativos à posição
que o registo de activação ocupa dentro da stack.
void funct2( )
{ main( )
...
funct21( );
funct22( );
...
} funct1( ) funct2( ) funct3( )
void main( )
{
...
funct1( ); funct21( ) funct22( )
funct2( );
funct3( );
...
} RA RA
funct21( ) funct22( )
RA RA RA RA RA
funct1( ) funct2( ) funct2( ) funct2( ) Funct3( )
RA RA RA RA RA
main( ) main( ) main( ) main( ) main( )
operandos podem também servir para colocar o resultado. No entanto, nem todas as
instruções obedecem a esta estrutura. Apresentam-se de seguida alguns exemplos
ilustrativos das diversas instruções:
Operador Descrição
NOP Operação Nula
Em que op identifica a operação, arg1 e arg2 são operandos e result pode ser um
terceiro operando ou resultado.
Para os exemplos que se seguem, convencionou-se que cada um dos campos (op,
arg1, arg2 e result) é representado por 1 byte, pelo que cada instrução tem como
comprimento máximo 4 bytes. Sendo, no entanto, o operador (op) o único campo
obrigatório.
A Unidade Central de Processamento (CPU), através do código op, não só determina
a operação a realizar, como o número de argumentos e o tipo de endereçamento
utilizado por cada um.
É possível que, cada um dos operandos utilize mais do que um modo de
endereçamento [Gilm95]. Os mais vulgares são:
Endereçamento Herdado
Endereçamento Imediato
Endereçamento Directo
Endereçamento Registo Directo e Indirecto
Endereçamento Indexado
Endereçamento Relativo
Em que os y’s servem para identificar a operação ADD e os x’s o registo a utilizar.
Os bits z’s representam o operando arg2.
O Endereçamento Indexado é representado na forma de base + offset (ex: 4(R0) ou
@R0 + 4), em que normalmente a base consiste num registo e o offset num valor
imediato. A base contém um endereço absoluto e o offset indica uma posição relativa à
base. Este tipo de endereçamento necessita de mais um byte para o offset.
O Endereçamento Relativo é um caso específico do endereçamento indexado, em
que o registo utilizado para a base é o program counter.
Nem todas as arquitecturas utilizam todos estes modos de endereçamento, no entanto
as que o fazem normalmente estão incluídas na família de processadores CISC
(Complex Instruction Set Computer), os quais caracterizam-se não só por utilizar
diversas formas de endereçamento, como também instruções com tamanho variável e
recorrerem a registos específicos para implementar determinado tipo de operações.
Já os processadores do tipo RISC (Reduced Instruction Set Computer), utilizam
essencialmente instruções com endereçamento por registo ou endereçamento imediato,
com tamanho fixo e em que todos os registos são de utilização geral. Mas como é
inevitável ter que se carregar e despejar o conteúdo destes, de e para memória, existe
um número muito limitado de instruções que podem referenciar posições de memória e
que são normalmente designadas por instruções de LOAD e STORE.
Não se pretende aqui, discutir as vantagens e desvantagens de cada uma destas
filosofias de concepção. Parte-se do princípio que ambas existem e que ambas
necessitam de compiladores. Interessa apenas apurar, quais os aspectos a ter em
consideração no desenvolvimento destes para cada uma das arquitecturas. Convém no
entanto perceber que apesar de ambas as arquitecturas, necessitarem de seleccionar as
instruções e alocar os registos, no caso dos CISC’s, as tarefas são bastante mais
complicadas, não só porque existem diversas opções para uma mesma instrução, como
determinadas instruções utilizam registos específicos. No caso dos RISC, as tarefas são
muito mais simples, porque normalmente só existe uma representação de cada instrução
e como os registos são todos de uso geral, o número de restrições que se coloca na
alocação é bastante inferior.
Em contrapartida, a maior parte das instruções de um CISC, podem utilizar
operandos directamente da memória, enquanto nos RISCs é necessário carregar
previamente os valores nos registos, através de uma operação de LOAD.
Outro aspecto importante na escolha das instruções, é o seu tempo de execução, o
qual depende em grande parte do tipo de endereçamento utilizado pelos operandos.
Assim as instruções mais rápidas são as que utilizam operandos com endereçamento
herdado ou endereçamento por registo, uma vez que o CPU com um único byte (op)
identifica pelo menos um dos operandos e a instrução a executar. Para além disso, estes
dois modos de endereçamento utilizam registos, os quais, como fazem parte da estrutura
interna do CPU, possuem tempos de acesso inferiores aos necessários para aceder a
qualquer valor da memória de dados (endereçamento directo) ou mesmo da memória de
código (endereçamento imediato).
Exemplo 2.4
Este exemplo demonstra como se processa toda esta situação, apresentando o
código gerado para a função origem.
Instruções Comentários
Exemplo 2.5
No caso da função origem, é gerado o seguinte código, onde a constante TRegAct
representa o tamanho do registo de activação:
Instruções Comentários
Soluções específicas
Os primeiros modelos de compiladores consideravam apenas quatro fases, a léxica, a
sintáctica, a semântica e a geração de código. Era da responsabilidade desta última, a
gestão dos registos, optimização do código e a selecção de instruções, tudo tratado
como se fosse um único processo. Com este tipo de organização, não é de admirar que
se considerasse esta, uma das fases mais complicadas de um compilador.
É dentro deste contexto que surge uma das soluções que está na base de alguns dos
melhores compiladores actuais. Apareceu pela primeira vez no YC (Y compiler)
[DF84a, DF84b], que teve por base o PO [DF80, GF88]. Trata-se como tal, de um
Representação
Intermédia
Expander
Cacher
Pseudo
Instruções
Combiner
Assigner
Código
Final
Exemplo 2.6
Considere que determinada máquina suporta as operações de Subtracção (SUBB)
e Atribuição/Load/Store (MOV), através das seguintes instruções (os respectivos
custos encontram-se à direita):
r[7] = &b
r[8] = * r[7]
a=b-y r[9] = &y
r[10] = * r[9]
r[11] = r[8] – r[10] r[11] = r[4] – r[5] SUBB r[4], r[2] SUBB R1, R0 1
r[12] = &a
*r[12] = r[11] *r[1] = r[11] MOV a, r[4] MOV a, R1 2
TOTAL 10
Há no entanto que ter em atenção, que antes de b ser novamente utilizado como
operando, pode acontecer que faltem registos, podendo nestas circunstâncias a
solução passar por libertar um dos que se encontram em utilização. Caso a escolha
recaia sobre o registo utilizado por b, então perdem-se todos os benefícios potenciais.
Apesar dos custos serem iguais, seria legítimo pensar que o Combiner optasse
pela opção 2, uma vez que o custo da primeira opção é apenas potencial.
No entanto, o Combiner pode também tirar proveito do facto de saber que a
instrução SUBB, obriga a que o operando esquerdo se encontre sempre em registo.
Pelo que caso não se realize a operação de load da variável b durante a primeira
expressão, será forçosamente necessário realizá-la na segunda, o que permite garantir
um custo potencial para a primeira opção de apenas 5 unidades
É possível confirmar pelo código que a seguir se apresenta, que o custo final da
opção 1 é de 10 unidades, em oposição às 11 unidades da opção 2.
As decisões são feitas em run time, em que para tal se associa a cada um dos nodos,
um vector com k+1 elementos, em que k representa o número de registos disponíveis
([0, k]). Na i-ésima posição do vector, encontra-se o custo necessário para se obter uma
solução (para o nodo em causa), utilizando apenas i registos, e na posição zero, o custo
para realizar a operação em memória (sem registos).
Desta forma, o algoritmo começa por determinar os vectores dos nodos terminais, ou
seja, o custo de utilizar directamente o respectivo identificador ou constante, com um ou
mais registos. Depois prossegue através dos nodos intermédios, construindo os
respectivos vectores, com base nas combinações de menor custo, entre as instruções
possíveis de utilizar e os vectores das árvores descendentes. O Exemplo 2.7 ilustra o
funcionamento deste algoritmo.
Exemplo 2.7
Considere a árvore da Eq. 2.16 e um conjunto de instruções com custos e formatos
semelhantes às utilizadas no exemplo da secção anterior (Exemplo 2.6).
a * b + c / ( d - e) Eq. 2.16
+ (-,15,12)
(-,4,4) * / (-,10,7)
a b c - (-,4,4)
(0,2,2) (0,2,2) (0,2,2)
d e
(0,2,2) (0,2,2)
Fig. 2.17 – Representação da árvore da Eq. 2.10, com os respectivos vectores de custo.
Seja V, o vector custo, então o cálculo de V[0], para um qualquer nodo terminal,
consiste no custo de utilizar a respectiva variável directamente de memória. Mas
como por defeito as variáveis já se encontram em memória, então o custo atribuído a
V[0] é de zero. V[1] e V[2] possuem os custos de colocar a variável num registo,
quando existem respectivamente um e dois registos disponíveis.
Para os nodos onde ocorrem as operações de subtracção e de multiplicação, com
um único registo obtém-se um custo de 4 unidades, duas provenientes da sub-árvore
esquerda (para colocar a variável em registo), mais duas da própria instrução e zero
da sub-árvore direita. Com dois registos, o custo passa para 5 unidades, pelo que se
opta por utilizar apenas um único registo.
Para os nodos onde ocorrem as operações de adição e divisão, em que ambos
operandos são registos, o custo de V[1] tem que considerar a operação de converter o
operando direito, de registo para endereço ( 2 unidades), mais o custo da instrução,
num total de 4 unidades. Caso se encontrem dois registos disponíveis o custo é de
apenas uma unidade.
O resultado final da selecção é então o seguinte:
Table-Driven Selector
Uma das primeiras tentativas de desenvolver um selector de instruções
completamente independente das características do processador, foi apresentada por S.
Graham [Graham80], que adapta as soluções utilizadas na análise sintáctica, sobre as
quais já existe perfeito domínio, ao processo de selecção de instruções.
A alocação dos registos é uma das fases de maior importância para a qualidade do
código final, uma vez que um mau processo de alocação pode pôr em causa todo o
esforço realizado pelas outras fases do processo de compilação. Pelo que, mesmo com
os diversos estudos e experiências realizadas nesta área, continua ainda a ser uma das
fases que maiores dificuldades coloca quanto à compreensão e implementação.
RI
pseudo-memória
Allocator
Spilling
RI
pseudo-registos
Splitting
Assigner
Assign
Representação
final
Para uma apresentação mais detalhada deste modelo, há antes que definir a noção de
pseudo-memória e pseudo-registo. A pseudo-memória é a representação atribuída por
defeito às variáveis, através da qual se pretende representar uma qualquer posição que a
variável possa ocupar, quer esta seja em memória, nos registos, ou noutro qualquer sítio.
Os pseudo-registos surgem numa fase posterior, representando as variáveis candidatas
aos registos físicos. Ambas as formas de representação são independentes de qualquer
restrição física do processador ou sistema operativo, e utilizam-se ao nível do front-end
e da representação intermédia.
uma função. O que permite, uma distribuição mais eficiente dos registos, minimizando
o número de operações de spilling, de splitting e de trocas entre registos. As contra
partidas, traduzem-se na complexidade dos algoritmos, uma vez que, um grande número
destes, recorre a elaboradas técnicas de análise, o que se traduz no aumento do tempo de
execução, do tamanho do compilador, etc.
A alocação global é quase sempre um problema NP-Completo, pelo que as soluções
têm sempre por base heurísticas que sem garantirem qualquer tipo de solução óptima,
permitem simplificar substancialmente as soluções.
O packing é uma das estratégias de alocação global onde cada registo físico
representa um pack, cuja dimensão é o período de execução do programa. A ideia base
consiste em preencher cada pack (registo ao longo do tempo), mas de forma a que não
ocorra sobreposição entre o período de vida útil de cada um dos pseudo-registo. Para tal
é necessário utilizar técnicas de análise do fluxo de dados, de forma a permitir
determinar o período de vida de cada variável.
Trata-se de uma solução genérica de alocação de recursos para a qual existem
diversas implementações. As mais simples limitam-se a atribuir os pseudo-registos aos
packs conforme estes estão disponíveis, adiando a execução das instruções quando não
existem os recursos necessários. O que por motivos relacionados com as dependências
entre dados, pode fazer com que o sistema de alocação caía em ciclo infinito (dead
lock).
Existem implementações mais complexas, que tentam gerir melhor atribuição dos
pseudo-registos aos packs, utilizando para além dos mecanismos de análise do fluxo de
dados, os mecanismos de análise de dependências entre dados, maximizando assim a
ocupação dos pack ao longo do tempo e detectando potenciais situações de ciclo
infinito. Há, no entanto, que ter em atenção a carga computacional deste tipo de
soluções, onde por vezes a utilização de heurísticas, permite simplificar
consideravelmente os algoritmos, sem que para isso degrade significativamente o
sistema de alocação.
Exemplo 2.8
O presente exemplo permite mostrar o funcionamento de um sistema de alocação
global de packing, para a seguinte sequência de instruções:
c=a+b
f=d+e
a=f+g
b=a+c
e=e+b
Como resultado da alocação, comprova-se que são necessários seis registos físicos
para se concluir a geração do código final com sucesso. No entanto nem sempre é
possível utilizar tantos registos como os idealmente necessários, pois por vezes só
está disponível um número restrito de registos.
O seguinte esquema representa o processo de alocação por packing, utilizando
apenas quatro registos, o que implica recorrer a operações de splitting, para concluir
a alocação com êxito.
forma que qualquer referência posterior a uma label seja substituída pelo endereço da
instrução.
O segundo caso é ligeiramente mais complexo, uma vez que as instruções referem
labels que ainda não foram identificadas, pelo que não podem ser imediatamente e
totalmente resolvidas. A solução passa então por gerar o código da instrução,
designadamente o espaço a ocupar pelo endereço da label, sem que no entanto este
contenha qualquer tipo de informação útil. Depois, é necessário manter uma listas com
este tipo de instruções (inacabadas) para que logo que o endereço da respectiva label
seja conhecido possam ser concluídas.
É ainda vulgar existir uma fase, após todo o processo de geração, responsável por
optimizar o código final, tirando partido de situações que só a este nível é que são
detectadas.
Por falta de tempo não foi possível incluir a geração do código máquina, no trabalho
desenvolvido ao longo desta tese de mestrado. Apresenta-se no entanto no capítulo 9
mais alguns detalhes relacionados com esta fase e uma ferramenta desenvolvida com
objectivo de auxiliar a sua construção.
Módulo Front
Optimizer
End
Rotina
Especificação
SSA
Representação
MIR
Data Flow
Analyser
Structural
Global
Analyser
Allocator
BEDS
Tree
Selector
State Instruction
Instruction Table Labelling
Specifiction
Register Local
Register Back End Table Allocator
Specifiction Generator
Register
Instruction Assigner
Mapping
Instruction Code
Table Emiter
Assembly
Fig. 3.1 – Diagrama estrutural do BEDS
De forma resumida o modelo divide-se em duas grandes partes, uma que funciona
com base numa biblioteca, que fornece uma série de rotinas fortemente relacionadas
com a representação intermédia, das quais fazem parte as rotinas para análise de fluxo
de controlo e dados, optimização e alocação global, que serão explicadas nos capítulos 5
e 6; e uma por segunda parte, composta por um sistema de geração e modelação, que a
partir de uma especificação com a informação referente ao processador e da relação
desta informação com as expressões da representação intermédia, permite modelar
determinadas rotinas e gerar alguns dos mecanismos necessários às tarefas de um back-
end, como é o caso do selector de instruções, o sistema de atribuição de registos, ou o
gerador de código final, que são abordados nos capítulos 7 e 8.
A implementação do modelo designou-se por BEDS – Back-End Development
System e à representação intermédia utilizada por este deu-se o nome de MIR – My
Intermediate Representation, a qual segue uma filosofia muito semelhante à da RTL,
mas devidamente adaptada às necessidades das várias fases deste modelo.
A implementação de todo o BEDS incluindo a MIR, foi feita em C++, obedecendo
ao paradigma da programação por objectos. Pelo que a biblioteca disponibilizada por
este não é mais do que um conjunto de classes, sendo a representação intermédia feita
por instanciação dos objectos dessas classes.
Desta forma o modelo obriga que o front-end transforme o código fonte numa
representação MIR. Depois, recorrendo às potencialidades fornecidas pela biblioteca e
pelo sistema gerador que compõem o BEDS, deverá ser possível desenvolver todas as
fases do back-end de um compilador.
Apesar dos processos de optimização não pertencerem às funções de um back-end, o
BEDS toma a responsabilidade de garantir as rotinas de optimização, ou pelo menos os
recursos necessários à sua implementação, pois como já se viu é bastante vantajoso que
estas rotinas sejam desenvolvidas sobre a representação intermédia, visto esta ser
independente da linguagem fonte e das características do processador, permitindo assim
a sua reutilização.
Para além disso, como de certa forma a representação intermédia é imposta, é
certamente agradável para quem pretende utilizar este tipo de sistemas, que encontre
implementado o maior número possível de mecanismos auxiliares; além de que, grande
parte desses mecanismos são necessários às fases obrigatórias do back-end, como é o
caso da alocação global.
Sobre a MIR trabalham essencialmente três tipos de rotinas, as relacionadas com os
processos de optimização, as relacionadas com a alocação global e as relacionadas com
a geração do código. Qualquer destas três rotinas serão analisadas com o devido detalhe
respectivamente nos capítulos 5, 6 e 7. Fica no entanto feita uma pequena descrição de
cada um dos módulos e de cada uma das rotinas.
Optimizer
O Optimizer representa uma classe com todas as funções de optimização. É um dos
módulos do BEDS ao qual é sempre possível acrescentar mais alguma coisa, pelo que
apenas se encontra implementado a título de exemplo.
As rotinas de optimização trabalham directamente sobre a MIR, necessitando por
vezes das estruturas de informação fornecidas pelo SSA, Data Flow Analyser, Control
Flow Analyser (Structural Analyser), Data Dependency Analyser e o Alias Analyser.
Estes dois últimos módulos ainda não se encontram implementados, pelo que todas as
rotinas de optimização que deles necessitam estão por desenvolver.
Global Allocator
Este módulo implementa a alocação global, com base no algoritmo de coloração de
grafos proposto por Chaitin [CACCHM81, Chait82]. Trata-se de uma fase do processo
de compilação que pode ter grande impacto na qualidade do código final, mas há que
ponderar a sua utilização, uma vez que requer muito processamento. Recorre de forma
directa ao Data Flow Analyser, ao SSA, ao Instruction Labelling e à Register Table.
Mas de forma indirecta envolve praticamente todas as restantes fases.
Structural Analyser
A MIR é composta essencialmente por um grafo com muita informação associada, o
qual pode assumir alguma complexidade, tornando a sua interpretação directa algo
inacessível. Há como tal que, criar mecanismos que permitam uma análise detalhada da
forma como o grafo está estruturado. O que normalmente se consegue através da
identificação de padrões típicos, que formam partes do grafo, e da interligação entre
eles. Este tipo de informação é essencial para determinados processos, como
optimizações do fluxo de controlo ou para a “linearização” do grafo.
Esta análise pode ser obtida de diversas formas, mas no caso do BEDS utilizou-se
uma abordagem designada por Structural Analyse, que tem por base os mecanismos de
parsing dos analisadores sintácticos, adaptados à utilização sobre grafos.
Poder-se-á questionar a razão de ser deste módulo, uma vez que a informação por ele
obtida, já é determinada através da análise sintáctica. No entanto é preciso ter presente
que é necessário construir a representação intermédia de forma a poder utilizar os
recursos fornecidos pelo BEDS, os quais por sua vez podem alterar a própria
representação (mantendo o valor semântico). Pelo que as estruturas que originalmente
existem no código fonte podem não existir na representação intermédia.
Tree Selector
Este módulo permite pegar na árvore de controlo do módulo anterior e obter uma
lista de árvores de expressões, as quais serão posteriormente requisitadas, uma a uma,
pelo Instruction Labelling.
Back-End Generator
O Back-End Generator é o sistema gerador que, a partir da especificação dos
registos, das instruções do processador e da relação destas com a representação
intermédia, permite gerar o selector de instruções e respectiva tabela de estados, a tabela
dos registos, um sistema de alocação local, o assigner e as rotinas para emissão do
código final.
Esta parte do BEDS pode funcionar independentemente do resto, aliás a ligação entre
este módulo e as componentes que ela gera, com os restantes obtém-se como opção do
sistema de geração e não por defeito.
Instruction Labelling
Esta é uma das rotinas do processo de compilação, gerada pelo módulo do Back-End
Generator, a qual é parte essencial dos sistemas de selecção com base no BURS. A sua
função é determinar o conjunto de padrões (instruções) que permitem cobrir cada uma
das árvores ao menor custo, tendo por base o State Table. Na prática é nesta rotina que
se faz a selecção das instruções, estando no entanto, o resultado obtido sujeito às
restrições do processo de alocação.
Local Allocator
Trata-se de uma rotina também gerada pelo módulo do Back-End Generator, que é
opcional e que permite alocar registos localmente, ou seja, ao nível de cada árvore de
expressões.
Register Assigner
As rotinas de alocação, quer sejam locais ou globais, são responsáveis por determinar
que operandos é que são candidatos a registos e que registos é que podem ser utilizados
por cada operando. Cabe ao Register Assigner verificar de entre esses registos, quais os
que se encontram livres, ou eventualmente ocupados, mas cujo conteúdo não seja mais
necessário, e depois, destes, seleccionar e atribuir os necessários a cada um dos
operandos.
Pode ainda acontecer, que do conjunto dos registos que um operando pode utilizar,
nenhum se encontre disponível, nesta situação o Register Assigner deve avisar o sistema
de alocação do sucedido, para que este opte por outro tipo de soluções, ou então ele
próprio deve decidir o que fazer. Em ambas as situações, a solução poderá passar por
realizar o splitting ou spilling de um dos registos, de forma a concluir a geração e a
alocação com êxito.
Code Emiter
Após a selecção definitiva das instruções e do processo de alocação, cabe ao Code
Emiter gerar o código final, que na actual situação do BEDS, resulta em código
assembly. Pretende-se posteriormente criar a possibilidade de gerar o próprio gerador de
código binário, com base na descrição das instruções e dos campos que as compõem.
State Register
Table Table
Instruction
Table
Assembly
Nas duas próximas secções explica-se sucintamente como é que através do BEDS se
pode conceber compiladores com sistemas de alocação local e global.
Para cada tipo de alocação impõe-se um modelo próprio de back-end, uma vez que o
tipo de interligação entre as diversas fases é distinto. Para o caso da alocação local o
modelo encontra-se representado na Fig. 3.2.
Neste modelo o BEDS gera um sistema de alocação do tipo On-The-Fly Optimizado,
ou seja, a alocação é feita localmente para cada árvore de expressões, sendo os registos
atribuídos conforme vão sendo necessários. Trata-se de um modelo optimizado, uma
vez que, entre outras coisas, permite a reutilização de registos numa mesma árvore. Este
processo de alocação será apresentado posteriormente com maior detalhe.
Uma vez gerado o código segundo a representação MIR, com auxílio do SSA,
processam-se as optimizações ao nível da representação intermédia. Estas podem
recorrer à análise do fluxo de controlo e de dados, à análise de dependência entre dados
ou à análise de aliases. A única limitação imposta aos processos de optimização é de
que estes não podem utilizar abordagens destrutivas sobre a MIR, ou seja, as alterações
feitas devem continuar a garantir uma representação MIR.
Após esta fase, procede-se à análise estrutural para se construir a árvore de controlo,
que cria uma estrutura de informação suplementar de forma a não alterar a MIR, o que é
irrelevante para o presente caso, mas fundamental para o caso da alocação global.
A árvore de controlo é percorrida na fase do Tree Selector, de baixo para cima e da
esquerda para a direita, processando cada folha de forma a criar uma lista de árvores de
expressões.
O Instruction Labelling vai requisitando árvore a árvore ao Tree Selector, realizando
para cada uma o labelling, de forma a determinar o conjunto de instruções que
permitem criar o respectivo código ao menor custo possível. Após isso a árvore é
transmitida ao Local Allocator, o qual é responsável por implementar uma política de
atribuição para os registos. Cabe ao Register Assigner realizar a atribuição propriamente
dita.
O Local Allocator liberta os registos que não se encontrem a ser utilizados. Este
processo faz-se ao nível da própria árvore, ou seja, por defeito são libertados todos os
registos ocupados pelos descendentes de um nodo, excepto o que é utilizado para
manter o resultado do próprio nodo e os registos que guardam os resultados de sub-
árvores de utilização comuns (estes só são libertados após a última utilização).
É com o trabalho conjunto destas três fases, o Instruction Labelling, o Local
Allocator e o Register Assigner, que é possível garantir a plena geração de código. Tal
só não acontece, se não for possível realizar o labelling (independentemente do custo),
situação que só deverá ocorrer por falha da especificação.
Mas para que a geração de código final seja bem sucedida, é necessária uma forte
integração entre as componentes envolvidas. Cabe no entanto ao Register Assignment
determinar se é ou não possível concluir o processo de geração com sucesso, caso tal
não o seja, deverá optar pelas seguintes alternativas: em primeiro lugar, tentar realizar o
splitting da variável associada ao nodo da árvore de expressões para o qual não foi
possível realizar a alocação, aumentando o custo da solução até aí proposta, na
esperança que o Instruction Labelling, numa nova travessia, encontre uma outra solução
(que certamente terá um custo igual ou superior à solução anterior). Se mesmo assim
não for possível gerar o código final, quer por não se conseguir realizar o labelling da
árvore, quer por ainda assim, não ser possível realizar a alocação, então opta-se por uma
solução de spilling. Neste caso, decompõem-se a árvore em duas (ou mais), de forma a
que o resultado da sub-árvore para a qual não foi possível realizar a alocação, fique
guardado em memória. A árvore original é assim reescrita de forma a utilizar o
endereço dessa posição de memória invés da sub-árvore do qual este resulta.
Infelizmente a implementação do processo de spilling não é tão simples como se
descreve, pelo menos no caso de se pretender obter uma solução que não comprometa a
portabilidade do sistema. Além de mais nem sempre é fácil determinar o ponto pelo
qual se deve dividir a árvore original. Os detalhes da implementação serão discutidos
posteriormente no capítulo 6.
Para concluir falta o Code Emiter, que pega nos padrões das instruções e substitui os
operandos pelos respectivos valores, quer estes sejam registos, endereços ou constantes
e imprime para um ficheiro, gerando assim o código em assembly.
failed
Tree List Instruction Tree List Global
Labelling Allocator
successful
State Data Flow Register
Table Analyser Table
State
Table
Instruction
Table Fig. 3.3 – Modelo de um compilador com
alocação global.
A nova operação de labelling, não deverá trazer grandes alterações, mas apenas
acrescentar e actualizar as situações directamente envolvidas com as operações de
spilling. Se tal não acontecer, existem duas alternativas: tentar atribuir os registos na
esperança de se obter o código final, sem que para tal exista qualquer vantagem
resultante do processo de alocação e correndo o risco de não ser possível realizar
correctamente o assigner; ou então voltar a realizar o labelling, tantas vezes quantas as
necessárias, e até se obter uma solução estável entre a fase da alocação e a fase de
labelling. Só após se obter tal solução é que se deve atribuir os registos, concluindo
depois a compilação com a passagem das árvores para o Code Emiter.
4 My Intermediate Representation
A especificação da representação intermédia, aqui designada por MIR, teve por base
a especificação do RTL System. No entanto, conforme se foi desenvolvendo a
implementação do BEDS, foi necessário modificar a especificação original. Tal não se
deve a nenhuma incorrecção por parte do RTL System, mas sim ao facto da MIR
integrar outros mecanismos diferentes dos utilizados neste sistema. Para além disso e
apesar de ambas as representações partilharem muitas das características, a MIR sofreu
alterações implícitas à própria estrutura do BEDS. Conceptualmente ambas
representações partilham os conceitos base da RTL e do SSA.
Muitas das características da MIR estão associadas, não à representação intermédia,
mas sim a imposições colocadas pelos vários módulos que compõem o BEDS. Há como
tal que distinguir o que é específico da MIR, do que não é, como por exemplo, as
estruturas associadas à MIR que permitem a análise dos dados. Dentro do possível
apenas interessa focar neste capítulo as partes específicas da MIR, uma vez que as
restantes serão apresentadas nos respectivos capítulos.
Assim sendo pode-se classificar as estruturas fornecidas pela MIR em quatro classes,
a classe Genérica, com as infra-estruturas de apoio à representação dos programas, a
classe Expressions que permite descrever as expressões da representação intermédia, a
classe DataTransfer que permite descrever todo o tipo de transferências entre dados e a
classe FlowNode, com os objectos que descrevem a organização do programa ao nível
das estruturas de controlo.
Antes de prosseguir com a descrição de cada uma destas classes, e como se disse
acima, vai-se previamente apresentar a noção de SSA.
dt1 a=0 a1 = 0
dt2 b=a+1 b1 = a1 + 1
dt3 a=2 a2 = 2
dt4 c=a+b c1 = a2 + b1
Como só é permitido uma única atribuição por variável, torna-se muito fácil
determinar quem é que utiliza o resultado proveniente de uma dada expressão ou quem
por sua vez é responsável pelos resultados por esta utilizados. Esta informação é
essencial para maioria dos processos de optimização.
Para além disso, o SSA permite implicitamente remover dependências do tipo anti-
dependence e output-dependence. Por exemplo, na representação normal do exemplo
anterior, existe uma anti-dependência entre dt3 e dt2, uma vez que dt3 redefine o valor de
uma variável utilizada por dt2. Tal já não acontece na forma SSA uma vez que a1 e a2
são para todos os efeitos variáveis distintas.
O mesmo acontece entre dt1 e dt3, onde na representação normal existe uma output-
dependence entre estas duas expressões, o que já não ocorre para a representação SSA.
A representação SSA é obtida, decompondo cada variável em tantas quantas as suas
definições (atribuições), de tal forma que cada uma represente um instante da vida da
variável original. Mas para que tal seja sempre verdade há que contornar determinadas
situações, das quais fazem parte os dois seguintes casos:
i0 i0
while .... if ... then
... ...
ii+1 i 10
... ...
fimwhile else
...
i 20
...
fimse
...
ji
i1 0 i1 0
while .... if ... then
... ...
i2 Φ(i1, i2) i2 10
... ...
fimwhile else
...
i3 20
...
fimse
...
i4 Φ(i2, i3)
j i4
A função Φ(...) é utilizada quando num dado ponto do programa existem duas ou
mais instancias duma mesma variável, transformando-as todas numa única e nova
instancia. Os parâmetros da função são como tal as instâncias que alcançam esse ponto
do programa, onde o resultado é a instância proveniente do ramo do fluxo por onde se
alcançou a actual posição do programa.
Se no entanto esta abordagem resolve o problema das atribuições, não deixa por si só
de levantar outros problemas: o primeiro é como saber onde se devem inserir as funções
Φ(...); e o segundo é como as representar no código final, de forma a que estas
funcionem como o previsto?
As respostas a estas perguntas são dadas no capítulo sobre optimizações (capítulo 5),
onde se descreve o processo de implementação das estruturas de apoio ao SSA.
Julgo que as explicações fornecidas sobre o SSA, serão suficientes para se poder
iniciar a descrição das classes da MIR.
Classe Program
Após se analisar, para várias linguagens, a organizado e a estrutura de um programa,
concluiu-se que seria necessário criar um suporte para representar as variáveis, o código
e as funções que funcionam a nível global.
A título de exemplo, para um compilador de C, a este nível encontravam-se
declaradas todas as funções, através de objectos do tipo Function (uma vez que estas
são globais), todas as variáveis tipo externo ou global e ainda o código implementado
fora de qualquer função.
Desta forma a classe Program é composta pelos seguintes atributos:
Classe Function
A classe Function possui a informação referente a uma função, procedimento ou
bloco de código com variáveis locais.
Há semelhança da classe anterior, também esta classe possui: uma tabela para os
identificadores locais, um conjunto de funções locais, um conjunto de FlowNodes com
o código da função, um apontador para o nodo inicial do conjunto anterior e um sistema
próprio para a gestão do espaço de endereçamento da memória de dados. Para além
disso, possui ainda os seguintes atributos:
Expressions
BinaryExpressions
AsgnExpression
AddExpression
...
UnaryExpressions
NegExpression
...
Storage
Memory
Register
Constant
BlockMemory
Label
...
JumpExpressions
Jump
CondJump
Call
Return
...
declarados para Expressions. Já o Storage possui um atributo, o value, que é uma união
que permite armazenar qualquer valor (variável, constante, etc) de um qualquer tipo
primitivo de dados da linguagem C (char, short, float, etc).
Não se pretende aqui, descrever extensamente todas as subclasses de Expressions, é
no entanto necessário apresentar algumas dessas classes para que seja possível
compreender a representação intermédia.
Classe BlockMemory
Esta é uma classe que não serve para descrever expressões, mas sim auxiliar o
processo de atribuição de endereços às variáveis. É iniciada com um determinado
tamanho que representa o espaço de memória em bytes, sem que no entanto esse espaço
exista. Depois conforme se constrói a representação intermédia, é possível requisitar aos
objectos desta classe, endereços para as variáveis, necessitando apenas que se indique o
tamanho, em bytes, do espaço de memória a este associado. A própria classe garante a
gestão do espaço de endereçamento.
Na prática não é mais que um array de bits, onde cada um representa um byte de
memória e onde a gestão consiste em alocar e a desalocar o espaço conforme é
necessário.
Classe Memory
Os objectos desta classe dão corpo às variáveis, estando normalmente associados a
um BlockMemory e a um endereço por este atribuído. Para além disso encontram-se
ligados à célula da tabela de identificadores cuja variável representam.
Classe Register
Os objectos desta classe são os recipientes, por omissão, do resultado das expressões.
O seu objectivo é de alguma forma representar o resultado intermédios de cada uma das
operações.
De notar que, apesar do nome desta classe ser Register, não significa que no código
final os objectos dela instanciados sejam substituídos directamente por registos físicos.
Há semelhança da classe anterior, também estes objectos podem estar relacionados
com uma célula da Tabela de Identificadores, aliás, para o pleno funcionamento de
todas as estruturas do BEDS, deverá sempre existir esta relação. Este aspecto será
explorado na descrição da classe DataTransfer e no capítulo sobre a alocação global.
Na representação intermédia estes objectos não chegam a fazer parte das árvores de
expressões, encontrando-se apenas associados a estas, através dos DataTransfer. Aliás,
são estes últimos os responsáveis pela instanciação dos objectos desta classe, pelo que
existe sempre um DataTransfer para cada Register (o inverso já não é verdade).
Mais explicações sobre as subclasses de Expressions, serão fornecidas
posteriormente conforme forem necessárias.
DataTransfer
Assignment
AttribAssignment
LabelAssignment
JumpAssignment
CondJumpAssignment
ReturnAssignment
PhyAssignment
Assignment
Register target
source Expression
Expression Expression
Classe Assignment
A classe Assignment é o tipo de DataTransfer de utilização genérica, a única
restrição é que o LHS tem que ser um Register, permitindo assim identificar trocas de
dados entre uma qualquer expressão que se encontre do RHS para um pseudo-registo.
Esta classe encontra-se representada na Fig. 4.1, onde se pode identificar o target do
tipo Register e o source que representa uma qualquer Expression.
A atribuição de uma Expression a source actualiza as estruturas de suporte à análise
do fluxo de dados. Para tal, o método responsável pela atribuição desta variável
Classe AttribAssignment
Este tipo de DataTransfer permite identificar transferências de dados entre uma
qualquer expressão e uma variável em memória. A sua função principal é indicar
quando é que se deve actualizar o valor em memória de uma variável. Como tal, o
target é sempre do tipo Memory e o source do tipo AsgnExpression, este último é uma
classe derivada de Expression, do tipo BinaryExpression, cuja função é identificar
directamente operações de atribuição.
Assignment
Register target
source Expression
Expression Expression
AttribAssignment
Memory target
source AsgnExpression
Classe LabelAssignment
Esta classe destina-se a identificar as posições onde é necessário inserir labels.
Encontra-se normalmente associada aos objectos da classe FlowNode, como se poderá
ver mais adiante. O único atributo que contém é o label, que identifica uma Expression
do tipo Label. Esta última classe apenas possui um identificador, que é único e é
atribuído aquando da instanciação deste tipo de objectos.
LabelAssignment
label Label
Classe JumpAssignment
Este tipo de DataTransfers serve para identificar operações de salto incondicional. A
sua utilização está sempre associada a um determinado tipo de FlowNode, o JumpNode.
Esta classe possui apenas uma única variável, a jpexp, que é do tipo Jump. Esta
última permite que lhe seja associado um objecto da classe Label, e cuja função é
identificar a posição para onde se deve efectuar o salto. A ligação entre estas classes
encontra-se representada na Fig. 4.4.
JumpAssignment
jpexp Jump
LabelAssignment
label Label
Classe CondJumpAssignment
Este é o tipo de DataTransfer que identifica operações de salto condicional. À
semelhança da classe anterior, a sua utilização está directamente associada a um
determinado tipo de FlowNode, o CondJumpNode.
Esta classe possui apenas uma variável, a cjpexp, da classe CondJump. Esta última
descreve toda a operação necessária à execução de um salto condicional. Como tal, está
associada a uma condição de teste e a dois objectos do tipo Label, para os quais se
realizam os saltos, mediante o valor da condição.
Como esta operação necessita de três argumentos, é necessário recorrer a alguns
mecanismos auxiliares de forma a manter a coerência com o sistema de expressões
binárias utilizadas pelo BEDS.
Assignment
Register target
source Expression
Expression Expression
CondJumpAssignment
cjexp CondJump
ArgExpression
LabelAssignment LabelAssignment
Classe CallAssignment
Os objectos desta classe pretendem descrever as chamadas de funções ou
procedimentos. O target está ligado a um Register e o source a uma Expression do tipo
Call. Este, por sua vez, possui como descendente esquerdo um objecto do tipo Function
que assinala a função/procedimento a invocar e do lado direito a lista de argumentos, ou
seja, a lista das expressões das quais resultam os argumentos. Quando existe mais do
que um argumento é necessário utilizar o ArgExpression. A Fig. 4.6 ilustra a utilização
desta classe.
Classe ReturnAssignment
O ReturnAssignment serve para identificar as operações de retorno de funções, as
quais estão sempre associadas aos FlowNodes do tipo ReturnNode.
Esta classe possui uma variável da classe Return que é descendente de Expression, a
qual está associada, caso exista, à expressão que dá origem ao valor a retornar. A
relação entre estas classes encontra-se representada na Fig. 4.7.
Assignment
source Expression
Register target
Expression Expression
Assignment
source Expression
Register target
Expression Expression
CallAssignment
Register target
source Call
Function ArgExpression
Classe PhyAssignment
Esta classe é exclusiva dos mecanismos necessários ao SSA, a sua função é assinalar
a presença de funções Φ(...). Não possui qualquer variável específica uma vez que a
informação de que necessita é determinada através dos mecanismos que implementam a
análise do fluxo de dados.
Como se poderá ver no capítulo 5.3, estes DataTransfer são inseridos pelo processo
que converte a representação não-SSA em SSA. É ainda possível inserir estes
DataTransfer aquando da geração da representação intermédia, mas infelizmente tal só
é possível para linguagens bem “comportadas”, ou seja, linguagens sem operações do
tipo goto ou com vários returns.
Quanto à classe DataTransfer, como forma de representação, está quase tudo dito. O
que falta referir está relacionado com as estruturas de dados que foram necessárias
introduzir para o funcionamento dos restantes módulos do BEDS, mas tal será feito nos
respectivos capítulos. Convém apenas sublinhar que, apesar dessas estruturas estarem
incluídas noutros projectos, são elas que dão razão de ser aos DataTransfer.
Assignment
source Expression
Register target
Expression Expression
ReturnAssignment
retexp Return
FlowNode
GenericNode
JumpNode
CondJumpNode
ReturnNode
IntervalNode
JumpNode
block
lassign LabelAssignment
...
jassign JumpAssignment
outEdges
Classe GenericNode
Esta classe não é directamente utilizada na representação intermédia, pois destina-se
apenas a conter as variáveis que são comuns às classes que dela descendem.
As variáveis que a compõem são: o block, que é uma sequência com todos os
DataTransfers contidos em GenericNode; e a lassign, do tipo LabelAssignment que
permite associar uma Label ao início do GenericNode. O lassign é sempre o primeiro
DataTransfer de block.
Classe JumpNode
Esta classe serve para representar qualquer bloco de instruções (DataTransfers), que
termine com uma operação de salto incondicional, como tal possui uma variável, a
jassign, do tipo JumpAssignment com toda a informação associado à operação de salto.
O jassign ocupa sempre a última posição de block. A Fig. 4.8 ilustra a composição desta
classe.
Classe CondJumpNode
Os blocos de instruções que terminem com uma operação do tipo salto condicional
são representados por objectos da classe CondJumpNode. As principais diferenças em
comparação com a classe anterior, é que esta possui no lugar do JumpAssignment, um
CondJumpAssignment e o outEdges está ligado a dois GenericNode, um por onde
continua a execução do programa caso a condição seja verdadeira e outro para o caso
desta ser falsa.
Classe ReturnNode
Esta classe serve para representar os conjuntos de instruções que terminam com uma
operação do tipo retorno. Ao contrário das duas classes anteriores não possui elementos
em outEdges e o último DataTransfer de block é um ReturnAssignment.
Classe IntervalNode
Este é um tipo de FlowNode cuja principal característica é permitir conter outros
FlowNodes. Destina-se a ser utilizado fundamentalmente pela análise estrutural. A qual,
como já atrás se disse, tem por objectivo construir a árvore de fluxo de controlo a partir
do respectivo grafo, em que para tal é necessário reconhecer determinados padrões pré-
definidos, formados por vários nodos e que representam estruturas condicionais e
cíclicas conhecidas, os quais são posteriormente substituídos por um único objecto desta
classe. O objectivo final é reduzir o grafo de fluxo de controlo a um único nodo deste
tipo. As variáveis desta classe são:
Após esta descrição da classe FlowNode, pode-se dizer que o grafo de controlo de
fluxo (CFG) de um programa, é, na representação MIR, formado por um conjunto de
GenericNodes, o qual contém mais dois elementos do que o número de vértices do CFG
original, que são o startNode e endNode.
5 Optimização
A fase de optimização, como já foi dito, é uma das fases mais importantes de um
compilador moderno e tende a ganhar cada vez mais relevo. Tal facto deve-se a que as
exigências actuais não se padecem com a construção de simples tradutores de código
fonte em código final, com base em técnicas ad doc. É exigido muito mais do que isto,
pretende-se compiladores que retirem o máximo proveito das potencialidades do
processador para o qual são construídos.
De notar que a velocidade de execução de um programa não depende só da
velocidade do processador, mas também da eficiência do código objecto; além de que a
quantidade de recursos necessárias à execução desses mesmos programas é em grande
parte determinada pelo processo de compilação.
Não é por uma qualquer razão que esta área é uma das mais activas de entre as
muitas que compõem o universo das áreas associadas ao desenvolvimento de geradores
de código. Não pelos processos de optimização em si, mas sim pelas diferentes formas
como estes são implementados, as quais têm evoluído a par dos modelos de
representação e das infra-estruturas possíveis de associar a estes modelos. É como tal
praticamente impossível falar de optimizações, sem falar das várias formas de análise
fundamentais à sua implementação. Pretende-se aqui (neste capítulo) focar aquelas que
são relevantes aos vários projectos que compõem o BEDS, das quais fazem parte a
análise do fluxo de controlo, a análise do fluxo de dados e alguns conceitos sobre a
análise de dependência entre dados.
Nodo 1
Nodo 1 Nodo 2 Nodo 3
Nodo 3 Nodo 4
Nodo 4
A Fig. 5.2 ilustra a representação MIR das listas de adjacências dos três primeiros
nodos do CFG da Fig. 5.1.
inEdges Null
Nodo 1
outEdges Nodo 2 Nodo 3
inEdges Nodo 1
Nodo 2
outEdges Nodo 5
Fig. 5.2 – Representação da lista de adjacências dos 3 primeiros nodos do grafo da Fig. 5.1.
Exemplo 5.1
Pretende-se mostrar a aplicação de uma forma de análise de intervalo, conhecida
por T1-T2 interval analysis, na redução do grafo da Fig. 5.1. Este tipo de análise
utiliza apenas as duas seguintes transformações para reduzir o grafo:
T1 T2
N1
N1,2 N1 N1
N2
Nodo 5 3ª Fase
Nodo
1,2,3,4,5
Nodo
1,2,3,4,5
Nodo Nodo
1,2,5 3,4
Nodo 3 Nodo 4
Fig. 5.4 – Árvore de controlo resultante da análise T1-T2 para o grafo da Fig. 5.1.
que indica a “camada” a que este pertence em relação a todo o grafo. Para tal foi
necessário acrescentar à classe FlowNode as seguintes variáveis:
Depois pega no nodo de menor ordem e a partir dele tenta identificar algum tipo de
região. É importante dizer, que uma das poucas restrições desta análise, é que as regiões
só podem ter um único ponto de entrada, pelo que o nodo seleccionado acaba por ser o
único que possui antecessores exteriores à região a identificar.
A identificação das regiões, no algoritmo utilizado, faz-se em duas fases: numa
primeira tenta-se construir a partir do nodo inicial uma região do tipo acíclico; caso não
seja possível, passa-se a uma segunda fase, a qual testa se o nodo inicial faz parte de
uma região do tipo Impróprio ou do tipo cíclico.
Após se ter determinado o tipo de região, esta é reduzida a um nodo abstracto,
obrigando a redireccionar todas as transições que se fazem entre os nodos que
pertencem à região e os nodos exteriores a esta e actualizando a variável interval de
cada nodo.
Sempre que ocorre uma redução, inicializa-se o processo, o qual se repete até que
não seja possível executar mais nenhuma redução, ou seja, até que se obtenha um único
nodo.
Tipo de regiões
Como já se referiu, as regiões podem ser de três grandes classes: acíclica, cíclica ou
impróprias. As primeiras e como o próprio nome indica, caracterizam-se por não
conterem caminhos cíclicos dentro da região que descrevem. A solução implementada
permite detectar os seguintes tipos: Block, IfThen e IfThenElse, que se encontram
representados na Fig. 5.5.
B1 B1 B1
...
B2 B2 B3
Bn
Nas regiões cíclicas existe sempre caminho entre dois quaisquer nodos. A solução
implementada permite identificar as seguintes regiões: SelfLoop, WhileLoop e o
NaturalLoop, que estão representados na Fig. 5.6.
B1
B1
B1
B2
B2
B1 B1
B2 B3 B2 B3 B4
Exemplo 5.2
Pretende-se ao longo deste exemplo mostrar como todo o processo da análise
estrutural se desenrola para o grafo da Fig. 5.1.
Nº de Ordem
0 Nodo 1
0 Nodo 1
2 Nodo 5 Nodo 4
2 Nodo 4
2 Nodo 5
Nodo 1
Nodo
Nodo 2
(3,4)
Nodo 5
IfThenElse Block
Nodo 1 Nodo
Nodo
(1,2,((3,4)))
((1,2,((3,4))),5)
Nodo
Nodo 2
((3,4))
Nodo 5
Nodo 5
O nodo final como já se disse representa a raiz da árvore de controlo de fluxo, que
para este exemplo se encontra representada na Fig. 5.11.
Block
IfThenElse Terminal
Nodo 5
Block
Terminal Terminal
Nodo 3 Nodo 4
A análise de fluxo de dados, pelo tipo de informação que permite obter, é uma das
principais formas de análise, funcionando de suporte a um grande número de rotinas do
processo de compilação. A sua função é determinar a forma como os dados (variáveis)
são manipulados no decorrer de um programa, função ou bloco de código. São várias as
informações que este tipo de análise e respectivas estruturas de dados permitem obter,
tais como: as posições onde ocorrem as definições de uma variável; as posições onde se
utiliza determinada definição de uma variável; as posições das definições que alcançam
determinada utilização; e que variáveis alcançam determinada posição do programa.
Nas secções que se seguem apresenta-se a forma como o BEDS se propõe
implementar os mecanismos necessários ao processo de análise do fluxo de dados, na
tentativa de obter, entre outras, as informações atrás referidas.
CellIDTable
flowSupporters (a)
Assignment
IDreg
Register target Source Memory
flowDependents
flowSupporters
Assignment
flowDependents
flowSupporters
Assignment
flowDependents
AttribAssignment
Memory target
source AsgnExpression
Apesar dos mecanismos até aqui descritos já permitirem, por si só, fornecer bastante
informação, não se pode ainda falar de um processo de análise. Para além de mais,
espera-se que a análise do fluxo de dados permita obter mais informação do que aquela
que os mecanismos até aqui apresentados fornecem, como por exemplo, determinar o
alcance das variáveis num programa.
De forma genérica, a análise do fluxo de dados deve permitir controlar o processo
evolutivo de determinadas características associadas aos dados, ao longo da execução
de um programa. Uma das quais é a própria presença (alcance) da variável, ou seja,
determinar quando é que esta está presente ou deixa de estar ao longo da execução do
programa. No entanto, não se deve restringir a análise do fluxo de dados a este exemplo,
pois existem outras características inerentes aos dados cuja evolução pode ser traçada
através deste tipo de análise, como por exemplo, a evolução do valor das variáveis.
Existem diversas formas de implementar a análise do fluxo de dados, recorrendo
inclusive à análise estrutural e à análise de intervalos, apresentadas em secções
anteriores. O método utilizado pelo BEDS é um dos mais simples de perceber e de
implementar; designa-se por Análise Iterativa e, como se pretende, trabalha sobre grafos
orientados. Estes no entanto devem sempre possuir um nodo inicial e um nodo final, os
quais serão posteriormente reconhecidos respectivamente por startNode e endNode
(variáveis de FlowNode). Caso o grafo contenha mais do que um nodo de saída, é
necessário reestruturá-lo de forma a que todos esses nodos passem apontar para um
único nodo (de saída). A descrição que se faz desta análise e das respectivas definições
foi retirada do capítulo 8 do livro Advanced Compiler Design and Implementation
[Much97], mas o algoritmo final, utilizado na análise do alcance das variáveis é da
autoria de Gary Kildall [Kild73].
<x1,..., xn> ∧L <y1,..., yn> = < x1 ∧ y1, ..., xn ∧ yn> Eq. 5.1
<x1,..., xn> ∨L <y1,..., yn> = < x1 ∨ y1, ..., xn ∨ yn> Eq. 5.2
∀ x ∈ L, x U T = T e x Π ⊥ = ⊥ Eq. 5.3
∀ x ∈ L, x ∨ T = T e x ∧ ⊥ = ⊥ Eq. 5.4
Define-se ainda, uma função que dado um nodo devolve um vector de bits
assinalando que variáveis são (re)definidas dentro desse nodo (0- (re)definida, 1-
inalterada), da seguinte forma:
O que não é mais do que a função de fluxo do respectivo FlowNode. De notar que
Def(...) não assinala mais do que o início de cada definição.
O vector de bits que se obtém à saída do FlowNode resulta da operação de meet entre
o resultado de Def(...) e o resultado de AliveIn(...), de tal forma que:
ou seja:
Vinicial , i = startNode
I AliveOut(p), i ≠ startNode
p∈inEdges ( i )
Enqueue( WorkLst, p)
AliveIn(b) T
FimPara
AliveIn(startNode) Vinicial
Repetir
b Dequeue( WorkList,)
totaleffect T
Para ∀ p ∈ Antecessores(b) Fazer
effect AliveOut(p)
totaleffect totaleffect Π effect
Se AliveIn(b) ≠ totaleffect Então
AliveIn(b) totaleffect
Enqueue( WorkList, b)
FimSe
FimPara
Até Que WorkList = ∅
Fim
O algoritmo começa por criar um queue auxiliar, a WorkList, com todos os nodos do
grafo excepto o startNode, depois inicializa os reticulados, com Vinicial para o startNode
e com top para os restantes. À partida estes dois valores (top e Vinicial) são iguais, mas
pode acontecer que se pretenda controlar a evolução das variáveis que são definidas
como parâmetros ou externamente ao grafo, pelo que Vinicial deve traduzir o estado
dessas variáveis.
De seguida o algoritmo entra na fase iterativa, onde começa por remover um
elemento de WorkList e determinar através dos nodos precedentes, que variáveis
alcançam o nodo em causa. Sempre que ocorrem alterações no respectivo reticulado, o
nodo é reposto na WorkList para voltar posteriormente a ser processado. O algoritmo
termina quando os valores dos reticulados estabilizarem.
O BEDS não se fica por esta forma de análise; é que, após determinar o alcance das
variáveis, o BEDS permite determinar o período de vida útil das mesmas. De reparar
que este último tipo de análise tem objectivos diferentes da anterior, dado que o período
de vida útil de uma variável termina após a sua última utilização. Pelo que se considera
que uma variável está “viva” num determinado ponto B do grafo, se e só se existir uma
definição dessa variável que alcance esse ponto e se existir pelo menos uma utilização a
partir desse ponto (inclusive).
Para tal foi necessário definir mais uma função, designada por Use(...), a qual
permite determinar para um dado nodo quais as variáveis (definições) nele utilizadas (0-
utilizada, 1- não utilizada), da seguinte forma:
Uma vez que todas as variáveis alcançam o endNode, então o resultado da análise do
alcance resulta num reticulado com todos os valores a ⊥. É este o ponto de partida para
se realizar a análise do período de vida útil.
A ideia base consiste em percorrer o grafo, desde o endNode até ao startNode,
testando que variáveis (definições) estão a ser utilizadas, mantendo apenas essas como
activas, as restantes deixam de o estar até que se encontre uma utilização ou respectiva
definição.
Para esta forma de análise, continua-se a utilizar o mesmo tipo de reticulados da
análise anterior, ou seja vectores de bits, também eles implementados com base nas
estruturas e funções da análise anterior, nomeadamente com base no vector in e nas
funções Def(...) e AliveIn(...).
A MOP é obtida aplicando iterativamente o seguinte conjunto de instruções a todos
os nodos do grafo (excepto o startNode) até se obter uma solução estável:
Na inserção das funções Φ(...), o primeiro problema é determinar onde é que estas
devem ser inseridas. Uma solução simples, consiste em colocar por cada variável e em
todos os nodos para onde convirjam dois ou mais caminhos uma função Φ(...). Mas
facilmente se percebe, que se trata de uma solução extrema, uma vez que, nem em todos
os nodos necessitam de uma função Φ(...) por cada variável.
A solução mais eficiente consiste em colocá-las, em posições do grafo, designadas
por Dominance Frontiers, que não são mais do que nodos do grafo alcançados por duas
ou mais definições de uma mesma variável. Esta solução designa-se por Minimal SSA
Form.
Para uma explicação mais formal do conceito de Dominance Frontiers, faz falta
definir o significado de nodo dominador (Dominator). Trata-se de um conceito que se
aplica aos grafos e que é definido da seguinte forma: um nodo a domina um nodo b, que
se representa por a dom b, se e só se, todos os caminhos possíveis que vão desde o nodo
inicial do grafo (startNode) até o nodo b, incluírem o nodo a. Diz-se então, que a
pertence ao conjunto dos nodos dominadores de b, o qual se representa por dom(b).
Define-se ainda que a é o dominador imediato de b, com a ≠ b, e representa-se por a
idom b, se e só se, a dom b e não existe nenhum nodo c, tal que c ≠ a e c ≠ b, para o qual
a dom c e c dom b. Nestas circunstâncias, a pode também ser designado por idom(b) e é
sempre único.
Define-se ainda que a domina estritamente (strictly dominates) b e representa-se por
a sdom b, se e só se, a dom b e a ≠ b.
Sejam então, A e B nodos de um grafo, tal que em A ocorre uma definição da variável
V, representada por V1 e A sdom B, então qualquer expressão de B vê a variável V como
sendo V1. Supondo agora um terceiro nodo C, tal que C ∈ Sucessores(B), mas B não
sdom C, o que implica, que C possui vários nodos precedentes, pelo que, pode ocorrer
que C veja para além de V1 outras definições de V. Diz-se então que C é uma dominance
frontier de A, pelo que necessita obrigatoriamente de uma função Φ(...) para a variável
V.
Por questões de eficiência computacional, não se pretende determinar as dominance
frontiers em relação a cada uma das variáveis, mas sim em relação a cada nodo do
grafo, o que permite uma solução independente das definições. Caso contrário, por cada
nova função Φ(...) inserida e uma vez que estas são definições, é necessário recalcular
novamente as dominance frontiers.
Diz-se então que, a dominance frontier do nodo X, a qual se representa por DF(X), é
o conjunto de todos os nodos Y’s, tais que, X é dominador de um dos antecessores de Y,
mas X não domina estritamente Y.
O método aqui utilizado para determinar as dominance frontiers foi apresentado por
Chaitin et al. [CFRWZ91] e tem por base a árvore de dominadores (dominator tree),
que tal como o nome indica é uma estrutura em forma de árvore que contém os mesmos
nodos do grafo, mas onde cada um possui como ascendente o nodo que imediatamente o
domina, ou seja, o ascendente do nodo X na árvore é sempre o idom(X).
Apesar de ser possível determinar DF(X) a partir da definição anterior e da árvore de
dominadores, ficou provado que a ordem desse algoritmo é quadrática. Chaitin, propôs
então, uma solução de ordem linear, provando que, para DF(X) contribuem dois tipos de
nodos, uns que serão designados por DFlocal(X) e outros por DFup(X,Z), de tal forma
que:
DF(X) = DFlocal(X) ∪ U DF
Z∈Children ( X )
up (X, Z) Eq. 5.19
Os DFlocal(X) são os sucessores de X, que não são estritamente dominados por X, tal
que:
Os DFup(X,Z) são os nodos, que não sendo estritamente dominados por X, pertencem
aos DF dos nodos estritamente dominados por X (que são os nodos descendentes de X
na árvore de dominadores), tal que:
para todo e qualquer Z cujo dominador imediato seja X, de tal forma que:
U DF up
Z∈N :idom ( Z ) = X
(X, Z) ≡ U DF
Z∈Children ( X )
up (X, Z) Eq. 5.24
De notar que, através da equivalência da Eq. 5.24 é possível determinar as DF, sem
que, para tal seja necessário construir a árvore de dominadores, da seguinte forma:
Foi esta última, a solução utilizada no BEDS que se encontra implementada na classe
DFSet do módulo SSA, a qual por sua vez, utiliza as classes IDom e IDomSet, para
determinar para cada nodo, o conjunto de nodos dos quais é dominador imediato.
O processo de inserção das funções Φ(...) é realizado para cada uma das variáveis de
forma independente, determinando-se, para cada uma, o conjunto de nodos do grafo
onde ocorrem as respectivas definições. As funções Φ(...) são então inseridas nas
dominance frontiers de cada um desses nodos. Convém no entanto, relembrar que as
próprias funções Φ(...) contribuem para o número de definições de cada uma das
variáveis.
A inserção das funções Φ(...) passa por pegar em cada definição de uma variável e
testar se já existe uma função Φ(...) para cada um dos nodos pertencentes à DF do nodo
onde ocorre a definição. Caso exista, basta então acrescentar a instância da variável
proveniente da actual definição aos parâmetros da função Φ(...). Caso contrário, é
necessário que antes se insira a função Φ(...). O algoritmo final para colocar as funções
Φ(...) e respectivos parâmetros, é o seguinte:
N1 N2 N3
... ... ...
v1(rx) ... v2(end.) ... v3(ry) ...
... ... ...
N4
...
v4(?)Φ(v1,v2,v3)
...
N1 N2 N3
... ... ...
v1(rx) ... v2(end.) ... v3(ry) ...
v5(rz) v1 v6(rz) v2 v7(rz) v3
N4
...
v4(rz)Φ(v5,v6,v7)
...
Fig. 5.19 – Exemplo de como se pode resolver a alocação para as funções Φ(...).
Até aqui muito se tem falado sobre optimizações, mas na realidade pouco ou nada foi
dito sobre estas. No entanto, apresentaram-se praticamente todos os mecanismos
necessárias à sua implementação.
De notar que praticamente nenhuma optimização, por si só, permite obter grandes
ganhos, quer ao nível da eficiência, quer ao nível do tamanho do código, e que a
aplicação de uma optimização pode melhorar um destes factores à custa da degradação
de outros. Mais, algumas optimizações devem ser aplicadas por diversas vezes, visto
que os efeitos colaterais de outras optimizações podem provocar novas oportunidades
de melhoramento. Além disso, a ordem pela qual são aplicadas é também um factor
importante para o resultado final.
É importante também perceber que uma optimização só deve ser aplicada se for
segura, ou seja, se for garantido que em toda e qualquer situação, as alterações por esta
realizadas não modificam o comportamento do programa original. Há ainda que
ponderar a sua utilização, pois os benefícios esperados podem não ocorrer para todas as
situações possíveis, podendo mesmo em determinadas circunstâncias degradar a
qualidade do código final.
Esta secção pretende descrever algumas formas de optimização, tentando dar
especial relevo àquelas que já são possíveis de implementar no BEDS e às que
facilmente se implementam através da representação SSA.
Convém antes realçar que no BEDS, grande parte do trabalho dentro desta área está
por realizar e que as poucas excepções se encontram praticamente por testar (só foram
implementadas com o objectivo de verificar o funcionamento das infra-estruturas
descritas nas secções anteriores).
vx Constante
Algebraic Simplifications
As propriedades algébricas podem ser utilizadas para simplificar determinadas
expressões. Algumas das propriedades mais utilizadas, são:
i+0≡0+i≡i–0≡i 0 – i = -i
i*1≡i+1≡i/1≡i i*0=0*i=0
-( -i ) ≡ i i + ( -j ) = i - j
b∧T≡T∧b≡b b∨F=F∨b=b
i^2 ≡ i * i 2*i=i+i
i * 5 ≡ t1 = i << 2 i*7≡ t1 = i << 3
t2 = t1 + i t2 = t1 - i
Algebraic Reassociation
Trata-se de um tipo de optimização com base nas propriedades algébricas, mais
concretamente na propriedade associativa, comutativa e distributiva. Os exemplos
típicos são:
a*b+a*c≡a*(b+c)
( i - j) + ( i - j) + ( i - j) ≡ ( 4 * i – 4 * j) ≡ 4 * ( i - j)
Convém no entanto salientar que, este tipo de transformações pode criar potenciais
situações de overflow.
Copy Propagation
Consiste em eliminar expressões do tipo vy vx, substituindo nas expressões
posteriores as utilizações de vy por vx.
Também esta é uma das optimizações facilmente implementáveis em SSA, uma vez
que basta pegar nos flowDependents do DataTransfer, correspondente à expressão vy
vx e substituir a utilização de vy por vx e actualizar os respectivos flowDependents e
flowSupporters.
vi 0
... /*Valor de vi mantém-se constante */
Enquanto vi Fazer
...
FimEnq
onde facilmente se percebe que a estrutura cíclica nunca será executada, uma vez que a
expressão de teste resulta sempre em falso.
O processo pela qual esta optimização avalia se o código é ou não alcançável, pode,
na sua forma mais simples, assemelhar-se ao Constant Folding, mesmo ao nível da
implementação. É no entanto possível utilizar abordagens mais agressivas, que
normalmente recorrem a processos de optimização do tipo Induction Variable, que é
apresentado mais adiante e cuja implementação é bastante mais elaborada.
a4*i/b t1 4 * i
cd+4*i ≡ a t1 / b
b d + t1
A sua implementação é algo mais complicada que as anteriores, pois necessita dos
mecanismos da análise de controlo do fluxo de dados. Onde os reticulados representam
o conjunto das expressões que se encontram disponíveis em determinada posição do
grafo. Na prática, estes são implementados através de um conjunto de (apontadores para
as) expressões.
De notar que uma expressão só está disponível em determinada posição do grafo, se
desde a posição onde esta é definida até ao ponto onde está disponível, não ocorre
nenhuma definição da variável que representa o seu resultado, nem de nenhum dos seus
operandos.
A substituição das sub-expressões passa por verificar se num determinado nodo,
existem sub-expressões que já se encontrem representadas no reticulado associado a
esse nodo. Se tal ocorrer, então é porque essa sub-expressão já foi previamente
calculada e não foi entretanto modificada, o que permite proceder à remoção da sub-
expressão, desde que se actualize todas as suas referências posteriores.
Code Hoisting
Trata-se de uma optimização que partilha os mecanismos de análise da optimização
anterior, e cujo objectivo, é determinar se existem expressões comuns aos vários
caminhos do grafo, que possam ser colocadas em evidência. O exemplo seguinte tenta
ilustrar esta situação:
Normalmente este tipo de expressões surgem, não por erro de quem programa, mas
como efeito indesejável de outras optimizações e do próprio processo de geração de
código. O seguinte exemplo ilustra esta situação:
i 1 i1 i1
Enquanto i <100 Fazer L1: t1 i > 99 t2 addr a
a[i] i + 1 Se t1 goto L2 t3 t2 – 4
FimEnq t2 addr a L1: t1 i > 99
t3 t2 – 4 Se t1 goto L2
t4 4 * i t4 4 * i
t5 t3 + t4 t5 t3 + t4
ii+1 ii+1
*t5 i *t5 i
goto L1 goto L1
L2: L2:
- Ou ainda se, as definições pertencem ao ciclo, mas são elas próprias constantes.
Induction Variable
A indução entre variáveis pode ser definida da seguinte forma: sendo x e y duas
variáveis, diz-se que x induz y se, qualquer variação no valor de x afecta y numa
quantidade proporcional.
Facilmente se percebe que através desta propriedade matemática, é possível realizar
uma série de simplificações sobre as expressões. Permitindo mesmo, provar que, em
determinadas circunstâncias, uma dada condição resulta sempre em verdadeiro ou em
falso, sem que para tal esta seja constante. O seguinte exemplo tenta ilustrar esta forma
de optimização:
De notar que, sempre que i aumenta em uma unidade, a[i] reduz-se em quatro
unidades, pelo que i induz a[i] . Aproveitando tal conhecimento, é possível remover para
fora do ciclo a parte que não depende de i.
Esta é também uma das optimizações que utiliza mecanismos da análise do fluxo de
dados.
Value Numbering
Uma optimização mais elaborada do que a eliminação de sub-expressões comuns, é
Value Numbering, que tem por objectivo, eliminar expressões equivalentes, mas não
necessariamente iguais. O seguinte exemplo ilustra uma situação onde é possível aplicar
esta forma de optimização:
i ... i ...
ji+1 ≡ ji+1
ki ki
pk+1 pj
Loop Inversion
Esta optimização consiste em transformar estruturas cíclicas do tipo while... ou for...,
em estruturas tipo repeat...until... ou repeat...while... . Trata-se como tal, de uma
optimização que funciona essencialmente sobre o grafo do fluxo de controlo e
eventualmente sobre as expressões de teste. No entanto, o seu efeito só pode ser medido
a nível da representação final, como ilustra o seguinte exemplo:
Código fonte
i1 i1
a1 a1
Enquanto i < 100 Fazer ≡ Repetir
aa*i aa*i
ii+1 ii+1
FimEnq Enquanto i < 100
RI s/ optimização RI c/optimização
i1 i1
a1 a1
L1: t1 i > 99 L1: aa*i
Se t1 goto L2 ii+1
aa*i t1 i < 100
ii+1 Se t1 goto L1
goto L1 L2:
L2:
RI s/ optimização RI c/optimização
Strength Reduction
São todas as optimizações que têm por objectivo substituir determinadas instruções
por outras de menor custo, como tal, são dependentes das características de cada
processador. O seguinte exemplo ilustra este tipo de optimização:
ab*2 ≡ a b << 2
aa+1 ≡ inc a
Existem muitas mais optimizações, mas por uma questão de espaço e de forma a não
alongar mais este capítulo sobre optimização, tiveram que ficar de fora.
Espera-se no entanto, que as optimizações aqui apresentadas tenham sido suficientes
para ilustrar o que é possível de realizar com estas, bem como as suas as vantagens e as
potencialidades que o BEDS fornece para sua implementação.
6 Alocação de Registos
Uma das melhores soluções encontradas para a alocação global utiliza um algoritmo
de coloração de grafos, através do qual se procura determinar o número mínimo de
cores necessárias para colorir todos os vértices do grafo, de forma a que não existam
dois vértices adjacentes com a mesma cor. Esta técnica foi utilizada por Chaitin et al.
[CACCHM81, Chait82] na concepção de um algoritmo para a alocação global de
registos. Esta é uma das melhores soluções propostas para resolver a alocação devido à
uniformidade com que se propõe tratar as diversas restrições inerentes a cada
processador, designadamente em relação aos registos, e por propor uma solução
sistemática na resolução da alocação.
Propõe-se ainda retirar o máximo proveito do processo de alocação, maximizando a
utilização dos registos. Para tal, delega nas fases de optimização e selecção de
instruções a responsabilidade de propor a utilização de registos para o maior número
possível de operandos. Assume, ainda a responsabilidade de minimizar o número de
instruções adicionais necessárias às operações de splitting, reduzindo como tal o
número de vezes em que é necessário salvaguardar o conteúdo dos registos para
memória de forma a disponibilizar os registos.
NOTA: A partir deste ponto e até ao final do capítulo, as definições de uma variável, as
variáveis temporárias e os pseudo-registos, passam a ser designados, só e
simplesmente por variáveis. E registo físico apenas por registo.
O algoritmo proposto por Chaitin começa por construir, para cada procedimento ou
função, o respectivo grafo de interferências. Onde cada vértice representa uma variável,
Desta forma, ao nível da MIR todos os operandos são por defeito candidatos aos
registos. É no entanto inconsistente tentar realizar a alocação sem discriminar quais são
realmente, os operandos que devem permanecer em registos, ou que pelo menos se tente
que permaneçam. Isto porque, em primeiro lugar, é insustentável considerar que todos
podem permanecer em registos ao longo de todo o programa, e em segundo lugar,
porque em última instância decidir se um operando ocupa ou não um registo depende
em muito das instruções do processador.
Desta forma, a nível da MIR e de todos os processos que se desenrolam
exclusivamente sobre ela, o objectivo é tentar que os operandos sejam vistos como um
tipo uniforme de dados, em que todos utilizam uma mesma forma de representação (os
Registers). Mas quando se trata de gerar o código final, da alocação ou de outros
processos directamente relacionados com as características do processador, é
normalmente necessário, discriminar quais os operandos que realmente podem ou
devem permanecer em registos, bem como determinar em que momentos é que tal deve
ser feito.
Convém ainda salientar que apenas as árvores de expressões passam para a fase de
selecção de instruções, das quais não constam os Registers, pelo que estes deixam de ter
qualquer significado ao nível da fase de selecção.
O BEDS determina quais os operandos que devem ou não permanecer em registos,
realizando uma pré-selecção das instruções, considerando para tal, que não existe
qualquer restrição por parte da alocação. Desta forma obtém a sequência óptima de
instruções para o correspondente código da representação intermédia, de onde é
possível saber quais os operandos que devem permanecer em registos, bem como o tipo
concreto de registo a utilizar, entre outras informações relevantes para a construção do
grafo de interferências.
Surge assim, pela primeira vez, a necessidade de interligar a representação MIR com
as fases posteriores do processo de compilação, nomeadamente com a selecção das
instruções. Esta não é no entanto, a única interligação necessária para se proceder com a
alocação, é também essencial consultar a Register Table, que é obtida pelo Back-End
Generator a partir da Register Specification (ver Fig. 3.1), o qual é parte integrante da
descrição do processador. Tudo com o objectivo de determinar o número de registos
disponíveis, bem como as restrições a colocar na utilização de cada um.
De forma a se conseguir realizar a pré-selecção das instruções, torna-se pertinente
“linearizar” a representação intermédia. Para tal, existe o Tree Selector cuja função é
percorrer a árvore de controlo de fluxo, através de uma travessia bottom-up e da
esquerda para a direita, processando cada um dos IntervalNodes, com o objectivo de
construir uma lista de árvores de expressões, segundo a ordem de execução (ver
capítulo 5.1).
Posteriormente, passa-se cada uma das árvores para o selector de instruções, o qual
trata de determinar quais as instruções idealmente necessárias, para executar o código
representado por estas.
Genericamente, as árvores são obtidas a partir dos AttribAssignments e de alguns
outros DataTransfers, nomeadamente dos responsáveis pelas expressões de salto e de
labelling. Por defeito, os Assignments não contribuem directamente para a obtenção das
árvores, mas apenas para as sub-árvores que as compõem.
É de notar que uma mesma sub-expressão pode fazer parte de várias árvores, o que
poderia levar a pensar que seria necessário controlar o processo de selecção destas sub-
árvores, de forma a que cada uma seja processada uma única vez. No entanto, e como se
poderá ver no capítulo 7, a solução óptima (conjunto de instruções) de uma árvore, é
determinada a partir das soluções óptimas de cada uma das suas sub-árvores. O que
implica que uma sub-árvore possui sempre a mesma solução óptima,
independentemente da restante árvore onde se insere. Como tal, não advém nenhum mal
em se pré-seleccionar as instruções de uma sub-árvore por diversas vezes uma vez que o
resultado é sempre o mesmo. O principal inconveniente é o tempo que se desperdiça.
No entanto, aquando da selecção final das instruções, tal já não pode acontecer, uma
vez que isso implicava que se gerasse código por cada vez que a sub-árvore fosse
processada, levando a que todo o esforço feito durante a representação intermédia para
se detectar sub-expressões comuns fosse anulado. Como tal e de forma a homogeneizar
o tratamento das árvores por parte do selector de instruções, implementou-se um
mecanismo de controlo, que assinala se uma dada sub-árvore já foi ou não processada.
Convém ainda salientar, que nem a criação da árvore de controlo, nem a criação da
lista de árvores destroem a representação intermédia, limitam-se apenas a decorar a
representação com mais alguma informação e a gerarem algumas estruturas de
informação temporárias. Pelo que o processo de alocação pode prosseguir sem qualquer
impedimento.
Antes de se continuar com a descrição das restantes fases do processo de alocação, é
conveniente perceber o que é que se ganhou com esta pré-selecção das instruções. Em
primeiro lugar, funciona como um teste de viabilidade da geração de código, uma vez
que se tal não for possível sem qualquer tipo de restrição em relação à fase de alocação,
então é garantido que também não é possível considerando essas restrições.
De notar que só não é possível gerar código se não existir pelo menos uma instrução,
ou conjunto de instruções, que permitam realizar cada uma das operações presentes na
MIR.
Em segundo lugar, permite simplificar algumas expressões e simultaneamente
eliminar algumas variáveis do tipo temporário. É que em determinados casos, algumas
sub-árvores (de expressões) são representadas ao nível do código final por uma única
instrução. Como tal, ao nível da MIR e uma vez que nesta fase do processo de
compilação já se executaram praticamente todas as operações de optimização,
exclusivas deste nível de representação, é possível reduzir cada uma dessas sub-árvores
a uma única operação representada por um só nodo, eliminando assim uma série de
DataTransfers e respectivas variáveis temporárias (Registers).
Em terceiro lugar e como já se viu, permite determinar quais os pseudo-registos que
devem permanecer em registos físicos, bem como o tipo concreto de registo.
O Tree Selector para processar as estruturas de controlo segue o tratamento standard
referido na secção 2.2.1. A selecção de instruções é apresentada no capítulo 7.
nada afecta o outro conjunto, e caso as variáveis também não interfiram entre si, de tal
forma que nenhuma possa ocupar um qualquer registo dos dois conjuntos, é então
possível obter vários grafos de interferências em vez de um. Este facto permite
simplificar a própria construção dos grafos e o próprio processo de alocação. Tal
situação é vulgar, por exemplo, para os processadores que separam por completo as
instruções/registos para inteiros e para vírgula flutuante.
Cor:
NºAdj:
Lst.Adj: ...
...
Cor:
NºAdj:
Lst.Adj: ∅
...
Cor:
NºAdj:
Lst.Adj: ...
...
Assim sendo e com base na própria representação proposta por Chaitin, achou-se por
bem utilizar uma matriz de adjacências, cuja única finalidade é assinalar a presença de
ramos entre vértices e que se adequa perfeitamente às pesquisas do tipo aleatório.
Como se trata de um grafo não orientado a matriz resultante é simétrica, pelo que na
prática apenas se utiliza a semi-matriz inferior (ou então a semi-matriz superior), de tal
forma que, dado dois índices i e j, correspondentes a dois vértices, então o valor na
posição ( i, j) = ( j, i) = AdjMtx[ max( i, j), min( i, j)].
No entanto, detecta-se que na maioria dos casos, o número de vértices é substancial e
que a relação entre esse número e o número médio de adjacentes por vértice é muito
elevada, fazendo com que a matriz de adjacências em determinadas circunstâncias seja
pouco eficiente, como por exemplo, quando é necessário determinar os adjacentes de
cada um dos vértices. Como tal, Chaitin propõe também e em simultâneo a utilização de
uma lista de adjacências, formada por uma sequência de listas, em que cada elemento da
sequência serve ainda para armazenar alguma informação referente a cada um dos
Ri a1 ... b1 ... Ri
Sem definições ou
... utilizações de a1 e b1.
... a1 ... b1
Fig. 6.3 – Exemplo com duas variáveis simultaneamente vivas, mas que aparentemente não
interferem uma com a outra.
Desta forma para uma dada variável, a função Interfere(...) verifica qual o conjunto
de registos cujos elementos podem ser utilizados para conter essa variável, o que é
determinado pela pré-selecção. Depois consultando o Register Table verifica quais os
registos que compõem esse conjunto e restringe a utilização de qualquer outro registo
que não se encontre aí incluído, colocando para tal ramos entre o vértice correspondente
à variável e os vértices dos registos que não pertençam ao conjunto.
Infelizmente para que este tipo de interferência funcione, é necessário que a variável
ao longo da sua “vida” ocupe sempre o mesmo tipo de registo, o que nem sempre é
verdade. Esta situação é bastante delicada, uma vez que as operações de troca entre
registos ocorrem ao nível das instruções e não da representação intermédia. E mesmo
que se tente introduzir um Assignment que represente essas trocas ao nível da MIR, o
que ocorre é que estes tendem a desaparecer através dos processos de optimização
(eliminação de cópias). Para além do mais, as trocas entre registos são operações que
não têm representação nas árvores de expressões e ao nível do selector de instruções
acabam por ficar camufladas (ver capítulo 7 - chain rules).
No actual estado do BEDS, este é um dos problemas que se encontra por resolver; a
solução mais viável é considerar a troca entre registos como uma nova definição
(AttribAssignment), que como tal e devido ao SSA, resultará numa variável
independente, à qual se pode atribuir um novo registo. De notar no entanto, que este
tipo de atribuição é feita a uma variável temporária, das que normalmente se encontram
associadas aos Assignments, onde representam os resultados dos nodos intermédios das
árvores de expressões. Como tal, esta nova forma de atribuição também deve permitir a
sua utilização na construção de outras árvores, sem no entanto perder a capacidade de
representar uma atribuição do tipo normalmente associado ao AttribAssignment.
É como tal imprescindível utilizar outros mecanismos para que se torne possível
concluir a coloração do grafo. Um método pessimista consiste em considerar que não
existe nenhuma combinação de cores que permita colorir o grafo. Pelo que a solução
passa pela sua reestruturação, de forma a que se torne possível obter um resultado
conclusivo. Uma das abordagens para a reestruturação, consiste em realizar o splitting
de uma ou mais variáveis, das que ainda se encontram representadas no grafo. O que
corresponde a decompor o período de “vida” útil de cada uma, em vários segmentos
mutuamente exclusivos, como se se tratassem de diversas variáveis, à semelhança do
que se faz para o SSA, mas agora aplicado de forma restrita.
A
V1 A – Azul
B – Branco
C - Castanho
C
B V2 V5 V4 B
V3
Fig. 6.4 – Exemplo de como é possível colorir um grafo com n=3 e todos os K ≥ 3.
Splitting
Existem outros métodos de remoção mais optimistas que, por exemplo, consideram
que é sempre possível obter uma solução que permita colorir o grafo, limitando-se,
como tal, a continuar a remover os vértices na esperança de que, aquando da atribuição
das cores tal pressuposto se confirme, caso contrário apelam ao splitting.
A coloração propriamente dita, só começa quando todos os vértices tiverem sido
removidos do grafo. Nesta fase pressupõem-se que estes foram armazenados
Um dos pontos críticos da alocação, está na selecção das variáveis a utilizar em caso
de ser necessário introduzir operações de splitting. Uma má selecção pode levar a
incluir uma série de instruções que em nada resolvam o processo de coloração do grafo,
deteriorando assim a qualidade final do código.
O objectivo é seleccionar a variável que, segundo a implementação do processo de
splitting, incorra na menor penalização possível. A solução ideal seria, como tal,
determinar o custo real do splitting das várias variáveis, mas devido à carga
computacional tal torna-se completamente inviável.
A forma mais simples para se determinar o custo de splitting, consiste em utilizar o
número de definições e de utilizações de cada uma das variáveis, de tal forma que:
Custospill ( v i ) = ∑ f (def ) + ∑ f
def ∈vi
1
use∈vi
2 (use) Eq. 6.1
Devido à representação SSA, no BEDS cada variável possui uma só definição, pelo
que o primeiro somatório resulta sempre no mesmo valor, podendo como tal ser
removido.
É ainda necessário avaliar os potenciais benefício que podem resultar do splitting de
cada uma das variáveis, uma vez que este tipo de operação permite normalmente
diminuir o número de restrições que existem no grafo.
Os benefícios podem assim, ser medidos através do número de adjacentes que cada
vértice possui. Convém no entanto reparar que não se trata de uma relação linear e que
por vezes inflaciona de forma especulativa os benefícios decorrentes do splitting.
Assim, a variável seleccionada deve ser escolhida de entre as que compõem o grafo,
de tal forma que maximize o valor da seguinte equação:
Grau ( v i )
Custo final ( v i ) = Eq. 6.2
Custo spill ( v i )
1. Evitar colocar operações de load e de store dentro de estruturas cíclicas, uma vez
que a penalização é ainda maior.
5. E por último, não confiar que os quatro pontos anteriores sejam suficientes para
garantir um bom processo de inserção de instruções de splitting.
Com já foi referido, o BEDS também fornece mecanismos para realizar a alocação
ao nível local, mais propriamente dito ao nível de cada uma das árvores de expressões.
O processo inicia-se após se terem realizado todas as tarefas inerentes à
representação intermédia e já numa fase em que se pretende gerar o código final. Para
tal e à semelhança da alocação global, é necessário “linearizar” o grafo de controlo de
fluxo e realizar a selecção das instruções. Só que agora, a alocação é feita ao mesmo
tempo que a selecção, ou seja, para cada árvore de expressões determinam-se as
instruções a utilizar, alocando em seguida os registos necessários. O processo prossegue
com a próxima árvore.
Como já se viu, a selecção das instruções permite determinar o tipo de registos a
utilizar para cada operando. Com base nessa informação e caso existam registos livres
escolhe-se um e atribui-se, caso contrário, o algoritmo de alocação apela a uma série de
estratégias simples, mas que normalmente surtem efeito, de forma a conseguir concluir
o processo de alocação. Em casos extremos chega-se mesmo a recorrer a operações de
splitting.
Por defeito, cada registo é apenas utilizado ao nível da própria instrução em que se
insere, sendo libertado imediatamente após a sua conclusão. É como tal normal que
estes sejam reutilizados por diversas vezes numa mesma expressão.
A única excepção à regra anterior surge para a situação em que a informação contida
no registo deve transitar para a próxima instrução ou ser utilizada posteriormente numa
outra expressão.
Após a selecção das instruções invoca-se o alocador local, que percorre a árvore de
expressões numa travessia do tipo post-fix.
Fazendo uma breve revisão sobre a relação entre uma árvore de expressões e as
instruções, pode-se dizer que a cada nodo de uma árvore, na sua forma mais simples, se
encontra associado uma instrução cujos operandos são determinados, sintetizando os
resultados das suas sub-árvores e cujo resultado, dará por sua vez origem a um dos
operandos do nodo antecessor, pelo que os valores sintetizados, que transitam de nodo
para nodo, não são mais do que endereços de memória, constantes, registos, etc.
Os registos surgem assim através das transferências explícitas de valores de memória
ou de constantes para registos, normalmente representadas por instruções de load ou de
move, ou então como meio necessário para conter o resultado de uma instrução.
O processo de alocação, como já se disse, atravessa a árvore de expressões,
realizando para cada nodo, as seguintes operações:
A segunda e terceira hipótese, que só são utilizadas no caso da primeira não resultar,
aplicam-se de forma mutuamente exclusiva. A segunda consiste em verificar se existe
algum registo que se encontre alocado mas que não pertença à árvore em causa. Nesse
caso liberta-se esse registo indicando que a sub-árvore da qual resultou deixou de estar
processada. A terceira solução consiste em realizar o splitting cortando a árvore em
duas.
De notar que a segunda solução implica voltar a gerar código para a sub-árvore da
qual derivou o registo que foi libertado, o que pode acarretar custos elevados. A terceira
solução consiste em inserir um store do resultado da sub-árvore onde ocorreu a falha do
registo e posteriormente um load a carregar esse mesmo resultado para o operando por
onde se dividiu a árvore.
Os custos de ambas as soluções encontram-se determinados pelo processo de
selecção das instruções, como se poderá ver no capítulo seguinte.
De princípio a terceira solução é mais económica, para além de que nem sempre é
possível aplicar a segunda, pois pode acontecer que não existem registos nas condições
exigidas. Só que por vezes não só existem, como apenas se limitam a realizar o load de
um valor, pelo que o custo associado é bastante baixo, sendo como tal preferível.
t1 t2 t3
r c r + r +
c r r r i
+1r
Expressões +2r
válidas +2i1+1c +
+2i1+2r
other
c r
+ 1 r
0 1 2 3 t2, t3
t1, t3
2 i 1 + 1 c
4 5 6 7 8 9
c r 2 r
13 t1 12 t2 10 11
t2, t3
Fig. 7.1 – Padrões e máquina de estados do top-down pattern matching.
De notar que o RHS, pode ser composto por operadores binários, unários e sem
operandos (neste último caso temos os símbolos terminais Reg e Int). Pode ainda conter
apenas um único símbolo não-terminal e neste caso diz-se tratar de regras em cadeia
(chain rules).
Os símbolos do LHS são sempre do tipo não-terminal, onde goal representa o não-
terminal objectivo a atingir para o nodo raiz da árvore.
A Fig. 7.2 representa a árvore de expressões para a qual se pretende determinar a
cobertura e o conjunto de acções a realizar. Associado a cada nodo encontra-se o estado
que o descreve, com tantas regras quantos os símbolos não-terminais da gramática.
Cada terminal (operador com zero operandos) possui um único estado, os restantes
(operadores unários e binários) podem possuir vários estados, dependendo o seu número
da combinação destes com os não-terminais de cada um dos operandos.
A título de exemplo, o estado do símbolo terminal Int é construído com base na regra
3, que deriva o não-terminal reg ao custo de 1 unidade e pela regra 7, que deriva o não-
De notar que um estado, só pode ser composto por regras de um mesmo operador ou
então por regras em cadeia. Estas últimas, como já se disse, são regras que se
caracterizam por possuir no RHS apenas um não-terminal (ex: #1, #6).
Após o labelling, é necessário realizar uma segunda travessia no sentido top-down,
para se seleccionar os padrões e se executar as respectivas acções. Neste caso e
pressupondo goal como o não-terminal objectivo para o nodo raiz, obtém-se então a
seguinte sequência de padrões e de acções:
Outro aspecto que acarreta algum cuidado é a própria representação destas estruturas,
que devem ser codificadas de forma a maximizar a velocidade de execução e minimizar
espaço ocupado. Alias, este último é um dos aspectos que todos os sistema tipo bottom-
up têm de considerar, uma vez que na maior parte dos casos, as tabelas de transição são
extremamente grandes. É, assim, habitual que estes sistemas se façam acompanhar por
mecanismos de compressão de tabelas e de minimização de estados [Chase87, DDH84].
Estudos mais detalhados de optimização do BURS, foram desenvolvidos por Henry
[FHP91, GHS82, HD89, Henry84, Henry89, Henry91], tendo este conseguido obter
técnicas, que apesar de bastante elaboradas, permitem reduzir o número de estados, o
que por si só reduz o espaço e o tempo de construção das tabelas.
Ao longo da próxima secção, pretende-se mostrar como obter os estados e construir
as tabelas de transições, bem como apresentar algumas das optimizações possíveis de
utilizar para aumentar a eficiência deste sistema.
Add
right #1 #2 #3 #4
left #1=Add(#1,#3)
#1 #1 #1=Add(#2,#3)
#2 #1 #4=Add(#4,#2)
#3
#4 #4
WorkList, para que também ele possa posteriormente ser processado. O ciclo repete-se
até que o conjunto Worklist se encontre vazio.
A função principal do algoritmo encontra-se representado na Fig. 7.5, através do qual
se pode verificar, que Worklist é uma estrutura do tipo stack e State, um conjunto, em
que alguma forma se salvaguarda a relação entre cada um dos seus elementos e os
índices das tabelas de transições. Operators é o conjunto de todos os operadores com
um ou mais operandos.
Proc Main( )
Var Global States : Set(Estados)
Var Global Worklist : Stack(Estados)
Var state : Estado
Var op : Operador
Início
States = ∅
Worklist = ∅
ComputeLeafStates( )
Enquanto Worklist ≠ ∅ Fazer
state = Pop(Worklist)
Para ∀ op ∈ Operators Fazer
ComputeTransitions(op, state)
FimPara
FimEnq
Fim
Como já foi dito, um estado deve conter a informação sobre as regras que permitem
sintetizar ao menor custo cada um dos símbolos não-terminais. Na prática, por cada
símbolo não-terminal, o estado possui um item composto pelo próprio símbolo não-
terminal, pela regra que o permite sintetizar e pelo respectivo custo. Caso este seja
infinito, significa então que a partir desse estado não existe nenhuma regra que derive
nesse não-terminal.
O custo de cada item de um estado necessita de ser normalizado, isto é, o seu valor
só deve depender do próprio estado e não do contexto onde este ocorre. O contra
exemplo desta situação, encontra-se representado na Fig. 7.2, onde o operador Fetch
possui dois estados distintos devido ao contexto em que está inserido. No entanto, como
ambos traduzem exactamente a mesma situação, devem então ser substituídos por um
único estado, representado da seguinte forma:
Consegue-se assim reduzir o número total de estados e como tal o tamanho das
tabelas e o tempo de geração das mesmas. De notar que este processo é fundamental
para que o número de estados não seja potencialmente infinito, o que inviabilizaria a
construção de todo o sistema.
Desta forma, o custo relativo ou custo delta é determinado subtraindo a cada não-
terminal o valor do de menor custo. O algoritmo de normalização encontra-se
representado na Fig. 7.6.
Os estados dos símbolos terminais determinam-se com base nas regras em que o
símbolo surge isolado do RHS da produção, retendo-se apenas as que permitem
sintetizar cada um dos não-terminais ao menor custo. Depois normalizam-se os custos e
aplicam-se as regras em cadeia na tentativa de se conseguir sintetizar os não-terminais
que ainda não foram alcançados através das primeiras regras, o que por si só, permite
aumentar o espaço de soluções do selector de instruções e por vezes reduzir os custos. O
processo termina após a inserção dos novos estados em State e em Worklist. O
algoritmo encontra-se representado na Fig. 7.7.
Proc ComputeLeafStates( )
Var leaf :Terminal
Var r : Regra
Var state : Estado
Var n : NãoTerminal
Início
Para ∀ leaf ∈ Leaves Fazer
state = ∅
Para ∀ r: n leaf Fazer
Se r.cost< state [n].cost Então
state [n] = {r.cost,r}
FimSe
FimPara
NormalizeCosts(state)
Closure(state)
WorkList = Append(WorkList, state)
States = States ∪ {state}
leaf.state = state
FimPara
Fim
A ideia base deste tipo de técnicas consiste em fazer com que dois ou mais estados
não idênticos o passem a ser, de forma a se poder eliminar um deles, acelerando assim o
processo de geração dos selectores, uma vez que se reduz o número de combinações
possíveis de se obter para cada operador e implicitamente o tamanho das tabelas.
Os algoritmos propostos por Proebsting e por Henry, divergem na forma como se
propõem alcançar estes objectivos. Mas ambos tentam eliminar todos os não-terminais,
para os quais se prove, que não existe nenhuma solução feita com base neles, que não
possa ser obtida através de outros não-terminais a um custo igual ou inferior. Com este
processo consegue-se eliminar alguns dos itens que compõem os estados, reduzindo
assim algumas das diferenças que possam existir. A remoção dos não-terminais não
deve afectar a capacidade de determinar a cobertura óptima de uma qualquer árvore de
expressões.
A técnica de Triangle Trimming verifica para todos os estados, se existe um par de
símbolos não-terminais ( i, j), tal que j possa substituir i, em qualquer dimensão de toda
e qualquer regra onde i é utilizado, produzindo o mesmo resultado mas a um custo não
superior. Nessa situação, i é removido do respectivo estado.
Diz-se então, que se para um dado operador op, existirem duas regras, r e t, onde seja
possível utilizar na dimensão d, respectivamente os não-terminais i e j (quer
directamente, quer por regras em cadeia), tal que:
i
⇓
Regra r: nr op ( pr,1 , ... , pr,d , ... , pr,arity)
⇑ ⇓ ⇓ ⇓ ⇓
Regra t: nt op ( pt,1 , ... , pt,d , ... , pt,arity)
⇑
j
É possível prova que j pode substituir i, se for possível derivar cada um dos pt,x a
partir de pr,x (pr,x⇒pt,x), para x =1...arity ∧ x≠d, e nr a partir de nt (nt ⇒ nr), de tal forma
que:
Exemplo 7.1
A Fig. 7.11 elucida o processo de compactação de tabelas utilizando vectores de
indexação, em que numa primeira fase reduzem-se as linhas e só depois as colunas da
tabela.
right
#0 #1 #2 #3 #4 #5 #6
#0
#1
left #2
#3
#4
#6 #7
#5
#6
O que a nível da tabela de transições, consiste em subtrair a-1 a cada elemento cujo
valor é diferente de nulo. Aquando da operação de labelling, ao valor obtido da tabela
adiciona-se a-1. Esta reformulação apenas compensa se b-a +1 < 256, o que permite
definir as tabelas com apenas um byte por elemento. Caso tal não aconteça, Henry, opta
por decompor a tabela de forma a que cada componente não indexe mais do que 256
estados distintos, para tal, há que antes realizar algumas permutas entre colunas e entre
linhas, de forma a minimizar os elementos em comum das várias sub-tabelas. A
decomposição faz-se segundo o esquema da Fig. 7.12.
Henry também utiliza os mecanismos de compactação de tabelas propostos por
Chase, mas ao contrário da implementação de Pelegri que trata as tabelas como
entidades individuais, Henry opta por as tratar como uma entidade única e tira proveito
disso, para compactar também os vectores de indexação. O Exemplo 7.2 ilustra como é
que tal acontece.
Exemplo 7.2
Pressupondo que de uma dada gramática e após a aplicação dos vectores de
indexação, resultaram as seguintes tabelas de transições:
Mul #0 #1 #2 #3 #4 #5 #6 #7 Plus #0 #1 #2 #3 #4 #5 #6 #7
f1 f4
#0 #0
#1 #1 PlusTable
#2 MulTable #2
#3 #3 #6 #7 ≡ #1 #2 + 5
#4 #5 ≡ #1 + 4 #4
#5 #5
#6 #6
#7 #7
f2 f3
Assign #0 #1 #2 #3 #4 #5 #6 #7 Fetch
f1
#0 #0
#1 #1
#2 AssignTable #2 FetchTable
#3 #3
#4 #1 ≡ #1 + 0 #4 #3 ≡ #1 + 2
#5 #5
#6 #6
#7 #7
f0 f0
Henry, para além dos vectores de indexação das tabelas de transições, codifica
também a informação sobre os estados, necessária para se determinarem as regras a
aplicar. Pressupondo então, que os estados obtidos para a gramática deste exemplo,
são os seguintes:
Estado nt Regra
reg 0
con 0
7 addr 5
x 0
y 0
Como os identificadores das regras podem assumir valores muito elevados e uma
vez que os valores por cada vector (fi) são muito próximos, aplica-se a reformulação
da Eq. 7.3.
♦
Henry desenvolveu várias outras optimizações, algumas das quais para o seu próprio
sistema, o CODEGEN. Julgo no entanto que as mais relevantes são as que aqui se
apresentaram, tanto que foram integradas na maior parte dos sistemas com base no
BURS.
7.5 IBURG
O BURS é sem dúvida um dos processos mais rápidos para realizar a selecção ou a
reescrita de árvores. É exactamente nestes dois aspectos, que residem as suas principais
vantagens. Infelizmente a estas contrapõem-se também algumas desvantagens, uma das
quais, advém do próprio processo para determinar os estados e gerar as tabelas de
transições, o qual é extremamente complexo, pelo menos quando se pretende obter
sistemas optimizados.
Mas mais inconveniente, pode ser a impossibilidade de avaliar o contexto de
execução em run-time, uma característica que é completamente antagónica à filosofia de
concepção do BURS, mas que pode ser extremamente importante para a implementação
de determinados sistemas, como é o caso da alocação de registos. Com a agravante, de
que a maioria dos selectores de instruções permite realizar este tipo de operações.
Uma solução de compromisso, de nome IBURG, foi desenvolvida por Fraser et al.
[FHP92] e partilha muitas das características do BURG, designadamente a gramática, o
processo bottom-up de labelling e o top-down de selecção das regras, e todo um
conjunto de pequenas operações. Aliás, quer Fraser, quer Proebsting, participaram
ambos na concepção do BURG e do IBURG.
Mas as diferenças também são relevantes, é que o IBURG ao optar por uma solução
mais hard-code, dispensa a construção das tabelas de transições e, em parte, dos
próprios estados. Como tal, deixa de ser necessário conhecer previamente o custo de
cada uma das regras da gramática.
Lógico que o sistema de reconhecimento se torna mais lento, mas com a vantagem de
permitir utilizar programação dinâmica para avaliar os custos em run-time. Convém no
entanto aqui esclarecer, que o IBURG só utiliza custos estáticos, mas que facilmente
podem ser substituídos por funções de custo.
struct state {
int op;
struct state *left, *right;
short cost[n_NT];
short rule[n_NT];
};
Exemplo 7.3
O seguinte trecho de código pertence à função state(...),obtida de uma gramática
que possui entre outros elementos, um operador (Plus), quatro regras, duas onde o
operador é utilizado e mais duas regras em cadeia ( reg:addr, con:addr), e ainda três
símbolos não-terminais, o reg (reg_NT), o addr (addr_NT) e o con (con_NT). As
variáveis p, left e right, representam respectivamente o estado do nodo actual, e os
descendentes esquerdo e direito.
case PLUS:
/* 10 reg: Plus( reg, addr) 2 */
c = leftcost[reg_NT] + rightcost[add_NT] + 2
if( c < p->cost[reg_NT]){
pcost[reg_NT] = c;
prule[reg_NT] = 10;
}
/* 11 addr: Plus( con, reg) 1 */
c = leftcost[con_NT] + rightcost[reg_NT] + 1
if( c < p->cost[addr_NT]){
pcost[addr_NT] = c;
prule[addr_NT] = 11;
/* 20 reg: addr 2 */
/* 21 con: addr 0 */
closure_addr(p);
}
♦
Se para um não-terminal ntx, existir pelo menos uma regra do tipo nty : ntx, então o
IBURG gera uma função de nome closure_ntx(p), em que dado um estado p, avalia se
Custo(nty : ntx) + pcost[ntx ] < pcost[nty] e se tal acontecer, substitui o custo de
Exemplo 7.4
Na continuação do exemplo anterior, temos a seguinte função de closure:
Pelo que já foi dito, verifica-se que nada impede a substituição do custo de cada uma
das regras por funções de custo, uma vez que não existe qualquer compromisso na
estrutura do algoritmo com os custos atribuídos aquando a especificação das regras.
A selecção das regras no IBURG não podia ser mas simples, uma vez que toda a
informação necessária encontra-se representada no próprio estado, pelo que basta
conhecer qual o não-terminal objectivo e realizar uma travessia top-down, para se
determinarem as regras a utilizar.
Apenas para compactar um pouco a forma de representar os estados, os autores do
IBURG utilizam vectores de regras, um por cada um dos símbolos não-terminais, mas
de tal forma, que cada vector contém apenas as regras que sintetizam determinado não-
terminal. O Exemplo 7.5 elucida esta situação.
Exemplo 7.5
Ainda dentro do contexto dos exemplos anteriores, seria possível obter os
seguintes vectores de regras:
struct state {
...
struct {
unsigned reg_nt:2;
unsigned addr_nt:2;
unsigned con_nt:2;
} rule;
};
Conseguindo assim reduzir o espaço ocupado por cada estado, o que pode no
entanto não ser muito relevante, pelo menos quando se considera apenas uma árvore.
Mas acontece por vezes ser necessário realizar o labellling a todas as árvores e só
depois é que se determinam as regras, como é o caso do sistema de alocação global
do BEDS, nestas circunstâncias e uma vez que estamos a falar de muitas árvore, este
sistema de compactação pode-se mostrar muito vantajoso.
♦
O BEDS não é por si só um sistema completo, quer quando visto como uma
ferramenta de apoio ao desenvolvimento de compiladores, ou como um conjunto de
componentes que podem integrar o compilador. Permite no entanto auxiliar o
desenvolvimento de algumas das suas componentes, quer gerando-as a partir de uma
descrição ou fornecendo-as directamente através de um conjunto de classes, as quais
devem ser parametrizadas à medida de cada caso.
Antes de se descreverem os passos essenciais à construção de um compilador, é de
todo conveniente esclarecer as diferentes fases temporais que envolvem o BEDS e a sua
aplicação ao desenvolvimento de compiladores. A fase primordial, que precede todas, é
a própria construção dos sistemas de geração de geradores, ou seja a construção do
BBEG e a implementação das classes que compõem o BEDS. Como não é directamente
relevante para a construção de um compilador não é aqui abordada.
A fase seguinte, que será considerada como primeira fase de um projecto para a
construção de um compilador, consiste em utilizar os mecanismos construídos na fase
anterior, designadamente o BBEG, para que com base numa descrição (especificação)
gere algumas das componentes que vão integrar o compilador. Componentes essas que,
por serem de alguma forma dependentes de factores externos ao BEDS, encontram-se
inacabadas, ou em stand-by, no processo de concepção e desenvolvimento.
...
Register Specification ...
Instruction Mapping Context Validation Functions
Instruction Specification Binary Code Generator Functions
Allocation System Type Cost Functions
BBEG
BEDS Class
Library
BEDS
Compiler
Como o BBEG foi concebido para ser completamente independente de qualquer uma
das restantes componente do BEDS, resulta que o código por ele gerado também se
mantém independente dessas rotinas, pelo que não é obrigado a partilhar com este as
mesmas estruturas de informação, designadamente as utilizadas na representação das
árvores de expressões, ou a forma como identifica os operadores, uma vez que por
defeito não existe qualquer relação entre os operadores das árvores que provêm do
front-end e os operadores definidos na especificação a utilizar pelo BBEG.
Foi como tal necessário definir uma interface que disciplinasse o diálogo entre ambas
as fases. Após várias experiências concluiu-se que esta deveria ser composta por duas
partes distintas, uma independente da especificação e que fornecesse os mecanismos de
acesso por defeito, e uma segunda parte, intrinsecamente dependente da especificação e
que permitisse tratar os casos pontuais, como por exemplo, o acesso a determinados
operadores/operandos, as funções de custo e de contexto, etc.
Para não comprometer as soluções utilizadas no front-end optou-se por implementar
a interface com base em macros, as quais devem ser fornecidas pelo utilizador, ou então
no caso deste pretender utilizar as rotinas geradas com os restantes módulos do BEDS,
pode, sob pedido explícito (na especificação), serem geradas pelo próprio BBEG.
As macros encontram-se divididas em dois grupos, um com as macros que permitem
o acesso aos campos das árvores de expressões e que são utilizadas por praticamente
todos os processos do back-end, mas fundamentalmente pelas funções de labelling; e
um segundo grupo, que comporta as macros utilizadas pelas rotinas de alocação e
geração de código. Integrada no primeiro grupo está ainda uma enumeração que permite
identificar os operadores das árvores de expressões.
As macros a utilizar por omissão nas operações de labelling, são:
Como já foi dito por inúmeras vezes, o BEDS integra a componente de alocação de
registos, permitindo meios para os descrever, disponibilizando depois essa informação
de forma a poder ser utilizada pelas rotinas de alocação, quer sejam locais ou globais.
Como o conjunto de registos varia de processador para processador e por vezes de
forma bastante distinta, torna-se difícil criar uma forma única e simples de os descrever.
/* Registos Simples */
typedef struct simplereg {
char *reg;
NODEPTR_TYPE p;
} SimpleRegister;
/* Registos Compostos */
typedef struct compreg {
char *reg;
int *comp;
NODEPTR_TYPE p;
} CompRegister;
Exemplo 8.1
Para um processador com quatro registos simples, R1, R2, R3 e R4, e dois registos
compostos D1 e D2, formados respectivamente por (R1,R2) e (R3,R4), obtêm-se as
seguintes estruturas de dados:
SimpleRegister bbeg_TERM[ ] = {
/* 1 */ “R1”, NULL,
/* 2 */ “R2”, NULL,
/* 3 */ “R3”, NULL,
/* 4 */ “R4”, NULL,
/* */ NULL, NULL,
};
CompRegister bbeg_COMPREG[ ] = {
/* 1 */ “D1”, compreg1, NULL,
/* 2 */ “D2”, compreg2, NULL,
/* */ NULL, NULL, NULL,
};
onde reg e creg apontam respectivamente para os vectores com os registos simples e
compostos que o não-terminal pode utilizar. O Exemplo 8.2 demonstra como empregar
esta estrutura.
Exemplo 8.2
Na continuação do exemplo anterior e pressupondo que existem três não-terminais
(nt1, nt2 e nt3), em que o primeiro tanto pode utilizar R3 como R4, o segundo não
utiliza qualquer registo e o terceiro pode utilizar apenas os registos compostos.
Obtêm-se então as seguintes estruturas de dados:
RegSet *bbeg_RegisterNTSet[ ] = {
/* 0 */ NULL;
/* nt1 */ &bbeg_nt1,
/* nt2 */ &bbeg_nt2,
/* nt3 */ &bbeg_nt3,
};
Há apenas a acrescentar que o utilizador pode requisitar ao BBEG para que este gere
todas estas estruturas de informação e respectivas definições com base nos dados da
especificação.
tal que:
em que term representa uma string válida segundo as convenções utilizadas para
representar os identificadores na linguagem C. As flags são descritas com base nas
seguintes produções:
lst_of_ops : lst_of_ops op / op .
Como se pode verificar, é possível associar a cada operador uma macro (function),
que permite aceder ao valor correspondente, ou no qual se traduz o operador. Estas
macros devem no entanto devolver um valor do tipo UValue, que não é mais que uma
união que comporta qualquer um dos tipos primitivos de dados da linguagem C. Pode-
se ainda associar a cada macro, o formato segundo o qual deve o valor ser imprimido e
que permite também indicar qual o campo da união a utilizar. No caso do formato não
ser fornecido, o valor é tratado como sendo do tipo decimal.
O utilizador pode optar por não indicar qualquer tipo de macro, nesta situação, quer o
valor a visualizar, quer o formato segundo o qual deve ser imprimido, são determinados
por síntese e segundo a regra que se aplica, utilizando as macros descritas na secção
8.2.1. É no entanto conveniente que se defina o formato dos operadores terminais, ou
seja, daqueles que não possuam operandos, uma vez que os restantes são determinados
por síntese com base nestes.
register : term .
term : IDENT .
def_set : term ';' / term '=' lst_of_elem ';' / term '=' function ';' .
Exemplo 8.3
Na continuação dos dois exemplos anteriores e pressupondo que existem apenas três
não-terminais que utilizam registos, um (reg) que de forma genérica usa qualquer
registo, outro (ireg) que apenas utiliza R1 e um terceiro (dreg) onde se utilizam os
registos compostos D1 e D2, obtém-se então a seguinte especificação:
OPERANDS:
regid : '$'CONST .
Como se pode verificar pelas produções, os padrões das regras apenas devem ser
descritos com base em operadores binários, unários ou sem operandos, e que é
necessário associar ao não-terminal que deriva da regra o campo de onde advém o seu
resultado (regid). Caso este seja $0 significa então que o resultado não advém de
nenhum dos elementos do RHS do padrão, devendo de princípio ser alocado ou obtido
através de uma macro. No caso de se pretender referir a algum dos elementos do RHS
($n, com n>0), a contagem deve ser feita começando em 1 e contando todos os
elementos, excepto parêntesis, quer estes sejam operadores ou operandos. O Exemplo
8.4 ilustra alguns casos desta situação.
Exemplo 8.4
RULES PATTERN:
RULE: reg < $0 > ::= con //Aloca ou calcula o valor de reg
...
EMIT: %{MOV $0, #$1\n%}
RULE: lab < $1 > ::= LABEL //Utiliza o valor do operando LABEL
...
EMIT: %{ LABEL $1\n%}
RULE: ireg < $2 > ::= ADDP(ireg,con) //Utiliza o valor do ireg do RHS
...
EMIT: %{ADDP $2, #$3\n%}
♦
O Exemplo 8.4 permite também verificar a utilização do EMIT que, como já se disse,
comporta uma string que admite campos sob a forma de $n, em que n refere um dos
elementos de RULE. Esta string aceita também os caracteres especiais normalmente
utilizados em funções como o printf(...). O Apêndice A ilustra alguns casos da
especificação de um hipotético processador.
>bbeg file.spec
NOTA: De forma a não alongar mais esta descrição, ao longo deste capítulo não se
apresentam os métodos que o front-end deve invocar para realizar as funções
pretendidas, mas apenas uma breve descrição. Caso seja necessário identificar
alguns dos métodos, aconselha-se a consulta do protótipo da respectiva classe
no Apêndice D.
Programa
Um dos primeiros passos que o front-end deve fazer para construir a RI do programa
que está a compilar, é criar a estrutura de suporte à própria representação, a qual servirá
para armazenar toda a informação referente ao programa, biblioteca, ou conjunto de
funções. Assim, o front-end deve ser dotado de meios para instanciar um objecto da
classe Program e implicitamente da classe IdentifierTable (instanciar e registar). Estes
dois objectos vão comportar todos os elementos globais, quer estes sejam funções,
variáveis, ou código de nível global, os quais de princípio são tratados de forma
semelhante aos elementos correspondentes das funções, procedimentos ou blocos de
código que se descrevem mais adiante.
FlowNodes
Na maior parte das situações o que o front-end identifica no código fonte são
expressões, que podem ser simples atribuições ou até estruturas condicionais. Neste
último caso o front-end deve ser dotado de meios para construir através de objectos
FlowNode a estrutura condicional equivalente.
De forma geral deve ser capaz de registar cada um dos nodos na função e depois,
caso se trate do nodo inicial ou final, deve ainda assinalar tal facto, e nunca esquecer
que cada FlowNode possui uma Label que deve ser convenientemente tratada.
Os restantes passos dependem da natureza do FlowNode, assim para o caso mais
simples, o JumpNode, há que tratar da operação de salto (Jump); no caso do
ConditionalJump há que tratar do salto condicional (CondJump); e no caso do
ReturnNode da operação de retorno (Return).
DataTransfers
Independentemente de ser ou não uma expressão condicional, o front-end deve ser
capaz de construir a respectiva representação em MIR. O que passa por instanciar, quer
objectos da classe DataTransfer, quer da classe Expressions. Em relação aos primeiros
podem ocorrer alguns problemas de interpretação, é que faz falta perceber em que é que
consiste um DataTransfer para se saber como os instanciar. Assim e seguindo a ideia
original do RTL, os DataTransfer devem assinalar toda e qualquer troca entre dados,
decompondo para tal as expressões nas operações mais básicas possíveis. Tudo isto para
salientar que é necessário alguns cuidados na implementação, no front-end, dos
mecanismos que vão permitir instanciar este tipo de objecto.
Todos os DataTransfers devem ser registados no nodo ao qual pertencem, ou seja, de
serem incluídos no nodo. Requer-se ainda que se defina o tipo concreto de
DataTransfer (Assignment, AtribAssignment, etc).
O Assignment necessita ainda que se actualize o source; o AttribAssignment que se
indique o target e o Register no qual resulta a expressão a atribuir; o JumpAssignment
que se indique a Label para onde se destina o salto; o CondJumpAssignment que se
indiquem as duas Labels destino, mais a expressão de teste; o ReturnAssignment
necessita da expressão da qual resulta o valor a devolver; o CallAssignment necessita de
conhecer a função a que se destina a operação de call e a lista de argumentos a passar; o
LabelAssignment dispensa qualquer tratamento interno; e o PhyAssignment deve ser
inserido e actualizado pelas rotinas próprias para a inserção deste tipo de DataTransfer.
Expressions
São quatro os procedimentos fundamentais a realizar pelo front-end para um
qualquer objecto do tipo Expression: primeiro registar a expressão no DataTransfer que
assinala o resultado da operação; segundo definir os identificadores dos operadores (só
no caso de não se utilizar os valores atribuídos por defeito); terceiro definir o tipo do
resultado da expressão; e quarto designar os descendentes da expressão caso estes
existam. As expressões do tipo Constant necessitam que se defina o seu valor e o
Register e o Memory que se indique a variável que representam (CellIDTable).
Convém aqui assinalar que o BEDS fornece uma tabela de conversão de tipos, em
que dado o tipo dos operandos, devolve o tipo do resultado, segundo as convenções
utilizadas na linguagem C.
Dotar o front-end de mecanismos que permitam executar todos os procedimentos até
aqui descritos como obrigatórios, permite manter actualizadas, aquando da compilação,
a maior parte das estruturas de dados, como é o caso do flowDependents ou do
flowSupporters. Há no entanto algumas estruturas que só podem ser preenchidas após a
construção da representação intermédia.
Structural Analyser
As rotinas de análise estrutural aplicam-se ao nível de cada função e limitam-se a
construir a árvore de controlo de fluxo, devolvendo-a sob a forma de um IntervalNode.
Esta rotina é fundamental para qualquer um dos processos que necessitam dos
mecanismos mais relacionados com o back-end, tais como o labelling, a alocação local,
a atribuição de registos, etc.
Tree Selector
Este módulo, como já se disse, permite obter a representação linear das expressões
do grafo de controlo de fluxo. Para tal, recorre à análise anterior para obter a árvore de
controlo de fluxo e depois com base nesta obtém a lista de árvores de expressões. Esta
pode ser acedida árvore a árvore ou requisitando a lista completa.
De notar que este processo não destrói a representação intermédia apenas permite
uma forma diferente de visualizar a organização das árvores de expressões.
Instruction Labelling
A operação de labelling realiza-se ao nível de cada árvore de expressões. Caso se
pretenda realizar para uma função, há primeiro que linearizar o respectivo grafo,
recorrendo ao Tree Selector.
Global Allocator
O processo de alocação global é substancialmente mais complexo, uma vez que
implica que se realize de antemão, a análise do período de vida útil e depois o labelling
de todo o grafo, o que por si implica obter a árvore de controlo de fluxo e a respectiva
linearização. Em seguida as rotinas constroem o grafo de interferências e tentam colori-
lo. Se tudo correr bem basta realizar a atribuição dos registos, caso contrário há que
fazer o splitting de uma das variáveis, inserindo as operações necessárias e depois
modificar os reticulados obtidos através da análise do período de vida útil, e voltar a
construir o grafo de interferências, até que se consiga obter uma solução estável. No
entanto, ao utilizador cabe apenas executar a análise do período de vida útil e depois
utilizar a classe Collor_Allocator.
Optimizer::Optimizer( )
Optimizer
Optimizer::EliminateUnreachebleCode( )
Optimizer::MaximizingBasicBlocks( )
Optimizer
B
A Structural StructuralAnalysis::StructuralAnalysis( )
StructuralAnalysis::Analize( )
C Analyser
K
TreeSelector::TreeSelector( )
Tree Selector TreeSelector::initTreeSelector( )
E
TreeSelector::buildList( )
N
D
Instruction Labelling( ) StateTable
Labelling
Register Allocator( )
Allocator
Machine
RegisterSet BBEG
Description
Register RegAssigner( )
Assigner
Fig. 8.2 – Sequência das operações para um back-end com alocação local.
Local Allocator
As rotinas de alocação local só se encontram presentes caso se tenha activado,
aquando a especificação, a flag RTLSALLOCATOR. Estas funcionam em simultâneo
com as operações de labelling, sendo como tal executadas sempre que esta operação é
utilizada. Caso se tenha activado esta flag, mas não se pretenda utilizar as rotinas de
alocação local, basta colocar a variável LRAllocator a falso, o que deve ser feito
directamente no ficheiro backend.c.
Code Emiter
Após a conclusão com êxito da selecção e da alocação, o front-end deve, para
terminar a cmpilação, invocar o Code Emiter de forma a gerar o código em assembly
(ou binário).
Como se pode constatar pelo capítulo 3, o modelo apresentado para o BEDS ainda
não comporta a geração do código binário, ou pelo menos, não disponibiliza os
mecanismos necessários ao desenvolvimento desta fase do processo de compilação. De
forma a compensar esta lacuna, decidiu-se apresentar uma ferramenta concebida
unicamente com o objectivo de auxiliar a implementação dos meios para geração de
código binário, o New Jersey Machine-Code Toolkit (NJMCT), fornecendo assim uma
solução completa para a concepção de back-ends,
Este capítulo começa por uma breve descrição desta ferramenta, após a qual se
descrevem os mecanismos que disponibiliza para o desenvolvimento de geradores de
código binário. Conclui explicando como é que se interligam as componentes obtidas
com as restantes fases do processo de compilação.
{} - Identificador de repetição
[] - Identificador de opção
| - Identificador de alternativa
Axioma { Espec}
Exemplo 9.1:
<8051.spec> ≡
<fieldinfo>
<pattern>
<constructor>
<assembly_opcode>
<assembly_operand>
<assembly_syntax>
É ainda possível associar a cada um dos fields alguns atributos pré-definidos que
activam, aquando da invocação das funções, a execução de determinados
procedimentos. A sintaxe a utilizar obedece à seguinte gramática:
field-item checked
| unchecked
| guaranteed
| sparse [binding {,binding}]
| names [{Indent | String}]
unchecked - Faz com que a função de codificação crie uma máscara para
proteger os bits do token que não pertencem ao field.
Exemplo 9.2
<fieldinfo> ≡
A principal função dos patterns é permitir atribuir valores aos fields, o que pode ser
feito com base num vasto conjunto de operações, recorrendo inclusivamente à utilização
de outros patterns. É como tal uma das componentes da linguagem com maior poder
descritivo.
A definição dos patterns obedece à seguinte gramática:
Os patterns são definidos com base em elementos simples, tais como fields, tokens,
ou através dos respectivos valores binários. Para tal utilizam-se as seguintes expressões
gramaticais:
generating_expression { lo to hi}
| { lo to hi columns n}
| [{integer}]
É ainda possível definir os patterns com base noutros patterns, em que para tal
utilizam-se as seguintes expressões:
Nas duas primeiras opções, o novo pattern é definido parcialmente com base no
pattern do RHS, em que no primeiro caso substitui alguns dos bits iniciais e no segundo
os últimos bits. As outras três opções seguintes correspondem à conjunção, sequência e
disjunção de patterns.
Exemplo 9.3
<pattern> ≡
patterns
ajc is any of [ajmp acall], which is op5 = [17 1]
djnz is op1 = 13
mov is some CodeOp
binary-operator +|-|*|/
Exemplo 9.4
<constructor> ≡
constructors
Como se viu no exemplo anterior, ajc tanto pode representar ajmp ou acall, pelo
que a primeira declaração dá origem a duas funções de codificação distintas, a
ajmp(...) e a acall(...), cada uma com um único parâmetro que é atribuído ao field
arg11. Ambas codificam a instrução binária através da conjunção de ajc com o
campo op7, concatenando o resultado com op8. O valor de ajc é obtido a partir de
ajmp ou de acall, enquanto que o valor de op7 e op8 é determinado respectivamente
com base nos 3 bits mais significativos e nos 11 bits menos significativos de arg11.
O segundo construtor define uma função, cujo nome provém da concatenação das
strings “djnz” com “REr” e que resulta em djnzREr(x,y). Onde x e y correspondem
respectivamente a op8 e a arg8. A instrução a emitir pela função consiste na
concatenação de arg8 com a conjunção dos seguintes padrões djnz, op2 e op8. O
valor de op2 é definido na própria declaração do construtor e é igual a 1.
♦
NOTA: A partir deste ponto e apenas para facilitar a descrição, considera-se que o
translator converte as instruções máquina para assembly.
Espec assembly-opcode-syntax
assembly-operand-syntax
assembly-syntax
Exemplo 9.5
<assembly_opcode>≡
assembly component
{o,a}w is w
*b is b
{*}A is $1
Exemplo 9.6
<assembly_operand>≡
assembly operand
Exemplo 9.7
<assembly_syntax>≡
assembly syntax
onearg^”A” "A"
xch^”AR” "A”, op8
cujo conteúdo não pode ser acedido directamente mas apenas copiado para um ficheiro
ou buffer. O acesso para escrita faz-se através das funções que emitem as instruções.
De notar, que podem existir vários relocatable blocks em utilização, mas só um é que
se encontra activo.
O campo rb.label é uma estrutura (RLabel) que permite armazenar as características
mais relevantes de uma label, a qual é formada pelos seguintes campos:
Um relocatable block, para além de rb.label, pode conter tantas labels quantas as
necessárias.
O mclib.h disponibiliza também diversas funções que permitem emitir as instruções
para rb.contents. De notar que estas são utilizadas pelas próprias funções de
codificação. A emissão de uma instrução incrementa automaticamente o rb.lc do bloco
activo e se necessário aumenta o rb.contents.
Como já se viu, se a instrução a emitir utiliza um endereço que ainda não foi
determinado, então na posição por ele a ocupar é colocado um placeholder, que tem por
finalidade reservar o espaço necessário ao endereço. A nível dos mecanismos internos
do NJMCT é declarada uma estrutura para reter a informação necessária à manutenção
do placeholder (RClosure), a qual é composta pelos seguintes campos:
O mclib.h contém várias outras funções e estruturas, para além das atrás referidas.
Optou-se, no entanto, por apresentar apenas aquelas que são mais relevantes. Convém
ainda referir que o utilizador é responsável por definir e implementar algumas estruturas
e funções, como é o caso dos procedimentos de alocação do espaço para o rb.contents.
9.4 Resumo
10 Conclusão
Durante o longo período em que decorreu o trabalho desenvolvido para esta tese,
houve uma grande reformulação das noções sobre a concepção e estrutura de um
compilador.
Começou-se com uma abordagem extremamente simplista, resumindo um
compilador a um conjunto de processos, formado pela análise léxica, sintáctica e
semântica, aos quais se seguia uma pequena fase de geração de código, que se pensava
ter a ver com pouco mais do que a selecção de instruções e atribuição de registos.
Apesar do conhecimento inicial ser algo limitado, o mesmo não se podia dizer dos
objectivos, os quais se propunham a obter soluções completas que permitissem a
automatização das fases do compilador inerentes à geração de código, à semelhança do
que existia para a análise léxica, sintáctica e semântica.
Assim, começou-se por estudar as soluções existentes, analisando o seu modo de
funcionamento, avaliando as potencialidades e medindo a eficiência. Foram alvo deste
processo ferramentas como o BURG, IBURG, BEG, NJMCT, algumas componentes do
GCC, etc.
Após esta fase constatou-se que o modelo de compilador até aí utilizado, não
permitia distrinçar de forma clara alguns processos fundamentais, tais como alocação
(distribuição) dos registos e optimização de código.
Foi como tal necessário rever os conceitos iniciais, estudar outras soluções (RTLS,
GCC, COSY, etc) e formalizar, não só um modelo para o compilador, como também
algo que era intrínseco a todas as fases, que é a forma da representação do código.
Surgiu assim a My Intermediate Representation e mais genericamente o Back-End
Development System, à volta dos quais está todo o trabalho desenvolvido para esta tese
de mestrado.
Como foi possível constatar ao longo dos últimos sete capítulos, o BEDS propõe-se a
fornecer, através de bibliotecas e de módulos gerados, tudo o que é necessário para
Como já atrás foi dito, o BEDS está longe de estar concluído, quanto mais não seja
porque ainda não houve qualquer fase de teste e avaliação dos resultados, excepção feita
a alguns casos pontuais utilizados para detectar e corrigir erros de implementação. Para
além disso, existem situações que ainda não foram contempladas e que apesar de não
serem fundamentais aos processos já existentes, é de todo conveniente a sua
concretização, quanto mais não seja para que o BEDS deixe o estado embrionário em
que se encontra e passe a ocupar uma posição no universo das soluções que existem
nesta área.
Das situações fundamentais a iniciar, ou a concluir, faz parte o desenvolvimento de
um conjunto de front-ends para as linguagens mais utilizadas, não só como forma de
incentivar a utilização do BEDS, como também para avaliar até que ponto a MIR
garante os mecanismos necessários à representação de código intermédio, isto para além
daqueles que já se sabem faltar, como é o caso da representação de arrays, estruturas e o
tratamento de tipos. Convém ainda verificar o comportamento da MIR em relação aos
apontadores.
É ainda necessário verificar os processos de análise já implementados e
eventualmente construir outros processos, tais como a análise de dependência de dados
e de aliases. Depois, e como forma de rentabilizar essas formas de análise, faz falta
desenvolver todo um conjunto de optimizações que são consideradas como
fundamentais à grande maioria dos compiladores modernos.
A nível dos processos de alocação é imprescindível testar as soluções fornecidas,
utilizando outras arquitecturas, de forma a verificar a eficiência da representação dos
registos e das próprias rotinas de alocação.
Na selecção de instruções são potencialmente poucas as melhorias que se possam
realizar, uma vez que as soluções utilizadas foram largamente testadas, quer no BEDS,
quer em vários outros selectores de instruções. O mesmo já não se pode dizer em
relação à linguagem de especificação, a BBEGL. Esta não só exige que se avalie a sua
capacidade descritiva, como eventualmente se a modifique de forma a fornecer ao
utilizador maior intervenção e simultaneamente que permita simplificar o processo de
descrição.
É ainda fundamental expandir a BBEGL (e simultaneamente o BEDS) para
comportar a descrição do código binário e da relação deste com as expressões da
representação intermédia, e posteriormente gerar o próprio gerador de código binário.
Para além dos aspectos anteriores, existem outros que só e simplesmente não foram
explorados, tais como: optimização de acessos à memória cache; rentabilização de
arquitecturas multi-pipelining e super-escalares; utilização de técnicas para
processamento paralelo; obtenção da informação necessária à construção do back-end a
partir da descrição VHDL do processador; etc.
Julgo que auge do BEDS será eventualmente alcançado, quando este permitir gerar
as rotinas necessárias a todas as fases atrás descritas, incluindo a optimização, com base
numa simples especificação do que estas devem realizar e em que fase do processo de
compilação o devem fazer.
Esperando que o trabalho realizado possa vir a ser útil a alguém e que consiga cativar
alguns adeptos, deixo desde já expressa a minha disponibilidade para prestar qualquer
esclarecimento e porque não contribuição, dentro das áreas abrangidas pelo trabalho
desenvolvido nesta tese de mestrado.
Bibliografia
[AC75] Aho, A.V. and Corasick, M.J. 1975. Efficient string matching: An aid to
bibliographic search. Communication ACM 18, June, pp. 333-340.
[AG86] Aho, A.V., and Ganapathi, M. (1986). Efficient tree pattern matching: An
aid code generation. In Proceedings of the (13)th ACM Symposium on
Principles of Programming Languages. ACM, New York, pp. 334-340.
[AGT89] Aho, A.V., Ganapathi, M. e Tjiang, S.W. 1989. Code generation using tree
matching and dynamic programming. ACM Transactions on Programming
Languages and Systems, 4(Oct), pp. 491-516.
[AJ76] Aho, A.V. and Johnson, S.C. 1976. Optimal code generation for expression
trees. Journal ACM 23:3, pp. 488-501.
[APCEB96] Auslander, J., Philipose, M., Chambers, C., Eggers, S.J. and Bershad,
B.N. 1996. Fast, effective dynamic compilation. Proceedings of the ACM
SIGPLAN ’96 Conference on Programming Language Design and
Implementation, pp. 149-159.
[AS87] Appel, A.W. and Supowit, K.J. 1987. Generalizations of the Sethi-Ullman
algorithm for register allocation. Software-Practice and Experience, Vol. 17,
6 (June), pp. 417-421.
[ASU86] Aho, A.V., Sethi, R., and Ullman, J.D. 1986. Compilers: Principles,
Techniques, and Tools. Addison Wesley, Reading, MA.
[BCKT89] Briggs, P., Cooper, K.D., Kennedy, K. and Torczon, L. 1989. Colouring
heuristics for register allocation. ACM, Department of Computer Science,
Rice University, Houston.
[BCT92] Briggs, P., Cooper, K.D. and Torczon, L. 1992, Colouring register pairs.
ACM Letters on Programming Languages and Systems, Vol. 1, 1 (March),
pp. 3-13.
[Bernstein, et al] Bernstein, D., Goldin, D., Golumbic, M., Krawczyk, H., Mansour, Y.,
Nahshon, I. and Pinter, R. 1989. Spill code minimization techniques for
optimizing compilers. ACM, IBM Israel Science and Technology, Haifa,
Israel.
[BGS94] Bacon, D.F., Graham, S.L. and Sharp, O.J. 1994. Compiler transformations
for high-performance computing. ACM Computer Surveys, Vol. 26, 4
(Dec), pp. 345-420.
[BM??] Brandis, M.M. and Mossenbock, H. Single Pass Generation of Static Single
Assignment Form for Structured Languages. Extraído da Internet.
[BMW91] Borstler, J., Moncke, U. and Wilhelm, R. 1991. Table Compression for tree
automata. ACM Transactions on Programming Languages and Systems,
Vol. 13, 3(July), pp. 295-314.
[BSM87] Biljon, W.R., Sewry, D.A. and Mulders, M.A. 1987. Register allocation in a
pattern matching code generator. Software-Practice and Experience, Vol.
17, 8 (Aug), pp. 521-531.
[Buck94] Buck, J.T. 1994. Static scheduling and code generation from dynamic data
flow graphs with integer-valued control streams. In Proceedings of 28th
Asilomar Conference on Signals, Systems, and Computers.
[CCMH91] Chang, P.P., Chen, W.Y., Mahlke, S.A. and Hwu, W.W. 1991. Comparing
static and dynamic code scheduling for multiple-instruction-issue
processors. ACM.
[CACCHM81] Chaitin, G.J., Auslander, M.A., Chandra, A.K., Cocke, J., Hopkins,
M.E., and Markstein, P.W. 1981. Register allocation via colouring.
Computer Languages 6, 1(Jan.), pp.47-57.
[CFRWZ91] Cytron, R., Ferrante, J., Rosen, B.K., Wegman, M.N. and Zadeck, F.K.
1991. Efficiently Computing Static Single Assignment Form and the
Control Dependence Graph. ACM Transactions on Programming
Languages and Systems, 13(April), pp. 451-490.
[CH90] Chow, F.C. and Hennessy, J.L. 1990. The priority-based colouring approach
to register allocation. ACM Transactions on Programming Languages and
Systems, Vol. 12, 4(Oct), pp. 501-536.
[Chait82] Chaitin, G.J. 1982. Register allocation and spilling via graph colouring. In
Proceedings of the SIGPLAN Symposium on Compiler Construction.
Boston, Mass. ACM SIGPLAN Notices 17, 6(June), pp. 98-105.
[DDH84] Dencker, P., Durre, K. and Heuft, J. 1984. Optimization of parser tables for
portable compilers. ACM Transactions on Programming Languages and
Systems, Vol. 6, 4(Oct), pp. 546-572.
[DF80] Davidson, J.W. and Fraser, C.W. 1980. The Design and Application of a
Retargetable Peephole Optimizer. ACM Transactions on Programming
Languages and Systems, Vol. 2, 2(April), pp. 191-202.
[DF84a] Davidson, J.W. and Fraser, C.W. 1984. Code selection through object code
optimization. ACM Transactions on Programming Languages and Systems,
Vol. 6, 4(Oct), pp. 505-526.
[DF84b] Davidson, J.W. and Fraser, C.W. 1984. Register allocation and exhaustive
peephole optimization. Software-Practice and Experience, Vol. 14, 9(Sept),
pp. 857-865.
[EP??] Engler, D.R. and Proebsting, T.A. DCG: An efficient, retargetable dynamic
code generation system. Extraído da Internet.
[EHK96] Engler, D.R., Hsieh, W.C. and Kaashoek, M.F. 1996. C: A language for
high-level, efficient, and machine-independent dynamic code generation. In
Proceedings of the 23th Annual Symposium on Principles of Programming
Languages. ACM, St. Petersburg, USA, pp. 131-144.
[FH90] Fraser, C. And Hanson, D. 1990. A code generation interface for ANSI C.
Research Report CS-TR-270-90.
[FHP91] Fraser, C.W., Henry, R.R. and Proebsting, T.A. 1991. BURG – Fast optimal
instruction selection and tree parsing. ACM SIGPLAN Notices, Vol. 27, 4
(April), pp. 68-76.
[FHP92] Fraser, C.W., Hanson, D.R. and Proebsting, T.A. 1992. Engineering
efficient code generators using tree matching and dynamic programming.
Research Report CS-TR-386-92.
[FOW87] Ferrante, J., Ottenstein, K.J. and Warren, J.D. 1987. The program
dependence graph and its use in optimization. ACM Transactions on
Programming Languages and Systems, Vol. 9, 3 (July), pp. 319-349.
[Fras89] Fraser, C.W. 1989. A language for writing code generators. ACM, AT&T
Bell Laboratories.
[FSW94] Ferdinand, C., Seidl, H. and Wilhelm, R. 1994. Tree automata for code
selection. Acta Informática, 31, pp. 741-760.
[FW88] Fraser, C.W. and Wendt, A.L. 1988. Automatic generation of fast
optimizing code generators. Proceedings of the ACM SIGPLAN ‘88
Conference on Programming Language Design and Implementation,
Atlanta, Georgia, pp. 79-84.
[GE90] Grosch, J. and Emmelmann, H. 1990. A tool box for compiler construction.
Project Compiler Generation, Report nº20, University Karlsruhe.
[GE85] Ganapathi, M. e Fischer, C.N. 1985. Affix grammar driven code generation.
ACM Transactions on Programming Languages and Systems, vol. 7, 4
(Oct), 560-599.
[GF88] Ganapathi, M. and Fischer, C.N. 1988. Integrating code generation and
peephole optimization. Acta Informática, 25, pp. 85-109.
[GG78] Glanville, R.S. and Graham, S.L. 1978. A new method for compiler code
generation. In Proceedings of the 5th Annual Symposium on Principles of
Programming Languages. ACM, New York, pp. 231-240.
[GHAMP84] Glanville, S.L., Henry, R.R., Aigrain, P., Mckusick, M., and Pelegri-
Llopart, E. 1984. Experience with a Graham-Glanville style code generator.
Proceedings of the ACM SIGPLAN Symposium on Compiler Construction,
ACM SIGPLAN Notices, vol.19, nº 6 (June), pp. 13-24.
[GHKSW90] Gray, R., Heuring,V., Kram,S., Sloam, A. and Waite,W. 1990. Eli: A
complete, flexible compiler construction system. Research report,
University of Colorado, Boulder.
[GHS82] Graham, S.L., Henry, R.R. and Schulman, R.A. 1982. An experiment in
table driven code generation. ACM SIGPLAN Noticves 17, 6 (June), pp.
32-43.
[Glan77] Glanville, R.S. 1977. A machine independent algorithm for code generation
and its use in retargetable compilers. Ph. D. Dissertation, University of
California, Berkeley.
[GSO94] Gupta, R., Soffa, M.L. and Ombres, D. 1994. Efficient register allocation
via colouring using clique separators. ACM Transactions on Programming
Languages and Systems, Vol. 16, 3 (May), pp. 370-386.
[HC86] Hatcher, P.J. e Christopher, T.W. 1986. High quality code generation via
bottom-up tree pattern matching. In Proceedings of the 13th Annual
Symposium of Principles of Programming Languages. ACM, pp. 119-129.
[HD89] Henry, R.R. e Damron, P.C. 1989. Performance of table driven code
generators using tree pattern matching. Tech. Rep. 89-02-02, Univ. of
Washington, Seatle, Wash.
[Henry89] Henry, R.R. 1989. Encoding optimal pattern selection in a table driven
bottom-up tree pattern matcher, Tech Rep. 89-02-04, Univ. of Washington,
Seatle, Wash.
[Henry91] Henry, R.R. 1991. Hard-coding Bottom-up Code Generation Tables to Save
Time and Space, Software-Practice and Experience, vol. 21, 1(Jan), pp. 1-
12.
[HKC84] Hatcher, P.J., Kukuck, R.C. and Christopher, T.W. 1984. Using dynamic
programming to generate optimized code in a Graham-Glanville style code
generator. In Proceedings of the ACM SIGPLAN Symposium on Compiler
Construction, ACM SIGPLAN Notices 19, 6 (June), pp. 25-36.
[HO82] Hoffmann, C.M. e O'Donnell, M.J. 1982. Pattern matching in trees. J. ACM
29, 1(Jan), pp. 68-95.
[JML91] Johnson, R.E., McConnell, C. e Lake, J.M. 1991. The RTL System: A
framework for code optimization. Proceedings of the International
Workshop on Code Generation, Dagstuhl, Germany, 5(May), pp. 255-274.
[KH93] Kolte, P. and Harrold, M.J. 1993. Load/Store range analysis for global
register allocation. Proceedings of the ACM SIGPLAN ’93 Conference on
[KPF95] Kurlander, S.M., Proebsting, T.A. and Fischer, C.N. 1995. Efficient
instruction scheduling for delayed-load architectures. ACM Transactions on
Programming Languages and Systems, Vol. 17, 5 (Sep), pp. 740-776.
[KRS94] Knoop, J., Ruthing, O. and Steffen, B. 1994. Optimal code motion: theory
and pratice. ACM Transactions on Programming Languages and Systems,
Vol. 16, 4 (July), pp. 1117-1155.
[LE95] Lo, J.L. and Eggers, S.J. 1995. Improving balanced scheduling with
compiler optimizations that increase instruction-level parallelism. ACM
SIGPLAN, La Jolla, USA.
[LDKT??] Liao, S., Devadas, S., Keutzer, K. and Tjiang, S. Instruction selection using
binate covering for code size optimization. ACM. Extraído da Internet.
[LDKTW??] Liao, S., Devadas, S., Keutzer, K., Tjiang, S. and Wang, A. Code
optimization techniques for embedded DSP microprocessors. ACM.
Extraído da Internet.
[MHL91] Maydan, D.E., Hennessy, J.L. and Lam, M.S. 1991. Efficient and exact data
dependence analyses. Proceedings of the ACM SIGPLAN ’91 Conference
on Programming Language Design and Implementation, Toronto, Ontario,
Canada, pp. 1-14.
[MRS90] McConnell, C., Roberts, J.D. and Schoening, C.B. 1990. The RTL System.
Departement of Computer Science, University Illinois at Urbana-
Champaign.
[MRS??A] McConnell, C., Roberts, J.D. and Schoening, C.B. 1990. Using SSA Form
in a Code Optimizer. Department of Computer Science, University Illinois
at Urbana-Champaign. Extraído da Internet.
[NG93] Ning, Q. and Gao, G.R. 1993. A novel framework of register allocation for
software pipelining. In Proceedings of the 20th Annual Symposium on
Principles of Programming Languages, ACM, pp. 29-42.
[NP??b] Norris, C. and Pollock, L.L. Register allocation over the program
dependence graph. Department of Computer and Information Sciences,
University of Delaware, Newark. Extraído da Internet.
[Patter95] Patterson, J.R.C. 1995. Accurate Static Branch Prediction by Value Range
Propagation. Proceedings of the ACM SIGPLAN Conference on
Programming Language Design and Implementation, La Jolla, San Diego,
pp. 67-78.
[PF92] Proebsting, T.A. and Fischer, C.N. 1992. Probabilistic register allocation.
Proceedings of the ACM SIGPLAN ´92 Conference on Programming
Language Design and Implementation, pp. 300-310.
[PF94] Proebsting, T.A. and Fraser, C.W. 1994. Detecting pipeline structural
hazards quickly. In Proceedings of the 21st Annual ACM SIGPLAN-
SIGACT Symposium on Principles of Programming Languages, pp. 280-
286.
[PF96] Proebsting, T.A. and Fischer, C.N. 1996. Demand-driven register allocation.
ACM Transactions on Programming Languages and Systems, Vol. 18, 6
(Oct), pp. 683-710.
[Pinter93] Pinter, S.S. 1993. Register allocation with instruction scheduling: a new
approach. Proceedings of the ACM SIGPLAN ´93 Conference on
Programming Language Design and Implementation, Albuquerque, pp. 248-
257.
[Proeb92b] Proebsting, T.A. 1992. Simple and Efficient BURS Table Generation. In
Proceedings of the 19th Annual Symposium on Principles of Programming
Languages. ACM, pp. 331-340.
[PTB??] Proebsting, T.A., Townsend, G. and Bridges, P. Toba: Java for applications,
a way ahead of time (WAT) compiler. University of Arizona. Extraído da
Internet.
[PW??] Proebsting, T.A. and Whaley, B.R. One-pass, optimal tree parsing – with or
without trees. Department of Computer Science, University of Arizona,
Tucson. Extraído da Internet.
[PWU97] Peleg, A., Wilkie, S. and Weiser, U. 1997. Intel MMX for multimedia PCs.
Communications of the ACM, Vol. 40, 1(Jan), pp. 25-38.
[RF94] Ramsey, N., and Fernández, M. 1994. New Jersey Machine-Code Toolkit
reference manual. Technical Report TR-471-94. Department of Computer
Science, Princeton University.
[RF95] Ramsey, N., and Fernández, M. 1995. The New Jersey Machine-Code
Toolkit. In Proceedings of the 1995 USENIX Technical Conference, pp.
289-302, New Orleans, LA.
[RF95a] Ramsey, N., and Fernández, M. 1995. New Jersey Machine-Code Toolkit.
Department of Computer Science, Princeton University, 15/12/95.
[RF96] Ramsey, N., and Fernández, M. 1996. New Jersey Machine-Code Toolkit
architecture specifications. Department of Computer Science, Princeton
University, 7/05/96.
[RLTS92] Rau, B.R., Lee, M., Tirumalai, P.P., Schlansker, M.S. 1992. Register
allocation for software pipelined loops. Proceedings of the ACM SIGPLAN
´92 Conference on Programming Language Design and Implementation, pp.
283-299.
[SKAH91] Smotherman, M., Krishnamurthy, S., Aravind, P.S. and Hunnicutt, D. 1991.
Efficient DAG construction and heuristic calculation for instruction
scheduling. ACM.
[Stallman94] Stallman, R. 1994. Using and porting GNU CC. Free Software
Foundation.
[SW94] Smith, J.E. and Weiss, S. 1994. PowerPc 601 and Alpha 21064: a tale of
two RISCs. IEEE Computer Journal, June, pp. 46-58
[VS95] Venugopal, R. and Srikant, Y.N. 1995. Scheduling expression trees with
reusable registers on delayed-load architectures. Computer Languages, Vol.
21, 1, pp. 49-65.
[Wall??] Wall, D.W. Global register allocation at link time. Digital Equipment
Corporation, Western Research Lab. Extraído da Internet.
[Wasil72] Wasilew, S.G. A compiler writing system with optimization capabilities for
complex order structures. Ph.D. dissertation, Northwestern University,
Evanston.
[Wilson, et al 94] Wilson, R.P., French, R.S., Wilson, C.S., Amarasinghe, S.P.,
Anderson, J.M., Tjiang, S.W., Liao, S.W., Tseng, C.W., Hall, M.W., Lam,
M.S. and Hennessy, J.L. 1994. The SUIF compiler system: A parallelizing
and optimizing research compiler. Technical Report CSL-TR-94-620,
Computer Systems Laboratory, Department of Electrical Engineering and
Computer Science, Stanford University.
[WKEE94] Wang, J., Krall, A., Ertl, M.A. and Eisenbeis, C. 1994. Software pipelining
with register allocation and spilling. Proceedings on MICRO-27, San Jose
CA, USA, pp. 95-99.
[YA95] Yeralan, S. and Ahluwalia, A. 1995. Programming and Interface the 8051
Microcontrolor. Addison-Wesley Publishing Company.
Gramática do BBEGL
/*--------------------------- gnr.con-------------------------------------*/
start_code : COD_C .
end_code : COD_C .
lst_of_ops : lst_of_ops op / op .
register : term .
term : IDENT .
def_set : term ';' / term '=' lst_of_elem ';' / term '=' function ';' .
regid : '$'CONST .
FLAGS:
SET RTLSINTERFACE;
SET RTLSGENERATOR;
SET RTLSALLOCATOR;
SET REGTABLES;
%{
/* versão 05.11.98 */
#include "main.h"
#include "Label.h"
OPERATORS:
LABEL = GETLABEL(),"%d";
CNST = GETCNST(),"%d";
MEM = GETMEM(),"%d";
ASGN;
ADD;
ADDP;
INDIR;
MUL;
DIV;
GT;
JUMP;
CJUMP;
ARG;
OPERANDS:
TERM = R0, R1, R2, R3;
reg = R0, R1, R2, R3;
ireg = R1;
dreg = D0<R2,R3>, D1<R0,R1>;
con;
addr;
nop;
lab;
AXIOM = addr;
RULES PATTERN:
END ;
%{
%}
- Operações aritméticas
- Operações lógicas
- Operações de transferência de dados
- Operações de manipulação de variáveis booleanas
- Operações de controlo da máquina e saltos.
Cada instrução pode ter um, dois ou três operandos, de entre os seguintes tipos:
estruturas diferem, pelo que apenas se garante que o operador pode ser identificado
através do primeiro byte, o qual pode ainda incluir referencias aos operandos, e que o
segundo e terceiro byte, caso existam, são apenas utilizados pelos operandos, os quais
são normalmente do tipo constante ou endereço.
Por exemplo, a instrução add A, Rn que permite somar o conteúdo do registo Rn ao
acumulador e a instrução mov addr, #data, que move o valor data para o endereço addr,
possuem ambas na representação em assembly dois argumentos. No entanto, na
representação em binário, a primeira consiste num único byte, em que os três bits menos
significativos indicam o registo a utilizar e os restantes sete bits, a operação e
implicitamente o primeiro operando; já a segunda instrução, necessita de utilizar um
byte para identificar a operação, mais dois bytes para representar respectivamente o
endereço (addr) e o valor da constante (data).
add A, Rn 00101rrr
mov addr, #data 01110101 addr (8bits) data (8bits)
Associou-se a op8 os nomes dos registos (R0...R7), o que é útil caso se pretenda
obter o Translator ou gerar código assembly.
Todos os campos definidos para operd8 servem para identificar o mesmo conjunto
de bits, apenas se definiram vários para facilitar a descrição da especificação. Desta
forma, arg8 e arg8d, servem para representar operandos de 8 bits, respectivamente do
tipo endereço e constante. Caso seja necessário um segundo operando do tipo endereço
utiliza-se arg81.
O operd16 possui 3 campos, em que arg16 e arg16d são campos de 16 bits, com
funções semelhantes a arg8 e a arg8d, e o campo arg11 serve apenas para as instruções
acall e ajmp.
O passo seguinte é descrever os padrões, tentando agrupar as instruções com o
objectivo de diminuir o tamanho da descrição. O método utilizado consistiu em criar
padrões para os casos mais genéricos e tratar os casos específicos individualmente, o
que resultou no seguinte:
patterns
constructors
geral is geral
movc^DPTR is op = 147
movc^PC is op = 131
assembly component
{*}A is $1
{*}R is $1
{*}Ri is $1
{*}E is $1
{*}Er is $1
{*}C is $1
{*}B is $1
{*}DPTR is $1
{*}ARi is $1
{*}AE is $1
{*}AR is $1
{*}AD is $1
{*}EA is $1
{*}ED is $1
{*}REr is $1
{*}EEr is $1
{*}RA is $1
{*}RE is $1
{*}RD is $1
{*}ER is $1
{*}EE is $1
{*}ERi is $1
{*}RiA is $1
{*}RiE is $1
{*}RiD is $1
{*}PC is $1
{*}A.DPTRi is $1
{*}DPREi.A is $1
{*}AB is $1
{*}CB is $1
{*}CnB is $1
assembly operand
[arg8d arg16d] is "#%d"
op8 is "%s"
op9 is "@R%d"
assembly syntax
onearg^A "A"
onebitarg^C "C"
xchd^ARi "A", op9
xch^ARi "A", op9
xch^AR "A", op8
twoarg1^ARi "A", op9
twoarg1^AE "A", arg8
twoarg1^AR "A", op8
twoarg1^AD "A", arg8d
twoarg2^ARi "A", op9
twoarg2^AE "A", arg8
twoarg2^AR "A", op8
twoarg2^AD "A", arg8d
twoarg2^EA arg8, "A"
cjne^AEEr "A", arg8, arg81
cjne^ADEr "A", arg8d, arg8
mov^AR "A", op8
Classe Program
class Program {
private:
//...
public:
Set<Function *> listOfFunctions;
Set<void *> flowNodes;
Program( );
void setRootNode(void *croot);
void *getRootNode( );
void setIdentTable(IdentifierTable *ctable);
IdentifierTable *getIdentTable( );
void setMainFunction(Function *cfunction);
Function *getMainFunction( );
virtual ~Program( );
bool insFunction(Function *cfun);
bool remFunction(Function *cfun);
int hasFunction(Function *cfun);
int howManyFunctions( );
};
Classe Function
typedef enum { FUNCTION=1,PROCEDUR, COMPSTATE} Ftype;
class Function {
private:
//...
public:
Set<void *> fflowNodes;
IndList<char *> argList;
Function();
virtual ~Function( );
void setName(char *caux);
char *getName( );
void setLevel(int clevel);
int getLevel( );
void setType(Ftype ctype);
Ftype getType( );
void setRootNode(void *croot);
void *getRootNode( );
void setParent(Function *cpar);
Function *getParent( );
Classe IdentifierTable
class IdentifierTable {
private:
//...
public:
StringDict<CellIDTable *> listID;
IdentifierTable();
IdentifierTable(char *cname);
IdentifierTable(char *cname, EType ctype);
virtual ~IdentifierTable(){}
char *getAddrName(char *name);
CellIDTable *insIDSymb(char *cname);
CellIDTable *insIDSymb(char *cname, EType ctype);
int hasIDSymb(char *cname);
EType getTypeIDSymb(char *cname);
bool setTypeIDSymb(char *cname, EType ctype);
char *getNextSymbol(char *cname);
CellIDTable *getAddrCellID(char *cname);
char *getNewIDTempByName(FlowNode *node, DataTransfer *crt);
CellIDTable *getNewIDTempByID(FlowNode *node, DataTransfer *crt);
int getNewIDTempByNumber(FlowNode *node, DataTransfer *crt);
char *getNewIDConst(FlowNode *node, DataTransfer *crt);
bool freeIDTemp(char *caux);
bool freeIDTemp(int caux);
void freeIDConst(int caux);
char *getNextVarName(char *cname);
int howManyVars();
char *getVarOfNumber(int cnum);
int getVarNumber(char *cname);
};
Classe CellIDTable
class CellIDTable {
private:
//...
public:
TwoKeySet<FlowNode *, DataTransfer *> IDreg;
FlowNode *getNextAssignNode(FlowNode *node);
DataTransfer *getLastAssignInNode(FlowNode *node);
CellIDTable();
CellIDTable(EScope cscope);
CellIDTable(EType ctype);
virtual ~CellIDTable();
void setScope(EScope cscope);
EScope getScope();
void setClass(EClass cclass);
EClass getClass();
void setType(EType ctype);
EType getType();
void addAsgn(DataTransfer *crt);
bool remAsgn(DataTransfer *crt);
int hasAsgn(DataTransfer *crt);
void setIDconst(Constant *cconst);
Constant *getIDconst();
void setIDmem(Memory *cmem);
Memory *getIDmem();
void setIDfunction(Function *cfun);
Function *getIDfunction();
void setIDCRMF(int ccrm, ActualValue cval);
int getIDCRMF();
ActualValue getActualValue();
void setVarNumber(int numb);
int getVarNumber();
};
Classe FlowNode
class FlowNode{
private:
//...
public:
Set<void *> inEdges;
IndList<void *> outEdges;
FlowNode();
void setFunction(void /*Function*/ *cfun)
void /*Function*/ *getFunction();
virtual ~FlowNode();
void* getInterval();
void setInterval(void *Cinterval);
void setStartNode(bool Cst);
bool getStartNode( );
void setEndNode(bool Cst);
bool getEndNode( );
int howManyOutEdges();
void sethasBeenVisited();
void clrhasBeenVisited();
bool gethasBeenVisited();
void addLinkIn(void *Clink);
bool remLinkIn(void *Clink);
void addLinkOut(int Lpos, void *Clink);
bool remLinkOut(void * Clink);
Classe DataTransfer
#define ASSIGN 0
#define PHYASGN 1
#define ATRIBASGN 2
#define LABELASGN 3
#define JMPASGN 4
#define CJMPASGN 5
#define RETASGN 6
typedef struct {
int rule;
void *phyTarget;
int phyType;
} phyContainer;
class DataTransfer {
private:
//...
public:
IndList<phyContainer *> list;
DataTransfer();
DataTransfer(FlowNode *Cflownode);
int AsgnType();
void setAsgnType(int );
virtual ~DataTransfer();
void setFlowNode(FlowNode *, bool);
FlowNode *getFlowNode();
bool insFlowDependent(DataTransfer *Cdep);
bool insFlowSupporter(DataTransfer *Csupp);
bool remFlowDependent(DataTransfer *Cdep);
bool remFlowSupporter(DataTransfer *Csupp);
int hasFlowDependent(DataTransfer *Cdep);
int hasFlowSupporter(DataTransfer *Csupp);
int howManyFlowDependents();
int howManyFlowSupporters();
DataTransfer *getNextFlowDependent(DataTransfer *crt);
DataTransfer *getNextFlowSupporter(DataTransfer *crt);
Set<DataTransfer*>*getAddrOfFlowDependents( );
Set<DataTransfer *> *getAddrOfFlowSupporters( );
int getTopNumber( );
void setNumber(int Cnumber);
int getNumber( );
void insNxtAtrib(DataTransfer *crt);
DataTransfer *getNxtAtrib(DataTransfer *crt);
bool remNxtAtrib(DataTransfer *crt);
Classe Expression
class Expression {
private:
//...
public:
void *state_label;
Expression( );
virtual ~Expression(){}
void setDataTransfer(DataTransfer *Cdt);
DataTransfer *getDataTransfer( );
void setType(EType ctype);
EType getType( );
int getOp(void);
void setOp(int cop);
void *getState( );
void setState(void *cstate);
void setLeft(Expression *cleft);
Expression *getLeft( );
void setRight(Expression *cright);
Expression *getRight( );
void setStatus(int st);
int getStatus( );
void *getVal(int r, int n);
void setVal(int r, void *caux, int t);
int getValType(int r, int n);
void DeterminateType();
};
Classe TreeSelector
typedef struct list {
Expression *exp;
struct list *next;
} List;
class TreeSelector{
private:
//...
public:
TreeSelector(Function *);
virtual ~TreeSelector( );
bool initTreeSelector( );
void buildList( );
void initPickTree( );
Expression *getNextTree( );
};Classe Color_Allocator
class Color_Allocator {
private:
//...
public:
Color_Allocator(Function *cfun, int InitDisp);
virtual ~Color_Allocator( );
//...
void Allocate_Registers( );
};
Classe IterativeDFAnalyse
class IterativeDFAnalyse {
private:
//...
public:
IterativeDFAnalyse(Function *cfun);
virtual ~IterativeDFAnalyse( );
void Worklist_Iterate( );
void AliveAnalyse( );
};
Classe ssaDF
class ssaDF {
private:
//...
public:
ssaDF(MyFunction *);
virtual ~ssaDF();
void placeAllPhyFunctions();
void InsertAllPhyAssign();
};
Classe StructuralAnalysis
class StructuralAnalysis {
private:
//...
public:
StructuralAnalysis(Function *cfun);
virtual ~StructuralAnalysis(){}
IntervalNode *Analize( );
void setFunction(Function *cfun);
Function *getFunction( );
};
f 10.0 f1 10.0
print( f ) print( f1 )
a2 a1 2
print( a ) print( a1 )
ba+1 b1 a1 + 1
print(b) print( b1 )
f f + 20.0 f2 f1 + 20.0
print( f ) print( f2 )
c input(...) c1 input(...)
c>0 c1 > 0
h5 h1 5
print( h ) cc+1 print( h1 ) c2 c1 + 1
aa+1 print(ch ) a2 a1 + 1 print(c2 )
print( a ) print( a2 )
Considera-se ainda, que existem quatro registos simples (R0,...,R3), que são utilizados
pelas variáveis a, b, c e h. E dois registos compostos (F0, F1), utilizados pelas variáveis f
e g, de tal forma que:
F0 = (R0, R1)
F1 = (R2, R3)
{ f1, a1, b1, f2, c1, h1, a2, c2, c3, g1, h2 }
R0 R1 R2 R3 f1 a1 b1 f2 c1 h1 a2 c2 c3 g1
R1 t
R2 t t
R3 t t t
f1 f f f f
a1 f f f f t
b1 f f f f t t
f2 f f f f f t t
c1 f f f f f t t t
h1 f f f f f t t t t
a2 f f f f f f t t t t
c2 f f f f f f t t f f f
c3 f f f f f f t t f t f f
g1 f f f f f f t f f t f f t
h2 f f f f f f t f f f f f f t
NºUse.: x
R0 NºAdj.: 3 R1 R2 R3
Spill: x
...
NºUse.: 2
f2 NºAdj.: 7 a1 b1 c1 h1 a2 c2 c3
Spill: 0.29
...
Nº inicial de
vértices adjacentes Indicação de que
o vértice já foi
Nº de adjacentes,
removido
conforme se processa
a remoção dos vértices
Considera-se ainda que os operandos das funções Φ(...) não entram em conflito entre
eles, isto porque na prática as instruções que substituem estas funções, são inseridas nos
nodos antecessores, pelo que na realidade as definições de cada um dos operandos
nunca alcançam a função Φ(...).
h2(0.33)
3/x
R0 g1(0.25)
3/x 4/3
R1 c3(0.17)
3/2/x 6
R2 c2(0.67)
3/x
3/2/1/x
R3 a2(0.2)
5
3/2/1/0/x
f1(0.29) h1(0.22)
2/x 9
a1(0.43) c1(0.5)
7/5 6
b1(0.15) f2(0.29)
13/11/10/9 7/6
De notar que se considera que numa mesma expressão, os operandos não entram em
conflito com a variável que guarda o resultado, excepto no caso de permanecerem
“vivos” para além dessa expressão.
Na Fig E3 encontram-se representadas duas entradas da lista de adjacências, uma
representando um registo ( R0) e outra uma variável (f2). Cada entrada possui o número
de utilizações da variável (não se aplica aos registos), o número de vértices adjacentes e
o custo de splitting (também não se aplica aos registos), calculado com base na razão
entre os dois valores anteriores.
O respectivo grafo encontra-se representado na Fig E5, onde junto de cada um dos
vértices, está a designação do registo ou variável, o custo de splitting (entre parêntesis)
e o número de adjacentes que o vértice possui conforme se processa o grafo. Este último
valor é colocado a x quando o vértice é removido do grafo. A legenda da informação
associada a cada vértice encontra-se representada na Fig E4.
g1(0.25)
4/3
a1(0.43) c3(0.17)
7/5 6/5
b1(0.15) a2(0.2)
5/4
13/11/10/9/1
b2(1)
2
h1(0.22)
f2(0.29) 9/8
7/6/5
c1(0.5)
6/5
Fig E6 - Grafo de adjacências após o splitting de b1.
Desta forma, o primeiro candidato é o próprio R0, que ao ser removido contribui para
reduzir em uma unidade, o número de interferências de todos os vértices a ele
adjacentes, repetindo-se o processo para R1, R2, R3 e f1. De notar que este último reduz
o número de adjacentes de a1 e b1 em duas unidades.
O processo continua, removendo-se h2, o que contribui para reduzir o número de
adjacentes de g1, mas ao contrário dos casos anteriores, ainda não é possível executar tal
operação, uma vez que a diferença entre o número de cores disponíveis e o grau do
vértice é inferior ao número de registos necessários à respectiva variável.
Pelo que se chega a uma situação em que nenhum dos vértices, dos que ainda se
encontram no grafo, está em condições de ser removido. Há então, que recorrer a
mecanismos mais complexos, que no caso do BEDS consiste em realizar o splitting de
um ou mais vértices, os quais são seleccionados com base nos valores previamente
calculados para este tipo de operações. Desta forma o primeiro candidato é a variável b1.
Como no BEDS, a operação de splitting corresponde a dividir uma variável em
tantas quantas as novas definições inseridas, quer estas advenham das operações de
load, quer das funções Φ(...) entretanto necessárias, acontece, no presente exemplo, que
seja necessário introduzir uma nova variável (b2), ao nível da representação e como tal
do grafo de interferências. Neste último, é ainda preciso (re)determinar as interferências
de b1 e b2 com as restantes variáveis. O grafo resultante encontra-se representado na Fig
E6.
g1(0.25)
4/3
a1(0.43) c3(0.17)
7/5 6/5
b1(0.15) a2(0.2)
5/4
13/11/10/9/1
b2(1)
2
h1(0.22)
f2(0.29) 9/8
7/6/5
c1(0.5)
6/5
Fig E7 - Grafo de interferências antes da segunda operação de splitting.
Após a remoção dos vértices b1, b2, g1, e c3 volta a colocar-se a mesma situação, ou
seja, nenhum dos restantes vértices está em condições de garantir a sua remoção. A
situação actual do grafo encontra-se representada na Fig E7.
A escolha do próximo candidato recai sobre a2, mas facilmente se constata que não
existe qualquer benefício em realizar o splitting deste vértice. Caso não existam
mecanismos que permitam detectar este tipo de situações, o que acontece é que o vértice
é mesmo sujeito a operação de splitting, acrescentando assim instruções que apenas
degradam a qualidade do código final. É, como tal, aconselhável implementar alguns
mecanismos que permitam controlar a ocorrência deste tipo de situações e assinalem o
momento em que se deve escolher outro candidato, o que no presente exemplo
corresponde a escolher o vértice h2. Procede-se então à sua decomposição conforme o
que se fez para b1 e que resulta no grafo da Fig E8. Repare-se que a remoção deste
vértice, também não acarreta vantagens, mas ao contrário do caso anterior, a situação
em que se encontra h2 não é facilmente detectável, pelo que se aceita como sendo
satisfatória a sua ocorrência.
a2(0.2)
5/4
a1(0.43) h3(1)
7/5/4 0
f2(0.29) h1(0.22)
7/6/5/4 9/8/6/5/4
c1(0.5)
6/5
Após a remoção de h3, volta a ser indispensável realizar nova operação de splitting,
sendo h1 novamente o candidato eleito. Mas nas actuais condições do grafo, tal
operação é em tudo semelhante à situação que ocorreu para a2, pelo que é aconselhável
seleccionar outro candidato.
a2(0.2)
5/4/2
a1(0.43) f3(1)
7/5/4 0
f2(0.29) h1(0.22)
7/6/5/4/1 9/8/6/5/4/2
c1(0.5)
6/5/3
Fig E9 - Grafo de interferências após o splitting de f2.
Desta forma, e uma vez que o splitting de h1 e a2 não produz qualquer vantagem, a
escolha recai sobre f2, obtendo-se o grafo que se encontra representado na Fig E9, onde
se pode constatar a introdução de uma nova variável (f3).
Topo
a2 f3 h1 c1 a1 f2 h3 c3 g1 b2 b1 h2 c2 f1 R3 R2 R1 R0
Fig E10 - Stack com os vértices do grafo inseridos pela ordem de remoção.
Torna-se assim possível remover f2, a1, c1, h1, f3, e conclui-se com a2, ficando os
elementos ordenados na stack conforme se encontra representado na Fig E10.
Após a remoção de todos os vértices do grafo para a stack, pode-se finalmente
começar a colorir o mesmo. As cores disponíveis vão de 1 a 4, sendo a atribuição feita
pela mesma ordem e conforme a disponibilidade de cada uma.
h2 2 g1
3,4
R0 c3
4 2
R1 c2
1
3
R2 a2
1
2
R3 h3
1
1
f1 h1
1,2 1
a1 c1
3 2
b1 f3
4 3,4
b2 f2
1 1,2
f1[R2,R3] 10.0
print( f1[R2,R3])
a1[R1] 2
print( a1[R1] )
b1[R0] a1[R1] + 1
print( b1[R0] )
store( b1[R0] )
f2[R2,R3] f1[R2,R3] + 20.0
print( f2[R2,R3] )
store( f2[R2,R3] )
c1[R2] input(...)
c1[R2] > 0
h1[R3] 5
print( h1[R3] )
store(h1[R3] ) c2[R3] c1[R2] + 1
a2[R3] a1[R1] + 1 print( c2[R3] )
print( a2[R3] )