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

   1 /**
   2  * @file   beifg.c
   3  * @date   18.11.2005
   4  * @author Sebastian Hack
   5  *
   6  * Copyright (C) 2005 Universitaet Karlsruhe
   7  * Released under the GPL
   8  */
   9
  10 #include <stdlib.h>
  11
  12 #ifdef HAVE_CONFIG_H
  13 #include "config.h"
  14 #endif
  15
  16 #ifdef HAVE_MALLOC_H
  17 #include <malloc.h>
  18 #endif
  19
  20 #ifdef HAVE_ALLOCA_H
  21 #include <alloca.h>
  22 #endif
  23
  24 #include "bitset.h"
  25
  26 #include "irnode_t.h"
  27 #include "irprintf.h"
  28 #include "beifg_t.h"
  29
  30 size_t (be_ifg_nodes_iter_size)(const void *self)
  31 {
  32         const be_ifg_t *ifg = self;
  33         return ifg->impl->nodes_iter_size;
  34 }
  35
  36 size_t (be_ifg_neighbours_iter_size)(const void *self)
  37 {
  38         const be_ifg_t *ifg = self;
  39         return ifg->impl->neighbours_iter_size;
  40 }
  41
  42 size_t (be_ifg_cliques_iter_size)(const void *self)
  43 {
  44         const be_ifg_t *ifg = self;
  45         return ifg->impl->cliques_iter_size;
  46 }
  47
  48 void (be_ifg_free)(void *self)
  49 {
  50         be_ifg_t *ifg = self;
  51         ifg->impl->free(self);
  52 }
  53
  54 int (be_ifg_connected)(const void *self, const ir_node *a, const ir_node *b)
  55 {
  56         const be_ifg_t *ifg = self;
  57         return ifg->impl->connected(self, a, b);
  58 }
  59
  60 ir_node *(be_ifg_neighbours_begin)(const void *self, void *iter, const ir_node *irn)
  61 {
  62         const be_ifg_t *ifg = self;
  63         return ifg->impl->neighbours_begin(self, iter, irn);
  64 }
  65
  66 ir_node *(be_ifg_neighbours_next)(const void *self, void *iter)
  67 {
  68         const be_ifg_t *ifg = self;
  69         return ifg->impl->neighbours_next(self, iter);
  70 }
  71
  72 void (be_ifg_neighbours_break)(const void *self, void *iter)
  73 {
  74         const be_ifg_t *ifg = self;
  75         ifg->impl->neighbours_break(self, iter);
  76 }
  77
  78 ir_node *(be_ifg_nodes_begin)(const void *self, void *iter)
  79 {
  80         const be_ifg_t *ifg = self;
  81         return ifg->impl->nodes_begin(self, iter);
  82 }
  83
  84 ir_node *(be_ifg_nodes_next)(const void *self, void *iter)
  85 {
  86         const be_ifg_t *ifg = self;
  87         return ifg->impl->nodes_next(self, iter);
  88 }
  89
  90 void (be_ifg_nodes_break)(const void *self, void *iter)
  91 {
  92         const be_ifg_t *ifg = self;
  93         ifg->impl->nodes_break(self, iter);
  94 }
  95
  96 int (be_ifg_cliques_begin)(const void *self, void *iter, ir_node **buf)
  97 {
  98         const be_ifg_t *ifg = self;
  99         return ifg->impl->cliques_begin(self, iter, buf);
 100 }
 101
 102 int (be_ifg_cliques_next)(const void *self, void *iter)
 103 {
 104         const be_ifg_t *ifg = self;
 105         return ifg->impl->cliques_next(self, iter);
 106 }
 107
 108 void (be_ifg_cliques_break)(const void *self, void *iter)
 109 {
 110         const be_ifg_t *ifg = self;
 111         ifg->impl->cliques_break(self, iter);
 112 }
 113
 114 int (be_ifg_degree)(const void *self, const ir_node *irn)
 115 {
 116         const be_ifg_t *ifg = self;
 117         return ifg->impl->degree(self, irn);
 118 }
 119
 120
 121 int be_ifg_is_simplicial(const be_ifg_t *ifg, const ir_node *irn)
 122 {
 123         int degree = be_ifg_degree(ifg, irn);
 124         void *iter = be_ifg_neighbours_iter_alloca(ifg);
 125
 126         ir_node **neighbours = xmalloc(degree * sizeof(neighbours[0]));
 127
 128         ir_node *curr;
 129         int i, j;
 130
 131         i = 0;
 132         be_ifg_foreach_neighbour(ifg, iter, irn, curr)
 133                 neighbours[i++] = curr;
 134
 135         for(i = 0; i < degree; ++i) {
 136                 for(j = 0; j < i; ++j)
 137                         if(!be_ifg_connected(ifg, neighbours[i], neighbours[j])) {
 138                                 free(neighbours);
 139                                 return 0;
 140                         }
 141         }
 142
 143
 144         free(neighbours);
 145         return 1;
 146 }
 147
 148 void be_ifg_check(const be_ifg_t *ifg)
 149 {
 150         void *iter1 = be_ifg_nodes_iter_alloca(ifg);
 151         void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
 152
 153         ir_node *n, *m;
 154
 155         /* Check, if all neighbours are indeed connected to the node. */
 156         be_ifg_foreach_node(ifg, iter1, n) {
 157                 be_ifg_foreach_neighbour(ifg, iter2, n, m)
 158                         if(!be_ifg_connected(ifg, n, m))
 159                                 ir_fprintf(stderr, "%+F is a neighbour of %+F but they are not connected!\n", n, m);
 160         }
 161 }
 162
 163 void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self)
 164 {
 165         void *nodes_it  = be_ifg_nodes_iter_alloca(ifg);
 166         void *neigh_it  = be_ifg_neighbours_iter_alloca(ifg);
 167         bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg));
 168
 169         ir_node *n, *m;
 170
 171         fprintf(file, "graph G {\n\tgraph [");
 172         if(cb->graph_attr)
 173                 cb->graph_attr(file, self);
 174         fprintf(file, "];\n");
 175
 176         if(cb->at_begin)
 177                 cb->at_begin(file, self);
 178
 179         be_ifg_foreach_node(ifg, nodes_it, n) {
 180                 if(cb->is_dump_node && cb->is_dump_node(self, n)) {
 181                         int idx = get_irn_idx(n);
 182                         bitset_set(nodes, idx);
 183                         fprintf(file, "\tnode [");
 184                         if(cb->node_attr)
 185                                 cb->node_attr(file, self, n);
 186                         fprintf(file, "]; n%d;\n", idx);
 187                 }
 188         }
 189
 190         /* Check, if all neighbours are indeed connected to the node. */
 191         be_ifg_foreach_node(ifg, nodes_it, n) {
 192                 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
 193                         int n_idx = get_irn_idx(n);
 194                         int m_idx = get_irn_idx(m);
 195
 196                         if(n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) {
 197                                 fprintf(file, "\tn%d -- n%d [", n_idx, m_idx);
 198                                 if(cb->edge_attr)
 199                                         cb->edge_attr(file, self, n, m);
 200                                 fprintf(file, "];\n");
 201                         }
 202                 }
 203         }
 204
 205         if(cb->at_end)
 206                 cb->at_end(file, self);
 207
 208         fprintf(file, "}\n");
 209         bitset_free(nodes);
 210 }