Fix compile-time regression caused by rL371928

[dsanders]

Summary

Also fixup rL371928 for cases that occur on our out-of-tree backend

There were still quite a few intermediate APInts and this caused the
compile time of MCCodeEmitter for our target to jump from 16s up to
~5m40s. This patch, brings it back down to ~17s by eliminating pretty
much all of them using two new APInt functions (extractBitsAsZExtValue(),
insertBits() but with a uint64_t). The exact conditions for eliminating
them is that the field extracted/inserted must be <=64-bit which is
almost always true.

Note: The two new APInt API's assume that APInt::WordSize is at least
64-bit because that means they touch at most 2 APInt words. They
statically assert that's true. It seems very unlikely that someone
is patching it to be smaller so this should be fine.

[jmolloy]

Thankyou Daniel! Looks great!

One question though, how did your out-of-tree backend trigger this case? It only gets enabled with BitWidth > 64 which was totally not supported before, so surely you would have had a broken encoder?

Cheers,

James

[dsanders]

In D67686#1673591, @jmolloy wrote:

Thankyou Daniel! Looks great!

One question though, how did your out-of-tree backend trigger this case? It only gets enabled with BitWidth > 64 which was totally not supported before, so surely you would have had a broken encoder?

Cheers,

James

Thanks.

Historically, we let tablegen give us the first 64-bits and then tacked on extra bytes via handwritten C++ (which is as error prone as you'd expect). A while back we made Inst field reflect the whole instruction and added >64-bit support to the disassembler but we didn't have time to do the encoder at the same time. We therefore added a quick hack to have the CodeEmitterGen discard the definition for bit 64 and up and filed a bug report to come back to it. The end result was that when your patch landed we got the APInt version because BitWidth was >64 in the early test but it still only generated the first 64-bits because of our hack. The next step for us now that we've updated our MCCodeEmitter to the APInt versions is to remove our hack and let tblgen handle it all :-)

[jmolloy]

Ah great, thanks for the context, and I'm glad this patch helps you out!

llvm/include/llvm/ADT/APInt.h

#endif
   /// Negate this APInt in place.
   void negate() {
     flipAllBits();
     ++(*this);
   }
 
   /// Insert the bits from a smaller APInt starting at bitPosition.
   void insertBits(const APInt &SubBits, unsigned bitPosition);
+  void insertBits(uint64_t SubBits, unsigned bitPosition, unsigned numBits);
 
   /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).
   APInt extractBits(unsigned numBits, unsigned bitPosition) const;
+  uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const;
 
   /// @}
   /// \name Value Characterization Functions
   /// @{
 
   /// Return the number of bits in the APInt.
   unsigned getBitWidth() const { return BitWidth; }
 

llvm/lib/Support/APInt.cpp

void APInt::insertBits(const APInt &subBits, unsigned bitPosition) {
   for (unsigned i = 0; i != subBitWidth; ++i) {
     if (subBits[i])
       setBit(bitPosition + i);
     else
       clearBit(bitPosition + i);
   }
 }
 
+void APInt::insertBits(uint64_t subBits, unsigned bitPosition, unsigned numBits) {
+  uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);
+  subBits &= maskBits;
+  if (isSingleWord()) {
+    U.VAL &= ~(maskBits << bitPosition);
+    U.VAL |= subBits << bitPosition;
+    return;
+  }
+
+  unsigned loBit = whichBit(bitPosition);
+  unsigned loWord = whichWord(bitPosition);
+  unsigned hiWord = whichWord(bitPosition + numBits - 1);
+  if (loWord == hiWord) {
+    U.pVal[loWord] &= ~(maskBits << loBit);
+    U.pVal[loWord] |= subBits << loBit;
+    return;
+  }
+
+  static_assert(8 * sizeof(WordType) <= 64, "This code assumes only two words affected");
+  unsigned wordBits = 8 * sizeof(WordType);
+  U.pVal[loWord] &= ~(maskBits << loBit);
+  U.pVal[loWord] |= subBits << loBit;
+
+  U.pVal[hiWord] &= ~(maskBits >> (wordBits - loBit));
+  U.pVal[hiWord] |= subBits >> (wordBits - loBit);
+}
+
 APInt APInt::extractBits(unsigned numBits, unsigned bitPosition) const {
   assert(numBits > 0 && "Can't extract zero bits");
   assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
          "Illegal bit extraction");
 
   if (isSingleWord())
     return APInt(numBits, U.VAL >> bitPosition);
 
