** 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 "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. */
/********************************************************************/
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);
/* 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 allocate in arrays with an arity
+ 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
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);
}
/* 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. *
- on = optimize_in_place(nn);
- if (nn != on) exchange(nn, on);*/
+ 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. */
j++;
}
/* Compacting the Phi's ins might generate Phis with only one
- predecessor. *
+ predecessor. */
if (get_irn_arity(n) == 1)
- exchange(n, get_irn_n(n, 0)); */
+ 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)));
current_ir_graph = rem;
}
-
-
-
-
-
-#if 0 /* An old implementation */
-
-/* To break the recursion of the graph walk if there are loops in
- the graph we have to allocate new nodes for Phis and blocks
- before descending. Here we use the old predecessors for the
- new nodes. These are replaced by the proper predecessors in
- copy_node.
- It turned out that it is not sufficient to just break loops
- for Phi and Block nodes, as the walker can hit visited but
- not copied nodes at any point in the graph.
- A simple fix would be allocating Id's for every node and then
- exchanging them, but this will cause new dead nodes on the new
- obstack.
- So now there is a different implementation more based on the
- view on the graph as a graph than as a represented program. */
-void
-create_dummy (ir_node *n, void *env) {
- assert (n);
-
- /* Assure link is set to NULL so we can test whether there is a
- new node by checking link.
- set_irn_link(n, NULL); */
-
- switch (get_irn_opcode(n)) {
- case iro_Block:
- set_new_node(n, new_ir_node(current_ir_graph, NULL, op_Block, mode_R,
- get_irn_arity(n), get_irn_in(n)));
- break;
- case iro_Phi:
- set_new_node(n, new_ir_node(current_ir_graph, NULL, op_Phi,
- get_irn_mode(n),
- get_irn_arity(n), get_irn_in(n)));
- break;
- default: {}
- } /* end switch (get_irn_opcode(n)) */
-}
-
-/* Create a copy of this node on a new obstack. */
-void
-copy_node2 (ir_node *n, void *env) {
- ir_node *res = NULL;
- ir_node *a = NULL;
- ir_node *b = NULL;
- int i = 0;
-
- 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);
- }
-
- switch (get_irn_opcode(n)) {
- case iro_Block:
- {
- res = get_new_node(n);
- assert(res);
- for (i = 0; i < get_Block_n_cfgpreds(n); i++)
- set_Block_cfgpred(res, i, get_new_node(get_Block_cfgpred(n, i)));
- set_Block_matured(res, 1);
- }
- 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)));
- 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_p value = NULL;
-
- if ((get_SymConst_kind(n)==type_tag) || (get_SymConst_kind(n)==size))
- {
-
- value = (type_or_id_p) get_SymConst_type(n);
- }
- else
- {
- if (get_SymConst_kind(n)==linkage_ptr_info)
- {
- value = (type_or_id_p) 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;
- 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:
- {
- res = get_new_node(n);
- for (i = 0; i < get_Phi_n_preds(n); i++)
- set_Phi_pred(res, i, get_new_node(get_Phi_pred(n, i)));
- set_nodes_Block(res, get_new_node(get_nodes_Block(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 = get_new_node(get_Id_pred(n));
- break;
- case iro_Bad:
- res = new_r_Bad ();
- break;
- }
- /* @@@ Here we could call optimize()!! Not necessary, called in constructor anyways. */
- set_new_node(n, res);
- printf(" "); DDMSG2(res);
-}
-
-void
-copy_graph2 () {
- ir_node *old_node, *new_node, *projX;
- ir_graph *irg = current_ir_graph;
-
- /*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. Get the ProjX of the Start node, that is
- predecessor of the start Block. We have to break the cycle and fix it
- later. We use the old in array as placeholder. */
- old_node = irg->start_block;
- new_node = new_r_Block (current_ir_graph, get_Block_n_cfgpreds(old_node),
- get_Block_cfgpred_arr(old_node));
- /* new_r_Block calls no optimization --> save */
- projX = get_Block_cfgpred(old_node, 0);
- irg->start_block = new_node;
- set_new_node (old_node, new_node);
- set_irn_visited (old_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;
- set_new_node (old_node, new_node);
- set_irn_visited (old_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 (old_node, get_irg_visited(current_ir_graph)+1);
- /* Copy the Projs for the Start's results. */
- old_node = projX;
- new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_X, pns_initial_exec);
- set_Block_cfgpred(irg->start_block, 0, new_node);
- set_new_node (old_node, new_node);
- set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
-
- 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 (old_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 (old_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 (old_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, create_dummy, copy_node2, NULL);
-
- /*CS*/
- printf("After DEAD NODE ELIMINATION !\n");
-}
-#endif