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