X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbelistsched.c;h=20f8fbce3f577c8685a191a308bdb2f3d93d54f1;hb=b35afc79238e7731b8b3beecc69468cb719735f5;hp=5a2aaa6f29fef6de464a480b2725735d4da525ad;hpb=52abe23f2fa0d4bd16ec0f2d707f99b201dc9fc2;p=libfirm diff --git a/ir/be/belistsched.c b/ir/be/belistsched.c index 5a2aaa6f2..20f8fbce3 100644 --- a/ir/be/belistsched.c +++ b/ir/be/belistsched.c @@ -22,7 +22,6 @@ * @brief Primitive list scheduling with different node selectors. * @author Sebastian Hack * @date 20.10.2004 - * @version $Id$ */ #include "config.h" @@ -30,13 +29,13 @@ #include #include #include +#include #include "benode.h" #include "be_t.h" #include "obst.h" #include "list.h" -#include "iterator.h" #include "iredges_t.h" #include "irgwalk.h" @@ -60,102 +59,65 @@ #include "lc_opts.h" #include "lc_opts_enum.h" -DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL); - -/** - * All scheduling info needed per node. - */ -typedef struct sched_irn_t { - unsigned num_not_sched_user; /**< The number of not yet scheduled users of this node */ - unsigned already_sched : 1; /**< Set if this node is already scheduled */ -} sched_irn_t; +DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) /** * Scheduling environment for the whole graph. */ typedef struct sched_env_t { - sched_irn_t *sched_info; /**< scheduling info per node */ - const list_sched_selector_t *selector; /**< The node selector. */ - void *selector_env; /**< A pointer to give to the selector. */ + unsigned *scheduled; /**< bitset of already scheduled nodes */ + const list_sched_selector_t *selector; /**< The node selector. */ + void *selector_env; /**< A pointer to give to the selector. */ } sched_env_t; /** * Environment for a block scheduler. */ typedef struct block_sched_env_t { - sched_irn_t *sched_info; /**< scheduling info per node, copied from the global scheduler object */ - ir_nodeset_t cands; /**< the set of candidates */ - ir_node *block; /**< the current block */ - sched_env_t *sched_env; /**< the scheduler environment */ - ir_nodeset_t live; /**< simple liveness during scheduling */ + /** scheduling info per node, copied from the global scheduler object */ + unsigned *scheduled; + /** the set of candidates */ + ir_nodeset_t cands; + ir_node *block; /**< the current block */ + sched_env_t *sched_env; /**< the scheduler environment */ const list_sched_selector_t *selector; - void *selector_block_env; + void *selector_block_env; } block_sched_env_t; /** * Returns non-zero if the node is already scheduled */ -static inline int is_already_scheduled(block_sched_env_t *env, ir_node *n) +static bool is_already_scheduled(const sched_env_t *env, ir_node *n) { - unsigned const idx = get_irn_idx(n); - - assert(idx < ARR_LEN(env->sched_info)); - return env->sched_info[idx].already_sched; + unsigned idx = get_irn_idx(n); + return rbitset_is_set(env->scheduled, idx); } /** * Mark a node as already scheduled */ -static inline void set_already_scheduled(block_sched_env_t *env, ir_node *n) +static void set_already_scheduled(sched_env_t *env, ir_node *n) { - unsigned const idx = get_irn_idx(n); - - assert(idx < ARR_LEN(env->sched_info)); - env->sched_info[idx].already_sched = 1; + unsigned idx = get_irn_idx(n); + rbitset_set(env->scheduled, idx); } static void selected(block_sched_env_t *env, ir_node *irn); +static void add_to_sched(block_sched_env_t *env, ir_node *irn); /** - * Try to put a node in the ready set. - * @param env The block scheduler environment. - * @param pred The previous scheduled node. - * @param irn The node to make ready. - * @return 1, if the node could be made ready, 0 else. + * Put a node in the ready set, or make it available immediately if it doesn't + * need to be scheduled */ -static inline int make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn) +static void node_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn) { - int i, n; - - /* Blocks cannot be scheduled. */ - if (is_Block(irn) || get_irn_n_edges(irn) == 0) - return 0; - - /* - * Check, if the given ir node is in a different block as the - * currently scheduled one. If that is so, don't make the node ready. - */ - if (env->block != get_nodes_block(irn)) - return 0; - - for (i = 0, n = get_irn_ins_or_deps(irn); i < n; ++i) { - ir_node *op = get_irn_in_or_dep(irn, i); - - /* if irn is an End we have keep-alives and op might be a block, skip that */ - if (is_Block(op)) { - assert(is_End(irn)); - continue; - } - - /* If the operand is local to the scheduled block and not yet - * scheduled, this nodes cannot be made ready, so exit. */ - if (! is_already_scheduled(env, op) && get_nodes_block(op) == env->block) - return 0; - } - - if (is_Proj(irn) || (arch_irn_get_flags(irn) & arch_irn_flags_not_scheduled)) { + if (is_Proj(irn) + || (arch_get_irn_flags(irn) & arch_irn_flags_not_scheduled)) { selected(env, irn); DB((dbg, LEVEL_3, "\tmaking immediately available: %+F\n", irn)); + } else if (be_is_Keep(irn) || be_is_CopyKeep(irn)) { + /* Keeps must be scheduled immediately */ + add_to_sched(env, irn); } else { ir_nodeset_insert(&env->cands, irn); @@ -165,140 +127,38 @@ static inline int make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn DB((dbg, LEVEL_2, "\tmaking ready: %+F\n", irn)); } - - return 1; } /** - * Try, to make all users of a node ready. - * In fact, a usage node can only be made ready, if all its operands - * have already been scheduled yet. This is checked by make_ready(). - * @param env The block schedule environment. - * @param irn The node, which usages (successors) are to be made ready. - */ -static void make_users_ready(block_sched_env_t *env, ir_node *irn) -{ - const ir_edge_t *edge; - - /* make all data users ready */ - foreach_out_edge(irn, edge) { - ir_node *user = get_edge_src_irn(edge); - - if (! is_Phi(user)) - make_ready(env, irn, user); - } - - /* and the dependent nodes as well */ - foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) { - ir_node *user = get_edge_src_irn(edge); - - if (! is_Phi(user)) - make_ready(env, irn, user); - } -} - -/** - * Returns the number of not yet schedules users. - */ -static inline int get_irn_not_sched_user(block_sched_env_t *env, ir_node *n) -{ - unsigned const idx = get_irn_idx(n); - - assert(idx < ARR_LEN(env->sched_info)); - return env->sched_info[idx].num_not_sched_user; -} - -/** - * Sets the number of not yet schedules users. - */ -static inline void set_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num) -{ - unsigned const idx = get_irn_idx(n); - - assert(idx < ARR_LEN(env->sched_info)); - env->sched_info[idx].num_not_sched_user = num; -} - -/** - * Add @p num to the number of not yet schedules users and returns the result. - */ -static inline int add_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num) -{ - unsigned const idx = get_irn_idx(n); - - assert(idx < ARR_LEN(env->sched_info)); - env->sched_info[idx].num_not_sched_user += num; - return env->sched_info[idx].num_not_sched_user; -} - -/** - * Returns the number of users of a node having mode datab. - */ -static int get_num_successors(ir_node *irn) -{ - int sum = 0; - const ir_edge_t *edge; - - if (get_irn_mode(irn) == mode_T) { - /* for mode_T nodes: count the users of all Projs */ - foreach_out_edge(irn, edge) { - ir_node *proj = get_edge_src_irn(edge); - ir_mode *mode = get_irn_mode(proj); - - if (mode == mode_T) { - sum += get_num_successors(proj); - } else if (mode_is_datab(mode)) { - sum += get_irn_n_edges(proj); - } - } - } - else { - /* do not count keep-alive edges */ - foreach_out_edge(irn, edge) { - if (get_irn_opcode(get_edge_src_irn(edge)) != iro_End) - sum++; - } - } - - return sum; -} - -/** - * Adds irn to @p live, updates all inputs that this user is scheduled - * and counts all of its non scheduled users. + * Try to put a node in the ready set. + * @param env The block scheduler environment. + * @param pred The previous scheduled node. + * @param irn The node to make ready. + * @return 1, if the node could be made ready, 0 else. */ -static void update_sched_liveness(block_sched_env_t *env, ir_node *irn) +static void try_make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn) { - int i; + int i, n; - /* ignore Projs */ - if (is_Proj(irn)) + /* we schedule one block at a time, so no need to consider users in other + * blocks */ + if (is_Block(irn) || get_nodes_block(irn) != env->block) return; + if (is_Phi(irn) || is_End(irn)) + return; + /* check if all operands are already available */ + n = get_irn_ins_or_deps(irn); + for (i = 0; i < n; ++i) { + ir_node *op = get_irn_in_or_dep(irn, i); - for (i = get_irn_ins_or_deps(irn) - 1; i >= 0; --i) { - ir_node *in = get_irn_in_or_dep(irn, i); - - /* if in is a proj: update predecessor */ - in = skip_Proj(in); - - /* if in is still in the live set: reduce number of users by one */ - if (ir_nodeset_contains(&env->live, in)) { - if (add_irn_not_sched_user(env, in, -1) <= 0) - ir_nodeset_remove(&env->live, in); - } + /* If the operand is local to the scheduled block and not yet + * scheduled, this nodes cannot be made ready, so exit. */ + if (get_nodes_block(op) == env->block + && !is_already_scheduled(env->sched_env, op)) + return; } - /* - get_num_successors returns the number of all users. This includes - users in different blocks as well. As the each block is scheduled separately - the liveness info of those users will not be updated and so these - users will keep up the register pressure as it is desired. - */ - i = get_num_successors(irn); - if (i > 0) { - set_irn_not_sched_user(env, irn, i); - ir_nodeset_insert(&env->live, irn); - } + node_ready(env, pred, irn); } static void selected(block_sched_env_t *env, ir_node *node) @@ -308,9 +168,17 @@ static void selected(block_sched_env_t *env, ir_node *node) env->selector->node_selected(env->selector_block_env, node); /* Insert the node in the set of all available scheduled nodes. */ - set_already_scheduled(env, node); + set_already_scheduled(env->sched_env, node); - make_users_ready(env, node); + /* check users, they might be ready now */ + foreach_out_edge(node, edge) { + ir_node *user = get_edge_src_irn(edge); + try_make_ready(env, node, user); + } + foreach_out_edge_kind(node, edge, EDGE_KIND_DEP) { + ir_node *user = get_edge_src_irn(edge); + try_make_ready(env, node, user); + } } /** @@ -321,12 +189,11 @@ static void selected(block_sched_env_t *env, ir_node *node) */ static void add_to_sched(block_sched_env_t *env, ir_node *irn) { - assert(! (arch_irn_get_flags(irn) & arch_irn_flags_not_scheduled)); + assert(! (arch_get_irn_flags(irn) & arch_irn_flags_not_scheduled)); - update_sched_liveness(env, irn); sched_add_before(env->block, irn); - DBG((dbg, LEVEL_2, "\tadding %+F\n", irn)); + DB((dbg, LEVEL_2, "\tschedule %+F\n", irn)); /* Remove the node from the ready set */ ir_nodeset_remove(&env->cands, irn); @@ -351,47 +218,25 @@ static void list_sched_block(ir_node *block, void *env_ptr) const list_sched_selector_t *selector = env->selector; block_sched_env_t be; - const ir_edge_t *edge; - ir_node *irn; - int j, m; + ir_nodeset_t *cands = &be.cands; /* Initialize the block's list head that will hold the schedule. */ sched_init_block(block); /* Initialize the block scheduling environment */ - be.sched_info = env->sched_info; - be.block = block; - ir_nodeset_init_size(&be.cands, get_irn_n_edges(block)); - ir_nodeset_init_size(&be.live, get_irn_n_edges(block)); - be.selector = selector; - be.sched_env = env; + be.block = block; + be.selector = selector; + be.sched_env = env; + ir_nodeset_init_size(cands, get_irn_n_edges(block)); - DBG((dbg, LEVEL_1, "scheduling %+F\n", block)); + DB((dbg, LEVEL_1, "scheduling %+F\n", block)); if (selector->init_block) be.selector_block_env = selector->init_block(env->selector_env, block); /* Then one can add all nodes are ready to the set. */ foreach_out_edge(block, edge) { - ir_node *irn = get_edge_src_irn(edge); - unsigned code = get_irn_opcode(irn); - int users; - - if (code == iro_End) { - /* Skip the end node because of keep-alive edges. */ - continue; - } - - users = get_irn_n_edges(irn); - if (users == 0) { - continue; - } else if (users == 1) { - /* ignore nodes that are only hold by the anchor */ - const ir_edge_t *edge = get_irn_out_edge_first_kind(irn, EDGE_KIND_NORMAL); - ir_node *user = get_edge_src_irn(edge); - if (is_Anchor(user)) - continue; - } + ir_node *irn = get_edge_src_irn(edge); if (is_Phi(irn)) { /* Phi functions are scheduled immediately, since they only @@ -401,60 +246,25 @@ static void list_sched_block(ir_node *block, void *env_ptr) /* The start block will be scheduled as the first node */ add_to_sched(&be, irn); } else { - /* Other nodes must have all operands in other blocks to be made - * ready */ - int ready = 1; - - /* Check, if the operands of a node are not local to this block */ - for (j = 0, m = get_irn_ins_or_deps(irn); j < m; ++j) { - ir_node *operand = get_irn_in_or_dep(irn, j); - - if (get_nodes_block(operand) == block) { - ready = 0; - break; - } else { - /* live in values increase register pressure */ - ir_nodeset_insert(&be.live, operand); - } - } - - /* Make the node ready, if all operands live in a foreign block */ - if (ready) { - DBG((dbg, LEVEL_2, "\timmediately ready: %+F\n", irn)); - make_ready(&be, NULL, irn); - } + try_make_ready(&be, NULL, irn); } } /* Iterate over all remaining nodes */ - while (ir_nodeset_size(&be.cands) > 0) { - ir_nodeset_iterator_t iter; - - /* Keeps must be scheduled immediately */ - foreach_ir_nodeset(&be.cands, irn, iter) { - if (be_is_Keep(irn) || be_is_CopyKeep(irn) || is_Sync(irn)) { - break; - } - } - - if (irn == NULL) { - irn = be.selector->select(be.selector_block_env, &be.cands, &be.live); - } - + while (ir_nodeset_size(cands) > 0) { + ir_node *irn = be.selector->select(be.selector_block_env, cands); DB((dbg, LEVEL_2, "\tpicked node %+F\n", irn)); + /* remove the scheduled node from the ready list. */ + ir_nodeset_remove(cands, irn); /* Add the node to the schedule. */ add_to_sched(&be, irn); - - /* remove the scheduled node from the ready list. */ - ir_nodeset_remove(&be.cands, irn); } + ir_nodeset_destroy(cands); + if (selector->finish_block) selector->finish_block(be.selector_block_env); - - ir_nodeset_destroy(&be.cands); - ir_nodeset_destroy(&be.live); } /* List schedule a graph. */ @@ -463,25 +273,19 @@ void be_list_sched_graph(ir_graph *irg, const list_sched_selector_t *selector) int num_nodes; sched_env_t env; -#if 1 /* Matze: This is very slow, we should avoid it to improve backend speed, * we just have to make sure that we have no dangling out-edges at this * point... */ - - /* Assure, that we have no dangling out-edges to deleted stuff */ edges_deactivate(irg); edges_activate(irg); -#endif num_nodes = get_irg_last_idx(irg); /* initialize environment for list scheduler */ memset(&env, 0, sizeof(env)); - env.selector = selector; - env.sched_info = NEW_ARR_F(sched_irn_t, num_nodes); - - memset(env.sched_info, 0, num_nodes * sizeof(env.sched_info[0])); + env.selector = selector; + env.scheduled = rbitset_malloc(num_nodes); if (selector->init_graph != NULL) env.selector_env = selector->init_graph(irg); @@ -492,10 +296,10 @@ void be_list_sched_graph(ir_graph *irg, const list_sched_selector_t *selector) if (selector->finish_graph != NULL) selector->finish_graph(env.selector_env); - DEL_ARR_F(env.sched_info); + free(env.scheduled); } -BE_REGISTER_MODULE_CONSTRUCTOR(be_init_listsched); +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_listsched) void be_init_listsched(void) { FIRM_DBG_REGISTER(dbg, "firm.be.sched");