X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeschedrss.c;h=45ac22a722929c2044ee7b2832feda70b0000dc4;hb=22b354ac921664032c93e5f0176fa668c95dfc60;hp=5ccf8d625b23e1428870c3d928f223e2ae2851f8;hpb=360e6fe36bae48ed6408bdd61d2a47cd8cf17cb4;p=libfirm diff --git a/ir/be/beschedrss.c b/ir/be/beschedrss.c index 5ccf8d625..45ac22a72 100644 --- a/ir/be/beschedrss.c +++ b/ir/be/beschedrss.c @@ -1,16 +1,34 @@ +/* + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. + */ + /** + * @file + * @brief Implementation of a register saturating list scheduler. + * @author Christian Wuerdig + * @date 29.08.2006 + * @version $Id$ + * * Implementation of a register saturating list scheduler * as described in: Sid-Ahmed-Ali Touati * Register Saturation in Superscalar and VLIW Codes - * - * @license This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - * @author Christian Wuerdig - * @date 29.08.2006 - * @cvs-id $Id$ */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif #include @@ -27,20 +45,23 @@ #include "irtools.h" #include "irbitset.h" #include "irprintf.h" +#include "irnodeset.h" #include "bipartite.h" #include "hungarian.h" #include "plist.h" +#include "array_t.h" #include "height.h" #include "beabi.h" #include "bemodule.h" -#include "benode_t.h" -#include "besched_t.h" -#include "beirg_t.h" +#include "benode.h" +#include "besched.h" +#include "beirg.h" +#include "belive.h" -#include -#include +#include "lc_opts.h" +#include "lc_opts_enum.h" #define ARR_LEN_SAFE(arr) ((arr) != NULL ? ARR_LEN((arr)) : 0) @@ -91,16 +112,16 @@ typedef struct _chain { typedef struct _rss_irn { plist_t *consumer_list; /**< List of consumers */ - ir_node **consumer; /**< Sorted consumer array (needed for faster access) */ + const ir_node **consumer; /**< Sorted consumer array (needed for faster access) */ plist_t *parent_list; /**< List of parents */ 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) */ + const ir_node **descendants; /**< Sorted descendant array (needed for faster access) */ - ir_node *killer; /**< The selected unique killer */ - ir_node *irn; /**< The corresponding firm node to this rss_irn */ + const ir_node *killer; /**< The selected unique killer */ + const ir_node *irn; /**< The corresponding firm node to this rss_irn */ chain_t *chain; /**< The chain, this node is associated to */ @@ -137,7 +158,7 @@ typedef struct _rss { 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 */ + ir_nodeset_t 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; @@ -198,7 +219,7 @@ static lc_opt_enum_int_var_t dump_var = { static const lc_opt_table_entry_t rss_option_table[] = { LC_OPT_ENT_ENUM_MASK("dump", "dump phases", &dump_var), - { NULL } + LC_OPT_LAST }; /****************************************************************************** @@ -276,11 +297,11 @@ static int bsearch_for_index(int key, int *arr, size_t len, int force) { return -1; } -static ir_node **build_sorted_array_from_list(plist_t *irn_list, struct obstack *obst) { +static const ir_node **build_sorted_array_from_list(plist_t *irn_list, struct obstack *obst) { plist_element_t *el; - int i = 0; - int len = plist_count(irn_list); - ir_node **arr = NEW_ARR_D(ir_node *, obst, len); + int i = 0; + int len = plist_count(irn_list); + const ir_node **arr = (const ir_node**)NEW_ARR_D(ir_node*, obst, len); /* copy the list into the array */ foreach_plist(irn_list, el) { @@ -288,7 +309,8 @@ static ir_node **build_sorted_array_from_list(plist_t *irn_list, struct obstack } /* sort the array by node index */ - qsort(arr, len, sizeof(arr[0]), cmp_irn_idx); + /* HACK cast for MSVC */ + qsort((void*)arr, len, sizeof(arr[0]), cmp_irn_idx); return arr; } @@ -413,19 +435,20 @@ static void debug_vcg_dump_kill(rss_t *rss) { } /* Dumps the potential killing DAG (PKG) as vcg. */ -static void debug_vcg_dump_pkg(rss_t *rss, ir_nodeset_t *max_ac, int iteration) { +static void debug_vcg_dump_pkg(rss_t *rss, ir_nodeset_t *max_ac, int iteration) +{ FILE *f; char file_name[256]; - char *suffix = alloca(32); + char suffix[32]; static const char suffix1[] = "-RSS-PKG.vcg"; static const char suffix2[] = "-RSS-PKG-MAXAC.vcg"; plist_element_t *el; if (! max_ac) { - snprintf(suffix, 32, "%s", suffix1); + snprintf(suffix, sizeof(suffix), "%s", suffix1); } else { - snprintf(suffix, 32, "-%02d%s", iteration, suffix2); + snprintf(suffix, sizeof(suffix), "-%02d%s", iteration, suffix2); } build_file_name(rss, suffix, strlen(suffix) + 1, file_name, sizeof(file_name)); @@ -559,7 +582,7 @@ static void debug_vcg_dump_dvg_pkiller(rss_t *rss, dvg_t *dvg) { /** * In case there is no rss information for irn, initialize it. */ -static void *init_rss_irn(ir_phase *ph, ir_node *irn, void *old) { +static void *init_rss_irn(ir_phase *ph, const 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)); @@ -611,7 +634,7 @@ static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int * ir_node *user = get_edge_src_irn(edge); /* skip ignore nodes as they do not really contribute to register pressure */ - if (arch_irn_is(rss->arch_env, user, ignore)) + if (arch_irn_is_ignore(user)) continue; /* @@ -626,8 +649,7 @@ static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int * } if (is_Proj(user)) { - - //if (arch_get_irn_reg_class(rss->arch_env, user, -1) == rss->cls) + //if (arch_get_irn_reg_class_out(user) == rss->cls) collect_descendants(rss, rirn, user, got_sink, cur_desc_walk); } else { @@ -660,7 +682,8 @@ static void collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *con assert(! is_Proj(consumer) && "Cannot handle Projs"); 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)) { + if (!arch_irn_is_ignore(consumer) && + !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)); } @@ -695,7 +718,7 @@ static void collect_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *irn, int * ir_node *consumer = get_edge_src_irn(edge); if (is_Proj(consumer)) { - //if (arch_get_irn_reg_class(rss->arch_env, consumer, -1) == rss->cls) + //if (arch_get_irn_reg_class_out(consumer) == rss->cls) collect_consumer(rss, rss_irn, consumer, got_sink); } else @@ -751,8 +774,9 @@ static void collect_node_info(rss_t *rss, ir_node *irn) { */ static int is_potential_killer(rss_t *rss, rss_irn_t *v, rss_irn_t *u) { plist_t *list; - ir_node **arr; + const ir_node **arr; plist_element_t *el; + (void) rss; assert(is_Sink(v->irn) || ((plist_count(v->descendant_list) > 0 && v->descendants) || 1)); assert(is_Sink(u->irn) || ((plist_count(u->consumer_list) > 0 && u->consumer) || 1)); @@ -857,7 +881,7 @@ static void build_kill_edges(rss_t *rss, pset *epk) { foreach_plist(rirn->pkiller_list, k_el) { ir_node *pkiller = plist_element_get_value(k_el); - rss_edge_t *ke = obstack_alloc(phase_obst(&rss->ph), sizeof(*ke)); + rss_edge_t *ke = OALLOC(phase_obst(&rss->ph), rss_edge_t); ke->src = irn; ke->tgt = pkiller; @@ -926,7 +950,7 @@ static void compute_bipartite_decomposition(rss_t *rss) { DBG((rss->dbg, LEVEL_2, "\t\t%+F choosen:\n", u_irn)); - cbc = obstack_alloc(phase_obst(&rss->ph), sizeof(*cbc)); + cbc = OALLOC(phase_obst(&rss->ph), cbc_t); cbc->nr = cur_num++; /* initialize S_cb */ @@ -1160,8 +1184,7 @@ static void compute_killing_function(rss_t *rss) { /* while X not empty */ while (ir_nodeset_size(&x) > 0) { - child_t *t = obstack_alloc(&obst, sizeof(*t)); - memset(t, 0, sizeof(*t)); + child_t *t = OALLOCZ(&obst, child_t); t = select_child_max_cost(rss, &x, &y, t, cbc); @@ -1222,29 +1245,29 @@ 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) { +static inline void add_dvg_edge(rss_t *rss, dvg_t *dvg, const ir_node *src, const ir_node *tgt, int have_source) { rss_edge_t *dvg_edge; rss_edge_t key; if (! have_source) - ir_nodeset_insert(&dvg->nodes, src); + ir_nodeset_insert(&dvg->nodes, (ir_node *) src); else assert(ir_nodeset_contains(&dvg->nodes, src) && "Wrong assumption"); - ir_nodeset_insert(&dvg->nodes, tgt); + ir_nodeset_insert(&dvg->nodes, (ir_node *) tgt); - key.src = tgt; - key.tgt = src; + key.src = (ir_node *) tgt; + key.tgt = (ir_node *) src; assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!"); - key.src = src; - key.tgt = tgt; + key.src = (ir_node *) src; + key.tgt = (ir_node *) 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 = OALLOC(phase_obst(&rss->ph), rss_edge_t); - dvg_edge->src = src; - dvg_edge->tgt = tgt; + dvg_edge->src = (ir_node *) src; + dvg_edge->tgt = (ir_node *) tgt; dvg_edge->next = NULL; DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", src, tgt)); @@ -1290,7 +1313,7 @@ static void compute_dvg(rss_t *rss, dvg_t *dvg) { There is an edge (u, v) in the DVG iff v is a descendant of the killer(u). */ if (BSEARCH_IRN_ARR(v_irn, u_kill->descendants)) { - rss_edge_t *dvg_edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*dvg_edge)); + rss_edge_t *dvg_edge = OALLOC(phase_obst(&rss->ph), rss_edge_t); rss_edge_t key; /* insert the user into the DVG and append it to the user list of u */ @@ -1325,7 +1348,7 @@ static void compute_dvg(rss_t *rss, dvg_t *dvg) { static void update_dvg(rss_t *rss, dvg_t *dvg, rss_irn_t *src, rss_irn_t *tgt) { int i, j, idx; rss_edge_t *edge; - rss_edge_t **arr = alloca(pset_count(dvg->edges) * sizeof(arr[0])); + rss_edge_t **arr = ALLOCAN(rss_edge_t*, pset_count(dvg->edges)); /* Add an edge from serialization target to serialization src: @@ -1432,9 +1455,9 @@ static void build_dvg_pkiller_list(rss_t *rss, dvg_t *dvg) { */ static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration) { int n = ir_nodeset_size(&dvg->nodes); - int *assignment = alloca(n * sizeof(assignment[0])); - int *assignment_rev = alloca(n * sizeof(assignment_rev[0])); - int *idx_map = alloca(n * sizeof(idx_map[0])); + int *assignment = ALLOCAN(int, n); + int *assignment_rev = ALLOCAN(int, n); + int *idx_map = ALLOCAN(int, n); hungarian_problem_t *bp; ir_nodeset_t *values, *temp; ir_nodeset_iterator_t iter; @@ -1447,7 +1470,7 @@ static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int itera if (pset_count(dvg->edges) == 0) return NULL; - bp = hungarian_new(n, n, 1, HUNGARIAN_MATCH_NORMAL); + bp = hungarian_new(n, n, HUNGARIAN_MATCH_NORMAL); /* At first, we build an index map for the nodes in the DVG, @@ -1545,7 +1568,7 @@ static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int itera DBG((rss->dbg, LEVEL_3, "\t\t\t%3d -> %3d %3d -> %3d\n", i, assignment[i], i, assignment_rev[i])); } - values = xmalloc(sizeof(values[0])); + values = XMALLOC(ir_nodeset_t); ir_nodeset_init_size(values, 10); cur_chain = 0; /* Construction of the minimal chain partition */ @@ -1555,7 +1578,7 @@ static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int itera int xj = idx_map[j]; ir_node *xj_irn = get_idx_irn(rss->irg, xj); rss_irn_t *xj_rss = get_rss_irn(rss, xj_irn); - chain_t *c = obstack_alloc(phase_obst(&rss->ph), sizeof(*c)); + chain_t *c = OALLOC(phase_obst(&rss->ph), chain_t); int source; /* there was no source for j -> we have a source of a new chain */ @@ -1623,7 +1646,7 @@ static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int itera free(temp); } - temp = xmalloc(sizeof(temp[0])); + temp = XMALLOC(ir_nodeset_t); ir_nodeset_init_size(temp, 10); /* Select all nodes from current value set, having another node in the set as descendant. */ @@ -1639,7 +1662,7 @@ static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int itera if (pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) { /* v[j] is descendant of u -> remove u and break */ - ir_nodeset_insert(temp, u->irn); + ir_nodeset_insert(temp, (ir_node *) u->irn); ir_nodeset_remove(values, u->irn); DBG((rss->dbg, LEVEL_3, "\t\t\tremoving %+F from values, adding it to temp\n", u->irn)); @@ -1696,7 +1719,7 @@ static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nod int n = ir_nodeset_size(sat_vals); int n_idx = ARR_LEN_SAFE(rss->idx_map); int i = 0; - ir_node **val_arr = alloca(n * sizeof(val_arr[0])); + ir_node **val_arr = ALLOCAN(ir_node*, n); bitset_t *bs_sv = bitset_alloca(n_idx); bitset_t *bs_vdesc = bitset_alloca(n_idx); bitset_t *bs_tmp = bitset_alloca(n_idx); @@ -1708,8 +1731,8 @@ static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nod int j, k; ir_node *irn; ir_nodeset_iterator_t iter; - rss_edge_t min_benefit_edge; - rss_edge_t min_omega20_edge; + rss_edge_t min_benefit_edge = {NULL, NULL, NULL}; + rss_edge_t min_omega20_edge = {NULL, NULL, NULL}; rss_irn_t *ser_u_omega1 = NULL, *ser_v_omega1 = NULL; rss_irn_t *ser_u_omega20 = NULL, *ser_v_omega20 = NULL; @@ -1790,8 +1813,10 @@ static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nod /* v cannot be serialized with itself * ignore nodes where serialization does not help */ if (i == j || IS_UNSERIALIZABLE_NODE(v)) { +#ifdef DEBUG_libfirm if (i != j) DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", v->irn)); +#endif continue; } @@ -1937,7 +1962,7 @@ static void perform_value_serialization_heuristic(rss_t *rss) { pset *ser_set = new_pset(cmp_rss_edges, 20); /* available_regs = R = |arch_non_ignore_regs cut ~abi_ignore_regs| */ - arch_put_non_ignore_regs(rss->arch_env, rss->cls, arch_nonign_bs); + arch_put_non_ignore_regs(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); @@ -1965,7 +1990,7 @@ static void perform_value_serialization_heuristic(rss_t *rss) { sat_vals = compute_maximal_antichain(rss, &dvg, iteration++); while (sat_vals && (ir_nodeset_size(sat_vals) > available_regs)) { serialization_t *ser, best_ser; - rss_edge_t *edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*edge)); + rss_edge_t *edge = OALLOC(phase_obst(&rss->ph), rss_edge_t); ir_node *dep_src, *dep_tgt; best_ser.edge = edge; @@ -2040,15 +2065,15 @@ static void process_block(ir_node *block, void *env) { rss->max_height = heights_recompute_block(rss->h, block); /* loop over all register classes */ - for (i = arch_isa_get_n_reg_class(rss->arch_env->isa) - 1; i >= 0; --i) { - const arch_register_class_t *cls = arch_isa_get_reg_class(rss->arch_env->isa, i); + for (i = arch_env_get_n_reg_class(rss->arch_env) - 1; i >= 0; --i) { + const arch_register_class_t *cls = arch_env_get_reg_class(rss->arch_env, i); 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); + ir_nodeset_init(&rss->live_block); + be_liveness_end_of_block(rss->liveness, rss->cls, rss->block, &rss->live_block); /* reset the list of interesting nodes */ plist_clear(rss->nodes); @@ -2077,7 +2102,7 @@ static void process_block(ir_node *block, void *env) { */ if (is_Proj(irn)) { ir_node *pred = get_Proj_pred(irn); - if (be_is_Barrier(pred) || is_Start(pred)) + if (be_is_Barrier(pred) || be_is_Start(pred)) continue; } @@ -2087,7 +2112,8 @@ static void process_block(ir_node *block, void *env) { if (be_is_Keep(irn)) continue; - if (! arch_irn_is(rss->arch_env, irn, ignore) && arch_get_irn_reg_class(rss->arch_env, irn, -1) == cls) { + if (!arch_irn_is_ignore(irn) && + arch_get_irn_reg_class_out(irn) == cls) { plist_insert_back(rss->nodes, skip_Proj(irn)); } //} @@ -2105,7 +2131,7 @@ static void process_block(ir_node *block, void *env) { */ perform_value_serialization_heuristic(rss); - del_pset(rss->live_block); + ir_nodeset_destroy(&rss->live_block); } phase_free(&rss->ph); @@ -2127,7 +2153,7 @@ BE_REGISTER_MODULE_CONSTRUCTOR(be_init_schedrss); /** * Preprocess the irg for scheduling. */ -void rss_schedule_preparation(const be_irg_t *birg) { +void rss_schedule_preparation(be_irg_t *birg) { ir_graph *irg = be_get_birg_irg(birg); rss_t rss; @@ -2144,6 +2170,7 @@ void rss_schedule_preparation(const be_irg_t *birg) { rss.nodes = plist_new(); rss.opts = &rss_options; rss.liveness = be_liveness(irg); + be_liveness_assure_sets(rss.liveness); irg_block_walk_graph(irg, NULL, process_block, &rss); heights_free(rss.h); plist_free(rss.nodes);