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