From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 12737 invoked by alias); 2 Jul 2011 08:59:28 -0000 Received: (qmail 12725 invoked by uid 22791); 2 Jul 2011 08:59:26 -0000 X-SWARE-Spam-Status: No, hits=-1.8 required=5.0 tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW X-Spam-Check-By: sourceware.org Received: from mail-qy0-f175.google.com (HELO mail-qy0-f175.google.com) (209.85.216.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sat, 02 Jul 2011 08:59:07 +0000 Received: by qyk30 with SMTP id 30so314142qyk.20 for ; Sat, 02 Jul 2011 01:59:06 -0700 (PDT) MIME-Version: 1.0 Received: by 10.229.49.130 with SMTP id v2mr3185680qcf.264.1309597146034; Sat, 02 Jul 2011 01:59:06 -0700 (PDT) Received: by 10.229.65.225 with HTTP; Sat, 2 Jul 2011 01:59:05 -0700 (PDT) In-Reply-To: References: <2017997593.883643.1309520672925.JavaMail.root@zmail06.collab.prod.int.phx2.redhat.com> Date: Sat, 02 Jul 2011 08:59:00 -0000 Message-ID: Subject: Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns From: Kai Tietz To: Richard Guenther Cc: Kai Tietz , gcc-patches@gcc.gnu.org Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org X-SW-Source: 2011-07/txt/msg00128.txt.bz2 2011/7/1 Kai Tietz : > 2011/7/1 Kai Tietz : >> 2011/7/1 Richard Guenther : >>> On Fri, Jul 1, 2011 at 1:44 PM, Kai Tietz wrote: >>>> Ok, here is reworked patch with adjusted testcase. >>>> >>>> ChangeLog gcc/ >>>> >>>> 2011-07-01 =A0Kai Tietz =A0 >>>> >>>> =A0 =A0 =A0 =A0* tree-ssa-forwprop.c (truth_valued_ssa): New function. >>>> =A0 =A0 =A0 =A0(detect_not_expr_operand): New function. >>>> =A0 =A0 =A0 =A0(simplify_bitwise_binary_1): New function. >>>> =A0 =A0 =A0 =A0(simplify_bitwise_binary): Use simplify_bitwise_binary_= 1. >>>> >>>> ChangeLog gcc/ >>>> >>>> 2011-07-01 =A0Kai Tietz =A0 >>>> >>>> =A0 =A0 =A0 =A0* gcc.dg/binop-notand1a.c: New test. >>>> =A0 =A0 =A0 =A0* gcc.dg/binop-notand2a.c: New test. >>>> =A0 =A0 =A0 =A0* gcc.dg/binop-notand3a.c: New test. >>>> =A0 =A0 =A0 =A0* gcc.dg/binop-notand4a.c: New test. >>>> =A0 =A0 =A0 =A0* gcc.dg/binop-notand5a.c: New test. >>>> =A0 =A0 =A0 =A0* gcc.dg/binop-notand6a.c: New test. >>>> =A0 =A0 =A0 =A0* gcc.dg/binop-notor1.c: New test. >>>> =A0 =A0 =A0 =A0* gcc.dg/binop-notor2.c: New test. >>>> =A0 =A0 =A0 =A0* gcc.dg/binop-notxor1.c: New test. >>>> =A0 =A0 =A0 =A0* gcc.dg/binop-notxor2.c: New test. >>>> >>>> >>>> Bootstrapped and regression tested for all standard languages plus Ada= and Obj-C++ for x86_64-pc-linux-gnu. =A0Ok for apply? >>> >>> (please post patches inline) >>> >>> +/* Checks if expression has type of one-bit precision, or is a known >>> + =A0 truth-value pression. =A0*/ >>> +static bool >>> +truth_valued_ssa_name (tree name) >>> >>> The function comment should refer to each parameter in capital letters. >>> The comment is also odd, if you consider the function name. =A0Better >>> would be "Return true if the SSA name NAME is of truth-value. =A0" >> >> Ok >> >>> + =A0/* Don't check here for BOOLEAN_TYPE as the precision isn't >>> + =A0 =A0 necessarily one and so ~X is not equal to !X. =A0*/ >>> + =A0if (TYPE_PRECISION (type) =3D=3D 1) >>> + =A0 =A0return true; >>> >>> Technically correct, but did you run into actual problems without this? >> Yes, this makes issues. =A0See BIT_NOT_EXPR in fold-const. =A0It uses LH= S type >> for ~0. =A0[*] >> >>> +/* Helper routine for simplify_bitwise_binary_1 function. >>> + =A0 If a NOT-expression is found, the operand of the NOT-expression is >>> + =A0 returned. =A0Othewise NULL_TREE is returned. >>> + =A0 Detected not-patterns are !X or X =3D=3D 0 for X with integral ty= pe, and >>> + =A0 X ^ 1 or ~X for X with integral type with precision of one. >>> + =A0 The value of CNT_CASTS is either zero, or one. =A0 */ >>> +static tree >>> +detect_not_expr_operand (tree name) >>> >>> What's a NOT-expression? =A0I'd suggest >>> >>> /* For the SSA name NAME return an expression X so that >>> =A0 NAME =3D !X. =A0If there is no such X, return NULL_TREE. =A0*/ >>> >>> Then a better name for the function would be lookup_inverted_value. >> Hmm, we don't look up inverted values in general. May >> lookup_inverted_truth_value? >> >>> + =A0def =3D SSA_NAME_DEF_STMT (name); >>> + =A0if (!def || !is_gimple_assign (def)) >>> + =A0 =A0return NULL_TREE; >>> + >>> >>> def is never NULL. >> Ok >> >>> + =A0code =3D gimple_assign_rhs_code (def); >>> + =A0op1 =3D gimple_assign_rhs1 (def); >>> + =A0op2 =3D NULL_TREE; >>> + >>> + =A0/* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand. >>> + =A0 =A0 If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, TRUTH_NOT_EXPR, >>> + =A0 =A0 or BIT_NOT_EXPR, then return. =A0*/ >>> + =A0if (code =3D=3D EQ_EXPR || code =3D=3D BIT_XOR_EXPR) >>> + =A0 =A0op2 =3D gimple_assign_rhs2 (def); >>> + >>> + =A0switch (code) >>> + =A0 =A0{ >>> + =A0 =A0case TRUTH_NOT_EXPR: >>> + =A0 =A0 =A0return op1; >>> + =A0 =A0case BIT_NOT_EXPR: >>> + =A0 =A0 =A0if (truth_valued_ssa_name (name)) >>> >>> op1, not name >> >> No, name is right. see [*] >> >>> + =A0 =A0 =A0 return op1; >>> + =A0 =A0 =A0break; >>> + =A0 =A0case EQ_EXPR: >>> + =A0 =A0 =A0/* Check if we have X =3D=3D 0 and X has an integral type.= =A0*/ >>> + =A0 =A0 =A0if (!INTEGRAL_TYPE_P (TREE_TYPE (op1))) >>> + =A0 =A0 =A0 break; >>> >>> I think you want this test generally, before the switch. >> No, no need for this. Just for comparisons I need to check that >> operands are equal. The type of NAME >> is always an integral value. >> >>> + =A0 =A0 =A0if (integer_zerop (op2)) >>> + =A0 =A0 =A0 return op1; >>> + =A0 =A0 =A0else if (integer_zerop (op1)) >>> + =A0 =A0 =A0 return op2; >>> >>> It's always op2 that is 0, no need to test op1. >> So for comparison constant will be moved always right-hand? =A0Ok fine b= y this. >> >>> What about NE_EXPR? >> Maybe for X !=3D 1 for an truth-valued X. But I never saw this pattern >> generated. All other cases related to NE_EXPR, which might be an >> inverted variant aren't trivial and not sure if it is worth checking >> them here. >> Eg. (X | Y) !=3D 0 -> (X !=3D 0 | Y !=3D 0) would be the inverted varian= t of >> (X =3D=3D 0 && Y =3D=3D 0). But those things might be better placed in >> and/or_comparison folding in gimple-fold.c, isn't it? >> >>> If you allow EQ/NE_EXPRs then what this function returns is >>> not something for which NAME =3D !X holds but something >>> for which NAME =3D X =3D=3D 0 holds. =A0Otherwise you have to >>> make sure op1 is a truth value. >> !X is (for integral types) X =3D=3D (type-x) 0. And this transformation = is >> bijective AFAICS. I don't see the point you mean here. >> >>> There is also EQ/NE_EXPR with op2 =3D=3D 1, which at least >>> for truth-valued op1 can be handled as well. >> >> See comment above. It is true that X !=3D 1 (for truth-valued X) is X = =3D=3D >> 0. This might be a special case worth to add, but for X !=3D 0 (for >> truth-valued X) it isn't. Same as for X =3D=3D 1 cases. We want to return >> the argument of the not expression here. So we would need to return >> for those cases !X. >> >>> + =A0 =A0 =A0break; >>> + =A0 =A0case BIT_XOR_EXPR: >>> + =A0 =A0 =A0/* Check if we have X ^ 1 and X is truth valued. =A0*/ >>> + =A0 =A0 =A0if (integer_onep (op2) && truth_valued_ssa_name (op1)) >>> + =A0 =A0 =A0 return op1; >>> + =A0 =A0 =A0break; >>> + =A0 =A0default: >>> + =A0 =A0 =A0break; >>> + =A0 =A0} >>> >>> + =A0/* First check if operands ARG1 and ARG2 are equal, if so we >>> + =A0 =A0 won't have a NOT-pattern match. =A0Fold these patterns, as >>> + =A0 =A0 we have detected it already. =A0*/ >>> + =A0if (operand_equal_p (arg1, arg2, 0)) >>> + =A0 =A0{ >>> + =A0 =A0 =A0/* X & X -> X, and X | X -> X. =A0*/ >>> + =A0 =A0 =A0if (code =3D=3D BIT_AND_EXPR || code =3D=3D BIT_IOR_EXPR) >>> + =A0 =A0 =A0 =A0return arg1; >>> + =A0 =A0 =A0/* X ^ X -> 0. =A0*/ >>> + =A0 =A0 =A0return integer_zero_node; >>> + =A0 =A0} >>> >>> gimple_fold catches this already, no reason to do that here. >> Ok >> >>> + =A0/* Do we have case not(X) op not(X)? =A0*/ >>> + =A0if (a1not && a2not) >>> + =A0 =A0{ >>> >>> CSE would have handled this, so no reason to check this - you've >>> done this with the previous operand_equal_p test already. >> No I didn't. =A0As this will match cases like (X ^ 1) & !X (for >> truth-valued X). We compare here the operand of the not-expression. >> >>> + =A0/* Get for each operation operand its optional by one integral typ= ed >>> + =A0 =A0 cast stripped argument. And get the not-expression's operand,= if >>> + =A0 =A0 argument represents an not-expression. =A0*/ >>> + =A0a1not =3D detect_not_expr_operand (arg1); >>> + =A0a2not =3D detect_not_expr_operand (arg2); >>> + >>> + =A0/* If there are no not-expressions found, =A0return NULL_TREE. */ >>> + =A0if (!a1not && !a2not) >>> + =A0 =A0return NULL_TREE; >>> >>> ... >>> >>> + =A0if (a2not) >>> + =A0 =A0{ >>> + =A0 =A0 =A0/* X equal to Y for X op not(Y) =A0*/ >>> + =A0 =A0 =A0if (operand_equal_p (arg1, a2not, 0)) >>> + =A0 =A0 =A0 =A0op =3D arg1; >>> + =A0 =A0} >>> >>> don't need a1not yet >>> >>> So I suggest to rewrite this to sth like >>> >>> a1not =3D detect_not_expr_operand (arg1); >>> if (a1not >>> =A0 =A0&& operand_equal_p (a1not, arg2, 0)) >>> =A0op =3D arg2; >>> else if ((a2not =3D detect_not_expr_operand (arg2)) >>> =A0 =A0 =A0 =A0 =A0 && operand_equal_p (arg1, a2not, 0)) >>> =A0op =3D arg1; >>> else >>> =A0 return NULL_TREE; >>> >>> ... >>> >>> as that is cheaper. =A0The ???s below are probably not worth handling. >>> >>> Richard. >>> >>>> Regards, >>>> Kai >>>> >>> >> >> Regards, >> Kai >> > > To be more correct here about the use of the LHS for ~ X instead of > using X. If I check X for truth-valued, I would match also things like > ~(X =3D=3D 0). But type of the comparison isn't necessarily bool, So I > would match for code like 'int foo (int c) { return c & ~(c =3D=3D 0); }' > and would fold it to zero. But it has for c with value zero the value > 0, and for c with value not zero the result c. Sorry, yesterday wasn't my day. Of course I meant sample 'int foo c) { return c & ~ (c !=3D 0); }'. Its result for c !=3D 0 is (c & 0xfffffffe), and for c =3D=3D 0 it is 0. Kai