X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeschedrss.c;h=e05ebb347a0df9d8e70410f534c1b785db524128;hb=0378ccc621a98322785250f96d85d3b32dc0cad1;hp=8521d6aafae849a8edb48157fd5ffda6d18fd8ef;hpb=e718abad5816e8066985b93df7d6721079901317;p=libfirm diff --git a/ir/be/beschedrss.c b/ir/be/beschedrss.c index 8521d6aaf..e05ebb347 100644 --- a/ir/be/beschedrss.c +++ b/ir/be/beschedrss.c @@ -45,6 +45,7 @@ #include "irtools.h" #include "irbitset.h" #include "irprintf.h" +#include "irnodeset.h" #include "bipartite.h" #include "hungarian.h" #include "plist.h" @@ -54,9 +55,10 @@ #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 "lc_opts.h" #include "lc_opts_enum.h" @@ -234,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) { @@ -247,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; @@ -295,7 +303,8 @@ static int bsearch_for_index(int key, int *arr, size_t len, int force) { return -1; } -static const 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); @@ -326,18 +335,20 @@ static const ir_node **build_sorted_array_from_list(plist_t *irn_list, struct ob *****************************************************/ #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); @@ -348,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]; @@ -385,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; @@ -508,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]; @@ -541,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]; @@ -580,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(ir_phase *ph, const 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 +627,8 @@ static void *init_rss_irn(ir_phase *ph, const 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; @@ -674,7 +691,8 @@ 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"); @@ -701,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 }; @@ -728,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; @@ -770,7 +790,8 @@ 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; const ir_node **arr; plist_element_t *el; @@ -804,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); @@ -835,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) { @@ -868,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) { @@ -879,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; @@ -894,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; @@ -919,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; @@ -948,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 */ @@ -1076,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; @@ -1118,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; @@ -1133,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; @@ -1148,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; @@ -1182,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); @@ -1244,7 +1273,8 @@ 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, const ir_node *src, const 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; @@ -1263,7 +1293,7 @@ static inline void add_dvg_edge(rss_t *rss, dvg_t *dvg, const ir_node *src, cons 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 = (ir_node *) src; dvg_edge->tgt = (ir_node *) tgt; @@ -1279,7 +1309,8 @@ static inline void add_dvg_edge(rss_t *rss, dvg_t *dvg, const ir_node *src, cons * 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")); @@ -1312,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 */ @@ -1344,7 +1375,8 @@ 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 = ALLOCAN(rss_edge_t*, pset_count(dvg->edges)); @@ -1382,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; @@ -1407,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; @@ -1452,7 +1486,8 @@ 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 = ALLOCAN(int, n); int *assignment_rev = ALLOCAN(int, n); @@ -1577,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 */ @@ -1701,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); } @@ -1714,7 +1749,8 @@ 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; @@ -1952,7 +1988,8 @@ 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)); unsigned available_regs, iteration; @@ -1989,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; @@ -2015,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); } @@ -2042,7 +2079,8 @@ 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; @@ -2101,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; } @@ -2139,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"); @@ -2152,7 +2191,8 @@ BE_REGISTER_MODULE_CONSTRUCTOR(be_init_schedrss); /** * Preprocess the irg for scheduling. */ -void rss_schedule_preparation(be_irg_t *birg) { +void rss_schedule_preparation(be_irg_t *birg) +{ ir_graph *irg = be_get_birg_irg(birg); rss_t rss;