From cebd07b64f1f537c5ecf00ec21ff4b7c4032f0a3 Mon Sep 17 00:00:00 2001
From: Alex AUVOLAT <alex.auvolat@ens.fr>
Date: Mon, 4 Nov 2013 22:05:57 +0100
Subject: Added stub C simulator (defined dumb-down syntax for netlists).

---
 sched/_tags                  |   3 +
 sched/graph.ml               |  61 +++++++++++++++
 sched/graph_test.byte        |   1 +
 sched/graph_test.ml          |  28 +++++++
 sched/main.byte              |   1 +
 sched/main.ml                |  50 ++++++++++++
 sched/netlist.ml             |  17 ++++
 sched/netlist_ast.ml         |  42 ++++++++++
 sched/netlist_lexer.mll      |  37 +++++++++
 sched/netlist_parser.mly     |  70 +++++++++++++++++
 sched/netlist_printer.ml     | 180 +++++++++++++++++++++++++++++++++++++++++++
 sched/netlist_simulator.byte | Bin 0 -> 190274 bytes
 sched/scheduler.ml           |  52 +++++++++++++
 sched/test/clock_div.dumb    |  11 +++
 sched/test/clock_div.mj      |   4 +
 sched/test/clock_div.net     |   9 +++
 sched/test/clock_div_sch.net |   9 +++
 sched/test/cm2.dumb          |   9 +++
 sched/test/cm2.mj            |   4 +
 sched/test/cm2.net           |   9 +++
 sched/test/cm2_sch.net       |   9 +++
 sched/test/fulladder.dumb    |  20 +++++
 sched/test/fulladder.mj      |   4 +
 sched/test/fulladder.net     |  12 +++
 sched/test/fulladder_sch.net |  12 +++
 sched/test/nadder.dumb       |  27 +++++++
 sched/test/nadder.mj         |  19 +++++
 sched/test/nadder.net        |  17 ++++
 sched/test/nadder_sch.net    |  17 ++++
 sched/test/ram.dumb          |  55 +++++++++++++
 sched/test/ram.mj            |  15 ++++
 sched/test/ram.net           |  32 ++++++++
 sched/test/ram_sch.net       |  32 ++++++++
 33 files changed, 868 insertions(+)
 create mode 100644 sched/_tags
 create mode 100644 sched/graph.ml
 create mode 120000 sched/graph_test.byte
 create mode 100644 sched/graph_test.ml
 create mode 120000 sched/main.byte
 create mode 100644 sched/main.ml
 create mode 100644 sched/netlist.ml
 create mode 100644 sched/netlist_ast.ml
 create mode 100644 sched/netlist_lexer.mll
 create mode 100644 sched/netlist_parser.mly
 create mode 100644 sched/netlist_printer.ml
 create mode 100755 sched/netlist_simulator.byte
 create mode 100644 sched/scheduler.ml
 create mode 100644 sched/test/clock_div.dumb
 create mode 100644 sched/test/clock_div.mj
 create mode 100644 sched/test/clock_div.net
 create mode 100644 sched/test/clock_div_sch.net
 create mode 100644 sched/test/cm2.dumb
 create mode 100644 sched/test/cm2.mj
 create mode 100644 sched/test/cm2.net
 create mode 100644 sched/test/cm2_sch.net
 create mode 100644 sched/test/fulladder.dumb
 create mode 100644 sched/test/fulladder.mj
 create mode 100644 sched/test/fulladder.net
 create mode 100644 sched/test/fulladder_sch.net
 create mode 100644 sched/test/nadder.dumb
 create mode 100644 sched/test/nadder.mj
 create mode 100644 sched/test/nadder.net
 create mode 100644 sched/test/nadder_sch.net
 create mode 100644 sched/test/ram.dumb
 create mode 100644 sched/test/ram.mj
 create mode 100644 sched/test/ram.net
 create mode 100644 sched/test/ram_sch.net

(limited to 'sched')

diff --git a/sched/_tags b/sched/_tags
new file mode 100644
index 0000000..503ce62
--- /dev/null
+++ b/sched/_tags
@@ -0,0 +1,3 @@
+true: use_menhir
+<*.ml>: debug
+<*.byte>: use_unix, debug
\ No newline at end of file
diff --git a/sched/graph.ml b/sched/graph.ml
new file mode 100644
index 0000000..54128ff
--- /dev/null
+++ b/sched/graph.ml
@@ -0,0 +1,61 @@
+exception Cycle
+type mark = NotVisited | InProgress | Visited
+
+type 'a graph =
+    { mutable g_nodes : 'a node list }
+and 'a node = {
+  n_label : 'a;
+  mutable n_mark : mark;
+  mutable n_link_to : 'a node list;
+  mutable n_linked_by : 'a node list;
+}
+
+let mk_graph () = { g_nodes = [] }
+
+let add_node g x =
+  let n = { n_label = x; n_mark = NotVisited; n_link_to = []; n_linked_by = [] } in
+  g.g_nodes <- n::g.g_nodes
+
+let node_for_label g x =
+  List.find (fun n -> n.n_label = x) g.g_nodes
+
+let add_edge g id1 id2 =
+  let n1 = node_for_label g id1 in
+  let n2 = node_for_label g id2 in
+  n1.n_link_to <- n2::n1.n_link_to;
+  n2.n_linked_by <- n1::n2.n_linked_by
+
+let clear_marks g =
+  List.iter (fun n -> n.n_mark <- NotVisited) g.g_nodes
+
+let find_roots g =
+  List.filter (fun n -> n.n_linked_by = []) g.g_nodes
+
+let has_cycle g =
+	clear_marks g;
+	let rec visit n =
+		match n.n_mark with
+		| InProgress -> true
+		| Visited -> false
+		| NotVisited ->
+			n.n_mark <- InProgress;
+			let ret = List.fold_left (fun x n -> x || (visit n)) false n.n_link_to in
+			n.n_mark <- Visited;
+			ret
+	in
+	let ret = List.fold_left (fun x n -> x || (if n.n_mark = Visited then false else visit n)) false g.g_nodes
+	in clear_marks g; ret;;
+
+let topological g =
+	clear_marks g;
+	let rec aux acc n =
+		if n.n_mark = Visited
+			then acc
+			else begin
+				n.n_mark <- Visited;
+				n.n_label :: (List.fold_left (fun x n -> aux x n) acc n.n_linked_by)
+			end
+	in
+	let ret = List.fold_left (fun x n -> aux x n) [] g.g_nodes
+	in clear_marks g; List.rev ret;;
+
diff --git a/sched/graph_test.byte b/sched/graph_test.byte
new file mode 120000
index 0000000..1ec2e64
--- /dev/null
+++ b/sched/graph_test.byte
@@ -0,0 +1 @@
+/home/katchup/Core/ENS/Info/SystDigit-Projet/tp1/_build/graph_test.byte
\ No newline at end of file
diff --git a/sched/graph_test.ml b/sched/graph_test.ml
new file mode 100644
index 0000000..ac31677
--- /dev/null
+++ b/sched/graph_test.ml
@@ -0,0 +1,28 @@
+open Graph
+
+let rec check l = match l with
+  | [] | [_] -> true
+  | s1::s2::l -> (String.length s1 <= String.length s2) && (check (s2::l))
+
+let test_good () =
+  let g = mk_graph () in
+  add_node g "1"; add_node g "21"; add_node g "22"; add_node g "333";
+  add_edge g "1" "21"; add_edge g "1" "22";
+  add_edge g "21" "333"; add_edge g "22" "333";
+  let l = topological g in
+  print_string "Test: Tri topologique --> ";
+  if check l then print_endline "OK" else print_endline "FAIL";
+  List.iter print_endline l;
+  print_newline ()
+
+let test_cycle () =
+  let g = mk_graph () in
+  add_node g "1"; add_node g "2"; add_node g "3";
+  add_edge g "1" "2"; add_edge g "2" "3"; add_edge g "3" "1";
+  print_string "Test: Detection de cycle --> ";
+  if has_cycle g then print_endline "OK" else print_endline "FAIL"
+;;
+
+test_cycle ();;
+test_good ();;
+
diff --git a/sched/main.byte b/sched/main.byte
new file mode 120000
index 0000000..0571503
--- /dev/null
+++ b/sched/main.byte
@@ -0,0 +1 @@
+/home/katchup/Core/ENS/Info/SystDigit-Projet/sched/_build/main.byte
\ No newline at end of file
diff --git a/sched/main.ml b/sched/main.ml
new file mode 100644
index 0000000..988d1ec
--- /dev/null
+++ b/sched/main.ml
@@ -0,0 +1,50 @@
+let simulate = ref false
+let number_steps = ref (-1)
+let sim_path = ref "./netlist_simulator.byte"
+let dumb_down = ref false
+
+let compile filename =
+  try
+    let p = Netlist.read_file filename in
+    let out_name = (Filename.chop_suffix filename ".net") ^ "_sch.net" in
+	let dumb_out_name = (Filename.chop_suffix filename ".net") ^ ".dumb" in
+	let q = ref p in
+
+    begin try
+		q := Scheduler.schedule p
+      with
+        | Scheduler.Combinational_cycle ->
+            Format.eprintf "The netlist has a combinatory cycle.@.";
+            exit 2;
+    end;
+
+    let out = open_out out_name in
+    Netlist_printer.print_program out !q;
+	close_out out;
+	let dumb_out = open_out dumb_out_name in
+	Netlist_printer.print_dumb_program dumb_out !q;
+	close_out dumb_out;
+
+    if !simulate then (
+      let simulator =
+        if !number_steps = -1 then
+			!sim_path
+        else
+			!sim_path ^ " -n " ^ (string_of_int !number_steps)
+      in
+      ignore (Unix.system (simulator^" "^(if !dumb_down then dumb_out_name else out_name)))
+    )
+  with
+    | Netlist.Parse_error s -> Format.eprintf "An error accurred: %s@." s; exit 2
+
+let main () =
+  Arg.parse
+    ["-s", Arg.Set simulate, "Launch the simulator";
+	 "-sim", Arg.Set_string sim_path, "Path to the circuit simulator";
+	 "-d", Arg.Set dumb_down, "Pass the dumbed-down netlist to the simulator (for the C simulator)";
+     "-n", Arg.Set_int number_steps, "Number of steps to simulate"]
+    compile
+    ""
+;;
+
+main ()
diff --git a/sched/netlist.ml b/sched/netlist.ml
new file mode 100644
index 0000000..b1d7932
--- /dev/null
+++ b/sched/netlist.ml
@@ -0,0 +1,17 @@
+exception Parse_error of string
+
+let find_file filename =
+  try
+    open_in filename
+  with
+    | _ -> raise (Parse_error "No such file '%s'")
+
+let read_file filename =
+  let ic = find_file filename in
+  let lexbuf = Lexing.from_channel ic in
+  lexbuf.Lexing.lex_curr_p <- { lexbuf.Lexing.lex_curr_p with Lexing.pos_fname = filename };
+  try
+    Netlist_parser.program Netlist_lexer.token lexbuf
+  with
+    | e -> raise (Parse_error ("Syntax error (exception: "^(Printexc.to_string e)^")"))
+
diff --git a/sched/netlist_ast.ml b/sched/netlist_ast.ml
new file mode 100644
index 0000000..ae16888
--- /dev/null
+++ b/sched/netlist_ast.ml
@@ -0,0 +1,42 @@
+type ident = string
+
+module Env = struct
+  include Map.Make(struct
+    type t = ident
+    let compare = compare
+  end)
+
+  let of_list l =
+    List.fold_left (fun env (x, ty) -> add x ty env) empty l
+end
+
+type ty = TBit | TBitArray of int
+type value = VBit of bool | VBitArray of bool array
+
+type binop = Or | Xor | And | Nand
+
+type arg =
+    | Avar of ident
+    | Aconst of value
+
+type exp =
+    | Earg of arg
+    | Ereg of ident
+    | Enot of arg
+    | Ebinop of binop * arg * arg
+    | Emux of arg * arg * arg
+    | Erom of int (*addr size*) * int (*word size*) * arg (*read_addr*)
+    | Eram of int (*addr size*) * int (*word size*)
+        * arg (*read_addr*) * arg (*write_enable*)
+        * arg (*write_addr*) * arg (*data*)
+    | Econcat of arg * arg
+    | Eslice of int * int * arg
+    | Eselect of int * arg
+
+type equation = ident * exp
+
+type program =
+    { p_eqs : equation list;
+      p_inputs : ident list;
+      p_outputs : ident list;
+      p_vars : ty Env.t; }
diff --git a/sched/netlist_lexer.mll b/sched/netlist_lexer.mll
new file mode 100644
index 0000000..78b0410
--- /dev/null
+++ b/sched/netlist_lexer.mll
@@ -0,0 +1,37 @@
+{
+open Netlist_parser
+exception Eof
+
+let keyword_list =
+[
+  "AND", AND;
+  "CONCAT", CONCAT;
+  "IN", IN;
+  "INPUT", INPUT;
+  "MUX", MUX;
+  "NAND", NAND;
+  "NOT", NOT;
+  "OR", OR;
+  "OUTPUT", OUTPUT;
+  "RAM", RAM;
+  "REG", REG;
+  "ROM", ROM;
+  "SELECT", SELECT;
+  "SLICE", SLICE;
+  "VAR", VAR;
+  "XOR", XOR;
+]
+
+}
+
+rule token = parse
+    [' ' '\t' '\n']     { token lexbuf }     (* skip blanks *)
+  | "="            { EQUAL }
+  | ":"            { COLON }
+  | ","            { COMMA }
+  | ['0'-'9']+ as lxm { INT(int_of_string lxm) }
+  | ('_' ? ['A'-'Z' 'a'-'z']('_' ? ['A'-'Z' 'a'-'z' ''' '0'-'9']) * as id)
+      { let s = Lexing.lexeme lexbuf in
+        try List.assoc s keyword_list
+        with Not_found -> NAME id }
+  | eof            { EOF }
diff --git a/sched/netlist_parser.mly b/sched/netlist_parser.mly
new file mode 100644
index 0000000..0908703
--- /dev/null
+++ b/sched/netlist_parser.mly
@@ -0,0 +1,70 @@
+%{
+ open Netlist_ast
+
+ let value_of_int n =
+   let rec aux n =
+     let b =
+       match n mod 10 with
+         | 0 -> false
+         | 1 -> true
+         | i -> Format.eprintf "Unexpected: %d@." i; raise Parsing.Parse_error
+     in
+     if n < 10 then
+       [b]
+     else
+       b::(aux (n / 10))
+   in
+   match aux n with
+     | [] -> Format.eprintf "Empty list@."; raise Parsing.Parse_error
+     | [b] -> VBit b
+     | bl -> VBitArray (Array.of_list (List.rev bl))
+%}
+
+%token <int> INT
+%token <string> NAME
+%token AND MUX NAND OR RAM ROM XOR REG NOT
+%token CONCAT SELECT SLICE
+%token COLON EQUAL COMMA VAR IN INPUT OUTPUT
+%token EOF
+
+%start program             /* the entry point */
+%type <Netlist_ast.program> program
+
+%%
+program:
+  INPUT inp=separated_list(COMMA, NAME)
+    OUTPUT out=separated_list(COMMA, NAME)
+    VAR vars=separated_list(COMMA, var) IN eqs=list(equ) EOF
+    { { p_eqs = eqs; p_vars = Env.of_list vars; p_inputs = inp; p_outputs = out; } }
+
+equ:
+  x=NAME EQUAL e=exp { (x, e) }
+
+exp:
+  | a=arg { Earg a }
+  | NOT x=arg { Enot x }
+  | REG x=NAME { Ereg x }
+  | AND x=arg y=arg { Ebinop(And, x, y) }
+  | OR x=arg y=arg { Ebinop(Or, x, y) }
+  | NAND x=arg y=arg { Ebinop(Nand, x, y) }
+  | XOR x=arg y=arg { Ebinop(Xor, x, y) }
+  | MUX x=arg y=arg z=arg { Emux(x, y, z) }
+  | ROM addr=INT word=INT ra=arg
+    { Erom(addr, word, ra) }
+  | RAM addr=INT word=INT ra=arg we=arg wa=arg data=arg
+    { Eram(addr, word, ra, we, wa, data) }
+  | CONCAT x=arg y=arg
+     { Econcat(x, y) }
+  | SELECT idx=INT x=arg
+     { Eselect (idx, x) }
+  | SLICE min=INT max=INT x=arg
+     { Eslice (min, max, x) }
+
+arg:
+  | n=INT { Aconst (value_of_int n) }
+  | id=NAME { Avar id }
+
+var: x=NAME ty=ty_exp { (x, ty) }
+ty_exp:
+  | /*empty*/ { TBit }
+  | COLON n=INT { TBitArray n }
diff --git a/sched/netlist_printer.ml b/sched/netlist_printer.ml
new file mode 100644
index 0000000..fbd432a
--- /dev/null
+++ b/sched/netlist_printer.ml
@@ -0,0 +1,180 @@
+open Netlist_ast
+open Format
+
+(* GENERAL PRINTER *)
+
+let rec print_env print lp sep rp ff env =
+  let first = ref true in
+  fprintf ff "%s" lp;
+  Env.iter
+    (fun x ty ->
+      if !first then
+        (first := false; fprintf ff "%a" print (x, ty))
+      else
+        fprintf ff "%s%a" sep print (x, ty)) env;
+  fprintf ff "%s" rp
+
+let rec print_list print lp sep rp ff = function
+  | [] -> ()
+  | x :: l ->
+      fprintf ff "%s%a" lp print x;
+      List.iter (fprintf ff "%s %a" sep print) l;
+      fprintf ff "%s" rp
+
+let print_ty ff ty = match ty with
+  | TBit -> ()
+  | TBitArray n -> fprintf ff " : %d" n
+
+let print_bool ff b =
+  if b then
+    fprintf ff "1"
+  else
+    fprintf ff "0"
+
+let print_value ff v = match v with
+  | VBit b -> print_bool ff b
+  | VBitArray a -> Array.iter (print_bool ff) a
+
+let print_arg ff arg = match arg with
+  | Aconst v -> print_value ff v
+  | Avar id -> fprintf ff "%s" id
+
+let print_op ff op = match op with
+  | And -> fprintf ff "AND"
+  | Nand -> fprintf ff "NAND"
+  | Or -> fprintf ff "OR"
+  | Xor -> fprintf ff "XOR"
+
+let print_exp ff e = match e with
+  | Earg a -> print_arg ff a
+  | Ereg x -> fprintf ff "REG %s" x
+  | Enot x -> fprintf ff "NOT %a" print_arg x
+  | Ebinop(op, x, y) -> fprintf ff  "%a %a %a" print_op op  print_arg x  print_arg y
+  | Emux (c, x, y) -> fprintf ff "MUX %a %a %a " print_arg c  print_arg x  print_arg y
+  | Erom (addr, word, ra) -> fprintf ff "ROM %d %d %a" addr word  print_arg ra
+  | Eram (addr, word, ra, we, wa, data) ->
+      fprintf ff "RAM %d %d %a %a %a %a" addr word
+        print_arg ra  print_arg we
+        print_arg wa  print_arg data
+  | Eselect (idx, x) -> fprintf ff "SELECT %d %a" idx print_arg x
+  | Econcat (x, y) ->  fprintf ff  "CONCAT %a %a" print_arg x  print_arg y
+  | Eslice (min, max, x) -> fprintf ff "SLICE %d %d %a" min max print_arg x
+
+let print_eq ff (x, e) =
+  fprintf ff "%s = %a@." x print_exp e
+
+let print_var ff (x, ty) =
+  fprintf ff "@[%s%a@]" x print_ty ty
+
+let print_vars ff env =
+  fprintf ff "@[<v 2>VAR@,%a@]@.IN@,"
+    (print_env print_var "" ", " "") env
+
+let print_idents ff ids =
+  let print_ident ff s = fprintf ff "%s" s in
+  print_list print_ident """,""" ff ids
+
+let print_program oc p =
+  let ff = formatter_of_out_channel oc in
+  fprintf ff "INPUT %a@." print_idents p.p_inputs;
+  fprintf ff "OUTPUT %a@." print_idents p.p_outputs;
+  print_vars ff p.p_vars;
+  List.iter (print_eq ff) p.p_eqs;
+  (* flush *)
+  fprintf ff "@."
+
+
+(* PRINTER FOR DUMBED-DOWN NETLIST (variables are identified by numbers) *)
+
+(* constants *)
+let c_arg = 0
+let c_reg = 1
+let c_not = 2
+let c_binop = 3
+let c_mux = 4
+let c_rom = 5
+let c_ram = 6
+let c_concat = 7
+let c_slice = 8
+let c_select = 9
+
+let binop_i = function
+	| Or -> 0
+	| Xor -> 1
+	| And -> 2
+	| Nand -> 3
+
+let print_dumb_program oc p =
+	let ff = formatter_of_out_channel oc in
+	(* associate numbers to variables *)
+	let n_vars = Env.fold (fun _ _ n -> n+1) p.p_vars 0 in
+	let n = ref 0 in
+	let var_id = Hashtbl.create n_vars in
+	fprintf ff "%d\n" n_vars;
+	Env.iter
+		(fun  k v ->
+			Hashtbl.add var_id k !n;
+			fprintf ff "%d %s\n"
+				(match v with
+					| TBit -> 1
+					| TBitArray(n) -> n)
+				k;
+			n := !n + 1)
+		p.p_vars;
+	(* write input vars *)
+	fprintf ff "%d" (List.length p.p_inputs);
+	List.iter (fun k -> fprintf ff " %d" (Hashtbl.find var_id k)) p.p_inputs;
+	fprintf ff "\n";
+	(* write output vars *)
+	fprintf ff "%d" (List.length p.p_outputs);
+	List.iter (fun k -> fprintf ff " %d" (Hashtbl.find var_id k)) p.p_outputs;
+	fprintf ff "\n";
+	(* write equations *)
+	fprintf ff "%d\n" (List.length p.p_eqs);
+	(* write equations *)
+	let print_arg = function
+	| Avar(k) -> fprintf ff " %d" (Hashtbl.find var_id k)
+	| Aconst(n) -> fprintf ff " $";
+		begin match n with
+		| VBit(x) -> fprintf ff "%d" (if x then 1 else 0)
+		| VBitArray(a) ->
+			let k = ref 0 in
+			for i = 0 to Array.length a - 1 do
+				k := 2 * !k + (if a.(i) then 1 else 0)
+			done;
+			fprintf ff "%d" !k
+		end
+	in
+	List.iter
+		(fun (k, eqn) ->
+			fprintf ff "%d " (Hashtbl.find var_id k);
+			begin match eqn with
+			| Earg(a) -> fprintf ff "%d" c_arg;
+				print_arg a
+			| Ereg(i) -> fprintf ff "%d %d" c_reg (Hashtbl.find var_id i)
+			| Enot(a) -> fprintf ff "%d" c_not;
+				print_arg a
+			| Ebinop(o, a, b) -> fprintf ff "%d %d" c_binop (binop_i o);
+				print_arg a;
+				print_arg b
+			| Emux(a, b, c) -> fprintf ff "%d" c_mux;
+				print_arg a; print_arg b; print_arg c
+			| Erom(u, v, a) -> fprintf ff "%d %d %d" c_rom u v;
+				print_arg a
+			| Eram (u, v, a, b, c, d) -> fprintf ff "%d %d %d" c_ram u v;
+				print_arg a; print_arg b; print_arg c; print_arg d
+			| Econcat(a, b) -> fprintf ff "%d" c_concat;
+				print_arg a; print_arg b
+			| Eslice(u, v, a) -> fprintf ff "%d %d %d" c_slice u v;
+				print_arg a
+			| Eselect(i, a) -> fprintf ff "%d %d" c_select i;
+				print_arg a
+			end;
+			fprintf ff "\n")
+		p.p_eqs;
+	(* flush *)
+	fprintf ff "@."
+
+
+
+
diff --git a/sched/netlist_simulator.byte b/sched/netlist_simulator.byte
new file mode 100755
index 0000000..155d39a
Binary files /dev/null and b/sched/netlist_simulator.byte differ
diff --git a/sched/scheduler.ml b/sched/scheduler.ml
new file mode 100644
index 0000000..130164b
--- /dev/null
+++ b/sched/scheduler.ml
@@ -0,0 +1,52 @@
+open Netlist_ast
+
+module Smap = Map.Make(String)
+
+exception Combinational_cycle
+
+let read_exp eq =
+	let add_arg x l = match x with
+		| Avar(f) -> f::l
+		| Aconst(_) -> l
+	in
+	let aux = function
+	| Earg(x) -> add_arg x []
+	| Ereg(i) -> []
+	| Enot(x) -> add_arg x []
+	| Ebinop(_, x, y) -> add_arg x (add_arg y [])
+	| Emux(a, b, c) -> add_arg a (add_arg b (add_arg c []))
+	| Erom(_, _, a) -> add_arg a []
+	| Eram(_, _, a, b, c, d) -> []
+	| Econcat(u, v) -> add_arg u (add_arg v [])
+	| Eslice(_, _, a) -> add_arg a []
+	| Eselect(_, a) -> add_arg a []
+	in
+		aux eq;;
+
+let schedule p =
+	let graph = Graph.mk_graph() in
+	let eq_map = List.fold_left (fun x (vn, eqn) -> Smap.add vn eqn x) Smap.empty p.p_eqs in
+	(* Add variables as graph nodes *)
+	List.iter (fun (k, _) -> Graph.add_node graph k) p.p_eqs;
+	(* Add dependencies as graph edges *)
+	List.iter 
+		(fun (n, e) -> List.iter
+			(fun m -> if Smap.mem m eq_map then Graph.add_edge graph m n else ())
+			(read_exp e))
+		p.p_eqs;
+	(* Verify there are no cycles *)
+	if Graph.has_cycle graph then raise Combinational_cycle;
+	(* Topological sort of graph nodes *)
+	let topo_vars = Graph.topological graph in
+	(* Construct new program with sorted expression list *)
+	{
+		p_eqs = List.fold_right
+			(fun n x -> if Smap.mem n eq_map then (n, Smap.find n eq_map)::x else x) topo_vars [];
+		p_inputs = p.p_inputs;
+		p_outputs = p.p_outputs;
+		p_vars = p.p_vars;
+	}
+	;;
+
+
+
diff --git a/sched/test/clock_div.dumb b/sched/test/clock_div.dumb
new file mode 100644
index 0000000..bcb07d0
--- /dev/null
+++ b/sched/test/clock_div.dumb
@@ -0,0 +1,11 @@
+3
+1 _l_2
+1 c
+1 o
+0
+1 2
+3
+0 1 2
+2 1 1
+1 2 0
+
diff --git a/sched/test/clock_div.mj b/sched/test/clock_div.mj
new file mode 100644
index 0000000..ad1e919
--- /dev/null
+++ b/sched/test/clock_div.mj
@@ -0,0 +1,4 @@
+main() = (o) where
+  o = reg(c);
+  c = not (reg (o))
+end where
\ No newline at end of file
diff --git a/sched/test/clock_div.net b/sched/test/clock_div.net
new file mode 100644
index 0000000..9a17fc7
--- /dev/null
+++ b/sched/test/clock_div.net
@@ -0,0 +1,9 @@
+INPUT 
+OUTPUT o
+VAR
+  _l_2, c, o
+IN
+c = NOT _l_2
+o = REG c
+_l_2 = REG o
+
diff --git a/sched/test/clock_div_sch.net b/sched/test/clock_div_sch.net
new file mode 100644
index 0000000..0ae5cd9
--- /dev/null
+++ b/sched/test/clock_div_sch.net
@@ -0,0 +1,9 @@
+INPUT 
+OUTPUT o
+VAR
+  _l_2, c, o
+IN
+_l_2 = REG o
+o = REG c
+c = NOT _l_2
+
diff --git a/sched/test/cm2.dumb b/sched/test/cm2.dumb
new file mode 100644
index 0000000..632c6ea
--- /dev/null
+++ b/sched/test/cm2.dumb
@@ -0,0 +1,9 @@
+4
+1	_l_1
+1	r
+1	s
+1	x
+1 3
+2 2 1
+3
+
diff --git a/sched/test/cm2.mj b/sched/test/cm2.mj
new file mode 100644
index 0000000..8863bf1
--- /dev/null
+++ b/sched/test/cm2.mj
@@ -0,0 +1,4 @@
+main(x) = (s, r) where
+  s = reg (x xor s);
+  r = x and s
+end where
\ No newline at end of file
diff --git a/sched/test/cm2.net b/sched/test/cm2.net
new file mode 100644
index 0000000..e296b96
--- /dev/null
+++ b/sched/test/cm2.net
@@ -0,0 +1,9 @@
+INPUT x
+OUTPUT s, r
+VAR
+  _l_1, r, s, x
+IN
+r = AND x s
+s = REG _l_1
+_l_1 = XOR x s
+
diff --git a/sched/test/cm2_sch.net b/sched/test/cm2_sch.net
new file mode 100644
index 0000000..e9900d5
--- /dev/null
+++ b/sched/test/cm2_sch.net
@@ -0,0 +1,9 @@
+INPUT x
+OUTPUT s, r
+VAR
+  _l_1, r, s, x
+IN
+s = REG _l_1
+_l_1 = XOR x s
+r = AND x s
+
diff --git a/sched/test/fulladder.dumb b/sched/test/fulladder.dumb
new file mode 100644
index 0000000..480d04d
--- /dev/null
+++ b/sched/test/fulladder.dumb
@@ -0,0 +1,20 @@
+9
+1 _l_1
+1 _l_3
+1 _l_4
+1 _l_5
+1 a
+1 b
+1 c
+1 r
+1 s
+3 4 5 6
+2 8 7
+6
+2 3 1 4 5
+3 3 2 2 6
+1 3 2 4 5
+0 3 1 4 5
+8 3 1 0 6
+7 3 0 1 3
+
diff --git a/sched/test/fulladder.mj b/sched/test/fulladder.mj
new file mode 100644
index 0000000..c4b6b0e
--- /dev/null
+++ b/sched/test/fulladder.mj
@@ -0,0 +1,4 @@
+main(a,b,c) = (s, r) where
+  s = (a xor b) xor c;
+  r = (a and b) or ((a xor b) and c);
+end where
\ No newline at end of file
diff --git a/sched/test/fulladder.net b/sched/test/fulladder.net
new file mode 100644
index 0000000..b2271c2
--- /dev/null
+++ b/sched/test/fulladder.net
@@ -0,0 +1,12 @@
+INPUT a, b, c
+OUTPUT s, r
+VAR
+  _l_1, _l_3, _l_4, _l_5, a, b, c, r, s
+IN
+r = OR _l_3 _l_5
+s = XOR _l_1 c
+_l_1 = XOR a b
+_l_3 = AND a b
+_l_4 = XOR a b
+_l_5 = AND _l_4 c
+
diff --git a/sched/test/fulladder_sch.net b/sched/test/fulladder_sch.net
new file mode 100644
index 0000000..96fc154
--- /dev/null
+++ b/sched/test/fulladder_sch.net
@@ -0,0 +1,12 @@
+INPUT a, b, c
+OUTPUT s, r
+VAR
+  _l_1, _l_3, _l_4, _l_5, a, b, c, r, s
+IN
+_l_4 = XOR a b
+_l_5 = AND _l_4 c
+_l_3 = AND a b
+_l_1 = XOR a b
+s = XOR _l_1 c
+r = OR _l_3 _l_5
+
diff --git a/sched/test/nadder.dumb b/sched/test/nadder.dumb
new file mode 100644
index 0000000..469984d
--- /dev/null
+++ b/sched/test/nadder.dumb
@@ -0,0 +1,27 @@
+12
+1 _l_10_50
+1 _l_11_49
+1 _l_16_22
+1 _l_17_21
+1 _l_7_52
+1 _l_9_51
+1 a
+1 b
+1 c
+1 c_n1_27
+1 o
+1 s_n_26
+2 6 7
+2 10 8
+10
+3 9 0 7
+2 9 0 6
+9 0 $0
+0 3 1 2 3
+1 3 2 0 9
+5 3 2 2 3
+4 3 1 2 3
+11 3 1 4 9
+8 3 0 5 1
+10 0 11
+
diff --git a/sched/test/nadder.mj b/sched/test/nadder.mj
new file mode 100644
index 0000000..0c95386
--- /dev/null
+++ b/sched/test/nadder.mj
@@ -0,0 +1,19 @@
+fulladder(a,b,c) = (s, r) where
+  s = (a ^ b) ^ c;
+  r = (a & b) + ((a ^ b) & c);
+end where
+
+adder<n>(a:[n], b:[n], c_in) = (o:[n], c_out) where
+  if n = 0 then
+    o = [];
+    c_out = 0
+  else
+    (s_n1, c_n1) = adder<n-1>(a[1..], b[1..], c_in);
+    (s_n, c_out) = fulladder(a[0], b[0], c_n1);
+    o = s_n . s_n1
+  end if
+end where
+
+main(a, b) = (o, c) where
+  (o, c) = adder<1>(a,b,0)
+end where
\ No newline at end of file
diff --git a/sched/test/nadder.net b/sched/test/nadder.net
new file mode 100644
index 0000000..bf87051
--- /dev/null
+++ b/sched/test/nadder.net
@@ -0,0 +1,17 @@
+INPUT a, b
+OUTPUT o, c
+VAR
+  _l_10_50, _l_11_49, _l_16_22, _l_17_21, _l_7_52, _l_9_51, a, b, c, 
+  c_n1_27, o, s_n_26
+IN
+o = s_n_26
+c = OR _l_9_51 _l_11_49
+s_n_26 = XOR _l_7_52 c_n1_27
+_l_7_52 = XOR _l_16_22 _l_17_21
+_l_9_51 = AND _l_16_22 _l_17_21
+_l_10_50 = XOR _l_16_22 _l_17_21
+_l_11_49 = AND _l_10_50 c_n1_27
+c_n1_27 = 0
+_l_16_22 = SELECT 0 a
+_l_17_21 = SELECT 0 b
+
diff --git a/sched/test/nadder_sch.net b/sched/test/nadder_sch.net
new file mode 100644
index 0000000..5602eb4
--- /dev/null
+++ b/sched/test/nadder_sch.net
@@ -0,0 +1,17 @@
+INPUT a, b
+OUTPUT o, c
+VAR
+  _l_10_50, _l_11_49, _l_16_22, _l_17_21, _l_7_52, _l_9_51, a, b, c, 
+  c_n1_27, o, s_n_26
+IN
+_l_17_21 = SELECT 0 b
+_l_16_22 = SELECT 0 a
+c_n1_27 = 0
+_l_10_50 = XOR _l_16_22 _l_17_21
+_l_11_49 = AND _l_10_50 c_n1_27
+_l_9_51 = AND _l_16_22 _l_17_21
+_l_7_52 = XOR _l_16_22 _l_17_21
+s_n_26 = XOR _l_7_52 c_n1_27
+c = OR _l_9_51 _l_11_49
+o = s_n_26
+
diff --git a/sched/test/ram.dumb b/sched/test/ram.dumb
new file mode 100644
index 0000000..74cf168
--- /dev/null
+++ b/sched/test/ram.dumb
@@ -0,0 +1,55 @@
+27
+1 _l_10_22
+1 _l_10_35
+1 _l_10_48
+1 _l_10_61
+1 _l_11_21
+1 _l_11_34
+1 _l_11_47
+1 _l_11_60
+3 _l_12_20
+2 _l_12_33
+1 _l_12_46
+3 _l_13_19
+2 _l_13_32
+1 _l_13_45
+3 _l_14_18
+2 _l_14_31
+1 _l_14_44
+4 _l_16
+1 _l_9_23
+1 _l_9_36
+1 _l_9_49
+1 _l_9_62
+4 c
+4 o
+2 ra
+2 wa
+1 we
+4 24 26 25 22
+1 23
+23
+11 8 1 3 22
+12 8 1 2 11
+13 8 1 1 12
+3 9 0 13
+23 6 2 4 24 26 25 17
+8 8 1 3 23
+9 8 1 2 8
+10 8 1 1 9
+21 9 0 10
+7 3 2 21 3
+16 0 7
+2 9 0 12
+20 9 0 9
+6 3 2 20 2
+15 7 6 16
+1 9 0 11
+19 9 0 8
+5 3 2 19 1
+14 7 5 15
+0 9 0 22
+18 9 0 23
+4 3 2 18 0
+17 7 4 14
+
diff --git a/sched/test/ram.mj b/sched/test/ram.mj
new file mode 100644
index 0000000..7c4d1ed
--- /dev/null
+++ b/sched/test/ram.mj
@@ -0,0 +1,15 @@
+const addr = 2
+const word = 4
+
+or_n<n>(a:[n],b:[n]) = (o:[n]) where
+  if n = 0 then
+    o = []
+  else
+    o = (a[0] and b[0]).(or_n<n-1>(a[1..], b[1..]))
+  end if
+end where
+
+main(ra:[addr], we, wa:[addr], c:[word]) = (o:[word]) where
+  o = ram<addr, word>(ra, we, wa, or_n<word>(o, c))
+end where
+
diff --git a/sched/test/ram.net b/sched/test/ram.net
new file mode 100644
index 0000000..ee4570a
--- /dev/null
+++ b/sched/test/ram.net
@@ -0,0 +1,32 @@
+INPUT ra, we, wa, c
+OUTPUT o
+VAR
+  _l_10_22, _l_10_35, _l_10_48, _l_10_61, _l_11_21, _l_11_34, _l_11_47, 
+  _l_11_60, _l_12_20 : 3, _l_12_33 : 2, _l_12_46 : 1, _l_13_19 : 3, _l_13_32 : 2, 
+  _l_13_45 : 1, _l_14_18 : 3, _l_14_31 : 2, _l_14_44 : 1, _l_16 : 4, 
+  _l_9_23, _l_9_36, _l_9_49, _l_9_62, c : 4, o : 4, ra : 2, wa : 2, we
+IN
+o = RAM 2 4 ra we wa _l_16
+_l_16 = CONCAT _l_11_21 _l_14_18
+_l_9_23 = SELECT 0 o
+_l_10_22 = SELECT 0 c
+_l_11_21 = AND _l_9_23 _l_10_22
+_l_12_20 = SLICE 1 3 o
+_l_13_19 = SLICE 1 3 c
+_l_14_18 = CONCAT _l_11_34 _l_14_31
+_l_9_36 = SELECT 0 _l_12_20
+_l_10_35 = SELECT 0 _l_13_19
+_l_11_34 = AND _l_9_36 _l_10_35
+_l_12_33 = SLICE 1 2 _l_12_20
+_l_13_32 = SLICE 1 2 _l_13_19
+_l_14_31 = CONCAT _l_11_47 _l_14_44
+_l_9_49 = SELECT 0 _l_12_33
+_l_10_48 = SELECT 0 _l_13_32
+_l_11_47 = AND _l_9_49 _l_10_48
+_l_12_46 = SLICE 1 1 _l_12_33
+_l_13_45 = SLICE 1 1 _l_13_32
+_l_14_44 = _l_11_60
+_l_9_62 = SELECT 0 _l_12_46
+_l_10_61 = SELECT 0 _l_13_45
+_l_11_60 = AND _l_9_62 _l_10_61
+
diff --git a/sched/test/ram_sch.net b/sched/test/ram_sch.net
new file mode 100644
index 0000000..56dda0e
--- /dev/null
+++ b/sched/test/ram_sch.net
@@ -0,0 +1,32 @@
+INPUT ra, we, wa, c
+OUTPUT o
+VAR
+  _l_10_22, _l_10_35, _l_10_48, _l_10_61, _l_11_21, _l_11_34, _l_11_47, 
+  _l_11_60, _l_12_20 : 3, _l_12_33 : 2, _l_12_46 : 1, _l_13_19 : 3, _l_13_32 : 2, 
+  _l_13_45 : 1, _l_14_18 : 3, _l_14_31 : 2, _l_14_44 : 1, _l_16 : 4, 
+  _l_9_23, _l_9_36, _l_9_49, _l_9_62, c : 4, o : 4, ra : 2, wa : 2, we
+IN
+_l_13_19 = SLICE 1 3 c
+_l_13_32 = SLICE 1 2 _l_13_19
+_l_13_45 = SLICE 1 1 _l_13_32
+_l_10_61 = SELECT 0 _l_13_45
+o = RAM 2 4 ra we wa _l_16
+_l_12_20 = SLICE 1 3 o
+_l_12_33 = SLICE 1 2 _l_12_20
+_l_12_46 = SLICE 1 1 _l_12_33
+_l_9_62 = SELECT 0 _l_12_46
+_l_11_60 = AND _l_9_62 _l_10_61
+_l_14_44 = _l_11_60
+_l_10_48 = SELECT 0 _l_13_32
+_l_9_49 = SELECT 0 _l_12_33
+_l_11_47 = AND _l_9_49 _l_10_48
+_l_14_31 = CONCAT _l_11_47 _l_14_44
+_l_10_35 = SELECT 0 _l_13_19
+_l_9_36 = SELECT 0 _l_12_20
+_l_11_34 = AND _l_9_36 _l_10_35
+_l_14_18 = CONCAT _l_11_34 _l_14_31
+_l_10_22 = SELECT 0 c
+_l_9_23 = SELECT 0 o
+_l_11_21 = AND _l_9_23 _l_10_22
+_l_16 = CONCAT _l_11_21 _l_14_18
+
-- 
cgit v1.2.3