[Bug rtl-optimization/59802] excessive compile time in RTL optimizers (loop unswitching, CPROP)

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

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59802

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |steven at gcc dot gnu.org

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to David Binderman from comment #3)
> (In reply to Richard Biener from comment #2)
> > Oh, did you configure with --enable-checking=release for 4.9?  (I did)
> 
> No, I used --enable-checking=yes.

That makes the comparison to 4.8 invalid (uses --enable-checking=release
by default).

Btw, callgrind shows that compile-time is dominated by
bitmap_intersection_of_preds (and bitmap_ior_and_compl),
called from lcm.c:compute_available.  LCM works with
sbitmaps which can be very expensive for large functions.

tree PRE uses regular bitmaps, but it seems that LCM can
end up using the full bitmap via returning bitmap_ones
from bitmap_intersection_of_preds (for a block with no preds).

It seems compute_available doesn't use optimal iteration order
and that explicitely representing the maximum set instead of
handling unvisited preds makes things more expensive (need to
use sbitmaps).

Iterating in inverted postorder gets me

 CPROP                   :   2.13 ( 5%) usr   0.06 (10%) sys   2.20 ( 5%) wall 
  4444 kB ( 2%) ggc

with no changes in generated code ...