The CanonicalizerPass uses the greedy pattern rewriter to apply canonicalization patterns until a fixpoint is reached. However, the pass succeeds even if no fixpoint is reached, as the return value of applyPatternsAndFoldGreedily is ignored.
void CanonicalizerPass::runOnOperation() {
/* ... */
(void)applyPatternsAndFoldGreedily(getOperation(), patterns, config);
}
This means that the IR is not guaranteed to be in canonical form after running the canonicalizer pass. This can be seen as either a bug or a case of incomplete documentation.
Based on a discussion in ⚙ D140482 [mlir] Signal CanonicalizerPass failure due to non-convergence, canonicalization could be considered “best-effort”, in which case the current implementation would be correct.
The problem with the current situation is:
- According to the MLIR docs, users expect that the IR is in canonical form after running
-canonicalize, but this is not necessarily the case. - Users often run canonicalization as a pre-processing pass to enable other transforms/canonicalizations. But this is incorrect, as the canonicalizer may not bring the IR in the canonical form.
-
-canonicalizemay apply some canonicalization patterns while “ignoring” others. Which patterns are applied and which are not (if any) can change if new patterns added or additional dialects are loaded. This is hard to debug. - Faulty canonicalization patterns (e.g., patterns that do not converge) can remain unnoticed. They can start breaking the CanonicalizerPass at any point in a non-predictable way. We currently have faulty patterns in the GPU and OpenACC dialects (that nobody noticed), as indicated by the failed tests of ⚙ D140482 [mlir] Signal CanonicalizerPass failure due to non-convergence. Probably even more in downstream projects. (This is what the docs say about canonicalization patterns:
Repeated applications of patterns should converge. Unstable or cyclic rewrites will cause infinite loops in the canonicalizer.)
Here are two proposals to fix this. (My preferred solution is the first one.)
Proposal 1: Signal pass failure on non-convergence
void CanonicalizerPass::runOnOperation() {
/* ... */
if (failed(applyPatternsAndFoldGreedily(getOperation(), patterns, config)))
signalPassFailure();
}
and do not limit the number of iterations by default (pass option of CanonicalizerPass):
Option<"maxIterations", "max-iterations", "int64_t",
/*default=*/"-1",
"Max. iterations between applying patterns / simplifying regions">,
The downside of this approach is that the CanonicalizerPass may run longer. It is, however, guaranteed to terminate. Otherwise, we must have a bug in a pattern. We can add additional debugging flags to the CanonicalizerPass that help tracking down such bugs (e.g., âš™ D140525 [mlir] Limit number of pattern rewrites in CanonicalizerPass).
Proposal 2: Keep ignoring convergence (NFC) and update documentation + fuzzer flags
Update the MLIR docs (Operation Canonicalization - MLIR) as follows:
MLIR has a single canonicalization pass, which iteratively applies
canonicalization transformations in a greedy way. Canonicalization
is best-effort and not guaranteed to bring the entire IR in a canonical
form. In the worst case, the canonicalizer could be a no-op; every pass
pipeline should work correctly under such an assumption.
Note: If canonicalization is a necessary pre-processing step, it should
be done in a dedicated pass or integrated into the pass that requires
pre-processing. (Ideally with a greedy pattern rewriter that applies only
only the required patterns and applies them to a fixpoint.)
This change would likely mean that many current pass pipelines are incorrect. To help fixing them, we could add a debug flag that replaces the CanonicalizerPass with a no-op. This can be used as a fuzzer.
@mehdi_amini @ftynse @River707 @nicolasvasilache @pifon2a @jpienaar