Parte III
Gerador de Código do Pro64
José Nelson Amaral
University of Alberta
Edmonton, AB, Canada
http://www.cs.ualberta.ca/~amaral
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
1
Conteúdo
Diagrama de blocos do gerador de código
Formação de Hyperblock e inserção de
predicados (HBF)
Sistema de Consulta de Predicados (PQS)
Preparação de Loops (CGPREP) e software
pipelining
Escalonamento global and local (IGLS)
Alocação de registradores global (GRA) e local
(LRA)
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
 WHIRL/CGIR e TARG-INFO
2
Diagrama de Blocos do
Gerador de Código
WHIRL
Rebaixamento WHIRL-to-TOP
EBO:
Otimização
Estendida de
blocos básicos,
peephole,
etc.
PQS:
Sistema de
Consulta de
Predicados
Opt Fluxo Controle II
EBO
CGIR: Quad Op List
Opt Fluxo Controle I
EBO
IGLS: pre-pass
GRA, LRA, EBO
IGLS: post-pass
Opt Fluxo Controle
Formação de Hiperbloco
Redução Caminho Crítico
Processamento de Loops Internos:
expansão, EBO
Prep. Loops,
software
pipelining
Workshop
em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
Emissão de Código
3
Formação de Hiperblocos e
Execução Predicada
Hiperbloco: região de fluxo com únicaentrada e múltiplas-saídas:
corpo de loops, região de ifs, etc.
Algoritmo de formação de Hiperbloco
Baseado no método desenvolvido por
Scott Mahlke [Mahlke96]
Extensão da SGI habilita a “duplicação
condicional do rabo” baseada em
heurísticas para eliminar efeitos colaterais
Workshop em Sistemas
(p.e. duplicação
dedecódigo).
Computacionais
Alto
Desempenho, Setembro 2001
4
Algoritmo de Formação de
Hiperbloco
Identificação
de Região
Seleção
de Blocos
Duplicação
de Rabo
Conversão
de Ifs





Regiões “redes” (ifs)
Loops internos
Regiões Gerais (baseadas em sequência)
Caminhos ordenados por prioridades
Inclusão de um caminho é guiada por seu
impacto em recursos, duração do schedule, e
nível de prioridade
Objetivo: Manter duração do escalonamento próxima à
duração do caminho com máxima prioridade.
 Desvios internos são substituídos por
predicados
 Reuso de predicados
Workshop em Sistemas

