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