2 * Copyright (C) 1995-2008 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
39 #include "irgraph_t.h"
41 #include "iredges_t.h"
43 #include "irphase_t.h"
51 #include "besched_t.h"
52 #include "beschedmris.h"
61 struct list_head lineage_head;
63 DEBUG_ONLY(firm_dbg_module_t *dbg;)
66 typedef struct _mris_irn_t {
68 ir_node *lineage_start;
69 ir_node *lineage_next;
71 struct list_head lineage_list;
74 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
76 #define get_mris_irn(env, irn) ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
77 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
79 static void *mris_irn_data_init(ir_phase *ph, const ir_node *irn, void *data)
81 mris_irn_t *mi = data ? data : phase_alloc(ph, sizeof(mi[0]));
83 memset(mi, 0, sizeof(mi[0]));
84 INIT_LIST_HEAD(&mi->lineage_list);
89 static int compute_height(mris_env_t *env, ir_node *irn, ir_visited_t visited)
91 mris_irn_t *mi = get_mris_irn(env, irn);
93 if(get_irn_visited(irn) >= visited) {
94 DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
99 const ir_edge_t *edge;
101 set_irn_visited(irn, visited);
104 foreach_out_edge(irn, edge) {
105 ir_node *dep = get_edge_src_irn(edge);
107 if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
108 int dep_height = compute_height(env, dep, visited);
109 mi->height = MAX(mi->height, dep_height);
114 DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
120 static void compute_heights(mris_env_t *env)
122 const ir_edge_t *edge;
123 ir_visited_t visited;
125 visited = get_irg_visited(env->irg) + 1;
126 set_irg_visited(env->irg, visited);
128 foreach_out_edge(env->bl, edge) {
129 ir_node *dep = get_edge_src_irn(edge);
130 if(to_appear(env, dep))
131 compute_height(env, dep, visited);
136 #define valid_node(env, dep) (to_appear(env, dep) && !be_is_Keep(dep))
138 static void grow_all_descendands(mris_env_t *env, ir_node *irn, bitset_t *visited)
140 const ir_edge_t *edge;
142 // assert(get_irn_mode(irn) != mode_T);
144 foreach_out_edge(irn, edge) {
145 ir_node *desc = get_edge_src_irn(edge);
146 if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
147 obstack_ptr_grow(&env->obst, desc);
148 bitset_add_irn(visited, desc);
152 foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
153 ir_node *desc = get_edge_src_irn(edge);
154 if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
155 obstack_ptr_grow(&env->obst, desc);
156 bitset_add_irn(visited, desc);
161 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
163 bitset_t *visited = bitset_irg_malloc(env->irg);
165 grow_all_descendands(env, irn, visited);
168 if(get_irn_mode(irn) == mode_T) {
169 const ir_edge_t *edge;
170 foreach_out_edge(irn, edge) {
171 ir_node *desc = get_edge_src_irn(edge);
172 assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
173 grow_all_descendands(env, desc, visited);
178 grow_all_descendands(env, irn, visited);
180 bitset_free(visited);
181 obstack_ptr_grow(&env->obst, NULL);
182 return obstack_finish(&env->obst);
185 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
187 int lowest_index = 0;
188 unsigned lowest_height = INT_MAX;
191 for(i = 0; in[i]; ++i) {
192 unsigned height = get_irn_height(env->heights, in[i]);
193 if(height < lowest_height) {
194 lowest_height = height;
200 ir_node *tmp = in[0];
201 in[0] = in[lowest_index];
202 in[lowest_index] = tmp;
209 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, ir_visited_t visited)
211 if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
213 set_irn_visited(irn, visited);
220 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
221 ir_node *op = get_irn_n(irn, i);
223 reaches_walker(env, op, tgt, found, visited);
229 static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
232 ir_visited_t visited = get_irg_visited(env->irg) + 1;
234 set_irg_visited(env->irg, visited);
235 reaches_walker(env, src, tgt, &found, visited);
240 static inline ir_node *skip_Projs(ir_node *irn)
242 return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
246 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
250 for(i = 0; in[i]; ++i) {
251 if(get_irn_mode(in[i]) == mode_T) {
252 const ir_edge_t *edge;
253 ir_node *proj = NULL;
254 ir_node *first = NULL;
256 foreach_out_edge(in[i], edge) {
257 ir_node *desc = get_edge_src_irn(edge);
259 first = first ? first : desc;
260 if(get_irn_mode(desc) == mode_M) {
266 proj = proj ? proj : first;
274 static void lineage_formation(mris_env_t *env)
276 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg);
278 const ir_edge_t *edge;
280 ir_nodeset_init(&nodes);
282 foreach_out_edge(env->bl, edge) {
283 ir_node *irn = get_edge_src_irn(edge);
284 if(to_appear(env, irn))
285 ir_nodeset_insert(&nodes, irn);
288 while(ir_nodeset_size(&nodes) > 0) {
291 ir_node *highest_node = NULL;
292 ir_node *lowest_desc = NULL;
294 mris_irn_t *start_mi;
295 ir_nodeset_iterator_t iter;
298 int recompute_height = 0;
299 unsigned curr_height = 0;
301 /* search the highest node which is not yet in a lineage. */
302 foreach_ir_nodeset(&nodes, irn, iter) {
303 unsigned height = get_irn_height(env->heights, irn);
304 if(height > curr_height) {
306 curr_height = height;
310 assert(highest_node);
311 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
313 start = highest_node;
314 mi = start_mi = get_mris_irn(env, highest_node);
316 /* start a lineage beginning with highest_node. */
317 mi->lineage_start = highest_node;
318 mi->lineage_next = NULL;
319 mi->lineage_end = NULL;
320 list_add(&mi->lineage_list, &env->lineage_head);
321 ir_nodeset_remove(&nodes, highest_node);
324 put all descendants in an array.
325 we also move the lowest descendant in front, so that the other nodes
326 are easily accessible as an array, too.
328 in = all_descendants(env, highest_node);
329 lowest_desc = put_lowest_in_front(env, in);
331 /* as long as the current highest node has still descendants */
333 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
334 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
335 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
339 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
341 /* count the number of all descendants which are not the lowest descendant */
342 for(n_desc = 0; in[n_desc]; ++n_desc);
345 we insert a CopyKeep node to express the artificial dependencies from the lowest
346 descendant to all other descendants.
348 if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
352 for(i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
355 op = get_irn_in_or_dep(lowest_desc, i);
356 cmp = highest_is_tuple ? skip_Projs(op) : op;
358 // if(cmp == highest_node)
359 if(op == highest_node)
363 assert(i < n && "could not find operand");
365 //replace_tuple_by_repr_proj(env, &in[1]);
366 if(!is_Proj(lowest_desc))
367 add_irn_dep(lowest_desc, in[1]);
369 obstack_free(&env->obst, in);
371 /* if the current lowest node is not yet in a lineage, add it to the current one. */
372 if(!lowest_mi->lineage_start) {
373 /* mark the current lowest node as the last one in the lineage. */
374 highest_mi->lineage_next = lowest_desc;
375 start_mi->lineage_end = lowest_desc;
377 lowest_mi->lineage_start = start;
378 ir_nodeset_remove(&nodes, lowest_desc);
381 /* else we cannot extend this lineage, so break. */
385 highest_node = lowest_desc;
386 highest_mi = lowest_mi;
388 /* recompute the descendants array and the new lowest descendant. */
389 in = all_descendants(env, highest_node);
390 lowest_desc = put_lowest_in_front(env, in);
393 /* recompute the heights if desired. */
395 heights_recompute(env->heights);
398 ir_nodeset_destroy(&nodes);
401 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
405 ir_node *u_end = u->lineage_end;
406 ir_node *v_start = v->lineage_start;
407 ir_node *start = skip_Projs(v_start);
409 if(be_is_Keep(start))
412 /* set lineage end of nodes in u to end of v. */
413 irn = last = u->lineage_start;
414 mi = get_mris_irn(env, irn);
415 while(irn && irn != u_end) {
416 mi = get_mris_irn(env, irn);
417 mi->lineage_end = v->lineage_end;
419 irn = mi->lineage_next;
422 /* insert a CopyKeep to make lineage v dependent on u. */
423 if(get_irn_ins_or_deps(start) == 0)
426 if(get_irn_mode(last) == mode_T) {
427 const ir_edge_t *edge;
428 foreach_out_edge(last, edge) {
429 last = get_edge_src_irn(edge);
434 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
435 mi->lineage_next = v_start;
437 /* add a dependency from the first node in v's lineage to the last in u's */
438 add_irn_dep(u_end, v_start);
440 /* set lineage start of nodes in v to start of u. */
441 irn = v->lineage_start;
442 while(irn && irn != v->lineage_end) {
443 mris_irn_t *mi = get_mris_irn(env, irn);
444 mi->lineage_start = u->lineage_start;
445 irn = mi->lineage_next;
448 heights_recompute(env->heights);
450 mi = get_mris_irn(env, v_start);
451 list_del(&mi->lineage_list);
456 static void fuse_lineages(mris_env_t *env)
458 mris_irn_t *u, *v, *tmp1, *tmp2;
461 foreach_lineage(env, u, tmp1) {
462 foreach_lineage(env, v, tmp2) {
463 if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
464 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
465 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
466 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
469 if(fuse_two_lineages(env, u, v))
477 static mris_env_t *dump_env = NULL;
479 static void block_walker(ir_node *bl, void *data)
481 mris_env_t *env = data;
483 lineage_formation(env);
487 static int mris_edge_hook(FILE *F, ir_node *irn)
489 mris_irn_t *mi = get_mris_irn(dump_env, irn);
491 if(mi->lineage_next) {
492 fprintf(F, "edge:{sourcename:\"");
493 PRINT_NODEID(mi->lineage_next);
494 fprintf(F, "\" targetname:\"");
496 fprintf(F, "\" color:lilac}\n");
501 void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix) {
502 DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook();
504 dump_consts_local(0);
505 set_dump_node_edge_hook(mris_edge_hook);
507 dump_ir_block_graph(env->irg, suffix);
508 set_dump_node_edge_hook(old);
511 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
513 mris_env_t *env = XMALLOC(mris_env_t);
514 ir_graph *irg = be_get_birg_irg(birg);
516 phase_init(&env->ph, "mris", irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init, NULL);
519 env->heights = heights_new(irg);
520 INIT_LIST_HEAD(&env->lineage_head);
521 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
522 obstack_init(&env->obst);
523 irg_walk_graph(irg, firm_clear_link, NULL, NULL);
524 irg_block_walk_graph(irg, block_walker, NULL, env);
525 obstack_free(&env->obst, NULL);
526 // dump_ir_block_graph_mris(env, "-mris");
530 void be_sched_mris_free(mris_env_t *env)
532 phase_free(&env->ph);
533 heights_free(env->heights);