[TableGen][CodeEmitter] Introducing the VarLenCodeEmitterGen infrastructure

[myhsu]

Summary

Full write up: https://gist.github.com/mshockwave/66e98d099256deefc062633909bb7b5b

The existing CodeEmitterGen infrastructure is unable to generate encoder function for ISAs with variable-length instructions. This patch introduces a new infrastructure to support variable-length instruction encoding, including a new TableGen syntax for writing instruction encoding directives and a new TableGen backend component, VarLenCodeEmitterGen, built on top of CodeEmitterGen.

[0x59616e]

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

46–48

Hi,
First off, I want to appreciate for all of your hard work. That's awesome. Really.

I have a question: shouldn't that && be || ?

My understanding is: We have to make sure that every argument is what it should be.

In this case, the first argument should be StringInit, the second should be IntInit, etc.

So, if one of them is incorret, then it is fatal error.

But this logic in the if statement won't fail unless all of the two (or three) arguments are not what they should be.

Thanks for reading this comment :)

[myhsu]

Fixed a minor logic issue.

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

46–48

yes you're right. Thanks!

[RKSimon]

Do you have any (full/partial) followup patches you can upload to phab showing the conversion of the M68k backend to VarLenCodeEmitterGen?

[myhsu]

In D115128#3175897, @RKSimon wrote:

Do you have any (full/partial) followup patches you can upload to phab showing the conversion of the M68k backend to VarLenCodeEmitterGen?

Yes I had already refactored all the arithmetic instructions in M68k (i.e. those in M68kInstrArithmetic.td). I was trying to add more documentations so I didn't show that at the beginning. I just put it in D115234.

[myhsu]

Incorporated feedbacks from @ricky26 :

• Replacing seq and seq:$dec with ascend and descend, respectively. The reason I picked these two words is because I want them to be more explicit on their placement directions (i.e. LSB->MSB and MSB->LSB).
• Replacing the operand operator in variant (operand "$foo", 8, 7) with slice operator.

I didn't incorporate the custom encoder idea we discussed on the mailing list because so far no one is using it and I want to make the patch as minimal as possible.

[ricky26]

LGTM. There's one comment that I think might be wrong. This is cool to see and I favour it much more than the existing code beads, IMO it's much more readable. Thanks! :)

llvm/include/llvm/Target/Target.td

761

These two examples seem to be the same.

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

67

Not really anything worth changing now (mostly a note to myself if I come to write a disassembler generator for this):
It might be worth coalescing neighbouring constant bits.

[myhsu]

In D115128#3187446, @ricky26 wrote:

LGTM. There's one comment that I think might be wrong. This is cool to see and I favour it much more than the existing code beads, IMO it's much more readable. Thanks! :)

Thank you for taking a look. I'll address those comments later. Meanwhile when I was refactoring other instructions (more specifically, control instructions that has pc-relative immediate) I found that your (encoder <custom encoder name>) directive is actually useful (using a custom encoder only on immediate that can be pc-relative). I'll push a separate review to add that feature.

[myhsu]

Updated documentations in include/llvm/Target/Target.td

llvm/include/llvm/Target/Target.td

761

you're right. I was intended to use the same arguments for both ascend and descend but forgot to change the final encodings.

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

67

oh, right, the coalescing will only happen in the later stage ( VarLenCodeEmitterGen::emitInstructionBaseValues). I agree it might be worth it to do in VarLenInst if we want to share this class with the disassembler.

[craig.topper]

Marking as changes required to flag the dangerous ArrayRef usage before this gets committed.

llvm/utils/TableGen/CodeEmitterGen.cpp

404

Given that only run is called on the VarLenCodeEmitterGen object, it might make sense to move the VarLenCodeEmitterGen class defintion into the cpp file and only expose a free function wrapper.

405

Curly brace the if body for consistency with the else

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

72

It might be better to not use the comma operator here and just have 3 variable declarations on 3 different lines.

84

I believe by the third paragraph of this section https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements this block and the follow else should have curly braces to keep consistency.

127

This code is dangerous. It will create a dangling reference to an initializer_list that goes out of scope when the line ends. Use a plain C array here.

llvm/utils/TableGen/VarLenCodeEmitterGen.h

17

I think there is typically a blank line after the include guards.

[craig.topper]

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

153

You can use auto here.

236

Can this use a Twine to build the message as part of the argument to report_fatal_error?

267

I think this violates the no static global constructor rule?

372

Curly braces to match the else

392

Why is this a separate std::string and not part of the stream?

404

Can this be return Case like the other changes in D115374

[myhsu]

Addressed coding standard feedbacks (thank you @craig.topper)

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

127

I don't think it will create a dangling reference in this particular case because DagInit::get actually copies NewArgs' elements. But I'm changing to plain C array anyway.

236

Unfortunately MCInst (i.e. MI here) doesn't have something like toString so using Twine might make the code here less concise.

267

