[WIP][TableGen] Add support for variable length instruction in DecoderGen.

[0x59616e]

Summary

This adds support for variable length encoding infrastructure in DecoderGen.

It thinks of the variable length instructions as fixed length by pretending they all have the same maximum length.

For example, given three instructions with length 2, 4 and 8 bytes, it just pretends them all have 8 bytes length.

In that way, we can use the algorithm for fixed length instructions to generate automaton for variable length instructions.

Also, since we can't know the instruction length before decoding, it adds an instruction length table and a callback function to let the disassembler to adjust the encoding of the instruction.

You can see example usage in D120606

[0x59616e]

addressed a bug when handling slice

[0x59616e]

update diff. I forgot the context

llvm/utils/TableGen/FixedLenDecoderEmitter.cpp

 #include "CodeGenInstruction.h"
 #include "CodeGenTarget.h"
 #include "InfoByHwMode.h"
+#include "VarLenCodeEmitterGen.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/CachedHashString.h"

   void emitTable(formatted_raw_ostream &o, DecoderTable &Table,
                  unsigned Indentation, unsigned BitWidth,
                  StringRef Namespace) const;
+  void emitInstrLenTable(formatted_raw_ostream &OS,
+                         std::vector<unsigned> &InstrLen) const;
   void emitPredicateFunction(formatted_raw_ostream &OS,
                              PredicateSet &Predicates,
                              unsigned Indentation) const;

 }
 
 static BitsInit &getBitsField(const Record &def, StringRef str) {
-  BitsInit *bits = def.getValueAsBitsInit(str);
-  return *bits;
+  const RecordVal *RV = def.getValue(str);
+  if (BitsInit *bits = dyn_cast<BitsInit>(RV->getValue()))
+    return *bits;
+
+  // variable length instruction
+  DagInit *dag = cast<DagInit>(RV->getValue());
+  VarLenInst VLI = VarLenInst(dag, RV);
+  SmallVector<Init *, 16> Bits;
+  auto SI = VLI.begin(), SE = VLI.end();
+
+  std::map<std::string, std::vector<std::pair<std::pair<int, int>, int>>>
+      SlicesMap;
+
+  while (SI != SE) {
+    if (const BitsInit *BI = dyn_cast<BitsInit>(SI->Value)) {
+      for (unsigned Idx = 0U; Idx < BI->getNumBits(); ++Idx) {
+        Bits.push_back(BI->getBit(Idx));
+      }
+    } else if (const BitInit *BI = dyn_cast<BitInit>(SI->Value)) {
+      Bits.push_back(const_cast<BitInit *>(BI));
+    } else if (const StringInit *OpName = dyn_cast<StringInit>(SI->Value)) {
+      // (operand "$<opname>", <num of bits>)
+      StringRef Str = OpName->getValue();
+      VarInit *VI = VarInit::get(Str.substr(1), BitsRecTy::get(SI->BitWidth));
+      for (unsigned Idx = 0U; Idx < SI->BitWidth; ++Idx) {
+        VarBitInit *VBI = VarBitInit::get(VI, Idx);
+        Bits.push_back(VBI);
+      }
+    } else if (const DagInit *DI = dyn_cast<DagInit>(SI->Value)) {
+      // (slice "$<opname>", LoBit, HiBit)
+      // We don't know how long this operand will be until
+      // we gather all of the slices.
+      StringRef Str = cast<StringInit>(DI->getArg(0))->getValue();
+      int64_t Hi = cast<IntInit>(DI->getArg(1))->getValue();
+      int64_t Lo = cast<IntInit>(DI->getArg(2))->getValue();
+      SlicesMap[Str.str()].push_back({{Lo, Bits.size()}, Hi - Lo + 1});
+
+      for (int64_t Idx = Lo; Idx <= Hi; ++Idx) {
+        // reserve a space;
+        Bits.push_back(UnsetInit::get());
+      }
+    } else {
+      llvm_unreachable("What kind of init it is ?");
+    }
+    ++SI;
+  }
+
+  for (auto &Slices : SlicesMap) {
+    int Len = 0;
+
+    for (auto &S : Slices.second)
+      Len += S.second;
+
+    VarInit *VI = VarInit::get(StringInit::get(Slices.first.substr(1)),
+                               BitsRecTy::get(Len));
+    for (auto &S : Slices.second) {
+      int BitsIdx = S.first.second;
+      int VarIdx = S.first.first;
+      int VarIdxEnd = VarIdx + S.second;
+      for (; VarIdx < VarIdxEnd; ++BitsIdx, ++VarIdx)
+        Bits[BitsIdx] = VarBitInit::get(VI, VarIdx);
+    }
+  }
+  return *BitsInit::get(Bits);
 }
 
 // Representation of the instruction to work on.

   // Populates the insn given the uid.
   void insnWithID(insn_t &Insn, unsigned Opcode) const {
     BitsInit &Bits = getBitsField(*AllInstructions[Opcode].EncodingDef, "Inst");
-
+    Insn.resize(BitWidth > Bits.getNumBits() ? BitWidth : Bits.getNumBits(),
+                BIT_UNSET);
     // We may have a SoftFail bitmask, which specifies a mask where an encoding
     // may differ from the value in "Inst" and yet still be valid, but the
     // disassembler should return SoftFail instead of Success.
     //
     // This is used for marking UNPREDICTABLE instructions in the ARM world.
-    BitsInit *SFBits =
-        AllInstructions[Opcode].EncodingDef->getValueAsBitsInit("SoftFail");
-
-    for (unsigned i = 0; i < BitWidth; ++i) {
+    const RecordVal *RV =
+        AllInstructions[Opcode].EncodingDef->getValue("SoftFail");
+    const BitsInit *SFBits = RV ? dyn_cast<BitsInit>(RV->getValue()) : nullptr;
+    for (unsigned i = 0; i < Bits.getNumBits(); ++i) {
       if (SFBits && bitFromBits(*SFBits, i) == BIT_TRUE)
-        Insn.push_back(BIT_UNSET);
+        Insn[i] = BIT_UNSET;
       else
-        Insn.push_back(bitFromBits(Bits, i));
+        Insn[i] = bitFromBits(Bits, i);
     }
   }
 

   OS.indent(Indentation) << "};\n\n";
 }
 
