X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=utils%2FTableGen%2FFixedLenDecoderEmitter.cpp;h=cbf40a90b4d89e9b6850d68e6841ec593e208a12;hp=af73bcfa67f582bfebe7b877baf84cf29b9ed2c6;hb=01d5be6990d0233151f6e5ab7ede6077ceb801f0;hpb=7a2bdde0a0eebcd2125055e0eacaca040f0b766c diff --git a/utils/TableGen/FixedLenDecoderEmitter.cpp b/utils/TableGen/FixedLenDecoderEmitter.cpp index af73bcfa67f..cbf40a90b4d 100644 --- a/utils/TableGen/FixedLenDecoderEmitter.cpp +++ b/utils/TableGen/FixedLenDecoderEmitter.cpp @@ -12,21 +12,113 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "decoder-emitter" - -#include "FixedLenDecoderEmitter.h" #include "CodeGenTarget.h" -#include "Record.h" +#include "llvm/ADT/APInt.h" +#include "llvm/ADT/SmallString.h" #include "llvm/ADT/StringExtras.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/ADT/Twine.h" +#include "llvm/MC/MCFixedLenDisassembler.h" +#include "llvm/Support/DataTypes.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/FormattedStream.h" +#include "llvm/Support/LEB128.h" #include "llvm/Support/raw_ostream.h" - -#include +#include "llvm/TableGen/Error.h" +#include "llvm/TableGen/Record.h" #include #include +#include using namespace llvm; +#define DEBUG_TYPE "decoder-emitter" + +namespace { +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; + + OperandInfo(std::string D, bool HCD) + : Decoder(D), HasCompleteDecoder(HCD) { } + + 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 SetVector PredicateSet; +typedef SetVector DecoderSet; +struct DecoderTableInfo { + DecoderTable Table; + FixupScopeList FixupStack; + PredicateSet Predicates; + DecoderSet Decoders; +}; + +} // End anonymous namespace + +namespace { +class FixedLenDecoderEmitter { + const std::vector *NumberedInstructions; +public: + + // Defaults preserved here for documentation, even though they aren't + // strictly necessary given the way that this is currently being called. + FixedLenDecoderEmitter(RecordKeeper &R, + std::string PredicateNamespace, + std::string GPrefix = "if (", + std::string GPostfix = " == MCDisassembler::Fail)", + std::string ROK = "MCDisassembler::Success", + std::string RFail = "MCDisassembler::Fail", + std::string L = "") : + Target(R), + PredicateNamespace(PredicateNamespace), + GuardPrefix(GPrefix), GuardPostfix(GPostfix), + ReturnOK(ROK), ReturnFail(RFail), Locals(L) {} + + // Emit the decoder state machine table. + void emitTable(formatted_raw_ostream &o, DecoderTable &Table, + unsigned Indentation, unsigned BitWidth, + StringRef Namespace) 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. // @@ -48,18 +140,16 @@ static bool ValueNotSet(bit_value_t V) { static int Value(bit_value_t V) { return ValueNotSet(V) ? -1 : (V == BIT_FALSE ? 0 : 1); } -static bit_value_t bitFromBits(BitsInit &bits, unsigned index) { - if (BitInit *bit = dynamic_cast(bits.getBit(index))) +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, BitsInit &bits) { - unsigned index; - - for (index = bits.getNumBits(); index > 0; index--) { +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"; @@ -71,7 +161,7 @@ static void dumpBits(raw_ostream &o, BitsInit &bits) { o << "_"; break; default: - assert(0 && "unexpected return value from bitFromBits"); + llvm_unreachable("unexpected return value from bitFromBits"); } } } @@ -82,13 +172,12 @@ static BitsInit &getBitsField(const Record &def, const char *str) { } // Forward declaration. +namespace { class FilterChooser; - -// FIXME: Possibly auto-detected? -#define BIT_WIDTH 32 +} // End anonymous namespace // Representation of the instruction to work on. -typedef bit_value_t insn_t[BIT_WIDTH]; +typedef std::vector insn_t; /// Filter - Filter works with FilterChooser to produce the decoding tree for /// the ISA. @@ -119,16 +208,17 @@ typedef bit_value_t insn_t[BIT_WIDTH]; /// /// 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 regsisters. +/// 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. +namespace { class Filter { protected: - FilterChooser *Owner; // points to the FilterChooser who owns this filter + 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 @@ -140,7 +230,7 @@ protected: std::vector VariableInstructions; // Map of well-known segment value to its delegate. - std::map FilterChooserMap; + std::map> FilterChooserMap; // Number of instructions which fall under FilteredInstructions category. unsigned NumFiltered; @@ -148,25 +238,21 @@ protected: // Keeps track of the last opcode in the filtered bucket. unsigned LastOpcFiltered; - // Number of instructions which fall under VariableInstructions category. - unsigned NumVariable; - public: - unsigned getNumFiltered() { return NumFiltered; } - unsigned getNumVariable() { return NumVariable; } - unsigned getSingletonOpc() { + unsigned getNumFiltered() const { return NumFiltered; } + unsigned getSingletonOpc() const { assert(NumFiltered == 1); return LastOpcFiltered; } // Return the filter chooser for the group of instructions without constant // segment values. - FilterChooser &getVariableFC() { + const FilterChooser &getVariableFC() const { assert(NumFiltered == 1); assert(FilterChooserMap.size() == 1); return *(FilterChooserMap.find((unsigned)-1)->second); } - Filter(const Filter &f); + Filter(Filter &&f); Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, bool mixed); ~Filter(); @@ -179,13 +265,15 @@ public: // match the remaining undecoded encoding bits against the singleton. void recurse(); - // Emit code to decode instructions given a segment or segments of bits. - void emit(raw_ostream &o, unsigned &Indentation); + // 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 of 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. @@ -212,6 +300,7 @@ typedef enum { /// 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; @@ -220,69 +309,78 @@ protected: const std::vector &AllInstructions; // Vector of uid's for this filter chooser to work on. - const std::vector Opcodes; + const std::vector &Opcodes; // Lookup table for the operand decoding of instructions. - std::map > &Operands; + 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. - bit_value_t FilterBitValues[BIT_WIDTH]; + std::vector FilterBitValues; // Links to the FilterChooser above us in the decoding tree. - FilterChooser *Parent; + const FilterChooser *Parent; // Index of the best filter from Filters. int BestIndex; + // Width of instructions + unsigned BitWidth; + + // Parent emitter + const FixedLenDecoderEmitter *Emitter; + + FilterChooser(const FilterChooser &) = delete; + void operator=(const FilterChooser &) = delete; public: - FilterChooser(const FilterChooser &FC) : - AllInstructions(FC.AllInstructions), Opcodes(FC.Opcodes), - Operands(FC.Operands), Filters(FC.Filters), Parent(FC.Parent), - BestIndex(FC.BestIndex) { - memcpy(FilterBitValues, FC.FilterBitValues, sizeof(FilterBitValues)); - } FilterChooser(const std::vector &Insts, const std::vector &IDs, - std::map > &Ops) : - AllInstructions(Insts), Opcodes(IDs), Operands(Ops), Filters(), - Parent(NULL), BestIndex(-1) { - for (unsigned i = 0; i < BIT_WIDTH; ++i) - FilterBitValues[i] = BIT_UNFILTERED; - + const std::map > &Ops, + unsigned BW, + const FixedLenDecoderEmitter *E) + : AllInstructions(Insts), Opcodes(IDs), Operands(Ops), Filters(), + FilterBitValues(BW, BIT_UNFILTERED), Parent(nullptr), BestIndex(-1), + BitWidth(BW), Emitter(E) { doFilter(); } FilterChooser(const std::vector &Insts, const std::vector &IDs, - std::map > &Ops, - bit_value_t (&ParentFilterBitValues)[BIT_WIDTH], - FilterChooser &parent) : - AllInstructions(Insts), Opcodes(IDs), Operands(Ops), - Filters(), Parent(&parent), BestIndex(-1) { - for (unsigned i = 0; i < BIT_WIDTH; ++i) - FilterBitValues[i] = ParentFilterBitValues[i]; - + const std::map > &Ops, + const std::vector &ParentFilterBitValues, + const FilterChooser &parent) + : AllInstructions(Insts), Opcodes(IDs), Operands(Ops), + Filters(), FilterBitValues(ParentFilterBitValues), + Parent(&parent), BestIndex(-1), BitWidth(parent.BitWidth), + Emitter(parent.Emitter) { doFilter(); } - // The top level filter chooser has NULL as its parent. - bool isTopLevel() { return Parent == NULL; } - - // Emit the top level typedef and decodeInstruction() function. - void emitTop(raw_ostream &o, unsigned Indentation); + unsigned getBitWidth() const { return BitWidth; } protected: // Populates the insn given the uid. void insnWithID(insn_t &Insn, unsigned Opcode) const { BitsInit &Bits = getBitsField(*AllInstructions[Opcode]->TheDef, "Inst"); - for (unsigned i = 0; i < BIT_WIDTH; ++i) - Insn[i] = bitFromBits(Bits, i); + // We may have a SoftFail bitmask, which specifies a mask where an encoding + // may differ from the value in "Inst" and yet still be valid, but the + // disassembler should return SoftFail instead of Success. + // + // This is used for marking UNPREDICTABLE instructions in the ARM world. + BitsInit *SFBits = + AllInstructions[Opcode]->TheDef->getValueAsBitsInit("SoftFail"); + + for (unsigned i = 0; i < BitWidth; ++i) { + if (SFBits && bitFromBits(*SFBits, i) == BIT_TRUE) + Insn.push_back(BIT_UNSET); + else + Insn.push_back(bitFromBits(Bits, i)); + } } // Returns the record name. @@ -296,15 +394,16 @@ protected: // 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; + unsigned NumBits) const; /// dumpFilterArray - dumpFilterArray prints out debugging info for the given /// filter array as a series of chars. - void dumpFilterArray(raw_ostream &o, bit_value_t (&filter)[BIT_WIDTH]); + 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); + void dumpStack(raw_ostream &o, const char *prefix) const; Filter &bestFilter() { assert(BestIndex != -1 && "BestIndex not set"); @@ -312,9 +411,9 @@ protected: } // Called from Filter::recurse() when singleton exists. For debug purpose. - void SingletonExists(unsigned Opc); + void SingletonExists(unsigned Opc) const; - bool PositionFiltered(unsigned i) { + bool PositionFiltered(unsigned i) const { return ValueSet(FilterBitValues[i]); } @@ -323,24 +422,47 @@ protected: // 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, - insn_t &Insn); + 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 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 code to decode the singleton. Return true if we have matched all the - // well-known bits. - bool emitSingletonDecoder(raw_ostream &o, unsigned &Indentation,unsigned Opc); + // Emits table entries to decode the singleton. + void emitSingletonTableEntry(DecoderTableInfo &TableInfo, + unsigned Opc) const; // Emits code to decode the singleton, and then to decode the rest. - void emitSingletonDecoder(raw_ostream &o, unsigned &Indentation,Filter &Best); + 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(FilterChooser &owner, unsigned startBit, unsigned numBit, - bool mixed); + 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); + 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 @@ -352,34 +474,34 @@ protected: // dump the conflict set to the standard error. void doFilter(); - // Emits code to decode our share of instructions. Returns true if the - // emitted code causes a return, which occurs if we know how to decode - // the instruction at this level or the instruction is not decodeable. - bool emit(raw_ostream &o, unsigned &Indentation); +public: + // emitTableEntries - Emit state machine entries to decode our share of + // instructions. + void emitTableEntries(DecoderTableInfo &TableInfo) const; }; +} // End anonymous namespace /////////////////////////// // // -// Filter Implmenetation // +// Filter Implementation // // // /////////////////////////// -Filter::Filter(const Filter &f) : - Owner(f.Owner), StartBit(f.StartBit), NumBits(f.NumBits), Mixed(f.Mixed), - FilteredInstructions(f.FilteredInstructions), - VariableInstructions(f.VariableInstructions), - FilterChooserMap(f.FilterChooserMap), NumFiltered(f.NumFiltered), - LastOpcFiltered(f.LastOpcFiltered), NumVariable(f.NumVariable) { +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 < BIT_WIDTH); + bool mixed) + : Owner(&owner), StartBit(startBit), NumBits(numBits), Mixed(mixed) { + assert(StartBit + NumBits - 1 < Owner->BitWidth); NumFiltered = 0; LastOpcFiltered = 0; - NumVariable = 0; for (unsigned i = 0, e = Owner->Opcodes.size(); i != e; ++i) { insn_t Insn; @@ -398,10 +520,9 @@ Filter::Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, FilteredInstructions[Field].push_back(LastOpcFiltered); ++NumFiltered; } else { - // Some of the encoding bit(s) are unspecfied. This contributes to + // Some of the encoding bit(s) are unspecified. This contributes to // one additional member of "Variable" instructions. VariableInstructions.push_back(Owner->Opcodes[i]); - ++NumVariable; } } @@ -410,12 +531,6 @@ Filter::Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, } Filter::~Filter() { - std::map::iterator filterIterator; - for (filterIterator = FilterChooserMap.begin(); - filterIterator != FilterChooserMap.end(); - filterIterator++) { - delete filterIterator->second; - } } // Divides the decoding task into sub tasks and delegates them to the @@ -425,33 +540,24 @@ Filter::~Filter() { // instructions. In order to unambiguously decode the singleton, we need to // match the remaining undecoded encoding bits against the singleton. void Filter::recurse() { - std::map >::const_iterator mapIterator; - - bit_value_t BitValueArray[BIT_WIDTH]; // Starts by inheriting our parent filter chooser's filter bit values. - memcpy(BitValueArray, Owner->FilterBitValues, sizeof(BitValueArray)); - - unsigned bitIndex; + std::vector BitValueArray(Owner->FilterBitValues); - if (VariableInstructions.size()) { + if (!VariableInstructions.empty()) { // Conservatively marks each segment position as BIT_UNSET. - for (bitIndex = 0; bitIndex < NumBits; bitIndex++) + 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::pair( - (unsigned)-1, - new FilterChooser(Owner->AllInstructions, - VariableInstructions, - Owner->Operands, - BitValueArray, - *Owner) - )); + FilterChooserMap.insert( + std::make_pair(-1U, llvm::make_unique( + Owner->AllInstructions, VariableInstructions, + Owner->Operands, BitValueArray, *Owner))); } // No need to recurse for a singleton filtered instruction. - // See also Filter::emit(). + // See also Filter::emit*(). if (getNumFiltered() == 1) { //Owner->SingletonExists(LastOpcFiltered); assert(FilterChooserMap.size() == 1); @@ -459,13 +565,11 @@ void Filter::recurse() { } // Otherwise, create sub choosers. - for (mapIterator = FilteredInstructions.begin(); - mapIterator != FilteredInstructions.end(); - mapIterator++) { + for (const auto &Inst : FilteredInstructions) { // Marks all the segment positions with either BIT_TRUE or BIT_FALSE. - for (bitIndex = 0; bitIndex < NumBits; bitIndex++) { - if (mapIterator->first & (1ULL << bitIndex)) + for (unsigned bitIndex = 0; bitIndex < NumBits; ++bitIndex) { + if (Inst.first & (1ULL << bitIndex)) BitValueArray[StartBit + bitIndex] = BIT_TRUE; else BitValueArray[StartBit + bitIndex] = BIT_FALSE; @@ -473,80 +577,109 @@ void Filter::recurse() { // Delegates to an inferior filter chooser for further processing on this // category of instructions. - FilterChooserMap.insert(std::pair( - mapIterator->first, - new FilterChooser(Owner->AllInstructions, - mapIterator->second, - Owner->Operands, - BitValueArray, - *Owner) - )); + FilterChooserMap.insert(std::make_pair( + Inst.first, llvm::make_unique( + Owner->AllInstructions, Inst.second, + Owner->Operands, BitValueArray, *Owner))); } } -// Emit code to decode instructions given a segment or segments of bits. -void Filter::emit(raw_ostream &o, unsigned &Indentation) { - o.indent(Indentation) << "// Check Inst{"; - - if (NumBits > 1) - o << (StartBit + NumBits - 1) << '-'; - - o << StartBit << "} ...\n"; +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 - 2; + // Our NumToSkip entries are 16-bits. Make sure our table isn't too + // big. + assert(Delta < 65536U && "disassembler decoding table too large!"); + Table[FixupIdx] = (uint8_t)Delta; + Table[FixupIdx + 1] = (uint8_t)(Delta >> 8); + } +} - o.indent(Indentation) << "switch (fieldFromInstruction(insn, " - << StartBit << ", " << NumBits << ")) {\n"; +// 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); - std::map::iterator filterIterator; + // A new filter entry begins a new scope for fixup resolution. + TableInfo.FixupStack.emplace_back(); - bool DefaultCase = false; - for (filterIterator = FilterChooserMap.begin(); - filterIterator != FilterChooserMap.end(); - filterIterator++) { + 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 (filterIterator->first == (unsigned)-1) { - DefaultCase = true; - - o.indent(Indentation) << "default:\n"; - o.indent(Indentation) << " break; // fallthrough\n"; - - // Closing curly brace for the switch statement. - // This is unconventional because we want the default processing to be - // performed for the fallthrough cases as well, i.e., when the "cases" - // did not prove a decoded instruction. - o.indent(Indentation) << "}\n"; - - } else - o.indent(Indentation) << "case " << filterIterator->first << ":\n"; + if (Filter.first == (unsigned)-1) { + 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[8]; + 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); + } // 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. - if (!DefaultCase) { ++Indentation; ++Indentation; } - - bool finished = filterIterator->second->emit(o, Indentation); - // For top level default case, there's no need for a break statement. - if (Owner->isTopLevel() && DefaultCase) - break; - if (!finished) - o.indent(Indentation) << "break;\n"; - - if (!DefaultCase) { --Indentation; --Indentation; } + 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 - 2; + assert(NumToSkip < 65536U && "disassembler decoding table too large!"); + Table[PrevFilter] = (uint8_t)NumToSkip; + Table[PrevFilter + 1] = (uint8_t)(NumToSkip >> 8); + } } - // If there is no default case, we still need to supply a closing brace. - if (!DefaultCase) { - // Closing curly brace for the switch statement. - o.indent(Indentation) << "}\n"; - } + // 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; + Dest->insert(Dest->end(), Source->begin(), Source->end()); + 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.size()) + if (!VariableInstructions.empty()) return FilteredInstructions.size(); else return FilteredInstructions.size() + 1; @@ -558,73 +691,229 @@ unsigned Filter::usefulness() const { // // ////////////////////////////////// -// Emit the top level typedef and decodeInstruction() function. -void FilterChooser::emitTop(raw_ostream &o, unsigned Indentation) { - switch (BIT_WIDTH) { - case 8: - o.indent(Indentation) << "typedef uint8_t field_t;\n"; - break; - case 16: - o.indent(Indentation) << "typedef uint16_t field_t;\n"; - break; - case 32: - o.indent(Indentation) << "typedef uint32_t field_t;\n"; - break; - case 64: - o.indent(Indentation) << "typedef uint64_t field_t;\n"; - break; - default: - assert(0 && "Unexpected instruction size!"); - } - - o << '\n'; - - o.indent(Indentation) << "static field_t " << - "fieldFromInstruction(field_t insn, unsigned startBit, unsigned numBits)\n"; - - o.indent(Indentation) << "{\n"; +// Emit the decoder state machine table. +void FixedLenDecoderEmitter::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; ++Indentation; - o.indent(Indentation) << "assert(startBit + numBits <= " << BIT_WIDTH - << " && \"Instruction field out of bounds!\");\n"; - o << '\n'; - o.indent(Indentation) << "field_t fieldMask;\n"; - o << '\n'; - o.indent(Indentation) << "if (numBits == " << BIT_WIDTH << ")\n"; - - ++Indentation; ++Indentation; - o.indent(Indentation) << "fieldMask = (field_t)-1;\n"; - --Indentation; --Indentation; + Indentation += 2; - o.indent(Indentation) << "else\n"; + // 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!"); - ++Indentation; ++Indentation; - o.indent(Indentation) << "fieldMask = ((1 << numBits) - 1) << startBit;\n"; - --Indentation; --Indentation; + uint64_t Pos = I - Table.begin(); + OS << "/* " << Pos << " */"; + OS.PadToColumn(12); - o << '\n'; - o.indent(Indentation) << "return (insn & fieldMask) >> startBit;\n"; - --Indentation; --Indentation; + 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 << utostr(*I++) << ", "; + OS << utostr(*I++) << ", "; + + // 16-bit numtoskip value. + uint8_t Byte = *I++; + uint32_t NumToSkip = Byte; + OS << utostr(Byte) << ", "; + Byte = *I++; + OS << utostr(Byte) << ", "; + NumToSkip |= Byte << 8; + 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 << utostr(*I) << ", "; + OS << utostr(*I++) << ", "; + // 16-bit numtoskip value. + uint8_t Byte = *I++; + uint32_t NumToSkip = Byte; + OS << utostr(Byte) << ", "; + Byte = *I++; + OS << utostr(Byte) << ", "; + NumToSkip |= Byte << 8; + 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 << utostr(*I) << ", "; + OS << utostr(*I++) << ", "; + + // 16-bit numtoskip value. + uint8_t Byte = *I++; + uint32_t NumToSkip = Byte; + OS << utostr(Byte) << ", "; + Byte = *I++; + OS << utostr(Byte) << ", "; + NumToSkip |= Byte << 8; + 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[8], *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 << utostr(*p) << ", "; + OS << utostr(*p) << ", "; + + // Decoder index. + for (; *I >= 128; ++I) + OS << utostr(*I) << ", "; + OS << utostr(*I++) << ", "; + + if (!IsTry) { + OS << "// Opcode: " + << NumberedInstructions->at(Opc)->TheDef->getName() << "\n"; + break; + } - o.indent(Indentation) << "}\n"; + // Fallthrough for OPC_TryDecode. - o << '\n'; + // 16-bit numtoskip value. + uint8_t Byte = *I++; + uint32_t NumToSkip = Byte; + OS << utostr(Byte) << ", "; + Byte = *I++; + OS << utostr(Byte) << ", "; + NumToSkip |= Byte << 8; - o.indent(Indentation) << - "static bool decodeInstruction(MCInst &MI, field_t insn) {\n"; - o.indent(Indentation) << " unsigned tmp = 0;\n"; + OS << "// Opcode: " + << NumberedInstructions->at(Opc)->TheDef->getName() + << ", 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 << ", " << utostr(*I); + Value += (*I & 0x7f) << Shift; + Shift += 7; + } while (*I++ >= 128); + if (Value > 127) + OS << " /* 0x" << utohexstr(Value) << " */"; + // Negative mask + Value = 0; + Shift = 0; + do { + OS << ", " << utostr(*I); + Value += (*I & 0x7f) << Shift; + Shift += 7; + } while (*I++ >= 128); + if (Value > 127) + OS << " /* 0x" << utohexstr(Value) << " */"; + OS << ",\n"; + break; + } + case MCD::OPC_Fail: { + ++I; + OS.indent(Indentation) << "MCD::OPC_Fail,\n"; + break; + } + } + } + OS.indent(Indentation) << "0\n"; - ++Indentation; ++Indentation; - // Emits code to decode the instructions. - emit(o, Indentation); + Indentation -= 2; - o << '\n'; - o.indent(Indentation) << "return false;\n"; - --Indentation; --Indentation; + OS.indent(Indentation) << "};\n\n"; +} - o.indent(Indentation) << "}\n"; +void FixedLenDecoderEmitter:: +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"; +} - o << '\n'; +void FixedLenDecoderEmitter:: +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 void *Decoder, bool &DecodeComplete) {\n"; + Indentation += 2; + OS.indent(Indentation) << "DecodeComplete = true;\n"; + OS.indent(Indentation) << "InsnType 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 @@ -633,7 +922,7 @@ void FilterChooser::emitTop(raw_ostream &o, unsigned Indentation) { // 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 { + unsigned StartBit, unsigned NumBits) const { Field = 0; for (unsigned i = 0; i < NumBits; ++i) { @@ -650,10 +939,8 @@ bool FilterChooser::fieldFromInsn(uint64_t &Field, insn_t &Insn, /// dumpFilterArray - dumpFilterArray prints out debugging info for the given /// filter array as a series of chars. void FilterChooser::dumpFilterArray(raw_ostream &o, - bit_value_t (&filter)[BIT_WIDTH]) { - unsigned bitIndex; - - for (bitIndex = BIT_WIDTH; bitIndex > 0; bitIndex--) { + const std::vector &filter) const { + for (unsigned bitIndex = BitWidth; bitIndex > 0; bitIndex--) { switch (filter[bitIndex - 1]) { case BIT_UNFILTERED: o << "."; @@ -673,8 +960,8 @@ void FilterChooser::dumpFilterArray(raw_ostream &o, /// 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) { - FilterChooser *current = this; +void FilterChooser::dumpStack(raw_ostream &o, const char *prefix) const { + const FilterChooser *current = this; while (current) { o << prefix; @@ -685,7 +972,7 @@ void FilterChooser::dumpStack(raw_ostream &o, const char *prefix) { } // Called from Filter::recurse() when singleton exists. For debug purpose. -void FilterChooser::SingletonExists(unsigned Opc) { +void FilterChooser::SingletonExists(unsigned Opc) const { insn_t Insn0; insnWithID(Insn0, Opc); @@ -698,7 +985,7 @@ void FilterChooser::SingletonExists(unsigned Opc) { errs() << '\n'; dumpStack(errs(), "\t\t"); - for (unsigned i = 0; i < Opcodes.size(); i++) { + for (unsigned i = 0; i < Opcodes.size(); ++i) { const std::string &Name = nameWithID(Opcodes[i]); errs() << '\t' << Name << " "; @@ -713,8 +1000,9 @@ void FilterChooser::SingletonExists(unsigned Opc) { // 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, - insn_t &Insn) { + std::vector &EndBits, + std::vector &FieldVals, + const insn_t &Insn) const { unsigned Num, BitNo; Num = BitNo = 0; @@ -726,13 +1014,11 @@ unsigned FilterChooser::getIslands(std::vector &StartBits, int State = 0; int Val = -1; - for (unsigned i = 0; i < BIT_WIDTH; ++i) { + for (unsigned i = 0; i < BitWidth; ++i) { Val = Value(Insn[i]); bool Filtered = PositionFiltered(i); switch (State) { - default: - assert(0 && "Unreachable code!"); - break; + default: llvm_unreachable("Unreachable code!"); case 0: case 1: if (Filtered || Val == -1) @@ -760,7 +1046,7 @@ unsigned FilterChooser::getIslands(std::vector &StartBits, } // If we are still in Island after the loop, do some housekeeping. if (State == 2) { - EndBits.push_back(BIT_WIDTH - 1); + EndBits.push_back(BitWidth - 1); FieldVals.push_back(FieldVal); ++Num; } @@ -770,126 +1056,359 @@ unsigned FilterChooser::getIslands(std::vector &StartBits, return Num; } -// Emits code to decode the singleton. Return true if we have matched all the -// well-known bits. -bool FilterChooser::emitSingletonDecoder(raw_ostream &o, unsigned &Indentation, - unsigned Opc) { - std::vector StartBits; - std::vector EndBits; - std::vector FieldVals; - insn_t Insn; - insnWithID(Insn, Opc); +void FilterChooser::emitBinaryParser(raw_ostream &o, unsigned &Indentation, + const OperandInfo &OpInfo, + bool &OpHasCompleteDecoder) const { + const std::string &Decoder = OpInfo.Decoder; + + if (OpInfo.numFields() != 1) + o.indent(Indentation) << "tmp = 0;\n"; + + for (const EncodingField &EF : OpInfo) { + o.indent(Indentation) << "tmp "; + if (OpInfo.numFields() != 1) o << '|'; + o << "= fieldFromInstruction" + << "(insn, " << EF.Base << ", " << EF.Width << ')'; + if (OpInfo.numFields() != 1 || EF.Offset != 0) + o << " << " << EF.Offset; + o << ";\n"; + } - // Look for islands of undecoded bits of the singleton. - getIslands(StartBits, EndBits, FieldVals, Insn); + 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"; + } +} - unsigned Size = StartBits.size(); - unsigned I, NumBits; - - // If we have matched all the well-known bits, just issue a return. - if (Size == 0) { - o.indent(Indentation) << "{\n"; - o.indent(Indentation) << " MI.setOpcode(" << Opc << ");\n"; - std::vector& InsnOperands = Operands[Opc]; - for (std::vector::iterator - I = InsnOperands.begin(), E = InsnOperands.end(); I != E; ++I) { - // If a custom instruction decoder was specified, use that. - if (I->FieldBase == ~0U && I->FieldLength == ~0U) { - o.indent(Indentation) << " " << I->Decoder << "(MI, insn);\n"; - break; - } +void FilterChooser::emitDecoder(raw_ostream &OS, unsigned Indentation, + unsigned Opc, bool &HasCompleteDecoder) const { + HasCompleteDecoder = true; - o.indent(Indentation) - << " tmp = fieldFromInstruction(insn, " << I->FieldBase - << ", " << I->FieldLength << ");\n"; - if (I->Decoder != "") { - o.indent(Indentation) << " " << I->Decoder << "(MI, tmp);\n"; - } else { - o.indent(Indentation) - << " MI.addOperand(MCOperand::CreateImm(tmp));\n"; - } + for (const auto &Op : Operands.find(Opc)->second) { + // If a custom instruction decoder was specified, use that. + if (Op.numFields() == 0 && Op.Decoder.size()) { + HasCompleteDecoder = Op.HasCompleteDecoder; + OS.indent(Indentation) << Emitter->GuardPrefix << Op.Decoder + << "(MI, insn, Address, Decoder)" + << Emitter->GuardPostfix + << " { " << (HasCompleteDecoder ? "" : "DecodeComplete = false; ") + << "return MCDisassembler::Fail; }\n"; + break; } - o.indent(Indentation) << " return true; // " << nameWithID(Opc) - << '\n'; - o.indent(Indentation) << "}\n"; - return true; + bool OpHasCompleteDecoder; + emitBinaryParser(OS, Indentation, Op, OpHasCompleteDecoder); + if (!OpHasCompleteDecoder) + HasCompleteDecoder = false; } +} - // Otherwise, there are more decodings to be done! +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); + S.flush(); + + // 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 easilly 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(StringRef(Decoder)); + // Now figure out the index for when we write out the table. + DecoderSet::const_iterator P = std::find(Decoders.begin(), + Decoders.end(), + Decoder.str()); + return (unsigned)(P - Decoders.begin()); +} - // Emit code to match the island(s) for the singleton. - o.indent(Indentation) << "// Check "; +static void emitSinglePredicateMatch(raw_ostream &o, StringRef str, + const std::string &PredicateNamespace) { + if (str[0] == '!') + o << "!Bits[" << PredicateNamespace << "::" + << str.slice(1,str.size()) << "]"; + else + o << "Bits[" << PredicateNamespace << "::" << str << "]"; +} - for (I = Size; I != 0; --I) { - o << "Inst{" << EndBits[I-1] << '-' << StartBits[I-1] << "} "; - if (I > 1) - o << "&& "; - else - o << "for singleton decoding...\n"; - } +bool FilterChooser::emitPredicateMatch(raw_ostream &o, unsigned &Indentation, + unsigned Opc) const { + ListInit *Predicates = + AllInstructions[Opc]->TheDef->getValueAsListInit("Predicates"); + bool IsFirstEmission = true; + for (unsigned i = 0; i < Predicates->size(); ++i) { + Record *Pred = Predicates->getElementAsRecord(i); + if (!Pred->getValue("AssemblerMatcherPredicate")) + continue; + + std::string P = Pred->getValueAsString("AssemblerCondString"); - o.indent(Indentation) << "if ("; + if (!P.length()) + continue; - for (I = Size; I != 0; --I) { - NumBits = EndBits[I-1] - StartBits[I-1] + 1; - o << "fieldFromInstruction(insn, " << StartBits[I-1] << ", " << NumBits - << ") == " << FieldVals[I-1]; - if (I > 1) + if (!IsFirstEmission) o << " && "; - else - o << ") {\n"; - } - o.indent(Indentation) << " MI.setOpcode(" << Opc << ");\n"; - std::vector& InsnOperands = Operands[Opc]; - for (std::vector::iterator - I = InsnOperands.begin(), E = InsnOperands.end(); I != E; ++I) { - // If a custom instruction decoder was specified, use that. - if (I->FieldBase == ~0U && I->FieldLength == ~0U) { - o.indent(Indentation) << " " << I->Decoder << "(MI, insn);\n"; - break; - } - o.indent(Indentation) - << " tmp = fieldFromInstruction(insn, " << I->FieldBase - << ", " << I->FieldLength << ");\n"; - if (I->Decoder != "") { - o.indent(Indentation) << " " << I->Decoder << "(MI, tmp);\n"; - } else { - o.indent(Indentation) - << " MI.addOperand(MCOperand::CreateImm(tmp));\n"; + StringRef SR(P); + std::pair pairs = SR.split(','); + while (pairs.second.size()) { + emitSinglePredicateMatch(o, pairs.first, Emitter->PredicateNamespace); + o << " && "; + pairs = pairs.second.split(','); } + emitSinglePredicateMatch(o, pairs.first, Emitter->PredicateNamespace); + IsFirstEmission = false; } - o.indent(Indentation) << " return true; // " << nameWithID(Opc) - << '\n'; - o.indent(Indentation) << "}\n"; + return !Predicates->empty(); +} + +bool FilterChooser::doesOpcodeNeedPredicate(unsigned Opc) const { + ListInit *Predicates = + AllInstructions[Opc]->TheDef->getValueAsListInit("Predicates"); + for (unsigned i = 0; i < Predicates->size(); ++i) { + Record *Pred = Predicates->getElementAsRecord(i); + if (!Pred->getValue("AssemblerMatcherPredicate")) + continue; + std::string P = Pred->getValueAsString("AssemblerCondString"); + + if (!P.length()) + continue; + + return true; + } return false; } -// Emits code to decode the singleton, and then to decode the rest. -void FilterChooser::emitSingletonDecoder(raw_ostream &o, unsigned &Indentation, - Filter &Best) { +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 easilly 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(Predicate.str()); + // Now figure out the index for when we write out the table. + PredicateSet::const_iterator P = std::find(TableInfo.Predicates.begin(), + TableInfo.Predicates.end(), + Predicate.str()); + 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); + S.flush(); + + 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); +} + +void FilterChooser::emitSoftFailTableEntry(DecoderTableInfo &TableInfo, + unsigned Opc) const { + BitsInit *SFBits = + AllInstructions[Opc]->TheDef->getValueAsBitsInit("SoftFail"); + if (!SFBits) return; + BitsInit *InstBits = AllInstructions[Opc]->TheDef->getValueAsBitsInit("Inst"); + + APInt PositiveMask(BitWidth, 0ULL); + APInt NegativeMask(BitWidth, 0ULL); + for (unsigned i = 0; i < BitWidth; ++i) { + bit_value_t B = bitFromBits(*SFBits, i); + bit_value_t IB = bitFromBits(*InstBits, i); + if (B != BIT_TRUE) continue; + + switch (IB) { + case BIT_FALSE: + // The bit is meant to be false, so emit a check to see if it is true. + PositiveMask.setBit(i); + break; + case BIT_TRUE: + // The bit is meant to be true, so emit a check to see if it is false. + NegativeMask.setBit(i); + break; + default: + // The bit is not set; this must be an error! + StringRef Name = AllInstructions[Opc]->TheDef->getName(); + errs() << "SoftFail Conflict: bit SoftFail{" << i << "} in " << Name + << " is set but Inst{" << i << "} is unset!\n" + << " - 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); + S.flush(); + 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(); + S.resync(); + encodeULEB128(NegativeMask.getZExtValue(), S); + S.flush(); + 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, + unsigned Opc) const { + std::vector StartBits; + std::vector EndBits; + std::vector FieldVals; + insn_t Insn; + insnWithID(Insn, Opc); + + // 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); + + // 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[8], *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 16-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); + } + + // Check for soft failure of the match. + emitSoftFailTableEntry(TableInfo, Opc); + + bool HasCompleteDecoder; + unsigned DIdx = getDecoderIndex(TableInfo.Decoders, Opc, 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); + uint8_t Buffer[8], *p; + encodeULEB128(Opc, 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); + S.flush(); + + // 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); + } +} + +// Emits table entries to decode the singleton, and then to decode the rest. +void FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo, + const Filter &Best) const { unsigned Opc = Best.getSingletonOpc(); - emitSingletonDecoder(o, Indentation, Opc); + // complex singletons need predicate checks from the first singleton + // to refer forward to the variable filterchooser that follows. + TableInfo.FixupStack.emplace_back(); - // Emit code for the rest. - o.indent(Indentation) << "else\n"; + emitSingletonTableEntry(TableInfo, Opc); - Indentation += 2; - Best.getVariableFC().emit(o, Indentation); - Indentation -= 2; + 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(FilterChooser &owner, unsigned startBit, - unsigned numBit, bool mixed) { +void FilterChooser::runSingleFilter(unsigned startBit, unsigned numBit, + bool mixed) { Filters.clear(); - Filter F(*this, startBit, numBit, true); - Filters.push_back(F); + Filters.emplace_back(*this, startBit, numBit, true); BestIndex = 0; // Sole Filter instance to choose from. bestFilter().recurse(); } @@ -897,11 +1416,11 @@ void FilterChooser::runSingleFilter(FilterChooser &owner, unsigned startBit, // 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) { + unsigned BitIndex, bool AllowMixed) { if (RA == ATTR_MIXED && AllowMixed) - Filters.push_back(Filter(*this, StartBit, BitIndex - StartBit, true)); + Filters.emplace_back(*this, StartBit, BitIndex - StartBit, true); else if (RA == ATTR_ALL_SET && !AllowMixed) - Filters.push_back(Filter(*this, StartBit, BitIndex - StartBit, false)); + Filters.emplace_back(*this, StartBit, BitIndex - StartBit, false); } // FilterProcessor scans the well-known encoding bits of the instructions and @@ -934,14 +1453,13 @@ bool FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { // 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(*this, StartBits[0], EndBits[0] - StartBits[0] + 1, - true); + runSingleFilter(StartBits[0], EndBits[0] - StartBits[0] + 1, true); return true; } } } - unsigned BitIndex, InsnIndex; + unsigned BitIndex; // We maintain BIT_WIDTH copies of the bitAttrs automaton. // The automaton consumes the corresponding bit from each @@ -960,23 +1478,23 @@ bool FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { // (MIXED) ------ . ----> (MIXED) // (FILTERED)---- . ----> (FILTERED) - bitAttr_t bitAttrs[BIT_WIDTH]; + 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 < BIT_WIDTH; ++BitIndex) + for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) if (FilterBitValues[BitIndex] == BIT_TRUE || FilterBitValues[BitIndex] == BIT_FALSE) - bitAttrs[BitIndex] = ATTR_FILTERED; + bitAttrs.push_back(ATTR_FILTERED); else - bitAttrs[BitIndex] = ATTR_NONE; + bitAttrs.push_back(ATTR_NONE); - for (InsnIndex = 0; InsnIndex < numInstructions; ++InsnIndex) { + for (unsigned InsnIndex = 0; InsnIndex < numInstructions; ++InsnIndex) { insn_t insn; insnWithID(insn, Opcodes[InsnIndex]); - for (BitIndex = 0; BitIndex < BIT_WIDTH; ++BitIndex) { + for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { switch (bitAttrs[BitIndex]) { case ATTR_NONE: if (insn[BitIndex] == BIT_UNSET) @@ -1022,7 +1540,7 @@ bool FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { bitAttr_t RA = ATTR_NONE; unsigned StartBit = 0; - for (BitIndex = 0; BitIndex < BIT_WIDTH; BitIndex++) { + for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { bitAttr_t bitAttr = bitAttrs[BitIndex]; assert(bitAttr != ATTR_NONE && "Bit without attributes"); @@ -1043,7 +1561,7 @@ bool FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { RA = ATTR_MIXED; break; default: - assert(0 && "Unexpected bitAttr!"); + llvm_unreachable("Unexpected bitAttr!"); } break; case ATTR_ALL_SET: @@ -1064,7 +1582,7 @@ bool FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { RA = ATTR_MIXED; break; default: - assert(0 && "Unexpected bitAttr!"); + llvm_unreachable("Unexpected bitAttr!"); } break; case ATTR_MIXED: @@ -1086,13 +1604,13 @@ bool FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { case ATTR_MIXED: break; default: - assert(0 && "Unexpected bitAttr!"); + llvm_unreachable("Unexpected bitAttr!"); } break; case ATTR_ALL_UNSET: - assert(0 && "regionAttr state machine has no ATTR_UNSET state"); + llvm_unreachable("regionAttr state machine has no ATTR_UNSET state"); case ATTR_FILTERED: - assert(0 && "regionAttr state machine has no ATTR_FILTERED state"); + llvm_unreachable("regionAttr state machine has no ATTR_FILTERED state"); } } @@ -1163,43 +1681,36 @@ void FilterChooser::doFilter() { BestIndex = -1; } -// Emits code to decode our share of instructions. Returns true if the -// emitted code causes a return, which occurs if we know how to decode -// the instruction at this level or the instruction is not decodeable. -bool FilterChooser::emit(raw_ostream &o, unsigned &Indentation) { - if (Opcodes.size() == 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. - return emitSingletonDecoder(o, Indentation, Opcodes[0]); + emitSingletonTableEntry(TableInfo, Opcodes[0]); + return; + } // Choose the best filter to do the decodings! if (BestIndex != -1) { - Filter &Best = bestFilter(); + const Filter &Best = Filters[BestIndex]; if (Best.getNumFiltered() == 1) - emitSingletonDecoder(o, Indentation, Best); + emitSingletonTableEntry(TableInfo, Best); else - bestFilter().emit(o, Indentation); - return false; + Best.emitTableEntry(TableInfo); + return; } - // We don't know how to decode these instructions! Return 0 and dump the - // conflict set! - o.indent(Indentation) << "return 0;" << " // Conflict set: "; - for (int i = 0, N = Opcodes.size(); i < N; ++i) { - o << nameWithID(Opcodes[i]); - if (i < (N - 1)) - o << ", "; - else - o << '\n'; - } + // 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 (unsigned i = 0; i < Opcodes.size(); i++) { + for (unsigned i = 0; i < Opcodes.size(); ++i) { const std::string &Name = nameWithID(Opcodes[i]); errs() << '\t' << Name << " "; @@ -1207,34 +1718,27 @@ bool FilterChooser::emit(raw_ostream &o, unsigned &Indentation) { getBitsField(*AllInstructions[Opcodes[i]]->TheDef, "Inst")); errs() << '\n'; } - - return true; } -bool FixedLenDecoderEmitter::populateInstruction(const CodeGenInstruction &CGI, - unsigned Opc){ +static bool populateInstruction(CodeGenTarget &Target, + const CodeGenInstruction &CGI, unsigned Opc, + std::map > &Operands){ 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. - // - // This also removes pseudo instructions from considerations of disassembly, - // which is a better design and less fragile than the name matchings. + BitsInit &Bits = getBitsField(Def, "Inst"); if (Bits.allInComplete()) return false; - // Ignore "asm parser only" instructions. - if (Def.getValueAsBit("isAsmParserOnly") || - Def.getValueAsBit("isCodeGenOnly")) - return false; - std::vector InsnOperands; // If the instruction has specified a custom decoding hook, use that instead // of trying to auto-generate the decoder. std::string InstDecoder = Def.getValueAsString("DecoderMethod"); if (InstDecoder != "") { - InsnOperands.push_back(OperandInfo(~0U, ~0U, InstDecoder)); + bool HasCompleteInstDecoder = Def.getValueAsBit("hasCompleteDecoder"); + InsnOperands.push_back(OperandInfo(InstDecoder, HasCompleteInstDecoder)); Operands[Opc] = InsnOperands; return true; } @@ -1254,70 +1758,281 @@ bool FixedLenDecoderEmitter::populateInstruction(const CodeGenInstruction &CGI, for (unsigned i = 0; i < In->getNumArgs(); ++i) InOutOperands.push_back(std::make_pair(In->getArg(i), In->getArgName(i))); - // For each operand, see if we can figure out where it is encoded. - for (std::vector >::iterator - NI = InOutOperands.begin(), NE = InOutOperands.end(); NI != NE; ++NI) { - unsigned PrevBit = ~0; - unsigned Base = ~0; - unsigned PrevPos = ~0; - std::string Decoder = ""; + // 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[InOutOperands[i].second] = InOutOperands[SO.first].second; + TiedNames[InOutOperands[SO.first].second] = InOutOperands[i].second; + } + } - for (unsigned bi = 0; bi < Bits.getNumBits(); ++bi) { - VarBitInit *BI = dynamic_cast(Bits.getBit(bi)); - if (!BI) continue; - - VarInit *Var = dynamic_cast(BI->getVariable()); - assert(Var); - unsigned CurrBit = BI->getBitNum(); - if (Var->getName() != NI->second) continue; - - // Figure out the lowest bit of the value, and the width of the field. - // Deliberately don't try to handle cases where the field is scattered, - // or where not all bits of the the field are explicit. - if (Base == ~0U && PrevBit == ~0U && PrevPos == ~0U) { - if (CurrBit == 0) - Base = bi; - 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); } - if ((PrevPos != ~0U && bi-1 != PrevPos) || - (CurrBit != ~0U && CurrBit-1 != PrevBit)) { - PrevBit = ~0; - Base = ~0; - PrevPos = ~0; + 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].getPrefix() || 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; + + 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 = 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 (TypedInit *TI = cast(Arg)) { + RecordRecTy *Type = cast(TI->getType()); + TypeRecord = Type->getRecord(); + } } - PrevPos = bi; - PrevBit = CurrBit; - - // At this point, we can locate the field, but we need to know how to - // interpret it. As a first step, require the target to provide callbacks - // for decoding register classes. - // FIXME: This need to be extended to handle instructions with custom - // decoder methods, and operands with (simple) MIOperandInfo's. - TypedInit *TI = dynamic_cast(NI->first); - RecordRecTy *Type = dynamic_cast(TI->getType()); - Record *TypeRecord = Type->getRecord(); bool isReg = false; + if (TypeRecord->isSubClassOf("RegisterOperand")) + TypeRecord = TypeRecord->getValueAsDef("RegClass"); if (TypeRecord->isSubClassOf("RegisterClass")) { - Decoder = "Decode" + Type->getRecord()->getName() + "RegisterClass"; + Decoder = "Decode" + TypeRecord->getName() + "RegisterClass"; + isReg = true; + } else if (TypeRecord->isSubClassOf("PointerLikeRegClass")) { + Decoder = "DecodePointerLikeRegClass" + + utostr(TypeRecord->getValueAsInt("RegClassKind")); isReg = true; } - RecordVal *DecoderString = TypeRecord->getValue("DecoderMethod"); - StringInit *String = DecoderString ? - dynamic_cast(DecoderString->getValue()) : - 0; + DecoderString = TypeRecord->getValue("DecoderMethod"); + String = DecoderString ? + dyn_cast(DecoderString->getValue()) : nullptr; if (!isReg && String && String->getValue() != "") Decoder = 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[Op.second].empty()) { + InsnOperands.insert(InsnOperands.end(), + NumberedInsnOperands[Op.second].begin(), + NumberedInsnOperands[Op.second].end()); + continue; + } + if (!NumberedInsnOperands[TiedNames[Op.second]].empty()) { + if (!NumberedInsnOperandsNoTie.count(TiedNames[Op.second])) { + // Figure out to which (sub)operand we're tied. + unsigned i = CGI.Operands.getOperandNamed(TiedNames[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[Op.second]] + [SO.second]); + } + } + continue; } - if (Base != ~0U) { - InsnOperands.push_back(OperandInfo(Base, PrevBit+1, Decoder)); - DEBUG(errs() << "ENCODED OPERAND: $" << NI->second << " @ (" - << utostr(Base+PrevBit) << ", " << utostr(Base) << ")\n"); + std::string Decoder = ""; + + // At this point, we can locate the field, but we need to know how to + // interpret it. As a first step, require the target to provide callbacks + // for decoding register classes. + // FIXME: This need to be extended to handle instructions with custom + // decoder methods, and operands with (simple) MIOperandInfo's. + TypedInit *TI = cast(Op.first); + RecordRecTy *Type = cast(TI->getType()); + Record *TypeRecord = Type->getRecord(); + bool isReg = false; + if (TypeRecord->isSubClassOf("RegisterOperand")) + TypeRecord = TypeRecord->getValueAsDef("RegClass"); + if (TypeRecord->isSubClassOf("RegisterClass")) { + Decoder = "Decode" + TypeRecord->getName() + "RegisterClass"; + isReg = true; + } else if (TypeRecord->isSubClassOf("PointerLikeRegClass")) { + Decoder = "DecodePointerLikeRegClass" + + utostr(TypeRecord->getValueAsInt("RegClassKind")); + isReg = true; } + + RecordVal *DecoderString = TypeRecord->getValue("DecoderMethod"); + StringInit *String = DecoderString ? + dyn_cast(DecoderString->getValue()) : nullptr; + if (!isReg && String && String->getValue() != "") + Decoder = 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); + 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[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; @@ -1344,30 +2059,278 @@ bool FixedLenDecoderEmitter::populateInstruction(const CodeGenInstruction &CGI, return true; } -void FixedLenDecoderEmitter::populateInstructions() { - for (unsigned i = 0, e = NumberedInstructions.size(); i < e; ++i) { - Record *R = NumberedInstructions[i]->TheDef; - if (R->getValueAsString("Namespace") == "TargetOpcode") +// emitFieldFromInstruction - Emit the templated helper function +// fieldFromInstruction(). +static void emitFieldFromInstruction(formatted_raw_ostream &OS) { + OS << "// Helper function for extracting fields from encoded instructions.\n" + << "template\n" + << "static InsnType fieldFromInstruction(InsnType insn, unsigned startBit,\n" + << " unsigned numBits) {\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"; +} + +// emitDecodeInstruction - Emit the templated helper function +// decodeInstruction(). +static void emitDecodeInstruction(formatted_raw_ostream &OS) { + OS << "template\n" + << "static DecodeStatus decodeInstruction(const uint8_t DecodeTable[], MCInst &MI,\n" + << " InsnType insn, uint64_t Address,\n" + << " const void *DisAsm,\n" + << " const MCSubtargetInfo &STI) {\n" + << " const FeatureBitset& Bits = STI.getFeatureBits();\n" + << "\n" + << " const uint8_t *Ptr = DecodeTable;\n" + << " uint32_t CurFieldValue = 0;\n" + << " DecodeStatus S = MCDisassembler::Success;\n" + << " for (;;) {\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" + << " CurFieldValue = fieldFromInstruction(insn, Start, Len);\n" + << " 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" + << " InsnType Val = decodeULEB128(++Ptr, &Len);\n" + << " Ptr += Len;\n" + << " // NumToSkip is a plain 16-bit integer.\n" + << " unsigned NumToSkip = *Ptr++;\n" + << " NumToSkip |= (*Ptr++) << 8;\n" + << "\n" + << " // Perform the filter operation.\n" + << " if (Val != CurFieldValue)\n" + << " Ptr += NumToSkip;\n" + << " 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" + << " InsnType FieldValue = fieldFromInstruction(insn, Start, Len);\n" + << " // Decode the field value.\n" + << " uint32_t ExpectedValue = decodeULEB128(++Ptr, &Len);\n" + << " Ptr += Len;\n" + << " // NumToSkip is a plain 16-bit integer.\n" + << " unsigned NumToSkip = *Ptr++;\n" + << " NumToSkip |= (*Ptr++) << 8;\n" + << "\n" + << " // If the actual and expected values don't match, skip.\n" + << " if (ExpectedValue != FieldValue)\n" + << " Ptr += NumToSkip;\n" + << " 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 16-bit integer.\n" + << " unsigned NumToSkip = *Ptr++;\n" + << " NumToSkip |= (*Ptr++) << 8;\n" + << " // Check the predicate.\n" + << " bool Pred;\n" + << " if (!(Pred = checkDecoderPredicate(PIdx, Bits)))\n" + << " Ptr += NumToSkip;\n" + << " (void)Pred;\n" + << " 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.setOpcode(Opc);\n" + << " bool DecodeComplete;\n" + << " S = decodeToMCInst(S, DecodeIdx, insn, MI, Address, DisAsm, DecodeComplete);\n" + << " assert(DecodeComplete);\n" + << "\n" + << " 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 16-bit integer.\n" + << " unsigned NumToSkip = *Ptr++;\n" + << " NumToSkip |= (*Ptr++) << 8;\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" + << " DEBUG(dbgs() << Loc << \": OPC_TryDecode: opcode \" << Opc\n" + << " << \", using decoder \" << DecodeIdx << \": \");\n" + << "\n" + << " if (DecodeComplete) {\n" + << " // Decoding complete.\n" + << " 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" + << " 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" + << " InsnType PositiveMask = decodeULEB128(++Ptr, &Len);\n" + << " Ptr += Len;\n" + << " InsnType NegativeMask = decodeULEB128(Ptr, &Len);\n" + << " Ptr += Len;\n" + << " bool Fail = (insn & PositiveMask) || (~insn & NegativeMask);\n" + << " if (Fail)\n" + << " S = MCDisassembler::SoftFail;\n" + << " DEBUG(dbgs() << Loc << \": OPC_SoftFail: \" << (Fail ? \"FAIL\\n\":\"PASS\\n\"));\n" + << " break;\n" + << " }\n" + << " case MCD::OPC_Fail: {\n" + << " 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 FixedLenDecoderEmitter::run(raw_ostream &o) { + formatted_raw_ostream OS(o); + OS << "#include \"llvm/MC/MCInst.h\"\n"; + OS << "#include \"llvm/Support/Debug.h\"\n"; + OS << "#include \"llvm/Support/DataTypes.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); + + Target.reverseBitsForLittleEndianEncoding(); + + // Parameterize the decoders based on namespace and instruction width. + NumberedInstructions = &Target.getInstructionsByEnumValue(); + std::map, + std::vector > OpcMap; + std::map > Operands; + + for (unsigned i = 0; i < NumberedInstructions->size(); ++i) { + const CodeGenInstruction *Inst = NumberedInstructions->at(i); + const Record *Def = Inst->TheDef; + unsigned Size = Def->getValueAsInt("Size"); + if (Def->getValueAsString("Namespace") == "TargetOpcode" || + Def->getValueAsBit("isPseudo") || + Def->getValueAsBit("isAsmParserOnly") || + Def->getValueAsBit("isCodeGenOnly")) continue; - if (populateInstruction(*NumberedInstructions[i], i)) - Opcodes.push_back(i); + std::string DecoderNamespace = Def->getValueAsString("DecoderNamespace"); + + if (Size) { + if (populateInstruction(Target, *Inst, i, Operands)) { + OpcMap[std::make_pair(DecoderNamespace, Size)].push_back(i); + } + } + } + + DecoderTableInfo TableInfo; + for (const auto &Opc : OpcMap) { + // Emit the decoder for this namespace+width combination. + FilterChooser FC(*NumberedInstructions, Opc.second, Operands, + 8*Opc.first.second, this); + + // 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(); } + + // 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); + + OS << "\n} // End llvm namespace\n"; } -// Emits disassembler code for instruction decoding. -void FixedLenDecoderEmitter::run(raw_ostream &o) -{ - o << "#include \"llvm/MC/MCInst.h\"\n"; - o << "#include \"llvm/Support/DataTypes.h\"\n"; - o << "#include \n"; - o << '\n'; - o << "namespace llvm {\n\n"; - - NumberedInstructions = Target.getInstructionsByEnumValue(); - populateInstructions(); - FilterChooser FC(NumberedInstructions, Opcodes, Operands); - FC.emitTop(o, 0); - - o << "\n} // End llvm namespace \n"; +namespace llvm { + +void EmitFixedLenDecoder(RecordKeeper &RK, raw_ostream &OS, + std::string PredicateNamespace, + std::string GPrefix, + std::string GPostfix, + std::string ROK, + std::string RFail, + std::string L) { + FixedLenDecoderEmitter(RK, PredicateNamespace, GPrefix, GPostfix, + ROK, RFail, L).run(OS); } + +} // End llvm namespace