Project

General

Profile

Revision a38c681e src/liveness.ml

View differences:

src/liveness.ml
98 98
  ISet.fold
99 99
    (fun var unused -> ISet.diff unused (cone_of_influence g var))
100 100
    (ISet.union outputs mems)
101
    (ISet.union inputs mems) 
101
    (ISet.union inputs mems)
102 102

  
103
(* Computes the set of output and mem variables of [node].
104
   We don't reuse input variables, due to possible aliasing *)
105
let node_non_locals node =
106
  let mems = ExprDep.node_memory_variables node in
107
 List.fold_left (fun non_loc v -> if ISet.mem v.var_id mems then non_loc else ISet.add v.var_id non_loc) (ExprDep.node_output_variables node) node.node_locals
108

  
109
(* checks whether a variable is aliasable,
110
   depending on its (address) type *)
111
let is_aliasable var =
112
 Types.is_address_type var.var_type
113
 
114 103
(* computes the set of potentially reusable variables.
115 104
   We don't reuse input variables, due to possible aliasing *)
116 105
let node_reusable_variables node =
......
123 112

  
124 113
(* Recursively removes useless variables,
125 114
   i.e. variables that are current roots of the dep graph [g]
126
   and returns [reusable] such roots *)
127
let remove_local_roots reusable g =
115
   and returns [locals] and [evaluated] such roots *)
116
let remove_local_roots locals evaluated g =
128 117
  let rem = ref true in
129 118
  let roots = ref Disjunction.CISet.empty in
130 119
  while !rem
131 120
  do
132 121
    rem := false;
133 122
    let new_roots = graph_roots g in
134
    let reusable_roots = Disjunction.CISet.filter (fun v -> List.mem v.var_id new_roots) reusable in
123
    let reusable_roots = Disjunction.CISet.filter (fun v -> (List.mem v.var_id new_roots) && (Disjunction.CISet.mem v locals)) evaluated in
135 124
    if not (Disjunction.CISet.is_empty reusable_roots) then
136 125
      begin
137 126
	rem := true;
......
141 130
  done;
142 131
  !roots
143 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
 
144 138
(* checks whether a variable [v] is an input of the [var] equation, with an address type.
145 139
   if so, [var] could not safely reuse/alias [v], should [v] be dead in the caller node,
146 140
   because [v] may not be dead in the callee node when [var] is assigned *)
......
163 157
    IdentDepGraph.remove_vertex g v
164 158
  end
165 159

  
166
(* computes the dead dependencies of variable [var] in graph [g],
167
   once [var] has been evaluated *)
168
let compute_dead_dependencies reusable var g dead =
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 =
169 166
  begin
170
    IdentDepGraph.iter_succ (IdentDepGraph.remove_edge g var) g var;
171
    dead := Disjunction.CISet.union (remove_local_roots reusable g) !dead;
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;
172 171
  end
173 172

  
174 173
let compute_reuse_policy node schedule disjoint g =
175
  let reusable = node_reusable_variables node in
174
  let locals = node_reusable_variables node in
176 175
  let sort = ref schedule in
177
  let dead = ref Disjunction.CISet.empty in
176
  let evaluated = ref Disjunction.CISet.empty in
177
  let reusable = ref Disjunction.CISet.empty in
178 178
  let policy = Hashtbl.create 23 in
179
  while false (*!sort <> []*)
179
  while !sort <> []
180 180
  do
181 181
    let head = get_node_var (List.hd !sort) node in
182
    compute_dead_dependencies reusable head.var_id g dead;
182
    compute_reusable_dependencies locals evaluated reusable head g;
183 183
    let aliasable = is_aliasable_input node head.var_id in
184 184
    let eligible v = Typing.eq_ground head.var_type v.var_type && not (aliasable v) in
185 185
    let reuse =
186 186
      try
187 187
	let disj = Hashtbl.find disjoint head.var_id in
188
	Disjunction.CISet.max_elt (Disjunction.CISet.filter (fun v -> (eligible v) && not (Disjunction.CISet.mem v !dead)) disj)
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 189
      with Not_found ->
190 190
      try
191
	Disjunction.CISet.choose (Disjunction.CISet.filter (fun v -> eligible v) !dead)
191
	Disjunction.CISet.choose (Disjunction.CISet.filter (fun v -> eligible v) !reusable)
192 192
      with Not_found -> head in
193
    dead := Disjunction.CISet.remove reuse !dead;
193
    reusable := Disjunction.CISet.remove reuse !reusable;
194 194
    Disjunction.replace_in_disjoint_map disjoint head reuse;
195 195
    merge_in_dep_graph head.var_id reuse.var_id g;
196 196
    Hashtbl.add policy head.var_id reuse;
197
    Log.report ~level:6 (fun fmt -> Format.fprintf fmt "reuse %s instead of %s@." reuse.var_id head.var_id);
198
    Log.report ~level:6 (fun fmt -> Format.fprintf fmt "new disjoint:%a@." Disjunction.pp_disjoint_map disjoint);
199
    Log.report ~level:6 
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 200
      (fun fmt -> Format.fprintf fmt "new dependency graph:%a@." pp_dep_graph g);
201 201
    sort := List.tl !sort;
202 202
  done;

Also available in: Unified diff