Backport from tree-ssa (relevant changes only):

	2003-12-18  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>

	* et-forest.h (et_forest_create, et_forest_delete,
	et_forest_add_node, et_forest_add_edge, et_forest_remove_node,
	et_forest_remove_edge, et_forest_parent,
	et_forest_common_ancestor, et_forest_node_value,
	et_forest_enumerate_sons): Declarations removed.
	(struct et_node): New.
	(et_new_tree, et_free_tree, et_set_father, et_split, et_nca,
	et_below): Declare.
	* et-forest.c (struct et_forest_occurrence, struct et_forest,
	struct et_forest_node): Removed.
	(et_forest_create, et_forest_delete,
	et_forest_add_node, et_forest_add_edge, et_forest_remove_node,
	et_forest_remove_edge, et_forest_parent,
	et_forest_common_ancestor, et_forest_node_value,
	et_forest_enumerate_sons, splay, remove_all_occurrences,
	find_leftmost_node, find_rightmost_node, calculate_value): Removed.
	(struct et_occ): New.
	(et_nodes, et_occurences): New.
	(set_depth, set_depth_add, set_prev, set_next, et_recomp_min,
	et_check_occ_sanity, et_check_sanity, et_check_tree_sanity,
	record_path_before_1, record_path_before, check_path_after_1,
	check_path_after, et_splay, et_new_occ, et_new_tree,
	et_free_tree, et_set_father, et_split, et_nca, et_below): New.
	* basic-block.h (struct basic_block_def): New field dom.
	(struct dominance_info): Type removed.
	(calculate_dominance_info, free_dominance_info,
	nearest_common_dominator, set_immediate_dominator,
	get_immediate_dominator, dominated_by_p, get_dominated_by,
	add_to_dominance_info, delete_from_dominance_info,
	recount_dominator, redirect_immediate_dominators,
	iterate_fix_dominators, verify_dominators): Declarations
	changed.
	(enum dom_state): New.
	(dom_computed): New variable.
	(first_dom_son, next_dom_son): Declare.
	* dominance.c (struct dominance_info): Removed.
	(BB_NODE, SET_BB_NODE): Removed.
	(calculate_dominance_info, free_dominance_info,
	nearest_common_dominator, set_immediate_dominator,
	get_immediate_dominator, dominated_by_p, get_dominated_by,
	add_to_dominance_info, delete_from_dominance_info,
	recount_dominator, redirect_immediate_dominators,
	iterate_fix_dominators, verify_dominators,
	debug_dominance_info): Work over new datastructure.  Access
	dominance datastructures through CFG.
	(assign_dfs_numbers, compute_dom_fast_query, first_dom_son,
	next_dom_son): New.
	* bt-load.c (dom): Variable removed.
	(augment_live_range, combine_btr_defs, migrate_btr_def,
	migrate_btr_defs, branch_target_load_optimize): Updated for the
	new interface for dominance information.
	* cfg.c {exit_entry_blocks): Update initializer.
	* cfglayout.c (copy_bbs): Removed loops argument. Updated for
	the new interface for dominance information.
	* cfglayout.h (copy_bbs): Declaration changed.
	* cfgloop.c (flow_loop_pre_header_find, flow_loops_cfg_dump,
	flow_loop_scan, canonicalize_loop_headers, flow_loops_find): Updated
	for the new interface for dominance information.
	(flow_loop_scan): Loops argument removed.
	(flow_loops_free): Don't release dominators.
	* cfgloop.h (struct cfg): Dom field removed.
	(flow_loop_scan, loop_split_edge_with, simple_loop_p,
	just_once_each_iteration_p, split_loop_bb): Declaration changed.
	* cfgloopanal.c (simple_loop_exit_p, simple_increment,
	just_once_each_iteration_p, simple_loop_p): Remove loops argument.
	Updated for the new interface for dominance information.
	* cfgloopmanip.c (remove_bbs, find_path, create_preheader,
	split_loop_bb, loopify, duplicate_loop_to_header_edge,
	force_single_succ_latches, loop_split_edge_with): Ditto.
	* gcse.c (dominators): Variable removed.
	(free_code_hoist_mem, compute_code_hoist_data, hoist_code):
	Updated for the new interface for dominance information.
	* ifcvt.c (post_dominators): Variable removed.
	(mark_loop_exit_edges, merge_if_block, find_if_header,
	find_cond_trap, find_if_case_1, find_if_case_2, if_convert):
	Updated for the new interface for dominance information.
	* loop-init.c (rtl_loop_optimizer_init,
	rtl_loop_optimizer_finalize): Ditto.
	* loop-unroll.c (decide_peel_simple, decide_peel_once_rolling,
	decide_peel_completely, decide_unroll_stupid,
	decide_unroll_constant_iterations,
	decide_unroll_runtime_iterations): Loops argument removed.
	Updated for the new interface for dominance information.
	(unroll_and_peel_loops, peel_loops_completely,
	unroll_loop_runtime_iterations): Updated for the new interface for
	dominance information.
	* loop-unswitch.c (may_unswitch_on_p, unswitch_loops,
	unswitch_single_loop, unswitch_loop): Updated for the new
	interface for dominance information.
	* predict.c (process_note_predictions, process_note_prediction,
	estimate_probability, note_prediction_to_br_prob): Ditto.
	* sched-rgn.c (find_rgns, init_regions): Ditto.
	* toplev.c (rest_of_handle_branch_prob): Free the dominators.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@75226 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 583 insertions, 507 deletions

