5 - Geração de código

Prévia do material em texto

DESCRIÇÃO
Ambiente de execução, Geração de código, Otimização e geração de programas executáveis.
PROPÓSITO
Apresentar as características do ambiente de execução de programas, analisar a geração de
código e a otimização de código. Apresentar os montadores e ligadores, que são ferramentas
essenciais para a geração do programa executável.
OBJETIVOS
MÓDULO 1
Identificar as características do ambiente de execução dos programas
MÓDULO 2
Classificar a geração de código intermediário e de montagem
MÓDULO 3
Descrever as principais técnicas de otimização de código
MÓDULO 4
Classificar o funcionamento dos montadores e dos ligadores
INTRODUÇÃO
A etapa de síntese é o final do processo de compilação e produz, como seu produto, o código
de montagem que será submetido ao montador para gerar o módulo objeto.
Nesta etapa, são realizados três passos: Geração de código intermediário, otimização e
geração de código de montagem.
Embora sejam vistos como passos autônomos, na maior parte das implementações reais eles
são realizados de forma concorrente.
Neste tema, estudaremos esta etapa e seus passos. Veremos, ainda, o ambiente de execução
de um programa, bem como de que modo é gerado o executável pelo ligador e realizada a sua
carga pelo carregador.
MÓDULO 1
 Identificar as características do ambiente de execução dos programas
AMBIENTE DE EXECUÇÃO
Ao término da etapa de Análise, temos algum tipo de representação intermediária do código-
fonte que será utilizada pela etapa de síntese para gerar o código de montagem.
Porém, antes de estudarmos os detalhes da criação deste código, veremos alguns detalhes
importantes referentes ao ambiente de execução de um programa devido ao seu impacto na
geração do código executável.
Fonte:Shutterstock
Estes aspectos de tempo de execução envolvem principalmente:
A alocação e gerência da memória do programa.
A chamada e controle de procedimentos.
O controle do escopo de declarações.
ORGANIZAÇÃO DA MEMÓRIA
Quando nos referimos à organização da memória, no contexto da compilação, estamos nos
referindo à alocação e liberação de memória para dados e instruções. A gerência do uso da
memória é realizada por um conjunto de rotinas (run-time support package) carregadas junto
ao módulo objeto gerado.
A organização da memória de um código-objeto pode ver vista na Figura 1, onde temos
basicamente duas áreas, dados e código, que são criadas a partir de pseudo-instruções do
assembly, conforme veremos mais à frente neste tema.
Fonte: EnsineMe
 Figura 1 ‒ Organização da memória de um código-objeto.
O local de armazenamento de um dado ou linha de comando na memória vai depender da
estratégia de alocação utilizada pelo sistema operacional (SO).
A memória para o programa em execução deve conter:
O código-objeto gerado.
O espaço para as variáveis globais (área estática).
A pilha para ativação de procedimentos.
O espaço para memória dinâmica (heap).
Como os primeiros SO eram monotarefa, o processo ocupava toda a memória disponível, com
exceção da área destinada ao próprio SO. Nos sistemas mais modernos, multitarefa, começou
a ser usado um esquema de memória virtual onde o espaço de endereçamento do processo
não corresponde sempre à mesma área da memória física, o que exigiu a relocação do código.
 SAIBA MAIS
Além disso, o processo recebe um espaço de endereçamento virtual que pode ser maior que a
memória RAM física e os seus “pedaços”, normalmente chamados de páginas, são carregados
e descarregados da memória RAM por demanda, caracterizando o que chamamos de
paginação.
Observação: Dois aspectos importantes para você observar é que:
Processo é o termo usado para referenciar um programa em execução.
Um programa não pode ser executado direto do disco (ou qualquer outro periférico), tem
que estar na memória.
Desta forma, um programa em execução possui uma organização de memória correspondente
à da figura 2.
Fonte: EnsineMe, 2020
 Figura 2 ‒ Organização da memória virtual de um processo.
Vejamos, agora, com um pouco mais de detalhes, cada uma destas áreas.
CÓDIGO-OBJETO
Esta área armazena as linhas de comando do programa. Como eles não sofrem alteração
durante a execução, podem receber o endereço estático.
ÁREA DE DADOS ESTÁTICA
Da mesma forma que a área de código, aqui pode ser utilizada alocação estática, já que as
variáveis do programa normalmente são declaradas com um determinado tipo e seu tamanho
não muda durante a execução do programa. Quando a linguagem-fonte permite mudar o tipo
da variável em tempo de execução, estas variáveis terão que utilizar alocação dinâmica.
ALOCAÇÃO EM PILHA
As áreas de dados para procedimentos são colocadas na pilha porque a alocação somente
será realizada quando da chamada do procedimento.
ALOCAÇÃO DINÂMICA
Estruturas referenciadas por ponteiros são reservadas dinamicamente por comandos
específicos de manipulação dos ponteiros. Normalmente, tais estruturas são alocadas na área
denominada "heap", que cresce no sentido contrário ao da pilha.
ALOCAÇÃO ESTÁTICA
A Figura 3 mostra o espaço de endereçamento virtual de um processo com as seções de
alocação estática destacadas. Note que o espaço do processo começa em 0x0000 0000 0040
0000.
Fonte: EnsineMe, 2020
 Figura 3 ‒ Organização da memória virtual de um processo.
Considere agora o seguinte programa em C com duas variáveis globais (a e b). Estas variáveis
são somadas e o resultado é retornado para o usuário.
1 long int a, b;
2 int main ( long int argc , char ** argv )
3 {
4 a = 7; 
5 b = 6; 
6 6 b = a+b; 
7 return b; 
8 }
Ao traduzir o programa para a linguagem assembly, o código gerado seria:
1 .section .data
2 A: .quad 0
3 B: .quad 0
4 .section .text
5 globl _start
6 _start :
7 movq $6 , A
8 movq $7 , B
9 movq A, % rax
10 movq B, % rbx 
11 addq %rax , % rbx # % rbx := % rbx + % rax
12 movq $60 , % rax
13 movq %rbx , % rdi
14 syscall
O primeiro aspecto a ser levantado é como as variáveis globais “A” e “B” foram declaradas no
programa assembly (linhas 2 e 3) ou seja, como rótulos declarados na seção “.data”.
Quando o programa for colocado em execução, serão reservados dois espaços de inteiro de 64
bits (devido ao parâmetro quad) das linhas 2 e 3. Já o 0 corresponde ao valor inicial da
variável, que no assembly precisa de inicialização para ser colocada em endereços diferentes.
Após a montagem e a ligação, obteremos o arquivo executável correspondente. Ao usar um
analisador de código, como o GDB, poderíamos visualizar o código em linguagem de máquina
e, por exemplo, a parte correspondente ao comando da linha 8 seria:
...
4000b0: 48 c7 04 25 e7 00 60 movq $0x7,0x6000e7
4000b7: 00 07 00 00 00
4000bc: ...
Onde
A primeira coluna indica endereços.
A segunda, o conteúdo de cada endereço.
A última coluna indica o mnemônico daquela instrução.
Analisando o retorno, podemos ver que a instrução movq $7, B quando em linguagem de
máquina, está alocada no endereço 4000b0: e em linguagem de máquina possui 12 bytes
(0x48c7 0425 e700 6000 0700 0000). Ela nos permite, ainda, verificar que o rótulo B está no
endereço 0x6000e7
Considerando a memória como um vetor, o conteúdo das diversas células seria:
...
M[0x004000b0] = 0x48
M[0x004000b1] = 0xc7
M[0x004000b2] = 0x04
M[0x004000b3] = 0x25
...
PILHA
A memória de pilha é usada para armazenar o conteúdo de variáveis bem como as
informações relativas às chamadas de procedimentos.
Ao se fazer a chamada de um procedimento, é empilhado um registro de ativação (AR de
Activation Record) , que possui informações sobre a CPU no momento da chamada, um local
para armazenar dados das variáveis locais, os parâmetros e ponteiros para controle. Ao
terminar a execução do procedimento, seu AR é desempilhado.
Fonte: EnsineMe, 2020
 Figura 4 ‒ Registro de ativação de um procedimento.
Veremos melhor o funcionamento da pilha daqui a pouco, quandoestudarmos os
procedimentos.
HEAP
A área de dados estática é utilizada para armazenar estruturas de dados de tamanho fixo, bem
como a pilha que também pode ser utilizada para esta finalidade.
 VOCÊ SABIA
Estas duas áreas, entretanto, somente podem armazenar com eficiência dados estáticos, como
variáveis escalares, vetores e matrizes. Quando são utilizadas variáveis dinâmicas (ponteiros,
filas, árvores etc.), não são o local ideal.
Para armazenar dados dinâmicos, o heap é o local mais adequado, pois consegue lidar muito
melhor com estruturas cujo tamanho podem variar ao longo do tempo de execução do
programa.
O nome desta área vem do inglês heap, que pode ser traduzido como amontoado. A ideia é
que ela se constitui em um “amontoado” de memória que pode ser utilizada para
armazenamento de dados do programa quando for solicitado.
O heap é delimitado na memória de um lado pela área de dados estática e, pelo outro, por um
endereço que marca o seu final e é armazenado no bloco de controle do processo, veja a
Figura 5.
Fonte: EnsineMe, 2020
 Figura 5 ‒ Espaço do heap.
Observe que na figura existe uma marcação do fundo do heap e do topo da pilha, cujos
endereços ficam armazenados em registradores e entre eles existe uma área de memória livre.
Desta forma, o heap pode crescer até atingir o topo da pilha ou a pilha pode crescer até atingir
o fundo do heap. Este controle, no caso do heap, é feito pela sua altura, ou seja, até que no
endereço a partir da posição inicial existam dados.
Note que o heap e a pilha crescem em sentidos contrários, um em direção ao outro.
O heap não é ocupado de forma contígua, ele pode possuir buracos, já que dados que foram
carregados podem já ter sido desalocados, o que gera blocos disponíveis entre os blocos
alocados. Nesta situação, ao ser solicitado pelo processo um espaço de n bytes para alocação
de X, normalmente o heap é gerenciado da seguinte forma:
1
Procura se existe um espaço disponível maior ou igual a n na área do heap; se existir, ele é
marcado como ocupado e é feita a alocação.

2
Se não existir, expande o heap aumentando a sua altura em “n”, marca o espaço como
ocupado e aloca a memória.
RELOCAÇÃO
Quando utilizamos o mecanismo de relocação, os endereços no módulo-objeto correspondem
a um deslocamento (offset) em relação à posição inicial do arquivo.
Quando o arquivo é carregado na memória, todos os endereços relativos devem ser ajustados
para a posição real. Para isto, os seus offsets devem ser acrescidos à posição inicial do código
na memória.
Observe a Figura 6. Nela podemos ver que no módulo-objeto existe um comando de salto que
referencia o rotulo A que está na posição 0x170, que corresponde a um deslocamento de 170
em relação à posição inicial do arquivo, que conceitualmente sempre é 0.
Quando o código é carregado a partir da posição 0x200 da memória RAM, a posição do rótulo
A corresponde ao endereço 0x370, ou seja, um deslocamento de 170 em relação ao endereço
inicial.
Observação: Um rótulo indica uma posição em um programa assembly que pode ser
referenciado em um comando de salto.
Fonte: EnsineMe, 2020.
 Figura 6 ‒ Mecanismo de relocação.
