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