Trabalho Compiladores - Otimizações

Objetivo: Implementar otimizações e/ou transformações sobre o código fonte, representado em 3-end., de uma linguagem Mini Pascal.

O que deve ser implementado?

• Cada grupo (pode ser o mesmo do trabalho 1) vai escolher um dos itens a seguir para implementar.

• Para qualquer um dos itens escolhidos, deve-se implementar o algoritmo para criação de blocos básicos.

• O item escohido para implementação (junto com a criação de blocos básicos) deve tomar como entrada um arquivo com código de 3-endereços. Exemplos de códigos em 3-end. estão aqui e aqui.

• As sugestões de implementação são as seguintes:

1. Otimização DCE (Dead Code Elimination): Observe que a eliminação deve ser feita dentro de cada bloco básico. Pode ser interessante construir DAGs e fazer a eliminação a partir desses DAGs.

• A saída deve ser o programa fonte sem as expressões que foram eliminadas.

2. Otimização sobre simplificações algébricas: As simplificações devem ocorrer dentro de cada bloco básico.

• A saída deve ser o programa transformado. Ou seja, o programa com as simplificações algébricas.

3. Otimização CSE (Common Subexpression Elimination): A eliminação de subexpressões comuns deve ocorrer dentro de cada bloco básico.

• A saída deve ser o programa alterado de forma a eliminar a computação subexpressões comuns.

4. Algoritmo de alcance de definições (Reaching Definitions): Deve-se implementar aqui o algoritmo de alcance de definições (cálculo dos conjuntos in, out, gen e kill) para cada bloco básico de um programa/procedimento;

• A saída deve ser o programa separado em blocos básicos e as informações de gen, kill in e out para cada bloco básico.

5. Algoritmo de Next-Use Information: O algoritmo deve ser executado dentro de cada bloco básico.

• A saída deve ser a informação de próximo-uso para cada declaração.

6. Algoritmo para Atribuição de Registradores Simbólicos: Nesse algoritmo, deve-se analisar todos os BBs de um procedimento para que a atribuição (e uso) dos registradores simbólicos seja corretamente implementada.

• A saída deve ser o programa, cujas declarações, devem ter atribuições para os registradores simbólicos.

7. Algoritmo de List Scheduling Simples: O intuito aqui é alterar a ordem das operações, respeitando as dependências, de forma a minimizar os stalls. Nesse caso, deve-se construir DAGs para as expressões. Nesse algoritmo, deve-se analisar todos os BBs de um procedimento para que o escalonmento seja corretamente implementado.

• A saída deve ser o programa transformado. Ou seja, com a ordem das operações alteradas.

Sugestão de metodologia?

• Trabalho em duplas.

• Entendimento da otimização. Sugestão: Os livros da bibliografia básica da disciplina contém algoritmos e idéias mais detalhadas sobre as sugestões de implementação.

• Implementação do algoritmo de blocos básicos.

• Testes envolvendo a criação de blocos básicos.

• Implementação do algoritmo escolhido

• Testes envolvendo a implementação.

Qual o Cronograma ?

• 22/10 - Início do trabalho

• 23/10 – Implementação do Trabalho em sala de aula. Cada dupla/grupo deve entregar ao Professor um pequeno relatório contendo uma descrição dos algoritmos que serão implementados e o estágio atual de desenvolvimento. A entrega deve ser ao final da aula do dia 23/10.

• 20/11 – 1o. Checkpoint: Cada dupla deve apresentar sua versão da implementação. Recomenda-se fortemente que o algoritmo de blocos básicos e a otimização escolhida já tenham sido implementados.

• 26/11 – Entrega do trabalho (uma semana após a prova):

  • Entregar um relatório indicando:

1. O que foi implementado

2. O que faltou implementar

3. A sintaxe para execução da ferramenta

4. Bugs/Falhas detectados e não corrigidos

5. Dificuldades encontradas durante o desenvolvimento do trabalho

6. Conclusões

• Enviar o código fonte da ferramenta, o respectivo arquivo executável e um arquivo de entrada (testbench) para execução.

Como será a avaliação?

• A avaliação da ferramenta constará da avaliação parcial do checkpoint (o checkpoint terá peso 1);

• da avaliação do(s) documento(s) e software(s) entregue(s) (peso 2);

• da avaliação final de todo o programa de acordo com a abrangência para com todos os testsbenchs (peso 5);

• Bônus (peso 2): organização e documentação do código, arquivo README, scripts para configuração e execução, clareza na explicação do relatório;

Dicas/Sugestões

• Procure entender cada um dos algoritmos que devem ser implementados. Faça testes com lápis e papel. Isso ajuda a entender o funcionamento do algoritmo e detectar casos de exceção.

• Inicie o trabalho o quanto antes. O tempo voa! Veja o caso do Trabalho 1!

• Documente o código. Isso ajudará a relembrar o que estava sendo feito no dia anterior e, principalmente, depurar o código em caso de bugs.

• Participe e procure motivar a participação do outro colega da dupla na implementação. Se possível, troquem as atividades durante o desenvolvimento do trabalho.

Perguntas frequentes:

Consulte – Atribuição do Trabalho 1 na página da disciplina. ATENÇÃO: Preste atenção nos prazos, não há muita flexibilidade para entrega do trabalho.