* Author:
* Created:
* CVS-ID: $Id$
- * Copyright: (c) 1998-2004 Universit�t Karlsruhe
+ * Copyright: (c) 1998-2004 Universität Karlsruhe
* Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
*/
# include "config.h"
#endif
+#ifdef HAVE_MALLOC_H
+# include <malloc.h>
+#endif
+#ifdef HAVE_ALLOCA_H
+# include <alloca.h>
+#endif
+
#include <assert.h>
#include "xmalloc.h"
#include "iropt_t.h"
#include "irgwalk.h"
#include "irgmod.h"
+#include "irdump.h"
#include "irvrfy.h"
#include "array.h"
**/
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);
+ ir_node *pred = get_Block_cfgpred_block(b, pos);
/* Bad blocks will be optimized away, so we don't need space for them */
- if (is_Bad(pred))
+ if (is_Block_dead(pred))
return 0;
if (get_Block_block_visited(pred) + 1
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. */
+ Handle all pred blocks with 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
+ ir_node *b_pred = get_Block_cfgpred_block(b, i);
+ if (! is_Block_dead(b_pred) &&
+ 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;
+ ir_node *b_pred_pred = get_Block_cfgpred_block(b_pred, j);
+ if (is_pred_of(b_pred_pred, pred))
+ goto non_dispensable;
}
} else {
- if (is_pred_of(b_pred, pred)) dispensable = 0;
+ if (is_pred_of(b_pred, pred))
+ goto non_dispensable;
}
}
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);
+ ir_node *b_pred = get_Block_cfgpred_block(b, i);
+ if (is_pred_of(b_pred, pred))
+ goto non_dispensable;
}
+ /* if we get here, the block is dispensable */
+ n_preds = get_Block_n_cfgpreds(pred);
}
}
return n_preds;
+
+non_dispensable:
+ set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
+ return 1;
}
+/**
+ * Store to defer the exchanged of Phi nodes.
+ */
+typedef struct _defer_ex_phi {
+ ir_node *phi_pred; /**< the previous Phi node that will be replaced */
+ ir_node *phi; /**< the new Phi node that replaces phi_pred */
+} defer_ex_phi;
/**
* This method removed Bad cf predecessors from Blocks and Phis, and removes
* for all nodes, not regarding whether there is a possibility for optimization.
*
* For each predecessor p of a Block b there are three cases:
- * -#. The predecessor p is a Bad node: just skip it. The in array of b shrinks by one.
- * -#. The predecessor p is empty. Remove p. All predecessors of p are now
+ * -1. The predecessor p is a Bad node: just skip it. The in array of b shrinks by one.
+ * -2. The predecessor p is empty. Remove p. All predecessors of p are now
* predecessors of b.
- * -#. The predecessor p is a block containing useful code. Just keep p as is.
+ * -3. The predecessor p is a block containing useful code. Just keep p as is.
*
* For Phi nodes f we have to check the conditions at the Block of f.
* For cases 1 and 3 we proceed as for Blocks. For case 2 we can have two
* \ / \ /
* \ / | /
* pred_b | /
- * | ____ | /
+ * | ____ | / ____
* | | | | | | |
* | | | === optimized to ===> \ | | |
* loop_b | loop_b |
int i, j, k, n, max_preds, n_preds, p_preds;
ir_node *pred, *phi;
ir_node **in;
+ defer_ex_phi *defers;
/* Count the number of predecessor if this block is merged with pred blocks
that are empty. */
}
in = xmalloc(max_preds * sizeof(*in));
+ defers = NEW_ARR_F(defer_ex_phi, 0);
+
/*-
printf(" working on "); DDMN(b);
for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
/* Find the new predecessors for the Phi */
p_preds = 0;
for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
- pred = get_nodes_block(get_Block_cfgpred(b, i));
+ pred = get_Block_cfgpred_block(b, i);
if (is_Bad(get_Block_cfgpred(b, i))) {
/* case Phi 1: Do nothing */
Somehow the removed Phi node can be used legally in loops.
Therefore we replace the old phi by the new one.
+ This must be done _AFTER_ all Phis are optimized, or
+ it will fail if two Phis use the same pred_Phi.
+
+ FIXME: Is the following true? We ALWAYS replace it by the new one.
Further we have to remove the old Phi node by replacing it
by Bad. Else it will remain in the keep alive array of End
replace it by Bad.
*/
if (get_nodes_block(phi_pred) == pred) {
+ int i;
/* 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?? */
+ for (i = ARR_LEN(defers) - 1; i >= 0; --i)
+ if (defers[i].phi_pred == phi_pred)
+ break;
+
+ if (i < 0) {
+ /* we have a new replacement */
+ defer_ex_phi elem;
+
+ elem.phi_pred = phi_pred;
+ elem.phi = phi;
+ ARR_APP1(defer_ex_phi, defers, elem);
+ }
}
} else {
/* case Phi 3: */
phi = get_irn_link(phi);
}
+ /* now, exchange all Phis */
+ for (i = ARR_LEN(defers) - 1; i >= 0; --i) {
+ exchange(defers[i].phi_pred, defers[i].phi);
+ }
+ DEL_ARR_F(defers);
+
/*- This happens only if merge between loop backedge and single loop entry.
See special case above. -*/
for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
< get_irg_block_visited(current_ir_graph)) {
/* case 2: It's an empty block and not yet visited. */
assert(get_Block_n_cfgpreds(b) > 1);
- /* Else it should be optimized by equivalent_node. */
+ /* Else it should be optimized by equivalent_node. */
for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
ir_node *pred_block = get_Block_cfgpred(pred, j);
* we will lose blocks and thereby generate memory leaks.
*/
void optimize_cf(ir_graph *irg) {
- int i, n;
+ int i, j, n;
ir_node **in;
ir_node *end = get_irg_end(irg);
ir_graph *rem = current_ir_graph;
/* 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);
+ set_irg_outs_inconsistent(current_ir_graph);
+ set_irg_extblk_inconsistent(current_ir_graph);
+ set_irg_loopinfo_inconsistent(current_ir_graph);
+ set_irg_doms_inconsistent(current_ir_graph);
if (dom_state == dom_consistent && get_opt_optimize() && get_opt_unreachable_code()) {
ir_node *end = get_irg_end(irg);
ir_node *ka = get_End_keepalive(end, i);
if (is_Block(ka)) {
+ /* do NOT keep dead blocks */
if (get_Block_dom_depth(ka) == -1)
set_End_keepalive(end, i, new_Bad());
}
- else if (is_Block_dead(get_nodes_block(ka)) || get_Block_dom_depth(get_nodes_block(ka)) == -1)
+ else if (is_Block_dead(get_nodes_block(ka)) ||
+ get_Block_dom_depth(get_nodes_block(ka)) == -1)
+ /* do NOT keep nodes in dead blocks */
set_End_keepalive(end, i, new_Bad());
}
}
-
irg_block_walk_graph(current_ir_graph, NULL, remove_senseless_conds, NULL);
/* Use block visited flag to mark non-empty blocks. */
/* 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);
+ n = get_End_n_keepalives(end);
+ if (n > 0)
+ NEW_ARR_A (ir_node *, in, n);
inc_irg_visited(current_ir_graph);
- for (i = 0; i < get_End_n_keepalives(end); i++) {
+ /* fix the keep alive */
+ for (i = j = 0; i < n; 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)) {
+ ir_op *op = get_irn_op(ka);
+
+ if ((op == 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) {
+ in[j++] = ka;
+ } else if (op == op_Phi) {
mark_irn_visited(ka);
- ARR_APP1 (ir_node *, in, ka);
- } else if (get_irn_op(ka) == op_IJmp) {
+ if (! is_Block_dead(get_nodes_block(ka)))
+ in[j++] = ka;
+ } else if (is_op_keep(op)) {
mark_irn_visited(ka);
- ARR_APP1 (ir_node *, in, ka);
+ if (! is_Block_dead(get_nodes_block(ka)))
+ in[j++] = ka;
}
}
}
- /* DEL_ARR_F(end->in); GL @@@ tut nicht ! */
- end->in = in;
-
+ if (j != n)
+ set_End_keepalives(end, j, in);
/* the verifier doesn't work yet with floating nodes */
if (get_irg_pinned(irg) == op_pin_state_pinned) {