Otimização de Código e Código Intermediário

Prévia do material em texto

COMPILADORES 
AULA 5 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Prof. Frank Coelho de Alcantara 
 
 
 
 
2 
CONVERSA INICIAL 
Depois de passar por todos os módulos anteriores, o seu algoritmo, 
representado pelo seu código-fonte, já não pode ser reconhecido como texto, e 
está representado na forma de uma estrutura de dados, sem erros de sintaxe ou 
semântica, permitindo a transcrição em linguagem de máquina. Esse é o último 
estágio do processo de compilação, e o chamaremos de otimização de código, 
simplesmente porque é nesse ponto que serão realizadas as adequações do seu 
algoritmo à linguagem de máquina. 
Estamos em um ponto do processo no qual o analisador semântico 
acabou de verificar seu código, você corrigiu os últimos erros encontrados, todos 
os tipos estão corretamente atribuídos, não existem erros na definição de 
variáveis ou funções e, finalmente, vamos gerar o código de máquina que será 
executado pela sua CPU. Esse código precisa ser eficiente, rápido e pequeno, 
de forma que seu programa seja executado sem desperdiçar recursos. Essa foi 
uma preocupação transversal a todo o processo de compilação, mas até agora 
não estávamos preocupados com as características físicas da sua CPU. 
Nesse módulo final, antes de criar o arquivo que será executado, temos 
que nos preocupar com as características físicas da máquina. Quantos 
registradores temos disponíveis? É uma arquitetura de 64 bits? Temos memória 
cache? Quais instruções a máquina entende? Essas são apenas algumas das 
perguntas que precisam ser respondidas antes que o processo de otimização de 
código tenha início. 
É nessa fase do processo que geraremos um código especial, o código 
intermediário, a partir da árvore semântica, e ele será utilizado para as primeiras 
otimizações. Depois, esse código intermediário será transformado na linguagem 
de máquina desejada e sofrerá as últimas otimizações, sendo, finalmente, 
convertido em código executável. 
Existem muitas técnicas interessantes de otimização de código que são 
específicas de uma determinada arquitetura. Essa é a razão que justifica o 
estudo das técnicas de configuração de compiladores. Todos os compiladores 
precisam ser informados, antes de começar o processo de compilação, sobre 
qual é a arquitetura alvo. Assim, na fase de otimização de código, será possível 
adotar técnicas de otimização adequadas à arquitetura desejada. Veremos nesta 
aula os conceitos referentes à geração do código intermediário e alguns dos 
processos de otimização. 
 
 
3 
TEMA 1 – OTIMIZAÇÃO DE CÓDIGO E CÓDIGO INTERMEDIÁRIO 
Otimização é uma palavra complexa. Em seu sentido mais amplo, 
significa “fazer ou tornar melhor”. No nosso caso, as técnicas de otimização têm 
a função de garantir que o seu algoritmo será executado utilizando o mínimo de 
recursos e o menor tempo possível; elas consistem, em linhas gerais, de técnicas 
que permitirão analisar um determinado fragmento de código, trocando-o por um 
código menor, mais rápido ou que consuma menos energia, sem, é claro, alterar 
a sua função. Podemos classificar a otimização de código em dois grandes 
grupos: a otimização dependente da máquina e a otimização independente da 
máquina. 
Os processos de otimização que são dependentes da máquina – ou, se 
preferir, que são dependentes do hardware – englobam todas as técnicas de 
otimização que são específicas de uma determinada arquitetura de hardware. 
Tais processos são desenhados de forma a obter o rendimento máximo das 
estruturas físicas disponíveis durante o tempo de execução. Notadamente, 
usamos técnicas específicas para utilizar o menor espaço de memória com a 
melhor configuração possível. 
Os processos de otimização independente da máquina – ou 
independentes do hardware – consistem em um conjunto de otimizações que 
pode ser realizado no seu código-fonte, ou na árvore semântica, durante a 
geração do código intermediário, e no próprio código intermediário, para que o 
resultado da conversão deste em linguagem de máquina produza o melhor 
programa possível. A Figura 1 mostra o diagrama desse processo. 
Figura 1 – Esquema de geração de código 
 
O leitor mais curioso deve estar se perguntando: Por que precisamos 
utilizar um código intermediário? Apenas por causa da otimização? Na verdade, 
o código intermediário tem outras vantagens importantes para o processo de 
compilação. Considere, por exemplo, que você tenha acabado de criar um 
compilador sem código intermediário de C para a arquitetura x64 da Intel. Isso 
 
 
4 
quer dizer que você criou um analisador léxico para o C, um analisador sintático, 
um analisador semântico, fez o parse na árvore semântica, transformou essa 
árvore em Assembly do x64 e otimizou esse código. Feito isso, seu cliente 
solicitou um compilador de C para Arm. Você terá de refazer, no mínimo, os 
últimos dois passos. Na maior parte das vezes, terá de refazer todos os passos, 
já que a otimização acaba tendo relação com as análises léxica, semântica e 
sintática, visto precisarmos gerar uma árvore que seja ideal para a geração de 
código. É nesse ponto que o código intermediário começa a se destacar. 
Vejamos, na Figura 2, o esquema de compilador que adotamos desde a primeira 
aula. 
Figura 2 – Diagrama em blocos de um compilador 
 
