El problema fundamental que aborda el aegraph en Cranelift es la "pass-ordering problem" en compiladores, donde la aplicación secuencial de pases de optimización (como GVN, LICM, propagación de constantes y eliminación de cargas redundantes) puede requerir múltiples iteraciones para alcanzar un punto fijo, o incluso fallar en encontrar la solución óptima debido a interacciones complejas. Este desafío clásico en la ingeniería de compiladores surge porque las optimizaciones, al ser algoritmos de grano grueso y separados, no pueden entrelazarse de manera fina para explotar todas las oportunidades de mejora.

La solución propuesta es un marco unificado que razona sobre todas las posibles reescrituras de manera integrada y las intercala a una granularidad fina. Esto se logra mediante una representación intermedia del programa que combina un "sea-of-nodes" para operaciones puras con el Control Flow Graph (CFG) para instrucciones con efectos secundarios. Esta aproximación permite aplicar optimizaciones como la canonicalización, el movimiento de código y las reescrituras algebraicas en un único bucle de punto fijo, eliminando la necesidad de múltiples pases y el problema de su ordenación heurística. La motivación actual para esta evolución radica en la búsqueda de mayor eficiencia y calidad de código en compiladores JIT como Cranelift, donde el tiempo de compilación es crítico pero la calidad del código generado también es importante.

Arquitectura del Sistema

La arquitectura del optimizador mid-end de Cranelift se basa en una representación intermedia denominada "sea-of-nodes-with-CFG". Esta representación descompone el programa en dos partes: un esqueleto de Control Flow Graph (CFG) que contiene las instrucciones con efectos secundarios (impure operations) y un "mar de nodos" (sea-of-nodes) para las operaciones puras (side-effect-free). Las operaciones puras se "levantan" del CFG y se canonicalizan mediante hash-consing, donde la identidad de un nodo se define por su contenido superficial y sus operandos ya canonicalizados. Esto asegura que computaciones idénticas se fusionen en una única instancia, logrando Global Value Numbering (GVN) de forma implícita.

Las reescrituras se aplican de forma "eager" (ansiosa) y recursiva a medida que se construyen los nodos en el sea-of-nodes. En lugar de una reescritura destructiva, se utiliza un "union node" para representar múltiples formas equivalentes de una expresión, formando un "aegraph" (e-graph acíclico). Esta estructura mantiene la aciclicidad del grafo, lo que permite un algoritmo de una sola pasada para las reescrituras. El lenguaje DSL ISLE (Instruction Selection and Lowering Expressions) se utiliza para definir las reglas de reescritura. La fase de "elaboración" revierte el proceso, volviendo a insertar los nodos puros en el CFG. Esta elaboración es "scoped" y basada en la demanda, utilizando un recorrido pre-orden del Dominance Tree (domtree) y un hashmap con "overlays" para gestionar los ámbitos de las definiciones. Esto permite la eliminación de código muerto (DCE) y el movimiento de código invariante de bucle (LICM) de forma natural, y ofrece puntos de extensión para rematerialización y scheduling de código para optimizar el uso de registros. La extracción de la mejor representación de un e-class se realiza mediante un algoritmo de programación dinámica que ignora la subestructura compartida para mantener la eficiencia, procesando los nodos de abajo hacia arriba en el grafo acíclico.

Flujo de Optimización Mid-End con Aegraph

  1. 1 CLIF (SSA CFG) IR de entrada con Control Flow Graph y SSA
  2. 2 Canonicalize & Rewrite Levantar operaciones puras, hash-consing, aplicar reescrituras eager y crear ...
  3. 3 Sea-of-Nodes-with-CFG Representación intermedia con esqueleto CFG y grafo acíclico de nodos puros
  4. 4 Scoped Elaboration Reinsertar nodos puros en el CFG, aplicando DCE, LICM y rematerialización
  5. 5 CLIF (SSA CFG) IR optimizado de salida
