MLIR  21.0.0git
GreedyPatternRewriteDriver.h
Go to the documentation of this file.
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 
18 
19 namespace mlir {
20 
21 /// This enum controls which ops are put on the worklist during a greedy
22 /// pattern rewrite.
24  /// No restrictions wrt. which ops are processed.
25  AnyOp,
26  /// Only pre-existing and newly created ops are processed.
28  /// Only pre-existing ops are processed.
30 };
31 
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.
40 };
41 
42 /// This class allows control over how the GreedyPatternRewriteDriver works.
44 public:
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; }
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.
63  return regionSimplificationLevel;
64  }
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; }
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; }
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; }
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; }
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 
140 private:
141  Region *scope = nullptr;
142  bool useTopDownTraversal = false;
143  GreedySimplifyRegionLevel regionSimplificationLevel =
145  int64_t maxIterations = 10;
146  int64_t maxNumRewrites = kNoLimit;
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.
176 LogicalResult
177 applyPatternsGreedily(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.
182 LLVM_DEPRECATED("Use applyPatternsGreedily() instead", "applyPatternsGreedily")
183 inline LogicalResult
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.
216 inline LogicalResult
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, &regionChanged)
225  .failed();
226  anyRegionChanged |= regionChanged;
227  }
228  if (changed)
229  *changed = anyRegionChanged;
230  return failure(failed);
231 }
232 /// Same as `applyPatternsGreedily` above with folding.
233 /// FIXME: Remove this once transition to above is complieted.
234 LLVM_DEPRECATED("Use applyPatternsGreedily() instead", "applyPatternsGreedily")
235 inline LogicalResult
239  bool *changed = nullptr) {
240  config.enableFolding();
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.
272 LogicalResult
273 applyOpPatternsGreedily(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.
279 LLVM_DEPRECATED("Use applyOpPatternsGreedily() instead",
280  "applyOpPatternsGreedily")
281 inline LogicalResult
282 applyOpPatternsAndFold(ArrayRef<Operation *> ops,
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_
This class represents a frozen set of patterns that can be processed by a pattern applicator.
This class allows control over how the GreedyPatternRewriteDriver works.
static constexpr int64_t kNoLimit
bool isFoldingEnabled() const
Whether this should fold while greedily rewriting.
GreedyRewriteConfig & setListener(RewriterBase::Listener *listener)
bool isConstantCSEEnabled() const
If set to "true", constants are CSE'd (even across multiple regions that are in a parent-ancestor rel...
GreedyRewriteConfig & setUseTopDownTraversal(bool use=true)
GreedyRewriteStrictness getStrictness() const
Strict mode can restrict the ops that are added to the worklist during the rewrite.
GreedyRewriteConfig & setStrictness(GreedyRewriteStrictness mode)
bool getUseTopDownTraversal() const
This specifies the order of initial traversal that populates the rewriters worklist.
GreedyRewriteConfig & setScope(Region *scope)
Region * getScope() const
Only ops within the scope are added to the worklist.
GreedyRewriteConfig & setMaxIterations(int64_t iterations)
RewriterBase::Listener * getListener() const
An optional listener that should be notified about IR modifications.
int64_t getMaxNumRewrites() const
This specifies the maximum number of rewrites within an iteration.
GreedyRewriteConfig & setRegionSimplificationLevel(GreedySimplifyRegionLevel level)
GreedyRewriteConfig & setMaxNumRewrites(int64_t limit)
int64_t getMaxIterations() const
This specifies the maximum number of times the rewriter will iterate between applying patterns and si...
GreedyRewriteConfig & enableConstantCSE(bool enable=true)
GreedySimplifyRegionLevel getRegionSimplificationLevel() const
Perform control flow optimizations to the region tree after applying all patterns.
GreedyRewriteConfig & enableFolding(bool enable=true)
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:677
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
Include the generated interface declarations.
const FrozenRewritePatternSet GreedyRewriteConfig bool * changed
@ Aggressive
Run extra simplificiations (e.g.
@ Normal
Run the normal simplification (e.g. dead args elimination).
@ Disabled
Disable region control-flow simplification.
const FrozenRewritePatternSet GreedyRewriteConfig config
LogicalResult applyPatternsGreedily(Region &region, const FrozenRewritePatternSet &patterns, GreedyRewriteConfig config=GreedyRewriteConfig(), bool *changed=nullptr)
Rewrite ops in the given region, which must be isolated from above, by repeatedly applying the highes...
LogicalResult applyOpPatternsGreedily(ArrayRef< Operation * > ops, const FrozenRewritePatternSet &patterns, GreedyRewriteConfig config=GreedyRewriteConfig(), bool *changed=nullptr, bool *allErased=nullptr)
Rewrite the specified ops by repeatedly applying the highest benefit patterns in a greedy worklist dr...
LLVM_DEPRECATED("Use applyOpPatternsGreedily() instead", "applyOpPatternsGreedily") inline LogicalResult applyOpPatternsAndFold(ArrayRef< Operation * > ops
Same as applyOpPatternsGreedily with folding.
const FrozenRewritePatternSet & patterns
LogicalResult applyPatternsAndFoldGreedily(Region &region, const FrozenRewritePatternSet &patterns, GreedyRewriteConfig config=GreedyRewriteConfig(), bool *changed=nullptr)
Same as applyPatternsAndGreedily above with folding.
GreedyRewriteStrictness
This enum controls which ops are put on the worklist during a greedy pattern rewrite.
@ ExistingOps
Only pre-existing ops are processed.
@ ExistingAndNewOps
Only pre-existing and newly created ops are processed.
@ AnyOp
No restrictions wrt. which ops are processed.