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"
55 #include "benodesets.h"
61 const arch_env_t *aenv;
65 struct list_head lineage_head;
67 DEBUG_ONLY(firm_dbg_module_t *dbg;)
70 typedef struct _mris_irn_t {
72 ir_node *lineage_start;
73 ir_node *lineage_next;
75 struct list_head lineage_list;
78 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
80 #define get_mris_irn(env, irn) ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
81 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
83 static void *mris_irn_data_init(ir_phase *ph, ir_node *irn, void *data)
85 mris_irn_t *mi = data ? data : phase_alloc(ph, sizeof(mi[0]));
87 memset(mi, 0, sizeof(mi[0]));
88 INIT_LIST_HEAD(&mi->lineage_list);
93 static int compute_height(mris_env_t *env, ir_node *irn, unsigned long visited)
95 mris_irn_t *mi = get_mris_irn(env, irn);
97 if(get_irn_visited(irn) >= visited) {
98 DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
103 const ir_edge_t *edge;
105 set_irn_visited(irn, visited);
108 foreach_out_edge(irn, edge) {
109 ir_node *dep = get_edge_src_irn(edge);
111 if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
112 int dep_height = compute_height(env, dep, visited);
113 mi->height = MAX(mi->height, dep_height);
118 DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
124 static void compute_heights(mris_env_t *env)
126 const ir_edge_t *edge;
127 unsigned long visited;
129 visited = get_irg_visited(env->irg) + 1;
130 set_irg_visited(env->irg, visited);
132 foreach_out_edge(env->bl, edge) {
133 ir_node *dep = get_edge_src_irn(edge);
134 if(to_appear(env, dep))
135 compute_height(env, dep, visited);
140 #define valid_node(env, dep) (to_appear(env, dep) && !be_is_Keep(dep))
142 static void grow_all_descendands(mris_env_t *env, ir_node *irn, bitset_t *visited)
144 const ir_edge_t *edge;
146 // assert(get_irn_mode(irn) != mode_T);
148 foreach_out_edge(irn, edge) {
149 ir_node *desc = get_edge_src_irn(edge);
150 if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
151 obstack_ptr_grow(&env->obst, desc);
152 bitset_add_irn(visited, desc);
156 foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
157 ir_node *desc = get_edge_src_irn(edge);
158 if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
159 obstack_ptr_grow(&env->obst, desc);
160 bitset_add_irn(visited, desc);
165 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
167 bitset_t *visited = bitset_irg_malloc(env->irg);
169 grow_all_descendands(env, irn, visited);
172 if(get_irn_mode(irn) == mode_T) {
173 const ir_edge_t *edge;
174 foreach_out_edge(irn, edge) {
175 ir_node *desc = get_edge_src_irn(edge);
176 assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
177 grow_all_descendands(env, desc, visited);
182 grow_all_descendands(env, irn, visited);
184 bitset_free(visited);
185 obstack_ptr_grow(&env->obst, NULL);
186 return obstack_finish(&env->obst);
189 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
191 int lowest_index = 0;
192 unsigned lowest_height = INT_MAX;
195 for(i = 0; in[i]; ++i) {
196 unsigned height = get_irn_height(env->heights, in[i]);
197 if(height < lowest_height) {
198 lowest_height = height;
204 ir_node *tmp = in[0];
205 in[0] = in[lowest_index];
206 in[lowest_index] = tmp;
213 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited)
215 if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
217 set_irn_visited(irn, visited);
224 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
225 ir_node *op = get_irn_n(irn, i);
227 reaches_walker(env, op, tgt, found, visited);
233 static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
236 unsigned long visited = get_irg_visited(env->irg) + 1;
238 set_irg_visited(env->irg, visited);
239 reaches_walker(env, src, tgt, &found, visited);
244 static INLINE ir_node *skip_Projs(ir_node *irn)
246 return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
250 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
254 for(i = 0; in[i]; ++i) {
255 if(get_irn_mode(in[i]) == mode_T) {
256 const ir_edge_t *edge;
257 ir_node *proj = NULL;
258 ir_node *first = NULL;
260 foreach_out_edge(in[i], edge) {
261 ir_node *desc = get_edge_src_irn(edge);
263 first = first ? first : desc;
264 if(get_irn_mode(desc) == mode_M) {
270 proj = proj ? proj : first;
278 static void lineage_formation(mris_env_t *env)
280 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg);
281 nodeset *nodes = new_nodeset(128);
283 const ir_edge_t *edge;
285 foreach_out_edge(env->bl, edge) {
286 ir_node *irn = get_edge_src_irn(edge);
287 if(to_appear(env, irn))
288 nodeset_insert(nodes, irn);
291 while(nodeset_count(nodes) > 0) {
294 ir_node *highest_node = NULL;
295 ir_node *lowest_desc = NULL;
297 mris_irn_t *start_mi;
300 int recompute_height = 0;
301 unsigned curr_height = 0;
303 /* search the highest node which is not yet in a lineage. */
304 for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) {
305 unsigned height = get_irn_height(env->heights, irn);
306 if(height > curr_height) {
308 curr_height = height;
312 assert(highest_node);
313 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
315 start = highest_node;
316 mi = start_mi = get_mris_irn(env, highest_node);
318 /* start a lineage beginning with highest_node. */
319 mi->lineage_start = highest_node;
320 mi->lineage_next = NULL;
321 mi->lineage_end = NULL;
322 list_add(&mi->lineage_list, &env->lineage_head);
323 nodeset_remove(nodes, highest_node);
326 put all descendants in an array.
327 we also move the lowest descendant in front, so that the other nodes
328 are easily accessible as an array, too.
330 in = all_descendants(env, highest_node);
331 lowest_desc = put_lowest_in_front(env, in);
333 /* as long as the current highest node has still descendants */
335 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
336 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
337 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
341 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
343 /* count the number of all descendants which are not the lowest descendant */
344 for(n_desc = 0; in[n_desc]; ++n_desc);
347 we insert a CopyKeep node to express the artificial dependencies from the lowest
348 descendant to all other descendants.
350 if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
354 for(i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
357 op = get_irn_in_or_dep(lowest_desc, i);
358 cmp = highest_is_tuple ? skip_Projs(op) : op;
360 // if(cmp == highest_node)
361 if(op == highest_node)
365 assert(i < n && "could not find operand");
367 //replace_tuple_by_repr_proj(env, &in[1]);
368 if(!is_Proj(lowest_desc))
369 add_irn_dep(lowest_desc, in[1]);
371 obstack_free(&env->obst, in);
373 /* if the current lowest node is not yet in a lineage, add it to the current one. */
374 if(!lowest_mi->lineage_start) {
375 /* mark the current lowest node as the last one in the lineage. */
376 highest_mi->lineage_next = lowest_desc;
377 start_mi->lineage_end = lowest_desc;
379 lowest_mi->lineage_start = start;
380 nodeset_remove(nodes, lowest_desc);
383 /* else we cannot extend this lineage, so break. */
387 highest_node = lowest_desc;
388 highest_mi = lowest_mi;
390 /* recompute the descendants array and the new lowest descendant. */
391 in = all_descendants(env, highest_node);
392 lowest_desc = put_lowest_in_front(env, in);
395 /* recompute the heights if desired. */
397 heights_recompute(env->heights);
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(sizeof(env[0]));
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);
517 env->aenv = be_get_birg_arch_env(birg);
520 env->heights = heights_new(irg);
521 INIT_LIST_HEAD(&env->lineage_head);
522 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
523 obstack_init(&env->obst);
524 irg_walk_graph(irg, firm_clear_link, NULL, NULL);
525 irg_block_walk_graph(irg, block_walker, NULL, env);
526 obstack_free(&env->obst, NULL);
527 // dump_ir_block_graph_mris(env, "-mris");
531 void be_sched_mris_free(mris_env_t *env)
533 phase_free(&env->ph);
534 heights_free(env->heights);