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"
31 #include "besched_t.h"
32 #include "beschedmris.h"
33 #include "benodesets.h"
38 const arch_env_t *aenv;
42 struct list_head lineage_head;
44 DEBUG_ONLY(firm_dbg_module_t *dbg;)
47 typedef struct _mris_irn_t {
49 ir_node *lineage_start;
50 ir_node *lineage_next;
52 struct list_head lineage_list;
55 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
57 #define get_mris_irn(env, irn) ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
58 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
60 static void *mris_irn_data_init(phase_t *ph, ir_node *irn, void *data)
62 mris_irn_t *mi = data ? data : phase_alloc(ph, sizeof(mi[0]));
63 memset(mi, 0, sizeof(mi[0]));
64 INIT_LIST_HEAD(&mi->lineage_list);
69 static int compute_height(mris_env_t *env, ir_node *irn, unsigned long visited)
71 mris_irn_t *mi = get_mris_irn(env, irn);
73 if(get_irn_visited(irn) >= visited) {
74 DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
79 const ir_edge_t *edge;
81 set_irn_visited(irn, visited);
84 foreach_out_edge(irn, edge) {
85 ir_node *dep = get_edge_src_irn(edge);
87 if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
88 int dep_height = compute_height(env, dep, visited);
89 mi->height = MAX(mi->height, dep_height);
94 DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
100 static void compute_heights(mris_env_t *env)
102 const ir_edge_t *edge;
103 unsigned long visited;
105 visited = get_irg_visited(env->irg) + 1;
106 set_irg_visited(env->irg, visited);
108 foreach_out_edge(env->bl, edge) {
109 ir_node *dep = get_edge_src_irn(edge);
110 if(to_appear(env, dep))
111 compute_height(env, dep, visited);
116 #define valid_node(env, dep) (to_appear(env, dep) && !be_is_Keep(dep))
118 static void grow_all_descendands(mris_env_t *env, ir_node *irn, bitset_t *visited)
120 const ir_edge_t *edge;
122 // assert(get_irn_mode(irn) != mode_T);
124 foreach_out_edge(irn, edge) {
125 ir_node *desc = get_edge_src_irn(edge);
126 if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
127 obstack_ptr_grow(&env->obst, desc);
128 bitset_add_irn(visited, desc);
132 foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
133 ir_node *desc = get_edge_src_irn(edge);
134 if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
135 obstack_ptr_grow(&env->obst, desc);
136 bitset_add_irn(visited, desc);
141 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
143 bitset_t *visited = bitset_irg_malloc(env->irg);
145 grow_all_descendands(env, irn, visited);
148 if(get_irn_mode(irn) == mode_T) {
149 const ir_edge_t *edge;
150 foreach_out_edge(irn, edge) {
151 ir_node *desc = get_edge_src_irn(edge);
152 assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
153 grow_all_descendands(env, desc, visited);
158 grow_all_descendands(env, irn, visited);
160 bitset_free(visited);
161 obstack_ptr_grow(&env->obst, NULL);
162 return obstack_finish(&env->obst);
165 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
167 int lowest_index = 0;
168 unsigned lowest_height = INT_MAX;
171 for(i = 0; in[i]; ++i) {
172 unsigned height = get_irn_height(env->heights, in[i]);
173 if(height < lowest_height) {
174 lowest_height = height;
180 ir_node *tmp = in[0];
181 in[0] = in[lowest_index];
182 in[lowest_index] = tmp;
189 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited)
191 if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
193 set_irn_visited(irn, visited);
200 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
201 ir_node *op = get_irn_n(irn, i);
203 reaches_walker(env, op, tgt, found, visited);
209 static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
212 unsigned long visited = get_irg_visited(env->irg) + 1;
214 set_irg_visited(env->irg, visited);
215 reaches_walker(env, src, tgt, &found, visited);
220 static INLINE ir_node *skip_Projs(ir_node *irn)
222 return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
226 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
230 for(i = 0; in[i]; ++i) {
231 if(get_irn_mode(in[i]) == mode_T) {
232 const ir_edge_t *edge;
233 ir_node *proj = NULL;
234 ir_node *first = NULL;
236 foreach_out_edge(in[i], edge) {
237 ir_node *desc = get_edge_src_irn(edge);
239 first = first ? first : desc;
240 if(get_irn_mode(desc) == mode_M) {
246 proj = proj ? proj : first;
254 static void lineage_formation(mris_env_t *env)
256 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg);
257 nodeset *nodes = new_nodeset(128);
259 const ir_edge_t *edge;
261 foreach_out_edge(env->bl, edge) {
262 ir_node *irn = get_edge_src_irn(edge);
263 if(to_appear(env, irn))
264 nodeset_insert(nodes, irn);
267 while(nodeset_count(nodes) > 0) {
270 ir_node *highest_node = NULL;
271 ir_node *lowest_desc = NULL;
273 mris_irn_t *start_mi;
276 int recompute_height = 0;
277 unsigned curr_height = 0;
279 /* search the highest node which is not yet in a lineage. */
280 for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) {
281 unsigned height = get_irn_height(env->heights, irn);
282 if(height > curr_height) {
284 curr_height = height;
288 assert(highest_node);
289 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
291 start = highest_node;
292 mi = start_mi = get_mris_irn(env, highest_node);
294 /* start a lineage beginning with highest_node. */
295 mi->lineage_start = highest_node;
296 mi->lineage_next = NULL;
297 mi->lineage_end = NULL;
298 list_add(&mi->lineage_list, &env->lineage_head);
299 nodeset_remove(nodes, highest_node);
302 put all descendants in an array.
303 we also move the lowest descendant in front, so that the other nodes
304 are easily accessible as an array, too.
306 in = all_descendants(env, highest_node);
307 lowest_desc = put_lowest_in_front(env, in);
309 /* as long as the current highest node has still descendants */
311 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
312 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
313 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
317 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
319 /* count the number of all descendants which are not the lowest descendant */
320 for(n_desc = 0; in[n_desc]; ++n_desc);
323 we insert a CopyKeep node to express the artificial dependencies from the lowest
324 descendant to all other descendants.
326 if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
330 for(i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
333 op = get_irn_in_or_dep(lowest_desc, i);
334 cmp = highest_is_tuple ? skip_Projs(op) : op;
336 // if(cmp == highest_node)
337 if(op == highest_node)
341 assert(i < n && "could not find operand");
343 //replace_tuple_by_repr_proj(env, &in[1]);
344 if(!is_Proj(lowest_desc))
345 add_irn_dep(lowest_desc, in[1]);
347 obstack_free(&env->obst, in);
349 /* if the current lowest node is not yet in a lineage, add it to the current one. */
350 if(!lowest_mi->lineage_start) {
351 /* mark the current lowest node as the last one in the lineage. */
352 highest_mi->lineage_next = lowest_desc;
353 start_mi->lineage_end = lowest_desc;
355 lowest_mi->lineage_start = start;
356 nodeset_remove(nodes, lowest_desc);
359 /* else we cannot extend this lineage, so break. */
363 highest_node = lowest_desc;
364 highest_mi = lowest_mi;
366 /* recompute the descendants array and the new lowest descendant. */
367 in = all_descendants(env, highest_node);
368 lowest_desc = put_lowest_in_front(env, in);
371 /* recompute the heights if desired. */
373 heights_recompute(env->heights);
377 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
381 ir_node *u_end = u->lineage_end;
382 ir_node *v_start = v->lineage_start;
383 ir_node *start = skip_Projs(v_start);
385 if(be_is_Keep(start))
388 /* set lineage end of nodes in u to end of v. */
389 irn = last = u->lineage_start;
390 mi = get_mris_irn(env, irn);
391 while(irn && irn != u_end) {
392 mi = get_mris_irn(env, irn);
393 mi->lineage_end = v->lineage_end;
395 irn = mi->lineage_next;
398 /* insert a CopyKeep to make lineage v dependent on u. */
399 if(get_irn_ins_or_deps(start) == 0)
402 if(get_irn_mode(last) == mode_T) {
403 const ir_edge_t *edge;
404 foreach_out_edge(last, edge) {
405 last = get_edge_src_irn(edge);
410 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
411 mi->lineage_next = v_start;
413 /* add a dependency from the first node in v's lineage to the last in u's */
414 add_irn_dep(u_end, v_start);
416 /* set lineage start of nodes in v to start of u. */
417 irn = v->lineage_start;
418 while(irn && irn != v->lineage_end) {
419 mris_irn_t *mi = get_mris_irn(env, irn);
420 mi->lineage_start = u->lineage_start;
421 irn = mi->lineage_next;
424 heights_recompute(env->heights);
426 mi = get_mris_irn(env, v_start);
427 list_del(&mi->lineage_list);
432 static void fuse_lineages(mris_env_t *env)
434 mris_irn_t *u, *v, *tmp1, *tmp2;
437 foreach_lineage(env, u, tmp1) {
438 foreach_lineage(env, v, tmp2) {
439 if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
440 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
441 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
442 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
445 if(fuse_two_lineages(env, u, v))
453 static mris_env_t *dump_env = NULL;
455 static void block_walker(ir_node *bl, void *data)
457 mris_env_t *env = data;
459 lineage_formation(env);
463 static int mris_edge_hook(FILE *F, ir_node *irn)
465 mris_irn_t *mi = get_mris_irn(dump_env, irn);
467 if(mi->lineage_next) {
468 fprintf(F, "edge:{sourcename:\"");
469 PRINT_NODEID(mi->lineage_next);
470 fprintf(F, "\" targetname:\"");
472 fprintf(F, "\" color:lilac}\n");
477 void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix) {
478 DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook();
480 dump_consts_local(0);
481 set_dump_node_edge_hook(mris_edge_hook);
483 dump_ir_block_graph(env->irg, suffix);
484 set_dump_node_edge_hook(old);
487 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
489 mris_env_t *env = xmalloc(sizeof(env[0]));
491 phase_init(&env->ph, "mris", birg->irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init);
492 env->aenv = birg->main_env->arch_env;
493 env->irg = birg->irg;
495 env->heights = heights_new(birg->irg);
496 INIT_LIST_HEAD(&env->lineage_head);
497 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
498 obstack_init(&env->obst);
499 irg_walk_graph(env->irg, firm_clear_link, NULL, NULL);
500 irg_block_walk_graph(birg->irg, block_walker, NULL, env);
501 obstack_free(&env->obst, NULL);
502 // dump_ir_block_graph_mris(env, "-mris");
506 void be_sched_mris_free(mris_env_t *env)
508 phase_free(&env->ph);
509 heights_free(env->heights);