STLExtras: Provide less/equal functors with templated function call operators, plus a deref'ing functor template utility

[dblaikie]

Summary

Similar to the C++14 void specializations of these templates, useful as a stop-gap until LLVM switches to '14.

Example use-cases in tblgen because I saw some functors that looked like they could be simplified/refactored.

[dblaikie]

Formatting and comments

[dblaikie]

Add asserts to the deref binary functor.

llvm/trunk/include/llvm/ADT/STLExtras.h

 
 #include "llvm/Support/Compiler.h"
 #include <cstddef> // for std::size_t
 #include <cstdlib> // for qsort
 #include <functional>
 #include <iterator>
 #include <memory>
 #include <utility> // for std::pair
+#include <cassert>
 
 namespace llvm {
 
 //===----------------------------------------------------------------------===//
 //     Extra additions to <functional>
 //===----------------------------------------------------------------------===//
 
 template<class Ty>

 
 template<typename First, typename Second>
 struct pair_hash {
   size_t operator()(const std::pair<First, Second> &P) const {
     return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
   }
 };
 
+/// A functor like C++14's std::less<void> in its absence.
+struct less {
+  template <typename A, typename B> bool operator()(A &&a, B &&b) const {
+    return std::forward<A>(a) < std::forward<B>(b);
+  }
+};
+
+/// A functor like C++14's std::equal<void> in its absence.
+struct equal {
+  template <typename A, typename B> bool operator()(A &&a, B &&b) const {
+    return std::forward<A>(a) == std::forward<B>(b);
+  }
+};
+
+/// Binary functor that adapts to any other binary functor after dereferencing
+/// operands.
+template <typename T> struct deref {
+  T func;
+  // Could be further improved to cope with non-derivable functors and
+  // non-binary functors (should be a variadic template member function
+  // operator()).
+  template <typename A, typename B>
+  auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
+    assert(lhs);
+    assert(rhs);
+    return func(*lhs, *rhs);
+  }
+};
+
 } // End llvm namespace
 
 #endif

llvm/trunk/utils/TableGen/CodeGenRegisters.h

public:
 
     CodeGenSubRegIndex(Record *R, unsigned Enum);
     CodeGenSubRegIndex(StringRef N, StringRef Nspace, unsigned Enum);
 
     const std::string &getName() const { return Name; }
     const std::string &getNamespace() const { return Namespace; }
     std::string getQualifiedName() const;
 
-    // Order CodeGenSubRegIndex pointers by EnumValue.
-    struct Less {
-      bool operator()(const CodeGenSubRegIndex *A,
-                      const CodeGenSubRegIndex *B) const {
-        assert(A && B);
-        return A->EnumValue < B->EnumValue;
-      }
-    };
-
     // Map of composite subreg indices.
-    typedef std::map<CodeGenSubRegIndex*, CodeGenSubRegIndex*, Less> CompMap;
+    typedef std::map<CodeGenSubRegIndex *, CodeGenSubRegIndex *,
+                     deref<llvm::less>> CompMap;
 
     // Returns the subreg index that results from composing this with Idx.
     // Returns NULL if this and Idx don't compose.
     CodeGenSubRegIndex *compose(CodeGenSubRegIndex *Idx) const {
       CompMap::const_iterator I = Composed.find(Idx);
       return I == Composed.end() ? nullptr : I->second;
     }
 
public:
 
     // Compute LaneMask from Composed. Return LaneMask.
     unsigned computeLaneMask() const;
 
   private:
     CompMap Composed;
   };
 
