gcc/et-forest.c

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