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

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