1 /* ET-trees data structure implementation.
2 Contributed by Pavel Nejedly
3 Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2010 Free Software
6 This file is part of the libiberty library.
7 Libiberty is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Library General Public
9 License as published by the Free Software Foundation; either
10 version 3 of the License, or (at your option) any later version.
12 Libiberty is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Library General Public License for more details.
17 You should have received a copy of the GNU Library General Public
18 License along with libiberty; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>.
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.
28 #include "coretypes.h"
29 #include "et-forest.h"
30 #include "alloc-pool.h"
32 /* We do not enable this with ENABLE_CHECKING, since it is awfully slow. */
36 #include "basic-block.h"
39 /* The occurrence of a node in the et tree. */
42 struct et_node *of; /* The node. */
44 struct et_occ *parent; /* Parent in the splay-tree. */
45 struct et_occ *prev; /* Left son in the splay-tree. */
46 struct et_occ *next; /* Right son in the splay-tree. */
48 int depth; /* The depth of the node is the sum of depth
49 fields on the path to the root. */
50 int min; /* The minimum value of the depth in the subtree
51 is obtained by adding sum of depth fields
52 on the path to the root. */
53 struct et_occ *min_occ; /* The occurrence in the subtree with the minimal
57 static alloc_pool et_nodes;
58 static alloc_pool et_occurrences;
60 /* Changes depth of OCC to D. */
63 set_depth (struct et_occ *occ, int d)
68 occ->min += d - occ->depth;
72 /* Adds D to the depth of OCC. */
75 set_depth_add (struct et_occ *occ, int d)
84 /* Sets prev field of OCC to P. */
87 set_prev (struct et_occ *occ, struct et_occ *t)
90 gcc_assert (occ != t);
98 /* Sets next field of OCC to P. */
101 set_next (struct et_occ *occ, struct et_occ *t)
104 gcc_assert (occ != t);
112 /* Recompute minimum for occurrence OCC. */
115 et_recomp_min (struct et_occ *occ)
117 struct et_occ *mson = occ->prev;
121 && mson->min > occ->next->min))
124 if (mson && mson->min < 0)
126 occ->min = mson->min + occ->depth;
127 occ->min_occ = mson->min_occ;
131 occ->min = occ->depth;
137 /* Checks whether neighborhood of OCC seems sane. */
140 et_check_occ_sanity (struct et_occ *occ)
145 gcc_assert (occ->parent != occ);
146 gcc_assert (occ->prev != occ);
147 gcc_assert (occ->next != occ);
148 gcc_assert (!occ->next || occ->next != occ->prev);
152 gcc_assert (occ->next != occ->parent);
153 gcc_assert (occ->next->parent == occ);
158 gcc_assert (occ->prev != occ->parent);
159 gcc_assert (occ->prev->parent == occ);
162 gcc_assert (!occ->parent
163 || occ->parent->prev == occ
164 || occ->parent->next == occ);
167 /* Checks whether tree rooted at OCC is sane. */
170 et_check_sanity (struct et_occ *occ)
172 et_check_occ_sanity (occ);
174 et_check_sanity (occ->prev);
176 et_check_sanity (occ->next);
179 /* Checks whether tree containing OCC is sane. */
182 et_check_tree_sanity (struct et_occ *occ)
187 et_check_sanity (occ);
190 /* For recording the paths. */
192 /* An ad-hoc constant; if the function has more blocks, this won't work,
193 but since it is used for debugging only, it does not matter. */
194 #define MAX_NODES 100000
197 static void *datas[MAX_NODES];
198 static int depths[MAX_NODES];
200 /* Records the path represented by OCC, with depth incremented by DEPTH. */
203 record_path_before_1 (struct et_occ *occ, int depth)
212 m = record_path_before_1 (occ->prev, depth);
217 fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
219 gcc_assert (len < MAX_NODES);
222 datas[len] = occ->of;
227 m = record_path_before_1 (occ->next, depth);
232 gcc_assert (mn == occ->min + depth - occ->depth);
237 /* Records the path represented by a tree containing OCC. */
240 record_path_before (struct et_occ *occ)
246 record_path_before_1 (occ, 0);
247 fprintf (stderr, "\n");
250 /* Checks whether the path represented by OCC, with depth incremented by DEPTH,
251 was not changed since the last recording. */
254 check_path_after_1 (struct et_occ *occ, int depth)
263 m = check_path_after_1 (occ->next, depth);
269 gcc_assert (depths[len] == depth && datas[len] == occ->of);
273 m = check_path_after_1 (occ->prev, depth);
278 gcc_assert (mn == occ->min + depth - occ->depth);
283 /* Checks whether the path represented by a tree containing OCC was
284 not changed since the last recording. */
287 check_path_after (struct et_occ *occ)
292 check_path_after_1 (occ, 0);
298 /* Splay the occurrence OCC to the root of the tree. */
301 et_splay (struct et_occ *occ)
303 struct et_occ *f, *gf, *ggf;
304 int occ_depth, f_depth, gf_depth;
307 record_path_before (occ);
308 et_check_tree_sanity (occ);
313 occ_depth = occ->depth;
322 set_depth_add (occ, f_depth);
323 occ->min_occ = f->min_occ;
329 set_prev (f, occ->next);
331 set_depth_add (f->prev, occ_depth);
336 set_next (f, occ->prev);
338 set_depth_add (f->next, occ_depth);
340 set_depth (f, -occ_depth);
345 et_check_tree_sanity (occ);
346 check_path_after (occ);
351 gf_depth = gf->depth;
353 set_depth_add (occ, f_depth + gf_depth);
354 occ->min_occ = gf->min_occ;
364 set_prev (gf, f->next);
365 set_prev (f, occ->next);
369 set_depth (f, -occ_depth);
370 set_depth_add (f->prev, occ_depth);
371 set_depth (gf, -f_depth);
372 set_depth_add (gf->prev, f_depth);
377 set_prev (gf, occ->next);
378 set_next (f, occ->prev);
382 set_depth (f, -occ_depth);
383 set_depth_add (f->next, occ_depth);
384 set_depth (gf, -occ_depth - f_depth);
385 set_depth_add (gf->prev, occ_depth + f_depth);
393 set_next (gf, occ->prev);
394 set_prev (f, occ->next);
398 set_depth (f, -occ_depth);
399 set_depth_add (f->prev, occ_depth);
400 set_depth (gf, -occ_depth - f_depth);
401 set_depth_add (gf->next, occ_depth + f_depth);
406 set_next (gf, f->prev);
407 set_next (f, occ->prev);
411 set_depth (f, -occ_depth);
412 set_depth_add (f->next, occ_depth);
413 set_depth (gf, -f_depth);
414 set_depth_add (gf->next, f_depth);
430 et_check_tree_sanity (occ);
435 et_check_sanity (occ);
436 check_path_after (occ);
440 /* Create a new et tree occurrence of NODE. */
442 static struct et_occ *
443 et_new_occ (struct et_node *node)
448 et_occurrences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);
449 nw = (struct et_occ *) pool_alloc (et_occurrences);
463 /* Create a new et tree containing DATA. */
466 et_new_tree (void *data)
471 et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);
472 nw = (struct et_node *) pool_alloc (et_nodes);
480 nw->rightmost_occ = et_new_occ (nw);
481 nw->parent_occ = NULL;
486 /* Releases et tree T. */
489 et_free_tree (struct et_node *t)
497 pool_free (et_occurrences, t->rightmost_occ);
498 pool_free (et_nodes, t);
501 /* Releases et tree T without maintaining other nodes. */
504 et_free_tree_force (struct et_node *t)
506 pool_free (et_occurrences, t->rightmost_occ);
508 pool_free (et_occurrences, t->parent_occ);
509 pool_free (et_nodes, t);
512 /* Release the alloc pools, if they are empty. */
517 free_alloc_pool_if_empty (&et_occurrences);
518 free_alloc_pool_if_empty (&et_nodes);
521 /* Sets father of et tree T to FATHER. */
524 et_set_father (struct et_node *t, struct et_node *father)
526 struct et_node *left, *right;
527 struct et_occ *rmost, *left_part, *new_f_occ, *p;
529 /* Update the path represented in the splay tree. */
530 new_f_occ = et_new_occ (father);
532 rmost = father->rightmost_occ;
535 left_part = rmost->prev;
537 p = t->rightmost_occ;
540 set_prev (new_f_occ, left_part);
541 set_next (new_f_occ, p);
545 et_recomp_min (new_f_occ);
547 set_prev (rmost, new_f_occ);
549 if (new_f_occ->min + rmost->depth < rmost->min)
551 rmost->min = new_f_occ->min + rmost->depth;
552 rmost->min_occ = new_f_occ->min_occ;
555 t->parent_occ = new_f_occ;
557 /* Update the tree. */
573 et_check_tree_sanity (rmost);
574 record_path_before (rmost);
578 /* Splits the edge from T to its father. */
581 et_split (struct et_node *t)
583 struct et_node *father = t->father;
584 struct et_occ *r, *l, *rmost, *p_occ;
586 /* Update the path represented by the splay tree. */
587 rmost = t->rightmost_occ;
590 for (r = rmost->next; r->prev; r = r->prev)
594 r->prev->parent = NULL;
595 p_occ = t->parent_occ;
597 t->parent_occ = NULL;
600 p_occ->next->parent = NULL;
610 pool_free (et_occurrences, p_occ);
612 /* Update the tree. */
613 if (father->son == t)
614 father->son = t->right;
615 if (father->son == t)
619 t->left->right = t->right;
620 t->right->left = t->left;
622 t->left = t->right = NULL;
626 et_check_tree_sanity (rmost);
627 record_path_before (rmost);
629 et_check_tree_sanity (r);
630 record_path_before (r);
634 /* Finds the nearest common ancestor of the nodes N1 and N2. */
637 et_nca (struct et_node *n1, struct et_node *n2)
639 struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
640 struct et_occ *l, *r, *ret;
655 if (l == o2 || (l && l->parent != NULL))
663 else if (r == o2 || (r && r->parent != NULL))
673 /* O1 and O2 are in different components of the forest. */
689 mn = o2->depth + o1->depth;
693 et_check_tree_sanity (o2);
696 if (ret && ret->min + o1->depth + o2->depth < mn)
697 return ret->min_occ->of;
702 /* Checks whether the node UP is an ancestor of the node DOWN. */
705 et_below (struct et_node *down, struct et_node *up)
707 struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
708 struct et_occ *l, *r;
727 if (l == d || l->parent != NULL)
733 et_check_tree_sanity (u);
740 /* In case O1 and O2 are in two different trees, we must just restore the
742 if (r && r->parent != NULL)
748 et_check_tree_sanity (u);
756 return !d->next || d->next->min + d->depth >= 0;
759 /* Returns the root of the tree that contains NODE. */
762 et_root (struct et_node *node)
764 struct et_occ *occ = node->rightmost_occ, *r;
766 /* The root of the tree corresponds to the rightmost occurrence in the
769 for (r = occ; r->next; r = r->next)