1//===- PDLToPDLInterp.cpp - Lower a PDL module to the interpreter ---------===//
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/Conversion/PDLToPDLInterp/PDLToPDLInterp.h"
10
11#include "PredicateTree.h"
12#include "mlir/Dialect/PDL/IR/PDLTypes.h"
13#include "mlir/Dialect/PDLInterp/IR/PDLInterp.h"
14#include "mlir/Pass/Pass.h"
15#include "llvm/ADT/MapVector.h"
16#include "llvm/ADT/ScopedHashTable.h"
17#include "llvm/ADT/Sequence.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/TypeSwitch.h"
20
21namespace mlir {
22#define GEN_PASS_DEF_CONVERTPDLTOPDLINTERPPASS
23#include "mlir/Conversion/Passes.h.inc"
24} // namespace mlir
25
26using namespace mlir;
27using namespace mlir::pdl_to_pdl_interp;
28
29//===----------------------------------------------------------------------===//
30// PatternLowering
31//===----------------------------------------------------------------------===//
32
33namespace {
34/// This class generators operations within the PDL Interpreter dialect from a
35/// given module containing PDL pattern operations.
36struct PatternLowering {
37public:
38 PatternLowering(pdl_interp::FuncOp matcherFunc, ModuleOp rewriterModule,
39 DenseMap<Operation *, PDLPatternConfigSet *> *configMap);
40
41 /// Generate code for matching and rewriting based on the pattern operations
42 /// within the module.
43 void lower(ModuleOp module);
44
45private:
46 using ValueMap = llvm::ScopedHashTable<Position *, Value>;
47 using ValueMapScope = llvm::ScopedHashTableScope<Position *, Value>;
48 using ConstraintOpMap = llvm::ScopedHashTable<ConstraintQuestion *,
49 pdl_interp::ApplyConstraintOp>;
50 using ConstraintOpMapScope =
51 llvm::ScopedHashTableScope<ConstraintQuestion *,
52 pdl_interp::ApplyConstraintOp>;
53
54 /// Generate interpreter operations for the tree rooted at the given matcher
55 /// node, in the specified region.
56 Block *generateMatcher(MatcherNode &node, Region &region,
57 Block *block = nullptr);
58
59 /// Get or create an access to the provided positional value in the current
60 /// block. This operation may mutate the provided block pointer if nested
61 /// regions (i.e., pdl_interp.iterate) are required.
62 Value getValueAt(Block *&currentBlock, Position *pos);
63
64 /// Create the interpreter predicate operations. This operation may mutate the
65 /// provided current block pointer if nested regions (iterates) are required.
66 void generate(BoolNode *boolNode, Block *&currentBlock, Value val);
67
68 /// Create the interpreter switch / predicate operations, with several case
69 /// destinations. This operation never mutates the provided current block
70 /// pointer, because the switch operation does not need Values beyond `val`.
71 void generate(SwitchNode *switchNode, Block *currentBlock, Value val);
72
73 /// Create the interpreter operations to record a successful pattern match
74 /// using the contained root operation. This operation may mutate the current
75 /// block pointer if nested regions (i.e., pdl_interp.iterate) are required.
76 void generate(SuccessNode *successNode, Block *&currentBlock);
77
78 /// Generate a rewriter function for the given pattern operation, and returns
79 /// a reference to that function.
80 SymbolRefAttr generateRewriter(pdl::PatternOp pattern,
81 SmallVectorImpl<Position *> &usedMatchValues);
82
83 /// Generate the rewriter code for the given operation.
84 void generateRewriter(pdl::ApplyNativeRewriteOp rewriteOp,
85 DenseMap<Value, Value> &rewriteValues,
86 function_ref<Value(Value)> mapRewriteValue);
87 void generateRewriter(pdl::AttributeOp attrOp,
88 DenseMap<Value, Value> &rewriteValues,
89 function_ref<Value(Value)> mapRewriteValue);
90 void generateRewriter(pdl::EraseOp eraseOp,
91 DenseMap<Value, Value> &rewriteValues,
92 function_ref<Value(Value)> mapRewriteValue);
93 void generateRewriter(pdl::OperationOp operationOp,
94 DenseMap<Value, Value> &rewriteValues,
95 function_ref<Value(Value)> mapRewriteValue);
96 void generateRewriter(pdl::RangeOp rangeOp,
97 DenseMap<Value, Value> &rewriteValues,
98 function_ref<Value(Value)> mapRewriteValue);
99 void generateRewriter(pdl::ReplaceOp replaceOp,
100 DenseMap<Value, Value> &rewriteValues,
101 function_ref<Value(Value)> mapRewriteValue);
102 void generateRewriter(pdl::ResultOp resultOp,
103 DenseMap<Value, Value> &rewriteValues,
104 function_ref<Value(Value)> mapRewriteValue);
105 void generateRewriter(pdl::ResultsOp resultOp,
106 DenseMap<Value, Value> &rewriteValues,
107 function_ref<Value(Value)> mapRewriteValue);
108 void generateRewriter(pdl::TypeOp typeOp,
109 DenseMap<Value, Value> &rewriteValues,
110 function_ref<Value(Value)> mapRewriteValue);
111 void generateRewriter(pdl::TypesOp typeOp,
112 DenseMap<Value, Value> &rewriteValues,
113 function_ref<Value(Value)> mapRewriteValue);
114
115 /// Generate the values used for resolving the result types of an operation
116 /// created within a dag rewriter region. If the result types of the operation
117 /// should be inferred, `hasInferredResultTypes` is set to true.
118 void generateOperationResultTypeRewriter(
119 pdl::OperationOp op, function_ref<Value(Value)> mapRewriteValue,
120 SmallVectorImpl<Value> &types, DenseMap<Value, Value> &rewriteValues,
121 bool &hasInferredResultTypes);
122
123 /// A builder to use when generating interpreter operations.
124 OpBuilder builder;
125
126 /// The matcher function used for all match related logic within PDL patterns.
127 pdl_interp::FuncOp matcherFunc;
128
129 /// The rewriter module containing the all rewrite related logic within PDL
130 /// patterns.
131 ModuleOp rewriterModule;
132
133 /// The symbol table of the rewriter module used for insertion.
134 SymbolTable rewriterSymbolTable;
135
136 /// A scoped map connecting a position with the corresponding interpreter
137 /// value.
138 ValueMap values;
139
140 /// A stack of blocks used as the failure destination for matcher nodes that
141 /// don't have an explicit failure path.
142 SmallVector<Block *, 8> failureBlockStack;
143
144 /// A mapping between values defined in a pattern match, and the corresponding
145 /// positional value.
146 DenseMap<Value, Position *> valueToPosition;
147
148 /// The set of operation values whose location will be used for newly
149 /// generated operations.
150 SetVector<Value> locOps;
151
152 /// A mapping between pattern operations and the corresponding configuration
153 /// set.
154 DenseMap<Operation *, PDLPatternConfigSet *> *configMap;
155
156 /// A scoped mapping from a constraint question to the ApplyConstraintOp
157 /// that implements it.
158 ConstraintOpMap constraintOpMap;
159};
160} // namespace
161
162PatternLowering::PatternLowering(
163 pdl_interp::FuncOp matcherFunc, ModuleOp rewriterModule,
164 DenseMap<Operation *, PDLPatternConfigSet *> *configMap)
165 : builder(matcherFunc.getContext()), matcherFunc(matcherFunc),
166 rewriterModule(rewriterModule), rewriterSymbolTable(rewriterModule),
167 configMap(configMap) {}
168
169void PatternLowering::lower(ModuleOp module) {
170 PredicateUniquer predicateUniquer;
171 PredicateBuilder predicateBuilder(predicateUniquer, module.getContext());
172
173 // Define top-level scope for the arguments to the matcher function.
174 ValueMapScope topLevelValueScope(values);
175 ConstraintOpMapScope topLevelConstraintScope(constraintOpMap);
176
177 // Insert the root operation, i.e. argument to the matcher, at the root
178 // position.
179 Block *matcherEntryBlock = &matcherFunc.front();
180 values.insert(Key: predicateBuilder.getRoot(), Val: matcherEntryBlock->getArgument(i: 0));
181
182 // Generate a root matcher node from the provided PDL module.
183 std::unique_ptr<MatcherNode> root = MatcherNode::generateMatcherTree(
184 module, builder&: predicateBuilder, valueToPosition);
185 Block *firstMatcherBlock = generateMatcher(node&: *root, region&: matcherFunc.getBody());
186 assert(failureBlockStack.empty() && "failed to empty the stack");
187
188 // After generation, merged the first matched block into the entry.
189 matcherEntryBlock->getOperations().splice(where: matcherEntryBlock->end(),
190 L2&: firstMatcherBlock->getOperations());
191 firstMatcherBlock->erase();
192}
193
194Block *PatternLowering::generateMatcher(MatcherNode &node, Region &region,
195 Block *block) {
196 // Push a new scope for the values used by this matcher.
197 if (!block)
198 block = &region.emplaceBlock();
199 ValueMapScope scope(values);
200 ConstraintOpMapScope constraintScope(constraintOpMap);
201
202 // If this is the return node, simply insert the corresponding interpreter
203 // finalize.
204 if (isa<ExitNode>(Val: node)) {
205 builder.setInsertionPointToEnd(block);
206 pdl_interp::FinalizeOp::create(builder, location: matcherFunc.getLoc());
207 return block;
208 }
209
210 // Get the next block in the match sequence.
211 // This is intentionally executed first, before we get the value for the
212 // position associated with the node, so that we preserve an "there exist"
213 // semantics: if getting a value requires an upward traversal (going from a
214 // value to its consumers), we want to perform the check on all the consumers
215 // before we pass control to the failure node.
216 std::unique_ptr<MatcherNode> &failureNode = node.getFailureNode();
217 Block *failureBlock;
218 if (failureNode) {
219 failureBlock = generateMatcher(node&: *failureNode, region);
220 failureBlockStack.push_back(Elt: failureBlock);
221 } else {
222 assert(!failureBlockStack.empty() && "expected valid failure block");
223 failureBlock = failureBlockStack.back();
224 }
225
226 // If this node contains a position, get the corresponding value for this
227 // block.
228 Block *currentBlock = block;
229 Position *position = node.getPosition();
230 Value val = position ? getValueAt(currentBlock, pos: position) : Value();
231
232 // If this value corresponds to an operation, record that we are going to use
233 // its location as part of a fused location.
234 bool isOperationValue = val && isa<pdl::OperationType>(Val: val.getType());
235 if (isOperationValue)
236 locOps.insert(X: val);
237
238 // Dispatch to the correct method based on derived node type.
239 TypeSwitch<MatcherNode *>(&node)
240 .Case<BoolNode, SwitchNode>(caseFn: [&](auto *derivedNode) {
241 this->generate(derivedNode, currentBlock, val);
242 })
243 .Case(caseFn: [&](SuccessNode *successNode) {
244 generate(successNode, currentBlock);
245 });
246
247 // Pop all the failure blocks that were inserted due to nesting of
248 // pdl_interp.iterate.
249 while (failureBlockStack.back() != failureBlock) {
250 failureBlockStack.pop_back();
251 assert(!failureBlockStack.empty() && "unable to locate failure block");
252 }
253
254 // Pop the new failure block.
255 if (failureNode)
256 failureBlockStack.pop_back();
257
258 if (isOperationValue)
259 locOps.remove(X: val);
260
261 return block;
262}
263
264Value PatternLowering::getValueAt(Block *&currentBlock, Position *pos) {
265 if (Value val = values.lookup(Key: pos))
266 return val;
267
268 // Get the value for the parent position.
269 Value parentVal;
270 if (Position *parent = pos->getParent())
271 parentVal = getValueAt(currentBlock, pos: parent);
272
273 // TODO: Use a location from the position.
274 Location loc = parentVal ? parentVal.getLoc() : builder.getUnknownLoc();
275 builder.setInsertionPointToEnd(currentBlock);
276 Value value;
277 switch (pos->getKind()) {
278 case Predicates::OperationPos: {
279 auto *operationPos = cast<OperationPosition>(Val: pos);
280 if (operationPos->isOperandDefiningOp())
281 // Standard (downward) traversal which directly follows the defining op.
282 value = pdl_interp::GetDefiningOpOp::create(
283 builder, location: loc, inputOp: builder.getType<pdl::OperationType>(), value: parentVal);
284 else
285 // A passthrough operation position.
286 value = parentVal;
287 break;
288 }
289 case Predicates::UsersPos: {
290 auto *usersPos = cast<UsersPosition>(Val: pos);
291
292 // The first operation retrieves the representative value of a range.
293 // This applies only when the parent is a range of values and we were
294 // requested to use a representative value (e.g., upward traversal).
295 if (isa<pdl::RangeType>(Val: parentVal.getType()) &&
296 usersPos->useRepresentative())
297 value = pdl_interp::ExtractOp::create(builder, location: loc, range: parentVal, index: 0);
298 else
299 value = parentVal;
300
301 // The second operation retrieves the users.
302 value = pdl_interp::GetUsersOp::create(builder, location: loc, value);
303 break;
304 }
305 case Predicates::ForEachPos: {
306 assert(!failureBlockStack.empty() && "expected valid failure block");
307 auto foreach = pdl_interp::ForEachOp::create(
308 builder, location: loc, range: parentVal, successor: failureBlockStack.back(), /*initLoop=*/true);
309 value = foreach.getLoopVariable();
310
311 // Create the continuation block.
312 Block *continueBlock = builder.createBlock(parent: &foreach.getRegion());
313 pdl_interp::ContinueOp::create(builder, location: loc);
314 failureBlockStack.push_back(Elt: continueBlock);
315
316 currentBlock = &foreach.getRegion().front();
317 break;
318 }
319 case Predicates::OperandPos: {
320 auto *operandPos = cast<OperandPosition>(Val: pos);
321 value = pdl_interp::GetOperandOp::create(
322 builder, location: loc, value: builder.getType<pdl::ValueType>(), inputOp: parentVal,
323 index: operandPos->getOperandNumber());
324 break;
325 }
326 case Predicates::OperandGroupPos: {
327 auto *operandPos = cast<OperandGroupPosition>(Val: pos);
328 Type valueTy = builder.getType<pdl::ValueType>();
329 value = pdl_interp::GetOperandsOp::create(
330 builder, location: loc,
331 resultType: operandPos->isVariadic() ? pdl::RangeType::get(elementType: valueTy) : valueTy,
332 inputOp: parentVal, index: operandPos->getOperandGroupNumber());
333 break;
334 }
335 case Predicates::AttributePos: {
336 auto *attrPos = cast<AttributePosition>(Val: pos);
337 value = pdl_interp::GetAttributeOp::create(
338 builder, location: loc, attribute: builder.getType<pdl::AttributeType>(), inputOp: parentVal,
339 name: attrPos->getName().strref());
340 break;
341 }
342 case Predicates::TypePos: {
343 if (isa<pdl::AttributeType>(Val: parentVal.getType()))
344 value = pdl_interp::GetAttributeTypeOp::create(builder, location: loc, value: parentVal);
345 else
346 value = pdl_interp::GetValueTypeOp::create(builder, location: loc, value: parentVal);
347 break;
348 }
349 case Predicates::ResultPos: {
350 auto *resPos = cast<ResultPosition>(Val: pos);
351 value = pdl_interp::GetResultOp::create(
352 builder, location: loc, value: builder.getType<pdl::ValueType>(), inputOp: parentVal,
353 index: resPos->getResultNumber());
354 break;
355 }
356 case Predicates::ResultGroupPos: {
357 auto *resPos = cast<ResultGroupPosition>(Val: pos);
358 Type valueTy = builder.getType<pdl::ValueType>();
359 value = pdl_interp::GetResultsOp::create(
360 builder, location: loc,
361 resultType: resPos->isVariadic() ? pdl::RangeType::get(elementType: valueTy) : valueTy,
362 inputOp: parentVal, index: resPos->getResultGroupNumber());
363 break;
364 }
365 case Predicates::AttributeLiteralPos: {
366 auto *attrPos = cast<AttributeLiteralPosition>(Val: pos);
367 value = pdl_interp::CreateAttributeOp::create(builder, location: loc,
368 value: attrPos->getValue());
369 break;
370 }
371 case Predicates::TypeLiteralPos: {
372 auto *typePos = cast<TypeLiteralPosition>(Val: pos);
373 Attribute rawTypeAttr = typePos->getValue();
374 if (TypeAttr typeAttr = dyn_cast<TypeAttr>(Val&: rawTypeAttr))
375 value = pdl_interp::CreateTypeOp::create(builder, location: loc, type: typeAttr);
376 else
377 value = pdl_interp::CreateTypesOp::create(builder, location: loc,
378 type: cast<ArrayAttr>(Val&: rawTypeAttr));
379 break;
380 }
381 case Predicates::ConstraintResultPos: {
382 // Due to the order of traversal, the ApplyConstraintOp has already been
383 // created and we can find it in constraintOpMap.
384 auto *constrResPos = cast<ConstraintPosition>(Val: pos);
385 pdl_interp::ApplyConstraintOp applyConstraintOp =
386 constraintOpMap.lookup(Key: constrResPos->getQuestion());
387 assert(applyConstraintOp && "expected constraint to be generated");
388 value = applyConstraintOp->getResult(idx: constrResPos->getIndex());
389 break;
390 }
391 default:
392 llvm_unreachable("Generating unknown Position getter");
393 break;
394 }
395
396 values.insert(Key: pos, Val: value);
397 return value;
398}
399
400void PatternLowering::generate(BoolNode *boolNode, Block *&currentBlock,
401 Value val) {
402 Location loc = val.getLoc();
403 Qualifier *question = boolNode->getQuestion();
404 Qualifier *answer = boolNode->getAnswer();
405 Region *region = currentBlock->getParent();
406
407 // Execute the getValue queries first, so that we create success
408 // matcher in the correct (possibly nested) region.
409 SmallVector<Value> args;
410 if (auto *equalToQuestion = dyn_cast<EqualToQuestion>(Val: question)) {
411 args = {getValueAt(currentBlock, pos: equalToQuestion->getValue())};
412 } else if (auto *cstQuestion = dyn_cast<ConstraintQuestion>(Val: question)) {
413 for (Position *position : cstQuestion->getArgs())
414 args.push_back(Elt: getValueAt(currentBlock, pos: position));
415 }
416
417 // Generate a new block as success successor and get the failure successor.
418 Block *success = &region->emplaceBlock();
419 Block *failure = failureBlockStack.back();
420
421 // Create the predicate.
422 builder.setInsertionPointToEnd(currentBlock);
423 Predicates::Kind kind = question->getKind();
424 switch (kind) {
425 case Predicates::IsNotNullQuestion:
426 pdl_interp::IsNotNullOp::create(builder, location: loc, value: val, trueDest: success, falseDest: failure);
427 break;
428 case Predicates::OperationNameQuestion: {
429 auto *opNameAnswer = cast<OperationNameAnswer>(Val: answer);
430 pdl_interp::CheckOperationNameOp::create(
431 builder, location: loc, inputOp: val, name: opNameAnswer->getValue().getStringRef(), trueDest: success,
432 falseDest: failure);
433 break;
434 }
435 case Predicates::TypeQuestion: {
436 auto *ans = cast<TypeAnswer>(Val: answer);
437 if (isa<pdl::RangeType>(Val: val.getType()))
438 pdl_interp::CheckTypesOp::create(builder, location: loc, value: val,
439 types: llvm::cast<ArrayAttr>(Val: ans->getValue()),
440 trueDest: success, falseDest: failure);
441 else
442 pdl_interp::CheckTypeOp::create(builder, location: loc, value: val,
443 type: llvm::cast<TypeAttr>(Val: ans->getValue()),
444 trueDest: success, falseDest: failure);
445 break;
446 }
447 case Predicates::AttributeQuestion: {
448 auto *ans = cast<AttributeAnswer>(Val: answer);
449 pdl_interp::CheckAttributeOp::create(builder, location: loc, attribute: val, constantValue: ans->getValue(),
450 trueDest: success, falseDest: failure);
451 break;
452 }
453 case Predicates::OperandCountAtLeastQuestion:
454 case Predicates::OperandCountQuestion:
455 pdl_interp::CheckOperandCountOp::create(
456 builder, location: loc, inputOp: val, count: cast<UnsignedAnswer>(Val: answer)->getValue(),
457 /*compareAtLeast=*/kind == Predicates::OperandCountAtLeastQuestion,
458 trueDest: success, falseDest: failure);
459 break;
460 case Predicates::ResultCountAtLeastQuestion:
461 case Predicates::ResultCountQuestion:
462 pdl_interp::CheckResultCountOp::create(
463 builder, location: loc, inputOp: val, count: cast<UnsignedAnswer>(Val: answer)->getValue(),
464 /*compareAtLeast=*/kind == Predicates::ResultCountAtLeastQuestion,
465 trueDest: success, falseDest: failure);
466 break;
467 case Predicates::EqualToQuestion: {
468 bool trueAnswer = isa<TrueAnswer>(Val: answer);
469 pdl_interp::AreEqualOp::create(builder, location: loc, lhs: val, rhs: args.front(),
470 trueDest: trueAnswer ? success : failure,
471 falseDest: trueAnswer ? failure : success);
472 break;
473 }
474 case Predicates::ConstraintQuestion: {
475 auto *cstQuestion = cast<ConstraintQuestion>(Val: question);
476 auto applyConstraintOp = pdl_interp::ApplyConstraintOp::create(
477 builder, location: loc, results: cstQuestion->getResultTypes(), name: cstQuestion->getName(),
478 args, isNegated: cstQuestion->getIsNegated(), trueDest: success, falseDest: failure);
479
480 constraintOpMap.insert(Key: cstQuestion, Val: applyConstraintOp);
481 break;
482 }
483 default:
484 llvm_unreachable("Generating unknown Predicate operation");
485 }
486
487 // Generate the matcher in the current (potentially nested) region.
488 // This might use the results of the current predicate.
489 generateMatcher(node&: *boolNode->getSuccessNode(), region&: *region, block: success);
490}
491
492template <typename OpT, typename PredT, typename ValT = typename PredT::KeyTy>
493static void createSwitchOp(Value val, Block *defaultDest, OpBuilder &builder,
494 llvm::MapVector<Qualifier *, Block *> &dests) {
495 std::vector<ValT> values;
496 std::vector<Block *> blocks;
497 values.reserve(dests.size());
498 blocks.reserve(n: dests.size());
499 for (const auto &it : dests) {
500 blocks.push_back(x: it.second);
501 values.push_back(cast<PredT>(it.first)->getValue());
502 }
503 OpT::create(builder, val.getLoc(), val, values, defaultDest, blocks);
504}
505
506void PatternLowering::generate(SwitchNode *switchNode, Block *currentBlock,
507 Value val) {
508 Qualifier *question = switchNode->getQuestion();
509 Region *region = currentBlock->getParent();
510 Block *defaultDest = failureBlockStack.back();
511
512 // If the switch question is not an exact answer, i.e. for the `at_least`
513 // cases, we generate a special block sequence.
514 Predicates::Kind kind = question->getKind();
515 if (kind == Predicates::OperandCountAtLeastQuestion ||
516 kind == Predicates::ResultCountAtLeastQuestion) {
517 // Order the children such that the cases are in reverse numerical order.
518 SmallVector<unsigned> sortedChildren = llvm::to_vector<16>(
519 Range: llvm::seq<unsigned>(Begin: 0, End: switchNode->getChildren().size()));
520 llvm::sort(C&: sortedChildren, Comp: [&](unsigned lhs, unsigned rhs) {
521 return cast<UnsignedAnswer>(Val: switchNode->getChild(i: lhs).first)->getValue() >
522 cast<UnsignedAnswer>(Val: switchNode->getChild(i: rhs).first)->getValue();
523 });
524
525 // Build the destination for each child using the next highest child as a
526 // a failure destination. This essentially creates the following control
527 // flow:
528 //
529 // if (operand_count < 1)
530 // goto failure
531 // if (child1.match())
532 // ...
533 //
534 // if (operand_count < 2)
535 // goto failure
536 // if (child2.match())
537 // ...
538 //
539 // failure:
540 // ...
541 //
542 failureBlockStack.push_back(Elt: defaultDest);
543 Location loc = val.getLoc();
544 for (unsigned idx : sortedChildren) {
545 auto &child = switchNode->getChild(i: idx);
546 Block *childBlock = generateMatcher(node&: *child.second, region&: *region);
547 Block *predicateBlock = builder.createBlock(insertBefore: childBlock);
548 builder.setInsertionPointToEnd(predicateBlock);
549 unsigned ans = cast<UnsignedAnswer>(Val: child.first)->getValue();
550 switch (kind) {
551 case Predicates::OperandCountAtLeastQuestion:
552 pdl_interp::CheckOperandCountOp::create(builder, location: loc, inputOp: val, count: ans,
553 /*compareAtLeast=*/true,
554 trueDest: childBlock, falseDest: defaultDest);
555 break;
556 case Predicates::ResultCountAtLeastQuestion:
557 pdl_interp::CheckResultCountOp::create(builder, location: loc, inputOp: val, count: ans,
558 /*compareAtLeast=*/true,
559 trueDest: childBlock, falseDest: defaultDest);
560 break;
561 default:
562 llvm_unreachable("Generating invalid AtLeast operation");
563 }
564 failureBlockStack.back() = predicateBlock;
565 }
566 Block *firstPredicateBlock = failureBlockStack.pop_back_val();
567 currentBlock->getOperations().splice(where: currentBlock->end(),
568 L2&: firstPredicateBlock->getOperations());
569 firstPredicateBlock->erase();
570 return;
571 }
572
573 // Otherwise, generate each of the children and generate an interpreter
574 // switch.
575 llvm::MapVector<Qualifier *, Block *> children;
576 for (auto &it : switchNode->getChildren())
577 children.insert(KV: {it.first, generateMatcher(node&: *it.second, region&: *region)});
578 builder.setInsertionPointToEnd(currentBlock);
579
580 switch (question->getKind()) {
581 case Predicates::OperandCountQuestion:
582 return createSwitchOp<pdl_interp::SwitchOperandCountOp, UnsignedAnswer,
583 int32_t>(val, defaultDest, builder, dests&: children);
584 case Predicates::ResultCountQuestion:
585 return createSwitchOp<pdl_interp::SwitchResultCountOp, UnsignedAnswer,
586 int32_t>(val, defaultDest, builder, dests&: children);
587 case Predicates::OperationNameQuestion:
588 return createSwitchOp<pdl_interp::SwitchOperationNameOp,
589 OperationNameAnswer>(val, defaultDest, builder,
590 dests&: children);
591 case Predicates::TypeQuestion:
592 if (isa<pdl::RangeType>(Val: val.getType())) {
593 return createSwitchOp<pdl_interp::SwitchTypesOp, TypeAnswer>(
594 val, defaultDest, builder, dests&: children);
595 }
596 return createSwitchOp<pdl_interp::SwitchTypeOp, TypeAnswer>(
597 val, defaultDest, builder, dests&: children);
598 case Predicates::AttributeQuestion:
599 return createSwitchOp<pdl_interp::SwitchAttributeOp, AttributeAnswer>(
600 val, defaultDest, builder, dests&: children);
601 default:
602 llvm_unreachable("Generating unknown switch predicate.");
603 }
604}
605
606void PatternLowering::generate(SuccessNode *successNode, Block *&currentBlock) {
607 pdl::PatternOp pattern = successNode->getPattern();
608 Value root = successNode->getRoot();
609
610 // Generate a rewriter for the pattern this success node represents, and track
611 // any values used from the match region.
612 SmallVector<Position *, 8> usedMatchValues;
613 SymbolRefAttr rewriterFuncRef = generateRewriter(pattern, usedMatchValues);
614
615 // Process any values used in the rewrite that are defined in the match.
616 std::vector<Value> mappedMatchValues;
617 mappedMatchValues.reserve(n: usedMatchValues.size());
618 for (Position *position : usedMatchValues)
619 mappedMatchValues.push_back(x: getValueAt(currentBlock, pos: position));
620
621 // Collect the set of operations generated by the rewriter.
622 SmallVector<StringRef, 4> generatedOps;
623 for (auto op :
624 pattern.getRewriter().getBodyRegion().getOps<pdl::OperationOp>())
625 generatedOps.push_back(Elt: *op.getOpName());
626 ArrayAttr generatedOpsAttr;
627 if (!generatedOps.empty())
628 generatedOpsAttr = builder.getStrArrayAttr(values: generatedOps);
629
630 // Grab the root kind if present.
631 StringAttr rootKindAttr;
632 if (pdl::OperationOp rootOp = root.getDefiningOp<pdl::OperationOp>())
633 if (std::optional<StringRef> rootKind = rootOp.getOpName())
634 rootKindAttr = builder.getStringAttr(bytes: *rootKind);
635
636 builder.setInsertionPointToEnd(currentBlock);
637 auto matchOp = pdl_interp::RecordMatchOp::create(
638 builder, location: pattern.getLoc(), inputs: mappedMatchValues, matchedOps: locOps.getArrayRef(),
639 rewriter: rewriterFuncRef, rootKind: rootKindAttr, generatedOps: generatedOpsAttr, benefit: pattern.getBenefitAttr(),
640 dest: failureBlockStack.back());
641
642 // Set the config of the lowered match to the parent pattern.
643 if (configMap)
644 configMap->try_emplace(Key: matchOp, Args: configMap->lookup(Val: pattern));
645}
646
647SymbolRefAttr PatternLowering::generateRewriter(
648 pdl::PatternOp pattern, SmallVectorImpl<Position *> &usedMatchValues) {
649 builder.setInsertionPointToEnd(rewriterModule.getBody());
650 // Get the pattern name if available, otherwise use default
651 StringRef rewriterName = "pdl_generated_rewriter";
652 if (auto symName = pattern.getSymName())
653 rewriterName = symName.value();
654 auto rewriterFunc = pdl_interp::FuncOp::create(
655 builder, location: pattern.getLoc(), name: rewriterName, type: builder.getFunctionType(inputs: {}, results: {}));
656 rewriterSymbolTable.insert(symbol: rewriterFunc);
657
658 // Generate the rewriter function body.
659 builder.setInsertionPointToEnd(&rewriterFunc.front());
660
661 // Map an input operand of the pattern to a generated interpreter value.
662 DenseMap<Value, Value> rewriteValues;
663 auto mapRewriteValue = [&](Value oldValue) {
664 Value &newValue = rewriteValues[oldValue];
665 if (newValue)
666 return newValue;
667
668 // Prefer materializing constants directly when possible.
669 Operation *oldOp = oldValue.getDefiningOp();
670 if (pdl::AttributeOp attrOp = dyn_cast<pdl::AttributeOp>(Val: oldOp)) {
671 if (Attribute value = attrOp.getValueAttr()) {
672 return newValue = pdl_interp::CreateAttributeOp::create(
673 builder, location: attrOp.getLoc(), value);
674 }
675 } else if (pdl::TypeOp typeOp = dyn_cast<pdl::TypeOp>(Val: oldOp)) {
676 if (TypeAttr type = typeOp.getConstantTypeAttr()) {
677 return newValue = pdl_interp::CreateTypeOp::create(
678 builder, location: typeOp.getLoc(), type);
679 }
680 } else if (pdl::TypesOp typeOp = dyn_cast<pdl::TypesOp>(Val: oldOp)) {
681 if (ArrayAttr type = typeOp.getConstantTypesAttr()) {
682 return newValue = pdl_interp::CreateTypesOp::create(
683 builder, location: typeOp.getLoc(), result: typeOp.getType(), value: type);
684 }
685 }
686
687 // Otherwise, add this as an input to the rewriter.
688 Position *inputPos = valueToPosition.lookup(Val: oldValue);
689 assert(inputPos && "expected value to be a pattern input");
690 usedMatchValues.push_back(Elt: inputPos);
691 return newValue = rewriterFunc.front().addArgument(type: oldValue.getType(),
692 loc: oldValue.getLoc());
693 };
694
695 // If this is a custom rewriter, simply dispatch to the registered rewrite
696 // method.
697 pdl::RewriteOp rewriter = pattern.getRewriter();
698 if (StringAttr rewriteName = rewriter.getNameAttr()) {
699 SmallVector<Value> args;
700 if (rewriter.getRoot())
701 args.push_back(Elt: mapRewriteValue(rewriter.getRoot()));
702 auto mappedArgs =
703 llvm::map_range(C: rewriter.getExternalArgs(), F: mapRewriteValue);
704 args.append(in_start: mappedArgs.begin(), in_end: mappedArgs.end());
705 pdl_interp::ApplyRewriteOp::create(builder, location: rewriter.getLoc(),
706 /*results=*/TypeRange(), name: rewriteName,
707 args);
708 } else {
709 // Otherwise this is a dag rewriter defined using PDL operations.
710 for (Operation &rewriteOp : *rewriter.getBody()) {
711 llvm::TypeSwitch<Operation *>(&rewriteOp)
712 .Case<pdl::ApplyNativeRewriteOp, pdl::AttributeOp, pdl::EraseOp,
713 pdl::OperationOp, pdl::RangeOp, pdl::ReplaceOp, pdl::ResultOp,
714 pdl::ResultsOp, pdl::TypeOp, pdl::TypesOp>(caseFn: [&](auto op) {
715 this->generateRewriter(op, rewriteValues, mapRewriteValue);
716 });
717 }
718 }
719
720 // Update the signature of the rewrite function.
721 rewriterFunc.setType(builder.getFunctionType(
722 inputs: llvm::to_vector<8>(Range: rewriterFunc.front().getArgumentTypes()),
723 /*results=*/{}));
724
725 pdl_interp::FinalizeOp::create(builder, location: rewriter.getLoc());
726 return SymbolRefAttr::get(
727 ctx: builder.getContext(),
728 value: pdl_interp::PDLInterpDialect::getRewriterModuleName(),
729 nestedRefs: SymbolRefAttr::get(symbol: rewriterFunc));
730}
731
732void PatternLowering::generateRewriter(
733 pdl::ApplyNativeRewriteOp rewriteOp, DenseMap<Value, Value> &rewriteValues,
734 function_ref<Value(Value)> mapRewriteValue) {
735 SmallVector<Value, 2> arguments;
736 for (Value argument : rewriteOp.getArgs())
737 arguments.push_back(Elt: mapRewriteValue(argument));
738 auto interpOp = pdl_interp::ApplyRewriteOp::create(
739 builder, location: rewriteOp.getLoc(), results: rewriteOp.getResultTypes(),
740 name: rewriteOp.getNameAttr(), args: arguments);
741 for (auto it : llvm::zip(t: rewriteOp.getResults(), u: interpOp.getResults()))
742 rewriteValues[std::get<0>(t&: it)] = std::get<1>(t&: it);
743}
744
745void PatternLowering::generateRewriter(
746 pdl::AttributeOp attrOp, DenseMap<Value, Value> &rewriteValues,
747 function_ref<Value(Value)> mapRewriteValue) {
748 Value newAttr = pdl_interp::CreateAttributeOp::create(
749 builder, location: attrOp.getLoc(), value: attrOp.getValueAttr());
750 rewriteValues[attrOp] = newAttr;
751}
752
753void PatternLowering::generateRewriter(
754 pdl::EraseOp eraseOp, DenseMap<Value, Value> &rewriteValues,
755 function_ref<Value(Value)> mapRewriteValue) {
756 pdl_interp::EraseOp::create(builder, location: eraseOp.getLoc(),
757 inputOp: mapRewriteValue(eraseOp.getOpValue()));
758}
759
760void PatternLowering::generateRewriter(
761 pdl::OperationOp operationOp, DenseMap<Value, Value> &rewriteValues,
762 function_ref<Value(Value)> mapRewriteValue) {
763 SmallVector<Value, 4> operands;
764 for (Value operand : operationOp.getOperandValues())
765 operands.push_back(Elt: mapRewriteValue(operand));
766
767 SmallVector<Value, 4> attributes;
768 for (Value attr : operationOp.getAttributeValues())
769 attributes.push_back(Elt: mapRewriteValue(attr));
770
771 bool hasInferredResultTypes = false;
772 SmallVector<Value, 2> types;
773 generateOperationResultTypeRewriter(op: operationOp, mapRewriteValue, types,
774 rewriteValues, hasInferredResultTypes);
775
776 // Create the new operation.
777 Location loc = operationOp.getLoc();
778 Value createdOp = pdl_interp::CreateOperationOp::create(
779 builder, location: loc, name: *operationOp.getOpName(), types, inferredResultTypes: hasInferredResultTypes,
780 operands, attributes, attributeNames: operationOp.getAttributeValueNames());
781 rewriteValues[operationOp.getOp()] = createdOp;
782
783 // Generate accesses for any results that have their types constrained.
784 // Handle the case where there is a single range representing all of the
785 // result types.
786 OperandRange resultTys = operationOp.getTypeValues();
787 if (resultTys.size() == 1 && isa<pdl::RangeType>(Val: resultTys[0].getType())) {
788 Value &type = rewriteValues[resultTys[0]];
789 if (!type) {
790 auto results = pdl_interp::GetResultsOp::create(builder, location: loc, inputOp: createdOp);
791 type = pdl_interp::GetValueTypeOp::create(builder, location: loc, value: results);
792 }
793 return;
794 }
795
796 // Otherwise, populate the individual results.
797 bool seenVariableLength = false;
798 Type valueTy = builder.getType<pdl::ValueType>();
799 Type valueRangeTy = pdl::RangeType::get(elementType: valueTy);
800 for (const auto &it : llvm::enumerate(First&: resultTys)) {
801 Value &type = rewriteValues[it.value()];
802 if (type)
803 continue;
804 bool isVariadic = isa<pdl::RangeType>(Val: it.value().getType());
805 seenVariableLength |= isVariadic;
806
807 // After a variable length result has been seen, we need to use result
808 // groups because the exact index of the result is not statically known.
809 Value resultVal;
810 if (seenVariableLength)
811 resultVal = pdl_interp::GetResultsOp::create(
812 builder, location: loc, resultType: isVariadic ? valueRangeTy : valueTy, inputOp: createdOp,
813 index: it.index());
814 else
815 resultVal = pdl_interp::GetResultOp::create(builder, location: loc, value: valueTy,
816 inputOp: createdOp, index: it.index());
817 type = pdl_interp::GetValueTypeOp::create(builder, location: loc, value: resultVal);
818 }
819}
820
821void PatternLowering::generateRewriter(
822 pdl::RangeOp rangeOp, DenseMap<Value, Value> &rewriteValues,
823 function_ref<Value(Value)> mapRewriteValue) {
824 SmallVector<Value, 4> replOperands;
825 for (Value operand : rangeOp.getArguments())
826 replOperands.push_back(Elt: mapRewriteValue(operand));
827 rewriteValues[rangeOp] = pdl_interp::CreateRangeOp::create(
828 builder, location: rangeOp.getLoc(), result: rangeOp.getType(), arguments: replOperands);
829}
830
831void PatternLowering::generateRewriter(
832 pdl::ReplaceOp replaceOp, DenseMap<Value, Value> &rewriteValues,
833 function_ref<Value(Value)> mapRewriteValue) {
834 SmallVector<Value, 4> replOperands;
835
836 // If the replacement was another operation, get its results. `pdl` allows
837 // for using an operation for simplicitly, but the interpreter isn't as
838 // user facing.
839 if (Value replOp = replaceOp.getReplOperation()) {
840 // Don't use replace if we know the replaced operation has no results.
841 auto opOp = replaceOp.getOpValue().getDefiningOp<pdl::OperationOp>();
842 if (!opOp || !opOp.getTypeValues().empty()) {
843 replOperands.push_back(Elt: pdl_interp::GetResultsOp::create(
844 builder, location: replOp.getLoc(), inputOp: mapRewriteValue(replOp)));
845 }
846 } else {
847 for (Value operand : replaceOp.getReplValues())
848 replOperands.push_back(Elt: mapRewriteValue(operand));
849 }
850
851 // If there are no replacement values, just create an erase instead.
852 if (replOperands.empty()) {
853 pdl_interp::EraseOp::create(builder, location: replaceOp.getLoc(),
854 inputOp: mapRewriteValue(replaceOp.getOpValue()));
855 return;
856 }
857
858 pdl_interp::ReplaceOp::create(builder, location: replaceOp.getLoc(),
859 inputOp: mapRewriteValue(replaceOp.getOpValue()),
860 replValues: replOperands);
861}
862
863void PatternLowering::generateRewriter(
864 pdl::ResultOp resultOp, DenseMap<Value, Value> &rewriteValues,
865 function_ref<Value(Value)> mapRewriteValue) {
866 rewriteValues[resultOp] = pdl_interp::GetResultOp::create(
867 builder, location: resultOp.getLoc(), value: builder.getType<pdl::ValueType>(),
868 inputOp: mapRewriteValue(resultOp.getParent()), index: resultOp.getIndex());
869}
870
871void PatternLowering::generateRewriter(
872 pdl::ResultsOp resultOp, DenseMap<Value, Value> &rewriteValues,
873 function_ref<Value(Value)> mapRewriteValue) {
874 rewriteValues[resultOp] = pdl_interp::GetResultsOp::create(
875 builder, location: resultOp.getLoc(), resultType: resultOp.getType(),
876 inputOp: mapRewriteValue(resultOp.getParent()), index: resultOp.getIndex());
877}
878
879void PatternLowering::generateRewriter(
880 pdl::TypeOp typeOp, DenseMap<Value, Value> &rewriteValues,
881 function_ref<Value(Value)> mapRewriteValue) {
882 // If the type isn't constant, the users (e.g. OperationOp) will resolve this
883 // type.
884 if (TypeAttr typeAttr = typeOp.getConstantTypeAttr()) {
885 rewriteValues[typeOp] =
886 pdl_interp::CreateTypeOp::create(builder, location: typeOp.getLoc(), type: typeAttr);
887 }
888}
889
890void PatternLowering::generateRewriter(
891 pdl::TypesOp typeOp, DenseMap<Value, Value> &rewriteValues,
892 function_ref<Value(Value)> mapRewriteValue) {
893 // If the type isn't constant, the users (e.g. OperationOp) will resolve this
894 // type.
895 if (ArrayAttr typeAttr = typeOp.getConstantTypesAttr()) {
896 rewriteValues[typeOp] = pdl_interp::CreateTypesOp::create(
897 builder, location: typeOp.getLoc(), result: typeOp.getType(), value: typeAttr);
898 }
899}
900
901void PatternLowering::generateOperationResultTypeRewriter(
902 pdl::OperationOp op, function_ref<Value(Value)> mapRewriteValue,
903 SmallVectorImpl<Value> &types, DenseMap<Value, Value> &rewriteValues,
904 bool &hasInferredResultTypes) {
905 Block *rewriterBlock = op->getBlock();
906
907 // Try to handle resolution for each of the result types individually. This is
908 // preferred over type inferrence because it will allow for us to use existing
909 // types directly, as opposed to trying to rebuild the type list.
910 OperandRange resultTypeValues = op.getTypeValues();
911 auto tryResolveResultTypes = [&] {
912 types.reserve(N: resultTypeValues.size());
913 for (const auto &it : llvm::enumerate(First&: resultTypeValues)) {
914 Value resultType = it.value();
915
916 // Check for an already translated value.
917 if (Value existingRewriteValue = rewriteValues.lookup(Val: resultType)) {
918 types.push_back(Elt: existingRewriteValue);
919 continue;
920 }
921
922 // Check for an input from the matcher.
923 if (resultType.getDefiningOp()->getBlock() != rewriterBlock) {
924 types.push_back(Elt: mapRewriteValue(resultType));
925 continue;
926 }
927
928 // Otherwise, we couldn't infer the result types. Bail out here to see if
929 // we can infer the types for this operation from another way.
930 types.clear();
931 return failure();
932 }
933 return success();
934 };
935 if (!resultTypeValues.empty() && succeeded(Result: tryResolveResultTypes()))
936 return;
937
938 // Otherwise, check if the operation has type inference support itself.
939 if (op.hasTypeInference()) {
940 hasInferredResultTypes = true;
941 return;
942 }
943
944 // Look for an operation that was replaced by `op`. The result types will be
945 // inferred from the results that were replaced.
946 for (OpOperand &use : op.getOp().getUses()) {
947 // Check that the use corresponds to a ReplaceOp and that it is the
948 // replacement value, not the operation being replaced.
949 pdl::ReplaceOp replOpUser = dyn_cast<pdl::ReplaceOp>(Val: use.getOwner());
950 if (!replOpUser || use.getOperandNumber() == 0)
951 continue;
952 // Make sure the replaced operation was defined before this one. PDL
953 // rewrites only have single block regions, so if the op isn't in the
954 // rewriter block (i.e. the current block of the operation) we already know
955 // it dominates (i.e. it's in the matcher).
956 Value replOpVal = replOpUser.getOpValue();
957 Operation *replacedOp = replOpVal.getDefiningOp();
958 if (replacedOp->getBlock() == rewriterBlock &&
959 !replacedOp->isBeforeInBlock(other: op))
960 continue;
961
962 Value replacedOpResults = pdl_interp::GetResultsOp::create(
963 builder, location: replacedOp->getLoc(), inputOp: mapRewriteValue(replOpVal));
964 types.push_back(Elt: pdl_interp::GetValueTypeOp::create(
965 builder, location: replacedOp->getLoc(), value: replacedOpResults));
966 return;
967 }
968
969 // If the types could not be inferred from any context and there weren't any
970 // explicit result types, assume the user actually meant for the operation to
971 // have no results.
972 if (resultTypeValues.empty())
973 return;
974
975 // The verifier asserts that the result types of each pdl.getOperation can be
976 // inferred. If we reach here, there is a bug either in the logic above or
977 // in the verifier for pdl.getOperation.
978 op->emitOpError() << "unable to infer result type for operation";
979 llvm_unreachable("unable to infer result type for operation");
980}
981
982//===----------------------------------------------------------------------===//
983// Conversion Pass
984//===----------------------------------------------------------------------===//
985
986namespace {
987struct PDLToPDLInterpPass
988 : public impl::ConvertPDLToPDLInterpPassBase<PDLToPDLInterpPass> {
989 PDLToPDLInterpPass() = default;
990 PDLToPDLInterpPass(const PDLToPDLInterpPass &rhs) = default;
991 PDLToPDLInterpPass(DenseMap<Operation *, PDLPatternConfigSet *> &configMap)
992 : configMap(&configMap) {}
993 void runOnOperation() final;
994
995 /// A map containing the configuration for each pattern.
996 DenseMap<Operation *, PDLPatternConfigSet *> *configMap = nullptr;
997};
998} // namespace
999
1000/// Convert the given module containing PDL pattern operations into a PDL
1001/// Interpreter operations.
1002void PDLToPDLInterpPass::runOnOperation() {
1003 ModuleOp module = getOperation();
1004
1005 // Create the main matcher function This function contains all of the match
1006 // related functionality from patterns in the module.
1007 OpBuilder builder = OpBuilder::atBlockBegin(block: module.getBody());
1008 auto matcherFunc = pdl_interp::FuncOp::create(
1009 builder, location: module.getLoc(),
1010 name: pdl_interp::PDLInterpDialect::getMatcherFunctionName(),
1011 type: builder.getFunctionType(inputs: builder.getType<pdl::OperationType>(),
1012 /*results=*/{}),
1013 /*attrs=*/ArrayRef<NamedAttribute>());
1014
1015 // Create a nested module to hold the functions invoked for rewriting the IR
1016 // after a successful match.
1017 ModuleOp rewriterModule =
1018 ModuleOp::create(builder, location: module.getLoc(),
1019 name: pdl_interp::PDLInterpDialect::getRewriterModuleName());
1020
1021 // Generate the code for the patterns within the module.
1022 PatternLowering generator(matcherFunc, rewriterModule, configMap);
1023 generator.lower(module);
1024
1025 // After generation, delete all of the pattern operations.
1026 for (pdl::PatternOp pattern :
1027 llvm::make_early_inc_range(Range: module.getOps<pdl::PatternOp>())) {
1028 // Drop the now dead config mappings.
1029 if (configMap)
1030 configMap->erase(Val: pattern);
1031
1032 pattern.erase();
1033 }
1034}
1035
1036std::unique_ptr<OperationPass<ModuleOp>> mlir::createConvertPDLToPDLInterpPass(
1037 DenseMap<Operation *, PDLPatternConfigSet *> &configMap) {
1038 return std::make_unique<PDLToPDLInterpPass>(args&: configMap);
1039}
1040