diff --git a/gcc/et-forest.c b/gcc/et-forest.c
index ffdce1d76bd..ea7793f83b3 100644
--- a/gcc/et-forest.c
+++ b/gcc/et-forest.c
@@ -30,638 +30,714 @@ Boston, MA 02111-1307, USA.
 #include "et-forest.h"
 #include "alloc-pool.h"
 
-struct et_forest_occurrence;
-typedef struct et_forest_occurrence* et_forest_occurrence_t;
+/* We do not enable this with ENABLE_CHECKING, since it is awfully slow.  */
+#undef DEBUG_ET
 
-/* The ET-forest type.  */
-struct et_forest
-{
-  /* Linked list of nodes is used to destroy the structure.  */
-  int nnodes;
-  alloc_pool node_pool;
-  alloc_pool occur_pool;
-};
+#ifdef DEBUG_ET
+#include "basic-block.h"
+#endif
 
-/* Single occurrence of node in ET-forest.
-   A single node may have multiple occurrences.
- */
-struct et_forest_occurrence
+/* The occurence of a node in the et tree.  */
+struct et_occ
 {
-  /* Parent in the splay-tree.  */
-  et_forest_occurrence_t parent;
+  struct et_node *of;		/* The node.  */
+
+  struct et_occ *parent;	/* Parent in the splay-tree.  */
+  struct et_occ *prev;		/* Left son in the splay-tree.  */
+  struct et_occ *next;		/* Right son in the splay-tree.  */
+
+  int depth;			/* The depth of the node is the sum of depth
+				   fields on the path to the root.  */
+  int min;			/* The minimum value of the depth in the subtree
+				   is obtained by adding sum of depth fields
+				   on the path to the root.  */
+  struct et_occ *min_occ;	/* The occurence in the subtree with the minimal
+				   depth.  */
+};
 
-  /* Children in the splay-tree.  */
-  et_forest_occurrence_t left, right;
+static alloc_pool et_nodes;
+static alloc_pool et_occurences;
 
-  /* Counts of vertices in the two splay-subtrees.  */
-  int count_left, count_right;
+/* Changes depth of OCC to D.  */
 
-  /* Next occurrence of this node in the sequence.  */
-  et_forest_occurrence_t next;
+static inline void
+set_depth (struct et_occ *occ, int d)
+{
+  if (!occ)
+    return;
 
-  /* The node, which this occurrence is of.  */
-  et_forest_node_t node;
-};
+  occ->min += d - occ->depth;
+  occ->depth = d;
+}
 
+/* Adds D to the depth of OCC.  */
 
-/* ET-forest node.  */
-struct et_forest_node
+static inline void
+set_depth_add (struct et_occ *occ, int d)
 {
-  et_forest_t forest;
-  void *value;
-
-  /* First and last occurrence of this node in the sequence.  */
-  et_forest_occurrence_t first, last;
-};
+  if (!occ)
+    return;
 
+  occ->min += d;
+  occ->depth += d;
+}
 
-static et_forest_occurrence_t splay (et_forest_occurrence_t);
-static void remove_all_occurrences (et_forest_t, et_forest_node_t);
-static inline et_forest_occurrence_t find_leftmost_node
-  (et_forest_occurrence_t);
-static inline et_forest_occurrence_t find_rightmost_node
-  (et_forest_occurrence_t);
-static int calculate_value (et_forest_occurrence_t);
+/* Sets prev field of OCC to P.  */
 
-/* Return leftmost node present in the tree roted by OCC.  */
-static inline et_forest_occurrence_t
-find_leftmost_node (et_forest_occurrence_t occ)
+static inline void
+set_prev (struct et_occ *occ, struct et_occ *t)
 {
-  while (occ->left)
-    occ = occ->left;
+#ifdef DEBUG_ET
+  if (occ == t)
+    abort ();
+#endif
 
-  return occ;
+  occ->prev = t;
+  if (t)
+    t->parent = occ;
 }
 
-/* Return rightmost node present in the tree roted by OCC.  */
-static inline et_forest_occurrence_t
-find_rightmost_node (et_forest_occurrence_t occ)
+/* Sets next field of OCC to P.  */
+
+static inline void
+set_next (struct et_occ *occ, struct et_occ *t)
 {
-  while (occ->right)
-    occ = occ->right;
-  return occ;
+#ifdef DEBUG_ET
+  if (occ == t)
+    abort ();
+#endif
+
+  occ->next = t;
+  if (t)
+    t->parent = occ;
 }
 
+/* Recompute minimum for occurence OCC.  */
 