Para que a relocação funcione, o ligador deve criar uma tabela de símbolos com os rótulos e
demais elemento identificáveis, como variáveis, do arquivo objeto que devem ser relocados e
os locais onde são referenciados. O mesmo ocorre em relação a símbolos externos existentes
em outros módulos objetos.
PROCEDIMENTOS
Constituem uma das principais abstrações da maioria das linguagens de programação
modernas, permitindo a criação de um ambiente mais controlado para a execução, sendo que
cada um deles possui seu próprio espaço de armazenamento.
 SAIBA MAIS
Os procedimentos são normalmente tratados como uma unidade de trabalho básica pelos
compiladores, sendo que o compilador típico processa uma coleção deles que serão
posteriormente ligados e carregados na memória para execução.
Quando ocorre a chamada de um procedimento, o controle da execução passa para a primeira
instrução do procedimento. Ao terminar, o controle retorna ao comando seguinte ao comando
de chamada no programa chamador.
A figura 7a mostra a sequência de chamadas e a 7b o empilhamento dos registros de ativação.
Fonte: EnsineMe
 Figura 7 (A e B) ‒ Chamada e retorno de procedimentos e seu empilhamento.
Considere o programa em Pascal da figura 8 (a) extraído de Cooper e Torczon (2014), com
vários procedimentos aninhados, enquanto as Figuras 8 (b) e 8 (c) mostram o grafo de
chamadas e o histórico de execução.
Fonte: Adaptado de Cooper e Torczon, 2014.
 Figura 8 (a, b e c) ‒ Programa de exemplo em Pascal.
O grafo de chamadas mostra as possíveis chamadas entre os procedimentos. A execução de
Main pode resultar em duas chamadas a Fee, uma a partir de execução da procedure Foe e
outra a partir da procedure Fum.
O histórico de execução mostra que as duas chamadas ocorrem, sendo que cada chamada
gera o seu próprio registro de ativação.
Observe, ainda, que quando Fum chama Fee, a chamada anterior de Fee não está mais ativa.
Observe a ordem de execução, a primeira chamada ocorre em 3 e no 4 Fee termina, a próxima
chamada de Fee é no evento 6.
Para dar suporte às chamadas, é utilizado o mecanismo de pilha. Quando uma chamada é
realizada, é colocado na pilha o registro de ativação (AR de activation record) onde estão o
código e as variáveis locais do procedimento.
Como somente existe um procedimento ativo de cada vez, o último que foi chamado, seu AR,
está no topo de pilha. Ao terminar a execução, o AR é desempilhado e no topo está agora o
registro da procedure chamada imediatamente antes.
 ATENÇÃO
O registro de ativação precisa possuir informações que permitam o funcionamento correto do
programa. Normalmente, elas envolvem:
Armazenar o endereço de retorno onde o procedimento chamado possa encontrá-lo.
Mapear os parâmetros reais no local de chamada aos nomes de parâmetro formais pelos
quais são conhecidos no procedimento chamado.
Alocar espaço de armazenamento para variáveis declaradas no escopo local do
procedimento chamado.
Armazenar demais informações do contexto de execução do procedimento.
Quando um procedimento é chamado mais de uma vez, cada chamada gera um novo AR, cada
um com os dados referentes à execução de uma das instâncias do procedimento.
A Figura 9 mostra os AR de um programa chamador e de um procedimento chamado.
Fonte: Adaptado de Cooper e Torczon, 2014
 Figura 9 ‒ Exemplo de registros de ativação.
Ao analisar os AR, você pode observar que:
O AR inteiro é endereçado por meio de um ponteiro de registro de ativação (ARP –
Activation Record Pointer), com os campos no AR estando em deslocamentos positivos e
negativos a partir do ARP.
A área de parâmetros mantém os parâmetros reais na mesma ordem de aparecimento na
chamada.
A área de salvamento de registradores contém espaço suficiente para armazenar o
contexto de hardware do procedimento.
Valor de retorno armazena a valor que a procedure retornará ao chamador.
Endereço de retorno contém o endereço da instrução que deve ser executada ao terminar
a execução do procedimento.
“Endereçabilidade” mantém informações para que o procedimento possa acessar
variáveis externas a ele.
O slot ARP do chamado armazena o ponteiro ARP do chamador.
A área de dados local mantém variáveis declaradas no escopo local do procedimento
chamado.
Relembre: Contexto de hardware é o valor de cada registrador da CPU no momento que um
processo é retirado de execução.
ALOCAÇÃO DE REGISTROS DE ATIVAÇÃO
Quando um procedimento A chama um procedimento B, será necessário fazer a alocação do
AR de B na pilha para isso. O uso da pilha para esta atividade tem as seguintes vantagens:
A alocação e a desalocação não são dispendiosas, já que existe apenas uma operação
aritmética sobre o valor que registra o topo de pilha, o TOS (Top-of-Stack) .
O procedimento chamado pode estender o AR incrementando o TOS.O AR pode ser aumentado de forma incremental, visando a manter objetos de tamanho
variável.
Para saber os procedimentos ativos, basta ao sistema percorrer a pilha do topo até a
base.
A Figura 10 mostra como fazer o aumento incremental de um AR para alocar um vetor A
dimensionado dinamicamente. O que aconteceu é que o procedimento chamado copiou o
ponteiro do TOS para a área de dados locais de A e depois incrementou o ponteiro do TOS
pelo tamanho de A.
Fonte: Adaptado de Cooper e Torczon, 2014.
 Figura 10 ‒ Alocação de pilha de um array dimensionado dinamicamente.
ENTENDENDO O AMBIENTE DE EXECUÇÃO
VERIFICANDO O APRENDIZADO
1. UM PROGRAMA PODE UTILIZAR ENDEREÇAMENTO ABSOLUTO OU
RELOCÁVEL. A RELOCAÇÃO PERMITE QUE O PROGRAMA SEJA
“PAGINADO”, ENTRE DUAS EXECUÇÕES NO PROCESSADOR.
CONSIDERANDO QUE UM PROGRAMA POSSUI UMA INSTRUÇÃO DE
SALTO PARA O ENDEREÇO 1200 NO SEU CÓDIGO-OBJETO, COM A
RELOCAÇÃO, A ÁREA DE DADOS COMEÇA NO ENDEREÇO 4000, A DE
CÓDIGO NO ENDEREÇO 2000.
PODEMOS AFIRMAR QUE NO CÓDIGO RELOCADO O ENDEREÇO DO
SALTO SERÁ:
A) 1200
B) 3200
C) 5200
D) 7200
E) 4000
2. PROGRAMAS SÃO CONSTITUÍDOS DE COMANDOS E DECLARAÇÕES.
AS DECLARAÇÕES PODEM CORRESPONDER A VARIÁVEIS,
CONSTANTES, PROCEDIMENTOS E OUTROS. QUANTO A VARIÁVEIS, O
SEU NOME É ASSOCIADO A UM ENDEREÇO DE MEMÓRIA ONDE SERÃO
ARMAZENADAS.
CONSIDERE O SEGUINTE TRECHO DE CÓDIGO ASSEMBLY:
.SECTION .DATA
 A: .QUAD 0
 B: .QUAD 0
PODEMOS AFIRMAR COM CERTEZA QUE A E B SERÃO ALOCADAS:
A) Na área de código
B) No heap
C) Na pilha
D) Na área de dados estáticos
E) No código-objeto
GABARITO
1. Um programa pode utilizar endereçamento absoluto ou relocável. A relocação permite
que o programa seja “paginado”, entre duas execuções no processador. Considerando
que um programa possui uma instrução de salto para o endereço 1200 no seu código-
objeto, com a relocação, a área de dados começa no endereço 4000, a de código no
endereço 2000.
Podemos afirmar que no código relocado o endereço do salto será:
A alternativa "B " está correta.
No código-objeto, todos os endereços são relativos, correspondem a um deslocamento a partir
do início do código, ou seja, endereço 0. Como o programa foi relocado e o código começa no
endereço 2000, o deslocamento, 1200, deve ser somado ao valor inicial, 2000, o que gera o
endereço 3200.
2. Programas são constituídos de comandos e declarações. As declarações podem
corresponder a variáveis, constantes, procedimentos e outros. Quanto a variáveis, o seu
nome é associado a um endereço de memória onde serão armazenadas.
Considere o seguinte trecho de código assembly:
.section .data
 A: .quad 0
 B: .quad 0
Podemos afirmar com certeza que A e B serão alocadas:
A alternativa "D " está correta.
No heap, são armazenadas variáveis apontadas. Na pilha, dados locais de um procedimento,
na área de código, as instruções e na área de dados estática, as variáveis do programa, como
é o caso de A e B.
MÓDULO 2
 Classificar a geração de código intermediário e de montagem
GERAÇÃO DE CÓDIGO INTERMEDIÁRIO
A fase de síntese é a responsável pela geração do código de montagem. Ela começa com a
geração do código intermediário, passa pela otimização e termina com a geração de código,
conforme a Figura 11.
Fonte: EnsineMe
 Figura 11‒ Etapa de Síntese.
Apesar de conceitualmente os passos da etapa de síntese serem apresentados de forma
estanque, eles são, normalmente, executados de forma concorrente, pois, enquanto é gerado o
código intermediário, a otimização vai sendo feita e a geração do código de montagem
também.
Neste módulo, abordaremos as técnicas de geração de código (intermediário e de montagem)
e no próximo veremos os princípios que são utilizados durante a otimização.
O produto final da análise pode ser uma representação intermediária gráfica, caso a Análise
Semântica seja feita a partir da Tradução Orientada à Sintaxe, com ações semânticas
associadas às produções da gramática ou linear utilizando código de três endereços ou outra
forma similar.
Seja a partir da representação gráfica ou linear, a geração de código intermediário criará uma
representação de nível mais baixo.
REPRESENTAÇÕES INTERMEDIÁRIAS
As representações podem ser dos seguintes tipos:
HIR – HIGH INTERMEDIATE REPRESENTATION
Utilizada nos estágios iniciais da compilação, busca simplificar as construções gramaticais
mantendo apenas as que são essenciais para a continuidade da tradução. Exemplos: Árvores
de derivação e sintáticas, grafo de sintaxe e representações linearizadas.
MIR – MEDIUM INTERMEDIATE REPRESENTATION
Serve de base para a geração de códigos eficientes. Permite expressar todas as características
de uma linguagem de programação. Exemplos: Árvores de derivação anotadas, notações pós-
fixadas, código de três endereços e grafos acíclicos dirigidos (DAG).
LIR – LOW INTERMEDIATE REPRESENTATION
Dependente da arquitetura do processador, mantém uma relação de 1-1 para linguagem de
máquina. Exemplo: Código assembly.
 SAIBA MAIS
