[Verifier] Speed up and parallelize dominance checking. NFC
One of the key algorithms used in the "mlir::verify(op)" method is the
dominance checker, which ensures that operand values properly dominate
the operations that use them.
The MLIR dominance implementation has a number of algorithmic problems,
and is not really set up in general to answer dense queries: it's constant
factors are really slow with multiple map lookups and scans, even in the
easy cases. Furthermore, when calling mlir::verify(module) or some other
high level operation, it makes sense to parallelize the dominator
verification of all the functions within the module.
This patch has a few changes to enact this:
1) It splits dominance checking into "IsolatedFromAbove" units. Instead
of building a monolithic DominanceInfo for everything in a module,
for example, it checks dominance for the module to all the functions
within it (noop, since there are no operands at this level) then each
function gets their own DominanceInfo for each of their scope.
2) It adds the ability for mlir::DominanceInfo (and post dom) to be
constrained to an IsolatedFromAbove region. There is no reason to
recurse into IsolatedFromAbove regions since use/def relationships
can't span this region anyway. This is already checked by the time
the verifier gets here.
3) It avoids querying DominanceInfo for trivial checks (e.g. intra Block
references) to eliminate constant factor issues).
4) It switches to lazily constructing DominanceInfo because the trivial
check case handles the vast majority of the cases and avoids
constructing DominanceInfo entirely in some cases (e.g. at the module
level or for many Regions's that contain a single Block).
5) It parallelizes analysis of collections IsolatedFromAbove operations,
e.g. each of the functions within a Module.
All together this is more than a 10% speedup on `firtool` in circt on a
large design when run in -verify-each mode (our default) since the verifier
is invoked after each pass.
Still todo is to parallelize the main verifier pass. I decided to split
this out to its own thing since this patch is already large-ish.
Differential Revision: https://reviews.llvm.org/D103373