-/* Operation splay for splay tree structure representing occurrences.  */
-static et_forest_occurrence_t
-splay (et_forest_occurrence_t node)
+static inline void
+et_recomp_min (struct et_occ *occ)
 {
-  et_forest_occurrence_t parent;
-  et_forest_occurrence_t grandparent;
+  struct et_occ *mson = occ->prev;
 
-  while (1)
-    {
-      parent = node->parent;
+  if (!mson
+      || (occ->next
+	  && mson->min > occ->next->min))
+      mson = occ->next;
 
-      if (! parent)
-	return node;  /* node == root.  */
+  if (mson && mson->min < 0)
+    {
+      occ->min = mson->min + occ->depth;
+      occ->min_occ = mson->min_occ;
+    }
+  else
+    {
+      occ->min = occ->depth;
+      occ->min_occ = occ;
+    }
+}
 
-      grandparent = parent->parent;
+#ifdef DEBUG_ET
+/* Checks whether neighbourhood of OCC seems sane.  */
 
-      if (! grandparent)
-	break;
+static void
+et_check_occ_sanity (struct et_occ *occ)
+{
+  if (!occ)
+    return;
 
-      /* Now there are four possible combinations:  */
+  if (occ->parent == occ)
+    abort ();
 
-      if (node == parent->left)
-	{
-	  if (parent == grandparent->left)
-	    {
-	      et_forest_occurrence_t node1, node2;
-	      int count1, count2;
-
-	      node1 = node->right;
-	      count1 = node->count_right;
-	      node2 = parent->right;
-	      count2 = parent->count_right;
-
-	      grandparent->left = node2;
-	      grandparent->count_left = count2;
-	      if (node2)
-		node2->parent = grandparent;
-	      parent->left = node1;
-	      parent->count_left = count1;
-	      if (node1)
-		node1->parent = parent;
-	      parent->right = grandparent;
-	      parent->count_right = count2 + grandparent->count_right + 1;
-	      node->right = parent;
-	      node->count_right = count1 + parent->count_right + 1;
-
-	      node->parent = grandparent->parent;
-	      parent->parent = node;
-	      grandparent->parent = parent;
-
-	      if (node->parent)
-		{
-		  if (node->parent->left == grandparent)
-		    node->parent->left = node;
-		  else
-		    node->parent->right = node;
-		}
-	    }
-	  else
-	    {
-	      /* parent == grandparent->right && node == parent->left*/
-	      et_forest_occurrence_t node1, node2;
-	      int count1, count2;
-
-	      node1 = node->left;
-	      count1 = node->count_left;
-	      node2 = node->right;
-	      count2 = node->count_right;
-
-	      grandparent->right = node1;
-	      grandparent->count_right = count1;
-	      if (node1)
-		node1->parent = grandparent;
-	      parent->left = node2;
-	      parent->count_left = count2;
-	      if (node2)
-		node2->parent = parent;
-	      node->left = grandparent;
-	      node->count_left = grandparent->count_left + count1 + 1;
-	      node->right = parent;
-	      node->count_right = parent->count_right + count2 + 1;
-
-	      node->parent = grandparent->parent;
-	      parent->parent = node;
-	      grandparent->parent = node;
-
-	      if (node->parent)
-		{
-		  if (node->parent->left == grandparent)
-		    node->parent->left = node;
-		  else
-		    node->parent->right = node;
-		}
-	    }
-	}
-      else
-	{
-	  /* node == parent->right.  */
-	  if (parent == grandparent->left)
-	    {
-	      et_forest_occurrence_t node1, node2;
-	      int count1, count2;
-
-	      node1 = node->left;
-	      count1 = node->count_left;
-	      node2 = node->right;
-	      count2 = node->count_right;
-
-	      parent->right = node1;
-	      parent->count_right = count1;
-	      if (node1)
-		node1->parent = parent;
-	      grandparent->left = node2;
-	      grandparent->count_left = count2;
-	      if (node2)
-		node2->parent = grandparent;
-	      node->left = parent;
-	      node->count_left = parent->count_left + count1 + 1;
-	      node->right = grandparent;
-	      node->count_right = grandparent->count_right + count2 + 1;
-
-	      node->parent = grandparent->parent;
-	      parent->parent = node;
-	      grandparent->parent = node;
-
-	      if (node->parent)
-		{
-		  if (node->parent->left == grandparent)
-		    node->parent->left = node;
-		  else
-		    node->parent->right = node;
-		}
-	    }
-	  else
-	    {
-	      /* parent == grandparent->right && node == parent->right*/
-	      et_forest_occurrence_t node1, node2;
-	      int count1, count2;
-
-	      node1 = node->left;
-	      count1 = node->count_left;
-	      node2 = parent->left;
-	      count2 = parent->count_left;
-
-	      grandparent->right = node2;
-	      grandparent->count_right = count2;
-	      if (node2)
-		node2->parent = grandparent;
-	      parent->right = node1;
-	      parent->count_right = count1;
-	      if (node1)
-		node1->parent = parent;
-	      parent->left = grandparent;
-	      parent->count_left = count2 + grandparent->count_left + 1;
-	      node->left = parent;
-	      node->count_left = count1 + parent->count_left + 1;
-
-	      node->parent = grandparent->parent;
-	      parent->parent = node;
-	      grandparent->parent = parent;
-
-	      if (node->parent)
-		{
-		  if (node->parent->left == grandparent)
-		    node->parent->left = node;
-		  else
-		    node->parent->right = node;
-		}
-	    }
-	}
+  if (occ->prev == occ)
+    abort ();
 
-    }
+  if (occ->next == occ)
+    abort ();
 
-  /* parent == root.  */
-  /* There are two possible combinations:  */
+  if (occ->next && occ->next == occ->prev)
+    abort ();
 
-  if (node == parent->left)
+  if (occ->next)
     {
-      et_forest_occurrence_t node1;
-      int count1;
-
-      node1 = node->right;
-      count1 = node->count_right;
-
-      parent->left = node1;
-      parent->count_left = count1;
-      if (node1)
-	node1->parent = parent;
-      node->right = parent;
-      node->count_right = parent->count_right + 1 + count1;
-      node->parent = parent->parent;  /* the same as = 0;  */
-      parent->parent = node;
-
-      if (node->parent)
-	{
-	  if (node->parent->left == parent)
-	    node->parent->left = node;
-	  else
-	    node->parent->right = node;
-	}
+      if (occ->next == occ->parent)
+	abort ();
+
+      if (occ->next->parent != occ)
+	abort ();
     }
-  else
+
+  if (occ->prev)
     {
-      /* node == parent->right.  */
-      et_forest_occurrence_t node1;
-      int count1;
-
-      node1 = node->left;
-      count1 = node->count_left;
-
-      parent->right = node1;
-      parent->count_right = count1;
-      if (node1)
-	node1->parent = parent;
-      node->left = parent;
-      node->count_left = parent->count_left + 1 + count1;
-      node->parent = parent->parent;  /* the same as = 0;  */
-      parent->parent = node;
-
-      if (node->parent)
-	{
-	  if (node->parent->left == parent)
-	    node->parent->left = node;
-	  else
-	    node->parent->right = node;
-	}
+      if (occ->prev == occ->parent)
+	abort ();
+
+      if (occ->prev->parent != occ)
+	abort ();
     }
 
-  return node;
+  if (occ->parent
+      && occ->parent->prev != occ
+      && occ->parent->next != occ)
+    abort ();
 }
 
