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  * $Id$
   8  */
   9 #ifdef HAVE_CONFIG_H
  10 #include "config.h"
  11 #endif
  12
  13 #ifdef HAVE_MALLOC_H
  14 #include <malloc.h>
  15 #endif
  16 #ifdef HAVE_ALLOCA_H
  17 #include <alloca.h>
  18 #endif
  19
  20 #include <stdlib.h>
  21 #include "debug.h"
  22
  23 #include "beifg_t.h"
  24
  25 #define IF_EDGE_HASH(e) ((e)->sourceNode)
  26 #define IF_NODE_HASH(n) ((n)->nodeNumber)
  27 #define IF_NODE_NEIGHBOUR_SLOTS 8
  28
  29 static int if_edge_cmp(const void* p1, const void* p2, size_t size) {
  30         const be_if_edge_t* e1 = p1;
  31         const be_if_edge_t* e2 = p2;
  32
  33         return !((e1->sourceNode == e2->sourceNode) && (e1->targetNode == e2->targetNode));
  34 }
  35
  36 static int if_node_cmp(const void* p1, const void* p2, size_t size) {
  37         const be_if_node_t* n1 = p1;
  38         const be_if_node_t* n2 = p2;
  39
  40         return (n1->nodeNumber != n2->nodeNumber);
  41 }
  42
  43 static INLINE be_if_edge_t *edge_init(be_if_edge_t* edge, int source, int target) {
  44         /* Bring the smaller entry to src. */
  45         if (source > target) {
  46                 edge->sourceNode = target;
  47                 edge->targetNode = source;
  48         } else {
  49                 edge->sourceNode = source;
  50                 edge->targetNode = target;
  51         }
  52         return edge;
  53 }
  54
  55 be_if_graph_t* be_ifg_new(int slots) {
  56         be_if_graph_t* graph = malloc(sizeof(*graph));
  57         graph->edges = new_set(if_edge_cmp, slots);
  58         graph->nodes = new_set(if_node_cmp, slots);
  59         return graph;
  60 }
  61
  62 void be_ifg_free(be_if_graph_t* graph) {
  63         be_if_node_t* ifn;
  64         for (ifn = set_first(graph->nodes); ifn; ifn = set_next(graph->nodes)) {
  65                 free(ifn->neighbourNodes);
  66                 ifn->neighbourNodes = 0;
  67         }
  68         free(graph->nodes);
  69         graph->nodes = 0;
  70         free(graph->edges);
  71         graph->edges = 0;
  72         free(graph);
  73 }
  74
  75 void be_ifg_add_interference(be_if_graph_t* graph, int source, int target) {
  76         /* insert edge */
  77         be_if_edge_t edge;
  78         edge_init(&edge, source, target);
  79         set_insert(graph->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge));
  80
  81         /* insert nodes */
  82         be_if_node_t node;
  83         node.nodeNumber = source;
  84         node.neighbourNodes = pset_new_ptr(IF_NODE_NEIGHBOUR_SLOTS);
  85         be_if_node_t* sourceNode = set_insert(graph->nodes, &node, sizeof(node), IF_NODE_HASH(&node));
  86         node.nodeNumber = target;
  87         node.neighbourNodes = pset_new_ptr(IF_NODE_NEIGHBOUR_SLOTS);
  88         be_if_node_t* targetNode = set_insert(graph->nodes, &node, sizeof(node), IF_NODE_HASH(&node));
  89
  90         /* insert neighbors into nodes */
  91         pset_insert_ptr(sourceNode->neighbourNodes, targetNode);
  92         pset_insert_ptr(targetNode->neighbourNodes, sourceNode);
  93 }
  94
  95 static INLINE int are_connected(const be_if_graph_t* graph, int source, int target) {
  96         be_if_edge_t edge;
  97         edge_init(&edge, source, target);
  98         return set_find(graph->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge)) != NULL;
  99 }
 100
 101 int be_ifg_has_edge(const be_if_graph_t* graph, const be_if_node_t* n1, const be_if_node_t* n2) {
 102         return are_connected(graph, n1->nodeNumber, n2->nodeNumber);
 103 }