\documentclass[a4paper,11pt,fleqn]{report}
\usepackage[portuges,brazil]{babel}
\usepackage{amssymb,amsmath,amsfonts}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}
\usepackage{euler}
\usepackage[top=20mm,bottom=20mm,left=20mm,right=20mm]{geometry}
%\topmargin -2cm \oddsidemargin -0.5cm \textwidth 16,5cm
\textheight 28cm
\parindent=1cm
\newcommand{\portanto}{\ensuremath{. {}^. .\;}}
\newcommand{\talque}{ \, \mid \,}
\newcommand{\nat}{\mathbb{N}}
\newcommand{\inteiros}{\mathbb{Z}}
\newcommand{\rac}{\mathbb{Q}}
\newcommand{\reais}{\mathbb{R}}
\newcommand{\complexos}{\mathbb{C}}
\pagestyle{empty}
\newcommand{\dmat}{\displaystyle}
\newcommand{\hsa}{\hspace{0.1cm}}
\newcommand{\hsb}{\hspace{0.25cm}}
\newcommand{\hsc}{\hspace{0.5cm}}
\newcommand{\hsd}{\hspace{0.75cm}}
\newcommand{\hse}{\hspace{1.0cm}}
\begin{document}
\noindent {\bf Universidade Católica Dom Bosco \\
              Curso de Engenharia de Computação \\
              Disciplina: Compiladores II\\
Professor: Ricardo Santos}\\

\centerline{\bf Lista de Exercícios No. 02}

\small
\noindent
\begin{itemize}
%\item[1)] Assinale a alternativa correta (V ou F)
%\item[( )] A verificação de tipos garante que os operandos
%associam com os tipos esperados por uma operação.
%\item[( )] As funções \textit{backpatching(), merge()} e \textit{makelist()}, adotadas na geração de código de três endereços baseada em
%\textit{backpatching}, são utilizadas, respectivamente, para: unir
%duas listas de instruções (gotos), substituir o alvo dos gotos da
%uma lista de gotos e criar uma nova lista a partir de uma
%instrução.
%\item[( )] A pilha e o heap são segmentos que cujos tamanhos
%são variáveis na memória enquanto que os segmentos de dados e
%código possuem tamanho determinado em tempo de compilação.
%\item[( )] O algoritmo de contagem de referências difere do algoritmo ``Marcar e Varrer'' na busca inicial dos objetos do heap.
%          Enquanto contagem de referências vasculha todo o Heap procurando por objetos que são apontados, Marcar e Varrer pesquisa apenas na rede de objetos alocados.
%
%\item[( )] Atributos herdados são sempre definidos em meio à execução de uma regra enquanto que
%atributos sintetizados são executados após toda a execução da
%regra e antes de sua redução.
%\item[( )] A geração de código de três endereços para um comando $break$, poderia
%ser traduzida como um $goto$ para um label fora da estrutura de
%controle $S$. Para tanto, esse $goto$ deve ser adicionado para um
%ponteiro $S.nextlist$ antes da redução de $S$. Nesse caso,
%considere que $S$ é a estrutura de controle que contém a instrução
%$break$.
%
%\item[( )] Na construção de um registro de ativação, o ponteiro $top_sp$ (ponteiro para o registro de ativação atual) aponta para o ``meio'' (mais precisamente, para o campo de informações de estado) do registrado de ativação chamado (\textit{callee}) pois é o limite
%onde o registro de ativação do invocador (\textit{caller}) sabe o
%tamanho do deslocamento.
%\item[( )] Triplas e Quadruplas são estruturas utilizadas para
%armazenar código após serem traduzidos para uma representação de
%três endereços.
%\item[( )] Variáveis dinâmicas declaradas e usadas somente em uma função $p$ podem ser
%declaradas no espaço de ``dados locais'' do registro de ativação
%de $p$ ao invés de armazena-lás no Heap.

\item[1)] Traduza o código a seguir para uma representação de três endereços
assumindo que os valores inteiros requerem 4 bytes de
armazenamento. Identifique os blocos básicos e o GFC.

\begin{verbatim}
if (i=2; i<=n; i++)
  a[i]=a[i]*10;
count=0;
s=n;
for (i=2; i<=s; i++)
  if (a[i]>100){
    count++;
    for (j=2*i; j<=n; j=j+i)
      a[j]=a[j]-10;
  }
\end{verbatim}


\item[2)] Considere a existência de uma árvore sintática para o
código a seguir. Mostre quais são as instruções de máquina para
este código tendo como base o algoritmo para seleção de instruções
baseado em matching de árvores.
\begin{verbatim}
t=a+b
u=t+c
v=u/d
\end{verbatim}

\item[3)] Execute o algoritmo de programação dinâmica para as
expressões a seguir. Considere a existência de três registradores
e as instruções de máquina definidas no exercício anterior.
\begin{verbatim}
a+b*(c*(d+e))
(a+p)*((b-q)/(c+r))
\end{verbatim}


\item[4)] Considere o programa P a seguir e utilize o algoritmo de list scheduling
para definir um escalonamento com menor quantidade de ciclos
possível. Considere que as operações de multiplicação consomem 2
ciclos e as demais operações 1 ciclo. Considere duas configurações
de processadores. No processador P1, existe apenas uma ULA
genérica que computa todas as operações. No processador P2,
existem dois multiplicadores e duas ULAs, sendo que essas computam
operações de soma, subtração e deslocamento.
% p=e+2
% i=p<<2
% t=m<<i
\begin{verbatim}
f=2*a
g=b*c
j=f*g
m=j-f
t=m<<c
\end{verbatim}

\item[5)] Otimize o código a seguir aplicando todas as otimizações
possíveis (CSE, propagação de cópias, DCE, redução em força e
eliminação de variáveis de indução). Mostre o código final e
aponte os ganhos em termos de ciclos de relógio reduzidos com as
otimizações. Considere que uma operação de multiplicação necessita
de 3 ciclos e as demais instruções são executadas em 1 ciclo.
\begin{verbatim}
dp=0
i=0
n=10
L: t1=i*8
t2=A[t1]
t3=i*8
t4=B[t3]
t5=t2*t4
dp=dp+t5
i=i+1
if i<n goto L
\end{verbatim}




\end{itemize}
\end{document}

-----------------------------------------------------------

\documentclass[11pt,fleqn]{report}
\usepackage[brazil]{babel}
\usepackage{amssymb}
\usepackage{amsmath}
%\usepackage{amsfonts}
\topmargin -2cm \oddsidemargin .1cm \textwidth 15cm \textheight
26cm
\parindent=1cm
\newcommand{\portanto}{\ensuremath{. {}^. .\;}}
\newcommand{\talque}{ \, \mid \,}
\newcommand{\nat}{\mathbb{N}}
\newcommand{\inteiros}{\mathbb{Z}}
\newcommand{\rac}{\mathbb{Q}}
\newcommand{\reais}{\mathbb{R}}
\newcommand{\complexos}{\mathbb{C}}
\newcommand{\dmat}{\displaystyle}
\pagestyle{empty}
