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 19 namespace mlir { 20 21 /// This enum controls which ops are put on the worklist during a greedy 22 /// pattern rewrite. 23 enum 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 enum 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. 43 class GreedyRewriteConfig { 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 useTopDownTraversal = false; 53 54 /// Perform control flow optimizations to the region tree after applying all 55 /// patterns. 56 /// 57 /// Note: Only applicable when simplifying entire regions. 58 GreedySimplifyRegionLevel enableRegionSimplification = 59 GreedySimplifyRegionLevel::Aggressive; 60 61 /// This specifies the maximum number of times the rewriter will iterate 62 /// between applying patterns and simplifying regions. Use `kNoLimit` to 63 /// disable this iteration limit. 64 /// 65 /// Note: Only applicable when simplifying entire regions. 66 int64_t maxIterations = 10; 67 68 /// This specifies the maximum number of rewrites within an iteration. Use 69 /// `kNoLimit` to disable this limit. 70 int64_t maxNumRewrites = kNoLimit; 71 72 static constexpr int64_t kNoLimit = -1; 73 74 /// Only ops within the scope are added to the worklist. If no scope is 75 /// specified, the closest enclosing region around the initial list of ops 76 /// (or the specified region, depending on which greedy rewrite entry point 77 /// is used) is used as a scope. 78 Region *scope = nullptr; 79 80 /// Strict mode can restrict the ops that are added to the worklist during 81 /// the rewrite. 82 /// 83 /// * GreedyRewriteStrictness::AnyOp: No ops are excluded. 84 /// * GreedyRewriteStrictness::ExistingAndNewOps: Only pre-existing ops (that 85 /// were on the worklist at the very beginning) and newly created ops are 86 /// enqueued. All other ops are excluded. 87 /// * GreedyRewriteStrictness::ExistingOps: Only pre-existing ops (that were 88 /// were on the worklist at the very beginning) enqueued. All other ops are 89 /// excluded. 90 GreedyRewriteStrictness strictMode = GreedyRewriteStrictness::AnyOp; 91 92 /// An optional listener that should be notified about IR modifications. 93 RewriterBase::Listener *listener = nullptr; 94 95 /// Whether this should fold while greedily rewriting. 96 bool fold = true; 97 98 /// If set to "true", constants are CSE'd (even across multiple regions that 99 /// are in a parent-ancestor relationship). 100 bool cseConstants = true; 101 }; 102 103 //===----------------------------------------------------------------------===// 104 // applyPatternsGreedily 105 //===----------------------------------------------------------------------===// 106 107 /// Rewrite ops in the given region, which must be isolated from above, by 108 /// repeatedly applying the highest benefit patterns in a greedy worklist 109 /// driven manner until a fixpoint is reached. 110 /// 111 /// The greedy rewrite may prematurely stop after a maximum number of 112 /// iterations, which can be configured in the configuration parameter. 113 /// 114 /// Also performs simple dead-code elimination before attempting to match any of 115 /// the provided patterns. 116 /// 117 /// A region scope can be set in the configuration parameter. By default, the 118 /// scope is set to the specified region. Only in-scope ops are added to the 119 /// worklist and only in-scope ops are allowed to be modified by the patterns. 120 /// 121 /// Returns "success" if the iterative process converged (i.e., fixpoint was 122 /// reached) and no more patterns can be matched within the region. `changed` 123 /// is set to "true" if the IR was modified at all. 124 /// 125 /// Note: This method does not apply patterns to the region's parent operation. 126 LogicalResult 127 applyPatternsGreedily(Region ®ion, const FrozenRewritePatternSet &patterns, 128 GreedyRewriteConfig config = GreedyRewriteConfig(), 129 bool *changed = nullptr); 130 /// Same as `applyPatternsAndGreedily` above with folding. 131 /// FIXME: Remove this once transition to above is complieted. 132 LLVM_DEPRECATED("Use applyPatternsGreedily() instead", "applyPatternsGreedily") 133 inline LogicalResult 134 applyPatternsAndFoldGreedily(Region ®ion, 135 const FrozenRewritePatternSet &patterns, 136 GreedyRewriteConfig config = GreedyRewriteConfig(), 137 bool *changed = nullptr) { 138 config.fold = true; 139 return applyPatternsGreedily(region, patterns, config, changed); 140 } 141 142 /// Rewrite ops nested under the given operation, which must be isolated from 143 /// above, by repeatedly applying the highest benefit patterns in a greedy 144 /// worklist driven manner until a fixpoint is reached. 145 /// 146 /// The greedy rewrite may prematurely stop after a maximum number of 147 /// iterations, which can be configured in the configuration parameter. 148 /// 149 /// Also performs simple dead-code elimination before attempting to match any of 150 /// the provided patterns. 151 /// 152 /// This overload runs a separate greedy rewrite for each region of the 153 /// specified op. A region scope can be set in the configuration parameter. By 154 /// default, the scope is set to the region of the current greedy rewrite. Only 155 /// in-scope ops are added to the worklist and only in-scope ops and the 156 /// specified op itself are allowed to be modified by the patterns. 157 /// 158 /// Note: The specified op may be modified, but it may not be removed by the 159 /// patterns. 160 /// 161 /// Returns "success" if the iterative process converged (i.e., fixpoint was 162 /// reached) and no more patterns can be matched within the region. `changed` 163 /// is set to "true" if the IR was modified at all. 164 /// 165 /// Note: This method does not apply patterns to the given operation itself. 166 inline LogicalResult 167 applyPatternsGreedily(Operation *op, const FrozenRewritePatternSet &patterns, 168 GreedyRewriteConfig config = GreedyRewriteConfig(), 169 bool *changed = nullptr) { 170 bool anyRegionChanged = false; 171 bool failed = false; 172 for (Region ®ion : op->getRegions()) { 173 bool regionChanged; 174 failed |= applyPatternsGreedily(region, patterns, config, ®ionChanged) 175 .failed(); 176 anyRegionChanged |= regionChanged; 177 } 178 if (changed) 179 *changed = anyRegionChanged; 180 return failure(failed); 181 } 182 /// Same as `applyPatternsGreedily` above with folding. 183 /// FIXME: Remove this once transition to above is complieted. 184 LLVM_DEPRECATED("Use applyPatternsGreedily() instead", "applyPatternsGreedily") 185 inline LogicalResult 186 applyPatternsAndFoldGreedily(Operation *op, 187 const FrozenRewritePatternSet &patterns, 188 GreedyRewriteConfig config = GreedyRewriteConfig(), 189 bool *changed = nullptr) { 190 config.fold = true; 191 return applyPatternsGreedily(op, patterns, config, changed); 192 } 193 194 /// Rewrite the specified ops by repeatedly applying the highest benefit 195 /// patterns in a greedy worklist driven manner until a fixpoint is reached. 196 /// 197 /// The greedy rewrite may prematurely stop after a maximum number of 198 /// iterations, which can be configured in the configuration parameter. 199 /// 200 /// Also performs simple dead-code elimination before attempting to match any of 201 /// the provided patterns. 202 /// 203 /// Newly created ops and other pre-existing ops that use results of rewritten 204 /// ops or supply operands to such ops are also processed, unless such ops are 205 /// excluded via `config.strictMode`. Any other ops remain unmodified (i.e., 206 /// regardless of `strictMode`). 207 /// 208 /// In addition to strictness, a region scope can be specified. Only ops within 209 /// the scope are simplified. This is similar to `applyPatternsGreedily`, 210 /// where only ops within the given region/op are simplified by default. If no 211 /// scope is specified, it is assumed to be the first common enclosing region of 212 /// the given ops. 213 /// 214 /// Note that ops in `ops` could be erased as result of folding, becoming dead, 215 /// or via pattern rewrites. If more far reaching simplification is desired, 216 /// `applyPatternsGreedily` should be used. 217 /// 218 /// Returns "success" if the iterative process converged (i.e., fixpoint was 219 /// reached) and no more patterns can be matched. `changed` is set to "true" if 220 /// the IR was modified at all. `allOpsErased` is set to "true" if all ops in 221 /// `ops` were erased. 222 LogicalResult 223 applyOpPatternsGreedily(ArrayRef<Operation *> ops, 224 const FrozenRewritePatternSet &patterns, 225 GreedyRewriteConfig config = GreedyRewriteConfig(), 226 bool *changed = nullptr, bool *allErased = nullptr); 227 /// Same as `applyOpPatternsGreedily` with folding. 228 /// FIXME: Remove this once transition to above is complieted. 229 LLVM_DEPRECATED("Use applyOpPatternsGreedily() instead", 230 "applyOpPatternsGreedily") 231 inline LogicalResult 232 applyOpPatternsAndFold(ArrayRef<Operation *> ops, 233 const FrozenRewritePatternSet &patterns, 234 GreedyRewriteConfig config = GreedyRewriteConfig(), 235 bool *changed = nullptr, bool *allErased = nullptr) { 236 config.fold = true; 237 return applyOpPatternsGreedily(ops, patterns, config, changed, allErased); 238 } 239 240 } // namespace mlir 241 242 #endif // MLIR_TRANSFORMS_GREEDYPATTERNREWRITEDRIVER_H_ 243