no, InstBits (and InstBits_<HW mode>) is a local variable. Here is how it looks in the generated .inc file:

void M68kMCCodeEmitter::getBinaryCodeForInstr(const MCInst &MI,
    SmallVectorImpl<MCFixup> &Fixups,
    APInt &Inst,
    APInt &Scratch,
    const MCSubtargetInfo &STI) const {
  static const APInt InstBits[] = {
    APInt::getZeroWidth(),
    APInt::getZeroWidth(),
    APInt::getZeroWidth(),
...

[jrtc27]

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

267

A local variable with static storage duration, i.e. a static global that's scoped to the function

[jrtc27]

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

127

That's not Craig's point; ArrayRef<Init *> NewArgs = {OperandName, LoBit, HiBit}; itself is broken, as NewArgs points to storage after that statement whose lifetime has ended (well, it's fine so long as you never use NewArgs, but then it's pointless), so by the time you've reached DagInit::get it's already too late, the storage is gone. Using an initialiser list for ArrayRef is solely for use within the same statement (i.e. things like foo(ArrayRef({...})).

[myhsu]

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

127

I see, that makes sense. Thanks for the explanation.

267

you're right. Then I think a potential solution will be using two integer arrays:

static const unsigned Index[][2] = {
  {/*TotalBits*/36, /*Storage index*/0},  // FOO16
  {/*TotalBits*/80, /*Storage index*/1},  // FOO32
  ...
};
static const uint64_t Storage[] = {
  UINT64_C(53312), UINT64_C(53352), ...
};

And use Index to indirectly access fixed values of each instruction in Storage.

[craig.topper]

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

273

Can this be a range for loop? Or can we use auto to move the declaration of IE/EE into the for statement?

275

const reference?

277

Use a range for loop and ListSeparator to manage the new line?

[myhsu]

• Addressed minor issues.
• Replace const APInt InstBits[] =... with two integer arrays to avoid static global ctor.

Now we will have two arrays, Index and InstBits that look like this:

unsigned Index[][2] = {
  {/*NumBits*/87, /*Index to InstBits*/0}, // FOO16
  {/*NumBits*/39, /*Index to InstBits*/2}, // FOO32
};
uint64_t InstBits[] = {
  UINT64_C(<fixed values>), UINT64_C(...), // FOO16
  UINT64_C(...),  // FOO32
};

[craig.topper]

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

428

I think this can be Scratch = Scratch.zextOrSelf(BitWidth)

[myhsu]

Use APInt::zextOrSelf to adjust the scratch buffer size in the generated code. Also, avoid generating said code if an instruction only has fixed values.

[myhsu]

ping

[RKSimon]

@craig.topper Any more comments?

[RKSimon]

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

125

(style) Don't use auto for non-obvious return types (could be StringRef / std::string / const std::string& .......)

[craig.topper]

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

379

Can this use setBitVal like the BitInit case below?

[myhsu]

Addressed feedbacks.

[myhsu]

kindly ping

[craig.topper]

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

104

nit. Is the default for HwMode ever used? The call when HwModes is empty passes -1

325

Can the indent call be done before the loop?

Though I'm not sure about the indent. The NumBits and Index don't have a new line after them so we're not at the start of a line here.

364

Use VarLenInsts.find to avoid doing two map lookups?

424

Use VarLenInsts.find() instead of looking up the map twice?

[RKSimon]

@myhsu I noticed you've created some further child patches - is ther plan to create a patch sequence that updates the M68k code entirely before pushing?

[myhsu]

In D115128#3300112, @RKSimon wrote:

@myhsu I noticed you've created some further child patches - is ther plan to create a patch sequence that updates the M68k code entirely before pushing?

Not really, my current plan is to commit D115128 and D115234 right away once they're accepted. Same logics also goes to D119100 and D119101.
I'll make separate patches for rest of the M68k changes

[myhsu]

Addressed feedbacks.

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

104

good point, I'm fixing this on the callsite.

325

Though I'm not sure about the indent. The NumBits and Index don't have a new line after them so we're not at the start of a line here.

IS and SS are actually separate streams for different parts of the code. And SS.indent(4) is indeed at the start of a line (line 391 prints the newline for it).

[craig.topper]

LGTM

llvm/include/llvm/Target/Target.td

 def ops;
 def outs;
 def ins;
 
 /// variable_ops definition - Mark this instruction as taking a variable number
 /// of operands.
 def variable_ops;
 
+/// variable-length instruction utilities.
+/// The `seq` operator should be used like this:
+///     (seq 0b0110, 0b1101)
+/// Which described an 8-bit instruciton encoding 0b11010110. The arguments
+/// can either be bits, another DAG with `seq`, or a DAG with `operand`.
+/// In addition, we can use `$dec` on `seq` to describe an encoding that is
+/// constructed from DAG arguments in reversed ordering. For instance:
+///     (seq:$dec 0b0110, 0b1101)
+/// This results in an encoding of 0b01101101 rather than 0b11010110 we saw
+/// previously.
+def seq;
+/// The `operand` operator should be used like this:
+///     (operand "$src", 4)
+/// Which represents a 4-bit encoding for an instruction operand named `$src`.
+/// Alternatively, we can use only part of the instruction operand's encoding:
+///     (operand "$src", 9, 6)
+/// This DAG represents bit 6 to 9 (total of 4 bits) in the encoding of operand `$src`.
+/// Note that in this scheme, the second argument should always be the high bit.
+def operand;
 
 /// PointerLikeRegClass - Values that are designed to have pointer width are
 /// derived from this.  TableGen treats the register class as having a symbolic
 /// type that it doesn't know, and resolves the actual regclass to use by using
 /// the TargetRegisterInfo::getPointerRegClass() hook at codegen time.
 class PointerLikeRegClass<int Kind> {
   int RegClassKind = Kind;
 }

llvm/test/TableGen/VarLenEncoder.td

+// RUN: llvm-tblgen -gen-emitter -I %p/../../include %s | FileCheck %s
+
+// Check if VarLenCodeEmitterGen works correctly.
+
+include "llvm/Target/Target.td"
+
+def ArchInstrInfo : InstrInfo { }
+
+def Arch : Target {
+  let InstructionSet = ArchInstrInfo;
+}
+
+def Reg : Register<"reg">;
+
+def RegClass : RegisterClass<"foo", [i64], 0, (add Reg)>;
+
+def GR64 : RegisterOperand<RegClass>;
+
+class MyMemOperand<dag sub_ops> : Operand<iPTR> {
+  let MIOperandInfo = sub_ops;
+  dag Base;
+  dag Extension;
+}
+
+class MyVarInst<MyMemOperand memory_op> : Instruction {
+  dag Inst;
+
+  let OutOperandList = (outs GR64:$dst);
+  let InOperandList  = (ins memory_op:$src);
+
+  // Testing `seq` and `seq:$dec`
+  let Inst = (seq
+    (seq:$dec 0b10110111, memory_op.Base),
+    memory_op.Extension,
+    // Testing operand referencing.
+    (operand "$dst", 4),
+    // Testing operand referencing with a certain bit range.
+    (operand "$dst", 3, 1)
+  );
+}
+
+class MemOp16<string op_name> : MyMemOperand<(ops GR64:$reg, i16imm:$offset)> {
+  // Testing sub-operand referencing.
+  let Base = (operand "$"#op_name#".reg", 8);
+  let Extension = (operand "$"#op_name#".offset", 16);
+}
+
+class MemOp32<string op_name> : MyMemOperand<(ops GR64:$reg, i32imm:$offset)> {
+  let Base = (operand "$"#op_name#".reg", 8);
+  // Testing variable-length instruction encoding.
+  let Extension = (operand "$"#op_name#".offset", 32);
+}
+
+def FOO16 : MyVarInst<MemOp16<"src">>;
+def FOO32 : MyVarInst<MemOp32<"src">>;
+
+// The fixed bits part
+// CHECK: APInt(39, UINT64_C(46848)), // FOO16
+// CHECK: APInt(55, UINT64_C(46848)), // FOO32
+
+// CHECK-LABEL: case ::FOO16: {
+// CHECK:     if (Scratch.getBitWidth() < 39)
+// CHECK-NEXT:   Scratch = Scratch.zext(39);
+// src.reg
+// CHECK: getMachineOpValue(MI, MI.getOperand(1), Scratch, Fixups, STI);
+// CHECK: Inst.insertBits(Scratch.extractBits(8, 0), 0);
+// src.offset
+// CHECK: getMachineOpValue(MI, MI.getOperand(2), Scratch, Fixups, STI);
+// CHECK: Inst.insertBits(Scratch.extractBits(16, 0), 16);
+// 1st dst
+// CHECK: getMachineOpValue(MI, MI.getOperand(0), Scratch, Fixups, STI);
+// CHECK: Inst.insertBits(Scratch.extractBits(4, 0), 32);
+// 2nd dst
+// CHECK: getMachineOpValue(MI, MI.getOperand(0), Scratch, Fixups, STI);
+// CHECK: Inst.insertBits(Scratch.extractBits(3, 1), 36);
+
+// CHECK-LABEL: case ::FOO32: {
+// CHECK:     if (Scratch.getBitWidth() < 55)
+// CHECK-NEXT:   Scratch = Scratch.zext(55);
+// src.reg
+// CHECK: getMachineOpValue(MI, MI.getOperand(1), Scratch, Fixups, STI);
+// CHECK: Inst.insertBits(Scratch.extractBits(8, 0), 0);
+// src.offset
+// CHECK: getMachineOpValue(MI, MI.getOperand(2), Scratch, Fixups, STI);
+// CHECK: Inst.insertBits(Scratch.extractBits(32, 0), 16);
+// 1st dst
+// CHECK: getMachineOpValue(MI, MI.getOperand(0), Scratch, Fixups, STI);
+// CHECK: Inst.insertBits(Scratch.extractBits(4, 0), 48);
+// 2nd dst
+// CHECK: getMachineOpValue(MI, MI.getOperand(0), Scratch, Fixups, STI);
+// CHECK: Inst.insertBits(Scratch.extractBits(3, 1), 52);

llvm/utils/TableGen/CMakeLists.txt

add_tablegen(llvm-tblgen LLVM
   RegisterBankEmitter.cpp
   RegisterInfoEmitter.cpp
   SDNodeProperties.cpp
   SearchableTableEmitter.cpp
   SubtargetEmitter.cpp
   SubtargetFeatureInfo.cpp
   TableGen.cpp
   Types.cpp
+  VarLenCodeEmitterGen.cpp
   X86DisassemblerTables.cpp
   X86EVEX2VEXTablesEmitter.cpp
   X86FoldTablesEmitter.cpp
   X86ModRMFilters.cpp
   X86RecognizableInstr.cpp
   WebAssemblyDisassemblerEmitter.cpp
   CTagsEmitter.cpp
   )
 target_link_libraries(llvm-tblgen PRIVATE LLVMTableGenGlobalISel)
 set_target_properties(llvm-tblgen PROPERTIES FOLDER "Tablegenning")

llvm/utils/TableGen/CodeEmitterGen.cpp

 // returns the (currently, 32-bit unsigned) value of the instruction.
 //
 //===----------------------------------------------------------------------===//
 
 #include "CodeGenInstruction.h"
 #include "CodeGenTarget.h"
 #include "SubtargetFeatureInfo.h"
 #include "Types.h"
+#include "VarLenCodeEmitterGen.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/TableGen/Record.h"
 #include "llvm/TableGen/TableGenBackend.h"
 #include <cassert>
void CodeEmitterGen::run(raw_ostream &o) {
   std::vector<Record*> Insts = Records.getAllDerivedDefinitions("Instruction");
 
   // For little-endian instruction bit encodings, reverse the bit order
   Target.reverseBitsForLittleEndianEncoding();
 
   ArrayRef<const CodeGenInstruction*> NumberedInstructions =
     Target.getInstructionsByEnumValue();
 
+  if (any_of(NumberedInstructions, [](const CodeGenInstruction *CGI) {
+        Record *R = CGI->TheDef;
+        return R->getValue("Inst") && isa<DagInit>(R->getValueInit("Inst"));
+      }))
+    VarLenCodeEmitterGen(Records).run(o);
+  else {
     const CodeGenHwModes &HWM = Target.getHwModes();
     // The set of HwModes used by instruction encodings.
     std::set<unsigned> HwModes;
     BitWidth = 0;
     for (const CodeGenInstruction *CGI : NumberedInstructions) {
       Record *R = CGI->TheDef;
       if (R->getValueAsString("Namespace") == "TargetOpcode" ||
           R->getValueAsBit("isPseudo"))
         continue;
 
       if (const RecordVal *RV = R->getValue("EncodingInfos")) {
         if (DefInit *DI = dyn_cast_or_null<DefInit>(RV->getValue())) {
           EncodingInfoByHwMode EBM(DI->getDef(), HWM);
           for (auto &KV : EBM) {
             BitsInit *BI = KV.second->getValueAsBitsInit("Inst");
             BitWidth = std::max(BitWidth, BI->getNumBits());
             HwModes.insert(KV.first);
           }
           continue;
         }
       }
       BitsInit *BI = R->getValueAsBitsInit("Inst");
       BitWidth = std::max(BitWidth, BI->getNumBits());
     }
     UseAPInt = BitWidth > 64;
-  
     // Emit function declaration
     if (UseAPInt) {
       o << "void " << Target.getName()
         << "MCCodeEmitter::getBinaryCodeForInstr(const MCInst &MI,\n"
         << "    SmallVectorImpl<MCFixup> &Fixups,\n"
         << "    APInt &Inst,\n"
         << "    APInt &Scratch,\n"
         << "    const MCSubtargetInfo &STI) const {\n";
     } else {
       o << "uint64_t " << Target.getName();
       o << "MCCodeEmitter::getBinaryCodeForInstr(const MCInst &MI,\n"
         << "    SmallVectorImpl<MCFixup> &Fixups,\n"
         << "    const MCSubtargetInfo &STI) const {\n";
     }
-  
     // Emit instruction base values
     if (HwModes.empty()) {
       emitInstructionBaseValues(o, NumberedInstructions, Target, -1);
     } else {
       for (unsigned HwMode : HwModes)
         emitInstructionBaseValues(o, NumberedInstructions, Target, (int)HwMode);
     }
 
     if (!HwModes.empty()) {
       o << "  const uint64_t *InstBits;\n";
       o << "  unsigned HwMode = STI.getHwMode();\n";
       o << "  switch (HwMode) {\n";
       o << "  default: llvm_unreachable(\"Unknown hardware mode!\"); break;\n";
       for (unsigned I : HwModes) {
         o << "  case " << I << ": InstBits = InstBits_" << HWM.getMode(I).Name
           << "; break;\n";
       }
       o << "  };\n";
     }
 
     // Map to accumulate all the cases.
     std::map<std::string, std::vector<std::string>> CaseMap;
 
     // Construct all cases statement for each opcode
     for (Record *R : Insts) {
       if (R->getValueAsString("Namespace") == "TargetOpcode" ||
           R->getValueAsBit("isPseudo"))
         continue;
       std::string InstName =
           (R->getValueAsString("Namespace") + "::" + R->getName()).str();
       std::string Case = getInstructionCase(R, Target);
 
       CaseMap[Case].push_back(std::move(InstName));
     }
 
     // Emit initial function code
     if (UseAPInt) {
       int NumWords = APInt::getNumWords(BitWidth);
       int NumBytes = (BitWidth + 7) / 8;
       o << "  const unsigned opcode = MI.getOpcode();\n"
         << "  if (Inst.getBitWidth() != " << BitWidth << ")\n"
         << "    Inst = Inst.zext(" << BitWidth << ");\n"
         << "  if (Scratch.getBitWidth() != " << BitWidth << ")\n"
         << "    Scratch = Scratch.zext(" << BitWidth << ");\n"
         << "  LoadIntFromMemory(Inst, (const uint8_t *)&InstBits[opcode * "
         << NumWords << "], " << NumBytes << ");\n"
         << "  APInt &Value = Inst;\n"
         << "  APInt &op = Scratch;\n"
         << "  switch (opcode) {\n";
     } else {
       o << "  const unsigned opcode = MI.getOpcode();\n"
         << "  uint64_t Value = InstBits[opcode];\n"
         << "  uint64_t op = 0;\n"
         << "  (void)op;  // suppress warning\n"
         << "  switch (opcode) {\n";
     }
 
     // Emit each case statement
     std::map<std::string, std::vector<std::string>>::iterator IE, EE;
     for (IE = CaseMap.begin(), EE = CaseMap.end(); IE != EE; ++IE) {
       const std::string &Case = IE->first;
       std::vector<std::string> &InstList = IE->second;
 
       for (int i = 0, N = InstList.size(); i < N; i++) {
-      if (i) o << "\n";
-      o << "    case " << InstList[i]  << ":";
+        if (i)
+          o << "\n";
+        o << "    case " << InstList[i] << ":";
       }
       o << " {\n";
       o << Case;
       o << "      break;\n"
         << "    }\n";
     }
 
     // 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().c_str());\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";

llvm/utils/TableGen/VarLenCodeEmitterGen.h

+#ifndef LLVM_UTILS_TABLEGEN_VARLENCODEEMITTERGEN_H
+#define LLVM_UTILS_TABLEGEN_VARLENCODEEMITTERGEN_H
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/TableGen/Record.h"
+
+namespace llvm {
+// Forward declarations
+class CodeGenTarget;
+class CodeGenInstruction;
+
+class VarLenCodeEmitterGen {
+  RecordKeeper &Records;
+
+  class VarLenInst {
+    size_t NumBits;
+
+    // {Number of bits, Value}
+    SmallVector<std::pair<unsigned, const Init *>, 4> Segments;
+
+    void buildRec(const DagInit *DI);
+
+  public:
+    VarLenInst() : NumBits(0U) {}
+
+    explicit VarLenInst(const DagInit *DI);
+
+    /// 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(); }
+  };
+
+  DenseMap<Record *, VarLenInst> VarLenInsts;
+
+  // Emit based values (i.e. fixed bits in the encoded instructions)
+  void emitInstructionBaseValues(
+      raw_ostream &OS,
+      ArrayRef<const CodeGenInstruction *> NumberedInstructions,
+      CodeGenTarget &Target, int HwMode = -1);
+
+  std::string getInstructionCase(Record *R, CodeGenTarget &Target);
+  std::string getInstructionCaseForEncoding(Record *R, Record *EncodingDef,
+                                            CodeGenTarget &Target);
+
+public:
+  explicit VarLenCodeEmitterGen(RecordKeeper &R) : Records(R) {}
+
+  void run(raw_ostream &OS);
+};
+} // end namespace llvm
+#endif

llvm/utils/TableGen/VarLenCodeEmitterGen.cpp

+#include "VarLenCodeEmitterGen.h"
+#include "CodeGenInstruction.h"
+#include "CodeGenTarget.h"
+#include "SubtargetFeatureInfo.h"
+#include "llvm/TableGen/Error.h"
+
+using namespace llvm;
+
+VarLenCodeEmitterGen::VarLenInst::VarLenInst(const DagInit *DI) : NumBits(0U) {
+  buildRec(DI);
+  for (const auto &S : Segments)
+    NumBits += S.first;
+}
+
+void VarLenCodeEmitterGen::VarLenInst::buildRec(const DagInit *DI) {
+  auto Op = DI->getOperator()->getAsString();
+
+  if (Op == "seq") {
+    bool Reverse = DI->getNameStr() == "dec";
+    int i = Reverse ? DI->getNumArgs() - 1 : 0,
+        e = Reverse ? -1 : DI->getNumArgs(), s = Reverse ? -1 : 1;
+    for (; i != e; i += s) {
+      const Init *Arg = DI->getArg(i);
+      if (const auto *BI = dyn_cast<BitsInit>(Arg)) {
+        if (!BI->isComplete())
+          PrintFatalError("Expecting complete bits init in seq");
+        Segments.push_back({BI->getNumBits(), BI});
+      } else if (const auto *BI = dyn_cast<BitInit>(Arg)) {
+        if (!BI->isConcrete())
+          PrintFatalError("Expecting concrete bit init in seq");
+        Segments.push_back({1, BI});
+      } else if (const auto *SubDI = dyn_cast<DagInit>(Arg))
+        buildRec(SubDI);
+      else
+        PrintFatalError("Unrecognized type of argument in seq: " +
+                        Arg->getAsString());
+    }
+  } else if (Op == "operand") {
+    // There are two formats for `operand`
+    // 1. (operand <operand name>, <# of bits>)
+    // 2. (operand <operand name>, <high bit>, <low bit>)
+    if (DI->getNumArgs() < 2)
+      PrintFatalError("Expecting at least 2 arguments for operand");
+    const Init *OperandName = DI->getArg(0), *HiBit = DI->getArg(1),
+               *LoBit = DI->getNumArgs() >= 3 ? DI->getArg(2) : nullptr;
+    if (!isa<StringInit>(OperandName) && !isa<IntInit>(HiBit) &&
+        (LoBit && !isa<IntInit>(LoBit)))
+      PrintFatalError("Invalid format for operand");
+    auto HiBitVal = cast<IntInit>(HiBit)->getValue(),
+         LoBitVal = LoBit ? cast<IntInit>(LoBit)->getValue() : 0;
+    if (HiBitVal < 0 || LoBitVal < 0 || HiBitVal <= LoBitVal)
+      PrintFatalError("Invalid bit range. Hi: " + std::to_string(HiBitVal) +
+                      ", Lo: " + std::to_string(LoBitVal));
+    unsigned NumBitsVal = static_cast<unsigned>(HiBitVal - LoBitVal);
+    if (LoBit) {
+      // (operand <operand name>, <high bit>, <low bit>)
+      ++NumBitsVal;
+      Segments.push_back({NumBitsVal, DI});
+    } else {
+      // (operand <operand name>, <# of bits>)
+      Segments.push_back({NumBitsVal, OperandName});
+    }
+  }
+}
+
+void VarLenCodeEmitterGen::run(raw_ostream &OS) {
+  CodeGenTarget Target(Records);
+  auto Insts = Records.getAllDerivedDefinitions("Instruction");
+
+  auto NumberedInstructions = Target.getInstructionsByEnumValue();
+  const CodeGenHwModes &HWM = Target.getHwModes();
+
+  // The set of HwModes used by instruction encodings.
+  std::set<unsigned> HwModes;
+  for (const CodeGenInstruction *CGI : NumberedInstructions) {
+    Record *R = CGI->TheDef;
+
+    // Create the corresponding VarLenInst instance.
+    if (R->getValueAsString("Namespace") == "TargetOpcode" ||
+        R->getValueAsBit("isPseudo"))
+      continue;
+
+    if (const RecordVal *RV = R->getValue("EncodingInfos")) {
+      if (DefInit *DI = dyn_cast_or_null<DefInit>(RV->getValue())) {
+        EncodingInfoByHwMode EBM(DI->getDef(), HWM);
+        for (auto &KV : EBM) {
+          HwModes.insert(KV.first);
+          Record *EncodingDef = KV.second;
+          auto *DI = EncodingDef->getValueAsDag("Inst");
+          VarLenInsts.insert({EncodingDef, VarLenInst(DI)});
+        }
+        continue;
+      }
+    }
+    auto *DI = R->getValueAsDag("Inst");
+    VarLenInsts.insert({R, VarLenInst(DI)});
+  }
+
+  // Emit function declaration
+  OS << "void " << Target.getName()
+     << "MCCodeEmitter::getBinaryCodeForInstr(const MCInst &MI,\n"
+     << "    SmallVectorImpl<MCFixup> &Fixups,\n"
+     << "    APInt &Inst,\n"
+     << "    APInt &Scratch,\n"
+     << "    const MCSubtargetInfo &STI) const {\n";
+
+  // Emit instruction base values
+  if (HwModes.empty()) {
+    emitInstructionBaseValues(OS, NumberedInstructions, Target, -1);
+  } else {
+    for (unsigned HwMode : HwModes)
+      emitInstructionBaseValues(OS, NumberedInstructions, Target, (int)HwMode);
+  }
+
+  if (!HwModes.empty()) {
+    OS << "  const uint64_t *InstBits;\n";
+    OS << "  unsigned HwMode = STI.getHwMode();\n";
+    OS << "  switch (HwMode) {\n";
+    OS << "  default: llvm_unreachable(\"Unknown hardware mode!\"); break;\n";
+    for (unsigned I : HwModes) {
+      OS << "  case " << I << ": InstBits = InstBits_" << HWM.getMode(I).Name
+         << "; break;\n";
+    }
+    OS << "  };\n";
+  }
+
+  // Map to accumulate all the cases.
+  std::map<std::string, std::vector<std::string>> CaseMap;
+
+  // Construct all cases statement for each opcode
+  for (Record *R : Insts) {
+    if (R->getValueAsString("Namespace") == "TargetOpcode" ||
+        R->getValueAsBit("isPseudo"))
+      continue;
+    std::string InstName =
+        (R->getValueAsString("Namespace") + "::" + R->getName()).str();
+    std::string Case = getInstructionCase(R, Target);
+
+    CaseMap[Case].push_back(std::move(InstName));
+  }
+
+  // Emit initial function code
+  OS << "  const unsigned opcode = MI.getOpcode();\n"
+     << "  switch (opcode) {\n";
+
+  // Emit each case statement
+  std::map<std::string, std::vector<std::string>>::iterator IE, EE;
+  for (IE = CaseMap.begin(), EE = CaseMap.end(); IE != EE; ++IE) {
+    const std::string &Case = IE->first;
+    std::vector<std::string> &InstList = IE->second;
+
+    for (int i = 0, N = InstList.size(); i < N; i++) {
+      if (i)
+        OS << "\n";
+      OS << "    case " << InstList[i] << ":";
+    }
+    OS << " {\n";
+    OS << Case;
+    OS << "      break;\n"
+       << "    }\n";
+  }
+  // Default case: unhandled opcode
+  OS << "  default:\n"
+     << "    std::string msg;\n"
+     << "    raw_string_ostream Msg(msg);\n"
+     << "    Msg << \"Not supported instr: \" << MI;\n"
+     << "    report_fatal_error(Msg.str().c_str());\n"
+     << "  }\n";
+  OS << "}\n\n";
+}
+
+static void emitInstBits(raw_ostream &OS, const APInt &Bits) {
+  if (!Bits.getNumWords()) {
+    // Use factory method to avoid ambiguous usages of ctors.
+    OS << "APInt::getZeroWidth()";
+    return;
+  }
+
+  OS << "APInt(" << Bits.getBitWidth() << ", ";
+  // Only emit braces if it's more than one word.
+  if (Bits.getNumWords() > 1)
+    OS << "{";
+
+  for (unsigned I = 0; I < Bits.getNumWords(); ++I)
+    OS << ((I > 0) ? ", " : "") << "UINT64_C(" << utostr(Bits.getRawData()[I])
+       << ")";
+
+  if (Bits.getNumWords() > 1)
+    OS << "}";
+  OS << ")";
+}
+
+void VarLenCodeEmitterGen::emitInstructionBaseValues(
+    raw_ostream &OS, ArrayRef<const CodeGenInstruction *> NumberedInstructions,
+    CodeGenTarget &Target, int HwMode) {
+  const CodeGenHwModes &HWM = Target.getHwModes();
+  if (HwMode == -1)
+    OS << "  static const APInt InstBits[] = {\n";
+  else
+    OS << "  static const APInt InstBits_" << HWM.getMode(HwMode).Name
+       << "[] = {\n";
+
+  for (const CodeGenInstruction *CGI : NumberedInstructions) {
+    Record *R = CGI->TheDef;
+
+    if (R->getValueAsString("Namespace") == "TargetOpcode" ||
+        R->getValueAsBit("isPseudo")) {
+      OS.indent(4) << "APInt::getZeroWidth(),\n";
+      continue;
+    }
+
+    Record *EncodingDef = R;
+    if (const RecordVal *RV = R->getValue("EncodingInfos")) {
+      if (auto *DI = dyn_cast_or_null<DefInit>(RV->getValue())) {
+        EncodingInfoByHwMode EBM(DI->getDef(), HWM);
+        if (EBM.hasMode(HwMode))
+          EncodingDef = EBM.get(HwMode);
+      }
+    }
+
+    if (!VarLenInsts.count(EncodingDef))
+      PrintFatalError(EncodingDef, "VarLenInst not found for this record");
+    const VarLenInst &VLI = VarLenInsts[EncodingDef];
+
+    unsigned i = 0U, BitWidth = VLI.size();
+
+    // Start by filling in fixed values.
+    APInt Value(BitWidth, 0);
+    auto SI = VLI.begin(), SE = VLI.end();
+    // Scan through all the segments that have fixed-bits values.
+    while (i < BitWidth && SI != SE) {
+      unsigned SegmentNumBits = SI->first;
+      if (const auto *BI = dyn_cast<BitsInit>(SI->second)) {
+        for (unsigned Idx = 0U; Idx != SegmentNumBits; ++Idx) {
+          auto *B = cast<BitInit>(BI->getBit(Idx));
+          Value |= APInt(BitWidth, (uint64_t)B->getValue()) << (i + Idx);
+        }
+      }
+      if (const auto *BI = dyn_cast<BitInit>(SI->second))
+        Value.setBitVal(i, BI->getValue());
+
+      i += SegmentNumBits;
+      ++SI;
+    }
+    OS << "    ";
+    emitInstBits(OS, Value);
+    OS << "," << '\t' << "// " << R->getName() << "\n";
+  }
+  OS.indent(4) << "APInt::getZeroWidth()\n  };\n";
+}
+
+std::string VarLenCodeEmitterGen::getInstructionCase(Record *R,
+                                                     CodeGenTarget &Target) {
+  std::string Case;
+  if (const RecordVal *RV = R->getValue("EncodingInfos")) {
+    if (auto *DI = dyn_cast_or_null<DefInit>(RV->getValue())) {
+      const CodeGenHwModes &HWM = Target.getHwModes();
+      EncodingInfoByHwMode EBM(DI->getDef(), HWM);
+      Case += "      switch (HwMode) {\n";
+      Case += "      default: llvm_unreachable(\"Unhandled HwMode\");\n";
+      for (auto &KV : EBM) {
+        Case += "      case " + itostr(KV.first) + ": {\n";
+        Case += getInstructionCaseForEncoding(R, KV.second, Target);
+        Case += "      break;\n";
+        Case += "      }\n";
+      }
+      Case += "      }\n";
+      return Case;
+    }
+  }
+  return getInstructionCaseForEncoding(R, R, Target);
+}
+
+std::string VarLenCodeEmitterGen::getInstructionCaseForEncoding(
+    Record *R, Record *EncodingDef, CodeGenTarget &Target) {
+  if (!VarLenInsts.count(EncodingDef))
+    PrintFatalError(EncodingDef, "Parsed encoding record not found");
+  const VarLenInst &VLI = VarLenInsts[EncodingDef];
+  size_t BitWidth = VLI.size();
+
+  CodeGenInstruction &CGI = Target.getInstruction(R);
+
+  std::string Case;
+  raw_string_ostream SS(Case);
+  // Resize the scratch buffer.
+  if (BitWidth) {
+    SS.indent(6) << "if (Scratch.getBitWidth() < " << BitWidth << ")\n";
+    SS.indent(6) << "  Scratch = Scratch.zext(" << BitWidth << ");\n";
+  }
+  // Populate based value.
+  SS.indent(6) << "Inst = InstBits[opcode];\n";
+
+  // Process each segment in VLI.
+  size_t Offset = 0U;
+  for (const auto &Pair : VLI) {
+    unsigned NumBits = Pair.first;
+    const Init *Val = Pair.second;
+    // If it's a StringInit or DagInit, it's a reference to an operand.
+    if (isa<StringInit>(Val) || isa<DagInit>(Val)) {
+      StringRef OperandName;
+      unsigned LoBit = 0U;
+      if (const auto *SV = dyn_cast<StringInit>(Val))
+        OperandName = SV->getValue();
+      else {
+        // (operand <operand name>, <high bit>, <low bit>)
+        const auto *DV = cast<DagInit>(Val);
+        OperandName = cast<StringInit>(DV->getArg(0))->getValue();
+        LoBit = static_cast<unsigned>(cast<IntInit>(DV->getArg(2))->getValue());
+      }
+
+      auto OpIdx = CGI.Operands.ParseOperandName(OperandName);
+      unsigned FlatOpIdx = CGI.Operands.getFlattenedOperandNumber(OpIdx);
+      StringRef EncoderMethodName = "getMachineOpValue";
+      auto &CustomEncoder = CGI.Operands[OpIdx.first].EncoderMethodName;
+      if (!CustomEncoder.empty())
+        EncoderMethodName = CustomEncoder;
+
+      SS.indent(6) << "Scratch.clearAllBits();\n";
+      SS.indent(6) << "// op: " << OperandName.drop_front(1) << "\n";
+      SS.indent(6) << EncoderMethodName << "(MI, MI.getOperand("
+                   << utostr(FlatOpIdx) << "), Scratch, Fixups, STI);\n";
+      std::string ExtractStr =
+          "Scratch.extractBits(" + utostr(NumBits) + ", " + utostr(LoBit) + ")";
+      SS.indent(6) << "Inst.insertBits(" << ExtractStr << ", " << Offset
+                   << ");\n";
+    }
+    Offset += NumBits;
+  }
+
+  StringRef PostEmitter = R->getValueAsString("PostEncoderMethod");
+  if (!PostEmitter.empty())
+    SS.indent(6) << "Inst = " << PostEmitter << "(MI, Inst, STI);\n";
+
+  return std::move(SS.str());
+}