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