Elimine eficientemente las subexpresiones comunes en .NET Expression Tree

.net algorithm c# expression-trees optimization

Pregunta

He escrito un DSL y un compilador que genera un árbol de expresiones .NET. Todas las expresiones dentro del árbol están libres de efectos secundarios y se garantiza que la expresión sea una expresión de "no declaración" (no locales, bucles, bloques, etc.). ( Editar : el árbol puede incluir literales, accesos a propiedades, operadores estándar y llamadas a funciones, que pueden estar haciendo cosas extravagantes como la memoria interna, pero no tienen efectos secundarios externos).

Ahora me gustaría realizar la optimización "Eliminación de subexpresión común" en él.

Por ejemplo, dado un árbol correspondiente a la C # lambda:

foo =>      (foo.Bar * 5 + foo.Baz * 2 > 7) 
         || (foo.Bar * 5 + foo.Baz * 2 < 3)  
         || (foo.Bar * 5 + 3 == foo.Xyz)

... Me gustaría generar el equivalente en árbol de (ignorar el hecho de que se está ignorando parte de la semántica de cortocircuito):

foo =>
{
     var local1 = foo.Bar * 5;

     // Notice that this local depends on the first one.        
     var local2 = local1 + foo.Baz * 2; 

     // Notice that no unnecessary locals have been generated.
     return local2 > 7 || local2 < 3 || (local1 + 3 == foo.Xyz);
}

Estoy familiarizado con la escritura de visitantes de expresión, pero el algoritmo para esta optimización no es inmediatamente obvio para mí; por supuesto, podría encontrar "duplicados" dentro de un árbol, pero obviamente hay algún truco para analizar las dependencias dentro y entre los subgrupos. Árboles para eliminar las sub-expresiones de manera eficiente y correcta.

Busqué algoritmos en Google pero parecen bastante complicados de implementar rápidamente. Además, parecen muy "generales" y no necesariamente tienen en cuenta la simplicidad de los árboles que tengo.

Respuesta aceptada

Tienes razón al notar que esto no es un problema trivial.

La forma clásica en que los compiladores lo manejan es una representación de la expresión del Acyclic Directed (DAG) . El DAG se construye de la misma manera que el árbol de sintaxis abstracta (y puede construirse atravesando el AST, tal vez un trabajo para la expresión visitante; no sé mucho de las bibliotecas de C #), excepto que un diccionario de subgrafos previamente emitidos es mantenido. Antes de generar cualquier tipo de nodo dado con hijos dados, se consulta el diccionario para ver si ya existe uno. Solo si esta comprobación falla, se crea una nueva, y luego se agrega al diccionario.

Dado que ahora un nodo puede descender de varios padres, el resultado es un DAG.

Luego, el DAG se recorre en profundidad primero para generar código. Dado que las subexpresiones comunes ahora están representadas por un solo nodo, el valor solo se calcula una vez y se almacena en una temperatura para otras expresiones emitidas más adelante en la generación de código para su uso. Si el código original contiene asignaciones, esta fase se complica. Dado que sus árboles no tienen efectos secundarios, el DAG debe ser la forma más sencilla de resolver su problema.

Como recuerdo, la cobertura de los DAG en el libro del Dragón es particularmente agradable.

Como otros han señalado, si sus compiladores compilarán sus árboles en última instancia, es un tanto inútil rehacer lo que ya está allí.

Adición

Tuve algunos códigos Java de un proyecto de un estudiante (yo enseño), así que hackeé un pequeño ejemplo de cómo funciona esto. Es demasiado largo para publicar, pero vea la Gist aquí .

Ejecutarlo en su entrada imprime el DAG a continuación. Los números en parens son (id único, cuenta padre DAG). El recuento principal es necesario para decidir cuándo calcular las variables temporales locales y cuándo usar la expresión para un nodo.

Binary OR (27,1)
  lhs:
    Binary OR (19,1)
      lhs:
        Binary GREATER (9,1)
          lhs:
            Binary ADD (7,2)
              lhs:
                Binary MULTIPLY (3,2)
                  lhs:
                    Id 'Bar' (1,1)
                  rhs:
                    Number 5 (2,1)
              rhs:
                Binary MULTIPLY (6,1)
                  lhs:
                    Id 'Baz' (4,1)
                  rhs:
                    Number 2 (5,1)
          rhs:
            Number 7 (8,1)
      rhs:
        Binary LESS (18,1)
          lhs:
            ref to Binary ADD (7,2)
          rhs:
            Number 3 (17,2)
  rhs:
    Binary EQUALS (26,1)
      lhs:
        Binary ADD (24,1)
          lhs:
            ref to Binary MULTIPLY (3,2)
          rhs:
            ref to Number 3 (17,2)
      rhs:
        Id 'Xyz' (25,1)

Entonces genera este código:

t3 = (Bar) * (5);
t7 = (t3) + ((Baz) * (2));
return (((t7) > (7)) || ((t7) < (3))) || (((t3) + (3)) == (Xyz));

Puede ver que los números de var de la temperatura corresponden a los nodos DAG. Podría hacer que el generador de código sea más complejo para deshacerse de los paréntesis innecesarios, pero lo dejaré para otros.


Respuesta popular

Está haciendo un trabajo innecesario, la eliminación de la subexpresión común es el trabajo del optimizador de fluctuaciones. Tomemos tu ejemplo y miremos el código generado. Lo escribí así:

    static void Main(string[] args) {
        var lambda = new Func<Foo, bool>(foo => 
               (foo.Bar * 5 + foo.Baz * 2 > 7)
            || (foo.Bar * 5 + foo.Baz * 2 < 3) 
            || (foo.Bar * 5 + 3 == foo.Xyz));
        var obj = new Foo() { Bar = 1, Baz = 2, Xyz = 3 };
        var result = lambda(obj);
        Console.WriteLine(result);
    }
}

