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