ReferencesTopSeleção de InstruçõesVida de Variáveis

Vida de Variáveis

Variáveis Temporárias

Duas variáveis a e b cabem no mesmo registo:

Exemplo

a <- 0
L1 b <- a+1
c <- c+b
a <- b ×2
if  a < N  goto  L1
return c

Exemplo: b

Exemplo: a

Exemplo: c

Equações de Fluxo de Dados

Usos e definições

Vida de Variável

Uma variável diz-se viva num vértice se

Uma variável diz-se viva na entrada a um nó se

Uma variável diz-se viva na saída a um nó se

Cálculo de Vida

  1. Se uma variável está em use[n], então é live-in em n;
  2. Se uma variável está live-in em n, então é live-out em todos os nós m em pred[n];
  3. Se uma variável está live-out em n, e não em def[n], então é live-in em n;
Como equações:

in[n] = use[n] U(out[n] - def[n])
out[n] = UNIONs em succ[n] in[s]

Cálculando Vida

Podem ser resolvidas iterativamente:
for each   n
in[n] <- {};out[n] <- {}
repeat n
for each n
in'[n] <- in[n]; out'[n] <- out[n]
in[n] <- use]n] U(out[n] - def[n])
out[n] <- UNIONs em succ[n] in[s]
until in'[n] = in[n] /
out'[n] = out[n] for all n

Exemplo de Iterações

1 iter 2 iter 3 iter
uso def in out in out in out
1 a a a
2 a b a a bc ac bc
3 bc c bc bc b bc b
4 b a b b a b a
5 a a a a ac ac ac
6 c c c c
4 iter 5 iter 6 iter 7 iter
in out in out in out in out
1 ac c ac c ac c ac
2 ac bc ac bc ac bc ac bc
3 bc b bc bc bc bc bc bc
4 b ac bc ac bc ac bc ac
5 ac ac ac ac ac ac ac ac
6 c c c c

Optimização

Tentar seguir a ordem de propagação mais natural:

1 iter 2 iter 3 iter
uso def in out in out
6 c c c c
5 a c ac ac ac ac ac
4 b ab ac bc ac bc ac bc
3 bc c bc bc bc bc bc bc
2 a b bc ac bc ac bc ac
1 a ac c ac c ac c

Melhoramentos

Blocos básicos:

Sequencial:

Representação de Conjuntos

Complexidade Temporal

Programa de tamano N:

Ponto Fixo Mínimo

X Y Z
uso def in out in out in out
1 a c ac cd acd c ac
2 a b ac bcacd bcd ac b
3 bc c bc bcbcd bcd b b
4 b a bc acbcd acd b ac
5 a ac acacd acd ac ac
6 c c c c

Vida Estática e Dinâmica

Gostariamos de saber exactamente que variáveis estão vivas em cada nó:

Halting Problem

Grafos de Interferência

a e b podem ser alocadas ao mesmo registo se não intererem:

Interferência em MOVE

t <- s          (copy)
...
x <- ...s ... (uso   de   s)
...
x <- ...t ... (uso   de   s)


vitor@cos.ufrj.br

ReferencesTopSeleção de InstruçõesVida de Variáveis