Seleção de InstruçõesTopTradução para Código IntermédioBlocos Básicos

Blocos Básicos

Problemas entre Árvores e Assembly

Tree pode interferir com optimização:

ESEQ e CJUMP são úteis para Translate.

Canonificação

Acabar com os ESEQ

Duas funções:

Árvores Canónicas

Obedecem a duas propriedades:

  1. Não têm SEQ ou ESEQ;
  2. O pai de cada CALL é EXP(...) ou MOVE(TEMP t,...).

Ideia: levantar ESEQ na árvore até que eles se tornem SEQ.

Associatividade:

ESEQ(s1,ESEQ(s2,e)) = ESEQ(ESEQ(s1,s2),e)

Operator:

BOP(op,ESEQ(s,e1),e2) -> ESEQ(BOP(op,e1,e2))
MEM(ESEQ(s,e1)) -> ESEQ(s,MEM(e1))
JUMP(ESEQ(s,e1)) -> ESEQ(s,JUMP(e1))
CJ(op,ES(s,e1),e2,l1,l2) -> S(s,CJ(op,e1,e2,l1,l2))

SEQ no segundo argumento:

BOP(op,e1,ES(s,e2)) -> ES(MOVE(T t,e1),ES(
s,BOP(op, T t, e2)))
CJ(op,e1,ES(s,e2),l1,l2) -> ES(MOVE(T t,e1),ES(
s,CJ(op,T t,e2,l1,l2)))

Se s e e1 comutarem:

BOP(op,e1,ES(s,e2)) -> ES(s,BOP(op,e1, e2))
CJ(op,e1,ES(s,e2),l1,l2) -> S(s,CJ(op,e1,e2,l1,l2))

Regras Gerais de Reescrita

Para cada Tree podemos identificar subexpressões e implementar regras de reescrita.

Se tivermos [e1,e2,ESEQ(s,e3)] devemos tirar s:

A função reorder() pega numa lista de expressões e retorna um par frase mais lista de expressões, onde frase são as coisas a fazer antes da lista.

Algoritmo de Reescrita

  1. Extrai sub-expressões;
  2. Insere sub-expressões limpas de ESEQ.

reorder() tira os ESEQ e coloca as frases num grande T_stm. Recebe ptrs. para subexps imediatas:

reorder(l2):

do_exp()

do_stm()

ESEQ tem um lado SEQ e um lado EXP:

CALL

Tree permite CALL como sub-expressões:

Lista Linear de Frases

No fim de do_stm() sobre s0 temos s'0 onde todos os nós SEQ estão no topo:

Processamento de Saltos Condicionais

Resolver o problema de CJUMP:

Ideia:

Blocos Básicos

Bloco básico é sempre da forma:

Divisão é muito simples:

Traces

Queremos escolher um ordenamento tal que cada CJUMP seja seguido pela label false:

Algoritmo para Traces

Começar com um bloco, e seguir um caminho:

Algoritmo guloso.

Finalização

Camos voltar para a árvore:


vitor@cos.ufrj.br

Seleção de InstruçõesTopTradução para Código IntermédioBlocos Básicos