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