Otimização por análise de fluxo - Compiladores - Exercícios

Prévia do material em texto

Otimização por análise de fluxo - Compiladores
Exercícios
1. A tarefa de otimização de código traz à tona diversas questões que devem ser
levadas em consideração. Inúmeros fatores podem contribuir na complexidade das
análises realizadas quanto ao fluxo de dados e de controle na otimização. Por isso,
definir as melhores técnicas a serem utilizadas nem sempre é uma tarefa fácil. Além
disso, sempre é preciso ficar atento ao objetivo final do programa quando se está
realizando a otimização de código.
Leia as afirmações a seguir sobre os cuidados que devem ser tomados no
momento de realizar as otimizações nos códigos:
I. Modificações que possam ter impacto prejudicial no código objeto devem ser
evitadas, pois a intenção da otimização é melhorar o desempenho do código,
conservando a essência do programa. 
II. As trocas de comandos (como realizar a transformação de while pelo if) nos
códigos intermediários devem ser evitadas, pois podem prejudicar o significado
dos códigos originais.
III. O empenho aplicado para otimizar os códigos deve ser satisfatório e estimável,
ou seja, algo que possa ser medido, garantindo otimização adequada e satisfatória.
Assinale a alternativa que contém as assertivas corretas:
Resposta correta.
C. apenas I e III.
As   afirmações   I   e   III   estão   corretas,   pois   tratam   de   questões   pertinentes
aos cuidados que devem ser tomados no momento de aplicar as otimizações,
como preservar o significado do programa original e medir o quanto a
otimização pode ser eficiente. Já a afirmação II não está correta, pois utiliza um
exemplo   que   não   se   aplica   na   situação   de   transformações   dos   códigos
intermediários, tendo em vista que a troca dos comandoswhile pelo ifpode ocorrer
no momento da geração de códigos intermediários para realizar otimizações.
2. A otimização, levando em consideração a análise de fluxo de controle, é
responsável pelo comportamento do código em relação aos laços e às repetições,
algo crucial no momento de otimizar os códigos intermediários. As análises podem
ser realizadas pelos blocos básicos de forma global ou local, e a representação da
estrutura de um código pode ser realizada por meio de grafos de fluxo de controle.
Uma das técnicas que podem ser aplicadas na análise de fluxo de controle é a
_________________, que apresenta como objetivo realizar a transformação de
variáveis que mudam constantemente a cada iteração. Esse tipo de variável pode
ser encontrado nos acessos a vetores e matrizes.
Leia as alternativas e assinale a que preenche a lacuna de forma correta:
Você acertou!
B. simplificação de variáveis de indução.
Quando   são   utilizadas   propriedades   algébricas   na   otimização,   a   redução   de
capacidade realiza substituições de operadores de alto custo por operadores mais
simples. As variáveis de indução, da simplificação de variáveis de indução, mudam
constantementeem cada iteração, pois estão presentes, geralmente, nos acessos
a   vetores   e   matrizes   e,   assim,   podem   ser   transformadas. Assim, uma das
técnicas que podem ser aplicadas na análise de fluxo de controle é a
simplificação de variáveis de indução. Quando um bloco de instruções não tem
a possibilidade de ser executado, é possível aplicar a eliminação de código morto.
Expressões   que   estão   presentes   nos   laços   e   não   se   modificam   ao   longo   da
execução podem ser analisadas pela  técnica de movimentação de código.  E a
eliminação de desvios desnecessários trata de instruções de desvios que não são
necessários, pois geralmente não são executados e, assim, podem ser eliminados.
3. Um bloco básico pode ser analisado de forma local ou global quando se está
realizando otimização no código. A análise de fluxo de dados procura verificar
variáveis e expressões presentes nos blocos básicos a fim de aplicar técnicas para
melhorar o desempenho.
Assinale a alternativa correta quanto à análise de fluxo de dados.
Você acertou!
D. A  análise   de   variáveis   diferentes,   mas   que   têm   valores   iguais,   pode   ser   realizada,
tendo em vista que essas variáveis podem ser eliminadas posteriormente, contribuindo na
otimização.
A   eliminação   de   expressões   repetidas   pode   ser   definida   como   a   técnica   de
eliminação de código redundante, mas ela não pode ser eliminada de imediato,
pois primeiramente a análise de fluxo de dados verifica se essa expressão não é
utilizada posteriormente com outros valores atribuídos. A comunicação entre os
blocos básicos é permitida pelas variáveis e expressões dos conjuntos de entrada
(in) e saída (out) entre os blocos básicos, e não os predecessores (pred) e seus
sucessores (succ). Os grafos acíclicos dirigidos (DAG) têm como foco analisar a
sequência das instruções, facilitando a descoberta de subexpressões comuns, por
exemplo.  As expressões chamadas de available não precisam ser recalculadas,
pois estão sempre disponíveis. A propagação de cópias é a técnica que verifica
que variáveis diferentes são utilizadas com os mesmos valores e, assim, podem
ser   eliminadas   posteriormente.  Assim, a análise de variáveis diferentes, mas
que têm valores iguais, pode ser realizada, tendo em vista que essas
variáveis podem ser eliminadas posteriormente, contribuindo na otimização.
4. A análise de fluxo de controle e de dados na otimização de códigos
intermediários pode ser feita de maneira conjunta para melhorar o desempenho,
sempre visando a contribuir positivamente na geração do código, tendo como
princípio a aplicação de diferentes técnicas para tal.
Observe a expressão a seguir em linguagem C:
y[i] = x[i] * x[i-1]
Levando em consideração que todas as variáveis são do tipo inteiro, o bloco de
instruções em código intermediário de três endereços ficaria desta forma:
Linha 1 ➔ _t1 := 4 * i
Linha 2 _t2 := i - 1➔
Linha 3 _t3 := 4 * _t2➔
Linha 4 _t4 := 4 * i➔
Linha 5 y[_t4] := x[_t1] * x[_t3]➔
Assinale a alternativa correta que apresenta as técnicas que podem ser aplicadas
para otimizar esse trecho de código.
Você acertou!
B. Identidades aritméticas e eliminação de subexpressões comuns.
Nesse trecho de código, a técnica de movimentação de código não pode ser 
aplicada, pois não são expressões que estão presentes em laços. A eliminação 
de desvios desnecessários trata de instruções de desvios, não sendo 
adequada a esse trecho de código. A eliminação de código morto também não 
pode ser aplicada, tendo em vista que se refere a um bloco de 
instruções que não tem a possibilidade de ser executado. Entre as 
propriedades algébricas está a redução de capacidade, que troca operadores 
mais complexos por mais simples, mas, nesse caso, não há essa possibilidade.
Para realizar a otimização do trecho de código, as técnicas que podem ser 
aplicadas são identidades aritméticas(linha 2) e eliminação de subexpressões
comuns (linhas 1 e 4).
Observe como fica o trecho de código intermediário otimizado:
_t1 := 4 * i
_t2 := _t1 - 1
y [_t1] := x[_t1] * x[_t2]
5. O grafo de fluxo de controle é uma ferramenta muito importante na análise de
fluxo de controle, pois possibilita não só realizar uma representação gráfica da
estrutura dos blocos básicos, mas também representa as dependências entre eles.
A partir disso, a aplicação de técnicas pode ser facilitada nos códigos
intermediários.
Leia as afirmativas a seguir, que tratam da construção dos grafos de fluxo de
controle, e classifique-as em verdadeiras (V) ou falsas (F).
( ) Cada bloco básico pode ser atribuído a uma aresta dirigida que representa as
instruções de saltos para outros vértices.
( ) Saltos condicionais e incondicionais apresentam duas arestas (condições
verdadeiras ou falsas), mas, quando não há saltos de instruções, é atribuída apenas
uma aresta.
( ) Os vértices representam cada bloco básico, e as arestas, as instruções de saltos
(podendo ser condicional ou incondicional).Assinale a alternativa que apresenta a ordem correta das afirmativas:
Você acertou!
C. F – F – V.
Para   a construção dos grafos de fluxo de controle, é   necessário   levar   em
consideração   que   os vértices representam   cada bloco básico, e
as arestas, as instruções de saltos (podendo ser condicional ou incondicional).
Quando   há saltos condicionais, duas   arestas   são   lançadas   (condições
verdadeiras ou falsas), mas, se os saltos são incondicionais ou sem saltos, há
apenas   uma   aresta.   Os   vértices   que   não   têm   arestas   representam   blocos
com instruções de retorno de funções.
	Otimização por análise de fluxo - Compiladores
	Exercícios