This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] sort and group case labels
- From: Steven Bosscher <steven at gcc dot gnu dot org>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 26 May 2004 00:06:58 +0200
- Subject: [patch] sort and group case labels
- Organization: SUSE Labs
[ sorry if anyone gets this twice. somehow a previous post from my
suse account hasn't made it through after almost an hour... ]
Hi,
The attached patch makes us sort and group case labels at the
tree level. This is necessary for some early expanding of
multiway branches that I'm working on, and en passant it allows
us to replace a linear search with a binary one.
Bootstrapped&tested on x86-64-unknown-linux-gnu. OK?
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 25 May 2004 20:03:01 -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 25 May 2004 20:03:02 -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 25 May 2004 20:03:03 -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,978 ----
free (label_for_bb);
}
+ /* Look for blocks ending in a multiway branc (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 old_labels = SWITCH_LABELS (stmt), new_labels;
+ int old_size = TREE_VEC_LENGTH (old_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. */
+ for (i = 0; i < old_size - 2; i++)
+ {
+ tree base_case, base_high, base_label, type;
+
+ base_case = TREE_VEC_ELT (old_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);
+
+ for (j = i; j < old_size - 2; j++)
+ {
+ tree merge_case = TREE_VEC_ELT (old_labels, j + 1);
+ tree merge_label = CASE_LABEL (merge_case);
+
+ /* 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))))
+ {
+ CASE_HIGH (base_case) = CASE_HIGH (merge_case) ?
+ CASE_HIGH (merge_case) : CASE_LOW (merge_case);
+ TREE_VEC_ELT (old_labels, j + 1) = NULL_TREE;
+ new_size--;
+ }
+ else
+ break;
+ }
+
+ i = j;
+ }
+
+ /* 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);
+ for (i = 0, j = 0; i < new_size; i++)
+ {
+ while (! TREE_VEC_ELT (old_labels, j))
+ j++;
+ TREE_VEC_ELT (new_labels, i) = TREE_VEC_ELT (old_labels, j++);
+ }
+ SWITCH_LABELS (stmt) = new_labels;
+ }
+ }
+ }
/* Checks whether we can merge block B into block A. */
*************** find_taken_edge_switch_expr (basic_block
*** 1940,1963 ****
}
! /* 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;
}
--- 2035,2064 ----
}
! /* 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);
! if (tree_int_cst_compare (CASE_LOW (t), val) > 0)
! high = i;
! else
! low = i;
!
! if (CASE_HIGH (t) == NULL)
{
! /* A singe-valued case label. */
if (tree_int_cst_equal (CASE_LOW (t), val))
return t;
}
*************** find_case_label_for_value (tree switch_e
*** 1970,1978 ****
}
}
- if (!default_case)
- abort ();
-
return default_case;
}
--- 2071,2076 ----
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 25 May 2004 20:03:03 -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