Hello,
this patch implements several improvements to dominance analysis:
1) Return type of get_dominated_by and get_dominated_by_region is
changed to vector, and iterate_fix_dominators takes the list of
basic blocks whose dominator needs to be updated as a vector.
2) recount_dominator is renamed to (hopefully) more correct name
recompute_dominator.
3) The algorithm used by iterate_fix_dominators is changed. The
algorithm we currently use is poorly documented, and it is fairly
nontrivial to show it is correct. Also, in some cases it may iterate
unnecessarily too much (which might be a problem, since
recompute_dominator calls are fairly expensive). For details about
the new algorithm, see the comment in iterate_fix_dominators.
4) Verify_dominators used to check only local correctness of the
dominators, i.e., it would consider any fixpoint of the equations
that define dominators correct, not necessarily only the largest one.
Instead, this patch makes us recompute all dominators, and compare
the results with the existing values.
Bootstrapped & regtested on i686, with verify_dominators calls inserted
at the end of iterate_fix_dominators. Even in this setting, the compile
time appears to be unchanged on the compilation of the preprocessed
gcc sources (iterate_fix_dominators is only used when we cannot update
the dominators in other ways, which is not too common).