From f667741c42d3bc8082877638726e4d3a22285431 Mon Sep 17 00:00:00 2001 From: Steven Bosscher Date: Wed, 26 May 2004 22:36:49 +0000 Subject: [PATCH] gimplify.c (compare_case_labels): New function. * 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. From-SVN: r82297 --- gcc/ChangeLog | 14 +++++ gcc/gimplify.c | 50 ++++++++++++------ gcc/stmt.c | 4 +- gcc/tree-cfg.c | 131 ++++++++++++++++++++++++++++++++++++++++------ gcc/tree-gimple.c | 2 + 5 files changed, 165 insertions(+), 36 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 167feba2e2f..5e7738ed12a 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,17 @@ +2004-05-27 Steven Bosscher + + * 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 * cfgcleanup.c (try_optimize_cfg): Do not merge across jumptables. diff --git a/gcc/gimplify.c b/gcc/gimplify.c index b081e5e619b..621569bf593 100644 --- a/gcc/gimplify.c +++ b/gcc/gimplify.c @@ -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)) diff --git a/gcc/stmt.c b/gcc/stmt.c index 330ae5f2b53..7c4c67b3bd7 100644 --- a/gcc/stmt.c +++ b/gcc/stmt.c @@ -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; diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index a8244c6dcf6..5385686ecdd 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -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; } diff --git a/gcc/tree-gimple.c b/gcc/tree-gimple.c index 18bc2f8afa3..e749ec80097 100644 --- a/gcc/tree-gimple.c +++ b/gcc/tree-gimple.c @@ -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 -- 2.30.2