2 * Implements a list scheduler for the MRIS algorithm in:
3 * Govindarajan, Yang, Amaral, Zhang, Gao
4 * Minimum Register Instruction Sequencing to Reduce Register Spills
5 * in out-of-order issue superscalar architectures
6 * @author Sebastian Hack
16 #include "irgraph_t.h"
18 #include "iredges_t.h"
24 #include "besched_t.h"
25 #include "beschedmris.h"
28 firm_dbg_module_t *dbg;
29 const arch_env_t *aenv;
34 struct list_head lineage_head;
38 typedef struct _mris_irn_t {
41 ir_node *lineage_start;
42 ir_node *lineage_next;
44 struct list_head lineage_list;
47 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
49 #define get_irn_height(env, irn) (get_mris_irn(env, irn)->height)
50 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
52 static mris_irn_t *get_mris_irn(mris_env_t *env, ir_node *irn)
54 mris_irn_t *mi = get_irn_link(irn);
57 mi = obstack_alloc(&env->obst, sizeof(mi[0]));
58 memset(mi, 0, sizeof(mi[0]));
59 set_irn_link(irn, mi);
60 INIT_LIST_HEAD(&mi->lineage_list);
66 static int compute_height(mris_env_t *env, ir_node *irn, unsigned long visited)
68 mris_irn_t *mi = get_mris_irn(env, irn);
70 if(get_irn_visited(irn) >= visited) {
71 DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
76 const ir_edge_t *edge;
78 set_irn_visited(irn, visited);
81 foreach_out_edge(irn, edge) {
82 ir_node *dep = get_edge_src_irn(edge);
84 if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
85 int dep_height = compute_height(env, dep, visited);
86 mi->height = MAX(mi->height, dep_height);
91 DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
97 static void compute_heights(mris_env_t *env)
99 const ir_edge_t *edge;
100 unsigned long visited;
102 visited = get_irg_visited(env->irg) + 1;
103 set_irg_visited(env->irg, visited);
105 foreach_out_edge(env->bl, edge) {
106 ir_node *dep = get_edge_src_irn(edge);
107 if(to_appear(env, dep))
108 compute_height(env, dep, visited);
112 #define valid_node(env, dep) (to_appear(env, dep) && !nodeset_find(env->inserted, dep) && !be_is_Keep(dep))
114 static void grow_all_descendands(mris_env_t *env, ir_node *irn, unsigned long visited)
116 const ir_edge_t *edge;
118 assert(get_irn_mode(irn) != mode_T);
120 foreach_out_edge(irn, edge) {
121 ir_node *desc = get_edge_src_irn(edge);
122 if(valid_node(env, desc) && get_irn_visited(desc) < visited) {
123 obstack_ptr_grow(&env->obst, desc);
124 set_irn_visited(desc, visited);
129 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
131 unsigned long visited;
132 const ir_edge_t *edge;
134 visited = get_irg_visited(env->irg) + 1;
135 set_irg_visited(env->irg, visited);
137 if(get_irn_mode(irn) == mode_T) {
138 foreach_out_edge(irn, edge) {
139 ir_node *desc = get_edge_src_irn(edge);
140 assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
141 grow_all_descendands(env, desc, visited);
146 grow_all_descendands(env, irn, visited);
148 obstack_ptr_grow(&env->obst, NULL);
149 return obstack_finish(&env->obst);
152 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
154 int lowest_index = 0;
155 int lowest_height = INT_MAX;
158 for(i = 0; in[i]; ++i) {
159 mris_irn_t *mi = get_mris_irn(env, in[i]);
160 if(mi->height < lowest_height) {
161 lowest_height = mi->height;
167 ir_node *tmp = in[0];
168 in[0] = in[lowest_index];
169 in[lowest_index] = tmp;
175 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited)
177 if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
179 set_irn_visited(irn, visited);
186 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
187 ir_node *op = get_irn_n(irn, i);
189 reaches_walker(env, op, tgt, found, visited);
195 static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
198 unsigned long visited = get_irg_visited(env->irg) + 1;
200 set_irg_visited(env->irg, visited);
201 reaches_walker(env, src, tgt, &found, visited);
205 static INLINE ir_node *skip_Projs(ir_node *irn)
207 return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
210 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
214 for(i = 0; in[i]; ++i) {
215 if(get_irn_mode(in[i]) == mode_T) {
216 const ir_edge_t *edge;
217 ir_node *proj = NULL;
218 ir_node *first = NULL;
220 foreach_out_edge(in[i], edge) {
221 ir_node *desc = get_edge_src_irn(edge);
223 first = first ? first : desc;
224 if(get_irn_mode(desc) == mode_M) {
230 proj = proj ? proj : first;
237 static void lineage_formation(mris_env_t *env)
239 firm_dbg_module_t *dbg = env->dbg;
240 nodeset *nodes = new_nodeset(128);
242 const ir_edge_t *edge;
244 foreach_out_edge(env->bl, edge) {
245 ir_node *irn = get_edge_src_irn(edge);
246 if(to_appear(env, irn))
247 nodeset_insert(nodes, irn);
250 compute_heights(env);
252 while(nodeset_count(nodes) > 0) {
255 ir_node *highest_node = NULL;
256 ir_node *lowest_desc = NULL;
259 int recompute_height = 0;
262 /* search the highest node which is not yet in a lineage. */
263 for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) {
264 mris_irn_t *inf = get_mris_irn(env, irn);
265 if(inf->height > curr_height) {
267 curr_height = inf->height;
271 assert(highest_node);
272 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env, highest_node)));
274 /* start a lineage beginning with highest_node. */
275 mi = get_mris_irn(env, highest_node);
276 mi->lineage_start = highest_node;
277 mi->lineage_next = NULL;
278 mi->lineage_end = NULL;
279 list_add(&mi->lineage_list, &env->lineage_head);
280 nodeset_remove(nodes, highest_node);
283 put all descendants in an array.
284 we also move the lowest descendant in front, so that the other nodes
285 are easily accessible as an array, too.
287 in = all_descendants(env, highest_node);
288 lowest_desc = put_lowest_in_front(env, in);
290 /* as long as the current highest node has still descendants */
292 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
293 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
294 mris_irn_t *start_mi = get_mris_irn(env, highest_mi->lineage_start);
295 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
299 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, mi->height));
301 /* count the number of all descendants which are not the lowest descendant */
302 for(n_desc = 0; in[n_desc + 1]; ++n_desc);
305 we insert a CopyKeep node to express the artificial dependencies from the lowest
306 descendant to all other descendants.
308 if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
309 const arch_register_class_t *cls;
310 ir_node *copy_keep, *op;
313 for(i = 0, n = get_irn_arity(lowest_desc); i < n; ++i) {
316 op = get_irn_n(lowest_desc, i);
317 cmp = highest_is_tuple ? skip_Projs(op) : op;
319 if(cmp == highest_node)
323 assert(i < n && "could not find operand");
325 cls = arch_get_irn_reg_class(env->aenv, op, BE_OUT_POS(0));
326 replace_tuple_by_repr_proj(env, &in[1]);
327 copy_keep = be_new_CopyKeep(cls, env->irg, env->bl, op, n_desc, &in[1], get_irn_mode(op));
328 set_irn_n(lowest_desc, i, copy_keep);
329 nodeset_insert(env->inserted, copy_keep);
331 obstack_free(&env->obst, in);
333 /* mark the current lowest node as the last one in the lineage. */
334 highest_mi->lineage_next = lowest_desc;
335 start_mi->lineage_end = lowest_desc;
337 /* if the current lowest node is not yet in a lineage, add it to the current one. */
338 if(!lowest_mi->lineage_start) {
339 lowest_mi->lineage_start = highest_mi->lineage_start;
340 nodeset_remove(nodes, lowest_desc);
343 /* else we cannot extend this lineage, so break. */
347 highest_node = lowest_desc;
348 highest_mi = lowest_mi;
350 /* recompute the descendants array and the new lowest descendant. */
351 in = all_descendants(env, highest_node);
352 lowest_desc = put_lowest_in_front(env, in);
355 /* recompute the heights if desired. */
357 compute_heights(env);
361 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
365 ir_node *irn, *last, *copy;
366 ir_node *u_end = u->lineage_end;
367 ir_node *v_start = v->lineage_start;
368 ir_node *start = skip_Projs(v_start);
370 if(be_is_Keep(start))
373 /* set lineage end of nodes in u to end of v. */
374 irn = last = u->lineage_start;
375 mi = get_mris_irn(env, irn);
376 while(irn != u_end) {
377 mi = get_mris_irn(env, irn);
378 mi->lineage_end = v->lineage_end;
380 irn = mi->lineage_next;
383 /* insert a CopyKeep to make lineage v dependent on u. */
385 const arch_register_class_t *cls;
389 if(get_irn_arity(start) == 0)
392 op = get_irn_n(start, 0);
394 cls = arch_get_irn_reg_class(env->aenv, op, BE_OUT_POS(0));
395 if(get_irn_mode(last) == mode_T) {
396 const ir_edge_t *edge;
397 foreach_out_edge(last, edge) {
398 last = get_edge_src_irn(edge);
402 copy = be_new_CopyKeep_single(cls, env->irg, env->bl, op, last, get_irn_mode(op));
403 set_irn_n(start, 0, copy);
404 copy_mi = get_mris_irn(env, copy);
405 nodeset_insert(env->inserted, copy);
408 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
409 mi->lineage_next = copy;
410 copy_mi->lineage_start = u->lineage_start;
411 copy_mi->lineage_end = v->lineage_end;
412 copy_mi->lineage_next = v_start;
414 /* set lineage start of nodes in v to start of u. */
415 irn = v->lineage_start;
416 while(irn != v->lineage_end) {
417 mris_irn_t *mi = get_mris_irn(env, irn);
418 mi->lineage_start = u->lineage_start;
419 irn = mi->lineage_next;
422 mi = get_mris_irn(env, v_start);
423 list_del(&mi->lineage_list);
428 static void fuse_lineages(mris_env_t *env)
431 mris_irn_t *u, *v, *tmp1, *tmp2;
434 foreach_lineage(env, u, tmp1) {
435 foreach_lineage(env, v, tmp2) {
439 if(!reaches(env, u->lineage_start, v->lineage_end) && reaches(env, v->lineage_start, u->lineage_end)) {
440 if(fuse_two_lineages(env, u, v))
447 static void block_walker(ir_node *bl, void *data)
449 mris_env_t *env = data;
451 lineage_formation(env);
456 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
458 mris_env_t *env = xmalloc(sizeof(env[0]));
460 env->aenv = birg->main_env->arch_env;
461 env->irg = birg->irg;
463 env->inserted = new_nodeset(128);
464 INIT_LIST_HEAD(&env->lineage_head);
465 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
466 obstack_init(&env->obst);
467 irg_walk_graph(env->irg, firm_clear_link, NULL, NULL);
468 irg_block_walk_graph(birg->irg, block_walker, NULL, env);
469 obstack_free(&env->obst, NULL);
473 static void cleanup_inserted(mris_env_t *env)
477 for(irn = nodeset_first(env->inserted); irn; irn = nodeset_next(env->inserted)) {
481 assert(be_is_CopyKeep(irn));
482 tgt = get_irn_n(irn, be_pos_CopyKeep_op);
484 /* reroute the edges, remove from schedule and make it invisible. */
485 edges_reroute(irn, tgt, env->irg);
487 for(i = -1, n = get_irn_arity(irn); i < n; ++i)
488 set_irn_n(irn, i, new_r_Bad(env->irg));
492 void be_sched_mris_free(mris_env_t *env)
494 cleanup_inserted(env);
495 del_nodeset(env->inserted);