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"
37 const arch_env_t *aenv;
41 struct list_head lineage_head;
43 DEBUG_ONLY(firm_dbg_module_t *dbg;)
46 typedef struct _mris_irn_t {
48 ir_node *lineage_start;
49 ir_node *lineage_next;
51 struct list_head lineage_list;
54 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
56 #define get_mris_irn(env, irn) ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
57 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
59 static void *mris_irn_data_init(phase_t *ph, ir_node *irn, void *data)
61 mris_irn_t *mi = data ? data : phase_alloc(ph, sizeof(mi[0]));
62 memset(mi, 0, sizeof(mi[0]));
63 INIT_LIST_HEAD(&mi->lineage_list);
68 static int compute_height(mris_env_t *env, ir_node *irn, unsigned long visited)
70 mris_irn_t *mi = get_mris_irn(env, irn);
72 if(get_irn_visited(irn) >= visited) {
73 DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
78 const ir_edge_t *edge;
80 set_irn_visited(irn, visited);
83 foreach_out_edge(irn, edge) {
84 ir_node *dep = get_edge_src_irn(edge);
86 if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
87 int dep_height = compute_height(env, dep, visited);
88 mi->height = MAX(mi->height, dep_height);
93 DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
99 static void compute_heights(mris_env_t *env)
101 const ir_edge_t *edge;
102 unsigned long visited;
104 visited = get_irg_visited(env->irg) + 1;
105 set_irg_visited(env->irg, visited);
107 foreach_out_edge(env->bl, edge) {
108 ir_node *dep = get_edge_src_irn(edge);
109 if(to_appear(env, dep))
110 compute_height(env, dep, visited);
115 #define valid_node(env, dep) (to_appear(env, dep) && !be_is_Keep(dep))
117 static void grow_all_descendands(mris_env_t *env, ir_node *irn, bitset_t *visited)
119 const ir_edge_t *edge;
121 // assert(get_irn_mode(irn) != mode_T);
123 foreach_out_edge(irn, edge) {
124 ir_node *desc = get_edge_src_irn(edge);
125 if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
126 obstack_ptr_grow(&env->obst, desc);
127 bitset_add_irn(visited, desc);
131 foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
132 ir_node *desc = get_edge_src_irn(edge);
133 if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
134 obstack_ptr_grow(&env->obst, desc);
135 bitset_add_irn(visited, desc);
140 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
142 bitset_t *visited = bitset_irg_malloc(env->irg);
144 grow_all_descendands(env, irn, visited);
147 if(get_irn_mode(irn) == mode_T) {
148 const ir_edge_t *edge;
149 foreach_out_edge(irn, edge) {
150 ir_node *desc = get_edge_src_irn(edge);
151 assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
152 grow_all_descendands(env, desc, visited);
157 grow_all_descendands(env, irn, visited);
159 bitset_free(visited);
160 obstack_ptr_grow(&env->obst, NULL);
161 return obstack_finish(&env->obst);
164 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
166 int lowest_index = 0;
167 unsigned lowest_height = INT_MAX;
170 for(i = 0; in[i]; ++i) {
171 unsigned height = get_irn_height(env->heights, in[i]);
172 if(height < lowest_height) {
173 lowest_height = height;
179 ir_node *tmp = in[0];
180 in[0] = in[lowest_index];
181 in[lowest_index] = tmp;
188 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited)
190 if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
192 set_irn_visited(irn, visited);
199 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
200 ir_node *op = get_irn_n(irn, i);
202 reaches_walker(env, op, tgt, found, visited);
208 static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
211 unsigned long visited = get_irg_visited(env->irg) + 1;
213 set_irg_visited(env->irg, visited);
214 reaches_walker(env, src, tgt, &found, visited);
219 static INLINE ir_node *skip_Projs(ir_node *irn)
221 return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
225 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
229 for(i = 0; in[i]; ++i) {
230 if(get_irn_mode(in[i]) == mode_T) {
231 const ir_edge_t *edge;
232 ir_node *proj = NULL;
233 ir_node *first = NULL;
235 foreach_out_edge(in[i], edge) {
236 ir_node *desc = get_edge_src_irn(edge);
238 first = first ? first : desc;
239 if(get_irn_mode(desc) == mode_M) {
245 proj = proj ? proj : first;
253 static void lineage_formation(mris_env_t *env)
255 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg);
256 nodeset *nodes = new_nodeset(128);
258 const ir_edge_t *edge;
260 foreach_out_edge(env->bl, edge) {
261 ir_node *irn = get_edge_src_irn(edge);
262 if(to_appear(env, irn))
263 nodeset_insert(nodes, irn);
266 while(nodeset_count(nodes) > 0) {
269 ir_node *highest_node = NULL;
270 ir_node *lowest_desc = NULL;
272 mris_irn_t *start_mi;
275 int recompute_height = 0;
276 unsigned curr_height = 0;
278 /* search the highest node which is not yet in a lineage. */
279 for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) {
280 unsigned height = get_irn_height(env->heights, irn);
281 if(height > curr_height) {
283 curr_height = height;
287 assert(highest_node);
288 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
290 start = highest_node;
291 mi = start_mi = get_mris_irn(env, highest_node);
293 /* start a lineage beginning with highest_node. */
294 mi->lineage_start = highest_node;
295 mi->lineage_next = NULL;
296 mi->lineage_end = NULL;
297 list_add(&mi->lineage_list, &env->lineage_head);
298 nodeset_remove(nodes, highest_node);
301 put all descendants in an array.
302 we also move the lowest descendant in front, so that the other nodes
303 are easily accessible as an array, too.
305 in = all_descendants(env, highest_node);
306 lowest_desc = put_lowest_in_front(env, in);
308 /* as long as the current highest node has still descendants */
310 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
311 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
312 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
316 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
318 /* count the number of all descendants which are not the lowest descendant */
319 for(n_desc = 0; in[n_desc]; ++n_desc);
322 we insert a CopyKeep node to express the artificial dependencies from the lowest
323 descendant to all other descendants.
325 if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
329 for(i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
332 op = get_irn_in_or_dep(lowest_desc, i);
333 cmp = highest_is_tuple ? skip_Projs(op) : op;
335 // if(cmp == highest_node)
336 if(op == highest_node)
340 assert(i < n && "could not find operand");
342 //replace_tuple_by_repr_proj(env, &in[1]);
343 if(!is_Proj(lowest_desc))
344 add_irn_dep(lowest_desc, in[1]);
346 obstack_free(&env->obst, in);
348 /* if the current lowest node is not yet in a lineage, add it to the current one. */
349 if(!lowest_mi->lineage_start) {
350 /* mark the current lowest node as the last one in the lineage. */
351 highest_mi->lineage_next = lowest_desc;
352 start_mi->lineage_end = lowest_desc;
354 lowest_mi->lineage_start = start;
355 nodeset_remove(nodes, lowest_desc);
358 /* else we cannot extend this lineage, so break. */
362 highest_node = lowest_desc;
363 highest_mi = lowest_mi;
365 /* recompute the descendants array and the new lowest descendant. */
366 in = all_descendants(env, highest_node);
367 lowest_desc = put_lowest_in_front(env, in);
370 /* recompute the heights if desired. */
372 heights_recompute(env->heights);
376 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
380 ir_node *u_end = u->lineage_end;
381 ir_node *v_start = v->lineage_start;
382 ir_node *start = skip_Projs(v_start);
384 if(be_is_Keep(start))
387 /* set lineage end of nodes in u to end of v. */
388 irn = last = u->lineage_start;
389 mi = get_mris_irn(env, irn);
390 while(irn && irn != u_end) {
391 mi = get_mris_irn(env, irn);
392 mi->lineage_end = v->lineage_end;
394 irn = mi->lineage_next;
397 /* insert a CopyKeep to make lineage v dependent on u. */
398 if(get_irn_ins_or_deps(start) == 0)
401 if(get_irn_mode(last) == mode_T) {
402 const ir_edge_t *edge;
403 foreach_out_edge(last, edge) {
404 last = get_edge_src_irn(edge);
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 = v_start;
412 /* add a dependency from the first node in v's lineage to the last in u's */
413 add_irn_dep(u_end, 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 mris_env_t *dump_env = NULL;
454 static void block_walker(ir_node *bl, void *data)
456 mris_env_t *env = data;
458 lineage_formation(env);
462 static int mris_edge_hook(FILE *F, ir_node *irn)
464 mris_irn_t *mi = get_mris_irn(dump_env, irn);
466 if(mi->lineage_next) {
467 fprintf(F, "edge:{sourcename:\"");
468 PRINT_NODEID(mi->lineage_next);
469 fprintf(F, "\" targetname:\"");
471 fprintf(F, "\" color:lilac}\n");
476 void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix) {
477 DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook();
479 dump_consts_local(0);
480 set_dump_node_edge_hook(mris_edge_hook);
482 dump_ir_block_graph(env->irg, suffix);
483 set_dump_node_edge_hook(old);
486 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
488 mris_env_t *env = xmalloc(sizeof(env[0]));
490 phase_init(&env->ph, "mris", birg->irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init);
491 env->aenv = birg->main_env->arch_env;
492 env->irg = birg->irg;
494 env->heights = heights_new(birg->irg);
495 INIT_LIST_HEAD(&env->lineage_head);
496 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
497 obstack_init(&env->obst);
498 irg_walk_graph(env->irg, firm_clear_link, NULL, NULL);
499 irg_block_walk_graph(birg->irg, block_walker, NULL, env);
500 obstack_free(&env->obst, NULL);
501 // dump_ir_block_graph_mris(env, "-mris");
505 void be_sched_mris_free(mris_env_t *env)
507 phase_free(&env->ph);
508 heights_free(env->heights);