Software Livre Pro64:
Uma Infra-estrutura para
Compiladores
Mini-Curso
José Nelson Amaral
Compiler Design and Optimization Laboratory
Department of Computing Science
University of Alberta
Edmonton, AB, Canada
http://www.cs.ualberta.ca/~amaral
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
1
2000
1998
1990
1994
1988
1980
Colaboradores
O Grupo de Desenvolvimento dos
Compiladores MIPSpro/Pro64 da SGI
Universidade de Delaware
Time de Compiladores do CAPSL
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
3
Colaboradores (cont.)
Estes indivíduos contribuíram diretamente
para este mini-curso:
A. Douillet (Udel)
S. Chan (Intel)
G. R. Gao (U. Delaware)
Z. Hu (Udel)
S. Liu (HP)
S. Mantripragada (SGI)
M. Murphy (SGI)
D. Stephenson (SGI)
D. Whitney (SGI)
F. Chow (Equator)
J. Dehnert (Trasmeta)
W. Ho (Routefree)
K. Lesniak (SGI)
R. Lo (Routefree)
C. Murthy (SGI)
G. Pirocanac (SGI)
R. Towle (SGI)
H. Yang (Udel)
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
4
Organização do Mini-Curso
Motivação e Origens do Pro64
Parte I: Discussão da infra-estrutura do
compilador SGI Pro64
Parte II: Gerador de código do Pro64
Parte III: Usando o Pro64 para pesquisa e
desenvolvimento de compiladores
Suporte para o SGI Pro64
Sumário
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
5
Motivação e Origens
O que é o SGI Pro64?
Quem poderá se beneficiar do uso
do Pro64?
Onde posso obter o Pro64?
Desenvolvimento futuro para o
Pro64
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
6
O que é o Pro64?
Um conjunto de compiladores otimizadores
para sistems Linux/ Intel IA64
Compiladores para C, C++ e Fortran90/95
Produzido em conformidade com os padrões
ABI e API do IA-64 Linux
Aberto para todos os pesquisadores e
projetistas da comunidade
Compatível com o ambiente NUE (Native User
Environment)Workshop
da HP
em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
7
Quem Poderá se Beneficiar
do Uso do Pro64?
Pesquisadores : Teste de novas
análises para compiladores e novos
algorítimos de otimização.
Projetistas: Geração de código
para outras arquiteturas ou outros
sistemas.
Educadores/Estudantes : Uma
plataforma para ensinar
Workshop em Sistemas
compiladores.
Computacionais de Alto
Desempenho, Setembro 2001
8
Onde Posso Obter os
Compiladores Pro64
Código Fonte e Documentação
http://oss.sgi.com/projects/Pro64/
Grupo de Suporte do Pro64 na
Universidade de Delaware
http://www.capsl.udel.edu/~pro64
[email protected]
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
9
Tópicos para Pesquisa
Futura no Pro64
Formação de Hyperblock
Sistema de Pesquisa de Predicados
Melhoria do Suporte para Especulação
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
10
PARTE I:
Infra-estrutura do
Compilador Pro64
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
11
Organização
Modelo Lógico de Compilação e Diagrama
de Fluxo
Representações Intermediárias
WHIRL/CGIR
Análise Inter-Procedural (IPA)
Otimizador de Loops Aninhados (LNO) e
Paralelização
Otimizador Global (WOPT)
Realimentação
Projeto para debugabilidade e
em Sistemas
testabilidadeWorkshop
Computacionais de Alto
Desempenho, Setembro 2001
12
Modelo Lógico de
Compilação
driver
(sgicc/sgif90/sgiCC)
back end
(be)
front end + IPA
(gfec/gfecc/mfef90)
Src
(.c/.C/.f)
WHIRL
(.B/.I)
linker
(ld)
obj
(.o)
Data Path
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
a.out/.so
Fork and Exec
13
Componentes do Pro64
Parte Frontal
Análise Interprocedural e Otimização
Otimização de Loops Aninhados e Paralelização
Otimização Global
Geração de Código
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
14
Fluxo de Dados e Relação
Entre Módulos
Lower to
High W.
-IPA
.B
Local
IPA
Main
IPA
-O3
LNO
Inliner
gfec
.I
gfecc
lower
I/O
(only for f90)
f90
Siga Qualquer Direção
Very high WHIRL
High WHIRL
Mid WHIRL
Low WHIRL
-O0
-phase:
w=off
-O2/O3
WHIRL
C
.w2c.c
.w2c.h
WHIRL
fortran
.w2f.f
Lower
all
Lower
Mid W
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
CG
Main
opt
15
Parte Frontal
Parte frontal para C é baseada em
gcc
Parte frontal para C++ é baseada em
g++
Parte frontal para Fortran90/95 do
MIPSpro
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
16
Representação
Intermediária (IR)
IR é chamada WHIRL
Interface comum entre componentes
Múltiplas linguages e múltiplos
processadores
Mesma IR, 5 níveis de representação
Continuamente reduz o nível a medida que
a compilação progride
Estratégia de otimização de acordo com o
Workshop em Sistemas
nível de representação
Computacionais de Alto
Desempenho, Setembro 2001
17
Fase Principal da Análise
Inter-Procedural (IPA)
Análise
análise de alias
análise vetorial
layout de código
Otimização (completamente integrada)
inlining
clonagem
eliminação de código morto e
eliminação de variáveis
propagação de constantes
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
18
Propriedades do Projeto da
Análise Inter-Procedural
Transparente ao Usuário
Fornece info (p.e. análise de
alias, propriedades de
procedures) para:
otimizador de ninhos de loops
otimizador principal
gerador de código
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
19
Otimizador de Loops
Aninhados/ Paralelizador
Todas as linguagens (incluindo
OpenMP)
Análise do nível de dependência
de Loops
Transformações do nível de loop
em Uniprocessadores
Paralelização Automática
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
20
Transformações ao Nível
de Loop
Baseado num modelo unificado de custo
Heurísticas integradas com software
pipelining
Fissão de Loops (Loop Fission)
Fusão de Loops (Loop Fusion)
Expansão e Recombinação de Loops
(Loop Unroll and jam)
Reversão de ordem de loops (Loop interchange)
Remoção de Iterações (Loop Peeling)
Re-organização de Loops (Loop Tiling)
Pré-Busca de Vetores (Vector data prefetching)
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
21
Paralelização
Automática
Privatização de Vetores
Paralelização Doacross
Análise de seções de vetores
Baseada em Diretivas
OpenMP
Integrada com métodos automáticos
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
22
Fase de Otimização Global
A única representação utilizada é Static Single
Assignment (SSA)
SSA é a tecnologia unificadora
Implementa todas as optimizações globais
tradicionais
Todas as otimizações preservam o formato SSA
Pode re-aplicar cada otimização sempre que for
necessário
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
23
Extensões do Pro64 para
SSA
Representação de aliases e operações
indiretas à memória
Integração de eliminação parcial de
redundância (SSA PRE)
Suporte a movimento especulativo de
código
Promoção de registradores através da
inserção de Workshop
loads
e stores
em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
24
Realimentação
Usada em todo o compilador
Instrumentação pode ser inserida em cada
estágio
Dados explícitos para instrumentação são
incorporados onde inseridos
Dados de instrumentação são mantidos e
a sua consistência é verificada em todas
as transformações realizadas no
programa.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
25
Projeto para Depuração (DFD)
e and Testabilidade (DFT)
DFD e DFT integrados desde o início
É possível incluir verificações adicionais de
validade.
Seleção de Opções simplificada permite:
Inserir components que são reconhecidamente
bons
Habilitar/desabilitar componentes inteiros ou
otimizações específicas
Invocar heurísticas alternativas
em Sistemas
Ativar traces Workshop
the
uma
Computacionaisúnica
de Alto fase
Desempenho, Setembro 2001
26