Dependendo de sua implementação, a etapa de síntese pode, no primeiro passo, gerar uma
representação do tipo MIR que será otimizada e depois transformada para a representação LIR
ou então gerar direto uma representação LIR que será otimizada.
NOTAÇÃO PÓS-FIXADA
Normalmente, utilizamos a notação infixa que coloca o operador entre os operandos, como x+y
para representar as operações. Existe, porém, outra notação denominada posfixa, onde o
operador é colocado após os operandos, por exemplo, x y +.
O grande atrativo desta notação para expressões aritméticas é dispensar o uso dos parênteses
para representar a prioridade das operações.
Observe a tabela abaixo, ela mostra as expressões na forma infixa e sua correspondente
posfixa:
INFIXA POSFIXA
a*b+c a b * c +
a*(b+c) b c + a *
(a+b)*c a b + c *
(a+b)*(c+d) a b + c d + *
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
Instruções de desvio também podem ser representadas nesta notação. Por exemplo, em
assembly, a instrução jump L que comanda um desvio incondicional para o rótulo L em posfixa
seria L jump.
Já desvios condicionais poderiam ser representados nas formas apresentadas na tabela
abaixo.
Notação posfixa Significado
x y L jeq Desvia se x e y forem iguais
x y L jne Desvia se x e y forem diferentes
x y L jlt Desvia se x for menor que y
x y L jle Desvia se x for menor ou igual a y
x y L jgt Desvia se x for maior que y
x y L jge Desvia se x for maior ou igual a y
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
Esta notação permite um uso eficiente da pilha, já que os operandos podem ser introduzidos na
pilha por instrução push e retirados por instruções pop. Além disso, a aplicação de um operador
retira os operandos da pilha e armazena o resultado no topo de pilha.
Por exemplo, a expressão a*(b+c) poderia ser traduzida em código intermediário com notação
posfixa como:
push a
push b
push c
add
mult
GERANDO CÓDIGO INTERMEDIÁRIO
A ideia do código intermediário é gerar uma representação do programa-fonte em um formato
independente da arquitetura da máquina alvo.
Vejamos alguns exemplos:
Considere o seguinte trecho de código-fonte:
 a = b + c * d;
 Ele poderia ser implementado em código intermediário como:
 _t1 := c * d
 a := b + _t1
 onde _t1 é uma variável intermediária temporária.
 
Vejamos, agora, um exemplo com instrução de desvio:
 As instruções de desvio podem ser de dois tipos:
Desvio incondicional
Possui o formato goto L, onde L é um rótulo que identifica uma linha do código.
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
Desvio condicional
Possui o formato if x opr y goto L, onde opr é um operador de comparação e L é um
rótulo que identifica uma linha do código que deve ser executada se o teste de
comparação produzir um resultado verdadeiro.
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Observe o seguinte trecho em C:
while (i++ <= k)
 x[i] = 0;
 x[0] = 0;
Uma possível tradução para código intermediário seria:
_L1: if i > k goto _L2
i := i + 1
x[i] := 0
goto _L1
_L2: x[0] := 0
Onde a penúltima linha possui um desvio incondicional que retorna para o início do loop (_L1) e
a primeira linha implementa um desvio condicional que termina o loop e salta para o primeiro
comando após o goto (_L2) se i for maior que o valor de k.
Veremos agora a tradução de procedimentos:
Como vimos no módulo anterior, a chamada de procedimento implica na geração do registro de
ativação e de sua manipulação na pilha. Estas atividades são realizadas em dois passos:
PASSO 1
PASSO 2
PASSO 1
O procedimento tem os seus argumentos do “registrador” pela instrução param.
PASSO 2
A instrução call que possui como um de seus parâmetros o nome da rotina, completa a
chamada da rotina.
Além destes dois passos, devemos destacar que a instrução return determina o fim da
execução do procedimento e faz a restauração do ponto de execução, transferindo o controle
para o comando seguinte ao da chamada do procedimento. Esta instrução pode,
opcionalmente, especificar um valor de retorno.
Considere o trecho abaixo, onde existe uma chamada da função f que recebe três argumentos
e retorna um valor:
f(a, b, c);
Como o procedimento possui três argumentos, existiriam três instruções param na mesma
sequência dos argumentos:
param a
param b
param c
Além disso, a instrução de invocação, além do nome da rotina, possui um segundo parâmetro,
que é quantidade de argumentos registrados que serão consumidos, no caso do exemplo 3, o
comando ficaria então:
... call f, 3
A instrução call tem um segundo parâmetro, que é a quantidade de elementos registrados com
param que serão consumidos pela rotina.
Resta apenas definir o armazenamento do retorno, já que é uma função que no nosso exemplo
seria colocada na variável x. A tradução completa seria então:
param a
param b
param c
x := call f,3
Vejamos outro exemplo, onde o parâmetro de uma função é o retorno de outra função.
Considere o seguinte código:
a = g (b, h(c));
Note que h é uma função cujo retorno corresponde ao segundo parâmetro de g. Sua tradução
para código intermediário seria:
param b
param c
_t1 := call h, 1
param _t1
a := call g, 2
Observe que os dois primeiros comandos registram os parâmetros b, utilizado por g e c
utilizado por h. Ao chamarmos a rotina h, ela consome o parâmetro c e retorna um valor que foi
armazenado em _t1.
Como _t1 é um parâmetro para g, ele é registrado na quarta linha e a quinta linha faz a
chamada de g, que irá consumir os dois parâmetros ainda não utilizados (b e _t1) e retornará o
valor em a.
 4. Vamos, agora, tratar do endereçamento:
O código intermediário lida normalmente com três tipos de endereçamento:
DIRETO
Modo utilizado até agora nos exemplos, ele indica o nome da variável que possui o seu
endereço armazenado na tabela de símbolos, por exemplo a:= b.
INDIRETO
Associado a variáveis que contêm endereços e utiliza operadores similares ao do C. Assim:
O operador & permite obter o endereço de uma variável.
x := &y
Atribui o endereço da variável y à variável x.
O operador * faz a operação inversa.
w := *x
Atribui o valor que está armazenado no endereço x à variável w.
Instruções que utilizam este tipo de endereçamento no programa-fonte devem ser
decompostas visando a isolar este tipo de endereçamento apenas nas operações de atribuição.
Considere o seguinte trecho onde p1 e p2 são dois ponteiros para o tipo inteiro e onde a é um
valor.
*p1 = a + *p2++;
Neste comando, o valor apontado por p2 é somado ao valor a e armazenado na posição
apontada por p1. Além disso, p2 é incrementado de uma posição. Se o tipo inteiro ocupa 4
bytes, o endereço seria então acrescido de 4.
O código intermediário gerado seria:
_t1 := *p2
p2 := p2 + 4
_t2 := a + _t1
*p1 := _t2
INDEXADO
Neste tipo de endereçamento, a posição do item é definida a partir de um deslocamento em
relação ao endereço base. Como exemplo típico, temos o acesso aos elementos de um vetor.
Desta forma, a instrução
x := y[i]
Transfere para a variável x o conteúdo do slot indicado pela soma do endereço inicial de y mais
o seu deslocamento (i).
E a instrução
x[i] := y
Armazena em x(i) o conteúdo de y.
Considere o seguinte trecho de código em C onde a e b são arranjos de inteiros:
for (i=0; i<10; ++i)
s[i] = a[i] + b[i];
Este trecho em código intermediário seria:
1 i := 0
2 _L1: if i >= 10 goto _L2
3 _t1 := 4*i
4 _t2 := a[_t1]
5 _t3 := 4*i
6 _t4 := b[_t3]
7 _t5 := _t2 + _t4;
8 _t6 := 4*i
9 s[_t6] := _t5
10 i := i + 1
11 goto _L1
12 _L2: ...
Note que o acesso aos elementos do arranjo está sendo feito em múltiplos de quatro. Analise
os comandos das linhas 3 e 4, 5 e 6, 7 e 8, isto acontece porque um inteiro, na máquina de
exemplo, ocupa 4 bytes na memória e no código intermediário o tamanho do deslocamento
deve estar em bytes. Se você quiser acessar a variável z[8] e o endereço inicial dela for 1000 (
correspondente a z[0]), você deverá acessar a posição de memória 1032 ( 1000 + 8 * 4).
GERAÇÃO DE CÓDIGO
Gerado o código intermediário e realizada a sua otimização, falta apenas gerar o código de
montagem que será submetido ao montador.
A geração deste código é totalmente dependente da arquitetura do processador alvo. A sua
quantidade de registradores e o uso possível de cada um, bem como o seu conjunto de
instruções, devem ser levados em conta e acarretam a necessidade de fazer dois tipos de
análise: A seleção de instruções e a alocação dos registradores que devem ser resolvidos
simultaneamente.
SELEÇÃO DE INSTRUÇÕES
Os processadores costumam possuir diversas instruções com finalidades semelhantes. Por
exemplo, podemos utilizar várias instruções diferentes para realizar uma soma:
Uma instrução específica para soma.
Uma instrução de incremento ou decremento (soma ±1).
 COMENTÁRIO
Cada uma destas instruções foi projetada para um uso específico, mas nada nos impede de
utilizá-las em outro contexto.
A seleção da instrução implica então em escolher a instrução mais adequada dentre as
disponíveis para a geração do código mais eficiente.
ALOCAÇÃO DE REGISTRADORES
A alocação dos registradores compreende estabelecer onde serão armazenados os dados
durante a execução (nos registradores).
 COMENTÁRIO
