gcc/et-forest.c

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