1212420Sken//===------------ FixedLenDecoderEmitter.cpp - Decoder Generator ----------===// 2212420Sken// 3237683Sken// The LLVM Compiler Infrastructure 4212420Sken// 5212420Sken// This file is distributed under the University of Illinois Open Source 6212420Sken// License. See LICENSE.TXT for details. 7212420Sken// 8212420Sken//===----------------------------------------------------------------------===// 9212420Sken// 10212420Sken// It contains the tablegen backend that emits the decoder functions for 11212420Sken// targets with fixed length instruction set. 12212420Sken// 13212420Sken//===----------------------------------------------------------------------===// 14212420Sken 15212420Sken#define DEBUG_TYPE "decoder-emitter" 16212420Sken 17212420Sken#include "CodeGenTarget.h" 18212420Sken#include "llvm/ADT/APInt.h" 19212420Sken#include "llvm/ADT/SmallString.h" 20212420Sken#include "llvm/ADT/StringExtras.h" 21212420Sken#include "llvm/ADT/StringRef.h" 22212420Sken#include "llvm/ADT/Twine.h" 23212420Sken#include "llvm/MC/MCFixedLenDisassembler.h" 24212420Sken#include "llvm/Support/DataTypes.h" 25212420Sken#include "llvm/Support/Debug.h" 26230592Sken#include "llvm/Support/FormattedStream.h" 27230592Sken#include "llvm/Support/LEB128.h" 28230592Sken#include "llvm/Support/raw_ostream.h" 29230592Sken#include "llvm/TableGen/Error.h" 30230592Sken#include "llvm/TableGen/Record.h" 31212420Sken#include "llvm/TableGen/TableGenBackend.h" 32212420Sken#include <map> 33212420Sken#include <string> 34212420Sken#include <vector> 35212420Sken 36212420Skenusing namespace llvm; 37230592Sken 38212420Skennamespace { 39212420Skenstruct EncodingField { 40212420Sken unsigned Base, Width, Offset; 41212420Sken EncodingField(unsigned B, unsigned W, unsigned O) 42212420Sken : Base(B), Width(W), Offset(O) { } 43212420Sken}; 44212420Sken 45212420Skenstruct OperandInfo { 46212420Sken std::vector<EncodingField> Fields; 47212420Sken std::string Decoder; 48212420Sken 49212420Sken OperandInfo(std::string D) 50216088Sken : Decoder(D) { } 51230592Sken 52230592Sken void addField(unsigned Base, unsigned Width, unsigned Offset) { 53230592Sken Fields.push_back(EncodingField(Base, Width, Offset)); 54230592Sken } 55212420Sken 56212420Sken unsigned numFields() const { return Fields.size(); } 57212420Sken 58212420Sken typedef std::vector<EncodingField>::const_iterator const_iterator; 59212420Sken 60230592Sken const_iterator begin() const { return Fields.begin(); } 61230592Sken const_iterator end() const { return Fields.end(); } 62212420Sken}; 63212420Sken 64230592Skentypedef std::vector<uint8_t> DecoderTable; 65212420Skentypedef uint32_t DecoderFixup; 66212420Skentypedef std::vector<DecoderFixup> FixupList; 67212420Skentypedef std::vector<FixupList> FixupScopeList; 68212420Skentypedef SetVector<std::string> PredicateSet; 69212420Skentypedef SetVector<std::string> DecoderSet; 70212420Skenstruct DecoderTableInfo { 71212420Sken DecoderTable Table; 72216088Sken FixupScopeList FixupStack; 73216088Sken PredicateSet Predicates; 74216088Sken DecoderSet Decoders; 75212420Sken}; 76212420Sken 77212420Sken} // End anonymous namespace 78212420Sken 79212420Skennamespace { 80212420Skenclass FixedLenDecoderEmitter { 81212420Sken const std::vector<const CodeGenInstruction*> *NumberedInstructions; 82230592Skenpublic: 83230592Sken 84212420Sken // Defaults preserved here for documentation, even though they aren't 85212420Sken // strictly necessary given the way that this is currently being called. 86230592Sken FixedLenDecoderEmitter(RecordKeeper &R, 87212420Sken std::string PredicateNamespace, 88230592Sken std::string GPrefix = "if (", 89230592Sken std::string GPostfix = " == MCDisassembler::Fail)" 90212420Sken " return MCDisassembler::Fail;", 91230592Sken std::string ROK = "MCDisassembler::Success", 92230592Sken std::string RFail = "MCDisassembler::Fail", 93230592Sken std::string L = "") : 94230592Sken Target(R), 95230592Sken PredicateNamespace(PredicateNamespace), 96230592Sken GuardPrefix(GPrefix), GuardPostfix(GPostfix), 97230592Sken ReturnOK(ROK), ReturnFail(RFail), Locals(L) {} 98230592Sken 99230592Sken // Emit the decoder state machine table. 100230592Sken void emitTable(formatted_raw_ostream &o, DecoderTable &Table, 101230592Sken unsigned Indentation, unsigned BitWidth, 102230592Sken StringRef Namespace) const; 103230592Sken void emitPredicateFunction(formatted_raw_ostream &OS, 104230592Sken PredicateSet &Predicates, 105230592Sken unsigned Indentation) const; 106230592Sken void emitDecoderFunction(formatted_raw_ostream &OS, 107230592Sken DecoderSet &Decoders, 108230592Sken unsigned Indentation) const; 109230592Sken 110230592Sken // run - Output the code emitter 111230592Sken void run(raw_ostream &o); 112230592Sken 113230592Skenprivate: 114212420Sken CodeGenTarget Target; 115212420Skenpublic: 116230592Sken std::string PredicateNamespace; 117212420Sken std::string GuardPrefix, GuardPostfix; 118212420Sken std::string ReturnOK, ReturnFail; 119212420Sken std::string Locals; 120212420Sken}; 121212420Sken} // End anonymous namespace 122212420Sken 123212420Sken// The set (BIT_TRUE, BIT_FALSE, BIT_UNSET) represents a ternary logic system 124212420Sken// for a bit value. 125230592Sken// 126230592Sken// BIT_UNFILTERED is used as the init value for a filter position. It is used 127212420Sken// only for filter processings. 128212420Skentypedef enum { 129230592Sken BIT_TRUE, // '1' 130216088Sken BIT_FALSE, // '0' 131216088Sken BIT_UNSET, // '?' 132216088Sken BIT_UNFILTERED // unfiltered 133216088Sken} bit_value_t; 134216088Sken 135230592Skenstatic bool ValueSet(bit_value_t V) { 136212420Sken return (V == BIT_TRUE || V == BIT_FALSE); 137230592Sken} 138230592Skenstatic bool ValueNotSet(bit_value_t V) { 139230592Sken return (V == BIT_UNSET); 140230592Sken} 141253549Skenstatic int Value(bit_value_t V) { 142253549Sken return ValueNotSet(V) ? -1 : (V == BIT_FALSE ? 0 : 1); 143253549Sken} 144253549Skenstatic bit_value_t bitFromBits(const BitsInit &bits, unsigned index) { 145230592Sken if (BitInit *bit = dyn_cast<BitInit>(bits.getBit(index))) 146230592Sken return bit->getValue() ? BIT_TRUE : BIT_FALSE; 147230592Sken 148230592Sken // The bit is uninitialized. 149230592Sken return BIT_UNSET; 150212420Sken} 151231240Sken// Prints the bit value for each position. 152230592Skenstatic void dumpBits(raw_ostream &o, const BitsInit &bits) { 153216368Sken for (unsigned index = bits.getNumBits(); index > 0; --index) { 154230592Sken switch (bitFromBits(bits, index - 1)) { 155230592Sken case BIT_TRUE: 156216368Sken o << "1"; 157230592Sken break; 158230592Sken case BIT_FALSE: 159230592Sken o << "0"; 160230592Sken break; 161216368Sken case BIT_UNSET: 162216368Sken o << "_"; 163230592Sken break; 164216368Sken default: 165216368Sken llvm_unreachable("unexpected return value from bitFromBits"); 166230592Sken } 167230592Sken } 168230592Sken} 169230592Sken 170230592Skenstatic BitsInit &getBitsField(const Record &def, const char *str) { 171230592Sken BitsInit *bits = def.getValueAsBitsInit(str); 172230592Sken return *bits; 173230592Sken} 174230592Sken 175212420Sken// Forward declaration. 176253460Sscottlnamespace { 177253460Sscottlclass FilterChooser; 178230592Sken} // End anonymous namespace 179230592Sken 180230592Sken// Representation of the instruction to work on. 181253460Sscottltypedef std::vector<bit_value_t> insn_t; 182230592Sken 183230592Sken/// Filter - Filter works with FilterChooser to produce the decoding tree for 184230592Sken/// the ISA. 185253460Sscottl/// 186230592Sken/// It is useful to think of a Filter as governing the switch stmts of the 187230592Sken/// decoding tree in a certain level. Each case stmt delegates to an inferior 188230592Sken/// FilterChooser to decide what further decoding logic to employ, or in another 189212420Sken/// words, what other remaining bits to look at. The FilterChooser eventually 190230592Sken/// chooses a best Filter to do its job. 191230592Sken/// 192230592Sken/// This recursive scheme ends when the number of Opcodes assigned to the 193253460Sscottl/// FilterChooser becomes 1 or if there is a conflict. A conflict happens when 194253460Sscottl/// the Filter/FilterChooser combo does not know how to distinguish among the 195230592Sken/// Opcodes assigned. 196230592Sken/// 197230592Sken/// An example of a conflict is 198230592Sken/// 199230592Sken/// Conflict: 200253460Sscottl/// 111101000.00........00010000.... 201230592Sken/// 111101000.00........0001........ 202230592Sken/// 1111010...00........0001........ 203253549Sken/// 1111010...00.................... 204253549Sken/// 1111010......................... 205253549Sken/// 1111............................ 206230592Sken/// ................................ 207230592Sken/// VST4q8a 111101000_00________00010000____ 208253549Sken/// VST4q8b 111101000_00________00010000____ 209230592Sken/// 210253460Sscottl/// The Debug output shows the path that the decoding tree follows to reach the 211230592Sken/// the conclusion that there is a conflict. VST4q8a is a vst4 to double-spaced 212212420Sken/// even registers, while VST4q8b is a vst4 to double-spaced odd regsisters. 213230592Sken/// 214212420Sken/// The encoding info in the .td files does not specify this meta information, 215230592Sken/// which could have been used by the decoder to resolve the conflict. The 216230592Sken/// decoder could try to decode the even/odd register numbering and assign to 217230592Sken/// VST4q8a or VST4q8b, but for the time being, the decoder chooses the "a" 218230592Sken/// version and return the Opcode since the two have the same Asm format string. 219230592Skennamespace { 220230592Skenclass Filter { 221230592Skenprotected: 222230592Sken const FilterChooser *Owner;// points to the FilterChooser who owns this filter 223212420Sken unsigned StartBit; // the starting bit position 224253460Sscottl unsigned NumBits; // number of bits to filter 225230592Sken bool Mixed; // a mixed region contains both set and unset bits 226230592Sken 227230592Sken // Map of well-known segment value to the set of uid's with that value. 228253460Sscottl std::map<uint64_t, std::vector<unsigned> > FilteredInstructions; 229253460Sscottl 230230592Sken // Set of uid's with non-constant segment values. 231230592Sken std::vector<unsigned> VariableInstructions; 232253460Sscottl 233230592Sken // Map of well-known segment value to its delegate. 234230592Sken std::map<unsigned, const FilterChooser*> FilterChooserMap; 235230592Sken 236212420Sken // Number of instructions which fall under FilteredInstructions category. 237212420Sken unsigned NumFiltered; 238230592Sken 239230592Sken // Keeps track of the last opcode in the filtered bucket. 240212420Sken unsigned LastOpcFiltered; 241253460Sscottl 242230592Skenpublic: 243230592Sken unsigned getNumFiltered() const { return NumFiltered; } 244212420Sken unsigned getSingletonOpc() const { 245230592Sken assert(NumFiltered == 1); 246230592Sken return LastOpcFiltered; 247230592Sken } 248230592Sken // Return the filter chooser for the group of instructions without constant 249230592Sken // segment values. 250253460Sscottl const FilterChooser &getVariableFC() const { 251230592Sken assert(NumFiltered == 1); 252212420Sken assert(FilterChooserMap.size() == 1); 253253460Sscottl return *(FilterChooserMap.find((unsigned)-1)->second); 254230592Sken } 255212420Sken 256230592Sken Filter(const Filter &f); 257212420Sken Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, bool mixed); 258212420Sken 259230592Sken ~Filter(); 260230592Sken 261212420Sken // Divides the decoding task into sub tasks and delegates them to the 262230592Sken // inferior FilterChooser's. 263230592Sken // 264230592Sken // A special case arises when there's only one entry in the filtered 265230592Sken // instructions. In order to unambiguously decode the singleton, we need to 266212420Sken // match the remaining undecoded encoding bits against the singleton. 267253460Sscottl void recurse(); 268230592Sken 269230592Sken // Emit table entries to decode instructions given a segment or segments of 270230592Sken // bits. 271230592Sken void emitTableEntry(DecoderTableInfo &TableInfo) const; 272230592Sken 273212420Sken // Returns the number of fanout produced by the filter. More fanout implies 274230592Sken // the filter distinguishes more categories of instructions. 275230592Sken unsigned usefulness() const; 276230592Sken}; // End of class Filter 277230592Sken} // End anonymous namespace 278230592Sken 279253460Sscottl// These are states of our finite state machines used in FilterChooser's 280212420Sken// filterProcessor() which produces the filter candidates to use. 281212420Skentypedef enum { 282212420Sken ATTR_NONE, 283249468Smav ATTR_FILTERED, 284253550Sken ATTR_ALL_SET, 285253460Sscottl ATTR_ALL_UNSET, 286230592Sken ATTR_MIXED 287212420Sken} bitAttr_t; 288212420Sken 289230592Sken/// FilterChooser - FilterChooser chooses the best filter among a set of Filters 290237800Sken/// in order to perform the decoding of instructions at the current level. 291237800Sken/// 292237800Sken/// Decoding proceeds from the top down. Based on the well-known encoding bits 293237800Sken/// of instructions available, FilterChooser builds up the possible Filters that 294237800Sken/// can further the task of decoding by distinguishing among the remaining 295230592Sken/// candidate instructions. 296253549Sken/// 297212420Sken/// Once a filter has been chosen, it is called upon to divide the decoding task 298212420Sken/// into sub-tasks and delegates them to its inferior FilterChoosers for further 299212420Sken/// processings. 300253460Sscottl/// 301212420Sken/// It is useful to think of a Filter as governing the switch stmts of the 302230592Sken/// decoding tree. And each case is delegated to an inferior FilterChooser to 303230592Sken/// decide what further remaining bits to look at. 304230592Skennamespace { 305230592Skenclass FilterChooser { 306212420Skenprotected: 307230592Sken friend class Filter; 308230592Sken 309212420Sken // Vector of codegen instructions to choose our filter. 310254253Sscottl const std::vector<const CodeGenInstruction*> &AllInstructions; 311254257Smav 312254253Sscottl // Vector of uid's for this filter chooser to work on. 313254253Sscottl const std::vector<unsigned> &Opcodes; 314230592Sken 315212420Sken // Lookup table for the operand decoding of instructions. 316230592Sken const std::map<unsigned, std::vector<OperandInfo> > &Operands; 317212420Sken 318230592Sken // Vector of candidate filters. 319230592Sken std::vector<Filter> Filters; 320230592Sken 321230592Sken // Array of bit values passed down from our parent. 322230592Sken // Set to all BIT_UNFILTERED's for Parent == NULL. 323230592Sken std::vector<bit_value_t> FilterBitValues; 324230592Sken 325230592Sken // Links to the FilterChooser above us in the decoding tree. 326212420Sken const FilterChooser *Parent; 327212420Sken 328230592Sken // Index of the best filter from Filters. 329230592Sken int BestIndex; 330230592Sken 331230592Sken // Width of instructions 332230592Sken unsigned BitWidth; 333230592Sken 334230592Sken // Parent emitter 335230592Sken const FixedLenDecoderEmitter *Emitter; 336212420Sken 337230592Skenpublic: 338230592Sken FilterChooser(const FilterChooser &FC) 339230592Sken : AllInstructions(FC.AllInstructions), Opcodes(FC.Opcodes), 340253460Sscottl Operands(FC.Operands), Filters(FC.Filters), 341212420Sken FilterBitValues(FC.FilterBitValues), Parent(FC.Parent), 342230592Sken BestIndex(FC.BestIndex), BitWidth(FC.BitWidth), 343230592Sken Emitter(FC.Emitter) { } 344212420Sken 345231240Sken FilterChooser(const std::vector<const CodeGenInstruction*> &Insts, 346230592Sken const std::vector<unsigned> &IDs, 347231240Sken const std::map<unsigned, std::vector<OperandInfo> > &Ops, 348230592Sken unsigned BW, 349231240Sken const FixedLenDecoderEmitter *E) 350231240Sken : AllInstructions(Insts), Opcodes(IDs), Operands(Ops), Filters(), 351231240Sken Parent(NULL), BestIndex(-1), BitWidth(BW), Emitter(E) { 352212420Sken for (unsigned i = 0; i < BitWidth; ++i) 353253460Sscottl FilterBitValues.push_back(BIT_UNFILTERED); 354231240Sken 355231240Sken doFilter(); 356231240Sken } 357231240Sken 358231240Sken FilterChooser(const std::vector<const CodeGenInstruction*> &Insts, 359231240Sken const std::vector<unsigned> &IDs, 360231240Sken const std::map<unsigned, std::vector<OperandInfo> > &Ops, 361253460Sscottl const std::vector<bit_value_t> &ParentFilterBitValues, 362253460Sscottl const FilterChooser &parent) 363231240Sken : AllInstructions(Insts), Opcodes(IDs), Operands(Ops), 364230592Sken Filters(), FilterBitValues(ParentFilterBitValues), 365230592Sken Parent(&parent), BestIndex(-1), BitWidth(parent.BitWidth), 366212420Sken Emitter(parent.Emitter) { 367231240Sken doFilter(); 368253460Sscottl } 369253460Sscottl 370231240Sken unsigned getBitWidth() const { return BitWidth; } 371231240Sken 372231240Skenprotected: 373231240Sken // Populates the insn given the uid. 374231240Sken void insnWithID(insn_t &Insn, unsigned Opcode) const { 375253460Sscottl BitsInit &Bits = getBitsField(*AllInstructions[Opcode]->TheDef, "Inst"); 376253460Sscottl 377231240Sken // We may have a SoftFail bitmask, which specifies a mask where an encoding 378240518Seadler // may differ from the value in "Inst" and yet still be valid, but the 379231240Sken // disassembler should return SoftFail instead of Success. 380253460Sscottl // 381253460Sscottl // This is used for marking UNPREDICTABLE instructions in the ARM world. 382231240Sken BitsInit *SFBits = 383231240Sken AllInstructions[Opcode]->TheDef->getValueAsBitsInit("SoftFail"); 384231240Sken 385231240Sken for (unsigned i = 0; i < BitWidth; ++i) { 386231240Sken if (SFBits && bitFromBits(*SFBits, i) == BIT_TRUE) 387231240Sken Insn.push_back(BIT_UNSET); 388231240Sken else 389231240Sken Insn.push_back(bitFromBits(Bits, i)); 390231240Sken } 391231240Sken } 392231240Sken 393231240Sken // Returns the record name. 394231240Sken const std::string &nameWithID(unsigned Opcode) const { 395231240Sken return AllInstructions[Opcode]->TheDef->getName(); 396231240Sken } 397231240Sken 398231240Sken // Populates the field of the insn given the start position and the number of 399231240Sken // consecutive bits to scan for. 400231240Sken // 401231240Sken // Returns false if there exists any uninitialized bit value in the range. 402212420Sken // Returns true, otherwise. 403212420Sken bool fieldFromInsn(uint64_t &Field, insn_t &Insn, unsigned StartBit, 404231240Sken unsigned NumBits) const; 405212420Sken 406231240Sken /// dumpFilterArray - dumpFilterArray prints out debugging info for the given 407231240Sken /// filter array as a series of chars. 408231240Sken void dumpFilterArray(raw_ostream &o, 409231240Sken const std::vector<bit_value_t> & filter) const; 410231240Sken 411231240Sken /// dumpStack - dumpStack traverses the filter chooser chain and calls 412231240Sken /// dumpFilterArray on each filter chooser up to the top level one. 413231240Sken void dumpStack(raw_ostream &o, const char *prefix) const; 414231240Sken 415231240Sken Filter &bestFilter() { 416231240Sken assert(BestIndex != -1 && "BestIndex not set"); 417253460Sscottl return Filters[BestIndex]; 418231240Sken } 419231240Sken 420231240Sken // Called from Filter::recurse() when singleton exists. For debug purpose. 421231240Sken void SingletonExists(unsigned Opc) const; 422231240Sken 423231240Sken bool PositionFiltered(unsigned i) const { 424231240Sken return ValueSet(FilterBitValues[i]); 425231240Sken } 426231240Sken 427231240Sken // Calculates the island(s) needed to decode the instruction. 428231240Sken // This returns a lit of undecoded bits of an instructions, for example, 429231240Sken // Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be 430231240Sken // decoded bits in order to verify that the instruction matches the Opcode. 431231240Sken unsigned getIslands(std::vector<unsigned> &StartBits, 432231240Sken std::vector<unsigned> &EndBits, 433231240Sken std::vector<uint64_t> &FieldVals, 434231240Sken const insn_t &Insn) const; 435231240Sken 436253460Sscottl // Emits code to check the Predicates member of an instruction are true. 437253460Sscottl // Returns true if predicate matches were emitted, false otherwise. 438231240Sken bool emitPredicateMatch(raw_ostream &o, unsigned &Indentation, 439231240Sken unsigned Opc) const; 440231240Sken 441231240Sken bool doesOpcodeNeedPredicate(unsigned Opc) const; 442231240Sken unsigned getPredicateIndex(DecoderTableInfo &TableInfo, StringRef P) const; 443231240Sken void emitPredicateTableEntry(DecoderTableInfo &TableInfo, 444231240Sken unsigned Opc) const; 445253460Sscottl 446253460Sscottl void emitSoftFailTableEntry(DecoderTableInfo &TableInfo, 447231240Sken unsigned Opc) const; 448231240Sken 449231240Sken // Emits table entries to decode the singleton. 450231240Sken void emitSingletonTableEntry(DecoderTableInfo &TableInfo, 451231240Sken unsigned Opc) const; 452231240Sken 453231240Sken // Emits code to decode the singleton, and then to decode the rest. 454231240Sken void emitSingletonTableEntry(DecoderTableInfo &TableInfo, 455231240Sken const Filter &Best) const; 456231240Sken 457231240Sken void emitBinaryParser(raw_ostream &o, unsigned &Indentation, 458231240Sken const OperandInfo &OpInfo) const; 459231240Sken 460231240Sken void emitDecoder(raw_ostream &OS, unsigned Indentation, unsigned Opc) const; 461231240Sken unsigned getDecoderIndex(DecoderSet &Decoders, unsigned Opc) const; 462231240Sken 463231240Sken // Assign a single filter and run with it. 464231240Sken void runSingleFilter(unsigned startBit, unsigned numBit, bool mixed); 465231240Sken 466231240Sken // reportRegion is a helper function for filterProcessor to mark a region as 467231240Sken // eligible for use as a filter region. 468231240Sken void reportRegion(bitAttr_t RA, unsigned StartBit, unsigned BitIndex, 469231240Sken bool AllowMixed); 470230592Sken 471230592Sken // FilterProcessor scans the well-known encoding bits of the instructions and 472230592Sken // builds up a list of candidate filters. It chooses the best filter and 473230592Sken // recursively descends down the decoding tree. 474230592Sken bool filterProcessor(bool AllowMixed, bool Greedy = true); 475230592Sken 476230592Sken // Decides on the best configuration of filter(s) to use in order to decode 477212420Sken // the instructions. A conflict of instructions may occur, in which case we 478230592Sken // dump the conflict set to the standard error. 479230592Sken void doFilter(); 480212420Sken 481212420Skenpublic: 482212420Sken // emitTableEntries - Emit state machine entries to decode our share of 483212420Sken // instructions. 484212420Sken void emitTableEntries(DecoderTableInfo &TableInfo) const; 485212420Sken}; 486253460Sscottl} // End anonymous namespace 487212420Sken 488230592Sken/////////////////////////// 489230592Sken// // 490230592Sken// Filter Implementation // 491230592Sken// // 492230592Sken/////////////////////////// 493212420Sken 494253460SscottlFilter::Filter(const Filter &f) 495253460Sscottl : Owner(f.Owner), StartBit(f.StartBit), NumBits(f.NumBits), Mixed(f.Mixed), 496212420Sken FilteredInstructions(f.FilteredInstructions), 497230592Sken VariableInstructions(f.VariableInstructions), 498212420Sken FilterChooserMap(f.FilterChooserMap), NumFiltered(f.NumFiltered), 499230592Sken LastOpcFiltered(f.LastOpcFiltered) { 500230592Sken} 501230592Sken 502212420SkenFilter::Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, 503253460Sscottl bool mixed) 504253460Sscottl : Owner(&owner), StartBit(startBit), NumBits(numBits), Mixed(mixed) { 505212420Sken assert(StartBit + NumBits - 1 < Owner->BitWidth); 506212420Sken 507212420Sken NumFiltered = 0; 508231240Sken LastOpcFiltered = 0; 509218811Sken 510212420Sken for (unsigned i = 0, e = Owner->Opcodes.size(); i != e; ++i) { 511218811Sken insn_t Insn; 512237683Sken 513212420Sken // Populates the insn given the uid. 514212420Sken Owner->insnWithID(Insn, Owner->Opcodes[i]); 515212420Sken 516212420Sken uint64_t Field; 517212420Sken // Scans the segment for possibly well-specified encoding bits. 518212420Sken bool ok = Owner->fieldFromInsn(Field, Insn, StartBit, NumBits); 519230592Sken 520212420Sken if (ok) { 521230592Sken // The encoding bits are well-known. Lets add the uid of the 522212420Sken // instruction into the bucket keyed off the constant field value. 523230592Sken LastOpcFiltered = Owner->Opcodes[i]; 524230592Sken FilteredInstructions[Field].push_back(LastOpcFiltered); 525212420Sken ++NumFiltered; 526212420Sken } else { 527212420Sken // Some of the encoding bit(s) are unspecified. This contributes to 528230592Sken // one additional member of "Variable" instructions. 529212420Sken VariableInstructions.push_back(Owner->Opcodes[i]); 530212420Sken } 531212420Sken } 532212420Sken 533218811Sken assert((FilteredInstructions.size() + VariableInstructions.size() > 0) 534212420Sken && "Filter returns no instruction categories"); 535212420Sken} 536253460Sscottl 537212420SkenFilter::~Filter() { 538230592Sken std::map<unsigned, const FilterChooser*>::iterator filterIterator; 539230592Sken for (filterIterator = FilterChooserMap.begin(); 540230592Sken filterIterator != FilterChooserMap.end(); 541213535Sken filterIterator++) { 542218812Sken delete filterIterator->second; 543218812Sken } 544218812Sken} 545218812Sken 546218812Sken// Divides the decoding task into sub tasks and delegates them to the 547230592Sken// inferior FilterChooser's. 548253460Sscottl// 549253460Sscottl// A special case arises when there's only one entry in the filtered 550253460Sscottl// instructions. In order to unambiguously decode the singleton, we need to 551253460Sscottl// match the remaining undecoded encoding bits against the singleton. 552230592Skenvoid Filter::recurse() { 553218812Sken std::map<uint64_t, std::vector<unsigned> >::const_iterator mapIterator; 554218812Sken 555218812Sken // Starts by inheriting our parent filter chooser's filter bit values. 556230592Sken std::vector<bit_value_t> BitValueArray(Owner->FilterBitValues); 557230592Sken 558253460Sscottl if (VariableInstructions.size()) { 559253460Sscottl // Conservatively marks each segment position as BIT_UNSET. 560230592Sken for (unsigned bitIndex = 0; bitIndex < NumBits; ++bitIndex) 561230592Sken BitValueArray[StartBit + bitIndex] = BIT_UNSET; 562230592Sken 563230592Sken // Delegates to an inferior filter chooser for further processing on this 564237683Sken // group of instructions whose segment values are variable. 565253460Sscottl FilterChooserMap.insert(std::pair<unsigned, const FilterChooser*>( 566253460Sscottl (unsigned)-1, 567237683Sken new FilterChooser(Owner->AllInstructions, 568230592Sken VariableInstructions, 569212420Sken Owner->Operands, 570212420Sken BitValueArray, 571212420Sken *Owner) 572253460Sscottl )); 573237683Sken } 574230592Sken 575240518Seadler // No need to recurse for a singleton filtered instruction. 576212420Sken // See also Filter::emit*(). 577212420Sken if (getNumFiltered() == 1) { 578230592Sken //Owner->SingletonExists(LastOpcFiltered); 579218811Sken assert(FilterChooserMap.size() == 1); 580212420Sken return; 581212420Sken } 582237683Sken 583230592Sken // Otherwise, create sub choosers. 584230592Sken for (mapIterator = FilteredInstructions.begin(); 585230592Sken mapIterator != FilteredInstructions.end(); 586230592Sken mapIterator++) { 587212420Sken 588230592Sken // Marks all the segment positions with either BIT_TRUE or BIT_FALSE. 589212420Sken for (unsigned bitIndex = 0; bitIndex < NumBits; ++bitIndex) { 590253460Sscottl if (mapIterator->first & (1ULL << bitIndex)) 591230592Sken BitValueArray[StartBit + bitIndex] = BIT_TRUE; 592230592Sken else 593218811Sken BitValueArray[StartBit + bitIndex] = BIT_FALSE; 594218811Sken } 595253460Sscottl 596230592Sken // Delegates to an inferior filter chooser for further processing on this 597218811Sken // category of instructions. 598230592Sken FilterChooserMap.insert(std::pair<unsigned, const FilterChooser*>( 599218811Sken mapIterator->first, 600212420Sken new FilterChooser(Owner->AllInstructions, 601212420Sken mapIterator->second, 602212420Sken Owner->Operands, 603230592Sken BitValueArray, 604212420Sken *Owner) 605212420Sken )); 606230592Sken } 607230592Sken} 608237683Sken 609212420Skenstatic void resolveTableFixups(DecoderTable &Table, const FixupList &Fixups, 610253460Sscottl uint32_t DestIdx) { 611212420Sken // Any NumToSkip fixups in the current scope can resolve to the 612230592Sken // current location. 613230592Sken for (FixupList::const_reverse_iterator I = Fixups.rbegin(), 614212420Sken E = Fixups.rend(); 615230592Sken I != E; ++I) { 616230592Sken // Calculate the distance from the byte following the fixup entry byte 617230592Sken // to the destination. The Target is calculated from after the 16-bit 618230592Sken // NumToSkip entry itself, so subtract two from the displacement here 619230592Sken // to account for that. 620230592Sken uint32_t FixupIdx = *I; 621253460Sscottl uint32_t Delta = DestIdx - FixupIdx - 2; 622253460Sscottl // Our NumToSkip entries are 16-bits. Make sure our table isn't too 623230592Sken // big. 624230592Sken assert(Delta < 65536U && "disassembler decoding table too large!"); 625230592Sken Table[FixupIdx] = (uint8_t)Delta; 626230592Sken Table[FixupIdx + 1] = (uint8_t)(Delta >> 8); 627230592Sken } 628212420Sken} 629230592Sken 630230592Sken// Emit table entries to decode instructions given a segment or segments 631253460Sscottl// of bits. 632253460Sscottlvoid Filter::emitTableEntry(DecoderTableInfo &TableInfo) const { 633230592Sken TableInfo.Table.push_back(MCD::OPC_ExtractField); 634230592Sken TableInfo.Table.push_back(StartBit); 635212420Sken TableInfo.Table.push_back(NumBits); 636212420Sken 637253460Sscottl // A new filter entry begins a new scope for fixup resolution. 638253460Sscottl TableInfo.FixupStack.push_back(FixupList()); 639237683Sken 640212420Sken std::map<unsigned, const FilterChooser*>::const_iterator filterIterator; 641230592Sken 642230592Sken DecoderTable &Table = TableInfo.Table; 643230592Sken 644230592Sken size_t PrevFilter = 0; 645230592Sken bool HasFallthrough = false; 646230592Sken for (filterIterator = FilterChooserMap.begin(); 647237683Sken filterIterator != FilterChooserMap.end(); 648230592Sken filterIterator++) { 649230592Sken // Field value -1 implies a non-empty set of variable instructions. 650230592Sken // See also recurse(). 651230592Sken if (filterIterator->first == (unsigned)-1) { 652230592Sken HasFallthrough = true; 653230592Sken 654230592Sken // Each scope should always have at least one filter value to check 655230592Sken // for. 656231240Sken assert(PrevFilter != 0 && "empty filter set!"); 657237683Sken FixupList &CurScope = TableInfo.FixupStack.back(); 658237683Sken // Resolve any NumToSkip fixups in the current scope. 659237683Sken resolveTableFixups(Table, CurScope, Table.size()); 660237683Sken CurScope.clear(); 661237683Sken PrevFilter = 0; // Don't re-process the filter's fallthrough. 662237683Sken } else { 663212420Sken Table.push_back(MCD::OPC_FilterValue); 664237683Sken // Encode and emit the value to filter against. 665212420Sken uint8_t Buffer[8]; 666230592Sken unsigned Len = encodeULEB128(filterIterator->first, Buffer); 667212420Sken Table.insert(Table.end(), Buffer, Buffer + Len); 668212420Sken // Reserve space for the NumToSkip entry. We'll backpatch the value 669212420Sken // later. 670212420Sken PrevFilter = Table.size(); 671212420Sken Table.push_back(0); 672237683Sken Table.push_back(0); 673212420Sken } 674212420Sken 675212420Sken // We arrive at a category of instructions with the same segment value. 676212420Sken // Now delegate to the sub filter chooser for further decodings. 677212420Sken // The case may fallthrough, which happens if the remaining well-known 678212420Sken // encoding bits do not match exactly. 679212420Sken filterIterator->second->emitTableEntries(TableInfo); 680212420Sken 681212420Sken // Now that we've emitted the body of the handler, update the NumToSkip 682230592Sken // of the filter itself to be able to skip forward when false. Subtract 683230592Sken // two as to account for the width of the NumToSkip field itself. 684230592Sken if (PrevFilter) { 685230592Sken uint32_t NumToSkip = Table.size() - PrevFilter - 2; 686230592Sken assert(NumToSkip < 65536U && "disassembler decoding table too large!"); 687212420Sken Table[PrevFilter] = (uint8_t)NumToSkip; 688212420Sken Table[PrevFilter + 1] = (uint8_t)(NumToSkip >> 8); 689212420Sken } 690212420Sken } 691212420Sken 692212420Sken // Any remaining unresolved fixups bubble up to the parent fixup scope. 693212420Sken assert(TableInfo.FixupStack.size() > 1 && "fixup stack underflow!"); 694212420Sken FixupScopeList::iterator Source = TableInfo.FixupStack.end() - 1; 695212420Sken FixupScopeList::iterator Dest = Source - 1; 696212420Sken Dest->insert(Dest->end(), Source->begin(), Source->end()); 697212420Sken TableInfo.FixupStack.pop_back(); 698230592Sken 699230592Sken // If there is no fallthrough, then the final filter should get fixed 700212420Sken // up according to the enclosing scope rather than the current position. 701253460Sscottl if (!HasFallthrough) 702212420Sken TableInfo.FixupStack.back().push_back(PrevFilter); 703212420Sken} 704237683Sken 705237683Sken// Returns the number of fanout produced by the filter. More fanout implies 706237683Sken// the filter distinguishes more categories of instructions. 707237683Skenunsigned Filter::usefulness() const { 708237683Sken if (VariableInstructions.size()) 709212420Sken return FilteredInstructions.size(); 710212420Sken else 711237683Sken return FilteredInstructions.size() + 1; 712237683Sken} 713237683Sken 714237683Sken////////////////////////////////// 715237683Sken// // 716237683Sken// Filterchooser Implementation // 717212420Sken// // 718212420Sken////////////////////////////////// 719212420Sken 720230592Sken// Emit the decoder state machine table. 721253460Sscottlvoid FixedLenDecoderEmitter::emitTable(formatted_raw_ostream &OS, 722212420Sken DecoderTable &Table, 723212420Sken unsigned Indentation, 724212420Sken unsigned BitWidth, 725212420Sken StringRef Namespace) const { 726230592Sken OS.indent(Indentation) << "static const uint8_t DecoderTable" << Namespace 727212420Sken << BitWidth << "[] = {\n"; 728230592Sken 729212420Sken Indentation += 2; 730253460Sscottl 731212420Sken // FIXME: We may be able to use the NumToSkip values to recover 732212420Sken // appropriate indentation levels. 733212420Sken DecoderTable::const_iterator I = Table.begin(); 734212420Sken DecoderTable::const_iterator E = Table.end(); 735230592Sken while (I != E) { 736230592Sken assert (I < E && "incomplete decode table entry!"); 737230592Sken 738230592Sken uint64_t Pos = I - Table.begin(); 739230592Sken OS << "/* " << Pos << " */"; 740230592Sken OS.PadToColumn(12); 741230592Sken 742230592Sken switch (*I) { 743230592Sken default: 744230592Sken PrintFatalError("invalid decode table opcode"); 745230592Sken case MCD::OPC_ExtractField: { 746230592Sken ++I; 747230592Sken unsigned Start = *I++; 748212420Sken unsigned Len = *I++; 749212420Sken OS.indent(Indentation) << "MCD::OPC_ExtractField, " << Start << ", " 750212420Sken << Len << ", // Inst{"; 751212420Sken if (Len > 1) 752212420Sken OS << (Start + Len - 1) << "-"; 753212420Sken OS << Start << "} ...\n"; 754253460Sscottl break; 755212420Sken } 756212420Sken case MCD::OPC_FilterValue: { 757212420Sken ++I; 758212420Sken OS.indent(Indentation) << "MCD::OPC_FilterValue, "; 759212420Sken // The filter value is ULEB128 encoded. 760212420Sken while (*I >= 128) 761253549Sken OS << utostr(*I++) << ", "; 762253549Sken OS << utostr(*I++) << ", "; 763253549Sken 764212420Sken // 16-bit numtoskip value. 765230592Sken uint8_t Byte = *I++; 766253549Sken uint32_t NumToSkip = Byte; 767253549Sken OS << utostr(Byte) << ", "; 768253549Sken Byte = *I++; 769212420Sken OS << utostr(Byte) << ", "; 770253549Sken NumToSkip |= Byte << 8; 771230592Sken OS << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; 772212420Sken break; 773212420Sken } 774212420Sken case MCD::OPC_CheckField: { 775212420Sken ++I; 776230592Sken unsigned Start = *I++; 777230592Sken unsigned Len = *I++; 778253549Sken OS.indent(Indentation) << "MCD::OPC_CheckField, " << Start << ", " 779253549Sken << Len << ", ";// << Val << ", " << NumToSkip << ",\n"; 780253549Sken // ULEB128 encoded field value. 781253549Sken for (; *I >= 128; ++I) 782253549Sken OS << utostr(*I) << ", "; 783253549Sken OS << utostr(*I++) << ", "; 784253549Sken // 16-bit numtoskip value. 785230592Sken uint8_t Byte = *I++; 786253549Sken uint32_t NumToSkip = Byte; 787253549Sken OS << utostr(Byte) << ", "; 788253549Sken Byte = *I++; 789253549Sken OS << utostr(Byte) << ", "; 790253549Sken NumToSkip |= Byte << 8; 791253549Sken OS << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; 792253549Sken break; 793253549Sken } 794253549Sken case MCD::OPC_CheckPredicate: { 795253549Sken ++I; 796253549Sken OS.indent(Indentation) << "MCD::OPC_CheckPredicate, "; 797253549Sken for (; *I >= 128; ++I) 798253549Sken OS << utostr(*I) << ", "; 799253549Sken OS << utostr(*I++) << ", "; 800253549Sken 801253549Sken // 16-bit numtoskip value. 802253549Sken uint8_t Byte = *I++; 803253549Sken uint32_t NumToSkip = Byte; 804253549Sken OS << utostr(Byte) << ", "; 805253549Sken Byte = *I++; 806230592Sken OS << utostr(Byte) << ", "; 807253549Sken NumToSkip |= Byte << 8; 808253549Sken OS << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; 809253549Sken break; 810253549Sken } 811253549Sken case MCD::OPC_Decode: { 812253549Sken ++I; 813253549Sken // Extract the ULEB128 encoded Opcode to a buffer. 814230592Sken uint8_t Buffer[8], *p = Buffer; 815230592Sken while ((*p++ = *I++) >= 128) 816230592Sken assert((p - Buffer) <= (ptrdiff_t)sizeof(Buffer) 817212420Sken && "ULEB128 value too large!"); 818212420Sken // Decode the Opcode value. 819212420Sken unsigned Opc = decodeULEB128(Buffer); 820212420Sken OS.indent(Indentation) << "MCD::OPC_Decode, "; 821212420Sken for (p = Buffer; *p >= 128; ++p) 822212420Sken OS << utostr(*p) << ", "; 823212420Sken OS << utostr(*p) << ", "; 824212420Sken 825212420Sken // Decoder index. 826212420Sken for (; *I >= 128; ++I) 827212420Sken OS << utostr(*I) << ", "; 828237683Sken OS << utostr(*I++) << ", "; 829237683Sken 830237683Sken OS << "// Opcode: " 831212420Sken << NumberedInstructions->at(Opc)->TheDef->getName() << "\n"; 832253460Sscottl break; 833212420Sken } 834212420Sken case MCD::OPC_SoftFail: { 835212420Sken ++I; 836212420Sken OS.indent(Indentation) << "MCD::OPC_SoftFail"; 837212420Sken // Positive mask 838230592Sken uint64_t Value = 0; 839212420Sken unsigned Shift = 0; 840230592Sken do { 841230592Sken OS << ", " << utostr(*I); 842230592Sken Value += (*I & 0x7f) << Shift; 843230592Sken Shift += 7; 844230592Sken } while (*I++ >= 128); 845230592Sken if (Value > 127) 846230592Sken OS << " /* 0x" << utohexstr(Value) << " */"; 847230592Sken // Negative mask 848212420Sken Value = 0; 849212420Sken Shift = 0; 850230592Sken do { 851230592Sken OS << ", " << utostr(*I); 852253549Sken Value += (*I & 0x7f) << Shift; 853253549Sken Shift += 7; 854253549Sken } while (*I++ >= 128); 855253549Sken if (Value > 127) 856253549Sken OS << " /* 0x" << utohexstr(Value) << " */"; 857230592Sken OS << ",\n"; 858212420Sken break; 859212420Sken } 860212420Sken case MCD::OPC_Fail: { 861212420Sken ++I; 862212420Sken OS.indent(Indentation) << "MCD::OPC_Fail,\n"; 863212420Sken break; 864212420Sken } 865230592Sken } 866253549Sken } 867212420Sken OS.indent(Indentation) << "0\n"; 868212420Sken 869212420Sken Indentation -= 2; 870212420Sken 871212420Sken OS.indent(Indentation) << "};\n\n"; 872237683Sken} 873237683Sken 874237683Skenvoid FixedLenDecoderEmitter:: 875237683SkenemitPredicateFunction(formatted_raw_ostream &OS, PredicateSet &Predicates, 876237683Sken unsigned Indentation) const { 877237683Sken // The predicate function is just a big switch statement based on the 878212420Sken // input predicate index. 879212420Sken OS.indent(Indentation) << "static bool checkDecoderPredicate(unsigned Idx, " 880212420Sken << "uint64_t Bits) {\n"; 881212420Sken Indentation += 2; 882212420Sken if (!Predicates.empty()) { 883212420Sken OS.indent(Indentation) << "switch (Idx) {\n"; 884212420Sken OS.indent(Indentation) << "default: llvm_unreachable(\"Invalid index!\");\n"; 885230592Sken unsigned Index = 0; 886212420Sken for (PredicateSet::const_iterator I = Predicates.begin(), E = Predicates.end(); 887212420Sken I != E; ++I, ++Index) { 888212420Sken OS.indent(Indentation) << "case " << Index << ":\n"; 889212420Sken OS.indent(Indentation+2) << "return (" << *I << ");\n"; 890253460Sscottl } 891212420Sken OS.indent(Indentation) << "}\n"; 892212420Sken } else { 893212420Sken // No case statement to emit 894212420Sken OS.indent(Indentation) << "llvm_unreachable(\"Invalid index!\");\n"; 895212420Sken } 896212420Sken Indentation -= 2; 897212420Sken OS.indent(Indentation) << "}\n\n"; 898230592Sken} 899212420Sken 900230592Skenvoid FixedLenDecoderEmitter:: 901230592SkenemitDecoderFunction(formatted_raw_ostream &OS, DecoderSet &Decoders, 902212420Sken unsigned Indentation) const { 903230592Sken // The decoder function is just a big switch statement based on the 904253460Sscottl // input decoder index. 905212420Sken OS.indent(Indentation) << "template<typename InsnType>\n"; 906230592Sken OS.indent(Indentation) << "static DecodeStatus decodeToMCInst(DecodeStatus S," 907253460Sscottl << " unsigned Idx, InsnType insn, MCInst &MI,\n"; 908230592Sken OS.indent(Indentation) << " uint64_t " 909230592Sken << "Address, const void *Decoder) {\n"; 910212420Sken Indentation += 2; 911230592Sken OS.indent(Indentation) << "InsnType tmp;\n"; 912230592Sken OS.indent(Indentation) << "switch (Idx) {\n"; 913212420Sken OS.indent(Indentation) << "default: llvm_unreachable(\"Invalid index!\");\n"; 914253460Sscottl unsigned Index = 0; 915230592Sken for (DecoderSet::const_iterator I = Decoders.begin(), E = Decoders.end(); 916230592Sken I != E; ++I, ++Index) { 917212420Sken OS.indent(Indentation) << "case " << Index << ":\n"; 918212420Sken OS << *I; 919212420Sken OS.indent(Indentation+2) << "return S;\n"; 920212420Sken } 921212420Sken OS.indent(Indentation) << "}\n"; 922212420Sken Indentation -= 2; 923212420Sken OS.indent(Indentation) << "}\n\n"; 924212420Sken} 925212420Sken 926212420Sken// Populates the field of the insn given the start position and the number of 927212420Sken// consecutive bits to scan for. 928212420Sken// 929212420Sken// Returns false if and on the first uninitialized bit value encountered. 930212420Sken// Returns true, otherwise. 931212420Skenbool FilterChooser::fieldFromInsn(uint64_t &Field, insn_t &Insn, 932212420Sken unsigned StartBit, unsigned NumBits) const { 933212420Sken Field = 0; 934212420Sken 935212420Sken for (unsigned i = 0; i < NumBits; ++i) { 936212420Sken if (Insn[StartBit + i] == BIT_UNSET) 937212420Sken return false; 938212420Sken 939212420Sken if (Insn[StartBit + i] == BIT_TRUE) 940212420Sken Field = Field | (1ULL << i); 941212420Sken } 942212420Sken 943212420Sken return true; 944253460Sscottl} 945253460Sscottl 946212420Sken/// dumpFilterArray - dumpFilterArray prints out debugging info for the given 947230592Sken/// filter array as a series of chars. 948212420Skenvoid FilterChooser::dumpFilterArray(raw_ostream &o, 949212420Sken const std::vector<bit_value_t> &filter) const { 950212420Sken for (unsigned bitIndex = BitWidth; bitIndex > 0; bitIndex--) { 951212420Sken switch (filter[bitIndex - 1]) { 952212420Sken case BIT_UNFILTERED: 953212420Sken o << "."; 954212420Sken break; 955212420Sken case BIT_UNSET: 956212420Sken o << "_"; 957253549Sken break; 958253549Sken case BIT_TRUE: 959253549Sken o << "1"; 960248825Smav break; 961253549Sken case BIT_FALSE: 962212420Sken o << "0"; 963212420Sken break; 964237683Sken } 965241759Sjwd } 966212420Sken} 967212420Sken 968212420Sken/// dumpStack - dumpStack traverses the filter chooser chain and calls 969212420Sken/// dumpFilterArray on each filter chooser up to the top level one. 970212420Skenvoid FilterChooser::dumpStack(raw_ostream &o, const char *prefix) const { 971212420Sken const FilterChooser *current = this; 972212420Sken 973212420Sken while (current) { 974212420Sken o << prefix; 975212420Sken dumpFilterArray(o, current->FilterBitValues); 976230592Sken o << '\n'; 977230592Sken current = current->Parent; 978230592Sken } 979230592Sken} 980230592Sken 981230592Sken// Called from Filter::recurse() when singleton exists. For debug purpose. 982212420Skenvoid FilterChooser::SingletonExists(unsigned Opc) const { 983212420Sken insn_t Insn0; 984212420Sken insnWithID(Insn0, Opc); 985212420Sken 986212420Sken errs() << "Singleton exists: " << nameWithID(Opc) 987212420Sken << " with its decoding dominating "; 988212420Sken for (unsigned i = 0; i < Opcodes.size(); ++i) { 989212420Sken if (Opcodes[i] == Opc) continue; 990212420Sken errs() << nameWithID(Opcodes[i]) << ' '; 991212420Sken } 992212420Sken errs() << '\n'; 993212420Sken 994212420Sken dumpStack(errs(), "\t\t"); 995212420Sken for (unsigned i = 0; i < Opcodes.size(); ++i) { 996212420Sken const std::string &Name = nameWithID(Opcodes[i]); 997212420Sken 998237683Sken errs() << '\t' << Name << " "; 999212420Sken dumpBits(errs(), 1000212420Sken getBitsField(*AllInstructions[Opcodes[i]]->TheDef, "Inst")); 1001212420Sken errs() << '\n'; 1002212420Sken } 1003212420Sken} 1004212420Sken 1005212420Sken// Calculates the island(s) needed to decode the instruction. 1006212420Sken// This returns a list of undecoded bits of an instructions, for example, 1007212420Sken// Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be 1008212420Sken// decoded bits in order to verify that the instruction matches the Opcode. 1009212420Skenunsigned FilterChooser::getIslands(std::vector<unsigned> &StartBits, 1010212420Sken std::vector<unsigned> &EndBits, 1011212420Sken std::vector<uint64_t> &FieldVals, 1012212420Sken const insn_t &Insn) const { 1013212420Sken unsigned Num, BitNo; 1014212420Sken Num = BitNo = 0; 1015212420Sken 1016212420Sken uint64_t FieldVal = 0; 1017212420Sken 1018212420Sken // 0: Init 1019212420Sken // 1: Water (the bit value does not affect decoding) 1020212420Sken // 2: Island (well-known bit value needed for decoding) 1021212420Sken int State = 0; 1022212420Sken int Val = -1; 1023212420Sken 1024212420Sken for (unsigned i = 0; i < BitWidth; ++i) { 1025212420Sken Val = Value(Insn[i]); 1026212420Sken bool Filtered = PositionFiltered(i); 1027212420Sken switch (State) { 1028212420Sken default: llvm_unreachable("Unreachable code!"); 1029212420Sken case 0: 1030212420Sken case 1: 1031212420Sken if (Filtered || Val == -1) 1032212420Sken State = 1; // Still in Water 1033253460Sscottl else { 1034212420Sken State = 2; // Into the Island 1035212420Sken BitNo = 0; 1036212420Sken StartBits.push_back(i); 1037212420Sken FieldVal = Val; 1038212420Sken } 1039253460Sscottl break; 1040253460Sscottl case 2: 1041212420Sken if (Filtered || Val == -1) { 1042212420Sken State = 1; // Into the Water 1043212420Sken EndBits.push_back(i - 1); 1044212420Sken FieldVals.push_back(FieldVal); 1045212420Sken ++Num; 1046216088Sken } else { 1047216088Sken State = 2; // Still in Island 1048216088Sken ++BitNo; 1049216088Sken FieldVal = FieldVal | Val << BitNo; 1050230592Sken } 1051212420Sken break; 1052212420Sken } 1053212420Sken } 1054212420Sken // If we are still in Island after the loop, do some housekeeping. 1055212420Sken if (State == 2) { 1056212420Sken EndBits.push_back(BitWidth - 1); 1057212420Sken FieldVals.push_back(FieldVal); 1058212420Sken ++Num; 1059212420Sken } 1060230592Sken 1061230592Sken assert(StartBits.size() == Num && EndBits.size() == Num && 1062212420Sken FieldVals.size() == Num); 1063230592Sken return Num; 1064230592Sken} 1065212420Sken 1066253460Sscottlvoid FilterChooser::emitBinaryParser(raw_ostream &o, unsigned &Indentation, 1067230592Sken const OperandInfo &OpInfo) const { 1068212420Sken const std::string &Decoder = OpInfo.Decoder; 1069230592Sken 1070230592Sken if (OpInfo.numFields() == 1) { 1071253460Sscottl OperandInfo::const_iterator OI = OpInfo.begin(); 1072230592Sken o.indent(Indentation) << "tmp = fieldFromInstruction" 1073230592Sken << "(insn, " << OI->Base << ", " << OI->Width 1074212420Sken << ");\n"; 1075212420Sken } else { 1076230592Sken o.indent(Indentation) << "tmp = 0;\n"; 1077230592Sken for (OperandInfo::const_iterator OI = OpInfo.begin(), OE = OpInfo.end(); 1078212420Sken OI != OE; ++OI) { 1079212420Sken o.indent(Indentation) << "tmp |= (fieldFromInstruction" 1080230592Sken << "(insn, " << OI->Base << ", " << OI->Width 1081230592Sken << ") << " << OI->Offset << ");\n"; 1082212420Sken } 1083212420Sken } 1084230592Sken 1085230592Sken if (Decoder != "") 1086212420Sken o.indent(Indentation) << Emitter->GuardPrefix << Decoder 1087253460Sscottl << "(MI, tmp, Address, Decoder)" 1088230592Sken << Emitter->GuardPostfix << "\n"; 1089212420Sken else 1090230592Sken o.indent(Indentation) << "MI.addOperand(MCOperand::CreateImm(tmp));\n"; 1091230592Sken 1092230592Sken} 1093230592Sken 1094230592Skenvoid FilterChooser::emitDecoder(raw_ostream &OS, unsigned Indentation, 1095230592Sken unsigned Opc) const { 1096230592Sken std::map<unsigned, std::vector<OperandInfo> >::const_iterator OpIter = 1097230592Sken Operands.find(Opc); 1098230592Sken const std::vector<OperandInfo>& InsnOperands = OpIter->second; 1099230592Sken for (std::vector<OperandInfo>::const_iterator 1100253460Sscottl I = InsnOperands.begin(), E = InsnOperands.end(); I != E; ++I) { 1101230592Sken // If a custom instruction decoder was specified, use that. 1102230592Sken if (I->numFields() == 0 && I->Decoder.size()) { 1103230592Sken OS.indent(Indentation) << Emitter->GuardPrefix << I->Decoder 1104230592Sken << "(MI, insn, Address, Decoder)" 1105230592Sken << Emitter->GuardPostfix << "\n"; 1106230592Sken break; 1107230592Sken } 1108230592Sken 1109253460Sscottl emitBinaryParser(OS, Indentation, *I); 1110230592Sken } 1111230592Sken} 1112230592Sken 1113230592Skenunsigned FilterChooser::getDecoderIndex(DecoderSet &Decoders, 1114230592Sken unsigned Opc) const { 1115230592Sken // Build up the predicate string. 1116230592Sken SmallString<256> Decoder; 1117230592Sken // FIXME: emitDecoder() function can take a buffer directly rather than 1118253460Sscottl // a stream. 1119230592Sken raw_svector_ostream S(Decoder); 1120230592Sken unsigned I = 4; 1121230592Sken emitDecoder(S, I, Opc); 1122230592Sken S.flush(); 1123212420Sken 1124230592Sken // Using the full decoder string as the key value here is a bit 1125212420Sken // heavyweight, but is effective. If the string comparisons become a 1126230592Sken // performance concern, we can implement a mangling of the predicate 1127230592Sken // data easilly enough with a map back to the actual string. That's 1128230592Sken // overkill for now, though. 1129230592Sken 1130212420Sken // Make sure the predicate is in the table. 1131230592Sken Decoders.insert(Decoder.str()); 1132230592Sken // Now figure out the index for when we write out the table. 1133230592Sken DecoderSet::const_iterator P = std::find(Decoders.begin(), 1134230592Sken Decoders.end(), 1135230592Sken Decoder.str()); 1136230592Sken return (unsigned)(P - Decoders.begin()); 1137230592Sken} 1138212802Sken 1139253460Sscottlstatic void emitSinglePredicateMatch(raw_ostream &o, StringRef str, 1140230592Sken const std::string &PredicateNamespace) { 1141230592Sken if (str[0] == '!') 1142230592Sken o << "!(Bits & " << PredicateNamespace << "::" 1143212420Sken << str.slice(1,str.size()) << ")"; 1144230592Sken else 1145230592Sken o << "(Bits & " << PredicateNamespace << "::" << str << ")"; 1146230592Sken} 1147212420Sken 1148230592Skenbool FilterChooser::emitPredicateMatch(raw_ostream &o, unsigned &Indentation, 1149230592Sken unsigned Opc) const { 1150230592Sken ListInit *Predicates = 1151253460Sscottl AllInstructions[Opc]->TheDef->getValueAsListInit("Predicates"); 1152253460Sscottl for (unsigned i = 0; i < Predicates->getSize(); ++i) { 1153230592Sken Record *Pred = Predicates->getElementAsRecord(i); 1154230592Sken if (!Pred->getValue("AssemblerMatcherPredicate")) 1155212420Sken continue; 1156230592Sken 1157230592Sken std::string P = Pred->getValueAsString("AssemblerCondString"); 1158212420Sken 1159230592Sken if (!P.length()) 1160230592Sken continue; 1161230592Sken 1162230592Sken if (i != 0) 1163230592Sken o << " && "; 1164230592Sken 1165230592Sken StringRef SR(P); 1166230592Sken std::pair<StringRef, StringRef> pairs = SR.split(','); 1167253460Sscottl while (pairs.second.size()) { 1168230592Sken emitSinglePredicateMatch(o, pairs.first, Emitter->PredicateNamespace); 1169230592Sken o << " && "; 1170230592Sken pairs = pairs.second.split(','); 1171230592Sken } 1172230592Sken emitSinglePredicateMatch(o, pairs.first, Emitter->PredicateNamespace); 1173230592Sken } 1174212420Sken return Predicates->getSize() > 0; 1175253460Sscottl} 1176230592Sken 1177230592Skenbool FilterChooser::doesOpcodeNeedPredicate(unsigned Opc) const { 1178230592Sken ListInit *Predicates = 1179230592Sken AllInstructions[Opc]->TheDef->getValueAsListInit("Predicates"); 1180230592Sken for (unsigned i = 0; i < Predicates->getSize(); ++i) { 1181212420Sken Record *Pred = Predicates->getElementAsRecord(i); 1182230592Sken if (!Pred->getValue("AssemblerMatcherPredicate")) 1183230592Sken continue; 1184253460Sscottl 1185253460Sscottl std::string P = Pred->getValueAsString("AssemblerCondString"); 1186230592Sken 1187230592Sken if (!P.length()) 1188230592Sken continue; 1189212420Sken 1190230592Sken return true; 1191212420Sken } 1192230592Sken return false; 1193212420Sken} 1194230592Sken 1195230592Skenunsigned FilterChooser::getPredicateIndex(DecoderTableInfo &TableInfo, 1196230592Sken StringRef Predicate) const { 1197212420Sken // Using the full predicate string as the key value here is a bit 1198230592Sken // heavyweight, but is effective. If the string comparisons become a 1199212420Sken // performance concern, we can implement a mangling of the predicate 1200230592Sken // data easilly enough with a map back to the actual string. That's 1201230592Sken // overkill for now, though. 1202230592Sken 1203230592Sken // Make sure the predicate is in the table. 1204218812Sken TableInfo.Predicates.insert(Predicate.str()); 1205218812Sken // Now figure out the index for when we write out the table. 1206218812Sken PredicateSet::const_iterator P = std::find(TableInfo.Predicates.begin(), 1207218812Sken TableInfo.Predicates.end(), 1208253460Sscottl Predicate.str()); 1209218812Sken return (unsigned)(P - TableInfo.Predicates.begin()); 1210230592Sken} 1211253460Sscottl 1212230592Skenvoid FilterChooser::emitPredicateTableEntry(DecoderTableInfo &TableInfo, 1213230592Sken unsigned Opc) const { 1214230592Sken if (!doesOpcodeNeedPredicate(Opc)) 1215218812Sken return; 1216218812Sken 1217230592Sken // Build up the predicate string. 1218253460Sscottl SmallString<256> Predicate; 1219253460Sscottl // FIXME: emitPredicateMatch() functions can take a buffer directly rather 1220230592Sken // than a stream. 1221230592Sken raw_svector_ostream PS(Predicate); 1222230592Sken unsigned I = 0; 1223230592Sken emitPredicateMatch(PS, I, Opc); 1224230592Sken 1225230592Sken // Figure out the index into the predicate table for the predicate just 1226230592Sken // computed. 1227230592Sken unsigned PIdx = getPredicateIndex(TableInfo, PS.str()); 1228230592Sken SmallString<16> PBytes; 1229230592Sken raw_svector_ostream S(PBytes); 1230230592Sken encodeULEB128(PIdx, S); 1231230592Sken S.flush(); 1232212420Sken 1233253460Sscottl TableInfo.Table.push_back(MCD::OPC_CheckPredicate); 1234230592Sken // Predicate index 1235237683Sken for (unsigned i = 0, e = PBytes.size(); i != e; ++i) 1236237683Sken TableInfo.Table.push_back(PBytes[i]); 1237230592Sken // Push location for NumToSkip backpatching. 1238230592Sken TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); 1239230592Sken TableInfo.Table.push_back(0); 1240230592Sken TableInfo.Table.push_back(0); 1241230592Sken} 1242230592Sken 1243230592Skenvoid FilterChooser::emitSoftFailTableEntry(DecoderTableInfo &TableInfo, 1244230592Sken unsigned Opc) const { 1245230592Sken BitsInit *SFBits = 1246230592Sken AllInstructions[Opc]->TheDef->getValueAsBitsInit("SoftFail"); 1247230592Sken if (!SFBits) return; 1248253460Sscottl BitsInit *InstBits = AllInstructions[Opc]->TheDef->getValueAsBitsInit("Inst"); 1249230592Sken 1250230592Sken APInt PositiveMask(BitWidth, 0ULL); 1251230592Sken APInt NegativeMask(BitWidth, 0ULL); 1252230592Sken for (unsigned i = 0; i < BitWidth; ++i) { 1253230592Sken bit_value_t B = bitFromBits(*SFBits, i); 1254230592Sken bit_value_t IB = bitFromBits(*InstBits, i); 1255230592Sken 1256230592Sken if (B != BIT_TRUE) continue; 1257230592Sken 1258230592Sken switch (IB) { 1259230592Sken case BIT_FALSE: 1260230592Sken // The bit is meant to be false, so emit a check to see if it is true. 1261230592Sken PositiveMask.setBit(i); 1262230592Sken break; 1263230592Sken case BIT_TRUE: 1264230592Sken // The bit is meant to be true, so emit a check to see if it is false. 1265230592Sken NegativeMask.setBit(i); 1266230592Sken break; 1267230592Sken default: 1268230592Sken // The bit is not set; this must be an error! 1269230592Sken StringRef Name = AllInstructions[Opc]->TheDef->getName(); 1270230592Sken errs() << "SoftFail Conflict: bit SoftFail{" << i << "} in " << Name 1271230592Sken << " is set but Inst{" << i << "} is unset!\n" 1272230592Sken << " - You can only mark a bit as SoftFail if it is fully defined" 1273253460Sscottl << " (1/0 - not '?') in Inst\n"; 1274230592Sken return; 1275230592Sken } 1276230592Sken } 1277230592Sken 1278230592Sken bool NeedPositiveMask = PositiveMask.getBoolValue(); 1279212420Sken bool NeedNegativeMask = NegativeMask.getBoolValue(); 1280212420Sken 1281212420Sken if (!NeedPositiveMask && !NeedNegativeMask) 1282230592Sken return; 1283212420Sken 1284230592Sken TableInfo.Table.push_back(MCD::OPC_SoftFail); 1285230592Sken 1286230592Sken SmallString<16> MaskBytes; 1287212420Sken raw_svector_ostream S(MaskBytes); 1288230592Sken if (NeedPositiveMask) { 1289230592Sken encodeULEB128(PositiveMask.getZExtValue(), S); 1290230592Sken S.flush(); 1291230592Sken for (unsigned i = 0, e = MaskBytes.size(); i != e; ++i) 1292230592Sken TableInfo.Table.push_back(MaskBytes[i]); 1293230592Sken } else 1294230592Sken TableInfo.Table.push_back(0); 1295230592Sken if (NeedNegativeMask) { 1296230592Sken MaskBytes.clear(); 1297230592Sken S.resync(); 1298230592Sken encodeULEB128(NegativeMask.getZExtValue(), S); 1299230592Sken S.flush(); 1300253460Sscottl for (unsigned i = 0, e = MaskBytes.size(); i != e; ++i) 1301230592Sken TableInfo.Table.push_back(MaskBytes[i]); 1302230592Sken } else 1303212420Sken TableInfo.Table.push_back(0); 1304212420Sken} 1305212420Sken 1306230592Sken// Emits table entries to decode the singleton. 1307253460Sscottlvoid FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo, 1308253460Sscottl unsigned Opc) const { 1309230592Sken std::vector<unsigned> StartBits; 1310230592Sken std::vector<unsigned> EndBits; 1311230592Sken std::vector<uint64_t> FieldVals; 1312230592Sken insn_t Insn; 1313230592Sken insnWithID(Insn, Opc); 1314230592Sken 1315230592Sken // Look for islands of undecoded bits of the singleton. 1316230592Sken getIslands(StartBits, EndBits, FieldVals, Insn); 1317230592Sken 1318230592Sken unsigned Size = StartBits.size(); 1319230592Sken 1320230592Sken // Emit the predicate table entry if one is needed. 1321212420Sken emitPredicateTableEntry(TableInfo, Opc); 1322253460Sscottl 1323230592Sken // Check any additional encoding fields needed. 1324237683Sken for (unsigned I = Size; I != 0; --I) { 1325237683Sken unsigned NumBits = EndBits[I-1] - StartBits[I-1] + 1; 1326212420Sken TableInfo.Table.push_back(MCD::OPC_CheckField); 1327230592Sken TableInfo.Table.push_back(StartBits[I-1]); 1328212420Sken TableInfo.Table.push_back(NumBits); 1329230592Sken uint8_t Buffer[8], *p; 1330230592Sken encodeULEB128(FieldVals[I-1], Buffer); 1331230592Sken for (p = Buffer; *p >= 128 ; ++p) 1332230592Sken TableInfo.Table.push_back(*p); 1333253460Sscottl TableInfo.Table.push_back(*p); 1334230592Sken // Push location for NumToSkip backpatching. 1335213535Sken TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); 1336230592Sken // The fixup is always 16-bits, so go ahead and allocate the space 1337230592Sken // in the table so all our relative position calculations work OK even 1338230592Sken // before we fully resolve the real value here. 1339230592Sken TableInfo.Table.push_back(0); 1340230592Sken TableInfo.Table.push_back(0); 1341230592Sken } 1342230592Sken 1343230592Sken // Check for soft failure of the match. 1344230592Sken emitSoftFailTableEntry(TableInfo, Opc); 1345230592Sken 1346230592Sken TableInfo.Table.push_back(MCD::OPC_Decode); 1347253460Sscottl uint8_t Buffer[8], *p; 1348230592Sken encodeULEB128(Opc, Buffer); 1349230592Sken for (p = Buffer; *p >= 128 ; ++p) 1350230592Sken TableInfo.Table.push_back(*p); 1351230592Sken TableInfo.Table.push_back(*p); 1352213535Sken 1353213535Sken unsigned DIdx = getDecoderIndex(TableInfo.Decoders, Opc); 1354230592Sken SmallString<16> Bytes; 1355230592Sken raw_svector_ostream S(Bytes); 1356213535Sken encodeULEB128(DIdx, S); 1357230592Sken S.flush(); 1358213535Sken 1359230592Sken // Decoder index 1360230592Sken for (unsigned i = 0, e = Bytes.size(); i != e; ++i) 1361230592Sken TableInfo.Table.push_back(Bytes[i]); 1362213535Sken} 1363230592Sken 1364230592Sken// Emits table entries to decode the singleton, and then to decode the rest. 1365253460Sscottlvoid FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo, 1366230592Sken const Filter &Best) const { 1367230592Sken unsigned Opc = Best.getSingletonOpc(); 1368230592Sken 1369213535Sken // complex singletons need predicate checks from the first singleton 1370230592Sken // to refer forward to the variable filterchooser that follows. 1371237683Sken TableInfo.FixupStack.push_back(FixupList()); 1372230592Sken 1373230592Sken emitSingletonTableEntry(TableInfo, Opc); 1374213535Sken 1375230592Sken resolveTableFixups(TableInfo.Table, TableInfo.FixupStack.back(), 1376230592Sken TableInfo.Table.size()); 1377230592Sken TableInfo.FixupStack.pop_back(); 1378230592Sken 1379253460Sscottl Best.getVariableFC().emitTableEntries(TableInfo); 1380253460Sscottl} 1381230592Sken 1382230592Sken 1383230592Sken// Assign a single filter and run with it. Top level API client can initialize 1384230592Sken// with a single filter to start the filtering process. 1385230592Skenvoid FilterChooser::runSingleFilter(unsigned startBit, unsigned numBit, 1386230592Sken bool mixed) { 1387230592Sken Filters.clear(); 1388253460Sscottl Filter F(*this, startBit, numBit, true); 1389253460Sscottl Filters.push_back(F); 1390230592Sken BestIndex = 0; // Sole Filter instance to choose from. 1391230592Sken bestFilter().recurse(); 1392230592Sken} 1393253460Sscottl 1394230592Sken// reportRegion is a helper function for filterProcessor to mark a region as 1395230592Sken// eligible for use as a filter region. 1396230592Skenvoid FilterChooser::reportRegion(bitAttr_t RA, unsigned StartBit, 1397230592Sken unsigned BitIndex, bool AllowMixed) { 1398230592Sken if (RA == ATTR_MIXED && AllowMixed) 1399230592Sken Filters.push_back(Filter(*this, StartBit, BitIndex - StartBit, true)); 1400230592Sken else if (RA == ATTR_ALL_SET && !AllowMixed) 1401230592Sken Filters.push_back(Filter(*this, StartBit, BitIndex - StartBit, false)); 1402230592Sken} 1403230592Sken 1404230592Sken// FilterProcessor scans the well-known encoding bits of the instructions and 1405230592Sken// builds up a list of candidate filters. It chooses the best filter and 1406253460Sscottl// recursively descends down the decoding tree. 1407230592Skenbool FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { 1408230592Sken Filters.clear(); 1409230592Sken BestIndex = -1; 1410230592Sken unsigned numInstructions = Opcodes.size(); 1411213535Sken 1412213535Sken assert(numInstructions && "Filter created with no instructions"); 1413230592Sken 1414213535Sken // No further filtering is necessary. 1415230592Sken if (numInstructions == 1) 1416213535Sken return true; 1417230592Sken 1418230592Sken // Heuristics. See also doFilter()'s "Heuristics" comment when num of 1419230592Sken // instructions is 3. 1420230592Sken if (AllowMixed && !Greedy) { 1421213535Sken assert(numInstructions == 3); 1422230592Sken 1423213535Sken for (unsigned i = 0; i < Opcodes.size(); ++i) { 1424230592Sken std::vector<unsigned> StartBits; 1425230592Sken std::vector<unsigned> EndBits; 1426230592Sken std::vector<uint64_t> FieldVals; 1427213535Sken insn_t Insn; 1428212772Sken 1429230592Sken insnWithID(Insn, Opcodes[i]); 1430230592Sken 1431230592Sken // Look for islands of undecoded bits of any instruction. 1432212772Sken if (getIslands(StartBits, EndBits, FieldVals, Insn) > 0) { 1433230592Sken // Found an instruction with island(s). Now just assign a filter. 1434253460Sscottl runSingleFilter(StartBits[0], EndBits[0] - StartBits[0] + 1, true); 1435230592Sken return true; 1436237683Sken } 1437230592Sken } 1438230592Sken } 1439230592Sken 1440212772Sken unsigned BitIndex; 1441230592Sken 1442253460Sscottl // We maintain BIT_WIDTH copies of the bitAttrs automaton. 1443230592Sken // The automaton consumes the corresponding bit from each 1444237683Sken // instruction. 1445230592Sken // 1446230592Sken // Input symbols: 0, 1, and _ (unset). 1447230592Sken // States: NONE, FILTERED, ALL_SET, ALL_UNSET, and MIXED. 1448230592Sken // Initial state: NONE. 1449230592Sken // 1450230592Sken // (NONE) ------- [01] -> (ALL_SET) 1451230592Sken // (NONE) ------- _ ----> (ALL_UNSET) 1452230592Sken // (ALL_SET) ---- [01] -> (ALL_SET) 1453230592Sken // (ALL_SET) ---- _ ----> (MIXED) 1454230592Sken // (ALL_UNSET) -- [01] -> (MIXED) 1455230592Sken // (ALL_UNSET) -- _ ----> (ALL_UNSET) 1456212420Sken // (MIXED) ------ . ----> (MIXED) 1457253460Sscottl // (FILTERED)---- . ----> (FILTERED) 1458230592Sken 1459237683Sken std::vector<bitAttr_t> bitAttrs; 1460237683Sken 1461237683Sken // FILTERED bit positions provide no entropy and are not worthy of pursuing. 1462213535Sken // Filter::recurse() set either BIT_TRUE or BIT_FALSE for each position. 1463230592Sken for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) 1464230592Sken if (FilterBitValues[BitIndex] == BIT_TRUE || 1465230592Sken FilterBitValues[BitIndex] == BIT_FALSE) 1466230592Sken bitAttrs.push_back(ATTR_FILTERED); 1467213535Sken else 1468253460Sscottl bitAttrs.push_back(ATTR_NONE); 1469230592Sken 1470237683Sken for (unsigned InsnIndex = 0; InsnIndex < numInstructions; ++InsnIndex) { 1471230592Sken insn_t insn; 1472230592Sken 1473230592Sken insnWithID(insn, Opcodes[InsnIndex]); 1474212420Sken 1475237683Sken for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { 1476230592Sken switch (bitAttrs[BitIndex]) { 1477253460Sscottl case ATTR_NONE: 1478230592Sken if (insn[BitIndex] == BIT_UNSET) 1479237683Sken bitAttrs[BitIndex] = ATTR_ALL_UNSET; 1480230592Sken else 1481230592Sken bitAttrs[BitIndex] = ATTR_ALL_SET; 1482230592Sken break; 1483230592Sken case ATTR_ALL_SET: 1484230592Sken if (insn[BitIndex] == BIT_UNSET) 1485230592Sken bitAttrs[BitIndex] = ATTR_MIXED; 1486230592Sken break; 1487253460Sscottl case ATTR_ALL_UNSET: 1488230592Sken if (insn[BitIndex] != BIT_UNSET) 1489237683Sken bitAttrs[BitIndex] = ATTR_MIXED; 1490230592Sken break; 1491230592Sken case ATTR_MIXED: 1492230592Sken case ATTR_FILTERED: 1493230592Sken break; 1494213535Sken } 1495212420Sken } 1496230592Sken } 1497230592Sken 1498230592Sken // The regionAttr automaton consumes the bitAttrs automatons' state, 1499230592Sken // lowest-to-highest. 1500213535Sken // 1501230592Sken // Input symbols: F(iltered), (all_)S(et), (all_)U(nset), M(ixed) 1502230592Sken // States: NONE, ALL_SET, MIXED 1503230592Sken // Initial state: NONE 1504212420Sken // 1505230592Sken // (NONE) ----- F --> (NONE) 1506230592Sken // (NONE) ----- S --> (ALL_SET) ; and set region start 1507253460Sscottl // (NONE) ----- U --> (NONE) 1508230592Sken // (NONE) ----- M --> (MIXED) ; and set region start 1509230592Sken // (ALL_SET) -- F --> (NONE) ; and report an ALL_SET region 1510230592Sken // (ALL_SET) -- S --> (ALL_SET) 1511213535Sken // (ALL_SET) -- U --> (NONE) ; and report an ALL_SET region 1512253460Sscottl // (ALL_SET) -- M --> (MIXED) ; and report an ALL_SET region 1513253460Sscottl // (MIXED) ---- F --> (NONE) ; and report a MIXED region 1514253460Sscottl // (MIXED) ---- S --> (ALL_SET) ; and report a MIXED region 1515230592Sken // (MIXED) ---- U --> (NONE) ; and report a MIXED region 1516237683Sken // (MIXED) ---- M --> (MIXED) 1517230592Sken 1518230592Sken bitAttr_t RA = ATTR_NONE; 1519213535Sken unsigned StartBit = 0; 1520230592Sken 1521230592Sken for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { 1522212420Sken bitAttr_t bitAttr = bitAttrs[BitIndex]; 1523237683Sken 1524213535Sken assert(bitAttr != ATTR_NONE && "Bit without attributes"); 1525230592Sken 1526230592Sken switch (RA) { 1527230592Sken case ATTR_NONE: 1528230592Sken switch (bitAttr) { 1529230592Sken case ATTR_FILTERED: 1530230592Sken break; 1531213535Sken case ATTR_ALL_SET: 1532230592Sken StartBit = BitIndex; 1533230592Sken RA = ATTR_ALL_SET; 1534213535Sken break; 1535230592Sken case ATTR_ALL_UNSET: 1536213535Sken break; 1537230592Sken case ATTR_MIXED: 1538230592Sken StartBit = BitIndex; 1539253460Sscottl RA = ATTR_MIXED; 1540230592Sken break; 1541230592Sken default: 1542230592Sken llvm_unreachable("Unexpected bitAttr!"); 1543230592Sken } 1544213535Sken break; 1545213535Sken case ATTR_ALL_SET: 1546230592Sken switch (bitAttr) { 1547230592Sken case ATTR_FILTERED: 1548230592Sken reportRegion(RA, StartBit, BitIndex, AllowMixed); 1549230592Sken RA = ATTR_NONE; 1550230592Sken break; 1551230592Sken case ATTR_ALL_SET: 1552213535Sken break; 1553230592Sken case ATTR_ALL_UNSET: 1554230592Sken reportRegion(RA, StartBit, BitIndex, AllowMixed); 1555213535Sken RA = ATTR_NONE; 1556253460Sscottl break; 1557230592Sken case ATTR_MIXED: 1558213535Sken reportRegion(RA, StartBit, BitIndex, AllowMixed); 1559253460Sscottl StartBit = BitIndex; 1560213535Sken RA = ATTR_MIXED; 1561230592Sken break; 1562230592Sken default: 1563230592Sken llvm_unreachable("Unexpected bitAttr!"); 1564230592Sken } 1565230592Sken break; 1566230592Sken case ATTR_MIXED: 1567230592Sken switch (bitAttr) { 1568253460Sscottl case ATTR_FILTERED: 1569253460Sscottl reportRegion(RA, StartBit, BitIndex, AllowMixed); 1570230592Sken StartBit = BitIndex; 1571230592Sken RA = ATTR_NONE; 1572213535Sken break; 1573230592Sken case ATTR_ALL_SET: 1574253460Sscottl reportRegion(RA, StartBit, BitIndex, AllowMixed); 1575230592Sken StartBit = BitIndex; 1576230592Sken RA = ATTR_ALL_SET; 1577213535Sken break; 1578253460Sscottl case ATTR_ALL_UNSET: 1579230592Sken reportRegion(RA, StartBit, BitIndex, AllowMixed); 1580213535Sken RA = ATTR_NONE; 1581230592Sken break; 1582230592Sken case ATTR_MIXED: 1583213535Sken break; 1584230592Sken default: 1585230592Sken llvm_unreachable("Unexpected bitAttr!"); 1586230592Sken } 1587230592Sken break; 1588230592Sken case ATTR_ALL_UNSET: 1589230592Sken llvm_unreachable("regionAttr state machine has no ATTR_UNSET state"); 1590230592Sken case ATTR_FILTERED: 1591230592Sken llvm_unreachable("regionAttr state machine has no ATTR_FILTERED state"); 1592230592Sken } 1593230592Sken } 1594230592Sken 1595230592Sken // At the end, if we're still in ALL_SET or MIXED states, report a region 1596253460Sscottl switch (RA) { 1597253460Sscottl case ATTR_NONE: 1598230592Sken break; 1599213535Sken case ATTR_FILTERED: 1600230592Sken break; 1601253460Sscottl case ATTR_ALL_SET: 1602230592Sken reportRegion(RA, StartBit, BitIndex, AllowMixed); 1603213535Sken break; 1604230592Sken case ATTR_ALL_UNSET: 1605230592Sken break; 1606230592Sken case ATTR_MIXED: 1607230592Sken reportRegion(RA, StartBit, BitIndex, AllowMixed); 1608230592Sken break; 1609230592Sken } 1610230592Sken 1611230592Sken // We have finished with the filter processings. Now it's time to choose 1612230592Sken // the best performing filter. 1613230592Sken BestIndex = 0; 1614230592Sken bool AllUseless = true; 1615230592Sken unsigned BestScore = 0; 1616230592Sken 1617253460Sscottl for (unsigned i = 0, e = Filters.size(); i != e; ++i) { 1618253460Sscottl unsigned Usefulness = Filters[i].usefulness(); 1619230592Sken 1620230592Sken if (Usefulness) 1621213535Sken AllUseless = false; 1622213535Sken 1623212420Sken if (Usefulness > BestScore) { 1624212420Sken BestIndex = i; 1625212420Sken BestScore = Usefulness; 1626212420Sken } 1627212420Sken } 1628212420Sken 1629212420Sken if (!AllUseless) 1630230592Sken bestFilter().recurse(); 1631212420Sken 1632230592Sken return !AllUseless; 1633230592Sken} // end of FilterChooser::filterProcessor(bool) 1634237683Sken 1635212420Sken// Decides on the best configuration of filter(s) to use in order to decode 1636212420Sken// the instructions. A conflict of instructions may occur, in which case we 1637253460Sscottl// dump the conflict set to the standard error. 1638230592Skenvoid FilterChooser::doFilter() { 1639212420Sken unsigned Num = Opcodes.size(); 1640212420Sken assert(Num && "FilterChooser created with no instructions"); 1641212420Sken 1642253460Sscottl // Try regions of consecutive known bit values first. 1643212420Sken if (filterProcessor(false)) 1644253460Sscottl return; 1645230592Sken 1646237683Sken // Then regions of mixed bits (both known and unitialized bit values allowed). 1647212420Sken if (filterProcessor(true)) 1648212420Sken return; 1649212420Sken 1650231240Sken // Heuristics to cope with conflict set {t2CMPrs, t2SUBSrr, t2SUBSrs} where 1651253550Sken // no single instruction for the maximum ATTR_MIXED region Inst{14-4} has a 1652253550Sken // well-known encoding pattern. In such case, we backtrack and scan for the 1653231240Sken // the very first consecutive ATTR_ALL_SET region and assign a filter to it. 1654231240Sken if (Num == 3 && filterProcessor(true, false)) 1655231240Sken return; 1656231240Sken 1657230592Sken // If we come to here, the instruction decoding has failed. 1658253550Sken // Set the BestIndex to -1 to indicate so. 1659253550Sken BestIndex = -1; 1660253550Sken} 1661253550Sken 1662253550Sken// emitTableEntries - Emit state machine entries to decode our share of 1663253550Sken// instructions. 1664253550Skenvoid FilterChooser::emitTableEntries(DecoderTableInfo &TableInfo) const { 1665253550Sken if (Opcodes.size() == 1) { 1666253550Sken // There is only one instruction in the set, which is great! 1667253550Sken // Call emitSingletonDecoder() to see whether there are any remaining 1668253550Sken // encodings bits. 1669230592Sken emitSingletonTableEntry(TableInfo, Opcodes[0]); 1670230592Sken return; 1671230592Sken } 1672230592Sken 1673230592Sken // Choose the best filter to do the decodings! 1674230592Sken if (BestIndex != -1) { 1675230592Sken const Filter &Best = Filters[BestIndex]; 1676230592Sken if (Best.getNumFiltered() == 1) 1677230592Sken emitSingletonTableEntry(TableInfo, Best); 1678230592Sken else 1679230592Sken Best.emitTableEntry(TableInfo); 1680230592Sken return; 1681212420Sken } 1682230592Sken 1683253460Sscottl // We don't know how to decode these instructions! Dump the 1684230592Sken // conflict set and bail. 1685230592Sken 1686230592Sken // Print out useful conflict information for postmortem analysis. 1687230592Sken errs() << "Decoding Conflict:\n"; 1688230592Sken 1689212420Sken dumpStack(errs(), "\t\t"); 1690212420Sken 1691212420Sken for (unsigned i = 0; i < Opcodes.size(); ++i) { 1692212420Sken const std::string &Name = nameWithID(Opcodes[i]); 1693212420Sken 1694212420Sken errs() << '\t' << Name << " "; 1695212420Sken dumpBits(errs(), 1696212420Sken getBitsField(*AllInstructions[Opcodes[i]]->TheDef, "Inst")); 1697212420Sken errs() << '\n'; 1698212420Sken } 1699212420Sken} 1700212420Sken 1701212420Skenstatic bool populateInstruction(const CodeGenInstruction &CGI, unsigned Opc, 1702218812Sken std::map<unsigned, std::vector<OperandInfo> > &Operands){ 1703237683Sken const Record &Def = *CGI.TheDef; 1704212420Sken // If all the bit positions are not specified; do not decode this instruction. 1705212420Sken // We are bound to fail! For proper disassembly, the well-known encoding bits 1706237683Sken // of the instruction must be fully specified. 1707212420Sken // 1708212420Sken // This also removes pseudo instructions from considerations of disassembly, 1709212420Sken // which is a better design and less fragile than the name matchings. 1710212420Sken // Ignore "asm parser only" instructions. 1711212420Sken if (Def.getValueAsBit("isAsmParserOnly") || 1712212420Sken Def.getValueAsBit("isCodeGenOnly")) 1713212420Sken return false; 1714212420Sken 1715237683Sken BitsInit &Bits = getBitsField(Def, "Inst"); 1716212420Sken if (Bits.allInComplete()) return false; 1717237683Sken 1718212420Sken std::vector<OperandInfo> InsnOperands; 1719212420Sken 1720212420Sken // If the instruction has specified a custom decoding hook, use that instead 1721212420Sken // of trying to auto-generate the decoder. 1722212420Sken std::string InstDecoder = Def.getValueAsString("DecoderMethod"); 1723237683Sken if (InstDecoder != "") { 1724212420Sken InsnOperands.push_back(OperandInfo(InstDecoder)); 1725212420Sken Operands[Opc] = InsnOperands; 1726212420Sken return true; 1727237683Sken } 1728212420Sken 1729212420Sken // Generate a description of the operand of the instruction that we know 1730212420Sken // how to decode automatically. 1731212420Sken // FIXME: We'll need to have a way to manually override this as needed. 1732237683Sken 1733212420Sken // Gather the outputs/inputs of the instruction, so we can find their 1734212420Sken // positions in the encoding. This assumes for now that they appear in the 1735237683Sken // MCInst in the order that they're listed. 1736253550Sken std::vector<std::pair<Init*, std::string> > InOutOperands; 1737237683Sken DagInit *Out = Def.getValueAsDag("OutOperandList"); 1738212420Sken DagInit *In = Def.getValueAsDag("InOperandList"); 1739212420Sken for (unsigned i = 0; i < Out->getNumArgs(); ++i) 1740212420Sken InOutOperands.push_back(std::make_pair(Out->getArg(i), Out->getArgName(i))); 1741212420Sken for (unsigned i = 0; i < In->getNumArgs(); ++i) 1742212420Sken InOutOperands.push_back(std::make_pair(In->getArg(i), In->getArgName(i))); 1743212420Sken 1744212420Sken // Search for tied operands, so that we can correctly instantiate 1745237683Sken // operands that are not explicitly represented in the encoding. 1746212420Sken std::map<std::string, std::string> TiedNames; 1747212420Sken for (unsigned i = 0; i < CGI.Operands.size(); ++i) { 1748237683Sken int tiedTo = CGI.Operands[i].getTiedRegister(); 1749212420Sken if (tiedTo != -1) { 1750212420Sken TiedNames[InOutOperands[i].second] = InOutOperands[tiedTo].second; 1751237683Sken TiedNames[InOutOperands[tiedTo].second] = InOutOperands[i].second; 1752212420Sken } 1753212420Sken } 1754212420Sken 1755212420Sken // For each operand, see if we can figure out where it is encoded. 1756237683Sken for (std::vector<std::pair<Init*, std::string> >::const_iterator 1757212420Sken NI = InOutOperands.begin(), NE = InOutOperands.end(); NI != NE; ++NI) { 1758212420Sken std::string Decoder = ""; 1759237683Sken 1760237683Sken // At this point, we can locate the field, but we need to know how to 1761216368Sken // interpret it. As a first step, require the target to provide callbacks 1762212420Sken // for decoding register classes. 1763212420Sken // FIXME: This need to be extended to handle instructions with custom 1764212420Sken // decoder methods, and operands with (simple) MIOperandInfo's. 1765212420Sken TypedInit *TI = cast<TypedInit>(NI->first); 1766212420Sken RecordRecTy *Type = cast<RecordRecTy>(TI->getType()); 1767212420Sken Record *TypeRecord = Type->getRecord(); 1768212420Sken bool isReg = false; 1769212420Sken if (TypeRecord->isSubClassOf("RegisterOperand")) 1770212420Sken TypeRecord = TypeRecord->getValueAsDef("RegClass"); 1771212420Sken if (TypeRecord->isSubClassOf("RegisterClass")) { 1772237683Sken Decoder = "Decode" + TypeRecord->getName() + "RegisterClass"; 1773212420Sken isReg = true; 1774216088Sken } 1775230592Sken 1776230592Sken RecordVal *DecoderString = TypeRecord->getValue("DecoderMethod"); 1777230592Sken StringInit *String = DecoderString ? 1778230592Sken dyn_cast<StringInit>(DecoderString->getValue()) : 0; 1779216088Sken if (!isReg && String && String->getValue() != "") 1780230592Sken Decoder = String->getValue(); 1781230592Sken 1782230592Sken OperandInfo OpInfo(Decoder); 1783230592Sken unsigned Base = ~0U; 1784230592Sken unsigned Width = 0; 1785230592Sken unsigned Offset = 0; 1786230592Sken 1787230592Sken for (unsigned bi = 0; bi < Bits.getNumBits(); ++bi) { 1788230592Sken VarInit *Var = 0; 1789237683Sken VarBitInit *BI = dyn_cast<VarBitInit>(Bits.getBit(bi)); 1790230592Sken if (BI) 1791230592Sken Var = dyn_cast<VarInit>(BI->getBitVar()); 1792230592Sken else 1793237683Sken Var = dyn_cast<VarInit>(Bits.getBit(bi)); 1794230592Sken 1795230592Sken if (!Var) { 1796230592Sken if (Base != ~0U) { 1797230592Sken OpInfo.addField(Base, Width, Offset); 1798230592Sken Base = ~0U; 1799230592Sken Width = 0; 1800230592Sken Offset = 0; 1801230592Sken } 1802230592Sken continue; 1803230592Sken } 1804230592Sken 1805230592Sken if (Var->getName() != NI->second && 1806230592Sken Var->getName() != TiedNames[NI->second]) { 1807230592Sken if (Base != ~0U) { 1808230592Sken OpInfo.addField(Base, Width, Offset); 1809230592Sken Base = ~0U; 1810230592Sken Width = 0; 1811230592Sken Offset = 0; 1812237683Sken } 1813237683Sken continue; 1814230592Sken } 1815230592Sken 1816230592Sken if (Base == ~0U) { 1817230592Sken Base = bi; 1818230592Sken Width = 1; 1819230592Sken Offset = BI ? BI->getBitNum() : 0; 1820230592Sken } else if (BI && BI->getBitNum() != Offset + Width) { 1821237683Sken OpInfo.addField(Base, Width, Offset); 1822230592Sken Base = bi; 1823230592Sken Width = 1; 1824230592Sken Offset = BI->getBitNum(); 1825230592Sken } else { 1826230592Sken ++Width; 1827230592Sken } 1828212420Sken } 1829246713Skib 1830246713Skib if (Base != ~0U) 1831246713Skib OpInfo.addField(Base, Width, Offset); 1832246713Skib 1833246713Skib if (OpInfo.numFields() > 0) 1834246713Skib InsnOperands.push_back(OpInfo); 1835212420Sken } 1836212420Sken 1837212420Sken Operands[Opc] = InsnOperands; 1838237683Sken 1839212420Sken 1840212420Sken#if 0 1841212420Sken DEBUG({ 1842230592Sken // Dumps the instruction encoding bits. 1843230592Sken dumpBits(errs(), Bits); 1844212420Sken 1845230592Sken errs() << '\n'; 1846230592Sken 1847230592Sken // Dumps the list of operand info. 1848230592Sken for (unsigned i = 0, e = CGI.Operands.size(); i != e; ++i) { 1849230592Sken const CGIOperandList::OperandInfo &Info = CGI.Operands[i]; 1850230592Sken const std::string &OperandName = Info.Name; 1851230592Sken const Record &OperandDef = *Info.Rec; 1852230592Sken 1853230592Sken errs() << "\t" << OperandName << " (" << OperandDef.getName() << ")\n"; 1854230592Sken } 1855230592Sken }); 1856230592Sken#endif 1857218812Sken 1858212420Sken return true; 1859212420Sken} 1860212420Sken 1861230592Sken// emitFieldFromInstruction - Emit the templated helper function 1862230592Sken// fieldFromInstruction(). 1863230592Skenstatic void emitFieldFromInstruction(formatted_raw_ostream &OS) { 1864253550Sken OS << "// Helper function for extracting fields from encoded instructions.\n" 1865230592Sken << "template<typename InsnType>\n" 1866253460Sscottl << "static InsnType fieldFromInstruction(InsnType insn, unsigned startBit,\n" 1867253460Sscottl << " unsigned numBits) {\n" 1868230592Sken << " assert(startBit + numBits <= (sizeof(InsnType)*8) &&\n" 1869212420Sken << " \"Instruction field out of bounds!\");\n" 1870212420Sken << " InsnType fieldMask;\n" 1871212420Sken << " if (numBits == sizeof(InsnType)*8)\n" 1872212420Sken << " fieldMask = (InsnType)(-1LL);\n" 1873212420Sken << " else\n" 1874231240Sken << " fieldMask = (((InsnType)1 << numBits) - 1) << startBit;\n" 1875231240Sken << " return (insn & fieldMask) >> startBit;\n" 1876231240Sken << "}\n\n"; 1877231240Sken} 1878231240Sken 1879231240Sken// emitDecodeInstruction - Emit the templated helper function 1880231240Sken// decodeInstruction(). 1881231240Skenstatic void emitDecodeInstruction(formatted_raw_ostream &OS) { 1882231240Sken OS << "template<typename InsnType>\n" 1883231240Sken << "static DecodeStatus decodeInstruction(const uint8_t DecodeTable[], MCInst &MI,\n" 1884231240Sken << " InsnType insn, uint64_t Address,\n" 1885231240Sken << " const void *DisAsm,\n" 1886231240Sken << " const MCSubtargetInfo &STI) {\n" 1887231240Sken << " uint64_t Bits = STI.getFeatureBits();\n" 1888231240Sken << "\n" 1889231240Sken << " const uint8_t *Ptr = DecodeTable;\n" 1890231240Sken << " uint32_t CurFieldValue = 0;\n" 1891231240Sken << " DecodeStatus S = MCDisassembler::Success;\n" 1892231240Sken << " for (;;) {\n" 1893231240Sken << " ptrdiff_t Loc = Ptr - DecodeTable;\n" 1894231240Sken << " switch (*Ptr) {\n" 1895231240Sken << " default:\n" 1896231240Sken << " errs() << Loc << \": Unexpected decode table opcode!\\n\";\n" 1897231240Sken << " return MCDisassembler::Fail;\n" 1898231240Sken << " case MCD::OPC_ExtractField: {\n" 1899231240Sken << " unsigned Start = *++Ptr;\n" 1900231240Sken << " unsigned Len = *++Ptr;\n" 1901231240Sken << " ++Ptr;\n" 1902231240Sken << " CurFieldValue = fieldFromInstruction(insn, Start, Len);\n" 1903231240Sken << " DEBUG(dbgs() << Loc << \": OPC_ExtractField(\" << Start << \", \"\n" 1904231240Sken << " << Len << \"): \" << CurFieldValue << \"\\n\");\n" 1905231240Sken << " break;\n" 1906231240Sken << " }\n" 1907253460Sscottl << " case MCD::OPC_FilterValue: {\n" 1908231240Sken << " // Decode the field value.\n" 1909231240Sken << " unsigned Len;\n" 1910231240Sken << " InsnType Val = decodeULEB128(++Ptr, &Len);\n" 1911231240Sken << " Ptr += Len;\n" 1912231240Sken << " // NumToSkip is a plain 16-bit integer.\n" 1913231240Sken << " unsigned NumToSkip = *Ptr++;\n" 1914231240Sken << " NumToSkip |= (*Ptr++) << 8;\n" 1915231240Sken << "\n" 1916231240Sken << " // Perform the filter operation.\n" 1917231240Sken << " if (Val != CurFieldValue)\n" 1918231240Sken << " Ptr += NumToSkip;\n" 1919231240Sken << " DEBUG(dbgs() << Loc << \": OPC_FilterValue(\" << Val << \", \" << NumToSkip\n" 1920231240Sken << " << \"): \" << ((Val != CurFieldValue) ? \"FAIL:\" : \"PASS:\")\n" 1921231240Sken << " << \" continuing at \" << (Ptr - DecodeTable) << \"\\n\");\n" 1922231240Sken << "\n" 1923231240Sken << " break;\n" 1924231240Sken << " }\n" 1925231240Sken << " case MCD::OPC_CheckField: {\n" 1926231240Sken << " unsigned Start = *++Ptr;\n" 1927231240Sken << " unsigned Len = *++Ptr;\n" 1928231240Sken << " InsnType FieldValue = fieldFromInstruction(insn, Start, Len);\n" 1929231240Sken << " // Decode the field value.\n" 1930231240Sken << " uint32_t ExpectedValue = decodeULEB128(++Ptr, &Len);\n" 1931231240Sken << " Ptr += Len;\n" 1932231240Sken << " // NumToSkip is a plain 16-bit integer.\n" 1933231240Sken << " unsigned NumToSkip = *Ptr++;\n" 1934231240Sken << " NumToSkip |= (*Ptr++) << 8;\n" 1935231240Sken << "\n" 1936231240Sken << " // If the actual and expected values don't match, skip.\n" 1937231240Sken << " if (ExpectedValue != FieldValue)\n" 1938231240Sken << " Ptr += NumToSkip;\n" 1939231240Sken << " DEBUG(dbgs() << Loc << \": OPC_CheckField(\" << Start << \", \"\n" 1940231240Sken << " << Len << \", \" << ExpectedValue << \", \" << NumToSkip\n" 1941231240Sken << " << \"): FieldValue = \" << FieldValue << \", ExpectedValue = \"\n" 1942231240Sken << " << ExpectedValue << \": \"\n" 1943231240Sken << " << ((ExpectedValue == FieldValue) ? \"PASS\\n\" : \"FAIL\\n\"));\n" 1944231240Sken << " break;\n" 1945231240Sken << " }\n" 1946231240Sken << " case MCD::OPC_CheckPredicate: {\n" 1947231240Sken << " unsigned Len;\n" 1948231240Sken << " // Decode the Predicate Index value.\n" 1949231240Sken << " unsigned PIdx = decodeULEB128(++Ptr, &Len);\n" 1950231240Sken << " Ptr += Len;\n" 1951231240Sken << " // NumToSkip is a plain 16-bit integer.\n" 1952231240Sken << " unsigned NumToSkip = *Ptr++;\n" 1953231240Sken << " NumToSkip |= (*Ptr++) << 8;\n" 1954231240Sken << " // Check the predicate.\n" 1955231240Sken << " bool Pred;\n" 1956231240Sken << " if (!(Pred = checkDecoderPredicate(PIdx, Bits)))\n" 1957231240Sken << " Ptr += NumToSkip;\n" 1958231240Sken << " (void)Pred;\n" 1959231240Sken << " DEBUG(dbgs() << Loc << \": OPC_CheckPredicate(\" << PIdx << \"): \"\n" 1960231240Sken << " << (Pred ? \"PASS\\n\" : \"FAIL\\n\"));\n" 1961231240Sken << "\n" 1962231240Sken << " break;\n" 1963231240Sken << " }\n" 1964231240Sken << " case MCD::OPC_Decode: {\n" 1965231240Sken << " unsigned Len;\n" 1966231240Sken << " // Decode the Opcode value.\n" 1967231240Sken << " unsigned Opc = decodeULEB128(++Ptr, &Len);\n" 1968231240Sken << " Ptr += Len;\n" 1969231240Sken << " unsigned DecodeIdx = decodeULEB128(Ptr, &Len);\n" 1970231240Sken << " Ptr += Len;\n" 1971231240Sken << " DEBUG(dbgs() << Loc << \": OPC_Decode: opcode \" << Opc\n" 1972231240Sken << " << \", using decoder \" << DecodeIdx << \"\\n\" );\n" 1973231240Sken << " DEBUG(dbgs() << \"----- DECODE SUCCESSFUL -----\\n\");\n" 1974231240Sken << "\n" 1975231240Sken << " MI.setOpcode(Opc);\n" 1976231240Sken << " return decodeToMCInst(S, DecodeIdx, insn, MI, Address, DisAsm);\n" 1977231240Sken << " }\n" 1978231240Sken << " case MCD::OPC_SoftFail: {\n" 1979231240Sken << " // Decode the mask values.\n" 1980231240Sken << " unsigned Len;\n" 1981231240Sken << " InsnType PositiveMask = decodeULEB128(++Ptr, &Len);\n" 1982231240Sken << " Ptr += Len;\n" 1983231240Sken << " InsnType NegativeMask = decodeULEB128(Ptr, &Len);\n" 1984231240Sken << " Ptr += Len;\n" 1985231240Sken << " bool Fail = (insn & PositiveMask) || (~insn & NegativeMask);\n" 1986231240Sken << " if (Fail)\n" 1987231240Sken << " S = MCDisassembler::SoftFail;\n" 1988231240Sken << " DEBUG(dbgs() << Loc << \": OPC_SoftFail: \" << (Fail ? \"FAIL\\n\":\"PASS\\n\"));\n" 1989231240Sken << " break;\n" 1990231240Sken << " }\n" 1991231240Sken << " case MCD::OPC_Fail: {\n" 1992231240Sken << " DEBUG(dbgs() << Loc << \": OPC_Fail\\n\");\n" 1993231240Sken << " return MCDisassembler::Fail;\n" 1994231240Sken << " }\n" 1995231240Sken << " }\n" 1996231240Sken << " }\n" 1997231240Sken << " llvm_unreachable(\"bogosity detected in disassembler state machine!\");\n" 1998231240Sken << "}\n\n"; 1999231240Sken} 2000231240Sken 2001231240Sken// Emits disassembler code for instruction decoding. 2002231240Skenvoid FixedLenDecoderEmitter::run(raw_ostream &o) { 2003231240Sken formatted_raw_ostream OS(o); 2004231240Sken OS << "#include \"llvm/MC/MCInst.h\"\n"; 2005231240Sken OS << "#include \"llvm/Support/Debug.h\"\n"; 2006231240Sken OS << "#include \"llvm/Support/DataTypes.h\"\n"; 2007231240Sken OS << "#include \"llvm/Support/LEB128.h\"\n"; 2008231240Sken OS << "#include \"llvm/Support/raw_ostream.h\"\n"; 2009231240Sken OS << "#include <assert.h>\n"; 2010231240Sken OS << '\n'; 2011231240Sken OS << "namespace llvm {\n\n"; 2012231240Sken 2013231240Sken emitFieldFromInstruction(OS); 2014231240Sken 2015231240Sken // Parameterize the decoders based on namespace and instruction width. 2016231240Sken NumberedInstructions = &Target.getInstructionsByEnumValue(); 2017231240Sken std::map<std::pair<std::string, unsigned>, 2018231240Sken std::vector<unsigned> > OpcMap; 2019231240Sken std::map<unsigned, std::vector<OperandInfo> > Operands; 2020231240Sken 2021231240Sken for (unsigned i = 0; i < NumberedInstructions->size(); ++i) { 2022231240Sken const CodeGenInstruction *Inst = NumberedInstructions->at(i); 2023231240Sken const Record *Def = Inst->TheDef; 2024231240Sken unsigned Size = Def->getValueAsInt("Size"); 2025231240Sken if (Def->getValueAsString("Namespace") == "TargetOpcode" || 2026231240Sken Def->getValueAsBit("isPseudo") || 2027231240Sken Def->getValueAsBit("isAsmParserOnly") || 2028231240Sken Def->getValueAsBit("isCodeGenOnly")) 2029231240Sken continue; 2030231240Sken 2031231240Sken std::string DecoderNamespace = Def->getValueAsString("DecoderNamespace"); 2032231240Sken 2033231240Sken if (Size) { 2034231240Sken if (populateInstruction(*Inst, i, Operands)) { 2035231240Sken OpcMap[std::make_pair(DecoderNamespace, Size)].push_back(i); 2036231240Sken } 2037231240Sken } 2038231240Sken } 2039231240Sken 2040231240Sken DecoderTableInfo TableInfo; 2041253460Sscottl for (std::map<std::pair<std::string, unsigned>, 2042253460Sscottl std::vector<unsigned> >::const_iterator 2043231240Sken I = OpcMap.begin(), E = OpcMap.end(); I != E; ++I) { 2044231240Sken // Emit the decoder for this namespace+width combination. 2045231240Sken FilterChooser FC(*NumberedInstructions, I->second, Operands, 2046253460Sscottl 8*I->first.second, this); 2047253550Sken 2048253550Sken // The decode table is cleared for each top level decoder function. The 2049231240Sken // predicates and decoders themselves, however, are shared across all 2050253460Sscottl // decoders to give more opportunities for uniqueing. 2051231240Sken TableInfo.Table.clear(); 2052253460Sscottl TableInfo.FixupStack.clear(); 2053231240Sken TableInfo.Table.reserve(16384); 2054253460Sscottl TableInfo.FixupStack.push_back(FixupList()); 2055231240Sken FC.emitTableEntries(TableInfo); 2056231240Sken // Any NumToSkip fixups in the top level scope can resolve to the 2057231240Sken // OPC_Fail at the end of the table. 2058231240Sken assert(TableInfo.FixupStack.size() == 1 && "fixup stack phasing error!"); 2059231240Sken // Resolve any NumToSkip fixups in the current scope. 2060231240Sken resolveTableFixups(TableInfo.Table, TableInfo.FixupStack.back(), 2061231240Sken TableInfo.Table.size()); 2062231240Sken TableInfo.FixupStack.clear(); 2063231240Sken 2064231240Sken TableInfo.Table.push_back(MCD::OPC_Fail); 2065212420Sken 2066212420Sken // Print the table to the output stream. 2067212420Sken emitTable(OS, TableInfo.Table, 0, FC.getBitWidth(), I->first.first); 2068212420Sken OS.flush(); 2069230592Sken } 2070212420Sken 2071230592Sken // Emit the predicate function. 2072230592Sken emitPredicateFunction(OS, TableInfo.Predicates, 0); 2073230592Sken 2074230592Sken // Emit the decoder function. 2075212420Sken emitDecoderFunction(OS, TableInfo.Decoders, 0); 2076253460Sscottl 2077230592Sken // Emit the main entry point for the decoder, decodeInstruction(). 2078253460Sscottl emitDecodeInstruction(OS); 2079253460Sscottl 2080230592Sken OS << "\n} // End llvm namespace\n"; 2081212420Sken} 2082212420Sken 2083230592Skennamespace llvm { 2084212420Sken 2085212420Skenvoid EmitFixedLenDecoder(RecordKeeper &RK, raw_ostream &OS, 2086212420Sken std::string PredicateNamespace, 2087230592Sken std::string GPrefix, 2088212420Sken std::string GPostfix, 2089218812Sken std::string ROK, 2090218812Sken std::string RFail, 2091218812Sken std::string L) { 2092218812Sken FixedLenDecoderEmitter(RK, PredicateNamespace, GPrefix, GPostfix, 2093218812Sken ROK, RFail, L).run(OS); 2094212420Sken} 2095212420Sken 2096212420Sken} // End llvm namespace 2097212420Sken