1//===- OperationSupport.cpp -----------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains out-of-line implementations of the support types that
10// Operation and related classes build on top of.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/IR/OperationSupport.h"
15#include "mlir/IR/BuiltinAttributes.h"
16#include "mlir/IR/BuiltinTypes.h"
17#include "mlir/IR/OpDefinition.h"
18#include "mlir/IR/OpImplementation.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/Support/SHA1.h"
21#include <numeric>
22#include <optional>
23
24using namespace mlir;
25
26void mlir::detail::appendAttributeProperty(
27 llvm::SmallVectorImpl<NamedAttribute> &attrs, StringRef name,
28 Attribute attr) {
29 if (attr)
30 attrs.emplace_back(Args&: name, Args&: attr);
31}
32
33ParseResult mlir::detail::parseOptionalOperandInto(
34 OpAsmParser &parser,
35 SmallVectorImpl<OpAsmParser::UnresolvedOperand> &operands) {
36 OpAsmParser::UnresolvedOperand operand;
37 OptionalParseResult result = parser.parseOptionalOperand(result&: operand);
38 if (!result.has_value())
39 return success();
40 if (failed(Result: *result))
41 return failure();
42 operands.push_back(Elt: operand);
43 return success();
44}
45
46ParseResult mlir::detail::parseOptionalTypeInto(AsmParser &parser,
47 SmallVectorImpl<Type> &types) {
48 Type type;
49 OptionalParseResult result = parser.parseOptionalType(result&: type);
50 if (!result.has_value())
51 return success();
52 if (failed(Result: *result))
53 return failure();
54 types.push_back(Elt: type);
55 return success();
56}
57
58void mlir::detail::splitPropertiesAndDiscardableAttributes(
59 OperationState &state, ArrayRef<NamedAttribute> attributes,
60 ArrayRef<StringRef> inherentNames,
61 llvm::function_ref<LogicalResult(DictionaryAttr)> setProperties) {
62 SmallVector<NamedAttribute> inherentAttributes;
63 for (const NamedAttribute &attr : attributes) {
64 StringRef name = attr.getName().getValue();
65 if (llvm::is_contained(Range&: inherentNames, Element: name))
66 inherentAttributes.push_back(Elt: attr);
67 else
68 state.addAttribute(name: attr.getName(), attr: attr.getValue());
69 }
70 if (inherentAttributes.empty())
71 return;
72 if (failed(Result: setProperties(
73 DictionaryAttr::get(context: state.getContext(), value: inherentAttributes))))
74 llvm::report_fatal_error(reason: "Property conversion failed.");
75}
76
77//===----------------------------------------------------------------------===//
78// NamedAttrList
79//===----------------------------------------------------------------------===//
80
81NamedAttrList::NamedAttrList(ArrayRef<NamedAttribute> attributes) {
82 assign(inStart: attributes.begin(), inEnd: attributes.end());
83}
84
85NamedAttrList::NamedAttrList(DictionaryAttr attributes)
86 : NamedAttrList(attributes ? attributes.getValue()
87 : ArrayRef<NamedAttribute>()) {
88 dictionarySorted.setPointerAndInt(PtrVal: attributes, IntVal: true);
89}
90
91NamedAttrList::NamedAttrList(const_iterator inStart, const_iterator inEnd) {
92 assign(inStart, inEnd);
93}
94
95ArrayRef<NamedAttribute> NamedAttrList::getAttrs() const { return attrs; }
96
97std::optional<NamedAttribute> NamedAttrList::findDuplicate() const {
98 std::optional<NamedAttribute> duplicate =
99 DictionaryAttr::findDuplicate(array&: attrs, isSorted: isSorted());
100 // DictionaryAttr::findDuplicate will sort the list, so reset the sorted
101 // state.
102 if (!isSorted())
103 dictionarySorted.setPointerAndInt(PtrVal: nullptr, IntVal: true);
104 return duplicate;
105}
106
107DictionaryAttr NamedAttrList::getDictionary(MLIRContext *context) const {
108 if (!isSorted()) {
109 DictionaryAttr::sortInPlace(array&: attrs);
110 dictionarySorted.setPointerAndInt(PtrVal: nullptr, IntVal: true);
111 }
112 if (!dictionarySorted.getPointer())
113 dictionarySorted.setPointer(DictionaryAttr::getWithSorted(context, value: attrs));
114 return llvm::cast<DictionaryAttr>(Val: dictionarySorted.getPointer());
115}
116
117/// Replaces the attributes with new list of attributes.
118void NamedAttrList::assign(const_iterator inStart, const_iterator inEnd) {
119 DictionaryAttr::sort(values: ArrayRef<NamedAttribute>{inStart, inEnd}, storage&: attrs);
120 dictionarySorted.setPointerAndInt(PtrVal: nullptr, IntVal: true);
121}
122
123void NamedAttrList::push_back(NamedAttribute newAttribute) {
124 if (isSorted())
125 dictionarySorted.setInt(attrs.empty() || attrs.back() < newAttribute);
126 dictionarySorted.setPointer(nullptr);
127 attrs.push_back(Elt: newAttribute);
128}
129
130/// Return the specified attribute if present, null otherwise.
131Attribute NamedAttrList::get(StringRef name) const {
132 auto it = findAttr(attrs: *this, name);
133 return it.second ? it.first->getValue() : Attribute();
134}
135Attribute NamedAttrList::get(StringAttr name) const {
136 auto it = findAttr(attrs: *this, name);
137 return it.second ? it.first->getValue() : Attribute();
138}
139
140/// Return the specified named attribute if present, std::nullopt otherwise.
141std::optional<NamedAttribute> NamedAttrList::getNamed(StringRef name) const {
142 auto it = findAttr(attrs: *this, name);
143 return it.second ? *it.first : std::optional<NamedAttribute>();
144}
145std::optional<NamedAttribute> NamedAttrList::getNamed(StringAttr name) const {
146 auto it = findAttr(attrs: *this, name);
147 return it.second ? *it.first : std::optional<NamedAttribute>();
148}
149
150/// If the an attribute exists with the specified name, change it to the new
151/// value. Otherwise, add a new attribute with the specified name/value.
152Attribute NamedAttrList::set(StringAttr name, Attribute value) {
153 assert(value && "attributes may never be null");
154
155 // Look for an existing attribute with the given name, and set its value
156 // in-place. Return the previous value of the attribute, if there was one.
157 auto it = findAttr(attrs&: *this, name);
158 if (it.second) {
159 // Update the existing attribute by swapping out the old value for the new
160 // value. Return the old value.
161 Attribute oldValue = it.first->getValue();
162 if (it.first->getValue() != value) {
163 it.first->setValue(value);
164
165 // If the attributes have changed, the dictionary is invalidated.
166 dictionarySorted.setPointer(nullptr);
167 }
168 return oldValue;
169 }
170 // Perform a string lookup to insert the new attribute into its sorted
171 // position.
172 if (isSorted())
173 it = findAttr(attrs&: *this, name: name.strref());
174 attrs.insert(I: it.first, Elt: {name, value});
175 // Invalidate the dictionary. Return null as there was no previous value.
176 dictionarySorted.setPointer(nullptr);
177 return Attribute();
178}
179
180Attribute NamedAttrList::set(StringRef name, Attribute value) {
181 assert(value && "attributes may never be null");
182 return set(name: mlir::StringAttr::get(context: value.getContext(), bytes: name), value);
183}
184
185Attribute
186NamedAttrList::eraseImpl(SmallVectorImpl<NamedAttribute>::iterator it) {
187 // Erasing does not affect the sorted property.
188 Attribute attr = it->getValue();
189 attrs.erase(CI: it);
190 dictionarySorted.setPointer(nullptr);
191 return attr;
192}
193
194Attribute NamedAttrList::erase(StringAttr name) {
195 auto it = findAttr(attrs&: *this, name);
196 return it.second ? eraseImpl(it: it.first) : Attribute();
197}
198
199Attribute NamedAttrList::erase(StringRef name) {
200 auto it = findAttr(attrs&: *this, name);
201 return it.second ? eraseImpl(it: it.first) : Attribute();
202}
203
204NamedAttrList &
205NamedAttrList::operator=(const SmallVectorImpl<NamedAttribute> &rhs) {
206 assign(inStart: rhs.begin(), inEnd: rhs.end());
207 return *this;
208}
209
210NamedAttrList::operator ArrayRef<NamedAttribute>() const { return attrs; }
211
212//===----------------------------------------------------------------------===//
213// OperationState
214//===----------------------------------------------------------------------===//
215
216OperationState::OperationState(Location location, StringRef name)
217 : location(location), name(name, location->getContext()) {}
218
219OperationState::OperationState(Location location, OperationName name)
220 : location(location), name(name) {}
221
222OperationState::OperationState(Location location, OperationName name,
223 ValueRange operands, TypeRange types,
224 ArrayRef<NamedAttribute> attributes,
225 BlockRange successors,
226 MutableArrayRef<std::unique_ptr<Region>> regions)
227 : location(location), name(name),
228 operands(operands.begin(), operands.end()),
229 types(types.begin(), types.end()),
230 attributes(attributes.begin(), attributes.end()),
231 successors(successors.begin(), successors.end()) {
232 for (std::unique_ptr<Region> &r : regions)
233 this->regions.push_back(Elt: std::move(r));
234}
235OperationState::OperationState(Location location, StringRef name,
236 ValueRange operands, TypeRange types,
237 ArrayRef<NamedAttribute> attributes,
238 BlockRange successors,
239 MutableArrayRef<std::unique_ptr<Region>> regions)
240 : OperationState(location, OperationName(name, location.getContext()),
241 operands, types, attributes, successors, regions) {}
242
243OperationState::~OperationState() {
244 if (properties)
245 propertiesDeleter(properties);
246}
247
248LogicalResult OperationState::setProperties(
249 Operation *op, function_ref<InFlightDiagnostic()> emitError) const {
250 if (LLVM_UNLIKELY(propertiesAttr)) {
251 assert(!properties);
252 return op->setPropertiesFromAttribute(attr: propertiesAttr, emitError);
253 }
254 if (properties)
255 propertiesSetter(op->getPropertiesStorage(), properties);
256 return success();
257}
258
259void OperationState::addOperands(ValueRange newOperands) {
260 operands.append(in_start: newOperands.begin(), in_end: newOperands.end());
261}
262
263void OperationState::addSuccessors(BlockRange newSuccessors) {
264 successors.append(in_start: newSuccessors.begin(), in_end: newSuccessors.end());
265}
266
267Region *OperationState::addRegion() {
268 regions.emplace_back(Args: new Region);
269 return regions.back().get();
270}
271
272void OperationState::addRegion(std::unique_ptr<Region> &&region) {
273 regions.push_back(Elt: std::move(region));
274}
275
276void OperationState::addRegions(
277 MutableArrayRef<std::unique_ptr<Region>> regions) {
278 for (std::unique_ptr<Region> &region : regions)
279 addRegion(region: std::move(region));
280}
281
282//===----------------------------------------------------------------------===//
283// OperandStorage
284//===----------------------------------------------------------------------===//
285
286detail::OperandStorage::OperandStorage(Operation *owner,
287 OpOperand *trailingOperands,
288 ValueRange values)
289 : isStorageDynamic(false), operandStorage(trailingOperands) {
290 numOperands = capacity = values.size();
291 for (unsigned i = 0; i < numOperands; ++i)
292 new (&operandStorage[i]) OpOperand(owner, values[i]);
293}
294
295detail::OperandStorage::~OperandStorage() {
296 for (auto &operand : getOperands())
297 operand.~OpOperand();
298
299 // If the storage is dynamic, deallocate it.
300 if (isStorageDynamic)
301 free(ptr: operandStorage);
302}
303
304/// Replace the operands contained in the storage with the ones provided in
305/// 'values'.
306void detail::OperandStorage::setOperands(Operation *owner, ValueRange values) {
307 MutableArrayRef<OpOperand> storageOperands = resize(owner, newSize: values.size());
308 for (unsigned i = 0, e = values.size(); i != e; ++i)
309 storageOperands[i].set(values[i]);
310}
311
312/// Replace the operands beginning at 'start' and ending at 'start' + 'length'
313/// with the ones provided in 'operands'. 'operands' may be smaller or larger
314/// than the range pointed to by 'start'+'length'.
315void detail::OperandStorage::setOperands(Operation *owner, unsigned start,
316 unsigned length, ValueRange operands) {
317 // If the new size is the same, we can update inplace.
318 unsigned newSize = operands.size();
319 if (newSize == length) {
320 MutableArrayRef<OpOperand> storageOperands = getOperands();
321 for (unsigned i = 0, e = length; i != e; ++i)
322 storageOperands[start + i].set(operands[i]);
323 return;
324 }
325 // If the new size is greater, remove the extra operands and set the rest
326 // inplace.
327 if (newSize < length) {
328 eraseOperands(start: start + operands.size(), length: length - newSize);
329 setOperands(owner, start, length: newSize, operands);
330 return;
331 }
332 // Otherwise, the new size is greater so we need to grow the storage.
333 auto storageOperands = resize(owner, newSize: size() + (newSize - length));
334
335 // Shift operands to the right to make space for the new operands.
336 unsigned rotateSize = storageOperands.size() - (start + length);
337 auto rbegin = storageOperands.rbegin();
338 std::rotate(first: rbegin, middle: std::next(x: rbegin, n: newSize - length), last: rbegin + rotateSize);
339
340 // Update the operands inplace.
341 for (unsigned i = 0, e = operands.size(); i != e; ++i)
342 storageOperands[start + i].set(operands[i]);
343}
344
345/// Erase an operand held by the storage.
346void detail::OperandStorage::eraseOperands(unsigned start, unsigned length) {
347 MutableArrayRef<OpOperand> operands = getOperands();
348 assert((start + length) <= operands.size());
349 numOperands -= length;
350
351 // Shift all operands down if the operand to remove is not at the end.
352 if (start != numOperands) {
353 auto *indexIt = std::next(x: operands.begin(), n: start);
354 std::rotate(first: indexIt, middle: std::next(x: indexIt, n: length), last: operands.end());
355 }
356 for (unsigned i = 0; i != length; ++i)
357 operands[numOperands + i].~OpOperand();
358}
359
360void detail::OperandStorage::eraseOperands(const BitVector &eraseIndices) {
361 MutableArrayRef<OpOperand> operands = getOperands();
362 assert(eraseIndices.size() == operands.size());
363
364 // Check that at least one operand is erased.
365 int firstErasedIndice = eraseIndices.find_first();
366 if (firstErasedIndice == -1)
367 return;
368
369 // Shift all of the removed operands to the end, and destroy them.
370 numOperands = firstErasedIndice;
371 for (unsigned i = firstErasedIndice + 1, e = operands.size(); i < e; ++i)
372 if (!eraseIndices.test(Idx: i))
373 operands[numOperands++] = std::move(operands[i]);
374 for (OpOperand &operand : operands.drop_front(N: numOperands))
375 operand.~OpOperand();
376}
377
378/// Resize the storage to the given size. Returns the array containing the new
379/// operands.
380MutableArrayRef<OpOperand> detail::OperandStorage::resize(Operation *owner,
381 unsigned newSize) {
382 // If the number of operands is less than or equal to the current amount, we
383 // can just update in place.
384 MutableArrayRef<OpOperand> origOperands = getOperands();
385 if (newSize <= numOperands) {
386 // If the number of new size is less than the current, remove any extra
387 // operands.
388 for (unsigned i = newSize; i != numOperands; ++i)
389 origOperands[i].~OpOperand();
390 numOperands = newSize;
391 return origOperands.take_front(N: newSize);
392 }
393
394 // If the new size is within the original inline capacity, grow inplace.
395 if (newSize <= capacity) {
396 OpOperand *opBegin = origOperands.data();
397 for (unsigned e = newSize; numOperands != e; ++numOperands)
398 new (&opBegin[numOperands]) OpOperand(owner);
399 return MutableArrayRef<OpOperand>(opBegin, newSize);
400 }
401
402 // Otherwise, we need to allocate a new storage.
403 unsigned newCapacity =
404 std::max(a: unsigned(llvm::NextPowerOf2(A: capacity + 2)), b: newSize);
405 OpOperand *newOperandStorage =
406 reinterpret_cast<OpOperand *>(malloc(size: sizeof(OpOperand) * newCapacity));
407
408 // Move the current operands to the new storage.
409 MutableArrayRef<OpOperand> newOperands(newOperandStorage, newSize);
410 std::uninitialized_move(first: origOperands.begin(), last: origOperands.end(),
411 result: newOperands.begin());
412
413 // Destroy the original operands.
414 for (auto &operand : origOperands)
415 operand.~OpOperand();
416
417 // Initialize any new operands.
418 for (unsigned e = newSize; numOperands != e; ++numOperands)
419 new (&newOperands[numOperands]) OpOperand(owner);
420
421 // If the current storage is dynamic, free it.
422 if (isStorageDynamic)
423 free(ptr: operandStorage);
424
425 // Update the storage representation to use the new dynamic storage.
426 operandStorage = newOperandStorage;
427 capacity = newCapacity;
428 isStorageDynamic = true;
429 return newOperands;
430}
431
432//===----------------------------------------------------------------------===//
433// Operation Value-Iterators
434//===----------------------------------------------------------------------===//
435
436//===----------------------------------------------------------------------===//
437// OperandRange
438//===----------------------------------------------------------------------===//
439
440unsigned OperandRange::getBeginOperandIndex() const {
441 assert(!empty() && "range must not be empty");
442 return base->getOperandNumber();
443}
444
445OperandRangeRange OperandRange::split(DenseI32ArrayAttr segmentSizes) const {
446 return OperandRangeRange(*this, segmentSizes);
447}
448
449//===----------------------------------------------------------------------===//
450// OperandRangeRange
451//===----------------------------------------------------------------------===//
452
453OperandRangeRange::OperandRangeRange(OperandRange operands,
454 Attribute operandSegments)
455 : OperandRangeRange(OwnerT(operands.getBase(), operandSegments), 0,
456 llvm::cast<DenseI32ArrayAttr>(Val&: operandSegments).size()) {
457}
458
459OperandRange OperandRangeRange::join() const {
460 const OwnerT &owner = getBase();
461 ArrayRef<int32_t> sizeData = llvm::cast<DenseI32ArrayAttr>(Val: owner.second);
462 return OperandRange(owner.first, llvm::sum_of(Range&: sizeData));
463}
464
465OperandRange OperandRangeRange::dereference(const OwnerT &object,
466 ptrdiff_t index) {
467 ArrayRef<int32_t> sizeData = llvm::cast<DenseI32ArrayAttr>(Val: object.second);
468 uint32_t startIndex = llvm::sum_of(Range: sizeData.take_front(N: index));
469 return OperandRange(object.first + startIndex, *(sizeData.begin() + index));
470}
471
472//===----------------------------------------------------------------------===//
473// MutableOperandRange
474//===----------------------------------------------------------------------===//
475
476/// Construct a new mutable range from the given operand, operand start index,
477/// and range length.
478MutableOperandRange::MutableOperandRange(
479 Operation *owner, unsigned start, unsigned length,
480 ArrayRef<OperandSegment> operandSegments)
481 : owner(owner), start(start), length(length),
482 operandSegments(operandSegments) {
483 assert((start + length) <= owner->getNumOperands() && "invalid range");
484}
485MutableOperandRange::MutableOperandRange(Operation *owner)
486 : MutableOperandRange(owner, /*start=*/0, owner->getNumOperands()) {}
487
488/// Construct a new mutable range for the given OpOperand.
489MutableOperandRange::MutableOperandRange(OpOperand &opOperand)
490 : MutableOperandRange(opOperand.getOwner(),
491 /*start=*/opOperand.getOperandNumber(),
492 /*length=*/1) {}
493
494/// Slice this range into a sub range, with the additional operand segment.
495MutableOperandRange
496MutableOperandRange::slice(unsigned subStart, unsigned subLen,
497 std::optional<OperandSegment> segment) const {
498 assert((subStart + subLen) <= length && "invalid sub-range");
499 MutableOperandRange subSlice(owner, start + subStart, subLen,
500 operandSegments);
501 if (segment)
502 subSlice.operandSegments.push_back(Elt: *segment);
503 return subSlice;
504}
505
506/// Append the given values to the range.
507void MutableOperandRange::append(ValueRange values) {
508 if (values.empty())
509 return;
510 owner->insertOperands(index: start + length, operands: values);
511 updateLength(newLength: length + values.size());
512}
513
514/// Assign this range to the given values.
515void MutableOperandRange::assign(ValueRange values) {
516 owner->setOperands(start, length, operands: values);
517 if (length != values.size())
518 updateLength(/*newLength=*/values.size());
519}
520
521/// Assign the range to the given value.
522void MutableOperandRange::assign(Value value) {
523 if (length == 1) {
524 owner->setOperand(idx: start, value);
525 } else {
526 owner->setOperands(start, length, operands: value);
527 updateLength(/*newLength=*/1);
528 }
529}
530
531/// Erase the operands within the given sub-range.
532void MutableOperandRange::erase(unsigned subStart, unsigned subLen) {
533 assert((subStart + subLen) <= length && "invalid sub-range");
534 if (length == 0)
535 return;
536 owner->eraseOperands(idx: start + subStart, length: subLen);
537 updateLength(newLength: length - subLen);
538}
539
540/// Clear this range and erase all of the operands.
541void MutableOperandRange::clear() {
542 if (length != 0) {
543 owner->eraseOperands(idx: start, length);
544 updateLength(/*newLength=*/0);
545 }
546}
547
548/// Explicit conversion to an OperandRange.
549OperandRange MutableOperandRange::getAsOperandRange() const {
550 return owner->getOperands().slice(n: start, m: length);
551}
552
553/// Allow implicit conversion to an OperandRange.
554MutableOperandRange::operator OperandRange() const {
555 return getAsOperandRange();
556}
557
558MutableOperandRange::operator MutableArrayRef<OpOperand>() const {
559 return owner->getOpOperands().slice(N: start, M: length);
560}
561
562MutableOperandRangeRange
563MutableOperandRange::split(NamedAttribute segmentSizes) const {
564 return MutableOperandRangeRange(*this, segmentSizes);
565}
566
567/// Update the length of this range to the one provided.
568void MutableOperandRange::updateLength(unsigned newLength) {
569 int32_t diff = int32_t(newLength) - int32_t(length);
570 length = newLength;
571
572 // Update any of the provided segment attributes.
573 for (OperandSegment &segment : operandSegments) {
574 auto attr = llvm::cast<DenseI32ArrayAttr>(Val: segment.second.getValue());
575 SmallVector<int32_t, 8> segments(attr.asArrayRef());
576 segments[segment.first] += diff;
577 segment.second.setValue(
578 DenseI32ArrayAttr::get(context: attr.getContext(), content: segments));
579 owner->setInherentAttr(name: segment.second.getName(), value: segment.second.getValue());
580 }
581}
582
583OpOperand &MutableOperandRange::operator[](unsigned index) const {
584 assert(index < length && "index is out of bounds");
585 return owner->getOpOperand(idx: start + index);
586}
587
588MutableArrayRef<OpOperand>::iterator MutableOperandRange::begin() const {
589 return owner->getOpOperands().slice(N: start, M: length).begin();
590}
591
592MutableArrayRef<OpOperand>::iterator MutableOperandRange::end() const {
593 return owner->getOpOperands().slice(N: start, M: length).end();
594}
595
596//===----------------------------------------------------------------------===//
597// MutableOperandRangeRange
598//===----------------------------------------------------------------------===//
599
600MutableOperandRangeRange::MutableOperandRangeRange(
601 const MutableOperandRange &operands, NamedAttribute operandSegmentAttr)
602 : MutableOperandRangeRange(
603 OwnerT(operands, operandSegmentAttr), 0,
604 llvm::cast<DenseI32ArrayAttr>(Val: operandSegmentAttr.getValue()).size()) {
605}
606
607MutableOperandRange MutableOperandRangeRange::join() const {
608 return getBase().first;
609}
610
611MutableOperandRangeRange::operator OperandRangeRange() const {
612 return OperandRangeRange(getBase().first, getBase().second.getValue());
613}
614
615MutableOperandRange MutableOperandRangeRange::dereference(const OwnerT &object,
616 ptrdiff_t index) {
617 ArrayRef<int32_t> sizeData =
618 llvm::cast<DenseI32ArrayAttr>(Val: object.second.getValue());
619 uint32_t startIndex = llvm::sum_of(Range: sizeData.take_front(N: index));
620 return object.first.slice(
621 subStart: startIndex, subLen: *(sizeData.begin() + index),
622 segment: MutableOperandRange::OperandSegment(index, object.second));
623}
624
625//===----------------------------------------------------------------------===//
626// ResultRange
627//===----------------------------------------------------------------------===//
628
629ResultRange::ResultRange(OpResult result)
630 : ResultRange(static_cast<detail::OpResultImpl *>(Value(result).getImpl()),
631 1) {}
632
633ResultRange::use_range ResultRange::getUses() const {
634 return {use_begin(), use_end()};
635}
636ResultRange::use_iterator ResultRange::use_begin() const {
637 return use_iterator(*this);
638}
639ResultRange::use_iterator ResultRange::use_end() const {
640 return use_iterator(*this, /*end=*/true);
641}
642ResultRange::user_range ResultRange::getUsers() {
643 return {user_begin(), user_end()};
644}
645ResultRange::user_iterator ResultRange::user_begin() {
646 return user_iterator(use_begin());
647}
648ResultRange::user_iterator ResultRange::user_end() {
649 return user_iterator(use_end());
650}
651
652ResultRange::UseIterator::UseIterator(ResultRange results, bool end)
653 : it(end ? results.end() : results.begin()), endIt(results.end()) {
654 // Only initialize current use if there are results/can be uses.
655 if (it != endIt)
656 skipOverResultsWithNoUsers();
657}
658
659ResultRange::UseIterator &ResultRange::UseIterator::operator++() {
660 // We increment over uses, if we reach the last use then move to next
661 // result.
662 if (use != (*it).use_end())
663 ++use;
664 if (use == (*it).use_end()) {
665 ++it;
666 skipOverResultsWithNoUsers();
667 }
668 return *this;
669}
670
671void ResultRange::UseIterator::skipOverResultsWithNoUsers() {
672 while (it != endIt && (*it).use_empty())
673 ++it;
674
675 // If we are at the last result, then set use to first use of
676 // first result (sentinel value used for end).
677 if (it == endIt)
678 use = {};
679 else
680 use = (*it).use_begin();
681}
682
683void ResultRange::replaceAllUsesWith(Operation *op) {
684 replaceAllUsesWith(values: op->getResults());
685}
686
687bool ResultRange::replaceUsesWithIf(
688 Operation *op, function_ref<bool(OpOperand &)> shouldReplace) {
689 return replaceUsesWithIf(values: op->getResults(), shouldReplace);
690}
691
692//===----------------------------------------------------------------------===//
693// ValueRange
694//===----------------------------------------------------------------------===//
695
696ValueRange::ValueRange(ArrayRef<Value> values)
697 : ValueRange(values.data(), values.size()) {}
698ValueRange::ValueRange(OperandRange values)
699 : ValueRange(values.begin().getBase(), values.size()) {}
700ValueRange::ValueRange(ResultRange values)
701 : ValueRange(values.getBase(), values.size()) {}
702
703/// See `llvm::detail::indexed_accessor_range_base` for details.
704ValueRange::OwnerT ValueRange::offset_base(const OwnerT &owner,
705 ptrdiff_t index) {
706 if (const auto *value = llvm::dyn_cast_if_present<const Value *>(Val: owner))
707 return {value + index};
708 if (auto *operand = llvm::dyn_cast_if_present<OpOperand *>(Val: owner))
709 return {operand + index};
710 // All elements are identical; the owner pointer never advances.
711 if (llvm::isa<const Repeated<Value> *>(Val: owner))
712 return owner;
713 return cast<detail::OpResultImpl *>(Val: owner)->getNextResultAtOffset(offset: index);
714}
715/// See `llvm::detail::indexed_accessor_range_base` for details.
716Value ValueRange::dereference_iterator(const OwnerT &owner, ptrdiff_t index) {
717 if (const auto *value = llvm::dyn_cast_if_present<const Value *>(Val: owner))
718 return value[index];
719 if (auto *operand = llvm::dyn_cast_if_present<OpOperand *>(Val: owner))
720 return operand[index].get();
721 if (auto *repeated =
722 llvm::dyn_cast_if_present<const Repeated<Value> *>(Val: owner))
723 return repeated->value();
724 return cast<detail::OpResultImpl *>(Val: owner)->getNextResultAtOffset(offset: index);
725}
726
727//===----------------------------------------------------------------------===//
728// Operation Equivalency
729//===----------------------------------------------------------------------===//
730
731llvm::hash_code OperationEquivalence::computeHash(
732 Operation *op, function_ref<llvm::hash_code(Value)> hashOperands,
733 function_ref<llvm::hash_code(Value)> hashResults, Flags flags) {
734 // Hash operations based upon their:
735 // - Operation Name
736 // - Attributes
737 // - Result Types
738 DictionaryAttr dictAttrs;
739 if (!(flags & Flags::IgnoreDiscardableAttrs))
740 dictAttrs = op->getRawDictionaryAttrs();
741 llvm::hash_code hash =
742 llvm::hash_combine(args: op->getName(), args: dictAttrs, args: op->getResultTypes());
743 if (!(flags & Flags::IgnoreProperties))
744 hash = llvm::hash_combine(args: hash, args: op->hashProperties());
745
746 // - Location if required
747 if (!(flags & Flags::IgnoreLocations))
748 hash = llvm::hash_combine(args: hash, args: op->getLoc());
749
750 // - Operands
751 if (!(flags & Flags::IgnoreCommutativity) &&
752 op->hasTrait<mlir::OpTrait::IsCommutative>() &&
753 op->getNumOperands() > 0) {
754 size_t operandHash = hashOperands(op->getOperand(idx: 0));
755 for (auto operand : op->getOperands().drop_front())
756 operandHash += hashOperands(operand);
757 hash = llvm::hash_combine(args: hash, args: operandHash);
758 } else {
759 for (Value operand : op->getOperands())
760 hash = llvm::hash_combine(args: hash, args: hashOperands(operand));
761 }
762
763 // - Results
764 for (Value result : op->getResults())
765 hash = llvm::hash_combine(args: hash, args: hashResults(result));
766 return hash;
767}
768
769/*static*/ bool OperationEquivalence::isRegionEquivalentTo(
770 Region *lhs, Region *rhs,
771 function_ref<LogicalResult(Value, Value)> checkEquivalent,
772 function_ref<void(Value, Value)> markEquivalent,
773 OperationEquivalence::Flags flags,
774 function_ref<LogicalResult(ValueRange, ValueRange)>
775 checkCommutativeEquivalent) {
776 DenseMap<Block *, Block *> blocksMap;
777 auto blocksEquivalent = [&](Block &lBlock, Block &rBlock) {
778 // Check block arguments.
779 if (lBlock.getNumArguments() != rBlock.getNumArguments())
780 return false;
781
782 // Map the two blocks.
783 auto insertion = blocksMap.insert(KV: {&lBlock, &rBlock});
784 if (insertion.first->getSecond() != &rBlock)
785 return false;
786
787 for (auto argPair :
788 llvm::zip(t: lBlock.getArguments(), u: rBlock.getArguments())) {
789 Value curArg = std::get<0>(t&: argPair);
790 Value otherArg = std::get<1>(t&: argPair);
791 if (curArg.getType() != otherArg.getType())
792 return false;
793 if (!(flags & OperationEquivalence::IgnoreLocations) &&
794 curArg.getLoc() != otherArg.getLoc())
795 return false;
796 // Corresponding bbArgs are equivalent.
797 if (markEquivalent)
798 markEquivalent(curArg, otherArg);
799 }
800
801 auto opsEquivalent = [&](Operation &lOp, Operation &rOp) {
802 // Check for op equality (recursively).
803 if (!OperationEquivalence::isEquivalentTo(lhs: &lOp, rhs: &rOp, checkEquivalent,
804 markEquivalent, flags,
805 checkCommutativeEquivalent))
806 return false;
807 // Check successor mapping.
808 for (auto successorsPair :
809 llvm::zip(t: lOp.getSuccessors(), u: rOp.getSuccessors())) {
810 Block *curSuccessor = std::get<0>(t&: successorsPair);
811 Block *otherSuccessor = std::get<1>(t&: successorsPair);
812 auto insertion = blocksMap.insert(KV: {curSuccessor, otherSuccessor});
813 if (insertion.first->getSecond() != otherSuccessor)
814 return false;
815 }
816 return true;
817 };
818 return llvm::all_of_zip(argsAndPredicate&: lBlock, argsAndPredicate&: rBlock, argsAndPredicate&: opsEquivalent);
819 };
820 return llvm::all_of_zip(argsAndPredicate&: *lhs, argsAndPredicate&: *rhs, argsAndPredicate&: blocksEquivalent);
821}
822
823// Value equivalence cache to be used with `isRegionEquivalentTo` and
824// `isEquivalentTo`.
825struct ValueEquivalenceCache {
826 DenseMap<Value, Value> equivalentValues;
827 LogicalResult checkEquivalent(Value lhsValue, Value rhsValue) {
828 return success(IsSuccess: lhsValue == rhsValue ||
829 equivalentValues.lookup(Val: lhsValue) == rhsValue);
830 }
831 LogicalResult checkCommutativeEquivalent(ValueRange lhsRange,
832 ValueRange rhsRange) {
833 // Handle simple case where sizes mismatch.
834 if (lhsRange.size() != rhsRange.size())
835 return failure();
836
837 // Handle where operands in order are equivalent.
838 auto lhsIt = lhsRange.begin();
839 auto rhsIt = rhsRange.begin();
840 for (; lhsIt != lhsRange.end(); ++lhsIt, ++rhsIt) {
841 if (failed(Result: checkEquivalent(lhsValue: *lhsIt, rhsValue: *rhsIt)))
842 break;
843 }
844 if (lhsIt == lhsRange.end())
845 return success();
846
847 // Replace values with their entry in equivalentValues if they're in there
848 // that way, a sorted pointer comparison is enough to determine
849 // commutativity.
850 auto sortValues = [this](ValueRange values) {
851 SmallVector<Value> sortedValues = llvm::map_to_vector(
852 C&: values, F: [this](Value a) { return equivalentValues.lookup_or(Val: a, Default&: a); });
853 llvm::sort(C&: sortedValues, Comp: [](Value a, Value b) {
854 return a.getAsOpaquePointer() < b.getAsOpaquePointer();
855 });
856 return sortedValues;
857 };
858 auto lhsSorted = sortValues({lhsIt, lhsRange.end()});
859 auto rhsSorted = sortValues({rhsIt, rhsRange.end()});
860 return success(IsSuccess: lhsSorted == rhsSorted);
861 }
862 void markEquivalent(Value lhsResult, Value rhsResult) {
863 auto insertion = equivalentValues.insert(KV: {lhsResult, rhsResult});
864 // Make sure that the value was not already marked equivalent to some other
865 // value.
866 (void)insertion;
867 assert(insertion.first->second == rhsResult &&
868 "inconsistent OperationEquivalence state");
869 }
870};
871
872/*static*/ bool
873OperationEquivalence::isRegionEquivalentTo(Region *lhs, Region *rhs,
874 OperationEquivalence::Flags flags) {
875 ValueEquivalenceCache cache;
876 return isRegionEquivalentTo(
877 lhs, rhs,
878 checkEquivalent: [&](Value lhsValue, Value rhsValue) -> LogicalResult {
879 return cache.checkEquivalent(lhsValue, rhsValue);
880 },
881 markEquivalent: [&](Value lhsResult, Value rhsResult) {
882 cache.markEquivalent(lhsResult, rhsResult);
883 },
884 flags,
885 checkCommutativeEquivalent: [&](ValueRange lhs, ValueRange rhs) -> LogicalResult {
886 return cache.checkCommutativeEquivalent(lhsRange: lhs, rhsRange: rhs);
887 });
888}
889
890/*static*/ bool OperationEquivalence::isEquivalentTo(
891 Operation *lhs, Operation *rhs,
892 function_ref<LogicalResult(Value, Value)> checkEquivalent,
893 function_ref<void(Value, Value)> markEquivalent, Flags flags,
894 function_ref<LogicalResult(ValueRange, ValueRange)>
895 checkCommutativeEquivalent) {
896 if (lhs == rhs)
897 return true;
898
899 // 1. Compare the operation properties.
900 if (!(flags & IgnoreDiscardableAttrs) &&
901 lhs->getRawDictionaryAttrs() != rhs->getRawDictionaryAttrs())
902 return false;
903
904 if (lhs->getName() != rhs->getName() ||
905 lhs->getNumRegions() != rhs->getNumRegions() ||
906 lhs->getNumSuccessors() != rhs->getNumSuccessors() ||
907 lhs->getNumOperands() != rhs->getNumOperands() ||
908 lhs->getNumResults() != rhs->getNumResults())
909 return false;
910 if (!(flags & IgnoreProperties) &&
911 !(lhs->getName().compareOpProperties(lhs: lhs->getPropertiesStorage(),
912 rhs: rhs->getPropertiesStorage())))
913 return false;
914 if (!(flags & IgnoreLocations) && lhs->getLoc() != rhs->getLoc())
915 return false;
916
917 // 2. Compare operands.
918 if (!(flags & IgnoreCommutativity) && checkCommutativeEquivalent &&
919 lhs->hasTrait<mlir::OpTrait::IsCommutative>()) {
920 auto lhsRange = lhs->getOperands();
921 auto rhsRange = rhs->getOperands();
922 if (failed(Result: checkCommutativeEquivalent(lhsRange, rhsRange)))
923 return false;
924 } else {
925 // Check pair wise for equivalence.
926 for (auto operandPair : llvm::zip(t: lhs->getOperands(), u: rhs->getOperands())) {
927 Value curArg = std::get<0>(t&: operandPair);
928 Value otherArg = std::get<1>(t&: operandPair);
929 if (curArg == otherArg)
930 continue;
931 if (curArg.getType() != otherArg.getType())
932 return false;
933 if (failed(Result: checkEquivalent(curArg, otherArg)))
934 return false;
935 }
936 }
937
938 // 3. Compare result types and mark results as equivalent.
939 for (auto resultPair : llvm::zip(t: lhs->getResults(), u: rhs->getResults())) {
940 Value curArg = std::get<0>(t&: resultPair);
941 Value otherArg = std::get<1>(t&: resultPair);
942 if (curArg.getType() != otherArg.getType())
943 return false;
944 if (markEquivalent)
945 markEquivalent(curArg, otherArg);
946 }
947
948 // 4. Compare regions.
949 for (auto regionPair : llvm::zip(t: lhs->getRegions(), u: rhs->getRegions()))
950 if (!isRegionEquivalentTo(
951 lhs: &std::get<0>(t&: regionPair), rhs: &std::get<1>(t&: regionPair), checkEquivalent,
952 markEquivalent, flags, checkCommutativeEquivalent))
953 return false;
954
955 return true;
956}
957
958/*static*/ bool OperationEquivalence::isEquivalentTo(Operation *lhs,
959 Operation *rhs,
960 Flags flags) {
961 ValueEquivalenceCache cache;
962 return OperationEquivalence::isEquivalentTo(
963 lhs, rhs,
964 checkEquivalent: [&](Value lhsValue, Value rhsValue) -> LogicalResult {
965 return cache.checkEquivalent(lhsValue, rhsValue);
966 },
967 markEquivalent: [&](Value lhsResult, Value rhsResult) {
968 cache.markEquivalent(lhsResult, rhsResult);
969 },
970 flags,
971 checkCommutativeEquivalent: [&](ValueRange lhs, ValueRange rhs) -> LogicalResult {
972 return cache.checkCommutativeEquivalent(lhsRange: lhs, rhsRange: rhs);
973 });
974}
975
976//===----------------------------------------------------------------------===//
977// OperationFingerPrint
978//===----------------------------------------------------------------------===//
979
980template <typename T>
981static void addDataToHash(llvm::SHA1 &hasher, const T &data) {
982 hasher.update(
983 Data: ArrayRef<uint8_t>(reinterpret_cast<const uint8_t *>(&data), sizeof(T)));
984}
985
986OperationFingerPrint::OperationFingerPrint(Operation *topOp,
987 bool includeNested) {
988 llvm::SHA1 hasher;
989
990 // Helper function that hashes an operation based on its mutable bits:
991 auto addOperationToHash = [&](Operation *op) {
992 // - Operation pointer
993 addDataToHash(hasher, data: op);
994 // - Parent operation pointer (to take into account the nesting structure)
995 if (op != topOp)
996 addDataToHash(hasher, data: op->getParentOp());
997 // - Attributes
998 addDataToHash(hasher, data: op->getRawDictionaryAttrs());
999 // - Properties
1000 addDataToHash(hasher, data: op->hashProperties());
1001 // - Blocks in Regions
1002 for (Region &region : op->getRegions()) {
1003 for (Block &block : region) {
1004 addDataToHash(hasher, data: &block);
1005 for (BlockArgument arg : block.getArguments())
1006 addDataToHash(hasher, data: arg);
1007 }
1008 }
1009 // - Location
1010 addDataToHash(hasher, data: op->getLoc().getAsOpaquePointer());
1011 // - Operands
1012 for (Value operand : op->getOperands())
1013 addDataToHash(hasher, data: operand);
1014 // - Successors
1015 for (unsigned i = 0, e = op->getNumSuccessors(); i != e; ++i)
1016 addDataToHash(hasher, data: op->getSuccessor(index: i));
1017 // - Result types
1018 for (Type t : op->getResultTypes())
1019 addDataToHash(hasher, data: t);
1020 };
1021
1022 if (includeNested)
1023 topOp->walk(callback&: addOperationToHash);
1024 else
1025 addOperationToHash(topOp);
1026
1027 hash = hasher.result();
1028}
1029
1030MLIR_DEFINE_EXPLICIT_TYPE_ID(mlir::EmptyProperties)
1031