let sint=1

module Label = struct
  let a = ref 0
  let fresh () = incr a; "scomp_"^(string_of_int !a)
end

type register = 
  | Zero | A0 | A1 | A2 | V0 | V1 | S0 | RA | SP | FP

type address =
  | Alab of string
  | Areg of int * register

type operand =
  | Oimm of int
  | Oreg of register

type arith = Add | Sub | Mul | Div | Rem

type comp = Ge | Le | Gt | Lt | Eq | Neq

type instruction =
  | Move of register * register
  | Li of register * int
  | La of register * string
  | Lw of register * address
  | Sw of register * address
  | Arith of arith * register * register * operand
  | SComp of comp * register * register * register
  | BComp of comp * register * register * string
  | B0Comp of comp * register * string
  | Neg of register * register
  | B of string
  | Jal of string
  | J of string
  | Jr of register
  | Syscall
  | Label of string

type data = 
  | Asciiz of string * string
  | Word of string * int

type program = {
  text : instruction list;
  data : data list;
}

open Format

module Smap = Map.Make(String)

let print_register fmt = function
  | Zero -> pp_print_string fmt "W11" (* T2 *)
  | A0 -> pp_print_string fmt "W2"
  | A1 -> pp_print_string fmt "W3"
  | A2 -> pp_print_string fmt "W4"
  | V0 -> pp_print_string fmt "W0"
  | V1 -> pp_print_string fmt "W1"
  | S0 -> pp_print_string fmt "W6"
  | RA -> pp_print_string fmt "W12"
  | SP -> pp_print_string fmt "W13"
  | FP -> pp_print_string fmt "W14"
  (* Noter que W10 (T1), W5 (A3), W7 (S1), W8 (S2) et  W15 (AT) sont utilisé comme registres temporaires *)
  (* Noter que W9 (T0) est un pointeur sur le haut du tas *)

let print_arith fmt = function
  | Add -> pp_print_string fmt "addu"
  | Sub -> pp_print_string fmt "sub"
  | Mul -> pp_print_string fmt "mul"
  | Div -> pp_print_string fmt "div"
  | Rem -> pp_print_string fmt "rem"

let print_address fmt (genv,s) =
  pp_print_int fmt (Smap.find s genv)

