gcc/et-forest.c

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