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