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
32enum class GreedySimplifyRegionLevel {
33 /// Disable region control-flow simplification.
34 Disabled,
35 /// Run the normal simplification (e.g. dead args elimination).
36 Normal,
37 /// Run extra simplificiations (e.g. block merging), these can be
38 /// more costly or have some tradeoffs associated.
39 Aggressive
40};
41
42/// This class allows control over how the GreedyPatternRewriteDriver works.
43class GreedyRewriteConfig {
44public:
45 /// This specifies the order of initial traversal that populates the rewriters
46 /// worklist. When set to true, it walks the operations top-down, which is
47 /// generally more efficient in compile time. When set to false, its initial
48 /// traversal of the region tree is bottom up on each block, which may match
49 /// larger patterns when given an ambiguous pattern set.
50 ///
51 /// Note: Only applicable when simplifying entire regions.
52 bool getUseTopDownTraversal() const { return useTopDownTraversal; }
53 GreedyRewriteConfig &setUseTopDownTraversal(bool use = true) {
54 useTopDownTraversal = use;
55 return *this;
56 }
57
58 /// Perform control flow optimizations to the region tree after applying all
59 /// patterns.
60 ///
61 /// Note: Only applicable when simplifying entire regions.
62 GreedySimplifyRegionLevel getRegionSimplificationLevel() const {
63 return regionSimplificationLevel;
64 }
65 GreedyRewriteConfig &
66 setRegionSimplificationLevel(GreedySimplifyRegionLevel level) {
67 regionSimplificationLevel = level;
68 return *this;
69 }
70
71 /// This specifies the maximum number of times the rewriter will iterate
72 /// between applying patterns and simplifying regions. Use `kNoLimit` to
73 /// disable this iteration limit.
74 ///
75 /// Note: Only applicable when simplifying entire regions.
76 int64_t getMaxIterations() const { return maxIterations; }
77 GreedyRewriteConfig &setMaxIterations(int64_t iterations) {
78 maxIterations = iterations;
79 return *this;
80 }
81
82 /// This specifies the maximum number of rewrites within an iteration. Use
83 /// `kNoLimit` to disable this limit.
84 int64_t getMaxNumRewrites() const { return maxNumRewrites; }
85 GreedyRewriteConfig &setMaxNumRewrites(int64_t limit) {
86 maxNumRewrites = limit;
87 return *this;
88 }
89
90 static constexpr int64_t kNoLimit = -1;
91
92 /// Only ops within the scope are added to the worklist. If no scope is
93 /// specified, the closest enclosing region around the initial list of ops
94 /// (or the specified region, depending on which greedy rewrite entry point
95 /// is used) is used as a scope.
96 Region *getScope() const { return scope; }
97 GreedyRewriteConfig &setScope(Region *scope) {
98 this->scope = scope;
99 return *this;
100 }
101
102 /// Strict mode can restrict the ops that are added to the worklist during
103 /// the rewrite.
104 ///
105 /// * GreedyRewriteStrictness::AnyOp: No ops are excluded.
106 /// * GreedyRewriteStrictness::ExistingAndNewOps: Only pre-existing ops (that
107 /// were on the worklist at the very beginning) and newly created ops are
108 /// enqueued. All other ops are excluded.
109 /// * GreedyRewriteStrictness::ExistingOps: Only pre-existing ops (that were
110 /// were on the worklist at the very beginning) enqueued. All other ops are
111 /// excluded.
112 GreedyRewriteStrictness getStrictness() const { return strictness; }
113 GreedyRewriteConfig &setStrictness(GreedyRewriteStrictness mode) {
114 strictness = mode;
115 return *this;
116 }
117
118 /// An optional listener that should be notified about IR modifications.
119 RewriterBase::Listener *getListener() const { return listener; }
120 GreedyRewriteConfig &setListener(RewriterBase::Listener *listener) {
121 this->listener = listener;
122 return *this;
123 }
124
125 /// Whether this should fold while greedily rewriting.
126 bool isFoldingEnabled() const { return fold; }
127 GreedyRewriteConfig &enableFolding(bool enable = true) {
128 fold = enable;
129 return *this;
130 }
131
132 /// If set to "true", constants are CSE'd (even across multiple regions that
133 /// are in a parent-ancestor relationship).
134 bool isConstantCSEEnabled() const { return cseConstants; }
135 GreedyRewriteConfig &enableConstantCSE(bool enable = true) {
136 cseConstants = enable;
137 return *this;
138 }
139
140private:
141 Region *scope = nullptr;
142 bool useTopDownTraversal = false;
143 GreedySimplifyRegionLevel regionSimplificationLevel =
144 GreedySimplifyRegionLevel::Aggressive;
145 int64_t maxIterations = 10;
146 int64_t maxNumRewrites = kNoLimit;
147 GreedyRewriteStrictness strictness = GreedyRewriteStrictness::AnyOp;
148 RewriterBase::Listener *listener = nullptr;
149 bool fold = true;
150 bool cseConstants = true;
151};
152
153//===----------------------------------------------------------------------===//
154// applyPatternsGreedily
155//===----------------------------------------------------------------------===//
156
157/// Rewrite ops in the given region, which must be isolated from above, by
158/// repeatedly applying the highest benefit patterns in a greedy worklist
159/// driven manner until a fixpoint is reached.
160///
161/// The greedy rewrite may prematurely stop after a maximum number of
162/// iterations, which can be configured in the configuration parameter.
163///
164/// Also performs simple dead-code elimination before attempting to match any of
165/// the provided patterns.
166///
167/// A region scope can be set in the configuration parameter. By default, the
168/// scope is set to the specified region. Only in-scope ops are added to the
169/// worklist and only in-scope ops are allowed to be modified by the patterns.
170///
171/// Returns "success" if the iterative process converged (i.e., fixpoint was
172/// reached) and no more patterns can be matched within the region. `changed`
173/// is set to "true" if the IR was modified at all.
174///
175/// Note: This method does not apply patterns to the region's parent operation.
176LogicalResult
177applyPatternsGreedily(Region &region, const FrozenRewritePatternSet &patterns,
178 GreedyRewriteConfig config = GreedyRewriteConfig(),
179 bool *changed = nullptr);
180/// Same as `applyPatternsAndGreedily` above with folding.
181/// FIXME: Remove this once transition to above is completed.
182LLVM_DEPRECATED("Use applyPatternsGreedily() instead", "applyPatternsGreedily")
183inline LogicalResult
184applyPatternsAndFoldGreedily(Region &region,
185 const FrozenRewritePatternSet &patterns,
186 GreedyRewriteConfig config = GreedyRewriteConfig(),
187 bool *changed = nullptr) {
188 config.enableFolding();
189 return applyPatternsGreedily(region, patterns, config, changed);
190}
191
192/// Rewrite ops nested under the given operation, which must be isolated from
193/// above, by repeatedly applying the highest benefit patterns in a greedy
194/// worklist driven manner until a fixpoint is reached.
195///
196/// The greedy rewrite may prematurely stop after a maximum number of
197/// iterations, which can be configured in the configuration parameter.
198///
199/// Also performs simple dead-code elimination before attempting to match any of
200/// the provided patterns.
201///
202/// This overload runs a separate greedy rewrite for each region of the
203/// specified op. A region scope can be set in the configuration parameter. By
204/// default, the scope is set to the region of the current greedy rewrite. Only
205/// in-scope ops are added to the worklist and only in-scope ops and the
206/// specified op itself are allowed to be modified by the patterns.
207///
208/// Note: The specified op may be modified, but it may not be removed by the
209/// patterns.
210///
211/// Returns "success" if the iterative process converged (i.e., fixpoint was
212/// reached) and no more patterns can be matched within the region. `changed`
213/// is set to "true" if the IR was modified at all.
214///
215/// Note: This method does not apply patterns to the given operation itself.
216inline LogicalResult
217applyPatternsGreedily(Operation *op, const FrozenRewritePatternSet &patterns,
218 GreedyRewriteConfig config = GreedyRewriteConfig(),
219 bool *changed = nullptr) {
220 bool anyRegionChanged = false;
221 bool failed = false;
222 for (Region &region : op->getRegions()) {
223 bool regionChanged;
224 failed |= applyPatternsGreedily(region, patterns, config, changed: &regionChanged)
225 .failed();
226 anyRegionChanged |= regionChanged;
227 }
228 if (changed)
229 *changed = anyRegionChanged;
230 return failure(IsFailure: failed);
231}
232/// Same as `applyPatternsGreedily` above with folding.
233/// FIXME: Remove this once transition to above is complieted.
234LLVM_DEPRECATED("Use applyPatternsGreedily() instead", "applyPatternsGreedily")
235inline LogicalResult
236applyPatternsAndFoldGreedily(Operation *op,
237 const FrozenRewritePatternSet &patterns,
238 GreedyRewriteConfig config = GreedyRewriteConfig(),
239 bool *changed = nullptr) {
240 config.enableFolding();
241 return applyPatternsGreedily(op, patterns, config, changed);
242}
243
244/// Rewrite the specified ops by repeatedly applying the highest benefit
245/// patterns in a greedy worklist driven manner until a fixpoint is reached.
246///
247/// The greedy rewrite may prematurely stop after a maximum number of
248/// iterations, which can be configured in the configuration parameter.
249///
250/// Also performs simple dead-code elimination before attempting to match any of
251/// the provided patterns.
252///
253/// Newly created ops and other pre-existing ops that use results of rewritten
254/// ops or supply operands to such ops are also processed, unless such ops are
255/// excluded via `config.strictMode`. Any other ops remain unmodified (i.e.,
256/// regardless of `strictMode`).
257///
258/// In addition to strictness, a region scope can be specified. Only ops within
259/// the scope are simplified. This is similar to `applyPatternsGreedily`,
260/// where only ops within the given region/op are simplified by default. If no
261/// scope is specified, it is assumed to be the first common enclosing region of
262/// the given ops.
263///
264/// Note that ops in `ops` could be erased as result of folding, becoming dead,
265/// or via pattern rewrites. If more far reaching simplification is desired,
266/// `applyPatternsGreedily` should be used.
267///
268/// Returns "success" if the iterative process converged (i.e., fixpoint was
269/// reached) and no more patterns can be matched. `changed` is set to "true" if
270/// the IR was modified at all. `allOpsErased` is set to "true" if all ops in
271/// `ops` were erased.
272LogicalResult
273applyOpPatternsGreedily(ArrayRef<Operation *> ops,
274 const FrozenRewritePatternSet &patterns,
275 GreedyRewriteConfig config = GreedyRewriteConfig(),
276 bool *changed = nullptr, bool *allErased = nullptr);
277/// Same as `applyOpPatternsGreedily` with folding.
278/// FIXME: Remove this once transition to above is complieted.
279LLVM_DEPRECATED("Use applyOpPatternsGreedily() instead",
280 "applyOpPatternsGreedily")
281inline LogicalResult
282applyOpPatternsAndFold(ArrayRef<Operation *> ops,
283 const FrozenRewritePatternSet &patterns,
284 GreedyRewriteConfig config = GreedyRewriteConfig(),
285 bool *changed = nullptr, bool *allErased = nullptr) {
286 config.enableFolding();
287 return applyOpPatternsGreedily(ops, patterns, config, changed, allErased);
288}
289
290} // namespace mlir
291
292#endif // MLIR_TRANSFORMS_GREEDYPATTERNREWRITEDRIVER_H_
293

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