Revision a38c681e src/liveness.ml
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