DIRECTED ACYCLIC GRAPH

DAG is at the heart of the ORCA/C compiler.
The ORCA/C compiler is written in Pascal.
If you wan't to read/understand the ByteWorks ORCA/C sources files then DAG is the main
important thing to understand.
You can program DAGs in C with GNO.
You can take the source code of the Pascal DAG file of the ORCA/C sources and 
recode it in C under GNO. I do not copy/paste the source file in Slack you can read the sources.
But the sources of the DAG file do not come with explanations that's why I wrote this text below.

Graphes orientés acycliques pour les expressions

  Un graphe orienté acyclique (DAG) correspondant à une expression identifie les sous-expressions
communes qu'elle contient. Comme un arbre abstrait, un DAG comprend un noeud pour chaque
sous-expression; un noeud intérieur représente un opérateur et ses fils représentent ses
opérandes. La différence est qu'un noeud de DAG représentant une sous-expression commune
a plus d'un "père"; dans un arbre abstrait, la sous-expression commune serait représentée
par un sous-arbre dupliqué.
  La figure 5.11 représente un DAG pour l'expression :
  a + a * (b - c) + (b - c) * d
La feuille correspondant à a possède deux pères car a apparaît dans les deux sous-expressions
a et a * (b - c). De même, les deux occurences de la sous-expression commune b - c sont
représentées par le même noeud, qui a aussi deux pères.

  La définition dirigée par la syntaxe de la figure 5.9 construira un DAG au lieu d'un arbre
abstrait si l'on modifie les opérations qui construisent les noeuds. On obtient un DAG si la
fonction construisant un noeud commence par vérifier si un noeud identique n'existe pas déjà.
Par exemple, avant de construire un nouveau noeud d'étiquette op avec des champs pointant vers
gauche et droit, CréerNoeud(op,gauche,droit) peut vérifier si un tel noeud n'a pas déjà été
construit. Si c'est le cas, CréerNoeud(op,gauche,droit) peut retourner un pointeur vers le noeud
construit précédemment. Les fonctions CréerFeuille construisant des feuilles peuvent avoir un
comportement similaire.

  Exemple 5.9 La séquence d'instructions de la figure 5.12 construit le DAG de la figure 5.11,
à condition que CréerNoeud et CréerFeuille ne créent de nouveaux noeuds que lorsque c'est
nécessaire, et rendent des pointeurs vers des noeuds existants, dont l'étiquette et les fils
sont corrects, chaque fois que c'est possible. Dans la figure 5.12, a, b, c et d pointent vers
les entrées dans la table des symboles des identificateurs a, b, c et d.
  Instructions pour construire le DAG de la figure 5.11
(1) p1 := CréerFeuille(id,a);
(2) p2 := CréerFeuille(id,a);
(3) p3 := CréerFeuille(id,b);
(4) p4 := CréerFeuille(id,c);
(5) p5 := CréerNoeud('-',p3,p4);
(6) p6 := CréerNoeud('*',p2,p5);
(7) p7 := CréerNoeud('+',p1,p6);
(8) p8 := CréerFeuille(id,b);
(9) p9 := CréerFeuille(id,c);
(10) p10 := CréerNoeud('-',p8,p9);
(11) p11 := CréerFeuille(id,d);
(12) p12 := CréerNoeud('*',p10,p11);
(13) p13 := CréerNoeud('+',p7,p12);

  Quand l'appel CréerFeuille(id,a) est répété ligne 2, le noeud construit par le précédent
appel CréerFeuille(id,a) est retourné, ce qui fait que p1=p2. De même, les noeuds retournés
lignes 8 et 9 sont les mêmes que ceux retournés lignes 3 et 4 respectivement. On en déduit
que le noeud retourné ligne 10 doit être le même que celui construit par l'appel de
CréerNoeud ligne 5.
  Dans de nombreuses applications, les noeuds sont implantés par des structures stockées dans
un tableau, comme dans la figure 5.13. Dans cette figure, chaque structure possède un champ
"étiquette" qui détermine la nature du noeud. On peut faire référence à un noeud à l'aide de
son indice ou position dans le tableau. Si cet indice est un nombre entier, il est souvent
appelé nombre de valeur, pour des raisons historiques. Par exemple, en utilisant les nombres
de valeur, on peut dire que le noeud 3 a pour étiquette +, que son fils gauche est le noeud 1
et que son fils droit est le noeud 2. L'algorithme qui suit peut être utilisé pour créer les
noeuds de la représentation sous forme de DAG d'une expression.

Algorithme 5.1. Méthode des nombres de valeur pour construire un noeud de DAG
  On suppose que les noeuds sont stockés dans un tableau, comme dans la figure 5.13, et que
chaque noeud est référencé par son nombre de valeur. Définissons la signature d'un noeud
opérateur comme le triplet (op,g,d) constitué par son étiquette op, son fils gauche g et son
fils droit d.
Données. L'étiquette op, le noeud g et le noeud d.
Résultat. Un noeud de signatur (op,g,d).
Méthode. Chercher dans le tableau un noeud m d'étiquette op, de fils gauche g et de fils 
droit d. S'il existe un tel noeud, retourner m; sinon, créer un nouveau noeud n d'étiquette op,
de fils gauche g et de fils droit d, et retourner n.
  Un moyen immédiat de déterminer si le noeud m est dans le tableau est de conserver tous les
noeuds créés auparavant dans une liste et de vérifier pour chaque noeud de la liste s'il a la
signature désirée. La recherche de m peut être rendue plus efficace en utilisant k listes,
appelées compartiments, et une fonction de hachage h pour déterminer dans quel compartiment
effectuer la recherche.
  La fonction de hachage h calcule le numéro d'un compartiment à partir des valeurs de
op, g et d. Elle rendra toujours le même numéro de compartiment si on lui donne les mêmes
arguments. Si m n'existe pas dans le compartiment de numéro h(op,g,d), on crée un nouveau
noeud n et on l'ajoute à ce compartiment, de sorte que les futures recherches puissent le
trouver là. Plusieurs signatures différentes peuvent correspondre au même numéro de 
compartiment, mais en pratique on espère que chaque compartiment ne contiendra qu'un petit
nombre de noeuds.
  Chaque compartiment peut être implanté comme une liste chaînée, ainsi que le montre la figure
5.14. Chaque cellule d'une liste chaînée représente un noeud. Les "têtes de compartiments",
consistant en un pointeur vers la première cellule d'une liste, sont stockées dans un tableau.
Le numéro de compartiment rendu par h(op,g,d) est un indice dans ce tableau des têtes de
compartiments.

  Cet algorithme peut être adapté pour s'appliquer à des noeuds qui ne sont pas alloués
séquentiellement dans un tableau. Dans de nombreux compilateurs, les noeuds sont alloués au
fur et à mesure des besoins, pour éviter d'allouer à l'avance un tableau qui, la plupart
du temps, sera trop largement dimensionné mais qui, de temps en temps,sera insuffisant.
Dans ce cas, on ne peut plus supposer que les noeuds sont contigus en mémoire; il faut donc
utiliser des pointeurs pour y accéder. Si la fonction de hachage peut être modifiée pour
calculer le numéro de compartiment à partir d'une étiquette et des pointeurs vers les fils,
on peut utiliser directement les pointeurs vers les noeuds d'une façon quelconque et utiliser
ces nombres comme nombres de valeur pour les noeuds.
  Les DAG peuvent aussi représenter des ensembles d'expressions, car un DAG peut posséder
plus d'une racine. Dans les chapitres 9 et 10, les calculs effectués au cours d'une
séquence d'instructions d'affectation seront représentés par un DAG.