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 1185bool FilterChooser::emitPredicateMatch(raw_ostream &o, unsigned &Indentation, 1186 unsigned Opc) const { 1187 ListInit *Predicates = 1188 AllInstructions[Opc].EncodingDef->getValueAsListInit("Predicates"); 1189 bool IsFirstEmission = true; 1190 for (unsigned i = 0; i < Predicates->size(); ++i) { 1191 Record *Pred = Predicates->getElementAsRecord(i); 1192 if (!Pred->getValue("AssemblerMatcherPredicate")) 1193 continue; 1194 1195 if (!dyn_cast<DagInit>(Pred->getValue("AssemblerCondDag")->getValue())) 1196 continue; 1197 1198 const DagInit *D = Pred->getValueAsDag("AssemblerCondDag"); 1199 std::string CombineType = D->getOperator()->getAsString(); 1200 if (CombineType != "any_of" && CombineType != "all_of") 1201 PrintFatalError(Pred->getLoc(), "Invalid AssemblerCondDag!"); 1202 if (D->getNumArgs() == 0) 1203 PrintFatalError(Pred->getLoc(), "Invalid AssemblerCondDag!"); 1204 bool IsOr = CombineType == "any_of"; 1205 1206 if (!IsFirstEmission) 1207 o << " && "; 1208 1209 if (IsOr) 1210 o << "("; 1211 1212 bool First = true; 1213 for (auto *Arg : D->getArgs()) { 1214 if (!First) { 1215 if (IsOr) 1216 o << " || "; 1217 else 1218 o << " && "; 1219 } 1220 if (auto *NotArg = dyn_cast<DagInit>(Arg)) { 1221 if (NotArg->getOperator()->getAsString() != "not" || 1222 NotArg->getNumArgs() != 1) 1223 PrintFatalError(Pred->getLoc(), "Invalid AssemblerCondDag!"); 1224 Arg = NotArg->getArg(0); 1225 o << "!"; 1226 } 1227 if (!isa<DefInit>(Arg) || 1228 !cast<DefInit>(Arg)->getDef()->isSubClassOf("SubtargetFeature")) 1229 PrintFatalError(Pred->getLoc(), "Invalid AssemblerCondDag!"); 1230 o << "Bits[" << Emitter->PredicateNamespace << "::" << Arg->getAsString() 1231 << "]"; 1232 1233 First = false; 1234 } 1235 1236 if (IsOr) 1237 o << ")"; 1238 1239 IsFirstEmission = false; 1240 } 1241 return !Predicates->empty(); 1242} 1243 1244bool FilterChooser::doesOpcodeNeedPredicate(unsigned Opc) const { 1245 ListInit *Predicates = 1246 AllInstructions[Opc].EncodingDef->getValueAsListInit("Predicates"); 1247 for (unsigned i = 0; i < Predicates->size(); ++i) { 1248 Record *Pred = Predicates->getElementAsRecord(i); 1249 if (!Pred->getValue("AssemblerMatcherPredicate")) 1250 continue; 1251 1252 if (dyn_cast<DagInit>(Pred->getValue("AssemblerCondDag")->getValue())) 1253 return true; 1254 } 1255 return false; 1256} 1257 1258unsigned FilterChooser::getPredicateIndex(DecoderTableInfo &TableInfo, 1259 StringRef Predicate) const { 1260 // Using the full predicate string as the key value here is a bit 1261 // heavyweight, but is effective. If the string comparisons become a 1262 // performance concern, we can implement a mangling of the predicate 1263 // data easily enough with a map back to the actual string. That's 1264 // overkill for now, though. 1265 1266 // Make sure the predicate is in the table. 1267 TableInfo.Predicates.insert(CachedHashString(Predicate)); 1268 // Now figure out the index for when we write out the table. 1269 PredicateSet::const_iterator P = find(TableInfo.Predicates, Predicate); 1270 return (unsigned)(P - TableInfo.Predicates.begin()); 1271} 1272 1273void FilterChooser::emitPredicateTableEntry(DecoderTableInfo &TableInfo, 1274 unsigned Opc) const { 1275 if (!doesOpcodeNeedPredicate(Opc)) 1276 return; 1277 1278 // Build up the predicate string. 1279 SmallString<256> Predicate; 1280 // FIXME: emitPredicateMatch() functions can take a buffer directly rather 1281 // than a stream. 1282 raw_svector_ostream PS(Predicate); 1283 unsigned I = 0; 1284 emitPredicateMatch(PS, I, Opc); 1285 1286 // Figure out the index into the predicate table for the predicate just 1287 // computed. 1288 unsigned PIdx = getPredicateIndex(TableInfo, PS.str()); 1289 SmallString<16> PBytes; 1290 raw_svector_ostream S(PBytes); 1291 encodeULEB128(PIdx, S); 1292 1293 TableInfo.Table.push_back(MCD::OPC_CheckPredicate); 1294 // Predicate index 1295 for (unsigned i = 0, e = PBytes.size(); i != e; ++i) 1296 TableInfo.Table.push_back(PBytes[i]); 1297 // Push location for NumToSkip backpatching. 1298 TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); 1299 TableInfo.Table.push_back(0); 1300 TableInfo.Table.push_back(0); 1301 TableInfo.Table.push_back(0); 1302} 1303 1304void FilterChooser::emitSoftFailTableEntry(DecoderTableInfo &TableInfo, 1305 unsigned Opc) const { 1306 BitsInit *SFBits = 1307 AllInstructions[Opc].EncodingDef->getValueAsBitsInit("SoftFail"); 1308 if (!SFBits) return; 1309 BitsInit *InstBits = 1310 AllInstructions[Opc].EncodingDef->getValueAsBitsInit("Inst"); 1311 1312 APInt PositiveMask(BitWidth, 0ULL); 1313 APInt NegativeMask(BitWidth, 0ULL); 1314 for (unsigned i = 0; i < BitWidth; ++i) { 1315 bit_value_t B = bitFromBits(*SFBits, i); 1316 bit_value_t IB = bitFromBits(*InstBits, i); 1317 1318 if (B != BIT_TRUE) continue; 1319 1320 switch (IB) { 1321 case BIT_FALSE: 1322 // The bit is meant to be false, so emit a check to see if it is true. 1323 PositiveMask.setBit(i); 1324 break; 1325 case BIT_TRUE: 1326 // The bit is meant to be true, so emit a check to see if it is false. 1327 NegativeMask.setBit(i); 1328 break; 1329 default: 1330 // The bit is not set; this must be an error! 1331 errs() << "SoftFail Conflict: bit SoftFail{" << i << "} in " 1332 << AllInstructions[Opc] << " is set but Inst{" << i 1333 << "} is unset!\n" 1334 << " - You can only mark a bit as SoftFail if it is fully defined" 1335 << " (1/0 - not '?') in Inst\n"; 1336 return; 1337 } 1338 } 1339 1340 bool NeedPositiveMask = PositiveMask.getBoolValue(); 1341 bool NeedNegativeMask = NegativeMask.getBoolValue(); 1342 1343 if (!NeedPositiveMask && !NeedNegativeMask) 1344 return; 1345 1346 TableInfo.Table.push_back(MCD::OPC_SoftFail); 1347 1348 SmallString<16> MaskBytes; 1349 raw_svector_ostream S(MaskBytes); 1350 if (NeedPositiveMask) { 1351 encodeULEB128(PositiveMask.getZExtValue(), S); 1352 for (unsigned i = 0, e = MaskBytes.size(); i != e; ++i) 1353 TableInfo.Table.push_back(MaskBytes[i]); 1354 } else 1355 TableInfo.Table.push_back(0); 1356 if (NeedNegativeMask) { 1357 MaskBytes.clear(); 1358 encodeULEB128(NegativeMask.getZExtValue(), S); 1359 for (unsigned i = 0, e = MaskBytes.size(); i != e; ++i) 1360 TableInfo.Table.push_back(MaskBytes[i]); 1361 } else 1362 TableInfo.Table.push_back(0); 1363} 1364 1365// Emits table entries to decode the singleton. 1366void FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo, 1367 EncodingIDAndOpcode Opc) const { 1368 std::vector<unsigned> StartBits; 1369 std::vector<unsigned> EndBits; 1370 std::vector<uint64_t> FieldVals; 1371 insn_t Insn; 1372 insnWithID(Insn, Opc.EncodingID); 1373 1374 // Look for islands of undecoded bits of the singleton. 1375 getIslands(StartBits, EndBits, FieldVals, Insn); 1376 1377 unsigned Size = StartBits.size(); 1378 1379 // Emit the predicate table entry if one is needed. 1380 emitPredicateTableEntry(TableInfo, Opc.EncodingID); 1381 1382 // Check any additional encoding fields needed. 1383 for (unsigned I = Size; I != 0; --I) { 1384 unsigned NumBits = EndBits[I-1] - StartBits[I-1] + 1; 1385 TableInfo.Table.push_back(MCD::OPC_CheckField); 1386 TableInfo.Table.push_back(StartBits[I-1]); 1387 TableInfo.Table.push_back(NumBits); 1388 uint8_t Buffer[16], *p; 1389 encodeULEB128(FieldVals[I-1], Buffer); 1390 for (p = Buffer; *p >= 128 ; ++p) 1391 TableInfo.Table.push_back(*p); 1392 TableInfo.Table.push_back(*p); 1393 // Push location for NumToSkip backpatching. 1394 TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); 1395 // The fixup is always 24-bits, so go ahead and allocate the space 1396 // in the table so all our relative position calculations work OK even 1397 // before we fully resolve the real value here. 1398 TableInfo.Table.push_back(0); 1399 TableInfo.Table.push_back(0); 1400 TableInfo.Table.push_back(0); 1401 } 1402 1403 // Check for soft failure of the match. 1404 emitSoftFailTableEntry(TableInfo, Opc.EncodingID); 1405 1406 bool HasCompleteDecoder; 1407 unsigned DIdx = 1408 getDecoderIndex(TableInfo.Decoders, Opc.EncodingID, HasCompleteDecoder); 1409 1410 // Produce OPC_Decode or OPC_TryDecode opcode based on the information 1411 // whether the instruction decoder is complete or not. If it is complete 1412 // then it handles all possible values of remaining variable/unfiltered bits 1413 // and for any value can determine if the bitpattern is a valid instruction 1414 // or not. This means OPC_Decode will be the final step in the decoding 1415 // process. If it is not complete, then the Fail return code from the 1416 // decoder method indicates that additional processing should be done to see 1417 // if there is any other instruction that also matches the bitpattern and 1418 // can decode it. 1419 TableInfo.Table.push_back(HasCompleteDecoder ? MCD::OPC_Decode : 1420 MCD::OPC_TryDecode); 1421 NumEncodingsSupported++; 1422 uint8_t Buffer[16], *p; 1423 encodeULEB128(Opc.Opcode, Buffer); 1424 for (p = Buffer; *p >= 128 ; ++p) 1425 TableInfo.Table.push_back(*p); 1426 TableInfo.Table.push_back(*p); 1427 1428 SmallString<16> Bytes; 1429 raw_svector_ostream S(Bytes); 1430 encodeULEB128(DIdx, S); 1431 1432 // Decoder index 1433 for (unsigned i = 0, e = Bytes.size(); i != e; ++i) 1434 TableInfo.Table.push_back(Bytes[i]); 1435 1436 if (!HasCompleteDecoder) { 1437 // Push location for NumToSkip backpatching. 1438 TableInfo.FixupStack.back().push_back(TableInfo.Table.size()); 1439 // Allocate the space for the fixup. 1440 TableInfo.Table.push_back(0); 1441 TableInfo.Table.push_back(0); 1442 TableInfo.Table.push_back(0); 1443 } 1444} 1445 1446// Emits table entries to decode the singleton, and then to decode the rest. 1447void FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo, 1448 const Filter &Best) const { 1449 EncodingIDAndOpcode Opc = Best.getSingletonOpc(); 1450 1451 // complex singletons need predicate checks from the first singleton 1452 // to refer forward to the variable filterchooser that follows. 1453 TableInfo.FixupStack.emplace_back(); 1454 1455 emitSingletonTableEntry(TableInfo, Opc); 1456 1457 resolveTableFixups(TableInfo.Table, TableInfo.FixupStack.back(), 1458 TableInfo.Table.size()); 1459 TableInfo.FixupStack.pop_back(); 1460 1461 Best.getVariableFC().emitTableEntries(TableInfo); 1462} 1463 1464// Assign a single filter and run with it. Top level API client can initialize 1465// with a single filter to start the filtering process. 1466void FilterChooser::runSingleFilter(unsigned startBit, unsigned numBit, 1467 bool mixed) { 1468 Filters.clear(); 1469 Filters.emplace_back(*this, startBit, numBit, true); 1470 BestIndex = 0; // Sole Filter instance to choose from. 1471 bestFilter().recurse(); 1472} 1473 1474// reportRegion is a helper function for filterProcessor to mark a region as 1475// eligible for use as a filter region. 1476void FilterChooser::reportRegion(bitAttr_t RA, unsigned StartBit, 1477 unsigned BitIndex, bool AllowMixed) { 1478 if (RA == ATTR_MIXED && AllowMixed) 1479 Filters.emplace_back(*this, StartBit, BitIndex - StartBit, true); 1480 else if (RA == ATTR_ALL_SET && !AllowMixed) 1481 Filters.emplace_back(*this, StartBit, BitIndex - StartBit, false); 1482} 1483 1484// FilterProcessor scans the well-known encoding bits of the instructions and 1485// builds up a list of candidate filters. It chooses the best filter and 1486// recursively descends down the decoding tree. 1487bool FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { 1488 Filters.clear(); 1489 BestIndex = -1; 1490 unsigned numInstructions = Opcodes.size(); 1491 1492 assert(numInstructions && "Filter created with no instructions"); 1493 1494 // No further filtering is necessary. 1495 if (numInstructions == 1) 1496 return true; 1497 1498 // Heuristics. See also doFilter()'s "Heuristics" comment when num of 1499 // instructions is 3. 1500 if (AllowMixed && !Greedy) { 1501 assert(numInstructions == 3); 1502 1503 for (unsigned i = 0; i < Opcodes.size(); ++i) { 1504 std::vector<unsigned> StartBits; 1505 std::vector<unsigned> EndBits; 1506 std::vector<uint64_t> FieldVals; 1507 insn_t Insn; 1508 1509 insnWithID(Insn, Opcodes[i].EncodingID); 1510 1511 // Look for islands of undecoded bits of any instruction. 1512 if (getIslands(StartBits, EndBits, FieldVals, Insn) > 0) { 1513 // Found an instruction with island(s). Now just assign a filter. 1514 runSingleFilter(StartBits[0], EndBits[0] - StartBits[0] + 1, true); 1515 return true; 1516 } 1517 } 1518 } 1519 1520 unsigned BitIndex; 1521 1522 // We maintain BIT_WIDTH copies of the bitAttrs automaton. 1523 // The automaton consumes the corresponding bit from each 1524 // instruction. 1525 // 1526 // Input symbols: 0, 1, and _ (unset). 1527 // States: NONE, FILTERED, ALL_SET, ALL_UNSET, and MIXED. 1528 // Initial state: NONE. 1529 // 1530 // (NONE) ------- [01] -> (ALL_SET) 1531 // (NONE) ------- _ ----> (ALL_UNSET) 1532 // (ALL_SET) ---- [01] -> (ALL_SET) 1533 // (ALL_SET) ---- _ ----> (MIXED) 1534 // (ALL_UNSET) -- [01] -> (MIXED) 1535 // (ALL_UNSET) -- _ ----> (ALL_UNSET) 1536 // (MIXED) ------ . ----> (MIXED) 1537 // (FILTERED)---- . ----> (FILTERED) 1538 1539 std::vector<bitAttr_t> bitAttrs; 1540 1541 // FILTERED bit positions provide no entropy and are not worthy of pursuing. 1542 // Filter::recurse() set either BIT_TRUE or BIT_FALSE for each position. 1543 for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) 1544 if (FilterBitValues[BitIndex] == BIT_TRUE || 1545 FilterBitValues[BitIndex] == BIT_FALSE) 1546 bitAttrs.push_back(ATTR_FILTERED); 1547 else 1548 bitAttrs.push_back(ATTR_NONE); 1549 1550 for (unsigned InsnIndex = 0; InsnIndex < numInstructions; ++InsnIndex) { 1551 insn_t insn; 1552 1553 insnWithID(insn, Opcodes[InsnIndex].EncodingID); 1554 1555 for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { 1556 switch (bitAttrs[BitIndex]) { 1557 case ATTR_NONE: 1558 if (insn[BitIndex] == BIT_UNSET) 1559 bitAttrs[BitIndex] = ATTR_ALL_UNSET; 1560 else 1561 bitAttrs[BitIndex] = ATTR_ALL_SET; 1562 break; 1563 case ATTR_ALL_SET: 1564 if (insn[BitIndex] == BIT_UNSET) 1565 bitAttrs[BitIndex] = ATTR_MIXED; 1566 break; 1567 case ATTR_ALL_UNSET: 1568 if (insn[BitIndex] != BIT_UNSET) 1569 bitAttrs[BitIndex] = ATTR_MIXED; 1570 break; 1571 case ATTR_MIXED: 1572 case ATTR_FILTERED: 1573 break; 1574 } 1575 } 1576 } 1577 1578 // The regionAttr automaton consumes the bitAttrs automatons' state, 1579 // lowest-to-highest. 1580 // 1581 // Input symbols: F(iltered), (all_)S(et), (all_)U(nset), M(ixed) 1582 // States: NONE, ALL_SET, MIXED 1583 // Initial state: NONE 1584 // 1585 // (NONE) ----- F --> (NONE) 1586 // (NONE) ----- S --> (ALL_SET) ; and set region start 1587 // (NONE) ----- U --> (NONE) 1588 // (NONE) ----- M --> (MIXED) ; and set region start 1589 // (ALL_SET) -- F --> (NONE) ; and report an ALL_SET region 1590 // (ALL_SET) -- S --> (ALL_SET) 1591 // (ALL_SET) -- U --> (NONE) ; and report an ALL_SET region 1592 // (ALL_SET) -- M --> (MIXED) ; and report an ALL_SET region 1593 // (MIXED) ---- F --> (NONE) ; and report a MIXED region 1594 // (MIXED) ---- S --> (ALL_SET) ; and report a MIXED region 1595 // (MIXED) ---- U --> (NONE) ; and report a MIXED region 1596 // (MIXED) ---- M --> (MIXED) 1597 1598 bitAttr_t RA = ATTR_NONE; 1599 unsigned StartBit = 0; 1600 1601 for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { 1602 bitAttr_t bitAttr = bitAttrs[BitIndex]; 1603 1604 assert(bitAttr != ATTR_NONE && "Bit without attributes"); 1605 1606 switch (RA) { 1607 case ATTR_NONE: 1608 switch (bitAttr) { 1609 case ATTR_FILTERED: 1610 break; 1611 case ATTR_ALL_SET: 1612 StartBit = BitIndex; 1613 RA = ATTR_ALL_SET; 1614 break; 1615 case ATTR_ALL_UNSET: 1616 break; 1617 case ATTR_MIXED: 1618 StartBit = BitIndex; 1619 RA = ATTR_MIXED; 1620 break; 1621 default: 1622 llvm_unreachable("Unexpected bitAttr!"); 1623 } 1624 break; 1625 case ATTR_ALL_SET: 1626 switch (bitAttr) { 1627 case ATTR_FILTERED: 1628 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1629 RA = ATTR_NONE; 1630 break; 1631 case ATTR_ALL_SET: 1632 break; 1633 case ATTR_ALL_UNSET: 1634 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1635 RA = ATTR_NONE; 1636 break; 1637 case ATTR_MIXED: 1638 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1639 StartBit = BitIndex; 1640 RA = ATTR_MIXED; 1641 break; 1642 default: 1643 llvm_unreachable("Unexpected bitAttr!"); 1644 } 1645 break; 1646 case ATTR_MIXED: 1647 switch (bitAttr) { 1648 case ATTR_FILTERED: 1649 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1650 StartBit = BitIndex; 1651 RA = ATTR_NONE; 1652 break; 1653 case ATTR_ALL_SET: 1654 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1655 StartBit = BitIndex; 1656 RA = ATTR_ALL_SET; 1657 break; 1658 case ATTR_ALL_UNSET: 1659 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1660 RA = ATTR_NONE; 1661 break; 1662 case ATTR_MIXED: 1663 break; 1664 default: 1665 llvm_unreachable("Unexpected bitAttr!"); 1666 } 1667 break; 1668 case ATTR_ALL_UNSET: 1669 llvm_unreachable("regionAttr state machine has no ATTR_UNSET state"); 1670 case ATTR_FILTERED: 1671 llvm_unreachable("regionAttr state machine has no ATTR_FILTERED state"); 1672 } 1673 } 1674 1675 // At the end, if we're still in ALL_SET or MIXED states, report a region 1676 switch (RA) { 1677 case ATTR_NONE: 1678 break; 1679 case ATTR_FILTERED: 1680 break; 1681 case ATTR_ALL_SET: 1682 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1683 break; 1684 case ATTR_ALL_UNSET: 1685 break; 1686 case ATTR_MIXED: 1687 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1688 break; 1689 } 1690 1691 // We have finished with the filter processings. Now it's time to choose 1692 // the best performing filter. 1693 BestIndex = 0; 1694 bool AllUseless = true; 1695 unsigned BestScore = 0; 1696 1697 for (unsigned i = 0, e = Filters.size(); i != e; ++i) { 1698 unsigned Usefulness = Filters[i].usefulness(); 1699 1700 if (Usefulness) 1701 AllUseless = false; 1702 1703 if (Usefulness > BestScore) { 1704 BestIndex = i; 1705 BestScore = Usefulness; 1706 } 1707 } 1708 1709 if (!AllUseless) 1710 bestFilter().recurse(); 1711 1712 return !AllUseless; 1713} // end of FilterChooser::filterProcessor(bool) 1714 1715// Decides on the best configuration of filter(s) to use in order to decode 1716// the instructions. A conflict of instructions may occur, in which case we 1717// dump the conflict set to the standard error. 1718void FilterChooser::doFilter() { 1719 unsigned Num = Opcodes.size(); 1720 assert(Num && "FilterChooser created with no instructions"); 1721 1722 // Try regions of consecutive known bit values first. 1723 if (filterProcessor(false)) 1724 return; 1725 1726 // Then regions of mixed bits (both known and unitialized bit values allowed). 1727 if (filterProcessor(true)) 1728 return; 1729 1730 // Heuristics to cope with conflict set {t2CMPrs, t2SUBSrr, t2SUBSrs} where 1731 // no single instruction for the maximum ATTR_MIXED region Inst{14-4} has a 1732 // well-known encoding pattern. In such case, we backtrack and scan for the 1733 // the very first consecutive ATTR_ALL_SET region and assign a filter to it. 1734 if (Num == 3 && filterProcessor(true, false)) 1735 return; 1736 1737 // If we come to here, the instruction decoding has failed. 1738 // Set the BestIndex to -1 to indicate so. 1739 BestIndex = -1; 1740} 1741 1742// emitTableEntries - Emit state machine entries to decode our share of 1743// instructions. 1744void FilterChooser::emitTableEntries(DecoderTableInfo &TableInfo) const { 1745 if (Opcodes.size() == 1) { 1746 // There is only one instruction in the set, which is great! 1747 // Call emitSingletonDecoder() to see whether there are any remaining 1748 // encodings bits. 1749 emitSingletonTableEntry(TableInfo, Opcodes[0]); 1750 return; 1751 } 1752 1753 // Choose the best filter to do the decodings! 1754 if (BestIndex != -1) { 1755 const Filter &Best = Filters[BestIndex]; 1756 if (Best.getNumFiltered() == 1) 1757 emitSingletonTableEntry(TableInfo, Best); 1758 else 1759 Best.emitTableEntry(TableInfo); 1760 return; 1761 } 1762 1763 // We don't know how to decode these instructions! Dump the 1764 // conflict set and bail. 1765 1766 // Print out useful conflict information for postmortem analysis. 1767 errs() << "Decoding Conflict:\n"; 1768 1769 dumpStack(errs(), "\t\t"); 1770 1771 for (unsigned i = 0; i < Opcodes.size(); ++i) { 1772 errs() << '\t'; 1773 emitNameWithID(errs(), Opcodes[i].EncodingID); 1774 errs() << " "; 1775 dumpBits( 1776 errs(), 1777 getBitsField(*AllInstructions[Opcodes[i].EncodingID].EncodingDef, "Inst")); 1778 errs() << '\n'; 1779 } 1780} 1781 1782static std::string findOperandDecoderMethod(TypedInit *TI) { 1783 std::string Decoder; 1784 1785 Record *Record = cast<DefInit>(TI)->getDef(); 1786 1787 RecordVal *DecoderString = Record->getValue("DecoderMethod"); 1788 StringInit *String = DecoderString ? 1789 dyn_cast<StringInit>(DecoderString->getValue()) : nullptr; 1790 if (String) { 1791 Decoder = std::string(String->getValue()); 1792 if (!Decoder.empty()) 1793 return Decoder; 1794 } 1795 1796 if (Record->isSubClassOf("RegisterOperand")) 1797 Record = Record->getValueAsDef("RegClass"); 1798 1799 if (Record->isSubClassOf("RegisterClass")) { 1800 Decoder = "Decode" + Record->getName().str() + "RegisterClass"; 1801 } else if (Record->isSubClassOf("PointerLikeRegClass")) { 1802 Decoder = "DecodePointerLikeRegClass" + 1803 utostr(Record->getValueAsInt("RegClassKind")); 1804 } 1805 1806 return Decoder; 1807} 1808 1809static bool 1810populateInstruction(CodeGenTarget &Target, const Record &EncodingDef, 1811 const CodeGenInstruction &CGI, unsigned Opc, 1812 std::map<unsigned, std::vector<OperandInfo>> &Operands) { 1813 const Record &Def = *CGI.TheDef; 1814 // If all the bit positions are not specified; do not decode this instruction. 1815 // We are bound to fail! For proper disassembly, the well-known encoding bits 1816 // of the instruction must be fully specified. 1817 1818 BitsInit &Bits = getBitsField(EncodingDef, "Inst"); 1819 if (Bits.allInComplete()) return false; 1820 1821 std::vector<OperandInfo> InsnOperands; 1822 1823 // If the instruction has specified a custom decoding hook, use that instead 1824 // of trying to auto-generate the decoder. 1825 StringRef InstDecoder = EncodingDef.getValueAsString("DecoderMethod"); 1826 if (InstDecoder != "") { 1827 bool HasCompleteInstDecoder = EncodingDef.getValueAsBit("hasCompleteDecoder"); 1828 InsnOperands.push_back( 1829 OperandInfo(std::string(InstDecoder), HasCompleteInstDecoder)); 1830 Operands[Opc] = InsnOperands; 1831 return true; 1832 } 1833 1834 // Generate a description of the operand of the instruction that we know 1835 // how to decode automatically. 1836 // FIXME: We'll need to have a way to manually override this as needed. 1837 1838 // Gather the outputs/inputs of the instruction, so we can find their 1839 // positions in the encoding. This assumes for now that they appear in the 1840 // MCInst in the order that they're listed. 1841 std::vector<std::pair<Init*, StringRef>> InOutOperands; 1842 DagInit *Out = Def.getValueAsDag("OutOperandList"); 1843 DagInit *In = Def.getValueAsDag("InOperandList"); 1844 for (unsigned i = 0; i < Out->getNumArgs(); ++i) 1845 InOutOperands.push_back(std::make_pair(Out->getArg(i), 1846 Out->getArgNameStr(i))); 1847 for (unsigned i = 0; i < In->getNumArgs(); ++i) 1848 InOutOperands.push_back(std::make_pair(In->getArg(i), 1849 In->getArgNameStr(i))); 1850 1851 // Search for tied operands, so that we can correctly instantiate 1852 // operands that are not explicitly represented in the encoding. 1853 std::map<std::string, std::string> TiedNames; 1854 for (unsigned i = 0; i < CGI.Operands.size(); ++i) { 1855 int tiedTo = CGI.Operands[i].getTiedRegister(); 1856 if (tiedTo != -1) { 1857 std::pair<unsigned, unsigned> SO = 1858 CGI.Operands.getSubOperandNumber(tiedTo); 1859 TiedNames[std::string(InOutOperands[i].second)] = 1860 std::string(InOutOperands[SO.first].second); 1861 TiedNames[std::string(InOutOperands[SO.first].second)] = 1862 std::string(InOutOperands[i].second); 1863 } 1864 } 1865 1866 std::map<std::string, std::vector<OperandInfo>> NumberedInsnOperands; 1867 std::set<std::string> NumberedInsnOperandsNoTie; 1868 if (Target.getInstructionSet()-> 1869 getValueAsBit("decodePositionallyEncodedOperands")) { 1870 const std::vector<RecordVal> &Vals = Def.getValues(); 1871 unsigned NumberedOp = 0; 1872 1873 std::set<unsigned> NamedOpIndices; 1874 if (Target.getInstructionSet()-> 1875 getValueAsBit("noNamedPositionallyEncodedOperands")) 1876 // Collect the set of operand indices that might correspond to named 1877 // operand, and skip these when assigning operands based on position. 1878 for (unsigned i = 0, e = Vals.size(); i != e; ++i) { 1879 unsigned OpIdx; 1880 if (!CGI.Operands.hasOperandNamed(Vals[i].getName(), OpIdx)) 1881 continue; 1882 1883 NamedOpIndices.insert(OpIdx); 1884 } 1885 1886 for (unsigned i = 0, e = Vals.size(); i != e; ++i) { 1887 // Ignore fixed fields in the record, we're looking for values like: 1888 // bits<5> RST = { ?, ?, ?, ?, ? }; 1889 if (Vals[i].getPrefix() || Vals[i].getValue()->isComplete()) 1890 continue; 1891 1892 // Determine if Vals[i] actually contributes to the Inst encoding. 1893 unsigned bi = 0; 1894 for (; bi < Bits.getNumBits(); ++bi) { 1895 VarInit *Var = nullptr; 1896 VarBitInit *BI = dyn_cast<VarBitInit>(Bits.getBit(bi)); 1897 if (BI) 1898 Var = dyn_cast<VarInit>(BI->getBitVar()); 1899 else 1900 Var = dyn_cast<VarInit>(Bits.getBit(bi)); 1901 1902 if (Var && Var->getName() == Vals[i].getName()) 1903 break; 1904 } 1905 1906 if (bi == Bits.getNumBits()) 1907 continue; 1908 1909 // Skip variables that correspond to explicitly-named operands. 1910 unsigned OpIdx; 1911 if (CGI.Operands.hasOperandNamed(Vals[i].getName(), OpIdx)) 1912 continue; 1913 1914 // Get the bit range for this operand: 1915 unsigned bitStart = bi++, bitWidth = 1; 1916 for (; bi < Bits.getNumBits(); ++bi) { 1917 VarInit *Var = nullptr; 1918 VarBitInit *BI = dyn_cast<VarBitInit>(Bits.getBit(bi)); 1919 if (BI) 1920 Var = dyn_cast<VarInit>(BI->getBitVar()); 1921 else 1922 Var = dyn_cast<VarInit>(Bits.getBit(bi)); 1923 1924 if (!Var) 1925 break; 1926 1927 if (Var->getName() != Vals[i].getName()) 1928 break; 1929 1930 ++bitWidth; 1931 } 1932 1933 unsigned NumberOps = CGI.Operands.size(); 1934 while (NumberedOp < NumberOps && 1935 (CGI.Operands.isFlatOperandNotEmitted(NumberedOp) || 1936 (!NamedOpIndices.empty() && NamedOpIndices.count( 1937 CGI.Operands.getSubOperandNumber(NumberedOp).first)))) 1938 ++NumberedOp; 1939 1940 OpIdx = NumberedOp++; 1941 1942 // OpIdx now holds the ordered operand number of Vals[i]. 1943 std::pair<unsigned, unsigned> SO = 1944 CGI.Operands.getSubOperandNumber(OpIdx); 1945 const std::string &Name = CGI.Operands[SO.first].Name; 1946 1947 LLVM_DEBUG(dbgs() << "Numbered operand mapping for " << Def.getName() 1948 << ": " << Name << "(" << SO.first << ", " << SO.second 1949 << ") => " << Vals[i].getName() << "\n"); 1950 1951 std::string Decoder; 1952 Record *TypeRecord = CGI.Operands[SO.first].Rec; 1953 1954 RecordVal *DecoderString = TypeRecord->getValue("DecoderMethod"); 1955 StringInit *String = DecoderString ? 1956 dyn_cast<StringInit>(DecoderString->getValue()) : nullptr; 1957 if (String && String->getValue() != "") 1958 Decoder = std::string(String->getValue()); 1959 1960 if (Decoder == "" && 1961 CGI.Operands[SO.first].MIOperandInfo && 1962 CGI.Operands[SO.first].MIOperandInfo->getNumArgs()) { 1963 Init *Arg = CGI.Operands[SO.first].MIOperandInfo-> 1964 getArg(SO.second); 1965 if (DefInit *DI = cast<DefInit>(Arg)) 1966 TypeRecord = DI->getDef(); 1967 } 1968 1969 bool isReg = false; 1970 if (TypeRecord->isSubClassOf("RegisterOperand")) 1971 TypeRecord = TypeRecord->getValueAsDef("RegClass"); 1972 if (TypeRecord->isSubClassOf("RegisterClass")) { 1973 Decoder = "Decode" + TypeRecord->getName().str() + "RegisterClass"; 1974 isReg = true; 1975 } else if (TypeRecord->isSubClassOf("PointerLikeRegClass")) { 1976 Decoder = "DecodePointerLikeRegClass" + 1977 utostr(TypeRecord->getValueAsInt("RegClassKind")); 1978 isReg = true; 1979 } 1980 1981 DecoderString = TypeRecord->getValue("DecoderMethod"); 1982 String = DecoderString ? 1983 dyn_cast<StringInit>(DecoderString->getValue()) : nullptr; 1984 if (!isReg && String && String->getValue() != "") 1985 Decoder = std::string(String->getValue()); 1986 1987 RecordVal *HasCompleteDecoderVal = 1988 TypeRecord->getValue("hasCompleteDecoder"); 1989 BitInit *HasCompleteDecoderBit = HasCompleteDecoderVal ? 1990 dyn_cast<BitInit>(HasCompleteDecoderVal->getValue()) : nullptr; 1991 bool HasCompleteDecoder = HasCompleteDecoderBit ? 1992 HasCompleteDecoderBit->getValue() : true; 1993 1994 OperandInfo OpInfo(Decoder, HasCompleteDecoder); 1995 OpInfo.addField(bitStart, bitWidth, 0); 1996 1997 NumberedInsnOperands[Name].push_back(OpInfo); 1998 1999 // FIXME: For complex operands with custom decoders we can't handle tied 2000 // sub-operands automatically. Skip those here and assume that this is 2001 // fixed up elsewhere. 2002 if (CGI.Operands[SO.first].MIOperandInfo && 2003 CGI.Operands[SO.first].MIOperandInfo->getNumArgs() > 1 && 2004 String && String->getValue() != "") 2005 NumberedInsnOperandsNoTie.insert(Name); 2006 } 2007 } 2008 2009 // For each operand, see if we can figure out where it is encoded. 2010 for (const auto &Op : InOutOperands) { 2011 if (!NumberedInsnOperands[std::string(Op.second)].empty()) { 2012 InsnOperands.insert(InsnOperands.end(), 2013 NumberedInsnOperands[std::string(Op.second)].begin(), 2014 NumberedInsnOperands[std::string(Op.second)].end()); 2015 continue; 2016 } 2017 if (!NumberedInsnOperands[TiedNames[std::string(Op.second)]].empty()) { 2018 if (!NumberedInsnOperandsNoTie.count(TiedNames[std::string(Op.second)])) { 2019 // Figure out to which (sub)operand we're tied. 2020 unsigned i = 2021 CGI.Operands.getOperandNamed(TiedNames[std::string(Op.second)]); 2022 int tiedTo = CGI.Operands[i].getTiedRegister(); 2023 if (tiedTo == -1) { 2024 i = CGI.Operands.getOperandNamed(Op.second); 2025 tiedTo = CGI.Operands[i].getTiedRegister(); 2026 } 2027 2028 if (tiedTo != -1) { 2029 std::pair<unsigned, unsigned> SO = 2030 CGI.Operands.getSubOperandNumber(tiedTo); 2031 2032 InsnOperands.push_back( 2033 NumberedInsnOperands[TiedNames[std::string(Op.second)]] 2034 [SO.second]); 2035 } 2036 } 2037 continue; 2038 } 2039 2040 TypedInit *TI = cast<TypedInit>(Op.first); 2041 2042 // At this point, we can locate the decoder field, but we need to know how 2043 // to interpret it. As a first step, require the target to provide 2044 // callbacks for decoding register classes. 2045 std::string Decoder = findOperandDecoderMethod(TI); 2046 Record *TypeRecord = cast<DefInit>(TI)->getDef(); 2047 2048 RecordVal *HasCompleteDecoderVal = 2049 TypeRecord->getValue("hasCompleteDecoder"); 2050 BitInit *HasCompleteDecoderBit = HasCompleteDecoderVal ? 2051 dyn_cast<BitInit>(HasCompleteDecoderVal->getValue()) : nullptr; 2052 bool HasCompleteDecoder = HasCompleteDecoderBit ? 2053 HasCompleteDecoderBit->getValue() : true; 2054 2055 OperandInfo OpInfo(Decoder, HasCompleteDecoder); 2056 2057 // Some bits of the operand may be required to be 1 depending on the 2058 // instruction's encoding. Collect those bits. 2059 if (const RecordVal *EncodedValue = EncodingDef.getValue(Op.second)) 2060 if (const BitsInit *OpBits = dyn_cast<BitsInit>(EncodedValue->getValue())) 2061 for (unsigned I = 0; I < OpBits->getNumBits(); ++I) 2062 if (const BitInit *OpBit = dyn_cast<BitInit>(OpBits->getBit(I))) 2063 if (OpBit->getValue()) 2064 OpInfo.InitValue |= 1ULL << I; 2065 2066 unsigned Base = ~0U; 2067 unsigned Width = 0; 2068 unsigned Offset = 0; 2069 2070 for (unsigned bi = 0; bi < Bits.getNumBits(); ++bi) { 2071 VarInit *Var = nullptr; 2072 VarBitInit *BI = dyn_cast<VarBitInit>(Bits.getBit(bi)); 2073 if (BI) 2074 Var = dyn_cast<VarInit>(BI->getBitVar()); 2075 else 2076 Var = dyn_cast<VarInit>(Bits.getBit(bi)); 2077 2078 if (!Var) { 2079 if (Base != ~0U) { 2080 OpInfo.addField(Base, Width, Offset); 2081 Base = ~0U; 2082 Width = 0; 2083 Offset = 0; 2084 } 2085 continue; 2086 } 2087 2088 if (Var->getName() != Op.second && 2089 Var->getName() != TiedNames[std::string(Op.second)]) { 2090 if (Base != ~0U) { 2091 OpInfo.addField(Base, Width, Offset); 2092 Base = ~0U; 2093 Width = 0; 2094 Offset = 0; 2095 } 2096 continue; 2097 } 2098 2099 if (Base == ~0U) { 2100 Base = bi; 2101 Width = 1; 2102 Offset = BI ? BI->getBitNum() : 0; 2103 } else if (BI && BI->getBitNum() != Offset + Width) { 2104 OpInfo.addField(Base, Width, Offset); 2105 Base = bi; 2106 Width = 1; 2107 Offset = BI->getBitNum(); 2108 } else { 2109 ++Width; 2110 } 2111 } 2112 2113 if (Base != ~0U) 2114 OpInfo.addField(Base, Width, Offset); 2115 2116 if (OpInfo.numFields() > 0) 2117 InsnOperands.push_back(OpInfo); 2118 } 2119 2120 Operands[Opc] = InsnOperands; 2121 2122#if 0 2123 LLVM_DEBUG({ 2124 // Dumps the instruction encoding bits. 2125 dumpBits(errs(), Bits); 2126 2127 errs() << '\n'; 2128 2129 // Dumps the list of operand info. 2130 for (unsigned i = 0, e = CGI.Operands.size(); i != e; ++i) { 2131 const CGIOperandList::OperandInfo &Info = CGI.Operands[i]; 2132 const std::string &OperandName = Info.Name; 2133 const Record &OperandDef = *Info.Rec; 2134 2135 errs() << "\t" << OperandName << " (" << OperandDef.getName() << ")\n"; 2136 } 2137 }); 2138#endif 2139 2140 return true; 2141} 2142 2143// emitFieldFromInstruction - Emit the templated helper function 2144// fieldFromInstruction(). 2145// On Windows we make sure that this function is not inlined when 2146// using the VS compiler. It has a bug which causes the function 2147// to be optimized out in some circustances. See llvm.org/pr38292 2148static void emitFieldFromInstruction(formatted_raw_ostream &OS) { 2149 OS << "// Helper functions for extracting fields from encoded instructions.\n" 2150 << "// InsnType must either be integral or an APInt-like object that " 2151 "must:\n" 2152 << "// * Have a static const max_size_in_bits equal to the number of bits " 2153 "in the\n" 2154 << "// encoding.\n" 2155 << "// * be default-constructible and copy-constructible\n" 2156 << "// * be constructible from a uint64_t\n" 2157 << "// * be constructible from an APInt (this can be private)\n" 2158 << "// * Support getBitsSet(loBit, hiBit)\n" 2159 << "// * be convertible to uint64_t\n" 2160 << "// * Support the ~, &, ==, !=, and |= operators with other objects of " 2161 "the same type\n" 2162 << "// * Support shift (<<, >>) with signed and unsigned integers on the " 2163 "RHS\n" 2164 << "// * Support put (<<) to raw_ostream&\n" 2165 << "template<typename InsnType>\n" 2166 << "#if defined(_MSC_VER) && !defined(__clang__)\n" 2167 << "__declspec(noinline)\n" 2168 << "#endif\n" 2169 << "static InsnType fieldFromInstruction(InsnType insn, unsigned " 2170 "startBit,\n" 2171 << " unsigned numBits, " 2172 "std::true_type) {\n" 2173 << " assert(startBit + numBits <= 64 && \"Cannot support >64-bit " 2174 "extractions!\");\n" 2175 << " assert(startBit + numBits <= (sizeof(InsnType) * 8) &&\n" 2176 << " \"Instruction field out of bounds!\");\n" 2177 << " InsnType fieldMask;\n" 2178 << " if (numBits == sizeof(InsnType) * 8)\n" 2179 << " fieldMask = (InsnType)(-1LL);\n" 2180 << " else\n" 2181 << " fieldMask = (((InsnType)1 << numBits) - 1) << startBit;\n" 2182 << " return (insn & fieldMask) >> startBit;\n" 2183 << "}\n" 2184 << "\n" 2185 << "template<typename InsnType>\n" 2186 << "static InsnType fieldFromInstruction(InsnType insn, unsigned " 2187 "startBit,\n" 2188 << " unsigned numBits, " 2189 "std::false_type) {\n" 2190 << " assert(startBit + numBits <= InsnType::max_size_in_bits && " 2191 "\"Instruction field out of bounds!\");\n" 2192 << " InsnType fieldMask = InsnType::getBitsSet(0, numBits);\n" 2193 << " return (insn >> startBit) & fieldMask;\n" 2194 << "}\n" 2195 << "\n" 2196 << "template<typename InsnType>\n" 2197 << "static InsnType fieldFromInstruction(InsnType insn, unsigned " 2198 "startBit,\n" 2199 << " unsigned numBits) {\n" 2200 << " return fieldFromInstruction(insn, startBit, numBits, " 2201 "std::is_integral<InsnType>());\n" 2202 << "}\n\n"; 2203} 2204 2205// emitDecodeInstruction - Emit the templated helper function 2206// decodeInstruction(). 2207static void emitDecodeInstruction(formatted_raw_ostream &OS) { 2208 OS << "template<typename InsnType>\n" 2209 << "static DecodeStatus decodeInstruction(const uint8_t DecodeTable[], " 2210 "MCInst &MI,\n" 2211 << " InsnType insn, uint64_t " 2212 "Address,\n" 2213 << " const void *DisAsm,\n" 2214 << " const MCSubtargetInfo &STI) {\n" 2215 << " const FeatureBitset& Bits = STI.getFeatureBits();\n" 2216 << "\n" 2217 << " const uint8_t *Ptr = DecodeTable;\n" 2218 << " InsnType CurFieldValue = 0;\n" 2219 << " DecodeStatus S = MCDisassembler::Success;\n" 2220 << " while (true) {\n" 2221 << " ptrdiff_t Loc = Ptr - DecodeTable;\n" 2222 << " switch (*Ptr) {\n" 2223 << " default:\n" 2224 << " errs() << Loc << \": Unexpected decode table opcode!\\n\";\n" 2225 << " return MCDisassembler::Fail;\n" 2226 << " case MCD::OPC_ExtractField: {\n" 2227 << " unsigned Start = *++Ptr;\n" 2228 << " unsigned Len = *++Ptr;\n" 2229 << " ++Ptr;\n" 2230 << " CurFieldValue = fieldFromInstruction(insn, Start, Len);\n" 2231 << " LLVM_DEBUG(dbgs() << Loc << \": OPC_ExtractField(\" << Start << " 2232 "\", \"\n" 2233 << " << Len << \"): \" << CurFieldValue << \"\\n\");\n" 2234 << " break;\n" 2235 << " }\n" 2236 << " case MCD::OPC_FilterValue: {\n" 2237 << " // Decode the field value.\n" 2238 << " unsigned Len;\n" 2239 << " InsnType Val = decodeULEB128(++Ptr, &Len);\n" 2240 << " Ptr += Len;\n" 2241 << " // NumToSkip is a plain 24-bit integer.\n" 2242 << " unsigned NumToSkip = *Ptr++;\n" 2243 << " NumToSkip |= (*Ptr++) << 8;\n" 2244 << " NumToSkip |= (*Ptr++) << 16;\n" 2245 << "\n" 2246 << " // Perform the filter operation.\n" 2247 << " if (Val != CurFieldValue)\n" 2248 << " Ptr += NumToSkip;\n" 2249 << " LLVM_DEBUG(dbgs() << Loc << \": OPC_FilterValue(\" << Val << " 2250 "\", \" << NumToSkip\n" 2251 << " << \"): \" << ((Val != CurFieldValue) ? \"FAIL:\" " 2252 ": \"PASS:\")\n" 2253 << " << \" continuing at \" << (Ptr - DecodeTable) << " 2254 "\"\\n\");\n" 2255 << "\n" 2256 << " break;\n" 2257 << " }\n" 2258 << " case MCD::OPC_CheckField: {\n" 2259 << " unsigned Start = *++Ptr;\n" 2260 << " unsigned Len = *++Ptr;\n" 2261 << " InsnType FieldValue = fieldFromInstruction(insn, Start, Len);\n" 2262 << " // Decode the field value.\n" 2263 << " InsnType ExpectedValue = decodeULEB128(++Ptr, &Len);\n" 2264 << " Ptr += Len;\n" 2265 << " // NumToSkip is a plain 24-bit integer.\n" 2266 << " unsigned NumToSkip = *Ptr++;\n" 2267 << " NumToSkip |= (*Ptr++) << 8;\n" 2268 << " NumToSkip |= (*Ptr++) << 16;\n" 2269 << "\n" 2270 << " // If the actual and expected values don't match, skip.\n" 2271 << " if (ExpectedValue != FieldValue)\n" 2272 << " Ptr += NumToSkip;\n" 2273 << " LLVM_DEBUG(dbgs() << Loc << \": OPC_CheckField(\" << Start << " 2274 "\", \"\n" 2275 << " << Len << \", \" << ExpectedValue << \", \" << " 2276 "NumToSkip\n" 2277 << " << \"): FieldValue = \" << FieldValue << \", " 2278 "ExpectedValue = \"\n" 2279 << " << ExpectedValue << \": \"\n" 2280 << " << ((ExpectedValue == FieldValue) ? \"PASS\\n\" : " 2281 "\"FAIL\\n\"));\n" 2282 << " break;\n" 2283 << " }\n" 2284 << " case MCD::OPC_CheckPredicate: {\n" 2285 << " unsigned Len;\n" 2286 << " // Decode the Predicate Index value.\n" 2287 << " unsigned PIdx = decodeULEB128(++Ptr, &Len);\n" 2288 << " Ptr += Len;\n" 2289 << " // NumToSkip is a plain 24-bit integer.\n" 2290 << " unsigned NumToSkip = *Ptr++;\n" 2291 << " NumToSkip |= (*Ptr++) << 8;\n" 2292 << " NumToSkip |= (*Ptr++) << 16;\n" 2293 << " // Check the predicate.\n" 2294 << " bool Pred;\n" 2295 << " if (!(Pred = checkDecoderPredicate(PIdx, Bits)))\n" 2296 << " Ptr += NumToSkip;\n" 2297 << " (void)Pred;\n" 2298 << " LLVM_DEBUG(dbgs() << Loc << \": OPC_CheckPredicate(\" << PIdx " 2299 "<< \"): \"\n" 2300 << " << (Pred ? \"PASS\\n\" : \"FAIL\\n\"));\n" 2301 << "\n" 2302 << " break;\n" 2303 << " }\n" 2304 << " case MCD::OPC_Decode: {\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 << "\n" 2312 << " MI.clear();\n" 2313 << " MI.setOpcode(Opc);\n" 2314 << " bool DecodeComplete;\n" 2315 << " S = decodeToMCInst(S, DecodeIdx, insn, MI, Address, DisAsm, " 2316 "DecodeComplete);\n" 2317 << " assert(DecodeComplete);\n" 2318 << "\n" 2319 << " LLVM_DEBUG(dbgs() << Loc << \": OPC_Decode: opcode \" << Opc\n" 2320 << " << \", using decoder \" << DecodeIdx << \": \"\n" 2321 << " << (S != MCDisassembler::Fail ? \"PASS\" : " 2322 "\"FAIL\") << \"\\n\");\n" 2323 << " return S;\n" 2324 << " }\n" 2325 << " case MCD::OPC_TryDecode: {\n" 2326 << " unsigned Len;\n" 2327 << " // Decode the Opcode value.\n" 2328 << " unsigned Opc = decodeULEB128(++Ptr, &Len);\n" 2329 << " Ptr += Len;\n" 2330 << " unsigned DecodeIdx = decodeULEB128(Ptr, &Len);\n" 2331 << " Ptr += Len;\n" 2332 << " // NumToSkip is a plain 24-bit integer.\n" 2333 << " unsigned NumToSkip = *Ptr++;\n" 2334 << " NumToSkip |= (*Ptr++) << 8;\n" 2335 << " NumToSkip |= (*Ptr++) << 16;\n" 2336 << "\n" 2337 << " // Perform the decode operation.\n" 2338 << " MCInst TmpMI;\n" 2339 << " TmpMI.setOpcode(Opc);\n" 2340 << " bool DecodeComplete;\n" 2341 << " S = decodeToMCInst(S, DecodeIdx, insn, TmpMI, Address, DisAsm, " 2342 "DecodeComplete);\n" 2343 << " LLVM_DEBUG(dbgs() << Loc << \": OPC_TryDecode: opcode \" << " 2344 "Opc\n" 2345 << " << \", using decoder \" << DecodeIdx << \": \");\n" 2346 << "\n" 2347 << " if (DecodeComplete) {\n" 2348 << " // Decoding complete.\n" 2349 << " LLVM_DEBUG(dbgs() << (S != MCDisassembler::Fail ? \"PASS\" : " 2350 "\"FAIL\") << \"\\n\");\n" 2351 << " MI = TmpMI;\n" 2352 << " return S;\n" 2353 << " } else {\n" 2354 << " assert(S == MCDisassembler::Fail);\n" 2355 << " // If the decoding was incomplete, skip.\n" 2356 << " Ptr += NumToSkip;\n" 2357 << " LLVM_DEBUG(dbgs() << \"FAIL: continuing at \" << (Ptr - " 2358 "DecodeTable) << \"\\n\");\n" 2359 << " // Reset decode status. This also drops a SoftFail status " 2360 "that could be\n" 2361 << " // set before the decode attempt.\n" 2362 << " S = MCDisassembler::Success;\n" 2363 << " }\n" 2364 << " break;\n" 2365 << " }\n" 2366 << " case MCD::OPC_SoftFail: {\n" 2367 << " // Decode the mask values.\n" 2368 << " unsigned Len;\n" 2369 << " InsnType PositiveMask = decodeULEB128(++Ptr, &Len);\n" 2370 << " Ptr += Len;\n" 2371 << " InsnType NegativeMask = decodeULEB128(Ptr, &Len);\n" 2372 << " Ptr += Len;\n" 2373 << " bool Fail = (insn & PositiveMask) || (~insn & NegativeMask);\n" 2374 << " if (Fail)\n" 2375 << " S = MCDisassembler::SoftFail;\n" 2376 << " LLVM_DEBUG(dbgs() << Loc << \": OPC_SoftFail: \" << (Fail ? " 2377 "\"FAIL\\n\":\"PASS\\n\"));\n" 2378 << " break;\n" 2379 << " }\n" 2380 << " case MCD::OPC_Fail: {\n" 2381 << " LLVM_DEBUG(dbgs() << Loc << \": OPC_Fail\\n\");\n" 2382 << " return MCDisassembler::Fail;\n" 2383 << " }\n" 2384 << " }\n" 2385 << " }\n" 2386 << " llvm_unreachable(\"bogosity detected in disassembler state " 2387 "machine!\");\n" 2388 << "}\n\n"; 2389} 2390 2391// Emits disassembler code for instruction decoding. 2392void FixedLenDecoderEmitter::run(raw_ostream &o) { 2393 formatted_raw_ostream OS(o); 2394 OS << "#include \"llvm/MC/MCInst.h\"\n"; 2395 OS << "#include \"llvm/Support/Debug.h\"\n"; 2396 OS << "#include \"llvm/Support/DataTypes.h\"\n"; 2397 OS << "#include \"llvm/Support/LEB128.h\"\n"; 2398 OS << "#include \"llvm/Support/raw_ostream.h\"\n"; 2399 OS << "#include <assert.h>\n"; 2400 OS << '\n'; 2401 OS << "namespace llvm {\n\n"; 2402 2403 emitFieldFromInstruction(OS); 2404 2405 Target.reverseBitsForLittleEndianEncoding(); 2406 2407 // Parameterize the decoders based on namespace and instruction width. 2408 std::set<StringRef> HwModeNames; 2409 const auto &NumberedInstructions = Target.getInstructionsByEnumValue(); 2410 NumberedEncodings.reserve(NumberedInstructions.size()); 2411 DenseMap<Record *, unsigned> IndexOfInstruction; 2412 // First, collect all HwModes referenced by the target. 2413 for (const auto &NumberedInstruction : NumberedInstructions) { 2414 IndexOfInstruction[NumberedInstruction->TheDef] = NumberedEncodings.size(); 2415 2416 if (const RecordVal *RV = 2417 NumberedInstruction->TheDef->getValue("EncodingInfos")) { 2418 if (auto *DI = dyn_cast_or_null<DefInit>(RV->getValue())) { 2419 const CodeGenHwModes &HWM = Target.getHwModes(); 2420 EncodingInfoByHwMode EBM(DI->getDef(), HWM); 2421 for (auto &KV : EBM.Map) 2422 HwModeNames.insert(HWM.getMode(KV.first).Name); 2423 } 2424 } 2425 } 2426 2427 // If HwModeNames is empty, add the empty string so we always have one HwMode. 2428 if (HwModeNames.empty()) 2429 HwModeNames.insert(""); 2430 2431 for (const auto &NumberedInstruction : NumberedInstructions) { 2432 IndexOfInstruction[NumberedInstruction->TheDef] = NumberedEncodings.size(); 2433 2434 if (const RecordVal *RV = 2435 NumberedInstruction->TheDef->getValue("EncodingInfos")) { 2436 if (DefInit *DI = dyn_cast_or_null<DefInit>(RV->getValue())) { 2437 const CodeGenHwModes &HWM = Target.getHwModes(); 2438 EncodingInfoByHwMode EBM(DI->getDef(), HWM); 2439 for (auto &KV : EBM.Map) { 2440 NumberedEncodings.emplace_back(KV.second, NumberedInstruction, 2441 HWM.getMode(KV.first).Name); 2442 HwModeNames.insert(HWM.getMode(KV.first).Name); 2443 } 2444 continue; 2445 } 2446 } 2447 // This instruction is encoded the same on all HwModes. Emit it for all 2448 // HwModes. 2449 for (StringRef HwModeName : HwModeNames) 2450 NumberedEncodings.emplace_back(NumberedInstruction->TheDef, 2451 NumberedInstruction, HwModeName); 2452 } 2453 for (const auto &NumberedAlias : RK.getAllDerivedDefinitions("AdditionalEncoding")) 2454 NumberedEncodings.emplace_back( 2455 NumberedAlias, 2456 &Target.getInstruction(NumberedAlias->getValueAsDef("AliasOf"))); 2457 2458 std::map<std::pair<std::string, unsigned>, std::vector<EncodingIDAndOpcode>> 2459 OpcMap; 2460 std::map<unsigned, std::vector<OperandInfo>> Operands; 2461 2462 for (unsigned i = 0; i < NumberedEncodings.size(); ++i) { 2463 const Record *EncodingDef = NumberedEncodings[i].EncodingDef; 2464 const CodeGenInstruction *Inst = NumberedEncodings[i].Inst; 2465 const Record *Def = Inst->TheDef; 2466 unsigned Size = EncodingDef->getValueAsInt("Size"); 2467 if (Def->getValueAsString("Namespace") == "TargetOpcode" || 2468 Def->getValueAsBit("isPseudo") || 2469 Def->getValueAsBit("isAsmParserOnly") || 2470 Def->getValueAsBit("isCodeGenOnly")) { 2471 NumEncodingsLackingDisasm++; 2472 continue; 2473 } 2474 2475 if (i < NumberedInstructions.size()) 2476 NumInstructions++; 2477 NumEncodings++; 2478 2479 if (!Size) 2480 continue; 2481 2482 if (populateInstruction(Target, *EncodingDef, *Inst, i, Operands)) { 2483 std::string DecoderNamespace = 2484 std::string(EncodingDef->getValueAsString("DecoderNamespace")); 2485 if (!NumberedEncodings[i].HwModeName.empty()) 2486 DecoderNamespace += 2487 std::string("_") + NumberedEncodings[i].HwModeName.str(); 2488 OpcMap[std::make_pair(DecoderNamespace, Size)].emplace_back( 2489 i, IndexOfInstruction.find(Def)->second); 2490 } else { 2491 NumEncodingsOmitted++; 2492 } 2493 } 2494 2495 DecoderTableInfo TableInfo; 2496 for (const auto &Opc : OpcMap) { 2497 // Emit the decoder for this namespace+width combination. 2498 ArrayRef<EncodingAndInst> NumberedEncodingsRef( 2499 NumberedEncodings.data(), NumberedEncodings.size()); 2500 FilterChooser FC(NumberedEncodingsRef, Opc.second, Operands, 2501 8 * Opc.first.second, this); 2502 2503 // The decode table is cleared for each top level decoder function. The 2504 // predicates and decoders themselves, however, are shared across all 2505 // decoders to give more opportunities for uniqueing. 2506 TableInfo.Table.clear(); 2507 TableInfo.FixupStack.clear(); 2508 TableInfo.Table.reserve(16384); 2509 TableInfo.FixupStack.emplace_back(); 2510 FC.emitTableEntries(TableInfo); 2511 // Any NumToSkip fixups in the top level scope can resolve to the 2512 // OPC_Fail at the end of the table. 2513 assert(TableInfo.FixupStack.size() == 1 && "fixup stack phasing error!"); 2514 // Resolve any NumToSkip fixups in the current scope. 2515 resolveTableFixups(TableInfo.Table, TableInfo.FixupStack.back(), 2516 TableInfo.Table.size()); 2517 TableInfo.FixupStack.clear(); 2518 2519 TableInfo.Table.push_back(MCD::OPC_Fail); 2520 2521 // Print the table to the output stream. 2522 emitTable(OS, TableInfo.Table, 0, FC.getBitWidth(), Opc.first.first); 2523 OS.flush(); 2524 } 2525 2526 // Emit the predicate function. 2527 emitPredicateFunction(OS, TableInfo.Predicates, 0); 2528 2529 // Emit the decoder function. 2530 emitDecoderFunction(OS, TableInfo.Decoders, 0); 2531 2532 // Emit the main entry point for the decoder, decodeInstruction(). 2533 emitDecodeInstruction(OS); 2534 2535 OS << "\n} // end namespace llvm\n"; 2536} 2537 2538namespace llvm { 2539 2540void EmitFixedLenDecoder(RecordKeeper &RK, raw_ostream &OS, 2541 const std::string &PredicateNamespace, 2542 const std::string &GPrefix, 2543 const std::string &GPostfix, const std::string &ROK, 2544 const std::string &RFail, const std::string &L) { 2545 FixedLenDecoderEmitter(RK, PredicateNamespace, GPrefix, GPostfix, 2546 ROK, RFail, L).run(OS); 2547} 2548 2549} // end namespace llvm 2550