Aula 27: Seleção de Instruções

Objetivos

  • Otimizar a seleção de instruções usando Tree Covering.
  • Programação Dinâmica para custo mínimo.

Conteúdo

A expansão simples ignora o poder da CPU. Processadores CISC (e até RISC modernos com extensões) têm instruções poderosas. Ex: Multiply-Accumulate (MAC) faz a + b*c em 1 ciclo. Se usarmos expansão simples, geramos um MUL e um ADD (2 ciclos + latência).

Tree Covering (Cobertura de Árvore)

  1. Representamos a expressão IR como uma árvore.
  2. Temos uma biblioteca de “Tiles” (padrões), onde cada tile corresponde a uma instrução de máquina e tem um custo.
  3. Objetivo: Cobrir a árvore inteira gastando o menor custo acumulado.

Isto é resolvido eficientemente com Programação Dinâmica (ou geradores como BURS). O algoritmo computa o custo ótimo para cada sub-árvore (bottom-up) e decide o melhor “tile” para a raiz.

Referências

  • Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools.
  • Cooper, K., & Torczon, L. (2011). Engineering a Compiler.
Back to top