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"
29 #include "besched_t.h"
30 #include "beschedmris.h"
35 const arch_env_t *aenv;
39 struct list_head lineage_head;
41 DEBUG_ONLY(firm_dbg_module_t *dbg;)
44 typedef struct _mris_irn_t {
46 ir_node *lineage_start;
47 ir_node *lineage_next;
49 struct list_head lineage_list;
52 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
54 #define get_mris_irn(env, irn) ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
55 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
57 static void *mris_irn_data_init(phase_t *ph, ir_node *irn, void *data)
59 mris_irn_t *mi = data ? data : phase_alloc(ph, sizeof(mi[0]));
60 memset(mi, 0, sizeof(mi[0]));
61 INIT_LIST_HEAD(&mi->lineage_list);
66 static int compute_height(mris_env_t *env, ir_node *irn, unsigned long visited)
68 mris_irn_t *mi = get_mris_irn(env, irn);
70 if(get_irn_visited(irn) >= visited) {
71 DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
76 const ir_edge_t *edge;
78 set_irn_visited(irn, visited);
81 foreach_out_edge(irn, edge) {
82 ir_node *dep = get_edge_src_irn(edge);
84 if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
85 int dep_height = compute_height(env, dep, visited);
86 mi->height = MAX(mi->height, dep_height);
91 DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
97 static void compute_heights(mris_env_t *env)
99 const ir_edge_t *edge;
100 unsigned long visited;
102 visited = get_irg_visited(env->irg) + 1;
103 set_irg_visited(env->irg, visited);
105 foreach_out_edge(env->bl, edge) {
106 ir_node *dep = get_edge_src_irn(edge);
107 if(to_appear(env, dep))
108 compute_height(env, dep, visited);
113 #define valid_node(env, dep) (to_appear(env, dep) && !be_is_Keep(dep))
115 static void grow_all_descendands(mris_env_t *env, ir_node *irn, unsigned long visited)
117 const ir_edge_t *edge;
119 assert(get_irn_mode(irn) != mode_T);
121 foreach_out_edge(irn, edge) {
122 ir_node *desc = get_edge_src_irn(edge);
123 if(valid_node(env, desc) && get_irn_visited(desc) < visited) {
124 obstack_ptr_grow(&env->obst, desc);
125 set_irn_visited(desc, visited);
129 foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
130 ir_node *desc = get_edge_src_irn(edge);
131 if(valid_node(env, desc) && get_irn_visited(desc) < visited) {
132 obstack_ptr_grow(&env->obst, desc);
133 set_irn_visited(desc, visited);
138 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
140 unsigned long visited;
141 const ir_edge_t *edge;
143 visited = get_irg_visited(env->irg) + 1;
144 set_irg_visited(env->irg, visited);
146 if(get_irn_mode(irn) == mode_T) {
147 foreach_out_edge(irn, edge) {
148 ir_node *desc = get_edge_src_irn(edge);
149 assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
150 grow_all_descendands(env, desc, visited);
155 grow_all_descendands(env, irn, visited);
157 obstack_ptr_grow(&env->obst, NULL);
158 return obstack_finish(&env->obst);
161 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
163 int lowest_index = 0;
164 unsigned lowest_height = INT_MAX;
167 for(i = 0; in[i]; ++i) {
168 unsigned height = get_irn_height(env->heights, in[i]);
169 if(height < lowest_height) {
170 lowest_height = height;
176 ir_node *tmp = in[0];
177 in[0] = in[lowest_index];
178 in[lowest_index] = tmp;
185 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited)
187 if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
189 set_irn_visited(irn, visited);
196 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
197 ir_node *op = get_irn_n(irn, i);
199 reaches_walker(env, op, tgt, found, visited);
205 static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
208 unsigned long visited = get_irg_visited(env->irg) + 1;
210 set_irg_visited(env->irg, visited);
211 reaches_walker(env, src, tgt, &found, visited);
216 static INLINE ir_node *skip_Projs(ir_node *irn)
218 return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
221 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
225 for(i = 0; in[i]; ++i) {
226 if(get_irn_mode(in[i]) == mode_T) {
227 const ir_edge_t *edge;
228 ir_node *proj = NULL;
229 ir_node *first = NULL;
231 foreach_out_edge(in[i], edge) {
232 ir_node *desc = get_edge_src_irn(edge);
234 first = first ? first : desc;
235 if(get_irn_mode(desc) == mode_M) {
241 proj = proj ? proj : first;
248 static void lineage_formation(mris_env_t *env)
250 firm_dbg_module_t *dbg = env->dbg;
251 nodeset *nodes = new_nodeset(128);
253 const ir_edge_t *edge;
255 foreach_out_edge(env->bl, edge) {
256 ir_node *irn = get_edge_src_irn(edge);
257 if(to_appear(env, irn))
258 nodeset_insert(nodes, irn);
261 while(nodeset_count(nodes) > 0) {
264 ir_node *highest_node = NULL;
265 ir_node *lowest_desc = NULL;
268 int recompute_height = 0;
269 unsigned curr_height = 0;
271 /* search the highest node which is not yet in a lineage. */
272 for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) {
273 unsigned height = get_irn_height(env->heights, irn);
274 if(height > curr_height) {
276 curr_height = height;
280 assert(highest_node);
281 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
283 /* start a lineage beginning with highest_node. */
284 mi = get_mris_irn(env, highest_node);
285 mi->lineage_start = highest_node;
286 mi->lineage_next = NULL;
287 mi->lineage_end = NULL;
288 list_add(&mi->lineage_list, &env->lineage_head);
289 nodeset_remove(nodes, highest_node);
292 put all descendants in an array.
293 we also move the lowest descendant in front, so that the other nodes
294 are easily accessible as an array, too.
296 in = all_descendants(env, highest_node);
297 lowest_desc = put_lowest_in_front(env, in);
299 /* as long as the current highest node has still descendants */
301 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
302 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
303 mris_irn_t *start_mi = get_mris_irn(env, highest_mi->lineage_start);
304 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
308 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
310 /* count the number of all descendants which are not the lowest descendant */
311 for(n_desc = 0; in[n_desc + 1]; ++n_desc);
314 we insert a CopyKeep node to express the artificial dependencies from the lowest
315 descendant to all other descendants.
317 if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
318 const arch_register_class_t *cls;
322 for(i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
325 op = get_irn_in_or_dep(lowest_desc, i);
326 cmp = highest_is_tuple ? skip_Projs(op) : op;
328 if(cmp == highest_node)
332 assert(i < n && "could not find operand");
334 cls = arch_get_irn_reg_class(env->aenv, op, BE_OUT_POS(0));
335 replace_tuple_by_repr_proj(env, &in[1]);
336 add_irn_dep(lowest_desc, in[1]);
338 obstack_free(&env->obst, in);
340 /* mark the current lowest node as the last one in the lineage. */
341 highest_mi->lineage_next = lowest_desc;
342 start_mi->lineage_end = lowest_desc;
344 /* if the current lowest node is not yet in a lineage, add it to the current one. */
345 if(!lowest_mi->lineage_start) {
346 lowest_mi->lineage_start = highest_mi->lineage_start;
347 nodeset_remove(nodes, lowest_desc);
350 /* else we cannot extend this lineage, so break. */
354 highest_node = lowest_desc;
355 highest_mi = lowest_mi;
357 /* recompute the descendants array and the new lowest descendant. */
358 in = all_descendants(env, highest_node);
359 lowest_desc = put_lowest_in_front(env, in);
362 /* recompute the heights if desired. */
364 heights_recompute(env->heights);
368 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
372 ir_node *irn, *last, *copy;
373 ir_node *u_end = u->lineage_end;
374 ir_node *v_start = v->lineage_start;
375 ir_node *start = skip_Projs(v_start);
377 if(be_is_Keep(start))
380 /* set lineage end of nodes in u to end of v. */
381 irn = last = u->lineage_start;
382 mi = get_mris_irn(env, irn);
383 while(irn && irn != u_end) {
384 mi = get_mris_irn(env, irn);
385 mi->lineage_end = v->lineage_end;
387 irn = mi->lineage_next;
390 /* insert a CopyKeep to make lineage v dependent on u. */
392 if(get_irn_ins_or_deps(start) == 0)
395 if(get_irn_mode(last) == mode_T) {
396 const ir_edge_t *edge;
397 foreach_out_edge(last, edge) {
398 last = get_edge_src_irn(edge);
403 add_irn_dep(start, last);
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)
430 mris_irn_t *u, *v, *tmp1, *tmp2;
433 foreach_lineage(env, u, tmp1) {
434 foreach_lineage(env, v, tmp2) {
435 if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
436 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
437 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
438 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
441 if(fuse_two_lineages(env, u, v))
449 static void block_walker(ir_node *bl, void *data)
451 mris_env_t *env = data;
453 lineage_formation(env);
454 //fuse_lineages(env);
458 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
460 mris_env_t *env = xmalloc(sizeof(env[0]));
462 phase_init(&env->ph, "mris", birg->irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init);
463 env->aenv = birg->main_env->arch_env;
464 env->irg = birg->irg;
466 env->heights = heights_new(birg->irg);
467 INIT_LIST_HEAD(&env->lineage_head);
468 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
469 obstack_init(&env->obst);
470 irg_walk_graph(env->irg, firm_clear_link, NULL, NULL);
471 irg_block_walk_graph(birg->irg, block_walker, NULL, env);
472 obstack_free(&env->obst, NULL);
476 void be_sched_mris_free(mris_env_t *env)
478 phase_free(&env->ph);
479 heights_free(env->heights);