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 static int len;
 210 static void *datas[100000];
 211 static int depths[100000];
 212
 213 /* Records the path represented by OCC, with depth incremented by DEPTH.  */
 214
 215 static int
 216 record_path_before_1 (struct et_occ *occ, int depth)
 217 {
 218   int mn, m;
 219
 220   depth += occ->depth;
 221   mn = depth;
 222
 223   if (occ->prev)
 224     {
 225       m = record_path_before_1 (occ->prev, depth);
 226       if (m < mn)
 227         mn = m;
 228     }
 229
 230   fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
 231   depths[len] = depth;
 232   datas[len] = occ->of;
 233   len++;
 234
 235   if (occ->next)
 236     {
 237       m = record_path_before_1 (occ->next, depth);
 238       if (m < mn)
 239         mn = m;
 240     }
 241
 242   if (mn != occ->min + depth - occ->depth)
 243     abort ();
 244
 245   return mn;
 246 }
 247
 248 /* Records the path represented by a tree containing OCC.  */
 249
 250 static void
 251 record_path_before (struct et_occ *occ)
 252 {
 253   while (occ->parent)
 254     occ = occ->parent;
 255
 256   len = 0;
 257   record_path_before_1 (occ, 0);
 258   fprintf (stderr, "\n");
 259 }
 260
 261 /* Checks whether the path represented by OCC, with depth incremented by DEPTH,
 262    was not changed since the last recording.  */
 263
 264 static int
 265 check_path_after_1 (struct et_occ *occ, int depth)
 266 {
 267   int mn, m;
 268
 269   depth += occ->depth;
 270   mn = depth;
 271
 272   if (occ->next)
 273     {
 274       m = check_path_after_1 (occ->next, depth);
 275       if (m < mn)
 276         mn =  m;
 277     }
 278
 279   len--;
 280   if (depths[len] != depth
 281       || datas[len] != occ->of)
 282     abort ();
 283
 284   if (occ->prev)
 285     {
 286       m = check_path_after_1 (occ->prev, depth);
 287       if (m < mn)
 288         mn =  m;
 289     }
 290
 291   if (mn != occ->min + depth - occ->depth)
 292     abort ();
 293
 294   return mn;
 295 }
 296
 297 /* Checks whether the path represented by a tree containing OCC was
 298    not changed since the last recording.  */
 299
 300 static void
 301 check_path_after (struct et_occ *occ)
 302 {
 303   while (occ->parent)
 304     occ = occ->parent;
 305
 306   check_path_after_1 (occ, 0);
 307   if (len != 0)
 308     abort ();
 309 }
 310
 311 #endif
 312
 313 /* Splay the occurrence OCC to the root of the tree.  */
 314
 315 static void
 316 et_splay (struct et_occ *occ)
 317 {
 318   struct et_occ *f, *gf, *ggf;
 319   int occ_depth, f_depth, gf_depth;
 320
 321 #ifdef DEBUG_ET
 322   record_path_before (occ);
 323   et_check_tree_sanity (occ);
 324 #endif
 325
 326   while (occ->parent)
 327     {
 328       occ_depth = occ->depth;
 329
 330       f = occ->parent;
 331       f_depth = f->depth;
 332
 333       gf = f->parent;
 334
 335       if (!gf)
 336         {
 337           set_depth_add (occ, f_depth);
 338           occ->min_occ = f->min_occ;
 339           occ->min = f->min;
 340
 341           if (f->prev == occ)
 342             {
 343               /* zig */
 344               set_prev (f, occ->next);
 345               set_next (occ, f);
 346               set_depth_add (f->prev, occ_depth);
 347             }
 348           else
 349             {
 350               /* zag */
 351               set_next (f, occ->prev);
 352               set_prev (occ, f);
 353               set_depth_add (f->next, occ_depth);
 354             }
 355           set_depth (f, -occ_depth);
 356           occ->parent = NULL;
 357
 358           et_recomp_min (f);
 359 #ifdef DEBUG_ET
 360           et_check_tree_sanity (occ);
 361           check_path_after (occ);
 362 #endif
 363           return;
 364         }
 365
 366       gf_depth = gf->depth;
 367
 368       set_depth_add (occ, f_depth + gf_depth);
 369       occ->min_occ = gf->min_occ;
 370       occ->min = gf->min;
 371
 372       ggf = gf->parent;
 373
 374       if (gf->prev == f)
 375         {
 376           if (f->prev == occ)
 377             {
 378               /* zig zig */
 379               set_prev (gf, f->next);
 380               set_prev (f, occ->next);
 381               set_next (occ, f);
 382               set_next (f, gf);
 383
 384               set_depth (f, -occ_depth);
 385               set_depth_add (f->prev, occ_depth);
 386               set_depth (gf, -f_depth);
 387               set_depth_add (gf->prev, f_depth);
 388             }
 389           else
 390             {
 391               /* zag zig */
 392               set_prev (gf, occ->next);
 393               set_next (f, occ->prev);
 394               set_prev (occ, f);
 395               set_next (occ, gf);
 396
 397               set_depth (f, -occ_depth);
 398               set_depth_add (f->next, occ_depth);
 399               set_depth (gf, -occ_depth - f_depth);
 400               set_depth_add (gf->prev, occ_depth + f_depth);
 401             }
 402         }
 403       else
 404         {
 405           if (f->prev == occ)
 406             {
 407               /* zig zag */
 408               set_next (gf, occ->prev);
 409               set_prev (f, occ->next);
 410               set_prev (occ, gf);
 411               set_next (occ, f);
 412
 413               set_depth (f, -occ_depth);
 414               set_depth_add (f->prev, occ_depth);
 415               set_depth (gf, -occ_depth - f_depth);
 416               set_depth_add (gf->next, occ_depth + f_depth);
 417             }
 418           else
 419             {
 420               /* zag zag */
 421               set_next (gf, f->prev);
 422               set_next (f, occ->prev);
 423               set_prev (occ, f);
 424               set_prev (f, gf);
 425
 426               set_depth (f, -occ_depth);
 427               set_depth_add (f->next, occ_depth);
 428               set_depth (gf, -f_depth);
 429               set_depth_add (gf->next, f_depth);
 430             }
 431         }
 432
 433       occ->parent = ggf;
 434       if (ggf)
 435         {
 436           if (ggf->prev == gf)
 437             ggf->prev = occ;
 438           else
 439             ggf->next = occ;
 440         }
 441
 442       et_recomp_min (gf);
 443       et_recomp_min (f);
 444 #ifdef DEBUG_ET
 445       et_check_tree_sanity (occ);
 446 #endif
 447     }
 448
 449 #ifdef DEBUG_ET
 450   et_check_sanity (occ);
 451   check_path_after (occ);
 452 #endif
 453 }
 454
 455 /* Create a new et tree occurrence of NODE.  */
 456
 457 static struct et_occ *
 458 et_new_occ (struct et_node *node)
 459 {
 460   struct et_occ *nw;
 461
 462   if (!et_occurrences)
 463     et_occurrences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);
 464   nw = pool_alloc (et_occurrences);
 465
 466   nw->of = node;
 467   nw->parent = NULL;
 468   nw->prev = NULL;
 469   nw->next = NULL;
 470
 471   nw->depth = 0;
 472   nw->min_occ = nw;
 473   nw->min = 0;
 474
 475   return nw;
 476 }
 477
 478 /* Create a new et tree containing DATA.  */
 479
 480 struct et_node *
 481 et_new_tree (void *data)
 482 {
 483   struct et_node *nw;
 484
 485   if (!et_nodes)
 486     et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);
 487   nw = pool_alloc (et_nodes);
 488
 489   nw->data = data;
 490   nw->father = NULL;
 491   nw->left = NULL;
 492   nw->right = NULL;
 493   nw->son = NULL;
 494
 495   nw->rightmost_occ = et_new_occ (nw);
 496   nw->parent_occ = NULL;
 497
 498   return nw;
 499 }
 500
 501 /* Releases et tree T.  */
 502
 503 void
 504 et_free_tree (struct et_node *t)
 505 {
 506   while (t->son)
 507     et_split (t->son);
 508
 509   if (t->father)
 510     et_split (t);
 511
 512   pool_free (et_occurrences, t->rightmost_occ);
 513   pool_free (et_nodes, t);
 514 }
 515
 516 /* Sets father of et tree T to FATHER.  */
 517
 518 void
 519 et_set_father (struct et_node *t, struct et_node *father)
 520 {
 521   struct et_node *left, *right;
 522   struct et_occ *rmost, *left_part, *new_f_occ, *p;
 523
 524   /* Update the path represented in the splay tree.  */
 525   new_f_occ = et_new_occ (father);
 526
 527   rmost = father->rightmost_occ;
 528   et_splay (rmost);
 529
 530   left_part = rmost->prev;
 531
 532   p = t->rightmost_occ;
 533   et_splay (p);
 534
 535   set_prev (new_f_occ, left_part);
 536   set_next (new_f_occ, p);
 537
 538   p->depth++;
 539   p->min++;
 540   et_recomp_min (new_f_occ);
 541
 542   set_prev (rmost, new_f_occ);
 543
 544   if (new_f_occ->min + rmost->depth < rmost->min)
 545     {
 546       rmost->min = new_f_occ->min + rmost->depth;
 547       rmost->min_occ = new_f_occ->min_occ;
 548     }
 549
 550   t->parent_occ = new_f_occ;
 551
 552   /* Update the tree.  */
 553   t->father = father;
 554   right = father->son;
 555   if (right)
 556     left = right->left;
 557   else
 558     left = right = t;
 559
 560   left->right = t;
 561   right->left = t;
 562   t->left = left;
 563   t->right = right;
 564
 565   father->son = t;
 566
 567 #ifdef DEBUG_ET
 568   et_check_tree_sanity (rmost);
 569   record_path_before (rmost);
 570 #endif
 571 }
 572
 573 /* Splits the edge from T to its father.  */
 574
 575 void
 576 et_split (struct et_node *t)
 577 {
 578   struct et_node *father = t->father;
 579   struct et_occ *r, *l, *rmost, *p_occ;
 580
 581   /* Update the path represented by the splay tree.  */
 582   rmost = t->rightmost_occ;
 583   et_splay (rmost);
 584
 585   for (r = rmost->next; r->prev; r = r->prev)
 586     continue;
 587   et_splay (r);
 588
 589   r->prev->parent = NULL;
 590   p_occ = t->parent_occ;
 591   et_splay (p_occ);
 592   t->parent_occ = NULL;
 593
 594   l = p_occ->prev;
 595   p_occ->next->parent = NULL;
 596
 597   set_prev (r, l);
 598
 599   et_recomp_min (r);
 600
 601   et_splay (rmost);
 602   rmost->depth = 0;
 603   rmost->min = 0;
 604
 605   pool_free (et_occurrences, p_occ);
 606
 607   /* Update the tree.  */
 608   if (father->son == t)
 609     father->son = t->right;
 610   if (father->son == t)
 611     father->son = NULL;
 612   else
 613     {
 614       t->left->right = t->right;
 615       t->right->left = t->left;
 616     }
 617   t->left = t->right = NULL;
 618   t->father = NULL;
 619
 620 #ifdef DEBUG_ET
 621   et_check_tree_sanity (rmost);
 622   record_path_before (rmost);
 623
 624   et_check_tree_sanity (r);
 625   record_path_before (r);
 626 #endif
 627 }
 628
 629 /* Finds the nearest common ancestor of the nodes N1 and N2.  */
 630
 631 struct et_node *
 632 et_nca (struct et_node *n1, struct et_node *n2)
 633 {
 634   struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
 635   struct et_occ *l, *r, *ret;
 636   int mn;
 637
 638   if (n1 == n2)
 639     return n1;
 640
 641   et_splay (o1);
 642   l = o1->prev;
 643   r = o1->next;
 644   if (l)
 645     l->parent = NULL;
 646   if (r)
 647     r->parent = NULL;
 648   et_splay (o2);
 649
 650   if (l == o2 || (l && l->parent != NULL))
 651     {
 652       ret = o2->next;
 653
 654       set_prev (o1, o2);
 655       if (r)
 656         r->parent = o1;
 657     }
 658   else
 659     {
 660       ret = o2->prev;
 661
 662       set_next (o1, o2);
 663       if (l)
 664         l->parent = o1;
 665     }
 666
 667   if (0 < o2->depth)
 668     {
 669       om = o1;
 670       mn = o1->depth;
 671     }
 672   else
 673     {
 674       om = o2;
 675       mn = o2->depth + o1->depth;
 676     }
 677
 678 #ifdef DEBUG_ET
 679   et_check_tree_sanity (o2);
 680 #endif
 681
 682   if (ret && ret->min + o1->depth + o2->depth < mn)
 683     return ret->min_occ->of;
 684   else
 685     return om->of;
 686 }
 687
 688 /* Checks whether the node UP is an ancestor of the node DOWN.  */
 689
 690 bool
 691 et_below (struct et_node *down, struct et_node *up)
 692 {
 693   struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
 694   struct et_occ *l, *r;
 695
 696   if (up == down)
 697     return true;
 698
 699   et_splay (u);
 700   l = u->prev;
 701   r = u->next;
 702
 703   if (!l)
 704     return false;
 705
 706   l->parent = NULL;
 707
 708   if (r)
 709     r->parent = NULL;
 710
 711   et_splay (d);
 712
 713   if (l == d || l->parent != NULL)
 714     {
 715       if (r)
 716         r->parent = u;
 717       set_prev (u, d);
 718 #ifdef DEBUG_ET
 719       et_check_tree_sanity (u);
 720 #endif
 721     }
 722   else
 723     {
 724       l->parent = u;
 725
 726       /* In case O1 and O2 are in two different trees, we must just restore the
 727          original state.  */
 728       if (r && r->parent != NULL)
 729         set_next (u, d);
 730       else
 731         set_next (u, r);
 732
 733 #ifdef DEBUG_ET
 734       et_check_tree_sanity (u);
 735 #endif
 736       return false;
 737     }
 738
 739   if (0 >= d->depth)
 740     return false;
 741
 742   return !d->next || d->next->min + d->depth >= 0;
 743 }