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 } ifg_clique_t;
  42
  43 typedef struct _cli_element_t {
  44         struct list_head list;
  45         ir_node *irn;
  46 } cli_element_t;
  47
  48 typedef struct _cli_iter_t {
  49         const ifg_clique_t *ifg;
  50         cli_head_t *curr_cli_head;
  51         cli_element_t *curr_cli_element;
  52         const ir_node *curr_irn;
  53         bitset_t *visited_neighbours;
  54         bitset_t *visited_nodes;
  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 ((is_dominated_by_max) || (irn == head->max)) /* node could be in clique */
 172         {
 173                 /* check if node is in clique */
 174                 list_for_each_entry(cli_element_t, element, &head->list, list)
 175                 {
 176                         if (&element->list != &head->list)
 177                         {
 178                                 if (element->irn == irn)
 179                                 { /* node is in clique */
 180                                         it->curr_cli_head    = head;
 181                                         it->curr_cli_element = (void *) head; /* needed because the next element is searched with list.next of it->curr_cli_element */
 182                                         break;
 183                                 }
 184                         }
 185                 }
 186
 187                 if (it->curr_cli_head != head) /*node was not in clique */
 188                 {
 189                         it->curr_cli_head = head;
 190                         head = get_next_cli_head(irn, it);
 191                 }
 192         }
 193         else
 194         {
 195                 it->curr_cli_head = head;
 196                 head = get_next_cli_head(irn, it);
 197         }
 198         return head;
 199 }
 200
 201 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 ..*/
 202 {
 203         cli_element_t *element = it->curr_cli_element;
 204         cli_head_t *head = it->curr_cli_head;
 205
 206         if (!head || it->curr_cli_element == NULL) /* way back of recursion or there are no more heads */
 207         {
 208                 it->curr_cli_element = NULL;
 209                 return NULL;
 210         }
 211         else
 212         {
 213                 element = list_entry(element->list.next, cli_element_t, list);
 214
 215                 if (&element->list == &head->list) /* Clique has no more elements */
 216                 {
 217                         head = get_next_cli_head(irn, it);
 218                         element = get_next_element(irn, it);
 219                 }
 220
 221                 if (element && element->irn == irn) /* the node you are searching neighbors for */
 222                 {
 223                         it->curr_cli_element = element;
 224                         element = get_next_element(irn, it);
 225                 }
 226
 227                 it->curr_cli_element = element;
 228
 229                 return element;
 230         }
 231 }
 232
 233 static void find_nodes(const ifg_clique_t *ifg, cli_iter_t *it)
 234 {
 235         cli_element_t *element;
 236         cli_head_t *cli_head = ifg->cli_root;
 237
 238         bitset_t *bitset_visnodes = bitset_malloc(get_irg_last_idx(ifg->env->irg));
 239
 240         it->visited_nodes = bitset_visnodes;
 241         it->curr_cli_head = cli_head;
 242
 243         assert(cli_head && "There is no root entry to work on!");
 244
 245         if (cli_head->list.next != &cli_head->list) /* if cli_head contains an element */
 246         {
 247                 element = list_entry(cli_head->list.next, cli_element_t, list);
 248                 it->curr_cli_element = element;
 249         }
 250
 251         return;
 252 }
 253
 254 static ir_node *get_next_node(cli_iter_t *it)
 255 {
 256         cli_head_t *cli_head = NULL;
 257         cli_element_t *element = it->curr_cli_element;
 258
 259         ir_node *irn;
 260
 261         if (element == NULL)
 262                 return NULL;
 263
 264         if (!(&it->curr_cli_head->list == element->list.next))
 265         {
 266                 irn = element->irn;
 267                 element = list_entry(element->list.next, cli_element_t, list);
 268                 it->curr_cli_element = element;
 269         }
 270         else /* reached end of clique */
 271         {
 272                 cli_head = it->curr_cli_head;
 273                 if (!(cli_head->next_cli_head == NULL))
 274                 {
 275                         irn = element->irn;
 276                         cli_head = cli_head->next_cli_head;
 277                         it->curr_cli_head = cli_head;
 278                         element = list_entry(cli_head->list.next, cli_element_t, list);
 279                         it->curr_cli_element = element;
 280                 }
 281                 else
 282                 {
 283                         it->curr_cli_head = NULL;
 284                         it->curr_cli_element = NULL;
 285                         irn = element->irn;
 286                 }
 287         }
 288         if (!(irn == NULL))
 289         {
 290                 if (bitset_is_set(it->visited_nodes, get_irn_idx(irn)))
 291                 {
 292                         irn = get_next_node(it);
 293                 }
 294                 if (!(irn == NULL))
 295                 {
 296                         bitset_set(it->visited_nodes, get_irn_idx(irn));
 297                 }
 298         }
 299
 300         return irn;
 301 }
 302
 303 static void find_neighbour_walker(ir_node *bl, void *data)
 304 {
 305         ifg_clique_t *ifg       = data;
 306         struct list_head *head  = get_block_border_head(ifg->env, bl);
 307         border_t *b;
 308         int was_def = 0;
 309         nodeset *live = new_nodeset(ifg->env->cls->n_regs);
 310
 311         assert(is_Block(bl) && "There is no block to work on.");
 312
 313         foreach_border_head(head, b) /* follow the borders of the block */
 314         {
 315                 ir_node *irn = b->irn;
 316
 317                 if (b->is_def) /* b is a new node */
 318                 {
 319                         nodeset_insert(live, irn);
 320                         if(b->is_real)
 321                         {
 322                                 was_def = 1;
 323                         }
 324                 }
 325                 else
 326                 {
 327                         if (was_def == 1) /* if there is a USE after a DEF... */
 328                         {
 329                                 write_clique(live, ifg); /* ...add the clique. */
 330                                 was_def = 0;
 331                         }
 332                         nodeset_remove(live, irn);
 333                 }
 334         }
 335         del_nodeset(live);
 336 }
 337
 338 static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const ir_node *irn)
 339 {
 340         cli_head_t *cli_head = ifg->cli_root;
 341         cli_element_t *element;
 342         bitset_t *bitset_visneighbours = bitset_malloc(get_irg_last_idx(ifg->env->irg));
 343
 344         int is_dominated_by_max = 0;
 345         int dominates_min = 0;
 346         int is_in_clique = 0;
 347
 348         it->curr_cli_head = cli_head;
 349         it->ifg = ifg;
 350         it->visited_neighbours = bitset_visneighbours;
 351
 352         assert(cli_head && "There is no root entry for a cli_head.");
 353
 354         is_dominated_by_max = value_dominates(cli_head->max, irn);
 355         dominates_min = value_dominates(irn, cli_head->min);
 356
 357         if ((is_dominated_by_max) || (irn == cli_head->max))  /* node could be in clique */
 358         {
 359                 /* check if node is in clique */
 360                 list_for_each_entry(cli_element_t, element, &cli_head->list, list)
 361                 {
 362                         if (element->irn == irn) /* node is in clique */
 363                         {
 364                                 it->curr_cli_element = (void *) cli_head; /* needed because the next element is searched with list.next of it->curr_cli_element */
 365                                 is_in_clique = 1;
 366                                 element = get_next_element(irn, it);
 367                                 break;
 368                         }
 369                 }
 370         }
 371         if(!is_in_clique)
 372         {
 373                 cli_head = get_next_cli_head(irn, it);
 374                 element = get_next_element(irn, it);
 375         }
 376
 377         it->curr_cli_element = element;
 378         it->curr_irn = irn;
 379
 380         return;
 381 }
 382
 383 static ir_node *get_next_neighbour(cli_iter_t *it)
 384 {
 385         ir_node *res = NULL;
 386         const ir_node *irn = it->curr_irn;
 387
 388         if (it->curr_cli_element != NULL)
 389                 res = it->curr_cli_element->irn;
 390         else
 391                 return NULL;
 392
 393         it->curr_cli_element = get_next_element(irn, it);
 394
 395         if (res)
 396         {
 397                 if (bitset_contains_irn(it->visited_neighbours, res))
 398                 {
 399                         res = get_next_neighbour(it);
 400                 }
 401                 else
 402                 {
 403                         bitset_set(it->visited_neighbours, get_irn_idx(res));
 404                 }
 405         }
 406
 407         return res;
 408 }
 409
 410
 411 /* PUBLIC FUNCTIONS */
 412
 413 static void ifg_clique_free(void *self)
 414 {
 415         ifg_clique_t *ifg = self;
 416         obstack_free(&ifg->obst, NULL);
 417
 418         free(self);
 419 }
 420
 421 static int ifg_clique_connected(const void *self, const ir_node *a, const ir_node *b)
 422 {
 423         const ifg_clique_t *ifg = self;
 424         cli_iter_t it;
 425         int connected = -1;
 426         ir_node *irn = NULL;
 427
 428         find_first_neighbour(ifg, &it, a);
 429         connected = 0;
 430         irn = get_next_neighbour(&it);
 431         while (irn != NULL)
 432         {
 433                 if (irn == b)
 434                 {
 435                         connected = 1;
 436                         break;
 437                 }
 438                 irn = get_next_neighbour(&it);
 439         }
 440
 441         return connected;
 442 }
 443
 444 static ir_node *ifg_clique_neighbours_begin(const void *self, void *iter, const ir_node *irn)
 445 {
 446         find_first_neighbour(self, iter, irn);
 447         return get_next_neighbour(iter);
 448 }
 449
 450 static ir_node *ifg_clique_neighbours_next(const void *self, void *iter)
 451 {
 452         return get_next_neighbour(iter);
 453 }
 454
 455 static void ifg_clique_neighbours_break(const void *self, void *iter)
 456 {
 457         cli_iter_t *it = iter;
 458
 459         bitset_free(it->visited_neighbours);
 460
 461         return;
 462 }
 463
 464 static ir_node *ifg_clique_nodes_begin(const void *self, void *iter)
 465 {
 466         find_nodes(self, iter);
 467         return get_next_node(iter);
 468 }
 469
 470 static ir_node *ifg_clique_nodes_next(const void *self, void *iter)
 471 {
 472         return get_next_node(iter);
 473 }
 474
 475 static void ifg_clique_nodes_break(const void *self, void *iter)
 476 {
 477         cli_iter_t *it = iter;
 478
 479         bitset_free(it->visited_nodes);
 480
 481         return;
 482 }
 483
 484 static int ifg_clique_degree(const void *self, const ir_node *irn)
 485 {
 486         int degree = -1;
 487         cli_iter_t it;
 488
 489         find_first_neighbour(self, &it, irn);
 490         degree = 0;
 491         irn = get_next_neighbour(&it);
 492         while (irn != NULL)
 493         {
 494                 degree++;
 495                 irn = get_next_neighbour(&it);
 496         }
 497
 498         return degree;
 499 }
 500
 501 static const be_ifg_impl_t ifg_clique_impl = {
 502         sizeof(cli_iter_t),
 503         sizeof(cli_iter_t),
 504         0,
 505         ifg_clique_free,
 506         ifg_clique_connected,
 507         ifg_clique_neighbours_begin,
 508         ifg_clique_neighbours_next,
 509         ifg_clique_neighbours_break,
 510         ifg_clique_nodes_begin,
 511         ifg_clique_nodes_next,
 512         ifg_clique_nodes_break,
 513         NULL,
 514         NULL,
 515         NULL,
 516         ifg_clique_degree
 517 };
 518
 519 be_ifg_t *be_ifg_clique_new(const be_chordal_env_t *env)
 520 {
 521         ifg_clique_t *ifg       = xmalloc(sizeof(*ifg));
 522
 523         ifg->impl               = &ifg_clique_impl;
 524         ifg->env                        = env;
 525
 526         ifg->cli_root           = NULL;
 527         obstack_init(&ifg->obst);
 528
 529         dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
 530
 531         obstack_finish(&ifg->obst);
 532         return (be_ifg_t *) ifg;
 533 }