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