https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100817
--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> --- Created attachment 50897 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50897&action=edit patch (In reply to Richard Biener from comment #3) > 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. It's measurably worse for regular CFGs (gcc/*.c), just as example: attribs.c.334t.statistics:146 pre "compute_antic iterations == 2" 39 -attribs.c.334t.statistics:146 pre "compute_antic iterations == 3" 27 +attribs.c.334t.statistics:146 pre "compute_antic iterations == 3" 17 +attribs.c.334t.statistics:146 pre "compute_antic iterations == 4" 9 +attribs.c.334t.statistics:146 pre "compute_antic iterations == 5" 1 still only the very first "iteration" technically requires the postorder on the inverted graph iteration order. I've attached the patch I've used for the measurement. The immediate "fix" would be to remove the assert replacing it with a comment refering to this PR. But not sure if action is really required.
