X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Ftailrec.c;h=57a28f40a5be85e43d79347bc35922d6677de32c;hb=9146b50286358b71f99756e570baf3884709e7ef;hp=509b2abc007b99bcba9987bd3f52c7766d6a464d;hpb=ab68bff54fbae0f22be8ab746156b3e19d97e184;p=libfirm diff --git a/ir/opt/tailrec.c b/ir/opt/tailrec.c index 509b2abc0..57a28f40a 100644 --- a/ir/opt/tailrec.c +++ b/ir/opt/tailrec.c @@ -16,6 +16,7 @@ #include #include "tailrec.h" #include "array.h" +#include "irprog.h" #include "irgwalk.h" #include "irgmod.h" #include "irop.h" @@ -23,15 +24,17 @@ #include "irgraph_t.h" #include "ircons.h" #include "irflag.h" -#include "tv.h" #include "firmstat.h" +static int n_opt_applications = 0; + /** * the environment for colelcting data */ typedef struct _collect_t { ir_node *proj_X; /**< initial exec proj */ ir_node *block; /**< old first block */ + int blk_idx; /**< cfgpred index of the initial exec in block */ ir_node *proj_m; /**< linked list of memory from start proj's */ ir_node *proj_data; /**< linked list of all parameter access proj's */ } collect_t; @@ -45,15 +48,15 @@ static void collect_data(ir_node *node, void *env) ir_node *pred; ir_op *op; - switch (intern_get_irn_opcode(node)) { + switch (get_irn_opcode(node)) { case iro_Proj: pred = get_Proj_pred(node); - op = intern_get_irn_op(pred); + op = get_irn_op(pred); if (op == op_Proj) { ir_node *start = get_Proj_pred(pred); - if (intern_get_irn_op(start) == op_Start) { + 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); @@ -86,7 +89,8 @@ 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->block = node; + data->blk_idx = i; break; } } @@ -120,11 +124,21 @@ static void do_opt_tail_rec(ir_graph *irg, ir_node *rets, int n_tail_calls) assert(n_tail_calls); + /* we add nwe nodes, so the outs are inconsistant */ + set_irg_outs_inconsistent(irg); + + /* we add new blocks and change the control flow */ + set_irg_dom_inconsistent(irg); + + /* we add a new loop */ + set_irg_loopinfo_inconsistent(irg); + set_optimize(0); /* collect needed data */ data.proj_X = NULL; data.block = NULL; + data.blk_idx = -1; data.proj_m = NULL; data.proj_data = NULL; irg_walk_graph(irg, NULL, collect_data, &data); @@ -149,7 +163,7 @@ static void do_opt_tail_rec(ir_graph *irg, ir_node *rets, int n_tail_calls) for (i = 1, p = rets; p; p = get_irn_link(p)) { ir_node *jmp; - switch_block(get_nodes_Block(p)); + set_cur_block(get_nodes_block(p)); jmp = new_Jmp(); exchange(p, new_Bad()); @@ -163,12 +177,7 @@ static void do_opt_tail_rec(ir_graph *irg, ir_node *rets, int n_tail_calls) jmp = new_Jmp(); /* the old first block is now the second one */ - for (i = 0; i < get_Block_n_cfgpreds(data.block); ++i) { - if (get_Block_cfgpred(data.block, i) == data.proj_X) { - set_Block_cfgpred(data.block, i, jmp); - break; - } - } + set_Block_cfgpred(data.block, data.blk_idx, jmp); /* allocate phi's, position 0 contains the memory phi */ NEW_ARR_A(ir_node *, phis, n_params + 1); @@ -182,6 +191,8 @@ static void do_opt_tail_rec(ir_graph *irg, ir_node *rets, int n_tail_calls) in[i] = get_Call_mem(calls); ++i; } + assert(i == n_tail_calls + 1); + phis[0] = new_rd_Phi(NULL, irg, block, n_tail_calls + 1, in, mode_M); /* build the data phi's */ @@ -226,10 +237,10 @@ static void do_opt_tail_rec(ir_graph *irg, ir_node *rets, int n_tail_calls) set_optimize(rem); } -/** +/* * convert simple tail-calls into loops */ -void optimize_tail_rec_irg(ir_graph *irg) +void opt_tail_rec_irg(ir_graph *irg) { ir_node *end_block = irg->end_block; int n_preds; @@ -244,37 +255,30 @@ void optimize_tail_rec_irg(ir_graph *irg) n_preds = get_Block_n_cfgpreds(end_block); for (i = 0; i < n_preds; ++i) { ir_node *ret = get_Block_cfgpred(end_block, i); - ir_node *proj_m, *call, *call_ptr; - tarval *tv; + ir_node *call, *call_ptr; entity *ent; int j, n_ress; ir_node **ress; /* search all returns of a block */ - if (intern_get_irn_op(ret) != op_Return) + if (get_irn_op(ret) != op_Return) continue; /* check, if it's a Return self() */ - proj_m = get_Return_mem(ret); - - if (intern_get_irn_op(proj_m) != op_Proj) - continue; - - call = get_Proj_pred(proj_m); - if (intern_get_irn_op(call) != op_Call) + call = skip_Proj(get_Return_mem(ret)); + if (get_irn_op(call) != op_Call) continue; /* check if it's a recursive call */ call_ptr = get_Call_ptr(call); - if (intern_get_irn_op(call_ptr) != op_Const) + if (get_irn_op(call_ptr) != op_SymConst) continue; - tv = get_Const_tarval(call_ptr); - if (! tarval_is_entity(tv)) + if (get_SymConst_kind(call_ptr) != symconst_addr_ent) continue; - ent = tarval_to_entity(tv); + ent = get_SymConst_entity(call_ptr); if (!ent || get_entity_irg(ent) != irg) continue; @@ -283,23 +287,7 @@ void optimize_tail_rec_irg(ir_graph *irg) ress = get_Return_res_arr(ret); for (j = 0; j < n_ress; ++j) { - ir_node *proj = ress[j]; - ir_node *proj_proj; - ir_node *irn; - - if (intern_get_irn_op(proj) != op_Proj) { - /* not routed to a call */ - break; - } - - proj_proj = get_Proj_pred(proj); - - if (intern_get_irn_op(proj) != op_Proj) { - /* not routed to a call */ - break; - } - - irn = get_Proj_pred(proj_proj); + ir_node *irn = skip_Proj(skip_Proj(ress[j])); if (irn != call) { /* not routed to a call */ @@ -323,20 +311,32 @@ void optimize_tail_rec_irg(ir_graph *irg) if (! n_tail_calls) return; + if (get_opt_tail_recursion_verbose() && get_firm_verbosity() > 1) + printf(" Performing tail recursion for graph %s and %d Calls\n", + get_entity_ld_name(get_irg_entity(irg)), n_tail_calls); + n_opt_applications++; + do_opt_tail_rec(irg, rets, n_tail_calls); } -/** +/* * optimize tail recursion away */ -void optimize_tail_recursion(void) +void opt_tail_recursion(void) { + int i; + if (! get_opt_tail_recursion() || ! get_opt_optimize()) return; + n_opt_applications = 0; + for (i = 0; i < get_irp_n_irgs(); i++) { current_ir_graph = get_irp_irg(i); - optimize_tail_rec_irg(current_ir_graph); + opt_tail_rec_irg(current_ir_graph); } + + if (get_opt_tail_recursion_verbose()) + printf("Performed tail recursion for %d of %d graphs\n", n_opt_applications, get_irp_n_irgs()); }