[FoldingSet] Move compare to header (NFC).

[fhahn]

Summary

Moving the compare operator implementations to the header gives a slight
speedup. Not sure if the speedups are worthwhile, but I noticed this
when looking at folding set performance in general.

NewPM-O3: -0.04%
NewPM-ReleaseThinLTO: -0.03%
NewPM-ReleaseLTO-g: -0.01

https://llvm-compile-time-tracker.com/compare.php?from=8fa81cfad47c827ea1b75afe1f32861d4a7bad37&to=3c5e5ebd834106e62407e79d80ced0a49eafc4b7&stat=instructions:u

[serge-sans-paille]

Out of curiosity: do you have any speedup when building with LTO? Looks like something LTO should handle gracefully...

[fhahn]

In D139573#3979467, @serge-sans-paille wrote:

Out of curiosity: do you have any speedup when building with LTO? Looks like something LTO should handle gracefully...

Sure, this is not needed when building with LTO, but many builds don't use LTO :)

[yurai007]

looking at folding set performance in general

Just as a side note regarding further improvements in future - when I was working on related patches some months ago I noted 2 extra ideas which could be worth exploring:

[1] faster hashing related to FoldingSet* classes family. Symbols like llvm::FoldingSetBase::FindNodeOrInsertPos and llvm::hashing::detail::hash_short are often seen as hot in profiler output (at least were - couple of months ago). There is long-standing task in my queue to try xxHash or even CRC just for FoldingSet and see if it helps.

[2] removing (somehow) indirection related to FoldingSet::NodeEquals in context of following callers: FunctionProtoTypes/PointerTypes/ElaboratedTypes/ParenTypes Profile functions. IIRC that indirection made inlining impossible which mattered for projects with compile time highly dominated by frontend. Moving compare operators in this change may help for NodeEquals but I believe there is still some room for improvement.

I'm not sure about [2], but I think that [1] should bring some value even for builds with LTO=ON.

llvm/include/llvm/ADT/FoldingSet.h

 
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/Support/Allocator.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
+#include <cstring>
 #include <type_traits>
 #include <utility>
 
 namespace llvm {
 
 /// This folding set used for two purposes:
 ///   1. Given information about a node we want to create, look up the unique
 ///      instance of the node in the set.  If the node already exists, return
public:
   FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {}
 
   /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef,
   /// used to lookup the node in the FoldingSetBase.
   unsigned ComputeHash() const {
     return static_cast<unsigned>(hash_combine_range(Data, Data + Size));
   }
 
-  bool operator==(FoldingSetNodeIDRef) const;
+  bool operator==(const FoldingSetNodeIDRef &RHS) const {
+    if (Size != RHS.Size)
+      return false;
+    return memcmp(Data, RHS.Data, Size * sizeof(*Data)) == 0;
+  }
 
-  bool operator!=(FoldingSetNodeIDRef RHS) const { return !(*this == RHS); }
+  bool operator!=(const FoldingSetNodeIDRef &RHS) const {
+    return !(*this == RHS);
+  }
 
   /// Used to compare the "ordering" of two nodes as defined by the
   /// profiled bits and their ordering defined by memcmp().
-  bool operator<(FoldingSetNodeIDRef) const;
+  bool operator<(const FoldingSetNodeIDRef &RHS) const {
+    if (Size != RHS.Size)
+      return Size < RHS.Size;
+    return memcmp(Data, RHS.Data, Size * sizeof(*Data)) < 0;
+  }
 
   const unsigned *getData() const { return Data; }
   size_t getSize() const { return Size; }
 };
 
 //===--------------------------------------------------------------------===//
 /// FoldingSetNodeID - This class is used to gather all the unique data bits of
 /// a node.  When all the bits are gathered this class is used to produce a
public:
 
   /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used
   /// to lookup the node in the FoldingSetBase.
   unsigned ComputeHash() const {
     return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash();
   }
 
   /// operator== - Used to compare two nodes to each other.
