Geração de Código Intermediário

• Vantagens do uso de uma notação intermediária:– facilidade de retargetting: geração de código

para vários processadores diferentes, reusando o máximo possível do código em todos os compiladores, mudando apenas o gerador de código final.

– uso de otimizador único para vários geradores de código diferentes.

Tradução dirigida por sintaxe

parserverificadorde código

código intermediário

geradorde código

intermediário

gerador de código

Código de Três Endereços

• Frequentemente usado como código intermediário, para linguagens imperativas/OO.

• Abstrai um assembler, onde cada instrução básica referencia 3 (ou menos) endereços (i.e. variáveis).

• Formato: x := y op z• Exemplo:

x + y * z

é reescrito para t1 := y * z

t2 := x + t1

Código de três endereços - exemplo

• t1 := -ct2 := b * t1

t3 := -ct4 := b * t3

t5 := t2 + t4

a := t5

*

assign

+

uminus

a

*

uminus

c

b

b

c

Tipos de código de três endereços

• Atribuição do tipo: x := y op z

• Atribuição do tipo: x := op y

• Cópia: x := y

• desvios incondicionais: goto L

• desvios condicionais: if x relop y goto L

• chamada de procedimentos: param x e call p,n e return y

Tipos de código de três endereços (cont.)

• atribuição indexada: x := y[i] e x[i] := y

• atribuição de endereços e ponteiros:x := &y, x := *y e *x := y

Tradução dirigida por sintaxe para código de três endereços

S id := E S.code := E.code || gen(id.place ‘:=‘ E.place)

E E1 + E2 E.place := newtemp; E.code := E1.code || E2.code || gen(E.place ‘:=‘ E1.place ‘*’ E2.place)

E - E1 E.place := newtemp; E.code := E1.code || gen(E.place ‘:=‘ ‘uminus’ E1.place)

E ( E1 ) E.place := E1.place; E.code := E1.codeE id E.place := id.place; E.code := ‘’

Tradução do while

S while E do S1 regra semântica:

S.begin := newlabel; S.end := newlabel; S.code := gen(S.begin ‘:’) || E.code || gen(‘if’ E.place ‘=‘ ‘0’ ‘goto’ S.end) || S1.code || gen(‘goto’ S.begin) || gen(S.end ‘: ‘)

Declarações

• Declarações dentro de um procedimento frequentemente são tratadas como um único grupo, e são acessadas como um offset do ponto onde começam a ser armazenadas (na pilha).

• offset inicialmente é zero, e a cada novo símbolo declarado o valor do offset é guardado na tabela de símbolos, e o offset é incrementado.

• exemplo: procedimento enter(name,type,offset)

Declarações

P {offset := 0} D D D ; DD id : T { enter(id.name, T.type, offset);

offset := offset + T.width }T integer { T.type := integer;

T.width := 4; }T real { T.type := real;

T.width := 8; }

T array [ num ] of T1 { T.type := array(num.val, T1.type); T.width := num.val * T1.width }

Declarações –tratando escopo

• uma possibilidade é manter tabelas de símbolos separadas para cada procedimento, com referências ao contexto mais externo (outra tabela de símbolos).

Declarações –tratando escopo

• procedimentos utilizados:– mktable(previous) – cria uma nova tabela de

símbolos, con referência à anterior– enter(table, name, type, offset) – insere um novo

símbolo na tabela– addwidth(table, width) – incrementa contador do

tamanho da tabela– enterproc(table,name,newtable) – insere um novo

símbolo (procedimento) na tabelae pilhas offset e tblptr

Declarações –tratando escopoP M D { addwidth(top(tblptr),top(offset));

pop(tblptr); pop(offset); }M {t := mktable(nil);

push(t,tblptr); push(0,offset);}

D D1 ; D2

D proc id ; N D1 ; S { t := top(tblptr); addwidth(t, top(offset)); pop(tblptr); pop(offset); enterproc(top(tblptr),id.name,t)}

D id : T { enter(top(tblptr),id.name,T.type,top(offset)); top(offset) := top(offset) + T.width }

N { t := mktable(top(tblptr)); push(t,tblptr); push (0,offset) }

Declarações –tratando registros

• nomes de campos de registros também podem ser guardados usando tabelas de símbolos específicas para cada (tipo) registro.

T record L D end { T.type := record(top(tblptr)); T.width := top(offset); pop(tblptr); pop(offset); }

L { t := mktable(nil); push(t,tblptr); push (0,offset) }

Revendo Atribuições

S id := E { p := lookup(id.name); if p != nil then emit (p ‘:=‘ E.place) else error }

E E1 + E2 { E.place := newtemp; emit (E.place ‘:=‘ E1.place ‘*’ E2.place) }

E - E1 { E.place := newtemp; emit(E.place ‘:=‘ ‘uminus’ E1.place) }

E ( E1 ) { E.place := E1.place }E id { p := lookup(id.name);

if p != nil then E.place := p else error }

Reuso de nomes

• controlando o tempo de vida dos nomes usados dentro de cada statement ou expressão, é possível fazer o reuso de nomes de variáveis temporárias.

• Exemplo: usar contador incrementado para cada novo temporário, e decrementado para cada uso.

• evaluate E1 to t1

evaluate E2 to t2

t := t1 + t2

Reuso de nomes - exemplo

• x := ((a * b) + (c * d)) – (e * f)

• $0 := a * b$1 := c * d$0 := $0 + $1$1 := e * f$0 := $0 - $1x := $0

