* [PATCH] Fix VRP switch handling (PR tree-optimization/49161)
@ 2011-05-25 18:03 Jakub Jelinek
2011-05-26 10:29 ` Richard Guenther
0 siblings, 1 reply; 2+ messages in thread
From: Jakub Jelinek @ 2011-05-25 18:03 UTC (permalink / raw)
To: gcc-patches
Hi!
The following testcase is miscompiled, because there are multiple
CASE_LABELs for the same target bb in a switch:
<bb 2>:
switch (x_1(D)) <default: <L13>, case 3: l4, case 4: l1, case 6: l3>
l3:
bar (-1);
l2:
l1:
l4:
bar (0);
find_switch_asserts sorts by uids of CASE_LABELs and adds x_1(D) == 4
as well as x_1(D) == 3 assertions on the same edge, instead of
adding properly x_1(D) >= 3 and x_1(D) <= 4 assertions.
Fixed thusly, bootstrapped/regtested on x86_64-linux and i686-linux,
ok for trunk/4.6?
2011-05-25 Jakub Jelinek <jakub@redhat.com>
PR tree-optimization/49161
* tree-vrp.c (struct case_info): New type.
(compare_case_labels): Sort case_info structs instead of
trees, and not primarily by CASE_LABEL uids but by
label_for_block indexes.
(find_switch_asserts): Put case labels into struct case_info
array instead of TREE_VEC, adjust sorting, compare label_for_block
values instead of CASE_LABELs.
* gcc.c-torture/execute/pr49161.c: New test.
--- gcc/tree-vrp.c.jj 2011-05-20 08:14:08.000000000 +0200
+++ gcc/tree-vrp.c 2011-05-25 16:03:18.000000000 +0200
@@ -4673,28 +4673,35 @@ find_conditional_asserts (basic_block bb
return need_assert;
}
-/* Compare two case labels sorting first by the destination label uid
+struct case_info
+{
+ tree expr;
+ basic_block bb;
+};
+
+/* Compare two case labels sorting first by the destination bb index
and then by the case value. */
static int
compare_case_labels (const void *p1, const void *p2)
{
- const_tree const case1 = *(const_tree const*)p1;
- const_tree const case2 = *(const_tree const*)p2;
- unsigned int uid1 = DECL_UID (CASE_LABEL (case1));
- unsigned int uid2 = DECL_UID (CASE_LABEL (case2));
+ const struct case_info *ci1 = (const struct case_info *) p1;
+ const struct case_info *ci2 = (const struct case_info *) p2;
+ int idx1 = ci1->bb->index;
+ int idx2 = ci2->bb->index;
- if (uid1 < uid2)
+ if (idx1 < idx2)
return -1;
- else if (uid1 == uid2)
+ else if (idx1 == idx2)
{
/* Make sure the default label is first in a group. */
- if (!CASE_LOW (case1))
+ if (!CASE_LOW (ci1->expr))
return -1;
- else if (!CASE_LOW (case2))
+ else if (!CASE_LOW (ci2->expr))
return 1;
else
- return tree_int_cst_compare (CASE_LOW (case1), CASE_LOW (case2));
+ return tree_int_cst_compare (CASE_LOW (ci1->expr),
+ CASE_LOW (ci2->expr));
}
else
return 1;
@@ -4715,8 +4722,8 @@ find_switch_asserts (basic_block bb, gim
gimple_stmt_iterator bsi;
tree op;
edge e;
- tree vec2;
- size_t n = gimple_switch_num_labels(last);
+ struct case_info *ci;
+ size_t n = gimple_switch_num_labels (last);
#if GCC_VERSION >= 4000
unsigned int idx;
#else
@@ -4731,36 +4738,38 @@ find_switch_asserts (basic_block bb, gim
return false;
/* Build a vector of case labels sorted by destination label. */
- vec2 = make_tree_vec (n);
+ ci = XNEWVEC (struct case_info, n);
for (idx = 0; idx < n; ++idx)
- TREE_VEC_ELT (vec2, idx) = gimple_switch_label (last, idx);
- qsort (&TREE_VEC_ELT (vec2, 0), n, sizeof (tree), compare_case_labels);
+ {
+ ci[idx].expr = gimple_switch_label (last, idx);
+ ci[idx].bb = label_to_block (CASE_LABEL (ci[idx].expr));
+ }
+ qsort (ci, n, sizeof (struct case_info), compare_case_labels);
for (idx = 0; idx < n; ++idx)
{
tree min, max;
- tree cl = TREE_VEC_ELT (vec2, idx);
+ tree cl = ci[idx].expr;
+ basic_block cbb = ci[idx].bb;
min = CASE_LOW (cl);
max = CASE_HIGH (cl);
/* If there are multiple case labels with the same destination
we need to combine them to a single value range for the edge. */
- if (idx + 1 < n
- && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx + 1)))
+ if (idx + 1 < n && cbb == ci[idx + 1].bb)
{
/* Skip labels until the last of the group. */
do {
++idx;
- } while (idx < n
- && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx)));
+ } while (idx < n && cbb == ci[idx].bb);
--idx;
/* Pick up the maximum of the case label range. */
- if (CASE_HIGH (TREE_VEC_ELT (vec2, idx)))
- max = CASE_HIGH (TREE_VEC_ELT (vec2, idx));
+ if (CASE_HIGH (ci[idx].expr))
+ max = CASE_HIGH (ci[idx].expr);
else
- max = CASE_LOW (TREE_VEC_ELT (vec2, idx));
+ max = CASE_LOW (ci[idx].expr);
}
/* Nothing to do if the range includes the default label until we
@@ -4769,7 +4778,7 @@ find_switch_asserts (basic_block bb, gim
continue;
/* Find the edge to register the assert expr on. */
- e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
+ e = find_edge (bb, cbb);
/* Register the necessary assertions for the operand in the
SWITCH_EXPR. */
@@ -4787,6 +4796,7 @@ find_switch_asserts (basic_block bb, gim
}
}
+ XDELETEVEC (ci);
return need_assert;
}
--- gcc/testsuite/gcc.c-torture/execute/pr49161.c.jj 2011-05-25 16:02:52.000000000 +0200
+++ gcc/testsuite/gcc.c-torture/execute/pr49161.c 2011-05-25 16:01:47.000000000 +0200
@@ -0,0 +1,46 @@
+/* PR tree-optimization/49161 */
+
+extern void abort (void);
+
+int c;
+
+__attribute__((noinline, noclone)) void
+bar (int x)
+{
+ if (x != c++)
+ abort ();
+}
+
+__attribute__((noinline, noclone)) void
+foo (int x)
+{
+ switch (x)
+ {
+ case 3: goto l1;
+ case 4: goto l2;
+ case 6: goto l3;
+ default: return;
+ }
+l1:
+ goto l4;
+l2:
+ goto l4;
+l3:
+ bar (-1);
+l4:
+ bar (0);
+ if (x != 4)
+ bar (1);
+ if (x != 3)
+ bar (-1);
+ bar (2);
+}
+
+int
+main ()
+{
+ foo (3);
+ if (c != 3)
+ abort ();
+ return 0;
+}
Jakub
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH] Fix VRP switch handling (PR tree-optimization/49161)
2011-05-25 18:03 [PATCH] Fix VRP switch handling (PR tree-optimization/49161) Jakub Jelinek
@ 2011-05-26 10:29 ` Richard Guenther
0 siblings, 0 replies; 2+ messages in thread
From: Richard Guenther @ 2011-05-26 10:29 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: gcc-patches
On Wed, May 25, 2011 at 7:21 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> Hi!
>
> The following testcase is miscompiled, because there are multiple
> CASE_LABELs for the same target bb in a switch:
> <bb 2>:
> switch (x_1(D)) <default: <L13>, case 3: l4, case 4: l1, case 6: l3>
>
> l3:
> bar (-1);
>
> l2:
> l1:
> l4:
> bar (0);
>
> find_switch_asserts sorts by uids of CASE_LABELs and adds x_1(D) == 4
> as well as x_1(D) == 3 assertions on the same edge, instead of
> adding properly x_1(D) >= 3 and x_1(D) <= 4 assertions.
>
> Fixed thusly, bootstrapped/regtested on x86_64-linux and i686-linux,
> ok for trunk/4.6?
Ok.
Thanks,
Richard.
> 2011-05-25 Jakub Jelinek <jakub@redhat.com>
>
> PR tree-optimization/49161
> * tree-vrp.c (struct case_info): New type.
> (compare_case_labels): Sort case_info structs instead of
> trees, and not primarily by CASE_LABEL uids but by
> label_for_block indexes.
> (find_switch_asserts): Put case labels into struct case_info
> array instead of TREE_VEC, adjust sorting, compare label_for_block
> values instead of CASE_LABELs.
>
> * gcc.c-torture/execute/pr49161.c: New test.
>
> --- gcc/tree-vrp.c.jj 2011-05-20 08:14:08.000000000 +0200
> +++ gcc/tree-vrp.c 2011-05-25 16:03:18.000000000 +0200
> @@ -4673,28 +4673,35 @@ find_conditional_asserts (basic_block bb
> return need_assert;
> }
>
> -/* Compare two case labels sorting first by the destination label uid
> +struct case_info
> +{
> + tree expr;
> + basic_block bb;
> +};
> +
> +/* Compare two case labels sorting first by the destination bb index
> and then by the case value. */
>
> static int
> compare_case_labels (const void *p1, const void *p2)
> {
> - const_tree const case1 = *(const_tree const*)p1;
> - const_tree const case2 = *(const_tree const*)p2;
> - unsigned int uid1 = DECL_UID (CASE_LABEL (case1));
> - unsigned int uid2 = DECL_UID (CASE_LABEL (case2));
> + const struct case_info *ci1 = (const struct case_info *) p1;
> + const struct case_info *ci2 = (const struct case_info *) p2;
> + int idx1 = ci1->bb->index;
> + int idx2 = ci2->bb->index;
>
> - if (uid1 < uid2)
> + if (idx1 < idx2)
> return -1;
> - else if (uid1 == uid2)
> + else if (idx1 == idx2)
> {
> /* Make sure the default label is first in a group. */
> - if (!CASE_LOW (case1))
> + if (!CASE_LOW (ci1->expr))
> return -1;
> - else if (!CASE_LOW (case2))
> + else if (!CASE_LOW (ci2->expr))
> return 1;
> else
> - return tree_int_cst_compare (CASE_LOW (case1), CASE_LOW (case2));
> + return tree_int_cst_compare (CASE_LOW (ci1->expr),
> + CASE_LOW (ci2->expr));
> }
> else
> return 1;
> @@ -4715,8 +4722,8 @@ find_switch_asserts (basic_block bb, gim
> gimple_stmt_iterator bsi;
> tree op;
> edge e;
> - tree vec2;
> - size_t n = gimple_switch_num_labels(last);
> + struct case_info *ci;
> + size_t n = gimple_switch_num_labels (last);
> #if GCC_VERSION >= 4000
> unsigned int idx;
> #else
> @@ -4731,36 +4738,38 @@ find_switch_asserts (basic_block bb, gim
> return false;
>
> /* Build a vector of case labels sorted by destination label. */
> - vec2 = make_tree_vec (n);
> + ci = XNEWVEC (struct case_info, n);
> for (idx = 0; idx < n; ++idx)
> - TREE_VEC_ELT (vec2, idx) = gimple_switch_label (last, idx);
> - qsort (&TREE_VEC_ELT (vec2, 0), n, sizeof (tree), compare_case_labels);
> + {
> + ci[idx].expr = gimple_switch_label (last, idx);
> + ci[idx].bb = label_to_block (CASE_LABEL (ci[idx].expr));
> + }
> + qsort (ci, n, sizeof (struct case_info), compare_case_labels);
>
> for (idx = 0; idx < n; ++idx)
> {
> tree min, max;
> - tree cl = TREE_VEC_ELT (vec2, idx);
> + tree cl = ci[idx].expr;
> + basic_block cbb = ci[idx].bb;
>
> min = CASE_LOW (cl);
> max = CASE_HIGH (cl);
>
> /* If there are multiple case labels with the same destination
> we need to combine them to a single value range for the edge. */
> - if (idx + 1 < n
> - && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx + 1)))
> + if (idx + 1 < n && cbb == ci[idx + 1].bb)
> {
> /* Skip labels until the last of the group. */
> do {
> ++idx;
> - } while (idx < n
> - && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx)));
> + } while (idx < n && cbb == ci[idx].bb);
> --idx;
>
> /* Pick up the maximum of the case label range. */
> - if (CASE_HIGH (TREE_VEC_ELT (vec2, idx)))
> - max = CASE_HIGH (TREE_VEC_ELT (vec2, idx));
> + if (CASE_HIGH (ci[idx].expr))
> + max = CASE_HIGH (ci[idx].expr);
> else
> - max = CASE_LOW (TREE_VEC_ELT (vec2, idx));
> + max = CASE_LOW (ci[idx].expr);
> }
>
> /* Nothing to do if the range includes the default label until we
> @@ -4769,7 +4778,7 @@ find_switch_asserts (basic_block bb, gim
> continue;
>
> /* Find the edge to register the assert expr on. */
> - e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
> + e = find_edge (bb, cbb);
>
> /* Register the necessary assertions for the operand in the
> SWITCH_EXPR. */
> @@ -4787,6 +4796,7 @@ find_switch_asserts (basic_block bb, gim
> }
> }
>
> + XDELETEVEC (ci);
> return need_assert;
> }
>
> --- gcc/testsuite/gcc.c-torture/execute/pr49161.c.jj 2011-05-25 16:02:52.000000000 +0200
> +++ gcc/testsuite/gcc.c-torture/execute/pr49161.c 2011-05-25 16:01:47.000000000 +0200
> @@ -0,0 +1,46 @@
> +/* PR tree-optimization/49161 */
> +
> +extern void abort (void);
> +
> +int c;
> +
> +__attribute__((noinline, noclone)) void
> +bar (int x)
> +{
> + if (x != c++)
> + abort ();
> +}
> +
> +__attribute__((noinline, noclone)) void
> +foo (int x)
> +{
> + switch (x)
> + {
> + case 3: goto l1;
> + case 4: goto l2;
> + case 6: goto l3;
> + default: return;
> + }
> +l1:
> + goto l4;
> +l2:
> + goto l4;
> +l3:
> + bar (-1);
> +l4:
> + bar (0);
> + if (x != 4)
> + bar (1);
> + if (x != 3)
> + bar (-1);
> + bar (2);
> +}
> +
> +int
> +main ()
> +{
> + foo (3);
> + if (c != 3)
> + abort ();
> + return 0;
> +}
>
> Jakub
>
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2011-05-26 9:05 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-05-25 18:03 [PATCH] Fix VRP switch handling (PR tree-optimization/49161) Jakub Jelinek
2011-05-26 10:29 ` Richard Guenther
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).