Continuing our conversation from this weeks ODM, we had an internal meeting today and came up with an algorithm and implementation thoughts which wouldn’t require modifications to the CIRCT optimizations which use the `PatternWriter`

s. I’d like to get confirmation that the algorithm is sound and that it could be implemented the way I think it can be.

### Problem statement

Given code `a`

, its optimized version `A`

, and a patched version of `a`

called `a'`

, generate optimized code for `a'`

(which we’ll call `A'`

) with a minimal number of changes between `A`

and `A'`

, both in terms of netlist and SystemVerilog text. We’re also given a mapping between operations in `a`

and `a'`

for all operations which are present in both (have not changed). We also assume that we can call a given transformation on an operation for only that operation (as we can for the canonicalizers) We further assume a deterministic compiler.

### Algorithm

- Run a given transformation on
`a`

(to produce`A`

). For each transform on each operation, log the operation and the transformation in the order in which they are run. - Iterate through the operations in
`a'`

in the same order as the transform log for`a`

(for all ops which exist in both) and run the optimization (*not*the transformation) on each operation, monitoring the transformation which it does on`a'`

. If*and only if*the same optimization was applied to`a`

, allow it to persist. If the transformation was not applied, roll back the transformation. - Profit.

The idea is to apply as many of the transforms to `a'`

which were applied to `a`

which are still valid to apply. By running the optimizations on `a'`

rather than just blindly applying them, we ensure that they are still valid. By checking that a transformation was applied to `a`

, we ensure that differences between `a`

and `a'`

do not cause non-linear changes to occur.

As a memory optimization step, we can run the steps concurrently.

### Implementation

This algorithm requires two capabilities: transformation observation and rollback.

We can implement the observation component by implementing a `Listener`

and recording the transformations.

I seem to recall (but cannot find at the moment) that there is some transformation rewind / rollback functionality which can be applied if transformations occur through a `PatternRewriter`

.

I think this would work on the canonicalizers as is. Further, I’m pretty sure this could be used on any optimization which uses the dialect conversion framework with the addition of a “use this listener/rollback widget” argument.

@seldridge / @mikeurbach / @mortbopet Do you agree? Am I understanding the MLIR mechanics properly?