OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [et-forest.c] - Blame information for rev 280

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* 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
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.