gcc/et-forest.c

   1 /* ET-trees data structure implementation.
   2    Contributed by Pavel Nejedly
   3    Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
   4
   5 This file is part of the libiberty library.
   6 Libiberty is free software; you can redistribute it and/or
   7 modify it under the terms of the GNU Library General Public
   8 License as published by the Free Software Foundation; either
   9 version 2 of the License, or (at your option) any later version.
  10
  11 Libiberty is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 Library General Public License for more details.
  15
  16 You should have received a copy of the GNU Library General Public
  17 License along with libiberty; see the file COPYING.LIB.  If
  18 not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.
  20
  21   The ET-forest structure is described in:
  22     D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
  23     J.  G'omput. System Sci., 26(3):362 381, 1983.
  24 */
  25
  26 #include "config.h"
  27 #include "system.h"
  28 #include "coretypes.h"
  29 #include "tm.h"
  30 #include "et-forest.h"
  31 #include "alloc-pool.h"
  32
  33 /* We do not enable this with ENABLE_CHECKING, since it is awfully slow.  */
  34 #undef DEBUG_ET
  35
  36 #ifdef DEBUG_ET
  37 #include "basic-block.h"
  38 #endif
  39
  40 /* The occurrence of a node in the et tree.  */
  41 struct et_occ
  42 {
  43   struct et_node *of;           /* The node.  */
  44
  45   struct et_occ *parent;        /* Parent in the splay-tree.  */
  46   struct et_occ *prev;          /* Left son in the splay-tree.  */
  47   struct et_occ *next;          /* Right son in the splay-tree.  */
  48
  49   int depth;                    /* The depth of the node is the sum of depth
  50                                    fields on the path to the root.  */
  51   int min;                      /* The minimum value of the depth in the subtree
  52                                    is obtained by adding sum of depth fields
  53                                    on the path to the root.  */
  54   struct et_occ *min_occ;       /* The occurrence in the subtree with the minimal
  55                                    depth.  */
  56 };
  57
  58 static alloc_pool et_nodes;
  59 static alloc_pool et_occurrences;
  60
  61 /* Changes depth of OCC to D.  */
  62
  63 static inline void
  64 set_depth (struct et_occ *occ, int d)
  65 {
  66   if (!occ)
  67     return;
  68
  69   occ->min += d - occ->depth;
  70   occ->depth = d;
  71 }
  72
  73 /* Adds D to the depth of OCC.  */
  74
  75 static inline void
  76 set_depth_add (struct et_occ *occ, int d)
  77 {
  78   if (!occ)
  79     return;
  80
  81   occ->min += d;
  82   occ->depth += d;
  83 }
  84
  85 /* Sets prev field of OCC to P.  */
  86
  87 static inline void
  88 set_prev (struct et_occ *occ, struct et_occ *t)
  89 {
  90 #ifdef DEBUG_ET
  91   if (occ == t)
  92     abort ();
  93 #endif
  94
  95   occ->prev = t;
  96   if (t)
  97     t->parent = occ;
  98 }
  99
 100 /* Sets next field of OCC to P.  */
 101
 102 static inline void
 103 set_next (struct et_occ *occ, struct et_occ *t)
 104 {
 105 #ifdef DEBUG_ET
 106   if (occ == t)
 107     abort ();
 108 #endif
 109
 110   occ->next = t;
 111   if (t)
 112     t->parent = occ;
 113 }
 114
 115 /* Recompute minimum for occurrence OCC.  */
 116
 117 static inline void
 118 et_recomp_min (struct et_occ *occ)
 119 {
 120   struct et_occ *mson = occ->prev;
 121
 122   if (!mson
 123       || (occ->next
 124           && mson->min > occ->next->min))
 125       mson = occ->next;
 126
 127   if (mson && mson->min < 0)
 128     {
 129       occ->min = mson->min + occ->depth;
 130       occ->min_occ = mson->min_occ;
 131     }
 132   else
 133     {
 134       occ->min = occ->depth;
 135       occ->min_occ = occ;
 136     }
 137 }
 138
 139 #ifdef DEBUG_ET
 140 /* Checks whether neighbourhood of OCC seems sane.  */
 141
 142 static void
 143 et_check_occ_sanity (struct et_occ *occ)
 144 {
 145   if (!occ)
 146     return;
 147
 148   if (occ->parent == occ)
 149     abort ();
 150
 151   if (occ->prev == occ)
 152     abort ();
 153
 154   if (occ->next == occ)
 155     abort ();
 156
 157   if (occ->next && occ->next == occ->prev)
 158     abort ();
 159
 160   if (occ->next)
 161     {
 162       if (occ->next == occ->parent)
 163         abort ();
 164
 165       if (occ->next->parent != occ)
 166         abort ();
 167     }
 168
 169   if (occ->prev)
 170     {
 171       if (occ->prev == occ->parent)
 172         abort ();
 173
 174       if (occ->prev->parent != occ)
 175         abort ();
 176     }
 177
 178   if (occ->parent
 179       && occ->parent->prev != occ
 180       && occ->parent->next != occ)
 181     abort ();
 182 }
 183
 184 /* Checks whether tree rooted at OCC is sane.  */
 185
 186 static void
 187 et_check_sanity (struct et_occ *occ)
 188 {
 189   et_check_occ_sanity (occ);
 190   if (occ->prev)
 191     et_check_sanity (occ->prev);
 192   if (occ->next)
 193     et_check_sanity (occ->next);
 194 }
 195
 196 /* Checks whether tree containing OCC is sane.  */
 197
 198 static void
 199 et_check_tree_sanity (struct et_occ *occ)
 200 {
 201   while (occ->parent)
 202     occ = occ->parent;
 203
 204   et_check_sanity (occ);
 205 }
 206
 207 /* For recording the paths.  */
 208
 209 /* An ad-hoc constant; if the function has more blocks, this won't work,
 210    but since it is used for debugging only, it does not matter.  */
 211 #define MAX_NODES 100000
 212
 213 static int len;
 214 static void *datas[MAX_NODES];
 215 static int depths[MAX_NODES];
 216
 217 /* Records the path represented by OCC, with depth incremented by DEPTH.  */
 218
 219 static int
 220 record_path_before_1 (struct et_occ *occ, int depth)
 221 {
 222   int mn, m;
 223
 224   depth += occ->depth;
 225   mn = depth;
 226
 227   if (occ->prev)
 228     {
 229       m = record_path_before_1 (occ->prev, depth);
 230       if (m < mn)
 231         mn = m;
 232     }
 233
 234   fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
 235
 236   if (len >= MAX_NODES)
 237     abort ();
 238
 239   depths[len] = depth;
 240   datas[len] = occ->of;
 241   len++;
 242
 243   if (occ->next)
 244     {
 245       m = record_path_before_1 (occ->next, depth);
 246       if (m < mn)
 247         mn = m;
 248     }
 249
 250   if (mn != occ->min + depth - occ->depth)
 251     abort ();
 252
 253   return mn;
 254 }
 255
 256 /* Records the path represented by a tree containing OCC.  */
 257
 258 static void
 259 record_path_before (struct et_occ *occ)
 260 {
 261   while (occ->parent)
 262     occ = occ->parent;
 263
 264   len = 0;
 265   record_path_before_1 (occ, 0);
 266   fprintf (stderr, "\n");
 267 }
 268
 269 /* Checks whether the path represented by OCC, with depth incremented by DEPTH,
 270    was not changed since the last recording.  */
 271
 272 static int
 273 check_path_after_1 (struct et_occ *occ, int depth)
 274 {
 275   int mn, m;
 276
 277   depth += occ->depth;
 278   mn = depth;
 279
 280   if (occ->next)
 281     {
 282       m = check_path_after_1 (occ->next, depth);
 283       if (m < mn)
 284         mn =  m;
 285     }
 286
 287   len--;
 288   if (depths[len] != depth
 289       || datas[len] != occ->of)
 290     abort ();
 291
 292   if (occ->prev)
 293     {
 294       m = check_path_after_1 (occ->prev, depth);
 295       if (m < mn)
 296         mn =  m;
 297     }
 298
 299   if (mn != occ->min + depth - occ->depth)
 300     abort ();
 301
 302   return mn;
 303 }
 304
 305 /* Checks whether the path represented by a tree containing OCC was
 306    not changed since the last recording.  */
 307
 308 static void
 309 check_path_after (struct et_occ *occ)
 310 {
 311   while (occ->parent)
 312     occ = occ->parent;
 313
 314   check_path_after_1 (occ, 0);
 315   if (len != 0)
 316     abort ();
 317 }
 318
 319 #endif
 320
 321 /* Splay the occurrence OCC to the root of the tree.  */
 322
 323 static void
 324 et_splay (struct et_occ *occ)
 325 {
 326   struct et_occ *f, *gf, *ggf;
 327   int occ_depth, f_depth, gf_depth;
 328
 329 #ifdef DEBUG_ET
 330   record_path_before (occ);
 331   et_check_tree_sanity (occ);
 332 #endif
 333
 334   while (occ->parent)
 335     {
 336       occ_depth = occ->depth;
 337
 338       f = occ->parent;
 339       f_depth = f->depth;
 340
 341       gf = f->parent;
 342
 343       if (!gf)
 344         {
 345           set_depth_add (occ, f_depth);
 346           occ->min_occ = f->min_occ;
 347           occ->min = f->min;
 348
 349           if (f->prev == occ)
 350             {
 351               /* zig */
 352               set_prev (f, occ->next);
 353               set_next (occ, f);
 354               set_depth_add (f->prev, occ_depth);
 355             }
 356           else
 357             {
 358               /* zag */
 359               set_next (f, occ->prev);
 360               set_prev (occ, f);
 361               set_depth_add (f->next, occ_depth);
 362             }
 363           set_depth (f, -occ_depth);
 364           occ->parent = NULL;
 365
 366           et_recomp_min (f);
 367 #ifdef DEBUG_ET
 368           et_check_tree_sanity (occ);
 369           check_path_after (occ);
 370 #endif
 371           return;
 372         }
 373
 374       gf_depth = gf->depth;
 375
 376       set_depth_add (occ, f_depth + gf_depth);
 377       occ->min_occ = gf->min_occ;
 378       occ->min = gf->min;
 379
 380       ggf = gf->parent;
 381
 382       if (gf->prev == f)
 383         {
 384           if (f->prev == occ)
 385             {
 386               /* zig zig */
 387               set_prev (gf, f->next);
 388               set_prev (f, occ->next);
 389               set_next (occ, f);
 390               set_next (f, gf);
 391
 392               set_depth (f, -occ_depth);
 393               set_depth_add (f->prev, occ_depth);
 394               set_depth (gf, -f_depth);
 395               set_depth_add (gf->prev, f_depth);
 396             }
 397           else
 398             {
 399               /* zag zig */
 400               set_prev (gf, occ->next);
 401               set_next (f, occ->prev);
 402               set_prev (occ, f);
 403               set_next (occ, gf);
 404
 405               set_depth (f, -occ_depth);
 406               set_depth_add (f->next, occ_depth);
 407               set_depth (gf, -occ_depth - f_depth);
 408               set_depth_add (gf->prev, occ_depth + f_depth);
 409             }
 410         }
 411       else
 412         {
 413           if (f->prev == occ)
 414             {
 415               /* zig zag */
 416               set_next (gf, occ->prev);
 417               set_prev (f, occ->next);
 418               set_prev (occ, gf);
 419               set_next (occ, f);
 420
 421               set_depth (f, -occ_depth);
 422               set_depth_add (f->prev, occ_depth);
 423               set_depth (gf, -occ_depth - f_depth);
 424               set_depth_add (gf->next, occ_depth + f_depth);
 425             }
 426           else
 427             {
 428               /* zag zag */
 429               set_next (gf, f->prev);
 430               set_next (f, occ->prev);
 431               set_prev (occ, f);
 432               set_prev (f, gf);
 433
 434               set_depth (f, -occ_depth);
 435               set_depth_add (f->next, occ_depth);
 436               set_depth (gf, -f_depth);
 437               set_depth_add (gf->next, f_depth);
 438             }
 439         }
 440
 441       occ->parent = ggf;
 442       if (ggf)
 443         {
 444           if (ggf->prev == gf)
 445             ggf->prev = occ;
 446           else
 447             ggf->next = occ;
 448         }
 449
 450       et_recomp_min (gf);
 451       et_recomp_min (f);
 452 #ifdef DEBUG_ET
 453       et_check_tree_sanity (occ);
 454 #endif
 455     }
 456
 457 #ifdef DEBUG_ET
 458   et_check_sanity (occ);
 459   check_path_after (occ);
 460 #endif
 461 }
 462
 463 /* Create a new et tree occurrence of NODE.  */
 464
 465 static struct et_occ *
 466 et_new_occ (struct et_node *node)
 467 {
 468   struct et_occ *nw;
 469
 470   if (!et_occurrences)
 471     et_occurrences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);
 472   nw = pool_alloc (et_occurrences);
 473
 474   nw->of = node;
 475   nw->parent = NULL;
 476   nw->prev = NULL;
 477   nw->next = NULL;
 478
 479   nw->depth = 0;
 480   nw->min_occ = nw;
 481   nw->min = 0;
 482
 483   return nw;
 484 }
 485
 486 /* Create a new et tree containing DATA.  */
 487
 488 struct et_node *
 489 et_new_tree (void *data)
 490 {
 491   struct et_node *nw;
 492
 493   if (!et_nodes)
 494     et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);
 495   nw = pool_alloc (et_nodes);
 496
 497   nw->data = data;
 498   nw->father = NULL;
 499   nw->left = NULL;
 500   nw->right = NULL;
 501   nw->son = NULL;
 502
 503   nw->rightmost_occ = et_new_occ (nw);
 504   nw->parent_occ = NULL;
 505
 506   return nw;
 507 }
 508
 509 /* Releases et tree T.  */
 510
 511 void
 512 et_free_tree (struct et_node *t)
 513 {
 514   while (t->son)
 515     et_split (t->son);
 516
 517   if (t->father)
 518     et_split (t);
 519
 520   pool_free (et_occurrences, t->rightmost_occ);
 521   pool_free (et_nodes, t);
 522 }
 523
 524 /* Sets father of et tree T to FATHER.  */
 525
 526 void
 527 et_set_father (struct et_node *t, struct et_node *father)
 528 {
 529   struct et_node *left, *right;
 530   struct et_occ *rmost, *left_part, *new_f_occ, *p;
 531
 532   /* Update the path represented in the splay tree.  */
 533   new_f_occ = et_new_occ (father);
 534
 535   rmost = father->rightmost_occ;
 536   et_splay (rmost);
 537
 538   left_part = rmost->prev;
 539
 540   p = t->rightmost_occ;
 541   et_splay (p);
 542
 543   set_prev (new_f_occ, left_part);
 544   set_next (new_f_occ, p);
 545
 546   p->depth++;
 547   p->min++;
 548   et_recomp_min (new_f_occ);
 549
 550   set_prev (rmost, new_f_occ);
 551
 552   if (new_f_occ->min + rmost->depth < rmost->min)
 553     {
 554       rmost->min = new_f_occ->min + rmost->depth;
 555       rmost->min_occ = new_f_occ->min_occ;
 556     }
 557
 558   t->parent_occ = new_f_occ;
 559
 560   /* Update the tree.  */
 561   t->father = father;
 562   right = father->son;
 563   if (right)
 564     left = right->left;
 565   else
 566     left = right = t;
 567
 568   left->right = t;
 569   right->left = t;
 570   t->left = left;
 571   t->right = right;
 572
 573   father->son = t;
 574
 575 #ifdef DEBUG_ET
 576   et_check_tree_sanity (rmost);
 577   record_path_before (rmost);
 578 #endif
 579 }
 580
 581 /* Splits the edge from T to its father.  */
 582
 583 void
 584 et_split (struct et_node *t)
 585 {
 586   struct et_node *father = t->father;
 587   struct et_occ *r, *l, *rmost, *p_occ;
 588
 589   /* Update the path represented by the splay tree.  */
 590   rmost = t->rightmost_occ;
 591   et_splay (rmost);
 592
 593   for (r = rmost->next; r->prev; r = r->prev)
 594     continue;
 595   et_splay (r);
 596
 597   r->prev->parent = NULL;
 598   p_occ = t->parent_occ;
 599   et_splay (p_occ);
 600   t->parent_occ = NULL;
 601
 602   l = p_occ->prev;
 603   p_occ->next->parent = NULL;
 604
 605   set_prev (r, l);
 606
 607   et_recomp_min (r);
 608
 609   et_splay (rmost);
 610   rmost->depth = 0;
 611   rmost->min = 0;
 612
 613   pool_free (et_occurrences, p_occ);
 614
 615   /* Update the tree.  */
 616   if (father->son == t)
 617     father->son = t->right;
 618   if (father->son == t)
 619     father->son = NULL;
 620   else
 621     {
 622       t->left->right = t->right;
 623       t->right->left = t->left;
 624     }
 625   t->left = t->right = NULL;
 626   t->father = NULL;
 627
 628 #ifdef DEBUG_ET
 629   et_check_tree_sanity (rmost);
 630   record_path_before (rmost);
 631
 632   et_check_tree_sanity (r);
 633   record_path_before (r);
 634 #endif
 635 }
 636
 637 /* Finds the nearest common ancestor of the nodes N1 and N2.  */
 638
 639 struct et_node *
 640 et_nca (struct et_node *n1, struct et_node *n2)
 641 {
 642   struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
 643   struct et_occ *l, *r, *ret;
 644   int mn;
 645
 646   if (n1 == n2)
 647     return n1;
 648
 649   et_splay (o1);
 650   l = o1->prev;
 651   r = o1->next;
 652   if (l)
 653     l->parent = NULL;
 654   if (r)
 655     r->parent = NULL;
 656   et_splay (o2);
 657
 658   if (l == o2 || (l && l->parent != NULL))
 659     {
 660       ret = o2->next;
 661
 662       set_prev (o1, o2);
 663       if (r)
 664         r->parent = o1;
 665     }
 666   else
 667     {
 668       ret = o2->prev;
 669
 670       set_next (o1, o2);
 671       if (l)
 672         l->parent = o1;
 673     }
 674
 675   if (0 < o2->depth)
 676     {
 677       om = o1;
 678       mn = o1->depth;
 679     }
 680   else
 681     {
 682       om = o2;
 683       mn = o2->depth + o1->depth;
 684     }
 685
 686 #ifdef DEBUG_ET
 687   et_check_tree_sanity (o2);
 688 #endif
 689
 690   if (ret && ret->min + o1->depth + o2->depth < mn)
 691     return ret->min_occ->of;
 692   else
 693     return om->of;
 694 }
 695
 696 /* Checks whether the node UP is an ancestor of the node DOWN.  */
 697
 698 bool
 699 et_below (struct et_node *down, struct et_node *up)
 700 {
 701   struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
 702   struct et_occ *l, *r;
 703
 704   if (up == down)
 705     return true;
 706
 707   et_splay (u);
 708   l = u->prev;
 709   r = u->next;
 710
 711   if (!l)
 712     return false;
 713
 714   l->parent = NULL;
 715
 716   if (r)
 717     r->parent = NULL;
 718
 719   et_splay (d);
 720
 721   if (l == d || l->parent != NULL)
 722     {
 723       if (r)
 724         r->parent = u;
 725       set_prev (u, d);
 726 #ifdef DEBUG_ET
 727       et_check_tree_sanity (u);
 728 #endif
 729     }
 730   else
 731     {
 732       l->parent = u;
 733
 734       /* In case O1 and O2 are in two different trees, we must just restore the
 735          original state.  */
 736       if (r && r->parent != NULL)
 737         set_next (u, d);
 738       else
 739         set_next (u, r);
 740
 741 #ifdef DEBUG_ET
 742       et_check_tree_sanity (u);
 743 #endif
 744       return false;
 745     }
 746
 747   if (0 >= d->depth)
 748     return false;
 749
 750   return !d->next || d->next->min + d->depth >= 0;
 751 }