2 * Implementation of a register saturating list scheduler
3 * as described in: Sid-Ahmed-Ali Touati
4 * Register Saturation in Superscalar and VLIW Codes
6 * @license This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
7 * @author Christian Wuerdig
20 #include "irgraph_t.h"
22 #include "iredges_t.h"
24 #include "irphase_t.h"
30 #include "bipartite.h"
31 #include "hungarian.h"
39 #include "besched_t.h"
41 #include <libcore/lc_opts.h>
42 #include <libcore/lc_opts_enum.h>
45 #define ARR_LEN_SAFE(arr) ((arr) != NULL ? ARR_LEN((arr)) : 0)
47 #define HASH_RSS_EDGE(edge) ((get_irn_node_nr((edge)->src) << 16) | (get_irn_node_nr((edge)->tgt) & 0xFFFF))
48 #define BSEARCH_IRN_ARR(val, arr) \
49 bsearch(&(val), (arr), ARR_LEN_SAFE((arr)), sizeof((arr)[0]), cmp_irn_idx)
51 #define BLOCK_IDX_MAP(rss, irn) bsearch_for_index(get_irn_idx((irn)), (rss)->idx_map, ARR_LEN_SAFE((rss)->idx_map), 1)
54 typedef struct _rss_opts_t {
58 /* Represents a child with associated costs */
59 typedef struct _child {
64 /* We need edges for several purposes. */
65 typedef struct _rss_edge {
71 /* Represents a connected bipartite component. */
73 ir_nodeset_t parents; /**< = S a set of value producers */
74 ir_nodeset_t children; /**< = T a set of value consumers */
75 pset *kill_edges; /**< = E a set of edges (t in T, s in S) such as each s in S gets killed by at least one t in T */
76 int nr; /**< a deterministic index for set insertion (used as hash) */
79 /* Represents a disjoint value DAG. */
85 /* Represents a chain of nodes. */
86 typedef struct _chain {
87 plist_t *elements; /**< List of chain elements */
88 int nr; /**< a deterministic index for set insertion (used as hash) */
91 typedef struct _rss_irn {
92 plist_t *consumer_list; /**< List of consumers */
93 ir_node **consumer; /**< Sorted consumer array (needed for faster access) */
95 plist_t *parent_list; /**< List of parents */
96 plist_t *pkiller_list; /**< List of potential killers */
98 plist_t *descendant_list; /**< List of descendants */
99 ir_node **descendants; /**< Sorted descendant array (needed for faster access) */
101 ir_node *killer; /**< The selected unique killer */
102 ir_node *irn; /**< The corresponding firm node to this rss_irn */
104 chain_t *chain; /**< The chain, this node is associated to */
106 unsigned desc_walk; /**< visited flag for collecting descendants */
107 unsigned kill_count; /**< number of nodes killed by this one */
109 unsigned live_out : 1; /**< irn has consumers outside of it's block */
110 unsigned visited : 1; /**< visited flag for bipartite decomposition */
111 unsigned havecons : 1; /**< visited flag collect consumer */
112 unsigned handled : 1; /**< flag indicating whether or not the list structures have been build */
113 unsigned dumped : 1; /**< flag indication whether or not this node was dumped */
116 /* Represents a serialization edge with associated costs. */
117 typedef struct _serialization {
118 rss_irn_t *u; /* the top node */
119 rss_irn_t *v; /* the node about to be serialized after u */
120 rss_edge_t *edge; /* the edge selected for the serialization */
121 int omega1; /* estimated: available regs - RS reduction */
122 int omega2; /* increase in critical path length */
126 typedef struct _rss {
127 ir_phase ph; /**< Phase to hold some data */
128 heights_t *h; /**< The current height object */
129 ir_graph *irg; /**< The irg to preprocess */
130 plist_t *nodes; /**< The list of interesting nodes */
131 const arch_env_t *arch_env; /**< The architecture environment */
132 be_abi_irg_t *abi; /**< The abi for this irg */
133 pset *cbc_set; /**< A set of connected bipartite components */
134 ir_node *block; /**< The current block in progress. */
135 int *idx_map; /**< Mapping irn indices to per block indices */
136 unsigned max_height; /**< maximum height in the current block */
137 rss_opts_t *opts; /**< The options */
138 be_lv_t *liveness; /**< The liveness information for this irg */
139 pset *live_block; /**< Values alive at end of block */
140 const arch_register_class_t *cls; /**< The current register class */
141 DEBUG_ONLY(firm_dbg_module_t *dbg);
144 #define get_rss_irn(rss, irn) (phase_get_or_set_irn_data(&rss->ph, irn))
147 * We need some special nodes:
148 * a source and a sink for all live-in and live-out values of a block
156 /** The opcode of the rss_Source node once allocated. */
157 static ir_op *op_rss_Source;
158 /** The opcode of the rss_Sink node once allocated. */
159 static ir_op *op_rss_Sink;
161 /** The rss_Source node of the current graph. */
162 static ir_node *_source = NULL;
163 /** The rss_Sink node of the current graph. */
164 static ir_node *_sink = NULL;
166 #define is_Source(irn) ((irn) == _source)
167 #define is_Sink(irn) ((irn) == _sink)
171 RSS_DUMP_CBC = 1 << 0,
172 RSS_DUMP_PKG = 1 << 1,
173 RSS_DUMP_KILL = 1 << 2,
174 RSS_DUMP_DVG = 1 << 3,
175 RSS_DUMP_MAXAC = 1 << 4,
176 RSS_DUMP_ALL = (RSS_DUMP_MAXAC << 1) - 1,
179 static rss_opts_t rss_options = {
183 static const lc_opt_enum_int_items_t dump_items[] = {
184 { "none", RSS_DUMP_NONE },
185 { "cbc", RSS_DUMP_CBC },
186 { "pkg", RSS_DUMP_PKG },
187 { "kill", RSS_DUMP_KILL },
188 { "dvg", RSS_DUMP_DVG },
189 { "maxac", RSS_DUMP_MAXAC },
190 { "all", RSS_DUMP_ALL },
194 static lc_opt_enum_int_var_t dump_var = {
195 &rss_options.dump_flags, dump_items
198 static const lc_opt_table_entry_t rss_option_table[] = {
199 LC_OPT_ENT_ENUM_MASK("dump", "dump phases", &dump_var),
203 /******************************************************************************
205 * | | | | / _| | | (_)
206 * | |__ ___| |_ __ ___ _ __ | |_ _ _ _ __ ___| |_ _ ___ _ __ ___
207 * | '_ \ / _ \ | '_ \ / _ \ '__| | _| | | | '_ \ / __| __| |/ _ \| '_ \/ __|
208 * | | | | __/ | |_) | __/ | | | | |_| | | | | (__| |_| | (_) | | | \__ \
209 * |_| |_|\___|_| .__/ \___|_| |_| \__,_|_| |_|\___|\__|_|\___/|_| |_|___/
212 ******************************************************************************/
215 * Acquire opcodes if needed and create source and sink nodes.
217 static void init_rss_special_nodes(ir_graph *irg) {
220 if (op_rss_Source == NULL) {
221 int iro_rss_base = get_next_ir_opcodes(iro_rss_last);
222 op_rss_Source = new_ir_op(iro_rss_base + iro_rss_Source, "rss_Source", op_pin_state_pinned, irop_flag_none, oparity_zero, 0, 0, NULL);
223 op_rss_Sink = new_ir_op(iro_rss_base + iro_rss_Sink, "rss_Sink", op_pin_state_pinned, irop_flag_none, oparity_zero, 0, 0, NULL);
225 block = get_irg_start_block(irg);
226 _source = new_ir_node(NULL, irg, block, op_rss_Source, mode_ANY, 0, NULL);
227 _sink = new_ir_node(NULL, irg, block, op_rss_Sink, mode_ANY, 0, NULL);
230 static int cmp_int(const void *a, const void *b) {
234 return QSORT_CMP(*i1, *i2);
237 static int cmp_child_costs(const void *a, const void *b) {
238 const child_t *c1 = a;
239 const child_t *c2 = b;
241 return QSORT_CMP(c1->cost, c2->cost);
244 static int cmp_irn_idx(const void *a, const void *b) {
245 const ir_node *n1 = *(ir_node **)a;
246 const ir_node *n2 = *(ir_node **)b;
248 return QSORT_CMP(get_irn_idx(n1), get_irn_idx(n2));
251 static int cmp_rss_edges(const void *a, const void *b) {
252 const rss_edge_t *e1 = a;
253 const rss_edge_t *e2 = b;
255 return (e1->src != e2->src) || (e1->tgt != e2->tgt);
258 static int bsearch_for_index(int key, int *arr, size_t len, int force) {
262 while (right >= left) {
263 int idx = (left + right) / 2;
267 else if (key > arr[idx])
274 assert(0 && "Something is wrong, key not found.");
278 static ir_node **build_sorted_array_from_list(plist_t *irn_list, struct obstack *obst) {
281 int len = plist_count(irn_list);
282 ir_node **arr = NEW_ARR_D(ir_node *, obst, len);
284 /* copy the list into the array */
285 foreach_plist(irn_list, el) {
286 arr[i++] = plist_element_get_value(el);
289 /* sort the array by node index */
290 qsort(arr, len, sizeof(arr[0]), cmp_irn_idx);
295 /*****************************************************
298 * __| | ___| |__ _ _ __ _ __ _ _ _ __ __ _
299 * / _` |/ _ \ '_ \| | | |/ _` |/ _` | | '_ \ / _` |
300 * | (_| | __/ |_) | |_| | (_| | (_| | | | | | (_| |
301 * \__,_|\___|_.__/ \__,_|\__, |\__, |_|_| |_|\__, |
305 *****************************************************/
308 static void dump_nodeset(ir_nodeset_t *ns, const char *prefix) {
309 ir_nodeset_iterator_t iter;
312 ir_nodeset_iterator_init(&iter, ns);
313 while( (irn = ir_nodeset_iterator_next(&iter)) != NULL ) {
314 ir_fprintf(stderr, "%s%+F\n", prefix, irn);
319 static void build_file_name(rss_t *rss, const char *suffix, size_t suf_len, char *buf, size_t len) {
320 const char *irg_name;
323 irg_name = get_entity_name(get_irg_entity(rss->irg));
324 snprintf(buf, len - suf_len, "%s-%s-block-%ld",
325 irg_name, arch_register_class_name(rss->cls), get_irn_node_nr(rss->block));
329 /* Dumps all collected bipartite components of current irg as vcg. */
330 static void debug_vcg_dump_bipartite(rss_t *rss) {
334 static const char suffix[] = "-RSS-CBC.vcg";
336 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
337 f = fopen(file_name, "w");
339 ir_fprintf(f, "graph: { title: \"connected bipartite component graph of %+F\"\n", rss->irg);
340 fprintf(f, "display_edge_labels: no\n");
341 fprintf(f, "layoutalgorithm: mindepth\n");
342 fprintf(f, "manhattan_edges: yes\n\n");
344 foreach_pset(rss->cbc_set, cbc) {
345 ir_nodeset_iterator_t iter;
349 fprintf(f, "graph: { titel: \"cbc %d\" label: \"cbc %d\" status:clustered color:yellow\n", cbc->nr, cbc->nr);
350 foreach_ir_nodeset(&cbc->parents, n, iter) {
351 ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
353 foreach_ir_nodeset(&cbc->children, n, iter) {
354 ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
356 foreach_pset(cbc->kill_edges, ke) {
357 ir_fprintf(f, "edge: { sourcename: \"n%d_%d\" targetname: \"n%d_%d\" }\n",
358 get_irn_node_nr(ke->src), cbc->nr, get_irn_node_nr(ke->tgt), cbc->nr);
366 /* Dump the computed killing function as vcg. */
367 static void debug_vcg_dump_kill(rss_t *rss) {
371 static const char suffix[] = "-RSS-KILL.vcg";
373 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
374 f = fopen(file_name, "w");
376 ir_fprintf(f, "graph: { title: \"computed kill graph of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
377 fprintf(f, "display_edge_labels: no\n");
378 fprintf(f, "layoutalgorithm: mindepth\n");
379 fprintf(f, "manhattan_edges: yes\n\n");
382 /* reset dump_flag */
384 foreach_phase_irn(&rss->ph, irn) {
385 rss_irn_t *node = get_rss_irn(rss, irn);
390 /* dump all nodes and their killers */
391 foreach_plist(rss->nodes, el) {
392 ir_node *irn = plist_element_get_value(el);
393 rss_irn_t *rirn = get_rss_irn(rss, irn);
394 rss_irn_t *pk_rirn = get_rss_irn(rss, rirn->killer);
396 if (! rirn->dumped) {
397 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
401 if (! pk_rirn->dumped) {
402 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(rirn->killer), rirn->killer);
406 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
407 get_irn_node_nr(rirn->killer), get_irn_node_nr(irn));
414 /* Dumps the potential killing DAG (PKG) as vcg. */
415 static void debug_vcg_dump_pkg(rss_t *rss, ir_nodeset_t *max_ac, int iteration) {
418 char *suffix = alloca(32);
419 static const char suffix1[] = "-RSS-PKG.vcg";
420 static const char suffix2[] = "-RSS-PKG-MAXAC.vcg";
424 snprintf(suffix, 32, "%s", suffix1);
427 snprintf(suffix, 32, "-%02d%s", iteration, suffix2);
430 build_file_name(rss, suffix, strlen(suffix) + 1, file_name, sizeof(file_name));
431 f = fopen(file_name, "w");
433 ir_fprintf(f, "graph: { title: \"potential killing DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
434 fprintf(f, "display_edge_labels: no\n");
435 fprintf(f, "layoutalgorithm: mindepth\n");
436 fprintf(f, "manhattan_edges: yes\n\n");
439 /* reset dump_flag */
441 foreach_phase_irn(&rss->ph, irn) {
442 rss_irn_t *node = get_rss_irn(rss, irn);
447 foreach_plist(rss->nodes, el) {
448 ir_node *irn = plist_element_get_value(el);
449 rss_irn_t *rirn = get_rss_irn(rss, irn);
451 plist_element_t *k_el;
453 /* dump selected saturating values in yellow */
454 if (max_ac && ir_nodeset_contains(max_ac, irn))
457 if (! rirn->dumped) {
459 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(irn), irn, rirn->chain->nr, c1);
461 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(irn), irn, c1);
465 foreach_plist(rirn->pkiller_list, k_el) {
466 ir_node *pkiller = plist_element_get_value(k_el);
467 rss_irn_t *pk_rirn = get_rss_irn(rss, pkiller);
470 if (max_ac && ir_nodeset_contains(max_ac, pkiller))
473 if (! pk_rirn->dumped) {
475 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(pkiller), pkiller, pk_rirn->chain->nr, c2);
477 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(pkiller), pkiller, c2);
480 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
481 get_irn_node_nr(pkiller), get_irn_node_nr(irn));
488 /* Dumps the disjoint value DAG (DVG) as vcg. */
489 static void debug_vcg_dump_dvg(rss_t *rss, dvg_t *dvg) {
490 static const char suffix[] = "-RSS-DVG.vcg";
493 ir_nodeset_iterator_t iter;
497 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
498 f = fopen(file_name, "w");
500 ir_fprintf(f, "graph: { title: \"disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
501 fprintf(f, "display_edge_labels: no\n");
502 fprintf(f, "layoutalgorithm: mindepth\n");
503 fprintf(f, "manhattan_edges: yes\n\n");
506 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
507 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
511 foreach_pset(dvg->edges, edge) {
512 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
513 get_irn_node_nr(edge->src), get_irn_node_nr(edge->tgt));
521 /* Dumps the PKG(DVG). */
522 static void debug_vcg_dump_dvg_pkiller(rss_t *rss, dvg_t *dvg) {
523 static const char suffix[] = "-RSS-DVG-PKG.vcg";
526 ir_nodeset_iterator_t iter;
529 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
530 f = fopen(file_name, "w");
532 ir_fprintf(f, "graph: { title: \"PKG of disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
533 fprintf(f, "display_edge_labels: no\n");
534 fprintf(f, "layoutalgorithm: mindepth\n");
535 fprintf(f, "manhattan_edges: yes\n\n");
538 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
539 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
543 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
544 rss_irn_t *node = get_rss_irn(rss, irn);
547 foreach_plist(node->dvg_pkiller_list, el) {
548 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
549 get_irn_node_nr(plist_element_get_value(el)), get_irn_node_nr(irn));
559 * In case there is no rss information for irn, initialize it.
561 static void *init_rss_irn(ir_phase *ph, ir_node *irn, void *old) {
562 rss_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
564 res->descendant_list = plist_obstack_new(phase_obst(ph));
565 res->descendants = NULL;
567 res->consumer_list = plist_obstack_new(phase_obst(ph));
568 res->consumer = NULL;
570 res->pkiller_list = plist_obstack_new(phase_obst(ph));
572 res->parent_list = plist_obstack_new(phase_obst(ph));
590 * Collect all nodes data dependent on current node.
592 static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int *got_sink, unsigned cur_desc_walk) {
593 const ir_edge_t *edge;
594 rss_irn_t *cur_node = get_rss_irn(rss, irn);
595 ir_node *block = rss->block;
596 ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
599 if (cur_node->desc_walk >= cur_desc_walk)
601 cur_node->desc_walk = cur_desc_walk;
603 /* Stop at Barriers */
604 if (be_is_Barrier(irn))
607 /* loop over normal and dependency edges */
608 for (i = 0; i < 2; ++i) {
609 foreach_out_edge_kind(irn, edge, ekind[i]) {
610 ir_node *user = get_edge_src_irn(edge);
612 /* skip ignore nodes as they do not really contribute to register pressure */
613 if (arch_irn_is(rss->arch_env, user, ignore))
617 (a) mode_X means Jump -> out_edge
618 (b) Phi as user of a normal node -> out-edge
620 if (get_irn_mode(user) == mode_X || is_Phi(user)) {
629 //if (arch_get_irn_reg_class(rss->arch_env, user, -1) == rss->cls)
630 collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
633 /* check if user lives in block and is not a control flow node */
634 if (get_nodes_block(user) == block) {
635 if (! plist_has_value(rirn->descendant_list, user)) {
636 plist_insert_back(rirn->descendant_list, user);
637 DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", user));
639 collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
641 else if (! *got_sink) {
643 /* user lives out of block: add sink as descendant if not already done */
644 plist_insert_back(rirn->descendant_list, _sink);
646 DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", _sink));
654 * Handles a single consumer.
656 static void collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *consumer, int *got_sink) {
657 ir_node *block = rss->block;
659 assert(! is_Proj(consumer) && "Cannot handle Projs");
661 if (! is_Phi(consumer) && ! is_Block(consumer) && get_nodes_block(consumer) == block) {
662 if (! arch_irn_is(rss->arch_env, consumer, ignore) && ! plist_has_value(rss_irn->consumer_list, consumer)) {
663 plist_insert_back(rss_irn->consumer_list, consumer);
664 DBG((rss->dbg, LEVEL_2, "\t\tconsumer %+F\n", consumer));
668 rss_irn->live_out = 1;
669 DBG((rss->dbg, LEVEL_2, "\t\tlive out %+F", consumer));
671 plist_insert_back(rss_irn->consumer_list, _sink);
673 DB((rss->dbg, LEVEL_2, ", %+F added instead", _sink));
675 DB((rss->dbg, LEVEL_2, "\n"));
680 * Collect all nodes consuming the value(s) produced by current node.
682 static void collect_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *irn, int *got_sink) {
683 const ir_edge_t *edge;
685 ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
686 rss_irn_t *cur_node = get_rss_irn(rss, irn);
688 if (cur_node->havecons)
690 cur_node->havecons = 1;
692 for (i = 0; i < 2; ++i) {
693 foreach_out_edge_kind(irn, edge, ekind[i]) {
694 ir_node *consumer = get_edge_src_irn(edge);
696 if (is_Proj(consumer)) {
697 //if (arch_get_irn_reg_class(rss->arch_env, consumer, -1) == rss->cls)
698 collect_consumer(rss, rss_irn, consumer, got_sink);
701 collect_single_consumer(rss, rss_irn, consumer, got_sink);
707 * Collects all consumer and descendant of a irn.
709 static void collect_node_info(rss_t *rss, ir_node *irn) {
710 static unsigned cur_desc_walk = 0;
711 rss_irn_t *rss_irn = get_rss_irn(rss, irn);
714 assert(! is_Proj(irn) && "Cannot handle Projs.");
716 /* check if node info is already available */
717 if (rss_irn->handled)
719 //phase_reinit_single_irn_data(&rss->ph, irn);
721 DBG((rss->dbg, LEVEL_1, "\tcomputing consumers of %+F:\n", irn));
723 /* collect all consumer */
725 collect_consumer(rss, rss_irn, irn, &got_sink);
727 /* build sorted consumer array */
728 rss_irn->consumer = build_sorted_array_from_list(rss_irn->consumer_list, phase_obst(&rss->ph));
730 DBG((rss->dbg, LEVEL_1, "\tcompute descendants of %+F:\n", irn));
732 /* collect descendants */
734 collect_descendants(rss, rss_irn, irn, &got_sink, ++cur_desc_walk);
736 /* build sorted descendant array */
737 rss_irn->descendants = build_sorted_array_from_list(rss_irn->descendant_list, phase_obst(&rss->ph));
739 rss_irn->handled = 1;
743 * Checks if v is a potential killer of u.
744 * v is in pkill(u) iff descendants(v) cut consumer(u) is v
746 * @param rss The rss object
747 * @param v The node to check for killer
748 * @param u The potentially killed value
749 * @return 1 if v is in pkill(u), 0 otherwise
751 static int is_potential_killer(rss_t *rss, rss_irn_t *v, rss_irn_t *u) {
756 assert(is_Sink(v->irn) || ((plist_count(v->descendant_list) > 0 && v->descendants) || 1));
757 assert(is_Sink(u->irn) || ((plist_count(u->consumer_list) > 0 && u->consumer) || 1));
759 /* as we loop over the list: loop over the shorter one */
760 if (plist_count(v->descendant_list) > plist_count(u->consumer_list)) {
761 list = u->consumer_list;
762 arr = v->descendants;
765 list = v->descendant_list;
769 /* for each list element: try to find element in array */
770 foreach_plist(list, el) {
771 ir_node *irn = plist_element_get_value(el);
772 ir_node *match = BSEARCH_IRN_ARR(irn, arr);
774 if (match && match != irn)
782 * Update descendants, consumer and pkiller list for the given irn.
784 static void update_node_info(rss_t *rss, ir_node *irn, ir_node *pk_irn) {
785 rss_irn_t *node = get_rss_irn(rss, irn);
786 rss_irn_t *pkiller = get_rss_irn(rss, pk_irn);
788 /* add consumer and rebuild the consumer array */
789 if (! plist_has_value(node->consumer_list, pk_irn)) {
790 plist_insert_back(node->consumer_list, pk_irn);
791 node->consumer = build_sorted_array_from_list(node->consumer_list, phase_obst(&rss->ph));
794 /* add pk_irn as descendant, add it's descendants to irn's and rebuild array */
795 if (! plist_has_value(node->descendant_list, pk_irn)) {
798 plist_insert_back(node->descendant_list, pk_irn);
800 foreach_plist(pkiller->descendant_list, el) {
801 ir_node *desc = plist_element_get_value(el);
803 if (! plist_has_value(node->descendant_list, desc))
804 plist_insert_back(node->descendant_list, desc);
807 node->descendants = build_sorted_array_from_list(node->descendant_list, phase_obst(&rss->ph));
813 * Compute the potential killing set PK.
815 static void compute_pkill_set(rss_t *rss) {
816 plist_element_t *u_el, *v_el;
818 foreach_plist(rss->nodes, u_el) {
819 ir_node *u_irn = plist_element_get_value(u_el);
820 rss_irn_t *u = get_rss_irn(rss, u_irn);
822 DBG((rss->dbg, LEVEL_1, "\tcomputing potential killers of %+F:\n", u_irn));
824 /* check each consumer if it is a potential killer */
825 foreach_plist(u->consumer_list, v_el) {
826 ir_node *v_irn = plist_element_get_value(v_el);
827 rss_irn_t *v = get_rss_irn(rss, v_irn);
829 /* check, if v is a potential killer of u */
830 if (is_potential_killer(rss, v, u)) {
831 if (! plist_has_value(u->pkiller_list, v_irn))
832 plist_insert_back(u->pkiller_list, v_irn);
834 DBG((rss->dbg, LEVEL_2, "\t\tpotential killer %+F\n", v_irn));
841 if (rss->opts->dump_flags & RSS_DUMP_PKG)
842 debug_vcg_dump_pkg(rss, NULL, 0);
846 * Build set of killing edges (from values to their potential killers)
848 static void build_kill_edges(rss_t *rss, pset *epk) {
849 plist_element_t *el, *k_el;
851 foreach_plist(rss->nodes, el) {
852 ir_node *irn = plist_element_get_value(el);
853 rss_irn_t *rirn = get_rss_irn(rss, irn);
855 DBG((rss->dbg, LEVEL_3, "\t\tbuilding kill edges for %+F:\n", irn));
857 foreach_plist(rirn->pkiller_list, k_el) {
858 ir_node *pkiller = plist_element_get_value(k_el);
859 rss_edge_t *ke = obstack_alloc(phase_obst(&rss->ph), sizeof(*ke));
865 DBG((rss->dbg, LEVEL_3, "\t\t\ttarget %+F\n", pkiller));
867 pset_insert(epk, ke, HASH_RSS_EDGE(ke));
873 /* print the given cbc for debugging purpose */
874 static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc) {
875 ir_nodeset_iterator_t iter;
879 DBG((mod, LEVEL_3, "\t\tS = set of parents:\n"));
880 foreach_ir_nodeset(&cbc->parents, n, iter) {
881 DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
883 DBG((mod, LEVEL_3, "\t\tT = set of children:\n"));
884 foreach_ir_nodeset(&cbc->children, n, iter) {
885 DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
887 DBG((mod, LEVEL_3, "\t\tE = Edges from producers to consumers\n"));
888 foreach_pset(cbc->kill_edges, ke) {
889 DBG((mod, LEVEL_3, "\t\t\t%+F -> %+F\n", ke->src, ke->tgt));
895 * Construct the bipartite decomposition.
896 * Sid-Ahmed-Ali Touati, Phd Thesis
897 * Register Pressure in Instruction Level Parallelism, p. 71
899 static void compute_bipartite_decomposition(rss_t *rss) {
900 pset *epk = new_pset(cmp_rss_edges, 10);
905 DBG((rss->dbg, LEVEL_1, "\tcomputing bipartite decomposition:\n"));
907 build_kill_edges(rss, epk);
909 foreach_plist(rss->nodes, el) {
910 ir_node *u_irn = plist_element_get_value(el);
911 rss_irn_t *u = get_rss_irn(rss, u_irn);
917 plist_element_t *el2;
919 rss_edge_t *kedge_root = NULL;
920 ir_node *t_irn, *s_irn;
921 ir_nodeset_iterator_t iter;
923 if (u->visited || u_irn == _sink)
926 DBG((rss->dbg, LEVEL_2, "\t\t%+F choosen:\n", u_irn));
928 cbc = obstack_alloc(phase_obst(&rss->ph), sizeof(*cbc));
931 /* initialize S_cb */
932 ir_nodeset_init_size(&cbc->parents, 5);
933 ir_nodeset_insert(&cbc->parents, u_irn);
934 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (init)\n", u_irn));
937 cbc->kill_edges = new_pset(cmp_rss_edges, 5);
939 /* each parent gets killed by at least one value from children */
941 /* T_cb = PK_successors(u) */
942 ir_nodeset_init_size(&cbc->children, 5);
943 foreach_plist(u->pkiller_list, el2) {
944 ir_nodeset_insert(&cbc->children, plist_element_get_value(el2));
945 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (init)\n", plist_element_get_value(el2)));
949 Now: insert the parents of all children into the parent set
950 and insert the children of all parents into the children set
951 until the sets don't change any more
953 while (p_change || c_change) {
954 ir_nodeset_iterator_t iter;
955 p_change = c_change = 0;
957 /* accumulate parents */
958 foreach_ir_nodeset(&cbc->children, t_irn, iter) {
959 foreach_pset(epk, k_edge) {
960 ir_node *val = k_edge->src;
962 if (k_edge->tgt == t_irn && ! ir_nodeset_contains(&cbc->parents, val)) {
963 ir_nodeset_insert(&cbc->parents, val);
965 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (killed by %+F)\n", val, t_irn));
970 /* accumulate children */
971 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
972 foreach_pset(epk, k_edge) {
973 ir_node *val = k_edge->tgt;
975 if (k_edge->src == s_irn && ! ir_nodeset_contains(&cbc->children, val)) {
976 ir_nodeset_insert(&cbc->children, val);
978 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (kills %+F)\n", val, s_irn));
984 /* mark all parent values as visited */
985 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
986 rss_irn_t *s = get_rss_irn(rss, s_irn);
988 /* assure bipartite property */
990 if (ir_nodeset_contains(&cbc->children, s_irn)) {
991 ir_nodeset_remove(&cbc->children, s_irn);
992 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F removed from to children\n", s_irn));
998 foreach_pset(epk, k_edge) {
999 if (ir_nodeset_contains(&cbc->parents, k_edge->src) &&
1000 ir_nodeset_contains(&cbc->children, k_edge->tgt)) {
1001 pset_insert(cbc->kill_edges, k_edge, HASH_RSS_EDGE(k_edge));
1003 Link all k_edges which are about to be removed together.
1004 Beware: pset_remove kills the iterator.
1006 k_edge->next = kedge_root;
1007 kedge_root = k_edge;
1011 /* remove all linked k_edges */
1012 for (; kedge_root; kedge_root = kedge_root->next) {
1013 pset_remove(epk, kedge_root, HASH_RSS_EDGE(kedge_root));
1016 /* verify the cbc */
1017 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
1020 foreach_pset(cbc->kill_edges, k_edge) {
1021 if (k_edge->src == s_irn) {
1023 pset_break(cbc->kill_edges);
1030 ir_fprintf(stderr, "Warning: parent %+F is not killed in current cbc\n", s_irn);
1033 assert(vrfy_ok && "Verification of CBC failed");
1035 /* add the connected bipartite component */
1036 if (ir_nodeset_size(&cbc->parents) > 0 &&
1037 ir_nodeset_size(&cbc->children) > 0 &&
1038 pset_count(cbc->kill_edges) > 0)
1039 pset_insert(rss->cbc_set, cbc, (unsigned)cbc->nr);
1040 DBG((rss->dbg, LEVEL_2, "\tbipartite component %d inserted:\n", cbc->nr));
1042 if (firm_dbg_get_mask(rss->dbg) & LEVEL_2)
1043 debug_print_cbc(rss->dbg, cbc);
1047 if (rss->opts->dump_flags & RSS_DUMP_CBC)
1048 debug_vcg_dump_bipartite(rss);
1054 * Select the child with the maximum cost.
1056 static child_t *select_child_max_cost(rss_t *rss, ir_nodeset_t *x, ir_nodeset_t *y, child_t *t, cbc_t *cbc) {
1058 ir_nodeset_iterator_t iter;
1059 float max_cost = -1.0f;
1061 DBG((rss->dbg, LEVEL_2, "\t\tcomputing children costs:\n"));
1063 foreach_ir_nodeset(&cbc->children, child, iter) {
1064 rss_irn_t *r_child = get_rss_irn(rss, child);
1065 int num_unkilled_parents = 0;
1066 int num_descendants;
1070 /* get the number of unkilled parents */
1071 foreach_pset(cbc->kill_edges, k_edge) {
1072 if (k_edge->tgt == child && ir_nodeset_contains(x, k_edge->src))
1073 ++num_unkilled_parents;
1076 cost = (float)num_unkilled_parents;
1078 num_descendants = plist_count(r_child->descendant_list) + ir_nodeset_size(y);
1080 if (num_descendants > 0)
1081 cost /= (float)num_descendants;
1083 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F, #desc %d, cost %.3f\n", child, num_descendants, cost));
1085 if (cost > max_cost) {
1096 * Remove all parents from x which are killed by t_irn.
1098 static void remove_covered_parents(rss_t *rss, ir_nodeset_t *x, ir_node *t_irn, cbc_t *cbc) {
1099 rss_irn_t *t = get_rss_irn(rss, t_irn);
1102 DBG((rss->dbg, LEVEL_2, "\t\tremoving parents covered by %+F:\n", t_irn));
1104 foreach_pset(cbc->kill_edges, k_edge) {
1105 if (k_edge->tgt == t_irn && ir_nodeset_contains(x, k_edge->src)) {
1106 ir_nodeset_remove(x, k_edge->src);
1107 plist_insert_back(t->parent_list, k_edge->src);
1108 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", k_edge->src));
1113 static void update_cumulated_descendent_values(rss_t *rss, ir_nodeset_t *y, ir_node *t_irn) {
1114 rss_irn_t *t = get_rss_irn(rss, t_irn);
1115 plist_element_t *el;
1117 DBG((rss->dbg, LEVEL_2, "\t\tupdating cumulated descendant value of %+F:\n", t_irn));
1119 foreach_plist(t->descendant_list, el) {
1120 ir_nodeset_insert(y, plist_element_get_value(el));
1121 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", plist_element_get_value(el)));
1126 * Greedy-k: a heuristics for the MMA problem
1128 static void compute_killing_function(rss_t *rss) {
1130 struct obstack obst;
1132 obstack_init(&obst);
1134 rss->cbc_set = pset_new_ptr(5);
1135 compute_bipartite_decomposition(rss);
1137 /* for all bipartite components do: */
1138 foreach_pset(rss->cbc_set, cbc) {
1142 ir_nodeset_iterator_t iter;
1143 child_t **sks = NEW_ARR_F(child_t *, 20);
1148 ir_nodeset_init_size(&x, 10);
1149 ir_nodeset_init_size(&y, 10);
1151 DBG((rss->dbg, LEVEL_1, "\tcomputing SKS for cbc %d:\n", cbc->nr));
1152 DBG((rss->dbg, LEVEL_2, "\t\tinitializing parents X:\n"));
1154 /* X = S_cb (all parents are initially uncovered) */
1155 foreach_ir_nodeset(&cbc->parents, p, iter) {
1156 ir_nodeset_insert(&x, p);
1157 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", p));
1160 /* while X not empty */
1161 while (ir_nodeset_size(&x) > 0) {
1162 child_t *t = obstack_alloc(&obst, sizeof(*t));
1163 memset(t, 0, sizeof(*t));
1165 t = select_child_max_cost(rss, &x, &y, t, cbc);
1167 if (cur_len >= cur_size) {
1168 ARR_EXTO(child_t *, sks, cur_size * 2);
1172 DBG((rss->dbg, LEVEL_2, "\t\tinsert child %+F (%.3f) into SKS at pos %d\n", t->irn, t->cost, cur_len));
1175 remove_covered_parents(rss, &x, t->irn, cbc);
1176 update_cumulated_descendent_values(rss, &y, t->irn);
1179 ARR_SHRINKLEN(sks, cur_len);
1181 /* sort SKS in increasing cost order */
1182 qsort(sks, cur_len, sizeof(sks[0]), cmp_child_costs);
1184 DBG((rss->dbg, LEVEL_2, "\tprocessing SKS for cbc %d:\n", cbc->nr));
1186 /* build killing function */
1187 for (i = cur_len - 1; i >= 0; --i) { /* loop over sks in decreasing cost order */
1188 child_t *t = sks[i];
1189 rss_irn_t *rt = get_rss_irn(rss, t->irn);
1190 plist_element_t *p_el;
1192 DBG((rss->dbg, LEVEL_3, "\t\t\tkiller %+F (%.3f):\n", t->irn, t->cost));
1194 /* kill all unkilled parents of t */
1195 foreach_plist(rt->parent_list, p_el) {
1196 ir_node *par = plist_element_get_value(p_el);
1197 rss_irn_t *rpar = get_rss_irn(rss, par);
1199 if (is_Sink(rpar->killer)) {
1200 rpar->killer = t->irn;
1201 DBG((rss->dbg, LEVEL_2, "\t\tkill %+F\n", rpar->irn));
1204 DBG((rss->dbg, LEVEL_3, "\t\t\tkeeping %+F as killer for %+F\n", rpar->killer, rpar->irn));
1209 ir_nodeset_destroy(&x);
1210 ir_nodeset_destroy(&y);
1214 if (rss->opts->dump_flags & RSS_DUMP_KILL)
1215 debug_vcg_dump_kill(rss);
1217 del_pset(rss->cbc_set);
1218 obstack_free(&obst, NULL);
1222 * Adds the edge src -> tgt to the dvg. Checks if reverse edge is already there (asserts).
1224 static INLINE void add_dvg_edge(rss_t *rss, dvg_t *dvg, ir_node *src, ir_node *tgt, int have_source) {
1225 rss_edge_t *dvg_edge;
1229 ir_nodeset_insert(&dvg->nodes, src);
1231 assert(ir_nodeset_contains(&dvg->nodes, src) && "Wrong assumption");
1233 ir_nodeset_insert(&dvg->nodes, tgt);
1237 assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
1241 if (NULL != pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
1242 /* add the edge to the DVG */
1243 dvg_edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*dvg_edge));
1245 dvg_edge->src = src;
1246 dvg_edge->tgt = tgt;
1247 dvg_edge->next = NULL;
1249 DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", src, tgt));
1250 pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
1255 * Computes the disjoint value DAG (DVG).
1256 * BEWARE: It is not made explicitly clear in the Touati paper,
1257 * but the DVG is meant to be build from the KILLING DAG
1259 static void compute_dvg(rss_t *rss, dvg_t *dvg) {
1260 plist_element_t *el;
1262 DBG((rss->dbg, LEVEL_1, "\tcomputing DVG:\n"));
1264 foreach_plist(rss->nodes, el) {
1265 ir_node *u_irn = plist_element_get_value(el);
1266 rss_irn_t *u = get_rss_irn(rss, u_irn);
1267 rss_irn_t *u_killer = get_rss_irn(rss, u->killer);
1270 /* TODO: omit nodes only having sink as pkiller and killing no one */
1272 /* add an edge to killer */
1273 add_dvg_edge(rss, dvg, u_irn, u->killer, 0);
1275 if (is_Sink(u->killer))
1278 /* We add an edge to every killer, from where we could be reached. */
1279 for (i = ARR_LEN_SAFE(u_killer->descendants) - 1; i >= 0; --i) {
1280 add_dvg_edge(rss, dvg, u_irn, u_killer->descendants[i], 1);
1285 foreach_plist(rss->nodes, el2) {
1286 ir_node *v_irn = plist_element_get_value(el2);
1289 There is an edge (u, v) in the DVG iff v is a descendant of the killer(u).
1291 if (BSEARCH_IRN_ARR(v_irn, u_kill->descendants)) {
1292 rss_edge_t *dvg_edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*dvg_edge));
1295 /* insert the user into the DVG and append it to the user list of u */
1296 ir_nodeset_insert(&dvg->nodes, v_irn);
1297 if (! plist_has_value(u->dvg_user_list, v_irn))
1298 plist_insert_back(u->dvg_user_list, v_irn);
1300 dvg_edge->src = u_irn;
1301 dvg_edge->tgt = v_irn;
1302 dvg_edge->next = NULL;
1307 assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
1309 /* add the edge to the DVG */
1310 DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", u_irn, v_irn));
1311 pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
1317 if (rss->opts->dump_flags & RSS_DUMP_DVG)
1318 debug_vcg_dump_dvg(rss, dvg);
1322 * Updates the dvg structure when a serialization edge from src -> tgt is added.
1324 static void update_dvg(rss_t *rss, dvg_t *dvg, rss_irn_t *src, rss_irn_t *tgt) {
1327 rss_edge_t **arr = alloca(pset_count(dvg->edges) * sizeof(arr[0]));
1330 Add an edge from serialization target to serialization src:
1331 src cannot be alive with target
1333 add_dvg_edge(rss, dvg, tgt->irn, src->irn, 0);
1335 /* Add edges to src's descendants as well, they also getting serialized. */
1336 for (i = ARR_LEN_SAFE(src->descendants) - 1; i >= 0; --i) {
1337 add_dvg_edge(rss, dvg, tgt->irn, src->descendants[i], 1);
1340 /* We also have to add edges from targets predecessors in dvg */
1342 /* We cannot insert elements into set over which we iterate ... */
1343 foreach_pset(dvg->edges, edge) {
1344 if (edge->tgt == tgt->irn) {
1349 for (i = 0; i < idx; ++i) {
1351 add_dvg_edge(rss, dvg, edge->src, src->irn, 1);
1352 for (j = ARR_LEN_SAFE(src->descendants) - 1; j >= 0; --j) {
1353 add_dvg_edge(rss, dvg, edge->src, src->descendants[j], 1);
1360 * Accumulate all descendants for root into list.
1362 static void accumulate_dvg_descendant_values(rss_t *rss, rss_irn_t *root, plist_t *list) {
1363 if (plist_count(root->dvg_user_list) > 0) {
1364 plist_element_t *el;
1366 foreach_plist(root->dvg_user_list, el) {
1367 ir_node *v_irn = plist_element_get_value(el);
1368 rss_irn_t *v = get_rss_irn(rss, v_irn);
1370 /* add v as descendant */
1371 if (! plist_has_value(list, v_irn)) {
1372 plist_insert_back(list, v_irn);
1373 DBG((rss->dbg, DEBUG_DVG, "\t\t\tadd DVG descendant %+F\n", v_irn));
1376 /* accumulate v's descendants */
1377 accumulate_dvg_descendant_values(rss, v, list);
1383 * Builds the list of potential killers for each node
1385 * Needs the descendant list for all user as sorted array.
1387 static void build_dvg_pkiller_list(rss_t *rss, dvg_t *dvg) {
1388 ir_nodeset_iterator_t iter;
1391 foreach_nodeset(&dvg->nodes, irn, iter) {
1392 rss_irn_t *node = get_rss_irn(rss, irn);
1393 plist_element_t *el, *el2;
1395 DBG((rss->dbg, DEBUG_DVG, "\t\tbuilding pkiller list for %+F\n", irn));
1397 /* check each user */
1398 foreach_plist(node->dvg_user_list, el) {
1399 ir_node *u_irn = plist_element_get_value(el);
1401 /* is the current user u_irn not a descendant of any other user -> pkiller */
1402 foreach_plist(node->dvg_user_list, el2) {
1403 ir_node *v_irn = plist_element_get_value(el2);
1404 rss_irn_t *v = get_rss_irn(rss, v_irn);
1407 ! BSEARCH_IRN_ARR(u_irn, v->dvg_desc) &&
1408 ! plist_has_value(node->dvg_pkiller_list, u_irn))
1410 plist_insert_back(node->dvg_pkiller_list, u_irn);
1411 DBG((rss->dbg, DEBUG_DVG, "\t\t\tadd DVG pkiller %+F\n", u_irn));
1416 node->dvg_pkiller = build_sorted_array_from_list(node->dvg_pkiller_list, phase_obst(&rss->ph));
1420 if (firm_dbg_get_mask(rss->dbg) & DEBUG_DVG)
1421 debug_vcg_dump_dvg_pkiller(rss, dvg);
1428 * Compute the maximal antichain of the current DVG.
1429 * This is a reimplementation of the MAXIMAL_ANTI_CHAIN function
1430 * from the DDG library 1.1 (DAG.cpp).
1432 static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration) {
1433 int n = ir_nodeset_size(&dvg->nodes);
1434 int *assignment = alloca(n * sizeof(assignment[0]));
1435 int *assignment_rev = alloca(n * sizeof(assignment_rev[0]));
1436 int *idx_map = alloca(n * sizeof(idx_map[0]));
1437 hungarian_problem_t *bp;
1438 ir_nodeset_t *values, *temp;
1439 ir_nodeset_iterator_t iter;
1441 int i, j, cost, cur_chain, res;
1442 rss_edge_t *dvg_edge;
1444 #define MAP_IDX(irn) bsearch_for_index(get_irn_idx(irn), idx_map, n, 1)
1446 if (pset_count(dvg->edges) == 0)
1449 bp = hungarian_new(n, n, 1, HUNGARIAN_MATCH_NORMAL);
1452 At first, we build an index map for the nodes in the DVG,
1453 because we cannot use the irn idx therefore as the resulting
1454 bipartite data structure would have around 1.2GB.
1455 So we limit the size to the number of nodes we have in the DVG
1456 and build a sorted index map for their irn indices.
1459 foreach_ir_nodeset(&dvg->nodes, u_irn, iter) {
1460 idx_map[i++] = get_irn_idx(u_irn);
1462 qsort(idx_map, n, sizeof(idx_map[0]), cmp_int);
1464 foreach_pset(dvg->edges, dvg_edge) {
1465 int idx_u = MAP_IDX(dvg_edge->src);
1466 int idx_v = MAP_IDX(dvg_edge->tgt);
1468 /* add the entry to the bipartite data structure */
1469 hungarian_add(bp, idx_u, idx_v, 1);
1470 DBG((rss->dbg, LEVEL_3, "\t\t\tadd %d (%+F) -> %d (%+F)\n",
1471 idx_u, dvg_edge->src, idx_v, dvg_edge->tgt));
1475 Add a bipartite entry for each pair of nodes (u, v), where exists a
1476 path in the DVG from u to v, ie. connect all descendants(v) to v.
1477 desc_dvg(v) = accumulated descendants of all z in dvg_user_list(v)
1479 foreach_ir_nodeset(&dvg->nodes, u_irn, iter) {
1480 rss_irn_t *u = get_rss_irn(rss, u_irn);
1481 int idx_u_irn = MAP_IDX(u_irn);
1483 DBG((rss->dbg, DEBUG_DVG, "\t\tcomputing DVG descendants of %+F:\n", u_irn));
1485 //plist_clear(u->dvg_desc_list);
1486 //accumulate_dvg_descendant_values(rss, u, u->dvg_desc_list);
1489 FIXME: The array is build on the phase obstack and we cannot free the data.
1490 So the array get as many times allocated as this function is called.
1493 /* build the sorted array for faster searches */
1494 //u->dvg_desc = build_sorted_array_from_list(u->dvg_desc_list, phase_obst(&rss->ph));
1496 DBG((rss->dbg, DEBUG_MAX_AC, "\t\tadding bipartite entries of %+F:\n", u_irn));
1498 /* add the bipartite entries for all descendants */
1499 for (i = ARR_LEN_SAFE(u->dvg_desc) - 1; i >= 0; --i) {
1500 rss_irn_t *desc = get_rss_irn(rss, u->dvg_desc[i]);
1501 int idx_desc = MAP_IDX(u->dvg_desc[i]);
1503 /* add the entry to the bipartite data structure */
1504 hungarian_add(bp, idx_u_irn, idx_desc, 1);
1505 DBG((rss->dbg, DEBUG_MAX_AC, "\t\t\tadd %d (%+F) -> %d (%+F)\n",
1506 idx_u_irn, u_irn, idx_desc, u->dvg_desc[i]));
1513 /* We want maximum cardinality matching */
1514 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
1517 DBG((rss->dbg, DEBUG_DVG, "\t\tcomputing DVG pkiller:\n"));
1518 /* beware: the following function needs the dvg_desc array */
1519 build_dvg_pkiller_list(rss, dvg);
1522 DBG((rss->dbg, LEVEL_2, "\t\tcomputing bipartite matching\n"));
1524 The maximum cardinality bipartite matching gives us the minimal
1525 chain partition, which corresponds to the maximum anti chains.
1527 res = hungarian_solve(bp, assignment, &cost, 1);
1528 assert(res == 0 && "Bipartite matching failed!");
1531 memset(assignment_rev, -1, n * sizeof(assignment_rev[0]));
1533 /* build the reverse assignment, ie. foreach i -> j, add j -> i */
1534 for (i = 0; i < n; ++i) {
1535 if (assignment[i] >= 0) {
1536 int j = assignment[i];
1537 assignment_rev[j] = i;
1541 DBG((rss->dbg, LEVEL_2, "\t\tgot assignment with cost %d\n", cost));
1542 DBG((rss->dbg, LEVEL_3, "\t\t\tassignment --- reverse assignment\n", cost));
1543 for (i = 0; i < n; ++i) {
1544 DBG((rss->dbg, LEVEL_3, "\t\t\t%3d -> %3d %3d -> %3d\n", i, assignment[i], i, assignment_rev[i]));
1547 values = xmalloc(sizeof(values[0]));
1548 ir_nodeset_init_size(values, 10);
1550 /* Construction of the minimal chain partition */
1551 for (j = 0; j < n; ++j) {
1552 /* check nodes, which did not occur as target */
1553 if (assignment_rev[j] == -1) {
1554 int xj = idx_map[j];
1555 ir_node *xj_irn = get_idx_irn(rss->irg, xj);
1556 rss_irn_t *xj_rss = get_rss_irn(rss, xj_irn);
1557 chain_t *c = obstack_alloc(phase_obst(&rss->ph), sizeof(*c));
1560 /* there was no source for j -> we have a source of a new chain */
1561 ir_nodeset_insert(values, xj_irn);
1563 c->elements = plist_obstack_new(phase_obst(&rss->ph));
1564 c->nr = cur_chain++;
1565 plist_insert_back(c->elements, xj_irn);
1569 DBG((rss->dbg, LEVEL_2, "\t\tstarting chain %d:\n", c->nr));
1570 DBG((rss->dbg, LEVEL_2, "\t\t\t%+F (%d)", xj_irn, j));
1572 /* follow chain, having j as source */
1574 while (assignment[source] >= 0) {
1575 int target = assignment[source];
1576 int irn_idx = idx_map[target];
1577 ir_node *irn = get_idx_irn(rss->irg, irn_idx);
1578 rss_irn_t *node = get_rss_irn(rss, irn);
1580 plist_insert_back(c->elements, irn);
1583 DB((rss->dbg, LEVEL_2, " -> %+F (%d)", irn, target));
1585 /* new source = last target */
1589 DB((rss->dbg, LEVEL_2, "\n"));
1594 Computing the maximal antichain: Select an element from each
1595 chain such, such it is parallel with the others.
1597 DBG((rss->dbg, LEVEL_1, "\t\tcomputing set of saturation values (MAX AC)\n"));
1598 DBG((rss->dbg, LEVEL_3, "\t\tstarting with:\n"));
1601 if (firm_dbg_get_mask(rss->dbg) & LEVEL_3)
1602 dump_nodeset(values, "\t\t\t");
1608 We need an explicit array for the values as
1609 we cannot iterate multiple times over the same
1610 set at the same time. :-(((((
1611 TODO Matze: now we can, so rewrite this...
1613 int n = ir_nodeset_size(values);
1615 ir_node **val_arr = NEW_ARR_F(ir_node *, n);
1617 foreach_ir_nodeset(values, u_irn, iter)
1618 val_arr[i++] = u_irn;
1621 ir_nodeset_destroy(temp);
1625 temp = xmalloc(sizeof(temp[0]));
1626 ir_nodeset_init_size(temp, 10);
1628 /* Select all nodes from current value set, having another node in the set as descendant. */
1629 for (i = 0; i < n; ++i) {
1630 rss_irn_t *u = get_rss_irn(rss, val_arr[i]);
1632 for (j = 0; j < n; ++j) {
1636 key.src = val_arr[i];
1637 key.tgt = val_arr[j];
1639 if (pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
1640 /* v[j] is descendant of u -> remove u and break */
1641 ir_nodeset_insert(temp, u->irn);
1642 ir_nodeset_remove(values, u->irn);
1644 DBG((rss->dbg, LEVEL_3, "\t\t\tremoving %+F from values, adding it to temp\n", u->irn));
1652 /* Try to insert the chain predecessor of all selected u's */
1653 foreach_ir_nodeset(temp, u_irn, iter) {
1654 rss_irn_t *u = get_rss_irn(rss, u_irn);
1655 chain_t *c = u->chain;
1656 plist_element_t *el = plist_find_value(c->elements, u_irn);
1658 assert(el && "Missing element in chain!");
1660 /* If u has predecessor in chain: insert the predecessor */
1661 if (el == plist_element_get_prev(el)) {
1662 ir_nodeset_insert(values, plist_element_get_value(el));
1663 DBG((rss->dbg, LEVEL_3, "\t\t\tadding %+F to values\n", plist_element_get_value(el)));
1669 } while (ir_nodeset_size(temp) > 0);
1671 DBG((rss->dbg, LEVEL_2, "\t\tfinal set:\n"));
1673 if (firm_dbg_get_mask(rss->dbg) & LEVEL_2) {
1674 dump_nodeset(values, "\t\t\t");
1678 if (rss->opts->dump_flags & RSS_DUMP_MAXAC)
1679 debug_vcg_dump_pkg(rss, values, iteration);
1682 ir_nodeset_destroy(temp);
1692 * Computes the best serialization between two nodes of sat_vals.
1694 static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nodeset_t *sat_vals, serialization_t *ser, int num_regs) {
1695 int n = ir_nodeset_size(sat_vals);
1696 int n_idx = ARR_LEN_SAFE(rss->idx_map);
1698 ir_node **val_arr = alloca(n * sizeof(val_arr[0]));
1699 bitset_t *bs_sv = bitset_alloca(n_idx);
1700 bitset_t *bs_vdesc = bitset_alloca(n_idx);
1701 bitset_t *bs_tmp = bitset_alloca(n_idx);
1702 bitset_t *bs_ukilldesc = bitset_alloca(n_idx);
1703 int best_benefit = INT_MAX;
1704 int best_omega2 = INT_MAX;
1705 int best_benefit_omega20 = INT_MAX;
1709 ir_nodeset_iterator_t iter;
1710 rss_edge_t min_benefit_edge;
1711 rss_edge_t min_omega20_edge;
1712 rss_irn_t *ser_u_omega1 = NULL, *ser_v_omega1 = NULL;
1713 rss_irn_t *ser_u_omega20 = NULL, *ser_v_omega20 = NULL;
1715 DBG((rss->dbg, LEVEL_1, "\tcomputing admissible serializations:\n"));
1718 We need an explicit array for the values as
1719 we cannot iterate multiple times over the same
1720 set at the same time. :-(((((
1723 foreach_ir_nodeset(sat_vals, irn, iter) {
1725 bitset_set(bs_sv, BLOCK_IDX_MAP(rss, irn));
1729 We build all admissible serializations and remember the best found so far.
1732 if v in pkiller(u): add edge from v to all other pkiller(u)
1733 else: for all vv in pkiller(u): add edge from v to vv if there exists no path from vv to v
1737 A node is unserializable if:
1738 - it has only one killer and this one is Sink
1739 - it kills no other values
1740 In this case there is no serialization which could
1741 reduce the registerpressure
1743 #define IS_UNSERIALIZABLE_NODE(rss_node) \
1746 (plist_count(rss_node->pkiller_list) == 1) && \
1747 is_Sink(rss_node->killer) && \
1748 (rss_node->kill_count == 0) \
1750 be_is_Barrier(rss_node->irn) || \
1751 be_is_Keep(rss_node->irn) \
1754 /* for all u in sat_vals */
1755 for (i = 0; i < n; ++i) {
1756 rss_irn_t *u = get_rss_irn(rss, val_arr[i]);
1757 plist_element_t *el;
1759 /* ignore nodes where serialization does not help */
1760 if (IS_UNSERIALIZABLE_NODE(u)) {
1761 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", u->irn));
1765 /* accumulate all descendants of all pkiller(u) */
1766 bitset_clear_all(bs_ukilldesc);
1767 foreach_plist(u->pkiller_list, el) {
1768 ir_node *irn = plist_element_get_value(el);
1769 rss_irn_t *node = get_rss_irn(rss, irn);
1772 bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, irn));
1776 for (k = ARR_LEN_SAFE(node->descendants) - 1; k >= 0; --k) {
1777 if (! is_Sink(node->descendants[k]))
1778 bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, node->descendants[k]));
1782 /* for all v in sat_vals */
1783 for (j = 0; j < n; ++j) {
1784 ir_node *v_irn = val_arr[j];
1785 rss_irn_t *v = get_rss_irn(rss, v_irn);
1786 unsigned v_height = get_irn_height(rss->h, v_irn);
1787 int omega1, omega2, is_pkiller;
1789 /* v cannot be serialized with itself
1790 * ignore nodes where serialization does not help */
1791 if (i == j || IS_UNSERIALIZABLE_NODE(v)) {
1793 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", v->irn));
1797 /* get descendants of v */
1798 bitset_clear_all(bs_vdesc);
1799 bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v_irn));
1800 for (k = ARR_LEN_SAFE(v->descendants) - 1; k >= 0; --k) {
1801 if (! is_Sink(v->descendants[k]))
1802 bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v->descendants[k]));
1805 /* if v is in pkiller(u) */
1806 is_pkiller = plist_has_value(u->pkiller_list, v_irn);
1808 /* for all vv in pkiller(u) */
1809 foreach_plist(u->pkiller_list, el) {
1810 ir_node *vv_irn = plist_element_get_value(el);
1813 if (is_Sink(vv_irn) || is_cfop(vv_irn))
1817 add_edge = vv_irn != v_irn && skip_Proj(vv_irn) != skip_Proj(v_irn);
1819 add_edge = ! heights_reachable_in_block(rss->h, skip_Proj(vv_irn), skip_Proj(v_irn));
1822 As we add an edge from vv -> v, we have to make sure,
1823 that there exists no path from v to vv.
1827 int vv_height = get_irn_height(rss->h, vv_irn);
1828 int mu1, mu2, critical_path_cost;
1831 mu1 = | descendants(v) cut sat_vals |
1832 the number of saturating values which cannot
1833 be simultaneously alive with u
1835 bitset_copy(bs_tmp, bs_vdesc);
1836 mu1 = bitset_popcnt(bitset_and(bs_tmp, bs_sv));
1839 mu2 = | accum_desc_all_pkiller(u) without descendants(v) |
1842 bitset_copy(bs_tmp, bs_ukilldesc);
1843 mu2 = bitset_popcnt(bitset_andnot(bs_tmp, bs_vdesc));
1849 /* omega1 = mu1 - mu2 */
1855 /* omega2 = increase of critical path */
1856 critical_path_cost =
1857 v_height /* longest path from v to sink */
1858 + rss->max_height - vv_height /* longest path from source to vv */
1862 If critical_path_cost > max_height -> the new edge
1863 would increase the longest critical path by the difference.
1865 omega2 = critical_path_cost > rss->max_height ? critical_path_cost - rss->max_height : 0;
1867 /* this keeps track of the edge with the best benefit */
1868 if (omega1 >= num_regs - n && omega1 < best_benefit) {
1869 min_benefit_edge.src = v_irn;
1870 min_benefit_edge.tgt = vv_irn;
1875 best_benefit = omega1;
1876 ser->new_killer = is_pkiller;
1879 /* this keeps track of the edge with the best omega1 costs where omega2 == 0 */
1880 if (omega2 == 0 && omega1 >= num_regs - n && omega1 < best_benefit_omega20) {
1881 min_omega20_edge.src = v_irn;
1882 min_omega20_edge.tgt = vv_irn;
1887 best_benefit_omega20 = omega1;
1888 ser->new_killer = is_pkiller;
1891 best_omega2 = MIN(best_omega2, omega2);
1893 DBG((rss->dbg, LEVEL_2, "\t\tfound %+F -> %+F (w1 %d, w2 %d)\n",
1894 v_irn, vv_irn, omega1, omega2));
1896 } /* for all vv in pkiller(u) */
1897 } /* for all v in sat_vals */
1898 } /* for all u in sat_vals */
1903 if (best_omega2 == 0) {
1904 ser->u = ser_u_omega20;
1905 ser->v = ser_v_omega20;
1906 ser->edge->src = min_omega20_edge.src;
1907 ser->edge->tgt = min_omega20_edge.tgt;
1908 ser->omega1 = best_benefit_omega20;
1909 ser->omega2 = best_omega2;
1912 ser->u = ser_u_omega1;
1913 ser->v = ser_v_omega1;
1914 ser->edge->src = min_benefit_edge.src;
1915 ser->edge->tgt = min_benefit_edge.tgt;
1916 ser->omega1 = best_benefit;
1917 ser->omega2 = best_omega2;
1922 #undef IS_UNSERIALIZABLE_NODE
1926 * Perform the value serialization heuristic and add all
1927 * computed serialization edges as dependencies to the irg.
1929 static void perform_value_serialization_heuristic(rss_t *rss) {
1930 bitset_t *arch_nonign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls));
1931 bitset_t *abi_ign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls));
1932 int available_regs, iteration;
1934 ir_nodeset_t *sat_vals;
1935 pset *ser_set = new_pset(cmp_rss_edges, 20);
1937 /* available_regs = R = |arch_non_ignore_regs cut ~abi_ignore_regs| */
1938 arch_put_non_ignore_regs(rss->arch_env, rss->cls, arch_nonign_bs);
1939 be_abi_put_ignore_regs(rss->abi, rss->cls, abi_ign_bs);
1940 bitset_andnot(arch_nonign_bs, abi_ign_bs);
1941 available_regs = bitset_popcnt(arch_nonign_bs);
1942 //num_live = pset_count(rss->live_block);
1943 //available_regs -= num_live < available_regs ? num_live : 0;
1945 DBG((rss->dbg, LEVEL_1, "\n\t#available regs: %d\n\n", available_regs));
1948 At first we need to compute the disjoint value DAG (DVG = {V, E_dv}).
1949 V = set of all nodes we are currently interested in
1950 E_dv = there is an edge from u to v iff v is a descendant of killer(u), forall u, v in V
1952 ir_nodeset_init_size(&dvg.nodes, plist_count(rss->nodes));
1953 dvg.edges = new_pset(cmp_rss_edges, plist_count(rss->nodes) * 5);
1954 compute_dvg(rss, &dvg);
1957 Then we perform the heuristic serialization algorithm
1958 on the DVG which gives us all necessary serialization
1961 DBG((rss->dbg, LEVEL_1, "\tcomputing maximal antichain:\n"));
1963 sat_vals = compute_maximal_antichain(rss, &dvg, iteration++);
1964 while (sat_vals && (ir_nodeset_size(sat_vals) > available_regs)) {
1965 serialization_t *ser, best_ser;
1966 rss_edge_t *edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*edge));
1967 ir_node *dep_src, *dep_tgt;
1969 best_ser.edge = edge;
1970 ser = compute_best_admissible_serialization(rss, sat_vals, &best_ser, available_regs);
1972 DBG((rss->dbg, LEVEL_1, "\tcurrent register saturation %d, target %d\n", ir_nodeset_size(sat_vals), available_regs));
1975 DBG((rss->dbg, LEVEL_1, "\tno RS improving serialization found, breaking at iteration %d\n", iteration));
1979 /* Insert the serialization as dependency edge into the irg. */
1980 DBG((rss->dbg, LEVEL_1, "\tserializing %+F -> %+F with edge %+F -> %+F and cost %d, %d\n",
1981 ser->u->irn, ser->v->irn, ser->edge->src, ser->edge->tgt, ser->omega1, ser->omega2));
1983 if (pset_find(ser_set, ser->edge, HASH_RSS_EDGE(ser->edge)))
1984 ir_printf("WARNING: serialization %+F -> %+F computed twice!\n", ser->edge->src, ser->edge->tgt);
1987 pset_insert(ser_set, ser->edge, HASH_RSS_EDGE(ser->edge));
1989 /* update the dvg */
1990 update_dvg(rss, &dvg, ser->v, ser->u);
1991 update_dvg(rss, &dvg, get_rss_irn(rss, ser->edge->src), get_rss_irn(rss, ser->edge->tgt));
1992 if(sat_vals != NULL) {
1993 ir_nodeset_destroy(sat_vals);
1997 dep_src = skip_Proj(ser->edge->src);
1998 dep_tgt = ser->edge->tgt;
1999 add_irn_dep(dep_src, dep_tgt);
2001 /* Update descendants, consumer and pkillers of the target */
2002 update_node_info(rss, ser->edge->tgt, ser->edge->src);
2004 /* TODO: try to find a cheaper way for updating height information */
2005 rss->max_height = heights_recompute_block(rss->h, rss->block);
2007 /* Recompute the antichain for next serialization */
2008 DBG((rss->dbg, LEVEL_1, "\tre-computing maximal antichain:\n"));
2009 sat_vals = compute_maximal_antichain(rss, &dvg, iteration++);
2012 ir_nodeset_destroy(&dvg.nodes);
2013 del_pset(dvg.edges);
2017 * Do initial calculations for a block.
2019 static void process_block(ir_node *block, void *env) {
2022 const ir_edge_t *edge;
2024 phase_init(&rss->ph, "rss block preprocessor", rss->irg, PHASE_DEFAULT_GROWTH, init_rss_irn);
2026 DBG((rss->dbg, LEVEL_1, "preprocessing block %+F\n", block));
2029 /* build an index map for all nodes in the current block */
2031 n = get_irn_n_edges(block);
2032 NEW_ARR_A(int *, rss->idx_map, n);
2033 foreach_out_edge(block, edge) {
2034 ir_node *irn = get_edge_src_irn(edge);
2035 rss->idx_map[i++] = get_irn_idx(irn);
2037 qsort(rss->idx_map, n, sizeof(rss->idx_map[0]), cmp_int);
2038 rss->max_height = heights_recompute_block(rss->h, block);
2040 /* loop over all register classes */
2041 for (i = arch_isa_get_n_reg_class(rss->arch_env->isa) - 1; i >= 0; --i) {
2042 const arch_register_class_t *cls = arch_isa_get_reg_class(rss->arch_env->isa, i);
2045 DBG((rss->dbg, LEVEL_1, "register class %s\n", arch_register_class_name(cls)));
2047 /* Get all live value at end of Block having current register class */
2048 rss->live_block = pset_new_ptr(10);
2049 be_liveness_end_of_block(rss->liveness, rss->arch_env, rss->cls, rss->block, rss->live_block);
2051 /* reset the list of interesting nodes */
2052 plist_clear(rss->nodes);
2053 plist_insert_back(rss->nodes, _sink);
2055 /* collect all nodes having a certain register class */
2056 foreach_out_edge(block, edge) {
2057 ir_node *irn = get_edge_src_irn(edge);
2058 ir_mode *mode = get_irn_mode(irn);
2062 - mode_T nodes (the projs are asked)
2063 - mode_X nodes (control flow nodes are always scheduled last)
2064 - Keeps (they are always immediately scheduled)
2065 - Phi (same as Keep)
2067 if (mode == mode_T || mode == mode_X || is_Phi(irn))
2071 In case of a proj, we skip
2072 - Barrier (they are a Barrier :)
2074 - the Proj itself, as it's scheduled always with it's super node
2077 ir_node *pred = get_Proj_pred(irn);
2078 if (be_is_Barrier(pred) || is_Start(pred))
2082 /* calculate the descendants and consumer for each node in the block */
2083 collect_node_info(rss, skip_Proj(irn));
2085 if (be_is_Keep(irn))
2088 if (! arch_irn_is(rss->arch_env, irn, ignore) && arch_get_irn_reg_class(rss->arch_env, irn, -1) == cls) {
2089 plist_insert_back(rss->nodes, skip_Proj(irn));
2094 /* compute the potential killing set PK(G) */
2095 compute_pkill_set(rss);
2097 /* compute the killing function k* */
2098 compute_killing_function(rss);
2101 Compute the heuristic value serialization and
2102 add the necessary dependencies to the irg.
2104 perform_value_serialization_heuristic(rss);
2106 del_pset(rss->live_block);
2109 phase_free(&rss->ph);
2113 * Register the options.
2115 void be_init_schedrss(void) {
2116 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
2117 lc_opt_entry_t *sched_grp = lc_opt_get_grp(be_grp, "sched");
2118 lc_opt_entry_t *rss_grp = lc_opt_get_grp(sched_grp, "rss");
2120 lc_opt_add_table(rss_grp, rss_option_table);
2123 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_schedrss);
2126 * Preprocess the irg for scheduling.
2128 void rss_schedule_preparation(const be_irg_t *birg) {
2131 FIRM_DBG_REGISTER(rss.dbg, "firm.be.sched.rss");
2133 //firm_dbg_set_mask(rss.dbg, LEVEL_1 | LEVEL_2 | LEVEL_3);
2135 init_rss_special_nodes(birg->irg);
2137 rss.irg = birg->irg;
2138 rss.arch_env = birg->main_env->arch_env;
2139 rss.abi = birg->abi;
2140 rss.h = heights_new(birg->irg);
2141 rss.nodes = plist_new();
2142 rss.opts = &rss_options;
2143 rss.liveness = be_liveness(birg->irg);
2144 irg_block_walk_graph(birg->irg, NULL, process_block, &rss);
2145 heights_free(rss.h);
2146 plist_free(rss.nodes);
2147 be_liveness_free(rss.liveness);
2149 if (birg->main_env->options->dump_flags & DUMP_SCHED)
2150 be_dump(rss.irg, "-rss", dump_ir_block_graph);