Existe uma hierarquia dos locais de armazenamento dos de acessos mais rápidos para os mais
lentos que, normalmente, é definida como registradores da CPU, o topo da pilha e a memória
em geral.
O acesso ao topo da pilha é considerado mais rápido que o acesso a uma posição da RAM
porque não é necessário manipular o endereço do topo da pilha, que fica em um registrador
(apontador da pilha), ao contrário de instruções que referenciam a memória onde o endereço
deve ser colocado no barramento de endereço e só depois é feita a leitura ou escrita na
memória principal.
METODOLOGIA PARA A SELEÇÃO DE
INSTRUÇÕES E ALOCAÇÃO DE
REGISTRADORES
Existem diversas estratégias que podem ser utilizadas para realizar as tarefas de seleção de
instruções e alocação de registradores. Elas serão impactadas pelo conjunto de instruções do
processador e pela arquitetura da CPU em termos de quantidade de registradores e seus
possíveis usos.
Iremos agora apresentar uma possível metodologia, que normalmente funciona bem na prática,
mas enfatizando que não é a única existente.
Para nosso estudo, vamos considerar que nosso processador possui dois registradores de uso
geral nomeados r0 e r1.
Sabendo-se que o seguinte trecho de código-fonte foi submetido ao compilador:
x = a - b + c;
y = d * e;
z = a + b + f;
w = x + y;
x = w;
O código intermediário gerado poderia ser:
t1 = a - b
t2 = t1 + c
x = t2
t3 = d * e
y = t3
t4 = a + b
t5 = t4 + f
z = t5
t6 = x + y
w = t6
x = w
Este código ainda é pouco eficiente e após o processo de otimização,eliminando expressões
redundantes etc., teríamos o seguinte código otimizado:
t1 = a - b
x = t1 + c
y = d * e
z = t1 + f
w = x + y
x = w
Para determinarmos as instruções a serem utilizadas e a alocação dos registradores,
controlaremos os valores existentes em r0 e r1 e o valores armazenados na memória para as
variáveis. Para tal, usaremos a tabela abaixo que mostra os conteúdos antes do início da
execução e após a alocação das variáveis, sendo que o valor de inicialização das variáveis a,
b, c, d, e, f correspondem aos valores que estão na memória (10, 5, 23, 3, 6, 8,
respectivamente) e L significa que o conteúdo é lixo, ou seja, não tem significado para o
programa.
Além disso, consideraremos que o processador possui o seguinte conjunto de instruções:
Comando Operação Significado
MOVE r r’ r = r’
Mover o conteúdo do registrado r para o registrador
r’
MOVE x r x = r
Mover o conteúdo do registrado r para a posição de
memória de x
MOVE r x r = x
Mover da posição de memória de x para o
registrador r
ADD r r’ r = r + r’
Realize a soma do valor do registrador r com o
valor do registrador r’ e deixe o resultado em r
ADD r x r = r + x
Leia x na memória, realize a soma com o valor do
registrador r e deixe o resultado no próprio
registrador r
SUB r r’ r = r - r’
Realize a subtração do valor do registrador r’ do
valor do registrador r e deixe o resultado em r
SUB r x r = r - x
Leia o valor de x na memória e o subtraia do valor
do registrador r, deixe o resultado no registrador r
MULT r r’ r = r * r’
Multiplique o valor do registrador r pelo valor do
registrador r’ e deixe o resultado em r
MULT r x r = r * x
Leia o valor de x na memória e o multiplique pelo
valor do registrador r, deixe o resultado no
registrador r
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
Como estratégia básica, retardaremos ao máximo transferir o valor dos registradores, atividade
denominada derramar, para as variáveis de memória.
Registradores Memória
r0 r1 a b c d e f w x y z
L L 10 5 23 3 6 8 L L L L
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
A geração passo a passo seria:
PASSO 1
PASSO 2
PASSO 3
PASSO 4
PASSO 5
PASSO 6
PASSO 7
PASSO 1
1. Começando pela instrução t1 = a – b, seu código implica em duas operações de montagem:
Mover o valor de a para o registrador r0
Move r0 a
Registradores Memória
r0 r1 a b c d e f w x y z
10 L 10 5 23 3 6 8 L L L L
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
Subtrai de r0 o valor de b
Sub r0 b
Registradores Memória
r0 r1 a b c d e f w x y z
5 L 10 5 23 3 6 8 L L L L
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
PASSO 2
A próxima instrução é x = t1 + c
Como r0 contém o resultado de t1, poderíamos realizar a soma diretamente armazenando o
resultado em r0, porém, desta forma perderíamos o conteúdo de t1 que será usado
posteriormente. Então, vamos carregar o valor de c em r1 e armazenar o resultado em r1.
Move r1 c
Registradores Memória
r0 r1 a b c d e f w x y z
5 23 10 5 23 3 6 8 L L L L
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
Add r1 r0
Registradores Memória
r0 r1 a b c d e f w x y z
5 28 10 5 23 3 6 8 L L L L
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
PASSO 3
A terceira instrução é y = d * e
Note que como nossa CPU somente possui dois registradores e eles estão com valores,
teremos que liberar um deles para poder fazer a multiplicação. Como r0 possui um valor que
será utilizado posteriormente e o valor de r1 corresponde ao valor de x que na memória está
defasado, iremos inicialmente derramar r1 para x e a.
Move x r1
Registradores Memória
r0 r1 a b c d e f w x y z
5 28 10 5 23 3 6 8 L 28 L L
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
A seguir, moveremos para r1 o valor de d
Move r1 d
Registradores Memória
r0 r1 a b c d e f w x y z
5 3 10 5 23 3 6 8 L 28 L L
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
E, finalmente, multiplicaremos r1 pelo valor de e, armazenando o resultado em r1 o valor
correspondente à variável y.
Mult r1 e
Registradores Memória
r0 r1 a b c d e f w x y z
5 18 10 5 23 3 6 8 L 28 L L
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
PASSO 4
A quarta instrução é z = t1 + f
Como t1 está em r0, e esta variável temporária não será mais utilizada, vamos usar o próprio r0
para armazenar o resultado que corresponde à variável z, vamos usar r0 para esta operação.
Add r0 f
Registradores Memória
r0 r1 a b c d e f w x y z
13 18 10 5 23 3 6 8 L 28 L L
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
PASSO 5
A quinta instrução é w = x + y
Como r1 já contém o valor de y, vamos utilizá-lo para realizar a soma, mas como y na memória
está com o valor defasado e y será sobrescrito após a soma, vamos inicialmente derramar r1
para y.
Move y r1
Registradores Memória
r0 r1 a b c d e f w x y z
13 18 10 5 23 3 6 8 L 28 18 L
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
Agora, faremos a soma de r1 com x armazenando o resultado em r1, que corresponderá ao
valor de w.
Add x r1
Registradores Memória
r0 r1 a b c d e f w x y z
13 46 10 5 23 3 6 8 L 28 18 L
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
PASSO 6
Finalmente, chegamos à última instrução x=w.
Como o valor de w está em r1, vamos derramá-lo para x.
Move x r1
Registradores Memória
r0 r1 a b c d e f w x y z
13 46 10 5 23 3 6 8 L 46 18 L
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
PASSO 7
7. Apesar de o código intermediário ter acabado, o montador ainda precisa atualizar os valores
de w e z na memória, pois atualmente eles estão apenas em r0 e r1. Para isto, seriam dados os
seguintes comandos:
Move z r0
Move w r1
Registradores Memória
r0 r1 a b c d e f w x y z
13 46 10 5 23 3 6 8 13 46 18 46
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
Agora, sim, acabou a tradução.
O código de montagem seria então:
Move r0 a 
Sub r0 b
Move r1 c 
Add r1 r0 
Move x r1 
Move r1 d 
Mult r1 e
Add r0 f
Move y r1
Add x r1
Move x r1 
Move z r0 
Move w r1
METODOLOGIA PARA A SELEÇÃO DE
INSTRUÇÕES E ALOCAÇÃO DE
REGISTRADORES
VERIFICANDO O APRENDIZADO
1. SELEÇÃO DE INSTRUÇÕES E ALOCAÇÃO DE REGISTRADOS SÃO
ATIVIDADES DESENVOLVIDAS DURANTE A GERAÇÃO DE CÓDIGO DE
MONTAGEM. A ALOCAÇÃO DE REGISTRADORES VISA A MANTER EM
REGISTRADORES DA CPU AS VARIÁVEIS MAIS UTILIZADAS PELO
PROGRAMA, DE FORMA A MINIMIZAR O ACESSO À MEMÓRIA E
EXECUTAR, PORTANTO, O PROGRAMA DE FORMA MAIS RÁPIDA.
MUITAS VEZES, DURANTE ESTE PROCESSO, É NECESSÁRIO
DERRAMAR O CONTEÚDO DE UM REGISTRADOR PARA UMA VARIÁVEL
PARA LIBERÁ-LO PARA USO DE OUTRA VARIÁVEL.
CONSIDERANDO QUE TEMOS UM REGISTRADOR “R0” E UMA VARIÁVEL
“A”, O COMANDO QUE FAZ O DERRAMAMENTO É:
A) Move a r0
B) Move r0 A
C) Load r0 A
D) Load A r0
E) Load A B
2. QUANDO FAZEMOS A GERAÇÃO DO CÓDIGO INTERMEDIÁRIO,
TEMOS QUE LIDAR COM VÁRIOS ASPECTOS DIFERENTES. ENTRE
ELES, PODEMOS CITAR O ENDEREÇAMENTO, OS PROCEDIMENTOS E
AS INSTRUÇÕES GERAIS DO PROGRAMA.
QUANTO AO ENDEREÇAMENTO, ELE PODE SER DE TRÊS TIPOS:
DIRETO
INDIRETO
INDEXADO
ANALISE AGORA OS COMANDOS ABAIXO:
*P1 := _T2
_T2 := A[_T1]
A:= B
ELES CORRESPONDEM RESPECTIVAMENTE AOS ENDEREÇAMENTOS:
A) Direto, indexado e indireto
B) Indireto, indexado e direto
C) Indexado, indireto e direto
D) Indexado, direto e indireto
E) Direto, direto e indexado
GABARITO
1. Seleção de instruções e alocação de registrados são atividades desenvolvidas durante
a geração de código de montagem. A alocação de registradores visa a manter em
registradores da CPU as variáveis mais utilizadas pelo programa, de forma a minimizar o
acesso à memória e executar, portanto, o programa de forma mais rápida.
Muitas vezes,durante este processo, é necessário derramar o conteúdo de um
registrador para uma variável para liberá-lo para uso de outra variável.
Considerando que temos um registrador “r0” e uma variável “a”, o comando que faz o
derramamento é:
A alternativa "A " está correta.
Derramar o conteúdo de um registrador é copiar o conteúdo para uma posição de memória. O
comando de cópia é o Move x r onde x é o nome da variável e r o nome do registrador.
Portanto, a resposta correta é a letra A.
2. Quando fazemos a geração do código intermediário, temos que lidar com vários
aspectos diferentes. Entre eles, podemos citar o endereçamento, os procedimentos e as
instruções gerais do programa.
Quanto ao endereçamento, ele pode ser de três tipos:
Direto
Indireto
Indexado
Analise agora os comandos abaixo:
*p1 := _t2
_t2 := a[_t1]
a:= b
Eles correspondem respectivamente aos endereçamentos:
A alternativa "B " está correta.
O endereçamento direto corresponde a fazer a referência ao nome da variável como é o caso
do comando a:= b. O endereçamento indireto utiliza ponteiros para acessar as variáveis, como
ocorre em *p1 := _t2. O endereçamento indexado corresponde ao acesso ao conteúdo de um
vetor, como ocorre no comando _t2 := a[_t1].
Portanto, a ordem correta é indireto, indexado e direto.
MÓDULO 3
 Descrever as principais técnicas de otimização de código
OTIMIZAÇÃO
A etapa de Análise do Compilador (front-end) realiza a tradução do programa-fonte para algum
tipo de representação intermediária e, a partir desta, a etapa de Síntese (back-end) produz um
código que possa ser executado em uma determinada arquitetura de máquina.
É neste processo de geração de código que surge a oportunidade de melhorar o desempenho
do programa através da otimização.
 VOCÊ SABIA
