From patchwork Sat Jul 21 13:57:03 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom de Vries X-Patchwork-Id: 172432 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 6D1722C00B3 for ; Sat, 21 Jul 2012 23:57:29 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1343483850; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC: Subject:Content-Type:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=CyM3dCtTa9W/v1U4loPSwHl5J6k=; b=vlnkDwLCZb9XY1e xx0lmvm7SIGYhFRu6z72i7Fx3/cQf5L35uAeawmvXlThiJBYbcozddRYcl9JDYCg RU/cYIO4nKm0+3t5GFc2tqMgisRhrPPttQsVVzvWF1ysui71IXaaphKrVxA0oMoR C821ADJTPFPjm2jLdJJSK9YRhD7s= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=kku3qhCyDkF4oyhtmFTN2H1Owihup38WZ8KYc7re2otzbeM1MYvNmGjW/BE/Mq aQZV8Kqr/s7FozZEfwi3l2D2a4uWuwXYuw8gFtooOQZoDuREQppybgoBGKUCjVmC xv0+7BgDJ0j0Klg8i9R1jvgO1cpEAxEIwxi5qNCTI+CxQ=; Received: (qmail 19161 invoked by alias); 21 Jul 2012 13:57:25 -0000 Received: (qmail 19150 invoked by uid 22791); 21 Jul 2012 13:57:24 -0000 X-SWARE-Spam-Status: No, hits=-3.6 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, RCVD_IN_HOSTKARMA_W, RCVD_IN_HOSTKARMA_WL X-Spam-Check-By: sourceware.org Received: from relay1.mentorg.com (HELO relay1.mentorg.com) (192.94.38.131) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sat, 21 Jul 2012 13:57:08 +0000 Received: from svr-orw-exc-10.mgc.mentorg.com ([147.34.98.58]) by relay1.mentorg.com with esmtp id 1SsaB9-0007CR-DQ from Tom_deVries@mentor.com ; Sat, 21 Jul 2012 06:57:07 -0700 Received: from SVR-IES-FEM-01.mgc.mentorg.com ([137.202.0.104]) by SVR-ORW-EXC-10.mgc.mentorg.com with Microsoft SMTPSVC(6.0.3790.4675); Sat, 21 Jul 2012 06:57:11 -0700 Received: from [127.0.0.1] (137.202.0.76) by SVR-IES-FEM-01.mgc.mentorg.com (137.202.0.104) with Microsoft SMTP Server id 14.1.289.1; Sat, 21 Jul 2012 14:57:05 +0100 Message-ID: <500AB52F.4050108@mentor.com> Date: Sat, 21 Jul 2012 15:57:03 +0200 From: Tom de Vries User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120714 Thunderbird/14.0 MIME-Version: 1.0 To: Jakub Jelinek CC: "gcc-patches@gcc.gnu.org" Subject: [PATCH] propagate anti-range to switch in tree-vrp 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 Jakub, this patch adds propagation of anti-ranges to switches. The test-case is this: ... void f3 (int s) { if (s >> 3 == -2) /* s in range [ -16, -9]. */ ; else { /* s in range ~[-16, -9], so none of the case labels can be taken. */ switch (s) { case -16: case -12: case -9: link_error (); break; default: break; } } } ... The call to link_error is unreachable but tree-vrp fails to analyze that. Using the patch, the switch is replaced by the default case. Bootstrapped and reg-tested (Ada inclusive) on x86_64. OK for trunk? Thanks, - Tom 2012-07-21 Tom de Vries * tree-vrp.c (find_case_label_ranges): New function. (vrp_visit_switch_stmt, simplify_switch_using_ranges): Use find_case_label_ranges instead of find_case_label_range. Handle second range. * gcc.dg/tree-ssa/vrp72.c: New test. Index: gcc/tree-vrp.c =================================================================== --- gcc/tree-vrp.c (revision 189508) +++ gcc/tree-vrp.c (working copy) @@ -6736,6 +6736,84 @@ find_case_label_range (gimple stmt, tree } } +/* Searches the case label vector VEC for the ranges of CASE_LABELs that are + used in range VR. The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and + MAX_IDX2. If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1. + Returns true if the default label is not needed. */ + +static bool +find_case_label_ranges (gimple stmt, value_range_t *vr, size_t *min_idx1, + size_t *max_idx1, size_t *min_idx2, + size_t *max_idx2) +{ + size_t i, j, k, l; + unsigned int n = gimple_switch_num_labels (stmt); + bool take_default; + tree case_low, case_high; + tree min = vr->min, max = vr->max; + + gcc_checking_assert (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE); + + take_default = !find_case_label_range (stmt, min, max, &i, &j); + + /* Set second range to emtpy. */ + *min_idx2 = 1; + *max_idx2 = 0; + + if (vr->type == VR_RANGE) + { + *min_idx1 = i; + *max_idx1 = j; + return !take_default; + } + + /* Set first range to all case labels. */ + *min_idx1 = 1; + *max_idx1 = n - 1; + + if (i > j) + return false; + + /* Make sure all the values of case labels [i , j] are contained in + range [MIN, MAX]. */ + case_low = CASE_LOW (gimple_switch_label (stmt, i)); + case_high = CASE_HIGH (gimple_switch_label (stmt, j)); + if (tree_int_cst_compare (case_low, min) < 0) + i += 1; + if (case_high != NULL_TREE + && tree_int_cst_compare (max, case_high) < 0) + j -= 1; + + if (i > j) + return false; + + /* If the range spans case labels [i, j], the corresponding anti-range spans + the labels [1, i - 1] and [j + 1, n - 1]. */ + k = j + 1; + l = n - 1; + if (k > l) + { + k = 1; + l = 0; + } + + j = i - 1; + i = 1; + if (i > j) + { + i = k; + j = l; + k = 1; + l = 0; + } + + *min_idx1 = i; + *max_idx1 = j; + *min_idx2 = k; + *max_idx2 = l; + return false; +} + /* Visit switch statement STMT. If we can determine which edge will be taken out of STMT's basic block, record it in *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return @@ -6746,7 +6824,7 @@ vrp_visit_switch_stmt (gimple stmt, edge { tree op, val; value_range_t *vr; - size_t i = 0, j = 0; + size_t i = 0, j = 0, k, l; bool take_default; *taken_edge_p = NULL; @@ -6764,12 +6842,13 @@ vrp_visit_switch_stmt (gimple stmt, edge fprintf (dump_file, "\n"); } - if (vr->type != VR_RANGE + if ((vr->type != VR_RANGE + && vr->type != VR_ANTI_RANGE) || symbolic_range_p (vr)) return SSA_PROP_VARYING; /* Find the single edge that is taken from the switch expression. */ - take_default = !find_case_label_range (stmt, vr->min, vr->max, &i, &j); + take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l); /* Check if the range spans no CASE_LABEL. If so, we only reach the default label */ @@ -6803,6 +6882,16 @@ vrp_visit_switch_stmt (gimple stmt, edge return SSA_PROP_VARYING; } } + for (; k <= l; ++k) + { + if (CASE_LABEL (gimple_switch_label (stmt, k)) != CASE_LABEL (val)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " not a single destination for this " + "range\n"); + return SSA_PROP_VARYING; + } + } } *taken_edge_p = find_edge (gimple_bb (stmt), @@ -8195,18 +8284,20 @@ simplify_switch_using_ranges (gimple stm size_t i = 0, j = 0, n, n2; tree vec2; switch_update su; + size_t k = 1, l = 0; if (TREE_CODE (op) == SSA_NAME) { vr = get_value_range (op); /* We can only handle integer ranges. */ - if (vr->type != VR_RANGE + if ((vr->type != VR_RANGE + && vr->type != VR_ANTI_RANGE) || symbolic_range_p (vr)) return false; /* Find case label for min/max of the value range. */ - take_default = !find_case_label_range (stmt, vr->min, vr->max, &i, &j); + take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l); } else if (TREE_CODE (op) == INTEGER_CST) { @@ -8233,7 +8324,7 @@ simplify_switch_using_ranges (gimple stm return false; /* Build a new vector of taken case labels. */ - vec2 = make_tree_vec (j - i + 1 + (int)take_default); + vec2 = make_tree_vec (j - i + 1 + l - k + 1 + (int)take_default); n2 = 0; /* Add the default edge, if necessary. */ @@ -8243,6 +8334,9 @@ simplify_switch_using_ranges (gimple stm for (; i <= j; ++i, ++n2) TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, i); + for (; k <= l; ++k, ++n2) + TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, k); + /* Mark needed edges. */ for (i = 0; i < n2; ++i) { Index: gcc/testsuite/gcc.dg/tree-ssa/vrp72.c =================================================================== --- /dev/null (new file) +++ gcc/testsuite/gcc.dg/tree-ssa/vrp72.c (revision 0) @@ -0,0 +1,35 @@ +/* { dg-do link } */ +/* { dg-options "-O2 -fno-tree-switch-conversion" } */ + +/* Based on f3 from vrp63.c, but with switch instead of if-chain. This test + tests the propagation of an anti-range in a switch statement. */ + +extern void link_error (void); + +void +f3 (int s) +{ + if (s >> 3 == -2) + /* s in range [ -16, -9]. */ + ; + else + { + /* s in range ~[-16, -9], so none of the case labels can be taken. */ + switch (s) + { + case -16: + case -12: + case -9: + link_error (); + break; + default: + break; + } + } +} + +int +main () +{ + return 0; +}