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"
58 const arch_env_t *aenv;
62 struct list_head lineage_head;
64 DEBUG_ONLY(firm_dbg_module_t *dbg;)
67 typedef struct _mris_irn_t {
69 ir_node *lineage_start;
70 ir_node *lineage_next;
72 struct list_head lineage_list;
75 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
77 #define get_mris_irn(env, irn) ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
78 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
80 static void *mris_irn_data_init(ir_phase *ph, const ir_node *irn, void *data)
82 mris_irn_t *mi = data ? data : phase_alloc(ph, sizeof(mi[0]));
84 memset(mi, 0, sizeof(mi[0]));
85 INIT_LIST_HEAD(&mi->lineage_list);
90 static int compute_height(mris_env_t *env, ir_node *irn, ir_visited_t visited)
92 mris_irn_t *mi = get_mris_irn(env, irn);
94 if(get_irn_visited(irn) >= visited) {
95 DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
100 const ir_edge_t *edge;
102 set_irn_visited(irn, visited);
105 foreach_out_edge(irn, edge) {
106 ir_node *dep = get_edge_src_irn(edge);
108 if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
109 int dep_height = compute_height(env, dep, visited);
110 mi->height = MAX(mi->height, dep_height);
115 DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
121 static void compute_heights(mris_env_t *env)
123 const ir_edge_t *edge;
124 ir_visited_t visited;
126 visited = get_irg_visited(env->irg) + 1;
127 set_irg_visited(env->irg, visited);
129 foreach_out_edge(env->bl, edge) {
130 ir_node *dep = get_edge_src_irn(edge);
131 if(to_appear(env, dep))
132 compute_height(env, dep, visited);
137 #define valid_node(env, dep) (to_appear(env, dep) && !be_is_Keep(dep))
139 static void grow_all_descendands(mris_env_t *env, ir_node *irn, bitset_t *visited)
141 const ir_edge_t *edge;
143 // assert(get_irn_mode(irn) != mode_T);
145 foreach_out_edge(irn, edge) {
146 ir_node *desc = get_edge_src_irn(edge);
147 if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
148 obstack_ptr_grow(&env->obst, desc);
149 bitset_add_irn(visited, desc);
153 foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
154 ir_node *desc = get_edge_src_irn(edge);
155 if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
156 obstack_ptr_grow(&env->obst, desc);
157 bitset_add_irn(visited, desc);
162 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
164 bitset_t *visited = bitset_irg_malloc(env->irg);
166 grow_all_descendands(env, irn, visited);
169 if(get_irn_mode(irn) == mode_T) {
170 const ir_edge_t *edge;
171 foreach_out_edge(irn, edge) {
172 ir_node *desc = get_edge_src_irn(edge);
173 assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
174 grow_all_descendands(env, desc, visited);
179 grow_all_descendands(env, irn, visited);
181 bitset_free(visited);
182 obstack_ptr_grow(&env->obst, NULL);
183 return obstack_finish(&env->obst);
186 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
188 int lowest_index = 0;
189 unsigned lowest_height = INT_MAX;
192 for(i = 0; in[i]; ++i) {
193 unsigned height = get_irn_height(env->heights, in[i]);
194 if(height < lowest_height) {
195 lowest_height = height;
201 ir_node *tmp = in[0];
202 in[0] = in[lowest_index];
203 in[lowest_index] = tmp;
210 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, ir_visited_t visited)
212 if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
214 set_irn_visited(irn, visited);
221 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
222 ir_node *op = get_irn_n(irn, i);
224 reaches_walker(env, op, tgt, found, visited);
230 static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
233 ir_visited_t visited = get_irg_visited(env->irg) + 1;
235 set_irg_visited(env->irg, visited);
236 reaches_walker(env, src, tgt, &found, visited);
241 static INLINE ir_node *skip_Projs(ir_node *irn)
243 return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
247 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
251 for(i = 0; in[i]; ++i) {
252 if(get_irn_mode(in[i]) == mode_T) {
253 const ir_edge_t *edge;
254 ir_node *proj = NULL;
255 ir_node *first = NULL;
257 foreach_out_edge(in[i], edge) {
258 ir_node *desc = get_edge_src_irn(edge);
260 first = first ? first : desc;
261 if(get_irn_mode(desc) == mode_M) {
267 proj = proj ? proj : first;
275 static void lineage_formation(mris_env_t *env)
277 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg);
279 const ir_edge_t *edge;
281 ir_nodeset_init(&nodes);
283 foreach_out_edge(env->bl, edge) {
284 ir_node *irn = get_edge_src_irn(edge);
285 if(to_appear(env, irn))
286 ir_nodeset_insert(&nodes, irn);
289 while(ir_nodeset_size(&nodes) > 0) {
292 ir_node *highest_node = NULL;
293 ir_node *lowest_desc = NULL;
295 mris_irn_t *start_mi;
296 ir_nodeset_iterator_t iter;
299 int recompute_height = 0;
300 unsigned curr_height = 0;
302 /* search the highest node which is not yet in a lineage. */
303 foreach_ir_nodeset(&nodes, irn, iter) {
304 unsigned height = get_irn_height(env->heights, irn);
305 if(height > curr_height) {
307 curr_height = height;
311 assert(highest_node);
312 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
314 start = highest_node;
315 mi = start_mi = get_mris_irn(env, highest_node);
317 /* start a lineage beginning with highest_node. */
318 mi->lineage_start = highest_node;
319 mi->lineage_next = NULL;
320 mi->lineage_end = NULL;
321 list_add(&mi->lineage_list, &env->lineage_head);
322 ir_nodeset_remove(&nodes, highest_node);
325 put all descendants in an array.
326 we also move the lowest descendant in front, so that the other nodes
327 are easily accessible as an array, too.
329 in = all_descendants(env, highest_node);
330 lowest_desc = put_lowest_in_front(env, in);
332 /* as long as the current highest node has still descendants */
334 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
335 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
336 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
340 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
342 /* count the number of all descendants which are not the lowest descendant */
343 for(n_desc = 0; in[n_desc]; ++n_desc);
346 we insert a CopyKeep node to express the artificial dependencies from the lowest
347 descendant to all other descendants.
349 if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
353 for(i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
356 op = get_irn_in_or_dep(lowest_desc, i);
357 cmp = highest_is_tuple ? skip_Projs(op) : op;
359 // if(cmp == highest_node)
360 if(op == highest_node)
364 assert(i < n && "could not find operand");
366 //replace_tuple_by_repr_proj(env, &in[1]);
367 if(!is_Proj(lowest_desc))
368 add_irn_dep(lowest_desc, in[1]);
370 obstack_free(&env->obst, in);
372 /* if the current lowest node is not yet in a lineage, add it to the current one. */
373 if(!lowest_mi->lineage_start) {
374 /* mark the current lowest node as the last one in the lineage. */
375 highest_mi->lineage_next = lowest_desc;
376 start_mi->lineage_end = lowest_desc;
378 lowest_mi->lineage_start = start;
379 ir_nodeset_remove(&nodes, lowest_desc);
382 /* else we cannot extend this lineage, so break. */
386 highest_node = lowest_desc;
387 highest_mi = lowest_mi;
389 /* recompute the descendants array and the new lowest descendant. */
390 in = all_descendants(env, highest_node);
391 lowest_desc = put_lowest_in_front(env, in);
394 /* recompute the heights if desired. */
396 heights_recompute(env->heights);
399 ir_nodeset_destroy(&nodes);
402 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
406 ir_node *u_end = u->lineage_end;
407 ir_node *v_start = v->lineage_start;
408 ir_node *start = skip_Projs(v_start);
410 if(be_is_Keep(start))
413 /* set lineage end of nodes in u to end of v. */
414 irn = last = u->lineage_start;
415 mi = get_mris_irn(env, irn);
416 while(irn && irn != u_end) {
417 mi = get_mris_irn(env, irn);
418 mi->lineage_end = v->lineage_end;
420 irn = mi->lineage_next;
423 /* insert a CopyKeep to make lineage v dependent on u. */
424 if(get_irn_ins_or_deps(start) == 0)
427 if(get_irn_mode(last) == mode_T) {
428 const ir_edge_t *edge;
429 foreach_out_edge(last, edge) {
430 last = get_edge_src_irn(edge);
435 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
436 mi->lineage_next = v_start;
438 /* add a dependency from the first node in v's lineage to the last in u's */
439 add_irn_dep(u_end, v_start);
441 /* set lineage start of nodes in v to start of u. */
442 irn = v->lineage_start;
443 while(irn && irn != v->lineage_end) {
444 mris_irn_t *mi = get_mris_irn(env, irn);
445 mi->lineage_start = u->lineage_start;
446 irn = mi->lineage_next;
449 heights_recompute(env->heights);
451 mi = get_mris_irn(env, v_start);
452 list_del(&mi->lineage_list);
457 static void fuse_lineages(mris_env_t *env)
459 mris_irn_t *u, *v, *tmp1, *tmp2;
462 foreach_lineage(env, u, tmp1) {
463 foreach_lineage(env, v, tmp2) {
464 if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
465 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
466 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
467 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
470 if(fuse_two_lineages(env, u, v))
478 static mris_env_t *dump_env = NULL;
480 static void block_walker(ir_node *bl, void *data)
482 mris_env_t *env = data;
484 lineage_formation(env);
488 static int mris_edge_hook(FILE *F, ir_node *irn)
490 mris_irn_t *mi = get_mris_irn(dump_env, irn);
492 if(mi->lineage_next) {
493 fprintf(F, "edge:{sourcename:\"");
494 PRINT_NODEID(mi->lineage_next);
495 fprintf(F, "\" targetname:\"");
497 fprintf(F, "\" color:lilac}\n");
502 void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix) {
503 DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook();
505 dump_consts_local(0);
506 set_dump_node_edge_hook(mris_edge_hook);
508 dump_ir_block_graph(env->irg, suffix);
509 set_dump_node_edge_hook(old);
512 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
514 mris_env_t *env = XMALLOC(mris_env_t);
515 ir_graph *irg = be_get_birg_irg(birg);
517 phase_init(&env->ph, "mris", irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init, NULL);
518 env->aenv = be_get_birg_arch_env(birg);
521 env->heights = heights_new(irg);
522 INIT_LIST_HEAD(&env->lineage_head);
523 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
524 obstack_init(&env->obst);
525 irg_walk_graph(irg, firm_clear_link, NULL, NULL);
526 irg_block_walk_graph(irg, block_walker, NULL, env);
527 obstack_free(&env->obst, NULL);
528 // dump_ir_block_graph_mris(env, "-mris");
532 void be_sched_mris_free(mris_env_t *env)
534 phase_free(&env->ph);
535 heights_free(env->heights);