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