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

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