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

["glisse at gcc dot gnu.org" <gcc-bugzilla@gcc.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.