(* <h1>TP05: Génération de code </h1>
 *)
(*<h2>Partie 1 : Compilation des expressions arithmétiques simples</h2>*)
type expr =
  | Const of int			(* constante *)
  | Add of expr*expr			(* addition *)
  | Mul of expr*expr			(* multiplication *)
  | IfTE of expr*expr*expr*expr		(* if e1=e2 then e3 else e4 *)
  | Call of string*expr list            (* appel de fonction *)
  | Var of int				(* i-ème argument d'une fonction *)

(* definitions: (f,n,b) est la définition de la fonction f, à n
   arguments, de corps b *)
type def = string*int*expr 

(* un programme est une liste de définitions de fonction,
 * suivie d'une expression à évaluer. *)
type prog = def list*expr


(* EXEMPLES *)
(* exemple basique *)
let basic: prog = [],Const 42

(* exemple d'expression: (9+5)*(4-1) *)
let trente: expr = Mul(Add(Const 9,Const 5),Add(Const 4,Const(-1)))

(* le programme pour calculer trente : pas de définition de fonction *)
let prog_trente: prog = [],trente
      
(* autre exemple: factorielle *)
let fact: def = ("fact", 1, 
		 IfTE(Var 1,Const 0, Const 1,
		      Mul(Var 1,Call("fact",[Add(Var 1,Const(-1))]))))

(* exemple de programme: on utilise factorielle *)
let prog_fact: prog = [fact],Add(Const 18,Call("fact",[Const 4]))

(* vous ne pouvez pas encore utiliser ces exemples évidemment... *)


(** Les Registres *)

(* les 32 registres sont identifiés par les chaînes des entiers de 0 à 31 *)
type registre = string

(* pour obtenir faciliment le registre numéro [i] *)
let reg i = "R" ^ string_of_int i

(* quelques registres *)
let r_zero:   registre = reg 0  (* y a toujours 0 dedans *)
let r_result: registre = reg 1  (* par défaut, contient le dernier résultat calculé *)
let r_fp:     registre = reg 29 (* Ici, on va dire qu'on s'en sert que pointeur de frame *)
let r_sp:     registre = reg 30 (* traditionnellement, le pointeur de pile *)
let r_return: registre = reg 31 (* pour savoir où continuer après un appel de fonction *)


(* fonction de compilation vers un fichier donné *)
let compile fichier =  
  (* fonctions d'affichage vers le fichier donné en argument *)
  let f = open_out fichier in
  let print s = output_string f ("\t"^s^"\n") in

  (* empiler la valeur dans le registre [r] sur la pile *)
  let push r = 
    print ("PSH "^r^" "^r_sp^" -4")
  in
    (* dépiler, en lisant dans un registre *)
  let pop r = 
    failwith "à faire..."
  in

  (* génération du code correspondant à une expression *)
  let rec gen_expr = function
    | Const k -> print ("ORI " ^ r_result ^ " " ^ r_zero ^ " " ^(string_of_int k))
    | Add(e1,e2) -> 
        failwith "à faire"
        
    | Mul(e1,e2) -> 
        failwith "copier-coller ce qui est au-dessus"
	
    | IfTE(e1,e2,e3,e4) -> 
        failwith "à faire"
	
    | Var n ->
        failwith "à faire encore, un peu après"

    | Call(f,l) -> 
        failwith "à faire aussi plus tard"
  in

  (** À partir d'ici, c'est de l'enrobage pour que ça marche *)

  (* juste pour pas avoir le '\t' au début de la ligne *)
  let print_lab s = output_string f s; output_char f '\n' in

  (* génération du code des définitions *)
  let gen_def (f,n,e) = 
    (* préambule *)
    print "";             (* on va à la ligne pour être propres :) *)
    print_lab (f^":");    (* le nom de la définition *)
    gen_expr e;	          (* Le calcul de la fonction, enfin *)

    (* postambule: on remet tout où il faut *)
    print ("RET "^r_return); 
                         (* saut à l'adresse de retour *)
  in

  (* génération du code du programme final *)
  let gen_prog (l,e) =
    (* initialisation *)
    print "";             (* on va à la ligne pour être propres (comme d'hab) *)
    print_lab "start:";
    print "BEQ 0 main";
    print "SYSCALL 1 0 6"; (* trois lignes magiques pour que ça marche: abra... *)
    print "SYSCALL 1 0 6"; (* ...cada... *)
    print "SYSCALL 1 0 6"; (* ...briais! (demandez à l'auteur de emuf pourquoi) *)


    (* génération du code des définitions *)
    List.iter gen_def l;

    (* génération du code de l'expression *)
    print_lab "main:";
    gen_expr e;

    (* avant de finir, on affiche le resultat *)
    print "SYSCALL R1 0 7"; (* afficher r.1 *)
    print "ORIU R1 0 10";   (* mettre '\n' dans r.1 (pour le retour à la ligne) *)
    print "SYSCALL 1 0 6";  (* afficher le caractère *)

    (* et on fait exit *)
    print "RET 0";
    
    close_out f;
    Sys.command ("cat "^fichier)       (* affiche le fichier généré *)

  in
    gen_prog

(* premier test de base *)
let _ = compile "basic.s" basic

(* compile le programme trente dans le fichier "trente.s" *)
let _ = compile "trente.s" prog_trente

(* compile le programme fact_5 dans le fichier "fact_5.s" *)
let _ = compile "fact.s" prog_fact


(* <h2>Partie 2 : Ordonnancement optimal</h2> *)
(* ne pas commencer ici tant qu'on n'a pas terminé tout au-dessus *)
let reorder_expr: expr -> expr = fun _ -> failwith "a faire: reorder_expr"

let reorder: prog -> prog = fun _ -> failwith "a faire: reorder_expr"

(* test de l'ordonnanceur sur l'expression (1+(3+(7+(12+(19+0))))) *)
let cinq_add = (Add(Const 1,Add(Const 3,Add(Const 7,Add(Const 12,Add(Const 19,Const 0))))))
let _ = compile "/tmp/cinqadd.s" ([],cinq_add)
let _ = compile "/tmp/cinqadd-opt.s" (reorder ([],cinq_add))
  

(* <h2>Partie 3 : Récursion terminale</h2> *)
(* idem: ne pas commencer ici tant qu'on n'a pas terminé tout au-dessus *)

(* annotation d'un programme : vous devez ignorer les annotations
   d'appels de fonctions déjà présentes, et les remplacer par des
   annotations correctes *)
let annot_expr: int -> expr -> expr = fun _ -> failwith "TODO (annot_expr)"
let annot_prog: prog -> prog = fun _ -> failwith "TODO (annot_prog)"

(* test: factorielle récursive terminale *)
(* vous pouvez décommenter la suite après avoir rajouté un '*int*' à la
 * définition du [Call] *)
(*
let fact_no_rt =
    ["fact",2,IfTE(Var 2,Const 0, Var 1,
		     Call("fact",-1,[Mul(Var 1,Var 2);
				    Add(Var 2, Const(-1))]))],
    Call("fact",-1,[Const 1; Const 5])


let fact_rt = annot_prog fact_no_rt

(* compilation et exécution *)
let _ = compile "fact_rt_5.s" fact_rt_5
*)


(* <h2>Partie 4 : Expressions avec fonctions imbriquées: lambda-lifting</h2> *)
type eexpr =
  | EConst of int
  | EAdd of eexpr*eexpr
  | EMul of eexpr*eexpr
  | EIfTE of eexpr*eexpr*eexpr*eexpr
  | ECall of string*eexpr list
      (* let f x1 ... xn = e in e' *)
  | ELet of string*string list*eexpr*eexpr
  | EVar of string

let lift: eexpr -> prog = fun _ -> failwith "TODO (lift)"

(* factorielle, avec une fonction imbriquée, récursive terminale *)
(*
let fact_rt_6 = ELet("fact",["n"],
		     ELet("aux", ["acc"; "n"],
			  EIfTE(EVar "n",EConst 0, EVar "acc",
				ECall("aux",[EMul(EVar "acc",EVar "n");
						  EAdd(EVar "n", EConst(-1))])),
			  ECall("aux",[EConst 1; EVar "n"])),
		     ECall("fact",[EConst 6]))


(* déroulage et annotation *)
let fact_rt_6_deroulee = annot_prog (lift fact_rt_6)
(* on peut aussi réordonnancer si vous voulez *)

(* compilation et exécution *)
let _ = compile "fact_rt_6.s" fact_rt_6_deroulee
*)