X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeifg.c;h=7b2aaab74877b61246bed4f0f77b935539fc7176;hb=34e3b8d50bce639e760da7233524a4db85c80290;hp=3a70c32565c198ecb540b5723932fe6b9f7144fa;hpb=26b9008643da89a023fd6839ded5b9abf21ef328;p=libfirm diff --git a/ir/be/beifg.c b/ir/be/beifg.c index 3a70c3256..7b2aaab74 100644 --- a/ir/be/beifg.c +++ b/ir/be/beifg.c @@ -1,20 +1,6 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. - * * This file is part of libFirm. - * - * This file may be distributed and/or modified under the terms of the - * GNU General Public License version 2 as published by the Free Software - * Foundation and appearing in the file LICENSE.GPL included in the - * packaging of this file. - * - * Licensees holding valid libFirm Professional Edition licenses may use - * this file in accordance with the libFirm Commercial License. - * Agreement provided with the Software. - * - * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE - * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR - * PURPOSE. + * Copyright (C) 2012 University of Karlsruhe. */ /** @@ -51,17 +37,10 @@ void be_ifg_free(be_ifg_t *self) free(self); } -int be_ifg_connected(const be_ifg_t *ifg, const ir_node *a, const ir_node *b) -{ - be_lv_t *lv = be_get_irg_liveness(ifg->env->irg); - return be_values_interfere(lv, a, b); -} - static void nodes_walker(ir_node *bl, void *data) { nodes_iter_t *it = (nodes_iter_t*)data; struct list_head *head = get_block_border_head(it->env, bl); - border_t *b; foreach_border_head(head, b) { if (b->is_def && b->is_real) { @@ -71,61 +50,36 @@ static void nodes_walker(ir_node *bl, void *data) } } -static void find_nodes(const be_ifg_t *ifg, nodes_iter_t *iter) +nodes_iter_t be_ifg_nodes_begin(be_ifg_t const *const ifg) { - obstack_init(&iter->obst); - iter->n = 0; - iter->curr = 0; - iter->env = ifg->env; - - irg_block_walk_graph(ifg->env->irg, nodes_walker, NULL, iter); - obstack_ptr_grow(&iter->obst, NULL); - iter->nodes = (ir_node**)obstack_finish(&iter->obst); + nodes_iter_t iter; + obstack_init(&iter.obst); + iter.n = 0; + iter.curr = 0; + iter.env = ifg->env; + + irg_block_walk_graph(ifg->env->irg, nodes_walker, NULL, &iter); + obstack_ptr_grow(&iter.obst, NULL); + iter.nodes = (ir_node**)obstack_finish(&iter.obst); + return iter; } -static inline void node_break(nodes_iter_t *it, int force) +ir_node *be_ifg_nodes_next(nodes_iter_t *const it) { - if ((it->curr >= it->n || force) && it->nodes) { + if (it->curr < it->n) { + return it->nodes[it->curr++]; + } else { obstack_free(&it->obst, NULL); - it->nodes = NULL; + return NULL; } } -static ir_node *get_next_node(nodes_iter_t *it) -{ - ir_node *res = NULL; - - if (it->curr < it->n) - res = it->nodes[it->curr++]; - - node_break(it, 0); - - return res; -} - -ir_node *be_ifg_nodes_begin(const be_ifg_t *ifg, nodes_iter_t *iter) -{ - find_nodes(ifg, iter); - return get_next_node(iter); -} - -ir_node *be_ifg_nodes_next(nodes_iter_t *iter) -{ - return get_next_node(iter); -} - -void be_ifg_nodes_break(nodes_iter_t *iter) -{ - node_break(iter, 1); -} - static void find_neighbour_walker(ir_node *block, void *data) { neighbours_iter_t *it = (neighbours_iter_t*)data; struct list_head *head = get_block_border_head(it->env, block); be_lv_t *lv = be_get_irg_liveness(it->env->irg); - border_t *b; int has_started = 0; if (!be_is_live_in(lv, block, it->irn) && block != get_nodes_block(it->irn)) @@ -244,10 +198,9 @@ static inline int get_next_clique(cliques_iter_t *it) /* before shrinking the set, return the current maximal clique */ if (output_on_shrink) { int count = 0; - ir_node *irn; /* fill the output buffer */ - foreach_pset(it->living, ir_node*, irn) { + foreach_pset(it->living, ir_node, irn) { it->buf[count++] = irn; } @@ -273,10 +226,8 @@ static inline int get_next_clique(cliques_iter_t *it) int be_ifg_cliques_begin(const be_ifg_t *ifg, cliques_iter_t *it, ir_node **buf) { - ir_node *start_bl = get_irg_start_block(ifg->env->irg); - obstack_init(&it->ob); - dom_tree_walk(start_bl, get_blocks_dom_order, NULL, it); + dom_tree_walk_irg(ifg->env->irg, get_blocks_dom_order, NULL, it); it->cenv = ifg->env; it->buf = buf; @@ -317,65 +268,52 @@ be_ifg_t *be_create_ifg(const be_chordal_env_t *env) return ifg; } -static void int_comp_rec(be_ifg_t *ifg, ir_node *n, bitset_t *seen) +static bool consider_component_node(bitset_t *const seen, ir_node *const irn) { - neighbours_iter_t neigh_it; - ir_node *m; - - be_ifg_foreach_neighbour(ifg, &neigh_it, n, m) { - if (bitset_is_set(seen, get_irn_idx(m))) - continue; - - if (arch_get_irn_register_req(m)->type & arch_register_req_type_ignore) - continue; + if (bitset_is_set(seen, get_irn_idx(irn))) + return false; + bitset_set(seen, get_irn_idx(irn)); - bitset_set(seen, get_irn_idx(m)); - int_comp_rec(ifg, m, seen); - } + arch_register_req_t const *const req = arch_get_irn_register_req(irn); + if (arch_register_req_is(req, ignore)) + return false; + return true; } -static int int_component_stat(ir_graph *irg, be_ifg_t *ifg) +static void int_comp_rec(be_ifg_t *ifg, ir_node *n, bitset_t *seen) { - int n_comp = 0; - nodes_iter_t nodes_it; - bitset_t *seen = bitset_malloc(get_irg_last_idx(irg)); - - ir_node *n; - - be_ifg_foreach_node(ifg, &nodes_it, n) { - if (bitset_is_set(seen, get_irn_idx(n))) - continue; - - if (arch_get_irn_register_req(n)->type & arch_register_req_type_ignore) - continue; + neighbours_iter_t neigh_it; - ++n_comp; - bitset_set(seen, get_irn_idx(n)); - int_comp_rec(ifg, n, seen); + be_ifg_foreach_neighbour(ifg, &neigh_it, n, m) { + if (consider_component_node(seen, m)) + int_comp_rec(ifg, m, seen); } - - free(seen); - return n_comp; } void be_ifg_stat(ir_graph *irg, be_ifg_t *ifg, be_ifg_stat_t *stat) { - nodes_iter_t nodes_it; - neighbours_iter_t neigh_it; - bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg)); - ir_node *n, *m; - - memset(stat, 0, sizeof(stat[0])); - - be_ifg_foreach_node(ifg, &nodes_it, n) { - stat->n_nodes += 1; + size_t n_nodes = 0; + size_t n_edges = 0; + size_t n_comps = 0; + bitset_t *const seen = bitset_malloc(get_irg_last_idx(irg)); + be_ifg_foreach_node(ifg, n) { + ++n_nodes; + + neighbours_iter_t neigh_it; be_ifg_foreach_neighbour(ifg, &neigh_it, n, m) { - bitset_set(nodes, get_irn_idx(n)); - stat->n_edges += !bitset_is_set(nodes, get_irn_idx(m)); + ++n_edges; + } + + if (consider_component_node(seen, n)) { + ++n_comps; + int_comp_rec(ifg, n, seen); } } + free(seen); - stat->n_comps = int_component_stat(irg, ifg); - bitset_free(nodes); + stat->n_nodes = n_nodes; + /* Every interference edge was counted twice, once for each end. */ + stat->n_edges = n_edges / 2; + stat->n_comps = n_comps; }