nsz Git - libfirm/blob - ir/be/beifg_pointer.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       Pointer based implementation of chordal interference graphs.
  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 #include "irphase_t.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
  47 typedef struct _ptr_element_t ptr_element_t;
  48
  49 typedef union element_content {
  50         ir_node       *irn;
  51         ptr_element_t *element;
  52 } element_content;
  53
  54 struct _ptr_element_t {
  55         int kind; /* kind = 8888 ..> both are ir_nodes, = 3101 ..> first is another element, second an ir_node */
  56         element_content content_first; /* could be a ptr_element or ir_node */
  57         element_content content_second; /* could be a ptr_element or ir_node */
  58 };
  59
  60 typedef struct _ptr_head_t {
  61         struct list_head list;
  62         ptr_element_t    *element;
  63 } ptr_head_t;
  64
  65 typedef struct _ifg_pointer_t {
  66         const be_ifg_impl_t    *impl;
  67         const be_chordal_env_t *env;
  68         ir_phase               ph;
  69         struct obstack         obst;
  70         ptr_head_t             *curr_ptr_head;
  71         ptr_element_t          *curr_element;
  72 } ifg_pointer_t;
  73
  74 typedef struct _ptr_iter_t {
  75         const ifg_pointer_t *ifg;
  76         const ir_node       *irn;
  77         ptr_head_t          *curr_ptr_head;
  78         ptr_head_t          *first_head;
  79         ptr_element_t       *curr_element_t;
  80         ir_node             *curr_irn;
  81         int                 get_first;
  82         int                 sub_call;
  83         bitset_t            *visited_neighbours;
  84 } ptr_iter_t;
  85
  86 /* PRIVATE FUNCTIONS */
  87
  88 static void *ptr_irn_data_init(ir_phase *ph, const ir_node *irn, void *data)
  89 {
  90         ptr_head_t *head = phase_alloc(ph, sizeof(*head));
  91         (void) irn;
  92         (void) data;
  93         INIT_LIST_HEAD(&head->list);
  94         return head;
  95 }
  96
  97 static ptr_element_t *ptr_get_new_element(ifg_pointer_t *ifg)
  98 {
  99         ptr_element_t *new_element = obstack_alloc(&ifg->obst, sizeof(ptr_element_t));
 100         memset(new_element, 0, sizeof(*new_element));
 101         return new_element;
 102 }
 103
 104 static ptr_head_t *ptr_get_new_head(ifg_pointer_t *ifg)
 105 {
 106         ptr_head_t *new_element = obstack_alloc(&ifg->obst, sizeof(*new_element));
 107         INIT_LIST_HEAD(&new_element->list);
 108         return new_element;
 109 }
 110
 111 static void write_pointers(bitset_t *live, ifg_pointer_t *ifg)
 112 {
 113         ir_node      *live_irn;
 114         bitset_pos_t  elm;
 115
 116         bitset_foreach_irn(ifg->env->irg, live, elm, live_irn) {
 117                 ptr_head_t *head    = phase_get_or_set_irn_data(&ifg->ph, live_irn);
 118                 ptr_head_t *element = ptr_get_new_head(ifg);
 119
 120                 element->element = ifg->curr_element; /* write current highest sub-clique for each node */
 121                 list_add(&element->list, &head->list);
 122         }
 123 }
 124
 125 static ptr_element_t *get_last_sub_clique(ifg_pointer_t *ifg, bitset_t *live, bitset_t *my_live, ir_node *irn)
 126 {
 127         ptr_element_t *element = ifg->curr_element;
 128         ptr_element_t *res = NULL;
 129
 130         /* search the last sub-clique before the sub-clique that contains the node irn */
 131         if (element && element->kind == 8888
 132                 && (element->content_first.irn == irn
 133                 || element->content_second.irn == irn)) /* contains the node we search and there is no other sub-clique before */
 134         {
 135                 if (bitset_is_set(live, get_irn_idx(element->content_first.irn)) && element->content_first.irn != irn) /* irn is still alive and not the node we search a sub-clique for */
 136                 {
 137                         bitset_set(my_live, get_irn_idx(element->content_first.irn));
 138                 }
 139
 140                 if (bitset_is_set(live, get_irn_idx(element->content_second.irn))&& element->content_second.irn != irn) /* irn is still alive and not the node we search a sub-clique for */
 141                 {
 142                         bitset_set(my_live, get_irn_idx(element->content_second.irn));
 143                 }
 144                 res = NULL;
 145         }
 146         else
 147         {
 148                 if (element && element->kind == 8889)
 149                 { /* this was a "single-node-clique" */
 150                         res = NULL;
 151                 }
 152
 153                 if (element && (element->kind == 3101)
 154                         && (element->content_second.irn == irn)) /* sub-clique contains node, return previous sub-clique */
 155                 {
 156                         res = element->content_first.element;
 157                 }
 158                 else
 159                 {
 160                         if (element && element->kind == 3101) /* look at previous sub-cliques if the contain the node you are searching for*/
 161                         {
 162                                 if (bitset_is_set(live, get_irn_idx(element->content_second.irn))) /* irn is still alive */
 163                                 {
 164                                         bitset_set(my_live, get_irn_idx(element->content_second.irn));
 165                                 }
 166                                 ifg->curr_element = element->content_first.element;
 167                                 res = get_last_sub_clique(ifg, live, my_live, irn);
 168                         }
 169                         else
 170                         {
 171                                 res = NULL;
 172                         }
 173                 }
 174         }
 175         return res;
 176 }
 177
 178 static void find_neighbour_walker(ir_node *bl, void *data)
 179 {
 180         ifg_pointer_t    *ifg      = data;
 181         struct list_head *head     = get_block_border_head(ifg->env, bl);
 182         int              was_def   = 0;
 183         int              was_first = 0;
 184         ir_node          *first    = NULL;
 185         bitset_t         *live     = bitset_malloc(get_irg_last_idx(ifg->env->irg));
 186         bitset_t         *my_live;
 187         bitset_pos_t     my_elm;
 188         border_t         *b;
 189         ir_node          *my_irn;
 190         element_content  last_irn;
 191         element_content  last_element;
 192
 193         last_irn.irn         = NULL;
 194         last_element.element = NULL;
 195
 196         assert(is_Block(bl) && "There is no block to work on.");
 197
 198         foreach_border_head(head, b) /* follow the borders of the block */
 199         {
 200                 ir_node       *irn     = b->irn;
 201                 ptr_element_t *element = NULL;
 202
 203                 if (b->is_def) /* b is a new node */
 204                 {
 205                         bitset_set(live, get_irn_idx(irn));
 206                         if (last_element.element)
 207                         {
 208                                 element = ptr_get_new_element(ifg);
 209                                 element->content_first.element = last_element.element;
 210                                 element->content_second.irn = b->irn;
 211                                 element->kind = 3101; /* first is an element, second an ir_node */
 212
 213                                 last_element.element = element;
 214                                 ifg->curr_element = element;
 215                         }
 216                         else
 217                         {
 218                                 if (last_irn.irn)       /* create new sub-clique */
 219                                 {
 220                                         element = ptr_get_new_element(ifg);
 221                                         element->content_first.irn = last_irn.irn;
 222                                         element->content_second.irn = b->irn;
 223                                         element->kind = 8888; /* both are ir_nodes */
 224
 225                                         last_element.element = element;
 226                                         ifg->curr_element    = element;
 227                                         last_irn.irn         = NULL;
 228                                 }
 229                                 else
 230                                 {
 231                                         last_irn.irn = b->irn;  /* needed to create first sub-clique */
 232                                         last_element.element = NULL;
 233                                 }
 234                         }
 235
 236                         was_def = 1;
 237                 }
 238                 else
 239                 {
 240                         if (was_def == 1) /* if there is a USE after a DEF... */
 241                         {
 242                                 if (!last_element.element)
 243                                 { /* there was only one element in the clique */
 244                                         element = ptr_get_new_element(ifg);
 245                                         element->kind = 8889; /* first is a node, second is NULL, because this is a "single-node-clique" */
 246                                         element->content_first.irn = last_irn.irn;
 247                                         last_irn.irn = NULL;
 248                                         element = NULL;
 249                                         ifg->curr_element = NULL;
 250                                 }
 251
 252
 253                                 write_pointers(live, ifg); /* ...write a pointer to the highest sub-clique for each living node. */
 254                                 was_def = 0;
 255                         }
 256
 257                         my_live = bitset_malloc(get_irg_last_idx(ifg->env->irg));
 258                         last_element.element = get_last_sub_clique(ifg, live, my_live, irn);
 259
 260                         /* check and add still living nodes */
 261                         if (bitset_popcnt(my_live) > 1)
 262                         {
 263                                 if (last_element.element)
 264                                 {
 265                                         bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
 266                                         {
 267                                                 ptr_element_t *my_element = ptr_get_new_element(ifg);
 268                                                 my_element->content_first.element = last_element.element;
 269                                                 my_element->content_second.irn = my_irn;
 270                                                 my_element->kind = 3101; /* first is an element, second an ir_node */
 271
 272                                                 last_element.element = my_element;
 273                                                 ifg->curr_element = my_element;
 274                                         }
 275                                 }
 276                                 else
 277                                 {
 278                                         bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
 279                                         {
 280                                                 ptr_element_t *my_element = NULL;
 281                                                 if (!first && !was_first)
 282                                                 {
 283                                                         first = my_irn;
 284                                                         was_first = 1;
 285                                                 }
 286                                                 else
 287                                                 {
 288                                                         if (first && was_first)
 289                                                         {
 290                                                                 my_element = ptr_get_new_element(ifg);
 291                                                                 my_element->content_first.irn = first;
 292                                                                 my_element->content_second.irn = my_irn;
 293                                                                 my_element->kind = 8888; /* both are ir_nodes */
 294                                                                 last_element.element = my_element;
 295                                                                 ifg->curr_element = my_element;
 296                                                                 first = NULL;
 297                                                         }
 298                                                         else
 299                                                         {
 300                                                                 my_element = ptr_get_new_element(ifg);
 301                                                                 my_element->content_first.element = last_element.element;
 302                                                                 my_element->content_second.irn = my_irn;
 303                                                                 my_element->kind = 3101; /* first is an element, second an ir_node */
 304                                                                 last_element.element = my_element;
 305                                                                 ifg->curr_element = my_element;
 306                                                         }
 307                                                 }
 308                                         }
 309                                         was_first = 0;
 310                                 }
 311                         }
 312                         else
 313                         {
 314                                 if (bitset_popcnt(my_live) == 1) /* there is only one node left */
 315                                 {
 316                                         if (last_element.element)
 317                                         {
 318                                                 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
 319                                                 {
 320                                                         ptr_element_t *my_element = ptr_get_new_element(ifg);
 321                                                         my_element->content_first.element = last_element.element;
 322                                                         my_element->content_second.irn = my_irn;
 323                                                         my_element->kind = 3101; /* first is an element, second an ir_node */
 324
 325                                                         last_element.element = my_element;
 326                                                         ifg->curr_element = my_element;
 327                                                 }
 328                                         }
 329                                         else
 330                                         {
 331                                                 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn);
 332                                                 {
 333                                                         ptr_element_t *my_element = ptr_get_new_element(ifg);
 334                                                         my_element->content_first.irn = my_irn;
 335                                                         my_element->content_second.irn = NULL;
 336                                                         my_element->kind = 8889;
 337                                                         last_element.element =  my_element;
 338                                                         ifg->curr_element = my_element;
 339                                                 }
 340                                         }
 341                                 }
 342                         }
 343                         bitset_free(my_live);
 344                         bitset_remv_irn(live, irn);
 345                 }
 346         }
 347         bitset_free(live);
 348 }
 349
 350 static ir_node *get_first_irn(const ifg_pointer_t *ifg, ptr_iter_t *it)
 351 {
 352         ir_node *irn = phase_get_first_node(&ifg->ph);
 353
 354         if (! irn)
 355                 return NULL;
 356
 357         it->curr_irn = irn;
 358
 359         return irn;
 360 }
 361
 362 static ir_node *get_next_irn(ptr_iter_t *it)
 363 {
 364         ir_node *irn = phase_get_next_node(&it->ifg->ph, it->curr_irn);
 365
 366         if (! irn)
 367                 return NULL;
 368
 369         it->curr_irn = irn;
 370
 371         return irn;
 372 }
 373
 374 static ir_node *get_next_neighbour(ptr_iter_t *it)
 375 {
 376         ir_node       *res;
 377         ptr_head_t    *head;
 378         ptr_element_t *element;
 379
 380         element = it->curr_element_t;
 381
 382         if (element == NULL)
 383         {
 384                 if (it->curr_ptr_head->list.next != &it->first_head->list)
 385                 {
 386                         head = list_entry(it->curr_ptr_head->list.next, ptr_head_t, list);
 387                         it->curr_ptr_head = head;
 388                         element = head->element;
 389                 }
 390                 else
 391                         return NULL; /* there are no more neighbours */
 392         }
 393
 394         if (element && element->kind == 8889) /* node has no neighbours */
 395         {
 396                 res = element->content_first.irn;
 397                 it->curr_element_t = NULL;
 398         }
 399         else
 400         {
 401                 if (element && element->kind == 8888) /* node has only one more neighbour */
 402                 {
 403                         if (it->get_first)
 404                         {
 405                                 if (element->content_first.irn != it->irn)
 406                                 {
 407                                         res = element->content_first.irn;
 408                                         it->get_first = 0;
 409                                         it->curr_element_t = NULL;
 410                                 }
 411                                 else
 412                                 {
 413                                         it->get_first = 0;
 414                                         it->curr_element_t = NULL;
 415                                         it->sub_call++;
 416                                         res = get_next_neighbour(it);
 417                                         it->sub_call--;
 418                                 }
 419                         }
 420                         else
 421                         {
 422                                 if (element->content_second.irn != it->irn)
 423                                 {
 424                                         res = element->content_second.irn;
 425                                         it->get_first = 1;
 426                                         it->curr_element_t = element;
 427                                 }
 428                                 else
 429                                 {
 430                                         it->get_first = 1;
 431                                         it->curr_element_t = element;
 432                                         it->sub_call++;
 433                                         res = get_next_neighbour(it);
 434                                         it->sub_call--;
 435                                 }
 436                         }
 437                 }
 438                 else
 439                 {
 440                         if (element && element->kind == 3101)
 441                         {
 442                                 it->curr_element_t = element->content_first.element;
 443                                 res = element->content_second.irn;
 444                         }
 445                         else
 446                         { /* element is only an ir_node */// TODO
 447                                 it->curr_element_t = NULL;
 448                                 return NULL;
 449                         }
 450                 }
 451         }
 452
 453         if (res && !it->sub_call)
 454         {
 455                 if (bitset_contains_irn(it->visited_neighbours, res) || res == it->irn)
 456                 {
 457                         res = get_next_neighbour(it);
 458                 }
 459                 else
 460                 {
 461                         bitset_set(it->visited_neighbours, get_irn_idx(res));
 462                 }
 463         }
 464
 465         return res;
 466 }
 467
 468 static ir_node *get_first_neighbour(const ifg_pointer_t *ifg, ptr_iter_t *it, const ir_node *irn)
 469 {
 470         ir_node       *res;
 471         ptr_head_t    *head;
 472         ptr_element_t *element;
 473         bitset_t      *bitsetvisited_neighbours = bitset_malloc(get_irg_last_idx(ifg->env->irg));
 474
 475         it->ifg       = ifg;
 476         it->irn       = irn;
 477         it->get_first = 0;
 478         it->sub_call  = 0;
 479
 480         it->visited_neighbours = bitsetvisited_neighbours;
 481
 482         head = phase_get_irn_data(&ifg->ph, irn);
 483         if (! head)
 484                 return NULL;
 485         else
 486         {
 487                 it->first_head = head;
 488                 head = list_entry(it->first_head->list.next, ptr_head_t, list); /* because first element is NULL */
 489                 it->curr_ptr_head = head;
 490                 element = head->element;
 491         }
 492
 493         if (element && element->kind == 8889) /* node has no neighbours */
 494         {
 495                 res = element->content_first.irn;
 496                 it->curr_element_t = NULL;
 497         }
 498         else
 499         {
 500                 if (element && element->kind == 8888) /* node has only one neighbour */
 501                 {
 502                         if (it->get_first)
 503                         {
 504                                 if (element->content_first.irn != it->irn)
 505                                 {
 506                                         res = element->content_first.irn;
 507                                         it->get_first = 0;
 508                                         it->curr_element_t = NULL;
 509                                 }
 510                                 else
 511                                 {
 512                                         it->get_first = 0;
 513                                         it->curr_element_t = NULL;
 514                                         it->sub_call++;
 515                                         res = get_next_neighbour(it);
 516                                         it->sub_call--;
 517                                 }
 518                         }
 519                         else
 520                         {
 521                                 if (element->content_second.irn != it->irn)
 522                                 {
 523                                         res = element->content_second.irn;
 524                                         it->curr_element_t = element;
 525                                         it->get_first = 1;
 526                                 }
 527                                 else
 528                                 {
 529                                         it->get_first = 1;
 530                                         it->curr_element_t = element;
 531                                         it->sub_call++;
 532                                         res = get_next_neighbour(it);
 533                                         it->sub_call--;
 534                                 }
 535                         }
 536                 }
 537                 else
 538                         if (element && element->kind == 3101)
 539                         {
 540                                 it->curr_element_t = element->content_first.element;
 541                                 res = element->content_second.irn;
 542                         }
 543                         else
 544                         { /* element is only an ir_node */
 545                                 it->curr_element_t = NULL;
 546                                 return NULL;
 547                         }
 548         }
 549
 550         if (res && !it->sub_call)
 551         {
 552                 if (bitset_contains_irn(it->visited_neighbours, res) || res == it->irn)
 553                 {
 554                         res = get_next_neighbour(it);
 555                 }
 556                 else
 557                 {
 558                         bitset_set(it->visited_neighbours, get_irn_idx(res));
 559                 }
 560         }
 561
 562         return res;
 563 }
 564
 565
 566
 567 /* PUBLIC FUNCTIONS */
 568
 569 static void ifg_pointer_free(void *self)
 570 {
 571         ifg_pointer_t *ifg = self;
 572         obstack_free(&ifg->obst, NULL);
 573         phase_free(&ifg->ph);
 574
 575         free(self);
 576 }
 577
 578 static int ifg_pointer_connected(const void *self, const ir_node *a, const ir_node *b)
 579 {
 580         const ifg_pointer_t *ifg = self;
 581         int                 connected = -1;
 582         ptr_iter_t          it;
 583         ir_node             *irn = NULL;
 584
 585         irn       = get_first_neighbour(ifg, &it, a);
 586         connected = 0;
 587         while (irn != NULL)
 588         {
 589                 if (irn == b)
 590                 {
 591                         connected = 1;
 592                         break;
 593                 }
 594                 irn = get_next_neighbour(&it);
 595         }
 596
 597         return connected;
 598 }
 599
 600 static ir_node *ifg_pointer_neighbours_begin(const void *self, void *iter, const ir_node *irn)
 601 {
 602         return get_first_neighbour(self, iter, irn);
 603 }
 604
 605 static ir_node *ifg_pointer_neighbours_next(const void *self, void *iter)
 606 {
 607         (void) self;
 608         return get_next_neighbour(iter);
 609 }
 610
 611 static void ifg_pointer_neighbours_break(const void *self, void *iter)
 612 {
 613         ptr_iter_t *it = iter;
 614         (void) self;
 615
 616         bitset_free(it->visited_neighbours);
 617
 618         return;
 619 }
 620
 621 static ir_node *ifg_pointer_nodes_begin(const void *self, void *iter)
 622 {
 623         return get_first_irn(self, iter);
 624 }
 625
 626 static ir_node *ifg_pointer_nodes_next(const void *self, void *iter)
 627 {
 628         (void) self;
 629         return get_next_irn(iter);
 630 }
 631
 632 static void ifg_pointer_nodes_break(const void *self, void *iter)
 633 {
 634         (void) self;
 635         (void) iter;
 636         return;
 637 }
 638
 639 static int ifg_pointer_degree(const void *self, const ir_node *irn)
 640 {
 641         int degree = -1;
 642         ptr_iter_t it;
 643
 644         irn = get_first_neighbour(self, &it, irn);
 645         degree = 0;
 646         while (irn != NULL)
 647         {
 648                 degree++;
 649                 irn = get_next_neighbour(&it);
 650         }
 651
 652         return degree;
 653 }
 654
 655 static const be_ifg_impl_t ifg_pointer_impl = {
 656         sizeof(ptr_iter_t),
 657         sizeof(ptr_iter_t),
 658         0,
 659         ifg_pointer_free,
 660         ifg_pointer_connected,
 661         ifg_pointer_neighbours_begin,
 662         ifg_pointer_neighbours_next,
 663         ifg_pointer_neighbours_break,
 664         ifg_pointer_nodes_begin,
 665         ifg_pointer_nodes_next,
 666         ifg_pointer_nodes_break,
 667         NULL,
 668         NULL,
 669         NULL,
 670         ifg_pointer_degree
 671 };
 672
 673 be_ifg_t *be_ifg_pointer_new(const be_chordal_env_t *env)
 674 {
 675         ifg_pointer_t *ifg      = xmalloc(sizeof(*ifg));
 676         ifg->impl               = &ifg_pointer_impl;
 677         ifg->env                        = env;
 678
 679         phase_init(&ifg->ph, "ptr_map", env->irg, PHASE_DEFAULT_GROWTH, ptr_irn_data_init, NULL);
 680         obstack_init(&ifg->obst);
 681
 682         dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
 683
 684         obstack_finish(&ifg->obst);
 685         return (be_ifg_t *) ifg;
 686 }