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

   1 /**
   2  * @file   beifg_clique.c
   3  * @date   18.11.2005
   4  * @author Sebastian Hack
   5  *
   6  * Copyright (C) 2005 Universitaet Karlsruhe
   7  * Released under the GPL
   8  */
   9 #ifdef HAVE_CONFIG_H
  10 #include "config.h"
  11 #endif
  12
  13 #include <stdlib.h>
  14
  15 #include "belive_t.h"
  16 #include "list.h"
  17
  18 #include "irnode_t.h"
  19 #include "irgraph_t.h"
  20 #include "irgwalk.h"
  21
  22 #include "be_t.h"
  23 #include "bera.h"
  24 #include "beifg_t.h"
  25 #include "bechordal_t.h"
  26
  27 typedef struct _cli_head_t {
  28         struct list_head list;
  29         struct _cli_head_t *next_cli_head;
  30         ir_node *min;
  31         ir_node *max;
  32 } cli_head_t;
  33
  34 typedef struct _ifg_clique_t {
  35         const be_ifg_impl_t *impl;
  36         const be_chordal_env_t *env;
  37         cli_head_t *cli_root;
  38         struct obstack obst;
  39         cli_head_t *curr_cli_head;
  40         bitset_t *visited_nodes;
  41         bitset_t *visited_neighbours;
  42 } ifg_clique_t;
  43
  44 typedef struct _cli_element_t {
  45         struct list_head list;
  46         ir_node *irn;
  47 } cli_element_t;
  48
  49 typedef struct _cli_iter_t {
  50         ifg_clique_t *ifg;
  51         cli_head_t *curr_cli_head;
  52         cli_element_t *curr_cli_element;
  53         const ir_node *curr_irn;
  54 } cli_iter_t;
  55
  56 /* PRIVATE FUNCTIONS */
  57 static cli_head_t *get_new_cli_head(ifg_clique_t *ifg)
  58 {
  59         cli_head_t *cli_head;
  60         cli_head_t *new_cli_head;
  61
  62         if (ifg->cli_root == NULL)
  63         {
  64                 new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
  65                 INIT_LIST_HEAD(&new_cli_head->list);
  66                 ifg->cli_root = new_cli_head;
  67         }
  68         else
  69         {
  70                 cli_head = ifg->cli_root;
  71                 while(!(cli_head->next_cli_head == NULL))
  72                 {
  73                         cli_head = cli_head->next_cli_head;
  74                 }
  75                 new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
  76                 INIT_LIST_HEAD(&new_cli_head->list);
  77                 cli_head->next_cli_head = new_cli_head;
  78         }
  79
  80         new_cli_head->min = NULL;
  81         new_cli_head->max = NULL;
  82         new_cli_head->next_cli_head = NULL;
  83         ifg->curr_cli_head = new_cli_head;
  84
  85         return new_cli_head;
  86 }
  87
  88 static cli_element_t *get_new_cli_element(ifg_clique_t *ifg)
  89 {
  90         cli_element_t *cli_element;
  91
  92         cli_element = obstack_alloc(&ifg->obst, sizeof(*cli_element));
  93         INIT_LIST_HEAD(&cli_element->list);
  94
  95         return cli_element;
  96 }
  97
  98 static void write_clique(nodeset *live_set, ifg_clique_t *ifg)
  99 {
 100         ir_node *live_irn;
 101         ir_node *test_node;
 102         int test_int = 0;
 103         ir_node *max_node = NULL;
 104         ir_node *min_node = NULL;
 105         cli_element_t *new_element = NULL;
 106         cli_element_t *element = NULL;
 107         cli_head_t *cli_head = get_new_cli_head(ifg);
 108         int is_element = 0;
 109
 110         foreach_nodeset(live_set, live_irn)
 111         {
 112                 /* test if node is max or min dominator*/
 113                 test_node = live_irn;
 114                 if (max_node == NULL)
 115                 {
 116                         max_node = test_node;
 117                         min_node = test_node;
 118                 }
 119                 else
 120                 {
 121                         test_int = value_dominates(test_node, max_node);
 122                         if (test_int == 1)
 123                         {
 124                                 max_node = test_node;
 125                         }
 126                         test_int = value_dominates(min_node, test_node);
 127                         if (test_int == 1)
 128                         {
 129                                 min_node = test_node;
 130                         }
 131                 }
 132
 133                 list_for_each_entry(cli_element_t, element, &cli_head->list, list){
 134                         if(element->irn == live_irn){
 135                                 is_element = 1;
 136                                 break;
 137                         }
 138                 }
 139
 140                 if (!is_element){
 141                         new_element = get_new_cli_element(ifg);
 142                         new_element->irn = live_irn;
 143                         list_add(&new_element->list, &cli_head->list) ;
 144                 }
 145         }
 146
 147         cli_head->min = min_node;
 148         cli_head->max = max_node;
 149 }
 150
 151 static cli_head_t *get_next_cli_head(const ir_node *irn, cli_iter_t *it) /* ...containing the node *irn */
 152 {
 153         cli_head_t *head;
 154         cli_element_t *element;
 155
 156         int is_dominated_by_max;
 157         //int dominates_min;
 158
 159         if (it->curr_cli_head == NULL || it->curr_cli_head->next_cli_head == NULL) /* way back of recursion or this is the last clique */
 160         {
 161                 it->curr_cli_head = NULL;
 162                 return NULL;
 163         }
 164
 165         head = it->curr_cli_head->next_cli_head;
 166
 167         is_dominated_by_max = value_dominates(head->max, irn);
 168         //dominates_min = value_dominates(irn, head->min);
 169
 170         if(head->min->node_nr == 2000)
 171                 assert("stop");
 172
 173         if ((is_dominated_by_max) || (irn == head->max)) /* node could be in clique */
 174         {
 175                 /* check if node is in clique */
 176                 list_for_each_entry(cli_element_t, element, &head->list, list)
 177                 {
 178                         if (&element->list != &head->list)
 179                         {
 180                                 if (element->irn == irn)
 181                                 { /* node is in clique */
 182                                         it->curr_cli_head    = head;
 183                                         it->curr_cli_element = (void *) head; /* needed because the next element is searched with list.next of it->curr_cli_element */
 184                                         break;
 185                                 }
 186                         }
 187                 }
 188
 189                 if (it->curr_cli_head != head) /*node was not in clique */
 190                 {
 191                         it->curr_cli_head = head;
 192                         head = get_next_cli_head(irn, it);
 193                 }
 194         }
 195         else
 196         {
 197                 it->curr_cli_head = head;
 198                 head = get_next_cli_head(irn, it);
 199         }
 200         return head;
 201 }
 202
 203 static cli_element_t *get_next_element(const ir_node *irn, cli_iter_t *it) /* ... of the current clique, returns NULL if there were no more elements ..*/
 204 {
 205         cli_element_t *element = it->curr_cli_element;
 206         cli_head_t *head = it->curr_cli_head;
 207
 208         if (!head || it->curr_cli_element == NULL) /* way back of recursion or there are no more heads */
 209         {
 210                 it->curr_cli_element = NULL;
 211                 return NULL;
 212         }
 213         else
 214         {
 215                 element = list_entry(element->list.next, cli_element_t, list);
 216
 217                 if (&element->list == &head->list) /* Clique has no more elements */
 218                 {
 219                         head = get_next_cli_head(irn, it);
 220                         element = get_next_element(irn, it);
 221                 }
 222
 223                 if (element != NULL && element->irn == irn) /* the node you are searching neighbors for */
 224                 {
 225                         it->curr_cli_element = element;
 226                         element = get_next_element(irn, it);
 227                 }
 228
 229                 it->curr_cli_element = element;
 230
 231                 return element;
 232         }
 233 }
 234
 235 static void find_nodes(const ifg_clique_t *ifg, cli_iter_t *it)
 236 {
 237         cli_element_t *element;
 238         cli_head_t *cli_head = ifg->cli_root;
 239
 240         bitset_clear_all(ifg->visited_nodes);
 241
 242         assert(cli_head && "There is no root entry to work on!");
 243
 244         it->curr_cli_head = cli_head;
 245
 246         if (cli_head->list.next != &cli_head->list) /* if cli_head contains an element */
 247         {
 248                 element = list_entry(cli_head->list.next, cli_element_t, list);
 249                 it->curr_cli_element = element;
 250         }
 251
 252         return;
 253 }
 254
 255 static ir_node *get_next_node(cli_iter_t *it)
 256 {
 257         cli_head_t *cli_head = NULL;
 258         cli_element_t *element = it->curr_cli_element;
 259
 260         ir_node *irn;
 261
 262         if (element == NULL)
 263                 return NULL;
 264
 265         if (!(&it->curr_cli_head->list == element->list.next))
 266         {
 267                 irn = element->irn;
 268                 element = list_entry(element->list.next, cli_element_t, list);
 269                 it->curr_cli_element = element;
 270         }
 271         else /* reached end of clique */
 272         {
 273                 cli_head = it->curr_cli_head;
 274                 if (!(cli_head->next_cli_head == NULL))
 275                 {
 276                         irn = element->irn;
 277                         cli_head = cli_head->next_cli_head;
 278                         it->curr_cli_head = cli_head;
 279                         element = list_entry(cli_head->list.next, cli_element_t, list);
 280                         it->curr_cli_element = element;
 281                 }
 282                 else
 283                 {
 284                         it->curr_cli_head = NULL;
 285                         it->curr_cli_element = NULL;
 286                         irn = element->irn;
 287                 }
 288         }
 289         if (!(irn == NULL))
 290         {
 291                 if (bitset_is_set(it->ifg->visited_nodes, get_irn_idx(irn)))
 292                 {
 293                         irn = get_next_node(it);
 294                 }
 295                 if (!(irn == NULL))
 296                 {
 297                         bitset_set(it->ifg->visited_nodes, get_irn_idx(irn));
 298                 }
 299         }
 300
 301         return irn;
 302 }
 303
 304 static void find_neighbour_walker(ir_node *bl, void *data)
 305 {
 306         ifg_clique_t *ifg       = data;
 307         struct list_head *head  = get_block_border_head(ifg->env, bl);
 308         border_t *b;
 309         int was_def = 0;
 310         nodeset *live = new_nodeset(ifg->env->cls->n_regs);
 311
 312         assert(is_Block(bl) && "There is no block to work on.");
 313
 314         foreach_border_head(head, b) /* follow the borders of the block */
 315         {
 316                 ir_node *irn = b->irn;
 317 //
 318 //              if (b->irn->node_nr == 1869)
 319 //                      printf("");
 320
 321                 if (b->is_def) /* b is a new node */
 322                 {
 323                         nodeset_insert(live, irn);
 324                         if(b->is_real)
 325                         {
 326                                 was_def = 1;
 327                         }
 328                 }
 329                 else
 330                 {
 331                         if (was_def == 1) /* if there is a USE after a DEF... */
 332                         {
 333                                 write_clique(live, ifg); /* ...add the clique. */
 334                                 was_def = 0;
 335                         }
 336                         nodeset_remove(live, irn);
 337                 }
 338         }
 339         del_nodeset(live);
 340 }
 341
 342 static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const ir_node *irn)
 343 {
 344         cli_head_t *cli_head = ifg->cli_root;
 345         cli_element_t *element;
 346
 347         int is_dominated_by_max = 0;
 348         int dominates_min = 0;
 349         int is_in_clique = 0;
 350
 351         it->curr_cli_head = cli_head;
 352         it->ifg = ifg;
 353         bitset_clear_all(it->ifg->visited_neighbours);
 354
 355         assert(cli_head && "There is no root entry for a cli_head.");
 356
 357         is_dominated_by_max = value_dominates(cli_head->max, irn);
 358         dominates_min = value_dominates(irn, cli_head->min);
 359
 360         if ((is_dominated_by_max) || (irn == cli_head->max))  /* node could be in clique */
 361         {
 362                 /* check if node is in clique */
 363                 list_for_each_entry(cli_element_t, element, &cli_head->list, list)
 364                 {
 365                         if (&element->list != &cli_head->list)
 366                         {
 367                                 if (element->irn == irn)
 368                                 { /* node is in clique */
 369                                         it->curr_cli_element = (void *) cli_head; /* needed because the next element is searched with list.next of it->curr_cli_element */
 370                                         is_in_clique = 1;
 371                                         element = get_next_element(irn, it);
 372                                         break;
 373                                 }
 374                         }
 375                 }
 376         }
 377         if(!is_in_clique)
 378         {
 379                 cli_head = get_next_cli_head(irn, it);
 380                 element = get_next_element(irn, it);
 381         }
 382
 383         it->curr_cli_element = element;
 384         it->curr_irn = irn;
 385
 386         return;
 387 }
 388
 389 static ir_node *get_next_neighbour(cli_iter_t *it)
 390 {
 391         ir_node *res = NULL;
 392         cli_element_t *element;
 393         cli_head_t *cli_head = it->curr_cli_head;
 394         const ir_node *irn = it->curr_irn;
 395
 396         if (it->curr_cli_element != NULL)
 397                 res = it->curr_cli_element->irn;
 398         else
 399                 return NULL;
 400
 401         element = get_next_element(irn, it);
 402
 403         if (element == NULL) /* no more elements in this clique */
 404         {
 405                 it->curr_cli_element = NULL;
 406         }
 407         else
 408         {
 409                 it->curr_cli_element = element;
 410         }
 411
 412         if (!(res == NULL))
 413         {
 414                 if (bitset_is_set(it->ifg->visited_neighbours, get_irn_idx(res)))
 415                 {
 416                         res = get_next_neighbour(it);
 417 //                      if (res == NULL) /* there are no more neighbours to return */
 418 //                      {
 419 //                              return NULL;
 420 //                      }
 421                 }
 422                 else
 423                 {
 424                         bitset_set(it->ifg->visited_neighbours, get_irn_idx(res));
 425                 }
 426         }
 427
 428         return res;
 429 }
 430
 431
 432 /* PUBLIC FUNCTIONS */
 433
 434 static void ifg_clique_free(void *self)
 435 {
 436         ifg_clique_t *ifg = self;
 437         obstack_free(&ifg->obst, NULL);
 438
 439         free(self);
 440 }
 441
 442 static int ifg_clique_connected(const ifg_clique_t *ifg, const ir_node *a, const ir_node *b)
 443 {
 444         cli_iter_t it;
 445         int connected = -1;
 446         ir_node *irn = NULL;
 447
 448         find_first_neighbour(ifg, &it, a);
 449         connected = 0;
 450         irn = get_next_neighbour(&it);
 451         while (irn != NULL)
 452         {
 453                 if (irn == b)
 454                 {
 455                         connected = 1;
 456                         break;
 457                 }
 458                 irn = get_next_neighbour(&it);
 459         }
 460
 461         return connected;
 462 }
 463
 464 static ir_node *ifg_clique_neighbours_begin(const void *self, void *iter, const ir_node *irn)
 465 {
 466         find_first_neighbour(self, iter, irn);
 467         return get_next_neighbour(iter);
 468 }
 469
 470 static ir_node *ifg_clique_neighbours_next(const void *self, void *iter)
 471 {
 472         return get_next_neighbour(iter);
 473 }
 474
 475 static void ifg_clique_neighbours_break(const void *self, void *iter)
 476 {
 477         return;
 478 }
 479
 480 static ir_node *ifg_clique_nodes_begin(const void *self, void *iter)
 481 {
 482         find_nodes(self, iter);
 483         return get_next_node(iter);
 484 }
 485
 486 static ir_node *ifg_clique_nodes_next(const void *self, void *iter)
 487 {
 488         return get_next_node(iter);
 489 }
 490
 491 static void ifg_clique_nodes_break(const void *self, void *iter)
 492 {
 493         return;
 494 }
 495
 496 static int ifg_clique_degree(const void *self, const ir_node *irn)
 497 {
 498         int degree = -1;
 499         cli_iter_t *it = NULL;
 500
 501         find_first_neighbour(self, it, irn);
 502         degree = 0;
 503         irn = get_next_neighbour(it);
 504         while (irn != NULL)
 505         {
 506                 degree++;
 507                 irn = get_next_neighbour(it);
 508         }
 509
 510         return degree;
 511 }
 512
 513 static const be_ifg_impl_t ifg_clique_impl = {
 514         sizeof(cli_iter_t),
 515         sizeof(cli_iter_t),
 516         0,
 517         ifg_clique_free,
 518         ifg_clique_connected,
 519         ifg_clique_neighbours_begin,
 520         ifg_clique_neighbours_next,
 521         ifg_clique_neighbours_break,
 522         ifg_clique_nodes_begin,
 523         ifg_clique_nodes_next,
 524         ifg_clique_nodes_break,
 525         NULL,
 526         NULL,
 527         NULL,
 528         ifg_clique_degree
 529 };
 530
 531 be_ifg_t *be_ifg_clique_new(const be_chordal_env_t *env)
 532 {
 533         ifg_clique_t *ifg       = xmalloc(sizeof(*ifg));
 534         bitset_t *bitset_visnodes = bitset_malloc(get_irg_last_idx(env->irg));
 535         bitset_t *bitset_visneighbours = bitset_malloc(get_irg_last_idx(env->irg));
 536         ifg->visited_nodes = bitset_visnodes;
 537         ifg->visited_neighbours = bitset_visneighbours;
 538         ifg->impl               = &ifg_clique_impl;
 539         ifg->env                        = env;
 540
 541         ifg->cli_root           = NULL;
 542         obstack_init(&ifg->obst);
 543
 544         dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
 545
 546         obstack_finish(&ifg->obst);
 547         return (be_ifg_t *) ifg;
 548 }