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]));
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);
280 nodeset *nodes = new_nodeset(128);
282 const ir_edge_t *edge;
284 foreach_out_edge(env->bl, edge) {
285 ir_node *irn = get_edge_src_irn(edge);
286 if(to_appear(env, irn))
287 nodeset_insert(nodes, irn);
290 while(nodeset_count(nodes) > 0) {
293 ir_node *highest_node = NULL;
294 ir_node *lowest_desc = NULL;
296 mris_irn_t *start_mi;
299 int recompute_height = 0;
300 unsigned curr_height = 0;
302 /* search the highest node which is not yet in a lineage. */
303 for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) {
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 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 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);
400 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
404 ir_node *u_end = u->lineage_end;
405 ir_node *v_start = v->lineage_start;
406 ir_node *start = skip_Projs(v_start);
408 if(be_is_Keep(start))
411 /* set lineage end of nodes in u to end of v. */
412 irn = last = u->lineage_start;
413 mi = get_mris_irn(env, irn);
414 while(irn && irn != u_end) {
415 mi = get_mris_irn(env, irn);
416 mi->lineage_end = v->lineage_end;
418 irn = mi->lineage_next;
421 /* insert a CopyKeep to make lineage v dependent on u. */
422 if(get_irn_ins_or_deps(start) == 0)
425 if(get_irn_mode(last) == mode_T) {
426 const ir_edge_t *edge;
427 foreach_out_edge(last, edge) {
428 last = get_edge_src_irn(edge);
433 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
434 mi->lineage_next = v_start;
436 /* add a dependency from the first node in v's lineage to the last in u's */
437 add_irn_dep(u_end, v_start);
439 /* set lineage start of nodes in v to start of u. */
440 irn = v->lineage_start;
441 while(irn && irn != v->lineage_end) {
442 mris_irn_t *mi = get_mris_irn(env, irn);
443 mi->lineage_start = u->lineage_start;
444 irn = mi->lineage_next;
447 heights_recompute(env->heights);
449 mi = get_mris_irn(env, v_start);
450 list_del(&mi->lineage_list);
455 static void fuse_lineages(mris_env_t *env)
457 mris_irn_t *u, *v, *tmp1, *tmp2;
460 foreach_lineage(env, u, tmp1) {
461 foreach_lineage(env, v, tmp2) {
462 if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
463 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
464 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
465 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
468 if(fuse_two_lineages(env, u, v))
476 static mris_env_t *dump_env = NULL;
478 static void block_walker(ir_node *bl, void *data)
480 mris_env_t *env = data;
482 lineage_formation(env);
486 static int mris_edge_hook(FILE *F, ir_node *irn)
488 mris_irn_t *mi = get_mris_irn(dump_env, irn);
490 if(mi->lineage_next) {
491 fprintf(F, "edge:{sourcename:\"");
492 PRINT_NODEID(mi->lineage_next);
493 fprintf(F, "\" targetname:\"");
495 fprintf(F, "\" color:lilac}\n");
500 void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix) {
501 DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook();
503 dump_consts_local(0);
504 set_dump_node_edge_hook(mris_edge_hook);
506 dump_ir_block_graph(env->irg, suffix);
507 set_dump_node_edge_hook(old);
510 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
512 mris_env_t *env = xmalloc(sizeof(env[0]));
513 ir_graph *irg = be_get_birg_irg(birg);
515 phase_init(&env->ph, "mris", irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init, NULL);
516 env->aenv = be_get_birg_arch_env(birg);
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);