**
** Author: Christian Schaefer
**
-** dead node elemination
-** 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 <config.h>
+#endif
+
+# include <assert.h>
+
# 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) {
}
}
-
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);
current_ir_graph = rem;
}
-/* Remeber the new node in the old node,
- by using a field that all nodes have. */
-void *
+/********************************************************************/
+/* Routines for dead node elimination / copying garbage collection */
+/* of the obstack. */
+/********************************************************************/
+
+/* 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;
- 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)
{
- return n->in[0];
+ return n->link;
}
+/* 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;
-/* Create this node on a new obstack. */
-void
+ 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;
+ }
+}
+
+/* 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 * res, a, b;
- int i;
+ ir_node *nn, *block;
+ int new_arity;
- if (is_binop(n)) {
- a = get_binop_left(n);
- b = get_binop_right(n);
- } else if (is_unop(n)) {
- a = get_unop_op(n);
+ 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);
+ }
}
+ 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);
+}
- switch (get_irn_opcode(n)) {
- case iro_Block:
- /*CS malloc*/
- ir_node **in [get_Block_n_cfgpreds(n)];
- for (i=0; i <(get_Return_n_res(n)); i++) {
- in[i] = get_Block_cfgpred (n, i);
- }
- res = new_r_Block (current_ir_graph, get_Block_n_cfgpreds(n), in);
- set_new_node(n, res);
- break;
- case iro_Start:
- res = new_r_Start (current_ir_graph, get_new_node(n));
- set_new_node(n, res);
- break;
- case iro_End:
- res = new_r_End (current_ir_graph, get_new_node(n));
- set_new_node(n, res);
- break;
- case iro_Jmp:
- res = new_r_Jmp (current_ir_graph, get_new_node(n));
- set_new_node(n, res);
- break;
- case iro_Cond:
- res = new_r_Cond (current_ir_graph, get_new_node(n),
- get_Cond_selector(n));
- set_new_node(n, res);
- break;
- case iro_Return:
- {
- /*CS malloc*/
- ir_node **in [get_Return_n_res(n)];
- for (i=0; i <(get_Return_n_res(n)); i++) {
- in[i] = get_Return_res (n, i);
- }
- res = new_r_Return (current_ir_graph, get_new_node(n),
- get_Return_mem (n), get_Return_n_res(n), in);
- set_new_node(n, res);
- }
- break;
- case iro_Raise:
- res = new_r_Raise (current_ir_graph, get_new_node(n),
- get_Raise_mem(n), get_Raise_exoptr(n));
- set_new_node(n, res);
- break;
- case iro_Const:
- res = new_r_Const (current_ir_graph, get_new_node(n),
- get_irn_mode(n), get_Const_tarval(n));
- set_new_node(n, res);
- break;
- case iro_SymConst:
- {
- if (get_SymConst_kind(n) == type_tag || get_SymConst_kind(n) == size)
- {
- res = new_r_Raise (current_ir_graph, get_new_node(n),
- get_SymConst_type(n), get_SymConst_kind (n));
- }
- else
- /* if get_SymConst_kind(n) == linkage_ptr_info */
- {
- res = new_r_Raise (current_ir_graph, get_new_node(n),
- get_SymConst_ptrinfo(n), get_SymConst_kind (n));
- }
- set_new_node(n, res);
- }
- break;
- case iro_Sel:
- {
- ir_node **in [get_Sel_n_index(n)];
- for (i=0; i <(get_Sel_n_index(n)); i++) {
- in[i] = get_Sel_index (n, i);
- }
- res = new_r_Sel (current_ir_graph, get_new_node(n),
- get_Sel_mem(n), get_Sel_ptr(n), get_Sel_n_index(n),
- in, get_Sel_entity(n));
- set_new_node(n, res);
- }
- break;
- case iro_Call:
- {
- ir_node **in [get_Call_arity(n)];
- for (i=0; i <(get_Call_arity(n)); i++) {
- in[i] = get_Call_param (n, i);
- }
- res = new_r_Call (current_ir_graph, get_new_node(n), get_Call_mem(n),
- get_Call_ptr(n), get_Call_arity(n),
- in, get_Call_type (n));
- set_new_node(n, res);
- }
- break;
- case iro_Add:
- res = new_r_Add (current_ir_graph, get_new_node(n),
- get_new_node(a),
- get_new_node(b), get_irn_mode(n));
- set_new_node(n, res);
- 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));
- set_new_node(n, res);
- break;
- case iro_Minus:
- res = new_r_Minus (current_ir_graph, get_new_node(n), get_new_node(a),
- get_irn_mode(n));
- set_new_node(n, res);
- break;
- case iro_Mul:
- res = new_r_Mul (current_ir_graph, get_new_node(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(n), 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(n), 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(n), 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(n), get_Mod_mem (n),
- get_new_node(a), get_new_node(b));
- break;
- case iro_Abs:
- res = new_r_Mod (current_ir_graph, get_new_node(n), get_Abs_op(n)
- get_irn_mode(n));
- break;
- case iro_And:
- res = new_r_And (current_ir_graph, get_new_node(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(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(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(n), get_Not_op(n),
- get_irn_mode(n));
- break;
- case iro_Cmp:
- res = new_r_Cmp (current_ir_graph, get_new_node(n), get_Cmp_left(n),
- get_Cmp_right(n));
- break;
- case iro_Shl:
- res = new_r_Shl (current_ir_graph, get_new_node(n), get_Shl_left(n),
- get_Shl_right(n), get_irn_mode(n));
- break;
- case iro_Shr:
- res = new_r_Shr (current_ir_graph, get_new_node(n), get_Shr_left(n),
- get_Shr_right(n), get_irn_mode(n));
- break;
- case iro_Shrs:
- res = new_r_Shrs (current_ir_graph, get_new_node(n), get_Shrs_left(n),
- get_Shrs_right(n), get_irn_mode(n));
- break;
- case iro_Rot:
- res = new_r_Rot (current_ir_graph, get_new_node(n), get_Rot_left(n),
- get_Rot_right(n), get_irn_mode(n));
- break;
- case iro_Conv:
- res = new_r_Conv (current_ir_graph, get_new_node(n), get_Conv_op(n),
- get_irn_mode(n));
- break;
- case iro_Phi:
- /*CS malloc*/
- ir_node **in [get_Phi_n_preds(n)];
- for (i=0; i <(get_Phi_n_preds(n)); i++) {
- in[i] = get_Phi_pred (n, i);
- }
- res = new_r_Phi (current_ir_graph, get_new_node(n),
- get_Phi_n_preds(n), in, get_irn_mode(n));
- set_new_node(n, res);
- break;
- case iro_Load:
- res = new_r_Load (current_ir_graph, get_new_node(n), get_Load_mem(n),
- get_Load_ptr(n));
- break;
- case iro_Store:
- res = new_r_Store (current_ir_graph, get_new_node(n), get_Store_mem(n),
- get_Store_ptr(n), get_Store_value(n));
- break;
- case iro_Alloc:
- res = new_r_Alloc (current_ir_graph, get_new_node(n),
- get_Alloc_mem(n), 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(n),
- get_Free_mem(n), get_Free_ptr(n),
- get_Free_size(n), get_Free_type(n));
- break;
- case iro_Sync:
- /*CS malloc*/
- ir_node **in [get_Sync_n_preds(n)];
- for (i=0; i <(get_Sync_n_preds(n)); i++) {
- in[i] = get_Sync_pred (n, i);
+/* 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_Sync (current_ir_graph, get_new_node(n),
- get_Sync_n_preds(n), in);
- set_new_node(n, res);
- break;
- case iro_Proj:
- res = new_r_Proj (current_ir_graph, get_new_node(n),
- get_Proj_pred(n), get_irn_mode(n),
- get_Proj_proj(n));
- break;
- case iro_Tuple:
- /*CS malloc*/
- ir_node **in [get_Tuple_n_preds(n)];
- for (i=0; i <(get_Tuple_n_preds(n)); i++) {
- in[i] = gget_Tuple_pred (n, i);
+ /* 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++;
}
- res = new_r_Tuple (current_ir_graph, get_new_node(n),
- get_Tuple_n_preds(n), in);
- set_new_node(n, res);
- break;
- case iro_Id:
- res = new_r_Id (current_ir_graph, get_new_node(n),
- get_Id_pred(n), get_irn_mode(n));
- break;
- case iro_Bad:
- res = new_r_Bad (get_new_node(n));
- break;
+ /* 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)));
}
+}
+
+/* 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_elemination(ir_graph *irg) {
- struct obstack *graveyard_obst;
- struct obstack *rebirth_obst;
+dead_node_elimination(ir_graph *irg) {
+ ir_graph *rem;
+ struct obstack *graveyard_obst = NULL;
+ struct obstack *rebirth_obst = NULL;
- /* A quiet place, where the old obstack can rest in peace,
- until it will be cremated. */
- graveyard_obst = irg->obst;
+ /* Remember external state of current_ir_graph. */
+ rem = current_ir_graph;
+ current_ir_graph = irg;
- /* A new obstack, where the reachable nodes will be copied to. */
- rebirth_obst = (struct obstack *) xmalloc (sizeof (struct obstack));
- current_ir_graph->obst = rebirth_obst;
- obstack_init (current_ir_graph->obst);
+ if (get_optimize() && get_opt_dead_node_elimination()) {
- /* 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);
+ /* A quiet place, where the old obstack can rest in peace,
+ until it will be cremated. */
+ graveyard_obst = irg->obst;
- /* Free memory from old unoptimized obstack */
- xfree (graveyard_obst);
+ /* A new obstack, where the reachable nodes will be copied to. */
+ rebirth_obst = (struct obstack *) xmalloc (sizeof (struct obstack));
+ current_ir_graph->obst = rebirth_obst;
+ obstack_init (current_ir_graph->obst);
+ /* Copy the graph from the old to the new obstack */
+ copy_graph();
+
+ /* Free memory from old unoptimized obstack */
+ obstack_free(graveyard_obst, 0); /* First empty the obstack ... */
+ xfree (graveyard_obst); /* ... then free it. */
+ }
+
+ current_ir_graph = rem;
}
projects / libfirm / blobdiff