let rec print_instruction genv fmt = function
  | Move (dst, src) -> 
      fprintf fmt "\tmove %a %a\n" print_register dst print_register src
  | Li (r, i) ->
      fprintf fmt "\tli   %a %d\n" print_register r i
  | La (r, s) ->
      if Smap.mem s genv then
          fprintf fmt "\tli   %a %a\n" print_register r print_address (genv,s)
      else
          fprintf fmt "\tla   %a %s\n" print_register r s

  | Lw (r, Alab a) ->
      fprintf fmt "\tli   W15 %a\n" print_address (genv,a);
      fprintf fmt "\tlh   %a W15\n" print_register r 
  | Sw (r, Alab a) ->
      fprintf fmt "\tli   W15 %a\n" print_address (genv,a);
      fprintf fmt "\tsh   W15 %a\n" print_register r 
  | Lw (r, Areg (0,src)) ->
      fprintf fmt "\tlh   %a %a\n" print_register r print_register src
  | Sw (r, Areg (0,src)) ->
      fprintf fmt "\tsh   %a %a\n" print_register src print_register r
  | Lw (r, Areg (ofs,src)) ->
      fprintf fmt "\taddui W10 %a %d\n" print_register src ofs;
      fprintf fmt "\tlh   %a W10\n" print_register r
  | Sw (r, Areg (ofs,src)) ->
      fprintf fmt "\taddui W10 %a %d\n" print_register src ofs;
      fprintf fmt "\tsh   W10 %a\n" print_register r

  | Arith (Add, dst, src, Oimm op) ->
      fprintf fmt "\taddui  %a %a %d\n" 
	print_register dst print_register src op
  | Arith (Sub, dst, src, Oimm op) ->
      fprintf fmt "\taddui  %a %a %d\n" 
	print_register dst print_register src (-op)
  | Arith (a, dst, src, Oreg op) when a=Add || a=Sub ->
      fprintf fmt "\t%a  %a %a %a\n" 
	print_arith a print_register dst print_register src print_register op
  | Arith (Mul, dst, src, Oreg op) ->
      fprintf fmt "\tmove %a %a\n" print_register A1 print_register src;
      fprintf fmt "\tmove %a %a\n" print_register A2 print_register op;
      fprintf fmt "\tla   W15 mul\n";
      fprintf fmt "\tjmp  W15 %a\n" print_register RA;
      fprintf fmt "\tmove %a W7\n" print_register dst
  | Arith (Mul, dst, src, Oimm op) ->
      fprintf fmt "\tmove %a %a\n" print_register A1 print_register src;
      fprintf fmt "\tli %a %d\n" print_register A2 op;
      fprintf fmt "\tla   W15 mul\n";
      fprintf fmt "\tjmp  W15 %a\n" print_register RA;
      fprintf fmt "\tmove %a W7\n" print_register dst
  | Arith (Div, dst, src, Oreg op) ->
      fprintf fmt "\tmove %a %a\n" print_register A1 print_register src;
      fprintf fmt "\tmove %a %a\n" print_register A2 print_register op;
      fprintf fmt "\tla   W15 div\n";
      fprintf fmt "\tjmp  W15 %a\n" print_register RA;
      fprintf fmt "\tmove %a W7\n" print_register dst
  | Arith (Div, dst, src, Oimm op) ->
      fprintf fmt "\tmove %a %a\n" print_register A1 print_register src;
      fprintf fmt "\tli %a %d\n" print_register A2 op;
      fprintf fmt "\tla   W15 div\n";
      fprintf fmt "\tjmp  W15 %a\n" print_register RA;
      fprintf fmt "\tmove %a W7\n" print_register dst
  | Arith (Rem, dst, src, Oreg op) ->
      fprintf fmt "\tmove %a %a\n" print_register A1 print_register src;
      fprintf fmt "\tmove %a %a\n" print_register A2 print_register op;
      fprintf fmt "\tla   W15 div\n";
      fprintf fmt "\tjmp  W15 %a\n" print_register RA;
      fprintf fmt "\tmove %a %a\n" print_register dst print_register A1
  | Arith (Rem, dst, src, Oimm op) ->
      fprintf fmt "\tmove %a %a\n" print_register A1 print_register src;
      fprintf fmt "\tli %a %d\n" print_register A2 op;
      fprintf fmt "\tla   W15 div\n";
      fprintf fmt "\tjmp  W15 %a\n" print_register RA;
      fprintf fmt "\tmove %a %a\n" print_register dst print_register A1

  | Arith (_,_,_,_) -> failwith "div/mod not supported"

  | SComp (Neq, dst, src1, src2) ->
      let l = Label.fresh () in
      fprintf fmt "\tla   W15 %s\n" l;
      fprintf fmt "\txor  %a %a %a\n"
        print_register dst print_register src1 print_register src2;
      fprintf fmt "\tjmpz W15\n";
      fprintf fmt "\tli   %a 1\n" print_register dst;
      fprintf fmt "%s:\n" l
  | SComp (Eq, dst, src1, src2) ->
      print_instruction genv fmt (SComp (Neq, dst, src1, src2));
      fprintf fmt "\tsubi %a 1 %a\n" print_register dst print_register dst
  | SComp (Ge, dst, src1, src2) ->
      let l1 = Label.fresh () in
      let l2 = Label.fresh () in
      fprintf fmt "\tla   W15 %s\n" l1;
      fprintf fmt "\tsub  %a %a %a\n"
        print_register dst print_register src1 print_register src2;
      fprintf fmt "\tjmpnc W15\n";
      fprintf fmt "\tli   %a 1\n" print_register dst;
      fprintf fmt "\tla   W15 %s\n" l2;
      fprintf fmt "\tjmp  W15\n";
      fprintf fmt "%s:\n" l1;
      fprintf fmt "\txor  %a %a %a\n" print_register dst print_register dst
      print_register dst;
      fprintf fmt "%s:\n" l2
  | SComp (Le, dst, src1, src2) ->
      print_instruction genv fmt (SComp (Ge, dst, src2, src1))
  | SComp (Gt, dst, src1, src2) ->
      let l1 = Label.fresh () in
      let l2 = Label.fresh () in
      fprintf fmt "\tla   W15 %s\n" l1;
      fprintf fmt "\tsub  %a %a %a\n"
        print_register dst print_register src1 print_register src2;
      fprintf fmt "\tjmpz W15\n";
      fprintf fmt "\tjmpnc W15\n";
      fprintf fmt "\tli   %a 1\n" print_register dst;
      fprintf fmt "\tla   W15 %s\n" l2;
      fprintf fmt "\tjmp  W15\n";
      fprintf fmt "%s:\n" l1;
      fprintf fmt "\txor  %a %a %a\n" print_register dst print_register dst
      print_register dst;
      fprintf fmt "%s:\n" l2
  | SComp (Lt, dst, src1, src2) ->
      print_instruction genv fmt (SComp (Gt, dst, src2, src1))


  | BComp (Neq, src1, src2, l) ->
      fprintf fmt "\tla   W15 %s\n" l;
      fprintf fmt "\txor  W10 %a %a\n"
        print_register src1 print_register src2;
      fprintf fmt "\tjmpnz W15\n";
  | BComp (Eq, src1, src2, l) ->
      fprintf fmt "\tla   W15 %s\n" l;
      fprintf fmt "\txor  W10 %a %a\n"
        print_register src1 print_register src2;
      fprintf fmt "\tjmpz W15\n";
  | BComp (Ge, src1, src2,l) ->
      fprintf fmt "\tla   W15 %s\n" l;
      fprintf fmt "\tsub  W10 %a %a\n"
        print_register src1 print_register src2;
      fprintf fmt "\tjmpc W15\n";
  | BComp (Le, src1, src2, l) ->
      print_instruction genv fmt (BComp (Ge, src2, src1, l))
  | BComp (Gt, src1, src2, l) ->
      let l1 = Label.fresh () in
      fprintf fmt "\tla   W15 %s\n" l1;
      fprintf fmt "\txor  W10 %a %a\n"
        print_register src1 print_register src2;
      fprintf fmt "\tjmpz W15\n";
      fprintf fmt "\tla   W15 %s\n" l;
      fprintf fmt "\tsub  W10 %a %a\n"
        print_register src1 print_register src2;
      fprintf fmt "\tjmpc W15\n";
      fprintf fmt "%s:\n" l1;
  | BComp (Lt, src1, src2, l) ->
      print_instruction genv fmt (BComp (Gt, src2, src1, l))


  | B0Comp (Eq, src, label) ->
      fprintf fmt "\tla    W15 %s\n" label;
      fprintf fmt "\tmove  %a %a\n"
        print_register src print_register src;
      fprintf fmt "\tjmpz  W15\n"

  | B0Comp (_,_,_) -> failwith "not supported"

  | Neg (dst,src) ->
      fprintf fmt "\tsub  %a %a %a\n" print_register dst print_register Zero print_register src
  | B s | J s ->
      fprintf fmt "\tla   W15 %s\n" s;
      fprintf fmt "\tjmp  W15\n"
  | Jal s ->
      fprintf fmt "\tla   W15 %s\n" s;
      fprintf fmt "\tjmp  W15 %a\n" print_register RA
  | Jr r ->
      fprintf fmt "\tjmp  %a\n" print_register r
  | Syscall ->
      fprintf fmt "\tla   W15 syscall\n";
      fprintf fmt "\tjmp  W15 W7\n"
  | Label s ->
      fprintf fmt "%s:\n" s