A melhoria do código gerado pode assumir diversos significados. Normalmente, otimizar
representa uma execução mais rápida, mas pode ainda significar a geração de um executável
que gaste menos energia ou consuma menos memória.
A otimização implica em realizar transformações no código, como alterar a ordem de execução
das instruções, eliminar ou substituir comandos, particionar a execução etc.
Para realizar estas transformações, o otimizador deve estar atento a dois aspectos:
Segurança
Ele deve ter certeza de que as transformações produziram o mesmo resultado do programa
original sem gerar efeitos colaterais
Lucratividade
A transformação produz um resultado melhor que o do programa original quanto à velocidade
de execução, uso de memória ou qualquer outro aspecto do desempenho do programa.
A oportunidade de otimização do código pode surgir de várias situações, como:
REDUZIR O OVERHEAD
Determinadas construções sintáticas geram um grande overhead de controle, como o suporte
em tempo de execução para o cálculo de endereços no acesso a um vetor. Os compiladores
podem, neste caso, realizar transformações para minimizar o overhead.
TIRAR PROVEITO DE CASOS ESPECIAIS
A partir do contexto da execução de um comando, o compilador pode especializar esta
operação como no caso do C++, onde o tradutor pode determinar que uma função virtual
sempre é executada a partir da mesma implementação. Neste caso, ele pode remapear os
chamados para o mesmo ponto, diminuindo o custo de cada invocação.
EQUIPARAR O CÓDIGO AOS RECURSOS DO SISTEMA
Se o programa gerado exige recursos que o processador não possui capacidade de suprir
diretamente, o otimizador pode realizar transformações no código para aproximá-lo dos
recursos disponíveis da CPU, maximizando o desempenho do programa.
ESCOPO DA OTIMIZAÇÃO
As otimizações operam em diferentes escopos, cada um deles apresentando diferentes
oportunidades aos otimizadores e utilizando métodos específicos.
Vejamos os principais tipos de escopo.
ESCOPO LOCAL
Neste escopo, os métodos de otimização operam em um único bloco básico, como todos os
comandos da seção então do comando SE.
Neste tipo de otimização, duas importantes propriedades são mantidas:
As instruções são executadas em sequência.
Se qualquer instrução for executada, o bloco inteiro será executado.
Estas duas propriedades facilitam a confirmação da segurança e lucratividade da otimização.
Desta forma, os métodos locais por fazer, muitas vezes, melhorias que não seriam obtidas em
escopos maiores, mas, por sua própria natureza, são limitados a melhorias que envolvem
operações que ocorrem no mesmo bloco.
ESCOPO REGIONAL
Os métodos deste escopo atuam em operações que transcendem um bloco, mas que não
correspondem a todo um procedimento.
 EXEMPLO
Por exemplo, os comandos pertencentes a um loop podem ser considerados uma região, note
que pode existir comando com blocos internos como o Se dentro do loop.
Em outro caso, dentro de um loop pode ser relativamente fácil provar que um determinado
ponteiro não sofre alteração ao longo da execução, embora possa ser modificado em outro
local do procedimento.
Este conhecimento pode permitir otimizações, como manter em um registrador o valor do
ponteiro, evitando operações de leitura na memória e agilizando a execução.
Este tipo de método de otimização possui vários pontos fortes dos quais podemos destacar:
A limitação de uma transformação para uma região permite que o compilador foque em
regiões bastante executadas — por exemplo, o corpo de um loop.
Podem ser aplicadas estratégias distintas para regiões diferentes.
Ao focar em uma área limitada no código, o compilador pode obter informações mais
fidedignas do funcionamento do programa, o que mostra oportunidades de melhoria.
ESCOPO INTRAPROCEDIMENTAL
O escopo aqui atinge o procedimento inteiro.
A principal motivação para utilizar este tipo de método de otimização é que decisões locais ou
regionais podem gerar uma consequência ruim em um contexto maior.
O procedimento é uma fronteira natural do programa visando à realização de análise, e
eventuais transformações geram ambientes isolados de runtime e servem, ainda, de unidades
de compilação separadas em vários sistemas.
 DICA
Métodos intraprocedimentais normalmente transformam o código do procedimento em algum
tipo de representação intermediária como um grafo. A partir desta representação, busca
identificar as regiões e os blocos, identificando quais fatos são mantidos na entrada de cada
um deles.
Desta forma, ele pode atuar individualmente em cada bloco ou região sem perder o contexto do
procedimento, realizando análises e transformações que garantam a segurança e a
lucratividade em um contexto maior que a região ou o bloco.
ESCOPO INTERPROCEDIMENTAL
Entendidos normalmente como métodos de otimização do programa inteiro, consideram todo o
código ao realizar as análises e as transformações.
Assim como mudar de um escopo local ou regional para intraprocedimental amplia as chances
de obter uma maior segurança e lucratividade, o mesmo ocorre ao passar do escopo de um
procedimento para o programa todo.
Esta elevação do escopo, ao mesmo tempo que abre novas possibilidades, também impõe
maiores desafios, como lidar com as regras de vinculação de parâmetros.
Em alguns casos, essas técnicas analisam o programa inteiro; em outros, o compilador pode
examinar apenas um subconjunto do código-fonte.
 EXEMPLO
Dois exemplos destas otimizações: Substituir a chamada de um procedimento por uma cópia
do corpo do procedimento chamado, e a propagação de constante interprocedimental, que
propaga e cruza informações sobre constantes ao longo do programa inteiro.
Uma observação importante é levar em conta a relação entre geração e otimização de código.
A otimização pode ocorrer concomitante à geração de código, como acontece na Análise
Semântica em relação ao parser.
Além disso, ela pode atuar diretamente na representação intermediária passada pela etapa de
Análise, muitas vezes eliminando ou substituindo expressões.
O que você deve notar é que, apesar de academicamente ser considerada um passo à parte
na etapa de Síntese, a otimização trabalha integrada coma geração de código, não existindo
uma separação nítida entre elas.
REALIZANDO A OTIMIZAÇÃO
Vimos os fundamentos teóricos da otimização. Veremos agora, através de um exemplo, o seu
funcionamento na prática.
Considere o seguinte código-fonte:
x = (a + b)*(c - d);
Ele deve ser compilado para uma máquina com um registrador principal, o acumulador, e que
possui as seguintes instruções:
Comando Significado
LOAD op
Leia o conteúdo de op na memória e o copie para o
acumulador
ADD op
Leia op na memória, realize a soma com o valor do
acumulador e deixe o resultado no próprio acumulador
SUB op
Leia op na memória e o subtraia do valor do acumulador,
deixe o resultado no próprio acumulador
MULT op
Leia op na memória e o multiplique como valor do acumulador,
deixe o resultado no próprio acumulador
STORE op
Copie para a posição correspondente a op na memória o valor
do acumulador
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
Considere ainda que a linguagem possui as seguintes produções em sua gramática:
S→V=E
E→E+T
E→E-T
T→T*F.
Poderiam ser geradas as seguintes representações intermediárias e código intermediário
Produção Representação Código
E→E+T
 
t1 := a + b
 
LOAD a
ADD b
STORE t1
E→E-T t2 := c - d LOAD c
SUB d
STORE t2
T→T*F
t3 := t1 * t2
 
LOAD t1
MULT t2
STORE t3
S→V=E
 
X := t3
LOAD t3
STORE x
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
Embora este código gerado esteja correto, ele está longe de ser eficiente. Isto decorre do fato
de a combinação de STORE t3 e LOAD t3 ter sido gerada por regras diferentes, porém elas
são desnecessárias. Observe que, após a realização da multiplicação, o resultado está no
acumulador, da forma como o código foi construído ele é salvo na memória, mas continua no
acumulador, de modo que fazer a sua leitura novamente, com o comando LOAD t3, é
sobrescrever o acumulador com o mesmo valor.
Podemos, então, eliminar o LOAD t3 do programa, e como o valor de t3 não é utilizado em
nenhum outro ponto, podemos também eliminar o STORE t3, o que diminui igualmente o
espaço utilizado de armazenamento na memória.
O código otimizado seria então reduzido de 11 instruções para 9, ficando assim:
LOAD a
ADD b
STORE t1
LOAD c
SUB d
STORE t2
LOAD t1
MULT t2
STORE x
Analisando um pouco mais o código, outra otimização, menos óbvia, pode ser realizada.
Como a multiplicação é comutativa, tanto faz realizar t1 * t2 ou t2 * t1, então, ao invés de
armazenar t2 , carregar t1 e só depois multiplicar por t2, como acontece no trecho:
STORE t2
LOAD t1
MULT t2
Podemos, logo após o cálculo da subtração, multiplicar diretamente por t1. Desta forma, tanto o
STORE t2 como o LOAD t2 podem ser eliminados e mudamos o operando da multiplicação
para t1.
Desta forma, o código fica:
LOAD a
ADD b
STORE t1
LOAD c
SUB d
MULT t1
STORE x
Note que é possível fazer isto porque o acumulador possui o resultado da subtração e ele, no
caso, é multiplicado pelo resultado da soma que está armazenado em t1. Aqui, novamente
usamos menos memória, já que inexiste o armazenamento de t2 e o código fica então com 7
instruções.
Quando falamos de otimização, visamos normalmente a uma maior velocidade de execução
associada a um código mais enxuto.
Este fato, entretanto, nem sempre é uma verdade absoluta, muitas vezes um código maior
pode ser mais rápido. Observe a seguinte situação:
for(i=1; i<=10; i++)
f(5*i);
Ela calcula o valor de uma função f para todos os múltiplos de 5 entre 5 e 50.
Um código maior equivalente seria:
f( 5);
f(10);
f(15);
f(20);
f(25);
f(30);
f(35);
f(40);
f(45);
f(50);
Este segundo código, quanto ao tamanho do programa, é menos otimizado, mas,
provavelmente, quanto à velocidade de execução seria mais rápido, porque dispensa as dez
multiplicações, dez operações de incremento e os onze testes de permanência do for.
De um modo geral existe uma forte correlação entre tempo de execução e tamanho do código,
porque remover instruções inúteis melhora o código. Outro fator a considerar é que instruções
mais longas possuem execução mais demorada.
 EXEMPLO
Por exemplo, carregar um valor a partir da memória é bem mais lento que carregar o valor a
partir de um registrador. Como na instrução de carga a partir da memória o endereço faz parte
da instrução e normalmente ocupa vários bytes, o tamanho da instrução também é maior, já
que o número do registrador normalmente ocupa poucos bits.
Outro exemplo envolve a decodificação de uma instrução, já que para poder ser executada,
exige que todos os seus bytes sejam transferidos para a CPU, o que aumenta o tempo quanto
mais longa for a instrução.
CÁLCULO DO CUSTO DO CÓDIGO
Uma forma de avaliar qual conjunto de instruções possui maior qualidade seria calcular o custo
de cada um deles.
Um modo de fazer isto é utilizar um modelo de custo das instruções. Imagine que temos uma
máquina com vários registradores nomeados R1, R2 etc., e as seguintes instruções com seus
respectivos custos:
Comando Custo Operação Significado
MOVE r r’ 1 r = r’
Mover o conteúdo do registrador r para
o registrador r’
MOVE x r 2 x = r
Mover o conteúdo do registrador r para
a posição de memória de x
MOVE r x 2 r = x
Mover da posição de memória de x para
o registrador r
ADD r r’ 1 r = r + r’
Realize a soma do valor do registrador r
com o valor do registrador r’ e deixe o
resultado em r
ADD r x 2 r = r + x
Leia x na memória, realize a soma com
o valor do registrador r e deixe o
resultado no próprio registrador r
SUB r r’ 1 r = r - r’
Realize a subtração do valor do
registrador r’ do valor do registrador r e
deixe o resultado em r
SUB r x 2 r = r - x
Leia o valor de x na memória e o
subtraia do valor do registrador r, deixe
o resultado no registrador r
MULT r r’ 1 r = r * r’
Multiplique o valor do registrador r pelo
valor do registrador r’ e deixe o
resultado em r
MULT r x 2 r = r * x
Leia o valor de x na memória e o
multiplique pelo valor do registrador r,
deixe o resultado no registrador r
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
A lógica da definição dos custos foi para realizar as operações; temos o custo do opcode igual
a 1, se a operação faz acesso à memória, temos o custo do acesso igual a 1, portanto
instruções que acessam a memória possuem custo 2 e as que manipulam apenas
registradores possuem custo 1.
A Tabela abaixo mostra 3 versões de código gerados para x=(a+b)*(c-d); com as novas
instruções e seus respectivos custos:
Código básico Código otimizado 1 Código otimizado 2
MOVE r0 a
ADD r0 b
MOVE t1 r0
MOVE r0 c
SUB r0 d
MOVE t2 r0
MOVE r0 t1
MULT r0 t2
MOVE t3 r0
MOVE r0 t3
MOVE x r0
MOVE r0 a
ADD r0 b
MOVE t1 r0
MOVE r0 c
SUB r0 d
MULT r0 t1
MOVE x r0
MOVE r0 a
ADD r0 b
MOVE r1 c
SUB r1 d
MULT r0 r1
MOVE x r0
CUSTO 22 CUSTO 14 CUSTO 11
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
A primeira versão corresponde ao código básico gerado pela aplicação das regras,
corresponde ao exemplo anterior, onde todas as operações são realizadas no mesmo
registrador e os valores intermediários armazenados na memória.
O código otimizado 1 corresponde à solução otimizada do primeiro exemplo, no qual somente
um valor temporário (t1) é armazenado na memória.
O código otimizado 2 utiliza mais um registrador para armazenar o resultado da soma e o da
subtração e realiza depois a multiplicação entre eles. Desta forma, todos os valores
temporários ficam em registradores, o que minimiza o acesso à memória e reduz o custo total
do código.
UTILIZANDO MULTIPROCESSAMENTO NA
OTIMIZAÇÃO
Muitos processadores modernos possuem vários núcleos que permitem a realização de
operações em paralelo. Compiladores podem realizar a otimização do seu código rearrumando-
o para tirar proveito deste recurso.
Considere que você deseja realizar a soma de oito variáveis gerando a expressão a + b +
c + d + e + f +g + h.
Em código de 3 endereços, ela seria expressa como:
t1 := a + b;
t2 := t1 + c;
t3 := t2 + d;
t4 := t3 + e;
t5 := t4 + f;
t6 := t5 + g;
t7 := t6 + h;
Que corresponderia à árvore sintática da Figura 12:
Fonte: EnsineMe
 Figura 12 ‒ Árvore sintática.
