1 /* ET-trees data structure implementation.
2 Contributed by Pavel Nejedly
3 Copyright (C) 2002-2018 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"
32 /* We do not enable this with CHECKING_P, since it is awfully slow. */
37 #include "hard-reg-set.h"
40 /* The occurrence of a node in the et tree. */
43 struct et_node *of; /* The node. */
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. */
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
58 static object_allocator<et_node> et_nodes ("et_nodes pool");
59 static object_allocator<et_occ> et_occurrences ("et_occ pool");
61 /* Changes depth of OCC to D. */
64 set_depth (struct et_occ *occ, int d)
69 occ->min += d - occ->depth;
73 /* Adds D to the depth of OCC. */
76 set_depth_add (struct et_occ *occ, int d)
85 /* Sets prev field of OCC to P. */
88 set_prev (struct et_occ *occ, struct et_occ *t)
91 gcc_assert (occ != t);
99 /* Sets next field of OCC to P. */
102 set_next (struct et_occ *occ, struct et_occ *t)
105 gcc_assert (occ != t);
113 /* Recompute minimum for occurrence OCC. */
116 et_recomp_min (struct et_occ *occ)
118 struct et_occ *mson = occ->prev;
122 && mson->min > occ->next->min))
125 if (mson && mson->min < 0)
127 occ->min = mson->min + occ->depth;
128 occ->min_occ = mson->min_occ;
132 occ->min = occ->depth;
138 /* Checks whether neighborhood of OCC seems sane. */
141 et_check_occ_sanity (struct et_occ *occ)
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);
153 gcc_assert (occ->next != occ->parent);
154 gcc_assert (occ->next->parent == occ);
159 gcc_assert (occ->prev != occ->parent);
160 gcc_assert (occ->prev->parent == occ);
163 gcc_assert (!occ->parent
164 || occ->parent->prev == occ
165 || occ->parent->next == occ);
168 /* Checks whether tree rooted at OCC is sane. */
171 et_check_sanity (struct et_occ *occ)
173 et_check_occ_sanity (occ);
175 et_check_sanity (occ->prev);
177 et_check_sanity (occ->next);
180 /* Checks whether tree containing OCC is sane. */
183 et_check_tree_sanity (struct et_occ *occ)
188 et_check_sanity (occ);
191 /* For recording the paths. */
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
198 static void *datas[MAX_NODES];
199 static int depths[MAX_NODES];
201 /* Records the path represented by OCC, with depth incremented by DEPTH. */
204 record_path_before_1 (struct et_occ *occ, int depth)
213 m = record_path_before_1 (occ->prev, depth);
218 fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
220 gcc_assert (len < MAX_NODES);
223 datas[len] = occ->of;
228 m = record_path_before_1 (occ->next, depth);
233 gcc_assert (mn == occ->min + depth - occ->depth);
238 /* Records the path represented by a tree containing OCC. */
241 record_path_before (struct et_occ *occ)
247 record_path_before_1 (occ, 0);
248 fprintf (stderr, "\n");
251 /* Checks whether the path represented by OCC, with depth incremented by DEPTH,
252 was not changed since the last recording. */
255 check_path_after_1 (struct et_occ *occ, int depth)
264 m = check_path_after_1 (occ->next, depth);
270 gcc_assert (depths[len] == depth && datas[len] == occ->of);
274 m = check_path_after_1 (occ->prev, depth);
279 gcc_assert (mn == occ->min + depth - occ->depth);
284 /* Checks whether the path represented by a tree containing OCC was
285 not changed since the last recording. */
288 check_path_after (struct et_occ *occ)
293 check_path_after_1 (occ, 0);
299 /* Splay the occurrence OCC to the root of the tree. */
302 et_splay (struct et_occ *occ)
304 struct et_occ *f, *gf, *ggf;
305 int occ_depth, f_depth, gf_depth;
308 record_path_before (occ);
309 et_check_tree_sanity (occ);
314 occ_depth = occ->depth;
323 set_depth_add (occ, f_depth);
324 occ->min_occ = f->min_occ;
330 set_prev (f, occ->next);
332 set_depth_add (f->prev, occ_depth);
337 set_next (f, occ->prev);
339 set_depth_add (f->next, occ_depth);
341 set_depth (f, -occ_depth);
346 et_check_tree_sanity (occ);
347 check_path_after (occ);
352 gf_depth = gf->depth;
354 set_depth_add (occ, f_depth + gf_depth);
355 occ->min_occ = gf->min_occ;
365 set_prev (gf, f->next);
366 set_prev (f, occ->next);
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);
378 set_prev (gf, occ->next);
379 set_next (f, occ->prev);
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);
394 set_next (gf, occ->prev);
395 set_prev (f, occ->next);
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);
407 set_next (gf, f->prev);
408 set_next (f, occ->prev);
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);
431 et_check_tree_sanity (occ);
436 et_check_sanity (occ);
437 check_path_after (occ);
441 /* Create a new et tree occurrence of NODE. */
443 static struct et_occ *
444 et_new_occ (struct et_node *node)
446 et_occ *nw = et_occurrences.allocate ();
460 /* Create a new et tree containing DATA. */
463 et_new_tree (void *data)
465 et_node *nw = et_nodes.allocate ();
473 nw->rightmost_occ = et_new_occ (nw);
474 nw->parent_occ = NULL;
479 /* Releases et tree T. */
482 et_free_tree (struct et_node *t)
490 et_occurrences.remove (t->rightmost_occ);
494 /* Releases et tree T without maintaining other nodes. */
497 et_free_tree_force (struct et_node *t)
499 et_occurrences.remove (t->rightmost_occ);
501 et_occurrences.remove (t->parent_occ);
505 /* Release the alloc pools, if they are empty. */
510 et_occurrences.release_if_empty ();
511 et_nodes.release_if_empty ();
514 /* Sets father of et tree T to FATHER. */
517 et_set_father (struct et_node *t, struct et_node *father)
519 struct et_node *left, *right;
520 struct et_occ *rmost, *left_part, *new_f_occ, *p;
522 /* Update the path represented in the splay tree. */
523 new_f_occ = et_new_occ (father);
525 rmost = father->rightmost_occ;
528 left_part = rmost->prev;
530 p = t->rightmost_occ;
533 set_prev (new_f_occ, left_part);
534 set_next (new_f_occ, p);
538 et_recomp_min (new_f_occ);
540 set_prev (rmost, new_f_occ);
542 if (new_f_occ->min + rmost->depth < rmost->min)
544 rmost->min = new_f_occ->min + rmost->depth;
545 rmost->min_occ = new_f_occ->min_occ;
548 t->parent_occ = new_f_occ;
550 /* Update the tree. */
566 et_check_tree_sanity (rmost);
567 record_path_before (rmost);
571 /* Splits the edge from T to its father. */
574 et_split (struct et_node *t)
576 struct et_node *father = t->father;
577 struct et_occ *r, *l, *rmost, *p_occ;
579 /* Update the path represented by the splay tree. */
580 rmost = t->rightmost_occ;
583 for (r = rmost->next; r->prev; r = r->prev)
587 r->prev->parent = NULL;
588 p_occ = t->parent_occ;
590 t->parent_occ = NULL;
593 p_occ->next->parent = NULL;
603 et_occurrences.remove (p_occ);
605 /* Update the tree. */
606 if (father->son == t)
607 father->son = t->right;
608 if (father->son == t)
612 t->left->right = t->right;
613 t->right->left = t->left;
615 t->left = t->right = NULL;
619 et_check_tree_sanity (rmost);
620 record_path_before (rmost);
622 et_check_tree_sanity (r);
623 record_path_before (r);
627 /* Finds the nearest common ancestor of the nodes N1 and N2. */
630 et_nca (struct et_node *n1, struct et_node *n2)
632 struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
633 struct et_occ *l, *r, *ret;
648 if (l == o2 || (l && l->parent != NULL))
656 else if (r == o2 || (r && r->parent != NULL))
666 /* O1 and O2 are in different components of the forest. */
682 mn = o2->depth + o1->depth;
686 et_check_tree_sanity (o2);
689 if (ret && ret->min + o1->depth + o2->depth < mn)
690 return ret->min_occ->of;
695 /* Checks whether the node UP is an ancestor of the node DOWN. */
698 et_below (struct et_node *down, struct et_node *up)
700 struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
701 struct et_occ *l, *r;
720 if (l == d || l->parent != NULL)
726 et_check_tree_sanity (u);
733 /* In case O1 and O2 are in two different trees, we must just restore the
735 if (r && r->parent != NULL)
741 et_check_tree_sanity (u);
749 return !d->next || d->next->min + d->depth >= 0;
752 /* Returns the root of the tree that contains NODE. */
755 et_root (struct et_node *node)
757 struct et_occ *occ = node->rightmost_occ, *r;
759 /* The root of the tree corresponds to the rightmost occurrence in the
762 for (r = occ; r->next; r = r->next)
773 /* Selftests for et-forest.c. */
775 /* Perform sanity checks for a tree consisting of a single node. */
780 void *test_data = (void *)0xcafebabe;
782 et_node *n = et_new_tree (test_data);
783 ASSERT_EQ (n->data, test_data);
784 ASSERT_EQ (n, et_root (n));
788 /* Test of this tree:
799 et_node *a = et_new_tree (NULL);
800 et_node *b = et_new_tree (NULL);
801 et_node *c = et_new_tree (NULL);
802 et_node *d = et_new_tree (NULL);
803 et_node *e = et_new_tree (NULL);
804 et_node *f = et_new_tree (NULL);
806 et_set_father (b, a);
807 et_set_father (c, a);
808 et_set_father (d, b);
809 et_set_father (e, b);
810 et_set_father (f, c);
812 ASSERT_TRUE (et_below (a, a));
813 ASSERT_TRUE (et_below (b, a));
814 ASSERT_TRUE (et_below (c, a));
815 ASSERT_TRUE (et_below (d, a));
816 ASSERT_TRUE (et_below (e, a));
817 ASSERT_TRUE (et_below (f, a));
819 ASSERT_FALSE (et_below (a, b));
820 ASSERT_TRUE (et_below (b, b));
821 ASSERT_FALSE (et_below (c, b));
822 ASSERT_TRUE (et_below (d, b));
823 ASSERT_TRUE (et_below (e, b));
824 ASSERT_FALSE (et_below (f, b));
826 ASSERT_FALSE (et_below (a, c));
827 ASSERT_FALSE (et_below (b, c));
828 ASSERT_TRUE (et_below (c, c));
829 ASSERT_FALSE (et_below (d, c));
830 ASSERT_FALSE (et_below (e, c));
831 ASSERT_TRUE (et_below (f, c));
833 ASSERT_FALSE (et_below (a, d));
834 ASSERT_FALSE (et_below (b, d));
835 ASSERT_FALSE (et_below (c, d));
836 ASSERT_TRUE (et_below (d, d));
837 ASSERT_FALSE (et_below (e, d));
838 ASSERT_FALSE (et_below (f, d));
840 ASSERT_FALSE (et_below (a, e));
841 ASSERT_FALSE (et_below (b, e));
842 ASSERT_FALSE (et_below (c, e));
843 ASSERT_FALSE (et_below (d, e));
844 ASSERT_TRUE (et_below (e, e));
845 ASSERT_FALSE (et_below (f, e));
847 ASSERT_FALSE (et_below (a, f));
848 ASSERT_FALSE (et_below (b, f));
849 ASSERT_FALSE (et_below (c, f));
850 ASSERT_FALSE (et_below (d, f));
851 ASSERT_FALSE (et_below (e, f));
852 ASSERT_TRUE (et_below (f, f));
854 et_free_tree_force (a);
857 /* Verify that two disconnected nodes are unrelated. */
860 test_disconnected_nodes ()
862 et_node *a = et_new_tree (NULL);
863 et_node *b = et_new_tree (NULL);
865 ASSERT_FALSE (et_below (a, b));
866 ASSERT_FALSE (et_below (b, a));
872 /* Run all of the selftests within this file. */
879 test_disconnected_nodes ();
882 } // namespace selftest
884 #endif /* CHECKING_P */