A case where PHI-OPT pessimizes the code

A case where PHI-OPT pessimizes the code

[Steven Bosscher]

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.

Re: A case where PHI-OPT pessimizes the code

[Richard Guenther]

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.

Re: A case where PHI-OPT pessimizes the code

[Steven Bosscher]

On Mon, Apr 23, 2012 at 2:27 PM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> int foo (_Bool b)
> {
>  if (b)
>    return 1;
>  else
>    return 0;
> }

Indeed PHI-OPT performs the transformation on this code, too. But the
resulting code on powerpc64 is fine:

[stevenb@gcc1-power7 gcc]$ cat t.c.149t.optimized

;; Function foo (foo, funcdef_no=0, decl_uid=1996, cgraph_uid=0)

foo (_Bool b)
{
  int D.2006;

<bb 2>:
  D.2006_4 = (int) b_2(D);
  return D.2006_4;

}


[stevenb@gcc1-power7 gcc]$ cat t.s
        .file   "t.c"
        .section        ".toc","aw"
        .section        ".text"
        .align 2
        .p2align 4,,15
        .globl foo
        .section        ".opd","aw"
        .align 3
foo:
        .quad   .L.foo,.TOC.@tocbase,0
        .previous
        .type   foo, @function
.L.foo:
        blr
        .long 0
        .byte 0,0,0,0,0,0,0,0
        .size   foo,.-.L.foo
        .ident  "GCC: (GNU) 4.8.0 20120418 (experimental) [trunk
revision 186580]"
[stevenb@gcc1-power7 gcc]$


However, this C test case shows the problem:

[stevenb@gcc1-power7 gcc]$ head -n 24 t.c
#define ONEUL (1UL)

int
foo (long unsigned int a)
{
  _Bool b;
  long unsigned int cst, csui;

  if (a > 27) goto return_zero;
/*cst = 217579583UL;*/
  cst = (ONEUL <<  0) | (ONEUL <<  1) | (ONEUL <<  2) | (ONEUL <<  3)
| (ONEUL <<  4) |
        (ONEUL <<  5) | (ONEUL << 19) | (ONEUL << 20) | (ONEUL << 21)
| (ONEUL << 22) |
        (ONEUL << 23) | (ONEUL << 26) | (ONEUL << 27);
  csui = (ONEUL << a);
  b = ((csui & cst) != 0);
  if (b)
    return 1;
  else
    return 0;

return_zero:
   return 0;
}

[stevenb@gcc1-power7 gcc]$ ./cc1 -quiet -O2 -fdump-tree-all t.c
[stevenb@gcc1-power7 gcc]$ cat t.s
        .file   "t.c"
        .section        ".toc","aw"
        .section        ".text"
        .align 2
        .p2align 4,,15
        .globl foo
        .section        ".opd","aw"
        .align 3
foo:
        .quad   .L.foo,.TOC.@tocbase,0
        .previous
        .type   foo, @function
.L.foo:
        cmpldi 7,3,27
        bgt 7,.L3
        li 10,1
        lis 9,0xcf8
        sld 3,10,3
        ori 9,9,63
        and. 10,3,9
        mfcr 9
        rlwinm 9,9,3,1
        xori 3,9,1
        blr
        .p2align 4,,15
.L3:
.L2:
        li 3,0
        blr
        .long 0
        .byte 0,0,0,0,0,0,0,0
        .size   foo,.-.L.foo
        .ident  "GCC: (GNU) 4.8.0 20120418 (experimental) [trunk
revision 186580]"


I will file a PR for this later today, maybe after trying on a few
other targets to see if this is a middle-end problem or a target
issue.

Ciao!
Steven

Re: A case where PHI-OPT pessimizes the code

[Alan Modra]

On Mon, Apr 23, 2012 at 02:50:13PM +0200, Steven Bosscher wrote:
>   csui = (ONEUL << a);
>   b = ((csui & cst) != 0);
>   if (b)
>     return 1;
>   else
>     return 0;

We (powerpc) would be much better if this were

   csui = (ONEUL << a);
   return (csui & cst) >> a;

Other targets would probably benefit too.

-- 
Alan Modra
Australia Development Lab, IBM

Re: A case where PHI-OPT pessimizes the code

[Steven Bosscher]

On Mon, Apr 23, 2012 at 4:43 PM, Alan Modra <amodra@gmail.com> wrote:
> On Mon, Apr 23, 2012 at 02:50:13PM +0200, Steven Bosscher wrote:
>>   csui = (ONEUL << a);
>>   b = ((csui & cst) != 0);
>>   if (b)
>>     return 1;
>>   else
>>     return 0;
>
> We (powerpc) would be much better if this were
>
>   csui = (ONEUL << a);
>   return (csui & cst) >> a;
>
> Other targets would probably benefit too.

Yes, this has been discussed before. See here:

  http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01791.html
  http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html

However, like Roger, I would prefer to not implement this right now. I
only want to port the code from stmt.c to GIMPLE, at least initially.
Later on, we could look at different code generation approaches for
this kind of switch() statement.

Ciao!
Steven

Re: A case where PHI-OPT pessimizes the code

[Alan Modra]

On Mon, Apr 23, 2012 at 06:07:52PM +0200, Steven Bosscher wrote:
> On Mon, Apr 23, 2012 at 4:43 PM, Alan Modra <amodra@gmail.com> wrote:
> > On Mon, Apr 23, 2012 at 02:50:13PM +0200, Steven Bosscher wrote:
> >>   csui = (ONEUL << a);
> >>   b = ((csui & cst) != 0);
> >>   if (b)
> >>     return 1;
> >>   else
> >>     return 0;
> >
> > We (powerpc) would be much better if this were
> >
> >   csui = (ONEUL << a);
> >   return (csui & cst) >> a;
> >
> > Other targets would probably benefit too.
> 
> Yes, this has been discussed before. See here:
> 
>   http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01791.html
>   http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html

I'm suggesting something slightly different to either of these.  I
realize it's probably not that easy to implement, and is really
outside the scope of the switch statement code you're working on, but
it would be nice if we could avoid the comparison.  On high end
powerpc machines, int -> cc -> int costs the equivalent of many
operations just on int.

(In the powerpc code you showed, the comparison is folded into the
AND, emitted as "and.", the move from cc is "mfcr; rlwinm; xori".
"and." isn't cheap and "mfcr" is relatively expensive.)

-- 
Alan Modra
Australia Development Lab, IBM

Re: A case where PHI-OPT pessimizes the code

[Steven Bosscher]

On Mon, Apr 23, 2012 at 2:50 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> I will file a PR for this later today, maybe after trying on a few
> other targets to see if this is a middle-end problem or a target
> issue.

This is now PR target/53087 (http://gcc.gnu.org/PR53087).

Actually the poor code looks to be coming from the &-operation, not
from the _Bool->int conversion. But I don't know enough powerpc-speak
to be sure...

Ciao!
Steven

Re: A case where PHI-OPT pessimizes the code

[Jeff Law]

On 04/23/2012 06:27 AM, Richard Guenther wrote:
> 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))
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.