Acesso a Arrays

• controlado de acordo com o tamanho e o tipo do array: base + (i – low) * w

• ou melhor ainda: i * w + (base – low * w)

• existem fórmulas genéricas para arrays multidimensionais:– 2D: A[i1 , i2]

base + ((i1 – low1) * n2+ i2 – low2) * w

• row-major vs. column-major

Expressões Booleanas

• Podem ser avaliadas de duas formas:– codificar true e false como números, e avaliar as

expressões da mesma forma que expressões matemáticas.

– usar o fluxo de controle, i.e. representar um valor por uma posição atingida no programa. Usada em if-then-else, while-do etc. Permite “curto-circuito” de expressões: se E1 é avaliado como true, na expressão E1 or E2, não é necessário avaliar E2.

Representação numérica - exemplo

• a or b and not c

• t1 := not ct2 := b and t1

t3 := a or t2

Representação numérica - exemplo

• a < b é traduzido paraif a < b then 1 else 0

• 100: if a < b goto 103101: t := 0102: goto 104103: t := 1104:

Esquema de Tradução

E E1 or E2 { E.place := newtemp; emit (E.place ‘:=‘ E1.place ‘or’ E2.place) }

E id1 relop id2 { E.place := newtemp; emit(‘if’ id1.place relop.op id2.place ‘goto’ nextstat + 3); emit(E.place ‘:=‘ ‘0’); emit(‘goto’ nextstat + 2); emit(E.place ‘:=‘ ‘1’)}

E ( E1 ) { E.place := E1.place }E true { E.place := newtemp;

emit(E.place ‘:=‘ ‘0’) }

Representação numérica - exemplo

• a < b or c < d and e < f

• 100: if a < b goto 103101: t1 := 0102: goto 104103: t1 := 1104: if c < d goto 107105: t2 := 0106: goto 108

107: t2 := 1108: if e < f goto 111109: t3 := 0110: goto 112111: t3 := 1112: t4 := t2 and t3113: t5 := t1 or t4

Fluxo de controle

• Associamos a cada expressão booleana desvios para labels caso a expressão seja avaliada para true ou false.

• E.true e E.false

Tradução do if-then

S if E then S1

regra semântica: E.true := newlabel; E.false := S.next; S1.next := S.next; S.code := E.code || gen(E.true ‘:’) || S1.code

Tradução do if-then-else

S if E then S1 else S2 regra semântica:

E.true := newlabel; E.false := newlabel; S1.next := S.next; S2.next := S.next; S.code := E.code || gen(E.true ‘:’) || S1.code

gen(‘goto’ S.next); gen(E.false ‘:’) || S2.code

Tradução do while

S while E do S1

regra semântica: S.begin := newlabel; E.true := newlabel; E.false := S.next; S1.next := S.begin; S.code := gen(S.begin ‘:’) || E.code || gen(E.true ‘:’) || S1.code || gen(‘goto’ S.begin)

Fluxo de controle

• a < b traduzido para: if a < b goto E.true goto E.false

Esquema de Tradução

E E1 or E2 { E1.true := E.true; E1.false := newlabel; E2.true := E.true; E2.false := E.false; E.code := E1.code || gen(E1.false ‘:’) || E2.code) }

E E1 and E2 {E1.true := newlabel; E1.false := E.false; E2.true := E.true; E2.false := E.false; E.code := E1.code || gen(E1.true ‘:’) || E2.code) }

Esquema de Tradução

E not E1 { E1.true := E.false; E1.false := E.true; E2.true := E.true; E2.false := E.false; E.code := E1.code}

E id1 relop id2

{E.code := gen(‘if’ id1.place relop.op id2.place ‘goto’ E.true || gen(‘goto’ E.false) }

E true {E.code := gen(‘goto’ E.true }

E false {E.code := gen(‘goto’ E.false }

Exemplo 1

• a < b or c < d and e < f

• if a < b goto Ltrue goto L1L1: if c < d goto L2 goto LfalseL2: if e < f goto Ltrue goto LFalse

• é possível otimizar o código acima.

Exemplo 2

• while a < b do if c < d then x := y + z else x := y – z

• L1: if a < b goto L2 goto LnextL2: if c < d goto L3 goto L4L3: t1 := y + z x := t1 goto L1L4: t2 := y – z x := t2 goto L1

switch/case

• switch expression begin case value: statement case value: statement … case value: statement default: statement end

implementação de switch/case

• sequência de goto’s condicionais, um para cada caso.

• loop percorrendo uma tabela de valores e labels para o código do statement correspodente.

• hash table com valores e labels

• criar um array de labels, com o label para o statement j na posição da tabela índice j.

tradução de switch/case

• switch E begin case V1: S1

case V2: S2

… case Vn-1: Sn-1

default: Sn

end

tradução de switch/case

código para avaliar E em t goto testL1: código para S1

goto nextL2: código para S2

goto next …Ln-1: código para Sn-1

goto nextLn: código para Sn

goto next

test: if t = V1 goto L1

if t = V2 goto L2

… if t = Vn-1 goto Ln-1 goto Ln

next:

outra tradução de switch/case

código para avaliar E em t if t V1 goto L1

código para S1

goto nextL1 : if t V2 goto L2

código para S2

goto next

L2: …

Ln-2: if t Vn-1 goto Ln-1

código para Sn-1 goto nextLn-1: código para Sn

next:

Backpatching

• uso de um passo extra para resolver as referências a labels definidos posteriormente.