X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;ds=sidebyside;f=ir%2Fir%2Firgopt.c;h=2116345fa7d65efabfc5267a6d2ac52771352be2;hb=003979e6f8a15a2e380407134af0092268ce2bbc;hp=e13aff300ba184bce0fec3c1748d8fd450d69d77;hpb=55a613a794cc2fadd5508dcf721c342d70f342cc;p=libfirm diff --git a/ir/ir/irgopt.c b/ir/ir/irgopt.c index e13aff300..2116345fa 100644 --- a/ir/ir/irgopt.c +++ b/ir/ir/irgopt.c @@ -1,9 +1,9 @@ -/* Coyright (C) 1998 - 2000 by Universitaet Karlsruhe -** All rights reserved. -** -** Author: Christian Schaefer -** -** Optimizations for a whole ir graph, i.e., a procedure. +/* Coyright (C) 1998 - 2002 by Universitaet Karlsruhe +* All rights reserved. +* +* Author: Christian Schaefer, Goetz Lindenmaier, Sebastian Felis +* +* Optimizations for a whole ir graph, i.e., a procedure. */ /* $Id$ */ @@ -39,17 +39,20 @@ void add_identities (pset *value_table, ir_node *node); /* apply optimizations of iropt to all nodes. */ /********************************************************************/ -void init_link (ir_node *n, void *env) { +static void init_link (ir_node *n, void *env) { set_irn_link(n, NULL); } -void +static void optimize_in_place_wrapper (ir_node *n, void *env) { int i; - ir_node *optimized; + ir_node *optimized, *old; for (i = 0; i < get_irn_arity(n); i++) { - optimized = optimize_in_place_2(get_irn_n(n, i)); + /* get?irn_n skips Id nodes, so comparison old != optimized does not + show all optimizations. Therefore always set new predecessor. */ + old = get_irn_n(n, i); + optimized = optimize_in_place_2(old); set_irn_n(n, i, optimized); } @@ -89,14 +92,14 @@ local_optimize_graph (ir_graph *irg) { /********************************************************************/ /* Remeber the new node in the old node by using a field all nodes have. */ -INLINE void +static INLINE void set_new_node (ir_node *old, ir_node *new) { old->link = new; } /* Get this new node, before the old node is forgotton.*/ -INLINE ir_node * +static INLINE ir_node * get_new_node (ir_node * n) { return n->link; @@ -108,7 +111,7 @@ get_new_node (ir_node * n) 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 +static INLINE int compute_new_arity(ir_node *b) { int i, res; int irg_v, block_v; @@ -218,7 +221,7 @@ copy_preds (ir_node *n, void *env) { in array contained Bads. Now it's possible. We don't call optimize_in_place as it requires that the fields in ir_graph are set properly. */ - if ((get_opt_control_flow()) && + if ((get_opt_control_flow_straightening()) && (get_Block_n_cfgpreds(nn) == 1) && (get_irn_op(get_Block_cfgpred(nn, 0)) == op_Jmp)) exchange(nn, get_nodes_Block(get_Block_cfgpred(nn, 0))); @@ -253,7 +256,7 @@ copy_preds (ir_node *n, void *env) { /* Copies the graph recursively, compacts the keepalive of the end node. */ static void -copy_graph () { +copy_graph (void) { ir_node *oe, *ne; /* old end, new end */ ir_node *ka; /* keep alive */ int i; @@ -308,8 +311,8 @@ copy_graph () { in current_ir_graph and fixes the environment. Then fixes the fields in current_ir_graph containing nodes of the graph. */ -void -copy_graph_env () { +static void +copy_graph_env (void) { ir_node *old_end; /* Not all nodes remembered in current_ir_graph might be reachable from the end node. Assure their link is set to NULL, so that @@ -410,10 +413,96 @@ dead_node_elimination(ir_graph *irg) { current_ir_graph = rem; } +/* Relink bad predeseccors of a block and store the old in array to the + link field. This function is called by relink_bad_predecessors(). + The array of link field starts with the block operand at position 0. + If block has bad predecessors, create a new in array without bad preds. + Otherwise let in array untouched. */ +static void relink_bad_block_predecessors(ir_node *n, void *env) { + ir_node **new_in, *irn; + int i, new_irn_n, old_irn_arity, new_irn_arity = 0; + + /* if link field of block is NULL, look for bad predecessors otherwise + this is allready done */ + if (get_irn_op(n) == op_Block && + get_irn_link(n) == NULL) { + + /* save old predecessors in link field (position 0 is the block operand)*/ + set_irn_link(n, (void *)get_irn_in(n)); + + /* count predecessors without bad nodes */ + old_irn_arity = get_irn_arity(n); + for (i = 0; i < old_irn_arity; i++) + if (!is_Bad(get_irn_n(n, i))) new_irn_arity++; + + /* arity changing: set new predecessors without bad nodes */ + if (new_irn_arity < old_irn_arity) { + /* get new predecessor array without Block predecessor */ + new_in = NEW_ARR_D (ir_node *, current_ir_graph->obst, (new_irn_arity+1)); + + /* set new predeseccors in array */ + new_in[0] = NULL; + new_irn_n = 1; + for (i = 1; i < old_irn_arity; i++) { + irn = get_irn_n(n, i); + if (!is_Bad(irn)) new_in[new_irn_n++] = irn; + } + n->in = new_in; + } /* ir node has bad predecessors */ + + } /* Block is not relinked */ +} + +/* Relinks Bad predecesors from Bocks and Phis called by walker + remove_bad_predecesors(). If n is a Block, call + relink_bad_block_redecessors(). If n is a Phinode, call also the relinking + function of Phi's Block. If this block has bad predecessors, relink preds + of the Phinode. */ +static void relink_bad_predecessors(ir_node *n, void *env) { + ir_node *block, **old_in; + int i, old_irn_arity, new_irn_arity; + + /* relink bad predeseccors of a block */ + if (get_irn_op(n) == op_Block) + relink_bad_block_predecessors(n, env); + + /* If Phi node relink its block and its predecessors */ + if (get_irn_op(n) == op_Phi) { + + /* Relink predeseccors of phi's block */ + block = get_nodes_Block(n); + if (get_irn_link(block) == NULL) + relink_bad_block_predecessors(block, env); + + old_in = (ir_node **)get_irn_link(block); /* Of Phi's Block */ + old_irn_arity = ARR_LEN(old_in); + + /* Relink Phi predeseccors if count of predeseccors changed */ + if (old_irn_arity != ARR_LEN(get_irn_in(block))) { + /* set new predeseccors in array + n->in[0] remains the same block */ + new_irn_arity = 1; + for(i = 1; i < old_irn_arity; i++) + if (!is_Bad((ir_node *)old_in[i])) n->in[new_irn_arity++] = n->in[i]; + + ARR_SETLEN(ir_node *, n->in, new_irn_arity); + } + + } /* n is a Phi node */ +} + +/* Removes Bad Bad predecesors from Blocks and the corresponding + inputs to Phi nodes as in dead_node_elimination but without + copying the graph. + On walking up set the link field to NULL, on walking down call + relink_bad_predecessors() (This function stores the old in array + to the link field and sets a new in array if arity of predecessors + changes) */ void remove_bad_predecessors(ir_graph *irg) { - printf("remove_bad_predecessors not implemented!!!\n"); + irg_walk_graph(irg, init_link, relink_bad_predecessors, NULL); } + /**********************************************************************/ /* Funcionality for inlining */ /**********************************************************************/ @@ -450,7 +539,7 @@ void inline_method(ir_node *call, ir_graph *called_graph) { type *called_frame; if (!get_optimize() || !get_opt_inline()) return; - /** Turn off optimizations, this can cause problems when allocating new nodes. **/ + /* -- Turn off optimizations, this can cause problems when allocating new nodes. -- */ rem_opt = get_optimize(); set_optimize(0); @@ -461,21 +550,23 @@ void inline_method(ir_node *call, ir_graph *called_graph) { if (get_irg_outs_state(current_ir_graph) == outs_consistent) set_irg_outs_inconsistent(current_ir_graph); - /** Check preconditions **/ + /* -- Check preconditions -- */ assert(get_irn_op(call) == op_Call); - /* @@@ TODO does not work for InterfaceIII.java after cgana + /* @@@ does not work for InterfaceIII.java after cgana assert(get_Call_type(call) == get_entity_type(get_irg_ent(called_graph))); assert(smaller_type(get_entity_type(get_irg_ent(called_graph)), get_Call_type(call))); */ assert(get_type_tpop(get_Call_type(call)) == type_method); - if (called_graph == current_ir_graph) return; - + if (called_graph == current_ir_graph) { + set_optimize(rem_opt); + return; + } - /** Part the Call node into two nodes. Pre_call collects the parameters of + /* -- the procedure and later replaces the Start node of the called graph. Post_call is the old Call node and collects the results of the called - graph. Both will end up being a tuple. **/ + graph. Both will end up being a tuple. -- */ post_bl = get_nodes_Block(call); set_irg_current_block(current_ir_graph, post_bl); /* XxMxPxP of Start + parameter of Call */ @@ -487,12 +578,12 @@ void inline_method(ir_node *call, ir_graph *called_graph) { pre_call = new_Tuple(5, in); post_call = call; - /** Part the block of the Call node into two blocks. + /* -- The new block gets the ins of the old block, pre_call and all its - predecessors and all Phi nodes. **/ + predecessors and all Phi nodes. -- */ part_block(pre_call); - /** Prepare state for dead node elimination **/ + /* -- Prepare state for dead node elimination -- */ /* Visited flags in calling irg must be >= flag in called irg. Else walker and arity computation will not work. */ if (get_irg_visited(current_ir_graph) <= get_irg_visited(called_graph)) @@ -515,7 +606,7 @@ void inline_method(ir_node *call, ir_graph *called_graph) { /* Initialize for compaction of in arrays */ inc_irg_block_visited(current_ir_graph); - /*** Replicate local entities of the called_graph ***/ + /* -- Replicate local entities of the called_graph -- */ /* copy the entities. */ called_frame = get_irg_frame_type(called_graph); for (i = 0; i < get_class_n_members(called_frame); i++) { @@ -530,7 +621,7 @@ void inline_method(ir_node *call, ir_graph *called_graph) { to inline, calling this inline will not visit the inlined nodes. */ set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1); - /** Performing dead node elimination inlines the graph **/ + /* -- Performing dead node elimination inlines the graph -- */ /* Copies the nodes to the obstack of current_ir_graph. Updates links to new entities. */ /* @@@ endless loops are not copied!! -- they should be, I think... */ @@ -542,7 +633,7 @@ void inline_method(ir_node *call, ir_graph *called_graph) { set_irg_block_visited(called_graph, get_irg_block_visited(current_ir_graph)); set_Block_block_visited(get_irg_start_block(called_graph), 0); - /*** Merge the end of the inlined procedure with the call site ***/ + /* -- Merge the end of the inlined procedure with the call site -- */ /* We will turn the old Call node into a Tuple with the following predecessors: -1: Block of Tuple. @@ -553,7 +644,7 @@ void inline_method(ir_node *call, ir_graph *called_graph) { 3: Phi of Exception memories. */ - /** Precompute some values **/ + /* -- Precompute some values -- */ end_bl = get_new_node(get_irg_end_block(called_graph)); end = get_new_node(get_irg_end(called_graph)); arity = get_irn_arity(end_bl); /* arity = n_exc + n_ret */ @@ -564,14 +655,14 @@ void inline_method(ir_node *call, ir_graph *called_graph) { set_irg_current_block(current_ir_graph, post_bl); /* just to make sure */ - /** archive keepalives **/ + /* -- archive keepalives -- */ for (i = 0; i < get_irn_arity(end); i++) add_End_keepalive(get_irg_end(current_ir_graph), get_irn_n(end, i)); /* The new end node will die, but the in array is not on the obstack ... */ free_End(end); - /** Collect control flow from Return blocks to post_calls block. Replace - Return nodes by Jump nodes. **/ +/* -- + Return nodes by Jump nodes. -- */ n_ret = 0; for (i = 0; i < arity; i++) { ir_node *ret; @@ -583,8 +674,8 @@ void inline_method(ir_node *call, ir_graph *called_graph) { } set_irn_in(post_bl, n_ret, cf_pred); - /** Collect results from Return nodes to post_call. Post_call is - turned into a tuple. **/ +/* -- + turned into a tuple. -- */ turn_into_tuple(post_call, 4); /* First the Memory-Phi */ n_ret = 0; @@ -667,12 +758,12 @@ void inline_method(ir_node *call, ir_graph *called_graph) { free(res_pred); free(cf_pred); - /*** Correct the control flow to the end node. +/* -- If the exception control flow from the Call directly branched to the end block we now have the following control flow predecessor pattern: ProjX -> Tuple -> Jmp. We must remove the Jmp along with it's empty block and add Jmp's - predecessors as predecessors of this end block. ***/ + predecessors as predecessors of this end block. -- */ /* find the problematic predecessor of the end block. */ end_bl = get_irg_end_block(current_ir_graph); for (i = 0; i < get_Block_n_cfgpreds(end_bl); i++) { @@ -701,7 +792,7 @@ void inline_method(ir_node *call, ir_graph *called_graph) { free(cf_pred); } - /** Turn cse back on. **/ + /* -- Turn cse back on. -- */ set_optimize(rem_opt); } @@ -727,8 +818,8 @@ static void collect_calls(ir_node *call, void *env) { if (get_irn_op(addr) == op_Const) { /* Check whether the constant is the pointer to a compiled entity. */ tv = get_Const_tarval(addr); - if (tv->u.P.ent) { - called_irg = get_entity_irg(tv->u.P.ent); + if (tarval_to_entity(tv)) { + called_irg = get_entity_irg(tarval_to_entity(tv)); if (called_irg && pos < MAX_INLINE) { /* The Call node calls a locally defined method. Remember to inline. */ calls[pos] = call; @@ -767,11 +858,10 @@ void inline_small_irgs(ir_graph *irg, int size) { /* There are calls to inline */ collect_phiprojs(irg); for (i = 0; i < pos; i++) { - char buf[1024]; tarval *tv; ir_graph *callee; tv = get_Const_tarval(get_Call_ptr(calls[i])); - callee = get_entity_irg(tv->u.P.ent); + callee = get_entity_irg(tarval_to_entity(tv)); if ((_obstack_memory_used(callee->obst) - obstack_room(callee->obst)) < size) { inline_method(calls[i], callee); } @@ -856,7 +946,7 @@ place_floats_early (ir_node *n) Start, Call and end at pinned nodes as Store, Call. Place_early places all floating nodes reachable from its argument through floating nodes and adds all beginnings at pinned nodes to the worklist. */ -INLINE void place_early () { +static INLINE void place_early (void) { assert(worklist); inc_irg_visited(current_ir_graph); @@ -910,7 +1000,7 @@ consumer_dom_dca (ir_node *dca, ir_node *consumer, ir_node *producer) return dca; } -INLINE int get_irn_loop_depth(ir_node *n) { +static INLINE int get_irn_loop_depth(ir_node *n) { return get_loop_depth(get_irn_loop(n)); } @@ -1010,7 +1100,7 @@ place_floats_late (ir_node *n) } } -INLINE void place_late() { +static INLINE void place_late(void) { assert(worklist); inc_irg_visited(current_ir_graph); @@ -1058,10 +1148,13 @@ void place_code(ir_graph *irg) { /* Control flow optimization. */ /* Removes Bad control flow predecessors and empty blocks. A block */ /* is empty if it contains only a Jmp node. */ -/* */ +/* Blocks can only be removed if they are not needed for the */ +/* semantics of Phi nodes. */ /********************************************************************/ - +/* Removes Tuples from Block control flow predecessors. + Optimizes blocks with equivalent_node(). + Replaces n by Bad if n is unreachable control flow. */ static void merge_blocks(ir_node *n, void *env) { int i; set_irn_link(n, NULL); @@ -1069,21 +1162,31 @@ static void merge_blocks(ir_node *n, void *env) { if (get_irn_op(n) == op_Block) { /* Remove Tuples */ for (i = 0; i < get_Block_n_cfgpreds(n); i++) - set_Block_cfgpred(n, i, skip_Tuple(get_Block_cfgpred(n, i))); - } else if (get_irn_mode(n) == mode_X) { + /* GL @@@ : is this possible? if (get_opt_normalize()) -- added, all tests go throug. + A different order of optimizations might cause problems. */ + if (get_opt_normalize()) + set_Block_cfgpred(n, i, skip_Tuple(get_Block_cfgpred(n, i))); + } else if (get_optimize() && (get_irn_mode(n) == mode_X)) { /* We will soon visit a block. Optimize it before visiting! */ ir_node *b = get_nodes_Block(n); ir_node *new = equivalent_node(b); while (irn_not_visited(b) && (!is_Bad(new)) && (new != b)) { - /* We would have to run gigo if new is bad. */ - if (get_optimize() && get_opt_control_flow()) exchange (b, new); + /* We would have to run gigo if new is bad, so we + promote it directly below. */ + assert(((b == new) || get_opt_control_flow_straightening() || get_opt_control_flow_weak_simplification()) && + ("strange flag setting")); + exchange (b, new); b = new; new = equivalent_node(b); } - if (is_Bad(new)) exchange (n, new_Bad()); + /* GL @@@ get_opt_normalize hinzugefuegt, 5.5.2003 */ + if (is_Bad(new) && get_opt_normalize()) exchange (n, new_Bad()); } } +/* Collects all Phi nodes in link list of Block. + Marks all blocks "block_visited" if they contain a node other + than Jmp. */ static void collect_nodes(ir_node *n, void *env) { if (is_no_Block(n)) { ir_node *b = get_nodes_Block(n); @@ -1099,7 +1202,7 @@ static void collect_nodes(ir_node *n, void *env) { } /* Returns true if pred is pred of block */ -int is_pred_of(ir_node *pred, ir_node *b) { +static int is_pred_of(ir_node *pred, ir_node *b) { int i; for (i = 0; i < get_Block_n_cfgpreds(b); i++) { ir_node *b_pred = get_nodes_Block(get_Block_cfgpred(b, i)); @@ -1108,7 +1211,7 @@ int is_pred_of(ir_node *pred, ir_node *b) { return 0; } -int test_whether_dispensable(ir_node *b, int pos) { +static int test_whether_dispensable(ir_node *b, int pos) { int i, j, n_preds = 1; int dispensable = 1; ir_node *cfop = get_Block_cfgpred(b, pos); @@ -1116,7 +1219,7 @@ int test_whether_dispensable(ir_node *b, int pos) { if (get_Block_block_visited(pred) + 1 < get_irg_block_visited(current_ir_graph)) { - if (!get_optimize() || !get_opt_control_flow()) { + if (!get_optimize() || !get_opt_control_flow_strong_simplification()) { /* Mark block so that is will not be removed. */ set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1); return 1; @@ -1156,7 +1259,7 @@ int test_whether_dispensable(ir_node *b, int pos) { return n_preds; } -void optimize_blocks(ir_node *b, void *env) { +static void optimize_blocks(ir_node *b, void *env) { int i, j, k, max_preds, n_preds; ir_node *pred, *phi; ir_node **in; @@ -1169,7 +1272,7 @@ void optimize_blocks(ir_node *b, void *env) { } in = (ir_node **) malloc(max_preds * sizeof(ir_node *)); - /** Debug output ** +/** printf(" working on "); DDMN(b); for (i = 0; i < get_Block_n_cfgpreds(b); i++) { pred = get_nodes_Block(get_Block_cfgpred(b, i)); @@ -1180,7 +1283,7 @@ void optimize_blocks(ir_node *b, void *env) { printf(" removing pred %i ", i); DDMN(pred); } else { printf(" Nothing to do for "); DDMN(pred); } } - ** end Debug output **/ + * end Debug output **/ /** Fix the Phi nodes **/ phi = get_irn_link(b); @@ -1205,15 +1308,18 @@ void optimize_blocks(ir_node *b, void *env) { } n_preds++; } -#if 0 - /* @@@ hier brauche ich schleifeninformation!!! Wenn keine Rueckwaertskante - dann darfs auch keine Verwendung geben. */ + /* The Phi_pred node is replaced now if it is a Phi. + In Schleifen kann offenbar der entfernte Phi Knoten legal verwendet werden. + Daher muss der Phiknoten durch den neuen ersetzt werden. + Weiter muss der alte Phiknoten entfernt werden (durch ersetzen oder + durch einen Bad) damit er aus den keep_alive verschwinden kann. + Man sollte also, falls keine Schleife vorliegt, exchange mit new_Bad + aufrufen. */ if (get_nodes_Block(phi_pred) == pred) { /* remove the Phi as it might be kept alive. Further there might be other users. */ - exchange(phi_pred, phi); /* geht, is aber doch semantisch falsch! */ + exchange(phi_pred, phi); /* geht, ist aber doch semantisch falsch! Warum?? */ } -#endif } else { in[n_preds] = get_Phi_pred(phi, i); n_preds ++; @@ -1221,10 +1327,11 @@ void optimize_blocks(ir_node *b, void *env) { } /* Fix the node */ set_irn_in(phi, n_preds, in); + phi = get_irn_link(phi); } - /** Move Phi nodes from removed blocks to this one. +/** This happens only if merge between loop backedge and single loop entry. **/ for (k = 0; k < get_Block_n_cfgpreds(b); k++) { pred = get_nodes_Block(get_Block_cfgpred(b, k)); @@ -1244,7 +1351,7 @@ void optimize_blocks(ir_node *b, void *env) { < get_irg_block_visited(current_ir_graph)) { /* It's an empty block and not yet visited. */ for (j = 0; j < get_Block_n_cfgpreds(pred); j++) { - /* @@@ Hier brauche ich schleifeninformation!!! Kontrllflusskante + /* @@@ Hier brauche ich Schleifeninformation!!! Kontrollflusskante muss Rueckwaertskante sein! (An allen vier in[n_preds] = phi Anweisungen.) Trotzdem tuts bisher!! */ in[n_preds] = phi; @@ -1315,7 +1422,6 @@ void optimize_cf(ir_graph *irg) { ir_graph *rem = current_ir_graph; current_ir_graph = irg; - /* Handle graph state */ assert(get_irg_phase_state(irg) != phase_building); if (get_irg_outs_state(current_ir_graph) == outs_consistent) @@ -1334,7 +1440,6 @@ void optimize_cf(ir_graph *irg) { for end if useful. */ in = NEW_ARR_F (ir_node *, 1); in[0] = get_nodes_Block(end); - inc_irg_visited(current_ir_graph); for(i = 0; i < get_End_n_keepalives(end); i++) { ir_node *ka = get_End_keepalive(end, i); @@ -1356,3 +1461,50 @@ void optimize_cf(ir_graph *irg) { current_ir_graph = rem; } + + +/** + * Called by walker of remove_critical_cf_edges. + * + * Place an empty block to an edge between a blocks of multiple + * predecessors and a block of multiple sucessors. + * + * @param n IR node + * @param env Envirnment of walker. This field is unused and has + * the value NULL. + */ +static void walk_critical_cf_edges(ir_node *n, void *env) { + int arity, i; + ir_node *pre, *block, **in, *jmp; + + /* Block has multiple predecessors */ + if ((op_Block == get_irn_op(n)) && + (get_irn_arity(n) > 1)) { + arity = get_irn_arity(n); + + for (i=0; iobst, 1); + /* set predecessor of new block */ + in[0] = pre; + block = new_Block(1, in); + /* insert new jmp node to new block */ + switch_block(block); + jmp = new_Jmp(); + switch_block(n); + /* set sucessor of new block */ + set_irn_n(n, i, jmp); + + } /* predecessor has multiple sucessors */ + } /* for all predecessors */ + } /* n is a block */ +} + +void remove_critical_cf_edges(ir_graph *irg) { + if (get_opt_critical_edges()) + irg_walk_graph(irg, NULL, walk_critical_cf_edges, NULL); +}