X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbelistsched.c;h=2d2ab76a854bb97cce5dc86e1a687f96bc927748;hb=50234c949b8432ee8db8e45079cad83a6383fa49;hp=7111443c7eca7535ecc87040dc9867eda9ac31f1;hpb=8e0086dfdf3c7706b8bc4ee0e54097b4ed63d1e7;p=libfirm diff --git a/ir/be/belistsched.c b/ir/be/belistsched.c index 7111443c7..2d2ab76a8 100644 --- a/ir/be/belistsched.c +++ b/ir/be/belistsched.c @@ -14,19 +14,23 @@ #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. @@ -37,12 +41,52 @@ typedef struct _sched_env_t { void *selector_env; /**< A pointer to give to the selector. */ } sched_env_t; -static ir_node *trivial_select(void *env, void *block_env, const struct list_head *sched_head, +#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) +{ + struct trivial_sched_env *env; + const ir_node *p = a; + const ir_node *q = b; + int res = 0; + + 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 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_set); - pset_break(ready_set); - return res; + ir_node *res; + +#if 0 + int i, n = pset_count(ready_set); + ir_node *irn; + ir_node **ready = alloca(n * sizeof(ready[0])); + + for(irn = pset_first(ready_set); irn; irn = pset_next(ready_set)) + ready[i++] = irn; +#endif + + res = pset_first(ready_set); + pset_break(ready_set); + return res; } static const list_sched_selector_t trivial_selector_struct = { @@ -57,30 +101,24 @@ 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, const list_sched_selector_t *selector) +void list_sched(const struct _arch_isa_t *isa, ir_graph *irg) { - sched_env_t env; - - memset(&env, 0, sizeof(env)); - env.selector = selector; - env.selector_env = selector->init_graph ? selector->init_graph(irg) : NULL; - env.irg = irg; + sched_env_t env; + const list_sched_selector_t *selector; - /* Normalize proj nodes. */ - normalize_proj_nodes(irg); + 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; - /* Compute the outs */ - if(get_irg_outs_state(irg) != outs_consistent) - compute_outs(irg); + /* Assure, that the out edges are computed */ + edges_assure(irg); - /* Dump the graph. */ - //dump_ir_block_graph(irg, "-before-sched"); + /* Schedule each single block. */ + irg_block_walk_graph(irg, list_sched_block, NULL, &env); - /* 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); + if(selector->finish_graph) + selector->finish_graph(env.selector_env, irg); } @@ -88,35 +126,13 @@ void list_sched(ir_graph *irg, const list_sched_selector_t *selector) * 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; + int curr_time; + pset *ready_set; + pset *already_scheduled; + ir_node *block; + firm_dbg_module_t *dbg; } block_sched_env_t; - - -/** - * 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) -{ - int i, n; - - 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; - } - - return mode_is_datab(get_irn_mode(irn)); -} - - /** * Try to put a node in the ready set. * @param env The block scheduler environment. @@ -147,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; @@ -180,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); + } } /** @@ -213,10 +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); - info->time_step = env->curr_time; - 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. */ @@ -250,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); + } + } } /** @@ -276,7 +293,7 @@ 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) { @@ -284,9 +301,9 @@ static void list_sched_block(ir_node *block, void *env_ptr) 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 i, n, j, m; + int j, m; int phi_seen = 0; sched_info_t *info = get_irn_sched_info(block); @@ -297,17 +314,19 @@ static void list_sched_block(ir_node *block, void *env_ptr) 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)); + 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 %n\n", block)); + DBG((be.dbg, LEVEL_1, "scheduling %+F\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); + 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) @@ -324,21 +343,21 @@ static void list_sched_block(ir_node *block, void *env_ptr) /* Other nodes must have all operands in other blocks to be made * ready */ else { - bool ready = true; + 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 = false; + ready = 0; 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)); + DBG((be.dbg, LEVEL_2, "\timmediately ready: %+F\n", irn)); make_ready(&be, irn); } } @@ -348,12 +367,12 @@ static void list_sched_block(ir_node *block, void *env_ptr) 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)); + // 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)); + DBG((be.dbg, LEVEL_3, "\tpicked node %+F\n", irn)); /* Add the node to the schedule. */ add_to_sched(&be, irn);