[mlir][bufferize] Always bufferize top-to-bottom

[springerm]

Summary

This ensures that we generate memref types with matching layout maps. (Especially when using partial bufferization passes.)

[bkramer]

mlir/lib/Dialect/Bufferization/Transforms/Bufferize.cpp

313

You have to pass the config to applyPatternsAndFoldGreedily or it'll just be ignored.

[mehdi_amini]

The commit description seems to indicate that this is a behavior change, is it? Can you expose it in a test?

More importantly what may be concerning is the use of the greedy pattern rewrite with an expectation of order of traversal that would be semantically meaningful.

[springerm]

You have to pass the config to applyPatternsAndFoldGreedily or it'll just be ignored.

My bad, thx for letting me know.

In D120893#3363444, @mehdi_amini wrote:

The commit description seems to indicate that this is a behavior change, is it? Can you expose it in a test?

Actually no change in behavior. Even without config, the traversal happened to be top-to-bottom. But I guess it was not guaranteed. This is just making it explicit.

More importantly what may be concerning is the use of the greedy pattern rewrite with an expectation of order of traversal that would be semantically meaningful.

Can you elaborate a bit? Why is it concerning to specify a traversal order? It looks like the API has been designed with this in mind.

[mehdi_amini]

Can you elaborate a bit? Why is it concerning to specify a traversal order? It looks like the API has been designed with this in mind.

The API is designed to not make it a semantics change. I believe the original intent was motivated by benchmarks showing that one order may produce drastically faster convergence than an other one.
What is important to understand is that the algorithm is iterative and worklist based. The only impact of this flag is how the worklist is "primed", it does not guarantee anything beyond that: the algorithm will update the worklist as it goes (revisiting operands/results somehow after rewriting an operation).

Basically for semantically driven rewrites, DialectConversion has a controlled order of traversal, but isn't greedy / iterative.

[springerm]

In D120893#3363516, @mehdi_amini wrote:

Can you elaborate a bit? Why is it concerning to specify a traversal order? It looks like the API has been designed with this in mind.

The API is designed to not make it a semantics change. I believe the original intent was motivated by benchmarks showing that one order may produce drastically faster convergence than an other one.
What is important to understand is that the algorithm is iterative and worklist based. The only impact of this flag is how the worklist is "primed", it does not guarantee anything beyond that: the algorithm will update the worklist as it goes (revisiting operands/results somehow after rewriting an operation).

Basically for semantically driven rewrites, DialectConversion has a controlled order of traversal, but isn't greedy / iterative.

OK, then we probably want a custom Operation::walk here.

[springerm]

In D120893#3363525, @springerm wrote:

In D120893#3363516, @mehdi_amini wrote:

Can you elaborate a bit? Why is it concerning to specify a traversal order? It looks like the API has been designed with this in mind.

The API is designed to not make it a semantics change. I believe the original intent was motivated by benchmarks showing that one order may produce drastically faster convergence than an other one.
What is important to understand is that the algorithm is iterative and worklist based. The only impact of this flag is how the worklist is "primed", it does not guarantee anything beyond that: the algorithm will update the worklist as it goes (revisiting operands/results somehow after rewriting an operation).

Basically for semantically driven rewrites, DialectConversion has a controlled order of traversal, but isn't greedy / iterative.

OK, then we probably want a custom Operation::walk here.

As a side note, the only reason why "top-to-bottom" traversal is a semantics change is because we are missing canonicalization patterns. The generated code is always correct, regardless of the pattern application order. It's just that some orders generate less efficient code. This could be cleaned up by canonicalization patterns (some of which do not currently exist).

mlir/lib/Dialect/Bufferization/Transforms/Bufferize.cpp

checkBufferizationResult(Operation *op, const BufferizationOptions &options) {
   return success();
 }
 
 LogicalResult bufferization::bufferizeOp(Operation *op,
                                          const BufferizationState &state) {
   // Bufferize the op and its nested ops.
   RewritePatternSet patterns(op->getContext());
   populateBufferizationPattern(state, patterns);
+
+  // Bufferize ops top-to-bottom. When creating a new op, we should ideally
+  // know the exact memref type of all operands. Otherwise, we have to use a
+  // memref type with a fully dynamic layout map, which has to canonicalize
+  // away.
+  // Moreover, if "fullyDynamicLayoutMaps = false", we may otherwise have to
+  // insert buffer copies to fold ("finalize") to_memref(to_tensor(x)) ops with
+  // non-cast-compatible layout maps.
+  GreedyRewriteConfig config;
+  config.useTopDownTraversal = true;
+
   if (failed(applyPatternsAndFoldGreedily(op, std::move(patterns))))
     return failure();
 
   return checkBufferizationResult(op, state.getOptions());
 }
 
 namespace {
 /// This a "no analysis, always copy" BufferizationState. In the absence of an