http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56113
--- Comment #23 from Steven Bosscher <steven at gcc dot gnu.org> 2013-01-31 22:51:36 UTC --- (In reply to comment #19) > Created attachment 29317 [details] > kill dominator queries from domwalk > > This patch kills dominator queries from domwalk, removing a quadratic > bottleneck > I introduced there. Do so by sorting DOM children after DFS completion > numbers. > > Which hopefully results in equivalent operation ;) Part of the "equivalent operation" can be achieved by walking the maximum extended basic block in DFS order first, and the remaining dominator sons second. It's too late now to try and draft a proof, but I think that with such a visiting order, you always visit all predecessors of the dominator sons that are not successor blocks in the CFG. This is trivially true for diamond regions and loops, and my intuition says it is true in general to be proven by induction...
