et-forest.c revision 132718
1/* ET-trees data structure implementation. 2 Contributed by Pavel Nejedly 3 Copyright (C) 2002, 2003, 2004 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., 59 Temple Place - Suite 330, 19Boston, 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 occurence 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 occurence in the subtree with the minimal 55 depth. */ 56}; 57 58static alloc_pool et_nodes; 59static alloc_pool et_occurences; 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 if (occ == t) 92 abort (); 93#endif 94 95 occ->prev = t; 96 if (t) 97 t->parent = occ; 98} 99 100/* Sets next field of OCC to P. */ 101 102static inline void 103set_next (struct et_occ *occ, struct et_occ *t) 104{ 105#ifdef DEBUG_ET 106 if (occ == t) 107 abort (); 108#endif 109 110 occ->next = t; 111 if (t) 112 t->parent = occ; 113} 114 115/* Recompute minimum for occurence OCC. */ 116 117static inline void 118et_recomp_min (struct et_occ *occ) 119{ 120 struct et_occ *mson = occ->prev; 121 122 if (!mson 123 || (occ->next 124 && mson->min > occ->next->min)) 125 mson = occ->next; 126 127 if (mson && mson->min < 0) 128 { 129 occ->min = mson->min + occ->depth; 130 occ->min_occ = mson->min_occ; 131 } 132 else 133 { 134 occ->min = occ->depth; 135 occ->min_occ = occ; 136 } 137} 138 139#ifdef DEBUG_ET 140/* Checks whether neighbourhood of OCC seems sane. */ 141 142static void 143et_check_occ_sanity (struct et_occ *occ) 144{ 145 if (!occ) 146 return; 147 148 if (occ->parent == occ) 149 abort (); 150 151 if (occ->prev == occ) 152 abort (); 153 154 if (occ->next == occ) 155 abort (); 156 157 if (occ->next && occ->next == occ->prev) 158 abort (); 159 160 if (occ->next) 161 { 162 if (occ->next == occ->parent) 163 abort (); 164 165 if (occ->next->parent != occ) 166 abort (); 167 } 168 169 if (occ->prev) 170 { 171 if (occ->prev == occ->parent) 172 abort (); 173 174 if (occ->prev->parent != occ) 175 abort (); 176 } 177 178 if (occ->parent 179 && occ->parent->prev != occ 180 && occ->parent->next != occ) 181 abort (); 182} 183 184/* Checks whether tree rooted at OCC is sane. */ 185 186static void 187et_check_sanity (struct et_occ *occ) 188{ 189 et_check_occ_sanity (occ); 190 if (occ->prev) 191 et_check_sanity (occ->prev); 192 if (occ->next) 193 et_check_sanity (occ->next); 194} 195 196/* Checks whether tree containing OCC is sane. */ 197 198static void 199et_check_tree_sanity (struct et_occ *occ) 200{ 201 while (occ->parent) 202 occ = occ->parent; 203 204 et_check_sanity (occ); 205} 206 207/* For recording the paths. */ 208 209static int len; 210static void *datas[100000]; 211static int depths[100000]; 212 213/* Records the path represented by OCC, with depth incremented by DEPTH. */ 214 215static int 216record_path_before_1 (struct et_occ *occ, int depth) 217{ 218 int mn, m; 219 220 depth += occ->depth; 221 mn = depth; 222 223 if (occ->prev) 224 { 225 m = record_path_before_1 (occ->prev, depth); 226 if (m < mn) 227 mn = m; 228 } 229 230 fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth); 231 depths[len] = depth; 232 datas[len] = occ->of; 233 len++; 234 235 if (occ->next) 236 { 237 m = record_path_before_1 (occ->next, depth); 238 if (m < mn) 239 mn = m; 240 } 241 242 if (mn != occ->min + depth - occ->depth) 243 abort (); 244 245 return mn; 246} 247 248/* Records the path represented by a tree containing OCC. */ 249 250static void 251record_path_before (struct et_occ *occ) 252{ 253 while (occ->parent) 254 occ = occ->parent; 255 256 len = 0; 257 record_path_before_1 (occ, 0); 258 fprintf (stderr, "\n"); 259} 260 261/* Checks whether the path represented by OCC, with depth incremented by DEPTH, 262 was not changed since the last recording. */ 263 264static int 265check_path_after_1 (struct et_occ *occ, int depth) 266{ 267 int mn, m; 268 269 depth += occ->depth; 270 mn = depth; 271 272 if (occ->next) 273 { 274 m = check_path_after_1 (occ->next, depth); 275 if (m < mn) 276 mn = m; 277 } 278 279 len--; 280 if (depths[len] != depth 281 || datas[len] != occ->of) 282 abort (); 283 284 if (occ->prev) 285 { 286 m = check_path_after_1 (occ->prev, depth); 287 if (m < mn) 288 mn = m; 289 } 290 291 if (mn != occ->min + depth - occ->depth) 292 abort (); 293 294 return mn; 295} 296 297/* Checks whether the path represented by a tree containing OCC was 298 not changed since the last recording. */ 299 300static void 301check_path_after (struct et_occ *occ) 302{ 303 while (occ->parent) 304 occ = occ->parent; 305 306 check_path_after_1 (occ, 0); 307 if (len != 0) 308 abort (); 309} 310 311#endif 312 313/* Splay the occurence OCC to the root of the tree. */ 314 315static void 316et_splay (struct et_occ *occ) 317{ 318 struct et_occ *f, *gf, *ggf; 319 int occ_depth, f_depth, gf_depth; 320 321#ifdef DEBUG_ET 322 record_path_before (occ); 323 et_check_tree_sanity (occ); 324#endif 325 326 while (occ->parent) 327 { 328 occ_depth = occ->depth; 329 330 f = occ->parent; 331 f_depth = f->depth; 332 333 gf = f->parent; 334 335 if (!gf) 336 { 337 set_depth_add (occ, f_depth); 338 occ->min_occ = f->min_occ; 339 occ->min = f->min; 340 341 if (f->prev == occ) 342 { 343 /* zig */ 344 set_prev (f, occ->next); 345 set_next (occ, f); 346 set_depth_add (f->prev, occ_depth); 347 } 348 else 349 { 350 /* zag */ 351 set_next (f, occ->prev); 352 set_prev (occ, f); 353 set_depth_add (f->next, occ_depth); 354 } 355 set_depth (f, -occ_depth); 356 occ->parent = NULL; 357 358 et_recomp_min (f); 359#ifdef DEBUG_ET 360 et_check_tree_sanity (occ); 361 check_path_after (occ); 362#endif 363 return; 364 } 365 366 gf_depth = gf->depth; 367 368 set_depth_add (occ, f_depth + gf_depth); 369 occ->min_occ = gf->min_occ; 370 occ->min = gf->min; 371 372 ggf = gf->parent; 373 374 if (gf->prev == f) 375 { 376 if (f->prev == occ) 377 { 378 /* zig zig */ 379 set_prev (gf, f->next); 380 set_prev (f, occ->next); 381 set_next (occ, f); 382 set_next (f, gf); 383 384 set_depth (f, -occ_depth); 385 set_depth_add (f->prev, occ_depth); 386 set_depth (gf, -f_depth); 387 set_depth_add (gf->prev, f_depth); 388 } 389 else 390 { 391 /* zag zig */ 392 set_prev (gf, occ->next); 393 set_next (f, occ->prev); 394 set_prev (occ, f); 395 set_next (occ, gf); 396 397 set_depth (f, -occ_depth); 398 set_depth_add (f->next, occ_depth); 399 set_depth (gf, -occ_depth - f_depth); 400 set_depth_add (gf->prev, occ_depth + f_depth); 401 } 402 } 403 else 404 { 405 if (f->prev == occ) 406 { 407 /* zig zag */ 408 set_next (gf, occ->prev); 409 set_prev (f, occ->next); 410 set_prev (occ, gf); 411 set_next (occ, f); 412 413 set_depth (f, -occ_depth); 414 set_depth_add (f->prev, occ_depth); 415 set_depth (gf, -occ_depth - f_depth); 416 set_depth_add (gf->next, occ_depth + f_depth); 417 } 418 else 419 { 420 /* zag zag */ 421 set_next (gf, f->prev); 422 set_next (f, occ->prev); 423 set_prev (occ, f); 424 set_prev (f, gf); 425 426 set_depth (f, -occ_depth); 427 set_depth_add (f->next, occ_depth); 428 set_depth (gf, -f_depth); 429 set_depth_add (gf->next, f_depth); 430 } 431 } 432 433 occ->parent = ggf; 434 if (ggf) 435 { 436 if (ggf->prev == gf) 437 ggf->prev = occ; 438 else 439 ggf->next = occ; 440 } 441 442 et_recomp_min (gf); 443 et_recomp_min (f); 444#ifdef DEBUG_ET 445 et_check_tree_sanity (occ); 446#endif 447 } 448 449#ifdef DEBUG_ET 450 et_check_sanity (occ); 451 check_path_after (occ); 452#endif 453} 454 455/* Create a new et tree occurence of NODE. */ 456 457static struct et_occ * 458et_new_occ (struct et_node *node) 459{ 460 struct et_occ *nw; 461 462 if (!et_occurences) 463 et_occurences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300); 464 nw = pool_alloc (et_occurences); 465 466 nw->of = node; 467 nw->parent = NULL; 468 nw->prev = NULL; 469 nw->next = NULL; 470 471 nw->depth = 0; 472 nw->min_occ = nw; 473 nw->min = 0; 474 475 return nw; 476} 477 478/* Create a new et tree containing DATA. */ 479 480struct et_node * 481et_new_tree (void *data) 482{ 483 struct et_node *nw; 484 485 if (!et_nodes) 486 et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300); 487 nw = pool_alloc (et_nodes); 488 489 nw->data = data; 490 nw->father = NULL; 491 nw->left = NULL; 492 nw->right = NULL; 493 nw->son = NULL; 494 495 nw->rightmost_occ = et_new_occ (nw); 496 nw->parent_occ = NULL; 497 498 return nw; 499} 500 501/* Releases et tree T. */ 502 503void 504et_free_tree (struct et_node *t) 505{ 506 while (t->son) 507 et_split (t->son); 508 509 if (t->father) 510 et_split (t); 511 512 pool_free (et_occurences, t->rightmost_occ); 513 pool_free (et_nodes, t); 514} 515 516/* Sets father of et tree T to FATHER. */ 517 518void 519et_set_father (struct et_node *t, struct et_node *father) 520{ 521 struct et_node *left, *right; 522 struct et_occ *rmost, *left_part, *new_f_occ, *p; 523 524 /* Update the path represented in the splay tree. */ 525 new_f_occ = et_new_occ (father); 526 527 rmost = father->rightmost_occ; 528 et_splay (rmost); 529 530 left_part = rmost->prev; 531 532 p = t->rightmost_occ; 533 et_splay (p); 534 535 set_prev (new_f_occ, left_part); 536 set_next (new_f_occ, p); 537 538 p->depth++; 539 p->min++; 540 et_recomp_min (new_f_occ); 541 542 set_prev (rmost, new_f_occ); 543 544 if (new_f_occ->min + rmost->depth < rmost->min) 545 { 546 rmost->min = new_f_occ->min + rmost->depth; 547 rmost->min_occ = new_f_occ->min_occ; 548 } 549 550 t->parent_occ = new_f_occ; 551 552 /* Update the tree. */ 553 t->father = father; 554 right = father->son; 555 if (right) 556 left = right->left; 557 else 558 left = right = t; 559 560 left->right = t; 561 right->left = t; 562 t->left = left; 563 t->right = right; 564 565 father->son = t; 566 567#ifdef DEBUG_ET 568 et_check_tree_sanity (rmost); 569 record_path_before (rmost); 570#endif 571} 572 573/* Splits the edge from T to its father. */ 574 575void 576et_split (struct et_node *t) 577{ 578 struct et_node *father = t->father; 579 struct et_occ *r, *l, *rmost, *p_occ; 580 581 /* Update the path represented by the splay tree. */ 582 rmost = t->rightmost_occ; 583 et_splay (rmost); 584 585 for (r = rmost->next; r->prev; r = r->prev) 586 continue; 587 et_splay (r); 588 589 r->prev->parent = NULL; 590 p_occ = t->parent_occ; 591 et_splay (p_occ); 592 t->parent_occ = NULL; 593 594 l = p_occ->prev; 595 p_occ->next->parent = NULL; 596 597 set_prev (r, l); 598 599 et_recomp_min (r); 600 601 et_splay (rmost); 602 rmost->depth = 0; 603 rmost->min = 0; 604 605 pool_free (et_occurences, p_occ); 606 607 /* Update the tree. */ 608 if (father->son == t) 609 father->son = t->right; 610 if (father->son == t) 611 father->son = NULL; 612 else 613 { 614 t->left->right = t->right; 615 t->right->left = t->left; 616 } 617 t->left = t->right = NULL; 618 t->father = NULL; 619 620#ifdef DEBUG_ET 621 et_check_tree_sanity (rmost); 622 record_path_before (rmost); 623 624 et_check_tree_sanity (r); 625 record_path_before (r); 626#endif 627} 628 629/* Finds the nearest common ancestor of the nodes N1 and N2. */ 630 631struct et_node * 632et_nca (struct et_node *n1, struct et_node *n2) 633{ 634 struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om; 635 struct et_occ *l, *r, *ret; 636 int mn; 637 638 if (n1 == n2) 639 return n1; 640 641 et_splay (o1); 642 l = o1->prev; 643 r = o1->next; 644 if (l) 645 l->parent = NULL; 646 if (r) 647 r->parent = NULL; 648 et_splay (o2); 649 650 if (l == o2 || (l && l->parent != NULL)) 651 { 652 ret = o2->next; 653 654 set_prev (o1, o2); 655 if (r) 656 r->parent = o1; 657 } 658 else 659 { 660 ret = o2->prev; 661 662 set_next (o1, o2); 663 if (l) 664 l->parent = o1; 665 } 666 667 if (0 < o2->depth) 668 { 669 om = o1; 670 mn = o1->depth; 671 } 672 else 673 { 674 om = o2; 675 mn = o2->depth + o1->depth; 676 } 677 678#ifdef DEBUG_ET 679 et_check_tree_sanity (o2); 680#endif 681 682 if (ret && ret->min + o1->depth + o2->depth < mn) 683 return ret->min_occ->of; 684 else 685 return om->of; 686} 687 688/* Checks whether the node UP is an ancestor of the node DOWN. */ 689 690bool 691et_below (struct et_node *down, struct et_node *up) 692{ 693 struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ; 694 struct et_occ *l, *r; 695 696 if (up == down) 697 return true; 698 699 et_splay (u); 700 l = u->prev; 701 r = u->next; 702 703 if (!l) 704 return false; 705 706 l->parent = NULL; 707 708 if (r) 709 r->parent = NULL; 710 711 et_splay (d); 712 713 if (l == d || l->parent != NULL) 714 { 715 if (r) 716 r->parent = u; 717 set_prev (u, d); 718#ifdef DEBUG_ET 719 et_check_tree_sanity (u); 720#endif 721 } 722 else 723 { 724 l->parent = u; 725 726 /* In case O1 and O2 are in two different trees, we must just restore the 727 original state. */ 728 if (r && r->parent != NULL) 729 set_next (u, d); 730 else 731 set_next (u, r); 732 733#ifdef DEBUG_ET 734 et_check_tree_sanity (u); 735#endif 736 return false; 737 } 738 739 if (0 >= d->depth) 740 return false; 741 742 return !d->next || d->next->min + d->depth >= 0; 743} 744