Seleção de Instruções

Seleção de Instruções

Nós em Instruções

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

• Nós de IR implementam uma operação;
• muitas máquinas podem adicionar e ler da memória na mesma instrução;
• Selecção de Instruções escolhe as melhores instruções para implementar uma IR.

Padrões em Árvores

• associam fragmentos de IR com instruções;
• Objectivo é numero mínimo de instruções.
• Máquina Jouette:

  ADD	ri   <-   rj+rk
  MUL	ri   <-  rj×rk
  SUB	ri   <-  rj-rk
  DIV	ri   <-  rj/rk
  ADDI	ri   <-  rj+c
  SUBI	ri   <-  rj-c
  LOAD	ri   <-  M[rj+c]
  STORE	M[rj+c]  <-  ri
  MOVEM	M[rj]  <-  M[ri]

  Supomos que r₀ a zero.

Á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

• Menor número de instruções;
• Instruções que levam menor tempo;
• Óptimo: soma o menor custo possível;
• Optimal: duas telhas adjacentes não podem ser substituidas por telhas de melhor custo;
• Óptimo contém optimal.
• Problema: interacção de instruções.
• ISAs:
  • RISC não tem muita flexibilidade;
  • CISC tem telhas grandes e muitas opções.

Maximal Munch

Algoritmo guloso:

• Gerar instruções em order inversa (visita pósfixa);
• Escolher a telha com mais nós;
• Senão, escolha arbitrária;
• Implementação em C:
  • munchStm() percorre frases;
  • munchExp() percorre expressões;
• Algoritmo termina bem: para cada nó existe pelo menos uma telha.

Programação Dinâmica

Maximal Munch não é óptimo:

• Programação Dinâmica encontra óptimo encontrando óptimos para sub-problemas;
• Cada nó n tem um custo, que é o custo total da árvore com n por raiz;
• Trabalha bottom-up;
• Para cada nó n:
  1. Encontra custos dos filhos, netos, recusivamente;
  2. Aplica todos os padrões contra n;
  3. O custo da telha t será c + SUMc_i.
• Faz emissão de instruções:
  1. para cada folha l_f da telha selecionada para n, emite para l_i;
  2. Emite instrução para n.

Programação Dinâmica: exemplo

• CONST 1 é um ADDI de custo 1;
• CONST 1 é um ADDI de custo 1;
• ADD

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

• MEM

Telha	Instrução	Nó	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:

• Schizo-Jouette tem registos a para endereços, e d para dados:
  1. ADD(I), MUL, SUB(I), DIV usam d;
  2. LOAD, STORE, MOVEM usam a;
  3. MOVEA faz d_j <- a_i;
  4. MOVED faz a_j <- d_i;
• Programação dinâmica deve saber do custo mínimo usando registo a e registo d;

• Usar gramáticas, eg LOAD, MOVEA, MOVED:

  d	->	MEM(+(a,CONST))
  d	->	MEM(+(CONST,a))
  d	->	MEM(CONST)
  d	->	MEM(a)
  d	->	a
  a	->	d

• Altamente ambígua:
  • generalizar programação dinâmica,
  • computar custo mínimo para cada não terminal.

Implementam este algoritmo:

• cada regra tem um custo e uma acção:
  • custos para solução óptima;
  • ações para emitir instruções.
• Output é um programa em C;
• Convenientes para máquinas CISC:
  • VAX tem 112 regras e 20 não terminais;
  • MC68020 141 regras e 35 não terminais.
  • instruções com mais de um resultado são dificeis.
• Exemplos: Twig e BURG.

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

• Examinar todas as telhas;
• Usar um case e comparar pelo tipo do nó;

Complexidade:

• N nós;
• T telhas, K telhas unificam em média, K' número máximo de nós a examinar por telha, T' padrões por nó;
• RISC: T = 50, K = 2, K'= 4, T'=5;
• Maximum Munch:
  1. considera N/K nós (não tem que ver não-folhas);
  2. Para cada nó vê K' nós e testa se optimal T' vezes: K'+T';
  3. Total: (K'+T')N/K).
