[TableGen] Add Instruction custom byte sequence emission

[m4yers]

Summary

This patch is part of a bigger one D50314. It adds a possibility to emit a
custom sequence of bytes attributed to an Instruction.

This feature can be used to simplify CISC machine code emission as it done in
M68K D50314 patch. You can check out M680x0InstrFormats.td, M680x0InstrArithmetic.td and
M680x0MCCodeEmitter.cpp to see how it is used. In short, the process is
like this:

• Define a set of parameterized "beads" of length 8. The composition and meaning of those bits is up to the concrete backend. In m68k case first 4 bits is the type, the last 4 bits is the payload.
• Every non-pseudo instruction receives a number of those beads and stores them into Beads Instruction variable.
• The beads are read by this tablegen generator to emit an array of those beads referenced by instruction opcode.
• The MCCodeEmitter interprets the beads of a concrete instruction to emit a machine command. In m68k case type is read to interpret the payload, which can be a reference to an operand, an immediate value or a complex pattern.

[lebedev.ri]

Is there some testing approach for changes like this?
It really isn't ideal to just use the final use-case (the target) as the one any testing strategy for this.

utils/TableGen/CodeBeadsGen.cpp

14–15

Ignorant question: but surely the problem of storing instruction encoding in tablegen has already arose?
How does this solution differ from the existing practice?

[m4yers]

utils/TableGen/CodeBeadsGen.cpp

14–15

It allows to pass encoding strings of various length. Also it is semantically different from TSFlags and I thought it'd be a poor choice to extend its size and reuse.

[efriedma]

utils/TableGen/CodeBeadsGen.cpp

14–15

Most other targets use CodeEmitterGen to generate a function getBinaryCodeForInstr. This is nice, but it only works for targets with fixed-length instructions of length 4 or less.

x86 doesn't store instruction encodings in TableGen; instead, it uses a hand-written implementation of X86MCCodeEmitter::encodeInstruction, driven by flags in the instruction description.

[lebedev.ri]

utils/TableGen/CodeBeadsGen.cpp

14–15

(At the very least this should be explained here in the comment.)

27

map and vector are unused it seems.

53–55

I wonder if it would be more straight-forward to go the other way around?
You wouldn't need to manually worry to specify multiple-of-BeadSize-bits value.

102

I'm surprised there is no abstraction for this in LLVM already.
Maybe i'm looking in the wrong places.

[m4yers]

Small fixes

utils/TableGen/CodeBeadsGen.cpp

14–15

I will qualify that the binary string is of arbitrary size.

53–55

Do you mean like this?

constexpr unsigned BeadSize = 8;
constexpr unsigned BeadsNumber = 24;
constexpr unsigned BeadsLength = BeadsNumber * BeadSize;

[RKSimon]

@m4yers Abandon this now that the m68k target has landed?

