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

   1 /*
   2  * Copyright (C) 1995-2007 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   beifg_clique.c
  22  * @date   18.11.2005
  23  * @author Sebastian Hack
  24  *
  25  * Copyright (C) 2005 Universitaet Karlsruhe
  26  * Released under the GPL
  27  */
  28 #ifdef HAVE_CONFIG_H
  29 #include "config.h"
  30 #endif
  31
  32 #include <stdlib.h>
  33
  34 #include "belive_t.h"
  35 #include "list.h"
  36
  37 #include "irnode_t.h"
  38 #include "irgraph_t.h"
  39 #include "irgwalk.h"
  40 #include "irbitset.h"
  41
  42 #include "be_t.h"
  43 #include "bera.h"
  44 #include "beifg_t.h"
  45 #include "bechordal_t.h"
  46 #include "benodesets.h"
  47
  48 typedef struct _cli_head_t {
  49         struct list_head list;
  50         struct _cli_head_t *next_cli_head;
  51         ir_node *min;
  52         ir_node *max;
  53 } cli_head_t;
  54
  55 typedef struct _ifg_clique_t {
  56         const be_ifg_impl_t *impl;
  57         const be_chordal_env_t *env;
  58         cli_head_t *cli_root;
  59         struct obstack obst;
  60         cli_head_t *curr_cli_head;
  61 } ifg_clique_t;
  62
  63 typedef struct _cli_element_t {
  64         struct list_head list;
  65         ir_node *irn;
  66 } cli_element_t;
  67
  68 typedef struct _cli_iter_t {
  69         const ifg_clique_t *ifg;
  70         cli_head_t *curr_cli_head;
  71         cli_element_t *curr_cli_element;
  72         const ir_node *curr_irn;
  73         bitset_t *visited_neighbours;
  74         bitset_t *visited_nodes;
  75 } cli_iter_t;
  76
  77 /* PRIVATE FUNCTIONS */
  78 static cli_head_t *get_new_cli_head(ifg_clique_t *ifg)
  79 {
  80         cli_head_t *cli_head;
  81         cli_head_t *new_cli_head;
  82
  83         if (ifg->cli_root == NULL)
  84         {
  85                 new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
  86                 INIT_LIST_HEAD(&new_cli_head->list);
  87                 ifg->cli_root = new_cli_head;
  88         }
  89         else
  90         {
  91                 cli_head = ifg->cli_root;
  92                 while(!(cli_head->next_cli_head == NULL))
  93                 {
  94                         cli_head = cli_head->next_cli_head;
  95                 }
  96                 new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
  97                 INIT_LIST_HEAD(&new_cli_head->list);
  98                 cli_head->next_cli_head = new_cli_head;
  99         }
 100
 101         new_cli_head->min = NULL;
 102         new_cli_head->max = NULL;
 103         new_cli_head->next_cli_head = NULL;
 104         ifg->curr_cli_head = new_cli_head;
 105
 106         return new_cli_head;
 107 }
 108
 109 static cli_element_t *get_new_cli_element(ifg_clique_t *ifg)
 110 {
 111         cli_element_t *cli_element;
 112
 113         cli_element = obstack_alloc(&ifg->obst, sizeof(*cli_element));
 114         INIT_LIST_HEAD(&cli_element->list);
 115
 116         return cli_element;
 117 }
 118
 119 static void write_clique(nodeset *live_set, ifg_clique_t *ifg)
 120 {
 121         ir_node *live_irn;
 122         ir_node *test_node;
 123         int test_int = 0;
 124         ir_node *max_node = NULL;
 125         ir_node *min_node = NULL;
 126         cli_element_t *new_element = NULL;
 127         cli_element_t *element = NULL;
 128         cli_head_t *cli_head = get_new_cli_head(ifg);
 129         int is_element = 0;
 130
 131         foreach_nodeset(live_set, live_irn)
 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                                 { /* node is in clique */
 200                                         it->curr_cli_head    = head;
 201                                         it->curr_cli_element = (void *) head; /* needed because the next element is searched with list.next of it->curr_cli_element */
 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 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 ..*/
 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         return;
 272 }
 273
 274 static ir_node *get_next_node(cli_iter_t *it)
 275 {
 276         cli_head_t *cli_head = NULL;
 277         cli_element_t *element = it->curr_cli_element;
 278
 279         ir_node *irn;
 280
 281         if (element == NULL)
 282                 return NULL;
 283
 284         if (!(&it->curr_cli_head->list == element->list.next))
 285         {
 286                 irn = element->irn;
 287                 element = list_entry(element->list.next, cli_element_t, list);
 288                 it->curr_cli_element = element;
 289         }
 290         else /* reached end of clique */
 291         {
 292                 cli_head = it->curr_cli_head;
 293                 if (!(cli_head->next_cli_head == NULL))
 294                 {
 295                         irn = element->irn;
 296                         cli_head = cli_head->next_cli_head;
 297                         it->curr_cli_head = cli_head;
 298                         element = list_entry(cli_head->list.next, cli_element_t, list);
 299                         it->curr_cli_element = element;
 300                 }
 301                 else
 302                 {
 303                         it->curr_cli_head = NULL;
 304                         it->curr_cli_element = NULL;
 305                         irn = element->irn;
 306                 }
 307         }
 308         if (!(irn == NULL))
 309         {
 310                 if (bitset_is_set(it->visited_nodes, get_irn_idx(irn)))
 311                 {
 312                         irn = get_next_node(it);
 313                 }
 314                 if (!(irn == NULL))
 315                 {
 316                         bitset_set(it->visited_nodes, get_irn_idx(irn));
 317                 }
 318         }
 319
 320         return irn;
 321 }
 322
 323 static void find_neighbour_walker(ir_node *bl, void *data)
 324 {
 325         ifg_clique_t *ifg       = data;
 326         struct list_head *head  = get_block_border_head(ifg->env, bl);
 327         border_t *b;
 328         int was_def = 0;
 329         nodeset *live = new_nodeset(ifg->env->cls->n_regs);
 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                         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                         nodeset_remove(live, irn);
 353                 }
 354         }
 355         del_nodeset(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 dominates_min = 0;
 366         int is_in_clique = 0;
 367
 368         it->curr_cli_head = cli_head;
 369         it->ifg = ifg;
 370         it->visited_neighbours = bitset_visneighbours;
 371
 372         assert(cli_head && "There is no root entry for a cli_head.");
 373
 374         is_dominated_by_max = value_dominates(cli_head->max, irn);
 375         dominates_min = value_dominates(irn, cli_head->min);
 376
 377         if ((is_dominated_by_max) || (irn == cli_head->max))  /* node could be in clique */
 378         {
 379                 /* check if node is in clique */
 380                 list_for_each_entry(cli_element_t, element, &cli_head->list, list)
 381                 {
 382                         if (element->irn == irn) /* node is in clique */
 383                         {
 384                                 it->curr_cli_element = (void *) cli_head; /* needed because the next element is searched with list.next of it->curr_cli_element */
 385                                 is_in_clique = 1;
 386                                 element = get_next_element(irn, it);
 387                                 break;
 388                         }
 389                 }
 390         }
 391         if(!is_in_clique)
 392         {
 393                 cli_head = get_next_cli_head(irn, it);
 394                 element = get_next_element(irn, it);
 395         }
 396
 397         it->curr_cli_element = element;
 398         it->curr_irn = irn;
 399
 400         return;
 401 }
 402
 403 static ir_node *get_next_neighbour(cli_iter_t *it)
 404 {
 405         ir_node *res = NULL;
 406         const ir_node *irn = it->curr_irn;
 407
 408         if (it->curr_cli_element != NULL)
 409                 res = it->curr_cli_element->irn;
 410         else
 411                 return NULL;
 412
 413         it->curr_cli_element = get_next_element(irn, it);
 414
 415         if (res)
 416         {
 417                 if (bitset_contains_irn(it->visited_neighbours, res))
 418                 {
 419                         res = get_next_neighbour(it);
 420                 }
 421                 else
 422                 {
 423                         bitset_set(it->visited_neighbours, get_irn_idx(res));
 424                 }
 425         }
 426
 427         return res;
 428 }
 429
 430
 431 /* PUBLIC FUNCTIONS */
 432
 433 static void ifg_clique_free(void *self)
 434 {
 435         ifg_clique_t *ifg = self;
 436         obstack_free(&ifg->obst, NULL);
 437
 438         free(self);
 439 }
 440
 441 static int ifg_clique_connected(const void *self, const ir_node *a, const ir_node *b)
 442 {
 443         const ifg_clique_t *ifg = self;
 444         cli_iter_t it;
 445         int connected = -1;
 446         ir_node *irn = NULL;
 447
 448         find_first_neighbour(ifg, &it, a);
 449         connected = 0;
 450         irn = get_next_neighbour(&it);
 451         while (irn != NULL)
 452         {
 453                 if (irn == b)
 454                 {
 455                         connected = 1;
 456                         break;
 457                 }
 458                 irn = get_next_neighbour(&it);
 459         }
 460
 461         return connected;
 462 }
 463
 464 static ir_node *ifg_clique_neighbours_begin(const void *self, void *iter, const ir_node *irn)
 465 {
 466         find_first_neighbour(self, iter, irn);
 467         return get_next_neighbour(iter);
 468 }
 469
 470 static ir_node *ifg_clique_neighbours_next(const void *self, void *iter)
 471 {
 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
 479         bitset_free(it->visited_neighbours);
 480
 481         return;
 482 }
 483
 484 static ir_node *ifg_clique_nodes_begin(const void *self, void *iter)
 485 {
 486         find_nodes(self, iter);
 487         return get_next_node(iter);
 488 }
 489
 490 static ir_node *ifg_clique_nodes_next(const void *self, void *iter)
 491 {
 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
 499         bitset_free(it->visited_nodes);
 500
 501         return;
 502 }
 503
 504 static int ifg_clique_degree(const void *self, const ir_node *irn)
 505 {
 506         int degree = -1;
 507         cli_iter_t it;
 508
 509         find_first_neighbour(self, &it, irn);
 510         degree = 0;
 511         irn = get_next_neighbour(&it);
 512         while (irn != NULL)
 513         {
 514                 degree++;
 515                 irn = get_next_neighbour(&it);
 516         }
 517
 518         return degree;
 519 }
 520
 521 static const be_ifg_impl_t ifg_clique_impl = {
 522         sizeof(cli_iter_t),
 523         sizeof(cli_iter_t),
 524         0,
 525         ifg_clique_free,
 526         ifg_clique_connected,
 527         ifg_clique_neighbours_begin,
 528         ifg_clique_neighbours_next,
 529         ifg_clique_neighbours_break,
 530         ifg_clique_nodes_begin,
 531         ifg_clique_nodes_next,
 532         ifg_clique_nodes_break,
 533         NULL,
 534         NULL,
 535         NULL,
 536         ifg_clique_degree
 537 };
 538
 539 be_ifg_t *be_ifg_clique_new(const be_chordal_env_t *env)
 540 {
 541         ifg_clique_t *ifg       = xmalloc(sizeof(*ifg));
 542
 543         ifg->impl               = &ifg_clique_impl;
 544         ifg->env                        = env;
 545
 546         ifg->cli_root           = NULL;
 547         obstack_init(&ifg->obst);
 548
 549         dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
 550
 551         obstack_finish(&ifg->obst);
 552         return (be_ifg_t *) ifg;
 553 }