-#define set_new_node(oldn, newn) set_irn_link(oldn, newn)
-
-/**
- * Get this new node, before the old node is forgotten.
- */
-#define get_new_node(oldn) get_irn_link(oldn)
-
-/**
- * Check if a new node was set.
- */
-#define has_new_node(n) (get_new_node(n) != NULL)
-
-/** a pointer to the new phases */
-static ir_phase *new_phases[PHASE_LAST];
-
-/**
- * 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 in the old blocks.
- * 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.
- */
-static inline int compute_new_arity(ir_node *b)
-{
- int i, res, irn_arity;
- 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 = irn_arity = get_irn_arity(b);
- for (i = 0; i < irn_arity; i++)
- if (is_Bad(get_irn_n(b, i))) 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. 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.
- *
- * @param n The node to be copied
- * @param env if non-NULL, the node number attribute will be copied to the new node
- *
- * Note: Also used for loop unrolling.
- */
-static void copy_node(ir_node *n, void *env)
-{
- ir_node *nn, *block;
- int new_arity, i;
- ir_phase *old_ph;
- ir_op *op = get_irn_op(n);
- (void) env;
-
- if (op == op_Bad) {
- /* node copied already */
- return;
- } else if (op == op_Block) {
- block = NULL;
- new_arity = compute_new_arity(n);
- n->attr.block.graph_arr = NULL;
- } else {
- block = get_nodes_block(n);
- if (op == op_Phi) {
- new_arity = compute_new_arity(block);
- } else {
- new_arity = get_irn_arity(n);
- }
- }
- nn = new_ir_node(get_irn_dbg_info(n),
- current_ir_graph,
- block,
- op,
- get_irn_mode(n),
- new_arity,
- get_irn_in(n) + 1);
- /* 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. */
- if (op == op_Block) {
- /* we cannot allow blocks WITHOUT macroblock input */
- set_Block_MacroBlock(nn, get_Block_MacroBlock(n));
- }
- copy_node_attr(n, nn);
-
- /* preserve the phase information for this node */
- for (i = PHASE_NOT_IRG_MANAGED+1; i < PHASE_LAST; i++) {
- old_ph = get_irg_phase(current_ir_graph, i);
- if (old_ph != NULL) {
- if(phase_get_irn_data(old_ph, n)) {
- phase_set_irn_data(new_phases[i], nn, phase_get_irn_data(old_ph, n));
- }
- }
- }
-
- if (env != NULL) {
- /* for easier debugging, we want to copy the node numbers too */
- nn->node_nr = n->node_nr;
- }
-
- set_new_node(n, nn);
- hook_dead_node_elim_subst(current_ir_graph, n, nn);
-}
-
-/**
- * Copies new predecessors of old node to new node remembered in link.
- * Spare the Bad predecessors of Phi and Block nodes.
- */
-static void copy_preds(ir_node *n, void *env)
-{
- ir_node *nn, *block;
- int i, j, irn_arity;
- (void) env;
-
- nn = get_new_node(n);
-
- if (is_Block(n)) {
- /* copy the macro block header */
- ir_node *mbh = get_Block_MacroBlock(n);
-
- if (mbh == n) {
- /* this block is a macroblock header */
- set_Block_MacroBlock(nn, nn);
- } else {
- /* get the macro block header */
- ir_node *nmbh = get_new_node(mbh);
- assert(nmbh != NULL);
- set_Block_MacroBlock(nn, nmbh);
- }
-
- /* Don't copy Bad nodes. */
- j = 0;
- irn_arity = get_irn_arity(n);
- for (i = 0; i < irn_arity; i++) {
- if (! is_Bad(get_irn_n(n, i))) {
- ir_node *pred = get_irn_n(n, i);
- set_irn_n(nn, j, get_new_node(pred));
- j++;
- }
- }
- /* repair the block visited flag from above misuse. Repair it in both
- graphs so that the old one can still be used. */
- set_Block_block_visited(nn, 0);
- set_Block_block_visited(n, 0);
- /* Local optimization could not merge two subsequent blocks if
- 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 (!has_Block_entity(nn) &&
- get_opt_control_flow_straightening() &&
- get_Block_n_cfgpreds(nn) == 1 &&
- is_Jmp(get_Block_cfgpred(nn, 0))) {
- ir_node *old = get_nodes_block(get_Block_cfgpred(nn, 0));
- if (nn == old) {
- /* Jmp jumps into the block it is in -- deal self cycle. */
- assert(is_Bad(get_new_node(get_irg_bad(current_ir_graph))));
- exchange(nn, get_new_node(get_irg_bad(current_ir_graph)));
- } else {
- exchange(nn, old);
- }
- }
- } else if (is_Phi(n) && get_irn_arity(n) > 0) {
- /* Don't copy node if corresponding predecessor in block is Bad.
- The Block itself should not be Bad. */
- block = get_nodes_block(n);
- set_nodes_block(nn, get_new_node(block));
- j = 0;
- irn_arity = get_irn_arity(n);
- for (i = 0; i < irn_arity; i++) {
- if (! is_Bad(get_irn_n(block, i))) {
- ir_node *pred = get_irn_n(n, i);
- set_irn_n(nn, j, get_new_node(pred));
- /*if (is_backedge(n, i)) set_backedge(nn, j);*/
- j++;
- }
- }
- /* If the pre walker reached this Phi after the post walker visited the
- block block_visited is > 0. */
- set_Block_block_visited(get_nodes_block(n), 0);
- /* Compacting the Phi's ins might generate Phis with only one
- predecessor. */
- if (get_irn_arity(nn) == 1)
- exchange(nn, get_irn_n(nn, 0));
- } else {
- irn_arity = get_irn_arity(n);
- for (i = -1; i < irn_arity; i++)
- set_irn_n(nn, i, get_new_node(get_irn_n(n, i)));
- }
- /* Now the new node is complete. We can add it to the hash table for CSE.
- @@@ inlining aborts if we identify End. Why? */
- if (!is_End(nn))
- add_identities(current_ir_graph->value_table, nn);
-}
-
-/**
- * Copies the graph recursively, compacts the keep-alives of the end node.
- *
- * @param irg the graph to be copied
- * @param copy_node_nr If non-zero, the node number will be copied
- */
-static void copy_graph(ir_graph *irg, int copy_node_nr)
-{
- ir_node *oe, *ne, *ob, *nb, *om, *nm; /* old end, new end, old bad, new bad, old NoMem, new NoMem */
- ir_node *ka; /* keep alive */
- int i, irn_arity;
- unsigned long vfl;
-
- /* Some nodes must be copied by hand, sigh */
- vfl = get_irg_visited(irg);
- set_irg_visited(irg, vfl + 1);
-
- oe = get_irg_end(irg);
- mark_irn_visited(oe);
- /* copy the end node by hand, allocate dynamic in array! */
- ne = new_ir_node(get_irn_dbg_info(oe),
- irg,
- NULL,
- op_End,
- mode_X,
- -1,
- NULL);
- /* Copy the attributes. Well, there might be some in the future... */
- copy_node_attr(oe, ne);
- set_new_node(oe, ne);
-
- /* copy the Bad node */
- ob = get_irg_bad(irg);
- mark_irn_visited(ob);
- nb = new_ir_node(get_irn_dbg_info(ob),
- irg,
- NULL,
- op_Bad,
- mode_T,
- 0,
- NULL);
- copy_node_attr(ob, nb);
- set_new_node(ob, nb);
-
- /* copy the NoMem node */
- om = get_irg_no_mem(irg);
- mark_irn_visited(om);
- nm = new_ir_node(get_irn_dbg_info(om),
- irg,
- NULL,
- op_NoMem,
- mode_M,
- 0,
- NULL);
- copy_node_attr(om, nm);
- set_new_node(om, nm);
-
- /* copy the live nodes */
- set_irg_visited(irg, vfl);
- irg_walk(get_nodes_block(oe), copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
-
- /* Note: from yet, the visited flag of the graph is equal to vfl + 1 */
-
- /* visit the anchors as well */
- for (i = get_irg_n_anchors(irg) - 1; i >= 0; --i) {
- ir_node *n = get_irg_anchor(irg, i);
-
- if (n && (get_irn_visited(n) <= vfl)) {
- set_irg_visited(irg, vfl);
- irg_walk(n, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
- }
- }
-
- /* copy_preds for the end node ... */
- set_nodes_block(ne, get_new_node(get_nodes_block(oe)));
-
- /*- ... and now the keep alives. -*/
- /* First pick the not marked block nodes and walk them. We must pick these
- first as else we will oversee blocks reachable from Phis. */
- irn_arity = get_End_n_keepalives(oe);
- for (i = 0; i < irn_arity; i++) {
- ka = get_End_keepalive(oe, i);
- if (is_Block(ka)) {
- if (get_irn_visited(ka) <= vfl) {
- /* We must keep the block alive and copy everything reachable */
- set_irg_visited(irg, vfl);
- irg_walk(ka, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
- }
- add_End_keepalive(ne, get_new_node(ka));
- }
- }
-
- /* Now pick other nodes. Here we will keep all! */
- irn_arity = get_End_n_keepalives(oe);
- for (i = 0; i < irn_arity; i++) {
- ka = get_End_keepalive(oe, i);
- if (!is_Block(ka)) {
- if (get_irn_visited(ka) <= vfl) {
- /* We didn't copy the node yet. */
- set_irg_visited(irg, vfl);
- irg_walk(ka, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
- }
- add_End_keepalive(ne, get_new_node(ka));
- }
- }
-
- /* start block sometimes only reached after keep alives */
- set_nodes_block(nb, get_new_node(get_nodes_block(ob)));
- set_nodes_block(nm, get_new_node(get_nodes_block(om)));
-}
-
-/**
- * Copies the graph reachable from current_ir_graph->end to the obstack
- * in current_ir_graph and fixes the environment.
- * Then fixes the fields in current_ir_graph containing nodes of the
- * graph.
- *
- * @param copy_node_nr If non-zero, the node number will be copied
- */
-static void copy_graph_env(int copy_node_nr)
-{
- ir_graph *irg = current_ir_graph;
- ir_node *old_end, *new_anchor;
- ir_phase *old_ph;
- int i;
-
- /* init the new_phases array */
- for (i = PHASE_NOT_IRG_MANAGED+1; i < PHASE_LAST; i++) {
- old_ph = get_irg_phase(irg, i);
- if (old_ph == NULL) {
- new_phases[i] = NULL;
- } else {
- new_phases[i] = xmalloc(sizeof(ir_phase));
- phase_init(new_phases[i], "", irg, old_ph->growth_factor,
- old_ph->data_init, old_ph->priv);
- }
- }
-
-
- /* remove end_except and end_reg nodes */
- old_end = get_irg_end(irg);
- set_irg_end_except (irg, old_end);
- set_irg_end_reg (irg, old_end);
-
- /* Not all nodes remembered in irg 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. */
- for (i = get_irg_n_anchors(irg) - 1; i >= 0; --i) {
- ir_node *n = get_irg_anchor(irg, i);
- if (n != NULL)
- set_new_node(n, NULL);
- }
- /* we use the block walk flag for removing Bads from Blocks ins. */
- inc_irg_block_visited(irg);
-
- /* copy the graph */
- copy_graph(irg, copy_node_nr);
-
- /* fix the anchor */
- old_end = get_irg_end(irg);
- new_anchor = new_Anchor(irg);
-
- for (i = get_irg_n_anchors(irg) - 1; i >= 0; --i) {
- ir_node *n = get_irg_anchor(irg, i);
- if (n) {
- set_irn_n(new_anchor, i, get_new_node(n));
- }
- }
-
- /* copy the new phases into the irg */
- for (i = PHASE_NOT_IRG_MANAGED+1; i < PHASE_LAST; i++) {
- old_ph = get_irg_phase(irg, i);
- if (old_ph != NULL) {
- free_irg_phase(irg, i);
- irg->phases[i] = new_phases[i];
- }
- }
-
- free_End(old_end);
- irg->anchor = new_anchor;
-
- /* ensure the new anchor is placed in the endblock */
- set_nodes_block(new_anchor, get_irg_end_block(irg));
-}
-
-/**
- * Copies all reachable nodes to a new obstack. Removes bad inputs
- * from block nodes and the corresponding inputs from Phi nodes.
- * Merges single exit blocks with single entry blocks and removes
- * 1-input Phis.
- * Adds all new nodes to a new hash table for CSE. Does not
- * perform CSE, so the hash table might contain common subexpressions.
- */
-void dead_node_elimination(ir_graph *irg)
-{
- ir_graph *rem;
-#ifdef INTERPROCEDURAL_VIEW
- int rem_ipview = get_interprocedural_view();
-#endif
- struct obstack *graveyard_obst = NULL;
- struct obstack *rebirth_obst = NULL;
-
- edges_deactivate(irg);
-
- /* inform statistics that we started a dead-node elimination run */
- hook_dead_node_elim(irg, 1);
-
- /* Remember external state of current_ir_graph. */
- rem = current_ir_graph;
- current_ir_graph = irg;
-#ifdef INTERPROCEDURAL_VIEW
- set_interprocedural_view(0);
-#endif
-
- assert(get_irg_phase_state(irg) != phase_building);
-
- /* Handle graph state */
- free_callee_info(irg);
- free_irg_outs(irg);
- free_trouts();
-
- /* @@@ so far we loose loops when copying */
- free_loop_information(irg);
-
- set_irg_doms_inconsistent(irg);
-
- /* A quiet place, where the old obstack can rest in peace,
- until it will be cremated. */
- graveyard_obst = irg->obst;
-
- /* A new obstack, where the reachable nodes will be copied to. */
- rebirth_obst = XMALLOC(struct obstack);
- irg->obst = rebirth_obst;
- obstack_init(irg->obst);
- irg->last_node_idx = 0;
-
- /* We also need a new value table for CSE */
- del_identities(irg->value_table);
- irg->value_table = new_identities();
-
- /* Copy the graph from the old to the new obstack */
- copy_graph_env(/*copy_node_nr=*/1);
-
- /* Free memory from old unoptimized obstack */
- obstack_free(graveyard_obst, 0); /* First empty the obstack ... */
- xfree(graveyard_obst); /* ... then free it. */
-
- /* inform statistics that the run is over */
- hook_dead_node_elim(irg, 0);
-
- current_ir_graph = rem;
-#ifdef INTERPROCEDURAL_VIEW
- set_interprocedural_view(rem_ipview);
-#endif
-}
-
-ir_graph_pass_t *dead_node_elimination_pass(const char *name)
-{
- return def_graph_pass(name ? name : "dce", dead_node_elimination);
-}
-
-/**
- * Relink bad predecessors 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)