[RISCV]Add support for resolving encoding conflicts among vendor specific CSRs

[quic-garvgupt]

This patch adds the framework for resolving encoding conflicts among CSRs.

Specifically, this patch adds a support for emitting a new lookup function for the primary key which return a pair of iterators pointing to first and last value hence giving a range of values which satisfies the query.

While printing the CSR name during objdump, iterate over the range and print the name of only that CSR which satisifes the feature requirement of subtarget.

Below is the signature of the new function that will be emitted for primary key:

llvm::iterator_range<const SysReg *>
lookupSysRegByEncoding(uint16_t Encoding) {
  SysReg Key;
  Key.Encoding = Encoding;
  auto Table = ArrayRef(SysRegsList);
  auto It = std::equal_range(Table.begin(), Table.end(), Key,
    [](const SysReg &LHS, const SysReg &RHS) {
      if (LHS.Encoding < RHS.Encoding)
        return true;
      if (LHS.Encoding > RHS.Encoding)
        return false;
      return false;
    });

  return llvm::make_range(It.first, It.second);
}

[llvmbot]

@llvm/pr-subscribers-backend-risc-v

Author: Garvit Gupta (quic-garvgupt)

Changes

This patch adds the framework for resolving encoding conflicts among CSRs.

Specifically, this patch adds a support for emitting a second lookup function for the primary key which takes an additional arguemnt List of type std::vector and inside the function definition, will populate the List with all sysreg that matches primary key.

While printing the CSR name during objdump, iterate over the List and print the name of only that CSR which satisifes the feature requirement of subtarget.

Below are the signatures of the functions that are generated for primary key:

`const SysReg *lookupSysRegByEncoding(uint16_t Encoding);`
`void lookupSysRegByEncoding(uint16_t Encoding, std::vector<const SysReg*> &List);`

Below is the definition for the second primary function:

void lookupSysRegByEncoding(uint16_t Encoding, std::vector<const SysReg*> &List) {
  struct KeyType {
    uint16_t Encoding;
  };
  KeyType Key = {Encoding};
  auto Table = ArrayRef(SysRegsList);
  auto Idx = std::lower_bound(Table.begin(), Table.end(), Key,
    [](const SysReg &LHS, const KeyType &RHS) {
      if (LHS.Encoding < RHS.Encoding)
        return true;
      if (LHS.Encoding > RHS.Encoding)
        return false;
      return false;
    });

  if (Idx == Table.end() ||
      Key.Encoding != Idx->Encoding)
    return;

  auto UpperBound = std::upper_bound(Table.begin(), Table.end(), Key,
    [](const KeyType &LHS, const SysReg &RHS) {
      if (LHS.Encoding < RHS.Encoding)
        return true;
      if (LHS.Encoding > RHS.Encoding)
        return false;
      return false;
    });

  while(Idx != UpperBound){
    List.push_back(&SysRegsList[Idx - Table.begin()]);
    Idx++;
  }
}

Usage: CSRs with same encodings need to be under separate features. Below is example illustrating the same-

let FeaturesRequired = [{ {Feature1} }] in {
def : SysReg<"csr1", 0x123>;
}

let FeaturesRequired = [{ {Feature2} }] in {
def : SysReg<"csr2", 0x123>;
}

---

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

2 Files Affected:

• (modified) llvm/lib/Target/RISCV/MCTargetDesc/RISCVInstPrinter.cpp (+9-5)
• (modified) llvm/utils/TableGen/SearchableTableEmitter.cpp (+90-43)

