Don't force std::set for SmallSet

[• espindola]

Summary

It is a bit surprising that MapVector uses a DenseMap but SetVector uses a std::set.

[• tstellarAMD]

I'm OK with the AMDGPU changes.

[chandlerc]

lib/Analysis/AliasAnalysisEvaluator.cpp

149

Why do we want a std::set here?

utils/TableGen/AsmMatcherEmitter.cpp

1724

Why not let this use DenseSet?

include/llvm/ADT/SmallSet.h

 // This file defines the SmallSet class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_SMALLSET_H
 #define LLVM_ADT_SMALLSET_H
 
 #include "llvm/ADT/None.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
-#include <set>
 
 namespace llvm {
 
-/// SmallSet - This maintains a set of unique values, optimizing for the case
-/// when the set is small (less than N).  In this case, the set can be
-/// maintained with no mallocs.  If the set gets large, we expand to using an
-/// std::set to maintain reasonable lookup times.
+/// This maintains a set of unique values, optimizing for the case when the set
+/// is small (less than N).  In this case, the set can be maintained with no
+/// mallocs.  If the set gets large, we expand to using another implementation
+/// to maintain reasonable lookup times.
 ///
 /// Note that this set does not provide a way to iterate over members in the
 /// set.
-template <typename T, unsigned N,  typename C = std::less<T> >
+template <typename T, unsigned N, typename BigSet = DenseSet<T>>
 class SmallSet {
   /// Use a SmallVector to hold the elements here (even though it will never
   /// reach its 'large' stage) to avoid calling the default ctors of elements
   /// we will never use.
   SmallVector<T, N> Vector;
-  std::set<T, C> Set;
+  BigSet Set;
   typedef typename SmallVector<T, N>::const_iterator VIterator;
   typedef typename SmallVector<T, N>::iterator mutable_iterator;
 
 public:
   typedef size_t size_type;
   SmallSet() {}
 
   bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const {

lib/Analysis/AliasAnalysisEvaluator.cpp

 #include "llvm/IR/Function.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include <set>
 using namespace llvm;
 
 static cl::opt<bool> PrintAll("print-all-alias-modref-info", cl::ReallyHidden);
 
 static cl::opt<bool> PrintNoAlias("print-no-aliases", cl::ReallyHidden);
 static cl::opt<bool> PrintMayAlias("print-may-aliases", cl::ReallyHidden);
 static cl::opt<bool> PrintPartialAlias("print-partial-aliases", cl::ReallyHidden);
 static cl::opt<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden);
return V->getType()->isPointerTy()
       && !isa<ConstantPointerNull>(V);
 }
 
 bool AAEval::runOnFunction(Function &F) {
   const DataLayout &DL = F.getParent()->getDataLayout();
   AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
 
   SetVector<Value *> Pointers;
-  SetVector<CallSite> CallSites;
+  SetVector<CallSite, std::vector<CallSite>, std::set<CallSite>> CallSites;
   SetVector<Value *> Loads;
   SetVector<Value *> Stores;
 
   for (auto &I : F.args())
     if (I.getType()->isPointerTy())    // Add all pointer arguments.
       Pointers.insert(&I);
 
   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {

lib/CodeGen/AggressiveAntiDepBreaker.h

 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/ScheduleDAG.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include <map>
+#include <set>
 
 namespace llvm {
 class RegisterClassInfo;
 
   /// Contains all the state necessary for anti-dep breaking.
 class LLVM_LIBRARY_VISIBILITY AggressiveAntiDepState {
   public:
     /// Information about a register reference within a liverange

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetOptions.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSelectionDAGInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include <algorithm>
 #include <cmath>
 #include <utility>
+#include <set>
 
 using namespace llvm;
 
 /// makeVTList - Return an instance of the SDVTList struct initialized with the
 /// specified members.
 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
   SDVTList Res = {VTs, NumVTs};
   return Res;

lib/ExecutionEngine/Orc/OrcMCJITReplacement.h

 #define LLVM_LIB_EXECUTIONENGINE_ORC_ORCMCJITREPLACEMENT_H
 
 #include "llvm/ExecutionEngine/ExecutionEngine.h"
 #include "llvm/ExecutionEngine/Orc/CompileUtils.h"
 #include "llvm/ExecutionEngine/Orc/IRCompileLayer.h"
 #include "llvm/ExecutionEngine/Orc/LazyEmittingLayer.h"
 #include "llvm/ExecutionEngine/Orc/ObjectLinkingLayer.h"
 #include "llvm/Object/Archive.h"
+#include <set>
 
 namespace llvm {
 namespace orc {
 
 class OrcMCJITReplacement : public ExecutionEngine {
 
   // OrcMCJITReplacement needs to do a little extra book-keeping to ensure that
   // Orc's automatic finalization doesn't kick in earlier than MCJIT clients are

lib/Target/AMDGPU/R600ControlFlowFinalizer.cpp

 #include "R600Defines.h"
 #include "R600InstrInfo.h"
 #include "R600MachineFunctionInfo.h"
 #include "R600RegisterInfo.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/raw_ostream.h"
+#include <set>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "r600cf"
 
 namespace {
 
 struct CFStack {

lib/Target/X86/X86FrameLowering.cpp

 #include "llvm/CodeGen/WinEHFuncInfo.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Function.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCSymbol.h"
 #include "llvm/Target/TargetOptions.h"
 #include "llvm/Support/Debug.h"
 #include <cstdlib>
+#include <set>
 
 using namespace llvm;
 
 X86FrameLowering::X86FrameLowering(const X86Subtarget &STI,
                                    unsigned StackAlignOverride)
     : TargetFrameLowering(StackGrowsDown, StackAlignOverride,
                           STI.is64Bit() ? -8 : -4),
       STI(STI), TII(*STI.getInstrInfo()), TRI(STI.getRegisterInfo()) {
static unsigned findDeadCallerSavedReg(MachineBasicBlock &MBB,
   case X86::TCRETURNdi:
   case X86::TCRETURNri:
   case X86::TCRETURNmi:
   case X86::TCRETURNdi64:
   case X86::TCRETURNri64:
   case X86::TCRETURNmi64:
   case X86::EH_RETURN:
   case X86::EH_RETURN64: {
-    SmallSet<uint16_t, 8> Uses;
+    SmallSet<uint16_t, 8, std::set<uint16_t>> Uses;
     for (unsigned i = 0, e = MBBI->getNumOperands(); i != e; ++i) {
       MachineOperand &MO = MBBI->getOperand(i);
       if (!MO.isReg() || MO.isDef())
         continue;
       unsigned Reg = MO.getReg();
       if (!Reg)
         continue;
       for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)

lib/Transforms/IPO/MergeFunctions.cpp

 #include "llvm/IR/ValueHandle.h"
 #include "llvm/IR/ValueMap.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include <vector>
+#include <set>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "mergefunc"
 
 STATISTIC(NumFunctionsMerged, "Number of functions merged");
 STATISTIC(NumThunksWritten, "Number of thunks generated");
 STATISTIC(NumAliasesWritten, "Number of aliases generated");

utils/TableGen/AsmMatcherEmitter.cpp

for ( ; AliasOpNo <  LastOpNo &&
         ResOperands.push_back(ResOperand::getRegOp(Reg));
         break;
       }
       }
     }
   }
 }
 
-static unsigned getConverterOperandID(const std::string &Name,
-                                      SetVector<std::string> &Table,
+typedef SetVector<std::string, std::vector<std::string>, std::set<std::string>>
+    StringSet;
+
+static unsigned getConverterOperandID(const std::string &Name, StringSet &Table,
                                       bool &IsNew) {
   IsNew = Table.insert(Name);
 
   unsigned ID = IsNew ? Table.size() - 1 :
     std::find(Table.begin(), Table.end(), Name) - Table.begin();
 
   assert(ID < Table.size());
 
   return ID;
 }
 
 
 static void emitConvertFuncs(CodeGenTarget &Target, StringRef ClassName,
                              std::vector<std::unique_ptr<MatchableInfo>> &Infos,
                              raw_ostream &OS) {
-  SetVector<std::string> OperandConversionKinds;
-  SetVector<std::string> InstructionConversionKinds;
+  StringSet OperandConversionKinds;
+  StringSet InstructionConversionKinds;
   std::vector<std::vector<uint8_t> > ConversionTable;
   size_t MaxRowLength = 2; // minimum is custom converter plus terminator.
 
   // TargetOperandClass - This is the target's operand class, like X86Operand.
   std::string TargetOperandClass = Target.getName() + "Operand";
 
   // Write the convert function to a separate stream, so we can drop it after
   // the enum. We'll build up the conversion handlers for the individual

utils/TableGen/FixedLenDecoderEmitter.cpp

struct OperandInfo {
   const_iterator begin() const { return Fields.begin(); }
   const_iterator end() const   { return Fields.end();   }
 };
 
 typedef std::vector<uint8_t> DecoderTable;
 typedef uint32_t DecoderFixup;
 typedef std::vector<DecoderFixup> FixupList;
 typedef std::vector<FixupList> FixupScopeList;
-typedef SetVector<std::string> PredicateSet;
-typedef SetVector<std::string> DecoderSet;
+
+typedef SetVector<std::string, std::vector<std::string>, std::set<std::string>>
+    StringSet;
+
+typedef StringSet PredicateSet;
+typedef StringSet DecoderSet;
 struct DecoderTableInfo {
   DecoderTable Table;
   FixupScopeList FixupStack;
   PredicateSet Predicates;
   DecoderSet Decoders;
 };
 
 } // End anonymous namespace