Blocos básicos e Traces Departamento de Estatística e Informática Universidade Federal de Sergipe...

Blocos básicos e Traces

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

Compiladores

Giovanny Lucero

giovanny@ufs.br

Adequação de Tree

• Alguns aspectos de Tree não tem correspondência com linguagens de máquina– CJUMP tem dois rótulos

• Ordem de avaliação de expressões interfere com otimização– Sem ESEQ e CALL, ordem de avaliação não

importa

Transformação em três passos

• Trees canônicos sem SEQ ou ESEQ– Subindo SEQ e ESEQ ao topo da árvore– Todo pai de SEQ é um SEQ– Portanto, substituímos os SEQs por uma lista de

Tree.Stm• Agrupação em blocos sem JUMPS internos ou

rótulos (Blocos Básicos)• Traces: c/CJUMP seguido imediatamente pelo seu

rótulo false

Árvores Canônicas

• Não tem SEQ nem ESEQ• O pai de cada CALL é

– EXP(...) ou MOVE(Temp t, ...)

Regras de transformação

ESEQ

ESEQs1

s2 e

ESEQ

SEQ e

s1 s2

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

BINOP

op ESEQ

s1 e1

e2 BINOP

op

ESEQ

s1

e1 e2

BINOP(op, ESEQ(s1,e1),e2) = ESEQ(s1, BINOP(op,

e1,e2))

