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