-/* Remove all occurrences of the given node before destroying the node.  */
+/* Checks whether tree rooted at OCC is sane.  */
+
 static void
-remove_all_occurrences (et_forest_t forest, et_forest_node_t forest_node)
+et_check_sanity (struct et_occ *occ)
 {
-  et_forest_occurrence_t first = forest_node->first;
-  et_forest_occurrence_t last = forest_node->last;
-  et_forest_occurrence_t node;
+  et_check_occ_sanity (occ);
+  if (occ->prev)
+    et_check_sanity (occ->prev);
+  if (occ->next)
+    et_check_sanity (occ->next);
+}
 
-  splay (first);
+/* Checks whether tree containing OCC is sane.  */
 
-  if (first->left)
-    first->left->parent = 0;
-  if (first->right)
-    first->right->parent = 0;
+static void
+et_check_tree_sanity (struct et_occ *occ)
+{
+  while (occ->parent)
+    occ = occ->parent;
 
-  if (last != first)
-    {
-      splay (last);
+  et_check_sanity (occ);
+}
 
-      if (last->left)
-	last->left->parent = 0;
-      if (last->right)
-	last->right->parent = 0;
-    }
+/* For recording the paths.  */
 
-  if (last->right && first->left) /* actually, first->left would suffice.  */
-    {
-      /* Need to join them.  */
-      et_forest_occurrence_t prev_node, next_node;
-
-      prev_node = splay (find_rightmost_node (first->left));
-      next_node = splay (find_leftmost_node (last->right));
-      /* prev_node and next_node are consecutive occurrences
-	 of the same node.  */
-      if (prev_node->next != next_node)
-	abort ();
+static int len;
+static void *datas[100000];
+static int depths[100000];
 
-      prev_node->right = next_node->right;
-      prev_node->count_right = next_node->count_right;
-      prev_node->next = next_node->next;
-      if (prev_node->right)
-	prev_node->right->parent = prev_node;
+/* Records the path represented by OCC, with depth incremented by DEPTH.  */
 
-      if (prev_node->node->last == next_node)
-	prev_node->node->last = prev_node;
+static int
+record_path_before_1 (struct et_occ *occ, int depth)
+{
+  int mn, m;
 
-      pool_free (forest->occur_pool, next_node);
+  depth += occ->depth;
+  mn = depth;
+
+  if (occ->prev)
+    {
+      m = record_path_before_1 (occ->prev, depth); 
+      if (m < mn)
+	mn = m;
     }
 
-  if (first != last)
+  fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
+  depths[len] = depth;
+  datas[len] = occ->of;
+  len++;
+
+  if (occ->next)
     {
-      node = first->next;
+      m = record_path_before_1 (occ->next, depth);
+      if (m < mn)
+	mn = m;
+    }
 
-      while (node != last)
-	{
-	  et_forest_occurrence_t next_node;
+  if (mn != occ->min + depth - occ->depth)
+    abort ();
 
-	  splay (node);
+  return mn;
+}
 
-	  if (node->left)
-	    node->left->parent = 0;
-	  if (node->right)
-	    node->right->parent = 0;
+/* Records the path represented by a tree containing OCC.  */
 
-	  next_node = node->next;
-	  pool_free (forest->occur_pool, node);
-	  node = next_node;
-	}
-    }
+static void
+record_path_before (struct et_occ *occ)
+{
+  while (occ->parent)
+    occ = occ->parent;
 
-  pool_free (forest->occur_pool, first);
-  if (first != last)
-    pool_free (forest->occur_pool, last);
+  len = 0;
+  record_path_before_1 (occ, 0);
+  fprintf (stderr, "\n");
 }
 
