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;
224 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
228 for(i = 0; in[i]; ++i) {
229 if(get_irn_mode(in[i]) == mode_T) {
230 const ir_edge_t *edge;
231 ir_node *proj = NULL;
232 ir_node *first = NULL;
234 foreach_out_edge(in[i], edge) {
235 ir_node *desc = get_edge_src_irn(edge);
237 first = first ? first : desc;
238 if(get_irn_mode(desc) == mode_M) {
244 proj = proj ? proj : first;
251 static void lineage_formation(mris_env_t *env)
253 firm_dbg_module_t *dbg = env->dbg;
254 nodeset *nodes = new_nodeset(128);
256 const ir_edge_t *edge;
258 foreach_out_edge(env->bl, edge) {
259 ir_node *irn = get_edge_src_irn(edge);
260 if(to_appear(env, irn))
261 nodeset_insert(nodes, irn);
264 while(nodeset_count(nodes) > 0) {
267 ir_node *highest_node = NULL;
268 ir_node *lowest_desc = NULL;
270 mris_irn_t *start_mi;
273 int recompute_height = 0;
274 unsigned curr_height = 0;
276 /* search the highest node which is not yet in a lineage. */
277 for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) {
278 unsigned height = get_irn_height(env->heights, irn);
279 if(height > curr_height) {
281 curr_height = height;
285 assert(highest_node);
286 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
288 start = highest_node;
289 mi = start_mi = get_mris_irn(env, highest_node);
291 /* start a lineage beginning with highest_node. */
292 mi->lineage_start = highest_node;
293 mi->lineage_next = NULL;
294 mi->lineage_end = NULL;
295 list_add(&mi->lineage_list, &env->lineage_head);
296 nodeset_remove(nodes, highest_node);
299 put all descendants in an array.
300 we also move the lowest descendant in front, so that the other nodes
301 are easily accessible as an array, too.
303 in = all_descendants(env, highest_node);
304 lowest_desc = put_lowest_in_front(env, in);
306 /* as long as the current highest node has still descendants */
308 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
309 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
310 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
314 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
316 /* count the number of all descendants which are not the lowest descendant */
317 for(n_desc = 0; in[n_desc]; ++n_desc);
320 we insert a CopyKeep node to express the artificial dependencies from the lowest
321 descendant to all other descendants.
323 if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
327 for(i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
330 op = get_irn_in_or_dep(lowest_desc, i);
331 cmp = highest_is_tuple ? skip_Projs(op) : op;
333 // if(cmp == highest_node)
334 if(op == highest_node)
338 assert(i < n && "could not find operand");
340 //replace_tuple_by_repr_proj(env, &in[1]);
341 if(!is_Proj(lowest_desc))
342 add_irn_dep(lowest_desc, in[1]);
344 obstack_free(&env->obst, in);
346 /* if the current lowest node is not yet in a lineage, add it to the current one. */
347 if(!lowest_mi->lineage_start) {
348 /* mark the current lowest node as the last one in the lineage. */
349 highest_mi->lineage_next = lowest_desc;
350 start_mi->lineage_end = lowest_desc;
352 lowest_mi->lineage_start = start;
353 nodeset_remove(nodes, lowest_desc);
356 /* else we cannot extend this lineage, so break. */
360 highest_node = lowest_desc;
361 highest_mi = lowest_mi;
363 /* recompute the descendants array and the new lowest descendant. */
364 in = all_descendants(env, highest_node);
365 lowest_desc = put_lowest_in_front(env, in);
368 /* recompute the heights if desired. */
370 heights_recompute(env->heights);
374 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
378 ir_node *u_end = u->lineage_end;
379 ir_node *v_start = v->lineage_start;
380 ir_node *start = skip_Projs(v_start);
382 if(be_is_Keep(start))
385 /* set lineage end of nodes in u to end of v. */
386 irn = last = u->lineage_start;
387 mi = get_mris_irn(env, irn);
388 while(irn && irn != u_end) {
389 mi = get_mris_irn(env, irn);
390 mi->lineage_end = v->lineage_end;
392 irn = mi->lineage_next;
395 /* insert a CopyKeep to make lineage v dependent on u. */
396 if(get_irn_ins_or_deps(start) == 0)
399 if(get_irn_mode(last) == mode_T) {
400 const ir_edge_t *edge;
401 foreach_out_edge(last, edge) {
402 last = get_edge_src_irn(edge);
407 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
408 mi->lineage_next = v_start;
410 /* add a dependency from the first node in v's lineage to the last in u's */
411 add_irn_dep(u_end, v_start);
413 /* set lineage start of nodes in v to start of u. */
414 irn = v->lineage_start;
415 while(irn && irn != v->lineage_end) {
416 mris_irn_t *mi = get_mris_irn(env, irn);
417 mi->lineage_start = u->lineage_start;
418 irn = mi->lineage_next;
421 heights_recompute(env->heights);
423 mi = get_mris_irn(env, v_start);
424 list_del(&mi->lineage_list);
429 static void fuse_lineages(mris_env_t *env)
431 mris_irn_t *u, *v, *tmp1, *tmp2;
434 foreach_lineage(env, u, tmp1) {
435 foreach_lineage(env, v, tmp2) {
436 if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
437 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
438 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
439 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
442 if(fuse_two_lineages(env, u, v))
450 static mris_env_t *dump_env = NULL;
452 static void block_walker(ir_node *bl, void *data)
454 mris_env_t *env = data;
456 lineage_formation(env);
460 static int mris_edge_hook(FILE *F, ir_node *irn)
462 mris_irn_t *mi = get_mris_irn(dump_env, irn);
464 if(mi->lineage_next) {
465 fprintf(F, "edge:{sourcename:\"");
466 PRINT_NODEID(mi->lineage_next);
467 fprintf(F, "\" targetname:\"");
469 fprintf(F, "\" color:lilac}\n");
474 void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix) {
475 DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook();
477 dump_consts_local(0);
478 set_dump_node_edge_hook(mris_edge_hook);
480 dump_ir_block_graph(env->irg, suffix);
481 set_dump_node_edge_hook(old);
484 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
486 mris_env_t *env = xmalloc(sizeof(env[0]));
488 phase_init(&env->ph, "mris", birg->irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init);
489 env->aenv = birg->main_env->arch_env;
490 env->irg = birg->irg;
492 env->heights = heights_new(birg->irg);
493 INIT_LIST_HEAD(&env->lineage_head);
494 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
495 obstack_init(&env->obst);
496 irg_walk_graph(env->irg, firm_clear_link, NULL, NULL);
497 irg_block_walk_graph(birg->irg, block_walker, NULL, env);
498 obstack_free(&env->obst, NULL);
499 // dump_ir_block_graph_mris(env, "-mris");
503 void be_sched_mris_free(mris_env_t *env)
505 phase_free(&env->ph);
506 heights_free(env->heights);