Re: [PATCH] Fix VRP switch handling (PR tree-optimization/49161)

[Richard Guenther <richard dot guenther at gmail dot com>]

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
>