DOM doesn't walk dominator sons in useful order to fixup complete unrolling. Especially diamond CFG patters are walked in random order instead of first visiting preds of the merge block.
Created attachment 20248 [details] testcase -O3 -funroll-loops -fno-tree-vrp (VRP messes up loop structure)
Created attachment 20249 [details] patch
Mine.
Other issue. DOM doesn't track non-executable BBs. Same testcase, see how if (D.1574_205 > D.1636_208) goto <bb 22>; else goto <bb 23>; <bb 22>: iftmp.5_209 = iftmp.5_206 + 1; <bb 23>: # iftmp.5_210 = PHI <iftmp.5_206(21), iftmp.5_209(22)> the condition is folded but iftmp.5_210 is not found to be constant (optimize_stmt asks for find_taken_edge but nothing tracks edge executability, which also could save compile-time. record_equivalences_from_phis would need to ignore values from non-executable edges)
In your patch you need to sbitmap_allocate (last_basic_block) (instead of n_basic_blocks).
Created attachment 20395 [details] fixed patch The testcase doesn't reproduce the problem w/o the patch anymore.
Subject: Bug 43571 Author: rguenth Date: Thu May 6 09:08:57 2010 New Revision: 159100 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=159100 Log: 2010-05-06 Richard Guenther <rguenther@suse.de> PR tree-optimization/43571 * domwalk.c (walk_dominator_tree): Walk the dominator sons in more optimal order. Modified: trunk/gcc/ChangeLog trunk/gcc/domwalk.c
Fixed.