From patchwork Wed Oct 7 09:54:11 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Hurugalawadi, Naveen" X-Patchwork-Id: 527211 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.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 5893C1402B4 for ; Wed, 7 Oct 2015 20:54:28 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=T9Ds/eVG; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:content-type:mime-version; q=dns; s= default; b=osvhlB8lDfiE6jYxfgRr7DrR9Z82Rvt4cA3zzJI2evKP2svkecw0k u84XmaDokkHFvEogu1NT+V8GcKtbn2Q4EdlrWPt+kNn4hxYsdhHCsMbDeIquKxPd Gk9v3nMLoJaLztw2aLlo0rbKByPksViO4ZcpXY/opK7fKxfsge6o/s= 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:from :to:subject:date:message-id:content-type:mime-version; s= default; bh=AEbDbfLNTd3ZqdOqbPhPN5HKLcQ=; b=T9Ds/eVGpCBIiC91mY2f xHPh1Wn8HiSXBY8/3b89u3tl1O0XlCNU62NpzsuDbf4Cggs4WokjfDSXnnGStkHn ZQ2UUFpeaM0aDbwFdjI47W1jLH2aNiJEzibaoBo33bvSoeGwxpHNKRDhMnZX2rYP dQ/lVKNtaXpPlmeJ6jZ3S5U= Received: (qmail 119616 invoked by alias); 7 Oct 2015 09:54:19 -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 119599 invoked by uid 89); 7 Oct 2015 09:54:18 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=1.4 required=5.0 tests=AWL, BAYES_50, KAM_LAZY_DOMAIN_SECURITY, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS autolearn=no version=3.3.2 X-HELO: na01-bl2-obe.outbound.protection.outlook.com Received: from mail-bl2on0075.outbound.protection.outlook.com (HELO na01-bl2-obe.outbound.protection.outlook.com) (65.55.169.75) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-SHA256 encrypted) ESMTPS; Wed, 07 Oct 2015 09:54:16 +0000 Received: from SN2PR0701MB1024.namprd07.prod.outlook.com (10.160.57.150) by SN2PR0701MB1022.namprd07.prod.outlook.com (10.160.57.148) with Microsoft SMTP Server (TLS) id 15.1.286.20; Wed, 7 Oct 2015 09:54:12 +0000 Received: from SN2PR0701MB1024.namprd07.prod.outlook.com ([10.160.57.150]) by SN2PR0701MB1024.namprd07.prod.outlook.com ([10.160.57.150]) with mapi id 15.01.0286.019; Wed, 7 Oct 2015 09:54:12 +0000 From: "Hurugalawadi, Naveen" To: "gcc-patches@gcc.gnu.org" Subject: Move some bit and binary optimizations in simplify and match Date: Wed, 7 Oct 2015 09:54:11 +0000 Message-ID: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Naveen.Hurugalawadi@caviumnetworks.com; x-microsoft-exchange-diagnostics: 1; SN2PR0701MB1022; 5:GAUosohhJwDa2632rcvP4QT3lDL0ZsM4Lsnt4kWpYsZ/RuSiir8KPfnur7G63TJUTcOwqJjHCOxbOpxxe/l4kx39ZYKxh67Q4ojpn2qT3UeYZ4LtARYBWO4/2LY9cv9kaYgWumnRMhsRiOPvGXTwEw==; 24:1jFGWbXVbJOGLH/1lbY9bw0wCnkA8qb4T2FugTpiy7YhIZRiWd+864Qp+GTwt1jbci6T8QsRLeFIzaxdfO2qr+UE+xgeV6tfaeQtRhYoQfo=; 20:GP/B3ad3mfqHuSXoVl1kmcKPKu8LPaSgkjd7VAHUwca1gMMqotHMw3qqfaqhfhyFMFHHbkzYiIb3F2Nlw890fQ== x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:SN2PR0701MB1022; x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:; x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(601004)(2401047)(8121501046)(520078)(5005006)(3002001); SRVR:SN2PR0701MB1022; BCL:0; PCL:0; RULEID:; SRVR:SN2PR0701MB1022; x-forefront-prvs: 0722981D2A x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(199003)(164054003)(189002)(377424004)(54534003)(101416001)(46102003)(5007970100001)(64706001)(86362001)(189998001)(99286002)(87936001)(50986999)(99936001)(2351001)(106116001)(33656002)(19580395003)(229853001)(92566002)(19580405001)(2501003)(76576001)(5003600100002)(74316001)(5004730100002)(2900100001)(54356999)(110136002)(77096005)(105586002)(5890100001)(5001920100001)(122556002)(11100500001)(102836002)(97736004)(5008740100001)(40100003)(81156007)(10400500002)(5001960100002)(107886002)(5002640100001)(106356001)(450100001); DIR:OUT; SFP:1101; SCL:1; SRVR:SN2PR0701MB1022; H:SN2PR0701MB1024.namprd07.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; A:1; MX:1; LANG:en; received-spf: None (protection.outlook.com: caviumnetworks.com does not designate permitted sender hosts) spamdiagnosticoutput: 1:23 spamdiagnosticmetadata: NSPM MIME-Version: 1.0 X-OriginatorOrg: caviumnetworks.com X-MS-Exchange-CrossTenant-originalarrivaltime: 07 Oct 2015 09:54:11.4576 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 711e4ccf-2e9b-4bcf-a551-4094005b6194 X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN2PR0701MB1022 Hi, Please find attached the patch that moves some more patterns from fold-const using simplify and match. Please review the patch and let me know if any modifications are required. Tested the patch on X86 without any regressions. Thanks, Naveen ChangeLog 2015-10-07 Naveen H.S * fold-const.c (fold_binary_loc) : Move X + (X / CST) * -CST -> X % CST to match.pd. Move Fold (A & ~B) - (A & B) into (A ^ B) - B to match.pd. Move (-A) * (-B) -> A * B to match.pd. Move (a * (1 << b)) is (a << b) to match.pd. Move convert (C1/X)*C2 into (C1*C2)/X to match.pd. Move (X & ~Y) | (~X & Y) is X ^ Y to match.pd. Move ~X & X, (X == 0) & X, and !X & X are zero to match.pd. Move X & ~X , X & (X == 0), and X & !X are zero to match.pd. Move Fold X & (X ^ Y) as X & ~Y to match.pd. Move Fold X & (Y ^ X) as ~Y & X to match.pd. * match.pd (plus @0 (mult:s (trunc_div:s @0 INTEGER_CST@1) (negate @1))): New simplifier. (minus (bit_and:s @0 (bit_not:s @1)) (bit_and:s @0 @1)) : New simplifier. (mult:c @0 (lshift integer_onep@1 @2)): New simplifier. (mult:c (plus @0 @0) INTEGER_CST@1): New simplifier. (mult (rdiv REAL_CST@0 @1) REAL_CST@2): New simplifier. (bit_ior (bit_and:s @0 (bit_not:s @1)) (bit_and:s (bit_not:s @0) @1)) : New simplifier. (bit_and:c @0 (bit_not:s @0)): New simplifier. (bit_and:c @0 (eq @0 integer_zerop@1)): New simplifier. (bit_and @0 (bit_xor:s @0 @1)): New simplifier. (bit_and @0 (bit_xor:s @1 @0)): New simplifier. (mult:c (negate @0) (negate @1)): New simplifier. diff --git a/gcc/fold-const.c b/gcc/fold-const.c index 7231fd6..ad850f0 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -9191,26 +9191,6 @@ fold_binary_loc (location_t loc, return NULL_TREE; case PLUS_EXPR: - if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type)) - { - /* X + (X / CST) * -CST is X % CST. */ - if (TREE_CODE (arg1) == MULT_EXPR - && TREE_CODE (TREE_OPERAND (arg1, 0)) == TRUNC_DIV_EXPR - && operand_equal_p (arg0, - TREE_OPERAND (TREE_OPERAND (arg1, 0), 0), 0)) - { - tree cst0 = TREE_OPERAND (TREE_OPERAND (arg1, 0), 1); - tree cst1 = TREE_OPERAND (arg1, 1); - tree sum = fold_binary_loc (loc, PLUS_EXPR, TREE_TYPE (cst1), - cst1, cst0); - if (sum && integer_zerop (sum)) - return fold_convert_loc (loc, type, - fold_build2_loc (loc, TRUNC_MOD_EXPR, - TREE_TYPE (arg0), arg0, - cst0)); - } - } - /* Handle (A1 * C1) + (A2 * C2) with A1, A2 or C1, C2 being the same or one. Make sure the type is not saturating and has the signedness of the stripped operands, as fold_plusminus_mult_expr will re-associate. @@ -9651,28 +9631,6 @@ fold_binary_loc (location_t loc, fold_convert_loc (loc, type, TREE_OPERAND (arg0, 0))); - if (! FLOAT_TYPE_P (type)) - { - /* Fold (A & ~B) - (A & B) into (A ^ B) - B, where B is - any power of 2 minus 1. */ - if (TREE_CODE (arg0) == BIT_AND_EXPR - && TREE_CODE (arg1) == BIT_AND_EXPR - && operand_equal_p (TREE_OPERAND (arg0, 0), - TREE_OPERAND (arg1, 0), 0)) - { - tree mask0 = TREE_OPERAND (arg0, 1); - tree mask1 = TREE_OPERAND (arg1, 1); - tree tem = fold_build1_loc (loc, BIT_NOT_EXPR, type, mask0); - - if (operand_equal_p (tem, mask1, 0)) - { - tem = fold_build2_loc (loc, BIT_XOR_EXPR, type, - TREE_OPERAND (arg0, 0), mask1); - return fold_build2_loc (loc, MINUS_EXPR, type, tem, mask1); - } - } - } - /* Fold __complex__ ( x, 0 ) - __complex__ ( 0, y ) to __complex__ ( x, -y ). This is not the same for SNaNs or if signed zeros are involved. */ @@ -9762,20 +9720,6 @@ fold_binary_loc (location_t loc, goto associate; case MULT_EXPR: - /* (-A) * (-B) -> A * B */ - if (TREE_CODE (arg0) == NEGATE_EXPR && negate_expr_p (arg1)) - return fold_build2_loc (loc, MULT_EXPR, type, - fold_convert_loc (loc, type, - TREE_OPERAND (arg0, 0)), - fold_convert_loc (loc, type, - negate_expr (arg1))); - if (TREE_CODE (arg1) == NEGATE_EXPR && negate_expr_p (arg0)) - return fold_build2_loc (loc, MULT_EXPR, type, - fold_convert_loc (loc, type, - negate_expr (arg0)), - fold_convert_loc (loc, type, - TREE_OPERAND (arg1, 0))); - if (! FLOAT_TYPE_P (type)) { /* Transform x * -C into -x * C if x is easily negatable. */ @@ -9789,16 +9733,6 @@ fold_binary_loc (location_t loc, negate_expr (arg0)), tem); - /* (a * (1 << b)) is (a << b) */ - if (TREE_CODE (arg1) == LSHIFT_EXPR - && integer_onep (TREE_OPERAND (arg1, 0))) - return fold_build2_loc (loc, LSHIFT_EXPR, type, op0, - TREE_OPERAND (arg1, 1)); - if (TREE_CODE (arg0) == LSHIFT_EXPR - && integer_onep (TREE_OPERAND (arg0, 0))) - return fold_build2_loc (loc, LSHIFT_EXPR, type, op1, - TREE_OPERAND (arg0, 1)); - /* (A + A) * C -> A * 2 * C */ if (TREE_CODE (arg0) == PLUS_EXPR && TREE_CODE (arg1) == INTEGER_CST @@ -9841,21 +9775,6 @@ fold_binary_loc (location_t loc, } else { - /* Convert (C1/X)*C2 into (C1*C2)/X. This transformation may change - the result for floating point types due to rounding so it is applied - only if -fassociative-math was specify. */ - if (flag_associative_math - && TREE_CODE (arg0) == RDIV_EXPR - && TREE_CODE (arg1) == REAL_CST - && TREE_CODE (TREE_OPERAND (arg0, 0)) == REAL_CST) - { - tree tem = const_binop (MULT_EXPR, TREE_OPERAND (arg0, 0), - arg1); - if (tem) - return fold_build2_loc (loc, RDIV_EXPR, type, tem, - TREE_OPERAND (arg0, 1)); - } - /* Strip sign operations from X in X*X, i.e. -Y*-Y -> Y*Y. */ if (operand_equal_p (arg0, arg1, 0)) { @@ -9972,28 +9891,6 @@ fold_binary_loc (location_t loc, arg1); } - /* (X & ~Y) | (~X & Y) is X ^ Y */ - if (TREE_CODE (arg0) == BIT_AND_EXPR - && TREE_CODE (arg1) == BIT_AND_EXPR) - { - tree a0, a1, l0, l1, n0, n1; - - a0 = fold_convert_loc (loc, type, TREE_OPERAND (arg1, 0)); - a1 = fold_convert_loc (loc, type, TREE_OPERAND (arg1, 1)); - - l0 = fold_convert_loc (loc, type, TREE_OPERAND (arg0, 0)); - l1 = fold_convert_loc (loc, type, TREE_OPERAND (arg0, 1)); - - n0 = fold_build1_loc (loc, BIT_NOT_EXPR, type, l0); - n1 = fold_build1_loc (loc, BIT_NOT_EXPR, type, l1); - - if ((operand_equal_p (n0, a0, 0) - && operand_equal_p (n1, a1, 0)) - || (operand_equal_p (n0, a1, 0) - && operand_equal_p (n1, a0, 0))) - return fold_build2_loc (loc, BIT_XOR_EXPR, type, l0, n1); - } - /* See if this can be simplified into a rotate first. If that is unsuccessful continue in the association code. */ goto bit_rotate; @@ -10012,22 +9909,6 @@ fold_binary_loc (location_t loc, goto bit_rotate; case BIT_AND_EXPR: - /* ~X & X, (X == 0) & X, and !X & X are always zero. */ - if ((TREE_CODE (arg0) == BIT_NOT_EXPR - || TREE_CODE (arg0) == TRUTH_NOT_EXPR - || (TREE_CODE (arg0) == EQ_EXPR - && integer_zerop (TREE_OPERAND (arg0, 1)))) - && operand_equal_p (TREE_OPERAND (arg0, 0), arg1, 0)) - return omit_one_operand_loc (loc, type, integer_zero_node, arg1); - - /* X & ~X , X & (X == 0), and X & !X are always zero. */ - if ((TREE_CODE (arg1) == BIT_NOT_EXPR - || TREE_CODE (arg1) == TRUTH_NOT_EXPR - || (TREE_CODE (arg1) == EQ_EXPR - && integer_zerop (TREE_OPERAND (arg1, 1)))) - && operand_equal_p (arg0, TREE_OPERAND (arg1, 0), 0)) - return omit_one_operand_loc (loc, type, integer_zero_node, arg0); - /* Fold (X ^ 1) & 1 as (X & 1) == 0. */ if (TREE_CODE (arg0) == BIT_XOR_EXPR && INTEGRAL_TYPE_P (type) @@ -10083,26 +9964,6 @@ fold_binary_loc (location_t loc, fold_build1_loc (loc, BIT_NOT_EXPR, type, tem), fold_convert_loc (loc, type, arg1)); } - /* Fold X & (X ^ Y) as X & ~Y. */ - if (TREE_CODE (arg1) == BIT_XOR_EXPR - && operand_equal_p (arg0, TREE_OPERAND (arg1, 0), 0)) - { - tem = fold_convert_loc (loc, type, TREE_OPERAND (arg1, 1)); - return fold_build2_loc (loc, BIT_AND_EXPR, type, - fold_convert_loc (loc, type, arg0), - fold_build1_loc (loc, BIT_NOT_EXPR, type, tem)); - } - /* Fold X & (Y ^ X) as ~Y & X. */ - if (TREE_CODE (arg1) == BIT_XOR_EXPR - && operand_equal_p (arg0, TREE_OPERAND (arg1, 1), 0) - && reorder_operands_p (arg0, TREE_OPERAND (arg1, 0))) - { - tem = fold_convert_loc (loc, type, TREE_OPERAND (arg1, 0)); - return fold_build2_loc (loc, BIT_AND_EXPR, type, - fold_build1_loc (loc, BIT_NOT_EXPR, type, tem), - fold_convert_loc (loc, type, arg0)); - } - /* Fold (X * Y) & -(1 << CST) to X * Y if Y is a constant multiple of 1 << CST. */ if (TREE_CODE (arg1) == INTEGER_CST) diff --git a/gcc/match.pd b/gcc/match.pd index bd5c267..690ea14 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -316,6 +316,56 @@ along with GCC; see the file COPYING3. If not see (coss (op @0)) (coss @0)))) +/* Fold X + (X / CST) * -CST to X % CST. */ +(simplify + (plus @0 (mult:s (trunc_div:s @0 INTEGER_CST@1) (negate @1))) + (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type)) + (trunc_mod @0 @1))) + +/* Fold (A & ~B) - (A & B) into (A ^ B) - B. */ +(simplify + (minus (bit_and:s @0 (bit_not:s @1)) (bit_and:s @0 @1)) + (if (! FLOAT_TYPE_P (type)) + (minus (bit_xor @0 @1) @1))) + +/* Fold (a * (1 << b)) into (a << b) */ +(simplify + (mult:c @0 (lshift integer_onep@1 @2)) + (if (! FLOAT_TYPE_P (type)) + (lshift @0 @2))) + +/* Fold (C1/X)*C2 into (C1*C2)/X. */ +(simplify + (mult (rdiv REAL_CST@0 @1) REAL_CST@2) + (if (FLOAT_TYPE_P (type) + && flag_associative_math) + (rdiv (mult @0 @2) @1))) + +/* Simplify (X & ~Y) | (~X & Y) is X ^ Y. */ +(simplify + (bit_ior (bit_and:s @0 (bit_not:s @1)) (bit_and:s (bit_not:s @0) @1)) + (bit_xor @0 @1)) + +/* Simplify ~X & X as zero. */ +(simplify + (bit_and:c @0 (bit_not:s @0)) + { build_zero_cst (type); }) + +/* Simplify (X == 0) & X as zero. */ +(simplify + (bit_and:c @0 (eq @0 integer_zerop@1)) + @1) + +/* Fold X & (X ^ Y) as X & ~Y. */ +(simplify + (bit_and @0 (bit_xor:s @0 @1)) + (bit_and @0 (bit_not @1))) + +/* Fold X & (Y ^ X) as ~Y & X. */ +(simplify + (bit_and @0 (bit_xor:s @1 @0)) + (bit_and (bit_not @1) @0)) + /* X % Y is smaller than Y. */ (for cmp (lt ge) (simplify @@ -549,6 +599,11 @@ along with GCC; see the file COPYING3. If not see (if (!FIXED_POINT_TYPE_P (type)) (plus @0 (negate @1)))) +/* (-A) * (-B) -> A * B */ +(simplify + (mult:c (negate @0) (negate @1)) + (mult @0 @1)) + /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST)) when profitable. For bitwise binary operations apply operand conversions to the