Construção de Compiladores
Análise e Otimização
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Módulos
Lista de tokens
Árvore sintática
Árvore sintática anotada
Código intermediário
Código intermediário otimizado
Linguagem de máquina
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Consiste em reconhecer instruções que formam um
específico padrão que pode ser:
 Substituído por um menor
 Substituído por um padrão mais eficiente
• Tipos de otimização
 Peephole: análise é feita sobre um pequeno conjunto de
instruções
 Baseados em análise: alguma técnica de análise de código deve
ser empregada para detectar relações
 Análise de tempo de vida (Liveness Analysis)
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• “Todo programa é melhorado se uma instrução é retirada”
 O programa deve apresentar o mesmo comportamento
x = a + b;
Universidade Federal da Paraíba
Departamento de Informática
Pra tirar uma instrução (x = a + b;),
devemos provar que o programa
não foi alterado
Análise e Otimização
• Propriedades que podem ser demonstradas
 O comando x = a+b nunca é executado
 O comando é inútil porque todas as vezes
x recebe o mesmo valor que tinha antes
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Não é prático otimizar um programa tentando eliminar
sucessivamente os seus comandos
 Condições de eliminação variadas
 Depende do comando
 Da posição do comando
 De todos os outros comandos do programa
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Outro exemplo clássico
 Retirada de comandos de um loop
Se N é 100, 100 somas a menos são executadas
Mas se o valor de N é 0??
E se “a” é usada após o loop???
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• A otimização deve definir a quantidade de informação que se deseja
manipular
 Podemos examinar otimizações locais
 Trechos pequenos de programas
 Trechos sem desvios
 Otimizações em um nível intermediário
 Considera apenas funções, módulos, ou classes
 Otimizações globais
 Consideram inter-relações de todas as partes de um programa
• A maioria dos compiladores oferece otimizações do primeiro tipo, e
quando muito algumas otimizações de nível intermediário.
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Um programa em representação intermediária pode ser
dividido em blocos básicos da seguinte maneira:
 Primeiro comando inicia um bloco
básico
 Qualquer comando rotulado, ou
que de alguma forma seja alvo de
um comando de desvio inicia um
novo bloco básico
 Qualquer comando de desvio,
condicional ou incondicional
termina um bloco básico
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Em um programa de grande porte, temos:
 Execução gasta 90% em 10% do código, e 10% do tempo nos
90% do código restantes.
 Regra dos (90%-10%)
 Em algumas referências temos (70%-30%)
• Principal vilão: loops aninhados
 Muito do trabalho no desenvolvimento de técnicas de otimização
é dedicado aos loops
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Ferramentas Code Profiler
 Registram o perfil de execução do programa, permitindo a
identificação dos trechos mais executados
• AQtime
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Oportunidades de otimização








Eliminação de código morto
Renomeação de variáveis temporárias
Transformações algébricas
Dobramento de constantes
Redução de força
Otimizações de loop
Eliminação de variáveis de indução
Eliminação de sub-expressões comuns
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Eliminação de código morto
 Código que não pode ser alcançado durante a execução de um
programa
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Eliminação de código morto
- Tema de algumas patentes
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Renomeação de variáveis temporárias
 Variáveis temporárias introduzidas durante a geração de código
intermediário podem não ser estritamente necessárias
 Considere a seguinte situação:
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Renomeação de variáveis temporárias
 Como variáveis temporárias são temporárias, podemos reusá-la
t4  t1
t5  t2
Del(t3)
Del(t6)
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Transformações algébricas
 Algumas transformações baseadas em propriedades algébricas
 Comutatividade
 Associatividade
 Identidade
 Exemplo: como a soma é comutativa, temos:
x=a+b*c;
x=b*c+a;
O primeiro operador
sempre deve estar no
acumulador
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Transformações algébricas
 Um exemplo baseado na associatividade
x=(a+b)+(c+d);
Universidade Federal da Paraíba
Departamento de Informática
x=(((a+b)+c)+d);
Análise e Otimização
• Dobramento de constantes
 Expressões compostas por constantes podem ser avaliadas em
tempo de compilação
 Isso evita sua avaliação repetida em tempo de execução
(i < 99)
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Redução de força
 Situação onde operações mais caras podem ser substituídas por
operações mais baratas
 Exemplo: calcule o comprimento da concatenação dos strings s1
e s2
strlen(strcat(s1, s2))
strlen(s1) + strlen(s2)
 Exemplo: calcule o quadrado de um número x
pow(x, 2)
x*x
e 2.0 * ln x, utiliza séries para calcular o logaritmo natural e a exponencial
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Otimizações de loop
 A mais comum é a transferência de computações invariantes do
