1//===- GreedyPatternRewriteDriver.h - Greedy Pattern Driver -----*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file declares methods for applying a set of patterns greedily, choosing
10// the patterns with the highest local benefit, until a fixed point is reached.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef MLIR_TRANSFORMS_GREEDYPATTERNREWRITEDRIVER_H_
15#define MLIR_TRANSFORMS_GREEDYPATTERNREWRITEDRIVER_H_
16
17#include "mlir/Rewrite/FrozenRewritePatternSet.h"
18
19namespace mlir {
20
21/// This enum controls which ops are put on the worklist during a greedy
22/// pattern rewrite.
23enum class GreedyRewriteStrictness {
24 /// No restrictions wrt. which ops are processed.
25 AnyOp,
26 /// Only pre-existing and newly created ops are processed.
27 ExistingAndNewOps,
28 /// Only pre-existing ops are processed.
29 ExistingOps
30};
31
32/// This class allows control over how the GreedyPatternRewriteDriver works.
33class GreedyRewriteConfig {
34public:
35 /// This specifies the order of initial traversal that populates the rewriters
36 /// worklist. When set to true, it walks the operations top-down, which is
37 /// generally more efficient in compile time. When set to false, its initial
38 /// traversal of the region tree is bottom up on each block, which may match
39 /// larger patterns when given an ambiguous pattern set.
40 ///
41 /// Note: Only applicable when simplifying entire regions.
42 bool useTopDownTraversal = false;
43
44 /// Perform control flow optimizations to the region tree after applying all
45 /// patterns.
46 ///
47 /// Note: Only applicable when simplifying entire regions.
48 bool enableRegionSimplification = true;
49
50 /// This specifies the maximum number of times the rewriter will iterate
51 /// between applying patterns and simplifying regions. Use `kNoLimit` to
52 /// disable this iteration limit.
53 ///
54 /// Note: Only applicable when simplifying entire regions.
55 int64_t maxIterations = 10;
56
57 /// This specifies the maximum number of rewrites within an iteration. Use
58 /// `kNoLimit` to disable this limit.
59 int64_t maxNumRewrites = kNoLimit;
60
61 static constexpr int64_t kNoLimit = -1;
62
63 /// Only ops within the scope are added to the worklist. If no scope is
64 /// specified, the closest enclosing region around the initial list of ops
65 /// (or the specified region, depending on which greedy rewrite entry point
66 /// is used) is used as a scope.
67 Region *scope = nullptr;
68
69 /// Strict mode can restrict the ops that are added to the worklist during
70 /// the rewrite.
71 ///
72 /// * GreedyRewriteStrictness::AnyOp: No ops are excluded.
73 /// * GreedyRewriteStrictness::ExistingAndNewOps: Only pre-existing ops (that
74 /// were on the worklist at the very beginning) and newly created ops are
75 /// enqueued. All other ops are excluded.
76 /// * GreedyRewriteStrictness::ExistingOps: Only pre-existing ops (that were
77 /// were on the worklist at the very beginning) enqueued. All other ops are
78 /// excluded.
79 GreedyRewriteStrictness strictMode = GreedyRewriteStrictness::AnyOp;
80
81 /// An optional listener that should be notified about IR modifications.
82 RewriterBase::Listener *listener = nullptr;
83};
84
85//===----------------------------------------------------------------------===//
86// applyPatternsGreedily
87//===----------------------------------------------------------------------===//
88
89/// Rewrite ops in the given region, which must be isolated from above, by
90/// repeatedly applying the highest benefit patterns in a greedy worklist
91/// driven manner until a fixpoint is reached.
92///
93/// The greedy rewrite may prematurely stop after a maximum number of
94/// iterations, which can be configured in the configuration parameter.
95///
96/// Also performs folding and simple dead-code elimination before attempting to
97/// match any of the provided patterns.
98///
99/// A region scope can be set in the configuration parameter. By default, the
100/// scope is set to the specified region. Only in-scope ops are added to the
101/// worklist and only in-scope ops are allowed to be modified by the patterns.
102///
103/// Returns "success" if the iterative process converged (i.e., fixpoint was
104/// reached) and no more patterns can be matched within the region. `changed`
105/// is set to "true" if the IR was modified at all.
106///
107/// Note: This method does not apply patterns to the region's parent operation.
108LogicalResult
109applyPatternsAndFoldGreedily(Region &region,
110 const FrozenRewritePatternSet &patterns,
111 GreedyRewriteConfig config = GreedyRewriteConfig(),
112 bool *changed = nullptr);
113
114/// Rewrite ops nested under the given operation, which must be isolated from
115/// above, by repeatedly applying the highest benefit patterns in a greedy
116/// worklist driven manner until a fixpoint is reached.
117///
118/// The greedy rewrite may prematurely stop after a maximum number of
119/// iterations, which can be configured in the configuration parameter.
120///
121/// Also performs folding and simple dead-code elimination before attempting to
122/// match any of the provided patterns.
123///
124/// This overload runs a separate greedy rewrite for each region of the
125/// specified op. A region scope can be set in the configuration parameter. By
126/// default, the scope is set to the region of the current greedy rewrite. Only
127/// in-scope ops are added to the worklist and only in-scope ops and the
128/// specified op itself are allowed to be modified by the patterns.
129///
130/// Note: The specified op may be modified, but it may not be removed by the
131/// patterns.
132///
133/// Returns "success" if the iterative process converged (i.e., fixpoint was
134/// reached) and no more patterns can be matched within the region. `changed`
135/// is set to "true" if the IR was modified at all.
136///
137/// Note: This method does not apply patterns to the given operation itself.
138inline LogicalResult
139applyPatternsAndFoldGreedily(Operation *op,
140 const FrozenRewritePatternSet &patterns,
141 GreedyRewriteConfig config = GreedyRewriteConfig(),
142 bool *changed = nullptr) {
143 bool anyRegionChanged = false;
144 bool failed = false;
145 for (Region &region : op->getRegions()) {
146 bool regionChanged;
147 failed |=
148 applyPatternsAndFoldGreedily(region, patterns, config, changed: &regionChanged)
149 .failed();
150 anyRegionChanged |= regionChanged;
151 }
152 if (changed)
153 *changed = anyRegionChanged;
154 return failure(isFailure: failed);
155}
156
157/// Rewrite the specified ops by repeatedly applying the highest benefit
158/// patterns in a greedy worklist driven manner until a fixpoint is reached.
159///
160/// The greedy rewrite may prematurely stop after a maximum number of
161/// iterations, which can be configured in the configuration parameter.
162///
163/// Also performs folding and simple dead-code elimination before attempting to
164/// match any of the provided patterns.
165///
166/// Newly created ops and other pre-existing ops that use results of rewritten
167/// ops or supply operands to such ops are also processed, unless such ops are
168/// excluded via `config.strictMode`. Any other ops remain unmodified (i.e.,
169/// regardless of `strictMode`).
170///
171/// In addition to strictness, a region scope can be specified. Only ops within
172/// the scope are simplified. This is similar to `applyPatternsAndFoldGreedily`,
173/// where only ops within the given region/op are simplified by default. If no
174/// scope is specified, it is assumed to be the first common enclosing region of
175/// the given ops.
176///
177/// Note that ops in `ops` could be erased as result of folding, becoming dead,
178/// or via pattern rewrites. If more far reaching simplification is desired,
179/// `applyPatternsAndFoldGreedily` should be used.
180///
181/// Returns "success" if the iterative process converged (i.e., fixpoint was
182/// reached) and no more patterns can be matched. `changed` is set to "true" if
183/// the IR was modified at all. `allOpsErased` is set to "true" if all ops in
184/// `ops` were erased.
185LogicalResult
186applyOpPatternsAndFold(ArrayRef<Operation *> ops,
187 const FrozenRewritePatternSet &patterns,
188 GreedyRewriteConfig config = GreedyRewriteConfig(),
189 bool *changed = nullptr, bool *allErased = nullptr);
190
191} // namespace mlir
192
193#endif // MLIR_TRANSFORMS_GREEDYPATTERNREWRITEDRIVER_H_
194

source code of mlir/include/mlir/Transforms/GreedyPatternRewriteDriver.h