X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Flower%2Flower_switch.c;h=bc6eed0df79d14b6888b7eac17230c5c41d3593d;hb=2cb4a701f143339e07259cf7331c670f5584de63;hp=1c794554224d08a59c3d6ebae2413418c197fa49;hpb=014476c446ab6fd72461c764c018fa401e5f88c1;p=libfirm diff --git a/ir/lower/lower_switch.c b/ir/lower/lower_switch.c index 1c7945542..bc6eed0df 100644 --- a/ir/lower/lower_switch.c +++ b/ir/lower/lower_switch.c @@ -24,24 +24,23 @@ * @version $Id$ */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif #include +#include "array_t.h" #include "ircons.h" #include "irgopt.h" #include "irgwalk.h" #include "irnode_t.h" #include "irouts.h" +#include "irpass_t.h" #define foreach_out_irn(irn, i, outirn) for(i = get_irn_n_outs(irn) - 1;\ i >= 0 && (outirn = get_irn_out(irn, i)); --i) typedef struct walk_env { unsigned spare_size; /**< the allowed spare size for table switches */ - struct obstack obst; /**< the obstack where data is allocated on */ int changed; /**< indicates whether a change was performed */ } walk_env_t; @@ -72,21 +71,21 @@ static int should_do_table_switch(ir_node *cond, unsigned spare_size) unsigned long spare, num_cases = 0; /* TODO: Minimum size for jump table? */ - if(get_irn_n_outs(cond) <= 4) + if (get_irn_n_outs(cond) <= 4) return 0; - default_pn = get_Cond_defaultProj(cond); + default_pn = get_Cond_default_proj(cond); foreach_out_irn(cond, i, proj) { long pn = get_Proj_proj(proj); - if(pn == default_pn) + if (pn == default_pn) continue; - if(pn < switch_min) + if (pn < switch_min) switch_min = pn; - if(pn > switch_max) + if (pn > switch_max) switch_max = pn; - num_cases++; + ++num_cases; } /* @@ -99,7 +98,9 @@ static int should_do_table_switch(ir_node *cond, unsigned spare_size) static int casecmp(const void *a, const void *b) { - return ((case_data_t *) a)->value - ((case_data_t *) b)->value; + const case_data_t *cda = a; + const case_data_t *cdb = b; + return (cda->value > cdb->value) - (cda->value < cdb->value); } /** @@ -108,10 +109,14 @@ static int casecmp(const void *a, const void *b) static void create_if_cascade(ifcas_env_t *env, ir_node *curblock, case_data_t *curcases, int numcases) { + assert(numcases >= 0); + set_cur_block(curblock); - if(numcases == 1) - { + if (numcases == 0) { + /* zero cases: "goto default;" */ + env->defusers[env->defindex++] = new_Jmp(); + } else if (numcases == 1) { /* only one case: "if(sel == val) goto target else goto default;" */ ir_node *val = new_Const_long(get_irn_mode(env->sel), curcases[0].value); ir_node *cmp = new_Cmp(env->sel, val); @@ -119,7 +124,7 @@ static void create_if_cascade(ifcas_env_t *env, ir_node *curblock, ir_node *cond = new_Cond(proj); set_Block_cfgpred(curcases[0].target, 0, new_Proj(cond, mode_X, pn_Cond_true)); env->defusers[env->defindex++] = new_Proj(cond, mode_X, pn_Cond_false); - } else if(numcases == 2) { + } else if (numcases == 2) { /* only two cases: "if(sel == val[0]) goto target[0];" */ ir_node *val = new_Const_long(get_irn_mode(env->sel), curcases[0].value); ir_node *cmp = new_Cmp(env->sel, val); @@ -131,6 +136,7 @@ static void create_if_cascade(ifcas_env_t *env, ir_node *curblock, set_Block_cfgpred(curcases[0].target, 0, new_Proj(cond, mode_X, pn_Cond_true)); in[0] = new_Proj(cond, mode_X, pn_Cond_false); neblock = new_Block(1, in); + set_cur_block(neblock); /* second part: "else if(sel == val[1]) goto target[1] else goto default;" */ val = new_Const_long(get_irn_mode(env->sel), curcases[1].value); @@ -156,6 +162,7 @@ static void create_if_cascade(ifcas_env_t *env, ir_node *curblock, set_cur_block(curblock); in[0] = new_Proj(cond, mode_X, pn_Cond_false); geblock = new_Block(1, in); + set_cur_block(geblock); create_if_cascade(env, ltblock, curcases, midcase); create_if_cascade(env, geblock, curcases + midcase, numcases - midcase); @@ -180,36 +187,37 @@ static void find_cond_nodes(ir_node *block, void *ctx) ir_node *defblock = NULL; ifcas_env_t ifcas_env; - if(get_Block_n_cfgpreds(block) != 1) + if (get_Block_n_cfgpreds(block) != 1) return; projx = get_Block_cfgpred(block, 0); - if(!is_Proj(projx)) + if (!is_Proj(projx)) return; assert(get_irn_mode(projx) == mode_X); cond = get_Proj_pred(projx); - if(!is_Cond(cond)) + if (!is_Cond(cond)) return; sel = get_Cond_selector(cond); sel_mode = get_irn_mode(sel); - if(sel_mode == mode_b) /* not a switch? */ + if (sel_mode == mode_b) /* not a switch? */ return; - if(should_do_table_switch(cond, env->spare_size)) + if (should_do_table_switch(cond, env->spare_size)) return; /* * Switch should be transformed into an if cascade. * So first order the cases, so we can do a binary search on them. */ + env->changed = 1; numcases = get_irn_n_outs(cond) - 1; // does not contain default case - cases = obstack_alloc(&env->obst, numcases * sizeof(*cases)); + NEW_ARR_A(case_data_t, cases, numcases); - default_pn = get_Cond_defaultProj(cond); + default_pn = get_Cond_default_proj(cond); ifcas_env.sel = sel; ifcas_env.defindex = 0; NEW_ARR_A(ir_node*, ifcas_env.defusers, numcases); @@ -219,8 +227,7 @@ static void find_cond_nodes(ir_node *block, void *ctx) ir_node *target = get_irn_out(proj, 0); assert(get_Block_n_cfgpreds(target) == 1 && "Encountered critical edge in switch"); - if(pn == default_pn) - { + if (pn == default_pn) { defblock = target; continue; } @@ -239,8 +246,6 @@ static void find_cond_nodes(ir_node *block, void *ctx) /* Connect new default case users */ set_irn_in(defblock, ifcas_env.defindex, ifcas_env.defusers); - - obstack_free(&env->obst, cases); } /** @@ -258,7 +263,7 @@ void lower_switch(ir_graph *irg, unsigned spare_size) current_ir_graph = irg; - obstack_init(&env.obst); + env.changed = 0; env.spare_size = spare_size; remove_critical_cf_edges(irg); @@ -266,14 +271,36 @@ void lower_switch(ir_graph *irg, unsigned spare_size) irg_block_walk_graph(irg, find_cond_nodes, NULL, &env); - if(env.changed) { + if (env.changed) { /* control flow changed */ set_irg_outs_inconsistent(irg); set_irg_doms_inconsistent(irg); set_irg_extblk_inconsistent(irg); set_irg_loopinfo_inconsistent(irg); } - - obstack_free(&env.obst, NULL); current_ir_graph = rem; } + +struct pass_t { + ir_graph_pass_t pass; + unsigned spare_size; +}; + +/** + * Wrapper for running lower_switch() as a pass. + */ +static int pass_wrapper(ir_graph *irg, void *context) { + struct pass_t *pass = context; + + lower_switch(irg, pass->spare_size); + return 0; +} + +/* creates a pass for lower_switch */ +ir_graph_pass_t *lower_switch_pass(const char *name, unsigned spare_size) { + struct pass_t *pass = XMALLOCZ(struct pass_t); + + pass->spare_size = spare_size; + return def_graph_pass_constructor( + &pass->pass, name ? name : "lower_switch", pass_wrapper); +}