Vida de VariáveisTopBlocos BásicosSeleção de Instruções

Seleção de Instruções

Nós em Instruções

Obj: gerar instruções para cada nó:

Padrões em Árvores

Árvores e Jouette

a[i] = x

2 LOAD r1   <-  M[fp+a]
4 ADDI r2   <-  r0+4
5 MUL r2   <-  ri ×r2
6 ADD r1   <-  r1 + r2
8 LOAD r2   <-  M[fp+x]
9 STORE M[r1+0]  <-  r2

a[i] = x

2 LOAD r1   <-  M[fp+a]
4 ADDI r2   <-  r0+4
5 MUL r2   <-  ri ×r2
6 ADD r1   <-  r1 + r2
8 ADDI r2   <-  fp+x
9 MOVEM M[r1]  <-  M[r2]

a[i] = x

2 ADDI r1   <-  r0+a
3 ADD r1   <-  fp+r0
4 LOAD r1   <-  M[r1+0]
6 ADDI r2   <-  r0+4
7 MUL r2   <-  ri ×r2
8 ADD r1   <-  r1 + r2
9 LOAD r1   <-  r1 + r2
11 ADDI r2   <-  r0 + x
12 LOAD r2   <-  M[r2+0]
13 STORE M[r1+0]   <-  r2

Tiling óptimo e optimal

O melhor tiling corresponde à sequência de menor custo:

Maximal Munch

Algoritmo guloso:

Programação Dinâmica

Maximal Munch não é óptimo:

Programação Dinâmica: exemplo

Telha Instrução Folhas Total
ADD 1 1+1 3
ADDI 1 1 2
ADDI 1 1 2
Telha Instrução Folhas Total
LOAD 1 2 3
LOAD 1 1 2
LOAD 1 1 2

Gramáticas de Árvores

Para máquinas com conjuntos complexos de instruções, e muitos tipos de registos e modos de endereçamento, existe uma generalização:

Implementam este algoritmo:

Todas as telhas que unificam têm que ser testadas:

Complexidade:

Na prática são muito rápidos.

Máquinas RISC

Características:
  1. 32 registos;
  2. uma classe de registos inteiros;
  3. aritmética entre registos;
  4. instruções de 3 endereços: r1 <- r2 OPr3;
  5. load e store com M[r+c];
  6. instruções de 32 bits;
  7. um resultado por instrução.

Máquinas CISC

Características:
  1. Registos: 6, 8,16;
  2. classes diferentes de registos inteiros;
  3. aritmética pode usar memória;
  4. instruções de 2 endereços: r1 <- r1 OPr2;
  5. muitos modos de endereçamento;
  6. instruções de tamanho variável;
  7. side-effects em instruções.

Pentium

32 bits:
  1. 6 registos gerais;
  2. multiplicação e divisão usam eax;
  3. operações podem mexer em memória:
    1. r1 <- r1 OPr2,
    2. M[r1+c] <- M[r1+c] OPr2,
    3. r1 <- r1 OPM[r2+c],
    4. M[r1+c1] NOT <- M[r1+c1] OPM[r2+c2],

Soluções para CISC

  1. Poucos registos:
  2. Classes de registos:
  3. Dois endereços:
  4. Aritmética pode usar memória:
  5. Múltiplos modos de endereçamento:
  6. Tamanho variável de instruções não afecta compilador.
  7. Side effects r2 <- M[r1];  r1 <- r1+4:

Implementação em Tiger

Alocação de registos?

Usamos tipo para assembly sem registos:

Mapa Temporário

Temp_map

Mapa Temporário

Esquema independente do tipo de máquina:

Chamadas de Procedimentos


vitor@cos.ufrj.br

Vida de VariáveisTopBlocos BásicosSeleção de Instruções