-/* Calculate ET value of the given node.  */
-static inline int
-calculate_value (et_forest_occurrence_t node)
+/* Checks whether the path represented by OCC, with depth incremented by DEPTH,
+   was not changed since the last recording.  */
+
+static int
+check_path_after_1 (struct et_occ *occ, int depth)
 {
-  int value = node->count_left;
+  int mn, m;
+
+  depth += occ->depth;
+  mn = depth;
 
-  while (node->parent)
+  if (occ->next)
     {
-      if (node == node->parent->right)
-	value += node->parent->count_left + 1;
+      m = check_path_after_1 (occ->next, depth); 
+      if (m < mn)
+	mn =  m;
+    }
 
-      node = node->parent;
+  len--;
+  if (depths[len] != depth
+      || datas[len] != occ->of)
+    abort ();
+
+  if (occ->prev)
+    {
+      m = check_path_after_1 (occ->prev, depth);
+      if (m < mn)
+	mn =  m;
     }
 
-  return value;
+  if (mn != occ->min + depth - occ->depth)
+    abort ();
+
+  return mn;
 }
 
+/* Checks whether the path represented by a tree containing OCC was
+   not changed since the last recording.  */
+
+static void
+check_path_after (struct et_occ *occ)
+{
+  while (occ->parent)
+    occ = occ->parent;
+
+  check_path_after_1 (occ, 0);
+  if (len != 0)
+    abort ();
+}
 
+#endif
 
+/* Splay the occurence OCC to the root of the tree.  */
 