utils/TableGen/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS Support)
 
 add_tablegen(llvm-tblgen LLVM
   AsmMatcherEmitter.cpp
   AsmWriterEmitter.cpp
   AsmWriterInst.cpp
   Attributes.cpp
   CallingConvEmitter.cpp
+  CodeBeadsGen.cpp
   CodeEmitterGen.cpp
   CodeGenDAGPatterns.cpp
   CodeGenHwModes.cpp
   CodeGenInstruction.cpp
   CodeGenMapTable.cpp
   CodeGenRegisters.cpp
   CodeGenSchedule.cpp
   CodeGenTarget.cpp

utils/TableGen/CodeBeadsGen.cpp

+//===-- CodeBeadsGen.cpp - Code Beads Generator -*- C++ -*-----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file
+/// This file contains tablegen implementation of "code beads", binary strings
+/// of arbitrary length defined for an instruction. They are used to pass very
+/// target specific binary information directly from a tablegen file, e.g.
+/// instruction encoding.
+///
+//===----------------------------------------------------------------------===//
+
+#include "CodeGenTarget.h"
+
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/TableGen/Error.h"
+#include "llvm/TableGen/Record.h"
+#include "llvm/TableGen/TableGenBackend.h"
+
+#include <string>
+
+using namespace llvm;
+
+namespace {
+
+class CodeBeadsGen {
+  RecordKeeper &Records;
+
+public:
+  CodeBeadsGen(RecordKeeper &R) : Records(R) {}
+  void run(raw_ostream &o);
+};
+
+void CodeBeadsGen::run(raw_ostream &o) {
+  CodeGenTarget Target(Records);
+
+  // For little-endian instruction bit encodings, reverse the bit order
+  Target.reverseBitsForLittleEndianEncoding();
+
+  auto Instructions = Target.getInstructionsByEnumValue();
+
+  constexpr unsigned BeadSize = 8;
+  constexpr unsigned BeadsNumber = 24;
+  constexpr unsigned BeadsLength = BeadsNumber * BeadSize;
+
+  // Emit function declaration
+  o << "const uint" << BeadSize << "_t * " << Target.getName();
+  o << "MCCodeEmitter::getGenInstrBeads(const MCInst &MI) const {\n";
+
+  // Emit instruction base values
+  o << "  static const uint" << BeadSize << "_t InstBits[][" << BeadsNumber
+    << "] = {\n";
+
+  for (const auto *CGI : Instructions) {
+    Record *R = CGI->TheDef;
+
+    // Pseudos don't have encoding
+    if (R->getValueAsString("Namespace") == "TargetOpcode" ||
+        R->getValueAsBit("isPseudo")) {
+      o << "\t{ 0x0 },";
+      o << '\t' << "// (Pseudo) " << R->getName() << "\n";
+      continue;
+    }
+
+    BitsInit *Beads = R->getValueAsBitsInit("Beads");
+
+    if (!Beads->isComplete()) {
+      PrintFatalError(R->getLoc(), "Record `" + R->getName() +
+                                       "', bit field 'Beads' is not complete");
+    }
+
+    if (Beads->getNumBits() > BeadsLength) {
+      PrintFatalError(R->getLoc(),
+                      "Record `" + R->getName() +
+                          "', bit field 'Beads' is too long(maximum: " +
+                          std::to_string(BeadsLength) + ")");
+    }
+
+    // Convert to byte array:
+    // [dcba] -> [a][b][c][d]
+    o << "\t{";
+    for (unsigned p = 0; p < BeadsNumber; ++p) {
+      unsigned Right = BeadSize * p;
+      unsigned Left = Right + BeadSize;
+      unsigned Value = 0;
+
+      for (unsigned i = Right; i != Left; ++i) {
+        unsigned Shift = i % BeadSize;
+
+        if (BitInit *B = dyn_cast<BitInit>(Beads->getBit(i))) {
+          Value |= (static_cast<unsigned>(B->getValue()) << Shift);
+        } else {
+          PrintFatalError(R->getLoc(),
+                          "Record `" + R->getName() + "', bit 'Beads[" +
+                              std::to_string(i) + "]' is not defined");
+        }
+      }
+
+      if (p != 0) {
+        o << ',';
+      }
+
+      o << " 0x";
+      o.write_hex(Value);
+      o << "";
+    }
+    o << " }," << '\t' << "// " << R->getName() << "\n";
+  }
+  o << "\t{ 0x0 }\n  };\n";
+
+  // Emit initial function code
+  o << "  return InstBits[MI.getOpcode()];\n"
+    << "}\n\n";
+}
+
+} // anonymous namespace
+
+namespace llvm {
+
+void EmitCodeBeads(RecordKeeper &RK, raw_ostream &OS) {
+  emitSourceFileHeader("Machine Code Beads", OS);
+  CodeBeadsGen(RK).run(OS);
+}
+
+} // namespace llvm

utils/TableGen/TableGen.cpp

 #include "llvm/TableGen/Record.h"
 #include "llvm/TableGen/SetTheory.h"
 
 using namespace llvm;
 
 enum ActionType {
   PrintRecords,
   DumpJSON,
+  GenCodeBeads,
   GenEmitter,
   GenRegisterInfo,
   GenInstrInfo,
   GenInstrDocs,
   GenAsmWriter,
   GenAsmMatcher,
   GenDisassembler,
   GenPseudoLowering,

 
 namespace {
   cl::opt<ActionType>
   Action(cl::desc("Action to perform:"),
          cl::values(clEnumValN(PrintRecords, "print-records",
                                "Print all records to stdout (default)"),
                     clEnumValN(DumpJSON, "dump-json",
                                "Dump all records as machine-readable JSON"),
+                    clEnumValN(GenCodeBeads, "gen-code-beads",
+                               "Generate machine code beads"),
                     clEnumValN(GenEmitter, "gen-emitter",
                                "Generate machine code emitter"),
                     clEnumValN(GenRegisterInfo, "gen-register-info",
                                "Generate registers and register classes info"),
                     clEnumValN(GenInstrInfo, "gen-instr-info",
                                "Generate instruction descriptions"),
                     clEnumValN(GenInstrDocs, "gen-instr-docs",
                                "Generate instruction documentation"),

 bool LLVMTableGenMain(raw_ostream &OS, RecordKeeper &Records) {
   switch (Action) {
   case PrintRecords:
     OS << Records;           // No argument, dump all contents
     break;
   case DumpJSON:
     EmitJSON(Records, OS);
     break;
+  case GenCodeBeads:
+    EmitCodeBeads(Records, OS);
+    break;
   case GenEmitter:
     EmitCodeEmitter(Records, OS);
     break;
   case GenRegisterInfo:
     EmitRegisterInfo(Records, OS);
     break;
   case GenInstrInfo:
     EmitInstrInfo(Records, OS);

utils/TableGen/TableGenBackends.h

 
 void EmitIntrinsicEnums(RecordKeeper &RK, raw_ostream &OS,
                         bool TargetOnly = false);
 void EmitIntrinsicImpl(RecordKeeper &RK, raw_ostream &OS,
                        bool TargetOnly = false);
 void EmitAsmMatcher(RecordKeeper &RK, raw_ostream &OS);
 void EmitAsmWriter(RecordKeeper &RK, raw_ostream &OS);
 void EmitCallingConv(RecordKeeper &RK, raw_ostream &OS);
+void EmitCodeBeads(RecordKeeper &RK, raw_ostream &OS);
 void EmitCodeEmitter(RecordKeeper &RK, raw_ostream &OS);
 void EmitDAGISel(RecordKeeper &RK, raw_ostream &OS);
 void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS);
 void EmitDisassembler(RecordKeeper &RK, raw_ostream &OS);
 void EmitFastISel(RecordKeeper &RK, raw_ostream &OS);
 void EmitInstrInfo(RecordKeeper &RK, raw_ostream &OS);
 void EmitInstrDocs(RecordKeeper &RK, raw_ostream &OS);
 void EmitPseudoLowering(RecordKeeper &RK, raw_ostream &OS);