[Bug tree-optimization/102814] [12 regression] quadratique/exponential time complexity for max-jump-thread-duplication-stmts

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

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

--- Comment #1 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
(In reply to Dmitry G. Dyachenko from comment #0)
> r12-4256 FAST
> r12-4444 SLOW
> 
> g++ -fpreprocessed -std=c++98 -O2 --param
> max-jump-thread-duplication-stmts=NNN -c x.ii

Well, you are basically eliding the fail safe we put in specifically for this
code explosion:

  /* Threading through an empty latch would cause code to be added to
     the latch.  This could alter the loop form sufficiently to cause
     loop optimizations to fail.  Disable these threads until after
     loop optimizations have run.  */
  if ((threaded_through_latch
       || (taken_edge && taken_edge->dest == loop->latch))
      && !(cfun->curr_properties & PROP_loop_opts_done)
      && empty_block_p (loop->latch))
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
        fprintf (dump_file,
                 "  FAIL: Thread through latch before loop opts would create
non-empty latch\n");
      return false;

The default is 15, and you're pushing it to > 180.  Nothing good can come of
that.

That being said, in this very specific case, thread3 is creating some monster
PHIs which then thread4 further explodes.  Luckily this combination is
disallowed by the pending threading restrictions in the presence of loops here:

https://gcc.gnu.org/pipermail/gcc-patches/2021-October/581894.html

But really, bad things can happen when you disable the fail-safe mechanisms
we've put in place.

Question to the larger audience... do we support bug reports against internal
--param constructs?