Message ID | 20110525172112.GP17079@tyan-ft48-01.lab.bos.redhat.com |
---|---|
State | New |
Headers | show |
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 >
--- 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; +}