# include "irgmod.h"
# include "array.h"
# include "pset.h"
-# include "pdeq.h" /* provisorisch fuer code placement */
+# include "pdeq.h" /* Fuer code placement */
# include "irouts.h"
/* Defined in iropt.c */
void del_identities (pset *value_table);
void add_identities (pset *value_table, ir_node *node);
-#if 0 /* Warum ist das hier nochmal definiert?
- Hat's nicht gelinkt wegen typeO tities - tity ?? */
-/* To fill the hash table */
-void
-add_identity (pset *value_table, ir_node *n) {
- /* identify_remember (value_table, n);*/
-}
-#endif
-
/********************************************************************/
/* apply optimizations of iropt to all nodes. */
/********************************************************************/
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);
}
}
set_irg_pinned(current_ir_graph, floats);
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);
/* Clean the value_table in irg for the cse. */
del_identities(irg->value_table);
/********************************************************************/
/* 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;
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),
Spare the Bad predecessors of Phi and Block nodes. */
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);
void
copy_graph () {
ir_node *oe, *ne; /* old end, new end */
- ir_node *ka; /* keep alive */
+ ir_node *ka; /* keep alive */
int i;
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,
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
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))); */
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
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 *));
+ res_pred = (ir_node **) malloc (n_res * sizeof (ir_node *));
cf_pred = (ir_node **) malloc (arity * sizeof (ir_node *));
set_irg_current_block(current_ir_graph, post_bl); /* just to make sure */
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;
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);
}
/********************************************************************/
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. */
}
}
-inline void place_late() {
+INLINE void place_late() {
assert(worklist);
inc_irg_visited(current_ir_graph);
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. */
+/* */
+/********************************************************************/
+
+
+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++)
+ set_Block_cfgpred(n, i, skip_Tuple(get_Block_cfgpred(n, i)));
+ } else if (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. */
+ if (get_optimize() && get_opt_control_flow()) exchange (b, new);
+ b = new;
+ new = equivalent_node(b);
+ }
+ if (is_Bad(new)) exchange (n, new_Bad());
+ }
+}
+
+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 */
+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;
+}
+
+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()) {
+ /* 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;
+}
+
+void optimize_blocks(ir_node *b, void *env) {
+ int i, j, k, max_preds, n_preds;
+ ir_node *pred, *phi;
+ ir_node **in;
+
+ 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++) {
+ 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++;
+ }
+#if 0
+ /* @@@ hier brauche ich schleifeninformation!!! Wenn keine Rueckwaertskante
+ dann darfs auch keine Verwendung geben. */
+ 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, is aber doch semantisch falsch! */
+ }
+#endif
+ } 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);
+ }
+
+ /** Move Phi nodes from removed blocks to this one.
+ 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!!! Kontrllflusskante
+ 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;
+}
projects / libfirm / blobdiff