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