* gcc.dg/pr34351.c: Compile for x86 targets only. Use %ebx register.

[pf3gnuchains/gcc-fork.git] / gcc / et-forest.c

diff --git a/gcc/et-forest.c b/gcc/et-forest.c
index e65ccda..6c62fac 100644 (file)
--- a/gcc/et-forest.c
+++ b/gcc/et-forest.c
@@ -1,12 +1,12 @@
 /* ET-trees data structure implementation.
    Contributed by Pavel Nejedly
-   Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
+   Copyright (C) 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
 
 This file is part of the libiberty library.
 Libiberty is free software; you can redistribute it and/or
 modify it under the terms of the GNU Library General Public
 License as published by the Free Software Foundation; either
-version 2 of the License, or (at your option) any later version.
+version 3 of the License, or (at your option) any later version.
 
 Libiberty is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ -14,9 +14,8 @@ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 Library General Public License for more details.
 
 You should have received a copy of the GNU Library General Public
-License along with libiberty; see the file COPYING.LIB.  If
-not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA.
+License along with libiberty; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.
 
   The ET-forest structure is described in:
     D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
@@ -88,8 +87,7 @@ static inline void
 set_prev (struct et_occ *occ, struct et_occ *t)
 {
 #ifdef DEBUG_ET
-  if (occ == t)
-    abort ();
+  gcc_assert (occ != t);
 #endif
 
   occ->prev = t;
@@ -103,8 +101,7 @@ static inline void
 set_next (struct et_occ *occ, struct et_occ *t)
 {
 #ifdef DEBUG_ET
-  if (occ == t)
-    abort ();
+  gcc_assert (occ != t);
 #endif
 
   occ->next = t;
@@ -137,7 +134,7 @@ et_recomp_min (struct et_occ *occ)
 }
 
 #ifdef DEBUG_ET
-/* Checks whether neighbourhood of OCC seems sane.  */
+/* Checks whether neighborhood of OCC seems sane.  */
 
 static void
 et_check_occ_sanity (struct et_occ *occ)
@@ -145,40 +142,26 @@ et_check_occ_sanity (struct et_occ *occ)
   if (!occ)
     return;
 
-  if (occ->parent == occ)
-    abort ();
-
-  if (occ->prev == occ)
-    abort ();
-
-  if (occ->next == occ)
-    abort ();
-
-  if (occ->next && occ->next == occ->prev)
-    abort ();
+  gcc_assert (occ->parent != occ);
+  gcc_assert (occ->prev != occ);
+  gcc_assert (occ->next != occ);
+  gcc_assert (!occ->next || occ->next != occ->prev);
 
   if (occ->next)
     {
-      if (occ->next == occ->parent)
-       abort ();
-
-      if (occ->next->parent != occ)
-       abort ();
+      gcc_assert (occ->next != occ->parent);
+      gcc_assert (occ->next->parent == occ);
     }
 
   if (occ->prev)
     {
-      if (occ->prev == occ->parent)
-       abort ();
-
-      if (occ->prev->parent != occ)
-       abort ();
+      gcc_assert (occ->prev != occ->parent);
+      gcc_assert (occ->prev->parent == occ);
     }
 
-  if (occ->parent
-      && occ->parent->prev != occ
-      && occ->parent->next != occ)
-    abort ();
+  gcc_assert (!occ->parent
+             || occ->parent->prev == occ
+             || occ->parent->next == occ);
 }
 
 /* Checks whether tree rooted at OCC is sane.  */
@@ -206,9 +189,13 @@ et_check_tree_sanity (struct et_occ *occ)
 
 /* For recording the paths.  */
 
+/* An ad-hoc constant; if the function has more blocks, this won't work,
+   but since it is used for debugging only, it does not matter.  */
+#define MAX_NODES 100000
+
 static int len;
-static void *datas[100000];
-static int depths[100000];
+static void *datas[MAX_NODES];
+static int depths[MAX_NODES];
 
 /* Records the path represented by OCC, with depth incremented by DEPTH.  */
 
@@ -228,6 +215,9 @@ record_path_before_1 (struct et_occ *occ, int depth)
     }
 
   fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
+
+  gcc_assert (len < MAX_NODES);
+
   depths[len] = depth;
   datas[len] = occ->of;
   len++;
@@ -239,8 +229,7 @@ record_path_before_1 (struct et_occ *occ, int depth)
        mn = m;
     }
 
-  if (mn != occ->min + depth - occ->depth)
-    abort ();
+  gcc_assert (mn == occ->min + depth - occ->depth);
 
   return mn;
 }
@@ -277,9 +266,7 @@ check_path_after_1 (struct et_occ *occ, int depth)
     }
 
   len--;
-  if (depths[len] != depth
-      || datas[len] != occ->of)
-    abort ();
+  gcc_assert (depths[len] == depth && datas[len] == occ->of);
 
   if (occ->prev)
     {
@@ -288,8 +275,7 @@ check_path_after_1 (struct et_occ *occ, int depth)
        mn =  m;
     }
 
-  if (mn != occ->min + depth - occ->depth)
-    abort ();
+  gcc_assert (mn == occ->min + depth - occ->depth);
 
   return mn;
 }
@@ -304,8 +290,7 @@ check_path_after (struct et_occ *occ)
     occ = occ->parent;
 
   check_path_after_1 (occ, 0);
-  if (len != 0)
-    abort ();
+  gcc_assert (!len);
 }
 
 #endif
@@ -513,6 +498,26 @@ et_free_tree (struct et_node *t)
   pool_free (et_nodes, t);
 }
 
+/* Releases et tree T without maintaining other nodes.  */
+
+void
+et_free_tree_force (struct et_node *t)
+{
+  pool_free (et_occurrences, t->rightmost_occ);
+  if (t->parent_occ)
+    pool_free (et_occurrences, t->parent_occ);
+  pool_free (et_nodes, t);
+}
+
+/* Release the alloc pools, if they are empty.  */
+
+void
+et_free_pools (void)
+{
+  free_alloc_pool_if_empty (&et_occurrences);
+  free_alloc_pool_if_empty (&et_nodes);
+}
+
 /* Sets father of et tree T to FATHER.  */
 
 void
@@ -741,3 +746,20 @@ et_below (struct et_node *down, struct et_node *up)
 
   return !d->next || d->next->min + d->depth >= 0;
 }
+
+/* Returns the root of the tree that contains NODE.  */
+
+struct et_node *
+et_root (struct et_node *node)
+{
+  struct et_occ *occ = node->rightmost_occ, *r;
+
+  /* The root of the tree corresponds to the rightmost occurence in the
+     represented path.  */
+  et_splay (occ);
+  for (r = occ; r->next; r = r->next)
+    continue;
+  et_splay (r);
+
+  return r->of;
+}