[Bug tree-optimization/94779] Bad optimization of simple switch

[gabravier at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94779

--- Comment #5 from Gabriel Ravier <gabravier at gmail dot com> ---
Going to take a quick look at how it gets optimized in the tree passes.

This is the first case :

int f1(unsigned x)
{
    if (x >= 2)
        __builtin_unreachable();

    switch (x)
    {
        case 0:
            return 1;
        case 1:
            return 2;
    }
}

This is the case which properly compiles down to `return x + 1;`, and should be
equivalent to the other code.

The ssa tree pass ends up, early in optimization, combining some expressions
into `# _1 = PHI <_4(5), _3(6)>`
Then, phiopt1 optimizes it to `_3 = x_2(D) + 1;`, at which point the
optimization we're talking about has been made

This is the second case : 

int f1(unsigned x)
{
    switch (x)
    {
        case 0:
            return 1;
        case 1:
            return 2;
    }
}

The ssa tree pass still combines some expressions into `# _1 = PHI <1(2),
2(3)>`
However, phiopt1 doesn't optimize into `x + 1`.

For me, this seems to be because in the first case, the tree is then this : 

f1 (unsigned int x)
{
  int _1;

  <bb 2> :
  if (x_2(D) > 1)
    goto <bb 3>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 3> :
  __builtin_unreachable ();

  <bb 4> :
  if (x_2(D) == 1)
    goto <bb 5>; [INV]
  else
    goto <bb 6>; [INV]

  <bb 5> :
<L3>:

  <bb 6> :
  # _1 = PHI <1(4), 2(5)>
<L6>:
  return _1;

}

And in the second case, it is instead this : 

f1 (unsigned int x)
{
  int _1;

  <bb 2> :
  switch (x_2(D)) <default: <L2> [INV], case 0: <L4> [INV], case 1: <L1> [INV]>

  <bb 3> :
<L1>:
  goto <bb 5>; [INV]

  <bb 4> :
<L2>:
  __builtin_unreachable ();

  <bb 5> :
  # _1 = PHI <1(2), 2(3)>
<L4>:
  return _1;

}

I believe phiopt1 is unable to optimize the PHI into `x + 1` in the second case
because the `switch` hasn't been optimized away into an if yet
It eventually gets optimized by switchlower1
phiopt4 is then, again, unable to optimize the PHI into `x + 1`. The tree is
then as such : 

f1 (unsigned int x)
{
  int _1;

  <bb 2> [local count: 1073741824]:
  if (x_2(D) == 0)
    goto <bb 5>; [65.00%]
  else
    goto <bb 3>; [35.00%]

  <bb 3> [local count: 1073741824]:
  if (x_2(D) == 1)
    goto <bb 5>; [100.00%]
  else
    goto <bb 4>; [0.00%]

  <bb 4> [count: 0]:
<L2>:
  __builtin_unreachable ();

  <bb 5> [local count: 1073741824]:
  # _1 = PHI <2(3), 1(2)>
<L4>:
  return _1;

}

And then there are no further tree passes that look like they should be
relevant to this

Assuming my analysis is correct (though considering I have little to no
experience with gcc's tree system, there is a pretty big chance that my
analysis is completely wrong), I believe that to solve this, there are two
possibilities : 
- Either there is a missing tree pass that would make phiopt4 capable of
optimizing the PHI into `x_2(D) + 1`
- Or there should there be some extra code added to phiopt4 to recognise the
idiom in this case