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 ? data : phase_alloc(ph, sizeof(mi[0]));
58 memset(data, 0, sizeof(mi[0]));
59 INIT_LIST_HEAD(&mi->lineage_list);
64 static int compute_height(mris_env_t *env, ir_node *irn, unsigned long visited)
66 mris_irn_t *mi = get_mris_irn(env, irn);
68 if(get_irn_visited(irn) >= visited) {
69 DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
74 const ir_edge_t *edge;
76 set_irn_visited(irn, visited);
79 foreach_out_edge(irn, edge) {
80 ir_node *dep = get_edge_src_irn(edge);
82 if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
83 int dep_height = compute_height(env, dep, visited);
84 mi->height = MAX(mi->height, dep_height);
89 DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
95 static void compute_heights(mris_env_t *env)
97 const ir_edge_t *edge;
98 unsigned long visited;
100 visited = get_irg_visited(env->irg) + 1;
101 set_irg_visited(env->irg, visited);
103 foreach_out_edge(env->bl, edge) {
104 ir_node *dep = get_edge_src_irn(edge);
105 if(to_appear(env, dep))
106 compute_height(env, dep, visited);
111 #define valid_node(env, dep) (to_appear(env, dep) && !nodeset_find(env->inserted, dep) && !be_is_Keep(dep))
113 static void grow_all_descendands(mris_env_t *env, ir_node *irn, unsigned long visited)
115 const ir_edge_t *edge;
117 assert(get_irn_mode(irn) != mode_T);
119 foreach_out_edge(irn, edge) {
120 ir_node *desc = get_edge_src_irn(edge);
121 if(valid_node(env, desc) && get_irn_visited(desc) < visited) {
122 obstack_ptr_grow(&env->obst, desc);
123 set_irn_visited(desc, visited);
128 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
130 unsigned long visited;
131 const ir_edge_t *edge;
133 visited = get_irg_visited(env->irg) + 1;
134 set_irg_visited(env->irg, visited);
136 if(get_irn_mode(irn) == mode_T) {
137 foreach_out_edge(irn, edge) {
138 ir_node *desc = get_edge_src_irn(edge);
139 assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
140 grow_all_descendands(env, desc, visited);
145 grow_all_descendands(env, irn, visited);
147 obstack_ptr_grow(&env->obst, NULL);
148 return obstack_finish(&env->obst);
151 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
153 int lowest_index = 0;
154 unsigned lowest_height = INT_MAX;
157 for(i = 0; in[i]; ++i) {
158 unsigned height = get_irn_height(env->heights, in[i]);
159 if(height < lowest_height) {
160 lowest_height = height;
166 ir_node *tmp = in[0];
167 in[0] = in[lowest_index];
168 in[lowest_index] = tmp;
175 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited)
177 if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
179 set_irn_visited(irn, visited);
186 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
187 ir_node *op = get_irn_n(irn, i);
189 reaches_walker(env, op, tgt, found, visited);
195 static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
198 unsigned long visited = get_irg_visited(env->irg) + 1;
200 set_irg_visited(env->irg, visited);
201 reaches_walker(env, src, tgt, &found, visited);
206 static INLINE ir_node *skip_Projs(ir_node *irn)
208 return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
211 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
215 for(i = 0; in[i]; ++i) {
216 if(get_irn_mode(in[i]) == mode_T) {
217 const ir_edge_t *edge;
218 ir_node *proj = NULL;
219 ir_node *first = NULL;
221 foreach_out_edge(in[i], edge) {
222 ir_node *desc = get_edge_src_irn(edge);
224 first = first ? first : desc;
225 if(get_irn_mode(desc) == mode_M) {
231 proj = proj ? proj : first;
238 static void lineage_formation(mris_env_t *env)
240 firm_dbg_module_t *dbg = env->dbg;
241 nodeset *nodes = new_nodeset(128);
243 const ir_edge_t *edge;
245 foreach_out_edge(env->bl, edge) {
246 ir_node *irn = get_edge_src_irn(edge);
247 if(to_appear(env, irn))
248 nodeset_insert(nodes, irn);
251 while(nodeset_count(nodes) > 0) {
254 ir_node *highest_node = NULL;
255 ir_node *lowest_desc = NULL;
258 int recompute_height = 0;
259 unsigned curr_height = 0;
261 /* search the highest node which is not yet in a lineage. */
262 for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) {
263 unsigned height = get_irn_height(env->heights, irn);
264 if(height > curr_height) {
266 curr_height = height;
270 assert(highest_node);
271 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
273 /* start a lineage beginning with highest_node. */
274 mi = get_mris_irn(env, highest_node);
275 mi->lineage_start = highest_node;
276 mi->lineage_next = NULL;
277 mi->lineage_end = NULL;
278 list_add(&mi->lineage_list, &env->lineage_head);
279 nodeset_remove(nodes, highest_node);
282 put all descendants in an array.
283 we also move the lowest descendant in front, so that the other nodes
284 are easily accessible as an array, too.
286 in = all_descendants(env, highest_node);
287 lowest_desc = put_lowest_in_front(env, in);
289 /* as long as the current highest node has still descendants */
291 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
292 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
293 mris_irn_t *start_mi = get_mris_irn(env, highest_mi->lineage_start);
294 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
298 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
300 /* count the number of all descendants which are not the lowest descendant */
301 for(n_desc = 0; in[n_desc + 1]; ++n_desc);
304 we insert a CopyKeep node to express the artificial dependencies from the lowest
305 descendant to all other descendants.
307 if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
308 const arch_register_class_t *cls;
309 ir_node *copy_keep, *op;
312 for(i = 0, n = get_irn_arity(lowest_desc); i < n; ++i) {
315 op = get_irn_n(lowest_desc, i);
316 cmp = highest_is_tuple ? skip_Projs(op) : op;
318 if(cmp == highest_node)
322 assert(i < n && "could not find operand");
324 cls = arch_get_irn_reg_class(env->aenv, op, BE_OUT_POS(0));
325 replace_tuple_by_repr_proj(env, &in[1]);
326 copy_keep = be_new_CopyKeep(cls, env->irg, env->bl, op, n_desc, &in[1], get_irn_mode(op));
327 set_irn_n(lowest_desc, i, copy_keep);
328 nodeset_insert(env->inserted, copy_keep);
330 obstack_free(&env->obst, in);
332 /* mark the current lowest node as the last one in the lineage. */
333 highest_mi->lineage_next = lowest_desc;
334 start_mi->lineage_end = lowest_desc;
336 /* if the current lowest node is not yet in a lineage, add it to the current one. */
337 if(!lowest_mi->lineage_start) {
338 lowest_mi->lineage_start = highest_mi->lineage_start;
339 nodeset_remove(nodes, lowest_desc);
342 /* else we cannot extend this lineage, so break. */
346 highest_node = lowest_desc;
347 highest_mi = lowest_mi;
349 /* recompute the descendants array and the new lowest descendant. */
350 in = all_descendants(env, highest_node);
351 lowest_desc = put_lowest_in_front(env, in);
354 /* recompute the heights if desired. */
356 heights_recompute(env->heights);
360 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
364 ir_node *irn, *last, *copy;
365 ir_node *u_end = u->lineage_end;
366 ir_node *v_start = v->lineage_start;
367 ir_node *start = skip_Projs(v_start);
369 if(be_is_Keep(start))
372 /* set lineage end of nodes in u to end of v. */
373 irn = last = u->lineage_start;
374 mi = get_mris_irn(env, irn);
375 while(irn && irn != u_end) {
376 mi = get_mris_irn(env, irn);
377 mi->lineage_end = v->lineage_end;
379 irn = mi->lineage_next;
382 /* insert a CopyKeep to make lineage v dependent on u. */
384 const arch_register_class_t *cls;
387 if(get_irn_arity(start) == 0)
390 op = get_irn_n(start, 0);
392 cls = arch_get_irn_reg_class(env->aenv, op, BE_OUT_POS(0));
393 if(get_irn_mode(last) == mode_T) {
394 const ir_edge_t *edge;
395 foreach_out_edge(last, edge) {
396 last = get_edge_src_irn(edge);
400 copy = be_new_CopyKeep_single(cls, env->irg, env->bl, op, last, get_irn_mode(op));
401 set_irn_n(start, 0, copy);
402 copy_mi = get_mris_irn(env, copy);
403 nodeset_insert(env->inserted, copy);
406 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
407 mi->lineage_next = copy;
408 copy_mi->lineage_start = u->lineage_start;
409 copy_mi->lineage_end = v->lineage_end;
410 copy_mi->lineage_next = v_start;
412 /* set lineage start of nodes in v to start of u. */
413 irn = v->lineage_start;
414 while(irn && irn != v->lineage_end) {
415 mris_irn_t *mi = get_mris_irn(env, irn);
416 mi->lineage_start = u->lineage_start;
417 irn = mi->lineage_next;
420 heights_recompute(env->heights);
422 mi = get_mris_irn(env, v_start);
423 list_del(&mi->lineage_list);
428 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 void block_walker(ir_node *bl, void *data)
452 mris_env_t *env = data;
454 lineage_formation(env);
459 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
461 mris_env_t *env = xmalloc(sizeof(env[0]));
463 phase_init(&env->ph, "mris", birg->irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init);
464 env->aenv = birg->main_env->arch_env;
465 env->irg = birg->irg;
467 env->inserted = new_nodeset(128);
468 env->heights = heights_new(birg->irg);
469 INIT_LIST_HEAD(&env->lineage_head);
470 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
471 obstack_init(&env->obst);
472 irg_walk_graph(env->irg, firm_clear_link, NULL, NULL);
473 irg_block_walk_graph(birg->irg, block_walker, NULL, env);
474 obstack_free(&env->obst, NULL);
478 static void cleanup_inserted(mris_env_t *env)
482 foreach_nodeset(env->inserted, irn) {
486 assert(be_is_CopyKeep(irn));
487 tgt = get_irn_n(irn, be_pos_CopyKeep_op);
489 /* reroute the edges, remove from schedule and make it invisible. */
490 edges_reroute(irn, tgt, env->irg);
491 if (sched_is_scheduled(irn))
493 for(i = -1, n = get_irn_arity(irn); i < n; ++i)
494 set_irn_n(irn, i, new_r_Bad(env->irg));
498 void be_sched_mris_free(mris_env_t *env)
500 cleanup_inserted(env);
501 phase_free(&env->ph);
502 del_nodeset(env->inserted);
503 heights_free(env->heights);