- 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 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 (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;
- }
-}
-
-/* TODO: add an ir_op operation */
-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 a node to the current_ir_graph. The Ins of the new node point to
- * the predecessors on the graph of the old node. For block/phi nodes not all
- * predecessors might be copied.
- * 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.
- */
-ir_node *copy_irn(ir_node *n, int copy_node_nr) {
- ir_node *nn, *block;
- int new_arity;
- ir_op *op = get_irn_op(n);
-
- /* The end node looses it's flexible in array. This doesn't matter,
- as dead node elimination builds End by hand, inlineing doesn't use
- the End node. */
- /* assert(op == op_End || ((_ARR_DESCR(n->in))->cookie != ARR_F_MAGIC)); */
-
- if (op == op_Bad) {
- /* node copied already */
- return NULL;
- } 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. */
- copy_node_attr(n, nn);
- new_backedge_info(nn);
-
-#if DEBUG_libfirm
- if (copy_node_nr) {
- /* for easier debugging, we want to copy the node numbers too */
- nn->node_nr = n->node_nr;
- }
-#endif
-
- return nn;
-}
-
-/**
- * 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 firm_copy_node (ir_node *n, void *env) {
- ir_node *nn = copy_irn(n, env != NULL);
-
- if (nn)
- set_new_node(n, nn);
-}
-
-
-/**
- * Copies new predecessors of old node to new node remembered in link.
- * Spare the Bad predecessors of Phi and Block nodes.
- */
-void
-copy_preds (ir_node *n, void *env) {
- ir_node *nn, *block;
- int i, j, irn_arity;
-
- nn = get_new_node(n);
-
- /* printf("\n old node: "); DDMSG2(n);
- printf(" new node: "); DDMSG2(nn);
- printf(" arities: old: %d, new: %d\n", get_irn_arity(n), get_irn_arity(nn)); */
-
- if (is_Block(n)) {
- /* 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))) {
- 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
- 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 ((get_opt_control_flow_straightening()) &&
- (get_Block_n_cfgpreds(nn) == 1) &&
- (get_irn_op(get_Block_cfgpred(nn, 0)) == op_Jmp)) {
- 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 (get_irn_op(n) == op_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;
- irn_arity = get_irn_arity(n);
- for (i = 0; i < irn_arity; i++)
- if (! is_Bad(get_irn_n(block, i))) {
- 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
- 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.
- @@@ inlinening aborts if we identify End. Why? */
- if (get_irn_op(nn) != op_End)
- add_identities (current_ir_graph->value_table, nn);
-}
-
-/**
- * Copies the graph recursively, compacts the keepalive of the end node.
- *
- * @param copy_node_nr If non-zero, the node number will be copied
- */
-static void
-copy_graph (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;
-
- oe = get_irg_end(current_ir_graph);
- /* copy the end node by hand, allocate dynamic in array! */
- ne = new_ir_node(get_irn_dbg_info(oe),
- current_ir_graph,
- 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(current_ir_graph);
- nb = new_ir_node(get_irn_dbg_info(ob),
- current_ir_graph,
- NULL,
- op_Bad,
- mode_T,
- 0,
- NULL);
- set_new_node(ob, nb);
-
- /* copy the NoMem node */
- om = get_irg_no_mem(current_ir_graph);
- nm = new_ir_node(get_irn_dbg_info(om),
- current_ir_graph,
- NULL,
- op_NoMem,
- mode_M,
- 0,
- NULL);
- set_new_node(om, nm);
-
- /* copy the live nodes */
- irg_walk(get_nodes_block(oe), firm_copy_node, copy_preds, (void *)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_irn_arity(oe);
- for (i = 0; i < irn_arity; i++) {
- ka = get_irn_intra_n(oe, i);
- if ((get_irn_op(ka) == op_Block) &&
- (get_irn_visited(ka) < get_irg_visited(current_ir_graph))) {
- /* We must keep the block alive and copy everything reachable */
- set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1);
- irg_walk(ka, firm_copy_node, copy_preds, (void *)copy_node_nr);
- add_End_keepalive(ne, get_new_node(ka));
- }
- }
-
- /* Now pick the Phis. Here we will keep all! */
- irn_arity = get_irn_arity(oe);
- for (i = 0; i < irn_arity; i++) {
- ka = get_irn_intra_n(oe, i);
- if ((get_irn_op(ka) == op_Phi)) {
- if (get_irn_visited(ka) < get_irg_visited(current_ir_graph)) {
- /* We didn't copy the Phi yet. */
- set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1);
- irg_walk(ka, firm_copy_node, copy_preds, (void *)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_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. */
- 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);
- set_irn_link(get_irg_initial_mem(current_ir_graph), NULL);
- set_irn_link(get_irg_no_mem (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 */
- copy_graph(copy_node_nr);
-
- /* fix the fields in current_ir_graph */
- old_end = get_irg_end(current_ir_graph);
- set_irg_end (current_ir_graph, get_new_node(old_end));
- set_irg_end_except (current_ir_graph, get_irg_end(current_ir_graph));
- set_irg_end_reg (current_ir_graph, get_irg_end(current_ir_graph));
- 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) {
- firm_copy_node (get_irg_frame(current_ir_graph), (void *)copy_node_nr);
- copy_preds(get_irg_frame(current_ir_graph), NULL);
- }
- if (get_irn_link(get_irg_globals(current_ir_graph)) == NULL) {
- firm_copy_node (get_irg_globals(current_ir_graph), (void *)copy_node_nr);
- copy_preds(get_irg_globals(current_ir_graph), NULL);
- }
- if (get_irn_link(get_irg_initial_mem(current_ir_graph)) == NULL) {
- firm_copy_node (get_irg_initial_mem(current_ir_graph), (void *)copy_node_nr);
- copy_preds(get_irg_initial_mem(current_ir_graph), NULL);
- }
- if (get_irn_link(get_irg_args(current_ir_graph)) == NULL) {
- firm_copy_node (get_irg_args(current_ir_graph), (void *)copy_node_nr);
- copy_preds(get_irg_args(current_ir_graph), 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_initial_mem(current_ir_graph, get_new_node(get_irg_initial_mem(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) {
- firm_copy_node(get_irg_bad(current_ir_graph), (void *)copy_node_nr);
- copy_preds(get_irg_bad(current_ir_graph), NULL);
- }
- set_irg_bad(current_ir_graph, get_new_node(get_irg_bad(current_ir_graph)));
-
- if (get_irn_link(get_irg_no_mem(current_ir_graph)) == NULL) {
- firm_copy_node(get_irg_no_mem(current_ir_graph), (void *)copy_node_nr);
- copy_preds(get_irg_no_mem(current_ir_graph), NULL);
- }
- set_irg_no_mem(current_ir_graph, get_new_node(get_irg_no_mem(current_ir_graph)));
-}
-
-/**
- * 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;
- int rem_ipview = get_interprocedural_view();
- struct obstack *graveyard_obst = NULL;
- struct obstack *rebirth_obst = NULL;
-
- edges_init_graph(irg);
-
- /* inform statistics that we started a dead-node elimination run */
- hook_dead_node_elim_start(irg);
-
- /* Remember external state of current_ir_graph. */
- rem = current_ir_graph;
- current_ir_graph = irg;
- set_interprocedural_view(false);
-
- /* Handle graph state */
- assert(get_irg_phase_state(current_ir_graph) != phase_building);
- free_callee_info(current_ir_graph);
- free_irg_outs(current_ir_graph);
- free_trouts();
- /* @@@ so far we loose loops when copying */
- free_loop_information(current_ir_graph);
-
- if (get_opt_optimize() && get_opt_dead_node_elimination()) {
-
- /* 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 (sizeof(*rebirth_obst));
- current_ir_graph->obst = rebirth_obst;
- obstack_init (current_ir_graph->obst);
-
- /* We also need a new hash 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(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_stop(irg);
-
- current_ir_graph = rem;
- set_interprocedural_view(rem_ipview);
-}
-
-/**
- * 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) {
- 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 already 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. We do not resize the array, as we must
- keep the old one to update Phis. */
- new_in = NEW_ARR_D (ir_node *, current_ir_graph->obst, (new_irn_arity+1));
-
- /* set new predecessors in array */
- new_in[0] = NULL;
- new_irn_n = 1;
- for (i = 0; i < old_irn_arity; i++) {
- irn = get_irn_n(n, i);
- if (!is_Bad(irn)) {
- new_in[new_irn_n] = irn;
- is_backedge(n, i) ? set_backedge(n, new_irn_n-1) : set_not_backedge(n, new_irn_n-1);
- new_irn_n++;
- }
- }
- //ARR_SETLEN(int, n->attr.block.backedge, new_irn_arity);
- ARR_SHRINKLEN(n->attr.block.backedge, new_irn_arity);
- n->in = new_in;
-
- } /* ir node has bad predecessors */
-
- } /* Block is not relinked */
-}
-
-/**
- * Relinks Bad predecessors from Blocks and Phis called by walker
- * remove_bad_predecesors(). If n is a Block, call
- * relink_bad_block_redecessors(). If n is a Phi-node, call also the relinking
- * function of Phi's Block. If this block has bad predecessors, relink preds
- * of the Phi-node.
- */
-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 predecessors 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 predecessors 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);