This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] sort and group case labels
On Wednesday 26 May 2004 20:52, Richard Henderson wrote:
> On Wed, May 26, 2004 at 12:06:58AM +0200, Steven Bosscher wrote:
> > + /* 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),
> > + fold (build (PLUS_EXPR, type,
> > + base_high,
> > + integer_one_node)))
> > + /* An overflow is not consecutive. */
> > + && tree_int_cst_lt (base_high,
> > + fold (build (PLUS_EXPR, type,
> > + base_high,
> > + integer_one_node))))
>
> Use int_const_binop instead, and use it only once.
OK.
> > + /* Copy the grouped old case labels into the new label vector,
> > + and replace the old label vector in this switch statement. */
> > + new_labels = make_tree_vec (new_size);
>
> Why allocating a new vector rather than compressing the existing?
> Can modify TREE_VEC_LENGTH.
I didn't know one could do that.
Take 2 attached, same bootstrap, same testing, same ChangeLog.
Gr.
Steven
* 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.
Index: gimplify.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gimplify.c,v
retrieving revision 2.5
diff -c -3 -p -r2.5 gimplify.c
*** gimplify.c 21 May 2004 22:00:14 -0000 2.5
--- gimplify.c 26 May 2004 20:42:28 -0000
*************** gimplify_loop_expr (tree *expr_p, tree *
*** 981,986 ****
--- 981,999 ----
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. */
*************** gimplify_switch_expr (tree *expr_p, tree
*** 996,1003 ****
if (SWITCH_BODY (switch_expr))
{
varray_type labels, saved_labels;
! bool saw_default;
! tree label_vec, t;
size_t i, len;
/* If someone can be bothered to fill in the labels, they can
--- 1009,1015 ----
if (SWITCH_BODY (switch_expr))
{
varray_type labels, saved_labels;
! tree label_vec, default_case = NULL_TREE;
size_t i, len;
/* If someone can be bothered to fill in the labels, they can
*************** gimplify_switch_expr (tree *expr_p, tree
*** 1014,1052 ****
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);
if (!CASE_LOW (t))
{
! saw_default = true;
break;
}
}
! label_vec = make_tree_vec (len + !saw_default);
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)
! {
! t = build (CASE_LABEL_EXPR, void_type_node, NULL_TREE,
! NULL_TREE, create_artificial_label ());
! TREE_VEC_ELT (label_vec, len) = t;
append_to_statement_list (SWITCH_BODY (switch_expr), pre_p);
! *expr_p = build (LABEL_EXPR, void_type_node, CASE_LABEL (t));
}
else
*expr_p = SWITCH_BODY (switch_expr);
SWITCH_BODY (switch_expr) = NULL;
}
else if (!SWITCH_LABELS (switch_expr))
--- 1026,1068 ----
gimplify_ctxp->case_labels = saved_labels;
len = VARRAY_ACTIVE_SIZE (labels);
for (i = 0; i < len; ++i)
{
! tree t = VARRAY_TREE (labels, i);
if (!CASE_LOW (t))
{
! /* 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 + 1);
SWITCH_LABELS (*expr_p) = label_vec;
append_to_statement_list (switch_expr, pre_p);
! if (! default_case)
! {
! /* 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 (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: stmt.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/stmt.c,v
retrieving revision 1.355
diff -c -3 -p -r1.355 stmt.c
*** stmt.c 19 May 2004 06:26:21 -0000 1.355
--- stmt.c 26 May 2004 20:42:29 -0000
*************** bool lshift_cheap_p (void)
*** 4434,4441 ****
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)
{
const struct case_bit_test *d1 = p1;
const struct case_bit_test *d2 = p2;
--- 4434,4441 ----
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)
{
const struct case_bit_test *d1 = p1;
const struct case_bit_test *d2 = p2;
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.3
diff -c -3 -p -r2.3 tree-cfg.c
*** tree-cfg.c 19 May 2004 19:30:27 -0000 2.3
--- tree-cfg.c 26 May 2004 20:42:30 -0000
*************** static void tree_cfg2vcg (FILE *);
*** 100,105 ****
--- 100,106 ----
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);
*************** build_tree_cfg (tree *tp)
*** 160,165 ****
--- 161,174 ----
/* 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 ();
*************** make_edges (void)
*** 470,478 ****
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 ();
}
--- 479,484 ----
*************** cleanup_dead_labels (void)
*** 842,847 ****
--- 848,864 ----
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;
}
*************** cleanup_dead_labels (void)
*** 878,883 ****
--- 895,974 ----
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;
+ }
+ }
+
+ /* Copy the grouped old case labels into the new label vector,
+ and replace the old label vector in this switch statement. */
+ 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. */
*************** find_taken_edge_switch_expr (basic_block
*** 1940,1978 ****
}
! /* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for 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;
! for (i = 0; i < n; ++i)
{
tree t = TREE_VEC_ELT (vec, i);
! if (CASE_LOW (t) == NULL)
! default_case = t;
! else if (CASE_HIGH (t) == NULL)
{
! /* A `normal' case label. */
! if (tree_int_cst_equal (CASE_LOW (t), val))
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)
return t;
}
}
- if (!default_case)
- abort ();
-
return default_case;
}
--- 2031,2075 ----
}
! /* 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 low, high, n = TREE_VEC_LENGTH (vec);
! tree default_case = TREE_VEC_ELT (vec, n - 1);
! for (low = -1, high = n - 1; high - low > 1; )
{
+ size_t i = (high + low) / 2;
tree t = TREE_VEC_ELT (vec, i);
+ int cmp;
! /* 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 singe-valued case label. */
! if (cmp == 0)
return t;
}
else
{
/* A case range. We can only handle integer ranges. */
! if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
return t;
}
}
return default_case;
}
Index: tree-gimple.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-gimple.c,v
retrieving revision 2.2
diff -c -3 -p -r2.2 tree-gimple.c
*** tree-gimple.c 24 May 2004 16:37:17 -0000 2.2
--- tree-gimple.c 26 May 2004 20:42:30 -0000
*************** Boston, MA 02111-1307, USA. */
*** 73,78 ****
--- 73,80 ----
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