CapaTecnologíaJustificación
data-processing Aegraph (Acyclic E-Graph) Estructura de datos central para representar y optimizar expresiones puras, permitiendo múltiples representaciones equivalentes y reescrituras eager. vs Clásicos e-graphs (e.g., egg framework), Pases de optimización destructivos secuenciales
data-processing ISLE DSL Lenguaje de dominio específico para definir reglas de reescritura de patrones, utilizado para las optimizaciones algebraicas y otras transformaciones. vs Implementación manual de reglas de reescritura, Otros DSLs de reescritura de grafos
data-processing Hash-consing Técnica para canonicalizar y deduplicar nodos de operaciones puras en el 'sea-of-nodes', asegurando que computaciones idénticas se representen una sola vez. vs Comparación profunda de árboles de expresiones, Global Value Numbering (GVN) explícito
data-processing Dominance Tree (Domtree) Estructura de datos del CFG utilizada para guiar la canonicalización y la elaboración de nodos, asegurando el orden correcto de procesamiento y la validez de SSA. vs Recorridos arbitrarios del CFG, Análisis de flujo de datos más complejos

Trade-offs

Ganancias
  • ▲ Calidad del código generado (tiempo de ejecución)
  • ▲ Unificación de optimizaciones (GVN, LICM, DCE, reescrituras)
  • ▲ Eliminación del problema de ordenación de pases
Costes
  • △ Tiempo de compilación
  • ▲ Complejidad de la implementación del optimizador 
def canonicalize_and_rewrite(basic_block):
  for inst in basic_block:
    if is_pure(inst):
      # ... (manejo de hashcons_map)
      else:
        optimized = rewrites(inst) # NEW: Aplicar reescrituras
        union = join_with_union_nodes(inst, optimized) # NEW: Unir original y optimizado
        optimized_form[inst.def] = union
    else:
      # ... (manejo de insts impuras)
Muestra cómo se integran la reescritura eager y la creación de union nodes en el proceso de canonicalización de un basic block.
def elaborate_domtree(bb, scope):
  demand_based_elaboration(bb, scope)
  for child in domtree.children(bb):
    subscope = { map = {}, parent = scope }
    elaborate_domtree(child, subscope)

def find_in_scope(value, scope):
  if value in scope.map:
    return scope.map[value]
  elif scope.parent:
    return find_in_scope(value, scope.parent)
  else:
    return None
Ilustra cómo se usa un ámbito jerárquico (scope) para la memoización durante la elaboración, evitando la duplicación de cómputos y manteniendo la validez de SSA.

Fundamentos Teóricos

El problema de la ordenación de pases en compiladores es un tema clásico en la investigación de compiladores, abordado por décadas de literatura. La idea de un "sea-of-nodes" como representación intermedia tiene raíces profundas en trabajos como el de Click y Cooper (1995) sobre el compilador de Java HotSpot, que utiliza una representación de grafo de dependencia para optimizaciones. La canonicalización mediante hash-consing es una técnica estándar en sistemas que manejan expresiones simbólicas, como se describe en "Functional Programming with Arbitrary Precision Integers" de John Harrison (1996).

La estructura de datos e-graph, y el concepto de "equality saturation" que permite representar y explorar múltiples equivalencias de un programa, fue popularizada por el paper "egg: Fast and Extensible Equality Saturation" de Max Willsey et al. (2021). Este trabajo revitalizó el interés en los e-graphs para la optimización de compiladores y la síntesis de programas. El aegraph de Cranelift es una adaptación de estos principios, buscando la eficiencia necesaria para un compilador JIT al imponer la aciclicidad y la reescritura "eager", lo que lo diferencia de la formulación clásica de "equality saturation" que puede generar ciclos y requiere un paso de "rebuild" más costoso. La extracción de la mejor expresión de un e-graph, que se demuestra ser un problema NP-hard (relacionado con el Weighted Set Cover), es un desafío bien conocido en la teoría de la optimización combinatoria.