[tblgen][disasm] Separate encodings from instructions

[dsanders]

Summary

Separate the concept of an encoding from an instruction. This will enable
the definition of additional encodings for the same instruction which can
be used to support variable length instruction sets in the disassembler
(and potentially assembler but I'm not working towards that right now)
without causing an explosion in the number of Instruction records that
CodeGen then has to pick between.

[dsanders]

ping

[dsanders]

ping

[dsanders]

ping

[kparzysz]

The encoding of an instruction includes encodings of its operands. How are you planning to implement separate encoder/decoder methods? Right now their names are all embedded into operand definitions.

[dsanders]

In D52366#1269627, @kparzysz wrote:

The encoding of an instruction includes encodings of its operands. How are you planning to implement separate encoder/decoder methods? Right now their names are all embedded into operand definitions.

The follow-on patch, D52369, adds the AdditionalEncoding class which defines the encoding in the same way that an Instruction does:

def : AdditionalEncoding<ADD1> {
  bits<8> Reg;
  bits<16> Inst; // You can also have bits<32> and it will still be a 16-bit encoding
  let Size = 2;
  let Inst{0-3} = 0;
  let Inst{4-7} = Reg;
  let Inst{8-15} = 0;
  ...
}

the decoders for variable fields like Reg from the above example are going to be inherited from the Instruction that the encoding maps to. This is sufficient for the majority of cases since many compressed ISA's use the same field encoding and only apply tighter range limits for the shorter encodings. There are a few that change the field encoding in a bigger way than merely truncating the bits and that case is currently only supported via AdditionalEncoding.DecoderMethod which would have to extract and decode every operand. I'm thinking that the per-operand DecoderMethods could be done with a field along the lines of:

list<NameToOperand> OperandOverrides = [NameToOperand<"Reg", SomeOperand>];

where NameToOperand is a class along the lines of:

class NameToOperand<string name, Operand operand> {
  string Name = name;
  Operand Op = operand;
}

that would then need to be plumbed into the code responsible for generating the code to extract and decode the variable fields.

The encoding side of things isn't something I've considered much so far since there's non-trivial decisions to be made to pick between the choices of valid encodings and these impact optimization as well as the validity of the generated code (e.g. jump tables sometimes need a known size to calculate the target of the jump). I've generally tried to make sure the AdditionalEncoding class makes sense from an encoder perspective but I haven't given much thought to actually generating an encoder from it yet

[dsanders]

Rebase

[dsanders]

Fold in another correction that ended up in a downstream-specific patch:
Only emit 'FOO => BAR' comments encodings caused by AdditionalEncoding. For Instruction, keep the existing 'FOO' comments.

[bogner]

utils/TableGen/FixedLenDecoderEmitter.cpp

94–95

Would simplifying by omitting this and just using brace-initialization be better?

419–421

Why not use the operator<< here if you're going to define it above anyway?

842–844

Same here (unless using => instead of : is important for some reason?)

[dsanders]

utils/TableGen/FixedLenDecoderEmitter.cpp

94–95

It's needed for std::vector<EncodingAndInst>::emplace_back(). It eventually ends up failing on the placement new inside std::allocator::construct() without it

419–421

Well spotted. It's just that I didn't notice this one when I added the operator. I'll fix this

842–844

It's not hugely important. I used => here to indicate that we've matched the AlternateEncoding record but we're building the MCInst as if we'd matched the Instruction. I can switch this for the operator

[dsanders]

Fixed the nits about not using the << operator but doing the same thing it does

[bogner]

utils/TableGen/FixedLenDecoderEmitter.cpp

94–95

I doubt that emplace_back() is much/any better than push_back({...}) for a simple value type like this, so I'd personally probably go with the simpler approach. It's pretty minor though.

utils/TableGen/FixedLenDecoderEmitter.cpp

 typedef SmallSetVector<CachedHashString, 16> DecoderSet;
 struct DecoderTableInfo {
   DecoderTable Table;
   FixupScopeList FixupStack;
   PredicateSet Predicates;
   DecoderSet Decoders;
 };
 
+struct EncodingAndInst {
+  const Record *EncodingDef;
+  const CodeGenInstruction *Inst;
+
+  EncodingAndInst(const Record *EncodingDef, const CodeGenInstruction *Inst)
+      : EncodingDef(EncodingDef), Inst(Inst) {}
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const EncodingAndInst &Value) {
+  if (Value.EncodingDef != Value.Inst->TheDef)
+    OS << Value.EncodingDef->getName() << ":";
+  OS << Value.Inst->TheDef->getName();
+  return OS;
+}
+
 class FixedLenDecoderEmitter {
-  ArrayRef<const CodeGenInstruction *> NumberedInstructions;
+  std::vector<EncodingAndInst> NumberedEncodings;
 
 public:
   // Defaults preserved here for documentation, even though they aren't
   // strictly necessary given the way that this is currently being called.
   FixedLenDecoderEmitter(RecordKeeper &R, std::string PredicateNamespace,
                          std::string GPrefix = "if (",
                          std::string GPostfix = " == MCDisassembler::Fail)",
                          std::string ROK = "MCDisassembler::Success",

 /// decide what further remaining bits to look at.
 namespace {
 
 class FilterChooser {
 protected:
   friend class Filter;
 
   // Vector of codegen instructions to choose our filter.
-  ArrayRef<const CodeGenInstruction *> AllInstructions;
+  ArrayRef<const EncodingAndInst> AllInstructions;
 
   // Vector of uid's for this filter chooser to work on.
   const std::vector<unsigned> &Opcodes;
 
   // Lookup table for the operand decoding of instructions.
   const std::map<unsigned, std::vector<OperandInfo>> &Operands;
 
   // Vector of candidate filters.
protected:
 
   // Width of instructions
   unsigned BitWidth;
 
   // Parent emitter
   const FixedLenDecoderEmitter *Emitter;
 
 public:
-  FilterChooser(ArrayRef<const CodeGenInstruction *> Insts,
+  FilterChooser(ArrayRef<const EncodingAndInst> Insts,
                 const std::vector<unsigned> &IDs,
                 const std::map<unsigned, std::vector<OperandInfo>> &Ops,
-                unsigned BW,
-                const FixedLenDecoderEmitter *E)
+                unsigned BW, const FixedLenDecoderEmitter *E)
       : AllInstructions(Insts), Opcodes(IDs), Operands(Ops),
         FilterBitValues(BW, BIT_UNFILTERED), Parent(nullptr), BestIndex(-1),
         BitWidth(BW), Emitter(E) {
     doFilter();
   }
 
-  FilterChooser(ArrayRef<const CodeGenInstruction *> Insts,
+  FilterChooser(ArrayRef<const EncodingAndInst> Insts,
                 const std::vector<unsigned> &IDs,
                 const std::map<unsigned, std::vector<OperandInfo>> &Ops,
                 const std::vector<bit_value_t> &ParentFilterBitValues,
                 const FilterChooser &parent)
       : AllInstructions(Insts), Opcodes(IDs), Operands(Ops),
         FilterBitValues(ParentFilterBitValues), Parent(&parent), BestIndex(-1),
         BitWidth(parent.BitWidth), Emitter(parent.Emitter) {
     doFilter();
   }
 
   FilterChooser(const FilterChooser &) = delete;
   void operator=(const FilterChooser &) = delete;
 
   unsigned getBitWidth() const { return BitWidth; }
 
 protected:
   // Populates the insn given the uid.
   void insnWithID(insn_t &Insn, unsigned Opcode) const {
-    BitsInit &Bits = getBitsField(*AllInstructions[Opcode]->TheDef, "Inst");
+    BitsInit &Bits = getBitsField(*AllInstructions[Opcode].EncodingDef, "Inst");
 
     // 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]->TheDef->getValueAsBitsInit("SoftFail");
+        AllInstructions[Opcode].EncodingDef->getValueAsBitsInit("SoftFail");
 
     for (unsigned i = 0; i < BitWidth; ++i) {
       if (SFBits && bitFromBits(*SFBits, i) == BIT_TRUE)
         Insn.push_back(BIT_UNSET);
       else
         Insn.push_back(bitFromBits(Bits, i));
     }
   }
 
-  // Returns the record name.
-  const StringRef nameWithID(unsigned Opcode) const {
-    return AllInstructions[Opcode]->TheDef->getName();
-  }
-
   // Populates the field of the insn given the start position and the number of
   // consecutive bits to scan for.
   //
   // Returns false if there exists any uninitialized bit value in the range.
   // Returns true, otherwise.
   bool fieldFromInsn(uint64_t &Field, insn_t &Insn, unsigned StartBit,
                      unsigned NumBits) const;
 
   /// dumpFilterArray - dumpFilterArray prints out debugging info for the given
   /// filter array as a series of chars.
   void dumpFilterArray(raw_ostream &o,
                        const std::vector<bit_value_t> & filter) const;
 
   /// dumpStack - dumpStack traverses the filter chooser chain and calls
case MCD::OPC_TryDecode: {
       OS << (unsigned)*p << ", ";
 
       // Decoder index.
       for (; *I >= 128; ++I)
         OS << (unsigned)*I << ", ";
       OS << (unsigned)*I++ << ", ";
 
       if (!IsTry) {
-        OS << "// Opcode: "
-           << NumberedInstructions[Opc]->TheDef->getName() << "\n";
+        OS << "// Opcode: " << NumberedEncodings[Opc] << "\n";
         break;
       }
 
       // Fallthrough for OPC_TryDecode.
 
       // 24-bit numtoskip value.
       uint8_t Byte = *I++;
       uint32_t NumToSkip = Byte;
       OS << (unsigned)Byte << ", ";
       Byte = *I++;
       OS << (unsigned)Byte << ", ";
       NumToSkip |= Byte << 8;
       Byte = *I++;
       OS << utostr(Byte) << ", ";
       NumToSkip |= Byte << 16;
 
-      OS << "// Opcode: "
-         << NumberedInstructions[Opc]->TheDef->getName()
+      OS << "// Opcode: " << NumberedEncodings[Opc]
          << ", skip to: " << ((I - Table.begin()) + NumToSkip) << "\n";
       break;
     }
     case MCD::OPC_SoftFail: {
       ++I;
       OS.indent(Indentation) << "MCD::OPC_SoftFail";
       // Positive mask
       uint64_t Value = 0;
o << "!Bits[" << PredicateNamespace << "::"
       << str.slice(1,str.size()) << "]";
   else
     o << "Bits[" << PredicateNamespace << "::" << str << "]";
 }
 
 bool FilterChooser::emitPredicateMatch(raw_ostream &o, unsigned &Indentation,
                                        unsigned Opc) const {
   ListInit *Predicates =
-    AllInstructions[Opc]->TheDef->getValueAsListInit("Predicates");
+      AllInstructions[Opc].EncodingDef->getValueAsListInit("Predicates");
   bool IsFirstEmission = true;
   for (unsigned i = 0; i < Predicates->size(); ++i) {
     Record *Pred = Predicates->getElementAsRecord(i);
     if (!Pred->getValue("AssemblerMatcherPredicate"))
       continue;
 
     StringRef P = Pred->getValueAsString("AssemblerCondString");
 
for (unsigned i = 0; i < Predicates->size(); ++i) {
     emitSinglePredicateMatch(o, pairs.first, Emitter->PredicateNamespace);
     IsFirstEmission = false;
   }
   return !Predicates->empty();
 }
 
 bool FilterChooser::doesOpcodeNeedPredicate(unsigned Opc) const {
   ListInit *Predicates =
-    AllInstructions[Opc]->TheDef->getValueAsListInit("Predicates");
+      AllInstructions[Opc].EncodingDef->getValueAsListInit("Predicates");
   for (unsigned i = 0; i < Predicates->size(); ++i) {
     Record *Pred = Predicates->getElementAsRecord(i);
     if (!Pred->getValue("AssemblerMatcherPredicate"))
       continue;
 
     StringRef P = Pred->getValueAsString("AssemblerCondString");
 
     if (P.empty())
void FilterChooser::emitPredicateTableEntry(DecoderTableInfo &TableInfo,
   TableInfo.Table.push_back(0);
   TableInfo.Table.push_back(0);
   TableInfo.Table.push_back(0);
 }
 
 void FilterChooser::emitSoftFailTableEntry(DecoderTableInfo &TableInfo,
                                            unsigned Opc) const {
   BitsInit *SFBits =
-    AllInstructions[Opc]->TheDef->getValueAsBitsInit("SoftFail");
+      AllInstructions[Opc].EncodingDef->getValueAsBitsInit("SoftFail");
   if (!SFBits) return;
-  BitsInit *InstBits = AllInstructions[Opc]->TheDef->getValueAsBitsInit("Inst");
+  BitsInit *InstBits =
+      AllInstructions[Opc].EncodingDef->getValueAsBitsInit("Inst");
 
   APInt PositiveMask(BitWidth, 0ULL);
   APInt NegativeMask(BitWidth, 0ULL);
   for (unsigned i = 0; i < BitWidth; ++i) {
     bit_value_t B = bitFromBits(*SFBits, i);
     bit_value_t IB = bitFromBits(*InstBits, i);
 
     if (B != BIT_TRUE) continue;
 
     switch (IB) {
     case BIT_FALSE:
       // The bit is meant to be false, so emit a check to see if it is true.
       PositiveMask.setBit(i);
       break;
     case BIT_TRUE:
       // The bit is meant to be true, so emit a check to see if it is false.
       NegativeMask.setBit(i);
       break;
     default:
       // The bit is not set; this must be an error!
-      StringRef Name = AllInstructions[Opc]->TheDef->getName();
-      errs() << "SoftFail Conflict: bit SoftFail{" << i << "} in " << Name
-             << " is set but Inst{" << i << "} is unset!\n"
+      errs() << "SoftFail Conflict: bit SoftFail{" << i << "} in "
+             << AllInstructions[Opc] << " is set but Inst{" << i
+             << "} is unset!\n"
              << "  - You can only mark a bit as SoftFail if it is fully defined"
              << " (1/0 - not '?') in Inst\n";
       return;
     }
   }
 
   bool NeedPositiveMask = PositiveMask.getBoolValue();
   bool NeedNegativeMask = NegativeMask.getBoolValue();
void FilterChooser::emitTableEntries(DecoderTableInfo &TableInfo) const {
   // conflict set and bail.
 
   // Print out useful conflict information for postmortem analysis.
   errs() << "Decoding Conflict:\n";
 
   dumpStack(errs(), "\t\t");
 
   for (unsigned i = 0; i < Opcodes.size(); ++i) {
-    errs() << '\t' << nameWithID(Opcodes[i]) << " ";
+    errs() << '\t' << Opcodes[i] << " ";
     dumpBits(errs(),
-             getBitsField(*AllInstructions[Opcodes[i]]->TheDef, "Inst"));
+             getBitsField(*AllInstructions[Opcodes[i]].EncodingDef, "Inst"));
     errs() << '\n';
   }
 }
 
 static std::string findOperandDecoderMethod(TypedInit *TI) {
   std::string Decoder;
 
   Record *Record = cast<DefInit>(TI)->getDef();
void FixedLenDecoderEmitter::run(raw_ostream &o) {
   OS << '\n';
   OS << "namespace llvm {\n\n";
 
   emitFieldFromInstruction(OS);
 
   Target.reverseBitsForLittleEndianEncoding();
 
   // Parameterize the decoders based on namespace and instruction width.
-  NumberedInstructions = Target.getInstructionsByEnumValue();
+  const auto &NumberedInstructions = Target.getInstructionsByEnumValue();
+  NumberedEncodings.reserve(NumberedInstructions.size());
+  for (const auto &NumberedInstruction : NumberedInstructions)
+    NumberedEncodings.emplace_back(NumberedInstruction->TheDef, NumberedInstruction);
+
   std::map<std::pair<std::string, unsigned>,
            std::vector<unsigned>> OpcMap;
   std::map<unsigned, std::vector<OperandInfo>> Operands;
 
-  for (unsigned i = 0; i < NumberedInstructions.size(); ++i) {
-    const CodeGenInstruction *Inst = NumberedInstructions[i];
+  for (unsigned i = 0; i < NumberedEncodings.size(); ++i) {
+    const CodeGenInstruction *Inst = NumberedEncodings[i].Inst;
     const Record *Def = Inst->TheDef;
     unsigned Size = Def->getValueAsInt("Size");
     if (Def->getValueAsString("Namespace") == "TargetOpcode" ||
         Def->getValueAsBit("isPseudo") ||
         Def->getValueAsBit("isAsmParserOnly") ||
         Def->getValueAsBit("isCodeGenOnly"))
       continue;
 
     StringRef DecoderNamespace = Def->getValueAsString("DecoderNamespace");
 
     if (Size) {
       if (populateInstruction(Target, *Inst, i, Operands)) {
         OpcMap[std::make_pair(DecoderNamespace, Size)].push_back(i);
       }
     }
   }
 
   DecoderTableInfo TableInfo;
   for (const auto &Opc : OpcMap) {
     // Emit the decoder for this namespace+width combination.
-    FilterChooser FC(NumberedInstructions, Opc.second, Operands,
-                     8*Opc.first.second, this);
+    ArrayRef<const EncodingAndInst> NumberedEncodingsRef(
+        NumberedEncodings.data(), NumberedEncodings.size());
+    FilterChooser FC(NumberedEncodingsRef, Opc.second, Operands,
+                     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
     // decoders to give more opportunities for uniqueing.
     TableInfo.Table.clear();
     TableInfo.FixupStack.clear();
     TableInfo.Table.reserve(16384);
     TableInfo.FixupStack.emplace_back();