X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbelistsched.c;h=7111443c7eca7535ecc87040dc9867eda9ac31f1;hb=4ca59cb404899ecc345f6eb30d82a623a346b6fe;hp=f7a16ef75d2d1834baa49967068f352b57ada512;hpb=15fb50549230a9c10012ed2a45fe332b6a799acd;p=libfirm diff --git a/ir/be/belistsched.c b/ir/be/belistsched.c index f7a16ef75..7111443c7 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 @@ -19,6 +22,7 @@ #include "iterator.h" #include "irdump.h" #include "irprintf_t.h" +#include "debug.h" #include "besched_t.h" #include "beutil.h" @@ -29,27 +33,37 @@ */ 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) +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 = pset_first(ready_list); - pset_break(ready_list); + ir_node *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 +}; + +const list_sched_selector_t *trivial_selector = &trivial_selector_struct; + static void list_sched_block(ir_node *block, void *env_ptr); -void list_sched(ir_graph *irg, list_sched_selector_t *selector, void *select_env) +void list_sched(ir_graph *irg, const list_sched_selector_t *selector) { sched_env_t env; memset(&env, 0, sizeof(env)); - env.select = selector; - env.select_env = select_env; + env.selector = selector; + env.selector_env = selector->init_graph ? selector->init_graph(irg) : NULL; env.irg = irg; /* Normalize proj nodes. */ @@ -60,10 +74,13 @@ void list_sched(ir_graph *irg, list_sched_selector_t *selector, void *select_env compute_outs(irg); /* Dump the graph. */ - dump_ir_block_graph(irg, "-before-sched"); + //dump_ir_block_graph(irg, "-before-sched"); /* Schedule each single block. */ irg_block_walk_graph(irg, list_sched_block, NULL, &env); + + if(selector->finish_graph) + selector->finish_graph(env.selector_env, irg); } @@ -75,6 +92,7 @@ typedef struct _block_sched_env_t { pset *ready_set; pset *already_scheduled; ir_node *block; + firm_dbg_module_t *dbg; } block_sched_env_t; @@ -129,7 +147,7 @@ static INLINE int make_ready(block_sched_env_t *env, ir_node *irn) return 0; } - ir_debugf("\tmaking ready: %n\n", irn); + DBG((env->dbg, LEVEL_2, "\tmaking ready: %n\n", irn)); pset_insert_ptr(env->ready_set, irn); return 1; @@ -166,7 +184,8 @@ static INLINE void make_users_ready(block_sched_env_t *env, ir_node *irn) for(i = 0, n = get_irn_n_outs(irn); i < n; ++i) { ir_node *user = get_irn_out(irn, i); - make_ready(env, user); + if(!is_Phi(user)) + make_ready(env, user); } } @@ -194,9 +213,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); + info->time_step = env->curr_time; sched_add(env->block, irn); - ir_debugf("\tadding %n\n", irn); + DBG((env->dbg, LEVEL_2, "\tadding %n\n", irn)); } /* Insert the node in the set of all already scheduled nodes. */ @@ -260,99 +280,100 @@ static void add_tuple_projs(block_sched_env_t *env, ir_node *irn) */ 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.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)); - - ir_debugf("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) { - ir_debugf("\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) { - ir_debugf("\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); - - ir_debugf("\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); - - { - sched_info_t *inf; - list_for_each_entry(sched_info_t, inf, &info->list, list) { - ir_node *irn = get_sched_info_irn(inf); - ir_debugf("node: %n, pos: %d\n", irn, inf->time_step); - } - } + void *block_env = NULL; + sched_env_t *env = env_ptr; + block_sched_env_t be; + const list_sched_selector_t *selector = env->selector; + + ir_node *irn; + int i, n, 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)); + + if(selector->init_block) + block_env = selector->init_block(env->selector_env, block); + + DBG((be.dbg, LEVEL_1, "scheduling %n\n", block)); + + /* Then one can add all nodes are ready to the set. */ + for(i = 0, n = get_irn_n_outs(block); i < n; ++i) { + ir_node *irn = get_irn_out(block, i); + + /* 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 { + 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)); + + /* 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 %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); + } + + if(selector->finish_block) + selector->finish_block(env->selector_env, block_env, block); + + del_pset(be.ready_set); + del_pset(be.already_scheduled); }