From patchwork Wed May 25 17:21:12 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 97386 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 3BBE9B6F91 for ; Thu, 26 May 2011 03:21:46 +1000 (EST) Received: (qmail 23006 invoked by alias); 25 May 2011 17:21:41 -0000 Received: (qmail 22996 invoked by uid 22791); 25 May 2011 17:21:39 -0000 X-SWARE-Spam-Status: No, hits=-6.4 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_HI, SPF_HELO_PASS, TW_CB, TW_TM, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 25 May 2011 17:21:15 +0000 Received: from int-mx02.intmail.prod.int.phx2.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id p4PHLEHf016108 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Wed, 25 May 2011 13:21:14 -0400 Received: from tyan-ft48-01.lab.bos.redhat.com (tyan-ft48-01.lab.bos.redhat.com [10.16.42.4]) by int-mx02.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id p4PHLDK9016164 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Wed, 25 May 2011 13:21:14 -0400 Received: from tyan-ft48-01.lab.bos.redhat.com (localhost.localdomain [127.0.0.1]) by tyan-ft48-01.lab.bos.redhat.com (8.14.4/8.14.4) with ESMTP id p4PHLDIR011231 for ; Wed, 25 May 2011 19:21:13 +0200 Received: (from jakub@localhost) by tyan-ft48-01.lab.bos.redhat.com (8.14.4/8.14.4/Submit) id p4PHLD4Z011229 for gcc-patches@gcc.gnu.org; Wed, 25 May 2011 19:21:13 +0200 Date: Wed, 25 May 2011 19:21:12 +0200 From: Jakub Jelinek To: gcc-patches@gcc.gnu.org Subject: [PATCH] Fix VRP switch handling (PR tree-optimization/49161) Message-ID: <20110525172112.GP17079@tyan-ft48-01.lab.bos.redhat.com> Reply-To: Jakub Jelinek MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Hi! The following testcase is miscompiled, because there are multiple CASE_LABELs for the same target bb in a switch: : switch (x_1(D)) , 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 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. 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; +}