Mercurial > hg > CbC > CbC_gcc

comparison gcc/et-forest.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
1 /* ET-trees data structure implementation.
2 Contributed by Pavel Nejedly
3 Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008 Free Software
4 Foundation, Inc.
5
6 This file is part of the libiberty library.
7 Libiberty is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Library General Public
9 License as published by the Free Software Foundation; either
10 version 3 of the License, or (at your option) any later version.
11
12 Libiberty is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Library General Public License for more details.
16
17 You should have received a copy of the GNU Library General Public
18 License along with libiberty; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>.
20
21 The ET-forest structure is described in:
22 D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
23 J. G'omput. System Sci., 26(3):362 381, 1983.
24 */
25
26 #include "config.h"
27 #include "system.h"
28 #include "coretypes.h"
29 #include "tm.h"
30 #include "et-forest.h"
31 #include "alloc-pool.h"
32
33 /* We do not enable this with ENABLE_CHECKING, since it is awfully slow. */
34 #undef DEBUG_ET
35
36 #ifdef DEBUG_ET
37 #include "basic-block.h"
38 #endif
39
40 /* The occurrence of a node in the et tree. */
41 struct 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
58 static alloc_pool et_nodes;
59 static alloc_pool et_occurrences;
60
61 /* Changes depth of OCC to D. */
62
63 static inline void
64 set_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
75 static inline void
76 set_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
87 static inline void
88 set_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
101 static inline void
102 set_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
115 static inline void
116 et_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
140 static void
141 et_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
170 static void
171 et_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
182 static void
183 et_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
197 static int len;
198 static void *datas[MAX_NODES];
199 static int depths[MAX_NODES];
200
201 /* Records the path represented by OCC, with depth incremented by DEPTH. */
202
203 static int
204 record_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
240 static void
241 record_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
254 static int
255 check_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
287 static void
288 check_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
301 static void
302 et_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
443 static struct et_occ *
444 et_new_occ (struct et_node *node)
445 {
446 struct et_occ *nw;
447
448 if (!et_occurrences)
449 et_occurrences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);
450 nw = (struct et_occ *) pool_alloc (et_occurrences);
451
452 nw->of = node;
453 nw->parent = NULL;
454 nw->prev = NULL;
455 nw->next = NULL;
456
457 nw->depth = 0;
458 nw->min_occ = nw;
459 nw->min = 0;
460
461 return nw;
462 }
463
464 /* Create a new et tree containing DATA. */
465
466 struct et_node *
467 et_new_tree (void *data)
468 {
469 struct et_node *nw;
470
471 if (!et_nodes)
472 et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);
473 nw = (struct et_node *) pool_alloc (et_nodes);
474
475 nw->data = data;
476 nw->father = NULL;
477 nw->left = NULL;
478 nw->right = NULL;
479 nw->son = NULL;
480
481 nw->rightmost_occ = et_new_occ (nw);
482 nw->parent_occ = NULL;
483
484 return nw;
485 }
486
487 /* Releases et tree T. */
488
489 void
490 et_free_tree (struct et_node *t)
491 {
492 while (t->son)
493 et_split (t->son);
494
495 if (t->father)
496 et_split (t);
497
498 pool_free (et_occurrences, t->rightmost_occ);
499 pool_free (et_nodes, t);
500 }
501
502 /* Releases et tree T without maintaining other nodes. */
503
504 void
505 et_free_tree_force (struct et_node *t)
506 {
507 pool_free (et_occurrences, t->rightmost_occ);
508 if (t->parent_occ)
509 pool_free (et_occurrences, t->parent_occ);
510 pool_free (et_nodes, t);
511 }
512
513 /* Release the alloc pools, if they are empty. */
514
515 void
516 et_free_pools (void)
517 {
518 free_alloc_pool_if_empty (&et_occurrences);
519 free_alloc_pool_if_empty (&et_nodes);
520 }
521
522 /* Sets father of et tree T to FATHER. */
523
524 void
525 et_set_father (struct et_node *t, struct et_node *father)
526 {
527 struct et_node *left, *right;
528 struct et_occ *rmost, *left_part, *new_f_occ, *p;
529
530 /* Update the path represented in the splay tree. */
531 new_f_occ = et_new_occ (father);
532
533 rmost = father->rightmost_occ;
534 et_splay (rmost);
535
536 left_part = rmost->prev;
537
538 p = t->rightmost_occ;
539 et_splay (p);
540
541 set_prev (new_f_occ, left_part);
542 set_next (new_f_occ, p);
543
544 p->depth++;
545 p->min++;
546 et_recomp_min (new_f_occ);
547
548 set_prev (rmost, new_f_occ);
549
550 if (new_f_occ->min + rmost->depth < rmost->min)
551 {
552 rmost->min = new_f_occ->min + rmost->depth;
553 rmost->min_occ = new_f_occ->min_occ;
554 }
555
556 t->parent_occ = new_f_occ;
557
558 /* Update the tree. */
559 t->father = father;
560 right = father->son;
561 if (right)
562 left = right->left;
563 else
564 left = right = t;
565
566 left->right = t;
567 right->left = t;
568 t->left = left;
569 t->right = right;
570
571 father->son = t;
572
573 #ifdef DEBUG_ET
574 et_check_tree_sanity (rmost);
575 record_path_before (rmost);
576 #endif
577 }
578
579 /* Splits the edge from T to its father. */
580
581 void
582 et_split (struct et_node *t)
583 {
584 struct et_node *father = t->father;
585 struct et_occ *r, *l, *rmost, *p_occ;
586
587 /* Update the path represented by the splay tree. */
588 rmost = t->rightmost_occ;
589 et_splay (rmost);
590
591 for (r = rmost->next; r->prev; r = r->prev)
592 continue;
593 et_splay (r);
594
595 r->prev->parent = NULL;
596 p_occ = t->parent_occ;
597 et_splay (p_occ);
598 t->parent_occ = NULL;
599
600 l = p_occ->prev;
601 p_occ->next->parent = NULL;
602
603 set_prev (r, l);
604
605 et_recomp_min (r);
606
607 et_splay (rmost);
608 rmost->depth = 0;
609 rmost->min = 0;
610
611 pool_free (et_occurrences, p_occ);
612
613 /* Update the tree. */
614 if (father->son == t)
615 father->son = t->right;
616 if (father->son == t)
617 father->son = NULL;
618 else
619 {
620 t->left->right = t->right;
621 t->right->left = t->left;
622 }
623 t->left = t->right = NULL;
624 t->father = NULL;
625
626 #ifdef DEBUG_ET
627 et_check_tree_sanity (rmost);
628 record_path_before (rmost);
629
630 et_check_tree_sanity (r);
631 record_path_before (r);
632 #endif
633 }
634
635 /* Finds the nearest common ancestor of the nodes N1 and N2. */
636
637 struct et_node *
638 et_nca (struct et_node *n1, struct et_node *n2)
639 {
640 struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
641 struct et_occ *l, *r, *ret;
642 int mn;
643
644 if (n1 == n2)
645 return n1;
646
647 et_splay (o1);
648 l = o1->prev;
649 r = o1->next;
650 if (l)
651 l->parent = NULL;
652 if (r)
653 r->parent = NULL;
654 et_splay (o2);
655
656 if (l == o2 || (l && l->parent != NULL))
657 {
658 ret = o2->next;
659
660 set_prev (o1, o2);
661 if (r)
662 r->parent = o1;
663 }
664 else
665 {
666 ret = o2->prev;
667
668 set_next (o1, o2);
669 if (l)
670 l->parent = o1;
671 }
672
673 if (0 < o2->depth)
674 {
675 om = o1;
676 mn = o1->depth;
677 }
678 else
679 {
680 om = o2;
681 mn = o2->depth + o1->depth;
682 }
683
684 #ifdef DEBUG_ET
685 et_check_tree_sanity (o2);
686 #endif
687
688 if (ret && ret->min + o1->depth + o2->depth < mn)
689 return ret->min_occ->of;
690 else
691 return om->of;
692 }
693
694 /* Checks whether the node UP is an ancestor of the node DOWN. */
695
696 bool
697 et_below (struct et_node *down, struct et_node *up)
698 {
699 struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
700 struct et_occ *l, *r;
701
702 if (up == down)
703 return true;
704
705 et_splay (u);
706 l = u->prev;
707 r = u->next;
708
709 if (!l)
710 return false;
711
712 l->parent = NULL;
713
714 if (r)
715 r->parent = NULL;
716
717 et_splay (d);
718
719 if (l == d || l->parent != NULL)
720 {
721 if (r)
722 r->parent = u;
723 set_prev (u, d);
724 #ifdef DEBUG_ET
725 et_check_tree_sanity (u);
726 #endif
727 }
728 else
729 {
730 l->parent = u;
731
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);
738
739 #ifdef DEBUG_ET
740 et_check_tree_sanity (u);
741 #endif
742 return false;
743 }
744
745 if (0 >= d->depth)
746 return false;
747
748 return !d->next || d->next->min + d->depth >= 0;
749 }
750
751 /* Returns the root of the tree that contains NODE. */
752
753 struct et_node *
754 et_root (struct et_node *node)
755 {
756 struct et_occ *occ = node->rightmost_occ, *r;
757
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);
764
765 return r->of;
766 }