-/* Coyright (C) 1998 - 2000 by Universitaet Karlsruhe
+/* Coyright (C) 1998 - 2002 by Universitaet Karlsruhe
** All rights reserved.
**
-** Author: Christian Schaefer
+** Author: Christian Schaefer, Goetz Lindenmaier, Sebastian Felis
**
** Optimizations for a whole ir graph, i.e., a procedure.
*/
# include "pset.h"
# include "pdeq.h" /* Fuer code placement */
# include "irouts.h"
+# include "irloop.h"
+# include "irbackedge_t.h"
/* Defined in iropt.c */
pset *new_identities (void);
}
}
+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 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. */
-void
+static void
copy_node (ir_node *n, void *env) {
ir_node *nn, *block;
int new_arity;
if (get_irn_opcode(n) == iro_Block) {
block = NULL;
new_arity = compute_new_arity(n);
+ n->attr.block.graph_arr = NULL;
} else {
block = get_nodes_Block(n);
if (get_irn_opcode(n) == iro_Phi) {
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_attrs(n, nn);
+ new_backedge_info(nn);
set_new_node(n, nn);
/* printf("\n old node: "); DDMSG2(n);
/* Copies new predecessors of old node to new node remembered in link.
Spare the Bad predecessors of Phi and Block nodes. */
-void
+static void
copy_preds (ir_node *n, void *env) {
ir_node *nn, *block;
int i, j;
for (i = 0; i < get_irn_arity(n); i++)
if (get_irn_opcode(get_irn_n(n, i)) != iro_Bad) {
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
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_Block_n_cfgpreds(nn) == 1
- && get_irn_op(get_Block_cfgpred(nn, 0)) == op_Jmp)
+ if ((get_opt_control_flow()) &&
+ (get_Block_n_cfgpreds(nn) == 1) &&
+ (get_irn_op(get_Block_cfgpred(nn, 0)) == op_Jmp))
exchange(nn, get_nodes_Block(get_Block_cfgpred(nn, 0)));
} else if (get_irn_opcode(n) == iro_Phi) {
/* Don't copy node if corresponding predecessor in block is Bad.
for (i = 0; i < get_irn_arity(n); i++)
if (get_irn_opcode(get_irn_n(block, i)) != iro_Bad) {
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
}
/* Copies the graph recursively, compacts the keepalive of the end node. */
-void
+static void
copy_graph () {
ir_node *oe, *ne; /* old end, new end */
ir_node *ka; /* keep alive */
graph. */
void
copy_graph_env () {
+ 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. */
copy_graph();
/* fix the fields in current_ir_graph */
- free_End(get_irg_end(current_ir_graph));
- set_irg_end (current_ir_graph, get_new_node(get_irg_end(current_ir_graph)));
+ old_end = get_irg_end(current_ir_graph);
+ set_irg_end (current_ir_graph, get_new_node(old_end));
+ 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) {
copy_node (get_irg_frame(current_ir_graph), NULL);
assert(get_irg_phase_state(current_ir_graph) != phase_building);
free_outs(current_ir_graph);
+ /* @@@ so far we loose loops when copying */
+ set_irg_loop(current_ir_graph, NULL);
+
if (get_optimize() && get_opt_dead_node_elimination()) {
/* A quiet place, where the old obstack can rest in peace,
current_ir_graph = rem;
}
+/* Relink bad predeseccors 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 allready 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 without Block predecessor */
+ new_in = NEW_ARR_D (ir_node *, current_ir_graph->obst, (new_irn_arity+1));
+
+ /* set new predeseccors in array */
+ new_in[0] = NULL;
+ new_irn_n = 1;
+ for (i = 1; i < old_irn_arity; i++) {
+ irn = get_irn_n(n, i);
+ if (!is_Bad(irn)) new_in[new_irn_n++] = irn;
+ }
+ n->in = new_in;
+ } /* ir node has bad predecessors */
+
+ } /* Block is not relinked */
+}
+
+/* Relinks Bad predecesors from Bocks and Phis called by walker
+ remove_bad_predecesors(). If n is a Block, call
+ relink_bad_block_redecessors(). If n is a Phinode, call also the relinking
+ function of Phi's Block. If this block has bad predecessors, relink preds
+ of the Phinode. */
+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 predeseccors 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 predeseccors 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);
+
+ /* Relink Phi predeseccors if count of predeseccors changed */
+ if (old_irn_arity != ARR_LEN(get_irn_in(block))) {
+ /* set new predeseccors in array
+ n->in[0] remains the same block */
+ new_irn_arity = 1;
+ for(i = 1; i < old_irn_arity; i++)
+ if (!is_Bad((ir_node *)old_in[i])) n->in[new_irn_arity++] = n->in[i];
+
+ ARR_SETLEN(ir_node *, n->in, new_irn_arity);
+ }
+
+ } /* n is a Phi node */
+}
+
+/* Removes Bad Bad predecesors from Blocks and the corresponding
+ inputs to Phi nodes as in dead_node_elimination but without
+ copying the graph.
+ On walking up set the link field to NULL, on walking down call
+ relink_bad_predecessors() (This function stores the old in array
+ to the link field and sets a new in array if arity of predecessors
+ changes) */
+void remove_bad_predecessors(ir_graph *irg) {
+ irg_walk_graph(irg, init_link, relink_bad_predecessors, NULL);
+}
+
+
/**********************************************************************/
/* Funcionality for inlining */
/**********************************************************************/
then updates the entity if it's a local one. env must be a pointer
to the frame type of the procedure. The new entities must be in
the link field of the entities. */
-void
+static INLINE void
copy_node_inline (ir_node *n, void *env) {
ir_node *new;
type *frame_tp = (type *)env;
/** Check preconditions **/
assert(get_irn_op(call) == op_Call);
- /* assert(get_Call_type(call) == get_entity_type(get_irg_ent(called_graph))); */
- assert(smaller_type(get_entity_type(get_irg_ent(called_graph)),
- get_Call_type(call)));
+ /* @@@ TODO does not work for InterfaceIII.java after cgana
+ assert(get_Call_type(call) == get_entity_type(get_irg_ent(called_graph)));
+ assert(smaller_type(get_entity_type(get_irg_ent(called_graph)),
+ get_Call_type(call)));
+ */
assert(get_type_tpop(get_Call_type(call)) == type_method);
if (called_graph == current_ir_graph) return;
/** Part the Call node into two nodes. Pre_call collects the parameters of
- the procedure and later replaces the Start node of the called graph.
- Post_call is the old Call node and collects the results of the called
- graph. Both will end up being a tuple. **/
+ the procedure and later replaces the Start node of the called graph.
+ Post_call is the old Call node and collects the results of the called
+ graph. Both will end up being a tuple. **/
post_bl = get_nodes_Block(call);
set_irg_current_block(current_ir_graph, post_bl);
/* XxMxPxP of Start + parameter of Call */
/* Visited flags in calling irg must be >= flag in called irg.
Else walker and arity computation will not work. */
if (get_irg_visited(current_ir_graph) <= get_irg_visited(called_graph))
- set_irg_visited(current_ir_graph, get_irg_visited(called_graph)+1); /***/
+ set_irg_visited(current_ir_graph, get_irg_visited(called_graph)+1);
if (get_irg_block_visited(current_ir_graph)< get_irg_block_visited(called_graph))
set_irg_block_visited(current_ir_graph, get_irg_block_visited(called_graph));
/* Set pre_call as new Start node in link field of the start node of
copying. */
set_irn_link(get_irg_start(called_graph), pre_call);
set_irn_visited(get_irg_start(called_graph),
- get_irg_visited(current_ir_graph));/***/
+ get_irg_visited(current_ir_graph));
set_irn_link(get_irg_start_block(called_graph),
- get_nodes_Block(pre_call));
+ get_nodes_Block(pre_call));
set_irn_visited(get_irg_start_block(called_graph),
- get_irg_visited(current_ir_graph)); /***/
+ get_irg_visited(current_ir_graph));
/* Initialize for compaction of in arrays */
inc_irg_block_visited(current_ir_graph);
/** Performing dead node elimination inlines the graph **/
/* Copies the nodes to the obstack of current_ir_graph. Updates links to new
entities. */
- /* @@@ endless loops are not copied!! */
+ /* @@@ endless loops are not copied!! -- they should be, I think... */
irg_walk(get_irg_end(called_graph), copy_node_inline, copy_preds,
get_irg_frame_type(called_graph));
}
phi = new_Phi(n_ret, cf_pred, mode_M);
set_Tuple_pred(call, 0, phi);
- set_irn_link(phi, get_irn_link(post_bl)); /* Conserve Phi-list for further inlinings */
- set_irn_link(post_bl, phi);
+ /* Conserve Phi-list for further inlinings -- but might be optimized */
+ if (get_nodes_Block(phi) == post_bl) {
+ set_irn_link(phi, get_irn_link(post_bl));
+ set_irn_link(post_bl, phi);
+ }
/* Now the real results */
if (n_res > 0) {
for (j = 0; j < n_res; j++) {
}
phi = new_Phi(n_ret, cf_pred, get_irn_mode(cf_pred[0]));
res_pred[j] = phi;
- set_irn_link(phi, get_irn_link(post_bl)); /* Conserve Phi-list for further inlinings */
- set_irn_link(post_bl, phi);
+ /* Conserve Phi-list for further inlinings -- but might be optimized */
+ if (get_nodes_Block(phi) == post_bl) {
+ set_irn_link(phi, get_irn_link(post_bl));
+ set_irn_link(post_bl, phi);
+ }
}
set_Tuple_pred(call, 2, new_Tuple(n_res, res_pred));
} else {
}
}
if (n_exc > 0) {
- new_Block(n_exc, cf_pred); /* whatch it: current_block is changed! */
+ new_Block(n_exc, cf_pred); /* watch it: current_block is changed! */
set_Tuple_pred(call, 1, new_Jmp());
/* The Phi for the memories with the exception objects */
n_exc = 0;
if (get_irn_op(addr) == op_Const) {
/* Check whether the constant is the pointer to a compiled entity. */
tv = get_Const_tarval(addr);
- if (tv->u.p.ent) {
- called_irg = get_entity_irg(tv->u.p.ent);
+ if (tv->u.P.ent) {
+ called_irg = get_entity_irg(tv->u.P.ent);
if (called_irg && pos < MAX_INLINE) {
/* The Call node calls a locally defined method. Remember to inline. */
calls[pos] = call;
}
}
-
/* Inlines all small methods at call sites where the called address comes
from a Const node that references the entity representing the called
method.
if (!(get_optimize() && get_opt_inline())) return;
- /*DDME(get_irg_ent(current_ir_graph));*/
-
current_ir_graph = irg;
/* Handle graph state */
assert(get_irg_phase_state(current_ir_graph) != phase_building);
/* There are calls to inline */
collect_phiprojs(irg);
for (i = 0; i < pos; i++) {
+ char buf[1024];
tarval *tv;
ir_graph *callee;
tv = get_Const_tarval(get_Call_ptr(calls[i]));
- callee = get_entity_irg(tv->u.p.ent);
+ callee = get_entity_irg(tv->u.P.ent);
if ((_obstack_memory_used(callee->obst) - obstack_room(callee->obst)) < size) {
- /*printf(" inlineing "); DDME(tv->u.p.ent);*/
inline_method(calls[i], callee);
}
}
return dca;
}
-#if 0
-/* @@@ Needs loop informations. Will implement later interprocedural. */
+INLINE int get_irn_loop_depth(ir_node *n) {
+ return get_loop_depth(get_irn_loop(n));
+}
+
+/* Move n to a block with less loop depth than it's current block. The
+ new block must be dominated by early. */
static void
-move_out_of_loops (ir_node *n, ir_node *dca)
+move_out_of_loops (ir_node *n, ir_node *early)
{
- assert(dca);
+ ir_node *best, *dca;
+ assert(n && early);
+
/* Find the region deepest in the dominator tree dominating
dca with the least loop nesting depth, but still dominated
by our early placement. */
- ir_node *best = dca;
- while (dca != get_nodes_Block(n)) {
+ dca = get_nodes_Block(n);
+ best = dca;
+ while (dca != early) {
dca = get_Block_idom(dca);
if (!dca) break; /* should we put assert(dca)? */
- if (get_Block_loop_depth(dca) < get_Block_loop_depth(best)) {
+ if (get_irn_loop_depth(dca) < get_irn_loop_depth(best)) {
best = dca;
}
}
- if (get_Block_dom_depth(best) >= get_Block_dom_depth(get_nodes_Block(n)))
+ if (best != get_nodes_Block(n)) {
+ /* debug output
+ printf("Moving out of loop: "); DDMN(n);
+ printf(" Outermost block: "); DDMN(early);
+ printf(" Best block: "); DDMN(best);
+ printf(" Innermost block: "); DDMN(get_nodes_Block(n));
+ */
set_nodes_Block(n, best);
+ }
}
-#endif
/* Find the latest legal block for N and place N into the
`optimal' Block between the latest and earliest legal block.
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)) {
+ 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
place_floats_late (succ);
}
- /* We have to determine the final block of this node... except for constants. */
+ /* 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)) {
dca = consumer_dom_dca (dca, get_irn_out(n, i), n);
}
set_nodes_Block(n, dca);
-#if 0
- move_out_of_loops (n, dca);
-#endif
+
+ move_out_of_loops (n, early);
}
}
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 ();
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++) {
- pred = get_Block_cfgpred(b, i);
max_preds += test_whether_dispensable(b, i);
}
in = (ir_node **) malloc(max_preds * sizeof(ir_node *));
-
/** Debug output **
printf(" working on "); DDMN(b);
for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
printf(" removing pred %i ", i); DDMN(pred);
} else { printf(" Nothing to do for "); DDMN(pred); }
}
- ** end Debug output **/
+ ** end Debug output **/
/** Fix the Phi nodes **/
phi = get_irn_link(b);
projects / libfirm / blobdiff