MEM(ESEQ(s,e1)) = ESEQ(s,MEM(e1))JUMP(ESEQ(s,e1) = SEQ(s,JUMP(e1)CJUMP(op,ESEQ(s,e1),e2,L1,L2) =

SEQ(s,CJUMP(op,e1,e2,L1,L2))

BINOP(op,e1,ESEQ(s1,e2)) = ESEQ(s1, BINOP(op,e1,e2))

BINOP

op ESEQ

s1 e2

e1

ESEQ

s1 BINOP

e1 e2

Está correto?

op

BINOP(op,e1,ESEQ(s1,e2)) = ESEQ(s1, BINOP(op,e1,e2))

BINOP

op ESEQ

s1 e2

e1

Está correto? Não em todos os casos.

•s1 pode realizar alguma ação que modifique o valor de e1.

ESEQ

s1 BINOP

e1 e2op

BINOP(op,e1,ESEQ(s1,e2)) = ESEQ(MOVE(TEMP t, e1), ESEQ(s1, BINOP(op, TEMP t, e2)

BINOP

op ESEQ

s1 e2

e1

ESEQ

MOVE ESEQ

s1 BINOP

Solução

•Criar um temporário t.

TEMP

t

e1

op e2TEMP

t

CJUMP(op,e1,ESEQ(s,e2),L1,L2) =SEQ(MOVE(TEMP t,e1), SEQ(s, CJUMP(op,TEMP t,e2,L1,L2)))

Se s e e1 comutam:BINOP(op,e1,ESEQ(s,e2)) = ESEQ(s,BINOP(op,e1,e2))

CJUMP(op,e1,ESEQ(s,e2),L1,L2) =SEQ(s, CJUMP(op,e1,e2,L1,L2) )

• Observe que s e e1 comutam se s não produz efeitos colaterais que alterem e1– Dados de e1 não são referenciados por s– Não podemos saber sempre se duas expressões

comutam. MOVE(MEM(x),y) e MEM(z)– Tomamos uma abordagem conservadora

• NAME(L) e CONST(n) comutam com todo mundo.

CALL

• Regras similares são aplicadas a CALL quando seu pai não é MOVE ou EXP.

• Exemplo:– BINOP(PLUS, CALL(...), CALL(...));

• CALLs devolvem resultados em um mesmo registrador. (Sobrescrita).

CALL

• Para resolver este problema, substituir cada ocorrência de CALL por:– ESEQ(MOVE(TEMP tnew, CALL(...),

TEMP tnew).

Linearização dos Statements

• Após execução destes passos, todos os SEQ estarão próximos a raiz da árvore.

• No entanto podemos encontrar construções desta forma:– SEQ(SEQ(a,b), c)).

• Para eliminarmos estas construções, aplicamos novas transformações tal que:– SEQ(SEQ(a,b),c) = SEQ(a, SEQ(b, c)).

• Agora sim, podemos eliminar os construtores SEQ.

Transformação em três passos

• Trees canônicos sem SEQ ou ESEQ– Subindo SEQ e ESEQ ao topo da árvore– Todo pai de SEQ é um SEQ– Portanto, substituímos os SEQs por uma lista de

Tree.Stm• Agrupação em blocos sem JUMPS internos ou

rótulos (Blocos Básicos)• Traces: c/CJUMP seguido imediatamente pelo seu

rótulo false

Blocos Básicos

• Em um bloco básico:– O primeiro comando é um rótulo– O último comando é um JUMP ou CJUMP– Não há mais rótulos JUMPS ou CJUMPS

Algoritmo:– scanear o programa Tree assim:

• Se um rótulo é achado, começa um novo bloco• Se um (C)JUMP é achado, termina o bloco• Se ficou algum bloco não finalizado por (C)JUMP, adicione

um JUMP para o próximo bloco • Se ficou algum bloco sem começar com rótulo, invente um

novo rótulo

Transformação em três passos

• Trees canônicos sem SEQ ou ESEQ– Subindo SEQ e ESEQ ao topo da árvore– Todo pai de SEQ é um SEQ– Portanto, substituímos os SEQs por uma lista de

Tree.Stm• Agrupação em blocos sem JUMPS internos ou

rótulos (Blocos Básicos)• Traces: c/CJUMP seguido imediatamente pelo

seu rótulo false

Traces

• Observe que os blocos básicos podem ser re-arranjados em qualquer ordem sem alterar a semântica do programa

• Escolhemos um ordenamento de blocos tal que c/CJUMP é seguido por seu rótulo falso, e

• Se possível, JUMPs seguido imediatamente do seu rótulo alvo

Traces

• Algoritmo:– Enquanto existir blocos não marcados.

• Comece com qualquer bloco (marque o bloco)

• Siga o possível caminho de execução (JUMP), marcando os blocos percorridos.

• Se CJUMP() escolha um dos dois caminhos.

• Ligue os blocos percorridos (trace gerado).

Traces

• Finalizando:– Qualquer CJUMP imediatamente seguido pelo

seu rótulo “false”. • Deixe como está.

– Qualquer CJUMP imediatamente seguido pelo seu rótulo “true”.

• Trocamos o rótulo true por false e negamos a condição.

Traces

– Qualquer CJUMP(cond, a, b, lt, lf) seguido nem por true ou false.

• Rescrevemos o CJUMP para a seguinte forma:– CJUMP(cond, a, b, lt, l’f)

– LABEL l’f

– JUMP(NAME lf);

Seleção de instrução

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

Compiladores

Giovanny Lucero

giovanny@ufs.br

Padrões Tree

• Identificamos uma instrução de máquina como um fragmento de Tree (um padrão)

• Tiling: recortamos a árvore em um mosaico/“quebra cabeças” de padrões– Objetivo: obter um conjunto “otimizado” de

padrões.

Padrões para Jouette– r_i TEMP

ADD r_i ← r_j + r_kMUL r_i ← r_j × r_k

SUB r_i ← r_j - r_kDIV r_i ← r_j / r_k

ADDI r_i ← r_j + c

SUBI r_i ← r_j - c

+ ×

- /

+CONST

+CONST CONST

-

CONST

Em jouette o registrador 0 sempre contém 0

LOAD r_i ← M[r_j+c]

STORE M[r_j+c] ← r_i

MOVEM M[r_i] ← M[r_j]

MOVE

MEM

+CONST

MOVE

MEM

+CONST

MOVE

MEM

CONST

MOVE

MEM

MEM

+CONST

MEM

+CONST

MEMMEM

CONST

MOVE

MEMMEM

TEMP i

Tiling árvoresMOVE

MEM MEM

+ +

fp CONST xMEM *

CONST 4+

fp CONST a

a[i]:=x

Tiling árvoresMOVE

MEM MEM

+ +

fp CONST xMEM *

TEMP i CONST 4+

fp CONST afp

2. LOAD r_1 ← M[fp+a]4. ADDI r_2 ← r_0 + 45. MUL r_2 ← r_i × r_26. ADD r_1 ← r_1 + r_28. LOAD r_2 ← M[fp+x]9. STORE M[r_1+0] ← r_2

a[i]:=x1

2

3 4

5

67

8

9

fp

TEMP i

Tiling árvoresMOVE

MEM MEM

+ +

fp CONST xMEM *

CONST 4+

CONST a

MOVE

MEM MEM

+ +

fp CONST xMEM *

TEMP i CONST 4+

fp CONST a

a[i]:=x

1

2

3 4

5

67

8

9

2. LOAD r_1 ← M[fp+a]4. ADDI r_2 ← r_0 + 45. MUL r_2 ← r_i × r_26. ADD r_1 ← r_1 + r_28. LOAD r_2 ← M[fp+x]9. STORE M[r_1+0] ← r_2 9. MOVEM M[r1] ← M[r2]

X X X X X X X X

Tilings ótimos e “otimais”

• C/instrução de máquina tem um custo (tempo de execução)

• Ótimo soma dos custos dos tiles é mínima• Otimal não existe nenhum par de tiles

adjacentes que possam ser combinados em um único tile mais eficiente

• Ótimo Ótimal, mas não viceversa• Para RISC otimal e ótimo não são muito diferentes• Para CISC nota-se às vezes a diferença

Maximal Munch

• Algoritmo top-down que calcula tiling otimal– Começando pela raiz, sempre escolha o tile maior que

puder

– Continue top-down com as sub-árvores ainda sem cobrir

– Por c/tile colocado, gere as instruções correspondentes

• Gera instruções em ordem inversa• Se todas as instruções têm o mesmo peso, o tile

maior é o que tem mais nós.

Tiling Ótimo

• O algoritmo usa programação dinâmica: encontra a solução ótima baseada nas soluções ótimas de cada subproblema– Tiling ótimo de uma árvore é baseado no tiling ótimos

das sub-árvores

• Associa com cada nó um custo– a soma dos custos do conjunto de instruções ótimo para

sua sub-árvore

• Trabalha bottom-up

Exemplo• CONST1 só é casado por

ADDI e tem custo 1• Similarmente CONST2• Para + temos:

MEM

+

CONST1 CONS2

Tile Instrução Custo tile Custo folhas

Custo total

ADD 1 1+1 3

ADDI 1 1 2

ADDI 1 1 2

++

CONST

+CONST

• Para MEM temos

Tile Instrução Custo tile Custo folhas

Custo total

LOAD 1 2 3

LOAD 1 1 2

LOAD 1 1 2

MEM

MEM

CONST+

MEM

CONST+

MEM

+

CONST1 CONS2

Emissão de código

• Uma vez calculado o custo da raiz (e assim da árvore inteira), emitimos o código assim

emission(n):

para cada folha l do tile t selecionado para n façaemission(l);emita o código para t

Emissão de código

O código emitido para o exemplo é

ADDI r_1 ← r_0+1

observe que não é gerado código para o nó +

MEM

+

CONST1 CONS2

Emissão de código

O código emitido para o exemplo é

observe que não é gerado código para o nó +

MEM

+

CONST1 CONS2

ADDI r_1 ← r_0+1LOAD r_1 ←M[r_1+2]

Complexidade dos Algoritmos

• Tanto maximal munch como programação dinâmica tem complexidade linear. Porém a constante do maximal munch é bem menor.– Detalhes no livro do tigre

• Na prática esta fase é muito eficiente se comparada com outras do compilador.

Geradores de geradores

• Existem ferramentas que geram automaticamente um gerador de código– Recebem como entrada a especificação dos

Tiles usando gramáticas– Para cada regra da gramática é associado um

custo e uma ação específica.• Custos são usados para encontrar o Tiling ótimo.• Ações das regras casadas são usadas na fase de

emissão.

39

Análise de Liveness

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

Compiladores

Giovanny Lucero

giovanny@ufs.br

40

Longevidade (Liveness)

• Tradução para código intermediário assume um número ilimitado de temporários

• Máquinas têm um número limitado de registradores• Dois temporários cabem num registrador se eles não são

usados ao mesmo tempo• Excessos de temporários devem ser armazenados em

memória• Análise de Liveness é uma tarefa prévia a alocação de

registradores– Baseado no grafo de fluxo de controle

• a está vivo (live) sse contém um valor necessário no futuro

41

a ← 0L1: b ← a + 1

c ← c + ba ← b * 2if a < N goto L1return c

a:=0

b := a+1

c := c+b

a := b*2

a < N

return c

Grafo de fluxo de controle1

2

3

4

5

6

b está viva em 3→4 e 2→3a em 1→2 e 4→5→2, mas não em 3→4c em todo o programa

Análise de liveness é feita de trás para frente

42

Definições

• definição = ocorrência no lado esquerdo de uma atribuição• uso = no lado direito• def(a)={n| n define a} (a é variável e n nó)• def(n)={a| n define a}• Similarmente definimos use(a) e use(n)• Liveness:

– Uma variável está viva numa aresta se há um caminho dirigido desde esta aresta até um nó que a usa e que não passa por nós que a definem

– Uma variável está viva num nó se ela está viva em alguma aresta que entra neste nó

– Uma variável vive fora de um nó se está viva em alguma aresta de saída

43

Liveness estático vs. dinâmico

a:=b*b

c := a+b

c<=b

return a

1

2

3

4 5

return c

• Note que o nó 4 nunca é alcançado. Logo a não está vivo fora de 2 (liveness dinâmico).

• Obs. dinâmico estático• Infelizmente, liveness dinâmico é

indecidível.• Liveness estático é suficiente para

realizar boas otimizações

44

Interferência entre variáveis

• Análise de liveness é útil para otimizações mas principalmente para alocação de registradores

• Duas variáveis se interferem se não podem ser alocadas num mesmo registrador

– a e b estão vivas na mesma instrução– b está viva numa instrução que define a

há um caso particular para instruções MOVEt s (copia) ...x ... s ... (uso de s)...y ... t ... (uso de t)

t e s não se interferem

45

Grafos de interferência

• Grafo de interferências– os nós são as variáveis– aresta de a para b se a e b se interferem

46

Grafos de interferência

47

Alocação de Registradores

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

Compiladores

Giovanny Lucero

giovanny@ufs.br

48

Alocador de registradores

• Atribui aos temporários um número pequeno de registradores

• Atribui uma locação de memória quando não é possível atribuir um registrador

• Se possível atribui o mesmo registrador a mais de um temporário.

49

• Se reduz ao problema do coloreamento de grafos– Colorir o grafo de interferências (onde os nós são os

temporários)– 1 cor por registrador (K registradores K cores)– nós adjacentes devem ter cores diferentes– o coloreamento se corresponde com uma atribuição de

registradores que satisfaz as interferências– Se não houver coloreamento, alguns temporários são

alocados em memória (spilling)• O problema é NP-Completo• Boa aproximação em tempo linear

Alocador de registradores

50

Coloreando por simplificação

• Cinco fases: Build, Simplify, Spill, Select e Start Over• Build

– Construa o grafo de interferências (análise de dataflow)• Simplify (heurística simples)

– Se grau(n) < k coloreie G’ e então pinte n com uma cor diferente dos seus vizinhos (implementado com uma pilha de nós).

• Spill– Se todos os nós tem grau ≥ k escolha um nó

candidato a eliminação (alocação em memória). Seja otimista e empilhe.

51

Coloreando por simplificação• Select: começando pelo grafo totalmente descolorido

desempilhe nós um por um e então faça:• Se o nó foi empilhado pela condição grau(n)<K, pinte

de uma cor diferente dos vizinhos• Se foi candidato a eliminação, confira se o spilling é

realmente preciso (pode ser que vizinhos repitam cores).Pinte se não houver spilling real.Se houver spilling real continue o select identificando outros spillings reais.

• Start Over– Se o Select detectou spillings reais, reescreva o programa,

pegando os valores da memória antes de c/uso e atualizando a memória a c/ definiçao.

– Repita o processo todo novamente

52

ExemploBuild

53

Exemplo

Escolhemos um nó de grau <= k e empilhamos

Simplify/Spill

54

Exemplo

Pilha

Simplify/Spill

55

X

Select

56

X

X

Select

57

Select

58

Coalescer

• Eliminar redundantes MOVEs– se a e b não se interferem MOVE a b pode ser

eliminado, juntando a e b em um único nó– O grafo resultante pode não ser k-colorável

• Estratégia Briggs: (não altera a k-coloração)– a e b podem ser coalescidos se o nó resultante ab tem

menos que k vizinhos com grau significativo (≥ k arestas)

• Estratégia George: (não altera a coloração)– a e b podem ser coalescidos se para todo vizinho t de a,

ou t interfere b ou t tem grau insignificante

59

Coloreamento com Coalescimento• Build

– Construa o grafo de interferências.Categorize os nós como “MOVE” e “não MOVE”

• Simplify– Empilhe só nós “não MOVE” de grau < k

• Coalesce– Usar George e Briggs no grafo reduzido obtido da simplificação– Faça simplify e coalesce até sobrar só nós “MOVE” ou de grau

significante• Freeze

– Não é possível simplify ou coalesce, escolha um nó move de baixo grau. “Congele” os MOVEs deste nó. Volte.

• Spill e Select como antes

60

Build

Simplify

Coalesce

Freeze

Potential spill Select

Actual spill

61

Quais temporários são MOVE?

62

Quais temporários são MOVE?

63

Exemplo

Pilha

Neste momento posso pensar em coalescer (unir os nós)

c e d possuem somente dois vizinhos de grau significante (Briggs)

64

ExemploMais alguém?

65

Exemplo

66

Exemplo

67

Nós Pré-coloridos

• Frame pointer, registradores standard para argumentos, etc.

• Select e Coalesce podem dar a um temporário ordinário a cor de um pré-colorido sempre que não haja interferência

• Nós pré-coloridos não podem passar pela fase simplify (não podemos escolher a cor)

• Nunca fazemos spilling de pré-coloridos

68

Cópias temporárias de registradores

• Como pré-coloridos não são spilled, o front-end deve cuidar que a vida destes seja curta

69

Registradores caller-save e calle-save

• Instrução CALL interfere com todos os registradores caller-save– Se uma variável não sobrevive além de um

procedimento, a tendência é coloca-lo num registrador caller-save

– Caso contrário, ela fica em um calle-save.

Acabou!!!