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): 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. Redução de força e eliminação de variáveis de indução

• A saída deve ser o programa transformado. Ou seja, o programa com a transformação de expressões “fortes” em expresões “fracas” e eliminação de variáveis de indução.

3. Otimização CSE (Common Subexpression Elimination)

• 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

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

Sugestão de metodologia?

• Trabalho em duplas/individual.

• 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 ?

• 08/10 - Início do trabalho

• 29/10 e 03/11 – Implementação do Trabalho em sala de aula. Cada 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 03/11.

• 24/11 – Entrega do trabalho:

  • Entregar um relatório (conforme modelo indicado no Trabalho 1 da disciplina) indicando:

1. O que foi implementado

2. O que faltou implementar (com Justificativa)

3. Bugs/Falhas detectados e não corrigidos

4. Dificuldades encontradas durante o desenvolvimento do trabalho

5. Conclusões

Como será a avaliação?

• Conforme descrito no Trabalho 1 da disciplina

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á flexibilidade (atrasos) para entrega do trabalho.