Upload
peri
View
21
Download
0
Embed Size (px)
DESCRIPTION
Departamento de Estatística e Informática Universidade Federal de Sergipe Compiladores. Blocos básicos e Traces. Giovanny Lucero [email protected]. Adequação de Tree. Alguns aspectos de Tree não tem correspondência com linguagens de máquina CJUMP tem dois rótulos - PowerPoint PPT Presentation
Citation preview
Blocos básicos e Traces
Departamento de Estatística e InformáticaUniversidade Federal de Sergipe
Compiladores
Giovanny Lucero
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
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
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
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!!!