class Foo {
    public int Bar { get; internal set; }
    public int Baz { get; internal set; }
    public int Xyz { get; internal set; }
}

El jitter x86 generó este código de máquina para la expresión lambda:

006526B8  push        ebp                          ; prologue
006526B9  mov         ebp,esp  
006526BB  push        esi  
006526BC  mov         esi,dword ptr [ecx+4]        ; esi = foo.Bar
006526BF  lea         esi,[esi+esi*4]              ; esi = 5 * foo.Bar
006526C2  mov         edx,dword ptr [ecx+8]        ; edx = foo.Baz
006526C5  add         edx,edx                      ; edx = 2 * foo.Baz
006526C7  lea         eax,[esi+edx]                ; eax = 5 * foo.Bar + 2 * foo.Baz
006526CA  cmp         eax,7                        ; > 7 test
006526CD  jg          006526E7                     ; > 7 then return true
006526CF  add         edx,esi                      ; HERE!!
006526D1  cmp         edx,3                        ; < 3 test
006526D4  jl          006526E7                     ; < 3 then return true
006526D6  add         esi,3                        ; HERE!!
006526D9  mov         eax,esi  
006526DB  cmp         eax,dword ptr [ecx+0Ch]      ; == foo.Xyz test
006526DE  sete        al                           ; convert to bool
006526E1  movzx       eax,al  
006526E4  pop         esi                          ; epilogue
006526E5  pop         ebp  
006526E6  ret 
006526E7  mov         eax,1  
006526EC  pop         esi  
006526ED  pop         ebp  
006526EE  ret   

foo.Bar * 5 los lugares en el código donde se foo.Bar * 5 sub-expresión foo.Bar * 5 con AQUÍ. Notable es cómo no eliminó la foo.Bar * 5 + foo.Baz * 2 , la adición se realizó nuevamente en la dirección 006526CF. Hay una buena razón para eso, el jitter x86 no tiene suficientes registros disponibles para almacenar el resultado intermedio. Si observa el código de máquina generado por la fluctuación x64 y luego lo ve eliminado, el registro r9 lo almacena.

Esto debería dar suficientes razones para reconsiderar su intención. Usted está haciendo un trabajo que no necesita hacerse. Y no solo eso, es probable que genere un código peor que el que generará el jitter ya que no tiene el lujo de estimar el presupuesto de registro de CPU.

No hagas esto



Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow
Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow