From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 12470 invoked by alias); 1 Jul 2011 13:57:32 -0000 Received: (qmail 12461 invoked by uid 22791); 1 Jul 2011 13:57:31 -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-f182.google.com (HELO mail-qy0-f182.google.com) (209.85.216.182) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 01 Jul 2011 13:57:17 +0000 Received: by qyk38 with SMTP id 38so1978565qyk.20 for ; Fri, 01 Jul 2011 06:57:16 -0700 (PDT) MIME-Version: 1.0 Received: by 10.229.88.197 with SMTP id b5mr2560487qcm.226.1309528636191; Fri, 01 Jul 2011 06:57:16 -0700 (PDT) Received: by 10.229.65.225 with HTTP; Fri, 1 Jul 2011 06:57:16 -0700 (PDT) In-Reply-To: References: <2017997593.883643.1309520672925.JavaMail.root@zmail06.collab.prod.int.phx2.redhat.com> Date: Fri, 01 Jul 2011 13:57: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/msg00037.txt.bz2 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 LHS= 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 typ= e, 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 by= 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 variant= 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 typed >> + =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. Regards, Kai