Observe que consideramos o código intermediário desde nosso primeiro 
contato com compiladores. Agora, vamos observar essa demanda proposta por 
outro ponto de vista. Em lugar de fazer um compilador de C para x64, vamos 
fazer um compilador de C para .obj (lembre-se: o .obj representa o código 
intermediário de muitos compiladores em C) e um módulo otimizador/gerador de 
código par x64. 
Podemos, nessa arquitetura, fazer o melhor conjunto de analisadores 
léxico, sintático e semântico para gerar o melhor código intermediário (.obj) 
possível. Em seguida, vamos transformar esse código intermediário em código 
de máquina de x64 com o máximo de eficiência. Se houver necessidade de 
 
 
5 
compilar para outras arquiteturas, tudo que precisaremos será fazer um novo par 
otimizador/gerador de código para as outras arquiteturas desejadas. Voltaremos 
a esse ponto na última aula. Não deixe de observar que o uso desse código 
intermediário também permite que você faça um grande esforço de otimização 
na criação do código intermediário, e que esse esforço será aproveitado para 
todas as arquiteturas-destino que você desejar, mesmo aquelas que ainda não 
tenham sido inventadas. 
Existem centenas, talvez milhares de códigos intermediários que 
podemos utilizar. Vamos conferir um dos mais simples. Isso permitirá que você 
entenda os processos de otimização sem precisar entender uma nova sintaxe. 
1.1 Three address code (3AC) 
Desde o aparecimento da tecnologia RISC1, nos idos dos anos 1970, o 
Three Address Code tem sido o paradigma mais utilizado para definição de 
linguagens do tipo Assembly cujo alvo sejam máquinas reais ou virtuais. O Three 
Address Code é uma linguagem de programação de baixo nível especificamente 
projetada para facilitar a conversão em código de máquina estruturada sobre o 
conceito de instruções compostas apenas de operadores, operandos e 
resultados. 
Nesse tipo de linguagem, a maior parte das declarações é especificada 
na forma de quatro campos (quádrupla) e trata da atribuição do resultado de uma 
operação binária entre duas variáveis a uma outra variável qualquer, ou seja, no 
máximo três endereços serão utilizados para representar qualquer declaração. 
É essa característica de uso máximo de três endereços que dá origem ao nome 
Three Address Code (3AC). 
A quádrupla será composta por um campo endereço para a variável 
resultado, dois campos endereços para as variáveis (operandos) e um campo 
operador. Essas quádruplas obedecem a uma regra simples: teremos no 
máximo um operando no lado direito da declaração. Podemos exemplificar 
quádruplas em 3AC por meio da declaração𝑎 = 𝑏 𝑂𝑃 𝑐, em que: 𝑎 , 𝑏, 𝑐 serão 
operandos que podem ser constantes, identificadores ou identificadores 
temporários, sendo estes últimos criados pelo próprio processo de compilação; 
e 𝑂𝑃 representa a operação que será realizada. Sem nos preocupar em definir 
 
1 Reduced Instruction Set Computer, ou, em tradução livre, “conjunto de instruções reduzido”. 
 
 
6 
uma nova linguagem de programação, vamos tentar entender o processo de 
transformação de operações algébricas usando o 3AC: vamos conferir como 
podemos traduzir expressões algébricas em 3AC. 
Tomemos, por exemplo, a expressão 𝑐 = 𝑎 + 𝑏 − 𝑑. Temos que traduzir 
essa equação em declarações em 3AC. Para tal, começamos do extremo direito 
e criamos o primeiro operando temporário: 𝑡1: 𝑡1 = 𝑏 − 𝑑. 
Em seguida, precisamos realizar a soma do resultado de 𝑏 − 𝑑 com 𝑎 e, 
para tanto, criamos o segundo operando temporário: 𝑡2: 𝑡2 = 𝑎 + 𝑡1. 
Por fim, precisamos atribuir o resultado da soma 𝑎 + (𝑏 − 𝑑) a 𝑐. Como 
esse valor está em 𝑡2 temos: 𝑐 = 𝑡2. 
 Tudo que fizemos foi representar os nós da árvore sintática da operação 
algébrica como sendo operandos temporários, como pode ser visto no Quadro 
1. 
Quadro 1 – Exemplo de 3AC relacionando expressão algébrica e árvore sintática 
 
Essa forma 𝑎 = 𝑏 𝑂𝑃 𝑐 é a forma simples, adequada aos seres humanos. 
Nós somos induzidos a pensar de forma algébrica desde que entramos na escola 
então não temos dificuldades de entender a representação do 3AC. Contudo, 
esta representação em quadruplas não é adequada a otimização ou a execução 
em hardware. Precisamos aumentar um pouco a complexidade do código 
intermediário para melhorar as possibilidades de otimização. Os códigos 3AC 
voltados para a otimização optam por uma sintaxe ainda mais próxima das 
linguagens Assembly. Esta sintaxe permite o uso de quadruplas, triplas e triplas 
indiretas. 
1.1.1 Quádruplas 
Para representar em 3AC a expressão 𝑎 = 𝑏 𝑂𝑃 𝑐 nesse ambiente de 
compilação voltado à eficiência, teríamos algo como 𝑂𝑃 𝑏, 𝑎 𝑐. Nesse caso, 
estamos usando as regras gerais do 3AC para criar a nossa própria linguagem 
 
 
7 
com o objetivo de mostrar o processo, mas sem nos preocupar em adotar 
qualquer padrão de compilação ou linguagem de programação. Partindo desse 
princípio, podemos criar os operadores que desejarmos. Podemos, por exemplo, 
criar um operador add para adição, um operador mult para multiplicação, e assim 
por diante. Lembre-se: meu compilador, meu código intermediário. Veja o 
exemplo a seguir. 
1.1.1.2 – Exemplo 1 
Considerando a operação aritmética 𝑒 = 𝑎 + 𝑏 ×
𝑐
𝑒𝑓
+ 𝑏 × 𝑎, gere o código 
3AC correspondente e o seu código intermediário. 
Solução 
Neste caso é preciso observar a precedência dos operadores. Vamos 
utilizar a mesma precedência de operadores que temos na aritmética. 
Considerando a expressão, temos a seguinte ordem: exponenciação, divisão, 
multiplicação, soma e atribuição. Então, teremos em 3AC: 
Quadro 2 – Exemplo de uso do 3AC para geração de código intermediário 
 
