1//===------------ FixedLenDecoderEmitter.cpp - Decoder Generator ----------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// It contains the tablegen backend that emits the decoder functions for 11// targets with fixed length instruction set. 12// 13//===----------------------------------------------------------------------===// 14 15#include "CodeGenTarget.h" 16#include "llvm/ADT/APInt.h" 17#include "llvm/ADT/SmallString.h" 18#include "llvm/ADT/StringExtras.h" 19#include "llvm/ADT/StringRef.h" 20#include "llvm/ADT/Twine.h" 21#include "llvm/MC/MCFixedLenDisassembler.h" 22#include "llvm/Support/DataTypes.h" 23#include "llvm/Support/Debug.h" 24#include "llvm/Support/FormattedStream.h" 25#include "llvm/Support/LEB128.h" 26#include "llvm/Support/raw_ostream.h" 27#include "llvm/TableGen/Error.h" 28#include "llvm/TableGen/Record.h" 29#include <map> 30#include <string> 31#include <utility> 32#include <vector> 33 34using namespace llvm; 35 36#define DEBUG_TYPE "decoder-emitter" 37 38namespace { 39struct EncodingField { 40 unsigned Base, Width, Offset; 41 EncodingField(unsigned B, unsigned W, unsigned O) 42 : Base(B), Width(W), Offset(O) { } 43}; 44 45struct OperandInfo { 46 std::vector<EncodingField> Fields; 47 std::string Decoder; 48 bool HasCompleteDecoder; 49 50 OperandInfo(std::string D, bool HCD) 51 : Decoder(std::move(D)), HasCompleteDecoder(HCD) {} 52 53 void addField(unsigned Base, unsigned Width, unsigned Offset) { 54 Fields.push_back(EncodingField(Base, Width, Offset)); 55 } 56 57 unsigned numFields() const { return Fields.size(); } 58 59 typedef std::vector<EncodingField>::const_iterator const_iterator; 60 61 const_iterator begin() const { return Fields.begin(); } 62 const_iterator end() const { return Fields.end(); } 63}; 64 65typedef std::vector<uint8_t> DecoderTable; 66typedef uint32_t DecoderFixup; 67typedef std::vector<DecoderFixup> FixupList; 68typedef std::vector<FixupList> FixupScopeList; 69typedef SmallSetVector<std::string, 16> PredicateSet; 70typedef SmallSetVector<std::string, 16> DecoderSet; 71struct DecoderTableInfo { 72 DecoderTable Table; 73 FixupScopeList FixupStack; 74 PredicateSet Predicates; 75 DecoderSet Decoders; 76}; 77 78} // End anonymous namespace 79 80namespace { 81class FixedLenDecoderEmitter { 82 ArrayRef<const CodeGenInstruction *> NumberedInstructions; 83public: 84 85 // Defaults preserved here for documentation, even though they aren't 86 // strictly necessary given the way that this is currently being called. 87 FixedLenDecoderEmitter(RecordKeeper &R, std::string PredicateNamespace, 88 std::string GPrefix = "if (", 89 std::string GPostfix = " == MCDisassembler::Fail)", 90 std::string ROK = "MCDisassembler::Success", 91 std::string RFail = "MCDisassembler::Fail", 92 std::string L = "") 93 : Target(R), PredicateNamespace(std::move(PredicateNamespace)), 94 GuardPrefix(std::move(GPrefix)), GuardPostfix(std::move(GPostfix)), 95 ReturnOK(std::move(ROK)), ReturnFail(std::move(RFail)), 96 Locals(std::move(L)) {} 97 98 // Emit the decoder state machine table. 99 void emitTable(formatted_raw_ostream &o, DecoderTable &Table, 100 unsigned Indentation, unsigned BitWidth, 101 StringRef Namespace) const; 102 void emitPredicateFunction(formatted_raw_ostream &OS, 103 PredicateSet &Predicates, 104 unsigned Indentation) const; 105 void emitDecoderFunction(formatted_raw_ostream &OS, 106 DecoderSet &Decoders, 107 unsigned Indentation) const; 108 109 // run - Output the code emitter 110 void run(raw_ostream &o); 111 112private: 113 CodeGenTarget Target; 114public: 115 std::string PredicateNamespace; 116 std::string GuardPrefix, GuardPostfix; 117 std::string ReturnOK, ReturnFail; 118 std::string Locals; 119}; 120} // End anonymous namespace 121 122// The set (BIT_TRUE, BIT_FALSE, BIT_UNSET) represents a ternary logic system 123// for a bit value. 124// 125// BIT_UNFILTERED is used as the init value for a filter position. It is used 126// only for filter processings. 127typedef enum { 128 BIT_TRUE, // '1' 129 BIT_FALSE, // '0' 130 BIT_UNSET, // '?' 131 BIT_UNFILTERED // unfiltered 132} bit_value_t; 133 134static bool ValueSet(bit_value_t V) { 135 return (V == BIT_TRUE || V == BIT_FALSE); 136} 137static bool ValueNotSet(bit_value_t V) { 138 return (V == BIT_UNSET); 139} 140static int Value(bit_value_t V) { 141 return ValueNotSet(V) ? -1 : (V == BIT_FALSE ? 0 : 1); 142} 143static bit_value_t bitFromBits(const BitsInit &bits, unsigned index) { 144 if (BitInit *bit = dyn_cast<BitInit>(bits.getBit(index))) 145 return bit->getValue() ? BIT_TRUE : BIT_FALSE; 146 147 // The bit is uninitialized. 148 return BIT_UNSET; 149} 150// Prints the bit value for each position. 151static void dumpBits(raw_ostream &o, const BitsInit &bits) { 152 for (unsigned index = bits.getNumBits(); index > 0; --index) { 153 switch (bitFromBits(bits, index - 1)) { 154 case BIT_TRUE: 155 o << "1"; 156 break; 157 case BIT_FALSE: 158 o << "0"; 159 break; 160 case BIT_UNSET: 161 o << "_"; 162 break; 163 default: 164 llvm_unreachable("unexpected return value from bitFromBits"); 165 } 166 } 167} 168 169static BitsInit &getBitsField(const Record &def, const char *str) { 170 BitsInit *bits = def.getValueAsBitsInit(str); 171 return *bits; 172} 173 174// Forward declaration. 175namespace { 176class FilterChooser; 177} // End anonymous namespace 178 179// Representation of the instruction to work on. 180typedef std::vector<bit_value_t> insn_t; 181 182/// Filter - Filter works with FilterChooser to produce the decoding tree for 183/// the ISA. 184/// 185/// It is useful to think of a Filter as governing the switch stmts of the 186/// decoding tree in a certain level. Each case stmt delegates to an inferior 187/// FilterChooser to decide what further decoding logic to employ, or in another 188/// words, what other remaining bits to look at. The FilterChooser eventually 189/// chooses a best Filter to do its job. 190/// 191/// This recursive scheme ends when the number of Opcodes assigned to the 192/// FilterChooser becomes 1 or if there is a conflict. A conflict happens when 193/// the Filter/FilterChooser combo does not know how to distinguish among the 194/// Opcodes assigned. 195/// 196/// An example of a conflict is 197/// 198/// Conflict: 199/// 111101000.00........00010000.... 200/// 111101000.00........0001........ 201/// 1111010...00........0001........ 202/// 1111010...00.................... 203/// 1111010......................... 204/// 1111............................ 205/// ................................ 206/// VST4q8a 111101000_00________00010000____ 207/// VST4q8b 111101000_00________00010000____ 208/// 209/// The Debug output shows the path that the decoding tree follows to reach the 210/// the conclusion that there is a conflict. VST4q8a is a vst4 to double-spaced 211/// even registers, while VST4q8b is a vst4 to double-spaced odd registers. 212/// 213/// The encoding info in the .td files does not specify this meta information, 214/// which could have been used by the decoder to resolve the conflict. The 215/// decoder could try to decode the even/odd register numbering and assign to 216/// VST4q8a or VST4q8b, but for the time being, the decoder chooses the "a" 217/// version and return the Opcode since the two have the same Asm format string. 218namespace { 219class Filter { 220protected: 221 const FilterChooser *Owner;// points to the FilterChooser who owns this filter 222 unsigned StartBit; // the starting bit position 223 unsigned NumBits; // number of bits to filter 224 bool Mixed; // a mixed region contains both set and unset bits 225 226 // Map of well-known segment value to the set of uid's with that value. 227 std::map<uint64_t, std::vector<unsigned> > FilteredInstructions; 228 229 // Set of uid's with non-constant segment values. 230 std::vector<unsigned> VariableInstructions; 231 232 // Map of well-known segment value to its delegate. 233 std::map<unsigned, std::unique_ptr<const FilterChooser>> FilterChooserMap; 234 235 // Number of instructions which fall under FilteredInstructions category. 236 unsigned NumFiltered; 237 238 // Keeps track of the last opcode in the filtered bucket. 239 unsigned LastOpcFiltered; 240 241public: 242 unsigned getNumFiltered() const { return NumFiltered; } 243 unsigned getSingletonOpc() const { 244 assert(NumFiltered == 1); 245 return LastOpcFiltered; 246 } 247 // Return the filter chooser for the group of instructions without constant 248 // segment values. 249 const FilterChooser &getVariableFC() const { 250 assert(NumFiltered == 1); 251 assert(FilterChooserMap.size() == 1); 252 return *(FilterChooserMap.find((unsigned)-1)->second); 253 } 254 255 Filter(Filter &&f); 256 Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, bool mixed); 257 258 ~Filter(); 259 260 // Divides the decoding task into sub tasks and delegates them to the 261 // inferior FilterChooser's. 262 // 263 // A special case arises when there's only one entry in the filtered 264 // instructions. In order to unambiguously decode the singleton, we need to 265 // match the remaining undecoded encoding bits against the singleton. 266 void recurse(); 267 268 // Emit table entries to decode instructions given a segment or segments of 269 // bits. 270 void emitTableEntry(DecoderTableInfo &TableInfo) const; 271 272 // Returns the number of fanout produced by the filter. More fanout implies 273 // the filter distinguishes more categories of instructions. 274 unsigned usefulness() const; 275}; // End of class Filter 276} // End anonymous namespace 277 278// These are states of our finite state machines used in FilterChooser's 279// filterProcessor() which produces the filter candidates to use. 280typedef enum { 281 ATTR_NONE, 282 ATTR_FILTERED, 283 ATTR_ALL_SET, 284 ATTR_ALL_UNSET, 285 ATTR_MIXED 286} bitAttr_t; 287 288/// FilterChooser - FilterChooser chooses the best filter among a set of Filters 289/// in order to perform the decoding of instructions at the current level. 290/// 291/// Decoding proceeds from the top down. Based on the well-known encoding bits 292/// of instructions available, FilterChooser builds up the possible Filters that 293/// can further the task of decoding by distinguishing among the remaining 294/// candidate instructions. 295/// 296/// Once a filter has been chosen, it is called upon to divide the decoding task 297/// into sub-tasks and delegates them to its inferior FilterChoosers for further 298/// processings. 299/// 300/// It is useful to think of a Filter as governing the switch stmts of the 301/// decoding tree. And each case is delegated to an inferior FilterChooser to 302/// decide what further remaining bits to look at. 303namespace { 304class FilterChooser { 305protected: 306 friend class Filter; 307 308 // Vector of codegen instructions to choose our filter. 309 ArrayRef<const CodeGenInstruction *> AllInstructions; 310 311 // Vector of uid's for this filter chooser to work on. 312 const std::vector<unsigned> &Opcodes; 313 314 // Lookup table for the operand decoding of instructions. 315 const std::map<unsigned, std::vector<OperandInfo> > &Operands; 316 317 // Vector of candidate filters. 318 std::vector<Filter> Filters; 319 320 // Array of bit values passed down from our parent. 321 // Set to all BIT_UNFILTERED's for Parent == NULL. 322 std::vector<bit_value_t> FilterBitValues; 323 324 // Links to the FilterChooser above us in the decoding tree. 325 const FilterChooser *Parent; 326 327 // Index of the best filter from Filters. 328 int BestIndex; 329 330 // Width of instructions 331 unsigned BitWidth; 332 333 // Parent emitter 334 const FixedLenDecoderEmitter *Emitter; 335 336 FilterChooser(const FilterChooser &) = delete; 337 void operator=(const FilterChooser &) = delete; 338public: 339 340 FilterChooser(ArrayRef<const CodeGenInstruction *> Insts, 341 const std::vector<unsigned> &IDs, 342 const std::map<unsigned, std::vector<OperandInfo> > &Ops, 343 unsigned BW, 344 const FixedLenDecoderEmitter *E) 345 : AllInstructions(Insts), Opcodes(IDs), Operands(Ops), Filters(), 346 FilterBitValues(BW, BIT_UNFILTERED), Parent(nullptr), BestIndex(-1), 347 BitWidth(BW), Emitter(E) { 348 doFilter(); 349 } 350 351 FilterChooser(ArrayRef<const CodeGenInstruction *> Insts, 352 const std::vector<unsigned> &IDs, 353 const std::map<unsigned, std::vector<OperandInfo> > &Ops, 354 const std::vector<bit_value_t> &ParentFilterBitValues, 355 const FilterChooser &parent) 356 : AllInstructions(Insts), Opcodes(IDs), Operands(Ops), 357 Filters(), FilterBitValues(ParentFilterBitValues), 358 Parent(&parent), BestIndex(-1), BitWidth(parent.BitWidth), 359 Emitter(parent.Emitter) { 360 doFilter(); 361 } 362 363 unsigned getBitWidth() const { return BitWidth; } 364 365protected: 366 // Populates the insn given the uid. 367 void insnWithID(insn_t &Insn, unsigned Opcode) const { 368 BitsInit &Bits = getBitsField(*AllInstructions[Opcode]->TheDef, "Inst"); 369 370 // We may have a SoftFail bitmask, which specifies a mask where an encoding 371 // may differ from the value in "Inst" and yet still be valid, but the 372 // disassembler should return SoftFail instead of Success. 373 // 374 // This is used for marking UNPREDICTABLE instructions in the ARM world. 375 BitsInit *SFBits = 376 AllInstructions[Opcode]->TheDef->getValueAsBitsInit("SoftFail"); 377 378 for (unsigned i = 0; i < BitWidth; ++i) { 379 if (SFBits && bitFromBits(*SFBits, i) == BIT_TRUE) 380 Insn.push_back(BIT_UNSET); 381 else 382 Insn.push_back(bitFromBits(Bits, i)); 383 } 384 } 385 386 // Returns the record name. 387 const std::string &nameWithID(unsigned Opcode) const { 388 return AllInstructions[Opcode]->TheDef->getName(); 389 } 390 391 // Populates the field of the insn given the start position and the number of 392 // consecutive bits to scan for. 393 // 394 // Returns false if there exists any uninitialized bit value in the range. 395 // Returns true, otherwise. 396 bool fieldFromInsn(uint64_t &Field, insn_t &Insn, unsigned StartBit, 397 unsigned NumBits) const; 398 399 /// dumpFilterArray - dumpFilterArray prints out debugging info for the given 400 /// filter array as a series of chars. 401 void dumpFilterArray(raw_ostream &o, 402 const std::vector<bit_value_t> & filter) const; 403 404 /// dumpStack - dumpStack traverses the filter chooser chain and calls 405 /// dumpFilterArray on each filter chooser up to the top level one. 406 void dumpStack(raw_ostream &o, const char *prefix) const; 407 408 Filter &bestFilter() { 409 assert(BestIndex != -1 && "BestIndex not set"); 410 return Filters[BestIndex]; 411 } 412 413 bool PositionFiltered(unsigned i) const { 414 return ValueSet(FilterBitValues[i]); 415 } 416 417 // Calculates the island(s) needed to decode the instruction. 418 // This returns a lit of undecoded bits of an instructions, for example, 419 // Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be 420 // decoded bits in order to verify that the instruction matches the Opcode. 421 unsigned getIslands(std::vector<unsigned> &StartBits, 422 std::vector<unsigned> &EndBits, 423 std::vector<uint64_t> &FieldVals, 424 const insn_t &Insn) const; 425 426 // Emits code to check the Predicates member of an instruction are true. 427 // Returns true if predicate matches were emitted, false otherwise. 428 bool emitPredicateMatch(raw_ostream &o, unsigned &Indentation, 429 unsigned Opc) const; 430 431 bool doesOpcodeNeedPredicate(unsigned Opc) const; 432 unsigned getPredicateIndex(DecoderTableInfo &TableInfo, StringRef P) const; 433 void emitPredicateTableEntry(DecoderTableInfo &TableInfo, 434 unsigned Opc) const; 435 436 void emitSoftFailTableEntry(DecoderTableInfo &TableInfo, 437 unsigned Opc) const; 438 439 // Emits table entries to decode the singleton. 440 void emitSingletonTableEntry(DecoderTableInfo &TableInfo, 441 unsigned Opc) const; 442 443 // Emits code to decode the singleton, and then to decode the rest. 444 void emitSingletonTableEntry(DecoderTableInfo &TableInfo, 445 const Filter &Best) const; 446 447 void emitBinaryParser(raw_ostream &o, unsigned &Indentation, 448 const OperandInfo &OpInfo, 449 bool &OpHasCompleteDecoder) const; 450 451 void emitDecoder(raw_ostream &OS, unsigned Indentation, unsigned Opc, 452 bool &HasCompleteDecoder) const; 453 unsigned getDecoderIndex(DecoderSet &Decoders, unsigned Opc, 454 bool &HasCompleteDecoder) const; 455 456 // Assign a single filter and run with it. 457 void runSingleFilter(unsigned startBit, unsigned numBit, bool mixed); 458 459 // reportRegion is a helper function for filterProcessor to mark a region as 460 // eligible for use as a filter region. 461 void reportRegion(bitAttr_t RA, unsigned StartBit, unsigned BitIndex, 462 bool AllowMixed); 463 464 // FilterProcessor scans the well-known encoding bits of the instructions and 465 // builds up a list of candidate filters. It chooses the best filter and 466 // recursively descends down the decoding tree. 467 bool filterProcessor(bool AllowMixed, bool Greedy = true); 468 469 // Decides on the best configuration of filter(s) to use in order to decode 470 // the instructions. A conflict of instructions may occur, in which case we 471 // dump the conflict set to the standard error. 472 void doFilter(); 473 474public: 475 // emitTableEntries - Emit state machine entries to decode our share of 476 // instructions. 477 void emitTableEntries(DecoderTableInfo &TableInfo) const; 478}; 479} // End anonymous namespace 480 481/////////////////////////// 482// // 483// Filter Implementation // 484// // 485/////////////////////////// 486 487Filter::Filter(Filter &&f) 488 : Owner(f.Owner), StartBit(f.StartBit), NumBits(f.NumBits), Mixed(f.Mixed), 489 FilteredInstructions(std::move(f.FilteredInstructions)), 490 VariableInstructions(std::move(f.VariableInstructions)), 491 FilterChooserMap(std::move(f.FilterChooserMap)), NumFiltered(f.NumFiltered), 492 LastOpcFiltered(f.LastOpcFiltered) { 493} 494 495Filter::Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, 496 bool mixed) 497 : Owner(&owner), StartBit(startBit), NumBits(numBits), Mixed(mixed) { 498 assert(StartBit + NumBits - 1 < Owner->BitWidth); 499 500 NumFiltered = 0; 501 LastOpcFiltered = 0; 502 503 for (unsigned i = 0, e = Owner->Opcodes.size(); i != e; ++i) { 504 insn_t Insn; 505 506 // Populates the insn given the uid. 507 Owner->insnWithID(Insn, Owner->Opcodes[i]); 508 509 uint64_t Field; 510 // Scans the segment for possibly well-specified encoding bits. 511 bool ok = Owner->fieldFromInsn(Field, Insn, StartBit, NumBits); 512 513 if (ok) { 514 // The encoding bits are well-known. Lets add the uid of the 515 // instruction into the bucket keyed off the constant field value. 516 LastOpcFiltered = Owner->Opcodes[i]; 517 FilteredInstructions[Field].push_back(LastOpcFiltered); 518 ++NumFiltered; 519 } else { 520 // Some of the encoding bit(s) are unspecified. This contributes to 521 // one additional member of "Variable" instructions. 522 VariableInstructions.push_back(Owner->Opcodes[i]); 523 } 524 } 525 526 assert((FilteredInstructions.size() + VariableInstructions.size() > 0) 527 && "Filter returns no instruction categories"); 528} 529 530Filter::~Filter() { 531} 532 533// Divides the decoding task into sub tasks and delegates them to the 534// inferior FilterChooser's. 535// 536// A special case arises when there's only one entry in the filtered 537// instructions. In order to unambiguously decode the singleton, we need to 538// match the remaining undecoded encoding bits against the singleton. 539void Filter::recurse() { 540 // Starts by inheriting our parent filter chooser's filter bit values. 541 std::vector<bit_value_t> BitValueArray(Owner->FilterBitValues); 542 543 if (!VariableInstructions.empty()) { 544 // Conservatively marks each segment position as BIT_UNSET. 545 for (unsigned bitIndex = 0; bitIndex < NumBits; ++bitIndex) 546 BitValueArray[StartBit + bitIndex] = BIT_UNSET; 547 548 // Delegates to an inferior filter chooser for further processing on this 549 // group of instructions whose segment values are variable. 550 FilterChooserMap.insert( 551 std::make_pair(-1U, llvm::make_unique<FilterChooser>( 552 Owner->AllInstructions, VariableInstructions, 553 Owner->Operands, BitValueArray, *Owner))); 554 } 555 556 // No need to recurse for a singleton filtered instruction. 557 // See also Filter::emit*(). 558 if (getNumFiltered() == 1) { 559 assert(FilterChooserMap.size() == 1); 560 return; 561 } 562 563 // Otherwise, create sub choosers. 564 for (const auto &Inst : FilteredInstructions) { 565 566 // Marks all the segment positions with either BIT_TRUE or BIT_FALSE. 567 for (unsigned bitIndex = 0; bitIndex < NumBits; ++bitIndex) { 568 if (Inst.first & (1ULL << bitIndex)) 569 BitValueArray[StartBit + bitIndex] = BIT_TRUE; 570 else 571 BitValueArray[StartBit + bitIndex] = BIT_FALSE; 572 } 573 574 // Delegates to an inferior filter chooser for further processing on this 575 // category of instructions. 576 FilterChooserMap.insert(std::make_pair( 577 Inst.first, llvm::make_unique<FilterChooser>( 578 Owner->AllInstructions, Inst.second, 579 Owner->Operands, BitValueArray, *Owner))); 580 } 581} 582 583static void resolveTableFixups(DecoderTable &Table, const FixupList &Fixups, 584 uint32_t DestIdx) { 585 // Any NumToSkip fixups in the current scope can resolve to the 586 // current location. 587 for (FixupList::const_reverse_iterator I = Fixups.rbegin(), 588 E = Fixups.rend(); 589 I != E; ++I) { 590 // Calculate the distance from the byte following the fixup entry byte 591 // to the destination. The Target is calculated from after the 16-bit 592 // NumToSkip entry itself, so subtract two from the displacement here 593 // to account for that. 594 uint32_t FixupIdx = *I; 595 uint32_t Delta = DestIdx - FixupIdx - 2; 596 // Our NumToSkip entries are 16-bits. Make sure our table isn't too 597 // big. 598 assert(Delta < 65536U && "disassembler decoding table too large!"); 599 Table[FixupIdx] = (uint8_t)Delta; 600 Table[FixupIdx + 1] = (uint8_t)(Delta >> 8); 601 } 602} 603 604// Emit table entries to decode instructions given a segment or segments 605// of bits. 606void Filter::emitTableEntry(DecoderTableInfo &TableInfo) const { 607 TableInfo.Table.push_back(MCD::OPC_ExtractField); 608 TableInfo.Table.push_back(StartBit); 609 TableInfo.Table.push_back(NumBits); 610 611 // A new filter entry begins a new scope for fixup resolution. 612 TableInfo.FixupStack.emplace_back(); 613 614 DecoderTable &Table = TableInfo.Table; 615 616 size_t PrevFilter = 0; 617 bool HasFallthrough = false; 618 for (auto &Filter : FilterChooserMap) { 619 // Field value -1 implies a non-empty set of variable instructions. 620 // See also recurse(). 621 if (Filter.first == (unsigned)-1) { 622 HasFallthrough = true; 623 624 // Each scope should always have at least one filter value to check 625 // for. 626 assert(PrevFilter != 0 && "empty filter set!"); 627 FixupList &CurScope = TableInfo.FixupStack.back(); 628 // Resolve any NumToSkip fixups in the current scope. 629 resolveTableFixups(Table, CurScope, Table.size()); 630 CurScope.clear(); 631 PrevFilter = 0; // Don't re-process the filter's fallthrough. 632 } else { 633 Table.push_back(MCD::OPC_FilterValue); 634 // Encode and emit the value to filter against. 635 uint8_t Buffer[8]; 636 unsigned Len = encodeULEB128(Filter.first, Buffer); 637 Table.insert(Table.end(), Buffer, Buffer + Len); 638 // Reserve space for the NumToSkip entry. We'll backpatch the value 639 // later. 640 PrevFilter = Table.size(); 641 Table.push_back(0); 642 Table.push_back(0); 643 } 644 645 // We arrive at a category of instructions with the same segment value. 646 // Now delegate to the sub filter chooser for further decodings. 647 // The case may fallthrough, which happens if the remaining well-known 648 // encoding bits do not match exactly. 649 Filter.second->emitTableEntries(TableInfo); 650 651 // Now that we've emitted the body of the handler, update the NumToSkip 652 // of the filter itself to be able to skip forward when false. Subtract 653 // two as to account for the width of the NumToSkip field itself. 654 if (PrevFilter) { 655 uint32_t NumToSkip = Table.size() - PrevFilter - 2; 656 assert(NumToSkip < 65536U && "disassembler decoding table too large!"); 657 Table[PrevFilter] = (uint8_t)NumToSkip; 658 Table[PrevFilter + 1] = (uint8_t)(NumToSkip >> 8); 659 } 660 } 661 662 // Any remaining unresolved fixups bubble up to the parent fixup scope. 663 assert(TableInfo.FixupStack.size() > 1 && "fixup stack underflow!"); 664 FixupScopeList::iterator Source = TableInfo.FixupStack.end() - 1; 665 FixupScopeList::iterator Dest = Source - 1; 666 Dest->insert(Dest->end(), Source->begin(), Source->end()); 667 TableInfo.FixupStack.pop_back(); 668 669 // If there is no fallthrough, then the final filter should get fixed 670 // up according to the enclosing scope rather than the current position. 671 if (!HasFallthrough) 672 TableInfo.FixupStack.back().push_back(PrevFilter); 673} 674 675// Returns the number of fanout produced by the filter. More fanout implies 676// the filter distinguishes more categories of instructions. 677unsigned Filter::usefulness() const { 678 if (!VariableInstructions.empty()) 679 return FilteredInstructions.size(); 680 else 681 return FilteredInstructions.size() + 1; 682} 683 684////////////////////////////////// 685// // 686// Filterchooser Implementation // 687// // 688////////////////////////////////// 689 690// Emit the decoder state machine table. 691void FixedLenDecoderEmitter::emitTable(formatted_raw_ostream &OS, 692 DecoderTable &Table, 693 unsigned Indentation, 694 unsigned BitWidth, 695 StringRef Namespace) const { 696 OS.indent(Indentation) << "static const uint8_t DecoderTable" << Namespace 697 << BitWidth << "[] = {\n"; 698 699 Indentation += 2; 700 701 // FIXME: We may be able to use the NumToSkip values to recover 702 // appropriate indentation levels. 703 DecoderTable::const_iterator I = Table.begin(); 704 DecoderTable::const_iterator E = Table.end(); 705 while (I != E) { 706 assert (I < E && "incomplete decode table entry!"); 707 708 uint64_t Pos = I - Table.begin(); 709 OS << "/* " << Pos << " */"; 710 OS.PadToColumn(12); 711 712 switch (*I) { 713 default: 714 PrintFatalError("invalid decode table opcode"); 715 case MCD::OPC_ExtractField: { 716 ++I; 717 unsigned Start = *I++; 718 unsigned Len = *I++; 719 OS.indent(Indentation) << "MCD::OPC_ExtractField, " << Start << ", " 720 << Len << ", // Inst{"; 721 if (Len > 1) 722 OS << (Start + Len - 1) << "-"; 723 OS << Start << "} ...\n"; 724 break; 725 } 726 case MCD::OPC_FilterValue: { 727 ++I; 728 OS.indent(Indentation) << "MCD::OPC_FilterValue, "; 729 // The filter value is ULEB128 encoded. 730 while (*I >= 128) 731 OS << (unsigned)*I++ << ", "; 732 OS << (unsigned)*I++ << ", "; 733 734 // 16-bit numtoskip value. 735 uint8_t Byte = *I++; 736 uint32_t NumToSkip = Byte; 737 OS << (unsigned)Byte << ", "; 738 Byte = *I++; 739 OS << (unsigned)Byte << ", "; 740 NumToSkip |= Byte << 8; 741 OS << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; 742 break; 743 } 744 case MCD::OPC_CheckField: { 745 ++I; 746 unsigned Start = *I++; 747 unsigned Len = *I++; 748 OS.indent(Indentation) << "MCD::OPC_CheckField, " << Start << ", " 749 << Len << ", ";// << Val << ", " << NumToSkip << ",\n"; 750 // ULEB128 encoded field value. 751 for (; *I >= 128; ++I) 752 OS << (unsigned)*I << ", "; 753 OS << (unsigned)*I++ << ", "; 754 // 16-bit numtoskip value. 755 uint8_t Byte = *I++; 756 uint32_t NumToSkip = Byte; 757 OS << (unsigned)Byte << ", "; 758 Byte = *I++; 759 OS << (unsigned)Byte << ", "; 760 NumToSkip |= Byte << 8; 761 OS << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; 762 break; 763 } 764 case MCD::OPC_CheckPredicate: { 765 ++I; 766 OS.indent(Indentation) << "MCD::OPC_CheckPredicate, "; 767 for (; *I >= 128; ++I) 768 OS << (unsigned)*I << ", "; 769 OS << (unsigned)*I++ << ", "; 770 771 // 16-bit numtoskip value. 772 uint8_t Byte = *I++; 773 uint32_t NumToSkip = Byte; 774 OS << (unsigned)Byte << ", "; 775 Byte = *I++; 776 OS << (unsigned)Byte << ", "; 777 NumToSkip |= Byte << 8; 778 OS << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; 779 break; 780 } 781 case MCD::OPC_Decode: 782 case MCD::OPC_TryDecode: { 783 bool IsTry = *I == MCD::OPC_TryDecode; 784 ++I; 785 // Extract the ULEB128 encoded Opcode to a buffer. 786 uint8_t Buffer[8], *p = Buffer; 787 while ((*p++ = *I++) >= 128) 788 assert((p - Buffer) <= (ptrdiff_t)sizeof(Buffer) 789 && "ULEB128 value too large!"); 790 // Decode the Opcode value. 791 unsigned Opc = decodeULEB128(Buffer); 792 OS.indent(Indentation) << "MCD::OPC_" << (IsTry ? "Try" : "") 793 << "Decode, "; 794 for (p = Buffer; *p >= 128; ++p) 795 OS << (unsigned)*p << ", "; 796 OS << (unsigned)*p << ", "; 797 798 // Decoder index. 799 for (; *I >= 128; ++I) 800 OS << (unsigned)*I << ", "; 801 OS << (unsigned)*I++ << ", "; 802 803 if (!IsTry) { 804 OS << "// Opcode: " 805 << NumberedInstructions[Opc]->TheDef->getName() << "\n"; 806 break; 807 } 808 809 // Fallthrough for OPC_TryDecode. 810 811 // 16-bit numtoskip value. 812 uint8_t Byte = *I++; 813 uint32_t NumToSkip = Byte; 814 OS << (unsigned)Byte << ", "; 815 Byte = *I++; 816 OS << (unsigned)Byte << ", "; 817 NumToSkip |= Byte << 8; 818 819 OS << "// Opcode: " 820 << NumberedInstructions[Opc]->TheDef->getName() 821 << ", skip to: " << ((I - Table.begin()) + NumToSkip) << "\n"; 822 break; 823 } 824 case MCD::OPC_SoftFail: { 825 ++I; 826 OS.indent(Indentation) << "MCD::OPC_SoftFail"; 827 // Positive mask 828 uint64_t Value = 0; 829 unsigned Shift = 0; 830 do { 831 OS << ", " << (unsigned)*I; 832 Value += (*I & 0x7f) << Shift; 833 Shift += 7; 834 } while (*I++ >= 128); 835 if (Value > 127) { 836 OS << " /* 0x"; 837 OS.write_hex(Value); 838 OS << " */"; 839 } 840 // Negative mask 841 Value = 0; 842 Shift = 0; 843 do { 844 OS << ", " << (unsigned)*I; 845 Value += (*I & 0x7f) << Shift; 846 Shift += 7; 847 } while (*I++ >= 128); 848 if (Value > 127) { 849 OS << " /* 0x"; 850 OS.write_hex(Value); 851 OS << " */"; 852 } 853 OS << ",\n"; 854 break; 855 } 856 case MCD::OPC_Fail: { 857 ++I; 858 OS.indent(Indentation) << "MCD::OPC_Fail,\n"; 859 break; 860 } 861 } 862 } 863 OS.indent(Indentation) << "0\n"; 864 865 Indentation -= 2; 866 867 OS.indent(Indentation) << "};\n\n"; 868} 869 870void FixedLenDecoderEmitter:: 871emitPredicateFunction(formatted_raw_ostream &OS, PredicateSet &Predicates, 872 unsigned Indentation) const { 873 // The predicate function is just a big switch statement based on the 874 // input predicate index. 875 OS.indent(Indentation) << "static bool checkDecoderPredicate(unsigned Idx, " 876 << "const FeatureBitset& Bits) {\n"; 877 Indentation += 2; 878 if (!Predicates.empty()) { 879 OS.indent(Indentation) << "switch (Idx) {\n"; 880 OS.indent(Indentation) << "default: llvm_unreachable(\"Invalid index!\");\n"; 881 unsigned Index = 0; 882 for (const auto &Predicate : Predicates) { 883 OS.indent(Indentation) << "case " << Index++ << ":\n"; 884 OS.indent(Indentation+2) << "return (" << Predicate << ");\n"; 885 } 886 OS.indent(Indentation) << "}\n"; 887 } else { 888 // No case statement to emit 889 OS.indent(Indentation) << "llvm_unreachable(\"Invalid index!\");\n"; 890 } 891 Indentation -= 2; 892 OS.indent(Indentation) << "}\n\n"; 893} 894 895void FixedLenDecoderEmitter:: 896emitDecoderFunction(formatted_raw_ostream &OS, DecoderSet &Decoders, 897 unsigned Indentation) const { 898 // The decoder function is just a big switch statement based on the 899 // input decoder index. 900 OS.indent(Indentation) << "template<typename InsnType>\n"; 901 OS.indent(Indentation) << "static DecodeStatus decodeToMCInst(DecodeStatus S," 902 << " unsigned Idx, InsnType insn, MCInst &MI,\n"; 903 OS.indent(Indentation) << " uint64_t " 904 << "Address, const void *Decoder, bool &DecodeComplete) {\n"; 905 Indentation += 2; 906 OS.indent(Indentation) << "DecodeComplete = true;\n"; 907 OS.indent(Indentation) << "InsnType tmp;\n"; 908 OS.indent(Indentation) << "switch (Idx) {\n"; 909 OS.indent(Indentation) << "default: llvm_unreachable(\"Invalid index!\");\n"; 910 unsigned Index = 0; 911 for (const auto &Decoder : Decoders) { 912 OS.indent(Indentation) << "case " << Index++ << ":\n"; 913 OS << Decoder; 914 OS.indent(Indentation+2) << "return S;\n"; 915 } 916 OS.indent(Indentation) << "}\n"; 917 Indentation -= 2; 918 OS.indent(Indentation) << "}\n\n"; 919} 920 921// Populates the field of the insn given the start position and the number of 922// consecutive bits to scan for. 923// 924// Returns false if and on the first uninitialized bit value encountered. 925// Returns true, otherwise. 926bool FilterChooser::fieldFromInsn(uint64_t &Field, insn_t &Insn, 927 unsigned StartBit, unsigned NumBits) const { 928 Field = 0; 929 930 for (unsigned i = 0; i < NumBits; ++i) { 931 if (Insn[StartBit + i] == BIT_UNSET) 932 return false; 933 934 if (Insn[StartBit + i] == BIT_TRUE) 935 Field = Field | (1ULL << i); 936 } 937 938 return true; 939} 940 941/// dumpFilterArray - dumpFilterArray prints out debugging info for the given 942/// filter array as a series of chars. 943void FilterChooser::dumpFilterArray(raw_ostream &o, 944 const std::vector<bit_value_t> &filter) const { 945 for (unsigned bitIndex = BitWidth; bitIndex > 0; bitIndex--) { 946 switch (filter[bitIndex - 1]) { 947 case BIT_UNFILTERED: 948 o << "."; 949 break; 950 case BIT_UNSET: 951 o << "_"; 952 break; 953 case BIT_TRUE: 954 o << "1"; 955 break; 956 case BIT_FALSE: 957 o << "0"; 958 break; 959 } 960 } 961} 962 963/// dumpStack - dumpStack traverses the filter chooser chain and calls 964/// dumpFilterArray on each filter chooser up to the top level one. 965void FilterChooser::dumpStack(raw_ostream &o, const char *prefix) const { 966 const FilterChooser *current = this; 967 968 while (current) { 969 o << prefix; 970 dumpFilterArray(o, current->FilterBitValues); 971 o << '\n'; 972 current = current->Parent; 973 } 974} 975 976// Calculates the island(s) needed to decode the instruction. 977// This returns a list of undecoded bits of an instructions, for example, 978// Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be 979// decoded bits in order to verify that the instruction matches the Opcode. 980unsigned FilterChooser::getIslands(std::vector<unsigned> &StartBits, 981 std::vector<unsigned> &EndBits, 982 std::vector<uint64_t> &FieldVals, 983 const insn_t &Insn) const { 984 unsigned Num, BitNo; 985 Num = BitNo = 0; 986 987 uint64_t FieldVal = 0; 988 989 // 0: Init 990 // 1: Water (the bit value does not affect decoding) 991 // 2: Island (well-known bit value needed for decoding) 992 int State = 0; 993 int Val = -1; 994 995 for (unsigned i = 0; i < BitWidth; ++i) { 996 Val = Value(Insn[i]); 997 bool Filtered = PositionFiltered(i); 998 switch (State) { 999 default: llvm_unreachable("Unreachable code!"); 1000 case 0: 1001 case 1: 1002 if (Filtered || Val == -1) 1003 State = 1; // Still in Water 1004 else { 1005 State = 2; // Into the Island 1006 BitNo = 0; 1007 StartBits.push_back(i); 1008 FieldVal = Val; 1009 } 1010 break; 1011 case 2: 1012 if (Filtered || Val == -1) { 1013 State = 1; // Into the Water 1014 EndBits.push_back(i - 1); 1015 FieldVals.push_back(FieldVal); 1016 ++Num; 1017 } else { 1018 State = 2; // Still in Island 1019 ++BitNo; 1020 FieldVal = FieldVal | Val << BitNo; 1021 } 1022 break; 1023 } 1024 } 1025 // If we are still in Island after the loop, do some housekeeping. 1026 if (State == 2) { 1027 EndBits.push_back(BitWidth - 1); 1028 FieldVals.push_back(FieldVal); 1029 ++Num; 1030 } 1031 1032 assert(StartBits.size() == Num && EndBits.size() == Num && 1033 FieldVals.size() == Num); 1034 return Num; 1035} 1036 1037void FilterChooser::emitBinaryParser(raw_ostream &o, unsigned &Indentation, 1038 const OperandInfo &OpInfo, 1039 bool &OpHasCompleteDecoder) const { 1040 const std::string &Decoder = OpInfo.Decoder; 1041 1042 if (OpInfo.numFields() != 1) 1043 o.indent(Indentation) << "tmp = 0;\n"; 1044 1045 for (const EncodingField &EF : OpInfo) { 1046 o.indent(Indentation) << "tmp "; 1047 if (OpInfo.numFields() != 1) o << '|'; 1048 o << "= fieldFromInstruction" 1049 << "(insn, " << EF.Base << ", " << EF.Width << ')'; 1050 if (OpInfo.numFields() != 1 || EF.Offset != 0) 1051 o << " << " << EF.Offset; 1052 o << ";\n"; 1053 } 1054 1055 if (Decoder != "") { 1056 OpHasCompleteDecoder = OpInfo.HasCompleteDecoder; 1057 o.indent(Indentation) << Emitter->GuardPrefix << Decoder 1058 << "(MI, tmp, Address, Decoder)" 1059 << Emitter->GuardPostfix 1060 << " { " << (OpHasCompleteDecoder ? "" : "DecodeComplete = false; ") 1061 << "return MCDisassembler::Fail; }\n"; 1062 } else { 1063 OpHasCompleteDecoder = true; 1064 o.indent(Indentation) << "MI.addOperand(MCOperand::createImm(tmp));\n"; 1065 } 1066} 1067 1068void FilterChooser::emitDecoder(raw_ostream &OS, unsigned Indentation, 1069 unsigned Opc, bool &HasCompleteDecoder) const { 1070 HasCompleteDecoder = true; 1071 1072 for (const auto &Op : Operands.find(Opc)->second) { 1073 // If a custom instruction decoder was specified, use that. 1074 if (Op.numFields() == 0 && Op.Decoder.size()) { 1075 HasCompleteDecoder = Op.HasCompleteDecoder; 1076 OS.indent(Indentation) << Emitter->GuardPrefix << Op.Decoder 1077 << "(MI, insn, Address, Decoder)" 1078 << Emitter->GuardPostfix 1079 << " { " << (HasCompleteDecoder ? "" : "DecodeComplete = false; ") 1080 << "return MCDisassembler::Fail; }\n"; 1081 break; 1082 } 1083 1084 bool OpHasCompleteDecoder; 1085 emitBinaryParser(OS, Indentation, Op, OpHasCompleteDecoder); 1086 if (!OpHasCompleteDecoder) 1087 HasCompleteDecoder = false; 1088 } 1089} 1090 1091unsigned FilterChooser::getDecoderIndex(DecoderSet &Decoders, 1092 unsigned Opc, 1093 bool &HasCompleteDecoder) const { 1094 // Build up the predicate string. 1095 SmallString<256> Decoder; 1096 // FIXME: emitDecoder() function can take a buffer directly rather than 1097 // a stream. 1098 raw_svector_ostream S(Decoder); 1099 unsigned I = 4; 1100 emitDecoder(S, I, Opc, HasCompleteDecoder); 1101 1102 // Using the full decoder string as the key value here is a bit 1103 // heavyweight, but is effective. If the string comparisons become a 1104 // performance concern, we can implement a mangling of the predicate 1105 // data easily enough with a map back to the actual string. That's 1106 // overkill for now, though. 1107 1108 // Make sure the predicate is in the table. 1109 Decoders.insert(StringRef(Decoder)); 1110 // Now figure out the index for when we write out the table. 1111 DecoderSet::const_iterator P = std::find(Decoders.begin(), 1112 Decoders.end(), 1113 Decoder.str()); 1114 return (unsigned)(P - Decoders.begin()); 1115} 1116 1117static void emitSinglePredicateMatch(raw_ostream &o, StringRef str, 1118 const std::string &PredicateNamespace) { 1119 if (str[0] == '!') 1120 o << "!Bits[" << PredicateNamespace << "::" 1121 << str.slice(1,str.size()) << "]"; 1122 else 1123 o << "Bits[" << PredicateNamespace << "::" << str << "]"; 1124} 1125 1126bool FilterChooser::emitPredicateMatch(raw_ostream &o, unsigned &Indentation, 1127 unsigned Opc) const { 1128 ListInit *Predicates = 1129 AllInstructions[Opc]->TheDef->getValueAsListInit("Predicates"); 1130 bool IsFirstEmission = true; 1131 for (unsigned i = 0; i < Predicates->size(); ++i) { 1132 Record *Pred = Predicates->getElementAsRecord(i); 1133 if (!Pred->getValue("AssemblerMatcherPredicate")) 1134 continue; 1135 1136 std::string P = Pred->getValueAsString("AssemblerCondString"); 1137 1138 if (!P.length()) 1139 continue; 1140 1141 if (!IsFirstEmission) 1142 o << " && "; 1143 1144 StringRef SR(P); 1145 std::pair<StringRef, StringRef> pairs = SR.split(','); 1146 while (pairs.second.size()) { 1147 emitSinglePredicateMatch(o, pairs.first, Emitter->PredicateNamespace); 1148 o << " && "; 1149 pairs = pairs.second.split(','); 1150 } 1151 emitSinglePredicateMatch(o, pairs.first, Emitter->PredicateNamespace); 1152 IsFirstEmission = false; 1153 } 1154 return !Predicates->empty(); 1155} 1156 1157bool FilterChooser::doesOpcodeNeedPredicate(unsigned Opc) const { 1158 ListInit *Predicates = 1159 AllInstructions[Opc]->TheDef->getValueAsListInit("Predicates"); 1160 for (unsigned i = 0; i < Predicates->size(); ++i) { 1161 Record *Pred = Predicates->getElementAsRecord(i); 1162 if (!Pred->getValue("AssemblerMatcherPredicate")) 1163 continue; 1164 1165 std::string P = Pred->getValueAsString("AssemblerCondString"); 1166 1167 if (!P.length()) 1168 continue; 1169 1170 return true; 1171 } 1172 return false; 1173} 1174 1175unsigned FilterChooser::getPredicateIndex(DecoderTableInfo &TableInfo, 1176 StringRef Predicate) const { 1177 // Using the full predicate string as the key value here is a bit 1178 // heavyweight, but is effective. If the string comparisons become a 1179 // performance concern, we can implement a mangling of the predicate 1180 // data easily enough with a map back to the actual string. That's 1181 // overkill for now, though. 1182 1183 // Make sure the predicate is in the table. 1184 TableInfo.Predicates.insert(Predicate.str()); 1185 // Now figure out the index for when we write out the table. 1186 PredicateSet::const_iterator P = std::find(TableInfo.Predicates.begin(), 1187 TableInfo.Predicates.end(), 1188 Predicate.str()); 1189 return (unsigned)(P - TableInfo.Predicates.begin()); 1190} 1191 1192void FilterChooser::emitPredicateTableEntry(DecoderTableInfo &TableInfo, 1193 unsigned Opc) const { 1194 if (!doesOpcodeNeedPredicate(Opc)) 1195 return; 1196 1197 // Build up the predicate string. 1198 SmallString<256> Predicate; 1199 // FIXME: emitPredicateMatch() functions can take a buffer directly rather 1200 // than a stream. 1201 raw_svector_ostream PS(Predicate); 1202 unsigned I = 0; 1203 emitPredicateMatch(PS, I, Opc); 1204 1205 // Figure out the index into the predicate table for the predicate just 1206 // computed. 1207 unsigned PIdx = getPredicateIndex(TableInfo, PS.str()); 1208 SmallString<16> PBytes; 1209 raw_svector_ostream S(PBytes); 1210 encodeULEB128(PIdx, S); 1211 1212 TableInfo.Table.push_back(MCD::OPC_CheckPredicate); 1213 // Predicate index 1214 for (unsigned i = 0, e = PBytes.size(); i != e; ++i) 1215 TableInfo.Table.push_back(PBytes[i]); 1216 // Push location for NumToSkip backpatching. 1217 TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); 1218 TableInfo.Table.push_back(0); 1219 TableInfo.Table.push_back(0); 1220} 1221 1222void FilterChooser::emitSoftFailTableEntry(DecoderTableInfo &TableInfo, 1223 unsigned Opc) const { 1224 BitsInit *SFBits = 1225 AllInstructions[Opc]->TheDef->getValueAsBitsInit("SoftFail"); 1226 if (!SFBits) return; 1227 BitsInit *InstBits = AllInstructions[Opc]->TheDef->getValueAsBitsInit("Inst"); 1228 1229 APInt PositiveMask(BitWidth, 0ULL); 1230 APInt NegativeMask(BitWidth, 0ULL); 1231 for (unsigned i = 0; i < BitWidth; ++i) { 1232 bit_value_t B = bitFromBits(*SFBits, i); 1233 bit_value_t IB = bitFromBits(*InstBits, i); 1234 1235 if (B != BIT_TRUE) continue; 1236 1237 switch (IB) { 1238 case BIT_FALSE: 1239 // The bit is meant to be false, so emit a check to see if it is true. 1240 PositiveMask.setBit(i); 1241 break; 1242 case BIT_TRUE: 1243 // The bit is meant to be true, so emit a check to see if it is false. 1244 NegativeMask.setBit(i); 1245 break; 1246 default: 1247 // The bit is not set; this must be an error! 1248 StringRef Name = AllInstructions[Opc]->TheDef->getName(); 1249 errs() << "SoftFail Conflict: bit SoftFail{" << i << "} in " << Name 1250 << " is set but Inst{" << i << "} is unset!\n" 1251 << " - You can only mark a bit as SoftFail if it is fully defined" 1252 << " (1/0 - not '?') in Inst\n"; 1253 return; 1254 } 1255 } 1256 1257 bool NeedPositiveMask = PositiveMask.getBoolValue(); 1258 bool NeedNegativeMask = NegativeMask.getBoolValue(); 1259 1260 if (!NeedPositiveMask && !NeedNegativeMask) 1261 return; 1262 1263 TableInfo.Table.push_back(MCD::OPC_SoftFail); 1264 1265 SmallString<16> MaskBytes; 1266 raw_svector_ostream S(MaskBytes); 1267 if (NeedPositiveMask) { 1268 encodeULEB128(PositiveMask.getZExtValue(), S); 1269 for (unsigned i = 0, e = MaskBytes.size(); i != e; ++i) 1270 TableInfo.Table.push_back(MaskBytes[i]); 1271 } else 1272 TableInfo.Table.push_back(0); 1273 if (NeedNegativeMask) { 1274 MaskBytes.clear(); 1275 encodeULEB128(NegativeMask.getZExtValue(), S); 1276 for (unsigned i = 0, e = MaskBytes.size(); i != e; ++i) 1277 TableInfo.Table.push_back(MaskBytes[i]); 1278 } else 1279 TableInfo.Table.push_back(0); 1280} 1281 1282// Emits table entries to decode the singleton. 1283void FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo, 1284 unsigned Opc) const { 1285 std::vector<unsigned> StartBits; 1286 std::vector<unsigned> EndBits; 1287 std::vector<uint64_t> FieldVals; 1288 insn_t Insn; 1289 insnWithID(Insn, Opc); 1290 1291 // Look for islands of undecoded bits of the singleton. 1292 getIslands(StartBits, EndBits, FieldVals, Insn); 1293 1294 unsigned Size = StartBits.size(); 1295 1296 // Emit the predicate table entry if one is needed. 1297 emitPredicateTableEntry(TableInfo, Opc); 1298 1299 // Check any additional encoding fields needed. 1300 for (unsigned I = Size; I != 0; --I) { 1301 unsigned NumBits = EndBits[I-1] - StartBits[I-1] + 1; 1302 TableInfo.Table.push_back(MCD::OPC_CheckField); 1303 TableInfo.Table.push_back(StartBits[I-1]); 1304 TableInfo.Table.push_back(NumBits); 1305 uint8_t Buffer[8], *p; 1306 encodeULEB128(FieldVals[I-1], Buffer); 1307 for (p = Buffer; *p >= 128 ; ++p) 1308 TableInfo.Table.push_back(*p); 1309 TableInfo.Table.push_back(*p); 1310 // Push location for NumToSkip backpatching. 1311 TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); 1312 // The fixup is always 16-bits, so go ahead and allocate the space 1313 // in the table so all our relative position calculations work OK even 1314 // before we fully resolve the real value here. 1315 TableInfo.Table.push_back(0); 1316 TableInfo.Table.push_back(0); 1317 } 1318 1319 // Check for soft failure of the match. 1320 emitSoftFailTableEntry(TableInfo, Opc); 1321 1322 bool HasCompleteDecoder; 1323 unsigned DIdx = getDecoderIndex(TableInfo.Decoders, Opc, HasCompleteDecoder); 1324 1325 // Produce OPC_Decode or OPC_TryDecode opcode based on the information 1326 // whether the instruction decoder is complete or not. If it is complete 1327 // then it handles all possible values of remaining variable/unfiltered bits 1328 // and for any value can determine if the bitpattern is a valid instruction 1329 // or not. This means OPC_Decode will be the final step in the decoding 1330 // process. If it is not complete, then the Fail return code from the 1331 // decoder method indicates that additional processing should be done to see 1332 // if there is any other instruction that also matches the bitpattern and 1333 // can decode it. 1334 TableInfo.Table.push_back(HasCompleteDecoder ? MCD::OPC_Decode : 1335 MCD::OPC_TryDecode); 1336 uint8_t Buffer[8], *p; 1337 encodeULEB128(Opc, Buffer); 1338 for (p = Buffer; *p >= 128 ; ++p) 1339 TableInfo.Table.push_back(*p); 1340 TableInfo.Table.push_back(*p); 1341 1342 SmallString<16> Bytes; 1343 raw_svector_ostream S(Bytes); 1344 encodeULEB128(DIdx, S); 1345 1346 // Decoder index 1347 for (unsigned i = 0, e = Bytes.size(); i != e; ++i) 1348 TableInfo.Table.push_back(Bytes[i]); 1349 1350 if (!HasCompleteDecoder) { 1351 // Push location for NumToSkip backpatching. 1352 TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); 1353 // Allocate the space for the fixup. 1354 TableInfo.Table.push_back(0); 1355 TableInfo.Table.push_back(0); 1356 } 1357} 1358 1359// Emits table entries to decode the singleton, and then to decode the rest. 1360void FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo, 1361 const Filter &Best) const { 1362 unsigned Opc = Best.getSingletonOpc(); 1363 1364 // complex singletons need predicate checks from the first singleton 1365 // to refer forward to the variable filterchooser that follows. 1366 TableInfo.FixupStack.emplace_back(); 1367 1368 emitSingletonTableEntry(TableInfo, Opc); 1369 1370 resolveTableFixups(TableInfo.Table, TableInfo.FixupStack.back(), 1371 TableInfo.Table.size()); 1372 TableInfo.FixupStack.pop_back(); 1373 1374 Best.getVariableFC().emitTableEntries(TableInfo); 1375} 1376 1377 1378// Assign a single filter and run with it. Top level API client can initialize 1379// with a single filter to start the filtering process. 1380void FilterChooser::runSingleFilter(unsigned startBit, unsigned numBit, 1381 bool mixed) { 1382 Filters.clear(); 1383 Filters.emplace_back(*this, startBit, numBit, true); 1384 BestIndex = 0; // Sole Filter instance to choose from. 1385 bestFilter().recurse(); 1386} 1387 1388// reportRegion is a helper function for filterProcessor to mark a region as 1389// eligible for use as a filter region. 1390void FilterChooser::reportRegion(bitAttr_t RA, unsigned StartBit, 1391 unsigned BitIndex, bool AllowMixed) { 1392 if (RA == ATTR_MIXED && AllowMixed) 1393 Filters.emplace_back(*this, StartBit, BitIndex - StartBit, true); 1394 else if (RA == ATTR_ALL_SET && !AllowMixed) 1395 Filters.emplace_back(*this, StartBit, BitIndex - StartBit, false); 1396} 1397 1398// FilterProcessor scans the well-known encoding bits of the instructions and 1399// builds up a list of candidate filters. It chooses the best filter and 1400// recursively descends down the decoding tree. 1401bool FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { 1402 Filters.clear(); 1403 BestIndex = -1; 1404 unsigned numInstructions = Opcodes.size(); 1405 1406 assert(numInstructions && "Filter created with no instructions"); 1407 1408 // No further filtering is necessary. 1409 if (numInstructions == 1) 1410 return true; 1411 1412 // Heuristics. See also doFilter()'s "Heuristics" comment when num of 1413 // instructions is 3. 1414 if (AllowMixed && !Greedy) { 1415 assert(numInstructions == 3); 1416 1417 for (unsigned i = 0; i < Opcodes.size(); ++i) { 1418 std::vector<unsigned> StartBits; 1419 std::vector<unsigned> EndBits; 1420 std::vector<uint64_t> FieldVals; 1421 insn_t Insn; 1422 1423 insnWithID(Insn, Opcodes[i]); 1424 1425 // Look for islands of undecoded bits of any instruction. 1426 if (getIslands(StartBits, EndBits, FieldVals, Insn) > 0) { 1427 // Found an instruction with island(s). Now just assign a filter. 1428 runSingleFilter(StartBits[0], EndBits[0] - StartBits[0] + 1, true); 1429 return true; 1430 } 1431 } 1432 } 1433 1434 unsigned BitIndex; 1435 1436 // We maintain BIT_WIDTH copies of the bitAttrs automaton. 1437 // The automaton consumes the corresponding bit from each 1438 // instruction. 1439 // 1440 // Input symbols: 0, 1, and _ (unset). 1441 // States: NONE, FILTERED, ALL_SET, ALL_UNSET, and MIXED. 1442 // Initial state: NONE. 1443 // 1444 // (NONE) ------- [01] -> (ALL_SET) 1445 // (NONE) ------- _ ----> (ALL_UNSET) 1446 // (ALL_SET) ---- [01] -> (ALL_SET) 1447 // (ALL_SET) ---- _ ----> (MIXED) 1448 // (ALL_UNSET) -- [01] -> (MIXED) 1449 // (ALL_UNSET) -- _ ----> (ALL_UNSET) 1450 // (MIXED) ------ . ----> (MIXED) 1451 // (FILTERED)---- . ----> (FILTERED) 1452 1453 std::vector<bitAttr_t> bitAttrs; 1454 1455 // FILTERED bit positions provide no entropy and are not worthy of pursuing. 1456 // Filter::recurse() set either BIT_TRUE or BIT_FALSE for each position. 1457 for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) 1458 if (FilterBitValues[BitIndex] == BIT_TRUE || 1459 FilterBitValues[BitIndex] == BIT_FALSE) 1460 bitAttrs.push_back(ATTR_FILTERED); 1461 else 1462 bitAttrs.push_back(ATTR_NONE); 1463 1464 for (unsigned InsnIndex = 0; InsnIndex < numInstructions; ++InsnIndex) { 1465 insn_t insn; 1466 1467 insnWithID(insn, Opcodes[InsnIndex]); 1468 1469 for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { 1470 switch (bitAttrs[BitIndex]) { 1471 case ATTR_NONE: 1472 if (insn[BitIndex] == BIT_UNSET) 1473 bitAttrs[BitIndex] = ATTR_ALL_UNSET; 1474 else 1475 bitAttrs[BitIndex] = ATTR_ALL_SET; 1476 break; 1477 case ATTR_ALL_SET: 1478 if (insn[BitIndex] == BIT_UNSET) 1479 bitAttrs[BitIndex] = ATTR_MIXED; 1480 break; 1481 case ATTR_ALL_UNSET: 1482 if (insn[BitIndex] != BIT_UNSET) 1483 bitAttrs[BitIndex] = ATTR_MIXED; 1484 break; 1485 case ATTR_MIXED: 1486 case ATTR_FILTERED: 1487 break; 1488 } 1489 } 1490 } 1491 1492 // The regionAttr automaton consumes the bitAttrs automatons' state, 1493 // lowest-to-highest. 1494 // 1495 // Input symbols: F(iltered), (all_)S(et), (all_)U(nset), M(ixed) 1496 // States: NONE, ALL_SET, MIXED 1497 // Initial state: NONE 1498 // 1499 // (NONE) ----- F --> (NONE) 1500 // (NONE) ----- S --> (ALL_SET) ; and set region start 1501 // (NONE) ----- U --> (NONE) 1502 // (NONE) ----- M --> (MIXED) ; and set region start 1503 // (ALL_SET) -- F --> (NONE) ; and report an ALL_SET region 1504 // (ALL_SET) -- S --> (ALL_SET) 1505 // (ALL_SET) -- U --> (NONE) ; and report an ALL_SET region 1506 // (ALL_SET) -- M --> (MIXED) ; and report an ALL_SET region 1507 // (MIXED) ---- F --> (NONE) ; and report a MIXED region 1508 // (MIXED) ---- S --> (ALL_SET) ; and report a MIXED region 1509 // (MIXED) ---- U --> (NONE) ; and report a MIXED region 1510 // (MIXED) ---- M --> (MIXED) 1511 1512 bitAttr_t RA = ATTR_NONE; 1513 unsigned StartBit = 0; 1514 1515 for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { 1516 bitAttr_t bitAttr = bitAttrs[BitIndex]; 1517 1518 assert(bitAttr != ATTR_NONE && "Bit without attributes"); 1519 1520 switch (RA) { 1521 case ATTR_NONE: 1522 switch (bitAttr) { 1523 case ATTR_FILTERED: 1524 break; 1525 case ATTR_ALL_SET: 1526 StartBit = BitIndex; 1527 RA = ATTR_ALL_SET; 1528 break; 1529 case ATTR_ALL_UNSET: 1530 break; 1531 case ATTR_MIXED: 1532 StartBit = BitIndex; 1533 RA = ATTR_MIXED; 1534 break; 1535 default: 1536 llvm_unreachable("Unexpected bitAttr!"); 1537 } 1538 break; 1539 case ATTR_ALL_SET: 1540 switch (bitAttr) { 1541 case ATTR_FILTERED: 1542 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1543 RA = ATTR_NONE; 1544 break; 1545 case ATTR_ALL_SET: 1546 break; 1547 case ATTR_ALL_UNSET: 1548 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1549 RA = ATTR_NONE; 1550 break; 1551 case ATTR_MIXED: 1552 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1553 StartBit = BitIndex; 1554 RA = ATTR_MIXED; 1555 break; 1556 default: 1557 llvm_unreachable("Unexpected bitAttr!"); 1558 } 1559 break; 1560 case ATTR_MIXED: 1561 switch (bitAttr) { 1562 case ATTR_FILTERED: 1563 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1564 StartBit = BitIndex; 1565 RA = ATTR_NONE; 1566 break; 1567 case ATTR_ALL_SET: 1568 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1569 StartBit = BitIndex; 1570 RA = ATTR_ALL_SET; 1571 break; 1572 case ATTR_ALL_UNSET: 1573 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1574 RA = ATTR_NONE; 1575 break; 1576 case ATTR_MIXED: 1577 break; 1578 default: 1579 llvm_unreachable("Unexpected bitAttr!"); 1580 } 1581 break; 1582 case ATTR_ALL_UNSET: 1583 llvm_unreachable("regionAttr state machine has no ATTR_UNSET state"); 1584 case ATTR_FILTERED: 1585 llvm_unreachable("regionAttr state machine has no ATTR_FILTERED state"); 1586 } 1587 } 1588 1589 // At the end, if we're still in ALL_SET or MIXED states, report a region 1590 switch (RA) { 1591 case ATTR_NONE: 1592 break; 1593 case ATTR_FILTERED: 1594 break; 1595 case ATTR_ALL_SET: 1596 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1597 break; 1598 case ATTR_ALL_UNSET: 1599 break; 1600 case ATTR_MIXED: 1601 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1602 break; 1603 } 1604 1605 // We have finished with the filter processings. Now it's time to choose 1606 // the best performing filter. 1607 BestIndex = 0; 1608 bool AllUseless = true; 1609 unsigned BestScore = 0; 1610 1611 for (unsigned i = 0, e = Filters.size(); i != e; ++i) { 1612 unsigned Usefulness = Filters[i].usefulness(); 1613 1614 if (Usefulness) 1615 AllUseless = false; 1616 1617 if (Usefulness > BestScore) { 1618 BestIndex = i; 1619 BestScore = Usefulness; 1620 } 1621 } 1622 1623 if (!AllUseless) 1624 bestFilter().recurse(); 1625 1626 return !AllUseless; 1627} // end of FilterChooser::filterProcessor(bool) 1628 1629// Decides on the best configuration of filter(s) to use in order to decode 1630// the instructions. A conflict of instructions may occur, in which case we 1631// dump the conflict set to the standard error. 1632void FilterChooser::doFilter() { 1633 unsigned Num = Opcodes.size(); 1634 assert(Num && "FilterChooser created with no instructions"); 1635 1636 // Try regions of consecutive known bit values first. 1637 if (filterProcessor(false)) 1638 return; 1639 1640 // Then regions of mixed bits (both known and unitialized bit values allowed). 1641 if (filterProcessor(true)) 1642 return; 1643 1644 // Heuristics to cope with conflict set {t2CMPrs, t2SUBSrr, t2SUBSrs} where 1645 // no single instruction for the maximum ATTR_MIXED region Inst{14-4} has a 1646 // well-known encoding pattern. In such case, we backtrack and scan for the 1647 // the very first consecutive ATTR_ALL_SET region and assign a filter to it. 1648 if (Num == 3 && filterProcessor(true, false)) 1649 return; 1650 1651 // If we come to here, the instruction decoding has failed. 1652 // Set the BestIndex to -1 to indicate so. 1653 BestIndex = -1; 1654} 1655 1656// emitTableEntries - Emit state machine entries to decode our share of 1657// instructions. 1658void FilterChooser::emitTableEntries(DecoderTableInfo &TableInfo) const { 1659 if (Opcodes.size() == 1) { 1660 // There is only one instruction in the set, which is great! 1661 // Call emitSingletonDecoder() to see whether there are any remaining 1662 // encodings bits. 1663 emitSingletonTableEntry(TableInfo, Opcodes[0]); 1664 return; 1665 } 1666 1667 // Choose the best filter to do the decodings! 1668 if (BestIndex != -1) { 1669 const Filter &Best = Filters[BestIndex]; 1670 if (Best.getNumFiltered() == 1) 1671 emitSingletonTableEntry(TableInfo, Best); 1672 else 1673 Best.emitTableEntry(TableInfo); 1674 return; 1675 } 1676 1677 // We don't know how to decode these instructions! Dump the 1678 // conflict set and bail. 1679 1680 // Print out useful conflict information for postmortem analysis. 1681 errs() << "Decoding Conflict:\n"; 1682 1683 dumpStack(errs(), "\t\t"); 1684 1685 for (unsigned i = 0; i < Opcodes.size(); ++i) { 1686 const std::string &Name = nameWithID(Opcodes[i]); 1687 1688 errs() << '\t' << Name << " "; 1689 dumpBits(errs(), 1690 getBitsField(*AllInstructions[Opcodes[i]]->TheDef, "Inst")); 1691 errs() << '\n'; 1692 } 1693} 1694 1695static bool populateInstruction(CodeGenTarget &Target, 1696 const CodeGenInstruction &CGI, unsigned Opc, 1697 std::map<unsigned, std::vector<OperandInfo> > &Operands){ 1698 const Record &Def = *CGI.TheDef; 1699 // If all the bit positions are not specified; do not decode this instruction. 1700 // We are bound to fail! For proper disassembly, the well-known encoding bits 1701 // of the instruction must be fully specified. 1702 1703 BitsInit &Bits = getBitsField(Def, "Inst"); 1704 if (Bits.allInComplete()) return false; 1705 1706 std::vector<OperandInfo> InsnOperands; 1707 1708 // If the instruction has specified a custom decoding hook, use that instead 1709 // of trying to auto-generate the decoder. 1710 std::string InstDecoder = Def.getValueAsString("DecoderMethod"); 1711 if (InstDecoder != "") { 1712 bool HasCompleteInstDecoder = Def.getValueAsBit("hasCompleteDecoder"); 1713 InsnOperands.push_back(OperandInfo(InstDecoder, HasCompleteInstDecoder)); 1714 Operands[Opc] = InsnOperands; 1715 return true; 1716 } 1717 1718 // Generate a description of the operand of the instruction that we know 1719 // how to decode automatically. 1720 // FIXME: We'll need to have a way to manually override this as needed. 1721 1722 // Gather the outputs/inputs of the instruction, so we can find their 1723 // positions in the encoding. This assumes for now that they appear in the 1724 // MCInst in the order that they're listed. 1725 std::vector<std::pair<Init*, std::string> > InOutOperands; 1726 DagInit *Out = Def.getValueAsDag("OutOperandList"); 1727 DagInit *In = Def.getValueAsDag("InOperandList"); 1728 for (unsigned i = 0; i < Out->getNumArgs(); ++i) 1729 InOutOperands.push_back(std::make_pair(Out->getArg(i), Out->getArgName(i))); 1730 for (unsigned i = 0; i < In->getNumArgs(); ++i) 1731 InOutOperands.push_back(std::make_pair(In->getArg(i), In->getArgName(i))); 1732 1733 // Search for tied operands, so that we can correctly instantiate 1734 // operands that are not explicitly represented in the encoding. 1735 std::map<std::string, std::string> TiedNames; 1736 for (unsigned i = 0; i < CGI.Operands.size(); ++i) { 1737 int tiedTo = CGI.Operands[i].getTiedRegister(); 1738 if (tiedTo != -1) { 1739 std::pair<unsigned, unsigned> SO = 1740 CGI.Operands.getSubOperandNumber(tiedTo); 1741 TiedNames[InOutOperands[i].second] = InOutOperands[SO.first].second; 1742 TiedNames[InOutOperands[SO.first].second] = InOutOperands[i].second; 1743 } 1744 } 1745 1746 std::map<std::string, std::vector<OperandInfo> > NumberedInsnOperands; 1747 std::set<std::string> NumberedInsnOperandsNoTie; 1748 if (Target.getInstructionSet()-> 1749 getValueAsBit("decodePositionallyEncodedOperands")) { 1750 const std::vector<RecordVal> &Vals = Def.getValues(); 1751 unsigned NumberedOp = 0; 1752 1753 std::set<unsigned> NamedOpIndices; 1754 if (Target.getInstructionSet()-> 1755 getValueAsBit("noNamedPositionallyEncodedOperands")) 1756 // Collect the set of operand indices that might correspond to named 1757 // operand, and skip these when assigning operands based on position. 1758 for (unsigned i = 0, e = Vals.size(); i != e; ++i) { 1759 unsigned OpIdx; 1760 if (!CGI.Operands.hasOperandNamed(Vals[i].getName(), OpIdx)) 1761 continue; 1762 1763 NamedOpIndices.insert(OpIdx); 1764 } 1765 1766 for (unsigned i = 0, e = Vals.size(); i != e; ++i) { 1767 // Ignore fixed fields in the record, we're looking for values like: 1768 // bits<5> RST = { ?, ?, ?, ?, ? }; 1769 if (Vals[i].getPrefix() || Vals[i].getValue()->isComplete()) 1770 continue; 1771 1772 // Determine if Vals[i] actually contributes to the Inst encoding. 1773 unsigned bi = 0; 1774 for (; bi < Bits.getNumBits(); ++bi) { 1775 VarInit *Var = nullptr; 1776 VarBitInit *BI = dyn_cast<VarBitInit>(Bits.getBit(bi)); 1777 if (BI) 1778 Var = dyn_cast<VarInit>(BI->getBitVar()); 1779 else 1780 Var = dyn_cast<VarInit>(Bits.getBit(bi)); 1781 1782 if (Var && Var->getName() == Vals[i].getName()) 1783 break; 1784 } 1785 1786 if (bi == Bits.getNumBits()) 1787 continue; 1788 1789 // Skip variables that correspond to explicitly-named operands. 1790 unsigned OpIdx; 1791 if (CGI.Operands.hasOperandNamed(Vals[i].getName(), OpIdx)) 1792 continue; 1793 1794 // Get the bit range for this operand: 1795 unsigned bitStart = bi++, bitWidth = 1; 1796 for (; bi < Bits.getNumBits(); ++bi) { 1797 VarInit *Var = nullptr; 1798 VarBitInit *BI = dyn_cast<VarBitInit>(Bits.getBit(bi)); 1799 if (BI) 1800 Var = dyn_cast<VarInit>(BI->getBitVar()); 1801 else 1802 Var = dyn_cast<VarInit>(Bits.getBit(bi)); 1803 1804 if (!Var) 1805 break; 1806 1807 if (Var->getName() != Vals[i].getName()) 1808 break; 1809 1810 ++bitWidth; 1811 } 1812 1813 unsigned NumberOps = CGI.Operands.size(); 1814 while (NumberedOp < NumberOps && 1815 (CGI.Operands.isFlatOperandNotEmitted(NumberedOp) || 1816 (!NamedOpIndices.empty() && NamedOpIndices.count( 1817 CGI.Operands.getSubOperandNumber(NumberedOp).first)))) 1818 ++NumberedOp; 1819 1820 OpIdx = NumberedOp++; 1821 1822 // OpIdx now holds the ordered operand number of Vals[i]. 1823 std::pair<unsigned, unsigned> SO = 1824 CGI.Operands.getSubOperandNumber(OpIdx); 1825 const std::string &Name = CGI.Operands[SO.first].Name; 1826 1827 DEBUG(dbgs() << "Numbered operand mapping for " << Def.getName() << ": " << 1828 Name << "(" << SO.first << ", " << SO.second << ") => " << 1829 Vals[i].getName() << "\n"); 1830 1831 std::string Decoder = ""; 1832 Record *TypeRecord = CGI.Operands[SO.first].Rec; 1833 1834 RecordVal *DecoderString = TypeRecord->getValue("DecoderMethod"); 1835 StringInit *String = DecoderString ? 1836 dyn_cast<StringInit>(DecoderString->getValue()) : nullptr; 1837 if (String && String->getValue() != "") 1838 Decoder = String->getValue(); 1839 1840 if (Decoder == "" && 1841 CGI.Operands[SO.first].MIOperandInfo && 1842 CGI.Operands[SO.first].MIOperandInfo->getNumArgs()) { 1843 Init *Arg = CGI.Operands[SO.first].MIOperandInfo-> 1844 getArg(SO.second); 1845 if (TypedInit *TI = cast<TypedInit>(Arg)) { 1846 RecordRecTy *Type = cast<RecordRecTy>(TI->getType()); 1847 TypeRecord = Type->getRecord(); 1848 } 1849 } 1850 1851 bool isReg = false; 1852 if (TypeRecord->isSubClassOf("RegisterOperand")) 1853 TypeRecord = TypeRecord->getValueAsDef("RegClass"); 1854 if (TypeRecord->isSubClassOf("RegisterClass")) { 1855 Decoder = "Decode" + TypeRecord->getName() + "RegisterClass"; 1856 isReg = true; 1857 } else if (TypeRecord->isSubClassOf("PointerLikeRegClass")) { 1858 Decoder = "DecodePointerLikeRegClass" + 1859 utostr(TypeRecord->getValueAsInt("RegClassKind")); 1860 isReg = true; 1861 } 1862 1863 DecoderString = TypeRecord->getValue("DecoderMethod"); 1864 String = DecoderString ? 1865 dyn_cast<StringInit>(DecoderString->getValue()) : nullptr; 1866 if (!isReg && String && String->getValue() != "") 1867 Decoder = String->getValue(); 1868 1869 RecordVal *HasCompleteDecoderVal = 1870 TypeRecord->getValue("hasCompleteDecoder"); 1871 BitInit *HasCompleteDecoderBit = HasCompleteDecoderVal ? 1872 dyn_cast<BitInit>(HasCompleteDecoderVal->getValue()) : nullptr; 1873 bool HasCompleteDecoder = HasCompleteDecoderBit ? 1874 HasCompleteDecoderBit->getValue() : true; 1875 1876 OperandInfo OpInfo(Decoder, HasCompleteDecoder); 1877 OpInfo.addField(bitStart, bitWidth, 0); 1878 1879 NumberedInsnOperands[Name].push_back(OpInfo); 1880 1881 // FIXME: For complex operands with custom decoders we can't handle tied 1882 // sub-operands automatically. Skip those here and assume that this is 1883 // fixed up elsewhere. 1884 if (CGI.Operands[SO.first].MIOperandInfo && 1885 CGI.Operands[SO.first].MIOperandInfo->getNumArgs() > 1 && 1886 String && String->getValue() != "") 1887 NumberedInsnOperandsNoTie.insert(Name); 1888 } 1889 } 1890 1891 // For each operand, see if we can figure out where it is encoded. 1892 for (const auto &Op : InOutOperands) { 1893 if (!NumberedInsnOperands[Op.second].empty()) { 1894 InsnOperands.insert(InsnOperands.end(), 1895 NumberedInsnOperands[Op.second].begin(), 1896 NumberedInsnOperands[Op.second].end()); 1897 continue; 1898 } 1899 if (!NumberedInsnOperands[TiedNames[Op.second]].empty()) { 1900 if (!NumberedInsnOperandsNoTie.count(TiedNames[Op.second])) { 1901 // Figure out to which (sub)operand we're tied. 1902 unsigned i = CGI.Operands.getOperandNamed(TiedNames[Op.second]); 1903 int tiedTo = CGI.Operands[i].getTiedRegister(); 1904 if (tiedTo == -1) { 1905 i = CGI.Operands.getOperandNamed(Op.second); 1906 tiedTo = CGI.Operands[i].getTiedRegister(); 1907 } 1908 1909 if (tiedTo != -1) { 1910 std::pair<unsigned, unsigned> SO = 1911 CGI.Operands.getSubOperandNumber(tiedTo); 1912 1913 InsnOperands.push_back(NumberedInsnOperands[TiedNames[Op.second]] 1914 [SO.second]); 1915 } 1916 } 1917 continue; 1918 } 1919 1920 std::string Decoder = ""; 1921 1922 // At this point, we can locate the field, but we need to know how to 1923 // interpret it. As a first step, require the target to provide callbacks 1924 // for decoding register classes. 1925 // FIXME: This need to be extended to handle instructions with custom 1926 // decoder methods, and operands with (simple) MIOperandInfo's. 1927 TypedInit *TI = cast<TypedInit>(Op.first); 1928 RecordRecTy *Type = cast<RecordRecTy>(TI->getType()); 1929 Record *TypeRecord = Type->getRecord(); 1930 bool isReg = false; 1931 if (TypeRecord->isSubClassOf("RegisterOperand")) 1932 TypeRecord = TypeRecord->getValueAsDef("RegClass"); 1933 if (TypeRecord->isSubClassOf("RegisterClass")) { 1934 Decoder = "Decode" + TypeRecord->getName() + "RegisterClass"; 1935 isReg = true; 1936 } else if (TypeRecord->isSubClassOf("PointerLikeRegClass")) { 1937 Decoder = "DecodePointerLikeRegClass" + 1938 utostr(TypeRecord->getValueAsInt("RegClassKind")); 1939 isReg = true; 1940 } 1941 1942 RecordVal *DecoderString = TypeRecord->getValue("DecoderMethod"); 1943 StringInit *String = DecoderString ? 1944 dyn_cast<StringInit>(DecoderString->getValue()) : nullptr; 1945 if (!isReg && String && String->getValue() != "") 1946 Decoder = String->getValue(); 1947 1948 RecordVal *HasCompleteDecoderVal = 1949 TypeRecord->getValue("hasCompleteDecoder"); 1950 BitInit *HasCompleteDecoderBit = HasCompleteDecoderVal ? 1951 dyn_cast<BitInit>(HasCompleteDecoderVal->getValue()) : nullptr; 1952 bool HasCompleteDecoder = HasCompleteDecoderBit ? 1953 HasCompleteDecoderBit->getValue() : true; 1954 1955 OperandInfo OpInfo(Decoder, HasCompleteDecoder); 1956 unsigned Base = ~0U; 1957 unsigned Width = 0; 1958 unsigned Offset = 0; 1959 1960 for (unsigned bi = 0; bi < Bits.getNumBits(); ++bi) { 1961 VarInit *Var = nullptr; 1962 VarBitInit *BI = dyn_cast<VarBitInit>(Bits.getBit(bi)); 1963 if (BI) 1964 Var = dyn_cast<VarInit>(BI->getBitVar()); 1965 else 1966 Var = dyn_cast<VarInit>(Bits.getBit(bi)); 1967 1968 if (!Var) { 1969 if (Base != ~0U) { 1970 OpInfo.addField(Base, Width, Offset); 1971 Base = ~0U; 1972 Width = 0; 1973 Offset = 0; 1974 } 1975 continue; 1976 } 1977 1978 if (Var->getName() != Op.second && 1979 Var->getName() != TiedNames[Op.second]) { 1980 if (Base != ~0U) { 1981 OpInfo.addField(Base, Width, Offset); 1982 Base = ~0U; 1983 Width = 0; 1984 Offset = 0; 1985 } 1986 continue; 1987 } 1988 1989 if (Base == ~0U) { 1990 Base = bi; 1991 Width = 1; 1992 Offset = BI ? BI->getBitNum() : 0; 1993 } else if (BI && BI->getBitNum() != Offset + Width) { 1994 OpInfo.addField(Base, Width, Offset); 1995 Base = bi; 1996 Width = 1; 1997 Offset = BI->getBitNum(); 1998 } else { 1999 ++Width; 2000 } 2001 } 2002 2003 if (Base != ~0U) 2004 OpInfo.addField(Base, Width, Offset); 2005 2006 if (OpInfo.numFields() > 0) 2007 InsnOperands.push_back(OpInfo); 2008 } 2009 2010 Operands[Opc] = InsnOperands; 2011 2012 2013#if 0 2014 DEBUG({ 2015 // Dumps the instruction encoding bits. 2016 dumpBits(errs(), Bits); 2017 2018 errs() << '\n'; 2019 2020 // Dumps the list of operand info. 2021 for (unsigned i = 0, e = CGI.Operands.size(); i != e; ++i) { 2022 const CGIOperandList::OperandInfo &Info = CGI.Operands[i]; 2023 const std::string &OperandName = Info.Name; 2024 const Record &OperandDef = *Info.Rec; 2025 2026 errs() << "\t" << OperandName << " (" << OperandDef.getName() << ")\n"; 2027 } 2028 }); 2029#endif 2030 2031 return true; 2032} 2033 2034// emitFieldFromInstruction - Emit the templated helper function 2035// fieldFromInstruction(). 2036static void emitFieldFromInstruction(formatted_raw_ostream &OS) { 2037 OS << "// Helper function for extracting fields from encoded instructions.\n" 2038 << "template<typename InsnType>\n" 2039 << "static InsnType fieldFromInstruction(InsnType insn, unsigned startBit,\n" 2040 << " unsigned numBits) {\n" 2041 << " assert(startBit + numBits <= (sizeof(InsnType)*8) &&\n" 2042 << " \"Instruction field out of bounds!\");\n" 2043 << " InsnType fieldMask;\n" 2044 << " if (numBits == sizeof(InsnType)*8)\n" 2045 << " fieldMask = (InsnType)(-1LL);\n" 2046 << " else\n" 2047 << " fieldMask = (((InsnType)1 << numBits) - 1) << startBit;\n" 2048 << " return (insn & fieldMask) >> startBit;\n" 2049 << "}\n\n"; 2050} 2051 2052// emitDecodeInstruction - Emit the templated helper function 2053// decodeInstruction(). 2054static void emitDecodeInstruction(formatted_raw_ostream &OS) { 2055 OS << "template<typename InsnType>\n" 2056 << "static DecodeStatus decodeInstruction(const uint8_t DecodeTable[], MCInst &MI,\n" 2057 << " InsnType insn, uint64_t Address,\n" 2058 << " const void *DisAsm,\n" 2059 << " const MCSubtargetInfo &STI) {\n" 2060 << " const FeatureBitset& Bits = STI.getFeatureBits();\n" 2061 << "\n" 2062 << " const uint8_t *Ptr = DecodeTable;\n" 2063 << " uint32_t CurFieldValue = 0;\n" 2064 << " DecodeStatus S = MCDisassembler::Success;\n" 2065 << " for (;;) {\n" 2066 << " ptrdiff_t Loc = Ptr - DecodeTable;\n" 2067 << " switch (*Ptr) {\n" 2068 << " default:\n" 2069 << " errs() << Loc << \": Unexpected decode table opcode!\\n\";\n" 2070 << " return MCDisassembler::Fail;\n" 2071 << " case MCD::OPC_ExtractField: {\n" 2072 << " unsigned Start = *++Ptr;\n" 2073 << " unsigned Len = *++Ptr;\n" 2074 << " ++Ptr;\n" 2075 << " CurFieldValue = fieldFromInstruction(insn, Start, Len);\n" 2076 << " DEBUG(dbgs() << Loc << \": OPC_ExtractField(\" << Start << \", \"\n" 2077 << " << Len << \"): \" << CurFieldValue << \"\\n\");\n" 2078 << " break;\n" 2079 << " }\n" 2080 << " case MCD::OPC_FilterValue: {\n" 2081 << " // Decode the field value.\n" 2082 << " unsigned Len;\n" 2083 << " InsnType Val = decodeULEB128(++Ptr, &Len);\n" 2084 << " Ptr += Len;\n" 2085 << " // NumToSkip is a plain 16-bit integer.\n" 2086 << " unsigned NumToSkip = *Ptr++;\n" 2087 << " NumToSkip |= (*Ptr++) << 8;\n" 2088 << "\n" 2089 << " // Perform the filter operation.\n" 2090 << " if (Val != CurFieldValue)\n" 2091 << " Ptr += NumToSkip;\n" 2092 << " DEBUG(dbgs() << Loc << \": OPC_FilterValue(\" << Val << \", \" << NumToSkip\n" 2093 << " << \"): \" << ((Val != CurFieldValue) ? \"FAIL:\" : \"PASS:\")\n" 2094 << " << \" continuing at \" << (Ptr - DecodeTable) << \"\\n\");\n" 2095 << "\n" 2096 << " break;\n" 2097 << " }\n" 2098 << " case MCD::OPC_CheckField: {\n" 2099 << " unsigned Start = *++Ptr;\n" 2100 << " unsigned Len = *++Ptr;\n" 2101 << " InsnType FieldValue = fieldFromInstruction(insn, Start, Len);\n" 2102 << " // Decode the field value.\n" 2103 << " uint32_t ExpectedValue = decodeULEB128(++Ptr, &Len);\n" 2104 << " Ptr += Len;\n" 2105 << " // NumToSkip is a plain 16-bit integer.\n" 2106 << " unsigned NumToSkip = *Ptr++;\n" 2107 << " NumToSkip |= (*Ptr++) << 8;\n" 2108 << "\n" 2109 << " // If the actual and expected values don't match, skip.\n" 2110 << " if (ExpectedValue != FieldValue)\n" 2111 << " Ptr += NumToSkip;\n" 2112 << " DEBUG(dbgs() << Loc << \": OPC_CheckField(\" << Start << \", \"\n" 2113 << " << Len << \", \" << ExpectedValue << \", \" << NumToSkip\n" 2114 << " << \"): FieldValue = \" << FieldValue << \", ExpectedValue = \"\n" 2115 << " << ExpectedValue << \": \"\n" 2116 << " << ((ExpectedValue == FieldValue) ? \"PASS\\n\" : \"FAIL\\n\"));\n" 2117 << " break;\n" 2118 << " }\n" 2119 << " case MCD::OPC_CheckPredicate: {\n" 2120 << " unsigned Len;\n" 2121 << " // Decode the Predicate Index value.\n" 2122 << " unsigned PIdx = decodeULEB128(++Ptr, &Len);\n" 2123 << " Ptr += Len;\n" 2124 << " // NumToSkip is a plain 16-bit integer.\n" 2125 << " unsigned NumToSkip = *Ptr++;\n" 2126 << " NumToSkip |= (*Ptr++) << 8;\n" 2127 << " // Check the predicate.\n" 2128 << " bool Pred;\n" 2129 << " if (!(Pred = checkDecoderPredicate(PIdx, Bits)))\n" 2130 << " Ptr += NumToSkip;\n" 2131 << " (void)Pred;\n" 2132 << " DEBUG(dbgs() << Loc << \": OPC_CheckPredicate(\" << PIdx << \"): \"\n" 2133 << " << (Pred ? \"PASS\\n\" : \"FAIL\\n\"));\n" 2134 << "\n" 2135 << " break;\n" 2136 << " }\n" 2137 << " case MCD::OPC_Decode: {\n" 2138 << " unsigned Len;\n" 2139 << " // Decode the Opcode value.\n" 2140 << " unsigned Opc = decodeULEB128(++Ptr, &Len);\n" 2141 << " Ptr += Len;\n" 2142 << " unsigned DecodeIdx = decodeULEB128(Ptr, &Len);\n" 2143 << " Ptr += Len;\n" 2144 << "\n" 2145 << " MI.clear();\n" 2146 << " MI.setOpcode(Opc);\n" 2147 << " bool DecodeComplete;\n" 2148 << " S = decodeToMCInst(S, DecodeIdx, insn, MI, Address, DisAsm, DecodeComplete);\n" 2149 << " assert(DecodeComplete);\n" 2150 << "\n" 2151 << " DEBUG(dbgs() << Loc << \": OPC_Decode: opcode \" << Opc\n" 2152 << " << \", using decoder \" << DecodeIdx << \": \"\n" 2153 << " << (S != MCDisassembler::Fail ? \"PASS\" : \"FAIL\") << \"\\n\");\n" 2154 << " return S;\n" 2155 << " }\n" 2156 << " case MCD::OPC_TryDecode: {\n" 2157 << " unsigned Len;\n" 2158 << " // Decode the Opcode value.\n" 2159 << " unsigned Opc = decodeULEB128(++Ptr, &Len);\n" 2160 << " Ptr += Len;\n" 2161 << " unsigned DecodeIdx = decodeULEB128(Ptr, &Len);\n" 2162 << " Ptr += Len;\n" 2163 << " // NumToSkip is a plain 16-bit integer.\n" 2164 << " unsigned NumToSkip = *Ptr++;\n" 2165 << " NumToSkip |= (*Ptr++) << 8;\n" 2166 << "\n" 2167 << " // Perform the decode operation.\n" 2168 << " MCInst TmpMI;\n" 2169 << " TmpMI.setOpcode(Opc);\n" 2170 << " bool DecodeComplete;\n" 2171 << " S = decodeToMCInst(S, DecodeIdx, insn, TmpMI, Address, DisAsm, DecodeComplete);\n" 2172 << " DEBUG(dbgs() << Loc << \": OPC_TryDecode: opcode \" << Opc\n" 2173 << " << \", using decoder \" << DecodeIdx << \": \");\n" 2174 << "\n" 2175 << " if (DecodeComplete) {\n" 2176 << " // Decoding complete.\n" 2177 << " DEBUG(dbgs() << (S != MCDisassembler::Fail ? \"PASS\" : \"FAIL\") << \"\\n\");\n" 2178 << " MI = TmpMI;\n" 2179 << " return S;\n" 2180 << " } else {\n" 2181 << " assert(S == MCDisassembler::Fail);\n" 2182 << " // If the decoding was incomplete, skip.\n" 2183 << " Ptr += NumToSkip;\n" 2184 << " DEBUG(dbgs() << \"FAIL: continuing at \" << (Ptr - DecodeTable) << \"\\n\");\n" 2185 << " // Reset decode status. This also drops a SoftFail status that could be\n" 2186 << " // set before the decode attempt.\n" 2187 << " S = MCDisassembler::Success;\n" 2188 << " }\n" 2189 << " break;\n" 2190 << " }\n" 2191 << " case MCD::OPC_SoftFail: {\n" 2192 << " // Decode the mask values.\n" 2193 << " unsigned Len;\n" 2194 << " InsnType PositiveMask = decodeULEB128(++Ptr, &Len);\n" 2195 << " Ptr += Len;\n" 2196 << " InsnType NegativeMask = decodeULEB128(Ptr, &Len);\n" 2197 << " Ptr += Len;\n" 2198 << " bool Fail = (insn & PositiveMask) || (~insn & NegativeMask);\n" 2199 << " if (Fail)\n" 2200 << " S = MCDisassembler::SoftFail;\n" 2201 << " DEBUG(dbgs() << Loc << \": OPC_SoftFail: \" << (Fail ? \"FAIL\\n\":\"PASS\\n\"));\n" 2202 << " break;\n" 2203 << " }\n" 2204 << " case MCD::OPC_Fail: {\n" 2205 << " DEBUG(dbgs() << Loc << \": OPC_Fail\\n\");\n" 2206 << " return MCDisassembler::Fail;\n" 2207 << " }\n" 2208 << " }\n" 2209 << " }\n" 2210 << " llvm_unreachable(\"bogosity detected in disassembler state machine!\");\n" 2211 << "}\n\n"; 2212} 2213 2214// Emits disassembler code for instruction decoding. 2215void FixedLenDecoderEmitter::run(raw_ostream &o) { 2216 formatted_raw_ostream OS(o); 2217 OS << "#include \"llvm/MC/MCInst.h\"\n"; 2218 OS << "#include \"llvm/Support/Debug.h\"\n"; 2219 OS << "#include \"llvm/Support/DataTypes.h\"\n"; 2220 OS << "#include \"llvm/Support/LEB128.h\"\n"; 2221 OS << "#include \"llvm/Support/raw_ostream.h\"\n"; 2222 OS << "#include <assert.h>\n"; 2223 OS << '\n'; 2224 OS << "namespace llvm {\n\n"; 2225 2226 emitFieldFromInstruction(OS); 2227 2228 Target.reverseBitsForLittleEndianEncoding(); 2229 2230 // Parameterize the decoders based on namespace and instruction width. 2231 NumberedInstructions = Target.getInstructionsByEnumValue(); 2232 std::map<std::pair<std::string, unsigned>, 2233 std::vector<unsigned> > OpcMap; 2234 std::map<unsigned, std::vector<OperandInfo> > Operands; 2235 2236 for (unsigned i = 0; i < NumberedInstructions.size(); ++i) { 2237 const CodeGenInstruction *Inst = NumberedInstructions[i]; 2238 const Record *Def = Inst->TheDef; 2239 unsigned Size = Def->getValueAsInt("Size"); 2240 if (Def->getValueAsString("Namespace") == "TargetOpcode" || 2241 Def->getValueAsBit("isPseudo") || 2242 Def->getValueAsBit("isAsmParserOnly") || 2243 Def->getValueAsBit("isCodeGenOnly")) 2244 continue; 2245 2246 std::string DecoderNamespace = Def->getValueAsString("DecoderNamespace"); 2247 2248 if (Size) { 2249 if (populateInstruction(Target, *Inst, i, Operands)) { 2250 OpcMap[std::make_pair(DecoderNamespace, Size)].push_back(i); 2251 } 2252 } 2253 } 2254 2255 DecoderTableInfo TableInfo; 2256 for (const auto &Opc : OpcMap) { 2257 // Emit the decoder for this namespace+width combination. 2258 FilterChooser FC(NumberedInstructions, Opc.second, Operands, 2259 8*Opc.first.second, this); 2260 2261 // The decode table is cleared for each top level decoder function. The 2262 // predicates and decoders themselves, however, are shared across all 2263 // decoders to give more opportunities for uniqueing. 2264 TableInfo.Table.clear(); 2265 TableInfo.FixupStack.clear(); 2266 TableInfo.Table.reserve(16384); 2267 TableInfo.FixupStack.emplace_back(); 2268 FC.emitTableEntries(TableInfo); 2269 // Any NumToSkip fixups in the top level scope can resolve to the 2270 // OPC_Fail at the end of the table. 2271 assert(TableInfo.FixupStack.size() == 1 && "fixup stack phasing error!"); 2272 // Resolve any NumToSkip fixups in the current scope. 2273 resolveTableFixups(TableInfo.Table, TableInfo.FixupStack.back(), 2274 TableInfo.Table.size()); 2275 TableInfo.FixupStack.clear(); 2276 2277 TableInfo.Table.push_back(MCD::OPC_Fail); 2278 2279 // Print the table to the output stream. 2280 emitTable(OS, TableInfo.Table, 0, FC.getBitWidth(), Opc.first.first); 2281 OS.flush(); 2282 } 2283 2284 // Emit the predicate function. 2285 emitPredicateFunction(OS, TableInfo.Predicates, 0); 2286 2287 // Emit the decoder function. 2288 emitDecoderFunction(OS, TableInfo.Decoders, 0); 2289 2290 // Emit the main entry point for the decoder, decodeInstruction(). 2291 emitDecodeInstruction(OS); 2292 2293 OS << "\n} // End llvm namespace\n"; 2294} 2295 2296namespace llvm { 2297 2298void EmitFixedLenDecoder(RecordKeeper &RK, raw_ostream &OS, 2299 const std::string &PredicateNamespace, 2300 const std::string &GPrefix, 2301 const std::string &GPostfix, const std::string &ROK, 2302 const std::string &RFail, const std::string &L) { 2303 FixedLenDecoderEmitter(RK, PredicateNamespace, GPrefix, GPostfix, 2304 ROK, RFail, L).run(OS); 2305} 2306 2307} // End llvm namespace 2308