From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 20981 invoked by alias); 19 May 2011 13:51:32 -0000 Received: (qmail 20971 invoked by uid 22791); 19 May 2011 13:51:30 -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,TW_TM 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; Thu, 19 May 2011 13:51:15 +0000 Received: by qyk35 with SMTP id 35so3464970qyk.20 for ; Thu, 19 May 2011 06:51:14 -0700 (PDT) MIME-Version: 1.0 Received: by 10.229.51.214 with SMTP id e22mr2378588qcg.156.1305813074414; Thu, 19 May 2011 06:51:14 -0700 (PDT) Received: by 10.229.33.209 with HTTP; Thu, 19 May 2011 06:51:14 -0700 (PDT) In-Reply-To: References: Date: Thu, 19 May 2011 17:23:00 -0000 Message-ID: Subject: Re: [patch tree-ssa-reassoc.c]: Better reassoication for comparision and boolean-logic From: Kai Tietz To: Richard Guenther Cc: GCC Patches 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-05/txt/msg01392.txt.bz2 2011/5/19 Richard Guenther : > On Thu, May 19, 2011 at 3:36 PM, Kai Tietz wrot= e: >> 2011/5/19 Richard Guenther : >>> On Thu, May 19, 2011 at 3:30 PM, Kai Tietz wr= ote: >>>> 2011/5/19 Richard Guenther : >>>>> On Thu, May 19, 2011 at 3:08 PM, Kai Tietz = wrote: >>>>>> 2011/5/19 Richard Guenther : >>>>>>> On Thu, May 19, 2011 at 2:59 PM, Kai Tietz wrote: >>>>>>>> 2011/5/19 Richard Guenther : >>>>>>>>> On Thu, May 19, 2011 at 2:48 PM, Kai Tietz wrote: >>>>>>>>>> Hello, >>>>>>>>>> >>>>>>>>>> This patch improves reassociation folding for comparision. It ex= pands >>>>>>>>>> expressions within binary-AND/OR expression like (X | Y) =3D=3D = 0 to (X =3D=3D >>>>>>>>>> 0 && Y =3D=3D 0) >>>>>>>>>> and (X | Y) !=3D 0 to (X !=3D 0 || Y !=3D 0). =A0This is necessa= ry to allow >>>>>>>>>> better reassociation >>>>>>>>>> on weak pre-folded logical expressions. =A0This unfolding gets u= ndone >>>>>>>>>> anyway later by pass, >>>>>>>>>> so no disadvantage gets introduced. >>>>>>>>>> Also while going through BB-list, it tries to do some little >>>>>>>>>> type-sinking for SSA sequences >>>>>>>>>> like "D1 =3D (type) bool1; D2 =3D (type) bool2; D3 =3D D1 & D2;'= to 'D1 =3D >>>>>>>>>> bool1 & bool2; D2 =3D (type) D1;'. >>>>>>>>>> This folding has the advantage to see better through intermediate >>>>>>>>>> results with none-boolean type. >>>>>>>>>> The function eliminate_redundant_comparison () got reworded so, = that >>>>>>>>>> doesn't break in all cases. >>>>>>>>>> It now continues to find duplicates and tries to find inverse va= riant >>>>>>>>>> (folded to constant). By this >>>>>>>>>> change we don't combine possible weak optimizations too fast, be= fore >>>>>>>>>> we can find and handle >>>>>>>>>> inverse or duplicates. >>>>>>>>> >>>>>>>>> sinking casting belongs not here but instead to tree-ssa-forwprop. >>>>>>>>> I'm not sure that a !=3D 0 | b !=3D 0 is the better canonical var= iant than >>>>>>>>> a | b !=3D 0 though. >>>>>>>>> >>>>>>>>> is_boolean_compatible_type_p looks like a strange remanent. >>>>>>>>> >>>>>>>>> Richard. >>>>>>>> >>>>>>>> Well, a | b !=3D 0 is for sure more optimal, but for reassociation= we >>>>>>>> need to see the unfolded variant temporary. This is necessary as >>>>>>>> fold-const can't see through SSA statements. =A0But this kind of >>>>>>>> expansion should be reversed then by pass to the form (a | b) !=3D= 0 >>>>>>>> back. >>>>>>> >>>>>>> ? =A0fold-const shouldn't deal with this at all as we are in gimple= and in >>>>>>> SSA form. =A0Surely re-association comes to play only with chains of >>>>>>> the above with more than two operands. >>>>>>> >>>>>>> Richard. >>>>>>> >>>>>>>> >>>>>>>> Regards, >>>>>>>> Kai >>>>>>>> >>>>>>> >>>>>> >>>>>> The issue you can see by testcase binop_tor4.c, as here are the >>>>>> intermediate variables d and e (with int type) are destroying the >>>>>> reassociation pass. This testcase for example needs this sinking. >>>>> >>>>> hoisting would work equally well >>>> >>>> Well, but just if then all operands in combined BIT_AND/OR block are >>>> getting hoisting. And well, there might be still some cases where we >>>> wouldn't find the equivalent. As hoisting leads to following >>>> sequences, eg: >>>> >>>> D1 =3D a !=3D 0; >>>> D2 =3D b !=3D 0; >>>> D3 =3D a =3D=3D 0; >>>> D4 =3D b =3D=3D 0; >>>> D5 =3D (long) D1 >>>> D6 =3D (long) D2 >>>> D7 =3D (long) D3 >>>> D8 =3D (long) D4 >>>> D9 =3D D5 & D6; >>>> D10 =3D D8 & D9 >>>> D11 =3D D9 & D10; >>>> >>>> which means that comparision folding will never will happen as the >>>> statement passed to fold algorithm is a cast to a comparison and not >>>> the comparison itself. =A0So sinking looks more sane IMHO. >>> >>> The above is what you do. >> >> No, I don't do this. Please see function sink_cast_and_expand function i= n patch. >> >> =A0if (gimple_assign_cast_p (s1) >> =A0 =A0 =A0&& gimple_assign_cast_p (s2) >> =A0 =A0 =A0&& is_boolean_compatible_type_p (TREE_TYPE (gimple_assign_rhs= 1 (s1))) >> =A0 =A0 =A0&& is_boolean_compatible_type_p (TREE_TYPE (gimple_assign_rhs= 1 (s2))) >> =A0 =A0 =A0&& useless_type_conversion_p (TREE_TYPE (gimple_assign_rhs1 (= s1)), >> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0T= REE_TYPE (gimple_assign_rhs1 (s2)))) >> =A0 =A0{ >> =A0 =A0 =A0gimple_stmt_iterator gsi; >> =A0 =A0 =A0gimple sum; >> =A0 =A0 =A0tree op1a, op1b, tmpvar; >> >> =A0 =A0 =A0tmpvar =3D create_tmp_reg (TREE_TYPE (gimple_assign_rhs1 (s1)= ), NULL); >> >> =A0 =A0 =A0add_referenced_var (tmpvar); >> =A0 =A0 =A0sum =3D build_and_add_sum (tmpvar, gimple_assign_rhs1 (s1), >> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 gimple_assig= n_rhs1 (s2), code); >> =A0 =A0 =A0op1 =3D gimple_get_lhs (sum); >> =A0 =A0 =A0op1 =3D fold_convert (type, op1); >> >> =A0 =A0 =A0op1a =3D gimple_assign_rhs1 (stmt); >> =A0 =A0 =A0op1b =3D gimple_assign_rhs2 (stmt); >> =A0 =A0 =A0gsi =3D gsi_for_stmt (stmt); >> =A0 =A0 =A0gimple_assign_set_rhs_from_tree (&gsi, op1); >> =A0 =A0 =A0update_stmt (stmt); >> =A0 =A0 =A0remove_visited_stmt_chain (op1a); >> =A0 =A0 =A0remove_visited_stmt_chain (op1b); >> =A0 =A0 =A0ret =3D true; >> =A0 =A0} >> >> The none-boolean cast get moved outer, not inner. > > You said =A0(X | Y) !=3D 0 to (X !=3D 0 || Y !=3D 0). =A0I would simply m= ove everything > down, including the cast (that's already done by tree-ssa-forwprop.c). Yes, here I do also already sinking. See build_expand_ne_eq_cmp function (which is called by sink_cast_and_expand () - tree is here unrolled recursively. if (is_boolean_compatible_type_p (type)) op1 =3D fold_build2 ((code =3D=3D NE_EXPR ? BIT_IOR_EXPR : BIT_AND_EXPR= ), type, op1a, op1b); else { gimple sum; tree tmpvar =3D create_tmp_reg (boolean_type_node, NULL); add_referenced_var (tmpvar); sum =3D build_and_add_sum (tmpvar, op1a, op1b, (code =3D=3D NE_EXPR ? BIT_IOR_EXPR : BIT_AND_EXPR)); op1 =3D gimple_get_lhs (sum); op1 =3D fold_convert (type, op1); } For internal expansions of (A | B | C) !=3D to the series of A!=3D0 & B !=3D 0 & C !=3D 0 will done only on boolean_type_node type. There is no recast. Just on final expansion it gets recasted. So yes, the way is to move everything down as far as possible. I don't see your point here that I wouldn't "simply move everything down" by this patch. If I wouldn't the testcases would fail. Regards, Kai