Fizemos uma flexibilização quanto ao uso de quádruplas justamente por 
existir alguns casos de exceção, nos quais uma quádrupla não será adequada. 
A primeira exceção ocorrerá com operações unárias do tipo 𝑎 = 𝑂𝑃 𝑏, como, 
por exemplo, a negação de um valor (Not). Nesse caso, não representamos o 
primeiro operador na instrução e dispensamos a vírgula 𝑜𝑝 𝑏 𝑎 . Outra exceção 
digna de nota ocorre nos jumps (saltos), tanto condicionais quanto 
incondicionais. 
 
 
8 
ATENÇÃO: os jumps são indispensáveis na maior parte das linguagens de 
programação. São eles que permitem a existência de sub-rotinas ou funções. E 
serão indispensáveis em linguagem de máquina. 
No caso dos jumps, o argumento resultado passa a ser uma referência à 
etiqueta, label, que marca o destino do salto: 
𝑔𝑜𝑡𝑜 𝐿. 
ATENÇÃO: vença seu preconceito. Ainda que seu professor de linguagem 
estruturada tenha lhe proibido de usar o comando goto (ir para), em linguagens 
de baixo nível temos pouca ou nenhuma, opção. Sempre que precisarmos de 
um jump, precisaremos de um goto. 
 
Em no nosso código intermediário, baseado em uma linguagem derivada 
do 3AC, teremos os seguintes tipos de sentenças: 
1. Declarações: podem ser operações binárias (ex.: 𝑡2 = 𝑎 + 𝑡1) ou unárias 
(Ex.: 𝑐 = 𝑜𝑝 𝑏). É importante observar que as operações unárias terão 
precedência sobre as operações binárias. 
2. Operações de cópia: atribuição de um valor a outro (Ex.: 𝑐 = 𝑎). 
3. Jumps incondicionais: instruções do tipo 𝑔𝑜𝑡𝑜 𝐿, em que 𝐿 representa uma 
label que podemos utilizar para marcar pontos específicos do código e 
para construir estruturas de jump (saltos) entre dois pontos diferentes do 
código. Sempre o ponto de destino do salto estará identificado por uma 
label, neste caso, 𝐿. 
4. Jumps condicionais: 𝑖𝑓 𝑥 𝑔𝑜𝑡𝑜 𝐿 𝑒𝑙𝑠𝑒 𝑔𝑜𝑡𝑜 𝐿1; em que 𝐿 𝑒 𝐿1 representam 
labels. Nesse tipo de instrução o jump ocorrerá em direção à label 𝐿 se a 
condição for verdadeira ou se a 𝐿1 se for falsa. Mesmo que neste caso 
existam quatro operadores 𝑖𝑓, 𝑔𝑜𝑡𝑜 e 𝑒𝑙𝑠𝑒, temos apenas três endereços 
(ou operandos) envolvidos 𝑥, 𝐿 𝑒 𝐿1. 
5. Jumps condicionais utilizando operadores relacionais: nesse caso, os 
comandos têm o formato 𝑖𝑓 𝑥 𝑟𝑒𝑙𝑜𝑝 𝑦 𝑔𝑜𝑡𝑜 𝐿 , em que 𝑟𝑒𝑙𝑜𝑝 representa um 
operador relacional (>, <, >=, 𝑒𝑡𝑐.). Nesse caso não existe a condição 
𝑒𝑙𝑠𝑒. 
 
 
9 
6. Chamadas de funções: 𝑝𝑎𝑟𝑎𝑚 𝑥 𝑐𝑎𝑙𝑙 𝐹 𝑟𝑒𝑡𝑢𝑟𝑛 𝑦; em que 𝐹 representa 
uma função, 𝑝𝑎𝑟𝑎𝑚 𝑥 o argumento passado para a função e 𝑟𝑒𝑡𝑢𝑟𝑛 𝑦 o 
endereço que receberá o resultado da função 𝐹. 
7. Instruções indexadas: nesse caso, para o uso de arrays, 𝑥 = 𝑦[𝑖] e 𝑦[𝑖] =
𝑥, observe que são operações de cópia. 
8. Ponteiros e endereços: instruções para referência: 𝑥 = &𝑦 ; 𝑥 =∗ 𝑦 e ∗ 𝑥 =
𝑦. 
Essas regras definem a sintaxe do nosso código intermediário, que 
poderá ser utilizado para a geração do código de máquina e para a otimização, 
mas ainda temos que melhorar um pouco. 
1.1.2 Triplas 
Na representação de 3AC em quádrupla, as variáveis temporárias são, na 
verdade, referências para o espaço de memória onde estão armazenados os 
valores dos operandos e de resultado. De fato, na vida real, não precisamos de 
variáveis para armazenar os valores e podemos usar as próprias referências 
diretamente nas instruções. Veja o Quadro 3 a seguir, no qual recuperamos a 
representação em quádruplas e usamos como referência os números de linhas 
para montar a representação em triplas. 
Quadro 3 – Representação, 3AC, quádruplas e triplas 
 
 
 
