Fix iteration counting in greedy pattern application

[frgossen]

Summary

Previously, checking that a fix point is reached was counted as a full
iteration. As this "iteration" never changes the IR, this seems counter-
intuitive.

[mehdi_amini]

mlir/lib/Transforms/Utils/GreedyPatternRewriteDriver.cpp

277

I don't quite get the change, if config.maxIterations was set to 1 for example, I would expect that we iterate once in the loop. When we get to this check ++iteration < 1 will be false and we'll exit the loop. With your change we may go through another iteration right?

[frgossen]

mlir/lib/Transforms/Utils/GreedyPatternRewriteDriver.cpp

277

Yes, with this change, we might go through the loop twice if maxIterations is set to 1.
However, the last iteration is merely a check to have reached a fix point and it is never changing the IR if this succeeds.
As a user, I would never think of this as an iteration.

For example, I have a pass with patterns that needs exactly one pass over the IR to reach the desired result.
As a user, I would think of this as one iteration, yet, I had to set maxIterations to 2 to account for the fix point check.

[mikeurbach]

Hi @frgossen, I just incorporated this change downstream into CIRCT, and I found it somewhat unintuitive.

Yes, with this change, we might go through the loop twice if maxIterations is set to 1.

We are in exactly this situation in one of our passes, where we use the maxIterations to run exactly one iteration. Our pass has several assertions that become false if more than one iteration is executed. Previously, we set maxIterations = 1, and now we must set maxIterations = 0. I am not sure why you mentioned your pass that processes the IR once required maxIterations = 2 previously. We set maxIterations = 1, and this did what we expected: ran our rewrite patterns once.

Here is the change we had to make in CIRCT: https://github.com/llvm/circt/commit/f0a4b7e48af58810e8e5ba67a9a3a47952579100#diff-159860a66be40b575200052287d986260fd5773a3ccd1b2d9a7ba52fdbf0a884R2560

This CIRCT change seems to indicate the previous behavior here was more intuitive (at least IMHO). Could you share more about your use-case and why the previous behavior is not intuitive? I'm personally in favor of reverting this at the moment.

[frgossen]

Hi Mike,

I understand applyPatternsAndFoldGreedily as a mechanism for transforming the IR in a pattern-based fashion. As such, I found it surprising that maxIterations would count its internal check to have reached a fix point as an iteration.

In my case, I use applyPatternsAndFoldGreedily to transform the IR and I know that I need exatly one iteration to reach the desired IR. Intuitively, I would set maxIterations = 1 but previously I needed to account for the fix point check also, which I would consider an implementation detail.

Correct me if I misunderstand this:
From looking at your code, I suspect that your use of applyPatternsAndFoldGreedily does not change the IR and you use it to make sure that none of the patterns apply. In that sense, you are not applying any of the patterns, meaning the (empty) rewrite succeeds within 0 iterations.

If this is still controversial, I don't mind changing it back but I do find the previous version counter-intuitive.

mlir/lib/Transforms/Utils/GreedyPatternRewriteDriver.cpp

#endif
       changed |= succeeded(matchResult);
     }
 
     // After applying patterns, make sure that the CFG of each of the regions
     // is kept up to date.
     if (config.enableRegionSimplification)
       changed |= succeeded(simplifyRegions(*this, regions));
   } while (changed &&
-           (++iteration < config.maxIterations ||
+           (iteration++ < config.maxIterations ||
             config.maxIterations == GreedyRewriteConfig::kNoIterationLimit));
 
   // Whether the rewrite converges, i.e. wasn't changed in the last iteration.
   return !changed;
 }
 
 void GreedyPatternRewriteDriver::addToWorklist(Operation *op) {
   // Check to see if the worklist already contains this op.