2 * Copyright (C) 1995-2008 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
33 #include "beschedrss.h"
40 #include "irgraph_t.h"
42 #include "iredges_t.h"
44 #include "irphase_t.h"
50 #include "irnodeset.h"
51 #include "bipartite.h"
52 #include "hungarian.h"
66 #include "lc_opts_enum.h"
69 #define ARR_LEN_SAFE(arr) ((arr) != NULL ? ARR_LEN((arr)) : 0)
71 #define HASH_RSS_EDGE(edge) ((get_irn_node_nr((edge)->src) << 16) | (get_irn_node_nr((edge)->tgt) & 0xFFFF))
72 #define BSEARCH_IRN_ARR(val, arr) \
73 bsearch(&(val), (arr), ARR_LEN_SAFE((arr)), sizeof((arr)[0]), cmp_irn_idx)
75 #define BLOCK_IDX_MAP(rss, irn) bsearch_for_index(get_irn_idx((irn)), (rss)->idx_map, ARR_LEN_SAFE((rss)->idx_map), 1)
78 typedef struct rss_opts_t {
82 /* Represents a child with associated costs */
83 typedef struct child {
88 /* We need edges for several purposes. */
89 typedef struct rss_edge {
95 /* Represents a connected bipartite component. */
97 ir_nodeset_t parents; /**< = S a set of value producers */
98 ir_nodeset_t children; /**< = T a set of value consumers */
99 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 */
100 int nr; /**< a deterministic index for set insertion (used as hash) */
103 /* Represents a disjoint value DAG. */
109 /* Represents a chain of nodes. */
110 typedef struct chain {
111 plist_t *elements; /**< List of chain elements */
112 int nr; /**< a deterministic index for set insertion (used as hash) */
115 typedef struct rss_irn {
116 plist_t *consumer_list; /**< List of consumers */
117 const ir_node **consumer; /**< Sorted consumer array (needed for faster access) */
119 plist_t *parent_list; /**< List of parents */
120 plist_t *pkiller_list; /**< List of potential killers */
122 plist_t *descendant_list; /**< List of descendants */
123 const ir_node **descendants; /**< Sorted descendant array (needed for faster access) */
125 const ir_node *killer; /**< The selected unique killer */
126 const ir_node *irn; /**< The corresponding firm node to this rss_irn */
128 chain_t *chain; /**< The chain, this node is associated to */
130 unsigned desc_walk; /**< visited flag for collecting descendants */
131 unsigned kill_count; /**< number of nodes killed by this one */
133 unsigned live_out : 1; /**< irn has consumers outside of it's block */
134 unsigned visited : 1; /**< visited flag for bipartite decomposition */
135 unsigned havecons : 1; /**< visited flag collect consumer */
136 unsigned handled : 1; /**< flag indicating whether or not the list structures have been build */
137 unsigned dumped : 1; /**< flag indication whether or not this node was dumped */
140 /* Represents a serialization edge with associated costs. */
141 typedef struct serialization {
142 rss_irn_t *u; /* the top node */
143 rss_irn_t *v; /* the node about to be serialized after u */
144 rss_edge_t *edge; /* the edge selected for the serialization */
145 int omega1; /* estimated: available regs - RS reduction */
146 int omega2; /* increase in critical path length */
151 ir_phase ph; /**< Phase to hold some data */
152 ir_heights_t *h; /**< The current height object */
153 ir_graph *irg; /**< The irg to preprocess */
154 plist_t *nodes; /**< The list of interesting nodes */
155 const arch_env_t *arch_env; /**< The architecture environment */
156 be_abi_irg_t *abi; /**< The abi for this irg */
157 pset *cbc_set; /**< A set of connected bipartite components */
158 ir_node *block; /**< The current block in progress. */
159 int *idx_map; /**< Mapping irn indices to per block indices */
160 unsigned max_height; /**< maximum height in the current block */
161 rss_opts_t *opts; /**< The options */
162 be_lv_t *liveness; /**< The liveness information for this irg */
163 ir_nodeset_t live_block; /**< Values alive at end of block */
164 const arch_register_class_t *cls; /**< The current register class */
165 DEBUG_ONLY(firm_dbg_module_t *dbg);
168 static inline rss_irn_t *get_rss_irn(rss_t *env, const ir_node *node)
170 return (rss_irn_t*)phase_get_or_set_irn_data(&env->ph, node);
174 * We need some special nodes:
175 * a source and a sink for all live-in and live-out values of a block
183 /** The opcode of the rss_Source node once allocated. */
184 static ir_op *op_rss_Source;
185 /** The opcode of the rss_Sink node once allocated. */
186 static ir_op *op_rss_Sink;
188 /** The rss_Source node of the current graph. */
189 static ir_node *_source = NULL;
190 /** The rss_Sink node of the current graph. */
191 static ir_node *_sink = NULL;
193 #define is_Source(irn) ((irn) == _source)
194 #define is_Sink(irn) ((irn) == _sink)
198 RSS_DUMP_CBC = 1 << 0,
199 RSS_DUMP_PKG = 1 << 1,
200 RSS_DUMP_KILL = 1 << 2,
201 RSS_DUMP_DVG = 1 << 3,
202 RSS_DUMP_MAXAC = 1 << 4,
203 RSS_DUMP_ALL = (RSS_DUMP_MAXAC << 1) - 1,
206 static rss_opts_t rss_options = {
210 static const lc_opt_enum_int_items_t dump_items[] = {
211 { "none", RSS_DUMP_NONE },
212 { "cbc", RSS_DUMP_CBC },
213 { "pkg", RSS_DUMP_PKG },
214 { "kill", RSS_DUMP_KILL },
215 { "dvg", RSS_DUMP_DVG },
216 { "maxac", RSS_DUMP_MAXAC },
217 { "all", RSS_DUMP_ALL },
221 static lc_opt_enum_int_var_t dump_var = {
222 &rss_options.dump_flags, dump_items
225 static const lc_opt_table_entry_t rss_option_table[] = {
226 LC_OPT_ENT_ENUM_MASK("dump", "dump phases", &dump_var),
230 /******************************************************************************
232 * | | | | / _| | | (_)
233 * | |__ ___| |_ __ ___ _ __ | |_ _ _ _ __ ___| |_ _ ___ _ __ ___
234 * | '_ \ / _ \ | '_ \ / _ \ '__| | _| | | | '_ \ / __| __| |/ _ \| '_ \/ __|
235 * | | | | __/ | |_) | __/ | | | | |_| | | | | (__| |_| | (_) | | | \__ \
236 * |_| |_|\___|_| .__/ \___|_| |_| \__,_|_| |_|\___|\__|_|\___/|_| |_|___/
239 ******************************************************************************/
242 * Acquire opcodes if needed and create source and sink nodes.
244 static void init_rss_special_nodes(ir_graph *irg)
248 if (op_rss_Source == NULL) {
249 int iro_rss_base = get_next_ir_opcodes(iro_rss_last);
250 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);
251 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);
253 block = get_irg_start_block(irg);
254 _source = new_ir_node(NULL, irg, block, op_rss_Source, mode_ANY, 0, NULL);
255 _sink = new_ir_node(NULL, irg, block, op_rss_Sink, mode_ANY, 0, NULL);
258 static int cmp_int(const void *a, const void *b)
260 const int *i1 = (const int*)a;
261 const int *i2 = (const int*)b;
263 return QSORT_CMP(*i1, *i2);
266 static int cmp_child_costs(const void *a, const void *b)
268 const child_t *c1 = (const child_t*)a;
269 const child_t *c2 = (const child_t*)b;
271 return QSORT_CMP(c1->cost, c2->cost);
274 static int cmp_irn_idx(const void *a, const void *b)
276 const ir_node *n1 = *(ir_node **)a;
277 const ir_node *n2 = *(ir_node **)b;
279 return QSORT_CMP(get_irn_idx(n1), get_irn_idx(n2));
282 static int cmp_rss_edges(const void *a, const void *b)
284 const rss_edge_t *e1 = (const rss_edge_t*)a;
285 const rss_edge_t *e2 = (const rss_edge_t*)b;
287 return (e1->src != e2->src) || (e1->tgt != e2->tgt);
290 static int bsearch_for_index(int key, int *arr, size_t len, int force)
295 while (right >= left) {
296 int idx = (left + right) / 2;
300 else if (key > arr[idx])
307 assert(0 && "Something is wrong, key not found.");
311 static const ir_node **build_sorted_array_from_list(plist_t *irn_list, struct obstack *obst)
315 int len = plist_count(irn_list);
316 const ir_node **arr = (const ir_node**)NEW_ARR_D(ir_node*, obst, len);
318 /* copy the list into the array */
319 foreach_plist(irn_list, el) {
320 arr[i++] = (ir_node*)plist_element_get_value(el);
323 /* sort the array by node index */
324 /* HACK cast for MSVC */
325 qsort((void*)arr, len, sizeof(arr[0]), cmp_irn_idx);
330 /*****************************************************
333 * __| | ___| |__ _ _ __ _ __ _ _ _ __ __ _
334 * / _` |/ _ \ '_ \| | | |/ _` |/ _` | | '_ \ / _` |
335 * | (_| | __/ |_) | |_| | (_| | (_| | | | | | (_| |
336 * \__,_|\___|_.__/ \__,_|\__, |\__, |_|_| |_|\__, |
340 *****************************************************/
343 static void dump_nodeset(ir_nodeset_t *ns, const char *prefix)
345 ir_nodeset_iterator_t iter;
348 ir_nodeset_iterator_init(&iter, ns);
349 while ( (irn = ir_nodeset_iterator_next(&iter)) != NULL ) {
350 ir_fprintf(stderr, "%s%+F\n", prefix, irn);
355 static void build_file_name(rss_t *rss, const char *suffix, size_t suf_len, char *buf, size_t len)
357 const char *irg_name;
360 irg_name = get_entity_name(get_irg_entity(rss->irg));
361 snprintf(buf, len - suf_len, "%s-%s-block-%ld",
362 irg_name, arch_register_class_name(rss->cls), get_irn_node_nr(rss->block));
366 /* Dumps all collected bipartite components of current irg as vcg. */
367 static void debug_vcg_dump_bipartite(rss_t *rss)
372 static const char suffix[] = "-RSS-CBC.vcg";
374 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
375 f = fopen(file_name, "w");
377 ir_fprintf(f, "graph: { title: \"connected bipartite component graph of %+F\"\n", rss->irg);
378 fprintf(f, "display_edge_labels: no\n");
379 fprintf(f, "layoutalgorithm: mindepth\n");
380 fprintf(f, "manhattan_edges: yes\n\n");
382 foreach_pset(rss->cbc_set, cbc_t*, cbc) {
383 ir_nodeset_iterator_t iter;
387 fprintf(f, "graph: { titel: \"cbc %d\" label: \"cbc %d\" status:clustered color:yellow\n", cbc->nr, cbc->nr);
388 foreach_ir_nodeset(&cbc->parents, n, iter) {
389 ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
391 foreach_ir_nodeset(&cbc->children, n, iter) {
392 ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
394 foreach_pset(cbc->kill_edges, rss_edge_t*, ke) {
395 ir_fprintf(f, "edge: { sourcename: \"n%d_%d\" targetname: \"n%d_%d\" }\n",
396 get_irn_node_nr(ke->src), cbc->nr, get_irn_node_nr(ke->tgt), cbc->nr);
404 /* Dump the computed killing function as vcg. */
405 static void debug_vcg_dump_kill(rss_t *rss)
410 static const char suffix[] = "-RSS-KILL.vcg";
412 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
413 f = fopen(file_name, "w");
415 ir_fprintf(f, "graph: { title: \"computed kill graph of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
416 fprintf(f, "display_edge_labels: no\n");
417 fprintf(f, "layoutalgorithm: mindepth\n");
418 fprintf(f, "manhattan_edges: yes\n\n");
421 /* reset dump_flag */
423 foreach_phase_irn(&rss->ph, irn) {
424 rss_irn_t *node = get_rss_irn(rss, irn);
429 /* dump all nodes and their killers */
430 foreach_plist(rss->nodes, el) {
431 ir_node *irn = (ir_node *)plist_element_get_value(el);
432 rss_irn_t *rirn = get_rss_irn(rss, irn);
433 rss_irn_t *pk_rirn = get_rss_irn(rss, rirn->killer);
435 if (! rirn->dumped) {
436 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
440 if (! pk_rirn->dumped) {
441 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(rirn->killer), rirn->killer);
445 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
446 get_irn_node_nr(rirn->killer), get_irn_node_nr(irn));
453 /* Dumps the potential killing DAG (PKG) as vcg. */
454 static void debug_vcg_dump_pkg(rss_t *rss, ir_nodeset_t *max_ac, int iteration)
459 static const char suffix1[] = "-RSS-PKG.vcg";
460 static const char suffix2[] = "-RSS-PKG-MAXAC.vcg";
464 snprintf(suffix, sizeof(suffix), "%s", suffix1);
467 snprintf(suffix, sizeof(suffix), "-%02d%s", iteration, suffix2);
470 build_file_name(rss, suffix, strlen(suffix) + 1, file_name, sizeof(file_name));
471 f = fopen(file_name, "w");
473 ir_fprintf(f, "graph: { title: \"potential killing DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
474 fprintf(f, "display_edge_labels: no\n");
475 fprintf(f, "layoutalgorithm: mindepth\n");
476 fprintf(f, "manhattan_edges: yes\n\n");
479 /* reset dump_flag */
481 foreach_phase_irn(&rss->ph, irn) {
482 rss_irn_t *node = get_rss_irn(rss, irn);
487 foreach_plist(rss->nodes, el) {
488 ir_node *irn = (ir_node *)plist_element_get_value(el);
489 rss_irn_t *rirn = get_rss_irn(rss, irn);
491 plist_element_t *k_el;
493 /* dump selected saturating values in yellow */
494 if (max_ac && ir_nodeset_contains(max_ac, irn))
497 if (! rirn->dumped) {
499 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(irn), irn, rirn->chain->nr, c1);
501 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(irn), irn, c1);
505 foreach_plist(rirn->pkiller_list, k_el) {
506 ir_node *pkiller = (ir_node *)plist_element_get_value(k_el);
507 rss_irn_t *pk_rirn = get_rss_irn(rss, pkiller);
510 if (max_ac && ir_nodeset_contains(max_ac, pkiller))
513 if (! pk_rirn->dumped) {
515 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(pkiller), pkiller, pk_rirn->chain->nr, c2);
517 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(pkiller), pkiller, c2);
520 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
521 get_irn_node_nr(pkiller), get_irn_node_nr(irn));
528 /* Dumps the disjoint value DAG (DVG) as vcg. */
529 static void debug_vcg_dump_dvg(rss_t *rss, dvg_t *dvg)
531 static const char suffix[] = "-RSS-DVG.vcg";
534 ir_nodeset_iterator_t iter;
538 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
539 f = fopen(file_name, "w");
541 ir_fprintf(f, "graph: { title: \"disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
542 fprintf(f, "display_edge_labels: no\n");
543 fprintf(f, "layoutalgorithm: mindepth\n");
544 fprintf(f, "manhattan_edges: yes\n\n");
547 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
548 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
552 foreach_pset(dvg->edges, rss_edge_t*, edge) {
553 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
554 get_irn_node_nr(edge->src), get_irn_node_nr(edge->tgt));
562 /* Dumps the PKG(DVG). */
563 static void debug_vcg_dump_dvg_pkiller(rss_t *rss, dvg_t *dvg)
565 static const char suffix[] = "-RSS-DVG-PKG.vcg";
568 ir_nodeset_iterator_t iter;
571 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
572 f = fopen(file_name, "w");
574 ir_fprintf(f, "graph: { title: \"PKG of disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
575 fprintf(f, "display_edge_labels: no\n");
576 fprintf(f, "layoutalgorithm: mindepth\n");
577 fprintf(f, "manhattan_edges: yes\n\n");
580 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
581 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
585 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
586 rss_irn_t *node = get_rss_irn(rss, irn);
589 foreach_plist(node->dvg_pkiller_list, el) {
590 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
591 get_irn_node_nr(plist_element_get_value(el)), get_irn_node_nr(irn));
601 * In case there is no rss information for irn, initialize it.
603 static void *init_rss_irn(ir_phase *ph, const ir_node *irn)
605 rss_irn_t *res = (rss_irn_t*)phase_alloc(ph, sizeof(res[0]));
607 res->descendant_list = plist_obstack_new(phase_obst(ph));
608 res->descendants = NULL;
610 res->consumer_list = plist_obstack_new(phase_obst(ph));
611 res->consumer = NULL;
613 res->pkiller_list = plist_obstack_new(phase_obst(ph));
615 res->parent_list = plist_obstack_new(phase_obst(ph));
633 * Collect all nodes data dependent on current node.
635 static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int *got_sink, unsigned cur_desc_walk)
637 const ir_edge_t *edge;
638 rss_irn_t *cur_node = get_rss_irn(rss, irn);
639 ir_node *block = rss->block;
640 ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
643 if (cur_node->desc_walk >= cur_desc_walk)
645 cur_node->desc_walk = cur_desc_walk;
647 /* Stop at Barriers */
648 if (be_is_Barrier(irn))
651 /* loop over normal and dependency edges */
652 for (i = 0; i < 2; ++i) {
653 foreach_out_edge_kind(irn, edge, ekind[i]) {
654 ir_node *user = get_edge_src_irn(edge);
656 /* skip ignore nodes as they do not really contribute to register pressure */
657 if (arch_irn_is_ignore(user))
661 (a) mode_X means Jump -> out_edge
662 (b) Phi as user of a normal node -> out-edge
664 if (get_irn_mode(user) == mode_X || is_Phi(user)) {
672 //if (arch_get_irn_reg_class_out(user) == rss->cls)
673 collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
676 /* check if user lives in block and is not a control flow node */
677 if (get_nodes_block(user) == block) {
678 if (! plist_has_value(rirn->descendant_list, user)) {
679 plist_insert_back(rirn->descendant_list, user);
680 DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", user));
682 collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
684 else if (! *got_sink) {
686 /* user lives out of block: add sink as descendant if not already done */
687 plist_insert_back(rirn->descendant_list, _sink);
689 DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", _sink));
697 * Handles a single consumer.
699 static void collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *consumer, int *got_sink)
701 ir_node *block = rss->block;
703 assert(! is_Proj(consumer) && "Cannot handle Projs");
705 if (! is_Phi(consumer) && ! is_Block(consumer) && get_nodes_block(consumer) == block) {
706 if (!arch_irn_is_ignore(consumer) &&
707 !plist_has_value(rss_irn->consumer_list, consumer)) {
708 plist_insert_back(rss_irn->consumer_list, consumer);
709 DBG((rss->dbg, LEVEL_2, "\t\tconsumer %+F\n", consumer));
713 rss_irn->live_out = 1;
714 DBG((rss->dbg, LEVEL_2, "\t\tlive out %+F", consumer));
716 plist_insert_back(rss_irn->consumer_list, _sink);
718 DB((rss->dbg, LEVEL_2, ", %+F added instead", _sink));
720 DB((rss->dbg, LEVEL_2, "\n"));
725 * Collect all nodes consuming the value(s) produced by current node.
727 static void collect_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *irn, int *got_sink)
729 const ir_edge_t *edge;
731 ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
732 rss_irn_t *cur_node = get_rss_irn(rss, irn);
734 if (cur_node->havecons)
736 cur_node->havecons = 1;
738 for (i = 0; i < 2; ++i) {
739 foreach_out_edge_kind(irn, edge, ekind[i]) {
740 ir_node *consumer = get_edge_src_irn(edge);
742 if (is_Proj(consumer)) {
743 //if (arch_get_irn_reg_class_out(consumer) == rss->cls)
744 collect_consumer(rss, rss_irn, consumer, got_sink);
747 collect_single_consumer(rss, rss_irn, consumer, got_sink);
753 * Collects all consumer and descendant of a irn.
755 static void collect_node_info(rss_t *rss, ir_node *irn)
757 static unsigned cur_desc_walk = 0;
758 rss_irn_t *rss_irn = get_rss_irn(rss, irn);
761 assert(! is_Proj(irn) && "Cannot handle Projs.");
763 /* check if node info is already available */
764 if (rss_irn->handled)
767 DBG((rss->dbg, LEVEL_1, "\tcomputing consumers of %+F:\n", irn));
769 /* collect all consumer */
771 collect_consumer(rss, rss_irn, irn, &got_sink);
773 /* build sorted consumer array */
774 rss_irn->consumer = build_sorted_array_from_list(rss_irn->consumer_list, phase_obst(&rss->ph));
776 DBG((rss->dbg, LEVEL_1, "\tcompute descendants of %+F:\n", irn));
778 /* collect descendants */
780 collect_descendants(rss, rss_irn, irn, &got_sink, ++cur_desc_walk);
782 /* build sorted descendant array */
783 rss_irn->descendants = build_sorted_array_from_list(rss_irn->descendant_list, phase_obst(&rss->ph));
785 rss_irn->handled = 1;
789 * Checks if v is a potential killer of u.
790 * v is in pkill(u) iff descendants(v) cut consumer(u) is v
792 * @param rss The rss object
793 * @param v The node to check for killer
794 * @param u The potentially killed value
795 * @return 1 if v is in pkill(u), 0 otherwise
797 static int is_potential_killer(rss_t *rss, rss_irn_t *v, rss_irn_t *u)
804 /* as we loop over the list: loop over the shorter one */
805 if (plist_count(v->descendant_list) > plist_count(u->consumer_list)) {
806 list = u->consumer_list;
807 arr = v->descendants;
810 list = v->descendant_list;
814 /* for each list element: try to find element in array */
815 foreach_plist(list, el) {
816 ir_node *irn = (ir_node*)plist_element_get_value(el);
817 ir_node *match = (ir_node*)BSEARCH_IRN_ARR(irn, arr);
819 if (match && match != irn)
827 * Update descendants, consumer and pkiller list for the given irn.
829 static void update_node_info(rss_t *rss, ir_node *irn, ir_node *pk_irn)
831 rss_irn_t *node = get_rss_irn(rss, irn);
832 rss_irn_t *pkiller = get_rss_irn(rss, pk_irn);
834 /* add consumer and rebuild the consumer array */
835 if (! plist_has_value(node->consumer_list, pk_irn)) {
836 plist_insert_back(node->consumer_list, pk_irn);
837 node->consumer = build_sorted_array_from_list(node->consumer_list, phase_obst(&rss->ph));
840 /* add pk_irn as descendant, add it's descendants to irn's and rebuild array */
841 if (! plist_has_value(node->descendant_list, pk_irn)) {
844 plist_insert_back(node->descendant_list, pk_irn);
846 foreach_plist(pkiller->descendant_list, el) {
847 ir_node *desc = (ir_node*)plist_element_get_value(el);
849 if (! plist_has_value(node->descendant_list, desc))
850 plist_insert_back(node->descendant_list, desc);
853 node->descendants = build_sorted_array_from_list(node->descendant_list, phase_obst(&rss->ph));
859 * Compute the potential killing set PK.
861 static void compute_pkill_set(rss_t *rss)
863 plist_element_t *u_el, *v_el;
865 foreach_plist(rss->nodes, u_el) {
866 ir_node *u_irn = (ir_node*)plist_element_get_value(u_el);
867 rss_irn_t *u = get_rss_irn(rss, u_irn);
869 DBG((rss->dbg, LEVEL_1, "\tcomputing potential killers of %+F:\n", u_irn));
871 /* check each consumer if it is a potential killer */
872 foreach_plist(u->consumer_list, v_el) {
873 ir_node *v_irn = (ir_node*)plist_element_get_value(v_el);
874 rss_irn_t *v = get_rss_irn(rss, v_irn);
876 /* check, if v is a potential killer of u */
877 if (is_potential_killer(rss, v, u)) {
878 if (! plist_has_value(u->pkiller_list, v_irn))
879 plist_insert_back(u->pkiller_list, v_irn);
881 DBG((rss->dbg, LEVEL_2, "\t\tpotential killer %+F\n", v_irn));
888 if (rss->opts->dump_flags & RSS_DUMP_PKG)
889 debug_vcg_dump_pkg(rss, NULL, 0);
893 * Build set of killing edges (from values to their potential killers)
895 static void build_kill_edges(rss_t *rss, pset *epk)
897 plist_element_t *el, *k_el;
899 foreach_plist(rss->nodes, el) {
900 ir_node *irn = (ir_node*)plist_element_get_value(el);
901 rss_irn_t *rirn = get_rss_irn(rss, irn);
903 DBG((rss->dbg, LEVEL_3, "\t\tbuilding kill edges for %+F:\n", irn));
905 foreach_plist(rirn->pkiller_list, k_el) {
906 ir_node *pkiller = (ir_node*)plist_element_get_value(k_el);
907 rss_edge_t *ke = OALLOC(phase_obst(&rss->ph), rss_edge_t);
913 DBG((rss->dbg, LEVEL_3, "\t\t\ttarget %+F\n", pkiller));
915 pset_insert(epk, ke, HASH_RSS_EDGE(ke));
921 /* print the given cbc for debugging purpose */
922 static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc)
924 ir_nodeset_iterator_t iter;
928 DBG((mod, LEVEL_3, "\t\tS = set of parents:\n"));
929 foreach_ir_nodeset(&cbc->parents, n, iter) {
930 DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
932 DBG((mod, LEVEL_3, "\t\tT = set of children:\n"));
933 foreach_ir_nodeset(&cbc->children, n, iter) {
934 DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
936 DBG((mod, LEVEL_3, "\t\tE = Edges from producers to consumers\n"));
937 foreach_pset(cbc->kill_edges, rss_edge_t*, ke) {
938 DBG((mod, LEVEL_3, "\t\t\t%+F -> %+F\n", ke->src, ke->tgt));
944 * Construct the bipartite decomposition.
945 * Sid-Ahmed-Ali Touati, Phd Thesis
946 * Register Pressure in Instruction Level Parallelism, p. 71
948 static void compute_bipartite_decomposition(rss_t *rss)
950 pset *epk = new_pset(cmp_rss_edges, 10);
955 DBG((rss->dbg, LEVEL_1, "\tcomputing bipartite decomposition:\n"));
957 build_kill_edges(rss, epk);
959 foreach_plist(rss->nodes, el) {
960 ir_node *u_irn = (ir_node*)plist_element_get_value(el);
961 rss_irn_t *u = get_rss_irn(rss, u_irn);
967 plist_element_t *el2;
969 rss_edge_t *kedge_root = NULL;
970 ir_node *t_irn, *s_irn;
971 ir_nodeset_iterator_t iter;
973 if (u->visited || u_irn == _sink)
976 DBG((rss->dbg, LEVEL_2, "\t\t%+F choosen:\n", u_irn));
978 cbc = OALLOC(phase_obst(&rss->ph), cbc_t);
981 /* initialize S_cb */
982 ir_nodeset_init_size(&cbc->parents, 5);
983 ir_nodeset_insert(&cbc->parents, u_irn);
984 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (init)\n", u_irn));
987 cbc->kill_edges = new_pset(cmp_rss_edges, 5);
989 /* each parent gets killed by at least one value from children */
991 /* T_cb = PK_successors(u) */
992 ir_nodeset_init_size(&cbc->children, 5);
993 foreach_plist(u->pkiller_list, el2) {
994 ir_nodeset_insert(&cbc->children, (ir_node*)plist_element_get_value(el2));
995 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (init)\n", plist_element_get_value(el2)));
999 Now: insert the parents of all children into the parent set
1000 and insert the children of all parents into the children set
1001 until the sets don't change any more
1003 while (p_change || c_change) {
1004 ir_nodeset_iterator_t iter;
1005 p_change = c_change = 0;
1007 /* accumulate parents */
1008 foreach_ir_nodeset(&cbc->children, t_irn, iter) {
1009 foreach_pset(epk, rss_edge_t*, k_edge) {
1010 ir_node *val = k_edge->src;
1012 if (k_edge->tgt == t_irn && ! ir_nodeset_contains(&cbc->parents, val)) {
1013 ir_nodeset_insert(&cbc->parents, val);
1015 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (killed by %+F)\n", val, t_irn));
1020 /* accumulate children */
1021 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
1022 foreach_pset(epk, rss_edge_t*, k_edge) {
1023 ir_node *val = k_edge->tgt;
1025 if (k_edge->src == s_irn && ! ir_nodeset_contains(&cbc->children, val)) {
1026 ir_nodeset_insert(&cbc->children, val);
1028 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (kills %+F)\n", val, s_irn));
1034 /* mark all parent values as visited */
1035 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
1036 rss_irn_t *s = get_rss_irn(rss, s_irn);
1038 /* assure bipartite property */
1040 if (ir_nodeset_contains(&cbc->children, s_irn)) {
1041 ir_nodeset_remove(&cbc->children, s_irn);
1042 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F removed from to children\n", s_irn));
1048 foreach_pset(epk, rss_edge_t*, k_edge) {
1049 if (ir_nodeset_contains(&cbc->parents, k_edge->src) &&
1050 ir_nodeset_contains(&cbc->children, k_edge->tgt)) {
1051 pset_insert(cbc->kill_edges, k_edge, HASH_RSS_EDGE(k_edge));
1053 Link all k_edges which are about to be removed together.
1054 Beware: pset_remove kills the iterator.
1056 k_edge->next = kedge_root;
1057 kedge_root = k_edge;
1061 /* remove all linked k_edges */
1062 for (; kedge_root; kedge_root = (rss_edge_t*)kedge_root->next) {
1063 pset_remove(epk, kedge_root, HASH_RSS_EDGE(kedge_root));
1066 /* verify the cbc */
1067 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
1070 foreach_pset(cbc->kill_edges, rss_edge_t*, k_edge) {
1071 if (k_edge->src == s_irn) {
1073 pset_break(cbc->kill_edges);
1080 ir_fprintf(stderr, "Warning: parent %+F is not killed in current cbc\n", s_irn);
1083 assert(vrfy_ok && "Verification of CBC failed");
1085 /* add the connected bipartite component */
1086 if (ir_nodeset_size(&cbc->parents) > 0 &&
1087 ir_nodeset_size(&cbc->children) > 0 &&
1088 pset_count(cbc->kill_edges) > 0)
1089 pset_insert(rss->cbc_set, cbc, (unsigned)cbc->nr);
1090 DBG((rss->dbg, LEVEL_2, "\tbipartite component %d inserted:\n", cbc->nr));
1092 if (firm_dbg_get_mask(rss->dbg) & LEVEL_2)
1093 debug_print_cbc(rss->dbg, cbc);
1097 if (rss->opts->dump_flags & RSS_DUMP_CBC)
1098 debug_vcg_dump_bipartite(rss);
1104 * Select the child with the maximum cost.
1106 static child_t *select_child_max_cost(rss_t *rss, ir_nodeset_t *x, ir_nodeset_t *y, child_t *t, cbc_t *cbc)
1109 ir_nodeset_iterator_t iter;
1110 float max_cost = -1.0f;
1112 DBG((rss->dbg, LEVEL_2, "\t\tcomputing children costs:\n"));
1114 foreach_ir_nodeset(&cbc->children, child, iter) {
1115 rss_irn_t *r_child = get_rss_irn(rss, child);
1116 int num_unkilled_parents = 0;
1117 int num_descendants;
1121 /* get the number of unkilled parents */
1122 foreach_pset(cbc->kill_edges, rss_edge_t*, k_edge) {
1123 if (k_edge->tgt == child && ir_nodeset_contains(x, k_edge->src))
1124 ++num_unkilled_parents;
1127 cost = (float)num_unkilled_parents;
1129 num_descendants = plist_count(r_child->descendant_list) + ir_nodeset_size(y);
1131 if (num_descendants > 0)
1132 cost /= (float)num_descendants;
1134 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F, #desc %d, cost %.3f\n", child, num_descendants, cost));
1136 if (cost > max_cost) {
1147 * Remove all parents from x which are killed by t_irn.
1149 static void remove_covered_parents(rss_t *rss, ir_nodeset_t *x, ir_node *t_irn, cbc_t *cbc)
1151 rss_irn_t *t = get_rss_irn(rss, t_irn);
1154 DBG((rss->dbg, LEVEL_2, "\t\tremoving parents covered by %+F:\n", t_irn));
1156 foreach_pset(cbc->kill_edges, rss_edge_t*, k_edge) {
1157 if (k_edge->tgt == t_irn && ir_nodeset_contains(x, k_edge->src)) {
1158 ir_nodeset_remove(x, k_edge->src);
1159 plist_insert_back(t->parent_list, k_edge->src);
1160 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", k_edge->src));
1165 static void update_cumulated_descendent_values(rss_t *rss, ir_nodeset_t *y, ir_node *t_irn)
1167 rss_irn_t *t = get_rss_irn(rss, t_irn);
1168 plist_element_t *el;
1170 DBG((rss->dbg, LEVEL_2, "\t\tupdating cumulated descendant value of %+F:\n", t_irn));
1172 foreach_plist(t->descendant_list, el) {
1173 ir_nodeset_insert(y, (ir_node*)plist_element_get_value(el));
1174 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", plist_element_get_value(el)));
1179 * Greedy-k: a heuristics for the MMA problem
1181 static void compute_killing_function(rss_t *rss)
1184 struct obstack obst;
1186 obstack_init(&obst);
1188 rss->cbc_set = pset_new_ptr(5);
1189 compute_bipartite_decomposition(rss);
1191 /* for all bipartite components do: */
1192 foreach_pset(rss->cbc_set, cbc_t*, cbc) {
1196 ir_nodeset_iterator_t iter;
1197 child_t **sks = NEW_ARR_F(child_t *, 20);
1202 ir_nodeset_init_size(&x, 10);
1203 ir_nodeset_init_size(&y, 10);
1205 DBG((rss->dbg, LEVEL_1, "\tcomputing SKS for cbc %d:\n", cbc->nr));
1206 DBG((rss->dbg, LEVEL_2, "\t\tinitializing parents X:\n"));
1208 /* X = S_cb (all parents are initially uncovered) */
1209 foreach_ir_nodeset(&cbc->parents, p, iter) {
1210 ir_nodeset_insert(&x, p);
1211 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", p));
1214 /* while X not empty */
1215 while (ir_nodeset_size(&x) > 0) {
1216 child_t *t = OALLOCZ(&obst, child_t);
1218 t = select_child_max_cost(rss, &x, &y, t, cbc);
1220 if (cur_len >= cur_size) {
1221 ARR_EXTO(child_t *, sks, cur_size * 2);
1225 DBG((rss->dbg, LEVEL_2, "\t\tinsert child %+F (%.3f) into SKS at pos %d\n", t->irn, t->cost, cur_len));
1228 remove_covered_parents(rss, &x, t->irn, cbc);
1229 update_cumulated_descendent_values(rss, &y, t->irn);
1232 ARR_SHRINKLEN(sks, cur_len);
1234 /* sort SKS in increasing cost order */
1235 qsort(sks, cur_len, sizeof(sks[0]), cmp_child_costs);
1237 DBG((rss->dbg, LEVEL_2, "\tprocessing SKS for cbc %d:\n", cbc->nr));
1239 /* build killing function */
1240 for (i = cur_len - 1; i >= 0; --i) { /* loop over sks in decreasing cost order */
1241 child_t *t = sks[i];
1242 rss_irn_t *rt = get_rss_irn(rss, t->irn);
1243 plist_element_t *p_el;
1245 DBG((rss->dbg, LEVEL_3, "\t\t\tkiller %+F (%.3f):\n", t->irn, t->cost));
1247 /* kill all unkilled parents of t */
1248 foreach_plist(rt->parent_list, p_el) {
1249 ir_node *par = (ir_node*)plist_element_get_value(p_el);
1250 rss_irn_t *rpar = get_rss_irn(rss, par);
1252 if (is_Sink(rpar->killer)) {
1253 rpar->killer = t->irn;
1254 DBG((rss->dbg, LEVEL_2, "\t\tkill %+F\n", rpar->irn));
1257 DBG((rss->dbg, LEVEL_3, "\t\t\tkeeping %+F as killer for %+F\n", rpar->killer, rpar->irn));
1262 ir_nodeset_destroy(&x);
1263 ir_nodeset_destroy(&y);
1267 if (rss->opts->dump_flags & RSS_DUMP_KILL)
1268 debug_vcg_dump_kill(rss);
1270 del_pset(rss->cbc_set);
1271 obstack_free(&obst, NULL);
1275 * Adds the edge src -> tgt to the dvg. Checks if reverse edge is already there (asserts).
1277 static inline void add_dvg_edge(rss_t *rss, dvg_t *dvg, const ir_node *src, const ir_node *tgt, int have_source)
1279 rss_edge_t *dvg_edge;
1283 ir_nodeset_insert(&dvg->nodes, (ir_node *) src);
1285 assert(ir_nodeset_contains(&dvg->nodes, src) && "Wrong assumption");
1287 ir_nodeset_insert(&dvg->nodes, (ir_node *) tgt);
1289 key.src = (ir_node *) tgt;
1290 key.tgt = (ir_node *) src;
1291 assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
1293 key.src = (ir_node *) src;
1294 key.tgt = (ir_node *) tgt;
1295 if (NULL != pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
1296 /* add the edge to the DVG */
1297 dvg_edge = OALLOC(phase_obst(&rss->ph), rss_edge_t);
1299 dvg_edge->src = (ir_node *) src;
1300 dvg_edge->tgt = (ir_node *) tgt;
1301 dvg_edge->next = NULL;
1303 DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", src, tgt));
1304 pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
1309 * Computes the disjoint value DAG (DVG).
1310 * BEWARE: It is not made explicitly clear in the Touati paper,
1311 * but the DVG is meant to be build from the KILLING DAG
1313 static void compute_dvg(rss_t *rss, dvg_t *dvg)
1315 plist_element_t *el;
1317 DBG((rss->dbg, LEVEL_1, "\tcomputing DVG:\n"));
1319 foreach_plist(rss->nodes, el) {
1320 ir_node *u_irn = (ir_node*)plist_element_get_value(el);
1321 rss_irn_t *u = get_rss_irn(rss, u_irn);
1322 rss_irn_t *u_killer = get_rss_irn(rss, u->killer);
1325 /* TODO: omit nodes only having sink as pkiller and killing no one */
1327 /* add an edge to killer */
1328 add_dvg_edge(rss, dvg, u_irn, u->killer, 0);
1330 if (is_Sink(u->killer))
1333 /* We add an edge to every killer, from where we could be reached. */
1334 for (i = ARR_LEN_SAFE(u_killer->descendants) - 1; i >= 0; --i) {
1335 add_dvg_edge(rss, dvg, u_irn, u_killer->descendants[i], 1);
1340 foreach_plist(rss->nodes, el2) {
1341 ir_node *v_irn = plist_element_get_value(el2);
1344 There is an edge (u, v) in the DVG iff v is a descendant of the killer(u).
1346 if (BSEARCH_IRN_ARR(v_irn, u_kill->descendants)) {
1347 rss_edge_t *dvg_edge = OALLOC(phase_obst(&rss->ph), rss_edge_t);
1350 /* insert the user into the DVG and append it to the user list of u */
1351 ir_nodeset_insert(&dvg->nodes, v_irn);
1352 if (! plist_has_value(u->dvg_user_list, v_irn))
1353 plist_insert_back(u->dvg_user_list, v_irn);
1355 dvg_edge->src = u_irn;
1356 dvg_edge->tgt = v_irn;
1357 dvg_edge->next = NULL;
1362 assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
1364 /* add the edge to the DVG */
1365 DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", u_irn, v_irn));
1366 pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
1372 if (rss->opts->dump_flags & RSS_DUMP_DVG)
1373 debug_vcg_dump_dvg(rss, dvg);
1377 * Updates the dvg structure when a serialization edge from src -> tgt is added.
1379 static void update_dvg(rss_t *rss, dvg_t *dvg, rss_irn_t *src, rss_irn_t *tgt)
1383 rss_edge_t **arr = ALLOCAN(rss_edge_t*, pset_count(dvg->edges));
1386 Add an edge from serialization target to serialization src:
1387 src cannot be alive with target
1389 add_dvg_edge(rss, dvg, tgt->irn, src->irn, 0);
1391 /* Add edges to src's descendants as well, they also getting serialized. */
1392 for (i = ARR_LEN_SAFE(src->descendants) - 1; i >= 0; --i) {
1393 add_dvg_edge(rss, dvg, tgt->irn, src->descendants[i], 1);
1396 /* We also have to add edges from targets predecessors in dvg */
1398 /* We cannot insert elements into set over which we iterate ... */
1399 foreach_pset(dvg->edges, rss_edge_t*, edge) {
1400 if (edge->tgt == tgt->irn) {
1405 for (i = 0; i < idx; ++i) {
1407 add_dvg_edge(rss, dvg, edge->src, src->irn, 1);
1408 for (j = ARR_LEN_SAFE(src->descendants) - 1; j >= 0; --j) {
1409 add_dvg_edge(rss, dvg, edge->src, src->descendants[j], 1);
1416 * Accumulate all descendants for root into list.
1418 static void accumulate_dvg_descendant_values(rss_t *rss, rss_irn_t *root, plist_t *list)
1420 if (plist_count(root->dvg_user_list) > 0) {
1421 plist_element_t *el;
1423 foreach_plist(root->dvg_user_list, el) {
1424 ir_node *v_irn = plist_element_get_value(el);
1425 rss_irn_t *v = get_rss_irn(rss, v_irn);
1427 /* add v as descendant */
1428 if (! plist_has_value(list, v_irn)) {
1429 plist_insert_back(list, v_irn);
1430 DBG((rss->dbg, DEBUG_DVG, "\t\t\tadd DVG descendant %+F\n", v_irn));
1433 /* accumulate v's descendants */
1434 accumulate_dvg_descendant_values(rss, v, list);
1440 * Builds the list of potential killers for each node
1442 * Needs the descendant list for all user as sorted array.
1444 static void build_dvg_pkiller_list(rss_t *rss, dvg_t *dvg)
1446 ir_nodeset_iterator_t iter;
1449 foreach_nodeset(&dvg->nodes, irn, iter) {
1450 rss_irn_t *node = get_rss_irn(rss, irn);
1451 plist_element_t *el, *el2;
1453 DBG((rss->dbg, DEBUG_DVG, "\t\tbuilding pkiller list for %+F\n", irn));
1455 /* check each user */
1456 foreach_plist(node->dvg_user_list, el) {
1457 ir_node *u_irn = plist_element_get_value(el);
1459 /* is the current user u_irn not a descendant of any other user -> pkiller */
1460 foreach_plist(node->dvg_user_list, el2) {
1461 ir_node *v_irn = plist_element_get_value(el2);
1462 rss_irn_t *v = get_rss_irn(rss, v_irn);
1465 ! BSEARCH_IRN_ARR(u_irn, v->dvg_desc) &&
1466 ! plist_has_value(node->dvg_pkiller_list, u_irn))
1468 plist_insert_back(node->dvg_pkiller_list, u_irn);
1469 DBG((rss->dbg, DEBUG_DVG, "\t\t\tadd DVG pkiller %+F\n", u_irn));
1474 node->dvg_pkiller = build_sorted_array_from_list(node->dvg_pkiller_list, phase_obst(&rss->ph));
1478 if (firm_dbg_get_mask(rss->dbg) & DEBUG_DVG)
1479 debug_vcg_dump_dvg_pkiller(rss, dvg);
1486 * Compute the maximal antichain of the current DVG.
1487 * This is a reimplementation of the MAXIMAL_ANTI_CHAIN function
1488 * from the DDG library 1.1 (DAG.cpp).
1490 static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration)
1492 unsigned n = ir_nodeset_size(&dvg->nodes);
1493 unsigned *assignment = ALLOCAN(unsigned, n);
1494 unsigned *assignment_rev = ALLOCAN(unsigned, n);
1495 int *idx_map = ALLOCAN(int, n);
1496 hungarian_problem_t *bp;
1497 ir_nodeset_t *values, *temp;
1498 ir_nodeset_iterator_t iter;
1503 rss_edge_t *dvg_edge;
1505 #define MAP_IDX(irn) bsearch_for_index(get_irn_idx(irn), idx_map, n, 1)
1507 if (pset_count(dvg->edges) == 0)
1510 bp = hungarian_new(n, n, HUNGARIAN_MATCH_NORMAL);
1513 At first, we build an index map for the nodes in the DVG,
1514 because we cannot use the irn idx therefore as the resulting
1515 bipartite data structure would have around 1.2GB.
1516 So we limit the size to the number of nodes we have in the DVG
1517 and build a sorted index map for their irn indices.
1520 foreach_ir_nodeset(&dvg->nodes, u_irn, iter) {
1521 idx_map[i++] = get_irn_idx(u_irn);
1523 qsort(idx_map, n, sizeof(idx_map[0]), cmp_int);
1525 foreach_pset(dvg->edges, rss_edge_t*, dvg_edge) {
1526 int idx_u = MAP_IDX(dvg_edge->src);
1527 int idx_v = MAP_IDX(dvg_edge->tgt);
1529 /* add the entry to the bipartite data structure */
1530 hungarian_add(bp, idx_u, idx_v, 1);
1531 DBG((rss->dbg, LEVEL_3, "\t\t\tadd %d (%+F) -> %d (%+F)\n",
1532 idx_u, dvg_edge->src, idx_v, dvg_edge->tgt));
1536 Add a bipartite entry for each pair of nodes (u, v), where exists a
1537 path in the DVG from u to v, ie. connect all descendants(v) to v.
1538 desc_dvg(v) = accumulated descendants of all z in dvg_user_list(v)
1540 foreach_ir_nodeset(&dvg->nodes, u_irn, iter) {
1541 rss_irn_t *u = get_rss_irn(rss, u_irn);
1542 int idx_u_irn = MAP_IDX(u_irn);
1544 DBG((rss->dbg, DEBUG_DVG, "\t\tcomputing DVG descendants of %+F:\n", u_irn));
1546 //plist_clear(u->dvg_desc_list);
1547 //accumulate_dvg_descendant_values(rss, u, u->dvg_desc_list);
1550 FIXME: The array is build on the phase obstack and we cannot free the data.
1551 So the array get as many times allocated as this function is called.
1554 /* build the sorted array for faster searches */
1555 //u->dvg_desc = build_sorted_array_from_list(u->dvg_desc_list, phase_obst(&rss->ph));
1557 DBG((rss->dbg, DEBUG_MAX_AC, "\t\tadding bipartite entries of %+F:\n", u_irn));
1559 /* add the bipartite entries for all descendants */
1560 for (i = ARR_LEN_SAFE(u->dvg_desc) - 1; i >= 0; --i) {
1561 rss_irn_t *desc = get_rss_irn(rss, u->dvg_desc[i]);
1562 int idx_desc = MAP_IDX(u->dvg_desc[i]);
1564 /* add the entry to the bipartite data structure */
1565 hungarian_add(bp, idx_u_irn, idx_desc, 1);
1566 DBG((rss->dbg, DEBUG_MAX_AC, "\t\t\tadd %d (%+F) -> %d (%+F)\n",
1567 idx_u_irn, u_irn, idx_desc, u->dvg_desc[i]));
1574 /* We want maximum cardinality matching */
1575 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
1578 DBG((rss->dbg, DEBUG_DVG, "\t\tcomputing DVG pkiller:\n"));
1579 /* beware: the following function needs the dvg_desc array */
1580 build_dvg_pkiller_list(rss, dvg);
1583 DBG((rss->dbg, LEVEL_2, "\t\tcomputing bipartite matching\n"));
1585 The maximum cardinality bipartite matching gives us the minimal
1586 chain partition, which corresponds to the maximum anti chains.
1588 res = hungarian_solve(bp, assignment, &cost, 1);
1589 assert(res == 0 && "Bipartite matching failed!");
1592 memset(assignment_rev, -1, n * sizeof(assignment_rev[0]));
1594 /* build the reverse assignment, ie. foreach i -> j, add j -> i */
1595 for (i = 0; i < n; ++i) {
1596 if (assignment[i] != (unsigned)-1) {
1597 unsigned j = assignment[i];
1598 assignment_rev[j] = i;
1602 DBG((rss->dbg, LEVEL_2, "\t\tgot assignment with cost %u\n", cost));
1603 DBG((rss->dbg, LEVEL_3, "\t\t\tassignment --- reverse assignment\n"));
1604 for (i = 0; i < n; ++i) {
1605 DBG((rss->dbg, LEVEL_3, "\t\t\t%3u -> %3u %3u -> %3u\n", i, assignment[i], i, assignment_rev[i]));
1608 values = XMALLOC(ir_nodeset_t);
1609 ir_nodeset_init_size(values, 10);
1611 /* Construction of the minimal chain partition */
1612 for (j = 0; j < n; ++j) {
1613 /* check nodes, which did not occur as target */
1614 if (assignment_rev[j] == (unsigned)-1) {
1615 int xj = idx_map[j];
1616 ir_node *xj_irn = get_idx_irn(rss->irg, xj);
1617 rss_irn_t *xj_rss = get_rss_irn(rss, xj_irn);
1618 chain_t *c = OALLOC(phase_obst(&rss->ph), chain_t);
1621 /* there was no source for j -> we have a source of a new chain */
1622 ir_nodeset_insert(values, xj_irn);
1624 c->elements = plist_obstack_new(phase_obst(&rss->ph));
1625 c->nr = cur_chain++;
1626 plist_insert_back(c->elements, xj_irn);
1630 DBG((rss->dbg, LEVEL_2, "\t\tstarting chain %d:\n", c->nr));
1631 DBG((rss->dbg, LEVEL_2, "\t\t\t%+F (%u)", xj_irn, j));
1633 /* follow chain, having j as source */
1635 while (assignment[source] != (unsigned)-1) {
1636 int target = assignment[source];
1637 int irn_idx = idx_map[target];
1638 ir_node *irn = get_idx_irn(rss->irg, irn_idx);
1639 rss_irn_t *node = get_rss_irn(rss, irn);
1641 plist_insert_back(c->elements, irn);
1644 DB((rss->dbg, LEVEL_2, " -> %+F (%d)", irn, target));
1646 /* new source = last target */
1650 DB((rss->dbg, LEVEL_2, "\n"));
1655 Computing the maximal antichain: Select an element from each
1656 chain such, such it is parallel with the others.
1658 DBG((rss->dbg, LEVEL_1, "\t\tcomputing set of saturation values (MAX AC)\n"));
1659 DBG((rss->dbg, LEVEL_3, "\t\tstarting with:\n"));
1662 if (firm_dbg_get_mask(rss->dbg) & LEVEL_3)
1663 dump_nodeset(values, "\t\t\t");
1669 We need an explicit array for the values as
1670 we cannot iterate multiple times over the same
1671 set at the same time. :-(((((
1672 TODO Matze: now we can, so rewrite this...
1674 unsigned n = ir_nodeset_size(values);
1676 ir_node **val_arr = NEW_ARR_F(ir_node *, n);
1678 foreach_ir_nodeset(values, u_irn, iter)
1679 val_arr[i++] = u_irn;
1682 ir_nodeset_destroy(temp);
1686 temp = XMALLOC(ir_nodeset_t);
1687 ir_nodeset_init_size(temp, 10);
1689 /* Select all nodes from current value set, having another node in the set as descendant. */
1690 for (i = 0; i < n; ++i) {
1691 rss_irn_t *u = get_rss_irn(rss, val_arr[i]);
1693 for (j = 0; j < n; ++j) {
1697 key.src = val_arr[i];
1698 key.tgt = val_arr[j];
1700 if (pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
1701 /* v[j] is descendant of u -> remove u and break */
1702 ir_nodeset_insert(temp, (ir_node *) u->irn);
1703 ir_nodeset_remove(values, u->irn);
1705 DBG((rss->dbg, LEVEL_3, "\t\t\tremoving %+F from values, adding it to temp\n", u->irn));
1713 /* Try to insert the chain predecessor of all selected u's */
1714 foreach_ir_nodeset(temp, u_irn, iter) {
1715 rss_irn_t *u = get_rss_irn(rss, u_irn);
1716 chain_t *c = u->chain;
1717 plist_element_t *el = plist_find_value(c->elements, u_irn);
1719 assert(el && "Missing element in chain!");
1721 /* If u has predecessor in chain: insert the predecessor */
1722 if (el == plist_element_get_prev(el)) {
1723 ir_nodeset_insert(values, (ir_node*)plist_element_get_value(el));
1724 DBG((rss->dbg, LEVEL_3, "\t\t\tadding %+F to values\n", plist_element_get_value(el)));
1730 } while (ir_nodeset_size(temp) > 0);
1732 DBG((rss->dbg, LEVEL_2, "\t\tfinal set:\n"));
1734 if (firm_dbg_get_mask(rss->dbg) & LEVEL_2) {
1735 dump_nodeset(values, "\t\t\t");
1739 if (rss->opts->dump_flags & RSS_DUMP_MAXAC)
1740 debug_vcg_dump_pkg(rss, values, iteration);
1743 ir_nodeset_destroy(temp);
1753 * Computes the best serialization between two nodes of sat_vals.
1755 static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nodeset_t *sat_vals, serialization_t *ser, int num_regs)
1757 int n = ir_nodeset_size(sat_vals);
1758 int n_idx = ARR_LEN_SAFE(rss->idx_map);
1760 ir_node **val_arr = ALLOCAN(ir_node*, n);
1761 bitset_t *bs_sv = bitset_alloca(n_idx);
1762 bitset_t *bs_vdesc = bitset_alloca(n_idx);
1763 bitset_t *bs_tmp = bitset_alloca(n_idx);
1764 bitset_t *bs_ukilldesc = bitset_alloca(n_idx);
1765 int best_benefit = INT_MAX;
1766 int best_omega2 = INT_MAX;
1767 int best_benefit_omega20 = INT_MAX;
1771 ir_nodeset_iterator_t iter;
1772 rss_edge_t min_benefit_edge = {NULL, NULL, NULL};
1773 rss_edge_t min_omega20_edge = {NULL, NULL, NULL};
1774 rss_irn_t *ser_u_omega1 = NULL, *ser_v_omega1 = NULL;
1775 rss_irn_t *ser_u_omega20 = NULL, *ser_v_omega20 = NULL;
1777 DBG((rss->dbg, LEVEL_1, "\tcomputing admissible serializations:\n"));
1780 We need an explicit array for the values as
1781 we cannot iterate multiple times over the same
1782 set at the same time. :-(((((
1785 foreach_ir_nodeset(sat_vals, irn, iter) {
1787 bitset_set(bs_sv, BLOCK_IDX_MAP(rss, irn));
1791 We build all admissible serializations and remember the best found so far.
1794 if v in pkiller(u): add edge from v to all other pkiller(u)
1795 else: for all vv in pkiller(u): add edge from v to vv if there exists no path from vv to v
1799 A node is unserializable if:
1800 - it has only one killer and this one is Sink
1801 - it kills no other values
1802 In this case there is no serialization which could
1803 reduce the registerpressure
1805 #define IS_UNSERIALIZABLE_NODE(rss_node) \
1808 (plist_count(rss_node->pkiller_list) == 1) && \
1809 is_Sink(rss_node->killer) && \
1810 (rss_node->kill_count == 0) \
1812 be_is_Barrier(rss_node->irn) || \
1813 be_is_Keep(rss_node->irn) \
1816 /* for all u in sat_vals */
1817 for (i = 0; i < n; ++i) {
1818 rss_irn_t *u = get_rss_irn(rss, val_arr[i]);
1819 plist_element_t *el;
1821 /* ignore nodes where serialization does not help */
1822 if (IS_UNSERIALIZABLE_NODE(u)) {
1823 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", u->irn));
1827 /* accumulate all descendants of all pkiller(u) */
1828 bitset_clear_all(bs_ukilldesc);
1829 foreach_plist(u->pkiller_list, el) {
1830 ir_node *irn = (ir_node*)plist_element_get_value(el);
1831 rss_irn_t *node = get_rss_irn(rss, irn);
1834 bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, irn));
1838 for (k = ARR_LEN_SAFE(node->descendants) - 1; k >= 0; --k) {
1839 if (! is_Sink(node->descendants[k]))
1840 bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, node->descendants[k]));
1844 /* for all v in sat_vals */
1845 for (j = 0; j < n; ++j) {
1846 ir_node *v_irn = val_arr[j];
1847 rss_irn_t *v = get_rss_irn(rss, v_irn);
1848 unsigned v_height = get_irn_height(rss->h, v_irn);
1849 int omega1, omega2, is_pkiller;
1851 /* v cannot be serialized with itself
1852 * ignore nodes where serialization does not help */
1853 if (i == j || IS_UNSERIALIZABLE_NODE(v)) {
1854 #ifdef DEBUG_libfirm
1856 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", v->irn));
1861 /* get descendants of v */
1862 bitset_clear_all(bs_vdesc);
1863 bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v_irn));
1864 for (k = ARR_LEN_SAFE(v->descendants) - 1; k >= 0; --k) {
1865 if (! is_Sink(v->descendants[k]))
1866 bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v->descendants[k]));
1869 /* if v is in pkiller(u) */
1870 is_pkiller = plist_has_value(u->pkiller_list, v_irn);
1872 /* for all vv in pkiller(u) */
1873 foreach_plist(u->pkiller_list, el) {
1874 ir_node *vv_irn = (ir_node*)plist_element_get_value(el);
1877 if (is_Sink(vv_irn) || is_cfop(vv_irn))
1881 add_edge = vv_irn != v_irn && skip_Proj(vv_irn) != skip_Proj(v_irn);
1883 add_edge = ! heights_reachable_in_block(rss->h, skip_Proj(vv_irn), skip_Proj(v_irn));
1886 As we add an edge from vv -> v, we have to make sure,
1887 that there exists no path from v to vv.
1891 unsigned vv_height = get_irn_height(rss->h, vv_irn);
1892 unsigned critical_path_cost;
1896 mu1 = | descendants(v) cut sat_vals |
1897 the number of saturating values which cannot
1898 be simultaneously alive with u
1900 bitset_copy(bs_tmp, bs_vdesc);
1901 bitset_and(bs_tmp, bs_sv);
1902 mu1 = bitset_popcount(bs_tmp);
1905 mu2 = | accum_desc_all_pkiller(u) without descendants(v) |
1908 bitset_copy(bs_tmp, bs_ukilldesc);
1909 bitset_andnot(bs_tmp, bs_vdesc);
1910 mu2 = bitset_popcount(bs_tmp);
1916 /* omega1 = mu1 - mu2 */
1922 /* omega2 = increase of critical path */
1923 critical_path_cost =
1924 v_height /* longest path from v to sink */
1925 + rss->max_height - vv_height /* longest path from source to vv */
1929 If critical_path_cost > max_height -> the new edge
1930 would increase the longest critical path by the difference.
1932 omega2 = critical_path_cost > rss->max_height ? critical_path_cost - rss->max_height : 0;
1934 /* this keeps track of the edge with the best benefit */
1935 if (omega1 >= num_regs - n && omega1 < best_benefit) {
1936 min_benefit_edge.src = v_irn;
1937 min_benefit_edge.tgt = vv_irn;
1942 best_benefit = omega1;
1943 ser->new_killer = is_pkiller;
1946 /* this keeps track of the edge with the best omega1 costs where omega2 == 0 */
1947 if (omega2 == 0 && omega1 >= num_regs - n && omega1 < best_benefit_omega20) {
1948 min_omega20_edge.src = v_irn;
1949 min_omega20_edge.tgt = vv_irn;
1954 best_benefit_omega20 = omega1;
1955 ser->new_killer = is_pkiller;
1958 best_omega2 = MIN(best_omega2, omega2);
1960 DBG((rss->dbg, LEVEL_2, "\t\tfound %+F -> %+F (w1 %d, w2 %d)\n",
1961 v_irn, vv_irn, omega1, omega2));
1963 } /* for all vv in pkiller(u) */
1964 } /* for all v in sat_vals */
1965 } /* for all u in sat_vals */
1970 if (best_omega2 == 0) {
1971 ser->u = ser_u_omega20;
1972 ser->v = ser_v_omega20;
1973 ser->edge->src = min_omega20_edge.src;
1974 ser->edge->tgt = min_omega20_edge.tgt;
1975 ser->omega1 = best_benefit_omega20;
1976 ser->omega2 = best_omega2;
1979 ser->u = ser_u_omega1;
1980 ser->v = ser_v_omega1;
1981 ser->edge->src = min_benefit_edge.src;
1982 ser->edge->tgt = min_benefit_edge.tgt;
1983 ser->omega1 = best_benefit;
1984 ser->omega2 = best_omega2;
1989 #undef IS_UNSERIALIZABLE_NODE
1993 * Perform the value serialization heuristic and add all
1994 * computed serialization edges as dependencies to the irg.
1996 static void perform_value_serialization_heuristic(rss_t *rss)
1998 unsigned available_regs, iteration;
2000 ir_nodeset_t *sat_vals;
2001 pset *ser_set = new_pset(cmp_rss_edges, 20);
2003 available_regs = be_get_n_allocatable_regs(rss->irg, rss->cls);
2005 DBG((rss->dbg, LEVEL_1, "\n\t#available regs: %d\n\n", available_regs));
2008 At first we need to compute the disjoint value DAG (DVG = {V, E_dv}).
2009 V = set of all nodes we are currently interested in
2010 E_dv = there is an edge from u to v iff v is a descendant of killer(u), forall u, v in V
2012 ir_nodeset_init_size(&dvg.nodes, plist_count(rss->nodes));
2013 dvg.edges = new_pset(cmp_rss_edges, plist_count(rss->nodes) * 5);
2014 compute_dvg(rss, &dvg);
2017 Then we perform the heuristic serialization algorithm
2018 on the DVG which gives us all necessary serialization
2021 DBG((rss->dbg, LEVEL_1, "\tcomputing maximal antichain:\n"));
2023 sat_vals = compute_maximal_antichain(rss, &dvg, iteration++);
2024 while (sat_vals && (ir_nodeset_size(sat_vals) > available_regs)) {
2025 serialization_t *ser, best_ser;
2026 rss_edge_t *edge = OALLOC(phase_obst(&rss->ph), rss_edge_t);
2027 ir_node *dep_src, *dep_tgt;
2029 best_ser.edge = edge;
2030 ser = compute_best_admissible_serialization(rss, sat_vals, &best_ser, available_regs);
2032 DBG((rss->dbg, LEVEL_1, "\tcurrent register saturation %d, target %d\n", ir_nodeset_size(sat_vals), available_regs));
2035 DBG((rss->dbg, LEVEL_1, "\tno RS improving serialization found, breaking at iteration %d\n", iteration));
2039 /* Insert the serialization as dependency edge into the irg. */
2040 DBG((rss->dbg, LEVEL_1, "\tserializing %+F -> %+F with edge %+F -> %+F and cost %d, %d\n",
2041 ser->u->irn, ser->v->irn, ser->edge->src, ser->edge->tgt, ser->omega1, ser->omega2));
2043 if (pset_find(ser_set, ser->edge, HASH_RSS_EDGE(ser->edge)))
2044 ir_printf("WARNING: serialization %+F -> %+F computed twice!\n", ser->edge->src, ser->edge->tgt);
2047 pset_insert(ser_set, ser->edge, HASH_RSS_EDGE(ser->edge));
2049 /* update the dvg */
2050 update_dvg(rss, &dvg, ser->v, ser->u);
2051 update_dvg(rss, &dvg, get_rss_irn(rss, ser->edge->src), get_rss_irn(rss, ser->edge->tgt));
2052 if (sat_vals != NULL) {
2053 ir_nodeset_destroy(sat_vals);
2057 dep_src = skip_Proj(ser->edge->src);
2058 dep_tgt = ser->edge->tgt;
2059 add_irn_dep(dep_src, dep_tgt);
2061 /* Update descendants, consumer and pkillers of the target */
2062 update_node_info(rss, ser->edge->tgt, ser->edge->src);
2064 /* TODO: try to find a cheaper way for updating height information */
2065 rss->max_height = heights_recompute_block(rss->h, rss->block);
2067 /* Recompute the antichain for next serialization */
2068 DBG((rss->dbg, LEVEL_1, "\tre-computing maximal antichain:\n"));
2069 sat_vals = compute_maximal_antichain(rss, &dvg, iteration++);
2072 ir_nodeset_destroy(&dvg.nodes);
2073 del_pset(dvg.edges);
2077 * Do initial calculations for a block.
2079 static void process_block(ir_node *block, void *env)
2081 rss_t *rss = (rss_t*)env;
2083 const ir_edge_t *edge;
2085 phase_init(&rss->ph, rss->irg, init_rss_irn);
2087 DBG((rss->dbg, LEVEL_1, "preprocessing block %+F\n", block));
2090 /* build an index map for all nodes in the current block */
2092 n = get_irn_n_edges(block);
2093 NEW_ARR_A(int, rss->idx_map, n);
2094 foreach_out_edge(block, edge) {
2095 ir_node *irn = get_edge_src_irn(edge);
2096 rss->idx_map[i++] = get_irn_idx(irn);
2098 qsort(rss->idx_map, n, sizeof(rss->idx_map[0]), cmp_int);
2099 rss->max_height = heights_recompute_block(rss->h, block);
2101 /* loop over all register classes */
2102 for (i = rss->arch_env->n_register_classes - 1; i >= 0; --i) {
2103 const arch_register_class_t *cls = &rss->arch_env->register_classes[i];
2106 DBG((rss->dbg, LEVEL_1, "register class %s\n", arch_register_class_name(cls)));
2108 /* Get all live value at end of Block having current register class */
2109 ir_nodeset_init(&rss->live_block);
2110 be_liveness_end_of_block(rss->liveness, rss->cls, rss->block, &rss->live_block);
2112 /* reset the list of interesting nodes */
2113 plist_clear(rss->nodes);
2114 plist_insert_back(rss->nodes, _sink);
2116 /* collect all nodes having a certain register class */
2117 foreach_out_edge(block, edge) {
2118 ir_node *irn = get_edge_src_irn(edge);
2119 ir_mode *mode = get_irn_mode(irn);
2123 - mode_T nodes (the projs are asked)
2124 - mode_X nodes (control flow nodes are always scheduled last)
2125 - Keeps (they are always immediately scheduled)
2126 - Phi (same as Keep)
2128 if (mode == mode_T || mode == mode_X || is_Phi(irn))
2132 In case of a proj, we skip
2133 - Barrier (they are a Barrier :)
2135 - the Proj itself, as it's scheduled always with it's super node
2138 ir_node *pred = get_Proj_pred(irn);
2139 if (be_is_Barrier(pred) || be_is_Start(pred))
2143 /* calculate the descendants and consumer for each node in the block */
2144 collect_node_info(rss, skip_Proj(irn));
2146 if (be_is_Keep(irn))
2149 if (!arch_irn_is_ignore(irn) &&
2150 arch_get_irn_reg_class_out(irn) == cls) {
2151 plist_insert_back(rss->nodes, skip_Proj(irn));
2156 /* compute the potential killing set PK(G) */
2157 compute_pkill_set(rss);
2159 /* compute the killing function k* */
2160 compute_killing_function(rss);
2163 Compute the heuristic value serialization and
2164 add the necessary dependencies to the irg.
2166 perform_value_serialization_heuristic(rss);
2168 ir_nodeset_destroy(&rss->live_block);
2171 phase_deinit(&rss->ph);
2174 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_schedrss);
2175 void be_init_schedrss(void)
2177 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
2178 lc_opt_entry_t *sched_grp = lc_opt_get_grp(be_grp, "sched");
2179 lc_opt_entry_t *rss_grp = lc_opt_get_grp(sched_grp, "rss");
2181 lc_opt_add_table(rss_grp, rss_option_table);
2185 * Preprocess the irg for scheduling.
2187 void rss_schedule_preparation(ir_graph *irg)
2191 FIRM_DBG_REGISTER(rss.dbg, "firm.be.sched.rss");
2193 //firm_dbg_set_mask(rss.dbg, LEVEL_1 | LEVEL_2 | LEVEL_3);
2195 init_rss_special_nodes(irg);
2198 rss.arch_env = be_get_irg_arch_env(irg);
2199 rss.abi = be_get_irg_abi(irg);
2200 rss.h = heights_new(irg);
2201 rss.nodes = plist_new();
2202 rss.opts = &rss_options;
2203 rss.liveness = be_liveness(irg);
2204 be_liveness_assure_sets(rss.liveness);
2205 irg_block_walk_graph(irg, NULL, process_block, &rss);
2206 heights_free(rss.h);
2207 plist_free(rss.nodes);
2208 be_liveness_free(rss.liveness);
2210 if (be_get_irg_options(irg)->dump_flags & DUMP_SCHED)
2211 dump_ir_graph(irg, "rss");