10 
1.1.3 Triplas indiretas 
Outra forma de representação utiliza um array extra para armazenar os 
endereços que gravam os resultados de cada declaração na ordem correta. 
Assim, as referências utilizadas em cada declaração apontam para a posição do 
resultado no array. 
Assim, terminamos a criação da sintaxe de uma linguagem para a geração 
de um código intermediário baseado em 3AC. Essa nossa linguagem, um pouco 
informal, contém todos os conceitos necessários à criação desse tipo de código 
intermediário, e não está muito distante das linguagens utilizadas para a criação 
dos códigos intermediários em sistemas de compilação profissional. Vamos ver 
outro exemplo. 
1.1.3.1 Exemplo 2 
Considerando a operação aritmética: 𝑒 = −(𝑎 ∗ 𝑏) + (𝑐 + 𝑑) − (𝑎 + 𝑏 +
𝑐 + 𝑑), gere o códido 3AC correspondente. Não se preocupe com a geração de 
operadores especiais, vamos apenas criar a árvore sintática na forma de código 
3AC. 
Solução 
Vamos representar essa operação utilizando um passo a passo 
comentado e bem detalhado. Não podemos nos esquecer de que as operações 
unárias têm precedência sobre as operações binárias. Também não podemos 
nos esquecer de que existe precedência entreos parênteses e as outras 
operações. Dessa forma, se substituirmos os parênteses por variáveis 
temporárias apenas para entender o problema, teremos: 𝑒 = −𝑡𝑥 + 𝑡𝑦 − 𝑡𝑧. 
Considerando 𝑡𝑥, relacionada ao primeiro parênteses (𝑎 ∗ 𝑏), teremos 
𝑡1 = 𝑎 ∗ 𝑏 , se a substituirmos. 
Para fazer o negativo (−𝑡𝑥) podemos usar uma declaração simples: 
𝑡2 = 0 − 𝑡1 
𝑡𝑥 = 𝑡2 
Agora podemos nos preocupar com 𝑡𝑦, relacionada ao segundo 
parênteses (𝑐 + 𝑑): 
𝑡3 = 𝑐 + 𝑑 
𝑡𝑦 = 𝑡3 
 
 
11 
Temos que nos preocupar com 𝑡𝑧, relacionado com (𝑎 + 𝑏 + 𝑐 + 𝑑) 
𝑡4 = 𝑐 + 𝑑 
𝑡5 = 𝑏 + 𝑡4 
𝑡6 = 𝑎 + 𝑡5 
𝑡𝑧 = 𝑡6 
Não precisaremos das declarações de cópia, então 
𝑡7 = 𝑡3 − 𝑡6 
𝑡8 = 𝑡2 − 𝑡7 
𝑒 = 𝑡8 
Colocando tudo em ordem e junto: 
𝑒 = −(𝑎 ∗ 𝑏) + (𝑐 + 𝑑) − (𝑎 + 𝑏 + 𝑐 + 𝑑) 
𝑡1 = 𝑎 ∗ 𝑏 
𝑡2 = 0 − 𝑡1 
𝑡𝑥 = 𝑡2 
𝑡3 = 𝑐 + 𝑑 
𝑡𝑦 = 𝑡3 
𝑡4 = 𝑐 + 𝑑 
𝑡5 = 𝑏 + 𝑡4 
𝑡6 = 𝑎 + 𝑡5 
𝑡𝑧 = 𝑡6 
𝑡7 = 𝑡3 − 𝑡6 
𝑡8 = 𝑡2 − 𝑡7 
𝑒 = 𝑡8 
Não precisamos utilizar as instruções de cópia, logo: 
𝑡1 = 𝑎 ∗ 𝑏 
𝑡2 = 0 − 𝑡1 
𝑡3 = 𝑐 + 𝑑 
𝑡4 = 𝑐 + 𝑑 
𝑡5 = 𝑏 + 𝑡4 
𝑡6 = 𝑎 + 𝑡5 
 
 
12 
𝑡7 = 𝑡3 − 𝑡6 
𝑡8 = 𝑡2 − 𝑡7 
𝑒 = 𝑡8 
Como 𝑡3 = 𝑡4, podemos otimizar, já removendo essa duplicidade. Assim, 
a expressão algébrica 𝑒 = −(𝑎 ∗ 𝑏) + (𝑐 + 𝑑) − (𝑎 + 𝑏 + 𝑐 + 𝑑) será codificada 
em 3AC da seguinte forma: 
𝑡1 = 𝑎 ∗ 𝑏 
𝑡2 = 0 − 𝑡1 
𝑡3 = 𝑐 + 𝑑 
𝑡5 = 𝑏 + 𝑡3 
𝑡6 = 𝑎 + 𝑡5 
𝑡7 = 𝑡3 − 𝑡6 
𝑡8 = 𝑡2 − 𝑡7 
𝑒 = 𝑡8 
Depois de ver um processo para a geração de código intermediário, 
podemos nos preocupar com a otimização de c. 
TEMA 2 – OTIMIZAÇÃO INDEPENDENTE DE MÁQUINA 
No último exemplo, vimos como o código intermediário pode ser 
otimizado. Em certo ponto, chegamos a duas variáveis temporárias 
armazenando o mesmo valor: 
𝑡3 = 𝑐 + 𝑑 
𝑡4 = 𝑐 + 𝑑 
Essa otimização, ainda que óbvia, ocorre com muita frequência durante o 
processo de otimização e, algumas vezes, até mesmo durante o processo de 
revisão de código. 
A otimização independente da máquina começa nas suas mãos. É você 
o responsável por escrever um código que não contenha redundâncias e que 
seja ótimo para a função necessária. Vamos ver um pequeno exemplo de como 
você pode tornar seu código mais eficiente. Em C, arrays são, na verdade, 
estruturas de dados controladas por ponteiros. Então, para acessar um 
 
 
13 
determinado valor, sempre operamos com endereços em memória. Observe as 
duas declarações a seguir: 
 
