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