[SelectionDAG] Stop storing EVTs in a function scoped static std::set.

[topperc]

EVTs potentially contain a Type * that points into memory owned by an LLVMContext. Storing them in a function scoped static means they may outlive the LLVMContext they point to.

This std::set is used to unique single element VT lists containing a single extended EVT. Single element VT list with a simple EVT are uniqued by a separate cache indexed by the MVT::SimpleValueType enum. VT lists with more than one element are uniqued by a FoldingSet owned by the SelectionDAG object.

This patch moves the single element cache into SelectionDAG so that it will be destroyed when SelectionDAG is destroyed.

Fixes #88233

[llvmbot]

@llvm/pr-subscribers-llvm-selectiondag

Author: Craig Topper (topperc)

Changes

EVTs potentially contain a Type * that points into memory owned by an LLVMContext. Storing them in a function scoped static means they may outlive the LLVMContext they point to.

This std::set is used to unique single element VT lists containing a single extended EVT. Single element VT list with a simple EVT are uniqued by a separate cache indexed by the MVT::SimpleValueType enum. VT lists with more than one element are uniqued by a FoldingSet owned by the SelectionDAG object.

This patch removes the single element extended EVT cache and puts them in the FoldingSet instead. This ensures they won't outlive the LLVMContext.

There is a bit of a compile time hit for this. Data from a measurement last month https://llvm-compile-time-tracker.com/compare.php?from=38b0e1c939e818564019bb5bff95a0f1abbf9d19&to=4bd9484a0aa9d3ed55b50536b6810e8909533b4b&stat=instructions:ua

I wonder if it may be because types like i24, i40, i48, i56 can show up sometimes, but they aren't MVTs.

Fixes #88233

---

Full diff: https://github.com/llvm/llvm-project/pull/118715.diff

2 Files Affected:

• (modified) llvm/include/llvm/CodeGen/SelectionDAGNodes.h (+2-2)
• (modified) llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp (+19-10)

diff --git a/llvm/include/llvm/CodeGen/SelectionDAGNodes.h b/llvm/include/llvm/CodeGen/SelectionDAGNodes.h
index 677b59e0c8fbeb..61f3c6329efce8 100644
--- a/llvm/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/llvm/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -664,7 +664,7 @@ END_TWO_BYTE_PACK()
   DebugLoc debugLoc;
 
   /// Return a pointer to the specified value type.
-  static const EVT *getValueTypeList(EVT VT);
+  static const EVT *getValueTypeList(MVT VT);
 
   /// Index in worklist of DAGCombiner, or negative if the node is not in the
   /// worklist. -1 = not in worklist; -2 = not in worklist, but has already been
@@ -1124,7 +1124,7 @@ END_TWO_BYTE_PACK()
   void addUse(SDUse &U) { U.addToList(&UseList); }
 
 protected:
-  static SDVTList getSDVTList(EVT VT) {
+  static SDVTList getSDVTList(MVT VT) {
     SDVTList Ret = { getValueTypeList(VT), 1 };
     return Ret;
   }
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 182529123ec6d8..4cfebd39e07eae 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -10623,7 +10623,22 @@ SDValue SelectionDAG::getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList,
 }
 
 SDVTList SelectionDAG::getVTList(EVT VT) {
-  return makeVTList(SDNode::getValueTypeList(VT), 1);
+  if (!VT.isExtended())
+    return makeVTList(SDNode::getValueTypeList(VT.getSimpleVT()), 1);
+
+  FoldingSetNodeID ID;
+  ID.AddInteger(1U);
+  ID.AddInteger(VT.getRawBits());
+
+  void *IP = nullptr;
+  SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
+  if (!Result) {
+    EVT *Array = Allocator.Allocate<EVT>(1);
+    Array[0] = VT;
+    Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 1);
+    VTListMap.InsertNode(Result, IP);
+  }
+  return Result->getSDVTList();
 }
 
 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
@@ -12383,17 +12398,11 @@ namespace {
 
 /// getValueTypeList - Return a pointer to the specified value type.
 ///
-const EVT *SDNode::getValueTypeList(EVT VT) {
-  static std::set<EVT, EVT::compareRawBits> EVTs;
+const EVT *SDNode::getValueTypeList(MVT VT) {
   static EVTArray SimpleVTArray;
-  static sys::SmartMutex<true> VTMutex;
 
-  if (VT.isExtended()) {
-    sys::SmartScopedLock<true> Lock(VTMutex);
-    return &(*EVTs.insert(VT).first);
-  }
-  assert(VT.getSimpleVT() < MVT::VALUETYPE_SIZE && "Value type out of range!");
-  return &SimpleVTArray.VTs[VT.getSimpleVT().SimpleTy];
+  assert(VT < MVT::VALUETYPE_SIZE && "Value type out of range!");
+  return &SimpleVTArray.VTs[VT.SimpleTy];
 }
 
 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the

[efriedma-quic]

Is there some reason you're switching to FoldingSet, instead of just sticking with std::set? Not sure what the performance of FoldingSet is like, but any performance difference is probably related to that switch, not whether the std::set is a global.

[topperc]

Is there some reason you're switching to FoldingSet, instead of just sticking with std::set? Not sure what the performance of FoldingSet is like, but any performance difference is probably related to that switch, not whether the std::set is a global.

Only because the FoldingSet already existed for the multiple element case so it was easy to reuse. I'll try with a std::set.

[topperc]

Is there some reason you're switching to FoldingSet, instead of just sticking with std::set? Not sure what the performance of FoldingSet is like, but any performance difference is probably related to that switch, not whether the std::set is a global.

Only because the FoldingSet already existed for the multiple element case so it was easy to reuse. I'll try with a std::set.

Looks like moving the std::set into SelectionDAG gives better results. https://llvm-compile-time-tracker.com/compare.php?from=2fea1ccb6221238674562533684c51b63de248d4&to=76f11748278f882b13ed351c166797511e0ae825&stat=instructions:u

[arsenm]

Did you try all the set types? Does DenseSet do any better?

[topperc]

I didn't try DenseSEt. Looks like we would need to add a DenseMapInfo for EVT including defining Empty and Tombstone values?

[arsenm]

Yes

[efriedma-quic]

The usage here depends on the address stability of the map entries (the VTList points at the map's key), and DenseSet doesn't provide that. So you'd need define a struct like EVTSetKey Key { EVT* Ptr; };, define DenseMapInfo for that, then use DenseSet<EVTSetKey>.

I guess you could do that, but it seems like overkill.