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
15 #include "irgraph_t.h"
17 #include "iredges_t.h"
19 #include "irphase_t.h"
24 #include "besched_t.h"
25 #include "beschedmris.h"
29 const arch_env_t *aenv;
34 struct list_head lineage_head;
36 DEBUG_ONLY(firm_dbg_module_t *dbg;)
39 typedef struct _mris_irn_t {
42 ir_node *lineage_start;
43 ir_node *lineage_next;
45 struct list_head lineage_list;
48 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
50 #define get_mris_irn(env, irn) ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
51 #define get_irn_height(env, irn) (get_mris_irn(env, irn)->height)
52 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
54 static void mris_irn_data_init(const phase_t *ph, const ir_node *irn, void *data)
56 mris_irn_t *mi = data;
57 memset(data, 0, sizeof(mi[0]));
58 INIT_LIST_HEAD(&mi->lineage_list);
61 static int compute_height(mris_env_t *env, ir_node *irn, unsigned long visited)
63 mris_irn_t *mi = get_mris_irn(env, irn);
65 if(get_irn_visited(irn) >= visited) {
66 DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
71 const ir_edge_t *edge;
73 set_irn_visited(irn, visited);
76 foreach_out_edge(irn, edge) {
77 ir_node *dep = get_edge_src_irn(edge);
79 if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
80 int dep_height = compute_height(env, dep, visited);
81 mi->height = MAX(mi->height, dep_height);
86 DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
92 static void compute_heights(mris_env_t *env)
94 const ir_edge_t *edge;
95 unsigned long visited;
97 visited = get_irg_visited(env->irg) + 1;
98 set_irg_visited(env->irg, visited);
100 foreach_out_edge(env->bl, edge) {
101 ir_node *dep = get_edge_src_irn(edge);
102 if(to_appear(env, dep))
103 compute_height(env, dep, visited);
107 #define valid_node(env, dep) (to_appear(env, dep) && !nodeset_find(env->inserted, dep) && !be_is_Keep(dep))
109 static void grow_all_descendands(mris_env_t *env, ir_node *irn, unsigned long visited)
111 const ir_edge_t *edge;
113 assert(get_irn_mode(irn) != mode_T);
115 foreach_out_edge(irn, edge) {
116 ir_node *desc = get_edge_src_irn(edge);
117 if(valid_node(env, desc) && get_irn_visited(desc) < visited) {
118 obstack_ptr_grow(&env->obst, desc);
119 set_irn_visited(desc, visited);
124 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
126 unsigned long visited;
127 const ir_edge_t *edge;
129 visited = get_irg_visited(env->irg) + 1;
130 set_irg_visited(env->irg, visited);
132 if(get_irn_mode(irn) == mode_T) {
133 foreach_out_edge(irn, edge) {
134 ir_node *desc = get_edge_src_irn(edge);
135 assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
136 grow_all_descendands(env, desc, visited);
141 grow_all_descendands(env, irn, visited);
143 obstack_ptr_grow(&env->obst, NULL);
144 return obstack_finish(&env->obst);
147 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
149 int lowest_index = 0;
150 int lowest_height = INT_MAX;
153 for(i = 0; in[i]; ++i) {
154 mris_irn_t *mi = get_mris_irn(env, in[i]);
155 if(mi->height < lowest_height) {
156 lowest_height = mi->height;
162 ir_node *tmp = in[0];
163 in[0] = in[lowest_index];
164 in[lowest_index] = tmp;
170 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited)
172 if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
174 set_irn_visited(irn, visited);
181 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
182 ir_node *op = get_irn_n(irn, i);
184 reaches_walker(env, op, tgt, found, visited);
190 static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
193 unsigned long visited = get_irg_visited(env->irg) + 1;
195 set_irg_visited(env->irg, visited);
196 reaches_walker(env, src, tgt, &found, visited);
200 static INLINE ir_node *skip_Projs(ir_node *irn)
202 return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
205 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
209 for(i = 0; in[i]; ++i) {
210 if(get_irn_mode(in[i]) == mode_T) {
211 const ir_edge_t *edge;
212 ir_node *proj = NULL;
213 ir_node *first = NULL;
215 foreach_out_edge(in[i], edge) {
216 ir_node *desc = get_edge_src_irn(edge);
218 first = first ? first : desc;
219 if(get_irn_mode(desc) == mode_M) {
225 proj = proj ? proj : first;
232 static void lineage_formation(mris_env_t *env)
234 firm_dbg_module_t *dbg = env->dbg;
235 nodeset *nodes = new_nodeset(128);
237 const ir_edge_t *edge;
239 foreach_out_edge(env->bl, edge) {
240 ir_node *irn = get_edge_src_irn(edge);
241 if(to_appear(env, irn))
242 nodeset_insert(nodes, irn);
245 compute_heights(env);
247 while(nodeset_count(nodes) > 0) {
250 ir_node *highest_node = NULL;
251 ir_node *lowest_desc = NULL;
254 int recompute_height = 0;
257 /* search the highest node which is not yet in a lineage. */
258 for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) {
259 mris_irn_t *inf = get_mris_irn(env, irn);
260 if(inf->height > curr_height) {
262 curr_height = inf->height;
266 assert(highest_node);
267 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env, highest_node)));
269 /* start a lineage beginning with highest_node. */
270 mi = get_mris_irn(env, highest_node);
271 mi->lineage_start = highest_node;
272 mi->lineage_next = NULL;
273 mi->lineage_end = NULL;
274 list_add(&mi->lineage_list, &env->lineage_head);
275 nodeset_remove(nodes, highest_node);
278 put all descendants in an array.
279 we also move the lowest descendant in front, so that the other nodes
280 are easily accessible as an array, too.
282 in = all_descendants(env, highest_node);
283 lowest_desc = put_lowest_in_front(env, in);
285 /* as long as the current highest node has still descendants */
287 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
288 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
289 mris_irn_t *start_mi = get_mris_irn(env, highest_mi->lineage_start);
290 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
294 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, mi->height));
296 /* count the number of all descendants which are not the lowest descendant */
297 for(n_desc = 0; in[n_desc + 1]; ++n_desc);
300 we insert a CopyKeep node to express the artificial dependencies from the lowest
301 descendant to all other descendants.
303 if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
304 const arch_register_class_t *cls;
305 ir_node *copy_keep, *op;
308 for(i = 0, n = get_irn_arity(lowest_desc); i < n; ++i) {
311 op = get_irn_n(lowest_desc, i);
312 cmp = highest_is_tuple ? skip_Projs(op) : op;
314 if(cmp == highest_node)
318 assert(i < n && "could not find operand");
320 cls = arch_get_irn_reg_class(env->aenv, op, BE_OUT_POS(0));
321 replace_tuple_by_repr_proj(env, &in[1]);
322 copy_keep = be_new_CopyKeep(cls, env->irg, env->bl, op, n_desc, &in[1], get_irn_mode(op));
323 set_irn_n(lowest_desc, i, copy_keep);
324 nodeset_insert(env->inserted, copy_keep);
326 obstack_free(&env->obst, in);
328 /* mark the current lowest node as the last one in the lineage. */
329 highest_mi->lineage_next = lowest_desc;
330 start_mi->lineage_end = lowest_desc;
332 /* if the current lowest node is not yet in a lineage, add it to the current one. */
333 if(!lowest_mi->lineage_start) {
334 lowest_mi->lineage_start = highest_mi->lineage_start;
335 nodeset_remove(nodes, lowest_desc);
338 /* else we cannot extend this lineage, so break. */
342 highest_node = lowest_desc;
343 highest_mi = lowest_mi;
345 /* recompute the descendants array and the new lowest descendant. */
346 in = all_descendants(env, highest_node);
347 lowest_desc = put_lowest_in_front(env, in);
350 /* recompute the heights if desired. */
352 compute_heights(env);
356 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
360 ir_node *irn, *last, *copy;
361 ir_node *u_end = u->lineage_end;
362 ir_node *v_start = v->lineage_start;
363 ir_node *start = skip_Projs(v_start);
365 if(be_is_Keep(start))
368 /* set lineage end of nodes in u to end of v. */
369 irn = last = u->lineage_start;
370 mi = get_mris_irn(env, irn);
371 while(irn != u_end) {
372 mi = get_mris_irn(env, irn);
373 mi->lineage_end = v->lineage_end;
375 irn = mi->lineage_next;
378 /* insert a CopyKeep to make lineage v dependent on u. */
380 const arch_register_class_t *cls;
383 if(get_irn_arity(start) == 0)
386 op = get_irn_n(start, 0);
388 cls = arch_get_irn_reg_class(env->aenv, op, BE_OUT_POS(0));
389 if(get_irn_mode(last) == mode_T) {
390 const ir_edge_t *edge;
391 foreach_out_edge(last, edge) {
392 last = get_edge_src_irn(edge);
396 copy = be_new_CopyKeep_single(cls, env->irg, env->bl, op, last, get_irn_mode(op));
397 set_irn_n(start, 0, copy);
398 copy_mi = get_mris_irn(env, copy);
399 nodeset_insert(env->inserted, copy);
402 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
403 mi->lineage_next = copy;
404 copy_mi->lineage_start = u->lineage_start;
405 copy_mi->lineage_end = v->lineage_end;
406 copy_mi->lineage_next = v_start;
408 /* set lineage start of nodes in v to start of u. */
409 irn = v->lineage_start;
410 while(irn != v->lineage_end) {
411 mris_irn_t *mi = get_mris_irn(env, irn);
412 mi->lineage_start = u->lineage_start;
413 irn = mi->lineage_next;
416 mi = get_mris_irn(env, v_start);
417 list_del(&mi->lineage_list);
422 static void fuse_lineages(mris_env_t *env)
425 mris_irn_t *u, *v, *tmp1, *tmp2;
428 foreach_lineage(env, u, tmp1) {
429 foreach_lineage(env, v, tmp2) {
433 if(!reaches(env, u->lineage_start, v->lineage_end) && reaches(env, v->lineage_start, u->lineage_end)) {
434 if(fuse_two_lineages(env, u, v))
441 static void block_walker(ir_node *bl, void *data)
443 mris_env_t *env = data;
445 lineage_formation(env);
450 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
452 mris_env_t *env = xmalloc(sizeof(env[0]));
454 phase_init(&env->ph, "mris", birg->irg, sizeof(mris_irn_t), 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init);
455 env->aenv = birg->main_env->arch_env;
456 env->irg = birg->irg;
458 env->inserted = new_nodeset(128);
459 INIT_LIST_HEAD(&env->lineage_head);
460 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
461 obstack_init(&env->obst);
462 irg_walk_graph(env->irg, firm_clear_link, NULL, NULL);
463 irg_block_walk_graph(birg->irg, block_walker, NULL, env);
464 obstack_free(&env->obst, NULL);
468 static void cleanup_inserted(mris_env_t *env)
472 foreach_nodeset(env->inserted, irn) {
476 assert(be_is_CopyKeep(irn));
477 tgt = get_irn_n(irn, be_pos_CopyKeep_op);
479 /* reroute the edges, remove from schedule and make it invisible. */
480 edges_reroute(irn, tgt, env->irg);
481 if (sched_is_scheduled(irn))
483 for(i = -1, n = get_irn_arity(irn); i < n; ++i)
484 set_irn_n(irn, i, new_r_Bad(env->irg));
488 void be_sched_mris_free(mris_env_t *env)
490 cleanup_inserted(env);
491 phase_free(&env->ph);
492 del_nodeset(env->inserted);