for (unsigned word = 0; word < NumDstWords; ++word) {
     uint64_t w1 =
         (loWord + word + 1) < NumSrcWords ? U.pVal[loWord + word + 1] : 0;
     DestPtr[word] = (w0 >> loBit) | (w1 << (APINT_BITS_PER_WORD - loBit));
   }
 
   return Result.clearUnusedBits();
 }
 
+uint64_t APInt::extractBitsAsZExtValue(unsigned numBits,
+                                       unsigned bitPosition) const {
+  assert(numBits > 0 && "Can't extract zero bits");
+  assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
+         "Illegal bit extraction");
+  assert(numBits <= 64 && "Illegal bit extraction");
+
+  uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);
+  if (isSingleWord())
+    return (U.VAL >> bitPosition) & maskBits;
+
+  unsigned loBit = whichBit(bitPosition);
+  unsigned loWord = whichWord(bitPosition);
+  unsigned hiWord = whichWord(bitPosition + numBits - 1);
+  if (loWord == hiWord)
+    return (U.pVal[loWord] >> loBit) & maskBits;
+
+  static_assert(8 * sizeof(WordType) <= 64, "This code assumes only two words affected");
+  unsigned wordBits = 8 * sizeof(WordType);
+  uint64_t retBits = U.pVal[loWord] >> loBit;
+  retBits |= U.pVal[hiWord] << (wordBits - loBit);
+  retBits &= maskBits;
+  return retBits;
+}
+
 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
   assert(!str.empty() && "Invalid string length");
   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
           radix == 36) &&
          "Radix should be 2, 8, 10, 16, or 36!");
 
   size_t slen = str.size();
 

llvm/test/TableGen/BigEncoder.td

def biz : Instruction {
     bits<32> factor;
     let Inst{7-0} = 0xCC;
     let Inst{11-8,15-12} = factor{10-3}; // offset by 3, multipart
     let AsmString = "biz  $factor";
     field bits<16> SoftFail = 0;
     }
 
 }
-
 // CHECK-LABEL: case ::biz: {
-// CHECK: const APInt [[x:M[0-9]+]] = APInt::getBitsSet(65, 3, 7);
-// CHECK-NEXT: Value |= (op & [[x]]) << 9;
-// CHECK-NEXT: const APInt [[y:M[0-9]+]] = APInt::getBitsSet(65, 7, 11);
-// CHECK-NEXT: Value |= (op & [[y]]) << 1;
+// CHECK:      Value.insertBits(op.extractBitsAsZExtValue(4, 3), 12, 4);
+// CHECK-NEXT: Value.insertBits(op.extractBitsAsZExtValue(4, 7), 8, 4);
 
 // CHECK-LABEL: case ::foo: {
-// CHECK: const APInt [[x:M[0-9]+]] = APInt::getBitsSet(65, 0, 7);
-// CHECK-NEXT: op &= [[x]];
-// CHECK-NEXT: op <<= 8;
-// CHECK-NEXT: Value |= op;
+// CHECK:      Value.insertBits(op.extractBitsAsZExtValue(7, 0), 8, 7);
 
 // CHECK-LABEL: case ::bar: {
-// CHECK: const APInt [[x:M[0-9]+]] = APInt::getBitsSet(65, 3, 11);
-// CHECK-NEXT: op &= [[x]];
-// CHECK-NEXT: op <<= 5;
-// CHECK-NEXT: Value |= op;
+// CHECK:      Value.insertBits(op.extractBitsAsZExtValue(8, 3), 8, 8);

llvm/unittests/ADT/APIntTest.cpp

