Algortimos para Escalonamento de Instruç˜oes e - LSCAD

Algortimos para
Escalonamento de
Instruções e Alocação de
Registradores na
Infraestrutura LLVM
Lucas da Costa Silva
Qualificação
Orientação: Prof. Dr. Ricardo Ribeiro dos Santos
Área de Concentração: Ciência da Computação
Qualificação apresentada como um dos requisitos para a obtenção do tı́tulo de mestre
em Ciência da Computação.
facom ufms
Faculdade de Computação
Universidade Federal de Mato Grosso do Sul
24 de maio de 2011
Conteúdo
1 Introdução
1
2 Fundamentação Teórica
3
2.1
Problema de Alocação de Registradores . . . . . . . . . . . . . . . . . . . .
3
2.2
Integração de Escalonamento e Alocação de Registradores . . . . . . . . .
7
3 Alocação de Registradores para Arquitetura 2D-VLIW
13
3.1
Arquitetura 2D-VLIW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2
Algoritmo de Escalonamento e Alocação de Registradores Baseado em Isomorfismo de Subgrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 Infraestrutura de compilação LLVM
22
4.1
Compilador LLVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2
Escalonamento de Instruções . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3
Alocação de Registradores . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.4
Especificação de um Modelo de Arquitetura . . . . . . . . . . . . . . . . . 27
5 Proposta de Trabalho
30
Referências Bibliográficas
32
i
Capı́tulo 1
Introdução
O escalonamento de instruções e a alocação de registradores são atividades que impactam diretamente no desempenho final de uma aplicação, uma vez que determinam
precisamente como o hardware será utilizado. Tais atividades devem ser executadas levando em consideração os recursos fı́sicos existentes no processador alvo.
Desde a década de 70, a comunidade da área de compiladores tem dedicado esforço
considerável em busca de soluções para os problemas de escalonamento e alocação de
recursos em processadores. Muito desse esforço deve-se ao fato que tais problemas pertencem à classe NP-completo [1]. Com isso, surge a necessidade de pesquisas em busca
de técnicas e algoritmos mais avançados. Aliado a isso, o surgimento de processadores
com múltiplos núcleos (Multicores) aumenta a complexidade dessas atividades, pois há
de se considerar não apenas os múltiplos recursos, mas também a maneira como estão
interconectados e suas restrições de utilização.
A arquitetura 2D-VLIW [16] apresenta uma topologia que explora o paralelismo em
nı́vel de instrução através de uma via de dados baseada em um pipeline e um modelo
de execução bidimensional. Visando a geração de código para a arquitetura 2D-VLIW,
tem-se adotado uma solução para escalonamento e alocação de registradores baseada na
técnica de isomorfismo de subgrafos [17]. De maneira geral, o algoritmo de escalonamento
de instruções 2D-VLIW recebe as operações na forma de um Grafo Acı́clico Dirigido
(DAG – Directed Acyclic Graph) e invoca um procedimento de matching que procura um
subgrafo que seja isomorfo ao DAG de entrada.
O principal objetivo deste projeto de mestrado é implementar a integração desse algoritmo de escalonamento e alocação para a arquitetura 2D-VLIW junto ao compilador
LLVM [8]. O compilador LLVM é uma infraestrutura de compilação em que uma das
suas maiores vantagens é a possibilidade de customização, que permite uma alteração em
seus módulos e a integração com novos algoritmos. Além da integração, serão executados
experimentos visando a validação e a verificação de desempenho desse novo algoritmo
junto ao compilador LLVM.
Este texto de qualificação está organizado conforme segue. O Capı́tulo 2 apresenta a
fundamentação teórica dos conceitos considerados ao longo do texto, relatando as pesqui-
1
sas relacionadas e apresentando seus resultados principais. No Capı́tulo 3 é apresentada
e descrita a arquitetura 2D-VLIW em uma visão de alto nı́vel para um detalhamento dos
algoritmos de escalonamento de instruções e alocação de registradores baseados em isomorfismo de subgrafos. No Capı́tulo 4, detalha-se a infraestrutura de compilação LLVM,
além de apresentar aspectos relevantes para integração com os algoritmos apresentados
no Capı́tulo 3. A proposta de trabalho é apresentada no Capı́tulo 5.
2
Capı́tulo 2
Fundamentação Teórica
Este capı́tulo apresenta as definições básicas para a resolução do problema de alocação
de registradores. Além disso, apresenta também outros trabalhos na literatura da área
que propõem técnicas para resolução do escalonamento de instruções e alocação de registradores de maneira integrada.
O escalonamento de instruções consiste em atribuir operações a recursos fı́sicos (elementos de processamento, unidades funcionais), aptos a executá-los de acordo com uma
ordem especı́fica.
A alocação de registradores é uma tarefa importante na otimização de geração de
código que afeta diretamente o desempenho do programa gerado. Há um vasto número
de trabalhos para o problema da fase de alocação de registradores. O objetivo desta fase
é mapear os registradores virtuais (utilizados pelas instruções) nos registradores fı́sicos da
arquitetura alvo. Caso não hajam registradores disponı́veis suficientes, ocorre o evento
spill — então instruções são adicionadas para gravar e ler da memória. Heurı́sticas são
estudadas para resolver o problema da alocação de registradores e minimizar o spill.
Uma técnica também utilizada é o coalescing que é a ação de unir duas variáveis, não
interferentes, que são relacionadas por uma cópia de instrução para o mesmo registrador.
2.1
Problema de Alocação de Registradores
Em virtude da complexidade inerente à atividade de alocação de registradores, apresenta-se a seguir definições básicas que serão usadas pelas técnicas e algoritmos descritos
na sequência. A Figura 2.2 apresenta um exemplo das definições apresentadas.
Definição 1 Alocação de Registradores é a otimização que faz o mapeamento dos registradores virtuais em registradores fı́sicos da arquitetura alvo.
Definição 2 Live range de uma variável é definida como o perı́odo que ela permanece
viva, ou seja, desde o momento que ela é definida até o momento que é redefinida ou até
seu último uso [1].
3
Definição 3 Bloco Básico é uma sequência de instruções, tal que a execução flui, sem
desvios da primeira instrução do Bloco Básico até a última instrução do Bloco Básico [2].
Definição 4 Grafo de interferência é um grafo G = (V, E), em que os elementos (vértices)
de V representam as live ranges existentes no código analisado e os elementos (arestas)
de E representam a interseção dessas live ranges.
A alocação de registradores pode ser realizada utilizando o algoritmo de Coloração de
Vértices [1]. Essa coloração é feita a partir do grafo de interferência. O algoritmo procura
colorir o grafo G com um número de cores K (representa o número de registradores fı́sicos)
de maneira que nenhum par de vértices conectados por uma aresta tenha a mesma cor.
Se uma K -coloração não for encontrada então ocorre o spill. Spill gera novas instruções
e um novo grafo de interferência. O pressuposto para a K -coloração de um grafo G, é
que, suponha que G tem menos do que K vizinhos, remova o vértice i e seus vizinhos
de G obtendo um subgrafo G’. Uma K -coloração de G’ pode ser estendida para uma
K -coloração de G atribuindo ao vértice i uma cor que não foi atribuı́da a nenhum de seus
vizinhos [1].
O algoritmo que realiza uma K -coloração tem as seguintes fases, representadas na
Figura 2.1:
• renumber: descobre as live ranges (variáveis com interferência)
• build: constrói o grafo de interferência
• coalescing: une live ranges não interferentes
• spill costs: calcula o custo do spill
• simplify: método de coloração
• spill code: insere novas instruções por causa do spill (load e store)
• select: mapeia os registradores virtuais nos registradores fı́sicos
build
coalescing
spill costs
simplify
renumber
select
spill code
Figura 2.1: Fases do algoritmo de Coloração de Vértices
Deve-se destacar que a fase coalescing pode aumentar o spill. Destaca-se também a
possibilidade de utilizar uma nova fase denominada freeze: se não puder remover vértices
por simplify nem por coalescing, então o passo freeze deve marcar um vértice para não
ser considerado pelo coalescing [2].
Definição 5 Dada uma operação do tipo a := b ( move) em que as live ranges de a e b
são não-conflitantes, então, os vértices que representam a e b no grafo de interferência
4
podem ser unidos e a operação pode ser eliminada. Essa união de vértices é denominada
coalescing.
Definição 6 Spill code é a inserção de instruções load e store no programa devido a
falta de registradores. A necessidade de spill code é detectada na fase simplify, pois não
há remoção de vértices do grafo de interferência [2].
A Figura 2.2 apresenta um exemplo de utilização do algoritmo de alocação de registradores através da coloração de vértices utilizando 3 registradores (K = 3). Dado o trecho
de código do Algoritmo 1, tem-se a organização em blocos básicos na Figura 2.2a, as live
ranges das variáveis a, b, c e d na Figura 2.2b (fase renumber ) e o grafo de interferência
na Figura 2.2c (fase build ). As fases coalescing e simplify não podem ser executadas,
então uma variável é selecionada para spill, fase spill cost. A variável d foi escolhida para
ser spilled. Na Figura 2.2d, continuando a alocação, só restam três variáveis, cada uma
pode ser colorida usando três cores. Seguindo a alocação, a variável d realmente não pode
voltar ao grafo e ser colorida, então na fase spill code o código é transformado (trecho de
código do Algoritmo 2), de forma que todo o processo de alocação precisa ser realizado
novamente (renumber ). O novo grafo de interferência é representado na Figura 2.2e, que
agora contém d1 e d2, ao invés de d. Na fase simplify primeiro remove a variável d1, como
na Figura 2.2f, e depois d2, b, a e c empilhando-as. Na Figura 2.2g, fase select desempilha as variáveis a, b, c e d2 atribuindo cores, ou seja, mapeando para os registradores
fı́sicos (no exemplo r1, r2 e r3) de maneira que nenhum par de vértices conectados por
uma aresta tenha o mesmo registrador. Por último, desempilha a variável d1, atribuindo
o registrador r1 como na Figura 2.2h. O código depois da alocação é representado no
Algoritmo 3.
Algoritmo 1 Algoritmo para exemplo de alocação de registradores
live in (a,d)
b=5
loop: c=b+a
b=b-1
if b ≤ 0 goto loop
live out (c,d)
Algoritmo 2 Algoritmo para exemplo de alocação de registradores com spill code
live in (a,d1)
M[Dloc] = d1
b=5
loop: c=b+a
b=b-1
if b ≤ 0 goto loop
d2=M[Dloc]
live out (c,d2)
5
live in(a,d)
b=5
a
c=a+b
b=b-1
b
c
d
live out (c,d)
(a)
Blocos
básicos
(b) Live range
c
b
d
b
c
a
a
(c) Grafo de Interferência
(d)
Spill
variável d
na
c
c
d2
d1
b
d2
b
a
a
(e) Constrói o Grafo de Interferência depois do Spill code
(f) Simplify da variável d1
c (r3)
c (r3)
d2 (r1)
d1 (r1)
b (r1)
d2 (r1)
b (r1)
a (r2)
a (r2)
(g) Select nas variáveis a, b,
c e d2
(h) Select na variável d1
Figura 2.2: Exemplo de Alocação de Registradores
6
Algoritmo 3 Algoritmo para exemplo de alocação de registradores com registradores
fı́sicos
live in (r2,r1)
M[Dloc] = r1
r1=5
loop: r3=r1+r2
r1=r1-1
if r1 ≤ 0 goto loop
r1=M[Dloc]
live out (r3,r1)
2.2
Integração de Escalonamento e Alocação de Registradores
A literatura da área de Compiladores dispõe de várias propostas de algoritmos para
escalonamento de instrução e alocação de registradores de forma separada ou conjunta.
Algumas dessas propostas são apresentadas a seguir.
O escalonamento pode ser aplicado a uma linguagem intermediária tanto antes da
alocação de registradores (prepass) quanto depois (postpass). A vantagem do prepass é a
exploração do paralelismo. Implica no aumento da live range das variáveis possibilitando
o aumento de spill code. Postpass não aumenta o spill code, pois a alocação já aconteceu,
entretanto faz o escalonamento mais restrito.
Em [6] apresenta-se as diferenças de cooperação entre escalonamento local e global
com alocação local e global. Local é o rearranjo das instruções dentro de um bloco básico
isolado do resto do programa. O global considera o movimento de instruções entre os
blocos. Dois métodos (Integrated Prepass Scheduling — integrado no prepass — e DAGDriven Register Allocation — integrado no postpass) foram propostos como solução para
escalonamento e alocação de uma forma cooperativa.
No método Integrated Prepass Scheduling foram combinadas duas técnicas de escalonamento: uma para reduzir o atraso do paralelismo (CSP) — Code Scheduling for Pipelined
processors que é o tempo de execução usado para computar o custo de cada vértice no
DAG. O custo acumulado identifica qual vértice está no caminho crı́tico durante o escalonamento. Esses vértices no caminho crı́tico têm uma maior prioridade — e outra para
minimizar o uso de registradores (CSR) — Code Scheduling to minimize Registers usage.
A ideia básica é manter um número de registradores disponı́veis durante o escalonamento.
Quando há registradores suficientes, o escalonador usa CSP para reduzir o atraso do paralelismo. Quando o número de registradores disponı́veis alcança um limite inferior, o
escalonador troca para o CSR para controlar o uso de registradores. As simulações foram
realizadas variando a quantidade de registradores de 4 a 30 e em uma máquina com alto
paralelismo (considera 11 ciclos de clock — CC — para load, 3 CC para adição de inteiros,
6 CC para para multiplicação de inteiros) e médio paralelismo (similar a máquina com alto
paralelismo exceto pelo clock rate menor — considera 6 CC para load, 2 CC para adição
e 3 CC para multiplicação). Como medida de comparação é utilizado o número de ciclos
7
para executar o programa. Com 4 registradores há maior diferença em ambos os testes
caindo a diferença exponencialmente quando aumenta a quantidade de registradores. A
quantidade de número de ciclos é a mesma com 30 registradores.
Na técnica DAG-Driven é utilizado um grafo de dependência. Dois termos são introduzidos: largura e altura. A largura é definida pelo máximo de vértices mutualmente
independentes que precisam de um registrador de destino. A altura do DAG é o comprimento do seu caminho mais longo. Se o número de registradores é maior que a largura
do DAG, a geometria permanece inalterada durante a alocação de registradores. Caso
contrário, a alocação irá reduzir a largura do DAG para um número menor ou igual ao
número de registradores. Enquanto a largura é reduzida, a altura é aumentada. Quanto
maior a altura, maior é o caminho crı́tico. Quanto maior o caminho crı́tico, menos eficiente é o código do escalonamento. As estratégias para controlar o crescimento da altura
são: exploração das dependências Write-After-Read (WAR) e o balanceamento de crescimento do DAG. O Benchmark utilizado é o Livermore loops (utilizou-se os doze primeiros
programas). A medida utilizada é o número de ciclos do clock necessários para executar
o programa. A quantidade de registradores variou de 4 a 30. Prepass tem um número
menor de ciclos de clock comparado com o postpass, mas gera um programa com mais
instruções.
Ambos algoritmos se mostram efetivos em resolver o problema de interdependência
entre o escalonamento e a alocação de registradores. Em um modelo de alto paralelismo
o Integrated Scheduling é melhor, já o DAG-driven allocator é melhor em um modelo de
médio paralelismo. O Integrated Scheduling executa o escalonamento com um número
limitado de registradores e oscila entre um escalonamento baseado numa heurı́stica. Se
há registradores suficientes então dá preferência para instruções que aumentam o paralelismo, senão ele prefere instruções que diminuem o número de variáveis utilizadas
no mesmo instante. No DAG-driven allocator a alocação local é executada e usa a informação de dependências de dados do DAG enquanto o escalonamento é restringido pelas
dependências adicionadas pela alocação.
Em [14] é apresentada uma abordagem baseada na construção de um grafo de interferência paralelo (parallelizable interference graph).
Definição 7 Seja Gs = (Vs , Es ) o grafo de escalonamento. Cada vértice v ∈ Vs corresponde a uma instrução do código intermediário. Há uma aresta direcionada (u, v) ∈ Es ,
de u para v se u deve ser executado antes de v.
Definição 8 Seja Gr = (Vr , Er ) o grafo de interferência. Cada vértice v ∈ Vr representa
um live range de um registrador virtual. Há um aresta não direcionada (u, v) ∈ Er se e
somente se live ranges u e v se interferem.
Em seguida é gerado um grafo contendo todas as falsas dependências (Gf ). As arestas
do grafo serão usadas na geração do grafo de interferência paralelo.
Definição 9 Seja Gf = (Vf , Ef ). Vf = Vs . Definido o conjunto Et contendo exatamente
restrições da máquina no escalonamento. O par (u, v) ∈ Ef é dado por u, v ∈ Vf , u 6= v e
(u, v) ∈
/ Et .
8
Com o grafo de falsas dependências é definido o grafo de interferência paralelo. Basicamente esse inclui ambas arestas do grafo de falsa dependência e aquelas do grafo de
interferência.
Definição 10 Seja G = (V, E) o grafo de interferência paralelo. V = Vr . E = Er ∪
{{u, v} : {u, v} ∈ Ef e u, v ∈ V }.
O escalonamento varre o grafo pelo incremento do número EP (número que representa
o possı́vel tempo para escalonar o vértice) do vértice. Quando as operações com o mesmo
número EP não podem ser escalonadas juntas então elas são postergadas e o número
EP é atualizado. O procedimento de coloração é realizado primeiro gerando o grafo de
interferência paralelo depois segue com a coloração exemplificada a seguir (considere r o
número de registradores fı́sicos da máquina):
1. Constrói o grafo de interferência paralelo Gs .
2. Procedimento de coloração:
(a) Simplify: remove v e atualiza G se há um vértice v ∈ V com grau menor
0
do que r. Usa considerações do escalonamento para remover de G e G uma
aresta de falsa dependência não em Er (exemplo: uma aresta {v, u} para que
o escalonamento de u com v pelo menos contribuam).
(b) Spill Cost: se V não estiver vazio escolhe um vértice v ∈ V com menor custo
e coloca v na lista de spill.
(c) Select: colore o grafo se não há spill.
(d) Spill : para cada item na lista de spill refazer o procedimento de coloração.
A solução é avaliada utilizando os programas do SPEC92 benchmark. Os resultados
da comparação são dados pelo tempo de execução. A melhora mais significativa é do
programa 023.eqntott de 0.33% e a menos significativa é do programa 050.ear de 0.05%.
Em [11] é apresentada a técnica Combined Register allocation and Instruction Scheduling Problem (CRISP) cujo objetivo é de minimizar o spill sem perder o paralelismo em
nı́vel de instrução, combinando assim o escalonamento e a alocação de registradores dentro de um bloco básico como um único problema de otimização. A solução do problema
é encontrar um custo C mı́nimo onde um escalonamento factı́vel T é somado ao dobro do
número de elementos do conjunto de spills SV R, dado por: C = T + 2|SV R|. Estabelecese o algoritmo (α, β)-Combined Heuristic, em que os parâmetros α, β ∈ [0, 1] =⇒ α+β =
1 proveem um peso relativo para controlar a pressão nos registradores γr e considerar o
paralelismo de instruções γs , dado pela função de classificação γ = αγs + βγr . Com essa
classificação é realizada a ordenação das instruções em uma lista. Então executa o algoritmo greedy list scheduling. Observa-se um desempenho de melhora de 16%-21% em
relação a execução de escalonamento seguido de alocação. Já para uma alocação seguida
de um escalonamento o desempenho é de 4%-21%.
Em [4] é apresentado o algoritmo Unified Resource Allocation using Reuse Dags and
Splitting baseado no paradigma medir-e-reduzir (measure-and-reduce) tanto de registradores quanto de unidades funcionais. A técnica constrói DAG de reuso (reuse DAGs) de
9
recursos. O DAG é composto por diversas cadeias de reuso. Cada cadeira representa um
conjunto de instruções que podem compartilhar o mesmo recurso. Usando reuse DAGs,
essa abordagem identifica grupos de instruções nas quais o paralelismo requer mais recursos do que há disponı́vel. Então, reduções são executadas para a demanda excessiva.
Se um número de cadeias excede o limite de registradores, é adicionado sequências de
arestas ou código spill (spill code) no DAG de reuso para reduzir a pressão, que leva a
redução do DAG de reuso. O objetivo é modificar o DAG identificando regiões de código
do DAG que precisam de reduções para os recursos requeridos para os nı́veis suportados
pela arquitetura. A técnica é descrita, basicamente em três passos:
1. Representação do programa e requisitos para cada recurso.
2. Algoritmos para mensurar os requisitos dos recursos.
3. Transformações para reduzir os recursos requeridos para os nı́veis suportados pela
arquitetura.
Uma extensão dessa técnica é apresentada em [3], baseando se na técnica IPS apresentada em [6]. A técnica apresentada é utilizado o DAG de reuso e Live range splitting para
dividir a live range, reduzindo assim a demanda de registradores. O algoritmo mantém
uma lista de todos os registradores sendo escalonados, quando é detectado uma alta
pressão nos registradores e não há instruções prontas para escalonar então é executado a
divisão da live range, que reduz o número de live ranges ativas. O live range splitting é
descrito a seguir:
1. Insere instrução load na lista de escalonamento pronta.
2. Insere instrução store na lista de escalonamento não pronta.
3. Move as dependências de usos, não escalonadas, da definição original para o load
inserido.
Os experimentos, utilizando Testsuite Speedup, foram mensurados pelo speedup com
registradores variando de 8, 16 a 32 registradores. Comparando com IPS de [6] essa
abordagem teve melhor desempenho, conforme a tabela 2.1.
Tabela 2.1: Comparação de speedup IPS e URSA
Registradores IPS URSA
8
1,25 4,25
16
1,75 3,25
32
2
2,25
Definição 11 Um PDG ( Program Dependence Graph) [13] é um grafo direcionado que
representa as dependências de controle e as dependências de dados entre as sentenças
10
do programa. Os vértices são sentenças e predicados de expressões que ocorrem em um
programa. Uma aresta representa uma dependência de controle ou de dados.
A Figura 2.3 apresenta um PDG de um código da mesma figura. Com arestas direcionadas para representar as dependências de dados (Data Dependence) — em tracejado;
e para representar dependências de controle (Control Dependence). Os vértices estão representando tanto as sentenças e expressões de predicados. Há uma dependência de dado
na instrução 1, devido a definição de i, na instrução 3, devido uso de i [12], portanto isso
é representado por uma aresta direcionada tracejada do vértice 1 para o vértice 3. As
sentenças while e if são representados, respectivamente, pelos vértices de predicado P 1 e
P 2. O vértice de região R1 representa as condições de controle na entrada do programa.
O vértice de região R2 representa as condições para entrar no laço ou para voltar em uma
outra iteração. R3 representa as condições sobre a qual o corpo do laço é executado. R4
representa a região do if quando verdadeiro, e caso contrário, else, que é representado
pela região R5.
Figura 2.3: Exemplo de PDG (Program Dependence Graph) [12]
Em [12] o escalonamento cooperativo global executa escalonamento em regiões é chamada de Register Allocation Sensitive Region (RASER). Esta técnica sobre o PDG tenta
criar regiões de código com uma quantidade igual de paralelismo. O objetivo é combinar
o paralelismo estimado em cada região com a quantidade de paralelismo explorável para
a arquitetura alvo.
A técnica é baseada no seguinte fluxo de execução:
1. Obtenção de estimativa do paralelismo disponı́vel em cada região do PDG.
2. Execução do Integrated Prepass Scheduling (IPS) em cada região, baseado em [6].
11
3. Construção de uma lista de regiões que o número de variáveis vivas excede o número
de registradores fı́sicos.
4. Redução dos spills por meio da redução da quantidade de variáveis vivas nestas
regiões.
5. Aplicação de transformações para aumentar o paralelismo nas regiões.
6. Eliminação de regiões sem descendentes.
O desempenho do RASER é comparado com o desempenho de um escalonamento de
regiões padrão (blocos básicos) seguido pela alocação de registradores. Os experimentos
são executados em uma máquina hipotética com médio paralelismo e com unidades funcionais em paralelo. Um simulador é usado para determinar o número de ciclos necessários
para executar o código intermediário e o número de loads e stores executados devido ao
spilling. Utiliza-se programas do benchmark Livermore loops, variando o número de registradores de 3 a 16. No estudo é indicado que para um conjunto pequeno de registradores,
em geral, RASER gera código que executa mais rápido, em 17 de 24 experimentos com 3
registradores e em 19 de 24 com 4 registradores. No pior caso a redução do número de ciclos executados varia de 0.2% até 49.2% em comparação com o postpass. Esta combinação
é particularmente benéfica em uma máquina com alto paralelismo. A medida utilizada é
o speedup.
12
Capı́tulo 3
Alocação de Registradores para
Arquitetura 2D-VLIW
Este capı́tulo apresenta a arquitetura 2D-VLIW (Two-Dimensional Very Long Instruction Words), uma técnica que explora o paralelismo em nı́vel de instrução. Também
apresenta uma técnica que considera a geometria dos grafos de entrada, assim como a
topologia dos elementos de processamento para ser utilizado no algoritmo de Escalonamento e Alocação de Registradores Baseado em Isomorfismo de Subgrafos. O resultado
do escalonamento é uma instrução 2D-VLIW.
3.1
Arquitetura 2D-VLIW
Two-Dimensional Very Long Instruction Words (2D-VLIW) é uma arquitetura de
alto desempenho que explora o paralelismo em nı́vel de instrução através de um arranjo
bidimensional de recursos de hardware e um pipeline. Na arquitetura 2D-VLIW, o compilador é o único responsável por alocar operações para os recursos disponı́veis. Essa
nova organização dos elementos de hardware vai ao encontro dos grafos de dependências
de operações, procurando maximizar o desempenho na execução do programa e melhorar a escalabilidade da arquitetura. 2D-VLIW segue a terminologia EPIC de operações
e instruções: uma operação corresponde a uma instrução RISC-like e uma instrução a
um grupo de operações. A execução dessas operações é auxiliada por um conjunto de
registradores locais, denominados registradores temporários. Os recursos de hardware, na
arquitetura 2D-VLIW, são comumente organizados como uma matriz de unidades funcionais que possui uma rede de interconexão bastante simples onde uma unidade funcional
na linha i, onde 0 ≤ i < Quantidade de linhas, é interconectada a outras duas unidades funcionais na linha (i + 1) mod Quantidade de linhas. Essa interconexão é estática
independente do programa sendo executado. Por outro lado, é flexı́vel o bastante para
mapear operações de uma gama de aplicações diferentes [17].
Na arquitetura 2D-VLIW, tem-se adotado uma solução para escalonamento de ins13
truções e alocação de registradores baseada na técnica de isomorfismo de subgrafos. De
maneira geral, o algoritmo de escalonamento de instruções 2D-VLIW recebe as operações
na forma de um DAG e invoca um procedimento de matching (combinação) que procura
um subgrafo que seja isomorfo ao DAG de entrada.
A Figura 3.1 apresenta uma visão geral da arquitetura 2D-VLIW. Nessa figura é
possı́vel observar a via de dados usada por uma instrução e a organização das UFs (unidades funcionais) através da matriz 4 × 4. Por simplicidade, a hierarquia de memória e os
registradores temporários não foram exibidos. Os resultados de uma UF podem ser escritos no Temp Register File (TRF) ou no Global Register File (GRF). TRF é um pequeno
banco contendo dois registradores dedicados para cada UF. O GRF tem 32 registradores.
O resultado de uma UF é sempre escrito em um registrador interno chamado FU Register
(FUR).
Figura 3.1: Visão da 2D-VLIW
As instruções 2D-VLIW são formadas por operações simples, que executam sobre
a matriz de unidades funcionais. O número de operações em uma instrução é equivalente à quantidade de unidades funcionais na matriz. Assim, para a matriz 4 × 4 da
Figura 3.1, uma instrução 2D-VLIW possui 16 operações. Caso não seja possı́vel encontrar 16 operações no programa para preencher toda a matriz, operações especiais do tipo
nop (operações nulas que não alteram os estados dos registradores) são inseridas.
A execução de instruções de um programa sobre a arquitetura 2D-VLIW passa por
registradores de pipeline ao longo da via de dados. Em cada ciclo de relógio, uma instrução
2D-VLIW é buscada da memória e colocada no registrador Busca/Decod. Quando alcança
os estágios de execução as operações que formam a instrução são executadas, em paralelo,
de acordo com o número de UFs na matriz.
14
Esta arquitetura depende da geração de código, mais precisamente, do escalonamento
de instruções e alocação de registradores. No caso de 2D-VLIW, o problema de escalonamento de instruções é modelado utilizando duas heurı́sticas distintas: um algoritmo
baseado em isomorfismo de subgrafos e um algoritmo guloso baseado em list scheduling. O
primeiro algoritmo representa tanto as operações de um programa quanto os recursos da
arquitetura através de dois grafos distintos: o grafo do programa e o grafo da arquitetura.
O objetivo do algoritmo de isomorfismo é obter um subgrafo do grafo da arquitetura que
seja isomorfo ao grafo do programa. Esse subgrafo indica exatamente quais recursos do
processador devem ser utilizados por cada operação. O algoritmo guloso baseado em list
scheduling estende o algoritmo tradicional list scheduling adaptando-o para representar a
topologia da arquitetura e obedecer às restrições de interconexão.
O problema da alocação de registradores na arquitetura 2D-VLIW é abordado através
de uma extensão do algoritmo original de escalonamento de instrução baseado em isomorfismo de subgrafos. Nesse novo algoritmo, o grafo da arquitetura é dotado com vértices
representando os registradores temporários e globais, possibilitando a alocação de registradores simultânea com a fase de escalonamento.
3.2
Algoritmo de Escalonamento e Alocação de Registradores Baseado em Isomorfismo de Subgrafos
Definição 12 No problema de isomorfismo de grafos, dois grafos G1 = (V1 , E1 ) e G2 =
(V2 , E2 ) são ditos isomorfos, denotado por G1 ∼
= G2 se existe uma bijeção ϕ : V1 → V2
tal que, para todo par de vértices vi , vj ∈ V1 vale que (vi , vj ) ∈ E1 se e somente se
(ϕ(vi ), ϕ(vj )) ∈ E2 . [17].
Definição 13 No problema de isomorfismo de subgrafos, o grafo G1 = (V1 , E1 ) é isomorfo
0
0
ao grafo G2 = (V2 , E2 ) se existe um subgrafo de G2 , por exemplo G2 , tal que G1 ∼
= G2
[17].
A Figura 3.2 exemplifica o isomorfismo de subgrafos. As Figuras 3.2a e 3.2b mostram o
grafo de entrada e o grafo base, respectivamente. O resultado do mapeamento das arestas
e vértices do grafo G1 para o grafo G2 é o grafo resultante na Figura 3.2c. Observe que
ϕ(a) = 6, ϕ(b) = 5, ϕ(c) = 4, ϕ(d) = 3.
A Figura 3.3 mostra um exemplo de escalonamento de instruções baseado em isomorfismo de subgrafos. Essa técnica considera a geometria dos grafos de entrada assim
como a topologia da matriz de unidades funcionais. O resultado do escalonamento é uma
instrução 2D-VLIW, em que cada posição da instrução possui uma operação que será
executada à medida que a instrução percorre a matriz de UFs.
O Algoritmo 5 descreve os passos principais de escalonamento de instruções 2D-VLIW
15
b
a
5
5 (b)
6
6 (a)
ab
ab
a
c
1
d
4
1
2
(a) Grafo de entrada G1
3
2
(b) Grafo base G2
4 (c)
1
3 (d)
2
0
(c) Grafo resultante G2
Figura 3.2: Exemplo do problema de isomorfismo de subgrafos.
Figura 3.3: Escalonamento de instruções baseado em isomorfismo de subgrafos
baseado em isomorfismo de subgrafos. Nesse algoritmo, algumas heurı́sticas são adaptadas visando facilitar a determinação do isomorfismo [17]. Considerando que o algoritmo
executa o isomorfismo entre dois grafos (grafo de entrada e grafo base) que representam
as dependências dos dados do programa e as caracterı́sticas da arquitetura, as seguintes
restrições devem ser obedecidas:
• i, j, k ∈ I,
• m ∈ M,
∀ 0 ≤ i, j, k < |I|
∀ 0 ≤ m < |M |
• Em uma cadeia de dependência de operações opj , opk → opi (opi depende dos resultados de opj e opk ) existente no grafo de entrada, opi pode ser escalonada em uma
U Fm se e somente se opj e opk já foram escalonadas e seus resultados estão vivos
na entrada de U Fm .
• Uma operação opi pode ser escalonada em uma U Fm se e somente se um registrador
de escrita (TRF ou GRF) alcançável por U Fm está livre.
• Se não existirem registradores temporários livres no momento do escalonamento da
operação opi , um código de spill deve ser inserido e escalonado a fim de garantir a
16
semântica correta de execução. A mesma ação deve ocorrer caso o registrador em
questão seja global.
No procedimento 5, primeiro é executado o procedimento topological order para ordenar topologicamente o DAG de entrada G1 . O procedimento subg iso sched alloc 4
0
0
encontra um subgrafo G2 , G2 ⊆ G2 , isomorfo para G1 . Caso não seja encontrado então
o escalonador escolhe uma heurı́stica com base no valor da variável tag e executa essa
heurı́stica sobre um dos parâmetros de entrada.
Algoritmo 4 Algoritmo de isomorfismo de subgrafos.
ENTRADA: Grafo de entrada G1 , grafo base G2 e tag.
SAÍDA: Subgrafo G02 .
subg iso sched alloc(DAG: G1 , GRAFO BASE: G2 , TAG: &tag )
1) sched nodes = 0;
2) nodeG1 = next(G1);
3) nodeG2 = next(G2);
4) while (sched nodes < |V1 | && sched nodes ≥ 0)
5) if ( IsFeasible(nodeG1 , nodeG2 ) )
6)
G02 = AddUsefulPair(nodeG1 , nodeG2 );
7)
sched nodes = sched nodes + 1;
8)
nodeG1 = next(G1);
9)
nodeG2 = next(G2);
10) else
11)
if ( nodeG2 .index < |V2 | )
12)
nodeG2 = next(G2);
13)
else
14)
backtrack();
15)
end if
16) end if
17) end while
18) tag = evaluate(G02 , G1 , G2 );
19) return G02 ;
O Algoritmo 4 executa a cada iteração uma verificação se o par de vértices selecionados
nodeG1 e nodeG2 são soluções factı́veis para o isomorfismo. A cada par de vértices factı́vel
encontrado (linha 5) o subgrafo G02 é incrementado (linha 6). Uma par de vértices é factı́vel
se os vértices possuem as mesmas caracterı́sticas (mesmo grau de entrada, mesmo grau de
saı́da, etc.) e contribuem para uma solução parcial do isomorfismo. Se um par de vértices
não é uma solução factı́vel, deve-se verificar se há ainda outros vértices de G2 que podem
ser pesquisados (linhas 11 e 12). Caso todos os vértices de G2 já tenham sido testados,
deve-se realizar uma ação de backtracking (linha 14) a fim de que um vértice previamente
escalonado de G1 escolha outro vértice de G2 como par. Antes do algoritmo finalizar,
a função evaluate() (linha 18) analisa o conteúdo do subgrafo G02 a fim de detectar se
o isomorfismo não pode ser concluı́do e, nesse caso, retornar o resultado para a variável
tag. Caso o isomorfismo não seja detectado, a função evaluate() analisa os grafos G1 e
17
G2 , assim como o valor atual da variável tag para indicar um novo valor de retorno para
essa variável.
Algoritmo 5 Algoritmo de escalonamento de instruções 2D-VLIW baseado em isomorfismo de subgrafos e alocação de registradores.
ENTRADA: Grafo de entrada G1 e grafo base G2 .
SAÍDA: Conjunto de instruções 2D-VLIW.
Sched(DAG: G1 , GRAFO BASE: G2 )
1) topological order(G1 );
2) G02 =subg iso sched alloc(G1 , G2 , tag);
3) while (G02 == N U LL)
4) switch(tag)
5)
case 1 : base graph resize(G2 );
6)
case 2 : DAG stretch(G1 );
7)
case 3 : DAG split(G1 );
0
8) G2 =subg iso sched alloc(G1 , G2 , tag);
9) end while
10) create 2D-VLIW instruction(G02 );
A heurı́stica base graph resize(), em 5, redimensiona o grafo base com o intuito de
oferecer mais opções de combinação para o grafo G1 . A heurı́stica DAG stretch transforma o grafo G1 em um grafo mais factı́vel que possa ser facilmente combinado com o
grafo G2 . Heurı́stica DAG split muda os vértices registradores do grafo. Todos os vértices
registradores são tratados como registradores TRF. Se não há registradores TRF suficientes para executar a ação, então ocorre o evento spill. Assim a heurı́stica divide o DAG
pela modificação dos vértices TRF para vértices GRF. Se não há vértices GRF suficientes
então o spill code é inserido no código, G1 é dividido e deve ser reconstruı́do. Depois da
combinação ser encontrada uma instrução 2D-VLIW é criada.
A heurı́stica de ordenação topológica provê uma ordenação dos vértices do grafo G1 .
A Figura 3.4 apresenta um exemplo de um DAG de entrada ordenado na Figura 3.4a
e o escalonamento resultante sem a realização de qualquer passo de backtracking na Figura 3.4b. O número do lado direito de cada vértice indica a ordem a ser seguida pelo
escalonador. Os retângulos em branco representam as UFs disponı́veis que podem ser
usadas pelo escalonador. Os retângulos hachurados indicam UFs já ocupadas. Existem
dois algoritmos de ordenação topológica implementados junto ao escalonador. Um é baseado na largura do DAG de entrada e o outro é baseado numa solução do problema de
BinPacking denominado Best Fit Decreasing.
Outra heurı́stica é o redimensionamento do grafo base que é executada quando o grafo
base G2 não possui vértices suficientes para comportar um subgrafo isomorfo para G1 .
Basicamente, a heurı́stica redimensiona o grafo base, formando assim um novo grafo base
maior e com mais possibilidades de comportar um subgrafo isomorfo para G1 . A Figura 3.5
exemplifica o desenrolamento de um grafo base, a matriz de UFs da Figura 3.5a, em um
grafo base ainda maior apresentado na Figura 3.5b.
Esse algoritmo tem sido experimentado e comparado com outras alternativas para
18
(a) Dag de entrada ordenado
(b) Estado do escalonamento
sem qualquer backtracking para o
DAG 3.4a
Figura 3.4: Exemplo de ordenação topológica
(a) Dag de entrada ordenado
(b) Estado do escalonamento sem qualquer backtracking para o DAG 3.5a
Figura 3.5: Exemplo de redimensionamento de grafo base
os mesmos problemas. Um dos experimentos consistiu na comparação entre o algoritmo
de escalonamento de instruções apresentado em [17] e o algoritmo de escalonamento de
instruções integrado com a alocação de registradores (IRA – Instruction scheduling and
Register Allocation). As métricas utilizadas foram: número de instruções 2D-VLIW,
OPI (operações por instrução) e tempo de combinação usando programas de SPEC e
MediaBench com o compilador Trimaran [5]. Para 6 de 9 programas IRA apresentou
uma melhor utilização de recursos. Outro resultado é a comparação de desempenho entre
escalonamento de instruções e IRA. IRA obteve melhor resultado em 4 de 9 programas,
segundo o autor o resultado era esperado devido ao tratamento de spill code realizado
pelo IRA.
A Figura 3.6 exibe a representação dos bancos de registradores temporários como
vértices do grafo base. Deve estar claro que qualquer registrador global pode ser lido e
19
escrito por qualquer UF desde que o limite do uso de portas de leitura e escrita sejam
obedecidos. Outro ponto importante a ser observado é que os valores lidos do banco de
registradores são enviados para as UFs através de registradores de pipeline.
Figura 3.6: Registradores globais e temporários
A vantagem dessa abordagem de alocação de registradores é a determinação de quais
registradores serão utilizados e, principalmente, garantir que o resultado de uma operação
esteja vivo na entrada das UFs das operações dependentes. O grafo de entrada é representado na Figura 3.7a e na 3.7b o mesmo grafo caracterizado com vértices representando
registradores. O resultado de escalonamento e da alocação de registradores considerando
esse grafo de entrada sobre a matriz de UFs com seus registradores temporários é apresentado na Figura 3.7c.
20
(a) Representação
original do grafo
de entrada
(b)
Representação
do
grafo de entrada
com
vértices
indicando o uso
de registradores
(c)
Resultado
do
escalonamento e da
alocação de registradores
Figura 3.7: Grafo de entrada representando as operações e registradores e o resultado
final de escalonamento com alocação de registradores
21
Capı́tulo 4
Infraestrutura de compilação LLVM
Este capı́tulo apresenta a infraestrutura de compilação Low-Level Virtual Machine
(LLVM). Destacando o back-end e as fases necessárias para este trabalho como o escalonamento de instruções, a alocação de registradores e a geração de código.
4.1
Compilador LLVM
O compilador Low-Level Virtual Machine (LLVM) é uma infraestrutura modular construı́da com uma coleção de ferramentas reutilizáveis. O LLVM foi iniciado num projeto
da Universidade de Illinois, desde então cresceu como um projeto consistente. O código
do projeto está sob a licença da “UIUC” (University of Illinois at Urbana-Champaign)
BSD-Style (Berkeley Software Distribution). O LLVM, em 2010, recebeu o prêmio da
ACM SIGPLAN (Special Interest Group on Programming Languages) em reconhecimento
do impacto que teve na comunidade de pesquisa em compiladores, que pode ser constatado pelo grande número de publicações que trazem referências a esse compilador. As
vantagens da infraestrutura do LLVM são o seu design (que faz ser simples para entender
e usar), a linguagem independente e a extensibilidade [8].
A Figura 4.1 representa em alto nı́vel a arquitetura do LLVM. Em compilador estático é
realizada a transformação de linguagens como C, C++ e Objective-C para uma linguagem
de representação intermediária (LLVM IR), realizada no front-end. Pode-se utilizar tanto
o GCC (llvm-gcc) quanto o Clang como front-end. A linguagem intermediária LLVM IR
é baseada em RISC e na forma SSA (static single assignment form). Com essa linguagem
intermediária o LLVM gera o LLVM Object, que pode ser executado pela infraestrutura
do LLVM utilizando o tradutor Just in Time (JIT). Então, o LLVM pode trabalhar com
o LLVM Object, chamado também de bitcode, realizando otimizações, gerando o código
Assembly ou gerando código nativo para arquiteturas especı́ficas de máquinas como X86,
ARM, PowerPC, MIPS, SPARC, XCore, entre outas. O código nativo é o código linked
com as bibliotecas necessárias para execução.
22
Back-end
Front-end
Assembly
Compilador estático
LLVM IR
LLVM Object
Otimizações
Código Nativo
Figura 4.1: Diagrama representando o esquema de geração de executáveis no LLVM
A forma SSA é uma representação intermediária em que cada variável tem somente
uma definição no programa. Na Figura 4.2 há um exemplo de código em C e a respectiva
versão na forma SSA [2].
Figura 4.2: SSA static single assignment form (Forma única de atribuição)
Dentre o conjunto de ferramentas do LLVM, destacam se:
• clang ou llvm-gcc: invoca o fron-end gerando um objeto LLVM IR.
• llc: invoca o back-end recebendo um objeto LLVM IR.
• opt: invoca o back-end fazendo otimizações em um objeto LLVM IR.
• llvmc: executa a compilação e tem seus argumentos baseados no compilador GCC.
O back-end do LLVM contém bibliotecas independentes para cada arquitetura. Nesta
fase há a tradução da LLVM IR para instruções reais e registradores reais. Exemplo
de código na representação em C e em LLVM IR, respectivamente, é apresentado na
Figura 4.3:
A Figura 4.4 representa uma visão abstrata dos estágios de geração de código no
back-end. A geração de código está dividida nos seguintes estágios [19]:
• Seleção de instrução: produz um código inicial para o conjunto de instruções.
A seleção de instruções então faz uso de registradores virtuais na forma SSA e
registradores fı́sicos que são necessários devido à restrição da arquitetura. Tem como
entrada as instruções LLVM IR e constrói um DAG das instruções chamado de ilegal
(contém instruções não suportadas) e a representação do conjunto de instruções da
23
Figura 4.3: Exemplo de código em C e em LLVM IR
máquina alvo. Esta fase produz como saı́da um DAG de instruções (legais) da
arquitetura alvo (SelectionDAG), utilizando um algoritmo guloso adaptado para
DAGs.
• Escalonamento: recebe o SelectionDAG de instruções legalizado, determina uma
ordem para as instruções, então emite as instruções como instruções de máquina,
utilizando uma variação do algoritmo list scheduling.
• Otimização em código de máquina baseado em SSA: é uma fase opcional
que opera sobre a forma SSA produzida pela seleção de instruções. Exemplos de
otimizações nessa fase são modulo-scheduling e peephole.
• Alocação de registradores: o código é transformado de uma infinidade de registradores virtuais numa forma SSA para registradores fı́sicos. Esta fase insere spill
code e elimina todas as referências de registradores virtuais do programa.
• Inserção de código prólogo/epı́logo: nesta fase códigos de prólogo e epı́logo
podem ser inseridos e as localizações de referências abstratas são removidas.
• Otimizações tardias: otimizações que operam no código de máquina final são
realizadas nesta fase. Exemplos de otimizações nesta fase são spill code scheduling
e peephole.
• Emissão de código: a fase final tem como saı́da o código em formato assembly ou
em código de máquina.
Uma estrutura importante do LLVM é o Pass, pois ele gerencia a execução das transformações e otimizações realizadas pelo compilador. Dependendo de como o Pass trabalha, ele deve herdar métodos das classes ModulePass, CallGraphSCCPass, FunctionPass,
LoopPass, RegionPass ou BasicBlockPass, que fornecem mais informações sobre a funcionalidade do Pass. Uma das principais caracterı́sticas do Pass é o escalonamento dos
passes que executam de uma maneira eficiente baseado nas restrições que o Pass encontra
(indicado pela classe que foi herdada). A classe que gerencia o escalonamento dos passes é
a classe PassManager. Nela, os resultados de análises são compartilhados, não permitindo
assim o cálculo de uma análise mais de uma vez.
24
LLVM
Front-end
Seleção de Instrução
Escalonamento
Fast
Otimização
ListScheduling
Back-end
Alocação de Registradores
Fast
Linear Scan
Inserção de código Prólogo/Epílogo
Otimizações tardias
PBQP
Emissão de código
Assembly
Código nativo
Figura 4.4: Fases do LLVM na geração de código
4.2
Escalonamento de Instruções
O escalonamento inicia na última fase da seleção de instrução. Esta fase recebe o
DAG das instruções alvo produzidas pela fase seleção de instruções e determina uma
ordem de execução para cada vértice do DAG. Então o DAG é convertido para uma lista
de MachineInstrs e o SelectionDAG é destruı́do. Este passo usa a técnica tradicional
prepass. Essa fase é logicamente separada da fase de seleção de instrução, mas está
conectada fortemente no código porque operam sobre o SelectionDAGs [19]. Exemplo de
trecho de código na Figura 4.5a é representado no SelectionDAG na Figura 4.5b, o grafo
é montado de baixo para cima, mas a execução se mantém como a do código, realizando
operações de ponto flutuante, primeiro a adição entre W e X, depois multiplica o seu
resultado por Y e em seguida soma o resultado com Z.
fadd:f32
fmul:f32
fadd:f32
W
(a) Trecho de código
Z
Y
X
(b) SelectionDAG
Figura 4.5: Exemplo do SelectionDAG (fadd:f32 (fmul:f32 (fadd:f32 W, X), Y), Z)
O algoritmo utilizado pelo LLVM é o list scheduling, que pode ser utilizado em duas
abordagens: top down e bottom up. O algoritmo basicamente usa uma fila de prioridade
para escalonar. A cada instante, os vértices de mesma prioridade são retirados da fila,
em ordem, e escalona se for um escalonamento legal. Uma ilegalidade pode ser devido
a conflitos estruturais (pipeline ou restrições de recursos) ou porque uma entrada para a
instrução não completou a execução.
25
Um outro algoritmo também utilizado para o escalonamento é Fast, que executa o list
scheduling com uma fila de prioridade para escalonar a estrutura de dados FastPriorityQueue, que simplesmente é uma fila de prioridades onde todos os vértices do grafo de
escalonamento têm a mesma prioridade.
4.3
Alocação de Registradores
O primeiro passo para a alocação é a determinação das live ranges das variáveis vivas.
As instruções PHI (φ), criadas pela forma SSA, devem ser tratados especialmente, porque
somente a definição é tratada, pois os usos serão tratados em um outro bloco básico. Para
cada instrução PHI do bloco básico, é simulado uma alocação até o fim do bloco básico e
o bloco sucessor transversal. Se o bloco básico sucessor tem uma instrução PHI e um dos
operandos está vindo do bloco corrente, então a variável é marcada como viva dentro do
bloco básico corrente e todos os seus blocos básicos predecessores até o bloco básico com
a definição da instrução encontrada.
O LLVM denota os registradores fı́sicos denotados por números inteiros de 1 a 1023.
Assim os registradores virtuais iniciam a partir do 1024. Para algumas arquiteturas
como X86 alguns registradores fı́sicos são marcados como aliased, por compartilhar o
mesmo endereço fı́sico (exemplo: o EAX, AX e AL, compartilham os oito primeiros bits).
Registradores fı́sicos, no LLVM, são agrupados em Register Classes. Registradores fı́sicos
são estaticamente definidos no arquivo TargetRegisterInfo.td enquanto que os virtuais
devem ser criados chamando MachineRegisterInfo::createVirtualRegister().
Uma importante transformação acontece durante a alocação de registradores chamada
SSA Deconstruction Phase. A forma SSA simplifica muitas análises que são executadas
no grafo de fluxo de controle. Entretanto, conjunto de instruções tradicionais não implementam instruções PHI. Então, o compilador deve substituir as instruções PHI com
outras instruções que preservam a mesma semântica [19].
A infraestrutura do LLVM provê diferentes alocações de registradores:
• Linear Scan: o algoritmo utiliza uma estratégia gulosa para realizar a alocação de
registradores. O algoritmo inicia transformando os blocos básicos numa sequência
linear. Então, realiza a coloração baseada nas live ranges em que duas live ranges
que se sobrepõem não podem ser alocadas para o mesmo registrador [15].
• Fast: aloca basicamente em nı́vel de bloco, tentando manter valores em registradores. Não há registradores vivos entre blocos. Portanto tudo é spilled no inı́cio
e no final de cada bloco. Esse algoritmo é usado, principalmente, em situações de
depuração de código com registradores alocados.
• PBQP — (Partitioned Boolean Quadratic Programming): trabalha na construção de
um problema PBQP que representa o problema de alocação de registradores, resolve
o problema PBQP e converte a solução para a um problema de alocação de registradores. Se alguma variável foi selecionada para spill, então o código spill é adicionado
26
e o processo é repetido. A representação do PBQP é um grafo, onde os vértices são
os registradores virtuais e as arestas são as restrições entre os registradores (como
as interferências). Cada vértice é associado a um vetor de custo (que dá o custo
de cada alocação para alocar o registrador virtual). Tipicamente pode-se estimar
o custo de spill e o custo zero para cada registrador, entretanto pode-se atribuir
valores de custo positivos ou negativos para cada registrador fı́sico priorizando-o.
Cada aresta é associada com a uma matriz de custo (que é a interferência entre os
vértices). O custo de uma especı́fica solução (alocação de registradores), é dada pela
soma dos custos de todos os vértices e arestas do grafo. O problema é resolvido por
programação dinâmica [18].
4.4
Especificação de um Modelo de Arquitetura
No projeto LLVM as descrições de dados são descritas em Tablegen. Tablegen consiste
em classes e definições. Classes são registros abstratos que são usados para construir outros
registros. Definições são registros concretos. Estes não têm qualquer valor indefinido. Os
registros têm um único nome, uma lista de valores e uma lista de superclasses. A lista
de valores contém os dados que constroem os registros. Um exemplo é representado na
Figura 4.6, que contém a definição de uma instrução add registrador - registrador de 32 bits
para a arquitetura X86. A palavra após “def ” indica o nome do registro “ADD32rr ”. O
corpo do registro contém todos os dados que o TableGen monta para o registro, indicando
que a instrução faz parte do namespace “X86”, o padrão indica como a instrução deve ser
emitida no arquivo assembly, que é uma instrução de dois endereços, etc.
Para escrever um compilador back-end para LLVM que converte a representação LLVM
IR para código de uma arquitetura alvo, deve-se seguir os passos:
1. Criar uma subclasse da classe TargetMachine que descreve as caracterı́sticas da
arquitetura alvo.
2. Descrever o conjunto de registradores do alvo. Usar TableGen para gerar código
para definição de registradores, aliases de registradores e classes de registradores de
um alvo especı́fico do arquivo de entrada RegisterInfo.td. Deve-se escrever um código
adicional para a subclasse da classe TargetRegisterInfo que representa o arquivo de
dados usado para a alocação de registradores e também descreve as interações entre
registradores.
3. Descrever o conjunto de instruções para a arquitetura alvo. Usar TableGen para
gerar código para as instruções especı́ficas descritas em TargetInstrFormats.td e
TargetInstrInfo.td. Deve-se escrever código adicional para uma subclasse da classe
TargetInstrInfo que representa as instruções de máquina suportadas pela máquina
alvo.
4. Descrever a seleção e conversão do LLVM IR para uma representação em DAG
das instruções para instruções nativas da arquitetura alvo. Usar TableGen para
27
Figura 4.6: Definição da instrução add em X86
gerar código que combina padrões e seleciona instruções baseadas em informação
adicional da arquitetura alvo de TargetInstrInfo.td. Deve-se escrever código para
XXXISelDAGToDAG.cpp, onde XXX identifica o alvo especı́fico, para executar a
combinação de padrões e seleção de instruções DAG-to-DAG . Também escrever
código em XXXISelLowering.cpp para substituir ou remover operações e tipos de
dados que não são suportados nativamente em um SelectionDAG.
5. Escrever código para um assembly printer que converte LLVM IR para um formato
GAS (GNU Assembler ) para arquitetura alvo. Deve-se adicionar assembly strings
para instruções definidas na versão de TargetInstrInfo.td da arquitetura alvo. Devese escrever também um código para a subclasse AsmPrinter que executa a conversão
28
LLVM-to-assembly e uma subclasse de TargetAsmInfo.
6. Opcionalmente, para suportar sub alvos (exemplo: variantes com capacidades diferentes), deve-se também escrever código para uma subclasse da classe TargetSubtarget,
que permite usar em linha de comando os parâmetros -mpcu= e -mattr=.
7. Opcionalmente, para adicionar suporte a Just In Time (JIT), cria-se um emissor
de código de máquina (subclasse de TargetJITInfo) que é usado para emitir código
binário diretamente na memória.
29
Capı́tulo 5
Proposta de Trabalho
Esse trabalho visa o desenvolvimento dos algoritmos de escalonamento de instruções
e alocação de registradores projetados para a arquitetura 2D-VLIW sobre a infraestrutura de compilação LLVM. De forma especı́fica, vislumbra-se implementar o algoritmo
integrado de escalonamento e alocação de registradores apresentado no Capı́tulo 3 junto
à infraestrutura de compilação LLVM além de descrever o modelo de processador (2DVLIW) que pode se beneficiar de algoritmos de escalonamento e alocação integrados. A
motivação desse trabalho reside na possibilidade de realizar comparações entre soluções de
escalonamento e alocação de recursos em diferentes arquiteturas compostas por múltiplas
unidades funcionais.
A integração com o LLVM torna-se factı́vel devido a sua modularização como explicado
na Seção 4.1. O LLVM é um projeto código aberto disponibilizado sob a licença University
of Illinois/NCSA Open Source License. Para ajuda há uma lista de discussão em: http:
//lists.cs.uiuc.edu/mailman/listinfo/llvmdev.
Os objetivos especı́ficos são:
1. Estender e integrar as fases da geração de código de forma a modificar os DAGs necessários para o algoritmo de isomorfismo de subgrafos como explicado na Seção 3.2.
O código do algoritmo de escalonamento de instruções e alocação de registradores já
se encontra implementado de forma independente do LLVM. Deve-se realizar uma
pesquisa detalhada sobre a estrutura de dados disponibilizada pelo LLVM a fim de
adequar as entradas e saı́das do algoritmo; As fases necessárias para implementar
alterações no LLVM estão descritas no Capı́tulo 4;
2. Projetar e implementar no LLVM a geração de código para a máquina da arquitetura
2D-VLIW.
As fases necessárias para implementar uma arquitetura alvo, no LLVM, estão descritas no Capı́tulo 4; e a descrição da arquitetura 2D-VLIW no Capı́tulo 3;
3. Avaliar experimentalmente e verificar métricas para mensurar o desempenho em
diferentes arquiteturas.
30
Simulação de programas dos benchmarks Livermore loops [10], SPEC [7] e MediaBench [9] utilizando os algoritmos de escalonamento e alocação implementados,
comparando os resultados com aqueles utilizados por algoritmos da literatura da
área. Análise dos resultados da simulação considerando métricas como: speedup
e IPC (instructions per cycle) dos programas, tempo de execução dos algoritmos,
número de spill codes gerados, ciclos gerados no código como resultado do escalonamento.
4. Preparar artigos e documentos para serem submetidos em eventos e periódicos da
área;
Uma proposta de cronograma e atividades para o desenvolvimento deste projeto é
apresentada na Tabela 5.1.
Tabela 5.1: Cronograma para execução do plano de trabalho
Atividades
1
2
3
4
5
M A
X X
M J
X X
2011
J A
X X
X X
X X
S O N D
X X
X X X
X X X
X X X X
2012
J F
X
X
X
X
Atividades
1. Projeto e estruturação de algoritmos de escalonamento e alocação de registradores.
2. Implementação de algoritmos de escalonamento e alocação de registradores junto à
infraestrutura LLVM.
3. Experimentação e avaliação de desempenho para efeitos de comparação com trabalhos relacionados.
4. Preparar e organizar artigos e documentos cientı́ficos para serem submetidos em
eventos e periódicos da área.
5. Preparação e escrita da Dissertação de Mestrado a ser submetida para o PPGCC
da FACOM-UFMS.
Destaca-se que os créditos necessários em disciplinas, do PPGCC da FACOM-UFMS,
serão concluı́dos até Julho/2011.
31
Referências Bibliográficas
[1] Alfred V. Aho, Ravi Sethi, e Jeffrey D. Ullman. Compilers: principles, techniques,
and tools. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1986.
ISBN 0-201-10088-6.
[2] Andrew W. Appel. Modern Compiler Implementation in Java. Cambridge University
Press, 1998. ISBN 0-521-58388-8.
[3] David A. Berson, Rajiv Gupta, e Mary Lou Soffa. URSA: A Unified ReSource Allocator for Registers and Functional Units in VLIW Architectures. In Proceedings of
the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques
for Fine and Medium Grain Parallelism, páginas 243–254. North-Holland Publishing
Co., Amsterdam, NL, 1993. ISBN 0-444-88464-5.
[4] David A. Berson, Rajiv Gupta, e Mary Lou Soffa. Integrated Instruction Scheduling and Register Allocation Techniques. In Proceedings of the 11th International
Workshop on Languages and Compilers for Parallel Computing, páginas 247–262.
Springer-Verlag, London, UK, 1999. ISBN 3-540-66426-2.
[5] Lakshmi N. Chakrapani, John Gyllenhaal, Wen mei W. Hwu, Scott A. Mahlke,
Krishna V. Palem, e Rodric M. Rabbah. Trimaran: An Infrastructure for Research
in Instruction-Level Parallelism. Lecture Notes in Computer Science, 3602:32–41,
2004.
[6] James R. Goodman e Wei-Chung Hsu. Code scheduling and register allocation in
large basic blocks. In Proceedings of the 2nd international conference on Supercomputing, páginas 442–452. ACM, New York, NY, USA, 1988. ISBN 0-89791-272-1.
[7] John L. Henning. SPEC CPU2000: Measuring CPU Performance in the New Millennium. IEEE Computer , 33:28–35, July 2000. ISSN 0018-9162.
[8] Chris Lattner e Vikram Adve. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In Proceedings of the 2004 International Symposium on Code Generation and Optimization. Palo Alto, CA, USA, Mar 2004.
[9] Chunho Lee, Miodrag Potkanjak, e William H. Mangione-Smith. MediaBench: A
Tool for Evaluating and Synthesizing Multimedia and Communications Systems. In
Proceedings. of the 30th International Symposium on Microarchitecture, páginas 330–
335. IEEE Computer Society, Research Triangle Park, NC, USA, December 1997.
32
[10] Frank H. McMahon. The Livermore Fortran Kernels: A Computer Test of Numerical
Performance Range. Relatório Técnico UCRL-53745, Lawrence Livermore National
Laboratory, Livermore, CA, USA, December 1986.
[11] Rajeev Motwani, Krishna V. Palem, Vivek Sarkar, e Salem Reyen. Combining Register Allocation and Instruction Scheduling. Relatório Técnico CS-TN-95-22, Stanford
University, Stanford, CA, USA, 1995.
[12] Cindy Norris e Lori L. Pollock. Register allocation sensitive region scheduling. In
Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and
Compilation Techniques, páginas 1–10. IFIP Working Group on Algol, Manchester,
UK, 1995. ISBN 0-89791-745-6.
[13] Cindy Norris e Lori L. Pollock. Experiences with Cooperating Register Allocation and
Instruction Scheduling. International Journal of Parallel Programming, 26(3):241–
283, 1998. ISSN 0885-7458.
[14] Shlomit S. Pinter. Register Allocation with Instruction Scheduling: a New Approach.
Journal of Programming Language, 4(1):21 – 38, 1996.
[15] Massimiliano Poletto e Vivek Sarkar. Linear scan register allocation. ACM Transactions on Programming Languages and Systems, 21:895–913, September 1999. ISSN
0164-0925.
[16] Ricardo R. Santos. 2D-VLIW: Uma Arquitetura de Processador Baseada na Geometria da Computação. Tese de Doutoramento, Unicamp, Jun 2007.
[17] Ricardo R. Santos, Rodolfo Azevedo, e Guido Araujo. Instruction Scheduling Based
on Subgraph Isomorphism for a High Performance Computer Processor. Journal of
Universal Computer Science, 14(21):3465–3480, 2009.
[18] Bernhard Scholz e Erik Eckstein. Register allocation for irregular architectures. SIGPLAN Not., 37(7):139–148, 2002. ISSN 0362-1340.
[19] The LLVM Team. Documentation for the LLVM System. Website, May 2010. http:
//llvm.org/releases/2.8/docs/index.html.
33