/* apply optimizations of iropt to all nodes. */
/*------------------------------------------------------------------*/
-static void init_link (ir_node *n, void *env) {
- set_irn_link(n, NULL);
-}
-
-#if 0 /* Old version. Avoids Ids.
- This is not necessary: we do a post walk, and get_irn_n
- removes ids anyways. So it's much cheaper to call the
- optimization less often and use the exchange() algorithm. */
-static void
-optimize_in_place_wrapper (ir_node *n, void *env) {
- int i, irn_arity;
- ir_node *optimized, *old;
-
- irn_arity = get_irn_arity(n);
- for (i = 0; i < irn_arity; i++) {
- /* get_irn_n skips Id nodes, so comparison old != optimized does not
- show all optimizations. Therefore always set new predecessor. */
- old = get_irn_intra_n(n, i);
- optimized = optimize_in_place_2(old);
- set_irn_n(n, i, optimized);
- }
-
- if (get_irn_op(n) == op_Block) {
- optimized = optimize_in_place_2(n);
- if (optimized != n) exchange (n, optimized);
- }
-}
-#else
-static void
-optimize_in_place_wrapper (ir_node *n, void *env) {
+/**
+ * A wrapper around optimize_inplace_2() to be called from a walker.
+ */
+static void optimize_in_place_wrapper (ir_node *n, void *env) {
ir_node *optimized = optimize_in_place_2(n);
if (optimized != n) exchange (n, optimized);
}
-#endif
-
static INLINE void do_local_optimize(ir_node *n) {
/* Handle graph state */
current_ir_graph->value_table = new_identities();
/* walk over the graph */
- irg_walk(n, init_link, optimize_in_place_wrapper, NULL);
+ irg_walk(n, firm_clear_link, optimize_in_place_wrapper, NULL);
}
void local_optimize_node(ir_node *n) {
static void kill_dead_blocks(ir_node *block, void *env)
{
if (get_Block_dom_depth(block) < 0)
- set_Block_dead(block);
+ if (block != get_irg_end_block(current_ir_graph)) {
+ /* we don't want that the end block of graphs with
+ endless loops is marked bad (although it is of course */
+ set_Block_dead(block);
+ }
}
void
if (get_irg_dom_state(current_ir_graph) == dom_consistent)
irg_block_walk_graph(irg, NULL, kill_dead_blocks, NULL);
- do_local_optimize(irg->end);
+ do_local_optimize(get_irg_end(irg));
current_ir_graph = rem;
}
+/**
+ * Data flow optimization walker.
+ */
+static void opt_walker(ir_node *n, void *env) {
+ pdeq *waitq = env;
+ ir_node *optimized;
+
+ optimized = optimize_in_place_2(n);
+ set_irn_link(optimized, NULL);
+
+ if (optimized != n) {
+ const ir_edge_t *edge;
+
+ exchange(n, optimized);
+ foreach_out_edge(optimized, edge) {
+ ir_node *succ = get_edge_src_irn(edge);
+
+ if (get_irn_link(succ) != waitq) {
+ pdeq_putr(waitq, succ);
+ set_irn_link(succ, waitq);
+ }
+ }
+ }
+}
+
+void optimize_graph_df(ir_graph *irg) {
+ pdeq *waitq = new_pdeq();
+ int state = edges_activated(irg);
+
+ if (! state)
+ edges_activate(irg);
+
+ if (get_opt_global_cse())
+ set_irg_pinned(current_ir_graph, op_pin_state_floats);
+
+ /* Clean the value_table in irg for the CSE. */
+ del_identities(irg->value_table);
+ irg->value_table = new_identities();
+
+ if (get_irg_dom_state(current_ir_graph) == dom_consistent)
+ irg_block_walk_graph(irg, NULL, kill_dead_blocks, NULL);
+
+ /* invalidate info */
+ set_irg_outs_inconsistent(irg);
+ set_irg_doms_inconsistent(irg);
+ set_irg_loopinfo_inconsistent(irg);
+
+ /* walk over the graph */
+ irg_walk_graph(irg, NULL, opt_walker, waitq);
+
+ /* finish the wait queue */
+ while (! pdeq_empty(waitq)) {
+ ir_node *n = pdeq_getl(waitq);
+ opt_walker(n, waitq);
+ }
+
+ del_pdeq(waitq);
+
+ if (! state)
+ edges_deactivate(irg);
+}
+
/*------------------------------------------------------------------*/
/* Routines for dead node elimination / copying garbage collection */
ir_node *oe, *ne, *ob, *nb, *om, *nm; /* old end, new end, old bad, new bad, old NoMem, new NoMem */
ir_node *ka; /* keep alive */
int i, irn_arity;
+ unsigned long vfl;
+
+ /* Some nodes must be copied by hand, sigh */
+ vfl = get_irg_visited(irg);
+ set_irg_visited(irg, vfl + 1);
oe = get_irg_end(irg);
+ mark_irn_visited(oe);
/* copy the end node by hand, allocate dynamic in array! */
ne = new_ir_node(get_irn_dbg_info(oe),
irg,
/* copy the Bad node */
ob = get_irg_bad(irg);
+ mark_irn_visited(ob);
nb = new_ir_node(get_irn_dbg_info(ob),
irg,
NULL,
mode_T,
0,
NULL);
+ copy_node_attr(ob, nb);
set_new_node(ob, nb);
/* copy the NoMem node */
om = get_irg_no_mem(irg);
+ mark_irn_visited(om);
nm = new_ir_node(get_irn_dbg_info(om),
irg,
NULL,
mode_M,
0,
NULL);
+ copy_node_attr(om, nm);
set_new_node(om, nm);
/* copy the live nodes */
+ set_irg_visited(irg, vfl);
irg_walk(get_nodes_block(oe), copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
+
+ /* Note: from yet, the visited flag of the graph is equal to vfl + 1 */
+
+ /* visit the anchors as well */
+ for (i = anchor_max - 1; i >= 0; --i) {
+ ir_node *n = irg->anchors[i];
+
+ if (n && (get_irn_visited(n) <= vfl)) {
+ set_irg_visited(irg, vfl);
+ irg_walk(n, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
+ }
+ }
+
/* copy_preds for the end node ... */
set_nodes_block(ne, get_new_node(get_nodes_block(oe)));
for (i = 0; i < irn_arity; i++) {
ka = get_irn_intra_n(oe, i);
if (is_Block(ka) &&
- (get_irn_visited(ka) < get_irg_visited(irg))) {
+ (get_irn_visited(ka) <= vfl)) {
/* We must keep the block alive and copy everything reachable */
- set_irg_visited(irg, get_irg_visited(irg)-1);
+ set_irg_visited(irg, vfl);
irg_walk(ka, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
add_End_keepalive(ne, get_new_node(ka));
}
for (i = 0; i < irn_arity; i++) {
ka = get_irn_intra_n(oe, i);
if (!is_Block(ka)) {
- if (get_irn_visited(ka) < get_irg_visited(irg)) {
+ if (get_irn_visited(ka) <= vfl) {
/* We didn't copy the node yet. */
- set_irg_visited(irg, get_irg_visited(irg)-1);
+ set_irg_visited(irg, vfl);
irg_walk(ka, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
}
add_End_keepalive(ne, get_new_node(ka));
copy_graph_env (int copy_node_nr) {
ir_graph *irg = current_ir_graph;
ir_node *old_end, *n;
+ int i;
+
+ /* remove end_except and end_reg nodes */
+ old_end = get_irg_end(irg);
+ set_irg_end_except (irg, old_end);
+ set_irg_end_reg (irg, old_end);
+
/* Not all nodes remembered in irg 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. */
- set_irn_link(get_irg_frame (irg), NULL);
- set_irn_link(get_irg_globals (irg), NULL);
- set_irn_link(get_irg_args (irg), NULL);
- set_irn_link(get_irg_initial_mem(irg), NULL);
- set_irn_link(get_irg_bad (irg), NULL);
- set_irn_link(get_irg_no_mem (irg), NULL);
+ for (i = anchor_max - 1; i >= 0; --i)
+ if (irg->anchors[i])
+ set_new_node(irg->anchors[i], NULL);
/* we use the block walk flag for removing Bads from Blocks ins. */
inc_irg_block_visited(irg);
/* fix the fields in irg */
old_end = get_irg_end(irg);
- set_irg_end (irg, get_new_node(old_end));
- set_irg_end_except (irg, get_irg_end(irg));
- set_irg_end_reg (irg, get_irg_end(irg));
- free_End(old_end);
- set_irg_end_block (irg, get_new_node(get_irg_end_block(irg)));
-
- n = get_irg_frame(irg);
- if (!has_new_node(n)) {
- copy_node (n, INT_TO_PTR(copy_node_nr));
- copy_preds(n, NULL);
+ for (i = anchor_max - 1; i >= 0; --i) {
+ n = irg->anchors[i];
+ if (n)
+ irg->anchors[i] = get_new_node(n);
}
- n = get_irg_globals(irg);
- if (!has_new_node(n)) {
- copy_node (n, INT_TO_PTR(copy_node_nr));
- copy_preds(n, NULL);
- }
- n = get_irg_initial_mem(irg);
- if (!has_new_node(n)) {
- copy_node (n, INT_TO_PTR(copy_node_nr));
- copy_preds(n, NULL);
- }
- n = get_irg_args(irg);
- if (!has_new_node(n)) {
- copy_node (n, INT_TO_PTR(copy_node_nr));
- copy_preds(n, NULL);
- }
- n = get_irg_bad(irg);
- if (!has_new_node(n)) {
- copy_node(n, INT_TO_PTR(copy_node_nr));
- copy_preds(n, NULL);
- }
- n = get_irg_no_mem(irg);
- if (!has_new_node(n)) {
- copy_node(n, INT_TO_PTR(copy_node_nr));
- copy_preds(n, NULL);
- }
- set_irg_start (irg, get_new_node(get_irg_start(irg)));
- set_irg_start_block(irg, get_new_node(get_irg_start_block(irg)));
- set_irg_frame (irg, get_new_node(get_irg_frame(irg)));
- set_irg_globals (irg, get_new_node(get_irg_globals(irg)));
- set_irg_initial_mem(irg, get_new_node(get_irg_initial_mem(irg)));
- set_irg_args (irg, get_new_node(get_irg_args(irg)));
- set_irg_bad (irg, get_new_node(get_irg_bad(irg)));
- set_irg_no_mem (irg, get_new_node(get_irg_no_mem(irg)));
+ free_End(old_end);
}
/**
rebirth_obst = xmalloc (sizeof(*rebirth_obst));
current_ir_graph->obst = rebirth_obst;
obstack_init (current_ir_graph->obst);
+ current_ir_graph->last_node_idx = 0;
/* We also need a new hash table for cse */
del_identities (irg->value_table);
* changes).
*/
void remove_bad_predecessors(ir_graph *irg) {
- irg_walk_graph(irg, init_link, relink_bad_predecessors, NULL);
+ irg_walk_graph(irg, firm_clear_link, relink_bad_predecessors, NULL);
}
/*
- __ _ __ __
- (_ __ o _ | \/ |_
- __)|_| | \_/ | \_/(/_ |_/\__|__
+ __ _ __ __
+ (_ __ o _ | \/ |_
+ __)|_| | \_/ | \_/(/_ |_/\__|__
The following stuff implements a facility that automatically patches
registered ir_node pointers to the new node when a dead node elimination occurs.
*/
struct _survive_dce_t {
- struct obstack obst;
- pmap *places;
- pmap *new_places;
- hook_entry_t dead_node_elim;
- hook_entry_t dead_node_elim_subst;
+ struct obstack obst;
+ pmap *places;
+ pmap *new_places;
+ hook_entry_t dead_node_elim;
+ hook_entry_t dead_node_elim_subst;
};
typedef struct _survive_dce_list_t {
- struct _survive_dce_list_t *next;
- ir_node **place;
+ struct _survive_dce_list_t *next;
+ ir_node **place;
} survive_dce_list_t;
static void dead_node_hook(void *context, ir_graph *irg, int start)
{
- survive_dce_t *sd = context;
-
- /* Create a new map before the dead node elimination is performed. */
- if(start) {
- sd->new_places = pmap_create_ex(pmap_count(sd->places));
- }
-
- /* Patch back all nodes if dead node elimination is over and something is to be done. */
- else {
- pmap_destroy(sd->places);
- sd->places = sd->new_places;
- sd->new_places = NULL;
- }
+ survive_dce_t *sd = context;
+
+ /* Create a new map before the dead node elimination is performed. */
+ if (start) {
+ sd->new_places = pmap_create_ex(pmap_count(sd->places));
+ }
+
+ /* Patch back all nodes if dead node elimination is over and something is to be done. */
+ else {
+ pmap_destroy(sd->places);
+ sd->places = sd->new_places;
+ sd->new_places = NULL;
+ }
}
+/**
+ * Hook called when dead node elimination replaces old by nw.
+ */
static void dead_node_subst_hook(void *context, ir_graph *irg, ir_node *old, ir_node *nw)
{
- survive_dce_t *sd = context;
- survive_dce_list_t *list = pmap_get(sd->places, old);
+ survive_dce_t *sd = context;
+ survive_dce_list_t *list = pmap_get(sd->places, old);
- /* If the node is to be patched back, write the new address to all registered locations. */
- if(list) {
- survive_dce_list_t *p;
+ /* If the node is to be patched back, write the new address to all registered locations. */
+ if (list) {
+ survive_dce_list_t *p;
- for(p = list; p; p = p->next)
- *(p->place) = nw;
+ for(p = list; p; p = p->next)
+ *(p->place) = nw;
- pmap_insert(sd->new_places, nw, list);
- }
+ pmap_insert(sd->new_places, nw, list);
+ }
}
/**
*/
survive_dce_t *new_survive_dce(void)
{
- survive_dce_t *res = xmalloc(sizeof(res[0]));
- obstack_init(&res->obst);
- res->places = pmap_create();
- res->new_places = NULL;
-
- res->dead_node_elim.hook._hook_dead_node_elim = dead_node_hook;
- res->dead_node_elim.context = res;
- res->dead_node_elim.next = NULL;
-
- res->dead_node_elim_subst.hook._hook_dead_node_elim_subst = dead_node_subst_hook;
- res->dead_node_elim_subst.context = res;
- res->dead_node_elim_subst.next = NULL;
-
- register_hook(hook_dead_node_elim, &res->dead_node_elim);
- register_hook(hook_dead_node_elim_subst, &res->dead_node_elim_subst);
- return res;
+ survive_dce_t *res = xmalloc(sizeof(res[0]));
+ obstack_init(&res->obst);
+ res->places = pmap_create();
+ res->new_places = NULL;
+
+ res->dead_node_elim.hook._hook_dead_node_elim = dead_node_hook;
+ res->dead_node_elim.context = res;
+ res->dead_node_elim.next = NULL;
+
+ res->dead_node_elim_subst.hook._hook_dead_node_elim_subst = dead_node_subst_hook;
+ res->dead_node_elim_subst.context = res;
+ res->dead_node_elim_subst.next = NULL;
+
+ register_hook(hook_dead_node_elim, &res->dead_node_elim);
+ register_hook(hook_dead_node_elim_subst, &res->dead_node_elim_subst);
+ return res;
}
/**
*/
void free_survive_dce(survive_dce_t *sd)
{
- obstack_free(&sd->obst, NULL);
- pmap_destroy(sd->places);
- unregister_hook(hook_dead_node_elim, &sd->dead_node_elim);
- unregister_hook(hook_dead_node_elim_subst, &sd->dead_node_elim_subst);
- free(sd);
+ obstack_free(&sd->obst, NULL);
+ pmap_destroy(sd->places);
+ unregister_hook(hook_dead_node_elim, &sd->dead_node_elim);
+ unregister_hook(hook_dead_node_elim_subst, &sd->dead_node_elim_subst);
+ free(sd);
}
/**
*/
void survive_dce_register_irn(survive_dce_t *sd, ir_node **place)
{
- if(*place != NULL) {
- ir_node *irn = *place;
- survive_dce_list_t *curr = pmap_get(sd->places, irn);
- survive_dce_list_t *nw = obstack_alloc(&sd->obst, sizeof(nw));
+ if(*place != NULL) {
+ ir_node *irn = *place;
+ survive_dce_list_t *curr = pmap_get(sd->places, irn);
+ survive_dce_list_t *nw = obstack_alloc(&sd->obst, sizeof(nw));
- nw->next = curr;
- nw->place = place;
+ nw->next = curr;
+ nw->place = place;
- pmap_insert(sd->places, irn, nw);
- }
+ pmap_insert(sd->places, irn, nw);
+ }
}
/*--------------------------------------------------------------------*/