Solution, graphe d'interférence

1  Temporaires vivants

La solution est liveness.ml.

Voici le code de la fonction fixpoint. Comme l'algo du poly, ce code est structuré selon une boucle.
let fixpoint g =
  let encore = ref true
  and niters = ref 0 in
   …
  while !encore do
    encore := false ;
    niters := !niters + 1 ;
    Pour tous les sommets de g do
       Calculer les  In et les  Out selon les formules
    done
    encore := Quelque chose a changé
  done ;
  !niters (* retourner le nombre total d'itérations effectuées *)

Soit concrètement :
(* Calcul des live-in/out par point fixe *)
let fixpoint g =
  let encore = ref true
  and niters = ref 0 in
  (* Récupérer tous les sommets (dans l'ordre inverse de l'exécution ici) *)
  let nodes = List.rev (Graph.nodes g) in

  while !encore do
(* Petit affichage déclenché par l'option « -v » *)
    if !verbose then begin
      Printf.fprintf stderr "***** Itération %d *******\n" !niters ;
      print_flowgraph stderr g
    end ;
    niters := !niters + 1
    encore := false ;
    List.iter  (* Pour tous les sommets *)
      (fun node ->
        let info = Graph.info g node in
   (* Calculer  Ink+1(node) et  Outk+1(node) *)
        let new_out =
          List.fold_left
            (fun r to_n ->
              union (Graph.info g to_n).live_in r)
            empty
            (Graph.succ g node) in
        let new_in = union info.use (diff new_out info.def) in
    (* Regarder si  Outk+1(node) ≢ Outk(node) *)
        encore :=  !encore || not (eqset info.live_out new_out) ;
        info.live_in <- new_in ;
        info.live_out <- new_out)
      nodes ;
  done ;
  !niters
On notera que le programme ne se pose pas trop de questions sur le calcul des Out (et des In). On commence par calculer Outk+1 en utlisant constructivement l'équation de point fixe :
Out (i) =
 
∪
j ∈ Succ(i)
In(j)
Les In se comprennent ici mieux comme la valeur courante de In pour tous les sommets qui sont des successeurs j du sommet en cours i. Il comprennent donc en géneral à la fois des Ink+1(j) et des Ink(j) selon qu'un successeur particulier j est traité avant ou après i par l'itération « pour tous les sommets ».

Puis on calcule Ink+1 :
Ink+1(i) = Use(i) ∪ ( Outk+1(i) \ Def (i))
Le nouvel  In(i) ainsi calculé est rangé dans le graphe, à l'intention des calculs suivants des Out.

Par rapport à la présentation du poly, on a fait apparaître des In sockés dans le graphe, là où l'algortithme effectue un calcul explicite.

Enfin l'itération sur les instructions du code (par List.iter) procède dans l'ordre inverse de présentation des instructions (à cause de List.rev), ce qui accelère notabablement la convergence.

2  Graphe des moves

La solution est liveness.ml. (Voir la fin de la fonction interference). Pas de commentaire pour le moment.

Ce document a été traduit de LATEX par HEVEA.