2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Implements a list scheduler for the MRIS algorithm.
23 * @author Sebastian Hack
27 * Implements a list scheduler for the MRIS algorithm in:
28 * Govindarajan, Yang, Amaral, Zhang, Gao
29 * Minimum Register Instruction Sequencing to Reduce Register Spills
30 * in out-of-order issue superscalar architectures
41 #include "irgraph_t.h"
43 #include "iredges_t.h"
45 #include "irphase_t.h"
53 #include "besched_t.h"
54 #include "beschedmris.h"
60 const arch_env_t *aenv;
64 struct list_head lineage_head;
66 DEBUG_ONLY(firm_dbg_module_t *dbg;)
69 typedef struct _mris_irn_t {
71 ir_node *lineage_start;
72 ir_node *lineage_next;
74 struct list_head lineage_list;
77 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
79 #define get_mris_irn(env, irn) ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
80 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
82 static void *mris_irn_data_init(ir_phase *ph, const ir_node *irn, void *data)
84 mris_irn_t *mi = data ? data : phase_alloc(ph, sizeof(mi[0]));
86 memset(mi, 0, sizeof(mi[0]));
87 INIT_LIST_HEAD(&mi->lineage_list);
92 static int compute_height(mris_env_t *env, ir_node *irn, unsigned long visited)
94 mris_irn_t *mi = get_mris_irn(env, irn);
96 if(get_irn_visited(irn) >= visited) {
97 DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
102 const ir_edge_t *edge;
104 set_irn_visited(irn, visited);
107 foreach_out_edge(irn, edge) {
108 ir_node *dep = get_edge_src_irn(edge);
110 if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
111 int dep_height = compute_height(env, dep, visited);
112 mi->height = MAX(mi->height, dep_height);
117 DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
123 static void compute_heights(mris_env_t *env)
125 const ir_edge_t *edge;
126 unsigned long visited;
128 visited = get_irg_visited(env->irg) + 1;
129 set_irg_visited(env->irg, visited);
131 foreach_out_edge(env->bl, edge) {
132 ir_node *dep = get_edge_src_irn(edge);
133 if(to_appear(env, dep))
134 compute_height(env, dep, visited);
139 #define valid_node(env, dep) (to_appear(env, dep) && !be_is_Keep(dep))
141 static void grow_all_descendands(mris_env_t *env, ir_node *irn, bitset_t *visited)
143 const ir_edge_t *edge;
145 // assert(get_irn_mode(irn) != mode_T);
147 foreach_out_edge(irn, edge) {
148 ir_node *desc = get_edge_src_irn(edge);
149 if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
150 obstack_ptr_grow(&env->obst, desc);
151 bitset_add_irn(visited, desc);
155 foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
156 ir_node *desc = get_edge_src_irn(edge);
157 if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
158 obstack_ptr_grow(&env->obst, desc);
159 bitset_add_irn(visited, desc);
164 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
166 bitset_t *visited = bitset_irg_malloc(env->irg);
168 grow_all_descendands(env, irn, visited);
171 if(get_irn_mode(irn) == mode_T) {
172 const ir_edge_t *edge;
173 foreach_out_edge(irn, edge) {
174 ir_node *desc = get_edge_src_irn(edge);
175 assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
176 grow_all_descendands(env, desc, visited);
181 grow_all_descendands(env, irn, visited);
183 bitset_free(visited);
184 obstack_ptr_grow(&env->obst, NULL);
185 return obstack_finish(&env->obst);
188 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
190 int lowest_index = 0;
191 unsigned lowest_height = INT_MAX;
194 for(i = 0; in[i]; ++i) {
195 unsigned height = get_irn_height(env->heights, in[i]);
196 if(height < lowest_height) {
197 lowest_height = height;
203 ir_node *tmp = in[0];
204 in[0] = in[lowest_index];
205 in[lowest_index] = tmp;
212 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited)
214 if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
216 set_irn_visited(irn, visited);
223 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
224 ir_node *op = get_irn_n(irn, i);
226 reaches_walker(env, op, tgt, found, visited);
232 static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
235 unsigned long visited = get_irg_visited(env->irg) + 1;
237 set_irg_visited(env->irg, visited);
238 reaches_walker(env, src, tgt, &found, visited);
243 static INLINE ir_node *skip_Projs(ir_node *irn)
245 return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
249 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
253 for(i = 0; in[i]; ++i) {
254 if(get_irn_mode(in[i]) == mode_T) {
255 const ir_edge_t *edge;
256 ir_node *proj = NULL;
257 ir_node *first = NULL;
259 foreach_out_edge(in[i], edge) {
260 ir_node *desc = get_edge_src_irn(edge);
262 first = first ? first : desc;
263 if(get_irn_mode(desc) == mode_M) {
269 proj = proj ? proj : first;
277 static void lineage_formation(mris_env_t *env)
279 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg);
281 const ir_edge_t *edge;
283 ir_nodeset_init(&nodes);
285 foreach_out_edge(env->bl, edge) {
286 ir_node *irn = get_edge_src_irn(edge);
287 if(to_appear(env, irn))
288 ir_nodeset_insert(&nodes, irn);
291 while(ir_nodeset_size(&nodes) > 0) {
294 ir_node *highest_node = NULL;
295 ir_node *lowest_desc = NULL;
297 mris_irn_t *start_mi;
298 ir_nodeset_iterator_t iter;
301 int recompute_height = 0;
302 unsigned curr_height = 0;
304 /* search the highest node which is not yet in a lineage. */
305 foreach_ir_nodeset(&nodes, irn, iter) {
306 unsigned height = get_irn_height(env->heights, irn);
307 if(height > curr_height) {
309 curr_height = height;
313 assert(highest_node);
314 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
316 start = highest_node;
317 mi = start_mi = get_mris_irn(env, highest_node);
319 /* start a lineage beginning with highest_node. */
320 mi->lineage_start = highest_node;
321 mi->lineage_next = NULL;
322 mi->lineage_end = NULL;
323 list_add(&mi->lineage_list, &env->lineage_head);
324 ir_nodeset_remove(&nodes, highest_node);
327 put all descendants in an array.
328 we also move the lowest descendant in front, so that the other nodes
329 are easily accessible as an array, too.
331 in = all_descendants(env, highest_node);
332 lowest_desc = put_lowest_in_front(env, in);
334 /* as long as the current highest node has still descendants */
336 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
337 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
338 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
342 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
344 /* count the number of all descendants which are not the lowest descendant */
345 for(n_desc = 0; in[n_desc]; ++n_desc);
348 we insert a CopyKeep node to express the artificial dependencies from the lowest
349 descendant to all other descendants.
351 if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
355 for(i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
358 op = get_irn_in_or_dep(lowest_desc, i);
359 cmp = highest_is_tuple ? skip_Projs(op) : op;
361 // if(cmp == highest_node)
362 if(op == highest_node)
366 assert(i < n && "could not find operand");
368 //replace_tuple_by_repr_proj(env, &in[1]);
369 if(!is_Proj(lowest_desc))
370 add_irn_dep(lowest_desc, in[1]);
372 obstack_free(&env->obst, in);
374 /* if the current lowest node is not yet in a lineage, add it to the current one. */
375 if(!lowest_mi->lineage_start) {
376 /* mark the current lowest node as the last one in the lineage. */
377 highest_mi->lineage_next = lowest_desc;
378 start_mi->lineage_end = lowest_desc;
380 lowest_mi->lineage_start = start;
381 ir_nodeset_remove(&nodes, lowest_desc);
384 /* else we cannot extend this lineage, so break. */
388 highest_node = lowest_desc;
389 highest_mi = lowest_mi;
391 /* recompute the descendants array and the new lowest descendant. */
392 in = all_descendants(env, highest_node);
393 lowest_desc = put_lowest_in_front(env, in);
396 /* recompute the heights if desired. */
398 heights_recompute(env->heights);
401 ir_nodeset_destroy(&nodes);
404 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
408 ir_node *u_end = u->lineage_end;
409 ir_node *v_start = v->lineage_start;
410 ir_node *start = skip_Projs(v_start);
412 if(be_is_Keep(start))
415 /* set lineage end of nodes in u to end of v. */
416 irn = last = u->lineage_start;
417 mi = get_mris_irn(env, irn);
418 while(irn && irn != u_end) {
419 mi = get_mris_irn(env, irn);
420 mi->lineage_end = v->lineage_end;
422 irn = mi->lineage_next;
425 /* insert a CopyKeep to make lineage v dependent on u. */
426 if(get_irn_ins_or_deps(start) == 0)
429 if(get_irn_mode(last) == mode_T) {
430 const ir_edge_t *edge;
431 foreach_out_edge(last, edge) {
432 last = get_edge_src_irn(edge);
437 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
438 mi->lineage_next = v_start;
440 /* add a dependency from the first node in v's lineage to the last in u's */
441 add_irn_dep(u_end, v_start);
443 /* set lineage start of nodes in v to start of u. */
444 irn = v->lineage_start;
445 while(irn && irn != v->lineage_end) {
446 mris_irn_t *mi = get_mris_irn(env, irn);
447 mi->lineage_start = u->lineage_start;
448 irn = mi->lineage_next;
451 heights_recompute(env->heights);
453 mi = get_mris_irn(env, v_start);
454 list_del(&mi->lineage_list);
459 static void fuse_lineages(mris_env_t *env)
461 mris_irn_t *u, *v, *tmp1, *tmp2;
464 foreach_lineage(env, u, tmp1) {
465 foreach_lineage(env, v, tmp2) {
466 if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
467 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
468 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
469 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
472 if(fuse_two_lineages(env, u, v))
480 static mris_env_t *dump_env = NULL;
482 static void block_walker(ir_node *bl, void *data)
484 mris_env_t *env = data;
486 lineage_formation(env);
490 static int mris_edge_hook(FILE *F, ir_node *irn)
492 mris_irn_t *mi = get_mris_irn(dump_env, irn);
494 if(mi->lineage_next) {
495 fprintf(F, "edge:{sourcename:\"");
496 PRINT_NODEID(mi->lineage_next);
497 fprintf(F, "\" targetname:\"");
499 fprintf(F, "\" color:lilac}\n");
504 void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix) {
505 DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook();
507 dump_consts_local(0);
508 set_dump_node_edge_hook(mris_edge_hook);
510 dump_ir_block_graph(env->irg, suffix);
511 set_dump_node_edge_hook(old);
514 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
516 mris_env_t *env = xmalloc(sizeof(env[0]));
517 ir_graph *irg = be_get_birg_irg(birg);
519 phase_init(&env->ph, "mris", irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init, NULL);
520 env->aenv = be_get_birg_arch_env(birg);
523 env->heights = heights_new(irg);
524 INIT_LIST_HEAD(&env->lineage_head);
525 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
526 obstack_init(&env->obst);
527 irg_walk_graph(irg, firm_clear_link, NULL, NULL);
528 irg_block_walk_graph(irg, block_walker, NULL, env);
529 obstack_free(&env->obst, NULL);
530 // dump_ir_block_graph_mris(env, "-mris");
534 void be_sched_mris_free(mris_env_t *env)
536 phase_free(&env->ph);
537 heights_free(env->heights);