Nos dois casos estamos definindo arrays de arrays; como são do tipo 
char, temos dois arrays de strings. O array primeiro ocupará menos memória 
que o array segundo. Em compensação, o acesso ao array segundo será muito 
mais rápido que o acesso ao array primeiro. Isso ocorre porque a memória é 
sequencial, então todas as strings estarão na memória em sequência. Para 
acessar a terceira string do array primeiro será necessário multiplicar três vezes 
o endereço do primeiro elemento da primeira string por 12 e somar 1. No array 
segundo precisarmos multiplicar por 16, três vezes, e somar 1. A diferença está 
no fato de que o comprimento do segundo elemento do array segundo é uma 
potência de dois. Multiplicar por uma potência de dois é apenas um shift e esta 
operação é absurdamente mais rápida que uma multiplicação por inteiro. 
Existem algumas otimizações que podem ser feitas no código-fonte, ou no 
código intermediário, para melhorar sua performance sem alterar a função do 
algoritmo. 
2.1 Peephole optimization 
A palavra peephole pode ser traduzida como olho-mágico. Esse tipo de 
otimização inclui todas as técnicas de otimização realizadas sobre uma pequena 
parte do código. Um conjunto de poucas linhas é analisado, linha por linha, em 
busca de oportunidades de otimização. Todas as vezes em que um desses 
pequenos conjuntos de linhas é analisado o seu ponto inicial é deslocado para a 
próxima linha, e o processo de análise se reinicia. Essa técnica pode ser aplicada 
tanto no código-fonte quanto no código intermediário e inclui: 
 Eliminação de instruções redundantes: ocorre quando duas ou mais 
linhas de código, ou instruções, têm exatamente o mesmo efeito; pode ser 
realizada durante o processo de codificação, durante a geração do código 
intermediário, como vimos em um dos exemplos, e durante a geração da 
linguagem de máquina. 
 Eliminação de código inatingível: ocorre quando, por causa de um jump 
qualquer, parte do código jamais será executada. Novamente, esse tipo 
 
 
14 
de operação pode ser executado em todos os níveis de otimização e é 
independente da arquitetura de hardware utilizada. 
 Eliminação de laços desnecessários: não é raro que alguns laços, 
principalmente em sistemas complexos, sejam desnecessários. 
Tomemos, como exemplo o código em Assembly a seguir, no qual é 
possível ver que o laço GOTO L1 é desnecessário: 
Tabela 1 – Exemplo de supressão de laços durante a otimização 
Antes Depois 
 
 
Em outros casos, notadamente em linguagens de alto nível, durante o 
processo de codificação, podemos apenas reduzir o número de processos 
que o laço executará simplesmente testando se o valor desejado já foi 
encontrado e interrompendo o laço. 
 Simplificação de expressões algébricas: em programas com conteúdo 
matemático, o processamento pode ficar mais simples, rápido e ocupar 
menos memória se as expressões algébricas forem simplificadas. No 
nível do código intermediário e da linguagem de máquina, algumas 
substituições somo 𝑥 = 𝑥 + 1 por 𝑖𝑛𝑐 𝑥 reduzem drasticamente o tempo 
de processamento. o mesmo ocorre se substituirmos 𝑥 ∗ 2 por 𝑥 ≪ 1, 
trocando uma multiplicação por um shift. 
 Redução de constantes: em muitos casos, durante a definição das 
constantes matemáticas utilizadas no processo de codificação, o 
programador determina uma operação que pode ser substituída por um 
número. Por exemplo: 𝑚𝑒𝑖𝑜𝑃𝐼 = 3.1415926/2 pode ser substituído por 
𝑚𝑒𝑖𝑜𝑃𝑖 = 1,5707963, eliminando uma divisão. Outra técnica muito 
importante de otimização é a que chamamos de otimização de blocos 
básicos. 
TEMA 3 – OTIMIZAÇÃO EM BLOCOS BÁSICOS 
Vimos algumas técnicas de otimização que podem ser aplicadas tanto no 
código-fonte quanto no código intermediário. Algumas, inclusive, podem ser 
 
 
15 
aplicadas em linguagem de máquina e, ainda assim, são independentes da 
máquina-alvo. As técnicas de otimização em blocos básicos são, para todos os 
efeitos, exclusivas do código intermediário. 
Chamamos de blocos básicos qualquer conjunto linear de instruções com 
começo e fim determinados de tal forma que não exista nenhum ponto de 
entrada ou saída no meio do bloco. Isto é, não há nenhum jump no meio do bloco 
e não há nenhum ponto no meio do bloco que seja o destino de qualquer jump. 
Vamos tentar deixar isso mais claro com um exemplo. 
3.1 Exemplo 3 
Divida o código intermediário a seguir em seus blocos básicos. 
𝐿𝑎𝑏𝑒𝑙 𝐿1 
𝑥 = 𝑧 − 3 
𝑦 = 2 ∗ 𝑥 
𝑖𝑓 (𝑥 > 5) 𝐿2 𝑒𝑙𝑠𝑒 𝐿3 
𝐿𝑎𝑏𝑒𝑙 𝐿2 
𝑥 = 𝑥 + 1 
𝑦 = 𝑦 + 1 
𝑔𝑜𝑡𝑜 𝐿4 
𝐿𝑎𝑏𝑒𝑙 𝐿3 
𝑥 = 𝑥 − 1 
𝑦 = 𝑦 − 1 
𝑔𝑜𝑡𝑜 𝐿4 
𝐿𝑎𝑏𝑒𝑙 𝐿4 
𝑥 = 𝑥 + 𝑦 
 
