From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-return-174105-listarch-gcc=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 1518 invoked by alias); 23 Apr 2012 12:27:54 -0000
Received: (qmail 1481 invoked by uid 22791); 23 Apr 2012 12:27:50 -0000
X-SWARE-Spam-Status: No, hits=-4.7 required=5.0	tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,KHOP_RCVD_TRUST,KHOP_THREADED,RCVD_IN_DNSWL_LOW,RCVD_IN_HOSTKARMA_YE,TW_BG,TW_LW,TW_PL
X-Spam-Check-By: sourceware.org
Received: from mail-iy0-f175.google.com (HELO mail-iy0-f175.google.com) (209.85.210.175)    by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 23 Apr 2012 12:27:35 +0000
Received: by iaag37 with SMTP id g37so17885762iaa.20        for <gcc@gcc.gnu.org>; Mon, 23 Apr 2012 05:27:35 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.50.194.133 with SMTP id hw5mr6123435igc.57.1335184055217; Mon, 23 Apr 2012 05:27:35 -0700 (PDT)
Received: by 10.42.228.200 with HTTP; Mon, 23 Apr 2012 05:27:35 -0700 (PDT)
In-Reply-To: <CABu31nNyBhnWHyA1y2r8G8G--QjO2vd_=2Cb1=WqFKr8VpX0xQ@mail.gmail.com>
References: <CABu31nNyBhnWHyA1y2r8G8G--QjO2vd_=2Cb1=WqFKr8VpX0xQ@mail.gmail.com>
Date: Mon, 23 Apr 2012 12:27:00 -0000
Message-ID: <CAFiYyc3ZdJG_F=LeAo5JpUT_S9Ku9wV7db15EP_ZOpapXf1crA@mail.gmail.com>
Subject: Re: A case where PHI-OPT pessimizes the code
From: Richard Guenther <richard.guenther@gmail.com>
To: Steven Bosscher <stevenb.gcc@gmail.com>
Cc: GCC Mailing List <gcc@gcc.gnu.org>, Richard Guenther <rguenther@suse.de>, Alan Modra <amodra@gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-IsSubscribed: yes
Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc/>
List-Post: <mailto:gcc@gcc.gnu.org>
List-Help: <http://gcc.gnu.org/ml/>
Sender: gcc-owner@gcc.gnu.org
X-SW-Source: 2012-04/txt/msg00782.txt.bz2

