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 #define get_rss_irn(rss, irn) (phase_get_or_set_irn_data(&rss->ph, irn))
171 * We need some special nodes:
172 * a source and a sink for all live-in and live-out values of a block
180 /** The opcode of the rss_Source node once allocated. */
181 static ir_op *op_rss_Source;
182 /** The opcode of the rss_Sink node once allocated. */
183 static ir_op *op_rss_Sink;
185 /** The rss_Source node of the current graph. */
186 static ir_node *_source = NULL;
187 /** The rss_Sink node of the current graph. */
188 static ir_node *_sink = NULL;
190 #define is_Source(irn) ((irn) == _source)
191 #define is_Sink(irn) ((irn) == _sink)
195 RSS_DUMP_CBC = 1 << 0,
196 RSS_DUMP_PKG = 1 << 1,
197 RSS_DUMP_KILL = 1 << 2,
198 RSS_DUMP_DVG = 1 << 3,
199 RSS_DUMP_MAXAC = 1 << 4,
200 RSS_DUMP_ALL = (RSS_DUMP_MAXAC << 1) - 1,
203 static rss_opts_t rss_options = {
207 static const lc_opt_enum_int_items_t dump_items[] = {
208 { "none", RSS_DUMP_NONE },
209 { "cbc", RSS_DUMP_CBC },
210 { "pkg", RSS_DUMP_PKG },
211 { "kill", RSS_DUMP_KILL },
212 { "dvg", RSS_DUMP_DVG },
213 { "maxac", RSS_DUMP_MAXAC },
214 { "all", RSS_DUMP_ALL },
218 static lc_opt_enum_int_var_t dump_var = {
219 &rss_options.dump_flags, dump_items
222 static const lc_opt_table_entry_t rss_option_table[] = {
223 LC_OPT_ENT_ENUM_MASK("dump", "dump phases", &dump_var),
227 /******************************************************************************
229 * | | | | / _| | | (_)
230 * | |__ ___| |_ __ ___ _ __ | |_ _ _ _ __ ___| |_ _ ___ _ __ ___
231 * | '_ \ / _ \ | '_ \ / _ \ '__| | _| | | | '_ \ / __| __| |/ _ \| '_ \/ __|
232 * | | | | __/ | |_) | __/ | | | | |_| | | | | (__| |_| | (_) | | | \__ \
233 * |_| |_|\___|_| .__/ \___|_| |_| \__,_|_| |_|\___|\__|_|\___/|_| |_|___/
236 ******************************************************************************/
239 * Acquire opcodes if needed and create source and sink nodes.
241 static void init_rss_special_nodes(ir_graph *irg)
245 if (op_rss_Source == NULL) {
246 int iro_rss_base = get_next_ir_opcodes(iro_rss_last);
247 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);
248 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);
250 block = get_irg_start_block(irg);
251 _source = new_ir_node(NULL, irg, block, op_rss_Source, mode_ANY, 0, NULL);
252 _sink = new_ir_node(NULL, irg, block, op_rss_Sink, mode_ANY, 0, NULL);
255 static int cmp_int(const void *a, const void *b)
260 return QSORT_CMP(*i1, *i2);
263 static int cmp_child_costs(const void *a, const void *b)
265 const child_t *c1 = a;
266 const child_t *c2 = b;
268 return QSORT_CMP(c1->cost, c2->cost);
271 static int cmp_irn_idx(const void *a, const void *b)
273 const ir_node *n1 = *(ir_node **)a;
274 const ir_node *n2 = *(ir_node **)b;
276 return QSORT_CMP(get_irn_idx(n1), get_irn_idx(n2));
279 static int cmp_rss_edges(const void *a, const void *b)
281 const rss_edge_t *e1 = a;
282 const rss_edge_t *e2 = b;
284 return (e1->src != e2->src) || (e1->tgt != e2->tgt);
287 static int bsearch_for_index(int key, int *arr, size_t len, int force)
292 while (right >= left) {
293 int idx = (left + right) / 2;
297 else if (key > arr[idx])
304 assert(0 && "Something is wrong, key not found.");
308 static const ir_node **build_sorted_array_from_list(plist_t *irn_list, struct obstack *obst)
312 int len = plist_count(irn_list);
313 const ir_node **arr = (const ir_node**)NEW_ARR_D(ir_node*, obst, len);
315 /* copy the list into the array */
316 foreach_plist(irn_list, el) {
317 arr[i++] = plist_element_get_value(el);
320 /* sort the array by node index */
321 /* HACK cast for MSVC */
322 qsort((void*)arr, len, sizeof(arr[0]), cmp_irn_idx);
327 /*****************************************************
330 * __| | ___| |__ _ _ __ _ __ _ _ _ __ __ _
331 * / _` |/ _ \ '_ \| | | |/ _` |/ _` | | '_ \ / _` |
332 * | (_| | __/ |_) | |_| | (_| | (_| | | | | | (_| |
333 * \__,_|\___|_.__/ \__,_|\__, |\__, |_|_| |_|\__, |
337 *****************************************************/
340 static void dump_nodeset(ir_nodeset_t *ns, const char *prefix)
342 ir_nodeset_iterator_t iter;
345 ir_nodeset_iterator_init(&iter, ns);
346 while ( (irn = ir_nodeset_iterator_next(&iter)) != NULL ) {
347 ir_fprintf(stderr, "%s%+F\n", prefix, irn);
352 static void build_file_name(rss_t *rss, const char *suffix, size_t suf_len, char *buf, size_t len)
354 const char *irg_name;
357 irg_name = get_entity_name(get_irg_entity(rss->irg));
358 snprintf(buf, len - suf_len, "%s-%s-block-%ld",
359 irg_name, arch_register_class_name(rss->cls), get_irn_node_nr(rss->block));
363 /* Dumps all collected bipartite components of current irg as vcg. */
364 static void debug_vcg_dump_bipartite(rss_t *rss)
369 static const char suffix[] = "-RSS-CBC.vcg";
371 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
372 f = fopen(file_name, "w");
374 ir_fprintf(f, "graph: { title: \"connected bipartite component graph of %+F\"\n", rss->irg);
375 fprintf(f, "display_edge_labels: no\n");
376 fprintf(f, "layoutalgorithm: mindepth\n");
377 fprintf(f, "manhattan_edges: yes\n\n");
379 foreach_pset(rss->cbc_set, cbc) {
380 ir_nodeset_iterator_t iter;
384 fprintf(f, "graph: { titel: \"cbc %d\" label: \"cbc %d\" status:clustered color:yellow\n", cbc->nr, cbc->nr);
385 foreach_ir_nodeset(&cbc->parents, n, iter) {
386 ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
388 foreach_ir_nodeset(&cbc->children, n, iter) {
389 ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
391 foreach_pset(cbc->kill_edges, ke) {
392 ir_fprintf(f, "edge: { sourcename: \"n%d_%d\" targetname: \"n%d_%d\" }\n",
393 get_irn_node_nr(ke->src), cbc->nr, get_irn_node_nr(ke->tgt), cbc->nr);
401 /* Dump the computed killing function as vcg. */
402 static void debug_vcg_dump_kill(rss_t *rss)
407 static const char suffix[] = "-RSS-KILL.vcg";
409 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
410 f = fopen(file_name, "w");
412 ir_fprintf(f, "graph: { title: \"computed kill graph of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
413 fprintf(f, "display_edge_labels: no\n");
414 fprintf(f, "layoutalgorithm: mindepth\n");
415 fprintf(f, "manhattan_edges: yes\n\n");
418 /* reset dump_flag */
420 foreach_phase_irn(&rss->ph, irn) {
421 rss_irn_t *node = get_rss_irn(rss, irn);
426 /* dump all nodes and their killers */
427 foreach_plist(rss->nodes, el) {
428 ir_node *irn = plist_element_get_value(el);
429 rss_irn_t *rirn = get_rss_irn(rss, irn);
430 rss_irn_t *pk_rirn = get_rss_irn(rss, rirn->killer);
432 if (! rirn->dumped) {
433 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
437 if (! pk_rirn->dumped) {
438 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(rirn->killer), rirn->killer);
442 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
443 get_irn_node_nr(rirn->killer), get_irn_node_nr(irn));
450 /* Dumps the potential killing DAG (PKG) as vcg. */
451 static void debug_vcg_dump_pkg(rss_t *rss, ir_nodeset_t *max_ac, int iteration)
456 static const char suffix1[] = "-RSS-PKG.vcg";
457 static const char suffix2[] = "-RSS-PKG-MAXAC.vcg";
461 snprintf(suffix, sizeof(suffix), "%s", suffix1);
464 snprintf(suffix, sizeof(suffix), "-%02d%s", iteration, suffix2);
467 build_file_name(rss, suffix, strlen(suffix) + 1, file_name, sizeof(file_name));
468 f = fopen(file_name, "w");
470 ir_fprintf(f, "graph: { title: \"potential killing DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
471 fprintf(f, "display_edge_labels: no\n");
472 fprintf(f, "layoutalgorithm: mindepth\n");
473 fprintf(f, "manhattan_edges: yes\n\n");
476 /* reset dump_flag */
478 foreach_phase_irn(&rss->ph, irn) {
479 rss_irn_t *node = get_rss_irn(rss, irn);
484 foreach_plist(rss->nodes, el) {
485 ir_node *irn = plist_element_get_value(el);
486 rss_irn_t *rirn = get_rss_irn(rss, irn);
488 plist_element_t *k_el;
490 /* dump selected saturating values in yellow */
491 if (max_ac && ir_nodeset_contains(max_ac, irn))
494 if (! rirn->dumped) {
496 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(irn), irn, rirn->chain->nr, c1);
498 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(irn), irn, c1);
502 foreach_plist(rirn->pkiller_list, k_el) {
503 ir_node *pkiller = plist_element_get_value(k_el);
504 rss_irn_t *pk_rirn = get_rss_irn(rss, pkiller);
507 if (max_ac && ir_nodeset_contains(max_ac, pkiller))
510 if (! pk_rirn->dumped) {
512 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(pkiller), pkiller, pk_rirn->chain->nr, c2);
514 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(pkiller), pkiller, c2);
517 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
518 get_irn_node_nr(pkiller), get_irn_node_nr(irn));
525 /* Dumps the disjoint value DAG (DVG) as vcg. */
526 static void debug_vcg_dump_dvg(rss_t *rss, dvg_t *dvg)
528 static const char suffix[] = "-RSS-DVG.vcg";
531 ir_nodeset_iterator_t iter;
535 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
536 f = fopen(file_name, "w");
538 ir_fprintf(f, "graph: { title: \"disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
539 fprintf(f, "display_edge_labels: no\n");
540 fprintf(f, "layoutalgorithm: mindepth\n");
541 fprintf(f, "manhattan_edges: yes\n\n");
544 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
545 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
549 foreach_pset(dvg->edges, edge) {
550 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
551 get_irn_node_nr(edge->src), get_irn_node_nr(edge->tgt));
559 /* Dumps the PKG(DVG). */
560 static void debug_vcg_dump_dvg_pkiller(rss_t *rss, dvg_t *dvg)
562 static const char suffix[] = "-RSS-DVG-PKG.vcg";
565 ir_nodeset_iterator_t iter;
568 build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
569 f = fopen(file_name, "w");
571 ir_fprintf(f, "graph: { title: \"PKG of disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
572 fprintf(f, "display_edge_labels: no\n");
573 fprintf(f, "layoutalgorithm: mindepth\n");
574 fprintf(f, "manhattan_edges: yes\n\n");
577 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
578 ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
582 foreach_ir_nodeset(&dvg->nodes, irn, iter) {
583 rss_irn_t *node = get_rss_irn(rss, irn);
586 foreach_plist(node->dvg_pkiller_list, el) {
587 ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
588 get_irn_node_nr(plist_element_get_value(el)), get_irn_node_nr(irn));
598 * In case there is no rss information for irn, initialize it.
600 static void *init_rss_irn(ir_phase *ph, const ir_node *irn)
602 rss_irn_t *res = phase_alloc(ph, sizeof(res[0]));
604 res->descendant_list = plist_obstack_new(phase_obst(ph));
605 res->descendants = NULL;
607 res->consumer_list = plist_obstack_new(phase_obst(ph));
608 res->consumer = NULL;
610 res->pkiller_list = plist_obstack_new(phase_obst(ph));
612 res->parent_list = plist_obstack_new(phase_obst(ph));
630 * Collect all nodes data dependent on current node.
632 static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int *got_sink, unsigned cur_desc_walk)
634 const ir_edge_t *edge;
635 rss_irn_t *cur_node = get_rss_irn(rss, irn);
636 ir_node *block = rss->block;
637 ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
640 if (cur_node->desc_walk >= cur_desc_walk)
642 cur_node->desc_walk = cur_desc_walk;
644 /* Stop at Barriers */
645 if (be_is_Barrier(irn))
648 /* loop over normal and dependency edges */
649 for (i = 0; i < 2; ++i) {
650 foreach_out_edge_kind(irn, edge, ekind[i]) {
651 ir_node *user = get_edge_src_irn(edge);
653 /* skip ignore nodes as they do not really contribute to register pressure */
654 if (arch_irn_is_ignore(user))
658 (a) mode_X means Jump -> out_edge
659 (b) Phi as user of a normal node -> out-edge
661 if (get_irn_mode(user) == mode_X || is_Phi(user)) {
669 //if (arch_get_irn_reg_class_out(user) == rss->cls)
670 collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
673 /* check if user lives in block and is not a control flow node */
674 if (get_nodes_block(user) == block) {
675 if (! plist_has_value(rirn->descendant_list, user)) {
676 plist_insert_back(rirn->descendant_list, user);
677 DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", user));
679 collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
681 else if (! *got_sink) {
683 /* user lives out of block: add sink as descendant if not already done */
684 plist_insert_back(rirn->descendant_list, _sink);
686 DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", _sink));
694 * Handles a single consumer.
696 static void collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *consumer, int *got_sink)
698 ir_node *block = rss->block;
700 assert(! is_Proj(consumer) && "Cannot handle Projs");
702 if (! is_Phi(consumer) && ! is_Block(consumer) && get_nodes_block(consumer) == block) {
703 if (!arch_irn_is_ignore(consumer) &&
704 !plist_has_value(rss_irn->consumer_list, consumer)) {
705 plist_insert_back(rss_irn->consumer_list, consumer);
706 DBG((rss->dbg, LEVEL_2, "\t\tconsumer %+F\n", consumer));
710 rss_irn->live_out = 1;
711 DBG((rss->dbg, LEVEL_2, "\t\tlive out %+F", consumer));
713 plist_insert_back(rss_irn->consumer_list, _sink);
715 DB((rss->dbg, LEVEL_2, ", %+F added instead", _sink));
717 DB((rss->dbg, LEVEL_2, "\n"));
722 * Collect all nodes consuming the value(s) produced by current node.
724 static void collect_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *irn, int *got_sink)
726 const ir_edge_t *edge;
728 ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
729 rss_irn_t *cur_node = get_rss_irn(rss, irn);
731 if (cur_node->havecons)
733 cur_node->havecons = 1;
735 for (i = 0; i < 2; ++i) {
736 foreach_out_edge_kind(irn, edge, ekind[i]) {
737 ir_node *consumer = get_edge_src_irn(edge);
739 if (is_Proj(consumer)) {
740 //if (arch_get_irn_reg_class_out(consumer) == rss->cls)
741 collect_consumer(rss, rss_irn, consumer, got_sink);
744 collect_single_consumer(rss, rss_irn, consumer, got_sink);
750 * Collects all consumer and descendant of a irn.
752 static void collect_node_info(rss_t *rss, ir_node *irn)
754 static unsigned cur_desc_walk = 0;
755 rss_irn_t *rss_irn = get_rss_irn(rss, irn);
758 assert(! is_Proj(irn) && "Cannot handle Projs.");
760 /* check if node info is already available */
761 if (rss_irn->handled)
764 DBG((rss->dbg, LEVEL_1, "\tcomputing consumers of %+F:\n", irn));
766 /* collect all consumer */
768 collect_consumer(rss, rss_irn, irn, &got_sink);
770 /* build sorted consumer array */
771 rss_irn->consumer = build_sorted_array_from_list(rss_irn->consumer_list, phase_obst(&rss->ph));
773 DBG((rss->dbg, LEVEL_1, "\tcompute descendants of %+F:\n", irn));
775 /* collect descendants */
777 collect_descendants(rss, rss_irn, irn, &got_sink, ++cur_desc_walk);
779 /* build sorted descendant array */
780 rss_irn->descendants = build_sorted_array_from_list(rss_irn->descendant_list, phase_obst(&rss->ph));
782 rss_irn->handled = 1;
786 * Checks if v is a potential killer of u.
787 * v is in pkill(u) iff descendants(v) cut consumer(u) is v
789 * @param rss The rss object
790 * @param v The node to check for killer
791 * @param u The potentially killed value
792 * @return 1 if v is in pkill(u), 0 otherwise
794 static int is_potential_killer(rss_t *rss, rss_irn_t *v, rss_irn_t *u)
801 /* as we loop over the list: loop over the shorter one */
802 if (plist_count(v->descendant_list) > plist_count(u->consumer_list)) {
803 list = u->consumer_list;
804 arr = v->descendants;
807 list = v->descendant_list;
811 /* for each list element: try to find element in array */
812 foreach_plist(list, el) {
813 ir_node *irn = plist_element_get_value(el);
814 ir_node *match = BSEARCH_IRN_ARR(irn, arr);
816 if (match && match != irn)
824 * Update descendants, consumer and pkiller list for the given irn.
826 static void update_node_info(rss_t *rss, ir_node *irn, ir_node *pk_irn)
828 rss_irn_t *node = get_rss_irn(rss, irn);
829 rss_irn_t *pkiller = get_rss_irn(rss, pk_irn);
831 /* add consumer and rebuild the consumer array */
832 if (! plist_has_value(node->consumer_list, pk_irn)) {
833 plist_insert_back(node->consumer_list, pk_irn);
834 node->consumer = build_sorted_array_from_list(node->consumer_list, phase_obst(&rss->ph));
837 /* add pk_irn as descendant, add it's descendants to irn's and rebuild array */
838 if (! plist_has_value(node->descendant_list, pk_irn)) {
841 plist_insert_back(node->descendant_list, pk_irn);
843 foreach_plist(pkiller->descendant_list, el) {
844 ir_node *desc = plist_element_get_value(el);
846 if (! plist_has_value(node->descendant_list, desc))
847 plist_insert_back(node->descendant_list, desc);
850 node->descendants = build_sorted_array_from_list(node->descendant_list, phase_obst(&rss->ph));
856 * Compute the potential killing set PK.
858 static void compute_pkill_set(rss_t *rss)
860 plist_element_t *u_el, *v_el;
862 foreach_plist(rss->nodes, u_el) {
863 ir_node *u_irn = plist_element_get_value(u_el);
864 rss_irn_t *u = get_rss_irn(rss, u_irn);
866 DBG((rss->dbg, LEVEL_1, "\tcomputing potential killers of %+F:\n", u_irn));
868 /* check each consumer if it is a potential killer */
869 foreach_plist(u->consumer_list, v_el) {
870 ir_node *v_irn = plist_element_get_value(v_el);
871 rss_irn_t *v = get_rss_irn(rss, v_irn);
873 /* check, if v is a potential killer of u */
874 if (is_potential_killer(rss, v, u)) {
875 if (! plist_has_value(u->pkiller_list, v_irn))
876 plist_insert_back(u->pkiller_list, v_irn);
878 DBG((rss->dbg, LEVEL_2, "\t\tpotential killer %+F\n", v_irn));
885 if (rss->opts->dump_flags & RSS_DUMP_PKG)
886 debug_vcg_dump_pkg(rss, NULL, 0);
890 * Build set of killing edges (from values to their potential killers)
892 static void build_kill_edges(rss_t *rss, pset *epk)
894 plist_element_t *el, *k_el;
896 foreach_plist(rss->nodes, el) {
897 ir_node *irn = plist_element_get_value(el);
898 rss_irn_t *rirn = get_rss_irn(rss, irn);
900 DBG((rss->dbg, LEVEL_3, "\t\tbuilding kill edges for %+F:\n", irn));
902 foreach_plist(rirn->pkiller_list, k_el) {
903 ir_node *pkiller = plist_element_get_value(k_el);
904 rss_edge_t *ke = OALLOC(phase_obst(&rss->ph), rss_edge_t);
910 DBG((rss->dbg, LEVEL_3, "\t\t\ttarget %+F\n", pkiller));
912 pset_insert(epk, ke, HASH_RSS_EDGE(ke));
918 /* print the given cbc for debugging purpose */
919 static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc)
921 ir_nodeset_iterator_t iter;
925 DBG((mod, LEVEL_3, "\t\tS = set of parents:\n"));
926 foreach_ir_nodeset(&cbc->parents, n, iter) {
927 DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
929 DBG((mod, LEVEL_3, "\t\tT = set of children:\n"));
930 foreach_ir_nodeset(&cbc->children, n, iter) {
931 DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
933 DBG((mod, LEVEL_3, "\t\tE = Edges from producers to consumers\n"));
934 foreach_pset(cbc->kill_edges, ke) {
935 DBG((mod, LEVEL_3, "\t\t\t%+F -> %+F\n", ke->src, ke->tgt));
941 * Construct the bipartite decomposition.
942 * Sid-Ahmed-Ali Touati, Phd Thesis
943 * Register Pressure in Instruction Level Parallelism, p. 71
945 static void compute_bipartite_decomposition(rss_t *rss)
947 pset *epk = new_pset(cmp_rss_edges, 10);
952 DBG((rss->dbg, LEVEL_1, "\tcomputing bipartite decomposition:\n"));
954 build_kill_edges(rss, epk);
956 foreach_plist(rss->nodes, el) {
957 ir_node *u_irn = plist_element_get_value(el);
958 rss_irn_t *u = get_rss_irn(rss, u_irn);
964 plist_element_t *el2;
966 rss_edge_t *kedge_root = NULL;
967 ir_node *t_irn, *s_irn;
968 ir_nodeset_iterator_t iter;
970 if (u->visited || u_irn == _sink)
973 DBG((rss->dbg, LEVEL_2, "\t\t%+F choosen:\n", u_irn));
975 cbc = OALLOC(phase_obst(&rss->ph), cbc_t);
978 /* initialize S_cb */
979 ir_nodeset_init_size(&cbc->parents, 5);
980 ir_nodeset_insert(&cbc->parents, u_irn);
981 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (init)\n", u_irn));
984 cbc->kill_edges = new_pset(cmp_rss_edges, 5);
986 /* each parent gets killed by at least one value from children */
988 /* T_cb = PK_successors(u) */
989 ir_nodeset_init_size(&cbc->children, 5);
990 foreach_plist(u->pkiller_list, el2) {
991 ir_nodeset_insert(&cbc->children, plist_element_get_value(el2));
992 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (init)\n", plist_element_get_value(el2)));
996 Now: insert the parents of all children into the parent set
997 and insert the children of all parents into the children set
998 until the sets don't change any more
1000 while (p_change || c_change) {
1001 ir_nodeset_iterator_t iter;
1002 p_change = c_change = 0;
1004 /* accumulate parents */
1005 foreach_ir_nodeset(&cbc->children, t_irn, iter) {
1006 foreach_pset(epk, k_edge) {
1007 ir_node *val = k_edge->src;
1009 if (k_edge->tgt == t_irn && ! ir_nodeset_contains(&cbc->parents, val)) {
1010 ir_nodeset_insert(&cbc->parents, val);
1012 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (killed by %+F)\n", val, t_irn));
1017 /* accumulate children */
1018 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
1019 foreach_pset(epk, k_edge) {
1020 ir_node *val = k_edge->tgt;
1022 if (k_edge->src == s_irn && ! ir_nodeset_contains(&cbc->children, val)) {
1023 ir_nodeset_insert(&cbc->children, val);
1025 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (kills %+F)\n", val, s_irn));
1031 /* mark all parent values as visited */
1032 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
1033 rss_irn_t *s = get_rss_irn(rss, s_irn);
1035 /* assure bipartite property */
1037 if (ir_nodeset_contains(&cbc->children, s_irn)) {
1038 ir_nodeset_remove(&cbc->children, s_irn);
1039 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F removed from to children\n", s_irn));
1045 foreach_pset(epk, k_edge) {
1046 if (ir_nodeset_contains(&cbc->parents, k_edge->src) &&
1047 ir_nodeset_contains(&cbc->children, k_edge->tgt)) {
1048 pset_insert(cbc->kill_edges, k_edge, HASH_RSS_EDGE(k_edge));
1050 Link all k_edges which are about to be removed together.
1051 Beware: pset_remove kills the iterator.
1053 k_edge->next = kedge_root;
1054 kedge_root = k_edge;
1058 /* remove all linked k_edges */
1059 for (; kedge_root; kedge_root = kedge_root->next) {
1060 pset_remove(epk, kedge_root, HASH_RSS_EDGE(kedge_root));
1063 /* verify the cbc */
1064 foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
1067 foreach_pset(cbc->kill_edges, k_edge) {
1068 if (k_edge->src == s_irn) {
1070 pset_break(cbc->kill_edges);
1077 ir_fprintf(stderr, "Warning: parent %+F is not killed in current cbc\n", s_irn);
1080 assert(vrfy_ok && "Verification of CBC failed");
1082 /* add the connected bipartite component */
1083 if (ir_nodeset_size(&cbc->parents) > 0 &&
1084 ir_nodeset_size(&cbc->children) > 0 &&
1085 pset_count(cbc->kill_edges) > 0)
1086 pset_insert(rss->cbc_set, cbc, (unsigned)cbc->nr);
1087 DBG((rss->dbg, LEVEL_2, "\tbipartite component %d inserted:\n", cbc->nr));
1089 if (firm_dbg_get_mask(rss->dbg) & LEVEL_2)
1090 debug_print_cbc(rss->dbg, cbc);
1094 if (rss->opts->dump_flags & RSS_DUMP_CBC)
1095 debug_vcg_dump_bipartite(rss);
1101 * Select the child with the maximum cost.
1103 static child_t *select_child_max_cost(rss_t *rss, ir_nodeset_t *x, ir_nodeset_t *y, child_t *t, cbc_t *cbc)
1106 ir_nodeset_iterator_t iter;
1107 float max_cost = -1.0f;
1109 DBG((rss->dbg, LEVEL_2, "\t\tcomputing children costs:\n"));
1111 foreach_ir_nodeset(&cbc->children, child, iter) {
1112 rss_irn_t *r_child = get_rss_irn(rss, child);
1113 int num_unkilled_parents = 0;
1114 int num_descendants;
1118 /* get the number of unkilled parents */
1119 foreach_pset(cbc->kill_edges, k_edge) {
1120 if (k_edge->tgt == child && ir_nodeset_contains(x, k_edge->src))
1121 ++num_unkilled_parents;
1124 cost = (float)num_unkilled_parents;
1126 num_descendants = plist_count(r_child->descendant_list) + ir_nodeset_size(y);
1128 if (num_descendants > 0)
1129 cost /= (float)num_descendants;
1131 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F, #desc %d, cost %.3f\n", child, num_descendants, cost));
1133 if (cost > max_cost) {
1144 * Remove all parents from x which are killed by t_irn.
1146 static void remove_covered_parents(rss_t *rss, ir_nodeset_t *x, ir_node *t_irn, cbc_t *cbc)
1148 rss_irn_t *t = get_rss_irn(rss, t_irn);
1151 DBG((rss->dbg, LEVEL_2, "\t\tremoving parents covered by %+F:\n", t_irn));
1153 foreach_pset(cbc->kill_edges, k_edge) {
1154 if (k_edge->tgt == t_irn && ir_nodeset_contains(x, k_edge->src)) {
1155 ir_nodeset_remove(x, k_edge->src);
1156 plist_insert_back(t->parent_list, k_edge->src);
1157 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", k_edge->src));
1162 static void update_cumulated_descendent_values(rss_t *rss, ir_nodeset_t *y, ir_node *t_irn)
1164 rss_irn_t *t = get_rss_irn(rss, t_irn);
1165 plist_element_t *el;
1167 DBG((rss->dbg, LEVEL_2, "\t\tupdating cumulated descendant value of %+F:\n", t_irn));
1169 foreach_plist(t->descendant_list, el) {
1170 ir_nodeset_insert(y, plist_element_get_value(el));
1171 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", plist_element_get_value(el)));
1176 * Greedy-k: a heuristics for the MMA problem
1178 static void compute_killing_function(rss_t *rss)
1181 struct obstack obst;
1183 obstack_init(&obst);
1185 rss->cbc_set = pset_new_ptr(5);
1186 compute_bipartite_decomposition(rss);
1188 /* for all bipartite components do: */
1189 foreach_pset(rss->cbc_set, cbc) {
1193 ir_nodeset_iterator_t iter;
1194 child_t **sks = NEW_ARR_F(child_t *, 20);
1199 ir_nodeset_init_size(&x, 10);
1200 ir_nodeset_init_size(&y, 10);
1202 DBG((rss->dbg, LEVEL_1, "\tcomputing SKS for cbc %d:\n", cbc->nr));
1203 DBG((rss->dbg, LEVEL_2, "\t\tinitializing parents X:\n"));
1205 /* X = S_cb (all parents are initially uncovered) */
1206 foreach_ir_nodeset(&cbc->parents, p, iter) {
1207 ir_nodeset_insert(&x, p);
1208 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", p));
1211 /* while X not empty */
1212 while (ir_nodeset_size(&x) > 0) {
1213 child_t *t = OALLOCZ(&obst, child_t);
1215 t = select_child_max_cost(rss, &x, &y, t, cbc);
1217 if (cur_len >= cur_size) {
1218 ARR_EXTO(child_t *, sks, cur_size * 2);
1222 DBG((rss->dbg, LEVEL_2, "\t\tinsert child %+F (%.3f) into SKS at pos %d\n", t->irn, t->cost, cur_len));
1225 remove_covered_parents(rss, &x, t->irn, cbc);
1226 update_cumulated_descendent_values(rss, &y, t->irn);
1229 ARR_SHRINKLEN(sks, cur_len);
1231 /* sort SKS in increasing cost order */
1232 qsort(sks, cur_len, sizeof(sks[0]), cmp_child_costs);
1234 DBG((rss->dbg, LEVEL_2, "\tprocessing SKS for cbc %d:\n", cbc->nr));
1236 /* build killing function */
1237 for (i = cur_len - 1; i >= 0; --i) { /* loop over sks in decreasing cost order */
1238 child_t *t = sks[i];
1239 rss_irn_t *rt = get_rss_irn(rss, t->irn);
1240 plist_element_t *p_el;
1242 DBG((rss->dbg, LEVEL_3, "\t\t\tkiller %+F (%.3f):\n", t->irn, t->cost));
1244 /* kill all unkilled parents of t */
1245 foreach_plist(rt->parent_list, p_el) {
1246 ir_node *par = plist_element_get_value(p_el);
1247 rss_irn_t *rpar = get_rss_irn(rss, par);
1249 if (is_Sink(rpar->killer)) {
1250 rpar->killer = t->irn;
1251 DBG((rss->dbg, LEVEL_2, "\t\tkill %+F\n", rpar->irn));
1254 DBG((rss->dbg, LEVEL_3, "\t\t\tkeeping %+F as killer for %+F\n", rpar->killer, rpar->irn));
1259 ir_nodeset_destroy(&x);
1260 ir_nodeset_destroy(&y);
1264 if (rss->opts->dump_flags & RSS_DUMP_KILL)
1265 debug_vcg_dump_kill(rss);
1267 del_pset(rss->cbc_set);
1268 obstack_free(&obst, NULL);
1272 * Adds the edge src -> tgt to the dvg. Checks if reverse edge is already there (asserts).
1274 static inline void add_dvg_edge(rss_t *rss, dvg_t *dvg, const ir_node *src, const ir_node *tgt, int have_source)
1276 rss_edge_t *dvg_edge;
1280 ir_nodeset_insert(&dvg->nodes, (ir_node *) src);
1282 assert(ir_nodeset_contains(&dvg->nodes, src) && "Wrong assumption");
1284 ir_nodeset_insert(&dvg->nodes, (ir_node *) tgt);
1286 key.src = (ir_node *) tgt;
1287 key.tgt = (ir_node *) src;
1288 assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
1290 key.src = (ir_node *) src;
1291 key.tgt = (ir_node *) tgt;
1292 if (NULL != pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
1293 /* add the edge to the DVG */
1294 dvg_edge = OALLOC(phase_obst(&rss->ph), rss_edge_t);
1296 dvg_edge->src = (ir_node *) src;
1297 dvg_edge->tgt = (ir_node *) tgt;
1298 dvg_edge->next = NULL;
1300 DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", src, tgt));
1301 pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
1306 * Computes the disjoint value DAG (DVG).
1307 * BEWARE: It is not made explicitly clear in the Touati paper,
1308 * but the DVG is meant to be build from the KILLING DAG
1310 static void compute_dvg(rss_t *rss, dvg_t *dvg)
1312 plist_element_t *el;
1314 DBG((rss->dbg, LEVEL_1, "\tcomputing DVG:\n"));
1316 foreach_plist(rss->nodes, el) {
1317 ir_node *u_irn = plist_element_get_value(el);
1318 rss_irn_t *u = get_rss_irn(rss, u_irn);
1319 rss_irn_t *u_killer = get_rss_irn(rss, u->killer);
1322 /* TODO: omit nodes only having sink as pkiller and killing no one */
1324 /* add an edge to killer */
1325 add_dvg_edge(rss, dvg, u_irn, u->killer, 0);
1327 if (is_Sink(u->killer))
1330 /* We add an edge to every killer, from where we could be reached. */
1331 for (i = ARR_LEN_SAFE(u_killer->descendants) - 1; i >= 0; --i) {
1332 add_dvg_edge(rss, dvg, u_irn, u_killer->descendants[i], 1);
1337 foreach_plist(rss->nodes, el2) {
1338 ir_node *v_irn = plist_element_get_value(el2);
1341 There is an edge (u, v) in the DVG iff v is a descendant of the killer(u).
1343 if (BSEARCH_IRN_ARR(v_irn, u_kill->descendants)) {
1344 rss_edge_t *dvg_edge = OALLOC(phase_obst(&rss->ph), rss_edge_t);
1347 /* insert the user into the DVG and append it to the user list of u */
1348 ir_nodeset_insert(&dvg->nodes, v_irn);
1349 if (! plist_has_value(u->dvg_user_list, v_irn))
1350 plist_insert_back(u->dvg_user_list, v_irn);
1352 dvg_edge->src = u_irn;
1353 dvg_edge->tgt = v_irn;
1354 dvg_edge->next = NULL;
1359 assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
1361 /* add the edge to the DVG */
1362 DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", u_irn, v_irn));
1363 pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
1369 if (rss->opts->dump_flags & RSS_DUMP_DVG)
1370 debug_vcg_dump_dvg(rss, dvg);
1374 * Updates the dvg structure when a serialization edge from src -> tgt is added.
1376 static void update_dvg(rss_t *rss, dvg_t *dvg, rss_irn_t *src, rss_irn_t *tgt)
1380 rss_edge_t **arr = ALLOCAN(rss_edge_t*, pset_count(dvg->edges));
1383 Add an edge from serialization target to serialization src:
1384 src cannot be alive with target
1386 add_dvg_edge(rss, dvg, tgt->irn, src->irn, 0);
1388 /* Add edges to src's descendants as well, they also getting serialized. */
1389 for (i = ARR_LEN_SAFE(src->descendants) - 1; i >= 0; --i) {
1390 add_dvg_edge(rss, dvg, tgt->irn, src->descendants[i], 1);
1393 /* We also have to add edges from targets predecessors in dvg */
1395 /* We cannot insert elements into set over which we iterate ... */
1396 foreach_pset(dvg->edges, edge) {
1397 if (edge->tgt == tgt->irn) {
1402 for (i = 0; i < idx; ++i) {
1404 add_dvg_edge(rss, dvg, edge->src, src->irn, 1);
1405 for (j = ARR_LEN_SAFE(src->descendants) - 1; j >= 0; --j) {
1406 add_dvg_edge(rss, dvg, edge->src, src->descendants[j], 1);
1413 * Accumulate all descendants for root into list.
1415 static void accumulate_dvg_descendant_values(rss_t *rss, rss_irn_t *root, plist_t *list)
1417 if (plist_count(root->dvg_user_list) > 0) {
1418 plist_element_t *el;
1420 foreach_plist(root->dvg_user_list, el) {
1421 ir_node *v_irn = plist_element_get_value(el);
1422 rss_irn_t *v = get_rss_irn(rss, v_irn);
1424 /* add v as descendant */
1425 if (! plist_has_value(list, v_irn)) {
1426 plist_insert_back(list, v_irn);
1427 DBG((rss->dbg, DEBUG_DVG, "\t\t\tadd DVG descendant %+F\n", v_irn));
1430 /* accumulate v's descendants */
1431 accumulate_dvg_descendant_values(rss, v, list);
1437 * Builds the list of potential killers for each node
1439 * Needs the descendant list for all user as sorted array.
1441 static void build_dvg_pkiller_list(rss_t *rss, dvg_t *dvg)
1443 ir_nodeset_iterator_t iter;
1446 foreach_nodeset(&dvg->nodes, irn, iter) {
1447 rss_irn_t *node = get_rss_irn(rss, irn);
1448 plist_element_t *el, *el2;
1450 DBG((rss->dbg, DEBUG_DVG, "\t\tbuilding pkiller list for %+F\n", irn));
1452 /* check each user */
1453 foreach_plist(node->dvg_user_list, el) {
1454 ir_node *u_irn = plist_element_get_value(el);
1456 /* is the current user u_irn not a descendant of any other user -> pkiller */
1457 foreach_plist(node->dvg_user_list, el2) {
1458 ir_node *v_irn = plist_element_get_value(el2);
1459 rss_irn_t *v = get_rss_irn(rss, v_irn);
1462 ! BSEARCH_IRN_ARR(u_irn, v->dvg_desc) &&
1463 ! plist_has_value(node->dvg_pkiller_list, u_irn))
1465 plist_insert_back(node->dvg_pkiller_list, u_irn);
1466 DBG((rss->dbg, DEBUG_DVG, "\t\t\tadd DVG pkiller %+F\n", u_irn));
1471 node->dvg_pkiller = build_sorted_array_from_list(node->dvg_pkiller_list, phase_obst(&rss->ph));
1475 if (firm_dbg_get_mask(rss->dbg) & DEBUG_DVG)
1476 debug_vcg_dump_dvg_pkiller(rss, dvg);
1483 * Compute the maximal antichain of the current DVG.
1484 * This is a reimplementation of the MAXIMAL_ANTI_CHAIN function
1485 * from the DDG library 1.1 (DAG.cpp).
1487 static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration)
1489 unsigned n = ir_nodeset_size(&dvg->nodes);
1490 unsigned *assignment = ALLOCAN(unsigned, n);
1491 unsigned *assignment_rev = ALLOCAN(unsigned, n);
1492 int *idx_map = ALLOCAN(int, n);
1493 hungarian_problem_t *bp;
1494 ir_nodeset_t *values, *temp;
1495 ir_nodeset_iterator_t iter;
1500 rss_edge_t *dvg_edge;
1502 #define MAP_IDX(irn) bsearch_for_index(get_irn_idx(irn), idx_map, n, 1)
1504 if (pset_count(dvg->edges) == 0)
1507 bp = hungarian_new(n, n, HUNGARIAN_MATCH_NORMAL);
1510 At first, we build an index map for the nodes in the DVG,
1511 because we cannot use the irn idx therefore as the resulting
1512 bipartite data structure would have around 1.2GB.
1513 So we limit the size to the number of nodes we have in the DVG
1514 and build a sorted index map for their irn indices.
1517 foreach_ir_nodeset(&dvg->nodes, u_irn, iter) {
1518 idx_map[i++] = get_irn_idx(u_irn);
1520 qsort(idx_map, n, sizeof(idx_map[0]), cmp_int);
1522 foreach_pset(dvg->edges, dvg_edge) {
1523 int idx_u = MAP_IDX(dvg_edge->src);
1524 int idx_v = MAP_IDX(dvg_edge->tgt);
1526 /* add the entry to the bipartite data structure */
1527 hungarian_add(bp, idx_u, idx_v, 1);
1528 DBG((rss->dbg, LEVEL_3, "\t\t\tadd %d (%+F) -> %d (%+F)\n",
1529 idx_u, dvg_edge->src, idx_v, dvg_edge->tgt));
1533 Add a bipartite entry for each pair of nodes (u, v), where exists a
1534 path in the DVG from u to v, ie. connect all descendants(v) to v.
1535 desc_dvg(v) = accumulated descendants of all z in dvg_user_list(v)
1537 foreach_ir_nodeset(&dvg->nodes, u_irn, iter) {
1538 rss_irn_t *u = get_rss_irn(rss, u_irn);
1539 int idx_u_irn = MAP_IDX(u_irn);
1541 DBG((rss->dbg, DEBUG_DVG, "\t\tcomputing DVG descendants of %+F:\n", u_irn));
1543 //plist_clear(u->dvg_desc_list);
1544 //accumulate_dvg_descendant_values(rss, u, u->dvg_desc_list);
1547 FIXME: The array is build on the phase obstack and we cannot free the data.
1548 So the array get as many times allocated as this function is called.
1551 /* build the sorted array for faster searches */
1552 //u->dvg_desc = build_sorted_array_from_list(u->dvg_desc_list, phase_obst(&rss->ph));
1554 DBG((rss->dbg, DEBUG_MAX_AC, "\t\tadding bipartite entries of %+F:\n", u_irn));
1556 /* add the bipartite entries for all descendants */
1557 for (i = ARR_LEN_SAFE(u->dvg_desc) - 1; i >= 0; --i) {
1558 rss_irn_t *desc = get_rss_irn(rss, u->dvg_desc[i]);
1559 int idx_desc = MAP_IDX(u->dvg_desc[i]);
1561 /* add the entry to the bipartite data structure */
1562 hungarian_add(bp, idx_u_irn, idx_desc, 1);
1563 DBG((rss->dbg, DEBUG_MAX_AC, "\t\t\tadd %d (%+F) -> %d (%+F)\n",
1564 idx_u_irn, u_irn, idx_desc, u->dvg_desc[i]));
1571 /* We want maximum cardinality matching */
1572 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
1575 DBG((rss->dbg, DEBUG_DVG, "\t\tcomputing DVG pkiller:\n"));
1576 /* beware: the following function needs the dvg_desc array */
1577 build_dvg_pkiller_list(rss, dvg);
1580 DBG((rss->dbg, LEVEL_2, "\t\tcomputing bipartite matching\n"));
1582 The maximum cardinality bipartite matching gives us the minimal
1583 chain partition, which corresponds to the maximum anti chains.
1585 res = hungarian_solve(bp, assignment, &cost, 1);
1586 assert(res == 0 && "Bipartite matching failed!");
1589 memset(assignment_rev, -1, n * sizeof(assignment_rev[0]));
1591 /* build the reverse assignment, ie. foreach i -> j, add j -> i */
1592 for (i = 0; i < n; ++i) {
1593 if (assignment[i] != (unsigned)-1) {
1594 unsigned j = assignment[i];
1595 assignment_rev[j] = i;
1599 DBG((rss->dbg, LEVEL_2, "\t\tgot assignment with cost %u\n", cost));
1600 DBG((rss->dbg, LEVEL_3, "\t\t\tassignment --- reverse assignment\n"));
1601 for (i = 0; i < n; ++i) {
1602 DBG((rss->dbg, LEVEL_3, "\t\t\t%3u -> %3u %3u -> %3u\n", i, assignment[i], i, assignment_rev[i]));
1605 values = XMALLOC(ir_nodeset_t);
1606 ir_nodeset_init_size(values, 10);
1608 /* Construction of the minimal chain partition */
1609 for (j = 0; j < n; ++j) {
1610 /* check nodes, which did not occur as target */
1611 if (assignment_rev[j] == (unsigned)-1) {
1612 int xj = idx_map[j];
1613 ir_node *xj_irn = get_idx_irn(rss->irg, xj);
1614 rss_irn_t *xj_rss = get_rss_irn(rss, xj_irn);
1615 chain_t *c = OALLOC(phase_obst(&rss->ph), chain_t);
1618 /* there was no source for j -> we have a source of a new chain */
1619 ir_nodeset_insert(values, xj_irn);
1621 c->elements = plist_obstack_new(phase_obst(&rss->ph));
1622 c->nr = cur_chain++;
1623 plist_insert_back(c->elements, xj_irn);
1627 DBG((rss->dbg, LEVEL_2, "\t\tstarting chain %d:\n", c->nr));
1628 DBG((rss->dbg, LEVEL_2, "\t\t\t%+F (%u)", xj_irn, j));
1630 /* follow chain, having j as source */
1632 while (assignment[source] != (unsigned)-1) {
1633 int target = assignment[source];
1634 int irn_idx = idx_map[target];
1635 ir_node *irn = get_idx_irn(rss->irg, irn_idx);
1636 rss_irn_t *node = get_rss_irn(rss, irn);
1638 plist_insert_back(c->elements, irn);
1641 DB((rss->dbg, LEVEL_2, " -> %+F (%d)", irn, target));
1643 /* new source = last target */
1647 DB((rss->dbg, LEVEL_2, "\n"));
1652 Computing the maximal antichain: Select an element from each
1653 chain such, such it is parallel with the others.
1655 DBG((rss->dbg, LEVEL_1, "\t\tcomputing set of saturation values (MAX AC)\n"));
1656 DBG((rss->dbg, LEVEL_3, "\t\tstarting with:\n"));
1659 if (firm_dbg_get_mask(rss->dbg) & LEVEL_3)
1660 dump_nodeset(values, "\t\t\t");
1666 We need an explicit array for the values as
1667 we cannot iterate multiple times over the same
1668 set at the same time. :-(((((
1669 TODO Matze: now we can, so rewrite this...
1671 unsigned n = ir_nodeset_size(values);
1673 ir_node **val_arr = NEW_ARR_F(ir_node *, n);
1675 foreach_ir_nodeset(values, u_irn, iter)
1676 val_arr[i++] = u_irn;
1679 ir_nodeset_destroy(temp);
1683 temp = XMALLOC(ir_nodeset_t);
1684 ir_nodeset_init_size(temp, 10);
1686 /* Select all nodes from current value set, having another node in the set as descendant. */
1687 for (i = 0; i < n; ++i) {
1688 rss_irn_t *u = get_rss_irn(rss, val_arr[i]);
1690 for (j = 0; j < n; ++j) {
1694 key.src = val_arr[i];
1695 key.tgt = val_arr[j];
1697 if (pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
1698 /* v[j] is descendant of u -> remove u and break */
1699 ir_nodeset_insert(temp, (ir_node *) u->irn);
1700 ir_nodeset_remove(values, u->irn);
1702 DBG((rss->dbg, LEVEL_3, "\t\t\tremoving %+F from values, adding it to temp\n", u->irn));
1710 /* Try to insert the chain predecessor of all selected u's */
1711 foreach_ir_nodeset(temp, u_irn, iter) {
1712 rss_irn_t *u = get_rss_irn(rss, u_irn);
1713 chain_t *c = u->chain;
1714 plist_element_t *el = plist_find_value(c->elements, u_irn);
1716 assert(el && "Missing element in chain!");
1718 /* If u has predecessor in chain: insert the predecessor */
1719 if (el == plist_element_get_prev(el)) {
1720 ir_nodeset_insert(values, plist_element_get_value(el));
1721 DBG((rss->dbg, LEVEL_3, "\t\t\tadding %+F to values\n", plist_element_get_value(el)));
1727 } while (ir_nodeset_size(temp) > 0);
1729 DBG((rss->dbg, LEVEL_2, "\t\tfinal set:\n"));
1731 if (firm_dbg_get_mask(rss->dbg) & LEVEL_2) {
1732 dump_nodeset(values, "\t\t\t");
1736 if (rss->opts->dump_flags & RSS_DUMP_MAXAC)
1737 debug_vcg_dump_pkg(rss, values, iteration);
1740 ir_nodeset_destroy(temp);
1750 * Computes the best serialization between two nodes of sat_vals.
1752 static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nodeset_t *sat_vals, serialization_t *ser, int num_regs)
1754 int n = ir_nodeset_size(sat_vals);
1755 int n_idx = ARR_LEN_SAFE(rss->idx_map);
1757 ir_node **val_arr = ALLOCAN(ir_node*, n);
1758 bitset_t *bs_sv = bitset_alloca(n_idx);
1759 bitset_t *bs_vdesc = bitset_alloca(n_idx);
1760 bitset_t *bs_tmp = bitset_alloca(n_idx);
1761 bitset_t *bs_ukilldesc = bitset_alloca(n_idx);
1762 int best_benefit = INT_MAX;
1763 int best_omega2 = INT_MAX;
1764 int best_benefit_omega20 = INT_MAX;
1768 ir_nodeset_iterator_t iter;
1769 rss_edge_t min_benefit_edge = {NULL, NULL, NULL};
1770 rss_edge_t min_omega20_edge = {NULL, NULL, NULL};
1771 rss_irn_t *ser_u_omega1 = NULL, *ser_v_omega1 = NULL;
1772 rss_irn_t *ser_u_omega20 = NULL, *ser_v_omega20 = NULL;
1774 DBG((rss->dbg, LEVEL_1, "\tcomputing admissible serializations:\n"));
1777 We need an explicit array for the values as
1778 we cannot iterate multiple times over the same
1779 set at the same time. :-(((((
1782 foreach_ir_nodeset(sat_vals, irn, iter) {
1784 bitset_set(bs_sv, BLOCK_IDX_MAP(rss, irn));
1788 We build all admissible serializations and remember the best found so far.
1791 if v in pkiller(u): add edge from v to all other pkiller(u)
1792 else: for all vv in pkiller(u): add edge from v to vv if there exists no path from vv to v
1796 A node is unserializable if:
1797 - it has only one killer and this one is Sink
1798 - it kills no other values
1799 In this case there is no serialization which could
1800 reduce the registerpressure
1802 #define IS_UNSERIALIZABLE_NODE(rss_node) \
1805 (plist_count(rss_node->pkiller_list) == 1) && \
1806 is_Sink(rss_node->killer) && \
1807 (rss_node->kill_count == 0) \
1809 be_is_Barrier(rss_node->irn) || \
1810 be_is_Keep(rss_node->irn) \
1813 /* for all u in sat_vals */
1814 for (i = 0; i < n; ++i) {
1815 rss_irn_t *u = get_rss_irn(rss, val_arr[i]);
1816 plist_element_t *el;
1818 /* ignore nodes where serialization does not help */
1819 if (IS_UNSERIALIZABLE_NODE(u)) {
1820 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", u->irn));
1824 /* accumulate all descendants of all pkiller(u) */
1825 bitset_clear_all(bs_ukilldesc);
1826 foreach_plist(u->pkiller_list, el) {
1827 ir_node *irn = plist_element_get_value(el);
1828 rss_irn_t *node = get_rss_irn(rss, irn);
1831 bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, irn));
1835 for (k = ARR_LEN_SAFE(node->descendants) - 1; k >= 0; --k) {
1836 if (! is_Sink(node->descendants[k]))
1837 bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, node->descendants[k]));
1841 /* for all v in sat_vals */
1842 for (j = 0; j < n; ++j) {
1843 ir_node *v_irn = val_arr[j];
1844 rss_irn_t *v = get_rss_irn(rss, v_irn);
1845 unsigned v_height = get_irn_height(rss->h, v_irn);
1846 int omega1, omega2, is_pkiller;
1848 /* v cannot be serialized with itself
1849 * ignore nodes where serialization does not help */
1850 if (i == j || IS_UNSERIALIZABLE_NODE(v)) {
1851 #ifdef DEBUG_libfirm
1853 DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", v->irn));
1858 /* get descendants of v */
1859 bitset_clear_all(bs_vdesc);
1860 bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v_irn));
1861 for (k = ARR_LEN_SAFE(v->descendants) - 1; k >= 0; --k) {
1862 if (! is_Sink(v->descendants[k]))
1863 bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v->descendants[k]));
1866 /* if v is in pkiller(u) */
1867 is_pkiller = plist_has_value(u->pkiller_list, v_irn);
1869 /* for all vv in pkiller(u) */
1870 foreach_plist(u->pkiller_list, el) {
1871 ir_node *vv_irn = plist_element_get_value(el);
1874 if (is_Sink(vv_irn) || is_cfop(vv_irn))
1878 add_edge = vv_irn != v_irn && skip_Proj(vv_irn) != skip_Proj(v_irn);
1880 add_edge = ! heights_reachable_in_block(rss->h, skip_Proj(vv_irn), skip_Proj(v_irn));
1883 As we add an edge from vv -> v, we have to make sure,
1884 that there exists no path from v to vv.
1888 unsigned vv_height = get_irn_height(rss->h, vv_irn);
1889 unsigned critical_path_cost;
1893 mu1 = | descendants(v) cut sat_vals |
1894 the number of saturating values which cannot
1895 be simultaneously alive with u
1897 bitset_copy(bs_tmp, bs_vdesc);
1898 bitset_and(bs_tmp, bs_sv);
1899 mu1 = bitset_popcount(bs_tmp);
1902 mu2 = | accum_desc_all_pkiller(u) without descendants(v) |
1905 bitset_copy(bs_tmp, bs_ukilldesc);
1906 bitset_andnot(bs_tmp, bs_vdesc);
1907 mu2 = bitset_popcount(bs_tmp);
1913 /* omega1 = mu1 - mu2 */
1919 /* omega2 = increase of critical path */
1920 critical_path_cost =
1921 v_height /* longest path from v to sink */
1922 + rss->max_height - vv_height /* longest path from source to vv */
1926 If critical_path_cost > max_height -> the new edge
1927 would increase the longest critical path by the difference.
1929 omega2 = critical_path_cost > rss->max_height ? critical_path_cost - rss->max_height : 0;
1931 /* this keeps track of the edge with the best benefit */
1932 if (omega1 >= num_regs - n && omega1 < best_benefit) {
1933 min_benefit_edge.src = v_irn;
1934 min_benefit_edge.tgt = vv_irn;
1939 best_benefit = omega1;
1940 ser->new_killer = is_pkiller;
1943 /* this keeps track of the edge with the best omega1 costs where omega2 == 0 */
1944 if (omega2 == 0 && omega1 >= num_regs - n && omega1 < best_benefit_omega20) {
1945 min_omega20_edge.src = v_irn;
1946 min_omega20_edge.tgt = vv_irn;
1951 best_benefit_omega20 = omega1;
1952 ser->new_killer = is_pkiller;
1955 best_omega2 = MIN(best_omega2, omega2);
1957 DBG((rss->dbg, LEVEL_2, "\t\tfound %+F -> %+F (w1 %d, w2 %d)\n",
1958 v_irn, vv_irn, omega1, omega2));
1960 } /* for all vv in pkiller(u) */
1961 } /* for all v in sat_vals */
1962 } /* for all u in sat_vals */
1967 if (best_omega2 == 0) {
1968 ser->u = ser_u_omega20;
1969 ser->v = ser_v_omega20;
1970 ser->edge->src = min_omega20_edge.src;
1971 ser->edge->tgt = min_omega20_edge.tgt;
1972 ser->omega1 = best_benefit_omega20;
1973 ser->omega2 = best_omega2;
1976 ser->u = ser_u_omega1;
1977 ser->v = ser_v_omega1;
1978 ser->edge->src = min_benefit_edge.src;
1979 ser->edge->tgt = min_benefit_edge.tgt;
1980 ser->omega1 = best_benefit;
1981 ser->omega2 = best_omega2;
1986 #undef IS_UNSERIALIZABLE_NODE
1990 * Perform the value serialization heuristic and add all
1991 * computed serialization edges as dependencies to the irg.
1993 static void perform_value_serialization_heuristic(rss_t *rss)
1995 bitset_t *arch_nonign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls));
1996 bitset_t *abi_ign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls));
1997 unsigned available_regs, iteration;
1999 ir_nodeset_t *sat_vals;
2000 pset *ser_set = new_pset(cmp_rss_edges, 20);
2002 /* available_regs = R = |arch_non_ignore_regs cut ~abi_ignore_regs| */
2003 arch_put_non_ignore_regs(rss->cls, arch_nonign_bs);
2004 be_abi_put_ignore_regs(rss->abi, rss->cls, abi_ign_bs);
2005 bitset_andnot(arch_nonign_bs, abi_ign_bs);
2006 available_regs = bitset_popcount(arch_nonign_bs);
2007 //num_live = pset_count(rss->live_block);
2008 //available_regs -= num_live < available_regs ? num_live : 0;
2010 DBG((rss->dbg, LEVEL_1, "\n\t#available regs: %d\n\n", available_regs));
2013 At first we need to compute the disjoint value DAG (DVG = {V, E_dv}).
2014 V = set of all nodes we are currently interested in
2015 E_dv = there is an edge from u to v iff v is a descendant of killer(u), forall u, v in V
2017 ir_nodeset_init_size(&dvg.nodes, plist_count(rss->nodes));
2018 dvg.edges = new_pset(cmp_rss_edges, plist_count(rss->nodes) * 5);
2019 compute_dvg(rss, &dvg);
2022 Then we perform the heuristic serialization algorithm
2023 on the DVG which gives us all necessary serialization
2026 DBG((rss->dbg, LEVEL_1, "\tcomputing maximal antichain:\n"));
2028 sat_vals = compute_maximal_antichain(rss, &dvg, iteration++);
2029 while (sat_vals && (ir_nodeset_size(sat_vals) > available_regs)) {
2030 serialization_t *ser, best_ser;
2031 rss_edge_t *edge = OALLOC(phase_obst(&rss->ph), rss_edge_t);
2032 ir_node *dep_src, *dep_tgt;
2034 best_ser.edge = edge;
2035 ser = compute_best_admissible_serialization(rss, sat_vals, &best_ser, available_regs);
2037 DBG((rss->dbg, LEVEL_1, "\tcurrent register saturation %d, target %d\n", ir_nodeset_size(sat_vals), available_regs));
2040 DBG((rss->dbg, LEVEL_1, "\tno RS improving serialization found, breaking at iteration %d\n", iteration));
2044 /* Insert the serialization as dependency edge into the irg. */
2045 DBG((rss->dbg, LEVEL_1, "\tserializing %+F -> %+F with edge %+F -> %+F and cost %d, %d\n",
2046 ser->u->irn, ser->v->irn, ser->edge->src, ser->edge->tgt, ser->omega1, ser->omega2));
2048 if (pset_find(ser_set, ser->edge, HASH_RSS_EDGE(ser->edge)))
2049 ir_printf("WARNING: serialization %+F -> %+F computed twice!\n", ser->edge->src, ser->edge->tgt);
2052 pset_insert(ser_set, ser->edge, HASH_RSS_EDGE(ser->edge));
2054 /* update the dvg */
2055 update_dvg(rss, &dvg, ser->v, ser->u);
2056 update_dvg(rss, &dvg, get_rss_irn(rss, ser->edge->src), get_rss_irn(rss, ser->edge->tgt));
2057 if (sat_vals != NULL) {
2058 ir_nodeset_destroy(sat_vals);
2062 dep_src = skip_Proj(ser->edge->src);
2063 dep_tgt = ser->edge->tgt;
2064 add_irn_dep(dep_src, dep_tgt);
2066 /* Update descendants, consumer and pkillers of the target */
2067 update_node_info(rss, ser->edge->tgt, ser->edge->src);
2069 /* TODO: try to find a cheaper way for updating height information */
2070 rss->max_height = heights_recompute_block(rss->h, rss->block);
2072 /* Recompute the antichain for next serialization */
2073 DBG((rss->dbg, LEVEL_1, "\tre-computing maximal antichain:\n"));
2074 sat_vals = compute_maximal_antichain(rss, &dvg, iteration++);
2077 ir_nodeset_destroy(&dvg.nodes);
2078 del_pset(dvg.edges);
2082 * Do initial calculations for a block.
2084 static void process_block(ir_node *block, void *env)
2088 const ir_edge_t *edge;
2090 phase_init(&rss->ph, rss->irg, init_rss_irn);
2092 DBG((rss->dbg, LEVEL_1, "preprocessing block %+F\n", block));
2095 /* build an index map for all nodes in the current block */
2097 n = get_irn_n_edges(block);
2098 NEW_ARR_A(int *, rss->idx_map, n);
2099 foreach_out_edge(block, edge) {
2100 ir_node *irn = get_edge_src_irn(edge);
2101 rss->idx_map[i++] = get_irn_idx(irn);
2103 qsort(rss->idx_map, n, sizeof(rss->idx_map[0]), cmp_int);
2104 rss->max_height = heights_recompute_block(rss->h, block);
2106 /* loop over all register classes */
2107 for (i = arch_env_get_n_reg_class(rss->arch_env) - 1; i >= 0; --i) {
2108 const arch_register_class_t *cls = arch_env_get_reg_class(rss->arch_env, i);
2111 DBG((rss->dbg, LEVEL_1, "register class %s\n", arch_register_class_name(cls)));
2113 /* Get all live value at end of Block having current register class */
2114 ir_nodeset_init(&rss->live_block);
2115 be_liveness_end_of_block(rss->liveness, rss->cls, rss->block, &rss->live_block);
2117 /* reset the list of interesting nodes */
2118 plist_clear(rss->nodes);
2119 plist_insert_back(rss->nodes, _sink);
2121 /* collect all nodes having a certain register class */
2122 foreach_out_edge(block, edge) {
2123 ir_node *irn = get_edge_src_irn(edge);
2124 ir_mode *mode = get_irn_mode(irn);
2128 - mode_T nodes (the projs are asked)
2129 - mode_X nodes (control flow nodes are always scheduled last)
2130 - Keeps (they are always immediately scheduled)
2131 - Phi (same as Keep)
2133 if (mode == mode_T || mode == mode_X || is_Phi(irn))
2137 In case of a proj, we skip
2138 - Barrier (they are a Barrier :)
2140 - the Proj itself, as it's scheduled always with it's super node
2143 ir_node *pred = get_Proj_pred(irn);
2144 if (be_is_Barrier(pred) || be_is_Start(pred))
2148 /* calculate the descendants and consumer for each node in the block */
2149 collect_node_info(rss, skip_Proj(irn));
2151 if (be_is_Keep(irn))
2154 if (!arch_irn_is_ignore(irn) &&
2155 arch_get_irn_reg_class_out(irn) == cls) {
2156 plist_insert_back(rss->nodes, skip_Proj(irn));
2161 /* compute the potential killing set PK(G) */
2162 compute_pkill_set(rss);
2164 /* compute the killing function k* */
2165 compute_killing_function(rss);
2168 Compute the heuristic value serialization and
2169 add the necessary dependencies to the irg.
2171 perform_value_serialization_heuristic(rss);
2173 ir_nodeset_destroy(&rss->live_block);
2176 phase_deinit(&rss->ph);
2179 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_schedrss);
2180 void be_init_schedrss(void)
2182 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
2183 lc_opt_entry_t *sched_grp = lc_opt_get_grp(be_grp, "sched");
2184 lc_opt_entry_t *rss_grp = lc_opt_get_grp(sched_grp, "rss");
2186 lc_opt_add_table(rss_grp, rss_option_table);
2190 * Preprocess the irg for scheduling.
2192 void rss_schedule_preparation(ir_graph *irg)
2196 FIRM_DBG_REGISTER(rss.dbg, "firm.be.sched.rss");
2198 //firm_dbg_set_mask(rss.dbg, LEVEL_1 | LEVEL_2 | LEVEL_3);
2200 init_rss_special_nodes(irg);
2203 rss.arch_env = be_get_irg_arch_env(irg);
2204 rss.abi = be_get_irg_abi(irg);
2205 rss.h = heights_new(irg);
2206 rss.nodes = plist_new();
2207 rss.opts = &rss_options;
2208 rss.liveness = be_liveness(irg);
2209 be_liveness_assure_sets(rss.liveness);
2210 irg_block_walk_graph(irg, NULL, process_block, &rss);
2211 heights_free(rss.h);
2212 plist_free(rss.nodes);
2213 be_liveness_free(rss.liveness);
2215 if (be_get_irg_options(irg)->dump_flags & DUMP_SCHED)
2216 dump_ir_graph(irg, "rss");