1/* ET-trees data structure implementation. 2 Contributed by Pavel Nejedly 3 Copyright (C) 2002, 2003, 2004, 2005 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 2 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 COPYING.LIB. If 18not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 19Boston, 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. */ 41struct 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 58static alloc_pool et_nodes; 59static alloc_pool et_occurrences; 60 61/* Changes depth of OCC to D. */ 62 63static inline void 64set_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 75static inline void 76set_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 87static inline void 88set_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 101static inline void 102set_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 115static inline void 116et_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 140static void 141et_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 170static void 171et_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 182static void 183et_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 197static int len; 198static void *datas[MAX_NODES]; 199static int depths[MAX_NODES]; 200 201/* Records the path represented by OCC, with depth incremented by DEPTH. */ 202 203static int 204record_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 240static void 241record_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 254static int 255check_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 287static void 288check_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 301static void 302et_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 443static struct et_occ * 444et_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 466struct et_node * 467et_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 489void 490et_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 504void 505et_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 513void 514et_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 570void 571et_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 626struct et_node * 627et_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 685bool 686et_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} 739