X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeifg.c;h=7f9a897380c16e0b6742502f0148e5a4097428ff;hb=7438ae082c9ec7658ccd006b40aa62084aedca2d;hp=6df89257220c067c64c2bd190d525f6fe6fc9e90;hpb=f4a2f61100d90e9caa870c496c30a6d222408d93;p=libfirm diff --git a/ir/be/beifg.c b/ir/be/beifg.c index 6df892572..7f9a89738 100644 --- a/ir/be/beifg.c +++ b/ir/be/beifg.c @@ -1,11 +1,14 @@ /** - * Common use interference graph. - * Originally written by Sebastian Hack. Refactored into a seperate - * source file and header by Kimon Hoffmann. + * @file beifg.c + * @date 18.11.2005 * @author Sebastian Hack - * @date 27.06.2005 - * $Id$ + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL */ + +#include + #ifdef HAVE_CONFIG_H #include "config.h" #endif @@ -13,91 +16,143 @@ #ifdef HAVE_MALLOC_H #include #endif + #ifdef HAVE_ALLOCA_H #include #endif -#include -#include "debug.h" - +#include "irnode_t.h" +#include "irprintf.h" #include "beifg_t.h" -#define IF_EDGE_HASH(e) ((e)->sourceNode) -#define IF_NODE_HASH(n) ((n)->nodeNumber) -#define IF_NODE_NEIGHBOUR_SLOTS 8 +size_t (be_ifg_nodes_iter_size)(const void *self) +{ + const be_ifg_t *ifg = self; + return ifg->impl->nodes_iter_size; +} + +size_t (be_ifg_neighbours_iter_size)(const void *self) +{ + const be_ifg_t *ifg = self; + return ifg->impl->neighbours_iter_size; +} -static int if_edge_cmp(const void* p1, const void* p2, size_t size) { - const be_if_edge_t* e1 = p1; - const be_if_edge_t* e2 = p2; +size_t (be_ifg_cliques_iter_size)(const void *self) +{ + const be_ifg_t *ifg = self; + return ifg->impl->cliques_iter_size; +} - return !((e1->sourceNode == e2->sourceNode) && (e1->targetNode == e2->targetNode)); +void (be_ifg_free)(void *self) +{ + be_ifg_t *ifg = self; + ifg->impl->free(self); } -static int if_node_cmp(const void* p1, const void* p2, size_t size) { - const be_if_node_t* n1 = p1; - const be_if_node_t* n2 = p2; +int (be_ifg_connected)(const void *self, const ir_node *a, const ir_node *b) +{ + const be_ifg_t *ifg = self; + return ifg->impl->connected(self, a, b); +} - return (n1->nodeNumber != n2->nodeNumber); +ir_node *(be_ifg_neighbours_begin)(const void *self, void *iter, const ir_node *irn) +{ + const be_ifg_t *ifg = self; + return ifg->impl->neighbours_begin(self, iter, irn); } -static INLINE be_if_edge_t *edge_init(be_if_edge_t* edge, int source, int target) { - /* Bring the smaller entry to src. */ - if (source > target) { - edge->sourceNode = target; - edge->targetNode = source; - } else { - edge->sourceNode = source; - edge->targetNode = target; - } - return edge; +ir_node *(be_ifg_neighbours_next)(const void *self, void *iter) +{ + const be_ifg_t *ifg = self; + return ifg->impl->neighbours_next(self, iter); } -be_if_graph_t* be_ifg_new(int slots) { - be_if_graph_t* graph = malloc(sizeof(*graph)); - graph->edges = new_set(if_edge_cmp, slots); - graph->nodes = new_set(if_node_cmp, slots); - return graph; +void (be_ifg_neighbours_break)(const void *self, void *iter) +{ + const be_ifg_t *ifg = self; + ifg->impl->neighbours_break(self, iter); } -void be_ifg_free(be_if_graph_t* graph) { - be_if_node_t* ifn; - for (ifn = set_first(graph->nodes); ifn; ifn = set_next(graph->nodes)) { - free(ifn->neighbourNodes); - ifn->neighbourNodes = 0; - } - free(graph->nodes); - graph->nodes = 0; - free(graph->edges); - graph->edges = 0; - free(graph); +ir_node *(be_ifg_nodes_begin)(const void *self, void *iter) +{ + const be_ifg_t *ifg = self; + return ifg->impl->nodes_begin(self, iter); +} + +ir_node *(be_ifg_nodes_next)(const void *self, void *iter) +{ + const be_ifg_t *ifg = self; + return ifg->impl->nodes_next(self, iter); +} + +void (be_ifg_nodes_break)(const void *self, void *iter) +{ + const be_ifg_t *ifg = self; + ifg->impl->nodes_break(self, iter); +} + +int (be_ifg_cliques_begin)(const void *self, void *iter, ir_node **buf) +{ + const be_ifg_t *ifg = self; + return ifg->impl->cliques_begin(self, iter, buf); } -void be_ifg_add_interference(be_if_graph_t* graph, int source, int target) { - /* insert edge */ - be_if_edge_t edge; - edge_init(&edge, source, target); - set_insert(graph->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge)); +int (be_ifg_cliques_next)(const void *self, void *iter) +{ + const be_ifg_t *ifg = self; + return ifg->impl->cliques_next(self, iter); +} - /* insert nodes */ - be_if_node_t node; - node.nodeNumber = source; - node.neighbourNodes = pset_new_ptr(IF_NODE_NEIGHBOUR_SLOTS); - be_if_node_t* sourceNode = set_insert(graph->nodes, &node, sizeof(node), IF_NODE_HASH(&node)); - node.nodeNumber = target; - node.neighbourNodes = pset_new_ptr(IF_NODE_NEIGHBOUR_SLOTS); - be_if_node_t* targetNode = set_insert(graph->nodes, &node, sizeof(node), IF_NODE_HASH(&node)); +void (be_ifg_cliques_break)(const void *self, void *iter) +{ + const be_ifg_t *ifg = self; + ifg->impl->cliques_break(self, iter); +} - /* insert neighbors into nodes */ - pset_insert_ptr(sourceNode->neighbourNodes, targetNode); - pset_insert_ptr(targetNode->neighbourNodes, sourceNode); +int (be_ifg_degree)(const void *self, const ir_node *irn) +{ + const be_ifg_t *ifg = self; + return ifg->impl->degree(self, irn); } -static INLINE int are_connected(const be_if_graph_t* graph, int source, int target) { - be_if_edge_t edge; - edge_init(&edge, source, target); - return set_find(graph->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge)) != NULL; + +int be_ifg_is_simplicial(const be_ifg_t *ifg, const ir_node *irn) +{ + int degree = be_ifg_degree(ifg, irn); + void *iter = be_ifg_neighbours_iter_alloca(ifg); + + ir_node **neighbours = malloc(degree * sizeof(neighbours[0])); + + ir_node *curr; + int i, j; + + be_ifg_foreach_neighbour(ifg, iter, irn, curr) + neighbours[i++] = curr; + + for(i = 0; i < degree; ++i) { + for(j = 0; j < i; ++j) + if(!be_ifg_connected(ifg, neighbours[i], neighbours[j])) { + free(neighbours); + return 0; + } + } + + + free(neighbours); + return 1; } -int be_ifg_has_edge(const be_if_graph_t* graph, const be_if_node_t* n1, const be_if_node_t* n2) { - return are_connected(graph, n1->nodeNumber, n2->nodeNumber); +void be_ifg_check(const be_ifg_t *ifg) +{ + void *iter1 = be_ifg_nodes_iter_alloca(ifg); + void *iter2 = be_ifg_neighbours_iter_alloca(ifg); + + ir_node *n, *m; + + /* Check, if all neighbours are indeed connected to the node. */ + be_ifg_foreach_node(ifg, iter1, n) { + be_ifg_foreach_neighbour(ifg, iter2, n, m) + if(!be_ifg_connected(ifg, n, m)) + ir_fprintf(stderr, "%+F is a neighbour of %+F but they are not connected!\n", n, m); + } }