tree-cfg.c (edge_to_cases): Renamed from edge_to_case_leader.

	* tree-cfg.c (edge_to_cases): Renamed from edge_to_case_leader.
	(edge_to_cases_elt): Renamed from edge_to_case_leader.
	(edge_to_cases_hash): Renamed from edge_to_case_leader_hash.
	(edge_to_cases_eq): Renamed from edge_to_case_leader_eq.
	(edge_to_cases_cleanup, recording_case_labels_p): New functions.
	(get_cases_for_edge): New function.
	(start_recording_case_labels, end_recording_case_labels): Similarly.
	(record_switch_edge): Don't muck with the CASE_LABEL.  Instead
	chain equivalent CASE_LABEL_EXPRs together.
	(get_case_leader_for_edge, get_case_leader_for_edge_hash): Kill.
	(make_switch_expr_edges): Do not record edge/cases here.
	(cleanup_tree_cfg): Record cases around the call to thread_jumps.
	(split_critical_edges): Record cases around the edge splitting code.
	(cleanup_dead_labels): Use CASE_LABEL again.
	(tree_redirect_edge_and_branch): If we have a mapping from edge
	to cases, use it to handle redirections.  Else do it the slow way.
	* tree.h (CASE_LEADER_OR_LABEL): Kill.
	(CASE_LABEL): Revert to just looking at the tree's second operand.
	* tree.c (get_case_label): Kill.

From-SVN: r90817

4 files changed, 181 insertions, 122 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 6bf212a..12dfd42 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,25 @@
+2004-11-17  Jeff Law  <law@redhat.com>
+
+	* tree-cfg.c (edge_to_cases): Renamed from edge_to_case_leader.
+	(edge_to_cases_elt): Renamed from edge_to_case_leader.
+	(edge_to_cases_hash): Renamed from edge_to_case_leader_hash.
+	(edge_to_cases_eq): Renamed from edge_to_case_leader_eq.
+	(edge_to_cases_cleanup, recording_case_labels_p): New functions.
+	(get_cases_for_edge): New function.
+	(start_recording_case_labels, end_recording_case_labels): Similarly.
+	(record_switch_edge): Don't muck with the CASE_LABEL.  Instead
+	chain equivalent CASE_LABEL_EXPRs together.
+	(get_case_leader_for_edge, get_case_leader_for_edge_hash): Kill.
+	(make_switch_expr_edges): Do not record edge/cases here.
+	(cleanup_tree_cfg): Record cases around the call to thread_jumps.
+	(split_critical_edges): Record cases around the edge splitting code.
+	(cleanup_dead_labels): Use CASE_LABEL again.
+	(tree_redirect_edge_and_branch): If we have a mapping from edge
+	to cases, use it to handle redirections.  Else do it the slow way.
+	* tree.h (CASE_LEADER_OR_LABEL): Kill.
+	(CASE_LABEL): Revert to just looking at the tree's second operand.
+	* tree.c (get_case_label): Kill.
+
 2004-11-17  Diego Novillo  <dnovillo@redhat.com>
 
 	PR tree-optimization/18307
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index f9be0b3..d771995 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -58,29 +58,32 @@ static const int initial_cfg_capacity = 20;
    building of the CFG in code with lots of gotos.  */
 static GTY(()) varray_type label_to_block_map;
 
-/* This hash table allows us to efficiently lookup the one and only one
-   CASE_LABEL_EXPR which contains the LABEL_DECL for the target block
-   of one or more case statements.  Efficient access to this node
-   allows us to efficiently update the case vector in response to
-   edge redirections and similar operations. 
+/* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
+   which use a particular edge.  The CASE_LABEL_EXPRs are chained together
+   via their TREE_CHAIN field, which we clear after we're done with the
+   hash table to prevent problems with duplication of SWITCH_EXPRs.
 
-   Right now this is only used to set up case label leaders.  In the
-   future we hope to make this table more persistent and use it to
-   more efficiently update case labels.  */
+   Access to this list of CASE_LABEL_EXPRs allows us to efficiently
+   update the case vector in response to edge redirections.
 
-struct edge_to_case_leader_elt
+   Right now this table is set up and torn down at key points in the
+   compilation process.  It would be nice if we could make the table
+   more persistent.  The key is getting notification of changes to
+   the CFG (particularly edge removal, creation and redirection).  */
+
+struct edge_to_cases_elt
 {
   /* The edge itself.  Necessary for hashing and equality tests.  */
   edge e;
 
-  /* The "leader" for all the CASE_LABEL_EXPRs which transfer control
-     to E->dest.  When we change the destination of E, we will need to
-     update the CASE_LEADER_OR_LABEL of this CASE_LABEL_EXPR (and no
-     others).  */
-  tree case_label;
+  /* The case labels associated with this edge.  We link these up via
+     their TREE_CHAIN field, then we wipe out the TREE_CHAIN fields
+     when we destroy the hash table.  This prevents problems when copying
+     SWITCH_EXPRs.  */
+  tree case_labels;
 };
 
