Construcción SSA (ir_ssa.rs)
Archivo: src/ir_ssa.rs (508 líneas)
¿Por qué existe?
Convierte el IR pre-SSA (producido por ir_constructor.rs) en forma SSA completa mediante dos pasos clásicos: (1) cálculo del dominator tree con el algoritmo de Cooper et al., y (2) inserción de φ-nodes con el algoritmo de pruned SSA (Cytron et al.). Esto habilita análisis y optimizaciones posteriores basados en dominancia.
Arquitectura / Estructuras clave
El módulo expone tres estructuras: el árbol de dominadores, el detector de loops naturales y el builder SSA que coloca φ-nodes.
| Componente | Descripción |
|---|---|
DominatorTree | idom[b] (dominador inmediato) y children[b]; se calcula con el algoritmo iterativo de Cooper |
DominatorTree::dominates(a, b) | Verifica si a domina a b subiendo por idom |
DominatorTree::dominance_frontier(blocks) | Calcula la dominance frontier (DF) one-pass de Cooper-Harvey-Kennedy: bloques donde el control flow puede "escapar" y juntarse |
LoopInfo | Detector de loops naturales: back_edges (donde el header domina al tail) y loops (bloques por header, vía BFS hacia atrás) |
SsaBuilder | Registra definiciones (record_def), marca variables con φ (mark_phi_variable) y computa φ-nodes |
SsaBuilder::compute_phi_nodes | Propaga los bloques de definición por la iterated dominance frontier (IDF) y coloca un φ en cada join, resolviendo los argumentos como reaching definitions en cada predecessor |
SsaBuilder::reaching_def | Resuelve la definición que alcanza a un bloque subiendo por idom hacia la raíz |
Cómo se integra
Toma el IrProgram del constructor y lo completa con información SSA (φ-nodes, dominadores) para que el optimizador y el conversor a bytecode trabajen sobre una representación bien formada. Sus tests validan diamantes (φ en el join), cadenas lineales (sin φ) y headers de loops (φ requerido).
intersect compara BlockIds directamente en vez del DFS-numbering de Cooper et al. Esto es correcto porque en Forja los bloques se crean secuencialmente con new_block() sin huecos en los IDs.