# include "config.h"
#endif
+#include "iroptimize.h"
+
#include <assert.h>
#include "plist.h"
#include "irflag_t.h"
#include "firmstat.h"
-#include "cfopt.h"
#include "iropt_dbg.h"
/*------------------------------------------------------------------*/
/* 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. */
+/* Further, we NEVER remove labeled blocks (even if we could move */
+/* the label. */
/*------------------------------------------------------------------*/
/**
/** An environment for merge_blocks and collect nodes. */
typedef struct _merge_env {
- int changed;
- plist_t *list;
+ int changed; /**< Set if the graph was changed. */
+ int phis_moved; /**< Set if Phi nodes were moved. */
+ plist_t *list; /**< Helper list for all found Switch Conds. */
} merge_env;
/**
ir_op *op = get_irn_op(n);
merge_env *env = ctx;
- if (op != op_Block) {
+ if (op == op_Block) {
+ /* mark the block as non-empty if it is labelled */
+ if (has_Block_label(n))
+ mark_Block_block_visited(n);
+ } else {
ir_node *b = get_nodes_block(n);
- if (op == op_Phi) {
+ if (op == op_Phi && get_irn_arity(n) > 0) {
/* Collect Phi nodes to compact ins along with block's ins. */
set_irn_link(n, get_irn_link(b));
set_irn_link(b, n);
* @@@ It is negotiable whether we should do this ... there might end up a copy
* from the Phi in the loop when removing the Phis.
*/
-static void optimize_blocks(ir_node *b, void *env) {
+static void optimize_blocks(ir_node *b, void *ctx) {
int i, j, k, n, max_preds, n_preds, p_preds = -1;
ir_node *pred, *phi;
ir_node **in;
- int *changed = env;
+ merge_env *env = ctx;
/* Count the number of predecessor if this block is merged with pred blocks
that are empty. */
exchange(phi, in[0]);
else
set_irn_in(phi, p_preds, in);
- *changed = 1;
+ env->changed = 1;
phi = get_irn_link(phi);
}
/*- This happens only if merge between loop backedge and single loop entry.
- Moreover, it is only needed if pred is the direct dominator of b, else there can be no uses
- of the Phi's in pred ... -*/
+ Moreover, it is only needed if predb is the direct dominator of b, else there can be no uses
+ of the Phi's in predb ... -*/
for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
- pred = get_nodes_block(get_Block_cfgpred(b, k));
+ ir_node *predb = get_nodes_block(get_Block_cfgpred(b, k));
- if (get_Block_block_visited(pred) + 1 < get_irg_block_visited(current_ir_graph)) {
+ if (get_Block_block_visited(predb) + 1 < get_irg_block_visited(current_ir_graph)) {
ir_node *next_phi;
/* we found a predecessor block at position k that will be removed */
- for (phi = get_irn_link(pred); phi; phi = next_phi) {
+ for (phi = get_irn_link(predb); phi; phi = next_phi) {
int q_preds = 0;
next_phi = get_irn_link(phi);
assert(is_Phi(phi));
- /* move this phi from the predecessor into the block b */
- set_nodes_block(phi, b);
- set_irn_link(phi, get_irn_link(b));
- set_irn_link(b, phi);
-
- /* first, copy all 0..k-1 predecessors */
- for (i = 0; i < k; i++) {
- pred = get_Block_cfgpred_block(b, i);
-
- if (is_Bad(pred)) {
- /* 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++) {
- if (! is_Bad(get_Block_cfgpred(pred, j)))
- in[q_preds++] = phi;
+ if (get_Block_idom(b) != predb) {
+ /* predb is not the dominator. There can't be uses of pred's Phi nodes, kill them .*/
+ exchange(phi, new_Bad());
+ } else {
+ /* predb is the direct dominator of b. There might be uses of the Phi nodes from
+ predb in further block, so move this phi from the predecessor into the block b */
+ set_nodes_block(phi, b);
+ set_irn_link(phi, get_irn_link(b));
+ set_irn_link(b, phi);
+ env->phis_moved = 1;
+
+ /* first, copy all 0..k-1 predecessors */
+ for (i = 0; i < k; i++) {
+ pred = get_Block_cfgpred_block(b, i);
+
+ if (is_Bad(pred)) {
+ /* 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++) {
+ if (! is_Bad(get_Block_cfgpred(pred, j)))
+ in[q_preds++] = phi;
+ }
+ } else {
+ in[q_preds++] = phi;
}
- } else {
- in[q_preds++] = phi;
}
- }
- /* now we are at k, copy the phi predecessors */
- pred = get_nodes_block(get_Block_cfgpred(b, k));
- for (i = 0; i < get_Phi_n_preds(phi); i++) {
- if (! is_Bad(get_Block_cfgpred(pred, i)))
- in[q_preds++] = get_Phi_pred(phi, i);
- }
+ /* now we are at k, copy the phi predecessors */
+ pred = get_nodes_block(get_Block_cfgpred(b, k));
+ for (i = 0; i < get_Phi_n_preds(phi); i++) {
+ if (! is_Bad(get_Block_cfgpred(pred, i)))
+ in[q_preds++] = get_Phi_pred(phi, i);
+ }
- /* and now all the rest */
- 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++) {
- if (! is_Bad(get_Block_cfgpred(pred, j)))
- in[q_preds++] = phi;
+ /* and now all the rest */
+ 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++) {
+ if (! is_Bad(get_Block_cfgpred(pred, j)))
+ in[q_preds++] = phi;
+ }
+ } else {
+ in[q_preds++] = phi;
}
- } else {
- in[q_preds++] = phi;
}
- }
- /* Fix the node */
- if (q_preds == 1)
- exchange(phi, in[0]);
- else
- set_irn_in(phi, q_preds, in);
- *changed = 1;
+ /* Fix the node */
+ if (q_preds == 1)
+ exchange(phi, in[0]);
+ else
+ set_irn_in(phi, q_preds, in);
+ env->changed = 1;
- assert(q_preds <= max_preds);
- // assert(p_preds == q_preds && "Wrong Phi Fix");
+ assert(q_preds <= max_preds);
+ // assert(p_preds == q_preds && "Wrong Phi Fix");
+ }
}
}
}
assert(n_preds <= max_preds);
set_irn_in(b, n_preds, in);
- *changed = 1;
+ env->changed = 1;
- assert(get_irn_link(b) == NULL || (n_preds == p_preds && "Wrong Phi Fix"));
+ assert(get_irn_link(b) == NULL || p_preds == -1 || (n_preds == p_preds && "Wrong Phi Fix"));
xfree(in);
}
* Block walker: optimize all blocks using the default optimizations.
* This removes Blocks that with only a Jmp predecessor.
*/
-static void remove_simple_blocks(ir_node *block, void *env) {
+static void remove_simple_blocks(ir_node *block, void *ctx) {
ir_node *new_blk = equivalent_node(block);
- int *changed = env;
+ merge_env *env = ctx;
if (new_blk != block) {
exchange(block, new_blk);
- *changed = 1;
+ env->changed = 1;
}
}
/* FIXME: is this still needed? */
edges_deactivate(irg);
- env.changed = 0;
+ env.changed = 0;
+ env.phis_moved = 0;
+
if (get_opt_optimize() && get_opt_unreachable_code()) {
ir_node *end;
/* Optimize the standard code. */
env.changed = 0;
- assure_irg_outs(irg);
- irg_block_walk(get_irg_end_block(irg), optimize_blocks, remove_simple_blocks, &env.changed);
+ assure_doms(irg);
+ irg_block_walk(get_irg_end_block(irg), optimize_blocks, remove_simple_blocks, &env);
/* Walk all keep alives, optimize them if block, add to new in-array
for end if useful. */
irg_block_walk(ka, optimize_blocks, remove_simple_blocks, &env.changed);
mark_irn_visited(ka);
in[j++] = ka;
- }
- }
- }
- for (i = 0; i < n; i++) {
- ir_node *ka = get_End_keepalive(end, i);
-
- if (irn_not_visited(ka)) {
- ir_op *op = get_irn_op(ka);
-
- if (op == op_Phi) {
+ } else if (op == op_Phi) {
mark_irn_visited(ka);
- /* don't keep alive dead or already visited blocks */
- if (! is_Block_dead(get_nodes_block(ka)) &&
- Block_not_block_visited(get_nodes_block(ka)))
+ /* don't keep alive dead blocks */
+ if (! is_Block_dead(get_nodes_block(ka)))
in[j++] = ka;
} else if (is_op_keep(op)) {
mark_irn_visited(ka);
clear_using_visited(irg);
+ if (env.phis_moved) {
+ /* Bad: when we moved Phi's, we might produce dead Phi nodes
+ that are kept-alive.
+ Some other phases cannot copy with this, so will them.
+ */
+ n = get_End_n_keepalives(end);
+ if (n > 0) {
+ if (env.changed) {
+ /* Handle graph state if was changed. */
+ set_irg_outs_inconsistent(irg);
+ }
+ assure_irg_outs(irg);
+
+ for (i = j = 0; i < n; ++i) {
+ ir_node *ka = get_End_keepalive(end, i);
+
+ if (is_Phi(ka)) {
+ int k;
+
+ for (k = get_irn_n_outs(ka) - 1; k >= 0; --k) {
+ ir_node *user = get_irn_out(ka, k);
+
+ if (user != ka && user != end) {
+ /* Is it a real user or just a self loop ? */
+ break;
+ }
+ }
+ if (k >= 0)
+ in[j++] = ka;
+ } else
+ in[j++] = ka;
+ }
+ if (j != n) {
+ set_End_keepalives(end, j, in);
+ env.changed = 1;
+ }
+ }
+ }
+
if (env.changed) {
/* Handle graph state if was changed. */
set_irg_outs_inconsistent(irg);
set_irg_loopinfo_inconsistent(irg);
}
+
/* the verifier doesn't work yet with floating nodes */
if (get_irg_pinned(irg) == op_pin_state_pinned) {
/* after optimize_cf(), only Bad data flow may remain. */