1 /* ET-trees data structure implementation. 2 Contributed by Pavel Nejedly 3 Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2010 Free Software 4 Foundation, Inc. 5 6 This file is part of the libiberty library. 7 Libiberty is free software; you can redistribute it and/or 8 modify it under the terms of the GNU Library General Public 9 License as published by the Free Software Foundation; either 10 version 3 of the License, or (at your option) any later version. 11 12 Libiberty is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 Library General Public License for more details. 16 17 You should have received a copy of the GNU Library General Public 18 License along with libiberty; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. 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 "et-forest.h" 30 #include "alloc-pool.h" 31 32 /* We do not enable this with ENABLE_CHECKING, since it is awfully slow. */ 33 #undef DEBUG_ET 34 35 #ifdef DEBUG_ET 36 #include "basic-block.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 alloc_pool et_nodes; 58 static alloc_pool et_occurrences; 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 struct et_occ *nw; 446 447 if (!et_occurrences) 448 et_occurrences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300); 449 nw = (struct et_occ *) pool_alloc (et_occurrences); 450 451 nw->of = node; 452 nw->parent = NULL; 453 nw->prev = NULL; 454 nw->next = NULL; 455 456 nw->depth = 0; 457 nw->min_occ = nw; 458 nw->min = 0; 459 460 return nw; 461 } 462 463 /* Create a new et tree containing DATA. */ 464 465 struct et_node * 466 et_new_tree (void *data) 467 { 468 struct et_node *nw; 469 470 if (!et_nodes) 471 et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300); 472 nw = (struct et_node *) pool_alloc (et_nodes); 473 474 nw->data = data; 475 nw->father = NULL; 476 nw->left = NULL; 477 nw->right = NULL; 478 nw->son = NULL; 479 480 nw->rightmost_occ = et_new_occ (nw); 481 nw->parent_occ = NULL; 482 483 return nw; 484 } 485 486 /* Releases et tree T. */ 487 488 void 489 et_free_tree (struct et_node *t) 490 { 491 while (t->son) 492 et_split (t->son); 493 494 if (t->father) 495 et_split (t); 496 497 pool_free (et_occurrences, t->rightmost_occ); 498 pool_free (et_nodes, t); 499 } 500 501 /* Releases et tree T without maintaining other nodes. */ 502 503 void 504 et_free_tree_force (struct et_node *t) 505 { 506 pool_free (et_occurrences, t->rightmost_occ); 507 if (t->parent_occ) 508 pool_free (et_occurrences, t->parent_occ); 509 pool_free (et_nodes, t); 510 } 511 512 /* Release the alloc pools, if they are empty. */ 513 514 void 515 et_free_pools (void) 516 { 517 free_alloc_pool_if_empty (&et_occurrences); 518 free_alloc_pool_if_empty (&et_nodes); 519 } 520 521 /* Sets father of et tree T to FATHER. */ 522 523 void 524 et_set_father (struct et_node *t, struct et_node *father) 525 { 526 struct et_node *left, *right; 527 struct et_occ *rmost, *left_part, *new_f_occ, *p; 528 529 /* Update the path represented in the splay tree. */ 530 new_f_occ = et_new_occ (father); 531 532 rmost = father->rightmost_occ; 533 et_splay (rmost); 534 535 left_part = rmost->prev; 536 537 p = t->rightmost_occ; 538 et_splay (p); 539 540 set_prev (new_f_occ, left_part); 541 set_next (new_f_occ, p); 542 543 p->depth++; 544 p->min++; 545 et_recomp_min (new_f_occ); 546 547 set_prev (rmost, new_f_occ); 548 549 if (new_f_occ->min + rmost->depth < rmost->min) 550 { 551 rmost->min = new_f_occ->min + rmost->depth; 552 rmost->min_occ = new_f_occ->min_occ; 553 } 554 555 t->parent_occ = new_f_occ; 556 557 /* Update the tree. */ 558 t->father = father; 559 right = father->son; 560 if (right) 561 left = right->left; 562 else 563 left = right = t; 564 565 left->right = t; 566 right->left = t; 567 t->left = left; 568 t->right = right; 569 570 father->son = t; 571 572 #ifdef DEBUG_ET 573 et_check_tree_sanity (rmost); 574 record_path_before (rmost); 575 #endif 576 } 577 578 /* Splits the edge from T to its father. */ 579 580 void 581 et_split (struct et_node *t) 582 { 583 struct et_node *father = t->father; 584 struct et_occ *r, *l, *rmost, *p_occ; 585 586 /* Update the path represented by the splay tree. */ 587 rmost = t->rightmost_occ; 588 et_splay (rmost); 589 590 for (r = rmost->next; r->prev; r = r->prev) 591 continue; 592 et_splay (r); 593 594 r->prev->parent = NULL; 595 p_occ = t->parent_occ; 596 et_splay (p_occ); 597 t->parent_occ = NULL; 598 599 l = p_occ->prev; 600 p_occ->next->parent = NULL; 601 602 set_prev (r, l); 603 604 et_recomp_min (r); 605 606 et_splay (rmost); 607 rmost->depth = 0; 608 rmost->min = 0; 609 610 pool_free (et_occurrences, p_occ); 611 612 /* Update the tree. */ 613 if (father->son == t) 614 father->son = t->right; 615 if (father->son == t) 616 father->son = NULL; 617 else 618 { 619 t->left->right = t->right; 620 t->right->left = t->left; 621 } 622 t->left = t->right = NULL; 623 t->father = NULL; 624 625 #ifdef DEBUG_ET 626 et_check_tree_sanity (rmost); 627 record_path_before (rmost); 628 629 et_check_tree_sanity (r); 630 record_path_before (r); 631 #endif 632 } 633 634 /* Finds the nearest common ancestor of the nodes N1 and N2. */ 635 636 struct et_node * 637 et_nca (struct et_node *n1, struct et_node *n2) 638 { 639 struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om; 640 struct et_occ *l, *r, *ret; 641 int mn; 642 643 if (n1 == n2) 644 return n1; 645 646 et_splay (o1); 647 l = o1->prev; 648 r = o1->next; 649 if (l) 650 l->parent = NULL; 651 if (r) 652 r->parent = NULL; 653 et_splay (o2); 654 655 if (l == o2 || (l && l->parent != NULL)) 656 { 657 ret = o2->next; 658 659 set_prev (o1, o2); 660 if (r) 661 r->parent = o1; 662 } 663 else if (r == o2 || (r && r->parent != NULL)) 664 { 665 ret = o2->prev; 666 667 set_next (o1, o2); 668 if (l) 669 l->parent = o1; 670 } 671 else 672 { 673 /* O1 and O2 are in different components of the forest. */ 674 if (l) 675 l->parent = o1; 676 if (r) 677 r->parent = o1; 678 return NULL; 679 } 680 681 if (0 < o2->depth) 682 { 683 om = o1; 684 mn = o1->depth; 685 } 686 else 687 { 688 om = o2; 689 mn = o2->depth + o1->depth; 690 } 691 692 #ifdef DEBUG_ET 693 et_check_tree_sanity (o2); 694 #endif 695 696 if (ret && ret->min + o1->depth + o2->depth < mn) 697 return ret->min_occ->of; 698 else 699 return om->of; 700 } 701 702 /* Checks whether the node UP is an ancestor of the node DOWN. */ 703 704 bool 705 et_below (struct et_node *down, struct et_node *up) 706 { 707 struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ; 708 struct et_occ *l, *r; 709 710 if (up == down) 711 return true; 712 713 et_splay (u); 714 l = u->prev; 715 r = u->next; 716 717 if (!l) 718 return false; 719 720 l->parent = NULL; 721 722 if (r) 723 r->parent = NULL; 724 725 et_splay (d); 726 727 if (l == d || l->parent != NULL) 728 { 729 if (r) 730 r->parent = u; 731 set_prev (u, d); 732 #ifdef DEBUG_ET 733 et_check_tree_sanity (u); 734 #endif 735 } 736 else 737 { 738 l->parent = u; 739 740 /* In case O1 and O2 are in two different trees, we must just restore the 741 original state. */ 742 if (r && r->parent != NULL) 743 set_next (u, d); 744 else 745 set_next (u, r); 746 747 #ifdef DEBUG_ET 748 et_check_tree_sanity (u); 749 #endif 750 return false; 751 } 752 753 if (0 >= d->depth) 754 return false; 755 756 return !d->next || d->next->min + d->depth >= 0; 757 } 758 759 /* Returns the root of the tree that contains NODE. */ 760 761 struct et_node * 762 et_root (struct et_node *node) 763 { 764 struct et_occ *occ = node->rightmost_occ, *r; 765 766 /* The root of the tree corresponds to the rightmost occurrence in the 767 represented path. */ 768 et_splay (occ); 769 for (r = occ; r->next; r = r->next) 770 continue; 771 et_splay (r); 772 773 return r->of; 774 } 775