X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Ftailrec.c;h=9e305d435ef637031a3af757b0330f60689cae0d;hb=153ed01cac8be211f278b6b7c319681c12a97c54;hp=7666bd8224b8b894ec832620b325cb70aaa7e376;hpb=ec02f60f3decb373023d411a2acf9222d5f5867f;p=libfirm diff --git a/ir/opt/tailrec.c b/ir/opt/tailrec.c index 7666bd822..9e305d435 100644 --- a/ir/opt/tailrec.c +++ b/ir/opt/tailrec.c @@ -26,7 +26,7 @@ #include #include "tailrec.h" #include "array.h" -#include "irprog.h" +#include "irprog_t.h" #include "irgwalk.h" #include "irgmod.h" #include "irop.h" @@ -36,6 +36,8 @@ #include "irflag.h" #include "trouts.h" #include "return.h" +#include "scalar_replace.h" +#include "irouts.h" #include "irhooks.h" /** @@ -67,11 +69,11 @@ static void collect_data(ir_node *node, void *env) ir_node *start = get_Proj_pred(pred); if (get_irn_op(start) == op_Start) { - if (get_Proj_proj(pred) == pn_Start_T_args) { - /* found Proj(ProjT(Start)) */ - set_irn_link(node, data->proj_data); - data->proj_data = node; - } + if (get_Proj_proj(pred) == pn_Start_T_args) { + /* found Proj(ProjT(Start)) */ + set_irn_link(node, data->proj_data); + data->proj_data = node; + } } } else if (op == op_Start) { @@ -98,11 +100,11 @@ static void collect_data(ir_node *node, void *env) */ if (node != current_ir_graph->start_block) { for (i = 0; i < n_pred; ++i) { - if (get_Block_cfgpred(node, i) == data->proj_X) { - data->block = node; - data->blk_idx = i; - break; - } + if (get_Block_cfgpred(node, i) == data->proj_X) { + data->block = node; + data->blk_idx = i; + break; + } } } break; @@ -129,9 +131,9 @@ static void do_opt_tail_rec(ir_graph *irg, ir_node *rets, int n_tail_calls) ir_node *p; int i, j, n_params; collect_t data; - int rem = get_optimize(); - entity *ent = get_irg_entity(irg); - type *method_tp = get_entity_type(ent); + int rem = get_optimize(); + entity *ent = get_irg_entity(irg); + ir_type *method_tp = get_entity_type(ent); assert(n_tail_calls); @@ -139,7 +141,7 @@ static void do_opt_tail_rec(ir_graph *irg, ir_node *rets, int n_tail_calls) set_irg_outs_inconsistent(irg); /* we add new blocks and change the control flow */ - set_irg_dom_inconsistent(irg); + set_irg_doms_inconsistent(irg); /* we add a new loop */ set_irg_loopinfo_inconsistent(irg); @@ -228,7 +230,7 @@ static void do_opt_tail_rec(ir_graph *irg, ir_node *rets, int n_tail_calls) in[0] = new_r_Proj(irg, block, irg->args, mode, i); for (j = 0; j < n_tail_calls; ++j) - in[j + 1] = call_params[j][i]; + in[j + 1] = call_params[j][i]; phis[i + 1] = new_r_Phi(irg, block, n_tail_calls + 1, in, mode); } @@ -249,7 +251,7 @@ static void do_opt_tail_rec(ir_graph *irg, ir_node *rets, int n_tail_calls) } /* tail recursion was done, all info is invalid */ - set_irg_dom_inconsistent(irg); + set_irg_doms_inconsistent(irg); set_irg_outs_inconsistent(irg); set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_inconsistent); set_trouts_inconsistent(); @@ -258,20 +260,48 @@ static void do_opt_tail_rec(ir_graph *irg, ir_node *rets, int n_tail_calls) set_optimize(rem); } +/** + * Check the lifetime of locals in the given graph. + * Tail recursion can only be done, if we can prove that + * the lifetime of locals end with the recursive call. + * We do this by checking that no address of a local variable is + * stored or transmitted as an argument to a call. + * + * @return non-zero if it's ok to do tail recursion + */ +static int check_lifetime_of_locals(ir_graph *irg) +{ + ir_node *irg_frame = get_irg_frame(irg); + int i; + + if (get_irg_outs_state(irg) != outs_consistent) + compute_irg_outs(irg); + + for (i = get_irn_n_outs(irg_frame) - 1; i >= 0; --i) { + ir_node *succ = get_irn_out(irg_frame, i); + + if (get_irn_op(succ) == op_Sel && is_address_taken(succ)) + return 0; + } + return 1; +} + /* * convert simple tail-calls into loops */ int opt_tail_rec_irg(ir_graph *irg) { ir_node *end_block; - int n_preds; int i, n_tail_calls = 0; ir_node *rets = NULL; - type *mtd_type, *call_type; + ir_type *mtd_type, *call_type; if (! get_opt_tail_recursion() || ! get_opt_optimize()) return 0; + if (! check_lifetime_of_locals(irg)) + return 0; + /* * This tail recursion optimization works best * if the Returns are normalized. @@ -281,12 +311,11 @@ int opt_tail_rec_irg(ir_graph *irg) end_block = get_irg_end_block(irg); set_irn_link(end_block, NULL); - n_preds = get_Block_n_cfgpreds(end_block); - for (i = 0; i < n_preds; ++i) { + for (i = get_Block_n_cfgpreds(end_block) - 1; i >= 0; --i) { ir_node *ret = get_Block_cfgpred(end_block, i); ir_node *call, *call_ptr; entity *ent; - int j, n_ress; + int j; ir_node **ress; /* search all returns of a block */ @@ -312,18 +341,16 @@ int opt_tail_rec_irg(ir_graph *irg) continue; /* ok, mem is routed to a recursive call, check return args */ - n_ress = get_Return_n_ress(ret); ress = get_Return_res_arr(ret); - - for (j = 0; j < n_ress; ++j) { + for (j = get_Return_n_ress(ret) - 1; j >= 0; --j) { ir_node *irn = skip_Proj(skip_Proj(ress[j])); if (irn != call) { - /* not routed to a call */ - break; + /* not routed to a call */ + break; } } - if (j < n_ress) + if (j >= 0) continue; /* @@ -336,7 +363,7 @@ int opt_tail_rec_irg(ir_graph *irg) if (mtd_type != call_type) { /* * Hmm, the types did not match, bad. - * This can happen in C when no prototyp is given + * This can happen in C when no prototype is given * or K&R style is used. */ #if 0 @@ -378,14 +405,15 @@ void opt_tail_recursion(void) { int i; int n_opt_applications = 0; + ir_graph *irg; if (! get_opt_tail_recursion() || ! get_opt_optimize()) return; - for (i = 0; i < get_irp_n_irgs(); i++) { - current_ir_graph = get_irp_irg(i); + for (i = get_irp_n_irgs() - 1; i >= 0; --i) { + irg = get_irp_irg(i); - if (opt_tail_rec_irg(current_ir_graph)) + if (opt_tail_rec_irg(irg)) ++n_opt_applications; }