• Programação dinâmica: (K'+T')N.

Máquinas RISC

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

Máquinas CISC

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: r₁ <- r₁ OPr₂;
5. muitos modos de endereçamento;
6. instruções de tamanho variável;
7. side-effects em instruções.

Pentium

1. 6 registos gerais;
2. multiplicação e divisão usam eax;
3. operações podem mexer em memória:
   1. r₁ <- r₁ OPr₂,
   2. M[r₁+c] <- M[r₁+c] OPr₂,
   3. r₁ <- r₁ OPM[r₂+c],
   4. M[r₁+c₁] NOT <- M[r₁+c₁] OPM[r₂+c₂],

Soluções para CISC

1. Poucos registos:
   • gerar temporários livremente;
   • problema do alocador de registos.
2. Classes de registos:
   • Multiplicação precisa de eax;
   • Mover o operando e resultado explicitamente:

     mov  eax,t1		eax	<- t1
     mul  t2		eax	<- eax ×t2;
     		edx	<- lixo
     mov  t3,eax		t3	<- eax

3. Dois endereços:
   • Adicionamos instruções extra:

     mov  t1,t2		t1	<- t2
     add  t1,t3		t1	<- t1 + t3

   • Esperamos que t₁ e t₂ no mesmo registo.
   • mov seria então removido.
4. Aritmética pode usar memória:
   • Cada TEMP é um "registo", mas pode ser MEM;
   • Alternativa, forçar registos:

     mov	eax,[ebp-8]
     add	eax,exc		add	[ebp-8],ecx
     mov	[ebp-8],eax

   • Duas sequências demoram o mesmo tempo;
   • Esquerda mexe em eax
5. Múltiplos modos de endereçamento:
   • Não ganham velocidade, codificação + curta, mexem em menos registos;
   • usar padrões mais complexos.
6. Tamanho variável de instruções não afecta compilador.
7. Side effects r₂ <- M[r₁];  r₁ <- r₁+4:
   • Ignorar auto-incremento;
   • Ad-hoc;
   • Usar padrões-DAG.

Implementação em Tiger

Alocação de registos?

• Alocação de registos pode ser feita ao mesmo tempo;
• Alg. independente de máquina: fazer antes ou depois;
• Antes não se pode ser muito preciso, mas feito às vezes.

• OPER: instrução assem, lista de operandos src, lista de resultados dst, e um jumps;
• LABEL é um ponto de salto: assem mostra como é a label em assembly, e label com símbolo;
• MOVE: como OPER, mas move dados (sem jumps).
• As_printf escreve em arquivo.

Mapa Temporário

Temp_map

• Tabela cuja chave é Temp_temp e cujo resultado é uma string;
• Mapeamentos podem ser encadeados: layer(sigma₁,sigma₂) tenta look(sigma₁,t) e depois look(sigma₂,t);
• Alocador de registos vai usar este mapa para descrever os nomes dos registos;
• Tb usado para registos especiais (fp, sp) e debugging.

Mapa Temporário

Esquema independente do tipo de máquina:

• apenas assem diz qual o nome da instrução;

  

  As_oper("LOAD 'd0 <- M['s0+8]",
       Temp_TempList(Temp_newtemp(), NULL),
       Temp_TempList(T_Temp(F_FP()), NULL),
       NULL)
  

• Obs: saltos condicionais têm várias labels em jumps mas habitualmente referem apenas uma.

Chamadas de Procedimentos

• Todos os argumentos são primeiro colocados nas suas posições correctas;
• munchArgs coloca os argumentos e retorna lista de temporários:
  • Usados para análise de vida;
• Destinos de call são registos que são destruídos: caller-save, endereço de retorno e valor de retorno.
• Semelhante para mul no Pentium: destinos são eax e edx;
• Se frame pointer não é usado:
  • usar fp virtual baseado em sp;
  • problema é que sp só é conhecido mais tarde.

Seleção de Instruções