scheduler.ml 2.04 KB
 Quentin Aristote committed Dec 31, 2018 1 ``````open Ast `````` Quentin Aristote committed Oct 16, 2018 2 3 4 5 ``````open Graph exception Combinational_cycle `````` Quentin Aristote committed Nov 08, 2018 6 7 8 ``````(* We create the graph of the dependencies of the equations and order it so that we know in which order we must execute our equations. *) `````` Quentin Aristote committed Oct 16, 2018 9 10 ``````let schedule p = let vars = mk_graph () in `````` Quentin Aristote committed Dec 31, 2018 11 12 13 `````` (* We first add a node for each variable in the netlist. *) Env.iter (fun v _ -> add_node vars v) p.p_vars ; (* Then we add the appropriate edges for each equation. *) `````` 14 `````` List.iter `````` Quentin Aristote committed Dec 31, 2018 15 16 `````` (fun (id, expr) -> let add_var = function `````` Quentin Aristote committed Jan 02, 2019 17 `````` | Avar x -> add_edge vars x id `````` Quentin Aristote committed Dec 31, 2018 18 19 20 21 22 23 24 25 26 27 28 29 `````` | _ -> () in match expr with | Earg a -> add_var a | Ereg x -> (* This leads to a combinational cycle when there isn't one if the netlist contains two equations similar to the following : > a = REG b > b = REG a It's not that much of a problem as those netlists are pretty useless. *) `````` Quentin Aristote committed Jan 17, 2019 30 `````` add_edge vars id x `````` Quentin Aristote committed Dec 31, 2018 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 `````` | Enot a -> add_var a | Ebinop (_, a, b) -> add_var a ; add_var b | Emux (s, a, b) -> add_var s; add_var a; add_var b | Erom (addr_size, word_size, read_addr) -> add_var read_addr | Eram (addr_size, word_size, read_addr, write_enable, write_addr, data) -> (* We do not need to know write_enable, write_addr and data to compute the output. *) add_var read_addr | Econcat (a, b) -> add_var a; add_var b | Eslice (_, _, a) -> add_var a | Eselect (_, a) -> add_var a) `````` Quentin Aristote committed Mar 04, 2019 53 `````` p.p_eqs ; `````` Quentin Aristote committed Oct 16, 2018 54 55 56 `````` let rec gen_eqs = function | [] -> [] | t::q -> try `````` Quentin Aristote committed Dec 31, 2018 57 58 59 `````` (t, List.assoc t p.p_eqs)::(gen_eqs q) with | Not_found -> gen_eqs q in `````` Quentin Aristote committed Mar 04, 2019 60 61 62 63 64 65 `````` try {p_eqs = gen_eqs (topological vars); p_inputs = p.p_inputs; p_outputs = p.p_outputs; p_vars = p.p_vars} with Has_cycle -> raise Combinational_cycle``````