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"
42 #include <libcore/lc_opts.h>
43 #include <libcore/lc_opts_enum.h>
46 #define ARR_LEN_SAFE(arr) ((arr) != NULL ? ARR_LEN((arr)) : 0)
48 #define HASH_RSS_EDGE(edge) ((get_irn_node_nr((edge)->src) << 16) | (get_irn_node_nr((edge)->tgt) & 0xFFFF))
49 #define BSEARCH_IRN_ARR(val, arr) \
50 bsearch(&(val), (arr), ARR_LEN_SAFE((arr)), sizeof((arr)[0]), cmp_irn_idx)
52 #define BLOCK_IDX_MAP(rss, irn) bsearch_for_index(get_irn_idx((irn)), (rss)->idx_map, ARR_LEN_SAFE((rss)->idx_map), 1)
55 typedef struct _rss_opts_t {
59 /* Represents a child with associated costs */
60 typedef struct _child {
65 /* We need edges for several purposes. */
66 typedef struct _rss_edge {
72 /* Represents a connected bipartite component. */
74 ir_nodeset_t parents; /**< = S a set of value producers */
75 ir_nodeset_t children; /**< = T a set of value consumers */
76 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 */
77 int nr; /**< a deterministic index for set insertion (used as hash) */
80 /* Represents a disjoint value DAG. */
86 /* Represents a chain of nodes. */
87 typedef struct _chain {
88 plist_t *elements; /**< List of chain elements */
89 int nr; /**< a deterministic index for set insertion (used as hash) */
92 typedef struct _rss_irn {
93 plist_t *consumer_list; /**< List of consumers */
94 ir_node **consumer; /**< Sorted consumer array (needed for faster access) */
96 plist_t *parent_list; /**< List of parents */
97 plist_t *pkiller_list; /**< List of potential killers */
99 plist_t *descendant_list; /**< List of descendants */
100 ir_node **descendants; /**< Sorted descendant array (needed for faster access) */
102 ir_node *killer; /**< The selected unique killer */
103 ir_node *irn; /**< The corresponding firm node to this rss_irn */
105 chain_t *chain; /**< The chain, this node is associated to */
107 unsigned desc_walk; /**< visited flag for collecting descendants */
108 unsigned kill_count; /**< number of nodes killed by this one */
110 unsigned live_out : 1; /**< irn has consumers outside of it's block */
111 unsigned visited : 1; /**< visited flag for bipartite decomposition */
112 unsigned havecons : 1; /**< visited flag collect consumer */
113 unsigned handled : 1; /**< flag indicating whether or not the list structures have been build */
114 unsigned dumped : 1; /**< flag indication whether or not this node was dumped */
117 /* Represents a serialization edge with associated costs. */
118 typedef struct _serialization {
119 rss_irn_t *u; /* the top node */
120 rss_irn_t *v; /* the node about to be serialized after u */
121 rss_edge_t *edge; /* the edge selected for the serialization */
122 int omega1; /* estimated: available regs - RS reduction */
123 int omega2; /* increase in critical path length */
127 typedef struct _rss {
128 ir_phase ph; /**< Phase to hold some data */
129 heights_t *h; /**< The current height object */
130 ir_graph *irg; /**< The irg to preprocess */
131 plist_t *nodes; /**< The list of interesting nodes */
132 const arch_env_t *arch_env; /**< The architecture environment */
133 be_abi_irg_t *abi; /**< The abi for this irg */
134 pset *cbc_set; /**< A set of connected bipartite components */
135 ir_node *block; /**< The current block in progress. */
136 int *idx_map; /**< Mapping irn indices to per block indices */
137 unsigned max_height; /**< maximum height in the current block */
138 rss_opts_t *opts; /**< The options */
139 be_lv_t *liveness; /**< The liveness information for this irg */
140 pset *live_block; /**< Values alive at end of block */
141 const arch_register_class_t *cls; /**< The current register class */
142 DEBUG_ONLY(firm_dbg_module_t *dbg);
145 #define get_rss_irn(rss, irn) (phase_get_or_set_irn_data(&rss->ph, irn))
148 * We need some special nodes:
149 * a source and a sink for all live-in and live-out values of a block
157 /** The opcode of the rss_Source node once allocated. */
158 static ir_op *op_rss_Source;
159 /** The opcode of the rss_Sink node once allocated. */
160 static ir_op *op_rss_Sink;
162 /** The rss_Source node of the current graph. */
163 static ir_node *_source = NULL;
164 /** The rss_Sink node of the current graph. */
165 static ir_node *_sink = NULL;
167 #define is_Source(irn) ((irn) == _source)
168 #define is_Sink(irn) ((irn) == _sink)
172 RSS_DUMP_CBC = 1 << 0,
173 RSS_DUMP_PKG = 1 << 1,
174 RSS_DUMP_KILL = 1 << 2,
175 RSS_DUMP_DVG = 1 << 3,
176 RSS_DUMP_MAXAC = 1 << 4,
177 RSS_DUMP_ALL = (RSS_DUMP_MAXAC << 1) - 1,
180 static rss_opts_t rss_options = {
184 static const lc_opt_enum_int_items_t dump_items[] = {
185 { "none", RSS_DUMP_NONE },
186 { "cbc", RSS_DUMP_CBC },
187 { "pkg", RSS_DUMP_PKG },
188 { "kill", RSS_DUMP_KILL },
189 { "dvg", RSS_DUMP_DVG },
190 { "maxac", RSS_DUMP_MAXAC },
191 { "all", RSS_DUMP_ALL },
195 static lc_opt_enum_int_var_t dump_var = {
196 &rss_options.dump_flags, dump_items
199 static const lc_opt_table_entry_t rss_option_table[] = {
200 LC_OPT_ENT_ENUM_MASK("dump", "dump phases", &dump_var),
204 /******************************************************************************
206 * | | | | / _| | | (_)
207 * | |__ ___| |_ __ ___ _ __ | |_ _ _ _ __ ___| |_ _ ___ _ __ ___
208 * | '_ \ / _ \ | '_ \ / _ \ '__| | _| | | | '_ \ / __| __| |/ _ \| '_ \/ __|
209 * | | | | __/ | |_) | __/ | | | | |_| | | | | (__| |_| | (_) | | | \__ \
210 * |_| |_|\___|_| .__/ \___|_| |_| \__,_|_| |_|\___|\__|_|\___/|_| |_|___/
213 ******************************************************************************/
216 * Acquire opcodes if needed and create source and sink nodes.
218 static void init_rss_special_nodes(ir_graph *irg) {
221 if (op_rss_Source == NULL) {
222 int iro_rss_base = get_next_ir_opcodes(iro_rss_last);
223 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);
224 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);
226 block = get_irg_start_block(irg);
227 _source = new_ir_node(NULL, irg, block, op_rss_Source, mode_ANY, 0, NULL);
228 _sink = new_ir_node(NULL, irg, block, op_rss_Sink, mode_ANY, 0, NULL);
231 static int cmp_int(const void *a, const void *b) {
235 return QSORT_CMP(*i1, *i2);
238 static int cmp_child_costs(const void *a, const void *b) {
239 const child_t *c1 = a;
240 const child_t *c2 = b;
242 return QSORT_CMP(c1->cost, c2->cost);
245 static int cmp_irn_idx(const void *a, const void *b) {
246 const ir_node *n1 = *(ir_node **)a;
247 const ir_node *n2 = *(ir_node **)b;
249 return QSORT_CMP(get_irn_idx(n1), get_irn_idx(n2));
252 static int cmp_rss_edges(const void *a, const void *b) {
253 const rss_edge_t *e1 = a;
254 const rss_edge_t *e2 = b;
256 return (e1->src != e2->src) || (e1->tgt != e2->tgt);
259 static int bsearch_for_index(int key, int *arr, size_t len, int force) {
263 while (right >= left) {
264 int idx = (left + right) / 2;
268 else if (key > arr[idx])
275 assert(0 && "Something is wrong, key not found.");
279 static ir_node **build_sorted_array_from_list(plist_t *irn_list, struct obstack *obst) {
282 int len = plist_count(irn_list);
283 ir_node **arr = NEW_ARR_D(ir_node *, obst, len);
285 /* copy the list into the array */
286 foreach_plist(irn_list, el) {
287 arr[i++] = plist_element_get_value(el);
290 /* sort the array by node index */
291 qsort(arr, len, sizeof(arr[0]), cmp_irn_idx);
296 /*****************************************************
299 * __| | ___| |__ _ _ __ _ __ _ _ _ __ __ _
300 * / _` |/ _ \ '_ \| | | |/ _` |/ _` | | '_ \ / _` |
301 * | (_| | __/ |_) | |_| | (_| | (_| | | | | | (_| |
302 * \__,_|\___|_.__/ \__,_|\__, |\__, |_|_| |_|\__, |
306 *****************************************************/
309 static void dump_nodeset(ir_nodeset_t *ns, const char *prefix) {
310 ir_nodeset_iterator_t iter;
313 ir_nodeset_iterator_init(&iter, ns);
314 while( (irn = ir_nodeset_iterator_next(&iter)) != NULL ) {
315 ir_fprintf(stderr, "%s%+F\n", prefix, irn);
320 static void build_file_name(rss_t *rss, const char *suffix, size_t suf_len, char *buf, size_t len) {
321 const char *irg_name;
324 irg_name = get_entity_name(get_irg_entity(rss->irg));
325 snprintf(buf, len - suf_len, "%s-%s-block-%ld",
326 irg_name, arch_register_class_name(rss->cls), get_irn_node_nr(rss->block));
330 /* Dumps all collected bipartite components of current irg as vcg. */
331 static void debug_vcg_dump_bipartite(rss_t *rss) {
335 static const char suffix[] = "-RSS-CBC.vcg";
337 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
338 f = fopen(file_name, "w");
340 ir_fprintf(f, "graph: { title: \"connected bipartite component graph of %+F\"\n", rss->irg);
341 fprintf(f, "display_edge_labels: no\n");
342 fprintf(f, "layoutalgorithm: mindepth\n");
343 fprintf(f, "manhattan_edges: yes\n\n");
345 foreach_pset(rss->cbc_set, cbc) {
346 ir_nodeset_iterator_t iter;
350 fprintf(f, "graph: { titel: \"cbc %d\" label: \"cbc %d\" status:clustered color:yellow\n", cbc->nr, cbc->nr);
351 foreach_ir_nodeset(&cbc->parents, n, iter) {
352 ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
354 foreach_ir_nodeset(&cbc->children, n, iter) {
355 ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
357 foreach_pset(cbc->kill_edges, ke) {
358 ir_fprintf(f, "edge: { sourcename: \"n%d_%d\" targetname: \"n%d_%d\" }\n",
359 get_irn_node_nr(ke->src), cbc->nr, get_irn_node_nr(ke->tgt), cbc->nr);
367 /* Dump the computed killing function as vcg. */
368 static void debug_vcg_dump_kill(rss_t *rss) {
372 static const char suffix[] = "-RSS-KILL.vcg";
374 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
375 f = fopen(file_name, "w");
377 ir_fprintf(f, "graph: { title: \"computed kill graph of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
378 fprintf(f, "display_edge_labels: no\n");
379 fprintf(f, "layoutalgorithm: mindepth\n");
380 fprintf(f, "manhattan_edges: yes\n\n");
383 /* reset dump_flag */
385 foreach_phase_irn(&rss->ph, irn) {
386 rss_irn_t *node = get_rss_irn(rss, irn);
391 /* dump all nodes and their killers */
392 foreach_plist(rss->nodes, el) {
393 ir_node *irn = plist_element_get_value(el);
394 rss_irn_t *rirn = get_rss_irn(rss, irn);
395 rss_irn_t *pk_rirn = get_rss_irn(rss, rirn->killer);
397 if (! rirn->dumped) {
398 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
402 if (! pk_rirn->dumped) {
403 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(rirn->killer), rirn->killer);
407 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
408 get_irn_node_nr(rirn->killer), get_irn_node_nr(irn));
415 /* Dumps the potential killing DAG (PKG) as vcg. */
416 static void debug_vcg_dump_pkg(rss_t *rss, ir_nodeset_t *max_ac, int iteration) {
419 char *suffix = alloca(32);
420 static const char suffix1[] = "-RSS-PKG.vcg";
421 static const char suffix2[] = "-RSS-PKG-MAXAC.vcg";
425 snprintf(suffix, 32, "%s", suffix1);
428 snprintf(suffix, 32, "-%02d%s", iteration, suffix2);
431 build_file_name(rss, suffix, strlen(suffix) + 1, file_name, sizeof(file_name));
432 f = fopen(file_name, "w");
434 ir_fprintf(f, "graph: { title: \"potential killing DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
435 fprintf(f, "display_edge_labels: no\n");
436 fprintf(f, "layoutalgorithm: mindepth\n");
437 fprintf(f, "manhattan_edges: yes\n\n");
440 /* reset dump_flag */
442 foreach_phase_irn(&rss->ph, irn) {
443 rss_irn_t *node = get_rss_irn(rss, irn);
448 foreach_plist(rss->nodes, el) {
449 ir_node *irn = plist_element_get_value(el);
450 rss_irn_t *rirn = get_rss_irn(rss, irn);
452 plist_element_t *k_el;
454 /* dump selected saturating values in yellow */
455 if (max_ac && ir_nodeset_contains(max_ac, irn))
458 if (! rirn->dumped) {
460 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(irn), irn, rirn->chain->nr, c1);
462 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(irn), irn, c1);
466 foreach_plist(rirn->pkiller_list, k_el) {
467 ir_node *pkiller = plist_element_get_value(k_el);
468 rss_irn_t *pk_rirn = get_rss_irn(rss, pkiller);
471 if (max_ac && ir_nodeset_contains(max_ac, pkiller))
474 if (! pk_rirn->dumped) {
476 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(pkiller), pkiller, pk_rirn->chain->nr, c2);
478 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(pkiller), pkiller, c2);
481 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
482 get_irn_node_nr(pkiller), get_irn_node_nr(irn));
489 /* Dumps the disjoint value DAG (DVG) as vcg. */
490 static void debug_vcg_dump_dvg(rss_t *rss, dvg_t *dvg) {
491 static const char suffix[] = "-RSS-DVG.vcg";
494 ir_nodeset_iterator_t iter;
498 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
499 f = fopen(file_name, "w");
501 ir_fprintf(f, "graph: { title: \"disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
502 fprintf(f, "display_edge_labels: no\n");
503 fprintf(f, "layoutalgorithm: mindepth\n");
504 fprintf(f, "manhattan_edges: yes\n\n");
507 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
508 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
512 foreach_pset(dvg->edges, edge) {
513 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
514 get_irn_node_nr(edge->src), get_irn_node_nr(edge->tgt));
522 /* Dumps the PKG(DVG). */
523 static void debug_vcg_dump_dvg_pkiller(rss_t *rss, dvg_t *dvg) {
524 static const char suffix[] = "-RSS-DVG-PKG.vcg";
527 ir_nodeset_iterator_t iter;
530 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
531 f = fopen(file_name, "w");
533 ir_fprintf(f, "graph: { title: \"PKG of disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
534 fprintf(f, "display_edge_labels: no\n");
535 fprintf(f, "layoutalgorithm: mindepth\n");
536 fprintf(f, "manhattan_edges: yes\n\n");
539 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
540 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
544 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
545 rss_irn_t *node = get_rss_irn(rss, irn);
548 foreach_plist(node->dvg_pkiller_list, el) {
549 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
550 get_irn_node_nr(plist_element_get_value(el)), get_irn_node_nr(irn));
560 * In case there is no rss information for irn, initialize it.
562 static void *init_rss_irn(ir_phase *ph, ir_node *irn, void *old) {
563 rss_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
565 res->descendant_list = plist_obstack_new(phase_obst(ph));
566 res->descendants = NULL;
568 res->consumer_list = plist_obstack_new(phase_obst(ph));
569 res->consumer = NULL;
571 res->pkiller_list = plist_obstack_new(phase_obst(ph));
573 res->parent_list = plist_obstack_new(phase_obst(ph));
591 * Collect all nodes data dependent on current node.
593 static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int *got_sink, unsigned cur_desc_walk) {
594 const ir_edge_t *edge;
595 rss_irn_t *cur_node = get_rss_irn(rss, irn);
596 ir_node *block = rss->block;
597 ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
600 if (cur_node->desc_walk >= cur_desc_walk)
602 cur_node->desc_walk = cur_desc_walk;
604 /* Stop at Barriers */
605 if (be_is_Barrier(irn))
608 /* loop over normal and dependency edges */
609 for (i = 0; i < 2; ++i) {
610 foreach_out_edge_kind(irn, edge, ekind[i]) {
611 ir_node *user = get_edge_src_irn(edge);
613 /* skip ignore nodes as they do not really contribute to register pressure */
614 if (arch_irn_is(rss->arch_env, user, ignore))
618 (a) mode_X means Jump -> out_edge
619 (b) Phi as user of a normal node -> out-edge
621 if (get_irn_mode(user) == mode_X || is_Phi(user)) {
630 //if (arch_get_irn_reg_class(rss->arch_env, user, -1) == rss->cls)
631 collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
634 /* check if user lives in block and is not a control flow node */
635 if (get_nodes_block(user) == block) {
636 if (! plist_has_value(rirn->descendant_list, user)) {
637 plist_insert_back(rirn->descendant_list, user);
638 DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", user));
640 collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
642 else if (! *got_sink) {
644 /* user lives out of block: add sink as descendant if not already done */
645 plist_insert_back(rirn->descendant_list, _sink);
647 DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", _sink));
655 * Handles a single consumer.
657 static void collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *consumer, int *got_sink) {
658 ir_node *block = rss->block;
660 assert(! is_Proj(consumer) && "Cannot handle Projs");
662 if (! is_Phi(consumer) && ! is_Block(consumer) && get_nodes_block(consumer) == block) {
663 if (! arch_irn_is(rss->arch_env, consumer, ignore) && ! plist_has_value(rss_irn->consumer_list, consumer)) {
664 plist_insert_back(rss_irn->consumer_list, consumer);
665 DBG((rss->dbg, LEVEL_2, "\t\tconsumer %+F\n", consumer));
669 rss_irn->live_out = 1;
670 DBG((rss->dbg, LEVEL_2, "\t\tlive out %+F", consumer));
672 plist_insert_back(rss_irn->consumer_list, _sink);
674 DB((rss->dbg, LEVEL_2, ", %+F added instead", _sink));
676 DB((rss->dbg, LEVEL_2, "\n"));
681 * Collect all nodes consuming the value(s) produced by current node.
683 static void collect_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *irn, int *got_sink) {
684 const ir_edge_t *edge;
686 ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
687 rss_irn_t *cur_node = get_rss_irn(rss, irn);
689 if (cur_node->havecons)
691 cur_node->havecons = 1;
693 for (i = 0; i < 2; ++i) {
694 foreach_out_edge_kind(irn, edge, ekind[i]) {
695 ir_node *consumer = get_edge_src_irn(edge);
697 if (is_Proj(consumer)) {
698 //if (arch_get_irn_reg_class(rss->arch_env, consumer, -1) == rss->cls)
699 collect_consumer(rss, rss_irn, consumer, got_sink);
702 collect_single_consumer(rss, rss_irn, consumer, got_sink);
708 * Collects all consumer and descendant of a irn.
710 static void collect_node_info(rss_t *rss, ir_node *irn) {
711 static unsigned cur_desc_walk = 0;
712 rss_irn_t *rss_irn = get_rss_irn(rss, irn);
715 assert(! is_Proj(irn) && "Cannot handle Projs.");
717 /* check if node info is already available */
718 if (rss_irn->handled)
720 //phase_reinit_single_irn_data(&rss->ph, irn);
722 DBG((rss->dbg, LEVEL_1, "\tcomputing consumers of %+F:\n", irn));
724 /* collect all consumer */
726 collect_consumer(rss, rss_irn, irn, &got_sink);
728 /* build sorted consumer array */
729 rss_irn->consumer = build_sorted_array_from_list(rss_irn->consumer_list, phase_obst(&rss->ph));
731 DBG((rss->dbg, LEVEL_1, "\tcompute descendants of %+F:\n", irn));
733 /* collect descendants */
735 collect_descendants(rss, rss_irn, irn, &got_sink, ++cur_desc_walk);
737 /* build sorted descendant array */
738 rss_irn->descendants = build_sorted_array_from_list(rss_irn->descendant_list, phase_obst(&rss->ph));
740 rss_irn->handled = 1;
744 * Checks if v is a potential killer of u.
745 * v is in pkill(u) iff descendants(v) cut consumer(u) is v
747 * @param rss The rss object
748 * @param v The node to check for killer
749 * @param u The potentially killed value
750 * @return 1 if v is in pkill(u), 0 otherwise
752 static int is_potential_killer(rss_t *rss, rss_irn_t *v, rss_irn_t *u) {
757 assert(is_Sink(v->irn) || ((plist_count(v->descendant_list) > 0 && v->descendants) || 1));
758 assert(is_Sink(u->irn) || ((plist_count(u->consumer_list) > 0 && u->consumer) || 1));
760 /* as we loop over the list: loop over the shorter one */
761 if (plist_count(v->descendant_list) > plist_count(u->consumer_list)) {
762 list = u->consumer_list;
763 arr = v->descendants;
766 list = v->descendant_list;
770 /* for each list element: try to find element in array */
771 foreach_plist(list, el) {
772 ir_node *irn = plist_element_get_value(el);
773 ir_node *match = BSEARCH_IRN_ARR(irn, arr);
775 if (match && match != irn)
783 * Update descendants, consumer and pkiller list for the given irn.
785 static void update_node_info(rss_t *rss, ir_node *irn, ir_node *pk_irn) {
786 rss_irn_t *node = get_rss_irn(rss, irn);
787 rss_irn_t *pkiller = get_rss_irn(rss, pk_irn);
789 /* add consumer and rebuild the consumer array */
790 if (! plist_has_value(node->consumer_list, pk_irn)) {
791 plist_insert_back(node->consumer_list, pk_irn);
792 node->consumer = build_sorted_array_from_list(node->consumer_list, phase_obst(&rss->ph));
795 /* add pk_irn as descendant, add it's descendants to irn's and rebuild array */
796 if (! plist_has_value(node->descendant_list, pk_irn)) {
799 plist_insert_back(node->descendant_list, pk_irn);
801 foreach_plist(pkiller->descendant_list, el) {
802 ir_node *desc = plist_element_get_value(el);
804 if (! plist_has_value(node->descendant_list, desc))
805 plist_insert_back(node->descendant_list, desc);
808 node->descendants = build_sorted_array_from_list(node->descendant_list, phase_obst(&rss->ph));
814 * Compute the potential killing set PK.
816 static void compute_pkill_set(rss_t *rss) {
817 plist_element_t *u_el, *v_el;
819 foreach_plist(rss->nodes, u_el) {
820 ir_node *u_irn = plist_element_get_value(u_el);
821 rss_irn_t *u = get_rss_irn(rss, u_irn);
823 DBG((rss->dbg, LEVEL_1, "\tcomputing potential killers of %+F:\n", u_irn));
825 /* check each consumer if it is a potential killer */
826 foreach_plist(u->consumer_list, v_el) {
827 ir_node *v_irn = plist_element_get_value(v_el);
828 rss_irn_t *v = get_rss_irn(rss, v_irn);
830 /* check, if v is a potential killer of u */
831 if (is_potential_killer(rss, v, u)) {
832 if (! plist_has_value(u->pkiller_list, v_irn))
833 plist_insert_back(u->pkiller_list, v_irn);
835 DBG((rss->dbg, LEVEL_2, "\t\tpotential killer %+F\n", v_irn));
842 if (rss->opts->dump_flags & RSS_DUMP_PKG)
843 debug_vcg_dump_pkg(rss, NULL, 0);
847 * Build set of killing edges (from values to their potential killers)
849 static void build_kill_edges(rss_t *rss, pset *epk) {
850 plist_element_t *el, *k_el;
852 foreach_plist(rss->nodes, el) {
853 ir_node *irn = plist_element_get_value(el);
854 rss_irn_t *rirn = get_rss_irn(rss, irn);
856 DBG((rss->dbg, LEVEL_3, "\t\tbuilding kill edges for %+F:\n", irn));
858 foreach_plist(rirn->pkiller_list, k_el) {
859 ir_node *pkiller = plist_element_get_value(k_el);
860 rss_edge_t *ke = obstack_alloc(phase_obst(&rss->ph), sizeof(*ke));
866 DBG((rss->dbg, LEVEL_3, "\t\t\ttarget %+F\n", pkiller));
868 pset_insert(epk, ke, HASH_RSS_EDGE(ke));
874 /* print the given cbc for debugging purpose */
875 static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc) {
876 ir_nodeset_iterator_t iter;
880 DBG((mod, LEVEL_3, "\t\tS = set of parents:\n"));
881 foreach_ir_nodeset(&cbc->parents, n, iter) {
882 DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
884 DBG((mod, LEVEL_3, "\t\tT = set of children:\n"));
885 foreach_ir_nodeset(&cbc->children, n, iter) {
886 DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
888 DBG((mod, LEVEL_3, "\t\tE = Edges from producers to consumers\n"));
889 foreach_pset(cbc->kill_edges, ke) {
890 DBG((mod, LEVEL_3, "\t\t\t%+F -> %+F\n", ke->src, ke->tgt));
896 * Construct the bipartite decomposition.
897 * Sid-Ahmed-Ali Touati, Phd Thesis
898 * Register Pressure in Instruction Level Parallelism, p. 71
900 static void compute_bipartite_decomposition(rss_t *rss) {
901 pset *epk = new_pset(cmp_rss_edges, 10);
906 DBG((rss->dbg, LEVEL_1, "\tcomputing bipartite decomposition:\n"));
908 build_kill_edges(rss, epk);
910 foreach_plist(rss->nodes, el) {
911 ir_node *u_irn = plist_element_get_value(el);
912 rss_irn_t *u = get_rss_irn(rss, u_irn);
918 plist_element_t *el2;
920 rss_edge_t *kedge_root = NULL;
921 ir_node *t_irn, *s_irn;
922 ir_nodeset_iterator_t iter;
924 if (u->visited || u_irn == _sink)
927 DBG((rss->dbg, LEVEL_2, "\t\t%+F choosen:\n", u_irn));
929 cbc = obstack_alloc(phase_obst(&rss->ph), sizeof(*cbc));
932 /* initialize S_cb */
933 ir_nodeset_init_size(&cbc->parents, 5);
934 ir_nodeset_insert(&cbc->parents, u_irn);
935 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (init)\n", u_irn));
938 cbc->kill_edges = new_pset(cmp_rss_edges, 5);
940 /* each parent gets killed by at least one value from children */
942 /* T_cb = PK_successors(u) */
943 ir_nodeset_init_size(&cbc->children, 5);
944 foreach_plist(u->pkiller_list, el2) {
945 ir_nodeset_insert(&cbc->children, plist_element_get_value(el2));
946 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (init)\n", plist_element_get_value(el2)));
950 Now: insert the parents of all children into the parent set
951 and insert the children of all parents into the children set
952 until the sets don't change any more
954 while (p_change || c_change) {
955 ir_nodeset_iterator_t iter;
956 p_change = c_change = 0;
958 /* accumulate parents */
959 foreach_ir_nodeset(&cbc->children, t_irn, iter) {
960 foreach_pset(epk, k_edge) {
961 ir_node *val = k_edge->src;
963 if (k_edge->tgt == t_irn && ! ir_nodeset_contains(&cbc->parents, val)) {
964 ir_nodeset_insert(&cbc->parents, val);
966 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (killed by %+F)\n", val, t_irn));
971 /* accumulate children */
972 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
973 foreach_pset(epk, k_edge) {
974 ir_node *val = k_edge->tgt;
976 if (k_edge->src == s_irn && ! ir_nodeset_contains(&cbc->children, val)) {
977 ir_nodeset_insert(&cbc->children, val);
979 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (kills %+F)\n", val, s_irn));
985 /* mark all parent values as visited */
986 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
987 rss_irn_t *s = get_rss_irn(rss, s_irn);
989 /* assure bipartite property */
991 if (ir_nodeset_contains(&cbc->children, s_irn)) {
992 ir_nodeset_remove(&cbc->children, s_irn);
993 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F removed from to children\n", s_irn));
999 foreach_pset(epk, k_edge) {
1000 if (ir_nodeset_contains(&cbc->parents, k_edge->src) &&
1001 ir_nodeset_contains(&cbc->children, k_edge->tgt)) {
1002 pset_insert(cbc->kill_edges, k_edge, HASH_RSS_EDGE(k_edge));
1004 Link all k_edges which are about to be removed together.
1005 Beware: pset_remove kills the iterator.
1007 k_edge->next = kedge_root;
1008 kedge_root = k_edge;
1012 /* remove all linked k_edges */
1013 for (; kedge_root; kedge_root = kedge_root->next) {
1014 pset_remove(epk, kedge_root, HASH_RSS_EDGE(kedge_root));
1017 /* verify the cbc */
1018 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
1021 foreach_pset(cbc->kill_edges, k_edge) {
1022 if (k_edge->src == s_irn) {
1024 pset_break(cbc->kill_edges);
1031 ir_fprintf(stderr, "Warning: parent %+F is not killed in current cbc\n", s_irn);
1034 assert(vrfy_ok && "Verification of CBC failed");
1036 /* add the connected bipartite component */
1037 if (ir_nodeset_size(&cbc->parents) > 0 &&
1038 ir_nodeset_size(&cbc->children) > 0 &&
1039 pset_count(cbc->kill_edges) > 0)
1040 pset_insert(rss->cbc_set, cbc, (unsigned)cbc->nr);
1041 DBG((rss->dbg, LEVEL_2, "\tbipartite component %d inserted:\n", cbc->nr));
1043 if (firm_dbg_get_mask(rss->dbg) & LEVEL_2)
1044 debug_print_cbc(rss->dbg, cbc);
1048 if (rss->opts->dump_flags & RSS_DUMP_CBC)
1049 debug_vcg_dump_bipartite(rss);
1055 * Select the child with the maximum cost.
1057 static child_t *select_child_max_cost(rss_t *rss, ir_nodeset_t *x, ir_nodeset_t *y, child_t *t, cbc_t *cbc) {
1059 ir_nodeset_iterator_t iter;
1060 float max_cost = -1.0f;
1062 DBG((rss->dbg, LEVEL_2, "\t\tcomputing children costs:\n"));
1064 foreach_ir_nodeset(&cbc->children, child, iter) {
1065 rss_irn_t *r_child = get_rss_irn(rss, child);
1066 int num_unkilled_parents = 0;
1067 int num_descendants;
1071 /* get the number of unkilled parents */
1072 foreach_pset(cbc->kill_edges, k_edge) {
1073 if (k_edge->tgt == child && ir_nodeset_contains(x, k_edge->src))
1074 ++num_unkilled_parents;
1077 cost = (float)num_unkilled_parents;
1079 num_descendants = plist_count(r_child->descendant_list) + ir_nodeset_size(y);
1081 if (num_descendants > 0)
1082 cost /= (float)num_descendants;
1084 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F, #desc %d, cost %.3f\n", child, num_descendants, cost));
1086 if (cost > max_cost) {
1097 * Remove all parents from x which are killed by t_irn.
1099 static void remove_covered_parents(rss_t *rss, ir_nodeset_t *x, ir_node *t_irn, cbc_t *cbc) {
1100 rss_irn_t *t = get_rss_irn(rss, t_irn);
1103 DBG((rss->dbg, LEVEL_2, "\t\tremoving parents covered by %+F:\n", t_irn));
1105 foreach_pset(cbc->kill_edges, k_edge) {
1106 if (k_edge->tgt == t_irn && ir_nodeset_contains(x, k_edge->src)) {
1107 ir_nodeset_remove(x, k_edge->src);
1108 plist_insert_back(t->parent_list, k_edge->src);
1109 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", k_edge->src));
1114 static void update_cumulated_descendent_values(rss_t *rss, ir_nodeset_t *y, ir_node *t_irn) {
1115 rss_irn_t *t = get_rss_irn(rss, t_irn);
1116 plist_element_t *el;
1118 DBG((rss->dbg, LEVEL_2, "\t\tupdating cumulated descendant value of %+F:\n", t_irn));
1120 foreach_plist(t->descendant_list, el) {
1121 ir_nodeset_insert(y, plist_element_get_value(el));
1122 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", plist_element_get_value(el)));
1127 * Greedy-k: a heuristics for the MMA problem
1129 static void compute_killing_function(rss_t *rss) {
1131 struct obstack obst;
1133 obstack_init(&obst);
1135 rss->cbc_set = pset_new_ptr(5);
1136 compute_bipartite_decomposition(rss);
1138 /* for all bipartite components do: */
1139 foreach_pset(rss->cbc_set, cbc) {
1143 ir_nodeset_iterator_t iter;
1144 child_t **sks = NEW_ARR_F(child_t *, 20);
1149 ir_nodeset_init_size(&x, 10);
1150 ir_nodeset_init_size(&y, 10);
1152 DBG((rss->dbg, LEVEL_1, "\tcomputing SKS for cbc %d:\n", cbc->nr));
1153 DBG((rss->dbg, LEVEL_2, "\t\tinitializing parents X:\n"));
1155 /* X = S_cb (all parents are initially uncovered) */
1156 foreach_ir_nodeset(&cbc->parents, p, iter) {
1157 ir_nodeset_insert(&x, p);
1158 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", p));
1161 /* while X not empty */
1162 while (ir_nodeset_size(&x) > 0) {
1163 child_t *t = obstack_alloc(&obst, sizeof(*t));
1164 memset(t, 0, sizeof(*t));
1166 t = select_child_max_cost(rss, &x, &y, t, cbc);
1168 if (cur_len >= cur_size) {
1169 ARR_EXTO(child_t *, sks, cur_size * 2);
1173 DBG((rss->dbg, LEVEL_2, "\t\tinsert child %+F (%.3f) into SKS at pos %d\n", t->irn, t->cost, cur_len));
1176 remove_covered_parents(rss, &x, t->irn, cbc);
1177 update_cumulated_descendent_values(rss, &y, t->irn);
1180 ARR_SHRINKLEN(sks, cur_len);
1182 /* sort SKS in increasing cost order */
1183 qsort(sks, cur_len, sizeof(sks[0]), cmp_child_costs);
1185 DBG((rss->dbg, LEVEL_2, "\tprocessing SKS for cbc %d:\n", cbc->nr));
1187 /* build killing function */
1188 for (i = cur_len - 1; i >= 0; --i) { /* loop over sks in decreasing cost order */
1189 child_t *t = sks[i];
1190 rss_irn_t *rt = get_rss_irn(rss, t->irn);
1191 plist_element_t *p_el;
1193 DBG((rss->dbg, LEVEL_3, "\t\t\tkiller %+F (%.3f):\n", t->irn, t->cost));
1195 /* kill all unkilled parents of t */
1196 foreach_plist(rt->parent_list, p_el) {
1197 ir_node *par = plist_element_get_value(p_el);
1198 rss_irn_t *rpar = get_rss_irn(rss, par);
1200 if (is_Sink(rpar->killer)) {
1201 rpar->killer = t->irn;
1202 DBG((rss->dbg, LEVEL_2, "\t\tkill %+F\n", rpar->irn));
1205 DBG((rss->dbg, LEVEL_3, "\t\t\tkeeping %+F as killer for %+F\n", rpar->killer, rpar->irn));
1210 ir_nodeset_destroy(&x);
1211 ir_nodeset_destroy(&y);
1215 if (rss->opts->dump_flags & RSS_DUMP_KILL)
1216 debug_vcg_dump_kill(rss);
1218 del_pset(rss->cbc_set);
1219 obstack_free(&obst, NULL);
1223 * Adds the edge src -> tgt to the dvg. Checks if reverse edge is already there (asserts).
1225 static INLINE void add_dvg_edge(rss_t *rss, dvg_t *dvg, ir_node *src, ir_node *tgt, int have_source) {
1226 rss_edge_t *dvg_edge;
1230 ir_nodeset_insert(&dvg->nodes, src);
1232 assert(ir_nodeset_contains(&dvg->nodes, src) && "Wrong assumption");
1234 ir_nodeset_insert(&dvg->nodes, tgt);
1238 assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
1242 if (NULL != pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
1243 /* add the edge to the DVG */
1244 dvg_edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*dvg_edge));
1246 dvg_edge->src = src;
1247 dvg_edge->tgt = tgt;
1248 dvg_edge->next = NULL;
1250 DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", src, tgt));
1251 pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
1256 * Computes the disjoint value DAG (DVG).
1257 * BEWARE: It is not made explicitly clear in the Touati paper,
1258 * but the DVG is meant to be build from the KILLING DAG
1260 static void compute_dvg(rss_t *rss, dvg_t *dvg) {
1261 plist_element_t *el;
1263 DBG((rss->dbg, LEVEL_1, "\tcomputing DVG:\n"));
1265 foreach_plist(rss->nodes, el) {
1266 ir_node *u_irn = plist_element_get_value(el);
1267 rss_irn_t *u = get_rss_irn(rss, u_irn);
1268 rss_irn_t *u_killer = get_rss_irn(rss, u->killer);
1271 /* TODO: omit nodes only having sink as pkiller and killing no one */
1273 /* add an edge to killer */
1274 add_dvg_edge(rss, dvg, u_irn, u->killer, 0);
1276 if (is_Sink(u->killer))
1279 /* We add an edge to every killer, from where we could be reached. */
1280 for (i = ARR_LEN_SAFE(u_killer->descendants) - 1; i >= 0; --i) {
1281 add_dvg_edge(rss, dvg, u_irn, u_killer->descendants[i], 1);
1286 foreach_plist(rss->nodes, el2) {
1287 ir_node *v_irn = plist_element_get_value(el2);
1290 There is an edge (u, v) in the DVG iff v is a descendant of the killer(u).
1292 if (BSEARCH_IRN_ARR(v_irn, u_kill->descendants)) {
1293 rss_edge_t *dvg_edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*dvg_edge));
1296 /* insert the user into the DVG and append it to the user list of u */
1297 ir_nodeset_insert(&dvg->nodes, v_irn);
1298 if (! plist_has_value(u->dvg_user_list, v_irn))
1299 plist_insert_back(u->dvg_user_list, v_irn);
1301 dvg_edge->src = u_irn;
1302 dvg_edge->tgt = v_irn;
1303 dvg_edge->next = NULL;
1308 assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
1310 /* add the edge to the DVG */
1311 DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", u_irn, v_irn));
1312 pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
1318 if (rss->opts->dump_flags & RSS_DUMP_DVG)
1319 debug_vcg_dump_dvg(rss, dvg);
1323 * Updates the dvg structure when a serialization edge from src -> tgt is added.
1325 static void update_dvg(rss_t *rss, dvg_t *dvg, rss_irn_t *src, rss_irn_t *tgt) {
1328 rss_edge_t **arr = alloca(pset_count(dvg->edges) * sizeof(arr[0]));
1331 Add an edge from serialization target to serialization src:
1332 src cannot be alive with target
1334 add_dvg_edge(rss, dvg, tgt->irn, src->irn, 0);
1336 /* Add edges to src's descendants as well, they also getting serialized. */
1337 for (i = ARR_LEN_SAFE(src->descendants) - 1; i >= 0; --i) {
1338 add_dvg_edge(rss, dvg, tgt->irn, src->descendants[i], 1);
1341 /* We also have to add edges from targets predecessors in dvg */
1343 /* We cannot insert elements into set over which we iterate ... */
1344 foreach_pset(dvg->edges, edge) {
1345 if (edge->tgt == tgt->irn) {
1350 for (i = 0; i < idx; ++i) {
1352 add_dvg_edge(rss, dvg, edge->src, src->irn, 1);
1353 for (j = ARR_LEN_SAFE(src->descendants) - 1; j >= 0; --j) {
1354 add_dvg_edge(rss, dvg, edge->src, src->descendants[j], 1);
1361 * Accumulate all descendants for root into list.
1363 static void accumulate_dvg_descendant_values(rss_t *rss, rss_irn_t *root, plist_t *list) {
1364 if (plist_count(root->dvg_user_list) > 0) {
1365 plist_element_t *el;
1367 foreach_plist(root->dvg_user_list, el) {
1368 ir_node *v_irn = plist_element_get_value(el);
1369 rss_irn_t *v = get_rss_irn(rss, v_irn);
1371 /* add v as descendant */
1372 if (! plist_has_value(list, v_irn)) {
1373 plist_insert_back(list, v_irn);
1374 DBG((rss->dbg, DEBUG_DVG, "\t\t\tadd DVG descendant %+F\n", v_irn));
1377 /* accumulate v's descendants */
1378 accumulate_dvg_descendant_values(rss, v, list);
1384 * Builds the list of potential killers for each node
1386 * Needs the descendant list for all user as sorted array.
1388 static void build_dvg_pkiller_list(rss_t *rss, dvg_t *dvg) {
1389 ir_nodeset_iterator_t iter;
1392 foreach_nodeset(&dvg->nodes, irn, iter) {
1393 rss_irn_t *node = get_rss_irn(rss, irn);
1394 plist_element_t *el, *el2;
1396 DBG((rss->dbg, DEBUG_DVG, "\t\tbuilding pkiller list for %+F\n", irn));
1398 /* check each user */
1399 foreach_plist(node->dvg_user_list, el) {
1400 ir_node *u_irn = plist_element_get_value(el);
1402 /* is the current user u_irn not a descendant of any other user -> pkiller */
1403 foreach_plist(node->dvg_user_list, el2) {
1404 ir_node *v_irn = plist_element_get_value(el2);
1405 rss_irn_t *v = get_rss_irn(rss, v_irn);
1408 ! BSEARCH_IRN_ARR(u_irn, v->dvg_desc) &&
1409 ! plist_has_value(node->dvg_pkiller_list, u_irn))
1411 plist_insert_back(node->dvg_pkiller_list, u_irn);
1412 DBG((rss->dbg, DEBUG_DVG, "\t\t\tadd DVG pkiller %+F\n", u_irn));
1417 node->dvg_pkiller = build_sorted_array_from_list(node->dvg_pkiller_list, phase_obst(&rss->ph));
1421 if (firm_dbg_get_mask(rss->dbg) & DEBUG_DVG)
1422 debug_vcg_dump_dvg_pkiller(rss, dvg);
1429 * Compute the maximal antichain of the current DVG.
1430 * This is a reimplementation of the MAXIMAL_ANTI_CHAIN function
1431 * from the DDG library 1.1 (DAG.cpp).
1433 static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration) {
1434 int n = ir_nodeset_size(&dvg->nodes);
1435 int *assignment = alloca(n * sizeof(assignment[0]));
1436 int *assignment_rev = alloca(n * sizeof(assignment_rev[0]));
1437 int *idx_map = alloca(n * sizeof(idx_map[0]));
1438 hungarian_problem_t *bp;
1439 ir_nodeset_t *values, *temp;
1440 ir_nodeset_iterator_t iter;
1442 int i, j, cost, cur_chain, res;
1443 rss_edge_t *dvg_edge;
1445 #define MAP_IDX(irn) bsearch_for_index(get_irn_idx(irn), idx_map, n, 1)
1447 if (pset_count(dvg->edges) == 0)
1450 bp = hungarian_new(n, n, 1, HUNGARIAN_MATCH_NORMAL);
1453 At first, we build an index map for the nodes in the DVG,
1454 because we cannot use the irn idx therefore as the resulting
1455 bipartite data structure would have around 1.2GB.
1456 So we limit the size to the number of nodes we have in the DVG
1457 and build a sorted index map for their irn indices.
1460 foreach_ir_nodeset(&dvg->nodes, u_irn, iter) {
1461 idx_map[i++] = get_irn_idx(u_irn);
1463 qsort(idx_map, n, sizeof(idx_map[0]), cmp_int);
1465 foreach_pset(dvg->edges, dvg_edge) {
1466 int idx_u = MAP_IDX(dvg_edge->src);
1467 int idx_v = MAP_IDX(dvg_edge->tgt);
1469 /* add the entry to the bipartite data structure */
1470 hungarian_add(bp, idx_u, idx_v, 1);
1471 DBG((rss->dbg, LEVEL_3, "\t\t\tadd %d (%+F) -> %d (%+F)\n",
1472 idx_u, dvg_edge->src, idx_v, dvg_edge->tgt));
1476 Add a bipartite entry for each pair of nodes (u, v), where exists a
1477 path in the DVG from u to v, ie. connect all descendants(v) to v.
1478 desc_dvg(v) = accumulated descendants of all z in dvg_user_list(v)
1480 foreach_ir_nodeset(&dvg->nodes, u_irn, iter) {
1481 rss_irn_t *u = get_rss_irn(rss, u_irn);
1482 int idx_u_irn = MAP_IDX(u_irn);
1484 DBG((rss->dbg, DEBUG_DVG, "\t\tcomputing DVG descendants of %+F:\n", u_irn));
1486 //plist_clear(u->dvg_desc_list);
1487 //accumulate_dvg_descendant_values(rss, u, u->dvg_desc_list);
1490 FIXME: The array is build on the phase obstack and we cannot free the data.
1491 So the array get as many times allocated as this function is called.
1494 /* build the sorted array for faster searches */
1495 //u->dvg_desc = build_sorted_array_from_list(u->dvg_desc_list, phase_obst(&rss->ph));
1497 DBG((rss->dbg, DEBUG_MAX_AC, "\t\tadding bipartite entries of %+F:\n", u_irn));
1499 /* add the bipartite entries for all descendants */
1500 for (i = ARR_LEN_SAFE(u->dvg_desc) - 1; i >= 0; --i) {
1501 rss_irn_t *desc = get_rss_irn(rss, u->dvg_desc[i]);
1502 int idx_desc = MAP_IDX(u->dvg_desc[i]);
1504 /* add the entry to the bipartite data structure */
1505 hungarian_add(bp, idx_u_irn, idx_desc, 1);
1506 DBG((rss->dbg, DEBUG_MAX_AC, "\t\t\tadd %d (%+F) -> %d (%+F)\n",
1507 idx_u_irn, u_irn, idx_desc, u->dvg_desc[i]));
1514 /* We want maximum cardinality matching */
1515 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
1518 DBG((rss->dbg, DEBUG_DVG, "\t\tcomputing DVG pkiller:\n"));
1519 /* beware: the following function needs the dvg_desc array */
1520 build_dvg_pkiller_list(rss, dvg);
1523 DBG((rss->dbg, LEVEL_2, "\t\tcomputing bipartite matching\n"));
1525 The maximum cardinality bipartite matching gives us the minimal
1526 chain partition, which corresponds to the maximum anti chains.
1528 res = hungarian_solve(bp, assignment, &cost, 1);
1529 assert(res == 0 && "Bipartite matching failed!");
1532 memset(assignment_rev, -1, n * sizeof(assignment_rev[0]));
1534 /* build the reverse assignment, ie. foreach i -> j, add j -> i */
1535 for (i = 0; i < n; ++i) {
1536 if (assignment[i] >= 0) {
1537 int j = assignment[i];
1538 assignment_rev[j] = i;
1542 DBG((rss->dbg, LEVEL_2, "\t\tgot assignment with cost %d\n", cost));
1543 DBG((rss->dbg, LEVEL_3, "\t\t\tassignment --- reverse assignment\n", cost));
1544 for (i = 0; i < n; ++i) {
1545 DBG((rss->dbg, LEVEL_3, "\t\t\t%3d -> %3d %3d -> %3d\n", i, assignment[i], i, assignment_rev[i]));
1548 values = xmalloc(sizeof(values[0]));
1549 ir_nodeset_init_size(values, 10);
1551 /* Construction of the minimal chain partition */
1552 for (j = 0; j < n; ++j) {
1553 /* check nodes, which did not occur as target */
1554 if (assignment_rev[j] == -1) {
1555 int xj = idx_map[j];
1556 ir_node *xj_irn = get_idx_irn(rss->irg, xj);
1557 rss_irn_t *xj_rss = get_rss_irn(rss, xj_irn);
1558 chain_t *c = obstack_alloc(phase_obst(&rss->ph), sizeof(*c));
1561 /* there was no source for j -> we have a source of a new chain */
1562 ir_nodeset_insert(values, xj_irn);
1564 c->elements = plist_obstack_new(phase_obst(&rss->ph));
1565 c->nr = cur_chain++;
1566 plist_insert_back(c->elements, xj_irn);
1570 DBG((rss->dbg, LEVEL_2, "\t\tstarting chain %d:\n", c->nr));
1571 DBG((rss->dbg, LEVEL_2, "\t\t\t%+F (%d)", xj_irn, j));
1573 /* follow chain, having j as source */
1575 while (assignment[source] >= 0) {
1576 int target = assignment[source];
1577 int irn_idx = idx_map[target];
1578 ir_node *irn = get_idx_irn(rss->irg, irn_idx);
1579 rss_irn_t *node = get_rss_irn(rss, irn);
1581 plist_insert_back(c->elements, irn);
1584 DB((rss->dbg, LEVEL_2, " -> %+F (%d)", irn, target));
1586 /* new source = last target */
1590 DB((rss->dbg, LEVEL_2, "\n"));
1595 Computing the maximal antichain: Select an element from each
1596 chain such, such it is parallel with the others.
1598 DBG((rss->dbg, LEVEL_1, "\t\tcomputing set of saturation values (MAX AC)\n"));
1599 DBG((rss->dbg, LEVEL_3, "\t\tstarting with:\n"));
1602 if (firm_dbg_get_mask(rss->dbg) & LEVEL_3)
1603 dump_nodeset(values, "\t\t\t");
1609 We need an explicit array for the values as
1610 we cannot iterate multiple times over the same
1611 set at the same time. :-(((((
1612 TODO Matze: now we can, so rewrite this...
1614 int n = ir_nodeset_size(values);
1616 ir_node **val_arr = NEW_ARR_F(ir_node *, n);
1618 foreach_ir_nodeset(values, u_irn, iter)
1619 val_arr[i++] = u_irn;
1622 ir_nodeset_destroy(temp);
1626 temp = xmalloc(sizeof(temp[0]));
1627 ir_nodeset_init_size(temp, 10);
1629 /* Select all nodes from current value set, having another node in the set as descendant. */
1630 for (i = 0; i < n; ++i) {
1631 rss_irn_t *u = get_rss_irn(rss, val_arr[i]);
1633 for (j = 0; j < n; ++j) {
1637 key.src = val_arr[i];
1638 key.tgt = val_arr[j];
1640 if (pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
1641 /* v[j] is descendant of u -> remove u and break */
1642 ir_nodeset_insert(temp, u->irn);
1643 ir_nodeset_remove(values, u->irn);
1645 DBG((rss->dbg, LEVEL_3, "\t\t\tremoving %+F from values, adding it to temp\n", u->irn));
1653 /* Try to insert the chain predecessor of all selected u's */
1654 foreach_ir_nodeset(temp, u_irn, iter) {
1655 rss_irn_t *u = get_rss_irn(rss, u_irn);
1656 chain_t *c = u->chain;
1657 plist_element_t *el = plist_find_value(c->elements, u_irn);
1659 assert(el && "Missing element in chain!");
1661 /* If u has predecessor in chain: insert the predecessor */
1662 if (el == plist_element_get_prev(el)) {
1663 ir_nodeset_insert(values, plist_element_get_value(el));
1664 DBG((rss->dbg, LEVEL_3, "\t\t\tadding %+F to values\n", plist_element_get_value(el)));
1670 } while (ir_nodeset_size(temp) > 0);
1672 DBG((rss->dbg, LEVEL_2, "\t\tfinal set:\n"));
1674 if (firm_dbg_get_mask(rss->dbg) & LEVEL_2) {
1675 dump_nodeset(values, "\t\t\t");
1679 if (rss->opts->dump_flags & RSS_DUMP_MAXAC)
1680 debug_vcg_dump_pkg(rss, values, iteration);
1683 ir_nodeset_destroy(temp);
1693 * Computes the best serialization between two nodes of sat_vals.
1695 static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nodeset_t *sat_vals, serialization_t *ser, int num_regs) {
1696 int n = ir_nodeset_size(sat_vals);
1697 int n_idx = ARR_LEN_SAFE(rss->idx_map);
1699 ir_node **val_arr = alloca(n * sizeof(val_arr[0]));
1700 bitset_t *bs_sv = bitset_alloca(n_idx);
1701 bitset_t *bs_vdesc = bitset_alloca(n_idx);
1702 bitset_t *bs_tmp = bitset_alloca(n_idx);
1703 bitset_t *bs_ukilldesc = bitset_alloca(n_idx);
1704 int best_benefit = INT_MAX;
1705 int best_omega2 = INT_MAX;
1706 int best_benefit_omega20 = INT_MAX;
1710 ir_nodeset_iterator_t iter;
1711 rss_edge_t min_benefit_edge;
1712 rss_edge_t min_omega20_edge;
1713 rss_irn_t *ser_u_omega1 = NULL, *ser_v_omega1 = NULL;
1714 rss_irn_t *ser_u_omega20 = NULL, *ser_v_omega20 = NULL;
1716 DBG((rss->dbg, LEVEL_1, "\tcomputing admissible serializations:\n"));
1719 We need an explicit array for the values as
1720 we cannot iterate multiple times over the same
1721 set at the same time. :-(((((
1724 foreach_ir_nodeset(sat_vals, irn, iter) {
1726 bitset_set(bs_sv, BLOCK_IDX_MAP(rss, irn));
1730 We build all admissible serializations and remember the best found so far.
1733 if v in pkiller(u): add edge from v to all other pkiller(u)
1734 else: for all vv in pkiller(u): add edge from v to vv if there exists no path from vv to v
1738 A node is unserializable if:
1739 - it has only one killer and this one is Sink
1740 - it kills no other values
1741 In this case there is no serialization which could
1742 reduce the registerpressure
1744 #define IS_UNSERIALIZABLE_NODE(rss_node) \
1747 (plist_count(rss_node->pkiller_list) == 1) && \
1748 is_Sink(rss_node->killer) && \
1749 (rss_node->kill_count == 0) \
1751 be_is_Barrier(rss_node->irn) || \
1752 be_is_Keep(rss_node->irn) \
1755 /* for all u in sat_vals */
1756 for (i = 0; i < n; ++i) {
1757 rss_irn_t *u = get_rss_irn(rss, val_arr[i]);
1758 plist_element_t *el;
1760 /* ignore nodes where serialization does not help */
1761 if (IS_UNSERIALIZABLE_NODE(u)) {
1762 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", u->irn));
1766 /* accumulate all descendants of all pkiller(u) */
1767 bitset_clear_all(bs_ukilldesc);
1768 foreach_plist(u->pkiller_list, el) {
1769 ir_node *irn = plist_element_get_value(el);
1770 rss_irn_t *node = get_rss_irn(rss, irn);
1773 bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, irn));
1777 for (k = ARR_LEN_SAFE(node->descendants) - 1; k >= 0; --k) {
1778 if (! is_Sink(node->descendants[k]))
1779 bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, node->descendants[k]));
1783 /* for all v in sat_vals */
1784 for (j = 0; j < n; ++j) {
1785 ir_node *v_irn = val_arr[j];
1786 rss_irn_t *v = get_rss_irn(rss, v_irn);
1787 unsigned v_height = get_irn_height(rss->h, v_irn);
1788 int omega1, omega2, is_pkiller;
1790 /* v cannot be serialized with itself
1791 * ignore nodes where serialization does not help */
1792 if (i == j || IS_UNSERIALIZABLE_NODE(v)) {
1794 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", v->irn));
1798 /* get descendants of v */
1799 bitset_clear_all(bs_vdesc);
1800 bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v_irn));
1801 for (k = ARR_LEN_SAFE(v->descendants) - 1; k >= 0; --k) {
1802 if (! is_Sink(v->descendants[k]))
1803 bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v->descendants[k]));
1806 /* if v is in pkiller(u) */
1807 is_pkiller = plist_has_value(u->pkiller_list, v_irn);
1809 /* for all vv in pkiller(u) */
1810 foreach_plist(u->pkiller_list, el) {
1811 ir_node *vv_irn = plist_element_get_value(el);
1814 if (is_Sink(vv_irn) || is_cfop(vv_irn))
1818 add_edge = vv_irn != v_irn && skip_Proj(vv_irn) != skip_Proj(v_irn);
1820 add_edge = ! heights_reachable_in_block(rss->h, skip_Proj(vv_irn), skip_Proj(v_irn));
1823 As we add an edge from vv -> v, we have to make sure,
1824 that there exists no path from v to vv.
1828 unsigned vv_height = get_irn_height(rss->h, vv_irn);
1829 unsigned critical_path_cost;
1833 mu1 = | descendants(v) cut sat_vals |
1834 the number of saturating values which cannot
1835 be simultaneously alive with u
1837 bitset_copy(bs_tmp, bs_vdesc);
1838 mu1 = bitset_popcnt(bitset_and(bs_tmp, bs_sv));
1841 mu2 = | accum_desc_all_pkiller(u) without descendants(v) |
1844 bitset_copy(bs_tmp, bs_ukilldesc);
1845 mu2 = bitset_popcnt(bitset_andnot(bs_tmp, bs_vdesc));
1851 /* omega1 = mu1 - mu2 */
1857 /* omega2 = increase of critical path */
1858 critical_path_cost =
1859 v_height /* longest path from v to sink */
1860 + rss->max_height - vv_height /* longest path from source to vv */
1864 If critical_path_cost > max_height -> the new edge
1865 would increase the longest critical path by the difference.
1867 omega2 = critical_path_cost > rss->max_height ? critical_path_cost - rss->max_height : 0;
1869 /* this keeps track of the edge with the best benefit */
1870 if (omega1 >= num_regs - n && omega1 < best_benefit) {
1871 min_benefit_edge.src = v_irn;
1872 min_benefit_edge.tgt = vv_irn;
1877 best_benefit = omega1;
1878 ser->new_killer = is_pkiller;
1881 /* this keeps track of the edge with the best omega1 costs where omega2 == 0 */
1882 if (omega2 == 0 && omega1 >= num_regs - n && omega1 < best_benefit_omega20) {
1883 min_omega20_edge.src = v_irn;
1884 min_omega20_edge.tgt = vv_irn;
1889 best_benefit_omega20 = omega1;
1890 ser->new_killer = is_pkiller;
1893 best_omega2 = MIN(best_omega2, omega2);
1895 DBG((rss->dbg, LEVEL_2, "\t\tfound %+F -> %+F (w1 %d, w2 %d)\n",
1896 v_irn, vv_irn, omega1, omega2));
1898 } /* for all vv in pkiller(u) */
1899 } /* for all v in sat_vals */
1900 } /* for all u in sat_vals */
1905 if (best_omega2 == 0) {
1906 ser->u = ser_u_omega20;
1907 ser->v = ser_v_omega20;
1908 ser->edge->src = min_omega20_edge.src;
1909 ser->edge->tgt = min_omega20_edge.tgt;
1910 ser->omega1 = best_benefit_omega20;
1911 ser->omega2 = best_omega2;
1914 ser->u = ser_u_omega1;
1915 ser->v = ser_v_omega1;
1916 ser->edge->src = min_benefit_edge.src;
1917 ser->edge->tgt = min_benefit_edge.tgt;
1918 ser->omega1 = best_benefit;
1919 ser->omega2 = best_omega2;
1924 #undef IS_UNSERIALIZABLE_NODE
1928 * Perform the value serialization heuristic and add all
1929 * computed serialization edges as dependencies to the irg.
1931 static void perform_value_serialization_heuristic(rss_t *rss) {
1932 bitset_t *arch_nonign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls));
1933 bitset_t *abi_ign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls));
1934 unsigned available_regs, iteration;
1936 ir_nodeset_t *sat_vals;
1937 pset *ser_set = new_pset(cmp_rss_edges, 20);
1939 /* available_regs = R = |arch_non_ignore_regs cut ~abi_ignore_regs| */
1940 arch_put_non_ignore_regs(rss->arch_env, rss->cls, arch_nonign_bs);
1941 be_abi_put_ignore_regs(rss->abi, rss->cls, abi_ign_bs);
1942 bitset_andnot(arch_nonign_bs, abi_ign_bs);
1943 available_regs = bitset_popcnt(arch_nonign_bs);
1944 //num_live = pset_count(rss->live_block);
1945 //available_regs -= num_live < available_regs ? num_live : 0;
1947 DBG((rss->dbg, LEVEL_1, "\n\t#available regs: %d\n\n", available_regs));
1950 At first we need to compute the disjoint value DAG (DVG = {V, E_dv}).
1951 V = set of all nodes we are currently interested in
1952 E_dv = there is an edge from u to v iff v is a descendant of killer(u), forall u, v in V
1954 ir_nodeset_init_size(&dvg.nodes, plist_count(rss->nodes));
1955 dvg.edges = new_pset(cmp_rss_edges, plist_count(rss->nodes) * 5);
1956 compute_dvg(rss, &dvg);
1959 Then we perform the heuristic serialization algorithm
1960 on the DVG which gives us all necessary serialization
1963 DBG((rss->dbg, LEVEL_1, "\tcomputing maximal antichain:\n"));
1965 sat_vals = compute_maximal_antichain(rss, &dvg, iteration++);
1966 while (sat_vals && (ir_nodeset_size(sat_vals) > available_regs)) {
1967 serialization_t *ser, best_ser;
1968 rss_edge_t *edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*edge));
1969 ir_node *dep_src, *dep_tgt;
1971 best_ser.edge = edge;
1972 ser = compute_best_admissible_serialization(rss, sat_vals, &best_ser, available_regs);
1974 DBG((rss->dbg, LEVEL_1, "\tcurrent register saturation %d, target %d\n", ir_nodeset_size(sat_vals), available_regs));
1977 DBG((rss->dbg, LEVEL_1, "\tno RS improving serialization found, breaking at iteration %d\n", iteration));
1981 /* Insert the serialization as dependency edge into the irg. */
1982 DBG((rss->dbg, LEVEL_1, "\tserializing %+F -> %+F with edge %+F -> %+F and cost %d, %d\n",
1983 ser->u->irn, ser->v->irn, ser->edge->src, ser->edge->tgt, ser->omega1, ser->omega2));
1985 if (pset_find(ser_set, ser->edge, HASH_RSS_EDGE(ser->edge)))
1986 ir_printf("WARNING: serialization %+F -> %+F computed twice!\n", ser->edge->src, ser->edge->tgt);
1989 pset_insert(ser_set, ser->edge, HASH_RSS_EDGE(ser->edge));
1991 /* update the dvg */
1992 update_dvg(rss, &dvg, ser->v, ser->u);
1993 update_dvg(rss, &dvg, get_rss_irn(rss, ser->edge->src), get_rss_irn(rss, ser->edge->tgt));
1994 if(sat_vals != NULL) {
1995 ir_nodeset_destroy(sat_vals);
1999 dep_src = skip_Proj(ser->edge->src);
2000 dep_tgt = ser->edge->tgt;
2001 add_irn_dep(dep_src, dep_tgt);
2003 /* Update descendants, consumer and pkillers of the target */
2004 update_node_info(rss, ser->edge->tgt, ser->edge->src);
2006 /* TODO: try to find a cheaper way for updating height information */
2007 rss->max_height = heights_recompute_block(rss->h, rss->block);
2009 /* Recompute the antichain for next serialization */
2010 DBG((rss->dbg, LEVEL_1, "\tre-computing maximal antichain:\n"));
2011 sat_vals = compute_maximal_antichain(rss, &dvg, iteration++);
2014 ir_nodeset_destroy(&dvg.nodes);
2015 del_pset(dvg.edges);
2019 * Do initial calculations for a block.
2021 static void process_block(ir_node *block, void *env) {
2024 const ir_edge_t *edge;
2026 phase_init(&rss->ph, "rss block preprocessor", rss->irg, PHASE_DEFAULT_GROWTH, init_rss_irn, NULL);
2028 DBG((rss->dbg, LEVEL_1, "preprocessing block %+F\n", block));
2031 /* build an index map for all nodes in the current block */
2033 n = get_irn_n_edges(block);
2034 NEW_ARR_A(int *, rss->idx_map, n);
2035 foreach_out_edge(block, edge) {
2036 ir_node *irn = get_edge_src_irn(edge);
2037 rss->idx_map[i++] = get_irn_idx(irn);
2039 qsort(rss->idx_map, n, sizeof(rss->idx_map[0]), cmp_int);
2040 rss->max_height = heights_recompute_block(rss->h, block);
2042 /* loop over all register classes */
2043 for (i = arch_isa_get_n_reg_class(rss->arch_env->isa) - 1; i >= 0; --i) {
2044 const arch_register_class_t *cls = arch_isa_get_reg_class(rss->arch_env->isa, i);
2047 DBG((rss->dbg, LEVEL_1, "register class %s\n", arch_register_class_name(cls)));
2049 /* Get all live value at end of Block having current register class */
2050 rss->live_block = pset_new_ptr(10);
2051 be_liveness_end_of_block(rss->liveness, rss->arch_env, rss->cls, rss->block, rss->live_block);
2053 /* reset the list of interesting nodes */
2054 plist_clear(rss->nodes);
2055 plist_insert_back(rss->nodes, _sink);
2057 /* collect all nodes having a certain register class */
2058 foreach_out_edge(block, edge) {
2059 ir_node *irn = get_edge_src_irn(edge);
2060 ir_mode *mode = get_irn_mode(irn);
2064 - mode_T nodes (the projs are asked)
2065 - mode_X nodes (control flow nodes are always scheduled last)
2066 - Keeps (they are always immediately scheduled)
2067 - Phi (same as Keep)
2069 if (mode == mode_T || mode == mode_X || is_Phi(irn))
2073 In case of a proj, we skip
2074 - Barrier (they are a Barrier :)
2076 - the Proj itself, as it's scheduled always with it's super node
2079 ir_node *pred = get_Proj_pred(irn);
2080 if (be_is_Barrier(pred) || is_Start(pred))
2084 /* calculate the descendants and consumer for each node in the block */
2085 collect_node_info(rss, skip_Proj(irn));
2087 if (be_is_Keep(irn))
2090 if (! arch_irn_is(rss->arch_env, irn, ignore) && arch_get_irn_reg_class(rss->arch_env, irn, -1) == cls) {
2091 plist_insert_back(rss->nodes, skip_Proj(irn));
2096 /* compute the potential killing set PK(G) */
2097 compute_pkill_set(rss);
2099 /* compute the killing function k* */
2100 compute_killing_function(rss);
2103 Compute the heuristic value serialization and
2104 add the necessary dependencies to the irg.
2106 perform_value_serialization_heuristic(rss);
2108 del_pset(rss->live_block);
2111 phase_free(&rss->ph);
2115 * Register the options.
2117 void be_init_schedrss(void) {
2118 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
2119 lc_opt_entry_t *sched_grp = lc_opt_get_grp(be_grp, "sched");
2120 lc_opt_entry_t *rss_grp = lc_opt_get_grp(sched_grp, "rss");
2122 lc_opt_add_table(rss_grp, rss_option_table);
2125 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_schedrss);
2128 * Preprocess the irg for scheduling.
2130 void rss_schedule_preparation(const be_irg_t *birg) {
2131 ir_graph *irg = be_get_birg_irg(birg);
2134 FIRM_DBG_REGISTER(rss.dbg, "firm.be.sched.rss");
2136 //firm_dbg_set_mask(rss.dbg, LEVEL_1 | LEVEL_2 | LEVEL_3);
2138 init_rss_special_nodes(irg);
2141 rss.arch_env = be_get_birg_arch_env(birg);
2142 rss.abi = birg->abi;
2143 rss.h = heights_new(irg);
2144 rss.nodes = plist_new();
2145 rss.opts = &rss_options;
2146 rss.liveness = be_liveness(irg);
2147 irg_block_walk_graph(irg, NULL, process_block, &rss);
2148 heights_free(rss.h);
2149 plist_free(rss.nodes);
2150 be_liveness_free(rss.liveness);
2152 if (birg->main_env->options->dump_flags & DUMP_SCHED)
2153 be_dump(rss.irg, "-rss", dump_ir_block_graph);