Elimina in modo efficiente le sotto espressioni comuni in .NET Expression Tree

.net algorithm c# expression-trees optimization

Domanda

Ho scritto un DSL e un compilatore che genera un albero di espressioni .NET da esso. Tutte le espressioni all'interno dell'albero sono prive di effetti collaterali e l'espressione è garantita come espressione di "non dichiarazione" (nessuna gente del posto, loop, blocchi ecc.). ( Modifica : l'albero può includere letterali, accessi di proprietà, operatori standard e chiamate di funzione, che possono fare cose di fantasia come la memoizzazione all'interno, ma sono esternamente privi di effetti collaterali).

Ora vorrei eseguire l'ottimizzazione "Eliminazione sottoespressione comune" su di essa.

Ad esempio, dato un albero corrispondente al lambda C #:

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

... Mi piacerebbe generare l'equivalente ad albero di (ignora il fatto che alcuni dei semantici di cortocircuito vengono ignorati):

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);
}

Ho familiarità con la scrittura di visitatori di espressioni, ma l'algoritmo per questa ottimizzazione non è immediatamente ovvio per me - potrei ovviamente trovare "duplicati" all'interno di un albero, ma c'è ovviamente qualche trucco per analizzare le dipendenze all'interno e tra i sotto- alberi per eliminare le sotto-espressioni in modo efficiente e corretto.

Ho cercato algoritmi su Google ma sembrano abbastanza complicati da implementare rapidamente. Inoltre, sembrano molto "generali" e non prendono necessariamente la semplicità degli alberi che ho in considerazione.

Risposta accettata

Hai ragione nel notare che questo non è un problema banale.

Il modo classico con cui i compilatori lo gestiscono è una rappresentazione DAG (Directed Acyclic Graph) dell'espressione. Il DAG è costruito nello stesso modo dell'albero di sintassi astratto (e può essere costruito attraversando l'AST - forse un lavoro per il visitatore dell'espressione, non conosco molte delle librerie C #), eccetto che un dizionario di sottoprogrammi precedentemente emessi è mantenuto. Prima di generare un dato tipo di nodo con determinati bambini, il dizionario viene consultato per vedere se ne esiste già uno. Solo se questo controllo fallisce, ne viene creato uno nuovo, quindi aggiunto al dizionario.

Poiché ora un nodo può discendere da più genitori, il risultato è un DAG.

Quindi il DAG viene prima attraversato per generare il codice. Poiché le sottoespressioni comuni sono ora rappresentate da un singolo nodo, il valore viene calcolato una sola volta e memorizzato in una temp per altre espressioni emesse successivamente nella generazione del codice da utilizzare. Se il codice originale contiene compiti, questa fase si complica. Poiché i tuoi alberi sono privi di effetti collaterali, il DAG dovrebbe essere il modo più semplice per risolvere il tuo problema.

Come ricordo, la copertura dei DAG nel libro del Drago è particolarmente bella.

Come altri hanno notato, se i tuoi alberi alla fine saranno compilati da un compilatore esistente, è quasi inutile rifare ciò che è già lì.

aggiunta

Ho avuto un po 'di codice Java in giro da un progetto studentesco (insegno), così ho fatto un piccolo esempio di come funziona. È troppo lungo per postare, ma vedi il Gist qui .

Eseguendolo sul tuo input, stampa il DAG qui sotto. I numeri in parentesi sono (ID univoco, conteggio genitori DAG). Il conteggio dei genitori è necessario per decidere quando calcolare le variabili temporali locali e quando utilizzare l'espressione per 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)

Quindi genera questo codice:

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

Si può vedere che i numeri temporanei var corrispondono ai nodi DAG. Potresti rendere il generatore di codice più complesso per eliminare le parentesi non necessarie, ma lo lascerò agli altri.


Risposta popolare

Stai facendo del lavoro non necessario, l'eliminazione di sottoespressione comune è il lavoro dell'ottimizzatore del jitter. Prendiamo il tuo esempio e guardiamo il codice generato. L'ho scritto così:

    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; }
}

Il jitter x86 ha generato questo codice macchina per l'espressione 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   

Ho segnato i punti nel codice in cui la sotto-espressione foo.Bar * 5 stata eliminata con QUI. Notevole è come non ha eliminato la sotto-espressione foo.Bar * 5 + foo.Baz * 2 , l'aggiunta è stata eseguita nuovamente all'indirizzo 006526CF. C'è una buona ragione per questo, il jitter x86 non ha abbastanza registri disponibili per memorizzare il risultato intermedio. Se si guarda il codice macchina generato dal jitter x64 allora non vede eliminato, il registro R9 memorizza.

Questo dovrebbe dare abbastanza ragioni per riconsiderare le tue intenzioni. Stai facendo un lavoro che non ha bisogno di essere fatto. E non solo, si rischia di generare codice peggiore di quello generato dal jitter poiché non si ha il lusso di stimare il budget del registro della CPU.

Non farlo.



Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché
Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché