This is an archive of the discontinued LLVM Phabricator instance.

[Dominators] Rewrite the dominator implementation for efficiency. NFC.
ClosedPublic

Authored by lattner on May 30 2021, 6:02 PM.

Details

Summary

The previous impl densely scanned the entire region starting with an op
when dominators were created, creating a DominatorTree for every region.

This is extremely expensive up front -- particularly for clients like
Linalg/Transforms/Fusion.cpp that construct DominanceInfo for a single
query. It is also extremely memory wasteful for IRs that use single
block regions commonly (e.g. affine.for) because it's making a
dominator tree for a region that has trivial dominance. The
implementation also had numerous unnecessary minor efficiencies, e.g.
doing multiple walks of the region tree or tryGetBlocksInSameRegion
building a DenseMap that it didn't need.

This patch switches to an approach where [Post]DominanceInfo is free
to construct, and which lazily constructs DominatorTree's for any
multiblock regions that it needs. This avoids the up-front cost
entirely, making its runtime proportional to the complexity of the
region tree instead of # ops in a region. This also avoids the memory
and time cost of creating DominatorTree's for single block regions.

Finally this rewrites the implementation for simplicity and to avoids
the constant factor problems the old implementation had.

Diff Detail

Event Timeline

lattner created this revision.May 30 2021, 6:02 PM
lattner requested review of this revision.May 30 2021, 6:02 PM

Adding a few others who have touched this code.

I'll be able to review this tomorrow, but a few really minor things I noticed.

mlir/include/mlir/IR/Region.h
68

return llvm::hasSingleElement(blocks); will do exactly the same thing.

mlir/lib/IR/Dominance.cpp
76

But a Block is always contained in an op unless it's not linked into the IR tree - should the comment be updated or I'm missing something?

mlir/lib/Transforms/CSE.cpp
216

Nit: You've added a redundant emptiness check with this NFC change FWIW.

Thanks! This is another thing that's been lingering for a while to be cleaned up. Took a cursory glance and generally seems alright, most comments are stylistic. Will look again when I get back to the office if some else hasn't approved by then.

mlir/include/mlir/IR/Dominance.h
46

nit: Can you please remove all of the double space after periods? It doesn't match the rest of the comment style and leads to a weird cognitive mismatch.

82
88
97

Any reason not to use PointerIntPair here?

128
164

Can you document this method?

mlir/include/mlir/IR/Region.h
68

We generally use llvm::hasSingleElement instead of adding methods like this.

mlir/lib/IR/Dominance.cpp
63–64

style nit: If one branch has braces, all branches should have braces.

134
294
mlir/lib/Transforms/BufferOptimizations.cpp
198

nit: I'd prefer not to have comments at the end of lines. It doesn't match the style anywhere else here.

mlir/include/mlir/IR/Dominance.h
109–110

Is "Memoize something that is complex to compute" a common pattern that should be factored out?

139

need trailing tick for a?

mlir/lib/IR/Dominance.cpp
47

Seems like an extra comment about how this code is using the fact that multi-block regions are not allowed in Graph Regions to optimize the fast path and avoid the RegionKind query would be good. I think the logic here isn't really obvious.

209

Change in style? should be a and be with ticks?

238

comment style for a and b?

285

missing a close tick

lattner marked 19 inline comments as done.Jun 1 2021, 10:00 AM

thanks for all the feedback, incorporated!

mlir/include/mlir/IR/Dominance.h
46

I'll make an effort, but can make no promises.

This is pretty nit'y, we're not at all consistent on this, even in the mlir codebase:

fgrep -r '. ' mlir/include | wc -l ===> 354 instances

97

Not anymore. That makes things simpler in fact, changed.

109–110

I'm open to suggestions, but that is a very general concept and there are many ways to do it. I don't think it's one general thing.

139

nice catch thx

164

Sure, copied from the .cpp file.

mlir/include/mlir/IR/Region.h
68

I don't want to pull STLExtras.h into Region.h. We shouldn't add dependencies to core IR headers like this particularly, when it is just a one liner.

mlir/lib/IR/Dominance.cpp
47

good point, done. Switching to returning PointerIntPair also allows early exits which makes it easier to read the logic.

76

You're missing something - this is returning the _block_ it is contained in, not the op it is contained in. The top level block (the body of the mlir::ModuleOp) has no enclosing Block, even though it has an enclosing Op (the ModuleOp)

mlir/lib/Transforms/BufferOptimizations.cpp
198

fixed

mlir/lib/Transforms/CSE.cpp
216

That's true. This microoptimization isn't important and is likely picked up by the compiler. Readability is more important here IMO.

lattner updated this revision to Diff 349001.Jun 1 2021, 10:00 AM
lattner marked 9 inline comments as done.

Incorporate feedback from review.

lattner accepted this revision.Jun 1 2021, 2:49 PM

This got a lot of valuable feedback already, I'm going to land this to hill climb on top of it (e.g. https://reviews.llvm.org/D103373). I value any other input of course!

This revision is now accepted and ready to land.Jun 1 2021, 2:49 PM