1218885Sdim//===------------ FixedLenDecoderEmitter.cpp - Decoder Generator ----------===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// It contains the tablegen backend that emits the decoder functions for 11218885Sdim// targets with fixed length instruction set. 12218885Sdim// 13218885Sdim//===----------------------------------------------------------------------===// 14218885Sdim 15218885Sdim#define DEBUG_TYPE "decoder-emitter" 16218885Sdim 17218885Sdim#include "CodeGenTarget.h" 18234353Sdim#include "llvm/ADT/APInt.h" 19239462Sdim#include "llvm/ADT/SmallString.h" 20218885Sdim#include "llvm/ADT/StringExtras.h" 21239462Sdim#include "llvm/ADT/StringRef.h" 22239462Sdim#include "llvm/ADT/Twine.h" 23239462Sdim#include "llvm/MC/MCFixedLenDisassembler.h" 24239462Sdim#include "llvm/Support/DataTypes.h" 25218885Sdim#include "llvm/Support/Debug.h" 26239462Sdim#include "llvm/Support/FormattedStream.h" 27239462Sdim#include "llvm/Support/LEB128.h" 28218885Sdim#include "llvm/Support/raw_ostream.h" 29249423Sdim#include "llvm/TableGen/Error.h" 30249423Sdim#include "llvm/TableGen/Record.h" 31239462Sdim#include "llvm/TableGen/TableGenBackend.h" 32218885Sdim#include <map> 33218885Sdim#include <string> 34249423Sdim#include <vector> 35218885Sdim 36218885Sdimusing namespace llvm; 37218885Sdim 38239462Sdimnamespace { 39239462Sdimstruct EncodingField { 40239462Sdim unsigned Base, Width, Offset; 41239462Sdim EncodingField(unsigned B, unsigned W, unsigned O) 42239462Sdim : Base(B), Width(W), Offset(O) { } 43239462Sdim}; 44239462Sdim 45239462Sdimstruct OperandInfo { 46239462Sdim std::vector<EncodingField> Fields; 47239462Sdim std::string Decoder; 48239462Sdim 49239462Sdim OperandInfo(std::string D) 50239462Sdim : Decoder(D) { } 51239462Sdim 52239462Sdim void addField(unsigned Base, unsigned Width, unsigned Offset) { 53239462Sdim Fields.push_back(EncodingField(Base, Width, Offset)); 54239462Sdim } 55239462Sdim 56239462Sdim unsigned numFields() const { return Fields.size(); } 57239462Sdim 58239462Sdim typedef std::vector<EncodingField>::const_iterator const_iterator; 59239462Sdim 60239462Sdim const_iterator begin() const { return Fields.begin(); } 61239462Sdim const_iterator end() const { return Fields.end(); } 62239462Sdim}; 63239462Sdim 64239462Sdimtypedef std::vector<uint8_t> DecoderTable; 65239462Sdimtypedef uint32_t DecoderFixup; 66239462Sdimtypedef std::vector<DecoderFixup> FixupList; 67239462Sdimtypedef std::vector<FixupList> FixupScopeList; 68239462Sdimtypedef SetVector<std::string> PredicateSet; 69239462Sdimtypedef SetVector<std::string> DecoderSet; 70239462Sdimstruct DecoderTableInfo { 71239462Sdim DecoderTable Table; 72239462Sdim FixupScopeList FixupStack; 73239462Sdim PredicateSet Predicates; 74239462Sdim DecoderSet Decoders; 75239462Sdim}; 76239462Sdim 77239462Sdim} // End anonymous namespace 78239462Sdim 79239462Sdimnamespace { 80239462Sdimclass FixedLenDecoderEmitter { 81239462Sdim const std::vector<const CodeGenInstruction*> *NumberedInstructions; 82239462Sdimpublic: 83239462Sdim 84239462Sdim // Defaults preserved here for documentation, even though they aren't 85239462Sdim // strictly necessary given the way that this is currently being called. 86239462Sdim FixedLenDecoderEmitter(RecordKeeper &R, 87239462Sdim std::string PredicateNamespace, 88239462Sdim std::string GPrefix = "if (", 89239462Sdim std::string GPostfix = " == MCDisassembler::Fail)" 90239462Sdim " return MCDisassembler::Fail;", 91239462Sdim std::string ROK = "MCDisassembler::Success", 92239462Sdim std::string RFail = "MCDisassembler::Fail", 93239462Sdim std::string L = "") : 94239462Sdim Target(R), 95239462Sdim PredicateNamespace(PredicateNamespace), 96239462Sdim GuardPrefix(GPrefix), GuardPostfix(GPostfix), 97239462Sdim ReturnOK(ROK), ReturnFail(RFail), Locals(L) {} 98239462Sdim 99239462Sdim // Emit the decoder state machine table. 100239462Sdim void emitTable(formatted_raw_ostream &o, DecoderTable &Table, 101239462Sdim unsigned Indentation, unsigned BitWidth, 102239462Sdim StringRef Namespace) const; 103239462Sdim void emitPredicateFunction(formatted_raw_ostream &OS, 104239462Sdim PredicateSet &Predicates, 105239462Sdim unsigned Indentation) const; 106239462Sdim void emitDecoderFunction(formatted_raw_ostream &OS, 107239462Sdim DecoderSet &Decoders, 108239462Sdim unsigned Indentation) const; 109239462Sdim 110239462Sdim // run - Output the code emitter 111239462Sdim void run(raw_ostream &o); 112239462Sdim 113239462Sdimprivate: 114239462Sdim CodeGenTarget Target; 115239462Sdimpublic: 116239462Sdim std::string PredicateNamespace; 117239462Sdim std::string GuardPrefix, GuardPostfix; 118239462Sdim std::string ReturnOK, ReturnFail; 119239462Sdim std::string Locals; 120239462Sdim}; 121239462Sdim} // End anonymous namespace 122239462Sdim 123218885Sdim// The set (BIT_TRUE, BIT_FALSE, BIT_UNSET) represents a ternary logic system 124218885Sdim// for a bit value. 125218885Sdim// 126218885Sdim// BIT_UNFILTERED is used as the init value for a filter position. It is used 127218885Sdim// only for filter processings. 128218885Sdimtypedef enum { 129218885Sdim BIT_TRUE, // '1' 130218885Sdim BIT_FALSE, // '0' 131218885Sdim BIT_UNSET, // '?' 132218885Sdim BIT_UNFILTERED // unfiltered 133218885Sdim} bit_value_t; 134218885Sdim 135218885Sdimstatic bool ValueSet(bit_value_t V) { 136218885Sdim return (V == BIT_TRUE || V == BIT_FALSE); 137218885Sdim} 138218885Sdimstatic bool ValueNotSet(bit_value_t V) { 139218885Sdim return (V == BIT_UNSET); 140218885Sdim} 141218885Sdimstatic int Value(bit_value_t V) { 142218885Sdim return ValueNotSet(V) ? -1 : (V == BIT_FALSE ? 0 : 1); 143218885Sdim} 144234353Sdimstatic bit_value_t bitFromBits(const BitsInit &bits, unsigned index) { 145243830Sdim if (BitInit *bit = dyn_cast<BitInit>(bits.getBit(index))) 146218885Sdim return bit->getValue() ? BIT_TRUE : BIT_FALSE; 147218885Sdim 148218885Sdim // The bit is uninitialized. 149218885Sdim return BIT_UNSET; 150218885Sdim} 151218885Sdim// Prints the bit value for each position. 152234353Sdimstatic void dumpBits(raw_ostream &o, const BitsInit &bits) { 153239462Sdim for (unsigned index = bits.getNumBits(); index > 0; --index) { 154218885Sdim switch (bitFromBits(bits, index - 1)) { 155218885Sdim case BIT_TRUE: 156218885Sdim o << "1"; 157218885Sdim break; 158218885Sdim case BIT_FALSE: 159218885Sdim o << "0"; 160218885Sdim break; 161218885Sdim case BIT_UNSET: 162218885Sdim o << "_"; 163218885Sdim break; 164218885Sdim default: 165234353Sdim llvm_unreachable("unexpected return value from bitFromBits"); 166218885Sdim } 167218885Sdim } 168218885Sdim} 169218885Sdim 170218885Sdimstatic BitsInit &getBitsField(const Record &def, const char *str) { 171218885Sdim BitsInit *bits = def.getValueAsBitsInit(str); 172218885Sdim return *bits; 173218885Sdim} 174218885Sdim 175218885Sdim// Forward declaration. 176239462Sdimnamespace { 177218885Sdimclass FilterChooser; 178239462Sdim} // End anonymous namespace 179218885Sdim 180218885Sdim// Representation of the instruction to work on. 181226633Sdimtypedef std::vector<bit_value_t> insn_t; 182218885Sdim 183218885Sdim/// Filter - Filter works with FilterChooser to produce the decoding tree for 184218885Sdim/// the ISA. 185218885Sdim/// 186218885Sdim/// It is useful to think of a Filter as governing the switch stmts of the 187218885Sdim/// decoding tree in a certain level. Each case stmt delegates to an inferior 188218885Sdim/// FilterChooser to decide what further decoding logic to employ, or in another 189218885Sdim/// words, what other remaining bits to look at. The FilterChooser eventually 190218885Sdim/// chooses a best Filter to do its job. 191218885Sdim/// 192218885Sdim/// This recursive scheme ends when the number of Opcodes assigned to the 193218885Sdim/// FilterChooser becomes 1 or if there is a conflict. A conflict happens when 194218885Sdim/// the Filter/FilterChooser combo does not know how to distinguish among the 195218885Sdim/// Opcodes assigned. 196218885Sdim/// 197218885Sdim/// An example of a conflict is 198218885Sdim/// 199218885Sdim/// Conflict: 200218885Sdim/// 111101000.00........00010000.... 201218885Sdim/// 111101000.00........0001........ 202218885Sdim/// 1111010...00........0001........ 203218885Sdim/// 1111010...00.................... 204218885Sdim/// 1111010......................... 205218885Sdim/// 1111............................ 206218885Sdim/// ................................ 207218885Sdim/// VST4q8a 111101000_00________00010000____ 208218885Sdim/// VST4q8b 111101000_00________00010000____ 209218885Sdim/// 210218885Sdim/// The Debug output shows the path that the decoding tree follows to reach the 211218885Sdim/// the conclusion that there is a conflict. VST4q8a is a vst4 to double-spaced 212218885Sdim/// even registers, while VST4q8b is a vst4 to double-spaced odd regsisters. 213218885Sdim/// 214218885Sdim/// The encoding info in the .td files does not specify this meta information, 215218885Sdim/// which could have been used by the decoder to resolve the conflict. The 216218885Sdim/// decoder could try to decode the even/odd register numbering and assign to 217218885Sdim/// VST4q8a or VST4q8b, but for the time being, the decoder chooses the "a" 218218885Sdim/// version and return the Opcode since the two have the same Asm format string. 219239462Sdimnamespace { 220218885Sdimclass Filter { 221218885Sdimprotected: 222234353Sdim const FilterChooser *Owner;// points to the FilterChooser who owns this filter 223218885Sdim unsigned StartBit; // the starting bit position 224218885Sdim unsigned NumBits; // number of bits to filter 225218885Sdim bool Mixed; // a mixed region contains both set and unset bits 226218885Sdim 227218885Sdim // Map of well-known segment value to the set of uid's with that value. 228218885Sdim std::map<uint64_t, std::vector<unsigned> > FilteredInstructions; 229218885Sdim 230218885Sdim // Set of uid's with non-constant segment values. 231218885Sdim std::vector<unsigned> VariableInstructions; 232218885Sdim 233218885Sdim // Map of well-known segment value to its delegate. 234234353Sdim std::map<unsigned, const FilterChooser*> FilterChooserMap; 235218885Sdim 236218885Sdim // Number of instructions which fall under FilteredInstructions category. 237218885Sdim unsigned NumFiltered; 238218885Sdim 239218885Sdim // Keeps track of the last opcode in the filtered bucket. 240218885Sdim unsigned LastOpcFiltered; 241218885Sdim 242218885Sdimpublic: 243234353Sdim unsigned getNumFiltered() const { return NumFiltered; } 244234353Sdim unsigned getSingletonOpc() const { 245218885Sdim assert(NumFiltered == 1); 246218885Sdim return LastOpcFiltered; 247218885Sdim } 248218885Sdim // Return the filter chooser for the group of instructions without constant 249218885Sdim // segment values. 250234353Sdim const FilterChooser &getVariableFC() const { 251218885Sdim assert(NumFiltered == 1); 252218885Sdim assert(FilterChooserMap.size() == 1); 253218885Sdim return *(FilterChooserMap.find((unsigned)-1)->second); 254218885Sdim } 255218885Sdim 256218885Sdim Filter(const Filter &f); 257218885Sdim Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, bool mixed); 258218885Sdim 259218885Sdim ~Filter(); 260218885Sdim 261218885Sdim // Divides the decoding task into sub tasks and delegates them to the 262218885Sdim // inferior FilterChooser's. 263218885Sdim // 264218885Sdim // A special case arises when there's only one entry in the filtered 265218885Sdim // instructions. In order to unambiguously decode the singleton, we need to 266218885Sdim // match the remaining undecoded encoding bits against the singleton. 267218885Sdim void recurse(); 268218885Sdim 269239462Sdim // Emit table entries to decode instructions given a segment or segments of 270239462Sdim // bits. 271239462Sdim void emitTableEntry(DecoderTableInfo &TableInfo) const; 272218885Sdim 273218885Sdim // Returns the number of fanout produced by the filter. More fanout implies 274218885Sdim // the filter distinguishes more categories of instructions. 275218885Sdim unsigned usefulness() const; 276218885Sdim}; // End of class Filter 277239462Sdim} // End anonymous namespace 278218885Sdim 279218885Sdim// These are states of our finite state machines used in FilterChooser's 280218885Sdim// filterProcessor() which produces the filter candidates to use. 281218885Sdimtypedef enum { 282218885Sdim ATTR_NONE, 283218885Sdim ATTR_FILTERED, 284218885Sdim ATTR_ALL_SET, 285218885Sdim ATTR_ALL_UNSET, 286218885Sdim ATTR_MIXED 287218885Sdim} bitAttr_t; 288218885Sdim 289218885Sdim/// FilterChooser - FilterChooser chooses the best filter among a set of Filters 290218885Sdim/// in order to perform the decoding of instructions at the current level. 291218885Sdim/// 292218885Sdim/// Decoding proceeds from the top down. Based on the well-known encoding bits 293218885Sdim/// of instructions available, FilterChooser builds up the possible Filters that 294218885Sdim/// can further the task of decoding by distinguishing among the remaining 295218885Sdim/// candidate instructions. 296218885Sdim/// 297218885Sdim/// Once a filter has been chosen, it is called upon to divide the decoding task 298218885Sdim/// into sub-tasks and delegates them to its inferior FilterChoosers for further 299218885Sdim/// processings. 300218885Sdim/// 301218885Sdim/// It is useful to think of a Filter as governing the switch stmts of the 302218885Sdim/// decoding tree. And each case is delegated to an inferior FilterChooser to 303218885Sdim/// decide what further remaining bits to look at. 304239462Sdimnamespace { 305218885Sdimclass FilterChooser { 306218885Sdimprotected: 307218885Sdim friend class Filter; 308218885Sdim 309218885Sdim // Vector of codegen instructions to choose our filter. 310218885Sdim const std::vector<const CodeGenInstruction*> &AllInstructions; 311218885Sdim 312218885Sdim // Vector of uid's for this filter chooser to work on. 313234353Sdim const std::vector<unsigned> &Opcodes; 314218885Sdim 315218885Sdim // Lookup table for the operand decoding of instructions. 316234353Sdim const std::map<unsigned, std::vector<OperandInfo> > &Operands; 317218885Sdim 318218885Sdim // Vector of candidate filters. 319218885Sdim std::vector<Filter> Filters; 320218885Sdim 321218885Sdim // Array of bit values passed down from our parent. 322218885Sdim // Set to all BIT_UNFILTERED's for Parent == NULL. 323226633Sdim std::vector<bit_value_t> FilterBitValues; 324218885Sdim 325218885Sdim // Links to the FilterChooser above us in the decoding tree. 326234353Sdim const FilterChooser *Parent; 327218885Sdim 328218885Sdim // Index of the best filter from Filters. 329218885Sdim int BestIndex; 330218885Sdim 331226633Sdim // Width of instructions 332226633Sdim unsigned BitWidth; 333226633Sdim 334226633Sdim // Parent emitter 335226633Sdim const FixedLenDecoderEmitter *Emitter; 336226633Sdim 337218885Sdimpublic: 338234353Sdim FilterChooser(const FilterChooser &FC) 339234353Sdim : AllInstructions(FC.AllInstructions), Opcodes(FC.Opcodes), 340226633Sdim Operands(FC.Operands), Filters(FC.Filters), 341226633Sdim FilterBitValues(FC.FilterBitValues), Parent(FC.Parent), 342234353Sdim BestIndex(FC.BestIndex), BitWidth(FC.BitWidth), 343234353Sdim Emitter(FC.Emitter) { } 344218885Sdim 345218885Sdim FilterChooser(const std::vector<const CodeGenInstruction*> &Insts, 346218885Sdim const std::vector<unsigned> &IDs, 347234353Sdim const std::map<unsigned, std::vector<OperandInfo> > &Ops, 348226633Sdim unsigned BW, 349234353Sdim const FixedLenDecoderEmitter *E) 350234353Sdim : AllInstructions(Insts), Opcodes(IDs), Operands(Ops), Filters(), 351226633Sdim Parent(NULL), BestIndex(-1), BitWidth(BW), Emitter(E) { 352226633Sdim for (unsigned i = 0; i < BitWidth; ++i) 353226633Sdim FilterBitValues.push_back(BIT_UNFILTERED); 354218885Sdim 355218885Sdim doFilter(); 356218885Sdim } 357218885Sdim 358218885Sdim FilterChooser(const std::vector<const CodeGenInstruction*> &Insts, 359218885Sdim const std::vector<unsigned> &IDs, 360234353Sdim const std::map<unsigned, std::vector<OperandInfo> > &Ops, 361234353Sdim const std::vector<bit_value_t> &ParentFilterBitValues, 362234353Sdim const FilterChooser &parent) 363234353Sdim : AllInstructions(Insts), Opcodes(IDs), Operands(Ops), 364226633Sdim Filters(), FilterBitValues(ParentFilterBitValues), 365226633Sdim Parent(&parent), BestIndex(-1), BitWidth(parent.BitWidth), 366226633Sdim Emitter(parent.Emitter) { 367218885Sdim doFilter(); 368218885Sdim } 369218885Sdim 370239462Sdim unsigned getBitWidth() const { return BitWidth; } 371218885Sdim 372218885Sdimprotected: 373218885Sdim // Populates the insn given the uid. 374218885Sdim void insnWithID(insn_t &Insn, unsigned Opcode) const { 375218885Sdim BitsInit &Bits = getBitsField(*AllInstructions[Opcode]->TheDef, "Inst"); 376218885Sdim 377234353Sdim // We may have a SoftFail bitmask, which specifies a mask where an encoding 378234353Sdim // may differ from the value in "Inst" and yet still be valid, but the 379234353Sdim // disassembler should return SoftFail instead of Success. 380234353Sdim // 381234353Sdim // This is used for marking UNPREDICTABLE instructions in the ARM world. 382234353Sdim BitsInit *SFBits = 383234353Sdim AllInstructions[Opcode]->TheDef->getValueAsBitsInit("SoftFail"); 384234353Sdim 385234353Sdim for (unsigned i = 0; i < BitWidth; ++i) { 386234353Sdim if (SFBits && bitFromBits(*SFBits, i) == BIT_TRUE) 387234353Sdim Insn.push_back(BIT_UNSET); 388234353Sdim else 389234353Sdim Insn.push_back(bitFromBits(Bits, i)); 390234353Sdim } 391218885Sdim } 392218885Sdim 393218885Sdim // Returns the record name. 394218885Sdim const std::string &nameWithID(unsigned Opcode) const { 395218885Sdim return AllInstructions[Opcode]->TheDef->getName(); 396218885Sdim } 397218885Sdim 398218885Sdim // Populates the field of the insn given the start position and the number of 399218885Sdim // consecutive bits to scan for. 400218885Sdim // 401218885Sdim // Returns false if there exists any uninitialized bit value in the range. 402218885Sdim // Returns true, otherwise. 403218885Sdim bool fieldFromInsn(uint64_t &Field, insn_t &Insn, unsigned StartBit, 404234353Sdim unsigned NumBits) const; 405218885Sdim 406218885Sdim /// dumpFilterArray - dumpFilterArray prints out debugging info for the given 407218885Sdim /// filter array as a series of chars. 408234353Sdim void dumpFilterArray(raw_ostream &o, 409234353Sdim const std::vector<bit_value_t> & filter) const; 410218885Sdim 411218885Sdim /// dumpStack - dumpStack traverses the filter chooser chain and calls 412218885Sdim /// dumpFilterArray on each filter chooser up to the top level one. 413234353Sdim void dumpStack(raw_ostream &o, const char *prefix) const; 414218885Sdim 415218885Sdim Filter &bestFilter() { 416218885Sdim assert(BestIndex != -1 && "BestIndex not set"); 417218885Sdim return Filters[BestIndex]; 418218885Sdim } 419218885Sdim 420218885Sdim // Called from Filter::recurse() when singleton exists. For debug purpose. 421234353Sdim void SingletonExists(unsigned Opc) const; 422218885Sdim 423234353Sdim bool PositionFiltered(unsigned i) const { 424218885Sdim return ValueSet(FilterBitValues[i]); 425218885Sdim } 426218885Sdim 427218885Sdim // Calculates the island(s) needed to decode the instruction. 428218885Sdim // This returns a lit of undecoded bits of an instructions, for example, 429218885Sdim // Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be 430218885Sdim // decoded bits in order to verify that the instruction matches the Opcode. 431218885Sdim unsigned getIslands(std::vector<unsigned> &StartBits, 432234353Sdim std::vector<unsigned> &EndBits, 433234353Sdim std::vector<uint64_t> &FieldVals, 434234353Sdim const insn_t &Insn) const; 435218885Sdim 436226633Sdim // Emits code to check the Predicates member of an instruction are true. 437226633Sdim // Returns true if predicate matches were emitted, false otherwise. 438234353Sdim bool emitPredicateMatch(raw_ostream &o, unsigned &Indentation, 439234353Sdim unsigned Opc) const; 440226633Sdim 441239462Sdim bool doesOpcodeNeedPredicate(unsigned Opc) const; 442239462Sdim unsigned getPredicateIndex(DecoderTableInfo &TableInfo, StringRef P) const; 443239462Sdim void emitPredicateTableEntry(DecoderTableInfo &TableInfo, 444239462Sdim unsigned Opc) const; 445234353Sdim 446239462Sdim void emitSoftFailTableEntry(DecoderTableInfo &TableInfo, 447239462Sdim unsigned Opc) const; 448218885Sdim 449239462Sdim // Emits table entries to decode the singleton. 450239462Sdim void emitSingletonTableEntry(DecoderTableInfo &TableInfo, 451239462Sdim unsigned Opc) const; 452239462Sdim 453218885Sdim // Emits code to decode the singleton, and then to decode the rest. 454239462Sdim void emitSingletonTableEntry(DecoderTableInfo &TableInfo, 455239462Sdim const Filter &Best) const; 456218885Sdim 457239462Sdim void emitBinaryParser(raw_ostream &o, unsigned &Indentation, 458234353Sdim const OperandInfo &OpInfo) const; 459226633Sdim 460239462Sdim void emitDecoder(raw_ostream &OS, unsigned Indentation, unsigned Opc) const; 461239462Sdim unsigned getDecoderIndex(DecoderSet &Decoders, unsigned Opc) const; 462239462Sdim 463218885Sdim // Assign a single filter and run with it. 464234353Sdim void runSingleFilter(unsigned startBit, unsigned numBit, bool mixed); 465218885Sdim 466218885Sdim // reportRegion is a helper function for filterProcessor to mark a region as 467218885Sdim // eligible for use as a filter region. 468218885Sdim void reportRegion(bitAttr_t RA, unsigned StartBit, unsigned BitIndex, 469234353Sdim bool AllowMixed); 470218885Sdim 471218885Sdim // FilterProcessor scans the well-known encoding bits of the instructions and 472218885Sdim // builds up a list of candidate filters. It chooses the best filter and 473218885Sdim // recursively descends down the decoding tree. 474218885Sdim bool filterProcessor(bool AllowMixed, bool Greedy = true); 475218885Sdim 476218885Sdim // Decides on the best configuration of filter(s) to use in order to decode 477218885Sdim // the instructions. A conflict of instructions may occur, in which case we 478218885Sdim // dump the conflict set to the standard error. 479218885Sdim void doFilter(); 480218885Sdim 481239462Sdimpublic: 482239462Sdim // emitTableEntries - Emit state machine entries to decode our share of 483239462Sdim // instructions. 484239462Sdim void emitTableEntries(DecoderTableInfo &TableInfo) const; 485218885Sdim}; 486239462Sdim} // End anonymous namespace 487218885Sdim 488218885Sdim/////////////////////////// 489218885Sdim// // 490234353Sdim// Filter Implementation // 491218885Sdim// // 492218885Sdim/////////////////////////// 493218885Sdim 494234353SdimFilter::Filter(const Filter &f) 495234353Sdim : Owner(f.Owner), StartBit(f.StartBit), NumBits(f.NumBits), Mixed(f.Mixed), 496234353Sdim FilteredInstructions(f.FilteredInstructions), 497234353Sdim VariableInstructions(f.VariableInstructions), 498234353Sdim FilterChooserMap(f.FilterChooserMap), NumFiltered(f.NumFiltered), 499234353Sdim LastOpcFiltered(f.LastOpcFiltered) { 500218885Sdim} 501218885Sdim 502218885SdimFilter::Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, 503234353Sdim bool mixed) 504234353Sdim : Owner(&owner), StartBit(startBit), NumBits(numBits), Mixed(mixed) { 505226633Sdim assert(StartBit + NumBits - 1 < Owner->BitWidth); 506218885Sdim 507218885Sdim NumFiltered = 0; 508218885Sdim LastOpcFiltered = 0; 509218885Sdim 510218885Sdim for (unsigned i = 0, e = Owner->Opcodes.size(); i != e; ++i) { 511218885Sdim insn_t Insn; 512218885Sdim 513218885Sdim // Populates the insn given the uid. 514218885Sdim Owner->insnWithID(Insn, Owner->Opcodes[i]); 515218885Sdim 516218885Sdim uint64_t Field; 517218885Sdim // Scans the segment for possibly well-specified encoding bits. 518218885Sdim bool ok = Owner->fieldFromInsn(Field, Insn, StartBit, NumBits); 519218885Sdim 520218885Sdim if (ok) { 521218885Sdim // The encoding bits are well-known. Lets add the uid of the 522218885Sdim // instruction into the bucket keyed off the constant field value. 523218885Sdim LastOpcFiltered = Owner->Opcodes[i]; 524218885Sdim FilteredInstructions[Field].push_back(LastOpcFiltered); 525218885Sdim ++NumFiltered; 526218885Sdim } else { 527234353Sdim // Some of the encoding bit(s) are unspecified. This contributes to 528218885Sdim // one additional member of "Variable" instructions. 529218885Sdim VariableInstructions.push_back(Owner->Opcodes[i]); 530218885Sdim } 531218885Sdim } 532218885Sdim 533218885Sdim assert((FilteredInstructions.size() + VariableInstructions.size() > 0) 534218885Sdim && "Filter returns no instruction categories"); 535218885Sdim} 536218885Sdim 537218885SdimFilter::~Filter() { 538234353Sdim std::map<unsigned, const FilterChooser*>::iterator filterIterator; 539218885Sdim for (filterIterator = FilterChooserMap.begin(); 540218885Sdim filterIterator != FilterChooserMap.end(); 541218885Sdim filterIterator++) { 542218885Sdim delete filterIterator->second; 543218885Sdim } 544218885Sdim} 545218885Sdim 546218885Sdim// Divides the decoding task into sub tasks and delegates them to the 547218885Sdim// inferior FilterChooser's. 548218885Sdim// 549218885Sdim// A special case arises when there's only one entry in the filtered 550218885Sdim// instructions. In order to unambiguously decode the singleton, we need to 551218885Sdim// match the remaining undecoded encoding bits against the singleton. 552218885Sdimvoid Filter::recurse() { 553218885Sdim std::map<uint64_t, std::vector<unsigned> >::const_iterator mapIterator; 554218885Sdim 555218885Sdim // Starts by inheriting our parent filter chooser's filter bit values. 556226633Sdim std::vector<bit_value_t> BitValueArray(Owner->FilterBitValues); 557218885Sdim 558218885Sdim if (VariableInstructions.size()) { 559218885Sdim // Conservatively marks each segment position as BIT_UNSET. 560239462Sdim for (unsigned bitIndex = 0; bitIndex < NumBits; ++bitIndex) 561218885Sdim BitValueArray[StartBit + bitIndex] = BIT_UNSET; 562218885Sdim 563221345Sdim // Delegates to an inferior filter chooser for further processing on this 564218885Sdim // group of instructions whose segment values are variable. 565234353Sdim FilterChooserMap.insert(std::pair<unsigned, const FilterChooser*>( 566218885Sdim (unsigned)-1, 567218885Sdim new FilterChooser(Owner->AllInstructions, 568218885Sdim VariableInstructions, 569218885Sdim Owner->Operands, 570218885Sdim BitValueArray, 571218885Sdim *Owner) 572218885Sdim )); 573218885Sdim } 574218885Sdim 575218885Sdim // No need to recurse for a singleton filtered instruction. 576239462Sdim // See also Filter::emit*(). 577218885Sdim if (getNumFiltered() == 1) { 578218885Sdim //Owner->SingletonExists(LastOpcFiltered); 579218885Sdim assert(FilterChooserMap.size() == 1); 580218885Sdim return; 581218885Sdim } 582218885Sdim 583218885Sdim // Otherwise, create sub choosers. 584218885Sdim for (mapIterator = FilteredInstructions.begin(); 585218885Sdim mapIterator != FilteredInstructions.end(); 586218885Sdim mapIterator++) { 587218885Sdim 588218885Sdim // Marks all the segment positions with either BIT_TRUE or BIT_FALSE. 589239462Sdim for (unsigned bitIndex = 0; bitIndex < NumBits; ++bitIndex) { 590218885Sdim if (mapIterator->first & (1ULL << bitIndex)) 591218885Sdim BitValueArray[StartBit + bitIndex] = BIT_TRUE; 592218885Sdim else 593218885Sdim BitValueArray[StartBit + bitIndex] = BIT_FALSE; 594218885Sdim } 595218885Sdim 596221345Sdim // Delegates to an inferior filter chooser for further processing on this 597218885Sdim // category of instructions. 598234353Sdim FilterChooserMap.insert(std::pair<unsigned, const FilterChooser*>( 599218885Sdim mapIterator->first, 600218885Sdim new FilterChooser(Owner->AllInstructions, 601218885Sdim mapIterator->second, 602218885Sdim Owner->Operands, 603218885Sdim BitValueArray, 604218885Sdim *Owner) 605218885Sdim )); 606218885Sdim } 607218885Sdim} 608218885Sdim 609239462Sdimstatic void resolveTableFixups(DecoderTable &Table, const FixupList &Fixups, 610239462Sdim uint32_t DestIdx) { 611239462Sdim // Any NumToSkip fixups in the current scope can resolve to the 612239462Sdim // current location. 613239462Sdim for (FixupList::const_reverse_iterator I = Fixups.rbegin(), 614239462Sdim E = Fixups.rend(); 615239462Sdim I != E; ++I) { 616239462Sdim // Calculate the distance from the byte following the fixup entry byte 617239462Sdim // to the destination. The Target is calculated from after the 16-bit 618239462Sdim // NumToSkip entry itself, so subtract two from the displacement here 619239462Sdim // to account for that. 620239462Sdim uint32_t FixupIdx = *I; 621239462Sdim uint32_t Delta = DestIdx - FixupIdx - 2; 622239462Sdim // Our NumToSkip entries are 16-bits. Make sure our table isn't too 623239462Sdim // big. 624239462Sdim assert(Delta < 65536U && "disassembler decoding table too large!"); 625239462Sdim Table[FixupIdx] = (uint8_t)Delta; 626239462Sdim Table[FixupIdx + 1] = (uint8_t)(Delta >> 8); 627239462Sdim } 628239462Sdim} 629218885Sdim 630239462Sdim// Emit table entries to decode instructions given a segment or segments 631239462Sdim// of bits. 632239462Sdimvoid Filter::emitTableEntry(DecoderTableInfo &TableInfo) const { 633239462Sdim TableInfo.Table.push_back(MCD::OPC_ExtractField); 634239462Sdim TableInfo.Table.push_back(StartBit); 635239462Sdim TableInfo.Table.push_back(NumBits); 636218885Sdim 637239462Sdim // A new filter entry begins a new scope for fixup resolution. 638239462Sdim TableInfo.FixupStack.push_back(FixupList()); 639218885Sdim 640234353Sdim std::map<unsigned, const FilterChooser*>::const_iterator filterIterator; 641218885Sdim 642239462Sdim DecoderTable &Table = TableInfo.Table; 643239462Sdim 644239462Sdim size_t PrevFilter = 0; 645239462Sdim bool HasFallthrough = false; 646218885Sdim for (filterIterator = FilterChooserMap.begin(); 647218885Sdim filterIterator != FilterChooserMap.end(); 648218885Sdim filterIterator++) { 649218885Sdim // Field value -1 implies a non-empty set of variable instructions. 650218885Sdim // See also recurse(). 651218885Sdim if (filterIterator->first == (unsigned)-1) { 652239462Sdim HasFallthrough = true; 653218885Sdim 654239462Sdim // Each scope should always have at least one filter value to check 655239462Sdim // for. 656239462Sdim assert(PrevFilter != 0 && "empty filter set!"); 657239462Sdim FixupList &CurScope = TableInfo.FixupStack.back(); 658239462Sdim // Resolve any NumToSkip fixups in the current scope. 659239462Sdim resolveTableFixups(Table, CurScope, Table.size()); 660239462Sdim CurScope.clear(); 661239462Sdim PrevFilter = 0; // Don't re-process the filter's fallthrough. 662239462Sdim } else { 663239462Sdim Table.push_back(MCD::OPC_FilterValue); 664239462Sdim // Encode and emit the value to filter against. 665239462Sdim uint8_t Buffer[8]; 666239462Sdim unsigned Len = encodeULEB128(filterIterator->first, Buffer); 667239462Sdim Table.insert(Table.end(), Buffer, Buffer + Len); 668239462Sdim // Reserve space for the NumToSkip entry. We'll backpatch the value 669239462Sdim // later. 670239462Sdim PrevFilter = Table.size(); 671239462Sdim Table.push_back(0); 672239462Sdim Table.push_back(0); 673239462Sdim } 674218885Sdim 675218885Sdim // We arrive at a category of instructions with the same segment value. 676218885Sdim // Now delegate to the sub filter chooser for further decodings. 677218885Sdim // The case may fallthrough, which happens if the remaining well-known 678218885Sdim // encoding bits do not match exactly. 679239462Sdim filterIterator->second->emitTableEntries(TableInfo); 680218885Sdim 681239462Sdim // Now that we've emitted the body of the handler, update the NumToSkip 682239462Sdim // of the filter itself to be able to skip forward when false. Subtract 683239462Sdim // two as to account for the width of the NumToSkip field itself. 684239462Sdim if (PrevFilter) { 685239462Sdim uint32_t NumToSkip = Table.size() - PrevFilter - 2; 686239462Sdim assert(NumToSkip < 65536U && "disassembler decoding table too large!"); 687239462Sdim Table[PrevFilter] = (uint8_t)NumToSkip; 688239462Sdim Table[PrevFilter + 1] = (uint8_t)(NumToSkip >> 8); 689239462Sdim } 690218885Sdim } 691218885Sdim 692239462Sdim // Any remaining unresolved fixups bubble up to the parent fixup scope. 693239462Sdim assert(TableInfo.FixupStack.size() > 1 && "fixup stack underflow!"); 694239462Sdim FixupScopeList::iterator Source = TableInfo.FixupStack.end() - 1; 695239462Sdim FixupScopeList::iterator Dest = Source - 1; 696239462Sdim Dest->insert(Dest->end(), Source->begin(), Source->end()); 697239462Sdim TableInfo.FixupStack.pop_back(); 698239462Sdim 699239462Sdim // If there is no fallthrough, then the final filter should get fixed 700239462Sdim // up according to the enclosing scope rather than the current position. 701239462Sdim if (!HasFallthrough) 702239462Sdim TableInfo.FixupStack.back().push_back(PrevFilter); 703218885Sdim} 704218885Sdim 705218885Sdim// Returns the number of fanout produced by the filter. More fanout implies 706218885Sdim// the filter distinguishes more categories of instructions. 707218885Sdimunsigned Filter::usefulness() const { 708218885Sdim if (VariableInstructions.size()) 709218885Sdim return FilteredInstructions.size(); 710218885Sdim else 711218885Sdim return FilteredInstructions.size() + 1; 712218885Sdim} 713218885Sdim 714218885Sdim////////////////////////////////// 715218885Sdim// // 716218885Sdim// Filterchooser Implementation // 717218885Sdim// // 718218885Sdim////////////////////////////////// 719218885Sdim 720239462Sdim// Emit the decoder state machine table. 721239462Sdimvoid FixedLenDecoderEmitter::emitTable(formatted_raw_ostream &OS, 722239462Sdim DecoderTable &Table, 723239462Sdim unsigned Indentation, 724239462Sdim unsigned BitWidth, 725239462Sdim StringRef Namespace) const { 726239462Sdim OS.indent(Indentation) << "static const uint8_t DecoderTable" << Namespace 727239462Sdim << BitWidth << "[] = {\n"; 728218885Sdim 729239462Sdim Indentation += 2; 730218885Sdim 731239462Sdim // FIXME: We may be able to use the NumToSkip values to recover 732239462Sdim // appropriate indentation levels. 733239462Sdim DecoderTable::const_iterator I = Table.begin(); 734239462Sdim DecoderTable::const_iterator E = Table.end(); 735239462Sdim while (I != E) { 736239462Sdim assert (I < E && "incomplete decode table entry!"); 737218885Sdim 738239462Sdim uint64_t Pos = I - Table.begin(); 739239462Sdim OS << "/* " << Pos << " */"; 740239462Sdim OS.PadToColumn(12); 741218885Sdim 742239462Sdim switch (*I) { 743239462Sdim default: 744243830Sdim PrintFatalError("invalid decode table opcode"); 745239462Sdim case MCD::OPC_ExtractField: { 746239462Sdim ++I; 747239462Sdim unsigned Start = *I++; 748239462Sdim unsigned Len = *I++; 749239462Sdim OS.indent(Indentation) << "MCD::OPC_ExtractField, " << Start << ", " 750239462Sdim << Len << ", // Inst{"; 751239462Sdim if (Len > 1) 752239462Sdim OS << (Start + Len - 1) << "-"; 753239462Sdim OS << Start << "} ...\n"; 754239462Sdim break; 755239462Sdim } 756239462Sdim case MCD::OPC_FilterValue: { 757239462Sdim ++I; 758239462Sdim OS.indent(Indentation) << "MCD::OPC_FilterValue, "; 759239462Sdim // The filter value is ULEB128 encoded. 760239462Sdim while (*I >= 128) 761239462Sdim OS << utostr(*I++) << ", "; 762239462Sdim OS << utostr(*I++) << ", "; 763239462Sdim 764239462Sdim // 16-bit numtoskip value. 765239462Sdim uint8_t Byte = *I++; 766239462Sdim uint32_t NumToSkip = Byte; 767239462Sdim OS << utostr(Byte) << ", "; 768239462Sdim Byte = *I++; 769239462Sdim OS << utostr(Byte) << ", "; 770239462Sdim NumToSkip |= Byte << 8; 771239462Sdim OS << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; 772239462Sdim break; 773239462Sdim } 774239462Sdim case MCD::OPC_CheckField: { 775239462Sdim ++I; 776239462Sdim unsigned Start = *I++; 777239462Sdim unsigned Len = *I++; 778239462Sdim OS.indent(Indentation) << "MCD::OPC_CheckField, " << Start << ", " 779239462Sdim << Len << ", ";// << Val << ", " << NumToSkip << ",\n"; 780239462Sdim // ULEB128 encoded field value. 781239462Sdim for (; *I >= 128; ++I) 782239462Sdim OS << utostr(*I) << ", "; 783239462Sdim OS << utostr(*I++) << ", "; 784239462Sdim // 16-bit numtoskip value. 785239462Sdim uint8_t Byte = *I++; 786239462Sdim uint32_t NumToSkip = Byte; 787239462Sdim OS << utostr(Byte) << ", "; 788239462Sdim Byte = *I++; 789239462Sdim OS << utostr(Byte) << ", "; 790239462Sdim NumToSkip |= Byte << 8; 791239462Sdim OS << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; 792239462Sdim break; 793239462Sdim } 794239462Sdim case MCD::OPC_CheckPredicate: { 795239462Sdim ++I; 796239462Sdim OS.indent(Indentation) << "MCD::OPC_CheckPredicate, "; 797239462Sdim for (; *I >= 128; ++I) 798239462Sdim OS << utostr(*I) << ", "; 799239462Sdim OS << utostr(*I++) << ", "; 800239462Sdim 801239462Sdim // 16-bit numtoskip value. 802239462Sdim uint8_t Byte = *I++; 803239462Sdim uint32_t NumToSkip = Byte; 804239462Sdim OS << utostr(Byte) << ", "; 805239462Sdim Byte = *I++; 806239462Sdim OS << utostr(Byte) << ", "; 807239462Sdim NumToSkip |= Byte << 8; 808239462Sdim OS << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; 809239462Sdim break; 810239462Sdim } 811239462Sdim case MCD::OPC_Decode: { 812239462Sdim ++I; 813239462Sdim // Extract the ULEB128 encoded Opcode to a buffer. 814239462Sdim uint8_t Buffer[8], *p = Buffer; 815239462Sdim while ((*p++ = *I++) >= 128) 816239462Sdim assert((p - Buffer) <= (ptrdiff_t)sizeof(Buffer) 817239462Sdim && "ULEB128 value too large!"); 818239462Sdim // Decode the Opcode value. 819239462Sdim unsigned Opc = decodeULEB128(Buffer); 820239462Sdim OS.indent(Indentation) << "MCD::OPC_Decode, "; 821239462Sdim for (p = Buffer; *p >= 128; ++p) 822239462Sdim OS << utostr(*p) << ", "; 823239462Sdim OS << utostr(*p) << ", "; 824239462Sdim 825239462Sdim // Decoder index. 826239462Sdim for (; *I >= 128; ++I) 827239462Sdim OS << utostr(*I) << ", "; 828239462Sdim OS << utostr(*I++) << ", "; 829239462Sdim 830239462Sdim OS << "// Opcode: " 831239462Sdim << NumberedInstructions->at(Opc)->TheDef->getName() << "\n"; 832239462Sdim break; 833239462Sdim } 834239462Sdim case MCD::OPC_SoftFail: { 835239462Sdim ++I; 836239462Sdim OS.indent(Indentation) << "MCD::OPC_SoftFail"; 837239462Sdim // Positive mask 838239462Sdim uint64_t Value = 0; 839239462Sdim unsigned Shift = 0; 840239462Sdim do { 841239462Sdim OS << ", " << utostr(*I); 842239462Sdim Value += (*I & 0x7f) << Shift; 843239462Sdim Shift += 7; 844239462Sdim } while (*I++ >= 128); 845239462Sdim if (Value > 127) 846239462Sdim OS << " /* 0x" << utohexstr(Value) << " */"; 847239462Sdim // Negative mask 848239462Sdim Value = 0; 849239462Sdim Shift = 0; 850239462Sdim do { 851239462Sdim OS << ", " << utostr(*I); 852239462Sdim Value += (*I & 0x7f) << Shift; 853239462Sdim Shift += 7; 854239462Sdim } while (*I++ >= 128); 855239462Sdim if (Value > 127) 856239462Sdim OS << " /* 0x" << utohexstr(Value) << " */"; 857239462Sdim OS << ",\n"; 858239462Sdim break; 859239462Sdim } 860239462Sdim case MCD::OPC_Fail: { 861239462Sdim ++I; 862239462Sdim OS.indent(Indentation) << "MCD::OPC_Fail,\n"; 863239462Sdim break; 864239462Sdim } 865239462Sdim } 866239462Sdim } 867239462Sdim OS.indent(Indentation) << "0\n"; 868239462Sdim 869239462Sdim Indentation -= 2; 870239462Sdim 871239462Sdim OS.indent(Indentation) << "};\n\n"; 872218885Sdim} 873218885Sdim 874239462Sdimvoid FixedLenDecoderEmitter:: 875239462SdimemitPredicateFunction(formatted_raw_ostream &OS, PredicateSet &Predicates, 876239462Sdim unsigned Indentation) const { 877239462Sdim // The predicate function is just a big switch statement based on the 878239462Sdim // input predicate index. 879239462Sdim OS.indent(Indentation) << "static bool checkDecoderPredicate(unsigned Idx, " 880239462Sdim << "uint64_t Bits) {\n"; 881239462Sdim Indentation += 2; 882263508Sdim if (!Predicates.empty()) { 883263508Sdim OS.indent(Indentation) << "switch (Idx) {\n"; 884263508Sdim OS.indent(Indentation) << "default: llvm_unreachable(\"Invalid index!\");\n"; 885263508Sdim unsigned Index = 0; 886263508Sdim for (PredicateSet::const_iterator I = Predicates.begin(), E = Predicates.end(); 887263508Sdim I != E; ++I, ++Index) { 888263508Sdim OS.indent(Indentation) << "case " << Index << ":\n"; 889263508Sdim OS.indent(Indentation+2) << "return (" << *I << ");\n"; 890263508Sdim } 891263508Sdim OS.indent(Indentation) << "}\n"; 892263508Sdim } else { 893263508Sdim // No case statement to emit 894263508Sdim OS.indent(Indentation) << "llvm_unreachable(\"Invalid index!\");\n"; 895239462Sdim } 896239462Sdim Indentation -= 2; 897239462Sdim OS.indent(Indentation) << "}\n\n"; 898239462Sdim} 899239462Sdim 900239462Sdimvoid FixedLenDecoderEmitter:: 901239462SdimemitDecoderFunction(formatted_raw_ostream &OS, DecoderSet &Decoders, 902239462Sdim unsigned Indentation) const { 903239462Sdim // The decoder function is just a big switch statement based on the 904239462Sdim // input decoder index. 905239462Sdim OS.indent(Indentation) << "template<typename InsnType>\n"; 906239462Sdim OS.indent(Indentation) << "static DecodeStatus decodeToMCInst(DecodeStatus S," 907239462Sdim << " unsigned Idx, InsnType insn, MCInst &MI,\n"; 908239462Sdim OS.indent(Indentation) << " uint64_t " 909239462Sdim << "Address, const void *Decoder) {\n"; 910239462Sdim Indentation += 2; 911239462Sdim OS.indent(Indentation) << "InsnType tmp;\n"; 912239462Sdim OS.indent(Indentation) << "switch (Idx) {\n"; 913239462Sdim OS.indent(Indentation) << "default: llvm_unreachable(\"Invalid index!\");\n"; 914239462Sdim unsigned Index = 0; 915239462Sdim for (DecoderSet::const_iterator I = Decoders.begin(), E = Decoders.end(); 916239462Sdim I != E; ++I, ++Index) { 917239462Sdim OS.indent(Indentation) << "case " << Index << ":\n"; 918239462Sdim OS << *I; 919239462Sdim OS.indent(Indentation+2) << "return S;\n"; 920239462Sdim } 921239462Sdim OS.indent(Indentation) << "}\n"; 922239462Sdim Indentation -= 2; 923239462Sdim OS.indent(Indentation) << "}\n\n"; 924239462Sdim} 925239462Sdim 926218885Sdim// Populates the field of the insn given the start position and the number of 927218885Sdim// consecutive bits to scan for. 928218885Sdim// 929218885Sdim// Returns false if and on the first uninitialized bit value encountered. 930218885Sdim// Returns true, otherwise. 931218885Sdimbool FilterChooser::fieldFromInsn(uint64_t &Field, insn_t &Insn, 932234353Sdim unsigned StartBit, unsigned NumBits) const { 933218885Sdim Field = 0; 934218885Sdim 935218885Sdim for (unsigned i = 0; i < NumBits; ++i) { 936218885Sdim if (Insn[StartBit + i] == BIT_UNSET) 937218885Sdim return false; 938218885Sdim 939218885Sdim if (Insn[StartBit + i] == BIT_TRUE) 940218885Sdim Field = Field | (1ULL << i); 941218885Sdim } 942218885Sdim 943218885Sdim return true; 944218885Sdim} 945218885Sdim 946218885Sdim/// dumpFilterArray - dumpFilterArray prints out debugging info for the given 947218885Sdim/// filter array as a series of chars. 948218885Sdimvoid FilterChooser::dumpFilterArray(raw_ostream &o, 949234353Sdim const std::vector<bit_value_t> &filter) const { 950239462Sdim for (unsigned bitIndex = BitWidth; bitIndex > 0; bitIndex--) { 951218885Sdim switch (filter[bitIndex - 1]) { 952218885Sdim case BIT_UNFILTERED: 953218885Sdim o << "."; 954218885Sdim break; 955218885Sdim case BIT_UNSET: 956218885Sdim o << "_"; 957218885Sdim break; 958218885Sdim case BIT_TRUE: 959218885Sdim o << "1"; 960218885Sdim break; 961218885Sdim case BIT_FALSE: 962218885Sdim o << "0"; 963218885Sdim break; 964218885Sdim } 965218885Sdim } 966218885Sdim} 967218885Sdim 968218885Sdim/// dumpStack - dumpStack traverses the filter chooser chain and calls 969218885Sdim/// dumpFilterArray on each filter chooser up to the top level one. 970234353Sdimvoid FilterChooser::dumpStack(raw_ostream &o, const char *prefix) const { 971234353Sdim const FilterChooser *current = this; 972218885Sdim 973218885Sdim while (current) { 974218885Sdim o << prefix; 975218885Sdim dumpFilterArray(o, current->FilterBitValues); 976218885Sdim o << '\n'; 977218885Sdim current = current->Parent; 978218885Sdim } 979218885Sdim} 980218885Sdim 981218885Sdim// Called from Filter::recurse() when singleton exists. For debug purpose. 982234353Sdimvoid FilterChooser::SingletonExists(unsigned Opc) const { 983218885Sdim insn_t Insn0; 984218885Sdim insnWithID(Insn0, Opc); 985218885Sdim 986218885Sdim errs() << "Singleton exists: " << nameWithID(Opc) 987218885Sdim << " with its decoding dominating "; 988218885Sdim for (unsigned i = 0; i < Opcodes.size(); ++i) { 989218885Sdim if (Opcodes[i] == Opc) continue; 990218885Sdim errs() << nameWithID(Opcodes[i]) << ' '; 991218885Sdim } 992218885Sdim errs() << '\n'; 993218885Sdim 994218885Sdim dumpStack(errs(), "\t\t"); 995234353Sdim for (unsigned i = 0; i < Opcodes.size(); ++i) { 996218885Sdim const std::string &Name = nameWithID(Opcodes[i]); 997218885Sdim 998218885Sdim errs() << '\t' << Name << " "; 999218885Sdim dumpBits(errs(), 1000218885Sdim getBitsField(*AllInstructions[Opcodes[i]]->TheDef, "Inst")); 1001218885Sdim errs() << '\n'; 1002218885Sdim } 1003218885Sdim} 1004218885Sdim 1005218885Sdim// Calculates the island(s) needed to decode the instruction. 1006218885Sdim// This returns a list of undecoded bits of an instructions, for example, 1007218885Sdim// Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be 1008218885Sdim// decoded bits in order to verify that the instruction matches the Opcode. 1009218885Sdimunsigned FilterChooser::getIslands(std::vector<unsigned> &StartBits, 1010234353Sdim std::vector<unsigned> &EndBits, 1011234353Sdim std::vector<uint64_t> &FieldVals, 1012234353Sdim const insn_t &Insn) const { 1013218885Sdim unsigned Num, BitNo; 1014218885Sdim Num = BitNo = 0; 1015218885Sdim 1016218885Sdim uint64_t FieldVal = 0; 1017218885Sdim 1018218885Sdim // 0: Init 1019218885Sdim // 1: Water (the bit value does not affect decoding) 1020218885Sdim // 2: Island (well-known bit value needed for decoding) 1021218885Sdim int State = 0; 1022218885Sdim int Val = -1; 1023218885Sdim 1024226633Sdim for (unsigned i = 0; i < BitWidth; ++i) { 1025218885Sdim Val = Value(Insn[i]); 1026218885Sdim bool Filtered = PositionFiltered(i); 1027218885Sdim switch (State) { 1028234353Sdim default: llvm_unreachable("Unreachable code!"); 1029218885Sdim case 0: 1030218885Sdim case 1: 1031218885Sdim if (Filtered || Val == -1) 1032218885Sdim State = 1; // Still in Water 1033218885Sdim else { 1034218885Sdim State = 2; // Into the Island 1035218885Sdim BitNo = 0; 1036218885Sdim StartBits.push_back(i); 1037218885Sdim FieldVal = Val; 1038218885Sdim } 1039218885Sdim break; 1040218885Sdim case 2: 1041218885Sdim if (Filtered || Val == -1) { 1042218885Sdim State = 1; // Into the Water 1043218885Sdim EndBits.push_back(i - 1); 1044218885Sdim FieldVals.push_back(FieldVal); 1045218885Sdim ++Num; 1046218885Sdim } else { 1047218885Sdim State = 2; // Still in Island 1048218885Sdim ++BitNo; 1049218885Sdim FieldVal = FieldVal | Val << BitNo; 1050218885Sdim } 1051218885Sdim break; 1052218885Sdim } 1053218885Sdim } 1054218885Sdim // If we are still in Island after the loop, do some housekeeping. 1055218885Sdim if (State == 2) { 1056226633Sdim EndBits.push_back(BitWidth - 1); 1057218885Sdim FieldVals.push_back(FieldVal); 1058218885Sdim ++Num; 1059218885Sdim } 1060218885Sdim 1061218885Sdim assert(StartBits.size() == Num && EndBits.size() == Num && 1062218885Sdim FieldVals.size() == Num); 1063218885Sdim return Num; 1064218885Sdim} 1065218885Sdim 1066226633Sdimvoid FilterChooser::emitBinaryParser(raw_ostream &o, unsigned &Indentation, 1067234353Sdim const OperandInfo &OpInfo) const { 1068234353Sdim const std::string &Decoder = OpInfo.Decoder; 1069226633Sdim 1070226633Sdim if (OpInfo.numFields() == 1) { 1071234353Sdim OperandInfo::const_iterator OI = OpInfo.begin(); 1072239462Sdim o.indent(Indentation) << "tmp = fieldFromInstruction" 1073239462Sdim << "(insn, " << OI->Base << ", " << OI->Width 1074239462Sdim << ");\n"; 1075226633Sdim } else { 1076239462Sdim o.indent(Indentation) << "tmp = 0;\n"; 1077234353Sdim for (OperandInfo::const_iterator OI = OpInfo.begin(), OE = OpInfo.end(); 1078226633Sdim OI != OE; ++OI) { 1079239462Sdim o.indent(Indentation) << "tmp |= (fieldFromInstruction" 1080226633Sdim << "(insn, " << OI->Base << ", " << OI->Width 1081226633Sdim << ") << " << OI->Offset << ");\n"; 1082226633Sdim } 1083226633Sdim } 1084226633Sdim 1085226633Sdim if (Decoder != "") 1086239462Sdim o.indent(Indentation) << Emitter->GuardPrefix << Decoder 1087234353Sdim << "(MI, tmp, Address, Decoder)" 1088234353Sdim << Emitter->GuardPostfix << "\n"; 1089226633Sdim else 1090239462Sdim o.indent(Indentation) << "MI.addOperand(MCOperand::CreateImm(tmp));\n"; 1091226633Sdim 1092226633Sdim} 1093226633Sdim 1094239462Sdimvoid FilterChooser::emitDecoder(raw_ostream &OS, unsigned Indentation, 1095239462Sdim unsigned Opc) const { 1096239462Sdim std::map<unsigned, std::vector<OperandInfo> >::const_iterator OpIter = 1097239462Sdim Operands.find(Opc); 1098239462Sdim const std::vector<OperandInfo>& InsnOperands = OpIter->second; 1099239462Sdim for (std::vector<OperandInfo>::const_iterator 1100239462Sdim I = InsnOperands.begin(), E = InsnOperands.end(); I != E; ++I) { 1101239462Sdim // If a custom instruction decoder was specified, use that. 1102239462Sdim if (I->numFields() == 0 && I->Decoder.size()) { 1103239462Sdim OS.indent(Indentation) << Emitter->GuardPrefix << I->Decoder 1104239462Sdim << "(MI, insn, Address, Decoder)" 1105239462Sdim << Emitter->GuardPostfix << "\n"; 1106239462Sdim break; 1107239462Sdim } 1108239462Sdim 1109239462Sdim emitBinaryParser(OS, Indentation, *I); 1110239462Sdim } 1111239462Sdim} 1112239462Sdim 1113239462Sdimunsigned FilterChooser::getDecoderIndex(DecoderSet &Decoders, 1114239462Sdim unsigned Opc) const { 1115239462Sdim // Build up the predicate string. 1116239462Sdim SmallString<256> Decoder; 1117239462Sdim // FIXME: emitDecoder() function can take a buffer directly rather than 1118239462Sdim // a stream. 1119239462Sdim raw_svector_ostream S(Decoder); 1120239462Sdim unsigned I = 4; 1121239462Sdim emitDecoder(S, I, Opc); 1122239462Sdim S.flush(); 1123239462Sdim 1124239462Sdim // Using the full decoder string as the key value here is a bit 1125239462Sdim // heavyweight, but is effective. If the string comparisons become a 1126239462Sdim // performance concern, we can implement a mangling of the predicate 1127239462Sdim // data easilly enough with a map back to the actual string. That's 1128239462Sdim // overkill for now, though. 1129239462Sdim 1130239462Sdim // Make sure the predicate is in the table. 1131239462Sdim Decoders.insert(Decoder.str()); 1132239462Sdim // Now figure out the index for when we write out the table. 1133239462Sdim DecoderSet::const_iterator P = std::find(Decoders.begin(), 1134239462Sdim Decoders.end(), 1135239462Sdim Decoder.str()); 1136239462Sdim return (unsigned)(P - Decoders.begin()); 1137239462Sdim} 1138239462Sdim 1139226633Sdimstatic void emitSinglePredicateMatch(raw_ostream &o, StringRef str, 1140234353Sdim const std::string &PredicateNamespace) { 1141226633Sdim if (str[0] == '!') 1142226633Sdim o << "!(Bits & " << PredicateNamespace << "::" 1143226633Sdim << str.slice(1,str.size()) << ")"; 1144226633Sdim else 1145226633Sdim o << "(Bits & " << PredicateNamespace << "::" << str << ")"; 1146226633Sdim} 1147226633Sdim 1148226633Sdimbool FilterChooser::emitPredicateMatch(raw_ostream &o, unsigned &Indentation, 1149234353Sdim unsigned Opc) const { 1150234353Sdim ListInit *Predicates = 1151234353Sdim AllInstructions[Opc]->TheDef->getValueAsListInit("Predicates"); 1152226633Sdim for (unsigned i = 0; i < Predicates->getSize(); ++i) { 1153226633Sdim Record *Pred = Predicates->getElementAsRecord(i); 1154226633Sdim if (!Pred->getValue("AssemblerMatcherPredicate")) 1155226633Sdim continue; 1156226633Sdim 1157226633Sdim std::string P = Pred->getValueAsString("AssemblerCondString"); 1158226633Sdim 1159226633Sdim if (!P.length()) 1160226633Sdim continue; 1161226633Sdim 1162226633Sdim if (i != 0) 1163226633Sdim o << " && "; 1164226633Sdim 1165226633Sdim StringRef SR(P); 1166226633Sdim std::pair<StringRef, StringRef> pairs = SR.split(','); 1167226633Sdim while (pairs.second.size()) { 1168226633Sdim emitSinglePredicateMatch(o, pairs.first, Emitter->PredicateNamespace); 1169226633Sdim o << " && "; 1170226633Sdim pairs = pairs.second.split(','); 1171226633Sdim } 1172226633Sdim emitSinglePredicateMatch(o, pairs.first, Emitter->PredicateNamespace); 1173226633Sdim } 1174226633Sdim return Predicates->getSize() > 0; 1175226633Sdim} 1176226633Sdim 1177239462Sdimbool FilterChooser::doesOpcodeNeedPredicate(unsigned Opc) const { 1178239462Sdim ListInit *Predicates = 1179239462Sdim AllInstructions[Opc]->TheDef->getValueAsListInit("Predicates"); 1180239462Sdim for (unsigned i = 0; i < Predicates->getSize(); ++i) { 1181239462Sdim Record *Pred = Predicates->getElementAsRecord(i); 1182239462Sdim if (!Pred->getValue("AssemblerMatcherPredicate")) 1183239462Sdim continue; 1184239462Sdim 1185239462Sdim std::string P = Pred->getValueAsString("AssemblerCondString"); 1186239462Sdim 1187239462Sdim if (!P.length()) 1188239462Sdim continue; 1189239462Sdim 1190239462Sdim return true; 1191239462Sdim } 1192239462Sdim return false; 1193239462Sdim} 1194239462Sdim 1195239462Sdimunsigned FilterChooser::getPredicateIndex(DecoderTableInfo &TableInfo, 1196239462Sdim StringRef Predicate) const { 1197239462Sdim // Using the full predicate string as the key value here is a bit 1198239462Sdim // heavyweight, but is effective. If the string comparisons become a 1199239462Sdim // performance concern, we can implement a mangling of the predicate 1200239462Sdim // data easilly enough with a map back to the actual string. That's 1201239462Sdim // overkill for now, though. 1202239462Sdim 1203239462Sdim // Make sure the predicate is in the table. 1204239462Sdim TableInfo.Predicates.insert(Predicate.str()); 1205239462Sdim // Now figure out the index for when we write out the table. 1206239462Sdim PredicateSet::const_iterator P = std::find(TableInfo.Predicates.begin(), 1207239462Sdim TableInfo.Predicates.end(), 1208239462Sdim Predicate.str()); 1209239462Sdim return (unsigned)(P - TableInfo.Predicates.begin()); 1210239462Sdim} 1211239462Sdim 1212239462Sdimvoid FilterChooser::emitPredicateTableEntry(DecoderTableInfo &TableInfo, 1213239462Sdim unsigned Opc) const { 1214239462Sdim if (!doesOpcodeNeedPredicate(Opc)) 1215239462Sdim return; 1216239462Sdim 1217239462Sdim // Build up the predicate string. 1218239462Sdim SmallString<256> Predicate; 1219239462Sdim // FIXME: emitPredicateMatch() functions can take a buffer directly rather 1220239462Sdim // than a stream. 1221239462Sdim raw_svector_ostream PS(Predicate); 1222239462Sdim unsigned I = 0; 1223239462Sdim emitPredicateMatch(PS, I, Opc); 1224239462Sdim 1225239462Sdim // Figure out the index into the predicate table for the predicate just 1226239462Sdim // computed. 1227239462Sdim unsigned PIdx = getPredicateIndex(TableInfo, PS.str()); 1228239462Sdim SmallString<16> PBytes; 1229239462Sdim raw_svector_ostream S(PBytes); 1230239462Sdim encodeULEB128(PIdx, S); 1231239462Sdim S.flush(); 1232239462Sdim 1233239462Sdim TableInfo.Table.push_back(MCD::OPC_CheckPredicate); 1234239462Sdim // Predicate index 1235239462Sdim for (unsigned i = 0, e = PBytes.size(); i != e; ++i) 1236239462Sdim TableInfo.Table.push_back(PBytes[i]); 1237239462Sdim // Push location for NumToSkip backpatching. 1238239462Sdim TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); 1239239462Sdim TableInfo.Table.push_back(0); 1240239462Sdim TableInfo.Table.push_back(0); 1241239462Sdim} 1242239462Sdim 1243239462Sdimvoid FilterChooser::emitSoftFailTableEntry(DecoderTableInfo &TableInfo, 1244239462Sdim unsigned Opc) const { 1245234353Sdim BitsInit *SFBits = 1246234353Sdim AllInstructions[Opc]->TheDef->getValueAsBitsInit("SoftFail"); 1247234353Sdim if (!SFBits) return; 1248234353Sdim BitsInit *InstBits = AllInstructions[Opc]->TheDef->getValueAsBitsInit("Inst"); 1249234353Sdim 1250234353Sdim APInt PositiveMask(BitWidth, 0ULL); 1251234353Sdim APInt NegativeMask(BitWidth, 0ULL); 1252234353Sdim for (unsigned i = 0; i < BitWidth; ++i) { 1253234353Sdim bit_value_t B = bitFromBits(*SFBits, i); 1254234353Sdim bit_value_t IB = bitFromBits(*InstBits, i); 1255234353Sdim 1256234353Sdim if (B != BIT_TRUE) continue; 1257234353Sdim 1258234353Sdim switch (IB) { 1259234353Sdim case BIT_FALSE: 1260234353Sdim // The bit is meant to be false, so emit a check to see if it is true. 1261234353Sdim PositiveMask.setBit(i); 1262234353Sdim break; 1263234353Sdim case BIT_TRUE: 1264234353Sdim // The bit is meant to be true, so emit a check to see if it is false. 1265234353Sdim NegativeMask.setBit(i); 1266234353Sdim break; 1267234353Sdim default: 1268234353Sdim // The bit is not set; this must be an error! 1269234353Sdim StringRef Name = AllInstructions[Opc]->TheDef->getName(); 1270239462Sdim errs() << "SoftFail Conflict: bit SoftFail{" << i << "} in " << Name 1271239462Sdim << " is set but Inst{" << i << "} is unset!\n" 1272234353Sdim << " - You can only mark a bit as SoftFail if it is fully defined" 1273234353Sdim << " (1/0 - not '?') in Inst\n"; 1274239462Sdim return; 1275234353Sdim } 1276234353Sdim } 1277234353Sdim 1278234353Sdim bool NeedPositiveMask = PositiveMask.getBoolValue(); 1279234353Sdim bool NeedNegativeMask = NegativeMask.getBoolValue(); 1280234353Sdim 1281234353Sdim if (!NeedPositiveMask && !NeedNegativeMask) 1282234353Sdim return; 1283234353Sdim 1284239462Sdim TableInfo.Table.push_back(MCD::OPC_SoftFail); 1285234353Sdim 1286239462Sdim SmallString<16> MaskBytes; 1287239462Sdim raw_svector_ostream S(MaskBytes); 1288239462Sdim if (NeedPositiveMask) { 1289239462Sdim encodeULEB128(PositiveMask.getZExtValue(), S); 1290239462Sdim S.flush(); 1291239462Sdim for (unsigned i = 0, e = MaskBytes.size(); i != e; ++i) 1292239462Sdim TableInfo.Table.push_back(MaskBytes[i]); 1293239462Sdim } else 1294239462Sdim TableInfo.Table.push_back(0); 1295239462Sdim if (NeedNegativeMask) { 1296239462Sdim MaskBytes.clear(); 1297239462Sdim S.resync(); 1298239462Sdim encodeULEB128(NegativeMask.getZExtValue(), S); 1299239462Sdim S.flush(); 1300239462Sdim for (unsigned i = 0, e = MaskBytes.size(); i != e; ++i) 1301239462Sdim TableInfo.Table.push_back(MaskBytes[i]); 1302239462Sdim } else 1303239462Sdim TableInfo.Table.push_back(0); 1304234353Sdim} 1305234353Sdim 1306239462Sdim// Emits table entries to decode the singleton. 1307239462Sdimvoid FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo, 1308239462Sdim unsigned Opc) const { 1309218885Sdim std::vector<unsigned> StartBits; 1310218885Sdim std::vector<unsigned> EndBits; 1311218885Sdim std::vector<uint64_t> FieldVals; 1312218885Sdim insn_t Insn; 1313218885Sdim insnWithID(Insn, Opc); 1314218885Sdim 1315218885Sdim // Look for islands of undecoded bits of the singleton. 1316218885Sdim getIslands(StartBits, EndBits, FieldVals, Insn); 1317218885Sdim 1318218885Sdim unsigned Size = StartBits.size(); 1319218885Sdim 1320239462Sdim // Emit the predicate table entry if one is needed. 1321239462Sdim emitPredicateTableEntry(TableInfo, Opc); 1322218885Sdim 1323239462Sdim // Check any additional encoding fields needed. 1324239462Sdim for (unsigned I = Size; I != 0; --I) { 1325239462Sdim unsigned NumBits = EndBits[I-1] - StartBits[I-1] + 1; 1326239462Sdim TableInfo.Table.push_back(MCD::OPC_CheckField); 1327239462Sdim TableInfo.Table.push_back(StartBits[I-1]); 1328239462Sdim TableInfo.Table.push_back(NumBits); 1329239462Sdim uint8_t Buffer[8], *p; 1330239462Sdim encodeULEB128(FieldVals[I-1], Buffer); 1331239462Sdim for (p = Buffer; *p >= 128 ; ++p) 1332239462Sdim TableInfo.Table.push_back(*p); 1333239462Sdim TableInfo.Table.push_back(*p); 1334239462Sdim // Push location for NumToSkip backpatching. 1335239462Sdim TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); 1336239462Sdim // The fixup is always 16-bits, so go ahead and allocate the space 1337239462Sdim // in the table so all our relative position calculations work OK even 1338239462Sdim // before we fully resolve the real value here. 1339239462Sdim TableInfo.Table.push_back(0); 1340239462Sdim TableInfo.Table.push_back(0); 1341218885Sdim } 1342218885Sdim 1343239462Sdim // Check for soft failure of the match. 1344239462Sdim emitSoftFailTableEntry(TableInfo, Opc); 1345218885Sdim 1346239462Sdim TableInfo.Table.push_back(MCD::OPC_Decode); 1347239462Sdim uint8_t Buffer[8], *p; 1348239462Sdim encodeULEB128(Opc, Buffer); 1349239462Sdim for (p = Buffer; *p >= 128 ; ++p) 1350239462Sdim TableInfo.Table.push_back(*p); 1351239462Sdim TableInfo.Table.push_back(*p); 1352218885Sdim 1353239462Sdim unsigned DIdx = getDecoderIndex(TableInfo.Decoders, Opc); 1354239462Sdim SmallString<16> Bytes; 1355239462Sdim raw_svector_ostream S(Bytes); 1356239462Sdim encodeULEB128(DIdx, S); 1357239462Sdim S.flush(); 1358218885Sdim 1359239462Sdim // Decoder index 1360239462Sdim for (unsigned i = 0, e = Bytes.size(); i != e; ++i) 1361239462Sdim TableInfo.Table.push_back(Bytes[i]); 1362218885Sdim} 1363218885Sdim 1364239462Sdim// Emits table entries to decode the singleton, and then to decode the rest. 1365239462Sdimvoid FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo, 1366239462Sdim const Filter &Best) const { 1367218885Sdim unsigned Opc = Best.getSingletonOpc(); 1368218885Sdim 1369239462Sdim // complex singletons need predicate checks from the first singleton 1370239462Sdim // to refer forward to the variable filterchooser that follows. 1371239462Sdim TableInfo.FixupStack.push_back(FixupList()); 1372218885Sdim 1373239462Sdim emitSingletonTableEntry(TableInfo, Opc); 1374218885Sdim 1375239462Sdim resolveTableFixups(TableInfo.Table, TableInfo.FixupStack.back(), 1376239462Sdim TableInfo.Table.size()); 1377239462Sdim TableInfo.FixupStack.pop_back(); 1378239462Sdim 1379239462Sdim Best.getVariableFC().emitTableEntries(TableInfo); 1380218885Sdim} 1381218885Sdim 1382239462Sdim 1383218885Sdim// Assign a single filter and run with it. Top level API client can initialize 1384218885Sdim// with a single filter to start the filtering process. 1385234353Sdimvoid FilterChooser::runSingleFilter(unsigned startBit, unsigned numBit, 1386234353Sdim bool mixed) { 1387218885Sdim Filters.clear(); 1388218885Sdim Filter F(*this, startBit, numBit, true); 1389218885Sdim Filters.push_back(F); 1390218885Sdim BestIndex = 0; // Sole Filter instance to choose from. 1391218885Sdim bestFilter().recurse(); 1392218885Sdim} 1393218885Sdim 1394218885Sdim// reportRegion is a helper function for filterProcessor to mark a region as 1395218885Sdim// eligible for use as a filter region. 1396218885Sdimvoid FilterChooser::reportRegion(bitAttr_t RA, unsigned StartBit, 1397234353Sdim unsigned BitIndex, bool AllowMixed) { 1398218885Sdim if (RA == ATTR_MIXED && AllowMixed) 1399218885Sdim Filters.push_back(Filter(*this, StartBit, BitIndex - StartBit, true)); 1400218885Sdim else if (RA == ATTR_ALL_SET && !AllowMixed) 1401218885Sdim Filters.push_back(Filter(*this, StartBit, BitIndex - StartBit, false)); 1402218885Sdim} 1403218885Sdim 1404218885Sdim// FilterProcessor scans the well-known encoding bits of the instructions and 1405218885Sdim// builds up a list of candidate filters. It chooses the best filter and 1406218885Sdim// recursively descends down the decoding tree. 1407218885Sdimbool FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { 1408218885Sdim Filters.clear(); 1409218885Sdim BestIndex = -1; 1410218885Sdim unsigned numInstructions = Opcodes.size(); 1411218885Sdim 1412218885Sdim assert(numInstructions && "Filter created with no instructions"); 1413218885Sdim 1414218885Sdim // No further filtering is necessary. 1415218885Sdim if (numInstructions == 1) 1416218885Sdim return true; 1417218885Sdim 1418218885Sdim // Heuristics. See also doFilter()'s "Heuristics" comment when num of 1419218885Sdim // instructions is 3. 1420218885Sdim if (AllowMixed && !Greedy) { 1421218885Sdim assert(numInstructions == 3); 1422218885Sdim 1423218885Sdim for (unsigned i = 0; i < Opcodes.size(); ++i) { 1424218885Sdim std::vector<unsigned> StartBits; 1425218885Sdim std::vector<unsigned> EndBits; 1426218885Sdim std::vector<uint64_t> FieldVals; 1427218885Sdim insn_t Insn; 1428218885Sdim 1429218885Sdim insnWithID(Insn, Opcodes[i]); 1430218885Sdim 1431218885Sdim // Look for islands of undecoded bits of any instruction. 1432218885Sdim if (getIslands(StartBits, EndBits, FieldVals, Insn) > 0) { 1433218885Sdim // Found an instruction with island(s). Now just assign a filter. 1434234353Sdim runSingleFilter(StartBits[0], EndBits[0] - StartBits[0] + 1, true); 1435218885Sdim return true; 1436218885Sdim } 1437218885Sdim } 1438218885Sdim } 1439218885Sdim 1440239462Sdim unsigned BitIndex; 1441218885Sdim 1442218885Sdim // We maintain BIT_WIDTH copies of the bitAttrs automaton. 1443218885Sdim // The automaton consumes the corresponding bit from each 1444218885Sdim // instruction. 1445218885Sdim // 1446218885Sdim // Input symbols: 0, 1, and _ (unset). 1447218885Sdim // States: NONE, FILTERED, ALL_SET, ALL_UNSET, and MIXED. 1448218885Sdim // Initial state: NONE. 1449218885Sdim // 1450218885Sdim // (NONE) ------- [01] -> (ALL_SET) 1451218885Sdim // (NONE) ------- _ ----> (ALL_UNSET) 1452218885Sdim // (ALL_SET) ---- [01] -> (ALL_SET) 1453218885Sdim // (ALL_SET) ---- _ ----> (MIXED) 1454218885Sdim // (ALL_UNSET) -- [01] -> (MIXED) 1455218885Sdim // (ALL_UNSET) -- _ ----> (ALL_UNSET) 1456218885Sdim // (MIXED) ------ . ----> (MIXED) 1457218885Sdim // (FILTERED)---- . ----> (FILTERED) 1458218885Sdim 1459226633Sdim std::vector<bitAttr_t> bitAttrs; 1460218885Sdim 1461218885Sdim // FILTERED bit positions provide no entropy and are not worthy of pursuing. 1462218885Sdim // Filter::recurse() set either BIT_TRUE or BIT_FALSE for each position. 1463226633Sdim for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) 1464218885Sdim if (FilterBitValues[BitIndex] == BIT_TRUE || 1465218885Sdim FilterBitValues[BitIndex] == BIT_FALSE) 1466226633Sdim bitAttrs.push_back(ATTR_FILTERED); 1467218885Sdim else 1468226633Sdim bitAttrs.push_back(ATTR_NONE); 1469218885Sdim 1470239462Sdim for (unsigned InsnIndex = 0; InsnIndex < numInstructions; ++InsnIndex) { 1471218885Sdim insn_t insn; 1472218885Sdim 1473218885Sdim insnWithID(insn, Opcodes[InsnIndex]); 1474218885Sdim 1475226633Sdim for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { 1476218885Sdim switch (bitAttrs[BitIndex]) { 1477218885Sdim case ATTR_NONE: 1478218885Sdim if (insn[BitIndex] == BIT_UNSET) 1479218885Sdim bitAttrs[BitIndex] = ATTR_ALL_UNSET; 1480218885Sdim else 1481218885Sdim bitAttrs[BitIndex] = ATTR_ALL_SET; 1482218885Sdim break; 1483218885Sdim case ATTR_ALL_SET: 1484218885Sdim if (insn[BitIndex] == BIT_UNSET) 1485218885Sdim bitAttrs[BitIndex] = ATTR_MIXED; 1486218885Sdim break; 1487218885Sdim case ATTR_ALL_UNSET: 1488218885Sdim if (insn[BitIndex] != BIT_UNSET) 1489218885Sdim bitAttrs[BitIndex] = ATTR_MIXED; 1490218885Sdim break; 1491218885Sdim case ATTR_MIXED: 1492218885Sdim case ATTR_FILTERED: 1493218885Sdim break; 1494218885Sdim } 1495218885Sdim } 1496218885Sdim } 1497218885Sdim 1498218885Sdim // The regionAttr automaton consumes the bitAttrs automatons' state, 1499218885Sdim // lowest-to-highest. 1500218885Sdim // 1501218885Sdim // Input symbols: F(iltered), (all_)S(et), (all_)U(nset), M(ixed) 1502218885Sdim // States: NONE, ALL_SET, MIXED 1503218885Sdim // Initial state: NONE 1504218885Sdim // 1505218885Sdim // (NONE) ----- F --> (NONE) 1506218885Sdim // (NONE) ----- S --> (ALL_SET) ; and set region start 1507218885Sdim // (NONE) ----- U --> (NONE) 1508218885Sdim // (NONE) ----- M --> (MIXED) ; and set region start 1509218885Sdim // (ALL_SET) -- F --> (NONE) ; and report an ALL_SET region 1510218885Sdim // (ALL_SET) -- S --> (ALL_SET) 1511218885Sdim // (ALL_SET) -- U --> (NONE) ; and report an ALL_SET region 1512218885Sdim // (ALL_SET) -- M --> (MIXED) ; and report an ALL_SET region 1513218885Sdim // (MIXED) ---- F --> (NONE) ; and report a MIXED region 1514218885Sdim // (MIXED) ---- S --> (ALL_SET) ; and report a MIXED region 1515218885Sdim // (MIXED) ---- U --> (NONE) ; and report a MIXED region 1516218885Sdim // (MIXED) ---- M --> (MIXED) 1517218885Sdim 1518218885Sdim bitAttr_t RA = ATTR_NONE; 1519218885Sdim unsigned StartBit = 0; 1520218885Sdim 1521239462Sdim for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { 1522218885Sdim bitAttr_t bitAttr = bitAttrs[BitIndex]; 1523218885Sdim 1524218885Sdim assert(bitAttr != ATTR_NONE && "Bit without attributes"); 1525218885Sdim 1526218885Sdim switch (RA) { 1527218885Sdim case ATTR_NONE: 1528218885Sdim switch (bitAttr) { 1529218885Sdim case ATTR_FILTERED: 1530218885Sdim break; 1531218885Sdim case ATTR_ALL_SET: 1532218885Sdim StartBit = BitIndex; 1533218885Sdim RA = ATTR_ALL_SET; 1534218885Sdim break; 1535218885Sdim case ATTR_ALL_UNSET: 1536218885Sdim break; 1537218885Sdim case ATTR_MIXED: 1538218885Sdim StartBit = BitIndex; 1539218885Sdim RA = ATTR_MIXED; 1540218885Sdim break; 1541218885Sdim default: 1542234353Sdim llvm_unreachable("Unexpected bitAttr!"); 1543218885Sdim } 1544218885Sdim break; 1545218885Sdim case ATTR_ALL_SET: 1546218885Sdim switch (bitAttr) { 1547218885Sdim case ATTR_FILTERED: 1548218885Sdim reportRegion(RA, StartBit, BitIndex, AllowMixed); 1549218885Sdim RA = ATTR_NONE; 1550218885Sdim break; 1551218885Sdim case ATTR_ALL_SET: 1552218885Sdim break; 1553218885Sdim case ATTR_ALL_UNSET: 1554218885Sdim reportRegion(RA, StartBit, BitIndex, AllowMixed); 1555218885Sdim RA = ATTR_NONE; 1556218885Sdim break; 1557218885Sdim case ATTR_MIXED: 1558218885Sdim reportRegion(RA, StartBit, BitIndex, AllowMixed); 1559218885Sdim StartBit = BitIndex; 1560218885Sdim RA = ATTR_MIXED; 1561218885Sdim break; 1562218885Sdim default: 1563234353Sdim llvm_unreachable("Unexpected bitAttr!"); 1564218885Sdim } 1565218885Sdim break; 1566218885Sdim case ATTR_MIXED: 1567218885Sdim switch (bitAttr) { 1568218885Sdim case ATTR_FILTERED: 1569218885Sdim reportRegion(RA, StartBit, BitIndex, AllowMixed); 1570218885Sdim StartBit = BitIndex; 1571218885Sdim RA = ATTR_NONE; 1572218885Sdim break; 1573218885Sdim case ATTR_ALL_SET: 1574218885Sdim reportRegion(RA, StartBit, BitIndex, AllowMixed); 1575218885Sdim StartBit = BitIndex; 1576218885Sdim RA = ATTR_ALL_SET; 1577218885Sdim break; 1578218885Sdim case ATTR_ALL_UNSET: 1579218885Sdim reportRegion(RA, StartBit, BitIndex, AllowMixed); 1580218885Sdim RA = ATTR_NONE; 1581218885Sdim break; 1582218885Sdim case ATTR_MIXED: 1583218885Sdim break; 1584218885Sdim default: 1585234353Sdim llvm_unreachable("Unexpected bitAttr!"); 1586218885Sdim } 1587218885Sdim break; 1588218885Sdim case ATTR_ALL_UNSET: 1589234353Sdim llvm_unreachable("regionAttr state machine has no ATTR_UNSET state"); 1590218885Sdim case ATTR_FILTERED: 1591234353Sdim llvm_unreachable("regionAttr state machine has no ATTR_FILTERED state"); 1592218885Sdim } 1593218885Sdim } 1594218885Sdim 1595218885Sdim // At the end, if we're still in ALL_SET or MIXED states, report a region 1596218885Sdim switch (RA) { 1597218885Sdim case ATTR_NONE: 1598218885Sdim break; 1599218885Sdim case ATTR_FILTERED: 1600218885Sdim break; 1601218885Sdim case ATTR_ALL_SET: 1602218885Sdim reportRegion(RA, StartBit, BitIndex, AllowMixed); 1603218885Sdim break; 1604218885Sdim case ATTR_ALL_UNSET: 1605218885Sdim break; 1606218885Sdim case ATTR_MIXED: 1607218885Sdim reportRegion(RA, StartBit, BitIndex, AllowMixed); 1608218885Sdim break; 1609218885Sdim } 1610218885Sdim 1611218885Sdim // We have finished with the filter processings. Now it's time to choose 1612218885Sdim // the best performing filter. 1613218885Sdim BestIndex = 0; 1614218885Sdim bool AllUseless = true; 1615218885Sdim unsigned BestScore = 0; 1616218885Sdim 1617218885Sdim for (unsigned i = 0, e = Filters.size(); i != e; ++i) { 1618218885Sdim unsigned Usefulness = Filters[i].usefulness(); 1619218885Sdim 1620218885Sdim if (Usefulness) 1621218885Sdim AllUseless = false; 1622218885Sdim 1623218885Sdim if (Usefulness > BestScore) { 1624218885Sdim BestIndex = i; 1625218885Sdim BestScore = Usefulness; 1626218885Sdim } 1627218885Sdim } 1628218885Sdim 1629218885Sdim if (!AllUseless) 1630218885Sdim bestFilter().recurse(); 1631218885Sdim 1632218885Sdim return !AllUseless; 1633218885Sdim} // end of FilterChooser::filterProcessor(bool) 1634218885Sdim 1635218885Sdim// Decides on the best configuration of filter(s) to use in order to decode 1636218885Sdim// the instructions. A conflict of instructions may occur, in which case we 1637218885Sdim// dump the conflict set to the standard error. 1638218885Sdimvoid FilterChooser::doFilter() { 1639218885Sdim unsigned Num = Opcodes.size(); 1640218885Sdim assert(Num && "FilterChooser created with no instructions"); 1641218885Sdim 1642218885Sdim // Try regions of consecutive known bit values first. 1643218885Sdim if (filterProcessor(false)) 1644218885Sdim return; 1645218885Sdim 1646218885Sdim // Then regions of mixed bits (both known and unitialized bit values allowed). 1647218885Sdim if (filterProcessor(true)) 1648218885Sdim return; 1649218885Sdim 1650218885Sdim // Heuristics to cope with conflict set {t2CMPrs, t2SUBSrr, t2SUBSrs} where 1651218885Sdim // no single instruction for the maximum ATTR_MIXED region Inst{14-4} has a 1652218885Sdim // well-known encoding pattern. In such case, we backtrack and scan for the 1653218885Sdim // the very first consecutive ATTR_ALL_SET region and assign a filter to it. 1654218885Sdim if (Num == 3 && filterProcessor(true, false)) 1655218885Sdim return; 1656218885Sdim 1657218885Sdim // If we come to here, the instruction decoding has failed. 1658218885Sdim // Set the BestIndex to -1 to indicate so. 1659218885Sdim BestIndex = -1; 1660218885Sdim} 1661218885Sdim 1662239462Sdim// emitTableEntries - Emit state machine entries to decode our share of 1663239462Sdim// instructions. 1664239462Sdimvoid FilterChooser::emitTableEntries(DecoderTableInfo &TableInfo) const { 1665239462Sdim if (Opcodes.size() == 1) { 1666218885Sdim // There is only one instruction in the set, which is great! 1667218885Sdim // Call emitSingletonDecoder() to see whether there are any remaining 1668218885Sdim // encodings bits. 1669239462Sdim emitSingletonTableEntry(TableInfo, Opcodes[0]); 1670239462Sdim return; 1671239462Sdim } 1672218885Sdim 1673218885Sdim // Choose the best filter to do the decodings! 1674218885Sdim if (BestIndex != -1) { 1675234353Sdim const Filter &Best = Filters[BestIndex]; 1676218885Sdim if (Best.getNumFiltered() == 1) 1677239462Sdim emitSingletonTableEntry(TableInfo, Best); 1678218885Sdim else 1679239462Sdim Best.emitTableEntry(TableInfo); 1680239462Sdim return; 1681218885Sdim } 1682218885Sdim 1683239462Sdim // We don't know how to decode these instructions! Dump the 1684239462Sdim // conflict set and bail. 1685218885Sdim 1686218885Sdim // Print out useful conflict information for postmortem analysis. 1687218885Sdim errs() << "Decoding Conflict:\n"; 1688218885Sdim 1689218885Sdim dumpStack(errs(), "\t\t"); 1690218885Sdim 1691234353Sdim for (unsigned i = 0; i < Opcodes.size(); ++i) { 1692218885Sdim const std::string &Name = nameWithID(Opcodes[i]); 1693218885Sdim 1694218885Sdim errs() << '\t' << Name << " "; 1695218885Sdim dumpBits(errs(), 1696218885Sdim getBitsField(*AllInstructions[Opcodes[i]]->TheDef, "Inst")); 1697218885Sdim errs() << '\n'; 1698218885Sdim } 1699218885Sdim} 1700218885Sdim 1701234353Sdimstatic bool populateInstruction(const CodeGenInstruction &CGI, unsigned Opc, 1702234353Sdim std::map<unsigned, std::vector<OperandInfo> > &Operands){ 1703218885Sdim const Record &Def = *CGI.TheDef; 1704218885Sdim // If all the bit positions are not specified; do not decode this instruction. 1705218885Sdim // We are bound to fail! For proper disassembly, the well-known encoding bits 1706218885Sdim // of the instruction must be fully specified. 1707218885Sdim // 1708218885Sdim // This also removes pseudo instructions from considerations of disassembly, 1709218885Sdim // which is a better design and less fragile than the name matchings. 1710218885Sdim // Ignore "asm parser only" instructions. 1711221345Sdim if (Def.getValueAsBit("isAsmParserOnly") || 1712221345Sdim Def.getValueAsBit("isCodeGenOnly")) 1713218885Sdim return false; 1714218885Sdim 1715224145Sdim BitsInit &Bits = getBitsField(Def, "Inst"); 1716224145Sdim if (Bits.allInComplete()) return false; 1717224145Sdim 1718218885Sdim std::vector<OperandInfo> InsnOperands; 1719218885Sdim 1720218885Sdim // If the instruction has specified a custom decoding hook, use that instead 1721218885Sdim // of trying to auto-generate the decoder. 1722218885Sdim std::string InstDecoder = Def.getValueAsString("DecoderMethod"); 1723218885Sdim if (InstDecoder != "") { 1724226633Sdim InsnOperands.push_back(OperandInfo(InstDecoder)); 1725218885Sdim Operands[Opc] = InsnOperands; 1726218885Sdim return true; 1727218885Sdim } 1728218885Sdim 1729218885Sdim // Generate a description of the operand of the instruction that we know 1730218885Sdim // how to decode automatically. 1731218885Sdim // FIXME: We'll need to have a way to manually override this as needed. 1732218885Sdim 1733218885Sdim // Gather the outputs/inputs of the instruction, so we can find their 1734218885Sdim // positions in the encoding. This assumes for now that they appear in the 1735218885Sdim // MCInst in the order that they're listed. 1736218885Sdim std::vector<std::pair<Init*, std::string> > InOutOperands; 1737218885Sdim DagInit *Out = Def.getValueAsDag("OutOperandList"); 1738218885Sdim DagInit *In = Def.getValueAsDag("InOperandList"); 1739218885Sdim for (unsigned i = 0; i < Out->getNumArgs(); ++i) 1740218885Sdim InOutOperands.push_back(std::make_pair(Out->getArg(i), Out->getArgName(i))); 1741218885Sdim for (unsigned i = 0; i < In->getNumArgs(); ++i) 1742218885Sdim InOutOperands.push_back(std::make_pair(In->getArg(i), In->getArgName(i))); 1743218885Sdim 1744226633Sdim // Search for tied operands, so that we can correctly instantiate 1745226633Sdim // operands that are not explicitly represented in the encoding. 1746226633Sdim std::map<std::string, std::string> TiedNames; 1747226633Sdim for (unsigned i = 0; i < CGI.Operands.size(); ++i) { 1748226633Sdim int tiedTo = CGI.Operands[i].getTiedRegister(); 1749226633Sdim if (tiedTo != -1) { 1750226633Sdim TiedNames[InOutOperands[i].second] = InOutOperands[tiedTo].second; 1751226633Sdim TiedNames[InOutOperands[tiedTo].second] = InOutOperands[i].second; 1752226633Sdim } 1753226633Sdim } 1754226633Sdim 1755218885Sdim // For each operand, see if we can figure out where it is encoded. 1756234353Sdim for (std::vector<std::pair<Init*, std::string> >::const_iterator 1757218885Sdim NI = InOutOperands.begin(), NE = InOutOperands.end(); NI != NE; ++NI) { 1758218885Sdim std::string Decoder = ""; 1759218885Sdim 1760226633Sdim // At this point, we can locate the field, but we need to know how to 1761226633Sdim // interpret it. As a first step, require the target to provide callbacks 1762226633Sdim // for decoding register classes. 1763226633Sdim // FIXME: This need to be extended to handle instructions with custom 1764226633Sdim // decoder methods, and operands with (simple) MIOperandInfo's. 1765243830Sdim TypedInit *TI = cast<TypedInit>(NI->first); 1766243830Sdim RecordRecTy *Type = cast<RecordRecTy>(TI->getType()); 1767226633Sdim Record *TypeRecord = Type->getRecord(); 1768226633Sdim bool isReg = false; 1769226633Sdim if (TypeRecord->isSubClassOf("RegisterOperand")) 1770226633Sdim TypeRecord = TypeRecord->getValueAsDef("RegClass"); 1771226633Sdim if (TypeRecord->isSubClassOf("RegisterClass")) { 1772226633Sdim Decoder = "Decode" + TypeRecord->getName() + "RegisterClass"; 1773226633Sdim isReg = true; 1774226633Sdim } 1775226633Sdim 1776226633Sdim RecordVal *DecoderString = TypeRecord->getValue("DecoderMethod"); 1777226633Sdim StringInit *String = DecoderString ? 1778243830Sdim dyn_cast<StringInit>(DecoderString->getValue()) : 0; 1779226633Sdim if (!isReg && String && String->getValue() != "") 1780226633Sdim Decoder = String->getValue(); 1781226633Sdim 1782226633Sdim OperandInfo OpInfo(Decoder); 1783226633Sdim unsigned Base = ~0U; 1784226633Sdim unsigned Width = 0; 1785226633Sdim unsigned Offset = 0; 1786226633Sdim 1787218885Sdim for (unsigned bi = 0; bi < Bits.getNumBits(); ++bi) { 1788226633Sdim VarInit *Var = 0; 1789243830Sdim VarBitInit *BI = dyn_cast<VarBitInit>(Bits.getBit(bi)); 1790226633Sdim if (BI) 1791243830Sdim Var = dyn_cast<VarInit>(BI->getBitVar()); 1792226633Sdim else 1793243830Sdim Var = dyn_cast<VarInit>(Bits.getBit(bi)); 1794218885Sdim 1795226633Sdim if (!Var) { 1796226633Sdim if (Base != ~0U) { 1797226633Sdim OpInfo.addField(Base, Width, Offset); 1798226633Sdim Base = ~0U; 1799226633Sdim Width = 0; 1800226633Sdim Offset = 0; 1801226633Sdim } 1802226633Sdim continue; 1803218885Sdim } 1804218885Sdim 1805226633Sdim if (Var->getName() != NI->second && 1806226633Sdim Var->getName() != TiedNames[NI->second]) { 1807226633Sdim if (Base != ~0U) { 1808226633Sdim OpInfo.addField(Base, Width, Offset); 1809226633Sdim Base = ~0U; 1810226633Sdim Width = 0; 1811226633Sdim Offset = 0; 1812226633Sdim } 1813226633Sdim continue; 1814218885Sdim } 1815218885Sdim 1816226633Sdim if (Base == ~0U) { 1817226633Sdim Base = bi; 1818226633Sdim Width = 1; 1819226633Sdim Offset = BI ? BI->getBitNum() : 0; 1820226633Sdim } else if (BI && BI->getBitNum() != Offset + Width) { 1821226633Sdim OpInfo.addField(Base, Width, Offset); 1822226633Sdim Base = bi; 1823226633Sdim Width = 1; 1824226633Sdim Offset = BI->getBitNum(); 1825226633Sdim } else { 1826226633Sdim ++Width; 1827218885Sdim } 1828218885Sdim } 1829218885Sdim 1830226633Sdim if (Base != ~0U) 1831226633Sdim OpInfo.addField(Base, Width, Offset); 1832226633Sdim 1833226633Sdim if (OpInfo.numFields() > 0) 1834226633Sdim InsnOperands.push_back(OpInfo); 1835218885Sdim } 1836218885Sdim 1837218885Sdim Operands[Opc] = InsnOperands; 1838218885Sdim 1839218885Sdim 1840218885Sdim#if 0 1841218885Sdim DEBUG({ 1842218885Sdim // Dumps the instruction encoding bits. 1843218885Sdim dumpBits(errs(), Bits); 1844218885Sdim 1845218885Sdim errs() << '\n'; 1846218885Sdim 1847218885Sdim // Dumps the list of operand info. 1848218885Sdim for (unsigned i = 0, e = CGI.Operands.size(); i != e; ++i) { 1849218885Sdim const CGIOperandList::OperandInfo &Info = CGI.Operands[i]; 1850218885Sdim const std::string &OperandName = Info.Name; 1851218885Sdim const Record &OperandDef = *Info.Rec; 1852218885Sdim 1853218885Sdim errs() << "\t" << OperandName << " (" << OperandDef.getName() << ")\n"; 1854218885Sdim } 1855218885Sdim }); 1856218885Sdim#endif 1857218885Sdim 1858218885Sdim return true; 1859218885Sdim} 1860218885Sdim 1861239462Sdim// emitFieldFromInstruction - Emit the templated helper function 1862239462Sdim// fieldFromInstruction(). 1863239462Sdimstatic void emitFieldFromInstruction(formatted_raw_ostream &OS) { 1864239462Sdim OS << "// Helper function for extracting fields from encoded instructions.\n" 1865239462Sdim << "template<typename InsnType>\n" 1866239462Sdim << "static InsnType fieldFromInstruction(InsnType insn, unsigned startBit,\n" 1867239462Sdim << " unsigned numBits) {\n" 1868239462Sdim << " assert(startBit + numBits <= (sizeof(InsnType)*8) &&\n" 1869239462Sdim << " \"Instruction field out of bounds!\");\n" 1870239462Sdim << " InsnType fieldMask;\n" 1871239462Sdim << " if (numBits == sizeof(InsnType)*8)\n" 1872239462Sdim << " fieldMask = (InsnType)(-1LL);\n" 1873239462Sdim << " else\n" 1874249423Sdim << " fieldMask = (((InsnType)1 << numBits) - 1) << startBit;\n" 1875239462Sdim << " return (insn & fieldMask) >> startBit;\n" 1876239462Sdim << "}\n\n"; 1877239462Sdim} 1878218885Sdim 1879239462Sdim// emitDecodeInstruction - Emit the templated helper function 1880239462Sdim// decodeInstruction(). 1881239462Sdimstatic void emitDecodeInstruction(formatted_raw_ostream &OS) { 1882239462Sdim OS << "template<typename InsnType>\n" 1883239462Sdim << "static DecodeStatus decodeInstruction(const uint8_t DecodeTable[], MCInst &MI,\n" 1884239462Sdim << " InsnType insn, uint64_t Address,\n" 1885239462Sdim << " const void *DisAsm,\n" 1886239462Sdim << " const MCSubtargetInfo &STI) {\n" 1887239462Sdim << " uint64_t Bits = STI.getFeatureBits();\n" 1888239462Sdim << "\n" 1889239462Sdim << " const uint8_t *Ptr = DecodeTable;\n" 1890243830Sdim << " uint32_t CurFieldValue = 0;\n" 1891239462Sdim << " DecodeStatus S = MCDisassembler::Success;\n" 1892239462Sdim << " for (;;) {\n" 1893239462Sdim << " ptrdiff_t Loc = Ptr - DecodeTable;\n" 1894239462Sdim << " switch (*Ptr) {\n" 1895239462Sdim << " default:\n" 1896239462Sdim << " errs() << Loc << \": Unexpected decode table opcode!\\n\";\n" 1897239462Sdim << " return MCDisassembler::Fail;\n" 1898239462Sdim << " case MCD::OPC_ExtractField: {\n" 1899239462Sdim << " unsigned Start = *++Ptr;\n" 1900239462Sdim << " unsigned Len = *++Ptr;\n" 1901239462Sdim << " ++Ptr;\n" 1902239462Sdim << " CurFieldValue = fieldFromInstruction(insn, Start, Len);\n" 1903239462Sdim << " DEBUG(dbgs() << Loc << \": OPC_ExtractField(\" << Start << \", \"\n" 1904239462Sdim << " << Len << \"): \" << CurFieldValue << \"\\n\");\n" 1905239462Sdim << " break;\n" 1906239462Sdim << " }\n" 1907239462Sdim << " case MCD::OPC_FilterValue: {\n" 1908239462Sdim << " // Decode the field value.\n" 1909239462Sdim << " unsigned Len;\n" 1910239462Sdim << " InsnType Val = decodeULEB128(++Ptr, &Len);\n" 1911239462Sdim << " Ptr += Len;\n" 1912239462Sdim << " // NumToSkip is a plain 16-bit integer.\n" 1913239462Sdim << " unsigned NumToSkip = *Ptr++;\n" 1914239462Sdim << " NumToSkip |= (*Ptr++) << 8;\n" 1915239462Sdim << "\n" 1916239462Sdim << " // Perform the filter operation.\n" 1917239462Sdim << " if (Val != CurFieldValue)\n" 1918239462Sdim << " Ptr += NumToSkip;\n" 1919239462Sdim << " DEBUG(dbgs() << Loc << \": OPC_FilterValue(\" << Val << \", \" << NumToSkip\n" 1920239462Sdim << " << \"): \" << ((Val != CurFieldValue) ? \"FAIL:\" : \"PASS:\")\n" 1921239462Sdim << " << \" continuing at \" << (Ptr - DecodeTable) << \"\\n\");\n" 1922239462Sdim << "\n" 1923239462Sdim << " break;\n" 1924239462Sdim << " }\n" 1925239462Sdim << " case MCD::OPC_CheckField: {\n" 1926239462Sdim << " unsigned Start = *++Ptr;\n" 1927239462Sdim << " unsigned Len = *++Ptr;\n" 1928239462Sdim << " InsnType FieldValue = fieldFromInstruction(insn, Start, Len);\n" 1929239462Sdim << " // Decode the field value.\n" 1930239462Sdim << " uint32_t ExpectedValue = decodeULEB128(++Ptr, &Len);\n" 1931239462Sdim << " Ptr += Len;\n" 1932239462Sdim << " // NumToSkip is a plain 16-bit integer.\n" 1933239462Sdim << " unsigned NumToSkip = *Ptr++;\n" 1934239462Sdim << " NumToSkip |= (*Ptr++) << 8;\n" 1935239462Sdim << "\n" 1936239462Sdim << " // If the actual and expected values don't match, skip.\n" 1937239462Sdim << " if (ExpectedValue != FieldValue)\n" 1938239462Sdim << " Ptr += NumToSkip;\n" 1939239462Sdim << " DEBUG(dbgs() << Loc << \": OPC_CheckField(\" << Start << \", \"\n" 1940239462Sdim << " << Len << \", \" << ExpectedValue << \", \" << NumToSkip\n" 1941239462Sdim << " << \"): FieldValue = \" << FieldValue << \", ExpectedValue = \"\n" 1942239462Sdim << " << ExpectedValue << \": \"\n" 1943239462Sdim << " << ((ExpectedValue == FieldValue) ? \"PASS\\n\" : \"FAIL\\n\"));\n" 1944239462Sdim << " break;\n" 1945239462Sdim << " }\n" 1946239462Sdim << " case MCD::OPC_CheckPredicate: {\n" 1947239462Sdim << " unsigned Len;\n" 1948239462Sdim << " // Decode the Predicate Index value.\n" 1949239462Sdim << " unsigned PIdx = decodeULEB128(++Ptr, &Len);\n" 1950239462Sdim << " Ptr += Len;\n" 1951239462Sdim << " // NumToSkip is a plain 16-bit integer.\n" 1952239462Sdim << " unsigned NumToSkip = *Ptr++;\n" 1953239462Sdim << " NumToSkip |= (*Ptr++) << 8;\n" 1954239462Sdim << " // Check the predicate.\n" 1955239462Sdim << " bool Pred;\n" 1956239462Sdim << " if (!(Pred = checkDecoderPredicate(PIdx, Bits)))\n" 1957239462Sdim << " Ptr += NumToSkip;\n" 1958239462Sdim << " (void)Pred;\n" 1959239462Sdim << " DEBUG(dbgs() << Loc << \": OPC_CheckPredicate(\" << PIdx << \"): \"\n" 1960239462Sdim << " << (Pred ? \"PASS\\n\" : \"FAIL\\n\"));\n" 1961239462Sdim << "\n" 1962239462Sdim << " break;\n" 1963239462Sdim << " }\n" 1964239462Sdim << " case MCD::OPC_Decode: {\n" 1965239462Sdim << " unsigned Len;\n" 1966239462Sdim << " // Decode the Opcode value.\n" 1967239462Sdim << " unsigned Opc = decodeULEB128(++Ptr, &Len);\n" 1968239462Sdim << " Ptr += Len;\n" 1969239462Sdim << " unsigned DecodeIdx = decodeULEB128(Ptr, &Len);\n" 1970239462Sdim << " Ptr += Len;\n" 1971239462Sdim << " DEBUG(dbgs() << Loc << \": OPC_Decode: opcode \" << Opc\n" 1972239462Sdim << " << \", using decoder \" << DecodeIdx << \"\\n\" );\n" 1973239462Sdim << " DEBUG(dbgs() << \"----- DECODE SUCCESSFUL -----\\n\");\n" 1974239462Sdim << "\n" 1975239462Sdim << " MI.setOpcode(Opc);\n" 1976239462Sdim << " return decodeToMCInst(S, DecodeIdx, insn, MI, Address, DisAsm);\n" 1977239462Sdim << " }\n" 1978239462Sdim << " case MCD::OPC_SoftFail: {\n" 1979239462Sdim << " // Decode the mask values.\n" 1980239462Sdim << " unsigned Len;\n" 1981239462Sdim << " InsnType PositiveMask = decodeULEB128(++Ptr, &Len);\n" 1982239462Sdim << " Ptr += Len;\n" 1983239462Sdim << " InsnType NegativeMask = decodeULEB128(Ptr, &Len);\n" 1984239462Sdim << " Ptr += Len;\n" 1985239462Sdim << " bool Fail = (insn & PositiveMask) || (~insn & NegativeMask);\n" 1986239462Sdim << " if (Fail)\n" 1987239462Sdim << " S = MCDisassembler::SoftFail;\n" 1988239462Sdim << " DEBUG(dbgs() << Loc << \": OPC_SoftFail: \" << (Fail ? \"FAIL\\n\":\"PASS\\n\"));\n" 1989239462Sdim << " break;\n" 1990239462Sdim << " }\n" 1991239462Sdim << " case MCD::OPC_Fail: {\n" 1992239462Sdim << " DEBUG(dbgs() << Loc << \": OPC_Fail\\n\");\n" 1993239462Sdim << " return MCDisassembler::Fail;\n" 1994239462Sdim << " }\n" 1995239462Sdim << " }\n" 1996239462Sdim << " }\n" 1997239462Sdim << " llvm_unreachable(\"bogosity detected in disassembler state machine!\");\n" 1998239462Sdim << "}\n\n"; 1999218885Sdim} 2000218885Sdim 2001218885Sdim// Emits disassembler code for instruction decoding. 2002234353Sdimvoid FixedLenDecoderEmitter::run(raw_ostream &o) { 2003239462Sdim formatted_raw_ostream OS(o); 2004239462Sdim OS << "#include \"llvm/MC/MCInst.h\"\n"; 2005239462Sdim OS << "#include \"llvm/Support/Debug.h\"\n"; 2006239462Sdim OS << "#include \"llvm/Support/DataTypes.h\"\n"; 2007239462Sdim OS << "#include \"llvm/Support/LEB128.h\"\n"; 2008239462Sdim OS << "#include \"llvm/Support/raw_ostream.h\"\n"; 2009239462Sdim OS << "#include <assert.h>\n"; 2010239462Sdim OS << '\n'; 2011239462Sdim OS << "namespace llvm {\n\n"; 2012218885Sdim 2013239462Sdim emitFieldFromInstruction(OS); 2014239462Sdim 2015226633Sdim // Parameterize the decoders based on namespace and instruction width. 2016239462Sdim NumberedInstructions = &Target.getInstructionsByEnumValue(); 2017226633Sdim std::map<std::pair<std::string, unsigned>, 2018226633Sdim std::vector<unsigned> > OpcMap; 2019226633Sdim std::map<unsigned, std::vector<OperandInfo> > Operands; 2020218885Sdim 2021239462Sdim for (unsigned i = 0; i < NumberedInstructions->size(); ++i) { 2022239462Sdim const CodeGenInstruction *Inst = NumberedInstructions->at(i); 2023234353Sdim const Record *Def = Inst->TheDef; 2024226633Sdim unsigned Size = Def->getValueAsInt("Size"); 2025226633Sdim if (Def->getValueAsString("Namespace") == "TargetOpcode" || 2026226633Sdim Def->getValueAsBit("isPseudo") || 2027226633Sdim Def->getValueAsBit("isAsmParserOnly") || 2028226633Sdim Def->getValueAsBit("isCodeGenOnly")) 2029226633Sdim continue; 2030226633Sdim 2031226633Sdim std::string DecoderNamespace = Def->getValueAsString("DecoderNamespace"); 2032226633Sdim 2033226633Sdim if (Size) { 2034226633Sdim if (populateInstruction(*Inst, i, Operands)) { 2035226633Sdim OpcMap[std::make_pair(DecoderNamespace, Size)].push_back(i); 2036226633Sdim } 2037226633Sdim } 2038226633Sdim } 2039226633Sdim 2040239462Sdim DecoderTableInfo TableInfo; 2041226633Sdim for (std::map<std::pair<std::string, unsigned>, 2042234353Sdim std::vector<unsigned> >::const_iterator 2043226633Sdim I = OpcMap.begin(), E = OpcMap.end(); I != E; ++I) { 2044226633Sdim // Emit the decoder for this namespace+width combination. 2045239462Sdim FilterChooser FC(*NumberedInstructions, I->second, Operands, 2046226633Sdim 8*I->first.second, this); 2047239462Sdim 2048239462Sdim // The decode table is cleared for each top level decoder function. The 2049239462Sdim // predicates and decoders themselves, however, are shared across all 2050239462Sdim // decoders to give more opportunities for uniqueing. 2051239462Sdim TableInfo.Table.clear(); 2052239462Sdim TableInfo.FixupStack.clear(); 2053239462Sdim TableInfo.Table.reserve(16384); 2054239462Sdim TableInfo.FixupStack.push_back(FixupList()); 2055239462Sdim FC.emitTableEntries(TableInfo); 2056239462Sdim // Any NumToSkip fixups in the top level scope can resolve to the 2057239462Sdim // OPC_Fail at the end of the table. 2058239462Sdim assert(TableInfo.FixupStack.size() == 1 && "fixup stack phasing error!"); 2059239462Sdim // Resolve any NumToSkip fixups in the current scope. 2060239462Sdim resolveTableFixups(TableInfo.Table, TableInfo.FixupStack.back(), 2061239462Sdim TableInfo.Table.size()); 2062239462Sdim TableInfo.FixupStack.clear(); 2063239462Sdim 2064239462Sdim TableInfo.Table.push_back(MCD::OPC_Fail); 2065239462Sdim 2066239462Sdim // Print the table to the output stream. 2067239462Sdim emitTable(OS, TableInfo.Table, 0, FC.getBitWidth(), I->first.first); 2068239462Sdim OS.flush(); 2069226633Sdim } 2070226633Sdim 2071239462Sdim // Emit the predicate function. 2072239462Sdim emitPredicateFunction(OS, TableInfo.Predicates, 0); 2073239462Sdim 2074239462Sdim // Emit the decoder function. 2075239462Sdim emitDecoderFunction(OS, TableInfo.Decoders, 0); 2076239462Sdim 2077239462Sdim // Emit the main entry point for the decoder, decodeInstruction(). 2078239462Sdim emitDecodeInstruction(OS); 2079239462Sdim 2080239462Sdim OS << "\n} // End llvm namespace\n"; 2081218885Sdim} 2082239462Sdim 2083239462Sdimnamespace llvm { 2084239462Sdim 2085239462Sdimvoid EmitFixedLenDecoder(RecordKeeper &RK, raw_ostream &OS, 2086239462Sdim std::string PredicateNamespace, 2087239462Sdim std::string GPrefix, 2088239462Sdim std::string GPostfix, 2089239462Sdim std::string ROK, 2090239462Sdim std::string RFail, 2091239462Sdim std::string L) { 2092239462Sdim FixedLenDecoderEmitter(RK, PredicateNamespace, GPrefix, GPostfix, 2093239462Sdim ROK, RFail, L).run(OS); 2094239462Sdim} 2095239462Sdim 2096239462Sdim} // End llvm namespace 2097