open Mips open Typing exception Very_bad_error of string (* Convention pour les registres : - a0, a1, a2, a3 : contiennent les (éventuels) 4 premiers arguments de la fonction - v0 : contient la valeur de retour des fonctions (rien de particulier pour un constructeur) - v0-v1, t0-t9, s0-s1 : utilisés pour les calculs Tous les registres doivent être sauvés par l'appellant Les registres a0, a1, a2, a3 sont susceptibles d'être modifiés par la fonction appellée. **sauf dans le cas où a0 représente this** !! *) (* Environnement pour accéder aux variables *) type whereis_var = | VGlobal | VStack of int (* position relative à $fp *) | VStackByRef of int | VRegister of register | VRegisterByRef of register type cg_env = { c_penv : env; c_names : whereis_var Smap.t; c_ret_ref : bool; c_fp_used : int; c_save_regs : register list; } let env_push n e = { c_penv = e.c_penv; c_names = e.c_names; c_ret_ref = e.c_ret_ref; c_fp_used = e.c_fp_used + n; c_save_regs = e.c_save_regs } let globals_env = ref Smap.empty let strings = Hashtbl.create 12 (* string -> label *) (* Identifiants uniques pour les machins - essentiellement labels *) let id = let last = ref 0 in fun prefix -> (last := !last + 1; prefix ^ (string_of_int !last)) let rec expr_does_call e = match e.te_desc with | TEInt _ | TENull | TEThis | TEIdent _ -> false | TEAssign(a, b) -> expr_does_call a || expr_does_call b | TECallFun (_, _, _) -> true | TECallVirtual (_, _, _, _) -> true | TEUnary (_, e) -> expr_does_call e | TEBinary (a, _, b) -> expr_does_call a || expr_does_call b | TEMember (e, _) -> expr_does_call e | TEPointerCast(e, _) -> expr_does_call e | TENew(_, _, _) -> true let rec stmt_does_call = function | TSEmpty | TSReturn(None) -> false | TSExpr(e) -> expr_does_call e | TSIf (e, sa, sb) -> expr_does_call e || stmt_does_call sa || stmt_does_call sb | TSWhile(e, s) -> expr_does_call e || stmt_does_call s | TSFor(e, f, g, s) -> (List.exists expr_does_call e) || (match f with | None -> false | Some k -> expr_does_call k) || (List.exists expr_does_call g) || stmt_does_call s | TSBlock(k) -> List.exists stmt_does_call k | TSReturn(Some k) -> expr_does_call k | TSDeclare(TClass _, _) -> true | TSDeclare (_, _) -> false | TSDeclareAssignExpr(_, _, e) -> expr_does_call e | TSDeclareAssignConstructor(_, _, _, _) -> true | TSWriteCout(l) -> List.exists (function | TSEExpr e -> expr_does_call e | TSEStr _ -> false) l (* Génération de code des machins *) type expr_type = | Addr (* top register contains address of value *) | Copy (* top register contains copy of value *) | Value of register (* other register is home to the value *) let cr r a = match a with (* conditionnally read *) | Addr -> lw r areg (0, r) | Copy -> nop | Value(k) -> if r <> k then move r k else nop let use_regs = [ v0; v1; t0; t1; t2; t3; t4; t5; t6; t7; t8; t9 ] let spare_reg = s0 let spare_reg2 = s1 let saver env save_regs = let sc, lc, env2 = List.fold_left (fun (code, more_code, env) r -> let new_fp_used = env.c_fp_used + 4 in let pos = - new_fp_used in code ++ sw r areg (pos, fp), lw r areg (pos, fp) ++ more_code, { c_penv = env.c_penv; c_names = Smap.map (function | VRegister k when k = r -> VStack (pos) | VRegisterByRef k when k = r -> VStackByRef(pos) | a -> a) env.c_names; c_ret_ref = env.c_ret_ref; c_fp_used = new_fp_used; c_save_regs = (List.filter (fun k -> k <> r) env.c_save_regs) } ) (nop, nop, env) save_regs in let d = env2.c_fp_used - env.c_fp_used in (if d = 0 then nop else la sp areg (-env2.c_fp_used, fp)) ++ sc, lc ++ (if d = 0 then nop else la sp areg (-env.c_fp_used, fp)), env2 (* Convention : doit garder $sp invariant ; renvoie le résultat dans le premier registre de free_regs on doit toujours avoir lors d'un appel à cette fonction, $fp - env.c_fp_used = $sp *) let rec gen_expr env free_regs save_regs e = (* register management *) let r = List.hd free_regs in (* register where to put result *) let more = List.tl free_regs in (* the generator... *) match e.te_desc with | TEInt(k) -> li r k, Copy | TENull -> move r zero, Copy | TEThis -> (* convention : this is always the first argument, so in a0 *) move r a0, Copy | TEIdent(i) -> begin match Smap.find i env.c_names with | VGlobal -> la r alab i, Addr | VStack(i) -> la r areg (i, fp), Addr | VStackByRef(i) -> lw r areg (i, fp), Addr | VRegister(k) -> nop, Value k | VRegisterByRef(k) when k <> r -> move r k, Addr | _ -> assert false end | TEAssign(e1, e2) -> begin match more with | [] -> let t1, ae1 = gen_expr env free_regs save_regs e1 in let t2, ae2 = gen_expr (env_push 4 env) free_regs save_regs e2 in let t2 = t2 ++ cr r ae2 in begin match ae1 with | Addr -> t1 ++ push r ++ t2 ++ pop spare_reg ++ sw r areg (0, spare_reg), Copy | Value k when t1 = nop && k <> r -> t2 ++ move k r, Copy | _ -> assert false end | b::_ -> let t1, ae1 = gen_expr env more (r::save_regs) e1 in let t2, ae2 = gen_expr env free_regs save_regs e2 in let t2 = t2 ++ cr r ae2 in begin match ae1 with | Addr -> t2 ++ t1 ++ sw r areg (0, b), Copy | Value k when t1 = nop && k <> r -> t2 ++ move k r, Copy | _ -> assert false end end | TECallFun(id, args, b) -> let code_save_regs, code_restore_regs, env_regs_saved = saver env save_regs in let args_code, su = code_for_args env_regs_saved args [ a0; a1; a2; a3 ] in code_save_regs ++ args_code ++ jal id ++ (if su <> 0 then popn su else nop) ++ (if r <> v0 then move r v0 else nop) ++ code_restore_regs, if b then Addr else Copy | TECallVirtual(obj, fi, args, b) -> let code_save_regs, code_restore_regs, env_regs_saved = saver env save_regs in let args_code, su = code_for_args env_regs_saved args [ a1; a2; a3 ] in let code2, a = gen_expr (env_push su env_regs_saved) (a0::use_regs) [] obj in assert (a = Addr); code_save_regs ++ args_code ++ code2 ++ lw v0 areg (0, a0) ++ lw v0 areg (fi, v0) ++ jalr v0 ++ (if su <> 0 then popn su else nop) ++ (if r <> v0 then move r v0 else nop) ++ code_restore_regs, if b then Addr else Copy | TEUnary (x, e) -> let t, a = gen_expr env free_regs save_regs e in begin match x with | Ast.Deref -> t ++ cr r a, Addr | Ast.Ref -> assert (a = Addr); t, Copy | Ast.Plus -> t ++ cr r a, Copy | Ast.Minus -> t ++ cr r a ++ neg r r, Copy | Ast.Not -> t ++ cr r a ++ not_ r r, Copy | Ast.PreIncr -> begin match a with | Addr -> t ++ lw spare_reg areg (0, r) ++ add spare_reg spare_reg oi 1 ++ sw spare_reg areg (0, r), Addr | Value v when t = nop && v <> r -> add v v oi 1 ++ move r v, Copy | _ -> assert false end | Ast.PreDecr -> begin match a with | Addr -> t ++ lw spare_reg areg (0, r) ++ sub spare_reg spare_reg oi 1 ++ sw spare_reg areg (0, r), Addr | Value v when t = nop && v <> r -> sub v v oi 1 ++ move r v, Copy | _ -> assert false end | Ast.PostIncr -> begin match a with | Addr -> t ++ move spare_reg r ++ lw spare_reg2 areg(0, spare_reg) ++ move r spare_reg2 ++ add spare_reg2 spare_reg2 oi 1 ++ sw spare_reg2 areg(0, spare_reg), Copy | Value v when t = nop && v <> r -> move r v ++ add v v oi 1, Copy | _ -> assert false end | Ast.PostDecr -> begin match a with | Addr -> t ++ move spare_reg r ++ lw spare_reg2 areg(0, spare_reg) ++ move r spare_reg2 ++ sub spare_reg2 spare_reg2 oi 1 ++ sw spare_reg2 areg(0, spare_reg), Copy | Value v when t = nop && v <> r -> move r v ++ sub v v oi 1, Copy | _ -> assert false end end | TEBinary(e1, op, e2) when op <> Ast.Lor && op <> Ast.Land -> let rb, precode = match more with | [] -> let t1, ae1 = gen_expr (env_push 4 env) free_regs save_regs e1 in let t2, ae2 = gen_expr env free_regs save_regs e2 in let t1 = t1 ++ cr r ae1 in let t2 = t2 ++ cr r ae2 in spare_reg, t2 ++ push r ++ t1 ++ pop spare_reg | b::_ -> let t1, ae1 = gen_expr env free_regs save_regs e1 in let t2, ae2 = gen_expr env more (r::save_regs) e2 in let t1 = t1 ++ cr r ae1 in let t2 = t2 ++ cr b ae2 in b, t1 ++ t2 in precode ++ (match op with | Ast.Add -> add r r oreg rb | Ast.Sub -> sub r r oreg rb | Ast.Mul -> mul r r oreg rb | Ast.Div -> div r r oreg rb | Ast.Modulo -> rem r r oreg rb | Ast.Equal -> seq r r rb | Ast.NotEqual -> sne r r rb | Ast.Lt -> slt r r rb | Ast.Le -> sle r r rb | Ast.Gt -> sgt r r rb | Ast.Ge -> sge r r rb | _ -> assert false ), Copy | TEBinary(e1, op, e2) (* when op = Ast.Lor || op = Ast.Land *) -> let t1, ae1 = gen_expr env free_regs save_regs e1 in let t2, ae2 = gen_expr env free_regs save_regs e2 in let t1 = t1 ++ cr r ae1 in let t2 = t2 ++ cr r ae2 in let lazy_lbl = id "_lazy" in t1 ++ (if op = Ast.Lor then bnez r lazy_lbl else beqz r lazy_lbl) ++ t2 ++ label lazy_lbl ++ sne r r zero, Copy | TEMember(e, i) -> let c, a = gen_expr env free_regs save_regs e in if i <> 0 then begin assert (a = Addr); c ++ la r areg (i, r), Addr end else c, a | TEPointerCast(e, i) -> let c, a = gen_expr env free_regs save_regs e in c ++ cr r a ++ (if i = 0 then nop else la r areg (i, r)), Copy | TENew(cls, constr, args) -> let code_save_regs, code_restore_regs, env_regs_saved = saver env save_regs in let args_code, stack_used = code_for_args env_regs_saved args [ a1; a2; a3 ] in let alloc = li v0 9 ++ li a0 cls.tc_size ++ syscall in code_save_regs ++ args_code ++ alloc ++ move a0 v0 ++ jal constr ++ move r a0 ++ (if stack_used <> 0 then popn stack_used else nop) ++ code_restore_regs, Copy and code_for_args env arg_list regs = let code, _, u = List.fold_left (fun (code, r, u) (arg, byref) -> match r with | [] -> let c, addr = gen_expr (env_push u env) use_regs [] arg in assert (addr = Addr || not byref); c ++ (if not byref then cr v0 addr else nop) ++ push v0 ++ code, regs, u + 4 | reg::more_regs -> let c, addr = gen_expr (env_push u env) (reg::use_regs) [] arg in assert (addr = Addr || not byref); c ++ (if not byref then cr reg addr else nop) ++ code, more_regs, u ) (nop, regs, 0) arg_list in code, u let gen_expr_v0 env = gen_expr env use_regs env.c_save_regs let rec gen_stmt env = function | TSEmpty -> nop, nop, env | TSExpr(e) -> comment "expr" ++ (fst (gen_expr_v0 env e)), nop, env | TSIf(cond, s1, s2) -> let c, a = gen_expr_v0 env cond in let l_else = id "_cond_else" in let l_end = id "_cond_end" in let c_then, d_then, _ = gen_stmt env s1 in let c_else, d_else, _ = gen_stmt env s2 in comment "if" ++ c ++ cr v0 a ++ beqz v0 l_else ++ c_then ++ b l_end ++ label l_else ++ c_else ++ label l_end, d_then ++ d_else, env | TSWhile(cond, body) -> let c, a = gen_expr_v0 env cond in let l_begin = id "_while_begin" in let l_cond = id "_while_cond" in let c_body, d_body, _ = gen_stmt env body in comment "while" ++ b l_cond ++ label l_begin ++ c_body ++ label l_cond ++ c ++ cr v0 a ++ bnez v0 l_begin, d_body, env | TSFor(before, cond, after, body) -> let l_begin = id "_for_begin" in let l_cond = id "_for_cond" in let c_before = List.fold_left (fun code expr -> let c, _ = gen_expr_v0 env expr in code ++ c) nop before in let c_after = List.fold_left (fun code expr -> let c, _ = gen_expr_v0 env expr in code ++ c) nop after in let c_cond = match cond with | None -> b l_begin | Some x -> let c, a = gen_expr_v0 env x in c ++ cr v0 a ++ bnez v0 l_begin in let c_body, d_body, _ = gen_stmt env body in comment "for" ++ c_before ++ b l_cond ++ label l_begin ++ c_body ++ c_after ++ label l_cond ++ c_cond, d_body, env | TSBlock(b) -> let c, d = gen_block env b in comment "block" ++ c, d, env | TSReturn (None) -> comment "return" ++ b "_return", nop, env | TSReturn (Some e) -> let c, a = gen_expr_v0 env e in assert (a = Addr || not env.c_ret_ref); comment "return" ++ c ++ (if not env.c_ret_ref then cr v0 a else nop) ++ b "_return", nop, env | TSDeclare (ty, id) -> let s = type_size env.c_penv ty in let new_fp_used = env.c_fp_used + s in let pos = - new_fp_used in let code = match ty with | TClass(i) -> let c = get_c env.c_penv i in let cproto = List.find (fun p -> p.tp_ret_type = None && p.tp_name = i && p.tp_args = []) c.tc_methods in la sp areg (pos, fp) ++ la a0 areg (pos, fp) ++ jal cproto.tp_unique_ident | _ -> la sp areg (pos, fp) ++ sw zero areg (0, sp) in comment ("declare " ^ id) ++ code, nop, { c_penv = env.c_penv; c_names = Smap.add id (VStack pos) env.c_names; c_ret_ref = env.c_ret_ref; c_fp_used = new_fp_used; c_save_regs = env.c_save_regs } | TSDeclareAssignConstructor(cls, id, constr, args) -> let new_fp_used = env.c_fp_used + cls.tc_size in let pos = - new_fp_used in let code = let code_save_regs, code_restore_regs, env_regs_saved = saver (env_push cls.tc_size env) env.c_save_regs in let args_code, su = code_for_args env_regs_saved args [ a1; a2; a3 ] in la sp areg (pos, fp) ++ code_save_regs ++ args_code ++ la a0 areg(pos, fp) ++ jal constr ++ (if su <> 0 then popn su else nop) ++ code_restore_regs in comment ("declare " ^ id) ++ code, nop, { c_penv = env.c_penv; c_names = Smap.add id (VStack pos) env.c_names; c_ret_ref = env.c_ret_ref; c_save_regs = env.c_save_regs; c_fp_used = new_fp_used; } | TSDeclareAssignExpr ((ty, ref), id, e) -> let s = if ref then 4 else type_size env.c_penv ty in assert (s = 4); let new_fp_used = env.c_fp_used + 4 in let pos = - new_fp_used in let code, a = gen_expr_v0 (env_push 4 env) e in assert (a = Addr || not ref); comment ("declare " ^ id) ++ la sp areg (pos, fp) ++ code ++ (if not ref then cr v0 a else nop) ++ sw v0 areg (pos, fp), nop, { c_penv = env.c_penv; c_names = Smap.add id (if ref then VStackByRef pos else VStack pos) env.c_names; c_ret_ref = env.c_ret_ref; c_fp_used = new_fp_used; c_save_regs = env.c_save_regs } | TSWriteCout(sl) -> let save = List.mem a0 env.c_save_regs in let env = if save then env_push 4 env else env in let text1, data1 = List.fold_left (fun (text, data) s -> match s with | TSEExpr(e) -> let t, a = gen_expr_v0 env e in text ++ t ++ cr v0 a ++ move a0 v0 ++ li v0 1 ++ syscall, data | TSEStr(s) -> let l, d = if Hashtbl.mem strings s then Hashtbl.find strings s, nop else let l = id "_s" in Hashtbl.add strings s l; l, label l ++ asciiz s in text ++ la a0 alab l ++ li v0 4 ++ syscall, data ++ d) (nop, nop) sl in comment "cout<<..." ++ (if save then push a0 else nop) ++ text1 ++ (if save then pop a0 else nop), data1, env and gen_block env b = let text, data, fin_env = List.fold_left (fun (t, d, e) s -> let tt, dd, e = gen_stmt e s in t ++ tt, d ++ dd, e) (nop, nop, env) b in let n = (fin_env.c_fp_used - env.c_fp_used) in text ++ (if n = 0 then nop else la sp areg (-env.c_fp_used, fp)), data let gen_decl tenv decl = match decl with | TDGlobal(ty, id) -> globals_env := Smap.add id VGlobal !globals_env; let bytes = type_size tenv ty in nop, (label id) ++ (dword (let rec a n = if n > 0 then 0::(a (n-4)) else [] in a bytes)) | TDFunction(proto, block) -> let regs_for_args = match proto.tp_class with | None -> [ a0; a1; a2; a3 ] | Some k -> [ a1; a2; a3 ] in let names, _, free_regs = List.fold_left (fun (env, p, regs) ((ty, r), id) -> let s = (if r then 4 else type_size tenv ty) in assert (s = 4); match regs with | reg::more_regs -> Smap.add id (if r then VRegisterByRef reg else VRegister reg) env, p, more_regs | _ -> Smap.add id (if r then VStackByRef p else VStack p) env, p + 4, regs ) (!globals_env, 0, regs_for_args) proto.tp_args in let env = { c_penv = tenv; c_names = names; c_ret_ref = (match proto.tp_ret_type with | None -> false | Some(_, r) -> r); c_fp_used = 8; c_save_regs = List.filter (fun r -> not (List.mem r free_regs)) [a0; a1; a2; a3]; } in let save_code, unsave_code, env2 = saver env (List.filter (fun x -> x <> a0 || proto.tp_class = None) env.c_save_regs) in let code_for_constructor, does_calls = match proto.tp_ret_type with | Some _ -> nop, (List.exists stmt_does_call block) | None -> let cls_name = (match proto.tp_class with | Some k -> k | None -> assert false) in jal (cls_name ^ "0"), true in let code_for_virtual = match proto.tp_virtual with | Some (c, _) when c.h_pos <> 0 -> la a0 areg (-c.h_pos, a0) | _ -> nop in let code1 = label proto.tp_unique_ident ++ sw fp areg (-4, sp) ++ sw ra areg (-8, sp) ++ move fp sp ++ la sp areg (-8, fp) in if does_calls then let text, data = gen_block env2 block in code1 ++ code_for_virtual ++ save_code ++ text ++ b "_return", data else let text, data = gen_block env block in code1 ++ code_for_constructor ++ code_for_virtual ++ text ++ b "_return", data | TDClass(c) -> let calls_something = ref false in (* Call default constructor of parent classes *) let code_parents = List.fold_left (fun code parent -> let cn = parent.h_class in let c = get_c tenv cn in let proto = List.find (fun p -> p.tp_ret_type = None && p.tp_args = [] && p.tp_name = cn) c.tc_methods in calls_something := true; code ++ (if parent.h_pos <> 0 then la a0 areg(parent.h_pos, a0) else nop) ++ jal proto.tp_unique_ident ++ (if parent.h_pos <> 0 then lw a0 areg(0, sp) else nop) ) nop c.tc_hier.h_supers in let code_parents = if code_parents <> nop then push a0 ++ code_parents ++ popn 4 else nop in (* Build vtables and build constructor *) let rec make_vtables hh = (* calculate vtable contents *) let vtable_size = List.fold_left (fun k (p, _) -> max k (p+4)) 0 hh.h_vtable in let vtable_as_array = Array.make (vtable_size / 4) "_nothing" in List.iter (fun (p, s) -> vtable_as_array.(p/4) <- s.tp_unique_ident) hh.h_vtable; let vt_l = Array.to_list vtable_as_array in (* code for vtable initialization *) let vtable = if vt_l = [] then nop else label ("_vt_" ^ c.tc_name ^ "_as_" ^ hh.h_class) ++ address vt_l in let constructor_code = if vt_l = [] then nop else la a1 alab ("_vt_" ^ c.tc_name ^ "_as_" ^ hh.h_class) ++ sw a1 areg (hh.h_pos, a0) in (* code for subclasses vtable initialization *) List.fold_left (fun (vt, cc) sup -> let mvt, mcc = make_vtables sup in vt ++ mvt, cc ++ mcc) (vtable, constructor_code) hh.h_supers in let vtables, vtable_init_code = make_vtables c.tc_hier in (* Initialize members *) let init_code_proper = Smap.fold (fun _ (ty, pos) code -> (match ty with | TClass(s) -> let cs = get_c tenv s in let proto = List.find (fun p -> p.tp_ret_type = None && p.tp_args = [] && p.tp_name = s) cs.tc_methods in calls_something := true; push a0 ++ (if pos <> 0 then la a0 areg (pos, a0) else nop) ++ jal proto.tp_unique_ident ++ pop a0 | _ -> sw zero areg (pos, a0) ) ++ code) c.tc_members nop in (* Put it all together *) label (c.tc_name ^ "0") ++ (if !calls_something then push ra else nop) ++ code_parents ++ vtable_init_code ++ init_code_proper ++ (if !calls_something then pop ra else nop) ++ jr ra, vtables let generate p = try let text, data = List.fold_left (fun (text, data) decl -> let more_text, more_data = gen_decl p.prog_env decl in text ++ more_text, data ++ more_data) (nop, nop) p.prog_decls in let text = label "main" ++ jal p.prog_main ++ li v0 10 ++ syscall ++ label "_return" ++ move sp fp ++ lw fp areg (-4, sp) ++ lw ra areg (-8, sp) ++ label "_nothing" ++ jr ra ++ text in { text = text; data = data } with | Assert_failure (k, a, b) -> raise (Very_bad_error ( "(unexpected) Assertion failure: "^k^" at "^(string_of_int a)^":"^(string_of_int b))) | Not_found -> raise (Very_bad_error ("(unexpected) Not found")) | Invalid_argument(k) -> raise (Very_bad_error ("(unexpected) Invalid argument: "^k)) | Match_failure(k, a, b) -> raise (Very_bad_error ( "(unexpected) Match failure: "^k^" at "^(string_of_int a)^":"^(string_of_int b))) | Stack_overflow -> raise (Very_bad_error ("(unexpected) Stack overflow")) | _ -> raise (Very_bad_error ("(unexpected) Other error"))