TEST(APIntTest, insertBits) {
   i260.insertBits(APInt(129, 1ull << 48), 15);
   EXPECT_EQ(i260.extractBits(64, 0).getZExtValue(), 0x8000000000007FFFull);
   EXPECT_EQ(i260.extractBits(64, 64).getZExtValue(), 0x0000000000000000ull);
   EXPECT_EQ(i260.extractBits(64, 128).getZExtValue(), 0xFFFFFFFFFFFF0000ull);
   EXPECT_EQ(i260.extractBits(64, 192).getZExtValue(), 0xFFFFFFFFFFFFFFFFull);
   EXPECT_EQ(i260.extractBits(4, 256).getZExtValue(), 0x000000000000000Full);
 }
 
+TEST(APIntTest, insertBitsUInt64) {
+  // Tests cloned from insertBits but adapted to the numBits <= 64 constraint
+  uint64_t iSrc = 0x00123456;
+
+  // Direct copy.
+  APInt i31(31, 0x76543210ull);
+  i31.insertBits(iSrc, 0, 31);
+  EXPECT_EQ(static_cast<int64_t>(0x00123456ull), i31.getSExtValue());
+
+  // Single word src/dst insertion.
+  APInt i63(63, 0x01234567FFFFFFFFull);
+  i63.insertBits(iSrc, 4, 31);
+  EXPECT_EQ(static_cast<int64_t>(0x012345600123456Full), i63.getSExtValue());
+
+  // Insert single word src into one word of dst.
+  APInt i120(120, UINT64_MAX, true);
+  i120.insertBits(iSrc, 8, 31);
+  EXPECT_EQ(static_cast<int64_t>(0xFFFFFF80123456FFull), i120.getSExtValue());
+
+  // Insert single word src into two words of dst.
+  APInt i127(127, UINT64_MAX, true);
+  i127.insertBits(iSrc, 48, 31);
+  EXPECT_EQ(i127.extractBits(64, 0).getZExtValue(), 0x3456FFFFFFFFFFFFull);
+  EXPECT_EQ(i127.extractBits(63, 64).getZExtValue(), 0x7FFFFFFFFFFF8012ull);
+
+  // Insert on word boundaries.
+  APInt i128(128, 0);
+  i128.insertBits(UINT64_MAX, 0, 64);
+  i128.insertBits(UINT64_MAX, 64, 64);
+  EXPECT_EQ(-1, i128.getSExtValue());
+
+  APInt i256(256, UINT64_MAX, true);
+  i256.insertBits(0, 0, 64);
+  i256.insertBits(0, 64, 1);
+  i256.insertBits(0, 64, 64);
+  i256.insertBits(0, 128, 5);
+  i256.insertBits(0, 128, 64);
+  i256.insertBits(0, 192, 64);
+  EXPECT_EQ(0u, i256.getSExtValue());
+
+  APInt i257(257, 0);
+  i257.insertBits(APInt(96, UINT64_MAX, true), 64);
+  EXPECT_EQ(i257.extractBitsAsZExtValue(64, 0), 0x0000000000000000ull);
+  EXPECT_EQ(i257.extractBitsAsZExtValue(64, 64), 0xFFFFFFFFFFFFFFFFull);
+  EXPECT_EQ(i257.extractBitsAsZExtValue(64, 128), 0x00000000FFFFFFFFull);
+  EXPECT_EQ(i257.extractBitsAsZExtValue(64, 192), 0x0000000000000000ull);
+  EXPECT_EQ(i257.extractBitsAsZExtValue(1, 256), 0x0000000000000000ull);
+
+  // General insertion.
+  APInt i260(260, UINT64_MAX, true);
+  i260.insertBits(APInt(129, 1ull << 48), 15);
+  EXPECT_EQ(i260.extractBitsAsZExtValue(64, 0), 0x8000000000007FFFull);
+  EXPECT_EQ(i260.extractBitsAsZExtValue(64, 64), 0x0000000000000000ull);
+  EXPECT_EQ(i260.extractBitsAsZExtValue(64, 128), 0xFFFFFFFFFFFF0000ull);
+  EXPECT_EQ(i260.extractBitsAsZExtValue(64, 192), 0xFFFFFFFFFFFFFFFFull);
+  EXPECT_EQ(i260.extractBitsAsZExtValue(4, 256), 0x000000000000000Full);
+}
+
 TEST(APIntTest, extractBits) {
   APInt i32(32, 0x1234567);
   EXPECT_EQ(0x3456, i32.extractBits(16, 4));
 
   APInt i257(257, 0xFFFFFFFFFF0000FFull, true);
   EXPECT_EQ(0xFFu, i257.extractBits(16, 0));
   EXPECT_EQ((0xFFu >> 1), i257.extractBits(16, 1));
   EXPECT_EQ(-1, i257.extractBits(32, 64).getSExtValue());
   EXPECT_EQ(-1, i257.extractBits(128, 128).getSExtValue());
   EXPECT_EQ(-1, i257.extractBits(66, 191).getSExtValue());
   EXPECT_EQ(static_cast<int64_t>(0xFFFFFFFFFF80007Full),
             i257.extractBits(128, 1).getSExtValue());
   EXPECT_EQ(static_cast<int64_t>(0xFFFFFFFFFF80007Full),
             i257.extractBits(129, 1).getSExtValue());
 
   EXPECT_EQ(APInt(48, 0),
             APInt(144, "281474976710655", 10).extractBits(48, 48));
   EXPECT_EQ(APInt(48, 0x0000ffffffffffffull),
             APInt(144, "281474976710655", 10).extractBits(48, 0));
   EXPECT_EQ(APInt(48, 0x00007fffffffffffull),
             APInt(144, "281474976710655", 10).extractBits(48, 1));
 }
 
