1 /* ET-trees data structure implementation. 2 Contributed by Pavel Nejedly 3 Copyright (C) 2002-2018 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 #include "selftest.h" 31 32 /* We do not enable this with CHECKING_P, since it is awfully slow. */ 33 #undef DEBUG_ET 34 35 #ifdef DEBUG_ET 36 #include "backend.h" 37 #include "hard-reg-set.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 object_allocator<et_node> et_nodes ("et_nodes pool"); 59 static object_allocator<et_occ> et_occurrences ("et_occ pool"); 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 et_occ *nw = et_occurrences.allocate (); 447 448 nw->of = node; 449 nw->parent = NULL; 450 nw->prev = NULL; 451 nw->next = NULL; 452 453 nw->depth = 0; 454 nw->min_occ = nw; 455 nw->min = 0; 456 457 return nw; 458 } 459 460 /* Create a new et tree containing DATA. */ 461 462 struct et_node * 463 et_new_tree (void *data) 464 { 465 et_node *nw = et_nodes.allocate (); 466 467 nw->data = data; 468 nw->father = NULL; 469 nw->left = NULL; 470 nw->right = NULL; 471 nw->son = NULL; 472 473 nw->rightmost_occ = et_new_occ (nw); 474 nw->parent_occ = NULL; 475 476 return nw; 477 } 478 479 /* Releases et tree T. */ 480 481 void 482 et_free_tree (struct et_node *t) 483 { 484 while (t->son) 485 et_split (t->son); 486 487 if (t->father) 488 et_split (t); 489 490 et_occurrences.remove (t->rightmost_occ); 491 et_nodes.remove (t); 492 } 493 494 /* Releases et tree T without maintaining other nodes. */ 495 496 void 497 et_free_tree_force (struct et_node *t) 498 { 499 et_occurrences.remove (t->rightmost_occ); 500 if (t->parent_occ) 501 et_occurrences.remove (t->parent_occ); 502 et_nodes.remove (t); 503 } 504 505 /* Release the alloc pools, if they are empty. */ 506 507 void 508 et_free_pools (void) 509 { 510 et_occurrences.release_if_empty (); 511 et_nodes.release_if_empty (); 512 } 513 514 /* Sets father of et tree T to FATHER. */ 515 516 void 517 et_set_father (struct et_node *t, struct et_node *father) 518 { 519 struct et_node *left, *right; 520 struct et_occ *rmost, *left_part, *new_f_occ, *p; 521 522 /* Update the path represented in the splay tree. */ 523 new_f_occ = et_new_occ (father); 524 525 rmost = father->rightmost_occ; 526 et_splay (rmost); 527 528 left_part = rmost->prev; 529 530 p = t->rightmost_occ; 531 et_splay (p); 532 533 set_prev (new_f_occ, left_part); 534 set_next (new_f_occ, p); 535 536 p->depth++; 537 p->min++; 538 et_recomp_min (new_f_occ); 539 540 set_prev (rmost, new_f_occ); 541 542 if (new_f_occ->min + rmost->depth < rmost->min) 543 { 544 rmost->min = new_f_occ->min + rmost->depth; 545 rmost->min_occ = new_f_occ->min_occ; 546 } 547 548 t->parent_occ = new_f_occ; 549 550 /* Update the tree. */ 551 t->father = father; 552 right = father->son; 553 if (right) 554 left = right->left; 555 else 556 left = right = t; 557 558 left->right = t; 559 right->left = t; 560 t->left = left; 561 t->right = right; 562 563 father->son = t; 564 565 #ifdef DEBUG_ET 566 et_check_tree_sanity (rmost); 567 record_path_before (rmost); 568 #endif 569 } 570 571 /* Splits the edge from T to its father. */ 572 573 void 574 et_split (struct et_node *t) 575 { 576 struct et_node *father = t->father; 577 struct et_occ *r, *l, *rmost, *p_occ; 578 579 /* Update the path represented by the splay tree. */ 580 rmost = t->rightmost_occ; 581 et_splay (rmost); 582 583 for (r = rmost->next; r->prev; r = r->prev) 584 continue; 585 et_splay (r); 586 587 r->prev->parent = NULL; 588 p_occ = t->parent_occ; 589 et_splay (p_occ); 590 t->parent_occ = NULL; 591 592 l = p_occ->prev; 593 p_occ->next->parent = NULL; 594 595 set_prev (r, l); 596 597 et_recomp_min (r); 598 599 et_splay (rmost); 600 rmost->depth = 0; 601 rmost->min = 0; 602 603 et_occurrences.remove (p_occ); 604 605 /* Update the tree. */ 606 if (father->son == t) 607 father->son = t->right; 608 if (father->son == t) 609 father->son = NULL; 610 else 611 { 612 t->left->right = t->right; 613 t->right->left = t->left; 614 } 615 t->left = t->right = NULL; 616 t->father = NULL; 617 618 #ifdef DEBUG_ET 619 et_check_tree_sanity (rmost); 620 record_path_before (rmost); 621 622 et_check_tree_sanity (r); 623 record_path_before (r); 624 #endif 625 } 626 627 /* Finds the nearest common ancestor of the nodes N1 and N2. */ 628 629 struct et_node * 630 et_nca (struct et_node *n1, struct et_node *n2) 631 { 632 struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om; 633 struct et_occ *l, *r, *ret; 634 int mn; 635 636 if (n1 == n2) 637 return n1; 638 639 et_splay (o1); 640 l = o1->prev; 641 r = o1->next; 642 if (l) 643 l->parent = NULL; 644 if (r) 645 r->parent = NULL; 646 et_splay (o2); 647 648 if (l == o2 || (l && l->parent != NULL)) 649 { 650 ret = o2->next; 651 652 set_prev (o1, o2); 653 if (r) 654 r->parent = o1; 655 } 656 else if (r == o2 || (r && r->parent != NULL)) 657 { 658 ret = o2->prev; 659 660 set_next (o1, o2); 661 if (l) 662 l->parent = o1; 663 } 664 else 665 { 666 /* O1 and O2 are in different components of the forest. */ 667 if (l) 668 l->parent = o1; 669 if (r) 670 r->parent = o1; 671 return NULL; 672 } 673 674 if (o2->depth > 0) 675 { 676 om = o1; 677 mn = o1->depth; 678 } 679 else 680 { 681 om = o2; 682 mn = o2->depth + o1->depth; 683 } 684 685 #ifdef DEBUG_ET 686 et_check_tree_sanity (o2); 687 #endif 688 689 if (ret && ret->min + o1->depth + o2->depth < mn) 690 return ret->min_occ->of; 691 else 692 return om->of; 693 } 694 695 /* Checks whether the node UP is an ancestor of the node DOWN. */ 696 697 bool 698 et_below (struct et_node *down, struct et_node *up) 699 { 700 struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ; 701 struct et_occ *l, *r; 702 703 if (up == down) 704 return true; 705 706 et_splay (u); 707 l = u->prev; 708 r = u->next; 709 710 if (!l) 711 return false; 712 713 l->parent = NULL; 714 715 if (r) 716 r->parent = NULL; 717 718 et_splay (d); 719 720 if (l == d || l->parent != NULL) 721 { 722 if (r) 723 r->parent = u; 724 set_prev (u, d); 725 #ifdef DEBUG_ET 726 et_check_tree_sanity (u); 727 #endif 728 } 729 else 730 { 731 l->parent = u; 732 733 /* In case O1 and O2 are in two different trees, we must just restore the 734 original state. */ 735 if (r && r->parent != NULL) 736 set_next (u, d); 737 else 738 set_next (u, r); 739 740 #ifdef DEBUG_ET 741 et_check_tree_sanity (u); 742 #endif 743 return false; 744 } 745 746 if (d->depth <= 0) 747 return false; 748 749 return !d->next || d->next->min + d->depth >= 0; 750 } 751 752 /* Returns the root of the tree that contains NODE. */ 753 754 struct et_node * 755 et_root (struct et_node *node) 756 { 757 struct et_occ *occ = node->rightmost_occ, *r; 758 759 /* The root of the tree corresponds to the rightmost occurrence in the 760 represented path. */ 761 et_splay (occ); 762 for (r = occ; r->next; r = r->next) 763 continue; 764 et_splay (r); 765 766 return r->of; 767 } 768 769 #if CHECKING_P 770 771 namespace selftest { 772 773 /* Selftests for et-forest.c. */ 774 775 /* Perform sanity checks for a tree consisting of a single node. */ 776 777 static void 778 test_single_node () 779 { 780 void *test_data = (void *)0xcafebabe; 781 782 et_node *n = et_new_tree (test_data); 783 ASSERT_EQ (n->data, test_data); 784 ASSERT_EQ (n, et_root (n)); 785 et_free_tree (n); 786 } 787 788 /* Test of this tree: 789 a 790 / \ 791 / \ 792 b c 793 / \ | 794 d e f. */ 795 796 static void 797 test_simple_tree () 798 { 799 et_node *a = et_new_tree (NULL); 800 et_node *b = et_new_tree (NULL); 801 et_node *c = et_new_tree (NULL); 802 et_node *d = et_new_tree (NULL); 803 et_node *e = et_new_tree (NULL); 804 et_node *f = et_new_tree (NULL); 805 806 et_set_father (b, a); 807 et_set_father (c, a); 808 et_set_father (d, b); 809 et_set_father (e, b); 810 et_set_father (f, c); 811 812 ASSERT_TRUE (et_below (a, a)); 813 ASSERT_TRUE (et_below (b, a)); 814 ASSERT_TRUE (et_below (c, a)); 815 ASSERT_TRUE (et_below (d, a)); 816 ASSERT_TRUE (et_below (e, a)); 817 ASSERT_TRUE (et_below (f, a)); 818 819 ASSERT_FALSE (et_below (a, b)); 820 ASSERT_TRUE (et_below (b, b)); 821 ASSERT_FALSE (et_below (c, b)); 822 ASSERT_TRUE (et_below (d, b)); 823 ASSERT_TRUE (et_below (e, b)); 824 ASSERT_FALSE (et_below (f, b)); 825 826 ASSERT_FALSE (et_below (a, c)); 827 ASSERT_FALSE (et_below (b, c)); 828 ASSERT_TRUE (et_below (c, c)); 829 ASSERT_FALSE (et_below (d, c)); 830 ASSERT_FALSE (et_below (e, c)); 831 ASSERT_TRUE (et_below (f, c)); 832 833 ASSERT_FALSE (et_below (a, d)); 834 ASSERT_FALSE (et_below (b, d)); 835 ASSERT_FALSE (et_below (c, d)); 836 ASSERT_TRUE (et_below (d, d)); 837 ASSERT_FALSE (et_below (e, d)); 838 ASSERT_FALSE (et_below (f, d)); 839 840 ASSERT_FALSE (et_below (a, e)); 841 ASSERT_FALSE (et_below (b, e)); 842 ASSERT_FALSE (et_below (c, e)); 843 ASSERT_FALSE (et_below (d, e)); 844 ASSERT_TRUE (et_below (e, e)); 845 ASSERT_FALSE (et_below (f, e)); 846 847 ASSERT_FALSE (et_below (a, f)); 848 ASSERT_FALSE (et_below (b, f)); 849 ASSERT_FALSE (et_below (c, f)); 850 ASSERT_FALSE (et_below (d, f)); 851 ASSERT_FALSE (et_below (e, f)); 852 ASSERT_TRUE (et_below (f, f)); 853 854 et_free_tree_force (a); 855 } 856 857 /* Verify that two disconnected nodes are unrelated. */ 858 859 static void 860 test_disconnected_nodes () 861 { 862 et_node *a = et_new_tree (NULL); 863 et_node *b = et_new_tree (NULL); 864 865 ASSERT_FALSE (et_below (a, b)); 866 ASSERT_FALSE (et_below (b, a)); 867 868 et_free_tree (a); 869 et_free_tree (b); 870 } 871 872 /* Run all of the selftests within this file. */ 873 874 void 875 et_forest_c_tests () 876 { 877 test_single_node (); 878 test_simple_tree (); 879 test_disconnected_nodes (); 880 } 881 882 } // namespace selftest 883 884 #endif /* CHECKING_P */ 885