-static htab_t edge_to_case_leader;
+static htab_t edge_to_cases;
 
 /* CFG statistics.  */
 struct cfg_stats_d
@@ -601,44 +604,95 @@ make_cond_expr_edges (basic_block bb)
   make_edge (bb, else_bb, EDGE_FALSE_VALUE);
 }
 
-/* Hashing routine for EDGE_TO_CASE_LEADER.  */
+/* Hashing routine for EDGE_TO_CASES.  */
 
 static hashval_t
-edge_to_case_leader_hash (const void *p)
+edge_to_cases_hash (const void *p)
 {
-  edge e = ((struct edge_to_case_leader_elt *)p)->e;
+  edge e = ((struct edge_to_cases_elt *)p)->e;
 
   /* Hash on the edge itself (which is a pointer).  */
   return htab_hash_pointer (e);
 }
 
-/* Equality routine for EDGE_TO_CASE_LEADER, edges are unique, so testing
+/* Equality routine for EDGE_TO_CASES, edges are unique, so testing
    for equality is just a pointer comparison.  */
 
 static int
-edge_to_case_leader_eq (const void *p1, const void *p2)
+edge_to_cases_eq (const void *p1, const void *p2)
 {
-  edge e1 = ((struct edge_to_case_leader_elt *)p1)->e;
-  edge e2 = ((struct edge_to_case_leader_elt *)p2)->e;
+  edge e1 = ((struct edge_to_cases_elt *)p1)->e;
+  edge e2 = ((struct edge_to_cases_elt *)p2)->e;
 
   return e1 == e2;
 }
 
+/* Called for each element in the hash table (P) as we delete the
+   edge to cases hash table.
+
+   Clear all the TREE_CHAINs to prevent problems with copying of 
+   SWITCH_EXPRs and structure sharing rules, then free the hash table
+   element.  */
+
+static void
+edge_to_cases_cleanup (void *p)
+{
+  struct edge_to_cases_elt *elt = p;
+  tree t, next;
+
+  for (t = elt->case_labels; t; t = next)
+    {
+      next = TREE_CHAIN (t);
+      TREE_CHAIN (t) = NULL;
+    }
+  free (p);
+}
+
+/* Start recording information mapping edges to case labels.  */
+
+static void
+start_recording_case_labels (void)
+{
+  gcc_assert (edge_to_cases == NULL);
+
+  edge_to_cases = htab_create (37,
+			       edge_to_cases_hash,
+			       edge_to_cases_eq,
+			       edge_to_cases_cleanup);
+}
+
+/* Return nonzero if we are recording information for case labels.  */
+
+static bool
+recording_case_labels_p (void)
+{
+  return (edge_to_cases != NULL);
+}
+
+/* Stop recording information mapping edges to case labels and
+   remove any information we have recorded.  */
+static void
+end_recording_case_labels (void)
+{
+  htab_delete (edge_to_cases);
+  edge_to_cases = NULL;
+}
+
 /* Record that CASE_LABEL (a CASE_LABEL_EXPR) references edge E.  */
 
 static void
 record_switch_edge (edge e, tree case_label)
 {
-  struct edge_to_case_leader_elt *elt;
+  struct edge_to_cases_elt *elt;
   void **slot;
 
   /* Build a hash table element so we can see if E is already
      in the table.  */
-  elt = xmalloc (sizeof (struct edge_to_case_leader_elt));
+  elt = xmalloc (sizeof (struct edge_to_cases_elt));
   elt->e = e;
-  elt->case_label = case_label;
+  elt->case_labels = case_label;
 
-  slot = htab_find_slot (edge_to_case_leader, elt, INSERT);
+  slot = htab_find_slot (edge_to_cases, elt, INSERT);
 
   if (*slot == NULL)
     {
@@ -652,70 +706,56 @@ record_switch_edge (edge e, tree case_label)
       free (elt);
 
       /* Get the entry stored in the hash table.  */
-      elt = (struct edge_to_case_leader_elt *) *slot;
+      elt = (struct edge_to_cases_elt *) *slot;
 
-      /* Make ELT->case_label the leader for CASE_LABEL.  */
-      CASE_LEADER_OR_LABEL (case_label) = elt->case_label;
+      /* Add it to the chain of CASE_LABEL_EXPRs referencing E.  */
+      TREE_CHAIN (case_label) = elt->case_labels;
+      elt->case_labels = case_label;
     }
 }
 
-/* Subroutine of get_case_leader_for_edge; returns the case leader for the
-   chain of CASE_LABEL_EXPRs associated with E using a hash table lookup.  */
+/* If we are inside a {start,end}_recording_cases block, then return
+   a chain of CASE_LABEL_EXPRs from T which reference E.
+
+   Otherwise return NULL.  */
 
 static tree