-  bool operator==(const FoldingSetNodeID &RHS) const;
-  bool operator==(const FoldingSetNodeIDRef RHS) const;
+  bool operator==(const FoldingSetNodeID &RHS) const {
+    return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
+  }
+  bool operator==(const FoldingSetNodeIDRef RHS) const {
+    return FoldingSetNodeIDRef(Bits.data(), Bits.size()) == RHS;
+  }
 
   bool operator!=(const FoldingSetNodeID &RHS) const { return !(*this == RHS); }
   bool operator!=(const FoldingSetNodeIDRef RHS) const { return !(*this ==RHS);}
 
   /// Used to compare the "ordering" of two nodes as defined by the
   /// profiled bits and their ordering defined by memcmp().
-  bool operator<(const FoldingSetNodeID &RHS) const;
-  bool operator<(const FoldingSetNodeIDRef RHS) const;
+  bool operator<(const FoldingSetNodeID &RHS) const {
+    return *this < FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
+  }
+  bool operator<(const FoldingSetNodeIDRef RHS) const {
+    return FoldingSetNodeIDRef(Bits.data(), Bits.size()) < RHS;
+  }
 
   /// Intern - Copy this node's data to a memory region allocated from the
   /// given allocator and return a FoldingSetNodeIDRef describing the
   /// interned data.
   FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const;
 };
 
 // Convenience type to hide the implementation of the folding set.

llvm/lib/Support/FoldingSet.cpp

 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/SwapByteOrder.h"
 #include <cassert>
 #include <cstring>
 using namespace llvm;
 
 //===----------------------------------------------------------------------===//
-// FoldingSetNodeIDRef Implementation
-
-bool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const {
-  if (Size != RHS.Size) return false;
-  return memcmp(Data, RHS.Data, Size*sizeof(*Data)) == 0;
-}
-
-/// Used to compare the "ordering" of two nodes as defined by the
-/// profiled bits and their ordering defined by memcmp().
-bool FoldingSetNodeIDRef::operator<(FoldingSetNodeIDRef RHS) const {
-  if (Size != RHS.Size)
-    return Size < RHS.Size;
-  return memcmp(Data, RHS.Data, Size*sizeof(*Data)) < 0;
-}
-
-//===----------------------------------------------------------------------===//
 // FoldingSetNodeID Implementation
 
 /// Add* - Add various data types to Bit data.
 ///
 void FoldingSetNodeID::AddString(StringRef String) {
   unsigned Size =  String.size();
 
   unsigned NumInserts = 1 + divideCeil(Size, 4);
void FoldingSetNodeID::AddString(StringRef String) {
   Bits.push_back(V);
 }
 
 // AddNodeID - Adds the Bit data of another ID to *this.
 void FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) {
   Bits.append(ID.Bits.begin(), ID.Bits.end());
 }
 
-/// operator== - Used to compare two nodes to each other.
-///
-bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS) const {
-  return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
-}
-
-/// operator== - Used to compare two nodes to each other.
-///
-bool FoldingSetNodeID::operator==(FoldingSetNodeIDRef RHS) const {
-  return FoldingSetNodeIDRef(Bits.data(), Bits.size()) == RHS;
-}
-
-/// Used to compare the "ordering" of two nodes as defined by the
-/// profiled bits and their ordering defined by memcmp().
-bool FoldingSetNodeID::operator<(const FoldingSetNodeID &RHS) const {
-  return *this < FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
-}
-
-bool FoldingSetNodeID::operator<(FoldingSetNodeIDRef RHS) const {
-  return FoldingSetNodeIDRef(Bits.data(), Bits.size()) < RHS;
-}
-
 /// Intern - Copy this node's data to a memory region allocated from the
 /// given allocator and return a FoldingSetNodeIDRef describing the
 /// interned data.
 FoldingSetNodeIDRef
 FoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const {
   unsigned *New = Allocator.Allocate<unsigned>(Bits.size());
   std::uninitialized_copy(Bits.begin(), Bits.end(), New);
   return FoldingSetNodeIDRef(New, Bits.size());