SE202 : la représentation intermédiaire (IR)

Samuel Tardieu

Année scolaire 2016/2017

La représentation intermédiaire

Modèle

L'arbre syntaxique abstrait (AST)

La représentation intermédiaire (IR)

Exemple de traduction : les fonctions

Une déclaration de fonction

Un appel de fonction

Les frames

À l'entrée dans une fonction, une nouvelle frame est créee pour pouvoir y placer tous les éléments qui doivent être stockés sur la pile (et pointée par le registre frame pointer) :

Pour pouvoir accéder à une variable d'un niveau supérieur (champ depth différent de celui de la fonction courante), il faut utiliser une indirection : le static link.

Le static link est une valeur qui représente la frame de niveau statique directement supérieur à celui de la fonction courante :

Pour un accès facile, le static link :

Exemple 1

let
  function f() =
    let var a := 2
    in
      a := a + 1;
      a
    end
in
  f()
end

Ici, la variable a est une variable locale à la fonction. Elle peut être stockée dans un registre, le static link n'est pas utilisé.

Exemple 2

let var a := 2
    function f() = (a := a + 1; a)
in f() end

Ici, la variable a est une variable accédée depuis f mais déclarée en dehors. Depuis f, elle est accédée à travers le static link, qui permet d'accéder aux variables du niveau le plus haut.

Les nouveaux objets

En plus des nœuds assez proches de ceux de l'AST, l'IR utilise deux types d'entités qui ne sont pas des nœuds :

Les types de nœuds de l'IR

Les nœuds de l'IR, dont les noms sont en majuscule (comme CONST) pour les distinguer facilement des nœuds de l'AST, sont regroupés en deux sous-hiérarchies :

Mais une traduction directe en profondeur de l'AST en IR pose des problèmes d'efficacité du code généré, il va falloir introduire d'autres mécanismes.

Le problème de la traduction directe

Un nœud de l'AST représentant l'expression a < 3 peut venir de plusieurs contextes :

Utiliser systématiquement la première traduction lors du parcours de l'arbre est inefficace. Il ne permettrait pas d'utiliser les sauts conditionnels présents dans les processeurs modernes, et obligerait à des normalisations (0 ou 1) inutiles.

Une solution

Pour pouvoir traduire l'arbre avec un parcours classique, on ne retourne pas directement un nœud lorsqu'on traite les nœuds enfants, mais une coquille (Shell), qui encapsule une représentation un peu plus abstraite du nœud. Ensuite, on sortira de la coquille la représentation qui nous intéresse selon le contexte.

Le Shell peut être de quatre types :

Traduire un Shell en nœud IR

Les trois opérateurs suivants, qui s'appliquent sur les différents Shell, permettent d'obtenir l'arbre IR correspondant à l'opération utilisée :

Par exemple, unEx() sur un nœud Cx (opérateur de comparaison) renverra un arbre calculant 0 ou 1. unCx() appelé sur le même nœud utilisera probablement un opérateur de saut conditionnel suivi d'un saut inconditionnel.

Conséquences d'utilisation du Shell

Sans les Shell, l'expression if a < b then 4 else 5 serait traduite comme :

Avec le Shell, elle est traduite comme :

Autre exemple

Avec le Shell, on peut facilement traduire

result := if a < b & c < d then 4 else 5

en (pseudo-nœuds) :

  CJUMP(">=", TEMP(a), TEMP(b), NAME(falseLabel))
  CJUMP(">=", TEMP(c), TEMP(d), NAME(falseLabel))
  MOVE(TEMP(result), CONST(4))
  JUMP(NAME(endLabel))
  LABEL(falseLabel)
  MOVE(TEMP(result), CONST(5))
  LABEL(endLabel)

Optimisations

On peut profiter de la traduction pour faire certaines optimisations, par exemple :

def unEx(self):
    return Ix(self.frame, self,
              Ex(CONST(1)), Ex(CONST(0))).unEx()