1

Tradução para Código Intermediário

Departamento de Estatística e InformáticaUniversidade Federal de Sergipe

Compiladores

Giovanny Lucero

giovanny@ufs.br

2

CI: Portabilidade e Modularidade

Java Sparc

MIPS

Pentium

Alpha

Linguagem Arquitetura Alvo

Compilação

4 diferentes compiladores

completos

3

CI: Portabilidade e ModularidadeLinguagem Arquitetura Alvo

Java

ML

Pascal

C

C++

Sparc

MIPS

Pentium

Alpha

20 diferentes compiladores

completos

Compilação

4

Problema

• A cada nova arquitetura, n novos compiladores (um para cada linguagem).

• O projeto dos n novos compiladores não faz reuso do que foi desenvolvido anteriormente.

• Solução:– Geração de Código Intermediário

5

CI: Portabilidade e Modularidade

Java

ML

Pascal

C

C++

Sparc

MIPS

Pentium

Alpha

6

CI: Portabilidade e Modularidade

Java

ML

Pascal

C

C++

Sparc

MIPS

Pentium

Alpha

Java

ML

Pascal

C

C++

Sparc

MIPS

Pentium

Alpha

CódigoIntermediário

vanguardas retaguardas

Representação abstrata do código

de máquina

7

Código Intermediário

• Independente da máquina

• Independente da linguagem fonte

• Conveniente para que a análise semântica o produza

• Conveniente para traduzir para código de máquina

• Semântica clara e simples de c/construtor

8

Código Intermediário

• Exemplos:– TREE (Appel & Palsberg)– Código de 3 endereços (Aho et al)– E muitos outros...

constantes em BINOPPLUS, MINUS, MUL, DIV,AND, OR, LSHIFT, RSHIFT, ARSHIFT, XOR

constantes em CJUMPEQ, NE, LT, GT, LE, GE, ULT, ULE, UGT, UGE

A linguagem intermediária Treeabstract class Exp

CONST(int value)NAME(Label label)TEMP(Temp temp)BINOP(int binop,

Exp left, Exp right)

MEM(Exp exp)CALL(Exp func,

ExpList args) ESEQ(Stm stm, Exp exp)

abstract class StmMOVE(Exp dst, Exp src)EXP(Exp exp)JUMP(Exp exp,

LabelList targets)CJUMP(int relop,

Exp left, Exp right, Label iftrue, Label iffalse)

SEQ(Stm left, Stm right)LABEL(Label label)

4

10

Tradução• Pode ser feita depois ou em paralelo com a checagem de

