Daily bump.
[official-gcc.git] / gcc / et-forest.c
blob4d18861d40dc3656631494909ef5b2137b9955e6
1 /* ET-trees data structure implementation.
2 Contributed by Pavel Nejedly
3 Copyright (C) 2002-2014 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.
25 #include "config.h"
26 #include "system.h"
27 #include "coretypes.h"
28 #include "et-forest.h"
29 #include "alloc-pool.h"
31 /* We do not enable this with ENABLE_CHECKING, since it is awfully slow. */
32 #undef DEBUG_ET
34 #ifdef DEBUG_ET
35 #include "vec.h"
36 #include "hashtab.h"
37 #include "hash-set.h"
38 #include "machmode.h"
39 #include "tm.h"
40 #include "hard-reg-set.h"
41 #include "input.h"
42 #include "function.h"
43 #include "basic-block.h"
44 #endif
46 /* The occurrence of a node in the et tree. */
47 struct et_occ
49 struct et_node *of; /* The node. */
51 struct et_occ *parent; /* Parent in the splay-tree. */
52 struct et_occ *prev; /* Left son in the splay-tree. */
53 struct et_occ *next; /* Right son in the splay-tree. */
55 int depth; /* The depth of the node is the sum of depth
56 fields on the path to the root. */
57 int min; /* The minimum value of the depth in the subtree
58 is obtained by adding sum of depth fields
59 on the path to the root. */
60 struct et_occ *min_occ; /* The occurrence in the subtree with the minimal
61 depth. */
64 static alloc_pool et_nodes;
65 static alloc_pool et_occurrences;
67 /* Changes depth of OCC to D. */
69 static inline void
70 set_depth (struct et_occ *occ, int d)
72 if (!occ)
73 return;
75 occ->min += d - occ->depth;
76 occ->depth = d;
79 /* Adds D to the depth of OCC. */
81 static inline void
82 set_depth_add (struct et_occ *occ, int d)
84 if (!occ)
85 return;
87 occ->min += d;
88 occ->depth += d;
91 /* Sets prev field of OCC to P. */
93 static inline void
94 set_prev (struct et_occ *occ, struct et_occ *t)
96 #ifdef DEBUG_ET
97 gcc_assert (occ != t);
98 #endif
100 occ->prev = t;
101 if (t)
102 t->parent = occ;
105 /* Sets next field of OCC to P. */
107 static inline void
108 set_next (struct et_occ *occ, struct et_occ *t)
110 #ifdef DEBUG_ET
111 gcc_assert (occ != t);
112 #endif
114 occ->next = t;
115 if (t)
116 t->parent = occ;
119 /* Recompute minimum for occurrence OCC. */
121 static inline void
122 et_recomp_min (struct et_occ *occ)
124 struct et_occ *mson = occ->prev;
126 if (!mson
127 || (occ->next
128 && mson->min > occ->next->min))
129 mson = occ->next;
131 if (mson && mson->min < 0)
133 occ->min = mson->min + occ->depth;
134 occ->min_occ = mson->min_occ;
136 else
138 occ->min = occ->depth;
139 occ->min_occ = occ;
143 #ifdef DEBUG_ET
144 /* Checks whether neighborhood of OCC seems sane. */
146 static void
147 et_check_occ_sanity (struct et_occ *occ)
149 if (!occ)
150 return;
152 gcc_assert (occ->parent != occ);
153 gcc_assert (occ->prev != occ);
154 gcc_assert (occ->next != occ);
155 gcc_assert (!occ->next || occ->next != occ->prev);
157 if (occ->next)
159 gcc_assert (occ->next != occ->parent);
160 gcc_assert (occ->next->parent == occ);
163 if (occ->prev)
165 gcc_assert (occ->prev != occ->parent);
166 gcc_assert (occ->prev->parent == occ);
169 gcc_assert (!occ->parent
170 || occ->parent->prev == occ
171 || occ->parent->next == occ);
174 /* Checks whether tree rooted at OCC is sane. */
176 static void
177 et_check_sanity (struct et_occ *occ)
179 et_check_occ_sanity (occ);
180 if (occ->prev)
181 et_check_sanity (occ->prev);
182 if (occ->next)
183 et_check_sanity (occ->next);
186 /* Checks whether tree containing OCC is sane. */
188 static void
189 et_check_tree_sanity (struct et_occ *occ)
191 while (occ->parent)
192 occ = occ->parent;
194 et_check_sanity (occ);
197 /* For recording the paths. */
199 /* An ad-hoc constant; if the function has more blocks, this won't work,
200 but since it is used for debugging only, it does not matter. */
201 #define MAX_NODES 100000
203 static int len;
204 static void *datas[MAX_NODES];
205 static int depths[MAX_NODES];
207 /* Records the path represented by OCC, with depth incremented by DEPTH. */
209 static int
210 record_path_before_1 (struct et_occ *occ, int depth)
212 int mn, m;
214 depth += occ->depth;
215 mn = depth;
217 if (occ->prev)
219 m = record_path_before_1 (occ->prev, depth);
220 if (m < mn)
221 mn = m;
224 fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
226 gcc_assert (len < MAX_NODES);
228 depths[len] = depth;
229 datas[len] = occ->of;
230 len++;
232 if (occ->next)
234 m = record_path_before_1 (occ->next, depth);
235 if (m < mn)
236 mn = m;
239 gcc_assert (mn == occ->min + depth - occ->depth);
241 return mn;
244 /* Records the path represented by a tree containing OCC. */
246 static void
247 record_path_before (struct et_occ *occ)
249 while (occ->parent)
250 occ = occ->parent;
252 len = 0;
253 record_path_before_1 (occ, 0);
254 fprintf (stderr, "\n");
257 /* Checks whether the path represented by OCC, with depth incremented by DEPTH,
258 was not changed since the last recording. */
260 static int
261 check_path_after_1 (struct et_occ *occ, int depth)
263 int mn, m;
265 depth += occ->depth;
266 mn = depth;
268 if (occ->next)
270 m = check_path_after_1 (occ->next, depth);
271 if (m < mn)
272 mn = m;
275 len--;
276 gcc_assert (depths[len] == depth && datas[len] == occ->of);
278 if (occ->prev)
280 m = check_path_after_1 (occ->prev, depth);
281 if (m < mn)
282 mn = m;
285 gcc_assert (mn == occ->min + depth - occ->depth);
287 return mn;
290 /* Checks whether the path represented by a tree containing OCC was
291 not changed since the last recording. */
293 static void
294 check_path_after (struct et_occ *occ)
296 while (occ->parent)
297 occ = occ->parent;
299 check_path_after_1 (occ, 0);
300 gcc_assert (!len);
303 #endif
305 /* Splay the occurrence OCC to the root of the tree. */
307 static void
308 et_splay (struct et_occ *occ)
310 struct et_occ *f, *gf, *ggf;
311 int occ_depth, f_depth, gf_depth;
313 #ifdef DEBUG_ET
314 record_path_before (occ);
315 et_check_tree_sanity (occ);
316 #endif
318 while (occ->parent)
320 occ_depth = occ->depth;
322 f = occ->parent;
323 f_depth = f->depth;
325 gf = f->parent;
327 if (!gf)
329 set_depth_add (occ, f_depth);
330 occ->min_occ = f->min_occ;
331 occ->min = f->min;
333 if (f->prev == occ)
335 /* zig */
336 set_prev (f, occ->next);
337 set_next (occ, f);
338 set_depth_add (f->prev, occ_depth);
340 else
342 /* zag */
343 set_next (f, occ->prev);
344 set_prev (occ, f);
345 set_depth_add (f->next, occ_depth);
347 set_depth (f, -occ_depth);
348 occ->parent = NULL;
350 et_recomp_min (f);
351 #ifdef DEBUG_ET
352 et_check_tree_sanity (occ);
353 check_path_after (occ);
354 #endif
355 return;
358 gf_depth = gf->depth;
360 set_depth_add (occ, f_depth + gf_depth);
361 occ->min_occ = gf->min_occ;
362 occ->min = gf->min;
364 ggf = gf->parent;
366 if (gf->prev == f)
368 if (f->prev == occ)
370 /* zig zig */
371 set_prev (gf, f->next);
372 set_prev (f, occ->next);
373 set_next (occ, f);
374 set_next (f, gf);
376 set_depth (f, -occ_depth);
377 set_depth_add (f->prev, occ_depth);
378 set_depth (gf, -f_depth);
379 set_depth_add (gf->prev, f_depth);
381 else
383 /* zag zig */
384 set_prev (gf, occ->next);
385 set_next (f, occ->prev);
386 set_prev (occ, f);
387 set_next (occ, gf);
389 set_depth (f, -occ_depth);
390 set_depth_add (f->next, occ_depth);
391 set_depth (gf, -occ_depth - f_depth);
392 set_depth_add (gf->prev, occ_depth + f_depth);
395 else
397 if (f->prev == occ)
399 /* zig zag */
400 set_next (gf, occ->prev);
401 set_prev (f, occ->next);
402 set_prev (occ, gf);
403 set_next (occ, f);
405 set_depth (f, -occ_depth);
406 set_depth_add (f->prev, occ_depth);
407 set_depth (gf, -occ_depth - f_depth);
408 set_depth_add (gf->next, occ_depth + f_depth);
410 else
412 /* zag zag */
413 set_next (gf, f->prev);
414 set_next (f, occ->prev);
415 set_prev (occ, f);
416 set_prev (f, gf);
418 set_depth (f, -occ_depth);
419 set_depth_add (f->next, occ_depth);
420 set_depth (gf, -f_depth);
421 set_depth_add (gf->next, f_depth);
425 occ->parent = ggf;
426 if (ggf)
428 if (ggf->prev == gf)
429 ggf->prev = occ;
430 else
431 ggf->next = occ;
434 et_recomp_min (gf);
435 et_recomp_min (f);
436 #ifdef DEBUG_ET
437 et_check_tree_sanity (occ);
438 #endif
441 #ifdef DEBUG_ET
442 et_check_sanity (occ);
443 check_path_after (occ);
444 #endif
447 /* Create a new et tree occurrence of NODE. */
449 static struct et_occ *
450 et_new_occ (struct et_node *node)
452 struct et_occ *nw;
454 if (!et_occurrences)
455 et_occurrences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);
456 nw = (struct et_occ *) pool_alloc (et_occurrences);
458 nw->of = node;
459 nw->parent = NULL;
460 nw->prev = NULL;
461 nw->next = NULL;
463 nw->depth = 0;
464 nw->min_occ = nw;
465 nw->min = 0;
467 return nw;
470 /* Create a new et tree containing DATA. */
472 struct et_node *
473 et_new_tree (void *data)
475 struct et_node *nw;
477 if (!et_nodes)
478 et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);
479 nw = (struct et_node *) pool_alloc (et_nodes);
481 nw->data = data;
482 nw->father = NULL;
483 nw->left = NULL;
484 nw->right = NULL;
485 nw->son = NULL;
487 nw->rightmost_occ = et_new_occ (nw);
488 nw->parent_occ = NULL;
490 return nw;
493 /* Releases et tree T. */
495 void
496 et_free_tree (struct et_node *t)
498 while (t->son)
499 et_split (t->son);
501 if (t->father)
502 et_split (t);
504 pool_free (et_occurrences, t->rightmost_occ);
505 pool_free (et_nodes, t);
508 /* Releases et tree T without maintaining other nodes. */
510 void
511 et_free_tree_force (struct et_node *t)
513 pool_free (et_occurrences, t->rightmost_occ);
514 if (t->parent_occ)
515 pool_free (et_occurrences, t->parent_occ);
516 pool_free (et_nodes, t);
519 /* Release the alloc pools, if they are empty. */
521 void
522 et_free_pools (void)
524 free_alloc_pool_if_empty (&et_occurrences);
525 free_alloc_pool_if_empty (&et_nodes);
528 /* Sets father of et tree T to FATHER. */
530 void
531 et_set_father (struct et_node *t, struct et_node *father)
533 struct et_node *left, *right;
534 struct et_occ *rmost, *left_part, *new_f_occ, *p;
536 /* Update the path represented in the splay tree. */
537 new_f_occ = et_new_occ (father);
539 rmost = father->rightmost_occ;
540 et_splay (rmost);
542 left_part = rmost->prev;
544 p = t->rightmost_occ;
545 et_splay (p);
547 set_prev (new_f_occ, left_part);
548 set_next (new_f_occ, p);
550 p->depth++;
551 p->min++;
552 et_recomp_min (new_f_occ);
554 set_prev (rmost, new_f_occ);
556 if (new_f_occ->min + rmost->depth < rmost->min)
558 rmost->min = new_f_occ->min + rmost->depth;
559 rmost->min_occ = new_f_occ->min_occ;
562 t->parent_occ = new_f_occ;
564 /* Update the tree. */
565 t->father = father;
566 right = father->son;
567 if (right)
568 left = right->left;
569 else
570 left = right = t;
572 left->right = t;
573 right->left = t;
574 t->left = left;
575 t->right = right;
577 father->son = t;
579 #ifdef DEBUG_ET
580 et_check_tree_sanity (rmost);
581 record_path_before (rmost);
582 #endif
585 /* Splits the edge from T to its father. */
587 void
588 et_split (struct et_node *t)
590 struct et_node *father = t->father;
591 struct et_occ *r, *l, *rmost, *p_occ;
593 /* Update the path represented by the splay tree. */
594 rmost = t->rightmost_occ;
595 et_splay (rmost);
597 for (r = rmost->next; r->prev; r = r->prev)
598 continue;
599 et_splay (r);
601 r->prev->parent = NULL;
602 p_occ = t->parent_occ;
603 et_splay (p_occ);
604 t->parent_occ = NULL;
606 l = p_occ->prev;
607 p_occ->next->parent = NULL;
609 set_prev (r, l);
611 et_recomp_min (r);
613 et_splay (rmost);
614 rmost->depth = 0;
615 rmost->min = 0;
617 pool_free (et_occurrences, p_occ);
619 /* Update the tree. */
620 if (father->son == t)
621 father->son = t->right;
622 if (father->son == t)
623 father->son = NULL;
624 else
626 t->left->right = t->right;
627 t->right->left = t->left;
629 t->left = t->right = NULL;
630 t->father = NULL;
632 #ifdef DEBUG_ET
633 et_check_tree_sanity (rmost);
634 record_path_before (rmost);
636 et_check_tree_sanity (r);
637 record_path_before (r);
638 #endif
641 /* Finds the nearest common ancestor of the nodes N1 and N2. */
643 struct et_node *
644 et_nca (struct et_node *n1, struct et_node *n2)
646 struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
647 struct et_occ *l, *r, *ret;
648 int mn;
650 if (n1 == n2)
651 return n1;
653 et_splay (o1);
654 l = o1->prev;
655 r = o1->next;
656 if (l)
657 l->parent = NULL;
658 if (r)
659 r->parent = NULL;
660 et_splay (o2);
662 if (l == o2 || (l && l->parent != NULL))
664 ret = o2->next;
666 set_prev (o1, o2);
667 if (r)
668 r->parent = o1;
670 else if (r == o2 || (r && r->parent != NULL))
672 ret = o2->prev;
674 set_next (o1, o2);
675 if (l)
676 l->parent = o1;
678 else
680 /* O1 and O2 are in different components of the forest. */
681 if (l)
682 l->parent = o1;
683 if (r)
684 r->parent = o1;
685 return NULL;
688 if (0 < o2->depth)
690 om = o1;
691 mn = o1->depth;
693 else
695 om = o2;
696 mn = o2->depth + o1->depth;
699 #ifdef DEBUG_ET
700 et_check_tree_sanity (o2);
701 #endif
703 if (ret && ret->min + o1->depth + o2->depth < mn)
704 return ret->min_occ->of;
705 else
706 return om->of;
709 /* Checks whether the node UP is an ancestor of the node DOWN. */
711 bool
712 et_below (struct et_node *down, struct et_node *up)
714 struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
715 struct et_occ *l, *r;
717 if (up == down)
718 return true;
720 et_splay (u);
721 l = u->prev;
722 r = u->next;
724 if (!l)
725 return false;
727 l->parent = NULL;
729 if (r)
730 r->parent = NULL;
732 et_splay (d);
734 if (l == d || l->parent != NULL)
736 if (r)
737 r->parent = u;
738 set_prev (u, d);
739 #ifdef DEBUG_ET
740 et_check_tree_sanity (u);
741 #endif
743 else
745 l->parent = u;
747 /* In case O1 and O2 are in two different trees, we must just restore the
748 original state. */
749 if (r && r->parent != NULL)
750 set_next (u, d);
751 else
752 set_next (u, r);
754 #ifdef DEBUG_ET
755 et_check_tree_sanity (u);
756 #endif
757 return false;
760 if (0 >= d->depth)
761 return false;
763 return !d->next || d->next->min + d->depth >= 0;
766 /* Returns the root of the tree that contains NODE. */
768 struct et_node *
769 et_root (struct et_node *node)
771 struct et_occ *occ = node->rightmost_occ, *r;
773 /* The root of the tree corresponds to the rightmost occurrence in the
774 represented path. */
775 et_splay (occ);
776 for (r = occ; r->next; r = r->next)
777 continue;
778 et_splay (r);
780 return r->of;