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 "irtools.h"
  29 #include "beifg_t.h"
  30
  31 size_t (be_ifg_nodes_iter_size)(const void *self)
  32 {
  33         const be_ifg_t *ifg = self;
  34         return ifg->impl->nodes_iter_size;
  35 }
  36
  37 size_t (be_ifg_neighbours_iter_size)(const void *self)
  38 {
  39         const be_ifg_t *ifg = self;
  40         return ifg->impl->neighbours_iter_size;
  41 }
  42
  43 size_t (be_ifg_cliques_iter_size)(const void *self)
  44 {
  45         const be_ifg_t *ifg = self;
  46         return ifg->impl->cliques_iter_size;
  47 }
  48
  49 void (be_ifg_free)(void *self)
  50 {
  51         be_ifg_t *ifg = self;
  52         ifg->impl->free(self);
  53 }
  54
  55 int (be_ifg_connected)(const void *self, const ir_node *a, const ir_node *b)
  56 {
  57         const be_ifg_t *ifg = self;
  58         return ifg->impl->connected(self, a, b);
  59 }
  60
  61 ir_node *(be_ifg_neighbours_begin)(const void *self, void *iter, const ir_node *irn)
  62 {
  63         const be_ifg_t *ifg = self;
  64         return ifg->impl->neighbours_begin(self, iter, irn);
  65 }
  66
  67 ir_node *(be_ifg_neighbours_next)(const void *self, void *iter)
  68 {
  69         const be_ifg_t *ifg = self;
  70         return ifg->impl->neighbours_next(self, iter);
  71 }
  72
  73 void (be_ifg_neighbours_break)(const void *self, void *iter)
  74 {
  75         const be_ifg_t *ifg = self;
  76         ifg->impl->neighbours_break(self, iter);
  77 }
  78
  79 ir_node *(be_ifg_nodes_begin)(const void *self, void *iter)
  80 {
  81         const be_ifg_t *ifg = self;
  82         return ifg->impl->nodes_begin(self, iter);
  83 }
  84
  85 ir_node *(be_ifg_nodes_next)(const void *self, void *iter)
  86 {
  87         const be_ifg_t *ifg = self;
  88         return ifg->impl->nodes_next(self, iter);
  89 }
  90
  91 void (be_ifg_nodes_break)(const void *self, void *iter)
  92 {
  93         const be_ifg_t *ifg = self;
  94         ifg->impl->nodes_break(self, iter);
  95 }
  96
  97 int (be_ifg_cliques_begin)(const void *self, void *iter, ir_node **buf)
  98 {
  99         const be_ifg_t *ifg = self;
 100         return ifg->impl->cliques_begin(self, iter, buf);
 101 }
 102
 103 int (be_ifg_cliques_next)(const void *self, void *iter)
 104 {
 105         const be_ifg_t *ifg = self;
 106         return ifg->impl->cliques_next(self, iter);
 107 }
 108
 109 void (be_ifg_cliques_break)(const void *self, void *iter)
 110 {
 111         const be_ifg_t *ifg = self;
 112         ifg->impl->cliques_break(self, iter);
 113 }
 114
 115 int (be_ifg_degree)(const void *self, const ir_node *irn)
 116 {
 117         const be_ifg_t *ifg = self;
 118         return ifg->impl->degree(self, irn);
 119 }
 120
 121
 122 int be_ifg_is_simplicial(const be_ifg_t *ifg, const ir_node *irn)
 123 {
 124         int degree = be_ifg_degree(ifg, irn);
 125         void *iter = be_ifg_neighbours_iter_alloca(ifg);
 126
 127         ir_node **neighbours = xmalloc(degree * sizeof(neighbours[0]));
 128
 129         ir_node *curr;
 130         int i, j;
 131
 132         i = 0;
 133         be_ifg_foreach_neighbour(ifg, iter, irn, curr)
 134                 neighbours[i++] = curr;
 135
 136         for(i = 0; i < degree; ++i) {
 137                 for(j = 0; j < i; ++j)
 138                         if(!be_ifg_connected(ifg, neighbours[i], neighbours[j])) {
 139                                 free(neighbours);
 140                                 return 0;
 141                         }
 142         }
 143
 144
 145         free(neighbours);
 146         return 1;
 147 }
 148
 149 void be_ifg_check(const be_ifg_t *ifg)
 150 {
 151         void *iter1 = be_ifg_nodes_iter_alloca(ifg);
 152         void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
 153
 154         ir_node *n, *m;
 155         int node_count = 0;
 156         int neighbours_count = 0;
 157         int degree = 0;
 158
 159         /* count all nodes */
 160         ir_printf("\n\nFound the following nodes in the graph %+F:\n\n", current_ir_graph);
 161         be_ifg_foreach_node(ifg,iter1,n)
 162         {
 163                 node_count++;
 164                 degree = be_ifg_degree(ifg, n);
 165                 ir_printf("%d. %+F with degree: %d\n", node_count, n, degree);
 166         }
 167
 168         ir_printf("\n\nNumber of nodes: %d\n\n", node_count);
 169
 170         /* Check, if all neighbours are indeed connected to the node. */
 171         be_ifg_foreach_node(ifg, iter1, n)
 172         {
 173                 ir_printf("\n%+F; ", n);
 174                 be_ifg_foreach_neighbour(ifg, iter2, n, m)
 175                 {
 176                         ir_printf("%+F; ", m);
 177                         neighbours_count++;
 178                         if(!be_ifg_connected(ifg, n, m))
 179                                 ir_fprintf(stderr, "%+F is a neighbour of %+F but they are not connected!\n", n, m);
 180                 }
 181         }
 182         ir_printf("\n\nFound %d nodes in the 'check neighbour section'\n", neighbours_count);
 183 }
 184
 185 int be_ifg_check_get_node_count(const be_ifg_t *ifg)
 186 {
 187         void *iter = be_ifg_nodes_iter_alloca(ifg);
 188         int node_count = 0;
 189         ir_node *n;
 190
 191         be_ifg_foreach_node(ifg, iter, n)
 192         {
 193                 node_count++;
 194         }
 195
 196         return node_count;
 197 }
 198
 199 static int be_ifg_check_cmp_nodes(const void *a, const void *b)
 200 {
 201         const ir_node *node_a = *(ir_node **)a;
 202         const ir_node *node_b = *(ir_node **)b;
 203
 204         int nr_a = node_a->node_nr;
 205         int nr_b = node_b->node_nr;
 206
 207         return QSORT_CMP(nr_a, nr_b);
 208 }
 209
 210 void be_ifg_check_sorted(const be_ifg_t *ifg, FILE *f)
 211 {
 212         void *iter1 = be_ifg_nodes_iter_alloca(ifg);
 213         void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
 214
 215         ir_node *n, *m;
 216         const int node_count = be_ifg_check_get_node_count(ifg);
 217         int neighbours_count = 0;
 218         int i = 0;
 219
 220         ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0]));
 221
 222         be_ifg_foreach_node(ifg, iter1, n)
 223         {
 224                 all_nodes[i] = n;
 225                 i++;
 226         }
 227
 228         qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
 229
 230         for (i = 0; i < node_count; i++)
 231         {
 232                 ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
 233                 int j = 0;
 234                 int k = 0;
 235                 int degree = 0;
 236
 237                 degree = be_ifg_degree(ifg, all_nodes[i]);
 238
 239                 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
 240                 {
 241                         neighbours[j] = m;
 242                         j++;
 243                 }
 244
 245                 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
 246
 247                 ir_fprintf(f, "%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
 248
 249                 for(k = 0; k < j; k++)
 250                 {
 251                         ir_fprintf(f, "%+F, ", neighbours[k]);
 252                 }
 253
 254                 ir_fprintf(f, "\n");
 255
 256                 free(neighbours);
 257         }
 258
 259         free(all_nodes);
 260
 261 }
 262
 263 void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self)
 264 {
 265         void *nodes_it  = be_ifg_nodes_iter_alloca(ifg);
 266         void *neigh_it  = be_ifg_neighbours_iter_alloca(ifg);
 267         bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg));
 268
 269         ir_node *n, *m;
 270
 271         fprintf(file, "graph G {\n\tgraph [");
 272         if(cb->graph_attr)
 273                 cb->graph_attr(file, self);
 274         fprintf(file, "];\n");
 275
 276         if(cb->at_begin)
 277                 cb->at_begin(file, self);
 278
 279         be_ifg_foreach_node(ifg, nodes_it, n) {
 280                 if(cb->is_dump_node && cb->is_dump_node(self, n)) {
 281                         int idx = get_irn_idx(n);
 282                         bitset_set(nodes, idx);
 283                         fprintf(file, "\tnode [");
 284                         if(cb->node_attr)
 285                                 cb->node_attr(file, self, n);
 286                         fprintf(file, "]; n%d;\n", idx);
 287                 }
 288         }
 289
 290         /* Check, if all neighbours are indeed connected to the node. */
 291         be_ifg_foreach_node(ifg, nodes_it, n) {
 292                 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
 293                         int n_idx = get_irn_idx(n);
 294                         int m_idx = get_irn_idx(m);
 295
 296                         if(n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) {
 297                                 fprintf(file, "\tn%d -- n%d [", n_idx, m_idx);
 298                                 if(cb->edge_attr)
 299                                         cb->edge_attr(file, self, n, m);
 300                                 fprintf(file, "];\n");
 301                         }
 302                 }
 303         }
 304
 305         if(cb->at_end)
 306                 cb->at_end(file, self);
 307
 308         fprintf(file, "}\n");
 309         bitset_free(nodes);
 310 }