Aula 24: Análise de Fluxo de Dados

Objetivos

  • Entender Dataflow Analysis global.
  • Calcular Reaching Definitions e Liveness.

Conteúdo

Para otimizar além de blocos básicos (em loops, ifs), precisamos entender como os dados fluem pelo grafo completo da função (CFG).

A Análise de Fluxo de Dados é um framework genérico que resolve equações iterativas sobre o grafo. Para cada bloco \(B\), temos conjuntos \(IN[B]\) e \(OUT[B]\).

\[ OUT[B] = GEN[B] \cup (IN[B] - KILL[B]) \]

Principais Análises

  1. Reaching Definitions: “A atribuição x=1 na linha 10 pode chegar até a linha 50 sem ser sobrescrita?”
    • Útil para Constant Propagation.
  2. Live Variable Analysis: “O valor de x neste ponto será lido no futuro?”
    • Direção: Backwards (do fim para o início).
    • Útil para Dead Code Elimination e Alocação de Registradores.
  3. Available Expressions: “A expressão a+b já foi calculada e não mudou?”
    • Útil para Global CSE.

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