-/* Create ET-forest structure.  */
-et_forest_t
-et_forest_create (void)
+static inline void
+et_splay (struct et_occ *occ)
 {
-  et_forest_t forest = xmalloc (sizeof (struct et_forest));
+  struct et_occ *f, *gf, *ggf;
+  int occ_depth, f_depth, gf_depth;
+
+#ifdef DEBUG_ET
+  record_path_before (occ);
+  et_check_tree_sanity (occ);
+#endif
+ 
+  while (occ->parent)
+    {
+      occ_depth = occ->depth;
 
-  forest->nnodes = 0;
-  forest->occur_pool = create_alloc_pool ("et_forest_occurrence pool", sizeof (struct et_forest_occurrence), 300);
-  forest->node_pool = create_alloc_pool ("et_forest_node pool", sizeof (struct et_forest_node), 300);
-  return forest;
-}
+      f = occ->parent;
+      f_depth = f->depth;
 
+      gf = f->parent;
 
+      if (!gf)
+	{
+	  set_depth_add (occ, f_depth);
+	  occ->min_occ = f->min_occ;
+	  occ->min = f->min;
 
-/* Deallocate the structure.  */
-void
-et_forest_delete (et_forest_t forest)
+	  if (f->prev == occ)
+	    {
+	      /* zig */
+	      set_prev (f, occ->next);
+	      set_next (occ, f);
+	      set_depth_add (f->prev, occ_depth);
+	    }
+	  else
+	    {
+	      /* zag */
+	      set_next (f, occ->prev);
+	      set_prev (occ, f);
+	      set_depth_add (f->next, occ_depth);
+	    }
+	  set_depth (f, -occ_depth);
+	  occ->parent = NULL;
+
+	  et_recomp_min (f);
+#ifdef DEBUG_ET
+	  et_check_tree_sanity (occ);
+	  check_path_after (occ);
+#endif
+	  return;
+	}
+
+      gf_depth = gf->depth;
+
+      set_depth_add (occ, f_depth + gf_depth);
+      occ->min_occ = gf->min_occ;
+      occ->min = gf->min;
+
+      ggf = gf->parent;
+
+      if (gf->prev == f)
+	{
+	  if (f->prev == occ)
+	    {
+	      /* zig zig */
+	      set_prev (gf, f->next);
+	      set_prev (f, occ->next);
+	      set_next (occ, f);
+	      set_next (f, gf);
+
+	      set_depth (f, -occ_depth);
+	      set_depth_add (f->prev, occ_depth);
+	      set_depth (gf, -f_depth);
+	      set_depth_add (gf->prev, f_depth);
+	    }
+	  else
+	    {
+	      /* zag zig */
+	      set_prev (gf, occ->next);
+	      set_next (f, occ->prev);
+	      set_prev (occ, f);
+	      set_next (occ, gf);
+
+	      set_depth (f, -occ_depth);
+	      set_depth_add (f->next, occ_depth);
+	      set_depth (gf, -occ_depth - f_depth);
+	      set_depth_add (gf->prev, occ_depth + f_depth);
+	    }
+	}
+      else
+	{
+	  if (f->prev == occ)
+	    {
+	      /* zig zag */
+	      set_next (gf, occ->prev);
+	      set_prev (f, occ->next);
+	      set_prev (occ, gf);
+	      set_next (occ, f);
+
+	      set_depth (f, -occ_depth);
+	      set_depth_add (f->prev, occ_depth);
+	      set_depth (gf, -occ_depth - f_depth);
+	      set_depth_add (gf->next, occ_depth + f_depth);
+	    }
+	  else
+	    {
+	      /* zag zag */
+	      set_next (gf, f->prev);
+	      set_next (f, occ->prev);
+	      set_prev (occ, f);
+	      set_prev (f, gf);
+
+	      set_depth (f, -occ_depth);
+	      set_depth_add (f->next, occ_depth);
+	      set_depth (gf, -f_depth);
+	      set_depth_add (gf->next, f_depth);
+	    }
+	}
+
+      occ->parent = ggf;
+      if (ggf)
+	{
+	  if (ggf->prev == gf)
+	    ggf->prev = occ;
+	  else
+	    ggf->next = occ;
+	}
+
+      et_recomp_min (gf);
+      et_recomp_min (f);
+#ifdef DEBUG_ET
+      et_check_tree_sanity (occ);
+#endif
+    }
+
+#ifdef DEBUG_ET
+  et_check_sanity (occ);
+  check_path_after (occ);
+#endif
+}
+
+/* Create a new et tree occurence of NODE.  */
+
+static struct et_occ *
+et_new_occ (struct et_node *node)
 {
-  if (forest->nnodes)
-    abort ();
-  free_alloc_pool (forest->occur_pool);
-  free_alloc_pool (forest->node_pool);
-  free (forest);
+  struct et_occ *nw;
+  
+  if (!et_occurences)
+    et_occurences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);
+  nw = pool_alloc (et_occurences);
+
+  nw->of = node;
+  nw->parent = NULL;
+  nw->prev = NULL;
+  nw->next = NULL;
+
+  nw->depth = 0;
+  nw->min_occ = nw;
+  nw->min = 0;
+
+  return nw;
 }
 
-/* Create new node with VALUE and return the edge.
-   Return NULL when memory allocation failed.  */
-et_forest_node_t
-et_forest_add_node (et_forest_t forest, void *value)
+/* Create a new et tree containing DATA.  */
+
+struct et_node *
+et_new_tree (void *data)
 {
-  /* Create node with one occurrence.  */
-  et_forest_node_t node;
-  et_forest_occurrence_t occ;
-
-  node = pool_alloc (forest->node_pool);
-  occ = pool_alloc (forest->occur_pool);
-
-  node->first = node->last = occ;
-  node->value = value;
-  forest->nnodes++;
-
-  occ->node = node;
-  occ->left = occ->right = occ->parent = 0;
-  occ->next = 0;
-  occ->count_left = occ->count_right = 0;
-  return node;
+  struct et_node *nw;
+  
+  if (!et_nodes)
+    et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);
+  nw = pool_alloc (et_nodes);
+
+  nw->data = data;
+  nw->father = NULL;
+  nw->left = NULL;
+  nw->right = NULL;
+  nw->son = NULL;
+
+  nw->rightmost_occ = et_new_occ (nw);
+  nw->parent_occ = NULL;
+
+  return nw;
 }
 
-/* Add new edge to the tree, return 1 if successful.
-   0 indicates that creation of the edge will close the cycle in graph.  */
-int
-et_forest_add_edge (et_forest_t forest ATTRIBUTE_UNUSED,
-		    et_forest_node_t parent_node, et_forest_node_t child_node)
+/* Releases et tree T.  */
+
+void
+et_free_tree (struct et_node *t)
 {
-  et_forest_occurrence_t new_occ, parent_occ, child_occ;
+  while (t->son)
+    et_split (t->son);
 
-  if (! parent_node || ! child_node)
-    abort ();
+  if (t->father)
+    et_split (t);
 
-  parent_occ = parent_node->first;
-  child_occ = child_node->first;
-
-  splay (parent_occ);
-  splay (child_occ);
-
-  if (parent_occ->parent)
-    return 0; /* Both child and parent are in the same tree.  */
-
-  if (child_occ->left)
-    abort ();  /* child must be root of its containing tree.  */
-
-  new_occ = pool_alloc (forest->occur_pool);
-
-  new_occ->node = parent_node;
-  new_occ->left = child_occ;
-  new_occ->count_left = child_occ->count_right + 1; /* count_left is 0.  */
-  new_occ->right = parent_occ->right;
-  new_occ->count_right = parent_occ->count_right;
-  new_occ->parent = parent_occ;
-  new_occ->next = parent_occ->next;
-  child_occ->parent = new_occ;
-  parent_occ->right = new_occ;
-  parent_occ->count_right = new_occ->count_left + new_occ->count_right + 1;
-  parent_occ->next = new_occ;
-  if (new_occ->right)
-    new_occ->right->parent = new_occ;
-
-  if (parent_node->last == parent_occ)
-    parent_node->last = new_occ;
-  return 1;
+  pool_free (et_occurences, t->rightmost_occ);
+  pool_free (et_nodes, t);
 }
 
