Aula 24: Análise de Fluxo de Dados

Data de Publicação

25/03/2026

Data de Modificação

08/03/2026

Objetivos

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

Motivação

O framework de Análise de Fluxo de Dados fornece uma base unificada para muitas otimizações globais. Para o engenheiro, ele oferece:

  • Uma forma sistemática de raciocinar sobre "o que sabemos" em cada ponto do programa.
  • Ferramentas para provar correção de otimizações (por exemplo, remover código morto com base em Liveness).

Conteúdo

Para otimizar além de blocos básicos (em loops, ifs), precisamos entender como os dados fluem pelo grafo de fluxo de controle (CFG) da função. A análise de fluxo de dados é um framework que responde perguntas do tipo “em cada ponto do programa, que informações podemos garantir?” por meio de equações sobre conjuntos associados a cada bloco.

Framework geral

Para cada bloco \(B\) definimos conjuntos \(IN[B]\) e \(OUT[B]\) (informação que entra e sai do bloco). A relação entre eles depende da direção da análise (para frente ou para trás) e do tipo de informação (definições que alcançam, variáveis vivas, expressões disponíveis, etc.):

\[ OUT[B] = GEN[B] \cup (IN[B] - KILL[B]) \quad \text{(forward)} \]

ou análogo para backward. \(GEN[B]\) é o que o bloco “gera”; \(KILL[B]\) é o que ele “invalida”. O algoritmo fixpoint repete até não haver mudança: inicializar \(IN\)/ \(OUT\) e atualizar usando os sucessores/predecessores até convergir.

flowchart LR
  CFG[CFG] --> Eq[Equações IN/OUT]
  Eq --> Iter[Iteração até fixpoint]
  Iter --> Result[Conjuntos por bloco]
  Result --> Opt[Otimizações]

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 (Common Subexpression Elimination).

Cada análise tem direção (forward: do início ao fim; backward: do fim ao início), conjunto de dados (definições, variáveis, expressões) e equações específicas para GEN, KILL e como combinar IN/OUT entre blocos (união ou interseção, conforme o caso).

Resumo

  • Análise de fluxo de dados responde perguntas sobre todo o CFG (não só um bloco).
  • Reaching definitions, liveness e available expressions são exemplos clássicos; cada uma alimenta otimizações específicas (constant propagation, dead code elimination, CSE).
  • O algoritmo é iterativo até fixpoint sobre as equações IN/OUT.

Referências

  • Aho et al. (2006). Compilers: Principles, Techniques, and Tools. Cap. 9 (análise de fluxo de dados).
  • Cooper & Torczon (2011). Engineering a Compiler.

Materiais da aula

Última atualização: 08/03/2026

De volta ao topo