Análise de Fluxo de Dados
(Dataflow Analysis)
Parte I
Construção e Optimização de Compiladores
2003/04
Salvador Abreu
Universidade de Évora
Departamento de Informática
Introdução
●
Transformações/Análises que vimos:
–
–
●
Vamos fazer:
–
–
–
●
●
●
Sobre a RI.
Após a passagem RI para código (MIPS, ...)
Mudança de representação (ao nível da RI!)
Análises sobre a RI.
Transformações da RI.
A geração de código mantém-se.
O fundamental é a análise de fluxo de dados
assente num grafo de fluxo de controle.
Ver referência principal, Cap. 17.
Representação
●
Regressamos às Arvores de RI
–
–
●
Porque queremos saber mais sobre o que as instruções
fazem
Porque as optimizações são em larga medida
independentes da arquitectura objecto
Temos de Simplificar mais a RI
–
Procurar que as expressões sejam “triviais”
●
Não devem conter sub-expressões complexas
–
●
Só acessos a temporários
Como fazer:
–
–
–
Sempre que ocorre um op ou um mem dentro dum op,
op, mem,
mem, jump
ou cjump:
cjump:
Introduzimos um novo temp e enquadramos num eseq.
eseq.
Aplicamos o método de canonificação para remover os eseq.
eseq.
Quadruplos
●
●
Objectivo: simplificar a RI no sentido de reduzir a
diversidade de expressões que ocorrem
Chamam-se “quadruplos” porque o nó típico é:
●
–
–
i.e. contém 4 características distintas
Pode ser representado como um quadruplo:
quadruplo:
●
●
D <- F1 OP F2
(OP, D, F1, F2)
Também se designa os quadruplos por “threeaddress code” por especificarem 3 “endereços”
(na realidade, temporários)
O que fica na RI simplificada?
Instrução (quadruplo)
t = a OP b
t = MEM[a]
MEM[a] = b
if (a OP b) goto L1 else goto L2
goto L
L:
f(a1, ... an)
t = f(a1, ..., an)
Padrão RI
move(t, op(OP, a, b))
move(t, mem(a))
move(mem(a), b)
cjump(OP, a, b, L1, L2)
jump(L)
label(L)
expr(call(f, a1, ..., an))
move(t, call(f, a1, ..., an))
Análises de Fluxo de Dados
●
Tudo calculado com base na AFD:
–
Alcance de Definições
●
●
–
Expressões Disponíveis
●
–
Indicam quais as expressões que já foram calculadas (e cujas
premissas não mudaram) em cada instrução
Alcance de Expressões
●
–
Como análise use/def + live{in,out}
Aplicado à RI revista
Necessário para a eliminação de sub-expressões redundantes
Análise de Vitalidade
Alcance de Definições
●
Problema:
–
–
Ver até onde chega uma afectação a um temporário
Dois pontos:
●
●
●
O local onde o temporário é definido
Os locais onde o temporário é usado
Abordagem
–
Etiquetar cada instrução si com di (ao nível da RI)
–
Associar a cada temporário t:
●
–
defs:
defs: { instruções di } nas quais t é definido
Associar a cada instrução si / di:
●
gen:
gen: instruções para a qual o temporário é definido {d
{di}
●
kill:
kill: instruções cujas definições são anuladas defs(
defs(t)-{d
)-{di}
gen e kill para Alcance de Definições
Instrução
d: t = a OP b
d: t = MEM[a]
MEM[a] = b
if (a OP b) goto L1 else goto L2
goto L
L:
f(a1, ... an)
d: t = f(a1, ..., an)
gen(s)
{d}
{d}
{}
{}
{}
{}
{}
{d}
kill(s)
defs(t) – {d}
defs(t) – {d}
{}
{}
{}
{}
{}
defs(t) – {d}
AFD para Alcance de Definições
●
Usar gen e kill para definir
–
–
in,
in, out:
out: definições em vigor à entrada e saída de cada
instrução (com etiqueta n).
dados pelas equações de fluxo de dados:
●
●
–
●
●
in(
in(n) = U out(
out(p) / p in pred(
pred(n)
out(
out(n) = gen(
gen(n) U (in
(in((n) – kill(
kill(n))
Requer grafo de fluxo de controle (para pred)
pred)
Semelhante ao cálculo de LIVEin e LIVEout (ponto
fixo dum operador monótono)
Resultado
–
Para cada instrução, a lista de instruções cujas
definições estão activas à entrada (in
).
(in)) e à saída (out
(out).
Expressões Disponíveis
●
Indicam quais as expressões que já foram
calculadas (e cujas premissas não mudaram) em
cada instrução
–
–
Objectivo: reconhecer ocorrências múltiplas do mesmo
valor no código.
e = a OP b está disponível no nó n sse:
●
●
●
e foi calculada em todos os caminhos da entrada até n.
não há definições para a nem b desde o último cálculo de e.
Pode ser implementado como solução de
equações de fluxo de dados com definições
apropriadas de gen e kill:
gen e kill para Expressões Disponíveis
Instrução
gen(s)
kill(s)
d: t = a OP b
d: t = MEM[a]
MEM[a] = b
if (a OP b) goto L1 else goto L2
goto L
L:
f(a1, ... an)
d: t = f(a1, ..., an)
{a OP b} – kill(s)
{MEM[a]) – kill(s)
{}
{}
{}
{}
{}
{d}
expressões com t
expressões com t
expressões da forma MEM[x]
{}
{}
{}
expressões da forma MEM[x]
expressões da forma MEM[x] e
expressões com t
AFD para Expressões Disponíveis
●
Usar gen e kill para definir
–
–
in,
in, out:
out: expressões disponíveis em vigor à entrada e
saída de cada instrução (com etiqueta n).
dados pelas equações de fluxo de dados:
●
●
–
Cuidado que in(
in(n) é calculado com base na intersecção
●
●
in(
in(n) = ∩ out(
out(p) / p in pred(
pred(n)
out(
out(n) = gen(
gen(n) U (in
(in((n) – kill(
kill(n))
a expressão tem de estar disponível por todos os caminhos
Resultado
–
Para cada instrução, a lista de instruções cujas
expressões calculadas estão activas à entrada (in
(in)) e à
saída (out
).
(out).
Implementação em GNU Prolog/CX
●
Ideia geral:
–
–
Usar uma unit genérica de resolução de equações de
fluxo de dados (EFD).
O contexto especifica:
●
O grafo de fluxo de controle.
–
●
Um predicado que especifique uma aplicação do operador que
representa as EFD.
–
–
●
Estabelece relações de adjacência entre nós (succ/pred).
O pressuposto é que todo o estado é representado como um único
termo, que será re-escrito pela invocação deste predicado.
O estado inicial deverá ser fornecido e ser passível de ter uma
interpretação correcta pelo predicado de re-escrita.
Uma ou mais relações que denotam propriedades estáticas
dos nós.
:-unit(fix).
:- unit(fix).
fix(INITIAL, FINAL) ::^ step(INITIAL, INTERMEDIATE),
fixpoint(INITIAL, INTERMEDIATE, FINAL).
fixpoint(STATE, STATE, STATE) :- !.
fixpoint(_, INTERMEDIATE, FINAL) :fix(INTERMEDIATE, FINAL).
Uso da unit fix: um exemplo.
:-unit(dataflow).
step(_INin-OUTin, IN-OUT) :use(USE),
def(DEF),
subargs :> subtract(OUTin, DEF, OUTx),
subargs :> merge(USE, OUTx, IN),
subargs :> union_succ(IN, OUT).
●
Caso da análise de vitalidade:
–
–
–
–
–
Define-se uma unit que especifique o predicado step/2.
step/2.
Notar os parâmetros de entrada e saída.
Representa uma aplicação das EFD.
Recorre ao contexto para definir use/1 e def/1.
def/1.
Unit auxiliar subargs para efectuar operações de
conjunto.