[Bug tree-optimization/96563] New: Failure to optimize loop with condition to simple arithmetic

[Bug tree-optimization/96563] New: Failure to optimize loop with condition to simple arithmetic

[gabravier at gmail dot com]

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

            Bug ID: 96563
           Summary: Failure to optimize loop with condition to simple
                    arithmetic
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gabravier at gmail dot com
  Target Milestone: ---

int f(int x)
{
    int i = 0;
    while (i <= 9)
    {
        if (i == x)
            return 8;
        ++i;
    }
    return 4;
}

This can be optimized to `return 4 + ((x <= 9) * 4);`. This transformation is
done by LLVM, but not by GCC.

[Bug tree-optimization/96563] Failure to optimize loop with condition to simple arithmetic

[glisse at gcc dot gnu.org]

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

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2020-08-11
     Ever confirmed|0                           |1
           Severity|normal                      |enhancement
             Status|UNCONFIRMED                 |NEW
           Keywords|                            |missed-optimization

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
At -O2 (before uncprop)

  <bb 2> [local count: 151290756]:

  <bb 3> [local count: 976138698]:
  # i_9 = PHI <0(2), i_4(6)>
  if (x_3(D) == i_9)
    goto <bb 7>; [5.50%]
  else
    goto <bb 4>; [94.50%]

  <bb 4> [local count: 922451069]:
  i_4 = i_9 + 1;
  if (i_4 != 10)
    goto <bb 6>; [89.42%]
  else
    goto <bb 8>; [10.58%]

  <bb 8> [local count: 97603126]:
  goto <bb 5>; [100.00%]

  <bb 6> [local count: 824847943]:
  goto <bb 3>; [100.00%]

  <bb 7> [local count: 53687628]:

  <bb 5> [local count: 151290756]:
  # _2 = PHI <8(7), 4(8)>
  return _2;

We don't really do anything special. At -O3, the loop gets unrolled

  <bb 2> [local count: 151290757]:
  if (x_3(D) == 0)
    goto <bb 14>; [5.50%]
  else
    goto <bb 3>; [94.50%]

  <bb 14> [local count: 8320992]:
  goto <bb 13>; [100.00%]

  <bb 3> [local count: 142969766]:
  if (x_3(D) == 1)
    goto <bb 15>; [5.50%]
  else
    goto <bb 4>; [94.50%]

  <bb 15> [local count: 7863337]:
  goto <bb 13>; [100.00%]

  <bb 4> [local count: 135106428]:
  if (x_3(D) == 2)
    goto <bb 16>; [5.50%]
  else
    goto <bb 5>; [94.50%]

  <bb 16> [local count: 7430853]:
  goto <bb 13>; [100.00%]

  <bb 5> [local count: 127675576]:
  if (x_3(D) == 3)
    goto <bb 17>; [5.50%]
  else
    goto <bb 6>; [94.50%]

  <bb 17> [local count: 7022157]:
  goto <bb 13>; [100.00%]

  <bb 6> [local count: 120653419]:
  if (x_3(D) == 4)
    goto <bb 18>; [5.50%]
  else
    goto <bb 7>; [94.50%]

  <bb 18> [local count: 6635938]:
  goto <bb 13>; [100.00%]

  <bb 7> [local count: 114017483]:
  if (x_3(D) == 5)
    goto <bb 19>; [5.50%]
  else
    goto <bb 8>; [94.50%]

  <bb 19> [local count: 6270962]:
  goto <bb 13>; [100.00%]

  <bb 8> [local count: 107746521]:
  if (x_3(D) == 6)
    goto <bb 20>; [5.50%]
  else
    goto <bb 9>; [94.50%]

  <bb 20> [local count: 5926059]:
  goto <bb 13>; [100.00%]

  <bb 9> [local count: 101820460]:
  if (x_3(D) == 7)
    goto <bb 21>; [5.50%]
  else
    goto <bb 10>; [94.50%]

  <bb 21> [local count: 5600125]:
  goto <bb 13>; [100.00%]

  <bb 10> [local count: 96220334]:
  if (x_3(D) == 8)
    goto <bb 22>; [5.50%]
  else
    goto <bb 11>; [94.50%]

  <bb 22> [local count: 5292118]:
  goto <bb 13>; [100.00%]

  <bb 11> [local count: 90928219]:
  if (x_3(D) == 9)
    goto <bb 23>; [5.50%]
  else
    goto <bb 12>; [94.50%]

  <bb 23> [local count: 5001052]:
  goto <bb 13>; [100.00%]

  <bb 12> [local count: 97603126]:

  <bb 13> [local count: 151290756]:
  # _2 = PHI <8(14), 4(12), 8(22), 8(21), 8(20), 8(19), 8(18), 8(17), 8(16),
8(15), 8(23)>
  return _2;

We have code in reassoc to handle x==0||x==1||x==2 and turn it into a range
test. I suspect the issue is related to those empty bb between the condition
and the PHI that hides the fact that they are jumping to the same place
eventually. Fixing this for the unrolled case is thus probably easiest,
although of course it would be nice if it also worked for 99 instead of 9,
where we are not going to unroll.

[Bug tree-optimization/96563] Failure to optimize loop with condition to simple arithmetic

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2020-08-11 00:00:00         |2021-8-19

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So I looked into this a little bit, clang is able to do it because it "unrolls"
the loop.

The reason why I say that is if you take:
int f(int x, int y)
{
    int i = 0;
    while (i <= y)
    {
        if (i == x)
            return 8;
        ++i;
    }
    return 4;
}

No compiler is able to optimize this at all.
Which should get us: 4 + ((x <= y && x >= 0)*4).

Even changing the original 9 to 1000, clang does not do the optimization ....

>although of course it would be nice if it also worked for 99 instead of 9, where we are not going to unroll.
Yes it would but not even clang/LLVM does that :)

[Bug tree-optimization/96563] Failure to optimize loop with condition to simple arithmetic

[gabravier at gmail dot com]

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

--- Comment #3 from Gabriel Ravier <gabravier at gmail dot com> ---
It seems like GCC does better for the unrolled case as of now on trunk and
seemingly since GCC 11, though the operation is done in a different way due to
`((unsigned)x <= 9) ? 8 : 4;` being expanded differently, which does seem
interesting w.r.t. perhaps optimizing `(((unsigned)x <= 9) * 4) + 4` to it or
the other way around.