[Bug tree-optimization/51005] -ftree-tail-merge slows down compilation of 20001226-1.c

[vries at gcc dot gnu.org]

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.