(*let print_data fmt = function
  | Asciiz (l, s) -> 
      fprintf fmt "%s:\t.asciiz %S\n" l s
  | Word (l, n) ->
      fprintf fmt "%s:\t.word %d\n" l n*)


let add_genv (n,genv,fmt) x = match x with
  | Asciiz (l, s) ->
      fprintf fmt "\tli   W15 %d\n" n;
      fprintf fmt "\tsh   W15 %a\n" print_register Zero;
      (n+1,Smap.add l n genv,fmt) (* not supported but we add 0 : empty string *)
  | Word (l, v) -> 
      fprintf fmt "\tli   W10 %d\n" v;
      fprintf fmt "\tli   W15 %d\n" n;
      fprintf fmt "\tsh   W15 W10\n";
      (n+1,Smap.add l n genv,fmt)

let print_program fmt p =
  let (n,genv,_) = List.fold_left add_genv (1,Smap.empty,fmt) p.data  in
  fprintf fmt "\txor  %a %a %a\n" print_register Zero print_register Zero print_register Zero;
  fprintf fmt "\tli   W9 %d\n" n;
  fprintf fmt "\tli   %a 65535\n" print_register SP;
  fprintf fmt "\tla   W15 main\n";
  fprintf fmt "\tjmp  W15 %a\n" print_register RA;

  fprintf fmt "end:\n";
  fprintf fmt "\tla   W15 end\n";
  fprintf fmt "\tjmp  W15\n";

  fprintf fmt "mul:\n"; (* A1*A2 -> W7 / A1 et A2 détruit *)
  fprintf fmt "\txor  W7 W7 W7\n";
  for i=0 to 15 do
    fprintf fmt "\tla   W15 mul_%d\n" i;
    fprintf fmt "\tsrl  %a %a\n" print_register A1 print_register A1;
    fprintf fmt "\tjmpnc W15\n";
    fprintf fmt "\taddu  W7 W7 %a\n" print_register A2;
    fprintf fmt "mul_%d:\n" i;
    if i<>15 then fprintf fmt "\taddu  %a %a %a\n" print_register A2 print_register A2
    print_register A2
  done;
  fprintf fmt "\tjmp    %a\n" print_register RA;

  fprintf fmt "div:\n"; (* A1/A2 -> R = A1, Q = W7 *)
  fprintf fmt "\tli   %a 1\n" print_register A0;
  fprintf fmt "\taddui %a %a -1\n" print_register SP print_register SP;
  fprintf fmt "\tsh   %a %a\n" print_register SP print_register Zero;
  (* le haut de la pile contient 0 si A1>0 et 1 sinon *)
  (* signes : A0=0xffff ou 0x1 *)
  fprintf fmt "\tsub  W15 %a %a\n" print_register A1 print_register Zero;
  fprintf fmt "\tla   W15 div_a\n";
  fprintf fmt "\tjmpc W15\n";
  fprintf fmt "\tsub  %a %a %a\n" print_register A0 print_register Zero print_register A0;
  fprintf fmt "\tsub  %a %a %a\n" print_register A1 print_register Zero print_register A1;
  fprintf fmt "\tli   W15 1\n";
  fprintf fmt "\tsh   %a W15\n" print_register SP;
  fprintf fmt "div_a:\n";
  fprintf fmt "\tsub  W15 %a %a\n" print_register A2 print_register Zero;
  fprintf fmt "\tla   W15 div_b\n";
  fprintf fmt "\tjmpc W15\n";
  fprintf fmt "\tsub  %a %a %a\n" print_register A0 print_register Zero print_register A0;
  fprintf fmt "\tsub  %a %a %a\n" print_register A2 print_register Zero
  print_register A2;
  fprintf fmt "div_b:\n";

  fprintf fmt "\txor  W7 W7 W7\n";
  fprintf fmt "div_0:\n";
  fprintf fmt "\tmove W10 %a\n" print_register A0;
  fprintf fmt "\tmove W11 %a\n" print_register A2;
  fprintf fmt "\tla   W15 div_end\n";
  fprintf fmt "\tsubu W5 %a W11\n" print_register A1;
  fprintf fmt "\tjmpnc W15\n";
  fprintf fmt "\tla   W15 div_1\n";
  for i=1 to 15 do
    fprintf fmt "\tmove W8 W5\n";
    if i<>1 then fprintf fmt "\taddu  W10 W10 W10\n";
    fprintf fmt "\taddu W11 W11 W11\n";
    fprintf fmt "\tjmpc W15\n";
    fprintf fmt "\tsubu W5 %a W11\n" print_register A1;
    if i<>15 then fprintf fmt "\tjmpnc W15\n";
  done;
  fprintf fmt "div_1:\n";
  fprintf fmt "\taddu W7 W7 W10\n";
  fprintf fmt "\tmove %a W8\n" print_register A1;
  fprintf fmt "\tla   W15 div_0\n";
  fprintf fmt "\tjmp  W15\n";
  fprintf fmt "div_end:\n";

  fprintf fmt "\txor  W11 W11 W11\n"; (* Remettre Zero à 0 *)

  (* Changer le signe du reste si nécessaire i.e. si A1<=0 *)
  fprintf fmt "\tla   W15 div_c\n";
  fprintf fmt "\tlh   W10 %a\n" print_register SP;
  fprintf fmt "\tjmpz W15\n";
  fprintf fmt "\tsub  %a %a %a\n" print_register A1 print_register Zero
  print_register A1;
  fprintf fmt "div_c:\n";
  fprintf fmt "\taddui %a %a 1\n" print_register SP print_register SP;

  fprintf fmt "\tjmp  %a\n" print_register RA;

  for i=0 to 15 do
    fprintf fmt "fun_output%d_0:\n" i;
    fprintf fmt "\tlh   %a %a\n" print_register V0 print_register SP;
    fprintf fmt "\taddui %a %a 1\n" print_register SP print_register SP;
    fprintf fmt "\toutput %d %a\n" i print_register V0;
    fprintf fmt "\tjmp  %a\n" print_register RA;
  
    fprintf fmt "fun_input%d_0:\n" i;
    fprintf fmt "\tinput %a %d\n" print_register V0 i;
    fprintf fmt "\tjmp  %a\n" print_register RA
  done;

  fprintf fmt "fun_sleep_0:\n";
  fprintf fmt "\tsleep\n";
  fprintf fmt "\tjmp  %a\n" print_register RA;

  fprintf fmt "syscall:\n";

  fprintf fmt "\tla   W10 syscall_print_int\n";
  fprintf fmt "\tli   W15 1\n";
  fprintf fmt "\txor  W15 W15 %a\n" print_register V0;
  fprintf fmt "\tjmpz W10\n";

  fprintf fmt "\tla   W10 syscall_print_newline\n";
  fprintf fmt "\tli   W15 4\n";
  fprintf fmt "\txor  W15 W15 %a\n" print_register V0;
  fprintf fmt "\tjmpz W10\n";

  fprintf fmt "\tla   W10 syscall_read_int\n";
  fprintf fmt "\tli   W15 5\n";
  fprintf fmt "\txor  W15 W15 %a\n" print_register V0;
  fprintf fmt "\tjmpz W10\n";

  fprintf fmt "\tla   W10 syscall_sbrk\n";
  fprintf fmt "\tli   W15 9\n";
  fprintf fmt "\txor  W15 W15 %a\n" print_register V0;
  fprintf fmt "\tjmpz W10\n";

  fprintf fmt "syscall_print_int:\n";
  fprintf fmt "\toutput 0 %a\n" print_register A0;
  fprintf fmt "\tjmp  W7\n";

  fprintf fmt "syscall_print_newline:\n";
  fprintf fmt "\tli   %a 1\n" print_register A0;
  fprintf fmt "\toutput 1 %a\n" print_register A0;
  fprintf fmt "\tjmp  W7\n";

  fprintf fmt "syscall_read_int:\n";
  fprintf fmt "\tinput %a 0\n" print_register V0;
  fprintf fmt "\tjmp  W7\n";

  fprintf fmt "syscall_sbrk:\n";
  fprintf fmt "\tmove %a W9\n" print_register V0;
  fprintf fmt "\taddu W9 W9 %a\n" print_register A0;
  fprintf fmt "\tjmp  W7\n";


  List.iter (print_instruction genv fmt) p.text;

