About applyPatternsAndFoldGreedily

I have a question about the usage of the api applyPatternsAndFoldGreedily. Unable to understand the working of this api. Under what use-cases, this api is being used?

snippet code is given below.

OwningRewritePatternList patterns(&getContext());
patterns.insert<FuncOpTypeConversion, ConstantOpQuantizationAndConversion, 
                    GemmOpConversion, AddOpConversion,  MatMulOpConversion, ReluOpConversion, SigmoidOpConversion>(&getContext());
(void)applyPatternsAndFoldGreedily(moduleOp, std::move(patterns));  

In the above process, each pattern’s matchAndRewrite functions are called repeatedly and exit.

Great if anyone can elaborate on the usage of the above api applyPatternsAndFoldGreedily.


This is exactly what it does, there is nothing more. It’ll actually repeatedly try to do so as long as patterns are matching successfully. It’ll stop when nothing can be matched anymore (or after a limited number of iterations to avoid infinite loops…).

This is in particular what is driving the canonicalize pass.

Is this fully true? I believe it also does region simplification. This has caught me before.

/// This class allows control over how the GreedyPatternRewriteDriver works.
class GreedyRewriteConfig {
  /// This specifies the order of initial traversal that populates the rewriters
  /// worklist.  When set to true, it walks the operations top-down, which is
  /// generally more efficient in compile time.  When set to false, its initial
  /// traversal of the region tree is bottom up on each block, which may match
  /// larger patterns when given an ambiguous pattern set.
  bool useTopDownTraversal = false;

  // Perform control flow optimizations to the region tree after applying all
  // patterns.
  bool enableRegionSimplification = true;

  /// This specifies the maximum number of times the rewriter will iterate
  /// between applying patterns and simplifying regions. Use `kNoIterationLimit`
  /// to disable this iteration limit.
  int64_t maxIterations = 10;

  static constexpr int64_t kNoIterationLimit = -1;

Sure, and folding as well :slight_smile:

@mehdi_amini Thanks for the response guys.

My another question in the main topic is “Under what use-cases, this api is being used?”… Is this api is used when the there is a transformation with in the same dialect? i.e source and target dialects are same.??

And another question is in what order, the pattern’s matchAndRewrite function will be called? Is the order of patterns classes in patterns.insert function matters??


There is no restrictions on the dialect involved, it can be used for any pattern application that does not require the features provided by dialect conversion.

And another question is in what order, the pattern’s matchAndRewrite function will be called? Is the order of patterns classes in patterns.insert function matters??

The intent is that the order shouldn’t matter, it is an iterative algorithm and it’ll visit operation multiple times. Right now the config can specify top-down/bottom-order for the initial pass, but it has a worklist internally which will revisit in various order depending on the IR mutations.
On a given operation, the patterns have a “benefit” field that control the order in which they are considered.

@mehdi_amini Thanks for the response.
Still I am not clear about the order of the pattern traversal.
In the specific code snippet I shared, the pattern class FuncOpTypeConversion is always called first, irrespective whether i placed it first or middle or last, how algorithm will decide to call this pattern first? Do it initially transverses the entire pattern classes and mark these in order of call ??

The algorithm traverses the IR first, not the list of patterns. It’ll likely apply FuncOpTypeConversion first because it visited the FuncOp first and nothing else.

1 Like

The code is reasonably readable by the way:

You should also try to use the -debug command line option (you have to build with assert enabled) to see a trace of application.

1 Like