Started CPU implementation.

6 files changed, 270 insertions, 71 deletions

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