X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firgopt.c;h=751ad2aa75a8e064c7eb893d2585c8a66c227b66;hb=9924f5a9ff6902ae3c18d5065b13b676bbf25502;hp=f5f26ea53baec6231e4241833e12f4699f5418f4;hpb=6aac20b1633e6f49605084db01f9c7564cb2bf35;p=libfirm diff --git a/ir/ir/irgopt.c b/ir/ir/irgopt.c index f5f26ea53..751ad2aa7 100644 --- a/ir/ir/irgopt.c +++ b/ir/ir/irgopt.c @@ -3,20 +3,32 @@ ** ** Author: Christian Schaefer ** -** dead node elimination -** walks one time through the whole graph and copies it into another graph, -** so unreachable nodes will be lost. +** Optimizations for a whole ir graph, i.e., a procedure. */ +#ifdef HAVE_CONFIG_H +# include +#endif + +# include + # include "irgopt.h" -# include "irnode.h" +# include "irnode_t.h" +# include "irgraph_t.h" # include "iropt.h" # include "irgwalk.h" -# include "irgraph.h" # include "ircons.h" +# include "misc.h" +# include "irgmod.h" + +# include "pset.h" +pset *new_identities (void); +void del_identities (pset *value_table); /********************************************************************/ /* apply optimizations of iropt to all nodes. */ +/********************************************************************/ + void optimize_in_place_wrapper (ir_node *n, void *env) { int i; @@ -30,12 +42,15 @@ optimize_in_place_wrapper (ir_node *n, void *env) { } } - void local_optimize_graph (ir_graph *irg) { ir_graph *rem = current_ir_graph; current_ir_graph = irg; + /* Should we clean the value_table in irg for the cse? Better do so... */ + del_identities(irg->value_table); + irg->value_table = new_identities(); + /* walk over the graph */ irg_walk(irg->end, NULL, optimize_in_place_wrapper, NULL); @@ -45,303 +60,184 @@ local_optimize_graph (ir_graph *irg) { /********************************************************************/ /* Routines for dead node elimination / copying garbage collection */ /* of the obstack. */ +/********************************************************************/ -/* Remeber the new node in the old node, - by using a field that all nodes have. */ -void * +/* Remeber the new node in the old node by using a field all nodes have. */ +inline void set_new_node (ir_node *old, ir_node *new) { - old->in[0] = new; /* Hi Chris: Benutze old->link, ich hab mich vergewissert dass - das hier ueberschrieben werden kann, das erspaart eine - indirektion --> schneller. */ - return old; + old->link = new; } /* Get this new node, before the old node is forgotton.*/ -ir_node * +inline ir_node * get_new_node (ir_node * n) { - ir_node *new; - new = n->in[0]; - assert(new); - - return new; + return n->link; } -/* Create this node on a new obstack. */ -void -copy_node (ir_node *n, void *env) { - ir_node *res = NULL; - ir_node *a = NULL; - ir_node *b = NULL; - int i; - - assert (n); - DDMSG2(n); - if (is_binop(n)) { - a = get_binop_left(n); - b = get_binop_right(n); - } else if (is_unop(n)) { - a = get_unop_op(n); +/* We use the block_visited flag to mark that we have computed the + number of useful predecessors for this block. + Further we encode the new arity in this flag. Remembering the arity is + useful, as it saves a lot of pointer accesses. This function is called + for all Phi and Block nodes in a Block. */ +inline int +compute_new_arity(ir_node *b) { + int i, res; + int irg_v, block_v; + + irg_v = get_irg_block_visited(current_ir_graph); + block_v = get_Block_block_visited(b); + if (block_v >= irg_v) { + /* we computed the number of preds for this block and saved it in the + block_v flag */ + return block_v - irg_v; + } else { + /* compute the number of good predecessors */ + res = get_irn_arity(b); + for (i = 0; i < get_irn_arity(b); i++) + if (get_irn_opcode(get_irn_n(b, i)) == iro_Bad) res--; + /* save it in the flag. */ + set_Block_block_visited(b, irg_v + res); + return res; } +} - switch (get_irn_opcode(n)) { - case iro_Block: - { - ir_node **in = get_Block_cfgpred_arr(n); - for (i = 0; i < get_Block_n_cfgpreds(n); i++) - set_Block_cfgpred(n, i, get_new_node(get_Block_cfgpred(n, i))); - res = new_r_Block (current_ir_graph, get_Block_n_cfgpreds(n), in); +/* Copies the node to the new obstack. The Ins of the new node point to + the predecessors on the old obstack. n->link points to the new node. + For Phi and Block nodes the function allocates in-arrays with an arity + only for useful predecessors. The arity is determined by counting + the non-bad predecessors of the block. */ +inline void +copy_node (ir_node *n, void *env) { + ir_node *nn, *block; + int new_arity; + + if (get_irn_opcode(n) == iro_Block) { + block = NULL; + new_arity = compute_new_arity(n); + } else { + block = get_nodes_Block(n); + if (get_irn_opcode(n) == iro_Phi) { + new_arity = compute_new_arity(block); + } else { + new_arity = get_irn_arity(n); } - break; - case iro_Start: - res = new_r_Start (current_ir_graph, get_new_node(get_nodes_Block(n))); - break; - case iro_End: - res = new_r_End (current_ir_graph, get_new_node(get_nodes_Block(n))); - current_ir_graph -> end = res; - current_ir_graph -> end_block = get_nodes_Block(res); - break; - case iro_Jmp: - res = new_r_Jmp (current_ir_graph, get_new_node(get_nodes_Block(n))); - break; - case iro_Cond: - res = new_r_Cond (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Cond_selector(n))); - break; - case iro_Return: - { - ir_node **in; - in = get_Return_res_arr(n); - for (i = 0; i < get_Return_n_res(n); i++) { - set_Return_res(n, i, get_new_node(get_Return_res(n, i))); + } + nn = new_ir_node(current_ir_graph, + block, + get_irn_op(n), + get_irn_mode(n), + new_arity, + get_irn_in(n)); + /* Copy the attributes. These might point to additional data. If this + was allocated on the old obstack the pointers now are dangling. This + frees e.g. the memory of the graph_arr allocated in new_immBlock. */ + copy_attrs(n, nn); + set_new_node(n, nn); +} + +/* Copies new predecessors of old node to new node remembered in link. + Spare the Bad predecessors of Phi and Block nodes. */ +inline void +copy_preds (ir_node *n, void *env) { + ir_node *nn, *block, *on; + int i, j; + + nn = get_new_node(n); + + if (get_irn_opcode(n) == iro_Block) { + /* Don't copy Bad nodes. */ + j = 0; + for (i = 0; i < get_irn_arity(n); i++) + if (get_irn_opcode(get_irn_n(n, i)) != iro_Bad) { + set_irn_n (nn, j, get_new_node(get_irn_n(n, i))); + j++; } - res = new_r_Return (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Return_mem(n)), - get_Return_n_res(n), in); - } - break; - case iro_Raise: - res = new_r_Raise (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Raise_mem(n)), - get_new_node(get_Raise_exo_ptr(n))); - break; - case iro_Const: - res = new_r_Const (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_irn_mode(n), get_Const_tarval(n)); - break; - case iro_SymConst: - { - type_or_id *value = NULL; - - if ((get_SymConst_kind(n)==type_tag) || (get_SymConst_kind(n)==size)) - { - - value = (type_or_id *) get_SymConst_type(n); - } - else - { - if (get_SymConst_kind(n)==linkage_ptr_info) - { - value = (type_or_id *) get_SymConst_ptrinfo(n); - } - } - res = new_r_SymConst (current_ir_graph, get_new_node(get_nodes_Block(n)), - value, get_SymConst_kind (n)); - } - break; - case iro_Sel: - { - ir_node **in = get_Sel_index_arr(n); - for (i = 0; i < get_Sel_n_index(n); i++) - set_Sel_index(n, i, get_new_node(get_Sel_index(n, i))); - res = new_r_Sel (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Sel_mem(n)), - get_new_node(get_Sel_ptr(n)), get_Sel_n_index(n), - in, get_Sel_entity(n)); - } - break; - case iro_Call: - { - ir_node **in = get_Call_param_arr(n); - for (i = 0; i < get_Call_arity(n); i++) - set_Call_param(n, i, get_new_node(get_Call_param(n, i))); - res = new_r_Call (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Call_mem(n)), - get_new_node(get_Call_ptr(n)), get_Call_arity(n), - in, get_Call_type (n)); - } - break; - case iro_Add: - res = new_r_Add (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(a), get_new_node(b), get_irn_mode(n)); - break; - case iro_Sub: - { - res = new_r_Sub (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(a), get_new_node(b), get_irn_mode(n)); - } - break; - case iro_Minus: - res = new_r_Minus (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(a), get_irn_mode(n)); - break; - case iro_Mul: - res = new_r_Mul (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(a), get_new_node(b), get_irn_mode(n)); - break; - case iro_Quot: - res = new_r_Quot (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Quot_mem(n)), get_new_node(a), - get_new_node(b)); - break; - case iro_DivMod: - res = new_r_DivMod (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_DivMod_mem(n)), get_new_node(a), - get_new_node(b)); - break; - case iro_Div: - res = new_r_Div (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Div_mem(n)), get_new_node(a), - get_new_node(b)); - break; - case iro_Mod: - res = new_r_Mod (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Mod_mem(n)), get_new_node(a), - get_new_node(b)); - break; - case iro_Abs: - res = new_r_Abs (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Abs_op(n)), get_irn_mode(n)); - break; - case iro_And: - res = new_r_And (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(a), get_new_node(b), get_irn_mode(n)); - break; - case iro_Or: - res = new_r_Or (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(a), get_new_node(b), get_irn_mode(n)); - break; - case iro_Eor: - res = new_r_Eor (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(a), get_new_node(b), get_irn_mode(n)); - break; - case iro_Not: - res = new_r_Not (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Not_op(n)), get_irn_mode(n)); - break; - case iro_Cmp: - res = new_r_Cmp (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Cmp_left(n)), - get_new_node(get_Cmp_right(n))); - break; - case iro_Shl: - res = new_r_Shl (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Shl_left(n)), - get_new_node(get_Shl_right(n)), get_irn_mode(n)); - break; - case iro_Shr: - res = new_r_Shr (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Shr_left(n)), - get_new_node(get_Shr_right(n)), get_irn_mode(n)); - break; - case iro_Shrs: - res = new_r_Shrs (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Shrs_left(n)), - get_new_node(get_Shrs_right(n)), get_irn_mode(n)); - break; - case iro_Rot: - res = new_r_Rot (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Rot_left(n)), - get_new_node(get_Rot_right(n)), get_irn_mode(n)); - break; - case iro_Conv: - res = new_r_Conv (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Conv_op(n)), - get_irn_mode(n)); - break; - case iro_Phi: - { - ir_node **in = get_Phi_preds_arr(n); - for (i = 0; i < get_Phi_n_preds(n); i++) - set_Phi_pred(n, i, get_new_node(get_Phi_pred(n, i))); - res = new_r_Phi (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_Phi_n_preds(n), in, get_irn_mode(n)); - } - break; - case iro_Load: - res = new_r_Load (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Load_mem(n)), - get_new_node(get_Load_ptr(n))); - break; - case iro_Store: - res = new_r_Store (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Store_mem(n)), - get_new_node(get_Store_ptr(n)), - get_new_node(get_Store_value(n))); - break; - case iro_Alloc: - res = new_r_Alloc (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Alloc_mem(n)), - get_new_node(get_Alloc_size(n)), - get_Alloc_type(n), get_Alloc_where(n)); - - break; - case iro_Free: - res = new_r_Free (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Free_mem(n)), - get_new_node(get_Free_ptr(n)), - get_new_node(get_Free_size(n)), get_Free_type(n)); - break; - case iro_Sync: - { - ir_node **in = get_Sync_preds_arr(n); - for (i = 0; i < get_Sync_n_preds(n); i++) - set_Sync_pred(n, i, get_new_node(get_Sync_pred(n, i))); - res = new_r_Sync (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_Sync_n_preds(n), in); - } - break; - case iro_Proj: - res = new_r_Proj (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Proj_pred(n)), get_irn_mode(n), - get_Proj_proj(n)); - break; - case iro_Tuple: - { - ir_node **in = get_Tuple_preds_arr(n); - for (i = 0; i < get_Tuple_n_preds(n); i++) - set_Tuple_pred(n, i, get_new_node(get_Tuple_pred(n, i))); - res = new_r_Tuple (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_Tuple_n_preds(n), in); - } - break; - case iro_Id: - res = new_r_Id (current_ir_graph, get_new_node(get_nodes_Block(n)), - get_new_node(get_Id_pred(n)), get_irn_mode(n)); - break; - case iro_Bad: - res = new_r_Bad (); - break; + /* repair the block visited flag from above misuse */ + set_Block_block_visited(nn, 0); + /* Local optimization could not merge two subsequent blocks if + in array contained Bads. Now it's possible, but don't do it for + the end block! */ + if (n != current_ir_graph->end_block) on = optimize_in_place(nn); + else on = nn; + if (nn != on) exchange(nn, on); + } else if (get_irn_opcode(n) == iro_Phi) { + /* Don't copy node if corresponding predecessor in block is Bad. + The Block itself should not be Bad. */ + block = get_nodes_Block(n); + set_irn_n (nn, -1, get_new_node(block)); + j = 0; + for (i = 0; i < get_irn_arity(n); i++) + if (get_irn_opcode(get_irn_n(block, i)) != iro_Bad) { + set_irn_n (nn, j, get_new_node(get_irn_n(n, i))); + j++; + } + /* Compacting the Phi's ins might generate Phis with only one + predecessor. */ + if (get_irn_arity(n) == 1) + exchange(n, get_irn_n(n, 0)); + } else { + for (i = -1; i < get_irn_arity(n); i++) + set_irn_n (nn, i, get_new_node(get_irn_n(n, i))); } - /* @@@ Here we could call optimize()!! */ - set_new_node(n, res); +} - printf(" "); DDMSG2(res); +/* Copies the graph reachable from current_ir_graph->end to the obstack + in current_ir_graph. + Then fixes the fields in current_ir_graph containing nodes of the + graph. */ +void +copy_graph () { + /* Not all nodes remembered in current_ir_graph might be reachable + from the end node. Assure their link is set to NULL so that + we can test whether new nodes have been computed. */ + set_irn_link(get_irg_frame (current_ir_graph), NULL); + set_irn_link(get_irg_globals(current_ir_graph), NULL); + set_irn_link(get_irg_args (current_ir_graph), NULL); + + /* we use the block walk flag for removing Bads from Blocks ins. */ + inc_irg_block_visited(current_ir_graph); + + /* copy the graph */ + irg_walk(get_irg_end(current_ir_graph), copy_node, copy_preds, NULL); + + /* fix the fields in current_ir_graph */ + set_irg_end (current_ir_graph, get_new_node(get_irg_end(current_ir_graph))); + set_irg_end_block (current_ir_graph, get_new_node(get_irg_end_block(current_ir_graph))); + if (get_irn_link(get_irg_frame(current_ir_graph)) == NULL) + irg_walk(get_irg_frame(current_ir_graph), copy_node, copy_preds, NULL); + if (get_irn_link(get_irg_globals(current_ir_graph)) == NULL) + irg_walk(get_irg_globals(current_ir_graph), copy_node, copy_preds, NULL); + if (get_irn_link(get_irg_args(current_ir_graph)) == NULL) + irg_walk(get_irg_args(current_ir_graph), copy_node, copy_preds, NULL); + set_irg_start (current_ir_graph, get_new_node(get_irg_start(current_ir_graph))); + set_irg_start_block(current_ir_graph, + get_new_node(get_irg_start_block(current_ir_graph))); + set_irg_frame (current_ir_graph, get_new_node(get_irg_frame(current_ir_graph))); + set_irg_globals(current_ir_graph, get_new_node(get_irg_globals(current_ir_graph))); + set_irg_args (current_ir_graph, get_new_node(get_irg_args(current_ir_graph))); + if (get_irn_link(get_irg_bad(current_ir_graph)) == NULL) { + copy_node(get_irg_bad(current_ir_graph), NULL); + copy_preds(get_irg_bad(current_ir_graph), NULL); + } + set_irg_bad(current_ir_graph, get_new_node(get_irg_bad(current_ir_graph))); } +/* Amroq call this emigrate() */ void dead_node_elimination(ir_graph *irg) { - struct obstack *graveyard_obst=NULL; - struct obstack *rebirth_obst; + ir_graph *rem; + struct obstack *graveyard_obst = NULL; + struct obstack *rebirth_obst = NULL; - ir_node *old_node, *new_node; - ir_graph *rem = current_ir_graph; + /* Remember external state of current_ir_graph. */ + rem = current_ir_graph; current_ir_graph = irg; - if (get_opt_dead_node_elimination()) { + if (get_optimize() && get_opt_dead_node_elimination()) { /* A quiet place, where the old obstack can rest in peace, until it will be cremated. */ @@ -352,64 +248,12 @@ dead_node_elimination(ir_graph *irg) { current_ir_graph->obst = rebirth_obst; obstack_init (current_ir_graph->obst); - /*CS*/ - printf("Before starting the DEAD NODE ELIMINATION !\n"); - - /* Copy nodes remembered in irg fields first. - The optimization contains tests against these fields, e.g., not - to optimize the start block away. Therefore these fields have to - be fixed first. - Further setting these fields in copy_node would impose additional - tests for all nodes of a kind. - Predict the visited flag the walker will use! */ - /* Copy the start Block node */ - old_node = irg->start_block; - new_node = new_r_Block (current_ir_graph, 0, NULL); /* new_r_Block calls - no optimization --> save */ - irg->start_block = new_node; - set_new_node (old_node, new_node); - set_irn_visited (new_node, get_irg_visited(current_ir_graph)+1); - /* Copy the Start node */ - old_node = irg->start; - new_node = new_r_Start (current_ir_graph, irg->start_block); - irg->start = new_node; - DDMSG2(new_node); - set_new_node (old_node, new_node); - set_irn_visited (new_node, get_irg_visited(current_ir_graph)+1); - /* Copy the Bad node */ - old_node = irg->bad; - new_node = new_ir_node (irg, irg->start_block, op_Bad, mode_T, 0, NULL); - irg->bad = new_node; - set_new_node (old_node, new_node); - set_irn_visited (new_node, get_irg_visited(current_ir_graph)+1); - /* Copy the Projs for the Start's results. */ - old_node = irg->frame; - new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_p, pns_frame_base); - irg->frame = new_node; - set_new_node (old_node, new_node); - set_irn_visited (new_node, get_irg_visited(current_ir_graph)+1); - - old_node = irg->globals; - new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_p, pns_globals); - irg->globals = new_node; - set_new_node (old_node, new_node); - set_irn_visited (new_node, get_irg_visited(current_ir_graph)+1); - - old_node = irg->args; - new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_T, pns_args); - irg->args = new_node; - set_new_node (old_node, new_node); - set_irn_visited (new_node, get_irg_visited(current_ir_graph)+1); - - /* Walks the graph once, and at the recursive way do the copy thing. - all reachable nodes will be copied to a new obstack. */ - irg_walk(irg->end, NULL, copy_node, NULL); - - /*CS*/ - printf("After the DEAD NODE ELIMINATION !\n"); + /* Copy the graph from the old to the new obstack */ + copy_graph(); /* Free memory from old unoptimized obstack */ - xfree (graveyard_obst); + obstack_free(graveyard_obst, 0); /* First empty the obstack ... */ + xfree (graveyard_obst); /* ... then free it. */ } current_ir_graph = rem;