-get_case_leader_for_edge_hash (edge e)
+get_cases_for_edge (edge e, tree t)
 {
-  struct edge_to_case_leader_elt elt, *elt_p;
+  struct edge_to_cases_elt elt, *elt_p;
   void **slot;
+  size_t i, n;
+  tree vec;
 
+  /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
+     chains available.  Return NULL so the caller can detect this case.  */
+  if (!recording_case_labels_p ())
+    return NULL;
+  
+restart:
   elt.e = e;
-  elt.case_label = NULL;
-  slot = htab_find_slot (edge_to_case_leader, &elt, NO_INSERT);
+  elt.case_labels = NULL;
+  slot = htab_find_slot (edge_to_cases, &elt, NO_INSERT);
 
   if (slot)
     {
-      tree t;
-
-      elt_p = (struct edge_to_case_leader_elt *)*slot;
-      t = elt_p->case_label;
-
-      while (TREE_CODE (CASE_LEADER_OR_LABEL (t)) == CASE_LABEL_EXPR)
-	t = CASE_LEADER_OR_LABEL (t);
-      return t;
+      elt_p = (struct edge_to_cases_elt *)*slot;
+      return elt_p->case_labels;
     }
 
-  return NULL;
-}
-
-/* Given an edge E, return the case leader for the chain of CASE_LABEL_EXPRs
-   which use E.  */
+  /* If we did not find E in the hash table, then this must be the first
+     time we have been queried for information about E & T.  Add all the
+     elements from T to the hash table then perform the query again.  */
 
-static tree
-get_case_leader_for_edge (edge e)
-{
-  tree vec, stmt;
-  size_t i, n;
-
-  /* If we have a hash table, then use it as it's significantly faster.  */
-  if (edge_to_case_leader)
-    return get_case_leader_for_edge_hash (e);
-
-  /* No hash table.  We have to walk the case vector.  */
-  stmt = bsi_stmt (bsi_last (e->src));
-  vec = SWITCH_LABELS (stmt);
+  vec = SWITCH_LABELS (t);
   n = TREE_VEC_LENGTH (vec);
-
   for (i = 0; i < n; i++)
     {
-      tree elt = TREE_VEC_ELT (vec, i);
-      tree t = CASE_LEADER_OR_LABEL (elt);
-
-      if (TREE_CODE (t) == LABEL_DECL
-	  && label_to_block (t) == e->dest)
-	return elt;
+      tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
+      basic_block label_bb = label_to_block (lab);
+      record_switch_edge (find_edge (e->src, label_bb), TREE_VEC_ELT (vec, i));
     }
-
-  abort ();
+  goto restart;
 }
 
 /* Create the edges for a SWITCH_EXPR starting at block BB.
@@ -732,22 +772,12 @@ make_switch_expr_edges (basic_block bb)
   vec = SWITCH_LABELS (entry);
   n = TREE_VEC_LENGTH (vec);
 
-  edge_to_case_leader
-    = htab_create (n, edge_to_case_leader_hash, edge_to_case_leader_eq, free);
-
   for (i = 0; i < n; ++i)
     {
       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
       basic_block label_bb = label_to_block (lab);
-      edge e = make_edge (bb, label_bb, 0);
-
-      if (!e)
-	e = find_edge (bb, label_bb);
-
-      record_switch_edge (e, TREE_VEC_ELT (vec, i));
+      make_edge (bb, label_bb, 0);
     }
-  htab_delete (edge_to_case_leader);
-  edge_to_case_leader = NULL;
 }
 
 
@@ -869,7 +899,13 @@ cleanup_tree_cfg (void)
 
   retval = cleanup_control_flow ();
   retval |= delete_unreachable_blocks ();
+
+  /* thread_jumps can redirect edges out of SWITCH_EXPRs, which can get
+     expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
+     mappings around the call to thread_jumps.  */
+  start_recording_case_labels ();
   retval |= thread_jumps ();
+  end_recording_case_labels ();
 
 #ifdef ENABLE_CHECKING
   if (retval)
@@ -1019,7 +1055,7 @@ cleanup_dead_labels (void)
 	      {
 		tree elt = TREE_VEC_ELT (vec, i);
 		tree label = main_block_label (CASE_LABEL (elt));
-		CASE_LEADER_OR_LABEL (elt) = label;
+		CASE_LABEL (elt) = label;
 	      }
 	    break;
 	  }
