Implement some micro-optimizations for Identifier. NFC

[lattner]

Summary

Identifier doesn't maintain a length, so every time strref() is called,
it does a strlen. In the case of comparisons, this isn't necessary:
there is no need to scan a string to get its length, then rescan it to
do the comparison. Just done one comparison.

This also moves some assertions in Identifier::get as another
microoptimization for 'assertions enabled' modes.

[lattner]

Change to increase pedantic correctness.

[rriddle]

mlir/include/mlir/IR/Identifier.h

54

Can you add the justification here?

[rriddle]

I wonder if it would be better to just change Identifier to store a StringMapEntry* instead of the raw character buffer. That way strref should be O(1).

[lattner]

Add comments explaining 'why not memcmp?' to Identifier.h

[lattner]

I improved the comment in Identifier.h. It is a good idea to include a pointer to StringMapEntry. I'll take a look at that as a followup, thanks!

mlir/include/mlir/IR/Identifier.h

public:
 
   /// Return a pointer to the start of the string data.
   const char *data() const { return pointer; }
 
   /// Return the number of bytes in this string.
   unsigned size() const { return ::strlen(pointer); }
 
   /// Return true if this identifier is the specified string.
-  bool is(StringRef string) const { return strref().equals(string); }
+  bool is(StringRef string) const {
+    // Note: this can't use memcmp, because memcmp doesn't guarantee that it
+    // will stop reading both buffers if one is shorter than the other.
+    return strncmp(pointer, string.data(), string.size()) == 0 &&
+           pointer[string.size()] == '\0';
+  }
 
   const char *begin() const { return pointer; }
   const char *end() const { return pointer + size(); }
 
   void print(raw_ostream &os) const;
   void dump() const;
 
   const void *getAsOpaquePointer() const {

mlir/lib/IR/Attributes.cpp

 //===----------------------------------------------------------------------===//
 // DictionaryAttr
 //===----------------------------------------------------------------------===//
 
 /// Perform a three-way comparison between the names of the specified
 /// NamedAttributes.
 static int compareNamedAttributes(const NamedAttribute *lhs,
                                   const NamedAttribute *rhs) {
-  return lhs->first.strref().compare(rhs->first.strref());
+  return strcmp(lhs->first.data(), rhs->first.data());
 }
 
 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;
   switch (value.size()) {
   case 0:
     break;
   case 1:
     // A single element is 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 (value[0].first.strref() > value[1].first.strref()) {
+    if (compareNamedAttributes(&value[0], &value[1]) > 0) {
       storage.push_back(value[1]);
       storage.push_back(value[0]);
       value = storage;
     }
     break;
   default:
     // Check to see they are sorted already.
     bool isSorted = true;
     for (unsigned i = 0, e = value.size() - 1; i != e; ++i) {
-      if (value[i].first.strref() > value[i + 1].first.strref()) {
+      if (compareNamedAttributes(&value[i], &value[i + 1]) > 0) {
         isSorted = false;
         break;
       }
     }
     // If not, do a general sort.
     if (!isSorted) {
       storage.append(value.begin(), value.end());
       llvm::array_pod_sort(storage.begin(), storage.end(),

 
 ArrayRef<NamedAttribute> DictionaryAttr::getValue() const {
   return getImpl()->getElements();
 }
 
 /// Return the specified attribute if present, null otherwise.
 Attribute DictionaryAttr::get(StringRef name) const {
   ArrayRef<NamedAttribute> values = getValue();
-  auto compare = [](NamedAttribute attr, StringRef name) {
-    return attr.first.strref() < name;
+  auto compare = [](NamedAttribute attr, StringRef name) -> bool {
+    // 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;
   };
   auto it = llvm::lower_bound(values, name, compare);
   return it != values.end() && it->first.is(name) ? it->second : Attribute();
 }
 Attribute DictionaryAttr::get(Identifier name) const {
   for (auto elt : getValue())
     if (elt.first == name)
       return elt.second;

mlir/lib/IR/MLIRContext.cpp

 }
 
 //===----------------------------------------------------------------------===//
 // Identifier uniquing
 //===----------------------------------------------------------------------===//
 
 /// Return an identifier for the specified string.
 Identifier Identifier::get(StringRef str, MLIRContext *context) {
-  assert(!str.empty() && "Cannot create an empty identifier");
-  assert(str.find('\0') == StringRef::npos &&
-         "Cannot create an identifier with a nul character");
-
   auto &impl = context->getImpl();
 
   { // Check for an existing identifier in read-only mode.
     llvm::sys::SmartScopedReader<true> contextLock(impl.identifierMutex);
     auto it = impl.identifiers.find(str);
     if (it != impl.identifiers.end())
       return Identifier(it->getKeyData());
   }
 
+  // Check invariants after seeing if we already have something in the
+  // identifier table - if we already had it in the table, then it already
+  // passed invariant checks.
+  assert(!str.empty() && "Cannot create an empty identifier");
+  assert(str.find('\0') == StringRef::npos &&
+         "Cannot create an identifier with a nul character");
+
   // Acquire a writer-lock so that we can safely create the new instance.
   llvm::sys::SmartScopedWriter<true> contextLock(impl.identifierMutex);
   auto it = impl.identifiers.insert({str, char()}).first;
   return Identifier(it->getKeyData());
 }
 
 //===----------------------------------------------------------------------===//
 // Type uniquing