Revision 53206908 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.Cycle vl) as exc > 

155 
let vl = filter_original n vl in 

156 
pp_error Format.err_formatter vl; 

157 
raise exc 

165  158  
159 
let compute_node_reuse_table report = 

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

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

162 
(* 

166  163 
if !Options.print_reuse 
167  164 
then 
168  165 
begin 
...  ...  
186  183 
Liveness.pp_reuse_policy reuse 
187  184 
); 
188  185 
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 

186 
*) 

187 
reuse 

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


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


195 
let report = schedule_node nd in 

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


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


203  
204 
let compute_prog_reuse_table report = 

205 
IMap.map compute_node_reuse_table report 

206  
207 
(* removes inlined local variables from schedule report, 

208 
which are now useless *) 

209 
let remove_node_inlined_locals locals report = 

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

211 
let schedule' = 

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

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

214 
report.schedule [] in 

215 
begin 

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

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

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

219 
{ report with schedule = schedule' } 

220 
end 

221  
222 
let remove_prog_inlined_locals removed reuse = 

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

207  224  
208  225 
let pp_eq_schedule fmt vl = 
209  226 
match vl with 
...  ...  
222  239 
let pp_fanin_table fmt node_schs = 
223  240 
IMap.iter 
224  241 
(fun nd report > 
225 
Format.fprintf fmt "%s : %a" nd Liveness.pp_fanin report.fanin_table) 

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

243 
node_schs 

244  
245 
let pp_dep_graph fmt node_schs = 

246 
IMap.iter 

247 
(fun nd report > 

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

226  249 
node_schs 
227  250  
228  251 
let pp_warning_unused fmt node_schs = 
...  ...  
241  264 
) 
242  265 
node_schs 
243  266  
267  
244  268 
(* Local Variables: *) 
245  269 
(* compilecommand:"make C .." *) 
246  270 
(* End: *) 
Also available in: Unified diff