Revision e41592cf src/scheduling.ml
src/scheduling.ml  

31  31 
For variables still unrelated, standard compare is used to choose the minimal element. 
32  32 
This priority is used since it helps a lot in factorizing generated code. 
33  33 
Moreover, the dependency graph is browsed in a depthfirst manner whenever possible, 
34 
to improve the behavior of optimization algorithms applied in forthcoming compilation steps.


34 
to improve the behavior of optimization algorithms applied in forthcoming compilation steps. 

35  35 
In the following functions: 
36  36 
 [eq_equiv] is the equivalence relation between vars of the same equation lhs 
37  37 
 [g] the (imperative) graph to be topologically sorted 
...  ...  
46  46 
List.exists ExprDep.is_instance_var (IdentDepGraph.succ g choice) 
47  47  
48  48 
(* Adds successors of [v] in graph [g] in [pending] or [frontier] sets, wrt [eq_equiv], 
49 
then removes [v] from [g]


49 
then removes [v] from [g] 

50  50 
*) 
51  51 
let add_successors eq_equiv g v pending frontier = 
52  52 
let succs_v = IdentDepGraph.succ g v in 
53  53 
begin 
54  54 
IdentDepGraph.remove_vertex g v; 
55 
List.iter


56 
(fun v' >


57 
if is_graph_root v' g then


58 
(if eq_equiv v v' then


59 
pending := ISet.add v' !pending


55 
List.iter 

56 
(fun v' > 

57 
if is_graph_root v' g then 

58 
(if eq_equiv v v' then 

59 
pending := ISet.add v' !pending 

60  60 
else 
61  61 
frontier := ISet.add v' !frontier) 
62  62 
) succs_v; 
...  ...  
134  134 
with Not_found > false in 
135  135  
136  136 
let n', g = global_dependency n in 
137 
Log.report ~level:5


138 
(fun fmt >


137 
Log.report ~level:5 

138 
(fun fmt > 

139  139 
Format.fprintf fmt 
140 
"dependency graph for node %s: %a"


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

141  141 
n'.node_id 
142  142 
pp_dep_graph g 
143  143 
); 
144 


144  
145  145 
(* TODO X: extend the graph with inputs (adapt the causality analysis to deal with inputs 
146  146 
compute: coi predecessors of outputs 
147  147 
warning (no modification) when memories are non used (do not impact output) or when inputs are not used (do not impact output) 
...  ...  
152  152 
let sort = topological_sort eq_equiv g in 
153  153 
let unused = Liveness.compute_unused_variables n gg in 
154  154 
let fanin = Liveness.compute_fanin n gg in 
155 


155  
156  156 
let (disjoint, reuse) = 
157  157 
if !Options.optimization >= 3 
158  158 
then 
...  ...  
166  166 
if !Options.print_reuse 
167  167 
then 
168  168 
begin 
169 
Log.report ~level:0


170 
(fun fmt >


169 
Log.report ~level:0 

170 
(fun fmt > 

171  171 
Format.fprintf fmt 
172  172 
"OPT:%B@." (try (Hashtbl.iter (fun s1 v2 > if s1 = v2.var_id then raise Not_found) reuse; false) with Not_found > true) 
173  173 
); 
174 
Log.report ~level:0


175 
(fun fmt >


174 
Log.report ~level:0 

175 
(fun fmt > 

176  176 
Format.fprintf fmt 
177 
"OPT:clock disjoint map for node %s: %a"


177 
"OPT:clock disjoint map for node %s: %a" 

178  178 
n'.node_id 
179  179 
Disjunction.pp_disjoint_map disjoint 
180  180 
); 
181 
Log.report ~level:0


182 
(fun fmt >


181 
Log.report ~level:0 

182 
(fun fmt > 

183  183 
Format.fprintf fmt 
184 
"OPT:reuse policy for node %s: %a"


184 
"OPT:reuse policy for node %s: %a" 

185  185 
n'.node_id 
186  186 
Liveness.pp_reuse_policy reuse 
187  187 
); 
...  ...  
196  196 
List.fold_right ( 
197  197 
fun top_decl (accu_prog, sch_map) > 
198  198 
match top_decl.top_decl_desc with 
199 
 Node nd >


199 
 Node nd > 

200  200 
let nd', report = schedule_node nd in 
201 
{top_decl with top_decl_desc = Node nd'}::accu_prog,


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

202  202 
IMap.add nd.node_id report sch_map 
203  203 
 _ > top_decl::accu_prog, sch_map 
204 
)


204 
) 

205  205 
prog 
206  206 
([],IMap.empty) 
207  207  
...  ...  
210  210 
 [] > assert false 
211  211 
 [v] > Format.fprintf fmt "%s" v 
212  212 
 _ > Format.fprintf fmt "(%a)" (fprintf_list ~sep:" , " (fun fmt v > Format.fprintf fmt "%s" v)) vl 
213 


213  
214  214 
let pp_schedule fmt node_schs = 
215  215 
IMap.iter 
216  216 
(fun nd report > 
Also available in: Unified diff