On Wed, Apr 18, 2012 at 12:04 AM, Steven Bosscher <stevenb....@gmail.com> wrote:
> Hello,
>
> This is another step towards moving GIMPLE_SWITCH expansion to an
> earlier point in the pipeline.
>
> With the attached patch, some of the logic from stmt.c:add_case_node()
> is moved to gimplify.c:gimplify_switch_expr(). This includes:
>
> * Code to drop case labels that are out of range for the switch index
> expression. (Actually, I suspect this code hasn't worked properly
> since gimplification was introduced, because the switch index
> expression can be promoted by language specific gimplification, so
> expand_case never actually sees the proper type with the current
> implementation in stmt.c.)
>
> * Code to fold_convert case label values to the right type. I've opted
> to go for folding to the original type of the SWITCH_EXPR, rather than
> to the post-gimplification switch index type.
>
> * Code to canonicalize CASE_LABEL's subnodes, CASE_LOW and CASE_HIGH.
> I've chosen to impose strict requirements that CASE_HIGH > CASE_LOW if
> CASE_HIGH is non-zero. This is different from what add_case_node does,
> but I think it makes sense to go for the minimal representation here:
> The case labels in stmt.c never lived very long (only during expand)
> but GIMPLE_SWITCH statements stay around for much of the compilation
> process and can also be streamed out, etc.
>
> Bootstrapped and tested on powerpc-unknown-linux-gnu. OK for trunk?
>
> Ciao!
> Steven
And this time with the right subject and the right patch attached.
Sorry for the inconvenience!
* targhooks.c (default_case_values_threshold): Fix code style nit.
* stmt.c (add_case_node, expand_case): Move logic to remove/reduce
case range and type folding from here...
* gimplify.c (gimplify_switch_expr): ... to here.
Index: targhooks.c
===================================================================
--- targhooks.c (revision 186526)
+++ targhooks.c (working copy)
@@ -1200,7 +1200,8 @@ default_target_can_inline_p (tree caller, tree cal
this means extra overhead for dispatch tables, which raises the
threshold for using them. */
-unsigned int default_case_values_threshold (void)
+unsigned int
+default_case_values_threshold (void)
{
return (HAVE_casesi ? 4 : 5);
}
Index: stmt.c
===================================================================
--- stmt.c (revision 186526)
+++ stmt.c (working copy)
@@ -1822,66 +1822,25 @@ expand_stack_restore (tree var)
fed to us in descending order from the sorted vector of case labels used
in the tree part of the middle end. So the list we construct is
sorted in ascending order. The bounds on the case range, LOW and HIGH,
- are converted to case's index type TYPE. */
+ are converted to case's index type TYPE. Note that the original type
+ of the case index in the source code is usually "lost" during
+ gimplification due to type promotion, but the case labels retain the
+ original type. */
static struct case_node *
add_case_node (struct case_node *head, tree type, tree low, tree high,
tree label, alloc_pool case_node_pool)
{
- tree min_value, max_value;
struct case_node *r;
- gcc_assert (TREE_CODE (low) == INTEGER_CST);
- gcc_assert (!high || TREE_CODE (high) == INTEGER_CST);
+ gcc_checking_assert (low);
+ gcc_checking_assert (! high || (TREE_TYPE (low) == TREE_TYPE (high)));
- min_value = TYPE_MIN_VALUE (type);
- max_value = TYPE_MAX_VALUE (type);
-
- /* If there's no HIGH value, then this is not a case range; it's
- just a simple case label. But that's just a degenerate case
- range.
- If the bounds are equal, turn this into the one-value case. */
- if (!high || tree_int_cst_equal (low, high))
- {
- /* If the simple case value is unreachable, ignore it. */
- if ((TREE_CODE (min_value) == INTEGER_CST
- && tree_int_cst_compare (low, min_value) < 0)
- || (TREE_CODE (max_value) == INTEGER_CST
- && tree_int_cst_compare (low, max_value) > 0))
- return head;
- low = fold_convert (type, low);
- high = low;
- }
- else
- {
- /* If the entire case range is unreachable, ignore it. */
- if ((TREE_CODE (min_value) == INTEGER_CST
- && tree_int_cst_compare (high, min_value) < 0)
- || (TREE_CODE (max_value) == INTEGER_CST
- && tree_int_cst_compare (low, max_value) > 0))
- return head;
-
- /* If the lower bound is less than the index type's minimum
- value, truncate the range bounds. */
- if (TREE_CODE (min_value) == INTEGER_CST
- && tree_int_cst_compare (low, min_value) < 0)
- low = min_value;
- low = fold_convert (type, low);
-
- /* If the upper bound is greater than the index type's maximum
- value, truncate the range bounds. */
- if (TREE_CODE (max_value) == INTEGER_CST
- && tree_int_cst_compare (high, max_value) > 0)
- high = max_value;
- high = fold_convert (type, high);
- }
-
-
/* Add this label to the chain. Make sure to drop overflow flags. */
r = (struct case_node *) pool_alloc (case_node_pool);
- r->low = build_int_cst_wide (TREE_TYPE (low), TREE_INT_CST_LOW (low),
+ r->low = build_int_cst_wide (type, TREE_INT_CST_LOW (low),
TREE_INT_CST_HIGH (low));
- r->high = build_int_cst_wide (TREE_TYPE (high), TREE_INT_CST_LOW (high),
+ r->high = build_int_cst_wide (type, TREE_INT_CST_LOW (high),
TREE_INT_CST_HIGH (high));
r->code_label = label;
r->parent = r->left = NULL;
@@ -2151,9 +2110,12 @@ expand_case (gimple stmt)
gcc_assert (low);
high = CASE_HIGH (elt);
- /* Discard empty ranges. */
- if (high && tree_int_cst_lt (high, low))
- continue;
+ /* The canonical from of a case label in GIMPLE is that a simple case
+ has an empty CASE_HIGH. For the casesi and tablejump expanders,
+ the back ends want simple cases to have high == low. */
+ gcc_assert (! high || tree_int_cst_lt (low, high));
+ if (! high)
+ high = low;
case_list = add_case_node (case_list, index_type, low, high,
CASE_LABEL (elt), case_node_pool);
@@ -2199,16 +2161,10 @@ expand_case (gimple stmt)
BITMAP_FREE (label_bitmap);
/* cleanup_tree_cfg removes all SWITCH_EXPR with a single
- destination, such as one with a default case only. However,
- it doesn't remove cases that are out of range for the switch
- type, so we may still get a zero here. */
- if (count == 0)
- {
- if (default_label)
- emit_jump (default_label);
- free_alloc_pool (case_node_pool);
- return;
- }
+ destination, such as one with a default case only.
+ It also removes cases that are out of range for the switch
+ type, so we should never get a zero here. */
+ gcc_assert (count > 0);
/* Compute span of values. */
range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
Index: gimplify.c
===================================================================
--- gimplify.c (revision 186526)
+++ gimplify.c (working copy)
@@ -1575,6 +1575,9 @@ gimplify_switch_expr (tree *expr_p, gimple_seq *pr
tree switch_expr = *expr_p;
gimple_seq switch_body_seq = NULL;
enum gimplify_status ret;
+ tree index_type = TREE_TYPE (switch_expr);
+ if (index_type == void_type_node)
+ index_type = TREE_TYPE (SWITCH_COND (switch_expr));
ret = gimplify_expr (&SWITCH_COND (switch_expr), pre_p, NULL, is_gimple_val,
fb_rvalue);
@@ -1585,6 +1588,7 @@ gimplify_switch_expr (tree *expr_p, gimple_seq *pr
{
VEC (tree,heap) *labels;
VEC (tree,heap) *saved_labels;
+ tree min_value, max_value;
tree default_case = NULL_TREE;
size_t i, len;
gimple gimple_switch;
@@ -1593,7 +1597,7 @@ gimplify_switch_expr (tree *expr_p, gimple_seq *pr
be bothered to null out the body too. */
gcc_assert (!SWITCH_LABELS (switch_expr));
- /* save old labels, get new ones from body, then restore the old
+ /* Save old labels, get new ones from body, then restore the old
labels. Save all the things from the switch body to append after. */
saved_labels = gimplify_ctxp->case_labels;
gimplify_ctxp->case_labels = VEC_alloc (tree, heap, 8);
@@ -1603,18 +1607,82 @@ gimplify_switch_expr (tree *expr_p, gimple_seq *pr
gimplify_ctxp->case_labels = saved_labels;
i = 0;
+ min_value = TYPE_MIN_VALUE (index_type);
+ max_value = TYPE_MAX_VALUE (index_type);
while (i < VEC_length (tree, labels))
{
tree elt = VEC_index (tree, labels, i);
tree low = CASE_LOW (elt);
+ tree high = CASE_HIGH (elt);
bool remove_element = FALSE;
+
if (low)
{
- /* Discard empty ranges. */
- tree high = CASE_HIGH (elt);
- if (high && tree_int_cst_lt (high, low))
- remove_element = TRUE;
+ gcc_checking_assert (TREE_CODE (low) == INTEGER_CST);
+ gcc_checking_assert (!high || TREE_CODE (high) == INTEGER_CST);
+
+ /* This is a non-default case label, i.e. it has a value.
+
+ See if the case label is reachable within the range of
+ the index type. Remove out-of-range case values. Turn
+ case ranges into a canonical form (high > low strictly)
+ and convert the case label values to the index type.
+
+ NB: The type of gimple_switch_index() may be the promoted
+ type, but the case labels retain the original type. */
+
+ if (high)
+ {
+ /* This is a case range. Discard empty ranges.
+ If the bounds or the range are equal, turn this
+ into a simple (one-value) case. */
+ int cmp = tree_int_cst_compare (high, low);
+ if (cmp < 0)
+ remove_element = TRUE;
+ else if (cmp == 0)
+ high = NULL_TREE;
+ }
+
+ if (! high)
+ {
+ /* If the simple case value is unreachable, ignore it. */
+ if ((TREE_CODE (min_value) == INTEGER_CST
+ && tree_int_cst_compare (low, min_value) < 0)
+ || (TREE_CODE (max_value) == INTEGER_CST
+ && tree_int_cst_compare (low, max_value) > 0))
+ remove_element = TRUE;
+ else
+ low = fold_convert (index_type, low);
+ }
+ else
+ {
+ /* If the entire case range is unreachable, ignore it. */
+ if ((TREE_CODE (min_value) == INTEGER_CST
+ && tree_int_cst_compare (high, min_value) < 0)
+ || (TREE_CODE (max_value) == INTEGER_CST
+ && tree_int_cst_compare (low, max_value) > 0))
+ remove_element = TRUE;
+ else
+ {
+ /* If the lower bound is less than the index type's
+ minimum value, truncate the range bounds. */
+ if (TREE_CODE (min_value) == INTEGER_CST
+ && tree_int_cst_compare (low, min_value) < 0)
+ low = min_value;
+ low = fold_convert (index_type, low);
+
+ /* If the upper bound is greater than the index type's
+ maximum value, truncate the range bounds. */
+ if (TREE_CODE (max_value) == INTEGER_CST
+ && tree_int_cst_compare (high, max_value) > 0)
+ high = max_value;
+ high = fold_convert (index_type, high);
+ }
+ }
+
+ CASE_LOW (elt) = low;
+ CASE_HIGH (elt) = high;
}
else
{
@@ -1636,25 +1704,21 @@ gimplify_switch_expr (tree *expr_p, gimple_seq *pr
if (!default_case)
{
- tree type = TREE_TYPE (switch_expr);
-
/* If the switch has no default label, add one, so that we jump
around the switch body. If the labels already cover the whole
- range of type, add the default label pointing to one of the
- existing labels. */
- if (type == void_type_node)
- type = TREE_TYPE (SWITCH_COND (switch_expr));
+ range of the switch index_type, add the default label pointing
+ to one of the existing labels. */
if (len
- && INTEGRAL_TYPE_P (type)
- && TYPE_MIN_VALUE (type)
- && TYPE_MAX_VALUE (type)
+ && INTEGRAL_TYPE_P (index_type)
+ && TYPE_MIN_VALUE (index_type)
+ && TYPE_MAX_VALUE (index_type)
&& tree_int_cst_equal (CASE_LOW (VEC_index (tree, labels, 0)),
- TYPE_MIN_VALUE (type)))
+ TYPE_MIN_VALUE (index_type)))
{
tree low, high = CASE_HIGH (VEC_index (tree, labels, len - 1));
if (!high)
high = CASE_LOW (VEC_index (tree, labels, len - 1));
- if (tree_int_cst_equal (high, TYPE_MAX_VALUE (type)))
+ if (tree_int_cst_equal (high, TYPE_MAX_VALUE (index_type)))
{
for (i = 1; i < len; i++)
{
