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