[TBLGEN] Fix subreg value overflow in DAGISelMatcher

[rampitec]

Summary

Tablegen's DAGISelMatcher emits integers in a VBR format,
so if an integer is below 128 it can fit into a single
byte, otherwise high bit is set, next byte is used etc.
MatcherTable is essentially an unsigned char table. When
SelectionDAGISel parses the table it does a reverse translation.

In a situation when numeric value of an integer to emit is
unknown it can be emitted not as OPC_EmitInteger but as
OPC_EmitStringInteger using a symbolic name of the value.
In this situation the value should not exceed 127.

One of the situations when OPC_EmitStringInteger is used is
if we need to emit a subreg into a matcher table. However,
number of subregs can exceed 127. Currently last defined subreg
for AMDGPU is 192. That results in a silent bug in the ISel
with matcher reading from an invalid offset.

Fixed this bug to emit actual VBR encoded value for a subregs
which value exceeds 127.

[rampitec]

Moved check inside test .

[arsenm]

llvm/utils/TableGen/DAGISelMatcherGen.cpp

718

Spelling indicies

719

Typo cannout

722–725

I would except this to check a function in CodeGenRegBank rather than needing to do a find_if on a list

[rampitec]

Addressed review comments.

[arsenm]

llvm/test/TableGen/dag-isel-subregs.td

12

Can you split all of these register definitions into a template file in Common? I'll want to re-use this at some point

llvm/utils/TableGen/DAGISelMatcherGen.cpp

722

Actually, why do you need to do the name lookup at all? Can't you juts do CodeGenRegBank.getSubRegIdx(Def)?

[rampitec]

Addressed review comments.

[rampitec]

llvm/utils/TableGen/DAGISelMatcherGen.cpp

722

I had to create another function which just lookups the map by Def, as CGP is constant. But you are right, string lookup was not needed.

[bcain]

llvm/utils/TableGen/RegisterInfoEmitter.cpp

176

Is it expected that the context for this .inc should have already included <cstdint> or that tablegen should be emitting that include in order to use this type?

[rampitec]

llvm/utils/TableGen/RegisterInfoEmitter.cpp

176

That is produced by the tablegen in many different places, so I assume it should be already defined.

llvm/test/TableGen/Common/reg-with-subregs-common.td

