Revision 44bea83a src/liveness.ml
src/liveness.ml | ||
---|---|---|
164 | 164 |
- either dirty castings |
165 | 165 |
- or complex inclusion expression (for instance: array <-> array cell, struct <-> struct field) to be able to reuse only some parts of structured data. |
166 | 166 |
... it seems too complex and potentially unsafe |
167 |
- for node instance calls: output variables could NOT reuse input variables, |
|
167 |
- for node instance calls: output variables could NOT reuse aliasable input variables,
|
|
168 | 168 |
even if inputs become dead, because the correctness would depend on the scheduling |
169 | 169 |
of the callee (so, the compiling strategy could NOT be modular anymore). |
170 | 170 |
- once a policy is set, we need to: |
... | ... | |
182 | 182 |
|
183 | 183 |
(* Replaces [v] by [v'] in death table [death] *) |
184 | 184 |
let replace_in_death_table death v v' = |
185 |
Hashtbl.iter (fun k dead -> Hashtbl.replace death k (replace_in_set dead v v')) death |
|
185 |
begin |
|
186 |
Hashtbl.remove death v; |
|
187 |
Hashtbl.iter (fun k dead -> Hashtbl.replace death k (replace_in_set dead v v')) death |
|
188 |
end |
|
189 |
|
|
190 |
let reuse_by_disjoint var reuse death disjoint = |
|
191 |
begin |
|
192 |
Log.report ~level:6 (fun fmt -> Format.fprintf fmt "reuse %s by disjoint %s@." var reuse.var_id); |
|
193 |
Disjunction.replace_in_disjoint_map disjoint var reuse.var_id; |
|
194 |
Log.report ~level:6 (fun fmt -> Format.fprintf fmt "new disjoint:%a@." Disjunction.pp_disjoint_map disjoint); |
|
195 |
end |
|
186 | 196 |
|
187 |
let find_compatible_local node var dead death disjoint policy = |
|
197 |
|
|
198 |
let reuse_by_dead var reuse death disjoint = |
|
199 |
begin |
|
200 |
Log.report ~level:6 (fun fmt -> Format.fprintf fmt "reuse %s by dead %s@." var reuse.var_id); |
|
201 |
replace_in_death_table death var reuse.var_id; |
|
202 |
Log.report ~level:6 (fun fmt -> Format.fprintf fmt "new death:%a@." pp_death_table death); |
|
203 |
end |
|
204 |
|
|
205 |
(* the set of really dead variables is a subset of dead vars by the death table. |
|
206 |
indeed, as variables may be aliased to other variables, |
|
207 |
a variable is dead only if all its disjoint-from-evaluated-var aliases are dead *) |
|
208 |
let dead_aliased_variables var reuse dead = |
|
209 |
dead |
|
210 |
|
|
211 |
let find_compatible_local node var dead death disjoint = |
|
188 | 212 |
(*Format.eprintf "find_compatible_local %s %s %a@." node.node_id var pp_iset dead;*) |
189 | 213 |
let typ = (get_node_var var node).var_type in |
190 | 214 |
let eq_var = get_node_eq var node in |
... | ... | |
202 | 226 |
(*Format.eprintf "filter %a = %s@." Printers.pp_var_name v (if res then "true" else "false");*) |
203 | 227 |
res |
204 | 228 |
end in |
205 |
(*Format.eprintf "reuse %s@." var;*)
|
|
229 |
Log.report ~level:6 (fun fmt -> Format.fprintf fmt "reuse %s@." var);
|
|
206 | 230 |
try |
207 | 231 |
let disj = Hashtbl.find disjoint var in |
208 | 232 |
let reuse = List.find (filter (fun v -> ISet.mem v.var_id disj && not (ISet.mem v.var_id dead))) locals in |
209 |
(*Format.eprintf "reuse %s by %s@." var reuse.var_id;*) |
|
210 |
Disjunction.replace_in_disjoint_map disjoint var reuse.var_id; |
|
211 |
(*Format.eprintf "new disjoint:%a@." Disjunction.pp_disjoint_map disjoint;*) |
|
212 |
Hashtbl.add policy var reuse.var_id |
|
233 |
reuse_by_disjoint var reuse death disjoint; |
|
234 |
Some reuse |
|
213 | 235 |
with Not_found -> |
214 | 236 |
try |
215 | 237 |
let reuse = List.find (filter (fun v -> ISet.mem v.var_id dead)) locals in |
216 |
(*Format.eprintf "reuse %s by %s@." var reuse.var_id;*) |
|
217 |
replace_in_death_table death var reuse.var_id; |
|
218 |
(*Format.eprintf "new death:%a@." pp_death_table death;*) |
|
219 |
Hashtbl.add policy var reuse.var_id |
|
220 |
with Not_found -> () |
|
238 |
reuse_by_dead var reuse death disjoint; |
|
239 |
Some reuse |
|
240 |
with Not_found -> None |
|
221 | 241 |
|
222 | 242 |
(* the reuse policy seeks to use less local variables |
223 | 243 |
by replacing local variables, applying the rules |
... | ... | |
231 | 251 |
*) |
232 | 252 |
let reuse_policy node sort death disjoint = |
233 | 253 |
let dead = ref ISet.empty in |
254 |
let real_dead = ref ISet.empty in |
|
234 | 255 |
let policy = Hashtbl.create 23 in |
235 |
let sort = ref sort in |
|
256 |
let sort = ref [] (*sort*) in |
|
257 |
let aux_vars = ExprDep.node_auxiliary_variables node in |
|
236 | 258 |
while !sort <> [] |
237 | 259 |
do |
238 | 260 |
let head = List.hd !sort in |
239 |
if Hashtbl.mem death head then
|
|
261 |
if ISet.mem head aux_vars then
|
|
240 | 262 |
begin |
241 |
dead := ISet.union (Hashtbl.find death head) !dead; |
|
242 |
end; |
|
243 |
find_compatible_local node head !dead death disjoint policy; |
|
244 |
sort := List.tl !sort; |
|
263 |
if Hashtbl.mem death head then |
|
264 |
begin |
|
265 |
dead := ISet.union (Hashtbl.find death head) !dead; |
|
266 |
end; |
|
267 |
real_dead := ISet.empty; |
|
268 |
(match find_compatible_local node head !real_dead death disjoint with |
|
269 |
| Some reuse -> Hashtbl.add policy head reuse |
|
270 |
| None -> ()); |
|
271 |
sort := List.tl !sort; |
|
272 |
end |
|
245 | 273 |
done; |
246 | 274 |
policy |
247 | 275 |
|
248 | 276 |
let pp_reuse_policy fmt policy = |
249 | 277 |
begin |
250 | 278 |
Format.fprintf fmt "{ /* reuse policy */@."; |
251 |
Hashtbl.iter (fun s t -> Format.fprintf fmt "%s -> %s@." s t) policy; |
|
279 |
Hashtbl.iter (fun s t -> Format.fprintf fmt "%s -> %s@." s t.var_id) policy;
|
|
252 | 280 |
Format.fprintf fmt "}@." |
253 | 281 |
end |
254 | 282 |
(* Local Variables: *) |
Also available in: Unified diff