gcc/et-forest.c

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