MLIR  16.0.0git
OperationSupport.cpp
Go to the documentation of this file.
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 
16 #include "mlir/IR/BuiltinTypes.h"
17 #include "mlir/IR/OpDefinition.h"
18 #include "llvm/ADT/BitVector.h"
19 #include "llvm/Support/SHA1.h"
20 #include <numeric>
21 
22 using namespace mlir;
23 
24 //===----------------------------------------------------------------------===//
25 // NamedAttrList
26 //===----------------------------------------------------------------------===//
27 
29  assign(attributes.begin(), attributes.end());
30 }
31 
32 NamedAttrList::NamedAttrList(DictionaryAttr attributes)
33  : NamedAttrList(attributes ? attributes.getValue()
34  : ArrayRef<NamedAttribute>()) {
35  dictionarySorted.setPointerAndInt(attributes, true);
36 }
37 
39  assign(inStart, inEnd);
40 }
41 
43 
45  Optional<NamedAttribute> duplicate =
46  DictionaryAttr::findDuplicate(attrs, isSorted());
47  // DictionaryAttr::findDuplicate will sort the list, so reset the sorted
48  // state.
49  if (!isSorted())
50  dictionarySorted.setPointerAndInt(nullptr, true);
51  return duplicate;
52 }
53 
54 DictionaryAttr NamedAttrList::getDictionary(MLIRContext *context) const {
55  if (!isSorted()) {
56  DictionaryAttr::sortInPlace(attrs);
57  dictionarySorted.setPointerAndInt(nullptr, true);
58  }
59  if (!dictionarySorted.getPointer())
60  dictionarySorted.setPointer(DictionaryAttr::getWithSorted(context, attrs));
61  return dictionarySorted.getPointer().cast<DictionaryAttr>();
62 }
63 
64 /// Add an attribute with the specified name.
65 void NamedAttrList::append(StringRef name, Attribute attr) {
66  append(StringAttr::get(attr.getContext(), name), attr);
67 }
68 
69 /// Replaces the attributes with new list of attributes.
71  DictionaryAttr::sort(ArrayRef<NamedAttribute>{inStart, inEnd}, attrs);
72  dictionarySorted.setPointerAndInt(nullptr, true);
73 }
74 
76  if (isSorted())
77  dictionarySorted.setInt(attrs.empty() || attrs.back() < newAttribute);
78  dictionarySorted.setPointer(nullptr);
79  attrs.push_back(newAttribute);
80 }
81 
82 /// Return the specified attribute if present, null otherwise.
83 Attribute NamedAttrList::get(StringRef name) const {
84  auto it = findAttr(*this, name);
85  return it.second ? it.first->getValue() : Attribute();
86 }
87 Attribute NamedAttrList::get(StringAttr name) const {
88  auto it = findAttr(*this, name);
89  return it.second ? it.first->getValue() : Attribute();
90 }
91 
92 /// Return the specified named attribute if present, None otherwise.
94  auto it = findAttr(*this, name);
95  return it.second ? *it.first : Optional<NamedAttribute>();
96 }
98  auto it = findAttr(*this, name);
99  return it.second ? *it.first : Optional<NamedAttribute>();
100 }
101 
102 /// If the an attribute exists with the specified name, change it to the new
103 /// value. Otherwise, add a new attribute with the specified name/value.
105  assert(value && "attributes may never be null");
106 
107  // Look for an existing attribute with the given name, and set its value
108  // in-place. Return the previous value of the attribute, if there was one.
109  auto it = findAttr(*this, name);
110  if (it.second) {
111  // Update the existing attribute by swapping out the old value for the new
112  // value. Return the old value.
113  Attribute oldValue = it.first->getValue();
114  if (it.first->getValue() != value) {
115  it.first->setValue(value);
116 
117  // If the attributes have changed, the dictionary is invalidated.
118  dictionarySorted.setPointer(nullptr);
119  }
120  return oldValue;
121  }
122  // Perform a string lookup to insert the new attribute into its sorted
123  // position.
124  if (isSorted())
125  it = findAttr(*this, name.strref());
126  attrs.insert(it.first, {name, value});
127  // Invalidate the dictionary. Return null as there was no previous value.
128  dictionarySorted.setPointer(nullptr);
129  return Attribute();
130 }
131 
133  assert(value && "attributes may never be null");
134  return set(mlir::StringAttr::get(value.getContext(), name), value);
135 }
136 
137 Attribute
138 NamedAttrList::eraseImpl(SmallVectorImpl<NamedAttribute>::iterator it) {
139  // Erasing does not affect the sorted property.
140  Attribute attr = it->getValue();
141  attrs.erase(it);
142  dictionarySorted.setPointer(nullptr);
143  return attr;
144 }
145 
146 Attribute NamedAttrList::erase(StringAttr name) {
147  auto it = findAttr(*this, name);
148  return it.second ? eraseImpl(it.first) : Attribute();
149 }
150 
152  auto it = findAttr(*this, name);
153  return it.second ? eraseImpl(it.first) : Attribute();
154 }
155 
158  assign(rhs.begin(), rhs.end());
159  return *this;
160 }
161 
162 NamedAttrList::operator ArrayRef<NamedAttribute>() const { return attrs; }
163 
164 //===----------------------------------------------------------------------===//
165 // OperationState
166 //===----------------------------------------------------------------------===//
167 
168 OperationState::OperationState(Location location, StringRef name)
169  : location(location), name(name, location->getContext()) {}
170 
172  : location(location), name(name) {}
173 
175  ValueRange operands, TypeRange types,
176  ArrayRef<NamedAttribute> attributes,
177  BlockRange successors,
178  MutableArrayRef<std::unique_ptr<Region>> regions)
179  : location(location), name(name),
180  operands(operands.begin(), operands.end()),
181  types(types.begin(), types.end()),
182  attributes(attributes.begin(), attributes.end()),
183  successors(successors.begin(), successors.end()) {
184  for (std::unique_ptr<Region> &r : regions)
185  this->regions.push_back(std::move(r));
186 }
187 OperationState::OperationState(Location location, StringRef name,
188  ValueRange operands, TypeRange types,
189  ArrayRef<NamedAttribute> attributes,
190  BlockRange successors,
191  MutableArrayRef<std::unique_ptr<Region>> regions)
192  : OperationState(location, OperationName(name, location.getContext()),
193  operands, types, attributes, successors, regions) {}
194 
196  operands.append(newOperands.begin(), newOperands.end());
197 }
198 
200  successors.append(newSuccessors.begin(), newSuccessors.end());
201 }
202 
204  regions.emplace_back(new Region);
205  return regions.back().get();
206 }
207 
208 void OperationState::addRegion(std::unique_ptr<Region> &&region) {
209  regions.push_back(std::move(region));
210 }
211 
213  MutableArrayRef<std::unique_ptr<Region>> regions) {
214  for (std::unique_ptr<Region> &region : regions)
215  addRegion(std::move(region));
216 }
217 
218 //===----------------------------------------------------------------------===//
219 // OperandStorage
220 //===----------------------------------------------------------------------===//
221 
223  OpOperand *trailingOperands,
224  ValueRange values)
225  : isStorageDynamic(false), operandStorage(trailingOperands) {
226  numOperands = capacity = values.size();
227  for (unsigned i = 0; i < numOperands; ++i)
228  new (&operandStorage[i]) OpOperand(owner, values[i]);
229 }
230 
232  for (auto &operand : getOperands())
233  operand.~OpOperand();
234 
235  // If the storage is dynamic, deallocate it.
236  if (isStorageDynamic)
237  free(operandStorage);
238 }
239 
240 /// Replace the operands contained in the storage with the ones provided in
241 /// 'values'.
243  MutableArrayRef<OpOperand> storageOperands = resize(owner, values.size());
244  for (unsigned i = 0, e = values.size(); i != e; ++i)
245  storageOperands[i].set(values[i]);
246 }
247 
248 /// Replace the operands beginning at 'start' and ending at 'start' + 'length'
249 /// with the ones provided in 'operands'. 'operands' may be smaller or larger
250 /// than the range pointed to by 'start'+'length'.
251 void detail::OperandStorage::setOperands(Operation *owner, unsigned start,
252  unsigned length, ValueRange operands) {
253  // If the new size is the same, we can update inplace.
254  unsigned newSize = operands.size();
255  if (newSize == length) {
256  MutableArrayRef<OpOperand> storageOperands = getOperands();
257  for (unsigned i = 0, e = length; i != e; ++i)
258  storageOperands[start + i].set(operands[i]);
259  return;
260  }
261  // If the new size is greater, remove the extra operands and set the rest
262  // inplace.
263  if (newSize < length) {
264  eraseOperands(start + operands.size(), length - newSize);
265  setOperands(owner, start, newSize, operands);
266  return;
267  }
268  // Otherwise, the new size is greater so we need to grow the storage.
269  auto storageOperands = resize(owner, size() + (newSize - length));
270 
271  // Shift operands to the right to make space for the new operands.
272  unsigned rotateSize = storageOperands.size() - (start + length);
273  auto rbegin = storageOperands.rbegin();
274  std::rotate(rbegin, std::next(rbegin, newSize - length), rbegin + rotateSize);
275 
276  // Update the operands inplace.
277  for (unsigned i = 0, e = operands.size(); i != e; ++i)
278  storageOperands[start + i].set(operands[i]);
279 }
280 
281 /// Erase an operand held by the storage.
282 void detail::OperandStorage::eraseOperands(unsigned start, unsigned length) {
283  MutableArrayRef<OpOperand> operands = getOperands();
284  assert((start + length) <= operands.size());
285  numOperands -= length;
286 
287  // Shift all operands down if the operand to remove is not at the end.
288  if (start != numOperands) {
289  auto *indexIt = std::next(operands.begin(), start);
290  std::rotate(indexIt, std::next(indexIt, length), operands.end());
291  }
292  for (unsigned i = 0; i != length; ++i)
293  operands[numOperands + i].~OpOperand();
294 }
295 
296 void detail::OperandStorage::eraseOperands(const BitVector &eraseIndices) {
297  MutableArrayRef<OpOperand> operands = getOperands();
298  assert(eraseIndices.size() == operands.size());
299 
300  // Check that at least one operand is erased.
301  int firstErasedIndice = eraseIndices.find_first();
302  if (firstErasedIndice == -1)
303  return;
304 
305  // Shift all of the removed operands to the end, and destroy them.
306  numOperands = firstErasedIndice;
307  for (unsigned i = firstErasedIndice + 1, e = operands.size(); i < e; ++i)
308  if (!eraseIndices.test(i))
309  operands[numOperands++] = std::move(operands[i]);
310  for (OpOperand &operand : operands.drop_front(numOperands))
311  operand.~OpOperand();
312 }
313 
314 /// Resize the storage to the given size. Returns the array containing the new
315 /// operands.
316 MutableArrayRef<OpOperand> detail::OperandStorage::resize(Operation *owner,
317  unsigned newSize) {
318  // If the number of operands is less than or equal to the current amount, we
319  // can just update in place.
320  MutableArrayRef<OpOperand> origOperands = getOperands();
321  if (newSize <= numOperands) {
322  // If the number of new size is less than the current, remove any extra
323  // operands.
324  for (unsigned i = newSize; i != numOperands; ++i)
325  origOperands[i].~OpOperand();
326  numOperands = newSize;
327  return origOperands.take_front(newSize);
328  }
329 
330  // If the new size is within the original inline capacity, grow inplace.
331  if (newSize <= capacity) {
332  OpOperand *opBegin = origOperands.data();
333  for (unsigned e = newSize; numOperands != e; ++numOperands)
334  new (&opBegin[numOperands]) OpOperand(owner);
335  return MutableArrayRef<OpOperand>(opBegin, newSize);
336  }
337 
338  // Otherwise, we need to allocate a new storage.
339  unsigned newCapacity =
340  std::max(unsigned(llvm::NextPowerOf2(capacity + 2)), newSize);
341  OpOperand *newOperandStorage =
342  reinterpret_cast<OpOperand *>(malloc(sizeof(OpOperand) * newCapacity));
343 
344  // Move the current operands to the new storage.
345  MutableArrayRef<OpOperand> newOperands(newOperandStorage, newSize);
346  std::uninitialized_move(origOperands.begin(), origOperands.end(),
347  newOperands.begin());
348 
349  // Destroy the original operands.
350  for (auto &operand : origOperands)
351  operand.~OpOperand();
352 
353  // Initialize any new operands.
354  for (unsigned e = newSize; numOperands != e; ++numOperands)
355  new (&newOperands[numOperands]) OpOperand(owner);
356 
357  // If the current storage is dynamic, free it.
358  if (isStorageDynamic)
359  free(operandStorage);
360 
361  // Update the storage representation to use the new dynamic storage.
362  operandStorage = newOperandStorage;
363  capacity = newCapacity;
364  isStorageDynamic = true;
365  return newOperands;
366 }
367 
368 //===----------------------------------------------------------------------===//
369 // Operation Value-Iterators
370 //===----------------------------------------------------------------------===//
371 
372 //===----------------------------------------------------------------------===//
373 // OperandRange
374 
376  assert(!empty() && "range must not be empty");
377  return base->getOperandNumber();
378 }
379 
381  return OperandRangeRange(*this, segmentSizes);
382 }
383 
384 //===----------------------------------------------------------------------===//
385 // OperandRangeRange
386 
388  Attribute operandSegments)
389  : OperandRangeRange(OwnerT(operands.getBase(), operandSegments), 0,
390  operandSegments.cast<DenseI32ArrayAttr>().size()) {}
391 
393  const OwnerT &owner = getBase();
394  ArrayRef<int32_t> sizeData = owner.second.cast<DenseI32ArrayAttr>();
395  return OperandRange(owner.first,
396  std::accumulate(sizeData.begin(), sizeData.end(), 0));
397 }
398 
399 OperandRange OperandRangeRange::dereference(const OwnerT &object,
400  ptrdiff_t index) {
401  ArrayRef<int32_t> sizeData = object.second.cast<DenseI32ArrayAttr>();
402  uint32_t startIndex =
403  std::accumulate(sizeData.begin(), sizeData.begin() + index, 0);
404  return OperandRange(object.first + startIndex, *(sizeData.begin() + index));
405 }
406 
407 //===----------------------------------------------------------------------===//
408 // MutableOperandRange
409 
410 /// Construct a new mutable range from the given operand, operand start index,
411 /// and range length.
413  Operation *owner, unsigned start, unsigned length,
414  ArrayRef<OperandSegment> operandSegments)
415  : owner(owner), start(start), length(length),
416  operandSegments(operandSegments.begin(), operandSegments.end()) {
417  assert((start + length) <= owner->getNumOperands() && "invalid range");
418 }
420  : MutableOperandRange(owner, /*start=*/0, owner->getNumOperands()) {}
421 
422 /// Slice this range into a sub range, with the additional operand segment.
424 MutableOperandRange::slice(unsigned subStart, unsigned subLen,
425  Optional<OperandSegment> segment) const {
426  assert((subStart + subLen) <= length && "invalid sub-range");
427  MutableOperandRange subSlice(owner, start + subStart, subLen,
428  operandSegments);
429  if (segment)
430  subSlice.operandSegments.push_back(*segment);
431  return subSlice;
432 }
433 
434 /// Append the given values to the range.
436  if (values.empty())
437  return;
438  owner->insertOperands(start + length, values);
439  updateLength(length + values.size());
440 }
441 
442 /// Assign this range to the given values.
444  owner->setOperands(start, length, values);
445  if (length != values.size())
446  updateLength(/*newLength=*/values.size());
447 }
448 
449 /// Assign the range to the given value.
451  if (length == 1) {
452  owner->setOperand(start, value);
453  } else {
454  owner->setOperands(start, length, value);
455  updateLength(/*newLength=*/1);
456  }
457 }
458 
459 /// Erase the operands within the given sub-range.
460 void MutableOperandRange::erase(unsigned subStart, unsigned subLen) {
461  assert((subStart + subLen) <= length && "invalid sub-range");
462  if (length == 0)
463  return;
464  owner->eraseOperands(start + subStart, subLen);
465  updateLength(length - subLen);
466 }
467 
468 /// Clear this range and erase all of the operands.
470  if (length != 0) {
471  owner->eraseOperands(start, length);
472  updateLength(/*newLength=*/0);
473  }
474 }
475 
476 /// Allow implicit conversion to an OperandRange.
477 MutableOperandRange::operator OperandRange() const {
478  return owner->getOperands().slice(start, length);
479 }
480 
483  return MutableOperandRangeRange(*this, segmentSizes);
484 }
485 
486 /// Update the length of this range to the one provided.
487 void MutableOperandRange::updateLength(unsigned newLength) {
488  int32_t diff = int32_t(newLength) - int32_t(length);
489  length = newLength;
490 
491  // Update any of the provided segment attributes.
492  for (OperandSegment &segment : operandSegments) {
493  auto attr = segment.second.getValue().cast<DenseI32ArrayAttr>();
494  SmallVector<int32_t, 8> segments(attr.asArrayRef());
495  segments[segment.first] += diff;
496  segment.second.setValue(
497  DenseI32ArrayAttr::get(attr.getContext(), segments));
498  owner->setAttr(segment.second.getName(), segment.second.getValue());
499  }
500 }
501 
502 //===----------------------------------------------------------------------===//
503 // MutableOperandRangeRange
504 
506  const MutableOperandRange &operands, NamedAttribute operandSegmentAttr)
508  OwnerT(operands, operandSegmentAttr), 0,
509  operandSegmentAttr.getValue().cast<DenseI32ArrayAttr>().size()) {}
510 
512  return getBase().first;
513 }
514 
515 MutableOperandRangeRange::operator OperandRangeRange() const {
516  return OperandRangeRange(getBase().first, getBase().second.getValue());
517 }
518 
519 MutableOperandRange MutableOperandRangeRange::dereference(const OwnerT &object,
520  ptrdiff_t index) {
521  ArrayRef<int32_t> sizeData =
522  object.second.getValue().cast<DenseI32ArrayAttr>();
523  uint32_t startIndex =
524  std::accumulate(sizeData.begin(), sizeData.begin() + index, 0);
525  return object.first.slice(
526  startIndex, *(sizeData.begin() + index),
527  MutableOperandRange::OperandSegment(index, object.second));
528 }
529 
530 //===----------------------------------------------------------------------===//
531 // ResultRange
532 
534  : ResultRange(static_cast<detail::OpResultImpl *>(Value(result).getImpl()),
535  1) {}
536 
538  return {use_begin(), use_end()};
539 }
541  return use_iterator(*this);
542 }
544  return use_iterator(*this, /*end=*/true);
545 }
547  return {user_begin(), user_end()};
548 }
550  return user_iterator(use_begin());
551 }
553  return user_iterator(use_end());
554 }
555 
557  : it(end ? results.end() : results.begin()), endIt(results.end()) {
558  // Only initialize current use if there are results/can be uses.
559  if (it != endIt)
560  skipOverResultsWithNoUsers();
561 }
562 
564  // We increment over uses, if we reach the last use then move to next
565  // result.
566  if (use != (*it).use_end())
567  ++use;
568  if (use == (*it).use_end()) {
569  ++it;
570  skipOverResultsWithNoUsers();
571  }
572  return *this;
573 }
574 
575 void ResultRange::UseIterator::skipOverResultsWithNoUsers() {
576  while (it != endIt && (*it).use_empty())
577  ++it;
578 
579  // If we are at the last result, then set use to first use of
580  // first result (sentinel value used for end).
581  if (it == endIt)
582  use = {};
583  else
584  use = (*it).use_begin();
585 }
586 
589 }
590 
591 //===----------------------------------------------------------------------===//
592 // ValueRange
593 
595  : ValueRange(values.data(), values.size()) {}
597  : ValueRange(values.begin().getBase(), values.size()) {}
599  : ValueRange(values.getBase(), values.size()) {}
600 
601 /// See `llvm::detail::indexed_accessor_range_base` for details.
602 ValueRange::OwnerT ValueRange::offset_base(const OwnerT &owner,
603  ptrdiff_t index) {
604  if (const auto *value = owner.dyn_cast<const Value *>())
605  return {value + index};
606  if (auto *operand = owner.dyn_cast<OpOperand *>())
607  return {operand + index};
608  return owner.get<detail::OpResultImpl *>()->getNextResultAtOffset(index);
609 }
610 /// See `llvm::detail::indexed_accessor_range_base` for details.
611 Value ValueRange::dereference_iterator(const OwnerT &owner, ptrdiff_t index) {
612  if (const auto *value = owner.dyn_cast<const Value *>())
613  return value[index];
614  if (auto *operand = owner.dyn_cast<OpOperand *>())
615  return operand[index].get();
616  return owner.get<detail::OpResultImpl *>()->getNextResultAtOffset(index);
617 }
618 
619 //===----------------------------------------------------------------------===//
620 // Operation Equivalency
621 //===----------------------------------------------------------------------===//
622 
624  Operation *op, function_ref<llvm::hash_code(Value)> hashOperands,
625  function_ref<llvm::hash_code(Value)> hashResults, Flags flags) {
626  // Hash operations based upon their:
627  // - Operation Name
628  // - Attributes
629  // - Result Types
630  llvm::hash_code hash = llvm::hash_combine(
631  op->getName(), op->getAttrDictionary(), op->getResultTypes());
632 
633  // - Operands
634  ValueRange operands = op->getOperands();
635  SmallVector<Value> operandStorage;
637  operandStorage.append(operands.begin(), operands.end());
638  llvm::sort(operandStorage, [](Value a, Value b) -> bool {
639  return a.getAsOpaquePointer() < b.getAsOpaquePointer();
640  });
641  operands = operandStorage;
642  }
643  for (Value operand : operands)
644  hash = llvm::hash_combine(hash, hashOperands(operand));
645 
646  // - Operands
647  for (Value result : op->getResults())
648  hash = llvm::hash_combine(hash, hashResults(result));
649  return hash;
650 }
651 
652 static bool
654  function_ref<LogicalResult(Value, Value)> mapOperands,
655  function_ref<LogicalResult(Value, Value)> mapResults,
657  DenseMap<Block *, Block *> blocksMap;
658  auto blocksEquivalent = [&](Block &lBlock, Block &rBlock) {
659  // Check block arguments.
660  if (lBlock.getNumArguments() != rBlock.getNumArguments())
661  return false;
662 
663  // Map the two blocks.
664  auto insertion = blocksMap.insert({&lBlock, &rBlock});
665  if (insertion.first->getSecond() != &rBlock)
666  return false;
667 
668  for (auto argPair :
669  llvm::zip(lBlock.getArguments(), rBlock.getArguments())) {
670  Value curArg = std::get<0>(argPair);
671  Value otherArg = std::get<1>(argPair);
672  if (curArg.getType() != otherArg.getType())
673  return false;
674  if (!(flags & OperationEquivalence::IgnoreLocations) &&
675  curArg.getLoc() != otherArg.getLoc())
676  return false;
677  // Check if this value was already mapped to another value.
678  if (failed(mapOperands(curArg, otherArg)))
679  return false;
680  }
681 
682  auto opsEquivalent = [&](Operation &lOp, Operation &rOp) {
683  // Check for op equality (recursively).
684  if (!OperationEquivalence::isEquivalentTo(&lOp, &rOp, mapOperands,
685  mapResults, flags))
686  return false;
687  // Check successor mapping.
688  for (auto successorsPair :
689  llvm::zip(lOp.getSuccessors(), rOp.getSuccessors())) {
690  Block *curSuccessor = std::get<0>(successorsPair);
691  Block *otherSuccessor = std::get<1>(successorsPair);
692  auto insertion = blocksMap.insert({curSuccessor, otherSuccessor});
693  if (insertion.first->getSecond() != otherSuccessor)
694  return false;
695  }
696  return true;
697  };
698  return llvm::all_of_zip(lBlock, rBlock, opsEquivalent);
699  };
700  return llvm::all_of_zip(*lhs, *rhs, blocksEquivalent);
701 }
702 
704  Operation *lhs, Operation *rhs,
705  function_ref<LogicalResult(Value, Value)> mapOperands,
706  function_ref<LogicalResult(Value, Value)> mapResults, Flags flags) {
707  if (lhs == rhs)
708  return true;
709 
710  // Compare the operation properties.
711  if (lhs->getName() != rhs->getName() ||
712  lhs->getAttrDictionary() != rhs->getAttrDictionary() ||
713  lhs->getNumRegions() != rhs->getNumRegions() ||
714  lhs->getNumSuccessors() != rhs->getNumSuccessors() ||
715  lhs->getNumOperands() != rhs->getNumOperands() ||
716  lhs->getNumResults() != rhs->getNumResults())
717  return false;
718  if (!(flags & IgnoreLocations) && lhs->getLoc() != rhs->getLoc())
719  return false;
720 
721  ValueRange lhsOperands = lhs->getOperands(), rhsOperands = rhs->getOperands();
722  SmallVector<Value> lhsOperandStorage, rhsOperandStorage;
723  if (lhs->hasTrait<mlir::OpTrait::IsCommutative>()) {
724  auto sortValues = [](ValueRange values) {
725  SmallVector<Value> sortedValues = llvm::to_vector(values);
726  llvm::sort(sortedValues, [](Value a, Value b) {
727  auto aArg = a.dyn_cast<BlockArgument>();
728  auto bArg = b.dyn_cast<BlockArgument>();
729 
730  // Case 1. Both `a` and `b` are `BlockArgument`s.
731  if (aArg && bArg) {
732  if (aArg.getParentBlock() == bArg.getParentBlock())
733  return aArg.getArgNumber() < bArg.getArgNumber();
734  return aArg.getParentBlock() < bArg.getParentBlock();
735  }
736 
737  // Case 2. One of then is a `BlockArgument` and other is not. Treat
738  // `BlockArgument` as lesser.
739  if (aArg && !bArg)
740  return true;
741  if (bArg && !aArg)
742  return false;
743 
744  // Case 3. Both are values.
745  return a.getAsOpaquePointer() < b.getAsOpaquePointer();
746  });
747  return sortedValues;
748  };
749  lhsOperandStorage = sortValues(lhsOperands);
750  lhsOperands = lhsOperandStorage;
751  rhsOperandStorage = sortValues(rhsOperands);
752  rhsOperands = rhsOperandStorage;
753  }
754  auto checkValueRangeMapping =
755  [](ValueRange lhs, ValueRange rhs,
756  function_ref<LogicalResult(Value, Value)> mapValues) {
757  for (auto operandPair : llvm::zip(lhs, rhs)) {
758  Value curArg = std::get<0>(operandPair);
759  Value otherArg = std::get<1>(operandPair);
760  if (curArg.getType() != otherArg.getType())
761  return false;
762  if (failed(mapValues(curArg, otherArg)))
763  return false;
764  }
765  return true;
766  };
767  // Check mapping of operands and results.
768  if (!checkValueRangeMapping(lhsOperands, rhsOperands, mapOperands))
769  return false;
770  if (!checkValueRangeMapping(lhs->getResults(), rhs->getResults(), mapResults))
771  return false;
772  for (auto regionPair : llvm::zip(lhs->getRegions(), rhs->getRegions()))
773  if (!isRegionEquivalentTo(&std::get<0>(regionPair),
774  &std::get<1>(regionPair), mapOperands, mapResults,
775  flags))
776  return false;
777  return true;
778 }
779 
780 //===----------------------------------------------------------------------===//
781 // OperationFingerPrint
782 //===----------------------------------------------------------------------===//
783 
784 template <typename T>
785 static void addDataToHash(llvm::SHA1 &hasher, const T &data) {
786  hasher.update(
787  ArrayRef<uint8_t>(reinterpret_cast<const uint8_t *>(&data), sizeof(T)));
788 }
789 
791  llvm::SHA1 hasher;
792 
793  // Hash each of the operations based upon their mutable bits:
794  topOp->walk([&](Operation *op) {
795  // - Operation pointer
796  addDataToHash(hasher, op);
797  // - Attributes
798  addDataToHash(hasher, op->getAttrDictionary());
799  // - Blocks in Regions
800  for (Region &region : op->getRegions()) {
801  for (Block &block : region) {
802  addDataToHash(hasher, &block);
803  for (BlockArgument arg : block.getArguments())
804  addDataToHash(hasher, arg);
805  }
806  }
807  // - Location
808  addDataToHash(hasher, op->getLoc().getAsOpaquePointer());
809  // - Operands
810  for (Value operand : op->getOperands())
811  addDataToHash(hasher, operand);
812  // - Successors
813  for (unsigned i = 0, e = op->getNumSuccessors(); i != e; ++i)
814  addDataToHash(hasher, op->getSuccessor(i));
815  });
816  hash = hasher.result();
817 }
static constexpr const bool value
static bool isRegionEquivalentTo(Region *lhs, Region *rhs, function_ref< LogicalResult(Value, Value)> mapOperands, function_ref< LogicalResult(Value, Value)> mapResults, OperationEquivalence::Flags flags)
static void addDataToHash(llvm::SHA1 &hasher, const T &data)
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
Attributes are known-constant values of operations.
Definition: Attributes.h:25
U cast() const
Definition: Attributes.h:137
MLIRContext * getContext() const
Return the context this attribute belongs to.
Definition: Attributes.cpp:20
This class represents an argument of a Block.
Definition: Value.h:296
unsigned getArgNumber() const
Returns the number of this argument.
Definition: Value.h:308
This class provides an abstraction over the different types of ranges over Blocks.
Definition: BlockSupport.h:106
Block represents an ordered list of Operations.
Definition: Block.h:30
unsigned getNumArguments()
Definition: Block.h:117
BlockArgListType getArguments()
Definition: Block.h:76
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
Definition: Location.h:64
const void * getAsOpaquePointer() const
Methods for supporting PointerLikeTypeTraits.
Definition: Location.h:105
MLIRContext is the top-level object for a collection of MLIR operations.
Definition: MLIRContext.h:56
This class represents a contiguous range of mutable operand ranges, e.g.
Definition: ValueRange.h:194
MutableOperandRange join() const
Flatten all of the sub ranges into a single contiguous mutable operand range.
MutableOperandRangeRange(const MutableOperandRange &operands, NamedAttribute operandSegmentAttr)
Construct a range given a parent set of operands, and an I32 tensor elements attribute containing the...
This class provides a mutable adaptor for a range of operands.
Definition: ValueRange.h:114
void assign(ValueRange values)
Assign this range to the given values.
void erase(unsigned subStart, unsigned subLen=1)
Erase the operands within the given sub-range.
MutableOperandRange slice(unsigned subStart, unsigned subLen, Optional< OperandSegment > segment=llvm::None) const
Slice this range into a sub range, with the additional operand segment.
void append(ValueRange values)
Append the given values to the range.
void clear()
Clear this range and erase all of the operands.
std::pair< unsigned, NamedAttribute > OperandSegment
A pair of a named attribute corresponding to an operand segment attribute, and the index within that ...
Definition: ValueRange.h:119
MutableOperandRangeRange split(NamedAttribute segmentSizes) const
Split this range into a set of contiguous subranges using the given elements attribute,...
MutableOperandRange(Operation *owner, unsigned start, unsigned length, ArrayRef< OperandSegment > operandSegments=llvm::None)
Construct a new mutable range from the given operand, operand start index, and range length.
NamedAttrList is array of NamedAttributes that tracks whether it is sorted and does some basic work t...
Optional< NamedAttribute > findDuplicate() const
Returns an entry with a duplicate name the list, if it exists, else returns llvm::None.
void assign(const_iterator inStart, const_iterator inEnd)
Replaces the attributes with new list of attributes.
SmallVectorImpl< NamedAttribute >::const_iterator const_iterator
Optional< NamedAttribute > getNamed(StringRef name) const
Return the specified named attribute if present, None otherwise.
ArrayRef< NamedAttribute > getAttrs() const
Return all of the attributes on this operation.
DictionaryAttr getDictionary(MLIRContext *context) const
Return a dictionary attribute for the underlying dictionary.
void push_back(NamedAttribute newAttribute)
Add an attribute with the specified name.
Attribute get(StringAttr name) const
Return the specified attribute if present, null otherwise.
Attribute erase(StringAttr name)
Erase the attribute with the given name from the list.
Attribute set(StringAttr name, Attribute value)
If the an attribute exists with the specified name, change it to the new value.
void append(StringRef name, Attribute attr)
Add an attribute with the specified name.
NamedAttrList & operator=(const SmallVectorImpl< NamedAttribute > &rhs)
NamedAttribute represents a combination of a name and an Attribute value.
Definition: Attributes.h:150
This class represents an operand of an operation.
Definition: Value.h:247
This is a value defined by a result of an operation.
Definition: Value.h:442
This class adds property that the operation is commutative.
This class represents a contiguous range of operand ranges, e.g.
Definition: ValueRange.h:81
OperandRangeRange(OperandRange operands, Attribute operandSegments)
Construct a range given a parent set of operands, and an I32 elements attribute containing the sizes ...
OperandRange join() const
Flatten all of the sub ranges into a single contiguous operand range.
This class implements the operand iterators for the Operation class.
Definition: ValueRange.h:41
unsigned getBeginOperandIndex() const
Return the operand index of the first element of this range.
OperandRangeRange split(DenseI32ArrayAttr segmentSizes) const
Split this range into a set of contiguous subranges using the given elements attribute,...
OperationFingerPrint(Operation *topOp)
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:31
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:528
void insertOperands(unsigned index, ValueRange operands)
Insert the given operands into the operand list at the given 'index'.
Definition: Operation.cpp:213
void setOperand(unsigned idx, Value value)
Definition: Operation.h:268
Block * getSuccessor(unsigned index)
Definition: Operation.h:508
unsigned getNumSuccessors()
Definition: Operation.h:506
void eraseOperands(unsigned idx, unsigned length=1)
Erase the operands starting at position idx and ending at position 'idx'+'length'.
Definition: Operation.h:277
Location getLoc()
The source location the operation was defined or derived from.
Definition: Operation.h:154
unsigned getNumOperands()
Definition: Operation.h:263
void setAttr(StringAttr name, Attribute value)
If the an attribute exists with the specified name, change it to the new value.
Definition: Operation.h:395
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:480
DictionaryAttr getAttrDictionary()
Return all of the attributes on this operation as a DictionaryAttr.
Definition: Operation.h:359
OperationName getName()
The name of an operation is the key identifier for it.
Definition: Operation.h:50
result_type_range getResultTypes()
Definition: Operation.h:345
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition: Operation.h:295
void setOperands(ValueRange operands)
Replace the current operands of this operation with the ones provided in 'operands'.
Definition: Operation.cpp:194
SuccessorRange getSuccessors()
Definition: Operation.h:503
result_range getResults()
Definition: Operation.h:332
std::enable_if_t< llvm::function_traits< std::decay_t< FnT > >::num_args==1, RetT > walk(FnT &&callback)
Walk the operation by calling the callback for each nested operation (including this one),...
Definition: Operation.h:574
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
This class implements a use iterator for a range of operation results.
Definition: ValueRange.h:313
UseIterator(ResultRange results, bool end=false)
Initialize the UseIterator.
This class implements the result iterators for the Operation class.
Definition: ValueRange.h:230
use_range getUses() const
Returns a range of all uses of results within this range, which is useful for iterating over all uses...
use_iterator use_begin() const
user_range getUsers()
Returns a range of all users.
ValueUserIterator< use_iterator, OpOperand > user_iterator
Definition: ValueRange.h:285
ResultRange(OpResult result)
use_iterator use_end() const
user_iterator user_end()
std::enable_if_t<!std::is_convertible< ValuesT, Operation * >::value > replaceAllUsesWith(ValuesT &&values)
Replace all uses of results of this range with the provided 'values'.
Definition: ValueRange.h:269
user_iterator user_begin()
UseIterator use_iterator
Definition: ValueRange.h:250
This class provides an abstraction over the various different ranges of value types.
Definition: TypeRange.h:36
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:349
PointerUnion< const Value *, OpOperand *, detail::OpResultImpl * > OwnerT
The type representing the owner of a ValueRange.
Definition: ValueRange.h:354
ValueRange(Arg &&arg)
Definition: ValueRange.h:362
An iterator over the users of an IRObject.
Definition: UseDefLists.h:291
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
Type getType() const
Return the type of this value.
Definition: Value.h:114
U dyn_cast() const
Definition: Value.h:95
void * getAsOpaquePointer() const
Methods for supporting PointerLikeTypeTraits.
Definition: Value.h:223
Block * getParentBlock()
Return the Block in which this Value is defined.
Definition: Value.cpp:48
Location getLoc() const
Return the location of this value.
Definition: Value.cpp:26
static DenseArrayAttrImpl get(MLIRContext *context, ArrayRef< int32_t > content)
Builder from ArrayRef<T>.
This class provides the implementation for an operation result.
Definition: Value.h:345
void eraseOperands(unsigned start, unsigned length)
Erase the operands held by the storage within the given range.
void setOperands(Operation *owner, ValueRange values)
Replace the operands contained in the storage with the ones provided in 'values'.
OperandStorage(Operation *owner, OpOperand *trailingOperands, ValueRange values)
Include the generated interface declarations.
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
Definition: LogicalResult.h:72
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
static bool isEquivalentTo(Operation *lhs, Operation *rhs, function_ref< LogicalResult(Value, Value)> mapOperands, function_ref< LogicalResult(Value, Value)> mapResults, Flags flags=Flags::None)
Compare two operations and return if they are equivalent.
static llvm::hash_code computeHash(Operation *op, function_ref< llvm::hash_code(Value)> hashOperands=[](Value v) { return hash_value(v);}, function_ref< llvm::hash_code(Value)> hashResults=[](Value v) { return hash_value(v);}, Flags flags=Flags::None)
Compute a hash for the given operation.
This represents an operation in an abstracted form, suitable for use with the builder APIs.
void addRegions(MutableArrayRef< std::unique_ptr< Region >> regions)
Take ownership of a set of regions that should be attached to the Operation.
SmallVector< Block *, 1 > successors
Successors of this operation and their respective operands.
SmallVector< Value, 4 > operands
void addOperands(ValueRange newOperands)
void addSuccessors(Block *successor)
SmallVector< std::unique_ptr< Region >, 1 > regions
Regions that the op will hold.
OperationState(Location location, StringRef name)
Region * addRegion()
Create a region that should be attached to the operation.