+void FixedLenDecoderEmitter::emitInstrLenTable(
+    formatted_raw_ostream &OS, std::vector<unsigned> &InstrLen) const {
+  OS << "static const uint8_t InstrLenTable[] = {\n";
+  for (unsigned &Len : InstrLen) {
+    OS << Len << ",\n";
+  }
+  OS << "};\n\n";
+}
+
 void FixedLenDecoderEmitter::
 emitPredicateFunction(formatted_raw_ostream &OS, PredicateSet &Predicates,
                       unsigned Indentation) const {

 
 void FilterChooser::emitSoftFailTableEntry(DecoderTableInfo &TableInfo,
                                            unsigned Opc) const {
-  BitsInit *SFBits =
-      AllInstructions[Opc].EncodingDef->getValueAsBitsInit("SoftFail");
+  const RecordVal *RV = AllInstructions[Opc].EncodingDef->getValue("SoftFail");
+  BitsInit *SFBits = RV ? dyn_cast<BitsInit>(RV->getValue()) : nullptr;
+
   if (!SFBits) return;
   BitsInit *InstBits =
       AllInstructions[Opc].EncodingDef->getValueAsBitsInit("Inst");

   return Decoder;
 }
 
-static bool
+static unsigned
 populateInstruction(CodeGenTarget &Target, const Record &EncodingDef,
                     const CodeGenInstruction &CGI, unsigned Opc,
                     std::map<unsigned, std::vector<OperandInfo>> &Operands) {

   // of the instruction must be fully specified.
 
   BitsInit &Bits = getBitsField(EncodingDef, "Inst");
-  if (Bits.allInComplete()) return false;
+  if (Bits.allInComplete())
+    return 0;
 
   std::vector<OperandInfo> InsnOperands;
 

     InsnOperands.push_back(
         OperandInfo(std::string(InstDecoder), HasCompleteInstDecoder));
     Operands[Opc] = InsnOperands;
-    return true;
+    return Bits.getNumBits();
   }
 
   // Generate a description of the operand of the instruction that we know

     });
 #endif
 
-  return true;
+  return Bits.getNumBits();
 }
 
 // emitFieldFromInstruction - Emit the templated helper function

 
 // emitDecodeInstruction - Emit the templated helper function
 // decodeInstruction().
