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