-/* Remove NODE from the tree and all connected edges.  */
+/* Sets father of et tree T to FATHER.  */
+
 void
-et_forest_remove_node (et_forest_t forest, et_forest_node_t node)
+et_set_father (struct et_node *t, struct et_node *father)
 {
-  remove_all_occurrences (forest, node);
-  forest->nnodes--;
+  struct et_node *left, *right;
+  struct et_occ *rmost, *left_part, *new_f_occ, *p;
 
-  pool_free (forest->node_pool, node);
-}
+  /* Update the path represented in the splay tree.  */
+  new_f_occ = et_new_occ (father);
 
-/* Remove edge from the tree, return 1 if successful,
-   0 indicates nonexisting edge.  */
-int
-et_forest_remove_edge (et_forest_t forest ATTRIBUTE_UNUSED,
-		       et_forest_node_t parent_node,
-		       et_forest_node_t child_node)
-{
-  et_forest_occurrence_t parent_pre_occ, parent_post_occ;
+  rmost = father->rightmost_occ;
+  et_splay (rmost);
 
-  splay (child_node->first);
+  left_part = rmost->prev;
 
-  if (! child_node->first->left)
-    return 0;
+  p = t->rightmost_occ;
+  et_splay (p);
 
-  parent_pre_occ = find_rightmost_node (child_node->first->left);
-  if (parent_pre_occ->node != parent_node)
-    abort ();
+  set_prev (new_f_occ, left_part);
+  set_next (new_f_occ, p);
+
+  p->depth++;
+  p->min++;
+  et_recomp_min (new_f_occ);
 
-  splay (parent_pre_occ);
-  parent_pre_occ->right->parent = 0;
+  set_prev (rmost, new_f_occ);
 
-  parent_post_occ = parent_pre_occ->next;
-  splay (parent_post_occ);
+  if (new_f_occ->min + rmost->depth < rmost->min)
+    {
+      rmost->min = new_f_occ->min + rmost->depth;
+      rmost->min_occ = new_f_occ->min_occ;
+    }
 
-  parent_post_occ->left->parent = 0;
+  t->parent_occ = new_f_occ;
 
-  parent_pre_occ->right = parent_post_occ->right;
-  parent_pre_occ->count_right = parent_post_occ->count_right;
-  if (parent_post_occ->right)
-    parent_post_occ->right->parent = parent_pre_occ;
+  /* Update the tree.  */
+  t->father = father;
+  right = father->son;
+  if (right)
+    left = right->left;
+  else
+    left = right = t;
 
-  parent_pre_occ->next = parent_post_occ->next;
+  left->right = t;
+  right->left = t;
+  t->left = left;
+  t->right = right;
 
-  if (parent_post_occ == parent_node->last)
-    parent_node->last = parent_pre_occ;
+  father->son = t;
 
-  pool_free (forest->occur_pool, parent_post_occ);
-  return 1;
+#ifdef DEBUG_ET
+  et_check_tree_sanity (rmost);
+  record_path_before (rmost);
+#endif
 }
 
-/* Return the parent of the NODE if any, NULL otherwise.  */
-et_forest_node_t
-et_forest_parent (et_forest_t forest ATTRIBUTE_UNUSED, et_forest_node_t node)
+/* Splits the edge from T to its father.  */
+
+void
+et_split (struct et_node *t)
 {
-  splay (node->first);
+  struct et_node *father = t->father;
+  struct et_occ *r, *l, *rmost, *p_occ;
 
-  if (node->first->left)
-    return find_rightmost_node (node->first->left)->node;
-  else
-    return 0;
-}
+  /* Update the path represented by the splay tree.  */
+  rmost = t->rightmost_occ;
+  et_splay (rmost);
 
+  for (r = rmost->next; r->prev; r = r->prev)
+    continue;
+  et_splay (r); 
 
