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
38 #include "irgraph_t.h"
40 #include "iredges_t.h"
42 #include "irphase_t.h"
48 #include "irnodeset.h"
49 #include "bipartite.h"
50 #include "hungarian.h"
64 #include "lc_opts_enum.h"
67 #define ARR_LEN_SAFE(arr) ((arr) != NULL ? ARR_LEN((arr)) : 0)
69 #define HASH_RSS_EDGE(edge) ((get_irn_node_nr((edge)->src) << 16) | (get_irn_node_nr((edge)->tgt) & 0xFFFF))
70 #define BSEARCH_IRN_ARR(val, arr) \
71 bsearch(&(val), (arr), ARR_LEN_SAFE((arr)), sizeof((arr)[0]), cmp_irn_idx)
73 #define BLOCK_IDX_MAP(rss, irn) bsearch_for_index(get_irn_idx((irn)), (rss)->idx_map, ARR_LEN_SAFE((rss)->idx_map), 1)
76 typedef struct _rss_opts_t {
80 /* Represents a child with associated costs */
81 typedef struct _child {
86 /* We need edges for several purposes. */
87 typedef struct _rss_edge {
93 /* Represents a connected bipartite component. */
95 ir_nodeset_t parents; /**< = S a set of value producers */
96 ir_nodeset_t children; /**< = T a set of value consumers */
97 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 */
98 int nr; /**< a deterministic index for set insertion (used as hash) */
101 /* Represents a disjoint value DAG. */
102 typedef struct _dvg {
107 /* Represents a chain of nodes. */
108 typedef struct _chain {
109 plist_t *elements; /**< List of chain elements */
110 int nr; /**< a deterministic index for set insertion (used as hash) */
113 typedef struct _rss_irn {
114 plist_t *consumer_list; /**< List of consumers */
115 const ir_node **consumer; /**< Sorted consumer array (needed for faster access) */
117 plist_t *parent_list; /**< List of parents */
118 plist_t *pkiller_list; /**< List of potential killers */
120 plist_t *descendant_list; /**< List of descendants */
121 const ir_node **descendants; /**< Sorted descendant array (needed for faster access) */
123 const ir_node *killer; /**< The selected unique killer */
124 const ir_node *irn; /**< The corresponding firm node to this rss_irn */
126 chain_t *chain; /**< The chain, this node is associated to */
128 unsigned desc_walk; /**< visited flag for collecting descendants */
129 unsigned kill_count; /**< number of nodes killed by this one */
131 unsigned live_out : 1; /**< irn has consumers outside of it's block */
132 unsigned visited : 1; /**< visited flag for bipartite decomposition */
133 unsigned havecons : 1; /**< visited flag collect consumer */
134 unsigned handled : 1; /**< flag indicating whether or not the list structures have been build */
135 unsigned dumped : 1; /**< flag indication whether or not this node was dumped */
138 /* Represents a serialization edge with associated costs. */
139 typedef struct _serialization {
140 rss_irn_t *u; /* the top node */
141 rss_irn_t *v; /* the node about to be serialized after u */
142 rss_edge_t *edge; /* the edge selected for the serialization */
143 int omega1; /* estimated: available regs - RS reduction */
144 int omega2; /* increase in critical path length */
148 typedef struct _rss {
149 ir_phase ph; /**< Phase to hold some data */
150 heights_t *h; /**< The current height object */
151 ir_graph *irg; /**< The irg to preprocess */
152 plist_t *nodes; /**< The list of interesting nodes */
153 const arch_env_t *arch_env; /**< The architecture environment */
154 be_abi_irg_t *abi; /**< The abi for this irg */
155 pset *cbc_set; /**< A set of connected bipartite components */
156 ir_node *block; /**< The current block in progress. */
157 int *idx_map; /**< Mapping irn indices to per block indices */
158 unsigned max_height; /**< maximum height in the current block */
159 rss_opts_t *opts; /**< The options */
160 be_lv_t *liveness; /**< The liveness information for this irg */
161 ir_nodeset_t live_block; /**< Values alive at end of block */
162 const arch_register_class_t *cls; /**< The current register class */
163 DEBUG_ONLY(firm_dbg_module_t *dbg);
166 #define get_rss_irn(rss, irn) (phase_get_or_set_irn_data(&rss->ph, irn))
169 * We need some special nodes:
170 * a source and a sink for all live-in and live-out values of a block
178 /** The opcode of the rss_Source node once allocated. */
179 static ir_op *op_rss_Source;
180 /** The opcode of the rss_Sink node once allocated. */
181 static ir_op *op_rss_Sink;
183 /** The rss_Source node of the current graph. */
184 static ir_node *_source = NULL;
185 /** The rss_Sink node of the current graph. */
186 static ir_node *_sink = NULL;
188 #define is_Source(irn) ((irn) == _source)
189 #define is_Sink(irn) ((irn) == _sink)
193 RSS_DUMP_CBC = 1 << 0,
194 RSS_DUMP_PKG = 1 << 1,
195 RSS_DUMP_KILL = 1 << 2,
196 RSS_DUMP_DVG = 1 << 3,
197 RSS_DUMP_MAXAC = 1 << 4,
198 RSS_DUMP_ALL = (RSS_DUMP_MAXAC << 1) - 1,
201 static rss_opts_t rss_options = {
205 static const lc_opt_enum_int_items_t dump_items[] = {
206 { "none", RSS_DUMP_NONE },
207 { "cbc", RSS_DUMP_CBC },
208 { "pkg", RSS_DUMP_PKG },
209 { "kill", RSS_DUMP_KILL },
210 { "dvg", RSS_DUMP_DVG },
211 { "maxac", RSS_DUMP_MAXAC },
212 { "all", RSS_DUMP_ALL },
216 static lc_opt_enum_int_var_t dump_var = {
217 &rss_options.dump_flags, dump_items
220 static const lc_opt_table_entry_t rss_option_table[] = {
221 LC_OPT_ENT_ENUM_MASK("dump", "dump phases", &dump_var),
225 /******************************************************************************
227 * | | | | / _| | | (_)
228 * | |__ ___| |_ __ ___ _ __ | |_ _ _ _ __ ___| |_ _ ___ _ __ ___
229 * | '_ \ / _ \ | '_ \ / _ \ '__| | _| | | | '_ \ / __| __| |/ _ \| '_ \/ __|
230 * | | | | __/ | |_) | __/ | | | | |_| | | | | (__| |_| | (_) | | | \__ \
231 * |_| |_|\___|_| .__/ \___|_| |_| \__,_|_| |_|\___|\__|_|\___/|_| |_|___/
234 ******************************************************************************/
237 * Acquire opcodes if needed and create source and sink nodes.
239 static void init_rss_special_nodes(ir_graph *irg) {
242 if (op_rss_Source == NULL) {
243 int iro_rss_base = get_next_ir_opcodes(iro_rss_last);
244 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);
245 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);
247 block = get_irg_start_block(irg);
248 _source = new_ir_node(NULL, irg, block, op_rss_Source, mode_ANY, 0, NULL);
249 _sink = new_ir_node(NULL, irg, block, op_rss_Sink, mode_ANY, 0, NULL);
252 static int cmp_int(const void *a, const void *b) {
256 return QSORT_CMP(*i1, *i2);
259 static int cmp_child_costs(const void *a, const void *b) {
260 const child_t *c1 = a;
261 const child_t *c2 = b;
263 return QSORT_CMP(c1->cost, c2->cost);
266 static int cmp_irn_idx(const void *a, const void *b) {
267 const ir_node *n1 = *(ir_node **)a;
268 const ir_node *n2 = *(ir_node **)b;
270 return QSORT_CMP(get_irn_idx(n1), get_irn_idx(n2));
273 static int cmp_rss_edges(const void *a, const void *b) {
274 const rss_edge_t *e1 = a;
275 const rss_edge_t *e2 = b;
277 return (e1->src != e2->src) || (e1->tgt != e2->tgt);
280 static int bsearch_for_index(int key, int *arr, size_t len, int force) {
284 while (right >= left) {
285 int idx = (left + right) / 2;
289 else if (key > arr[idx])
296 assert(0 && "Something is wrong, key not found.");
300 static const ir_node **build_sorted_array_from_list(plist_t *irn_list, struct obstack *obst) {
303 int len = plist_count(irn_list);
304 const ir_node **arr = (const ir_node**)NEW_ARR_D(ir_node*, obst, len);
306 /* copy the list into the array */
307 foreach_plist(irn_list, el) {
308 arr[i++] = plist_element_get_value(el);
311 /* sort the array by node index */
312 /* HACK cast for MSVC */
313 qsort((void*)arr, len, sizeof(arr[0]), cmp_irn_idx);
318 /*****************************************************
321 * __| | ___| |__ _ _ __ _ __ _ _ _ __ __ _
322 * / _` |/ _ \ '_ \| | | |/ _` |/ _` | | '_ \ / _` |
323 * | (_| | __/ |_) | |_| | (_| | (_| | | | | | (_| |
324 * \__,_|\___|_.__/ \__,_|\__, |\__, |_|_| |_|\__, |
328 *****************************************************/
331 static void dump_nodeset(ir_nodeset_t *ns, const char *prefix) {
332 ir_nodeset_iterator_t iter;
335 ir_nodeset_iterator_init(&iter, ns);
336 while( (irn = ir_nodeset_iterator_next(&iter)) != NULL ) {
337 ir_fprintf(stderr, "%s%+F\n", prefix, irn);
342 static void build_file_name(rss_t *rss, const char *suffix, size_t suf_len, char *buf, size_t len) {
343 const char *irg_name;
346 irg_name = get_entity_name(get_irg_entity(rss->irg));
347 snprintf(buf, len - suf_len, "%s-%s-block-%ld",
348 irg_name, arch_register_class_name(rss->cls), get_irn_node_nr(rss->block));
352 /* Dumps all collected bipartite components of current irg as vcg. */
353 static void debug_vcg_dump_bipartite(rss_t *rss) {
357 static const char suffix[] = "-RSS-CBC.vcg";
359 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
360 f = fopen(file_name, "w");
362 ir_fprintf(f, "graph: { title: \"connected bipartite component graph of %+F\"\n", rss->irg);
363 fprintf(f, "display_edge_labels: no\n");
364 fprintf(f, "layoutalgorithm: mindepth\n");
365 fprintf(f, "manhattan_edges: yes\n\n");
367 foreach_pset(rss->cbc_set, cbc) {
368 ir_nodeset_iterator_t iter;
372 fprintf(f, "graph: { titel: \"cbc %d\" label: \"cbc %d\" status:clustered color:yellow\n", cbc->nr, cbc->nr);
373 foreach_ir_nodeset(&cbc->parents, n, iter) {
374 ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
376 foreach_ir_nodeset(&cbc->children, n, iter) {
377 ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
379 foreach_pset(cbc->kill_edges, ke) {
380 ir_fprintf(f, "edge: { sourcename: \"n%d_%d\" targetname: \"n%d_%d\" }\n",
381 get_irn_node_nr(ke->src), cbc->nr, get_irn_node_nr(ke->tgt), cbc->nr);
389 /* Dump the computed killing function as vcg. */
390 static void debug_vcg_dump_kill(rss_t *rss) {
394 static const char suffix[] = "-RSS-KILL.vcg";
396 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
397 f = fopen(file_name, "w");
399 ir_fprintf(f, "graph: { title: \"computed kill graph of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
400 fprintf(f, "display_edge_labels: no\n");
401 fprintf(f, "layoutalgorithm: mindepth\n");
402 fprintf(f, "manhattan_edges: yes\n\n");
405 /* reset dump_flag */
407 foreach_phase_irn(&rss->ph, irn) {
408 rss_irn_t *node = get_rss_irn(rss, irn);
413 /* dump all nodes and their killers */
414 foreach_plist(rss->nodes, el) {
415 ir_node *irn = plist_element_get_value(el);
416 rss_irn_t *rirn = get_rss_irn(rss, irn);
417 rss_irn_t *pk_rirn = get_rss_irn(rss, rirn->killer);
419 if (! rirn->dumped) {
420 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
424 if (! pk_rirn->dumped) {
425 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(rirn->killer), rirn->killer);
429 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
430 get_irn_node_nr(rirn->killer), get_irn_node_nr(irn));
437 /* Dumps the potential killing DAG (PKG) as vcg. */
438 static void debug_vcg_dump_pkg(rss_t *rss, ir_nodeset_t *max_ac, int iteration)
443 static const char suffix1[] = "-RSS-PKG.vcg";
444 static const char suffix2[] = "-RSS-PKG-MAXAC.vcg";
448 snprintf(suffix, sizeof(suffix), "%s", suffix1);
451 snprintf(suffix, sizeof(suffix), "-%02d%s", iteration, suffix2);
454 build_file_name(rss, suffix, strlen(suffix) + 1, file_name, sizeof(file_name));
455 f = fopen(file_name, "w");
457 ir_fprintf(f, "graph: { title: \"potential killing DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
458 fprintf(f, "display_edge_labels: no\n");
459 fprintf(f, "layoutalgorithm: mindepth\n");
460 fprintf(f, "manhattan_edges: yes\n\n");
463 /* reset dump_flag */
465 foreach_phase_irn(&rss->ph, irn) {
466 rss_irn_t *node = get_rss_irn(rss, irn);
471 foreach_plist(rss->nodes, el) {
472 ir_node *irn = plist_element_get_value(el);
473 rss_irn_t *rirn = get_rss_irn(rss, irn);
475 plist_element_t *k_el;
477 /* dump selected saturating values in yellow */
478 if (max_ac && ir_nodeset_contains(max_ac, irn))
481 if (! rirn->dumped) {
483 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(irn), irn, rirn->chain->nr, c1);
485 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(irn), irn, c1);
489 foreach_plist(rirn->pkiller_list, k_el) {
490 ir_node *pkiller = plist_element_get_value(k_el);
491 rss_irn_t *pk_rirn = get_rss_irn(rss, pkiller);
494 if (max_ac && ir_nodeset_contains(max_ac, pkiller))
497 if (! pk_rirn->dumped) {
499 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(pkiller), pkiller, pk_rirn->chain->nr, c2);
501 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(pkiller), pkiller, c2);
504 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
505 get_irn_node_nr(pkiller), get_irn_node_nr(irn));
512 /* Dumps the disjoint value DAG (DVG) as vcg. */
513 static void debug_vcg_dump_dvg(rss_t *rss, dvg_t *dvg) {
514 static const char suffix[] = "-RSS-DVG.vcg";
517 ir_nodeset_iterator_t iter;
521 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
522 f = fopen(file_name, "w");
524 ir_fprintf(f, "graph: { title: \"disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
525 fprintf(f, "display_edge_labels: no\n");
526 fprintf(f, "layoutalgorithm: mindepth\n");
527 fprintf(f, "manhattan_edges: yes\n\n");
530 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
531 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
535 foreach_pset(dvg->edges, edge) {
536 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
537 get_irn_node_nr(edge->src), get_irn_node_nr(edge->tgt));
545 /* Dumps the PKG(DVG). */
546 static void debug_vcg_dump_dvg_pkiller(rss_t *rss, dvg_t *dvg) {
547 static const char suffix[] = "-RSS-DVG-PKG.vcg";
550 ir_nodeset_iterator_t iter;
553 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
554 f = fopen(file_name, "w");
556 ir_fprintf(f, "graph: { title: \"PKG of disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
557 fprintf(f, "display_edge_labels: no\n");
558 fprintf(f, "layoutalgorithm: mindepth\n");
559 fprintf(f, "manhattan_edges: yes\n\n");
562 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
563 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
567 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
568 rss_irn_t *node = get_rss_irn(rss, irn);
571 foreach_plist(node->dvg_pkiller_list, el) {
572 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
573 get_irn_node_nr(plist_element_get_value(el)), get_irn_node_nr(irn));
583 * In case there is no rss information for irn, initialize it.
585 static void *init_rss_irn(ir_phase *ph, const ir_node *irn, void *old) {
586 rss_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
588 res->descendant_list = plist_obstack_new(phase_obst(ph));
589 res->descendants = NULL;
591 res->consumer_list = plist_obstack_new(phase_obst(ph));
592 res->consumer = NULL;
594 res->pkiller_list = plist_obstack_new(phase_obst(ph));
596 res->parent_list = plist_obstack_new(phase_obst(ph));
614 * Collect all nodes data dependent on current node.
616 static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int *got_sink, unsigned cur_desc_walk) {
617 const ir_edge_t *edge;
618 rss_irn_t *cur_node = get_rss_irn(rss, irn);
619 ir_node *block = rss->block;
620 ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
623 if (cur_node->desc_walk >= cur_desc_walk)
625 cur_node->desc_walk = cur_desc_walk;
627 /* Stop at Barriers */
628 if (be_is_Barrier(irn))
631 /* loop over normal and dependency edges */
632 for (i = 0; i < 2; ++i) {
633 foreach_out_edge_kind(irn, edge, ekind[i]) {
634 ir_node *user = get_edge_src_irn(edge);
636 /* skip ignore nodes as they do not really contribute to register pressure */
637 if (arch_irn_is_ignore(user))
641 (a) mode_X means Jump -> out_edge
642 (b) Phi as user of a normal node -> out-edge
644 if (get_irn_mode(user) == mode_X || is_Phi(user)) {
652 //if (arch_get_irn_reg_class_out(user) == rss->cls)
653 collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
656 /* check if user lives in block and is not a control flow node */
657 if (get_nodes_block(user) == block) {
658 if (! plist_has_value(rirn->descendant_list, user)) {
659 plist_insert_back(rirn->descendant_list, user);
660 DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", user));
662 collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
664 else if (! *got_sink) {
666 /* user lives out of block: add sink as descendant if not already done */
667 plist_insert_back(rirn->descendant_list, _sink);
669 DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", _sink));
677 * Handles a single consumer.
679 static void collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *consumer, int *got_sink) {
680 ir_node *block = rss->block;
682 assert(! is_Proj(consumer) && "Cannot handle Projs");
684 if (! is_Phi(consumer) && ! is_Block(consumer) && get_nodes_block(consumer) == block) {
685 if (!arch_irn_is_ignore(consumer) &&
686 !plist_has_value(rss_irn->consumer_list, consumer)) {
687 plist_insert_back(rss_irn->consumer_list, consumer);
688 DBG((rss->dbg, LEVEL_2, "\t\tconsumer %+F\n", consumer));
692 rss_irn->live_out = 1;
693 DBG((rss->dbg, LEVEL_2, "\t\tlive out %+F", consumer));
695 plist_insert_back(rss_irn->consumer_list, _sink);
697 DB((rss->dbg, LEVEL_2, ", %+F added instead", _sink));
699 DB((rss->dbg, LEVEL_2, "\n"));
704 * Collect all nodes consuming the value(s) produced by current node.
706 static void collect_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *irn, int *got_sink) {
707 const ir_edge_t *edge;
709 ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
710 rss_irn_t *cur_node = get_rss_irn(rss, irn);
712 if (cur_node->havecons)
714 cur_node->havecons = 1;
716 for (i = 0; i < 2; ++i) {
717 foreach_out_edge_kind(irn, edge, ekind[i]) {
718 ir_node *consumer = get_edge_src_irn(edge);
720 if (is_Proj(consumer)) {
721 //if (arch_get_irn_reg_class_out(consumer) == rss->cls)
722 collect_consumer(rss, rss_irn, consumer, got_sink);
725 collect_single_consumer(rss, rss_irn, consumer, got_sink);
731 * Collects all consumer and descendant of a irn.
733 static void collect_node_info(rss_t *rss, ir_node *irn) {
734 static unsigned cur_desc_walk = 0;
735 rss_irn_t *rss_irn = get_rss_irn(rss, irn);
738 assert(! is_Proj(irn) && "Cannot handle Projs.");
740 /* check if node info is already available */
741 if (rss_irn->handled)
743 //phase_reinit_single_irn_data(&rss->ph, irn);
745 DBG((rss->dbg, LEVEL_1, "\tcomputing consumers of %+F:\n", irn));
747 /* collect all consumer */
749 collect_consumer(rss, rss_irn, irn, &got_sink);
751 /* build sorted consumer array */
752 rss_irn->consumer = build_sorted_array_from_list(rss_irn->consumer_list, phase_obst(&rss->ph));
754 DBG((rss->dbg, LEVEL_1, "\tcompute descendants of %+F:\n", irn));
756 /* collect descendants */
758 collect_descendants(rss, rss_irn, irn, &got_sink, ++cur_desc_walk);
760 /* build sorted descendant array */
761 rss_irn->descendants = build_sorted_array_from_list(rss_irn->descendant_list, phase_obst(&rss->ph));
763 rss_irn->handled = 1;
767 * Checks if v is a potential killer of u.
768 * v is in pkill(u) iff descendants(v) cut consumer(u) is v
770 * @param rss The rss object
771 * @param v The node to check for killer
772 * @param u The potentially killed value
773 * @return 1 if v is in pkill(u), 0 otherwise
775 static int is_potential_killer(rss_t *rss, rss_irn_t *v, rss_irn_t *u) {
781 assert(is_Sink(v->irn) || ((plist_count(v->descendant_list) > 0 && v->descendants) || 1));
782 assert(is_Sink(u->irn) || ((plist_count(u->consumer_list) > 0 && u->consumer) || 1));
784 /* as we loop over the list: loop over the shorter one */
785 if (plist_count(v->descendant_list) > plist_count(u->consumer_list)) {
786 list = u->consumer_list;
787 arr = v->descendants;
790 list = v->descendant_list;
794 /* for each list element: try to find element in array */
795 foreach_plist(list, el) {
796 ir_node *irn = plist_element_get_value(el);
797 ir_node *match = BSEARCH_IRN_ARR(irn, arr);
799 if (match && match != irn)
807 * Update descendants, consumer and pkiller list for the given irn.
809 static void update_node_info(rss_t *rss, ir_node *irn, ir_node *pk_irn) {
810 rss_irn_t *node = get_rss_irn(rss, irn);
811 rss_irn_t *pkiller = get_rss_irn(rss, pk_irn);
813 /* add consumer and rebuild the consumer array */
814 if (! plist_has_value(node->consumer_list, pk_irn)) {
815 plist_insert_back(node->consumer_list, pk_irn);
816 node->consumer = build_sorted_array_from_list(node->consumer_list, phase_obst(&rss->ph));
819 /* add pk_irn as descendant, add it's descendants to irn's and rebuild array */
820 if (! plist_has_value(node->descendant_list, pk_irn)) {
823 plist_insert_back(node->descendant_list, pk_irn);
825 foreach_plist(pkiller->descendant_list, el) {
826 ir_node *desc = plist_element_get_value(el);
828 if (! plist_has_value(node->descendant_list, desc))
829 plist_insert_back(node->descendant_list, desc);
832 node->descendants = build_sorted_array_from_list(node->descendant_list, phase_obst(&rss->ph));
838 * Compute the potential killing set PK.
840 static void compute_pkill_set(rss_t *rss) {
841 plist_element_t *u_el, *v_el;
843 foreach_plist(rss->nodes, u_el) {
844 ir_node *u_irn = plist_element_get_value(u_el);
845 rss_irn_t *u = get_rss_irn(rss, u_irn);
847 DBG((rss->dbg, LEVEL_1, "\tcomputing potential killers of %+F:\n", u_irn));
849 /* check each consumer if it is a potential killer */
850 foreach_plist(u->consumer_list, v_el) {
851 ir_node *v_irn = plist_element_get_value(v_el);
852 rss_irn_t *v = get_rss_irn(rss, v_irn);
854 /* check, if v is a potential killer of u */
855 if (is_potential_killer(rss, v, u)) {
856 if (! plist_has_value(u->pkiller_list, v_irn))
857 plist_insert_back(u->pkiller_list, v_irn);
859 DBG((rss->dbg, LEVEL_2, "\t\tpotential killer %+F\n", v_irn));
866 if (rss->opts->dump_flags & RSS_DUMP_PKG)
867 debug_vcg_dump_pkg(rss, NULL, 0);
871 * Build set of killing edges (from values to their potential killers)
873 static void build_kill_edges(rss_t *rss, pset *epk) {
874 plist_element_t *el, *k_el;
876 foreach_plist(rss->nodes, el) {
877 ir_node *irn = plist_element_get_value(el);
878 rss_irn_t *rirn = get_rss_irn(rss, irn);
880 DBG((rss->dbg, LEVEL_3, "\t\tbuilding kill edges for %+F:\n", irn));
882 foreach_plist(rirn->pkiller_list, k_el) {
883 ir_node *pkiller = plist_element_get_value(k_el);
884 rss_edge_t *ke = obstack_alloc(phase_obst(&rss->ph), sizeof(*ke));
890 DBG((rss->dbg, LEVEL_3, "\t\t\ttarget %+F\n", pkiller));
892 pset_insert(epk, ke, HASH_RSS_EDGE(ke));
898 /* print the given cbc for debugging purpose */
899 static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc) {
900 ir_nodeset_iterator_t iter;
904 DBG((mod, LEVEL_3, "\t\tS = set of parents:\n"));
905 foreach_ir_nodeset(&cbc->parents, n, iter) {
906 DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
908 DBG((mod, LEVEL_3, "\t\tT = set of children:\n"));
909 foreach_ir_nodeset(&cbc->children, n, iter) {
910 DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
912 DBG((mod, LEVEL_3, "\t\tE = Edges from producers to consumers\n"));
913 foreach_pset(cbc->kill_edges, ke) {
914 DBG((mod, LEVEL_3, "\t\t\t%+F -> %+F\n", ke->src, ke->tgt));
920 * Construct the bipartite decomposition.
921 * Sid-Ahmed-Ali Touati, Phd Thesis
922 * Register Pressure in Instruction Level Parallelism, p. 71
924 static void compute_bipartite_decomposition(rss_t *rss) {
925 pset *epk = new_pset(cmp_rss_edges, 10);
930 DBG((rss->dbg, LEVEL_1, "\tcomputing bipartite decomposition:\n"));
932 build_kill_edges(rss, epk);
934 foreach_plist(rss->nodes, el) {
935 ir_node *u_irn = plist_element_get_value(el);
936 rss_irn_t *u = get_rss_irn(rss, u_irn);
942 plist_element_t *el2;
944 rss_edge_t *kedge_root = NULL;
945 ir_node *t_irn, *s_irn;
946 ir_nodeset_iterator_t iter;
948 if (u->visited || u_irn == _sink)
951 DBG((rss->dbg, LEVEL_2, "\t\t%+F choosen:\n", u_irn));
953 cbc = obstack_alloc(phase_obst(&rss->ph), sizeof(*cbc));
956 /* initialize S_cb */
957 ir_nodeset_init_size(&cbc->parents, 5);
958 ir_nodeset_insert(&cbc->parents, u_irn);
959 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (init)\n", u_irn));
962 cbc->kill_edges = new_pset(cmp_rss_edges, 5);
964 /* each parent gets killed by at least one value from children */
966 /* T_cb = PK_successors(u) */
967 ir_nodeset_init_size(&cbc->children, 5);
968 foreach_plist(u->pkiller_list, el2) {
969 ir_nodeset_insert(&cbc->children, plist_element_get_value(el2));
970 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (init)\n", plist_element_get_value(el2)));
974 Now: insert the parents of all children into the parent set
975 and insert the children of all parents into the children set
976 until the sets don't change any more
978 while (p_change || c_change) {
979 ir_nodeset_iterator_t iter;
980 p_change = c_change = 0;
982 /* accumulate parents */
983 foreach_ir_nodeset(&cbc->children, t_irn, iter) {
984 foreach_pset(epk, k_edge) {
985 ir_node *val = k_edge->src;
987 if (k_edge->tgt == t_irn && ! ir_nodeset_contains(&cbc->parents, val)) {
988 ir_nodeset_insert(&cbc->parents, val);
990 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (killed by %+F)\n", val, t_irn));
995 /* accumulate children */
996 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
997 foreach_pset(epk, k_edge) {
998 ir_node *val = k_edge->tgt;
1000 if (k_edge->src == s_irn && ! ir_nodeset_contains(&cbc->children, val)) {
1001 ir_nodeset_insert(&cbc->children, val);
1003 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (kills %+F)\n", val, s_irn));
1009 /* mark all parent values as visited */
1010 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
1011 rss_irn_t *s = get_rss_irn(rss, s_irn);
1013 /* assure bipartite property */
1015 if (ir_nodeset_contains(&cbc->children, s_irn)) {
1016 ir_nodeset_remove(&cbc->children, s_irn);
1017 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F removed from to children\n", s_irn));
1023 foreach_pset(epk, k_edge) {
1024 if (ir_nodeset_contains(&cbc->parents, k_edge->src) &&
1025 ir_nodeset_contains(&cbc->children, k_edge->tgt)) {
1026 pset_insert(cbc->kill_edges, k_edge, HASH_RSS_EDGE(k_edge));
1028 Link all k_edges which are about to be removed together.
1029 Beware: pset_remove kills the iterator.
1031 k_edge->next = kedge_root;
1032 kedge_root = k_edge;
1036 /* remove all linked k_edges */
1037 for (; kedge_root; kedge_root = kedge_root->next) {
1038 pset_remove(epk, kedge_root, HASH_RSS_EDGE(kedge_root));
1041 /* verify the cbc */
1042 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
1045 foreach_pset(cbc->kill_edges, k_edge) {
1046 if (k_edge->src == s_irn) {
1048 pset_break(cbc->kill_edges);
1055 ir_fprintf(stderr, "Warning: parent %+F is not killed in current cbc\n", s_irn);
1058 assert(vrfy_ok && "Verification of CBC failed");
1060 /* add the connected bipartite component */
1061 if (ir_nodeset_size(&cbc->parents) > 0 &&
1062 ir_nodeset_size(&cbc->children) > 0 &&
1063 pset_count(cbc->kill_edges) > 0)
1064 pset_insert(rss->cbc_set, cbc, (unsigned)cbc->nr);
1065 DBG((rss->dbg, LEVEL_2, "\tbipartite component %d inserted:\n", cbc->nr));
1067 if (firm_dbg_get_mask(rss->dbg) & LEVEL_2)
1068 debug_print_cbc(rss->dbg, cbc);
1072 if (rss->opts->dump_flags & RSS_DUMP_CBC)
1073 debug_vcg_dump_bipartite(rss);
1079 * Select the child with the maximum cost.
1081 static child_t *select_child_max_cost(rss_t *rss, ir_nodeset_t *x, ir_nodeset_t *y, child_t *t, cbc_t *cbc) {
1083 ir_nodeset_iterator_t iter;
1084 float max_cost = -1.0f;
1086 DBG((rss->dbg, LEVEL_2, "\t\tcomputing children costs:\n"));
1088 foreach_ir_nodeset(&cbc->children, child, iter) {
1089 rss_irn_t *r_child = get_rss_irn(rss, child);
1090 int num_unkilled_parents = 0;
1091 int num_descendants;
1095 /* get the number of unkilled parents */
1096 foreach_pset(cbc->kill_edges, k_edge) {
1097 if (k_edge->tgt == child && ir_nodeset_contains(x, k_edge->src))
1098 ++num_unkilled_parents;
1101 cost = (float)num_unkilled_parents;
1103 num_descendants = plist_count(r_child->descendant_list) + ir_nodeset_size(y);
1105 if (num_descendants > 0)
1106 cost /= (float)num_descendants;
1108 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F, #desc %d, cost %.3f\n", child, num_descendants, cost));
1110 if (cost > max_cost) {
1121 * Remove all parents from x which are killed by t_irn.
1123 static void remove_covered_parents(rss_t *rss, ir_nodeset_t *x, ir_node *t_irn, cbc_t *cbc) {
1124 rss_irn_t *t = get_rss_irn(rss, t_irn);
1127 DBG((rss->dbg, LEVEL_2, "\t\tremoving parents covered by %+F:\n", t_irn));
1129 foreach_pset(cbc->kill_edges, k_edge) {
1130 if (k_edge->tgt == t_irn && ir_nodeset_contains(x, k_edge->src)) {
1131 ir_nodeset_remove(x, k_edge->src);
1132 plist_insert_back(t->parent_list, k_edge->src);
1133 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", k_edge->src));
1138 static void update_cumulated_descendent_values(rss_t *rss, ir_nodeset_t *y, ir_node *t_irn) {
1139 rss_irn_t *t = get_rss_irn(rss, t_irn);
1140 plist_element_t *el;
1142 DBG((rss->dbg, LEVEL_2, "\t\tupdating cumulated descendant value of %+F:\n", t_irn));
1144 foreach_plist(t->descendant_list, el) {
1145 ir_nodeset_insert(y, plist_element_get_value(el));
1146 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", plist_element_get_value(el)));
1151 * Greedy-k: a heuristics for the MMA problem
1153 static void compute_killing_function(rss_t *rss) {
1155 struct obstack obst;
1157 obstack_init(&obst);
1159 rss->cbc_set = pset_new_ptr(5);
1160 compute_bipartite_decomposition(rss);
1162 /* for all bipartite components do: */
1163 foreach_pset(rss->cbc_set, cbc) {
1167 ir_nodeset_iterator_t iter;
1168 child_t **sks = NEW_ARR_F(child_t *, 20);
1173 ir_nodeset_init_size(&x, 10);
1174 ir_nodeset_init_size(&y, 10);
1176 DBG((rss->dbg, LEVEL_1, "\tcomputing SKS for cbc %d:\n", cbc->nr));
1177 DBG((rss->dbg, LEVEL_2, "\t\tinitializing parents X:\n"));
1179 /* X = S_cb (all parents are initially uncovered) */
1180 foreach_ir_nodeset(&cbc->parents, p, iter) {
1181 ir_nodeset_insert(&x, p);
1182 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", p));
1185 /* while X not empty */
1186 while (ir_nodeset_size(&x) > 0) {
1187 child_t *t = obstack_alloc(&obst, sizeof(*t));
1188 memset(t, 0, sizeof(*t));
1190 t = select_child_max_cost(rss, &x, &y, t, cbc);
1192 if (cur_len >= cur_size) {
1193 ARR_EXTO(child_t *, sks, cur_size * 2);
1197 DBG((rss->dbg, LEVEL_2, "\t\tinsert child %+F (%.3f) into SKS at pos %d\n", t->irn, t->cost, cur_len));
1200 remove_covered_parents(rss, &x, t->irn, cbc);
1201 update_cumulated_descendent_values(rss, &y, t->irn);
1204 ARR_SHRINKLEN(sks, cur_len);
1206 /* sort SKS in increasing cost order */
1207 qsort(sks, cur_len, sizeof(sks[0]), cmp_child_costs);
1209 DBG((rss->dbg, LEVEL_2, "\tprocessing SKS for cbc %d:\n", cbc->nr));
1211 /* build killing function */
1212 for (i = cur_len - 1; i >= 0; --i) { /* loop over sks in decreasing cost order */
1213 child_t *t = sks[i];
1214 rss_irn_t *rt = get_rss_irn(rss, t->irn);
1215 plist_element_t *p_el;
1217 DBG((rss->dbg, LEVEL_3, "\t\t\tkiller %+F (%.3f):\n", t->irn, t->cost));
1219 /* kill all unkilled parents of t */
1220 foreach_plist(rt->parent_list, p_el) {
1221 ir_node *par = plist_element_get_value(p_el);
1222 rss_irn_t *rpar = get_rss_irn(rss, par);
1224 if (is_Sink(rpar->killer)) {
1225 rpar->killer = t->irn;
1226 DBG((rss->dbg, LEVEL_2, "\t\tkill %+F\n", rpar->irn));
1229 DBG((rss->dbg, LEVEL_3, "\t\t\tkeeping %+F as killer for %+F\n", rpar->killer, rpar->irn));
1234 ir_nodeset_destroy(&x);
1235 ir_nodeset_destroy(&y);
1239 if (rss->opts->dump_flags & RSS_DUMP_KILL)
1240 debug_vcg_dump_kill(rss);
1242 del_pset(rss->cbc_set);
1243 obstack_free(&obst, NULL);
1247 * Adds the edge src -> tgt to the dvg. Checks if reverse edge is already there (asserts).
1249 static inline void add_dvg_edge(rss_t *rss, dvg_t *dvg, const ir_node *src, const ir_node *tgt, int have_source) {
1250 rss_edge_t *dvg_edge;
1254 ir_nodeset_insert(&dvg->nodes, (ir_node *) src);
1256 assert(ir_nodeset_contains(&dvg->nodes, src) && "Wrong assumption");
1258 ir_nodeset_insert(&dvg->nodes, (ir_node *) tgt);
1260 key.src = (ir_node *) tgt;
1261 key.tgt = (ir_node *) src;
1262 assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
1264 key.src = (ir_node *) src;
1265 key.tgt = (ir_node *) tgt;
1266 if (NULL != pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
1267 /* add the edge to the DVG */
1268 dvg_edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*dvg_edge));
1270 dvg_edge->src = (ir_node *) src;
1271 dvg_edge->tgt = (ir_node *) tgt;
1272 dvg_edge->next = NULL;
1274 DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", src, tgt));
1275 pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
1280 * Computes the disjoint value DAG (DVG).
1281 * BEWARE: It is not made explicitly clear in the Touati paper,
1282 * but the DVG is meant to be build from the KILLING DAG
1284 static void compute_dvg(rss_t *rss, dvg_t *dvg) {
1285 plist_element_t *el;
1287 DBG((rss->dbg, LEVEL_1, "\tcomputing DVG:\n"));
1289 foreach_plist(rss->nodes, el) {
1290 ir_node *u_irn = plist_element_get_value(el);
1291 rss_irn_t *u = get_rss_irn(rss, u_irn);
1292 rss_irn_t *u_killer = get_rss_irn(rss, u->killer);
1295 /* TODO: omit nodes only having sink as pkiller and killing no one */
1297 /* add an edge to killer */
1298 add_dvg_edge(rss, dvg, u_irn, u->killer, 0);
1300 if (is_Sink(u->killer))
1303 /* We add an edge to every killer, from where we could be reached. */
1304 for (i = ARR_LEN_SAFE(u_killer->descendants) - 1; i >= 0; --i) {
1305 add_dvg_edge(rss, dvg, u_irn, u_killer->descendants[i], 1);
1310 foreach_plist(rss->nodes, el2) {
1311 ir_node *v_irn = plist_element_get_value(el2);
1314 There is an edge (u, v) in the DVG iff v is a descendant of the killer(u).
1316 if (BSEARCH_IRN_ARR(v_irn, u_kill->descendants)) {
1317 rss_edge_t *dvg_edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*dvg_edge));
1320 /* insert the user into the DVG and append it to the user list of u */
1321 ir_nodeset_insert(&dvg->nodes, v_irn);
1322 if (! plist_has_value(u->dvg_user_list, v_irn))
1323 plist_insert_back(u->dvg_user_list, v_irn);
1325 dvg_edge->src = u_irn;
1326 dvg_edge->tgt = v_irn;
1327 dvg_edge->next = NULL;
1332 assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
1334 /* add the edge to the DVG */
1335 DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", u_irn, v_irn));
1336 pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
1342 if (rss->opts->dump_flags & RSS_DUMP_DVG)
1343 debug_vcg_dump_dvg(rss, dvg);
1347 * Updates the dvg structure when a serialization edge from src -> tgt is added.
1349 static void update_dvg(rss_t *rss, dvg_t *dvg, rss_irn_t *src, rss_irn_t *tgt) {
1352 rss_edge_t **arr = ALLOCAN(rss_edge_t*, pset_count(dvg->edges));
1355 Add an edge from serialization target to serialization src:
1356 src cannot be alive with target
1358 add_dvg_edge(rss, dvg, tgt->irn, src->irn, 0);
1360 /* Add edges to src's descendants as well, they also getting serialized. */
1361 for (i = ARR_LEN_SAFE(src->descendants) - 1; i >= 0; --i) {
1362 add_dvg_edge(rss, dvg, tgt->irn, src->descendants[i], 1);
1365 /* We also have to add edges from targets predecessors in dvg */
1367 /* We cannot insert elements into set over which we iterate ... */
1368 foreach_pset(dvg->edges, edge) {
1369 if (edge->tgt == tgt->irn) {
1374 for (i = 0; i < idx; ++i) {
1376 add_dvg_edge(rss, dvg, edge->src, src->irn, 1);
1377 for (j = ARR_LEN_SAFE(src->descendants) - 1; j >= 0; --j) {
1378 add_dvg_edge(rss, dvg, edge->src, src->descendants[j], 1);
1385 * Accumulate all descendants for root into list.
1387 static void accumulate_dvg_descendant_values(rss_t *rss, rss_irn_t *root, plist_t *list) {
1388 if (plist_count(root->dvg_user_list) > 0) {
1389 plist_element_t *el;
1391 foreach_plist(root->dvg_user_list, el) {
1392 ir_node *v_irn = plist_element_get_value(el);
1393 rss_irn_t *v = get_rss_irn(rss, v_irn);
1395 /* add v as descendant */
1396 if (! plist_has_value(list, v_irn)) {
1397 plist_insert_back(list, v_irn);
1398 DBG((rss->dbg, DEBUG_DVG, "\t\t\tadd DVG descendant %+F\n", v_irn));
1401 /* accumulate v's descendants */
1402 accumulate_dvg_descendant_values(rss, v, list);
1408 * Builds the list of potential killers for each node
1410 * Needs the descendant list for all user as sorted array.
1412 static void build_dvg_pkiller_list(rss_t *rss, dvg_t *dvg) {
1413 ir_nodeset_iterator_t iter;
1416 foreach_nodeset(&dvg->nodes, irn, iter) {
1417 rss_irn_t *node = get_rss_irn(rss, irn);
1418 plist_element_t *el, *el2;
1420 DBG((rss->dbg, DEBUG_DVG, "\t\tbuilding pkiller list for %+F\n", irn));
1422 /* check each user */
1423 foreach_plist(node->dvg_user_list, el) {
1424 ir_node *u_irn = plist_element_get_value(el);
1426 /* is the current user u_irn not a descendant of any other user -> pkiller */
1427 foreach_plist(node->dvg_user_list, el2) {
1428 ir_node *v_irn = plist_element_get_value(el2);
1429 rss_irn_t *v = get_rss_irn(rss, v_irn);
1432 ! BSEARCH_IRN_ARR(u_irn, v->dvg_desc) &&
1433 ! plist_has_value(node->dvg_pkiller_list, u_irn))
1435 plist_insert_back(node->dvg_pkiller_list, u_irn);
1436 DBG((rss->dbg, DEBUG_DVG, "\t\t\tadd DVG pkiller %+F\n", u_irn));
1441 node->dvg_pkiller = build_sorted_array_from_list(node->dvg_pkiller_list, phase_obst(&rss->ph));
1445 if (firm_dbg_get_mask(rss->dbg) & DEBUG_DVG)
1446 debug_vcg_dump_dvg_pkiller(rss, dvg);
1453 * Compute the maximal antichain of the current DVG.
1454 * This is a reimplementation of the MAXIMAL_ANTI_CHAIN function
1455 * from the DDG library 1.1 (DAG.cpp).
1457 static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration) {
1458 int n = ir_nodeset_size(&dvg->nodes);
1459 int *assignment = ALLOCAN(int, n);
1460 int *assignment_rev = ALLOCAN(int, n);
1461 int *idx_map = ALLOCAN(int, n);
1462 hungarian_problem_t *bp;
1463 ir_nodeset_t *values, *temp;
1464 ir_nodeset_iterator_t iter;
1466 int i, j, cost, cur_chain, res;
1467 rss_edge_t *dvg_edge;
1469 #define MAP_IDX(irn) bsearch_for_index(get_irn_idx(irn), idx_map, n, 1)
1471 if (pset_count(dvg->edges) == 0)
1474 bp = hungarian_new(n, n, HUNGARIAN_MATCH_NORMAL);
1477 At first, we build an index map for the nodes in the DVG,
1478 because we cannot use the irn idx therefore as the resulting
1479 bipartite data structure would have around 1.2GB.
1480 So we limit the size to the number of nodes we have in the DVG
1481 and build a sorted index map for their irn indices.
1484 foreach_ir_nodeset(&dvg->nodes, u_irn, iter) {
1485 idx_map[i++] = get_irn_idx(u_irn);
1487 qsort(idx_map, n, sizeof(idx_map[0]), cmp_int);
1489 foreach_pset(dvg->edges, dvg_edge) {
1490 int idx_u = MAP_IDX(dvg_edge->src);
1491 int idx_v = MAP_IDX(dvg_edge->tgt);
1493 /* add the entry to the bipartite data structure */
1494 hungarian_add(bp, idx_u, idx_v, 1);
1495 DBG((rss->dbg, LEVEL_3, "\t\t\tadd %d (%+F) -> %d (%+F)\n",
1496 idx_u, dvg_edge->src, idx_v, dvg_edge->tgt));
1500 Add a bipartite entry for each pair of nodes (u, v), where exists a
1501 path in the DVG from u to v, ie. connect all descendants(v) to v.
1502 desc_dvg(v) = accumulated descendants of all z in dvg_user_list(v)
1504 foreach_ir_nodeset(&dvg->nodes, u_irn, iter) {
1505 rss_irn_t *u = get_rss_irn(rss, u_irn);
1506 int idx_u_irn = MAP_IDX(u_irn);
1508 DBG((rss->dbg, DEBUG_DVG, "\t\tcomputing DVG descendants of %+F:\n", u_irn));
1510 //plist_clear(u->dvg_desc_list);
1511 //accumulate_dvg_descendant_values(rss, u, u->dvg_desc_list);
1514 FIXME: The array is build on the phase obstack and we cannot free the data.
1515 So the array get as many times allocated as this function is called.
1518 /* build the sorted array for faster searches */
1519 //u->dvg_desc = build_sorted_array_from_list(u->dvg_desc_list, phase_obst(&rss->ph));
1521 DBG((rss->dbg, DEBUG_MAX_AC, "\t\tadding bipartite entries of %+F:\n", u_irn));
1523 /* add the bipartite entries for all descendants */
1524 for (i = ARR_LEN_SAFE(u->dvg_desc) - 1; i >= 0; --i) {
1525 rss_irn_t *desc = get_rss_irn(rss, u->dvg_desc[i]);
1526 int idx_desc = MAP_IDX(u->dvg_desc[i]);
1528 /* add the entry to the bipartite data structure */
1529 hungarian_add(bp, idx_u_irn, idx_desc, 1);
1530 DBG((rss->dbg, DEBUG_MAX_AC, "\t\t\tadd %d (%+F) -> %d (%+F)\n",
1531 idx_u_irn, u_irn, idx_desc, u->dvg_desc[i]));
1538 /* We want maximum cardinality matching */
1539 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
1542 DBG((rss->dbg, DEBUG_DVG, "\t\tcomputing DVG pkiller:\n"));
1543 /* beware: the following function needs the dvg_desc array */
1544 build_dvg_pkiller_list(rss, dvg);
1547 DBG((rss->dbg, LEVEL_2, "\t\tcomputing bipartite matching\n"));
1549 The maximum cardinality bipartite matching gives us the minimal
1550 chain partition, which corresponds to the maximum anti chains.
1552 res = hungarian_solve(bp, assignment, &cost, 1);
1553 assert(res == 0 && "Bipartite matching failed!");
1556 memset(assignment_rev, -1, n * sizeof(assignment_rev[0]));
1558 /* build the reverse assignment, ie. foreach i -> j, add j -> i */
1559 for (i = 0; i < n; ++i) {
1560 if (assignment[i] >= 0) {
1561 int j = assignment[i];
1562 assignment_rev[j] = i;
1566 DBG((rss->dbg, LEVEL_2, "\t\tgot assignment with cost %d\n", cost));
1567 DBG((rss->dbg, LEVEL_3, "\t\t\tassignment --- reverse assignment\n", cost));
1568 for (i = 0; i < n; ++i) {
1569 DBG((rss->dbg, LEVEL_3, "\t\t\t%3d -> %3d %3d -> %3d\n", i, assignment[i], i, assignment_rev[i]));
1572 values = XMALLOC(ir_nodeset_t);
1573 ir_nodeset_init_size(values, 10);
1575 /* Construction of the minimal chain partition */
1576 for (j = 0; j < n; ++j) {
1577 /* check nodes, which did not occur as target */
1578 if (assignment_rev[j] == -1) {
1579 int xj = idx_map[j];
1580 ir_node *xj_irn = get_idx_irn(rss->irg, xj);
1581 rss_irn_t *xj_rss = get_rss_irn(rss, xj_irn);
1582 chain_t *c = obstack_alloc(phase_obst(&rss->ph), sizeof(*c));
1585 /* there was no source for j -> we have a source of a new chain */
1586 ir_nodeset_insert(values, xj_irn);
1588 c->elements = plist_obstack_new(phase_obst(&rss->ph));
1589 c->nr = cur_chain++;
1590 plist_insert_back(c->elements, xj_irn);
1594 DBG((rss->dbg, LEVEL_2, "\t\tstarting chain %d:\n", c->nr));
1595 DBG((rss->dbg, LEVEL_2, "\t\t\t%+F (%d)", xj_irn, j));
1597 /* follow chain, having j as source */
1599 while (assignment[source] >= 0) {
1600 int target = assignment[source];
1601 int irn_idx = idx_map[target];
1602 ir_node *irn = get_idx_irn(rss->irg, irn_idx);
1603 rss_irn_t *node = get_rss_irn(rss, irn);
1605 plist_insert_back(c->elements, irn);
1608 DB((rss->dbg, LEVEL_2, " -> %+F (%d)", irn, target));
1610 /* new source = last target */
1614 DB((rss->dbg, LEVEL_2, "\n"));
1619 Computing the maximal antichain: Select an element from each
1620 chain such, such it is parallel with the others.
1622 DBG((rss->dbg, LEVEL_1, "\t\tcomputing set of saturation values (MAX AC)\n"));
1623 DBG((rss->dbg, LEVEL_3, "\t\tstarting with:\n"));
1626 if (firm_dbg_get_mask(rss->dbg) & LEVEL_3)
1627 dump_nodeset(values, "\t\t\t");
1633 We need an explicit array for the values as
1634 we cannot iterate multiple times over the same
1635 set at the same time. :-(((((
1636 TODO Matze: now we can, so rewrite this...
1638 int n = ir_nodeset_size(values);
1640 ir_node **val_arr = NEW_ARR_F(ir_node *, n);
1642 foreach_ir_nodeset(values, u_irn, iter)
1643 val_arr[i++] = u_irn;
1646 ir_nodeset_destroy(temp);
1650 temp = XMALLOC(ir_nodeset_t);
1651 ir_nodeset_init_size(temp, 10);
1653 /* Select all nodes from current value set, having another node in the set as descendant. */
1654 for (i = 0; i < n; ++i) {
1655 rss_irn_t *u = get_rss_irn(rss, val_arr[i]);
1657 for (j = 0; j < n; ++j) {
1661 key.src = val_arr[i];
1662 key.tgt = val_arr[j];
1664 if (pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
1665 /* v[j] is descendant of u -> remove u and break */
1666 ir_nodeset_insert(temp, (ir_node *) u->irn);
1667 ir_nodeset_remove(values, u->irn);
1669 DBG((rss->dbg, LEVEL_3, "\t\t\tremoving %+F from values, adding it to temp\n", u->irn));
1677 /* Try to insert the chain predecessor of all selected u's */
1678 foreach_ir_nodeset(temp, u_irn, iter) {
1679 rss_irn_t *u = get_rss_irn(rss, u_irn);
1680 chain_t *c = u->chain;
1681 plist_element_t *el = plist_find_value(c->elements, u_irn);
1683 assert(el && "Missing element in chain!");
1685 /* If u has predecessor in chain: insert the predecessor */
1686 if (el == plist_element_get_prev(el)) {
1687 ir_nodeset_insert(values, plist_element_get_value(el));
1688 DBG((rss->dbg, LEVEL_3, "\t\t\tadding %+F to values\n", plist_element_get_value(el)));
1694 } while (ir_nodeset_size(temp) > 0);
1696 DBG((rss->dbg, LEVEL_2, "\t\tfinal set:\n"));
1698 if (firm_dbg_get_mask(rss->dbg) & LEVEL_2) {
1699 dump_nodeset(values, "\t\t\t");
1703 if (rss->opts->dump_flags & RSS_DUMP_MAXAC)
1704 debug_vcg_dump_pkg(rss, values, iteration);
1707 ir_nodeset_destroy(temp);
1717 * Computes the best serialization between two nodes of sat_vals.
1719 static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nodeset_t *sat_vals, serialization_t *ser, int num_regs) {
1720 int n = ir_nodeset_size(sat_vals);
1721 int n_idx = ARR_LEN_SAFE(rss->idx_map);
1723 ir_node **val_arr = ALLOCAN(ir_node*, n);
1724 bitset_t *bs_sv = bitset_alloca(n_idx);
1725 bitset_t *bs_vdesc = bitset_alloca(n_idx);
1726 bitset_t *bs_tmp = bitset_alloca(n_idx);
1727 bitset_t *bs_ukilldesc = bitset_alloca(n_idx);
1728 int best_benefit = INT_MAX;
1729 int best_omega2 = INT_MAX;
1730 int best_benefit_omega20 = INT_MAX;
1734 ir_nodeset_iterator_t iter;
1735 rss_edge_t min_benefit_edge = {NULL, NULL, NULL};
1736 rss_edge_t min_omega20_edge = {NULL, NULL, NULL};
1737 rss_irn_t *ser_u_omega1 = NULL, *ser_v_omega1 = NULL;
1738 rss_irn_t *ser_u_omega20 = NULL, *ser_v_omega20 = NULL;
1740 DBG((rss->dbg, LEVEL_1, "\tcomputing admissible serializations:\n"));
1743 We need an explicit array for the values as
1744 we cannot iterate multiple times over the same
1745 set at the same time. :-(((((
1748 foreach_ir_nodeset(sat_vals, irn, iter) {
1750 bitset_set(bs_sv, BLOCK_IDX_MAP(rss, irn));
1754 We build all admissible serializations and remember the best found so far.
1757 if v in pkiller(u): add edge from v to all other pkiller(u)
1758 else: for all vv in pkiller(u): add edge from v to vv if there exists no path from vv to v
1762 A node is unserializable if:
1763 - it has only one killer and this one is Sink
1764 - it kills no other values
1765 In this case there is no serialization which could
1766 reduce the registerpressure
1768 #define IS_UNSERIALIZABLE_NODE(rss_node) \
1771 (plist_count(rss_node->pkiller_list) == 1) && \
1772 is_Sink(rss_node->killer) && \
1773 (rss_node->kill_count == 0) \
1775 be_is_Barrier(rss_node->irn) || \
1776 be_is_Keep(rss_node->irn) \
1779 /* for all u in sat_vals */
1780 for (i = 0; i < n; ++i) {
1781 rss_irn_t *u = get_rss_irn(rss, val_arr[i]);
1782 plist_element_t *el;
1784 /* ignore nodes where serialization does not help */
1785 if (IS_UNSERIALIZABLE_NODE(u)) {
1786 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", u->irn));
1790 /* accumulate all descendants of all pkiller(u) */
1791 bitset_clear_all(bs_ukilldesc);
1792 foreach_plist(u->pkiller_list, el) {
1793 ir_node *irn = plist_element_get_value(el);
1794 rss_irn_t *node = get_rss_irn(rss, irn);
1797 bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, irn));
1801 for (k = ARR_LEN_SAFE(node->descendants) - 1; k >= 0; --k) {
1802 if (! is_Sink(node->descendants[k]))
1803 bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, node->descendants[k]));
1807 /* for all v in sat_vals */
1808 for (j = 0; j < n; ++j) {
1809 ir_node *v_irn = val_arr[j];
1810 rss_irn_t *v = get_rss_irn(rss, v_irn);
1811 unsigned v_height = get_irn_height(rss->h, v_irn);
1812 int omega1, omega2, is_pkiller;
1814 /* v cannot be serialized with itself
1815 * ignore nodes where serialization does not help */
1816 if (i == j || IS_UNSERIALIZABLE_NODE(v)) {
1817 #ifdef DEBUG_libfirm
1819 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", v->irn));
1824 /* get descendants of v */
1825 bitset_clear_all(bs_vdesc);
1826 bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v_irn));
1827 for (k = ARR_LEN_SAFE(v->descendants) - 1; k >= 0; --k) {
1828 if (! is_Sink(v->descendants[k]))
1829 bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v->descendants[k]));
1832 /* if v is in pkiller(u) */
1833 is_pkiller = plist_has_value(u->pkiller_list, v_irn);
1835 /* for all vv in pkiller(u) */
1836 foreach_plist(u->pkiller_list, el) {
1837 ir_node *vv_irn = plist_element_get_value(el);
1840 if (is_Sink(vv_irn) || is_cfop(vv_irn))
1844 add_edge = vv_irn != v_irn && skip_Proj(vv_irn) != skip_Proj(v_irn);
1846 add_edge = ! heights_reachable_in_block(rss->h, skip_Proj(vv_irn), skip_Proj(v_irn));
1849 As we add an edge from vv -> v, we have to make sure,
1850 that there exists no path from v to vv.
1854 unsigned vv_height = get_irn_height(rss->h, vv_irn);
1855 unsigned critical_path_cost;
1859 mu1 = | descendants(v) cut sat_vals |
1860 the number of saturating values which cannot
1861 be simultaneously alive with u
1863 bitset_copy(bs_tmp, bs_vdesc);
1864 mu1 = bitset_popcnt(bitset_and(bs_tmp, bs_sv));
1867 mu2 = | accum_desc_all_pkiller(u) without descendants(v) |
1870 bitset_copy(bs_tmp, bs_ukilldesc);
1871 mu2 = bitset_popcnt(bitset_andnot(bs_tmp, bs_vdesc));
1877 /* omega1 = mu1 - mu2 */
1883 /* omega2 = increase of critical path */
1884 critical_path_cost =
1885 v_height /* longest path from v to sink */
1886 + rss->max_height - vv_height /* longest path from source to vv */
1890 If critical_path_cost > max_height -> the new edge
1891 would increase the longest critical path by the difference.
1893 omega2 = critical_path_cost > rss->max_height ? critical_path_cost - rss->max_height : 0;
1895 /* this keeps track of the edge with the best benefit */
1896 if (omega1 >= num_regs - n && omega1 < best_benefit) {
1897 min_benefit_edge.src = v_irn;
1898 min_benefit_edge.tgt = vv_irn;
1903 best_benefit = omega1;
1904 ser->new_killer = is_pkiller;
1907 /* this keeps track of the edge with the best omega1 costs where omega2 == 0 */
1908 if (omega2 == 0 && omega1 >= num_regs - n && omega1 < best_benefit_omega20) {
1909 min_omega20_edge.src = v_irn;
1910 min_omega20_edge.tgt = vv_irn;
1915 best_benefit_omega20 = omega1;
1916 ser->new_killer = is_pkiller;
1919 best_omega2 = MIN(best_omega2, omega2);
1921 DBG((rss->dbg, LEVEL_2, "\t\tfound %+F -> %+F (w1 %d, w2 %d)\n",
1922 v_irn, vv_irn, omega1, omega2));
1924 } /* for all vv in pkiller(u) */
1925 } /* for all v in sat_vals */
1926 } /* for all u in sat_vals */
1931 if (best_omega2 == 0) {
1932 ser->u = ser_u_omega20;
1933 ser->v = ser_v_omega20;
1934 ser->edge->src = min_omega20_edge.src;
1935 ser->edge->tgt = min_omega20_edge.tgt;
1936 ser->omega1 = best_benefit_omega20;
1937 ser->omega2 = best_omega2;
1940 ser->u = ser_u_omega1;
1941 ser->v = ser_v_omega1;
1942 ser->edge->src = min_benefit_edge.src;
1943 ser->edge->tgt = min_benefit_edge.tgt;
1944 ser->omega1 = best_benefit;
1945 ser->omega2 = best_omega2;
1950 #undef IS_UNSERIALIZABLE_NODE
1954 * Perform the value serialization heuristic and add all
1955 * computed serialization edges as dependencies to the irg.
1957 static void perform_value_serialization_heuristic(rss_t *rss) {
1958 bitset_t *arch_nonign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls));
1959 bitset_t *abi_ign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls));
1960 unsigned available_regs, iteration;
1962 ir_nodeset_t *sat_vals;
1963 pset *ser_set = new_pset(cmp_rss_edges, 20);
1965 /* available_regs = R = |arch_non_ignore_regs cut ~abi_ignore_regs| */
1966 arch_put_non_ignore_regs(rss->cls, arch_nonign_bs);
1967 be_abi_put_ignore_regs(rss->abi, rss->cls, abi_ign_bs);
1968 bitset_andnot(arch_nonign_bs, abi_ign_bs);
1969 available_regs = bitset_popcnt(arch_nonign_bs);
1970 //num_live = pset_count(rss->live_block);
1971 //available_regs -= num_live < available_regs ? num_live : 0;
1973 DBG((rss->dbg, LEVEL_1, "\n\t#available regs: %d\n\n", available_regs));
1976 At first we need to compute the disjoint value DAG (DVG = {V, E_dv}).
1977 V = set of all nodes we are currently interested in
1978 E_dv = there is an edge from u to v iff v is a descendant of killer(u), forall u, v in V
1980 ir_nodeset_init_size(&dvg.nodes, plist_count(rss->nodes));
1981 dvg.edges = new_pset(cmp_rss_edges, plist_count(rss->nodes) * 5);
1982 compute_dvg(rss, &dvg);
1985 Then we perform the heuristic serialization algorithm
1986 on the DVG which gives us all necessary serialization
1989 DBG((rss->dbg, LEVEL_1, "\tcomputing maximal antichain:\n"));
1991 sat_vals = compute_maximal_antichain(rss, &dvg, iteration++);
1992 while (sat_vals && (ir_nodeset_size(sat_vals) > available_regs)) {
1993 serialization_t *ser, best_ser;
1994 rss_edge_t *edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*edge));
1995 ir_node *dep_src, *dep_tgt;
1997 best_ser.edge = edge;
1998 ser = compute_best_admissible_serialization(rss, sat_vals, &best_ser, available_regs);
2000 DBG((rss->dbg, LEVEL_1, "\tcurrent register saturation %d, target %d\n", ir_nodeset_size(sat_vals), available_regs));
2003 DBG((rss->dbg, LEVEL_1, "\tno RS improving serialization found, breaking at iteration %d\n", iteration));
2007 /* Insert the serialization as dependency edge into the irg. */
2008 DBG((rss->dbg, LEVEL_1, "\tserializing %+F -> %+F with edge %+F -> %+F and cost %d, %d\n",
2009 ser->u->irn, ser->v->irn, ser->edge->src, ser->edge->tgt, ser->omega1, ser->omega2));
2011 if (pset_find(ser_set, ser->edge, HASH_RSS_EDGE(ser->edge)))
2012 ir_printf("WARNING: serialization %+F -> %+F computed twice!\n", ser->edge->src, ser->edge->tgt);
2015 pset_insert(ser_set, ser->edge, HASH_RSS_EDGE(ser->edge));
2017 /* update the dvg */
2018 update_dvg(rss, &dvg, ser->v, ser->u);
2019 update_dvg(rss, &dvg, get_rss_irn(rss, ser->edge->src), get_rss_irn(rss, ser->edge->tgt));
2020 if(sat_vals != NULL) {
2021 ir_nodeset_destroy(sat_vals);
2025 dep_src = skip_Proj(ser->edge->src);
2026 dep_tgt = ser->edge->tgt;
2027 add_irn_dep(dep_src, dep_tgt);
2029 /* Update descendants, consumer and pkillers of the target */
2030 update_node_info(rss, ser->edge->tgt, ser->edge->src);
2032 /* TODO: try to find a cheaper way for updating height information */
2033 rss->max_height = heights_recompute_block(rss->h, rss->block);
2035 /* Recompute the antichain for next serialization */
2036 DBG((rss->dbg, LEVEL_1, "\tre-computing maximal antichain:\n"));
2037 sat_vals = compute_maximal_antichain(rss, &dvg, iteration++);
2040 ir_nodeset_destroy(&dvg.nodes);
2041 del_pset(dvg.edges);
2045 * Do initial calculations for a block.
2047 static void process_block(ir_node *block, void *env) {
2050 const ir_edge_t *edge;
2052 phase_init(&rss->ph, "rss block preprocessor", rss->irg, PHASE_DEFAULT_GROWTH, init_rss_irn, NULL);
2054 DBG((rss->dbg, LEVEL_1, "preprocessing block %+F\n", block));
2057 /* build an index map for all nodes in the current block */
2059 n = get_irn_n_edges(block);
2060 NEW_ARR_A(int *, rss->idx_map, n);
2061 foreach_out_edge(block, edge) {
2062 ir_node *irn = get_edge_src_irn(edge);
2063 rss->idx_map[i++] = get_irn_idx(irn);
2065 qsort(rss->idx_map, n, sizeof(rss->idx_map[0]), cmp_int);
2066 rss->max_height = heights_recompute_block(rss->h, block);
2068 /* loop over all register classes */
2069 for (i = arch_env_get_n_reg_class(rss->arch_env) - 1; i >= 0; --i) {
2070 const arch_register_class_t *cls = arch_env_get_reg_class(rss->arch_env, i);
2073 DBG((rss->dbg, LEVEL_1, "register class %s\n", arch_register_class_name(cls)));
2075 /* Get all live value at end of Block having current register class */
2076 ir_nodeset_init(&rss->live_block);
2077 be_liveness_end_of_block(rss->liveness, rss->cls, rss->block, &rss->live_block);
2079 /* reset the list of interesting nodes */
2080 plist_clear(rss->nodes);
2081 plist_insert_back(rss->nodes, _sink);
2083 /* collect all nodes having a certain register class */
2084 foreach_out_edge(block, edge) {
2085 ir_node *irn = get_edge_src_irn(edge);
2086 ir_mode *mode = get_irn_mode(irn);
2090 - mode_T nodes (the projs are asked)
2091 - mode_X nodes (control flow nodes are always scheduled last)
2092 - Keeps (they are always immediately scheduled)
2093 - Phi (same as Keep)
2095 if (mode == mode_T || mode == mode_X || is_Phi(irn))
2099 In case of a proj, we skip
2100 - Barrier (they are a Barrier :)
2102 - the Proj itself, as it's scheduled always with it's super node
2105 ir_node *pred = get_Proj_pred(irn);
2106 if (be_is_Barrier(pred) || is_Start(pred))
2110 /* calculate the descendants and consumer for each node in the block */
2111 collect_node_info(rss, skip_Proj(irn));
2113 if (be_is_Keep(irn))
2116 if (!arch_irn_is_ignore(irn) &&
2117 arch_get_irn_reg_class_out(irn) == cls) {
2118 plist_insert_back(rss->nodes, skip_Proj(irn));
2123 /* compute the potential killing set PK(G) */
2124 compute_pkill_set(rss);
2126 /* compute the killing function k* */
2127 compute_killing_function(rss);
2130 Compute the heuristic value serialization and
2131 add the necessary dependencies to the irg.
2133 perform_value_serialization_heuristic(rss);
2135 ir_nodeset_destroy(&rss->live_block);
2138 phase_free(&rss->ph);
2142 * Register the options.
2144 void be_init_schedrss(void) {
2145 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
2146 lc_opt_entry_t *sched_grp = lc_opt_get_grp(be_grp, "sched");
2147 lc_opt_entry_t *rss_grp = lc_opt_get_grp(sched_grp, "rss");
2149 lc_opt_add_table(rss_grp, rss_option_table);
2152 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_schedrss);
2155 * Preprocess the irg for scheduling.
2157 void rss_schedule_preparation(be_irg_t *birg) {
2158 ir_graph *irg = be_get_birg_irg(birg);
2161 FIRM_DBG_REGISTER(rss.dbg, "firm.be.sched.rss");
2163 //firm_dbg_set_mask(rss.dbg, LEVEL_1 | LEVEL_2 | LEVEL_3);
2165 init_rss_special_nodes(irg);
2168 rss.arch_env = be_get_birg_arch_env(birg);
2169 rss.abi = birg->abi;
2170 rss.h = heights_new(irg);
2171 rss.nodes = plist_new();
2172 rss.opts = &rss_options;
2173 rss.liveness = be_liveness(irg);
2174 be_liveness_assure_sets(rss.liveness);
2175 irg_block_walk_graph(irg, NULL, process_block, &rss);
2176 heights_free(rss.h);
2177 plist_free(rss.nodes);
2178 be_liveness_free(rss.liveness);
2180 if (birg->main_env->options->dump_flags & DUMP_SCHED)
2181 be_dump(rss.irg, "-rss", dump_ir_block_graph);