Éliminer efficacement les sous-expressions courantes dans l'arbre d'expression .NET

.net algorithm c# expression-trees optimization

Question

J'ai écrit un DSL et un compilateur qui génère un arbre d'expression .NET à partir de celui-ci. Toutes les expressions dans l’arbre sont exemptes d’effets secondaires et il est garanti que l’expression est une expression "non-instruction" (pas de caractère local, de boucle, de bloc, etc.). ( Édition : l’arborescence peut inclure des littéraux, des accès à des propriétés, des opérateurs standard et des appels de fonctions - pouvant faire des choses fantaisistes telles que la mémorisation à l’intérieur, mais exempts d’effets secondaires externes).

J'aimerais maintenant procéder à l'optimisation "Élimination de la sous-expression commune".

Par exemple, étant donné un arbre correspondant au lambda C #:

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

... Je voudrais générer l'équivalent-arbre de (ignorer le fait que certaines sémantiques de court-circuit sont ignorées):

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

Je connais bien l'écriture de l'expression expression-visiteurs, mais l'algorithme de cette optimisation ne m'est pas immédiatement évident. Je pourrais bien sûr trouver des "doublons" dans un arbre, mais il est évident qu'il est difficile d'analyser les dépendances à l'intérieur et entre les sous-éléments. arbres pour éliminer les sous-expressions efficacement et correctement.

J'ai cherché des algorithmes sur Google mais ils semblent assez compliqués à implémenter rapidement. En outre, ils semblent très "généraux" et ne tiennent pas nécessairement compte de la simplicité des arbres que j'ai.

Réponse acceptée

Vous avez raison de noter que ce n'est pas un problème trivial.

La manière classique dont les compilateurs le traitent est une représentation DAG (Directed Acyclic Graph) de l'expression. Le DAG est construit de la même manière que l'arbre de syntaxe abstraite (et peut être construit en parcourant l'AST - peut-être un travail pour le visiteur d'expression; je ne connais pas grand-chose des bibliothèques C #), sauf qu'un dictionnaire de sous-graphes précédemment émis est maintenu. Avant de générer un type de nœud donné avec des enfants donnés, le dictionnaire est consulté pour déterminer s'il en existe déjà un. Si cette vérification échoue, une nouvelle création est créée, puis ajoutée au dictionnaire.

Étant donné qu’à présent, un nœud peut descendre de plusieurs parents, le résultat est un DAG.

Ensuite, le DAG est d'abord traversé en profondeur pour générer du code. Étant donné que les sous-expressions communes sont maintenant représentées par un seul nœud, la valeur est calculée une seule fois et stockée dans un temp pour que d'autres expressions émises plus tard lors de la génération de code puissent être utilisées. Si le code d'origine contient des assignations, cette phase devient compliquée. Puisque vos arbres sont exempts d’effets secondaires, le DAG devrait être le moyen le plus simple de résoudre votre problème.

Si je me souviens bien, la couverture des DAG dans le livre de Dragon est particulièrement intéressante.

Comme d'autres l'ont noté, si vos arbres sont finalement compilés par un compilateur existant, il est en quelque sorte inutile de rétablir ce qui existe déjà.

Une addition

J'avais un peu de code Java dans un projet étudiant (je l'enseigne), alors voici un petit exemple de son fonctionnement. C'est trop long à poster, mais voyez le Gist ici .

L'exécuter sur votre entrée imprime le DAG ci-dessous. Les nombres entre parenthèses sont (identifiant unique, nombre de parents DAG). Le nombre de parents est nécessaire pour décider quand calculer les variables temp locales et quand utiliser simplement l'expression pour un nœud.

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)

Ensuite, il génère ce code:

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

Vous pouvez voir que les numéros de variable temporaire correspondent aux nœuds DAG. Vous pourriez rendre le générateur de code plus complexe pour supprimer les parenthèses inutiles, mais je laisserai cela à d'autres.


Réponse populaire

Vous effectuez un travail inutile, l'élimination de la sous-expression courante est le travail de l'optimiseur de gigue. Prenons votre exemple et regardons le code généré. Je l'ai écrit comme ça:

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

La gigue x86 a généré ce code machine pour l'expression 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   

J'ai marqué les endroits dans le code où la sous-expression foo.Bar * 5 été éliminée avec ICI. Il convient de noter comment il n'a pas éliminé la sous-expression foo.Bar * 5 + foo.Baz * 2 , l'addition a été effectuée à nouveau à l'adresse 006526CF. Il y a une bonne raison à cela, la jitter x86 ne dispose pas de suffisamment de registres pour stocker le résultat intermédiaire. Si vous regardez le code machine généré par la gigue x64, vous le voyez éliminé, le registre r9 le stocke.

Cela devrait donner suffisamment de raisons pour reconsidérer votre intention. Vous faites un travail qui n'a pas besoin d'être fait. Et non seulement cela, vous êtes susceptible de générer un code pire que celui de la gigue, car vous n'avez pas le luxe d'estimer le budget du registre du processeur.

Ne fais pas ça.



Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow