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 pset *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) {
777 assert(is_Sink(v->irn) || ((plist_count(v->descendant_list) > 0 && v->descendants) || 1));
778 assert(is_Sink(u->irn) || ((plist_count(u->consumer_list) > 0 && u->consumer) || 1));
780 /* as we loop over the list: loop over the shorter one */
781 if (plist_count(v->descendant_list) > plist_count(u->consumer_list)) {
782 list = u->consumer_list;
783 arr = v->descendants;
786 list = v->descendant_list;
790 /* for each list element: try to find element in array */
791 foreach_plist(list, el) {
792 ir_node *irn = plist_element_get_value(el);
793 ir_node *match = BSEARCH_IRN_ARR(irn, arr);
795 if (match && match != irn)
803 * Update descendants, consumer and pkiller list for the given irn.
805 static void update_node_info(rss_t *rss, ir_node *irn, ir_node *pk_irn) {
806 rss_irn_t *node = get_rss_irn(rss, irn);
807 rss_irn_t *pkiller = get_rss_irn(rss, pk_irn);
809 /* add consumer and rebuild the consumer array */
810 if (! plist_has_value(node->consumer_list, pk_irn)) {
811 plist_insert_back(node->consumer_list, pk_irn);
812 node->consumer = build_sorted_array_from_list(node->consumer_list, phase_obst(&rss->ph));
815 /* add pk_irn as descendant, add it's descendants to irn's and rebuild array */
816 if (! plist_has_value(node->descendant_list, pk_irn)) {
819 plist_insert_back(node->descendant_list, pk_irn);
821 foreach_plist(pkiller->descendant_list, el) {
822 ir_node *desc = plist_element_get_value(el);
824 if (! plist_has_value(node->descendant_list, desc))
825 plist_insert_back(node->descendant_list, desc);
828 node->descendants = build_sorted_array_from_list(node->descendant_list, phase_obst(&rss->ph));
834 * Compute the potential killing set PK.
836 static void compute_pkill_set(rss_t *rss) {
837 plist_element_t *u_el, *v_el;
839 foreach_plist(rss->nodes, u_el) {
840 ir_node *u_irn = plist_element_get_value(u_el);
841 rss_irn_t *u = get_rss_irn(rss, u_irn);
843 DBG((rss->dbg, LEVEL_1, "\tcomputing potential killers of %+F:\n", u_irn));
845 /* check each consumer if it is a potential killer */
846 foreach_plist(u->consumer_list, v_el) {
847 ir_node *v_irn = plist_element_get_value(v_el);
848 rss_irn_t *v = get_rss_irn(rss, v_irn);
850 /* check, if v is a potential killer of u */
851 if (is_potential_killer(rss, v, u)) {
852 if (! plist_has_value(u->pkiller_list, v_irn))
853 plist_insert_back(u->pkiller_list, v_irn);
855 DBG((rss->dbg, LEVEL_2, "\t\tpotential killer %+F\n", v_irn));
862 if (rss->opts->dump_flags & RSS_DUMP_PKG)
863 debug_vcg_dump_pkg(rss, NULL, 0);
867 * Build set of killing edges (from values to their potential killers)
869 static void build_kill_edges(rss_t *rss, pset *epk) {
870 plist_element_t *el, *k_el;
872 foreach_plist(rss->nodes, el) {
873 ir_node *irn = plist_element_get_value(el);
874 rss_irn_t *rirn = get_rss_irn(rss, irn);
876 DBG((rss->dbg, LEVEL_3, "\t\tbuilding kill edges for %+F:\n", irn));
878 foreach_plist(rirn->pkiller_list, k_el) {
879 ir_node *pkiller = plist_element_get_value(k_el);
880 rss_edge_t *ke = obstack_alloc(phase_obst(&rss->ph), sizeof(*ke));
886 DBG((rss->dbg, LEVEL_3, "\t\t\ttarget %+F\n", pkiller));
888 pset_insert(epk, ke, HASH_RSS_EDGE(ke));
894 /* print the given cbc for debugging purpose */
895 static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc) {
896 ir_nodeset_iterator_t iter;
900 DBG((mod, LEVEL_3, "\t\tS = set of parents:\n"));
901 foreach_ir_nodeset(&cbc->parents, n, iter) {
902 DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
904 DBG((mod, LEVEL_3, "\t\tT = set of children:\n"));
905 foreach_ir_nodeset(&cbc->children, n, iter) {
906 DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
908 DBG((mod, LEVEL_3, "\t\tE = Edges from producers to consumers\n"));
909 foreach_pset(cbc->kill_edges, ke) {
910 DBG((mod, LEVEL_3, "\t\t\t%+F -> %+F\n", ke->src, ke->tgt));
916 * Construct the bipartite decomposition.
917 * Sid-Ahmed-Ali Touati, Phd Thesis
918 * Register Pressure in Instruction Level Parallelism, p. 71
920 static void compute_bipartite_decomposition(rss_t *rss) {
921 pset *epk = new_pset(cmp_rss_edges, 10);
926 DBG((rss->dbg, LEVEL_1, "\tcomputing bipartite decomposition:\n"));
928 build_kill_edges(rss, epk);
930 foreach_plist(rss->nodes, el) {
931 ir_node *u_irn = plist_element_get_value(el);
932 rss_irn_t *u = get_rss_irn(rss, u_irn);
938 plist_element_t *el2;
940 rss_edge_t *kedge_root = NULL;
941 ir_node *t_irn, *s_irn;
942 ir_nodeset_iterator_t iter;
944 if (u->visited || u_irn == _sink)
947 DBG((rss->dbg, LEVEL_2, "\t\t%+F choosen:\n", u_irn));
949 cbc = obstack_alloc(phase_obst(&rss->ph), sizeof(*cbc));
952 /* initialize S_cb */
953 ir_nodeset_init_size(&cbc->parents, 5);
954 ir_nodeset_insert(&cbc->parents, u_irn);
955 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (init)\n", u_irn));
958 cbc->kill_edges = new_pset(cmp_rss_edges, 5);
960 /* each parent gets killed by at least one value from children */
962 /* T_cb = PK_successors(u) */
963 ir_nodeset_init_size(&cbc->children, 5);
964 foreach_plist(u->pkiller_list, el2) {
965 ir_nodeset_insert(&cbc->children, plist_element_get_value(el2));
966 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (init)\n", plist_element_get_value(el2)));
970 Now: insert the parents of all children into the parent set
971 and insert the children of all parents into the children set
972 until the sets don't change any more
974 while (p_change || c_change) {
975 ir_nodeset_iterator_t iter;
976 p_change = c_change = 0;
978 /* accumulate parents */
979 foreach_ir_nodeset(&cbc->children, t_irn, iter) {
980 foreach_pset(epk, k_edge) {
981 ir_node *val = k_edge->src;
983 if (k_edge->tgt == t_irn && ! ir_nodeset_contains(&cbc->parents, val)) {
984 ir_nodeset_insert(&cbc->parents, val);
986 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (killed by %+F)\n", val, t_irn));
991 /* accumulate children */
992 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
993 foreach_pset(epk, k_edge) {
994 ir_node *val = k_edge->tgt;
996 if (k_edge->src == s_irn && ! ir_nodeset_contains(&cbc->children, val)) {
997 ir_nodeset_insert(&cbc->children, val);
999 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (kills %+F)\n", val, s_irn));
1005 /* mark all parent values as visited */
1006 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
1007 rss_irn_t *s = get_rss_irn(rss, s_irn);
1009 /* assure bipartite property */
1011 if (ir_nodeset_contains(&cbc->children, s_irn)) {
1012 ir_nodeset_remove(&cbc->children, s_irn);
1013 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F removed from to children\n", s_irn));
1019 foreach_pset(epk, k_edge) {
1020 if (ir_nodeset_contains(&cbc->parents, k_edge->src) &&
1021 ir_nodeset_contains(&cbc->children, k_edge->tgt)) {
1022 pset_insert(cbc->kill_edges, k_edge, HASH_RSS_EDGE(k_edge));
1024 Link all k_edges which are about to be removed together.
1025 Beware: pset_remove kills the iterator.
1027 k_edge->next = kedge_root;
1028 kedge_root = k_edge;
1032 /* remove all linked k_edges */
1033 for (; kedge_root; kedge_root = kedge_root->next) {
1034 pset_remove(epk, kedge_root, HASH_RSS_EDGE(kedge_root));
1037 /* verify the cbc */
1038 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
1041 foreach_pset(cbc->kill_edges, k_edge) {
1042 if (k_edge->src == s_irn) {
1044 pset_break(cbc->kill_edges);
1051 ir_fprintf(stderr, "Warning: parent %+F is not killed in current cbc\n", s_irn);
1054 assert(vrfy_ok && "Verification of CBC failed");
1056 /* add the connected bipartite component */
1057 if (ir_nodeset_size(&cbc->parents) > 0 &&
1058 ir_nodeset_size(&cbc->children) > 0 &&
1059 pset_count(cbc->kill_edges) > 0)
1060 pset_insert(rss->cbc_set, cbc, (unsigned)cbc->nr);
1061 DBG((rss->dbg, LEVEL_2, "\tbipartite component %d inserted:\n", cbc->nr));
1063 if (firm_dbg_get_mask(rss->dbg) & LEVEL_2)
1064 debug_print_cbc(rss->dbg, cbc);
1068 if (rss->opts->dump_flags & RSS_DUMP_CBC)
1069 debug_vcg_dump_bipartite(rss);
1075 * Select the child with the maximum cost.
1077 static child_t *select_child_max_cost(rss_t *rss, ir_nodeset_t *x, ir_nodeset_t *y, child_t *t, cbc_t *cbc) {
1079 ir_nodeset_iterator_t iter;
1080 float max_cost = -1.0f;
1082 DBG((rss->dbg, LEVEL_2, "\t\tcomputing children costs:\n"));
1084 foreach_ir_nodeset(&cbc->children, child, iter) {
1085 rss_irn_t *r_child = get_rss_irn(rss, child);
1086 int num_unkilled_parents = 0;
1087 int num_descendants;
1091 /* get the number of unkilled parents */
1092 foreach_pset(cbc->kill_edges, k_edge) {
1093 if (k_edge->tgt == child && ir_nodeset_contains(x, k_edge->src))
1094 ++num_unkilled_parents;
1097 cost = (float)num_unkilled_parents;
1099 num_descendants = plist_count(r_child->descendant_list) + ir_nodeset_size(y);
1101 if (num_descendants > 0)
1102 cost /= (float)num_descendants;
1104 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F, #desc %d, cost %.3f\n", child, num_descendants, cost));
1106 if (cost > max_cost) {
1117 * Remove all parents from x which are killed by t_irn.
1119 static void remove_covered_parents(rss_t *rss, ir_nodeset_t *x, ir_node *t_irn, cbc_t *cbc) {
1120 rss_irn_t *t = get_rss_irn(rss, t_irn);
1123 DBG((rss->dbg, LEVEL_2, "\t\tremoving parents covered by %+F:\n", t_irn));
1125 foreach_pset(cbc->kill_edges, k_edge) {
1126 if (k_edge->tgt == t_irn && ir_nodeset_contains(x, k_edge->src)) {
1127 ir_nodeset_remove(x, k_edge->src);
1128 plist_insert_back(t->parent_list, k_edge->src);
1129 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", k_edge->src));
1134 static void update_cumulated_descendent_values(rss_t *rss, ir_nodeset_t *y, ir_node *t_irn) {
1135 rss_irn_t *t = get_rss_irn(rss, t_irn);
1136 plist_element_t *el;
1138 DBG((rss->dbg, LEVEL_2, "\t\tupdating cumulated descendant value of %+F:\n", t_irn));
1140 foreach_plist(t->descendant_list, el) {
1141 ir_nodeset_insert(y, plist_element_get_value(el));
1142 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", plist_element_get_value(el)));
1147 * Greedy-k: a heuristics for the MMA problem
1149 static void compute_killing_function(rss_t *rss) {
1151 struct obstack obst;
1153 obstack_init(&obst);
1155 rss->cbc_set = pset_new_ptr(5);
1156 compute_bipartite_decomposition(rss);
1158 /* for all bipartite components do: */
1159 foreach_pset(rss->cbc_set, cbc) {
1163 ir_nodeset_iterator_t iter;
1164 child_t **sks = NEW_ARR_F(child_t *, 20);
1169 ir_nodeset_init_size(&x, 10);
1170 ir_nodeset_init_size(&y, 10);
1172 DBG((rss->dbg, LEVEL_1, "\tcomputing SKS for cbc %d:\n", cbc->nr));
1173 DBG((rss->dbg, LEVEL_2, "\t\tinitializing parents X:\n"));
1175 /* X = S_cb (all parents are initially uncovered) */
1176 foreach_ir_nodeset(&cbc->parents, p, iter) {
1177 ir_nodeset_insert(&x, p);
1178 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", p));
1181 /* while X not empty */
1182 while (ir_nodeset_size(&x) > 0) {
1183 child_t *t = obstack_alloc(&obst, sizeof(*t));
1184 memset(t, 0, sizeof(*t));
1186 t = select_child_max_cost(rss, &x, &y, t, cbc);
1188 if (cur_len >= cur_size) {
1189 ARR_EXTO(child_t *, sks, cur_size * 2);
1193 DBG((rss->dbg, LEVEL_2, "\t\tinsert child %+F (%.3f) into SKS at pos %d\n", t->irn, t->cost, cur_len));
1196 remove_covered_parents(rss, &x, t->irn, cbc);
1197 update_cumulated_descendent_values(rss, &y, t->irn);
1200 ARR_SHRINKLEN(sks, cur_len);
1202 /* sort SKS in increasing cost order */
1203 qsort(sks, cur_len, sizeof(sks[0]), cmp_child_costs);
1205 DBG((rss->dbg, LEVEL_2, "\tprocessing SKS for cbc %d:\n", cbc->nr));
1207 /* build killing function */
1208 for (i = cur_len - 1; i >= 0; --i) { /* loop over sks in decreasing cost order */
1209 child_t *t = sks[i];
1210 rss_irn_t *rt = get_rss_irn(rss, t->irn);
1211 plist_element_t *p_el;
1213 DBG((rss->dbg, LEVEL_3, "\t\t\tkiller %+F (%.3f):\n", t->irn, t->cost));
1215 /* kill all unkilled parents of t */
1216 foreach_plist(rt->parent_list, p_el) {
1217 ir_node *par = plist_element_get_value(p_el);
1218 rss_irn_t *rpar = get_rss_irn(rss, par);
1220 if (is_Sink(rpar->killer)) {
1221 rpar->killer = t->irn;
1222 DBG((rss->dbg, LEVEL_2, "\t\tkill %+F\n", rpar->irn));
1225 DBG((rss->dbg, LEVEL_3, "\t\t\tkeeping %+F as killer for %+F\n", rpar->killer, rpar->irn));
1230 ir_nodeset_destroy(&x);
1231 ir_nodeset_destroy(&y);
1235 if (rss->opts->dump_flags & RSS_DUMP_KILL)
1236 debug_vcg_dump_kill(rss);
1238 del_pset(rss->cbc_set);
1239 obstack_free(&obst, NULL);
1243 * Adds the edge src -> tgt to the dvg. Checks if reverse edge is already there (asserts).
1245 static INLINE void add_dvg_edge(rss_t *rss, dvg_t *dvg, ir_node *src, ir_node *tgt, int have_source) {
1246 rss_edge_t *dvg_edge;
1250 ir_nodeset_insert(&dvg->nodes, src);
1252 assert(ir_nodeset_contains(&dvg->nodes, src) && "Wrong assumption");
1254 ir_nodeset_insert(&dvg->nodes, tgt);
1258 assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
1262 if (NULL != pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
1263 /* add the edge to the DVG */
1264 dvg_edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*dvg_edge));
1266 dvg_edge->src = src;
1267 dvg_edge->tgt = tgt;
1268 dvg_edge->next = NULL;
1270 DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", src, tgt));
1271 pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
1276 * Computes the disjoint value DAG (DVG).
1277 * BEWARE: It is not made explicitly clear in the Touati paper,
1278 * but the DVG is meant to be build from the KILLING DAG
1280 static void compute_dvg(rss_t *rss, dvg_t *dvg) {
1281 plist_element_t *el;
1283 DBG((rss->dbg, LEVEL_1, "\tcomputing DVG:\n"));
1285 foreach_plist(rss->nodes, el) {
1286 ir_node *u_irn = plist_element_get_value(el);
1287 rss_irn_t *u = get_rss_irn(rss, u_irn);
1288 rss_irn_t *u_killer = get_rss_irn(rss, u->killer);
1291 /* TODO: omit nodes only having sink as pkiller and killing no one */
1293 /* add an edge to killer */
1294 add_dvg_edge(rss, dvg, u_irn, u->killer, 0);
1296 if (is_Sink(u->killer))
1299 /* We add an edge to every killer, from where we could be reached. */
1300 for (i = ARR_LEN_SAFE(u_killer->descendants) - 1; i >= 0; --i) {
1301 add_dvg_edge(rss, dvg, u_irn, u_killer->descendants[i], 1);
1306 foreach_plist(rss->nodes, el2) {
1307 ir_node *v_irn = plist_element_get_value(el2);
1310 There is an edge (u, v) in the DVG iff v is a descendant of the killer(u).
1312 if (BSEARCH_IRN_ARR(v_irn, u_kill->descendants)) {
1313 rss_edge_t *dvg_edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*dvg_edge));
1316 /* insert the user into the DVG and append it to the user list of u */
1317 ir_nodeset_insert(&dvg->nodes, v_irn);
1318 if (! plist_has_value(u->dvg_user_list, v_irn))
1319 plist_insert_back(u->dvg_user_list, v_irn);
1321 dvg_edge->src = u_irn;
1322 dvg_edge->tgt = v_irn;
1323 dvg_edge->next = NULL;
1328 assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
1330 /* add the edge to the DVG */
1331 DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", u_irn, v_irn));
1332 pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
1338 if (rss->opts->dump_flags & RSS_DUMP_DVG)
1339 debug_vcg_dump_dvg(rss, dvg);
1343 * Updates the dvg structure when a serialization edge from src -> tgt is added.
1345 static void update_dvg(rss_t *rss, dvg_t *dvg, rss_irn_t *src, rss_irn_t *tgt) {
1348 rss_edge_t **arr = alloca(pset_count(dvg->edges) * sizeof(arr[0]));
1351 Add an edge from serialization target to serialization src:
1352 src cannot be alive with target
1354 add_dvg_edge(rss, dvg, tgt->irn, src->irn, 0);
1356 /* Add edges to src's descendants as well, they also getting serialized. */
1357 for (i = ARR_LEN_SAFE(src->descendants) - 1; i >= 0; --i) {
1358 add_dvg_edge(rss, dvg, tgt->irn, src->descendants[i], 1);
1361 /* We also have to add edges from targets predecessors in dvg */
1363 /* We cannot insert elements into set over which we iterate ... */
1364 foreach_pset(dvg->edges, edge) {
1365 if (edge->tgt == tgt->irn) {
1370 for (i = 0; i < idx; ++i) {
1372 add_dvg_edge(rss, dvg, edge->src, src->irn, 1);
1373 for (j = ARR_LEN_SAFE(src->descendants) - 1; j >= 0; --j) {
1374 add_dvg_edge(rss, dvg, edge->src, src->descendants[j], 1);
1381 * Accumulate all descendants for root into list.
1383 static void accumulate_dvg_descendant_values(rss_t *rss, rss_irn_t *root, plist_t *list) {
1384 if (plist_count(root->dvg_user_list) > 0) {
1385 plist_element_t *el;
1387 foreach_plist(root->dvg_user_list, el) {
1388 ir_node *v_irn = plist_element_get_value(el);
1389 rss_irn_t *v = get_rss_irn(rss, v_irn);
1391 /* add v as descendant */
1392 if (! plist_has_value(list, v_irn)) {
1393 plist_insert_back(list, v_irn);
1394 DBG((rss->dbg, DEBUG_DVG, "\t\t\tadd DVG descendant %+F\n", v_irn));
1397 /* accumulate v's descendants */
1398 accumulate_dvg_descendant_values(rss, v, list);
1404 * Builds the list of potential killers for each node
1406 * Needs the descendant list for all user as sorted array.
1408 static void build_dvg_pkiller_list(rss_t *rss, dvg_t *dvg) {
1409 ir_nodeset_iterator_t iter;
1412 foreach_nodeset(&dvg->nodes, irn, iter) {
1413 rss_irn_t *node = get_rss_irn(rss, irn);
1414 plist_element_t *el, *el2;
1416 DBG((rss->dbg, DEBUG_DVG, "\t\tbuilding pkiller list for %+F\n", irn));
1418 /* check each user */
1419 foreach_plist(node->dvg_user_list, el) {
1420 ir_node *u_irn = plist_element_get_value(el);
1422 /* is the current user u_irn not a descendant of any other user -> pkiller */
1423 foreach_plist(node->dvg_user_list, el2) {
1424 ir_node *v_irn = plist_element_get_value(el2);
1425 rss_irn_t *v = get_rss_irn(rss, v_irn);
1428 ! BSEARCH_IRN_ARR(u_irn, v->dvg_desc) &&
1429 ! plist_has_value(node->dvg_pkiller_list, u_irn))
1431 plist_insert_back(node->dvg_pkiller_list, u_irn);
1432 DBG((rss->dbg, DEBUG_DVG, "\t\t\tadd DVG pkiller %+F\n", u_irn));
1437 node->dvg_pkiller = build_sorted_array_from_list(node->dvg_pkiller_list, phase_obst(&rss->ph));
1441 if (firm_dbg_get_mask(rss->dbg) & DEBUG_DVG)
1442 debug_vcg_dump_dvg_pkiller(rss, dvg);
1449 * Compute the maximal antichain of the current DVG.
1450 * This is a reimplementation of the MAXIMAL_ANTI_CHAIN function
1451 * from the DDG library 1.1 (DAG.cpp).
1453 static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration) {
1454 int n = ir_nodeset_size(&dvg->nodes);
1455 int *assignment = alloca(n * sizeof(assignment[0]));
1456 int *assignment_rev = alloca(n * sizeof(assignment_rev[0]));
1457 int *idx_map = alloca(n * sizeof(idx_map[0]));
1458 hungarian_problem_t *bp;
1459 ir_nodeset_t *values, *temp;
1460 ir_nodeset_iterator_t iter;
1462 int i, j, cost, cur_chain, res;
1463 rss_edge_t *dvg_edge;
1465 #define MAP_IDX(irn) bsearch_for_index(get_irn_idx(irn), idx_map, n, 1)
1467 if (pset_count(dvg->edges) == 0)
1470 bp = hungarian_new(n, n, 1, HUNGARIAN_MATCH_NORMAL);
1473 At first, we build an index map for the nodes in the DVG,
1474 because we cannot use the irn idx therefore as the resulting
1475 bipartite data structure would have around 1.2GB.
1476 So we limit the size to the number of nodes we have in the DVG
1477 and build a sorted index map for their irn indices.
1480 foreach_ir_nodeset(&dvg->nodes, u_irn, iter) {
1481 idx_map[i++] = get_irn_idx(u_irn);
1483 qsort(idx_map, n, sizeof(idx_map[0]), cmp_int);
1485 foreach_pset(dvg->edges, dvg_edge) {
1486 int idx_u = MAP_IDX(dvg_edge->src);
1487 int idx_v = MAP_IDX(dvg_edge->tgt);
1489 /* add the entry to the bipartite data structure */
1490 hungarian_add(bp, idx_u, idx_v, 1);
1491 DBG((rss->dbg, LEVEL_3, "\t\t\tadd %d (%+F) -> %d (%+F)\n",
1492 idx_u, dvg_edge->src, idx_v, dvg_edge->tgt));
1496 Add a bipartite entry for each pair of nodes (u, v), where exists a
1497 path in the DVG from u to v, ie. connect all descendants(v) to v.
1498 desc_dvg(v) = accumulated descendants of all z in dvg_user_list(v)
1500 foreach_ir_nodeset(&dvg->nodes, u_irn, iter) {
1501 rss_irn_t *u = get_rss_irn(rss, u_irn);
1502 int idx_u_irn = MAP_IDX(u_irn);
1504 DBG((rss->dbg, DEBUG_DVG, "\t\tcomputing DVG descendants of %+F:\n", u_irn));
1506 //plist_clear(u->dvg_desc_list);
1507 //accumulate_dvg_descendant_values(rss, u, u->dvg_desc_list);
1510 FIXME: The array is build on the phase obstack and we cannot free the data.
1511 So the array get as many times allocated as this function is called.
1514 /* build the sorted array for faster searches */
1515 //u->dvg_desc = build_sorted_array_from_list(u->dvg_desc_list, phase_obst(&rss->ph));
1517 DBG((rss->dbg, DEBUG_MAX_AC, "\t\tadding bipartite entries of %+F:\n", u_irn));
1519 /* add the bipartite entries for all descendants */
1520 for (i = ARR_LEN_SAFE(u->dvg_desc) - 1; i >= 0; --i) {
1521 rss_irn_t *desc = get_rss_irn(rss, u->dvg_desc[i]);
1522 int idx_desc = MAP_IDX(u->dvg_desc[i]);
1524 /* add the entry to the bipartite data structure */
1525 hungarian_add(bp, idx_u_irn, idx_desc, 1);
1526 DBG((rss->dbg, DEBUG_MAX_AC, "\t\t\tadd %d (%+F) -> %d (%+F)\n",
1527 idx_u_irn, u_irn, idx_desc, u->dvg_desc[i]));
1534 /* We want maximum cardinality matching */
1535 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
1538 DBG((rss->dbg, DEBUG_DVG, "\t\tcomputing DVG pkiller:\n"));
1539 /* beware: the following function needs the dvg_desc array */
1540 build_dvg_pkiller_list(rss, dvg);
1543 DBG((rss->dbg, LEVEL_2, "\t\tcomputing bipartite matching\n"));
1545 The maximum cardinality bipartite matching gives us the minimal
1546 chain partition, which corresponds to the maximum anti chains.
1548 res = hungarian_solve(bp, assignment, &cost, 1);
1549 assert(res == 0 && "Bipartite matching failed!");
1552 memset(assignment_rev, -1, n * sizeof(assignment_rev[0]));
1554 /* build the reverse assignment, ie. foreach i -> j, add j -> i */
1555 for (i = 0; i < n; ++i) {
1556 if (assignment[i] >= 0) {
1557 int j = assignment[i];
1558 assignment_rev[j] = i;
1562 DBG((rss->dbg, LEVEL_2, "\t\tgot assignment with cost %d\n", cost));
1563 DBG((rss->dbg, LEVEL_3, "\t\t\tassignment --- reverse assignment\n", cost));
1564 for (i = 0; i < n; ++i) {
1565 DBG((rss->dbg, LEVEL_3, "\t\t\t%3d -> %3d %3d -> %3d\n", i, assignment[i], i, assignment_rev[i]));
1568 values = xmalloc(sizeof(values[0]));
1569 ir_nodeset_init_size(values, 10);
1571 /* Construction of the minimal chain partition */
1572 for (j = 0; j < n; ++j) {
1573 /* check nodes, which did not occur as target */
1574 if (assignment_rev[j] == -1) {
1575 int xj = idx_map[j];
1576 ir_node *xj_irn = get_idx_irn(rss->irg, xj);
1577 rss_irn_t *xj_rss = get_rss_irn(rss, xj_irn);
1578 chain_t *c = obstack_alloc(phase_obst(&rss->ph), sizeof(*c));
1581 /* there was no source for j -> we have a source of a new chain */
1582 ir_nodeset_insert(values, xj_irn);
1584 c->elements = plist_obstack_new(phase_obst(&rss->ph));
1585 c->nr = cur_chain++;
1586 plist_insert_back(c->elements, xj_irn);
1590 DBG((rss->dbg, LEVEL_2, "\t\tstarting chain %d:\n", c->nr));
1591 DBG((rss->dbg, LEVEL_2, "\t\t\t%+F (%d)", xj_irn, j));
1593 /* follow chain, having j as source */
1595 while (assignment[source] >= 0) {
1596 int target = assignment[source];
1597 int irn_idx = idx_map[target];
1598 ir_node *irn = get_idx_irn(rss->irg, irn_idx);
1599 rss_irn_t *node = get_rss_irn(rss, irn);
1601 plist_insert_back(c->elements, irn);
1604 DB((rss->dbg, LEVEL_2, " -> %+F (%d)", irn, target));
1606 /* new source = last target */
1610 DB((rss->dbg, LEVEL_2, "\n"));
1615 Computing the maximal antichain: Select an element from each
1616 chain such, such it is parallel with the others.
1618 DBG((rss->dbg, LEVEL_1, "\t\tcomputing set of saturation values (MAX AC)\n"));
1619 DBG((rss->dbg, LEVEL_3, "\t\tstarting with:\n"));
1622 if (firm_dbg_get_mask(rss->dbg) & LEVEL_3)
1623 dump_nodeset(values, "\t\t\t");
1629 We need an explicit array for the values as
1630 we cannot iterate multiple times over the same
1631 set at the same time. :-(((((
1632 TODO Matze: now we can, so rewrite this...
1634 int n = ir_nodeset_size(values);
1636 ir_node **val_arr = NEW_ARR_F(ir_node *, n);
1638 foreach_ir_nodeset(values, u_irn, iter)
1639 val_arr[i++] = u_irn;
1642 ir_nodeset_destroy(temp);
1646 temp = xmalloc(sizeof(temp[0]));
1647 ir_nodeset_init_size(temp, 10);
1649 /* Select all nodes from current value set, having another node in the set as descendant. */
1650 for (i = 0; i < n; ++i) {
1651 rss_irn_t *u = get_rss_irn(rss, val_arr[i]);
1653 for (j = 0; j < n; ++j) {
1657 key.src = val_arr[i];
1658 key.tgt = val_arr[j];
1660 if (pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
1661 /* v[j] is descendant of u -> remove u and break */
1662 ir_nodeset_insert(temp, u->irn);
1663 ir_nodeset_remove(values, u->irn);
1665 DBG((rss->dbg, LEVEL_3, "\t\t\tremoving %+F from values, adding it to temp\n", u->irn));
1673 /* Try to insert the chain predecessor of all selected u's */
1674 foreach_ir_nodeset(temp, u_irn, iter) {
1675 rss_irn_t *u = get_rss_irn(rss, u_irn);
1676 chain_t *c = u->chain;
1677 plist_element_t *el = plist_find_value(c->elements, u_irn);
1679 assert(el && "Missing element in chain!");
1681 /* If u has predecessor in chain: insert the predecessor */
1682 if (el == plist_element_get_prev(el)) {
1683 ir_nodeset_insert(values, plist_element_get_value(el));
1684 DBG((rss->dbg, LEVEL_3, "\t\t\tadding %+F to values\n", plist_element_get_value(el)));
1690 } while (ir_nodeset_size(temp) > 0);
1692 DBG((rss->dbg, LEVEL_2, "\t\tfinal set:\n"));
1694 if (firm_dbg_get_mask(rss->dbg) & LEVEL_2) {
1695 dump_nodeset(values, "\t\t\t");
1699 if (rss->opts->dump_flags & RSS_DUMP_MAXAC)
1700 debug_vcg_dump_pkg(rss, values, iteration);
1703 ir_nodeset_destroy(temp);
1713 * Computes the best serialization between two nodes of sat_vals.
1715 static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nodeset_t *sat_vals, serialization_t *ser, int num_regs) {
1716 int n = ir_nodeset_size(sat_vals);
1717 int n_idx = ARR_LEN_SAFE(rss->idx_map);
1719 ir_node **val_arr = alloca(n * sizeof(val_arr[0]));
1720 bitset_t *bs_sv = bitset_alloca(n_idx);
1721 bitset_t *bs_vdesc = bitset_alloca(n_idx);
1722 bitset_t *bs_tmp = bitset_alloca(n_idx);
1723 bitset_t *bs_ukilldesc = bitset_alloca(n_idx);
1724 int best_benefit = INT_MAX;
1725 int best_omega2 = INT_MAX;
1726 int best_benefit_omega20 = INT_MAX;
1730 ir_nodeset_iterator_t iter;
1731 rss_edge_t min_benefit_edge;
1732 rss_edge_t min_omega20_edge;
1733 rss_irn_t *ser_u_omega1 = NULL, *ser_v_omega1 = NULL;
1734 rss_irn_t *ser_u_omega20 = NULL, *ser_v_omega20 = NULL;
1736 DBG((rss->dbg, LEVEL_1, "\tcomputing admissible serializations:\n"));
1739 We need an explicit array for the values as
1740 we cannot iterate multiple times over the same
1741 set at the same time. :-(((((
1744 foreach_ir_nodeset(sat_vals, irn, iter) {
1746 bitset_set(bs_sv, BLOCK_IDX_MAP(rss, irn));
1750 We build all admissible serializations and remember the best found so far.
1753 if v in pkiller(u): add edge from v to all other pkiller(u)
1754 else: for all vv in pkiller(u): add edge from v to vv if there exists no path from vv to v
1758 A node is unserializable if:
1759 - it has only one killer and this one is Sink
1760 - it kills no other values
1761 In this case there is no serialization which could
1762 reduce the registerpressure
1764 #define IS_UNSERIALIZABLE_NODE(rss_node) \
1767 (plist_count(rss_node->pkiller_list) == 1) && \
1768 is_Sink(rss_node->killer) && \
1769 (rss_node->kill_count == 0) \
1771 be_is_Barrier(rss_node->irn) || \
1772 be_is_Keep(rss_node->irn) \
1775 /* for all u in sat_vals */
1776 for (i = 0; i < n; ++i) {
1777 rss_irn_t *u = get_rss_irn(rss, val_arr[i]);
1778 plist_element_t *el;
1780 /* ignore nodes where serialization does not help */
1781 if (IS_UNSERIALIZABLE_NODE(u)) {
1782 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", u->irn));
1786 /* accumulate all descendants of all pkiller(u) */
1787 bitset_clear_all(bs_ukilldesc);
1788 foreach_plist(u->pkiller_list, el) {
1789 ir_node *irn = plist_element_get_value(el);
1790 rss_irn_t *node = get_rss_irn(rss, irn);
1793 bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, irn));
1797 for (k = ARR_LEN_SAFE(node->descendants) - 1; k >= 0; --k) {
1798 if (! is_Sink(node->descendants[k]))
1799 bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, node->descendants[k]));
1803 /* for all v in sat_vals */
1804 for (j = 0; j < n; ++j) {
1805 ir_node *v_irn = val_arr[j];
1806 rss_irn_t *v = get_rss_irn(rss, v_irn);
1807 unsigned v_height = get_irn_height(rss->h, v_irn);
1808 int omega1, omega2, is_pkiller;
1810 /* v cannot be serialized with itself
1811 * ignore nodes where serialization does not help */
1812 if (i == j || IS_UNSERIALIZABLE_NODE(v)) {
1814 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", v->irn));
1818 /* get descendants of v */
1819 bitset_clear_all(bs_vdesc);
1820 bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v_irn));
1821 for (k = ARR_LEN_SAFE(v->descendants) - 1; k >= 0; --k) {
1822 if (! is_Sink(v->descendants[k]))
1823 bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v->descendants[k]));
1826 /* if v is in pkiller(u) */
1827 is_pkiller = plist_has_value(u->pkiller_list, v_irn);
1829 /* for all vv in pkiller(u) */
1830 foreach_plist(u->pkiller_list, el) {
1831 ir_node *vv_irn = plist_element_get_value(el);
1834 if (is_Sink(vv_irn) || is_cfop(vv_irn))
1838 add_edge = vv_irn != v_irn && skip_Proj(vv_irn) != skip_Proj(v_irn);
1840 add_edge = ! heights_reachable_in_block(rss->h, skip_Proj(vv_irn), skip_Proj(v_irn));
1843 As we add an edge from vv -> v, we have to make sure,
1844 that there exists no path from v to vv.
1848 unsigned vv_height = get_irn_height(rss->h, vv_irn);
1849 unsigned critical_path_cost;
1853 mu1 = | descendants(v) cut sat_vals |
1854 the number of saturating values which cannot
1855 be simultaneously alive with u
1857 bitset_copy(bs_tmp, bs_vdesc);
1858 mu1 = bitset_popcnt(bitset_and(bs_tmp, bs_sv));
1861 mu2 = | accum_desc_all_pkiller(u) without descendants(v) |
1864 bitset_copy(bs_tmp, bs_ukilldesc);
1865 mu2 = bitset_popcnt(bitset_andnot(bs_tmp, bs_vdesc));
1871 /* omega1 = mu1 - mu2 */
1877 /* omega2 = increase of critical path */
1878 critical_path_cost =
1879 v_height /* longest path from v to sink */
1880 + rss->max_height - vv_height /* longest path from source to vv */
1884 If critical_path_cost > max_height -> the new edge
1885 would increase the longest critical path by the difference.
1887 omega2 = critical_path_cost > rss->max_height ? critical_path_cost - rss->max_height : 0;
1889 /* this keeps track of the edge with the best benefit */
1890 if (omega1 >= num_regs - n && omega1 < best_benefit) {
1891 min_benefit_edge.src = v_irn;
1892 min_benefit_edge.tgt = vv_irn;
1897 best_benefit = omega1;
1898 ser->new_killer = is_pkiller;
1901 /* this keeps track of the edge with the best omega1 costs where omega2 == 0 */
1902 if (omega2 == 0 && omega1 >= num_regs - n && omega1 < best_benefit_omega20) {
1903 min_omega20_edge.src = v_irn;
1904 min_omega20_edge.tgt = vv_irn;
1909 best_benefit_omega20 = omega1;
1910 ser->new_killer = is_pkiller;
1913 best_omega2 = MIN(best_omega2, omega2);
1915 DBG((rss->dbg, LEVEL_2, "\t\tfound %+F -> %+F (w1 %d, w2 %d)\n",
1916 v_irn, vv_irn, omega1, omega2));
1918 } /* for all vv in pkiller(u) */
1919 } /* for all v in sat_vals */
1920 } /* for all u in sat_vals */
1925 if (best_omega2 == 0) {
1926 ser->u = ser_u_omega20;
1927 ser->v = ser_v_omega20;
1928 ser->edge->src = min_omega20_edge.src;
1929 ser->edge->tgt = min_omega20_edge.tgt;
1930 ser->omega1 = best_benefit_omega20;
1931 ser->omega2 = best_omega2;
1934 ser->u = ser_u_omega1;
1935 ser->v = ser_v_omega1;
1936 ser->edge->src = min_benefit_edge.src;
1937 ser->edge->tgt = min_benefit_edge.tgt;
1938 ser->omega1 = best_benefit;
1939 ser->omega2 = best_omega2;
1944 #undef IS_UNSERIALIZABLE_NODE
1948 * Perform the value serialization heuristic and add all
1949 * computed serialization edges as dependencies to the irg.
1951 static void perform_value_serialization_heuristic(rss_t *rss) {
1952 bitset_t *arch_nonign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls));
1953 bitset_t *abi_ign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls));
1954 unsigned available_regs, iteration;
1956 ir_nodeset_t *sat_vals;
1957 pset *ser_set = new_pset(cmp_rss_edges, 20);
1959 /* available_regs = R = |arch_non_ignore_regs cut ~abi_ignore_regs| */
1960 arch_put_non_ignore_regs(rss->arch_env, rss->cls, arch_nonign_bs);
1961 be_abi_put_ignore_regs(rss->abi, rss->cls, abi_ign_bs);
1962 bitset_andnot(arch_nonign_bs, abi_ign_bs);
1963 available_regs = bitset_popcnt(arch_nonign_bs);
1964 //num_live = pset_count(rss->live_block);
1965 //available_regs -= num_live < available_regs ? num_live : 0;
1967 DBG((rss->dbg, LEVEL_1, "\n\t#available regs: %d\n\n", available_regs));
1970 At first we need to compute the disjoint value DAG (DVG = {V, E_dv}).
1971 V = set of all nodes we are currently interested in
1972 E_dv = there is an edge from u to v iff v is a descendant of killer(u), forall u, v in V
1974 ir_nodeset_init_size(&dvg.nodes, plist_count(rss->nodes));
1975 dvg.edges = new_pset(cmp_rss_edges, plist_count(rss->nodes) * 5);
1976 compute_dvg(rss, &dvg);
1979 Then we perform the heuristic serialization algorithm
1980 on the DVG which gives us all necessary serialization
1983 DBG((rss->dbg, LEVEL_1, "\tcomputing maximal antichain:\n"));
1985 sat_vals = compute_maximal_antichain(rss, &dvg, iteration++);
1986 while (sat_vals && (ir_nodeset_size(sat_vals) > available_regs)) {
1987 serialization_t *ser, best_ser;
1988 rss_edge_t *edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*edge));
1989 ir_node *dep_src, *dep_tgt;
1991 best_ser.edge = edge;
1992 ser = compute_best_admissible_serialization(rss, sat_vals, &best_ser, available_regs);
1994 DBG((rss->dbg, LEVEL_1, "\tcurrent register saturation %d, target %d\n", ir_nodeset_size(sat_vals), available_regs));
1997 DBG((rss->dbg, LEVEL_1, "\tno RS improving serialization found, breaking at iteration %d\n", iteration));
2001 /* Insert the serialization as dependency edge into the irg. */
2002 DBG((rss->dbg, LEVEL_1, "\tserializing %+F -> %+F with edge %+F -> %+F and cost %d, %d\n",
2003 ser->u->irn, ser->v->irn, ser->edge->src, ser->edge->tgt, ser->omega1, ser->omega2));
2005 if (pset_find(ser_set, ser->edge, HASH_RSS_EDGE(ser->edge)))
2006 ir_printf("WARNING: serialization %+F -> %+F computed twice!\n", ser->edge->src, ser->edge->tgt);
2009 pset_insert(ser_set, ser->edge, HASH_RSS_EDGE(ser->edge));
2011 /* update the dvg */
2012 update_dvg(rss, &dvg, ser->v, ser->u);
2013 update_dvg(rss, &dvg, get_rss_irn(rss, ser->edge->src), get_rss_irn(rss, ser->edge->tgt));
2014 if(sat_vals != NULL) {
2015 ir_nodeset_destroy(sat_vals);
2019 dep_src = skip_Proj(ser->edge->src);
2020 dep_tgt = ser->edge->tgt;
2021 add_irn_dep(dep_src, dep_tgt);
2023 /* Update descendants, consumer and pkillers of the target */
2024 update_node_info(rss, ser->edge->tgt, ser->edge->src);
2026 /* TODO: try to find a cheaper way for updating height information */
2027 rss->max_height = heights_recompute_block(rss->h, rss->block);
2029 /* Recompute the antichain for next serialization */
2030 DBG((rss->dbg, LEVEL_1, "\tre-computing maximal antichain:\n"));
2031 sat_vals = compute_maximal_antichain(rss, &dvg, iteration++);
2034 ir_nodeset_destroy(&dvg.nodes);
2035 del_pset(dvg.edges);
2039 * Do initial calculations for a block.
2041 static void process_block(ir_node *block, void *env) {
2044 const ir_edge_t *edge;
2046 phase_init(&rss->ph, "rss block preprocessor", rss->irg, PHASE_DEFAULT_GROWTH, init_rss_irn, NULL);
2048 DBG((rss->dbg, LEVEL_1, "preprocessing block %+F\n", block));
2051 /* build an index map for all nodes in the current block */
2053 n = get_irn_n_edges(block);
2054 NEW_ARR_A(int *, rss->idx_map, n);
2055 foreach_out_edge(block, edge) {
2056 ir_node *irn = get_edge_src_irn(edge);
2057 rss->idx_map[i++] = get_irn_idx(irn);
2059 qsort(rss->idx_map, n, sizeof(rss->idx_map[0]), cmp_int);
2060 rss->max_height = heights_recompute_block(rss->h, block);
2062 /* loop over all register classes */
2063 for (i = arch_isa_get_n_reg_class(rss->arch_env->isa) - 1; i >= 0; --i) {
2064 const arch_register_class_t *cls = arch_isa_get_reg_class(rss->arch_env->isa, i);
2067 DBG((rss->dbg, LEVEL_1, "register class %s\n", arch_register_class_name(cls)));
2069 /* Get all live value at end of Block having current register class */
2070 rss->live_block = pset_new_ptr(10);
2071 be_liveness_end_of_block(rss->liveness, rss->arch_env, rss->cls, rss->block, rss->live_block);
2073 /* reset the list of interesting nodes */
2074 plist_clear(rss->nodes);
2075 plist_insert_back(rss->nodes, _sink);
2077 /* collect all nodes having a certain register class */
2078 foreach_out_edge(block, edge) {
2079 ir_node *irn = get_edge_src_irn(edge);
2080 ir_mode *mode = get_irn_mode(irn);
2084 - mode_T nodes (the projs are asked)
2085 - mode_X nodes (control flow nodes are always scheduled last)
2086 - Keeps (they are always immediately scheduled)
2087 - Phi (same as Keep)
2089 if (mode == mode_T || mode == mode_X || is_Phi(irn))
2093 In case of a proj, we skip
2094 - Barrier (they are a Barrier :)
2096 - the Proj itself, as it's scheduled always with it's super node
2099 ir_node *pred = get_Proj_pred(irn);
2100 if (be_is_Barrier(pred) || is_Start(pred))
2104 /* calculate the descendants and consumer for each node in the block */
2105 collect_node_info(rss, skip_Proj(irn));
2107 if (be_is_Keep(irn))
2110 if (! arch_irn_is(rss->arch_env, irn, ignore) && arch_get_irn_reg_class(rss->arch_env, irn, -1) == cls) {
2111 plist_insert_back(rss->nodes, skip_Proj(irn));
2116 /* compute the potential killing set PK(G) */
2117 compute_pkill_set(rss);
2119 /* compute the killing function k* */
2120 compute_killing_function(rss);
2123 Compute the heuristic value serialization and
2124 add the necessary dependencies to the irg.
2126 perform_value_serialization_heuristic(rss);
2128 del_pset(rss->live_block);
2131 phase_free(&rss->ph);
2135 * Register the options.
2137 void be_init_schedrss(void) {
2138 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
2139 lc_opt_entry_t *sched_grp = lc_opt_get_grp(be_grp, "sched");
2140 lc_opt_entry_t *rss_grp = lc_opt_get_grp(sched_grp, "rss");
2142 lc_opt_add_table(rss_grp, rss_option_table);
2145 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_schedrss);
2148 * Preprocess the irg for scheduling.
2150 void rss_schedule_preparation(const be_irg_t *birg) {
2151 ir_graph *irg = be_get_birg_irg(birg);
2154 FIRM_DBG_REGISTER(rss.dbg, "firm.be.sched.rss");
2156 //firm_dbg_set_mask(rss.dbg, LEVEL_1 | LEVEL_2 | LEVEL_3);
2158 init_rss_special_nodes(irg);
2161 rss.arch_env = be_get_birg_arch_env(birg);
2162 rss.abi = birg->abi;
2163 rss.h = heights_new(irg);
2164 rss.nodes = plist_new();
2165 rss.opts = &rss_options;
2166 rss.liveness = be_liveness(irg);
2167 irg_block_walk_graph(irg, NULL, process_block, &rss);
2168 heights_free(rss.h);
2169 plist_free(rss.nodes);
2170 be_liveness_free(rss.liveness);
2172 if (birg->main_env->options->dump_flags & DUMP_SCHED)
2173 be_dump(rss.irg, "-rss", dump_ir_block_graph);