X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbesched.c;h=0026d35bdd8670ae16470cd4f6b69948b88dbbb6;hb=755e96e2816108e2bef2317b741e49aac230d5bb;hp=8bc578e479b41f4b8db83b095826e3aad7ca68b4;hpb=815bec48617376ca9f803033dcd8bd97c7283765;p=libfirm diff --git a/ir/be/besched.c b/ir/be/besched.c index 8bc578e47..0026d35bd 100644 --- a/ir/be/besched.c +++ b/ir/be/besched.c @@ -11,11 +11,14 @@ #include "impl.h" #include "irprintf.h" #include "irgwalk.h" -#include "irnode_t.h" +#include "firm_types.h" #include "irgraph_t.h" #include "iredges_t.h" +#include "ircons.h" +#include "irextbb.h" #include "debug.h" +#include "bemodule.h" #include "bearch.h" #include "besched_t.h" #include "beutil.h" @@ -30,6 +33,8 @@ FIRM_IMPL1(sched_first, ir_node *, const ir_node *) FIRM_IMPL1(sched_last, ir_node *, const ir_node *) FIRM_IMPL2(sched_add_after, ir_node *, ir_node *, ir_node *) FIRM_IMPL2(sched_add_before, ir_node *, ir_node *, ir_node *) +FIRM_IMPL1_VOID(sched_init_block, ir_node *) +FIRM_IMPL1_VOID(sched_reset, ir_node *) FIRM_IMPL2(sched_comes_after, int, const ir_node *, const ir_node *) FIRM_IMPL1_VOID(sched_remove, ir_node *) @@ -37,12 +42,13 @@ size_t sched_irn_data_offset = 0; static void block_sched_dumper(ir_node *block, void *env) { - FILE *f = env; + FILE *f = env; const ir_node *curr; ir_fprintf(f, "%+F:\n", block); + sched_foreach(block, curr) { - sched_info_t *info = get_irn_sched_info(curr); + sched_info_t *info = get_irn_sched_info(curr); ir_fprintf(f, "\t%6d: %+F\n", info->time_step, curr); } } @@ -53,16 +59,18 @@ void be_sched_dump(FILE *f, ir_graph *irg) } /* Init the scheduling stuff. */ -void be_sched_init(void) +void be_init_sched(void) { sched_irn_data_offset = register_additional_node_data(sizeof(sched_info_t)); } +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_sched); + void sched_renumber(const ir_node *block) { ir_node *irn; sched_info_t *inf; - sched_timestep_t step = 0; + sched_timestep_t step = SCHED_INITIAL_GRANULARITY; sched_foreach(block, irn) { inf = get_irn_sched_info(irn); @@ -182,7 +190,7 @@ int sched_verify_irg(ir_graph *irg) int sched_skip_cf_predicator(const ir_node *irn, void *data) { arch_env_t *ae = data; - return arch_irn_classify(ae, irn) == arch_irn_class_branch; + return arch_irn_class_is(ae, irn, branch); } int sched_skip_phi_predicator(const ir_node *irn, void *data) { @@ -195,68 +203,75 @@ ir_node *sched_skip(ir_node *from, int forward, sched_predicator_t *predicator, const ir_node *bl = get_block(from); ir_node *curr; - if (is_Block(from)) - from = forward ? sched_next(from) : sched_prev(from); - - for(curr = from; curr != bl && predicator(curr, data); curr = forward ? sched_next(curr) : sched_prev(curr)); + if (forward) { + if (is_Block(from)) + from = sched_next(from); + for (curr = from; curr != bl && predicator(curr, data); curr = sched_next(curr)) { + } + } else { + if (is_Block(from)) + from = sched_prev(from); + for (curr = from; curr != bl && predicator(curr, data); curr = sched_prev(curr)) { + } + } return curr; } -/** A simple forward single linked list. */ -typedef struct { - ir_node *start; /**< start of the list */ - ir_node *end; /**< last block in the list */ - unsigned n_blks; /**< number of blocks in the list */ -} anchor; +//--------------------------------------------------------------------------- + +typedef struct remove_dead_nodes_env_t_ { + ir_graph *irg; + bitset_t *reachable; +} remove_dead_nodes_env_t; /** - * Ext-Block walker: create a block schedule + * Post-walker: remember all visited nodes in a bitset. */ -static void create_block_list(ir_extblk *blk, void *env) { - anchor *list = env; - int i, n; - - for (i = 0, n = get_extbb_n_blocks(blk); i < n; ++i) { - ir_node *block = get_extbb_block(blk, i); - - set_irn_link(block, NULL); - if (list->start) - set_irn_link(list->end, block); - else - list->start = block; - - list->end = block; - ++list->n_blks; - } +static void mark_dead_nodes_walker(ir_node *node, void *data) +{ + remove_dead_nodes_env_t *env = (remove_dead_nodes_env_t*) data; + bitset_set(env->reachable, get_irn_idx(node)); } -/* - * Calculates a block schedule. The schedule is stored as a linked - * list starting at the start_block of the irg. +/** + * Post-block-walker: + * Walk through the schedule of every block and remove all dead nodes from it. */ -ir_node **sched_create_block_schedule(ir_graph *irg) +static void remove_dead_nodes_walker(ir_node *block, void *data) { - anchor list; - ir_node **blk_list, *b, *n; - unsigned i; + remove_dead_nodes_env_t *env = (remove_dead_nodes_env_t*) data; + ir_node *node, *next; + + for (node = sched_first(block); ! sched_is_end(node); node = next) { + int i; - /* schedule extended basic blocks */ - compute_extbb(irg); + /* get next node now, as after calling sched_remove it will be invalid */ + next = sched_next(node); - list.start = NULL; - list.end = NULL; - list.n_blks = 0; - irg_extblock_walk_graph(irg, NULL, create_block_list, &list); + if (bitset_is_set(env->reachable, get_irn_idx(node))) + continue; - /** create an array, so we can go forward and backward */ - blk_list = NEW_ARR_D(ir_node *, irg->obst,list.n_blks); + sched_remove(node); - for (i = 0, b = list.start; b; b = n, ++i) { - n = get_irn_link(b); - set_irn_link(b, INT_TO_PTR(i)); + /* when a node is exchanged, it is turned into Bad, do not set ins for those */ + if (is_Bad(node)) + continue; - blk_list[i] = b; + for (i = get_irn_arity(node) - 1; i >= 0; --i) + set_irn_n(node, i, new_r_Bad(env->irg)); } - return blk_list; +} + +void be_remove_dead_nodes_from_schedule(ir_graph *irg) +{ + remove_dead_nodes_env_t env; + env.irg = irg; + env.reachable = bitset_alloca(get_irg_last_idx(irg)); + + // mark all reachable nodes + irg_walk_graph(irg, mark_dead_nodes_walker, NULL, &env); + + // walk schedule and remove non-marked nodes + irg_block_walk_graph(irg, remove_dead_nodes_walker, NULL, &env); }