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
21 * Implements a list scheduler for the MRIS algorithm in:
22 * Govindarajan, Yang, Amaral, Zhang, Gao
23 * Minimum Register Instruction Sequencing to Reduce Register Spills
24 * in out-of-order issue superscalar architectures
25 * @author Sebastian Hack
37 #include "irgraph_t.h"
39 #include "iredges_t.h"
41 #include "irphase_t.h"
50 #include "besched_t.h"
51 #include "beschedmris.h"
52 #include "benodesets.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, ir_node *irn, void *data)
82 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, unsigned long 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 unsigned long 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, unsigned long 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 unsigned long 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);
277 nodeset *nodes = new_nodeset(128);
279 const ir_edge_t *edge;
281 foreach_out_edge(env->bl, edge) {
282 ir_node *irn = get_edge_src_irn(edge);
283 if(to_appear(env, irn))
284 nodeset_insert(nodes, irn);
287 while(nodeset_count(nodes) > 0) {
290 ir_node *highest_node = NULL;
291 ir_node *lowest_desc = NULL;
293 mris_irn_t *start_mi;
296 int recompute_height = 0;
297 unsigned curr_height = 0;
299 /* search the highest node which is not yet in a lineage. */
300 for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) {
301 unsigned height = get_irn_height(env->heights, irn);
302 if(height > curr_height) {
304 curr_height = height;
308 assert(highest_node);
309 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
311 start = highest_node;
312 mi = start_mi = get_mris_irn(env, highest_node);
314 /* start a lineage beginning with highest_node. */
315 mi->lineage_start = highest_node;
316 mi->lineage_next = NULL;
317 mi->lineage_end = NULL;
318 list_add(&mi->lineage_list, &env->lineage_head);
319 nodeset_remove(nodes, highest_node);
322 put all descendants in an array.
323 we also move the lowest descendant in front, so that the other nodes
324 are easily accessible as an array, too.
326 in = all_descendants(env, highest_node);
327 lowest_desc = put_lowest_in_front(env, in);
329 /* as long as the current highest node has still descendants */
331 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
332 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
333 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
337 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
339 /* count the number of all descendants which are not the lowest descendant */
340 for(n_desc = 0; in[n_desc]; ++n_desc);
343 we insert a CopyKeep node to express the artificial dependencies from the lowest
344 descendant to all other descendants.
346 if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
350 for(i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
353 op = get_irn_in_or_dep(lowest_desc, i);
354 cmp = highest_is_tuple ? skip_Projs(op) : op;
356 // if(cmp == highest_node)
357 if(op == highest_node)
361 assert(i < n && "could not find operand");
363 //replace_tuple_by_repr_proj(env, &in[1]);
364 if(!is_Proj(lowest_desc))
365 add_irn_dep(lowest_desc, in[1]);
367 obstack_free(&env->obst, in);
369 /* if the current lowest node is not yet in a lineage, add it to the current one. */
370 if(!lowest_mi->lineage_start) {
371 /* mark the current lowest node as the last one in the lineage. */
372 highest_mi->lineage_next = lowest_desc;
373 start_mi->lineage_end = lowest_desc;
375 lowest_mi->lineage_start = start;
376 nodeset_remove(nodes, lowest_desc);
379 /* else we cannot extend this lineage, so break. */
383 highest_node = lowest_desc;
384 highest_mi = lowest_mi;
386 /* recompute the descendants array and the new lowest descendant. */
387 in = all_descendants(env, highest_node);
388 lowest_desc = put_lowest_in_front(env, in);
391 /* recompute the heights if desired. */
393 heights_recompute(env->heights);
397 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
401 ir_node *u_end = u->lineage_end;
402 ir_node *v_start = v->lineage_start;
403 ir_node *start = skip_Projs(v_start);
405 if(be_is_Keep(start))
408 /* set lineage end of nodes in u to end of v. */
409 irn = last = u->lineage_start;
410 mi = get_mris_irn(env, irn);
411 while(irn && irn != u_end) {
412 mi = get_mris_irn(env, irn);
413 mi->lineage_end = v->lineage_end;
415 irn = mi->lineage_next;
418 /* insert a CopyKeep to make lineage v dependent on u. */
419 if(get_irn_ins_or_deps(start) == 0)
422 if(get_irn_mode(last) == mode_T) {
423 const ir_edge_t *edge;
424 foreach_out_edge(last, edge) {
425 last = get_edge_src_irn(edge);
430 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
431 mi->lineage_next = v_start;
433 /* add a dependency from the first node in v's lineage to the last in u's */
434 add_irn_dep(u_end, v_start);
436 /* set lineage start of nodes in v to start of u. */
437 irn = v->lineage_start;
438 while(irn && irn != v->lineage_end) {
439 mris_irn_t *mi = get_mris_irn(env, irn);
440 mi->lineage_start = u->lineage_start;
441 irn = mi->lineage_next;
444 heights_recompute(env->heights);
446 mi = get_mris_irn(env, v_start);
447 list_del(&mi->lineage_list);
452 static void fuse_lineages(mris_env_t *env)
454 mris_irn_t *u, *v, *tmp1, *tmp2;
457 foreach_lineage(env, u, tmp1) {
458 foreach_lineage(env, v, tmp2) {
459 if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
460 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
461 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
462 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
465 if(fuse_two_lineages(env, u, v))
473 static mris_env_t *dump_env = NULL;
475 static void block_walker(ir_node *bl, void *data)
477 mris_env_t *env = data;
479 lineage_formation(env);
483 static int mris_edge_hook(FILE *F, ir_node *irn)
485 mris_irn_t *mi = get_mris_irn(dump_env, irn);
487 if(mi->lineage_next) {
488 fprintf(F, "edge:{sourcename:\"");
489 PRINT_NODEID(mi->lineage_next);
490 fprintf(F, "\" targetname:\"");
492 fprintf(F, "\" color:lilac}\n");
497 void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix) {
498 DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook();
500 dump_consts_local(0);
501 set_dump_node_edge_hook(mris_edge_hook);
503 dump_ir_block_graph(env->irg, suffix);
504 set_dump_node_edge_hook(old);
507 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
509 mris_env_t *env = xmalloc(sizeof(env[0]));
510 ir_graph *irg = be_get_birg_irg(birg);
512 phase_init(&env->ph, "mris", irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init, NULL);
513 env->aenv = be_get_birg_arch_env(birg);
516 env->heights = heights_new(irg);
517 INIT_LIST_HEAD(&env->lineage_head);
518 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
519 obstack_init(&env->obst);
520 irg_walk_graph(irg, firm_clear_link, NULL, NULL);
521 irg_block_walk_graph(irg, block_walker, NULL, env);
522 obstack_free(&env->obst, NULL);
523 // dump_ir_block_graph_mris(env, "-mris");
527 void be_sched_mris_free(mris_env_t *env)
529 phase_free(&env->ph);
530 heights_free(env->heights);