X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeschedrss.c;h=f8d54ed3a136761e37ea13c273253256c5d0a049;hb=80a6158fdd766f42ee6c508a773bc114ff1b61f3;hp=6575100fe14191a0707b1719d5a85a74ef8f1260;hpb=d9d8809fef34d7bb639b61c8ca3c2a372f8eb790;p=libfirm diff --git a/ir/be/beschedrss.c b/ir/be/beschedrss.c index 6575100fe..f8d54ed3a 100644 --- a/ir/be/beschedrss.c +++ b/ir/be/beschedrss.c @@ -23,6 +23,7 @@ #include "ircons_t.h" #include "irphase_t.h" #include "irgwalk.h" +#include "irdump.h" #include "irtools.h" #include "irbitset.h" #include "irprintf.h" @@ -33,9 +34,16 @@ #include "height.h" #include "beabi.h" +#include "bemodule.h" #include "benode_t.h" #include "besched_t.h" +#ifdef WITH_LIBCORE +#include +#include +#endif /* WITH_LIBCORE */ + + #define ARR_LEN_SAFE(arr) ((arr) != NULL ? ARR_LEN((arr)) : 0) #define HASH_RSS_EDGE(edge) ((get_irn_node_nr((edge)->src) << 16) | (get_irn_node_nr((edge)->tgt) & 0xFFFF)) @@ -44,6 +52,11 @@ #define BLOCK_IDX_MAP(rss, irn) bsearch_for_index(get_irn_idx((irn)), (rss)->idx_map, ARR_LEN_SAFE((rss)->idx_map), 1) +/* the rss options */ +typedef struct _rss_opts_t { + int dump_flags; +} rss_opts_t; + /* Represents a child with associated costs */ typedef struct _child { ir_node *irn; @@ -82,32 +95,22 @@ typedef struct _rss_irn { ir_node **consumer; /**< Sorted consumer array (needed for faster access) */ plist_t *parent_list; /**< List of parents */ - ir_node **parents; /**< Sorted parent array (needed for faster access) */ + plist_t *pkiller_list; /**< List of potential killers */ plist_t *descendant_list; /**< List of descendants */ ir_node **descendants; /**< Sorted descendant array (needed for faster access) */ - plist_t *pkiller_list; /**< List of potential killers */ - ir_node **pkillers; /**< Sorted pkiller array (needed for faster access) */ - -#if 0 - plist_t *dvg_desc_list; /**< List of all descendants in the DVG */ - ir_node **dvg_desc; /**< Sorted dvg descendant array (needed for faster access) */ - - plist_t *dvg_pkiller_list; /**< List of potential killers in the DVG */ - ir_node **dvg_pkiller; /**< Sorted dvg pkiller array (needed for faster access) */ - - plist_t *dvg_user_list; /**< List of users in the disjoint value DAG DVG */ -#endif - plist_t *kill_value_list; /**< List of values getting potentially killed by this node */ - ir_node *killer; /**< The selected unique killer */ ir_node *irn; /**< The corresponding firm node to this rss_irn */ chain_t *chain; /**< The chain, this node is associated to */ + unsigned desc_walk; /**< visited flag for collecting descendants */ + unsigned kill_count; /**< number of nodes killed by this one */ + unsigned live_out : 1; /**< irn has consumers outside of it's block */ unsigned visited : 1; /**< visited flag for bipartite decomposition */ + unsigned havecons : 1; /**< visited flag collect consumer */ unsigned handled : 1; /**< flag indicating whether or not the list structures have been build */ unsigned dumped : 1; /**< flag indication whether or not this node was dumped */ } rss_irn_t; @@ -119,6 +122,7 @@ typedef struct _serialization { rss_edge_t *edge; /* the edge selected for the serialization */ int omega1; /* estimated: available regs - RS reduction */ int omega2; /* increase in critical path length */ + int new_killer; } serialization_t; typedef struct _rss { @@ -132,6 +136,9 @@ typedef struct _rss { ir_node *block; /**< The current block in progress. */ int *idx_map; /**< Mapping irn indices to per block indices */ unsigned max_height; /**< maximum height in the current block */ + rss_opts_t *opts; /**< The options */ + be_lv_t *liveness; /**< The liveness information for this irg */ + pset *live_block; /**< Values alive at end of block */ const arch_register_class_t *cls; /**< The current register class */ DEBUG_ONLY(firm_dbg_module_t *dbg); } rss_t; @@ -143,7 +150,7 @@ typedef struct _rss { * a source and a sink for all live-in and live-out values of a block */ -static enum { +enum { iro_rss_Source, iro_rss_Sink, iro_rss_last @@ -155,6 +162,42 @@ static ir_node *_sink = NULL; #define is_Source(irn) ((irn) == _source) #define is_Sink(irn) ((irn) == _sink) +enum { + RSS_DUMP_NONE = 0, + RSS_DUMP_CBC = 1 << 0, + RSS_DUMP_PKG = 1 << 1, + RSS_DUMP_KILL = 1 << 2, + RSS_DUMP_DVG = 1 << 3, + RSS_DUMP_MAXAC = 1 << 4, + RSS_DUMP_ALL = (RSS_DUMP_MAXAC << 1) - 1, +}; + +static rss_opts_t rss_options = { + RSS_DUMP_NONE, +}; + +#ifdef WITH_LIBCORE +static const lc_opt_enum_int_items_t dump_items[] = { + { "none", RSS_DUMP_NONE }, + { "cbc", RSS_DUMP_CBC }, + { "pkg", RSS_DUMP_PKG }, + { "kill", RSS_DUMP_KILL }, + { "dvg", RSS_DUMP_DVG }, + { "maxac", RSS_DUMP_MAXAC }, + { "all", RSS_DUMP_ALL }, + { NULL, 0 } +}; + +static lc_opt_enum_int_var_t dump_var = { + &rss_options.dump_flags, dump_items +}; + +static const lc_opt_table_entry_t rss_option_table[] = { + LC_OPT_ENT_ENUM_MASK("dump", "dump phases", &dump_var), + { NULL } +}; +#endif /* WITH_LIBCORE */ + /****************************************************************************** * _ _ __ _ _ * | | | | / _| | | (_) @@ -255,19 +298,21 @@ static ir_node **build_sorted_array_from_list(plist_t *irn_list, struct obstack * *****************************************************/ +#ifdef DEBUG_libfirm static void dump_nodeset(nodeset *ns, const char *prefix) { ir_node *irn; foreach_nodeset(ns, irn) { - ir_printf("%s%+F\n", prefix, irn); + ir_fprintf(stderr, "%s%+F\n", prefix, irn); } } +#endif static void build_file_name(rss_t *rss, const char *suffix, size_t suf_len, char *buf, size_t len) { const char *irg_name; memset(buf, 0, len); irg_name = get_entity_name(get_irg_entity(rss->irg)); - snprintf(buf, len - suf_len, "%s-%s-block-%d", + snprintf(buf, len - suf_len, "%s-%s-block-%ld", irg_name, arch_register_class_name(rss->cls), get_irn_node_nr(rss->block)); strcat(buf, suffix); } @@ -323,11 +368,13 @@ static void debug_vcg_dump_kill(rss_t *rss) { fprintf(f, "layoutalgorithm: mindepth\n"); fprintf(f, "manhattan_edges: yes\n\n"); - /* first: reset dumped flag of all nodes */ - foreach_plist(rss->nodes, el) { - ir_node *irn = plist_element_get_value(el); - rss_irn_t *rirn = get_rss_irn(rss, irn); - rirn->dumped = 0; + { + /* reset dump_flag */ + ir_node *irn; + foreach_phase_irn(&rss->ph, irn) { + rss_irn_t *node = get_rss_irn(rss, irn); + node->dumped = 0; + } } /* dump all nodes and their killers */ @@ -367,7 +414,7 @@ static void debug_vcg_dump_pkg(rss_t *rss, nodeset *max_ac, int iteration) { snprintf(suffix, 32, "%s", suffix1); } else { - snprintf(suffix, 32, "-%0.2d%s", iteration, suffix2); + snprintf(suffix, 32, "-%02d%s", iteration, suffix2); } build_file_name(rss, suffix, strlen(suffix) + 1, file_name, sizeof(file_name)); @@ -378,6 +425,15 @@ static void debug_vcg_dump_pkg(rss_t *rss, nodeset *max_ac, int iteration) { fprintf(f, "layoutalgorithm: mindepth\n"); fprintf(f, "manhattan_edges: yes\n\n"); + { + /* reset dump_flag */ + ir_node *irn; + foreach_phase_irn(&rss->ph, irn) { + rss_irn_t *node = get_rss_irn(rss, irn); + node->dumped = 0; + } + } + foreach_plist(rss->nodes, el) { ir_node *irn = plist_element_get_value(el); rss_irn_t *rirn = get_rss_irn(rss, irn); @@ -388,8 +444,13 @@ static void debug_vcg_dump_pkg(rss_t *rss, nodeset *max_ac, int iteration) { if (max_ac && nodeset_find(max_ac, irn)) c1 = "color:yellow"; - ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(irn), irn, c1); - rirn->dumped = 1; + if (! rirn->dumped) { + if (rirn->chain) + ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(irn), irn, rirn->chain->nr, c1); + else + ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(irn), irn, c1); + rirn->dumped = 1; + } foreach_plist(rirn->pkiller_list, k_el) { ir_node *pkiller = plist_element_get_value(k_el); @@ -400,7 +461,10 @@ static void debug_vcg_dump_pkg(rss_t *rss, nodeset *max_ac, int iteration) { c2 = "color:yellow"; if (! pk_rirn->dumped) { - ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(pkiller), pkiller, c2); + if (pk_rirn->chain) + ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(pkiller), pkiller, pk_rirn->chain->nr, c2); + else + ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(pkiller), pkiller, c2); pk_rirn->dumped = 1; } ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n", @@ -434,9 +498,6 @@ static void debug_vcg_dump_dvg(rss_t *rss, dvg_t *dvg) { /* dump all edges */ foreach_pset(dvg->edges, edge) { - rss_irn_t *src = get_rss_irn(rss, edge->src); - rss_irn_t *tgt = get_rss_irn(rss, edge->tgt); - ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n", get_irn_node_nr(edge->src), get_irn_node_nr(edge->tgt)); } @@ -488,33 +549,27 @@ static void debug_vcg_dump_dvg_pkiller(rss_t *rss, dvg_t *dvg) { static void *init_rss_irn(phase_t *ph, ir_node *irn, void *old) { rss_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0])); - res->descendant_list = plist_obstack_new(phase_obst(ph)); - res->descendants = NULL; - - res->consumer_list = plist_obstack_new(phase_obst(ph)); - res->consumer = NULL; + res->descendant_list = plist_obstack_new(phase_obst(ph)); + res->descendants = NULL; - res->pkiller_list = plist_obstack_new(phase_obst(ph)); - res->pkillers = NULL; + res->consumer_list = plist_obstack_new(phase_obst(ph)); + res->consumer = NULL; - res->parent_list = plist_obstack_new(phase_obst(ph)); - res->parents = NULL; + res->pkiller_list = plist_obstack_new(phase_obst(ph)); - //res->dvg_desc_list = plist_obstack_new(phase_obst(ph)); - //res->dvg_desc = NULL; + res->parent_list = plist_obstack_new(phase_obst(ph)); - res->kill_value_list = plist_obstack_new(phase_obst(ph)); - //res->dvg_user_list = plist_obstack_new(phase_obst(ph)); - //res->dvg_pkiller_list = plist_obstack_new(phase_obst(ph)); + res->killer = NULL; + res->irn = irn; + res->chain = NULL; - res->killer = NULL; - res->irn = irn; - res->chain = NULL; - - res->live_out = 0; - res->visited = 0; - res->handled = 0; - res->dumped = 0; + res->kill_count = 0; + res->desc_walk = 0; + res->live_out = 0; + res->visited = 0; + res->handled = 0; + res->dumped = 0; + res->havecons = 0; return res; } @@ -522,11 +577,20 @@ static void *init_rss_irn(phase_t *ph, ir_node *irn, void *old) { /** * Collect all nodes data dependent on current node. */ -static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int *got_sink) { +static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int *got_sink, unsigned cur_desc_walk) { const ir_edge_t *edge; - ir_node *block = rss->block; - ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP }; - int i; + rss_irn_t *cur_node = get_rss_irn(rss, irn); + ir_node *block = rss->block; + ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP }; + int i; + + if (cur_node->desc_walk >= cur_desc_walk) + return; + cur_node->desc_walk = cur_desc_walk; + + /* Stop at Barriers */ + if (be_is_Barrier(irn)) + return; /* loop over normal and dependency edges */ for (i = 0; i < 2; ++i) { @@ -537,20 +601,38 @@ static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int * if (arch_irn_is(rss->arch_env, user, ignore)) continue; - /* check if user lives in block and is not a control flow node */ - if (get_nodes_block(user) == block && get_irn_mode(user) != mode_X) { - /* skip mode_T nodes */ - if (get_irn_mode(user) != mode_T && ! plist_has_value(rirn->descendant_list, user)) { - plist_insert_back(rirn->descendant_list, user); - DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", user)); - } - collect_descendants(rss, rirn, user, got_sink); + /* + (a) mode_X means Jump -> out_edge + (b) Phi as user of a normal node -> out-edge + */ + if (get_irn_mode(user) == mode_X || is_Phi(user)) { + if (! *got_sink) + goto force_sink; + else + continue; } - else if (! *got_sink) { - /* user lives out of block: add sink as descendant if not already done */ - plist_insert_back(rirn->descendant_list, _sink); - *got_sink = 1; - DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", _sink)); + + if (is_Proj(user)) { + + //if (arch_get_irn_reg_class(rss->arch_env, user, -1) == rss->cls) + collect_descendants(rss, rirn, user, got_sink, cur_desc_walk); + } + else { + /* check if user lives in block and is not a control flow node */ + if (get_nodes_block(user) == block) { + if (! plist_has_value(rirn->descendant_list, user)) { + plist_insert_back(rirn->descendant_list, user); + DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", user)); + } + collect_descendants(rss, rirn, user, got_sink, cur_desc_walk); + } + else if (! *got_sink) { +force_sink: + /* user lives out of block: add sink as descendant if not already done */ + plist_insert_back(rirn->descendant_list, _sink); + *got_sink = 1; + DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", _sink)); + } } } } @@ -559,34 +641,13 @@ static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int * /** * Handles a single consumer. */ -static int collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *consumer, int got_sink) { - ir_node *block = rss->block; - ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP }; - int i; - - if (get_nodes_block(consumer) == block) { - /* the consumer of a mode_T node are it's projs */ - if (get_irn_mode(consumer) == mode_T) { - const ir_edge_t *cons_edge; +static void collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *consumer, int *got_sink) { + ir_node *block = rss->block; - DBG((rss->dbg, LEVEL_2, "\t\tmode_T consumer %+F skipped\n", consumer)); + assert(! is_Proj(consumer) && "Cannot handle Projs"); - for (i = 0; i < 2; ++i) { - foreach_out_edge_kind(consumer, cons_edge, ekind[i]) { - ir_node *cons_proj = get_edge_src_irn(cons_edge); - - assert(get_nodes_block(cons_proj) == block && "Proj in wrong block!"); - - /* skip ignore nodes, as they do not really contribute to register pressure */ - if (arch_irn_is(rss->arch_env, cons_proj, ignore)) - continue; - - plist_insert_back(rss_irn->consumer_list, cons_proj); - DBG((rss->dbg, LEVEL_3, "\t\t\treal consumer %+F\n", cons_proj)); - } - } - } - else if (! arch_irn_is(rss->arch_env, consumer, ignore)) { + if (! is_Phi(consumer) && ! is_Block(consumer) && get_nodes_block(consumer) == block) { + if (! arch_irn_is(rss->arch_env, consumer, ignore) && ! plist_has_value(rss_irn->consumer_list, consumer)) { plist_insert_back(rss_irn->consumer_list, consumer); DBG((rss->dbg, LEVEL_2, "\t\tconsumer %+F\n", consumer)); } @@ -594,97 +655,62 @@ static int collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *cons else { rss_irn->live_out = 1; DBG((rss->dbg, LEVEL_2, "\t\tlive out %+F", consumer)); - if (! got_sink) { + if (! *got_sink) { plist_insert_back(rss_irn->consumer_list, _sink); - got_sink = 1; + *got_sink = 1; DB((rss->dbg, LEVEL_2, ", %+F added instead", _sink)); } DB((rss->dbg, LEVEL_2, "\n")); } - - return got_sink; } /** * Collect all nodes consuming the value(s) produced by current node. */ -static void collect_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *irn) { +static void collect_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *irn, int *got_sink) { const ir_edge_t *edge; - int got_sink = 0; int i; - ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP }; + ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP }; + rss_irn_t *cur_node = get_rss_irn(rss, irn); + + if (cur_node->havecons) + return; + cur_node->havecons = 1; for (i = 0; i < 2; ++i) { foreach_out_edge_kind(irn, edge, ekind[i]) { ir_node *consumer = get_edge_src_irn(edge); - got_sink = collect_single_consumer(rss, rss_irn, consumer, got_sink); - } - } -} - -#if 0 -/** - * We need to build the consumer and descendant list for _source. - */ -static void collect_node_info_source(rss_t *rss) { - const ir_edge_t *edge; - rss_irn_t *rirn = get_rss_irn(rss, _source); - ir_node *block = rss->block; - - if (rirn->handled) - return; - - foreach_out_edge(block, edge) { - ir_node *irn = get_edge_src_irn(edge); - int i; - - for (i = get_irn_arity(n) - 1; i >= 0; --i) { + if (is_Proj(consumer)) { + //if (arch_get_irn_reg_class(rss->arch_env, consumer, -1) == rss->cls) + collect_consumer(rss, rss_irn, consumer, got_sink); + } + else + collect_single_consumer(rss, rss_irn, consumer, got_sink); } } } -static void reset_node_info(rss_irn_t *rss_irn) { - /* Beware: array data resides on phase obstack, so it gets removed automatically */ - - plist_clear(rss_irn->consumer_list); - rss_irn->consumer = NULL; - - plist_clear(rss_irn->parent_list); - rss_irn->parents = NULL; - - plist_clear(rss_irn->descendant_list); - rss_irn->descendants = NULL; - - plist_clear(rss_irn->pkiller_list); - rss_irn->pkillers = NULL; - - plist_clear(rss_irn->kill_value_list); - - rss_irn->killer = NULL; - rss_irn->live_out = 0; - rss_irn->visited = 0; - rss_irn->handled = 0; -} -#endif /* if 0 */ - /** * Collects all consumer and descendant of a irn. */ static void collect_node_info(rss_t *rss, ir_node *irn) { - rss_irn_t *rss_irn = get_rss_irn(rss, irn); - int got_sink; + static unsigned cur_desc_walk = 0; + rss_irn_t *rss_irn = get_rss_irn(rss, irn); + int got_sink; - assert(get_irn_mode(irn) != mode_T && "Cannot handle mode_T nodes."); + assert(! is_Proj(irn) && "Cannot handle Projs."); /* check if node info is already available */ if (rss_irn->handled) - phase_reinit_single_irn_data(&rss->ph, irn); + return; + //phase_reinit_single_irn_data(&rss->ph, irn); DBG((rss->dbg, LEVEL_1, "\tcomputing consumers of %+F:\n", irn)); /* collect all consumer */ - collect_consumer(rss, rss_irn, irn); + got_sink = 0; + collect_consumer(rss, rss_irn, irn, &got_sink); /* build sorted consumer array */ rss_irn->consumer = build_sorted_array_from_list(rss_irn->consumer_list, phase_obst(&rss->ph)); @@ -693,7 +719,7 @@ static void collect_node_info(rss_t *rss, ir_node *irn) { /* collect descendants */ got_sink = 0; - collect_descendants(rss, rss_irn, irn, &got_sink); + collect_descendants(rss, rss_irn, irn, &got_sink, ++cur_desc_walk); /* build sorted descendant array */ rss_irn->descendants = build_sorted_array_from_list(rss_irn->descendant_list, phase_obst(&rss->ph)); @@ -769,16 +795,6 @@ static void update_node_info(rss_t *rss, ir_node *irn, ir_node *pk_irn) { node->descendants = build_sorted_array_from_list(node->descendant_list, phase_obst(&rss->ph)); } -#if 0 - /* check, if pkiller is a potential killer of irn */ - if (is_potential_killer(rss, pkiller, node)) { - if (! plist_has_value(node->pkiller_list, pk_irn)) - plist_insert_back(node->pkiller_list, pk_irn); - if (! plist_has_value(pkiller->kill_value_list, irn)) - plist_insert_back(pkiller->kill_value_list, irn); - DBG((rss->dbg, LEVEL_1, "\tpotential killer %+F added to %+F\n", pk_irn, irn)); - } -#endif } /** @@ -802,8 +818,7 @@ static void compute_pkill_set(rss_t *rss) { if (is_potential_killer(rss, v, u)) { if (! plist_has_value(u->pkiller_list, v_irn)) plist_insert_back(u->pkiller_list, v_irn); - if (! plist_has_value(v->kill_value_list, u_irn)) - plist_insert_back(v->kill_value_list, u_irn); + v->kill_count++; DBG((rss->dbg, LEVEL_2, "\t\tpotential killer %+F\n", v_irn)); } } @@ -811,10 +826,8 @@ static void compute_pkill_set(rss_t *rss) { u->killer = _sink; } - DEBUG_ONLY( - if (firm_dbg_get_mask(rss->dbg)) - debug_vcg_dump_pkg(rss, NULL, 0); - ) + if (rss->opts->dump_flags & RSS_DUMP_PKG) + debug_vcg_dump_pkg(rss, NULL, 0); } /** @@ -844,6 +857,7 @@ static void build_kill_edges(rss_t *rss, pset *epk) { } } +#ifdef DEBUG_libfirm /* print the given cbc for debugging purpose */ static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc) { ir_node *n; @@ -862,6 +876,7 @@ static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc) { DBG((mod, LEVEL_3, "\t\t\t%+F -> %+F\n", ke->src, ke->tgt)); } } +#endif /** * Construct the bipartite decomposition. @@ -883,6 +898,7 @@ static void compute_bipartite_decomposition(rss_t *rss) { rss_irn_t *u = get_rss_irn(rss, u_irn); int p_change = 1; int c_change = 1; + int vrfy_ok = 1; cbc_t *cbc; plist_element_t *el2; @@ -925,32 +941,26 @@ static void compute_bipartite_decomposition(rss_t *rss) { /* accumulate parents */ foreach_nodeset(cbc->children, t_irn) { - rss_irn_t *t = get_rss_irn(rss, t_irn); - plist_element_t *kvl_el; - foreach_pset(epk, k_edge) { ir_node *val = k_edge->src; - if (k_edge->src == t_irn && ! nodeset_find(cbc->parents, k_edge->src)) { + if (k_edge->tgt == t_irn && ! nodeset_find(cbc->parents, val)) { nodeset_insert(cbc->parents, val); p_change = 1; - DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents\n", val)); + DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (killed by %+F)\n", val, t_irn)); } } } /* accumulate children */ foreach_nodeset(cbc->parents, s_irn) { - rss_irn_t *s = get_rss_irn(rss, s_irn); - plist_element_t *pkl_el; - - foreach_plist(s->pkiller_list, pkl_el) { - ir_node *val = plist_element_get_value(pkl_el); + foreach_pset(epk, k_edge) { + ir_node *val = k_edge->tgt; - if (! nodeset_find(cbc->children, val)) { + if (k_edge->src == s_irn && ! nodeset_find(cbc->children, val)) { nodeset_insert(cbc->children, val); c_change = 1; - DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children\n", val)); + DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (kills %+F)\n", val, s_irn)); } } } @@ -961,10 +971,12 @@ static void compute_bipartite_decomposition(rss_t *rss) { rss_irn_t *s = get_rss_irn(rss, s_irn); s->visited = 1; /* assure bipartite property */ +#if 0 if (nodeset_find(cbc->children, s_irn)) { nodeset_remove(cbc->children, s_irn); DBG((rss->dbg, LEVEL_3, "\t\t\t%+F removed from to children\n", s_irn)); } +#endif } /* update edges */ @@ -985,13 +997,36 @@ static void compute_bipartite_decomposition(rss_t *rss) { pset_remove(epk, kedge_root, HASH_RSS_EDGE(kedge_root)); } + /* verify the cbc */ + foreach_nodeset(cbc->parents, s_irn) { + int is_killed = 0; + + foreach_pset(cbc->kill_edges, k_edge) { + if (k_edge->src == s_irn) { + is_killed = 1; + pset_break(cbc->kill_edges); + break; + } + } + + if (! is_killed) { + vrfy_ok = 0; + ir_fprintf(stderr, "Warning: parent %+F is not killed in current cbc\n", s_irn); + } + } + assert(vrfy_ok && "Verification of CBC failed"); + /* add the connected bipartite component */ - pset_insert(rss->cbc_set, cbc, (unsigned)cbc->nr); - DBG((rss->dbg, LEVEL_1, "\tbipartite component %d inserted:\n", cbc->nr)); - DEBUG_ONLY(debug_print_cbc(rss->dbg, cbc)); + if (nodeset_count(cbc->parents) > 0 && nodeset_count(cbc->children) > 0 && pset_count(cbc->kill_edges) > 0) + pset_insert(rss->cbc_set, cbc, (unsigned)cbc->nr); + DBG((rss->dbg, LEVEL_2, "\tbipartite component %d inserted:\n", cbc->nr)); + DEBUG_ONLY( + if (firm_dbg_get_mask(rss->dbg) & LEVEL_2) + debug_print_cbc(rss->dbg, cbc); + ); } - if (firm_dbg_get_mask(rss->dbg)) + if (rss->opts->dump_flags & RSS_DUMP_CBC) debug_vcg_dump_bipartite(rss); del_pset(epk); @@ -1153,10 +1188,8 @@ static void compute_killing_function(rss_t *rss) { DEL_ARR_F(sks); } - DEBUG_ONLY( - if (firm_dbg_get_mask(rss->dbg)) - debug_vcg_dump_kill(rss); - ); + if (rss->opts->dump_flags & RSS_DUMP_KILL) + debug_vcg_dump_kill(rss); del_pset(rss->cbc_set); obstack_free(&obst, NULL); @@ -1166,26 +1199,33 @@ static void compute_killing_function(rss_t *rss) { * Adds the edge src -> tgt to the dvg. Checks if reverse edge is already there (asserts). */ static INLINE void add_dvg_edge(rss_t *rss, dvg_t *dvg, ir_node *src, ir_node *tgt, int have_source) { - rss_edge_t *dvg_edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*dvg_edge)); + rss_edge_t *dvg_edge; rss_edge_t key; if (! have_source) nodeset_insert(dvg->nodes, src); + else + assert(nodeset_find(dvg->nodes, src) != NULL && "Wrong assumption"); nodeset_insert(dvg->nodes, tgt); - /* add an edge to our killer */ - dvg_edge->src = src; - dvg_edge->tgt = tgt; - dvg_edge->next = NULL; - key.src = tgt; key.tgt = src; assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!"); - /* add the edge to the DVG */ - DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", src, tgt)); - pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge)); + key.src = src; + key.tgt = tgt; + if (NULL != pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) { + /* add the edge to the DVG */ + dvg_edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*dvg_edge)); + + dvg_edge->src = src; + dvg_edge->tgt = tgt; + dvg_edge->next = NULL; + + DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", src, tgt)); + pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge)); + } } /** @@ -1251,23 +1291,45 @@ static void compute_dvg(rss_t *rss, dvg_t *dvg) { #endif /* if 0 */ } - DEBUG_ONLY( - if (firm_dbg_get_mask(rss->dbg)) - debug_vcg_dump_dvg(rss, dvg); - ); + if (rss->opts->dump_flags & RSS_DUMP_DVG) + debug_vcg_dump_dvg(rss, dvg); } /** * Updates the dvg structure when a serialization edge from src -> tgt is added. */ static void update_dvg(rss_t *rss, dvg_t *dvg, rss_irn_t *src, rss_irn_t *tgt) { - int i; + int i, j, idx; + rss_edge_t *edge; + rss_edge_t **arr = alloca(pset_count(dvg->edges) * sizeof(arr[0])); - add_dvg_edge(rss, dvg, tgt->irn, src->irn, 1); + /* + Add an edge from serialization target to serialization src: + src cannot be alive with target + */ + add_dvg_edge(rss, dvg, tgt->irn, src->irn, 0); + /* Add edges to src's descendants as well, they also getting serialized. */ for (i = ARR_LEN_SAFE(src->descendants) - 1; i >= 0; --i) { add_dvg_edge(rss, dvg, tgt->irn, src->descendants[i], 1); } + + /* We also have to add edges from targets predecessors in dvg */ + idx = 0; + /* We cannot insert elements into set over which we iterate ... */ + foreach_pset(dvg->edges, edge) { + if (edge->tgt == tgt->irn) { + arr[idx++] = edge; + } + } + + for (i = 0; i < idx; ++i) { + edge = arr[i]; + add_dvg_edge(rss, dvg, edge->src, src->irn, 1); + for (j = ARR_LEN_SAFE(src->descendants) - 1; j >= 0; --j) { + add_dvg_edge(rss, dvg, edge->src, src->descendants[j], 1); + } + } } #if 0 @@ -1437,7 +1499,7 @@ static nodeset *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration) The maximum cardinality bipartite matching gives us the minimal chain partition, which corresponds to the maximum anti chains. */ - res = hungarian_solve(bp, assignment, &cost); + res = hungarian_solve(bp, assignment, &cost, 1); assert(res == 0 && "Bipartite matching failed!"); hungarian_free(bp); @@ -1507,8 +1569,13 @@ static nodeset *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration) chain such, such it is parallel with the others. */ DBG((rss->dbg, LEVEL_1, "\t\tcomputing set of saturation values (MAX AC)\n")); - DBG((rss->dbg, LEVEL_2, "\t\tstarting with:\n")); - dump_nodeset(values, "\t\t\t"); + DBG((rss->dbg, LEVEL_3, "\t\tstarting with:\n")); + + DEBUG_ONLY( + if (firm_dbg_get_mask(rss->dbg) & LEVEL_3) + dump_nodeset(values, "\t\t\t"); + ) + temp = NULL; do { /* @@ -1561,7 +1628,7 @@ static nodeset *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration) assert(el && "Missing element in chain!"); /* If u has predecessor in chain: insert the predecessor */ - if (el = plist_element_get_prev(el)) { + if (el == plist_element_get_prev(el)) { nodeset_insert(values, plist_element_get_value(el)); DBG((rss->dbg, LEVEL_3, "\t\t\tadding %+F to values\n", plist_element_get_value(el))); } @@ -1575,10 +1642,12 @@ static nodeset *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration) DEBUG_ONLY( if (firm_dbg_get_mask(rss->dbg) & LEVEL_2) { dump_nodeset(values, "\t\t\t"); - debug_vcg_dump_pkg(rss, values, iteration); } ); + if (rss->opts->dump_flags & RSS_DUMP_MAXAC) + debug_vcg_dump_pkg(rss, values, iteration); + del_nodeset(temp); return values; @@ -1598,16 +1667,16 @@ static serialization_t *compute_best_admissible_serialization(rss_t *rss, nodese bitset_t *bs_vdesc = bitset_alloca(n_idx); bitset_t *bs_tmp = bitset_alloca(n_idx); bitset_t *bs_ukilldesc = bitset_alloca(n_idx); - unsigned best_benefit = UINT_MAX; - unsigned best_omega2 = UINT_MAX; - unsigned best_benefit_omega20 = UINT_MAX; - int has_positive_omega1 = 0; + int best_benefit = INT_MAX; + int best_omega2 = INT_MAX; + int best_benefit_omega20 = INT_MAX; + int has_omega1 = 0; int j, k; ir_node *irn; rss_edge_t min_benefit_edge; rss_edge_t min_omega20_edge; - rss_irn_t *ser_u_omega1, *ser_v_omega1; - rss_irn_t *ser_u_omega20, *ser_v_omega20; + rss_irn_t *ser_u_omega1 = NULL, *ser_v_omega1 = NULL; + rss_irn_t *ser_u_omega20 = NULL, *ser_v_omega20 = NULL; DBG((rss->dbg, LEVEL_1, "\tcomputing admissible serializations:\n")); @@ -1637,20 +1706,27 @@ static serialization_t *compute_best_admissible_serialization(rss_t *rss, nodese In this case there is no serialization which could reduce the registerpressure */ -#define IS_UNSERIALIZABLE_NODE(rss_node) \ - ((plist_count(rss_node->pkiller_list) == 1) && \ - is_Sink(rss_node->killer) && \ - (plist_count(rss_node->kill_value_list) == 0)) +#define IS_UNSERIALIZABLE_NODE(rss_node) \ + ( \ + ( \ + (plist_count(rss_node->pkiller_list) == 1) && \ + is_Sink(rss_node->killer) && \ + (rss_node->kill_count == 0) \ + ) || \ + be_is_Barrier(rss_node->irn) || \ + be_is_Keep(rss_node->irn) \ + ) /* for all u in sat_vals */ for (i = 0; i < n; ++i) { - rss_irn_t *u = get_rss_irn(rss, val_arr[i]); - int u_height = get_irn_height(rss->h, val_arr[i]); + rss_irn_t *u = get_rss_irn(rss, val_arr[i]); plist_element_t *el; /* ignore nodes where serialization does not help */ - if (IS_UNSERIALIZABLE_NODE(u)) + if (IS_UNSERIALIZABLE_NODE(u)) { + DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", u->irn)); continue; + } /* accumulate all descendants of all pkiller(u) */ bitset_clear_all(bs_ukilldesc); @@ -1674,12 +1750,15 @@ static serialization_t *compute_best_admissible_serialization(rss_t *rss, nodese ir_node *v_irn = val_arr[j]; rss_irn_t *v = get_rss_irn(rss, v_irn); unsigned v_height = get_irn_height(rss->h, v_irn); - unsigned omega1, omega2, is_pkiller; + int omega1, omega2, is_pkiller; /* v cannot be serialized with itself * ignore nodes where serialization does not help */ - if (i == j || IS_UNSERIALIZABLE_NODE(v)) + if (i == j || IS_UNSERIALIZABLE_NODE(v)) { + if (i != j) + DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", v->irn)); continue; + } /* get descendants of v */ bitset_clear_all(bs_vdesc); @@ -1690,14 +1769,14 @@ static serialization_t *compute_best_admissible_serialization(rss_t *rss, nodese } /* if v is in pkiller(u) */ - is_pkiller = plist_has_value(u->pkiller_list, val_arr[j]); + is_pkiller = plist_has_value(u->pkiller_list, v_irn); /* for all vv in pkiller(u) */ foreach_plist(u->pkiller_list, el) { ir_node *vv_irn = plist_element_get_value(el); int add_edge; - if (is_Sink(vv_irn)) + if (is_Sink(vv_irn) || is_cfop(vv_irn)) continue; if (is_pkiller) @@ -1711,8 +1790,8 @@ static serialization_t *compute_best_admissible_serialization(rss_t *rss, nodese */ if (add_edge) { - unsigned vv_height = get_irn_height(rss->h, vv_irn); - unsigned mu1, mu2, critical_path_cost; + int vv_height = get_irn_height(rss->h, vv_irn); + int mu1, mu2, critical_path_cost; /* mu1 = | descendants(v) cut sat_vals | @@ -1733,13 +1812,11 @@ static serialization_t *compute_best_admissible_serialization(rss_t *rss, nodese mu2 = 0; } - //assert(mu1 >= mu2); - /* omega1 = mu1 - mu2 */ - omega1 = mu2 >= mu2 ? mu1 - mu2 : 0; + omega1 = mu1 - mu2; - if (omega1 > 0) - has_positive_omega1 = 1; + if (omega1 != 0) + has_omega1 = 1; /* omega2 = increase of critical path */ critical_path_cost = @@ -1754,25 +1831,27 @@ static serialization_t *compute_best_admissible_serialization(rss_t *rss, nodese omega2 = critical_path_cost > rss->max_height ? critical_path_cost - rss->max_height : 0; /* this keeps track of the edge with the best benefit */ - if (num_regs - omega1 < best_benefit) { + if (omega1 >= num_regs - n && omega1 < best_benefit) { min_benefit_edge.src = v_irn; min_benefit_edge.tgt = vv_irn; ser_u_omega1 = u; ser_v_omega1 = v; - best_benefit = num_regs - omega1; + best_benefit = omega1; + ser->new_killer = is_pkiller; } /* this keeps track of the edge with the best omega1 costs where omega2 == 0 */ - if (omega2 == 0 && (num_regs - omega1 < best_benefit_omega20)) { + if (omega2 == 0 && omega1 >= num_regs - n && omega1 < best_benefit_omega20) { min_omega20_edge.src = v_irn; min_omega20_edge.tgt = vv_irn; ser_u_omega20 = u; ser_v_omega20 = v; - best_benefit_omega20 = num_regs - omega1; + best_benefit_omega20 = omega1; + ser->new_killer = is_pkiller; } best_omega2 = MIN(best_omega2, omega2); @@ -1784,7 +1863,7 @@ static serialization_t *compute_best_admissible_serialization(rss_t *rss, nodese } /* for all v in sat_vals */ } /* for all u in sat_vals */ - if (! has_positive_omega1) + if (! has_omega1) return NULL; if (best_omega2 == 0) { @@ -1825,7 +1904,9 @@ static void perform_value_serialization_heuristic(rss_t *rss) { arch_put_non_ignore_regs(rss->arch_env, rss->cls, arch_nonign_bs); be_abi_put_ignore_regs(rss->abi, rss->cls, abi_ign_bs); bitset_andnot(arch_nonign_bs, abi_ign_bs); - available_regs = bitset_popcnt(arch_nonign_bs); + available_regs = bitset_popcnt(arch_nonign_bs); + //num_live = pset_count(rss->live_block); + //available_regs -= num_live < available_regs ? num_live : 0; DBG((rss->dbg, LEVEL_1, "\n\t#available regs: %d\n\n", available_regs)); @@ -1849,7 +1930,6 @@ static void perform_value_serialization_heuristic(rss_t *rss) { while (sat_vals && (nodeset_count(sat_vals) > available_regs)) { serialization_t *ser, best_ser; rss_edge_t *edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*edge)); - rss_irn_t *tgt, *src; ir_node *dep_src, *dep_tgt; best_ser.edge = edge; @@ -1887,17 +1967,6 @@ static void perform_value_serialization_heuristic(rss_t *rss) { /* TODO: try to find a cheaper way for updating height information */ rss->max_height = heights_recompute_block(rss->h, rss->block); -#if 0 - src = get_rss_irn(rss, ser->edge->src); - tgt = get_rss_irn(rss, ser->edge->tgt); - src->killer = tgt->irn; - del_nodeset(dvg.nodes); - del_pset(dvg.edges); - dvg.nodes = new_nodeset(plist_count(rss->nodes)); - dvg.edges = new_pset(cmp_rss_edges, plist_count(rss->nodes) * 5); - compute_dvg(rss, &dvg); -#endif /* if 0 */ - /* Recompute the antichain for next serialization */ DBG((rss->dbg, LEVEL_1, "\tre-computing maximal antichain:\n")); sat_vals = compute_maximal_antichain(rss, &dvg, iteration++); @@ -1938,23 +2007,51 @@ static void process_block(ir_node *block, void *env) { rss->cls = cls; DBG((rss->dbg, LEVEL_1, "register class %s\n", arch_register_class_name(cls))); + /* Get all live value at end of Block having current register class */ + rss->live_block = pset_new_ptr(10); + be_liveness_end_of_block(rss->liveness, rss->arch_env, rss->cls, rss->block, rss->live_block); + /* reset the list of interesting nodes */ plist_clear(rss->nodes); plist_insert_back(rss->nodes, _sink); /* collect all nodes having a certain register class */ foreach_out_edge(block, edge) { - ir_node *irn = get_edge_src_irn(edge); + ir_node *irn = get_edge_src_irn(edge); + ir_mode *mode = get_irn_mode(irn); - if (get_irn_mode(irn) == mode_T || be_is_Keep(irn) || be_is_Barrier(skip_Proj(irn))) + /* + We skip: + - mode_T nodes (the projs are asked) + - mode_X nodes (control flow nodes are always scheduled last) + - Keeps (they are always immediately scheduled) + - Phi (same as Keep) + */ + if (mode == mode_T || mode == mode_X || is_Phi(irn)) continue; - if (! arch_irn_is(rss->arch_env, irn, ignore) && arch_get_irn_reg_class(rss->arch_env, irn, -1) == cls) { - plist_insert_back(rss->nodes, irn); + /* + In case of a proj, we skip + - Barrier (they are a Barrier :) + - Start + - the Proj itself, as it's scheduled always with it's super node + */ + if (is_Proj(irn)) { + ir_node *pred = get_Proj_pred(irn); + if (be_is_Barrier(pred) || is_Start(pred)) + continue; + } + + /* calculate the descendants and consumer for each node in the block */ + collect_node_info(rss, skip_Proj(irn)); + + if (be_is_Keep(irn)) + continue; - /* calculate the descendants and consumer for each node in the block */ - collect_node_info(rss, irn); + if (! arch_irn_is(rss->arch_env, irn, ignore) && arch_get_irn_reg_class(rss->arch_env, irn, -1) == cls) { + plist_insert_back(rss->nodes, skip_Proj(irn)); } + //} } /* compute the potential killing set PK(G) */ @@ -1968,11 +2065,28 @@ static void process_block(ir_node *block, void *env) { add the necessary dependencies to the irg. */ perform_value_serialization_heuristic(rss); + + del_pset(rss->live_block); } phase_free(&rss->ph); } +#ifdef WITH_LIBCORE +/** + * Register the options. + */ +void be_init_schedrss(void) { + lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be"); + lc_opt_entry_t *sched_grp = lc_opt_get_grp(be_grp, "sched"); + lc_opt_entry_t *rss_grp = lc_opt_get_grp(sched_grp, "rss"); + + lc_opt_add_table(rss_grp, rss_option_table); +} + +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_schedrss); +#endif /* WITH_LIBCORE */ + /** * Preprocess the irg for scheduling. */ @@ -1981,7 +2095,7 @@ void rss_schedule_preparation(const be_irg_t *birg) { FIRM_DBG_REGISTER(rss.dbg, "firm.be.sched.rss"); - firm_dbg_set_mask(rss.dbg, LEVEL_1 | LEVEL_2 | LEVEL_3); + //firm_dbg_set_mask(rss.dbg, LEVEL_1 | LEVEL_2 | LEVEL_3); init_rss_special_nodes(birg->irg); @@ -1990,7 +2104,13 @@ void rss_schedule_preparation(const be_irg_t *birg) { rss.abi = birg->abi; rss.h = heights_new(birg->irg); rss.nodes = plist_new(); + rss.opts = &rss_options; + rss.liveness = be_liveness(birg->irg); irg_block_walk_graph(birg->irg, NULL, process_block, &rss); heights_free(rss.h); plist_free(rss.nodes); + be_liveness_free(rss.liveness); + + if (birg->main_env->options->dump_flags & DUMP_SCHED) + be_dump(rss.irg, "-rss", dump_ir_block_graph); }