A sua execução em um processador com 4 cores seria:
 Core 1 Core 2 Core 3 Core 4
Instante 1 t1 := a + b; Não utilizado Não utilizado Não utilizado
Instante 2 t2 := t1 + c; Não utilizado Não utilizado Não utilizado
Instante 3 t3 := t2 + d; Não utilizado Não utilizado Não utilizado
Instante 4 t4 := t3 + e; Não utilizado Não utilizado Não utilizado
Instante 5 t5 := t4 + f; Não utilizado Não utilizado Não utilizado
Instante 6 t6 := t5 + g; Não utilizado Não utilizado Não utilizado
Instante 7 t7 := t6 + h; Não utilizado Não utilizado Não utilizado
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
Note que são necessárias sete unidades de tempo para a execução do código e 3 cores ficam
ociosos.
Se o compilador pudesse modificar o fluxo de execução de forma que existam operações
independentes, elas poderiam ser executadas em paralelo.
Na árvore da Figura 12, devido à forma como o fluxo está definido, somente podemos realizar a
soma de c após o resultado da soma de a e b, e assim, sucessivamente.
Considere agora outra árvore, veja a Figura 13, com um fluxo diferente:
Fonte: EnsineMe
 Figura 13 ‒ Árvore sintática.
Note que agora a soma de a e b é independente da soma de c e d, e esta da soma de e e f, e
assim, sucessivamente. Na realidade, as quatro somas que envolvem as folhas são totalmente
independentes entre si, e a soma do resultado de a+b com o resultado de c + d independe das
somas da subárvore esquerda da raiz.
Desta forma, se o código de três endereços for rearrumado, elas poderão ser realizadas em
paralelo. Um possível código seria:
t1 := a + b;
t2 := c + d;
t3 := e + f;
t4 := g + h ;
t5 := t1 + t2;
t6 := t3 + t4;
t7 := t5 + t6;
Em uma arquitetura com 4 cores, a ordem de execução poderia ser:
 Core 1 Core 2 Core 3 Core 4
Instante 1 t1 := a + b; t2 := c + d; t3 := e + f; t4 := g + h ;
Instante 2 t5 := t1 + t2; t6 := t3 + t4; Não utilizado Não utilizado
Instante 3 t7 := t5 + t6; Não utilizado Não utilizado Não utilizado
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
Observe que agora bastaram três unidades de tempo para a execução do código todo, ou seja,
menos da metade da execução anterior e a ociosidade dos cores do processador foi reduzida.
Para que isso seja viável durante a otimização, é necessário que na árvore original:
Todos os operadores sejam idênticos e correspondam a operações que sejam
comutativas e associativas.
Os nós interiores que correspondem aos operandos somente possam ser utilizados uma
vez.
REALIZANDO A OTIMIZAÇÃO
VERIFICANDO O APRENDIZADO
1. A OTIMIZAÇÃO DO CÓDIGO VISA A MELHORAR O TEMPO DE
RESPOSTA DO PROGRAMA.
PARA ISSO, SÃO REALIZADAS TRANSFORMAÇÕES, COMO TROCA DE
INSTRUÇÃO, INVERSÃO DE ORDEM, USO DE REGISTRADORES ETC.
AS OTIMIZAÇÕES PODEM SER REALIZADAS EM VÁRIOS NÍVEIS
DIFERENTES, DENOMINADOS ESCOPOS.
UM ESCOPO DEFINE A PARTE DO CÓDIGO QUE SERÁ AVALIADA E
SOFRERÁ TRANSFORMAÇÕES.
EM UM DETERMINADO ESCOPO, DUAS IMPORTANTES PROPRIEDADES
SÃO MANTIDAS:
AS INSTRUÇÕES SÃO EXECUTADAS EM SEQUÊNCIA.
SE QUALQUER INSTRUÇÃO FOR EXECUTADA, O BLOCO INTEIRO
SERÁ EXECUTADO.
QUE ESCOPO É ESTE?
A) Escopo local.
B) Escopo regional.
C) Escopo intraprocedimental.
D) Escopo interprocedimental.
E) Não foram informadas propriedades suficientes para definir o atual escopo em questão.
2. COMPUTADORES MODERNOS COSTUMAM TER PROCESSADORES
COM MÚLTIPLOS CORES, O QUE PERMITE A EXECUÇÃO DE
INSTRUÇÕES DE FORMA PARALELA, AGILIZANDO, ASSIM, A OBTENÇÃO
DA RESPOSTA.
UM TIPO DE OTIMIZAÇÃO QUE PODEMOS FAZER SERIA REORDENAR
AS OPERAÇÕES, DE FORMA QUE ELAS POSSAM SER EXECUTADAS EM
PARALELO.
CONSIDERANDO ESTA ABORDAGEM E A ÁRVORE SINTÁTICA ABAIXO,
ANALISE AS AFIRMAÇÕES:
FONTE: ENSINEME
I. UMA FORMA DE FAZER A OTIMIZAÇÃO DE CÓDIGO PARA
MULTIPROCESSADORES É DIMINUIR A ALTURA DA ÁRVORE.
II. NO CASO DA ÁRVORE APRESENTADA E CONSIDERANDO UM
PROCESSADOR DE 4 CORES, TERÍAMOS QUE SEPARAR AS
OPERAÇÕES EM 4 PARES, DE FORMA QUE PUDESSEM SER
REALIZADAS EM PARALELO.
III. O USO DESTE TIPO DE OTIMIZAÇÃO DIMINUI A OCIOSIDADE DA CPU.
ESTÁ CORRETO O QUE SE AFIRMA EM:
A) II
B) I e II
C) I e III
D) II e III
E) I, II e III
GABARITO
1. A otimização do código visa a melhorar o tempo de resposta do programa.
Para isso, são realizadas transformações, como troca de instrução, inversão de ordem,
uso de registradores etc.
As otimizações podem ser realizadas em vários níveis diferentes, denominados escopos.
Um escopo define a parte do código que será avaliada e sofrerá transformações.
Em um determinado escopo, duas importantes propriedades são mantidas:
As instruções são executadas em sequência.
Se qualquer instrução for executada, o bloco inteiro será executado.
Que escopo é este?
A alternativa "A " está correta.
No escopo local, a otimização é realizada em um bloco de comandos como a cláusula então de
um comando se. Para que a correção do código seja mantida, é necessário que estas duas
propriedades sejam mantidas.
2. Computadores modernos costumam ter processadores com múltiplos cores, o que
permite a execução de instruções de forma paralela, agilizando, assim, a obtenção da
resposta.
Um tipo de otimização que podemos fazer seria reordenar as operações, de forma que
elas possam ser executadas em paralelo.
Considerando esta abordagem e a árvore sintática abaixo, analise as afirmações:
Fonte: EnsineMe
I. Uma forma de fazer a otimização de código para multiprocessadores é diminuir a altura
da árvore.
II. No caso da árvore apresentada e considerando um processador de 4 cores, teríamos
que separar as operações em 4 pares, de forma que pudessem ser realizadas em
paralelo.
III. O uso deste tipo de otimização diminui a ociosidade da CPU.
Está correto o que se afirma em:
A alternativa "C " está correta.
Este tipo de otimização realmente implica na diminuição da altura da árvore e gerando
execução em paralelo de instruções, o que efetivamente diminui a ociosidade da CPU.
Porém, para que este tipo de otimização seja possível, é necessário que:
Todos os operadores sejam idênticos e correspondam a operações que sejam
comutativas e associativas.
Os nós interiores que correspondem aos operandos somente possam ser utilizados uma
vez.
Ao analisarmos a árvore, notamos que temos o operador de multiplicação misturado ao de
soma. Desta forma, a afirmativa II está errada.
MÓDULO 4
 Classificar o funcionamento dos montadores e dos ligadores
CÓDIGO-OBJETO
Uma vez gerado o código de montagem, após a otimização do código intermediário, o trabalho
do compilador em tese terá terminado, não é verdade?
Na prática do dia a dia, não.
Os compiladores costumam incorporar o montador para gerar o código-objeto e até o ligador
para gerar o código executável.
A Figura 14 mostra a relação entre os diversos tipos de código manipulados no processo de
gerar um arquivo executável. Ela nos mostra que o compilador trabalha com um arquivo texto
de entrada (programa-fonte) e gera um arquivo texto de saída (programa em assembly) . A
partir deste último, o montador cria o módulo objeto (arquivo binário) e o ligador gera o
módulo de carregamento, que corresponde ao arquivo binário executável.
Fonte: EnsineMe
 Figura 14 ‒ Arquivos do processo de tradução.
Neste ponto, você pode se perguntar então como o compilador interage com os outros
aplicativos.
O que você deve entender é que, para o usuário, a interação do compilador com o montador e
o ligador ocorre de forma praticamente transparente.
Na realidade, existem ainda outros aplicativos que são chamados pelo compilador como, por
exemplo, o pré-processador que tem como responsabilidade preparar o programa-fonte para a
compilação.
 EXEMPLO
