This is an archive of the discontinued LLVM Phabricator instance.

Fix iteration counting in greedy pattern application
ClosedPublic

Authored by frgossen on Apr 12 2022, 4:02 PM.

Details

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.

Diff Detail

Event Timeline

frgossen created this revision.Apr 12 2022, 4:02 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 12 2022, 4:02 PM
frgossen requested review of this revision.Apr 12 2022, 4:02 PM
mehdi_amini added inline comments.Apr 12 2022, 9:22 PM
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?

pifon2a accepted this revision.Apr 13 2022, 5:45 AM
This revision is now accepted and ready to land.Apr 13 2022, 5:45 AM
frgossen added inline comments.Apr 13 2022, 7:25 AM
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.

frgossen marked an inline comment as done.Apr 21 2022, 12:13 PM
This revision was landed with ongoing or failed builds.Apr 21 2022, 12:17 PM
This revision was automatically updated to reflect the committed changes.

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.

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.