loop para fora dele
 Dado o comando x=exp, A expressão exp é composta apenas de
constantes, ou de variáveis cujos valores não são alterados dentro
do loop
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Eliminação de variáveis de indução
 Variáveis de indução assumem valores em progressão
aritmética, a cada vez que o código do loop é executado
Qual a outra otimização feita no código resultante?
Qual outra otimização poderia ter sido feita no código resultante?
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Eliminação de sub-expressões comuns
 Suponha que a mesma expressão ocorre mais
de uma vez em um trecho de programa
 Se a e b não são alterados, é possível guardar
o valor da expressão a+b em uma temporária
 Se a variável x ainda está disponível com o
mesmo valor, podemos usar o próprio x
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Eliminação de sub-expressões comuns
 É necessário garantir que os valores de a, b (e, se for o caso, x)
não se alteram
 Preciso examinar todos os comandos que podem ocorrer entre as
duas avaliações da expressão
 E se estes dois comandos não estão no mesmo bloco básico?
 Devemos verificar quais outros blocos básicos podem ter seus
comandos executados
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Eliminação de sub-expressões comuns
 Podemos ter problemas mesmo quando os comandos estão no
mesmo bloco
 Exemplo: array
 Exemplo: ponteiros
j=i
É o endereço de memória
de “a” ou “b”.
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Eliminação de sub-expressões comuns: o algoritmo DAG
 Determinar a possibilidade de eliminação de subexpressões
comuns em um bloco básico
 Baseado na construção de um grafo acíclico dirigido (dag)
 Vértices representam valores distintos assumidos pelas diversas
variáveis do programa no bloco considerado
Valor de alguma variável do programa
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Eliminação de sub-expressões comuns: o algoritmo DAG
 Em princípio, vértices distintos correspondem a valores que
podem ser distintos durante a execução
 Cenário A - Int a, b, x, y, ...
 Cenário B - após execução de x=a+b; e y=a+b;
Cenário A
Universidade Federal da Paraíba
Departamento de Informática
Cenário B
Análise e Otimização
• Eliminação de sub-expressões comuns: o algoritmo DAG
 Podemos distinguir dois tipos de variáveis:
 Variáveis definidas pelo programador
 Variáveis temporárias, que são usadas apenas durante a execução
do trecho em questão
– Possuem valores irrelevantes no início e no fim do trecho considerado
– São normalmente criadas durante a geração de código intermediário
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Eliminação de sub-expressões comuns: o algoritmo DAG
 Inicialmente, cada variável definida pelo programador rotula um
vértice separado
 Cada vez que um comando x=y op z; for considerado,
procuraremos um vértice n com o operador op, que tenha como
filhos vértices rotulados por y e z.
 Se este vértice existir, passará a ser o vértice rotulado com x, além
de outros rótulos que já existam para n.
 Se não existir, um vértice será criado com essas características, e
um único rótulo, x.
 Este processo vale para todos os operadores binários op da
linguagem intermediária. Operadores unários, ternários, etc. são
tratados de forma semelhante.
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Eliminação de sub-expressões comuns: o algoritmo DAG
t7 z x
+
x
t2
*
c
Universidade Federal da Paraíba
Departamento de Informática
a
t4
t1
+
a
y
t6
+
t5
+
y
t3
*
b
d
e
x
y
z
Análise e Otimização
• Eliminação de sub-expressões comuns: o algoritmo DAG
 O último passo é retirar dos nós os rótulos desnecessários:
 Se um nó está rotulado por alguma variável declarada pelo
programador, todas as variáveis temporárias são removidas
 Caso contrário apenas uma variável temporária será deixada.
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Eliminação de sub-expressões comuns: o algoritmo DAG
 Gerando o código otimizado
 Podemos usar uma ordem qualquer dos nós desde que um valor só
seja usado após a instrução que gerou o mesmo valor
 No caso de mais de uma variável rotulando um nó (z e x) apenas
para uma delas o comando é gerado, sendo o valor copiado para as
demais
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Benchmark
 Conjunto de testes
 http://www.netlib.org/benchmark/
 Livermorec benchmark
Universidade Federal da Paraíba
Departamento de Informática
Análise e Otimização
• Observação final:
 “Embora a otimização possa melhorar as características de um
programa, ela não faz milagres”
 Não se pode justificar um programa mal escrito, porque “vai ser
otimizado”.
 Em particular, normalmente a otimização não altera a ordem dos
algoritmos, alterando apenas as constantes multiplicativas
 Se existe para um problema um algoritmo O(n log n), não espere
que um programa em que você usou um algoritmo O(n2) se
transforme durante a otimização no algoritmo O(n log n).
Universidade Federal da Paraíba
Departamento de Informática