-static void emitDecodeInstruction(formatted_raw_ostream &OS) {
+static void emitDecodeInstruction(formatted_raw_ostream &OS,
+                                  bool isVarLenInst) {
   OS << "template <typename InsnType>\n"
      << "static DecodeStatus decodeInstruction(const uint8_t DecodeTable[], "
         "MCInst &MI,\n"
      << "                                      InsnType insn, uint64_t "
         "Address,\n"
      << "                                      const void *DisAsm,\n"
-     << "                                      const MCSubtargetInfo &STI) {\n"
+     << "                                      const MCSubtargetInfo &STI";
+  if (isVarLenInst) {
+    OS << ",\n"
+       << "                                      std::function<void(APInt &,"
+       << " uint64_t)> makeUp";
+  }
+  OS << ") {\n"
      << "  const FeatureBitset &Bits = STI.getFeatureBits();\n"
      << "\n"
      << "  const uint8_t *Ptr = DecodeTable;\n"

      << "\n"
      << "      MI.clear();\n"
      << "      MI.setOpcode(Opc);\n"
-     << "      bool DecodeComplete;\n"
-     << "      S = decodeToMCInst(S, DecodeIdx, insn, MI, Address, DisAsm, "
-        "DecodeComplete);\n"
-     << "      assert(DecodeComplete);\n"
+     << "      bool DecodeComplete;\n";
+  if (isVarLenInst) {
+    OS << "      Len = InstrLenTable[Opc];\n"
+       << "      APInt tmp(Len, insn);\n"
+       << "      makeUp(tmp, Len);\n"
+       << "      S = decodeToMCInst(S, DecodeIdx, tmp, MI, Address, DisAsm, "
+       << "DecodeComplete);\n";
+  } else {
+    OS << "      S = decodeToMCInst(S, DecodeIdx, insn, MI, Address, DisAsm, "
+          "DecodeComplete);\n";
+  }
+  OS << "      assert(DecodeComplete);\n"
      << "\n"
      << "      LLVM_DEBUG(dbgs() << Loc << \": OPC_Decode: opcode \" << Opc\n"
      << "                   << \", using decoder \" << DecodeIdx << \": \"\n"

   std::map<std::pair<std::string, unsigned>, std::vector<EncodingIDAndOpcode>>
       OpcMap;
   std::map<unsigned, std::vector<OperandInfo>> Operands;
+  std::vector<unsigned> InstrLen;
+
+  bool isVarLenInst = false;
+  unsigned maxInstLen = 0;
 
   for (unsigned i = 0; i < NumberedEncodings.size(); ++i) {
     const Record *EncodingDef = NumberedEncodings[i].EncodingDef;

       NumInstructions++;
     NumEncodings++;
 
-    if (!Size)
+    isVarLenInst = (EncodingDef->getValue("isVarLenInst") != nullptr);
+    if (!Size && !isVarLenInst)
       continue;
 
-    if (populateInstruction(Target, *EncodingDef, *Inst, i, Operands)) {
+    if (isVarLenInst)
+      InstrLen.resize(NumberedInstructions.size(), 0);
+
+    if (unsigned Len =
+            populateInstruction(Target, *EncodingDef, *Inst, i, Operands)) {
+      if (isVarLenInst) {
+        maxInstLen = std::max(maxInstLen, Len);
+        InstrLen[i] = Len;
+      }
       std::string DecoderNamespace =
           std::string(EncodingDef->getValueAsString("DecoderNamespace"));
       if (!NumberedEncodings[i].HwModeName.empty())

     ArrayRef<EncodingAndInst> NumberedEncodingsRef(
         NumberedEncodings.data(), NumberedEncodings.size());
     FilterChooser FC(NumberedEncodingsRef, Opc.second, Operands,
-                     8 * Opc.first.second, this);
+                     isVarLenInst ? maxInstLen : 8 * Opc.first.second, this);
 
     // The decode table is cleared for each top level decoder function. The
     // predicates and decoders themselves, however, are shared across all

     OS.flush();
   }
 
+  if (isVarLenInst)
+    emitInstrLenTable(OS, InstrLen);
   // Emit the predicate function.
   emitPredicateFunction(OS, TableInfo.Predicates, 0);
 

   emitDecoderFunction(OS, TableInfo.Decoders, 0);
 
   // Emit the main entry point for the decoder, decodeInstruction().
-  emitDecodeInstruction(OS);
+  emitDecodeInstruction(OS, isVarLenInst);
 
   OS << "\n} // end namespace llvm\n";
 }

llvm/utils/TableGen/VarLenCodeEmitterGen.h

 #ifndef LLVM_UTILS_TABLEGEN_VARLENCODEEMITTERGEN_H
 #define LLVM_UTILS_TABLEGEN_VARLENCODEEMITTERGEN_H
 
+#include "llvm/TableGen/Record.h"
+
 namespace llvm {
 
+struct EncodingSegment {
+  unsigned BitWidth;
+  const Init *Value;
+  StringRef CustomEncoder = "";
+};
+
+class VarLenInst {
+  const RecordVal *TheDef;
+  size_t NumBits;
+
+  // Set if any of the segment is not fixed value.
+  bool HasDynamicSegment;
+
+  SmallVector<EncodingSegment, 4> Segments;
+
+  void buildRec(const DagInit *DI);
+
+  StringRef getCustomEncoderName(const Init *EI) const {
+    if (const auto *DI = dyn_cast<DagInit>(EI)) {
+      if (DI->getNumArgs() && isa<StringInit>(DI->getArg(0)))
+        return cast<StringInit>(DI->getArg(0))->getValue();
+    }
+    return "";
+  }
+
+public:
+  VarLenInst() : TheDef(nullptr), NumBits(0U), HasDynamicSegment(false) {}
+
+  explicit VarLenInst(const DagInit *DI, const RecordVal *TheDef);
+
+  /// Number of bits
+  size_t size() const { return NumBits; }
+
+  using const_iterator = decltype(Segments)::const_iterator;
+
+  const_iterator begin() const { return Segments.begin(); }
+  const_iterator end() const { return Segments.end(); }
+  size_t getNumSegments() const { return Segments.size(); }
+
+  bool isFixedValueOnly() const { return !HasDynamicSegment; }
+};
+
 class RecordKeeper;
 class raw_ostream;
 

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/TableGen/Error.h"
-#include "llvm/TableGen/Record.h"
 
 using namespace llvm;
 

 class VarLenCodeEmitterGen {
   RecordKeeper &Records;
 
-  struct EncodingSegment {
-    unsigned BitWidth;
-    const Init *Value;
-    StringRef CustomEncoder = "";
-  };
-
-  class VarLenInst {
-    RecordVal *TheDef;
-    size_t NumBits;
-
-    // Set if any of the segment is not fixed value.
-    bool HasDynamicSegment;
-
-    SmallVector<EncodingSegment, 4> Segments;
-
-    void buildRec(const DagInit *DI);
-
-    StringRef getCustomEncoderName(const Init *EI) const {
-      if (const auto *DI = dyn_cast<DagInit>(EI)) {
-        if (DI->getNumArgs() && isa<StringInit>(DI->getArg(0)))
-          return cast<StringInit>(DI->getArg(0))->getValue();
-      }
-      return "";
-    }
-
-  public:
-    VarLenInst() : TheDef(nullptr), NumBits(0U), HasDynamicSegment(false) {}
-
-    explicit VarLenInst(const DagInit *DI, RecordVal *TheDef);
-
-    /// Number of bits
-    size_t size() const { return NumBits; }
-
-    using const_iterator = decltype(Segments)::const_iterator;
-
-    const_iterator begin() const { return Segments.begin(); }
-    const_iterator end() const { return Segments.end(); }
-    size_t getNumSegments() const { return Segments.size(); }
-
-    bool isFixedValueOnly() const { return !HasDynamicSegment; }
-  };
-
   DenseMap<Record *, VarLenInst> VarLenInsts;
 
   // Emit based values (i.e. fixed bits in the encoded instructions)

 
 } // end anonymous namespace
 
-VarLenCodeEmitterGen::VarLenInst::VarLenInst(const DagInit *DI,
-                                             RecordVal *TheDef)
+VarLenInst::VarLenInst(const DagInit *DI, const RecordVal *TheDef)
     : TheDef(TheDef), NumBits(0U) {
   buildRec(DI);
   for (const auto &S : Segments)
     NumBits += S.BitWidth;
 }
 
-void VarLenCodeEmitterGen::VarLenInst::buildRec(const DagInit *DI) {
+void VarLenInst::buildRec(const DagInit *DI) {
   assert(TheDef && "The def record is nullptr ?");
 
   std::string Op = DI->getOperator()->getAsString();