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

   1 /**
   2  * @file   beifg_list.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 #ifdef HAVE_CONFIG_H
  11 #include "config.h"
  12 #endif
  13
  14 #include <stdlib.h>
  15
  16 #include "benodesets.h"
  17 #include "list.h"
  18
  19 #include "irnode_t.h"
  20 #include "irgraph_t.h"
  21 #include "irgwalk.h"
  22
  23 #include "be_t.h"
  24 #include "bera.h"
  25 #include "beifg_t.h"
  26 #include "bechordal_t.h"
  27
  28
  29 typedef struct _adj_head_t adj_head_t;
  30
  31 typedef struct _ifg_list_t {
  32         const be_ifg_impl_t *impl;
  33         const be_chordal_env_t *env;
  34         struct obstack obst;
  35         adj_head_t **adj_heads;
  36 } ifg_list_t;
  37
  38 typedef struct _adj_element_t adj_element_t;
  39
  40 struct _adj_element_t {
  41         adj_element_t *next_adj_element;
  42         ir_node *neighbour;
  43 };
  44
  45 struct _adj_head_t {
  46         ir_node *irn; /* the node you search neighbours for */
  47         adj_element_t *first_adj_element;
  48         int degree;
  49 };
  50
  51 typedef struct _nodes_iter_t {
  52         const ifg_list_t *ifg;
  53         unsigned int curr_node_idx;
  54 } nodes_iter_t;
  55
  56 typedef struct _adj_iter_t {
  57         const ifg_list_t *ifg;
  58         adj_element_t *curr_adj_element;
  59 } adj_iter_t;
  60
  61 /* PRIVATE FUNCTIONS */
  62
  63 static void create_node (ifg_list_t *ifg, ir_node *irn) /* add node to the array of all nodes in this ifg implementation, if the node isn't already in the ifg */
  64 {
  65         adj_head_t *adj_head = NULL;
  66
  67         adj_head = ifg->adj_heads[irn->node_idx];
  68         if (!adj_head)
  69         {
  70                 adj_head = obstack_alloc(&ifg->obst, sizeof(*adj_head));
  71                 adj_head->irn = irn;
  72                 adj_head->first_adj_element = NULL;
  73                 adj_head->degree = 0;
  74                 ifg->adj_heads[irn->node_idx] = adj_head;
  75         }
  76 }
  77
  78 static adj_element_t *create_adj_element(ifg_list_t *ifg, ir_node *irn)
  79 {
  80         adj_element_t *element = NULL;
  81
  82         element = obstack_alloc(&ifg->obst, sizeof(*element));
  83         element->next_adj_element = NULL;
  84         element->neighbour = irn;
  85
  86         return element;
  87 }
  88
  89 static void add_edge(ifg_list_t *ifg, ir_node *node_a, ir_node *node_b) /* write the information about the edge between a and b */
  90 {
  91         adj_head_t *adj_head = NULL;
  92         adj_element_t *curr_element = NULL;
  93         adj_element_t *new_element = NULL;
  94
  95         adj_head = ifg->adj_heads[node_a->node_idx]; /* find the neighbours list of a */
  96
  97         assert (adj_head && "There is no entry for node a");
  98         curr_element = adj_head->first_adj_element;
  99
 100         if (curr_element)
 101         {
 102                 while (curr_element->neighbour != node_b && curr_element->next_adj_element)
 103                 {
 104                         curr_element = curr_element->next_adj_element;
 105                 }
 106
 107                 if (curr_element->neighbour != node_b && curr_element->next_adj_element == NULL)
 108                 {
 109                         adj_head->degree++;
 110                         new_element = create_adj_element(ifg, node_b); /* if b isn't in list, add b */
 111                         curr_element->next_adj_element = new_element;
 112                 }
 113         }
 114         else
 115         {
 116                 adj_head->degree++;
 117                 new_element = create_adj_element(ifg, node_b); /* a has no neighbours, add b as the first one*/
 118                 adj_head->first_adj_element = new_element;
 119         }
 120
 121         /* do the same vice versa */
 122         adj_head = ifg->adj_heads[node_b->node_idx];
 123
 124         assert (adj_head && "There is no entry for node a");
 125         curr_element = adj_head->first_adj_element;
 126
 127         if (curr_element)
 128         {
 129                 while (curr_element->neighbour != node_a && curr_element->next_adj_element)
 130                 {
 131                         curr_element = curr_element->next_adj_element;
 132                 }
 133
 134                 if (curr_element->neighbour != node_a && curr_element->next_adj_element == NULL)
 135                 {
 136                         adj_head->degree++;
 137                         new_element = create_adj_element(ifg, node_a);
 138                         curr_element->next_adj_element = new_element;
 139                 }
 140         }
 141         else
 142         {
 143                 adj_head->degree++;
 144                 new_element = create_adj_element(ifg, node_a);
 145                 adj_head->first_adj_element = new_element;
 146         }
 147 }
 148
 149 static void find_neighbour_walker(ir_node *bl, void *data) /* find all adjacent nodes in the irg */
 150 {
 151         ifg_list_t *ifg = data;
 152         struct list_head *head  = get_block_border_head(ifg->env, bl);
 153
 154         nodeset *live = new_nodeset(ifg->env->cls->n_regs);
 155         ir_node *live_irn = NULL;
 156         border_t *b = NULL;
 157
 158         assert (is_Block(bl) && "There is no block to work on");
 159
 160         foreach_border_head(head, b) /* follow the borders of each block */
 161         {
 162                 if (b->is_def)
 163                 {
 164                         create_node(ifg, b->irn); /* add the node to the array of all nodes of this ifg implementation */
 165                         nodeset_insert(live, b->irn);
 166                         if (b->is_real) /* this is a new node */
 167                         {
 168                                 foreach_nodeset(live, live_irn)
 169                                 {
 170                                         if (b->irn != live_irn) /* add a as a neighbour to b and vice versa */
 171                                                 add_edge(ifg, b->irn, live_irn);
 172                                 }
 173                         }
 174                 }
 175                 else /* b->irn is now dead */
 176                 {
 177                         if (nodeset_find(live, b->irn))
 178                                 nodeset_remove(live, b->irn);
 179                 }
 180         }
 181
 182         if (live)
 183                 del_nodeset(live);
 184 }
 185
 186 static ir_node *get_first_node(const ifg_list_t *ifg, nodes_iter_t *it)
 187 {
 188         ir_node *res = NULL;
 189         adj_head_t *adj_head= NULL;
 190         int curr_idx = -1;
 191
 192         it->ifg = ifg;
 193         it->curr_node_idx = 0;
 194
 195         while (adj_head == NULL)
 196         {
 197                 curr_idx++;
 198                 adj_head = ifg->adj_heads[curr_idx];
 199         }
 200
 201         if (adj_head == NULL) /* there are no nodes in this ifg */
 202                 return NULL;
 203         else
 204         {
 205                 res = adj_head->irn;
 206                 it->curr_node_idx = curr_idx;
 207         }
 208
 209         return res;
 210 }
 211
 212 static ir_node *get_next_node(nodes_iter_t *it)
 213 {
 214         const ifg_list_t *ifg = it->ifg;
 215         ir_node *res = NULL;
 216         adj_head_t *adj_head= NULL;
 217         unsigned int curr_idx = it->curr_node_idx;
 218
 219         while (adj_head == NULL && curr_idx < it->ifg->env->irg->last_node_idx - 1)
 220         {
 221                 curr_idx++;
 222                 adj_head = ifg->adj_heads[curr_idx];
 223         }
 224
 225         if (adj_head == NULL) /* there are no more nodes in this ifg */
 226                 return NULL;
 227         else
 228         {
 229                 res = adj_head->irn;
 230                 it->curr_node_idx = curr_idx;
 231         }
 232
 233         return res;
 234 }
 235
 236 static ir_node *get_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const ir_node *curr_irn)
 237 {
 238         ir_node *res = NULL;
 239         adj_head_t *adj_head = NULL;
 240
 241         adj_head = ifg->adj_heads[curr_irn->node_idx];
 242         assert (adj_head && "There is no entry for this node");
 243
 244         it->curr_adj_element = NULL;
 245         it->ifg = ifg;
 246
 247         if (adj_head->first_adj_element) /* return first neighbour */
 248         {
 249                 res = adj_head->first_adj_element->neighbour;
 250                 it->curr_adj_element = adj_head->first_adj_element;
 251         }
 252         else /* node has no neighbours */
 253                 return NULL;
 254
 255         return res;
 256 }
 257
 258 static ir_node *get_next_neighbour(adj_iter_t *it)
 259 {
 260         ir_node *res = NULL;
 261         adj_element_t *element = it->curr_adj_element;
 262
 263         if (element->next_adj_element) /* return next neighbour */
 264         {
 265                 res = element->next_adj_element->neighbour;
 266                 it->curr_adj_element = element->next_adj_element;
 267         }
 268         else /* was last neighbour */
 269                 return NULL;
 270
 271         return res;
 272 }
 273
 274 /* PUBLIC FUNCTIONS */
 275
 276 static void ifg_list_free(void *self)
 277 {
 278         ifg_list_t *ifg = self;
 279         obstack_free(&ifg->obst, NULL);
 280         free(ifg->adj_heads);
 281         free(ifg);
 282 }
 283
 284 static int ifg_list_connected(const void *self, const ir_node *a, const ir_node *b)
 285 {
 286         const ifg_list_t *ifg = self;
 287         int res = -1;
 288         adj_head_t *adj_head = NULL;
 289         adj_element_t *curr_element = NULL;
 290
 291         /* first try: find b in the neigbours of a */
 292         adj_head = ifg->adj_heads[a->node_idx];
 293
 294         assert(adj_head && "There is no entry for the node a");
 295         curr_element = adj_head->first_adj_element;
 296
 297         if(curr_element)
 298         {
 299                 while (curr_element->neighbour != b && curr_element->next_adj_element)
 300                 {
 301                         curr_element = curr_element->next_adj_element;
 302                 }
 303                 if (curr_element->neighbour == b)
 304                         return 1;
 305                 else
 306                         res = 0;
 307         }
 308         else /* node a has no neighbours */
 309                 res = 0;
 310
 311         /* second try, this should not be necessary... only to check the solution */
 312         adj_head = ifg->adj_heads[b->node_idx];
 313
 314         assert(adj_head && "There is no entry for the node b");
 315         curr_element = adj_head->first_adj_element;
 316
 317         if(curr_element)
 318         {
 319                 while (curr_element->neighbour != a && curr_element->next_adj_element)
 320                 {
 321                         curr_element = curr_element->next_adj_element;
 322                 }
 323                 if (curr_element->neighbour == a)
 324                 {
 325                         assert ("Found the neighbour only in the second try.");
 326                         return 1;
 327                 }
 328                 else
 329                         res = 0;
 330         }
 331         else /* node b has no neighbours */
 332                 res = 0;
 333
 334         return res;
 335 }
 336
 337 static ir_node *ifg_list_nodes_begin(const void *self, void *iter)
 338 {
 339         nodes_iter_t *it = iter;
 340         return get_first_node(self, it);
 341 }
 342
 343 static ir_node *ifg_list_nodes_next(const void *self, void *iter)
 344 {
 345         return get_next_node(iter);
 346 }
 347
 348 static void ifg_list_nodes_break(const void *self, void *iter)
 349 {
 350         nodes_iter_t *it = iter;
 351         it->curr_node_idx = 0;
 352         it->ifg = NULL;
 353 }
 354
 355 static ir_node *ifg_list_neighbours_begin(const void *self, void *iter,const ir_node *irn)
 356 {
 357         adj_iter_t *it = iter;
 358         return get_first_neighbour(self, it, irn);
 359 }
 360
 361 static ir_node *ifg_list_neighbours_next(const void *self, void *iter)
 362 {
 363         return get_next_neighbour(iter);
 364 }
 365
 366 static void ifg_list_neighbours_break(const void *self, void *iter)
 367 {
 368         adj_iter_t *it= iter;
 369         it->curr_adj_element = NULL;
 370         it->ifg = NULL;
 371 }
 372
 373 static int ifg_list_degree(const void *self, const ir_node *irn)
 374 {
 375         const ifg_list_t *ifg = self;
 376         adj_head_t *adj_head = NULL;
 377
 378         adj_head = ifg->adj_heads[irn->node_idx];
 379
 380         assert (adj_head && "There is no entry for this node");
 381
 382         return adj_head->degree;
 383 }
 384
 385 static const be_ifg_impl_t ifg_list_impl = {
 386         sizeof(nodes_iter_t),
 387         sizeof(adj_iter_t),
 388         0,
 389         ifg_list_free,
 390         ifg_list_connected,
 391         ifg_list_neighbours_begin,
 392         ifg_list_neighbours_next,
 393         ifg_list_neighbours_break,
 394         ifg_list_nodes_begin,
 395         ifg_list_nodes_next,
 396         ifg_list_nodes_break,
 397         NULL,
 398         NULL,
 399         NULL,
 400         ifg_list_degree
 401 };
 402
 403 be_ifg_t *be_ifg_list_new(const be_chordal_env_t *env)
 404 {
 405         ifg_list_t *ifg = xmalloc(sizeof(*ifg));
 406         adj_head_t **adj_heads_array = xmalloc(env->irg->last_node_idx * sizeof(adj_heads_array[0]));
 407
 408         ifg->impl = &ifg_list_impl;
 409         ifg->env  = env;
 410
 411         memset(adj_heads_array, 0, env->irg->last_node_idx * sizeof(adj_heads_array[0]));
 412         ifg->adj_heads = adj_heads_array;
 413
 414         obstack_init(&ifg->obst);
 415         dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
 416         obstack_finish(&ifg->obst);
 417
 418         return (be_ifg_t *) ifg;
 419 }