scheduler.ml 2.04 KB
Newer Older
1
open Ast
Quentin Aristote's avatar
commit  
Quentin Aristote committed
2
3
4
5
open Graph

exception Combinational_cycle

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's avatar
commit  
Quentin Aristote committed
9
10
let schedule p =
  let vars = mk_graph () in
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
15
16
    (fun (id, expr) ->
       let add_var = function
17
         | Avar x -> add_edge vars x id
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's avatar
Quentin Aristote committed
30
             add_edge vars id x
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's avatar
Quentin Aristote committed
53
    p.p_eqs ;
Quentin Aristote's avatar
commit  
Quentin Aristote committed
54
55
56
    let rec gen_eqs = function
      | [] -> []
      | t::q -> try
57
58
59
        (t, List.assoc t p.p_eqs)::(gen_eqs q)
      with
        | Not_found -> gen_eqs q in
Quentin Aristote's avatar
Quentin Aristote committed
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