1//===- DialectConversion.cpp - MLIR dialect conversion generic pass -------===//
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/Transforms/DialectConversion.h"
10#include "mlir/Config/mlir-config.h"
11#include "mlir/IR/Block.h"
12#include "mlir/IR/Builders.h"
13#include "mlir/IR/BuiltinOps.h"
14#include "mlir/IR/Dominance.h"
15#include "mlir/IR/IRMapping.h"
16#include "mlir/IR/Iterators.h"
17#include "mlir/IR/Operation.h"
18#include "mlir/Interfaces/FunctionInterfaces.h"
19#include "mlir/Rewrite/PatternApplicator.h"
20#include "llvm/ADT/ScopeExit.h"
21#include "llvm/ADT/SmallPtrSet.h"
22#include "llvm/Support/Debug.h"
23#include "llvm/Support/DebugLog.h"
24#include "llvm/Support/ErrorHandling.h"
25#include "llvm/Support/FormatVariadic.h"
26#include "llvm/Support/SaveAndRestore.h"
27#include "llvm/Support/ScopedPrinter.h"
28#include <optional>
29#include <utility>
30
31using namespace mlir;
32using namespace mlir::detail;
33
34#define DEBUG_TYPE "dialect-conversion"
35
36/// A utility function to log a successful result for the given reason.
37template <typename... Args>
38static void logSuccess(llvm::ScopedPrinter &os, StringRef fmt, Args &&...args) {
39 LLVM_DEBUG({
40 os.unindent();
41 os.startLine() << "} -> SUCCESS";
42 if (!fmt.empty())
43 os.getOStream() << " : "
44 << llvm::formatv(fmt.data(), std::forward<Args>(args)...);
45 os.getOStream() << "\n";
46 });
47}
48
49/// A utility function to log a failure result for the given reason.
50template <typename... Args>
51static void logFailure(llvm::ScopedPrinter &os, StringRef fmt, Args &&...args) {
52 LLVM_DEBUG({
53 os.unindent();
54 os.startLine() << "} -> FAILURE : "
55 << llvm::formatv(fmt.data(), std::forward<Args>(args)...)
56 << "\n";
57 });
58}
59
60/// Helper function that computes an insertion point where the given value is
61/// defined and can be used without a dominance violation.
62static OpBuilder::InsertPoint computeInsertPoint(Value value) {
63 Block *insertBlock = value.getParentBlock();
64 Block::iterator insertPt = insertBlock->begin();
65 if (OpResult inputRes = dyn_cast<OpResult>(Val&: value))
66 insertPt = ++inputRes.getOwner()->getIterator();
67 return OpBuilder::InsertPoint(insertBlock, insertPt);
68}
69
70/// Helper function that computes an insertion point where the given values are
71/// defined and can be used without a dominance violation.
72static OpBuilder::InsertPoint computeInsertPoint(ArrayRef<Value> vals) {
73 assert(!vals.empty() && "expected at least one value");
74 DominanceInfo domInfo;
75 OpBuilder::InsertPoint pt = computeInsertPoint(value: vals.front());
76 for (Value v : vals.drop_front()) {
77 // Choose the "later" insertion point.
78 OpBuilder::InsertPoint nextPt = computeInsertPoint(value: v);
79 if (domInfo.dominates(aBlock: pt.getBlock(), aIt: pt.getPoint(), bBlock: nextPt.getBlock(),
80 bIt: nextPt.getPoint())) {
81 // pt is before nextPt => choose nextPt.
82 pt = nextPt;
83 } else {
84#ifndef NDEBUG
85 // nextPt should be before pt => choose pt.
86 // If pt, nextPt are no dominance relationship, then there is no valid
87 // insertion point at which all given values are defined.
88 bool dom = domInfo.dominates(nextPt.getBlock(), nextPt.getPoint(),
89 pt.getBlock(), pt.getPoint());
90 assert(dom && "unable to find valid insertion point");
91#endif // NDEBUG
92 }
93 }
94 return pt;
95}
96
97namespace {
98enum OpConversionMode {
99 /// In this mode, the conversion will ignore failed conversions to allow
100 /// illegal operations to co-exist in the IR.
101 Partial,
102
103 /// In this mode, all operations must be legal for the given target for the
104 /// conversion to succeed.
105 Full,
106
107 /// In this mode, operations are analyzed for legality. No actual rewrites are
108 /// applied to the operations on success.
109 Analysis,
110};
111} // namespace
112
113//===----------------------------------------------------------------------===//
114// ConversionValueMapping
115//===----------------------------------------------------------------------===//
116
117/// A vector of SSA values, optimized for the most common case of one or two
118/// values. Inline size chosen empirically based on compilation profiling.
119/// Profiled: 2.3M calls, avg=2.0+-0.3. N=2 covers 98% of cases inline.
120using ValueVector = SmallVector<Value, 2>;
121
122namespace {
123
124/// Helper class to make it possible to use `ValueVector` as a key in DenseMap.
125struct ValueVectorMapInfo {
126 static ::llvm::hash_code getHashValue(const ValueVector &val) {
127 return ::llvm::hash_combine_range(R: val);
128 }
129 static bool isEqual(const ValueVector &LHS, const ValueVector &RHS) {
130 return LHS == RHS;
131 }
132};
133
134/// This class wraps a IRMapping to provide recursive lookup
135/// functionality, i.e. we will traverse if the mapped value also has a mapping.
136struct ConversionValueMapping {
137 /// Return "true" if an SSA value is mapped to the given value. May return
138 /// false positives.
139 bool isMappedTo(Value value) const { return mappedTo.contains(V: value); }
140
141 /// Lookup a value in the mapping.
142 ValueVector lookup(const ValueVector &from) const;
143
144 template <typename T>
145 struct IsValueVector : std::is_same<std::decay_t<T>, ValueVector> {};
146
147 /// Map a value vector to the one provided.
148 template <typename OldVal, typename NewVal>
149 std::enable_if_t<IsValueVector<OldVal>::value && IsValueVector<NewVal>::value>
150 map(OldVal &&oldVal, NewVal &&newVal) {
151 LLVM_DEBUG({
152 ValueVector next(newVal);
153 while (true) {
154 assert(next != oldVal && "inserting cyclic mapping");
155 auto it = mapping.find(next);
156 if (it == mapping.end())
157 break;
158 next = it->second;
159 }
160 });
161 mappedTo.insert_range(newVal);
162
163 mapping[std::forward<OldVal>(oldVal)] = std::forward<NewVal>(newVal);
164 }
165
166 /// Map a value vector or single value to the one provided.
167 template <typename OldVal, typename NewVal>
168 std::enable_if_t<!IsValueVector<OldVal>::value ||
169 !IsValueVector<NewVal>::value>
170 map(OldVal &&oldVal, NewVal &&newVal) {
171 if constexpr (IsValueVector<OldVal>{}) {
172 map(std::forward<OldVal>(oldVal), ValueVector{newVal});
173 } else if constexpr (IsValueVector<NewVal>{}) {
174 map(ValueVector{oldVal}, std::forward<NewVal>(newVal));
175 } else {
176 map(oldVal: ValueVector{oldVal}, newVal: ValueVector{newVal});
177 }
178 }
179
180 void map(Value oldVal, SmallVector<Value> &&newVal) {
181 map(oldVal: ValueVector{oldVal}, newVal: ValueVector(std::move(newVal)));
182 }
183
184 /// Drop the last mapping for the given values.
185 void erase(const ValueVector &value) { mapping.erase(Val: value); }
186
187private:
188 /// Current value mappings.
189 DenseMap<ValueVector, ValueVector, ValueVectorMapInfo> mapping;
190
191 /// All SSA values that are mapped to. May contain false positives.
192 DenseSet<Value> mappedTo;
193};
194} // namespace
195
196/// Marker attribute for pure type conversions. I.e., mappings whose only
197/// purpose is to resolve a type mismatch. (In contrast, mappings that point to
198/// the replacement values of a "replaceOp" call, etc., are not pure type
199/// conversions.)
200static const StringRef kPureTypeConversionMarker = "__pure_type_conversion__";
201
202/// Return the operation that defines all values in the vector. Return nullptr
203/// if the values are not defined by the same operation.
204static Operation *getCommonDefiningOp(const ValueVector &values) {
205 assert(!values.empty() && "expected non-empty value vector");
206 Operation *op = values.front().getDefiningOp();
207 for (Value v : llvm::drop_begin(RangeOrContainer: values)) {
208 if (v.getDefiningOp() != op)
209 return nullptr;
210 }
211 return op;
212}
213
214/// A vector of values is a pure type conversion if all values are defined by
215/// the same operation and the operation has the `kPureTypeConversionMarker`
216/// attribute.
217static bool isPureTypeConversion(const ValueVector &values) {
218 assert(!values.empty() && "expected non-empty value vector");
219 Operation *op = getCommonDefiningOp(values);
220 return op && op->hasDiscardableAttr(name: kPureTypeConversionMarker);
221}
222
223ValueVector ConversionValueMapping::lookup(const ValueVector &from) const {
224 auto it = mapping.find(Val: from);
225 if (it == mapping.end()) {
226 // No mapping found: The lookup stops here.
227 return {};
228 }
229 return it->second;
230}
231
232//===----------------------------------------------------------------------===//
233// Rewriter and Translation State
234//===----------------------------------------------------------------------===//
235namespace {
236/// This class contains a snapshot of the current conversion rewriter state.
237/// This is useful when saving and undoing a set of rewrites.
238struct RewriterState {
239 RewriterState(unsigned numRewrites, unsigned numIgnoredOperations,
240 unsigned numReplacedOps)
241 : numRewrites(numRewrites), numIgnoredOperations(numIgnoredOperations),
242 numReplacedOps(numReplacedOps) {}
243
244 /// The current number of rewrites performed.
245 unsigned numRewrites;
246
247 /// The current number of ignored operations.
248 unsigned numIgnoredOperations;
249
250 /// The current number of replaced ops that are scheduled for erasure.
251 unsigned numReplacedOps;
252};
253
254//===----------------------------------------------------------------------===//
255// IR rewrites
256//===----------------------------------------------------------------------===//
257
258static void notifyIRErased(RewriterBase::Listener *listener, Operation &op);
259
260/// Notify the listener that the given block and its contents are being erased.
261static void notifyIRErased(RewriterBase::Listener *listener, Block &b) {
262 for (Operation &op : b)
263 notifyIRErased(listener, op);
264 listener->notifyBlockErased(block: &b);
265}
266
267/// Notify the listener that the given operation and its contents are being
268/// erased.
269static void notifyIRErased(RewriterBase::Listener *listener, Operation &op) {
270 for (Region &r : op.getRegions()) {
271 for (Block &b : r) {
272 notifyIRErased(listener, b);
273 }
274 }
275 listener->notifyOperationErased(op: &op);
276}
277
278/// An IR rewrite that can be committed (upon success) or rolled back (upon
279/// failure).
280///
281/// The dialect conversion keeps track of IR modifications (requested by the
282/// user through the rewriter API) in `IRRewrite` objects. Some kind of rewrites
283/// are directly applied to the IR as the rewriter API is used, some are applied
284/// partially, and some are delayed until the `IRRewrite` objects are committed.
285class IRRewrite {
286public:
287 /// The kind of the rewrite. Rewrites can be undone if the conversion fails.
288 /// Enum values are ordered, so that they can be used in `classof`: first all
289 /// block rewrites, then all operation rewrites.
290 enum class Kind {
291 // Block rewrites
292 CreateBlock,
293 EraseBlock,
294 InlineBlock,
295 MoveBlock,
296 BlockTypeConversion,
297 // Operation rewrites
298 MoveOperation,
299 ModifyOperation,
300 ReplaceOperation,
301 CreateOperation,
302 UnresolvedMaterialization,
303 // Value rewrites
304 ReplaceValue
305 };
306
307 virtual ~IRRewrite() = default;
308
309 /// Roll back the rewrite. Operations may be erased during rollback.
310 virtual void rollback() = 0;
311
312 /// Commit the rewrite. At this point, it is certain that the dialect
313 /// conversion will succeed. All IR modifications, except for operation/block
314 /// erasure, must be performed through the given rewriter.
315 ///
316 /// Instead of erasing operations/blocks, they should merely be unlinked
317 /// commit phase and finally be erased during the cleanup phase. This is
318 /// because internal dialect conversion state (such as `mapping`) may still
319 /// be using them.
320 ///
321 /// Any IR modification that was already performed before the commit phase
322 /// (e.g., insertion of an op) must be communicated to the listener that may
323 /// be attached to the given rewriter.
324 virtual void commit(RewriterBase &rewriter) {}
325
326 /// Cleanup operations/blocks. Cleanup is called after commit.
327 virtual void cleanup(RewriterBase &rewriter) {}
328
329 Kind getKind() const { return kind; }
330
331 static bool classof(const IRRewrite *rewrite) { return true; }
332
333protected:
334 IRRewrite(Kind kind, ConversionPatternRewriterImpl &rewriterImpl)
335 : kind(kind), rewriterImpl(rewriterImpl) {}
336
337 const ConversionConfig &getConfig() const;
338
339 const Kind kind;
340 ConversionPatternRewriterImpl &rewriterImpl;
341};
342
343/// A block rewrite.
344class BlockRewrite : public IRRewrite {
345public:
346 /// Return the block that this rewrite operates on.
347 Block *getBlock() const { return block; }
348
349 static bool classof(const IRRewrite *rewrite) {
350 return rewrite->getKind() >= Kind::CreateBlock &&
351 rewrite->getKind() <= Kind::BlockTypeConversion;
352 }
353
354protected:
355 BlockRewrite(Kind kind, ConversionPatternRewriterImpl &rewriterImpl,
356 Block *block)
357 : IRRewrite(kind, rewriterImpl), block(block) {}
358
359 // The block that this rewrite operates on.
360 Block *block;
361};
362
363/// A value rewrite.
364class ValueRewrite : public IRRewrite {
365public:
366 /// Return the value that this rewrite operates on.
367 Value getValue() const { return value; }
368
369 static bool classof(const IRRewrite *rewrite) {
370 return rewrite->getKind() == Kind::ReplaceValue;
371 }
372
373protected:
374 ValueRewrite(Kind kind, ConversionPatternRewriterImpl &rewriterImpl,
375 Value value)
376 : IRRewrite(kind, rewriterImpl), value(value) {}
377
378 // The value that this rewrite operates on.
379 Value value;
380};
381
382/// Creation of a block. Block creations are immediately reflected in the IR.
383/// There is no extra work to commit the rewrite. During rollback, the newly
384/// created block is erased.
385class CreateBlockRewrite : public BlockRewrite {
386public:
387 CreateBlockRewrite(ConversionPatternRewriterImpl &rewriterImpl, Block *block)
388 : BlockRewrite(Kind::CreateBlock, rewriterImpl, block) {}
389
390 static bool classof(const IRRewrite *rewrite) {
391 return rewrite->getKind() == Kind::CreateBlock;
392 }
393
394 void commit(RewriterBase &rewriter) override {
395 // The block was already created and inserted. Just inform the listener.
396 if (auto *listener = rewriter.getListener())
397 listener->notifyBlockInserted(block, /*previous=*/{}, /*previousIt=*/{});
398 }
399
400 void rollback() override {
401 // Unlink all of the operations within this block, they will be deleted
402 // separately.
403 auto &blockOps = block->getOperations();
404 while (!blockOps.empty())
405 blockOps.remove(IT: blockOps.begin());
406 block->dropAllUses();
407 if (block->getParent())
408 block->erase();
409 else
410 delete block;
411 }
412};
413
414/// Erasure of a block. Block erasures are partially reflected in the IR. Erased
415/// blocks are immediately unlinked, but only erased during cleanup. This makes
416/// it easier to rollback a block erasure: the block is simply inserted into its
417/// original location.
418class EraseBlockRewrite : public BlockRewrite {
419public:
420 EraseBlockRewrite(ConversionPatternRewriterImpl &rewriterImpl, Block *block)
421 : BlockRewrite(Kind::EraseBlock, rewriterImpl, block),
422 region(block->getParent()), insertBeforeBlock(block->getNextNode()) {}
423
424 static bool classof(const IRRewrite *rewrite) {
425 return rewrite->getKind() == Kind::EraseBlock;
426 }
427
428 ~EraseBlockRewrite() override {
429 assert(!block &&
430 "rewrite was neither rolled back nor committed/cleaned up");
431 }
432
433 void rollback() override {
434 // The block (owned by this rewrite) was not actually erased yet. It was
435 // just unlinked. Put it back into its original position.
436 assert(block && "expected block");
437 auto &blockList = region->getBlocks();
438 Region::iterator before = insertBeforeBlock
439 ? Region::iterator(insertBeforeBlock)
440 : blockList.end();
441 blockList.insert(where: before, New: block);
442 block = nullptr;
443 }
444
445 void commit(RewriterBase &rewriter) override {
446 assert(block && "expected block");
447
448 // Notify the listener that the block and its contents are being erased.
449 if (auto *listener =
450 dyn_cast_or_null<RewriterBase::Listener>(Val: rewriter.getListener()))
451 notifyIRErased(listener, b&: *block);
452 }
453
454 void cleanup(RewriterBase &rewriter) override {
455 // Erase the contents of the block.
456 for (auto &op : llvm::make_early_inc_range(Range: llvm::reverse(C&: *block)))
457 rewriter.eraseOp(op: &op);
458 assert(block->empty() && "expected empty block");
459
460 // Erase the block.
461 block->dropAllDefinedValueUses();
462 delete block;
463 block = nullptr;
464 }
465
466private:
467 // The region in which this block was previously contained.
468 Region *region;
469
470 // The original successor of this block before it was unlinked. "nullptr" if
471 // this block was the only block in the region.
472 Block *insertBeforeBlock;
473};
474
475/// Inlining of a block. This rewrite is immediately reflected in the IR.
476/// Note: This rewrite represents only the inlining of the operations. The
477/// erasure of the inlined block is a separate rewrite.
478class InlineBlockRewrite : public BlockRewrite {
479public:
480 InlineBlockRewrite(ConversionPatternRewriterImpl &rewriterImpl, Block *block,
481 Block *sourceBlock, Block::iterator before)
482 : BlockRewrite(Kind::InlineBlock, rewriterImpl, block),
483 sourceBlock(sourceBlock),
484 firstInlinedInst(sourceBlock->empty() ? nullptr
485 : &sourceBlock->front()),
486 lastInlinedInst(sourceBlock->empty() ? nullptr : &sourceBlock->back()) {
487 // If a listener is attached to the dialect conversion, ops must be moved
488 // one-by-one. When they are moved in bulk, notifications cannot be sent
489 // because the ops that used to be in the source block at the time of the
490 // inlining (before the "commit" phase) are unknown at the time when
491 // notifications are sent (which is during the "commit" phase).
492 assert(!getConfig().listener &&
493 "InlineBlockRewrite not supported if listener is attached");
494 }
495
496 static bool classof(const IRRewrite *rewrite) {
497 return rewrite->getKind() == Kind::InlineBlock;
498 }
499
500 void rollback() override {
501 // Put the operations from the destination block (owned by the rewrite)
502 // back into the source block.
503 if (firstInlinedInst) {
504 assert(lastInlinedInst && "expected operation");
505 sourceBlock->getOperations().splice(where: sourceBlock->begin(),
506 L2&: block->getOperations(),
507 first: Block::iterator(firstInlinedInst),
508 last: ++Block::iterator(lastInlinedInst));
509 }
510 }
511
512private:
513 // The block that originally contained the operations.
514 Block *sourceBlock;
515
516 // The first inlined operation.
517 Operation *firstInlinedInst;
518
519 // The last inlined operation.
520 Operation *lastInlinedInst;
521};
522
523/// Moving of a block. This rewrite is immediately reflected in the IR.
524class MoveBlockRewrite : public BlockRewrite {
525public:
526 MoveBlockRewrite(ConversionPatternRewriterImpl &rewriterImpl, Block *block,
527 Region *previousRegion, Region::iterator previousIt)
528 : BlockRewrite(Kind::MoveBlock, rewriterImpl, block),
529 region(previousRegion),
530 insertBeforeBlock(previousIt == previousRegion->end() ? nullptr
531 : &*previousIt) {}
532
533 static bool classof(const IRRewrite *rewrite) {
534 return rewrite->getKind() == Kind::MoveBlock;
535 }
536
537 void commit(RewriterBase &rewriter) override {
538 // The block was already moved. Just inform the listener.
539 if (auto *listener = rewriter.getListener()) {
540 // Note: `previousIt` cannot be passed because this is a delayed
541 // notification and iterators into past IR state cannot be represented.
542 listener->notifyBlockInserted(block, /*previous=*/region,
543 /*previousIt=*/{});
544 }
545 }
546
547 void rollback() override {
548 // Move the block back to its original position.
549 Region::iterator before =
550 insertBeforeBlock ? Region::iterator(insertBeforeBlock) : region->end();
551 if (Region *currentParent = block->getParent()) {
552 // Block is still in a region, use cheap splice to move it back.
553 region->getBlocks().splice(where: before, L2&: currentParent->getBlocks(), N: block);
554 return;
555 }
556 // Block was orphaned by a prior rollback, can't splice.
557 region->getBlocks().insert(where: before, New: block);
558 }
559
560private:
561 // The region in which this block was previously contained.
562 Region *region;
563
564 // The original successor of this block before it was moved. "nullptr" if
565 // this block was the only block in the region.
566 Block *insertBeforeBlock;
567};
568
569/// Block type conversion. This rewrite is partially reflected in the IR.
570class BlockTypeConversionRewrite : public BlockRewrite {
571public:
572 BlockTypeConversionRewrite(ConversionPatternRewriterImpl &rewriterImpl,
573 Block *origBlock, Block *newBlock)
574 : BlockRewrite(Kind::BlockTypeConversion, rewriterImpl, origBlock),
575 newBlock(newBlock) {}
576
577 static bool classof(const IRRewrite *rewrite) {
578 return rewrite->getKind() == Kind::BlockTypeConversion;
579 }
580
581 Block *getOrigBlock() const { return block; }
582
583 Block *getNewBlock() const { return newBlock; }
584
585 void commit(RewriterBase &rewriter) override;
586
587 void rollback() override;
588
589private:
590 /// The new block that was created as part of this signature conversion.
591 Block *newBlock;
592};
593
594/// Replacing a value. This rewrite is not immediately reflected in the
595/// IR. An internal IR mapping is updated, but the actual replacement is delayed
596/// until the rewrite is committed.
597class ReplaceValueRewrite : public ValueRewrite {
598public:
599 ReplaceValueRewrite(ConversionPatternRewriterImpl &rewriterImpl, Value value,
600 const TypeConverter *converter)
601 : ValueRewrite(Kind::ReplaceValue, rewriterImpl, value),
602 converter(converter) {}
603
604 static bool classof(const IRRewrite *rewrite) {
605 return rewrite->getKind() == Kind::ReplaceValue;
606 }
607
608 void commit(RewriterBase &rewriter) override;
609
610 void rollback() override;
611
612private:
613 /// The current type converter when the value was replaced.
614 const TypeConverter *converter;
615};
616
617/// An operation rewrite.
618class OperationRewrite : public IRRewrite {
619public:
620 /// Return the operation that this rewrite operates on.
621 Operation *getOperation() const { return op; }
622
623 static bool classof(const IRRewrite *rewrite) {
624 return rewrite->getKind() >= Kind::MoveOperation &&
625 rewrite->getKind() <= Kind::UnresolvedMaterialization;
626 }
627
628protected:
629 OperationRewrite(Kind kind, ConversionPatternRewriterImpl &rewriterImpl,
630 Operation *op)
631 : IRRewrite(kind, rewriterImpl), op(op) {}
632
633 // The operation that this rewrite operates on.
634 Operation *op;
635};
636
637/// Moving of an operation. This rewrite is immediately reflected in the IR.
638class MoveOperationRewrite : public OperationRewrite {
639public:
640 MoveOperationRewrite(ConversionPatternRewriterImpl &rewriterImpl,
641 Operation *op, OpBuilder::InsertPoint previous)
642 : OperationRewrite(Kind::MoveOperation, rewriterImpl, op),
643 block(previous.getBlock()),
644 insertBeforeOp(previous.getPoint() == previous.getBlock()->end()
645 ? nullptr
646 : &*previous.getPoint()) {}
647
648 static bool classof(const IRRewrite *rewrite) {
649 return rewrite->getKind() == Kind::MoveOperation;
650 }
651
652 void commit(RewriterBase &rewriter) override {
653 // The operation was already moved. Just inform the listener.
654 if (auto *listener = rewriter.getListener()) {
655 // Note: `previousIt` cannot be passed because this is a delayed
656 // notification and iterators into past IR state cannot be represented.
657 listener->notifyOperationInserted(
658 op, /*previous=*/OpBuilder::InsertPoint(/*insertBlock=*/block,
659 /*insertPt=*/{}));
660 }
661 }
662
663 void rollback() override {
664 // Move the operation back to its original position.
665 Block::iterator before =
666 insertBeforeOp ? Block::iterator(insertBeforeOp) : block->end();
667 block->getOperations().splice(where: before, L2&: op->getBlock()->getOperations(), N: op);
668 }
669
670private:
671 // The block in which this operation was previously contained.
672 Block *block;
673
674 // The original successor of this operation before it was moved. "nullptr"
675 // if this operation was the only operation in the region.
676 Operation *insertBeforeOp;
677};
678
679/// In-place modification of an op. This rewrite is immediately reflected in
680/// the IR. The previous state of the operation is stored in this object.
681class ModifyOperationRewrite : public OperationRewrite {
682public:
683 ModifyOperationRewrite(ConversionPatternRewriterImpl &rewriterImpl,
684 Operation *op)
685 : OperationRewrite(Kind::ModifyOperation, rewriterImpl, op),
686 name(op->getName()), loc(op->getLoc()),
687 attrs(op->getDiscardableAttrDictionary()),
688 operands(op->operand_begin(), op->operand_end()),
689 successors(op->successor_begin(), op->successor_end()) {
690 if (PropertyRef prop = op->getPropertiesStorage()) {
691 // Make a copy of the properties.
692 propertiesStorage = operator new(op->getPropertiesStorageSize());
693 PropertyRef propCopy(name.getOpPropertiesTypeID(), propertiesStorage);
694 name.initOpProperties(storage: propCopy, /*init=*/prop);
695 }
696 }
697
698 static bool classof(const IRRewrite *rewrite) {
699 return rewrite->getKind() == Kind::ModifyOperation;
700 }
701
702 ~ModifyOperationRewrite() override {
703 assert(!propertiesStorage &&
704 "rewrite was neither committed nor rolled back");
705 }
706
707 void commit(RewriterBase &rewriter) override {
708 // Notify the listener that the operation was modified in-place.
709 if (auto *listener =
710 dyn_cast_or_null<RewriterBase::Listener>(Val: rewriter.getListener()))
711 listener->notifyOperationModified(op);
712
713 if (propertiesStorage) {
714 PropertyRef propCopy(name.getOpPropertiesTypeID(), propertiesStorage);
715 // Note: The operation may have been erased in the mean time, so
716 // OperationName must be stored in this object.
717 name.destroyOpProperties(properties: propCopy);
718 operator delete(propertiesStorage);
719 propertiesStorage = nullptr;
720 }
721 }
722
723 void rollback() override {
724 op->setLoc(loc);
725 op->setDiscardableAttrs(attrs);
726 op->setOperands(operands);
727 for (const auto &it : llvm::enumerate(First&: successors))
728 op->setSuccessor(block: it.value(), index: it.index());
729 if (propertiesStorage) {
730 PropertyRef propCopy(name.getOpPropertiesTypeID(), propertiesStorage);
731 op->copyProperties(rhs: propCopy);
732 name.destroyOpProperties(properties: propCopy);
733 operator delete(propertiesStorage);
734 propertiesStorage = nullptr;
735 }
736 }
737
738private:
739 OperationName name;
740 LocationAttr loc;
741 DictionaryAttr attrs;
742 SmallVector<Value, 8> operands;
743 SmallVector<Block *, 2> successors;
744 void *propertiesStorage = nullptr;
745};
746
747/// Replacing an operation. Erasing an operation is treated as a special case
748/// with "null" replacements. This rewrite is not immediately reflected in the
749/// IR. An internal IR mapping is updated, but values are not replaced and the
750/// original op is not erased until the rewrite is committed.
751class ReplaceOperationRewrite : public OperationRewrite {
752public:
753 ReplaceOperationRewrite(ConversionPatternRewriterImpl &rewriterImpl,
754 Operation *op, const TypeConverter *converter)
755 : OperationRewrite(Kind::ReplaceOperation, rewriterImpl, op),
756 converter(converter) {}
757
758 static bool classof(const IRRewrite *rewrite) {
759 return rewrite->getKind() == Kind::ReplaceOperation;
760 }
761
762 void commit(RewriterBase &rewriter) override;
763
764 void rollback() override;
765
766 void cleanup(RewriterBase &rewriter) override;
767
768private:
769 /// An optional type converter that can be used to materialize conversions
770 /// between the new and old values if necessary.
771 const TypeConverter *converter;
772};
773
774class CreateOperationRewrite : public OperationRewrite {
775public:
776 CreateOperationRewrite(ConversionPatternRewriterImpl &rewriterImpl,
777 Operation *op)
778 : OperationRewrite(Kind::CreateOperation, rewriterImpl, op) {}
779
780 static bool classof(const IRRewrite *rewrite) {
781 return rewrite->getKind() == Kind::CreateOperation;
782 }
783
784 void commit(RewriterBase &rewriter) override {
785 // The operation was already created and inserted. Just inform the listener.
786 if (auto *listener = rewriter.getListener())
787 listener->notifyOperationInserted(op, /*previous=*/{});
788 }
789
790 void rollback() override;
791};
792
793/// The type of materialization.
794enum MaterializationKind {
795 /// This materialization materializes a conversion from an illegal type to a
796 /// legal one.
797 Target,
798
799 /// This materialization materializes a conversion from a legal type back to
800 /// an illegal one.
801 Source
802};
803
804/// Helper class that stores metadata about an unresolved materialization.
805class UnresolvedMaterializationInfo {
806public:
807 UnresolvedMaterializationInfo() = default;
808 UnresolvedMaterializationInfo(const TypeConverter *converter,
809 MaterializationKind kind, Type originalType)
810 : converterAndKind(converter, kind), originalType(originalType) {}
811
812 /// Return the type converter of this materialization (which may be null).
813 const TypeConverter *getConverter() const {
814 return converterAndKind.getPointer();
815 }
816
817 /// Return the kind of this materialization.
818 MaterializationKind getMaterializationKind() const {
819 return converterAndKind.getInt();
820 }
821
822 /// Return the original type of the SSA value.
823 Type getOriginalType() const { return originalType; }
824
825private:
826 /// The corresponding type converter to use when resolving this
827 /// materialization, and the kind of this materialization.
828 llvm::PointerIntPair<const TypeConverter *, 2, MaterializationKind>
829 converterAndKind;
830
831 /// The original type of the SSA value. Only used for target
832 /// materializations.
833 Type originalType;
834};
835
836/// An unresolved materialization, i.e., a "builtin.unrealized_conversion_cast"
837/// op. Unresolved materializations fold away or are replaced with
838/// source/target materializations at the end of the dialect conversion.
839class UnresolvedMaterializationRewrite : public OperationRewrite {
840public:
841 UnresolvedMaterializationRewrite(ConversionPatternRewriterImpl &rewriterImpl,
842 UnrealizedConversionCastOp op,
843 ValueVector mappedValues)
844 : OperationRewrite(Kind::UnresolvedMaterialization, rewriterImpl, op),
845 mappedValues(std::move(mappedValues)) {}
846
847 static bool classof(const IRRewrite *rewrite) {
848 return rewrite->getKind() == Kind::UnresolvedMaterialization;
849 }
850
851 void rollback() override;
852
853 UnrealizedConversionCastOp getOperation() const {
854 return cast<UnrealizedConversionCastOp>(Val: op);
855 }
856
857private:
858 /// The values in the conversion value mapping that are being replaced by the
859 /// results of this unresolved materialization.
860 ValueVector mappedValues;
861};
862} // namespace
863
864#if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS
865/// Return "true" if there is an operation rewrite that matches the specified
866/// rewrite type and operation among the given rewrites.
867template <typename RewriteTy, typename R>
868static bool hasRewrite(R &&rewrites, Operation *op) {
869 return any_of(std::forward<R>(rewrites), [&](auto &rewrite) {
870 auto *rewriteTy = dyn_cast<RewriteTy>(rewrite.get());
871 return rewriteTy && rewriteTy->getOperation() == op;
872 });
873}
874
875/// Return "true" if there is a block rewrite that matches the specified
876/// rewrite type and block among the given rewrites.
877template <typename RewriteTy, typename R>
878static bool hasRewrite(R &&rewrites, Block *block) {
879 return any_of(std::forward<R>(rewrites), [&](auto &rewrite) {
880 auto *rewriteTy = dyn_cast<RewriteTy>(rewrite.get());
881 return rewriteTy && rewriteTy->getBlock() == block;
882 });
883}
884#endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS
885
886//===----------------------------------------------------------------------===//
887// ConversionPatternRewriterImpl
888//===----------------------------------------------------------------------===//
889namespace mlir {
890namespace detail {
891struct ConversionPatternRewriterImpl : public RewriterBase::Listener {
892 explicit ConversionPatternRewriterImpl(ConversionPatternRewriter &rewriter,
893 const ConversionConfig &config,
894 OperationConverter &opConverter)
895 : rewriter(rewriter), config(config), opConverter(opConverter),
896 notifyingRewriter(rewriter.getContext(), config.listener) {}
897
898 //===--------------------------------------------------------------------===//
899 // State Management
900 //===--------------------------------------------------------------------===//
901
902 /// Return the current state of the rewriter.
903 RewriterState getCurrentState();
904
905 /// Apply all requested operation rewrites. This method is invoked when the
906 /// conversion process succeeds.
907 void applyRewrites();
908
909 /// Reset the state of the rewriter to a previously saved point. Optionally,
910 /// the name of the pattern that triggered the rollback can specified for
911 /// debugging purposes.
912 void resetState(RewriterState state, StringRef patternName = "");
913
914 /// Append a rewrite. Rewrites are committed upon success and rolled back upon
915 /// failure.
916 template <typename RewriteTy, typename... Args>
917 void appendRewrite(Args &&...args) {
918 assert(config.allowPatternRollback && "appending rewrites is not allowed");
919 rewrites.push_back(
920 std::make_unique<RewriteTy>(*this, std::forward<Args>(args)...));
921 }
922
923 /// Undo the rewrites (motions, splits) one by one in reverse order until
924 /// "numRewritesToKeep" rewrites remains. Optionally, the name of the pattern
925 /// that triggered the rollback can specified for debugging purposes.
926 void undoRewrites(unsigned numRewritesToKeep = 0, StringRef patternName = "");
927
928 /// Remap the given values to those with potentially different types. Returns
929 /// success if the values could be remapped, failure otherwise. `valueDiagTag`
930 /// is the tag used when describing a value within a diagnostic, e.g.
931 /// "operand".
932 LogicalResult remapValues(StringRef valueDiagTag,
933 std::optional<Location> inputLoc, ValueRange values,
934 SmallVector<ValueVector> &remapped);
935
936 /// Return "true" if the given operation is ignored, and does not need to be
937 /// converted.
938 bool isOpIgnored(Operation *op) const;
939
940 /// Return "true" if the given operation was replaced or erased.
941 bool wasOpReplaced(Operation *op) const;
942
943 /// Lookup the most recently mapped values with the desired types in the
944 /// mapping, taking into account only replacements. Perform a best-effort
945 /// search for existing materializations with the desired types.
946 ///
947 /// If `skipPureTypeConversions` is "true", materializations that are pure
948 /// type conversions are not considered.
949 ValueVector lookupOrDefault(Value from, TypeRange desiredTypes = {},
950 bool skipPureTypeConversions = false) const;
951
952 /// Lookup the given value within the map, or return an empty vector if the
953 /// value is not mapped. If it is mapped, this follows the same behavior
954 /// as `lookupOrDefault`.
955 ValueVector lookupOrNull(Value from, TypeRange desiredTypes = {}) const;
956
957 //===--------------------------------------------------------------------===//
958 // IR Rewrites / Type Conversion
959 //===--------------------------------------------------------------------===//
960
961 /// Convert the types of block arguments within the given region.
962 FailureOr<Block *>
963 convertRegionTypes(Region *region, const TypeConverter &converter,
964 TypeConverter::SignatureConversion *entryConversion);
965
966 /// Apply the given signature conversion on the given block. The new block
967 /// containing the updated signature is returned. If no conversions were
968 /// necessary, e.g. if the block has no arguments, `block` is returned.
969 /// `converter` is used to generate any necessary cast operations that
970 /// translate between the origin argument types and those specified in the
971 /// signature conversion.
972 Block *applySignatureConversion(
973 Block *block, const TypeConverter *converter,
974 TypeConverter::SignatureConversion &signatureConversion);
975
976 /// Replace the results of the given operation with the given values and
977 /// erase the operation.
978 ///
979 /// There can be multiple replacement values for each result (1:N
980 /// replacement). If the replacement values are empty, the respective result
981 /// is dropped and a source materialization is built if the result still has
982 /// uses.
983 void replaceOp(Operation *op, SmallVector<SmallVector<Value>> &&newValues);
984
985 /// Replace the uses of the given value with the given values. The specified
986 /// converter is used to build materializations (if necessary). If `functor`
987 /// is specified, only the uses that the functor returns "true" for are
988 /// replaced.
989 void replaceValueUses(Value from, ValueRange to,
990 const TypeConverter *converter,
991 function_ref<bool(OpOperand &)> functor = nullptr);
992
993 /// Erase the given block and its contents.
994 void eraseBlock(Block *block);
995
996 /// Inline the source block into the destination block before the given
997 /// iterator.
998 void inlineBlockBefore(Block *source, Block *dest, Block::iterator before);
999
1000 //===--------------------------------------------------------------------===//
1001 // Materializations
1002 //===--------------------------------------------------------------------===//
1003
1004 /// Build an unresolved materialization operation given a range of output
1005 /// types and a list of input operands. Returns the inputs if they their
1006 /// types match the output types.
1007 ///
1008 /// If a cast op was built, it can optionally be returned with the `castOp`
1009 /// output argument.
1010 ///
1011 /// If `valuesToMap` is set to a non-null Value, then that value is mapped to
1012 /// the results of the unresolved materialization in the conversion value
1013 /// mapping.
1014 ///
1015 /// If `isPureTypeConversion` is "true", the materialization is created only
1016 /// to resolve a type mismatch. That means it is not a regular value
1017 /// replacement issued by the user. (Replacement values that are created
1018 /// "out of thin air" appear like unresolved materializations because they are
1019 /// unrealized_conversion_cast ops. However, they must be treated like
1020 /// regular value replacements.)
1021 ValueRange buildUnresolvedMaterialization(
1022 MaterializationKind kind, OpBuilder::InsertPoint ip, Location loc,
1023 ValueVector valuesToMap, ValueRange inputs, TypeRange outputTypes,
1024 Type originalType, const TypeConverter *converter,
1025 bool isPureTypeConversion = true);
1026
1027 /// Find a replacement value for the given SSA value in the conversion value
1028 /// mapping. The replacement value must have the same type as the given SSA
1029 /// value. If there is no replacement value with the correct type, find the
1030 /// latest replacement value (regardless of the type) and build a source
1031 /// materialization.
1032 Value findOrBuildReplacementValue(Value value,
1033 const TypeConverter *converter);
1034
1035 //===--------------------------------------------------------------------===//
1036 // Rewriter Notification Hooks
1037 //===--------------------------------------------------------------------===//
1038
1039 //// Notifies that an op was inserted.
1040 void notifyOperationInserted(Operation *op,
1041 OpBuilder::InsertPoint previous) override;
1042
1043 /// Notifies that a block was inserted.
1044 void notifyBlockInserted(Block *block, Region *previous,
1045 Region::iterator previousIt) override;
1046
1047 /// Notifies that a pattern match failed for the given reason.
1048 void
1049 notifyMatchFailure(Location loc,
1050 function_ref<void(Diagnostic &)> reasonCallback) override;
1051
1052 //===--------------------------------------------------------------------===//
1053 // IR Erasure
1054 //===--------------------------------------------------------------------===//
1055
1056 /// A rewriter that keeps track of erased ops and blocks. It ensures that no
1057 /// operation or block is erased multiple times. This rewriter assumes that
1058 /// no new IR is created between calls to `eraseOp`/`eraseBlock`.
1059 struct SingleEraseRewriter : public RewriterBase, RewriterBase::Listener {
1060 public:
1061 SingleEraseRewriter(
1062 MLIRContext *context,
1063 std::function<void(Operation *)> opErasedCallback = nullptr)
1064 : RewriterBase(context, /*listener=*/this),
1065 opErasedCallback(std::move(opErasedCallback)) {}
1066
1067 /// Erase the given op (unless it was already erased).
1068 void eraseOp(Operation *op) override {
1069 if (wasErased(ptr: op))
1070 return;
1071 op->dropAllUses();
1072 RewriterBase::eraseOp(op);
1073 }
1074
1075 /// Erase the given block (unless it was already erased).
1076 void eraseBlock(Block *block) override {
1077 if (wasErased(ptr: block))
1078 return;
1079 assert(block->empty() && "expected empty block");
1080 block->dropAllDefinedValueUses();
1081 RewriterBase::eraseBlock(block);
1082 }
1083
1084 bool wasErased(void *ptr) const { return erased.contains(V: ptr); }
1085
1086 void notifyOperationErased(Operation *op) override {
1087 erased.insert(V: op);
1088 if (opErasedCallback)
1089 opErasedCallback(op);
1090 }
1091
1092 void notifyBlockErased(Block *block) override { erased.insert(V: block); }
1093
1094 private:
1095 /// Pointers to all erased operations and blocks.
1096 DenseSet<void *> erased;
1097
1098 /// A callback that is invoked when an operation is erased.
1099 std::function<void(Operation *)> opErasedCallback;
1100 };
1101
1102 //===--------------------------------------------------------------------===//
1103 // State
1104 //===--------------------------------------------------------------------===//
1105
1106 /// The rewriter that is used to perform the conversion.
1107 ConversionPatternRewriter &rewriter;
1108
1109 // Mapping between replaced values that differ in type. This happens when
1110 // replacing a value with one of a different type.
1111 ConversionValueMapping mapping;
1112
1113 /// Ordered list of block operations (creations, splits, motions).
1114 /// This vector is maintained only if `allowPatternRollback` is set to
1115 /// "true". Otherwise, all IR rewrites are materialized immediately and no
1116 /// bookkeeping is needed.
1117 SmallVector<std::unique_ptr<IRRewrite>> rewrites;
1118
1119 /// A set of operations that should no longer be considered for legalization.
1120 /// E.g., ops that are recursively legal. Ops that were replaced/erased are
1121 /// tracked separately.
1122 SetVector<Operation *> ignoredOps;
1123
1124 /// A set of operations that were replaced/erased. Such ops are not erased
1125 /// immediately but only when the dialect conversion succeeds. In the mean
1126 /// time, they should no longer be considered for legalization and any attempt
1127 /// to modify/access them is invalid rewriter API usage.
1128 SetVector<Operation *> replacedOps;
1129
1130 /// A set of operations that were created by the current pattern.
1131 SetVector<Operation *> patternNewOps;
1132
1133 /// A set of operations that were modified by the current pattern.
1134 SetVector<Operation *> patternModifiedOps;
1135
1136 /// A list of unresolved materializations that were created by the current
1137 /// pattern.
1138 DenseSet<UnrealizedConversionCastOp> patternMaterializations;
1139
1140 /// A mapping for looking up metadata of unresolved materializations.
1141 llvm::MapVector<UnrealizedConversionCastOp, UnresolvedMaterializationInfo>
1142 unresolvedMaterializations;
1143
1144 /// The current type converter, or nullptr if no type converter is currently
1145 /// active.
1146 const TypeConverter *currentTypeConverter = nullptr;
1147
1148 /// A mapping of regions to type converters that should be used when
1149 /// converting the arguments of blocks within that region.
1150 DenseMap<Region *, const TypeConverter *> regionToConverter;
1151
1152 /// Dialect conversion configuration.
1153 const ConversionConfig &config;
1154
1155 /// The operation converter to use for recursive legalization.
1156 OperationConverter &opConverter;
1157
1158 /// A set of erased operations. This set is utilized only if
1159 /// `allowPatternRollback` is set to "false". Conceptually, this set is
1160 /// similar to `replacedOps` (which is maintained when the flag is set to
1161 /// "true"). However, erasing from a DenseSet is more efficient than erasing
1162 /// from a SetVector.
1163 DenseSet<Operation *> erasedOps;
1164
1165 /// A set of erased blocks. This set is utilized only if
1166 /// `allowPatternRollback` is set to "false".
1167 DenseSet<Block *> erasedBlocks;
1168
1169 /// A rewriter that notifies the listener (if any) about all IR
1170 /// modifications. This rewriter is utilized only if `allowPatternRollback`
1171 /// is set to "false". If the flag is set to "true", the listener is notified
1172 /// with a separate mechanism (e.g., in `IRRewrite::commit`).
1173 IRRewriter notifyingRewriter;
1174
1175#ifndef NDEBUG
1176 /// A set of replaced values. This set is for debugging purposes only and it
1177 /// is maintained only if `allowPatternRollback` is set to "true".
1178 DenseSet<Value> replacedValues;
1179
1180 /// A set of operations that have pending updates. This tracking isn't
1181 /// strictly necessary, and is thus only active during debug builds for extra
1182 /// verification.
1183 SmallPtrSet<Operation *, 1> pendingRootUpdates;
1184
1185 /// A raw output stream used to prefix the debug log.
1186 llvm::impl::raw_ldbg_ostream os{(Twine("[") + DEBUG_TYPE + ":1] ").str(),
1187 llvm::dbgs()};
1188
1189 /// A logger used to emit diagnostics during the conversion process.
1190 llvm::ScopedPrinter logger{os};
1191 std::string logPrefix;
1192#endif
1193};
1194} // namespace detail
1195} // namespace mlir
1196
1197const ConversionConfig &IRRewrite::getConfig() const {
1198 return rewriterImpl.config;
1199}
1200
1201void BlockTypeConversionRewrite::commit(RewriterBase &rewriter) {
1202 // Inform the listener about all IR modifications that have already taken
1203 // place: References to the original block have been replaced with the new
1204 // block.
1205 if (auto *listener =
1206 dyn_cast_or_null<RewriterBase::Listener>(Val: rewriter.getListener()))
1207 for (Operation *op : getNewBlock()->getUsers())
1208 listener->notifyOperationModified(op);
1209}
1210
1211void BlockTypeConversionRewrite::rollback() {
1212 getNewBlock()->replaceAllUsesWith(newValue: getOrigBlock());
1213}
1214
1215/// Replace all uses of `from` with `repl`.
1216static void
1217performReplaceValue(RewriterBase &rewriter, Value from, Value repl,
1218 function_ref<bool(OpOperand &)> functor = nullptr) {
1219 if (isa<BlockArgument>(Val: repl)) {
1220 // `repl` is a block argument. Directly replace all uses.
1221 if (functor) {
1222 rewriter.replaceUsesWithIf(from, to: repl, functor);
1223 } else {
1224 rewriter.replaceAllUsesWith(from, to: repl);
1225 }
1226 return;
1227 }
1228
1229 // If the replacement value is an operation, only replace those uses that:
1230 // - are in a different block than the replacement operation, or
1231 // - are in the same block but after the replacement operation.
1232 //
1233 // Example:
1234 // ^bb0(%arg0: i32):
1235 // %0 = "consumer"(%arg0) : (i32) -> (i32)
1236 // "another_consumer"(%arg0) : (i32) -> ()
1237 //
1238 // In the above example, replaceAllUsesWith(%arg0, %0) will replace the
1239 // use in "another_consumer" but not the use in "consumer". When using the
1240 // normal RewriterBase API, this would typically be done with
1241 // `replaceUsesWithIf` / `replaceAllUsesExcept`. However, that API is not
1242 // supported by the `ConversionPatternRewriter`. Due to the mapping mechanism
1243 // it cannot be supported efficiently with `allowPatternRollback` set to
1244 // "true". Therefore, the conversion driver is trying to be smart and replaces
1245 // only those uses that do not lead to a dominance violation. E.g., the
1246 // FuncToLLVM lowering (`restoreByValRefArgumentType`) relies on this
1247 // behavior.
1248 //
1249 // TODO: As we move more and more towards `allowPatternRollback` set to
1250 // "false", we should remove this special handling, in order to align the
1251 // `ConversionPatternRewriter` API with the normal `RewriterBase` API.
1252 Operation *replOp = repl.getDefiningOp();
1253 Block *replBlock = replOp->getBlock();
1254 rewriter.replaceUsesWithIf(from, to: repl, functor: [&](OpOperand &operand) {
1255 Operation *user = operand.getOwner();
1256 bool result =
1257 user->getBlock() != replBlock || replOp->isBeforeInBlock(other: user);
1258 if (result && functor)
1259 result &= functor(operand);
1260 return result;
1261 });
1262}
1263
1264void ReplaceValueRewrite::commit(RewriterBase &rewriter) {
1265 Value repl = rewriterImpl.findOrBuildReplacementValue(value, converter);
1266 if (!repl)
1267 return;
1268 performReplaceValue(rewriter, from: value, repl);
1269}
1270
1271void ReplaceValueRewrite::rollback() {
1272 rewriterImpl.mapping.erase(value: {value});
1273#ifndef NDEBUG
1274 rewriterImpl.replacedValues.erase(value);
1275#endif // NDEBUG
1276}
1277
1278void ReplaceOperationRewrite::commit(RewriterBase &rewriter) {
1279 auto *listener =
1280 dyn_cast_or_null<RewriterBase::Listener>(Val: rewriter.getListener());
1281
1282 // Compute replacement values.
1283 SmallVector<Value> replacements =
1284 llvm::map_to_vector(C: op->getResults(), F: [&](OpResult result) {
1285 return rewriterImpl.findOrBuildReplacementValue(value: result, converter);
1286 });
1287
1288 // Notify the listener that the operation is about to be replaced.
1289 if (listener)
1290 listener->notifyOperationReplaced(op, replacement: replacements);
1291
1292 // Replace all uses with the new values.
1293 for (auto [result, newValue] :
1294 llvm::zip_equal(t: op->getResults(), u&: replacements))
1295 if (newValue)
1296 rewriter.replaceAllUsesWith(from: result, to: newValue);
1297
1298 // The original op will be erased, so remove it from the set of unlegalized
1299 // ops.
1300 if (getConfig().unlegalizedOps)
1301 getConfig().unlegalizedOps->erase(V: op);
1302
1303 // Notify the listener that the operation and its contents are being erased.
1304 if (listener)
1305 notifyIRErased(listener, op&: *op);
1306
1307 // Do not erase the operation yet. It may still be referenced in `mapping`.
1308 // Just unlink it for now and erase it during cleanup.
1309 if (!op->getBlock())
1310 llvm::reportFatalInternalError(
1311 reason: "dialect conversion attempted to replace a root operation that has no "
1312 "parent block; the pass must ensure its target op is nested in a "
1313 "block");
1314 op->getBlock()->getOperations().remove(IT: op);
1315}
1316
1317void ReplaceOperationRewrite::rollback() {
1318 for (auto result : op->getResults())
1319 rewriterImpl.mapping.erase(value: {result});
1320}
1321
1322void ReplaceOperationRewrite::cleanup(RewriterBase &rewriter) {
1323 rewriter.eraseOp(op);
1324}
1325
1326void CreateOperationRewrite::rollback() {
1327 for (Region &region : op->getRegions()) {
1328 while (!region.getBlocks().empty())
1329 region.getBlocks().remove(IT: region.getBlocks().begin());
1330 }
1331 op->dropAllUses();
1332 op->erase();
1333}
1334
1335void UnresolvedMaterializationRewrite::rollback() {
1336 if (!mappedValues.empty())
1337 rewriterImpl.mapping.erase(value: mappedValues);
1338 rewriterImpl.unresolvedMaterializations.erase(Key: getOperation());
1339 op->erase();
1340}
1341
1342void ConversionPatternRewriterImpl::applyRewrites() {
1343 // Commit all rewrites. Use a new rewriter, so the modifications are not
1344 // tracked for rollback purposes etc.
1345 IRRewriter irRewriter(rewriter.getContext(), config.listener);
1346 // Note: New rewrites may be added during the "commit" phase and the
1347 // `rewrites` vector may reallocate.
1348 for (size_t i = 0; i < rewrites.size(); ++i)
1349 rewrites[i]->commit(rewriter&: irRewriter);
1350
1351 // Clean up all rewrites.
1352 SingleEraseRewriter eraseRewriter(
1353 rewriter.getContext(), /*opErasedCallback=*/[&](Operation *op) {
1354 if (auto castOp = dyn_cast<UnrealizedConversionCastOp>(Val: op))
1355 unresolvedMaterializations.erase(Key: castOp);
1356 });
1357 for (auto &rewrite : rewrites)
1358 rewrite->cleanup(rewriter&: eraseRewriter);
1359}
1360
1361//===----------------------------------------------------------------------===//
1362// State Management
1363//===----------------------------------------------------------------------===//
1364
1365ValueVector ConversionPatternRewriterImpl::lookupOrDefault(
1366 Value from, TypeRange desiredTypes, bool skipPureTypeConversions) const {
1367 // Helper function that looks up a single value.
1368 auto lookup = [&](const ValueVector &values) -> ValueVector {
1369 assert(!values.empty() && "expected non-empty value vector");
1370
1371 // If the pattern rollback is enabled, use the mapping to look up the
1372 // values.
1373 if (config.allowPatternRollback)
1374 return mapping.lookup(from: values);
1375
1376 // Otherwise, look up values by examining the IR. All replacements have
1377 // already been materialized in IR.
1378 Operation *op = getCommonDefiningOp(values);
1379 if (!op)
1380 return {};
1381 auto castOp = dyn_cast<UnrealizedConversionCastOp>(Val: op);
1382 if (!castOp)
1383 return {};
1384 if (!this->unresolvedMaterializations.contains(Key: castOp))
1385 return {};
1386 if (castOp.getOutputs() != values)
1387 return {};
1388 return castOp.getInputs();
1389 };
1390
1391 // Helper function that looks up each value in `values` individually and then
1392 // composes the results. If that fails, it tries to look up the entire vector
1393 // at once.
1394 auto composedLookup = [&](const ValueVector &values) -> ValueVector {
1395 // If possible, replace each value with (one or multiple) mapped values.
1396 ValueVector next;
1397 for (Value v : values) {
1398 ValueVector r = lookup({v});
1399 if (!r.empty()) {
1400 llvm::append_range(C&: next, R&: r);
1401 } else {
1402 next.push_back(Elt: v);
1403 }
1404 }
1405 if (next != values) {
1406 // At least one value was replaced.
1407 return next;
1408 }
1409
1410 // Otherwise: Check if there is a mapping for the entire vector. Such
1411 // mappings are materializations. (N:M mapping are not supported for value
1412 // replacements.)
1413 //
1414 // Note: From a correctness point of view, materializations do not have to
1415 // be stored (and looked up) in the mapping. But for performance reasons,
1416 // we choose to reuse existing IR (when possible) instead of creating it
1417 // multiple times.
1418 ValueVector r = lookup(values);
1419 if (r.empty()) {
1420 // No mapping found: The lookup stops here.
1421 return {};
1422 }
1423 return r;
1424 };
1425
1426 // Try to find the deepest values that have the desired types. If there is no
1427 // such mapping, simply return the deepest values.
1428 ValueVector desiredValue;
1429 ValueVector current{from};
1430 ValueVector lastNonMaterialization{from};
1431 do {
1432 // Store the current value if the types match.
1433 bool match = TypeRange(ValueRange(current)) == desiredTypes;
1434 if (skipPureTypeConversions) {
1435 // Skip pure type conversions, if requested.
1436 bool pureConversion = isPureTypeConversion(values: current);
1437 match &= !pureConversion;
1438 // Keep track of the last mapped value that was not a pure type
1439 // conversion.
1440 if (!pureConversion)
1441 lastNonMaterialization = current;
1442 }
1443 if (match)
1444 desiredValue = current;
1445
1446 // Lookup next value in the mapping.
1447 ValueVector next = composedLookup(current);
1448 if (next.empty())
1449 break;
1450 current = std::move(next);
1451 } while (true);
1452
1453 // If the desired values were found use them, otherwise default to the leaf
1454 // values. (Skip pure type conversions, if requested.)
1455 if (!desiredTypes.empty())
1456 return desiredValue;
1457 if (skipPureTypeConversions)
1458 return lastNonMaterialization;
1459 return current;
1460}
1461
1462ValueVector
1463ConversionPatternRewriterImpl::lookupOrNull(Value from,
1464 TypeRange desiredTypes) const {
1465 ValueVector result = lookupOrDefault(from, desiredTypes);
1466 if (result == ValueVector{from} ||
1467 (!desiredTypes.empty() && TypeRange(ValueRange(result)) != desiredTypes))
1468 return {};
1469 return result;
1470}
1471
1472RewriterState ConversionPatternRewriterImpl::getCurrentState() {
1473 return RewriterState(rewrites.size(), ignoredOps.size(), replacedOps.size());
1474}
1475
1476void ConversionPatternRewriterImpl::resetState(RewriterState state,
1477 StringRef patternName) {
1478 // Undo any rewrites.
1479 undoRewrites(numRewritesToKeep: state.numRewrites, patternName);
1480
1481 // Pop all of the recorded ignored operations that are no longer valid.
1482 while (ignoredOps.size() != state.numIgnoredOperations)
1483 ignoredOps.pop_back();
1484
1485 while (replacedOps.size() != state.numReplacedOps)
1486 replacedOps.pop_back();
1487}
1488
1489void ConversionPatternRewriterImpl::undoRewrites(unsigned numRewritesToKeep,
1490 StringRef patternName) {
1491 for (auto &rewrite :
1492 llvm::reverse(C: llvm::drop_begin(RangeOrContainer&: rewrites, N: numRewritesToKeep)))
1493 rewrite->rollback();
1494 rewrites.resize(N: numRewritesToKeep);
1495}
1496
1497LogicalResult ConversionPatternRewriterImpl::remapValues(
1498 StringRef valueDiagTag, std::optional<Location> inputLoc, ValueRange values,
1499 SmallVector<ValueVector> &remapped) {
1500 remapped.reserve(N: llvm::size(Range&: values));
1501
1502 for (const auto &it : llvm::enumerate(First&: values)) {
1503 Value operand = it.value();
1504 Type origType = operand.getType();
1505 Location operandLoc = inputLoc ? *inputLoc : operand.getLoc();
1506
1507 if (!currentTypeConverter) {
1508 // The current pattern does not have a type converter. Pass the most
1509 // recently mapped values, excluding materializations. Materializations
1510 // are intentionally excluded because their presence may depend on other
1511 // patterns. Including materializations would make the lookup fragile
1512 // and unpredictable.
1513 remapped.push_back(Elt: lookupOrDefault(from: operand, /*desiredTypes=*/{},
1514 /*skipPureTypeConversions=*/true));
1515 continue;
1516 }
1517
1518 // If there is no legal conversion, fail to match this pattern.
1519 SmallVector<Type, 1> legalTypes;
1520 if (failed(Result: currentTypeConverter->convertType(v: operand, results&: legalTypes))) {
1521 notifyMatchFailure(loc: operandLoc, reasonCallback: [=](Diagnostic &diag) {
1522 diag << "unable to convert type for " << valueDiagTag << " #"
1523 << it.index() << ", type was " << origType;
1524 });
1525 return failure();
1526 }
1527 // If a type is converted to 0 types, there is nothing to do.
1528 if (legalTypes.empty()) {
1529 remapped.push_back(Elt: {});
1530 continue;
1531 }
1532
1533 ValueVector repl = lookupOrDefault(from: operand, desiredTypes: legalTypes);
1534 if (!repl.empty() && TypeRange(ValueRange(repl)) == legalTypes) {
1535 // Mapped values have the correct type or there is an existing
1536 // materialization. Or the operand is not mapped at all and has the
1537 // correct type.
1538 remapped.push_back(Elt: std::move(repl));
1539 continue;
1540 }
1541
1542 // Create a materialization for the most recently mapped values.
1543 repl = lookupOrDefault(from: operand, /*desiredTypes=*/{},
1544 /*skipPureTypeConversions=*/true);
1545 ValueRange castValues = buildUnresolvedMaterialization(
1546 kind: MaterializationKind::Target, ip: computeInsertPoint(vals: repl), loc: operandLoc,
1547 /*valuesToMap=*/repl, /*inputs=*/repl, /*outputTypes=*/legalTypes,
1548 /*originalType=*/origType, converter: currentTypeConverter);
1549 remapped.push_back(Elt: castValues);
1550 }
1551 return success();
1552}
1553
1554bool ConversionPatternRewriterImpl::isOpIgnored(Operation *op) const {
1555 // Check to see if this operation is ignored or was replaced.
1556 return wasOpReplaced(op) || ignoredOps.count(key: op);
1557}
1558
1559bool ConversionPatternRewriterImpl::wasOpReplaced(Operation *op) const {
1560 // Check to see if this operation was replaced.
1561 return replacedOps.count(key: op) || erasedOps.count(V: op);
1562}
1563
1564//===----------------------------------------------------------------------===//
1565// Type Conversion
1566//===----------------------------------------------------------------------===//
1567
1568FailureOr<Block *> ConversionPatternRewriterImpl::convertRegionTypes(
1569 Region *region, const TypeConverter &converter,
1570 TypeConverter::SignatureConversion *entryConversion) {
1571 regionToConverter[region] = &converter;
1572 if (region->empty())
1573 return nullptr;
1574
1575 // Convert the arguments of each non-entry block within the region.
1576 for (Block &block :
1577 llvm::make_early_inc_range(Range: llvm::drop_begin(RangeOrContainer&: *region, N: 1))) {
1578 // Compute the signature for the block with the provided converter.
1579 std::optional<TypeConverter::SignatureConversion> conversion =
1580 converter.convertBlockSignature(block: &block);
1581 if (!conversion)
1582 return failure();
1583 // Convert the block with the computed signature.
1584 applySignatureConversion(block: &block, converter: &converter, signatureConversion&: *conversion);
1585 }
1586
1587 // Convert the entry block. If an entry signature conversion was provided,
1588 // use that one. Otherwise, compute the signature with the type converter.
1589 if (entryConversion)
1590 return applySignatureConversion(block: &region->front(), converter: &converter,
1591 signatureConversion&: *entryConversion);
1592 std::optional<TypeConverter::SignatureConversion> conversion =
1593 converter.convertBlockSignature(block: &region->front());
1594 if (!conversion)
1595 return failure();
1596 return applySignatureConversion(block: &region->front(), converter: &converter, signatureConversion&: *conversion);
1597}
1598
1599Block *ConversionPatternRewriterImpl::applySignatureConversion(
1600 Block *block, const TypeConverter *converter,
1601 TypeConverter::SignatureConversion &signatureConversion) {
1602#if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS
1603 // A block cannot be converted multiple times.
1604 if (hasRewrite<BlockTypeConversionRewrite>(rewrites, block))
1605 llvm::reportFatalInternalError("block was already converted");
1606#endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS
1607
1608 OpBuilder::InsertionGuard g(rewriter);
1609
1610 // If no arguments are being changed or added, there is nothing to do.
1611 unsigned origArgCount = block->getNumArguments();
1612 auto convertedTypes = signatureConversion.getConvertedTypes();
1613 if (llvm::equal(LRange: block->getArgumentTypes(), RRange&: convertedTypes))
1614 return block;
1615
1616 // Compute the locations of all block arguments in the new block.
1617 SmallVector<Location> newLocs(convertedTypes.size(),
1618 rewriter.getUnknownLoc());
1619 for (unsigned i = 0; i < origArgCount; ++i) {
1620 auto inputMap = signatureConversion.getInputMapping(input: i);
1621 if (!inputMap || inputMap->replacedWithValues())
1622 continue;
1623 Location origLoc = block->getArgument(i).getLoc();
1624 for (unsigned j = 0; j < inputMap->size; ++j)
1625 newLocs[inputMap->inputNo + j] = origLoc;
1626 }
1627
1628 // Insert a new block with the converted block argument types and move all ops
1629 // from the old block to the new block.
1630 Block *newBlock =
1631 rewriter.createBlock(parent: block->getParent(), insertPt: std::next(x: block->getIterator()),
1632 argTypes: convertedTypes, locs: newLocs);
1633
1634 // If a listener is attached to the dialect conversion, ops cannot be moved
1635 // to the destination block in bulk ("fast path"). This is because at the time
1636 // the notifications are sent, it is unknown which ops were moved. Instead,
1637 // ops should be moved one-by-one ("slow path"), so that a separate
1638 // `MoveOperationRewrite` is enqueued for each moved op. Moving ops in bulk is
1639 // a bit more efficient, so we try to do that when possible.
1640 bool fastPath = !config.listener;
1641 if (fastPath) {
1642 if (config.allowPatternRollback)
1643 appendRewrite<InlineBlockRewrite>(args&: newBlock, args&: block, args: newBlock->end());
1644 newBlock->getOperations().splice(where: newBlock->end(), L2&: block->getOperations());
1645 } else {
1646 while (!block->empty())
1647 rewriter.moveOpBefore(op: &block->front(), block: newBlock, iterator: newBlock->end());
1648 }
1649
1650 // Replace all uses of the old block with the new block.
1651 block->replaceAllUsesWith(newValue&: newBlock);
1652
1653 for (unsigned i = 0; i != origArgCount; ++i) {
1654 BlockArgument origArg = block->getArgument(i);
1655 Type origArgType = origArg.getType();
1656
1657 std::optional<TypeConverter::SignatureConversion::InputMapping> inputMap =
1658 signatureConversion.getInputMapping(input: i);
1659 if (!inputMap) {
1660 // This block argument was dropped and no replacement value was provided.
1661 // Materialize a replacement value "out of thin air".
1662 // Note: Materialization must be built here because we cannot find a
1663 // valid insertion point in the new block. (Will point to the old block.)
1664 Value mat =
1665 buildUnresolvedMaterialization(
1666 kind: MaterializationKind::Source,
1667 ip: OpBuilder::InsertPoint(newBlock, newBlock->begin()),
1668 loc: origArg.getLoc(),
1669 /*valuesToMap=*/{}, /*inputs=*/ValueRange(),
1670 /*outputTypes=*/origArgType, /*originalType=*/Type(), converter,
1671 /*isPureTypeConversion=*/false)
1672 .front();
1673 replaceValueUses(from: origArg, to: mat, converter);
1674 continue;
1675 }
1676
1677 if (inputMap->replacedWithValues()) {
1678 // This block argument was dropped and replacement values were provided.
1679 assert(inputMap->size == 0 &&
1680 "invalid to provide a replacement value when the argument isn't "
1681 "dropped");
1682 replaceValueUses(from: origArg, to: inputMap->replacementValues, converter);
1683 continue;
1684 }
1685
1686 // This is a 1->1+ mapping.
1687 auto replArgs =
1688 newBlock->getArguments().slice(N: inputMap->inputNo, M: inputMap->size);
1689 replaceValueUses(from: origArg, to: replArgs, converter);
1690 }
1691
1692 if (config.allowPatternRollback)
1693 appendRewrite<BlockTypeConversionRewrite>(/*origBlock=*/args&: block, args&: newBlock);
1694
1695 // Erase the old block. (It is just unlinked for now and will be erased during
1696 // cleanup.)
1697 rewriter.eraseBlock(block);
1698
1699 return newBlock;
1700}
1701
1702//===----------------------------------------------------------------------===//
1703// Materializations
1704//===----------------------------------------------------------------------===//
1705
1706/// Build an unresolved materialization operation given an output type and set
1707/// of input operands.
1708ValueRange ConversionPatternRewriterImpl::buildUnresolvedMaterialization(
1709 MaterializationKind kind, OpBuilder::InsertPoint ip, Location loc,
1710 ValueVector valuesToMap, ValueRange inputs, TypeRange outputTypes,
1711 Type originalType, const TypeConverter *converter,
1712 bool isPureTypeConversion) {
1713 assert((!originalType || kind == MaterializationKind::Target) &&
1714 "original type is valid only for target materializations");
1715 assert(TypeRange(inputs) != outputTypes &&
1716 "materialization is not necessary");
1717
1718 // Create an unresolved materialization. We use a new OpBuilder to avoid
1719 // tracking the materialization like we do for other operations.
1720 OpBuilder builder(outputTypes.front().getContext());
1721 builder.setInsertionPoint(block: ip.getBlock(), insertPoint: ip.getPoint());
1722 UnrealizedConversionCastOp convertOp =
1723 UnrealizedConversionCastOp::create(builder, location: loc, resultTypes: outputTypes, operands: inputs);
1724 if (config.attachDebugMaterializationKind) {
1725 StringRef kindStr =
1726 kind == MaterializationKind::Source ? "source" : "target";
1727 convertOp->setDiscardableAttr(name: "__kind__", value: builder.getStringAttr(bytes: kindStr));
1728 }
1729 if (isPureTypeConversion)
1730 convertOp->setDiscardableAttr(name: kPureTypeConversionMarker,
1731 value: builder.getUnitAttr());
1732
1733 // Register the materialization.
1734 unresolvedMaterializations[convertOp] =
1735 UnresolvedMaterializationInfo(converter, kind, originalType);
1736 if (config.allowPatternRollback) {
1737 if (!valuesToMap.empty())
1738 mapping.map(oldVal&: valuesToMap, newVal: convertOp.getResults());
1739 appendRewrite<UnresolvedMaterializationRewrite>(args&: convertOp,
1740 args: std::move(valuesToMap));
1741 } else {
1742 patternMaterializations.insert(V: convertOp);
1743 }
1744 return convertOp.getResults();
1745}
1746
1747Value ConversionPatternRewriterImpl::findOrBuildReplacementValue(
1748 Value value, const TypeConverter *converter) {
1749 assert(config.allowPatternRollback &&
1750 "this code path is valid only in rollback mode");
1751
1752 // Try to find a replacement value with the same type in the conversion value
1753 // mapping. This includes cached materializations. We try to reuse those
1754 // instead of generating duplicate IR.
1755 ValueVector repl = lookupOrNull(from: value, desiredTypes: value.getType());
1756 if (!repl.empty())
1757 return repl.front();
1758
1759 // Check if the value is dead. No replacement value is needed in that case.
1760 // This is an approximate check that may have false negatives but does not
1761 // require computing and traversing an inverse mapping. (We may end up
1762 // building source materializations that are never used and that fold away.)
1763 if (llvm::all_of(Range: value.getUsers(),
1764 P: [&](Operation *op) { return replacedOps.contains(key: op); }) &&
1765 !mapping.isMappedTo(value))
1766 return Value();
1767
1768 // No replacement value was found. Get the latest replacement value
1769 // (regardless of the type) and build a source materialization to the
1770 // original type.
1771 repl = lookupOrNull(from: value);
1772
1773 // Compute the insertion point of the materialization.
1774 OpBuilder::InsertPoint ip;
1775 if (repl.empty()) {
1776 // The source materialization has no inputs. Insert it right before the
1777 // value that it is replacing.
1778 ip = computeInsertPoint(value);
1779 } else {
1780 // Compute the "earliest" insertion point at which all values in `repl` are
1781 // defined. It is important to emit the materialization at that location
1782 // because the same materialization may be reused in a different context.
1783 // (That's because materializations are cached in the conversion value
1784 // mapping.) The insertion point of the materialization must be valid for
1785 // all future users that may be created later in the conversion process.
1786 ip = computeInsertPoint(vals: repl);
1787 }
1788 Value castValue = buildUnresolvedMaterialization(
1789 kind: MaterializationKind::Source, ip, loc: value.getLoc(),
1790 /*valuesToMap=*/repl, /*inputs=*/repl,
1791 /*outputTypes=*/value.getType(),
1792 /*originalType=*/Type(), converter,
1793 /*isPureTypeConversion=*/!repl.empty())
1794 .front();
1795 return castValue;
1796}
1797
1798//===----------------------------------------------------------------------===//
1799// Rewriter Notification Hooks
1800//===----------------------------------------------------------------------===//
1801
1802void ConversionPatternRewriterImpl::notifyOperationInserted(
1803 Operation *op, OpBuilder::InsertPoint previous) {
1804 // If no previous insertion point is provided, the op used to be detached.
1805 bool wasDetached = !previous.isSet();
1806 LLVM_DEBUG({
1807 logger.startLine() << "** Insert : '" << op->getName() << "' (" << op
1808 << ")";
1809 if (wasDetached)
1810 logger.getOStream() << " (was detached)";
1811 logger.getOStream() << "\n";
1812 });
1813
1814 // In rollback mode, it is easier to misuse the API, so perform extra error
1815 // checking.
1816 assert(!(config.allowPatternRollback && wasOpReplaced(op->getParentOp())) &&
1817 "attempting to insert into a block within a replaced/erased op");
1818
1819 // In "no rollback" mode, the listener is always notified immediately.
1820 if (!config.allowPatternRollback && config.listener)
1821 config.listener->notifyOperationInserted(op, previous);
1822
1823 if (wasDetached) {
1824 // If the op was detached, it is most likely a newly created op. Add it the
1825 // set of newly created ops, so that it will be legalized. If this op is
1826 // not a newly created op, it will be legalized a second time, which is
1827 // inefficient but harmless.
1828 patternNewOps.insert(X: op);
1829
1830 if (config.allowPatternRollback) {
1831 // TODO: If the same op is inserted multiple times from a detached
1832 // state, the rollback mechanism may erase the same op multiple times.
1833 // This is a bug in the rollback-based dialect conversion driver.
1834 appendRewrite<CreateOperationRewrite>(args&: op);
1835 } else {
1836 // In "no rollback" mode, there is an extra data structure for tracking
1837 // erased operations that must be kept up to date.
1838 erasedOps.erase(V: op);
1839 }
1840 return;
1841 }
1842
1843 // The op was moved from one place to another.
1844 if (config.allowPatternRollback)
1845 appendRewrite<MoveOperationRewrite>(args&: op, args&: previous);
1846}
1847
1848/// Given that `fromRange` is about to be replaced with `toRange`, compute
1849/// replacement values with the types of `fromRange`.
1850static SmallVector<Value>
1851getReplacementValues(ConversionPatternRewriterImpl &impl, ValueRange fromRange,
1852 const SmallVector<SmallVector<Value>> &toRange,
1853 const TypeConverter *converter) {
1854 assert(!impl.config.allowPatternRollback &&
1855 "this code path is valid only in 'no rollback' mode");
1856 SmallVector<Value> repls;
1857 for (auto [from, to] : llvm::zip_equal(t&: fromRange, u: toRange)) {
1858 if (from.use_empty()) {
1859 // The replaced value is dead. No replacement value is needed.
1860 repls.push_back(Elt: Value());
1861 continue;
1862 }
1863
1864 if (to.empty()) {
1865 // The replaced value is dropped. Materialize a replacement value "out of
1866 // thin air".
1867 Value srcMat = impl.buildUnresolvedMaterialization(
1868 kind: MaterializationKind::Source, ip: computeInsertPoint(value: from), loc: from.getLoc(),
1869 /*valuesToMap=*/{}, /*inputs=*/ValueRange(),
1870 /*outputTypes=*/from.getType(), /*originalType=*/Type(),
1871 converter)[0];
1872 repls.push_back(Elt: srcMat);
1873 continue;
1874 }
1875
1876 if (TypeRange(ValueRange(to)) == TypeRange(from.getType())) {
1877 // The replacement value already has the correct type. Use it directly.
1878 repls.push_back(Elt: to[0]);
1879 continue;
1880 }
1881
1882 // The replacement value has the wrong type. Build a source materialization
1883 // to the original type.
1884 // TODO: This is a bit inefficient. We should try to reuse existing
1885 // materializations if possible. This would require an extension of the
1886 // `lookupOrDefault` API.
1887 Value srcMat = impl.buildUnresolvedMaterialization(
1888 kind: MaterializationKind::Source, ip: computeInsertPoint(vals: to), loc: from.getLoc(),
1889 /*valuesToMap=*/{}, /*inputs=*/to, /*outputTypes=*/from.getType(),
1890 /*originalType=*/Type(), converter)[0];
1891 repls.push_back(Elt: srcMat);
1892 }
1893
1894 return repls;
1895}
1896
1897void ConversionPatternRewriterImpl::replaceOp(
1898 Operation *op, SmallVector<SmallVector<Value>> &&newValues) {
1899 assert(newValues.size() == op->getNumResults() &&
1900 "incorrect number of replacement values");
1901 LLVM_DEBUG({
1902 logger.startLine() << "** Replace : '" << op->getName() << "'(" << op
1903 << ")\n";
1904 if (currentTypeConverter) {
1905 // If the user-provided replacement types are different from the
1906 // legalized types, as per the current type converter, print a note.
1907 // In most cases, the replacement types are expected to match the types
1908 // produced by the type converter, so this could indicate a bug in the
1909 // user code.
1910 for (auto [result, repls] :
1911 llvm::zip_equal(op->getResults(), newValues)) {
1912 Type resultType = result.getType();
1913 auto logProlog = [&, repls = repls]() {
1914 logger.startLine() << " Note: Replacing op result of type "
1915 << resultType << " with value(s) of type (";
1916 llvm::interleaveComma(repls, logger.getOStream(), [&](Value v) {
1917 logger.getOStream() << v.getType();
1918 });
1919 logger.getOStream() << ")";
1920 };
1921 SmallVector<Type> convertedTypes;
1922 if (failed(currentTypeConverter->convertTypes(resultType,
1923 convertedTypes))) {
1924 logProlog();
1925 logger.getOStream() << ", but the type converter failed to legalize "
1926 "the original type.\n";
1927 continue;
1928 }
1929 if (TypeRange(convertedTypes) != TypeRange(ValueRange(repls))) {
1930 logProlog();
1931 logger.getOStream() << ", but the legalized type(s) is/are (";
1932 llvm::interleaveComma(convertedTypes, logger.getOStream(),
1933 [&](Type t) { logger.getOStream() << t; });
1934 logger.getOStream() << ")\n";
1935 }
1936 }
1937 }
1938 });
1939
1940 if (!config.allowPatternRollback) {
1941 // Pattern rollback is not allowed: materialize all IR changes immediately.
1942 SmallVector<Value> repls = getReplacementValues(
1943 impl&: *this, fromRange: op->getResults(), toRange: newValues, converter: currentTypeConverter);
1944 // Update internal data structures, so that there are no dangling pointers
1945 // to erased IR.
1946 op->walk(callback: [&](Operation *op) {
1947 erasedOps.insert(V: op);
1948 ignoredOps.remove(X: op);
1949 if (auto castOp = dyn_cast<UnrealizedConversionCastOp>(Val: op)) {
1950 unresolvedMaterializations.erase(Key: castOp);
1951 patternMaterializations.erase(V: castOp);
1952 }
1953 // The original op will be erased, so remove it from the set of
1954 // unlegalized ops.
1955 if (config.unlegalizedOps)
1956 config.unlegalizedOps->erase(V: op);
1957 });
1958 op->walk(callback: [&](Block *block) { erasedBlocks.insert(V: block); });
1959 // Replace the op with the replacement values and notify the listener.
1960 notifyingRewriter.replaceOp(op, newValues: repls);
1961 return;
1962 }
1963
1964 assert(!ignoredOps.contains(op) && "operation was already replaced");
1965#ifndef NDEBUG
1966 for (Value v : op->getResults())
1967 assert(!replacedValues.contains(v) &&
1968 "attempting to replace a value that was already replaced");
1969#endif // NDEBUG
1970
1971 // Check if replaced op is an unresolved materialization, i.e., an
1972 // unrealized_conversion_cast op that was created by the conversion driver.
1973 if (auto castOp = dyn_cast<UnrealizedConversionCastOp>(Val: op)) {
1974 // Make sure that the user does not mess with unresolved materializations
1975 // that were inserted by the conversion driver. We keep track of these
1976 // ops in internal data structures.
1977 assert(!unresolvedMaterializations.contains(castOp) &&
1978 "attempting to replace/erase an unresolved materialization");
1979 }
1980
1981 // Create mappings for each of the new result values.
1982 for (auto [repl, result] : llvm::zip_equal(t&: newValues, u: op->getResults()))
1983 mapping.map(oldVal: static_cast<Value>(result), newVal: std::move(repl));
1984
1985 appendRewrite<ReplaceOperationRewrite>(args&: op, args&: currentTypeConverter);
1986 // Mark this operation and all nested ops as replaced.
1987 op->walk(callback: [&](Operation *op) { replacedOps.insert(X: op); });
1988}
1989
1990void ConversionPatternRewriterImpl::replaceValueUses(
1991 Value from, ValueRange to, const TypeConverter *converter,
1992 function_ref<bool(OpOperand &)> functor) {
1993 LLVM_DEBUG({
1994 logger.startLine() << "** Replace Value : '" << from << "'";
1995 if (auto blockArg = dyn_cast<BlockArgument>(from)) {
1996 if (Operation *parentOp = blockArg.getOwner()->getParentOp()) {
1997 logger.getOStream() << " (in region of '" << parentOp->getName()
1998 << "' (" << parentOp << ")";
1999 } else {
2000 logger.getOStream() << " (unlinked block)";
2001 }
2002 }
2003 if (functor) {
2004 logger.getOStream() << ", conditional replacement";
2005 }
2006 });
2007
2008 if (!config.allowPatternRollback) {
2009 SmallVector<Value> toConv = llvm::to_vector(Range&: to);
2010 SmallVector<Value> repls =
2011 getReplacementValues(impl&: *this, fromRange: from, toRange: {toConv}, converter);
2012 IRRewriter r(from.getContext());
2013 Value repl = repls.front();
2014 if (!repl)
2015 return;
2016
2017 performReplaceValue(rewriter&: r, from, repl, functor);
2018 return;
2019 }
2020
2021#ifndef NDEBUG
2022 // Make sure that a value is not replaced multiple times. In rollback mode,
2023 // `replaceAllUsesWith` replaces not only all current uses of the given value,
2024 // but also all future uses that may be introduced by future pattern
2025 // applications. Therefore, it does not make sense to call
2026 // `replaceAllUsesWith` multiple times with the same value. Doing so would
2027 // overwrite the mapping and mess with the internal state of the dialect
2028 // conversion driver.
2029 assert(!replacedValues.contains(from) &&
2030 "attempting to replace a value that was already replaced");
2031 assert(!wasOpReplaced(from.getDefiningOp()) &&
2032 "attempting to replace a op result that was already replaced");
2033 replacedValues.insert(from);
2034#endif // NDEBUG
2035
2036 if (functor)
2037 llvm::reportFatalInternalError(
2038 reason: "conditional value replacement is not supported in rollback mode");
2039 mapping.map(oldVal&: from, newVal&: to);
2040 appendRewrite<ReplaceValueRewrite>(args&: from, args&: converter);
2041}
2042
2043void ConversionPatternRewriterImpl::eraseBlock(Block *block) {
2044 if (!config.allowPatternRollback) {
2045 // Pattern rollback is not allowed: materialize all IR changes immediately.
2046 // Update internal data structures, so that there are no dangling pointers
2047 // to erased IR.
2048 block->walk(callback: [&](Operation *op) {
2049 erasedOps.insert(V: op);
2050 ignoredOps.remove(X: op);
2051 if (auto castOp = dyn_cast<UnrealizedConversionCastOp>(Val: op)) {
2052 unresolvedMaterializations.erase(Key: castOp);
2053 patternMaterializations.erase(V: castOp);
2054 }
2055 // The original op will be erased, so remove it from the set of
2056 // unlegalized ops.
2057 if (config.unlegalizedOps)
2058 config.unlegalizedOps->erase(V: op);
2059 });
2060 block->walk(callback: [&](Block *block) { erasedBlocks.insert(V: block); });
2061 // Erase the block and notify the listener.
2062 notifyingRewriter.eraseBlock(block);
2063 return;
2064 }
2065
2066 assert(!wasOpReplaced(block->getParentOp()) &&
2067 "attempting to erase a block within a replaced/erased op");
2068 appendRewrite<EraseBlockRewrite>(args&: block);
2069
2070 // Unlink the block from its parent region. The block is kept in the rewrite
2071 // object and will be actually destroyed when rewrites are applied. This
2072 // allows us to keep the operations in the block live and undo the removal by
2073 // re-inserting the block.
2074 block->getParent()->getBlocks().remove(IT: block);
2075
2076 // Mark all nested ops as erased.
2077 block->walk(callback: [&](Operation *op) { replacedOps.insert(X: op); });
2078}
2079
2080void ConversionPatternRewriterImpl::notifyBlockInserted(
2081 Block *block, Region *previous, Region::iterator previousIt) {
2082 // If no previous insertion point is provided, the block used to be detached.
2083 bool wasDetached = !previous;
2084 Operation *newParentOp = block->getParentOp();
2085 LLVM_DEBUG(
2086 {
2087 Operation *parent = newParentOp;
2088 if (parent) {
2089 logger.startLine() << "** Insert Block into : '" << parent->getName()
2090 << "' (" << parent << ")";
2091 } else {
2092 logger.startLine()
2093 << "** Insert Block into detached Region (nullptr parent op)";
2094 }
2095 if (wasDetached)
2096 logger.getOStream() << " (was detached)";
2097 logger.getOStream() << "\n";
2098 });
2099
2100 // In rollback mode, it is easier to misuse the API, so perform extra error
2101 // checking.
2102 assert(!(config.allowPatternRollback && wasOpReplaced(newParentOp)) &&
2103 "attempting to insert into a region within a replaced/erased op");
2104 (void)newParentOp;
2105
2106 // In "no rollback" mode, the listener is always notified immediately.
2107 if (!config.allowPatternRollback && config.listener)
2108 config.listener->notifyBlockInserted(block, previous, previousIt);
2109
2110 if (wasDetached) {
2111 // If the block was detached, it is most likely a newly created block.
2112 if (config.allowPatternRollback) {
2113 // TODO: If the same block is inserted multiple times from a detached
2114 // state, the rollback mechanism may erase the same block multiple times.
2115 // This is a bug in the rollback-based dialect conversion driver.
2116 appendRewrite<CreateBlockRewrite>(args&: block);
2117 } else {
2118 // In "no rollback" mode, there is an extra data structure for tracking
2119 // erased blocks that must be kept up to date.
2120 erasedBlocks.erase(V: block);
2121 }
2122 return;
2123 }
2124
2125 // The block was moved from one place to another.
2126 if (config.allowPatternRollback)
2127 appendRewrite<MoveBlockRewrite>(args&: block, args&: previous, args&: previousIt);
2128}
2129
2130void ConversionPatternRewriterImpl::inlineBlockBefore(Block *source,
2131 Block *dest,
2132 Block::iterator before) {
2133 appendRewrite<InlineBlockRewrite>(args&: dest, args&: source, args&: before);
2134}
2135
2136void ConversionPatternRewriterImpl::notifyMatchFailure(
2137 Location loc, function_ref<void(Diagnostic &)> reasonCallback) {
2138 LLVM_DEBUG({
2139 Diagnostic diag(loc, DiagnosticSeverity::Remark);
2140 reasonCallback(diag);
2141 logger.startLine() << "** Failure : " << diag.str() << "\n";
2142 if (config.notifyCallback)
2143 config.notifyCallback(diag);
2144 });
2145}
2146
2147//===----------------------------------------------------------------------===//
2148// ConversionPatternRewriter
2149//===----------------------------------------------------------------------===//
2150
2151ConversionPatternRewriter::ConversionPatternRewriter(
2152 MLIRContext *ctx, const ConversionConfig &config,
2153 OperationConverter &opConverter)
2154 : PatternRewriter(ctx), impl(new detail::ConversionPatternRewriterImpl(
2155 *this, config, opConverter)) {
2156 setListener(impl.get());
2157}
2158
2159ConversionPatternRewriter::~ConversionPatternRewriter() = default;
2160
2161const ConversionConfig &ConversionPatternRewriter::getConfig() const {
2162 return impl->config;
2163}
2164
2165void ConversionPatternRewriter::replaceOp(Operation *op, Operation *newOp) {
2166 assert(op && newOp && "expected non-null op");
2167 replaceOp(op, newValues: newOp->getResults());
2168}
2169
2170void ConversionPatternRewriter::replaceOp(Operation *op, ValueRange newValues) {
2171 assert(op->getNumResults() == newValues.size() &&
2172 "incorrect # of replacement values");
2173
2174 // If the current insertion point is before the erased operation, we adjust
2175 // the insertion point to be after the operation.
2176 if (getInsertionPoint() == op->getIterator())
2177 setInsertionPointAfter(op);
2178
2179 SmallVector<SmallVector<Value>> newVals =
2180 llvm::map_to_vector(C&: newValues, F: [](Value v) -> SmallVector<Value> {
2181 return v ? SmallVector<Value>{v} : SmallVector<Value>();
2182 });
2183 impl->replaceOp(op, newValues: std::move(newVals));
2184}
2185
2186void ConversionPatternRewriter::replaceOpWithMultiple(
2187 Operation *op, SmallVector<SmallVector<Value>> &&newValues) {
2188 assert(op->getNumResults() == newValues.size() &&
2189 "incorrect # of replacement values");
2190
2191 // If the current insertion point is before the erased operation, we adjust
2192 // the insertion point to be after the operation.
2193 if (getInsertionPoint() == op->getIterator())
2194 setInsertionPointAfter(op);
2195
2196 impl->replaceOp(op, newValues: std::move(newValues));
2197}
2198
2199void ConversionPatternRewriter::eraseOp(Operation *op) {
2200 LLVM_DEBUG({
2201 impl->logger.startLine()
2202 << "** Erase : '" << op->getName() << "'(" << op << ")\n";
2203 });
2204
2205 // If the current insertion point is before the erased operation, we adjust
2206 // the insertion point to be after the operation.
2207 if (getInsertionPoint() == op->getIterator())
2208 setInsertionPointAfter(op);
2209
2210 SmallVector<SmallVector<Value>> nullRepls(op->getNumResults(), {});
2211 impl->replaceOp(op, newValues: std::move(nullRepls));
2212}
2213
2214void ConversionPatternRewriter::eraseBlock(Block *block) {
2215 impl->eraseBlock(block);
2216}
2217
2218Block *ConversionPatternRewriter::applySignatureConversion(
2219 Block *block, TypeConverter::SignatureConversion &conversion,
2220 const TypeConverter *converter) {
2221 assert(!impl->wasOpReplaced(block->getParentOp()) &&
2222 "attempting to apply a signature conversion to a block within a "
2223 "replaced/erased op");
2224 return impl->applySignatureConversion(block, converter, signatureConversion&: conversion);
2225}
2226
2227FailureOr<Block *> ConversionPatternRewriter::convertRegionTypes(
2228 Region *region, const TypeConverter &converter,
2229 TypeConverter::SignatureConversion *entryConversion) {
2230 assert(!impl->wasOpReplaced(region->getParentOp()) &&
2231 "attempting to apply a signature conversion to a block within a "
2232 "replaced/erased op");
2233 return impl->convertRegionTypes(region, converter, entryConversion);
2234}
2235
2236void ConversionPatternRewriter::replaceAllUsesWith(Value from, ValueRange to) {
2237 impl->replaceValueUses(from, to, converter: impl->currentTypeConverter);
2238}
2239
2240bool ConversionPatternRewriter::replaceUsesWithIf(
2241 Value from, ValueRange to, function_ref<bool(OpOperand &)> functor,
2242 bool *allUsesReplaced) {
2243 assert(!allUsesReplaced &&
2244 "allUsesReplaced is not supported in a dialect conversion");
2245 bool replaced = false;
2246 impl->replaceValueUses(from, to, converter: impl->currentTypeConverter,
2247 functor: [&](OpOperand &operand) {
2248 bool replace = functor(operand);
2249 replaced |= replace;
2250 return replace;
2251 });
2252 return replaced;
2253}
2254
2255Value ConversionPatternRewriter::getRemappedValue(Value key) {
2256 SmallVector<ValueVector> remappedValues;
2257 if (failed(Result: impl->remapValues(valueDiagTag: "value", /*inputLoc=*/std::nullopt, values: key,
2258 remapped&: remappedValues)))
2259 return nullptr;
2260 assert(remappedValues.front().size() == 1 && "1:N conversion not supported");
2261 return remappedValues.front().front();
2262}
2263
2264LogicalResult
2265ConversionPatternRewriter::getRemappedValues(ValueRange keys,
2266 SmallVectorImpl<Value> &results) {
2267 if (keys.empty())
2268 return success();
2269 SmallVector<ValueVector> remapped;
2270 if (failed(Result: impl->remapValues(valueDiagTag: "value", /*inputLoc=*/std::nullopt, values: keys,
2271 remapped)))
2272 return failure();
2273 for (const auto &values : remapped) {
2274 assert(values.size() == 1 && "1:N conversion not supported");
2275 results.push_back(Elt: values.front());
2276 }
2277 return success();
2278}
2279
2280void ConversionPatternRewriter::inlineBlockBefore(Block *source, Block *dest,
2281 Block::iterator before,
2282 ValueRange argValues) {
2283#ifndef NDEBUG
2284 assert(argValues.size() == source->getNumArguments() &&
2285 "incorrect # of argument replacement values");
2286 assert(!impl->wasOpReplaced(source->getParentOp()) &&
2287 "attempting to inline a block from a replaced/erased op");
2288 assert(!impl->wasOpReplaced(dest->getParentOp()) &&
2289 "attempting to inline a block into a replaced/erased op");
2290 auto opIgnored = [&](Operation *op) { return impl->isOpIgnored(op); };
2291 // The source block will be deleted, so it should not have any users (i.e.,
2292 // there should be no predecessors).
2293 assert(llvm::all_of(source->getUsers(), opIgnored) &&
2294 "expected 'source' to have no predecessors");
2295#endif // NDEBUG
2296
2297 // If a listener is attached to the dialect conversion, ops cannot be moved
2298 // to the destination block in bulk ("fast path"). This is because at the time
2299 // the notifications are sent, it is unknown which ops were moved. Instead,
2300 // ops should be moved one-by-one ("slow path"), so that a separate
2301 // `MoveOperationRewrite` is enqueued for each moved op. Moving ops in bulk is
2302 // a bit more efficient, so we try to do that when possible.
2303 bool fastPath = !getConfig().listener;
2304
2305 if (fastPath && impl->config.allowPatternRollback)
2306 impl->inlineBlockBefore(source, dest, before);
2307
2308 // Replace all uses of block arguments.
2309 for (auto it : llvm::zip(t: source->getArguments(), u&: argValues))
2310 replaceAllUsesWith(from: std::get<0>(t&: it), to: std::get<1>(t&: it));
2311
2312 if (fastPath) {
2313 // Move all ops at once.
2314 dest->getOperations().splice(where: before, L2&: source->getOperations());
2315 } else {
2316 // Move op by op.
2317 while (!source->empty())
2318 moveOpBefore(op: &source->front(), block: dest, iterator: before);
2319 }
2320
2321 // If the current insertion point is within the source block, adjust the
2322 // insertion point to the destination block.
2323 if (getInsertionBlock() == source)
2324 setInsertionPoint(block: dest, insertPoint: getInsertionPoint());
2325
2326 // Erase the source block.
2327 eraseBlock(block: source);
2328}
2329
2330void ConversionPatternRewriter::startOpModification(Operation *op) {
2331 if (!impl->config.allowPatternRollback) {
2332 // Pattern rollback is not allowed: no extra bookkeeping is needed.
2333 PatternRewriter::startOpModification(op);
2334 return;
2335 }
2336 assert(!impl->wasOpReplaced(op) &&
2337 "attempting to modify a replaced/erased op");
2338#ifndef NDEBUG
2339 impl->pendingRootUpdates.insert(op);
2340#endif
2341 impl->appendRewrite<ModifyOperationRewrite>(args&: op);
2342}
2343
2344void ConversionPatternRewriter::finalizeOpModification(Operation *op) {
2345 impl->patternModifiedOps.insert(X: op);
2346 if (!impl->config.allowPatternRollback) {
2347 PatternRewriter::finalizeOpModification(op);
2348 if (getConfig().listener)
2349 getConfig().listener->notifyOperationModified(op);
2350 return;
2351 }
2352
2353 // There is nothing to do here, we only need to track the operation at the
2354 // start of the update.
2355#ifndef NDEBUG
2356 assert(!impl->wasOpReplaced(op) &&
2357 "attempting to modify a replaced/erased op");
2358 assert(impl->pendingRootUpdates.erase(op) &&
2359 "operation did not have a pending in-place update");
2360#endif
2361}
2362
2363void ConversionPatternRewriter::cancelOpModification(Operation *op) {
2364 if (!impl->config.allowPatternRollback) {
2365 PatternRewriter::cancelOpModification(op);
2366 return;
2367 }
2368#ifndef NDEBUG
2369 assert(impl->pendingRootUpdates.erase(op) &&
2370 "operation did not have a pending in-place update");
2371#endif
2372 // Erase the last update for this operation.
2373 auto it = llvm::find_if(
2374 Range: llvm::reverse(C&: impl->rewrites), P: [&](std::unique_ptr<IRRewrite> &rewrite) {
2375 auto *modifyRewrite = dyn_cast<ModifyOperationRewrite>(Val: rewrite.get());
2376 return modifyRewrite && modifyRewrite->getOperation() == op;
2377 });
2378 assert(it != impl->rewrites.rend() && "no root update started on op");
2379 (*it)->rollback();
2380 int updateIdx = std::prev(x: impl->rewrites.rend()) - it;
2381 impl->rewrites.erase(CI: impl->rewrites.begin() + updateIdx);
2382}
2383
2384detail::ConversionPatternRewriterImpl &ConversionPatternRewriter::getImpl() {
2385 return *impl;
2386}
2387
2388//===----------------------------------------------------------------------===//
2389// ConversionPattern
2390//===----------------------------------------------------------------------===//
2391
2392FailureOr<SmallVector<Value>> ConversionPattern::getOneToOneAdaptorOperands(
2393 ArrayRef<ValueRange> operands) const {
2394 SmallVector<Value> oneToOneOperands;
2395 oneToOneOperands.reserve(N: operands.size());
2396 for (ValueRange operand : operands) {
2397 if (operand.size() != 1)
2398 return failure();
2399
2400 oneToOneOperands.push_back(Elt: operand.front());
2401 }
2402 return std::move(oneToOneOperands);
2403}
2404
2405LogicalResult
2406ConversionPattern::matchAndRewrite(Operation *op,
2407 PatternRewriter &rewriter) const {
2408 auto &dialectRewriter = static_cast<ConversionPatternRewriter &>(rewriter);
2409 auto &rewriterImpl = dialectRewriter.getImpl();
2410
2411 // Track the current conversion pattern type converter in the rewriter.
2412 llvm::SaveAndRestore currentConverterGuard(rewriterImpl.currentTypeConverter,
2413 getTypeConverter());
2414
2415 // Remap the operands of the operation.
2416 SmallVector<ValueVector> remapped;
2417 if (failed(Result: rewriterImpl.remapValues(valueDiagTag: "operand", inputLoc: op->getLoc(),
2418 values: op->getOperands(), remapped))) {
2419 return failure();
2420 }
2421 SmallVector<ValueRange> remappedAsRange =
2422 llvm::to_vector_of<ValueRange>(Range&: remapped);
2423 return matchAndRewrite(op, operands: remappedAsRange, rewriter&: dialectRewriter);
2424}
2425
2426//===----------------------------------------------------------------------===//
2427// OperationLegalizer
2428//===----------------------------------------------------------------------===//
2429
2430namespace {
2431/// A set of rewrite patterns that can be used to legalize a given operation.
2432using LegalizationPatterns = SmallVector<const Pattern *, 1>;
2433
2434/// This class defines a recursive operation legalizer.
2435class OperationLegalizer {
2436public:
2437 using LegalizationAction = ConversionTarget::LegalizationAction;
2438
2439 OperationLegalizer(ConversionPatternRewriter &rewriter,
2440 const ConversionTarget &targetInfo,
2441 const FrozenRewritePatternSet &patterns);
2442
2443 /// Returns true if the given operation is known to be illegal on the target.
2444 bool isIllegal(Operation *op) const;
2445
2446 /// Attempt to legalize the given operation. Returns success if the operation
2447 /// was legalized, failure otherwise.
2448 LogicalResult legalize(Operation *op);
2449
2450 /// Returns the conversion target in use by the legalizer.
2451 const ConversionTarget &getTarget() { return target; }
2452
2453private:
2454 /// Attempt to legalize the given operation by folding it.
2455 LogicalResult legalizeWithFold(Operation *op);
2456
2457 /// Attempt to legalize the given operation by applying a pattern. Returns
2458 /// success if the operation was legalized, failure otherwise.
2459 LogicalResult legalizeWithPattern(Operation *op);
2460
2461 /// Return true if the given pattern may be applied to the given operation,
2462 /// false otherwise.
2463 bool canApplyPattern(Operation *op, const Pattern &pattern);
2464
2465 /// Legalize the resultant IR after successfully applying the given pattern.
2466 LogicalResult
2467 legalizePatternResult(Operation *op, const Pattern &pattern,
2468 const RewriterState &curState,
2469 const SetVector<Operation *> &newOps,
2470 const SetVector<Operation *> &modifiedOps);
2471
2472 LogicalResult
2473 legalizePatternCreatedOperations(const SetVector<Operation *> &newOps);
2474 LogicalResult
2475 legalizePatternRootUpdates(const SetVector<Operation *> &modifiedOps);
2476
2477 //===--------------------------------------------------------------------===//
2478 // Cost Model
2479 //===--------------------------------------------------------------------===//
2480
2481 /// Build an optimistic legalization graph given the provided patterns. This
2482 /// function populates 'anyOpLegalizerPatterns' and 'legalizerPatterns' with
2483 /// patterns for operations that are not directly legal, but may be
2484 /// transitively legal for the current target given the provided patterns.
2485 void buildLegalizationGraph(
2486 LegalizationPatterns &anyOpLegalizerPatterns,
2487 DenseMap<OperationName, LegalizationPatterns> &legalizerPatterns);
2488
2489 /// Compute the benefit of each node within the computed legalization graph.
2490 /// This orders the patterns within 'legalizerPatterns' based upon two
2491 /// criteria:
2492 /// 1) Prefer patterns that have the lowest legalization depth, i.e.
2493 /// represent the more direct mapping to the target.
2494 /// 2) When comparing patterns with the same legalization depth, prefer the
2495 /// pattern with the highest PatternBenefit. This allows for users to
2496 /// prefer specific legalizations over others.
2497 void computeLegalizationGraphBenefit(
2498 LegalizationPatterns &anyOpLegalizerPatterns,
2499 DenseMap<OperationName, LegalizationPatterns> &legalizerPatterns);
2500
2501 /// Compute the legalization depth when legalizing an operation of the given
2502 /// type.
2503 unsigned computeOpLegalizationDepth(
2504 OperationName op, DenseMap<OperationName, unsigned> &minOpPatternDepth,
2505 DenseMap<OperationName, LegalizationPatterns> &legalizerPatterns);
2506
2507 /// Apply the conversion cost model to the given set of patterns, and return
2508 /// the smallest legalization depth of any of the patterns. See
2509 /// `computeLegalizationGraphBenefit` for the breakdown of the cost model.
2510 unsigned applyCostModelToPatterns(
2511 LegalizationPatterns &patterns,
2512 DenseMap<OperationName, unsigned> &minOpPatternDepth,
2513 DenseMap<OperationName, LegalizationPatterns> &legalizerPatterns);
2514
2515 /// The current set of patterns that have been applied.
2516 SmallPtrSet<const Pattern *, 8> appliedPatterns;
2517
2518 /// The rewriter to use when converting operations.
2519 ConversionPatternRewriter &rewriter;
2520
2521 /// The legalization information provided by the target.
2522 const ConversionTarget &target;
2523
2524 /// The pattern applicator to use for conversions.
2525 PatternApplicator applicator;
2526};
2527} // namespace
2528
2529OperationLegalizer::OperationLegalizer(ConversionPatternRewriter &rewriter,
2530 const ConversionTarget &targetInfo,
2531 const FrozenRewritePatternSet &patterns)
2532 : rewriter(rewriter), target(targetInfo), applicator(patterns) {
2533 // The set of patterns that can be applied to illegal operations to transform
2534 // them into legal ones.
2535 DenseMap<OperationName, LegalizationPatterns> legalizerPatterns;
2536 LegalizationPatterns anyOpLegalizerPatterns;
2537
2538 buildLegalizationGraph(anyOpLegalizerPatterns, legalizerPatterns);
2539 computeLegalizationGraphBenefit(anyOpLegalizerPatterns, legalizerPatterns);
2540}
2541
2542bool OperationLegalizer::isIllegal(Operation *op) const {
2543 return target.isIllegal(op);
2544}
2545
2546LogicalResult OperationLegalizer::legalize(Operation *op) {
2547#ifndef NDEBUG
2548 const char *logLineComment =
2549 "//===-------------------------------------------===//\n";
2550
2551 auto &logger = rewriter.getImpl().logger;
2552#endif
2553
2554 // Check to see if the operation is ignored and doesn't need to be converted.
2555 bool isIgnored = rewriter.getImpl().isOpIgnored(op);
2556
2557 LLVM_DEBUG({
2558 logger.getOStream() << "\n";
2559 logger.startLine() << logLineComment;
2560 logger.startLine() << "Legalizing operation : ";
2561 // Do not print the operation name if the operation is ignored. Ignored ops
2562 // may have been erased and should not be accessed. The pointer can be
2563 // printed safely.
2564 if (!isIgnored)
2565 logger.getOStream() << "'" << op->getName() << "' ";
2566 logger.getOStream() << "(" << op << ") {\n";
2567 logger.indent();
2568
2569 // If the operation has no regions, just print it here.
2570 if (!isIgnored && op->getNumRegions() == 0) {
2571 logger.startLine() << OpWithFlags(op,
2572 OpPrintingFlags().printGenericOpForm())
2573 << "\n";
2574 }
2575 });
2576
2577 if (isIgnored) {
2578 LLVM_DEBUG({
2579 logSuccess(logger, "operation marked 'ignored' during conversion");
2580 logger.startLine() << logLineComment;
2581 });
2582 return success();
2583 }
2584
2585 // Check if this operation is legal on the target.
2586 if (auto legalityInfo = target.isLegal(op)) {
2587 LLVM_DEBUG({
2588 logSuccess(
2589 logger, "operation marked legal by the target{0}",
2590 legalityInfo->isRecursivelyLegal
2591 ? "; NOTE: operation is recursively legal; skipping internals"
2592 : "");
2593 logger.startLine() << logLineComment;
2594 });
2595
2596 // If this operation is recursively legal, mark its children as ignored so
2597 // that we don't consider them for legalization.
2598 if (legalityInfo->isRecursivelyLegal) {
2599 op->walk(callback: [&](Operation *nested) {
2600 if (op != nested)
2601 rewriter.getImpl().ignoredOps.insert(X: nested);
2602 });
2603 }
2604
2605 return success();
2606 }
2607
2608 // If the operation is not legal, try to fold it in-place if the folding mode
2609 // is 'BeforePatterns'. 'Never' will skip this.
2610 const ConversionConfig &config = rewriter.getConfig();
2611 if (config.foldingMode == DialectConversionFoldingMode::BeforePatterns) {
2612 if (succeeded(Result: legalizeWithFold(op))) {
2613 LLVM_DEBUG({
2614 logSuccess(logger, "operation was folded");
2615 logger.startLine() << logLineComment;
2616 });
2617 return success();
2618 }
2619 }
2620
2621 // Otherwise, we need to apply a legalization pattern to this operation.
2622 if (succeeded(Result: legalizeWithPattern(op))) {
2623 LLVM_DEBUG({
2624 logSuccess(logger, "");
2625 logger.startLine() << logLineComment;
2626 });
2627 return success();
2628 }
2629
2630 // If the operation can't be legalized via patterns, try to fold it in-place
2631 // if the folding mode is 'AfterPatterns'.
2632 if (config.foldingMode == DialectConversionFoldingMode::AfterPatterns) {
2633 if (succeeded(Result: legalizeWithFold(op))) {
2634 LLVM_DEBUG({
2635 logSuccess(logger, "operation was folded");
2636 logger.startLine() << logLineComment;
2637 });
2638 return success();
2639 }
2640 }
2641
2642 LLVM_DEBUG({
2643 logFailure(logger, "no matched legalization pattern");
2644 logger.startLine() << logLineComment;
2645 });
2646 return failure();
2647}
2648
2649/// Helper function that moves and returns the given object. Also resets the
2650/// original object, so that it is in a valid, empty state again.
2651template <typename T>
2652static T moveAndReset(T &obj) {
2653 T result = std::move(obj);
2654 obj = T();
2655 return result;
2656}
2657
2658LogicalResult OperationLegalizer::legalizeWithFold(Operation *op) {
2659 auto &rewriterImpl = rewriter.getImpl();
2660 LLVM_DEBUG({
2661 rewriterImpl.logger.startLine() << "* Fold {\n";
2662 rewriterImpl.logger.indent();
2663 });
2664
2665 // Clear pattern state, so that the next pattern application starts with a
2666 // clean slate. (The op/block sets are populated by listener notifications.)
2667 llvm::scope_exit cleanup([&]() {
2668 rewriterImpl.patternNewOps.clear();
2669 rewriterImpl.patternModifiedOps.clear();
2670 });
2671
2672 // Upon failure, undo all changes made by the folder.
2673 RewriterState curState = rewriterImpl.getCurrentState();
2674
2675 // Try to fold the operation.
2676 StringRef opName = op->getName().getStringRef();
2677 SmallVector<Value, 2> replacementValues;
2678 SmallVector<Operation *, 2> newOps;
2679 rewriter.setInsertionPoint(op);
2680 rewriter.startOpModification(op);
2681 if (failed(Result: rewriter.tryFold(op, results&: replacementValues, materializedConstants: &newOps))) {
2682 LLVM_DEBUG(logFailure(rewriterImpl.logger, "unable to fold"));
2683 rewriter.cancelOpModification(op);
2684 return failure();
2685 }
2686 rewriter.finalizeOpModification(op);
2687
2688 // An empty list of replacement values indicates that the fold was in-place.
2689 // As the operation changed, a new legalization needs to be attempted.
2690 if (replacementValues.empty())
2691 return legalize(op);
2692
2693 // Insert a replacement for 'op' with the folded replacement values.
2694 rewriter.replaceOp(op, newValues: replacementValues);
2695
2696 // Recursively legalize any new constant operations.
2697 for (Operation *newOp : newOps) {
2698 if (failed(Result: legalize(op: newOp))) {
2699 LLVM_DEBUG(logFailure(rewriterImpl.logger,
2700 "failed to legalize generated constant '{0}'",
2701 newOp->getName()));
2702 if (!rewriter.getConfig().allowPatternRollback) {
2703 // Rolling back a folder is like rolling back a pattern.
2704 llvm::reportFatalInternalError(
2705 reason: "op '" + opName +
2706 "' folder rollback of IR modifications requested");
2707 }
2708 rewriterImpl.resetState(state: curState, patternName: std::string(opName) + " folder");
2709 return failure();
2710 }
2711 }
2712
2713 LLVM_DEBUG(logSuccess(rewriterImpl.logger, ""));
2714 return success();
2715}
2716
2717/// Report a fatal error indicating that newly produced or modified IR could
2718/// not be legalized.
2719static void
2720reportNewIrLegalizationFatalError(const Pattern &pattern,
2721 const SetVector<Operation *> &newOps,
2722 const SetVector<Operation *> &modifiedOps) {
2723 auto newOpNames = llvm::map_range(
2724 C: newOps, F: [](Operation *op) { return op->getName().getStringRef(); });
2725 auto modifiedOpNames = llvm::map_range(
2726 C: modifiedOps, F: [](Operation *op) { return op->getName().getStringRef(); });
2727 llvm::reportFatalInternalError(reason: "pattern '" + pattern.getDebugName() +
2728 "' produced IR that could not be legalized. " +
2729 "new ops: {" + llvm::join(R&: newOpNames, Separator: ", ") +
2730 "}, " + "modified ops: {" +
2731 llvm::join(R&: modifiedOpNames, Separator: ", ") + "}");
2732}
2733
2734LogicalResult OperationLegalizer::legalizeWithPattern(Operation *op) {
2735 auto &rewriterImpl = rewriter.getImpl();
2736 const ConversionConfig &config = rewriter.getConfig();
2737
2738#if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS
2739 Operation *checkOp;
2740 std::optional<OperationFingerPrint> topLevelFingerPrint;
2741 if (!rewriterImpl.config.allowPatternRollback) {
2742 // The op may be getting erased, so we have to check the parent op.
2743 // (In rare cases, a pattern may even erase the parent op, which will cause
2744 // a crash here. Expensive checks are "best effort".) Skip the check if the
2745 // op does not have a parent op.
2746 if ((checkOp = op->getParentOp())) {
2747 if (!op->getContext()->isMultithreadingEnabled()) {
2748 topLevelFingerPrint = OperationFingerPrint(checkOp);
2749 } else {
2750 // Another thread may be modifying a sibling operation. Therefore, the
2751 // fingerprinting mechanism of the parent op works only in
2752 // single-threaded mode.
2753 LLVM_DEBUG({
2754 rewriterImpl.logger.startLine()
2755 << "WARNING: Multi-threadeding is enabled. Some dialect "
2756 "conversion expensive checks are skipped in multithreading "
2757 "mode!\n";
2758 });
2759 }
2760 }
2761 }
2762#endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS
2763
2764 // Functor that returns if the given pattern may be applied.
2765 auto canApply = [&](const Pattern &pattern) {
2766 bool canApply = canApplyPattern(op, pattern);
2767 if (canApply && config.listener)
2768 config.listener->notifyPatternBegin(pattern, op);
2769 return canApply;
2770 };
2771
2772 // Functor that cleans up the rewriter state after a pattern failed to match.
2773 RewriterState curState = rewriterImpl.getCurrentState();
2774 auto onFailure = [&](const Pattern &pattern) {
2775 assert(rewriterImpl.pendingRootUpdates.empty() && "dangling root updates");
2776 if (!rewriterImpl.config.allowPatternRollback) {
2777 // Erase all unresolved materializations.
2778 for (auto op : rewriterImpl.patternMaterializations) {
2779 rewriterImpl.unresolvedMaterializations.erase(Key: op);
2780 op.erase();
2781 }
2782 rewriterImpl.patternMaterializations.clear();
2783#if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS
2784 // Expensive pattern check that can detect API violations.
2785 if (checkOp && topLevelFingerPrint) {
2786 OperationFingerPrint fingerPrintAfterPattern(checkOp);
2787 if (fingerPrintAfterPattern != *topLevelFingerPrint)
2788 llvm::reportFatalInternalError(
2789 "pattern '" + pattern.getDebugName() +
2790 "' returned failure but IR did change");
2791 }
2792#endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS
2793 }
2794 rewriterImpl.patternNewOps.clear();
2795 rewriterImpl.patternModifiedOps.clear();
2796 LLVM_DEBUG({
2797 logFailure(rewriterImpl.logger, "pattern failed to match");
2798 if (rewriterImpl.config.notifyCallback) {
2799 Diagnostic diag(op->getLoc(), DiagnosticSeverity::Remark);
2800 diag << "Failed to apply pattern \"" << pattern.getDebugName()
2801 << "\" on op:\n"
2802 << *op;
2803 rewriterImpl.config.notifyCallback(diag);
2804 }
2805 });
2806 if (config.listener)
2807 config.listener->notifyPatternEnd(pattern, status: failure());
2808 rewriterImpl.resetState(state: curState, patternName: pattern.getDebugName());
2809 appliedPatterns.erase(Ptr: &pattern);
2810 };
2811
2812 // Functor that performs additional legalization when a pattern is
2813 // successfully applied.
2814 auto onSuccess = [&](const Pattern &pattern) {
2815 assert(rewriterImpl.pendingRootUpdates.empty() && "dangling root updates");
2816 if (!rewriterImpl.config.allowPatternRollback) {
2817 // Eagerly erase unused materializations.
2818 for (auto op : rewriterImpl.patternMaterializations) {
2819 if (op->use_empty()) {
2820 rewriterImpl.unresolvedMaterializations.erase(Key: op);
2821 op.erase();
2822 }
2823 }
2824 rewriterImpl.patternMaterializations.clear();
2825 }
2826 SetVector<Operation *> newOps = moveAndReset(obj&: rewriterImpl.patternNewOps);
2827 SetVector<Operation *> modifiedOps =
2828 moveAndReset(obj&: rewriterImpl.patternModifiedOps);
2829 auto result =
2830 legalizePatternResult(op, pattern, curState, newOps, modifiedOps);
2831 appliedPatterns.erase(Ptr: &pattern);
2832 if (failed(Result: result)) {
2833 if (!rewriterImpl.config.allowPatternRollback)
2834 reportNewIrLegalizationFatalError(pattern, newOps, modifiedOps);
2835 rewriterImpl.resetState(state: curState, patternName: pattern.getDebugName());
2836 }
2837 if (config.listener)
2838 config.listener->notifyPatternEnd(pattern, status: result);
2839 return result;
2840 };
2841
2842 // Try to match and rewrite a pattern on this operation.
2843 return applicator.matchAndRewrite(op, rewriter, canApply, onFailure,
2844 onSuccess);
2845}
2846
2847bool OperationLegalizer::canApplyPattern(Operation *op,
2848 const Pattern &pattern) {
2849 LLVM_DEBUG({
2850 auto &os = rewriter.getImpl().logger;
2851 os.getOStream() << "\n";
2852 os.startLine() << "* Pattern : '" << op->getName() << " -> (";
2853 llvm::interleaveComma(pattern.getGeneratedOps(), os.getOStream());
2854 os.getOStream() << ")' {\n";
2855 os.indent();
2856 });
2857
2858 // Ensure that we don't cycle by not allowing the same pattern to be
2859 // applied twice in the same recursion stack if it is not known to be safe.
2860 if (!pattern.hasBoundedRewriteRecursion() &&
2861 !appliedPatterns.insert(Ptr: &pattern).second) {
2862 LLVM_DEBUG(
2863 logFailure(rewriter.getImpl().logger, "pattern was already applied"));
2864 return false;
2865 }
2866 return true;
2867}
2868
2869LogicalResult OperationLegalizer::legalizePatternResult(
2870 Operation *op, const Pattern &pattern, const RewriterState &curState,
2871 const SetVector<Operation *> &newOps,
2872 const SetVector<Operation *> &modifiedOps) {
2873 [[maybe_unused]] auto &impl = rewriter.getImpl();
2874 assert(impl.pendingRootUpdates.empty() && "dangling root updates");
2875
2876#if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS
2877 if (impl.config.allowPatternRollback) {
2878 // Check that the root was either replaced or updated in place.
2879 auto newRewrites = llvm::drop_begin(impl.rewrites, curState.numRewrites);
2880 auto replacedRoot = [&] {
2881 return hasRewrite<ReplaceOperationRewrite>(newRewrites, op);
2882 };
2883 auto updatedRootInPlace = [&] {
2884 return hasRewrite<ModifyOperationRewrite>(newRewrites, op);
2885 };
2886 if (!replacedRoot() && !updatedRootInPlace())
2887 llvm::reportFatalInternalError(
2888 "expected pattern to replace the root operation "
2889 "or modify it in place");
2890 }
2891#endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS
2892
2893 // Legalize each of the actions registered during application.
2894 if (failed(Result: legalizePatternRootUpdates(modifiedOps)) ||
2895 failed(Result: legalizePatternCreatedOperations(newOps))) {
2896 return failure();
2897 }
2898
2899 LLVM_DEBUG(logSuccess(impl.logger, "pattern applied successfully"));
2900 return success();
2901}
2902
2903LogicalResult OperationLegalizer::legalizePatternCreatedOperations(
2904 const SetVector<Operation *> &newOps) {
2905 for (Operation *op : newOps) {
2906 if (failed(Result: legalize(op))) {
2907 LLVM_DEBUG(logFailure(rewriter.getImpl().logger,
2908 "failed to legalize generated operation '{0}'({1})",
2909 op->getName(), op));
2910 return failure();
2911 }
2912 }
2913 return success();
2914}
2915
2916LogicalResult OperationLegalizer::legalizePatternRootUpdates(
2917 const SetVector<Operation *> &modifiedOps) {
2918 for (Operation *op : modifiedOps) {
2919 if (failed(Result: legalize(op))) {
2920 LLVM_DEBUG(
2921 logFailure(rewriter.getImpl().logger,
2922 "failed to legalize operation updated in-place '{0}'",
2923 op->getName()));
2924 return failure();
2925 }
2926 }
2927 return success();
2928}
2929
2930//===----------------------------------------------------------------------===//
2931// Cost Model
2932//===----------------------------------------------------------------------===//
2933
2934void OperationLegalizer::buildLegalizationGraph(
2935 LegalizationPatterns &anyOpLegalizerPatterns,
2936 DenseMap<OperationName, LegalizationPatterns> &legalizerPatterns) {
2937 // A mapping between an operation and a set of operations that can be used to
2938 // generate it.
2939 DenseMap<OperationName, SmallPtrSet<OperationName, 2>> parentOps;
2940 // A mapping between an operation and any currently invalid patterns it has.
2941 DenseMap<OperationName, SmallPtrSet<const Pattern *, 2>> invalidPatterns;
2942 // A worklist of patterns to consider for legality.
2943 SetVector<const Pattern *> patternWorklist;
2944
2945 // Build the mapping from operations to the parent ops that may generate them.
2946 applicator.walkAllPatterns(walk: [&](const Pattern &pattern) {
2947 std::optional<OperationName> root = pattern.getRootKind();
2948
2949 // If the pattern has no specific root, we can't analyze the relationship
2950 // between the root op and generated operations. Given that, add all such
2951 // patterns to the legalization set.
2952 if (!root) {
2953 anyOpLegalizerPatterns.push_back(Elt: &pattern);
2954 return;
2955 }
2956
2957 // Skip operations that are always known to be legal.
2958 if (target.getOpAction(op: *root) == LegalizationAction::Legal)
2959 return;
2960
2961 // Add this pattern to the invalid set for the root op and record this root
2962 // as a parent for any generated operations.
2963 invalidPatterns[*root].insert(Ptr: &pattern);
2964 for (auto op : pattern.getGeneratedOps())
2965 parentOps[op].insert(Ptr: *root);
2966
2967 // Add this pattern to the worklist.
2968 patternWorklist.insert(X: &pattern);
2969 });
2970
2971 // If there are any patterns that don't have a specific root kind, we can't
2972 // make direct assumptions about what operations will never be legalized.
2973 // Note: Technically we could, but it would require an analysis that may
2974 // recurse into itself. It would be better to perform this kind of filtering
2975 // at a higher level than here anyways.
2976 if (!anyOpLegalizerPatterns.empty()) {
2977 for (const Pattern *pattern : patternWorklist)
2978 legalizerPatterns[*pattern->getRootKind()].push_back(Elt: pattern);
2979 return;
2980 }
2981
2982 while (!patternWorklist.empty()) {
2983 auto *pattern = patternWorklist.pop_back_val();
2984
2985 // Check to see if any of the generated operations are invalid.
2986 if (llvm::any_of(Range: pattern->getGeneratedOps(), P: [&](OperationName op) {
2987 std::optional<LegalizationAction> action = target.getOpAction(op);
2988 return !legalizerPatterns.count(Val: op) &&
2989 (!action || action == LegalizationAction::Illegal);
2990 }))
2991 continue;
2992
2993 // Otherwise, if all of the generated operation are valid, this op is now
2994 // legal so add all of the child patterns to the worklist.
2995 legalizerPatterns[*pattern->getRootKind()].push_back(Elt: pattern);
2996 invalidPatterns[*pattern->getRootKind()].erase(Ptr: pattern);
2997
2998 // Add any invalid patterns of the parent operations to see if they have now
2999 // become legal.
3000 for (auto op : parentOps[*pattern->getRootKind()])
3001 patternWorklist.set_union(invalidPatterns[op]);
3002 }
3003}
3004
3005void OperationLegalizer::computeLegalizationGraphBenefit(
3006 LegalizationPatterns &anyOpLegalizerPatterns,
3007 DenseMap<OperationName, LegalizationPatterns> &legalizerPatterns) {
3008 // The smallest pattern depth, when legalizing an operation.
3009 DenseMap<OperationName, unsigned> minOpPatternDepth;
3010
3011 // For each operation that is transitively legal, compute a cost for it.
3012 for (auto &opIt : legalizerPatterns)
3013 if (!minOpPatternDepth.count(Val: opIt.first))
3014 computeOpLegalizationDepth(op: opIt.first, minOpPatternDepth,
3015 legalizerPatterns);
3016
3017 // Apply the cost model to the patterns that can match any operation. Those
3018 // with a specific operation type are already resolved when computing the op
3019 // legalization depth.
3020 if (!anyOpLegalizerPatterns.empty())
3021 applyCostModelToPatterns(patterns&: anyOpLegalizerPatterns, minOpPatternDepth,
3022 legalizerPatterns);
3023
3024 // Apply a cost model to the pattern applicator. We order patterns first by
3025 // depth then benefit. `legalizerPatterns` contains per-op patterns by
3026 // decreasing benefit.
3027 applicator.applyCostModel(model: [&](const Pattern &pattern) {
3028 ArrayRef<const Pattern *> orderedPatternList;
3029 if (std::optional<OperationName> rootName = pattern.getRootKind())
3030 orderedPatternList = legalizerPatterns[*rootName];
3031 else
3032 orderedPatternList = anyOpLegalizerPatterns;
3033
3034 // If the pattern is not found, then it was removed and cannot be matched.
3035 auto *it = llvm::find(Range&: orderedPatternList, Val: &pattern);
3036 if (it == orderedPatternList.end())
3037 return PatternBenefit::impossibleToMatch();
3038
3039 // Patterns found earlier in the list have higher benefit.
3040 return PatternBenefit(std::distance(first: it, last: orderedPatternList.end()));
3041 });
3042}
3043
3044unsigned OperationLegalizer::computeOpLegalizationDepth(
3045 OperationName op, DenseMap<OperationName, unsigned> &minOpPatternDepth,
3046 DenseMap<OperationName, LegalizationPatterns> &legalizerPatterns) {
3047 // Check for existing depth.
3048 auto depthIt = minOpPatternDepth.find(Val: op);
3049 if (depthIt != minOpPatternDepth.end())
3050 return depthIt->second;
3051
3052 // If a mapping for this operation does not exist, then this operation
3053 // is always legal. Return 0 as the depth for a directly legal operation.
3054 auto opPatternsIt = legalizerPatterns.find(Val: op);
3055 if (opPatternsIt == legalizerPatterns.end() || opPatternsIt->second.empty())
3056 return 0u;
3057
3058 // Record this initial depth in case we encounter this op again when
3059 // recursively computing the depth.
3060 minOpPatternDepth.try_emplace(Key: op, Args: std::numeric_limits<unsigned>::max());
3061
3062 // Apply the cost model to the operation patterns, and update the minimum
3063 // depth.
3064 unsigned minDepth = applyCostModelToPatterns(
3065 patterns&: opPatternsIt->second, minOpPatternDepth, legalizerPatterns);
3066 minOpPatternDepth[op] = minDepth;
3067 return minDepth;
3068}
3069
3070unsigned OperationLegalizer::applyCostModelToPatterns(
3071 LegalizationPatterns &patterns,
3072 DenseMap<OperationName, unsigned> &minOpPatternDepth,
3073 DenseMap<OperationName, LegalizationPatterns> &legalizerPatterns) {
3074 unsigned minDepth = std::numeric_limits<unsigned>::max();
3075
3076 // Compute the depth for each pattern within the set.
3077 SmallVector<std::pair<const Pattern *, unsigned>, 4> patternsByDepth;
3078 patternsByDepth.reserve(N: patterns.size());
3079 for (const Pattern *pattern : patterns) {
3080 unsigned depth = 1;
3081 for (auto generatedOp : pattern->getGeneratedOps()) {
3082 unsigned generatedOpDepth = computeOpLegalizationDepth(
3083 op: generatedOp, minOpPatternDepth, legalizerPatterns);
3084 depth = std::max(a: depth, b: generatedOpDepth + 1);
3085 }
3086 patternsByDepth.emplace_back(Args&: pattern, Args&: depth);
3087
3088 // Update the minimum depth of the pattern list.
3089 minDepth = std::min(a: minDepth, b: depth);
3090 }
3091
3092 // If the operation only has one legalization pattern, there is no need to
3093 // sort them.
3094 if (patternsByDepth.size() == 1)
3095 return minDepth;
3096
3097 // Sort the patterns by those likely to be the most beneficial.
3098 llvm::stable_sort(Range&: patternsByDepth,
3099 C: [](const std::pair<const Pattern *, unsigned> &lhs,
3100 const std::pair<const Pattern *, unsigned> &rhs) {
3101 // First sort by the smaller pattern legalization
3102 // depth.
3103 if (lhs.second != rhs.second)
3104 return lhs.second < rhs.second;
3105
3106 // Then sort by the larger pattern benefit.
3107 auto lhsBenefit = lhs.first->getBenefit();
3108 auto rhsBenefit = rhs.first->getBenefit();
3109 return lhsBenefit > rhsBenefit;
3110 });
3111
3112 // Update the legalization pattern to use the new sorted list.
3113 patterns.clear();
3114 for (auto &patternIt : patternsByDepth)
3115 patterns.push_back(Elt: patternIt.first);
3116 return minDepth;
3117}
3118
3119//===----------------------------------------------------------------------===//
3120// Reconcile Unrealized Casts
3121//===----------------------------------------------------------------------===//
3122
3123/// Try to reconcile all given UnrealizedConversionCastOps and store the
3124/// left-over ops in `remainingCastOps` (if provided). See documentation in
3125/// DialectConversion.h for more details.
3126/// The `isCastOpOfInterestFn` is used to filter the cast ops to proceed: the
3127/// algorithm may visit an operand (or user) which is a cast op, but will not
3128/// try to reconcile it if not in the filtered set.
3129template <typename RangeT>
3130static void reconcileUnrealizedCastsImpl(
3131 RangeT castOps,
3132 function_ref<bool(UnrealizedConversionCastOp)> isCastOpOfInterestFn,
3133 SmallVectorImpl<UnrealizedConversionCastOp> *remainingCastOps) {
3134 // A worklist of cast ops to process.
3135 SetVector<UnrealizedConversionCastOp> worklist(llvm::from_range, castOps);
3136
3137 // Helper function that return the unrealized_conversion_cast op that
3138 // defines all inputs of the given op (in the same order). Return "nullptr"
3139 // if there is no such op.
3140 auto getInputCast =
3141 [](UnrealizedConversionCastOp castOp) -> UnrealizedConversionCastOp {
3142 if (castOp.getInputs().empty())
3143 return {};
3144 auto inputCastOp =
3145 castOp.getInputs().front().getDefiningOp<UnrealizedConversionCastOp>();
3146 if (!inputCastOp)
3147 return {};
3148 if (inputCastOp.getOutputs() != castOp.getInputs())
3149 return {};
3150 return inputCastOp;
3151 };
3152
3153 // Process ops in the worklist bottom-to-top.
3154 while (!worklist.empty()) {
3155 UnrealizedConversionCastOp castOp = worklist.pop_back_val();
3156
3157 // Traverse the chain of input cast ops to see if an op with the same
3158 // input types can be found.
3159 UnrealizedConversionCastOp nextCast = castOp;
3160 while (nextCast) {
3161 if (nextCast.getInputs().getTypes() == castOp.getResultTypes()) {
3162 if (llvm::any_of(nextCast.getInputs(), [&](Value v) {
3163 return v.getDefiningOp() == castOp;
3164 })) {
3165 // Ran into a cycle.
3166 break;
3167 }
3168
3169 // Found a cast where the input types match the output types of the
3170 // matched op. We can directly use those inputs.
3171 castOp.replaceAllUsesWith(values: nextCast.getInputs());
3172 break;
3173 }
3174 nextCast = getInputCast(nextCast);
3175 }
3176 }
3177
3178 // A set of all alive cast ops. I.e., ops whose results are (transitively)
3179 // used by an op that is not a cast op.
3180 DenseSet<Operation *> liveOps;
3181
3182 // Helper function that marks the given op and transitively reachable input
3183 // cast ops as alive.
3184 auto markOpLive = [&](Operation *rootOp) {
3185 SmallVector<Operation *> worklist;
3186 worklist.push_back(Elt: rootOp);
3187 while (!worklist.empty()) {
3188 Operation *op = worklist.pop_back_val();
3189 if (liveOps.insert(V: op).second) {
3190 // Successfully inserted: process reachable input cast ops.
3191 for (Value v : op->getOperands())
3192 if (auto castOp = v.getDefiningOp<UnrealizedConversionCastOp>())
3193 if (isCastOpOfInterestFn(castOp))
3194 worklist.push_back(Elt: castOp);
3195 }
3196 }
3197 };
3198
3199 // Find all alive cast ops.
3200 for (UnrealizedConversionCastOp op : castOps) {
3201 // The op may have been marked live already as being an operand of another
3202 // live cast op.
3203 if (liveOps.contains(V: op.getOperation()))
3204 continue;
3205 // If any of the users is not a cast op, mark the current op (and its
3206 // input ops) as live.
3207 if (llvm::any_of(op->getUsers(), [&](Operation *user) {
3208 auto castOp = dyn_cast<UnrealizedConversionCastOp>(Val: user);
3209 return !castOp || !isCastOpOfInterestFn(castOp);
3210 }))
3211 markOpLive(op);
3212 }
3213
3214 // Erase all dead cast ops.
3215 for (UnrealizedConversionCastOp op : castOps) {
3216 if (liveOps.contains(V: op)) {
3217 // Op is alive and was not erased. Add it to the remaining cast ops.
3218 if (remainingCastOps)
3219 remainingCastOps->push_back(Elt: op);
3220 continue;
3221 }
3222
3223 // Op is dead. Erase it.
3224 op->dropAllUses();
3225 op->erase();
3226 }
3227}
3228
3229void mlir::reconcileUnrealizedCasts(
3230 ArrayRef<UnrealizedConversionCastOp> castOps,
3231 SmallVectorImpl<UnrealizedConversionCastOp> *remainingCastOps) {
3232 // Set of all cast ops for faster lookups.
3233 DenseSet<UnrealizedConversionCastOp> castOpSet;
3234 for (UnrealizedConversionCastOp op : castOps)
3235 castOpSet.insert(V: op);
3236 reconcileUnrealizedCasts(castOps: castOpSet, remainingCastOps);
3237}
3238
3239void mlir::reconcileUnrealizedCasts(
3240 const DenseSet<UnrealizedConversionCastOp> &castOps,
3241 SmallVectorImpl<UnrealizedConversionCastOp> *remainingCastOps) {
3242 reconcileUnrealizedCastsImpl(
3243 castOps: llvm::make_range(x: castOps.begin(), y: castOps.end()),
3244 isCastOpOfInterestFn: [&](UnrealizedConversionCastOp castOp) {
3245 return castOps.contains(V: castOp);
3246 },
3247 remainingCastOps);
3248}
3249
3250namespace mlir {
3251static void reconcileUnrealizedCasts(
3252 const llvm::MapVector<UnrealizedConversionCastOp,
3253 UnresolvedMaterializationInfo> &castOps,
3254 SmallVectorImpl<UnrealizedConversionCastOp> *remainingCastOps) {
3255 reconcileUnrealizedCastsImpl(
3256 castOps: castOps.keys(),
3257 isCastOpOfInterestFn: [&](UnrealizedConversionCastOp castOp) {
3258 return castOps.contains(Key: castOp);
3259 },
3260 remainingCastOps);
3261}
3262} // namespace mlir
3263
3264//===----------------------------------------------------------------------===//
3265// OperationConverter
3266//===----------------------------------------------------------------------===//
3267
3268namespace mlir {
3269// This class converts operations to a given conversion target via a set of
3270// rewrite patterns. The conversion behaves differently depending on the
3271// conversion mode.
3272struct OperationConverter {
3273 explicit OperationConverter(MLIRContext *ctx, const ConversionTarget &target,
3274 const FrozenRewritePatternSet &patterns,
3275 const ConversionConfig &config,
3276 OpConversionMode mode)
3277 : rewriter(ctx, config, *this), opLegalizer(rewriter, target, patterns),
3278 mode(mode) {}
3279
3280 /// Applies the conversion to the given operations (and their nested
3281 /// operations).
3282 LogicalResult applyConversion(ArrayRef<Operation *> ops);
3283
3284 /// Legalizes the given operations (and their nested operations) to the
3285 /// conversion target.
3286 template <typename Fn>
3287 LogicalResult legalizeOperations(ArrayRef<Operation *> ops, Fn onFailure,
3288 bool isRecursiveLegalization = false);
3289 LogicalResult legalizeOperations(ArrayRef<Operation *> ops,
3290 bool isRecursiveLegalization = false) {
3291 return legalizeOperations(
3292 ops, /*onFailure=*/[&]() {}, isRecursiveLegalization);
3293 }
3294
3295 /// Converts a single operation. If `isRecursiveLegalization` is "true", the
3296 /// conversion is a recursive legalization request, triggered from within a
3297 /// pattern. In that case, do not emit errors because there will be another
3298 /// attempt at legalizing the operation later (via the regular pre-order
3299 /// legalization mechanism).
3300 LogicalResult convert(Operation *op, bool isRecursiveLegalization = false);
3301
3302 const ConversionTarget &getTarget() { return opLegalizer.getTarget(); }
3303
3304private:
3305 /// The rewriter to use when converting operations.
3306 ConversionPatternRewriter rewriter;
3307
3308 /// The legalizer to use when converting operations.
3309 OperationLegalizer opLegalizer;
3310
3311 /// The conversion mode to use when legalizing operations.
3312 OpConversionMode mode;
3313};
3314} // namespace mlir
3315
3316LogicalResult OperationConverter::convert(Operation *op,
3317 bool isRecursiveLegalization) {
3318 const ConversionConfig &config = rewriter.getConfig();
3319 auto emitFailedToLegalizeDiag = [&](bool wasExplicitlyIllegal) {
3320 InFlightDiagnostic diag = op->emitError()
3321 << "failed to legalize operation '"
3322 << op->getName() << "'";
3323 if (wasExplicitlyIllegal)
3324 diag << " that was explicitly marked illegal";
3325 diag << ": " << OpWithFlags(op, OpPrintingFlags().skipRegions());
3326 };
3327
3328 // Legalize the given operation.
3329 if (failed(Result: opLegalizer.legalize(op))) {
3330 // Handle the case of a failed conversion for each of the different modes.
3331 // Full conversions expect all operations to be converted.
3332 if (mode == OpConversionMode::Full) {
3333 if (!isRecursiveLegalization)
3334 emitFailedToLegalizeDiag(/*wasExplicitlyIllegal=*/false);
3335 return failure();
3336 }
3337 // Partial conversions allow conversions to fail iff the operation was not
3338 // explicitly marked as illegal. If the user provided a `unlegalizedOps`
3339 // set, non-legalizable ops are added to that set.
3340 if (mode == OpConversionMode::Partial) {
3341 if (opLegalizer.isIllegal(op)) {
3342 if (!isRecursiveLegalization)
3343 emitFailedToLegalizeDiag(/*wasExplicitlyIllegal=*/true);
3344 return failure();
3345 }
3346 if (config.unlegalizedOps && !isRecursiveLegalization)
3347 config.unlegalizedOps->insert(V: op);
3348 }
3349 } else if (mode == OpConversionMode::Analysis) {
3350 // Analysis conversions don't fail if any operations fail to legalize,
3351 // they are only interested in the operations that were successfully
3352 // legalized.
3353 if (config.legalizableOps && !isRecursiveLegalization)
3354 config.legalizableOps->insert(V: op);
3355 }
3356 return success();
3357}
3358
3359static LogicalResult
3360legalizeUnresolvedMaterialization(RewriterBase &rewriter,
3361 UnrealizedConversionCastOp op,
3362 const UnresolvedMaterializationInfo &info) {
3363 assert(!op.use_empty() &&
3364 "expected that dead materializations have already been DCE'd");
3365 Operation::operand_range inputOperands = op.getOperands();
3366
3367 // Try to materialize the conversion.
3368 if (const TypeConverter *converter = info.getConverter()) {
3369 rewriter.setInsertionPoint(op);
3370 SmallVector<Value> newMaterialization;
3371 switch (info.getMaterializationKind()) {
3372 case MaterializationKind::Target:
3373 newMaterialization = converter->materializeTargetConversion(
3374 builder&: rewriter, loc: op->getLoc(), resultType: op.getResultTypes(), inputs: inputOperands,
3375 originalType: info.getOriginalType());
3376 break;
3377 case MaterializationKind::Source:
3378 assert(op->getNumResults() == 1 && "expected single result");
3379 Value sourceMat = converter->materializeSourceConversion(
3380 builder&: rewriter, loc: op->getLoc(), resultType: op.getResultTypes().front(), inputs: inputOperands);
3381 if (sourceMat)
3382 newMaterialization.push_back(Elt: sourceMat);
3383 break;
3384 }
3385 if (!newMaterialization.empty()) {
3386#ifndef NDEBUG
3387 ValueRange newMaterializationRange(newMaterialization);
3388 assert(TypeRange(newMaterializationRange) == op.getResultTypes() &&
3389 "materialization callback produced value of incorrect type");
3390#endif // NDEBUG
3391 rewriter.replaceOp(op, newValues: newMaterialization);
3392 return success();
3393 }
3394 StringRef direction =
3395 info.getMaterializationKind() == MaterializationKind::Target ? "target"
3396 : "source";
3397 InFlightDiagnostic diag =
3398 op.emitError()
3399 << "failed to legalize unresolved " << direction
3400 << " materialization from (" << inputOperands.getTypes() << ") to ("
3401 << op.getResultTypes()
3402 << ") that remained live after conversion (no matching callback)";
3403 diag.attachNote(noteLoc: op->getUsers().begin()->getLoc())
3404 << "see existing live user here: " << *op->getUsers().begin();
3405 return failure();
3406 }
3407
3408 InFlightDiagnostic diag =
3409 op->emitError()
3410 << "failed to legalize unresolved materialization "
3411 "from ("
3412 << inputOperands.getTypes() << ") to (" << op.getResultTypes()
3413 << ") that remained live after conversion (no type converter specified)";
3414 diag.attachNote(noteLoc: op->getUsers().begin()->getLoc())
3415 << "see existing live user here: " << *op->getUsers().begin();
3416 return failure();
3417}
3418
3419template <typename Fn>
3420LogicalResult
3421OperationConverter::legalizeOperations(ArrayRef<Operation *> ops, Fn onFailure,
3422 bool isRecursiveLegalization) {
3423 const ConversionTarget &target = opLegalizer.getTarget();
3424
3425 // Compute the set of operations and blocks to convert.
3426 SmallVector<Operation *> toConvert;
3427 for (Operation *op : ops) {
3428 op->walk<WalkOrder::PreOrder, ForwardDominanceIterator<>>(
3429 [&](Operation *op) {
3430 toConvert.push_back(Elt: op);
3431 // Don't check this operation's children for conversion if the
3432 // operation is recursively legal.
3433 auto legalityInfo = target.isLegal(op);
3434 if (legalityInfo && legalityInfo->isRecursivelyLegal)
3435 return WalkResult::skip();
3436 return WalkResult::advance();
3437 });
3438 }
3439 for (Operation *op : toConvert) {
3440 if (failed(Result: convert(op, isRecursiveLegalization))) {
3441 // Failed to convert an operation.
3442 onFailure();
3443 return failure();
3444 }
3445 }
3446 return success();
3447}
3448
3449LogicalResult ConversionPatternRewriter::legalize(Operation *op) {
3450 return impl->opConverter.legalizeOperations(ops: op,
3451 /*isRecursiveLegalization=*/true);
3452}
3453
3454LogicalResult ConversionPatternRewriter::legalize(Region *r) {
3455 // Fast path: If the region is empty, there is nothing to legalize.
3456 if (r->empty())
3457 return success();
3458
3459 // Gather a list of all operations to legalize. This is done before
3460 // converting the entry block signature because unrealized_conversion_cast
3461 // ops should not be included.
3462 SmallVector<Operation *> ops;
3463 for (Block &b : *r)
3464 for (Operation &op : b)
3465 ops.push_back(Elt: &op);
3466
3467 // If the current pattern runs with a type converter, convert the entry block
3468 // signature.
3469 if (const TypeConverter *converter = impl->currentTypeConverter) {
3470 std::optional<TypeConverter::SignatureConversion> conversion =
3471 converter->convertBlockSignature(block: &r->front());
3472 if (!conversion)
3473 return failure();
3474 applySignatureConversion(block: &r->front(), conversion&: *conversion, converter);
3475 }
3476
3477 // Legalize all operations in the region. This includes all nested
3478 // operations.
3479 return impl->opConverter.legalizeOperations(ops,
3480 /*isRecursiveLegalization=*/true);
3481}
3482
3483LogicalResult OperationConverter::applyConversion(ArrayRef<Operation *> ops) {
3484 // Convert each operation and discard rewrites on failure.
3485 ConversionPatternRewriterImpl &rewriterImpl = rewriter.getImpl();
3486
3487 LogicalResult status = legalizeOperations(ops, /*onFailure=*/[&]() {
3488 // Dialect conversion failed.
3489 if (rewriterImpl.config.allowPatternRollback) {
3490 // Rollback is allowed: restore the original IR.
3491 rewriterImpl.undoRewrites();
3492 } else {
3493 // Rollback is not allowed: apply all modifications that have been
3494 // performed so far.
3495 rewriterImpl.applyRewrites();
3496 }
3497 });
3498 if (failed(Result: status))
3499 return failure();
3500
3501 // After a successful conversion, apply rewrites.
3502 rewriterImpl.applyRewrites();
3503
3504 // Reconcile all UnrealizedConversionCastOps that were inserted by the
3505 // dialect conversion frameworks. (Not the ones that were inserted by
3506 // patterns.)
3507 const llvm::MapVector<UnrealizedConversionCastOp,
3508 UnresolvedMaterializationInfo> &materializations =
3509 rewriterImpl.unresolvedMaterializations;
3510 SmallVector<UnrealizedConversionCastOp> remainingCastOps;
3511 reconcileUnrealizedCasts(castOps: materializations, remainingCastOps: &remainingCastOps);
3512
3513 // Drop markers.
3514 for (UnrealizedConversionCastOp castOp : remainingCastOps)
3515 castOp->removeDiscardableAttr(name: kPureTypeConversionMarker);
3516
3517 // Try to legalize all unresolved materializations.
3518 if (rewriter.getConfig().buildMaterializations) {
3519 // Use a new rewriter, so the modifications are not tracked for rollback
3520 // purposes etc.
3521 IRRewriter irRewriter(rewriterImpl.rewriter.getContext(),
3522 rewriter.getConfig().listener);
3523 for (UnrealizedConversionCastOp castOp : remainingCastOps) {
3524 auto it = materializations.find(Key: castOp);
3525 assert(it != materializations.end() && "inconsistent state");
3526 if (failed(Result: legalizeUnresolvedMaterialization(rewriter&: irRewriter, op: castOp,
3527 info: it->second)))
3528 return failure();
3529 }
3530 }
3531
3532 return success();
3533}
3534
3535//===----------------------------------------------------------------------===//
3536// Type Conversion
3537//===----------------------------------------------------------------------===//
3538
3539void TypeConverter::SignatureConversion::addInputs(unsigned origInputNo,
3540 ArrayRef<Type> types) {
3541 assert(!types.empty() && "expected valid types");
3542 remapInput(origInputNo, /*newInputNo=*/argTypes.size(), newInputCount: types.size());
3543 addInputs(types);
3544}
3545
3546void TypeConverter::SignatureConversion::addInputs(ArrayRef<Type> types) {
3547 assert(!types.empty() &&
3548 "1->0 type remappings don't need to be added explicitly");
3549 argTypes.append(in_start: types.begin(), in_end: types.end());
3550}
3551
3552void TypeConverter::SignatureConversion::remapInput(unsigned origInputNo,
3553 unsigned newInputNo,
3554 unsigned newInputCount) {
3555 assert(!remappedInputs[origInputNo] && "input has already been remapped");
3556 assert(newInputCount != 0 && "expected valid input count");
3557 remappedInputs[origInputNo] =
3558 InputMapping{.inputNo: newInputNo, .size: newInputCount, /*replacementValues=*/{}};
3559}
3560
3561void TypeConverter::SignatureConversion::remapInput(
3562 unsigned origInputNo, ArrayRef<Value> replacements) {
3563 assert(!remappedInputs[origInputNo] && "input has already been remapped");
3564 remappedInputs[origInputNo] = InputMapping{
3565 .inputNo: origInputNo, /*size=*/0,
3566 .replacementValues: SmallVector<Value, 1>(replacements.begin(), replacements.end())};
3567}
3568
3569/// Internal implementation of the type conversion.
3570/// This is used with either a Type or a Value as the first argument.
3571/// - we can cache the context-free conversions until the last registered
3572/// context-aware conversion.
3573/// - we can't cache the result of type conversion happening after context-aware
3574/// conversions, because the type converter may return different results for the
3575/// same input type.
3576LogicalResult
3577TypeConverter::convertTypeImpl(PointerUnion<Type, Value> typeOrValue,
3578 SmallVectorImpl<Type> &results) const {
3579 assert(typeOrValue && "expected non-null type");
3580 Type t = (isa<Value>(Val: typeOrValue)) ? cast<Value>(Val&: typeOrValue).getType()
3581 : cast<Type>(Val&: typeOrValue);
3582 {
3583 std::shared_lock<decltype(cacheMutex)> cacheReadLock(cacheMutex,
3584 std::defer_lock);
3585 if (t.getContext()->isMultithreadingEnabled())
3586 cacheReadLock.lock();
3587 auto existingIt = cachedDirectConversions.find(Val: t);
3588 if (existingIt != cachedDirectConversions.end()) {
3589 if (existingIt->second)
3590 results.push_back(Elt: existingIt->second);
3591 return success(IsSuccess: existingIt->second != nullptr);
3592 }
3593 auto multiIt = cachedMultiConversions.find(Val: t);
3594 if (multiIt != cachedMultiConversions.end()) {
3595 results.append(in_start: multiIt->second.begin(), in_end: multiIt->second.end());
3596 return success();
3597 }
3598 }
3599 // Walk the added converters in reverse order to apply the most recently
3600 // registered first.
3601 size_t currentCount = results.size();
3602
3603 // We can cache the context-free conversions until the last registered
3604 // context-aware conversion. But only if we're processing a Value right now.
3605 auto isCacheable = [&](int index) {
3606 int numberOfConversionsUntilContextAware =
3607 conversions.size() - 1 - contextAwareTypeConversionsIndex;
3608 return index < numberOfConversionsUntilContextAware;
3609 };
3610
3611 std::unique_lock<decltype(cacheMutex)> cacheWriteLock(cacheMutex,
3612 std::defer_lock);
3613
3614 for (auto indexedConverter : llvm::enumerate(First: llvm::reverse(C: conversions))) {
3615 const ConversionCallbackFn &converter = indexedConverter.value();
3616 std::optional<LogicalResult> result = converter(typeOrValue, results);
3617 if (!result) {
3618 assert(results.size() == currentCount &&
3619 "failed type conversion should not change results");
3620 continue;
3621 }
3622 if (!isCacheable(indexedConverter.index()))
3623 return success();
3624 if (t.getContext()->isMultithreadingEnabled())
3625 cacheWriteLock.lock();
3626 if (!succeeded(Result: *result)) {
3627 assert(results.size() == currentCount &&
3628 "failed type conversion should not change results");
3629 cachedDirectConversions.try_emplace(Key: t, Args: nullptr);
3630 return failure();
3631 }
3632 auto newTypes = ArrayRef<Type>(results).drop_front(N: currentCount);
3633 if (newTypes.size() == 1)
3634 cachedDirectConversions.try_emplace(Key: t, Args: newTypes.front());
3635 else
3636 cachedMultiConversions.try_emplace(Key: t, Args: llvm::to_vector<2>(Range&: newTypes));
3637 return success();
3638 }
3639 return failure();
3640}
3641
3642LogicalResult TypeConverter::convertType(Type t,
3643 SmallVectorImpl<Type> &results) const {
3644 return convertTypeImpl(typeOrValue: t, results);
3645}
3646
3647LogicalResult TypeConverter::convertType(Value v,
3648 SmallVectorImpl<Type> &results) const {
3649 return convertTypeImpl(typeOrValue: v, results);
3650}
3651
3652Type TypeConverter::convertType(Type t) const {
3653 // Use the multi-type result version to convert the type.
3654 SmallVector<Type, 1> results;
3655 if (failed(Result: convertType(t, results)))
3656 return nullptr;
3657
3658 // Check to ensure that only one type was produced.
3659 return results.size() == 1 ? results.front() : nullptr;
3660}
3661
3662Type TypeConverter::convertType(Value v) const {
3663 // Use the multi-type result version to convert the type.
3664 SmallVector<Type, 1> results;
3665 if (failed(Result: convertType(v, results)))
3666 return nullptr;
3667
3668 // Check to ensure that only one type was produced.
3669 return results.size() == 1 ? results.front() : nullptr;
3670}
3671
3672LogicalResult
3673TypeConverter::convertTypes(TypeRange types,
3674 SmallVectorImpl<Type> &results) const {
3675 for (Type type : types)
3676 if (failed(Result: convertType(t: type, results)))
3677 return failure();
3678 return success();
3679}
3680
3681LogicalResult
3682TypeConverter::convertTypes(ValueRange values,
3683 SmallVectorImpl<Type> &results) const {
3684 for (Value value : values)
3685 if (failed(Result: convertType(v: value, results)))
3686 return failure();
3687 return success();
3688}
3689
3690bool TypeConverter::isLegal(Type type) const {
3691 return convertType(t: type) == type;
3692}
3693
3694bool TypeConverter::isLegal(Value value) const {
3695 return convertType(v: value) == value.getType();
3696}
3697
3698bool TypeConverter::isLegal(Operation *op) const {
3699 return isLegal(range: op->getOperands()) && isLegal(range: op->getResults());
3700}
3701
3702bool TypeConverter::isLegal(Region *region) const {
3703 return llvm::all_of(
3704 Range&: *region, P: [this](Block &block) { return isLegal(range: block.getArguments()); });
3705}
3706
3707bool TypeConverter::isSignatureLegal(FunctionType ty) const {
3708 if (!isLegal(range: ty.getInputs()))
3709 return false;
3710 if (!isLegal(range: ty.getResults()))
3711 return false;
3712 return true;
3713}
3714
3715LogicalResult
3716TypeConverter::convertSignatureArg(unsigned inputNo, Type type,
3717 SignatureConversion &result) const {
3718 // Try to convert the given input type.
3719 SmallVector<Type, 1> convertedTypes;
3720 if (failed(Result: convertType(t: type, results&: convertedTypes)))
3721 return failure();
3722
3723 // If this argument is being dropped, there is nothing left to do.
3724 if (convertedTypes.empty())
3725 return success();
3726
3727 // Otherwise, add the new inputs.
3728 result.addInputs(origInputNo: inputNo, types: convertedTypes);
3729 return success();
3730}
3731LogicalResult
3732TypeConverter::convertSignatureArgs(TypeRange types,
3733 SignatureConversion &result,
3734 unsigned origInputOffset) const {
3735 for (unsigned i = 0, e = types.size(); i != e; ++i)
3736 if (failed(Result: convertSignatureArg(inputNo: origInputOffset + i, type: types[i], result)))
3737 return failure();
3738 return success();
3739}
3740LogicalResult
3741TypeConverter::convertSignatureArg(unsigned inputNo, Value value,
3742 SignatureConversion &result) const {
3743 // Try to convert the given input type.
3744 SmallVector<Type, 1> convertedTypes;
3745 if (failed(Result: convertType(v: value, results&: convertedTypes)))
3746 return failure();
3747
3748 // If this argument is being dropped, there is nothing left to do.
3749 if (convertedTypes.empty())
3750 return success();
3751
3752 // Otherwise, add the new inputs.
3753 result.addInputs(origInputNo: inputNo, types: convertedTypes);
3754 return success();
3755}
3756LogicalResult
3757TypeConverter::convertSignatureArgs(ValueRange values,
3758 SignatureConversion &result,
3759 unsigned origInputOffset) const {
3760 for (unsigned i = 0, e = values.size(); i != e; ++i)
3761 if (failed(Result: convertSignatureArg(inputNo: origInputOffset + i, value: values[i], result)))
3762 return failure();
3763 return success();
3764}
3765
3766Value TypeConverter::materializeSourceConversion(OpBuilder &builder,
3767 Location loc, Type resultType,
3768 ValueRange inputs) const {
3769 for (const SourceMaterializationCallbackFn &fn :
3770 llvm::reverse(C: sourceMaterializations))
3771 if (Value result = fn(builder, resultType, inputs, loc))
3772 return result;
3773 return nullptr;
3774}
3775
3776Value TypeConverter::materializeTargetConversion(OpBuilder &builder,
3777 Location loc, Type resultType,
3778 ValueRange inputs,
3779 Type originalType) const {
3780 SmallVector<Value> result = materializeTargetConversion(
3781 builder, loc, resultType: TypeRange(resultType), inputs, originalType);
3782 if (result.empty())
3783 return nullptr;
3784 assert(result.size() == 1 && "expected single result");
3785 return result.front();
3786}
3787
3788SmallVector<Value> TypeConverter::materializeTargetConversion(
3789 OpBuilder &builder, Location loc, TypeRange resultTypes, ValueRange inputs,
3790 Type originalType) const {
3791 for (const TargetMaterializationCallbackFn &fn :
3792 llvm::reverse(C: targetMaterializations)) {
3793 SmallVector<Value> result =
3794 fn(builder, resultTypes, inputs, loc, originalType);
3795 if (result.empty())
3796 continue;
3797 assert(TypeRange(ValueRange(result)) == resultTypes &&
3798 "callback produced incorrect number of values or values with "
3799 "incorrect types");
3800 return result;
3801 }
3802 return {};
3803}
3804
3805std::optional<TypeConverter::SignatureConversion>
3806TypeConverter::convertBlockSignature(Block *block) const {
3807 SignatureConversion conversion(block->getNumArguments());
3808 if (failed(Result: convertSignatureArgs(values: block->getArguments(), result&: conversion)))
3809 return std::nullopt;
3810 return conversion;
3811}
3812
3813//===----------------------------------------------------------------------===//
3814// Type attribute conversion
3815//===----------------------------------------------------------------------===//
3816TypeConverter::AttributeConversionResult
3817TypeConverter::AttributeConversionResult::result(Attribute attr) {
3818 return AttributeConversionResult(attr, resultTag);
3819}
3820
3821TypeConverter::AttributeConversionResult
3822TypeConverter::AttributeConversionResult::na() {
3823 return AttributeConversionResult(nullptr, naTag);
3824}
3825
3826TypeConverter::AttributeConversionResult
3827TypeConverter::AttributeConversionResult::abort() {
3828 return AttributeConversionResult(nullptr, abortTag);
3829}
3830
3831bool TypeConverter::AttributeConversionResult::hasResult() const {
3832 return impl.getInt() == resultTag;
3833}
3834
3835bool TypeConverter::AttributeConversionResult::isNa() const {
3836 return impl.getInt() == naTag;
3837}
3838
3839bool TypeConverter::AttributeConversionResult::isAbort() const {
3840 return impl.getInt() == abortTag;
3841}
3842
3843Attribute TypeConverter::AttributeConversionResult::getResult() const {
3844 assert(hasResult() && "Cannot get result from N/A or abort");
3845 return impl.getPointer();
3846}
3847
3848std::optional<Attribute>
3849TypeConverter::convertTypeAttribute(Type type, Attribute attr) const {
3850 for (const TypeAttributeConversionCallbackFn &fn :
3851 llvm::reverse(C: typeAttributeConversions)) {
3852 AttributeConversionResult res = fn(type, attr);
3853 if (res.hasResult())
3854 return res.getResult();
3855 if (res.isAbort())
3856 return std::nullopt;
3857 }
3858 return std::nullopt;
3859}
3860
3861//===----------------------------------------------------------------------===//
3862// FunctionOpInterfaceSignatureConversion
3863//===----------------------------------------------------------------------===//
3864
3865static LogicalResult convertFuncOpTypes(FunctionOpInterface funcOp,
3866 const TypeConverter &typeConverter,
3867 ConversionPatternRewriter &rewriter) {
3868 FunctionType type = dyn_cast<FunctionType>(Val: funcOp.getFunctionType());
3869 if (!type)
3870 return failure();
3871
3872 // Convert the function signature (inputs and results).
3873 TypeConverter::SignatureConversion funcConversion(type.getNumInputs());
3874 SmallVector<Type, 1> newResults;
3875 if (failed(Result: typeConverter.convertSignatureArgs(types: type.getInputs(),
3876 result&: funcConversion)) ||
3877 failed(Result: typeConverter.convertTypes(types: type.getResults(), results&: newResults)))
3878 return failure();
3879
3880 // If the function has a body, apply a separate signature conversion to the
3881 // entry block. Some function ops (e.g., gpu.func) have extra block arguments
3882 // beyond the function type inputs (e.g., workgroup memory arguments that are
3883 // not part of the public signature). Use a distinct conversion sized for all
3884 // entry block arguments so that applySignatureConversion does not access
3885 // out-of-bounds mappings.
3886 if (!funcOp.getFunctionBody().empty()) {
3887 Block *entryBlock = &funcOp.getFunctionBody().front();
3888 unsigned numEntryBlockArgs = entryBlock->getNumArguments();
3889 unsigned numFuncTypeInputs = type.getNumInputs();
3890 TypeConverter::SignatureConversion blockConversion(numEntryBlockArgs);
3891 // Convert the function-type inputs the same way as for the function type.
3892 if (failed(Result: typeConverter.convertSignatureArgs(types: type.getInputs(),
3893 result&: blockConversion)))
3894 return failure();
3895 // Add identity mappings for extra block args beyond the function type
3896 // inputs. These arguments are preserved as-is.
3897 for (unsigned i = numFuncTypeInputs; i < numEntryBlockArgs; ++i)
3898 blockConversion.addInputs(origInputNo: i, types: entryBlock->getArgument(i).getType());
3899 rewriter.applySignatureConversion(block: entryBlock, conversion&: blockConversion,
3900 converter: &typeConverter);
3901 }
3902
3903 auto newType = FunctionType::get(
3904 context: rewriter.getContext(), inputs: funcConversion.getConvertedTypes(), results: newResults);
3905
3906 rewriter.modifyOpInPlace(root: funcOp, callable: [&] { funcOp.setType(newType); });
3907
3908 return success();
3909}
3910
3911/// Create a default conversion pattern that rewrites the type signature of a
3912/// FunctionOpInterface op. This only supports ops which use FunctionType to
3913/// represent their type.
3914namespace {
3915struct FunctionOpInterfaceSignatureConversion : public ConversionPattern {
3916 FunctionOpInterfaceSignatureConversion(StringRef functionLikeOpName,
3917 MLIRContext *ctx,
3918 const TypeConverter &converter,
3919 PatternBenefit benefit)
3920 : ConversionPattern(converter, functionLikeOpName, benefit, ctx) {}
3921
3922 LogicalResult
3923 matchAndRewrite(Operation *op, ArrayRef<Value> /*operands*/,
3924 ConversionPatternRewriter &rewriter) const override {
3925 FunctionOpInterface funcOp = cast<FunctionOpInterface>(Val: op);
3926 return convertFuncOpTypes(funcOp, typeConverter: *typeConverter, rewriter);
3927 }
3928};
3929
3930struct AnyFunctionOpInterfaceSignatureConversion
3931 : public OpInterfaceConversionPattern<FunctionOpInterface> {
3932 using Base::Base;
3933
3934 LogicalResult
3935 matchAndRewrite(FunctionOpInterface funcOp, ArrayRef<Value> /*operands*/,
3936 ConversionPatternRewriter &rewriter) const override {
3937 return convertFuncOpTypes(funcOp, typeConverter: *typeConverter, rewriter);
3938 }
3939};
3940} // namespace
3941
3942FailureOr<Operation *>
3943mlir::convertOpResultTypes(Operation *op, ValueRange operands,
3944 const TypeConverter &converter,
3945 ConversionPatternRewriter &rewriter) {
3946 assert(op && "Invalid op");
3947 Location loc = op->getLoc();
3948 if (converter.isLegal(op))
3949 return rewriter.notifyMatchFailure(arg&: loc, msg: "op already legal");
3950
3951 OperationState newOp(loc, op->getName());
3952 newOp.addOperands(newOperands: operands);
3953
3954 SmallVector<Type> newResultTypes;
3955 if (failed(Result: converter.convertTypes(values: op->getResults(), results&: newResultTypes)))
3956 return rewriter.notifyMatchFailure(arg&: loc, msg: "couldn't convert return types");
3957
3958 newOp.addTypes(newTypes: newResultTypes);
3959 newOp.addAttributes(newAttributes: op->getDiscardableAttrDictionary().getValue());
3960 newOp.propertiesAttr = op->getPropertiesAsAttribute();
3961 return rewriter.create(state: newOp);
3962}
3963
3964void mlir::populateFunctionOpInterfaceTypeConversionPattern(
3965 StringRef functionLikeOpName, RewritePatternSet &patterns,
3966 const TypeConverter &converter, PatternBenefit benefit) {
3967 patterns.add<FunctionOpInterfaceSignatureConversion>(
3968 arg&: functionLikeOpName, args: patterns.getContext(), args: converter, args&: benefit);
3969}
3970
3971void mlir::populateAnyFunctionOpInterfaceTypeConversionPattern(
3972 RewritePatternSet &patterns, const TypeConverter &converter,
3973 PatternBenefit benefit) {
3974 patterns.add<AnyFunctionOpInterfaceSignatureConversion>(
3975 arg: converter, args: patterns.getContext(), args&: benefit);
3976}
3977
3978//===----------------------------------------------------------------------===//
3979// ConversionTarget
3980//===----------------------------------------------------------------------===//
3981
3982void ConversionTarget::setOpAction(OperationName op,
3983 LegalizationAction action) {
3984 legalOperations[op].action = action;
3985}
3986
3987void ConversionTarget::setDialectAction(ArrayRef<StringRef> dialectNames,
3988 LegalizationAction action) {
3989 for (StringRef dialect : dialectNames)
3990 legalDialects[dialect] = action;
3991}
3992
3993auto ConversionTarget::getOpAction(OperationName op) const
3994 -> std::optional<LegalizationAction> {
3995 std::optional<LegalizationInfo> info = getOpInfo(op);
3996 return info ? info->action : std::optional<LegalizationAction>();
3997}
3998
3999auto ConversionTarget::isLegal(Operation *op) const
4000 -> std::optional<LegalOpDetails> {
4001 std::optional<LegalizationInfo> info = getOpInfo(op: op->getName());
4002 if (!info)
4003 return std::nullopt;
4004
4005 // Returns true if this operation instance is known to be legal.
4006 auto isOpLegal = [&] {
4007 // Handle dynamic legality either with the provided legality function.
4008 if (info->action == LegalizationAction::Dynamic) {
4009 std::optional<bool> result = info->legalityFn(op);
4010 if (result)
4011 return *result;
4012 }
4013
4014 // Otherwise, the operation is only legal if it was marked 'Legal'.
4015 return info->action == LegalizationAction::Legal;
4016 };
4017 if (!isOpLegal())
4018 return std::nullopt;
4019
4020 // This operation is legal, compute any additional legality information.
4021 LegalOpDetails legalityDetails;
4022 if (info->isRecursivelyLegal) {
4023 auto legalityFnIt = opRecursiveLegalityFns.find(Val: op->getName());
4024 if (legalityFnIt != opRecursiveLegalityFns.end()) {
4025 legalityDetails.isRecursivelyLegal =
4026 legalityFnIt->second(op).value_or(u: true);
4027 } else {
4028 legalityDetails.isRecursivelyLegal = true;
4029 }
4030 }
4031 return legalityDetails;
4032}
4033
4034bool ConversionTarget::isIllegal(Operation *op) const {
4035 std::optional<LegalizationInfo> info = getOpInfo(op: op->getName());
4036 if (!info)
4037 return false;
4038
4039 if (info->action == LegalizationAction::Dynamic) {
4040 std::optional<bool> result = info->legalityFn(op);
4041 if (!result)
4042 return false;
4043
4044 return !(*result);
4045 }
4046
4047 return info->action == LegalizationAction::Illegal;
4048}
4049
4050static ConversionTarget::DynamicLegalityCallbackFn composeLegalityCallbacks(
4051 ConversionTarget::DynamicLegalityCallbackFn oldCallback,
4052 ConversionTarget::DynamicLegalityCallbackFn newCallback) {
4053 if (!oldCallback)
4054 return newCallback;
4055
4056 auto chain = [oldCl = std::move(oldCallback), newCl = std::move(newCallback)](
4057 Operation *op) -> std::optional<bool> {
4058 if (std::optional<bool> result = newCl(op))
4059 return *result;
4060
4061 return oldCl(op);
4062 };
4063 return chain;
4064}
4065
4066void ConversionTarget::setLegalityCallback(
4067 OperationName name, const DynamicLegalityCallbackFn &callback) {
4068 assert(callback && "expected valid legality callback");
4069 auto *infoIt = legalOperations.find(Key: name);
4070 assert(infoIt != legalOperations.end() &&
4071 infoIt->second.action == LegalizationAction::Dynamic &&
4072 "expected operation to already be marked as dynamically legal");
4073 infoIt->second.legalityFn =
4074 composeLegalityCallbacks(oldCallback: std::move(infoIt->second.legalityFn), newCallback: callback);
4075}
4076
4077void ConversionTarget::markOpRecursivelyLegal(
4078 OperationName name, const DynamicLegalityCallbackFn &callback) {
4079 auto *infoIt = legalOperations.find(Key: name);
4080 assert(infoIt != legalOperations.end() &&
4081 infoIt->second.action != LegalizationAction::Illegal &&
4082 "expected operation to already be marked as legal");
4083 infoIt->second.isRecursivelyLegal = true;
4084 if (callback)
4085 opRecursiveLegalityFns[name] = composeLegalityCallbacks(
4086 oldCallback: std::move(opRecursiveLegalityFns[name]), newCallback: callback);
4087 else
4088 opRecursiveLegalityFns.erase(Val: name);
4089}
4090
4091void ConversionTarget::setLegalityCallback(
4092 ArrayRef<StringRef> dialects, const DynamicLegalityCallbackFn &callback) {
4093 assert(callback && "expected valid legality callback");
4094 for (StringRef dialect : dialects)
4095 dialectLegalityFns[dialect] = composeLegalityCallbacks(
4096 oldCallback: std::move(dialectLegalityFns[dialect]), newCallback: callback);
4097}
4098
4099void ConversionTarget::setLegalityCallback(
4100 const DynamicLegalityCallbackFn &callback) {
4101 assert(callback && "expected valid legality callback");
4102 unknownLegalityFn = composeLegalityCallbacks(oldCallback: unknownLegalityFn, newCallback: callback);
4103}
4104
4105auto ConversionTarget::getOpInfo(OperationName op) const
4106 -> std::optional<LegalizationInfo> {
4107 // Check for info for this specific operation.
4108 const auto *it = legalOperations.find(Key: op);
4109 if (it != legalOperations.end())
4110 return it->second;
4111 // Check for info for the parent dialect.
4112 auto dialectIt = legalDialects.find(Key: op.getDialectNamespace());
4113 if (dialectIt != legalDialects.end()) {
4114 DynamicLegalityCallbackFn callback;
4115 auto dialectFn = dialectLegalityFns.find(Key: op.getDialectNamespace());
4116 if (dialectFn != dialectLegalityFns.end())
4117 callback = dialectFn->second;
4118 return LegalizationInfo{.action: dialectIt->second, /*isRecursivelyLegal=*/false,
4119 .legalityFn: callback};
4120 }
4121 // Otherwise, check if we mark unknown operations as dynamic.
4122 if (unknownLegalityFn)
4123 return LegalizationInfo{.action: LegalizationAction::Dynamic,
4124 /*isRecursivelyLegal=*/false, .legalityFn: unknownLegalityFn};
4125 return std::nullopt;
4126}
4127
4128#if MLIR_ENABLE_PDL_IN_PATTERNMATCH
4129//===----------------------------------------------------------------------===//
4130// PDL Configuration
4131//===----------------------------------------------------------------------===//
4132
4133void PDLConversionConfig::notifyRewriteBegin(PatternRewriter &rewriter) {
4134 auto &rewriterImpl =
4135 static_cast<ConversionPatternRewriter &>(rewriter).getImpl();
4136 rewriterImpl.currentTypeConverter = getTypeConverter();
4137}
4138
4139void PDLConversionConfig::notifyRewriteEnd(PatternRewriter &rewriter) {
4140 auto &rewriterImpl =
4141 static_cast<ConversionPatternRewriter &>(rewriter).getImpl();
4142 rewriterImpl.currentTypeConverter = nullptr;
4143}
4144
4145/// Remap the given value using the rewriter and the type converter in the
4146/// provided config.
4147static FailureOr<SmallVector<Value>>
4148pdllConvertValues(ConversionPatternRewriter &rewriter, ValueRange values) {
4149 SmallVector<Value> mappedValues;
4150 if (failed(rewriter.getRemappedValues(values, mappedValues)))
4151 return failure();
4152 return std::move(mappedValues);
4153}
4154
4155void mlir::registerConversionPDLFunctions(RewritePatternSet &patterns) {
4156 patterns.getPDLPatterns().registerRewriteFunction(
4157 "convertValue",
4158 [](PatternRewriter &rewriter, Value value) -> FailureOr<Value> {
4159 auto results = pdllConvertValues(
4160 static_cast<ConversionPatternRewriter &>(rewriter), value);
4161 if (failed(results))
4162 return failure();
4163 return results->front();
4164 });
4165 patterns.getPDLPatterns().registerRewriteFunction(
4166 "convertValues", [](PatternRewriter &rewriter, ValueRange values) {
4167 return pdllConvertValues(
4168 static_cast<ConversionPatternRewriter &>(rewriter), values);
4169 });
4170 patterns.getPDLPatterns().registerRewriteFunction(
4171 "convertType",
4172 [](PatternRewriter &rewriter, Type type) -> FailureOr<Type> {
4173 auto &rewriterImpl =
4174 static_cast<ConversionPatternRewriter &>(rewriter).getImpl();
4175 if (const TypeConverter *converter =
4176 rewriterImpl.currentTypeConverter) {
4177 if (Type newType = converter->convertType(type))
4178 return newType;
4179 return failure();
4180 }
4181 return type;
4182 });
4183 patterns.getPDLPatterns().registerRewriteFunction(
4184 "convertTypes",
4185 [](PatternRewriter &rewriter,
4186 TypeRange types) -> FailureOr<SmallVector<Type>> {
4187 auto &rewriterImpl =
4188 static_cast<ConversionPatternRewriter &>(rewriter).getImpl();
4189 const TypeConverter *converter = rewriterImpl.currentTypeConverter;
4190 if (!converter)
4191 return SmallVector<Type>(types);
4192
4193 SmallVector<Type> remappedTypes;
4194 if (failed(converter->convertTypes(types, remappedTypes)))
4195 return failure();
4196 return std::move(remappedTypes);
4197 });
4198}
4199#endif // MLIR_ENABLE_PDL_IN_PATTERNMATCH
4200
4201//===----------------------------------------------------------------------===//
4202// Op Conversion Entry Points
4203//===----------------------------------------------------------------------===//
4204
4205namespace {
4206/// This is the type of Action that is dispatched when a conversion is applied.
4207class ApplyConversionAction
4208 : public tracing::ActionImpl<ApplyConversionAction> {
4209public:
4210 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(ApplyConversionAction)
4211 using Base = tracing::ActionImpl<ApplyConversionAction>;
4212 ApplyConversionAction(ArrayRef<IRUnit> irUnits) : Base(irUnits) {}
4213 static constexpr StringLiteral tag = "apply-conversion";
4214
4215 void print(raw_ostream &os) const override { os << tag; }
4216};
4217} // namespace
4218
4219static LogicalResult applyConversion(ArrayRef<Operation *> ops,
4220 const ConversionTarget &target,
4221 const FrozenRewritePatternSet &patterns,
4222 ConversionConfig config,
4223 OpConversionMode mode) {
4224 if (ops.empty())
4225 return success();
4226 MLIRContext *ctx = ops.front()->getContext();
4227 LogicalResult status = success();
4228 SmallVector<IRUnit> irUnits(ops.begin(), ops.end());
4229 ctx->executeAction<ApplyConversionAction>(
4230 actionFn: [&] {
4231 OperationConverter opConverter(ops.front()->getContext(), target,
4232 patterns, config, mode);
4233 status = opConverter.applyConversion(ops);
4234 },
4235 irUnits);
4236 return status;
4237}
4238
4239//===----------------------------------------------------------------------===//
4240// Partial Conversion
4241//===----------------------------------------------------------------------===//
4242
4243LogicalResult mlir::applyPartialConversion(
4244 ArrayRef<Operation *> ops, const ConversionTarget &target,
4245 const FrozenRewritePatternSet &patterns, ConversionConfig config) {
4246 return applyConversion(ops, target, patterns, config,
4247 mode: OpConversionMode::Partial);
4248}
4249LogicalResult
4250mlir::applyPartialConversion(Operation *op, const ConversionTarget &target,
4251 const FrozenRewritePatternSet &patterns,
4252 ConversionConfig config) {
4253 return applyPartialConversion(ops: llvm::ArrayRef(op), target, patterns, config);
4254}
4255
4256//===----------------------------------------------------------------------===//
4257// Full Conversion
4258//===----------------------------------------------------------------------===//
4259
4260LogicalResult mlir::applyFullConversion(ArrayRef<Operation *> ops,
4261 const ConversionTarget &target,
4262 const FrozenRewritePatternSet &patterns,
4263 ConversionConfig config) {
4264 return applyConversion(ops, target, patterns, config, mode: OpConversionMode::Full);
4265}
4266LogicalResult mlir::applyFullConversion(Operation *op,
4267 const ConversionTarget &target,
4268 const FrozenRewritePatternSet &patterns,
4269 ConversionConfig config) {
4270 return applyFullConversion(ops: llvm::ArrayRef(op), target, patterns, config);
4271}
4272
4273//===----------------------------------------------------------------------===//
4274// Analysis Conversion
4275//===----------------------------------------------------------------------===//
4276
4277/// Find a common IsolatedFromAbove ancestor of the given ops. If at least one
4278/// op is a top-level module op (which is expected to be isolated from above),
4279/// return that op.
4280static Operation *findCommonAncestor(ArrayRef<Operation *> ops) {
4281 // Check if there is a top-level operation within `ops`. If so, return that
4282 // op.
4283 for (Operation *op : ops) {
4284 if (!op->getParentOp()) {
4285#ifndef NDEBUG
4286 assert(op->hasTrait<OpTrait::IsIsolatedFromAbove>() &&
4287 "expected top-level op to be isolated from above");
4288 for (Operation *other : ops)
4289 assert(op->isAncestor(other) &&
4290 "expected ops to have a common ancestor");
4291#endif // NDEBUG
4292 return op;
4293 }
4294 }
4295
4296 // No top-level op. Find a common ancestor.
4297 Operation *commonAncestor =
4298 ops.front()->getParentWithTrait<OpTrait::IsIsolatedFromAbove>();
4299 for (Operation *op : ops.drop_front()) {
4300 while (!commonAncestor->isProperAncestor(other: op)) {
4301 commonAncestor =
4302 commonAncestor->getParentWithTrait<OpTrait::IsIsolatedFromAbove>();
4303 assert(commonAncestor &&
4304 "expected to find a common isolated from above ancestor");
4305 }
4306 }
4307
4308 return commonAncestor;
4309}
4310
4311LogicalResult mlir::applyAnalysisConversion(
4312 ArrayRef<Operation *> ops, ConversionTarget &target,
4313 const FrozenRewritePatternSet &patterns, ConversionConfig config) {
4314#ifndef NDEBUG
4315 if (config.legalizableOps)
4316 assert(config.legalizableOps->empty() && "expected empty set");
4317#endif // NDEBUG
4318
4319 // Clone closted common ancestor that is isolated from above.
4320 Operation *commonAncestor = findCommonAncestor(ops);
4321 IRMapping mapping;
4322 Operation *clonedAncestor = commonAncestor->clone(mapper&: mapping);
4323 // Compute inverse IR mapping.
4324 DenseMap<Operation *, Operation *> inverseOperationMap;
4325 for (auto &it : mapping.getOperationMap())
4326 inverseOperationMap[it.second] = it.first;
4327
4328 // Convert the cloned operations. The original IR will remain unchanged.
4329 SmallVector<Operation *> opsToConvert = llvm::map_to_vector(
4330 C&: ops, F: [&](Operation *op) { return mapping.lookup(from: op); });
4331 LogicalResult status = applyConversion(ops: opsToConvert, target, patterns, config,
4332 mode: OpConversionMode::Analysis);
4333
4334 // Remap `legalizableOps`, so that they point to the original ops and not the
4335 // cloned ops.
4336 if (config.legalizableOps) {
4337 DenseSet<Operation *> originalLegalizableOps;
4338 for (Operation *op : *config.legalizableOps)
4339 originalLegalizableOps.insert(V: inverseOperationMap[op]);
4340 *config.legalizableOps = std::move(originalLegalizableOps);
4341 }
4342
4343 // Erase the cloned IR.
4344 clonedAncestor->erase();
4345 return status;
4346}
4347
4348LogicalResult
4349mlir::applyAnalysisConversion(Operation *op, ConversionTarget &target,
4350 const FrozenRewritePatternSet &patterns,
4351 ConversionConfig config) {
4352 return applyAnalysisConversion(ops: llvm::ArrayRef(op), target, patterns, config);
4353}
4354