+include "llvm/Target/Target.td"
+
+def TestTargetInstrInfo : InstrInfo;
+
+def TestTarget : Target {
+  let InstructionSet = TestTargetInstrInfo;
+}
+
+class Indexes<int N> {
+  list<int> all = [0,   1,  2,  3,  4,  5,  6 , 7,
+                   8,   9, 10, 11, 12, 13, 14, 15,
+                   16, 17, 18, 19, 20, 21, 22, 23,
+                   24, 25, 26, 27, 28, 29, 30, 31];
+  list<int> slice =
+    !foldl([]<int>, all, acc, cur,
+           !listconcat(acc, !if(!lt(cur, N), [cur], [])));
+}
+
+foreach Index = 0-31 in {
+  def sub#Index : SubRegIndex<32, !shl(Index, 5)>;
+}
+
+foreach Size = {2,4,8,16} in {
+  foreach Index = Indexes<!add(33, !mul(Size, -1))>.slice in {
+    def !foldl("", Indexes<Size>.slice, acc, cur,
+               !strconcat(acc#!if(!eq(acc,""),"","_"), "sub"#!add(cur, Index))) :
+      SubRegIndex<!mul(Size, 32), !shl(Index, 5)> {
+      let CoveringSubRegIndices =
+        !foldl([]<SubRegIndex>, Indexes<Size>.slice, acc, cur,
+               !listconcat(acc, [!cast<SubRegIndex>(sub#!add(cur, Index))]));
+    }
+  }
+}
+
+foreach Index = 0-255 in {
+  def R#Index : Register <"r"#Index>;
+}
+
+def GPR32 : RegisterClass<"TestTarget", [i32], 32,
+                          (add (sequence "R%u", 0, 255))>;
+
+def GPR64 : RegisterTuples<[sub0, sub1],
+                           [(decimate (shl GPR32, 0), 1),
+                            (decimate (shl GPR32, 1), 1)
+                           ]>;
+
+def GPR128 : RegisterTuples<[sub0, sub1, sub2, sub3],
+                            [
+                             (decimate (shl GPR32, 0), 1),
+                             (decimate (shl GPR32, 1), 1),
+                             (decimate (shl GPR32, 2), 1),
+                             (decimate (shl GPR32, 3), 1)
+                            ]>;
+
+def GPR256 : RegisterTuples<[sub0, sub1, sub2, sub3, sub4, sub5, sub6, sub7],
+                             [
+                              (decimate (shl GPR32, 0), 1),
+                              (decimate (shl GPR32, 1), 1),
+                              (decimate (shl GPR32, 2), 1),
+                              (decimate (shl GPR32, 3), 1),
+                              (decimate (shl GPR32, 4), 1),
+                              (decimate (shl GPR32, 5), 1),
+                              (decimate (shl GPR32, 6), 1),
+                              (decimate (shl GPR32, 7), 1)
+                             ]>;
+
+def GPR512 : RegisterTuples<[sub0, sub1, sub2, sub3, sub4, sub5, sub6, sub7,
+                             sub8, sub9, sub10, sub11, sub12, sub13, sub14, sub15],
+                             [
+                              (decimate (shl GPR32, 0), 1),
+                              (decimate (shl GPR32, 1), 1),
+                              (decimate (shl GPR32, 2), 1),
+                              (decimate (shl GPR32, 3), 1),
+                              (decimate (shl GPR32, 4), 1),
+                              (decimate (shl GPR32, 5), 1),
+                              (decimate (shl GPR32, 6), 1),
+                              (decimate (shl GPR32, 7), 1),
+                              (decimate (shl GPR32, 8), 1),
+                              (decimate (shl GPR32, 9), 1),
+                              (decimate (shl GPR32, 10), 1),
+                              (decimate (shl GPR32, 11), 1),
+                              (decimate (shl GPR32, 12), 1),
+                              (decimate (shl GPR32, 13), 1),
+                              (decimate (shl GPR32, 14), 1),
+                              (decimate (shl GPR32, 15), 1)
+                             ]>;
+
+def GPR1024 : RegisterTuples<[sub0, sub1, sub2, sub3, sub4, sub5, sub6, sub7,
+                              sub8, sub9, sub10, sub11, sub12, sub13, sub14, sub15,
+                              sub16, sub17, sub18, sub19, sub20, sub21, sub22, sub23,
+                              sub24, sub25, sub26, sub27, sub28, sub29, sub30, sub31],
+                             [
+                              (decimate (shl GPR32, 0), 1),
+                              (decimate (shl GPR32, 1), 1),
+                              (decimate (shl GPR32, 2), 1),
+                              (decimate (shl GPR32, 3), 1),
+                              (decimate (shl GPR32, 4), 1),
+                              (decimate (shl GPR32, 5), 1),
+                              (decimate (shl GPR32, 6), 1),
+                              (decimate (shl GPR32, 7), 1),
+                              (decimate (shl GPR32, 8), 1),
+                              (decimate (shl GPR32, 9), 1),
+                              (decimate (shl GPR32, 10), 1),
+                              (decimate (shl GPR32, 11), 1),
+                              (decimate (shl GPR32, 12), 1),
+                              (decimate (shl GPR32, 13), 1),
+                              (decimate (shl GPR32, 14), 1),
+                              (decimate (shl GPR32, 15), 1),
+                              (decimate (shl GPR32, 16), 1),
+                              (decimate (shl GPR32, 17), 1),
+                              (decimate (shl GPR32, 18), 1),
+                              (decimate (shl GPR32, 19), 1),
+                              (decimate (shl GPR32, 20), 1),
+                              (decimate (shl GPR32, 21), 1),
+                              (decimate (shl GPR32, 22), 1),
+                              (decimate (shl GPR32, 23), 1),
+                              (decimate (shl GPR32, 24), 1),
+                              (decimate (shl GPR32, 25), 1),
+                              (decimate (shl GPR32, 26), 1),
+                              (decimate (shl GPR32, 27), 1),
+                              (decimate (shl GPR32, 28), 1),
+                              (decimate (shl GPR32, 29), 1),
+                              (decimate (shl GPR32, 30), 1),
+                              (decimate (shl GPR32, 31), 1)
+                             ]>;
+
+def GPR_64 : RegisterClass<"", [v2i32], 64, (add GPR64)>;
+def GPR_1024 : RegisterClass<"", [v32i32], 1024, (add GPR1024)>;

llvm/test/TableGen/dag-isel-subregs.td

+// RUN: llvm-tblgen -gen-dag-isel -I %p/../../include -I %p/Common %s | FileCheck %s
+
+include "reg-with-subregs-common.td"
+
+// CHECK-LABEL: OPC_CheckOpcode, TARGET_VAL(ISD::EXTRACT_SUBVECTOR),
+// CHECK: OPC_CheckChild1Integer, 0,
+// CHECK: OPC_EmitInteger, MVT::i32, sub0_sub1,
+def : Pat<(v2i32 (extract_subvector v32i32:$src, (i32 0))),
+          (EXTRACT_SUBREG GPR_1024:$src, sub0_sub1)>;
+
+// CHECK: OPC_CheckChild1Integer, 15,
+// CHECK: OPC_EmitInteger, MVT::i32, 5|128,1/*133*/,
+def : Pat<(v2i32 (extract_subvector v32i32:$src, (i32 15))),
+          (EXTRACT_SUBREG GPR_1024:$src, sub30_sub31)>;

llvm/utils/TableGen/CodeGenRegisters.h

public:
 
     // Sub-register indices. The first NumNamedIndices are defined by the user
     // in the .td files. The rest are synthesized such that all sub-registers
     // have a unique name.
     const std::deque<CodeGenSubRegIndex> &getSubRegIndices() const {
       return SubRegIndices;
     }
 
-    // Find a SubRegIndex form its Record def.
+    // Find a SubRegIndex from its Record def or add to the list if it does
+    // not exist there yet.
     CodeGenSubRegIndex *getSubRegIdx(Record*);
 
+    // Find a SubRegIndex from its Record def.
+    const CodeGenSubRegIndex *findSubRegIdx(const Record* Def) const;
+
     // Find or create a sub-register index representing the A+B composition.
     CodeGenSubRegIndex *getCompositeSubRegIndex(CodeGenSubRegIndex *A,
                                                 CodeGenSubRegIndex *B);
 
     // Find or create a sub-register index representing the concatenation of
     // non-overlapping sibling indices.
     CodeGenSubRegIndex *
       getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8>&);

llvm/utils/TableGen/CodeGenRegisters.cpp

CodeGenSubRegIndex *CodeGenRegBank::getSubRegIdx(Record *Def) {
   CodeGenSubRegIndex *&Idx = Def2SubRegIdx[Def];
   if (Idx)
     return Idx;
   SubRegIndices.emplace_back(Def, SubRegIndices.size() + 1);
   Idx = &SubRegIndices.back();
   return Idx;
 }
 
+const CodeGenSubRegIndex *
+CodeGenRegBank::findSubRegIdx(const Record* Def) const {
+  auto I = Def2SubRegIdx.find(Def);
+  return (I == Def2SubRegIdx.end()) ? nullptr : I->second;
+}
+
 CodeGenRegister *CodeGenRegBank::getReg(Record *Def) {
   CodeGenRegister *&Reg = Def2Reg[Def];
   if (Reg)
     return Reg;
   Registers.emplace_back(Def, Registers.size() + 1);
   Reg = &Registers.back();
   return Reg;
 }

llvm/utils/TableGen/DAGISelMatcherEmitter.cpp

case Matcher::EmitInteger: {
     OS << "OPC_EmitInteger, "
        << getEnumName(cast<EmitIntegerMatcher>(N)->getVT()) << ", ";
     unsigned Bytes = 2+EmitVBRValue(Val, OS);
     OS << '\n';
     return Bytes;
   }
   case Matcher::EmitStringInteger: {
     const std::string &Val = cast<EmitStringIntegerMatcher>(N)->getValue();
-    // These should always fit into one byte.
+    // These should always fit into 7 bits.
     OS << "OPC_EmitInteger, "
       << getEnumName(cast<EmitStringIntegerMatcher>(N)->getVT()) << ", "
       << Val << ",\n";
     return 3;
   }
 
   case Matcher::EmitRegister: {
     const EmitRegisterMatcher *Matcher = cast<EmitRegisterMatcher>(N);

llvm/utils/TableGen/DAGISelMatcherGen.cpp

if (Def->isSubClassOf("RegisterClass")) {
       std::string Value = getQualifiedName(Def) + "RegClassID";
       AddMatcher(new EmitStringIntegerMatcher(Value, MVT::i32));
       ResultOps.push_back(NextRecordedOperandNo++);
       return;
     }
 
     // Handle a subregister index. This is used for INSERT_SUBREG etc.
     if (Def->isSubClassOf("SubRegIndex")) {
+      const CodeGenRegBank &RB = CGP.getTargetInfo().getRegBank();
+      // If we have more than 127 subreg indices the encoding can overflow
+      // 7 bit and we cannot use StringInteger.
+      if (RB.getSubRegIndices().size() > 127) {
+        const CodeGenSubRegIndex *I = RB.findSubRegIdx(Def);
+        assert(I && "Cannot find subreg index by name!");
+        if (I->EnumValue > 127) {
+          AddMatcher(new EmitIntegerMatcher(I->EnumValue, MVT::i32));
+          ResultOps.push_back(NextRecordedOperandNo++);
+          return;
+        }
+      }
       std::string Value = getQualifiedName(Def);
       AddMatcher(new EmitStringIntegerMatcher(Value, MVT::i32));
       ResultOps.push_back(NextRecordedOperandNo++);
       return;
     }
   }
 
   errs() << "unhandled leaf node: \n";

llvm/utils/TableGen/RegisterInfoEmitter.cpp

void RegisterInfoEmitter::runEnums(raw_ostream &OS,
   }
 
   auto &SubRegIndices = Bank.getSubRegIndices();
   if (!SubRegIndices.empty()) {
     OS << "\n// Subregister indices\n\n";
     std::string Namespace = SubRegIndices.front().getNamespace();
     if (!Namespace.empty())
       OS << "namespace " << Namespace << " {\n";
-    OS << "enum {\n  NoSubRegister,\n";
+    OS << "enum : uint16_t {\n  NoSubRegister,\n";
     unsigned i = 0;
     for (const auto &Idx : SubRegIndices)
       OS << "  " << Idx.getName() << ",\t// " << ++i << "\n";
     OS << "  NUM_TARGET_SUBREGS\n};\n";
     if (!Namespace.empty())
       OS << "} // end namespace " << Namespace << "\n\n";
   }