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