Saídas laterais
Computacionais de Alto
Desempenho, Setembro 2001
5
Seleção de Blocos para
Formação de Hiperblocos
Dois objetivos conflitantes:
(1) Mais blocos podem potencialmente melhorar
o desempenho através da eliminação de desvios
entre os blocos incluídos.
(2) Muitos blocos podem resultar em perda de
desempenho por causa da saturação dos recursos
do processador ou pelo aumento da altura de
dependências.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
6
Função de Priorização de
Caminhos
A função de priorização de caminhos combina
quatro elementos:
(1) a freqüência de execução dos caminhos;
(2) o número de instruções no caminho;
(3) altura da dependência do caminho;
(4) condições de perigo no caminho;
Intuição: inclui caminhos com menos instruções,
com altura de dependência mais baixa,
que possuem menos condições de perigo,
e que são executados com maior freqüência.
Condições de perigo incluem chamadas de funções
Workshopna
em Sistemas
e armazenamentos
memória não resolvidos.
Computacionais de Alto
Desempenho, Setembro 2001
7
Algoritmo de Duplicação
do Rabo
Para converter o conjunto de blocos selecionados em
um hiperbloco (com um único bloco de entrada),
fluxo de controle dos blocos não-selecionados
(pontos de entrada laterais) tem que ser eliminados.
O algoritmo de duplicação do rabo primeiro marca
todos os blocos que possuem pontos de
entrada lateral.
Depois o algoritmo marca todos os blocos que
podem ser alcançados a partir dos blocos marcados.
Todos os blocos marcados formam os rabos que
Workshop em Sistemas
devem ser duplicados.
Computacionais de Alto
Desempenho, Setembro 2001
8
Propriedades do Algoritmo de
Formação de Hiperbloco no
Pro64
Formar “bons” vs. “ótimos” hiperblocos
Duplicação condicional de código
Reduzir duplicação desnecessária
Integração de HPF com escalonamento
global - uma parte integrada do IGLS
Evitar reversão desnecessária de
conversão de ifs
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
9
Formação de Hiperbloco - Um
Exemplo
1
1
1
4,5
2
6,7
8
aa = a[i];
bb = b[i];
switch (aa) {
case 1:
if (aa < tabsiz)
aa = tab[aa];
case 2:
if (bb < tabsiz)
bb = tab[bb];
default:
ans = aa + bb;
4
4
2
2
5
5
7’
7
7
8
8
H1
(a) Fonte
(b) CFG
6’
6
6
8’
H2
(c) Formação de Hiperblocos
com duplicação agressiva
de rabo
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
10
Formação de Hiperbloco - Um
Exemplo
Cont.
1
1
1
4
4
2
2
4
2
H1
5
5
6’
6
5
6
6
7’
7
7
8’
8
8
(a) CFG
H1
H2
(b) Formação de Hiperblocos
em Sistemas
com Workshop
duplicação
agressiva
Computacionais de Alto
de rabo
Desempenho, Setembro 2001
7
H2
8
(c) Formação de hiperblocos
no Pro64
11
Sistema de Consulta de
Predicados (PQS)
Objetivo: coletar informação e oferecer
interfaces que permitem que outras fases do
compilador consultem relações entre os
valores dos predicados.
Funções do PQS functions (exemplos)
BOOL PQSCG_is_disjoint (PQS_TN tn1, PQS_TN tn2)
BOOL PQSCG_is_subset (PQS_TN_SET& tns1, PQS_TN_SET& tns2)
Eficiência: O(log n), onde n é o número de
temporários (TNs) ancestrais.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
12
Preparação de Loops e
Optimização para Software
Pipelining
Canonização de Loops para SWP
Remoção de Leitura/Escrita (register
aware)
Expansão de Loops (resource aware)
Remoção de recorrências
Pré-busca (vários tipos)
Conversão de Ifs forçada
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
13
Revisão do Método de
Software Pipelining do Pro64
Aplicado somente a loops adequados a SWP
Extensiva preparação e otimização de loops
antes da aplicação de SWP [DehnertTowle93]
Algoritmo de SWP sensível a longevidade dos
valores produzidos [Huff93]
Alocação de Registradores depois de escalonamento baseada em Cydra 5 [RLTS92, DeTo93]
Otimiza while e do loops
Simples conversão para escalonamento sem
em Sistemas
SWP quando Workshop
SWP
falha.
Computacionais
de Alto
Desempenho, Setembro 2001
14
Escalonamento em Módulo
Sensível a Longevidade para
SWP no Pro64
Propriedades
 Tenta inserir cada
operação ASAP ou ALAP
para minimizar pressão
em registradores
 Escalonamento com
Folgas
 Retentativas limitadas
 Escalonamento baseado
em operações
Compute Estart/Lstart para
todas ops não inseridas
Escolha uma “boa” operação
para inserir no escalonamento
parcial no períodoEstart/Lstart
sim
Sucesso
não
Aloca
Regist.
fim
Remove Ops c/conflito
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
15
Método Integrado de
Escalonamento Global e
Local (IGLS)
O IGLS integra movimento global de
código (GCM) com escalonamento local
[MantripragadaJainDehnert98]
IGLS estendido a escalonamento de
hiperbloco
Executa movimento lucrativo de código
entre hiperblocos e regiões normais
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
16
Diagrama de Blocos
da Fase IGLS
Escalonamento de
Hiperblocos (HBS)
Seleção Prioritária de Blocos
Movimento Global de
Código (GCM)
Seleção de Movimento
Seleção de Alvo
Escalonamento Local
de Código (LCS)
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
17
Vantagens da Extensão do
IGLS
Um Re-exame do Exemplo
1
 Vantagens:
Não existem
fronteiras fixas
entre
hiperblocos e
não-hiperblocos
GCM move
código para
dentro ou para
fora de um
hiperbloco de
acordo com o
custo
1
4
4
2
2
H1
5
5
6
6
7
7
H2
H1
8
(a) Hiperbloco no Pro64
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
8
8’
H2
(b) Extensão
do Hiperbloco
18
Software Pipelining
vs
Escalonamento Normal
Sim
loop candidato
a SWP ?
IGLS
Processam. de Loop
Interior (SWP)
GRA/LRA
Falha/sem lucro
Sucesso
Não
IGLS
Emissão de Código
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
19
WHIRL
Baseado em Árvores Abstratas de
Sintaxe
Representação é simples e eficiente
Usada em várias fases através de
rebaixamento
Projetada para múltiplas arquiteturas
Usa mapas e tabelas de símbolos
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
20
Representação Intermediária
para Geração de Código
(CGIR)
Simples e convencional
Arquitetura Load/store
Predicação
Flags em operações (cópia, adição inteira,
load, etc.)
Flags em operandos (TNs)
Estruturada como blocos básicos
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
21
Alocação de Registradores
Global e Local
(GRA/LRA)
 LRA-RQ gera uma
estimativa para o número
de registradores requeridos
 Aloca variáveis globais
usando um alocador
baseado na prioridade de
registradores
[ChowHennessy90,Chow83,
Briggs92]
Do prepass IGLS
GRA
LRA Pedido de Registr.
LRA-RQ
Alocação de Registr.
Baseada na Prioridade
de Registradores
comExtensões p/IA-64
 Incorpora extensões
específicas a IA-64, e.g.
uso da pilha de Workshop em Sistemas
Computacionais de Alto
registradores
Desempenho, Setembro 2001
LRA
Para postpass IGLS
22
Alocador de
Registradores do Pro64
Baseado em Prioridades
Create_LRANGE
GRA-Create
(live range set)
Create_Live_BB_Sets
(para cada live range,
descubra blocos onde a variável está viva)
Create_Interference_Graph
(percorre o grafo
em ordem topológica reversa para encontrar
intervalos de vida que são simultaneamente vivos)
Simplify
GRA-Color
GRA-Spill
(forma uma pilha de LRs para ser colorida de
cima para baixo)
Choose_Register or GRA_Note_Spill
Spill
(Spill
e otimiza
a localização de spill-code)
Workshop
em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
23
Alocação Local de
Registradores (LRA)
 Assign_registers
usa uma
varredura linear
reversa com
prioridade
 Reordenamento:
Ordenação em
“depth-first” no
DDG
Assign_Registers
falha
sucesso
Fix_LRA
primeira
vez
Reordenamento
de Instruções
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
Spill global
spill local
24
Do WHIRL ao CGIR:
Um Exemplo
i
T1 = sp + &a;
T2 = ld
T1
T3 = sp + &i;
T4 = ld
T3
T5 = sxt T4
T6 = T5 << 2
T 7 = T6
T 8 = T2 + T7
T9 = ld T8
T10 = sp + &aa
:= st T10 T9
(b) WHIRL
(c) CGIR
ST aa
int *a;
int
i;
int
aa;
aa = a[i];
LD
+
a
*
CVTL32
(a) Fonte
4
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
25
Do WHIRL ao CGIR
Cont’d
Informação passada:
informação de alias
informação de loop
tabela de símbolos e
mapeamentos
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
26
A Tabela com Informação
Sobre a Arquitetura Alvo
(TARG_INFO)
Objetivo:
Descrição parametrizada da máquina alvo
e da arquitetura do sistema
Separa detalhes da arquitetura dos
algoritmos do compilador
Minimiza mudanças no compilador
quando o compilador é adaptado para
uma nova arquitetura.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
27
A Tabela com Informação
Sobre a Arquitetura Alvo
(TARG_INFO) (Cont.)
Baseada em uma extensão das tabelas
da Cydra, com grandes melhoramentos
Modelos de architetura que já foram
implementados com a TARG_INFO:
Toda a família MIPS
IA-64
IA-32
Processadores gráficos da SGI (versão
anterior)
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
28