A divisão em blocos básicos exclui as labels, já que estas são apenas 
marcadores no código; podemos criar, ao mesmo tempo, um diagrama de 
controle de fluxo para entender nosso código. Nesse caso, ficaremos com os 
seguintes blocos: 
Figura 3 – Exemplo de blocos básicos 
 
 
 
16 
 Não há nenhum jump no meio do bloco. Observe também que um jump 
sempre determina o fim um bloco e que o destino de um jump sempre determina 
o começo de um bloco. Podemos definir um bloco básico como sendo a maior 
parcela de código que não contém uma label, exceto a label da primeira instrução 
do bloco, e nenhum jump, exceto o jump na última instrução do bloco. Devemos 
utilizar esse conceito para encontrar um diagrama de fluxo de dados, comoo 
mostrado no exemplo da Figura 3. Podemos otimizar o código intermediário tanto 
otimizando o código dentro dos blocos quanto otimizando o diagrama de fluxo 
de dados. Dentro dos blocos básicos podemos: 
1. Eliminar declarações repetidas: 
𝑎 = 𝑏 + 𝑐 
𝑏 = 𝑎 − 𝑑 
𝑐 = 𝑏 + 𝑐 
𝑑 = 𝑎 − 𝑑 
 
Existem duas declarações comuns, apesar de não repetidas, que podem 
ser simplificadas economizando tempo de processamento e recursos. 
𝑎 = 𝑏 + 𝑐 
𝑏 = 𝑎 − 𝑑 
𝑐 = 𝑎 
𝑑 = 𝑏 
 
2. Substituir variáveis: considere o seguinte bloco: 
Lable L1 
t1 = 2 ∗ 𝑥 
𝑡2 ∶= 𝑡1 + 𝑥 
𝑖𝑓 𝑡2 > 0 𝑔𝑜𝑡𝑜 𝐿2 
 
Observe que não existe nenhuma forma de encontrar 𝑡2 sem primeiro 
calcular 𝑡1, mas esse código pode ser otimizado: 
Lable L1 
𝑡2 ∶= 3 ∗ 𝑥 
𝑖𝑓 𝑡2 > 0 𝑔𝑜𝑡𝑜 𝐿2 
 
3. Evitar a cópia de variáveis: se há uma expressão do tipo 𝑡1 = 𝑥, 
podemos, dentro do bloco, substituir todas a referências posteriores a 𝑥 
por 𝑡1 utilizando apenas uma variável temporária. Essa modificação 
provavelmente não irá tornar o código menor ou mais rápido, mas 
permitirá localizar novas opções de otimização. Vamos ver um exemplo 
dessas otimizações: 
 
 
17 
4.1 Exemplo 4 
Otimize o código a seguir supondo que seja um bloco básico de um 
código maior e apenas 𝑚 e 𝑛 sejam utilizados no resto do programa. 
𝑡1 = 𝑥 ∗∗ 2 
𝑡2 = 3 
𝑡3 = 𝑥 
𝑡4 = 𝑡3 ∗ 𝑡3 
𝑡5 = 𝑡2 ∗ 2 
𝑚 = 𝑡1 + 𝑡4 
𝑛 = 𝑡5 ∗ 𝑚 
Podemos começar com a simplificação algébrica analisando as linhas 1 e 5: 
𝑡1 = 𝑥 ∗∗ 2 
𝑡2 = 3 
𝑡3 = 𝑥 
𝑡4 = 𝑡3 ∗ 𝑡3 
𝑡5 = 𝑡2 ∗ 2 
𝑚 = 𝑡1 + 𝑡4 
𝑛 = 𝑡5 ∗ 𝑚 
Substituindo essas linhas teremos: 
𝑡1 = 𝑥 ∗ 𝑥 
𝑡2 = 3 
𝑡3 = 𝑥 
𝑡4 = 𝑡3 ∗ 𝑡3 
𝑡5 = 𝑡2 ≪ 1 
𝑚 = 𝑡1 + 𝑡4 
𝑛 = 𝑡5 ∗ 𝑚 
 
As duas operações são mais rápidas. Podemos agora nos preocupar com 
a cópia de variáveis: 
𝑡1 = 𝑥 ∗ 𝑥 
𝑡2 = 3 
𝑡3 = 𝑥 
𝑡4 = 𝑡3 ∗ 𝑡3 
𝑡5 = 𝑡2 ≪ 1 
𝑚 = 𝑡1 + 𝑡4 
𝑛 = 𝑡5 ∗ 𝑚 
E podemos otimizar para: 
𝑡1 = 𝑥 ∗ 𝑥 
𝑡2 = 3 
𝑡3 = 𝑥 
𝑡4 = 𝑥 ∗ 𝑥 
𝑡5 = 3 ≪ 1 
𝑚 = 𝑡1 + 𝑡4 
𝑛 = 𝑡5 ∗ 𝑚 
 
 
18 
 
Fica claro que podemos reduzir uma constante: 
 
𝑡1 = 𝑥 ∗ 𝑥 
𝑡2 = 3 
𝑡3 = 𝑥 
𝑡4 = 𝑥 ∗ 𝑥 
𝑡5 = 3 ≪ 1 
𝑚 = 𝑡1 + 𝑡3 
𝑛 = 𝑡5 ∗ 𝑚 
Obtendo: 
 
