1/* ET-trees data structure implementation.
2   Contributed by Pavel Nejedly
3   Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4
5This file is part of the libiberty library.
6Libiberty is free software; you can redistribute it and/or
7modify it under the terms of the GNU Library General Public
8License as published by the Free Software Foundation; either
9version 2 of the License, or (at your option) any later version.
10
11Libiberty is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14Library General Public License for more details.
15
16You should have received a copy of the GNU Library General Public
17License along with libiberty; see the file COPYING.LIB.  If
18not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19Boston, MA 02110-1301, USA.
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.  */
41struct 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
58static alloc_pool et_nodes;
59static alloc_pool et_occurrences;
60
61/* Changes depth of OCC to D.  */
62
63static inline void
64set_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
75static inline void
76set_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
87static inline void
88set_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
101static inline void
102set_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
115static inline void
116et_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
140static void
141et_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
170static void
171et_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
182static void
183et_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
197static int len;
198static void *datas[MAX_NODES];
199static int depths[MAX_NODES];
200
201/* Records the path represented by OCC, with depth incremented by DEPTH.  */
202
203static int
204record_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
240static void
241record_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
254static int
255check_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
287static void
288check_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
301static void
302et_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
443static struct et_occ *
444et_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 = 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
466struct et_node *
467et_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 = 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
489void
490et_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
504void
505et_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
515void
516et_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
524void
525et_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
581void
582et_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
637struct et_node *
638et_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
696bool
697et_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