OSDN Git Service

* gimplify.c (compare_case_labels): New function.
authorsteven <steven@138bc75d-0d04-0410-961f-82ee72b054a4>
Wed, 26 May 2004 22:36:49 +0000 (22:36 +0000)
committersteven <steven@138bc75d-0d04-0410-961f-82ee72b054a4>
Wed, 26 May 2004 22:36:49 +0000 (22:36 +0000)
(gimplify_switch_expr): Sort case labels, and make sure the
last label in the label vector is the default case.
* tree-cfg.c (group_case_labels): New function.
(build_tree_cfg): Cleanup redundant labels and group case labels
before creating edges.
(cleanup_dead_labels): Handle GOTO_EXPRs.
(find_case_label_for_value): Use a binary search to find the
case label for the given value.
* tree-gimple.c: Mention that labels are sorted, and that the
last label must be the default.

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

gcc/ChangeLog
gcc/gimplify.c
gcc/stmt.c
gcc/tree-cfg.c
gcc/tree-gimple.c

index 167feba..5e7738e 100644 (file)
@@ -1,3 +1,17 @@
+2004-05-27  Steven Bosscher  <stevenb@suse.de>
+
+       * gimplify.c (compare_case_labels): New function.
+       (gimplify_switch_expr): Sort case labels, and make sure the
+       last label in the label vector is the default case.
+       * tree-cfg.c (group_case_labels): New function.
+       (build_tree_cfg): Cleanup redundant labels and group case labels
+       before creating edges.
+       (cleanup_dead_labels): Handle GOTO_EXPRs.
+       (find_case_label_for_value): Use a binary search to find the
+       case label for the given value.
+       * tree-gimple.c: Mention that labels are sorted, and that the
+       last label must be the default.
+
 2004-05-27  Jan Hubicka  <jh@suse.cz>
 
        * cfgcleanup.c (try_optimize_cfg): Do not merge across jumptables.
index b081e5e..621569b 100644 (file)
@@ -981,6 +981,19 @@ gimplify_loop_expr (tree *expr_p, tree *pre_p)
   return GS_ALL_DONE;
 }
 
+/* Compare two case labels.  Because the front end should already have
+   made sure that case ranges do not overlap, it is enough to only compare
+   the CASE_LOW values of each case label.  */
+
+static int
+compare_case_labels (const void *p1, const void *p2)
+{
+  tree case1 = *(tree *)p1;
+  tree case2 = *(tree *)p2;
+
+  return tree_int_cst_compare (CASE_LOW (case1), CASE_LOW (case2));
+}
+
 /* Gimplify a SWITCH_EXPR, and collect a TREE_VEC of the labels it can
    branch to.  */
 
@@ -996,8 +1009,7 @@ gimplify_switch_expr (tree *expr_p, tree *pre_p)
   if (SWITCH_BODY (switch_expr))
     {
       varray_type labels, saved_labels;
-      bool saw_default;
-      tree label_vec, t;
+      tree label_vec, default_case = NULL_TREE;
       size_t i, len;
 
       /* If someone can be bothered to fill in the labels, they can
@@ -1014,39 +1026,43 @@ gimplify_switch_expr (tree *expr_p, tree *pre_p)
       gimplify_ctxp->case_labels = saved_labels;
 
       len = VARRAY_ACTIVE_SIZE (labels);
-      saw_default = false;
 
       for (i = 0; i < len; ++i)
        {
-         t = VARRAY_TREE (labels, i);
+         tree t = VARRAY_TREE (labels, i);
          if (!CASE_LOW (t))
            {
-             saw_default = true;
+             /* The default case must be the last label in the list.  */
+             default_case = t;
+             VARRAY_TREE (labels, i) = VARRAY_TREE (labels, len - 1);
+             len--;
              break;
            }
        }
 
-      label_vec = make_tree_vec (len + !saw_default);
+      label_vec = make_tree_vec (len + 1);
       SWITCH_LABELS (*expr_p) = label_vec;
-
-      for (i = 0; i < len; ++i)
-       TREE_VEC_ELT (label_vec, i) = VARRAY_TREE (labels, i);
-
       append_to_statement_list (switch_expr, pre_p);
 
-      /* If the switch has no default label, add one, so that we jump
-        around the switch body.  */
-      if (!saw_default)
+      if (! default_case)
        {
-         t = build (CASE_LABEL_EXPR, void_type_node, NULL_TREE,
-                    NULL_TREE, create_artificial_label ());
-         TREE_VEC_ELT (label_vec, len) = t;
+         /* If the switch has no default label, add one, so that we jump
+            around the switch body.  */
+         default_case = build (CASE_LABEL_EXPR, void_type_node, NULL_TREE,
+                               NULL_TREE, create_artificial_label ());
          append_to_statement_list (SWITCH_BODY (switch_expr), pre_p);
-         *expr_p = build (LABEL_EXPR, void_type_node, CASE_LABEL (t));
+         *expr_p = build (LABEL_EXPR, void_type_node,
+                          CASE_LABEL (default_case));
        }
       else
        *expr_p = SWITCH_BODY (switch_expr);
 
+      qsort (&VARRAY_TREE (labels, 0), len, sizeof (tree),
+            compare_case_labels);
+      for (i = 0; i < len; ++i)
+       TREE_VEC_ELT (label_vec, i) = VARRAY_TREE (labels, i);
+      TREE_VEC_ELT (label_vec, len) = default_case;
+
       SWITCH_BODY (switch_expr) = NULL;
     }
   else if (!SWITCH_LABELS (switch_expr))
index 330ae5f..7c4c67b 100644 (file)
@@ -4434,8 +4434,8 @@ bool lshift_cheap_p (void)
    number of case nodes, i.e. the node with the most cases gets
    tested first.  */
 
-static
-int case_bit_test_cmp (const void *p1, const void *p2)
+static int
+case_bit_test_cmp (const void *p1, const void *p2)
 {
   const struct case_bit_test *d1 = p1;
   const struct case_bit_test *d2 = p2;
index a8244c6..5385686 100644 (file)
@@ -100,6 +100,7 @@ static void tree_cfg2vcg (FILE *);
 static void tree_merge_blocks (basic_block, basic_block);
 static bool tree_can_merge_blocks_p (basic_block, basic_block);
 static void remove_bb (basic_block);
+static void group_case_labels (void);
 static void cleanup_dead_labels (void);
 static bool cleanup_control_flow (void);
 static bool cleanup_control_expr_graph (basic_block, block_stmt_iterator);
@@ -160,6 +161,14 @@ build_tree_cfg (tree *tp)
   /* Adjust the size of the array.  */
   VARRAY_GROW (basic_block_info, n_basic_blocks);
 
+  /* To speed up statement iterator walks, we first purge dead labels.  */
+  cleanup_dead_labels ();
+
+  /* Group case nodes to reduce the number of edges.
+     We do this after cleaning up dead labels because otherwise we miss
+     a lot of obvious case merging opportunities.  */
+  group_case_labels ();
+
   /* Create the edges of the flowgraph.  */
   make_edges ();
 
@@ -470,9 +479,6 @@ make_edges (void)
      builder inserted for completeness.  */
   remove_fake_edges ();
 
-  /* To speed up statement iterator walks, we first purge dead labels.  */
-  cleanup_dead_labels ();
-
   /* Clean up the graph and warn for unreachable code.  */
   cleanup_tree_cfg ();
 }
@@ -842,6 +848,17 @@ cleanup_dead_labels (void)
            break;
          }
 
+       /* We have to handle GOTO_EXPRs until they're removed, and we don't
+          remove them until after we've created the CFG edges.  */
+       case GOTO_EXPR:
+         {
+           tree label = GOTO_DESTINATION (stmt);
+           if (! computed_goto_p (stmt))
+             GOTO_DESTINATION (stmt) =
+               label_for_bb[label_to_block (label)->index];
+           break;
+         }
+
        default:
          break;
       }
@@ -878,6 +895,80 @@ cleanup_dead_labels (void)
   free (label_for_bb);
 }
 