𝑡1 = 𝑥 ∗ 𝑥 
𝑡2 = 3 
𝑡3 = 𝑥 
𝑡4 = 𝑥 ∗ 𝑥 
𝑡5 = 6 
𝑚 = 𝑡1 + 𝑡4 
𝑛 = 𝑡5 ∗ 𝑚 
 
Podemos eliminar declarações comuns: 
𝑡1 = 𝑥 ∗ 𝑥 
𝑡2 = 3 
𝑡3 = 𝑥 
𝑡4 = 𝑥 ∗ 𝑥 
𝑡5 = 6 
𝑚 = 𝑡1 + 𝑡4 
𝑛 = 𝑡5 ∗ 𝑚 
E encontrar: 
𝑡1 = 𝑥 ∗ 𝑥 
𝑡2 = 3 
𝑡3 = 𝑥 
𝑡4 = 𝑡1 
𝑡5 = 6 
𝑚 = 𝑡1 + 𝑡4 
𝑛 = 𝑡5 ∗ 𝑚 
Neste ponto podemos ver os problemas com declarações comuns 
novamente: 
𝑡1 = 𝑥 ∗ 𝑥 
𝑡2 = 3 
𝑡3 = 𝑥 
𝑡4 = 𝑡1 
𝑡5 = 6 
𝑚 = 𝑡1 + 𝑡4 
𝑛 = 𝑡5 ∗ 𝑚 
E ficamos com: 
𝑡1 = 𝑥 ∗ 𝑥 
 
 
19 
𝑡2 = 3 
𝑡3 = 𝑥 
𝑡4 = 𝑡1 
𝑡5 = 6 
𝑚 = 𝑡1 + 𝑡1 
𝑛 = 6 ∗ 𝑚 
Finalmente podemos eliminar o código inútil: 
 
𝑎 = 𝑥 ∗ 𝑥 
𝑚 = 𝑡1 + 𝑡1 
𝑛 = 6 ∗ 𝑚 
 
E vamos parar por aqui. Contudo, observe que 𝑡1 + 𝑡1 é igual a 2𝑡1 que, 
por sua vez, pode ser substituído por um shift e, dependendo do hardware-
alvo, pode ser que esta linha ainda possa ser otimizada. 
TEMA 4 – GERAÇÃO DE CÓDIGO 
Quando chegarmos à geração de código, já teremos passado por todos 
os níveis de análise, e nosso código intermediário já terá sido criado, tenha sido 
ele criado especificamente para uma determinada arquitetura de hardware ou de 
uma forma mais genérica. Será esse código intermediário aquele que será 
transformado em código Assembly e, finalmente, em linguagem de máquina. 
Podemos definir o processo de geração de código em quatro grandes blocos: 
1. Seleção de instrução: no código intermediário otimizado, consiste de um 
conjunto de declarações. Por exemplo: podemos ter chegado a uma 
declaração como 𝑧 = 𝑡1 + 𝑡2, que pode ser substituída por uma 
multiplicação ou por um shift, e é nessa fase que precisaremos selecionar 
qual operação é mais adequada de acordo com a arquitetura. Existem 
ainda os casos em que uma determinada operação pode substituir 
diversas outras. O exemplo clássico são as operações de ponto flutuante. 
Todas as operações de ponto flutuante, como multiplicação e divisão, 
podem ser realizadas utilizando as instruções com números inteiros. 
Caberá ao compilador optar pela operação que consumir menos memória 
e for mais rápida. Como os processadores mais modernos possuem 
hardware específico para ponto flutuante, é, na maioria das vezes, mais 
inteligente utilizar estas funções. 
2. Agendamento de instruções: definir a ordem como as instruções serão 
executadas. Preocupação importante hoje, já que muitas máquinas 
 
 
20 
dispõem de várias CPUs, a execução do código em paralelo pode 
aumentar significativamente a velocidade do programa. Então, não só a 
ordem em que as declarações serão executadas, mas também sua 
distribuição deve ser levada em consideração durante a geração do 
código. 
3. Alocação de registradores e memória: nenhum espaço de 
armazenamento é tão rápido quanto os registradores. Contudo, 
infelizmente, sua quantidade é limitada às dezenas, enquanto não é raro 
encontrar programas com dezenas de milhares de variáveis. Distribuir as 
variáveis nos diversos tipos de memória é, além de função do processo 
de geração de código, fator primordial de otimização dependente da 
máquina. Além dos registradores, as máquinas modernas contêm um ou 
mais níveis de memória cache, memórias que são construídas dentro do 
próprio chip da CPU e que são várias vezes mais rápidas que as 
memórias externas. Caberá ao processo de geração de código alocar 
essas memórias. Da mesma forma também caberá à geração de código 
a escolha do dado que será colocado nas memórias externas à CPU. 
4. Geração de informações de debug: durante a geração do código, dados 
importantes, como os endereços de entrada de funções, são guardados 
no próprio código gerado. Essas informações poderão ser utilizadas para 
a localização de problemas no código gerado ou durante a fase de 
otimização e encapsulamento final. 
Se consideramos essas quatro funções, o código gerado será um código 
intermediário, transcrito para o Assembly da arquitetura-alvo com as melhores 
instruções, agendamento correto, utilizando os recursos mínimos de memória e 
marcado para correção. Esse código ainda será otimizado. 
TEMA 5 – OTIMIZAÇÃO DEPENDENTE DA MÁQUINA E ENCAPSULAMENTO 
Todas as técnicas de otimização que vimos no processo de otimização 
não dependente da máquina podem ser aplicadas ao código gerado no 
Assembly da arquitetura-alvo antes que este seja compilado em binário, a 
verdadeira linguagem de máquina. Além dessas técnicas, poderemos: 
 Utilizar instruções especiais: os processadores modernos possuem 
