1 /* ET-trees data structure implementation.
2 Contributed by Pavel Nejedly
3 Copyright (C) 2002-2015 Free Software Foundation, Inc.
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.
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.
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/>.
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.
27 #include "coretypes.h"
28 #include "alloc-pool.h"
29 #include "et-forest.h"
31 /* We do not enable this with ENABLE_CHECKING, since it is awfully slow. */
36 #include "hard-reg-set.h"
39 #include "basic-block.h"
42 /* The occurrence of a node in the et tree. */
45 struct et_node *of; /* The node. */
47 struct et_occ *parent; /* Parent in the splay-tree. */
48 struct et_occ *prev; /* Left son in the splay-tree. */
49 struct et_occ *next; /* Right son in the splay-tree. */
51 int depth; /* The depth of the node is the sum of depth
52 fields on the path to the root. */
53 int min; /* The minimum value of the depth in the subtree
54 is obtained by adding sum of depth fields
55 on the path to the root. */
56 struct et_occ *min_occ; /* The occurrence in the subtree with the minimal
59 /* Pool allocation new operator. */
60 inline void *operator new (size_t)
62 return pool.allocate ();
65 /* Delete operator utilizing pool allocation. */
66 inline void operator delete (void *ptr)
68 pool.remove ((et_occ *) ptr);
71 /* Memory allocation pool. */
72 static pool_allocator<et_occ> pool;
76 pool_allocator<et_node> et_node::pool ("et_nodes pool", 300);
77 pool_allocator<et_occ> et_occ::pool ("et_occ pool", 300);
79 /* Changes depth of OCC to D. */
82 set_depth (struct et_occ *occ, int d)
87 occ->min += d - occ->depth;
91 /* Adds D to the depth of OCC. */
94 set_depth_add (struct et_occ *occ, int d)
103 /* Sets prev field of OCC to P. */
106 set_prev (struct et_occ *occ, struct et_occ *t)
109 gcc_assert (occ != t);
117 /* Sets next field of OCC to P. */
120 set_next (struct et_occ *occ, struct et_occ *t)
123 gcc_assert (occ != t);
131 /* Recompute minimum for occurrence OCC. */
134 et_recomp_min (struct et_occ *occ)
136 struct et_occ *mson = occ->prev;
140 && mson->min > occ->next->min))
143 if (mson && mson->min < 0)
145 occ->min = mson->min + occ->depth;
146 occ->min_occ = mson->min_occ;
150 occ->min = occ->depth;
156 /* Checks whether neighborhood of OCC seems sane. */
159 et_check_occ_sanity (struct et_occ *occ)
164 gcc_assert (occ->parent != occ);
165 gcc_assert (occ->prev != occ);
166 gcc_assert (occ->next != occ);
167 gcc_assert (!occ->next || occ->next != occ->prev);
171 gcc_assert (occ->next != occ->parent);
172 gcc_assert (occ->next->parent == occ);
177 gcc_assert (occ->prev != occ->parent);
178 gcc_assert (occ->prev->parent == occ);
181 gcc_assert (!occ->parent
182 || occ->parent->prev == occ
183 || occ->parent->next == occ);
186 /* Checks whether tree rooted at OCC is sane. */
189 et_check_sanity (struct et_occ *occ)
191 et_check_occ_sanity (occ);
193 et_check_sanity (occ->prev);
195 et_check_sanity (occ->next);
198 /* Checks whether tree containing OCC is sane. */
201 et_check_tree_sanity (struct et_occ *occ)
206 et_check_sanity (occ);
209 /* For recording the paths. */
211 /* An ad-hoc constant; if the function has more blocks, this won't work,
212 but since it is used for debugging only, it does not matter. */
213 #define MAX_NODES 100000
216 static void *datas[MAX_NODES];
217 static int depths[MAX_NODES];
219 /* Records the path represented by OCC, with depth incremented by DEPTH. */
222 record_path_before_1 (struct et_occ *occ, int depth)
231 m = record_path_before_1 (occ->prev, depth);
236 fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
238 gcc_assert (len < MAX_NODES);
241 datas[len] = occ->of;
246 m = record_path_before_1 (occ->next, depth);
251 gcc_assert (mn == occ->min + depth - occ->depth);
256 /* Records the path represented by a tree containing OCC. */
259 record_path_before (struct et_occ *occ)
265 record_path_before_1 (occ, 0);
266 fprintf (stderr, "\n");
269 /* Checks whether the path represented by OCC, with depth incremented by DEPTH,
270 was not changed since the last recording. */
273 check_path_after_1 (struct et_occ *occ, int depth)
282 m = check_path_after_1 (occ->next, depth);
288 gcc_assert (depths[len] == depth && datas[len] == occ->of);
292 m = check_path_after_1 (occ->prev, depth);
297 gcc_assert (mn == occ->min + depth - occ->depth);
302 /* Checks whether the path represented by a tree containing OCC was
303 not changed since the last recording. */
306 check_path_after (struct et_occ *occ)
311 check_path_after_1 (occ, 0);
317 /* Splay the occurrence OCC to the root of the tree. */
320 et_splay (struct et_occ *occ)
322 struct et_occ *f, *gf, *ggf;
323 int occ_depth, f_depth, gf_depth;
326 record_path_before (occ);
327 et_check_tree_sanity (occ);
332 occ_depth = occ->depth;
341 set_depth_add (occ, f_depth);
342 occ->min_occ = f->min_occ;
348 set_prev (f, occ->next);
350 set_depth_add (f->prev, occ_depth);
355 set_next (f, occ->prev);
357 set_depth_add (f->next, occ_depth);
359 set_depth (f, -occ_depth);
364 et_check_tree_sanity (occ);
365 check_path_after (occ);
370 gf_depth = gf->depth;
372 set_depth_add (occ, f_depth + gf_depth);
373 occ->min_occ = gf->min_occ;
383 set_prev (gf, f->next);
384 set_prev (f, occ->next);
388 set_depth (f, -occ_depth);
389 set_depth_add (f->prev, occ_depth);
390 set_depth (gf, -f_depth);
391 set_depth_add (gf->prev, f_depth);
396 set_prev (gf, occ->next);
397 set_next (f, occ->prev);
401 set_depth (f, -occ_depth);
402 set_depth_add (f->next, occ_depth);
403 set_depth (gf, -occ_depth - f_depth);
404 set_depth_add (gf->prev, occ_depth + f_depth);
412 set_next (gf, occ->prev);
413 set_prev (f, occ->next);
417 set_depth (f, -occ_depth);
418 set_depth_add (f->prev, occ_depth);
419 set_depth (gf, -occ_depth - f_depth);
420 set_depth_add (gf->next, occ_depth + f_depth);
425 set_next (gf, f->prev);
426 set_next (f, occ->prev);
430 set_depth (f, -occ_depth);
431 set_depth_add (f->next, occ_depth);
432 set_depth (gf, -f_depth);
433 set_depth_add (gf->next, f_depth);
449 et_check_tree_sanity (occ);
454 et_check_sanity (occ);
455 check_path_after (occ);
459 /* Create a new et tree occurrence of NODE. */
461 static struct et_occ *
462 et_new_occ (struct et_node *node)
464 et_occ *nw = new et_occ;
478 /* Create a new et tree containing DATA. */
481 et_new_tree (void *data)
493 nw->rightmost_occ = et_new_occ (nw);
494 nw->parent_occ = NULL;
499 /* Releases et tree T. */
502 et_free_tree (struct et_node *t)
510 delete t->rightmost_occ;
514 /* Releases et tree T without maintaining other nodes. */
517 et_free_tree_force (struct et_node *t)
519 delete t->rightmost_occ;
521 delete t->parent_occ;
525 /* Release the alloc pools, if they are empty. */
530 et_occ::pool.release_if_empty ();
531 et_node::pool.release_if_empty ();
534 /* Sets father of et tree T to FATHER. */
537 et_set_father (struct et_node *t, struct et_node *father)
539 struct et_node *left, *right;
540 struct et_occ *rmost, *left_part, *new_f_occ, *p;
542 /* Update the path represented in the splay tree. */
543 new_f_occ = et_new_occ (father);
545 rmost = father->rightmost_occ;
548 left_part = rmost->prev;
550 p = t->rightmost_occ;
553 set_prev (new_f_occ, left_part);
554 set_next (new_f_occ, p);
558 et_recomp_min (new_f_occ);
560 set_prev (rmost, new_f_occ);
562 if (new_f_occ->min + rmost->depth < rmost->min)
564 rmost->min = new_f_occ->min + rmost->depth;
565 rmost->min_occ = new_f_occ->min_occ;
568 t->parent_occ = new_f_occ;
570 /* Update the tree. */
586 et_check_tree_sanity (rmost);
587 record_path_before (rmost);
591 /* Splits the edge from T to its father. */
594 et_split (struct et_node *t)
596 struct et_node *father = t->father;
597 struct et_occ *r, *l, *rmost, *p_occ;
599 /* Update the path represented by the splay tree. */
600 rmost = t->rightmost_occ;
603 for (r = rmost->next; r->prev; r = r->prev)
607 r->prev->parent = NULL;
608 p_occ = t->parent_occ;
610 t->parent_occ = NULL;
613 p_occ->next->parent = NULL;
625 /* Update the tree. */
626 if (father->son == t)
627 father->son = t->right;
628 if (father->son == t)
632 t->left->right = t->right;
633 t->right->left = t->left;
635 t->left = t->right = NULL;
639 et_check_tree_sanity (rmost);
640 record_path_before (rmost);
642 et_check_tree_sanity (r);
643 record_path_before (r);
647 /* Finds the nearest common ancestor of the nodes N1 and N2. */
650 et_nca (struct et_node *n1, struct et_node *n2)
652 struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
653 struct et_occ *l, *r, *ret;
668 if (l == o2 || (l && l->parent != NULL))
676 else if (r == o2 || (r && r->parent != NULL))
686 /* O1 and O2 are in different components of the forest. */
702 mn = o2->depth + o1->depth;
706 et_check_tree_sanity (o2);
709 if (ret && ret->min + o1->depth + o2->depth < mn)
710 return ret->min_occ->of;
715 /* Checks whether the node UP is an ancestor of the node DOWN. */
718 et_below (struct et_node *down, struct et_node *up)
720 struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
721 struct et_occ *l, *r;
740 if (l == d || l->parent != NULL)
746 et_check_tree_sanity (u);
753 /* In case O1 and O2 are in two different trees, we must just restore the
755 if (r && r->parent != NULL)
761 et_check_tree_sanity (u);
769 return !d->next || d->next->min + d->depth >= 0;
772 /* Returns the root of the tree that contains NODE. */
775 et_root (struct et_node *node)
777 struct et_occ *occ = node->rightmost_occ, *r;
779 /* The root of the tree corresponds to the rightmost occurrence in the
782 for (r = occ; r->next; r = r->next)