[TableGen][SelectionDAG] Improve efficiency of encoding negative immediates for isel's CheckInteger opcode.

[craig.topper]

Summary

CheckInteger uses an int64_t encoded using a variable width encoding
that is optimized for encoding a number with a lot of leading zeros.
Negative numbers have no leading zeros so use the largest encoding
requiring 9 bytes.

I believe its most like we want to check for positive and negative
numbers near 0. -1 is quite common due to its use in the 'not'
idiom.

To optimize for this, we can borrow an idea from the bitcode format
and move the sign bit to bit 0 with the magnitude stored in the
upper bits. This will drastically increase the number of leading
zeros for small magnitudes. Then we can run this value through
VBR encoding.

This gives a small reduction in the table size on all in tree
targets except VE where size increased by about 300 bytes due
to intrinsic ids now requiring 3 bytes instead of 2. Since the
intrinsic enum space is shared by all targets this an unfortunate
consquence of where VE is currently located in the range.

[RKSimon]

This gives a small reduction in the table size on all in tree targets except VE where size increased by about 300 bytes due to intrinsic ids now requiring 3 bytes instead of 2. Since the intrinsic enum space is shared by all targets this an unfortunate consquence of where VE is currently located in the range.

I'm not very familiar with this - what options do we have for altering the range to help avoid the VE bloat?

[craig.topper]

In D96317#2550753, @RKSimon wrote:

This gives a small reduction in the table size on all in tree targets except VE where size increased by about 300 bytes due to intrinsic ids now requiring 3 bytes instead of 2. Since the intrinsic enum space is shared by all targets this an unfortunate consquence of where VE is currently located in the range.

I'm not very familiar with this - what options do we have for altering the range to help avoid the VE bloat?

Pretty sure the intrinsic IDs are just alphabetized and they are all prefixed by the target name. So I think it's just a function of how many target names come before "VE" and how many intrinsics those targets have.

[RKSimon]

I've no objection to this but I don't know enough to approve - @Paul-C-Anagnostopoulos ?

[Paul-C-Anagnostopoulos]

I'm only slightly more familiar with it, but it looks fine to me.

I take it that C++ doesn't have a standard rotate function?

[craig.topper]

In D96317#2568513, @Paul-C-Anagnostopoulos wrote:

I'm only slightly more familiar with it, but it looks fine to me.

I take it that C++ doesn't have a standard rotate function?

I don't think there's a standardized rotate. clang has __builtin_rotateright64. MSVC has its own rotate intrinsics. gcc has some intrinsics in ia32intrin.h. None of them are portable.

[RKSimon]

OK, there seems to be no objections. LGTM.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
   MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
   if (cast<VTSDNode>(N)->getVT() == VT)
     return true;
 
   // Handle the case when VT is iPTR.
   return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI->getPointerTy(DL);
 }
 