+TEST(APIntTest, extractBitsAsZExtValue) {
+  // Tests based on extractBits
+  APInt i32(32, 0x1234567);
+  EXPECT_EQ(0x3456u, i32.extractBitsAsZExtValue(16, 4));
+
+  APInt i257(257, 0xFFFFFFFFFF0000FFull, true);
+  EXPECT_EQ(0xFFu, i257.extractBitsAsZExtValue(16, 0));
+  EXPECT_EQ((0xFFu >> 1), i257.extractBitsAsZExtValue(16, 1));
+  EXPECT_EQ(0xFFFFFFFFull, i257.extractBitsAsZExtValue(32, 64));
+  EXPECT_EQ(0xFFFFFFFFFFFFFFFFull, i257.extractBitsAsZExtValue(64, 128));
+  EXPECT_EQ(0xFFFFFFFFFFFFFFFFull, i257.extractBitsAsZExtValue(64, 192));
+  EXPECT_EQ(0xFFFFFFFFFFFFFFFFull, i257.extractBitsAsZExtValue(64, 191));
+  EXPECT_EQ(0x3u, i257.extractBitsAsZExtValue(2, 255));
+  EXPECT_EQ(0xFFFFFFFFFF80007Full, i257.extractBitsAsZExtValue(64, 1));
+  EXPECT_EQ(0xFFFFFFFFFFFFFFFFull, i257.extractBitsAsZExtValue(64, 65));
+  EXPECT_EQ(0xFFFFFFFFFF80007Full, i257.extractBitsAsZExtValue(64, 1));
+  EXPECT_EQ(0xFFFFFFFFFFFFFFFFull, i257.extractBitsAsZExtValue(64, 65));
+  EXPECT_EQ(0x1ull, i257.extractBitsAsZExtValue(1, 129));
+
+  EXPECT_EQ(APInt(48, 0),
+            APInt(144, "281474976710655", 10).extractBitsAsZExtValue(48, 48));
+  EXPECT_EQ(APInt(48, 0x0000ffffffffffffull),
+            APInt(144, "281474976710655", 10).extractBitsAsZExtValue(48, 0));
+  EXPECT_EQ(APInt(48, 0x00007fffffffffffull),
+            APInt(144, "281474976710655", 10).extractBitsAsZExtValue(48, 1));
+}
+
 TEST(APIntTest, getLowBitsSet) {
   APInt i128lo64 = APInt::getLowBitsSet(128, 64);
   EXPECT_EQ(0u, i128lo64.countLeadingOnes());
   EXPECT_EQ(64u, i128lo64.countLeadingZeros());
   EXPECT_EQ(64u, i128lo64.getActiveBits());
   EXPECT_EQ(0u, i128lo64.countTrailingZeros());
   EXPECT_EQ(64u, i128lo64.countTrailingOnes());
   EXPECT_EQ(64u, i128lo64.countPopulation());

llvm/utils/TableGen/CodeEmitterGen.cpp

for (--bit; bit >= 0;) {
       if (varBit == -1 || varBit != (beginVarBit - N)) break;
       ++N;
       --bit;
     }
 
     std::string maskStr;
     int opShift;
 
-    if (UseAPInt) {
-      unsigned loBit = beginVarBit - N + 1;
-      unsigned hiBit = loBit + N;
-      maskStr = "M" + itostr(bit);
-      Case += "      const APInt " + maskStr + " = APInt::getBitsSet(" +
-              itostr(BitWidth) + ", " + itostr(loBit) + ", " + itostr(hiBit) +
-              ");\n";
+    unsigned loInstBit = beginInstBit - N + 1;
+    if (UseAPInt) {
+      std::string extractStr;
+      if (N >= 64) {
+        extractStr = "op.extractBits(" + itostr(hiBit - loBit) + ", " +
+                     itostr(loBit) + ")";
+        Case += "      Value.insertBits(" + extractStr + ", " +
+                itostr(loInstBit) + ");\n";
+      } else {
+        extractStr = "op.extractBitsAsZExtValue(" + itostr(hiBit - loBit) +
+                     ", " + itostr(loBit) + ")";
+        Case += "      Value.insertBits(" + extractStr + ", " +
+                itostr(loInstBit) + ", " + itostr(hiBit - loBit) + ");\n";
+      }
     } else {
       uint64_t opMask = ~(uint64_t)0 >> (64 - N);
       opShift = beginVarBit - N + 1;
       opMask <<= opShift;
       maskStr = "UINT64_C(" + utostr(opMask) + ")";
-    }
       opShift = beginInstBit - beginVarBit;
 
       if (numOperandLits == 1) {
-      // Because Op may be an APInt, ensure all arithmetic is done in-place
-      // where possible to elide copies.
         Case += "      op &= " + maskStr + ";\n";
         if (opShift > 0) {
           Case += "      op <<= " + itostr(opShift) + ";\n";
         } else if (opShift < 0) {
           Case += "      op >>= " + itostr(-opShift) + ";\n";
         }
         Case += "      Value |= op;\n";
       } else {
         if (opShift > 0) {
-        Case += "      Value |= (op & " + maskStr + ") << " + itostr(opShift) +
-                ";\n";
+          Case += "      Value |= (op & " + maskStr + ") << " +
+                  itostr(opShift) + ";\n";
         } else if (opShift < 0) {
-        Case += "      Value |= (op & " + maskStr + ") >> " + itostr(-opShift) +
-                ";\n";
+          Case += "      Value |= (op & " + maskStr + ") >> " +
+                  itostr(-opShift) + ";\n";
         } else {
           Case += "      Value |= (op & " + maskStr + ");\n";
         }
       }
     }
   }
