1//===- PatternMatch.cpp - Base classes for pattern match ------------------===//
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/IR/PatternMatch.h"
10#include "mlir/IR/Iterators.h"
11#include "mlir/IR/RegionKindInterface.h"
12#include "llvm/ADT/SmallPtrSet.h"
13
14using namespace mlir;
15
16//===----------------------------------------------------------------------===//
17// PatternBenefit
18//===----------------------------------------------------------------------===//
19
20PatternBenefit::PatternBenefit(unsigned benefit) : representation(benefit) {
21 assert(representation == benefit && benefit != ImpossibleToMatchSentinel &&
22 "This pattern match benefit is too large to represent");
23}
24
25unsigned short PatternBenefit::getBenefit() const {
26 assert(!isImpossibleToMatch() && "Pattern doesn't match");
27 return representation;
28}
29
30//===----------------------------------------------------------------------===//
31// Pattern
32//===----------------------------------------------------------------------===//
33
34//===----------------------------------------------------------------------===//
35// OperationName Root Constructors
36//===----------------------------------------------------------------------===//
37
38Pattern::Pattern(StringRef rootName, PatternBenefit benefit,
39 MLIRContext *context, ArrayRef<StringRef> generatedNames)
40 : Pattern(OperationName(rootName, context).getAsOpaquePointer(),
41 RootKind::OperationName, generatedNames, benefit, context) {}
42
43//===----------------------------------------------------------------------===//
44// MatchAnyOpTypeTag Root Constructors
45//===----------------------------------------------------------------------===//
46
47Pattern::Pattern(MatchAnyOpTypeTag tag, PatternBenefit benefit,
48 MLIRContext *context, ArrayRef<StringRef> generatedNames)
49 : Pattern(nullptr, RootKind::Any, generatedNames, benefit, context) {}
50
51//===----------------------------------------------------------------------===//
52// MatchInterfaceOpTypeTag Root Constructors
53//===----------------------------------------------------------------------===//
54
55Pattern::Pattern(MatchInterfaceOpTypeTag tag, TypeID interfaceID,
56 PatternBenefit benefit, MLIRContext *context,
57 ArrayRef<StringRef> generatedNames)
58 : Pattern(interfaceID.getAsOpaquePointer(), RootKind::InterfaceID,
59 generatedNames, benefit, context) {}
60
61//===----------------------------------------------------------------------===//
62// MatchTraitOpTypeTag Root Constructors
63//===----------------------------------------------------------------------===//
64
65Pattern::Pattern(MatchTraitOpTypeTag tag, TypeID traitID,
66 PatternBenefit benefit, MLIRContext *context,
67 ArrayRef<StringRef> generatedNames)
68 : Pattern(traitID.getAsOpaquePointer(), RootKind::TraitID, generatedNames,
69 benefit, context) {}
70
71//===----------------------------------------------------------------------===//
72// General Constructors
73//===----------------------------------------------------------------------===//
74
75Pattern::Pattern(const void *rootValue, RootKind rootKind,
76 ArrayRef<StringRef> generatedNames, PatternBenefit benefit,
77 MLIRContext *context)
78 : rootValue(rootValue), rootKind(rootKind), benefit(benefit),
79 contextAndHasBoundedRecursion(context, false) {
80 if (generatedNames.empty())
81 return;
82 generatedOps.reserve(N: generatedNames.size());
83 llvm::append_range(C&: generatedOps,
84 R: llvm::map_range(C&: generatedNames, F: [context](StringRef name) {
85 return OperationName(name, context);
86 }));
87}
88
89//===----------------------------------------------------------------------===//
90// RewritePattern
91//===----------------------------------------------------------------------===//
92
93/// Out-of-line vtable anchor.
94void RewritePattern::anchor() {}
95
96//===----------------------------------------------------------------------===//
97// RewriterBase
98//===----------------------------------------------------------------------===//
99
100bool RewriterBase::Listener::classof(const OpBuilder::Listener *base) {
101 return base->getKind() == OpBuilder::ListenerBase::Kind::RewriterBaseListener;
102}
103
104RewriterBase::~RewriterBase() {
105 // Out of line to provide a vtable anchor for the class.
106}
107
108void RewriterBase::replaceAllOpUsesWith(Operation *from, ValueRange to) {
109 // Notify the listener that we're about to replace this op.
110 if (auto *rewriteListener = dyn_cast_if_present<Listener>(Val: listener))
111 rewriteListener->notifyOperationReplaced(op: from, replacement: to);
112
113 replaceAllUsesWith(from: from->getResults(), to);
114}
115
116void RewriterBase::replaceAllOpUsesWith(Operation *from, Operation *to) {
117 // Notify the listener that we're about to replace this op.
118 if (auto *rewriteListener = dyn_cast_if_present<Listener>(Val: listener))
119 rewriteListener->notifyOperationReplaced(op: from, replacement: to);
120
121 replaceAllUsesWith(from: from->getResults(), to: to->getResults());
122}
123
124/// This method replaces the results of the operation with the specified list of
125/// values. The number of provided values must match the number of results of
126/// the operation. The replaced op is erased.
127void RewriterBase::replaceOp(Operation *op, ValueRange newValues) {
128 assert(op->getNumResults() == newValues.size() &&
129 "incorrect # of replacement values");
130
131 // Replace all result uses. Also notifies the listener of modifications.
132 replaceAllOpUsesWith(from: op, to: newValues);
133
134 // Erase op and notify listener.
135 eraseOp(op);
136}
137
138/// This method replaces the results of the operation with the specified new op
139/// (replacement). The number of results of the two operations must match. The
140/// replaced op is erased.
141void RewriterBase::replaceOp(Operation *op, Operation *newOp) {
142 assert(op && newOp && "expected non-null op");
143 assert(op->getNumResults() == newOp->getNumResults() &&
144 "ops have different number of results");
145
146 // Replace all result uses. Also notifies the listener of modifications.
147 replaceAllOpUsesWith(from: op, to: newOp->getResults());
148
149 // Erase op and notify listener.
150 eraseOp(op);
151}
152
153/// This method erases an operation that is known to have no uses. The uses of
154/// the given operation *must* be known to be dead.
155void RewriterBase::eraseOp(Operation *op) {
156 assert(op->use_empty() && "expected 'op' to have no uses");
157 auto *rewriteListener = dyn_cast_if_present<Listener>(Val: listener);
158
159 // If the current insertion point is before the erased operation, we adjust
160 // the insertion point to be after the operation.
161 if (getInsertionPoint() == op->getIterator())
162 setInsertionPointAfter(op);
163
164 // Fast path: If no listener is attached, the op can be dropped in one go.
165 if (!rewriteListener) {
166 op->erase();
167 return;
168 }
169
170 // Helper function that erases a single op.
171 auto eraseSingleOp = [&](Operation *op) {
172#ifndef NDEBUG
173 // All nested ops should have been erased already.
174 assert(
175 llvm::all_of(op->getRegions(), [&](Region &r) { return r.empty(); }) &&
176 "expected empty regions");
177 // All users should have been erased already if the op is in a region with
178 // SSA dominance.
179 if (!op->use_empty() && op->getParentOp())
180 assert(mayBeGraphRegion(*op->getParentRegion()) &&
181 "expected that op has no uses");
182#endif // NDEBUG
183 rewriteListener->notifyOperationErased(op);
184
185 // Explicitly drop all uses in case the op is in a graph region.
186 op->dropAllUses();
187 op->erase();
188 };
189
190 // Nested ops must be erased one-by-one, so that listeners have a consistent
191 // view of the IR every time a notification is triggered. Users must be
192 // erased before definitions. I.e., post-order, reverse dominance.
193 std::function<void(Operation *)> eraseTree = [&](Operation *op) {
194 // Erase nested ops.
195 for (Region &r : llvm::reverse(C: op->getRegions())) {
196 // Erase all blocks in the right order. Successors should be erased
197 // before predecessors because successor blocks may use values defined
198 // in predecessor blocks. A post-order traversal of blocks within a
199 // region visits successors before predecessors. Repeat the traversal
200 // until the region is empty. (The block graph could be disconnected.)
201 while (!r.empty()) {
202 SmallVector<Block *> erasedBlocks;
203 // Some blocks may have invalid successor, use a set including nullptr
204 // to avoid null pointer.
205 llvm::SmallPtrSet<Block *, 4> visited{nullptr};
206 for (Block *b : llvm::post_order_ext(G: &r.front(), S&: visited)) {
207 // Visit ops in reverse order.
208 for (Operation &op :
209 llvm::make_early_inc_range(Range: ReverseIterator::makeIterable(range&: *b)))
210 eraseTree(&op);
211 // Do not erase the block immediately. This is not supprted by the
212 // post_order iterator.
213 erasedBlocks.push_back(Elt: b);
214 }
215 for (Block *b : erasedBlocks) {
216 // Explicitly drop all uses in case there is a cycle in the block
217 // graph.
218 for (BlockArgument bbArg : b->getArguments())
219 bbArg.dropAllUses();
220 b->dropAllUses();
221 eraseBlock(block: b);
222 }
223 }
224 }
225 // Then erase the enclosing op.
226 eraseSingleOp(op);
227 };
228
229 eraseTree(op);
230}
231
232void RewriterBase::eraseBlock(Block *block) {
233 assert(block->use_empty() && "expected 'block' to have no uses");
234
235 for (auto &op : llvm::make_early_inc_range(Range: llvm::reverse(C&: *block))) {
236 assert(op.use_empty() && "expected 'op' to have no uses");
237 eraseOp(op: &op);
238 }
239
240 // Notify the listener that the block is about to be removed.
241 if (auto *rewriteListener = dyn_cast_if_present<Listener>(Val: listener))
242 rewriteListener->notifyBlockErased(block);
243
244 block->erase();
245}
246
247void RewriterBase::eraseOperands(Operation *op, const BitVector &eraseIndices) {
248 assert(eraseIndices.size() == op->getNumOperands() &&
249 "expected one bit per operand");
250 if (eraseIndices.none())
251 return;
252
253 modifyOpInPlace(root: op, callable: [&]() {
254 op->eraseOperands(eraseIndices);
255 if (!op->hasTrait<OpTrait::AttrSizedOperandSegments>())
256 return;
257
258 // TODO: Add an interface to update the operand segment-size property
259 // directly, without converting it to and from an attribute.
260 auto attrName = StringAttr::get(
261 context: op->getContext(),
262 bytes: OpTrait::AttrSizedOperandSegments<void>::getOperandSegmentSizeAttr());
263 auto sizes = op->getAttrOfType<DenseI32ArrayAttr>(name: attrName);
264 assert(sizes && "expected operand segment sizes attribute");
265 SmallVector<int32_t> newSizes(sizes.asArrayRef());
266 unsigned offset = 0;
267 for (int32_t &size : newSizes) {
268 // The attribute and bit vector still use the original operand indices.
269 unsigned end = offset + size;
270 for (; offset < end; ++offset)
271 size -= eraseIndices.test(Idx: offset);
272 }
273 op->setInherentAttr(name: attrName,
274 value: DenseI32ArrayAttr::get(context: op->getContext(), content: newSizes));
275 });
276}
277
278Operation *RewriterBase::eraseOpResults(Operation *op,
279 const BitVector &eraseIndices) {
280 assert(op->getNumResults() == eraseIndices.size() &&
281 "number of op results and bitvector size must match");
282
283 // Gather new result types.
284 SmallVector<Type> newResultTypes;
285 newResultTypes.reserve(N: op->getNumResults() - eraseIndices.count());
286 for (OpResult result : op->getResults())
287 if (!eraseIndices[result.getResultNumber()])
288 newResultTypes.push_back(Elt: result.getType());
289
290 // Create a new operation and inline all regions.
291 InsertionGuard g(*this);
292 setInsertionPoint(op);
293 OperationState state(op->getLoc(), op->getName().getStringRef(),
294 op->getOperands(), newResultTypes,
295 op->getDiscardableAttrDictionary().getValue());
296 state.propertiesAttr = op->getPropertiesAsAttribute();
297 for ([[maybe_unused]] auto i : llvm::seq<unsigned>(Begin: 0, End: op->getNumRegions()))
298 state.addRegion();
299 Operation *newOp = create(state);
300 for (const auto &[index, region] : llvm::enumerate(First: op->getRegions())) {
301 // Move all blocks of `region` into `newRegion`.
302 Region &newRegion = newOp->getRegion(index);
303 inlineRegionBefore(region, parent&: newRegion, before: newRegion.begin());
304 }
305
306 // Replace the original operation with the new operation.
307 SmallVector<Value> replacements(op->getNumResults(), Value());
308 unsigned nextResultIdx = 0;
309 for (auto i : llvm::seq<unsigned>(Begin: 0, End: op->getNumResults()))
310 if (!eraseIndices[i])
311 replacements[i] = newOp->getResult(idx: nextResultIdx++);
312 replaceOp(op, newValues: replacements);
313 return newOp;
314}
315
316void RewriterBase::finalizeOpModification(Operation *op) {
317 // Notify the listener that the operation was modified.
318 if (auto *rewriteListener = dyn_cast_if_present<Listener>(Val: listener))
319 rewriteListener->notifyOperationModified(op);
320}
321
322void RewriterBase::replaceAllUsesExcept(
323 Value from, Value to, const SmallPtrSetImpl<Operation *> &preservedUsers) {
324 replaceUsesWithIf(from, to, functor: [&](OpOperand &use) {
325 Operation *user = use.getOwner();
326 return !preservedUsers.contains(Ptr: user);
327 });
328}
329
330bool RewriterBase::replaceUsesWithIf(Value from, Value to,
331 function_ref<bool(OpOperand &)> functor,
332 bool *allUsesReplaced) {
333 bool replaced = false;
334 bool allReplaced = true;
335 for (OpOperand &operand : llvm::make_early_inc_range(Range: from.getUses())) {
336 bool replace = functor(operand);
337 if (replace) {
338 modifyOpInPlace(root: operand.getOwner(), callable: [&]() { operand.set(to); });
339 replaced = true;
340 }
341 allReplaced &= replace;
342 }
343 if (allUsesReplaced)
344 *allUsesReplaced = allReplaced;
345 return replaced;
346}
347
348bool RewriterBase::replaceUsesWithIf(ValueRange from, ValueRange to,
349 function_ref<bool(OpOperand &)> functor,
350 bool *allUsesReplaced) {
351 assert(from.size() == to.size() && "incorrect number of replacements");
352 bool replaced = false;
353 bool allReplaced = true;
354 for (auto it : llvm::zip_equal(t&: from, u&: to)) {
355 bool r = true;
356 replaced |=
357 replaceUsesWithIf(from: std::get<0>(t&: it), to: std::get<1>(t&: it), functor,
358 /*allUsesReplaced=*/allUsesReplaced ? &r : nullptr);
359 allReplaced &= r;
360 }
361 if (allUsesReplaced)
362 *allUsesReplaced = allReplaced;
363 return replaced;
364}
365
366void RewriterBase::inlineBlockBefore(Block *source, Block *dest,
367 Block::iterator before,
368 ValueRange argValues) {
369 assert(argValues.size() == source->getNumArguments() &&
370 "incorrect # of argument replacement values");
371
372 // The source block will be deleted, so it should not have any users (i.e.,
373 // there should be no predecessors).
374 assert(source->hasNoPredecessors() &&
375 "expected 'source' to have no predecessors");
376
377 if (dest->end() != before) {
378 // The source block will be inserted in the middle of the dest block, so
379 // the source block should have no successors. Otherwise, the remainder of
380 // the dest block would be unreachable.
381 assert(source->hasNoSuccessors() &&
382 "expected 'source' to have no successors");
383 } else {
384 // The source block will be inserted at the end of the dest block, so the
385 // dest block should have no successors. Otherwise, the inserted operations
386 // will be unreachable.
387 assert(dest->hasNoSuccessors() && "expected 'dest' to have no successors");
388 }
389
390 // Replace all of the successor arguments with the provided values.
391 for (auto it : llvm::zip(t: source->getArguments(), u&: argValues))
392 replaceAllUsesWith(from: std::get<0>(t&: it), to: std::get<1>(t&: it));
393
394 // Move operations from the source block to the dest block and erase the
395 // source block.
396 if (!listener) {
397 // Fast path: If no listener is attached, move all operations at once.
398 dest->getOperations().splice(where: before, L2&: source->getOperations());
399 } else {
400 while (!source->empty())
401 moveOpBefore(op: &source->front(), block: dest, iterator: before);
402 }
403
404 // If the current insertion point is within the source block, adjust the
405 // insertion point to the destination block.
406 if (getInsertionBlock() == source)
407 setInsertionPoint(block: dest, insertPoint: getInsertionPoint());
408
409 // Erase the source block.
410 assert(source->empty() && "expected 'source' to be empty");
411 eraseBlock(block: source);
412}
413
414void RewriterBase::inlineBlockBefore(Block *source, Operation *op,
415 ValueRange argValues) {
416 inlineBlockBefore(source, dest: op->getBlock(), before: op->getIterator(), argValues);
417}
418
419void RewriterBase::mergeBlocks(Block *source, Block *dest,
420 ValueRange argValues) {
421 inlineBlockBefore(source, dest, before: dest->end(), argValues);
422}
423
424/// Split the operations starting at "before" (inclusive) out of the given
425/// block into a new block, and return it.
426Block *RewriterBase::splitBlock(Block *block, Block::iterator before) {
427 // Fast path: If no listener is attached, split the block directly.
428 if (!listener)
429 return block->splitBlock(splitBefore: before);
430
431 // `createBlock` sets the insertion point at the beginning of the new block.
432 InsertionGuard g(*this);
433 Block *newBlock =
434 createBlock(parent: block->getParent(), insertPt: std::next(x: block->getIterator()));
435
436 // If `before` points to end of the block, no ops should be moved.
437 if (before == block->end())
438 return newBlock;
439
440 // Move ops one-by-one from the end of `block` to the beginning of `newBlock`.
441 // Stop when the operation pointed to by `before` has been moved.
442 while (before->getBlock() != newBlock)
443 moveOpBefore(op: &block->back(), block: newBlock, iterator: newBlock->begin());
444
445 return newBlock;
446}
447
448/// Move the blocks that belong to "region" before the given position in
449/// another region. The two regions must be different. The caller is in
450/// charge to update create the operation transferring the control flow to the
451/// region and pass it the correct block arguments.
452void RewriterBase::inlineRegionBefore(Region &region, Region &parent,
453 Region::iterator before) {
454 // Fast path: If no listener is attached, move all blocks at once.
455 if (!listener) {
456 parent.getBlocks().splice(where: before, L2&: region.getBlocks());
457 return;
458 }
459
460 // Move blocks from the beginning of the region one-by-one.
461 while (!region.empty())
462 moveBlockBefore(block: &region.front(), region: &parent, iterator: before);
463}
464void RewriterBase::inlineRegionBefore(Region &region, Block *before) {
465 inlineRegionBefore(region, parent&: *before->getParent(), before: before->getIterator());
466}
467
468void RewriterBase::moveBlockBefore(Block *block, Block *anotherBlock) {
469 moveBlockBefore(block, region: anotherBlock->getParent(),
470 iterator: anotherBlock->getIterator());
471}
472
473void RewriterBase::moveBlockBefore(Block *block, Region *region,
474 Region::iterator iterator) {
475 Region *currentRegion = block->getParent();
476 Region::iterator nextIterator = std::next(x: block->getIterator());
477 block->moveBefore(region, iterator);
478 if (listener)
479 listener->notifyBlockInserted(block, /*previous=*/currentRegion,
480 /*previousIt=*/nextIterator);
481}
482
483void RewriterBase::moveOpBefore(Operation *op, Operation *existingOp) {
484 moveOpBefore(op, block: existingOp->getBlock(), iterator: existingOp->getIterator());
485}
486
487void RewriterBase::moveOpBefore(Operation *op, Block *block,
488 Block::iterator iterator) {
489 Block *currentBlock = op->getBlock();
490 Block::iterator nextIterator = std::next(x: op->getIterator());
491 op->moveBefore(block, iterator);
492 if (listener)
493 listener->notifyOperationInserted(
494 op, /*previous=*/InsertPoint(currentBlock, nextIterator));
495}
496
497void RewriterBase::moveOpAfter(Operation *op, Operation *existingOp) {
498 moveOpAfter(op, block: existingOp->getBlock(), iterator: existingOp->getIterator());
499}
500
501void RewriterBase::moveOpAfter(Operation *op, Block *block,
502 Block::iterator iterator) {
503 assert(iterator != block->end() && "cannot move after end of block");
504 moveOpBefore(op, block, iterator: std::next(x: iterator));
505}
506