1 //===- PDL.cpp - Pattern Descriptor Language Dialect ----------------------===//
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 #include "mlir/Dialect/PDL/IR/PDL.h"
10 #include "mlir/Dialect/PDL/IR/PDLOps.h"
11 #include "mlir/Dialect/PDL/IR/PDLTypes.h"
12 #include "mlir/IR/BuiltinTypes.h"
13 #include "mlir/Interfaces/InferTypeOpInterface.h"
14 #include "llvm/ADT/StringSwitch.h"
15 
16 using namespace mlir;
17 using namespace mlir::pdl;
18 
19 //===----------------------------------------------------------------------===//
20 // PDLDialect
21 //===----------------------------------------------------------------------===//
22 
23 void PDLDialect::initialize() {
24   addOperations<
25 #define GET_OP_LIST
26 #include "mlir/Dialect/PDL/IR/PDLOps.cpp.inc"
27       >();
28   registerTypes();
29 }
30 
31 //===----------------------------------------------------------------------===//
32 // PDL Operations
33 //===----------------------------------------------------------------------===//
34 
35 /// Returns true if the given operation is used by a "binding" pdl operation
36 /// within the main matcher body of a `pdl.pattern`.
37 static bool hasBindingUseInMatcher(Operation *op, Block *matcherBlock) {
38   for (OpOperand &use : op->getUses()) {
39     Operation *user = use.getOwner();
40     if (user->getBlock() != matcherBlock)
41       continue;
42     if (isa<AttributeOp, OperandOp, OperandsOp, OperationOp>(user))
43       return true;
44     // Only the first operand of RewriteOp may be bound to, i.e. the root
45     // operation of the pattern.
46     if (isa<RewriteOp>(user) && use.getOperandNumber() == 0)
47       return true;
48     // A result by itself is not binding, it must also be bound.
49     if (isa<ResultOp, ResultsOp>(user) &&
50         hasBindingUseInMatcher(user, matcherBlock))
51       return true;
52   }
53   return false;
54 }
55 
56 /// Returns success if the given operation is used by a "binding" pdl operation
57 /// within the main matcher body of a `pdl.pattern`. On failure, emits an error
58 /// with the given context message.
59 static LogicalResult
60 verifyHasBindingUseInMatcher(Operation *op,
61                              StringRef bindableContextStr = "`pdl.operation`") {
62   // If the pattern is not a pattern, there is nothing to do.
63   if (!isa<PatternOp>(op->getParentOp()))
64     return success();
65   if (hasBindingUseInMatcher(op, op->getBlock()))
66     return success();
67   return op->emitOpError()
68          << "expected a bindable (i.e. " << bindableContextStr
69          << ") user when defined in the matcher body of a `pdl.pattern`";
70 }
71 
72 //===----------------------------------------------------------------------===//
73 // pdl::ApplyNativeConstraintOp
74 //===----------------------------------------------------------------------===//
75 
76 static LogicalResult verify(ApplyNativeConstraintOp op) {
77   if (op.getNumOperands() == 0)
78     return op.emitOpError("expected at least one argument");
79   return success();
80 }
81 
82 //===----------------------------------------------------------------------===//
83 // pdl::ApplyNativeRewriteOp
84 //===----------------------------------------------------------------------===//
85 
86 static LogicalResult verify(ApplyNativeRewriteOp op) {
87   if (op.getNumOperands() == 0 && op.getNumResults() == 0)
88     return op.emitOpError("expected at least one argument or result");
89   return success();
90 }
91 
92 //===----------------------------------------------------------------------===//
93 // pdl::AttributeOp
94 //===----------------------------------------------------------------------===//
95 
96 static LogicalResult verify(AttributeOp op) {
97   Value attrType = op.type();
98   Optional<Attribute> attrValue = op.value();
99 
100   if (!attrValue && isa<RewriteOp>(op->getParentOp()))
101     return op.emitOpError("expected constant value when specified within a "
102                           "`pdl.rewrite`");
103   if (attrValue && attrType)
104     return op.emitOpError("expected only one of [`type`, `value`] to be set");
105   return verifyHasBindingUseInMatcher(op);
106 }
107 
108 //===----------------------------------------------------------------------===//
109 // pdl::OperandOp
110 //===----------------------------------------------------------------------===//
111 
112 static LogicalResult verify(OperandOp op) {
113   return verifyHasBindingUseInMatcher(op);
114 }
115 
116 //===----------------------------------------------------------------------===//
117 // pdl::OperandsOp
118 //===----------------------------------------------------------------------===//
119 
120 static LogicalResult verify(OperandsOp op) {
121   return verifyHasBindingUseInMatcher(op);
122 }
123 
124 //===----------------------------------------------------------------------===//
125 // pdl::OperationOp
126 //===----------------------------------------------------------------------===//
127 
128 static ParseResult parseOperationOpAttributes(
129     OpAsmParser &p, SmallVectorImpl<OpAsmParser::OperandType> &attrOperands,
130     ArrayAttr &attrNamesAttr) {
131   Builder &builder = p.getBuilder();
132   SmallVector<Attribute, 4> attrNames;
133   if (succeeded(p.parseOptionalLBrace())) {
134     do {
135       StringAttr nameAttr;
136       OpAsmParser::OperandType operand;
137       if (p.parseAttribute(nameAttr) || p.parseEqual() ||
138           p.parseOperand(operand))
139         return failure();
140       attrNames.push_back(nameAttr);
141       attrOperands.push_back(operand);
142     } while (succeeded(p.parseOptionalComma()));
143     if (p.parseRBrace())
144       return failure();
145   }
146   attrNamesAttr = builder.getArrayAttr(attrNames);
147   return success();
148 }
149 
150 static void printOperationOpAttributes(OpAsmPrinter &p, OperationOp op,
151                                        OperandRange attrArgs,
152                                        ArrayAttr attrNames) {
153   if (attrNames.empty())
154     return;
155   p << " {";
156   interleaveComma(llvm::seq<int>(0, attrNames.size()), p,
157                   [&](int i) { p << attrNames[i] << " = " << attrArgs[i]; });
158   p << '}';
159 }
160 
161 /// Verifies that the result types of this operation, defined within a
162 /// `pdl.rewrite`, can be inferred.
163 static LogicalResult verifyResultTypesAreInferrable(OperationOp op,
164                                                     OperandRange resultTypes) {
165   // Functor that returns if the given use can be used to infer a type.
166   Block *rewriterBlock = op->getBlock();
167   auto canInferTypeFromUse = [&](OpOperand &use) {
168     // If the use is within a ReplaceOp and isn't the operation being replaced
169     // (i.e. is not the first operand of the replacement), we can infer a type.
170     ReplaceOp replOpUser = dyn_cast<ReplaceOp>(use.getOwner());
171     if (!replOpUser || use.getOperandNumber() == 0)
172       return false;
173     // Make sure the replaced operation was defined before this one.
174     Operation *replacedOp = replOpUser.operation().getDefiningOp();
175     return replacedOp->getBlock() != rewriterBlock ||
176            replacedOp->isBeforeInBlock(op);
177   };
178 
179   // Check to see if the uses of the operation itself can be used to infer
180   // types.
181   if (llvm::any_of(op.op().getUses(), canInferTypeFromUse))
182     return success();
183 
184   // Otherwise, make sure each of the types can be inferred.
185   for (auto it : llvm::enumerate(resultTypes)) {
186     Operation *resultTypeOp = it.value().getDefiningOp();
187     assert(resultTypeOp && "expected valid result type operation");
188 
189     // If the op was defined by a `apply_native_rewrite`, it is guaranteed to be
190     // usable.
191     if (isa<ApplyNativeRewriteOp>(resultTypeOp))
192       continue;
193 
194     // If the type operation was defined in the matcher and constrains the
195     // result of an input operation, it can be used.
196     auto constrainsInputOp = [rewriterBlock](Operation *user) {
197       return user->getBlock() != rewriterBlock && isa<OperationOp>(user);
198     };
199     if (TypeOp typeOp = dyn_cast<TypeOp>(resultTypeOp)) {
200       if (typeOp.type() || llvm::any_of(typeOp->getUsers(), constrainsInputOp))
201         continue;
202     } else if (TypesOp typeOp = dyn_cast<TypesOp>(resultTypeOp)) {
203       if (typeOp.types() || llvm::any_of(typeOp->getUsers(), constrainsInputOp))
204         continue;
205     }
206 
207     return op
208         .emitOpError("must have inferable or constrained result types when "
209                      "nested within `pdl.rewrite`")
210         .attachNote()
211         .append("result type #", it.index(), " was not constrained");
212   }
213   return success();
214 }
215 
216 static LogicalResult verify(OperationOp op) {
217   bool isWithinRewrite = isa<RewriteOp>(op->getParentOp());
218   if (isWithinRewrite && !op.name())
219     return op.emitOpError("must have an operation name when nested within "
220                           "a `pdl.rewrite`");
221   ArrayAttr attributeNames = op.attributeNames();
222   auto attributeValues = op.attributes();
223   if (attributeNames.size() != attributeValues.size()) {
224     return op.emitOpError()
225            << "expected the same number of attribute values and attribute "
226               "names, got "
227            << attributeNames.size() << " names and " << attributeValues.size()
228            << " values";
229   }
230 
231   // If the operation is within a rewrite body and doesn't have type inference,
232   // ensure that the result types can be resolved.
233   if (isWithinRewrite && !op.hasTypeInference()) {
234     if (failed(verifyResultTypesAreInferrable(op, op.types())))
235       return failure();
236   }
237 
238   return verifyHasBindingUseInMatcher(op, "`pdl.operation` or `pdl.rewrite`");
239 }
240 
241 bool OperationOp::hasTypeInference() {
242   Optional<StringRef> opName = name();
243   if (!opName)
244     return false;
245 
246   OperationName name(*opName, getContext());
247   if (const AbstractOperation *op = name.getAbstractOperation())
248     return op->getInterface<InferTypeOpInterface>();
249   return false;
250 }
251 
252 //===----------------------------------------------------------------------===//
253 // pdl::PatternOp
254 //===----------------------------------------------------------------------===//
255 
256 static LogicalResult verify(PatternOp pattern) {
257   Region &body = pattern.body();
258   auto *term = body.front().getTerminator();
259   if (!isa<RewriteOp>(term)) {
260     return pattern.emitOpError("expected body to terminate with `pdl.rewrite`")
261         .attachNote(term->getLoc())
262         .append("see terminator defined here");
263   }
264 
265   // Check that all values defined in the top-level pattern are referenced at
266   // least once in the source tree.
267   WalkResult result = body.walk([&](Operation *op) -> WalkResult {
268     if (!isa_and_nonnull<PDLDialect>(op->getDialect())) {
269       pattern
270           .emitOpError("expected only `pdl` operations within the pattern body")
271           .attachNote(op->getLoc())
272           .append("see non-`pdl` operation defined here");
273       return WalkResult::interrupt();
274     }
275     return WalkResult::advance();
276   });
277   return failure(result.wasInterrupted());
278 }
279 
280 void PatternOp::build(OpBuilder &builder, OperationState &state,
281                       Optional<StringRef> rootKind, Optional<uint16_t> benefit,
282                       Optional<StringRef> name) {
283   build(builder, state,
284         rootKind ? builder.getStringAttr(*rootKind) : StringAttr(),
285         builder.getI16IntegerAttr(benefit ? *benefit : 0),
286         name ? builder.getStringAttr(*name) : StringAttr());
287   builder.createBlock(state.addRegion());
288 }
289 
290 /// Returns the rewrite operation of this pattern.
291 RewriteOp PatternOp::getRewriter() {
292   return cast<RewriteOp>(body().front().getTerminator());
293 }
294 
295 /// Return the root operation kind that this pattern matches, or None if
296 /// there isn't a specific root.
297 Optional<StringRef> PatternOp::getRootKind() {
298   OperationOp rootOp = cast<OperationOp>(getRewriter().root().getDefiningOp());
299   return rootOp.name();
300 }
301 
302 //===----------------------------------------------------------------------===//
303 // pdl::ReplaceOp
304 //===----------------------------------------------------------------------===//
305 
306 static LogicalResult verify(ReplaceOp op) {
307   if (op.replOperation() && !op.replValues().empty())
308     return op.emitOpError() << "expected no replacement values to be provided"
309                                " when the replacement operation is present";
310   return success();
311 }
312 
313 //===----------------------------------------------------------------------===//
314 // pdl::ResultsOp
315 //===----------------------------------------------------------------------===//
316 
317 static ParseResult parseResultsValueType(OpAsmParser &p, IntegerAttr index,
318                                          Type &resultType) {
319   if (!index) {
320     resultType = RangeType::get(p.getBuilder().getType<ValueType>());
321     return success();
322   }
323   if (p.parseArrow() || p.parseType(resultType))
324     return failure();
325   return success();
326 }
327 
328 static void printResultsValueType(OpAsmPrinter &p, ResultsOp op,
329                                   IntegerAttr index, Type resultType) {
330   if (index)
331     p << " -> " << resultType;
332 }
333 
334 static LogicalResult verify(ResultsOp op) {
335   if (!op.index() && op.getType().isa<pdl::ValueType>()) {
336     return op.emitOpError() << "expected `pdl.range<value>` result type when "
337                                "no index is specified, but got: "
338                             << op.getType();
339   }
340   return success();
341 }
342 
343 //===----------------------------------------------------------------------===//
344 // pdl::RewriteOp
345 //===----------------------------------------------------------------------===//
346 
347 static LogicalResult verify(RewriteOp op) {
348   Region &rewriteRegion = op.body();
349 
350   // Handle the case where the rewrite is external.
351   if (op.name()) {
352     if (!rewriteRegion.empty()) {
353       return op.emitOpError()
354              << "expected rewrite region to be empty when rewrite is external";
355     }
356     return success();
357   }
358 
359   // Otherwise, check that the rewrite region only contains a single block.
360   if (rewriteRegion.empty()) {
361     return op.emitOpError() << "expected rewrite region to be non-empty if "
362                                "external name is not specified";
363   }
364 
365   // Check that no additional arguments were provided.
366   if (!op.externalArgs().empty()) {
367     return op.emitOpError() << "expected no external arguments when the "
368                                "rewrite is specified inline";
369   }
370   if (op.externalConstParams()) {
371     return op.emitOpError() << "expected no external constant parameters when "
372                                "the rewrite is specified inline";
373   }
374 
375   return success();
376 }
377 
378 //===----------------------------------------------------------------------===//
379 // pdl::TypeOp
380 //===----------------------------------------------------------------------===//
381 
382 static LogicalResult verify(TypeOp op) {
383   return verifyHasBindingUseInMatcher(
384       op, "`pdl.attribute`, `pdl.operand`, or `pdl.operation`");
385 }
386 
387 //===----------------------------------------------------------------------===//
388 // pdl::TypesOp
389 //===----------------------------------------------------------------------===//
390 
391 static LogicalResult verify(TypesOp op) {
392   return verifyHasBindingUseInMatcher(op, "`pdl.operands`, or `pdl.operation`");
393 }
394 
395 //===----------------------------------------------------------------------===//
396 // TableGen'd op method definitions
397 //===----------------------------------------------------------------------===//
398 
399 #define GET_OP_CLASSES
400 #include "mlir/Dialect/PDL/IR/PDLOps.cpp.inc"
401