[Bug tree-optimization/115828] Inefficient loop termination (should use compare against 0)

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
ivcanon adds the decrementing by one IV as expected:

  <bb 2> [local count: 53687088]:

  <bb 3> [local count: 1020054736]:
  # i_8 = PHI <i_5(5), 36(2)>
  # ivtmp_2 = PHI <ivtmp_1(5), 19(2)>
  v ={v} i_8;
  i_5 = i_8 + -2;
  ivtmp_1 = ivtmp_2 - 1;
  if (ivtmp_1 != 0)
    goto <bb 5>; [94.74%]
  else
    goto <bb 4>; [5.26%]

  <bb 5> [local count: 966367644]:
  goto <bb 3>; [100.00%]

IVOPTs then considers

Candidate 8:
  Incr POS: orig biv
  IV struct:
    Type:       int
    Base:       36
    Step:       -2
    Biv:        N
    Overflowness wrto loop niter:       No-overflow

But it doesn't consider Base 38 and rewrite

  v ={v} i_8;
  i_5 = i_8 + -2;

into

  i_5 = i_8 + -2;
  v ={v} i_5;
  if (i_5 != 0)

IVOPTs considers Base 34 because of the i_5 BIV.

Even with disabling IVCANON we do not consider an IV candidate with an != 0
exit test.  We usually add those for doloop but AVR disables IVOPTs
doloop heuristic.

We might want to add the doloop IV candidate unconditionally (but not mark
it doloop if the target doesn't have doloop).  But discovering a doloop
like candidate for step != -1 (in this case -2) is difficult when ivcanon
rewrote the exit test - the natural place would be to record the candidate
because of the exit test use.  The other possibility would be to add
these candidates during BIV processing and add a BIV variant that decrements
to zero.

Then only costs would have to be in a way that we also select that candidate of
course.