[PATCH] Fix PR14495 (2/2)
Richard Guenther
rguenther@suse.de
Fri Mar 28 21:25:00 GMT 2008
This implements removal of never reached case labels in switch
statements in the VRP pass. In particular this will also fix
PR34793 where we produce "may be used uninitialized" warnings
because CFG construction always inserts a default case label
which then feeds an undefined PHI argument ... thus this patch
also gets somewhat big as expansion and case label grouping
need to deal with switch stmts without a default label.
For small switch statements omitting the default label results
in non-insignificant code size savings, as often range checking
is present before these and most sources have a default case
label just to silence the compiler warning that not all possible
input values are covered. I measured compile-time effects on
cc1files where I can measure nothing but noise.
Bootstrapped and tested on x86_64-unknown-linux-gnu, ok
for mainline?
Thanks,
Richard.
2007-04-16 Richard Guenther <rguenther@suse.de>
PR tree-optimization/14495
PR tree-optimization/34793
* tree-vrp.c (struct switch_update): New structure.
(to_remove_edges, to_update_switch_stmts): New VECs.
(simplify_switch_using_ranges): New function. Remove not taken
case labels and edges.
(simplify_stmt_using_ranges): Call it.
(identify_jump_threads): Mark edges we have queued for removal
so we don't thread them.
(execute_vrp): Remove edges queued for removal, update SWITCH_STMT
case label vector.
* tree-cfg.c (group_case_labels): Deal with missing default label.
(tree_verify_flow_info): Allow missing default label.
* stmt.c (emit_case_bit_tests): Deal with NULL default_label.
(emit_case_nodes): Likewise.
(expand_case): Do not rely on the default label to be present.
* expr.c (try_casesi): Deal with NULL default_label.
(do_tablejump): Likewise.
* gcc.dg/tree-ssa/vrp39.c: New testcase.
* gcc.dg/tree-ssa/vrp40.c: Likewise.
Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c.orig 2008-03-28 13:23:13.000000000 +0100
--- gcc/tree-vrp.c 2008-03-28 15:32:59.000000000 +0100
*************** static value_range_t **vr_value;
*** 102,107 ****
--- 102,117 ----
node. */
static int *vr_phi_edge_counts;
+ typedef struct {
+ tree stmt;
+ tree vec;
+ } switch_update;
+
+ static VEC (edge, heap) *to_remove_edges;
+ DEF_VEC_O(switch_update);
+ DEF_VEC_ALLOC_O(switch_update, heap);
+ static VEC (switch_update, heap) *to_update_switch_stmts;
+
/* Return whether TYPE should use an overflow infinity distinct from
TYPE_{MIN,MAX}_VALUE. We use an overflow infinity value to
*************** simplify_cond_using_ranges (tree stmt)
*** 6168,6173 ****
--- 6178,6282 ----
}
}
+ /* Simplify a switch statement using the value range of the switch
+ argument. */
+
+ static void
+ simplify_switch_using_ranges (tree stmt)
+ {
+ tree op = TREE_OPERAND (stmt, 0);
+ value_range_t *vr;
+ bool take_default;
+ edge e;
+ edge_iterator ei;
+ size_t i = 0, j = 0, n, n2;
+ tree vec, vec2;
+ switch_update su;
+
+ if (TREE_CODE (op) != SSA_NAME)
+ return;
+
+ vr = get_value_range (op);
+
+ /* We only can handle integer ranges. */
+ if (vr->type != VR_RANGE
+ || symbolic_range_p (vr))
+ return;
+
+ /* Find case label for min/max of the value range. */
+ vec = SWITCH_LABELS (stmt);
+ n = TREE_VEC_LENGTH (vec);
+ take_default = !find_case_label_index (vec, 0, vr->min, &i);
+ take_default |= !find_case_label_index (vec, i, vr->max, &j);
+
+ /* If the case label range is continuous, we do not need to
+ preserve the default case label. Verify that. */
+ if (!take_default && j > i)
+ {
+ tree low, high;
+ size_t k;
+
+ high = CASE_LOW (TREE_VEC_ELT (vec, i));
+ if (CASE_HIGH (TREE_VEC_ELT (vec, i)))
+ high = CASE_HIGH (TREE_VEC_ELT (vec, i));
+ for (k = i + 1; k <= j; ++k)
+ {
+ low = CASE_LOW (TREE_VEC_ELT (vec, k));
+ if (!integer_onep (int_const_binop (MINUS_EXPR, low, high, 0)))
+ {
+ take_default = true;
+ break;
+ }
+ high = low;
+ if (CASE_HIGH (TREE_VEC_ELT (vec, k)))
+ high = CASE_HIGH (TREE_VEC_ELT (vec, k));
+ }
+ }
+
+ /* Bail out if this is just all edges taken. */
+ if (i == 0
+ && j == n - 2
+ && take_default)
+ return;
+
+ /* Build a new vector of taken case labels. */
+ vec2 = make_tree_vec (j - i + 1 + (int)take_default);
+ for (n2 = 0; i <= j; ++i, ++n2)
+ TREE_VEC_ELT (vec2, n2) = TREE_VEC_ELT (vec, i);
+
+ /* Add the default edge, if necessary. */
+ if (take_default)
+ TREE_VEC_ELT (vec2, n2++) = TREE_VEC_ELT (vec, n - 1);
+
+ /* Mark needed edges. */
+ for (i = 0; i < n2; ++i)
+ {
+ e = find_edge (bb_for_stmt (stmt),
+ label_to_block (CASE_LABEL (TREE_VEC_ELT (vec2, i))));
+ e->aux = (void *)-1;
+ }
+ /* Queue not needed edges for later removal. */
+ FOR_EACH_EDGE (e, ei, bb_for_stmt (stmt)->succs)
+ {
+ if (e->aux == (void *)-1)
+ {
+ e->aux = NULL;
+ continue;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "removing unreachable case label\n");
+ }
+ VEC_safe_push (edge, heap, to_remove_edges, e);
+ }
+
+ /* And queue an update for the stmt. */
+ su.stmt = stmt;
+ su.vec = vec2;
+ VEC_safe_push (switch_update, heap, to_update_switch_stmts, &su);
+ }
+
/* Simplify STMT using ranges if possible. */
void
*************** simplify_stmt_using_ranges (tree stmt)
*** 6194,6202 ****
}
else if (TREE_CODE (stmt) == COND_EXPR
&& COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
! {
! simplify_cond_using_ranges (stmt);
! }
}
/* Stack of dest,src equivalency pairs that need to be restored after
--- 6303,6311 ----
}
else if (TREE_CODE (stmt) == COND_EXPR
&& COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
! simplify_cond_using_ranges (stmt);
! else if (TREE_CODE (stmt) == SWITCH_EXPR)
! simplify_switch_using_ranges (stmt);
}
/* Stack of dest,src equivalency pairs that need to be restored after
*************** identify_jump_threads (void)
*** 6248,6253 ****
--- 6357,6364 ----
{
basic_block bb;
tree dummy;
+ int i;
+ edge e;
/* Ugh. When substituting values earlier in this pass we can
wipe the dominance information. So rebuild the dominator
*************** identify_jump_threads (void)
*** 6261,6266 ****
--- 6372,6382 ----
recompute it. */
mark_dfs_back_edges ();
+ /* Do not thread across edges we are about to remove. Just marking
+ them as EDGE_DFS_BACK will do. */
+ for (i = 0; VEC_iterate (edge, to_remove_edges, i, e); ++i)
+ e->flags |= EDGE_DFS_BACK;
+
/* Allocate our unwinder stack to unwind any temporary equivalences
that might be recorded. */
stack = VEC_alloc (tree, heap, 20);
*************** identify_jump_threads (void)
*** 6306,6312 ****
&& INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
{
edge_iterator ei;
- edge e;
/* We've got a block with multiple predecessors and multiple
successors which also ends in a suitable conditional. For
--- 6422,6427 ----
*************** record_numbers_of_iterations (void)
*** 6473,6478 ****
--- 6588,6597 ----
static unsigned int
execute_vrp (void)
{
+ int i;
+ edge e;
+ switch_update *su;
+
loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
scev_initialize ();
*************** execute_vrp (void)
*** 6490,6499 ****
--- 6609,6635 ----
ranges are corrected. */
record_numbers_of_iterations ();
+ to_remove_edges = VEC_alloc (edge, heap, 10);
+ to_update_switch_stmts = VEC_alloc (switch_update, heap, 5);
+
vrp_initialize ();
ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
vrp_finalize ();
+ /* Remove dead edges from SWITCH_EXPR optimization. This leaves the
+ CFG in a broken state and requires a cfg_cleanup run. */
+ for (i = 0; VEC_iterate (edge, to_remove_edges, i, e); ++i)
+ remove_edge (e);
+ /* Update SWITCH_EXPR case label vector. */
+ for (i = 0; VEC_iterate (switch_update, to_update_switch_stmts, i, su); ++i)
+ SWITCH_LABELS (su->stmt) = su->vec;
+
+ if (VEC_length (edge, to_remove_edges) > 0)
+ free_dominance_info (CDI_DOMINATORS);
+
+ VEC_free (edge, heap, to_remove_edges);
+ VEC_free (switch_update, heap, to_update_switch_stmts);
+
/* ASSERT_EXPRs must be removed before finalizing jump threads
as finalizing jump threads calls the CFG cleanup code which
does not properly handle ASSERT_EXPRs. */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp39.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp39.c 2008-03-28 13:23:18.000000000 +0100
***************
*** 0 ****
--- 1,27 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+ void bar0 (void);
+ void bar1 (void);
+ void bar2 (void);
+ void bar3 (void);
+
+ void
+ foo (int a)
+ {
+ if (a < 100)
+ return;
+ if (200 < a)
+ return;
+
+ switch (a)
+ {
+ case 99: bar0 (); return;
+ case 100: bar1 (); return;
+ case 101: bar2 (); return;
+ case 102: bar3 (); return;
+ }
+ }
+
+ /* { dg-final { scan-tree-dump-not "case 99:" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp40.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp40.c 2008-03-28 13:23:18.000000000 +0100
***************
*** 0 ****
--- 1,22 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -Wuninitialized" } */
+
+ int foo(int val)
+ {
+ int tmp;
+ if ((val > 5) && (val < 8))
+ {
+ switch (val)
+ {
+ case 6:
+ tmp = 1;
+ break;
+ case 7:
+ tmp = 2;
+ break;
+ }
+ return tmp; /* { dg-bogus "used uninitialized" } */
+ }
+ return 0;
+ }
+
Index: gcc/tree-cfg.c
===================================================================
*** gcc/tree-cfg.c.orig 2008-03-27 17:29:57.000000000 +0100
--- gcc/tree-cfg.c 2008-03-28 16:53:24.000000000 +0100
*************** group_case_labels (void)
*** 1060,1077 ****
tree labels = SWITCH_LABELS (stmt);
int old_size = TREE_VEC_LENGTH (labels);
int i, j, new_size = old_size;
! tree default_case = TREE_VEC_ELT (labels, old_size - 1);
! tree default_label;
/* The default label is always the last case in a switch
! statement after gimplification. */
! default_label = CASE_LABEL (default_case);
! /* 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 - 1)
{
tree base_case, base_label, base_high;
base_case = TREE_VEC_ELT (labels, i);
--- 1060,1082 ----
tree labels = SWITCH_LABELS (stmt);
int old_size = TREE_VEC_LENGTH (labels);
int i, j, new_size = old_size;
! tree default_case = NULL_TREE;
! tree default_label = NULL_TREE;
/* The default label is always the last case in a switch
! statement after gimplification if it was not optimized
! away. */
! if (!CASE_LOW (TREE_VEC_ELT (labels, old_size - 1))
! && !CASE_HIGH (TREE_VEC_ELT (labels, old_size - 1)))
! {
! default_case = TREE_VEC_ELT (labels, old_size - 1);
! default_label = CASE_LABEL (default_case);
! old_size--;
! }
! /* Look for possible opportunities to merge cases. */
i = 0;
! while (i < old_size)
{
tree base_case, base_label, base_high;
base_case = TREE_VEC_ELT (labels, i);
*************** group_case_labels (void)
*** 1095,1101 ****
/* 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 - 1)
{
tree merge_case = TREE_VEC_ELT (labels, i);
tree merge_label = CASE_LABEL (merge_case);
--- 1100,1106 ----
/* 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)
{
tree merge_case = TREE_VEC_ELT (labels, i);
tree merge_label = CASE_LABEL (merge_case);
*************** tree_verify_flow_info (void)
*** 4629,4641 ****
/* Verify that the case labels are sorted. */
prev = TREE_VEC_ELT (vec, 0);
! for (i = 1; i < n - 1; ++i)
{
tree c = TREE_VEC_ELT (vec, i);
if (! CASE_LOW (c))
{
! error ("found default case not at end of case vector");
! err = 1;
continue;
}
if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
--- 4634,4649 ----
/* Verify that the case labels are sorted. */
prev = TREE_VEC_ELT (vec, 0);
! for (i = 1; i < n; ++i)
{
tree c = TREE_VEC_ELT (vec, i);
if (! CASE_LOW (c))
{
! if (i != n - 1)
! {
! error ("found default case not at end of case vector");
! err = 1;
! }
continue;
}
if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
*************** tree_verify_flow_info (void)
*** 4649,4659 ****
}
prev = c;
}
! if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
! {
! error ("no default case found at end of case vector");
! err = 1;
! }
FOR_EACH_EDGE (e, ei, bb->succs)
{
--- 4657,4665 ----
}
prev = c;
}
! /* VRP will remove the default case if it can prove it will
! never be executed. So do not verify there always exists
! a default case here. */
FOR_EACH_EDGE (e, ei, bb->succs)
{
Index: gcc/stmt.c
===================================================================
*** gcc/stmt.c.orig 2007-12-05 15:34:03.000000000 +0100
--- gcc/stmt.c 2008-03-28 14:22:48.000000000 +0100
*************** emit_case_bit_tests (tree index_type, tr
*** 2259,2266 ****
mode = TYPE_MODE (index_type);
expr = expand_normal (range);
! emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
! default_label);
index = convert_to_mode (word_mode, index, 0);
index = expand_binop (word_mode, ashl_optab, const1_rtx,
--- 2259,2267 ----
mode = TYPE_MODE (index_type);
expr = expand_normal (range);
! if (default_label)
! emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
! default_label);
index = convert_to_mode (word_mode, index, 0);
index = expand_binop (word_mode, ashl_optab, const1_rtx,
*************** emit_case_bit_tests (tree index_type, tr
*** 2275,2281 ****
word_mode, 1, test[i].label);
}
! emit_jump (default_label);
}
#ifndef HAVE_casesi
--- 2276,2283 ----
word_mode, 1, test[i].label);
}
! if (default_label)
! emit_jump (default_label);
}
#ifndef HAVE_casesi
*************** expand_case (tree exp)
*** 2321,2327 ****
struct case_node *case_list = 0;
/* Label to jump to if no case matches. */
! tree default_label_decl;
alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
sizeof (struct case_node),
--- 2323,2329 ----
struct case_node *case_list = 0;
/* Label to jump to if no case matches. */
! tree default_label_decl = NULL_TREE;
alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
sizeof (struct case_node),
*************** expand_case (tree exp)
*** 2339,2356 ****
{
tree elt;
bitmap label_bitmap;
/* cleanup_tree_cfg removes all SWITCH_EXPR with their index
expressions being INTEGER_CST. */
gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
! /* The default case is at the end of TREE_VEC. */
! elt = TREE_VEC_ELT (vec, TREE_VEC_LENGTH (vec) - 1);
! gcc_assert (!CASE_HIGH (elt));
! gcc_assert (!CASE_LOW (elt));
! default_label_decl = CASE_LABEL (elt);
! for (i = TREE_VEC_LENGTH (vec) - 1; --i >= 0; )
{
tree low, high;
elt = TREE_VEC_ELT (vec, i);
--- 2341,2361 ----
{
tree elt;
bitmap label_bitmap;
+ int vl = TREE_VEC_LENGTH (vec);
/* cleanup_tree_cfg removes all SWITCH_EXPR with their index
expressions being INTEGER_CST. */
gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
! /* The default case, if ever taken, is at the end of TREE_VEC. */
! elt = TREE_VEC_ELT (vec, vl - 1);
! if (!CASE_LOW (elt) && !CASE_HIGH (elt))
! {
! default_label_decl = CASE_LABEL (elt);
! --vl;
! }
! for (i = vl - 1; i >= 0; --i)
{
tree low, high;
elt = TREE_VEC_ELT (vec, i);
*************** expand_case (tree exp)
*** 2369,2375 ****
before_case = start = get_last_insn ();
! default_label = label_rtx (default_label_decl);
/* Get upper and lower bounds of case values. */
--- 2374,2381 ----
before_case = start = get_last_insn ();
! if (default_label_decl)
! default_label = label_rtx (default_label_decl);
/* Get upper and lower bounds of case values. */
*************** expand_case (tree exp)
*** 2414,2420 ****
type, so we may still get a zero here. */
if (count == 0)
{
! emit_jump (default_label);
free_alloc_pool (case_node_pool);
return;
}
--- 2420,2427 ----
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;
}
*************** expand_case (tree exp)
*** 2510,2516 ****
&& estimate_case_costs (case_list));
balance_case_nodes (&case_list, NULL);
emit_case_nodes (index, case_list, default_label, index_type);
! emit_jump (default_label);
}
else
{
--- 2517,2524 ----
&& estimate_case_costs (case_list));
balance_case_nodes (&case_list, NULL);
emit_case_nodes (index, case_list, default_label, index_type);
! if (default_label)
! emit_jump (default_label);
}
else
{
*************** expand_case (tree exp)
*** 2560,2568 ****
}
/* Fill in the gaps with the default. */
! for (i = 0; i < ncases; i++)
! if (labelvec[i] == 0)
! labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
/* Output the table. */
emit_label (table_label);
--- 2568,2577 ----
}
/* Fill in the gaps with the default. */
! if (default_label)
! for (i = 0; i < ncases; i++)
! if (labelvec[i] == 0)
! labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
/* Output the table. */
emit_label (table_label);
*************** emit_case_nodes (rtx index, case_node_pt
*** 3044,3050 ****
emit_case_nodes (index, node->left, default_label, index_type);
/* If left-hand subtree does nothing,
go to default. */
! emit_jump (default_label);
/* Code branches here for the right-hand subtree. */
expand_label (test_label);
--- 3053,3060 ----
emit_case_nodes (index, node->left, default_label, index_type);
/* If left-hand subtree does nothing,
go to default. */
! if (default_label)
! emit_jump (default_label);
/* Code branches here for the right-hand subtree. */
expand_label (test_label);
*************** emit_case_nodes (rtx index, case_node_pt
*** 3179,3185 ****
{
/* If the left-hand subtree fell through,
don't let it fall into the right-hand subtree. */
! emit_jump (default_label);
expand_label (test_label);
emit_case_nodes (index, node->right, default_label, index_type);
--- 3189,3196 ----
{
/* If the left-hand subtree fell through,
don't let it fall into the right-hand subtree. */
! if (default_label)
! emit_jump (default_label);
expand_label (test_label);
emit_case_nodes (index, node->right, default_label, index_type);
Index: gcc/expr.c
===================================================================
*** gcc/expr.c.orig 2008-03-19 11:37:33.000000000 +0100
--- gcc/expr.c 2008-03-28 16:29:22.000000000 +0100
*************** try_casesi (tree index_type, tree index_
*** 9884,9891 ****
index_expr, minval);
minval = integer_zero_node;
index = expand_normal (index_expr);
! emit_cmp_and_jump_insns (rangertx, index, LTU, NULL_RTX,
! omode, 1, default_label);
/* Now we can safely truncate. */
index = convert_to_mode (index_mode, index, 0);
}
--- 9884,9892 ----
index_expr, minval);
minval = integer_zero_node;
index = expand_normal (index_expr);
! if (default_label)
! emit_cmp_and_jump_insns (rangertx, index, LTU, NULL_RTX,
! omode, 1, default_label);
/* Now we can safely truncate. */
index = convert_to_mode (index_mode, index, 0);
}
*************** do_tablejump (rtx index, enum machine_mo
*** 9964,9971 ****
or equal to the minimum value of the range and less than or equal to
the maximum value of the range. */
! emit_cmp_and_jump_insns (index, range, GTU, NULL_RTX, mode, 1,
! default_label);
/* If index is in range, it must fit in Pmode.
Convert to Pmode so we can index with it. */
--- 9965,9973 ----
or equal to the minimum value of the range and less than or equal to
the maximum value of the range. */
! if (default_label)
! emit_cmp_and_jump_insns (index, range, GTU, NULL_RTX, mode, 1,
! default_label);
/* If index is in range, it must fit in Pmode.
Convert to Pmode so we can index with it. */
More information about the Gcc-patches
mailing list