On Mon, Apr 23, 2012 at 2:15 PM, Steven Bosscher <stevenb.gcc@gmail.com> wr=
ote:
> Hello,
>
> I ported the code to expand switch() statements with bit tests from
> stmt.c to GIMPLE, and looked at the resulting code to verify that the
> transformation applies correctly, when I noticed this strange PHI-OPT
> transformation that results in worse code for the test case of PR45830
> which looks like this:
>
> int
> foo (int *a)
> {
> =A0switch (*a)
> =A0 =A0{
> =A0 =A0case 0: =A0 =A0 case 1: =A0 =A0case 2: =A0 =A0case 3: =A0 =A0case =
4: =A0 =A0case 5:
> =A0 =A0case 19: =A0 =A0case 20: =A0 =A0case 21: =A0 =A0case 22: =A0 =A0ca=
se 23:
> =A0 =A0case 26: =A0 =A0case 27:
> =A0 =A0 =A0return 1;
> =A0 =A0default:
> =A0 =A0 =A0return 0;
> =A0 =A0}
> }
>
>
> After transforming the switch() to a series of bit tests, the code
> looks like this:
>
>
> ;; Function foo (foo, funcdef_no=3D0, decl_uid=3D1996, cgraph_uid=3D0)
>
> beginning to process the following SWITCH statement (pr45830.c:8) : -----=
--
> switch (D.2013_3) <default: <L13>, case 0 ... 5: <L15>, case 19 ...
> 23: <L15>, case 26 ... 27: <L15>>
>
> =A0expanding as bit test is preferableSwitch converted
> --------------------------------
> foo (int * a)
> {
> =A0_Bool D.2023;
> =A0long unsigned int D.2022;
> =A0long unsigned int D.2021;
> =A0long unsigned int csui.1;
> =A0_Bool D.2019;
> =A0int D.2014;
> =A0int D.2013;
>
> <bb 2>:
> =A0D.2013_3 =3D *a_2(D);
> =A0D.2019_5 =3D D.2013_3 > 27;
> =A0if (D.2019_5 !=3D 0)
> =A0 =A0goto <bb 3> (<L13>);
> =A0else
> =A0 =A0goto <bb 5>;
>
> <bb 5>:
> =A0D.2021_7 =3D (long unsigned int) D.2013_3;
> =A0csui.1_4 =3D 1 << D.2021_7;
> =A0D.2022_8 =3D csui.1_4 & 217579583;
> =A0D.2023_9 =3D D.2022_8 !=3D 0;
> =A0if (D.2023_9 !=3D 0)
> =A0 =A0goto <bb 4> (<L15>);
> =A0else
> =A0 =A0goto <bb 6>;
>
> <bb 6>:
>
> <L13>:
>
> =A0# D.2014_1 =3D PHI <1(5), 0(3)>
> <L15>:
> =A0return D.2014_1;
>
> }
>
>
> This is the equivalent code of what the expander in stmt.c would
> generate. Unfortunately, the first PHI-OPT pass (phiopt1) changes the
> code as follows:
>
> ;; Function foo (foo, funcdef_no=3D0, decl_uid=3D1996, cgraph_uid=3D0)
>
> Removing basic block 4
> foo (int * a)
> {
> =A0int D.2026;
> =A0_Bool D.2025;
> =A0long unsigned int D.2022;
> =A0long unsigned int D.2021;
> =A0long unsigned int csui.1;
> =A0int D.2014;
> =A0int D.2013;
>
> <bb 2>:
> =A0D.2013_3 =3D *a_2(D);
> =A0if (D.2013_3 > 27)
> =A0 =A0goto <bb 4> (<L15>);
> =A0else
> =A0 =A0goto <bb 3>;
>
> <bb 3>:
> =A0D.2021_7 =3D (long unsigned int) D.2013_3;
> =A0csui.1_4 =3D 1 << D.2021_7;
> =A0D.2022_8 =3D csui.1_4 & 217579583;
> =A0D.2025_9 =3D D.2022_8 !=3D 0;
> =A0D.2026_5 =3D (int) D.2025_9; =A0// new statement
>
> =A0# D.2014_1 =3D PHI <D.2026_5(3), 0(2)> // modified PHI node
> <L15>:
> =A0return D.2014_1;
>
> }
>
>
> This results in worse code on powerpc64:
>
> BEFORE =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0AFTER
> foo: =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0foo:
> =A0 =A0 =A0 =A0lwz 9,0(3) =A0 =A0 =A0 =A0 =A0 =A0 =A0lwz 9,0(3)
> =A0 =A0 =A0 =A0cmplwi 7,9,27 | =A0 =A0 =A0 =A0 cmpwi 7,9,27
> =A0 =A0 =A0 =A0bgt 7,.L4 =A0 =A0 | =A0 =A0 =A0 =A0 bgt 7,.L3
> =A0 =A0 =A0 =A0li 8,1 =A0 =A0 =A0 =A0| =A0 =A0 =A0 =A0 li 3,1
> =A0 =A0 =A0 =A0lis 10,0xcf8 =A0 =A0 =A0 =A0 =A0 =A0lis 10,0xcf8
> =A0 =A0 =A0 =A0sld 9,8,9 =A0 =A0 | =A0 =A0 =A0 =A0 sld 9,3,9
> =A0 =A0 =A0 =A0ori 10,10,63 =A0 =A0 =A0 =A0 =A0 =A0ori 10,10,63
> =A0 =A0 =A0 =A0and. 8,9,10 =A0 =A0 =A0 =A0 =A0 =A0 and. 8,9,10
> =A0 =A0 =A0 =A0li 3,1 =A0 =A0 =A0 =A0| =A0 =A0 =A0 =A0 mfcr 10
> =A0 =A0 =A0 =A0bnelr 0 =A0 =A0 =A0 | =A0 =A0 =A0 =A0 rlwinm 10,10,3,1
> .L4: =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0| =A0 =A0 =A0 =A0 xori 3,10,1
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0> =A0 =A0 =A0 =A0 blr
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0> =A0 =A0 =A0 =A0 .p2align 4,,=
15
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0> .L3:
> =A0 =A0 =A0 =A0li 3,0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0li 3,0
> =A0 =A0 =A0 =A0blr =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 blr
>
> BEFORE is the code that results if stmt.c expands the switch to bit
> tests (i.e. PHI-OPT never gets to transform the code as shown), and
> AFTER is with my equivalent GIMPLE implementation. Apparently, the
> optimizers are unable to recover from the transformation PHI-OPT
> performs.
>
> I am not sure how to fix this problem. I am somewhat surprised by the
> code generated by the powerpc backend for "t=3D(int)(_Bool)some_bool",
> because I would have expected the type range for _Bool to be <0,1> so
> that the type conversion should be a single bit test. On the other
> hand, maybe PHI-OPT should recognize this pattern and reject the
> transformation???
>
> Your thoughts/comments/suggestions, please?
>
> Ciao!
> Steven
>
>
> P.S. Unfortunately I haven't been able to produce a test case that
> shows the problem without my switch conversion pass.

int foo (_Bool b)
{
  if (b)
    return 1;
  else
    return 0;
}

PHI-OPT tries to do conditional replacement, thus transform

     bb0:
      if (cond) goto bb2; else goto bb1;
     bb1:
     bb2:
      x =3D PHI <0 (bb1), 1 (bb0), ...>;

to

     bb0:
      x' =3D cond;
      goto bb2;
     bb2:
      x =3D PHI <x' (bb0), ...>;

trying to save a compare (assuming the target has a set-cc like instruction=
).

I think the ppc backend should be fixed here (if possible), or the generic
expansion of this kind of pattern needs to improve.  On x86_64 we simply
do

(insn 7 6 8 (set (reg:SI 63 [ D.1715 ])
        (zero_extend:SI (reg/v:QI 61 [ b ]))) t.c:4 -1
     (nil))

Richard.