From 61d4d9a5d33505727afe52f524b90943f8caf21e Mon Sep 17 00:00:00 2001 From: Craig Topper Date: Thu, 18 Feb 2021 08:45:08 -0800 Subject: [PATCH] [TableGen][SelectionDAG] Improve efficiency of encoding negative immediates for isel's CheckInteger opcode. 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. Reviewed By: RKSimon Differential Revision: https://reviews.llvm.org/D96317 --- llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 13 +++++++++++++ llvm/test/TableGen/dag-isel-regclass-emit-enum.td | 2 +- llvm/test/TableGen/dag-isel-subregs.td | 2 +- llvm/utils/TableGen/DAGISelMatcherEmitter.cpp | 19 ++++++++++++++++--- 4 files changed, 31 insertions(+), 5 deletions(-) diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index c58452c..1992007 100644 --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -2578,6 +2578,17 @@ CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex, return VT == MVT::iPTR && cast(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) { @@ -2585,6 +2596,8 @@ CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex, if (Val & 128) Val = GetVBR(Val, MatcherTable, MatcherIndex); + Val = decodeSignRotatedValue(Val); + ConstantSDNode *C = dyn_cast(N); return C && C->getSExtValue() == Val; } diff --git a/llvm/test/TableGen/dag-isel-regclass-emit-enum.td b/llvm/test/TableGen/dag-isel-regclass-emit-enum.td index 462bb3f..1aeeb66 100644 --- a/llvm/test/TableGen/dag-isel-regclass-emit-enum.td +++ b/llvm/test/TableGen/dag-isel-regclass-emit-enum.td @@ -31,7 +31,7 @@ def GPRAbove127 : RegisterClass<"TestTarget", [i32], 32, 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, diff --git a/llvm/test/TableGen/dag-isel-subregs.td b/llvm/test/TableGen/dag-isel-subregs.td index 963e5fc..c1e4032 100644 --- a/llvm/test/TableGen/dag-isel-subregs.td +++ b/llvm/test/TableGen/dag-isel-subregs.td @@ -8,7 +8,7 @@ include "reg-with-subregs-common.td" 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)>; diff --git a/llvm/utils/TableGen/DAGISelMatcherEmitter.cpp b/llvm/utils/TableGen/DAGISelMatcherEmitter.cpp index 62b351e..4a81b45 100644 --- a/llvm/utils/TableGen/DAGISelMatcherEmitter.cpp +++ b/llvm/utils/TableGen/DAGISelMatcherEmitter.cpp @@ -206,6 +206,18 @@ static unsigned EmitVBRValue(uint64_t Val, raw_ostream &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; @@ -579,15 +591,16 @@ EmitMatcher(const Matcher *N, const unsigned Indent, unsigned CurrentIdx, case Matcher::CheckInteger: { OS << "OPC_CheckInteger, "; - unsigned Bytes=1+EmitVBRValue(cast(N)->getValue(), OS); + unsigned Bytes = + 1 + EmitSignedVBRValue(cast(N)->getValue(), OS); OS << '\n'; return Bytes; } case Matcher::CheckChildInteger: { OS << "OPC_CheckChild" << cast(N)->getChildNo() << "Integer, "; - unsigned Bytes=1+EmitVBRValue(cast(N)->getValue(), - OS); + unsigned Bytes = 1 + EmitSignedVBRValue( + cast(N)->getValue(), OS); OS << '\n'; return Bytes; } -- 2.7.4