lustrec / src / liveness.ml @ a38c681e
History  View  Annotate  Download (9.84 KB)
1 
(*  

2 
* SchedMCore  A MultiCore Scheduling Framework 
3 
* Copyright (C) 20092013, ONERA, Toulouse, FRANCE  LIFL, Lille, FRANCE 
4 
* Copyright (C) 20122013, 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 021111307 
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 indegree 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 
(* compilecommand:"make C .." *) 
244 
(* End: *) 