[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

721

Spelling indicies

722

Typo cannout

725–728

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

725

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

725

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/dag-isel-subregs.td

+// RUN: llvm-tblgen -gen-dag-isel -I %p/../../include %s | FileCheck %s
+
+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)>;
+
+// 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/DAGISelEmitter.cpp

void DAGISelEmitter::run(raw_ostream &OS) {
   // We want to process the matches in order of minimal cost.  Sort the patterns
   // so the least cost one is at the start.
   std::stable_sort(Patterns.begin(), Patterns.end(),
                    PatternSortingPredicate(CGP));
 
 
   // Convert each variant of each pattern into a Matcher.
   std::vector<Matcher*> PatternMatchers;
+  const std::deque<CodeGenSubRegIndex> &SRI =
+    CGP.getTargetInfo().getRegBank().getSubRegIndices();
   for (unsigned i = 0, e = Patterns.size(); i != e; ++i) {
     for (unsigned Variant = 0; ; ++Variant) {
-      if (Matcher *M = ConvertPatternToMatcher(*Patterns[i], Variant, CGP))
+      if (Matcher *M = ConvertPatternToMatcher(*Patterns[i], Variant, CGP, SRI))
         PatternMatchers.push_back(M);
       else
         break;
     }
   }
 
   std::unique_ptr<Matcher> TheMatcher =
     std::make_unique<ScopeMatcher>(PatternMatchers);

llvm/utils/TableGen/DAGISelMatcher.h

 //===- DAGISelMatcher.h - Representation of DAG pattern matcher -*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_UTILS_TABLEGEN_DAGISELMATCHER_H
 #define LLVM_UTILS_TABLEGEN_DAGISELMATCHER_H
 
+#include "CodeGenRegisters.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/MachineValueType.h"
 
 namespace llvm {
   struct CodeGenRegister;
   class CodeGenDAGPatterns;
   class Matcher;
   class PatternToMatch;
   class raw_ostream;
   class ComplexPattern;
   class Record;
   class SDNodeInfo;
   class TreePredicateFn;
   class TreePattern;
 
 Matcher *ConvertPatternToMatcher(const PatternToMatch &Pattern,unsigned Variant,
-                                 const CodeGenDAGPatterns &CGP);
+                                 const CodeGenDAGPatterns &CGP,
+                                 const std::deque<CodeGenSubRegIndex> &SRI);
 void OptimizeMatcher(std::unique_ptr<Matcher> &Matcher,
                      const CodeGenDAGPatterns &CGP);
 void EmitMatcherTable(const Matcher *Matcher, const CodeGenDAGPatterns &CGP,
                       raw_ostream &OS);
 
 
 /// Matcher - Base class for all the DAG ISel Matcher representation
 /// nodes.

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

#endif
   return VT;
 }
 
 
 namespace {
   class MatcherGen {
     const PatternToMatch &Pattern;
     const CodeGenDAGPatterns &CGP;
+    const std::deque<CodeGenSubRegIndex> &SRI;
 
     /// PatWithNoTypes - This is a clone of Pattern.getSrcPattern() that starts
     /// out with all of the types removed.  This allows us to insert type checks
     /// as we scan the tree.
     TreePatternNodePtr PatWithNoTypes;
 
     /// VariableMap - A map from variable names ('$dst') to the recorded operand
     /// number that they were captured as.  These are biased by 1 to make
class MatcherGen {
 
     /// Matcher - This is the top level of the generated matcher, the result.
     Matcher *TheMatcher;
 
     /// CurPredicate - As we emit matcher nodes, this points to the latest check
     /// which should have future checks stuck into its Next position.
     Matcher *CurPredicate;
   public:
-    MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp);
+    MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp,
+               const std::deque<CodeGenSubRegIndex> &SRI);
 
     bool EmitMatcherCode(unsigned Variant);
     void EmitResultCode();
 
     Matcher *GetMatcher() const { return TheMatcher; }
   private:
     void AddMatcher(Matcher *NewNode);
     void InferPossibleTypes(unsigned ForceMode);
void EmitResultInstructionAsOperand(const TreePatternNode *N,
                                         SmallVectorImpl<unsigned> &ResultOps);
     void EmitResultSDNodeXFormAsOperand(const TreePatternNode *N,
                                         SmallVectorImpl<unsigned> &ResultOps);
     };
 
 } // end anonymous namespace
 
 MatcherGen::MatcherGen(const PatternToMatch &pattern,
-                       const CodeGenDAGPatterns &cgp)
-: Pattern(pattern), CGP(cgp), NextRecordedOperandNo(0),
+                       const CodeGenDAGPatterns &cgp,
+                       const std::deque<CodeGenSubRegIndex> &sri)
+: Pattern(pattern), CGP(cgp), SRI(sri), NextRecordedOperandNo(0),
   TheMatcher(nullptr), CurPredicate(nullptr) {
   // We need to produce the matcher tree for the patterns source pattern.  To do
   // this we need to match the structure as well as the types.  To do the type
   // matching, we want to figure out the fewest number of type checks we need to
   // emit.  For example, if there is only one integer type supported by a
   // target, there should be no type comparisons at all for integer patterns!
   //
   // To figure out the fewest number of type checks needed, clone the pattern,
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")) {
+      // If we have more than 127 subreg indicies the encoding can overflow
+      // 7 bit and we cannout use StringInteger.
+      if (SRI.size() > 127) {
+        StringRef Name = Def->getName();
+        auto I = std::find_if(SRI.cbegin(), SRI.cend(),
+          [&Name](const CodeGenSubRegIndex &I) {
+            return Name.equals(I.getName());
+          });
+        assert(I != SRI.cend() && "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";
void MatcherGen::EmitResultCode() {
 
   Results.resize(NumSrcResults);
   AddMatcher(new CompleteMatchMatcher(Results, Pattern));
 }
 
 
 /// ConvertPatternToMatcher - Create the matcher for the specified pattern with
 /// the specified variant.  If the variant number is invalid, this returns null.
-Matcher *llvm::ConvertPatternToMatcher(const PatternToMatch &Pattern,
-                                       unsigned Variant,
-                                       const CodeGenDAGPatterns &CGP) {
-  MatcherGen Gen(Pattern, CGP);
+Matcher *
+llvm::ConvertPatternToMatcher(const PatternToMatch &Pattern, unsigned Variant,
+                              const CodeGenDAGPatterns &CGP,
+                              const std::deque<CodeGenSubRegIndex> &SRI) {
+  MatcherGen Gen(Pattern, CGP, SRI);
 
   // Generate the code for the matcher.
   if (Gen.EmitMatcherCode(Variant))
     return nullptr;
 
   // FIXME2: Kill extra MoveParent commands at the end of the matcher sequence.
   // FIXME2: Split result code out to another table, and make the matcher end
   // with an "Emit <index>" command.  This allows result generation stuff to be
   // shared and factored?
 
   // If the match succeeds, then we generate Pattern.
   Gen.EmitResultCode();
 
   // Unconditional match.
   return Gen.GetMatcher();
 }

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";
   }