From a52b8ce7b14dd492f20b1041df97c48e98db922a Mon Sep 17 00:00:00 2001
From: "A. Jiang" <de34@live.cn>
Date: Sun, 28 Sep 2025 21:36:03 +0800
Subject: [PATCH] [CodeGen] Get rid of incorrect `std` template specializations
 (#160804)

This is a backport of llvm a558d6560437 to release/21.x, with slight
context adjustment due to llvm 356be1a36ecc not being present.

> This patch renames comparators
> - from `std::equal_to<llvm::rdf::RegisterRef>` to
> `llvm::rdf::RegisterRefEqualTo`, and
> - from `std::less<llvm::rdf::RegisterRef>` to
> `llvm::rdf::RegisterRefLess`.
>
> The original specializations don't satisfy the requirements for the
> original `std` templates by being stateful and
> non-default-constructible, so they make the program have UB due to C++17
> [namespace.std]/2, C++20/23 [namespace.std]/5.
>
> > A program may explicitly instantiate a class template defined in the
> standard library only if the declaration
> > - depends on the name of at least one program-defined type, and
> > - the instantiation meets the standard library requirements for the
> original template.

This also contains a follow-up fix from llvm 99f296d2a811:

> [CodeGen][test] Fix Buildbot failure due to uninitialized variables (#161085)
>
> Under some options used by LLVM Buildbot, an uninitialized variable
> (recently added to the test suite) caused constant evaluation failure,
> despite the type of that variable is an empty class.
>
> This PR explicitly initializes the variables with `{}` to fix the error.
> Follows-up a558d656043734cc4d02e0a0a12e4c308c28f8c7.
---
 llvm/include/llvm/CodeGen/RDFGraph.h      |  2 +-
 llvm/include/llvm/CodeGen/RDFRegisters.h  | 54 ++++++++++++-----------
 llvm/lib/CodeGen/RDFLiveness.cpp          |  9 ++--
 llvm/lib/Target/Hexagon/RDFCopy.cpp       |  2 +-
 llvm/lib/Target/Hexagon/RDFCopy.h         |  8 ++--
 llvm/unittests/CodeGen/TypeTraitsTest.cpp | 36 +++++++++++++++
 6 files changed, 75 insertions(+), 36 deletions(-)

diff --git a/llvm/include/llvm/CodeGen/RDFGraph.h b/llvm/include/llvm/CodeGen/RDFGraph.h
index 8a93afbcb549..6bb6033a8a2f 100644
--- a/llvm/include/llvm/CodeGen/RDFGraph.h
+++ b/llvm/include/llvm/CodeGen/RDFGraph.h
@@ -447,7 +447,7 @@ private:
   AllocatorTy MemPool;
 };
 
-using RegisterSet = std::set<RegisterRef>;
+using RegisterSet = std::set<RegisterRef, RegisterRefLess>;
 
 struct TargetOperandInfo {
   TargetOperandInfo(const TargetInstrInfo &tii) : TII(tii) {}
diff --git a/llvm/include/llvm/CodeGen/RDFRegisters.h b/llvm/include/llvm/CodeGen/RDFRegisters.h
index 4a9a4063c9e8..82027cad53bd 100644
--- a/llvm/include/llvm/CodeGen/RDFRegisters.h
+++ b/llvm/include/llvm/CodeGen/RDFRegisters.h
@@ -199,6 +199,33 @@ private:
   std::vector<AliasInfo> AliasInfos;
 };
 
+struct RegisterRefEqualTo {
+  constexpr RegisterRefEqualTo(const llvm::rdf::PhysicalRegisterInfo &pri)
+      : PRI(&pri) {}
+
+  bool operator()(llvm::rdf::RegisterRef A, llvm::rdf::RegisterRef B) const {
+    return PRI->equal_to(A, B);
+  }
+
+private:
+  // Make it a pointer just in case. See comment in `RegisterRefLess` below.
+  const llvm::rdf::PhysicalRegisterInfo *PRI;
+};
+
+struct RegisterRefLess {
+  constexpr RegisterRefLess(const llvm::rdf::PhysicalRegisterInfo &pri)
+      : PRI(&pri) {}
+
+  bool operator()(llvm::rdf::RegisterRef A, llvm::rdf::RegisterRef B) const {
+    return PRI->less(A, B);
+  }
+
+private:
+  // Make it a pointer because apparently some versions of MSVC use std::swap
+  // on the comparator object.
+  const llvm::rdf::PhysicalRegisterInfo *PRI;
+};
+
 struct RegisterAggr {
   RegisterAggr(const PhysicalRegisterInfo &pri)
       : Units(pri.getTRI().getNumRegUnits()), PRI(pri) {}
@@ -334,18 +361,6 @@ template <> struct hash<llvm::rdf::RegisterAggr> {
   }
 };
 
-template <> struct equal_to<llvm::rdf::RegisterRef> {
-  constexpr equal_to(const llvm::rdf::PhysicalRegisterInfo &pri) : PRI(&pri) {}
-
-  bool operator()(llvm::rdf::RegisterRef A, llvm::rdf::RegisterRef B) const {
-    return PRI->equal_to(A, B);
-  }
-
-private:
-  // Make it a pointer just in case. See comment in `less` below.
-  const llvm::rdf::PhysicalRegisterInfo *PRI;
-};
-
 template <> struct equal_to<llvm::rdf::RegisterAggr> {
   bool operator()(const llvm::rdf::RegisterAggr &A,
                   const llvm::rdf::RegisterAggr &B) const {
@@ -353,23 +368,10 @@ template <> struct equal_to<llvm::rdf::RegisterAggr> {
   }
 };
 
-template <> struct less<llvm::rdf::RegisterRef> {
-  constexpr less(const llvm::rdf::PhysicalRegisterInfo &pri) : PRI(&pri) {}
-
-  bool operator()(llvm::rdf::RegisterRef A, llvm::rdf::RegisterRef B) const {
-    return PRI->less(A, B);
-  }
-
-private:
-  // Make it a pointer because apparently some versions of MSVC use std::swap
-  // on the std::less specialization.
-  const llvm::rdf::PhysicalRegisterInfo *PRI;
-};
-
 } // namespace std
 
 namespace llvm::rdf {
-using RegisterSet = std::set<RegisterRef, std::less<RegisterRef>>;
+using RegisterSet = std::set<RegisterRef, RegisterRefLess>;
 } // namespace llvm::rdf
 
 #endif // LLVM_CODEGEN_RDFREGISTERS_H
diff --git a/llvm/lib/CodeGen/RDFLiveness.cpp b/llvm/lib/CodeGen/RDFLiveness.cpp
index 318422b46e81..2e1cf499eab4 100644
--- a/llvm/lib/CodeGen/RDFLiveness.cpp
+++ b/llvm/lib/CodeGen/RDFLiveness.cpp
@@ -652,8 +652,9 @@ void Liveness::computePhiInfo() {
   // defs, cache the result of subtracting these defs from a given register
   // ref.
   using RefHash = std::hash<RegisterRef>;
-  using RefEqual = std::equal_to<RegisterRef>;
-  using SubMap = std::unordered_map<RegisterRef, RegisterRef>;
+  using RefEqual = RegisterRefEqualTo;
+  using SubMap =
+      std::unordered_map<RegisterRef, RegisterRef, RefHash, RefEqual>;
   std::unordered_map<RegisterAggr, SubMap> Subs;
   auto ClearIn = [](RegisterRef RR, const RegisterAggr &Mid, SubMap &SM) {
     if (Mid.empty())
@@ -868,7 +869,7 @@ void Liveness::computeLiveIns() {
       std::vector<RegisterRef> LV;
       for (const MachineBasicBlock::RegisterMaskPair &LI : B.liveins())
         LV.push_back(RegisterRef(LI.PhysReg, LI.LaneMask));
-      llvm::sort(LV, std::less<RegisterRef>(PRI));
+      llvm::sort(LV, RegisterRefLess(PRI));
       dbgs() << printMBBReference(B) << "\t rec = {";
       for (auto I : LV)
         dbgs() << ' ' << Print(I, DFG);
@@ -878,7 +879,7 @@ void Liveness::computeLiveIns() {
       LV.clear();
       for (RegisterRef RR : LiveMap[&B].refs())
         LV.push_back(RR);
-      llvm::sort(LV, std::less<RegisterRef>(PRI));
+      llvm::sort(LV, RegisterRefLess(PRI));
       dbgs() << "\tcomp = {";
       for (auto I : LV)
         dbgs() << ' ' << Print(I, DFG);
diff --git a/llvm/lib/Target/Hexagon/RDFCopy.cpp b/llvm/lib/Target/Hexagon/RDFCopy.cpp
index fafdad08909d..3b1d3bd89680 100644
--- a/llvm/lib/Target/Hexagon/RDFCopy.cpp
+++ b/llvm/lib/Target/Hexagon/RDFCopy.cpp
@@ -108,7 +108,7 @@ bool CopyPropagation::scanBlock(MachineBasicBlock *B) {
   for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
     if (DFG.IsCode<NodeAttrs::Stmt>(IA)) {
       NodeAddr<StmtNode*> SA = IA;
-      EqualityMap EM(std::less<RegisterRef>(DFG.getPRI()));
+      EqualityMap EM(RegisterRefLess(DFG.getPRI()));
       if (interpretAsCopy(SA.Addr->getCode(), EM))
         recordCopy(SA, EM);
     }
diff --git a/llvm/lib/Target/Hexagon/RDFCopy.h b/llvm/lib/Target/Hexagon/RDFCopy.h
index e4fb89892831..92b2c6598265 100644
--- a/llvm/lib/Target/Hexagon/RDFCopy.h
+++ b/llvm/lib/Target/Hexagon/RDFCopy.h
@@ -25,8 +25,8 @@ class MachineInstr;
 namespace rdf {
 
   struct CopyPropagation {
-    CopyPropagation(DataFlowGraph &dfg) : MDT(dfg.getDT()), DFG(dfg),
-        RDefMap(std::less<RegisterRef>(DFG.getPRI())) {}
+    CopyPropagation(DataFlowGraph &dfg)
+        : MDT(dfg.getDT()), DFG(dfg), RDefMap(RegisterRefLess(DFG.getPRI())) {}
 
     virtual ~CopyPropagation() = default;
 
@@ -35,7 +35,7 @@ namespace rdf {
     bool trace() const { return Trace; }
     DataFlowGraph &getDFG() { return DFG; }
 
-    using EqualityMap = std::map<RegisterRef, RegisterRef>;
+    using EqualityMap = std::map<RegisterRef, RegisterRef, RegisterRefLess>;
     virtual bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM);
 
   private:
@@ -45,7 +45,7 @@ namespace rdf {
     bool Trace = false;
 
     // map: register -> (map: stmt -> reaching def)
-    std::map<RegisterRef,std::map<NodeId,NodeId>> RDefMap;
+    std::map<RegisterRef, std::map<NodeId, NodeId>, RegisterRefLess> RDefMap;
     // map: statement -> (map: dst reg -> src reg)
     std::map<NodeId, EqualityMap> CopyMap;
     std::vector<NodeId> Copies;
diff --git a/llvm/unittests/CodeGen/TypeTraitsTest.cpp b/llvm/unittests/CodeGen/TypeTraitsTest.cpp
index 0ca4fa4e82c7..c32ae155f7a1 100644
--- a/llvm/unittests/CodeGen/TypeTraitsTest.cpp
+++ b/llvm/unittests/CodeGen/TypeTraitsTest.cpp
@@ -6,13 +6,16 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/CodeGen/RDFRegisters.h"
 #include "llvm/CodeGen/RegisterPressure.h"
 #include "llvm/CodeGen/ScheduleDAG.h"
 #include "llvm/CodeGen/SelectionDAGNodes.h"
 #include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "gtest/gtest.h"
+#include <functional>
 #include <type_traits>
+#include <utility>
 
 using namespace llvm;
 
@@ -24,5 +27,38 @@ static_assert(std::is_trivially_copyable_v<SDValue>, "trivially copyable");
 static_assert(std::is_trivially_copyable_v<SlotIndex>, "trivially copyable");
 static_assert(std::is_trivially_copyable_v<IdentifyingPassPtr>,
               "trivially copyable");
+
+// https://llvm.org/PR105169
+// Verify that we won't accidently specialize std::less and std::equal_to in a
+// wrong way.
+// C++17 [namespace.std]/2, C++20/23 [namespace.std]/5:
+//   A program may explicitly instantiate a template defined in the standard
+//   library only if the declaration
+//   - depends on the name of a user-defined type and
+//   - the instantiation meets the standard library requirements for the
+//   original template.
+template <class Fn> constexpr bool CheckStdCmpRequirements() {
+  // std::less and std::equal_to are literal, default constructible, and
+  // copyable classes.
+  Fn f1{};
+  auto f2 = f1;
+  auto f3 = std::move(f2);
+  f2 = f3;
+  f2 = std::move(f3);
+
+  // Properties held on all known implementations, although not guaranteed by
+  // the standard.
+  static_assert(std::is_empty_v<Fn>);
+  static_assert(std::is_trivially_default_constructible_v<Fn>);
+  static_assert(std::is_trivially_copyable_v<Fn>);
+
+  return true;
+}
+
+static_assert(CheckStdCmpRequirements<std::less<rdf::RegisterRef>>(),
+              "same as the original template");
+static_assert(CheckStdCmpRequirements<std::equal_to<rdf::RegisterRef>>(),
+              "same as the original template");
+
 #endif
 
-- 
2.54.0

