X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firgopt.c;h=200dfdbf28c232398d1a95c382b33f965b28db0b;hb=fba3706965dd1f7e0cd8fc13a79a608966ca2527;hp=695abca7eb7e4f3aaae7ddea225b4ce4c1053163;hpb=de783051855281a9fbc4ff617911cc55574ef3c9;p=libfirm diff --git a/ir/ir/irgopt.c b/ir/ir/irgopt.c index 695abca7e..200dfdbf2 100644 --- a/ir/ir/irgopt.c +++ b/ir/ir/irgopt.c @@ -1,18 +1,22 @@ -/* Coyright (C) 1998 - 2000 by Universitaet Karlsruhe -** All rights reserved. -** -** Author: Christian Schaefer -** -** Optimizations for a whole ir graph, i.e., a procedure. -*/ +/* + * Project: libFIRM + * File name: ir/ir/irgopt.c + * Purpose: Optimizations for a whole ir graph, i.e., a procedure. + * Author: Christian Schaefer, Goetz Lindenmaier + * Modified by: Sebastian Felis + * Created: + * CVS-ID: $Id$ + * Copyright: (c) 1998-2003 Universität Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ -/* $Id$ */ #ifdef HAVE_CONFIG_H # include #endif # include +# include # include "irprog.h" # include "irgopt.h" @@ -21,12 +25,13 @@ # include "iropt_t.h" # include "irgwalk.h" # include "ircons.h" -# include "misc.h" # include "irgmod.h" # include "array.h" # include "pset.h" # include "pdeq.h" /* Fuer code placement */ # include "irouts.h" +# include "irloop.h" +# include "irbackedge_t.h" /* Defined in iropt.c */ pset *new_identities (void); @@ -37,17 +42,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); } @@ -87,14 +95,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; @@ -106,7 +114,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; @@ -128,13 +136,29 @@ compute_new_arity(ir_node *b) { } } +static INLINE void new_backedge_info(ir_node *n) { + switch(get_irn_opcode(n)) { + case iro_Block: + n->attr.block.cg_backedge = NULL; + n->attr.block.backedge = new_backedge_arr(current_ir_graph->obst, get_irn_arity(n)); + break; + case iro_Phi: + n->attr.phi_backedge = new_backedge_arr(current_ir_graph->obst, get_irn_arity(n)); + break; + case iro_Filter: + n->attr.filter.backedge = new_backedge_arr(current_ir_graph->obst, get_irn_arity(n)); + break; + default: ; + } +} + /* Copies the node to the new obstack. The Ins of the new node point to the predecessors on the old obstack. For block/phi nodes not all predecessors might be copied. 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. */ -void +static void copy_node (ir_node *n, void *env) { ir_node *nn, *block; int new_arity; @@ -142,6 +166,7 @@ copy_node (ir_node *n, void *env) { if (get_irn_opcode(n) == iro_Block) { block = NULL; new_arity = compute_new_arity(n); + n->attr.block.graph_arr = NULL; } else { block = get_nodes_Block(n); if (get_irn_opcode(n) == iro_Phi) { @@ -161,6 +186,7 @@ copy_node (ir_node *n, void *env) { 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); + new_backedge_info(nn); set_new_node(n, nn); /* printf("\n old node: "); DDMSG2(n); @@ -170,7 +196,7 @@ copy_node (ir_node *n, void *env) { /* Copies new predecessors of old node to new node remembered in link. Spare the Bad predecessors of Phi and Block nodes. */ -void +static void copy_preds (ir_node *n, void *env) { ir_node *nn, *block; int i, j; @@ -187,6 +213,7 @@ copy_preds (ir_node *n, void *env) { 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))); + /*if (is_backedge(n, i)) set_backedge(nn, j);*/ j++; } /* repair the block visited flag from above misuse. Repair it in both @@ -197,7 +224,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))); @@ -210,6 +237,7 @@ copy_preds (ir_node *n, void *env) { 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))); + /*if (is_backedge(n, i)) set_backedge(nn, j);*/ j++; } /* If the pre walker reached this Phi after the post walker visited the @@ -230,8 +258,8 @@ copy_preds (ir_node *n, void *env) { } /* Copies the graph recursively, compacts the keepalive of the end node. */ -void -copy_graph () { +static void +copy_graph (void) { ir_node *oe, *ne; /* old end, new end */ ir_node *ka; /* keep alive */ int i; @@ -286,8 +314,9 @@ 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 we can test whether new nodes have been computed. */ @@ -302,8 +331,9 @@ copy_graph_env () { copy_graph(); /* fix the fields in current_ir_graph */ - free_End(get_irg_end(current_ir_graph)); - set_irg_end (current_ir_graph, get_new_node(get_irg_end(current_ir_graph))); + old_end = get_irg_end(current_ir_graph); + set_irg_end (current_ir_graph, get_new_node(old_end)); + free_End(old_end); 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) { copy_node (get_irg_frame(current_ir_graph), NULL); @@ -357,6 +387,9 @@ dead_node_elimination(ir_graph *irg) { assert(get_irg_phase_state(current_ir_graph) != phase_building); free_outs(current_ir_graph); + /* @@@ so far we loose loops when copying */ + set_irg_loop(current_ir_graph, NULL); + if (get_optimize() && get_opt_dead_node_elimination()) { /* A quiet place, where the old obstack can rest in peace, @@ -383,6 +416,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) { + irg_walk_graph(irg, init_link, relink_bad_predecessors, NULL); +} + + /**********************************************************************/ /* Funcionality for inlining */ /**********************************************************************/ @@ -391,7 +514,7 @@ dead_node_elimination(ir_graph *irg) { then updates the entity if it's a local one. env must be a pointer to the frame type of the procedure. The new entities must be in the link field of the entities. */ -void +static INLINE void copy_node_inline (ir_node *n, void *env) { ir_node *new; type *frame_tp = (type *)env; @@ -419,7 +542,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); @@ -430,22 +553,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); - /* assert(get_Call_type(call) == get_entity_type(get_irg_ent(called_graph))); */ - /* - @@@ TODO does not work for InterfaceIII.java after cgana - assert(smaller_type(get_entity_type(get_irg_ent(called_graph)), - get_Call_type(call))); + /* @@@ 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. **/ + /* -- + 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. -- */ post_bl = get_nodes_Block(call); set_irg_current_block(current_ir_graph, post_bl); /* XxMxPxP of Start + parameter of Call */ @@ -457,16 +581,16 @@ 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)) - set_irg_visited(current_ir_graph, get_irg_visited(called_graph)+1); /***/ + set_irg_visited(current_ir_graph, get_irg_visited(called_graph)+1); if (get_irg_block_visited(current_ir_graph)< get_irg_block_visited(called_graph)) set_irg_block_visited(current_ir_graph, get_irg_block_visited(called_graph)); /* Set pre_call as new Start node in link field of the start node of @@ -476,16 +600,16 @@ void inline_method(ir_node *call, ir_graph *called_graph) { copying. */ set_irn_link(get_irg_start(called_graph), pre_call); set_irn_visited(get_irg_start(called_graph), - get_irg_visited(current_ir_graph));/***/ + get_irg_visited(current_ir_graph)); set_irn_link(get_irg_start_block(called_graph), - get_nodes_Block(pre_call)); + get_nodes_Block(pre_call)); set_irn_visited(get_irg_start_block(called_graph), - get_irg_visited(current_ir_graph)); /***/ + get_irg_visited(current_ir_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++) { @@ -500,10 +624,10 @@ 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!! */ + /* @@@ endless loops are not copied!! -- they should be, I think... */ irg_walk(get_irg_end(called_graph), copy_node_inline, copy_preds, get_irg_frame_type(called_graph)); @@ -512,7 +636,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. @@ -523,7 +647,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 */ @@ -534,14 +658,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; @@ -553,8 +677,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; @@ -567,8 +691,11 @@ void inline_method(ir_node *call, ir_graph *called_graph) { } phi = new_Phi(n_ret, cf_pred, mode_M); set_Tuple_pred(call, 0, phi); - set_irn_link(phi, get_irn_link(post_bl)); /* Conserve Phi-list for further inlinings */ - set_irn_link(post_bl, phi); + /* Conserve Phi-list for further inlinings -- but might be optimized */ + if (get_nodes_Block(phi) == post_bl) { + set_irn_link(phi, get_irn_link(post_bl)); + set_irn_link(post_bl, phi); + } /* Now the real results */ if (n_res > 0) { for (j = 0; j < n_res; j++) { @@ -582,8 +709,11 @@ void inline_method(ir_node *call, ir_graph *called_graph) { } phi = new_Phi(n_ret, cf_pred, get_irn_mode(cf_pred[0])); res_pred[j] = phi; - set_irn_link(phi, get_irn_link(post_bl)); /* Conserve Phi-list for further inlinings */ - set_irn_link(post_bl, phi); + /* Conserve Phi-list for further inlinings -- but might be optimized */ + if (get_nodes_Block(phi) == post_bl) { + set_irn_link(phi, get_irn_link(post_bl)); + set_irn_link(post_bl, phi); + } } set_Tuple_pred(call, 2, new_Tuple(n_res, res_pred)); } else { @@ -604,7 +734,7 @@ void inline_method(ir_node *call, ir_graph *called_graph) { } } if (n_exc > 0) { - new_Block(n_exc, cf_pred); /* whatch it: current_block is changed! */ + new_Block(n_exc, cf_pred); /* watch it: current_block is changed! */ set_Tuple_pred(call, 1, new_Jmp()); /* The Phi for the memories with the exception objects */ n_exc = 0; @@ -631,41 +761,44 @@ 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. ***/ - /* 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++) { - cf_op = get_Block_cfgpred(end_bl, i); - if (get_irn_op(cf_op) == op_Proj) { - cf_op = get_Proj_pred(cf_op); - if (get_irn_op(cf_op) == op_Tuple) { - cf_op = get_Tuple_pred(cf_op, 1); - assert(get_irn_op(cf_op) == op_Jmp); - break; + if (n_exc > 0) { + /* -- If the exception control flow from the inlined 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. No problem if + there is no exception, because then branches Bad to End which + is fine. -- */ + /* 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++) { + cf_op = get_Block_cfgpred(end_bl, i); + if (get_irn_op(cf_op) == op_Proj) { + cf_op = get_Proj_pred(cf_op); + if (get_irn_op(cf_op) == op_Tuple) { + cf_op = get_Tuple_pred(cf_op, 1); + assert(get_irn_op(cf_op) == op_Jmp); + break; + } } } - } - /* repair */ - if (i < get_Block_n_cfgpreds(end_bl)) { - bl = get_nodes_Block(cf_op); - arity = get_Block_n_cfgpreds(end_bl) + get_Block_n_cfgpreds(bl) - 1; - cf_pred = (ir_node **) malloc (arity * sizeof (ir_node *)); - for (j = 0; j < i; j++) - cf_pred[j] = get_Block_cfgpred(end_bl, j); - for (j = j; j < i + get_Block_n_cfgpreds(bl); j++) - cf_pred[j] = get_Block_cfgpred(bl, j-i); - for (j = j; j < arity; j++) - cf_pred[j] = get_Block_cfgpred(end_bl, j-get_Block_n_cfgpreds(bl) +1); - set_irn_in(end_bl, arity, cf_pred); - free(cf_pred); + /* repair */ + if (i < get_Block_n_cfgpreds(end_bl)) { + bl = get_nodes_Block(cf_op); + arity = get_Block_n_cfgpreds(end_bl) + get_Block_n_cfgpreds(bl) - 1; + cf_pred = (ir_node **) malloc (arity * sizeof (ir_node *)); + for (j = 0; j < i; j++) + cf_pred[j] = get_Block_cfgpred(end_bl, j); + for (j = j; j < i + get_Block_n_cfgpreds(bl); j++) + cf_pred[j] = get_Block_cfgpred(bl, j-i); + for (j = j; j < arity; j++) + cf_pred[j] = get_Block_cfgpred(end_bl, j-get_Block_n_cfgpreds(bl) +1); + set_irn_in(end_bl, arity, cf_pred); + free(cf_pred); + } } - /** Turn cse back on. **/ + /* -- Turn cse back on. -- */ set_optimize(rem_opt); } @@ -691,8 +824,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; @@ -702,7 +835,6 @@ static void collect_calls(ir_node *call, void *env) { } } - /* Inlines all small methods at call sites where the called address comes from a Const node that references the entity representing the called method. @@ -716,8 +848,6 @@ void inline_small_irgs(ir_graph *irg, int size) { if (!(get_optimize() && get_opt_inline())) return; - /*DDME(get_irg_ent(current_ir_graph));*/ - current_ir_graph = irg; /* Handle graph state */ assert(get_irg_phase_state(current_ir_graph) != phase_building); @@ -737,9 +867,8 @@ void inline_small_irgs(ir_graph *irg, int size) { 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) { - /*printf(" inlineing "); DDME(tv->u.p.ent);*/ inline_method(calls[i], callee); } } @@ -823,7 +952,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); @@ -877,28 +1006,41 @@ consumer_dom_dca (ir_node *dca, ir_node *consumer, ir_node *producer) return dca; } -#if 0 -/* @@@ Needs loop informations. Will implement later interprocedural. */ +static INLINE int get_irn_loop_depth(ir_node *n) { + return get_loop_depth(get_irn_loop(n)); +} + +/* Move n to a block with less loop depth than it's current block. The + new block must be dominated by early. */ static void -move_out_of_loops (ir_node *n, ir_node *dca) +move_out_of_loops (ir_node *n, ir_node *early) { - assert(dca); + ir_node *best, *dca; + assert(n && early); + /* Find the region deepest in the dominator tree dominating dca with the least loop nesting depth, but still dominated by our early placement. */ - ir_node *best = dca; - while (dca != get_nodes_Block(n)) { + dca = get_nodes_Block(n); + best = dca; + while (dca != early) { dca = get_Block_idom(dca); if (!dca) break; /* should we put assert(dca)? */ - if (get_Block_loop_depth(dca) < get_Block_loop_depth(best)) { + if (get_irn_loop_depth(dca) < get_irn_loop_depth(best)) { best = dca; } } - if (get_Block_dom_depth(best) >= get_Block_dom_depth(get_nodes_Block(n))) + if (best != get_nodes_Block(n)) { + /* debug output + printf("Moving out of loop: "); DDMN(n); + printf(" Outermost block: "); DDMN(early); + printf(" Best block: "); DDMN(best); + printf(" Innermost block: "); DDMN(get_nodes_Block(n)); + */ set_nodes_Block(n, best); + } } -#endif /* Find the latest legal block for N and place N into the `optimal' Block between the latest and earliest legal block. @@ -910,11 +1052,17 @@ static void place_floats_late (ir_node *n) { int i; + ir_node *early; assert (irn_not_visited(n)); /* no multiple placement */ /* no need to place block nodes, control nodes are already placed. */ - if ((get_irn_op(n) != op_Block) && (!is_cfop(n)) && (get_irn_mode(n) != mode_X)) { + if ((get_irn_op(n) != op_Block) && + (!is_cfop(n)) && + (get_irn_mode(n) != mode_X)) { + /* Remember the early palacement of this block to move it + out of loop no further than the early placement. */ + early = get_nodes_Block(n); /* Assure that our users are all placed, except the Phi-nodes. --- Each dataflow cycle contains at least one Phi-node. We have to break the `user has to be placed before the @@ -929,7 +1077,8 @@ place_floats_late (ir_node *n) place_floats_late (succ); } - /* We have to determine the final block of this node... except for constants. */ + /* We have to determine the final block of this node... except for + constants. */ if ((get_op_pinned(get_irn_op(n)) == floats) && (get_irn_op(n) != op_Const) && (get_irn_op(n) != op_SymConst)) { @@ -941,9 +1090,8 @@ place_floats_late (ir_node *n) dca = consumer_dom_dca (dca, get_irn_out(n, i), n); } set_nodes_Block(n, dca); -#if 0 - move_out_of_loops (n, dca); -#endif + + move_out_of_loops (n, early); } } @@ -958,7 +1106,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); @@ -982,6 +1130,8 @@ void place_code(ir_graph *irg) { if (get_irg_dom_state(irg) != dom_consistent) compute_doms(irg); + construct_backedges(irg); + /* Place all floating nodes as early as possible. This guarantees a legal code placement. */ worklist = new_pdeq (); @@ -1004,10 +1154,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); @@ -1015,21 +1168,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); @@ -1045,7 +1208,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)); @@ -1054,7 +1217,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); @@ -1062,7 +1225,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; @@ -1102,20 +1265,20 @@ 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; + /* Count the number of predecessor if this block is merged with pred blocks + that are empty. */ max_preds = 0; for (i = 0; i < get_Block_n_cfgpreds(b); i++) { - pred = get_Block_cfgpred(b, i); max_preds += test_whether_dispensable(b, i); } 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)); @@ -1126,7 +1289,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); @@ -1151,15 +1314,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 ++; @@ -1167,10 +1333,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)); @@ -1190,7 +1357,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; @@ -1261,7 +1428,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) @@ -1280,7 +1446,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); @@ -1302,3 +1467,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); +}