This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: A case where PHI-OPT pessimizes the code


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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]