http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51005
--- Comment #4 from vries at gcc dot gnu.org 2011-11-14 12:05:58 UTC --- Created attachment 25816 --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25816 Patch that also delegates updating the vops, but keeps dominator info up-to-date bootstrapped and reg-tested on x64_64 and i686, build and reg-tested on ARM and MIPS (with an additional verify_dominators after each update). This patch updates dominator info after each cluster application. It does this roughly in the following way: - for a cluster, determine the nearest-common-dominator dom - for the dom, determine the set directly dominated by the dom, called fix_dom_bbs - for each of fix_dom_bbs, determine whether there is a path from dom to it, which does not pass through cluster. If for a member of fix_dom_bb such a path exists, it is still directly dominated by dom. If such a path doesn't exist, it's now dominated by cluster. The patch implement this path search by a walk marking all bbs reachable from dom but not through cluster. This walk is done once for each cluster. For the example, there are 2 clusters of 4096 bbs in 1 iteration. Using this patch, the compilation time for this example is comparable to recalculating the dominator info each iteration from scratch. The time-complexity of this approach per iteration is O(n_clusters * (n_bbs + n_edges)). Best case, this algorithm is faster than recomputing dominator info from scratch each iteration. But worst case, it's slower.
