gcc/et-forest.c

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