X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeschedregpress.c;h=e7d8eb6a6583e4fbed439ef5a34b89e6a812bc22;hb=59e2d36967edfaaa770afdf3d498bed3b39e55ee;hp=e34afa838b52e59760b7885e43361890500bcede;hpb=e66230064eece9d3e28b66ae3a26bf8554459c60;p=libfirm diff --git a/ir/be/beschedregpress.c b/ir/be/beschedregpress.c index e34afa838..e7d8eb6a6 100644 --- a/ir/be/beschedregpress.c +++ b/ir/be/beschedregpress.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -22,79 +22,44 @@ * @brief Register pressure node selector. * @author Sebastian Hack * @date 29.08.2006 - * @version $Id$ */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif #include #include "iredges_t.h" #include "irgwalk.h" #include "irtools.h" +#include "util.h" -#include "besched_t.h" +#include "besched.h" #include "belistsched.h" -#include "benode_t.h" +#include "benode.h" +#include "bemodule.h" -typedef struct _usage_stats_t { +typedef struct usage_stats_t { ir_node *irn; - struct _usage_stats_t *next; + struct usage_stats_t *next; int max_hops; int uses_in_block; /**< Number of uses inside the current block. */ int already_consumed; /**< Number of insns using this value already scheduled. */ } usage_stats_t; -typedef struct { - const list_sched_selector_t *vtab; - const arch_env_t *arch_env; -} reg_pressure_main_env_t; - typedef struct { struct obstack obst; - const reg_pressure_main_env_t *main_env; usage_stats_t *root; ir_nodeset_t already_scheduled; } reg_pressure_selector_env_t; -#if 0 -/* -* Ugly global variable for the compare function -* since qsort(3) does not pass an extra pointer. -*/ -static ir_node *curr_bl = NULL; - -static int cmp_usage(const void *a, const void *b) +static inline usage_stats_t *get_or_set_usage_stats(reg_pressure_selector_env_t *env, ir_node *irn) { - struct trivial_sched_env *env; - const ir_node *p = a; - const ir_node *q = b; - int res = 0; + usage_stats_t *us = (usage_stats_t*)get_irn_link(irn); - res = is_live_end(env->curr_bl, a) - is_live_end(env->curr_bl, b); - - /* - * One of them is live at the end of the block. - * Then, that one shall be scheduled at after the other - */ - if(res != 0) - return res; - - - return res; -} -#endif - -static INLINE usage_stats_t *get_or_set_usage_stats(reg_pressure_selector_env_t *env, ir_node *irn) -{ - usage_stats_t *us = get_irn_link(irn); - - if(!us) { - us = obstack_alloc(&env->obst, sizeof(us[0])); + if (!us) { + us = OALLOC(&env->obst, usage_stats_t); us->irn = irn; us->already_consumed = 0; us->max_hops = INT_MAX; @@ -106,9 +71,9 @@ static INLINE usage_stats_t *get_or_set_usage_stats(reg_pressure_selector_env_t return us; } -static INLINE usage_stats_t *get_usage_stats(ir_node *irn) +static inline usage_stats_t *get_usage_stats(ir_node *irn) { - usage_stats_t *us = get_irn_link(irn); + usage_stats_t *us = (usage_stats_t*)get_irn_link(irn); assert(us && "This node must have usage stats"); return us; } @@ -120,20 +85,20 @@ static int max_hops_walker(reg_pressure_selector_env_t *env, ir_node *irn, ir_no * If the reached node is not in the block desired, * return the value passed for this situation. */ - if(get_nodes_block(irn) != bl) + if (get_nodes_block(irn) != bl) return block_dominates(bl, curr_bl) ? 0 : INT_MAX; /* * If the node is in the current block but not * yet scheduled, we keep on searching from that node. */ - if(!ir_nodeset_contains(&env->already_scheduled, irn)) { + if (!ir_nodeset_contains(&env->already_scheduled, irn)) { int i, n; int res = 0; - for(i = 0, n = get_irn_ins_or_deps(irn); i < n; ++i) { + for (i = 0, n = get_irn_ins_or_deps(irn); i < n; ++i) { ir_node *operand = get_irn_in_or_dep(irn, i); - if(get_irn_visited(operand) < visited_nr) { + if (get_irn_visited(operand) < visited_nr) { int tmp; set_irn_visited(operand, visited_nr); @@ -159,8 +124,6 @@ static int compute_max_hops(reg_pressure_selector_env_t *env, ir_node *irn) ir_graph *irg = get_irn_irg(bl); int res = 0; - const ir_edge_t *edge; - foreach_out_edge(irn, edge) { ir_node *user = get_edge_src_irn(edge); unsigned visited_nr = get_irg_visited(irg) + 1; @@ -174,56 +137,29 @@ static int compute_max_hops(reg_pressure_selector_env_t *env, ir_node *irn) return res; } -static void *reg_pressure_graph_init(const list_sched_selector_t *vtab, const be_irg_t *birg) +static void *reg_pressure_graph_init(ir_graph *irg) { - reg_pressure_main_env_t *main_env = xmalloc(sizeof(main_env[0])); + irg_walk_graph(irg, firm_clear_link, NULL, NULL); - main_env->arch_env = be_get_birg_arch_env(birg); - main_env->vtab = vtab; - irg_walk_graph(be_get_birg_irg(birg), firm_clear_link, NULL, NULL); - - return main_env; -} - -static INLINE int must_appear_in_schedule(const list_sched_selector_t *sel, void *block_env, const ir_node *irn) -{ - int res = -1; - - if(sel->to_appear_in_schedule) - res = sel->to_appear_in_schedule(block_env, irn); - - return res >= 0 ? res : (to_appear_in_schedule(irn) || be_is_Keep(irn) || be_is_CopyKeep(irn) || be_is_RegParams(irn)); + return NULL; } static void *reg_pressure_block_init(void *graph_env, ir_node *bl) { - ir_node *irn; - reg_pressure_selector_env_t *env = xmalloc(sizeof(env[0])); + reg_pressure_selector_env_t *env = XMALLOC(reg_pressure_selector_env_t); + (void) graph_env; obstack_init(&env->obst); ir_nodeset_init(&env->already_scheduled); env->root = NULL; - env->main_env = graph_env; /* * Collect usage statistics. */ sched_foreach(bl, irn) { - if(must_appear_in_schedule(env->main_env->vtab, env, irn)) { - int i, n; - - for(i = 0, n = get_irn_arity(irn); i < n; ++i) { - //ir_node *op = get_irn_n(irn, i); - if(must_appear_in_schedule(env->main_env->vtab, env, irn)) { - usage_stats_t *us = get_or_set_usage_stats(env, irn); -#if 0 /* Liveness is not computed here! */ - if(is_live_end(bl, op)) - us->uses_in_block = 99999; - else -#endif - us->uses_in_block++; - } - } + for (int i = 0, n = get_irn_arity(irn); i < n; ++i) { + usage_stats_t *us = get_or_set_usage_stats(env, irn); + us->uses_in_block++; } } @@ -232,10 +168,10 @@ static void *reg_pressure_block_init(void *graph_env, ir_node *bl) static void reg_pressure_block_free(void *block_env) { - reg_pressure_selector_env_t *env = block_env; + reg_pressure_selector_env_t *env = (reg_pressure_selector_env_t*)block_env; usage_stats_t *us; - for(us = env->root; us; us = us->next) + for (us = env->root; us; us = us->next) set_irn_link(us->irn, NULL); obstack_free(&env->obst, NULL); @@ -246,30 +182,31 @@ static void reg_pressure_block_free(void *block_env) static int get_result_hops_sum(reg_pressure_selector_env_t *env, ir_node *irn) { int res = 0; - if(get_irn_mode(irn) == mode_T) { - const ir_edge_t *edge; - + if (get_irn_mode(irn) == mode_T) { foreach_out_edge(irn, edge) res += get_result_hops_sum(env, get_edge_src_irn(edge)); } - else if(mode_is_data(get_irn_mode(irn))) + else if (mode_is_data(get_irn_mode(irn))) res = compute_max_hops(env, irn); return res; } -static INLINE int reg_pr_costs(reg_pressure_selector_env_t *env, ir_node *irn) +static inline int reg_pr_costs(reg_pressure_selector_env_t *env, ir_node *irn) { int i, n; int sum = 0; - for(i = 0, n = get_irn_arity(irn); i < n; ++i) { + for (i = 0, n = get_irn_arity(irn); i < n; ++i) { ir_node *op = get_irn_n(irn, i); - if(must_appear_in_schedule(env->main_env->vtab, env, op)) - sum += compute_max_hops(env, op); + if (is_Proj(op) + || (arch_get_irn_flags(op) & arch_irn_flags_not_scheduled)) + continue; + + sum += compute_max_hops(env, op); } sum += get_result_hops_sum(env, irn); @@ -277,24 +214,20 @@ static INLINE int reg_pr_costs(reg_pressure_selector_env_t *env, ir_node *irn) return sum; } -static ir_node *reg_pressure_select(void *block_env, ir_nodeset_t *ready_set, - ir_nodeset_t *live_set) +static ir_node *reg_pressure_select(void *block_env, ir_nodeset_t *ready_set) { - ir_nodeset_iterator_t iter; - reg_pressure_selector_env_t *env = block_env; - ir_node *irn, *res = NULL; - int curr_cost = INT_MAX; - (void) live_set; + reg_pressure_selector_env_t *env = (reg_pressure_selector_env_t*)block_env; + ir_node *res = NULL; + int curr_cost = INT_MAX; assert(ir_nodeset_size(ready_set) > 0); - ir_nodeset_iterator_init(&iter, ready_set); - while( (irn = ir_nodeset_iterator_next(&iter)) != NULL) { + foreach_ir_nodeset(ready_set, irn, iter) { /* Ignore branch instructions for the time being. They should only be scheduled if there is nothing else. */ - if (! arch_irn_class_is(env->main_env->arch_env, irn, branch)) { + if (!is_cfop(irn)) { int costs = reg_pr_costs(env, irn); if (costs <= curr_cost) { res = irn; @@ -308,10 +241,8 @@ static ir_node *reg_pressure_select(void *block_env, ir_nodeset_t *ready_set, Take it and finish. */ - if(!res) { - ir_nodeset_iterator_init(&iter, ready_set); - res = ir_nodeset_iterator_next(&iter); - + if (!res) { + res = ir_nodeset_first(ready_set); assert(res && "There must be a node scheduled."); } @@ -319,17 +250,22 @@ static ir_node *reg_pressure_select(void *block_env, ir_nodeset_t *ready_set, return res; } -static const list_sched_selector_t reg_pressure_selector_struct = { - reg_pressure_graph_init, - reg_pressure_block_init, - reg_pressure_select, - NULL, /* to_appear_in_schedule */ - NULL, /* node_ready */ - NULL, /* node_selected */ - NULL, /* exectime */ - NULL, /* latency */ - reg_pressure_block_free, - free -}; - -const list_sched_selector_t *reg_pressure_selector = ®_pressure_selector_struct; +static void sched_reg_pressure(ir_graph *irg) +{ + static const list_sched_selector_t reg_pressure_selector = { + reg_pressure_graph_init, + reg_pressure_block_init, + reg_pressure_select, + NULL, /* node_ready */ + NULL, /* node_selected */ + reg_pressure_block_free, + free + }; + be_list_sched_graph(irg, ®_pressure_selector); +} + +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_sched_regpress) +void be_init_sched_regpress(void) +{ + be_register_scheduler("regpress", sched_reg_pressure); +}