Revision 3b2bd83d src/scheduling.ml
src/scheduling.ml  

17  17  
18  18 
type schedule_report = 
19  19 
{ 
20 
(* the scheduled node *) 

21 
node : node_desc; 

20  22 
(* a schedule computed wrt the dependency graph *) 
21  23 
schedule : ident list list; 
22  24 
(* the set of unused variables (no output or mem depends on them) *) 
23  25 
unused_vars : ISet.t; 
24  26 
(* the table mapping each local var to its indegree *) 
25  27 
fanin_table : (ident, int) Hashtbl.t; 
28 
(* the dependency graph *) 

29 
dep_graph : IdentDepGraph.t; 

26  30 
(* the table mapping each assignment to a reusable variable *) 
27 
reuse_table : (ident, var_decl) Hashtbl.t


31 
(*reuse_table : (ident, var_decl) Hashtbl.t*)


28  32 
} 
29  33  
30  34 
(* Topological sort with a priority for variables belonging in the same equation lhs. 
...  ...  
125  129 
if vdecl.var_orig then v :: res else res) vl [] 
126  130  
127  131 
let schedule_node n = 
128 
let node_vars = get_node_vars n in


132 
(* let node_vars = get_node_vars n in *)


129  133 
try 
130  134 
let eq_equiv = ExprDep.node_eq_equiv n in 
131  135 
let eq_equiv v1 v2 = 
...  ...  
134  138 
with Not_found > false in 
135  139  
136  140 
let n', g = global_dependency n in 
137 
Log.report ~level:5 

138 
(fun fmt > 

139 
Format.fprintf fmt 

140 
"dependency graph for node %s: %a" 

141 
n'.node_id 

142 
pp_dep_graph g 

143 
); 

144  141 

145  142 
(* TODO X: extend the graph with inputs (adapt the causality analysis to deal with inputs 
146  143 
compute: coi predecessors of outputs 
...  ...  
152  149 
let sort = topological_sort eq_equiv g in 
153  150 
let unused = Liveness.compute_unused_variables n gg in 
154  151 
let fanin = Liveness.compute_fanin n gg in 
152 
{ node = n'; schedule = sort; unused_vars = unused; fanin_table = fanin; dep_graph = gg; } 

155  153  
156 
let (disjoint, reuse) = 

157 
if !Options.optimization >= 3 

158 
then 

159 
let disjoint = Disjunction.clock_disjoint_map node_vars in 

160 
(disjoint, 

161 
Liveness.compute_reuse_policy n sort disjoint gg) 

162 
else 

163 
(Hashtbl.create 1, 

164 
Hashtbl.create 1) in 

154 
with (Causality.Error err) as exc > 

155 
match err with 

156 
 DataCycle vl > 

157 
let vl = filter_original n vl in 

158 
Causality.pp_error Format.err_formatter err; 

159 
raise exc 

160 
 _ > raise exc 

165  161  
162 
let compute_node_reuse_table report = 

163 
let disjoint = Disjunction.clock_disjoint_map (get_node_vars report.node) in 

164 
let reuse = Liveness.compute_reuse_policy report.node report.schedule disjoint report.dep_graph in 

165 
(* 

166  166 
if !Options.print_reuse 
167  167 
then 
168  168 
begin 
...  ...  
186  186 
Liveness.pp_reuse_policy reuse 
187  187 
); 
188  188 
end; 
189 
n', { schedule = sort; unused_vars = unused; fanin_table = fanin; reuse_table = reuse } 

190 
with (Causality.Cycle vl) as exc > 

191 
let vl = filter_original n vl in 

192 
pp_error Format.err_formatter vl; 

193 
raise exc 

189 
*) 

190 
reuse 

191  
194  192  
195  193 
let schedule_prog prog = 
196  194 
List.fold_right ( 
197  195 
fun top_decl (accu_prog, sch_map) > 
198  196 
match top_decl.top_decl_desc with 
199  197 
 Node nd > 
200 
let nd', report = schedule_node nd in


201 
{top_decl with top_decl_desc = Node nd'}::accu_prog,


198 
let report = schedule_node nd in 

199 
{top_decl with top_decl_desc = Node report.node}::accu_prog,


202  200 
IMap.add nd.node_id report sch_map 
203  201 
 _ > top_decl::accu_prog, sch_map 
204  202 
) 
205  203 
prog 
206  204 
([],IMap.empty) 
205 


206  
207 
let compute_prog_reuse_table report = 

208 
IMap.map compute_node_reuse_table report 

209  
210 
(* removes inlined local variables from schedule report, 

211 
which are now useless *) 

212 
let remove_node_inlined_locals locals report = 

213 
let is_inlined v = IMap.exists (fun l _ > v = l) locals in 

214 
let schedule' = 

215 
List.fold_right (fun heads q > let heads' = List.filter (fun v > not (is_inlined v)) heads 

216 
in if heads' = [] then q else heads'::q) 

217 
report.schedule [] in 

218 
begin 

219 
IMap.iter (fun v _ > Hashtbl.remove report.fanin_table v) locals; 

220 
IMap.iter (fun v _ > let iv = ExprDep.mk_instance_var v 

221 
in Liveness.replace_in_dep_graph v iv report.dep_graph) locals; 

222 
{ report with schedule = schedule' } 

223 
end 

224  
225 
let remove_prog_inlined_locals removed reuse = 

226 
IMap.mapi (fun id > remove_node_inlined_locals (IMap.find id removed)) reuse 

207  227  
208  228 
let pp_eq_schedule fmt vl = 
209  229 
match vl with 
...  ...  
222  242 
let pp_fanin_table fmt node_schs = 
223  243 
IMap.iter 
224  244 
(fun nd report > 
225 
Format.fprintf fmt "%s : %a" nd Liveness.pp_fanin report.fanin_table) 

245 
Format.fprintf fmt "%s: %a" nd Liveness.pp_fanin report.fanin_table) 

246 
node_schs 

247  
248 
let pp_dep_graph fmt node_schs = 

249 
IMap.iter 

250 
(fun nd report > 

251 
Format.fprintf fmt "%s dependency graph: %a" nd pp_dep_graph report.dep_graph) 

226  252 
node_schs 
227  253  
228  254 
let pp_warning_unused fmt node_schs = 
...  ...  
236  262 
(fun u > 
237  263 
let vu = get_node_var u nd in 
238  264 
if vu.var_orig 
239 
then Format.fprintf fmt "Warning: variable '%s' seems unused@.%a@." u Location.pp_loc vu.var_loc)


265 
then Format.fprintf fmt " Warning: variable '%s' seems unused@, %a@,@," u Location.pp_loc vu.var_loc)


240  266 
unused 
241  267 
) 
242  268 
node_schs 
243  269  
270  
244  271 
(* Local Variables: *) 
245  272 
(* compilecommand:"make C .." *) 
246  273 
(* End: *) 
Also available in: Unified diff