tipos.public class ExpTranslator extends ExpVisitorR { ... public ExpTy translate(Expression e) { return (StmTy) e.accept(this); } protected Object visitAndExpR(AndExp e) { // código para checagem e tradução } ...}

class StmTy public Tree.Stm stm; public lps.semantica.vinculaveis.Type ty;}

11

Tradução de variáveis simples

MEM

BINOP

PLUS TEMP fp CONST k

MEM(BINOP(PLUS, TEMP fp, CONST k))

• k é o offset da variável dentro do frame• Calculado na tradução da declaração da variável

TEMP t

Ou então:

12

• Simplificaremos as árvores, assim:

MEM

+

TEMP fpCONST k

MEM(+( TEMP fp, CONST k))

13

Variáveis não locais

• Quando x é declarada num escopo externo, vínculos estáticos devem ser usados

MEM(+(CONS Kn, MEM(+(CONS Kn-1, ... MEM(+(CONS K1, TEMP fp))...)

Onde K1,...,Kn-1 são os offsets do vínculo estático nas

funções aninhadas e Kn é o offset de x no seu frame

• As informações de aninhamento deverão estar registradas no ambiente (tabela de símbolos)

14

Valores estruturados• Valores não atômicos (não escalares)• Tratamento depende da linguagem. Por exemplo:

– Pascal• Variável estruturada armazena um valor estruturado• Variáveis estruturadas são criadas na Pilha• Atribuição e comparação por cópia

– Java• Não há variáveis estruturadas, só valores

estruturados.• Variáveis de tipo estruturado armazenam, na pilha,

uma referência a um valor estruturado• Valores estruturados são criados no heap• Atribuição e comparação por referência

15

Variáveis array• Pascal

– Criação na pilha– Limites fazem parte da variável (para checagem

dinâmica)• O gerenciamento de heap é abstraído por uma biblioteca

de procedimentos externos

16

Seleção de componentes• Array em Pascal: a[i]

(i-lb)*s+a, onde a é o endereço base, s é o tamanho de cada elemento, lb é o limite inferior dos índices de a

– Se a for global a-s*lb pode ser calculado na compilação

– Adicionalmente checagem de limites deve ser feitaMEM

+

MEM *MEM(+(MEM(e), *(i, CONST(W)))

e i CONST

w

17

Seleção de componentes• Seleção de campo: a.f

a + offset de f em a– A informação do offset deve estar no ambiente– A árvore para a.f é:

MEM (+(TEMP fp, +(CONST ka, CONST ka.f)))

18

Criação de registros e arrays

• Em geral:– Campos inicializados com null ou 0

• Obs. Outra linguagem pode requerer a criação recursiva dos componentes

– Criação no heap• Chamando uma função do runtime system (função

externa)

• Esta função retorna um ponteiro para área onde o registro/array é criado.

CALL(NAME(malloc), EXPLIST(A1,...(new EXPLIST(AN,NULL)))

19

Criação de registros e arrays

20

Aritmética

• Em geral, um operador aritmético binário da sintaxe abstrata tem um correspondente em Tree.

• Tree não tem operadores unários.– Negação unária de inteiros implementada como

subtração de zero.– Etc.

21

Condicionais

• Expressões booleanas são representadas usando CJUMP– Combinar com if_then_else, while ...– Combinar em expressões com operadores lógicos de

circuito curto

• 5 < x é traduzido para

• 5 < x && x < 10

CJUMP(LT, CONST(5), x, t, f )

SEQ ( CJUMP(LT, CONST(5), x, c, f ), SEQ ( LABEL c,

CJUMP(LT, x, CONST(10), t, f ) ) )

22

If then else

• Considere:– s1(t, f) = CJUMP(BINOP, left, right, t, f)

• If e1 then e2 else e3.

–e1 é sempre uma expressão booleana

–No entanto e2 e e3 podem ser:• Um statement que não retorna valor algum • Uma expressão booleana• Uma expressão numérica

–É preciso analisar cada um dos casos.

23

If then else

• Caso e2 e e3 statements:

–SEQ ( S1(t, f ), SEQ ( LABEL t,

SEQ(e2, SEQ(LABEL f,

e3))))

• Caso e2 e e3 expressões booleanas:

SEQ(s1(z,f), SEQ(LABEL z,

SEQ(s2(t,f), SEQ(LABEL f, s3(r,f)))

24

If then else

• Caso e2 e e3 expressões:ESEQ(s1(t,f), SEQ(LABEL t, SEQ(

MOVE(TEMP r, e2), SEQ(LABEL F,

MOVE(TEMP r, e3)))), Temp r)

• Observação:–e2 e e3 podem ser diferentes. Neste casos emprega-se as abordagens apresentadas anteriormente de forma híbrida.

25

While

• Layout:

While (cond) { body}

26

While

• Layout:

While (cond) { body}

test: if not (condition) goto done body goto testdone:

27

While

• Layout:

• Se um break é encontrado no interior do laço, a tradução é simplesmente um jump(done).

LABEL(test);CJUMP(BINOP, e1,e2, done, body)LABEL(body);Loop body statementsJUMP (NAME test)

LABEL(done);

test: if not (condition) goto done body goto testdone:

28

FOR

• O for pode ser expresso usando o que foi definido pelo while:

For (i = lo; i <= hi; i++;){ //body}

i = lo;Limit = hi;While (i <= limit){

//body i++

}

29

FOR

• Problema– E se limit igual ao maior inteiro positivo

possível?

i = lo;limit = hi;While (i <= limit){

//body i++

}

30

FOR

• Solução – Colocar um teste adicional no fim do looping,

antes do incremento.i = lo;limit = hi;While (i <= limit){

//body if (i == maxInt)

break; i++

}

31

Chamada a subrotina

• f(a1,a2,...,an)

call(NAME(lf),[e1,...,en])– Onde lf é o label para a função f.

– [e1,...,en] representa um Explist.

32

Chamada a subrotina

• Para linguagens que suportam funções aninhadas, temos:

• f(a1,a2,...,an)

call(NAME(lf),[sL,e1,...,en])– Onde SL é o vínculo estático.

33

Declarações

• Declaração de tipos– Em geral, não geram código

• Declaração de variáveis– Define o local de memória

• Definição de função– Prólogo– Corpo– Epílogo

34

Definição de função

• Uma função é traduzida para um segmento de linguagem assembly com um prólogo, corpo e epilogo.

• O prologo contém:– Pseudo-instruções– O label relativo ao nome da função– Uma função para ajustar o stack pointer (alocar um novo frame)– Instruções para salvar argumentos escapados para o frame e mover

argumentos não escapados para os registradores.– Armazenar instruções para salvar qualquer callee save registers,

incluindo o registro que armazena o endereço de retorno.

35

Definição de função

• Em seguida vem o corpo.

• Depois do corpo vem o epilogo, que contém:– Uma instrução para mover o valor de retorno para o

registro reservado para esta proposta.– Instruções de carregamento para restaurar os callee

save registers.– Uma instrução para reiniciar o stack pointer (desalocar

frames).– Uma instrução de retorno (jump to return address).– Pseudo instruções para anunciar o fim de uma função.

36

Strings

• Um literal String é implementado como um endereço constante de um segmento de memória inicializado para os próprios caracteres.– NAME(lab)

• Toda string é colocada em uma lista global (lista de fragmentos).

• Todas operações com string são executadas por funções providas pelo próprio sistema.

37

Classes e Objetos

• Criação de objetos similar a criação de variáveis registro.

• Chamada a métodos similar a chamadas de funções.– Primeiro deve determinar qual classe declara o método.

– This pointer é passado como argumento do método.

• Acesso a variáveis– Similar ao acesso a campo de registro.