From patchwork Fri Apr 26 18:53:41 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 239997 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]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "localhost", Issuer "www.qmailtoaster.com" (not verified)) by ozlabs.org (Postfix) with ESMTPS id AB1202C0111 for ; Sat, 27 Apr 2013 04:53:52 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:content-type; q= dns; s=default; b=m/FCdDxTjaWfW12LKQb3oBD5VcIynpvFnffrMo4gfpGkPo DYxXeWN78y97xIM052ThahsIus23TVL7DEJMhuPiV3Mao9cbA6SJnJhydiz3V8Eu LlXaOA2DEeMgdEKhx+P/kZaOuRHPvxBb+bsA5dUtQG+kl4UNAIZpoyUpkKmxM= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:content-type; s= default; bh=g8KyXkrfhbuotNp4L0GFe/0/Q4s=; b=N8Y+ltQ4mBm9+2oT9BuJ /iUorzPh0i0H46MKaYiEjgc/3y6y5xlWub/7RqYYCDn0rEAfrov57w+pahHM0NTg p9KdUGo+ZlqeIaBPcXtMHEwdVQlzaF1JT8yPdVj4xxD9rPNJrBbRYGRjYZbQ60me rGkqpSqPU5OiGziDli3QlC0= Received: (qmail 14465 invoked by alias); 26 Apr 2013 18:53:46 -0000 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 Received: (qmail 14456 invoked by uid 89); 26 Apr 2013 18:53:46 -0000 X-Spam-SWARE-Status: No, score=-6.7 required=5.0 tests=AWL, BAYES_00, RCVD_IN_HOSTKARMA_W, RCVD_IN_HOSTKARMA_WL, RP_MATCHES_RCVD, SPF_HELO_PASS, SPF_PASS, TW_TM autolearn=ham version=3.3.1 Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Fri, 26 Apr 2013 18:53:43 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r3QIrgoU006753 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Fri, 26 Apr 2013 14:53:42 -0400 Received: from stumpy.slc.redhat.com (ovpn-113-32.phx2.redhat.com [10.3.113.32]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id r3QIrgLb004276 for ; Fri, 26 Apr 2013 14:53:42 -0400 Message-ID: <517ACD35.9060801@redhat.com> Date: Fri, 26 Apr 2013 12:53:41 -0600 From: Jeff Law User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130402 Thunderbird/17.0.5 MIME-Version: 1.0 To: gcc-patches Subject: [RFA][PATCH] Eliminate more unnecessary type conversions X-Virus-Found: No So looking at more dumps made it pretty obvious that my previous patch to tree-vrp.c to eliminate useless casts to boolean types which fed into comparisons could and should be generalized. Given: x1 = (T1) x0; if (x1 COND CONST) If the known value range for x0 fits into T1, then we can rewrite as x1 = (T1) x0; if (x0 COND (T)CONST) Which typically makes the first statement dead and may allow further simplifications. Bootstrapped and regression tested on x86_64-unknown-linux-gnu. OK for the trunk? commit ad290c7270201042bfc3cde1d84c12e639e4bff7 Author: Jeff Law Date: Fri Apr 26 12:52:06 2013 -0600 * tree-vrp.c (range_fits_type_p): Move to earlier point in file. (simplify_cond_using_ranges): Generalize code to simplify COND_EXPRs where one argument is a constant and the other is an SSA_NAME created by an integral type conversion. * gcc.dg/tree-ssa/vrp88.c: New test. diff --git a/gcc/ChangeLog b/gcc/ChangeLog index d06eee6..f9b207c 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +2013-04-26 Jeff Law + + * tree-vrp.c (range_fits_type_p): Move to earlier point in file. + (simplify_cond_using_ranges): Generalize code to simplify + COND_EXPRs where one argument is a constant and the other + is an SSA_NAME created by an integral type conversion. + 2013-04-26 Vladimir Makarov * rtl.h (struct rtx_def): Add comment for field jump. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index bbea9fa..6d7839f 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2013-04-26 Jeff Law + + * gcc.dg/tree-ssa/vrp88.c: New test. + 2013-04-26 Jakub Jelinek PR go/57045 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp88.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp88.c new file mode 100644 index 0000000..e43bdff --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp88.c @@ -0,0 +1,39 @@ +/* { dg-do compile } */ + +/* { dg-options "-O2 -fdump-tree-vrp1-details" } */ + + +typedef const struct bitmap_head_def *const_bitmap; +typedef unsigned long BITMAP_WORD; +typedef struct bitmap_element_def { + struct bitmap_element_def *next; + BITMAP_WORD bits[((128 + (8 * 8 * 1u) - 1) / (8 * 8 * 1u))]; +} bitmap_element; +typedef struct bitmap_head_def { + bitmap_element *first; +} bitmap_head; +unsigned char +bitmap_single_bit_set_p (const_bitmap a) +{ + unsigned long count = 0; + const bitmap_element *elt; + unsigned ix; + if ((!(a)->first)) + return 0; + elt = a->first; + if (elt->next != ((void *)0)) + return 0; + for (ix = 0; ix != ((128 + (8 * 8 * 1u) - 1) / (8 * 8 * 1u)); ix++) + { + count += __builtin_popcountl (elt->bits[ix]); + if (count > 1) + return 0; + } + return count == 1; +} + +/* Verify that VRP simplified an "if" statement. */ +/* { dg-final { scan-tree-dump "Folded into: if.*" "vrp1"} } */ +/* { dg-final { cleanup-tree-dump "vrp1" } } */ + + diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index cb4a09a..07e3e01 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -8509,6 +8509,57 @@ test_for_singularity (enum tree_code cond_code, tree op0, return NULL; } +/* Return whether the value range *VR fits in an integer type specified + by PRECISION and UNSIGNED_P. */ + +static bool +range_fits_type_p (value_range_t *vr, unsigned precision, bool unsigned_p) +{ + tree src_type; + unsigned src_precision; + double_int tem; + + /* We can only handle integral and pointer types. */ + src_type = TREE_TYPE (vr->min); + if (!INTEGRAL_TYPE_P (src_type) + && !POINTER_TYPE_P (src_type)) + return false; + + /* An extension is fine unless VR is signed and unsigned_p, + and so is an identity transform. */ + src_precision = TYPE_PRECISION (TREE_TYPE (vr->min)); + if ((src_precision < precision + && !(unsigned_p && !TYPE_UNSIGNED (src_type))) + || (src_precision == precision + && TYPE_UNSIGNED (src_type) == unsigned_p)) + return true; + + /* Now we can only handle ranges with constant bounds. */ + if (vr->type != VR_RANGE + || TREE_CODE (vr->min) != INTEGER_CST + || TREE_CODE (vr->max) != INTEGER_CST) + return false; + + /* For sign changes, the MSB of the double_int has to be clear. + An unsigned value with its MSB set cannot be represented by + a signed double_int, while a negative value cannot be represented + by an unsigned double_int. */ + if (TYPE_UNSIGNED (src_type) != unsigned_p + && (TREE_INT_CST_HIGH (vr->min) | TREE_INT_CST_HIGH (vr->max)) < 0) + return false; + + /* Then we can perform the conversion on both ends and compare + the result for equality. */ + tem = tree_to_double_int (vr->min).ext (precision, unsigned_p); + if (tree_to_double_int (vr->min) != tem) + return false; + tem = tree_to_double_int (vr->max).ext (precision, unsigned_p); + if (tree_to_double_int (vr->max) != tem) + return false; + + return true; +} + /* Simplify a conditional using a relational operator to an equality test if the range information indicates only one value can satisfy the original conditional. */ @@ -8590,18 +8641,15 @@ simplify_cond_using_ranges (gimple stmt) } } - /* If we have a comparison of a SSA_NAME boolean against - a constant (which obviously must be [0..1]), see if the - SSA_NAME was set by a type conversion where the source - of the conversion is another SSA_NAME with a range [0..1]. + /* If we have a comparison of an SSA_NAME (OP0) against a constant, + see if OP0 was set by a type conversion where the source of + the conversion is another SSA_NAME with a range that fits + into the range of OP0's type. - If so, we can replace the SSA_NAME in the comparison with - the RHS of the conversion. This will often make the type - conversion dead code which DCE will clean up. */ + If so, the conversion is redundant as the earlier SSA_NAME can be + used for the comparison directly if we just massage the constant in the + comparison. */ if (TREE_CODE (op0) == SSA_NAME - && (TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE - || (INTEGRAL_TYPE_P (TREE_TYPE (op0)) - && TYPE_PRECISION (TREE_TYPE (op0)) == 1)) && TREE_CODE (op1) == INTEGER_CST) { gimple def_stmt = SSA_NAME_DEF_STMT (op0); @@ -8618,8 +8666,9 @@ simplify_cond_using_ranges (gimple stmt) value_range_t *vr = get_value_range (innerop); if (range_int_cst_p (vr) - && operand_equal_p (vr->min, integer_zero_node, 0) - && operand_equal_p (vr->max, integer_one_node, 0)) + && range_fits_type_p (vr, + TYPE_PRECISION (TREE_TYPE (op0)), + TYPE_UNSIGNED (TREE_TYPE (op0)))) { tree newconst = fold_convert (TREE_TYPE (innerop), op1); gimple_cond_set_lhs (stmt, innerop); @@ -8809,57 +8858,6 @@ simplify_conversion_using_ranges (gimple stmt) return true; } -/* Return whether the value range *VR fits in an integer type specified - by PRECISION and UNSIGNED_P. */ - -static bool -range_fits_type_p (value_range_t *vr, unsigned precision, bool unsigned_p) -{ - tree src_type; - unsigned src_precision; - double_int tem; - - /* We can only handle integral and pointer types. */ - src_type = TREE_TYPE (vr->min); - if (!INTEGRAL_TYPE_P (src_type) - && !POINTER_TYPE_P (src_type)) - return false; - - /* An extension is fine unless VR is signed and unsigned_p, - and so is an identity transform. */ - src_precision = TYPE_PRECISION (TREE_TYPE (vr->min)); - if ((src_precision < precision - && !(unsigned_p && !TYPE_UNSIGNED (src_type))) - || (src_precision == precision - && TYPE_UNSIGNED (src_type) == unsigned_p)) - return true; - - /* Now we can only handle ranges with constant bounds. */ - if (vr->type != VR_RANGE - || TREE_CODE (vr->min) != INTEGER_CST - || TREE_CODE (vr->max) != INTEGER_CST) - return false; - - /* For sign changes, the MSB of the double_int has to be clear. - An unsigned value with its MSB set cannot be represented by - a signed double_int, while a negative value cannot be represented - by an unsigned double_int. */ - if (TYPE_UNSIGNED (src_type) != unsigned_p - && (TREE_INT_CST_HIGH (vr->min) | TREE_INT_CST_HIGH (vr->max)) < 0) - return false; - - /* Then we can perform the conversion on both ends and compare - the result for equality. */ - tem = tree_to_double_int (vr->min).ext (precision, unsigned_p); - if (tree_to_double_int (vr->min) != tem) - return false; - tem = tree_to_double_int (vr->max).ext (precision, unsigned_p); - if (tree_to_double_int (vr->max) != tem) - return false; - - return true; -} - /* Simplify a conversion from integral SSA name to float in STMT. */ static bool