+/* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
+   and scan the sorted vector of cases.  Combine the ones jumping to the
+   same label.
+   Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
+
+static void
+group_case_labels (void)
+{
+  basic_block bb;
+
+  FOR_EACH_BB (bb)
+    {
+      tree stmt = last_stmt (bb);
+      if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
+       {
+         tree labels = SWITCH_LABELS (stmt);
+         int old_size = TREE_VEC_LENGTH (labels);
+         int i, j, new_size = old_size;
+
+         /* Look for possible opportunities to merge cases.
+            Ignore the last element of the label vector because it
+            must be the default case.  */
+          i = 0;
+         while (i < old_size - 2)
+           {
+             tree base_case, base_label, base_high, type;
+             base_case = TREE_VEC_ELT (labels, i);
+
+             if (! base_case)
+               abort ();
+
+             type = TREE_TYPE (CASE_LOW (base_case));
+             base_label = CASE_LABEL (base_case);
+             base_high = CASE_HIGH (base_case) ?
+               CASE_HIGH (base_case) : CASE_LOW (base_case);
+
+             /* Try to merge case labels.  Break out when we reach the end
+                of the label vector or when we cannot merge the next case
+                label with the current one.  */
+             while (i < old_size - 2)
+               {
+                 tree merge_case = TREE_VEC_ELT (labels, ++i);
+                 tree merge_label = CASE_LABEL (merge_case);
+                 tree t = int_const_binop (PLUS_EXPR, base_high,
+                                           integer_one_node, 1);
+
+                 /* Merge the cases if they jump to the same place,
+                    and their ranges are consecutive.  */
+                 if (merge_label == base_label
+                     && tree_int_cst_equal (CASE_LOW (merge_case), t))
+                   {
+                     base_high = CASE_HIGH (merge_case) ?
+                       CASE_HIGH (merge_case) : CASE_LOW (merge_case);
+                     CASE_HIGH (base_case) = base_high;
+                     TREE_VEC_ELT (labels, i) = NULL_TREE;
+                     new_size--;
+                   }
+                 else
+                   break;
+               }
+           }
+
+         /* Compress the case labels in the label vector, and adjust the
+            length of the vector.  */
+         for (i = 0, j = 0; i < new_size; i++)
+           {
+             while (! TREE_VEC_ELT (labels, j))
+               j++;
+             TREE_VEC_ELT (labels, i) = TREE_VEC_ELT (labels, j++);
+           }
+         TREE_VEC_LENGTH (labels) = new_size;
+       }
+    }
+}
 
 /* Checks whether we can merge block B into block A.  */
 
@@ -1940,39 +2031,45 @@ find_taken_edge_switch_expr (basic_block bb, tree val)
 }
 
 
-/* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.  */
+/* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.
+   We can make optimal use here of the fact that the case labels are
+   sorted: We can do a binary search for a case matching VAL.  */
 
 static tree
 find_case_label_for_value (tree switch_expr, tree val)
 {
   tree vec = SWITCH_LABELS (switch_expr);
-  size_t i, n = TREE_VEC_LENGTH (vec);
-  tree default_case = NULL;
+  size_t low, high, n = TREE_VEC_LENGTH (vec);
+  tree default_case = TREE_VEC_ELT (vec, n - 1);
 
-  for (i = 0; i < n; ++i)
+  for (low = -1, high = n - 1; high - low > 1; )
     {
+      size_t i = (high + low) / 2;
       tree t = TREE_VEC_ELT (vec, i);
+      int cmp;
 
-      if (CASE_LOW (t) == NULL)
-       default_case = t;
-      else if (CASE_HIGH (t) == NULL)
+      /* Cache the result of comparing CASE_LOW and val.  */
+      cmp = tree_int_cst_compare (CASE_LOW (t), val);
+
+      if (cmp > 0)
+       high = i;
+      else
+       low = i;
+
+      if (CASE_HIGH (t) == NULL)
        {
-         /* A `normal' case label.  */
-         if (tree_int_cst_equal (CASE_LOW (t), val))
+         /* A singe-valued case label.  */
+         if (cmp == 0)
            return t;
        }
       else
        {
          /* A case range.  We can only handle integer ranges.  */
-         if (tree_int_cst_compare (CASE_LOW (t), val) <= 0
-             && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
+         if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
            return t;
        }
     }
 
-  if (!default_case)
-    abort ();
-
   return default_case;
 }
 
index 18bc2f8..e749ec8 100644 (file)
@@ -73,6 +73,8 @@ Boston, MA 02111-1307, USA.  */
        op1 -> stmt
        op2 -> array of case labels (as LABEL_DECLs?)
          FIXME: add case value info
+       The SWITCH_LABELS (op2) are sorted in ascending order, and the
+       last label in the vector is always the default case.
    jump-stmt:
        GOTO_EXPR
          op0 -> LABEL_DECL | '*' ID