Project

General

Profile

Revision 44bea83a src/liveness.ml

View differences:

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