This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: A case where PHI-OPT pessimizes the code
- From: Richard Guenther <richard dot guenther at gmail dot com>
- To: Steven Bosscher <stevenb dot gcc at gmail dot com>
- Cc: GCC Mailing List <gcc at gcc dot gnu dot org>, Richard Guenther <rguenther at suse dot de>, Alan Modra <amodra at gmail dot com>
- Date: Mon, 23 Apr 2012 14:27:35 +0200
- Subject: Re: A case where PHI-OPT pessimizes the code
- References: <CABu31nNyBhnWHyA1y2r8G8G--QjO2vd_=2Cb1=WqFKr8VpX0xQ@mail.gmail.com>
On Mon, Apr 23, 2012 at 2:15 PM, Steven Bosscher <stevenb.gcc@gmail.com> 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) <default: <L13>, case 0 ... 5: <L15>, case 19 ...
> 23: <L15>, case 26 ... 27: <L15>>
>
> ?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;
>
> <bb 2>:
> ?D.2013_3 = *a_2(D);
> ?D.2019_5 = D.2013_3 > 27;
> ?if (D.2019_5 != 0)
> ? ?goto <bb 3> (<L13>);
> ?else
> ? ?goto <bb 5>;
>
> <bb 5>:
> ?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 <bb 4> (<L15>);
> ?else
> ? ?goto <bb 6>;
>
> <bb 6>:
>
> <L13>:
>
> ?# D.2014_1 = PHI <1(5), 0(3)>
> <L15>:
> ?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;
>
> <bb 2>:
> ?D.2013_3 = *a_2(D);
> ?if (D.2013_3 > 27)
> ? ?goto <bb 4> (<L15>);
> ?else
> ? ?goto <bb 3>;
>
> <bb 3>:
> ?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 <D.2026_5(3), 0(2)> // modified PHI node
> <L15>:
> ?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 <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.