[Bug tree-optimization/100817] ICE with -O2: in compute_antic, at tree-ssa-pre.c:2513

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

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
The number of iterations grows linear with loop depth, starting with 6 for

for (; a;)
 for (; a >= 0;)
  for (; a;)
   for (; a; a += 2)
    ;

adding 2 for every

 for (; a;)
  for (; a >= 0;)

added.  The issue is that the postorder on the inverted graph chosen for
iteration is "worst" in how it iterates over the loop nest.  Adding an
exit to the innermost loop makes antic iteration iterate two times independent
on loop depth.  For anti iteration it's important to minimize the number of
blocks that are visited before all sucessors are visited, but here the whole
loop nest is only backwards reachable via backedges but there walking the
nest outer-to-inner producing N such blocks.

Now, doing reverse program order iteration after the initial postorder
traversal would fix this, so I'm going to explore this idea.