-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");
+/* Find the latest legal block for N and place N into the
+ `optimal' Block between the latest and earliest legal block.
+ The `optimal' block is the dominance-deepest block of those
+ with the least loop-nesting-depth. This places N out of as many
+ loops as possible and then makes it as controldependant as
+ possible. */
+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)) {
+ /* 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
+ producer' dependance cycle and the Phi-nodes are the
+ place to do so, because we need to base our placement on the
+ final region of our users, which is OK with Phi-nodes, as they
+ are pinned, and they never have to be placed after a
+ producer of one of their inputs in the same block anyway. */
+ for (i = 0; i < get_irn_n_outs(n); i++) {
+ ir_node *succ = get_irn_out(n, i);
+ if (irn_not_visited(succ) && (get_irn_op(succ) != op_Phi))
+ place_floats_late (succ);
+ }
+
+ /* 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)) {
+ ir_node *dca = NULL; /* deepest common ancestor in the
+ dominator tree of all nodes'
+ blocks depending on us; our final
+ placement has to dominate DCA. */
+ for (i = 0; i < get_irn_n_outs(n); i++) {
+ dca = consumer_dom_dca (dca, get_irn_out(n, i), n);
+ }
+ set_nodes_Block(n, dca);
+
+ move_out_of_loops (n, early);
+ }
+ }
+
+ mark_irn_visited(n);
+
+ /* Add predecessors of all non-floating nodes on list. (Those of floating
+ nodes are placeded already and therefore are marked.) */
+ for (i = 0; i < get_irn_n_outs(n); i++) {
+ if (irn_not_visited(get_irn_out(n, i))) {
+ pdeq_putr (worklist, get_irn_out(n, i));
+ }
+ }
+}
+
+static INLINE void place_late(void) {
+ assert(worklist);
+ inc_irg_visited(current_ir_graph);
+
+ /* This fills the worklist initially. */
+ place_floats_late(get_irg_start_block(current_ir_graph));
+ /* And now empty the worklist again... */
+ while (!pdeq_empty (worklist)) {
+ ir_node *n = pdeq_getl (worklist);
+ if (irn_not_visited(n)) place_floats_late(n);
+ }
+}
+
+void place_code(ir_graph *irg) {
+ ir_graph *rem = current_ir_graph;
+ current_ir_graph = irg;
+
+ if (!(get_optimize() && get_opt_global_cse())) return;
+
+ /* Handle graph state */
+ assert(get_irg_phase_state(irg) != phase_building);
+ 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 ();
+ place_early();
+
+ /* place_early invalidates the outs, place_late needs them. */
+ compute_outs(irg);
+ /* Now move the nodes down in the dominator tree. This reduces the
+ unnecessary executions of the node. */
+ place_late();
+
+ set_irg_outs_inconsistent(current_ir_graph);
+ del_pdeq (worklist);
+ current_ir_graph = rem;
+}
+
+
+
+/********************************************************************/
+/* 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);
+
+ if (get_irn_op(n) == op_Block) {
+ /* Remove Tuples */
+ for (i = 0; i < get_Block_n_cfgpreds(n); i++)
+ /* 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, 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);
+ }
+ /* 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);
+
+ if ((get_irn_op(n) == op_Phi)) {
+ /* Collect Phi nodes to compact ins along with block's ins. */
+ set_irn_link(n, get_irn_link(b));
+ set_irn_link(b, n);
+ } else if (get_irn_op(n) != op_Jmp) { /* Check for non empty block. */
+ mark_Block_block_visited(b);
+ }
+ }
+}
+
+/* Returns true if pred is pred of block */
+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));
+ if (b_pred == pred) return 1;
+ }
+ return 0;
+}
+
+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);
+ ir_node *pred = get_nodes_Block(cfop);
+
+ if (get_Block_block_visited(pred) + 1
+ < get_irg_block_visited(current_ir_graph)) {
+ 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;
+ }
+ /* Seems to be empty. */
+ if (!get_irn_link(b)) {
+ /* There are no Phi nodes ==> dispensable. */
+ n_preds = get_Block_n_cfgpreds(pred);
+ } else {
+ /* b's pred blocks and pred's pred blocks must be pairwise disjunct.
+ Work preds < pos as if they were already removed. */
+ for (i = 0; i < pos; i++) {
+ ir_node *b_pred = get_nodes_Block(get_Block_cfgpred(b, i));
+ if (get_Block_block_visited(b_pred) + 1
+ < get_irg_block_visited(current_ir_graph)) {
+ for (j = 0; j < get_Block_n_cfgpreds(b_pred); j++) {
+ ir_node *b_pred_pred = get_nodes_Block(get_Block_cfgpred(b_pred, j));
+ if (is_pred_of(b_pred_pred, pred)) dispensable = 0;
+ }
+ } else {
+ if (is_pred_of(b_pred, pred)) dispensable = 0;
+ }
+ }
+ for (i = pos +1; i < get_Block_n_cfgpreds(b); i++) {
+ ir_node *b_pred = get_nodes_Block(get_Block_cfgpred(b, i));
+ if (is_pred_of(b_pred, pred)) dispensable = 0;
+ }
+ if (!dispensable) {
+ set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
+ n_preds = 1;
+ } else {
+ n_preds = get_Block_n_cfgpreds(pred);
+ }
+ }
+ }
+
+ return n_preds;
+}
+
+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++) {
+ max_preds += test_whether_dispensable(b, i);
+ }
+ in = (ir_node **) malloc(max_preds * sizeof(ir_node *));
+
+/**
+ printf(" working on "); DDMN(b);
+ for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
+ pred = get_nodes_Block(get_Block_cfgpred(b, i));
+ if (is_Bad(get_Block_cfgpred(b, i))) {
+ printf(" removing Bad %i\n ", i);
+ } else if (get_Block_block_visited(pred) +1
+ < get_irg_block_visited(current_ir_graph)) {
+ printf(" removing pred %i ", i); DDMN(pred);
+ } else { printf(" Nothing to do for "); DDMN(pred); }
+ }
+ * end Debug output **/
+
+ /** Fix the Phi nodes **/
+ phi = get_irn_link(b);
+ while (phi) {
+ assert(get_irn_op(phi) == op_Phi);
+ /* Find the new predecessors for the Phi */
+ n_preds = 0;
+ for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
+ pred = get_nodes_Block(get_Block_cfgpred(b, i));
+ if (is_Bad(get_Block_cfgpred(b, i))) {
+ /* Do nothing */
+ } else if (get_Block_block_visited(pred) +1
+ < get_irg_block_visited(current_ir_graph)) {
+ /* It's an empty block and not yet visited. */
+ ir_node *phi_pred = get_Phi_pred(phi, i);
+ for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
+ if (get_nodes_Block(phi_pred) == pred) {
+ assert(get_irn_op(phi_pred) == op_Phi); /* Block is empty!! */
+ in[n_preds] = get_Phi_pred(phi_pred, j);
+ } else {
+ in[n_preds] = phi_pred;
+ }
+ n_preds++;
+ }
+ /* 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, ist aber doch semantisch falsch! Warum?? */
+ }
+ } else {
+ in[n_preds] = get_Phi_pred(phi, i);
+ n_preds ++;
+ }
+ }
+ /* Fix the node */
+ set_irn_in(phi, n_preds, in);
+
+ phi = get_irn_link(phi);
+ }
+
+/**
+ 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));
+ if (get_Block_block_visited(pred) +1
+ < get_irg_block_visited(current_ir_graph)) {
+ phi = get_irn_link(pred);
+ while (phi) {
+ if (get_irn_op(phi) == op_Phi) {
+ set_nodes_Block(phi, b);
+
+ n_preds = 0;
+ for (i = 0; i < k; i++) {
+ pred = get_nodes_Block(get_Block_cfgpred(b, i));
+ if (is_Bad(get_Block_cfgpred(b, i))) {
+ /* Do nothing */
+ } else if (get_Block_block_visited(pred) +1
+ < 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!!! Kontrollflusskante
+ muss Rueckwaertskante sein! (An allen vier in[n_preds] = phi
+ Anweisungen.) Trotzdem tuts bisher!! */
+ in[n_preds] = phi;
+ n_preds++;
+ }
+ } else {
+ in[n_preds] = phi;
+ n_preds++;
+ }
+ }
+ for (i = 0; i < get_Phi_n_preds(phi); i++) {
+ in[n_preds] = get_Phi_pred(phi, i);
+ n_preds++;
+ }
+ for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
+ pred = get_nodes_Block(get_Block_cfgpred(b, i));
+ if (is_Bad(get_Block_cfgpred(b, i))) {
+ /* Do nothing */
+ } else if (get_Block_block_visited(pred) +1
+ < 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++) {
+ in[n_preds] = phi;
+ n_preds++;
+ }
+ } else {
+ in[n_preds] = phi;
+ n_preds++;
+ }
+ }
+ set_irn_in(phi, n_preds, in);
+ }
+ phi = get_irn_link(phi);
+ }
+ }
+ }
+
+ /** Fix the block **/
+ n_preds = 0;
+ for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
+ pred = get_nodes_Block(get_Block_cfgpred(b, i));
+ if (is_Bad(get_Block_cfgpred(b, i))) {
+ /* Do nothing */
+ } else if (get_Block_block_visited(pred) +1
+ < get_irg_block_visited(current_ir_graph)) {
+ /* It's an empty block and not yet visited. */
+ assert(get_Block_n_cfgpreds(b) > 1);
+ /* Else it should be optimized by equivalent_node. */
+ for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
+ in[n_preds] = get_Block_cfgpred(pred, j);
+ n_preds++;
+ }
+ /* Remove block as it might be kept alive. */
+ exchange(pred, b/*new_Bad()*/);
+ } else {
+ in[n_preds] = get_Block_cfgpred(b, i);
+ n_preds ++;
+ }
+ }
+ set_irn_in(b, n_preds, in);
+ free(in);
+}
+
+void optimize_cf(ir_graph *irg) {
+ int i;
+ ir_node **in;
+ ir_node *end = get_irg_end(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)
+ set_irg_outs_inconsistent(current_ir_graph);
+ if (get_irg_dom_state(current_ir_graph) == dom_consistent)
+ set_irg_dom_inconsistent(current_ir_graph);
+
+ /* Use block visited flag to mark non-empty blocks. */
+ inc_irg_block_visited(irg);
+ irg_walk(end, merge_blocks, collect_nodes, NULL);
+
+ /* Optimize the standard code. */
+ irg_block_walk(get_irg_end_block(irg), optimize_blocks, NULL, NULL);
+
+ /* Walk all keep alives, optimize them if block, add to new in-array
+ 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);
+ if (irn_not_visited(ka)) {
+ if ((get_irn_op(ka) == op_Block) && Block_not_block_visited(ka)) {
+ set_irg_block_visited(current_ir_graph, /* Don't walk all the way to Start. */
+ get_irg_block_visited(current_ir_graph)-1);
+ irg_block_walk(ka, optimize_blocks, NULL, NULL);
+ mark_irn_visited(ka);
+ ARR_APP1 (ir_node *, in, ka);
+ } else if (get_irn_op(ka) == op_Phi) {
+ mark_irn_visited(ka);
+ ARR_APP1 (ir_node *, in, ka);
+ }
+ }
+ }
+ /* DEL_ARR_F(end->in); GL @@@ tut nicht ! */
+ end->in = in;
+
+ 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);
+
+ if (n == get_irg_end_block(current_ir_graph))
+ return; // No use to add a block here.
+
+ for (i=0; i<arity; i++) {
+ pre = get_irn_n(n, i);
+ /* Predecessor has multiple sucessors. Insert new flow edge */
+ if ((NULL != pre) &&
+ (op_Proj == get_irn_op(pre)) &&
+ op_Raise != get_irn_op(skip_Proj(pre))) {
+
+ /* set predecessor array for new block */
+ in = NEW_ARR_D (ir_node *, current_ir_graph->obst, 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);