\documentclass[a4paper,12pt,fleqn]{report}
\usepackage[portuges,brazil]{babel}
\usepackage{amssymb,amsmath,amsfonts}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}
\usepackage{euler}
\usepackage[top=30mm,bottom=20mm,left=20mm,right=20mm]{geometry}
%\topmargin -2cm \oddsidemargin -0.5cm \textwidth 16,5cm
\textheight 24cm
\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\\
RA:\hspace{3cm}Nome:\hspace{8cm}Data:}


\centerline{\bf Exame Final}


\small
\noindent
\begin{itemize}
\item[1)]\tiny{ (valor 2,0)}\small Assinale a alternativa correta (V ou F)
%\item[( )] O algoritmo de geração de código baseado em programação dinâmica deve sempre calcular o vetor de custos de uma árvore das folhas para a raíz pois, um vértice raíz de uma sub-árvore $S$ necessita dos resultados de seus descendentes para calcular seu vetor de custos.
\item[( )] Dada a expressão: $result := x + ( x + 1 ) * ( x + 1 ) - ( x + 1) * y$, a representação na forma de DAGs possui menos vértices que a representação através de uma árvore sintática. Exatamente, essa redução é de 6 vértices devido ao reuso da sub-expressão $x+1$.
\item[( )] Exemplos de ações semânticas são: verificação de tipos e inserção de símbolos da linguagem na tabela de símbolos.
\item[( )] A otimização ``Identidade Algébrica'' possibilita transformar uma expressão do tipo: $x=y+0$ em $x=y$.
\item[( )] No algoritmo de Alcance de Definições (``Reaching Definitions''), o conjunto $out$ para um bloco básico $B$ pode ser definido como: $out_B=in_B\bigcup (gen_B - kill_B)$.
\item[( )] Um GFC (ou CFG) representa apenas o fluxo de controle de um programa através de seus blocos básicos.
\item[( )] Uma das razões para a adoção de mais de uma linguagem intermediária por um compilador está na possibilidade de explorar a geração de código para mais de uma linguagem de máquina.
\item[( )] Sobre a organização da memória em tempo de execução, as variáveis globais de um programa são armazenadas no segmento de dados, as variáveis locais de procedimento são armazenadas no segmento de pilha do registro de ativação do procedimento e os dados alocados dinamicamente ficam no segmento de heap.
%\item[( )] Blocos Básicos (BBs) podem ser representados como uma lista encadeada de quadruplas.  A primeira  quadrupla tem uma flag especial tal que aponta para a quadrupla da instrução líder, um campo que aponta para o BB predecessor e outro campo que aponta para o BB sucessor. As quadruplas que representam as instruções do BB devem armazenar: 
\item[( )] Atributos herdados são sempre definidos após à execução de uma regra de produção enquanto que
atributos sintetizados são executados em meio à execução da
regra.
\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[( )] Dado o seguinte código: \begin{verbatim}int a; float b; a%b \end{verbatim}, o compilador deve informar um erro detectado através da verificação dinâmica de tipos já que o operador módulo $(\%)$ não aceita operandos do tipo float.

\item[2)]\tiny{ (valor 1,0)}\small Defina a diferença entre os algoritmos de \textit{garbage collection}: Contagem de Referências e Marcar e Varrer. Você pode utilizar exemplos para detalhar sua resposta.

%
%\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.
\newpage
\item[2)]\tiny{ (valor 1,5)}\small Gere código de três endereços para o corpo do procedimento a seguir. Obs: Não esqueça que o acesso a todo elemento de um vetor do tipo $int$ deve estar alinhado em 4 bytes.

\begin{verbatim}
void insertion_sort_rec(int *vetInt, int n){       
  int i, j, elemI;

  if ( n > 1 ) {   
    insertion_sort_rec(vetInt, n-1);
    elemI = vetInt[n-1]; 
    j = n – 1;

    while ( j >= 0 && ( vetInt[j-1] > elemI)){
      vetInt[j] = vetInt[j - 1];
      j--;
    }
    vetInt[j] = elemI;
  }
}
\end{verbatim}

%\item[2)]\tiny{ (valor 1,5)}\small Mostre o GFC (CFG) para o código a seguir. Mostre as instruções que estão dentro de cada bloco básico.
%\begin{verbatim}
%L0:
%  i=i+1
%  t1=4*i
%  if i<n goto L1
%  goto L2
%L1:
%  j=j-1
%  t2=4*j
%  if j<m goto L3
%  goto L4
%L3:
%  a[t2]=8*a[t2]
%  goto L0
%L2:
%  a[t2]=a[t2]-8
%  goto L0
%L4:
%  a[t1]=a[t1]-8
%  goto L0
%\end{verbatim}

\newpage
\item[3)]\tiny{ (valor 2,0)}\small Baseando-se no código a seguir, indique quais otimizações poderiam ser realizadas sobre o código a seguir e mostre o código final após a aplicação de cada otimização. Procure justificar por que a otimização pode (ou não) ser realizada sobre o código. 
\begin{verbatim}
s=0
i=0
L1:
if i<n goto L2
j=4*i
k=j+a
x=M[k]
s=s+x
i=i+1
goto L1
L2:
s=s/2
i=i-i
\end{verbatim}

\newpage
\item[4)]\tiny{ (valor 2,0)}\small 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 a operação de multiplicação consome 2 ciclos e as demais operações consomem apenas 1 ciclo. Informe o Delay de cada operação, e o conteúdo dos conjuntos Cand, MCands, ECand e Sched após cada passo do algoritmo.
\begin{verbatim}
p=e+2
f=2*a
c=d>>1
g=b*c
j=f*g
m=j-f
i=p<<2
t=m<<i
\end{verbatim}

\newpage
\item[5)]\tiny{ (valor 2,0)}\small Mostre a árvore de ativação junto com a pilha de
registros de ativação (considere o valor do parâmetro, o valor de retorno, o acesso às variáveis globais e as variáveis locais) para o programa a seguir. Obs: O conteúdo do procedimento $insertion\underline{ }sort$ é apresentado no exercício 2.
\begin{verbatim}
int main(void){
   int vetInt[] = { 11, 8, 10, 9, 3 };
   insertion_sort( vetInt, 5);
}
\end{verbatim}



\end{itemize}
\end{document}

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

\documentclass[12pt,fleqn]{report}
\usepackage[brazil]{babel}
\usepackage{amssymb}
\usepackage{amsmath}
%\usepackage{amsfonts}
%\topmargin -2cm \oddsidemargin .1cm \textwidth 15cm 
\textheight 24cm

\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}
