nsz Git - libfirm/blob - ir/be/beifg_pointer.c

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