Index: llvm/utils/TableGen/CMakeLists.txt =================================================================== --- llvm/utils/TableGen/CMakeLists.txt +++ llvm/utils/TableGen/CMakeLists.txt @@ -1,4 +1,5 @@ add_subdirectory(GlobalISel) +add_subdirectory(DecoderEmitter) set(LLVM_LINK_COMPONENTS Support) @@ -21,7 +22,6 @@ DAGISelMatcherGen.cpp DAGISelMatcherOpt.cpp DAGISelMatcher.cpp - DecoderEmitter.cpp DFAEmitter.cpp DFAPacketizerEmitter.cpp DirectiveEmitter.cpp @@ -60,4 +60,5 @@ CTagsEmitter.cpp ) target_link_libraries(llvm-tblgen PRIVATE LLVMTableGenGlobalISel) +target_link_libraries(llvm-tblgen PRIVATE LLVMTableDecoderEmitter) set_target_properties(llvm-tblgen PROPERTIES FOLDER "Tablegenning") Index: llvm/utils/TableGen/DecoderEmitter.cpp =================================================================== --- llvm/utils/TableGen/DecoderEmitter.cpp +++ /dev/null @@ -1,2705 +0,0 @@ -//===---------------- DecoderEmitter.cpp - Decoder Generator --------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -// It contains the tablegen backend that emits the decoder functions for -// targets with fixed/variable length instruction set. -// -//===----------------------------------------------------------------------===// - -#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" -#include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/SetVector.h" -#include "llvm/ADT/SmallString.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/StringExtras.h" -#include "llvm/ADT/StringRef.h" -#include "llvm/MC/MCDecoderOps.h" -#include "llvm/Support/Casting.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/ErrorHandling.h" -#include "llvm/Support/FormattedStream.h" -#include "llvm/Support/LEB128.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/TableGen/Error.h" -#include "llvm/TableGen/Record.h" -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -using namespace llvm; - -#define DEBUG_TYPE "decoder-emitter" - -namespace { - -STATISTIC(NumEncodings, "Number of encodings considered"); -STATISTIC(NumEncodingsLackingDisasm, "Number of encodings without disassembler info"); -STATISTIC(NumInstructions, "Number of instructions considered"); -STATISTIC(NumEncodingsSupported, "Number of encodings supported"); -STATISTIC(NumEncodingsOmitted, "Number of encodings omitted"); - -struct EncodingField { - unsigned Base, Width, Offset; - EncodingField(unsigned B, unsigned W, unsigned O) - : Base(B), Width(W), Offset(O) { } -}; - -struct OperandInfo { - std::vector Fields; - std::string Decoder; - bool HasCompleteDecoder; - uint64_t InitValue; - - OperandInfo(std::string D, bool HCD) - : Decoder(std::move(D)), HasCompleteDecoder(HCD), InitValue(0) {} - - void addField(unsigned Base, unsigned Width, unsigned Offset) { - Fields.push_back(EncodingField(Base, Width, Offset)); - } - - unsigned numFields() const { return Fields.size(); } - - typedef std::vector::const_iterator const_iterator; - - const_iterator begin() const { return Fields.begin(); } - const_iterator end() const { return Fields.end(); } -}; - -typedef std::vector DecoderTable; -typedef uint32_t DecoderFixup; -typedef std::vector FixupList; -typedef std::vector FixupScopeList; -typedef SmallSetVector PredicateSet; -typedef SmallSetVector DecoderSet; -struct DecoderTableInfo { - DecoderTable Table; - FixupScopeList FixupStack; - PredicateSet Predicates; - DecoderSet Decoders; -}; - -struct EncodingAndInst { - const Record *EncodingDef; - const CodeGenInstruction *Inst; - StringRef HwModeName; - - EncodingAndInst(const Record *EncodingDef, const CodeGenInstruction *Inst, - StringRef HwModeName = "") - : EncodingDef(EncodingDef), Inst(Inst), HwModeName(HwModeName) {} -}; - -struct EncodingIDAndOpcode { - unsigned EncodingID; - unsigned Opcode; - - EncodingIDAndOpcode() : EncodingID(0), Opcode(0) {} - EncodingIDAndOpcode(unsigned EncodingID, unsigned Opcode) - : EncodingID(EncodingID), Opcode(Opcode) {} -}; - -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 DecoderEmitter { - RecordKeeper &RK; - std::vector NumberedEncodings; - -public: - // Defaults preserved here for documentation, even though they aren't - // strictly necessary given the way that this is currently being called. - DecoderEmitter(RecordKeeper &R, std::string PredicateNamespace, - std::string GPrefix = "if (", - std::string GPostfix = " == MCDisassembler::Fail)", - std::string ROK = "MCDisassembler::Success", - std::string RFail = "MCDisassembler::Fail", std::string L = "") - : RK(R), Target(R), PredicateNamespace(std::move(PredicateNamespace)), - GuardPrefix(std::move(GPrefix)), GuardPostfix(std::move(GPostfix)), - ReturnOK(std::move(ROK)), ReturnFail(std::move(RFail)), - Locals(std::move(L)) {} - - // Emit the decoder state machine table. - void emitTable(formatted_raw_ostream &o, DecoderTable &Table, - unsigned Indentation, unsigned BitWidth, - StringRef Namespace) const; - void emitInstrLenTable(formatted_raw_ostream &OS, - std::vector &InstrLen) const; - void emitPredicateFunction(formatted_raw_ostream &OS, - PredicateSet &Predicates, - unsigned Indentation) const; - void emitDecoderFunction(formatted_raw_ostream &OS, - DecoderSet &Decoders, - unsigned Indentation) const; - - // run - Output the code emitter - void run(raw_ostream &o); - -private: - CodeGenTarget Target; - -public: - std::string PredicateNamespace; - std::string GuardPrefix, GuardPostfix; - std::string ReturnOK, ReturnFail; - std::string Locals; -}; - -} // end anonymous namespace - -// The set (BIT_TRUE, BIT_FALSE, BIT_UNSET) represents a ternary logic system -// for a bit value. -// -// BIT_UNFILTERED is used as the init value for a filter position. It is used -// only for filter processings. -typedef enum { - BIT_TRUE, // '1' - BIT_FALSE, // '0' - BIT_UNSET, // '?' - BIT_UNFILTERED // unfiltered -} bit_value_t; - -static bool ValueSet(bit_value_t V) { - return (V == BIT_TRUE || V == BIT_FALSE); -} - -static bool ValueNotSet(bit_value_t V) { - return (V == BIT_UNSET); -} - -static int Value(bit_value_t V) { - return ValueNotSet(V) ? -1 : (V == BIT_FALSE ? 0 : 1); -} - -static bit_value_t bitFromBits(const BitsInit &bits, unsigned index) { - if (BitInit *bit = dyn_cast(bits.getBit(index))) - return bit->getValue() ? BIT_TRUE : BIT_FALSE; - - // The bit is uninitialized. - return BIT_UNSET; -} - -// Prints the bit value for each position. -static void dumpBits(raw_ostream &o, const BitsInit &bits) { - for (unsigned index = bits.getNumBits(); index > 0; --index) { - switch (bitFromBits(bits, index - 1)) { - case BIT_TRUE: - o << "1"; - break; - case BIT_FALSE: - o << "0"; - break; - case BIT_UNSET: - o << "_"; - break; - default: - llvm_unreachable("unexpected return value from bitFromBits"); - } - } -} - -static BitsInit &getBitsField(const Record &def, StringRef str) { - const RecordVal *RV = def.getValue(str); - if (BitsInit *Bits = dyn_cast(RV->getValue())) - return *Bits; - - // variable length instruction - VarLenInst VLI = VarLenInst(cast(RV->getValue()), RV); - SmallVector Bits; - - for (auto &SI : VLI) { - if (const BitsInit *BI = dyn_cast(SI.Value)) { - for (unsigned Idx = 0U; Idx < BI->getNumBits(); ++Idx) { - Bits.push_back(BI->getBit(Idx)); - } - } else if (const BitInit *BI = dyn_cast(SI.Value)) { - Bits.push_back(const_cast(BI)); - } else { - for (unsigned Idx = 0U; Idx < SI.BitWidth; ++Idx) - Bits.push_back(UnsetInit::get(def.getRecords())); - } - } - - return *BitsInit::get(def.getRecords(), Bits); -} - -// Representation of the instruction to work on. -typedef std::vector insn_t; - -namespace { - -static const uint64_t NO_FIXED_SEGMENTS_SENTINEL = -1ULL; - -class FilterChooser; - -/// Filter - Filter works with FilterChooser to produce the decoding tree for -/// the ISA. -/// -/// It is useful to think of a Filter as governing the switch stmts of the -/// decoding tree in a certain level. Each case stmt delegates to an inferior -/// FilterChooser to decide what further decoding logic to employ, or in another -/// words, what other remaining bits to look at. The FilterChooser eventually -/// chooses a best Filter to do its job. -/// -/// This recursive scheme ends when the number of Opcodes assigned to the -/// FilterChooser becomes 1 or if there is a conflict. A conflict happens when -/// the Filter/FilterChooser combo does not know how to distinguish among the -/// Opcodes assigned. -/// -/// An example of a conflict is -/// -/// Conflict: -/// 111101000.00........00010000.... -/// 111101000.00........0001........ -/// 1111010...00........0001........ -/// 1111010...00.................... -/// 1111010......................... -/// 1111............................ -/// ................................ -/// VST4q8a 111101000_00________00010000____ -/// VST4q8b 111101000_00________00010000____ -/// -/// The Debug output shows the path that the decoding tree follows to reach the -/// the conclusion that there is a conflict. VST4q8a is a vst4 to double-spaced -/// even registers, while VST4q8b is a vst4 to double-spaced odd registers. -/// -/// The encoding info in the .td files does not specify this meta information, -/// which could have been used by the decoder to resolve the conflict. The -/// decoder could try to decode the even/odd register numbering and assign to -/// VST4q8a or VST4q8b, but for the time being, the decoder chooses the "a" -/// version and return the Opcode since the two have the same Asm format string. -class Filter { -protected: - const FilterChooser *Owner;// points to the FilterChooser who owns this filter - unsigned StartBit; // the starting bit position - unsigned NumBits; // number of bits to filter - bool Mixed; // a mixed region contains both set and unset bits - - // Map of well-known segment value to the set of uid's with that value. - std::map> - FilteredInstructions; - - // Set of uid's with non-constant segment values. - std::vector VariableInstructions; - - // Map of well-known segment value to its delegate. - std::map> FilterChooserMap; - - // Number of instructions which fall under FilteredInstructions category. - unsigned NumFiltered; - - // Keeps track of the last opcode in the filtered bucket. - EncodingIDAndOpcode LastOpcFiltered; - -public: - Filter(Filter &&f); - Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, bool mixed); - - ~Filter() = default; - - unsigned getNumFiltered() const { return NumFiltered; } - - EncodingIDAndOpcode getSingletonOpc() const { - assert(NumFiltered == 1); - return LastOpcFiltered; - } - - // Return the filter chooser for the group of instructions without constant - // segment values. - const FilterChooser &getVariableFC() const { - assert(NumFiltered == 1); - assert(FilterChooserMap.size() == 1); - return *(FilterChooserMap.find(NO_FIXED_SEGMENTS_SENTINEL)->second); - } - - // Divides the decoding task into sub tasks and delegates them to the - // inferior FilterChooser's. - // - // A special case arises when there's only one entry in the filtered - // instructions. In order to unambiguously decode the singleton, we need to - // match the remaining undecoded encoding bits against the singleton. - void recurse(); - - // Emit table entries to decode instructions given a segment or segments of - // bits. - void emitTableEntry(DecoderTableInfo &TableInfo) const; - - // Returns the number of fanout produced by the filter. More fanout implies - // the filter distinguishes more categories of instructions. - unsigned usefulness() const; -}; // end class Filter - -} // end anonymous namespace - -// These are states of our finite state machines used in FilterChooser's -// filterProcessor() which produces the filter candidates to use. -typedef enum { - ATTR_NONE, - ATTR_FILTERED, - ATTR_ALL_SET, - ATTR_ALL_UNSET, - ATTR_MIXED -} bitAttr_t; - -/// FilterChooser - FilterChooser chooses the best filter among a set of Filters -/// in order to perform the decoding of instructions at the current level. -/// -/// Decoding proceeds from the top down. Based on the well-known encoding bits -/// of instructions available, FilterChooser builds up the possible Filters that -/// can further the task of decoding by distinguishing among the remaining -/// candidate instructions. -/// -/// Once a filter has been chosen, it is called upon to divide the decoding task -/// into sub-tasks and delegates them to its inferior FilterChoosers for further -/// processings. -/// -/// It is useful to think of a Filter as governing the switch stmts of the -/// decoding tree. And each case is delegated to an inferior FilterChooser to -/// decide what further remaining bits to look at. -namespace { - -class FilterChooser { -protected: - friend class Filter; - - // Vector of codegen instructions to choose our filter. - ArrayRef AllInstructions; - - // Vector of uid's for this filter chooser to work on. - // The first member of the pair is the opcode id being decoded, the second is - // the opcode id that should be emitted. - const std::vector &Opcodes; - - // Lookup table for the operand decoding of instructions. - const std::map> &Operands; - - // Vector of candidate filters. - std::vector Filters; - - // Array of bit values passed down from our parent. - // Set to all BIT_UNFILTERED's for Parent == NULL. - std::vector FilterBitValues; - - // Links to the FilterChooser above us in the decoding tree. - const FilterChooser *Parent; - - // Index of the best filter from Filters. - int BestIndex; - - // Width of instructions - unsigned BitWidth; - - // Parent emitter - const DecoderEmitter *Emitter; - -public: - FilterChooser(ArrayRef Insts, - const std::vector &IDs, - const std::map> &Ops, - unsigned BW, const DecoderEmitter *E) - : AllInstructions(Insts), Opcodes(IDs), Operands(Ops), - FilterBitValues(BW, BIT_UNFILTERED), Parent(nullptr), BestIndex(-1), - BitWidth(BW), Emitter(E) { - doFilter(); - } - - FilterChooser(ArrayRef Insts, - const std::vector &IDs, - const std::map> &Ops, - const std::vector &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].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. - const RecordVal *RV = - AllInstructions[Opcode].EncodingDef->getValue("SoftFail"); - const BitsInit *SFBits = RV ? dyn_cast(RV->getValue()) : nullptr; - for (unsigned i = 0; i < Bits.getNumBits(); ++i) { - if (SFBits && bitFromBits(*SFBits, i) == BIT_TRUE) - Insn[i] = BIT_UNSET; - else - Insn[i] = bitFromBits(Bits, i); - } - } - - // Emit the name of the encoding/instruction pair. - void emitNameWithID(raw_ostream &OS, unsigned Opcode) const { - const Record *EncodingDef = AllInstructions[Opcode].EncodingDef; - const Record *InstDef = AllInstructions[Opcode].Inst->TheDef; - if (EncodingDef != InstDef) - OS << EncodingDef->getName() << ":"; - OS << InstDef->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 & filter) const; - - /// dumpStack - dumpStack traverses the filter chooser chain and calls - /// dumpFilterArray on each filter chooser up to the top level one. - void dumpStack(raw_ostream &o, const char *prefix) const; - - Filter &bestFilter() { - assert(BestIndex != -1 && "BestIndex not set"); - return Filters[BestIndex]; - } - - bool PositionFiltered(unsigned i) const { - return ValueSet(FilterBitValues[i]); - } - - // Calculates the island(s) needed to decode the instruction. - // This returns a lit of undecoded bits of an instructions, for example, - // Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be - // decoded bits in order to verify that the instruction matches the Opcode. - unsigned getIslands(std::vector &StartBits, - std::vector &EndBits, - std::vector &FieldVals, - const insn_t &Insn) const; - - // Emits code to check the Predicates member of an instruction are true. - // Returns true if predicate matches were emitted, false otherwise. - bool emitPredicateMatch(raw_ostream &o, unsigned &Indentation, - unsigned Opc) const; - bool emitPredicateMatchAux(const Init &Val, bool ParenIfBinOp, - raw_ostream &OS) const; - - bool doesOpcodeNeedPredicate(unsigned Opc) const; - unsigned getPredicateIndex(DecoderTableInfo &TableInfo, StringRef P) const; - void emitPredicateTableEntry(DecoderTableInfo &TableInfo, - unsigned Opc) const; - - void emitSoftFailTableEntry(DecoderTableInfo &TableInfo, - unsigned Opc) const; - - // Emits table entries to decode the singleton. - void emitSingletonTableEntry(DecoderTableInfo &TableInfo, - EncodingIDAndOpcode Opc) const; - - // Emits code to decode the singleton, and then to decode the rest. - void emitSingletonTableEntry(DecoderTableInfo &TableInfo, - const Filter &Best) const; - - void emitBinaryParser(raw_ostream &o, unsigned &Indentation, - const OperandInfo &OpInfo, - bool &OpHasCompleteDecoder) const; - - void emitDecoder(raw_ostream &OS, unsigned Indentation, unsigned Opc, - bool &HasCompleteDecoder) const; - unsigned getDecoderIndex(DecoderSet &Decoders, unsigned Opc, - bool &HasCompleteDecoder) const; - - // Assign a single filter and run with it. - void runSingleFilter(unsigned startBit, unsigned numBit, bool mixed); - - // reportRegion is a helper function for filterProcessor to mark a region as - // eligible for use as a filter region. - void reportRegion(bitAttr_t RA, unsigned StartBit, unsigned BitIndex, - bool AllowMixed); - - // FilterProcessor scans the well-known encoding bits of the instructions and - // builds up a list of candidate filters. It chooses the best filter and - // recursively descends down the decoding tree. - bool filterProcessor(bool AllowMixed, bool Greedy = true); - - // Decides on the best configuration of filter(s) to use in order to decode - // the instructions. A conflict of instructions may occur, in which case we - // dump the conflict set to the standard error. - void doFilter(); - -public: - // emitTableEntries - Emit state machine entries to decode our share of - // instructions. - void emitTableEntries(DecoderTableInfo &TableInfo) const; -}; - -} // end anonymous namespace - -/////////////////////////// -// // -// Filter Implementation // -// // -/////////////////////////// - -Filter::Filter(Filter &&f) - : Owner(f.Owner), StartBit(f.StartBit), NumBits(f.NumBits), Mixed(f.Mixed), - FilteredInstructions(std::move(f.FilteredInstructions)), - VariableInstructions(std::move(f.VariableInstructions)), - FilterChooserMap(std::move(f.FilterChooserMap)), NumFiltered(f.NumFiltered), - LastOpcFiltered(f.LastOpcFiltered) { -} - -Filter::Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, - bool mixed) - : Owner(&owner), StartBit(startBit), NumBits(numBits), Mixed(mixed) { - assert(StartBit + NumBits - 1 < Owner->BitWidth); - - NumFiltered = 0; - LastOpcFiltered = {0, 0}; - - for (unsigned i = 0, e = Owner->Opcodes.size(); i != e; ++i) { - insn_t Insn; - - // Populates the insn given the uid. - Owner->insnWithID(Insn, Owner->Opcodes[i].EncodingID); - - uint64_t Field; - // Scans the segment for possibly well-specified encoding bits. - bool ok = Owner->fieldFromInsn(Field, Insn, StartBit, NumBits); - - if (ok) { - // The encoding bits are well-known. Lets add the uid of the - // instruction into the bucket keyed off the constant field value. - LastOpcFiltered = Owner->Opcodes[i]; - FilteredInstructions[Field].push_back(LastOpcFiltered); - ++NumFiltered; - } else { - // Some of the encoding bit(s) are unspecified. This contributes to - // one additional member of "Variable" instructions. - VariableInstructions.push_back(Owner->Opcodes[i]); - } - } - - assert((FilteredInstructions.size() + VariableInstructions.size() > 0) - && "Filter returns no instruction categories"); -} - -// Divides the decoding task into sub tasks and delegates them to the -// inferior FilterChooser's. -// -// A special case arises when there's only one entry in the filtered -// instructions. In order to unambiguously decode the singleton, we need to -// match the remaining undecoded encoding bits against the singleton. -void Filter::recurse() { - // Starts by inheriting our parent filter chooser's filter bit values. - std::vector BitValueArray(Owner->FilterBitValues); - - if (!VariableInstructions.empty()) { - // Conservatively marks each segment position as BIT_UNSET. - for (unsigned bitIndex = 0; bitIndex < NumBits; ++bitIndex) - BitValueArray[StartBit + bitIndex] = BIT_UNSET; - - // Delegates to an inferior filter chooser for further processing on this - // group of instructions whose segment values are variable. - FilterChooserMap.insert(std::make_pair(NO_FIXED_SEGMENTS_SENTINEL, - std::make_unique(Owner->AllInstructions, - VariableInstructions, Owner->Operands, BitValueArray, *Owner))); - } - - // No need to recurse for a singleton filtered instruction. - // See also Filter::emit*(). - if (getNumFiltered() == 1) { - assert(FilterChooserMap.size() == 1); - return; - } - - // Otherwise, create sub choosers. - for (const auto &Inst : FilteredInstructions) { - - // Marks all the segment positions with either BIT_TRUE or BIT_FALSE. - for (unsigned bitIndex = 0; bitIndex < NumBits; ++bitIndex) { - if (Inst.first & (1ULL << bitIndex)) - BitValueArray[StartBit + bitIndex] = BIT_TRUE; - else - BitValueArray[StartBit + bitIndex] = BIT_FALSE; - } - - // Delegates to an inferior filter chooser for further processing on this - // category of instructions. - FilterChooserMap.insert(std::make_pair( - Inst.first, std::make_unique( - Owner->AllInstructions, Inst.second, - Owner->Operands, BitValueArray, *Owner))); - } -} - -static void resolveTableFixups(DecoderTable &Table, const FixupList &Fixups, - uint32_t DestIdx) { - // Any NumToSkip fixups in the current scope can resolve to the - // current location. - for (FixupList::const_reverse_iterator I = Fixups.rbegin(), - E = Fixups.rend(); - I != E; ++I) { - // Calculate the distance from the byte following the fixup entry byte - // to the destination. The Target is calculated from after the 16-bit - // NumToSkip entry itself, so subtract two from the displacement here - // to account for that. - uint32_t FixupIdx = *I; - uint32_t Delta = DestIdx - FixupIdx - 3; - // Our NumToSkip entries are 24-bits. Make sure our table isn't too - // big. - assert(Delta < (1u << 24)); - Table[FixupIdx] = (uint8_t)Delta; - Table[FixupIdx + 1] = (uint8_t)(Delta >> 8); - Table[FixupIdx + 2] = (uint8_t)(Delta >> 16); - } -} - -// Emit table entries to decode instructions given a segment or segments -// of bits. -void Filter::emitTableEntry(DecoderTableInfo &TableInfo) const { - TableInfo.Table.push_back(MCD::OPC_ExtractField); - TableInfo.Table.push_back(StartBit); - TableInfo.Table.push_back(NumBits); - - // A new filter entry begins a new scope for fixup resolution. - TableInfo.FixupStack.emplace_back(); - - DecoderTable &Table = TableInfo.Table; - - size_t PrevFilter = 0; - bool HasFallthrough = false; - for (auto &Filter : FilterChooserMap) { - // Field value -1 implies a non-empty set of variable instructions. - // See also recurse(). - if (Filter.first == NO_FIXED_SEGMENTS_SENTINEL) { - HasFallthrough = true; - - // Each scope should always have at least one filter value to check - // for. - assert(PrevFilter != 0 && "empty filter set!"); - FixupList &CurScope = TableInfo.FixupStack.back(); - // Resolve any NumToSkip fixups in the current scope. - resolveTableFixups(Table, CurScope, Table.size()); - CurScope.clear(); - PrevFilter = 0; // Don't re-process the filter's fallthrough. - } else { - Table.push_back(MCD::OPC_FilterValue); - // Encode and emit the value to filter against. - uint8_t Buffer[16]; - unsigned Len = encodeULEB128(Filter.first, Buffer); - Table.insert(Table.end(), Buffer, Buffer + Len); - // Reserve space for the NumToSkip entry. We'll backpatch the value - // later. - PrevFilter = Table.size(); - Table.push_back(0); - Table.push_back(0); - Table.push_back(0); - } - - // We arrive at a category of instructions with the same segment value. - // Now delegate to the sub filter chooser for further decodings. - // The case may fallthrough, which happens if the remaining well-known - // encoding bits do not match exactly. - Filter.second->emitTableEntries(TableInfo); - - // Now that we've emitted the body of the handler, update the NumToSkip - // of the filter itself to be able to skip forward when false. Subtract - // two as to account for the width of the NumToSkip field itself. - if (PrevFilter) { - uint32_t NumToSkip = Table.size() - PrevFilter - 3; - assert(NumToSkip < (1u << 24) && "disassembler decoding table too large!"); - Table[PrevFilter] = (uint8_t)NumToSkip; - Table[PrevFilter + 1] = (uint8_t)(NumToSkip >> 8); - Table[PrevFilter + 2] = (uint8_t)(NumToSkip >> 16); - } - } - - // Any remaining unresolved fixups bubble up to the parent fixup scope. - assert(TableInfo.FixupStack.size() > 1 && "fixup stack underflow!"); - FixupScopeList::iterator Source = TableInfo.FixupStack.end() - 1; - FixupScopeList::iterator Dest = Source - 1; - llvm::append_range(*Dest, *Source); - TableInfo.FixupStack.pop_back(); - - // If there is no fallthrough, then the final filter should get fixed - // up according to the enclosing scope rather than the current position. - if (!HasFallthrough) - TableInfo.FixupStack.back().push_back(PrevFilter); -} - -// Returns the number of fanout produced by the filter. More fanout implies -// the filter distinguishes more categories of instructions. -unsigned Filter::usefulness() const { - if (!VariableInstructions.empty()) - return FilteredInstructions.size(); - else - return FilteredInstructions.size() + 1; -} - -////////////////////////////////// -// // -// Filterchooser Implementation // -// // -////////////////////////////////// - -// Emit the decoder state machine table. -void DecoderEmitter::emitTable(formatted_raw_ostream &OS, DecoderTable &Table, - unsigned Indentation, unsigned BitWidth, - StringRef Namespace) const { - OS.indent(Indentation) << "static const uint8_t DecoderTable" << Namespace - << BitWidth << "[] = {\n"; - - Indentation += 2; - - // FIXME: We may be able to use the NumToSkip values to recover - // appropriate indentation levels. - DecoderTable::const_iterator I = Table.begin(); - DecoderTable::const_iterator E = Table.end(); - while (I != E) { - assert (I < E && "incomplete decode table entry!"); - - uint64_t Pos = I - Table.begin(); - OS << "/* " << Pos << " */"; - OS.PadToColumn(12); - - switch (*I) { - default: - PrintFatalError("invalid decode table opcode"); - case MCD::OPC_ExtractField: { - ++I; - unsigned Start = *I++; - unsigned Len = *I++; - OS.indent(Indentation) << "MCD::OPC_ExtractField, " << Start << ", " - << Len << ", // Inst{"; - if (Len > 1) - OS << (Start + Len - 1) << "-"; - OS << Start << "} ...\n"; - break; - } - case MCD::OPC_FilterValue: { - ++I; - OS.indent(Indentation) << "MCD::OPC_FilterValue, "; - // The filter value is ULEB128 encoded. - while (*I >= 128) - OS << (unsigned)*I++ << ", "; - OS << (unsigned)*I++ << ", "; - - // 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 << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; - break; - } - case MCD::OPC_CheckField: { - ++I; - unsigned Start = *I++; - unsigned Len = *I++; - OS.indent(Indentation) << "MCD::OPC_CheckField, " << Start << ", " - << Len << ", ";// << Val << ", " << NumToSkip << ",\n"; - // ULEB128 encoded field value. - for (; *I >= 128; ++I) - OS << (unsigned)*I << ", "; - OS << (unsigned)*I++ << ", "; - // 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 << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; - break; - } - case MCD::OPC_CheckPredicate: { - ++I; - OS.indent(Indentation) << "MCD::OPC_CheckPredicate, "; - for (; *I >= 128; ++I) - OS << (unsigned)*I << ", "; - OS << (unsigned)*I++ << ", "; - - // 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 << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; - break; - } - case MCD::OPC_Decode: - case MCD::OPC_TryDecode: { - bool IsTry = *I == MCD::OPC_TryDecode; - ++I; - // Extract the ULEB128 encoded Opcode to a buffer. - uint8_t Buffer[16], *p = Buffer; - while ((*p++ = *I++) >= 128) - assert((p - Buffer) <= (ptrdiff_t)sizeof(Buffer) - && "ULEB128 value too large!"); - // Decode the Opcode value. - unsigned Opc = decodeULEB128(Buffer); - OS.indent(Indentation) << "MCD::OPC_" << (IsTry ? "Try" : "") - << "Decode, "; - for (p = Buffer; *p >= 128; ++p) - OS << (unsigned)*p << ", "; - OS << (unsigned)*p << ", "; - - // Decoder index. - for (; *I >= 128; ++I) - OS << (unsigned)*I << ", "; - OS << (unsigned)*I++ << ", "; - - if (!IsTry) { - 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: " << 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; - unsigned Shift = 0; - do { - OS << ", " << (unsigned)*I; - Value += (*I & 0x7f) << Shift; - Shift += 7; - } while (*I++ >= 128); - if (Value > 127) { - OS << " /* 0x"; - OS.write_hex(Value); - OS << " */"; - } - // Negative mask - Value = 0; - Shift = 0; - do { - OS << ", " << (unsigned)*I; - Value += (*I & 0x7f) << Shift; - Shift += 7; - } while (*I++ >= 128); - if (Value > 127) { - OS << " /* 0x"; - OS.write_hex(Value); - OS << " */"; - } - OS << ",\n"; - break; - } - case MCD::OPC_Fail: { - ++I; - OS.indent(Indentation) << "MCD::OPC_Fail,\n"; - break; - } - } - } - OS.indent(Indentation) << "0\n"; - - Indentation -= 2; - - OS.indent(Indentation) << "};\n\n"; -} - -void DecoderEmitter::emitInstrLenTable(formatted_raw_ostream &OS, - std::vector &InstrLen) const { - OS << "static const uint8_t InstrLenTable[] = {\n"; - for (unsigned &Len : InstrLen) { - OS << Len << ",\n"; - } - OS << "};\n\n"; -} - -void DecoderEmitter::emitPredicateFunction(formatted_raw_ostream &OS, - PredicateSet &Predicates, - unsigned Indentation) const { - // The predicate function is just a big switch statement based on the - // input predicate index. - OS.indent(Indentation) << "static bool checkDecoderPredicate(unsigned Idx, " - << "const FeatureBitset &Bits) {\n"; - Indentation += 2; - if (!Predicates.empty()) { - OS.indent(Indentation) << "switch (Idx) {\n"; - OS.indent(Indentation) << "default: llvm_unreachable(\"Invalid index!\");\n"; - unsigned Index = 0; - for (const auto &Predicate : Predicates) { - OS.indent(Indentation) << "case " << Index++ << ":\n"; - OS.indent(Indentation+2) << "return (" << Predicate << ");\n"; - } - OS.indent(Indentation) << "}\n"; - } else { - // No case statement to emit - OS.indent(Indentation) << "llvm_unreachable(\"Invalid index!\");\n"; - } - Indentation -= 2; - OS.indent(Indentation) << "}\n\n"; -} - -void DecoderEmitter::emitDecoderFunction(formatted_raw_ostream &OS, - DecoderSet &Decoders, - unsigned Indentation) const { - // The decoder function is just a big switch statement based on the - // input decoder index. - OS.indent(Indentation) << "template \n"; - OS.indent(Indentation) << "static DecodeStatus decodeToMCInst(DecodeStatus S," - << " unsigned Idx, InsnType insn, MCInst &MI,\n"; - OS.indent(Indentation) - << " uint64_t " - << "Address, const MCDisassembler *Decoder, bool &DecodeComplete) {\n"; - Indentation += 2; - OS.indent(Indentation) << "DecodeComplete = true;\n"; - // TODO: When InsnType is large, using uint64_t limits all fields to 64 bits - // It would be better for emitBinaryParser to use a 64-bit tmp whenever - // possible but fall back to an InsnType-sized tmp for truly large fields. - OS.indent(Indentation) << "using TmpType = " - "std::conditional_t::" - "value, InsnType, uint64_t>;\n"; - OS.indent(Indentation) << "TmpType tmp;\n"; - OS.indent(Indentation) << "switch (Idx) {\n"; - OS.indent(Indentation) << "default: llvm_unreachable(\"Invalid index!\");\n"; - unsigned Index = 0; - for (const auto &Decoder : Decoders) { - OS.indent(Indentation) << "case " << Index++ << ":\n"; - OS << Decoder; - OS.indent(Indentation+2) << "return S;\n"; - } - OS.indent(Indentation) << "}\n"; - Indentation -= 2; - OS.indent(Indentation) << "}\n\n"; -} - -// Populates the field of the insn given the start position and the number of -// consecutive bits to scan for. -// -// Returns false if and on the first uninitialized bit value encountered. -// Returns true, otherwise. -bool FilterChooser::fieldFromInsn(uint64_t &Field, insn_t &Insn, - unsigned StartBit, unsigned NumBits) const { - Field = 0; - - for (unsigned i = 0; i < NumBits; ++i) { - if (Insn[StartBit + i] == BIT_UNSET) - return false; - - if (Insn[StartBit + i] == BIT_TRUE) - Field = Field | (1ULL << i); - } - - return true; -} - -/// dumpFilterArray - dumpFilterArray prints out debugging info for the given -/// filter array as a series of chars. -void FilterChooser::dumpFilterArray(raw_ostream &o, - const std::vector &filter) const { - for (unsigned bitIndex = BitWidth; bitIndex > 0; bitIndex--) { - switch (filter[bitIndex - 1]) { - case BIT_UNFILTERED: - o << "."; - break; - case BIT_UNSET: - o << "_"; - break; - case BIT_TRUE: - o << "1"; - break; - case BIT_FALSE: - o << "0"; - break; - } - } -} - -/// dumpStack - dumpStack traverses the filter chooser chain and calls -/// dumpFilterArray on each filter chooser up to the top level one. -void FilterChooser::dumpStack(raw_ostream &o, const char *prefix) const { - const FilterChooser *current = this; - - while (current) { - o << prefix; - dumpFilterArray(o, current->FilterBitValues); - o << '\n'; - current = current->Parent; - } -} - -// Calculates the island(s) needed to decode the instruction. -// This returns a list of undecoded bits of an instructions, for example, -// Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be -// decoded bits in order to verify that the instruction matches the Opcode. -unsigned FilterChooser::getIslands(std::vector &StartBits, - std::vector &EndBits, - std::vector &FieldVals, - const insn_t &Insn) const { - unsigned Num, BitNo; - Num = BitNo = 0; - - uint64_t FieldVal = 0; - - // 0: Init - // 1: Water (the bit value does not affect decoding) - // 2: Island (well-known bit value needed for decoding) - int State = 0; - - for (unsigned i = 0; i < BitWidth; ++i) { - int64_t Val = Value(Insn[i]); - bool Filtered = PositionFiltered(i); - switch (State) { - default: llvm_unreachable("Unreachable code!"); - case 0: - case 1: - if (Filtered || Val == -1) - State = 1; // Still in Water - else { - State = 2; // Into the Island - BitNo = 0; - StartBits.push_back(i); - FieldVal = Val; - } - break; - case 2: - if (Filtered || Val == -1) { - State = 1; // Into the Water - EndBits.push_back(i - 1); - FieldVals.push_back(FieldVal); - ++Num; - } else { - State = 2; // Still in Island - ++BitNo; - FieldVal = FieldVal | Val << BitNo; - } - break; - } - } - // If we are still in Island after the loop, do some housekeeping. - if (State == 2) { - EndBits.push_back(BitWidth - 1); - FieldVals.push_back(FieldVal); - ++Num; - } - - assert(StartBits.size() == Num && EndBits.size() == Num && - FieldVals.size() == Num); - return Num; -} - -void FilterChooser::emitBinaryParser(raw_ostream &o, unsigned &Indentation, - const OperandInfo &OpInfo, - bool &OpHasCompleteDecoder) const { - const std::string &Decoder = OpInfo.Decoder; - - bool UseInsertBits = OpInfo.numFields() != 1 || OpInfo.InitValue != 0; - - if (UseInsertBits) { - o.indent(Indentation) << "tmp = 0x"; - o.write_hex(OpInfo.InitValue); - o << ";\n"; - } - - for (const EncodingField &EF : OpInfo) { - o.indent(Indentation); - if (UseInsertBits) - o << "insertBits(tmp, "; - else - o << "tmp = "; - o << "fieldFromInstruction(insn, " << EF.Base << ", " << EF.Width << ')'; - if (UseInsertBits) - o << ", " << EF.Offset << ", " << EF.Width << ')'; - else if (EF.Offset != 0) - o << " << " << EF.Offset; - o << ";\n"; - } - - if (Decoder != "") { - OpHasCompleteDecoder = OpInfo.HasCompleteDecoder; - o.indent(Indentation) << Emitter->GuardPrefix << Decoder - << "(MI, tmp, Address, Decoder)" - << Emitter->GuardPostfix - << " { " << (OpHasCompleteDecoder ? "" : "DecodeComplete = false; ") - << "return MCDisassembler::Fail; }\n"; - } else { - OpHasCompleteDecoder = true; - o.indent(Indentation) << "MI.addOperand(MCOperand::createImm(tmp));\n"; - } -} - -void FilterChooser::emitDecoder(raw_ostream &OS, unsigned Indentation, - unsigned Opc, bool &HasCompleteDecoder) const { - HasCompleteDecoder = true; - - for (const auto &Op : Operands.find(Opc)->second) { - // If a custom instruction decoder was specified, use that. - if (Op.numFields() == 0 && !Op.Decoder.empty()) { - HasCompleteDecoder = Op.HasCompleteDecoder; - OS.indent(Indentation) << Emitter->GuardPrefix << Op.Decoder - << "(MI, insn, Address, Decoder)" - << Emitter->GuardPostfix - << " { " << (HasCompleteDecoder ? "" : "DecodeComplete = false; ") - << "return MCDisassembler::Fail; }\n"; - break; - } - - bool OpHasCompleteDecoder; - emitBinaryParser(OS, Indentation, Op, OpHasCompleteDecoder); - if (!OpHasCompleteDecoder) - HasCompleteDecoder = false; - } -} - -unsigned FilterChooser::getDecoderIndex(DecoderSet &Decoders, - unsigned Opc, - bool &HasCompleteDecoder) const { - // Build up the predicate string. - SmallString<256> Decoder; - // FIXME: emitDecoder() function can take a buffer directly rather than - // a stream. - raw_svector_ostream S(Decoder); - unsigned I = 4; - emitDecoder(S, I, Opc, HasCompleteDecoder); - - // Using the full decoder string as the key value here is a bit - // heavyweight, but is effective. If the string comparisons become a - // performance concern, we can implement a mangling of the predicate - // data easily enough with a map back to the actual string. That's - // overkill for now, though. - - // Make sure the predicate is in the table. - Decoders.insert(CachedHashString(Decoder)); - // Now figure out the index for when we write out the table. - DecoderSet::const_iterator P = find(Decoders, Decoder.str()); - return (unsigned)(P - Decoders.begin()); -} - -// If ParenIfBinOp is true, print a surrounding () if Val uses && or ||. -bool FilterChooser::emitPredicateMatchAux(const Init &Val, bool ParenIfBinOp, - raw_ostream &OS) const { - if (auto *D = dyn_cast(&Val)) { - if (!D->getDef()->isSubClassOf("SubtargetFeature")) - return true; - OS << "Bits[" << Emitter->PredicateNamespace << "::" << D->getAsString() - << "]"; - return false; - } - if (auto *D = dyn_cast(&Val)) { - std::string Op = D->getOperator()->getAsString(); - if (Op == "not" && D->getNumArgs() == 1) { - OS << '!'; - return emitPredicateMatchAux(*D->getArg(0), true, OS); - } - if ((Op == "any_of" || Op == "all_of") && D->getNumArgs() > 0) { - bool Paren = D->getNumArgs() > 1 && std::exchange(ParenIfBinOp, true); - if (Paren) - OS << '('; - ListSeparator LS(Op == "any_of" ? " || " : " && "); - for (auto *Arg : D->getArgs()) { - OS << LS; - if (emitPredicateMatchAux(*Arg, ParenIfBinOp, OS)) - return true; - } - if (Paren) - OS << ')'; - return false; - } - } - return true; -} - -bool FilterChooser::emitPredicateMatch(raw_ostream &o, unsigned &Indentation, - unsigned Opc) const { - ListInit *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; - - if (!isa(Pred->getValue("AssemblerCondDag")->getValue())) - continue; - - if (!IsFirstEmission) - o << " && "; - if (emitPredicateMatchAux(*Pred->getValueAsDag("AssemblerCondDag"), - Predicates->size() > 1, o)) - PrintFatalError(Pred->getLoc(), "Invalid AssemblerCondDag!"); - IsFirstEmission = false; - } - return !Predicates->empty(); -} - -bool FilterChooser::doesOpcodeNeedPredicate(unsigned Opc) const { - ListInit *Predicates = - AllInstructions[Opc].EncodingDef->getValueAsListInit("Predicates"); - for (unsigned i = 0; i < Predicates->size(); ++i) { - Record *Pred = Predicates->getElementAsRecord(i); - if (!Pred->getValue("AssemblerMatcherPredicate")) - continue; - - if (isa(Pred->getValue("AssemblerCondDag")->getValue())) - return true; - } - return false; -} - -unsigned FilterChooser::getPredicateIndex(DecoderTableInfo &TableInfo, - StringRef Predicate) const { - // Using the full predicate string as the key value here is a bit - // heavyweight, but is effective. If the string comparisons become a - // performance concern, we can implement a mangling of the predicate - // data easily enough with a map back to the actual string. That's - // overkill for now, though. - - // Make sure the predicate is in the table. - TableInfo.Predicates.insert(CachedHashString(Predicate)); - // Now figure out the index for when we write out the table. - PredicateSet::const_iterator P = find(TableInfo.Predicates, Predicate); - return (unsigned)(P - TableInfo.Predicates.begin()); -} - -void FilterChooser::emitPredicateTableEntry(DecoderTableInfo &TableInfo, - unsigned Opc) const { - if (!doesOpcodeNeedPredicate(Opc)) - return; - - // Build up the predicate string. - SmallString<256> Predicate; - // FIXME: emitPredicateMatch() functions can take a buffer directly rather - // than a stream. - raw_svector_ostream PS(Predicate); - unsigned I = 0; - emitPredicateMatch(PS, I, Opc); - - // Figure out the index into the predicate table for the predicate just - // computed. - unsigned PIdx = getPredicateIndex(TableInfo, PS.str()); - SmallString<16> PBytes; - raw_svector_ostream S(PBytes); - encodeULEB128(PIdx, S); - - TableInfo.Table.push_back(MCD::OPC_CheckPredicate); - // Predicate index - for (unsigned i = 0, e = PBytes.size(); i != e; ++i) - TableInfo.Table.push_back(PBytes[i]); - // Push location for NumToSkip backpatching. - TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); - TableInfo.Table.push_back(0); - TableInfo.Table.push_back(0); - TableInfo.Table.push_back(0); -} - -void FilterChooser::emitSoftFailTableEntry(DecoderTableInfo &TableInfo, - unsigned Opc) const { - const RecordVal *RV = AllInstructions[Opc].EncodingDef->getValue("SoftFail"); - BitsInit *SFBits = RV ? dyn_cast(RV->getValue()) : nullptr; - - if (!SFBits) return; - 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! - 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(); - - if (!NeedPositiveMask && !NeedNegativeMask) - return; - - TableInfo.Table.push_back(MCD::OPC_SoftFail); - - SmallString<16> MaskBytes; - raw_svector_ostream S(MaskBytes); - if (NeedPositiveMask) { - encodeULEB128(PositiveMask.getZExtValue(), S); - for (unsigned i = 0, e = MaskBytes.size(); i != e; ++i) - TableInfo.Table.push_back(MaskBytes[i]); - } else - TableInfo.Table.push_back(0); - if (NeedNegativeMask) { - MaskBytes.clear(); - encodeULEB128(NegativeMask.getZExtValue(), S); - for (unsigned i = 0, e = MaskBytes.size(); i != e; ++i) - TableInfo.Table.push_back(MaskBytes[i]); - } else - TableInfo.Table.push_back(0); -} - -// Emits table entries to decode the singleton. -void FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo, - EncodingIDAndOpcode Opc) const { - std::vector StartBits; - std::vector EndBits; - std::vector FieldVals; - insn_t Insn; - insnWithID(Insn, Opc.EncodingID); - - // Look for islands of undecoded bits of the singleton. - getIslands(StartBits, EndBits, FieldVals, Insn); - - unsigned Size = StartBits.size(); - - // Emit the predicate table entry if one is needed. - emitPredicateTableEntry(TableInfo, Opc.EncodingID); - - // Check any additional encoding fields needed. - for (unsigned I = Size; I != 0; --I) { - unsigned NumBits = EndBits[I-1] - StartBits[I-1] + 1; - TableInfo.Table.push_back(MCD::OPC_CheckField); - TableInfo.Table.push_back(StartBits[I-1]); - TableInfo.Table.push_back(NumBits); - uint8_t Buffer[16], *p; - encodeULEB128(FieldVals[I-1], Buffer); - for (p = Buffer; *p >= 128 ; ++p) - TableInfo.Table.push_back(*p); - TableInfo.Table.push_back(*p); - // Push location for NumToSkip backpatching. - TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); - // The fixup is always 24-bits, so go ahead and allocate the space - // in the table so all our relative position calculations work OK even - // before we fully resolve the real value here. - TableInfo.Table.push_back(0); - TableInfo.Table.push_back(0); - TableInfo.Table.push_back(0); - } - - // Check for soft failure of the match. - emitSoftFailTableEntry(TableInfo, Opc.EncodingID); - - bool HasCompleteDecoder; - unsigned DIdx = - getDecoderIndex(TableInfo.Decoders, Opc.EncodingID, HasCompleteDecoder); - - // Produce OPC_Decode or OPC_TryDecode opcode based on the information - // whether the instruction decoder is complete or not. If it is complete - // then it handles all possible values of remaining variable/unfiltered bits - // and for any value can determine if the bitpattern is a valid instruction - // or not. This means OPC_Decode will be the final step in the decoding - // process. If it is not complete, then the Fail return code from the - // decoder method indicates that additional processing should be done to see - // if there is any other instruction that also matches the bitpattern and - // can decode it. - TableInfo.Table.push_back(HasCompleteDecoder ? MCD::OPC_Decode : - MCD::OPC_TryDecode); - NumEncodingsSupported++; - uint8_t Buffer[16], *p; - encodeULEB128(Opc.Opcode, Buffer); - for (p = Buffer; *p >= 128 ; ++p) - TableInfo.Table.push_back(*p); - TableInfo.Table.push_back(*p); - - SmallString<16> Bytes; - raw_svector_ostream S(Bytes); - encodeULEB128(DIdx, S); - - // Decoder index - for (unsigned i = 0, e = Bytes.size(); i != e; ++i) - TableInfo.Table.push_back(Bytes[i]); - - if (!HasCompleteDecoder) { - // Push location for NumToSkip backpatching. - TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); - // Allocate the space for the fixup. - TableInfo.Table.push_back(0); - TableInfo.Table.push_back(0); - TableInfo.Table.push_back(0); - } -} - -// Emits table entries to decode the singleton, and then to decode the rest. -void FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo, - const Filter &Best) const { - EncodingIDAndOpcode Opc = Best.getSingletonOpc(); - - // complex singletons need predicate checks from the first singleton - // to refer forward to the variable filterchooser that follows. - TableInfo.FixupStack.emplace_back(); - - emitSingletonTableEntry(TableInfo, Opc); - - resolveTableFixups(TableInfo.Table, TableInfo.FixupStack.back(), - TableInfo.Table.size()); - TableInfo.FixupStack.pop_back(); - - Best.getVariableFC().emitTableEntries(TableInfo); -} - -// Assign a single filter and run with it. Top level API client can initialize -// with a single filter to start the filtering process. -void FilterChooser::runSingleFilter(unsigned startBit, unsigned numBit, - bool mixed) { - Filters.clear(); - Filters.emplace_back(*this, startBit, numBit, true); - BestIndex = 0; // Sole Filter instance to choose from. - bestFilter().recurse(); -} - -// reportRegion is a helper function for filterProcessor to mark a region as -// eligible for use as a filter region. -void FilterChooser::reportRegion(bitAttr_t RA, unsigned StartBit, - unsigned BitIndex, bool AllowMixed) { - if (RA == ATTR_MIXED && AllowMixed) - Filters.emplace_back(*this, StartBit, BitIndex - StartBit, true); - else if (RA == ATTR_ALL_SET && !AllowMixed) - Filters.emplace_back(*this, StartBit, BitIndex - StartBit, false); -} - -// FilterProcessor scans the well-known encoding bits of the instructions and -// builds up a list of candidate filters. It chooses the best filter and -// recursively descends down the decoding tree. -bool FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { - Filters.clear(); - BestIndex = -1; - unsigned numInstructions = Opcodes.size(); - - assert(numInstructions && "Filter created with no instructions"); - - // No further filtering is necessary. - if (numInstructions == 1) - return true; - - // Heuristics. See also doFilter()'s "Heuristics" comment when num of - // instructions is 3. - if (AllowMixed && !Greedy) { - assert(numInstructions == 3); - - for (auto Opcode : Opcodes) { - std::vector StartBits; - std::vector EndBits; - std::vector FieldVals; - insn_t Insn; - - insnWithID(Insn, Opcode.EncodingID); - - // Look for islands of undecoded bits of any instruction. - if (getIslands(StartBits, EndBits, FieldVals, Insn) > 0) { - // Found an instruction with island(s). Now just assign a filter. - runSingleFilter(StartBits[0], EndBits[0] - StartBits[0] + 1, true); - return true; - } - } - } - - unsigned BitIndex; - - // We maintain BIT_WIDTH copies of the bitAttrs automaton. - // The automaton consumes the corresponding bit from each - // instruction. - // - // Input symbols: 0, 1, and _ (unset). - // States: NONE, FILTERED, ALL_SET, ALL_UNSET, and MIXED. - // Initial state: NONE. - // - // (NONE) ------- [01] -> (ALL_SET) - // (NONE) ------- _ ----> (ALL_UNSET) - // (ALL_SET) ---- [01] -> (ALL_SET) - // (ALL_SET) ---- _ ----> (MIXED) - // (ALL_UNSET) -- [01] -> (MIXED) - // (ALL_UNSET) -- _ ----> (ALL_UNSET) - // (MIXED) ------ . ----> (MIXED) - // (FILTERED)---- . ----> (FILTERED) - - std::vector bitAttrs; - - // FILTERED bit positions provide no entropy and are not worthy of pursuing. - // Filter::recurse() set either BIT_TRUE or BIT_FALSE for each position. - for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) - if (FilterBitValues[BitIndex] == BIT_TRUE || - FilterBitValues[BitIndex] == BIT_FALSE) - bitAttrs.push_back(ATTR_FILTERED); - else - bitAttrs.push_back(ATTR_NONE); - - for (unsigned InsnIndex = 0; InsnIndex < numInstructions; ++InsnIndex) { - insn_t insn; - - insnWithID(insn, Opcodes[InsnIndex].EncodingID); - - for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { - switch (bitAttrs[BitIndex]) { - case ATTR_NONE: - if (insn[BitIndex] == BIT_UNSET) - bitAttrs[BitIndex] = ATTR_ALL_UNSET; - else - bitAttrs[BitIndex] = ATTR_ALL_SET; - break; - case ATTR_ALL_SET: - if (insn[BitIndex] == BIT_UNSET) - bitAttrs[BitIndex] = ATTR_MIXED; - break; - case ATTR_ALL_UNSET: - if (insn[BitIndex] != BIT_UNSET) - bitAttrs[BitIndex] = ATTR_MIXED; - break; - case ATTR_MIXED: - case ATTR_FILTERED: - break; - } - } - } - - // The regionAttr automaton consumes the bitAttrs automatons' state, - // lowest-to-highest. - // - // Input symbols: F(iltered), (all_)S(et), (all_)U(nset), M(ixed) - // States: NONE, ALL_SET, MIXED - // Initial state: NONE - // - // (NONE) ----- F --> (NONE) - // (NONE) ----- S --> (ALL_SET) ; and set region start - // (NONE) ----- U --> (NONE) - // (NONE) ----- M --> (MIXED) ; and set region start - // (ALL_SET) -- F --> (NONE) ; and report an ALL_SET region - // (ALL_SET) -- S --> (ALL_SET) - // (ALL_SET) -- U --> (NONE) ; and report an ALL_SET region - // (ALL_SET) -- M --> (MIXED) ; and report an ALL_SET region - // (MIXED) ---- F --> (NONE) ; and report a MIXED region - // (MIXED) ---- S --> (ALL_SET) ; and report a MIXED region - // (MIXED) ---- U --> (NONE) ; and report a MIXED region - // (MIXED) ---- M --> (MIXED) - - bitAttr_t RA = ATTR_NONE; - unsigned StartBit = 0; - - for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { - bitAttr_t bitAttr = bitAttrs[BitIndex]; - - assert(bitAttr != ATTR_NONE && "Bit without attributes"); - - switch (RA) { - case ATTR_NONE: - switch (bitAttr) { - case ATTR_FILTERED: - break; - case ATTR_ALL_SET: - StartBit = BitIndex; - RA = ATTR_ALL_SET; - break; - case ATTR_ALL_UNSET: - break; - case ATTR_MIXED: - StartBit = BitIndex; - RA = ATTR_MIXED; - break; - default: - llvm_unreachable("Unexpected bitAttr!"); - } - break; - case ATTR_ALL_SET: - switch (bitAttr) { - case ATTR_FILTERED: - reportRegion(RA, StartBit, BitIndex, AllowMixed); - RA = ATTR_NONE; - break; - case ATTR_ALL_SET: - break; - case ATTR_ALL_UNSET: - reportRegion(RA, StartBit, BitIndex, AllowMixed); - RA = ATTR_NONE; - break; - case ATTR_MIXED: - reportRegion(RA, StartBit, BitIndex, AllowMixed); - StartBit = BitIndex; - RA = ATTR_MIXED; - break; - default: - llvm_unreachable("Unexpected bitAttr!"); - } - break; - case ATTR_MIXED: - switch (bitAttr) { - case ATTR_FILTERED: - reportRegion(RA, StartBit, BitIndex, AllowMixed); - StartBit = BitIndex; - RA = ATTR_NONE; - break; - case ATTR_ALL_SET: - reportRegion(RA, StartBit, BitIndex, AllowMixed); - StartBit = BitIndex; - RA = ATTR_ALL_SET; - break; - case ATTR_ALL_UNSET: - reportRegion(RA, StartBit, BitIndex, AllowMixed); - RA = ATTR_NONE; - break; - case ATTR_MIXED: - break; - default: - llvm_unreachable("Unexpected bitAttr!"); - } - break; - case ATTR_ALL_UNSET: - llvm_unreachable("regionAttr state machine has no ATTR_UNSET state"); - case ATTR_FILTERED: - llvm_unreachable("regionAttr state machine has no ATTR_FILTERED state"); - } - } - - // At the end, if we're still in ALL_SET or MIXED states, report a region - switch (RA) { - case ATTR_NONE: - break; - case ATTR_FILTERED: - break; - case ATTR_ALL_SET: - reportRegion(RA, StartBit, BitIndex, AllowMixed); - break; - case ATTR_ALL_UNSET: - break; - case ATTR_MIXED: - reportRegion(RA, StartBit, BitIndex, AllowMixed); - break; - } - - // We have finished with the filter processings. Now it's time to choose - // the best performing filter. - BestIndex = 0; - bool AllUseless = true; - unsigned BestScore = 0; - - for (unsigned i = 0, e = Filters.size(); i != e; ++i) { - unsigned Usefulness = Filters[i].usefulness(); - - if (Usefulness) - AllUseless = false; - - if (Usefulness > BestScore) { - BestIndex = i; - BestScore = Usefulness; - } - } - - if (!AllUseless) - bestFilter().recurse(); - - return !AllUseless; -} // end of FilterChooser::filterProcessor(bool) - -// Decides on the best configuration of filter(s) to use in order to decode -// the instructions. A conflict of instructions may occur, in which case we -// dump the conflict set to the standard error. -void FilterChooser::doFilter() { - unsigned Num = Opcodes.size(); - assert(Num && "FilterChooser created with no instructions"); - - // Try regions of consecutive known bit values first. - if (filterProcessor(false)) - return; - - // Then regions of mixed bits (both known and unitialized bit values allowed). - if (filterProcessor(true)) - return; - - // Heuristics to cope with conflict set {t2CMPrs, t2SUBSrr, t2SUBSrs} where - // no single instruction for the maximum ATTR_MIXED region Inst{14-4} has a - // well-known encoding pattern. In such case, we backtrack and scan for the - // the very first consecutive ATTR_ALL_SET region and assign a filter to it. - if (Num == 3 && filterProcessor(true, false)) - return; - - // If we come to here, the instruction decoding has failed. - // Set the BestIndex to -1 to indicate so. - BestIndex = -1; -} - -// emitTableEntries - Emit state machine entries to decode our share of -// instructions. -void FilterChooser::emitTableEntries(DecoderTableInfo &TableInfo) const { - if (Opcodes.size() == 1) { - // There is only one instruction in the set, which is great! - // Call emitSingletonDecoder() to see whether there are any remaining - // encodings bits. - emitSingletonTableEntry(TableInfo, Opcodes[0]); - return; - } - - // Choose the best filter to do the decodings! - if (BestIndex != -1) { - const Filter &Best = Filters[BestIndex]; - if (Best.getNumFiltered() == 1) - emitSingletonTableEntry(TableInfo, Best); - else - Best.emitTableEntry(TableInfo); - return; - } - - // We don't know how to decode these instructions! Dump the - // conflict set and bail. - - // Print out useful conflict information for postmortem analysis. - errs() << "Decoding Conflict:\n"; - - dumpStack(errs(), "\t\t"); - - for (auto Opcode : Opcodes) { - errs() << '\t'; - emitNameWithID(errs(), Opcode.EncodingID); - errs() << " "; - dumpBits( - errs(), - getBitsField(*AllInstructions[Opcode.EncodingID].EncodingDef, "Inst")); - errs() << '\n'; - } -} - -static std::string findOperandDecoderMethod(Record *Record) { - std::string Decoder; - - RecordVal *DecoderString = Record->getValue("DecoderMethod"); - StringInit *String = DecoderString ? - dyn_cast(DecoderString->getValue()) : nullptr; - if (String) { - Decoder = std::string(String->getValue()); - if (!Decoder.empty()) - return Decoder; - } - - if (Record->isSubClassOf("RegisterOperand")) - Record = Record->getValueAsDef("RegClass"); - - if (Record->isSubClassOf("RegisterClass")) { - Decoder = "Decode" + Record->getName().str() + "RegisterClass"; - } else if (Record->isSubClassOf("PointerLikeRegClass")) { - Decoder = "DecodePointerLikeRegClass" + - utostr(Record->getValueAsInt("RegClassKind")); - } - - return Decoder; -} - -OperandInfo getOpInfo(Record *TypeRecord) { - std::string Decoder = findOperandDecoderMethod(TypeRecord); - - RecordVal *HasCompleteDecoderVal = TypeRecord->getValue("hasCompleteDecoder"); - BitInit *HasCompleteDecoderBit = - HasCompleteDecoderVal - ? dyn_cast(HasCompleteDecoderVal->getValue()) - : nullptr; - bool HasCompleteDecoder = - HasCompleteDecoderBit ? HasCompleteDecoderBit->getValue() : true; - - return OperandInfo(Decoder, HasCompleteDecoder); -} - -void parseVarLenInstOperand(const Record &Def, - std::vector &Operands, - const CodeGenInstruction &CGI) { - - const RecordVal *RV = Def.getValue("Inst"); - VarLenInst VLI(cast(RV->getValue()), RV); - SmallVector TiedTo; - - for (unsigned Idx = 0; Idx < CGI.Operands.size(); ++Idx) { - auto &Op = CGI.Operands[Idx]; - if (Op.MIOperandInfo && Op.MIOperandInfo->getNumArgs() > 0) - for (auto *Arg : Op.MIOperandInfo->getArgs()) - Operands.push_back(getOpInfo(cast(Arg)->getDef())); - else - Operands.push_back(getOpInfo(Op.Rec)); - - int TiedReg = Op.getTiedRegister(); - TiedTo.push_back(-1); - if (TiedReg != -1) { - TiedTo[Idx] = TiedReg; - TiedTo[TiedReg] = Idx; - } - } - - unsigned CurrBitPos = 0; - for (auto &EncodingSegment : VLI) { - unsigned Offset = 0; - StringRef OpName; - - if (const StringInit *SI = dyn_cast(EncodingSegment.Value)) { - OpName = SI->getValue(); - } else if (const DagInit *DI = dyn_cast(EncodingSegment.Value)) { - OpName = cast(DI->getArg(0))->getValue(); - Offset = cast(DI->getArg(2))->getValue(); - } - - if (!OpName.empty()) { - auto OpSubOpPair = - const_cast(CGI).Operands.ParseOperandName( - OpName); - unsigned OpIdx = CGI.Operands.getFlattenedOperandNumber(OpSubOpPair); - Operands[OpIdx].addField(CurrBitPos, EncodingSegment.BitWidth, Offset); - - int TiedReg = TiedTo[OpSubOpPair.first]; - if (TiedReg != -1) { - unsigned OpIdx = CGI.Operands.getFlattenedOperandNumber( - std::make_pair(TiedReg, OpSubOpPair.second)); - Operands[OpIdx].addField(CurrBitPos, EncodingSegment.BitWidth, Offset); - } - } - - CurrBitPos += EncodingSegment.BitWidth; - } -} - -static unsigned -populateInstruction(CodeGenTarget &Target, const Record &EncodingDef, - const CodeGenInstruction &CGI, unsigned Opc, - std::map> &Operands, - bool IsVarLenInst) { - const Record &Def = *CGI.TheDef; - // If all the bit positions are not specified; do not decode this instruction. - // We are bound to fail! For proper disassembly, the well-known encoding bits - // of the instruction must be fully specified. - - BitsInit &Bits = getBitsField(EncodingDef, "Inst"); - if (Bits.allInComplete()) - return 0; - - std::vector InsnOperands; - - // If the instruction has specified a custom decoding hook, use that instead - // of trying to auto-generate the decoder. - StringRef InstDecoder = EncodingDef.getValueAsString("DecoderMethod"); - if (InstDecoder != "") { - bool HasCompleteInstDecoder = EncodingDef.getValueAsBit("hasCompleteDecoder"); - InsnOperands.push_back( - OperandInfo(std::string(InstDecoder), HasCompleteInstDecoder)); - Operands[Opc] = InsnOperands; - return Bits.getNumBits(); - } - - // Generate a description of the operand of the instruction that we know - // how to decode automatically. - // FIXME: We'll need to have a way to manually override this as needed. - - // Gather the outputs/inputs of the instruction, so we can find their - // positions in the encoding. This assumes for now that they appear in the - // MCInst in the order that they're listed. - std::vector> InOutOperands; - DagInit *Out = Def.getValueAsDag("OutOperandList"); - DagInit *In = Def.getValueAsDag("InOperandList"); - for (unsigned i = 0; i < Out->getNumArgs(); ++i) - InOutOperands.push_back( - std::make_pair(Out->getArg(i), Out->getArgNameStr(i))); - for (unsigned i = 0; i < In->getNumArgs(); ++i) - InOutOperands.push_back( - std::make_pair(In->getArg(i), In->getArgNameStr(i))); - - // Search for tied operands, so that we can correctly instantiate - // operands that are not explicitly represented in the encoding. - std::map TiedNames; - for (unsigned i = 0; i < CGI.Operands.size(); ++i) { - int tiedTo = CGI.Operands[i].getTiedRegister(); - if (tiedTo != -1) { - std::pair SO = - CGI.Operands.getSubOperandNumber(tiedTo); - TiedNames[std::string(InOutOperands[i].second)] = - std::string(InOutOperands[SO.first].second); - TiedNames[std::string(InOutOperands[SO.first].second)] = - std::string(InOutOperands[i].second); - } - } - - if (IsVarLenInst) { - parseVarLenInstOperand(EncodingDef, InsnOperands, CGI); - } else { - std::map> NumberedInsnOperands; - std::set NumberedInsnOperandsNoTie; - if (Target.getInstructionSet()->getValueAsBit( - "decodePositionallyEncodedOperands")) { - const std::vector &Vals = Def.getValues(); - unsigned NumberedOp = 0; - - std::set NamedOpIndices; - if (Target.getInstructionSet()->getValueAsBit( - "noNamedPositionallyEncodedOperands")) - // Collect the set of operand indices that might correspond to named - // operand, and skip these when assigning operands based on position. - for (unsigned i = 0, e = Vals.size(); i != e; ++i) { - unsigned OpIdx; - if (!CGI.Operands.hasOperandNamed(Vals[i].getName(), OpIdx)) - continue; - - NamedOpIndices.insert(OpIdx); - } - - for (unsigned i = 0, e = Vals.size(); i != e; ++i) { - // Ignore fixed fields in the record, we're looking for values like: - // bits<5> RST = { ?, ?, ?, ?, ? }; - if (Vals[i].isNonconcreteOK() || Vals[i].getValue()->isComplete()) - continue; - - // Determine if Vals[i] actually contributes to the Inst encoding. - unsigned bi = 0; - for (; bi < Bits.getNumBits(); ++bi) { - VarInit *Var = nullptr; - VarBitInit *BI = dyn_cast(Bits.getBit(bi)); - if (BI) - Var = dyn_cast(BI->getBitVar()); - else - Var = dyn_cast(Bits.getBit(bi)); - - if (Var && Var->getName() == Vals[i].getName()) - break; - } - - if (bi == Bits.getNumBits()) - continue; - - // Skip variables that correspond to explicitly-named operands. - unsigned OpIdx; - if (CGI.Operands.hasOperandNamed(Vals[i].getName(), OpIdx)) - continue; - - // Get the bit range for this operand: - unsigned bitStart = bi++, bitWidth = 1; - for (; bi < Bits.getNumBits(); ++bi) { - VarInit *Var = nullptr; - VarBitInit *BI = dyn_cast(Bits.getBit(bi)); - if (BI) - Var = dyn_cast(BI->getBitVar()); - else - Var = dyn_cast(Bits.getBit(bi)); - - if (!Var) - break; - - if (Var->getName() != Vals[i].getName()) - break; - - ++bitWidth; - } - - unsigned NumberOps = CGI.Operands.size(); - while (NumberedOp < NumberOps && - (CGI.Operands.isFlatOperandNotEmitted(NumberedOp) || - (!NamedOpIndices.empty() && - NamedOpIndices.count( - CGI.Operands.getSubOperandNumber(NumberedOp).first)))) - ++NumberedOp; - - OpIdx = NumberedOp++; - - // OpIdx now holds the ordered operand number of Vals[i]. - std::pair SO = - CGI.Operands.getSubOperandNumber(OpIdx); - const std::string &Name = CGI.Operands[SO.first].Name; - - LLVM_DEBUG(dbgs() << "Numbered operand mapping for " << Def.getName() - << ": " << Name << "(" << SO.first << ", " - << SO.second << ") => " << Vals[i].getName() << "\n"); - - std::string Decoder; - Record *TypeRecord = CGI.Operands[SO.first].Rec; - - RecordVal *DecoderString = TypeRecord->getValue("DecoderMethod"); - StringInit *String = - DecoderString ? dyn_cast(DecoderString->getValue()) - : nullptr; - if (String && String->getValue() != "") - Decoder = std::string(String->getValue()); - - if (Decoder == "" && CGI.Operands[SO.first].MIOperandInfo && - CGI.Operands[SO.first].MIOperandInfo->getNumArgs()) { - Init *Arg = CGI.Operands[SO.first].MIOperandInfo->getArg(SO.second); - if (DefInit *DI = cast(Arg)) - TypeRecord = DI->getDef(); - } - - bool isReg = false; - if (TypeRecord->isSubClassOf("RegisterOperand")) - TypeRecord = TypeRecord->getValueAsDef("RegClass"); - if (TypeRecord->isSubClassOf("RegisterClass")) { - Decoder = "Decode" + TypeRecord->getName().str() + "RegisterClass"; - isReg = true; - } else if (TypeRecord->isSubClassOf("PointerLikeRegClass")) { - Decoder = "DecodePointerLikeRegClass" + - utostr(TypeRecord->getValueAsInt("RegClassKind")); - isReg = true; - } - - DecoderString = TypeRecord->getValue("DecoderMethod"); - String = DecoderString ? dyn_cast(DecoderString->getValue()) - : nullptr; - if (!isReg && String && String->getValue() != "") - Decoder = std::string(String->getValue()); - - RecordVal *HasCompleteDecoderVal = - TypeRecord->getValue("hasCompleteDecoder"); - BitInit *HasCompleteDecoderBit = - HasCompleteDecoderVal - ? dyn_cast(HasCompleteDecoderVal->getValue()) - : nullptr; - bool HasCompleteDecoder = - HasCompleteDecoderBit ? HasCompleteDecoderBit->getValue() : true; - - OperandInfo OpInfo(Decoder, HasCompleteDecoder); - OpInfo.addField(bitStart, bitWidth, 0); - - NumberedInsnOperands[Name].push_back(OpInfo); - - // FIXME: For complex operands with custom decoders we can't handle tied - // sub-operands automatically. Skip those here and assume that this is - // fixed up elsewhere. - if (CGI.Operands[SO.first].MIOperandInfo && - CGI.Operands[SO.first].MIOperandInfo->getNumArgs() > 1 && String && - String->getValue() != "") - NumberedInsnOperandsNoTie.insert(Name); - } - } - - // For each operand, see if we can figure out where it is encoded. - for (const auto &Op : InOutOperands) { - if (!NumberedInsnOperands[std::string(Op.second)].empty()) { - llvm::append_range(InsnOperands, - NumberedInsnOperands[std::string(Op.second)]); - continue; - } - if (!NumberedInsnOperands[TiedNames[std::string(Op.second)]].empty()) { - if (!NumberedInsnOperandsNoTie.count( - TiedNames[std::string(Op.second)])) { - // Figure out to which (sub)operand we're tied. - unsigned i = - CGI.Operands.getOperandNamed(TiedNames[std::string(Op.second)]); - int tiedTo = CGI.Operands[i].getTiedRegister(); - if (tiedTo == -1) { - i = CGI.Operands.getOperandNamed(Op.second); - tiedTo = CGI.Operands[i].getTiedRegister(); - } - - if (tiedTo != -1) { - std::pair SO = - CGI.Operands.getSubOperandNumber(tiedTo); - - InsnOperands.push_back( - NumberedInsnOperands[TiedNames[std::string(Op.second)]] - [SO.second]); - } - } - continue; - } - - // At this point, we can locate the decoder field, but we need to know how - // to interpret it. As a first step, require the target to provide - // callbacks for decoding register classes. - - OperandInfo OpInfo = getOpInfo(cast(Op.first)->getDef()); - - // Some bits of the operand may be required to be 1 depending on the - // instruction's encoding. Collect those bits. - if (const RecordVal *EncodedValue = EncodingDef.getValue(Op.second)) - if (const BitsInit *OpBits = - dyn_cast(EncodedValue->getValue())) - for (unsigned I = 0; I < OpBits->getNumBits(); ++I) - if (const BitInit *OpBit = dyn_cast(OpBits->getBit(I))) - if (OpBit->getValue()) - OpInfo.InitValue |= 1ULL << I; - - unsigned Base = ~0U; - unsigned Width = 0; - unsigned Offset = 0; - - for (unsigned bi = 0; bi < Bits.getNumBits(); ++bi) { - VarInit *Var = nullptr; - VarBitInit *BI = dyn_cast(Bits.getBit(bi)); - if (BI) - Var = dyn_cast(BI->getBitVar()); - else - Var = dyn_cast(Bits.getBit(bi)); - - if (!Var) { - if (Base != ~0U) { - OpInfo.addField(Base, Width, Offset); - Base = ~0U; - Width = 0; - Offset = 0; - } - continue; - } - - if ((Var->getName() != Op.second && - Var->getName() != TiedNames[std::string(Op.second)])) { - if (Base != ~0U) { - OpInfo.addField(Base, Width, Offset); - Base = ~0U; - Width = 0; - Offset = 0; - } - continue; - } - - if (Base == ~0U) { - Base = bi; - Width = 1; - Offset = BI ? BI->getBitNum() : 0; - } else if (BI && BI->getBitNum() != Offset + Width) { - OpInfo.addField(Base, Width, Offset); - Base = bi; - Width = 1; - Offset = BI->getBitNum(); - } else { - ++Width; - } - } - - if (Base != ~0U) - OpInfo.addField(Base, Width, Offset); - - if (OpInfo.numFields() > 0) - InsnOperands.push_back(OpInfo); - } - } - - Operands[Opc] = InsnOperands; - -#if 0 - LLVM_DEBUG({ - // Dumps the instruction encoding bits. - dumpBits(errs(), Bits); - - errs() << '\n'; - - // Dumps the list of operand info. - for (unsigned i = 0, e = CGI.Operands.size(); i != e; ++i) { - const CGIOperandList::OperandInfo &Info = CGI.Operands[i]; - const std::string &OperandName = Info.Name; - const Record &OperandDef = *Info.Rec; - - errs() << "\t" << OperandName << " (" << OperandDef.getName() << ")\n"; - } - }); -#endif - - return Bits.getNumBits(); -} - -// emitFieldFromInstruction - Emit the templated helper function -// fieldFromInstruction(). -// On Windows we make sure that this function is not inlined when -// using the VS compiler. It has a bug which causes the function -// to be optimized out in some circustances. See llvm.org/pr38292 -static void emitFieldFromInstruction(formatted_raw_ostream &OS) { - OS << "// Helper functions for extracting fields from encoded instructions.\n" - << "// InsnType must either be integral or an APInt-like object that " - "must:\n" - << "// * be default-constructible and copy-constructible\n" - << "// * be constructible from an APInt (this can be private)\n" - << "// * Support insertBits(bits, startBit, numBits)\n" - << "// * Support extractBitsAsZExtValue(numBits, startBit)\n" - << "// * Support the ~, &, ==, and != operators with other objects of " - "the same type\n" - << "// * Support the != and bitwise & with uint64_t\n" - << "// * Support put (<<) to raw_ostream&\n" - << "template \n" - << "#if defined(_MSC_VER) && !defined(__clang__)\n" - << "__declspec(noinline)\n" - << "#endif\n" - << "static std::enable_if_t::value, InsnType>\n" - << "fieldFromInstruction(const InsnType &insn, unsigned startBit,\n" - << " unsigned numBits) {\n" - << " assert(startBit + numBits <= 64 && \"Cannot support >64-bit " - "extractions!\");\n" - << " assert(startBit + numBits <= (sizeof(InsnType) * 8) &&\n" - << " \"Instruction field out of bounds!\");\n" - << " InsnType fieldMask;\n" - << " if (numBits == sizeof(InsnType) * 8)\n" - << " fieldMask = (InsnType)(-1LL);\n" - << " else\n" - << " fieldMask = (((InsnType)1 << numBits) - 1) << startBit;\n" - << " return (insn & fieldMask) >> startBit;\n" - << "}\n" - << "\n" - << "template \n" - << "static std::enable_if_t::value, " - "uint64_t>\n" - << "fieldFromInstruction(const InsnType &insn, unsigned startBit,\n" - << " unsigned numBits) {\n" - << " return insn.extractBitsAsZExtValue(numBits, startBit);\n" - << "}\n\n"; -} - -// emitInsertBits - Emit the templated helper function insertBits(). -static void emitInsertBits(formatted_raw_ostream &OS) { - OS << "// Helper function for inserting bits extracted from an encoded " - "instruction into\n" - << "// a field.\n" - << "template \n" - << "static std::enable_if_t::value>\n" - << "insertBits(InsnType &field, InsnType bits, unsigned startBit, " - "unsigned numBits) {\n" - << " assert(startBit + numBits <= sizeof field * 8);\n" - << " field |= (InsnType)bits << startBit;\n" - << "}\n" - << "\n" - << "template \n" - << "static std::enable_if_t::value>\n" - << "insertBits(InsnType &field, uint64_t bits, unsigned startBit, " - "unsigned numBits) {\n" - << " field.insertBits(bits, startBit, numBits);\n" - << "}\n\n"; -} - -// emitDecodeInstruction - Emit the templated helper function -// decodeInstruction(). -static void emitDecodeInstruction(formatted_raw_ostream &OS, - bool IsVarLenInst) { - OS << "template \n" - << "static DecodeStatus decodeInstruction(const uint8_t DecodeTable[], " - "MCInst &MI,\n" - << " InsnType insn, uint64_t " - "Address,\n" - << " const MCDisassembler *DisAsm,\n" - << " const MCSubtargetInfo &STI"; - if (IsVarLenInst) { - OS << ",\n" - << " llvm::function_ref makeUp"; - } - OS << ") {\n" - << " const FeatureBitset &Bits = STI.getFeatureBits();\n" - << "\n" - << " const uint8_t *Ptr = DecodeTable;\n" - << " uint64_t CurFieldValue = 0;\n" - << " DecodeStatus S = MCDisassembler::Success;\n" - << " while (true) {\n" - << " ptrdiff_t Loc = Ptr - DecodeTable;\n" - << " switch (*Ptr) {\n" - << " default:\n" - << " errs() << Loc << \": Unexpected decode table opcode!\\n\";\n" - << " return MCDisassembler::Fail;\n" - << " case MCD::OPC_ExtractField: {\n" - << " unsigned Start = *++Ptr;\n" - << " unsigned Len = *++Ptr;\n" - << " ++Ptr;\n"; - if (IsVarLenInst) - OS << " makeUp(insn, Start + Len);\n"; - OS << " CurFieldValue = fieldFromInstruction(insn, Start, Len);\n" - << " LLVM_DEBUG(dbgs() << Loc << \": OPC_ExtractField(\" << Start << " - "\", \"\n" - << " << Len << \"): \" << CurFieldValue << \"\\n\");\n" - << " break;\n" - << " }\n" - << " case MCD::OPC_FilterValue: {\n" - << " // Decode the field value.\n" - << " unsigned Len;\n" - << " uint64_t Val = decodeULEB128(++Ptr, &Len);\n" - << " Ptr += Len;\n" - << " // NumToSkip is a plain 24-bit integer.\n" - << " unsigned NumToSkip = *Ptr++;\n" - << " NumToSkip |= (*Ptr++) << 8;\n" - << " NumToSkip |= (*Ptr++) << 16;\n" - << "\n" - << " // Perform the filter operation.\n" - << " if (Val != CurFieldValue)\n" - << " Ptr += NumToSkip;\n" - << " LLVM_DEBUG(dbgs() << Loc << \": OPC_FilterValue(\" << Val << " - "\", \" << NumToSkip\n" - << " << \"): \" << ((Val != CurFieldValue) ? \"FAIL:\" " - ": \"PASS:\")\n" - << " << \" continuing at \" << (Ptr - DecodeTable) << " - "\"\\n\");\n" - << "\n" - << " break;\n" - << " }\n" - << " case MCD::OPC_CheckField: {\n" - << " unsigned Start = *++Ptr;\n" - << " unsigned Len = *++Ptr;\n"; - if (IsVarLenInst) - OS << " makeUp(insn, Start + Len);\n"; - OS << " uint64_t FieldValue = fieldFromInstruction(insn, Start, Len);\n" - << " // Decode the field value.\n" - << " unsigned PtrLen = 0;\n" - << " uint64_t ExpectedValue = decodeULEB128(++Ptr, &PtrLen);\n" - << " Ptr += PtrLen;\n" - << " // NumToSkip is a plain 24-bit integer.\n" - << " unsigned NumToSkip = *Ptr++;\n" - << " NumToSkip |= (*Ptr++) << 8;\n" - << " NumToSkip |= (*Ptr++) << 16;\n" - << "\n" - << " // If the actual and expected values don't match, skip.\n" - << " if (ExpectedValue != FieldValue)\n" - << " Ptr += NumToSkip;\n" - << " LLVM_DEBUG(dbgs() << Loc << \": OPC_CheckField(\" << Start << " - "\", \"\n" - << " << Len << \", \" << ExpectedValue << \", \" << " - "NumToSkip\n" - << " << \"): FieldValue = \" << FieldValue << \", " - "ExpectedValue = \"\n" - << " << ExpectedValue << \": \"\n" - << " << ((ExpectedValue == FieldValue) ? \"PASS\\n\" : " - "\"FAIL\\n\"));\n" - << " break;\n" - << " }\n" - << " case MCD::OPC_CheckPredicate: {\n" - << " unsigned Len;\n" - << " // Decode the Predicate Index value.\n" - << " unsigned PIdx = decodeULEB128(++Ptr, &Len);\n" - << " Ptr += Len;\n" - << " // NumToSkip is a plain 24-bit integer.\n" - << " unsigned NumToSkip = *Ptr++;\n" - << " NumToSkip |= (*Ptr++) << 8;\n" - << " NumToSkip |= (*Ptr++) << 16;\n" - << " // Check the predicate.\n" - << " bool Pred;\n" - << " if (!(Pred = checkDecoderPredicate(PIdx, Bits)))\n" - << " Ptr += NumToSkip;\n" - << " (void)Pred;\n" - << " LLVM_DEBUG(dbgs() << Loc << \": OPC_CheckPredicate(\" << PIdx " - "<< \"): \"\n" - << " << (Pred ? \"PASS\\n\" : \"FAIL\\n\"));\n" - << "\n" - << " break;\n" - << " }\n" - << " case MCD::OPC_Decode: {\n" - << " unsigned Len;\n" - << " // Decode the Opcode value.\n" - << " unsigned Opc = decodeULEB128(++Ptr, &Len);\n" - << " Ptr += Len;\n" - << " unsigned DecodeIdx = decodeULEB128(Ptr, &Len);\n" - << " Ptr += Len;\n" - << "\n" - << " MI.clear();\n" - << " MI.setOpcode(Opc);\n" - << " bool DecodeComplete;\n"; - if (IsVarLenInst) { - OS << " Len = InstrLenTable[Opc];\n" - << " makeUp(insn, Len);\n"; - } - OS << " S = decodeToMCInst(S, DecodeIdx, insn, MI, Address, DisAsm, " - "DecodeComplete);\n" - << " assert(DecodeComplete);\n" - << "\n" - << " LLVM_DEBUG(dbgs() << Loc << \": OPC_Decode: opcode \" << Opc\n" - << " << \", using decoder \" << DecodeIdx << \": \"\n" - << " << (S != MCDisassembler::Fail ? \"PASS\" : " - "\"FAIL\") << \"\\n\");\n" - << " return S;\n" - << " }\n" - << " case MCD::OPC_TryDecode: {\n" - << " unsigned Len;\n" - << " // Decode the Opcode value.\n" - << " unsigned Opc = decodeULEB128(++Ptr, &Len);\n" - << " Ptr += Len;\n" - << " unsigned DecodeIdx = decodeULEB128(Ptr, &Len);\n" - << " Ptr += Len;\n" - << " // NumToSkip is a plain 24-bit integer.\n" - << " unsigned NumToSkip = *Ptr++;\n" - << " NumToSkip |= (*Ptr++) << 8;\n" - << " NumToSkip |= (*Ptr++) << 16;\n" - << "\n" - << " // Perform the decode operation.\n" - << " MCInst TmpMI;\n" - << " TmpMI.setOpcode(Opc);\n" - << " bool DecodeComplete;\n" - << " S = decodeToMCInst(S, DecodeIdx, insn, TmpMI, Address, DisAsm, " - "DecodeComplete);\n" - << " LLVM_DEBUG(dbgs() << Loc << \": OPC_TryDecode: opcode \" << " - "Opc\n" - << " << \", using decoder \" << DecodeIdx << \": \");\n" - << "\n" - << " if (DecodeComplete) {\n" - << " // Decoding complete.\n" - << " LLVM_DEBUG(dbgs() << (S != MCDisassembler::Fail ? \"PASS\" : " - "\"FAIL\") << \"\\n\");\n" - << " MI = TmpMI;\n" - << " return S;\n" - << " } else {\n" - << " assert(S == MCDisassembler::Fail);\n" - << " // If the decoding was incomplete, skip.\n" - << " Ptr += NumToSkip;\n" - << " LLVM_DEBUG(dbgs() << \"FAIL: continuing at \" << (Ptr - " - "DecodeTable) << \"\\n\");\n" - << " // Reset decode status. This also drops a SoftFail status " - "that could be\n" - << " // set before the decode attempt.\n" - << " S = MCDisassembler::Success;\n" - << " }\n" - << " break;\n" - << " }\n" - << " case MCD::OPC_SoftFail: {\n" - << " // Decode the mask values.\n" - << " unsigned Len;\n" - << " uint64_t PositiveMask = decodeULEB128(++Ptr, &Len);\n" - << " Ptr += Len;\n" - << " uint64_t NegativeMask = decodeULEB128(Ptr, &Len);\n" - << " Ptr += Len;\n" - << " bool Fail = (insn & PositiveMask) != 0 || (~insn & " - "NegativeMask) != 0;\n" - << " if (Fail)\n" - << " S = MCDisassembler::SoftFail;\n" - << " LLVM_DEBUG(dbgs() << Loc << \": OPC_SoftFail: \" << (Fail ? " - "\"FAIL\\n\" : \"PASS\\n\"));\n" - << " break;\n" - << " }\n" - << " case MCD::OPC_Fail: {\n" - << " LLVM_DEBUG(dbgs() << Loc << \": OPC_Fail\\n\");\n" - << " return MCDisassembler::Fail;\n" - << " }\n" - << " }\n" - << " }\n" - << " llvm_unreachable(\"bogosity detected in disassembler state " - "machine!\");\n" - << "}\n\n"; -} - -// Emits disassembler code for instruction decoding. -void DecoderEmitter::run(raw_ostream &o) { - formatted_raw_ostream OS(o); - OS << "#include \"llvm/MC/MCInst.h\"\n"; - OS << "#include \"llvm/MC/MCSubtargetInfo.h\"\n"; - OS << "#include \"llvm/MC/SubtargetFeature.h\"\n"; - OS << "#include \"llvm/Support/DataTypes.h\"\n"; - OS << "#include \"llvm/Support/Debug.h\"\n"; - OS << "#include \"llvm/Support/LEB128.h\"\n"; - OS << "#include \"llvm/Support/raw_ostream.h\"\n"; - OS << "#include \n"; - OS << '\n'; - OS << "namespace llvm {\n\n"; - - emitFieldFromInstruction(OS); - emitInsertBits(OS); - - Target.reverseBitsForLittleEndianEncoding(); - - // Parameterize the decoders based on namespace and instruction width. - std::set HwModeNames; - const auto &NumberedInstructions = Target.getInstructionsByEnumValue(); - NumberedEncodings.reserve(NumberedInstructions.size()); - DenseMap IndexOfInstruction; - // First, collect all HwModes referenced by the target. - for (const auto &NumberedInstruction : NumberedInstructions) { - IndexOfInstruction[NumberedInstruction->TheDef] = NumberedEncodings.size(); - - if (const RecordVal *RV = - NumberedInstruction->TheDef->getValue("EncodingInfos")) { - if (auto *DI = dyn_cast_or_null(RV->getValue())) { - const CodeGenHwModes &HWM = Target.getHwModes(); - EncodingInfoByHwMode EBM(DI->getDef(), HWM); - for (auto &KV : EBM) - HwModeNames.insert(HWM.getMode(KV.first).Name); - } - } - } - - // If HwModeNames is empty, add the empty string so we always have one HwMode. - if (HwModeNames.empty()) - HwModeNames.insert(""); - - for (const auto &NumberedInstruction : NumberedInstructions) { - IndexOfInstruction[NumberedInstruction->TheDef] = NumberedEncodings.size(); - - if (const RecordVal *RV = - NumberedInstruction->TheDef->getValue("EncodingInfos")) { - if (DefInit *DI = dyn_cast_or_null(RV->getValue())) { - const CodeGenHwModes &HWM = Target.getHwModes(); - EncodingInfoByHwMode EBM(DI->getDef(), HWM); - for (auto &KV : EBM) { - NumberedEncodings.emplace_back(KV.second, NumberedInstruction, - HWM.getMode(KV.first).Name); - HwModeNames.insert(HWM.getMode(KV.first).Name); - } - continue; - } - } - // This instruction is encoded the same on all HwModes. Emit it for all - // HwModes. - for (StringRef HwModeName : HwModeNames) - NumberedEncodings.emplace_back(NumberedInstruction->TheDef, - NumberedInstruction, HwModeName); - } - for (const auto &NumberedAlias : RK.getAllDerivedDefinitions("AdditionalEncoding")) - NumberedEncodings.emplace_back( - NumberedAlias, - &Target.getInstruction(NumberedAlias->getValueAsDef("AliasOf"))); - - std::map, std::vector> - OpcMap; - std::map> Operands; - std::vector InstrLen; - - bool IsVarLenInst = - any_of(NumberedInstructions, [](const CodeGenInstruction *CGI) { - RecordVal *RV = CGI->TheDef->getValue("Inst"); - return RV && isa(RV->getValue()); - }); - unsigned MaxInstLen = 0; - - for (unsigned i = 0; i < NumberedEncodings.size(); ++i) { - const Record *EncodingDef = NumberedEncodings[i].EncodingDef; - const CodeGenInstruction *Inst = NumberedEncodings[i].Inst; - const Record *Def = Inst->TheDef; - unsigned Size = EncodingDef->getValueAsInt("Size"); - if (Def->getValueAsString("Namespace") == "TargetOpcode" || - Def->getValueAsBit("isPseudo") || - Def->getValueAsBit("isAsmParserOnly") || - Def->getValueAsBit("isCodeGenOnly")) { - NumEncodingsLackingDisasm++; - continue; - } - - if (i < NumberedInstructions.size()) - NumInstructions++; - NumEncodings++; - - if (!Size && !IsVarLenInst) - continue; - - if (IsVarLenInst) - InstrLen.resize(NumberedInstructions.size(), 0); - - if (unsigned Len = populateInstruction(Target, *EncodingDef, *Inst, i, - Operands, IsVarLenInst)) { - if (IsVarLenInst) { - MaxInstLen = std::max(MaxInstLen, Len); - InstrLen[i] = Len; - } - std::string DecoderNamespace = - std::string(EncodingDef->getValueAsString("DecoderNamespace")); - if (!NumberedEncodings[i].HwModeName.empty()) - DecoderNamespace += - std::string("_") + NumberedEncodings[i].HwModeName.str(); - OpcMap[std::make_pair(DecoderNamespace, Size)].emplace_back( - i, IndexOfInstruction.find(Def)->second); - } else { - NumEncodingsOmitted++; - } - } - - DecoderTableInfo TableInfo; - for (const auto &Opc : OpcMap) { - // Emit the decoder for this namespace+width combination. - ArrayRef NumberedEncodingsRef( - NumberedEncodings.data(), NumberedEncodings.size()); - FilterChooser FC(NumberedEncodingsRef, Opc.second, Operands, - 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 - // decoders to give more opportunities for uniqueing. - TableInfo.Table.clear(); - TableInfo.FixupStack.clear(); - TableInfo.Table.reserve(16384); - TableInfo.FixupStack.emplace_back(); - FC.emitTableEntries(TableInfo); - // Any NumToSkip fixups in the top level scope can resolve to the - // OPC_Fail at the end of the table. - assert(TableInfo.FixupStack.size() == 1 && "fixup stack phasing error!"); - // Resolve any NumToSkip fixups in the current scope. - resolveTableFixups(TableInfo.Table, TableInfo.FixupStack.back(), - TableInfo.Table.size()); - TableInfo.FixupStack.clear(); - - TableInfo.Table.push_back(MCD::OPC_Fail); - - // Print the table to the output stream. - emitTable(OS, TableInfo.Table, 0, FC.getBitWidth(), Opc.first.first); - OS.flush(); - } - - // For variable instruction, we emit a instruction length table - // to let the decoder know how long the instructions are. - // You can see example usage in M68k's disassembler. - if (IsVarLenInst) - emitInstrLenTable(OS, InstrLen); - // Emit the predicate function. - emitPredicateFunction(OS, TableInfo.Predicates, 0); - - // Emit the decoder function. - emitDecoderFunction(OS, TableInfo.Decoders, 0); - - // Emit the main entry point for the decoder, decodeInstruction(). - emitDecodeInstruction(OS, IsVarLenInst); - - OS << "\n} // end namespace llvm\n"; -} - -namespace llvm { - -void EmitDecoder(RecordKeeper &RK, raw_ostream &OS, - const std::string &PredicateNamespace, - const std::string &GPrefix, const std::string &GPostfix, - const std::string &ROK, const std::string &RFail, - const std::string &L) { - DecoderEmitter(RK, PredicateNamespace, GPrefix, GPostfix, ROK, RFail, L) - .run(OS); -} - -} // end namespace llvm Index: llvm/utils/TableGen/DecoderEmitter/CMakeLists.txt =================================================================== --- /dev/null +++ llvm/utils/TableGen/DecoderEmitter/CMakeLists.txt @@ -0,0 +1,10 @@ +set(LLVM_LINK_COMPONENTS + TableGen + ) + +add_llvm_library(LLVMTableDecoderEmitter LINK_COMPONENTS DISABLE_LLVM_LINK_LLVM_DYLIB + "DecoderEmitter.cpp" + "Filter.cpp" + "FilterChooser.cpp" + "HelperFunctions.cpp" + ) Index: llvm/utils/TableGen/DecoderEmitter/DecoderEmitter.h =================================================================== --- /dev/null +++ llvm/utils/TableGen/DecoderEmitter/DecoderEmitter.h @@ -0,0 +1,530 @@ +//===----------- DecoderEmitter.h - Decoder Generator -----------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_UTILS_TABLEGEN_DECODEREMITTER_DECODEREMITTER_H +#define LLVM_UTILS_TABLEGEN_DECODEREMITTER_DECODEREMITTER_H + +#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" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/MC/MCDecoderOps.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/FormattedStream.h" +#include "llvm/Support/LEB128.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/TableGen/Error.h" +#include "llvm/TableGen/Record.h" +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace llvm; + +namespace tblgen_decoder_emitter { + +////////////////////// +// Structs and Types +////////////////////// + +struct EncodingField { + unsigned Base, Width, Offset; + EncodingField(unsigned B, unsigned W, unsigned O) + : Base(B), Width(W), Offset(O) {} +}; + +struct OperandInfo { + std::vector Fields; + std::string Decoder; + bool HasCompleteDecoder; + uint64_t InitValue; + + OperandInfo(std::string D, bool HCD) + : Decoder(std::move(D)), HasCompleteDecoder(HCD), InitValue(0) {} + + void addField(unsigned Base, unsigned Width, unsigned Offset) { + Fields.push_back(EncodingField(Base, Width, Offset)); + } + + unsigned numFields() const { return Fields.size(); } + + typedef std::vector::const_iterator const_iterator; + + const_iterator begin() const { return Fields.begin(); } + const_iterator end() const { return Fields.end(); } +}; + +typedef std::vector DecoderTable; +typedef uint32_t DecoderFixup; +typedef std::vector FixupList; +typedef std::vector FixupScopeList; +typedef SmallSetVector PredicateSet; +typedef SmallSetVector DecoderSet; +struct DecoderTableInfo { + DecoderTable Table; + FixupScopeList FixupStack; + PredicateSet Predicates; + DecoderSet Decoders; +}; + +struct EncodingAndInst { + const Record *EncodingDef; + const CodeGenInstruction *Inst; + StringRef HwModeName; + + EncodingAndInst(const Record *EncodingDef, const CodeGenInstruction *Inst, + StringRef HwModeName = "") + : EncodingDef(EncodingDef), Inst(Inst), HwModeName(HwModeName) {} +}; + +struct EncodingIDAndOpcode { + unsigned EncodingID; + unsigned Opcode; + + EncodingIDAndOpcode() : EncodingID(0), Opcode(0) {} + EncodingIDAndOpcode(unsigned EncodingID, unsigned Opcode) + : EncodingID(EncodingID), Opcode(Opcode) {} +}; + +inline 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; +} + +// The set (BIT_TRUE, BIT_FALSE, BIT_UNSET) represents a ternary logic system +// for a bit value. +// +// BIT_UNFILTERED is used as the init value for a filter position. It is used +// only for filter processings. +typedef enum { + BIT_TRUE, // '1' + BIT_FALSE, // '0' + BIT_UNSET, // '?' + BIT_UNFILTERED // unfiltered +} bit_value_t; + +// Representation of the instruction to work on. +typedef std::vector insn_t; + +static const uint64_t NoFixedSegmentsSentinel = -1ULL; + +////////////////////// +// Functions +////////////////////// + +std::string findOperandDecoderMethod(Record *Record); + +OperandInfo getOpInfo(Record *TypeRecord); + +void parseVarLenInstOperand(const Record &Def, + std::vector &Operands, + const CodeGenInstruction &CGI); + +unsigned +populateInstruction(CodeGenTarget &Target, const Record &EncodingDef, + const CodeGenInstruction &CGI, unsigned Opc, + std::map> &Operands, + bool IsVarLenInst); + +// emitFieldFromInstruction - Emit the templated helper function +// fieldFromInstruction(). +// On Windows we make sure that this function is not inlined when +// using the VS compiler. It has a bug which causes the function +// to be optimized out in some circustances. See llvm.org/pr38292 +void emitFieldFromInstruction(formatted_raw_ostream &OS); + +// emitInsertBits - Emit the templated helper function insertBits(). +void emitInsertBits(formatted_raw_ostream &OS); + +// emitDecodeInstruction - Emit the templated helper function +// decodeInstruction(). +void emitDecodeInstruction(formatted_raw_ostream &OS, bool IsVarLenInst); + +bool valueSet(bit_value_t V); + +bool valueNotSet(bit_value_t V); + +int value(bit_value_t V); + +bit_value_t bitFromBits(const BitsInit &Bits, unsigned Index); + +// Prints the bit value for each position. +void dumpBits(raw_ostream &O, const BitsInit &Bits); + +BitsInit &getBitsField(const Record &Def, StringRef Str); + +void resolveTableFixups(DecoderTable &Table, const FixupList &Fixups, + uint32_t DestIdx); + +////////////////////// +// Classes +////////////////////// + +class FilterChooser; +class Filter; + +class DecoderEmitter { + RecordKeeper &RK; + std::vector NumberedEncodings; + + ArrayRef NumberedInstructions; + DenseMap IndexOfInstruction; + // The opcode map. + // It maps the DecoderNamespace (e.g. ARM Thumb16) and instruction sizes + // to the encodings which belong into this subset. + std::map, std::vector> + OpcMap; + std::map> Operands; + std::vector InstrLen; + +public: + // Defaults preserved here for documentation, even though they aren't + // strictly necessary given the way that this is currently being called. + DecoderEmitter(RecordKeeper &R, std::string PredicateNamespace, + std::string GPrefix = "if (", + std::string GPostfix = " == MCDisassembler::Fail)", + std::string ROK = "MCDisassembler::Success", + std::string RFail = "MCDisassembler::Fail", std::string L = "") + : RK(R), NumberedInstructions(nullptr), Target(R), + PredicateNamespace(std::move(PredicateNamespace)), GuardPrefix(std::move(GPrefix)), + GuardPostfix(std::move(GPostfix)), ReturnOK(std::move(ROK)), + ReturnFail(std::move(RFail)), Locals(std::move(L)) {} + + // Emit the decoder state machine table. + void emitTable(formatted_raw_ostream &O, DecoderTable &Table, + unsigned Indentation, unsigned BitWidth, + StringRef Namespace) const; + void emitInstrLenTable(formatted_raw_ostream &OS, + std::vector &InstrLen) const; + void emitPredicateFunction(formatted_raw_ostream &OS, + PredicateSet &Predicates, + unsigned Indentation) const; + void emitDecoderFunction(formatted_raw_ostream &OS, DecoderSet &Decoders, + unsigned Indentation) const; + void retrieveHwModeEncodings(); + unsigned + fillOpcMap(bool const IsVarLenInst); + + // run - Output the code emitter + void run(raw_ostream &O); + +private: + CodeGenTarget Target; + +public: + std::string PredicateNamespace; + std::string GuardPrefix, GuardPostfix; + std::string ReturnOK, ReturnFail; + std::string Locals; +}; + +/// Filter - Filter works with FilterChooser to produce the decoding tree for +/// the ISA. +/// +/// It is useful to think of a Filter as governing the switch stmts of the +/// decoding tree in a certain level. Each case stmt delegates to an inferior +/// FilterChooser to decide what further decoding logic to employ, or in +/// another words, what other remaining bits to look at. The FilterChooser +/// eventually chooses a best Filter to do its job. +/// +/// This recursive scheme ends when the number of Opcodes assigned to the +/// FilterChooser becomes 1 or if there is a conflict. A conflict happens +/// when the Filter/FilterChooser combo does not know how to distinguish among +/// the Opcodes assigned. +/// +/// An example of a conflict is +/// +/// Conflict: +/// 111101000.00........00010000.... +/// 111101000.00........0001........ +/// 1111010...00........0001........ +/// 1111010...00.................... +/// 1111010......................... +/// 1111............................ +/// ................................ +/// VST4q8a 111101000_00________00010000____ +/// VST4q8b 111101000_00________00010000____ +/// +/// The Debug output shows the path that the decoding tree follows to reach +/// the the conclusion that there is a conflict. VST4q8a is a vst4 to +/// double-spaced even registers, while VST4q8b is a vst4 to double-spaced odd +/// registers. +/// +/// The encoding info in the .td files does not specify this meta information, +/// which could have been used by the decoder to resolve the conflict. The +/// decoder could try to decode the even/odd register numbering and assign to +/// VST4q8a or VST4q8b, but for the time being, the decoder chooses the "a" +/// version and return the Opcode since the two have the same Asm format +/// string. +class Filter { +protected: + const FilterChooser + *Owner; // points to the FilterChooser who owns this filter + unsigned StartBit; // the starting bit position + unsigned NumBits; // number of bits to filter + bool Mixed; // a mixed region contains both set and unset bits + + // Map of well-known segment value to the set of uid's with that value. + std::map> FilteredInstructions; + + // Set of uid's with non-constant segment values. + std::vector VariableInstructions; + + // Map of well-known segment value to its delegate. + std::map> FilterChooserMap; + + // Number of instructions which fall under FilteredInstructions category. + unsigned NumFiltered; + + // Keeps track of the last opcode in the filtered bucket. + EncodingIDAndOpcode LastOpcFiltered; + +public: + Filter(Filter &&F); + Filter(FilterChooser &Owner, unsigned StartBit, unsigned NumBits, bool Mixed); + + ~Filter() = default; + + unsigned getNumFiltered() const { return NumFiltered; } + + EncodingIDAndOpcode getSingletonOpc() const { + assert(NumFiltered == 1); + return LastOpcFiltered; + } + + // Return the filter chooser for the group of instructions without constant + // segment values. + const FilterChooser &getVariableFC() const { + assert(NumFiltered == 1); + assert(FilterChooserMap.size() == 1); + return *(FilterChooserMap.find(NoFixedSegmentsSentinel)->second); + } + + // Divides the decoding task into sub tasks and delegates them to the + // inferior FilterChooser's. + // + // A special case arises when there's only one entry in the filtered + // instructions. In order to unambiguously decode the singleton, we need to + // match the remaining undecoded encoding bits against the singleton. + void recurse(); + + // Emit table entries to decode instructions given a segment or segments of + // bits. + void emitTableEntry(DecoderTableInfo &TableInfo) const; + + // Returns the number of fanout produced by the filter. More fanout implies + // the filter distinguishes more categories of instructions. + unsigned usefulness() const; +}; // end class Filter + +// These are states of our finite state machines used in FilterChooser's +// filterProcessor() which produces the filter candidates to use. +typedef enum { + ATTR_NONE, + ATTR_FILTERED, + ATTR_ALL_SET, + ATTR_ALL_UNSET, + ATTR_MIXED +} bitAttr_t; + +/// FilterChooser - FilterChooser chooses the best filter among a set of +/// Filters in order to perform the decoding of instructions at the current +/// level. +/// +/// Decoding proceeds from the top down. Based on the well-known encoding +/// bits of instructions available, FilterChooser builds up the possible +/// Filters that can further the task of decoding by distinguishing among the +/// remaining candidate instructions. +/// +/// Once a filter has been chosen, it is called upon to divide the decoding +/// task into sub-tasks and delegates them to its inferior FilterChoosers for +/// further processings. +/// +/// It is useful to think of a Filter as governing the switch stmts of the +/// decoding tree. And each case is delegated to an inferior FilterChooser to +/// decide what further remaining bits to look at. +class FilterChooser { +protected: + friend class Filter; + + // Vector of codegen instructions to choose our filter. + ArrayRef AllInstructions; + + // Vector of uid's for this filter chooser to work on. + // The first member of the pair is the opcode id being decoded, the second + // is the opcode id that should be emitted. + const std::vector &Opcodes; + + // Lookup table for the operand decoding of instructions. + const std::map> &Operands; + + // Vector of candidate filters. + std::vector Filters; + + // Array of bit values passed down from our parent. + // Set to all BIT_UNFILTERED's for Parent == NULL. + std::vector FilterBitValues; + + // Links to the FilterChooser above us in the decoding tree. + const FilterChooser *Parent; + + // Index of the best filter from Filters. + int BestIndex; + + // Width of instructions + unsigned BitWidth; + + // Parent emitter + const DecoderEmitter *Emitter; + +public: + FilterChooser(ArrayRef Insts, + const std::vector &IDs, + const std::map> &Ops, + unsigned BW, const DecoderEmitter *E) + : AllInstructions(Insts), Opcodes(IDs), Operands(Ops), + FilterBitValues(BW, BIT_UNFILTERED), Parent(nullptr), BestIndex(-1), + BitWidth(BW), Emitter(E) { + doFilter(); + } + + FilterChooser(ArrayRef Insts, + const std::vector &IDs, + const std::map> &Ops, + const std::vector &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; + + // Emit the name of the encoding/instruction pair. + void emitNameWithID(raw_ostream &ErrOS, unsigned Opcode) const; + + // 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 &ErrOS, + const std::vector &Filter) const; + + /// dumpStack - dumpStack traverses the filter chooser chain and calls + /// dumpFilterArray on each filter chooser up to the top level one. + void dumpStack(raw_ostream &ErrOS, const char *Prefix) const; + + Filter &bestFilter() { + assert(BestIndex != -1 && "BestIndex not set"); + return Filters[BestIndex]; + } + + bool positionFiltered(unsigned I) const { + return valueSet(FilterBitValues[I]); + } + + // Calculates the island(s) needed to decode the instruction. + // This returns a lit of undecoded bits of an instructions, for example, + // Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be + // decoded bits in order to verify that the instruction matches the Opcode. + unsigned getIslands(std::vector &StartBits, + std::vector &EndBits, + std::vector &FieldVals, + const insn_t &Insn) const; + + // Emits code to check the Predicates member of an instruction are true. + // Returns true if predicate matches were emitted, false otherwise. + bool emitPredicateMatch(raw_ostream &O, unsigned &Indentation, + unsigned Opc) const; + bool emitPredicateMatchAux(const Init &Val, bool ParenIfBinOp, + raw_ostream &OS) const; + + bool doesOpcodeNeedPredicate(unsigned Opc) const; + unsigned getPredicateIndex(DecoderTableInfo &TableInfo, StringRef P) const; + void emitPredicateTableEntry(DecoderTableInfo &TableInfo, unsigned Opc) const; + + void emitSoftFailTableEntry(DecoderTableInfo &TableInfo, unsigned Opc) const; + + // Emits table entries to decode the singleton. + void emitSingletonTableEntry(DecoderTableInfo &TableInfo, + EncodingIDAndOpcode Opc) const; + + // Emits code to decode the singleton, and then to decode the rest. + void emitSingletonTableEntry(DecoderTableInfo &TableInfo, + const Filter &Best) const; + + void emitBinaryParser(raw_ostream &O, unsigned &Indentation, + const OperandInfo &OpInfo, + bool &OpHasCompleteDecoder) const; + + void emitDecoder(raw_ostream &OS, unsigned Indentation, unsigned Opc, + bool &HasCompleteDecoder) const; + unsigned getDecoderIndex(DecoderSet &Decoders, unsigned Opc, + bool &HasCompleteDecoder) const; + + // Assign a single filter and run with it. + void runSingleFilter(unsigned StartBit, unsigned NumBit, bool Mixed); + + // reportRegion is a helper function for filterProcessor to mark a region as + // eligible for use as a filter region. + void reportRegion(bitAttr_t RA, unsigned StartBit, unsigned BitIndex, + bool AllowMixed); + + // FilterProcessor scans the well-known encoding bits of the instructions + // and builds up a list of candidate filters. It chooses the best filter + // and recursively descends down the decoding tree. + bool filterProcessor(bool AllowMixed, bool Greedy = true); + + // Decides on the best configuration of filter(s) to use in order to decode + // the instructions. A conflict of instructions may occur, in which case we + // dump the conflict set to the standard error. + void doFilter(); + +public: + // emitTableEntries - Emit state machine entries to decode our share of + // instructions. + void emitTableEntries(DecoderTableInfo &TableInfo) const; +}; + +} // end namespace tblgen_decoder_emitter + +#endif // LLVM_UTILS_TABLEGEN_DECODEREMITTER_DECODEREMITTER_H Index: llvm/utils/TableGen/DecoderEmitter/DecoderEmitter.cpp =================================================================== --- /dev/null +++ llvm/utils/TableGen/DecoderEmitter/DecoderEmitter.cpp @@ -0,0 +1,477 @@ +//===------------ DecoderEmitter.cpp - Decoder Generator --------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// It contains the tablegen backend that emits the decoder functions for +// targets with fixed/variable length instruction set. +// +//===----------------------------------------------------------------------===// + +#include "DecoderEmitter.h" + +using namespace llvm; +namespace tblgen_decoder_emitter { + +#define DEBUG_TYPE "decoder-emitter-DecoderEmitter" + +STATISTIC(NumEncodings, "Number of encodings considered"); +STATISTIC(NumEncodingsLackingDisasm, "Number of encodings without disassembler info"); +STATISTIC(NumInstructions, "Number of instructions considered"); +STATISTIC(NumEncodingsOmitted, "Number of encodings omitted"); + +// Emit the decoder state machine table. +void DecoderEmitter::emitTable(formatted_raw_ostream &OS, DecoderTable &Table, + unsigned Indentation, unsigned BitWidth, + StringRef Namespace) const { + OS.indent(Indentation) << "static const uint8_t DecoderTable" << Namespace + << BitWidth << "[] = {\n"; + + Indentation += 2; + + // FIXME: We may be able to use the NumToSkip values to recover + // appropriate indentation levels. + DecoderTable::const_iterator I = Table.begin(); + DecoderTable::const_iterator const E = Table.end(); + while (I != E) { + assert (I < E && "incomplete decode table entry!"); + + uint64_t const Pos = I - Table.begin(); + OS << "/* " << Pos << " */"; + OS.PadToColumn(12); + + switch (*I) { + default: + PrintFatalError("invalid decode table opcode"); + case MCD::OPC_ExtractField: { + ++I; + unsigned const Start = *I++; + unsigned const Len = *I++; + OS.indent(Indentation) << "MCD::OPC_ExtractField, " << Start << ", " + << Len << ", // Inst{"; + if (Len > 1) + OS << (Start + Len - 1) << "-"; + OS << Start << "} ...\n"; + break; + } + case MCD::OPC_FilterValue: { + ++I; + OS.indent(Indentation) << "MCD::OPC_FilterValue, "; + // The filter value is ULEB128 encoded. + while (*I >= 128) + OS << (unsigned)*I++ << ", "; + OS << (unsigned)*I++ << ", "; + + // 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 << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; + break; + } + case MCD::OPC_CheckField: { + ++I; + unsigned const Start = *I++; + unsigned const Len = *I++; + OS.indent(Indentation) << "MCD::OPC_CheckField, " << Start << ", " + << Len << ", ";// << Val << ", " << NumToSkip << ",\n"; + // ULEB128 encoded field value. + for (; *I >= 128; ++I) + OS << (unsigned)*I << ", "; + OS << (unsigned)*I++ << ", "; + // 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 << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; + break; + } + case MCD::OPC_CheckPredicate: { + ++I; + OS.indent(Indentation) << "MCD::OPC_CheckPredicate, "; + for (; *I >= 128; ++I) + OS << (unsigned)*I << ", "; + OS << (unsigned)*I++ << ", "; + + // 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 << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; + break; + } + case MCD::OPC_Decode: + case MCD::OPC_TryDecode: { + bool const IsTry = *I == MCD::OPC_TryDecode; + ++I; + // Extract the ULEB128 encoded Opcode to a buffer. + uint8_t Buffer[16], *P = Buffer; + while ((*P++ = *I++) >= 128) + assert((P - Buffer) <= (ptrdiff_t)sizeof(Buffer) + && "ULEB128 value too large!"); + // Decode the Opcode value. + unsigned const Opc = decodeULEB128(Buffer); + OS.indent(Indentation) << "MCD::OPC_" << (IsTry ? "Try" : "") + << "Decode, "; + for (P = Buffer; *P >= 128; ++P) + OS << (unsigned)*P << ", "; + OS << (unsigned)*P << ", "; + + // Decoder index. + for (; *I >= 128; ++I) + OS << (unsigned)*I << ", "; + OS << (unsigned)*I++ << ", "; + + if (!IsTry) { + 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: " << 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; + unsigned Shift = 0; + do { + OS << ", " << (unsigned)*I; + Value += (*I & 0x7f) << Shift; + Shift += 7; + } while (*I++ >= 128); + if (Value > 127) { + OS << " /* 0x"; + OS.write_hex(Value); + OS << " */"; + } + // Negative mask + Value = 0; + Shift = 0; + do { + OS << ", " << (unsigned)*I; + Value += (*I & 0x7f) << Shift; + Shift += 7; + } while (*I++ >= 128); + if (Value > 127) { + OS << " /* 0x"; + OS.write_hex(Value); + OS << " */"; + } + OS << ",\n"; + break; + } + case MCD::OPC_Fail: { + ++I; + OS.indent(Indentation) << "MCD::OPC_Fail,\n"; + break; + } + } + } + OS.indent(Indentation) << "0\n"; + + Indentation -= 2; + + OS.indent(Indentation) << "};\n\n"; +} + +void DecoderEmitter::emitInstrLenTable(formatted_raw_ostream &OS, + std::vector &InstrLen) const { + OS << "static const uint8_t InstrLenTable[] = {\n"; + for (unsigned const&Len : InstrLen) { + OS << Len << ",\n"; + } + OS << "};\n\n"; +} + +void DecoderEmitter::emitPredicateFunction(formatted_raw_ostream &OS, + PredicateSet &Predicates, + unsigned Indentation) const { + // The predicate function is just a big switch statement based on the + // input predicate index. + OS.indent(Indentation) << "static bool checkDecoderPredicate(unsigned Idx, " + << "const FeatureBitset &Bits) {\n"; + Indentation += 2; + if (!Predicates.empty()) { + OS.indent(Indentation) << "switch (Idx) {\n"; + OS.indent(Indentation) << "default: llvm_unreachable(\"Invalid index!\");\n"; + unsigned Index = 0; + for (const auto &Predicate : Predicates) { + OS.indent(Indentation) << "case " << Index++ << ":\n"; + OS.indent(Indentation+2) << "return (" << Predicate << ");\n"; + } + OS.indent(Indentation) << "}\n"; + } else { + // No case statement to emit + OS.indent(Indentation) << "llvm_unreachable(\"Invalid index!\");\n"; + } + Indentation -= 2; + OS.indent(Indentation) << "}\n\n"; +} + +void DecoderEmitter::emitDecoderFunction(formatted_raw_ostream &OS, + DecoderSet &Decoders, + unsigned Indentation) const { + // The decoder function is just a big switch statement based on the + // input decoder index. + OS.indent(Indentation) << "template \n"; + OS.indent(Indentation) << "static DecodeStatus decodeToMCInst(DecodeStatus S," + << " unsigned Idx, InsnType insn, MCInst &MI,\n"; + OS.indent(Indentation) + << " uint64_t " + << "Address, const MCDisassembler *Decoder, bool &DecodeComplete) {\n"; + Indentation += 2; + OS.indent(Indentation) << "DecodeComplete = true;\n"; + // TODO: When InsnType is large, using uint64_t limits all fields to 64 bits + // It would be better for emitBinaryParser to use a 64-bit tmp whenever + // possible but fall back to an InsnType-sized tmp for truly large fields. + OS.indent(Indentation) << "using TmpType = " + "std::conditional_t::" + "value, InsnType, uint64_t>;\n"; + OS.indent(Indentation) << "TmpType tmp;\n"; + OS.indent(Indentation) << "switch (Idx) {\n"; + OS.indent(Indentation) << "default: llvm_unreachable(\"Invalid index!\");\n"; + unsigned Index = 0; + for (const auto &Decoder : Decoders) { + OS.indent(Indentation) << "case " << Index++ << ":\n"; + OS << Decoder; + OS.indent(Indentation+2) << "return S;\n"; + } + OS.indent(Indentation) << "}\n"; + Indentation -= 2; + OS.indent(Indentation) << "}\n\n"; +} + +/// Encodings of instructions might differ if the Hardware Mode is different as well. +/// Here we add all possible encodings. +void DecoderEmitter::retrieveHwModeEncodings() { + std::set HwModeNames; + + // First, collect all HwModes referenced by the target. + for (const auto &NumberedInstruction : NumberedInstructions) { + IndexOfInstruction[NumberedInstruction->TheDef] = NumberedEncodings.size(); + + if (const RecordVal *RV = + NumberedInstruction->TheDef->getValue("EncodingInfos")) { + if (auto *DI = dyn_cast_or_null(RV->getValue())) { + const CodeGenHwModes &HWM = Target.getHwModes(); + EncodingInfoByHwMode const EBM(DI->getDef(), HWM); + for (auto &KV : EBM) + HwModeNames.insert(HWM.getMode(KV.first).Name); + } + } + } + + // If HwModeNames is empty, add the empty string so we always have one HwMode. + if (HwModeNames.empty()) + HwModeNames.insert(""); + + for (const auto &NumberedInstruction : NumberedInstructions) { + IndexOfInstruction[NumberedInstruction->TheDef] = NumberedEncodings.size(); + + if (const RecordVal *RV = + NumberedInstruction->TheDef->getValue("EncodingInfos")) { + if (DefInit *DI = dyn_cast_or_null(RV->getValue())) { + const CodeGenHwModes &HWM = Target.getHwModes(); + EncodingInfoByHwMode EBM(DI->getDef(), HWM); + for (auto &KV : EBM) { + NumberedEncodings.emplace_back(KV.second, NumberedInstruction, + HWM.getMode(KV.first).Name); + HwModeNames.insert(HWM.getMode(KV.first).Name); + } + continue; + } + } + // This instruction is encoded the same on all HwModes. Emit it for all + // HwModes. + for (StringRef HwModeName : HwModeNames) + NumberedEncodings.emplace_back(NumberedInstruction->TheDef, + NumberedInstruction, HwModeName); + } +} + +/// Fills the Opcode Map with the encodings of the different decoder spaces. +/// It returns the maximum length of all variable length instructions. +/// Or 0 if no variable length is in the set (\p IsVarLenInst = false) +unsigned DecoderEmitter::fillOpcMap(bool const IsVarLenInst) { + unsigned MaxInstLen = 0; + for (unsigned I = 0; I < NumberedEncodings.size(); ++I) { + const Record *EncodingDef = NumberedEncodings[I].EncodingDef; + const CodeGenInstruction *Inst = NumberedEncodings[I].Inst; + const Record *Def = Inst->TheDef; + unsigned const Size = EncodingDef->getValueAsInt("Size"); + if (Def->getValueAsString("Namespace") == "TargetOpcode" || + Def->getValueAsBit("isPseudo") || + Def->getValueAsBit("isAsmParserOnly") || + Def->getValueAsBit("isCodeGenOnly")) { + NumEncodingsLackingDisasm++; + continue; + } + + if (I < NumberedInstructions.size()) + NumInstructions++; + NumEncodings++; + + if (!Size && !IsVarLenInst) + continue; + + if (IsVarLenInst) + InstrLen.resize(NumberedInstructions.size(), 0); + + if (unsigned const Len = populateInstruction(Target, *EncodingDef, *Inst, I, + Operands, IsVarLenInst)) { + if (IsVarLenInst) { + MaxInstLen = std::max(MaxInstLen, Len); + InstrLen[I] = Len; + } + std::string DecoderNamespace = + std::string(EncodingDef->getValueAsString("DecoderNamespace")); + if (!NumberedEncodings[I].HwModeName.empty()) + DecoderNamespace += + std::string("_") + NumberedEncodings[I].HwModeName.str(); + OpcMap[std::make_pair(DecoderNamespace, Size)].emplace_back( + I, IndexOfInstruction.find(Def)->second); + } else { + NumEncodingsOmitted++; + } + } + return MaxInstLen; +} + +// Emits disassembler code for instruction decoding. +void DecoderEmitter::run(raw_ostream &O) { + formatted_raw_ostream OS(O); + OS << "#include \"llvm/MC/MCInst.h\"\n"; + OS << "#include \"llvm/MC/MCSubtargetInfo.h\"\n"; + OS << "#include \"llvm/MC/SubtargetFeature.h\"\n"; + OS << "#include \"llvm/Support/DataTypes.h\"\n"; + OS << "#include \"llvm/Support/Debug.h\"\n"; + OS << "#include \"llvm/Support/LEB128.h\"\n"; + OS << "#include \"llvm/Support/raw_ostream.h\"\n"; + OS << "#include \n"; + OS << '\n'; + OS << "namespace llvm {\n\n"; + + emitFieldFromInstruction(OS); + emitInsertBits(OS); + + Target.reverseBitsForLittleEndianEncoding(); + + // Parameterize the decoders based on namespace and instruction width. + NumberedInstructions = Target.getInstructionsByEnumValue(); + NumberedEncodings.reserve(NumberedInstructions.size()); + + retrieveHwModeEncodings(); + + for (const auto &NumberedAlias : RK.getAllDerivedDefinitions("AdditionalEncoding")) + NumberedEncodings.emplace_back( + NumberedAlias, + &Target.getInstruction(NumberedAlias->getValueAsDef("AliasOf"))); + + bool const IsVarLenInst = + any_of(NumberedInstructions, [](const CodeGenInstruction *CGI) { + RecordVal *RV = CGI->TheDef->getValue("Inst"); + return RV && isa(RV->getValue()); + }); + + unsigned const MaxInstLen = fillOpcMap(IsVarLenInst); + + // Build the state machine for instruction decoding. + DecoderTableInfo TableInfo; + for (const auto &Opc : OpcMap) { + // Emit the decoder for this namespace+width combination. + ArrayRef const NumberedEncodingsRef( + NumberedEncodings.data(), NumberedEncodings.size()); + FilterChooser const FC(NumberedEncodingsRef, Opc.second, Operands, + 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 + // decoders to give more opportunities for uniqueing. + TableInfo.Table.clear(); + TableInfo.FixupStack.clear(); + TableInfo.Table.reserve(16384); + TableInfo.FixupStack.emplace_back(); + FC.emitTableEntries(TableInfo); + // Any NumToSkip fixups in the top level scope can resolve to the + // OPC_Fail at the end of the table. + assert(TableInfo.FixupStack.size() == 1 && "fixup stack phasing error!"); + // Resolve any NumToSkip fixups in the current scope. + resolveTableFixups(TableInfo.Table, TableInfo.FixupStack.back(), + TableInfo.Table.size()); + TableInfo.FixupStack.clear(); + + TableInfo.Table.push_back(MCD::OPC_Fail); + + // Print the table to the output stream. + emitTable(OS, TableInfo.Table, 0, FC.getBitWidth(), Opc.first.first); + OS.flush(); + } + + // For variable instruction, we emit a instruction length table + // to let the decoder know how long the instructions are. + // You can see example usage in M68k's disassembler. + if (IsVarLenInst) + emitInstrLenTable(OS, InstrLen); + // Emit the predicate function. + emitPredicateFunction(OS, TableInfo.Predicates, 0); + + // Emit the decoder function. + emitDecoderFunction(OS, TableInfo.Decoders, 0); + + // Emit the main entry point for the decoder, decodeInstruction(). + emitDecodeInstruction(OS, IsVarLenInst); + + OS << "\n} // end namespace llvm\n"; +} +} // end namespace tblgen_decoder_emitter + +namespace llvm { + +void EmitDecoder(RecordKeeper &RK, raw_ostream &OS, + const std::string &PredicateNamespace, + const std::string &GPrefix, const std::string &GPostfix, + const std::string &ROK, const std::string &RFail, + const std::string &L) { + tblgen_decoder_emitter::DecoderEmitter(RK, PredicateNamespace, GPrefix, GPostfix, ROK, RFail, L) + .run(OS); +} + +} // end namespace llvm + Index: llvm/utils/TableGen/DecoderEmitter/Filter.cpp =================================================================== --- /dev/null +++ llvm/utils/TableGen/DecoderEmitter/Filter.cpp @@ -0,0 +1,194 @@ +//===----------------------- Filter.cpp - Filter ----------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Contains a Filter used by the Decoder Emitter to distinguish +// subsets of instructions. +// +//===----------------------------------------------------------------------===// + +#include "DecoderEmitter.h" + +using namespace llvm; + +namespace tblgen_decoder_emitter { + +Filter::Filter(Filter &&F) + : Owner(F.Owner), StartBit(F.StartBit), NumBits(F.NumBits), Mixed(F.Mixed), + FilteredInstructions(std::move(F.FilteredInstructions)), + VariableInstructions(std::move(F.VariableInstructions)), + FilterChooserMap(std::move(F.FilterChooserMap)), + NumFiltered(F.NumFiltered), LastOpcFiltered(F.LastOpcFiltered) {} + +Filter::Filter(FilterChooser &Owner, unsigned StartBit, unsigned NumBits, + bool Mixed) + : Owner(&Owner), StartBit(StartBit), NumBits(NumBits), Mixed(Mixed) { + assert(StartBit + NumBits - 1 < Owner.BitWidth); + + NumFiltered = 0; + LastOpcFiltered = {0, 0}; + + for (unsigned I = 0, E = Owner.Opcodes.size(); I != E; ++I) { + insn_t Insn; + + // Populates the insn given the uid. + Owner.insnWithID(Insn, Owner.Opcodes[I].EncodingID); + + uint64_t Field; + // Scans the segment for possibly well-specified encoding bits. + bool const Ok = Owner.fieldFromInsn(Field, Insn, StartBit, NumBits); + + if (Ok) { + // The encoding bits are well-known. Lets add the uid of the + // instruction into the bucket keyed off the constant field value. + LastOpcFiltered = Owner.Opcodes[I]; + FilteredInstructions[Field].push_back(LastOpcFiltered); + ++NumFiltered; + } else { + // Some of the encoding bit(s) are unspecified. This contributes to + // one additional member of "Variable" instructions. + VariableInstructions.push_back(Owner.Opcodes[I]); + } + } + + assert((FilteredInstructions.size() + VariableInstructions.size() > 0) && + "Filter returns no instruction categories"); +} + +// Divides the decoding task into sub tasks and delegates them to the +// inferior FilterChooser's. +// +// A special case arises when there's only one entry in the filtered +// instructions. In order to unambiguously decode the singleton, we need to +// match the remaining undecoded encoding bits against the singleton. +void Filter::recurse() { + // Starts by inheriting our parent filter chooser's filter bit values. + std::vector BitValueArray(Owner->FilterBitValues); + + if (!VariableInstructions.empty()) { + // Conservatively marks each segment position as BIT_UNSET. + for (unsigned BitIndex = 0; BitIndex < NumBits; ++BitIndex) + BitValueArray[StartBit + BitIndex] = BIT_UNSET; + + // Delegates to an inferior filter chooser for further processing on this + // group of instructions whose segment values are variable. + FilterChooserMap.insert(std::make_pair( + NoFixedSegmentsSentinel, + std::make_unique(Owner->AllInstructions, + VariableInstructions, Owner->Operands, + BitValueArray, *Owner))); + } + + // No need to recurse for a singleton filtered instruction. + // See also Filter::emit*(). + if (getNumFiltered() == 1) { + assert(FilterChooserMap.size() == 1); + return; + } + + // Otherwise, create sub choosers. + for (const auto &Inst : FilteredInstructions) { + // Marks all the segment positions with either BIT_TRUE or BIT_FALSE. + for (unsigned BitIndex = 0; BitIndex < NumBits; ++BitIndex) { + if (Inst.first & (1ULL << BitIndex)) + BitValueArray[StartBit + BitIndex] = BIT_TRUE; + else + BitValueArray[StartBit + BitIndex] = BIT_FALSE; + } + + // Delegates to an inferior filter chooser for further processing on this + // category of instructions. + FilterChooserMap.insert(std::make_pair( + Inst.first, std::make_unique( + Owner->AllInstructions, Inst.second, Owner->Operands, + BitValueArray, *Owner))); + } +} + +// Emit table entries to decode instructions given a segment or segments +// of bits. +void Filter::emitTableEntry(DecoderTableInfo &TableInfo) const { + TableInfo.Table.push_back(MCD::OPC_ExtractField); + TableInfo.Table.push_back(StartBit); + TableInfo.Table.push_back(NumBits); + + // A new filter entry begins a new scope for fixup resolution. + TableInfo.FixupStack.emplace_back(); + + DecoderTable &Table = TableInfo.Table; + + size_t PrevFilter = 0; + bool HasFallthrough = false; + for (auto &Filter : FilterChooserMap) { + // Field value -1 implies a non-empty set of variable instructions. + // See also recurse(). + if (Filter.first == NoFixedSegmentsSentinel) { + HasFallthrough = true; + + // Each scope should always have at least one filter value to check + // for. + assert(PrevFilter != 0 && "empty filter set!"); + FixupList &CurScope = TableInfo.FixupStack.back(); + // Resolve any NumToSkip fixups in the current scope. + resolveTableFixups(Table, CurScope, Table.size()); + CurScope.clear(); + PrevFilter = 0; // Don't re-process the filter's fallthrough. + } else { + Table.push_back(MCD::OPC_FilterValue); + // Encode and emit the value to filter against. + uint8_t Buffer[16]; + unsigned const Len = encodeULEB128(Filter.first, Buffer); + Table.insert(Table.end(), Buffer, Buffer + Len); + // Reserve space for the NumToSkip entry. We'll backpatch the value + // later. + PrevFilter = Table.size(); + Table.push_back(0); + Table.push_back(0); + Table.push_back(0); + } + + // We arrive at a category of instructions with the same segment value. + // Now delegate to the sub filter chooser for further decodings. + // The case may fallthrough, which happens if the remaining well-known + // encoding bits do not match exactly. + Filter.second->emitTableEntries(TableInfo); + + // Now that we've emitted the body of the handler, update the NumToSkip + // of the filter itself to be able to skip forward when false. Subtract + // two as to account for the width of the NumToSkip field itself. + if (PrevFilter) { + uint32_t const NumToSkip = Table.size() - PrevFilter - 3; + assert(NumToSkip < (1u << 24) && + "disassembler decoding table too large!"); + Table[PrevFilter] = (uint8_t)NumToSkip; + Table[PrevFilter + 1] = (uint8_t)(NumToSkip >> 8); + Table[PrevFilter + 2] = (uint8_t)(NumToSkip >> 16); + } + } + + // Any remaining unresolved fixups bubble up to the parent fixup scope. + assert(TableInfo.FixupStack.size() > 1 && "fixup stack underflow!"); + FixupScopeList::iterator const Source = TableInfo.FixupStack.end() - 1; + FixupScopeList::iterator const Dest = Source - 1; + llvm::append_range(*Dest, *Source); + TableInfo.FixupStack.pop_back(); + + // If there is no fallthrough, then the final filter should get fixed + // up according to the enclosing scope rather than the current position. + if (!HasFallthrough) + TableInfo.FixupStack.back().push_back(PrevFilter); +} + +// Returns the number of fanout produced by the filter. More fanout implies +// the filter distinguishes more categories of instructions. +unsigned Filter::usefulness() const { + if (!VariableInstructions.empty()) + return FilteredInstructions.size(); + return FilteredInstructions.size() + 1; +} + +} // end namespace tblgen_decoder_emitter Index: llvm/utils/TableGen/DecoderEmitter/FilterChooser.cpp =================================================================== --- /dev/null +++ llvm/utils/TableGen/DecoderEmitter/FilterChooser.cpp @@ -0,0 +1,856 @@ +//===---------------- FilterChooser.cpp - Filter Chooser --------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Contains the FilterChooser class used by the Decoder Emitter. +// The FilterChooser selects the best Filter which separates +// several instruction sets. +// +//===----------------------------------------------------------------------===// + +#include "DecoderEmitter.h" + +using namespace llvm; + +namespace tblgen_decoder_emitter { + +#define DEBUG_TYPE "decoder-emitter-FilterChooser" +STATISTIC(NumEncodingsSupported, "Number of encodings supported"); + +// Populates the insn given the uid. +void FilterChooser::insnWithID(insn_t &Insn, unsigned Opcode) const { + BitsInit const &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. + const RecordVal *RV = + AllInstructions[Opcode].EncodingDef->getValue("SoftFail"); + const BitsInit *SFBits = RV ? dyn_cast(RV->getValue()) : nullptr; + for (unsigned I = 0; I < Bits.getNumBits(); ++I) { + if (SFBits && bitFromBits(*SFBits, I) == BIT_TRUE) + Insn[I] = BIT_UNSET; + else + Insn[I] = bitFromBits(Bits, I); + } +} + +// Emit the name of the encoding/instruction pair. +void FilterChooser::emitNameWithID(raw_ostream &ErrOS, unsigned Opcode) const { + const Record *EncodingDef = AllInstructions[Opcode].EncodingDef; + const Record *InstDef = AllInstructions[Opcode].Inst->TheDef; + if (EncodingDef != InstDef) + ErrOS << EncodingDef->getName() << ":"; + ErrOS << InstDef->getName(); +} + +// Populates the field of the insn given the start position and the number of +// consecutive bits to scan for. +// +// Returns false if and on the first uninitialized bit value encountered. +// Returns true, otherwise. +bool FilterChooser::fieldFromInsn(uint64_t &Field, insn_t &Insn, + unsigned StartBit, unsigned NumBits) const { + Field = 0; + + for (unsigned I = 0; I < NumBits; ++I) { + if (Insn[StartBit + I] == BIT_UNSET) + return false; + + if (Insn[StartBit + I] == BIT_TRUE) + Field = Field | (1ULL << I); + } + + return true; +} + +/// dumpFilterArray - dumpFilterArray prints out debugging info for the given +/// filter array as a series of chars. +void FilterChooser::dumpFilterArray( + raw_ostream &ErrOS, const std::vector &Filter) const { + for (unsigned BitIndex = BitWidth; BitIndex > 0; BitIndex--) { + switch (Filter[BitIndex - 1]) { + case BIT_UNFILTERED: + ErrOS << "."; + break; + case BIT_UNSET: + ErrOS << "_"; + break; + case BIT_TRUE: + ErrOS << "1"; + break; + case BIT_FALSE: + ErrOS << "0"; + break; + } + } +} + +/// dumpStack - dumpStack traverses the filter chooser chain and calls +/// dumpFilterArray on each filter chooser up to the top level one. +void FilterChooser::dumpStack(raw_ostream &ErrOS, const char *Prefix) const { + const FilterChooser *Current = this; + + while (Current) { + ErrOS << Prefix; + dumpFilterArray(ErrOS, Current->FilterBitValues); + ErrOS << '\n'; + Current = Current->Parent; + } +} + +// Calculates the island(s) needed to decode the instruction. +// This returns a list of undecoded bits of an instructions, for example, +// Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be +// decoded bits in order to verify that the instruction matches the Opcode. +unsigned FilterChooser::getIslands(std::vector &StartBits, + std::vector &EndBits, + std::vector &FieldVals, + const insn_t &Insn) const { + unsigned Num, BitNo; + Num = BitNo = 0; + + uint64_t FieldVal = 0; + + // 0: Init + // 1: Water (the bit value does not affect decoding) + // 2: Island (well-known bit value needed for decoding) + int State = 0; + + for (unsigned I = 0; I < BitWidth; ++I) { + int64_t const Val = tblgen_decoder_emitter::value(Insn[I]); + bool const Filtered = positionFiltered(I); + switch (State) { + default: + llvm_unreachable("Unreachable code!"); + case 0: + case 1: + if (Filtered || Val == -1) + State = 1; // Still in Water + else { + State = 2; // Into the Island + BitNo = 0; + StartBits.push_back(I); + FieldVal = Val; + } + break; + case 2: + if (Filtered || Val == -1) { + State = 1; // Into the Water + EndBits.push_back(I - 1); + FieldVals.push_back(FieldVal); + ++Num; + } else { + State = 2; // Still in Island + ++BitNo; + FieldVal = FieldVal | Val << BitNo; + } + break; + } + } + // If we are still in Island after the loop, do some housekeeping. + if (State == 2) { + EndBits.push_back(BitWidth - 1); + FieldVals.push_back(FieldVal); + ++Num; + } + + assert(StartBits.size() == Num && EndBits.size() == Num && + FieldVals.size() == Num); + return Num; +} + +void FilterChooser::emitBinaryParser(raw_ostream &O, unsigned &Indentation, + const OperandInfo &OpInfo, + bool &OpHasCompleteDecoder) const { + const std::string &Decoder = OpInfo.Decoder; + + bool const UseInsertBits = OpInfo.numFields() != 1 || OpInfo.InitValue != 0; + + if (UseInsertBits) { + O.indent(Indentation) << "tmp = 0x"; + O.write_hex(OpInfo.InitValue); + O << ";\n"; + } + + for (const EncodingField &EF : OpInfo) { + O.indent(Indentation); + if (UseInsertBits) + O << "insertBits(tmp, "; + else + O << "tmp = "; + O << "fieldFromInstruction(insn, " << EF.Base << ", " << EF.Width << ')'; + if (UseInsertBits) + O << ", " << EF.Offset << ", " << EF.Width << ')'; + else if (EF.Offset != 0) + O << " << " << EF.Offset; + O << ";\n"; + } + + if (Decoder != "") { + OpHasCompleteDecoder = OpInfo.HasCompleteDecoder; + O.indent(Indentation) << Emitter->GuardPrefix << Decoder + << "(MI, tmp, Address, Decoder)" + << Emitter->GuardPostfix << " { " + << (OpHasCompleteDecoder ? "" + : "DecodeComplete = false; ") + << "return MCDisassembler::Fail; }\n"; + } else { + OpHasCompleteDecoder = true; + O.indent(Indentation) << "MI.addOperand(MCOperand::createImm(tmp));\n"; + } +} + +void FilterChooser::emitDecoder(raw_ostream &OS, unsigned Indentation, + unsigned Opc, bool &HasCompleteDecoder) const { + HasCompleteDecoder = true; + + for (const auto &Op : Operands.find(Opc)->second) { + // If a custom instruction decoder was specified, use that. + if (Op.numFields() == 0 && !Op.Decoder.empty()) { + HasCompleteDecoder = Op.HasCompleteDecoder; + OS.indent(Indentation) + << Emitter->GuardPrefix << Op.Decoder + << "(MI, insn, Address, Decoder)" << Emitter->GuardPostfix << " { " + << (HasCompleteDecoder ? "" : "DecodeComplete = false; ") + << "return MCDisassembler::Fail; }\n"; + break; + } + + bool OpHasCompleteDecoder; + emitBinaryParser(OS, Indentation, Op, OpHasCompleteDecoder); + if (!OpHasCompleteDecoder) + HasCompleteDecoder = false; + } +} + +unsigned FilterChooser::getDecoderIndex(DecoderSet &Decoders, unsigned Opc, + bool &HasCompleteDecoder) const { + // Build up the predicate string. + SmallString<256> Decoder; + // FIXME: emitDecoder() function can take a buffer directly rather than + // a stream. + raw_svector_ostream S(Decoder); + unsigned const I = 4; + emitDecoder(S, I, Opc, HasCompleteDecoder); + + // Using the full decoder string as the key value here is a bit + // heavyweight, but is effective. If the string comparisons become a + // performance concern, we can implement a mangling of the predicate + // data easily enough with a map back to the actual string. That's + // overkill for now, though. + + // Make sure the predicate is in the table. + Decoders.insert(CachedHashString(Decoder)); + // Now figure out the index for when we write out the table. + DecoderSet::const_iterator P = find(Decoders, Decoder.str()); + return (unsigned)(P - Decoders.begin()); +} + +// If ParenIfBinOp is true, print a surrounding () if Val uses && or ||. +bool FilterChooser::emitPredicateMatchAux(const Init &Val, bool ParenIfBinOp, + raw_ostream &OS) const { + if (auto *D = dyn_cast(&Val)) { + if (!D->getDef()->isSubClassOf("SubtargetFeature")) + return true; + OS << "Bits[" << Emitter->PredicateNamespace << "::" << D->getAsString() + << "]"; + return false; + } + if (auto *D = dyn_cast(&Val)) { + std::string const Op = D->getOperator()->getAsString(); + if (Op == "not" && D->getNumArgs() == 1) { + OS << '!'; + return emitPredicateMatchAux(*D->getArg(0), true, OS); + } + if ((Op == "any_of" || Op == "all_of") && D->getNumArgs() > 0) { + bool const Paren = + D->getNumArgs() > 1 && std::exchange(ParenIfBinOp, true); + if (Paren) + OS << '('; + ListSeparator LS(Op == "any_of" ? " || " : " && "); + for (auto *Arg : D->getArgs()) { + OS << LS; + if (emitPredicateMatchAux(*Arg, ParenIfBinOp, OS)) + return true; + } + if (Paren) + OS << ')'; + return false; + } + } + return true; +} + +bool FilterChooser::emitPredicateMatch(raw_ostream &O, unsigned &Indentation, + unsigned Opc) const { + ListInit *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; + + if (!isa(Pred->getValue("AssemblerCondDag")->getValue())) + continue; + + if (!IsFirstEmission) + O << " && "; + if (emitPredicateMatchAux(*Pred->getValueAsDag("AssemblerCondDag"), + Predicates->size() > 1, O)) + PrintFatalError(Pred->getLoc(), "Invalid AssemblerCondDag!"); + IsFirstEmission = false; + } + return !Predicates->empty(); +} + +bool FilterChooser::doesOpcodeNeedPredicate(unsigned Opc) const { + ListInit *Predicates = + AllInstructions[Opc].EncodingDef->getValueAsListInit("Predicates"); + for (unsigned I = 0; I < Predicates->size(); ++I) { + Record *Pred = Predicates->getElementAsRecord(I); + if (!Pred->getValue("AssemblerMatcherPredicate")) + continue; + + if (isa(Pred->getValue("AssemblerCondDag")->getValue())) + return true; + } + return false; +} + +unsigned FilterChooser::getPredicateIndex(DecoderTableInfo &TableInfo, + StringRef Predicate) const { + // Using the full predicate string as the key value here is a bit + // heavyweight, but is effective. If the string comparisons become a + // performance concern, we can implement a mangling of the predicate + // data easily enough with a map back to the actual string. That's + // overkill for now, though. + + // Make sure the predicate is in the table. + TableInfo.Predicates.insert(CachedHashString(Predicate)); + // Now figure out the index for when we write out the table. + PredicateSet::const_iterator P = find(TableInfo.Predicates, Predicate); + return (unsigned)(P - TableInfo.Predicates.begin()); +} + +void FilterChooser::emitPredicateTableEntry(DecoderTableInfo &TableInfo, + unsigned Opc) const { + if (!doesOpcodeNeedPredicate(Opc)) + return; + + // Build up the predicate string. + SmallString<256> Predicate; + // FIXME: emitPredicateMatch() functions can take a buffer directly rather + // than a stream. + raw_svector_ostream PS(Predicate); + unsigned I = 0; + emitPredicateMatch(PS, I, Opc); + + // Figure out the index into the predicate table for the predicate just + // computed. + unsigned const PIdx = getPredicateIndex(TableInfo, PS.str()); + SmallString<16> PBytes; + raw_svector_ostream S(PBytes); + encodeULEB128(PIdx, S); + + TableInfo.Table.push_back(MCD::OPC_CheckPredicate); + // Predicate index + for (unsigned I = 0, E = PBytes.size(); I != E; ++I) + TableInfo.Table.push_back(PBytes[I]); + // Push location for NumToSkip backpatching. + TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); + TableInfo.Table.push_back(0); + TableInfo.Table.push_back(0); + TableInfo.Table.push_back(0); +} + +void FilterChooser::emitSoftFailTableEntry(DecoderTableInfo &TableInfo, + unsigned Opc) const { + const RecordVal *RV = AllInstructions[Opc].EncodingDef->getValue("SoftFail"); + BitsInit *SFBits = RV ? dyn_cast(RV->getValue()) : nullptr; + + if (!SFBits) + return; + 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 const B = bitFromBits(*SFBits, I); + bit_value_t const 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! + 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 const NeedPositiveMask = PositiveMask.getBoolValue(); + bool const NeedNegativeMask = NegativeMask.getBoolValue(); + + if (!NeedPositiveMask && !NeedNegativeMask) + return; + + TableInfo.Table.push_back(MCD::OPC_SoftFail); + + SmallString<16> MaskBytes; + raw_svector_ostream S(MaskBytes); + if (NeedPositiveMask) { + encodeULEB128(PositiveMask.getZExtValue(), S); + for (unsigned I = 0, E = MaskBytes.size(); I != E; ++I) + TableInfo.Table.push_back(MaskBytes[I]); + } else + TableInfo.Table.push_back(0); + if (NeedNegativeMask) { + MaskBytes.clear(); + encodeULEB128(NegativeMask.getZExtValue(), S); + for (unsigned I = 0, E = MaskBytes.size(); I != E; ++I) + TableInfo.Table.push_back(MaskBytes[I]); + } else + TableInfo.Table.push_back(0); +} + +// Emits table entries to decode the singleton. +void FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo, + EncodingIDAndOpcode Opc) const { + std::vector StartBits; + std::vector EndBits; + std::vector FieldVals; + insn_t Insn; + insnWithID(Insn, Opc.EncodingID); + + // Look for islands of undecoded bits of the singleton. + getIslands(StartBits, EndBits, FieldVals, Insn); + + unsigned const Size = StartBits.size(); + + // Emit the predicate table entry if one is needed. + emitPredicateTableEntry(TableInfo, Opc.EncodingID); + + // Check any additional encoding fields needed. + for (unsigned I = Size; I != 0; --I) { + unsigned NumBits = EndBits[I - 1] - StartBits[I - 1] + 1; + TableInfo.Table.push_back(MCD::OPC_CheckField); + TableInfo.Table.push_back(StartBits[I - 1]); + TableInfo.Table.push_back(NumBits); + uint8_t Buffer[16], *P; + encodeULEB128(FieldVals[I - 1], Buffer); + for (P = Buffer; *P >= 128; ++P) + TableInfo.Table.push_back(*P); + TableInfo.Table.push_back(*P); + // Push location for NumToSkip backpatching. + TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); + // The fixup is always 24-bits, so go ahead and allocate the space + // in the table so all our relative position calculations work OK even + // before we fully resolve the real value here. + TableInfo.Table.push_back(0); + TableInfo.Table.push_back(0); + TableInfo.Table.push_back(0); + } + + // Check for soft failure of the match. + emitSoftFailTableEntry(TableInfo, Opc.EncodingID); + + bool HasCompleteDecoder; + unsigned const DIdx = + getDecoderIndex(TableInfo.Decoders, Opc.EncodingID, HasCompleteDecoder); + + // Produce OPC_Decode or OPC_TryDecode opcode based on the information + // whether the instruction decoder is complete or not. If it is complete + // then it handles all possible values of remaining variable/unfiltered bits + // and for any value can determine if the bitpattern is a valid instruction + // or not. This means OPC_Decode will be the final step in the decoding + // process. If it is not complete, then the Fail return code from the + // decoder method indicates that additional processing should be done to see + // if there is any other instruction that also matches the bitpattern and + // can decode it. + TableInfo.Table.push_back(HasCompleteDecoder ? MCD::OPC_Decode + : MCD::OPC_TryDecode); + NumEncodingsSupported++; + uint8_t Buffer[16], *P; + encodeULEB128(Opc.Opcode, Buffer); + for (P = Buffer; *P >= 128; ++P) + TableInfo.Table.push_back(*P); + TableInfo.Table.push_back(*P); + + SmallString<16> Bytes; + raw_svector_ostream S(Bytes); + encodeULEB128(DIdx, S); + + // Decoder index + for (unsigned I = 0, E = Bytes.size(); I != E; ++I) + TableInfo.Table.push_back(Bytes[I]); + + if (!HasCompleteDecoder) { + // Push location for NumToSkip backpatching. + TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); + // Allocate the space for the fixup. + TableInfo.Table.push_back(0); + TableInfo.Table.push_back(0); + TableInfo.Table.push_back(0); + } +} + +// Emits table entries to decode the singleton, and then to decode the rest. +void FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo, + const Filter &Best) const { + EncodingIDAndOpcode const Opc = Best.getSingletonOpc(); + + // complex singletons need predicate checks from the first singleton + // to refer forward to the variable filterchooser that follows. + TableInfo.FixupStack.emplace_back(); + + emitSingletonTableEntry(TableInfo, Opc); + + resolveTableFixups(TableInfo.Table, TableInfo.FixupStack.back(), + TableInfo.Table.size()); + TableInfo.FixupStack.pop_back(); + + Best.getVariableFC().emitTableEntries(TableInfo); +} + +// Assign a single filter and run with it. Top level API client can initialize +// with a single filter to start the filtering process. +void FilterChooser::runSingleFilter(unsigned StartBit, unsigned NumBit, + bool Mixed) { + Filters.clear(); + Filters.emplace_back(*this, StartBit, NumBit, true); + BestIndex = 0; // Sole Filter instance to choose from. + bestFilter().recurse(); +} + +// reportRegion is a helper function for filterProcessor to mark a region as +// eligible for use as a filter region. +void FilterChooser::reportRegion(bitAttr_t RA, unsigned StartBit, + unsigned BitIndex, bool AllowMixed) { + if (RA == ATTR_MIXED && AllowMixed) + Filters.emplace_back(*this, StartBit, BitIndex - StartBit, true); + else if (RA == ATTR_ALL_SET && !AllowMixed) + Filters.emplace_back(*this, StartBit, BitIndex - StartBit, false); +} + +// FilterProcessor scans the well-known encoding bits of the instructions and +// builds up a list of candidate filters. It chooses the best filter and +// recursively descends down the decoding tree. +bool FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { + Filters.clear(); + BestIndex = -1; + unsigned const NumInstructions = Opcodes.size(); + + assert(NumInstructions && "Filter created with no instructions"); + + // No further filtering is necessary. + if (NumInstructions == 1) + return true; + + // Heuristics. See also doFilter()'s "Heuristics" comment when num of + // instructions is 3. + if (AllowMixed && !Greedy) { + assert(NumInstructions == 3); + + for (auto Opcode : Opcodes) { + std::vector StartBits; + std::vector EndBits; + std::vector FieldVals; + insn_t Insn; + + insnWithID(Insn, Opcode.EncodingID); + + // Look for islands of undecoded bits of any instruction. + if (getIslands(StartBits, EndBits, FieldVals, Insn) > 0) { + // Found an instruction with island(s). Now just assign a filter. + runSingleFilter(StartBits[0], EndBits[0] - StartBits[0] + 1, true); + return true; + } + } + } + + unsigned BitIndex; + + // We maintain BIT_WIDTH copies of the bitAttrs automaton. + // The automaton consumes the corresponding bit from each + // instruction. + // + // Input symbols: 0, 1, and _ (unset). + // States: NONE, FILTERED, ALL_SET, ALL_UNSET, and MIXED. + // Initial state: NONE. + // + // (NONE) ------- [01] -> (ALL_SET) + // (NONE) ------- _ ----> (ALL_UNSET) + // (ALL_SET) ---- [01] -> (ALL_SET) + // (ALL_SET) ---- _ ----> (MIXED) + // (ALL_UNSET) -- [01] -> (MIXED) + // (ALL_UNSET) -- _ ----> (ALL_UNSET) + // (MIXED) ------ . ----> (MIXED) + // (FILTERED)---- . ----> (FILTERED) + + std::vector BitAttrs; + + // FILTERED bit positions provide no entropy and are not worthy of pursuing. + // Filter::recurse() set either BIT_TRUE or BIT_FALSE for each position. + for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) + if (FilterBitValues[BitIndex] == BIT_TRUE || + FilterBitValues[BitIndex] == BIT_FALSE) + BitAttrs.push_back(ATTR_FILTERED); + else + BitAttrs.push_back(ATTR_NONE); + + for (unsigned InsnIndex = 0; InsnIndex < NumInstructions; ++InsnIndex) { + insn_t Insn; + + insnWithID(Insn, Opcodes[InsnIndex].EncodingID); + + for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { + switch (BitAttrs[BitIndex]) { + case ATTR_NONE: + if (Insn[BitIndex] == BIT_UNSET) + BitAttrs[BitIndex] = ATTR_ALL_UNSET; + else + BitAttrs[BitIndex] = ATTR_ALL_SET; + break; + case ATTR_ALL_SET: + if (Insn[BitIndex] == BIT_UNSET) + BitAttrs[BitIndex] = ATTR_MIXED; + break; + case ATTR_ALL_UNSET: + if (Insn[BitIndex] != BIT_UNSET) + BitAttrs[BitIndex] = ATTR_MIXED; + break; + case ATTR_MIXED: + case ATTR_FILTERED: + break; + } + } + } + + // The regionAttr automaton consumes the bitAttrs automatons' state, + // lowest-to-highest. + // + // Input symbols: F(iltered), (all_)S(et), (all_)U(nset), M(ixed) + // States: NONE, ALL_SET, MIXED + // Initial state: NONE + // + // (NONE) ----- F --> (NONE) + // (NONE) ----- S --> (ALL_SET) ; and set region start + // (NONE) ----- U --> (NONE) + // (NONE) ----- M --> (MIXED) ; and set region start + // (ALL_SET) -- F --> (NONE) ; and report an ALL_SET region + // (ALL_SET) -- S --> (ALL_SET) + // (ALL_SET) -- U --> (NONE) ; and report an ALL_SET region + // (ALL_SET) -- M --> (MIXED) ; and report an ALL_SET region + // (MIXED) ---- F --> (NONE) ; and report a MIXED region + // (MIXED) ---- S --> (ALL_SET) ; and report a MIXED region + // (MIXED) ---- U --> (NONE) ; and report a MIXED region + // (MIXED) ---- M --> (MIXED) + + bitAttr_t RA = ATTR_NONE; + unsigned StartBit = 0; + + for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { + bitAttr_t const BitAttr = BitAttrs[BitIndex]; + + assert(BitAttr != ATTR_NONE && "Bit without attributes"); + + switch (RA) { + case ATTR_NONE: + switch (BitAttr) { + case ATTR_FILTERED: + break; + case ATTR_ALL_SET: + StartBit = BitIndex; + RA = ATTR_ALL_SET; + break; + case ATTR_ALL_UNSET: + break; + case ATTR_MIXED: + StartBit = BitIndex; + RA = ATTR_MIXED; + break; + default: + llvm_unreachable("Unexpected bitAttr!"); + } + break; + case ATTR_ALL_SET: + switch (BitAttr) { + case ATTR_FILTERED: + reportRegion(RA, StartBit, BitIndex, AllowMixed); + RA = ATTR_NONE; + break; + case ATTR_ALL_SET: + break; + case ATTR_ALL_UNSET: + reportRegion(RA, StartBit, BitIndex, AllowMixed); + RA = ATTR_NONE; + break; + case ATTR_MIXED: + reportRegion(RA, StartBit, BitIndex, AllowMixed); + StartBit = BitIndex; + RA = ATTR_MIXED; + break; + default: + llvm_unreachable("Unexpected bitAttr!"); + } + break; + case ATTR_MIXED: + switch (BitAttr) { + case ATTR_FILTERED: + reportRegion(RA, StartBit, BitIndex, AllowMixed); + StartBit = BitIndex; + RA = ATTR_NONE; + break; + case ATTR_ALL_SET: + reportRegion(RA, StartBit, BitIndex, AllowMixed); + StartBit = BitIndex; + RA = ATTR_ALL_SET; + break; + case ATTR_ALL_UNSET: + reportRegion(RA, StartBit, BitIndex, AllowMixed); + RA = ATTR_NONE; + break; + case ATTR_MIXED: + break; + default: + llvm_unreachable("Unexpected bitAttr!"); + } + break; + case ATTR_ALL_UNSET: + llvm_unreachable("regionAttr state machine has no ATTR_UNSET state"); + case ATTR_FILTERED: + llvm_unreachable("regionAttr state machine has no ATTR_FILTERED state"); + } + } + + // At the end, if we're still in ALL_SET or MIXED states, report a region + switch (RA) { + case ATTR_NONE: + break; + case ATTR_FILTERED: + break; + case ATTR_ALL_SET: + reportRegion(RA, StartBit, BitIndex, AllowMixed); + break; + case ATTR_ALL_UNSET: + break; + case ATTR_MIXED: + reportRegion(RA, StartBit, BitIndex, AllowMixed); + break; + } + + // We have finished with the filter processings. Now it's time to choose + // the best performing filter. + BestIndex = 0; + bool AllUseless = true; + unsigned BestScore = 0; + + for (unsigned I = 0, E = Filters.size(); I != E; ++I) { + unsigned const Usefulness = Filters[I].usefulness(); + + if (Usefulness) + AllUseless = false; + + if (Usefulness > BestScore) { + BestIndex = I; + BestScore = Usefulness; + } + } + + if (!AllUseless) + bestFilter().recurse(); + + return !AllUseless; +} // end of FilterChooser::filterProcessor(bool) + +// Decides on the best configuration of filter(s) to use in order to decode +// the instructions. A conflict of instructions may occur, in which case we +// dump the conflict set to the standard error. +void FilterChooser::doFilter() { + unsigned const Num = Opcodes.size(); + assert(Num && "FilterChooser created with no instructions"); + + // Try regions of consecutive known bit values first. + if (filterProcessor(false)) + return; + + // Then regions of mixed bits (both known and unitialized bit values allowed). + if (filterProcessor(true)) + return; + + // Heuristics to cope with conflict set {t2CMPrs, t2SUBSrr, t2SUBSrs} where + // no single instruction for the maximum ATTR_MIXED region Inst{14-4} has a + // well-known encoding pattern. In such case, we backtrack and scan for the + // the very first consecutive ATTR_ALL_SET region and assign a filter to it. + if (Num == 3 && filterProcessor(true, false)) + return; + + // If we come to here, the instruction decoding has failed. + // Set the BestIndex to -1 to indicate so. + BestIndex = -1; +} + +// emitTableEntries - Emit state machine entries to decode our share of +// instructions. +void FilterChooser::emitTableEntries(DecoderTableInfo &TableInfo) const { + if (Opcodes.size() == 1) { + // There is only one instruction in the set, which is great! + // Call emitSingletonDecoder() to see whether there are any remaining + // encodings bits. + emitSingletonTableEntry(TableInfo, Opcodes[0]); + return; + } + + // Choose the best filter to do the decodings! + if (BestIndex != -1) { + const Filter &Best = Filters[BestIndex]; + if (Best.getNumFiltered() == 1) + emitSingletonTableEntry(TableInfo, Best); + else + Best.emitTableEntry(TableInfo); + return; + } + + // We don't know how to decode these instructions! Dump the + // conflict set and bail. + + // Print out useful conflict information for postmortem analysis. + errs() << "Decoding Conflict:\n"; + + dumpStack(errs(), "\t\t"); + + for (auto Opcode : Opcodes) { + errs() << '\t'; + emitNameWithID(errs(), Opcode.EncodingID); + errs() << " "; + dumpBits( + errs(), + getBitsField(*AllInstructions[Opcode.EncodingID].EncodingDef, "Inst")); + errs() << '\n'; + } +} +} // end namespace tblgen_decoder_emitter Index: llvm/utils/TableGen/DecoderEmitter/HelperFunctions.cpp =================================================================== --- /dev/null +++ llvm/utils/TableGen/DecoderEmitter/HelperFunctions.cpp @@ -0,0 +1,798 @@ +//===-- HelperFunctions.cpp - Decoder Emitter Helper Functions --*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Contains the helper functions used by the Decoder Emitter classes. +// +//===----------------------------------------------------------------------===// + +#include "DecoderEmitter.h" +using namespace llvm; +namespace tblgen_decoder_emitter { + +#define DEBUG_TYPE "decoder-emitter-HelperFunctions" + +bool valueSet(bit_value_t V) { return (V == BIT_TRUE || V == BIT_FALSE); } + +bool valueNotSet(bit_value_t V) { return (V == BIT_UNSET); } + +int value(bit_value_t V) { + return tblgen_decoder_emitter::valueNotSet(V) ? -1 : (V == BIT_FALSE ? 0 : 1); +} + +bit_value_t bitFromBits(const BitsInit &Bits, unsigned Index) { + if (BitInit *Bit = dyn_cast(Bits.getBit(Index))) + return Bit->getValue() ? BIT_TRUE : BIT_FALSE; + + // The bit is uninitialized. + return BIT_UNSET; +} + +// Prints the bit value for each position. +void dumpBits(raw_ostream &ErrOS, const BitsInit &Bits) { + for (unsigned Index = Bits.getNumBits(); Index > 0; --Index) { + switch (tblgen_decoder_emitter::bitFromBits(Bits, Index - 1)) { + case BIT_TRUE: + ErrOS << "1"; + break; + case BIT_FALSE: + ErrOS << "0"; + break; + case BIT_UNSET: + ErrOS << "_"; + break; + default: + llvm_unreachable("unexpected return value from bitFromBits"); + } + } +} + +BitsInit &getBitsField(const Record &Def, StringRef Str) { + const RecordVal *RV = Def.getValue(Str); + if (BitsInit *Bits = dyn_cast(RV->getValue())) + return *Bits; + + // variable length instruction + VarLenInst const VLI = VarLenInst(cast(RV->getValue()), RV); + SmallVector Bits; + + for (auto &SI : VLI) { + if (const BitsInit *BI = dyn_cast(SI.Value)) { + for (unsigned Idx = 0U; Idx < BI->getNumBits(); ++Idx) { + Bits.push_back(BI->getBit(Idx)); + } + } else if (const BitInit *BI = dyn_cast(SI.Value)) { + Bits.push_back(const_cast(BI)); + } else { + for (unsigned Idx = 0U; Idx < SI.BitWidth; ++Idx) + Bits.push_back(UnsetInit::get(Def.getRecords())); + } + } + + return *BitsInit::get(Def.getRecords(), Bits); +} + +void resolveTableFixups(DecoderTable &Table, const FixupList &Fixups, + uint32_t DestIdx) { + // Any NumToSkip fixups in the current scope can resolve to the + // current location. + for (FixupList::const_reverse_iterator I = Fixups.rbegin(), E = Fixups.rend(); + I != E; ++I) { + // Calculate the distance from the byte following the fixup entry byte + // to the destination. The Target is calculated from after the 16-bit + // NumToSkip entry itself, so subtract two from the displacement here + // to account for that. + uint32_t const FixupIdx = *I; + uint32_t const Delta = DestIdx - FixupIdx - 3; + // Our NumToSkip entries are 24-bits. Make sure our table isn't too + // big. + assert(Delta < (1u << 24)); + Table[FixupIdx] = (uint8_t)Delta; + Table[FixupIdx + 1] = (uint8_t)(Delta >> 8); + Table[FixupIdx + 2] = (uint8_t)(Delta >> 16); + } +} + +std::string findOperandDecoderMethod(Record *Record) { + std::string Decoder; + + RecordVal *DecoderString = Record->getValue("DecoderMethod"); + StringInit *String = + DecoderString ? dyn_cast(DecoderString->getValue()) : nullptr; + if (String) { + Decoder = std::string(String->getValue()); + if (!Decoder.empty()) + return Decoder; + } + + if (Record->isSubClassOf("RegisterOperand")) + Record = Record->getValueAsDef("RegClass"); + + if (Record->isSubClassOf("RegisterClass")) { + Decoder = "Decode" + Record->getName().str() + "RegisterClass"; + } else if (Record->isSubClassOf("PointerLikeRegClass")) { + Decoder = "DecodePointerLikeRegClass" + + utostr(Record->getValueAsInt("RegClassKind")); + } + + return Decoder; +} + +OperandInfo getOpInfo(Record *TypeRecord) { + std::string const Decoder = findOperandDecoderMethod(TypeRecord); + + RecordVal *HasCompleteDecoderVal = TypeRecord->getValue("hasCompleteDecoder"); + BitInit *HasCompleteDecoderBit = + HasCompleteDecoderVal + ? dyn_cast(HasCompleteDecoderVal->getValue()) + : nullptr; + bool const HasCompleteDecoder = + HasCompleteDecoderBit ? HasCompleteDecoderBit->getValue() : true; + + return OperandInfo(Decoder, HasCompleteDecoder); +} + +void parseVarLenInstOperand(const Record &Def, + std::vector &Operands, + const CodeGenInstruction &CGI) { + + const RecordVal *RV = Def.getValue("Inst"); + VarLenInst const VLI(cast(RV->getValue()), RV); + SmallVector TiedTo; + + for (unsigned Idx = 0; Idx < CGI.Operands.size(); ++Idx) { + auto &Op = CGI.Operands[Idx]; + if (Op.MIOperandInfo && Op.MIOperandInfo->getNumArgs() > 0) + for (auto *Arg : Op.MIOperandInfo->getArgs()) + Operands.push_back(getOpInfo(cast(Arg)->getDef())); + else + Operands.push_back(getOpInfo(Op.Rec)); + + int const TiedReg = Op.getTiedRegister(); + TiedTo.push_back(-1); + if (TiedReg != -1) { + TiedTo[Idx] = TiedReg; + TiedTo[TiedReg] = Idx; + } + } + + unsigned CurrBitPos = 0; + for (auto &EncodingSegment : VLI) { + unsigned Offset = 0; + StringRef OpName; + + if (const StringInit *SI = dyn_cast(EncodingSegment.Value)) { + OpName = SI->getValue(); + } else if (const DagInit *DI = dyn_cast(EncodingSegment.Value)) { + OpName = cast(DI->getArg(0))->getValue(); + Offset = cast(DI->getArg(2))->getValue(); + } + + if (!OpName.empty()) { + auto OpSubOpPair = + const_cast(CGI).Operands.ParseOperandName( + OpName); + unsigned const OpIdx = + CGI.Operands.getFlattenedOperandNumber(OpSubOpPair); + Operands[OpIdx].addField(CurrBitPos, EncodingSegment.BitWidth, Offset); + + int const TiedReg = TiedTo[OpSubOpPair.first]; + if (TiedReg != -1) { + unsigned const OpIdx = CGI.Operands.getFlattenedOperandNumber( + std::make_pair(TiedReg, OpSubOpPair.second)); + Operands[OpIdx].addField(CurrBitPos, EncodingSegment.BitWidth, Offset); + } + } + + CurrBitPos += EncodingSegment.BitWidth; + } +} + +unsigned +populateInstruction(CodeGenTarget &Target, const Record &EncodingDef, + const CodeGenInstruction &CGI, unsigned Opc, + std::map> &Operands, + bool IsVarLenInst) { + const Record &Def = *CGI.TheDef; + // If all the bit positions are not specified; do not decode this instruction. + // We are bound to fail! For proper disassembly, the well-known encoding bits + // of the instruction must be fully specified. + + BitsInit const &Bits = getBitsField(EncodingDef, "Inst"); + if (Bits.allInComplete()) + return 0; + + std::vector InsnOperands; + + // If the instruction has specified a custom decoding hook, use that instead + // of trying to auto-generate the decoder. + StringRef const InstDecoder = EncodingDef.getValueAsString("DecoderMethod"); + if (InstDecoder != "") { + bool const HasCompleteInstDecoder = + EncodingDef.getValueAsBit("hasCompleteDecoder"); + InsnOperands.push_back( + OperandInfo(std::string(InstDecoder), HasCompleteInstDecoder)); + Operands[Opc] = InsnOperands; + return Bits.getNumBits(); + } + + // Generate a description of the operand of the instruction that we know + // how to decode automatically. + // FIXME: We'll need to have a way to manually override this as needed. + + // Gather the outputs/inputs of the instruction, so we can find their + // positions in the encoding. This assumes for now that they appear in the + // MCInst in the order that they're listed. + std::vector> InOutOperands; + DagInit *Out = Def.getValueAsDag("OutOperandList"); + DagInit *In = Def.getValueAsDag("InOperandList"); + for (unsigned I = 0; I < Out->getNumArgs(); ++I) + InOutOperands.push_back( + std::make_pair(Out->getArg(I), Out->getArgNameStr(I))); + for (unsigned I = 0; I < In->getNumArgs(); ++I) + InOutOperands.push_back( + std::make_pair(In->getArg(I), In->getArgNameStr(I))); + + // Search for tied operands, so that we can correctly instantiate + // operands that are not explicitly represented in the encoding. + std::map TiedNames; + for (unsigned I = 0; I < CGI.Operands.size(); ++I) { + int const TiedTo = CGI.Operands[I].getTiedRegister(); + if (TiedTo != -1) { + std::pair const SO = + CGI.Operands.getSubOperandNumber(TiedTo); + TiedNames[std::string(InOutOperands[I].second)] = + std::string(InOutOperands[SO.first].second); + TiedNames[std::string(InOutOperands[SO.first].second)] = + std::string(InOutOperands[I].second); + } + } + + if (IsVarLenInst) { + parseVarLenInstOperand(EncodingDef, InsnOperands, CGI); + } else { + std::map> NumberedInsnOperands; + std::set NumberedInsnOperandsNoTie; + if (Target.getInstructionSet()->getValueAsBit( + "decodePositionallyEncodedOperands")) { + const std::vector &Vals = Def.getValues(); + unsigned NumberedOp = 0; + + std::set NamedOpIndices; + if (Target.getInstructionSet()->getValueAsBit( + "noNamedPositionallyEncodedOperands")) + // Collect the set of operand indices that might correspond to named + // operand, and skip these when assigning operands based on position. + for (unsigned I = 0, E = Vals.size(); I != E; ++I) { + unsigned OpIdx; + if (!CGI.Operands.hasOperandNamed(Vals[I].getName(), OpIdx)) + continue; + + NamedOpIndices.insert(OpIdx); + } + + for (unsigned I = 0, E = Vals.size(); I != E; ++I) { + // Ignore fixed fields in the record, we're looking for values like: + // bits<5> RST = { ?, ?, ?, ?, ? }; + if (Vals[I].isNonconcreteOK() || Vals[I].getValue()->isComplete()) + continue; + + // Determine if Vals[i] actually contributes to the Inst encoding. + unsigned Bi = 0; + for (; Bi < Bits.getNumBits(); ++Bi) { + VarInit *Var = nullptr; + VarBitInit *BI = dyn_cast(Bits.getBit(Bi)); + if (BI) + Var = dyn_cast(BI->getBitVar()); + else + Var = dyn_cast(Bits.getBit(Bi)); + + if (Var && Var->getName() == Vals[I].getName()) + break; + } + + if (Bi == Bits.getNumBits()) + continue; + + // Skip variables that correspond to explicitly-named operands. + unsigned OpIdx; + if (CGI.Operands.hasOperandNamed(Vals[I].getName(), OpIdx)) + continue; + + // Get the bit range for this operand: + unsigned const BitStart = Bi++; + unsigned BitWidth = 1; + for (; Bi < Bits.getNumBits(); ++Bi) { + VarInit *Var = nullptr; + VarBitInit *BI = dyn_cast(Bits.getBit(Bi)); + if (BI) + Var = dyn_cast(BI->getBitVar()); + else + Var = dyn_cast(Bits.getBit(Bi)); + + if (!Var) + break; + + if (Var->getName() != Vals[I].getName()) + break; + + ++BitWidth; + } + + unsigned const NumberOps = CGI.Operands.size(); + while (NumberedOp < NumberOps && + (CGI.Operands.isFlatOperandNotEmitted(NumberedOp) || + (!NamedOpIndices.empty() && + NamedOpIndices.count( + CGI.Operands.getSubOperandNumber(NumberedOp).first)))) + ++NumberedOp; + + OpIdx = NumberedOp++; + + // OpIdx now holds the ordered operand number of Vals[i]. + std::pair const SO = + CGI.Operands.getSubOperandNumber(OpIdx); + const std::string &Name = CGI.Operands[SO.first].Name; + + LLVM_DEBUG(dbgs() << "Numbered operand mapping for " << Def.getName() + << ": " << Name << "(" << SO.first << ", " + << SO.second << ") => " << Vals[I].getName() << "\n"); + + std::string Decoder; + Record *TypeRecord = CGI.Operands[SO.first].Rec; + + RecordVal *DecoderString = TypeRecord->getValue("DecoderMethod"); + StringInit *String = + DecoderString ? dyn_cast(DecoderString->getValue()) + : nullptr; + if (String && String->getValue() != "") + Decoder = std::string(String->getValue()); + + if (Decoder == "" && CGI.Operands[SO.first].MIOperandInfo && + CGI.Operands[SO.first].MIOperandInfo->getNumArgs()) { + Init *Arg = CGI.Operands[SO.first].MIOperandInfo->getArg(SO.second); + if (DefInit *DI = dyn_cast(Arg)) + TypeRecord = DI->getDef(); + } + + bool IsReg = false; + if (TypeRecord->isSubClassOf("RegisterOperand")) + TypeRecord = TypeRecord->getValueAsDef("RegClass"); + if (TypeRecord->isSubClassOf("RegisterClass")) { + Decoder = "Decode" + TypeRecord->getName().str() + "RegisterClass"; + IsReg = true; + } else if (TypeRecord->isSubClassOf("PointerLikeRegClass")) { + Decoder = "DecodePointerLikeRegClass" + + utostr(TypeRecord->getValueAsInt("RegClassKind")); + IsReg = true; + } + + DecoderString = TypeRecord->getValue("DecoderMethod"); + String = DecoderString ? dyn_cast(DecoderString->getValue()) + : nullptr; + if (!IsReg && String && String->getValue() != "") + Decoder = std::string(String->getValue()); + + RecordVal *HasCompleteDecoderVal = + TypeRecord->getValue("hasCompleteDecoder"); + BitInit *HasCompleteDecoderBit = + HasCompleteDecoderVal + ? dyn_cast(HasCompleteDecoderVal->getValue()) + : nullptr; + bool const HasCompleteDecoder = + HasCompleteDecoderBit ? HasCompleteDecoderBit->getValue() : true; + + OperandInfo OpInfo(Decoder, HasCompleteDecoder); + OpInfo.addField(BitStart, BitWidth, 0); + + NumberedInsnOperands[Name].push_back(OpInfo); + + // FIXME: For complex operands with custom decoders we can't handle tied + // sub-operands automatically. Skip those here and assume that this is + // fixed up elsewhere. + if (CGI.Operands[SO.first].MIOperandInfo && + CGI.Operands[SO.first].MIOperandInfo->getNumArgs() > 1 && String && + String->getValue() != "") + NumberedInsnOperandsNoTie.insert(Name); + } + } + + // For each operand, see if we can figure out where it is encoded. + for (const auto &Op : InOutOperands) { + if (!NumberedInsnOperands[std::string(Op.second)].empty()) { + llvm::append_range(InsnOperands, + NumberedInsnOperands[std::string(Op.second)]); + continue; + } + if (!NumberedInsnOperands[TiedNames[std::string(Op.second)]].empty()) { + if (!NumberedInsnOperandsNoTie.count( + TiedNames[std::string(Op.second)])) { + // Figure out to which (sub)operand we're tied. + unsigned I = + CGI.Operands.getOperandNamed(TiedNames[std::string(Op.second)]); + int TiedTo = CGI.Operands[I].getTiedRegister(); + if (TiedTo == -1) { + I = CGI.Operands.getOperandNamed(Op.second); + TiedTo = CGI.Operands[I].getTiedRegister(); + } + + if (TiedTo != -1) { + std::pair const SO = + CGI.Operands.getSubOperandNumber(TiedTo); + + InsnOperands.push_back( + NumberedInsnOperands[TiedNames[std::string(Op.second)]] + [SO.second]); + } + } + continue; + } + + // At this point, we can locate the decoder field, but we need to know how + // to interpret it. As a first step, require the target to provide + // callbacks for decoding register classes. + + OperandInfo OpInfo = getOpInfo(cast(Op.first)->getDef()); + + // Some bits of the operand may be required to be 1 depending on the + // instruction's encoding. Collect those bits. + if (const RecordVal *EncodedValue = EncodingDef.getValue(Op.second)) + if (const BitsInit *OpBits = + dyn_cast(EncodedValue->getValue())) + for (unsigned I = 0; I < OpBits->getNumBits(); ++I) + if (const BitInit *OpBit = dyn_cast(OpBits->getBit(I))) + if (OpBit->getValue()) + OpInfo.InitValue |= 1ULL << I; + + unsigned Base = ~0U; + unsigned Width = 0; + unsigned Offset = 0; + + for (unsigned Bi = 0; Bi < Bits.getNumBits(); ++Bi) { + VarInit *Var = nullptr; + VarBitInit *BI = dyn_cast(Bits.getBit(Bi)); + if (BI) + Var = dyn_cast(BI->getBitVar()); + else + Var = dyn_cast(Bits.getBit(Bi)); + + if (!Var) { + if (Base != ~0U) { + OpInfo.addField(Base, Width, Offset); + Base = ~0U; + Width = 0; + Offset = 0; + } + continue; + } + + if ((Var->getName() != Op.second && + Var->getName() != TiedNames[std::string(Op.second)])) { + if (Base != ~0U) { + OpInfo.addField(Base, Width, Offset); + Base = ~0U; + Width = 0; + Offset = 0; + } + continue; + } + + if (Base == ~0U) { + Base = Bi; + Width = 1; + Offset = BI ? BI->getBitNum() : 0; + } else if (BI && BI->getBitNum() != Offset + Width) { + OpInfo.addField(Base, Width, Offset); + Base = Bi; + Width = 1; + Offset = BI->getBitNum(); + } else { + ++Width; + } + } + + if (Base != ~0U) + OpInfo.addField(Base, Width, Offset); + + if (OpInfo.numFields() > 0) + InsnOperands.push_back(OpInfo); + } + } + + Operands[Opc] = InsnOperands; + +#if 0 + LLVM_DEBUG({ + // Dumps the instruction encoding bits. + dumpBits(errs(), Bits); + + errs() << '\n'; + + // Dumps the list of operand info. + for (unsigned i = 0, e = CGI.Operands.size(); i != e; ++i) { + const CGIOperandList::OperandInfo &Info = CGI.Operands[i]; + const std::string &OperandName = Info.Name; + const Record &OperandDef = *Info.Rec; + + errs() << "\t" << OperandName << " (" << OperandDef.getName() << ")\n"; + } + }); +#endif + + return Bits.getNumBits(); +} + +// emitFieldFromInstruction - Emit the templated helper function +// fieldFromInstruction(). +// On Windows we make sure that this function is not inlined when +// using the VS compiler. It has a bug which causes the function +// to be optimized out in some circustances. See llvm.org/pr38292 +void emitFieldFromInstruction(formatted_raw_ostream &OS) { + OS << "// Helper functions for extracting fields from encoded instructions.\n" + << "// InsnType must either be integral or an APInt-like object that " + "must:\n" + << "// * be default-constructible and copy-constructible\n" + << "// * be constructible from an APInt (this can be private)\n" + << "// * Support insertBits(bits, startBit, numBits)\n" + << "// * Support extractBitsAsZExtValue(numBits, startBit)\n" + << "// * Support the ~, &, ==, and != operators with other objects of " + "the same type\n" + << "// * Support the != and bitwise & with uint64_t\n" + << "// * Support put (<<) to raw_ostream&\n" + << "template \n" + << "#if defined(_MSC_VER) && !defined(__clang__)\n" + << "__declspec(noinline)\n" + << "#endif\n" + << "static std::enable_if_t::value, InsnType>\n" + << "fieldFromInstruction(const InsnType &insn, unsigned startBit,\n" + << " unsigned numBits) {\n" + << " assert(startBit + numBits <= 64 && \"Cannot support >64-bit " + "extractions!\");\n" + << " assert(startBit + numBits <= (sizeof(InsnType) * 8) &&\n" + << " \"Instruction field out of bounds!\");\n" + << " InsnType fieldMask;\n" + << " if (numBits == sizeof(InsnType) * 8)\n" + << " fieldMask = (InsnType)(-1LL);\n" + << " else\n" + << " fieldMask = (((InsnType)1 << numBits) - 1) << startBit;\n" + << " return (insn & fieldMask) >> startBit;\n" + << "}\n" + << "\n" + << "template \n" + << "static std::enable_if_t::value, " + "uint64_t>\n" + << "fieldFromInstruction(const InsnType &insn, unsigned startBit,\n" + << " unsigned numBits) {\n" + << " return insn.extractBitsAsZExtValue(numBits, startBit);\n" + << "}\n\n"; +} + +// emitInsertBits - Emit the templated helper function insertBits(). +void emitInsertBits(formatted_raw_ostream &OS) { + OS << "// Helper function for inserting bits extracted from an encoded " + "instruction into\n" + << "// a field.\n" + << "template \n" + << "static std::enable_if_t::value>\n" + << "insertBits(InsnType &field, InsnType bits, unsigned startBit, " + "unsigned numBits) {\n" + << " assert(startBit + numBits <= sizeof field * 8);\n" + << " field |= (InsnType)bits << startBit;\n" + << "}\n" + << "\n" + << "template \n" + << "static std::enable_if_t::value>\n" + << "insertBits(InsnType &field, uint64_t bits, unsigned startBit, " + "unsigned numBits) {\n" + << " field.insertBits(bits, startBit, numBits);\n" + << "}\n\n"; +} + +// emitDecodeInstruction - Emit the templated helper function +// decodeInstruction(). +void emitDecodeInstruction(formatted_raw_ostream &OS, bool IsVarLenInst) { + OS << "template \n" + << "static DecodeStatus decodeInstruction(const uint8_t DecodeTable[], " + "MCInst &MI,\n" + << " InsnType insn, uint64_t " + "Address,\n" + << " const MCDisassembler *DisAsm,\n" + << " const MCSubtargetInfo &STI"; + if (IsVarLenInst) { + OS << ",\n" + << " llvm::function_ref makeUp"; + } + OS << ") {\n" + << " const FeatureBitset &Bits = STI.getFeatureBits();\n" + << "\n" + << " const uint8_t *Ptr = DecodeTable;\n" + << " uint64_t CurFieldValue = 0;\n" + << " DecodeStatus S = MCDisassembler::Success;\n" + << " while (true) {\n" + << " ptrdiff_t Loc = Ptr - DecodeTable;\n" + << " switch (*Ptr) {\n" + << " default:\n" + << " errs() << Loc << \": Unexpected decode table opcode!\\n\";\n" + << " return MCDisassembler::Fail;\n" + << " case MCD::OPC_ExtractField: {\n" + << " unsigned Start = *++Ptr;\n" + << " unsigned Len = *++Ptr;\n" + << " ++Ptr;\n"; + if (IsVarLenInst) + OS << " makeUp(insn, Start + Len);\n"; + OS << " CurFieldValue = fieldFromInstruction(insn, Start, Len);\n" + << " LLVM_DEBUG(dbgs() << Loc << \": OPC_ExtractField(\" << Start << " + "\", \"\n" + << " << Len << \"): \" << CurFieldValue << \"\\n\");\n" + << " break;\n" + << " }\n" + << " case MCD::OPC_FilterValue: {\n" + << " // Decode the field value.\n" + << " unsigned Len;\n" + << " uint64_t Val = decodeULEB128(++Ptr, &Len);\n" + << " Ptr += Len;\n" + << " // NumToSkip is a plain 24-bit integer.\n" + << " unsigned NumToSkip = *Ptr++;\n" + << " NumToSkip |= (*Ptr++) << 8;\n" + << " NumToSkip |= (*Ptr++) << 16;\n" + << "\n" + << " // Perform the filter operation.\n" + << " if (Val != CurFieldValue)\n" + << " Ptr += NumToSkip;\n" + << " LLVM_DEBUG(dbgs() << Loc << \": OPC_FilterValue(\" << Val << " + "\", \" << NumToSkip\n" + << " << \"): \" << ((Val != CurFieldValue) ? \"FAIL:\" " + ": \"PASS:\")\n" + << " << \" continuing at \" << (Ptr - DecodeTable) << " + "\"\\n\");\n" + << "\n" + << " break;\n" + << " }\n" + << " case MCD::OPC_CheckField: {\n" + << " unsigned Start = *++Ptr;\n" + << " unsigned Len = *++Ptr;\n"; + if (IsVarLenInst) + OS << " makeUp(insn, Start + Len);\n"; + OS << " uint64_t FieldValue = fieldFromInstruction(insn, Start, Len);\n" + << " // Decode the field value.\n" + << " unsigned PtrLen = 0;\n" + << " uint64_t ExpectedValue = decodeULEB128(++Ptr, &PtrLen);\n" + << " Ptr += PtrLen;\n" + << " // NumToSkip is a plain 24-bit integer.\n" + << " unsigned NumToSkip = *Ptr++;\n" + << " NumToSkip |= (*Ptr++) << 8;\n" + << " NumToSkip |= (*Ptr++) << 16;\n" + << "\n" + << " // If the actual and expected values don't match, skip.\n" + << " if (ExpectedValue != FieldValue)\n" + << " Ptr += NumToSkip;\n" + << " LLVM_DEBUG(dbgs() << Loc << \": OPC_CheckField(\" << Start << " + "\", \"\n" + << " << Len << \", \" << ExpectedValue << \", \" << " + "NumToSkip\n" + << " << \"): FieldValue = \" << FieldValue << \", " + "ExpectedValue = \"\n" + << " << ExpectedValue << \": \"\n" + << " << ((ExpectedValue == FieldValue) ? \"PASS\\n\" : " + "\"FAIL\\n\"));\n" + << " break;\n" + << " }\n" + << " case MCD::OPC_CheckPredicate: {\n" + << " unsigned Len;\n" + << " // Decode the Predicate Index value.\n" + << " unsigned PIdx = decodeULEB128(++Ptr, &Len);\n" + << " Ptr += Len;\n" + << " // NumToSkip is a plain 24-bit integer.\n" + << " unsigned NumToSkip = *Ptr++;\n" + << " NumToSkip |= (*Ptr++) << 8;\n" + << " NumToSkip |= (*Ptr++) << 16;\n" + << " // Check the predicate.\n" + << " bool Pred;\n" + << " if (!(Pred = checkDecoderPredicate(PIdx, Bits)))\n" + << " Ptr += NumToSkip;\n" + << " (void)Pred;\n" + << " LLVM_DEBUG(dbgs() << Loc << \": OPC_CheckPredicate(\" << PIdx " + "<< \"): \"\n" + << " << (Pred ? \"PASS\\n\" : \"FAIL\\n\"));\n" + << "\n" + << " break;\n" + << " }\n" + << " case MCD::OPC_Decode: {\n" + << " unsigned Len;\n" + << " // Decode the Opcode value.\n" + << " unsigned Opc = decodeULEB128(++Ptr, &Len);\n" + << " Ptr += Len;\n" + << " unsigned DecodeIdx = decodeULEB128(Ptr, &Len);\n" + << " Ptr += Len;\n" + << "\n" + << " MI.clear();\n" + << " MI.setOpcode(Opc);\n" + << " bool DecodeComplete;\n"; + if (IsVarLenInst) { + OS << " Len = InstrLenTable[Opc];\n" + << " makeUp(insn, Len);\n"; + } + OS << " S = decodeToMCInst(S, DecodeIdx, insn, MI, Address, DisAsm, " + "DecodeComplete);\n" + << " assert(DecodeComplete);\n" + << "\n" + << " LLVM_DEBUG(dbgs() << Loc << \": OPC_Decode: opcode \" << Opc\n" + << " << \", using decoder \" << DecodeIdx << \": \"\n" + << " << (S != MCDisassembler::Fail ? \"PASS\" : " + "\"FAIL\") << \"\\n\");\n" + << " return S;\n" + << " }\n" + << " case MCD::OPC_TryDecode: {\n" + << " unsigned Len;\n" + << " // Decode the Opcode value.\n" + << " unsigned Opc = decodeULEB128(++Ptr, &Len);\n" + << " Ptr += Len;\n" + << " unsigned DecodeIdx = decodeULEB128(Ptr, &Len);\n" + << " Ptr += Len;\n" + << " // NumToSkip is a plain 24-bit integer.\n" + << " unsigned NumToSkip = *Ptr++;\n" + << " NumToSkip |= (*Ptr++) << 8;\n" + << " NumToSkip |= (*Ptr++) << 16;\n" + << "\n" + << " // Perform the decode operation.\n" + << " MCInst TmpMI;\n" + << " TmpMI.setOpcode(Opc);\n" + << " bool DecodeComplete;\n" + << " S = decodeToMCInst(S, DecodeIdx, insn, TmpMI, Address, DisAsm, " + "DecodeComplete);\n" + << " LLVM_DEBUG(dbgs() << Loc << \": OPC_TryDecode: opcode \" << " + "Opc\n" + << " << \", using decoder \" << DecodeIdx << \": \");\n" + << "\n" + << " if (DecodeComplete) {\n" + << " // Decoding complete.\n" + << " LLVM_DEBUG(dbgs() << (S != MCDisassembler::Fail ? \"PASS\" : " + "\"FAIL\") << \"\\n\");\n" + << " MI = TmpMI;\n" + << " return S;\n" + << " } else {\n" + << " assert(S == MCDisassembler::Fail);\n" + << " // If the decoding was incomplete, skip.\n" + << " Ptr += NumToSkip;\n" + << " LLVM_DEBUG(dbgs() << \"FAIL: continuing at \" << (Ptr - " + "DecodeTable) << \"\\n\");\n" + << " // Reset decode status. This also drops a SoftFail status " + "that could be\n" + << " // set before the decode attempt.\n" + << " S = MCDisassembler::Success;\n" + << " }\n" + << " break;\n" + << " }\n" + << " case MCD::OPC_SoftFail: {\n" + << " // Decode the mask values.\n" + << " unsigned Len;\n" + << " uint64_t PositiveMask = decodeULEB128(++Ptr, &Len);\n" + << " Ptr += Len;\n" + << " uint64_t NegativeMask = decodeULEB128(Ptr, &Len);\n" + << " Ptr += Len;\n" + << " bool Fail = (insn & PositiveMask) != 0 || (~insn & " + "NegativeMask) != 0;\n" + << " if (Fail)\n" + << " S = MCDisassembler::SoftFail;\n" + << " LLVM_DEBUG(dbgs() << Loc << \": OPC_SoftFail: \" << (Fail ? " + "\"FAIL\\n\" : \"PASS\\n\"));\n" + << " break;\n" + << " }\n" + << " case MCD::OPC_Fail: {\n" + << " LLVM_DEBUG(dbgs() << Loc << \": OPC_Fail\\n\");\n" + << " return MCDisassembler::Fail;\n" + << " }\n" + << " }\n" + << " }\n" + << " llvm_unreachable(\"bogosity detected in disassembler state " + "machine!\");\n" + << "}\n\n"; +} + +} // end namespace tblgen_decoder_emitter Index: llvm/utils/TableGen/DecoderEmitter/InstructionDecoding.md =================================================================== --- /dev/null +++ llvm/utils/TableGen/DecoderEmitter/InstructionDecoding.md @@ -0,0 +1,171 @@ +# Instruction Decoding + +The disassembler of LLVM decodes instructions with the help of a non-cyclic [state machine](https://en.wikipedia.org/wiki/Finite-state_machine). + +Reading this will help you a lot to understand the code! +Because we describe here how this state machine is generated. + +## The general idea + +We start with a single set off all instructions of an architecture. +These instructions are put in groups. Each group holds the instructions of a specific CPU extension or mode +(think of `Thumb` mode in ARM, or vector extension of some processors). +For each group a state machine is generated. It decodes instructions of this group. + +To generate the state machine we first take all instructions of a group. +This set is split into subsets each of which can be distinguished to the other subsets by a certain bit field in its encoding. +This and other separation information is called `Filter`. + +The subsets are further split into smaller subsets until only single instructions are left. + +_Each subset represents a state in our decoding state machine._ + +
+ +This generator will build the states for several instruction groups (the `uint8_t decoder[]` tables) +and a decoder function which walks over those states until it fails or identifies an instruction. + +## Step 1 - Determine best bits for set separation + +In this step we determine which bits are most suited to separate the current set of instructions into subsets. + +Lets assume we have four instructions with a width of 8 bits (all instructions of a group have the same bit width). + +```text +Bit 0 1 2 3 4 5 6 7 + +IA: 0 1 0 ? ? 1 ? ? +IB: ? 1 0 0 0 ? ? ? +IC: 0 0 0 0 1 ? ? ? +ID: ? 0 1 ? ? ? ? ? + +`?` = unset bit position (holds variable bits) +``` + +Now we have a `BitAttr` mask which saves which bits are suitable for filtering the set into subsets. + +``` +BitAttr: . . _ _ _ _ _ _ + +"." = Bit already used by previous Filter. +"_" = Bit unset/None (not used by previous Filter) +``` + +In the beginning all bits are unset (`_`) but the more instructions become filtered the more bits are set to `.`. + +To determine which bits in instruction `IA` to `ID` can be used to distinguish them, we define a automaton (see below). +The automaton gets the value at `BitAttr[i]` (`Filtered` or `Unset`/`None`) as start state and as input the bits at `IA[i]`, `IB[i]`, `IC[i]`, `ID[i]`. + +The result can be: `AllSet` (`S`), `All_unset` (`U`), `Mixed` (`M`) or `Filtered` (`F`) +The result is written to `BitAttr[i]`. + +``` + 0,1 + ┌─────┐ + │ │ + │ │ + │ │ + │ ▼ + ┌─┴───────┐ + 0,1 │ │ 0,1,? + ┌─────────────────►│All_Set │ ┌────┐ + │ │ │ │ │ + │ └────┬────┘ │ │ + │ │ │ │ + │ │? │ ▼ + │ │ ┌───┴──────┐ + │ ▼ │ │ +┌────┴───┐ ┌───────────┐ │ Filtered │ +│ │ │ ├─────┐ │ │ +│ None │ │ Mixed │ │0,1,? └──────────┘ +│ │ │ │◄────┘ +└───┬────┘ └───────────┘ + │ ▲ + │ │0,1 + │ │ + │ ┌────┴─────┐ + │ ? │ │ + └──────────────────►│ All_unset│ + │ │ + └─┬────────┘ + │ ▲ + │ │ + │ │ + │ │ + └─────┘ + ? +``` + +Here is how our little example would play out. + +``` +IA: 0 1 0 ? ? 1 ? ? +IB: ? 1 0 0 0 ? ? ? +IC: 0 0 0 0 1 ? ? ? +ID: ? 0 1 ? ? ? ? ? + +BitAttr: . . _ _ _ _ _ _ + +becomes + +BitAttr: . . S M M M U U +``` + +## Step 2 - Determine potential Filters + +Now we report regions in the `BitAttr` which might be suitable as a `Filter`. +A `region` is the index of the start bit and the length. + +There are three region reporting strategies: + +1. Report only successive `S` bits. +2. Report only successive `S` or successive `M` bits. +3. A special and rare case (explained in code). + +The strategies are tried from 1 to 3. +If non of them works we get a conflict (the set of instructions are indistinguishable). This case is explained in the code. + +If we continue with our example we get the following regions: + +``` +region = (startIndex, length) + +Bit 0 1 2 3 4 5 6 7 +BitAttr: . . S M M M U U + +strategy 1 = R1 = (2, 1) +strategy 2 = R1 = (2, 1), R2 = (3, 3) +``` + +## Step 3 - Select the best region as Filter + +We determine the best `Filter` by checking which region distinguishes the most instructions. +Lets assume we used strategy 2 here, so we have: + +``` +Bit 0 1 2 3 4 5 6 7 + +IA: 0 1 0 ? ? 1 ? ? +IB: ? 1 0 0 0 ? ? ? +IC: 0 0 0 0 1 ? ? ? +ID: ? 0 1 ? ? ? ? ? + +R1 = (2, 1) +R2 = (3, 3) +``` + +`R1` can create two subsets: `(IA, IB, IC)` and `(ID)`. +`R2` can create only one subset `(IA, IB, IC, ID)`. + +`R1` can separate instructions by bit 2 (which is either `0` or `1` in all instructions). + +`R2` has not a single bit position where all instruction bits are known (remember: `?` are variable bits, we can't distinguish them). +Therefore it can not separate instructions. + +Because `R1` creates the most subsets it is chosen as the Filter. + +## Recurse + +The `BitAttr` bits are reset to either `Filtered` (if used) or `Unset` and passed on to the inferior `FilterChooser` of each subset. +For each subset we start the process again from `Step 1` (not for subsets of size 1 obviously). +