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
18 #include "irgraph_t.h"
20 #include "iredges_t.h"
22 #include "irphase_t.h"
29 #include "besched_t.h"
30 #include "beschedmris.h"
35 const arch_env_t *aenv;
40 struct list_head lineage_head;
42 DEBUG_ONLY(firm_dbg_module_t *dbg;)
45 typedef struct _mris_irn_t {
47 ir_node *lineage_start;
48 ir_node *lineage_next;
50 struct list_head lineage_list;
53 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
55 #define get_mris_irn(env, irn) ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
56 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
58 static void *mris_irn_data_init(phase_t *ph, ir_node *irn, void *data)
60 mris_irn_t *mi = data ? data : phase_alloc(ph, sizeof(mi[0]));
61 memset(mi, 0, sizeof(mi[0]));
62 INIT_LIST_HEAD(&mi->lineage_list);
67 static int compute_height(mris_env_t *env, ir_node *irn, unsigned long visited)
69 mris_irn_t *mi = get_mris_irn(env, irn);
71 if(get_irn_visited(irn) >= visited) {
72 DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
77 const ir_edge_t *edge;
79 set_irn_visited(irn, visited);
82 foreach_out_edge(irn, edge) {
83 ir_node *dep = get_edge_src_irn(edge);
85 if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
86 int dep_height = compute_height(env, dep, visited);
87 mi->height = MAX(mi->height, dep_height);
92 DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
98 static void compute_heights(mris_env_t *env)
100 const ir_edge_t *edge;
101 unsigned long visited;
103 visited = get_irg_visited(env->irg) + 1;
104 set_irg_visited(env->irg, visited);
106 foreach_out_edge(env->bl, edge) {
107 ir_node *dep = get_edge_src_irn(edge);
108 if(to_appear(env, dep))
109 compute_height(env, dep, visited);
114 #define valid_node(env, dep) (to_appear(env, dep) && !nodeset_find(env->inserted, dep) && !be_is_Keep(dep))
116 static void grow_all_descendands(mris_env_t *env, ir_node *irn, unsigned long visited)
118 const ir_edge_t *edge;
120 assert(get_irn_mode(irn) != mode_T);
122 foreach_out_edge(irn, edge) {
123 ir_node *desc = get_edge_src_irn(edge);
124 if(valid_node(env, desc) && get_irn_visited(desc) < visited) {
125 obstack_ptr_grow(&env->obst, desc);
126 set_irn_visited(desc, visited);
131 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
133 unsigned long visited;
134 const ir_edge_t *edge;
136 visited = get_irg_visited(env->irg) + 1;
137 set_irg_visited(env->irg, visited);
139 if(get_irn_mode(irn) == mode_T) {
140 foreach_out_edge(irn, edge) {
141 ir_node *desc = get_edge_src_irn(edge);
142 assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
143 grow_all_descendands(env, desc, visited);
148 grow_all_descendands(env, irn, visited);
150 obstack_ptr_grow(&env->obst, NULL);
151 return obstack_finish(&env->obst);
154 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
156 int lowest_index = 0;
157 unsigned lowest_height = INT_MAX;
160 for(i = 0; in[i]; ++i) {
161 unsigned height = get_irn_height(env->heights, in[i]);
162 if(height < lowest_height) {
163 lowest_height = height;
169 ir_node *tmp = in[0];
170 in[0] = in[lowest_index];
171 in[lowest_index] = tmp;
178 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited)
180 if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
182 set_irn_visited(irn, visited);
189 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
190 ir_node *op = get_irn_n(irn, i);
192 reaches_walker(env, op, tgt, found, visited);
198 static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
201 unsigned long visited = get_irg_visited(env->irg) + 1;
203 set_irg_visited(env->irg, visited);
204 reaches_walker(env, src, tgt, &found, visited);
209 static INLINE ir_node *skip_Projs(ir_node *irn)
211 return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
214 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
218 for(i = 0; in[i]; ++i) {
219 if(get_irn_mode(in[i]) == mode_T) {
220 const ir_edge_t *edge;
221 ir_node *proj = NULL;
222 ir_node *first = NULL;
224 foreach_out_edge(in[i], edge) {
225 ir_node *desc = get_edge_src_irn(edge);
227 first = first ? first : desc;
228 if(get_irn_mode(desc) == mode_M) {
234 proj = proj ? proj : first;
241 static void lineage_formation(mris_env_t *env)
243 firm_dbg_module_t *dbg = env->dbg;
244 nodeset *nodes = new_nodeset(128);
246 const ir_edge_t *edge;
248 foreach_out_edge(env->bl, edge) {
249 ir_node *irn = get_edge_src_irn(edge);
250 if(to_appear(env, irn))
251 nodeset_insert(nodes, irn);
254 while(nodeset_count(nodes) > 0) {
257 ir_node *highest_node = NULL;
258 ir_node *lowest_desc = NULL;
261 int recompute_height = 0;
262 unsigned curr_height = 0;
264 /* search the highest node which is not yet in a lineage. */
265 for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) {
266 unsigned height = get_irn_height(env->heights, irn);
267 if(height > curr_height) {
269 curr_height = height;
273 assert(highest_node);
274 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
276 /* start a lineage beginning with highest_node. */
277 mi = get_mris_irn(env, highest_node);
278 mi->lineage_start = highest_node;
279 mi->lineage_next = NULL;
280 mi->lineage_end = NULL;
281 list_add(&mi->lineage_list, &env->lineage_head);
282 nodeset_remove(nodes, highest_node);
285 put all descendants in an array.
286 we also move the lowest descendant in front, so that the other nodes
287 are easily accessible as an array, too.
289 in = all_descendants(env, highest_node);
290 lowest_desc = put_lowest_in_front(env, in);
292 /* as long as the current highest node has still descendants */
294 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
295 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
296 mris_irn_t *start_mi = get_mris_irn(env, highest_mi->lineage_start);
297 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
301 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
303 /* count the number of all descendants which are not the lowest descendant */
304 for(n_desc = 0; in[n_desc + 1]; ++n_desc);
307 we insert a CopyKeep node to express the artificial dependencies from the lowest
308 descendant to all other descendants.
310 if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
311 const arch_register_class_t *cls;
312 ir_node *copy_keep, *op;
315 for(i = 0, n = get_irn_arity(lowest_desc); i < n; ++i) {
318 op = get_irn_n(lowest_desc, i);
319 cmp = highest_is_tuple ? skip_Projs(op) : op;
321 if(cmp == highest_node)
325 assert(i < n && "could not find operand");
327 cls = arch_get_irn_reg_class(env->aenv, op, BE_OUT_POS(0));
328 replace_tuple_by_repr_proj(env, &in[1]);
329 copy_keep = be_new_CopyKeep(cls, env->irg, env->bl, op, n_desc, &in[1], get_irn_mode(op));
330 set_irn_n(lowest_desc, i, copy_keep);
331 nodeset_insert(env->inserted, copy_keep);
333 obstack_free(&env->obst, in);
335 /* mark the current lowest node as the last one in the lineage. */
336 highest_mi->lineage_next = lowest_desc;
337 start_mi->lineage_end = lowest_desc;
339 /* if the current lowest node is not yet in a lineage, add it to the current one. */
340 if(!lowest_mi->lineage_start) {
341 lowest_mi->lineage_start = highest_mi->lineage_start;
342 nodeset_remove(nodes, lowest_desc);
345 /* else we cannot extend this lineage, so break. */
349 highest_node = lowest_desc;
350 highest_mi = lowest_mi;
352 /* recompute the descendants array and the new lowest descendant. */
353 in = all_descendants(env, highest_node);
354 lowest_desc = put_lowest_in_front(env, in);
357 /* recompute the heights if desired. */
359 heights_recompute(env->heights);
363 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
367 ir_node *irn, *last, *copy;
368 ir_node *u_end = u->lineage_end;
369 ir_node *v_start = v->lineage_start;
370 ir_node *start = skip_Projs(v_start);
372 if(be_is_Keep(start))
375 /* set lineage end of nodes in u to end of v. */
376 irn = last = u->lineage_start;
377 mi = get_mris_irn(env, irn);
378 while(irn && irn != u_end) {
379 mi = get_mris_irn(env, irn);
380 mi->lineage_end = v->lineage_end;
382 irn = mi->lineage_next;
385 /* insert a CopyKeep to make lineage v dependent on u. */
387 const arch_register_class_t *cls;
390 if(get_irn_arity(start) == 0)
393 op = get_irn_n(start, 0);
395 cls = arch_get_irn_reg_class(env->aenv, op, BE_OUT_POS(0));
396 if(get_irn_mode(last) == mode_T) {
397 const ir_edge_t *edge;
398 foreach_out_edge(last, edge) {
399 last = get_edge_src_irn(edge);
403 copy = be_new_CopyKeep_single(cls, env->irg, env->bl, op, last, get_irn_mode(op));
404 set_irn_n(start, 0, copy);
405 copy_mi = get_mris_irn(env, copy);
406 nodeset_insert(env->inserted, copy);
409 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
410 mi->lineage_next = copy;
411 copy_mi->lineage_start = u->lineage_start;
412 copy_mi->lineage_end = v->lineage_end;
413 copy_mi->lineage_next = v_start;
415 /* set lineage start of nodes in v to start of u. */
416 irn = v->lineage_start;
417 while(irn && irn != v->lineage_end) {
418 mris_irn_t *mi = get_mris_irn(env, irn);
419 mi->lineage_start = u->lineage_start;
420 irn = mi->lineage_next;
423 heights_recompute(env->heights);
425 mi = get_mris_irn(env, v_start);
426 list_del(&mi->lineage_list);
431 static void fuse_lineages(mris_env_t *env)
433 mris_irn_t *u, *v, *tmp1, *tmp2;
436 foreach_lineage(env, u, tmp1) {
437 foreach_lineage(env, v, tmp2) {
438 if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
439 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
440 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
441 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
444 if(fuse_two_lineages(env, u, v))
452 static void block_walker(ir_node *bl, void *data)
454 mris_env_t *env = data;
456 lineage_formation(env);
457 //fuse_lineages(env);
461 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
463 mris_env_t *env = xmalloc(sizeof(env[0]));
465 phase_init(&env->ph, "mris", birg->irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init);
466 env->aenv = birg->main_env->arch_env;
467 env->irg = birg->irg;
469 env->inserted = new_nodeset(128);
470 env->heights = heights_new(birg->irg);
471 INIT_LIST_HEAD(&env->lineage_head);
472 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
473 obstack_init(&env->obst);
474 irg_walk_graph(env->irg, firm_clear_link, NULL, NULL);
475 irg_block_walk_graph(birg->irg, block_walker, NULL, env);
476 obstack_free(&env->obst, NULL);
480 static void cleanup_inserted(mris_env_t *env)
484 foreach_nodeset(env->inserted, irn) {
488 assert(be_is_CopyKeep(irn));
489 tgt = get_irn_n(irn, be_pos_CopyKeep_op);
491 /* reroute the edges, remove from schedule and make it invisible. */
492 edges_reroute(irn, tgt, env->irg);
493 if (sched_is_scheduled(irn))
495 for(i = -1, n = get_irn_arity(irn); i < n; ++i)
496 set_irn_n(irn, i, new_r_Bad(env->irg));
500 void be_sched_mris_free(mris_env_t *env)
502 cleanup_inserted(env);
503 phase_free(&env->ph);
504 del_nodeset(env->inserted);
505 heights_free(env->heights);