lustrec / src / liveness.ml @ a38c681e
History | View | Annotate | Download (9.84 KB)
1 |
(* ---------------------------------------------------------------------------- |
---|---|
2 |
* SchedMCore - A MultiCore Scheduling Framework |
3 |
* Copyright (C) 2009-2013, ONERA, Toulouse, FRANCE - LIFL, Lille, FRANCE |
4 |
* Copyright (C) 2012-2013, INPT, Toulouse, FRANCE |
5 |
* |
6 |
* This file is part of Prelude |
7 |
* |
8 |
* Prelude is free software; you can redistribute it and/or |
9 |
* modify it under the terms of the GNU Lesser General Public License |
10 |
* as published by the Free Software Foundation ; either version 2 of |
11 |
* the License, or (at your option) any later version. |
12 |
* |
13 |
* Prelude is distributed in the hope that it will be useful, but |
14 |
* WITHOUT ANY WARRANTY ; without even the implied warranty of |
15 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
16 |
* Lesser General Public License for more details. |
17 |
* |
18 |
* You should have received a copy of the GNU Lesser General Public |
19 |
* License along with this program ; if not, write to the Free Software |
20 |
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 |
21 |
* USA |
22 |
*---------------------------------------------------------------------------- *) |
23 |
|
24 |
open Utils |
25 |
open LustreSpec |
26 |
open Corelang |
27 |
open Graph |
28 |
open Causality |
29 |
|
30 |
(* Computes the last dependency |
31 |
*) |
32 |
|
33 |
(* Computes the death table of [node] wrt dep graph [g] and topological [sort]. |
34 |
The death table is a mapping: ident -> Set(ident) such that: |
35 |
death x is the set of local variables which get dead (i.e. unused) |
36 |
after x is evaluated, but were until live. |
37 |
let death_table node g sort = |
38 |
let death = Hashtbl.create 23 in |
39 |
let sort = ref (List.rev sort) in |
40 |
let buried = ref ISet.empty in |
41 |
begin |
42 |
buried := ExprDep.node_memory_variables node; |
43 |
buried := List.fold_left (fun dead (v : var_decl) -> ISet.add v.var_id dead) !buried node.node_outputs; |
44 |
(* We could also try to reuse input variables, due to C parameter copying semantics *) |
45 |
buried := List.fold_left (fun dead (v : var_decl) -> ISet.add v.var_id dead) !buried node.node_inputs; |
46 |
while (!sort <> []) |
47 |
do |
48 |
let head = List.hd !sort in |
49 |
let dead = IdentDepGraph.fold_succ |
50 |
(fun tgt dead -> if not (ExprDep.is_instance_var tgt || ISet.mem tgt !buried) then ISet.add tgt dead else dead) |
51 |
g head ISet.empty in |
52 |
buried := ISet.union !buried dead; |
53 |
Hashtbl.add death head dead; |
54 |
sort := List.tl !sort |
55 |
done; |
56 |
IdentDepGraph.clear g; |
57 |
death |
58 |
end |
59 |
*) |
60 |
|
61 |
(* computes the in-degree for each local variable of node [n], according to dep graph [g]. |
62 |
*) |
63 |
let compute_fanin n g = |
64 |
let locals = ISet.diff (ExprDep.node_local_variables n) (ExprDep.node_memory_variables n) in |
65 |
let fanin = Hashtbl.create 23 in |
66 |
begin |
67 |
IdentDepGraph.iter_vertex (fun v -> if ISet.mem v locals then Hashtbl.add fanin v (IdentDepGraph.in_degree g v)) g; |
68 |
fanin |
69 |
end |
70 |
|
71 |
let pp_fanin fmt fanin = |
72 |
begin |
73 |
Format.fprintf fmt "{ /* locals fanin: */@."; |
74 |
Hashtbl.iter (fun s t -> Format.fprintf fmt "%s -> %d@." s t) fanin; |
75 |
Format.fprintf fmt "}@." |
76 |
end |
77 |
|
78 |
(* computes the cone of influence of a given [var] wrt a dependency graph [g]. |
79 |
*) |
80 |
let cone_of_influence g var = |
81 |
(*Format.printf "coi: %s@." var;*) |
82 |
let frontier = ref (ISet.add var ISet.empty) in |
83 |
let coi = ref ISet.empty in |
84 |
while not (ISet.is_empty !frontier) |
85 |
do |
86 |
let head = ISet.min_elt !frontier in |
87 |
(*Format.printf "head: %s@." head;*) |
88 |
frontier := ISet.remove head !frontier; |
89 |
if ExprDep.is_read_var head then coi := ISet.add (ExprDep.undo_read_var head) !coi; |
90 |
List.iter (fun s -> frontier := ISet.add s !frontier) (IdentDepGraph.succ g head); |
91 |
done; |
92 |
!coi |
93 |
|
94 |
let compute_unused_variables n g = |
95 |
let inputs = ExprDep.node_input_variables n in |
96 |
let mems = ExprDep.node_memory_variables n in |
97 |
let outputs = ExprDep.node_output_variables n in |
98 |
ISet.fold |
99 |
(fun var unused -> ISet.diff unused (cone_of_influence g var)) |
100 |
(ISet.union outputs mems) |
101 |
(ISet.union inputs mems) |
102 |
|
103 |
(* computes the set of potentially reusable variables. |
104 |
We don't reuse input variables, due to possible aliasing *) |
105 |
let node_reusable_variables node = |
106 |
let mems = ExprDep.node_memory_variables node in |
107 |
List.fold_left |
108 |
(fun acc l -> |
109 |
if ISet.mem l.var_id mems then acc else Disjunction.CISet.add l acc) |
110 |
Disjunction.CISet.empty |
111 |
node.node_locals |
112 |
|
113 |
(* Recursively removes useless variables, |
114 |
i.e. variables that are current roots of the dep graph [g] |
115 |
and returns [locals] and [evaluated] such roots *) |
116 |
let remove_local_roots locals evaluated g = |
117 |
let rem = ref true in |
118 |
let roots = ref Disjunction.CISet.empty in |
119 |
while !rem |
120 |
do |
121 |
rem := false; |
122 |
let new_roots = graph_roots g in |
123 |
let reusable_roots = Disjunction.CISet.filter (fun v -> (List.mem v.var_id new_roots) && (Disjunction.CISet.mem v locals)) evaluated in |
124 |
if not (Disjunction.CISet.is_empty reusable_roots) then |
125 |
begin |
126 |
rem := true; |
127 |
Disjunction.CISet.iter (fun v -> IdentDepGraph.remove_vertex g v.var_id) reusable_roots; |
128 |
roots := Disjunction.CISet.union reusable_roots !roots |
129 |
end |
130 |
done; |
131 |
!roots |
132 |
|
133 |
(* checks whether a variable is aliasable, |
134 |
depending on its (address) type *) |
135 |
let is_aliasable var = |
136 |
Types.is_address_type var.var_type |
137 |
|
138 |
(* checks whether a variable [v] is an input of the [var] equation, with an address type. |
139 |
if so, [var] could not safely reuse/alias [v], should [v] be dead in the caller node, |
140 |
because [v] may not be dead in the callee node when [var] is assigned *) |
141 |
let is_aliasable_input node var = |
142 |
let eq_var = get_node_eq var node in |
143 |
let inputs_var = |
144 |
match NodeDep.get_callee eq_var.eq_rhs with |
145 |
| None -> [] |
146 |
| Some (_, args) -> List.fold_right (fun e r -> match e.expr_desc with Expr_ident id -> id::r | _ -> r) args [] in |
147 |
fun v -> Types.is_address_type v.var_type && List.mem v.var_id inputs_var |
148 |
|
149 |
(* merges two variables [v] and [v'] of graph [g]. |
150 |
[v] is replaced by [v'] |
151 |
*) |
152 |
let merge_in_dep_graph v v' g = |
153 |
begin |
154 |
IdentDepGraph.add_vertex g v'; |
155 |
IdentDepGraph.iter_succ (fun s -> IdentDepGraph.add_edge g v' s) g v; |
156 |
IdentDepGraph.iter_pred (fun p -> IdentDepGraph.add_edge g p v') g v; |
157 |
IdentDepGraph.remove_vertex g v |
158 |
end |
159 |
|
160 |
(* computes the reusable dependencies of variable [var] in graph [g], |
161 |
once [var] has been evaluated |
162 |
[dead] is the set of evaluated and dead variables |
163 |
[eval] is the set of evaluated variables |
164 |
*) |
165 |
let compute_reusable_dependencies locals evaluated reusable var g = |
166 |
begin |
167 |
Log.report ~level:2 (fun fmt -> Format.fprintf fmt "compute_reusable_dependencies %a %a %a %a %a@." Disjunction.pp_ciset locals Disjunction.pp_ciset !evaluated Disjunction.pp_ciset !reusable Printers.pp_var_name var pp_dep_graph g); |
168 |
evaluated := Disjunction.CISet.add var !evaluated; |
169 |
IdentDepGraph.iter_succ (IdentDepGraph.remove_edge g var.var_id) g var.var_id; |
170 |
reusable := Disjunction.CISet.union (remove_local_roots locals !evaluated g) !reusable; |
171 |
end |
172 |
|
173 |
let compute_reuse_policy node schedule disjoint g = |
174 |
let locals = node_reusable_variables node in |
175 |
let sort = ref schedule in |
176 |
let evaluated = ref Disjunction.CISet.empty in |
177 |
let reusable = ref Disjunction.CISet.empty in |
178 |
let policy = Hashtbl.create 23 in |
179 |
while !sort <> [] |
180 |
do |
181 |
let head = get_node_var (List.hd !sort) node in |
182 |
compute_reusable_dependencies locals evaluated reusable head g; |
183 |
let aliasable = is_aliasable_input node head.var_id in |
184 |
let eligible v = Typing.eq_ground head.var_type v.var_type && not (aliasable v) in |
185 |
let reuse = |
186 |
try |
187 |
let disj = Hashtbl.find disjoint head.var_id in |
188 |
Disjunction.CISet.max_elt (Disjunction.CISet.filter (fun v -> (eligible v) && (Disjunction.CISet.mem v !evaluated) && not (Disjunction.CISet.mem v !reusable)) disj) |
189 |
with Not_found -> |
190 |
try |
191 |
Disjunction.CISet.choose (Disjunction.CISet.filter (fun v -> eligible v) !reusable) |
192 |
with Not_found -> head in |
193 |
reusable := Disjunction.CISet.remove reuse !reusable; |
194 |
Disjunction.replace_in_disjoint_map disjoint head reuse; |
195 |
merge_in_dep_graph head.var_id reuse.var_id g; |
196 |
Hashtbl.add policy head.var_id reuse; |
197 |
Log.report ~level:2 (fun fmt -> Format.fprintf fmt "reuse %s instead of %s@." reuse.var_id head.var_id); |
198 |
Log.report ~level:1 (fun fmt -> Format.fprintf fmt "new disjoint:%a@." Disjunction.pp_disjoint_map disjoint); |
199 |
Log.report ~level:2 |
200 |
(fun fmt -> Format.fprintf fmt "new dependency graph:%a@." pp_dep_graph g); |
201 |
sort := List.tl !sort; |
202 |
done; |
203 |
IdentDepGraph.clear g; |
204 |
policy |
205 |
|
206 |
(* Reuse policy: |
207 |
- could reuse variables with the same type exactly only (simple). |
208 |
- reusing variables with different types would involve: |
209 |
- either dirty castings |
210 |
- or complex inclusion expression (for instance: array <-> array cell, struct <-> struct field) to be able to reuse only some parts of structured data. |
211 |
... it seems too complex and potentially unsafe |
212 |
- for node instance calls: output variables could NOT reuse aliasable input variables, |
213 |
even if inputs become dead, because the correctness would depend on the scheduling |
214 |
of the callee (so, the compiling strategy could NOT be modular anymore). |
215 |
- once a policy is set, we need to: |
216 |
- replace each variable by its reuse alias. |
217 |
- simplify resulting equations, as we may now have: |
218 |
x = x; --> ; for scalar vars |
219 |
or: |
220 |
x = &{ f1 = x->f1; f2 = t; } --> x->f2 = t; for struct vars |
221 |
- such simplifications are, until now, only expressible at the C source level... |
222 |
*) |
223 |
|
224 |
|
225 |
(* the reuse policy seeks to use less local variables |
226 |
by replacing local variables, applying the rules |
227 |
in the following order: |
228 |
1) use another clock disjoint still live variable, |
229 |
with the greatest possible disjoint clock |
230 |
2) reuse a dead variable |
231 |
For the sake of safety, we replace variables by others: |
232 |
- with the same type |
233 |
- not aliasable (i.e. address type) |
234 |
*) |
235 |
|
236 |
let pp_reuse_policy fmt policy = |
237 |
begin |
238 |
Format.fprintf fmt "{ /* reuse policy */@."; |
239 |
Hashtbl.iter (fun s t -> Format.fprintf fmt "%s -> %s@." s t.var_id) policy; |
240 |
Format.fprintf fmt "}@." |
241 |
end |
242 |
(* Local Variables: *) |
243 |
(* compile-command:"make -C .." *) |
244 |
(* End: *) |