From patchwork Sat Apr 21 04:06:49 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew Pinski X-Patchwork-Id: 154191 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 709A6B6FC8 for ; Sat, 21 Apr 2012 14:07:38 +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=1335586058; h=Comment: DomainKey-Signature:Received:Received:Received:Received: MIME-Version:Received:Received:In-Reply-To:References:Date: Message-ID:Subject:From:To:Cc:Content-Type:Mailing-List: Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:Sender:Delivered-To; bh=PPWG1/UQBUmrM0PNwSKj4bOlBgE=; b=gLPZf5RHt/E/xVxtVgRNAgYBJZEl0QQt7DpyjyJEf21WoOntc1ovGIGE2Vlhsp llYkciQHWC2GDSScbW8bgrQ3GNoQRBL3nn9qbipySfCJ4wPDhkFlZzx09wLXzvPx AnSR1XRVHzFChmjI70xMfU81Drl61tFI68IhHkQjOWJ38= 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:MIME-Version:Received:Received:In-Reply-To:References:Date:Message-ID:Subject:From:To:Cc:Content-Type:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=szIcNLGh3H2CvHl1Xca5PCVcGpgqvxqh4ug+nBKKDz319N2enBPHtTDr3GtfHX Q+P1wc2ov7Ipurj3+gXzbJSP3tK7QfMq4DI5xHSNUJc1/nD6RCmfPffCrFLhTP+9 /zHFa3qA7Y8srFbNAfCwePIFzj/bmCHEfjBnB2zyqSN2I=; Received: (qmail 21313 invoked by alias); 21 Apr 2012 04:07:32 -0000 Received: (qmail 21302 invoked by uid 22791); 21 Apr 2012 04:07:30 -0000 X-SWARE-Spam-Status: No, hits=-5.3 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, FREEMAIL_FROM, KHOP_RCVD_TRUST, KHOP_THREADED, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE, TW_TM X-Spam-Check-By: sourceware.org Received: from mail-wg0-f41.google.com (HELO mail-wg0-f41.google.com) (74.125.82.41) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sat, 21 Apr 2012 04:06:51 +0000 Received: by wgbds1 with SMTP id ds1so1366775wgb.2 for ; Fri, 20 Apr 2012 21:06:49 -0700 (PDT) MIME-Version: 1.0 Received: by 10.180.76.240 with SMTP id n16mr3090025wiw.10.1334981209694; Fri, 20 Apr 2012 21:06:49 -0700 (PDT) Received: by 10.216.100.197 with HTTP; Fri, 20 Apr 2012 21:06:49 -0700 (PDT) In-Reply-To: References: Date: Fri, 20 Apr 2012 21:06:49 -0700 Message-ID: Subject: Re: [PATCH] Fix PR 33512 Folding of x & ((~x) | y) into x & y on the tree level From: Andrew Pinski To: Richard Guenther Cc: GCC Patches 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 This time with the patch and describing what the bug was. The problem was defcodefor_name does not always set arg1 and arg2. This fixes it so it is always set to NULL if they don't exist. Thanks, Andrew On Fri, Apr 20, 2012 at 9:05 PM, Andrew Pinski wrote: > On Thu, Jan 19, 2012 at 3:13 AM, Richard Guenther > wrote: >> On Thu, Jan 19, 2012 at 10:00 AM, Andrew Pinski >> wrote: >>> On Tue, Jan 17, 2012 at 1:38 AM, Richard Guenther >>> wrote: >>>> On Tue, Jan 17, 2012 at 8:06 AM, Andrew Pinski >>>> wrote: >>>>> Hi, >>>>>  This adds the folding of x & ((~x) | y)) into x & y on the tree >>>>> level via fold-const.c >>>>> There is already partly done on the RTL level but it would be a good >>>>> thing for the tree level also. >>>>> >>>>> >>>>> OK for 4.8 (yes I know we have not branched yet but I thought I would >>>>> send it out so I don't forget about it)? >>>>> Bootstrapped and tested on x86_64-linux-gnu with no regressions. >>>> >>>> Can you instead patch tree-ssa-forwprop.c:simplify_bitwise_binary? >>> >>> Yes and here is a new patch which also adds optimizing x | ((~x) & y)) to x | y. >>> Also it adds the optimizing x & (x | y) to x and x | (x & y) to x to >>> tree-ssa-forwprop.c:simplify_bitwise_binary >>> since it was an easy extension on top of the ~x case (well I >>> implemented the one without the ~ first).  I did not remove those >>> folding from fold-const.c though. >>> >>> Also I was thinking maybe this belongs in reassociate though I don't >>> see how to do it. >> >> I still have plans to create that piecewise gimple_fold (see my proposal >> from early last year) that would be the container for this kind of pattern >> matching.  It would then be usable from reassoc as well (but reassoc >> has the issue of only collecting one kind of op, so its simplification >> wouldn't trigger reliably on these). >> >> http://gcc.gnu.org/ml/gcc-patches/2011-03/msg01099.html >> >>> OK for 4.8, once in stage 1? Again bootstrapped and tested on >>> x86_64-linux-gnu with no regressions. >> >> Ok. > > Here is an updated patch which fixes a bug which I found while doing > the treecombine branch.  I rewrote defcodefor_name so more than > SSA_NAMEs can be passed to it. > > OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions. > > Thanks, > Andrew Pinski > > ChangeLog: > > ChangeLog: > * tree-ssa-forwprop.c (defcodefor_name): New function. > (simplify_bitwise_binary): Use defcodefor_name instead of manually > Simplify "( X | Y) & X" to X and "( X & Y) | X" to X. > Simplify "(~X | Y) & X" to "X & Y" and > "(~X & Y) | X" to "X | Y". > > testsuite/ChangeLog: > * gcc.dg/tree-ssa/andor-3.c: New testcase. > * gcc.dg/tree-ssa/andor-4.c: New testcase. > * gcc.dg/tree-ssa/andor-5.c: New testcase. > >> >> Thanks, >> Richard. >> >>> Thanks, >>> Andrew Pinski >>> >>> ChangeLog: >>> * tree-ssa-forwprop.c (defcodefor_name): New function. >>> (simplify_bitwise_binary): Use defcodefor_name. >>> Simplify "( X | Y) & X" to X and "( X & Y) | X" to X. >>> Simplify "(~X | Y) & X" to "X & Y" and >>> "(~X & Y) | X" to "X | Y". >>> >>> testsuite/ChangeLog: >>> * gcc.dg/tree-ssa/andor-3.c: New testcase. >>> * gcc.dg/tree-ssa/andor-4.c: New testcase. >>> * gcc.dg/tree-ssa/andor-5.c: New testcase. >>> >>> >>>> >>>> Thanks, >>>> Richard. >>>> >>>>> Thanks, >>>>> Andrew Pinski >>>>> >>>>> ChangeLog: >>>>> * fold-const.c (fold_binary_loc ): Add folding of x >>>>> & (~x | y) into x & y. >>>>> >>>>> testsuite/ChangeLog: >>>>> * gcc.dg/tree-ssa/andor-3.c: New testcase. Index: testsuite/gcc.dg/tree-ssa/andor-3.c =================================================================== --- testsuite/gcc.dg/tree-ssa/andor-3.c (revision 0) +++ testsuite/gcc.dg/tree-ssa/andor-3.c (revision 0) @@ -0,0 +1,24 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int f(int y, int x) +{ + return x & ((~x) | y); +} +int f1(int y, int x) +{ + return x & (y | (~x)); +} +int f2(int y, int x) +{ + return ((~x) | y) & x; +} +int f3(int y, int x) +{ + return (y | (~x)) & x; +} + + +/* { dg-final { scan-tree-dump-times "~x" 0 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "x_..D. \& y_..D." 4 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: testsuite/gcc.dg/tree-ssa/andor-4.c =================================================================== --- testsuite/gcc.dg/tree-ssa/andor-4.c (revision 0) +++ testsuite/gcc.dg/tree-ssa/andor-4.c (revision 0) @@ -0,0 +1,24 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int f(int y, int x) +{ + return x | ((~x) & y); +} +int f1(int y, int x) +{ + return x | (y & (~x)); +} +int f2(int y, int x) +{ + return ((~x) & y) | x; +} +int f3(int y, int x) +{ + return (y & (~x)) | x; +} + + +/* { dg-final { scan-tree-dump-times "~x" 0 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "x_..D. \\\| y_..D." 4 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: testsuite/gcc.dg/tree-ssa/andor-5.c =================================================================== --- testsuite/gcc.dg/tree-ssa/andor-5.c (revision 0) +++ testsuite/gcc.dg/tree-ssa/andor-5.c (revision 0) @@ -0,0 +1,50 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int f(int y, int x) +{ + int a = x | y; + return a & x; +} +int f1(int y, int x) +{ + int a = y | x; + return a & x; +} +int f2(int y, int x) +{ + int a = x | y; + return x & a; +} +int f3(int y, int x) +{ + int a = x | y; + return x & a; +} +int f4(int y, int x) +{ + int a = x & y; + return a | x; +} +int f5(int y, int x) +{ + int a = y & x; + return a | x; +} +int f6(int y, int x) +{ + int a = x & y; + return x | a; +} +int f7(int y, int x) +{ + int a = x & y; + return x | a; +} +/* These all should be optimized to just return x; */ + + +/* { dg-final { scan-tree-dump-times "\\\|" 0 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "\&" 0 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "return x_..D.;" 8 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: tree-ssa-forwprop.c =================================================================== --- tree-ssa-forwprop.c (revision 186645) +++ tree-ssa-forwprop.c (working copy) @@ -1794,6 +1794,51 @@ simplify_bitwise_binary_1 (enum tree_cod return NULL_TREE; } +/* Given a ssa_name in NAME see if it was defined by an assignment and + set CODE to be the code and ARG1 to the first operand on the rhs and ARG2 + to the second operand on the rhs. */ + +static inline void +defcodefor_name (tree name, enum tree_code *code, tree *arg1, tree *arg2) +{ + gimple def; + enum tree_code code1; + tree arg11; + tree arg21; + tree arg31; + enum gimple_rhs_class grhs_class; + + code1 = TREE_CODE (name); + arg11 = name; + arg21 = NULL_TREE; + grhs_class = get_gimple_rhs_class (code1); + + if (code1 == SSA_NAME) + { + def = SSA_NAME_DEF_STMT (name); + + if (def && is_gimple_assign (def) + && can_propagate_from (def)) + { + code1 = gimple_assign_rhs_code (def); + arg11 = gimple_assign_rhs1 (def); + arg21 = gimple_assign_rhs2 (def); + arg31 = gimple_assign_rhs2 (def); + } + } + else if (grhs_class == GIMPLE_TERNARY_RHS + || GIMPLE_BINARY_RHS + || GIMPLE_UNARY_RHS + || GIMPLE_SINGLE_RHS) + extract_ops_from_tree_1 (name, &code1, &arg11, &arg21, &arg31); + + *code = code1; + *arg1 = arg11; + if (arg2) + *arg2 = arg21; + /* Ignore arg3 currently. */ +} + /* Simplify bitwise binary operations. Return true if a transformation applied, otherwise return false. */ @@ -1805,33 +1850,11 @@ simplify_bitwise_binary (gimple_stmt_ite tree arg2 = gimple_assign_rhs2 (stmt); enum tree_code code = gimple_assign_rhs_code (stmt); tree res; - gimple def1 = NULL, def2 = NULL; - tree def1_arg1, def2_arg1; + tree def1_arg1, def1_arg2, def2_arg1, def2_arg2; enum tree_code def1_code, def2_code; - def1_code = TREE_CODE (arg1); - def1_arg1 = arg1; - if (TREE_CODE (arg1) == SSA_NAME) - { - def1 = SSA_NAME_DEF_STMT (arg1); - if (is_gimple_assign (def1)) - { - def1_code = gimple_assign_rhs_code (def1); - def1_arg1 = gimple_assign_rhs1 (def1); - } - } - - def2_code = TREE_CODE (arg2); - def2_arg1 = arg2; - if (TREE_CODE (arg2) == SSA_NAME) - { - def2 = SSA_NAME_DEF_STMT (arg2); - if (is_gimple_assign (def2)) - { - def2_code = gimple_assign_rhs_code (def2); - def2_arg1 = gimple_assign_rhs1 (def2); - } - } + defcodefor_name (arg1, &def1_code, &def1_arg1, &def1_arg2); + defcodefor_name (arg2, &def2_code, &def2_arg1, &def2_arg2); /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST)). */ if (TREE_CODE (arg2) == INTEGER_CST @@ -1890,10 +1913,10 @@ simplify_bitwise_binary (gimple_stmt_ite if (code == BIT_AND_EXPR && def1_code == BIT_IOR_EXPR && TREE_CODE (arg2) == INTEGER_CST - && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST) + && TREE_CODE (def1_arg2) == INTEGER_CST) { tree cst = fold_build2 (BIT_AND_EXPR, TREE_TYPE (arg2), - arg2, gimple_assign_rhs2 (def1)); + arg2, def1_arg2); tree tem; gimple newop; if (integer_zerop (cst)) @@ -1923,10 +1946,10 @@ simplify_bitwise_binary (gimple_stmt_ite || code == BIT_XOR_EXPR) && def1_code == code && TREE_CODE (arg2) == INTEGER_CST - && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST) + && TREE_CODE (def1_arg2) == INTEGER_CST) { tree cst = fold_build2 (code, TREE_TYPE (arg2), - arg2, gimple_assign_rhs2 (def1)); + arg2, def1_arg2); gimple_assign_set_rhs1 (stmt, def1_arg1); gimple_assign_set_rhs2 (stmt, cst); update_stmt (stmt); @@ -1953,6 +1976,86 @@ simplify_bitwise_binary (gimple_stmt_ite return true; } + if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR) + { + enum tree_code ocode = code == BIT_AND_EXPR ? BIT_IOR_EXPR : BIT_AND_EXPR; + if (def1_code == ocode) + { + tree x = arg2; + enum tree_code coden; + tree a1, a2; + /* ( X | Y) & X -> X */ + /* ( X & Y) | X -> X */ + if (x == def1_arg1 + || x == def1_arg2) + { + gimple_assign_set_rhs_from_tree (gsi, x); + update_stmt (gsi_stmt (*gsi)); + return true; + } + + defcodefor_name (def1_arg1, &coden, &a1, &a2); + /* (~X | Y) & X -> X & Y */ + /* (~X & Y) | X -> X | Y */ + if (coden == BIT_NOT_EXPR && a1 == x) + { + gimple_assign_set_rhs_with_ops (gsi, code, + x, def1_arg2); + gcc_assert (gsi_stmt (*gsi) == stmt); + update_stmt (stmt); + return true; + } + defcodefor_name (def1_arg2, &coden, &a1, &a2); + /* (Y | ~X) & X -> X & Y */ + /* (Y & ~X) | X -> X | Y */ + if (coden == BIT_NOT_EXPR && a1 == x) + { + gimple_assign_set_rhs_with_ops (gsi, code, + x, def1_arg1); + gcc_assert (gsi_stmt (*gsi) == stmt); + update_stmt (stmt); + return true; + } + } + if (def2_code == ocode) + { + enum tree_code coden; + tree a1; + tree x = arg1; + /* X & ( X | Y) -> X */ + /* X | ( X & Y) -> X */ + if (x == def2_arg1 + || x == def2_arg2) + { + gimple_assign_set_rhs_from_tree (gsi, x); + update_stmt (gsi_stmt (*gsi)); + return true; + } + defcodefor_name (def2_arg1, &coden, &a1, NULL); + /* (~X | Y) & X -> X & Y */ + /* (~X & Y) | X -> X | Y */ + if (coden == BIT_NOT_EXPR && a1 == x) + { + gimple_assign_set_rhs_with_ops (gsi, code, + x, def2_arg2); + gcc_assert (gsi_stmt (*gsi) == stmt); + update_stmt (stmt); + return true; + } + defcodefor_name (def2_arg2, &coden, &a1, NULL); + /* (Y | ~X) & X -> X & Y */ + /* (Y & ~X) | X -> X | Y */ + if (coden == BIT_NOT_EXPR && a1 == x) + { + gimple_assign_set_rhs_with_ops (gsi, code, + x, def2_arg1); + gcc_assert (gsi_stmt (*gsi) == stmt); + update_stmt (stmt); + return true; + } + } + } + return false; }