Re: A case where PHI-OPT pessimizes the code

[Richard Guenther <richard.guenther@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.