From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 10367 invoked by alias); 23 Apr 2012 15:14:40 -0000 Received: (qmail 10356 invoked by uid 22791); 23 Apr 2012 15:14:39 -0000 X-SWARE-Spam-Status: No, hits=-7.2 required=5.0 tests=AWL,BAYES_00,KHOP_RCVD_UNTRUST,KHOP_THREADED,RCVD_IN_DNSWL_HI,RCVD_IN_HOSTKARMA_W,SPF_HELO_PASS,TW_BG,TW_LW,TW_PL,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 23 Apr 2012 15:14:21 +0000 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id q3NFEKK9028501 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Mon, 23 Apr 2012 11:14:20 -0400 Received: from stumpy.slc.redhat.com (ovpn-113-130.phx2.redhat.com [10.3.113.130]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id q3NFEJMH012373; Mon, 23 Apr 2012 11:14:19 -0400 Message-ID: <4F9571CB.4040806@redhat.com> Date: Mon, 23 Apr 2012 15:14:00 -0000 From: Jeff Law User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:10.0.1) Gecko/20120216 Thunderbird/10.0.1 MIME-Version: 1.0 To: Richard Guenther CC: Steven Bosscher , GCC Mailing List , Richard Guenther , Alan Modra Subject: Re: A case where PHI-OPT pessimizes the code References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-IsSubscribed: yes Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org X-SW-Source: 2012-04/txt/msg00788.txt.bz2 On 04/23/2012 06:27 AM, Richard Guenther wrote: > On Mon, Apr 23, 2012 at 2:15 PM, Steven Bosscher wrote: >> 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) >> { >> switch (*a) >> { >> case 0: case 1: case 2: case 3: case 4: case 5: >> case 19: case 20: case 21: case 22: case 23: >> case 26: case 27: >> return 1; >> default: >> return 0; >> } >> } >> >> >> After transforming the switch() to a series of bit tests, the code >> looks like this: >> >> >> ;; Function foo (foo, funcdef_no=0, decl_uid=1996, cgraph_uid=0) >> >> beginning to process the following SWITCH statement (pr45830.c:8) : ------- >> switch (D.2013_3), case 0 ... 5:, case 19 ... >> 23:, case 26 ... 27:> >> >> expanding as bit test is preferableSwitch converted >> -------------------------------- >> foo (int * a) >> { >> _Bool D.2023; >> long unsigned int D.2022; >> long unsigned int D.2021; >> long unsigned int csui.1; >> _Bool D.2019; >> int D.2014; >> int D.2013; >> >> : >> D.2013_3 = *a_2(D); >> D.2019_5 = D.2013_3> 27; >> if (D.2019_5 != 0) >> goto (); >> else >> goto; >> >> : >> D.2021_7 = (long unsigned int) D.2013_3; >> csui.1_4 = 1<< D.2021_7; >> D.2022_8 = csui.1_4& 217579583; >> D.2023_9 = D.2022_8 != 0; >> if (D.2023_9 != 0) >> goto (); >> else >> goto; >> >> : >> >> : >> >> # D.2014_1 = PHI<1(5), 0(3)> >> : >> return 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=0, decl_uid=1996, cgraph_uid=0) >> >> Removing basic block 4 >> foo (int * a) >> { >> int D.2026; >> _Bool D.2025; >> long unsigned int D.2022; >> long unsigned int D.2021; >> long unsigned int csui.1; >> int D.2014; >> int D.2013; >> >> : >> D.2013_3 = *a_2(D); >> if (D.2013_3> 27) >> goto (); >> else >> goto; >> >> : >> D.2021_7 = (long unsigned int) D.2013_3; >> csui.1_4 = 1<< D.2021_7; >> D.2022_8 = csui.1_4& 217579583; >> D.2025_9 = D.2022_8 != 0; >> D.2026_5 = (int) D.2025_9; // new statement >> >> # D.2014_1 = PHI // modified PHI node >> : >> return D.2014_1; >> >> } >> >> >> This results in worse code on powerpc64: >> >> BEFORE AFTER >> foo: foo: >> lwz 9,0(3) lwz 9,0(3) >> cmplwi 7,9,27 | cmpwi 7,9,27 >> bgt 7,.L4 | bgt 7,.L3 >> li 8,1 | li 3,1 >> lis 10,0xcf8 lis 10,0xcf8 >> sld 9,8,9 | sld 9,3,9 >> ori 10,10,63 ori 10,10,63 >> and. 8,9,10 and. 8,9,10 >> li 3,1 | mfcr 10 >> bnelr 0 | rlwinm 10,10,3,1 >> .L4: | xori 3,10,1 >> > blr >> > .p2align 4,,15 >> > .L3: >> li 3,0 li 3,0 >> blr 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=(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 = PHI<0 (bb1), 1 (bb0), ...>; > > to > > bb0: > x' = cond; > goto bb2; > bb2: > x = PHI; > > 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)) FWIW, there's a patch buried in a BZ where phi-opt is extended to eliminate PHIs using casts, arithmetic, etc. I never followed up on it because my tests showed that it wasn't a win. It might be possible to retask those bits to improve this code. jeff ps. It was related to missing a conditional move in a loop, so a search for missing cmov or something like that might find the bug. Alternately it was probably attached to the 4.7/4.6 pendinging patches tracker bug.