# 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);
void
optimize_in_place_wrapper (ir_node *n, void *env) {
- int start, i;
+ int i;
ir_node *optimized;
- if (get_irn_op(n) == op_Block)
- start = 0;
- else
- start = -1;
-
- /* optimize all sons after recursion, i.e., the sons' sons are
- optimized already. */
- for (i = start; i < get_irn_arity(n); i++) {
+ for (i = 0; i < get_irn_arity(n); i++) {
optimized = optimize_in_place_2(get_irn_n(n, i));
set_irn_n(n, i, optimized);
- assert(get_irn_op(optimized) != op_Id);
+ }
+
+ if (get_irn_op(n) == op_Block) {
+ optimized = optimize_in_place_2(n);
+ if (optimized != n) exchange (n, optimized);
}
}
/********************************************************************/
/* Remeber the new node in the old node by using a field all nodes have. */
-inline void
+INLINE void
set_new_node (ir_node *old, ir_node *new)
{
old->link = new;
}
/* Get this new node, before the old node is forgotton.*/
-inline ir_node *
+INLINE ir_node *
get_new_node (ir_node * n)
{
return n->link;
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. */
-inline int
+INLINE int
compute_new_arity(ir_node *b) {
int i, res;
int irg_v, block_v;
}
}
+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) {
new_arity = get_irn_arity(n);
}
}
- nn = new_ir_node(current_ir_graph,
+ nn = new_ir_node(get_irn_dbg_info(n),
+ current_ir_graph,
block,
get_irn_op(n),
get_irn_mode(n),
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, *on;
+ ir_node *nn, *block;
int i, j;
nn = get_new_node(n);
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 */
oe = get_irg_end(current_ir_graph);
/* copy the end node by hand, allocate dynamic in array! */
- ne = new_ir_node(current_ir_graph,
+ ne = new_ir_node(get_irn_dbg_info(oe),
+ current_ir_graph,
NULL,
op_End,
mode_X,
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);
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_unknown(current_ir_graph)) == NULL) {
+ copy_node(get_irg_unknown(current_ir_graph), NULL);
+ copy_preds(get_irg_unknown(current_ir_graph), NULL);
+ }
+ set_irg_unknown(current_ir_graph, get_new_node(get_irg_unknown(current_ir_graph)));
}
/* Copies all reachable nodes to a new obstack. Removes bad inputs
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,
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;
ir_node **res_pred;
ir_node **cf_pred;
ir_node *ret, *phi;
- ir_node *cf_op, *bl;
- int arity, n_ret, n_exc, n_res, i, j;
- type *called_frame, *caller_frame;
+ ir_node *cf_op = NULL, *bl;
+ int arity, n_ret, n_exc, n_res, i, j, rem_opt;
+ type *called_frame;
- if (!get_opt_inline()) return;
+ if (!get_optimize() || !get_opt_inline()) return;
+ /** Turn off optimizations, this can cause problems when allocating new nodes. **/
+ rem_opt = get_optimize();
+ set_optimize(0);
/* Handle graph state */
assert(get_irg_phase_state(current_ir_graph) != phase_building);
+ assert(get_irg_pinned(current_ir_graph) == pinned);
+ assert(get_irg_pinned(called_graph) == pinned);
if (get_irg_outs_state(current_ir_graph) == outs_consistent)
set_irg_outs_inconsistent(current_ir_graph);
/** Check preconditions **/
assert(get_irn_op(call) == op_Call);
- assert(get_Call_type(call) == get_entity_type(get_irg_ent(called_graph)));
+ /* assert(get_Call_type(call) == get_entity_type(get_irg_ent(called_graph))); */
+ /*
+ @@@ TODO does not work for InterfaceIII.java after cgana
+ 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 */
in[1] = get_Call_mem(call);
in[2] = get_irg_frame(current_ir_graph);
in[3] = get_irg_globals(current_ir_graph);
- in[4] = new_Tuple (get_Call_n_params(call),
- get_Call_param_arr(call));
+ in[4] = new_Tuple (get_Call_n_params(call), get_Call_param_arr(call));
pre_call = new_Tuple(5, in);
post_call = call;
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
- calling graph and pre_calls block as new block for the start block
- of calling graph.
- Further mark these nodes so that they are not visited by the
- copying. */
+ calling graph and pre_calls block as new block for the start block
+ of calling graph.
+ Further mark these nodes so that they are not visited by the
+ 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));/***/
/* Initialize for compaction of in arrays */
inc_irg_block_visited(current_ir_graph);
- /*
- set_Block_block_visited(get_irg_start_block(called_graph),
- get_irg_block_visited(current_ir_graph) +1 +1); /* count for self edge */
/*** Replicate local entities of the called_graph ***/
/* copy the entities. */
called_frame = get_irg_frame_type(called_graph);
- for (i = 0; i < get_class_n_member(called_frame); i++) {
+ for (i = 0; i < get_class_n_members(called_frame); i++) {
entity *new_ent, *old_ent;
old_ent = get_class_member(called_frame, i);
new_ent = copy_entity_own(old_ent, get_cur_frame_type());
entities. */
/* @@@ endless loops are not copied!! */
irg_walk(get_irg_end(called_graph), copy_node_inline, copy_preds,
- get_irg_frame_type(called_graph));
+ get_irg_frame_type(called_graph));
/* Repair called_graph */
set_irg_visited(called_graph, get_irg_visited(current_ir_graph));
end_bl = get_new_node(get_irg_end_block(called_graph));
end = get_new_node(get_irg_end(called_graph));
arity = get_irn_arity(end_bl); /* arity = n_exc + n_ret */
- n_res = get_method_n_res(get_Call_type(call));
+ n_res = get_method_n_ress(get_Call_type(call));
res_pred = (ir_node **) malloc (n_res * sizeof (ir_node *));
cf_pred = (ir_node **) malloc (arity * sizeof (ir_node *));
for (j = 0; j < n_res; j++) {
n_ret = 0;
for (i = 0; i < arity; i++) {
- ret = get_irn_n(end_bl, i);
- if (get_irn_op(ret) == op_Return) {
- cf_pred[n_ret] = get_Return_res(ret, j);
- n_ret++;
- }
+ ret = get_irn_n(end_bl, i);
+ if (get_irn_op(ret) == op_Return) {
+ cf_pred[n_ret] = get_Return_res(ret, j);
+ n_ret++;
+ }
}
phi = new_Phi(n_ret, cf_pred, get_irn_mode(cf_pred[0]));
res_pred[j] = phi;
}
}
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;
ir_node *ret;
ret = skip_Proj(get_irn_n(end_bl, i));
if (get_irn_op(ret) == op_Call) {
- cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_Block(ret), ret, mode_M, 3);
- n_exc++;
+ cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_Block(ret), ret, mode_M, 3);
+ n_exc++;
} else if (is_fragile_op(ret)) {
- /* We rely that all cfops have the memory output at the same position. */
- cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_Block(ret), ret, mode_M, 0);
- n_exc++;
+ /* We rely that all cfops have the memory output at the same position. */
+ cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_Block(ret), ret, mode_M, 0);
+ n_exc++;
} else if (get_irn_op(ret) == op_Raise) {
- cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_Block(ret), ret, mode_M, 1);
- n_exc++;
+ cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_Block(ret), ret, mode_M, 1);
+ n_exc++;
}
}
set_Tuple_pred(call, 3, new_Phi(n_exc, cf_pred, mode_M));
if (get_irn_op(cf_op) == op_Proj) {
cf_op = get_Proj_pred(cf_op);
if (get_irn_op(cf_op) == op_Tuple) {
- cf_op = get_Tuple_pred(cf_op, 1);
- assert(get_irn_op(cf_op) == op_Jmp);
- break;
+ cf_op = get_Tuple_pred(cf_op, 1);
+ assert(get_irn_op(cf_op) == op_Jmp);
+ break;
}
}
}
set_irn_in(end_bl, arity, cf_pred);
free(cf_pred);
}
+
+ /** Turn cse back on. **/
+ set_optimize(rem_opt);
}
/********************************************************************/
if (!(get_optimize() && get_opt_inline())) return;
- /*DDME(get_irg_ent(current_ir_graph));*/
+ //DDME(get_irg_ent(current_ir_graph));
current_ir_graph = irg;
/* Handle graph state */
tv = get_Const_tarval(get_Call_ptr(calls[i]));
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);
}
}
Start, Call and end at pinned nodes as Store, Call. Place_early
places all floating nodes reachable from its argument through floating
nodes and adds all beginnings at pinned nodes to the worklist. */
-inline void place_early () {
- int i;
- bool del_me;
-
+INLINE void place_early () {
assert(worklist);
inc_irg_visited(current_ir_graph);
static ir_node *
consumer_dom_dca (ir_node *dca, ir_node *consumer, ir_node *producer)
{
- ir_node *block;
+ ir_node *block = NULL;
/* Compute the latest block into which we can place a node so that it is
before consumer. */
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);
}
}
}
}
-inline void place_late() {
+INLINE void place_late() {
assert(worklist);
inc_irg_visited(current_ir_graph);
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 ();
}
static void collect_nodes(ir_node *n, void *env) {
- int i;
if (is_no_Block(n)) {
ir_node *b = get_nodes_Block(n);
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);
if (get_irg_dom_state(current_ir_graph) == dom_consistent)
set_irg_dom_inconsistent(current_ir_graph);
- //DDME(get_irg_ent(irg));
-
/* Use block visited flag to mark non-empty blocks. */
inc_irg_block_visited(irg);
irg_walk(end, merge_blocks, collect_nodes, NULL);
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 (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);
ARR_APP1 (ir_node *, in, ka);
}
}
+ }
/* DEL_ARR_F(end->in); GL @@@ tut nicht ! */
end->in = in;
projects / libfirm / blobdiff