X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Firextbb.c;h=5d9591261dd3764cd3ed49bbbef1e30b4bef7fa6;hb=d2dc2564b47d9c113d7e6e598574e9733627fcca;hp=8b3f867b3a556ce8e29d194545be1f793683e325;hpb=4fdc15b9e6c98c35906c0b3307e07766b3b13264;p=libfirm diff --git a/ir/ana/irextbb.c b/ir/ana/irextbb.c index 8b3f867b3..5d9591261 100644 --- a/ir/ana/irextbb.c +++ b/ir/ana/irextbb.c @@ -21,6 +21,8 @@ #include "irgwalk.h" #include "irnode_t.h" #include "irgraph_t.h" +#include "iredges_t.h" +#include "irouts.h" #include "xmalloc.h" #include "irprintf.h" @@ -29,6 +31,10 @@ typedef struct _env { ir_extblk *head; /**< head of the list of all extended blocks */ } env_t; +int (is_ir_extbb)(const void *thing) { + return _is_ir_extbb(thing); +} + /** * allocate a new extended block header. */ @@ -60,6 +66,25 @@ static void addto_extblk(ir_extblk *extblk, ir_node *block) set_Block_extbb(block, extblk); } +/** + * Returns the number of block successors. + * we are interested only in 1, 2 and >2. + */ +static int get_block_n_succs(ir_node *block) { + if (edges_activated(current_ir_graph)) { + const ir_edge_t *edge; + + edge = get_block_succ_first(block); + if (! edge) + return 0; + edge = get_block_succ_next(block, edge); + if (! edge) + return 1; + edge = get_block_succ_next(block, edge); + return edge ? 3 : 2; + } + return get_Block_n_cfg_outs(block); +} /** * Pre block-walker. Calculates the extended block info. @@ -70,8 +95,7 @@ static void pre_walk_calc_extbb(ir_node *block, void *ctx) env_t *env = ctx; if (n <= 0 || n > 1 || - block == get_irg_start_block(current_ir_graph) || - block == get_irg_end_block(current_ir_graph)) { + block == get_irg_start_block(current_ir_graph)) { /* * block is a JOIN-node ie the control flow from * many other blocks joins here. block is a leader. @@ -91,12 +115,35 @@ static void pre_walk_calc_extbb(ir_node *block, void *ctx) * Only one control flow predecessor. This block belongs * to the same extended basic block as its predecessor. */ - set_Block_extbb(block, NULL); + ir_node *cf_op = skip_Proj(get_Block_cfgpred(block, 0)); + + if (irn_not_visited(cf_op)) { + ir_node *pred_bl = get_nodes_block(cf_op); + if (get_block_n_succs(pred_bl) > 2) { + /* More than two successors means we have a jump table. + * we cannot include a jump target into the current extended + * basic block, so create a new one here. + */ + allocate_extblk(block, env); + } + else { + /* either the previous block has only one successor or + * this is the first successor after an if, include it. + */ + set_Block_extbb(block, NULL); + } + mark_irn_visited(cf_op); + } + else { + /* already marked, so begin a new extended block here */ + allocate_extblk(block, env); + } } } } -static int _sentinel; +/** A special extended block used as sentinel */ +static ir_extblk _sentinel = { k_ir_extblk, 0xFEA1DEAD }; /** * Post block-walker. Calculates the extended block info. @@ -107,7 +154,7 @@ static void post_walk_calc_extbb(ir_node *block, void *ctx) { ir_extblk *extbb = get_Block_extbb(block); env_t *env = ctx; - ir_extblk *sentinel = (ir_extblk *)&_sentinel; + ir_extblk *sentinel = &_sentinel; if (! extbb) { ir_node *curr, *prev; @@ -148,6 +195,66 @@ static void post_walk_calc_extbb(ir_node *block, void *ctx) } } +#ifdef NEED_SORT +/** + * Walker for cf_dependent_on(). + * This function searches a node tgt recursively from a given node + * but is restricted to the given extended basic block. + * + * @return 1 if tgt was reachable from curr, 0 if not. + */ +static int check_cf_dependence(ir_node *curr, ir_node *tgt, ir_extblk *extbb) +{ + int n, i; + + /* Note: we did not include the leader in our serach, so + there could not be any loops here. */ + if (get_Block_extbb(curr) != extbb) + return 0; + + if (curr == tgt) + return 1; + + for (i = 0, n = get_Block_n_cfgpreds(curr); i < n; ++i) { + if (check_cf_dependence(get_Block_cfgpred_block(curr, i), tgt, extbb)) + return 1; + } + return 0; +} + +/** + * Check if a block is control dependent on another one. + * Both blocks must be in the same extended basic block. + * @param blk1 The first block. + * @param blk2 The second block. + * @return 1, if blk1 is control dependent (transitively) on blk2, 0 if not. + */ +static int cf_dependent_on(ir_node *blk1, ir_node *blk2) +{ + ir_extblk *extbb = get_Block_extbb(blk1); + ir_graph *irg = get_irn_irg(blk1); + + assert(extbb == get_Block_extbb(blk2)); + return check_cf_dependence(blk1, blk2, extbb); +} + +/** + * Compare two blocks for dependency. + * + * @return + * 0 if both blocks nodes are equal + * 1 block b1 depends on block b2 + * -1 block b2 depends on block d2 + */ +static int block_order(const void *b1, const void *b2) +{ + ir_node *n1 = *(ir_node **)b1; + ir_node *n2 = *(ir_node **)b2; + + return n1 == n2 ? 0 : (cf_dependent_on(n1, n2) ? -1 : 1); +} +#endif /* NEED_SORT */ + /* * Compute the extended basic blocks for a graph */ @@ -165,6 +272,13 @@ void compute_extbb(ir_graph *irg) { env.obst = irg->extbb_obst; env.head = NULL; + if (! edges_activated(irg)) { + /* we don't have edges */ + assure_irg_outs(irg); + } + + /* we must mark nodes, so increase the visited flag */ + inc_irg_visited(irg); irg_block_walk_graph(irg, pre_walk_calc_extbb, post_walk_calc_extbb, &env); /* @@ -193,9 +307,20 @@ void compute_extbb(ir_graph *irg) { extbb->link = NULL; extbb->visited = 0; + +#ifdef NEED_SORT + /* we want the blocks in scheduled order, so sort them */ + /* FIXME: is this really needed? Or generates the algorithm automagically ordered ones? */ + if (len > 1) { + /* temporary remove the leader from the extended block to break loops */ + set_Block_extbb(extbb->blks[0], NULL); + qsort(&extbb->blks[1], len-1, sizeof(extbb->blks[0]), block_order); + set_Block_extbb(extbb->blks[0], extbb); + } +#endif } - irg->extblk_state = ir_extblk_info_valid; + irg->extblk_state = extblk_valid; } /* free all extended block info. */ @@ -205,7 +330,7 @@ void free_extbb(ir_graph *irg) { xfree(irg->extbb_obst); irg->extbb_obst = NULL; } - irg->extblk_state = ir_extblk_info_none; + irg->extblk_state = extblk_none; } /* Return the extended block of a node. */ @@ -300,16 +425,22 @@ static void irg_extblock_walk_2(ir_extblk *blk, extbb_walk_func *pre, extbb_walk flag, so that it can be interleaved with the other walker. */ void irg_extblock_walk(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env) { - ir_node *block, *pred; + ir_node *pred, *start_bl = get_irg_start_block(current_ir_graph); + ir_extblk *start_blk = get_Block_extbb(start_bl); int i; assert(blk); assert(!get_interprocedural_view()); /* interprocedural_view not implemented */ inc_irg_block_visited(current_ir_graph); - irg_extblock_walk_2(block, pre, post, env); + + /* assure the start block is the first one */ + mark_extbb_visited(start_blk); + if (post) + post(start_blk, env); + irg_extblock_walk_2(blk, pre, post, env); /* keepalive: the endless loops ... */ - if (get_extbb_leader(blk) == get_irg_end_block(current_ir_graph)) { + if (blk == get_Block_extbb(get_irg_end_block(current_ir_graph))) { ir_node *node = get_irg_end(current_ir_graph); int arity = get_irn_arity(node); for (i = 0; i < arity; i++) { @@ -326,13 +457,16 @@ void irg_extblock_walk(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *po } } } + + if (pre) + pre(start_blk, env); } /* Walks only over reachable Extended Basic Block nodes in the graph. */ void irg_extblock_walk_graph(ir_graph *irg, extbb_walk_func *pre, extbb_walk_func *post, void *env) { - ir_node *end = get_irg_end(irg); - ir_extblk *blk = get_Block_extbb(end); + ir_node *endbl = get_irg_end_block(irg); + ir_extblk *blk = get_Block_extbb(endbl); ir_graph *rem = current_ir_graph; current_ir_graph = irg; irg_extblock_walk(blk, pre, post, env);