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