* omp-low.c (MASK_GANG, MASK_WORKER, MASK_VECTOR): Delete.
[official-gcc.git] / gcc / et-forest.c
blobbf2f7656ed29ed1c6c65c49ccbd55d3919bc5a96
1 /* ET-trees data structure implementation.
2 Contributed by Pavel Nejedly
3 Copyright (C) 2002-2015 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 "alloc-pool.h"
29 #include "et-forest.h"
31 /* We do not enable this with CHECKING_P, since it is awfully slow. */
32 #undef DEBUG_ET
34 #ifdef DEBUG_ET
35 #include "backend.h"
36 #include "hard-reg-set.h"
37 #endif
39 /* The occurrence of a node in the et tree. */
40 struct et_occ
42 struct et_node *of; /* The node. */
44 struct et_occ *parent; /* Parent in the splay-tree. */
45 struct et_occ *prev; /* Left son in the splay-tree. */
46 struct et_occ *next; /* Right son in the splay-tree. */
48 int depth; /* The depth of the node is the sum of depth
49 fields on the path to the root. */
50 int min; /* The minimum value of the depth in the subtree
51 is obtained by adding sum of depth fields
52 on the path to the root. */
53 struct et_occ *min_occ; /* The occurrence in the subtree with the minimal
54 depth. */
57 static object_allocator<et_node> et_nodes ("et_nodes pool");
58 static object_allocator<et_occ> et_occurrences ("et_occ pool");
60 /* Changes depth of OCC to D. */
62 static inline void
63 set_depth (struct et_occ *occ, int d)
65 if (!occ)
66 return;
68 occ->min += d - occ->depth;
69 occ->depth = d;
72 /* Adds D to the depth of OCC. */
74 static inline void
75 set_depth_add (struct et_occ *occ, int d)
77 if (!occ)
78 return;
80 occ->min += d;
81 occ->depth += d;
84 /* Sets prev field of OCC to P. */
86 static inline void
87 set_prev (struct et_occ *occ, struct et_occ *t)
89 #ifdef DEBUG_ET
90 gcc_assert (occ != t);
91 #endif
93 occ->prev = t;
94 if (t)
95 t->parent = occ;
98 /* Sets next field of OCC to P. */
100 static inline void
101 set_next (struct et_occ *occ, struct et_occ *t)
103 #ifdef DEBUG_ET
104 gcc_assert (occ != t);
105 #endif
107 occ->next = t;
108 if (t)
109 t->parent = occ;
112 /* Recompute minimum for occurrence OCC. */
114 static inline void
115 et_recomp_min (struct et_occ *occ)
117 struct et_occ *mson = occ->prev;
119 if (!mson
120 || (occ->next
121 && mson->min > occ->next->min))
122 mson = occ->next;
124 if (mson && mson->min < 0)
126 occ->min = mson->min + occ->depth;
127 occ->min_occ = mson->min_occ;
129 else
131 occ->min = occ->depth;
132 occ->min_occ = occ;
136 #ifdef DEBUG_ET
137 /* Checks whether neighborhood of OCC seems sane. */
139 static void
140 et_check_occ_sanity (struct et_occ *occ)
142 if (!occ)
143 return;
145 gcc_assert (occ->parent != occ);
146 gcc_assert (occ->prev != occ);
147 gcc_assert (occ->next != occ);
148 gcc_assert (!occ->next || occ->next != occ->prev);
150 if (occ->next)
152 gcc_assert (occ->next != occ->parent);
153 gcc_assert (occ->next->parent == occ);
156 if (occ->prev)
158 gcc_assert (occ->prev != occ->parent);
159 gcc_assert (occ->prev->parent == occ);
162 gcc_assert (!occ->parent
163 || occ->parent->prev == occ
164 || occ->parent->next == occ);
167 /* Checks whether tree rooted at OCC is sane. */
169 static void
170 et_check_sanity (struct et_occ *occ)
172 et_check_occ_sanity (occ);
173 if (occ->prev)
174 et_check_sanity (occ->prev);
175 if (occ->next)
176 et_check_sanity (occ->next);
179 /* Checks whether tree containing OCC is sane. */
181 static void
182 et_check_tree_sanity (struct et_occ *occ)
184 while (occ->parent)
185 occ = occ->parent;
187 et_check_sanity (occ);
190 /* For recording the paths. */
192 /* An ad-hoc constant; if the function has more blocks, this won't work,
193 but since it is used for debugging only, it does not matter. */
194 #define MAX_NODES 100000
196 static int len;
197 static void *datas[MAX_NODES];
198 static int depths[MAX_NODES];
200 /* Records the path represented by OCC, with depth incremented by DEPTH. */
202 static int
203 record_path_before_1 (struct et_occ *occ, int depth)
205 int mn, m;
207 depth += occ->depth;
208 mn = depth;
210 if (occ->prev)
212 m = record_path_before_1 (occ->prev, depth);
213 if (m < mn)
214 mn = m;
217 fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
219 gcc_assert (len < MAX_NODES);
221 depths[len] = depth;
222 datas[len] = occ->of;
223 len++;
225 if (occ->next)
227 m = record_path_before_1 (occ->next, depth);
228 if (m < mn)
229 mn = m;
232 gcc_assert (mn == occ->min + depth - occ->depth);
234 return mn;
237 /* Records the path represented by a tree containing OCC. */
239 static void
240 record_path_before (struct et_occ *occ)
242 while (occ->parent)
243 occ = occ->parent;
245 len = 0;
246 record_path_before_1 (occ, 0);
247 fprintf (stderr, "\n");
250 /* Checks whether the path represented by OCC, with depth incremented by DEPTH,
251 was not changed since the last recording. */
253 static int
254 check_path_after_1 (struct et_occ *occ, int depth)
256 int mn, m;
258 depth += occ->depth;
259 mn = depth;
261 if (occ->next)
263 m = check_path_after_1 (occ->next, depth);
264 if (m < mn)
265 mn = m;
268 len--;
269 gcc_assert (depths[len] == depth && datas[len] == occ->of);
271 if (occ->prev)
273 m = check_path_after_1 (occ->prev, depth);
274 if (m < mn)
275 mn = m;
278 gcc_assert (mn == occ->min + depth - occ->depth);
280 return mn;
283 /* Checks whether the path represented by a tree containing OCC was
284 not changed since the last recording. */
286 static void
287 check_path_after (struct et_occ *occ)
289 while (occ->parent)
290 occ = occ->parent;
292 check_path_after_1 (occ, 0);
293 gcc_assert (!len);
296 #endif
298 /* Splay the occurrence OCC to the root of the tree. */
300 static void
301 et_splay (struct et_occ *occ)
303 struct et_occ *f, *gf, *ggf;
304 int occ_depth, f_depth, gf_depth;
306 #ifdef DEBUG_ET
307 record_path_before (occ);
308 et_check_tree_sanity (occ);
309 #endif
311 while (occ->parent)
313 occ_depth = occ->depth;
315 f = occ->parent;
316 f_depth = f->depth;
318 gf = f->parent;
320 if (!gf)
322 set_depth_add (occ, f_depth);
323 occ->min_occ = f->min_occ;
324 occ->min = f->min;
326 if (f->prev == occ)
328 /* zig */
329 set_prev (f, occ->next);
330 set_next (occ, f);
331 set_depth_add (f->prev, occ_depth);
333 else
335 /* zag */
336 set_next (f, occ->prev);
337 set_prev (occ, f);
338 set_depth_add (f->next, occ_depth);
340 set_depth (f, -occ_depth);
341 occ->parent = NULL;
343 et_recomp_min (f);
344 #ifdef DEBUG_ET
345 et_check_tree_sanity (occ);
346 check_path_after (occ);
347 #endif
348 return;
351 gf_depth = gf->depth;
353 set_depth_add (occ, f_depth + gf_depth);
354 occ->min_occ = gf->min_occ;
355 occ->min = gf->min;
357 ggf = gf->parent;
359 if (gf->prev == f)
361 if (f->prev == occ)
363 /* zig zig */
364 set_prev (gf, f->next);
365 set_prev (f, occ->next);
366 set_next (occ, f);
367 set_next (f, gf);
369 set_depth (f, -occ_depth);
370 set_depth_add (f->prev, occ_depth);
371 set_depth (gf, -f_depth);
372 set_depth_add (gf->prev, f_depth);
374 else
376 /* zag zig */
377 set_prev (gf, occ->next);
378 set_next (f, occ->prev);
379 set_prev (occ, f);
380 set_next (occ, gf);
382 set_depth (f, -occ_depth);
383 set_depth_add (f->next, occ_depth);
384 set_depth (gf, -occ_depth - f_depth);
385 set_depth_add (gf->prev, occ_depth + f_depth);
388 else
390 if (f->prev == occ)
392 /* zig zag */
393 set_next (gf, occ->prev);
394 set_prev (f, occ->next);
395 set_prev (occ, gf);
396 set_next (occ, f);
398 set_depth (f, -occ_depth);
399 set_depth_add (f->prev, occ_depth);
400 set_depth (gf, -occ_depth - f_depth);
401 set_depth_add (gf->next, occ_depth + f_depth);
403 else
405 /* zag zag */
406 set_next (gf, f->prev);
407 set_next (f, occ->prev);
408 set_prev (occ, f);
409 set_prev (f, gf);
411 set_depth (f, -occ_depth);
412 set_depth_add (f->next, occ_depth);
413 set_depth (gf, -f_depth);
414 set_depth_add (gf->next, f_depth);
418 occ->parent = ggf;
419 if (ggf)
421 if (ggf->prev == gf)
422 ggf->prev = occ;
423 else
424 ggf->next = occ;
427 et_recomp_min (gf);
428 et_recomp_min (f);
429 #ifdef DEBUG_ET
430 et_check_tree_sanity (occ);
431 #endif
434 #ifdef DEBUG_ET
435 et_check_sanity (occ);
436 check_path_after (occ);
437 #endif
440 /* Create a new et tree occurrence of NODE. */
442 static struct et_occ *
443 et_new_occ (struct et_node *node)
445 et_occ *nw = et_occurrences.allocate ();
447 nw->of = node;
448 nw->parent = NULL;
449 nw->prev = NULL;
450 nw->next = NULL;
452 nw->depth = 0;
453 nw->min_occ = nw;
454 nw->min = 0;
456 return nw;
459 /* Create a new et tree containing DATA. */
461 struct et_node *
462 et_new_tree (void *data)
464 et_node *nw = et_nodes.allocate ();
466 nw->data = data;
467 nw->father = NULL;
468 nw->left = NULL;
469 nw->right = NULL;
470 nw->son = NULL;
472 nw->rightmost_occ = et_new_occ (nw);
473 nw->parent_occ = NULL;
475 return nw;
478 /* Releases et tree T. */
480 void
481 et_free_tree (struct et_node *t)
483 while (t->son)
484 et_split (t->son);
486 if (t->father)
487 et_split (t);
489 et_occurrences.remove (t->rightmost_occ);
490 et_nodes.remove (t);
493 /* Releases et tree T without maintaining other nodes. */
495 void
496 et_free_tree_force (struct et_node *t)
498 et_occurrences.remove (t->rightmost_occ);
499 if (t->parent_occ)
500 et_occurrences.remove (t->parent_occ);
501 et_nodes.remove (t);
504 /* Release the alloc pools, if they are empty. */
506 void
507 et_free_pools (void)
509 et_occurrences.release_if_empty ();
510 et_nodes.release_if_empty ();
513 /* Sets father of et tree T to FATHER. */
515 void
516 et_set_father (struct et_node *t, struct et_node *father)
518 struct et_node *left, *right;
519 struct et_occ *rmost, *left_part, *new_f_occ, *p;
521 /* Update the path represented in the splay tree. */
522 new_f_occ = et_new_occ (father);
524 rmost = father->rightmost_occ;
525 et_splay (rmost);
527 left_part = rmost->prev;
529 p = t->rightmost_occ;
530 et_splay (p);
532 set_prev (new_f_occ, left_part);
533 set_next (new_f_occ, p);
535 p->depth++;
536 p->min++;
537 et_recomp_min (new_f_occ);
539 set_prev (rmost, new_f_occ);
541 if (new_f_occ->min + rmost->depth < rmost->min)
543 rmost->min = new_f_occ->min + rmost->depth;
544 rmost->min_occ = new_f_occ->min_occ;
547 t->parent_occ = new_f_occ;
549 /* Update the tree. */
550 t->father = father;
551 right = father->son;
552 if (right)
553 left = right->left;
554 else
555 left = right = t;
557 left->right = t;
558 right->left = t;
559 t->left = left;
560 t->right = right;
562 father->son = t;
564 #ifdef DEBUG_ET
565 et_check_tree_sanity (rmost);
566 record_path_before (rmost);
567 #endif
570 /* Splits the edge from T to its father. */
572 void
573 et_split (struct et_node *t)
575 struct et_node *father = t->father;
576 struct et_occ *r, *l, *rmost, *p_occ;
578 /* Update the path represented by the splay tree. */
579 rmost = t->rightmost_occ;
580 et_splay (rmost);
582 for (r = rmost->next; r->prev; r = r->prev)
583 continue;
584 et_splay (r);
586 r->prev->parent = NULL;
587 p_occ = t->parent_occ;
588 et_splay (p_occ);
589 t->parent_occ = NULL;
591 l = p_occ->prev;
592 p_occ->next->parent = NULL;
594 set_prev (r, l);
596 et_recomp_min (r);
598 et_splay (rmost);
599 rmost->depth = 0;
600 rmost->min = 0;
602 et_occurrences.remove (p_occ);
604 /* Update the tree. */
605 if (father->son == t)
606 father->son = t->right;
607 if (father->son == t)
608 father->son = NULL;
609 else
611 t->left->right = t->right;
612 t->right->left = t->left;
614 t->left = t->right = NULL;
615 t->father = NULL;
617 #ifdef DEBUG_ET
618 et_check_tree_sanity (rmost);
619 record_path_before (rmost);
621 et_check_tree_sanity (r);
622 record_path_before (r);
623 #endif
626 /* Finds the nearest common ancestor of the nodes N1 and N2. */
628 struct et_node *
629 et_nca (struct et_node *n1, struct et_node *n2)
631 struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
632 struct et_occ *l, *r, *ret;
633 int mn;
635 if (n1 == n2)
636 return n1;
638 et_splay (o1);
639 l = o1->prev;
640 r = o1->next;
641 if (l)
642 l->parent = NULL;
643 if (r)
644 r->parent = NULL;
645 et_splay (o2);
647 if (l == o2 || (l && l->parent != NULL))
649 ret = o2->next;
651 set_prev (o1, o2);
652 if (r)
653 r->parent = o1;
655 else if (r == o2 || (r && r->parent != NULL))
657 ret = o2->prev;
659 set_next (o1, o2);
660 if (l)
661 l->parent = o1;
663 else
665 /* O1 and O2 are in different components of the forest. */
666 if (l)
667 l->parent = o1;
668 if (r)
669 r->parent = o1;
670 return NULL;
673 if (0 < o2->depth)
675 om = o1;
676 mn = o1->depth;
678 else
680 om = o2;
681 mn = o2->depth + o1->depth;
684 #ifdef DEBUG_ET
685 et_check_tree_sanity (o2);
686 #endif
688 if (ret && ret->min + o1->depth + o2->depth < mn)
689 return ret->min_occ->of;
690 else
691 return om->of;
694 /* Checks whether the node UP is an ancestor of the node DOWN. */
696 bool
697 et_below (struct et_node *down, struct et_node *up)
699 struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
700 struct et_occ *l, *r;
702 if (up == down)
703 return true;
705 et_splay (u);
706 l = u->prev;
707 r = u->next;
709 if (!l)
710 return false;
712 l->parent = NULL;
714 if (r)
715 r->parent = NULL;
717 et_splay (d);
719 if (l == d || l->parent != NULL)
721 if (r)
722 r->parent = u;
723 set_prev (u, d);
724 #ifdef DEBUG_ET
725 et_check_tree_sanity (u);
726 #endif
728 else
730 l->parent = u;
732 /* In case O1 and O2 are in two different trees, we must just restore the
733 original state. */
734 if (r && r->parent != NULL)
735 set_next (u, d);
736 else
737 set_next (u, r);
739 #ifdef DEBUG_ET
740 et_check_tree_sanity (u);
741 #endif
742 return false;
745 if (0 >= d->depth)
746 return false;
748 return !d->next || d->next->min + d->depth >= 0;
751 /* Returns the root of the tree that contains NODE. */
753 struct et_node *
754 et_root (struct et_node *node)
756 struct et_occ *occ = node->rightmost_occ, *r;
758 /* The root of the tree corresponds to the rightmost occurrence in the
759 represented path. */
760 et_splay (occ);
761 for (r = occ; r->next; r = r->next)
762 continue;
763 et_splay (r);
765 return r->of;