expresiones - funciones anonimas c#

Eliminar eficientemente sub-expresiones comunes en.NET Expression Tree

Question

Escribí un DSL y un compilador que genera un árbol de expresiones .NET a partir de él. Todas las expresiones dentro del árbol están libres de efectos secundarios y se garantiza que la expresión sea una expresión "sin enunciado" (sin 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 sofisticadas como la memoria interna, pero externamente no tienen efectos secundarios).

Ahora me gustaría realizar la optimización de "Eliminación de sub-expresión común".

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

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 árbol equivalente de (ignore el hecho de que algunas de las semánticas de cortocircuito están siendo ignoradas):

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 expresiones, pero el algoritmo para esta optimización no es inmediatamente obvio para mí. Por supuesto, pude encontrar "duplicados" dentro de un árbol, pero obviamente hay algún truco para analizar las dependencias dentro y entre subtemas. árboles para eliminar 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 en cuenta.

Answer 1

1. Haga un SortedDictionary<Expression, object> que pueda comparar Expression arbitrarias s.
   (Aquí puede definir su propia función de comparación arbitraria; por ejemplo, puede comparar lexicográficamente los tipos de las expresiones, y si son iguales, puede comparar los niños uno por uno).

2. Revise todas las hojas y agréguelas al diccionario; si ya existen, entonces son duplicados, así que combínalos.
   (Este es también un buen momento para emitir código, como crear una nueva variable, para esta hoja, si es la primera instancia de la misma, luego puede almacenar el código emitido dentro del valor del object en el diccionario).

3. Luego revise los padres de todas las hojas anteriores y agréguelos al diccionario; si ya existen, entonces son duplicados, así que combínalos.

4. Sigue subiendo de nivel por nivel hasta que llegues a la raíz.

Ahora sabe qué son todos los duplicados y dónde ocurren, y ha generado código para todos ellos.

Answer 2

Descargo de responsabilidad: nunca he abordado un problema como este, solo estoy lanzando una idea que parece razonablemente eficiente:

Para cada nodo en el árbol tiene algún tipo de firma. Un hash debería hacer, las colisiones se pueden resolver. La firma debe asignar todas las entradas de Foo.Bar al mismo valor.

Recorre el árbol (O (n)) construyendo una lista de firmas de nodos INTERNOS (ignorar hojas), ordena una clave combinada del tamaño de la expresión y luego la firma (O (n log n)). Tome el elemento más común de la expresión más pequeña en la lista (O (n)) y reemplace la expresión con una variable local. (Verifique que sean realmente compatibles en este momento, en caso de que tengamos una colisión hash. B)

Repita esto hasta que no logre nada. Esto no puede ejecutarse más de n / 2 veces, limitando así toda la operación a O (n ^ 2 log n).

Answer 3

Está haciendo un trabajo innecesario, la eliminación común de sub-expresiones es el trabajo del optimizador de jitter. Tomemos su 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 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 la sub-expresión foo.Bar * 5 fue eliminada con AQUÍ. Notable es cómo no eliminó la sub-expresión de 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 intermediario. Si observa el código de máquina generado por el jitter x64, entonces lo ve eliminado, el registro r9 lo almacena.

Esto debería dar suficientes razones para reconsiderar su intención. Estás 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 del registro de la CPU.

No hagas esto

Answer 4

Estoy de acuerdo con hans-passant sobre la practicidad de hacer esto. Sin embargo, si está investigando esto académicamente, puede interesarle el algoritmo de Quine-McCluskey. Tenga cuidado con este es un problema muy complejo. Mathematica tiene un optimizador de expresiones multiusos muy agradable y, dependiendo de tus necesidades, puedes usarlo, por ejemplo, si le das tu expresión :

(foo.Bar = A, foo.Baz = B, foo.Xyz = X)

Answer 5

Estás en lo correcto al notar que este no es un problema trivial.

La forma clásica en que los compiladores lo manejan es una representación de Gráfico Dirigido Acíclico (DAG) de la expresión. El DAG se construye de la misma manera que el árbol sintáctico abstracto (y se puede construir atravesando el AST, quizás un trabajo para el visitante de la expresión, no conozco muchas bibliotecas C #), excepto que un diccionario de subgrafos emitidos previamente es mantenido. Antes de generar cualquier tipo de nodo dado con niños dados, se consulta el diccionario para ver si ya existe uno. Solo si esta verificación falla, se crea una nueva y luego se agrega al diccionario.

Como ahora un nodo puede descender de múltiples padres, el resultado es un DAG.

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

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

Como otros han notado, si tus árboles finalmente serán compilados por un compilador existente, es inútil rehacer lo que ya está allí.

Adición

Tenía un código Java de un proyecto de estudiante (enseño) por lo que he pirateado un pequeño ejemplo de cómo funciona esto. Es demasiado largo para publicar, pero vea el Gist aquí .

Al ejecutarlo en su entrada imprime el DAG a continuación. Los números en parens son (identificación única, recuento de padres DAG). El recuento de los padres es necesario para decidir cuándo calcular las variables temporales locales y cuándo usar la expresión de 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)

Luego 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 temp var corresponden a los nodos de DAG. Puede hacer que el generador de códigos sea más complejo para deshacerse de los paréntesis innecesarios, pero lo dejo para otros.