[Bug tree-optimization/59967] [4.8/4.9/5 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

["rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
In the size estimation we have

 BB: 46, after_exit: 0
  size:   1 _319 = MEM[(double *)c0_188(D) + 16B];
  size:   1 _321 = i_171 >> 2;
   Constant expression will be folded away.
  size:   2 if (_321 != 0)

so somehow we fail to see that the conditional is constant after peeling.

Reworking things so we can use a lattice (also avoid calling simple_iv
too many times) will improve that (but also the code doesn't then
only consider MAX (taken-paths-lengths) in case there is an else block).
It looks like reworking this to do a domwalk may be profitable.

The simplistic approach gets us from an estimated size after unrolling
of to 238 (still that won't unroll the loop).  I think we should also
consider size->eliminated_by_peeling in the call heuristic - the
call itself might be a minor distraction and especially eliminated
branches might result in a good speed benefit.

That said, the core algorithm for likely-eliminated should be improved,
but it won't help by itself.