1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
open Netlist_ast
module Smap = Map.Make(String)
exception Combinational_cycle
let read_exp eq =
let add_arg x l = match x with
| Avar(f) -> f::l
| Aconst(_) -> l
in
let aux = function
| Earg(x) -> add_arg x []
| Ereg(i) -> []
| Enot(x) -> add_arg x []
| Ebinop(_, x, y) -> add_arg x (add_arg y [])
| Emux(a, b, c) -> add_arg a (add_arg b (add_arg c []))
| Erom(_, _, a) -> add_arg a []
| Eram(_, _, a, b, c, d) -> []
| Econcat(u, v) -> add_arg u (add_arg v [])
| Eslice(_, _, a) -> add_arg a []
| Eselect(_, a) -> add_arg a []
in
aux eq
let 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 prog_eq_map p =
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 schedule p =
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;
}
|
