2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Implementation of a register saturating list scheduler.
23 * @author Christian Wuerdig
27 * Implementation of a register saturating list scheduler
28 * as described in: Sid-Ahmed-Ali Touati
29 * Register Saturation in Superscalar and VLIW Codes
40 #include "irgraph_t.h"
42 #include "iredges_t.h"
44 #include "irphase_t.h"
50 #include "bipartite.h"
51 #include "hungarian.h"
59 #include "besched_t.h"
62 #include <libcore/lc_opts.h>
63 #include <libcore/lc_opts_enum.h>
66 #define ARR_LEN_SAFE(arr) ((arr) != NULL ? ARR_LEN((arr)) : 0)
68 #define HASH_RSS_EDGE(edge) ((get_irn_node_nr((edge)->src) << 16) | (get_irn_node_nr((edge)->tgt) & 0xFFFF))
69 #define BSEARCH_IRN_ARR(val, arr) \
70 bsearch(&(val), (arr), ARR_LEN_SAFE((arr)), sizeof((arr)[0]), cmp_irn_idx)
72 #define BLOCK_IDX_MAP(rss, irn) bsearch_for_index(get_irn_idx((irn)), (rss)->idx_map, ARR_LEN_SAFE((rss)->idx_map), 1)
75 typedef struct _rss_opts_t {
79 /* Represents a child with associated costs */
80 typedef struct _child {
85 /* We need edges for several purposes. */
86 typedef struct _rss_edge {
92 /* Represents a connected bipartite component. */
94 ir_nodeset_t parents; /**< = S a set of value producers */
95 ir_nodeset_t children; /**< = T a set of value consumers */
96 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 */
97 int nr; /**< a deterministic index for set insertion (used as hash) */
100 /* Represents a disjoint value DAG. */
101 typedef struct _dvg {
106 /* Represents a chain of nodes. */
107 typedef struct _chain {
108 plist_t *elements; /**< List of chain elements */
109 int nr; /**< a deterministic index for set insertion (used as hash) */
112 typedef struct _rss_irn {
113 plist_t *consumer_list; /**< List of consumers */
114 ir_node **consumer; /**< Sorted consumer array (needed for faster access) */
116 plist_t *parent_list; /**< List of parents */
117 plist_t *pkiller_list; /**< List of potential killers */
119 plist_t *descendant_list; /**< List of descendants */
120 ir_node **descendants; /**< Sorted descendant array (needed for faster access) */
122 ir_node *killer; /**< The selected unique killer */
123 ir_node *irn; /**< The corresponding firm node to this rss_irn */
125 chain_t *chain; /**< The chain, this node is associated to */
127 unsigned desc_walk; /**< visited flag for collecting descendants */
128 unsigned kill_count; /**< number of nodes killed by this one */
130 unsigned live_out : 1; /**< irn has consumers outside of it's block */
131 unsigned visited : 1; /**< visited flag for bipartite decomposition */
132 unsigned havecons : 1; /**< visited flag collect consumer */
133 unsigned handled : 1; /**< flag indicating whether or not the list structures have been build */
134 unsigned dumped : 1; /**< flag indication whether or not this node was dumped */
137 /* Represents a serialization edge with associated costs. */
138 typedef struct _serialization {
139 rss_irn_t *u; /* the top node */
140 rss_irn_t *v; /* the node about to be serialized after u */
141 rss_edge_t *edge; /* the edge selected for the serialization */
142 int omega1; /* estimated: available regs - RS reduction */
143 int omega2; /* increase in critical path length */
147 typedef struct _rss {
148 ir_phase ph; /**< Phase to hold some data */
149 heights_t *h; /**< The current height object */
150 ir_graph *irg; /**< The irg to preprocess */
151 plist_t *nodes; /**< The list of interesting nodes */
152 const arch_env_t *arch_env; /**< The architecture environment */
153 be_abi_irg_t *abi; /**< The abi for this irg */
154 pset *cbc_set; /**< A set of connected bipartite components */
155 ir_node *block; /**< The current block in progress. */
156 int *idx_map; /**< Mapping irn indices to per block indices */
157 unsigned max_height; /**< maximum height in the current block */
158 rss_opts_t *opts; /**< The options */
159 be_lv_t *liveness; /**< The liveness information for this irg */
160 ir_nodeset_t live_block; /**< Values alive at end of block */
161 const arch_register_class_t *cls; /**< The current register class */
162 DEBUG_ONLY(firm_dbg_module_t *dbg);
165 #define get_rss_irn(rss, irn) (phase_get_or_set_irn_data(&rss->ph, irn))
168 * We need some special nodes:
169 * a source and a sink for all live-in and live-out values of a block
177 /** The opcode of the rss_Source node once allocated. */
178 static ir_op *op_rss_Source;
179 /** The opcode of the rss_Sink node once allocated. */
180 static ir_op *op_rss_Sink;
182 /** The rss_Source node of the current graph. */
183 static ir_node *_source = NULL;
184 /** The rss_Sink node of the current graph. */
185 static ir_node *_sink = NULL;
187 #define is_Source(irn) ((irn) == _source)
188 #define is_Sink(irn) ((irn) == _sink)
192 RSS_DUMP_CBC = 1 << 0,
193 RSS_DUMP_PKG = 1 << 1,
194 RSS_DUMP_KILL = 1 << 2,
195 RSS_DUMP_DVG = 1 << 3,
196 RSS_DUMP_MAXAC = 1 << 4,
197 RSS_DUMP_ALL = (RSS_DUMP_MAXAC << 1) - 1,
200 static rss_opts_t rss_options = {
204 static const lc_opt_enum_int_items_t dump_items[] = {
205 { "none", RSS_DUMP_NONE },
206 { "cbc", RSS_DUMP_CBC },
207 { "pkg", RSS_DUMP_PKG },
208 { "kill", RSS_DUMP_KILL },
209 { "dvg", RSS_DUMP_DVG },
210 { "maxac", RSS_DUMP_MAXAC },
211 { "all", RSS_DUMP_ALL },
215 static lc_opt_enum_int_var_t dump_var = {
216 &rss_options.dump_flags, dump_items
219 static const lc_opt_table_entry_t rss_option_table[] = {
220 LC_OPT_ENT_ENUM_MASK("dump", "dump phases", &dump_var),
224 /******************************************************************************
226 * | | | | / _| | | (_)
227 * | |__ ___| |_ __ ___ _ __ | |_ _ _ _ __ ___| |_ _ ___ _ __ ___
228 * | '_ \ / _ \ | '_ \ / _ \ '__| | _| | | | '_ \ / __| __| |/ _ \| '_ \/ __|
229 * | | | | __/ | |_) | __/ | | | | |_| | | | | (__| |_| | (_) | | | \__ \
230 * |_| |_|\___|_| .__/ \___|_| |_| \__,_|_| |_|\___|\__|_|\___/|_| |_|___/
233 ******************************************************************************/
236 * Acquire opcodes if needed and create source and sink nodes.
238 static void init_rss_special_nodes(ir_graph *irg) {
241 if (op_rss_Source == NULL) {
242 int iro_rss_base = get_next_ir_opcodes(iro_rss_last);
243 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);
244 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);
246 block = get_irg_start_block(irg);
247 _source = new_ir_node(NULL, irg, block, op_rss_Source, mode_ANY, 0, NULL);
248 _sink = new_ir_node(NULL, irg, block, op_rss_Sink, mode_ANY, 0, NULL);
251 static int cmp_int(const void *a, const void *b) {
255 return QSORT_CMP(*i1, *i2);
258 static int cmp_child_costs(const void *a, const void *b) {
259 const child_t *c1 = a;
260 const child_t *c2 = b;
262 return QSORT_CMP(c1->cost, c2->cost);
265 static int cmp_irn_idx(const void *a, const void *b) {
266 const ir_node *n1 = *(ir_node **)a;
267 const ir_node *n2 = *(ir_node **)b;
269 return QSORT_CMP(get_irn_idx(n1), get_irn_idx(n2));
272 static int cmp_rss_edges(const void *a, const void *b) {
273 const rss_edge_t *e1 = a;
274 const rss_edge_t *e2 = b;
276 return (e1->src != e2->src) || (e1->tgt != e2->tgt);
279 static int bsearch_for_index(int key, int *arr, size_t len, int force) {
283 while (right >= left) {
284 int idx = (left + right) / 2;
288 else if (key > arr[idx])
295 assert(0 && "Something is wrong, key not found.");
299 static ir_node **build_sorted_array_from_list(plist_t *irn_list, struct obstack *obst) {
302 int len = plist_count(irn_list);
303 ir_node **arr = NEW_ARR_D(ir_node *, obst, len);
305 /* copy the list into the array */
306 foreach_plist(irn_list, el) {
307 arr[i++] = plist_element_get_value(el);
310 /* sort the array by node index */
311 qsort(arr, len, sizeof(arr[0]), cmp_irn_idx);
316 /*****************************************************
319 * __| | ___| |__ _ _ __ _ __ _ _ _ __ __ _
320 * / _` |/ _ \ '_ \| | | |/ _` |/ _` | | '_ \ / _` |
321 * | (_| | __/ |_) | |_| | (_| | (_| | | | | | (_| |
322 * \__,_|\___|_.__/ \__,_|\__, |\__, |_|_| |_|\__, |
326 *****************************************************/
329 static void dump_nodeset(ir_nodeset_t *ns, const char *prefix) {
330 ir_nodeset_iterator_t iter;
333 ir_nodeset_iterator_init(&iter, ns);
334 while( (irn = ir_nodeset_iterator_next(&iter)) != NULL ) {
335 ir_fprintf(stderr, "%s%+F\n", prefix, irn);
340 static void build_file_name(rss_t *rss, const char *suffix, size_t suf_len, char *buf, size_t len) {
341 const char *irg_name;
344 irg_name = get_entity_name(get_irg_entity(rss->irg));
345 snprintf(buf, len - suf_len, "%s-%s-block-%ld",
346 irg_name, arch_register_class_name(rss->cls), get_irn_node_nr(rss->block));
350 /* Dumps all collected bipartite components of current irg as vcg. */
351 static void debug_vcg_dump_bipartite(rss_t *rss) {
355 static const char suffix[] = "-RSS-CBC.vcg";
357 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
358 f = fopen(file_name, "w");
360 ir_fprintf(f, "graph: { title: \"connected bipartite component graph of %+F\"\n", rss->irg);
361 fprintf(f, "display_edge_labels: no\n");
362 fprintf(f, "layoutalgorithm: mindepth\n");
363 fprintf(f, "manhattan_edges: yes\n\n");
365 foreach_pset(rss->cbc_set, cbc) {
366 ir_nodeset_iterator_t iter;
370 fprintf(f, "graph: { titel: \"cbc %d\" label: \"cbc %d\" status:clustered color:yellow\n", cbc->nr, cbc->nr);
371 foreach_ir_nodeset(&cbc->parents, n, iter) {
372 ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
374 foreach_ir_nodeset(&cbc->children, n, iter) {
375 ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
377 foreach_pset(cbc->kill_edges, ke) {
378 ir_fprintf(f, "edge: { sourcename: \"n%d_%d\" targetname: \"n%d_%d\" }\n",
379 get_irn_node_nr(ke->src), cbc->nr, get_irn_node_nr(ke->tgt), cbc->nr);
387 /* Dump the computed killing function as vcg. */
388 static void debug_vcg_dump_kill(rss_t *rss) {
392 static const char suffix[] = "-RSS-KILL.vcg";
394 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
395 f = fopen(file_name, "w");
397 ir_fprintf(f, "graph: { title: \"computed kill graph of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
398 fprintf(f, "display_edge_labels: no\n");
399 fprintf(f, "layoutalgorithm: mindepth\n");
400 fprintf(f, "manhattan_edges: yes\n\n");
403 /* reset dump_flag */
405 foreach_phase_irn(&rss->ph, irn) {
406 rss_irn_t *node = get_rss_irn(rss, irn);
411 /* dump all nodes and their killers */
412 foreach_plist(rss->nodes, el) {
413 ir_node *irn = plist_element_get_value(el);
414 rss_irn_t *rirn = get_rss_irn(rss, irn);
415 rss_irn_t *pk_rirn = get_rss_irn(rss, rirn->killer);
417 if (! rirn->dumped) {
418 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
422 if (! pk_rirn->dumped) {
423 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(rirn->killer), rirn->killer);
427 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
428 get_irn_node_nr(rirn->killer), get_irn_node_nr(irn));
435 /* Dumps the potential killing DAG (PKG) as vcg. */
436 static void debug_vcg_dump_pkg(rss_t *rss, ir_nodeset_t *max_ac, int iteration) {
439 char *suffix = alloca(32);
440 static const char suffix1[] = "-RSS-PKG.vcg";
441 static const char suffix2[] = "-RSS-PKG-MAXAC.vcg";
445 snprintf(suffix, 32, "%s", suffix1);
448 snprintf(suffix, 32, "-%02d%s", iteration, suffix2);
451 build_file_name(rss, suffix, strlen(suffix) + 1, file_name, sizeof(file_name));
452 f = fopen(file_name, "w");
454 ir_fprintf(f, "graph: { title: \"potential killing DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
455 fprintf(f, "display_edge_labels: no\n");
456 fprintf(f, "layoutalgorithm: mindepth\n");
457 fprintf(f, "manhattan_edges: yes\n\n");
460 /* reset dump_flag */
462 foreach_phase_irn(&rss->ph, irn) {
463 rss_irn_t *node = get_rss_irn(rss, irn);
468 foreach_plist(rss->nodes, el) {
469 ir_node *irn = plist_element_get_value(el);
470 rss_irn_t *rirn = get_rss_irn(rss, irn);
472 plist_element_t *k_el;
474 /* dump selected saturating values in yellow */
475 if (max_ac && ir_nodeset_contains(max_ac, irn))
478 if (! rirn->dumped) {
480 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(irn), irn, rirn->chain->nr, c1);
482 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(irn), irn, c1);
486 foreach_plist(rirn->pkiller_list, k_el) {
487 ir_node *pkiller = plist_element_get_value(k_el);
488 rss_irn_t *pk_rirn = get_rss_irn(rss, pkiller);
491 if (max_ac && ir_nodeset_contains(max_ac, pkiller))
494 if (! pk_rirn->dumped) {
496 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(pkiller), pkiller, pk_rirn->chain->nr, c2);
498 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(pkiller), pkiller, c2);
501 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
502 get_irn_node_nr(pkiller), get_irn_node_nr(irn));
509 /* Dumps the disjoint value DAG (DVG) as vcg. */
510 static void debug_vcg_dump_dvg(rss_t *rss, dvg_t *dvg) {
511 static const char suffix[] = "-RSS-DVG.vcg";
514 ir_nodeset_iterator_t iter;
518 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
519 f = fopen(file_name, "w");
521 ir_fprintf(f, "graph: { title: \"disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
522 fprintf(f, "display_edge_labels: no\n");
523 fprintf(f, "layoutalgorithm: mindepth\n");
524 fprintf(f, "manhattan_edges: yes\n\n");
527 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
528 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
532 foreach_pset(dvg->edges, edge) {
533 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
534 get_irn_node_nr(edge->src), get_irn_node_nr(edge->tgt));
542 /* Dumps the PKG(DVG). */
543 static void debug_vcg_dump_dvg_pkiller(rss_t *rss, dvg_t *dvg) {
544 static const char suffix[] = "-RSS-DVG-PKG.vcg";
547 ir_nodeset_iterator_t iter;
550 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
551 f = fopen(file_name, "w");
553 ir_fprintf(f, "graph: { title: \"PKG of disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
554 fprintf(f, "display_edge_labels: no\n");
555 fprintf(f, "layoutalgorithm: mindepth\n");
556 fprintf(f, "manhattan_edges: yes\n\n");
559 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
560 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
564 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
565 rss_irn_t *node = get_rss_irn(rss, irn);
568 foreach_plist(node->dvg_pkiller_list, el) {
569 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
570 get_irn_node_nr(plist_element_get_value(el)), get_irn_node_nr(irn));
580 * In case there is no rss information for irn, initialize it.
582 static void *init_rss_irn(ir_phase *ph, ir_node *irn, void *old) {
583 rss_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
585 res->descendant_list = plist_obstack_new(phase_obst(ph));
586 res->descendants = NULL;
588 res->consumer_list = plist_obstack_new(phase_obst(ph));
589 res->consumer = NULL;
591 res->pkiller_list = plist_obstack_new(phase_obst(ph));
593 res->parent_list = plist_obstack_new(phase_obst(ph));
611 * Collect all nodes data dependent on current node.
613 static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int *got_sink, unsigned cur_desc_walk) {
614 const ir_edge_t *edge;
615 rss_irn_t *cur_node = get_rss_irn(rss, irn);
616 ir_node *block = rss->block;
617 ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
620 if (cur_node->desc_walk >= cur_desc_walk)
622 cur_node->desc_walk = cur_desc_walk;
624 /* Stop at Barriers */
625 if (be_is_Barrier(irn))
628 /* loop over normal and dependency edges */
629 for (i = 0; i < 2; ++i) {
630 foreach_out_edge_kind(irn, edge, ekind[i]) {
631 ir_node *user = get_edge_src_irn(edge);
633 /* skip ignore nodes as they do not really contribute to register pressure */
634 if (arch_irn_is(rss->arch_env, user, ignore))
638 (a) mode_X means Jump -> out_edge
639 (b) Phi as user of a normal node -> out-edge
641 if (get_irn_mode(user) == mode_X || is_Phi(user)) {
650 //if (arch_get_irn_reg_class(rss->arch_env, user, -1) == rss->cls)
651 collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
654 /* check if user lives in block and is not a control flow node */
655 if (get_nodes_block(user) == block) {
656 if (! plist_has_value(rirn->descendant_list, user)) {
657 plist_insert_back(rirn->descendant_list, user);
658 DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", user));
660 collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
662 else if (! *got_sink) {
664 /* user lives out of block: add sink as descendant if not already done */
665 plist_insert_back(rirn->descendant_list, _sink);
667 DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", _sink));
675 * Handles a single consumer.
677 static void collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *consumer, int *got_sink) {
678 ir_node *block = rss->block;
680 assert(! is_Proj(consumer) && "Cannot handle Projs");
682 if (! is_Phi(consumer) && ! is_Block(consumer) && get_nodes_block(consumer) == block) {
683 if (! arch_irn_is(rss->arch_env, consumer, ignore) && ! plist_has_value(rss_irn->consumer_list, consumer)) {
684 plist_insert_back(rss_irn->consumer_list, consumer);
685 DBG((rss->dbg, LEVEL_2, "\t\tconsumer %+F\n", consumer));
689 rss_irn->live_out = 1;
690 DBG((rss->dbg, LEVEL_2, "\t\tlive out %+F", consumer));
692 plist_insert_back(rss_irn->consumer_list, _sink);
694 DB((rss->dbg, LEVEL_2, ", %+F added instead", _sink));
696 DB((rss->dbg, LEVEL_2, "\n"));
701 * Collect all nodes consuming the value(s) produced by current node.
703 static void collect_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *irn, int *got_sink) {
704 const ir_edge_t *edge;
706 ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
707 rss_irn_t *cur_node = get_rss_irn(rss, irn);
709 if (cur_node->havecons)
711 cur_node->havecons = 1;
713 for (i = 0; i < 2; ++i) {
714 foreach_out_edge_kind(irn, edge, ekind[i]) {
715 ir_node *consumer = get_edge_src_irn(edge);
717 if (is_Proj(consumer)) {
718 //if (arch_get_irn_reg_class(rss->arch_env, consumer, -1) == rss->cls)
719 collect_consumer(rss, rss_irn, consumer, got_sink);
722 collect_single_consumer(rss, rss_irn, consumer, got_sink);
728 * Collects all consumer and descendant of a irn.
730 static void collect_node_info(rss_t *rss, ir_node *irn) {
731 static unsigned cur_desc_walk = 0;
732 rss_irn_t *rss_irn = get_rss_irn(rss, irn);
735 assert(! is_Proj(irn) && "Cannot handle Projs.");
737 /* check if node info is already available */
738 if (rss_irn->handled)
740 //phase_reinit_single_irn_data(&rss->ph, irn);
742 DBG((rss->dbg, LEVEL_1, "\tcomputing consumers of %+F:\n", irn));
744 /* collect all consumer */
746 collect_consumer(rss, rss_irn, irn, &got_sink);
748 /* build sorted consumer array */
749 rss_irn->consumer = build_sorted_array_from_list(rss_irn->consumer_list, phase_obst(&rss->ph));
751 DBG((rss->dbg, LEVEL_1, "\tcompute descendants of %+F:\n", irn));
753 /* collect descendants */
755 collect_descendants(rss, rss_irn, irn, &got_sink, ++cur_desc_walk);
757 /* build sorted descendant array */
758 rss_irn->descendants = build_sorted_array_from_list(rss_irn->descendant_list, phase_obst(&rss->ph));
760 rss_irn->handled = 1;
764 * Checks if v is a potential killer of u.
765 * v is in pkill(u) iff descendants(v) cut consumer(u) is v
767 * @param rss The rss object
768 * @param v The node to check for killer
769 * @param u The potentially killed value
770 * @return 1 if v is in pkill(u), 0 otherwise
772 static int is_potential_killer(rss_t *rss, rss_irn_t *v, rss_irn_t *u) {
778 assert(is_Sink(v->irn) || ((plist_count(v->descendant_list) > 0 && v->descendants) || 1));
779 assert(is_Sink(u->irn) || ((plist_count(u->consumer_list) > 0 && u->consumer) || 1));
781 /* as we loop over the list: loop over the shorter one */
782 if (plist_count(v->descendant_list) > plist_count(u->consumer_list)) {
783 list = u->consumer_list;
784 arr = v->descendants;
787 list = v->descendant_list;
791 /* for each list element: try to find element in array */
792 foreach_plist(list, el) {
793 ir_node *irn = plist_element_get_value(el);
794 ir_node *match = BSEARCH_IRN_ARR(irn, arr);
796 if (match && match != irn)
804 * Update descendants, consumer and pkiller list for the given irn.
806 static void update_node_info(rss_t *rss, ir_node *irn, ir_node *pk_irn) {
807 rss_irn_t *node = get_rss_irn(rss, irn);
808 rss_irn_t *pkiller = get_rss_irn(rss, pk_irn);
810 /* add consumer and rebuild the consumer array */
811 if (! plist_has_value(node->consumer_list, pk_irn)) {
812 plist_insert_back(node->consumer_list, pk_irn);
813 node->consumer = build_sorted_array_from_list(node->consumer_list, phase_obst(&rss->ph));
816 /* add pk_irn as descendant, add it's descendants to irn's and rebuild array */
817 if (! plist_has_value(node->descendant_list, pk_irn)) {
820 plist_insert_back(node->descendant_list, pk_irn);
822 foreach_plist(pkiller->descendant_list, el) {
823 ir_node *desc = plist_element_get_value(el);
825 if (! plist_has_value(node->descendant_list, desc))
826 plist_insert_back(node->descendant_list, desc);
829 node->descendants = build_sorted_array_from_list(node->descendant_list, phase_obst(&rss->ph));
835 * Compute the potential killing set PK.
837 static void compute_pkill_set(rss_t *rss) {
838 plist_element_t *u_el, *v_el;
840 foreach_plist(rss->nodes, u_el) {
841 ir_node *u_irn = plist_element_get_value(u_el);
842 rss_irn_t *u = get_rss_irn(rss, u_irn);
844 DBG((rss->dbg, LEVEL_1, "\tcomputing potential killers of %+F:\n", u_irn));
846 /* check each consumer if it is a potential killer */
847 foreach_plist(u->consumer_list, v_el) {
848 ir_node *v_irn = plist_element_get_value(v_el);
849 rss_irn_t *v = get_rss_irn(rss, v_irn);
851 /* check, if v is a potential killer of u */
852 if (is_potential_killer(rss, v, u)) {
853 if (! plist_has_value(u->pkiller_list, v_irn))
854 plist_insert_back(u->pkiller_list, v_irn);
856 DBG((rss->dbg, LEVEL_2, "\t\tpotential killer %+F\n", v_irn));
863 if (rss->opts->dump_flags & RSS_DUMP_PKG)
864 debug_vcg_dump_pkg(rss, NULL, 0);
868 * Build set of killing edges (from values to their potential killers)
870 static void build_kill_edges(rss_t *rss, pset *epk) {
871 plist_element_t *el, *k_el;
873 foreach_plist(rss->nodes, el) {
874 ir_node *irn = plist_element_get_value(el);
875 rss_irn_t *rirn = get_rss_irn(rss, irn);
877 DBG((rss->dbg, LEVEL_3, "\t\tbuilding kill edges for %+F:\n", irn));
879 foreach_plist(rirn->pkiller_list, k_el) {
880 ir_node *pkiller = plist_element_get_value(k_el);
881 rss_edge_t *ke = obstack_alloc(phase_obst(&rss->ph), sizeof(*ke));
887 DBG((rss->dbg, LEVEL_3, "\t\t\ttarget %+F\n", pkiller));
889 pset_insert(epk, ke, HASH_RSS_EDGE(ke));
895 /* print the given cbc for debugging purpose */
896 static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc) {
897 ir_nodeset_iterator_t iter;
901 DBG((mod, LEVEL_3, "\t\tS = set of parents:\n"));
902 foreach_ir_nodeset(&cbc->parents, n, iter) {
903 DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
905 DBG((mod, LEVEL_3, "\t\tT = set of children:\n"));
906 foreach_ir_nodeset(&cbc->children, n, iter) {
907 DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
909 DBG((mod, LEVEL_3, "\t\tE = Edges from producers to consumers\n"));
910 foreach_pset(cbc->kill_edges, ke) {
911 DBG((mod, LEVEL_3, "\t\t\t%+F -> %+F\n", ke->src, ke->tgt));
917 * Construct the bipartite decomposition.
918 * Sid-Ahmed-Ali Touati, Phd Thesis
919 * Register Pressure in Instruction Level Parallelism, p. 71
921 static void compute_bipartite_decomposition(rss_t *rss) {
922 pset *epk = new_pset(cmp_rss_edges, 10);
927 DBG((rss->dbg, LEVEL_1, "\tcomputing bipartite decomposition:\n"));
929 build_kill_edges(rss, epk);
931 foreach_plist(rss->nodes, el) {
932 ir_node *u_irn = plist_element_get_value(el);
933 rss_irn_t *u = get_rss_irn(rss, u_irn);
939 plist_element_t *el2;
941 rss_edge_t *kedge_root = NULL;
942 ir_node *t_irn, *s_irn;
943 ir_nodeset_iterator_t iter;
945 if (u->visited || u_irn == _sink)
948 DBG((rss->dbg, LEVEL_2, "\t\t%+F choosen:\n", u_irn));
950 cbc = obstack_alloc(phase_obst(&rss->ph), sizeof(*cbc));
953 /* initialize S_cb */
954 ir_nodeset_init_size(&cbc->parents, 5);
955 ir_nodeset_insert(&cbc->parents, u_irn);
956 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (init)\n", u_irn));
959 cbc->kill_edges = new_pset(cmp_rss_edges, 5);
961 /* each parent gets killed by at least one value from children */
963 /* T_cb = PK_successors(u) */
964 ir_nodeset_init_size(&cbc->children, 5);
965 foreach_plist(u->pkiller_list, el2) {
966 ir_nodeset_insert(&cbc->children, plist_element_get_value(el2));
967 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (init)\n", plist_element_get_value(el2)));
971 Now: insert the parents of all children into the parent set
972 and insert the children of all parents into the children set
973 until the sets don't change any more
975 while (p_change || c_change) {
976 ir_nodeset_iterator_t iter;
977 p_change = c_change = 0;
979 /* accumulate parents */
980 foreach_ir_nodeset(&cbc->children, t_irn, iter) {
981 foreach_pset(epk, k_edge) {
982 ir_node *val = k_edge->src;
984 if (k_edge->tgt == t_irn && ! ir_nodeset_contains(&cbc->parents, val)) {
985 ir_nodeset_insert(&cbc->parents, val);
987 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (killed by %+F)\n", val, t_irn));
992 /* accumulate children */
993 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
994 foreach_pset(epk, k_edge) {
995 ir_node *val = k_edge->tgt;
997 if (k_edge->src == s_irn && ! ir_nodeset_contains(&cbc->children, val)) {
998 ir_nodeset_insert(&cbc->children, val);
1000 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (kills %+F)\n", val, s_irn));
1006 /* mark all parent values as visited */
1007 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
1008 rss_irn_t *s = get_rss_irn(rss, s_irn);
1010 /* assure bipartite property */
1012 if (ir_nodeset_contains(&cbc->children, s_irn)) {
1013 ir_nodeset_remove(&cbc->children, s_irn);
1014 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F removed from to children\n", s_irn));
1020 foreach_pset(epk, k_edge) {
1021 if (ir_nodeset_contains(&cbc->parents, k_edge->src) &&
1022 ir_nodeset_contains(&cbc->children, k_edge->tgt)) {
1023 pset_insert(cbc->kill_edges, k_edge, HASH_RSS_EDGE(k_edge));
1025 Link all k_edges which are about to be removed together.
1026 Beware: pset_remove kills the iterator.
1028 k_edge->next = kedge_root;
1029 kedge_root = k_edge;
1033 /* remove all linked k_edges */
1034 for (; kedge_root; kedge_root = kedge_root->next) {
1035 pset_remove(epk, kedge_root, HASH_RSS_EDGE(kedge_root));
1038 /* verify the cbc */
1039 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
1042 foreach_pset(cbc->kill_edges, k_edge) {
1043 if (k_edge->src == s_irn) {
1045 pset_break(cbc->kill_edges);
1052 ir_fprintf(stderr, "Warning: parent %+F is not killed in current cbc\n", s_irn);
1055 assert(vrfy_ok && "Verification of CBC failed");
1057 /* add the connected bipartite component */
1058 if (ir_nodeset_size(&cbc->parents) > 0 &&
1059 ir_nodeset_size(&cbc->children) > 0 &&
1060 pset_count(cbc->kill_edges) > 0)
1061 pset_insert(rss->cbc_set, cbc, (unsigned)cbc->nr);
1062 DBG((rss->dbg, LEVEL_2, "\tbipartite component %d inserted:\n", cbc->nr));
1064 if (firm_dbg_get_mask(rss->dbg) & LEVEL_2)
1065 debug_print_cbc(rss->dbg, cbc);
1069 if (rss->opts->dump_flags & RSS_DUMP_CBC)
1070 debug_vcg_dump_bipartite(rss);
1076 * Select the child with the maximum cost.
1078 static child_t *select_child_max_cost(rss_t *rss, ir_nodeset_t *x, ir_nodeset_t *y, child_t *t, cbc_t *cbc) {
1080 ir_nodeset_iterator_t iter;
1081 float max_cost = -1.0f;
1083 DBG((rss->dbg, LEVEL_2, "\t\tcomputing children costs:\n"));
1085 foreach_ir_nodeset(&cbc->children, child, iter) {
1086 rss_irn_t *r_child = get_rss_irn(rss, child);
1087 int num_unkilled_parents = 0;
1088 int num_descendants;
1092 /* get the number of unkilled parents */
1093 foreach_pset(cbc->kill_edges, k_edge) {
1094 if (k_edge->tgt == child && ir_nodeset_contains(x, k_edge->src))
1095 ++num_unkilled_parents;
1098 cost = (float)num_unkilled_parents;
1100 num_descendants = plist_count(r_child->descendant_list) + ir_nodeset_size(y);
1102 if (num_descendants > 0)
1103 cost /= (float)num_descendants;
1105 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F, #desc %d, cost %.3f\n", child, num_descendants, cost));
1107 if (cost > max_cost) {
1118 * Remove all parents from x which are killed by t_irn.
1120 static void remove_covered_parents(rss_t *rss, ir_nodeset_t *x, ir_node *t_irn, cbc_t *cbc) {
1121 rss_irn_t *t = get_rss_irn(rss, t_irn);
1124 DBG((rss->dbg, LEVEL_2, "\t\tremoving parents covered by %+F:\n", t_irn));
1126 foreach_pset(cbc->kill_edges, k_edge) {
1127 if (k_edge->tgt == t_irn && ir_nodeset_contains(x, k_edge->src)) {
1128 ir_nodeset_remove(x, k_edge->src);
1129 plist_insert_back(t->parent_list, k_edge->src);
1130 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", k_edge->src));
1135 static void update_cumulated_descendent_values(rss_t *rss, ir_nodeset_t *y, ir_node *t_irn) {
1136 rss_irn_t *t = get_rss_irn(rss, t_irn);
1137 plist_element_t *el;
1139 DBG((rss->dbg, LEVEL_2, "\t\tupdating cumulated descendant value of %+F:\n", t_irn));
1141 foreach_plist(t->descendant_list, el) {
1142 ir_nodeset_insert(y, plist_element_get_value(el));
1143 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", plist_element_get_value(el)));
1148 * Greedy-k: a heuristics for the MMA problem
1150 static void compute_killing_function(rss_t *rss) {
1152 struct obstack obst;
1154 obstack_init(&obst);
1156 rss->cbc_set = pset_new_ptr(5);
1157 compute_bipartite_decomposition(rss);
1159 /* for all bipartite components do: */
1160 foreach_pset(rss->cbc_set, cbc) {
1164 ir_nodeset_iterator_t iter;
1165 child_t **sks = NEW_ARR_F(child_t *, 20);
1170 ir_nodeset_init_size(&x, 10);
1171 ir_nodeset_init_size(&y, 10);
1173 DBG((rss->dbg, LEVEL_1, "\tcomputing SKS for cbc %d:\n", cbc->nr));
1174 DBG((rss->dbg, LEVEL_2, "\t\tinitializing parents X:\n"));
1176 /* X = S_cb (all parents are initially uncovered) */
1177 foreach_ir_nodeset(&cbc->parents, p, iter) {
1178 ir_nodeset_insert(&x, p);
1179 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", p));
1182 /* while X not empty */
1183 while (ir_nodeset_size(&x) > 0) {
1184 child_t *t = obstack_alloc(&obst, sizeof(*t));
1185 memset(t, 0, sizeof(*t));
1187 t = select_child_max_cost(rss, &x, &y, t, cbc);
1189 if (cur_len >= cur_size) {
1190 ARR_EXTO(child_t *, sks, cur_size * 2);
1194 DBG((rss->dbg, LEVEL_2, "\t\tinsert child %+F (%.3f) into SKS at pos %d\n", t->irn, t->cost, cur_len));
1197 remove_covered_parents(rss, &x, t->irn, cbc);
1198 update_cumulated_descendent_values(rss, &y, t->irn);
1201 ARR_SHRINKLEN(sks, cur_len);
1203 /* sort SKS in increasing cost order */
1204 qsort(sks, cur_len, sizeof(sks[0]), cmp_child_costs);
1206 DBG((rss->dbg, LEVEL_2, "\tprocessing SKS for cbc %d:\n", cbc->nr));
1208 /* build killing function */
1209 for (i = cur_len - 1; i >= 0; --i) { /* loop over sks in decreasing cost order */
1210 child_t *t = sks[i];
1211 rss_irn_t *rt = get_rss_irn(rss, t->irn);
1212 plist_element_t *p_el;
1214 DBG((rss->dbg, LEVEL_3, "\t\t\tkiller %+F (%.3f):\n", t->irn, t->cost));
1216 /* kill all unkilled parents of t */
1217 foreach_plist(rt->parent_list, p_el) {
1218 ir_node *par = plist_element_get_value(p_el);
1219 rss_irn_t *rpar = get_rss_irn(rss, par);
1221 if (is_Sink(rpar->killer)) {
1222 rpar->killer = t->irn;
1223 DBG((rss->dbg, LEVEL_2, "\t\tkill %+F\n", rpar->irn));
1226 DBG((rss->dbg, LEVEL_3, "\t\t\tkeeping %+F as killer for %+F\n", rpar->killer, rpar->irn));
1231 ir_nodeset_destroy(&x);
1232 ir_nodeset_destroy(&y);
1236 if (rss->opts->dump_flags & RSS_DUMP_KILL)
1237 debug_vcg_dump_kill(rss);
1239 del_pset(rss->cbc_set);
1240 obstack_free(&obst, NULL);
1244 * Adds the edge src -> tgt to the dvg. Checks if reverse edge is already there (asserts).
1246 static INLINE void add_dvg_edge(rss_t *rss, dvg_t *dvg, ir_node *src, ir_node *tgt, int have_source) {
1247 rss_edge_t *dvg_edge;
1251 ir_nodeset_insert(&dvg->nodes, src);
1253 assert(ir_nodeset_contains(&dvg->nodes, src) && "Wrong assumption");
1255 ir_nodeset_insert(&dvg->nodes, tgt);
1259 assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
1263 if (NULL != pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
1264 /* add the edge to the DVG */
1265 dvg_edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*dvg_edge));
1267 dvg_edge->src = src;
1268 dvg_edge->tgt = tgt;
1269 dvg_edge->next = NULL;
1271 DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", src, tgt));
1272 pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
1277 * Computes the disjoint value DAG (DVG).
1278 * BEWARE: It is not made explicitly clear in the Touati paper,
1279 * but the DVG is meant to be build from the KILLING DAG
1281 static void compute_dvg(rss_t *rss, dvg_t *dvg) {
1282 plist_element_t *el;
1284 DBG((rss->dbg, LEVEL_1, "\tcomputing DVG:\n"));
1286 foreach_plist(rss->nodes, el) {
1287 ir_node *u_irn = plist_element_get_value(el);
1288 rss_irn_t *u = get_rss_irn(rss, u_irn);
1289 rss_irn_t *u_killer = get_rss_irn(rss, u->killer);
1292 /* TODO: omit nodes only having sink as pkiller and killing no one */
1294 /* add an edge to killer */
1295 add_dvg_edge(rss, dvg, u_irn, u->killer, 0);
1297 if (is_Sink(u->killer))
1300 /* We add an edge to every killer, from where we could be reached. */
1301 for (i = ARR_LEN_SAFE(u_killer->descendants) - 1; i >= 0; --i) {
1302 add_dvg_edge(rss, dvg, u_irn, u_killer->descendants[i], 1);
1307 foreach_plist(rss->nodes, el2) {
1308 ir_node *v_irn = plist_element_get_value(el2);
1311 There is an edge (u, v) in the DVG iff v is a descendant of the killer(u).
1313 if (BSEARCH_IRN_ARR(v_irn, u_kill->descendants)) {
1314 rss_edge_t *dvg_edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*dvg_edge));
1317 /* insert the user into the DVG and append it to the user list of u */
1318 ir_nodeset_insert(&dvg->nodes, v_irn);
1319 if (! plist_has_value(u->dvg_user_list, v_irn))
1320 plist_insert_back(u->dvg_user_list, v_irn);
1322 dvg_edge->src = u_irn;
1323 dvg_edge->tgt = v_irn;
1324 dvg_edge->next = NULL;
1329 assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
1331 /* add the edge to the DVG */
1332 DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", u_irn, v_irn));
1333 pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
1339 if (rss->opts->dump_flags & RSS_DUMP_DVG)
1340 debug_vcg_dump_dvg(rss, dvg);
1344 * Updates the dvg structure when a serialization edge from src -> tgt is added.
1346 static void update_dvg(rss_t *rss, dvg_t *dvg, rss_irn_t *src, rss_irn_t *tgt) {
1349 rss_edge_t **arr = alloca(pset_count(dvg->edges) * sizeof(arr[0]));
1352 Add an edge from serialization target to serialization src:
1353 src cannot be alive with target
1355 add_dvg_edge(rss, dvg, tgt->irn, src->irn, 0);
1357 /* Add edges to src's descendants as well, they also getting serialized. */
1358 for (i = ARR_LEN_SAFE(src->descendants) - 1; i >= 0; --i) {
1359 add_dvg_edge(rss, dvg, tgt->irn, src->descendants[i], 1);
1362 /* We also have to add edges from targets predecessors in dvg */
1364 /* We cannot insert elements into set over which we iterate ... */
1365 foreach_pset(dvg->edges, edge) {
1366 if (edge->tgt == tgt->irn) {
1371 for (i = 0; i < idx; ++i) {
1373 add_dvg_edge(rss, dvg, edge->src, src->irn, 1);
1374 for (j = ARR_LEN_SAFE(src->descendants) - 1; j >= 0; --j) {
1375 add_dvg_edge(rss, dvg, edge->src, src->descendants[j], 1);
1382 * Accumulate all descendants for root into list.
1384 static void accumulate_dvg_descendant_values(rss_t *rss, rss_irn_t *root, plist_t *list) {
1385 if (plist_count(root->dvg_user_list) > 0) {
1386 plist_element_t *el;
1388 foreach_plist(root->dvg_user_list, el) {
1389 ir_node *v_irn = plist_element_get_value(el);
1390 rss_irn_t *v = get_rss_irn(rss, v_irn);
1392 /* add v as descendant */
1393 if (! plist_has_value(list, v_irn)) {
1394 plist_insert_back(list, v_irn);
1395 DBG((rss->dbg, DEBUG_DVG, "\t\t\tadd DVG descendant %+F\n", v_irn));
1398 /* accumulate v's descendants */
1399 accumulate_dvg_descendant_values(rss, v, list);
1405 * Builds the list of potential killers for each node
1407 * Needs the descendant list for all user as sorted array.
1409 static void build_dvg_pkiller_list(rss_t *rss, dvg_t *dvg) {
1410 ir_nodeset_iterator_t iter;
1413 foreach_nodeset(&dvg->nodes, irn, iter) {
1414 rss_irn_t *node = get_rss_irn(rss, irn);
1415 plist_element_t *el, *el2;
1417 DBG((rss->dbg, DEBUG_DVG, "\t\tbuilding pkiller list for %+F\n", irn));
1419 /* check each user */
1420 foreach_plist(node->dvg_user_list, el) {
1421 ir_node *u_irn = plist_element_get_value(el);
1423 /* is the current user u_irn not a descendant of any other user -> pkiller */
1424 foreach_plist(node->dvg_user_list, el2) {
1425 ir_node *v_irn = plist_element_get_value(el2);
1426 rss_irn_t *v = get_rss_irn(rss, v_irn);
1429 ! BSEARCH_IRN_ARR(u_irn, v->dvg_desc) &&
1430 ! plist_has_value(node->dvg_pkiller_list, u_irn))
1432 plist_insert_back(node->dvg_pkiller_list, u_irn);
1433 DBG((rss->dbg, DEBUG_DVG, "\t\t\tadd DVG pkiller %+F\n", u_irn));
1438 node->dvg_pkiller = build_sorted_array_from_list(node->dvg_pkiller_list, phase_obst(&rss->ph));
1442 if (firm_dbg_get_mask(rss->dbg) & DEBUG_DVG)
1443 debug_vcg_dump_dvg_pkiller(rss, dvg);
1450 * Compute the maximal antichain of the current DVG.
1451 * This is a reimplementation of the MAXIMAL_ANTI_CHAIN function
1452 * from the DDG library 1.1 (DAG.cpp).
1454 static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration) {
1455 int n = ir_nodeset_size(&dvg->nodes);
1456 int *assignment = alloca(n * sizeof(assignment[0]));
1457 int *assignment_rev = alloca(n * sizeof(assignment_rev[0]));
1458 int *idx_map = alloca(n * sizeof(idx_map[0]));
1459 hungarian_problem_t *bp;
1460 ir_nodeset_t *values, *temp;
1461 ir_nodeset_iterator_t iter;
1463 int i, j, cost, cur_chain, res;
1464 rss_edge_t *dvg_edge;
1466 #define MAP_IDX(irn) bsearch_for_index(get_irn_idx(irn), idx_map, n, 1)
1468 if (pset_count(dvg->edges) == 0)
1471 bp = hungarian_new(n, n, 1, HUNGARIAN_MATCH_NORMAL);
1474 At first, we build an index map for the nodes in the DVG,
1475 because we cannot use the irn idx therefore as the resulting
1476 bipartite data structure would have around 1.2GB.
1477 So we limit the size to the number of nodes we have in the DVG
1478 and build a sorted index map for their irn indices.
1481 foreach_ir_nodeset(&dvg->nodes, u_irn, iter) {
1482 idx_map[i++] = get_irn_idx(u_irn);
1484 qsort(idx_map, n, sizeof(idx_map[0]), cmp_int);
1486 foreach_pset(dvg->edges, dvg_edge) {
1487 int idx_u = MAP_IDX(dvg_edge->src);
1488 int idx_v = MAP_IDX(dvg_edge->tgt);
1490 /* add the entry to the bipartite data structure */
1491 hungarian_add(bp, idx_u, idx_v, 1);
1492 DBG((rss->dbg, LEVEL_3, "\t\t\tadd %d (%+F) -> %d (%+F)\n",
1493 idx_u, dvg_edge->src, idx_v, dvg_edge->tgt));
1497 Add a bipartite entry for each pair of nodes (u, v), where exists a
1498 path in the DVG from u to v, ie. connect all descendants(v) to v.
1499 desc_dvg(v) = accumulated descendants of all z in dvg_user_list(v)
1501 foreach_ir_nodeset(&dvg->nodes, u_irn, iter) {
1502 rss_irn_t *u = get_rss_irn(rss, u_irn);
1503 int idx_u_irn = MAP_IDX(u_irn);
1505 DBG((rss->dbg, DEBUG_DVG, "\t\tcomputing DVG descendants of %+F:\n", u_irn));
1507 //plist_clear(u->dvg_desc_list);
1508 //accumulate_dvg_descendant_values(rss, u, u->dvg_desc_list);
1511 FIXME: The array is build on the phase obstack and we cannot free the data.
1512 So the array get as many times allocated as this function is called.
1515 /* build the sorted array for faster searches */
1516 //u->dvg_desc = build_sorted_array_from_list(u->dvg_desc_list, phase_obst(&rss->ph));
1518 DBG((rss->dbg, DEBUG_MAX_AC, "\t\tadding bipartite entries of %+F:\n", u_irn));
1520 /* add the bipartite entries for all descendants */
1521 for (i = ARR_LEN_SAFE(u->dvg_desc) - 1; i >= 0; --i) {
1522 rss_irn_t *desc = get_rss_irn(rss, u->dvg_desc[i]);
1523 int idx_desc = MAP_IDX(u->dvg_desc[i]);
1525 /* add the entry to the bipartite data structure */
1526 hungarian_add(bp, idx_u_irn, idx_desc, 1);
1527 DBG((rss->dbg, DEBUG_MAX_AC, "\t\t\tadd %d (%+F) -> %d (%+F)\n",
1528 idx_u_irn, u_irn, idx_desc, u->dvg_desc[i]));
1535 /* We want maximum cardinality matching */
1536 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
1539 DBG((rss->dbg, DEBUG_DVG, "\t\tcomputing DVG pkiller:\n"));
1540 /* beware: the following function needs the dvg_desc array */
1541 build_dvg_pkiller_list(rss, dvg);
1544 DBG((rss->dbg, LEVEL_2, "\t\tcomputing bipartite matching\n"));
1546 The maximum cardinality bipartite matching gives us the minimal
1547 chain partition, which corresponds to the maximum anti chains.
1549 res = hungarian_solve(bp, assignment, &cost, 1);
1550 assert(res == 0 && "Bipartite matching failed!");
1553 memset(assignment_rev, -1, n * sizeof(assignment_rev[0]));
1555 /* build the reverse assignment, ie. foreach i -> j, add j -> i */
1556 for (i = 0; i < n; ++i) {
1557 if (assignment[i] >= 0) {
1558 int j = assignment[i];
1559 assignment_rev[j] = i;
1563 DBG((rss->dbg, LEVEL_2, "\t\tgot assignment with cost %d\n", cost));
1564 DBG((rss->dbg, LEVEL_3, "\t\t\tassignment --- reverse assignment\n", cost));
1565 for (i = 0; i < n; ++i) {
1566 DBG((rss->dbg, LEVEL_3, "\t\t\t%3d -> %3d %3d -> %3d\n", i, assignment[i], i, assignment_rev[i]));
1569 values = xmalloc(sizeof(values[0]));
1570 ir_nodeset_init_size(values, 10);
1572 /* Construction of the minimal chain partition */
1573 for (j = 0; j < n; ++j) {
1574 /* check nodes, which did not occur as target */
1575 if (assignment_rev[j] == -1) {
1576 int xj = idx_map[j];
1577 ir_node *xj_irn = get_idx_irn(rss->irg, xj);
1578 rss_irn_t *xj_rss = get_rss_irn(rss, xj_irn);
1579 chain_t *c = obstack_alloc(phase_obst(&rss->ph), sizeof(*c));
1582 /* there was no source for j -> we have a source of a new chain */
1583 ir_nodeset_insert(values, xj_irn);
1585 c->elements = plist_obstack_new(phase_obst(&rss->ph));
1586 c->nr = cur_chain++;
1587 plist_insert_back(c->elements, xj_irn);
1591 DBG((rss->dbg, LEVEL_2, "\t\tstarting chain %d:\n", c->nr));
1592 DBG((rss->dbg, LEVEL_2, "\t\t\t%+F (%d)", xj_irn, j));
1594 /* follow chain, having j as source */
1596 while (assignment[source] >= 0) {
1597 int target = assignment[source];
1598 int irn_idx = idx_map[target];
1599 ir_node *irn = get_idx_irn(rss->irg, irn_idx);
1600 rss_irn_t *node = get_rss_irn(rss, irn);
1602 plist_insert_back(c->elements, irn);
1605 DB((rss->dbg, LEVEL_2, " -> %+F (%d)", irn, target));
1607 /* new source = last target */
1611 DB((rss->dbg, LEVEL_2, "\n"));
1616 Computing the maximal antichain: Select an element from each
1617 chain such, such it is parallel with the others.
1619 DBG((rss->dbg, LEVEL_1, "\t\tcomputing set of saturation values (MAX AC)\n"));
1620 DBG((rss->dbg, LEVEL_3, "\t\tstarting with:\n"));
1623 if (firm_dbg_get_mask(rss->dbg) & LEVEL_3)
1624 dump_nodeset(values, "\t\t\t");
1630 We need an explicit array for the values as
1631 we cannot iterate multiple times over the same
1632 set at the same time. :-(((((
1633 TODO Matze: now we can, so rewrite this...
1635 int n = ir_nodeset_size(values);
1637 ir_node **val_arr = NEW_ARR_F(ir_node *, n);
1639 foreach_ir_nodeset(values, u_irn, iter)
1640 val_arr[i++] = u_irn;
1643 ir_nodeset_destroy(temp);
1647 temp = xmalloc(sizeof(temp[0]));
1648 ir_nodeset_init_size(temp, 10);
1650 /* Select all nodes from current value set, having another node in the set as descendant. */
1651 for (i = 0; i < n; ++i) {
1652 rss_irn_t *u = get_rss_irn(rss, val_arr[i]);
1654 for (j = 0; j < n; ++j) {
1658 key.src = val_arr[i];
1659 key.tgt = val_arr[j];
1661 if (pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
1662 /* v[j] is descendant of u -> remove u and break */
1663 ir_nodeset_insert(temp, u->irn);
1664 ir_nodeset_remove(values, u->irn);
1666 DBG((rss->dbg, LEVEL_3, "\t\t\tremoving %+F from values, adding it to temp\n", u->irn));
1674 /* Try to insert the chain predecessor of all selected u's */
1675 foreach_ir_nodeset(temp, u_irn, iter) {
1676 rss_irn_t *u = get_rss_irn(rss, u_irn);
1677 chain_t *c = u->chain;
1678 plist_element_t *el = plist_find_value(c->elements, u_irn);
1680 assert(el && "Missing element in chain!");
1682 /* If u has predecessor in chain: insert the predecessor */
1683 if (el == plist_element_get_prev(el)) {
1684 ir_nodeset_insert(values, plist_element_get_value(el));
1685 DBG((rss->dbg, LEVEL_3, "\t\t\tadding %+F to values\n", plist_element_get_value(el)));
1691 } while (ir_nodeset_size(temp) > 0);
1693 DBG((rss->dbg, LEVEL_2, "\t\tfinal set:\n"));
1695 if (firm_dbg_get_mask(rss->dbg) & LEVEL_2) {
1696 dump_nodeset(values, "\t\t\t");
1700 if (rss->opts->dump_flags & RSS_DUMP_MAXAC)
1701 debug_vcg_dump_pkg(rss, values, iteration);
1704 ir_nodeset_destroy(temp);
1714 * Computes the best serialization between two nodes of sat_vals.
1716 static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nodeset_t *sat_vals, serialization_t *ser, int num_regs) {
1717 int n = ir_nodeset_size(sat_vals);
1718 int n_idx = ARR_LEN_SAFE(rss->idx_map);
1720 ir_node **val_arr = alloca(n * sizeof(val_arr[0]));
1721 bitset_t *bs_sv = bitset_alloca(n_idx);
1722 bitset_t *bs_vdesc = bitset_alloca(n_idx);
1723 bitset_t *bs_tmp = bitset_alloca(n_idx);
1724 bitset_t *bs_ukilldesc = bitset_alloca(n_idx);
1725 int best_benefit = INT_MAX;
1726 int best_omega2 = INT_MAX;
1727 int best_benefit_omega20 = INT_MAX;
1731 ir_nodeset_iterator_t iter;
1732 rss_edge_t min_benefit_edge;
1733 rss_edge_t min_omega20_edge;
1734 rss_irn_t *ser_u_omega1 = NULL, *ser_v_omega1 = NULL;
1735 rss_irn_t *ser_u_omega20 = NULL, *ser_v_omega20 = NULL;
1737 DBG((rss->dbg, LEVEL_1, "\tcomputing admissible serializations:\n"));
1740 We need an explicit array for the values as
1741 we cannot iterate multiple times over the same
1742 set at the same time. :-(((((
1745 foreach_ir_nodeset(sat_vals, irn, iter) {
1747 bitset_set(bs_sv, BLOCK_IDX_MAP(rss, irn));
1751 We build all admissible serializations and remember the best found so far.
1754 if v in pkiller(u): add edge from v to all other pkiller(u)
1755 else: for all vv in pkiller(u): add edge from v to vv if there exists no path from vv to v
1759 A node is unserializable if:
1760 - it has only one killer and this one is Sink
1761 - it kills no other values
1762 In this case there is no serialization which could
1763 reduce the registerpressure
1765 #define IS_UNSERIALIZABLE_NODE(rss_node) \
1768 (plist_count(rss_node->pkiller_list) == 1) && \
1769 is_Sink(rss_node->killer) && \
1770 (rss_node->kill_count == 0) \
1772 be_is_Barrier(rss_node->irn) || \
1773 be_is_Keep(rss_node->irn) \
1776 /* for all u in sat_vals */
1777 for (i = 0; i < n; ++i) {
1778 rss_irn_t *u = get_rss_irn(rss, val_arr[i]);
1779 plist_element_t *el;
1781 /* ignore nodes where serialization does not help */
1782 if (IS_UNSERIALIZABLE_NODE(u)) {
1783 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", u->irn));
1787 /* accumulate all descendants of all pkiller(u) */
1788 bitset_clear_all(bs_ukilldesc);
1789 foreach_plist(u->pkiller_list, el) {
1790 ir_node *irn = plist_element_get_value(el);
1791 rss_irn_t *node = get_rss_irn(rss, irn);
1794 bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, irn));
1798 for (k = ARR_LEN_SAFE(node->descendants) - 1; k >= 0; --k) {
1799 if (! is_Sink(node->descendants[k]))
1800 bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, node->descendants[k]));
1804 /* for all v in sat_vals */
1805 for (j = 0; j < n; ++j) {
1806 ir_node *v_irn = val_arr[j];
1807 rss_irn_t *v = get_rss_irn(rss, v_irn);
1808 unsigned v_height = get_irn_height(rss->h, v_irn);
1809 int omega1, omega2, is_pkiller;
1811 /* v cannot be serialized with itself
1812 * ignore nodes where serialization does not help */
1813 if (i == j || IS_UNSERIALIZABLE_NODE(v)) {
1815 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", v->irn));
1819 /* get descendants of v */
1820 bitset_clear_all(bs_vdesc);
1821 bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v_irn));
1822 for (k = ARR_LEN_SAFE(v->descendants) - 1; k >= 0; --k) {
1823 if (! is_Sink(v->descendants[k]))
1824 bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v->descendants[k]));
1827 /* if v is in pkiller(u) */
1828 is_pkiller = plist_has_value(u->pkiller_list, v_irn);
1830 /* for all vv in pkiller(u) */
1831 foreach_plist(u->pkiller_list, el) {
1832 ir_node *vv_irn = plist_element_get_value(el);
1835 if (is_Sink(vv_irn) || is_cfop(vv_irn))
1839 add_edge = vv_irn != v_irn && skip_Proj(vv_irn) != skip_Proj(v_irn);
1841 add_edge = ! heights_reachable_in_block(rss->h, skip_Proj(vv_irn), skip_Proj(v_irn));
1844 As we add an edge from vv -> v, we have to make sure,
1845 that there exists no path from v to vv.
1849 unsigned vv_height = get_irn_height(rss->h, vv_irn);
1850 unsigned critical_path_cost;
1854 mu1 = | descendants(v) cut sat_vals |
1855 the number of saturating values which cannot
1856 be simultaneously alive with u
1858 bitset_copy(bs_tmp, bs_vdesc);
1859 mu1 = bitset_popcnt(bitset_and(bs_tmp, bs_sv));
1862 mu2 = | accum_desc_all_pkiller(u) without descendants(v) |
1865 bitset_copy(bs_tmp, bs_ukilldesc);
1866 mu2 = bitset_popcnt(bitset_andnot(bs_tmp, bs_vdesc));
1872 /* omega1 = mu1 - mu2 */
1878 /* omega2 = increase of critical path */
1879 critical_path_cost =
1880 v_height /* longest path from v to sink */
1881 + rss->max_height - vv_height /* longest path from source to vv */
1885 If critical_path_cost > max_height -> the new edge
1886 would increase the longest critical path by the difference.
1888 omega2 = critical_path_cost > rss->max_height ? critical_path_cost - rss->max_height : 0;
1890 /* this keeps track of the edge with the best benefit */
1891 if (omega1 >= num_regs - n && omega1 < best_benefit) {
1892 min_benefit_edge.src = v_irn;
1893 min_benefit_edge.tgt = vv_irn;
1898 best_benefit = omega1;
1899 ser->new_killer = is_pkiller;
1902 /* this keeps track of the edge with the best omega1 costs where omega2 == 0 */
1903 if (omega2 == 0 && omega1 >= num_regs - n && omega1 < best_benefit_omega20) {
1904 min_omega20_edge.src = v_irn;
1905 min_omega20_edge.tgt = vv_irn;
1910 best_benefit_omega20 = omega1;
1911 ser->new_killer = is_pkiller;
1914 best_omega2 = MIN(best_omega2, omega2);
1916 DBG((rss->dbg, LEVEL_2, "\t\tfound %+F -> %+F (w1 %d, w2 %d)\n",
1917 v_irn, vv_irn, omega1, omega2));
1919 } /* for all vv in pkiller(u) */
1920 } /* for all v in sat_vals */
1921 } /* for all u in sat_vals */
1926 if (best_omega2 == 0) {
1927 ser->u = ser_u_omega20;
1928 ser->v = ser_v_omega20;
1929 ser->edge->src = min_omega20_edge.src;
1930 ser->edge->tgt = min_omega20_edge.tgt;
1931 ser->omega1 = best_benefit_omega20;
1932 ser->omega2 = best_omega2;
1935 ser->u = ser_u_omega1;
1936 ser->v = ser_v_omega1;
1937 ser->edge->src = min_benefit_edge.src;
1938 ser->edge->tgt = min_benefit_edge.tgt;
1939 ser->omega1 = best_benefit;
1940 ser->omega2 = best_omega2;
1945 #undef IS_UNSERIALIZABLE_NODE
1949 * Perform the value serialization heuristic and add all
1950 * computed serialization edges as dependencies to the irg.
1952 static void perform_value_serialization_heuristic(rss_t *rss) {
1953 bitset_t *arch_nonign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls));
1954 bitset_t *abi_ign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls));
1955 unsigned available_regs, iteration;
1957 ir_nodeset_t *sat_vals;
1958 pset *ser_set = new_pset(cmp_rss_edges, 20);
1960 /* available_regs = R = |arch_non_ignore_regs cut ~abi_ignore_regs| */
1961 arch_put_non_ignore_regs(rss->arch_env, rss->cls, arch_nonign_bs);
1962 be_abi_put_ignore_regs(rss->abi, rss->cls, abi_ign_bs);
1963 bitset_andnot(arch_nonign_bs, abi_ign_bs);
1964 available_regs = bitset_popcnt(arch_nonign_bs);
1965 //num_live = pset_count(rss->live_block);
1966 //available_regs -= num_live < available_regs ? num_live : 0;
1968 DBG((rss->dbg, LEVEL_1, "\n\t#available regs: %d\n\n", available_regs));
1971 At first we need to compute the disjoint value DAG (DVG = {V, E_dv}).
1972 V = set of all nodes we are currently interested in
1973 E_dv = there is an edge from u to v iff v is a descendant of killer(u), forall u, v in V
1975 ir_nodeset_init_size(&dvg.nodes, plist_count(rss->nodes));
1976 dvg.edges = new_pset(cmp_rss_edges, plist_count(rss->nodes) * 5);
1977 compute_dvg(rss, &dvg);
1980 Then we perform the heuristic serialization algorithm
1981 on the DVG which gives us all necessary serialization
1984 DBG((rss->dbg, LEVEL_1, "\tcomputing maximal antichain:\n"));
1986 sat_vals = compute_maximal_antichain(rss, &dvg, iteration++);
1987 while (sat_vals && (ir_nodeset_size(sat_vals) > available_regs)) {
1988 serialization_t *ser, best_ser;
1989 rss_edge_t *edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*edge));
1990 ir_node *dep_src, *dep_tgt;
1992 best_ser.edge = edge;
1993 ser = compute_best_admissible_serialization(rss, sat_vals, &best_ser, available_regs);
1995 DBG((rss->dbg, LEVEL_1, "\tcurrent register saturation %d, target %d\n", ir_nodeset_size(sat_vals), available_regs));
1998 DBG((rss->dbg, LEVEL_1, "\tno RS improving serialization found, breaking at iteration %d\n", iteration));
2002 /* Insert the serialization as dependency edge into the irg. */
2003 DBG((rss->dbg, LEVEL_1, "\tserializing %+F -> %+F with edge %+F -> %+F and cost %d, %d\n",
2004 ser->u->irn, ser->v->irn, ser->edge->src, ser->edge->tgt, ser->omega1, ser->omega2));
2006 if (pset_find(ser_set, ser->edge, HASH_RSS_EDGE(ser->edge)))
2007 ir_printf("WARNING: serialization %+F -> %+F computed twice!\n", ser->edge->src, ser->edge->tgt);
2010 pset_insert(ser_set, ser->edge, HASH_RSS_EDGE(ser->edge));
2012 /* update the dvg */
2013 update_dvg(rss, &dvg, ser->v, ser->u);
2014 update_dvg(rss, &dvg, get_rss_irn(rss, ser->edge->src), get_rss_irn(rss, ser->edge->tgt));
2015 if(sat_vals != NULL) {
2016 ir_nodeset_destroy(sat_vals);
2020 dep_src = skip_Proj(ser->edge->src);
2021 dep_tgt = ser->edge->tgt;
2022 add_irn_dep(dep_src, dep_tgt);
2024 /* Update descendants, consumer and pkillers of the target */
2025 update_node_info(rss, ser->edge->tgt, ser->edge->src);
2027 /* TODO: try to find a cheaper way for updating height information */
2028 rss->max_height = heights_recompute_block(rss->h, rss->block);
2030 /* Recompute the antichain for next serialization */
2031 DBG((rss->dbg, LEVEL_1, "\tre-computing maximal antichain:\n"));
2032 sat_vals = compute_maximal_antichain(rss, &dvg, iteration++);
2035 ir_nodeset_destroy(&dvg.nodes);
2036 del_pset(dvg.edges);
2040 * Do initial calculations for a block.
2042 static void process_block(ir_node *block, void *env) {
2045 const ir_edge_t *edge;
2047 phase_init(&rss->ph, "rss block preprocessor", rss->irg, PHASE_DEFAULT_GROWTH, init_rss_irn, NULL);
2049 DBG((rss->dbg, LEVEL_1, "preprocessing block %+F\n", block));
2052 /* build an index map for all nodes in the current block */
2054 n = get_irn_n_edges(block);
2055 NEW_ARR_A(int *, rss->idx_map, n);
2056 foreach_out_edge(block, edge) {
2057 ir_node *irn = get_edge_src_irn(edge);
2058 rss->idx_map[i++] = get_irn_idx(irn);
2060 qsort(rss->idx_map, n, sizeof(rss->idx_map[0]), cmp_int);
2061 rss->max_height = heights_recompute_block(rss->h, block);
2063 /* loop over all register classes */
2064 for (i = arch_isa_get_n_reg_class(rss->arch_env->isa) - 1; i >= 0; --i) {
2065 const arch_register_class_t *cls = arch_isa_get_reg_class(rss->arch_env->isa, i);
2068 DBG((rss->dbg, LEVEL_1, "register class %s\n", arch_register_class_name(cls)));
2070 /* Get all live value at end of Block having current register class */
2071 ir_nodeset_init(&rss->live_block);
2072 be_liveness_end_of_block(rss->liveness, rss->arch_env, rss->cls, rss->block, &rss->live_block);
2074 /* reset the list of interesting nodes */
2075 plist_clear(rss->nodes);
2076 plist_insert_back(rss->nodes, _sink);
2078 /* collect all nodes having a certain register class */
2079 foreach_out_edge(block, edge) {
2080 ir_node *irn = get_edge_src_irn(edge);
2081 ir_mode *mode = get_irn_mode(irn);
2085 - mode_T nodes (the projs are asked)
2086 - mode_X nodes (control flow nodes are always scheduled last)
2087 - Keeps (they are always immediately scheduled)
2088 - Phi (same as Keep)
2090 if (mode == mode_T || mode == mode_X || is_Phi(irn))
2094 In case of a proj, we skip
2095 - Barrier (they are a Barrier :)
2097 - the Proj itself, as it's scheduled always with it's super node
2100 ir_node *pred = get_Proj_pred(irn);
2101 if (be_is_Barrier(pred) || is_Start(pred))
2105 /* calculate the descendants and consumer for each node in the block */
2106 collect_node_info(rss, skip_Proj(irn));
2108 if (be_is_Keep(irn))
2111 if (! arch_irn_is(rss->arch_env, irn, ignore) && arch_get_irn_reg_class(rss->arch_env, irn, -1) == cls) {
2112 plist_insert_back(rss->nodes, skip_Proj(irn));
2117 /* compute the potential killing set PK(G) */
2118 compute_pkill_set(rss);
2120 /* compute the killing function k* */
2121 compute_killing_function(rss);
2124 Compute the heuristic value serialization and
2125 add the necessary dependencies to the irg.
2127 perform_value_serialization_heuristic(rss);
2129 ir_nodeset_destroy(&rss->live_block);
2132 phase_free(&rss->ph);
2136 * Register the options.
2138 void be_init_schedrss(void) {
2139 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
2140 lc_opt_entry_t *sched_grp = lc_opt_get_grp(be_grp, "sched");
2141 lc_opt_entry_t *rss_grp = lc_opt_get_grp(sched_grp, "rss");
2143 lc_opt_add_table(rss_grp, rss_option_table);
2146 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_schedrss);
2149 * Preprocess the irg for scheduling.
2151 void rss_schedule_preparation(be_irg_t *birg) {
2152 ir_graph *irg = be_get_birg_irg(birg);
2155 FIRM_DBG_REGISTER(rss.dbg, "firm.be.sched.rss");
2157 //firm_dbg_set_mask(rss.dbg, LEVEL_1 | LEVEL_2 | LEVEL_3);
2159 init_rss_special_nodes(irg);
2162 rss.arch_env = be_get_birg_arch_env(birg);
2163 rss.abi = birg->abi;
2164 rss.h = heights_new(irg);
2165 rss.nodes = plist_new();
2166 rss.opts = &rss_options;
2167 rss.liveness = be_liveness(birg);
2168 be_liveness_assure_sets(rss.liveness);
2169 irg_block_walk_graph(irg, NULL, process_block, &rss);
2170 heights_free(rss.h);
2171 plist_free(rss.nodes);
2172 be_liveness_free(rss.liveness);
2174 if (birg->main_env->options->dump_flags & DUMP_SCHED)
2175 be_dump(rss.irg, "-rss", dump_ir_block_graph);