Por exemplo, em um programa escritoem C++, existem as diretivas de compilação que
começam com # na primeira coluna (#define, #include etc.). Um pré-processador como o cpp,
ao encontrá-las, faz a sua substituição pela sua expansão, no caso de #define ou pelo
conteúdo do arquivo, no caso de #include. Além disso, o pré-processador faz a limpeza do
código-fonte eliminando os comentários, indentação, espaços em branco inúteis e quebras de
linha.
Após a atividade de pré-processamento, restou apenas o arquivo-fonte, em modo texto, que
passa pelas etapas de Análise e Síntese, a partir das quais é gerado o arquivo em linguagem
de montagem (assembly) do processador alvo.
A partir deste ponto, é invocado o montador que irá gerar o módulo objeto e, a seguir, é
chamado o ligador para acrescentar o código de bibliotecas e gerar o módulo de carregamento.
 ATENÇÃO
Observação: Através de diretivas, o programador pode interromper o processo antes da
montagem e gerar apenas arquivo do programa assembly, que por ser em texto puro, pode ser
lido e alterado diretamente.
MONTADORES
Ao término da etapa de Síntese, é produzido um arquivo texto contendo um programa em
assembly, equivalente ao programa originalmente descrito na linguagem de alto nível
(programa-fonte).
Um programa assembly é constituído por um conjunto de mnemônicos que correspondem às
instruções que o processador-alvo consegue executar.
O montador é o responsável por traduzir o código assembly para a linguagem de máquina do
processador, transformando os mnemônicos na sequência de bits correspondentes ao código
de operação e aos endereços do jogo de instruções da CPU.
Como você pode deduzir, cada tipo de CPU possui sua própria arquitetura e conjunto de
instruções, e os montadores, portanto, devem ser projetados especificamente para cada uma
delas.
Observação: Os exemplos de código deste módulo correspondem ao assembly da
família de processadores 68000.
POS DS.W 1
; Busca 0 na sequencia de inteiros
SRCH0 MOVEA.L #DATUM,A0 ; DATUM definido alhures 
MOVE.L #DATUM,D0 ; guarda inicio
CLR.W D1
LOOP CMP.W (A0)+,D1
BNE LOOP
SUB.L A0,D0
MOVE.W D0,POS
RTS
END
ESTRUTURA DE UM PROGRAMA ASSEMBLY
Cada linha do código assembly pode possuir instruções ou comentários.
Os comentários começam por ; como, por exemplo:
; Busca 0 na sequência de inteiros.
Já as instruções podem possuir até quatro campos.
RÓTULO
Este campo opcional serve para criar uma identificação para linha, permitindo que ela seja
referenciada, por exemplo, em uma instrução de salto, como LOOP CMP.W (A0)+,D1.
OPERAÇÃO
Corresponde a um mnemônico que define uma instrução do programa, como MOVE ou RTS ou
uma pseudo-instrução, como DS. Exemplo: SUB.L A0,D0.
OPERANDO
Dependendo da operação especificada, o montador sabe quantos operandos devem existir
(zero, um ou dois) que podem ser registradores (de dados, D0 a D7 ou de endereços AO a A7),
rótulos ou valores constantes definidos com o uso de #. Exemplo: MOVE.L #DATUM,D0.
COMENTÁRIO
Iniciado a partir do “;” após o qual todo o restante da linha pode ser ignorado pelo montador.
Exemplo: MOVE.L #DATUM,D0 ; guarda início.
PSEUDO-INSTRUÇÕES
São orientações ao montador de como tratar determinados aspectos do programa. Vejamos
algumas delas:
EQU
Associa um valor a um símbolo. Por exemplo: SIZE EQU 100 associa 100 a SIZE e todas as
vezes que size for referenciado, será substituído pelo valor 100.
DS
É similar a definir uma variável. Por exemplo: VALUE DS.W 1 corresponde a reservar espaço
uma variável chamada VALUE de tamanho 2 bytes (a letra indica o tamanho B(yte) um byte,
W(ord) dois bytes, o padrão ou L(ong word) quatro bytes).
DC
É similar a declarar uma constante. Por exemplo: CONTADOR DC.L 100 define a constante
CONTADOR de 4 bytes (note o L) com valor 100.
ORG
Determina a origem de um conjunto de palavras de máquina (segmento) que devem ser
alocadas de forma contigua na memória. Exemplo: ORG ident.
END
Indica o fim do programa – END ident.
MACRO-INSTRUÇÕES
Uma macro-instrução corresponde a um grupo de instruções que pode ser usado como se
fosse uma única instrução ao longo do código-fonte. Seu uso facilita a especificação de trechos
repetidos, que desta forma podem ser codificados uma única vez e referenciados em todos os
lugares que são usados.
PROCESSO DE MONTAGEM
O processo de montagem possui como entrada o arquivo texto com o fonte do programa
assembly e gera como saída um arquivo binário, o módulo objeto, contendo o código de
máquina e outras informações necessárias para a execução do programa.
Neste processo, inicialmente ocorre o pré-processamento, em que tudo que for não relevante
como os comentários é eliminado e as constantes são convertidas.
Além disso, as macro-instruções são processadas e o seu código é inserido no local onde elas
estavam.
Uma vez realizado este processamento, o arquivo-fonte agora possui apenas instruções e
pseudo-instruções, então está na hora de começar efetivamente a montagem.
Para tal, o montador trabalha em duas passagens no código:
PASSAGEM UM
O arquivo fonte é lido linha a linha e para cada uma delas a operação é analisada para saber
se corresponde a uma instrução ou a uma pseudo-instrução.
A partir do processamento das pseudo-instruções EQU, DC ou DS ou de instruções como
rótulos, a tabela de símbolo é atualizada.
Por exemplo, considere o seguinte código: Onde $ indica que os valores estão em hexadecimal
DADOS EQU $6000
CODIGO EQU $4000
 ORG DADOS
VALOR DS.W 1
RESULTADO DS.W 1
 ORG CODIGO
PROGRAMA MOVE.W VALOR,D0
 MOVE.W D0,RESULTADO
 RTS
 END PROGRAMA
A tabela de símbolos gerada seria:
Símbolo Valor
DADOS $6000
PROGRAMA $4000
CÓDIGO $4000
RESULTADO $6002
VALOR $6000
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
A pseudo-instrução ORG definiu dois segmentos, um chamado DADOS que começa na
posição $6000 e outro de CODIGO, começando na posição $4000.
A pseudo-instrução DS gerou a alocação de espaço no segmento para duas variáveis de dois
bytes sendo o seu conteúdo então:
Posição $6000 $6002
Conteúdo $0000 $0000
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
Note que a primeira variável VALOR está no endereço 6000 e RESULTADO em 6002, ou seja,
dois bytes depois devido ao tamanho de VALOR e com zero, já que não foram inicializadas.
PASSAGEM DOIS
Após a primeira passagem, como todos os operandos e símbolos já foram definidos, o
montador pode, processando novamente o programa linha a linha, ler as instruções e gerar o
código de máquina correspondente.
Ao processar instruções que referenciam rótulos ou que tenham operando, ele consulta a
tabela de símbolos para obter os seus endereços e os associa aos endereços dos operandos
do código de máquina.
Resumindo, para gerar o código de máquina, o montador tem que:
Obter a codificação de máquina para cada instrução
Resolver as referências simbólicas presentes nos operandos das instruções.
O processamento das instruções do nosso exemplo faz com que o código de máquina seja
carregado no segmento do programa e seu conteúdo ficaria, então, assim:
Posição $4000 $4002 $4004 $4006 $4008 $400A $400C
Conteúdo $3038 $0000 $6000 $31C0 $0000 $6002 4E75
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
Observação: Foram utilizados os códigos de operação da linguagem de máquina do 68000.
LIGADORES E CARREGADORES
O produto do montador é o módulo objeto, arquivo binário que contém parte da informação
necessária para que o programa seja executado. Porém, para que o programa possa executar,
antes de ele ser carregado na memória pelo carregador, será verificado se existe no código
referência a elementos (rotinas ou dados) externos: se existir, eles são integrados ao
executável pelo ligador.
FORMATO DO MÓDULO OBJETO
O módulo objeto possui tipicamente os seguintes componentes:
CABEÇALHO
Composto pela identificação do tipo de arquivo e dados sobre o seu tamanho.
CÓDIGOGERADO
Com as instruções e endereços em linguagem de máquinas.
RELOCAÇÃO
Contém as orientações para como fazer o carregamento na memória.
SÍMBOLOS
Contém os símbolos definidos no módulo.
DEPURAÇÃO
Contém o número de linha, estruturas de dados e nomes originais dos símbolos, bem como
outras referências para o código-fonte.
FUNÇÃO DO CARREGAMENTO
O carregamento é o ato de trazer um programa para a memória RAM e colocá-lo em execução.
Esta função é executada pelo carregador, um programa associado ao sistema operacional que,
ao receber o nome de um arquivo, executa a seguintes etapas:
Lê o arquivo.
Verifica se está no formato executável aceito pelo SO, por exemplo, exe para Windows, e
emite uma mensagem de erro se não estiver.
Faz a criação de processo para o programa.
Faz a alocação da memória para o processo.
Copia as instruções e dados para o espaço de memória alocado.
Coloca o processo na fila de prontos para execução.
A partir deste ponto, o SO, utilizando seus critérios de gerência de processador, colocá-lo-á em
execução.
MONTAGEM E CARREGAMENTO COMBINADOS
Também chamado de assemble and go (“monta e executa”), combina a montagem e o
carregamento em um único programa. Desta forma, não existe a criação do módulo objeto,
após a montagem o programa é carregado diretamente na memória e liberado para a
execução.
Para isso, algumas propriedades devem estar presentes no programa:
Ele não pode fazer referência a dados ou rotinas externas, ou seja, não existe ligação a
ser realizada.
Ele deve estar com endereçamento absoluto, portanto não existe relocação, ou seja, os
dados e código são colocados diretamente em sua posição final na memória do
computador durante a montagem.
Ao terminar a montagem, o controle de execução é transferido para a primeira instrução
executável do código de máquina gerado.
Este esquema possui duas grandes desvantagens:
A cada nova execução, o programa deve ser novamente montado, mesmo que não tenha
sofrido alteração no código.
Tanto o montador quando o programa executável deve estar na memória ao mesmo
tempo.
Este esquema é restrito a sistemas muito simples e raramente utilizado na prática.
CARREGAMENTO ABSOLUTO
Outra forma simples de carregamento que não tem as desvantagens do assemble and go
consiste em separar as duas etapas, porém ainda utilizando código absoluto, ou seja, sem usar
relocação.
 COMENTÁRIO
Neste método de carregamento, o montador gera diretamente o módulo de carregamento que
não precisa ser regenerado a cada execução. Desta forma, o montador pode ser retirado da
memória liberando espaço para a execução do programa.
Para poder funcionar neste esquema, o módulo de carregamento precisa conter, além do
código, as informações de onde cada pedaço do programa, sejam as linhas de comando ou as
variáveis, deve ser alocado na memória. Devem conter, portanto, os endereços absolutos da
memória. Outra necessidade é que o módulo não tenha referências externas, já que não irá
ocorrer a ligação.
No módulo de carregamento, para que este método funcione, devem existir registros que
associem os segmentos do código à sua posição de carga e que informem o seu tamanho em
bytes.
Existem, na realidade, dois tipos de registro:
Registro do tipo 0
Chamado também de texto, que contém as informações a serem transferidas para a memória e
sua posição de carga.
Registro tipo 1
Que indica a ocorrência do término do módulo de carregamento e que indica a posição inicial
do programa.
Considerando o código do exemplo de montagem repetido abaixo:
DADOS EQU $6000 $6000
CODIGO EQU $4000
 ORG DADOS
