X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbelistsched.c;h=2d2ab76a854bb97cce5dc86e1a687f96bc927748;hb=50234c949b8432ee8db8e45079cad83a6383fa49;hp=c80a0864b5e2bdee5c33ab119b9b03e8aedf2b83;hpb=a60e76c8b340baf47fd348a183a495b390a7c53e;p=libfirm diff --git a/ir/be/belistsched.c b/ir/be/belistsched.c index c80a0864b..2d2ab76a8 100644 --- a/ir/be/belistsched.c +++ b/ir/be/belistsched.c @@ -4,6 +4,9 @@ * @date 20.10.2004 * @author Sebastian Hack */ +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif #include #include @@ -11,96 +14,125 @@ #include "fourcc.h" #include "obst.h" -#include "irouts.h" +#include "list.h" +#include "iterator.h" + +#include "iredges_t.h" #include "irgwalk.h" #include "irnode_t.h" #include "irmode_t.h" -#include "list.h" -#include "iterator.h" #include "irdump.h" #include "irprintf_t.h" #include "debug.h" #include "besched_t.h" #include "beutil.h" +#include "belive_t.h" #include "belistsched.h" +#include "firm/bearch_firm.h" + /** * Scheduling environment for the whole graph. */ typedef struct _sched_env_t { const ir_graph *irg; /**< The graph to schedule. */ - list_sched_selector_t *select; /**< The node selector. */ - void *select_env; /**< A pointer to give to the selector. */ + const list_sched_selector_t *selector; /**< The node selector. */ + void *selector_env; /**< A pointer to give to the selector. */ } sched_env_t; -ir_node *trivial_selector(void *env, ir_node *block, int curr_time, - pset *already_scheduled, pset *ready_list) +#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) { - ir_node *res = pset_first(ready_list); - pset_break(ready_list); - return res; -} + struct trivial_sched_env *env; + const ir_node *p = a; + const ir_node *q = b; + int res = 0; -static void list_sched_block(ir_node *block, void *env_ptr); + 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; -void list_sched(ir_graph *irg, list_sched_selector_t *selector, void *select_env) -{ - sched_env_t env; - memset(&env, 0, sizeof(env)); - env.select = selector; - env.select_env = select_env; - env.irg = irg; + return res; +} +#endif - /* Normalize proj nodes. */ - normalize_proj_nodes(irg); +static ir_node *trivial_select(void *env, void *block_env, + const struct list_head *sched_head, + int curr_time, pset *ready_set) +{ + ir_node *res; - /* Compute the outs */ - if(get_irg_outs_state(irg) != outs_consistent) - compute_outs(irg); +#if 0 + int i, n = pset_count(ready_set); + ir_node *irn; + ir_node **ready = alloca(n * sizeof(ready[0])); - /* Dump the graph. */ - dump_ir_block_graph(irg, "-before-sched"); + for(irn = pset_first(ready_set); irn; irn = pset_next(ready_set)) + ready[i++] = irn; +#endif - /* Schedule each single block. */ - irg_block_walk_graph(irg, list_sched_block, NULL, &env); + res = pset_first(ready_set); + pset_break(ready_set); + return res; } +static const list_sched_selector_t trivial_selector_struct = { + NULL, + NULL, + trivial_select, + NULL, + NULL +}; -/** - * Environment for a block scheduler. - */ -typedef struct _block_sched_env_t { - int curr_time; - pset *ready_set; - pset *already_scheduled; - ir_node *block; - firm_dbg_module_t *dbg; -} block_sched_env_t; - +const list_sched_selector_t *trivial_selector = &trivial_selector_struct; +static void list_sched_block(ir_node *block, void *env_ptr); -/** - * Checks, if a node is to appear in a schedule. Such nodes either - * consume real data (mode datab) or produce such. - * @param irn The node to check for. - * @return 1, if the node consumes/produces data, false if not. - */ -static INLINE int to_appear_in_schedule(ir_node *irn) +void list_sched(const struct _arch_isa_t *isa, ir_graph *irg) { - int i, n; + sched_env_t env; + const list_sched_selector_t *selector; - for(i = 0, n = get_irn_arity(irn); i < n; ++i) { - ir_node *op = get_irn_n(irn, i); - if(mode_is_datab(get_irn_mode(op))) - return 1; - } + memset(&env, 0, sizeof(env)); + selector = env.selector = isa->impl->get_list_sched_selector(isa); + env.selector_env = selector->init_graph ? selector->init_graph(isa, irg) : NULL; + env.irg = irg; + + /* Assure, that the out edges are computed */ + edges_assure(irg); + + /* Schedule each single block. */ + irg_block_walk_graph(irg, list_sched_block, NULL, &env); - return mode_is_datab(get_irn_mode(irn)); + if(selector->finish_graph) + selector->finish_graph(env.selector_env, irg); } +/** + * Environment for a block scheduler. + */ +typedef struct _block_sched_env_t { + int curr_time; + pset *ready_set; + pset *already_scheduled; + ir_node *block; + firm_dbg_module_t *dbg; +} block_sched_env_t; + /** * Try to put a node in the ready set. * @param env The block scheduler environment. @@ -131,7 +163,7 @@ static INLINE int make_ready(block_sched_env_t *env, ir_node *irn) return 0; } - DBG((env->dbg, LEVEL_2, "\tmaking ready: %n\n", irn)); + DBG((env->dbg, LEVEL_2, "\tmaking ready: %+F\n", irn)); pset_insert_ptr(env->ready_set, irn); return 1; @@ -164,13 +196,13 @@ static INLINE int make_ready(block_sched_env_t *env, ir_node *irn) */ static INLINE void make_users_ready(block_sched_env_t *env, ir_node *irn) { - int i, n; + const ir_edge_t *edge; - for(i = 0, n = get_irn_n_outs(irn); i < n; ++i) { - ir_node *user = get_irn_out(irn, i); - if(!is_Phi(user)) - make_ready(env, user); - } + foreach_out_edge(irn, edge) { + ir_node *user = edge->src; + if(!is_Phi(user)) + make_ready(env, user); + } } /** @@ -197,9 +229,10 @@ static ir_node *add_to_sched(block_sched_env_t *env, ir_node *irn) if(to_appear_in_schedule(irn)) { sched_info_t *info = get_irn_sched_info(irn); INIT_LIST_HEAD(&info->list); - sched_add(env->block, irn); + info->scheduled = 1; + sched_add_before(env->block, irn); - DBG((env->dbg, LEVEL_2, "\tadding %n\n", irn)); + DBG((env->dbg, LEVEL_2, "\tadding %+F\n", irn)); } /* Insert the node in the set of all already scheduled nodes. */ @@ -233,21 +266,22 @@ static ir_node *add_to_sched(block_sched_env_t *env, ir_node *irn) */ static void add_tuple_projs(block_sched_env_t *env, ir_node *irn) { - int i, n; - assert(get_irn_mode(irn) == mode_T && "Mode of node must be tuple"); + const ir_edge_t *edge; - for(i = 0, n = get_irn_n_outs(irn); i < n; ++i) { - ir_node *out = get_irn_out(irn, i); + assert(get_irn_mode(irn) == mode_T && "Mode of node must be tuple"); - assert(is_Proj(out) && "successor of a modeT node must be a proj"); + foreach_out_edge(irn, edge) { + ir_node *out = edge->src; - if(get_irn_mode(out) == mode_T) - add_tuple_projs(env, out); - else { - add_to_sched(env, out); - make_users_ready(env, out); - } - } + assert(is_Proj(out) && "successor of a modeT node must be a proj"); + + if(get_irn_mode(out) == mode_T) + add_tuple_projs(env, out); + else { + add_to_sched(env, out); + make_users_ready(env, out); + } + } } /** @@ -259,96 +293,106 @@ static void add_tuple_projs(block_sched_env_t *env, ir_node *irn) * Also the outs must have been computed. * * @param block The block node. - * @param env Schedulting environment. + * @param env Scheduling environment. */ static void list_sched_block(ir_node *block, void *env_ptr) { - sched_env_t *env = env_ptr; - block_sched_env_t be; - - ir_node *irn; - int j, m; - int phi_seen = 0; - sched_info_t *info = get_irn_sched_info(block); - - /* Initialize the block's list head that will hold the schedule. */ - INIT_LIST_HEAD(&info->list); - - /* Initialize the block scheduling environment */ - be.dbg = firm_dbg_register("firm.be.sched"); - be.block = block; - be.curr_time = 0; - be.ready_set = new_pset(node_cmp_func, get_irn_n_outs(block)); - be.already_scheduled = new_pset(node_cmp_func, get_irn_n_outs(block)); - - DBG((be.dbg, LEVEL_1, "scheduling %n\n", block)); - - /* Then one can add all nodes are ready to the set. */ - int i; - int n; - for(i = 0, n = get_irn_n_outs(block); i < n; ++i) { - ir_node *irn = get_irn_out(block, i); - - /* Phi functions are scheduled immediately, since they only transfer - * data flow from the predecessors to this block. */ - if(is_Phi(irn)) { - add_to_sched(&be, irn); - make_users_ready(&be, irn); - phi_seen = 1; - } - - /* Other nodes must have all operands in other blocks to be made - * ready */ - else { - bool ready = true; - - /* Check, if the operands of a node are not local to this block */ - for(j = 0, m = get_irn_arity(irn); j < m; ++j) { - ir_node *operand = get_irn_n(irn, j); - - if(get_nodes_block(operand) == block) { - ready = false; - break; - } - } - - /* Make the node ready, if all operands live in a foreign block */ - if(ready) { - DBG((be.dbg, LEVEL_2, "\timmediately ready: %n\n", irn)); - make_ready(&be, irn); - } - } - } - - /* Increase the time, if some phi functions have been scheduled */ - be.curr_time += phi_seen; - - while(pset_count(be.ready_set) > 0) { - DBG((be.dbg, LEVEL_2, "\tready set: %*n\n", pset_iterator, be.ready_set)); - // pset_print(stdout, be.ready_set, irn_printer); - - /* select a node to be scheduled and check if it was ready */ - irn = env->select(env->select_env, block, be.curr_time, - be.already_scheduled, be.ready_set); - - DBG((be.dbg, LEVEL_3, "\tpicked node %n\n", irn)); - - /* Add the node to the schedule. */ - add_to_sched(&be, irn); - - if(get_irn_mode(irn) == mode_T) - add_tuple_projs(&be, irn); - else - make_users_ready(&be, irn); - - /* Increase the time step. */ - be.curr_time += 1; - - /* remove the scheduled node from the ready list. */ - if(pset_find_ptr(be.ready_set, irn)) - pset_remove_ptr(be.ready_set, irn); - } - - del_pset(be.ready_set); - del_pset(be.already_scheduled); + void *block_env = NULL; + sched_env_t *env = env_ptr; + block_sched_env_t be; + const list_sched_selector_t *selector = env->selector; + const ir_edge_t *edge; + ir_node *irn; + int j, m; + int phi_seen = 0; + sched_info_t *info = get_irn_sched_info(block); + + /* Initialize the block's list head that will hold the schedule. */ + INIT_LIST_HEAD(&info->list); + + /* Initialize the block scheduling environment */ + be.dbg = firm_dbg_register("firm.be.sched"); + be.block = block; + be.curr_time = 0; + be.ready_set = new_pset(node_cmp_func, get_irn_n_edges(block)); + be.already_scheduled = new_pset(node_cmp_func, get_irn_n_edges(block)); + + firm_dbg_set_mask(be.dbg, 0); + + if(selector->init_block) + block_env = selector->init_block(env->selector_env, block); + + DBG((be.dbg, LEVEL_1, "scheduling %+F\n", 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); + + /* Skip the end node because of keepalive edges. */ + if(get_irn_opcode(irn) == iro_End) + continue; + + /* Phi functions are scheduled immediately, since they only transfer + * data flow from the predecessors to this block. */ + if(is_Phi(irn)) { + add_to_sched(&be, irn); + make_users_ready(&be, irn); + phi_seen = 1; + } + + /* Other nodes must have all operands in other blocks to be made + * ready */ + else { + int ready = 1; + + /* Check, if the operands of a node are not local to this block */ + for(j = 0, m = get_irn_arity(irn); j < m; ++j) { + ir_node *operand = get_irn_n(irn, j); + + if(get_nodes_block(operand) == block) { + ready = 0; + break; + } + } + + /* Make the node ready, if all operands live in a foreign block */ + if(ready) { + DBG((be.dbg, LEVEL_2, "\timmediately ready: %+F\n", irn)); + make_ready(&be, irn); + } + } + } + + /* Increase the time, if some phi functions have been scheduled */ + be.curr_time += phi_seen; + + while(pset_count(be.ready_set) > 0) { + // DBG((be.dbg, LEVEL_2, "\tready set: %*n\n", pset_iterator, be.ready_set)); + + /* select a node to be scheduled and check if it was ready */ + irn = selector->select(env->selector_env, block_env, &info->list, be.curr_time, be.ready_set); + + DBG((be.dbg, LEVEL_3, "\tpicked node %+F\n", irn)); + + /* Add the node to the schedule. */ + add_to_sched(&be, irn); + + if(get_irn_mode(irn) == mode_T) + add_tuple_projs(&be, irn); + else + make_users_ready(&be, irn); + + /* Increase the time step. */ + be.curr_time += 1; + + /* remove the scheduled node from the ready list. */ + if(pset_find_ptr(be.ready_set, irn)) + pset_remove_ptr(be.ready_set, irn); + } + + if(selector->finish_block) + selector->finish_block(env->selector_env, block_env, block); + + del_pset(be.ready_set); + del_pset(be.already_scheduled); }