-/* Return nearest common ancestor of NODE1 and NODE2.
-   Return NULL of they are in different trees.  */
-et_forest_node_t
-et_forest_common_ancestor (et_forest_t forest ATTRIBUTE_UNUSED,
-			   et_forest_node_t node1, et_forest_node_t node2)
-{
-  int value1, value2, max_value;
-  et_forest_node_t ancestor;
+  r->prev->parent = NULL;
+  p_occ = t->parent_occ;
+  et_splay (p_occ);
+  t->parent_occ = NULL;
 
-  if (node1 == node2)
-    return node1;
+  l = p_occ->prev;
+  p_occ->next->parent = NULL;
 
-  if (! node1 || ! node2)
-    abort ();
+  set_prev (r, l);
 
-  splay (node1->first);
-  splay (node2->first);
+  et_recomp_min (r);
 
-  if (! node1->first->parent)  /* The two vertices are in different trees.  */
-    return 0;
+  et_splay (rmost);
+  rmost->depth = 0;
+  rmost->min = 0;
 
-  value2 = calculate_value (node2->first);
-  value1 = calculate_value (node1->first);
+  pool_free (et_occurences, p_occ);
 
-  if (value1 < value2)
+  /* Update the tree.  */
+  if (father->son == t)
+    father->son = t->right;
+  if (father->son == t)
+    father->son = NULL;
+  else
     {
-      ancestor = node1;
-      max_value = value2;
+      t->left->right = t->right;
+      t->right->left = t->left;
+    }
+  t->left = t->right = NULL;
+  t->father = NULL;
+
+#ifdef DEBUG_ET
+  et_check_tree_sanity (rmost);
+  record_path_before (rmost);
+
+  et_check_tree_sanity (r);
+  record_path_before (r);
+#endif
+}
+
+/* Finds the nearest common ancestor of the nodes N1 and N2.  */
+
+struct et_node *
+et_nca (struct et_node *n1, struct et_node *n2)
+{
+  struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
+  struct et_occ *l, *r, *ret;
+  int mn;
+
+  if (n1 == n2)
+    return n1;
+
+  et_splay (o1);
+  l = o1->prev;
+  r = o1->next;
+  if (l)
+    l->parent = NULL;
+  if (r)
+    r->parent = NULL;
+  et_splay (o2);
+
+  if (l == o2 || (l && l->parent != NULL))
+    {
+      ret = o2->next;
+
+      set_prev (o1, o2);
+      if (r)
+	r->parent = o1;
     }
   else
     {
-      ancestor = node2;
-      max_value = value1;
+      ret = o2->prev;
+
+      set_next (o1, o2);
+      if (l)
+	l->parent = o1;
     }
 
-  while (calculate_value (ancestor->last) < max_value)
+  if (0 < o2->depth)
     {
-      /* Find parent node.  */
-      splay (ancestor->first);
-      ancestor = find_rightmost_node (ancestor->first->left) ->node;
+      om = o1;
+      mn = o1->depth;
+    }
+  else
+    {
+      om = o2;
+      mn = o2->depth + o1->depth;
     }
 
-  return ancestor;
-}
+#ifdef DEBUG_ET
+  et_check_tree_sanity (o2);
+#endif
 
-/* Return the value pointer of node set during it's creation.  */
-void *
-et_forest_node_value (et_forest_t forest ATTRIBUTE_UNUSED,
-		      et_forest_node_t node)
-{
-  /* Alloc threading NULL as a special node of the forest.  */
-  if (!node)
-    return NULL;
-  return node->value;
+  if (ret && ret->min + o1->depth + o2->depth < mn)
+    return ret->min_occ->of;
+  else
+    return om->of;
 }
 
-/* Find all sons of NODE and store them into ARRAY allocated by the caller.
-   Return number of nodes found.  */
-int
-et_forest_enumerate_sons (et_forest_t forest ATTRIBUTE_UNUSED,
-			  et_forest_node_t node, et_forest_node_t *array)
+/* Checks whether the node UP is an ancestor of the node DOWN.  */
+
+bool
+et_below (struct et_node *down, struct et_node *up)
 {
-  int n = 0;
-  et_forest_occurrence_t occ = node->first, stop = node->last, occ1;
+  struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
+  struct et_occ *l, *r;
+
+  if (up == down)
+    return true;
+
+  et_splay (u);
+  l = u->prev;
+  r = u->next;
+
+  if (!l)
+    return false;
+
+  l->parent = NULL;
+
+  if (r)
+    r->parent = NULL;
 
-  /* Parent is the rightmost node of the left successor.
-     Look for all occurrences having no right successor
-     and lookup the sons.  */
-  while (occ != stop)
+  et_splay (d);
+
+  if (l == d || l->parent != NULL)
     {
-      splay (occ);
-      if (occ->right)
-	{
-          occ1 = find_leftmost_node (occ->right);
-	  if (occ1->node->first == occ1)
-	    array[n++] = occ1->node;
-	}
-      occ = occ->next;
+      if (r)
+	r->parent = u;
+      set_prev (u, d);
+#ifdef DEBUG_ET
+      et_check_tree_sanity (u);
+#endif
     }
-  return n;
+  else
+    {
+      l->parent = u;
+
+      /* In case O1 and O2 are in two different trees, we must just restore the
+	 original state.  */
+      if (r && r->parent != NULL)
+	set_next (u, d);
+      else
+	set_next (u, r);
+
+#ifdef DEBUG_ET
+      et_check_tree_sanity (u);
+#endif
+      return false;
+    }
+
+  if (0 >= d->depth)
+    return false;
+
+  return !d->next || d->next->min + d->depth >= 0;
 }