| /* ET-trees data structure implementation. |
| Contributed by Pavel Nejedly |
| Copyright (C) 2002-2017 Free Software Foundation, Inc. |
| |
| This file is part of the libiberty library. |
| Libiberty is free software; you can redistribute it and/or |
| modify it under the terms of the GNU Library General Public |
| License as published by the Free Software Foundation; either |
| version 3 of the License, or (at your option) any later version. |
| |
| Libiberty is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| Library General Public License for more details. |
| |
| You should have received a copy of the GNU Library General Public |
| License along with libiberty; see the file COPYING3. If not see |
| <http://www.gnu.org/licenses/>. |
| |
| The ET-forest structure is described in: |
| D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. |
| J. G'omput. System Sci., 26(3):362 381, 1983. |
| */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "alloc-pool.h" |
| #include "et-forest.h" |
| #include "selftest.h" |
| |
| /* We do not enable this with CHECKING_P, since it is awfully slow. */ |
| #undef DEBUG_ET |
| |
| #ifdef DEBUG_ET |
| #include "backend.h" |
| #include "hard-reg-set.h" |
| #endif |
| |
| /* The occurrence of a node in the et tree. */ |
| struct et_occ |
| { |
| struct et_node *of; /* The node. */ |
| |
| struct et_occ *parent; /* Parent in the splay-tree. */ |
| struct et_occ *prev; /* Left son in the splay-tree. */ |
| struct et_occ *next; /* Right son in the splay-tree. */ |
| |
| int depth; /* The depth of the node is the sum of depth |
| fields on the path to the root. */ |
| int min; /* The minimum value of the depth in the subtree |
| is obtained by adding sum of depth fields |
| on the path to the root. */ |
| struct et_occ *min_occ; /* The occurrence in the subtree with the minimal |
| depth. */ |
| }; |
| |
| static object_allocator<et_node> et_nodes ("et_nodes pool"); |
| static object_allocator<et_occ> et_occurrences ("et_occ pool"); |
| |
| /* Changes depth of OCC to D. */ |
| |
| static inline void |
| set_depth (struct et_occ *occ, int d) |
| { |
| if (!occ) |
| return; |
| |
| occ->min += d - occ->depth; |
| occ->depth = d; |
| } |
| |
| /* Adds D to the depth of OCC. */ |
| |
| static inline void |
| set_depth_add (struct et_occ *occ, int d) |
| { |
| if (!occ) |
| return; |
| |
| occ->min += d; |
| occ->depth += d; |
| } |
| |
| /* Sets prev field of OCC to P. */ |
| |
| static inline void |
| set_prev (struct et_occ *occ, struct et_occ *t) |
| { |
| #ifdef DEBUG_ET |
| gcc_assert (occ != t); |
| #endif |
| |
| occ->prev = t; |
| if (t) |
| t->parent = occ; |
| } |
| |
| /* Sets next field of OCC to P. */ |
| |
| static inline void |
| set_next (struct et_occ *occ, struct et_occ *t) |
| { |
| #ifdef DEBUG_ET |
| gcc_assert (occ != t); |
| #endif |
| |
| occ->next = t; |
| if (t) |
| t->parent = occ; |
| } |
| |
| /* Recompute minimum for occurrence OCC. */ |
| |
| static inline void |
| et_recomp_min (struct et_occ *occ) |
| { |
| struct et_occ *mson = occ->prev; |
| |
| if (!mson |
| || (occ->next |
| && mson->min > occ->next->min)) |
| mson = occ->next; |
| |
| if (mson && mson->min < 0) |
| { |
| occ->min = mson->min + occ->depth; |
| occ->min_occ = mson->min_occ; |
| } |
| else |
| { |
| occ->min = occ->depth; |
| occ->min_occ = occ; |
| } |
| } |
| |
| #ifdef DEBUG_ET |
| /* Checks whether neighborhood of OCC seems sane. */ |
| |
| static void |
| et_check_occ_sanity (struct et_occ *occ) |
| { |
| if (!occ) |
| return; |
| |
| gcc_assert (occ->parent != occ); |
| gcc_assert (occ->prev != occ); |
| gcc_assert (occ->next != occ); |
| gcc_assert (!occ->next || occ->next != occ->prev); |
| |
| if (occ->next) |
| { |
| gcc_assert (occ->next != occ->parent); |
| gcc_assert (occ->next->parent == occ); |
| } |
| |
| if (occ->prev) |
| { |
| gcc_assert (occ->prev != occ->parent); |
| gcc_assert (occ->prev->parent == occ); |
| } |
| |
| gcc_assert (!occ->parent |
| || occ->parent->prev == occ |
| || occ->parent->next == occ); |
| } |
| |
| /* Checks whether tree rooted at OCC is sane. */ |
| |
| static void |
| et_check_sanity (struct et_occ *occ) |
| { |
| et_check_occ_sanity (occ); |
| if (occ->prev) |
| et_check_sanity (occ->prev); |
| if (occ->next) |
| et_check_sanity (occ->next); |
| } |
| |
| /* Checks whether tree containing OCC is sane. */ |
| |
| static void |
| et_check_tree_sanity (struct et_occ *occ) |
| { |
| while (occ->parent) |
| occ = occ->parent; |
| |
| et_check_sanity (occ); |
| } |
| |
| /* For recording the paths. */ |
| |
| /* An ad-hoc constant; if the function has more blocks, this won't work, |
| but since it is used for debugging only, it does not matter. */ |
| #define MAX_NODES 100000 |
| |
| static int len; |
| static void *datas[MAX_NODES]; |
| static int depths[MAX_NODES]; |
| |
| /* Records the path represented by OCC, with depth incremented by DEPTH. */ |
| |
| static int |
| record_path_before_1 (struct et_occ *occ, int depth) |
| { |
| int mn, m; |
| |
| depth += occ->depth; |
| mn = depth; |
| |
| if (occ->prev) |
| { |
| m = record_path_before_1 (occ->prev, depth); |
| if (m < mn) |
| mn = m; |
| } |
| |
| fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth); |
| |
| gcc_assert (len < MAX_NODES); |
| |
| depths[len] = depth; |
| datas[len] = occ->of; |
| len++; |
| |
| if (occ->next) |
| { |
| m = record_path_before_1 (occ->next, depth); |
| if (m < mn) |
| mn = m; |
| } |
| |
| gcc_assert (mn == occ->min + depth - occ->depth); |
| |
| return mn; |
| } |
| |
| /* Records the path represented by a tree containing OCC. */ |
| |
| static void |
| record_path_before (struct et_occ *occ) |
| { |
| while (occ->parent) |
| occ = occ->parent; |
| |
| len = 0; |
| record_path_before_1 (occ, 0); |
| fprintf (stderr, "\n"); |
| } |
| |
| /* Checks whether the path represented by OCC, with depth incremented by DEPTH, |
| was not changed since the last recording. */ |
| |
| static int |
| check_path_after_1 (struct et_occ *occ, int depth) |
| { |
| int mn, m; |
| |
| depth += occ->depth; |
| mn = depth; |
| |
| if (occ->next) |
| { |
| m = check_path_after_1 (occ->next, depth); |
| if (m < mn) |
| mn = m; |
| } |
| |
| len--; |
| gcc_assert (depths[len] == depth && datas[len] == occ->of); |
| |
| if (occ->prev) |
| { |
| m = check_path_after_1 (occ->prev, depth); |
| if (m < mn) |
| mn = m; |
| } |
| |
| gcc_assert (mn == occ->min + depth - occ->depth); |
| |
| return mn; |
| } |
| |
| /* Checks whether the path represented by a tree containing OCC was |
| not changed since the last recording. */ |
| |
| static void |
| check_path_after (struct et_occ *occ) |
| { |
| while (occ->parent) |
| occ = occ->parent; |
| |
| check_path_after_1 (occ, 0); |
| gcc_assert (!len); |
| } |
| |
| #endif |
| |
| /* Splay the occurrence OCC to the root of the tree. */ |
| |
| static void |
| et_splay (struct et_occ *occ) |
| { |
| struct et_occ *f, *gf, *ggf; |
| int occ_depth, f_depth, gf_depth; |
| |
| #ifdef DEBUG_ET |
| record_path_before (occ); |
| et_check_tree_sanity (occ); |
| #endif |
| |
| while (occ->parent) |
| { |
| occ_depth = occ->depth; |
| |
| f = occ->parent; |
| f_depth = f->depth; |
| |
| gf = f->parent; |
| |
| if (!gf) |
| { |
| set_depth_add (occ, f_depth); |
| occ->min_occ = f->min_occ; |
| occ->min = f->min; |
| |
| if (f->prev == occ) |
| { |
| /* zig */ |
| set_prev (f, occ->next); |
| set_next (occ, f); |
| set_depth_add (f->prev, occ_depth); |
| } |
| else |
| { |
| /* zag */ |
| set_next (f, occ->prev); |
| set_prev (occ, f); |
| set_depth_add (f->next, occ_depth); |
| } |
| set_depth (f, -occ_depth); |
| occ->parent = NULL; |
| |
| et_recomp_min (f); |
| #ifdef DEBUG_ET |
| et_check_tree_sanity (occ); |
| check_path_after (occ); |
| #endif |
| return; |
| } |
| |
| gf_depth = gf->depth; |
| |
| set_depth_add (occ, f_depth + gf_depth); |
| occ->min_occ = gf->min_occ; |
| occ->min = gf->min; |
| |
| ggf = gf->parent; |
| |
| if (gf->prev == f) |
| { |
| if (f->prev == occ) |
| { |
| /* zig zig */ |
| set_prev (gf, f->next); |
| set_prev (f, occ->next); |
| set_next (occ, f); |
| set_next (f, gf); |
| |
| set_depth (f, -occ_depth); |
| set_depth_add (f->prev, occ_depth); |
| set_depth (gf, -f_depth); |
| set_depth_add (gf->prev, f_depth); |
| } |
| else |
| { |
| /* zag zig */ |
| set_prev (gf, occ->next); |
| set_next (f, occ->prev); |
| set_prev (occ, f); |
| set_next (occ, gf); |
| |
| set_depth (f, -occ_depth); |
| set_depth_add (f->next, occ_depth); |
| set_depth (gf, -occ_depth - f_depth); |
| set_depth_add (gf->prev, occ_depth + f_depth); |
| } |
| } |
| else |
| { |
| if (f->prev == occ) |
| { |
| /* zig zag */ |
| set_next (gf, occ->prev); |
| set_prev (f, occ->next); |
| set_prev (occ, gf); |
| set_next (occ, f); |
| |
| set_depth (f, -occ_depth); |
| set_depth_add (f->prev, occ_depth); |
| set_depth (gf, -occ_depth - f_depth); |
| set_depth_add (gf->next, occ_depth + f_depth); |
| } |
| else |
| { |
| /* zag zag */ |
| set_next (gf, f->prev); |
| set_next (f, occ->prev); |
| set_prev (occ, f); |
| set_prev (f, gf); |
| |
| set_depth (f, -occ_depth); |
| set_depth_add (f->next, occ_depth); |
| set_depth (gf, -f_depth); |
| set_depth_add (gf->next, f_depth); |
| } |
| } |
| |
| occ->parent = ggf; |
| if (ggf) |
| { |
| if (ggf->prev == gf) |
| ggf->prev = occ; |
| else |
| ggf->next = occ; |
| } |
| |
| et_recomp_min (gf); |
| et_recomp_min (f); |
| #ifdef DEBUG_ET |
| et_check_tree_sanity (occ); |
| #endif |
| } |
| |
| #ifdef DEBUG_ET |
| et_check_sanity (occ); |
| check_path_after (occ); |
| #endif |
| } |
| |
| /* Create a new et tree occurrence of NODE. */ |
| |
| static struct et_occ * |
| et_new_occ (struct et_node *node) |
| { |
| et_occ *nw = et_occurrences.allocate (); |
| |
| nw->of = node; |
| nw->parent = NULL; |
| nw->prev = NULL; |
| nw->next = NULL; |
| |
| nw->depth = 0; |
| nw->min_occ = nw; |
| nw->min = 0; |
| |
| return nw; |
| } |
| |
| /* Create a new et tree containing DATA. */ |
| |
| struct et_node * |
| et_new_tree (void *data) |
| { |
| et_node *nw = et_nodes.allocate (); |
| |
| nw->data = data; |
| nw->father = NULL; |
| nw->left = NULL; |
| nw->right = NULL; |
| nw->son = NULL; |
| |
| nw->rightmost_occ = et_new_occ (nw); |
| nw->parent_occ = NULL; |
| |
| return nw; |
| } |
| |
| /* Releases et tree T. */ |
| |
| void |
| et_free_tree (struct et_node *t) |
| { |
| while (t->son) |
| et_split (t->son); |
| |
| if (t->father) |
| et_split (t); |
| |
| et_occurrences.remove (t->rightmost_occ); |
| et_nodes.remove (t); |
| } |
| |
| /* Releases et tree T without maintaining other nodes. */ |
| |
| void |
| et_free_tree_force (struct et_node *t) |
| { |
| et_occurrences.remove (t->rightmost_occ); |
| if (t->parent_occ) |
| et_occurrences.remove (t->parent_occ); |
| et_nodes.remove (t); |
| } |
| |
| /* Release the alloc pools, if they are empty. */ |
| |
| void |
| et_free_pools (void) |
| { |
| et_occurrences.release_if_empty (); |
| et_nodes.release_if_empty (); |
| } |
| |
| /* Sets father of et tree T to FATHER. */ |
| |
| void |
| et_set_father (struct et_node *t, struct et_node *father) |
| { |
| struct et_node *left, *right; |
| struct et_occ *rmost, *left_part, *new_f_occ, *p; |
| |
| /* Update the path represented in the splay tree. */ |
| new_f_occ = et_new_occ (father); |
| |
| rmost = father->rightmost_occ; |
| et_splay (rmost); |
| |
| left_part = rmost->prev; |
| |
| p = t->rightmost_occ; |
| et_splay (p); |
| |
| set_prev (new_f_occ, left_part); |
| set_next (new_f_occ, p); |
| |
| p->depth++; |
| p->min++; |
| et_recomp_min (new_f_occ); |
| |
| set_prev (rmost, new_f_occ); |
| |
| if (new_f_occ->min + rmost->depth < rmost->min) |
| { |
| rmost->min = new_f_occ->min + rmost->depth; |
| rmost->min_occ = new_f_occ->min_occ; |
| } |
| |
| t->parent_occ = new_f_occ; |
| |
| /* Update the tree. */ |
| t->father = father; |
| right = father->son; |
| if (right) |
| left = right->left; |
| else |
| left = right = t; |
| |
| left->right = t; |
| right->left = t; |
| t->left = left; |
| t->right = right; |
| |
| father->son = t; |
| |
| #ifdef DEBUG_ET |
| et_check_tree_sanity (rmost); |
| record_path_before (rmost); |
| #endif |
| } |
| |
| /* Splits the edge from T to its father. */ |
| |
| void |
| et_split (struct et_node *t) |
| { |
| struct et_node *father = t->father; |
| struct et_occ *r, *l, *rmost, *p_occ; |
| |
| /* Update the path represented by the splay tree. */ |
| rmost = t->rightmost_occ; |
| et_splay (rmost); |
| |
| for (r = rmost->next; r->prev; r = r->prev) |
| continue; |
| et_splay (r); |
| |
| r->prev->parent = NULL; |
| p_occ = t->parent_occ; |
| et_splay (p_occ); |
| t->parent_occ = NULL; |
| |
| l = p_occ->prev; |
| p_occ->next->parent = NULL; |
| |
| set_prev (r, l); |
| |
| et_recomp_min (r); |
| |
| et_splay (rmost); |
| rmost->depth = 0; |
| rmost->min = 0; |
| |
| et_occurrences.remove (p_occ); |
| |
| /* Update the tree. */ |
| if (father->son == t) |
| father->son = t->right; |
| if (father->son == t) |
| father->son = NULL; |
| else |
| { |
| t->left->right = t->right; |
| t->right->left = t->left; |
| } |
| t->left = t->right = NULL; |
| t->father = NULL; |
| |
| #ifdef DEBUG_ET |
| et_check_tree_sanity (rmost); |
| record_path_before (rmost); |
| |
| et_check_tree_sanity (r); |
| record_path_before (r); |
| #endif |
| } |
| |
| /* Finds the nearest common ancestor of the nodes N1 and N2. */ |
| |
| struct et_node * |
| et_nca (struct et_node *n1, struct et_node *n2) |
| { |
| struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om; |
| struct et_occ *l, *r, *ret; |
| int mn; |
| |
| if (n1 == n2) |
| return n1; |
| |
| et_splay (o1); |
| l = o1->prev; |
| r = o1->next; |
| if (l) |
| l->parent = NULL; |
| if (r) |
| r->parent = NULL; |
| et_splay (o2); |
| |
| if (l == o2 || (l && l->parent != NULL)) |
| { |
| ret = o2->next; |
| |
| set_prev (o1, o2); |
| if (r) |
| r->parent = o1; |
| } |
| else if (r == o2 || (r && r->parent != NULL)) |
| { |
| ret = o2->prev; |
| |
| set_next (o1, o2); |
| if (l) |
| l->parent = o1; |
| } |
| else |
| { |
| /* O1 and O2 are in different components of the forest. */ |
| if (l) |
| l->parent = o1; |
| if (r) |
| r->parent = o1; |
| return NULL; |
| } |
| |
| if (0 < o2->depth) |
| { |
| om = o1; |
| mn = o1->depth; |
| } |
| else |
| { |
| om = o2; |
| mn = o2->depth + o1->depth; |
| } |
| |
| #ifdef DEBUG_ET |
| et_check_tree_sanity (o2); |
| #endif |
| |
| if (ret && ret->min + o1->depth + o2->depth < mn) |
| return ret->min_occ->of; |
| else |
| return om->of; |
| } |
| |
| /* Checks whether the node UP is an ancestor of the node DOWN. */ |
| |
| bool |
| et_below (struct et_node *down, struct et_node *up) |
| { |
| struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ; |
| struct et_occ *l, *r; |
| |
| if (up == down) |
| return true; |
| |
| et_splay (u); |
| l = u->prev; |
| r = u->next; |
| |
| if (!l) |
| return false; |
| |
| l->parent = NULL; |
| |
| if (r) |
| r->parent = NULL; |
| |
| et_splay (d); |
| |
| if (l == d || l->parent != NULL) |
| { |
| if (r) |
| r->parent = u; |
| set_prev (u, d); |
| #ifdef DEBUG_ET |
| et_check_tree_sanity (u); |
| #endif |
| } |
| else |
| { |
| l->parent = u; |
| |
| /* In case O1 and O2 are in two different trees, we must just restore the |
| original state. */ |
| if (r && r->parent != NULL) |
| set_next (u, d); |
| else |
| set_next (u, r); |
| |
| #ifdef DEBUG_ET |
| et_check_tree_sanity (u); |
| #endif |
| return false; |
| } |
| |
| if (0 >= d->depth) |
| return false; |
| |
| return !d->next || d->next->min + d->depth >= 0; |
| } |
| |
| /* Returns the root of the tree that contains NODE. */ |
| |
| struct et_node * |
| et_root (struct et_node *node) |
| { |
| struct et_occ *occ = node->rightmost_occ, *r; |
| |
| /* The root of the tree corresponds to the rightmost occurrence in the |
| represented path. */ |
| et_splay (occ); |
| for (r = occ; r->next; r = r->next) |
| continue; |
| et_splay (r); |
| |
| return r->of; |
| } |
| |
| #if CHECKING_P |
| |
| namespace selftest { |
| |
| /* Selftests for et-forest.c. */ |
| |
| /* Perform sanity checks for a tree consisting of a single node. */ |
| |
| static void |
| test_single_node () |
| { |
| void *test_data = (void *)0xcafebabe; |
| |
| et_node *n = et_new_tree (test_data); |
| ASSERT_EQ (n->data, test_data); |
| ASSERT_EQ (n, et_root (n)); |
| et_free_tree (n); |
| } |
| |
| /* Test of this tree: |
| a |
| / \ |
| / \ |
| b c |
| / \ | |
| d e f. */ |
| |
| static void |
| test_simple_tree () |
| { |
| et_node *a = et_new_tree (NULL); |
| et_node *b = et_new_tree (NULL); |
| et_node *c = et_new_tree (NULL); |
| et_node *d = et_new_tree (NULL); |
| et_node *e = et_new_tree (NULL); |
| et_node *f = et_new_tree (NULL); |
| |
| et_set_father (b, a); |
| et_set_father (c, a); |
| et_set_father (d, b); |
| et_set_father (e, b); |
| et_set_father (f, c); |
| |
| ASSERT_TRUE (et_below (a, a)); |
| ASSERT_TRUE (et_below (b, a)); |
| ASSERT_TRUE (et_below (c, a)); |
| ASSERT_TRUE (et_below (d, a)); |
| ASSERT_TRUE (et_below (e, a)); |
| ASSERT_TRUE (et_below (f, a)); |
| |
| ASSERT_FALSE (et_below (a, b)); |
| ASSERT_TRUE (et_below (b, b)); |
| ASSERT_FALSE (et_below (c, b)); |
| ASSERT_TRUE (et_below (d, b)); |
| ASSERT_TRUE (et_below (e, b)); |
| ASSERT_FALSE (et_below (f, b)); |
| |
| ASSERT_FALSE (et_below (a, c)); |
| ASSERT_FALSE (et_below (b, c)); |
| ASSERT_TRUE (et_below (c, c)); |
| ASSERT_FALSE (et_below (d, c)); |
| ASSERT_FALSE (et_below (e, c)); |
| ASSERT_TRUE (et_below (f, c)); |
| |
| ASSERT_FALSE (et_below (a, d)); |
| ASSERT_FALSE (et_below (b, d)); |
| ASSERT_FALSE (et_below (c, d)); |
| ASSERT_TRUE (et_below (d, d)); |
| ASSERT_FALSE (et_below (e, d)); |
| ASSERT_FALSE (et_below (f, d)); |
| |
| ASSERT_FALSE (et_below (a, e)); |
| ASSERT_FALSE (et_below (b, e)); |
| ASSERT_FALSE (et_below (c, e)); |
| ASSERT_FALSE (et_below (d, e)); |
| ASSERT_TRUE (et_below (e, e)); |
| ASSERT_FALSE (et_below (f, e)); |
| |
| ASSERT_FALSE (et_below (a, f)); |
| ASSERT_FALSE (et_below (b, f)); |
| ASSERT_FALSE (et_below (c, f)); |
| ASSERT_FALSE (et_below (d, f)); |
| ASSERT_FALSE (et_below (e, f)); |
| ASSERT_TRUE (et_below (f, f)); |
| |
| et_free_tree_force (a); |
| } |
| |
| /* Verify that two disconnected nodes are unrelated. */ |
| |
| static void |
| test_disconnected_nodes () |
| { |
| et_node *a = et_new_tree (NULL); |
| et_node *b = et_new_tree (NULL); |
| |
| ASSERT_FALSE (et_below (a, b)); |
| ASSERT_FALSE (et_below (b, a)); |
| |
| et_free_tree (a); |
| et_free_tree (b); |
| } |
| |
| /* Run all of the selftests within this file. */ |
| |
| void |
| et_forest_c_tests () |
| { |
| test_single_node (); |
| test_simple_tree (); |
| test_disconnected_nodes (); |
| } |
| |
| } // namespace selftest |
| |
| #endif /* CHECKING_P */ |