@@ -4281,30 +4317,47 @@ tree_redirect_edge_and_branch (edge e, basic_block dest)
 
     case SWITCH_EXPR:
       {
-	edge e2;
-
-        /* We need to update the LABEL_DECL in the switch vector to
-	   reflect the edge redirection.
+        tree cases = get_cases_for_edge (e, stmt);
+	edge e2 = find_edge (e->src, dest);
 
-	   There is precisely one CASE_LABEL_EXPR in the switch vector
-	   which needs updating.  Either its label needs to be updated
-	   or it needs to be directed to a new case leader.  */
-	e2 = find_edge (e->src, dest);
-	if (e2)
+	/* If we have a list of cases associated with E, then use it
+	   as it's a lot faster than walking the entire case vector.  */
+	if (cases)
 	  {
-	    /* In this case we need to change the case leader for the
-	       current leader of E to be the case leader for E2.  */
-	    tree e_leader = get_case_leader_for_edge (e);
-	    tree e2_leader = get_case_leader_for_edge (e2);
-	    CASE_LEADER_OR_LABEL (e_leader) = e2_leader;
+	    tree last, first;
+
+	    first = cases;
+	    while (cases)
+	      {
+		last = cases;
+		CASE_LABEL (cases) = label;
+		cases = TREE_CHAIN (cases);
+	      }
+
+	    /* If there was already an edge in the CFG, then we need
+	       to move all the cases associated with E to E2.  */
+	    if (e2)
+	      {
+		tree cases2 = get_cases_for_edge (e2, stmt);
+
+		TREE_CHAIN (last) = TREE_CHAIN (cases2);
+		TREE_CHAIN (cases2) = first;
+	      }
 	  }
 	else
 	  {
-	    /* No edge exists from E->src to DEST, so we will simply
-	       change E->dest.  The case leader does not change, but
-	       the LABEL_DECL for the leader does change.  */
-	    CASE_LEADER_OR_LABEL (get_case_leader_for_edge (e)) = label;
+	    tree vec = SWITCH_LABELS (stmt);
+	    size_t i, n = TREE_VEC_LENGTH (vec);
+
+	    for (i = 0; i < n; i++)
+	      {
+		tree elt = TREE_VEC_ELT (vec, i);
+
+		if (label_to_block (CASE_LABEL (elt)) == e->dest)
+		  CASE_LABEL (elt) = label;
+	      }
 	  }
+
 	break;
       }
 
@@ -5320,6 +5373,10 @@ split_critical_edges (void)
   edge e;
   edge_iterator ei;
 
+  /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
+     expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
+     mappings around the calls to split_edge.  */
+  start_recording_case_labels ();
   FOR_ALL_BB (bb)
     {
       FOR_EACH_EDGE (e, ei, bb->succs)
@@ -5328,6 +5385,7 @@ split_critical_edges (void)
 	    split_edge (e);
 	  }
     }
+  end_recording_case_labels ();
 }
 
 struct tree_opt_pass pass_split_crit_edges = 
diff --git a/gcc/tree.c b/gcc/tree.c
index 654ce78..32ec8a5 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -6061,19 +6061,6 @@ signed_type_for (tree type)
   return lang_hooks.types.signed_type (type);
 }
 
-/* Return the LABEL_DECL associated with T, which must be a 
-   CASE_LABEL_EXPR.  This will walk through any CASE_LABEL_EXPRs
-   appearing in operand 2 until it finds a CASE_LABEL_EXPR with
-   a LABEL_DECL in operand 2.  */
-
-tree
-get_case_label (tree t)
-{
-  while (TREE_CODE (CASE_LEADER_OR_LABEL (t)) == CASE_LABEL_EXPR)
-    t = CASE_LEADER_OR_LABEL (t);
-  return CASE_LEADER_OR_LABEL (t);
-}
-
 /* Returns the largest value obtainable by casting something in INNER type to
    OUTER type.  */
 
diff --git a/gcc/tree.h b/gcc/tree.h
index a8670d9..83dd4ca 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -1231,15 +1231,7 @@ struct tree_vec GTY(())
    of a case label, respectively.  */
 #define CASE_LOW(NODE)          	TREE_OPERAND ((NODE), 0)
 #define CASE_HIGH(NODE)         	TREE_OPERAND ((NODE), 1)
-
-/* Operand 2 has two uses, it may either be a LABEL_DECL node or a
-   another CASE_LABEL_EXPR node.  This accessor gets direct access
-   to that operand.  Use it when you want to assign a value to
-   operand 2 or when you want to conditionalize actions based on
-   whether operand 2 is a LABEL_DECL or CASE_LABEL_EXPR.  */
-#define CASE_LEADER_OR_LABEL(NODE)	TREE_OPERAND ((NODE), 2)
-
-#define CASE_LABEL(NODE) get_case_label (NODE)
+#define CASE_LABEL(NODE)		TREE_OPERAND ((NODE), 2)
 
 /* The operands of a BIND_EXPR.  */
 #define BIND_EXPR_VARS(NODE) (TREE_OPERAND (BIND_EXPR_CHECK (NODE), 0))