VALOR DS.W 1
RESULTADO DS.W 1
 ORG CODIGO
PROGRAMA MOVE.W VALOR,D0
 MOVE.W D0,RESULTADO 
 RTS
 END PROGRAMA
E as informações dos endereços onde as instruções e dados foram carregados descritos na
tabela abaixo:
Posição $4000 $4002 $4004 $4006 $4008 $400A $400C
Conteúdo $3038 $0000 $6000 $31C0 $0000 $6002 4E75
 Atenção! Para visualização completa da tabela utilize a rolagem horizontal
A organização do módulo de carregamento seria composta de três registros:
0 00006000 4 00000000
0 00004000 E 30380000600031C0000060024E75
1 00004000
Onde:
O primeiro campo de cada registro indica o seu tipo.
No caso do primeiro registro, ele indica que é do tipo texto e o conteúdo do quarto campo
(00000000) com tamanho de 4 bytes, indicado pelo terceiro campo com o número 4, deve
ser carregado na posição de memória indicada no segundo campo (00006000).
No segundo registro, também do tipo 0, indica a transferência do conteúdo
30380000600031C0000060024E75 (quarto campo) como tamanho de 14 bytes (E no
terceiro campo) para posição 00004000 (segundo campo).
O terceiro registro do tipo 1 mostra que a primeira instrução está no endereço de memória
00004000.
RELOCAÇÃO E LIGAÇÃO
Os esquemas vistos até agora, devido à sua simplicidade, não são flexíveis o suficiente para o
uso com modernos sistemas operacionais, particularmente devido à necessidade de os
montadores terem acesso direto às posições de memória, o que limita a possibilidade da
multiprogramação.
Além disto, dificilmente nos tempos atuais um programa pode prescindir do uso de bibliotecas
que possuem funções e procedimentos pré-compilados, o que exige a atividade de ligação.
Dois tipos de ajustes são então necessários no módulo objeto:
Relocação
Realizada de forma conjunta por montador e carregador. O montador deve marcar no código as
posições passiveis de alteração devido à relocação e o carregador deve reservar um espaço de
memória suficiente para receber o código de máquina e seus dados.
Ligação
Quando o módulo objeto faz referência a símbolos externos como funções ou procedimento, o
ligador junta o código-objeto destes itens ao código-objeto do programa e cria um único módulo
de carga para o carregador.
CARREGADOR DE LIGAÇÃO DIRETA
De forma similar ao que aconteceu com o montador e o carregador, esquemas iniciais de
ligação incorporam esta tarefa ao carregamento.
O carregador de ligação direta recebe como argumentos a lista de módulos a carregar e, a
partir desta, segue os seguintes passos:
PASSO 1
PASSO 2
PASSO 3
PASSO 1
Aloca na memória espaço suficiente para todos os segmentos de todos os módulos objetos e
define qual o endereço inicial de carga do programa.
PASSO 2
Cria uma tabela de símbolos externos globais com a posição dos diversos símbolos.
PASSO 3
No último passo sobre os arquivos de entrada, o carregador irá realizar a transferência do
código de máquina para a memória e transferir o controle da execução do programa para o
endereço inicial do programa recém-carregado.
LIGADOR E CARREGADOR SEPARADOS
Outra estratégia mais moderna e utilizada é separar o carregador do ligador.
O ligador recebe como entrada os diversos módulos a serem conectados, gerando um único
módulo carga que é passado ao carregador, que o transfere para a memória e realiza apenas
os ajustes de relocação, de acordo com a posição de carregamento na memória.
CARREGAMENTO E LIGAÇÃO DINÂMICOS
As estratégias de ligação e carregamento vistas até agora assumem que o programa irá
executar sozinho no computador, o sistema seria monousuário.
Sistemas modernos são essencialmente multiusuários e envolvem o uso de paginação e
memória virtual.
 COMENTÁRIO
Neste esquema, o programa pode, em um determinado momento, estar carregado em uma
posição, por exemplo, 3000, e ao sofrer paginação e ser novamente carregado, ir para a
posição 4000. Para resolver isto, foram desenvolvidas técnicas de carregamento e ligação
dinâmicas.
A ideia básica é que a referência a endereços de dados e instruções são mantidas de forma
relativa até o momento em que são necessárias para a execução do comando.
Normalmente, para obter velocidade, o hardware deve fornecer suporte para essa atividade.
Existem dois esquemas básicos para este método de ligação dinâmica:
Em tempo de carregamento (loadtime)
O módulodo programa principal é transferido para a memória. Se existir no módulo referência
a algum símbolo externo, o carregador procura o módulo alvo e o carrega na memória,
realizando o acerto dos endereços.
Em tempo de execução (runtime)
Neste método, não basta existir a referência no módulo principal, somente se a instrução que
referencia o símbolo for executada é que o carregador irá procurar o módulo e carregá-lo na
memória, fazendo o acerto dos endereços. Por exemplo, existindo na cláusula senão de um
comando se uma referência externa, caso o programa nunca passe por esta cláusula, o módulo
jamais será carregado na memória.
O PROCESSO DE MONTAGEM
VERIFICANDO O APRENDIZADO
1. O PROCESSO DE TRADUÇÃO DE UM PROGRAMA-FONTE EM UM
PROGRAMA EXECUTÁVEL ENVOLVE VÁRIAS ETAPAS, CADA UMA
DELAS RESPONSÁVEL POR UM TIPO DE ATIVIDADE, E QUE PODEM SER
REALIZADAS POR DIFERENTES PROGRAMAS, PRODUZINDO UM
DETERMINADO RESULTADO.
COMO PRODUTOS, TEMOS, ENTRE OUTROS, LISTA DE TOKENS,
ÁRVORE SINTÁTICA, CÓDIGO-OBJETO, REPRESENTAÇÕES
INTERMEDIÁRIAS, CÓDIGO INTERMEDIÁRIO, CÓDIGO EXECUTÁVEL E
CÓDIGO DE MONTAGEM.
DENTRE ESTES PROGRAMAS, QUAL O RESPONSÁVEL POR GERAR O
CÓDIGO-OBJETO?
A) Compilador
B) Ligador
C) Montador
D) Carregador
E) Ligador e montador combinados
2. DURANTE O PROCESSO DE MONTAGEM, O MONTADOR DEVE, ENTRE
OUTRAS ATIVIDADES, DETERMINAR OS ENDEREÇOS DE MEMÓRIA
ONDE SERÃO COLOCADOS OS DADOS E AS INSTRUÇÕES. PARA ISSO,
ELE UTILIZA A PSEUDO-INSTRUÇÃO ORG COMO NO EXEMPLO ABAIXO,
ONDE O ENDEREÇO INICIAL DA ÁREA DE DADOS É $6000 E DA ÁREA DE
CÓDIGO É $4000.
ORG DADOS $ 6000
ORG CÓDIGO $4000
DEPOIS DISSO, O PROGRAMA PODERÁ OU NÃO SOFRER LIGAÇÃO E
SERÁ CARREGADO NA MEMÓRIA.
CONSIDERANDO QUE UM PROGRAMA NÃO POSSUI REFERÊNCIAS
EXTERNAS E QUE SEMPRE SERÁ CARREGADO NOS ENDEREÇOS QUE
CONSTAM DE SEU CÓDIGO, PODEMOS AFIRMAR QUE A LIGAÇÃO E/OU
CARREGAMENTO MAIS SIMPLES QUE PODERÁ SER UTILIZADO PARA O
PROGRAMA É:
A) Ligação dinâmica
B) Carregamento dinâmico
C) Carregamento de ligação direta
D) Montagem e carregamento combinados
E) Montagem e ligação combinados
GABARITO
1. O processo de tradução de um programa-fonte em um programa executável envolve
várias etapas, cada uma delas responsável por um tipo de atividade, e que podem ser
realizadas por diferentes programas, produzindo um determinado resultado.
Como produtos, temos, entre outros, lista de tokens, árvore sintática, código-objeto,
representações intermediárias, código intermediário, código executável e código de
montagem.
Dentre estes programas, qual o responsável por gerar o código-objeto?
A alternativa "C " está correta.
O produto final da etapa de síntese do compilador é o código de montagem que o montador irá
transformar no código-objeto, que a seguir será ligado e transformado no programa executável
que o carregador alocará na memória.
2. Durante o processo de montagem, o montador deve, entre outras atividades,
determinar os endereços de memória onde serão colocados os dados e as instruções.
Para isso, ele utiliza a pseudo-instrução org como no exemplo abaixo, onde o endereço
inicial da área de dados é $6000 e da área de código é $4000.
Org dados $ 6000
Org código $4000
Depois disso, o programa poderá ou não sofrer ligação e será carregado na memória.
Considerando que um programa não possui referências externas e que sempre será
carregado nos endereços que constam de seu código, podemos afirmar que a ligação
e/ou carregamento mais simples que poderá ser utilizado para o programa é:
A alternativa "D " está correta.
A ligação dinâmica, o carregamento dinâmico e o carregamento de ligação direta pressupõem o
uso de relocação. Como foi dito que o programa utiliza endereçamento absoluto e não possui
referências externas, montagem e carregamento combinados, que é o método mais simples de
carga, pode ser utilizado.
CONCLUSÃO
CONSIDERAÇÕES FINAIS
Neste tema, iniciamos nosso estudo analisando o ambiente de execução de um programa.
Vimos as principais formas de geração de código, tanto do intermediário como o de montagem.
Estudamos as principais técnicas de otimização e, por último, vimos como são gerados o
módulo objeto e o programa executável.
AVALIAÇÃO DO TEMA:
REFERÊNCIAS
AHO, A. V. et al. Compiladores: Princípios, técnicas e ferramentas. 2. ed. São Paulo:
Pearson, 2008.
COOPER, K. D.; TORCZON, L. Construindo compiladores. 2. ed. Rio de Janeiro: Elsevier,
2014.
LOUDEN, K. C. Compiladores: Princípios e práticas. São Paulo: Cengage Learning, 2004.
PRICE, A. M. de A.; TOSCANI, S. S. Implementação de Linguagens – Compiladores. 3. ed.
Porto Alegre: Bookman, 2008.
RICARTE, I. Introdução à compilação. Rio de Janeiro: Elsevier, 2008.
SANTOS, P. R.; LANGLOIS, T. Compiladores: Da teoria à prática. Rio de Janeiro: LTC, 2018.
SEBESTA, R. W. Conceitos de linguagens de programação. 11. ed. Porto Alegre: Bookman,
2018.
TANENBAUM, A. S. Organização Estruturada de Computadores. 5. ed. São Paulo: Pearson,
2006.
EXPLORE+
Para saber mais sobre os assuntos tratados neste tema, pesquise na internet:
As páginas Wiki Portugal-a-Programar e Tutorialspoint.
CONTEUDISTA
Sidney Nicolau Venturi Filho
 CURRÍCULO LATTES
javascript:void(0);
javascript:void(0);