+// Bit 0 stores the sign of the immediate. The upper bits contain the magnitude
+// shifted left by 1.
+static uint64_t decodeSignRotatedValue(uint64_t V) {
+  if ((V & 1) == 0)
+    return V >> 1;
+  if (V != 1)
+    return -(V >> 1);
+  // There is no such thing as -0 with integers.  "-0" really means MININT.
+  return 1ULL << 63;
+}
+
 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
 CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
              SDValue N) {
   int64_t Val = MatcherTable[MatcherIndex++];
   if (Val & 128)
     Val = GetVBR(Val, MatcherTable, MatcherIndex);
 
+  Val = decodeSignRotatedValue(Val);
+
   ConstantSDNode *C = dyn_cast<ConstantSDNode>(N);
   return C && C->getSExtValue() == Val;
 }
 
 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
 CheckChildInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
                   SDValue N, unsigned ChildNo) {
   if (ChildNo >= N.getNumOperands())

llvm/test/TableGen/dag-isel-regclass-emit-enum.td

 // CHECK-NEXT: OPC_Scope, 14, /*->20*/ // 2 children in Scope
 // CHECK-NEXT: OPC_CheckChild1Integer, 0,
 // CHECK-NEXT: OPC_EmitInteger, MVT::i32, 0|128,1/*128*/,
 // CHECK-NEXT: OPC_MorphNodeTo1, TARGET_VAL(TargetOpcode::COPY_TO_REGCLASS), 0,
 // CHECK-NEXT:     MVT::i32, 2/*#Ops*/, 1, 0,
 def : Pat<(i32 (add i32:$src, (i32 0))),
           (COPY_TO_REGCLASS GPRAbove127, GPR0:$src)>;
 
-// CHECK:      OPC_CheckChild1Integer, 1,
+// CHECK:      OPC_CheckChild1Integer, 2,
 // CHECK-NEXT: OPC_EmitInteger, MVT::i32, TestNamespace::GPR127RegClassID,
 // CHECK-NEXT: OPC_MorphNodeTo1, TARGET_VAL(TargetOpcode::COPY_TO_REGCLASS), 0,
 // CHECK-NEXT:     MVT::i32, 2/*#Ops*/, 1, 0,
 def : Pat<(i32 (add i32:$src, (i32 1))),
           (COPY_TO_REGCLASS GPR127, GPR0:$src)>;

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_CheckChild1Integer, 30,
 // 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/DAGISelMatcherEmitter.cpp

static unsigned EmitVBRValue(uint64_t Val, raw_ostream &OS) {
   }
   OS << Val;
   if (!OmitComments)
     OS << "/*" << InVal << "*/";
   OS << ", ";
   return NumBytes+1;
 }
 
+/// Emit the specified signed value as a VBR. To improve compression we encode
+/// positive numbers shifted left by 1 and negative numbers negated and shifted
+/// left by 1 with bit 0 set.
+static unsigned EmitSignedVBRValue(uint64_t Val, raw_ostream &OS) {
+  if ((int64_t)Val >= 0)
+    Val = Val << 1;
+  else
+    Val = (-Val << 1) | 1;
+
+  return EmitVBRValue(Val, OS);
+}
+
 // This is expensive and slow.
 static std::string getIncludePath(const Record *R) {
   std::string str;
   raw_string_ostream Stream(str);
   auto Locs = R->getLoc();
   SMLoc L;
   if (Locs.size() > 1) {
     // Get where the pattern prototype was instantiated
case Matcher::CheckType:
   case Matcher::CheckChildType:
     OS << "OPC_CheckChild"
        << cast<CheckChildTypeMatcher>(N)->getChildNo() << "Type, "
        << getEnumName(cast<CheckChildTypeMatcher>(N)->getType()) << ",\n";
     return 2;
 
   case Matcher::CheckInteger: {
     OS << "OPC_CheckInteger, ";
-    unsigned Bytes=1+EmitVBRValue(cast<CheckIntegerMatcher>(N)->getValue(), OS);
+    unsigned Bytes =
+        1 + EmitSignedVBRValue(cast<CheckIntegerMatcher>(N)->getValue(), OS);
     OS << '\n';
     return Bytes;
   }
   case Matcher::CheckChildInteger: {
     OS << "OPC_CheckChild" << cast<CheckChildIntegerMatcher>(N)->getChildNo()
        << "Integer, ";
-    unsigned Bytes=1+EmitVBRValue(cast<CheckChildIntegerMatcher>(N)->getValue(),
-                                  OS);
+    unsigned Bytes = 1 + EmitSignedVBRValue(
+                             cast<CheckChildIntegerMatcher>(N)->getValue(), OS);
     OS << '\n';
     return Bytes;
   }
   case Matcher::CheckCondCode:
     OS << "OPC_CheckCondCode, ISD::"
        << cast<CheckCondCodeMatcher>(N)->getCondCodeName() << ",\n";
     return 2;