instruções específicas para lidar com tipos especiais de dados, como 
 
 
21 
áudio, vídeo, tabelas e vetores. Caberá ao processo de otimização de 
código dependente da máquina encontrar os blocos básicos do código 
Assembly que podem ser substituídos e fazer esta substituição. 
 Reorganizar o código: em algumas arquiteturas, a ordem das operações 
é importante. Podemos, por exemplo, ter arquiteturas nas quais ler a 
memória seja mais eficiente que somar registradores. Caberá ao processo 
de otimização identificar esses gargalos e adotar a sequência mais 
eficiente. 
Uma vez que o código tenha sido otimizado, poderá ser convertido em 
linguagem de máquina e encapsulado. Esse processo de encapsulamento é 
importante para que o seu código possa ser executado em um ambiente de 
execução composto de hardware e sistema operacional e, como não poderia 
deixar de ser, é diferente em cada um desses ambientes. 
Vamos, por exemplo, analisar o ambiente composto por processadores 
Intel rodando o Windows 10. 
O código que geraremos usará o conjunto de instruções conhecidas como 
x64e deverá atender, no mínimo, ao formato PE (Portable Executable), um 
formato de arquivo definido no Windows NT 3.1 e usado até os dias de hoje. Tal 
formato consiste em uma tabela de bytes começando com os binários 0101 1010 
e 0100 1101 que representam as letras MZ, iniciais de Mark Zbikowski, criador 
do padrão. O padrão de informações nesse modelo pode ser visto na Tabela 2. 
Tabela 2 – Estrutura do cabeçalho de um executável Windows 
Campo Função 
 
Começa com as letras MZ e contém uma struct com as 
informações necessárias para rodar o seu executável. Contém 
também um pequeno programa de testes. 
 
Uma das informações contidas no DOS Header é um Ponteiro 
para o início do PE Header, em que se encontram as letras PE e, 
em seguida, as informações necessárias à execução no 
Windows. 
 
Um cabeçalho importado do Unix ainda mantém informações 
relevantes sobre a máquina que executará o programa e sua 
memória. 
 
Apesar do nome, esta seção é obrigatória e contém informações 
sobre a estrutura de memória necessária para executar seu 
programa. 
DOS Header 
PE Header 
COFF Header 
Optional 
Header 
 
 
22 
 
 
As duas últimas seções contêm os dados referentes às estruturas 
de dados que serão necessários para a execução do seu 
programa, incluídos os endereços físicos e virtuais. 
Todas essas informações são geradas durante a fase final de geração de 
código e utilizadas para a criação do seu executável. 
FINALIZANDO 
Essa foi uma longa jornada. Partimos de um texto contendo um algoritmo 
em linguagem de alto nível e chegamos a um arquivo executável. Vimos, nesta 
última aula, a importância do código intermediário e algumas das técnicas que 
podemos utilizar para aumentar a eficiência dos nossos programas. Espero que 
você tenha percebido que a eficiência do seu programa começa pela forma como 
você codifica suas ideias e resolve seus problemas e termina na otimização do 
código gerado já em linguagem de máquina. 
O 3AC é uma forma interessante de entender – e de aplicar – os conceitos 
de otimização no seu código, notadamente porque sua estrutura é perfeitamente 
adequada à representação de árvores sintáticas ou semânticas, facilitando a 
transformação dos objetos resultantes do processo de análise do código-fonte 
em código para otimização. Essa importância fica ainda mais clara quando 
percebemos quão perto da linguagem Assembly o 3AC está. 
Essa proximidade permitiu que estudássemos as técnicas de otimização 
sem precisarmos estudar nenhuma linguagem Assembly. Permitiu também que 
eu pudesse afirmar que todas as técnicas que vimos para o 3AC podem ser 
aplicadas diretamente no código Assembly, totalmente independente da 
máquina, e, depois, no código Assembly adequado à sua arquitetura-alvo. 
Por fim, você deve dedicar um pouco de esforço para entender o processo 
de encapsulamento de código. Esse processo será diferente em todos os pares 
hardware/sistema operacional que forem usados para rodar os seus programas. 
Entretanto, se sua preocupação for eficiência e velocidade, será temeroso deixar 
isso por conta das configurações padrão dos compiladores comerciais. 
Apesar de longa, esta jornada ainda não terminou. O processo de 
compilação mudou muito nos últimos anos e você irá se deparar, no mercado, 
Section Table 
Mapable 
Sections 
 
 
23 
com soluções de tradução de código-fonte em linguagem de máquina que 
utilizarão os conceitos que vimos até agora de formas completamente inusitadas. 
Não perca a última e mais excitante aula desta disciplina. 
 
 
 
24 
REFERÊNCIAS 
AHO, A. V. et al. Compiladores: princípios, técnicas e ferramentas. 2a. ed. 
Boston, MA, USA: Pearson Education Inc., 2007. 
HOLUB, A. I. Compiler design in C. Englewood Cliffs, NJ, USA: Prentice Hall 
Software Series, 1990. 
MOGENSEN, T. Æ. Basics of Compiler Design. Copenhagen: Department of 
Computer Science University of Copenhagen, 2010. 
PITTS, A. M. Regular Languages and Finite Automata for Part IA of the 
Computer Science Tripos. Cambridge University Computer Laboratory. 
Cambridge, 2013. p. 58. 
STEPHEN Cole Kleene. Wikipedia, 24 dez. 2017. Disponível em: 
<https://en.wikipedia.org/wiki/Stephen_Cole_Kleene>. Acesso em: 27 nov. 2017.