diff options
Diffstat (limited to 'utils/TableGen')
| -rw-r--r-- | utils/TableGen/ARMDecoderEmitter.cpp | 197 | ||||
| -rw-r--r-- | utils/TableGen/DisassemblerEmitter.cpp | 5 | ||||
| -rw-r--r-- | utils/TableGen/FixedLenDecoderEmitter.cpp | 1372 | ||||
| -rw-r--r-- | utils/TableGen/FixedLenDecoderEmitter.h | 56 |
4 files changed, 1532 insertions, 98 deletions
diff --git a/utils/TableGen/ARMDecoderEmitter.cpp b/utils/TableGen/ARMDecoderEmitter.cpp index 21af620..a8de745 100644 --- a/utils/TableGen/ARMDecoderEmitter.cpp +++ b/utils/TableGen/ARMDecoderEmitter.cpp @@ -221,7 +221,7 @@ typedef enum { #define BIT_WIDTH 32 // Forward declaration. -class FilterChooser; +class ARMFilterChooser; // Representation of the instruction to work on. typedef bit_value_t insn_t[BIT_WIDTH]; @@ -262,9 +262,9 @@ typedef bit_value_t insn_t[BIT_WIDTH]; /// 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 { +class ARMFilter { protected: - FilterChooser *Owner; // points to the FilterChooser who owns this filter + ARMFilterChooser *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 @@ -276,7 +276,7 @@ protected: std::vector<unsigned> VariableInstructions; // Map of well-known segment value to its delegate. - std::map<unsigned, FilterChooser*> FilterChooserMap; + std::map<unsigned, ARMFilterChooser*> FilterChooserMap; // Number of instructions which fall under FilteredInstructions category. unsigned NumFiltered; @@ -296,16 +296,17 @@ public: } // Return the filter chooser for the group of instructions without constant // segment values. - FilterChooser &getVariableFC() { + ARMFilterChooser &getVariableFC() { assert(NumFiltered == 1); assert(FilterChooserMap.size() == 1); return *(FilterChooserMap.find((unsigned)-1)->second); } - Filter(const Filter &f); - Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, bool mixed); + ARMFilter(const ARMFilter &f); + ARMFilter(ARMFilterChooser &owner, unsigned startBit, unsigned numBits, + bool mixed); - ~Filter(); + ~ARMFilter(); // Divides the decoding task into sub tasks and delegates them to the // inferior FilterChooser's. @@ -333,7 +334,7 @@ typedef enum { ATTR_MIXED } bitAttr_t; -/// FilterChooser - FilterChooser chooses the best filter among a set of Filters +/// ARMFilterChooser - 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 @@ -348,11 +349,11 @@ 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. -class FilterChooser { +class ARMFilterChooser { static TARGET_NAME_t TargetName; protected: - friend class Filter; + friend class ARMFilter; // Vector of codegen instructions to choose our filter. const std::vector<const CodeGenInstruction*> &AllInstructions; @@ -361,14 +362,14 @@ protected: const std::vector<unsigned> Opcodes; // Vector of candidate filters. - std::vector<Filter> Filters; + std::vector<ARMFilter> 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]; // Links to the FilterChooser above us in the decoding tree. - FilterChooser *Parent; + ARMFilterChooser *Parent; // Index of the best filter from Filters. int BestIndex; @@ -376,13 +377,13 @@ protected: public: static void setTargetName(TARGET_NAME_t tn) { TargetName = tn; } - FilterChooser(const FilterChooser &FC) : + ARMFilterChooser(const ARMFilterChooser &FC) : AllInstructions(FC.AllInstructions), Opcodes(FC.Opcodes), Filters(FC.Filters), Parent(FC.Parent), BestIndex(FC.BestIndex) { memcpy(FilterBitValues, FC.FilterBitValues, sizeof(FilterBitValues)); } - FilterChooser(const std::vector<const CodeGenInstruction*> &Insts, + ARMFilterChooser(const std::vector<const CodeGenInstruction*> &Insts, const std::vector<unsigned> &IDs) : AllInstructions(Insts), Opcodes(IDs), Filters(), Parent(NULL), BestIndex(-1) { @@ -392,10 +393,10 @@ public: doFilter(); } - FilterChooser(const std::vector<const CodeGenInstruction*> &Insts, - const std::vector<unsigned> &IDs, - bit_value_t (&ParentFilterBitValues)[BIT_WIDTH], - FilterChooser &parent) : + ARMFilterChooser(const std::vector<const CodeGenInstruction*> &Insts, + const std::vector<unsigned> &IDs, + bit_value_t (&ParentFilterBitValues)[BIT_WIDTH], + ARMFilterChooser &parent) : AllInstructions(Insts), Opcodes(IDs), Filters(), Parent(&parent), BestIndex(-1) { for (unsigned i = 0; i < BIT_WIDTH; ++i) @@ -426,8 +427,9 @@ protected: Insn[i] = bitFromBits(Bits, i); // Set Inst{21} to 1 (wback) when IndexModeBits == IndexModeUpd. - if (getByteField(*AllInstructions[Opcode]->TheDef, "IndexModeBits") - == IndexModeUpd) + Record *R = AllInstructions[Opcode]->TheDef; + if (R->getValue("IndexModeBits") && + getByteField(*R, "IndexModeBits") == IndexModeUpd) Insn[21] = BIT_TRUE; } @@ -452,7 +454,7 @@ protected: /// dumpFilterArray on each filter chooser up to the top level one. void dumpStack(raw_ostream &o, const char *prefix); - Filter &bestFilter() { + ARMFilter &bestFilter() { assert(BestIndex != -1 && "BestIndex not set"); return Filters[BestIndex]; } @@ -497,11 +499,12 @@ protected: bool emitSingletonDecoder(raw_ostream &o, unsigned &Indentation,unsigned Opc); // Emits code to decode the singleton, and then to decode the rest. - void emitSingletonDecoder(raw_ostream &o, unsigned &Indentation,Filter &Best); + void emitSingletonDecoder(raw_ostream &o, unsigned &Indentation, + ARMFilter &Best); // Assign a single filter and run with it. - void runSingleFilter(FilterChooser &owner, unsigned startBit, unsigned numBit, - bool mixed); + void runSingleFilter(ARMFilterChooser &owner, 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. @@ -530,7 +533,7 @@ protected: // // /////////////////////////// -Filter::Filter(const Filter &f) : +ARMFilter::ARMFilter(const ARMFilter &f) : Owner(f.Owner), StartBit(f.StartBit), NumBits(f.NumBits), Mixed(f.Mixed), FilteredInstructions(f.FilteredInstructions), VariableInstructions(f.VariableInstructions), @@ -538,7 +541,7 @@ Filter::Filter(const Filter &f) : LastOpcFiltered(f.LastOpcFiltered), NumVariable(f.NumVariable) { } -Filter::Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, +ARMFilter::ARMFilter(ARMFilterChooser &owner, unsigned startBit, unsigned numBits, bool mixed) : Owner(&owner), StartBit(startBit), NumBits(numBits), Mixed(mixed) { assert(StartBit + NumBits - 1 < BIT_WIDTH); @@ -575,8 +578,8 @@ Filter::Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, && "Filter returns no instruction categories"); } -Filter::~Filter() { - std::map<unsigned, FilterChooser*>::iterator filterIterator; +ARMFilter::~ARMFilter() { + std::map<unsigned, ARMFilterChooser*>::iterator filterIterator; for (filterIterator = FilterChooserMap.begin(); filterIterator != FilterChooserMap.end(); filterIterator++) { @@ -590,7 +593,7 @@ Filter::~Filter() { // 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() { +void ARMFilter::recurse() { std::map<uint64_t, std::vector<unsigned> >::const_iterator mapIterator; bit_value_t BitValueArray[BIT_WIDTH]; @@ -606,12 +609,12 @@ void Filter::recurse() { // Delegates to an inferior filter chooser for futher processing on this // group of instructions whose segment values are variable. - FilterChooserMap.insert(std::pair<unsigned, FilterChooser*>( + FilterChooserMap.insert(std::pair<unsigned, ARMFilterChooser*>( (unsigned)-1, - new FilterChooser(Owner->AllInstructions, - VariableInstructions, - BitValueArray, - *Owner) + new ARMFilterChooser(Owner->AllInstructions, + VariableInstructions, + BitValueArray, + *Owner) )); } @@ -638,18 +641,18 @@ void Filter::recurse() { // Delegates to an inferior filter chooser for futher processing on this // category of instructions. - FilterChooserMap.insert(std::pair<unsigned, FilterChooser*>( + FilterChooserMap.insert(std::pair<unsigned, ARMFilterChooser*>( mapIterator->first, - new FilterChooser(Owner->AllInstructions, - mapIterator->second, - BitValueArray, - *Owner) + new ARMFilterChooser(Owner->AllInstructions, + mapIterator->second, + BitValueArray, + *Owner) )); } } // Emit code to decode instructions given a segment or segments of bits. -void Filter::emit(raw_ostream &o, unsigned &Indentation) { +void ARMFilter::emit(raw_ostream &o, unsigned &Indentation) { o.indent(Indentation) << "// Check Inst{"; if (NumBits > 1) @@ -660,7 +663,7 @@ void Filter::emit(raw_ostream &o, unsigned &Indentation) { o.indent(Indentation) << "switch (fieldFromInstruction(insn, " << StartBit << ", " << NumBits << ")) {\n"; - std::map<unsigned, FilterChooser*>::iterator filterIterator; + std::map<unsigned, ARMFilterChooser*>::iterator filterIterator; bool DefaultCase = false; for (filterIterator = FilterChooserMap.begin(); @@ -709,7 +712,7 @@ void Filter::emit(raw_ostream &o, unsigned &Indentation) { // Returns the number of fanout produced by the filter. More fanout implies // the filter distinguishes more categories of instructions. -unsigned Filter::usefulness() const { +unsigned ARMFilter::usefulness() const { if (VariableInstructions.size()) return FilteredInstructions.size(); else @@ -723,10 +726,10 @@ unsigned Filter::usefulness() const { ////////////////////////////////// // Define the symbol here. -TARGET_NAME_t FilterChooser::TargetName; +TARGET_NAME_t ARMFilterChooser::TargetName; // This provides an opportunity for target specific code emission. -void FilterChooser::emitTopHook(raw_ostream &o) { +void ARMFilterChooser::emitTopHook(raw_ostream &o) { if (TargetName == TARGET_ARM) { // Emit code that references the ARMFormat data type. o << "static const ARMFormat ARMFormats[] = {\n"; @@ -747,7 +750,7 @@ void FilterChooser::emitTopHook(raw_ostream &o) { } // Emit the top level typedef and decodeInstruction() function. -void FilterChooser::emitTop(raw_ostream &o, unsigned &Indentation) { +void ARMFilterChooser::emitTop(raw_ostream &o, unsigned &Indentation) { // Run the target specific emit hook. emitTopHook(o); @@ -818,7 +821,7 @@ void FilterChooser::emitTop(raw_ostream &o, unsigned &Indentation) { // This provides an opportunity for target specific code emission after // emitTop(). -void FilterChooser::emitBot(raw_ostream &o, unsigned &Indentation) { +void ARMFilterChooser::emitBot(raw_ostream &o, unsigned &Indentation) { if (TargetName != TARGET_THUMB) return; // Emit code that decodes the Thumb ISA. @@ -843,7 +846,7 @@ void FilterChooser::emitBot(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, +bool ARMFilterChooser::fieldFromInsn(uint64_t &Field, insn_t &Insn, unsigned StartBit, unsigned NumBits) const { Field = 0; @@ -860,7 +863,7 @@ 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, +void ARMFilterChooser::dumpFilterArray(raw_ostream &o, bit_value_t (&filter)[BIT_WIDTH]) { unsigned bitIndex; @@ -884,8 +887,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 ARMFilterChooser::dumpStack(raw_ostream &o, const char *prefix) { + ARMFilterChooser *current = this; while (current) { o << prefix; @@ -896,7 +899,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 ARMFilterChooser::SingletonExists(unsigned Opc) { insn_t Insn0; insnWithID(Insn0, Opc); @@ -923,7 +926,7 @@ void FilterChooser::SingletonExists(unsigned Opc) { // 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<unsigned> &StartBits, +unsigned ARMFilterChooser::getIslands(std::vector<unsigned> &StartBits, std::vector<unsigned> &EndBits, std::vector<uint64_t> &FieldVals, insn_t &Insn) { unsigned Num, BitNo; @@ -983,7 +986,7 @@ unsigned FilterChooser::getIslands(std::vector<unsigned> &StartBits, // 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, +bool ARMFilterChooser::emitSingletonDecoder(raw_ostream &o, unsigned &Indentation, unsigned Opc) { std::vector<unsigned> StartBits; std::vector<unsigned> EndBits; @@ -1046,8 +1049,9 @@ bool FilterChooser::emitSingletonDecoder(raw_ostream &o, unsigned &Indentation, } // Emits code to decode the singleton, and then to decode the rest. -void FilterChooser::emitSingletonDecoder(raw_ostream &o, unsigned &Indentation, - Filter &Best) { +void ARMFilterChooser::emitSingletonDecoder(raw_ostream &o, + unsigned &Indentation, + ARMFilter &Best) { unsigned Opc = Best.getSingletonOpc(); @@ -1063,10 +1067,11 @@ void FilterChooser::emitSingletonDecoder(raw_ostream &o, unsigned &Indentation, // 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 ARMFilterChooser::runSingleFilter(ARMFilterChooser &owner, + unsigned startBit, + unsigned numBit, bool mixed) { Filters.clear(); - Filter F(*this, startBit, numBit, true); + ARMFilter F(*this, startBit, numBit, true); Filters.push_back(F); BestIndex = 0; // Sole Filter instance to choose from. bestFilter().recurse(); @@ -1074,18 +1079,18 @@ 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) { +void ARMFilterChooser::reportRegion(bitAttr_t RA, unsigned StartBit, + unsigned BitIndex, bool AllowMixed) { if (RA == ATTR_MIXED && AllowMixed) - Filters.push_back(Filter(*this, StartBit, BitIndex - StartBit, true)); + Filters.push_back(ARMFilter(*this, StartBit, BitIndex - StartBit, true)); else if (RA == ATTR_ALL_SET && !AllowMixed) - Filters.push_back(Filter(*this, StartBit, BitIndex - StartBit, false)); + Filters.push_back(ARMFilter(*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) { +bool ARMFilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { Filters.clear(); BestIndex = -1; unsigned numInstructions = Opcodes.size(); @@ -1317,7 +1322,7 @@ bool FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { // 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() { +void ARMFilterChooser::doFilter() { unsigned Num = Opcodes.size(); assert(Num && "FilterChooser created with no instructions"); @@ -1350,7 +1355,7 @@ void FilterChooser::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 FilterChooser::emit(raw_ostream &o, unsigned &Indentation) { +bool ARMFilterChooser::emit(raw_ostream &o, unsigned &Indentation) { if (Opcodes.size() == 1) // There is only one instruction in the set, which is great! // Call emitSingletonDecoder() to see whether there are any remaining @@ -1359,7 +1364,7 @@ bool FilterChooser::emit(raw_ostream &o, unsigned &Indentation) { // Choose the best filter to do the decodings! if (BestIndex != -1) { - Filter &Best = bestFilter(); + ARMFilter &Best = bestFilter(); if (Best.getNumFiltered() == 1) emitSingletonDecoder(o, Indentation, Best); else @@ -1538,7 +1543,7 @@ protected: std::vector<unsigned> Opcodes2; ARMDecoderEmitter &Frontend; CodeGenTarget Target; - FilterChooser *FC; + ARMFilterChooser *FC; TARGET_NAME_t TargetName; }; @@ -1752,32 +1757,20 @@ ARMDEBackend::populateInstruction(const CodeGenInstruction &CGI, void ARMDecoderEmitter::ARMDEBackend::populateInstructions() { getInstructionsByEnumValue(NumberedInstructions); - uint16_t numUIDs = NumberedInstructions.size(); - uint16_t uid; - - const char *instClass = NULL; - - switch (TargetName) { - case TARGET_ARM: - instClass = "InstARM"; - break; - default: - assert(0 && "Unreachable code!"); - } - - for (uid = 0; uid < numUIDs; uid++) { - // filter out intrinsics - if (!NumberedInstructions[uid]->TheDef->isSubClassOf(instClass)) - continue; + unsigned numUIDs = NumberedInstructions.size(); + if (TargetName == TARGET_ARM) { + for (unsigned uid = 0; uid < numUIDs; uid++) { + // filter out intrinsics + if (!NumberedInstructions[uid]->TheDef->isSubClassOf("InstARM")) + continue; - if (populateInstruction(*NumberedInstructions[uid], TargetName)) - Opcodes.push_back(uid); - } + if (populateInstruction(*NumberedInstructions[uid], TargetName)) + Opcodes.push_back(uid); + } - // Special handling for the ARM chip, which supports two modes of execution. - // This branch handles the Thumb opcodes. - if (TargetName == TARGET_ARM) { - for (uid = 0; uid < numUIDs; uid++) { + // Special handling for the ARM chip, which supports two modes of execution. + // This branch handles the Thumb opcodes. + for (unsigned uid = 0; uid < numUIDs; uid++) { // filter out intrinsics if (!NumberedInstructions[uid]->TheDef->isSubClassOf("InstARM") && !NumberedInstructions[uid]->TheDef->isSubClassOf("InstThumb")) @@ -1786,6 +1779,18 @@ void ARMDecoderEmitter::ARMDEBackend::populateInstructions() { if (populateInstruction(*NumberedInstructions[uid], TARGET_THUMB)) Opcodes2.push_back(uid); } + + return; + } + + // For other targets. + for (unsigned uid = 0; uid < numUIDs; uid++) { + Record *R = NumberedInstructions[uid]->TheDef; + if (R->getValueAsString("Namespace") == "TargetOpcode") + continue; + + if (populateInstruction(*NumberedInstructions[uid], TargetName)) + Opcodes.push_back(uid); } } @@ -1805,20 +1810,20 @@ void ARMDecoderEmitter::ARMDEBackend::emit(raw_ostream &o) { o << '\n'; o << "namespace llvm {\n\n"; - FilterChooser::setTargetName(TargetName); + ARMFilterChooser::setTargetName(TargetName); switch (TargetName) { case TARGET_ARM: { // Emit common utility and ARM ISA decoder. - FC = new FilterChooser(NumberedInstructions, Opcodes); + FC = new ARMFilterChooser(NumberedInstructions, Opcodes); // Reset indentation level. unsigned Indentation = 0; FC->emitTop(o, Indentation); delete FC; // Emit Thumb ISA decoder as well. - FilterChooser::setTargetName(TARGET_THUMB); - FC = new FilterChooser(NumberedInstructions, Opcodes2); + ARMFilterChooser::setTargetName(TARGET_THUMB); + FC = new ARMFilterChooser(NumberedInstructions, Opcodes2); // Reset indentation level. Indentation = 0; FC->emitBot(o, Indentation); diff --git a/utils/TableGen/DisassemblerEmitter.cpp b/utils/TableGen/DisassemblerEmitter.cpp index 2d8bf66..90a2af2 100644 --- a/utils/TableGen/DisassemblerEmitter.cpp +++ b/utils/TableGen/DisassemblerEmitter.cpp @@ -13,6 +13,7 @@ #include "X86DisassemblerTables.h" #include "X86RecognizableInstr.h" #include "ARMDecoderEmitter.h" +#include "FixedLenDecoderEmitter.h" using namespace llvm; using namespace llvm::X86Disassembler; @@ -127,11 +128,11 @@ void DisassemblerEmitter::run(raw_ostream &OS) { } // Fixed-instruction-length targets use a common disassembler. + // ARM use its own implementation for now. if (Target.getName() == "ARM") { ARMDecoderEmitter(Records).run(OS); return; } - throw TGError(Target.getTargetRecord()->getLoc(), - "Unable to generate disassembler for this target"); + FixedLenDecoderEmitter(Records).run(OS); } diff --git a/utils/TableGen/FixedLenDecoderEmitter.cpp b/utils/TableGen/FixedLenDecoderEmitter.cpp new file mode 100644 index 0000000..2c222b3 --- /dev/null +++ b/utils/TableGen/FixedLenDecoderEmitter.cpp @@ -0,0 +1,1372 @@ +//===------------ FixedLenDecoderEmitter.cpp - Decoder Generator ----------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// It contains the tablegen backend that emits the decoder functions for +// targets with fixed length instruction set. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "decoder-emitter" + +#include "FixedLenDecoderEmitter.h" +#include "CodeGenTarget.h" +#include "Record.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" + +#include <vector> +#include <map> +#include <string> + +using namespace llvm; + +// 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(BitsInit &bits, unsigned index) { + if (BitInit *bit = dynamic_cast<BitInit*>(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--) { + switch (bitFromBits(bits, index - 1)) { + case BIT_TRUE: + o << "1"; + break; + case BIT_FALSE: + o << "0"; + break; + case BIT_UNSET: + o << "_"; + break; + default: + assert(0 && "unexpected return value from bitFromBits"); + } + } +} + +static BitsInit &getBitsField(const Record &def, const char *str) { + BitsInit *bits = def.getValueAsBitsInit(str); + return *bits; +} + +// Forward declaration. +class FilterChooser; + +// FIXME: Possibly auto-detected? +#define BIT_WIDTH 32 + +// Representation of the instruction to work on. +typedef bit_value_t insn_t[BIT_WIDTH]; + +/// 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 regsisters. +/// +/// 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: + 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<uint64_t, std::vector<unsigned> > FilteredInstructions; + + // Set of uid's with non-constant segment values. + std::vector<unsigned> VariableInstructions; + + // Map of well-known segment value to its delegate. + std::map<unsigned, FilterChooser*> FilterChooserMap; + + // Number of instructions which fall under FilteredInstructions category. + unsigned NumFiltered; + + // 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() { + assert(NumFiltered == 1); + return LastOpcFiltered; + } + // Return the filter chooser for the group of instructions without constant + // segment values. + FilterChooser &getVariableFC() { + assert(NumFiltered == 1); + assert(FilterChooserMap.size() == 1); + return *(FilterChooserMap.find((unsigned)-1)->second); + } + + Filter(const Filter &f); + Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, bool mixed); + + ~Filter(); + + // 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 code to decode instructions given a segment or segments of bits. + void emit(raw_ostream &o, unsigned &Indentation); + + // 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 + +// 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. + const std::vector<const CodeGenInstruction*> &AllInstructions; + + // Vector of uid's for this filter chooser to work on. + const std::vector<unsigned> Opcodes; + + // Lookup table for the operand decoding of instructions. + std::map<unsigned, std::vector<OperandInfo> > &Operands; + + // Vector of candidate filters. + std::vector<Filter> 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]; + + // Links to the FilterChooser above us in the decoding tree. + FilterChooser *Parent; + + // Index of the best filter from Filters. + int BestIndex; + +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<const CodeGenInstruction*> &Insts, + const std::vector<unsigned> &IDs, + std::map<unsigned, std::vector<OperandInfo> > &Ops) : + AllInstructions(Insts), Opcodes(IDs), Operands(Ops), Filters(), + Parent(NULL), BestIndex(-1) { + for (unsigned i = 0; i < BIT_WIDTH; ++i) + FilterBitValues[i] = BIT_UNFILTERED; + + doFilter(); + } + + FilterChooser(const std::vector<const CodeGenInstruction*> &Insts, + const std::vector<unsigned> &IDs, + std::map<unsigned, std::vector<OperandInfo> > &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]; + + 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); + +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); + } + + // Returns the record name. + const std::string &nameWithID(unsigned Opcode) const { + return AllInstructions[Opcode]->TheDef->getName(); + } + + // Populates the field of the insn given the start position and the number of + // consecutive bits to scan for. + // + // Returns false if there exists any uninitialized bit value in the range. + // Returns true, otherwise. + bool fieldFromInsn(uint64_t &Field, insn_t &Insn, unsigned StartBit, + unsigned NumBits) const; + + /// dumpFilterArray - dumpFilterArray prints out debugging info for the given + /// filter array as a series of chars. + void dumpFilterArray(raw_ostream &o, bit_value_t (&filter)[BIT_WIDTH]); + + /// 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); + + Filter &bestFilter() { + assert(BestIndex != -1 && "BestIndex not set"); + return Filters[BestIndex]; + } + + // Called from Filter::recurse() when singleton exists. For debug purpose. + void SingletonExists(unsigned Opc); + + bool PositionFiltered(unsigned i) { + 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<unsigned> &StartBits, + std::vector<unsigned> &EndBits, std::vector<uint64_t> &FieldVals, + insn_t &Insn); + + // 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 code to decode the singleton, and then to decode the rest. + void emitSingletonDecoder(raw_ostream &o, unsigned &Indentation,Filter &Best); + + // Assign a single filter and run with it. + void runSingleFilter(FilterChooser &owner, 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(); + + // 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); +}; + +/////////////////////////// +// // +// Filter Implmenetation // +// // +/////////////////////////// + +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(FilterChooser &owner, unsigned startBit, unsigned numBits, + bool mixed) : Owner(&owner), StartBit(startBit), NumBits(numBits), + Mixed(mixed) { + assert(StartBit + NumBits - 1 < BIT_WIDTH); + + NumFiltered = 0; + LastOpcFiltered = 0; + NumVariable = 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]); + + 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 unspecfied. This contributes to + // one additional member of "Variable" instructions. + VariableInstructions.push_back(Owner->Opcodes[i]); + ++NumVariable; + } + } + + assert((FilteredInstructions.size() + VariableInstructions.size() > 0) + && "Filter returns no instruction categories"); +} + +Filter::~Filter() { + std::map<unsigned, FilterChooser*>::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 +// 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() { + std::map<uint64_t, std::vector<unsigned> >::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; + + if (VariableInstructions.size()) { + // Conservatively marks each segment position as BIT_UNSET. + for (bitIndex = 0; bitIndex < NumBits; bitIndex++) + BitValueArray[StartBit + bitIndex] = BIT_UNSET; + + // Delegates to an inferior filter chooser for futher processing on this + // group of instructions whose segment values are variable. + FilterChooserMap.insert(std::pair<unsigned, FilterChooser*>( + (unsigned)-1, + new FilterChooser(Owner->AllInstructions, + VariableInstructions, + Owner->Operands, + BitValueArray, + *Owner) + )); + } + + // No need to recurse for a singleton filtered instruction. + // See also Filter::emit(). + if (getNumFiltered() == 1) { + //Owner->SingletonExists(LastOpcFiltered); + assert(FilterChooserMap.size() == 1); + return; + } + + // Otherwise, create sub choosers. + for (mapIterator = FilteredInstructions.begin(); + mapIterator != FilteredInstructions.end(); + mapIterator++) { + + // Marks all the segment positions with either BIT_TRUE or BIT_FALSE. + for (bitIndex = 0; bitIndex < NumBits; bitIndex++) { + if (mapIterator->first & (1ULL << bitIndex)) + BitValueArray[StartBit + bitIndex] = BIT_TRUE; + else + BitValueArray[StartBit + bitIndex] = BIT_FALSE; + } + + // Delegates to an inferior filter chooser for futher processing on this + // category of instructions. + FilterChooserMap.insert(std::pair<unsigned, FilterChooser*>( + mapIterator->first, + new FilterChooser(Owner->AllInstructions, + mapIterator->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"; + + o.indent(Indentation) << "switch (fieldFromInstruction(insn, " + << StartBit << ", " << NumBits << ")) {\n"; + + std::map<unsigned, FilterChooser*>::iterator filterIterator; + + bool DefaultCase = false; + for (filterIterator = FilterChooserMap.begin(); + filterIterator != FilterChooserMap.end(); + filterIterator++) { + + // 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"; + + // 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; } + } + + // 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"; + } +} + +// 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()) + return FilteredInstructions.size(); + else + return FilteredInstructions.size() + 1; +} + +////////////////////////////////// +// // +// Filterchooser Implementation // +// // +////////////////////////////////// + +// 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"; + + ++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; + + o.indent(Indentation) << "else\n"; + + ++Indentation; ++Indentation; + o.indent(Indentation) << "fieldMask = ((1 << numBits) - 1) << startBit;\n"; + --Indentation; --Indentation; + + o << '\n'; + o.indent(Indentation) << "return (insn & fieldMask) >> startBit;\n"; + --Indentation; --Indentation; + + o.indent(Indentation) << "}\n"; + + o << '\n'; + + o.indent(Indentation) << + "static bool decodeInstruction(MCInst &MI, field_t insn) {\n"; + o.indent(Indentation) << " unsigned tmp = 0;\n"; + + ++Indentation; ++Indentation; + // Emits code to decode the instructions. + emit(o, Indentation); + + o << '\n'; + o.indent(Indentation) << "return false;\n"; + --Indentation; --Indentation; + + o.indent(Indentation) << "}\n"; + + o << '\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, + bit_value_t (&filter)[BIT_WIDTH]) { + unsigned bitIndex; + + for (bitIndex = BIT_WIDTH; 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) { + FilterChooser *current = this; + + while (current) { + o << prefix; + dumpFilterArray(o, current->FilterBitValues); + o << '\n'; + current = current->Parent; + } +} + +// Called from Filter::recurse() when singleton exists. For debug purpose. +void FilterChooser::SingletonExists(unsigned Opc) { + insn_t Insn0; + insnWithID(Insn0, Opc); + + errs() << "Singleton exists: " << nameWithID(Opc) + << " with its decoding dominating "; + for (unsigned i = 0; i < Opcodes.size(); ++i) { + if (Opcodes[i] == Opc) continue; + errs() << nameWithID(Opcodes[i]) << ' '; + } + errs() << '\n'; + + dumpStack(errs(), "\t\t"); + for (unsigned i = 0; i < Opcodes.size(); i++) { + const std::string &Name = nameWithID(Opcodes[i]); + + errs() << '\t' << Name << " "; + dumpBits(errs(), + getBitsField(*AllInstructions[Opcodes[i]]->TheDef, "Inst")); + errs() << '\n'; + } +} + +// 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<unsigned> &StartBits, + std::vector<unsigned> &EndBits, std::vector<uint64_t> &FieldVals, + insn_t &Insn) { + 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; + int Val = -1; + + for (unsigned i = 0; i < BIT_WIDTH; ++i) { + Val = Value(Insn[i]); + bool Filtered = PositionFiltered(i); + switch (State) { + default: + assert(0 && "Unreachable code!"); + break; + 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(BIT_WIDTH - 1); + FieldVals.push_back(FieldVal); + ++Num; + } + + assert(StartBits.size() == Num && EndBits.size() == Num && + FieldVals.size() == Num); + 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<unsigned> StartBits; + std::vector<unsigned> EndBits; + std::vector<uint64_t> 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(); + 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<OperandInfo>& InsnOperands = Operands[Opc]; + for (std::vector<OperandInfo>::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"; + } + } + + o.indent(Indentation) << " return true; // " << nameWithID(Opc) + << '\n'; + o.indent(Indentation) << "}\n"; + return true; + } + + // Otherwise, there are more decodings to be done! + + // Emit code to match the island(s) for the singleton. + o.indent(Indentation) << "// Check "; + + for (I = Size; I != 0; --I) { + o << "Inst{" << EndBits[I-1] << '-' << StartBits[I-1] << "} "; + if (I > 1) + o << "&& "; + else + o << "for singleton decoding...\n"; + } + + o.indent(Indentation) << "if ("; + + 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) + o << " && "; + else + o << ") {\n"; + } + o.indent(Indentation) << " MI.setOpcode(" << Opc << ");\n"; + std::vector<OperandInfo>& InsnOperands = Operands[Opc]; + for (std::vector<OperandInfo>::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"; + } + } + o.indent(Indentation) << " return true; // " << nameWithID(Opc) + << '\n'; + o.indent(Indentation) << "}\n"; + + 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 Opc = Best.getSingletonOpc(); + + emitSingletonDecoder(o, Indentation, Opc); + + // Emit code for the rest. + o.indent(Indentation) << "else\n"; + + Indentation += 2; + Best.getVariableFC().emit(o, Indentation); + Indentation -= 2; +} + +// 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) { + Filters.clear(); + Filter F(*this, startBit, numBit, true); + Filters.push_back(F); + 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.push_back(Filter(*this, StartBit, BitIndex - StartBit, true)); + else if (RA == ATTR_ALL_SET && !AllowMixed) + Filters.push_back(Filter(*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 (unsigned i = 0; i < Opcodes.size(); ++i) { + std::vector<unsigned> StartBits; + std::vector<unsigned> EndBits; + std::vector<uint64_t> FieldVals; + insn_t Insn; + + insnWithID(Insn, Opcodes[i]); + + // 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); + return true; + } + } + } + + unsigned BitIndex, InsnIndex; + + // 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) + + bitAttr_t bitAttrs[BIT_WIDTH]; + + // 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) + if (FilterBitValues[BitIndex] == BIT_TRUE || + FilterBitValues[BitIndex] == BIT_FALSE) + bitAttrs[BitIndex] = ATTR_FILTERED; + else + bitAttrs[BitIndex] = ATTR_NONE; + + for (InsnIndex = 0; InsnIndex < numInstructions; ++InsnIndex) { + insn_t insn; + + insnWithID(insn, Opcodes[InsnIndex]); + + for (BitIndex = 0; BitIndex < BIT_WIDTH; ++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 < BIT_WIDTH; 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: + assert(0 && "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: + assert(0 && "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: + assert(0 && "Unexpected bitAttr!"); + } + break; + case ATTR_ALL_UNSET: + assert(0 && "regionAttr state machine has no ATTR_UNSET state"); + case ATTR_FILTERED: + assert(0 && "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; +} + +// 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) + // 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]); + + // Choose the best filter to do the decodings! + if (BestIndex != -1) { + Filter &Best = bestFilter(); + if (Best.getNumFiltered() == 1) + emitSingletonDecoder(o, Indentation, Best); + else + bestFilter().emit(o, Indentation); + return false; + } + + // 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'; + } + + // Print out useful conflict information for postmortem analysis. + errs() << "Decoding Conflict:\n"; + + dumpStack(errs(), "\t\t"); + + for (unsigned i = 0; i < Opcodes.size(); i++) { + const std::string &Name = nameWithID(Opcodes[i]); + + errs() << '\t' << Name << " "; + dumpBits(errs(), + getBitsField(*AllInstructions[Opcodes[i]]->TheDef, "Inst")); + errs() << '\n'; + } + + return true; +} + +bool FixedLenDecoderEmitter::populateInstruction(const CodeGenInstruction &CGI, + unsigned Opc){ + 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")) + return false; + + std::vector<OperandInfo> 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)); + Operands[Opc] = InsnOperands; + return true; + } + + // 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<std::pair<Init*, std::string> > 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->getArgName(i))); + 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<std::pair<Init*, std::string> >::iterator + NI = InOutOperands.begin(), NE = InOutOperands.end(); NI != NE; ++NI) { + unsigned PrevBit = ~0; + unsigned Base = ~0; + unsigned PrevPos = ~0; + std::string Decoder = ""; + + for (unsigned bi = 0; bi < Bits.getNumBits(); ++bi) { + VarBitInit *BI = dynamic_cast<VarBitInit*>(Bits.getBit(bi)); + if (!BI) continue; + + VarInit *Var = dynamic_cast<VarInit*>(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 + continue; + } + + if ((PrevPos != ~0U && bi-1 != PrevPos) || + (CurrBit != ~0U && CurrBit-1 != PrevBit)) { + PrevBit = ~0; + Base = ~0; + PrevPos = ~0; + } + + 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<TypedInit*>(NI->first); + RecordRecTy *Type = dynamic_cast<RecordRecTy*>(TI->getType()); + Record *TypeRecord = Type->getRecord(); + bool isReg = false; + if (TypeRecord->isSubClassOf("RegisterClass")) { + Decoder = "Decode" + Type->getRecord()->getName() + "RegisterClass"; + isReg = true; + } + + RecordVal *DecoderString = TypeRecord->getValue("DecoderMethod"); + StringInit *String = DecoderString ? + dynamic_cast<StringInit*>(DecoderString->getValue()) : + 0; + if (!isReg && String && String->getValue() != "") + Decoder = String->getValue(); + } + + if (Base != ~0U) { + InsnOperands.push_back(OperandInfo(Base, PrevBit+1, Decoder)); + DEBUG(errs() << "ENCODED OPERAND: $" << NI->second << " @ (" + << utostr(Base+PrevBit) << ", " << utostr(Base) << ")\n"); + } + } + + Operands[Opc] = InsnOperands; + + +#if 0 + 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 true; +} + +void FixedLenDecoderEmitter::populateInstructions() { + for (unsigned i = 0, e = NumberedInstructions.size(); i < e; ++i) { + Record *R = NumberedInstructions[i]->TheDef; + if (R->getValueAsString("Namespace") == "TargetOpcode") + continue; + + if (populateInstruction(*NumberedInstructions[i], i)) + Opcodes.push_back(i); + } +} + +// 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 <assert.h>\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"; +} diff --git a/utils/TableGen/FixedLenDecoderEmitter.h b/utils/TableGen/FixedLenDecoderEmitter.h new file mode 100644 index 0000000..d46a495 --- /dev/null +++ b/utils/TableGen/FixedLenDecoderEmitter.h @@ -0,0 +1,56 @@ +//===------------ FixedLenDecoderEmitter.h - Decoder Generator --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// It contains the tablegen backend that emits the decoder functions for +// targets with fixed length instruction set. +// +//===----------------------------------------------------------------------===// + +#ifndef FixedLenDECODEREMITTER_H +#define FixedLenDECODEREMITTER_H + +#include "CodeGenTarget.h" +#include "TableGenBackend.h" + +#include "llvm/Support/DataTypes.h" + +namespace llvm { + +struct OperandInfo { + unsigned FieldBase; + unsigned FieldLength; + std::string Decoder; + + OperandInfo(unsigned FB, unsigned FL, std::string D) + : FieldBase(FB), FieldLength(FL), Decoder(D) { } +}; + +class FixedLenDecoderEmitter : public TableGenBackend { +public: + FixedLenDecoderEmitter(RecordKeeper &R) : + Records(R), Target(R), + NumberedInstructions(Target.getInstructionsByEnumValue()) {} + + // run - Output the code emitter + void run(raw_ostream &o); + +private: + RecordKeeper &Records; + CodeGenTarget Target; + std::vector<const CodeGenInstruction*> NumberedInstructions; + std::vector<unsigned> Opcodes; + std::map<unsigned, std::vector<OperandInfo> > Operands; + + bool populateInstruction(const CodeGenInstruction &CGI, unsigned Opc); + void populateInstructions(); +}; + +} // end llvm namespace + +#endif |