From 85bc61cb7fa8f4b9af78064cb65fbad49a109d5f Mon Sep 17 00:00:00 2001 From: Alex AUVOLAT Date: Thu, 2 Jan 2014 22:30:11 +0100 Subject: Started CPU implementation. --- .gitignore | 3 +- README | 12 ++-- cpu/Makefile | 5 +- cpu/alu.ml | 17 ++++++ cpu/cpu.ml | 157 ++++++++++++++++++++++++++++++++++++++++++++++++++++ cpu/netlist_gen.ml | 154 ++++++++++++++++++++++++++++----------------------- cpu/netlist_gen.mli | 5 ++ cpu/prog_rom0.rom | 3 + csim/load.c | 10 ++-- csim/sim.c | 4 +- csim/sim.h | 2 +- plan_micro.pdf | Bin 76513 -> 76611 bytes plan_micro.tm | 54 +++++++++++------- sched/Makefile | 10 ++++ tests/Makefile | 2 +- tests/decode7.rom | 2 +- 16 files changed, 334 insertions(+), 106 deletions(-) create mode 100644 cpu/cpu.ml create mode 100644 cpu/prog_rom0.rom create mode 100644 sched/Makefile diff --git a/.gitignore b/.gitignore index 119a01b..2b5941f 100644 --- a/.gitignore +++ b/.gitignore @@ -1,6 +1,7 @@ *.swp */_build/* -*/*.byte +*.byte +*.native csim/csim *.o *.ps diff --git a/README b/README index 5475dbe..7523ba5 100644 --- a/README +++ b/README @@ -228,12 +228,16 @@ decode7_128, and use the ROM data from the file specified on the command line. The format of a ROM file is as follows : -
+ -The data is composed of 2^(address width) values separated by spaces. If they -have no prefix, they are read as binary. If they have a / prefix, they are read -as decimal (this enables the use of whichever representation is preferred). +The data is composed of n values separated by spaces. If they have no prefix, +they are read as binary. If they have a / prefix, they are read as decimal. If +they have a x prefix, they are read as hexadecimal (this enables the use of +whichever representation is preferred). + +When the ROM is used, all the extra words (those needed by the simulator but +not defined in the ROM file) will be considered zeroes. diff --git a/cpu/Makefile b/cpu/Makefile index 74bfbae..1ab6397 100644 --- a/cpu/Makefile +++ b/cpu/Makefile @@ -3,10 +3,11 @@ GENERATOR=netlist_ast.ml netlist_gen.ml netlist_gen.mli AUXILLARY=alu.ml -SCHED=../sched/main.byte +SCHED=../sched/main.native SIM=../csim/csim -all: cpu_opt.sim +all: _build/cpu_opt.dumb + $(SIM) -rom ROM0 prog_rom0.rom $< %.sim: _build/%.dumb $(SIM) $< diff --git a/cpu/alu.ml b/cpu/alu.ml index 0a0c00f..cf33cd2 100644 --- a/cpu/alu.ml +++ b/cpu/alu.ml @@ -12,5 +12,22 @@ let rec nadder n a b c_in = let s_n1, c_out = nadder (n-1) (a % (1, n-1)) (b % (1, n-1)) c_n1 in s_n ++ s_n1, c_out +let nadder_nocarry n a b = + let a, b = nadder n a b (const "0") in + ignore b a +let rec rep n k = + if n = 1 then k + else + let s = rep (n/2) k in + if n mod 2 = 0 then s ++ s else s ++ s ++ k + +let rec sign_extend n_a n_dest a = + a ++ rep (n_dest - n_a) (a ** (n_a - 1)) + +let rec eq_c n v c = (* v is a value, c is a constant *) + if n = 1 then + if c = 1 then v else not v + else + (eq_c 1 (v ** 0) (c mod 2)) ^& (eq_c (n-1) (v % (1, n-1)) (c/2)) diff --git a/cpu/cpu.ml b/cpu/cpu.ml new file mode 100644 index 0000000..13f3f8b --- /dev/null +++ b/cpu/cpu.ml @@ -0,0 +1,157 @@ +open Netlist_gen +open Alu + +let zeroes n = + const (String.make n '0') + +let one n = + const "1" ++ zeroes (n-1) +let two n = + const "01" ++ zeroes (n-2) + + +let cpu_ram ra we wa d = + (* Ram chip has word size = 8 bits and address size = 16 bits + 0x0000 to 0x3FFF is ROM0 + 0x4000 to 0x7FFF is unused, reserved for MMIO + 0x8000 to 0xFFFF is RAM *) + let ra_hi1 = ra ** 15 in + let ra_lo1 = ra % (0, 14) in + let ra_hi2 = ra ** 14 in + let ra_lo2 = ra % (0, 13) in + let read_rom = (not ra_hi1) ^& (not ra_hi2) in + let read_ram = ra_hi1 in + let wa_hi1 = wa ** 15 in + let wa_lo1 = wa % (0, 14) in + let we_ram = we ^& wa_hi1 in + + let rd_rom = rom "ROM0" 14 8 ra_lo2 in + let rd_ram = ram 15 8 ra_lo1 we_ram wa_lo1 d in + mux read_ram (mux read_rom (zeroes 8) rd_rom) rd_ram + +let r0 = zeroes 16 +let r1, save_r1 = loop 16 +let r2, save_r2 = loop 16 +let r3, save_r3 = loop 16 +let r4, save_r4 = loop 16 +let r5, save_r5 = loop 16 +let r6, save_r6 = loop 16 +let r7, save_r7 = loop 16 + +let cpu_get_reg i = + let a00 = mux (i ** 0) r0 r1 in + let a01 = mux (i ** 0) r2 r3 in + let a02 = mux (i ** 0) r4 r5 in + let a03 = mux (i ** 0) r6 r7 in + let a10 = mux (i ** 1) a00 a01 in + let a11 = mux (i ** 1) a02 a03 in + mux (i ** 3) a10 a00 + +let save_cpu_regs wr wd = + let r1_prev = reg 16 r1 in + let r2_prev = reg 16 r2 in + let r3_prev = reg 16 r3 in + let r4_prev = reg 16 r4 in + let r5_prev = reg 16 r5 in + let r6_prev = reg 16 r6 in + let r7_prev = reg 16 r7 in + + save_r1 (mux (eq_c 3 wr 1) r1_prev wd) ^. + save_r2 (mux (eq_c 3 wr 2) r1_prev wd) ^. + save_r3 (mux (eq_c 3 wr 3) r1_prev wd) ^. + save_r4 (mux (eq_c 3 wr 4) r1_prev wd) ^. + save_r5 (mux (eq_c 3 wr 5) r1_prev wd) ^. + save_r6 (mux (eq_c 3 wr 6) r1_prev wd) ^. + save_r7 (mux (eq_c 3 wr 7) r1_prev wd) ^. + r0 + +(* +let ticker n = + let k, save_k = loop n in + let s = reg n k in + let next = nadder_nocarry n s (one n) in + ignore (save_k next) s + +let tick1 = ticker 1 +let tick2 = ticker 2 +*) + +let rl, rh, i, ex, exf, pc = + let next_read, save_next_read = loop 1 in + let read = not (reg 1 (not next_read)) in + let next_pc, save_next_pc = loop 16 in + let pc = reg 16 next_pc in + + let ra, we, wa, d = zeroes 16, zeroes 1, zeroes 16, zeroes 8 in + let ram_read, save_ram_read = loop 8 in + + (* Read instruction low when read is set and instruction high on next tick *) + let next_read_ihi, save_next_read_ihi = loop 1 in + let read_ihi = reg 1 next_read_ihi in + let read_ilow = read in + + let ra = mux read_ilow ra pc in + let ilow = reg 8 (mux read_ilow (zeroes 8) ram_read) in + let ra = mux read_ihi ra (nadder_nocarry 16 pc (one 16)) in + let ihi = mux read_ihi (zeroes 8) ram_read in + + let exec = ignore (save_next_read_ihi read_ilow) read_ihi in + let i = ilow ++ ihi in + + (* Execute instruction if exec is set *) + let next_pc = nadder_nocarry 16 pc (two 16) in + let exec_finished = exec in + + let i_i = i % (11, 15) in + let i_r = i % (8, 10) in + let i_ra = i % (5, 7) in + let i_rb = i % (2, 4) in + let i_f = i % (0, 1) in + let i_id = i % (0, 7) in + let i_jd = i % (0, 10) in + let i_kd = i % (0, 4) in + + (* registers *) + let v_r = cpu_get_reg i_r in + let v_ra = cpu_get_reg i_ra in + let v_rb = cpu_get_reg i_rb in + let wr = zeroes 3 in + let rwd = zeroes 16 in + + (* instruction : j *) + let instr_j = exec ^& eq_c 5 i_i 0b01000 in + let next_pc = mux instr_j next_pc (nadder_nocarry 16 pc (sign_extend 11 16 i_jd)) in + (* instruction : jal *) + let instr_jal = exec ^& eq_c 5 i_i 0b01001 in + let wr = mux instr_jal wr (const "011") in + let rwd = mux instr_jal rwd next_pc in + let next_pc = mux instr_jal next_pc (nadder_nocarry 16 pc (sign_extend 11 16 i_jd)) in + + save_cpu_regs wr rwd ^. + save_ram_read (cpu_ram ra we wa d) ^. + save_next_read exec_finished ^. + save_next_pc (mux exec_finished pc next_pc) ^. + read_ilow, read_ihi, i, exec, exec_finished, pc + +let p = + program + [] + [ + "read_ilow", 1, rl; + "read_ihi", 1, rh; + "instruction", 16, i; + "exec_instr", 1, ex; + "exec_finished", 1, exf; + "pc", 16, pc; + "r0", 16, r0; + "r1", 16, r1; + "r2", 16, r2; + "r3", 16, r3; + "r4", 16, r4; + "r5", 16, r5; + "r6", 16, r6; + "r7", 16, r7; + ] + +let () = Netlist_gen.print stdout p + diff --git a/cpu/netlist_gen.ml b/cpu/netlist_gen.ml index f721997..0c38b6f 100644 --- a/cpu/netlist_gen.ml +++ b/cpu/netlist_gen.ml @@ -15,12 +15,8 @@ let get_size p arg = match arg with let add p id eq size = assert (not (Env.mem id p.p_vars) || (Env.find id p.p_vars = size)); - let new_eqs = - if List.mem_assoc id p.p_eqs - then p.p_eqs - else (id, eq)::p.p_eqs - in - { p_eqs = new_eqs; + assert (not (List.mem_assoc id p.p_eqs)); + { p_eqs = (id, eq)::p.p_eqs; p_inputs = p.p_inputs; p_outputs = p.p_outputs; p_vars = Env.add id size p.p_vars } @@ -40,8 +36,16 @@ let loop s = p_vars = Env.add i s p.p_vars }), (fun v1 -> fun p -> - let x, p = v1 p in - (Avar i), add p i (Earg x) s) + (Avar i), + (if List.mem_assoc i p.p_eqs then p else + let x, p = v1 p in + add p i (Earg x) s)) + +let ignore v1 v2 = + fun p -> + let v1, p = v1 p in + v2 p +let ( ^. ) v1 v2 = ignore v1 v2 let const n = let l = String.length n in @@ -52,111 +56,123 @@ let const n = let ( ++ ) v1 v2 = let i = id "" in fun p -> - let x1, p = v1 p in - let x2, p = v2 p in - let sz1, sz2 = get_size p x1, get_size p x2 in - (Avar i), add p i (Econcat (x1, x2)) (sz1 + sz2) + if List.mem_assoc i p.p_eqs then Avar i, p else + let x1, p = v1 p in + let x2, p = v2 p in + let sz1, sz2 = get_size p x1, get_size p x2 in + (Avar i), add p i (Econcat (x1, x2)) (sz1 + sz2) let ( ^| ) v1 v2 = let i = id "" in fun p -> - let x1, p = v1 p in - let x2, p = v2 p in - let sz = get_size p x1 in - assert (sz = get_size p x2); - (Avar i), add p i (Ebinop (Or, x1, x2)) sz + if List.mem_assoc i p.p_eqs then Avar i, p else + let x1, p = v1 p in + let x2, p = v2 p in + let sz = get_size p x1 in + assert (sz = get_size p x2); + (Avar i), add p i (Ebinop (Or, x1, x2)) sz let ( ^^ ) v1 v2 = let i = id "" in fun p -> - let x1, p = v1 p in - let x2, p = v2 p in - let sz = get_size p x1 in - assert (sz = get_size p x2); - (Avar i), add p i (Ebinop (Xor, x1, x2)) sz + if List.mem_assoc i p.p_eqs then Avar i, p else + let x1, p = v1 p in + let x2, p = v2 p in + let sz = get_size p x1 in + assert (sz = get_size p x2); + (Avar i), add p i (Ebinop (Xor, x1, x2)) sz let ( ^& ) v1 v2 = let i = id "" in fun p -> - let x1, p = v1 p in - let x2, p = v2 p in - let sz = get_size p x1 in - assert (sz = get_size p x2); - (Avar i), add p i (Ebinop (And, x1, x2)) sz + if List.mem_assoc i p.p_eqs then Avar i, p else + let x1, p = v1 p in + let x2, p = v2 p in + let sz = get_size p x1 in + assert (sz = get_size p x2); + (Avar i), add p i (Ebinop (And, x1, x2)) sz let ( ^$ ) v1 v2 = let i = id "" in fun p -> - let x1, p = v1 p in - let x2, p = v2 p in - let sz = get_size p x1 in - assert (sz = get_size p x2); - (Avar i), add p i (Ebinop (Nand, x1, x2)) sz + if List.mem_assoc i p.p_eqs then Avar i, p else + let x1, p = v1 p in + let x2, p = v2 p in + let sz = get_size p x1 in + assert (sz = get_size p x2); + (Avar i), add p i (Ebinop (Nand, x1, x2)) sz let not v1 = let i = id "" in fun p -> - let x, p = v1 p in - (Avar i), add p i (Enot (x)) (get_size p x) + if List.mem_assoc i p.p_eqs then Avar i, p else + let x, p = v1 p in + (Avar i), add p i (Enot (x)) (get_size p x) let mux v1 v2 v3 = let i = id "" in fun p -> - let x1, p = v1 p in - let x2, p = v2 p in - let x3, p = v3 p in - let sz = get_size p x2 in - assert (get_size p x3 = sz); - assert (get_size p x1 = 1); - (Avar i), add p i (Emux (x1, x2, x3)) sz + if List.mem_assoc i p.p_eqs then Avar i, p else + let x1, p = v1 p in + let x2, p = v2 p in + let x3, p = v3 p in + let sz = get_size p x2 in + assert (get_size p x3 = sz); + assert (get_size p x1 = 1); + (Avar i), add p i (Emux (x1, x2, x3)) sz let ( ** ) v s = let i = id "" in fun p -> - let x, p = v p in - let sz = get_size p x in - assert (s >= 0 && s < sz); - (Avar i), add p i (Eselect (s, x)) 1 + if List.mem_assoc i p.p_eqs then Avar i, p else + let x, p = v p in + let sz = get_size p x in + assert (s >= 0 && s < sz); + (Avar i), add p i (Eselect (s, x)) 1 let ( % ) v (s1, s2) = let i = id "" in fun p -> - let x, p = v p in - let sz = get_size p x in - assert (s1 >= 0 && s2 >= s1 && sz > s2); - (Avar i), add p i (Eslice (s1, s2, x)) (s2 - s1 + 1) + if List.mem_assoc i p.p_eqs then Avar i, p else + let x, p = v p in + let sz = get_size p x in + assert (s1 >= 0 && s2 >= s1 && sz > s2); + (Avar i), add p i (Eslice (s1, s2, x)) (s2 - s1 + 1) let rom i a_s w_s ra = let i = id i in fun p -> - let ra, p = ra p in - assert ((get_size p ra) = a_s); - (Avar i), add p i (Erom (a_s, w_s, ra)) w_s + if List.mem_assoc i p.p_eqs then Avar i, p else + let ra, p = ra p in + assert ((get_size p ra) = a_s); + (Avar i), add p i (Erom (a_s, w_s, ra)) w_s let ram a_s w_s ra we wa d = let i = id "" in fun p -> - let ra, p = ra p in - let we, p = we p in - let wa, p = wa p in - let d, p = d p in - assert ((get_size p ra) = a_s); - assert ((get_size p wa) = a_s); - assert ((get_size p we) = 1); - assert ((get_size p d) = w_s); - (Avar i), add p i (Eram (a_s, w_s, ra, we, wa, d)) w_s + if List.mem_assoc i p.p_eqs then Avar i, p else + let ra, p = ra p in + let we, p = we p in + let wa, p = wa p in + let d, p = d p in + assert ((get_size p ra) = a_s); + assert ((get_size p wa) = a_s); + assert ((get_size p we) = 1); + assert ((get_size p d) = w_s); + (Avar i), add p i (Eram (a_s, w_s, ra, we, wa, d)) w_s let reg n v = let i = id "" in fun p -> - let v, p = v p in - assert (get_size p v = n); - match v with - | Avar j -> - (Avar i), add p i (Ereg j) n - | Aconst k -> - (Avar i), add p i (Earg v) n + if List.mem_assoc i p.p_eqs then Avar i, p else + let v, p = v p in + assert (get_size p v = n); + match v with + | Avar j -> + (Avar i), add p i (Ereg j) n + | Aconst k -> + (Avar i), add p i (Earg v) n let program entries outputs = @@ -242,7 +258,7 @@ let print oc p = (Printf.fprintf oc ", %s") (List.tl p.p_outputs)); Printf.fprintf oc "\nVAR "; let stts s t = if t = 1 then s else s ^ " : " ^ (string_of_int t) in - ignore (Env.fold (fun s t b -> + Pervasives.ignore (Env.fold (fun s t b -> if b then Printf.fprintf oc "%s" (stts s t) else Printf.fprintf oc ", %s" (stts s t); false) p.p_vars true); diff --git a/cpu/netlist_gen.mli b/cpu/netlist_gen.mli index 3d40477..280ee8c 100644 --- a/cpu/netlist_gen.mli +++ b/cpu/netlist_gen.mli @@ -7,6 +7,9 @@ val id : string -> Netlist_ast.ident val get : Netlist_ast.ident -> t val loop : int -> (t * (t -> t)) +val ignore: t -> t -> t (* ignores first value *) +val ( ^. ) : t -> t -> t (* ignores first value *) + val const : string -> t val ( ++ ) : t -> t -> t (* concat *) @@ -25,8 +28,10 @@ val ( ** ) : t -> int -> t (* select *) val ( % ) : t -> int * int -> t (* slice *) val rom : string -> int -> int -> t -> t + (* addr_size, word_size, read_addr *) val ram : int -> int -> t -> t -> t -> t -> t + (* addr_size, word_size, read_addr, write_enable, write_addr, data *) val reg : int -> t -> t diff --git a/cpu/prog_rom0.rom b/cpu/prog_rom0.rom new file mode 100644 index 0000000..0e93de2 --- /dev/null +++ b/cpu/prog_rom0.rom @@ -0,0 +1,3 @@ +4 8 +/1 10001100 +01111111 11100010 diff --git a/csim/load.c b/csim/load.c index 4e7583a..bb77a0e 100644 --- a/csim/load.c +++ b/csim/load.c @@ -20,13 +20,15 @@ void add_rom(const char *prefix, FILE *file) { rom->prefix = prefix; // Load ROM file - fscanf(file, "%d %d\n", &(rom->addr_size), &(rom->word_size)); - rom->data = malloc(pow2(rom->addr_size) * sizeof(t_value)); + fscanf(file, "%d %d\n", &(rom->words_defined), &(rom->word_size)); + rom->data = malloc(rom->words_defined * sizeof(t_value)); - for (i = 0; i < pow2(rom->addr_size); i++) { + for (i = 0; i < rom->words_defined; i++) { fscanf(file, " "); if (fscanf(file, "/%lu", &(rom->data[i]))) { // ok, value is read + } else if (fscanf(file, "x%x", &(rom->data[i]))) { + // ok, value is read } else { rom->data[i] = read_bool(file, NULL); } @@ -124,7 +126,7 @@ t_program *load_dumb_netlist (FILE *stream) { // find corresponding ROM for (r = roms; r != NULL; r = r->next) { if (is_prefix(r->prefix, p->vars[p->eqs[i].dest_var].name)) { - if (r->addr_size == as && r->word_size == ws) { + if (r->word_size == ws) { p->eqs[i].Rom.rom = r; break; } else { diff --git a/csim/sim.c b/csim/sim.c index e3d61da..04cad15 100644 --- a/csim/sim.c +++ b/csim/sim.c @@ -121,8 +121,8 @@ void machine_step(t_machine *m) { } break; case C_ROM: - if (p->eqs[i].Rom.rom != NULL) { - a = m->var_values[p->eqs[i].Rom.read_addr]; + a = m->var_values[p->eqs[i].Rom.read_addr]; + if (p->eqs[i].Rom.rom != NULL && a < p->eqs[i].Rom.rom->words_defined) { v = p->eqs[i].Rom.rom->data[a]; } else { v = 0; diff --git a/csim/sim.h b/csim/sim.h index c331fa5..0265f53 100644 --- a/csim/sim.h +++ b/csim/sim.h @@ -26,7 +26,7 @@ typedef unsigned long long int t_value; typedef struct _s_rom { - int addr_size, word_size; + int word_size, words_defined; t_value *data; const char *prefix; struct _s_rom *next; diff --git a/plan_micro.pdf b/plan_micro.pdf index 780a408..8b9a899 100644 Binary files a/plan_micro.pdf and b/plan_micro.pdf differ diff --git a/plan_micro.tm b/plan_micro.tm index 8a128be..715b87c 100644 --- a/plan_micro.tm +++ b/plan_micro.tm @@ -45,14 +45,16 @@ La mémoire est adressée sur 16 bits, il y a donc 64ko disponnibles. + Le CPU est little-endian (le mot 0x1234 est codé 34 puis 12) + On définit plusieurs zones de mémoire : - |>||>||>>>>|Memory map> + |>||>||>>>>|Memory map> @@ -61,12 +63,12 @@ On définit plusieurs zones de mémoire : - |>||>||>||>|||>||>||>||>||>>>>|Memory map> Les 0x3000 (12288) octets de mémoire pour le VGA correspondent à un @@ -199,13 +201,15 @@ <\auxiliary> <\collection> <\associate|table> - > + > + + > > + microproceseur|> > + l'assembleur)|> <\associate|toc> |math-font-series||Registres> @@ -216,37 +220,45 @@ |.>>>>|> + |Modèle simple + |.>>>>|> + > + + |Modèle avec affichage bitmapé + |.>>>>|> + > + |math-font-series||Jeu d'instruction> |.>>>>|> - + |Types d'instructions |.>>>>|> - > + > |Format de base |.>>>>|> - > + > |Format |R> |.>>>>|> - > + > |Format |I> |.>>>>|> - > + > |Format K |.>>>>|> - > + > |Format |J> |.>>>>|> - > + > |math-font-series||Tableau d'instructions> |.>>>>|> - + \ No newline at end of file diff --git a/sched/Makefile b/sched/Makefile new file mode 100644 index 0000000..460b639 --- /dev/null +++ b/sched/Makefile @@ -0,0 +1,10 @@ +IN=graph.ml main.ml netlist_ast.ml netlist_dumb.ml netlist_lexer.mll netlist.ml netlist_parser.mly netlist_printer.ml scheduler.ml simplify.ml + +all: main.native + +main.native: $(IN) + ocamlbuild -libs unix main.native + +clean: + rm -rf _build + rm main.native diff --git a/tests/Makefile b/tests/Makefile index 718cd70..7a0792c 100644 --- a/tests/Makefile +++ b/tests/Makefile @@ -1,7 +1,7 @@ .SECONDARY: MINIJAZZ=../minijazz/mjc.byte -SCHED=../sched/main.byte +SCHED=../sched/main.native SIM=../csim/csim %.sim: %.dumb diff --git a/tests/decode7.rom b/tests/decode7.rom index 0eaa3b1..094bae1 100644 --- a/tests/decode7.rom +++ b/tests/decode7.rom @@ -1,4 +1,4 @@ -4 7 +16 7 1110111 0010010 1011101 -- cgit v1.2.3