Project

General

Profile

Revision d50b0dc0 src/liveness.ml

View differences:

src/liveness.ml
121 121
    | None           -> []
122 122
    | Some (_, args) -> List.fold_right (fun e r -> match e.expr_desc with Expr_ident id -> id::r | _ -> r) args [] in
123 123
  fun v -> is_aliasable v && List.mem v.var_id inputs_var
124

  
124
(*
125
    let res =
126
is_aliasable v && List.mem v.var_id inputs_var
127
    in (Format.eprintf "aliasable %s by %s = %B@." var v.var_id res; res)
128
*)
125 129
(* replace variable [v] by [v'] in graph [g].
126 130
   [v'] is a dead variable
127 131
*)
......
171 175
  end
172 176

  
173 177
(* tests whether a variable [v] may be (re)used instead of [var]. The conditions are:
178
   - [v] has been really used ([v] is its own representative)
174 179
   - same type
175 180
   - [v] is not an aliasable input of the equation defining [var]
176 181
   - [v] is not one of the current heads (which contain [var])
177
   - the representative of [v] is not currently in use
182
   - [v] is not currently in use
178 183
 *)
179 184
let eligible node ctx heads var v =
180
     Typing.eq_ground var.var_type v.var_type
185
     Hashtbl.find ctx.policy v.var_id == v
186
  && Typing.eq_ground (Types.unclock_type var.var_type) (Types.unclock_type v.var_type)
181 187
  && not (is_aliasable_input node var.var_id v)
182 188
  && not (List.exists (fun h -> h.var_id = v.var_id) heads)
183
  && let repr_v = Hashtbl.find ctx.policy v.var_id
184
     in not (Disjunction.CISet.exists (fun p -> IdentDepGraph.mem_edge ctx.dep_graph p.var_id repr_v.var_id) ctx.evaluated)
189
  && (*let repr_v = Hashtbl.find ctx.policy v.var_id*)
190
     not (Disjunction.CISet.exists (fun p -> IdentDepGraph.mem_edge ctx.dep_graph p.var_id v.var_id) ctx.evaluated)
185 191

  
186 192
let compute_reuse node ctx heads var =
187 193
  let disjoint = Hashtbl.find ctx.disjoint var.var_id in
188 194
  let locally_reusable v =
189 195
    IdentDepGraph.fold_pred (fun p r -> r && Disjunction.CISet.exists (fun d -> p = d.var_id) disjoint) ctx.dep_graph v.var_id true in
190 196
  let eligibles = Disjunction.CISet.filter (eligible node ctx heads var) ctx.evaluated in
197
  Log.report ~level:7 (fun fmt -> Format.fprintf fmt "eligibles:%a@." Disjunction.pp_ciset eligibles);
191 198
  let quasi_dead, live = Disjunction.CISet.partition locally_reusable eligibles in
199
  Log.report ~level:7 (fun fmt -> Format.fprintf fmt "live:%a@." Disjunction.pp_ciset live);
192 200
  try
193 201
    let disjoint_live = Disjunction.CISet.inter disjoint live in
202
    Log.report ~level:7 (fun fmt -> Format.fprintf fmt "disjoint live:%a@." Disjunction.pp_ciset disjoint_live);
194 203
    let reuse = Disjunction.CISet.max_elt disjoint_live in
204
    (*let reuse' = Hashtbl.find ctx.policy reuse.var_id in*)
195 205
    begin
196 206
      IdentDepGraph.add_edge ctx.dep_graph var.var_id reuse.var_id;
197
      Hashtbl.add ctx.policy var.var_id (Hashtbl.find ctx.policy reuse.var_id);
207
      (*if reuse != reuse' then IdentDepGraph.add_edge ctx.dep_graph reuse.var_id reuse'.var_id;*)
208
      Hashtbl.add ctx.policy var.var_id reuse;
198 209
      ctx.evaluated <- Disjunction.CISet.add var ctx.evaluated;
199 210
      (*Format.eprintf "%s reused by live@." var.var_id;*)
200 211
    end
201 212
  with Not_found ->
202 213
  try
203 214
    let dead = Disjunction.CISet.filter (fun v -> is_graph_root v.var_id ctx.dep_graph) quasi_dead in
215
    Log.report ~level:7 (fun fmt -> Format.fprintf fmt "dead:%a@." Disjunction.pp_ciset dead);
204 216
    let reuse = Disjunction.CISet.choose dead in
217
    (*let reuse' = Hashtbl.find ctx.policy reuse.var_id in*)
205 218
    begin
206 219
      IdentDepGraph.add_edge ctx.dep_graph var.var_id reuse.var_id;
207
      Hashtbl.add ctx.policy var.var_id (Hashtbl.find ctx.policy reuse.var_id);
220
      (*if reuse != reuse' then IdentDepGraph.add_edge ctx.dep_graph reuse.var_id reuse'.var_id;*)
221
      Hashtbl.add ctx.policy var.var_id reuse;
208 222
      ctx.evaluated <- Disjunction.CISet.add var ctx.evaluated;
209 223
      (*Format.eprintf "%s reused by dead %a@." var.var_id Disjunction.pp_ciset dead;*)
210 224
    end
......
225 239
    Log.report ~level:6 (fun fmt -> Format.fprintf fmt "new context:%a@." pp_context ctx);
226 240
    let heads = List.map (fun v -> get_node_var v node) (List.hd !sort) in
227 241
    Log.report ~level:6 (fun fmt -> Format.fprintf fmt "NEW HEADS:");
228
    List.iter (fun head -> Log.report ~level:6 (fun fmt -> Format.fprintf fmt "%s " head.var_id)) heads;
242
    List.iter (fun head -> Log.report ~level:6 (fun fmt -> Format.fprintf fmt "%s (%a)" head.var_id Printers.pp_node_eq (get_node_eq head.var_id node))) heads;
229 243
    Log.report ~level:6 (fun fmt -> Format.fprintf fmt "@.");
230 244
    Log.report ~level:6 (fun fmt -> Format.fprintf fmt "COMPUTE_DEPENDENCIES@.");
231 245
    compute_dependencies heads ctx;

Also available in: Unified diff