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