Entfernen Sie gängige Unterausdrücke in .NET Expression Tree effizient

.net algorithm c# expression-trees optimization

Frage

Ich habe ein DSL und einen Compiler geschrieben, der daraus einen .NET-Ausdrucksbaum generiert. Alle Ausdrücke innerhalb des Baumes sind frei von Nebeneffekten und der Ausdruck ist garantiert ein "Nicht-Aussage" -Ausdruck (keine lokalen Variablen, Schleifen, Blöcke usw.). ( Bearbeiten : Der Baum kann Literale, Eigenschaftenzugriffe, Standardoperatoren und Funktionsaufrufe enthalten - die zwar interessante Dinge wie Memoization innerhalb machen können, aber extern frei von Nebenwirkungen sind).

Jetzt möchte ich die "Common Sub-Expression Elimination" -Optimierung darauf durchführen.

Angenommen, ein Baum entspricht dem C # Lambda:

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

... Ich möchte das Tree-Äquivalent von (ich ignoriere die Tatsache, dass einige der Kurzschlüsse Semantik ignoriert werden):

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

Ich bin mit dem Schreiben von Ausdruck-Besuchern vertraut, aber der Algorithmus für diese Optimierung ist nicht sofort für mich offensichtlich - ich könnte natürlich "Duplikate" innerhalb eines Baumes finden, aber es gibt offensichtlich einen Trick, um die Abhängigkeiten innerhalb und zwischen Bäume, um Unterausdrücke effizient und korrekt zu eliminieren.

Ich habe bei Google nach Algorithmen gesucht, aber sie scheinen schnell zu implementieren. Außerdem scheinen sie sehr "allgemein" zu sein und berücksichtigen nicht unbedingt die Einfachheit der Bäume, die ich in Betracht ziehe.

Akzeptierte Antwort

Sie haben Recht, dies ist kein triviales Problem.

Die klassische Art, mit der Compiler damit umgehen, ist eine Directed Azyklic Graph (DAG) -Darstellung des Ausdrucks. Die DAG ist in der gleichen Weise aufgebaut wie der abstrakte Syntaxbaum (und kann durch Überqueren des AST aufgebaut werden - vielleicht ein Job für den Ausdruck Besucher; ich kenne nicht viele C # -Bibliotheken), außer dass ein Wörterbuch von zuvor ausgegebenen Untergraphen ist gewartet. Bevor ein beliebiger Knotentyp mit gegebenen Kindern erzeugt wird, wird das Wörterbuch konsultiert, um zu sehen, ob es bereits existiert. Nur wenn diese Überprüfung fehlschlägt, wird eine neue erstellt und dann zum Wörterbuch hinzugefügt.

Da nun ein Knoten von mehreren Eltern abstammen kann, ist das Ergebnis eine DAG.

Dann wird die DAG zuerst Tiefe durchlaufen, um Code zu erzeugen. Da allgemeine Sub-Ausdrücke jetzt durch einen einzelnen Knoten repräsentiert werden, wird der Wert nur einmal berechnet und in einem Temp für andere Ausdrücke gespeichert, die später in der zu erzeugenden Code-Generierung ausgegeben werden. Wenn der Originalcode Zuweisungen enthält, wird diese Phase kompliziert. Da Ihre Bäume frei von Nebenwirkungen sind, sollte die DAG der einfachste Weg sein, um Ihr Problem zu lösen.

Soweit ich mich erinnere, ist die Berichterstattung über DAGs im Dragon-Buch besonders schön.

Wie andere bemerkt haben, wenn Ihre Bäume letztendlich von einem bestehenden Compiler kompiliert werden, ist es sinnlos, was bereits vorhanden ist.

Zusatz

Ich hatte etwas Java-Code von einem Schülerprojekt (ich unterrichte), also ein kleines Beispiel dafür, wie das funktioniert. Es ist zu lange, um es zu posten, aber den Gist sehen Sie hier .

Wenn Sie die Eingabe ausführen, wird der DAG unten gedruckt. Die Zahlen in Parens sind (eindeutige ID, DAG-Elternzahl). Die übergeordnete Anzahl wird benötigt, um zu entscheiden, wann die lokalen temporären Variablen berechnet werden sollen und wann nur der Ausdruck für einen Knoten verwendet werden soll.

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)

Dann erzeugt es diesen Code:

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

Sie können sehen, dass die Temp-Var-Nummern den DAG-Knoten entsprechen. Sie könnten den Codegenerator komplexer machen, um unnötige Klammern zu entfernen, aber ich überlasse das anderen.


Beliebte Antwort

Sie machen unnötige Arbeit, die Beseitigung gemeinsamer Unterausdrücke ist die Aufgabe des Jitter-Optimierers. Nehmen wir Ihr Beispiel und sehen Sie sich den generierten Code an. Ich habe es so geschrieben:

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

Der x86-Jitter erzeugte diesen Maschinencode für den Lambda-Ausdruck:

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   

Ich markierte die Stellen im Code, wo der foo.Bar * 5 mit HERE eliminiert wurde. Bemerkenswert ist, wie die foo.Bar * 5 + foo.Baz * 2 nicht eliminiert wurde, die Addition wurde erneut unter der Adresse 006526CF durchgeführt. Es gibt einen guten Grund dafür, dass der x86-Jitter nicht genügend Register zur Verfügung hat, um das Zwischenergebnis zu speichern. Wenn Sie sich den Maschinencode ansehen, der vom x64-Jitter erzeugt wird, dann sehen Sie , dass er beseitigt ist, das r9-Register speichert ihn.

Dies sollte genug Gründe geben, um Ihre Absicht zu überdenken. Du machst Arbeit, die nicht getan werden muss. Und nicht nur das, Sie werden wahrscheinlich schlechteren Code erzeugen, als der Jitter erzeugt, da Sie nicht den Luxus haben, das CPU-Register-Budget zu schätzen.

Tu das nicht.



Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum
Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum