From cebd07b64f1f537c5ecf00ec21ff4b7c4032f0a3 Mon Sep 17 00:00:00 2001 From: Alex AUVOLAT Date: Mon, 4 Nov 2013 22:05:57 +0100 Subject: Added stub C simulator (defined dumb-down syntax for netlists). --- .gitignore | 2 + csim/Makefile | 5 ++ csim/load.c | 104 +++++++++++++++++++++++++ csim/main.c | 97 +++++++++++++++++++++++ csim/sim.c | 23 ++++++ csim/sim.h | 116 ++++++++++++++++++++++++++++ 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 ++++++++ tp1/_tags | 3 - tp1/graph.ml | 61 --------------- tp1/graph_test.ml | 28 ------- tp1/netlist.ml | 17 ---- tp1/netlist_ast.ml | 42 ---------- tp1/netlist_lexer.mll | 37 --------- tp1/netlist_parser.mly | 70 ----------------- tp1/netlist_printer.ml | 82 -------------------- tp1/netlist_simulator.byte | Bin 190274 -> 0 bytes tp1/scheduler.ml | 52 ------------- tp1/scheduler_test.ml | 41 ---------- tp1/test/clock_div.mj | 4 - tp1/test/clock_div.net | 9 --- tp1/test/cm2.mj | 4 - tp1/test/cm2.net | 9 --- tp1/test/fulladder.mj | 4 - tp1/test/fulladder.net | 12 --- tp1/test/nadder.mj | 19 ----- tp1/test/nadder.net | 17 ---- tp1/test/ram.mj | 15 ---- tp1/test/ram.net | 32 -------- 60 files changed, 1215 insertions(+), 558 deletions(-) create mode 100644 csim/Makefile create mode 100644 csim/load.c create mode 100644 csim/main.c create mode 100644 csim/sim.c create mode 100644 csim/sim.h 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 delete mode 100644 tp1/_tags delete mode 100644 tp1/graph.ml delete mode 100644 tp1/graph_test.ml delete mode 100644 tp1/netlist.ml delete mode 100644 tp1/netlist_ast.ml delete mode 100644 tp1/netlist_lexer.mll delete mode 100644 tp1/netlist_parser.mly delete mode 100644 tp1/netlist_printer.ml delete mode 100755 tp1/netlist_simulator.byte delete mode 100644 tp1/scheduler.ml delete mode 100644 tp1/scheduler_test.ml delete mode 100644 tp1/test/clock_div.mj delete mode 100644 tp1/test/clock_div.net delete mode 100644 tp1/test/cm2.mj delete mode 100644 tp1/test/cm2.net delete mode 100644 tp1/test/fulladder.mj delete mode 100644 tp1/test/fulladder.net delete mode 100644 tp1/test/nadder.mj delete mode 100644 tp1/test/nadder.net delete mode 100644 tp1/test/ram.mj delete mode 100644 tp1/test/ram.net diff --git a/.gitignore b/.gitignore index a9d6766..c90ad14 100644 --- a/.gitignore +++ b/.gitignore @@ -3,3 +3,5 @@ tp1/*test.byte tp1/test/*_sch.net camlsim/*.byte *.swp +csim/csim +*.o diff --git a/csim/Makefile b/csim/Makefile new file mode 100644 index 0000000..32d100d --- /dev/null +++ b/csim/Makefile @@ -0,0 +1,5 @@ +main: main.o load.o sim.o + gcc -o csim $^ + +%.o: %.c + gcc -c $< -o $@ -g diff --git a/csim/load.c b/csim/load.c new file mode 100644 index 0000000..397af5a --- /dev/null +++ b/csim/load.c @@ -0,0 +1,104 @@ +/* + Système Digital + 2013-2014 + Alex AUVOLAT + + load.c Code for loading dumbed-down netlist files + (no parsing of .net files !!) +*/ + +#include + +#include "sim.h" + +void read_arg(FILE *stream, t_arg *dest) { + if (fscanf(stream, "$%Ld ", &(dest->val)) > 0) { + dest->source_var = -1; + } else { + fscanf(stream, "%d ", &(dest->source_var)); + } +} + +t_program *load_dumb_netlist (FILE *stream) { + int i; + + // let us suppose that the input to be read is well-formed. + t_program *p = malloc(sizeof(t_program)); + + // Read variable list, with sizes and identifiers + fscanf(stream, "%d ", &(p->n_vars)); + p->vars = malloc(p->n_vars * sizeof(t_variable)); + + for (i = 0; i < p->n_vars; i++) { + fscanf(stream, "%d ", &(p->vars[i].size)); + p->vars[i].mask = (0xFFFFFFFFFFFFFFFF >> (64 - p->vars[i].size)); + + p->vars[i].name = malloc(42); // let's bet that the name of a variable will never be longer than 42 chars + fscanf(stream, "%s\n", p->vars[i].name); + } + + // read input list + fscanf(stream, "%d ", &(p->n_inputs)); + p->inputs = malloc(p->n_inputs * sizeof(t_id)); + for (i = 0; i < p->n_inputs; i++) { + fscanf(stream, "%d ", &(p->inputs[i])); + } + // read output list + fscanf(stream, "%d ", &(p->n_outputs)); + p->outputs = malloc(p->n_outputs * sizeof(t_id)); + for (i = 0; i < p->n_outputs; i++) { + fscanf(stream, "%d ", &(p->outputs[i])); + } + + // read equation list + fscanf(stream, "%d ", &(p->n_eqs)); + p->eqs = malloc(p->n_eqs * sizeof(t_equation)); + for (i = 0; i < p->n_eqs; i++) { + fscanf(stream, "%d ", &(p->eqs[i].dest_var)); + fscanf(stream, "%d ", &(p->eqs[i].type)); + switch (p->eqs[i].type) { + case C_ARG: + read_arg(stream, &(p->eqs[i].Arg.a)); + break; + case C_REG: + fscanf(stream, "%d ", &(p->eqs[i].Reg.var)); + break; + case C_NOT: + read_arg(stream, &(p->eqs[i].Not.a)); + break; + case C_BINOP: + fscanf(stream, "%d ", &(p->eqs[i].Binop.op)); + read_arg(stream, &(p->eqs[i].Binop.a)); + read_arg(stream, &(p->eqs[i].Binop.b)); + break; + case C_MUX: + read_arg(stream, &(p->eqs[i].Mux.a)); + read_arg(stream, &(p->eqs[i].Mux.b)); + read_arg(stream, &(p->eqs[i].Mux.c)); + break; + case C_ROM: + fscanf(stream, "%d %d ", &(p->eqs[i].Rom.addr_size), &(p->eqs[i].Rom.word_size)); + read_arg(stream, &(p->eqs[i].Rom.read_addr)); + break; + case C_RAM: + fscanf(stream, "%d %d ", &(p->eqs[i].Ram.addr_size), &(p->eqs[i].Ram.word_size)); + read_arg(stream, &(p->eqs[i].Ram.read_addr)); + read_arg(stream, &(p->eqs[i].Ram.write_enable)); + read_arg(stream, &(p->eqs[i].Ram.write_enable)); + read_arg(stream, &(p->eqs[i].Ram.data)); + break; + case C_CONCAT: + read_arg(stream, &(p->eqs[i].Mux.a)); + read_arg(stream, &(p->eqs[i].Mux.b)); + break; + case C_SLICE: + fscanf(stream, "%d %d ", &(p->eqs[i].Slice.begin), &(p->eqs[i].Slice.end)); + read_arg(stream, &(p->eqs[i].Slice.source)); + break; + case C_SELECT: + fscanf(stream, "%d ", &(p->eqs[i].Select.i)); + read_arg(stream, &(p->eqs[i].Select.source)); + break; + } + } +} diff --git a/csim/main.c b/csim/main.c new file mode 100644 index 0000000..ce3f5b6 --- /dev/null +++ b/csim/main.c @@ -0,0 +1,97 @@ +/* + Système Digital + 2013-2014 + Alex AUVOLAT + + main.c Main file for the C simulator +*/ + +#include +#include +#include + +#include "sim.h" + +void usage() { + printf ("\nUsage:\n\tcsim [options] \n\n"); + printf("Available options:\n"); + printf("\n -rom \n\tLoad a filename as a ROM file for the machine\n"); + printf("\n -n \n\tOnly run #steps steps of simulation (-1 = infinity)\n"); + printf("\n -in \n\tRead inputs from given file (eg. named pipe). Defaults to STDIN.\n"); + printf("\n -out \n\tWrite outputs to given file (eg. named pipe). Defaults to STDOut.\n"); + exit(1); +} + +// Arguments to be parsed +int steps = 42; +char *romfile = NULL; +char *filename = NULL; +char *infile = NULL; +char *outfile = NULL; + +int main(int argc, char **argv) { + int i; + for (i = 1; i < argc; i++) { + if (!strcmp(argv[i], "-rom")) { + if (++i == argc) usage(); + romfile = argv[i]; + } else if (!strcmp(argv[i], "-n")) { + if (++i == argc) usage(); + steps = atoi(argv[i]); + } else if (!strcmp(argv[i], "-in")) { + if (++i == argc) usage(); + infile = argv[i]; + } else if (!strcmp(argv[i], "-out")) { + if (++i == argc) usage(); + outfile = argv[i]; + } else { + filename = argv[i]; + } + } + + if (filename == NULL) usage(); + + // Load program + FILE *p_in; + p_in = fopen(filename, "r"); + if (!p_in) { + fprintf(stderr, "Error: could not open file %s for input.\n", filename); + return 1; + } + t_program* program = load_dumb_netlist(p_in); + fclose(p_in); + + // Setup input and outputs + FILE *input = stdin, *output = stdout; + if (infile != NULL) { + input = fopen(infile, "r"); + if (!infile) { + fprintf(stderr, "Error: could not open file %s for input.\n", infile); + return 1; + } + } + if (outfile != NULL) { + output = fopen(outfile, "w"); + if (!output) { + fprintf(stderr, "Error: could not open file %s for output.\n", outfile); + return 1; + } + } + + // Run + t_machine *machine = init_machine(program); + while (i < steps || steps == -1) { + read_inputs(machine, input); + machine_step(machine); + write_outputs(machine, output); + } + + // Cleanup + if (input != stdin) fclose(input); + if (output != stdout) fclose(output); + + // No need to free memory, the OS deletes everything anyways when the process ends. + + return 0; +} + diff --git a/csim/sim.c b/csim/sim.c new file mode 100644 index 0000000..27827d5 --- /dev/null +++ b/csim/sim.c @@ -0,0 +1,23 @@ +/* + Système Digital + 2013-2014 + Alex AUVOLAT + + sim.c The code that actually runs the machine +*/ + +#include "sim.h" + +t_machine *init_machine (t_program *p) { +} + +void read_inputs(t_machine *m, FILE *stream) { +} + +void machine_step(t_machine *m) { +} + +void write_outputs(t_machine *m, FILE *stream) { +} + + diff --git a/csim/sim.h b/csim/sim.h new file mode 100644 index 0000000..75f3502 --- /dev/null +++ b/csim/sim.h @@ -0,0 +1,116 @@ +#ifndef DEF_SIM_H +#define DEF_SIM_H + +// TODO implement ROM + +#include + +// Gate types +#define C_ARG 0 +#define C_REG 1 +#define C_NOT 2 +#define C_BINOP 3 +#define C_MUX 4 +#define C_ROM 5 +#define C_RAM 6 +#define C_CONCAT 7 +#define C_SLICE 8 +#define C_SELECT 9 + +// Binary operators +#define OP_OR 0 +#define OP_XOR 1 +#define OP_AND 2 +#define OP_NAND 3 + +// Data structures +typedef unsigned long long int t_value; +typedef int t_id; + +typedef struct { // a variable in the simulator + t_value mask; + int size; + char *name; +} t_variable; + +typedef struct { + t_value val; + t_id source_var; // if source_var == -1 then it's a direct value, else it's that variable +} t_arg; + +typedef struct { + int type; + t_id dest_var; + union { + struct { + t_arg a; + } Arg; + struct { + t_id var; + } Reg; + struct { + t_arg a; + } Not; + struct { + int op; + t_arg a, b; + } Binop; + struct { + t_arg a, b, c; + } Mux; + struct { + int addr_size, word_size; + t_arg read_addr; + } Rom; + struct { + int addr_size, word_size; + t_arg read_addr, write_enable, write_addr, data; + } Ram; + struct { + t_arg a, b; + } Concat; + struct { + int begin, end; + t_arg source; + } Slice; + struct { + int i; + t_arg source; + } Select; + }; +} t_equation; + + +typedef struct { + int n_vars, n_inputs, n_outputs; + t_variable *vars; + t_id *inputs, *outputs; + + int n_eqs; + t_equation *eqs; +} t_program; + +// machine = execution instance + +typedef union { + t_value r_val; + t_value *mem_val; +} t_mem_reg_data; + +typedef struct { + t_program *prog; + t_value *var_values; + t_mem_reg_data *mem_data; +} t_machine; + + +// The functions for doing stuff with these data structures + +t_program *load_dumb_netlist(FILE *stream); +t_machine *init_machine(t_program *p); +void read_inputs(t_machine *m, FILE *stream); +void machine_step(t_machine *m); +void write_outputs(t_machine *m, FILE *stream); + + +#endif 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 +%token 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 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 "@[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(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(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(a:[n],b:[n]) = (o:[n]) where + if n = 0 then + o = [] + else + o = (a[0] and b[0]).(or_n(a[1..], b[1..])) + end if +end where + +main(ra:[addr], we, wa:[addr], c:[word]) = (o:[word]) where + o = ram(ra, we, wa, or_n(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 + diff --git a/tp1/_tags b/tp1/_tags deleted file mode 100644 index 503ce62..0000000 --- a/tp1/_tags +++ /dev/null @@ -1,3 +0,0 @@ -true: use_menhir -<*.ml>: debug -<*.byte>: use_unix, debug \ No newline at end of file diff --git a/tp1/graph.ml b/tp1/graph.ml deleted file mode 100644 index 54128ff..0000000 --- a/tp1/graph.ml +++ /dev/null @@ -1,61 +0,0 @@ -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/tp1/graph_test.ml b/tp1/graph_test.ml deleted file mode 100644 index ac31677..0000000 --- a/tp1/graph_test.ml +++ /dev/null @@ -1,28 +0,0 @@ -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/tp1/netlist.ml b/tp1/netlist.ml deleted file mode 100644 index b1d7932..0000000 --- a/tp1/netlist.ml +++ /dev/null @@ -1,17 +0,0 @@ -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/tp1/netlist_ast.ml b/tp1/netlist_ast.ml deleted file mode 100644 index ae16888..0000000 --- a/tp1/netlist_ast.ml +++ /dev/null @@ -1,42 +0,0 @@ -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/tp1/netlist_lexer.mll b/tp1/netlist_lexer.mll deleted file mode 100644 index 78b0410..0000000 --- a/tp1/netlist_lexer.mll +++ /dev/null @@ -1,37 +0,0 @@ -{ -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/tp1/netlist_parser.mly b/tp1/netlist_parser.mly deleted file mode 100644 index 0908703..0000000 --- a/tp1/netlist_parser.mly +++ /dev/null @@ -1,70 +0,0 @@ -%{ - 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 -%token 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 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/tp1/netlist_printer.ml b/tp1/netlist_printer.ml deleted file mode 100644 index d513137..0000000 --- a/tp1/netlist_printer.ml +++ /dev/null @@ -1,82 +0,0 @@ -open Netlist_ast -open Format - -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 "@[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 "@." diff --git a/tp1/netlist_simulator.byte b/tp1/netlist_simulator.byte deleted file mode 100755 index 155d39a..0000000 Binary files a/tp1/netlist_simulator.byte and /dev/null differ diff --git a/tp1/scheduler.ml b/tp1/scheduler.ml deleted file mode 100644 index 130164b..0000000 --- a/tp1/scheduler.ml +++ /dev/null @@ -1,52 +0,0 @@ -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/tp1/scheduler_test.ml b/tp1/scheduler_test.ml deleted file mode 100644 index 20c20f5..0000000 --- a/tp1/scheduler_test.ml +++ /dev/null @@ -1,41 +0,0 @@ -let print_only = ref false -let number_steps = ref (-1) - -let compile filename = - try - let p = Netlist.read_file filename in - let out_name = (Filename.chop_suffix filename ".net") ^ "_sch.net" in - let out = open_out out_name in - let close_all () = - close_out out - in - begin try - let p = Scheduler.schedule p in - Netlist_printer.print_program out p; - with - | Scheduler.Combinational_cycle -> - Format.eprintf "The netlist has a combinatory cycle.@."; - close_all (); exit 2 - end; - close_all (); - if not !print_only then ( - let simulator = - if !number_steps = -1 then - "./netlist_simulator.byte" - else - "./netlist_simulator.byte -n "^(string_of_int !number_steps) - in - ignore (Unix.system (simulator^" "^out_name)) - ) - with - | Netlist.Parse_error s -> Format.eprintf "An error accurred: %s@." s; exit 2 - -let main () = - Arg.parse - ["-print", Arg.Set print_only, "Only print the result of scheduling"; - "-n", Arg.Set_int number_steps, "Number of steps to simulate"] - compile - "" -;; - -main () diff --git a/tp1/test/clock_div.mj b/tp1/test/clock_div.mj deleted file mode 100644 index ad1e919..0000000 --- a/tp1/test/clock_div.mj +++ /dev/null @@ -1,4 +0,0 @@ -main() = (o) where - o = reg(c); - c = not (reg (o)) -end where \ No newline at end of file diff --git a/tp1/test/clock_div.net b/tp1/test/clock_div.net deleted file mode 100644 index 9a17fc7..0000000 --- a/tp1/test/clock_div.net +++ /dev/null @@ -1,9 +0,0 @@ -INPUT -OUTPUT o -VAR - _l_2, c, o -IN -c = NOT _l_2 -o = REG c -_l_2 = REG o - diff --git a/tp1/test/cm2.mj b/tp1/test/cm2.mj deleted file mode 100644 index 8863bf1..0000000 --- a/tp1/test/cm2.mj +++ /dev/null @@ -1,4 +0,0 @@ -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/tp1/test/cm2.net b/tp1/test/cm2.net deleted file mode 100644 index e296b96..0000000 --- a/tp1/test/cm2.net +++ /dev/null @@ -1,9 +0,0 @@ -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/tp1/test/fulladder.mj b/tp1/test/fulladder.mj deleted file mode 100644 index c4b6b0e..0000000 --- a/tp1/test/fulladder.mj +++ /dev/null @@ -1,4 +0,0 @@ -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/tp1/test/fulladder.net b/tp1/test/fulladder.net deleted file mode 100644 index b2271c2..0000000 --- a/tp1/test/fulladder.net +++ /dev/null @@ -1,12 +0,0 @@ -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/tp1/test/nadder.mj b/tp1/test/nadder.mj deleted file mode 100644 index 0c95386..0000000 --- a/tp1/test/nadder.mj +++ /dev/null @@ -1,19 +0,0 @@ -fulladder(a,b,c) = (s, r) where - s = (a ^ b) ^ c; - r = (a & b) + ((a ^ b) & c); -end where - -adder(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(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/tp1/test/nadder.net b/tp1/test/nadder.net deleted file mode 100644 index bf87051..0000000 --- a/tp1/test/nadder.net +++ /dev/null @@ -1,17 +0,0 @@ -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/tp1/test/ram.mj b/tp1/test/ram.mj deleted file mode 100644 index 7c4d1ed..0000000 --- a/tp1/test/ram.mj +++ /dev/null @@ -1,15 +0,0 @@ -const addr = 2 -const word = 4 - -or_n(a:[n],b:[n]) = (o:[n]) where - if n = 0 then - o = [] - else - o = (a[0] and b[0]).(or_n(a[1..], b[1..])) - end if -end where - -main(ra:[addr], we, wa:[addr], c:[word]) = (o:[word]) where - o = ram(ra, we, wa, or_n(o, c)) -end where - diff --git a/tp1/test/ram.net b/tp1/test/ram.net deleted file mode 100644 index ee4570a..0000000 --- a/tp1/test/ram.net +++ /dev/null @@ -1,32 +0,0 @@ -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 - -- cgit v1.2.3