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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [et-forest.c] - Blame information for rev 708

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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