diff options
| -rw-r--r-- | README | 136 | ||||
| -rw-r--r-- | camlsim/_tags | 3 | ||||
| -rw-r--r-- | camlsim/machine.ml | 174 | ||||
| -rw-r--r-- | camlsim/netlist.ml | 17 | ||||
| -rw-r--r-- | camlsim/netlist_ast.ml | 42 | ||||
| -rw-r--r-- | camlsim/netlist_lexer.mll | 37 | ||||
| -rw-r--r-- | camlsim/netlist_parser.mly | 70 | ||||
| -rw-r--r-- | camlsim/simulator.ml | 67 | ||||
| -rw-r--r-- | csim/load.c | 304 | ||||
| -rw-r--r-- | csim/main.c | 154 | ||||
| -rw-r--r-- | csim/sim.c | 382 | ||||
| -rw-r--r-- | csim/sim.h | 122 | ||||
| -rw-r--r-- | csim/util.c | 52 | ||||
| -rw-r--r-- | sched/graph.ml | 48 | ||||
| -rw-r--r-- | sched/main.ml | 38 | ||||
| -rw-r--r-- | sched/netlist_dumb.ml | 372 | ||||
| -rw-r--r-- | sched/scheduler.ml | 130 | ||||
| -rw-r--r-- | sched/simplify.ml | 568 |
18 files changed, 1149 insertions, 1567 deletions
@@ -11,48 +11,40 @@ Contents of the repository : ---------------------------- sched/ - A scheduler for netlists. - Input : a netlist. - Output : a netlist with topologically sorted operators - plus a dumbed-down version for input to the C circuit simulator - This program is also capable of a few optimisation (usually reduces netlist - size by 1/4 or 1/3). - $ cd sched/ - $ ocamlbuild main.byte + A scheduler for netlists. + Input : a netlist. + Output : a netlist with topologically sorted operators + plus a dumbed-down version for input to the C circuit simulator + This program is also capable of a few optimisation (usually reduces netlist + size by 1/4 or 1/3). + $ cd sched/ + $ ocamlbuild main.byte csim/ - A circuit simulator written in C. - This program does NOT do the scheduling. - This program does NOT read a netlist, it reads a specifically formatted - dumbed-down netlist, that is output by the scheduler. - $ cd csim/ - $ make - -camlsim/ - A circuit simulator written in OCaml. - This program does NOT do the scheduling. The netlist must be passed through - the scheduler first. - This program is *highly incomplete* and not recomended for real use.. - $ cd camlsim/ - $ ocamlbuild simulator.byte + A circuit simulator written in C. + This program does NOT do the scheduling. + This program does NOT read a netlist, it reads a specifically formatted + dumbed-down netlist, that is output by the scheduler. + $ cd csim/ + $ make minijazz/ - The MiniJazz compiler (given by the teachers). + The MiniJazz compiler (given by the teachers). tests/ - Various test files. + Various test files. *.pdf - Documentation about the project. + Documentation about the project. REFERENCES ---------- - - Computer organization and design : the hardware/software interface - 4th ed - Chapters 2 to 4 + - Computer organization and design : the hardware/software interface + 4th ed + Chapters 2 to 4 @@ -63,15 +55,15 @@ Convention for binary values ---------------------------- /!\ This convention is contrary to the one used in the example file nadder.mj - (Therefore I have modified that file...) + (Therefore I have modified that file...) The bit array [a_0 a_1 a_2 ... a_n-1] represents the decimal number : - a_0 + 2*a_1 + 4*a_2 + ... + 2^(n-1)*a_n-1 + a_0 + 2*a_1 + 4*a_2 + ... + 2^(n-1)*a_n-1 When represented in binary, we write the bits in the order : - a_0 a_1 a_2 ... a_n-1 + a_0 a_1 a_2 ... a_n-1 Even though the normal notation for a binary number is : - a_n-1 a_n-2 ... a_0 + a_n-1 a_n-2 ... a_0 /!\ BINARY NUMBERS ARE WRITTEN REVERSE ! @@ -115,29 +107,29 @@ list given in *1 (the first line gives variable #0, etc.) Table of equation types : -Type# Desc Arguments -0 Arg <arg> -1 Reg <var#> -2 Not <arg> -3 Binop <op# *4> <arg> <arg> -4 Mux <arg> <arg:when false> <arg:when true> -5 Rom <addr_size> <word_size> <arg:read_addr> -6 Ram <addr_size> <word_size> <arg:read_addr> <arg:write_enable> - <arg:write_addr> <arg:data> -7 Concat <arg> <arg> -8 Slice <begin> <end> <arg> -9 Select <id> <arg> +Type# Desc Arguments +0 Arg <arg> +1 Reg <var#> +2 Not <arg> +3 Binop <op# *4> <arg> <arg> +4 Mux <arg> <arg:when false> <arg:when true> +5 Rom <addr_size> <word_size> <arg:read_addr> +6 Ram <addr_size> <word_size> <arg:read_addr> <arg:write_enable> + <arg:write_addr> <arg:data> +7 Concat <arg> <arg> +8 Slice <begin> <end> <arg> +9 Select <id> <arg> An argument (<arg> or <arg:*>) can be either a binary value, represented by the bits in standard order defined above, either a reference to another variable, with the syntax $<var_id> *4 : The operators are : -0 OR -1 XOR -2 AND -3 NAND - +0 OR +1 XOR +2 AND +3 NAND + This syntax is formalized by the reference implementation provided in the source file csim/load.h. @@ -155,38 +147,38 @@ This is the description of the format currently used by the C simulator. <var count> [for each variable] - <var size> <var name> + <var size> <var name> <input list size> [for each input <input var id>] <out list size> [for each input <output var id>] <register list size> [for each register] - <register destination variable> <register source variable> + <register destination variable> <register source variable> <ram list size> [for each ram] - <addr size> <word size> - <write enable var> <write addr var> <data var> + <addr size> <word size> + <write enable var> <write addr var> <data var> <equation list size> [for each equation] - <destination variable> <equation type> <args...> + <destination variable> <equation type> <args...> Equation types : -ID DESCR ARGS --- ----- ---- -0 Copy var_id -1 Not var_id -2 Binop op_id var_a_id var_b_id -3 Mux var_a_id var_b_id -4 ROM addr_size word_size write_addr_var_id -5 Concat var_a var_b -6 Slice begin end var_id -7 Select number var_id -8 RAM Read ram_number var_id +ID DESCR ARGS +-- ----- ---- +0 Copy var_id +1 Not var_id +2 Binop op_id var_a_id var_b_id +3 Mux var_a_id var_b_id +4 ROM addr_size word_size write_addr_var_id +5 Concat var_a var_b +6 Slice begin end var_id +7 Select number var_id +8 RAM Read ram_number var_id Operators : -0 OR -1 XOR -2 AND -3 NAND +0 OR +1 XOR +2 AND +3 NAND Constant variables are standardized so that their name (eg. $00101) gives the value of the constant, therefore there is no need to write a constant @@ -224,13 +216,13 @@ To know what file to load in a ROM chip, we recognize a certain prefix in the name of the variable holding the ROM. For example, if we have in a netlist the following line : - decode7_128 = ROM 4 7 _l_42_122 + decode7_128 = ROM 4 7 _l_42_122 which is a possible output for the MiniJazz compiler, and if the simulator is provided with the command-line argument : - -rom decode7 path/to/decode7.rom - + -rom decode7 path/to/decode7.rom + then the simulator will detect the prefix `decode7` in the variable name decode7_128, and use the ROM data from the file specified on the command line. diff --git a/camlsim/_tags b/camlsim/_tags deleted file mode 100644 index 503ce62..0000000 --- a/camlsim/_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/camlsim/machine.ml b/camlsim/machine.ml deleted file mode 100644 index 232cb08..0000000 --- a/camlsim/machine.ml +++ /dev/null @@ -1,174 +0,0 @@ -(* - Système Digital, cours de J.Vuillemin, 2013-2013 - Alex AUVOLAT, ENS INFO 2013 - - Circuit Simulator, machine simulator - - ASSUMPTIONS: - - Only one ROM chip -*) - -open Netlist_ast - -exception Error of string -exception Is_not_modified - -let load_rom filename = - () (* TODO *) - - -type ram_prop = int * int (* addr size ; word size *) -type machine = { - p : program; - mutable vars : value Env.t; - mutable regs : value Env.t; - ram_chips : ram_prop array; - ram : value array array; -} - -let rec two_to_the = function - | 0 -> 1 - | n -> let k = (two_to_the (n/2)) in - if n mod 2 = 1 then 2 * k else k - -let create p = - let ram_chips = Array.of_list - (List.fold_left - (fun x (_, v) -> match v with - | Eram (a, w, _, _, _, _) -> - (a, w)::x - | _ -> x) - [] - p.p_eqs) in - let vars = Env.fold - (fun k v x -> - Env.add k - (match v with - | TBit -> VBit(false) - | TBitArray(n) -> VBitArray(Array.make n false)) - x) - p.p_vars - Env.empty in - { - p = p; - vars = vars; - regs = Env.empty; (* no use putting anything at the moment *) - ram_chips = ram_chips; - ram = Array.map - (fun (a, w) -> Array.make (two_to_the a) (VBitArray (Array.make w false))) - ram_chips; - } - -let read_inputs m f = - List.iter - (fun n -> - m.vars <- Env.add n (f (n, Env.find n m.p.p_vars)) m.vars) - m.p.p_inputs - -let step m = - let get = function - | Avar(x) -> - begin match Env.find x m.vars with - | VBit(x) -> VBit(x) - | VBitArray(u) as s -> - if Array.length u = 1 then VBit(u.(0)) else s - end - | Aconst(x) -> x - in - (* Load register values into dest variables *) - Env.iter - (fun k v -> - m.vars <- Env.add k v m.vars) - m.regs; - (* Do all the logic *) - List.iter - (fun (varname, exp) -> - let evaluate = function - | Earg(k) -> get k - | Ereg(_) -> raise Is_not_modified (* do nothing, registers are handled somewhere else *) - | Enot(k) -> - begin match get k with - | VBit(u) -> VBit (not u) - | VBitArray(u) -> VBitArray(Array.map (fun x -> not x) u) - end - | Ebinop(op, k1, k2) -> - let f = begin match op with - | Or -> (fun x y -> x || y) - | Xor -> (fun x y -> (x || y) && (not (x && y))) - | And -> (fun x y -> x && y) - | Nand -> (fun x y -> not (x && y)) - end in - begin match get k1, get k2 with - | VBit(u), VBit(v) -> VBit(f u v) - | VBitArray(u), VBitArray(v) when Array.length u = Array.length v -> - let r = Array.make (Array.length u) false in - for i = 0 to Array.length u - 1 do - r.(i) <- (f u.(i) v.(i)) - done; VBitArray(r) - | VBit(u), VBitArray(v) -> VBit(f u v.(0)) - | VBitArray(u), VBit(v) -> VBit(f u.(0) v) - | _ -> raise (Error "Incompatible data types.") - end - | Emux (control, in0, in1) -> - begin match get control, get in0, get in1 with - | VBit(u), x, y -> - if u then y else x - | VBitArray(u), VBitArray(a), VBitArray(b) - when Array.length a = Array.length b - && Array.length u = Array.length a -> - let r = Array.make (Array.length u) false in - for i = 0 to Array.length u - 1 do - r.(i) <- (if u.(i) then b.(i) else a.(i)) - done; - VBitArray(r) - | _ -> raise (Error "Invalid data size in mux") - end - | Erom(_, w, _) -> VBitArray(Array.make w false) (* TODO *) - | Eram(_, _, _,_, _, _) -> raise Is_not_modified (* TODO *) - | Econcat(k1, k2) -> - let a1 = match get k1 with - | VBit(u) -> [|u|] - | VBitArray(u) -> u - in - let a2 = match get k2 with - | VBit(u) -> [|u|] - | VBitArray(u) -> u - in - VBitArray(Array.append a1 a2) - | Eslice (first, last, k) -> - begin match get k with - | VBit(u) when first = 0 && last = 0 -> VBit(u) - | VBitArray(u) -> - let r = Array.make (last - first) false in - for i = first to last - 1 do - r.(i - first) <- u.(i) - done; - VBitArray(u) - | _ -> raise (Error "Invalid slicing parameters") - end - | Eselect(id, k) -> - begin match get k with - | VBit(u) when id = 0 -> VBit(u) - | VBitArray(u) -> VBit(u.(id)) - | _ -> raise (Error "Invalid select parameters") - end - in - try - m.vars <- Env.add varname (evaluate exp) m.vars - with Is_not_modified -> ()) - m.p.p_eqs; - (* Saves register values *) - m.regs <- List.fold_left - (fun x (k, v) -> - match v with - | Ereg(n) -> Env.add k (Env.find n m.vars) x - | _ -> x) - Env.empty - m.p.p_eqs - -let print_outputs m f = - List.iter - (fun n -> - f (n, Env.find n m.vars)) - m.p.p_outputs - diff --git a/camlsim/netlist.ml b/camlsim/netlist.ml deleted file mode 100644 index b1d7932..0000000 --- a/camlsim/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/camlsim/netlist_ast.ml b/camlsim/netlist_ast.ml deleted file mode 100644 index ae16888..0000000 --- a/camlsim/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/camlsim/netlist_lexer.mll b/camlsim/netlist_lexer.mll deleted file mode 100644 index 78b0410..0000000 --- a/camlsim/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/camlsim/netlist_parser.mly b/camlsim/netlist_parser.mly deleted file mode 100644 index 0908703..0000000 --- a/camlsim/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> 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/camlsim/simulator.ml b/camlsim/simulator.ml deleted file mode 100644 index fbb831a..0000000 --- a/camlsim/simulator.ml +++ /dev/null @@ -1,67 +0,0 @@ -(* - Système Digital, cours de J.Vuillemin, 2013-2013 - Alex AUVOLAT, ENS INFO 2013 - - Circuit Simulator, main file -*) - -open Netlist_ast - -let num_steps = ref (-1) -let step = ref 0 - -let read_input = function - | (s, TBit) -> Format.printf "%s (1 bit) : @?" s; - let k = ref (read_line()) in - while String.length !k < 1 do - Format.printf "Too short. Retry : "; - k := read_line(); - done; - VBit ((!k).[0] = '1') - | (s, TBitArray(n)) -> Format.printf "%s (%d bits) : @?" s n; - let k = ref (read_line()) in - while String.length !k < 1 do - Format.printf "Too short. Retry : "; - k := read_line(); - done; - let r = Array.make n false in - for i = 0 to n-1 do - r.(i) <- ((!k).[i] = '1') - done; - VBitArray(r) - -let print_output = function - | (n, VBit (b)) -> - Format.printf "%s\t: %d@." n (if b then 1 else 0) - | (n, VBitArray (a)) -> - Format.printf "%s\t: " n; - for i = 0 to Array.length a - 1 do - Format.printf "%d" (if a.(i) then 1 else 0) - done; - Format.printf "@." - -let loadrun filename = - let p = Netlist.read_file filename in - - let machine = Machine.create p in - - while !num_steps > !step || !num_steps == -1 do - step := !step + 1; - Format.printf "Step #%d@." !step; - - Machine.read_inputs machine read_input; - Machine.step machine; - Machine.print_outputs machine print_output - done - -let () = - try - Arg.parse - ["-rom", Arg.String(Machine.load_rom), "Load one ROM file into the simulator (will be used by all ROM chips)."; - "-n", Arg.Set_int num_steps, "Number of steps to simulate"] - loadrun - "" - with - | Netlist.Parse_error s -> Format.eprintf "An error occurred: %s@." s; exit 2 - | Machine.Error s -> Format.eprintf "An error occurred: %s@." s; exit 2 - diff --git a/csim/load.c b/csim/load.c index 607e0e2..4e7583a 100644 --- a/csim/load.c +++ b/csim/load.c @@ -1,10 +1,10 @@ /* - Système Digital - 2013-2014 - Alex AUVOLAT + Système Digital + 2013-2014 + Alex AUVOLAT - load.c Code for loading dumbed-down netlist files - (no parsing of .net files !!) + load.c Code for loading dumbed-down netlist files + (no parsing of .net files !!) */ #include <stdlib.h> @@ -14,154 +14,154 @@ t_rom *roms = NULL; void add_rom(const char *prefix, FILE *file) { - int i; - - t_rom *rom = malloc(sizeof(t_rom)); - rom->prefix = prefix; - - // Load ROM file - fscanf(file, "%d %d\n", &(rom->addr_size), &(rom->word_size)); - rom->data = malloc(pow2(rom->addr_size) * sizeof(t_value)); - - for (i = 0; i < pow2(rom->addr_size); i++) { - fscanf(file, " "); - if (fscanf(file, "/%lu", &(rom->data[i]))) { - // ok, value is read - } else { - rom->data[i] = read_bool(file, NULL); - } - } - - rom->next = roms; - roms = rom; + int i; + + t_rom *rom = malloc(sizeof(t_rom)); + rom->prefix = prefix; + + // Load ROM file + fscanf(file, "%d %d\n", &(rom->addr_size), &(rom->word_size)); + rom->data = malloc(pow2(rom->addr_size) * sizeof(t_value)); + + for (i = 0; i < pow2(rom->addr_size); i++) { + fscanf(file, " "); + if (fscanf(file, "/%lu", &(rom->data[i]))) { + // ok, value is read + } else { + rom->data[i] = read_bool(file, NULL); + } + } + + rom->next = roms; + roms = rom; } t_program *load_dumb_netlist (FILE *stream) { - int i, j, as, ws; - t_rom *r; - - // 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)); - for(j = 0; j < p->vars[i].size; j++) { - p->vars[i].mask = (p->vars[i].mask << 1) | 1; - } - - 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); - - if (p->vars[i].size >= 8*sizeof(t_value)) { - fprintf(stderr, "Warning: variable %s might be too big for machine integers.\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 register list - fscanf(stream, "%d", &(p->n_regs)); - p->regs = malloc(p->n_regs * sizeof(t_reg)); - for (i = 0; i < p->n_regs; i++) { - fscanf(stream, "%d %d\n", &(p->regs[i].dest), &(p->regs[i].source)); - } - // read RAM list - fscanf(stream, "%d", &(p->n_rams)); - p->rams = malloc(p->n_rams * sizeof(t_ram)); - for (i = 0; i < p->n_rams; i++) { - fscanf(stream, "%d %d %d %d %d\n", - &(p->rams[i].addr_size), - &(p->rams[i].word_size), - &(p->rams[i].write_enable), - &(p->rams[i].write_addr), &(p->rams[i].data)); - } - - // 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_COPY: - fscanf(stream, "%d ", &(p->eqs[i].Copy.a)); - break; - case C_NOT: - fscanf(stream, "%d ", &(p->eqs[i].Not.a)); - break; - case C_BINOP: - fscanf(stream, "%d %d %d ", - &(p->eqs[i].Binop.op), - &(p->eqs[i].Binop.a), - &(p->eqs[i].Binop.b)); - break; - case C_MUX: - fscanf(stream, "%d %d %d ", - &(p->eqs[i].Mux.a), - &(p->eqs[i].Mux.b), - &(p->eqs[i].Mux.c)); - break; - case C_ROM: - fscanf(stream, "%d %d %d ", - &as, &ws, - &(p->eqs[i].Rom.read_addr)); - p->eqs[i].Rom.rom = NULL; - // find corresponding ROM - for (r = roms; r != NULL; r = r->next) { - if (is_prefix(r->prefix, p->vars[p->eqs[i].dest_var].name)) { - if (r->addr_size == as && r->word_size == ws) { - p->eqs[i].Rom.rom = r; - break; - } else { - fprintf(stderr, - "Error: ROM prefixed by '%s' does not have size corresponding to variable that uses it.\n", - r->prefix); - } - } - } - if (p->eqs[i].Rom.rom == NULL) - fprintf(stderr, "Warning: ROM variable '%s' has no ROM data.\n", - p->vars[p->eqs[i].dest_var].name); - break; - case C_CONCAT: - fscanf(stream, "%d %d ", - &(p->eqs[i].Concat.a), - &(p->eqs[i].Concat.b)); - p->eqs[i].Concat.shift = p->vars[p->eqs[i].Concat.a].size; - break; - case C_SLICE: - fscanf(stream, "%d %d %d ", - &(p->eqs[i].Slice.begin), - &(p->eqs[i].Slice.end), - &(p->eqs[i].Slice.source)); - break; - case C_SELECT: - fscanf(stream, "%d %d ", - &(p->eqs[i].Select.i), - &(p->eqs[i].Select.source)); - break; - case C_READRAM: - fscanf(stream, "%d %d ", - &(p->eqs[i].ReadRAM.ram_id), - &(p->eqs[i].ReadRAM.source)); - break; - } - } - - return p; + int i, j, as, ws; + t_rom *r; + + // 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)); + for(j = 0; j < p->vars[i].size; j++) { + p->vars[i].mask = (p->vars[i].mask << 1) | 1; + } + + 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); + + if (p->vars[i].size >= 8*sizeof(t_value)) { + fprintf(stderr, "Warning: variable %s might be too big for machine integers.\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 register list + fscanf(stream, "%d", &(p->n_regs)); + p->regs = malloc(p->n_regs * sizeof(t_reg)); + for (i = 0; i < p->n_regs; i++) { + fscanf(stream, "%d %d\n", &(p->regs[i].dest), &(p->regs[i].source)); + } + // read RAM list + fscanf(stream, "%d", &(p->n_rams)); + p->rams = malloc(p->n_rams * sizeof(t_ram)); + for (i = 0; i < p->n_rams; i++) { + fscanf(stream, "%d %d %d %d %d\n", + &(p->rams[i].addr_size), + &(p->rams[i].word_size), + &(p->rams[i].write_enable), + &(p->rams[i].write_addr), &(p->rams[i].data)); + } + + // 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_COPY: + fscanf(stream, "%d ", &(p->eqs[i].Copy.a)); + break; + case C_NOT: + fscanf(stream, "%d ", &(p->eqs[i].Not.a)); + break; + case C_BINOP: + fscanf(stream, "%d %d %d ", + &(p->eqs[i].Binop.op), + &(p->eqs[i].Binop.a), + &(p->eqs[i].Binop.b)); + break; + case C_MUX: + fscanf(stream, "%d %d %d ", + &(p->eqs[i].Mux.a), + &(p->eqs[i].Mux.b), + &(p->eqs[i].Mux.c)); + break; + case C_ROM: + fscanf(stream, "%d %d %d ", + &as, &ws, + &(p->eqs[i].Rom.read_addr)); + p->eqs[i].Rom.rom = NULL; + // find corresponding ROM + for (r = roms; r != NULL; r = r->next) { + if (is_prefix(r->prefix, p->vars[p->eqs[i].dest_var].name)) { + if (r->addr_size == as && r->word_size == ws) { + p->eqs[i].Rom.rom = r; + break; + } else { + fprintf(stderr, + "Error: ROM prefixed by '%s' does not have size corresponding to variable that uses it.\n", + r->prefix); + } + } + } + if (p->eqs[i].Rom.rom == NULL) + fprintf(stderr, "Warning: ROM variable '%s' has no ROM data.\n", + p->vars[p->eqs[i].dest_var].name); + break; + case C_CONCAT: + fscanf(stream, "%d %d ", + &(p->eqs[i].Concat.a), + &(p->eqs[i].Concat.b)); + p->eqs[i].Concat.shift = p->vars[p->eqs[i].Concat.a].size; + break; + case C_SLICE: + fscanf(stream, "%d %d %d ", + &(p->eqs[i].Slice.begin), + &(p->eqs[i].Slice.end), + &(p->eqs[i].Slice.source)); + break; + case C_SELECT: + fscanf(stream, "%d %d ", + &(p->eqs[i].Select.i), + &(p->eqs[i].Select.source)); + break; + case C_READRAM: + fscanf(stream, "%d %d ", + &(p->eqs[i].ReadRAM.ram_id), + &(p->eqs[i].ReadRAM.source)); + break; + } + } + + return p; } diff --git a/csim/main.c b/csim/main.c index 6e5bc29..5689cb4 100644 --- a/csim/main.c +++ b/csim/main.c @@ -1,9 +1,9 @@ /* - Système Digital - 2013-2014 - Alex AUVOLAT + Système Digital + 2013-2014 + Alex AUVOLAT - main.c Main file for the C simulator + main.c Main file for the C simulator */ #include <stdlib.h> @@ -14,14 +14,14 @@ void usage() { - printf ("\nUsage:\n\tcsim [options] <netlist_file>\n\n"); - printf("Available options:\n"); - printf("\n -rom <prefix> <file>\n\tLoad a filename as a ROM file for the machine\n"); - printf("\tA given ROM file is used for all ROM chips with variable name having given prefix\n"); - printf("\n -n <steps>\n\tOnly run #steps steps of simulation (0 = infinity)\n"); - printf("\n -in <in-file>\n\tRead inputs from given file (eg. named pipe). Defaults to STDIN.\n"); - printf("\n -out <out-file>\n\tWrite outputs to given file (eg. named pipe). Defaults to STDOut.\n"); - exit(1); + printf ("\nUsage:\n\tcsim [options] <netlist_file>\n\n"); + printf("Available options:\n"); + printf("\n -rom <prefix> <file>\n\tLoad a filename as a ROM file for the machine\n"); + printf("\tA given ROM file is used for all ROM chips with variable name having given prefix\n"); + printf("\n -n <steps>\n\tOnly run #steps steps of simulation (0 = infinity)\n"); + printf("\n -in <in-file>\n\tRead inputs from given file (eg. named pipe). Defaults to STDIN.\n"); + printf("\n -out <out-file>\n\tWrite outputs to given file (eg. named pipe). Defaults to STDOut.\n"); + exit(1); } // Arguments to be parsed @@ -31,77 +31,77 @@ 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(); - if (++i == argc) usage(); - FILE *rom = fopen(argv[i], "r"); - if (!rom) { - fprintf(stderr, "Could not open ROM file: '%s'\n", argv[i]); - return 1; - } - add_rom(argv[i-1], rom); - fclose(rom); - } 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]; - } - } + int i; + for (i = 1; i < argc; i++) { + if (!strcmp(argv[i], "-rom")) { + if (++i == argc) usage(); + if (++i == argc) usage(); + FILE *rom = fopen(argv[i], "r"); + if (!rom) { + fprintf(stderr, "Could not open ROM file: '%s'\n", argv[i]); + return 1; + } + add_rom(argv[i-1], rom); + fclose(rom); + } 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(); + 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); + // 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; - } - } + // 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); - i = 0; - while (i < steps || steps == 0) { - read_inputs(machine, input); - machine_step(machine); - write_outputs(machine, output); - i++; - } + // Run + t_machine *machine = init_machine(program); + i = 0; + while (i < steps || steps == 0) { + read_inputs(machine, input); + machine_step(machine); + write_outputs(machine, output); + i++; + } - // Cleanup - if (input != stdin) fclose(input); - if (output != stdout) fclose(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. + // No need to free memory, the OS deletes everything anyways when the process ends. - return 0; + return 0; } @@ -1,9 +1,9 @@ /* - Système Digital - 2013-2014 - Alex AUVOLAT + Système Digital + 2013-2014 + Alex AUVOLAT - sim.c The code that actually runs the machine + sim.c The code that actually runs the machine */ #include <stdlib.h> @@ -15,203 +15,203 @@ t_machine *init_machine (t_program *p) { - int i, j; - - t_machine *m = malloc(sizeof(t_machine)); - m->prog = p; - - // Allocate variables - m->var_values = malloc(p->n_vars * sizeof(t_value)); - for (i = 0; i < p->n_vars; i++) { - m->var_values[i] = 0; - if (p->vars[i].name[0] == '$') { - // setup constant value - t_value a = 1; - char *o = p->vars[i].name + 1; - while (*o) { - if (*o == '1') m->var_values[i] |= a; - a <<= 1; - o++; - } - } - } - - // Allocate space for registers and rams - m->reg_data = malloc(p->n_regs * sizeof(t_value)); - for (i = 0; i < p->n_regs; i++) { - m->reg_data[i] = 0; - } - m->ram_data = malloc(p->n_rams * sizeof(t_value*)); - for (i = 0; i < p->n_rams; i++) { - m->ram_data[i] = malloc(pow2(p->rams[i].addr_size) * sizeof(t_value)); - for (j = 0; j < pow2(p->rams[i].addr_size); j++) { - m->ram_data[i][j] = 0; - } - } - - return m; + int i, j; + + t_machine *m = malloc(sizeof(t_machine)); + m->prog = p; + + // Allocate variables + m->var_values = malloc(p->n_vars * sizeof(t_value)); + for (i = 0; i < p->n_vars; i++) { + m->var_values[i] = 0; + if (p->vars[i].name[0] == '$') { + // setup constant value + t_value a = 1; + char *o = p->vars[i].name + 1; + while (*o) { + if (*o == '1') m->var_values[i] |= a; + a <<= 1; + o++; + } + } + } + + // Allocate space for registers and rams + m->reg_data = malloc(p->n_regs * sizeof(t_value)); + for (i = 0; i < p->n_regs; i++) { + m->reg_data[i] = 0; + } + m->ram_data = malloc(p->n_rams * sizeof(t_value*)); + for (i = 0; i < p->n_rams; i++) { + m->ram_data[i] = malloc(pow2(p->rams[i].addr_size) * sizeof(t_value)); + for (j = 0; j < pow2(p->rams[i].addr_size); j++) { + m->ram_data[i][j] = 0; + } + } + + return m; } void read_inputs(t_machine *m, FILE *stream) { - /* FORMAT : - For each input in the list, *in the order specified*, - either '/' followed by the decimal value - or the binary value - */ - int i; - t_id var; - t_program *p = m->prog; - - if (p->n_inputs == 0) return; // nothing to do - - for (i = 0; i < p->n_inputs; i++) { - var = p->inputs[i]; - fscanf(stream, " "); - if (fscanf(stream, "/%lu", &(m->var_values[var]))) { - // ok, value is read - } else { - m->var_values[var] = read_bool(stream, NULL); - } - m->var_values[var] &= p->vars[var].mask; - } + /* FORMAT : + For each input in the list, *in the order specified*, + either '/' followed by the decimal value + or the binary value + */ + int i; + t_id var; + t_program *p = m->prog; + + if (p->n_inputs == 0) return; // nothing to do + + for (i = 0; i < p->n_inputs; i++) { + var = p->inputs[i]; + fscanf(stream, " "); + if (fscanf(stream, "/%lu", &(m->var_values[var]))) { + // ok, value is read + } else { + m->var_values[var] = read_bool(stream, NULL); + } + m->var_values[var] &= p->vars[var].mask; + } } void machine_step(t_machine *m) { - int i, j; - t_value a, b, c, d, e, ma, mb, v; - t_program *p = m->prog; - - // READ REGISTERS && MEMORY - for (i = 0; i < p->n_regs; i++) { - m->var_values[p->regs[i].dest] = m->reg_data[i]; - if (DEBUG) fprintf(stderr, "%s <- reg %s : %lx\n", - p->vars[p->regs[i].dest].name, - p->vars[p->regs[i].dest].name, - m->reg_data[i]); - } - - // DO THE LOGIC - for (i = 0; i < p->n_eqs; i++) { - v = 0; - switch (p->eqs[i].type) { - case C_COPY: - v = m->var_values[p->eqs[i].Copy.a]; - break; - case C_NOT: - v = ~m->var_values[p->eqs[i].Not.a]; - break; - case C_BINOP: - a = m->var_values[p->eqs[i].Binop.a]; - b = m->var_values[p->eqs[i].Binop.b]; - if (p->eqs[i].Binop.op == OP_OR) v = a | b; - if (p->eqs[i].Binop.op == OP_AND) v = a & b; - if (p->eqs[i].Binop.op == OP_XOR) v = a ^ b; - if (p->eqs[i].Binop.op == OP_NAND) v = ~(a & b); - break; - case C_MUX: - a = m->var_values[p->eqs[i].Mux.a]; - b = m->var_values[p->eqs[i].Mux.b]; - c = m->var_values[p->eqs[i].Mux.c]; - ma = m->prog->vars[p->eqs[i].Mux.a].mask; - if (ma == 1) { - v = (a ? c : b); - } else { - v = (a & c) | (~a & b); - } - break; - case C_ROM: - if (p->eqs[i].Rom.rom != NULL) { - a = m->var_values[p->eqs[i].Rom.read_addr]; - v = p->eqs[i].Rom.rom->data[a]; - } else { - v = 0; - } - break; - case C_CONCAT: - a = m->var_values[p->eqs[i].Concat.a]; - b = m->var_values[p->eqs[i].Concat.b]; - ma = p->vars[p->eqs[i].Concat.a].mask; - mb = p->vars[p->eqs[i].Concat.b].mask; - b <<= p->eqs[i].Concat.shift; - v = a | b; - if (DEBUG) fprintf (stderr, "concat %lx (&%lx) %lx (&%lx) <%d = %lx .. ", - a, ma, b, mb, p->eqs[i].Concat.shift, v); - break; - case C_SLICE: - a = m->var_values[p->eqs[i].Slice.source]; - ma = 1; - mb = 0; - for (j = 0; j <= p->eqs[i].Slice.end; j++) { - if (j >= p->eqs[i].Slice.begin) mb |= ma; - ma <<= 1; - } - v = (a & mb) >> p->eqs[i].Slice.begin; - if (DEBUG) fprintf(stderr, "slice %d-%d m=%lx %lx->%lx .. ", - p->eqs[i].Slice.begin, - p->eqs[i].Slice.end, - mb, a, v); - break; - case C_SELECT: - a = m->var_values[p->eqs[i].Select.source]; - v = (a >> p->eqs[i].Select.i) & 1; - if (DEBUG) fprintf(stderr, "select %d %lx->%lx .. ", - p->eqs[i].Select.i, a, v); - break; - case C_READRAM: - a = m->var_values[p->eqs[i].ReadRAM.source]; - v = m->ram_data[p->eqs[i].ReadRAM.ram_id][a]; - if (DEBUG) fprintf(stderr, "Read ram %lx = %lx\n", a, v); - } - m->var_values[p->eqs[i].dest_var] = v & (p->vars[p->eqs[i].dest_var].mask); - if (DEBUG) fprintf(stderr, "%s &%lx : %lx\n", - p->vars[p->eqs[i].dest_var].name, - p->vars[p->eqs[i].dest_var].mask, - m->var_values[p->eqs[i].dest_var]); - } - - // SAVE REGISTERS && MEMORY - for (i = 0; i < p->n_regs; i++) { - m->reg_data[i] = m->var_values[p->regs[i].source]; - if (DEBUG) fprintf(stderr, "reg %s <- %s : %lx\n", - p->vars[p->regs[i].dest].name, - p->vars[p->regs[i].source].name, - m->reg_data[i]); - } - for (i = 0; i < p->n_rams; i++) { - e = m->var_values[p->rams[i].write_enable]; - if (e != 0) { - a = m->var_values[p->rams[i].write_addr]; - d = m->var_values[p->rams[i].data]; - m->ram_data[i][a] = d; - if (DEBUG) fprintf(stderr, "Write ram %lx = %lx\n", a, d); - } - } + int i, j; + t_value a, b, c, d, e, ma, mb, v; + t_program *p = m->prog; + + // READ REGISTERS && MEMORY + for (i = 0; i < p->n_regs; i++) { + m->var_values[p->regs[i].dest] = m->reg_data[i]; + if (DEBUG) fprintf(stderr, "%s <- reg %s : %lx\n", + p->vars[p->regs[i].dest].name, + p->vars[p->regs[i].dest].name, + m->reg_data[i]); + } + + // DO THE LOGIC + for (i = 0; i < p->n_eqs; i++) { + v = 0; + switch (p->eqs[i].type) { + case C_COPY: + v = m->var_values[p->eqs[i].Copy.a]; + break; + case C_NOT: + v = ~m->var_values[p->eqs[i].Not.a]; + break; + case C_BINOP: + a = m->var_values[p->eqs[i].Binop.a]; + b = m->var_values[p->eqs[i].Binop.b]; + if (p->eqs[i].Binop.op == OP_OR) v = a | b; + if (p->eqs[i].Binop.op == OP_AND) v = a & b; + if (p->eqs[i].Binop.op == OP_XOR) v = a ^ b; + if (p->eqs[i].Binop.op == OP_NAND) v = ~(a & b); + break; + case C_MUX: + a = m->var_values[p->eqs[i].Mux.a]; + b = m->var_values[p->eqs[i].Mux.b]; + c = m->var_values[p->eqs[i].Mux.c]; + ma = m->prog->vars[p->eqs[i].Mux.a].mask; + if (ma == 1) { + v = (a ? c : b); + } else { + v = (a & c) | (~a & b); + } + break; + case C_ROM: + if (p->eqs[i].Rom.rom != NULL) { + a = m->var_values[p->eqs[i].Rom.read_addr]; + v = p->eqs[i].Rom.rom->data[a]; + } else { + v = 0; + } + break; + case C_CONCAT: + a = m->var_values[p->eqs[i].Concat.a]; + b = m->var_values[p->eqs[i].Concat.b]; + ma = p->vars[p->eqs[i].Concat.a].mask; + mb = p->vars[p->eqs[i].Concat.b].mask; + b <<= p->eqs[i].Concat.shift; + v = a | b; + if (DEBUG) fprintf (stderr, "concat %lx (&%lx) %lx (&%lx) <%d = %lx .. ", + a, ma, b, mb, p->eqs[i].Concat.shift, v); + break; + case C_SLICE: + a = m->var_values[p->eqs[i].Slice.source]; + ma = 1; + mb = 0; + for (j = 0; j <= p->eqs[i].Slice.end; j++) { + if (j >= p->eqs[i].Slice.begin) mb |= ma; + ma <<= 1; + } + v = (a & mb) >> p->eqs[i].Slice.begin; + if (DEBUG) fprintf(stderr, "slice %d-%d m=%lx %lx->%lx .. ", + p->eqs[i].Slice.begin, + p->eqs[i].Slice.end, + mb, a, v); + break; + case C_SELECT: + a = m->var_values[p->eqs[i].Select.source]; + v = (a >> p->eqs[i].Select.i) & 1; + if (DEBUG) fprintf(stderr, "select %d %lx->%lx .. ", + p->eqs[i].Select.i, a, v); + break; + case C_READRAM: + a = m->var_values[p->eqs[i].ReadRAM.source]; + v = m->ram_data[p->eqs[i].ReadRAM.ram_id][a]; + if (DEBUG) fprintf(stderr, "Read ram %lx = %lx\n", a, v); + } + m->var_values[p->eqs[i].dest_var] = v & (p->vars[p->eqs[i].dest_var].mask); + if (DEBUG) fprintf(stderr, "%s &%lx : %lx\n", + p->vars[p->eqs[i].dest_var].name, + p->vars[p->eqs[i].dest_var].mask, + m->var_values[p->eqs[i].dest_var]); + } + + // SAVE REGISTERS && MEMORY + for (i = 0; i < p->n_regs; i++) { + m->reg_data[i] = m->var_values[p->regs[i].source]; + if (DEBUG) fprintf(stderr, "reg %s <- %s : %lx\n", + p->vars[p->regs[i].dest].name, + p->vars[p->regs[i].source].name, + m->reg_data[i]); + } + for (i = 0; i < p->n_rams; i++) { + e = m->var_values[p->rams[i].write_enable]; + if (e != 0) { + a = m->var_values[p->rams[i].write_addr]; + d = m->var_values[p->rams[i].data]; + m->ram_data[i][a] = d; + if (DEBUG) fprintf(stderr, "Write ram %lx = %lx\n", a, d); + } + } } void write_outputs(t_machine *m, FILE *stream) { - /* FORMAT : - For each output value, a line in the form - var_name binary_value decimal_value - */ - int i; - t_id var; - t_value v, mask; - t_program *p = m->prog; - - for (i = 0; i < p->n_outputs; i++) { - var = p->outputs[i]; - fprintf(stream, "%s\t", p->vars[var].name); - v = m->var_values[var]; - mask = p->vars[var].mask; - while (mask > 0) { - fprintf(stream, "%d", v & 1); - v >>= 1; - mask >>= 1; - } - fprintf(stream, "\t%ld\n", m->var_values[var]); - } - fprintf(stream, "\n"); + /* FORMAT : + For each output value, a line in the form + var_name binary_value decimal_value + */ + int i; + t_id var; + t_value v, mask; + t_program *p = m->prog; + + for (i = 0; i < p->n_outputs; i++) { + var = p->outputs[i]; + fprintf(stream, "%s\t", p->vars[var].name); + v = m->var_values[var]; + mask = p->vars[var].mask; + while (mask > 0) { + fprintf(stream, "%d", v & 1); + v >>= 1; + mask >>= 1; + } + fprintf(stream, "\t%ld\n", m->var_values[var]); + } + fprintf(stream, "\n"); } @@ -26,93 +26,93 @@ typedef unsigned long long int t_value; typedef struct _s_rom { - int addr_size, word_size; - t_value *data; - const char *prefix; - struct _s_rom *next; + int addr_size, word_size; + t_value *data; + const char *prefix; + struct _s_rom *next; } t_rom; // Identifier for the variables of the circuit. typedef int t_id; -typedef struct { // a variable in the simulator - t_value mask; - int size; - char *name; +typedef struct { // a variable in the simulator + t_value mask; + int size; + char *name; } t_variable; typedef struct { - t_id dest, source; + t_id dest, source; } t_reg; typedef struct { - int addr_size, word_size; - t_id write_enable, write_addr, data; + int addr_size, word_size; + t_id write_enable, write_addr, data; } t_ram; typedef struct { - int type; - t_id dest_var; - union { - struct { - t_id a; - } Copy; - struct { - t_id a; - } Not; - struct { - int op; - t_id a, b; - } Binop; - struct { - t_id a, b, c; - } Mux; - struct { - t_rom *rom; - t_id read_addr; - } Rom; - struct { - t_id a, b; - int shift; - } Concat; - struct { - int begin, end; - t_id source; - } Slice; - struct { - int i; - t_id source; - } Select; - struct { - int ram_id; - t_id source; - } ReadRAM; - }; + int type; + t_id dest_var; + union { + struct { + t_id a; + } Copy; + struct { + t_id a; + } Not; + struct { + int op; + t_id a, b; + } Binop; + struct { + t_id a, b, c; + } Mux; + struct { + t_rom *rom; + t_id read_addr; + } Rom; + struct { + t_id a, b; + int shift; + } Concat; + struct { + int begin, end; + t_id source; + } Slice; + struct { + int i; + t_id source; + } Select; + struct { + int ram_id; + t_id source; + } ReadRAM; + }; } t_equation; typedef struct { - int n_vars, n_inputs, n_outputs; - - t_variable *vars; - t_id *inputs, *outputs; + int n_vars, n_inputs, n_outputs; + + t_variable *vars; + t_id *inputs, *outputs; - int n_regs, n_rams; - t_reg *regs; - t_ram *rams; + int n_regs, n_rams; + t_reg *regs; + t_ram *rams; - int n_eqs; - t_equation *eqs; + int n_eqs; + t_equation *eqs; } t_program; // machine = execution instance typedef struct { - t_program *prog; - t_value *var_values; // indexed by variable ID + t_program *prog; + t_value *var_values; // indexed by variable ID - t_value *reg_data; // indexed by number in register list - t_value **ram_data; // indexed by number in ram list + t_value *reg_data; // indexed by number in register list + t_value **ram_data; // indexed by number in ram list } t_machine; diff --git a/csim/util.c b/csim/util.c index c815e8e..ac8bdc3 100644 --- a/csim/util.c +++ b/csim/util.c @@ -1,45 +1,45 @@ /* - Système Digital - 2013-2014 - Alex AUVOLAT + Système Digital + 2013-2014 + Alex AUVOLAT - util.c Various utility functions used elsewhere + util.c Various utility functions used elsewhere */ #include "sim.h" int pow2(int exp) { - return (1 << exp); + return (1 << exp); } t_value read_bool(FILE *stream, t_value *mask) { - t_value r = 0; - t_value pow = 1; + t_value r = 0; + t_value pow = 1; - char c; - if (mask != NULL) *mask = 0; + char c; + if (mask != NULL) *mask = 0; - for(;;) { - fscanf(stream, "%c", &c); - if (c == '1') { - r |= pow; - } else if (c != '0') { - break; - } - if (mask != NULL) (*mask) |= pow; + for(;;) { + fscanf(stream, "%c", &c); + if (c == '1') { + r |= pow; + } else if (c != '0') { + break; + } + if (mask != NULL) (*mask) |= pow; - pow *= 2; - } + pow *= 2; + } - return r; + return r; } int is_prefix(const char *prefix, const char *str) { - while (*prefix) { - if (*prefix != *str) return 0; - prefix++; - str++; - } - return 1; + while (*prefix) { + if (*prefix != *str) return 0; + prefix++; + str++; + } + return 1; } diff --git a/sched/graph.ml b/sched/graph.ml index 08762a1..d5f34a9 100644 --- a/sched/graph.ml +++ b/sched/graph.ml @@ -32,29 +32,29 @@ 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 + 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 + 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/main.ml b/sched/main.ml index c8ea58e..326a2bd 100644 --- a/sched/main.ml +++ b/sched/main.ml @@ -7,14 +7,14 @@ let compile filename = try let p = Netlist.read_file filename in let out_name = (Filename.chop_suffix filename ".net") ^ ".snet" in - let dumb_out_name = (Filename.chop_suffix filename ".net") ^ ".dumb" in + let dumb_out_name = (Filename.chop_suffix filename ".net") ^ ".dumb" in let out_opt_name = (Filename.chop_suffix filename ".net") ^ "_opt.snet" in - let dumb_opt_out_name = (Filename.chop_suffix filename ".net") ^ "_opt.dumb" in - let q, q_opt = ref p, ref p in + let dumb_opt_out_name = (Filename.chop_suffix filename ".net") ^ "_opt.dumb" in + let q, q_opt = ref p, ref p in begin try - q := Scheduler.schedule p; - q_opt := Simplify.simplify p + q := Scheduler.schedule p; + q_opt := Simplify.simplify p with | Scheduler.Combinational_cycle -> Format.eprintf "The netlist has a combinatory cycle.@."; @@ -23,24 +23,24 @@ let compile filename = 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_dumb.print_program dumb_out !q; - close_out dumb_out; + close_out out; + let dumb_out = open_out dumb_out_name in + Netlist_dumb.print_program dumb_out !q; + close_out dumb_out; - let out_opt = open_out out_opt_name in - Netlist_printer.print_program out_opt !q_opt; - close_out out_opt; - let dumb_opt_out = open_out dumb_opt_out_name in - Netlist_dumb.print_program dumb_opt_out !q_opt; - close_out dumb_opt_out; + let out_opt = open_out out_opt_name in + Netlist_printer.print_program out_opt !q_opt; + close_out out_opt; + let dumb_opt_out = open_out dumb_opt_out_name in + Netlist_dumb.print_program dumb_opt_out !q_opt; + close_out dumb_opt_out; if !simulate then ( let simulator = if !number_steps = -1 then - !sim_path + !sim_path else - !sim_path ^ " -n " ^ (string_of_int !number_steps) + !sim_path ^ " -n " ^ (string_of_int !number_steps) in ignore (Unix.system (simulator^" "^(if !dumb_down then dumb_out_name else out_name))) ) @@ -50,8 +50,8 @@ let compile filename = 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)"; + "-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 "" diff --git a/sched/netlist_dumb.ml b/sched/netlist_dumb.ml index 01c187b..646787e 100644 --- a/sched/netlist_dumb.ml +++ b/sched/netlist_dumb.ml @@ -1,5 +1,5 @@ (* PRINTER FOR DUMBED-DOWN NETLIST - (the format used by the C simulator) + (the format used by the C simulator) *) open Netlist_ast @@ -8,165 +8,165 @@ open Format (* Alternative program AST format, better corresponding to the dumb syntax *) type var_def = { - name : string; - size : int } + name : string; + size : int } type var_id = int type const_val = bool array (* keep type binop from netlist_ast *) type reg_var = { reg_dest : var_id; source : var_id } type ram_var = { ram_id : int; - addr_size : int; word_size : int; - write_enable : var_id; - write_addr : var_id; data : var_id } + addr_size : int; word_size : int; + write_enable : var_id; + write_addr : var_id; data : var_id } type dumb_exp = - | Dcopy of var_id (* copy a variable - these cannot be eliminated totally *) - | Dnot of var_id - | Dbinop of binop * var_id * var_id - | Dmux of var_id * var_id * var_id - | Drom of int * int * var_id - | Dconcat of var_id * var_id - | Dslice of int * int * var_id - | Dselect of int * var_id - | Dreadram of int * var_id + | Dcopy of var_id (* copy a variable - these cannot be eliminated totally *) + | Dnot of var_id + | Dbinop of binop * var_id * var_id + | Dmux of var_id * var_id * var_id + | Drom of int * int * var_id + | Dconcat of var_id * var_id + | Dslice of int * int * var_id + | Dselect of int * var_id + | Dreadram of int * var_id type dumb_equation = var_id * dumb_exp type dumb_program = { - d_vars : var_def list; - d_inputs : var_id list; - d_outputs : var_id list; - d_regs : reg_var list; - d_rams : ram_var list; - d_eqs : dumb_equation list } + d_vars : var_def list; + d_inputs : var_id list; + d_outputs : var_id list; + d_regs : reg_var list; + d_rams : ram_var list; + d_eqs : dumb_equation list } -(* Convert a program to a dumb program *) +(* Convert a program to a dumb program *) let mkbinstr a = - let r = String.make (Array.length a) '0' in - for i = 0 to Array.length a - 1 do - if a.(i) then r.[i] <- '1' - done; - r + let r = String.make (Array.length a) '0' in + for i = 0 to Array.length a - 1 do + if a.(i) then r.[i] <- '1' + done; + r let const_info a = - "$" ^ (mkbinstr a), Array.length a, a + "$" ^ (mkbinstr a), Array.length a, a let make_program_dumb p = - (* - 1. Identify constants and create new variables for them, - put them on the variable list - 2. Create map from variable identifier to variable ID, - add them to variable list - 3. Extract regs and rams into separate list - 4. Reformat equation list (replace constants by the - coresponding constant variables) - 5. Done. - *) - let next_id = ref 0 in - let vars = ref [] in - let var_map = Hashtbl.create (Env.cardinal p.p_vars) in - - (* Extract constants *) - List.iter - (fun (_, eq) -> - let add = function - | Aconst(k) -> - let id, sz, v = const_info k in - if not (Hashtbl.mem var_map id) then begin - vars := { name= id; size= sz }::(!vars); - Hashtbl.add var_map id (!next_id); - next_id := !next_id + 1 - end - | _ -> () - in match eq with - | Earg(a) -> add a - | Enot(a) -> add a - | Ebinop(_, a, b) -> add a; add b - | Emux(a, b, c) -> add a; add b; add c - | Erom(_, _, a) -> add a - | Eram(_, _, a, b, c, d) -> add a; add b; add c; add d - | Econcat(a, b) -> add a; add b - | Eslice(_, _, a) -> add a - | Eselect(_, a) ->add a - | _ -> ()) - p.p_eqs; - - (* Make ids for variables *) - let add_var n = - if not (Hashtbl.mem var_map n) then begin - vars := { name = n; size = Env.find n p.p_vars }::(!vars); - Hashtbl.add var_map n (!next_id); - next_id := !next_id + 1 - end - in - List.iter add_var p.p_inputs; - List.iter (fun (n, _) -> add_var n) p.p_eqs; - Env.iter (fun n _ -> add_var n) p.p_vars; - - let var_id = Hashtbl.find var_map in - let arg_id = function - | Avar(x) -> var_id x - | Aconst(x) -> - let n, _, _ = const_info x in var_id n - in - - (* Extract registers *) - let regs, eq2 = List.fold_left - (fun (regs, eqs) (n, eq) -> - match eq with - | Ereg(x) -> - { - reg_dest = var_id n; - source = var_id x; - }::regs, eqs - | _ -> regs, (n, eq)::eqs) - ([],[]) - p.p_eqs in - (* Extract rams, replace arguments by variable id's *) - let ram_id = ref 0 in - let rams, eq3 = List.fold_left - (fun (rams, eqs) (n, eq) -> - let ram2 = ref None in - let eq2 = match eq with - | Eram(asz, wsz, ra, we, wa, d) -> - ram_id := !ram_id + 1; - ram2 := Some({ - ram_id = !ram_id - 1; - addr_size = asz; - word_size = wsz; - write_enable = arg_id we; - write_addr = arg_id wa; - data = arg_id d; - }); - Dreadram(!ram_id - 1, arg_id ra) - | Earg(a) -> Dcopy(arg_id a) - | Enot(a) -> Dnot(arg_id a) - | Ebinop(o, a, b) -> Dbinop(o, arg_id a, arg_id b) - | Emux(a, b, c) -> Dmux(arg_id a, arg_id b, arg_id c) - | Erom(u, v, a) -> Drom(u, v, arg_id a) - | Econcat(a, b) -> Dconcat(arg_id a, arg_id b) - | Eslice(u, v, a) -> Dslice(u, v, arg_id a) - | Eselect(i, a) -> Dselect(i, arg_id a) - | _ -> failwith "This should not happen." - in - (match !ram2 with | None -> rams | Some k -> k::rams), - (var_id n, eq2)::eqs - ) - ([],[]) - eq2 in - - (* Replace arguments by variable id's *) - { - d_vars = List.rev (!vars); - d_inputs = List.map var_id p.p_inputs; - d_outputs = List.map var_id p.p_outputs; - d_regs = regs; - d_rams = List.rev rams; - d_eqs = eq3; - } - + (* + 1. Identify constants and create new variables for them, + put them on the variable list + 2. Create map from variable identifier to variable ID, + add them to variable list + 3. Extract regs and rams into separate list + 4. Reformat equation list (replace constants by the + coresponding constant variables) + 5. Done. + *) + let next_id = ref 0 in + let vars = ref [] in + let var_map = Hashtbl.create (Env.cardinal p.p_vars) in + + (* Extract constants *) + List.iter + (fun (_, eq) -> + let add = function + | Aconst(k) -> + let id, sz, v = const_info k in + if not (Hashtbl.mem var_map id) then begin + vars := { name= id; size= sz }::(!vars); + Hashtbl.add var_map id (!next_id); + next_id := !next_id + 1 + end + | _ -> () + in match eq with + | Earg(a) -> add a + | Enot(a) -> add a + | Ebinop(_, a, b) -> add a; add b + | Emux(a, b, c) -> add a; add b; add c + | Erom(_, _, a) -> add a + | Eram(_, _, a, b, c, d) -> add a; add b; add c; add d + | Econcat(a, b) -> add a; add b + | Eslice(_, _, a) -> add a + | Eselect(_, a) ->add a + | _ -> ()) + p.p_eqs; + + (* Make ids for variables *) + let add_var n = + if not (Hashtbl.mem var_map n) then begin + vars := { name = n; size = Env.find n p.p_vars }::(!vars); + Hashtbl.add var_map n (!next_id); + next_id := !next_id + 1 + end + in + List.iter add_var p.p_inputs; + List.iter (fun (n, _) -> add_var n) p.p_eqs; + Env.iter (fun n _ -> add_var n) p.p_vars; + + let var_id = Hashtbl.find var_map in + let arg_id = function + | Avar(x) -> var_id x + | Aconst(x) -> + let n, _, _ = const_info x in var_id n + in + + (* Extract registers *) + let regs, eq2 = List.fold_left + (fun (regs, eqs) (n, eq) -> + match eq with + | Ereg(x) -> + { + reg_dest = var_id n; + source = var_id x; + }::regs, eqs + | _ -> regs, (n, eq)::eqs) + ([],[]) + p.p_eqs in + (* Extract rams, replace arguments by variable id's *) + let ram_id = ref 0 in + let rams, eq3 = List.fold_left + (fun (rams, eqs) (n, eq) -> + let ram2 = ref None in + let eq2 = match eq with + | Eram(asz, wsz, ra, we, wa, d) -> + ram_id := !ram_id + 1; + ram2 := Some({ + ram_id = !ram_id - 1; + addr_size = asz; + word_size = wsz; + write_enable = arg_id we; + write_addr = arg_id wa; + data = arg_id d; + }); + Dreadram(!ram_id - 1, arg_id ra) + | Earg(a) -> Dcopy(arg_id a) + | Enot(a) -> Dnot(arg_id a) + | Ebinop(o, a, b) -> Dbinop(o, arg_id a, arg_id b) + | Emux(a, b, c) -> Dmux(arg_id a, arg_id b, arg_id c) + | Erom(u, v, a) -> Drom(u, v, arg_id a) + | Econcat(a, b) -> Dconcat(arg_id a, arg_id b) + | Eslice(u, v, a) -> Dslice(u, v, arg_id a) + | Eselect(i, a) -> Dselect(i, arg_id a) + | _ -> failwith "This should not happen." + in + (match !ram2 with | None -> rams | Some k -> k::rams), + (var_id n, eq2)::eqs + ) + ([],[]) + eq2 in + + (* Replace arguments by variable id's *) + { + d_vars = List.rev (!vars); + d_inputs = List.map var_id p.p_inputs; + d_outputs = List.map var_id p.p_outputs; + d_regs = regs; + d_rams = List.rev rams; + d_eqs = eq3; + } + (* Printer code *) @@ -182,53 +182,53 @@ let c_select = 7 let c_readram = 8 let binop_id = function - | Or -> 0 - | Xor -> 1 - | And -> 2 - | Nand -> 3 + | Or -> 0 + | Xor -> 1 + | And -> 2 + | Nand -> 3 let print_dumb_program oc p = - let ff = formatter_of_out_channel oc in - (* print variable list *) - fprintf ff "%d\n" (List.length p.d_vars); - List.iter - (fun v -> - fprintf ff "%d %s\n" v.size v.name) - p.d_vars; - (* print input list *) - fprintf ff "%d" (List.length p.d_inputs); - List.iter (fun k -> fprintf ff " %d" k) p.d_inputs; - fprintf ff "\n"; - (* print output list *) - fprintf ff "%d" (List.length p.d_outputs); - List.iter (fun k -> fprintf ff " %d" k) p.d_outputs; - fprintf ff "\n"; - (* print register list *) - fprintf ff "%d\n" (List.length p.d_regs); - List.iter (fun (r: reg_var) -> - fprintf ff "%d %d\n" r.reg_dest r.source) p.d_regs; - (* print ram list *) - fprintf ff "%d\n" (List.length p.d_rams); - List.iter (fun r -> fprintf ff "%d %d %d %d %d\n" - r.addr_size r.word_size r.write_enable - r.write_addr r.data) p.d_rams; - (* print equation list *) - fprintf ff "%d\n" (List.length p.d_eqs); - List.iter (fun (n, e) -> - fprintf ff "%d " n; match e with - | Dcopy(x) -> fprintf ff "%d %d\n" c_copy x - | Dnot(x) -> fprintf ff "%d %d\n" c_not x - | Dbinop(o, a, b) -> fprintf ff "%d %d %d %d\n" c_binop (binop_id o) a b - | Dmux(a, b, c) -> fprintf ff "%d %d %d %d\n" c_mux a b c - | Drom(u, v, a) -> fprintf ff "%d %d %d %d\n" c_rom u v a - | Dconcat(a, b) -> fprintf ff "%d %d %d\n" c_concat a b - | Dslice(u, v, a) -> fprintf ff "%d %d %d %d\n" c_slice u v a - | Dselect(i, a) -> fprintf ff "%d %d %d\n" c_select i a - | Dreadram(i, k) -> fprintf ff "%d %d %d\n" c_readram i k) - p.d_eqs; - (*flush*) - fprintf ff "@." + let ff = formatter_of_out_channel oc in + (* print variable list *) + fprintf ff "%d\n" (List.length p.d_vars); + List.iter + (fun v -> + fprintf ff "%d %s\n" v.size v.name) + p.d_vars; + (* print input list *) + fprintf ff "%d" (List.length p.d_inputs); + List.iter (fun k -> fprintf ff " %d" k) p.d_inputs; + fprintf ff "\n"; + (* print output list *) + fprintf ff "%d" (List.length p.d_outputs); + List.iter (fun k -> fprintf ff " %d" k) p.d_outputs; + fprintf ff "\n"; + (* print register list *) + fprintf ff "%d\n" (List.length p.d_regs); + List.iter (fun (r: reg_var) -> + fprintf ff "%d %d\n" r.reg_dest r.source) p.d_regs; + (* print ram list *) + fprintf ff "%d\n" (List.length p.d_rams); + List.iter (fun r -> fprintf ff "%d %d %d %d %d\n" + r.addr_size r.word_size r.write_enable + r.write_addr r.data) p.d_rams; + (* print equation list *) + fprintf ff "%d\n" (List.length p.d_eqs); + List.iter (fun (n, e) -> + fprintf ff "%d " n; match e with + | Dcopy(x) -> fprintf ff "%d %d\n" c_copy x + | Dnot(x) -> fprintf ff "%d %d\n" c_not x + | Dbinop(o, a, b) -> fprintf ff "%d %d %d %d\n" c_binop (binop_id o) a b + | Dmux(a, b, c) -> fprintf ff "%d %d %d %d\n" c_mux a b c + | Drom(u, v, a) -> fprintf ff "%d %d %d %d\n" c_rom u v a + | Dconcat(a, b) -> fprintf ff "%d %d %d\n" c_concat a b + | Dslice(u, v, a) -> fprintf ff "%d %d %d %d\n" c_slice u v a + | Dselect(i, a) -> fprintf ff "%d %d %d\n" c_select i a + | Dreadram(i, k) -> fprintf ff "%d %d %d\n" c_readram i k) + p.d_eqs; + (*flush*) + fprintf ff "@." let print_program oc p = - print_dumb_program oc (make_program_dumb p) + print_dumb_program oc (make_program_dumb p) diff --git a/sched/scheduler.ml b/sched/scheduler.ml index d079f64..611aab4 100644 --- a/sched/scheduler.ml +++ b/sched/scheduler.ml @@ -5,80 +5,80 @@ 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 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 read_exp_all 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) -> [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) -> add_arg a (add_arg b (add_arg c (add_arg d []))) - | Econcat(u, v) -> add_arg u (add_arg v []) - | Eslice(_, _, a) -> add_arg a [] - | Eselect(_, a) -> add_arg a [] - in - aux 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) -> [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) -> add_arg a (add_arg b (add_arg c (add_arg d []))) + | Econcat(u, v) -> add_arg u (add_arg v []) + | Eslice(_, _, a) -> add_arg a [] + | Eselect(_, a) -> add_arg a [] + in + aux eq let prog_eq_map p = - List.fold_left - (fun x (vn, eqn) -> Smap.add vn eqn x) - Smap.empty p.p_eqs + List.fold_left + (fun x (vn, eqn) -> Smap.add vn eqn x) + Smap.empty p.p_eqs let prog_graph p eq_map = - let graph = Graph.mk_graph() 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; - graph + let graph = Graph.mk_graph() 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; + graph let schedule p = - let eq_map = prog_eq_map p in - let graph = prog_graph p eq_map in + let eq_map = prog_eq_map p in + let graph = prog_graph p eq_map in - (* 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; - } + (* 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/simplify.ml b/sched/simplify.ml index c47a9d0..37e4539 100644 --- a/sched/simplify.ml +++ b/sched/simplify.ml @@ -1,17 +1,17 @@ (* SIMPLIFICATION PASSES *) (* - Order of simplifications : - - cascade slices and selects - - transform k = SLICE i j var when var = CONCAT var' var'' - - simplify stupid things (a xor 0 = a, a and 0 = 0, etc.) - transform k = SLICE i i var into k = SELECT i var - - transform k = SELECT 0 var into k = var when var is also one bit - - look for variables with same equation, put the second to identity - - eliminate k' for each equation k' = k - - topological sort + Order of simplifications : + - cascade slices and selects + - transform k = SLICE i j var when var = CONCAT var' var'' + - simplify stupid things (a xor 0 = a, a and 0 = 0, etc.) + transform k = SLICE i i var into k = SELECT i var + - transform k = SELECT 0 var into k = var when var is also one bit + - look for variables with same equation, put the second to identity + - eliminate k' for each equation k' = k + - topological sort - TODO : eliminate unused variables. problem : they are hard to identify + TODO : eliminate unused variables. problem : they are hard to identify *) open Netlist_ast @@ -21,321 +21,321 @@ module Smap = Map.Make(String) (* Simplify cascade slicing/selecting *) let cascade_slices p = - let usefull = ref false in - let slices = Hashtbl.create 42 in - let eqs_new = List.map - (fun (n, eq) -> (n, match eq with - | Eslice(u, v, Avar(x)) -> - let dec, nx = - if Hashtbl.mem slices x then begin - Hashtbl.find slices x - end else - (0, x) - in - Hashtbl.add slices n (u + dec, nx); - if nx <> x || dec <> 0 then usefull := true; - Eslice(u + dec, v + dec, Avar(nx)) - | Eselect(u, Avar(x)) -> - begin try - let ku, kx = Hashtbl.find slices x in - usefull := true; - Eselect(ku + u, Avar(kx)) - with - Not_found -> Eselect(u, Avar(x)) - end - | _ -> eq)) - p.p_eqs in - { - p_eqs = eqs_new; - p_inputs = p.p_inputs; - p_outputs = p.p_outputs; - p_vars = p.p_vars; - }, !usefull + let usefull = ref false in + let slices = Hashtbl.create 42 in + let eqs_new = List.map + (fun (n, eq) -> (n, match eq with + | Eslice(u, v, Avar(x)) -> + let dec, nx = + if Hashtbl.mem slices x then begin + Hashtbl.find slices x + end else + (0, x) + in + Hashtbl.add slices n (u + dec, nx); + if nx <> x || dec <> 0 then usefull := true; + Eslice(u + dec, v + dec, Avar(nx)) + | Eselect(u, Avar(x)) -> + begin try + let ku, kx = Hashtbl.find slices x in + usefull := true; + Eselect(ku + u, Avar(kx)) + with + Not_found -> Eselect(u, Avar(x)) + end + | _ -> eq)) + p.p_eqs in + { + p_eqs = eqs_new; + p_inputs = p.p_inputs; + p_outputs = p.p_outputs; + p_vars = p.p_vars; + }, !usefull (* If - var = CONCAT a b - x = SLICE i j var - or - y = SELECT i var - then x or y may be simplified + var = CONCAT a b + x = SLICE i j var + or + y = SELECT i var + then x or y may be simplified *) let pass_concat p = - let usefull = ref false in - let concats = Hashtbl.create 42 in - List.iter (fun (n, eq) -> match eq with - | Econcat(x, y) -> - let s1 = match x with - | Aconst(a) -> Array.length a - | Avar(z) -> Env.find z p.p_vars - in let s2 = match y with - | Aconst(a) -> Array.length a - | Avar(z) -> Env.find z p.p_vars - in - Hashtbl.add concats n (x, s1, y, s2) - | _ -> ()) p.p_eqs; - let eqs_new = List.map - (fun (n, eq) -> (n, match eq with - | Eselect(i, Avar(n)) -> - begin try - let (x, s1, y, s2) = Hashtbl.find concats n in - usefull := true; - if i < s1 then - Eselect(i, x) - else - Eselect(i-s1, y) - with Not_found -> eq end - | Eslice(i, j, Avar(n)) -> - begin try - let (x, s1, y, s2) = Hashtbl.find concats n in - if j < s1 then begin - usefull := true; - Eslice(i, j, x) - end else if i >= s1 then begin - usefull := true; - Eslice(i - s1, j - s1, y) - end else eq - with Not_found -> eq end - | _ -> eq)) - p.p_eqs in - { - p_eqs = eqs_new; - p_inputs = p.p_inputs; - p_outputs = p.p_outputs; - p_vars = p.p_vars; - }, !usefull - + let usefull = ref false in + let concats = Hashtbl.create 42 in + List.iter (fun (n, eq) -> match eq with + | Econcat(x, y) -> + let s1 = match x with + | Aconst(a) -> Array.length a + | Avar(z) -> Env.find z p.p_vars + in let s2 = match y with + | Aconst(a) -> Array.length a + | Avar(z) -> Env.find z p.p_vars + in + Hashtbl.add concats n (x, s1, y, s2) + | _ -> ()) p.p_eqs; + let eqs_new = List.map + (fun (n, eq) -> (n, match eq with + | Eselect(i, Avar(n)) -> + begin try + let (x, s1, y, s2) = Hashtbl.find concats n in + usefull := true; + if i < s1 then + Eselect(i, x) + else + Eselect(i-s1, y) + with Not_found -> eq end + | Eslice(i, j, Avar(n)) -> + begin try + let (x, s1, y, s2) = Hashtbl.find concats n in + if j < s1 then begin + usefull := true; + Eslice(i, j, x) + end else if i >= s1 then begin + usefull := true; + Eslice(i - s1, j - s1, y) + end else eq + with Not_found -> eq end + | _ -> eq)) + p.p_eqs in + { + p_eqs = eqs_new; + p_inputs = p.p_inputs; + p_outputs = p.p_outputs; + p_vars = p.p_vars; + }, !usefull + (* Simplifies some trivial arithmetic possibilites : - a and 1 = a - a and 0 = 0 - a or 1 = 1 - a or 0 = a - a xor 0 = a - slice i i x = select i x - concat const const = const.const - slice i j const = const.[i..j] - select i const = const.[i] + a and 1 = a + a and 0 = 0 + a or 1 = 1 + a or 0 = a + a xor 0 = a + slice i i x = select i x + concat const const = const.const + slice i j const = const.[i..j] + select i const = const.[i] *) let arith_simplify p = - let usefull = ref false in - { - p_eqs = List.map - (fun (n, eq) -> - let useless = ref false in - let neq = match eq with - | Ebinop(Or, Aconst([|false|]), x) -> Earg(x) - | Ebinop(Or, Aconst([|true|]), x) -> Earg(Aconst([|true|])) - | Ebinop(Or, x, Aconst([|false|])) -> Earg(x) - | Ebinop(Or, x, Aconst([|true|])) -> Earg(Aconst([|true|])) + let usefull = ref false in + { + p_eqs = List.map + (fun (n, eq) -> + let useless = ref false in + let neq = match eq with + | Ebinop(Or, Aconst([|false|]), x) -> Earg(x) + | Ebinop(Or, Aconst([|true|]), x) -> Earg(Aconst([|true|])) + | Ebinop(Or, x, Aconst([|false|])) -> Earg(x) + | Ebinop(Or, x, Aconst([|true|])) -> Earg(Aconst([|true|])) - | Ebinop(And, Aconst([|false|]), x) -> Earg(Aconst([|false|])) - | Ebinop(And, Aconst([|true|]), x) -> Earg(x) - | Ebinop(And, x, Aconst([|false|])) -> Earg(Aconst([|false|])) - | Ebinop(And, x, Aconst([|true|])) -> Earg(x) + | Ebinop(And, Aconst([|false|]), x) -> Earg(Aconst([|false|])) + | Ebinop(And, Aconst([|true|]), x) -> Earg(x) + | Ebinop(And, x, Aconst([|false|])) -> Earg(Aconst([|false|])) + | Ebinop(And, x, Aconst([|true|])) -> Earg(x) - | Ebinop(Xor, Aconst([|false|]), x) -> Earg(x) - | Ebinop(Xor, x, Aconst([|false|])) -> Earg(x) + | Ebinop(Xor, Aconst([|false|]), x) -> Earg(x) + | Ebinop(Xor, x, Aconst([|false|])) -> Earg(x) - | Eslice(i, j, k) when i = j -> Eselect(i, k) + | Eslice(i, j, k) when i = j -> Eselect(i, k) - | Econcat(Aconst(a), Aconst(b)) -> - Earg(Aconst(Array.append a b)) - - | Eslice(i, j, Aconst(a)) -> - Earg(Aconst(Array.sub a i (j - i + 1))) - - | Eselect(i, Aconst(a)) -> - Earg(Aconst([|a.(i)|])) - - | _ -> useless := true; eq in - if not !useless then usefull := true; - (n, neq)) - p.p_eqs; - p_inputs = p.p_inputs; - p_outputs = p.p_outputs; - p_vars = p.p_vars; - }, !usefull + | Econcat(Aconst(a), Aconst(b)) -> + Earg(Aconst(Array.append a b)) + + | Eslice(i, j, Aconst(a)) -> + Earg(Aconst(Array.sub a i (j - i + 1))) + + | Eselect(i, Aconst(a)) -> + Earg(Aconst([|a.(i)|])) + + | _ -> useless := true; eq in + if not !useless then usefull := true; + (n, neq)) + p.p_eqs; + p_inputs = p.p_inputs; + p_outputs = p.p_outputs; + p_vars = p.p_vars; + }, !usefull (* if x is one bit, then : - select 0 x = x + select 0 x = x and same thing with select *) let select_to_id p = - let usefull = ref false in - { - p_eqs = List.map - (fun (n, eq) -> match eq with - | Eselect(0, Avar(id)) when Env.find id p.p_vars = 1 -> - usefull := true; - (n, Earg(Avar(id))) - | Eslice(0, sz, Avar(id)) when Env.find id p.p_vars = sz + 1 -> - usefull := true; - (n, Earg(Avar(id))) - | _ -> (n, eq)) - p.p_eqs; - p_inputs = p.p_inputs; - p_outputs = p.p_outputs; - p_vars = p.p_vars; - }, !usefull + let usefull = ref false in + { + p_eqs = List.map + (fun (n, eq) -> match eq with + | Eselect(0, Avar(id)) when Env.find id p.p_vars = 1 -> + usefull := true; + (n, Earg(Avar(id))) + | Eslice(0, sz, Avar(id)) when Env.find id p.p_vars = sz + 1 -> + usefull := true; + (n, Earg(Avar(id))) + | _ -> (n, eq)) + p.p_eqs; + p_inputs = p.p_inputs; + p_outputs = p.p_outputs; + p_vars = p.p_vars; + }, !usefull (* - If a = eqn(v1, v2, ...) and b = eqn(v1, v2, ...) <- the same equation - then say b = a + If a = eqn(v1, v2, ...) and b = eqn(v1, v2, ...) <- the same equation + then say b = a *) let same_eq_simplify p = - let usefull = ref false in - let id_outputs = - (List.fold_left (fun x k -> Sset.add k x) Sset.empty p.p_outputs) in - let eq_map = Hashtbl.create 42 in - List.iter - (fun (n, eq) -> if Sset.mem n id_outputs then - Hashtbl.add eq_map eq n) - p.p_eqs; - let simplify_eq (n, eq) = - if Sset.mem n id_outputs then - (n, eq) - else if Hashtbl.mem eq_map eq then begin - usefull := true; - (n, Earg(Avar(Hashtbl.find eq_map eq))) - end else begin - Hashtbl.add eq_map eq n; - (n, eq) - end - in - let eq2 = List.map simplify_eq p.p_eqs in - { - p_eqs = eq2; - p_inputs = p.p_inputs; - p_outputs = p.p_outputs; - p_vars = p.p_vars; - }, !usefull + let usefull = ref false in + let id_outputs = + (List.fold_left (fun x k -> Sset.add k x) Sset.empty p.p_outputs) in + let eq_map = Hashtbl.create 42 in + List.iter + (fun (n, eq) -> if Sset.mem n id_outputs then + Hashtbl.add eq_map eq n) + p.p_eqs; + let simplify_eq (n, eq) = + if Sset.mem n id_outputs then + (n, eq) + else if Hashtbl.mem eq_map eq then begin + usefull := true; + (n, Earg(Avar(Hashtbl.find eq_map eq))) + end else begin + Hashtbl.add eq_map eq n; + (n, eq) + end + in + let eq2 = List.map simplify_eq p.p_eqs in + { + p_eqs = eq2; + p_inputs = p.p_inputs; + p_outputs = p.p_outputs; + p_vars = p.p_vars; + }, !usefull -(* Replace one specific variable by another argument in the arguments of all equations - (possibly a constant, possibly another variable) +(* Replace one specific variable by another argument in the arguments of all equations + (possibly a constant, possibly another variable) *) let eliminate_var var rep p = - let rep_arg = function - | Avar(i) when i = var -> rep - | k -> k - in - let rep_eqs = List.map - (fun (n, eq) -> (n, match eq with - | Earg(a) -> Earg(rep_arg a) - | Ereg(i) when i = var -> - begin match rep with - | Avar(j) -> Ereg(j) - | Aconst(k) -> Earg(Aconst(k)) - end - | Ereg(j) -> Ereg(j) - | Enot(a) -> Enot(rep_arg a) - | Ebinop(o, a, b) -> Ebinop(o, rep_arg a, rep_arg b) - | Emux(a, b, c) -> Emux(rep_arg a, rep_arg b, rep_arg c) - | Erom(u, v, a) -> Erom(u, v, rep_arg a) - | Eram(u, v, a, b, c, d) -> Eram(u, v, rep_arg a, rep_arg b, rep_arg c, rep_arg d) - | Econcat(a, b) -> Econcat(rep_arg a, rep_arg b) - | Eslice(u, v, a) -> Eslice(u, v, rep_arg a) - | Eselect(u, a) -> Eselect(u, rep_arg a) - )) - p.p_eqs in - { - p_eqs = List.fold_left - (fun x (n, eq) -> - if n = var then x else (n, eq)::x) - [] rep_eqs; - p_inputs = p.p_inputs; - p_outputs = p.p_outputs; - p_vars = Env.remove var p.p_vars; - } + let rep_arg = function + | Avar(i) when i = var -> rep + | k -> k + in + let rep_eqs = List.map + (fun (n, eq) -> (n, match eq with + | Earg(a) -> Earg(rep_arg a) + | Ereg(i) when i = var -> + begin match rep with + | Avar(j) -> Ereg(j) + | Aconst(k) -> Earg(Aconst(k)) + end + | Ereg(j) -> Ereg(j) + | Enot(a) -> Enot(rep_arg a) + | Ebinop(o, a, b) -> Ebinop(o, rep_arg a, rep_arg b) + | Emux(a, b, c) -> Emux(rep_arg a, rep_arg b, rep_arg c) + | Erom(u, v, a) -> Erom(u, v, rep_arg a) + | Eram(u, v, a, b, c, d) -> Eram(u, v, rep_arg a, rep_arg b, rep_arg c, rep_arg d) + | Econcat(a, b) -> Econcat(rep_arg a, rep_arg b) + | Eslice(u, v, a) -> Eslice(u, v, rep_arg a) + | Eselect(u, a) -> Eselect(u, rep_arg a) + )) + p.p_eqs in + { + p_eqs = List.fold_left + (fun x (n, eq) -> + if n = var then x else (n, eq)::x) + [] rep_eqs; + p_inputs = p.p_inputs; + p_outputs = p.p_outputs; + p_vars = Env.remove var p.p_vars; + } (* Remove all equations of type : - a = b - a = const - (except if a is an output variable) + a = b + a = const + (except if a is an output variable) *) let rec eliminate_id p = - let id_outputs = - (List.fold_left (fun x k -> Sset.add k x) Sset.empty p.p_outputs) in + let id_outputs = + (List.fold_left (fun x k -> Sset.add k x) Sset.empty p.p_outputs) in - let rep = - List.fold_left - (fun x (n, eq) -> - if x = None && (not (Sset.mem n id_outputs)) then - match eq with - | Earg(rarg) -> - Some(n, rarg) - | _ -> None - else - x) - None p.p_eqs in - match rep with - | None -> p, false - | Some(n, rep) -> fst (eliminate_id (eliminate_var n rep p)), true + let rep = + List.fold_left + (fun x (n, eq) -> + if x = None && (not (Sset.mem n id_outputs)) then + match eq with + | Earg(rarg) -> + Some(n, rarg) + | _ -> None + else + x) + None p.p_eqs in + match rep with + | None -> p, false + | Some(n, rep) -> fst (eliminate_id (eliminate_var n rep p)), true (* Eliminate dead variables *) let eliminate_dead p = - let rec living basis = - let new_basis = List.fold_left - (fun b2 (n, eq) -> - if Sset.mem n b2 then - List.fold_left - (fun x k -> Sset.add k x) - b2 - (Scheduler.read_exp_all eq) - else - b2) - basis (List.rev p.p_eqs) - in - if Sset.cardinal new_basis > Sset.cardinal basis - then living new_basis - else new_basis - in - let outs = List.fold_left (fun x k -> Sset.add k x) Sset.empty p.p_outputs in - let ins = List.fold_left (fun x k -> Sset.add k x) Sset.empty p.p_inputs in - let live = living (Sset.union outs ins) in - { - p_eqs = List.filter (fun (n, _) -> Sset.mem n live) p.p_eqs; - p_inputs = p.p_inputs; - p_outputs = p.p_outputs; - p_vars = Env.fold - (fun k s newenv -> - if Sset.mem k live - then Env.add k s newenv - else newenv) - p.p_vars Env.empty - }, (Sset.cardinal live < Env.cardinal p.p_vars) + let rec living basis = + let new_basis = List.fold_left + (fun b2 (n, eq) -> + if Sset.mem n b2 then + List.fold_left + (fun x k -> Sset.add k x) + b2 + (Scheduler.read_exp_all eq) + else + b2) + basis (List.rev p.p_eqs) + in + if Sset.cardinal new_basis > Sset.cardinal basis + then living new_basis + else new_basis + in + let outs = List.fold_left (fun x k -> Sset.add k x) Sset.empty p.p_outputs in + let ins = List.fold_left (fun x k -> Sset.add k x) Sset.empty p.p_inputs in + let live = living (Sset.union outs ins) in + { + p_eqs = List.filter (fun (n, _) -> Sset.mem n live) p.p_eqs; + p_inputs = p.p_inputs; + p_outputs = p.p_outputs; + p_vars = Env.fold + (fun k s newenv -> + if Sset.mem k live + then Env.add k s newenv + else newenv) + p.p_vars Env.empty + }, (Sset.cardinal live < Env.cardinal p.p_vars) (* Topological sort *) let topo_sort p = - (Scheduler.schedule p, false) + (Scheduler.schedule p, false) (* Apply all the simplification passes, - in the order given in the header of this file + in the order given in the header of this file *) let rec simplify_with steps p = - let pp, use = List.fold_left - (fun (x, u) (f, n) -> - print_string n; - let xx, uu = f x in - print_string (if uu then " *\n" else "\n"); - (xx, u || uu)) - (p, false) steps in - if use then simplify_with steps pp else pp + let pp, use = List.fold_left + (fun (x, u) (f, n) -> + print_string n; + let xx, uu = f x in + print_string (if uu then " *\n" else "\n"); + (xx, u || uu)) + (p, false) steps in + if use then simplify_with steps pp else pp let simplify p = - let p = simplify_with [ - topo_sort, "topo_sort"; - cascade_slices, "cascade_slices"; - pass_concat, "pass_concat"; - arith_simplify, "arith_simplify"; - select_to_id, "select_to_id"; - same_eq_simplify, "same_eq_simplify"; - eliminate_id, "eliminate_id"; - ] p in - let p = simplify_with [ - eliminate_dead, "eliminate_dead"; - topo_sort, "topo_sort"; (* make sure last step is a topological sort *) - ] p in - p + let p = simplify_with [ + topo_sort, "topo_sort"; + cascade_slices, "cascade_slices"; + pass_concat, "pass_concat"; + arith_simplify, "arith_simplify"; + select_to_id, "select_to_id"; + same_eq_simplify, "same_eq_simplify"; + eliminate_id, "eliminate_id"; + ] p in + let p = simplify_with [ + eliminate_dead, "eliminate_dead"; + topo_sort, "topo_sort"; (* make sure last step is a topological sort *) + ] p in + p |