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