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"
39 const arch_env_t *aenv;
43 struct list_head lineage_head;
45 DEBUG_ONLY(firm_dbg_module_t *dbg;)
48 typedef struct _mris_irn_t {
50 ir_node *lineage_start;
51 ir_node *lineage_next;
53 struct list_head lineage_list;
56 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
58 #define get_mris_irn(env, irn) ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
59 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
61 static void *mris_irn_data_init(ir_phase *ph, ir_node *irn, void *data)
63 mris_irn_t *mi = data ? data : phase_alloc(ph, sizeof(mi[0]));
64 memset(mi, 0, sizeof(mi[0]));
65 INIT_LIST_HEAD(&mi->lineage_list);
70 static int compute_height(mris_env_t *env, ir_node *irn, unsigned long visited)
72 mris_irn_t *mi = get_mris_irn(env, irn);
74 if(get_irn_visited(irn) >= visited) {
75 DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
80 const ir_edge_t *edge;
82 set_irn_visited(irn, visited);
85 foreach_out_edge(irn, edge) {
86 ir_node *dep = get_edge_src_irn(edge);
88 if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
89 int dep_height = compute_height(env, dep, visited);
90 mi->height = MAX(mi->height, dep_height);
95 DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
101 static void compute_heights(mris_env_t *env)
103 const ir_edge_t *edge;
104 unsigned long visited;
106 visited = get_irg_visited(env->irg) + 1;
107 set_irg_visited(env->irg, visited);
109 foreach_out_edge(env->bl, edge) {
110 ir_node *dep = get_edge_src_irn(edge);
111 if(to_appear(env, dep))
112 compute_height(env, dep, visited);
117 #define valid_node(env, dep) (to_appear(env, dep) && !be_is_Keep(dep))
119 static void grow_all_descendands(mris_env_t *env, ir_node *irn, bitset_t *visited)
121 const ir_edge_t *edge;
123 // assert(get_irn_mode(irn) != mode_T);
125 foreach_out_edge(irn, edge) {
126 ir_node *desc = get_edge_src_irn(edge);
127 if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
128 obstack_ptr_grow(&env->obst, desc);
129 bitset_add_irn(visited, desc);
133 foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
134 ir_node *desc = get_edge_src_irn(edge);
135 if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
136 obstack_ptr_grow(&env->obst, desc);
137 bitset_add_irn(visited, desc);
142 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
144 bitset_t *visited = bitset_irg_malloc(env->irg);
146 grow_all_descendands(env, irn, visited);
149 if(get_irn_mode(irn) == mode_T) {
150 const ir_edge_t *edge;
151 foreach_out_edge(irn, edge) {
152 ir_node *desc = get_edge_src_irn(edge);
153 assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
154 grow_all_descendands(env, desc, visited);
159 grow_all_descendands(env, irn, visited);
161 bitset_free(visited);
162 obstack_ptr_grow(&env->obst, NULL);
163 return obstack_finish(&env->obst);
166 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
168 int lowest_index = 0;
169 unsigned lowest_height = INT_MAX;
172 for(i = 0; in[i]; ++i) {
173 unsigned height = get_irn_height(env->heights, in[i]);
174 if(height < lowest_height) {
175 lowest_height = height;
181 ir_node *tmp = in[0];
182 in[0] = in[lowest_index];
183 in[lowest_index] = tmp;
190 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited)
192 if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
194 set_irn_visited(irn, visited);
201 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
202 ir_node *op = get_irn_n(irn, i);
204 reaches_walker(env, op, tgt, found, visited);
210 static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
213 unsigned long visited = get_irg_visited(env->irg) + 1;
215 set_irg_visited(env->irg, visited);
216 reaches_walker(env, src, tgt, &found, visited);
221 static INLINE ir_node *skip_Projs(ir_node *irn)
223 return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
227 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
231 for(i = 0; in[i]; ++i) {
232 if(get_irn_mode(in[i]) == mode_T) {
233 const ir_edge_t *edge;
234 ir_node *proj = NULL;
235 ir_node *first = NULL;
237 foreach_out_edge(in[i], edge) {
238 ir_node *desc = get_edge_src_irn(edge);
240 first = first ? first : desc;
241 if(get_irn_mode(desc) == mode_M) {
247 proj = proj ? proj : first;
255 static void lineage_formation(mris_env_t *env)
257 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg);
258 nodeset *nodes = new_nodeset(128);
260 const ir_edge_t *edge;
262 foreach_out_edge(env->bl, edge) {
263 ir_node *irn = get_edge_src_irn(edge);
264 if(to_appear(env, irn))
265 nodeset_insert(nodes, irn);
268 while(nodeset_count(nodes) > 0) {
271 ir_node *highest_node = NULL;
272 ir_node *lowest_desc = NULL;
274 mris_irn_t *start_mi;
277 int recompute_height = 0;
278 unsigned curr_height = 0;
280 /* search the highest node which is not yet in a lineage. */
281 for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) {
282 unsigned height = get_irn_height(env->heights, irn);
283 if(height > curr_height) {
285 curr_height = height;
289 assert(highest_node);
290 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
292 start = highest_node;
293 mi = start_mi = get_mris_irn(env, highest_node);
295 /* start a lineage beginning with highest_node. */
296 mi->lineage_start = highest_node;
297 mi->lineage_next = NULL;
298 mi->lineage_end = NULL;
299 list_add(&mi->lineage_list, &env->lineage_head);
300 nodeset_remove(nodes, highest_node);
303 put all descendants in an array.
304 we also move the lowest descendant in front, so that the other nodes
305 are easily accessible as an array, too.
307 in = all_descendants(env, highest_node);
308 lowest_desc = put_lowest_in_front(env, in);
310 /* as long as the current highest node has still descendants */
312 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
313 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
314 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
318 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
320 /* count the number of all descendants which are not the lowest descendant */
321 for(n_desc = 0; in[n_desc]; ++n_desc);
324 we insert a CopyKeep node to express the artificial dependencies from the lowest
325 descendant to all other descendants.
327 if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
331 for(i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
334 op = get_irn_in_or_dep(lowest_desc, i);
335 cmp = highest_is_tuple ? skip_Projs(op) : op;
337 // if(cmp == highest_node)
338 if(op == highest_node)
342 assert(i < n && "could not find operand");
344 //replace_tuple_by_repr_proj(env, &in[1]);
345 if(!is_Proj(lowest_desc))
346 add_irn_dep(lowest_desc, in[1]);
348 obstack_free(&env->obst, in);
350 /* if the current lowest node is not yet in a lineage, add it to the current one. */
351 if(!lowest_mi->lineage_start) {
352 /* mark the current lowest node as the last one in the lineage. */
353 highest_mi->lineage_next = lowest_desc;
354 start_mi->lineage_end = lowest_desc;
356 lowest_mi->lineage_start = start;
357 nodeset_remove(nodes, lowest_desc);
360 /* else we cannot extend this lineage, so break. */
364 highest_node = lowest_desc;
365 highest_mi = lowest_mi;
367 /* recompute the descendants array and the new lowest descendant. */
368 in = all_descendants(env, highest_node);
369 lowest_desc = put_lowest_in_front(env, in);
372 /* recompute the heights if desired. */
374 heights_recompute(env->heights);
378 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
382 ir_node *u_end = u->lineage_end;
383 ir_node *v_start = v->lineage_start;
384 ir_node *start = skip_Projs(v_start);
386 if(be_is_Keep(start))
389 /* set lineage end of nodes in u to end of v. */
390 irn = last = u->lineage_start;
391 mi = get_mris_irn(env, irn);
392 while(irn && irn != u_end) {
393 mi = get_mris_irn(env, irn);
394 mi->lineage_end = v->lineage_end;
396 irn = mi->lineage_next;
399 /* insert a CopyKeep to make lineage v dependent on u. */
400 if(get_irn_ins_or_deps(start) == 0)
403 if(get_irn_mode(last) == mode_T) {
404 const ir_edge_t *edge;
405 foreach_out_edge(last, edge) {
406 last = get_edge_src_irn(edge);
411 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
412 mi->lineage_next = v_start;
414 /* add a dependency from the first node in v's lineage to the last in u's */
415 add_irn_dep(u_end, v_start);
417 /* set lineage start of nodes in v to start of u. */
418 irn = v->lineage_start;
419 while(irn && irn != v->lineage_end) {
420 mris_irn_t *mi = get_mris_irn(env, irn);
421 mi->lineage_start = u->lineage_start;
422 irn = mi->lineage_next;
425 heights_recompute(env->heights);
427 mi = get_mris_irn(env, v_start);
428 list_del(&mi->lineage_list);
433 static void fuse_lineages(mris_env_t *env)
435 mris_irn_t *u, *v, *tmp1, *tmp2;
438 foreach_lineage(env, u, tmp1) {
439 foreach_lineage(env, v, tmp2) {
440 if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
441 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
442 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
443 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
446 if(fuse_two_lineages(env, u, v))
454 static mris_env_t *dump_env = NULL;
456 static void block_walker(ir_node *bl, void *data)
458 mris_env_t *env = data;
460 lineage_formation(env);
464 static int mris_edge_hook(FILE *F, ir_node *irn)
466 mris_irn_t *mi = get_mris_irn(dump_env, irn);
468 if(mi->lineage_next) {
469 fprintf(F, "edge:{sourcename:\"");
470 PRINT_NODEID(mi->lineage_next);
471 fprintf(F, "\" targetname:\"");
473 fprintf(F, "\" color:lilac}\n");
478 void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix) {
479 DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook();
481 dump_consts_local(0);
482 set_dump_node_edge_hook(mris_edge_hook);
484 dump_ir_block_graph(env->irg, suffix);
485 set_dump_node_edge_hook(old);
488 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
490 mris_env_t *env = xmalloc(sizeof(env[0]));
491 ir_graph *irg = be_get_birg_irg(birg);
493 phase_init(&env->ph, "mris", irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init, NULL);
494 env->aenv = be_get_birg_arch_env(birg);
497 env->heights = heights_new(irg);
498 INIT_LIST_HEAD(&env->lineage_head);
499 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
500 obstack_init(&env->obst);
501 irg_walk_graph(irg, firm_clear_link, NULL, NULL);
502 irg_block_walk_graph(irg, block_walker, NULL, env);
503 obstack_free(&env->obst, NULL);
504 // dump_ir_block_graph_mris(env, "-mris");
508 void be_sched_mris_free(mris_env_t *env)
510 phase_free(&env->ph);
511 heights_free(env->heights);