diff --git a/llvm/lib/Target/RISCV/MCTargetDesc/RISCVInstPrinter.cpp b/llvm/lib/Target/RISCV/MCTargetDesc/RISCVInstPrinter.cpp
index 48b669c78cade..57d74f1502c7c 100644
--- a/llvm/lib/Target/RISCV/MCTargetDesc/RISCVInstPrinter.cpp
+++ b/llvm/lib/Target/RISCV/MCTargetDesc/RISCVInstPrinter.cpp
@@ -121,11 +121,15 @@ void RISCVInstPrinter::printCSRSystemRegister(const MCInst *MI, unsigned OpNo,
                                               const MCSubtargetInfo &STI,
                                               raw_ostream &O) {
   unsigned Imm = MI->getOperand(OpNo).getImm();
-  auto SysReg = RISCVSysReg::lookupSysRegByEncoding(Imm);
-  if (SysReg && SysReg->haveRequiredFeatures(STI.getFeatureBits()))
-    markup(O, Markup::Register) << SysReg->Name;
-  else
-    markup(O, Markup::Register) << formatImm(Imm);
+  std::vector<const RISCVSysReg::SysReg *> CSRList;
+  RISCVSysReg::lookupSysRegByEncoding(Imm, CSRList);
+  for(auto &Reg : CSRList){
+    if (Reg->haveRequiredFeatures(STI.getFeatureBits())) {
+      markup(O, Markup::Register) << Reg->Name;
+      return;
+    }
+  }
+  markup(O, Markup::Register) << formatImm(Imm);
 }
 
 void RISCVInstPrinter::printFenceArg(const MCInst *MI, unsigned OpNo,
diff --git a/llvm/utils/TableGen/SearchableTableEmitter.cpp b/llvm/utils/TableGen/SearchableTableEmitter.cpp
index 48ee23db957de..b444e8494576d 100644
--- a/llvm/utils/TableGen/SearchableTableEmitter.cpp
+++ b/llvm/utils/TableGen/SearchableTableEmitter.cpp
@@ -190,9 +190,11 @@ class SearchableTableEmitter {
   void emitGenericTable(const GenericTable &Table, raw_ostream &OS);
   void emitGenericEnum(const GenericEnum &Enum, raw_ostream &OS);
   void emitLookupDeclaration(const GenericTable &Table,
-                             const SearchIndex &Index, raw_ostream &OS);
+                             const SearchIndex &Index, bool UseListArg,
+                             raw_ostream &OS);
   void emitLookupFunction(const GenericTable &Table, const SearchIndex &Index,
-                          bool IsPrimary, raw_ostream &OS);
+                          bool IsPrimary, bool UseListArg,
+                          raw_ostream &OS);
   void emitIfdef(StringRef Guard, raw_ostream &OS);
 
   bool parseFieldType(GenericField &Field, Init *II);
@@ -319,9 +321,10 @@ void SearchableTableEmitter::emitGenericEnum(const GenericEnum &Enum,
 void SearchableTableEmitter::emitLookupFunction(const GenericTable &Table,
                                                 const SearchIndex &Index,
                                                 bool IsPrimary,
+                                                bool UseListArg,
                                                 raw_ostream &OS) {
   OS << "\n";
-  emitLookupDeclaration(Table, Index, OS);
+  emitLookupDeclaration(Table, Index, UseListArg, OS);
   OS << " {\n";
 
   std::vector<Record *> IndexRowsStorage;
@@ -401,16 +404,19 @@ void SearchableTableEmitter::emitLookupFunction(const GenericTable &Table,
         Index.Loc, Field, IndexRows.back()->getValueInit(Field.Name));
     OS << "  if ((" << Field.Name << " < " << FirstRepr << ") ||\n";
     OS << "      (" << Field.Name << " > " << LastRepr << "))\n";
-    OS << "    return nullptr;\n";
+    if (UseListArg)
+      OS << "    return;\n";
+    else
+      OS << "    return nullptr;\n";
     OS << "  auto Table = ArrayRef(" << IndexName << ");\n";
     OS << "  size_t Idx = " << Index.Fields[0].Name << " - " << FirstRepr
        << ";\n";
-    OS << "  return ";
-    if (IsPrimary)
-      OS << "&Table[Idx]";
+    if (UseListArg)
+      OS << "  return;\n";
+    else if (IsPrimary)
+      OS << "  return &Table[Idx];\n";
     else
-      OS << "&" << Table.Name << "[Table[Idx]._index]";
-    OS << ";\n";
+      OS << "  return &" << Table.Name << "[Table[Idx]._index];\n";
     OS << "}\n";
     return;
   }
@@ -423,7 +429,10 @@ void SearchableTableEmitter::emitLookupFunction(const GenericTable &Table,
         Index.Loc, Field, IndexRows.back()->getValueInit(Field.Name));
     OS << "  if ((" << Field.Name << " < " << FirstRepr << ") ||\n";
     OS << "      (" << Field.Name << " > " << LastRepr << "))\n";
-    OS << "    return nullptr;\n\n";
+    if (UseListArg)
+      OS << "    return;\n\n";
+    else
+      OS << "    return nullptr;\n\n";
   }
 
   OS << "  struct KeyType {\n";
