X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeschedrss.c;h=e05ebb347a0df9d8e70410f534c1b785db524128;hb=0378ccc621a98322785250f96d85d3b32dc0cad1;hp=adb258fb4dd086f9edc676c3c47a3d7248b69b02;hpb=311439dee8e33414f35d7b262c5c49c52f4108d6;p=libfirm diff --git a/ir/be/beschedrss.c b/ir/be/beschedrss.c index adb258fb4..e05ebb347 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 -#endif +#include "config.h" #include @@ -27,19 +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 "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) @@ -90,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 */ @@ -124,7 +146,7 @@ typedef struct _serialization { } serialization_t; typedef struct _rss { - phase_t ph; /**< Phase to hold some data */ + ir_phase ph; /**< Phase to hold some data */ heights_t *h; /**< The current height object */ ir_graph *irg; /**< The irg to preprocess */ plist_t *nodes; /**< The list of interesting nodes */ @@ -136,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; @@ -197,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 }; /****************************************************************************** @@ -214,7 +236,8 @@ static const lc_opt_table_entry_t rss_option_table[] = { /** * Acquire opcodes if needed and create source and sink nodes. */ -static void init_rss_special_nodes(ir_graph *irg) { +static void init_rss_special_nodes(ir_graph *irg) +{ ir_node *block; if (op_rss_Source == NULL) { @@ -227,35 +250,40 @@ static void init_rss_special_nodes(ir_graph *irg) { _sink = new_ir_node(NULL, irg, block, op_rss_Sink, mode_ANY, 0, NULL); } -static int cmp_int(const void *a, const void *b) { +static int cmp_int(const void *a, const void *b) +{ const int *i1 = a; const int *i2 = b; return QSORT_CMP(*i1, *i2); } -static int cmp_child_costs(const void *a, const void *b) { +static int cmp_child_costs(const void *a, const void *b) +{ const child_t *c1 = a; const child_t *c2 = b; return QSORT_CMP(c1->cost, c2->cost); } -static int cmp_irn_idx(const void *a, const void *b) { +static int cmp_irn_idx(const void *a, const void *b) +{ const ir_node *n1 = *(ir_node **)a; const ir_node *n2 = *(ir_node **)b; return QSORT_CMP(get_irn_idx(n1), get_irn_idx(n2)); } -static int cmp_rss_edges(const void *a, const void *b) { +static int cmp_rss_edges(const void *a, const void *b) +{ const rss_edge_t *e1 = a; const rss_edge_t *e2 = b; return (e1->src != e2->src) || (e1->tgt != e2->tgt); } -static int bsearch_for_index(int key, int *arr, size_t len, int force) { +static int bsearch_for_index(int key, int *arr, size_t len, int force) +{ int left = 0; int right = len; @@ -275,11 +303,12 @@ 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) { @@ -287,7 +316,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; } @@ -305,18 +335,20 @@ static ir_node **build_sorted_array_from_list(plist_t *irn_list, struct obstack *****************************************************/ #ifdef DEBUG_libfirm -static void dump_nodeset(ir_nodeset_t *ns, const char *prefix) { +static void dump_nodeset(ir_nodeset_t *ns, const char *prefix) +{ ir_nodeset_iterator_t iter; ir_node *irn; ir_nodeset_iterator_init(&iter, ns); - while( (irn = ir_nodeset_iterator_next(&iter)) != NULL ) { + while ( (irn = ir_nodeset_iterator_next(&iter)) != NULL ) { 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) { +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); @@ -327,7 +359,8 @@ static void build_file_name(rss_t *rss, const char *suffix, size_t suf_len, char } /* Dumps all collected bipartite components of current irg as vcg. */ -static void debug_vcg_dump_bipartite(rss_t *rss) { +static void debug_vcg_dump_bipartite(rss_t *rss) +{ cbc_t *cbc; FILE *f; char file_name[256]; @@ -364,7 +397,8 @@ static void debug_vcg_dump_bipartite(rss_t *rss) { } /* Dump the computed killing function as vcg. */ -static void debug_vcg_dump_kill(rss_t *rss) { +static void debug_vcg_dump_kill(rss_t *rss) +{ FILE *f; char file_name[256]; plist_element_t *el; @@ -412,19 +446,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)); @@ -486,7 +521,8 @@ static void debug_vcg_dump_pkg(rss_t *rss, ir_nodeset_t *max_ac, int iteration) } /* Dumps the disjoint value DAG (DVG) as vcg. */ -static void debug_vcg_dump_dvg(rss_t *rss, dvg_t *dvg) { +static void debug_vcg_dump_dvg(rss_t *rss, dvg_t *dvg) +{ static const char suffix[] = "-RSS-DVG.vcg"; FILE *f; char file_name[256]; @@ -519,7 +555,8 @@ static void debug_vcg_dump_dvg(rss_t *rss, dvg_t *dvg) { #if 0 /* Dumps the PKG(DVG). */ -static void debug_vcg_dump_dvg_pkiller(rss_t *rss, dvg_t *dvg) { +static void debug_vcg_dump_dvg_pkiller(rss_t *rss, dvg_t *dvg) +{ static const char suffix[] = "-RSS-DVG-PKG.vcg"; FILE *f; char file_name[256]; @@ -558,7 +595,8 @@ 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(phase_t *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)); @@ -589,7 +627,8 @@ 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, unsigned cur_desc_walk) { +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; rss_irn_t *cur_node = get_rss_irn(rss, irn); ir_node *block = rss->block; @@ -610,7 +649,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; /* @@ -625,8 +664,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 { @@ -653,13 +691,15 @@ force_sink: /** * Handles a single consumer. */ -static void collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *consumer, int *got_sink) { +static void collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *consumer, int *got_sink) +{ ir_node *block = rss->block; 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)); } @@ -679,7 +719,8 @@ static void collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *con /** * 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, int *got_sink) { +static void collect_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *irn, int *got_sink) +{ const ir_edge_t *edge; int i; ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP }; @@ -694,7 +735,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 @@ -706,7 +747,8 @@ static void collect_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *irn, int * /** * Collects all consumer and descendant of a irn. */ -static void collect_node_info(rss_t *rss, ir_node *irn) { +static void collect_node_info(rss_t *rss, ir_node *irn) +{ static unsigned cur_desc_walk = 0; rss_irn_t *rss_irn = get_rss_irn(rss, irn); int got_sink; @@ -748,10 +790,12 @@ static void collect_node_info(rss_t *rss, ir_node *irn) { * @param u The potentially killed value * @return 1 if v is in pkill(u), 0 otherwise */ -static int is_potential_killer(rss_t *rss, rss_irn_t *v, rss_irn_t *u) { +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)); @@ -781,7 +825,8 @@ static int is_potential_killer(rss_t *rss, rss_irn_t *v, rss_irn_t *u) { /** * Update descendants, consumer and pkiller list for the given irn. */ -static void update_node_info(rss_t *rss, ir_node *irn, ir_node *pk_irn) { +static void update_node_info(rss_t *rss, ir_node *irn, ir_node *pk_irn) +{ rss_irn_t *node = get_rss_irn(rss, irn); rss_irn_t *pkiller = get_rss_irn(rss, pk_irn); @@ -812,7 +857,8 @@ static void update_node_info(rss_t *rss, ir_node *irn, ir_node *pk_irn) { /** * Compute the potential killing set PK. */ -static void compute_pkill_set(rss_t *rss) { +static void compute_pkill_set(rss_t *rss) +{ plist_element_t *u_el, *v_el; foreach_plist(rss->nodes, u_el) { @@ -845,7 +891,8 @@ static void compute_pkill_set(rss_t *rss) { /** * Build set of killing edges (from values to their potential killers) */ -static void build_kill_edges(rss_t *rss, pset *epk) { +static void build_kill_edges(rss_t *rss, pset *epk) +{ plist_element_t *el, *k_el; foreach_plist(rss->nodes, el) { @@ -856,7 +903,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; @@ -871,7 +918,8 @@ 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) { +static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc) +{ ir_nodeset_iterator_t iter; ir_node *n; rss_edge_t *ke; @@ -896,7 +944,8 @@ static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc) { * Sid-Ahmed-Ali Touati, Phd Thesis * Register Pressure in Instruction Level Parallelism, p. 71 */ -static void compute_bipartite_decomposition(rss_t *rss) { +static void compute_bipartite_decomposition(rss_t *rss) +{ pset *epk = new_pset(cmp_rss_edges, 10); int cur_num = 0; @@ -925,7 +974,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 */ @@ -1053,7 +1102,8 @@ static void compute_bipartite_decomposition(rss_t *rss) { /** * Select the child with the maximum cost. */ -static child_t *select_child_max_cost(rss_t *rss, ir_nodeset_t *x, ir_nodeset_t *y, child_t *t, cbc_t *cbc) { +static child_t *select_child_max_cost(rss_t *rss, ir_nodeset_t *x, ir_nodeset_t *y, child_t *t, cbc_t *cbc) +{ ir_node *child; ir_nodeset_iterator_t iter; float max_cost = -1.0f; @@ -1095,7 +1145,8 @@ static child_t *select_child_max_cost(rss_t *rss, ir_nodeset_t *x, ir_nodeset_t /** * Remove all parents from x which are killed by t_irn. */ -static void remove_covered_parents(rss_t *rss, ir_nodeset_t *x, ir_node *t_irn, cbc_t *cbc) { +static void remove_covered_parents(rss_t *rss, ir_nodeset_t *x, ir_node *t_irn, cbc_t *cbc) +{ rss_irn_t *t = get_rss_irn(rss, t_irn); rss_edge_t *k_edge; @@ -1110,7 +1161,8 @@ static void remove_covered_parents(rss_t *rss, ir_nodeset_t *x, ir_node *t_irn, } } -static void update_cumulated_descendent_values(rss_t *rss, ir_nodeset_t *y, ir_node *t_irn) { +static void update_cumulated_descendent_values(rss_t *rss, ir_nodeset_t *y, ir_node *t_irn) +{ rss_irn_t *t = get_rss_irn(rss, t_irn); plist_element_t *el; @@ -1125,7 +1177,8 @@ static void update_cumulated_descendent_values(rss_t *rss, ir_nodeset_t *y, ir_n /** * Greedy-k: a heuristics for the MMA problem */ -static void compute_killing_function(rss_t *rss) { +static void compute_killing_function(rss_t *rss) +{ cbc_t *cbc; struct obstack obst; @@ -1159,8 +1212,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); @@ -1221,29 +1273,30 @@ 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)); @@ -1256,7 +1309,8 @@ static INLINE void add_dvg_edge(rss_t *rss, dvg_t *dvg, ir_node *src, ir_node *t * BEWARE: It is not made explicitly clear in the Touati paper, * but the DVG is meant to be build from the KILLING DAG */ -static void compute_dvg(rss_t *rss, dvg_t *dvg) { +static void compute_dvg(rss_t *rss, dvg_t *dvg) +{ plist_element_t *el; DBG((rss->dbg, LEVEL_1, "\tcomputing DVG:\n")); @@ -1289,7 +1343,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 */ @@ -1321,10 +1375,11 @@ static void compute_dvg(rss_t *rss, dvg_t *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) { +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: @@ -1359,7 +1414,8 @@ static void update_dvg(rss_t *rss, dvg_t *dvg, rss_irn_t *src, rss_irn_t *tgt) { /** * Accumulate all descendants for root into list. */ -static void accumulate_dvg_descendant_values(rss_t *rss, rss_irn_t *root, plist_t *list) { +static void accumulate_dvg_descendant_values(rss_t *rss, rss_irn_t *root, plist_t *list) +{ if (plist_count(root->dvg_user_list) > 0) { plist_element_t *el; @@ -1384,7 +1440,8 @@ static void accumulate_dvg_descendant_values(rss_t *rss, rss_irn_t *root, plist_ * in the given DVG. * Needs the descendant list for all user as sorted array. */ -static void build_dvg_pkiller_list(rss_t *rss, dvg_t *dvg) { +static void build_dvg_pkiller_list(rss_t *rss, dvg_t *dvg) +{ ir_nodeset_iterator_t iter; ir_node *irn; @@ -1429,11 +1486,12 @@ static void build_dvg_pkiller_list(rss_t *rss, dvg_t *dvg) { * This is a reimplementation of the MAXIMAL_ANTI_CHAIN function * from the DDG library 1.1 (DAG.cpp). */ -static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration) { +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; @@ -1446,7 +1504,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, @@ -1544,7 +1602,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 */ @@ -1554,7 +1612,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 */ @@ -1622,7 +1680,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. */ @@ -1638,7 +1696,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)); @@ -1678,7 +1736,7 @@ static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int itera if (rss->opts->dump_flags & RSS_DUMP_MAXAC) debug_vcg_dump_pkg(rss, values, iteration); - if(temp != NULL) { + if (temp != NULL) { ir_nodeset_destroy(temp); free(temp); } @@ -1691,11 +1749,12 @@ static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int itera /** * Computes the best serialization between two nodes of sat_vals. */ -static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nodeset_t *sat_vals, serialization_t *ser, int num_regs) { +static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nodeset_t *sat_vals, serialization_t *ser, int num_regs) +{ 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); @@ -1707,8 +1766,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; @@ -1789,8 +1848,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; } @@ -1824,8 +1885,9 @@ static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nod */ if (add_edge) { - int vv_height = get_irn_height(rss->h, vv_irn); - int mu1, mu2, critical_path_cost; + unsigned vv_height = get_irn_height(rss->h, vv_irn); + unsigned critical_path_cost; + unsigned mu1, mu2; /* mu1 = | descendants(v) cut sat_vals | @@ -1926,16 +1988,17 @@ static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nod * Perform the value serialization heuristic and add all * computed serialization edges as dependencies to the irg. */ -static void perform_value_serialization_heuristic(rss_t *rss) { +static void perform_value_serialization_heuristic(rss_t *rss) +{ bitset_t *arch_nonign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls)); bitset_t *abi_ign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls)); - int available_regs, iteration; + unsigned available_regs, iteration; dvg_t dvg; ir_nodeset_t *sat_vals; 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); @@ -1963,7 +2026,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; @@ -1989,7 +2052,7 @@ static void perform_value_serialization_heuristic(rss_t *rss) { /* update the dvg */ update_dvg(rss, &dvg, ser->v, ser->u); update_dvg(rss, &dvg, get_rss_irn(rss, ser->edge->src), get_rss_irn(rss, ser->edge->tgt)); - if(sat_vals != NULL) { + if (sat_vals != NULL) { ir_nodeset_destroy(sat_vals); free(sat_vals); } @@ -2016,12 +2079,13 @@ static void perform_value_serialization_heuristic(rss_t *rss) { /** * Do initial calculations for a block. */ -static void process_block(ir_node *block, void *env) { +static void process_block(ir_node *block, void *env) +{ rss_t *rss = env; int i, n; const ir_edge_t *edge; - phase_init(&rss->ph, "rss block preprocessor", rss->irg, PHASE_DEFAULT_GROWTH, init_rss_irn); + phase_init(&rss->ph, "rss block preprocessor", rss->irg, PHASE_DEFAULT_GROWTH, init_rss_irn, NULL); DBG((rss->dbg, LEVEL_1, "preprocessing block %+F\n", block)); rss->block = block; @@ -2038,15 +2102,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); @@ -2075,7 +2139,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; } @@ -2085,7 +2149,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)); } //} @@ -2103,7 +2168,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); @@ -2112,7 +2177,8 @@ static void process_block(ir_node *block, void *env) { /** * Register the options. */ -void be_init_schedrss(void) { +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"); @@ -2125,23 +2191,26 @@ 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; FIRM_DBG_REGISTER(rss.dbg, "firm.be.sched.rss"); //firm_dbg_set_mask(rss.dbg, LEVEL_1 | LEVEL_2 | LEVEL_3); - init_rss_special_nodes(birg->irg); + init_rss_special_nodes(irg); - rss.irg = birg->irg; - rss.arch_env = birg->main_env->arch_env; + rss.irg = irg; + rss.arch_env = be_get_birg_arch_env(birg); rss.abi = birg->abi; - rss.h = heights_new(birg->irg); + rss.h = heights_new(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); + 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); be_liveness_free(rss.liveness);