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"
26 #include "besched_t.h"
27 #include "beschedmris.h"
32 const arch_env_t *aenv;
37 struct list_head lineage_head;
39 DEBUG_ONLY(firm_dbg_module_t *dbg;)
42 typedef struct _mris_irn_t {
44 ir_node *lineage_start;
45 ir_node *lineage_next;
47 struct list_head lineage_list;
50 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
52 #define get_mris_irn(env, irn) ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
53 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
55 static void mris_irn_data_init(phase_t *ph, const ir_node *irn, void *data)
57 mris_irn_t *mi = data;
58 memset(data, 0, sizeof(mi[0]));
59 INIT_LIST_HEAD(&mi->lineage_list);
63 static int compute_height(mris_env_t *env, ir_node *irn, unsigned long visited)
65 mris_irn_t *mi = get_mris_irn(env, irn);
67 if(get_irn_visited(irn) >= visited) {
68 DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
73 const ir_edge_t *edge;
75 set_irn_visited(irn, visited);
78 foreach_out_edge(irn, edge) {
79 ir_node *dep = get_edge_src_irn(edge);
81 if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
82 int dep_height = compute_height(env, dep, visited);
83 mi->height = MAX(mi->height, dep_height);
88 DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
94 static void compute_heights(mris_env_t *env)
96 const ir_edge_t *edge;
97 unsigned long visited;
99 visited = get_irg_visited(env->irg) + 1;
100 set_irg_visited(env->irg, visited);
102 foreach_out_edge(env->bl, edge) {
103 ir_node *dep = get_edge_src_irn(edge);
104 if(to_appear(env, dep))
105 compute_height(env, dep, visited);
110 #define valid_node(env, dep) (to_appear(env, dep) && !nodeset_find(env->inserted, dep) && !be_is_Keep(dep))
112 static void grow_all_descendands(mris_env_t *env, ir_node *irn, unsigned long visited)
114 const ir_edge_t *edge;
116 assert(get_irn_mode(irn) != mode_T);
118 foreach_out_edge(irn, edge) {
119 ir_node *desc = get_edge_src_irn(edge);
120 if(valid_node(env, desc) && get_irn_visited(desc) < visited) {
121 obstack_ptr_grow(&env->obst, desc);
122 set_irn_visited(desc, visited);
127 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
129 unsigned long visited;
130 const ir_edge_t *edge;
132 visited = get_irg_visited(env->irg) + 1;
133 set_irg_visited(env->irg, visited);
135 if(get_irn_mode(irn) == mode_T) {
136 foreach_out_edge(irn, edge) {
137 ir_node *desc = get_edge_src_irn(edge);
138 assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
139 grow_all_descendands(env, desc, visited);
144 grow_all_descendands(env, irn, visited);
146 obstack_ptr_grow(&env->obst, NULL);
147 return obstack_finish(&env->obst);
150 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
152 int lowest_index = 0;
153 unsigned lowest_height = INT_MAX;
156 for(i = 0; in[i]; ++i) {
157 unsigned height = get_irn_height(env->heights, in[i]);
158 if(height < lowest_height) {
159 lowest_height = height;
165 ir_node *tmp = in[0];
166 in[0] = in[lowest_index];
167 in[lowest_index] = tmp;
174 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited)
176 if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
178 set_irn_visited(irn, visited);
185 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
186 ir_node *op = get_irn_n(irn, i);
188 reaches_walker(env, op, tgt, found, visited);
194 static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
197 unsigned long visited = get_irg_visited(env->irg) + 1;
199 set_irg_visited(env->irg, visited);
200 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 while(nodeset_count(nodes) > 0) {
253 ir_node *highest_node = NULL;
254 ir_node *lowest_desc = NULL;
257 int recompute_height = 0;
258 unsigned curr_height = 0;
260 /* search the highest node which is not yet in a lineage. */
261 for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) {
262 unsigned height = get_irn_height(env->heights, irn);
263 if(height > curr_height) {
265 curr_height = height;
269 assert(highest_node);
270 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
272 /* start a lineage beginning with highest_node. */
273 mi = get_mris_irn(env, highest_node);
274 mi->lineage_start = highest_node;
275 mi->lineage_next = NULL;
276 mi->lineage_end = NULL;
277 list_add(&mi->lineage_list, &env->lineage_head);
278 nodeset_remove(nodes, highest_node);
281 put all descendants in an array.
282 we also move the lowest descendant in front, so that the other nodes
283 are easily accessible as an array, too.
285 in = all_descendants(env, highest_node);
286 lowest_desc = put_lowest_in_front(env, in);
288 /* as long as the current highest node has still descendants */
290 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
291 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
292 mris_irn_t *start_mi = get_mris_irn(env, highest_mi->lineage_start);
293 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
297 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
299 /* count the number of all descendants which are not the lowest descendant */
300 for(n_desc = 0; in[n_desc + 1]; ++n_desc);
303 we insert a CopyKeep node to express the artificial dependencies from the lowest
304 descendant to all other descendants.
306 if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
307 const arch_register_class_t *cls;
308 ir_node *copy_keep, *op;
311 for(i = 0, n = get_irn_arity(lowest_desc); i < n; ++i) {
314 op = get_irn_n(lowest_desc, i);
315 cmp = highest_is_tuple ? skip_Projs(op) : op;
317 if(cmp == highest_node)
321 assert(i < n && "could not find operand");
323 cls = arch_get_irn_reg_class(env->aenv, op, BE_OUT_POS(0));
324 replace_tuple_by_repr_proj(env, &in[1]);
325 copy_keep = be_new_CopyKeep(cls, env->irg, env->bl, op, n_desc, &in[1], get_irn_mode(op));
326 set_irn_n(lowest_desc, i, copy_keep);
327 nodeset_insert(env->inserted, copy_keep);
329 obstack_free(&env->obst, in);
331 /* mark the current lowest node as the last one in the lineage. */
332 highest_mi->lineage_next = lowest_desc;
333 start_mi->lineage_end = lowest_desc;
335 /* if the current lowest node is not yet in a lineage, add it to the current one. */
336 if(!lowest_mi->lineage_start) {
337 lowest_mi->lineage_start = highest_mi->lineage_start;
338 nodeset_remove(nodes, lowest_desc);
341 /* else we cannot extend this lineage, so break. */
345 highest_node = lowest_desc;
346 highest_mi = lowest_mi;
348 /* recompute the descendants array and the new lowest descendant. */
349 in = all_descendants(env, highest_node);
350 lowest_desc = put_lowest_in_front(env, in);
353 /* recompute the heights if desired. */
355 heights_recompute(env->heights);
359 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
363 ir_node *irn, *last, *copy;
364 ir_node *u_end = u->lineage_end;
365 ir_node *v_start = v->lineage_start;
366 ir_node *start = skip_Projs(v_start);
368 if(be_is_Keep(start))
371 /* set lineage end of nodes in u to end of v. */
372 irn = last = u->lineage_start;
373 mi = get_mris_irn(env, irn);
374 while(irn && irn != u_end) {
375 mi = get_mris_irn(env, irn);
376 mi->lineage_end = v->lineage_end;
378 irn = mi->lineage_next;
381 /* insert a CopyKeep to make lineage v dependent on u. */
383 const arch_register_class_t *cls;
386 if(get_irn_arity(start) == 0)
389 op = get_irn_n(start, 0);
391 cls = arch_get_irn_reg_class(env->aenv, op, BE_OUT_POS(0));
392 if(get_irn_mode(last) == mode_T) {
393 const ir_edge_t *edge;
394 foreach_out_edge(last, edge) {
395 last = get_edge_src_irn(edge);
399 copy = be_new_CopyKeep_single(cls, env->irg, env->bl, op, last, get_irn_mode(op));
400 set_irn_n(start, 0, copy);
401 copy_mi = get_mris_irn(env, copy);
402 nodeset_insert(env->inserted, copy);
405 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
406 mi->lineage_next = copy;
407 copy_mi->lineage_start = u->lineage_start;
408 copy_mi->lineage_end = v->lineage_end;
409 copy_mi->lineage_next = v_start;
411 /* set lineage start of nodes in v to start of u. */
412 irn = v->lineage_start;
413 while(irn && irn != v->lineage_end) {
414 mris_irn_t *mi = get_mris_irn(env, irn);
415 mi->lineage_start = u->lineage_start;
416 irn = mi->lineage_next;
419 heights_recompute(env->heights);
421 mi = get_mris_irn(env, v_start);
422 list_del(&mi->lineage_list);
427 static void fuse_lineages(mris_env_t *env)
430 mris_irn_t *u, *v, *tmp1, *tmp2;
433 foreach_lineage(env, u, tmp1) {
434 foreach_lineage(env, v, tmp2) {
435 if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
436 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
437 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
438 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
441 if(fuse_two_lineages(env, u, v))
449 static void block_walker(ir_node *bl, void *data)
451 mris_env_t *env = data;
453 lineage_formation(env);
458 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
460 mris_env_t *env = xmalloc(sizeof(env[0]));
462 phase_init(&env->ph, "mris", birg->irg, sizeof(mris_irn_t), 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init);
463 env->aenv = birg->main_env->arch_env;
464 env->irg = birg->irg;
466 env->inserted = new_nodeset(128);
467 env->heights = heights_new(birg->irg);
468 INIT_LIST_HEAD(&env->lineage_head);
469 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
470 obstack_init(&env->obst);
471 irg_walk_graph(env->irg, firm_clear_link, NULL, NULL);
472 irg_block_walk_graph(birg->irg, block_walker, NULL, env);
473 obstack_free(&env->obst, NULL);
477 static void cleanup_inserted(mris_env_t *env)
481 foreach_nodeset(env->inserted, irn) {
485 assert(be_is_CopyKeep(irn));
486 tgt = get_irn_n(irn, be_pos_CopyKeep_op);
488 /* reroute the edges, remove from schedule and make it invisible. */
489 edges_reroute(irn, tgt, env->irg);
490 if (sched_is_scheduled(irn))
492 for(i = -1, n = get_irn_arity(irn); i < n; ++i)
493 set_irn_n(irn, i, new_r_Bad(env->irg));
497 void be_sched_mris_free(mris_env_t *env)
499 cleanup_inserted(env);
500 phase_free(&env->ph);
501 del_nodeset(env->inserted);
502 heights_free(env->heights);