+}
 
 std::string CodeEmitterGen::getInstructionCase(Record *R,
                                                CodeGenTarget &Target) {
   std::string Case;
   BitsInit *BI = R->getValueAsBitsInit("Inst");
   unsigned NumberedOp = 0;
   std::set<unsigned> NamedOpIndices;
 
void CodeEmitterGen::run(raw_ostream &o) {
   }
 
   // Default case: unhandled opcode
   o << "  default:\n"
     << "    std::string msg;\n"
     << "    raw_string_ostream Msg(msg);\n"
     << "    Msg << \"Not supported instr: \" << MI;\n"
     << "    report_fatal_error(Msg.str());\n"
-    << "  }\n"
-    << "  return Value;\n"
-    << "}\n\n";
+    << "  }\n";
+  if (UseAPInt)
+    o << "  Inst = Value;\n";
+  else
+    o << "  return Value;\n";
+  o << "}\n\n";
 
   const auto &All = SubtargetFeatureInfo::getAll(Records);
   std::map<Record *, SubtargetFeatureInfo, LessRecordByID> SubtargetFeatures;
   SubtargetFeatures.insert(All.begin(), All.end());
 
   o << "#ifdef ENABLE_INSTR_PREDICATE_VERIFIER\n"
     << "#undef ENABLE_INSTR_PREDICATE_VERIFIER\n"
     << "#include <sstream>\n\n";