1 /* ET-trees data structure implementation.
2 Contributed by Pavel Nejedly
3 Copyright (C) 2002-2014 Free Software Foundation, Inc.
4
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.
10
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.
15
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/>.
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 "et-forest.h"
29 #include "alloc-pool.h"
30
31 /* We do not enable this with ENABLE_CHECKING, since it is awfully slow. */
32 #undef DEBUG_ET
33
34 #ifdef DEBUG_ET
35 #include "basic-block.h" /* To access index in record_path_before_1. */
36 #endif
37
38 /* The occurrence of a node in the et tree. */
39 struct et_occ
40 {
41 struct et_node *of; /* The node. */
42
43 struct et_occ *parent; /* Parent in the splay-tree. */
44 struct et_occ *prev; /* Left son in the splay-tree. */
45 struct et_occ *next; /* Right son in the splay-tree. */
46
47 int depth; /* The depth of the node is the sum of depth
48 fields on the path to the root. */
49 int min; /* The minimum value of the depth in the subtree
50 is obtained by adding sum of depth fields
51 on the path to the root. */
52 struct et_occ *min_occ; /* The occurrence in the subtree with the minimal
53 depth. */
54 };
55
56 static alloc_pool et_nodes;
57 static alloc_pool et_occurrences;
58
59 /* Changes depth of OCC to D. */
60
61 static inline void
set_depth(struct et_occ * occ,int d)62 set_depth (struct et_occ *occ, int d)
63 {
64 if (!occ)
65 return;
66
67 occ->min += d - occ->depth;
68 occ->depth = d;
69 }
70
71 /* Adds D to the depth of OCC. */
72
73 static inline void
set_depth_add(struct et_occ * occ,int d)74 set_depth_add (struct et_occ *occ, int d)
75 {
76 if (!occ)
77 return;
78
79 occ->min += d;
80 occ->depth += d;
81 }
82
83 /* Sets prev field of OCC to P. */
84
85 static inline void
set_prev(struct et_occ * occ,struct et_occ * t)86 set_prev (struct et_occ *occ, struct et_occ *t)
87 {
88 #ifdef DEBUG_ET
89 gcc_assert (occ != t);
90 #endif
91
92 occ->prev = t;
93 if (t)
94 t->parent = occ;
95 }
96
97 /* Sets next field of OCC to P. */
98
99 static inline void
set_next(struct et_occ * occ,struct et_occ * t)100 set_next (struct et_occ *occ, struct et_occ *t)
101 {
102 #ifdef DEBUG_ET
103 gcc_assert (occ != t);
104 #endif
105
106 occ->next = t;
107 if (t)
108 t->parent = occ;
109 }
110
111 /* Recompute minimum for occurrence OCC. */
112
113 static inline void
et_recomp_min(struct et_occ * occ)114 et_recomp_min (struct et_occ *occ)
115 {
116 struct et_occ *mson = occ->prev;
117
118 if (!mson
119 || (occ->next
120 && mson->min > occ->next->min))
121 mson = occ->next;
122
123 if (mson && mson->min < 0)
124 {
125 occ->min = mson->min + occ->depth;
126 occ->min_occ = mson->min_occ;
127 }
128 else
129 {
130 occ->min = occ->depth;
131 occ->min_occ = occ;
132 }
133 }
134
135 #ifdef DEBUG_ET
136 /* Checks whether neighborhood of OCC seems sane. */
137
138 static void
et_check_occ_sanity(struct et_occ * occ)139 et_check_occ_sanity (struct et_occ *occ)
140 {
141 if (!occ)
142 return;
143
144 gcc_assert (occ->parent != occ);
145 gcc_assert (occ->prev != occ);
146 gcc_assert (occ->next != occ);
147 gcc_assert (!occ->next || occ->next != occ->prev);
148
149 if (occ->next)
150 {
151 gcc_assert (occ->next != occ->parent);
152 gcc_assert (occ->next->parent == occ);
153 }
154
155 if (occ->prev)
156 {
157 gcc_assert (occ->prev != occ->parent);
158 gcc_assert (occ->prev->parent == occ);
159 }
160
161 gcc_assert (!occ->parent
162 || occ->parent->prev == occ
163 || occ->parent->next == occ);
164 }
165
166 /* Checks whether tree rooted at OCC is sane. */
167
168 static void
et_check_sanity(struct et_occ * occ)169 et_check_sanity (struct et_occ *occ)
170 {
171 et_check_occ_sanity (occ);
172 if (occ->prev)
173 et_check_sanity (occ->prev);
174 if (occ->next)
175 et_check_sanity (occ->next);
176 }
177
178 /* Checks whether tree containing OCC is sane. */
179
180 static void
et_check_tree_sanity(struct et_occ * occ)181 et_check_tree_sanity (struct et_occ *occ)
182 {
183 while (occ->parent)
184 occ = occ->parent;
185
186 et_check_sanity (occ);
187 }
188
189 /* For recording the paths. */
190
191 /* An ad-hoc constant; if the function has more blocks, this won't work,
192 but since it is used for debugging only, it does not matter. */
193 #define MAX_NODES 100000
194
195 static int len;
196 static void *datas[MAX_NODES];
197 static int depths[MAX_NODES];
198
199 /* Records the path represented by OCC, with depth incremented by DEPTH. */
200
201 static int
record_path_before_1(struct et_occ * occ,int depth)202 record_path_before_1 (struct et_occ *occ, int depth)
203 {
204 int mn, m;
205
206 depth += occ->depth;
207 mn = depth;
208
209 if (occ->prev)
210 {
211 m = record_path_before_1 (occ->prev, depth);
212 if (m < mn)
213 mn = m;
214 }
215
216 fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
217
218 gcc_assert (len < MAX_NODES);
219
220 depths[len] = depth;
221 datas[len] = occ->of;
222 len++;
223
224 if (occ->next)
225 {
226 m = record_path_before_1 (occ->next, depth);
227 if (m < mn)
228 mn = m;
229 }
230
231 gcc_assert (mn == occ->min + depth - occ->depth);
232
233 return mn;
234 }
235
236 /* Records the path represented by a tree containing OCC. */
237
238 static void
record_path_before(struct et_occ * occ)239 record_path_before (struct et_occ *occ)
240 {
241 while (occ->parent)
242 occ = occ->parent;
243
244 len = 0;
245 record_path_before_1 (occ, 0);
246 fprintf (stderr, "\n");
247 }
248
249 /* Checks whether the path represented by OCC, with depth incremented by DEPTH,
250 was not changed since the last recording. */
251
252 static int
check_path_after_1(struct et_occ * occ,int depth)253 check_path_after_1 (struct et_occ *occ, int depth)
254 {
255 int mn, m;
256
257 depth += occ->depth;
258 mn = depth;
259
260 if (occ->next)
261 {
262 m = check_path_after_1 (occ->next, depth);
263 if (m < mn)
264 mn = m;
265 }
266
267 len--;
268 gcc_assert (depths[len] == depth && datas[len] == occ->of);
269
270 if (occ->prev)
271 {
272 m = check_path_after_1 (occ->prev, depth);
273 if (m < mn)
274 mn = m;
275 }
276
277 gcc_assert (mn == occ->min + depth - occ->depth);
278
279 return mn;
280 }
281
282 /* Checks whether the path represented by a tree containing OCC was
283 not changed since the last recording. */
284
285 static void
check_path_after(struct et_occ * occ)286 check_path_after (struct et_occ *occ)
287 {
288 while (occ->parent)
289 occ = occ->parent;
290
291 check_path_after_1 (occ, 0);
292 gcc_assert (!len);
293 }
294
295 #endif
296
297 /* Splay the occurrence OCC to the root of the tree. */
298
299 static void
et_splay(struct et_occ * occ)300 et_splay (struct et_occ *occ)
301 {
302 struct et_occ *f, *gf, *ggf;
303 int occ_depth, f_depth, gf_depth;
304
305 #ifdef DEBUG_ET
306 record_path_before (occ);
307 et_check_tree_sanity (occ);
308 #endif
309
310 while (occ->parent)
311 {
312 occ_depth = occ->depth;
313
314 f = occ->parent;
315 f_depth = f->depth;
316
317 gf = f->parent;
318
319 if (!gf)
320 {
321 set_depth_add (occ, f_depth);
322 occ->min_occ = f->min_occ;
323 occ->min = f->min;
324
325 if (f->prev == occ)
326 {
327 /* zig */
328 set_prev (f, occ->next);
329 set_next (occ, f);
330 set_depth_add (f->prev, occ_depth);
331 }
332 else
333 {
334 /* zag */
335 set_next (f, occ->prev);
336 set_prev (occ, f);
337 set_depth_add (f->next, occ_depth);
338 }
339 set_depth (f, -occ_depth);
340 occ->parent = NULL;
341
342 et_recomp_min (f);
343 #ifdef DEBUG_ET
344 et_check_tree_sanity (occ);
345 check_path_after (occ);
346 #endif
347 return;
348 }
349
350 gf_depth = gf->depth;
351
352 set_depth_add (occ, f_depth + gf_depth);
353 occ->min_occ = gf->min_occ;
354 occ->min = gf->min;
355
356 ggf = gf->parent;
357
358 if (gf->prev == f)
359 {
360 if (f->prev == occ)
361 {
362 /* zig zig */
363 set_prev (gf, f->next);
364 set_prev (f, occ->next);
365 set_next (occ, f);
366 set_next (f, gf);
367
368 set_depth (f, -occ_depth);
369 set_depth_add (f->prev, occ_depth);
370 set_depth (gf, -f_depth);
371 set_depth_add (gf->prev, f_depth);
372 }
373 else
374 {
375 /* zag zig */
376 set_prev (gf, occ->next);
377 set_next (f, occ->prev);
378 set_prev (occ, f);
379 set_next (occ, gf);
380
381 set_depth (f, -occ_depth);
382 set_depth_add (f->next, occ_depth);
383 set_depth (gf, -occ_depth - f_depth);
384 set_depth_add (gf->prev, occ_depth + f_depth);
385 }
386 }
387 else
388 {
389 if (f->prev == occ)
390 {
391 /* zig zag */
392 set_next (gf, occ->prev);
393 set_prev (f, occ->next);
394 set_prev (occ, gf);
395 set_next (occ, f);
396
397 set_depth (f, -occ_depth);
398 set_depth_add (f->prev, occ_depth);
399 set_depth (gf, -occ_depth - f_depth);
400 set_depth_add (gf->next, occ_depth + f_depth);
401 }
402 else
403 {
404 /* zag zag */
405 set_next (gf, f->prev);
406 set_next (f, occ->prev);
407 set_prev (occ, f);
408 set_prev (f, gf);
409
410 set_depth (f, -occ_depth);
411 set_depth_add (f->next, occ_depth);
412 set_depth (gf, -f_depth);
413 set_depth_add (gf->next, f_depth);
414 }
415 }
416
417 occ->parent = ggf;
418 if (ggf)
419 {
420 if (ggf->prev == gf)
421 ggf->prev = occ;
422 else
423 ggf->next = occ;
424 }
425
426 et_recomp_min (gf);
427 et_recomp_min (f);
428 #ifdef DEBUG_ET
429 et_check_tree_sanity (occ);
430 #endif
431 }
432
433 #ifdef DEBUG_ET
434 et_check_sanity (occ);
435 check_path_after (occ);
436 #endif
437 }
438
439 /* Create a new et tree occurrence of NODE. */
440
441 static struct et_occ *
et_new_occ(struct et_node * node)442 et_new_occ (struct et_node *node)
443 {
444 struct et_occ *nw;
445
446 if (!et_occurrences)
447 et_occurrences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);
448 nw = (struct et_occ *) pool_alloc (et_occurrences);
449
450 nw->of = node;
451 nw->parent = NULL;
452 nw->prev = NULL;
453 nw->next = NULL;
454
455 nw->depth = 0;
456 nw->min_occ = nw;
457 nw->min = 0;
458
459 return nw;
460 }
461
462 /* Create a new et tree containing DATA. */
463
464 struct et_node *
et_new_tree(void * data)465 et_new_tree (void *data)
466 {
467 struct et_node *nw;
468
469 if (!et_nodes)
470 et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);
471 nw = (struct et_node *) pool_alloc (et_nodes);
472
473 nw->data = data;
474 nw->father = NULL;
475 nw->left = NULL;
476 nw->right = NULL;
477 nw->son = NULL;
478
479 nw->rightmost_occ = et_new_occ (nw);
480 nw->parent_occ = NULL;
481
482 return nw;
483 }
484
485 /* Releases et tree T. */
486
487 void
et_free_tree(struct et_node * t)488 et_free_tree (struct et_node *t)
489 {
490 while (t->son)
491 et_split (t->son);
492
493 if (t->father)
494 et_split (t);
495
496 pool_free (et_occurrences, t->rightmost_occ);
497 pool_free (et_nodes, t);
498 }
499
500 /* Releases et tree T without maintaining other nodes. */
501
502 void
et_free_tree_force(struct et_node * t)503 et_free_tree_force (struct et_node *t)
504 {
505 pool_free (et_occurrences, t->rightmost_occ);
506 if (t->parent_occ)
507 pool_free (et_occurrences, t->parent_occ);
508 pool_free (et_nodes, t);
509 }
510
511 /* Release the alloc pools, if they are empty. */
512
513 void
et_free_pools(void)514 et_free_pools (void)
515 {
516 free_alloc_pool_if_empty (&et_occurrences);
517 free_alloc_pool_if_empty (&et_nodes);
518 }
519
520 /* Sets father of et tree T to FATHER. */
521
522 void
et_set_father(struct et_node * t,struct et_node * father)523 et_set_father (struct et_node *t, struct et_node *father)
524 {
525 struct et_node *left, *right;
526 struct et_occ *rmost, *left_part, *new_f_occ, *p;
527
528 /* Update the path represented in the splay tree. */
529 new_f_occ = et_new_occ (father);
530
531 rmost = father->rightmost_occ;
532 et_splay (rmost);
533
534 left_part = rmost->prev;
535
536 p = t->rightmost_occ;
537 et_splay (p);
538
539 set_prev (new_f_occ, left_part);
540 set_next (new_f_occ, p);
541
542 p->depth++;
543 p->min++;
544 et_recomp_min (new_f_occ);
545
546 set_prev (rmost, new_f_occ);
547
548 if (new_f_occ->min + rmost->depth < rmost->min)
549 {
550 rmost->min = new_f_occ->min + rmost->depth;
551 rmost->min_occ = new_f_occ->min_occ;
552 }
553
554 t->parent_occ = new_f_occ;
555
556 /* Update the tree. */
557 t->father = father;
558 right = father->son;
559 if (right)
560 left = right->left;
561 else
562 left = right = t;
563
564 left->right = t;
565 right->left = t;
566 t->left = left;
567 t->right = right;
568
569 father->son = t;
570
571 #ifdef DEBUG_ET
572 et_check_tree_sanity (rmost);
573 record_path_before (rmost);
574 #endif
575 }
576
577 /* Splits the edge from T to its father. */
578
579 void
et_split(struct et_node * t)580 et_split (struct et_node *t)
581 {
582 struct et_node *father = t->father;
583 struct et_occ *r, *l, *rmost, *p_occ;
584
585 /* Update the path represented by the splay tree. */
586 rmost = t->rightmost_occ;
587 et_splay (rmost);
588
589 for (r = rmost->next; r->prev; r = r->prev)
590 continue;
591 et_splay (r);
592
593 r->prev->parent = NULL;
594 p_occ = t->parent_occ;
595 et_splay (p_occ);
596 t->parent_occ = NULL;
597
598 l = p_occ->prev;
599 p_occ->next->parent = NULL;
600
601 set_prev (r, l);
602
603 et_recomp_min (r);
604
605 et_splay (rmost);
606 rmost->depth = 0;
607 rmost->min = 0;
608
609 pool_free (et_occurrences, p_occ);
610
611 /* Update the tree. */
612 if (father->son == t)
613 father->son = t->right;
614 if (father->son == t)
615 father->son = NULL;
616 else
617 {
618 t->left->right = t->right;
619 t->right->left = t->left;
620 }
621 t->left = t->right = NULL;
622 t->father = NULL;
623
624 #ifdef DEBUG_ET
625 et_check_tree_sanity (rmost);
626 record_path_before (rmost);
627
628 et_check_tree_sanity (r);
629 record_path_before (r);
630 #endif
631 }
632
633 /* Finds the nearest common ancestor of the nodes N1 and N2. */
634
635 struct et_node *
et_nca(struct et_node * n1,struct et_node * n2)636 et_nca (struct et_node *n1, struct et_node *n2)
637 {
638 struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
639 struct et_occ *l, *r, *ret;
640 int mn;
641
642 if (n1 == n2)
643 return n1;
644
645 et_splay (o1);
646 l = o1->prev;
647 r = o1->next;
648 if (l)
649 l->parent = NULL;
650 if (r)
651 r->parent = NULL;
652 et_splay (o2);
653
654 if (l == o2 || (l && l->parent != NULL))
655 {
656 ret = o2->next;
657
658 set_prev (o1, o2);
659 if (r)
660 r->parent = o1;
661 }
662 else if (r == o2 || (r && r->parent != NULL))
663 {
664 ret = o2->prev;
665
666 set_next (o1, o2);
667 if (l)
668 l->parent = o1;
669 }
670 else
671 {
672 /* O1 and O2 are in different components of the forest. */
673 if (l)
674 l->parent = o1;
675 if (r)
676 r->parent = o1;
677 return NULL;
678 }
679
680 if (0 < o2->depth)
681 {
682 om = o1;
683 mn = o1->depth;
684 }
685 else
686 {
687 om = o2;
688 mn = o2->depth + o1->depth;
689 }
690
691 #ifdef DEBUG_ET
692 et_check_tree_sanity (o2);
693 #endif
694
695 if (ret && ret->min + o1->depth + o2->depth < mn)
696 return ret->min_occ->of;
697 else
698 return om->of;
699 }
700
701 /* Checks whether the node UP is an ancestor of the node DOWN. */
702
703 bool
et_below(struct et_node * down,struct et_node * up)704 et_below (struct et_node *down, struct et_node *up)
705 {
706 struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
707 struct et_occ *l, *r;
708
709 if (up == down)
710 return true;
711
712 et_splay (u);
713 l = u->prev;
714 r = u->next;
715
716 if (!l)
717 return false;
718
719 l->parent = NULL;
720
721 if (r)
722 r->parent = NULL;
723
724 et_splay (d);
725
726 if (l == d || l->parent != NULL)
727 {
728 if (r)
729 r->parent = u;
730 set_prev (u, d);
731 #ifdef DEBUG_ET
732 et_check_tree_sanity (u);
733 #endif
734 }
735 else
736 {
737 l->parent = u;
738
739 /* In case O1 and O2 are in two different trees, we must just restore the
740 original state. */
741 if (r && r->parent != NULL)
742 set_next (u, d);
743 else
744 set_next (u, r);
745
746 #ifdef DEBUG_ET
747 et_check_tree_sanity (u);
748 #endif
749 return false;
750 }
751
752 if (0 >= d->depth)
753 return false;
754
755 return !d->next || d->next->min + d->depth >= 0;
756 }
757
758 /* Returns the root of the tree that contains NODE. */
759
760 struct et_node *
et_root(struct et_node * node)761 et_root (struct et_node *node)
762 {
763 struct et_occ *occ = node->rightmost_occ, *r;
764
765 /* The root of the tree corresponds to the rightmost occurrence in the
766 represented path. */
767 et_splay (occ);
768 for (r = occ; r->next; r = r->next)
769 continue;
770 et_splay (r);
771
772 return r->of;
773 }
774