+  inline bool operator<(const CodeGenSubRegIndex &A,
+                        const CodeGenSubRegIndex &B) {
+    return A.EnumValue < B.EnumValue;
+  }
+
   /// CodeGenRegister - Represents a register definition.
   struct CodeGenRegister {
     Record *TheDef;
     unsigned EnumValue;
     unsigned CostPerUse;
     bool CoveredBySubRegs;
 
     // Map SubRegIndex -> Register.
-    typedef std::map<CodeGenSubRegIndex*, CodeGenRegister*,
-                     CodeGenSubRegIndex::Less> SubRegMap;
+    typedef std::map<CodeGenSubRegIndex *, CodeGenRegister *, deref<llvm::less>>
+        SubRegMap;
 
     CodeGenRegister(Record *R, unsigned Enum);
 
     const std::string &getName() const;
 
     // Extract more information from TheDef. This is used to build an object
     // graph after all CodeGenRegister objects have been created.
     void buildObjectGraph(CodeGenRegBank&);
struct CodeGenRegister {
 
     // Adopt a register unit for pressure tracking.
     // A unit is adopted iff its unit number is >= NativeRegUnits.count().
     void adoptRegUnit(unsigned RUID) { RegUnits.set(RUID); }
 
     // Get the sum of this register's register unit weights.
     unsigned getWeight(const CodeGenRegBank &RegBank) const;
 
-    // Order CodeGenRegister pointers by EnumValue.
-    struct Less {
-      bool operator()(const CodeGenRegister *A,
-                      const CodeGenRegister *B) const {
-        assert(A && B);
-        return A->EnumValue < B->EnumValue;
-      }
-    };
-
-    struct Equal {
-      bool operator()(const CodeGenRegister *A,
-                      const CodeGenRegister *B) const {
-        assert(A && B);
-        return A->EnumValue == B->EnumValue;
-      }
-    };
-
     // Canonically ordered set.
     typedef std::vector<const CodeGenRegister*> Vec;
 
   private:
     bool SubRegsComplete;
     bool SuperRegsComplete;
     unsigned TopoSig;
 
private:
 
     SubRegMap SubRegs;
     SuperRegList SuperRegs;
     DenseMap<const CodeGenRegister*, CodeGenSubRegIndex*> SubReg2Idx;
     RegUnitList RegUnits;
     RegUnitLaneMaskList RegUnitLaneMasks;
   };
 
+  inline bool operator<(const CodeGenRegister &A, const CodeGenRegister &B) {
+    return A.EnumValue < B.EnumValue;
+  }
+
+  inline bool operator==(const CodeGenRegister &A, const CodeGenRegister &B) {
+    return A.EnumValue == B.EnumValue;
+  }
 
   class CodeGenRegisterClass {
     CodeGenRegister::Vec Members;
     // Allocation orders. Order[0] always contains all registers in Members.
     std::vector<SmallVector<Record*, 16> > Orders;
     // Bit mask of sub-classes including this, indexed by their EnumValue.
     BitVector SubClasses;
     // List of super-classes, topologocally ordered to have the larger classes

llvm/trunk/utils/TableGen/CodeGenRegisters.cpp

 };
 }
 
 //===----------------------------------------------------------------------===//
 //                            CodeGenRegisterClass
 //===----------------------------------------------------------------------===//
 
 static void sortAndUniqueRegisters(CodeGenRegister::Vec &M) {
-  std::sort(M.begin(), M.end(), CodeGenRegister::Less());
-  M.erase(std::unique(M.begin(), M.end(), CodeGenRegister::Equal()), M.end());
+  std::sort(M.begin(), M.end(), deref<llvm::less>());
+  M.erase(std::unique(M.begin(), M.end(), deref<llvm::equal>()), M.end());
 }
 
 CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R)
   : TheDef(R),
     Name(R->getName()),
     TopoSigs(RegBank.getNumTopoSigs()),
     EnumValue(-1),
     LaneMask(0) {
void CodeGenRegisterClass::inheritProperties(CodeGenRegBank &RegBank) {
   for (unsigned i = 0, ie = Super.Orders.size(); i != ie; ++i)
     for (unsigned j = 0, je = Super.Orders[i].size(); j != je; ++j)
       if (contains(RegBank.getReg(Super.Orders[i][j])))
         Orders[i].push_back(Super.Orders[i][j]);
 }
 
 bool CodeGenRegisterClass::contains(const CodeGenRegister *Reg) const {
   return std::binary_search(Members.begin(), Members.end(), Reg,
-                            CodeGenRegister::Less());
+                            deref<llvm::less>());
 }
 
 namespace llvm {
   raw_ostream &operator<<(raw_ostream &OS, const CodeGenRegisterClass::Key &K) {
     OS << "{ S=" << K.SpillSize << ", A=" << K.SpillAlignment;
     for (const auto R : *K.Members)
       OS << ", " << R->getName();
     return OS << " }";

 //
 // 1. All RC registers are also in this.
 // 2. The RC spill size must not be smaller than our spill size.
 // 3. RC spill alignment must be compatible with ours.
 //
 static bool testSubClass(const CodeGenRegisterClass *A,
                          const CodeGenRegisterClass *B) {
   return A->SpillAlignment && B->SpillAlignment % A->SpillAlignment == 0 &&
          A->SpillSize <= B->SpillSize &&
          std::includes(A->getMembers().begin(), A->getMembers().end(),
                        B->getMembers().begin(), B->getMembers().end(),
-                  CodeGenRegister::Less());
+                       deref<llvm::less>());
 }
 
 /// Sorting predicate for register classes.  This provides a topological
 /// ordering that arranges all register classes before their sub-classes.
 ///
 /// Register classes with the same registers, spill size, and alignment form a
 /// clique.  They will be ordered alphabetically.
 ///
for (auto I = RegClasses.begin(), E = std::prev(RegClasses.end());
     CodeGenRegisterClass *RC2 = &*I;
     if (RC1 == RC2)
       continue;
 
     // Compute the set intersection of RC1 and RC2.
     const CodeGenRegister::Vec &Memb1 = RC1->getMembers();
     const CodeGenRegister::Vec &Memb2 = RC2->getMembers();
     CodeGenRegister::Vec Intersection;
-    std::set_intersection(Memb1.begin(), Memb1.end(),
-                          Memb2.begin(), Memb2.end(),
-                          std::inserter(Intersection, Intersection.begin()),
-                          CodeGenRegister::Less());
+    std::set_intersection(
+        Memb1.begin(), Memb1.end(), Memb2.begin(), Memb2.end(),
+        std::inserter(Intersection, Intersection.begin()), deref<llvm::less>());
 
     // Skip disjoint class pairs.
     if (Intersection.empty())
       continue;
 
     // If RC1 and RC2 have different spill sizes or alignments, use the
     // larger size for sub-classing.  If they are equal, prefer RC1.
     if (RC2->SpillSize > RC1->SpillSize ||

 // Synthesize missing sub-classes for getSubClassWithSubReg().
 //
 // Make sure that the set of registers in RC with a given SubIdx sub-register
 // form a register class.  Update RC->SubClassWithSubReg.
 //
 void CodeGenRegBank::inferSubClassWithSubReg(CodeGenRegisterClass *RC) {
   // Map SubRegIndex to set of registers in RC supporting that SubRegIndex.
   typedef std::map<const CodeGenSubRegIndex *, CodeGenRegister::Vec,
-                   CodeGenSubRegIndex::Less> SubReg2SetMap;
+                   deref<llvm::less>> SubReg2SetMap;
 
   // Compute the set of registers supporting each SubRegIndex.
   SubReg2SetMap SRSets;
   for (const auto R : RC->getMembers()) {
     const CodeGenRegister::SubRegMap &SRM = R->getSubRegs();
     for (CodeGenRegister::SubRegMap::const_iterator I = SRM.begin(),
          E = SRM.end(); I != E; ++I)
       SRSets[I->first].push_back(R);

llvm/trunk/utils/TableGen/RegisterInfoEmitter.cpp

RegisterInfoEmitter::runMCDesc(raw_ostream &OS, CodeGenTarget &Target,
 
   // List of lane masks accompanying register unit sequences.
   SequenceToOffsetTable<MaskVec> LaneMaskSeqs;
   SmallVector<MaskVec, 4> RegUnitLaneMasks(Regs.size());
 
   // Keep track of sub-register names as well. These are not differentially
   // encoded.
   typedef SmallVector<const CodeGenSubRegIndex*, 4> SubRegIdxVec;
-  SequenceToOffsetTable<SubRegIdxVec, CodeGenSubRegIndex::Less> SubRegIdxSeqs;
+  SequenceToOffsetTable<SubRegIdxVec, deref<llvm::less>> SubRegIdxSeqs;
   SmallVector<SubRegIdxVec, 4> SubRegIdxLists(Regs.size());
 
   SequenceToOffsetTable<std::string> RegStrings;
 
   // Precompute register lists for the SequenceToOffsetTable.
   unsigned i = 0;
   for (auto I = Regs.begin(), E = Regs.end(); I != E; ++I, ++i) {
     const auto &Reg = *I;
if (!RegisterClasses.empty()) {
     // The corresponding bitmasks follow the sub-class mask in memory. Each
     // mask has RCMaskWords uint32_t entries.
     //
     // Every bit mask present in the list has at least one bit set.
 
     // Compress the sub-reg index lists.
     typedef std::vector<const CodeGenSubRegIndex*> IdxList;
     SmallVector<IdxList, 8> SuperRegIdxLists(RegisterClasses.size());
-    SequenceToOffsetTable<IdxList, CodeGenSubRegIndex::Less> SuperRegIdxSeqs;
+    SequenceToOffsetTable<IdxList, deref<llvm::less>> SuperRegIdxSeqs;
     BitVector MaskBV(RegisterClasses.size());
 
     for (const auto &RC : RegisterClasses) {
       OS << "static const uint32_t " << RC.getName() << "SubClassMask[] = {\n  ";
       printBitVectorAsHex(OS, RC.getSubClasses(), 32);
 
       // Emit super-reg class masks for any relevant SubRegIndices that can
       // project into RC.