From patchwork Wed Apr 20 15:50:57 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Kai Tietz X-Patchwork-Id: 92226 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 CC34CB7007 for ; Thu, 21 Apr 2011 01:51:18 +1000 (EST) Received: (qmail 29159 invoked by alias); 20 Apr 2011 15:51:16 -0000 Received: (qmail 28856 invoked by uid 22791); 20 Apr 2011 15:51:15 -0000 X-SWARE-Spam-Status: No, hits=-1.0 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_ENVFROM_END_DIGIT, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, RFC_ABUSE_POST X-Spam-Check-By: sourceware.org Received: from mail-qw0-f47.google.com (HELO mail-qw0-f47.google.com) (209.85.216.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 20 Apr 2011 15:51:00 +0000 Received: by qwh5 with SMTP id 5so479659qwh.20 for ; Wed, 20 Apr 2011 08:50:59 -0700 (PDT) MIME-Version: 1.0 Received: by 10.229.43.232 with SMTP id x40mr5644132qce.32.1303314659353; Wed, 20 Apr 2011 08:50:59 -0700 (PDT) Received: by 10.229.67.96 with HTTP; Wed, 20 Apr 2011 08:50:56 -0700 (PDT) In-Reply-To: <4DAEFD44.5020006@redhat.com> References: <4DAEFD44.5020006@redhat.com> Date: Wed, 20 Apr 2011 17:50:57 +0200 Message-ID: Subject: Re: [patch middle-end]: Missed optimization for (x & ~y) | (~x & y) From: Kai Tietz To: Richard Henderson Cc: GCC Patches , Jakub Jelinek 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 2011/4/20 Richard Henderson : > On 04/20/2011 08:22 AM, Kai Tietz wrote: >> +      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, TRUTH_XOR_EXPR, type, l0, n1); > > First, you typoed BIT_XOR_EXPR in this first block. Duh, corrected. > Second, I don't see how you're arbitrarily choosing L0 and N1 in the > expansion.  If you write the expression the other way around, > >  (~x & y) | (x & ~y) > > don't you wind up with > >  (~x ^ ~y) > > ?  Or do the extra NOT expressions get folded away anyway? Not I didn't wind up here. First ~X ^ ~Y is in result the same as X ^ Y, and for this I used here the explicit folding. Well, it might be a bit slower, but it has the advantage to compare equal transformations in doubt. >> +      if (TREE_CODE (arg0) == TREE_CODE (arg1) >> +       && (TREE_CODE (arg1) == TRUTH_AND_EXPR >> +           || TREE_CODE (arg1) == TRUTH_ANDIF_EXPR)) > > I don't believe you want to apply this transformation with ANDIF. Yes, it is superflous. I removed it. > > r~ > Adjusted patch attached. Kai Index: gcc/gcc/fold-const.c =================================================================== --- gcc.orig/gcc/fold-const.c 2011-04-20 17:10:39.478091900 +0200 +++ gcc/gcc/fold-const.c 2011-04-20 17:41:23.427677200 +0200 @@ -10660,6 +10660,28 @@ fold_binary_loc (location_t loc, && reorder_operands_p (arg0, TREE_OPERAND (arg1, 0))) return omit_one_operand_loc (loc, type, arg0, TREE_OPERAND (arg1, 0)); + /* (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); + } + t1 = distribute_bit_expr (loc, code, type, arg0, arg1); if (t1 != NULL_TREE) return t1; @@ -12039,6 +12061,27 @@ fold_binary_loc (location_t loc, && operand_equal_p (arg0, TREE_OPERAND (arg1, 0), 0)) return omit_one_operand_loc (loc, type, integer_one_node, arg0); + /* (X && !Y) || (!X && Y) is X ^ Y */ + if (TREE_CODE (arg0) == TREE_CODE (arg1) + && TREE_CODE (arg1) == TRUTH_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, TRUTH_NOT_EXPR, type, l0); + n1 = fold_build1_loc (loc, TRUTH_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, TRUTH_XOR_EXPR, type, l0, n1); + } goto truth_andor; case TRUTH_XOR_EXPR: Index: gcc/gcc/testsuite/gcc.dg/binop-xor1.c =================================================================== --- /dev/null 1970-01-01 00:00:00.000000000 +0000 +++ gcc/gcc/testsuite/gcc.dg/binop-xor1.c 2011-04-20 17:11:22.905039900 +0200 @@ -0,0 +1,14 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (int a, int b, int c) +{ + return ((a && !b && c) || (!a && b && c)); +} + +/* We expect to see ""; confirm that, so that we know to count + it in the real test. */ +/* { dg-final { scan-tree-dump-times "\]*>" 5 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "\^" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc/gcc/testsuite/gcc.dg/binop-xor2.c =================================================================== --- /dev/null 1970-01-01 00:00:00.000000000 +0000 +++ gcc/gcc/testsuite/gcc.dg/binop-xor2.c 2011-04-20 17:11:22.908540300 +0200 @@ -0,0 +1,14 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (int a, int b) +{ + return ((a & ~b) | (~a & b)); +} + +/* We expect to see ""; confirm that, so that we know to count + it in the real test. */ +/* { dg-final { scan-tree-dump-times "\]*>" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "\^" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc/gcc/testsuite/gcc.dg/binop-xor3.c =================================================================== --- /dev/null 1970-01-01 00:00:00.000000000 +0000 +++ gcc/gcc/testsuite/gcc.dg/binop-xor3.c 2011-04-20 17:11:22.911040600 +0200 @@ -0,0 +1,14 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (int a, int b) +{ + return ((a && !b) || (!a && b)); +} + +/* We expect to see ""; confirm that, so that we know to count + it in the real test. */ +/* { dg-final { scan-tree-dump-times "\]*>" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "\^" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc/gcc/testsuite/gcc.dg/binop-xor4.c =================================================================== --- /dev/null 1970-01-01 00:00:00.000000000 +0000 +++ gcc/gcc/testsuite/gcc.dg/binop-xor4.c 2011-04-20 17:11:22.913541000 +0200 @@ -0,0 +1,14 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (int a, int b, int c) +{ + return ((a & ~b) | (~a & b)) & c; +} + +/* We expect to see ""; confirm that, so that we know to count + it in the real test. */ +/* { dg-final { scan-tree-dump-times "\]*>" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "\^" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc/gcc/testsuite/gcc.dg/binop-xor5.c =================================================================== --- /dev/null 1970-01-01 00:00:00.000000000 +0000 +++ gcc/gcc/testsuite/gcc.dg/binop-xor5.c 2011-04-20 17:11:22.916541300 +0200 @@ -0,0 +1,15 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (int a, int b, int c) +{ + return ((a & ~b & c) | (~a & b & c)); +} + +/* We expect to see ""; confirm that, so that we know to count + it in the real test. */ +/* { dg-final { scan-tree-dump-times "\]*>" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "\^" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "\&" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */