nsz Git - libfirm/blob - ir/be/beifg.c

   1 /**
   2  * Common use interference graph.
   3  * Originally written by Sebastian Hack. Refactored into a seperate
   4  * source file and header by Kimon Hoffmann.
   5  * @author Sebastian Hack
   6  * @date 27.06.2005
   7  */
   8
   9 #include <malloc.h>
  10 #include "debug.h"
  11
  12 #include "beifg_t.h"
  13
  14 #define IF_EDGE_HASH(e) ((e)->sourceNode)
  15 #define IF_NODE_HASH(n) ((n)->nodeNumber)
  16 #define IF_NODE_NEIGHBOUR_SLOTS 8
  17
  18 static int if_edge_cmp(const void* p1, const void* p2, size_t size) {
  19         const be_if_edge_t* e1 = p1;
  20         const be_if_edge_t* e2 = p2;
  21
  22         return !((e1->sourceNode == e2->sourceNode) && (e1->targetNode == e2->targetNode));
  23 }
  24
  25 static int if_node_cmp(const void* p1, const void* p2, size_t size) {
  26         const be_if_node_t* n1 = p1;
  27         const be_if_node_t* n2 = p2;
  28
  29         return (n1->nodeNumber != n2->nodeNumber);
  30 }
  31
  32 static INLINE be_if_edge_t *edge_init(be_if_edge_t* edge, int source, int target) {
  33         /* Bring the smaller entry to src. */
  34         if (source > target) {
  35                 edge->sourceNode = target;
  36                 edge->targetNode = source;
  37         } else {
  38                 edge->sourceNode = source;
  39                 edge->targetNode = target;
  40         }
  41         return edge;
  42 }
  43
  44 be_if_graph_t* be_ifg_new(int slots) {
  45         be_if_graph_t* graph = malloc(sizeof(*graph));
  46         graph->edges = new_set(if_edge_cmp, slots);
  47         graph->nodes = new_set(if_node_cmp, slots);
  48         return graph;
  49 }
  50
  51 void be_ifg_free(be_if_graph_t* graph) {
  52         be_if_node_t* ifn;
  53         for (ifn = set_first(graph->nodes); ifn; ifn = set_next(graph->nodes)) {
  54                 free(ifn->neighbourNodes);
  55                 ifn->neighbourNodes = 0;
  56         }
  57         free(graph->nodes);
  58         graph->nodes = 0;
  59         free(graph->edges);
  60         graph->edges = 0;
  61         free(graph);
  62 }
  63
  64 void be_ifg_add_interference(be_if_graph_t* graph, int source, int target) {
  65         /* insert edge */
  66         be_if_edge_t edge;
  67         edge_init(&edge, source, target);
  68         set_insert(graph->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge));
  69
  70         /* insert nodes */
  71         be_if_node_t node;
  72         node.nodeNumber = source;
  73         node.neighbourNodes = pset_new_ptr(IF_NODE_NEIGHBOUR_SLOTS);
  74         be_if_node_t* sourceNode = set_insert(graph->nodes, &node, sizeof(node), IF_NODE_HASH(&node));
  75         node.nodeNumber = target;
  76         node.neighbourNodes = pset_new_ptr(IF_NODE_NEIGHBOUR_SLOTS);
  77         be_if_node_t* targetNode = set_insert(graph->nodes, &node, sizeof(node), IF_NODE_HASH(&node));
  78
  79         /* insert neighbors into nodes */
  80         pset_insert_ptr(sourceNode->neighbourNodes, targetNode);
  81         pset_insert_ptr(targetNode->neighbourNodes, sourceNode);
  82 }
  83
  84 static INLINE int are_connected(const be_if_graph_t* graph, int source, int target) {
  85         be_if_edge_t edge;
  86         edge_init(&edge, source, target);
  87         return set_find(graph->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge)) != NULL;
  88 }
  89
  90 int be_ifg_has_edge(const be_if_graph_t* graph, const be_if_node_t* n1, const be_if_node_t* n2) {
  91         return are_connected(graph, n1->nodeNumber, n2->nodeNumber);
  92 }