1/* ET-trees data structure implementation. 2 Contributed by Pavel Nejedly 3 Copyright (C) 2002-2015 Free Software Foundation, Inc. 4 5This file is part of the libiberty library. 6Libiberty is free software; you can redistribute it and/or 7modify it under the terms of the GNU Library General Public 8License as published by the Free Software Foundation; either 9version 3 of the License, or (at your option) any later version. 10 11Libiberty is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14Library General Public License for more details. 15 16You should have received a copy of the GNU Library General Public 17License 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. */ 47struct 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 64static alloc_pool et_nodes; 65static alloc_pool et_occurrences; 66 67/* Changes depth of OCC to D. */ 68 69static inline void 70set_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 81static inline void 82set_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 93static inline void 94set_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 107static inline void 108set_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 121static inline void 122et_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 146static void 147et_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 176static void 177et_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 188static void 189et_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 203static int len; 204static void *datas[MAX_NODES]; 205static int depths[MAX_NODES]; 206 207/* Records the path represented by OCC, with depth incremented by DEPTH. */ 208 209static int 210record_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 246static void 247record_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 260static int 261check_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 293static void 294check_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 307static void 308et_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 449static struct et_occ * 450et_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 472struct et_node * 473et_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 495void 496et_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 510void 511et_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 521void 522et_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 530void 531et_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 587void 588et_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 643struct et_node * 644et_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 711bool 712et_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 768struct et_node * 769et_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} 782