summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAlex AUVOLAT <alex.auvolat@ens.fr>2013-12-17 11:37:54 +0100
committerAlex AUVOLAT <alex.auvolat@ens.fr>2013-12-17 11:37:54 +0100
commit1e5b58007da3be94755b017004cd5fe484ccbed7 (patch)
tree0b285c48f3151add05cf7c8dfbb960646c7df49f
parentf91d7484c8d5af62dff97eb9ce5a5ac85aba2005 (diff)
downloadSystDigit-Projet-1e5b58007da3be94755b017004cd5fe484ccbed7.tar.gz
SystDigit-Projet-1e5b58007da3be94755b017004cd5fe484ccbed7.zip
Tabs to spaces ; deleted Caml simulator (useless anyways)
-rw-r--r--README136
-rw-r--r--camlsim/_tags3
-rw-r--r--camlsim/machine.ml174
-rw-r--r--camlsim/netlist.ml17
-rw-r--r--camlsim/netlist_ast.ml42
-rw-r--r--camlsim/netlist_lexer.mll37
-rw-r--r--camlsim/netlist_parser.mly70
-rw-r--r--camlsim/simulator.ml67
-rw-r--r--csim/load.c304
-rw-r--r--csim/main.c154
-rw-r--r--csim/sim.c382
-rw-r--r--csim/sim.h122
-rw-r--r--csim/util.c52
-rw-r--r--sched/graph.ml48
-rw-r--r--sched/main.ml38
-rw-r--r--sched/netlist_dumb.ml372
-rw-r--r--sched/scheduler.ml130
-rw-r--r--sched/simplify.ml568
18 files changed, 1149 insertions, 1567 deletions
diff --git a/README b/README
index bbbc454..5475dbe 100644
--- a/README
+++ b/README
@@ -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;
}
diff --git a/csim/sim.c b/csim/sim.c
index db30ea3..e3d61da 100644
--- a/csim/sim.c
+++ b/csim/sim.c
@@ -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");
}
diff --git a/csim/sim.h b/csim/sim.h
index 80fab56..c331fa5 100644
--- a/csim/sim.h
+++ b/csim/sim.h
@@ -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