1/* ET-trees data structure implementation.
2 Contributed by Pavel Nejedly
3 Copyright (C) 2002-2017 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 3 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 COPYING3. If not see
18<http://www.gnu.org/licenses/>.
19
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.
23*/
24
25#include "config.h"
26#include "system.h"
27#include "coretypes.h"
28#include "alloc-pool.h"
29#include "et-forest.h"
30#include "selftest.h"
31
32/* We do not enable this with CHECKING_P, since it is awfully slow. */
33#undef DEBUG_ET
34
35#ifdef DEBUG_ET
36#include "backend.h"
37#include "hard-reg-set.h"
38#endif
39
40/* The occurrence 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 occurrence in the subtree with the minimal
55 depth. */
56};
57
58static object_allocator<et_node> et_nodes ("et_nodes pool");
59static object_allocator<et_occ> et_occurrences ("et_occ pool");
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 gcc_assert (occ != t);
92#endif
93
94 occ->prev = t;
95 if (t)
96 t->parent = occ;
97}
98
99/* Sets next field of OCC to P. */
100
101static inline void
102set_next (struct et_occ *occ, struct et_occ *t)
103{
104#ifdef DEBUG_ET
105 gcc_assert (occ != t);
106#endif
107
108 occ->next = t;
109 if (t)
110 t->parent = occ;
111}
112
113/* Recompute minimum for occurrence OCC. */
114
115static inline void
116et_recomp_min (struct et_occ *occ)
117{
118 struct et_occ *mson = occ->prev;
119
120 if (!mson
121 || (occ->next
122 && mson->min > occ->next->min))
123 mson = occ->next;
124
125 if (mson && mson->min < 0)
126 {
127 occ->min = mson->min + occ->depth;
128 occ->min_occ = mson->min_occ;
129 }
130 else
131 {
132 occ->min = occ->depth;
133 occ->min_occ = occ;
134 }
135}
136
137#ifdef DEBUG_ET
138/* Checks whether neighborhood of OCC seems sane. */
139
140static void
141et_check_occ_sanity (struct et_occ *occ)
142{
143 if (!occ)
144 return;
145
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);
150
151 if (occ->next)
152 {
153 gcc_assert (occ->next != occ->parent);
154 gcc_assert (occ->next->parent == occ);
155 }
156
157 if (occ->prev)
158 {
159 gcc_assert (occ->prev != occ->parent);
160 gcc_assert (occ->prev->parent == occ);
161 }
162
163 gcc_assert (!occ->parent
164 || occ->parent->prev == occ
165 || occ->parent->next == occ);
166}
167
168/* Checks whether tree rooted at OCC is sane. */
169
170static void
171et_check_sanity (struct et_occ *occ)
172{
173 et_check_occ_sanity (occ);
174 if (occ->prev)
175 et_check_sanity (occ->prev);
176 if (occ->next)
177 et_check_sanity (occ->next);
178}
179
180/* Checks whether tree containing OCC is sane. */
181
182static void
183et_check_tree_sanity (struct et_occ *occ)
184{
185 while (occ->parent)
186 occ = occ->parent;
187
188 et_check_sanity (occ);
189}
190
191/* For recording the paths. */
192
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
196
197static int len;
198static void *datas[MAX_NODES];
199static int depths[MAX_NODES];
200
201/* Records the path represented by OCC, with depth incremented by DEPTH. */
202
203static int
204record_path_before_1 (struct et_occ *occ, int depth)
205{
206 int mn, m;
207
208 depth += occ->depth;
209 mn = depth;
210
211 if (occ->prev)
212 {
213 m = record_path_before_1 (occ->prev, depth);
214 if (m < mn)
215 mn = m;
216 }
217
218 fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
219
220 gcc_assert (len < MAX_NODES);
221
222 depths[len] = depth;
223 datas[len] = occ->of;
224 len++;
225
226 if (occ->next)
227 {
228 m = record_path_before_1 (occ->next, depth);
229 if (m < mn)
230 mn = m;
231 }
232
233 gcc_assert (mn == occ->min + depth - occ->depth);
234
235 return mn;
236}
237
238/* Records the path represented by a tree containing OCC. */
239
240static void
241record_path_before (struct et_occ *occ)
242{
243 while (occ->parent)
244 occ = occ->parent;
245
246 len = 0;
247 record_path_before_1 (occ, 0);
248 fprintf (stderr, "\n");
249}
250
251/* Checks whether the path represented by OCC, with depth incremented by DEPTH,
252 was not changed since the last recording. */
253
254static int
255check_path_after_1 (struct et_occ *occ, int depth)
256{
257 int mn, m;
258
259 depth += occ->depth;
260 mn = depth;
261
262 if (occ->next)
263 {
264 m = check_path_after_1 (occ->next, depth);
265 if (m < mn)
266 mn = m;
267 }
268
269 len--;
270 gcc_assert (depths[len] == depth && datas[len] == occ->of);
271
272 if (occ->prev)
273 {
274 m = check_path_after_1 (occ->prev, depth);
275 if (m < mn)
276 mn = m;
277 }
278
279 gcc_assert (mn == occ->min + depth - occ->depth);
280
281 return mn;
282}
283
284/* Checks whether the path represented by a tree containing OCC was
285 not changed since the last recording. */
286
287static void
288check_path_after (struct et_occ *occ)
289{
290 while (occ->parent)
291 occ = occ->parent;
292
293 check_path_after_1 (occ, 0);
294 gcc_assert (!len);
295}
296
297#endif
298
299/* Splay the occurrence OCC to the root of the tree. */
300
301static void
302et_splay (struct et_occ *occ)
303{
304 struct et_occ *f, *gf, *ggf;
305 int occ_depth, f_depth, gf_depth;
306
307#ifdef DEBUG_ET
308 record_path_before (occ);
309 et_check_tree_sanity (occ);
310#endif
311
312 while (occ->parent)
313 {
314 occ_depth = occ->depth;
315
316 f = occ->parent;
317 f_depth = f->depth;
318
319 gf = f->parent;
320
321 if (!gf)
322 {
323 set_depth_add (occ, f_depth);
324 occ->min_occ = f->min_occ;
325 occ->min = f->min;
326
327 if (f->prev == occ)
328 {
329 /* zig */
330 set_prev (f, occ->next);
331 set_next (occ, f);
332 set_depth_add (f->prev, occ_depth);
333 }
334 else
335 {
336 /* zag */
337 set_next (f, occ->prev);
338 set_prev (occ, f);
339 set_depth_add (f->next, occ_depth);
340 }
341 set_depth (f, -occ_depth);
342 occ->parent = NULL;
343
344 et_recomp_min (f);
345#ifdef DEBUG_ET
346 et_check_tree_sanity (occ);
347 check_path_after (occ);
348#endif
349 return;
350 }
351
352 gf_depth = gf->depth;
353
354 set_depth_add (occ, f_depth + gf_depth);
355 occ->min_occ = gf->min_occ;
356 occ->min = gf->min;
357
358 ggf = gf->parent;
359
360 if (gf->prev == f)
361 {
362 if (f->prev == occ)
363 {
364 /* zig zig */
365 set_prev (gf, f->next);
366 set_prev (f, occ->next);
367 set_next (occ, f);
368 set_next (f, gf);
369
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);
374 }
375 else
376 {
377 /* zag zig */
378 set_prev (gf, occ->next);
379 set_next (f, occ->prev);
380 set_prev (occ, f);
381 set_next (occ, gf);
382
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);
387 }
388 }
389 else
390 {
391 if (f->prev == occ)
392 {
393 /* zig zag */
394 set_next (gf, occ->prev);
395 set_prev (f, occ->next);
396 set_prev (occ, gf);
397 set_next (occ, f);
398
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);
403 }
404 else
405 {
406 /* zag zag */
407 set_next (gf, f->prev);
408 set_next (f, occ->prev);
409 set_prev (occ, f);
410 set_prev (f, gf);
411
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);
416 }
417 }
418
419 occ->parent = ggf;
420 if (ggf)
421 {
422 if (ggf->prev == gf)
423 ggf->prev = occ;
424 else
425 ggf->next = occ;
426 }
427
428 et_recomp_min (gf);
429 et_recomp_min (f);
430#ifdef DEBUG_ET
431 et_check_tree_sanity (occ);
432#endif
433 }
434
435#ifdef DEBUG_ET
436 et_check_sanity (occ);
437 check_path_after (occ);
438#endif
439}
440
441/* Create a new et tree occurrence of NODE. */
442
443static struct et_occ *
444et_new_occ (struct et_node *node)
445{
446 et_occ *nw = et_occurrences.allocate ();
447
448 nw->of = node;
449 nw->parent = NULL;
450 nw->prev = NULL;
451 nw->next = NULL;
452
453 nw->depth = 0;
454 nw->min_occ = nw;
455 nw->min = 0;
456
457 return nw;
458}
459
460/* Create a new et tree containing DATA. */
461
462struct et_node *
463et_new_tree (void *data)
464{
465 et_node *nw = et_nodes.allocate ();
466
467 nw->data = data;
468 nw->father = NULL;
469 nw->left = NULL;
470 nw->right = NULL;
471 nw->son = NULL;
472
473 nw->rightmost_occ = et_new_occ (nw);
474 nw->parent_occ = NULL;
475
476 return nw;
477}
478
479/* Releases et tree T. */
480
481void
482et_free_tree (struct et_node *t)
483{
484 while (t->son)
485 et_split (t->son);
486
487 if (t->father)
488 et_split (t);
489
490 et_occurrences.remove (t->rightmost_occ);
491 et_nodes.remove (t);
492}
493
494/* Releases et tree T without maintaining other nodes. */
495
496void
497et_free_tree_force (struct et_node *t)
498{
499 et_occurrences.remove (t->rightmost_occ);
500 if (t->parent_occ)
501 et_occurrences.remove (t->parent_occ);
502 et_nodes.remove (t);
503}
504
505/* Release the alloc pools, if they are empty. */
506
507void
508et_free_pools (void)
509{
510 et_occurrences.release_if_empty ();
511 et_nodes.release_if_empty ();
512}
513
514/* Sets father of et tree T to FATHER. */
515
516void
517et_set_father (struct et_node *t, struct et_node *father)
518{
519 struct et_node *left, *right;
520 struct et_occ *rmost, *left_part, *new_f_occ, *p;
521
522 /* Update the path represented in the splay tree. */
523 new_f_occ = et_new_occ (father);
524
525 rmost = father->rightmost_occ;
526 et_splay (rmost);
527
528 left_part = rmost->prev;
529
530 p = t->rightmost_occ;
531 et_splay (p);
532
533 set_prev (new_f_occ, left_part);
534 set_next (new_f_occ, p);
535
536 p->depth++;
537 p->min++;
538 et_recomp_min (new_f_occ);
539
540 set_prev (rmost, new_f_occ);
541
542 if (new_f_occ->min + rmost->depth < rmost->min)
543 {
544 rmost->min = new_f_occ->min + rmost->depth;
545 rmost->min_occ = new_f_occ->min_occ;
546 }
547
548 t->parent_occ = new_f_occ;
549
550 /* Update the tree. */
551 t->father = father;
552 right = father->son;
553 if (right)
554 left = right->left;
555 else
556 left = right = t;
557
558 left->right = t;
559 right->left = t;
560 t->left = left;
561 t->right = right;
562
563 father->son = t;
564
565#ifdef DEBUG_ET
566 et_check_tree_sanity (rmost);
567 record_path_before (rmost);
568#endif
569}
570
571/* Splits the edge from T to its father. */
572
573void
574et_split (struct et_node *t)
575{
576 struct et_node *father = t->father;
577 struct et_occ *r, *l, *rmost, *p_occ;
578
579 /* Update the path represented by the splay tree. */
580 rmost = t->rightmost_occ;
581 et_splay (rmost);
582
583 for (r = rmost->next; r->prev; r = r->prev)
584 continue;
585 et_splay (r);
586
587 r->prev->parent = NULL;
588 p_occ = t->parent_occ;
589 et_splay (p_occ);
590 t->parent_occ = NULL;
591
592 l = p_occ->prev;
593 p_occ->next->parent = NULL;
594
595 set_prev (r, l);
596
597 et_recomp_min (r);
598
599 et_splay (rmost);
600 rmost->depth = 0;
601 rmost->min = 0;
602
603 et_occurrences.remove (p_occ);
604
605 /* Update the tree. */
606 if (father->son == t)
607 father->son = t->right;
608 if (father->son == t)
609 father->son = NULL;
610 else
611 {
612 t->left->right = t->right;
613 t->right->left = t->left;
614 }
615 t->left = t->right = NULL;
616 t->father = NULL;
617
618#ifdef DEBUG_ET
619 et_check_tree_sanity (rmost);
620 record_path_before (rmost);
621
622 et_check_tree_sanity (r);
623 record_path_before (r);
624#endif
625}
626
627/* Finds the nearest common ancestor of the nodes N1 and N2. */
628
629struct et_node *
630et_nca (struct et_node *n1, struct et_node *n2)
631{
632 struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
633 struct et_occ *l, *r, *ret;
634 int mn;
635
636 if (n1 == n2)
637 return n1;
638
639 et_splay (o1);
640 l = o1->prev;
641 r = o1->next;
642 if (l)
643 l->parent = NULL;
644 if (r)
645 r->parent = NULL;
646 et_splay (o2);
647
648 if (l == o2 || (l && l->parent != NULL))
649 {
650 ret = o2->next;
651
652 set_prev (o1, o2);
653 if (r)
654 r->parent = o1;
655 }
656 else if (r == o2 || (r && r->parent != NULL))
657 {
658 ret = o2->prev;
659
660 set_next (o1, o2);
661 if (l)
662 l->parent = o1;
663 }
664 else
665 {
666 /* O1 and O2 are in different components of the forest. */
667 if (l)
668 l->parent = o1;
669 if (r)
670 r->parent = o1;
671 return NULL;
672 }
673
674 if (0 < o2->depth)
675 {
676 om = o1;
677 mn = o1->depth;
678 }
679 else
680 {
681 om = o2;
682 mn = o2->depth + o1->depth;
683 }
684
685#ifdef DEBUG_ET
686 et_check_tree_sanity (o2);
687#endif
688
689 if (ret && ret->min + o1->depth + o2->depth < mn)
690 return ret->min_occ->of;
691 else
692 return om->of;
693}
694
695/* Checks whether the node UP is an ancestor of the node DOWN. */
696
697bool
698et_below (struct et_node *down, struct et_node *up)
699{
700 struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
701 struct et_occ *l, *r;
702
703 if (up == down)
704 return true;
705
706 et_splay (u);
707 l = u->prev;
708 r = u->next;
709
710 if (!l)
711 return false;
712
713 l->parent = NULL;
714
715 if (r)
716 r->parent = NULL;
717
718 et_splay (d);
719
720 if (l == d || l->parent != NULL)
721 {
722 if (r)
723 r->parent = u;
724 set_prev (u, d);
725#ifdef DEBUG_ET
726 et_check_tree_sanity (u);
727#endif
728 }
729 else
730 {
731 l->parent = u;
732
733 /* In case O1 and O2 are in two different trees, we must just restore the
734 original state. */
735 if (r && r->parent != NULL)
736 set_next (u, d);
737 else
738 set_next (u, r);
739
740#ifdef DEBUG_ET
741 et_check_tree_sanity (u);
742#endif
743 return false;
744 }
745
746 if (0 >= d->depth)
747 return false;
748
749 return !d->next || d->next->min + d->depth >= 0;
750}
751
752/* Returns the root of the tree that contains NODE. */
753
754struct et_node *
755et_root (struct et_node *node)
756{
757 struct et_occ *occ = node->rightmost_occ, *r;
758
759 /* The root of the tree corresponds to the rightmost occurrence in the
760 represented path. */
761 et_splay (occ);
762 for (r = occ; r->next; r = r->next)
763 continue;
764 et_splay (r);
765
766 return r->of;
767}
768
769#if CHECKING_P
770
771namespace selftest {
772
773/* Selftests for et-forest.c. */
774
775/* Perform sanity checks for a tree consisting of a single node. */
776
777static void
778test_single_node ()
779{
780 void *test_data = (void *)0xcafebabe;
781
782 et_node *n = et_new_tree (test_data);
783 ASSERT_EQ (n->data, test_data);
784 ASSERT_EQ (n, et_root (n));
785 et_free_tree (n);
786}
787
788/* Test of this tree:
789 a
790 / \
791 / \
792 b c
793 / \ |
794 d e f. */
795
796static void
797test_simple_tree ()
798{
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);
805
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);
811
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));
818
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));
825
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));
832
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));
839
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));
846
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));
853
854 et_free_tree_force (a);
855}
856
857/* Verify that two disconnected nodes are unrelated. */
858
859static void
860test_disconnected_nodes ()
861{
862 et_node *a = et_new_tree (NULL);
863 et_node *b = et_new_tree (NULL);
864
865 ASSERT_FALSE (et_below (a, b));
866 ASSERT_FALSE (et_below (b, a));
867
868 et_free_tree (a);
869 et_free_tree (b);
870}
871
872/* Run all of the selftests within this file. */
873
874void
875et_forest_c_tests ()
876{
877 test_single_node ();
878 test_simple_tree ();
879 test_disconnected_nodes ();
880}
881
882} // namespace selftest
883
884#endif /* CHECKING_P */
885