[mlir] Extract DictionaryAttr sort method

[jpienaar]

Summary

Enable sorting array of NamedAttributes, as would be expected by getWithSorted, into static member function so that external callers can get same sorting behavior while keeping sorting logic local.

[rriddle]

mlir/lib/IR/Attributes.cpp

109

Please use camelCase naming.

126

Can we change this to storage.append({value[1], value[0]}); to make this a one liner?

131–132

Just use llvm::is_sorted here?

160

Why not pass in array twice here?

[jpienaar]

Update to address review comments.

[jpienaar]

Reuse compareNamedAttributes instead of using strcmp in is_sorted

[rriddle]

mlir/include/mlir/IR/OperationSupport.h

314

Can we defer this until it is needed?

mlir/lib/IR/Attributes.cpp

111

Can we remove this now?

[jpienaar]

Remove uncalled site

mlir/include/mlir/IR/Attributes.h

public:
 
   /// Support range iteration.
   using iterator = llvm::ArrayRef<NamedAttribute>::iterator;
   iterator begin() const;
   iterator end() const;
   bool empty() const { return size() == 0; }
   size_t size() const;
 
+  /// Sorts the NamedAttributes in the array ordered by name as expected by
+  /// getWithSorted.
+  /// Requires: uniquely named attributes.
+  static void sort(SmallVectorImpl<NamedAttribute> &array);
+
   /// Methods for supporting type inquiry through isa, cast, and dyn_cast.
   static bool kindof(unsigned kind) {
     return kind == StandardAttributes::Dictionary;
   }
 };
 
 //===----------------------------------------------------------------------===//
 // FloatAttr

mlir/include/mlir/IR/OperationSupport.h

void addAttribute(Identifier name, Attribute attr) {
     attributes.push_back({name, attr});
   }
 
   /// Add an array of named attributes.
   void addAttributes(ArrayRef<NamedAttribute> newAttributes) {
     attributes.append(newAttributes.begin(), newAttributes.end());
   }
 
+  /// Sorts the NamedAttributes.
+  void sortAttributes() { DictionaryAttr::sort(attributes); }
+
   /// Add an array of successors.
   void addSuccessors(ArrayRef<Block *> newSuccessors) {
     successors.append(newSuccessors.begin(), newSuccessors.end());
   }
   void addSuccessors(Block *successor) { successors.push_back(successor); }
   void addSuccessors(SuccessorRange newSuccessors);
 
   /// Create a region that should be attached to the operation.  These regions

mlir/lib/IR/Attributes.cpp

static bool compareNamedAttributeWithName(const NamedAttribute &attr,
   // This is correct even when attr.first.data()[name.size()] is not a zero
   // string terminator, because we only care about a less than comparison.
   // This can't use memcmp, because it doesn't guarantee that it will stop
   // reading both buffers if one is shorter than the other, even if there is
   // a difference.
   return strncmp(attr.first.data(), name.data(), name.size()) < 0;
 }
 
-DictionaryAttr DictionaryAttr::get(ArrayRef<NamedAttribute> value,
-                                   MLIRContext *context) {
-  assert(llvm::all_of(value,
-                      [](const NamedAttribute &attr) { return attr.second; }) &&
-         "value cannot have null entries");
-
-  // We need to sort the element list to canonicalize it, but we also don't want
-  // to do a ton of work in the super common case where the element list is
-  // already sorted.
-  SmallVector<NamedAttribute, 8> storage;
+/// Helper function that does either an in place sort or sorts from source array
+/// into destination. If inPlace then storage is both the source and the
+/// destination, else value is the source and storage destination. Returns
+/// whether source was sorted.
+template <bool inPlace>
+static bool dictionaryAttrSort(ArrayRef<NamedAttribute> value,
+                               SmallVectorImpl<NamedAttribute> &storage) {
+  if (inPlace)
+    value = storage;
+  // Specialize for the common case.
   switch (value.size()) {
   case 0:
-    break;
   case 1:
-    // A single element is already sorted.
+    // Zero or one elements are already sorted.
     break;
   case 2:
     assert(value[0].first != value[1].first &&
            "DictionaryAttr element names must be unique");
-
-    // Don't invoke a general sort for two element case.
     if (compareNamedAttributes(&value[0], &value[1]) > 0) {
-      storage.push_back(value[1]);
-      storage.push_back(value[0]);
-      value = storage;
+      if (inPlace)
+        std::swap(storage[0], storage[1]);
+      else
+        storage.append({value[1], value[0]});
+      return true;
     }
     break;
   default:
     // Check to see they are sorted already.
-    bool isSorted = true;
-    for (unsigned i = 0, e = value.size() - 1; i != e; ++i) {
-      if (compareNamedAttributes(&value[i], &value[i + 1]) > 0) {
-        isSorted = false;
-        break;
-      }
-    }
-    // If not, do a general sort.
+    bool isSorted =
+        llvm::is_sorted(value, [](NamedAttribute l, NamedAttribute r) {
+          return compareNamedAttributes(&l, &r) < 0;
+        });
     if (!isSorted) {
+      // If not, do a general sort.
+      if (!inPlace)
         storage.append(value.begin(), value.end());
       llvm::array_pod_sort(storage.begin(), storage.end(),
                            compareNamedAttributes);
       value = storage;
     }
 
     // Ensure that the attribute elements are unique.
     assert(std::adjacent_find(value.begin(), value.end(),
                               [](NamedAttribute l, NamedAttribute r) {
                                 return l.first == r.first;
                               }) == value.end() &&
            "DictionaryAttr element names must be unique");
-  }
+    return !isSorted;
+  }
+  return false;
+}
+
+/// Sorts the NamedAttributes in the array ordered by name as expected by
+/// getWithSorted.
+/// Requires: uniquely named attributes.
+void DictionaryAttr::sort(SmallVectorImpl<NamedAttribute> &array) {
+  dictionaryAttrSort</*inPlace=*/true>(array, array);
 
+DictionaryAttr DictionaryAttr::get(ArrayRef<NamedAttribute> value,
+                                   MLIRContext *context) {
+  assert(llvm::all_of(value,
+                      [](const NamedAttribute &attr) { return attr.second; }) &&
+         "value cannot have null entries");
+
+  // We need to sort the element list to canonicalize it.
+  SmallVector<NamedAttribute, 8> storage;
+  if (dictionaryAttrSort</*inPlace=*/false>(value, storage))
+    value = storage;
+
   return Base::get(context, StandardAttributes::Dictionary, value);
 }
 
 /// Construct a dictionary with an array of values that is known to already be
 /// sorted by name and uniqued.
 DictionaryAttr DictionaryAttr::getWithSorted(ArrayRef<NamedAttribute> value,
                                              MLIRContext *context) {
   // Ensure that the attribute elements are unique and sorted.