gcc/et-forest.c

   1 /* ET-trees data structure implementation.
   2    Contributed by Pavel Nejedly
   3    Copyright (C) 2002, 2003, 2004 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., 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, 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 /* Sets father of et tree T to FATHER.  */
 503
 504 void
 505 et_set_father (struct et_node *t, struct et_node *father)
 506 {
 507   struct et_node *left, *right;
 508   struct et_occ *rmost, *left_part, *new_f_occ, *p;
 509
 510   /* Update the path represented in the splay tree.  */
 511   new_f_occ = et_new_occ (father);
 512
 513   rmost = father->rightmost_occ;
 514   et_splay (rmost);
 515
 516   left_part = rmost->prev;
 517
 518   p = t->rightmost_occ;
 519   et_splay (p);
 520
 521   set_prev (new_f_occ, left_part);
 522   set_next (new_f_occ, p);
 523
 524   p->depth++;
 525   p->min++;
 526   et_recomp_min (new_f_occ);
 527
 528   set_prev (rmost, new_f_occ);
 529
 530   if (new_f_occ->min + rmost->depth < rmost->min)
 531     {
 532       rmost->min = new_f_occ->min + rmost->depth;
 533       rmost->min_occ = new_f_occ->min_occ;
 534     }
 535
 536   t->parent_occ = new_f_occ;
 537
 538   /* Update the tree.  */
 539   t->father = father;
 540   right = father->son;
 541   if (right)
 542     left = right->left;
 543   else
 544     left = right = t;
 545
 546   left->right = t;
 547   right->left = t;
 548   t->left = left;
 549   t->right = right;
 550
 551   father->son = t;
 552
 553 #ifdef DEBUG_ET
 554   et_check_tree_sanity (rmost);
 555   record_path_before (rmost);
 556 #endif
 557 }
 558
 559 /* Splits the edge from T to its father.  */
 560
 561 void
 562 et_split (struct et_node *t)
 563 {
 564   struct et_node *father = t->father;
 565   struct et_occ *r, *l, *rmost, *p_occ;
 566
 567   /* Update the path represented by the splay tree.  */
 568   rmost = t->rightmost_occ;
 569   et_splay (rmost);
 570
 571   for (r = rmost->next; r->prev; r = r->prev)
 572     continue;
 573   et_splay (r);
 574
 575   r->prev->parent = NULL;
 576   p_occ = t->parent_occ;
 577   et_splay (p_occ);
 578   t->parent_occ = NULL;
 579
 580   l = p_occ->prev;
 581   p_occ->next->parent = NULL;
 582
 583   set_prev (r, l);
 584
 585   et_recomp_min (r);
 586
 587   et_splay (rmost);
 588   rmost->depth = 0;
 589   rmost->min = 0;
 590
 591   pool_free (et_occurrences, p_occ);
 592
 593   /* Update the tree.  */
 594   if (father->son == t)
 595     father->son = t->right;
 596   if (father->son == t)
 597     father->son = NULL;
 598   else
 599     {
 600       t->left->right = t->right;
 601       t->right->left = t->left;
 602     }
 603   t->left = t->right = NULL;
 604   t->father = NULL;
 605
 606 #ifdef DEBUG_ET
 607   et_check_tree_sanity (rmost);
 608   record_path_before (rmost);
 609
 610   et_check_tree_sanity (r);
 611   record_path_before (r);
 612 #endif
 613 }
 614
 615 /* Finds the nearest common ancestor of the nodes N1 and N2.  */
 616
 617 struct et_node *
 618 et_nca (struct et_node *n1, struct et_node *n2)
 619 {
 620   struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
 621   struct et_occ *l, *r, *ret;
 622   int mn;
 623
 624   if (n1 == n2)
 625     return n1;
 626
 627   et_splay (o1);
 628   l = o1->prev;
 629   r = o1->next;
 630   if (l)
 631     l->parent = NULL;
 632   if (r)
 633     r->parent = NULL;
 634   et_splay (o2);
 635
 636   if (l == o2 || (l && l->parent != NULL))
 637     {
 638       ret = o2->next;
 639
 640       set_prev (o1, o2);
 641       if (r)
 642         r->parent = o1;
 643     }
 644   else
 645     {
 646       ret = o2->prev;
 647
 648       set_next (o1, o2);
 649       if (l)
 650         l->parent = o1;
 651     }
 652
 653   if (0 < o2->depth)
 654     {
 655       om = o1;
 656       mn = o1->depth;
 657     }
 658   else
 659     {
 660       om = o2;
 661       mn = o2->depth + o1->depth;
 662     }
 663
 664 #ifdef DEBUG_ET
 665   et_check_tree_sanity (o2);
 666 #endif
 667
 668   if (ret && ret->min + o1->depth + o2->depth < mn)
 669     return ret->min_occ->of;
 670   else
 671     return om->of;
 672 }
 673
 674 /* Checks whether the node UP is an ancestor of the node DOWN.  */
 675
 676 bool
 677 et_below (struct et_node *down, struct et_node *up)
 678 {
 679   struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
 680   struct et_occ *l, *r;
 681
 682   if (up == down)
 683     return true;
 684
 685   et_splay (u);
 686   l = u->prev;
 687   r = u->next;
 688
 689   if (!l)
 690     return false;
 691
 692   l->parent = NULL;
 693
 694   if (r)
 695     r->parent = NULL;
 696
 697   et_splay (d);
 698
 699   if (l == d || l->parent != NULL)
 700     {
 701       if (r)
 702         r->parent = u;
 703       set_prev (u, d);
 704 #ifdef DEBUG_ET
 705       et_check_tree_sanity (u);
 706 #endif
 707     }
 708   else
 709     {
 710       l->parent = u;
 711
 712       /* In case O1 and O2 are in two different trees, we must just restore the
 713          original state.  */
 714       if (r && r->parent != NULL)
 715         set_next (u, d);
 716       else
 717         set_next (u, r);
 718
 719 #ifdef DEBUG_ET
 720       et_check_tree_sanity (u);
 721 #endif
 722       return false;
 723     }
 724
 725   if (0 >= d->depth)
 726     return false;
 727
 728   return !d->next || d->next->min + d->depth >= 0;
 729 }