@@ -452,55 +461,80 @@ void SearchableTableEmitter::emitLookupFunction(const GenericTable &Table,
   OS << "  auto Idx = std::lower_bound(Table.begin(), Table.end(), Key,\n";
   OS << "    [](const " << IndexTypeName << " &LHS, const KeyType &RHS) {\n";
 
-  for (const auto &Field : Index.Fields) {
-    if (isa<StringRecTy>(Field.RecType)) {
-      OS << "      int Cmp" << Field.Name << " = StringRef(LHS." << Field.Name
-         << ").compare(RHS." << Field.Name << ");\n";
-      OS << "      if (Cmp" << Field.Name << " < 0) return true;\n";
-      OS << "      if (Cmp" << Field.Name << " > 0) return false;\n";
-    } else if (Field.Enum) {
-      // Explicitly cast to unsigned, because the signedness of enums is
-      // compiler-dependent.
-      OS << "      if ((unsigned)LHS." << Field.Name << " < (unsigned)RHS."
-         << Field.Name << ")\n";
-      OS << "        return true;\n";
-      OS << "      if ((unsigned)LHS." << Field.Name << " > (unsigned)RHS."
-         << Field.Name << ")\n";
-      OS << "        return false;\n";
-    } else {
-      OS << "      if (LHS." << Field.Name << " < RHS." << Field.Name << ")\n";
-      OS << "        return true;\n";
-      OS << "      if (LHS." << Field.Name << " > RHS." << Field.Name << ")\n";
-      OS << "        return false;\n";
+  auto emitComparator = [&]() {
+    for (const auto &Field : Index.Fields) {
+      if (isa<StringRecTy>(Field.RecType)) {
+        OS << "      int Cmp" << Field.Name << " = StringRef(LHS." << Field.Name
+           << ").compare(RHS." << Field.Name << ");\n";
+        OS << "      if (Cmp" << Field.Name << " < 0) return true;\n";
+        OS << "      if (Cmp" << Field.Name << " > 0) return false;\n";
+      } else if (Field.Enum) {
+        // Explicitly cast to unsigned, because the signedness of enums is
+        // compiler-dependent.
+        OS << "      if ((unsigned)LHS." << Field.Name << " < (unsigned)RHS."
+           << Field.Name << ")\n";
+        OS << "        return true;\n";
+        OS << "      if ((unsigned)LHS." << Field.Name << " > (unsigned)RHS."
+           << Field.Name << ")\n";
+        OS << "        return false;\n";
+      } else {
+        OS << "      if (LHS." << Field.Name << " < RHS." << Field.Name
+           << ")\n";
+        OS << "        return true;\n";
+        OS << "      if (LHS." << Field.Name << " > RHS." << Field.Name
+           << ")\n";
+        OS << "        return false;\n";
+      }
     }
-  }
 
-  OS << "      return false;\n";
-  OS << "    });\n\n";
+    OS << "      return false;\n";
+    OS << "    });\n\n";
+  };
+  emitComparator();
 
   OS << "  if (Idx == Table.end()";
 
   for (const auto &Field : Index.Fields)
     OS << " ||\n      Key." << Field.Name << " != Idx->" << Field.Name;
-  OS << ")\n    return nullptr;\n";
 
-  if (IsPrimary)
+  if (UseListArg) {
+    OS << ")\n    return;\n\n";
+    OS << "  auto UpperBound = std::upper_bound(Table.begin(), Table.end(), "
+          "Key,\n";
+    OS << "    [](const KeyType &LHS, const " << IndexTypeName << " &RHS) {\n";
+    emitComparator();
+    OS << "  while(Idx != UpperBound){\n";
+    OS << "    List.push_back(&" << Table.Name << "[Idx - Table.begin()]);\n";
+    OS << "    Idx++;\n";
+    OS << "  }\n";
+  } else if (IsPrimary) {
+    OS << ")\n    return nullptr;\n\n";
     OS << "  return &*Idx;\n";
-  else
+  } else {
+    OS << ")\n    return nullptr;\n\n";
     OS << "  return &" << Table.Name << "[Idx->_index];\n";
+  }
 
   OS << "}\n";
 }
 
 void SearchableTableEmitter::emitLookupDeclaration(const GenericTable &Table,
                                                    const SearchIndex &Index,
+                                                   bool UseListArg,
                                                    raw_ostream &OS) {
-  OS << "const " << Table.CppTypeName << " *" << Index.Name << "(";
-
+  if (UseListArg)
+    OS << "void ";
+  else
+    OS << "const " << Table.CppTypeName << " *";
+  OS << Index.Name << "(";
   ListSeparator LS;
   for (const auto &Field : Index.Fields)
     OS << LS << searchableFieldType(Table, Index, Field, TypeInArgument) << " "
        << Field.Name;
+
+  if (UseListArg)
+    OS << ", std::vector<const " << Table.CppTypeName << "*> &List";
+
   OS << ")";
 }
 
@@ -510,11 +544,14 @@ void SearchableTableEmitter::emitGenericTable(const GenericTable &Table,
 
   // Emit the declarations for the functions that will perform lookup.
   if (Table.PrimaryKey) {
-    emitLookupDeclaration(Table, *Table.PrimaryKey, OS);
+    auto &Index = *Table.PrimaryKey;
+    emitLookupDeclaration(Table, Index, /*UseListArg=*/false, OS);
+    OS << ";\n";
+    emitLookupDeclaration(Table, Index, /*UseListArg=*/true, OS);
     OS << ";\n";
   }
   for (const auto &Index : Table.Indices) {
-    emitLookupDeclaration(Table, *Index, OS);
+    emitLookupDeclaration(Table, *Index, /*UseListArg=*/false, OS);
     OS << ";\n";
   }
 
@@ -540,10 +577,20 @@ void SearchableTableEmitter::emitGenericTable(const GenericTable &Table,
 
   // Indexes are sorted "{ Thing, PrimaryIdx }" arrays, so that a binary
   // search can be performed by "Thing".
-  if (Table.PrimaryKey)
-    emitLookupFunction(Table, *Table.PrimaryKey, true, OS);
+  if (Table.PrimaryKey) {
+    auto &Index = *Table.PrimaryKey;
+    // Two lookupfunction functions need to be generated to allow more than one
+    // lookup signature for the primary key lookup : first will return a SysReg
+    // that matches the primary key, second will populate a vector passed as
+    // argument with all the SysRegs that match the primary key.
+    emitLookupFunction(Table, Index, /*IsPrimary=*/true,
+                       /*UseListArg=*/false, OS);
+    emitLookupFunction(Table, Index, /*IsPrimary=*/true,
+                       /*UseListArg=*/true, OS);
+  }
   for (const auto &Index : Table.Indices)
-    emitLookupFunction(Table, *Index, false, OS);
+    emitLookupFunction(Table, *Index, /*IsPrimary=*/false,
+                       /*UseListArg=*/false, OS);
 
   OS << "#endif\n\n";
 }

[quic-garvgupt]

Hi, @wangpc-pp , @apazos, @asb, @topperc , can you please review this PR? Thanks

Re: for creating separate PR for changes in searchable Tables @wangpc-pp

I understand that the changes will affect all targets, however before sending this PR to more broader set of reviewers, I wanted to know the comments from the reviewers of RISCV community because the framework here is to resolve encoding conflicts among CSRs, which as per my understanding in unique to RISCV. If and when this change is approved for RISCV, I will push it to a different PR with a broad set of reviewers.

[topperc]

Can lookupSysRegByEncoding use equal_range instead of calling lower_bound and upper_bound? Then iterate the returned range to push into the vector?

[topperc]

Can the new signature of lookupSysRegByEncoding return the std::pair from equal_range instead of needing to copy into a vector?

[apazos]

In past community discussion we talked about how vendor CSRs will require an extension guarding them to be able to resolve conflicting encoding. Hence in this patch only the framework for handling conflicting encoding was pushed.

@topperc, thanks for the suggestions.

It should be possible to return an iterator range instead of passing in a vector to be populated.

The decision to emit 2 APIs was to not break targets that already use the original API. This allows making a toolchain build that supports more than one target. I also understand only the PrimaryKey lookup function does the lookup by encoding. It is possible to add a variable to GenericTable to control the return value type of the PrimaryKey lookup function, but not sure it helps much. We build several targets, some with custom CSRs (like in RISC-V downstream toolchains) and targets that do not have them (e..g, ARM, AArch64, etc.) and need the original API. So at the end, the tablegen generated code will have to produce both APIs.

@quic-garvgupt, it will be great if you can add a tablegen test showing the usage example you have in the commit message.

[topperc]

We build several targets, some with custom CSRs (like in RISC-V downstream toolchains) and targets that do not have them (e..g, ARM, AArch64, etc.) and need the original API. So at the end, the tablegen generated code will have to produce both APIs.

Does the tablegen code being modified know about CSRs? Isn't it just a generic framework for a searchable table?

My suggestion was that RISCV would set the flag in its .td file to make the CSR table use a range. No other target needs to be affected since they won't set the flag.

[jrtc27]

We build several targets, some with custom CSRs (like in RISC-V downstream toolchains) and targets that do not have them (e..g, ARM, AArch64, etc.) and need the original API. So at the end, the tablegen generated code will have to produce both APIs.

Does the tablegen code being modified know about CSRs? Isn't it just a generic framework for a searchable table?

My suggestion was that RISCV would set the flag in its .td file to make the CSR table use a range. No other target needs to be affected since they won't set the flag.

Per-table index though, please, i.e. a bit in SearchIndex and a corresponding PrimaryKeyFoo one in GenericTable.

[topperc]

We build several targets, some with custom CSRs (like in RISC-V downstream toolchains) and targets that do not have them (e..g, ARM, AArch64, etc.) and need the original API. So at the end, the tablegen generated code will have to produce both APIs.

Does the tablegen code being modified know about CSRs? Isn't it just a generic framework for a searchable table? My suggestion was that RISCV would set the flag in its .td file to make the CSR table use a range. No other target needs to be affected since they won't set the flag.

Per-table index though, please, i.e. a bit in SearchIndex and a corresponding PrimaryKeyFoo one in GenericTable.

Agreed. It should be like PrimaryKeyEarlyOut in GenericTable and EarlyOut in SearchIndex.

[apazos]

It is fine to add the variables to GenericTable and SearchIndex to control the API being generated.

When upstreaming the framework the values of those variables will be set to false by default, since upstream RISC-V does not have vendor CSRs that can conflict.

Downstream users who have custom/vendor CSRs will set them to true but will require additional changes to call the proper API in RISCVAsmParser::parseCSRSystemRegister and RISCVInstPrinter::printCSRSystemRegister.

Maybe we can consider a separate patch that sets the variables to true for RISC-V and modifies parser/printer to use the new API. This way downstream users of RISC-V backend do not have the burden to maintain those changes. I think most downstream users have vendor/custom CSRs that have encoding conflict. Would that be acceptable?

[topperc]

Maybe we can consider a separate patch that sets the variables to true for RISC-V and modifies parser/printer to use the new API. This way downstream users of RISC-V backend do not have the burden to maintain those changes. I think most downstream users have vendor/custom CSRs that have encoding conflict. Would that be acceptable?

Yes. I definitely think we should do that.

[apazos]

Sounds good, @topperc!

@quic-garvgupt, please have a follow up patch that will set the vars to true for RISC-V target.

[github-actions[bot]]

:white_check_mark: With the latest revision this PR passed the C/C++ code formatter.

[topperc]

Please retitle this patch and update the description. The only thing in this patch is a new tablegen feature that should be described on its own. The RISC-V use case can be used to justify it, but should not be the primary description.

[nvjle]

Please also update the SearchableTables Reference in docs/TableGen/BackEnds.rst.

[quic-garvgupt]

I am not able to install the dependencies needed to build the documentation locally. I will really appreciate if someone else can build the documentation and verify if the changes in BackEnds.rst file are fine. Thanks

[francisvm]

I am not able to install the dependencies needed to build the documentation locally. I will really appreciate if someone else can build the documentation and verify if the changes in BackEnds.rst file are fine. Thanks

The "Test documentation build" check below does ninja docs-llvm-html docs-llvm-man, and looks successful, so I think you're good.

[quic-garvgupt]

I am not able to install the dependencies needed to build the documentation locally. I will really appreciate if someone else can build the documentation and verify if the changes in BackEnds.rst file are fine. Thanks

The "Test documentation build" check below does ninja docs-llvm-html docs-llvm-man, and looks successful, so I think you're good.

I didn't realize we build documentation. Thanks for letting me know!