gcc/et-forest.c

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