X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeifg.h;h=dddb0b45b12c4c99c2ede0dc60f6c423648b46b6;hb=3f807bf48426a29da4129ff29c44a4b4690c45f6;hp=ec0c9c6d0c307d28f3619f51caf952b846c277dc;hpb=ea1fc4bc4471f4e92e8df1f5f62da9aa3b1685e7;p=libfirm diff --git a/ir/be/beifg.h b/ir/be/beifg.h index ec0c9c6d0..dddb0b45b 100644 --- a/ir/be/beifg.h +++ b/ir/be/beifg.h @@ -1,86 +1,105 @@ -/** - * Common use interference graph. - * Originally written by Sebastian Hack. Refactored into a seperate - * source file and header by Kimon Hoffmann. - * @author Sebastian Hack - * @date 27.06.2005 +/* + * 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. */ -#ifndef _BEIFG_H_ -#define _BEIFG_H_ - -typedef struct _be_if_graph_t be_if_graph_t; -typedef struct _be_if_node_t be_if_node_t; -typedef struct _be_if_edge_t be_if_edge_t; /** - * Creates a new interference graph with the specified number of - * initial slots. - * @param slots the initial number of slots used for hashing. - * Must be greater than 0. - * @return the created, empty interference graph. + * @file + * @brief Interface for interference graphs. + * @author Sebastian Hack + * @date 18.11.2005 + * @version $Id$ */ -be_if_graph_t* be_ifg_new(int slots); +#ifndef FIRM_BE_BEIFG_H +#define FIRM_BE_BEIFG_H -/** - * Frees the passed interference graph an all contained nodes. - * @param graph the interference graph that shall be freed. Please note - * that after a call to this function all pointers to the graph, - * its edges or its nodes are invalid. - */ -void be_ifg_free(be_if_graph_t* graph); +#include -/** - * Adds a new undirected interference edge between the two nodes - * specified by their node numbers. If the corresponding nodes do - * not yet exist in the iunterference grpah they are created pririor - * to creation of the edge. - * @param graph the graph to add the interference edge to. - * @param source the key of the source node. - * @param target the key of the target node. - */ -void be_ifg_add_interference(be_if_graph_t* graph, int source, int target); +#include "irnode.h" -/** - * Returns the set of all edges within the specified - * graph. - * @param graph the graph the return the set of edges of. - * @return A set of all edges within the specified graph as - * be_if_edge_t instances. - */ -set* be_get_ifg_edges(const be_if_graph_t* graph); +#include "becopyopt.h" +#include "beirg.h" -/** - * Returns the set of all nodes within the specified - * graph. - * @param graph the graph the return the set of nodes of. - * @return A set of all nodes within the specified graph as - * be_if_node_t instances. - */ -set* be_get_ifg_nodes(const be_if_graph_t* graph); +typedef struct _be_ifg_impl_t be_ifg_impl_t; +typedef struct _be_ifg_t be_ifg_t; -/** - * Returns whether the specified graph alreadz contains an undirected - * edge between the two passed nodes. - * @param graph the graph to which containment both nodes @p n1 and - * @p n2 belong. - * @param n1 the one end of the edge to query the graph for. - * @param n2 the other end of the edge. - * @return TRUE if the graph contains an edge between @p n1 and @p n2, - * otherwise FALSE. - */ -int be_ifg_has_edge(const be_if_graph_t* graph, const be_if_node_t* n1, const be_if_node_t* n2); +#define be_ifg_nodes_iter_alloca(self) (alloca(be_ifg_nodes_iter_size(self))) +#define be_ifg_neighbours_iter_alloca(self) (alloca(be_ifg_neighbours_iter_size(self))) +#define be_ifg_cliques_iter_alloca(self) (alloca(be_ifg_cliques_iter_size(self))) + +size_t (be_ifg_nodes_iter_size)(const be_ifg_t *self); +size_t (be_ifg_neighbours_iter_size)(const be_ifg_t *self); +size_t (be_ifg_cliques_iter_size)(const be_ifg_t *self); +void (be_ifg_free)(be_ifg_t *self); +int (be_ifg_connected)(const be_ifg_t *self, const ir_node *a, const ir_node *b); +ir_node *(be_ifg_neighbours_begin)(const be_ifg_t *self, void *iter, const ir_node *irn); +ir_node *(be_ifg_neighbours_next)(const be_ifg_t *self, void *iter); +void (be_ifg_neighbours_break)(const be_ifg_t *self, void *iter); +ir_node *(be_ifg_nodes_begin)(const be_ifg_t *self, void *iter); +ir_node *(be_ifg_nodes_next)(const be_ifg_t *self, void *iter); +void (be_ifg_nodes_break)(const be_ifg_t *self, void *iter); +int (be_ifg_cliques_begin)(const be_ifg_t *self, void *iter, ir_node **buf); +int (be_ifg_cliques_next)(const be_ifg_t *self, void *iter); +void (be_ifg_cliques_break)(const be_ifg_t *self, void *iter); +int (be_ifg_degree)(const be_ifg_t *self, const ir_node *irn); + +#define be_ifg_foreach_neighbour(self, iter, irn, pos) \ + for(pos = be_ifg_neighbours_begin(self, iter, irn); (pos); pos = be_ifg_neighbours_next(self, iter)) + +#define be_ifg_foreach_node(self, iter, pos) \ + for(pos = be_ifg_nodes_begin(self, iter); (pos); pos = be_ifg_nodes_next(self, iter)) + +#define be_ifg_foreach_clique(self, iter, buf, count) \ + for(*(count) = be_ifg_cliques_begin(self, iter, buf); \ + *(count) != -1 ; \ + *(count) = be_ifg_cliques_next(self, iter)) + +typedef struct { + int n_nodes; + int n_edges; + int n_comps; +} be_ifg_stat_t; + +void be_ifg_stat(be_irg_t *birg, be_ifg_t *ifg, be_ifg_stat_t *stat); -#define be_ifn_get_degree(ifnode) \ - pset_count(ifnode->neighb) +be_ifg_t *be_create_ifg(const be_chordal_env_t *env); -#define be_ifn_foreach_neighbour(ifnode, curr) \ - for (curr = pset_first(ifnode->neighbourNodes); curr; curr = pset_next(ifnode->neighbourNodes)) +/* + ____ _ + | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _ + | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` | + | |_| | |_| | | | | | | |_) | | | | | (_| | + |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, | + |_| |___/ +*/ -#define be_ifg_foreach_node(ifgraph, curr) \ - for (curr = set_first(ifgraph->nodes); curr; curr = set_next(ifgraph->nodes)) +typedef struct _be_ifg_dump_dot_cb_t { + int (*is_dump_node)(void *self, ir_node *irn); + void (*graph_attr)(FILE *f, void *self); + void (*node_attr)(FILE *f, void *self, ir_node *irn); + void (*edge_attr)(FILE *f, void *self, ir_node *from, ir_node *to); + void (*at_begin)(FILE *file, void *self); + void (*at_end)(FILE *file, void *self); +} be_ifg_dump_dot_cb_t; -#define be_ifg_foreach_edge(ifgraph, curr) \ - for (curr = set_first(ifgraph->edges); curr; curr = set_next(ifgraph->edges)) +void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self); +void be_ifg_check_sorted(const be_ifg_t *ifg); +void be_ifg_check_sorted_to_file(const be_ifg_t *ifg, FILE *f); +void be_ifg_check_performance(be_chordal_env_t *chordal_env); -#endif /*_BEIFG_H_*/ +#endif /* FIRM_BE_BEIFG_H */