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