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

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