From patchwork Wed Sep 29 19:48:11 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 66092 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 EDB57B70A3 for ; Thu, 30 Sep 2010 05:46:49 +1000 (EST) Received: (qmail 4898 invoked by alias); 29 Sep 2010 19:46:47 -0000 Received: (qmail 4885 invoked by uid 22791); 29 Sep 2010 19:46:46 -0000 X-SWARE-Spam-Status: No, hits=-6.2 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_HI, SPF_HELO_PASS, 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, 29 Sep 2010 19:46:41 +0000 Received: from int-mx08.intmail.prod.int.phx2.redhat.com (int-mx08.intmail.prod.int.phx2.redhat.com [10.5.11.21]) by mx1.redhat.com (8.13.8/8.13.8) with ESMTP id o8TJkdo7014158 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Wed, 29 Sep 2010 15:46:40 -0400 Received: from tyan-ft48-01.lab.bos.redhat.com (tyan-ft48-01.lab.bos.redhat.com [10.16.42.4]) by int-mx08.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id o8TJkcEP008511 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Wed, 29 Sep 2010 15:46:39 -0400 Received: from tyan-ft48-01.lab.bos.redhat.com (tyan-ft48-01.lab.bos.redhat.com [127.0.0.1]) by tyan-ft48-01.lab.bos.redhat.com (8.14.4/8.14.4) with ESMTP id o8TJmEZr028950 for ; Wed, 29 Sep 2010 21:48:14 +0200 Received: (from jakub@localhost) by tyan-ft48-01.lab.bos.redhat.com (8.14.4/8.14.4/Submit) id o8TJmCcV028948 for gcc-patches@gcc.gnu.org; Wed, 29 Sep 2010 21:48:12 +0200 Date: Wed, 29 Sep 2010 21:48:11 +0200 From: Jakub Jelinek To: gcc-patches@gcc.gnu.org Subject: [PATCH] ((A & N) + B) & M optimization (PR tree-optimization/31261) Message-ID: <20100929194811.GE10599@tyan-ft48-01.lab.bos.redhat.com> Reply-To: Jakub Jelinek MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-12-10) 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! I've discovered today I have a 3.5 years old patch unreviewed, which I forgot to ping ever since. Here it is updated to current trunk with the *_loc stuff. This is something RTL simplification usually handles too, but there is nothing in the GIMPLE land that performs such an optimization. The testcase shows a couple of cases that can be optimized. Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? 2010-09-29 Jakub Jelinek PR tree-optimization/31261 * fold-const.c (fold_binary): Optimize ((A & N) + B) & M for constants M and N, M == (1LL << cst) - 1 && (N & M) == M. * gcc.dg/tree-ssa/pr31261.c: New test. Jakub --- gcc/fold-const.c.jj 2010-09-16 11:05:27.000000000 +0200 +++ gcc/fold-const.c 2010-09-29 09:59:48.113522128 +0200 @@ -11071,6 +11071,120 @@ fold_binary_loc (location_t loc, fold_convert_loc (loc, type, arg0)); } + /* For constants M and N, if M == (1LL << cst) - 1 && (N & M) == M, + ((A & N) + B) & M -> (A + B) & M + Similarly if (N & M) == 0, + ((A | N) + B) & M -> (A + B) & M + and for - instead of + (or unary - instead of +) + and/or ^ instead of |. + If B is constant and (B & M) == 0, fold into A & M. */ + if (host_integerp (arg1, 1)) + { + unsigned HOST_WIDE_INT cst1 = tree_low_cst (arg1, 1); + if (~cst1 && (cst1 & (cst1 + 1)) == 0 + && INTEGRAL_TYPE_P (TREE_TYPE (arg0)) + && (TREE_CODE (arg0) == PLUS_EXPR + || TREE_CODE (arg0) == MINUS_EXPR + || TREE_CODE (arg0) == NEGATE_EXPR) + && (TYPE_OVERFLOW_WRAPS (TREE_TYPE (arg0)) + || TREE_CODE (TREE_TYPE (arg0)) == INTEGER_TYPE)) + { + tree pmop[2]; + int which = 0; + unsigned HOST_WIDE_INT cst0; + + pmop[0] = TREE_OPERAND (arg0, 0); + pmop[1] = NULL; + if (TREE_CODE (arg0) != NEGATE_EXPR) + { + pmop[1] = TREE_OPERAND (arg0, 1); + which = 1; + } + + if (!host_integerp (TYPE_MAX_VALUE (TREE_TYPE (arg0)), 1) + || (tree_low_cst (TYPE_MAX_VALUE (TREE_TYPE (arg0)), 1) + & cst1) != cst1) + which = -1; + + for (; which >= 0; which--) + switch (TREE_CODE (pmop[which])) + { + case BIT_AND_EXPR: + case BIT_IOR_EXPR: + case BIT_XOR_EXPR: + if (TREE_CODE (TREE_OPERAND (pmop[which], 1)) + != INTEGER_CST) + break; + /* tree_low_cst not used, because we don't care about + the upper bits. */ + cst0 = TREE_INT_CST_LOW (TREE_OPERAND (pmop[which], 1)); + cst0 &= cst1; + if (TREE_CODE (pmop[which]) == BIT_AND_EXPR) + { + if (cst0 != cst1) + break; + } + else if (cst0 != 0) + break; + pmop[which] = TREE_OPERAND (pmop[which], 0); + break; + case INTEGER_CST: + if ((TREE_CODE (arg0) == PLUS_EXPR + || (TREE_CODE (arg0) == MINUS_EXPR && which == 0)) + && (TREE_INT_CST_LOW (pmop[which]) & cst1) == 0) + pmop[which] = NULL; + break; + default: + break; + } + + if (pmop[0] != TREE_OPERAND (arg0, 0) + || (TREE_CODE (arg0) != NEGATE_EXPR + && pmop[1] != TREE_OPERAND (arg0, 1))) + { + tree utype = type; + if (! TYPE_OVERFLOW_WRAPS (TREE_TYPE (arg0))) + { + utype = unsigned_type_for (type); + if (pmop[0] != NULL) + pmop[0] = fold_convert_loc (loc, utype, pmop[0]); + if (pmop[1] != NULL) + pmop[1] = fold_convert_loc (loc, utype, pmop[1]); + } + + if (TREE_CODE (arg0) == NEGATE_EXPR) + tem = fold_build1_loc (loc, NEGATE_EXPR, utype, pmop[0]); + else if (TREE_CODE (arg0) == PLUS_EXPR) + { + if (pmop[0] != NULL && pmop[1] != NULL) + tem = fold_build2_loc (loc, PLUS_EXPR, utype, + pmop[0], pmop[1]); + else if (pmop[0] != NULL) + tem = pmop[0]; + else if (pmop[1] != NULL) + tem = pmop[1]; + else + return build_int_cst (type, 0); + } + else if (pmop[0] == NULL) + tem = fold_build1_loc (loc, NEGATE_EXPR, utype, pmop[1]); + else + tem = fold_build2_loc (loc, MINUS_EXPR, utype, + pmop[0], pmop[1]); + if (utype == type) + return fold_build2_loc (loc, BIT_AND_EXPR, type, + tem, arg1); + else + { + tem = fold_build2_loc (loc, BIT_AND_EXPR, utype, tem, + fold_convert_loc (loc, utype, + arg1)); + return fold_convert_loc (loc, type, tem); + } + } + } + } + t1 = distribute_bit_expr (loc, code, type, arg0, arg1); if (t1 != NULL_TREE) return t1; --- gcc/testsuite/gcc.dg/tree-ssa/pr31261.c.jj 2010-09-29 09:48:36.374396699 +0200 +++ gcc/testsuite/gcc.dg/tree-ssa/pr31261.c 2010-09-29 10:12:49.612377621 +0200 @@ -0,0 +1,40 @@ +/* PR tree-optimization/31261 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-original" } */ + +unsigned int +f1 (unsigned int a) +{ + return (8 - (a & 7)) & 7; +} + +long int +f2 (long int b) +{ + return (16 + (b & 7)) & 15; +} + +char +f3 (char c) +{ + return -(c & 63) & 31; +} + +int +f4 (int d) +{ + return (12 - (d & 15)) & 7; +} + +int +f5 (int e) +{ + return (12 - (e & 7)) & 15; +} + +/* { dg-final { scan-tree-dump-times "return -a \& 7;" 1 "original" } } */ +/* { dg-final { scan-tree-dump-times "return b \& 7;" 1 "original" } } */ +/* { dg-final { scan-tree-dump-times "return \\(char\\) -\\(unsigned char\\) c \& 31;" 1 "original" } } */ +/* { dg-final { scan-tree-dump-times "return \\(int\\) \\(12 - \\(unsigned int\\) d\\) \& 7;" 1 "original" } } */ +/* { dg-final { scan-tree-dump-times "return 12 - \\(e \& 7\\) \& 15;" 1 "original" } } */ +/* { dg-final { cleanup-tree-dump "original" } } */