[MLIR][NFC] Speed up is valid symbol check #154924
Conversation
|
@llvm/pr-subscribers-mlir-affine @llvm/pr-subscribers-mlir Author: William Moses (wsmoses) ChangesThis adds an early exit condition, and removes the closure indirection, potentially enabling tail recursion elim, etc. Full diff: https://github.com/llvm/llvm-project/pull/154924.diff 1 Files Affected:
diff --git a/mlir/lib/Dialect/Affine/IR/AffineOps.cpp b/mlir/lib/Dialect/Affine/IR/AffineOps.cpp
index 22608a16cc1ab..53538d9c01428 100644
--- a/mlir/lib/Dialect/Affine/IR/AffineOps.cpp
+++ b/mlir/lib/Dialect/Affine/IR/AffineOps.cpp
@@ -465,10 +465,16 @@ bool mlir::affine::isValidSymbol(Value value, Region *region) {
return true;
// `Pure` operation that whose operands are valid symbolic identifiers.
- if (isPure(defOp) && llvm::all_of(defOp->getOperands(), [&](Value operand) {
- return affine::isValidSymbol(operand, region);
- })) {
- return true;
+ if (isPure(defOp)) {
+ bool allValid = true;
+ for (auto operand : defOp->getOperands()) {
+ if (!affine::isValidSymbol(operand, region)) {
+ allValid = false;
+ break;
+ }
+ }
+ if (allValid)
+ return true;
}
// Dim op results could be valid symbols at any level.
|
Mmmm, how so?
Ditto: I don't see it? |
c772acf to
1953029
Compare
|
okay updated both the PR and comment. In particular, I'm trying to fix things when a single pass takes >2 mins with this profile (not tested this fixes, but is generally good regardless -- and seems likely): 
|
|
In particular I believe the PR in its current form reduces the runtime from O( (# of ancestor regions) * (# of operands + [potentially recursive] isPure cost) ) -> O( (# of ancestor regions) + (# of operands + [potentially recursive] isPure cost) ) |
|
okay confirmed the impact of this diff: |
| } | ||
| } | ||
| if (allValid) | ||
| return true; |
There was a problem hiding this comment.
Can you explain this hunk?
I
There was a problem hiding this comment.
I essentially inlined the llvm:all_of. So specifically it checks each operand if it is valid, and if any is not valid, doesn't return true. In addition to inlining (and thus not capturing/etc), there's an early break if it is known not valid. llvm::all_of forwards to std::all_of, which I don't know if is required to have an early break vs always iterate the entire range.
There was a problem hiding this comment.
which I don't know if is required to have an early break vs always iterate the entire range.
Yeah, well in absence of more evidence, please rollback this change.
There was a problem hiding this comment.
so per https://en.cppreference.com/w/cpp/algorithm/all_any_none_of.html it looks like it's up to the stdc++ implementation. Which means that the existing llvm::all_of does not guarantee to early exit, whereas this does.
There was a problem hiding this comment.
If you believe this is a problem, please send a patch to fix llvm::all_of.
There was a problem hiding this comment.
made like a change from 3m56s on the big code to 3m57s, putting this part back to all_of
|
on our larger test code this also is confirmed to reduce a compile time of 1hr (and counting) to 3 minutes |
Co-authored-by: Mehdi Amini <joker.eph@gmail.com>
This removes the closure indirection, and removes the recursion on isValidSymbol. The rewriting of the recursion is particularly helpful to avoid redundant checks of isPure and checking the isValidSymbol of the operands for each parent region check