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 #define DEBUG_TYPE "decoder-emitter" 16 17 #include "FixedLenDecoderEmitter.h" 18 #include "CodeGenTarget.h" 19 #include "llvm/TableGen/Record.h" 20 #include "llvm/ADT/APInt.h" 21 #include "llvm/ADT/StringExtras.h" 22 #include "llvm/Support/Debug.h" 23 #include "llvm/Support/raw_ostream.h" 24 25 #include <vector> 26 #include <map> 27 #include <string> 28 29 using namespace llvm; 30 31 // The set (BIT_TRUE, BIT_FALSE, BIT_UNSET) represents a ternary logic system 32 // for a bit value. 33 // 34 // BIT_UNFILTERED is used as the init value for a filter position. It is used 35 // only for filter processings. 36 typedef enum { 37 BIT_TRUE, // '1' 38 BIT_FALSE, // '0' 39 BIT_UNSET, // '?' 40 BIT_UNFILTERED // unfiltered 41 } bit_value_t; 42 43 static bool ValueSet(bit_value_t V) { 44 return (V == BIT_TRUE || V == BIT_FALSE); 45 } 46 static bool ValueNotSet(bit_value_t V) { 47 return (V == BIT_UNSET); 48 } 49 static int Value(bit_value_t V) { 50 return ValueNotSet(V) ? -1 : (V == BIT_FALSE ? 0 : 1); 51 } 52 static bit_value_t bitFromBits(const BitsInit &bits, unsigned index) { 53 if (BitInit *bit = dynamic_cast<BitInit*>(bits.getBit(index))) 54 return bit->getValue() ? BIT_TRUE : BIT_FALSE; 55 56 // The bit is uninitialized. 57 return BIT_UNSET; 58 } 59 // Prints the bit value for each position. 60 static void dumpBits(raw_ostream &o, const BitsInit &bits) { 61 unsigned index; 62 63 for (index = bits.getNumBits(); index > 0; index--) { 64 switch (bitFromBits(bits, index - 1)) { 65 case BIT_TRUE: 66 o << "1"; 67 break; 68 case BIT_FALSE: 69 o << "0"; 70 break; 71 case BIT_UNSET: 72 o << "_"; 73 break; 74 default: 75 llvm_unreachable("unexpected return value from bitFromBits"); 76 } 77 } 78 } 79 80 static BitsInit &getBitsField(const Record &def, const char *str) { 81 BitsInit *bits = def.getValueAsBitsInit(str); 82 return *bits; 83 } 84 85 // Forward declaration. 86 class FilterChooser; 87 88 // Representation of the instruction to work on. 89 typedef std::vector<bit_value_t> insn_t; 90 91 /// Filter - Filter works with FilterChooser to produce the decoding tree for 92 /// the ISA. 93 /// 94 /// It is useful to think of a Filter as governing the switch stmts of the 95 /// decoding tree in a certain level. Each case stmt delegates to an inferior 96 /// FilterChooser to decide what further decoding logic to employ, or in another 97 /// words, what other remaining bits to look at. The FilterChooser eventually 98 /// chooses a best Filter to do its job. 99 /// 100 /// This recursive scheme ends when the number of Opcodes assigned to the 101 /// FilterChooser becomes 1 or if there is a conflict. A conflict happens when 102 /// the Filter/FilterChooser combo does not know how to distinguish among the 103 /// Opcodes assigned. 104 /// 105 /// An example of a conflict is 106 /// 107 /// Conflict: 108 /// 111101000.00........00010000.... 109 /// 111101000.00........0001........ 110 /// 1111010...00........0001........ 111 /// 1111010...00.................... 112 /// 1111010......................... 113 /// 1111............................ 114 /// ................................ 115 /// VST4q8a 111101000_00________00010000____ 116 /// VST4q8b 111101000_00________00010000____ 117 /// 118 /// The Debug output shows the path that the decoding tree follows to reach the 119 /// the conclusion that there is a conflict. VST4q8a is a vst4 to double-spaced 120 /// even registers, while VST4q8b is a vst4 to double-spaced odd regsisters. 121 /// 122 /// The encoding info in the .td files does not specify this meta information, 123 /// which could have been used by the decoder to resolve the conflict. The 124 /// decoder could try to decode the even/odd register numbering and assign to 125 /// VST4q8a or VST4q8b, but for the time being, the decoder chooses the "a" 126 /// version and return the Opcode since the two have the same Asm format string. 127 class Filter { 128 protected: 129 const FilterChooser *Owner;// points to the FilterChooser who owns this filter 130 unsigned StartBit; // the starting bit position 131 unsigned NumBits; // number of bits to filter 132 bool Mixed; // a mixed region contains both set and unset bits 133 134 // Map of well-known segment value to the set of uid's with that value. 135 std::map<uint64_t, std::vector<unsigned> > FilteredInstructions; 136 137 // Set of uid's with non-constant segment values. 138 std::vector<unsigned> VariableInstructions; 139 140 // Map of well-known segment value to its delegate. 141 std::map<unsigned, const FilterChooser*> FilterChooserMap; 142 143 // Number of instructions which fall under FilteredInstructions category. 144 unsigned NumFiltered; 145 146 // Keeps track of the last opcode in the filtered bucket. 147 unsigned LastOpcFiltered; 148 149 public: 150 unsigned getNumFiltered() const { return NumFiltered; } 151 unsigned getSingletonOpc() const { 152 assert(NumFiltered == 1); 153 return LastOpcFiltered; 154 } 155 // Return the filter chooser for the group of instructions without constant 156 // segment values. 157 const FilterChooser &getVariableFC() const { 158 assert(NumFiltered == 1); 159 assert(FilterChooserMap.size() == 1); 160 return *(FilterChooserMap.find((unsigned)-1)->second); 161 } 162 163 Filter(const Filter &f); 164 Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, bool mixed); 165 166 ~Filter(); 167 168 // Divides the decoding task into sub tasks and delegates them to the 169 // inferior FilterChooser's. 170 // 171 // A special case arises when there's only one entry in the filtered 172 // instructions. In order to unambiguously decode the singleton, we need to 173 // match the remaining undecoded encoding bits against the singleton. 174 void recurse(); 175 176 // Emit code to decode instructions given a segment or segments of bits. 177 void emit(raw_ostream &o, unsigned &Indentation) const; 178 179 // Returns the number of fanout produced by the filter. More fanout implies 180 // the filter distinguishes more categories of instructions. 181 unsigned usefulness() const; 182 }; // End of class Filter 183 184 // These are states of our finite state machines used in FilterChooser's 185 // filterProcessor() which produces the filter candidates to use. 186 typedef enum { 187 ATTR_NONE, 188 ATTR_FILTERED, 189 ATTR_ALL_SET, 190 ATTR_ALL_UNSET, 191 ATTR_MIXED 192 } bitAttr_t; 193 194 /// FilterChooser - FilterChooser chooses the best filter among a set of Filters 195 /// in order to perform the decoding of instructions at the current level. 196 /// 197 /// Decoding proceeds from the top down. Based on the well-known encoding bits 198 /// of instructions available, FilterChooser builds up the possible Filters that 199 /// can further the task of decoding by distinguishing among the remaining 200 /// candidate instructions. 201 /// 202 /// Once a filter has been chosen, it is called upon to divide the decoding task 203 /// into sub-tasks and delegates them to its inferior FilterChoosers for further 204 /// processings. 205 /// 206 /// It is useful to think of a Filter as governing the switch stmts of the 207 /// decoding tree. And each case is delegated to an inferior FilterChooser to 208 /// decide what further remaining bits to look at. 209 class FilterChooser { 210 protected: 211 friend class Filter; 212 213 // Vector of codegen instructions to choose our filter. 214 const std::vector<const CodeGenInstruction*> &AllInstructions; 215 216 // Vector of uid's for this filter chooser to work on. 217 const std::vector<unsigned> &Opcodes; 218 219 // Lookup table for the operand decoding of instructions. 220 const std::map<unsigned, std::vector<OperandInfo> > &Operands; 221 222 // Vector of candidate filters. 223 std::vector<Filter> Filters; 224 225 // Array of bit values passed down from our parent. 226 // Set to all BIT_UNFILTERED's for Parent == NULL. 227 std::vector<bit_value_t> FilterBitValues; 228 229 // Links to the FilterChooser above us in the decoding tree. 230 const FilterChooser *Parent; 231 232 // Index of the best filter from Filters. 233 int BestIndex; 234 235 // Width of instructions 236 unsigned BitWidth; 237 238 // Parent emitter 239 const FixedLenDecoderEmitter *Emitter; 240 241 public: 242 FilterChooser(const FilterChooser &FC) 243 : AllInstructions(FC.AllInstructions), Opcodes(FC.Opcodes), 244 Operands(FC.Operands), Filters(FC.Filters), 245 FilterBitValues(FC.FilterBitValues), Parent(FC.Parent), 246 BestIndex(FC.BestIndex), BitWidth(FC.BitWidth), 247 Emitter(FC.Emitter) { } 248 249 FilterChooser(const std::vector<const CodeGenInstruction*> &Insts, 250 const std::vector<unsigned> &IDs, 251 const std::map<unsigned, std::vector<OperandInfo> > &Ops, 252 unsigned BW, 253 const FixedLenDecoderEmitter *E) 254 : AllInstructions(Insts), Opcodes(IDs), Operands(Ops), Filters(), 255 Parent(NULL), BestIndex(-1), BitWidth(BW), Emitter(E) { 256 for (unsigned i = 0; i < BitWidth; ++i) 257 FilterBitValues.push_back(BIT_UNFILTERED); 258 259 doFilter(); 260 } 261 262 FilterChooser(const std::vector<const CodeGenInstruction*> &Insts, 263 const std::vector<unsigned> &IDs, 264 const std::map<unsigned, std::vector<OperandInfo> > &Ops, 265 const std::vector<bit_value_t> &ParentFilterBitValues, 266 const FilterChooser &parent) 267 : AllInstructions(Insts), Opcodes(IDs), Operands(Ops), 268 Filters(), FilterBitValues(ParentFilterBitValues), 269 Parent(&parent), BestIndex(-1), BitWidth(parent.BitWidth), 270 Emitter(parent.Emitter) { 271 doFilter(); 272 } 273 274 // The top level filter chooser has NULL as its parent. 275 bool isTopLevel() const { return Parent == NULL; } 276 277 // Emit the top level typedef and decodeInstruction() function. 278 void emitTop(raw_ostream &o, unsigned Indentation, 279 const std::string &Namespace) const; 280 281 protected: 282 // Populates the insn given the uid. 283 void insnWithID(insn_t &Insn, unsigned Opcode) const { 284 BitsInit &Bits = getBitsField(*AllInstructions[Opcode]->TheDef, "Inst"); 285 286 // We may have a SoftFail bitmask, which specifies a mask where an encoding 287 // may differ from the value in "Inst" and yet still be valid, but the 288 // disassembler should return SoftFail instead of Success. 289 // 290 // This is used for marking UNPREDICTABLE instructions in the ARM world. 291 BitsInit *SFBits = 292 AllInstructions[Opcode]->TheDef->getValueAsBitsInit("SoftFail"); 293 294 for (unsigned i = 0; i < BitWidth; ++i) { 295 if (SFBits && bitFromBits(*SFBits, i) == BIT_TRUE) 296 Insn.push_back(BIT_UNSET); 297 else 298 Insn.push_back(bitFromBits(Bits, i)); 299 } 300 } 301 302 // Returns the record name. 303 const std::string &nameWithID(unsigned Opcode) const { 304 return AllInstructions[Opcode]->TheDef->getName(); 305 } 306 307 // Populates the field of the insn given the start position and the number of 308 // consecutive bits to scan for. 309 // 310 // Returns false if there exists any uninitialized bit value in the range. 311 // Returns true, otherwise. 312 bool fieldFromInsn(uint64_t &Field, insn_t &Insn, unsigned StartBit, 313 unsigned NumBits) const; 314 315 /// dumpFilterArray - dumpFilterArray prints out debugging info for the given 316 /// filter array as a series of chars. 317 void dumpFilterArray(raw_ostream &o, 318 const std::vector<bit_value_t> & filter) const; 319 320 /// dumpStack - dumpStack traverses the filter chooser chain and calls 321 /// dumpFilterArray on each filter chooser up to the top level one. 322 void dumpStack(raw_ostream &o, const char *prefix) const; 323 324 Filter &bestFilter() { 325 assert(BestIndex != -1 && "BestIndex not set"); 326 return Filters[BestIndex]; 327 } 328 329 // Called from Filter::recurse() when singleton exists. For debug purpose. 330 void SingletonExists(unsigned Opc) const; 331 332 bool PositionFiltered(unsigned i) const { 333 return ValueSet(FilterBitValues[i]); 334 } 335 336 // Calculates the island(s) needed to decode the instruction. 337 // This returns a lit of undecoded bits of an instructions, for example, 338 // Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be 339 // decoded bits in order to verify that the instruction matches the Opcode. 340 unsigned getIslands(std::vector<unsigned> &StartBits, 341 std::vector<unsigned> &EndBits, 342 std::vector<uint64_t> &FieldVals, 343 const insn_t &Insn) const; 344 345 // Emits code to check the Predicates member of an instruction are true. 346 // Returns true if predicate matches were emitted, false otherwise. 347 bool emitPredicateMatch(raw_ostream &o, unsigned &Indentation, 348 unsigned Opc) const; 349 350 void emitSoftFailCheck(raw_ostream &o, unsigned Indentation, 351 unsigned Opc) const; 352 353 // Emits code to decode the singleton. Return true if we have matched all the 354 // well-known bits. 355 bool emitSingletonDecoder(raw_ostream &o, unsigned &Indentation, 356 unsigned Opc) const; 357 358 // Emits code to decode the singleton, and then to decode the rest. 359 void emitSingletonDecoder(raw_ostream &o, unsigned &Indentation, 360 const Filter &Best) const; 361 362 void emitBinaryParser(raw_ostream &o , unsigned &Indentation, 363 const OperandInfo &OpInfo) const; 364 365 // Assign a single filter and run with it. 366 void runSingleFilter(unsigned startBit, unsigned numBit, bool mixed); 367 368 // reportRegion is a helper function for filterProcessor to mark a region as 369 // eligible for use as a filter region. 370 void reportRegion(bitAttr_t RA, unsigned StartBit, unsigned BitIndex, 371 bool AllowMixed); 372 373 // FilterProcessor scans the well-known encoding bits of the instructions and 374 // builds up a list of candidate filters. It chooses the best filter and 375 // recursively descends down the decoding tree. 376 bool filterProcessor(bool AllowMixed, bool Greedy = true); 377 378 // Decides on the best configuration of filter(s) to use in order to decode 379 // the instructions. A conflict of instructions may occur, in which case we 380 // dump the conflict set to the standard error. 381 void doFilter(); 382 383 // Emits code to decode our share of instructions. Returns true if the 384 // emitted code causes a return, which occurs if we know how to decode 385 // the instruction at this level or the instruction is not decodeable. 386 bool emit(raw_ostream &o, unsigned &Indentation) const; 387 }; 388 389 /////////////////////////// 390 // // 391 // Filter Implementation // 392 // // 393 /////////////////////////// 394 395 Filter::Filter(const Filter &f) 396 : Owner(f.Owner), StartBit(f.StartBit), NumBits(f.NumBits), Mixed(f.Mixed), 397 FilteredInstructions(f.FilteredInstructions), 398 VariableInstructions(f.VariableInstructions), 399 FilterChooserMap(f.FilterChooserMap), NumFiltered(f.NumFiltered), 400 LastOpcFiltered(f.LastOpcFiltered) { 401 } 402 403 Filter::Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, 404 bool mixed) 405 : Owner(&owner), StartBit(startBit), NumBits(numBits), Mixed(mixed) { 406 assert(StartBit + NumBits - 1 < Owner->BitWidth); 407 408 NumFiltered = 0; 409 LastOpcFiltered = 0; 410 411 for (unsigned i = 0, e = Owner->Opcodes.size(); i != e; ++i) { 412 insn_t Insn; 413 414 // Populates the insn given the uid. 415 Owner->insnWithID(Insn, Owner->Opcodes[i]); 416 417 uint64_t Field; 418 // Scans the segment for possibly well-specified encoding bits. 419 bool ok = Owner->fieldFromInsn(Field, Insn, StartBit, NumBits); 420 421 if (ok) { 422 // The encoding bits are well-known. Lets add the uid of the 423 // instruction into the bucket keyed off the constant field value. 424 LastOpcFiltered = Owner->Opcodes[i]; 425 FilteredInstructions[Field].push_back(LastOpcFiltered); 426 ++NumFiltered; 427 } else { 428 // Some of the encoding bit(s) are unspecified. This contributes to 429 // one additional member of "Variable" instructions. 430 VariableInstructions.push_back(Owner->Opcodes[i]); 431 } 432 } 433 434 assert((FilteredInstructions.size() + VariableInstructions.size() > 0) 435 && "Filter returns no instruction categories"); 436 } 437 438 Filter::~Filter() { 439 std::map<unsigned, const FilterChooser*>::iterator filterIterator; 440 for (filterIterator = FilterChooserMap.begin(); 441 filterIterator != FilterChooserMap.end(); 442 filterIterator++) { 443 delete filterIterator->second; 444 } 445 } 446 447 // Divides the decoding task into sub tasks and delegates them to the 448 // inferior FilterChooser's. 449 // 450 // A special case arises when there's only one entry in the filtered 451 // instructions. In order to unambiguously decode the singleton, we need to 452 // match the remaining undecoded encoding bits against the singleton. 453 void Filter::recurse() { 454 std::map<uint64_t, std::vector<unsigned> >::const_iterator mapIterator; 455 456 // Starts by inheriting our parent filter chooser's filter bit values. 457 std::vector<bit_value_t> BitValueArray(Owner->FilterBitValues); 458 459 unsigned bitIndex; 460 461 if (VariableInstructions.size()) { 462 // Conservatively marks each segment position as BIT_UNSET. 463 for (bitIndex = 0; bitIndex < NumBits; bitIndex++) 464 BitValueArray[StartBit + bitIndex] = BIT_UNSET; 465 466 // Delegates to an inferior filter chooser for further processing on this 467 // group of instructions whose segment values are variable. 468 FilterChooserMap.insert(std::pair<unsigned, const FilterChooser*>( 469 (unsigned)-1, 470 new FilterChooser(Owner->AllInstructions, 471 VariableInstructions, 472 Owner->Operands, 473 BitValueArray, 474 *Owner) 475 )); 476 } 477 478 // No need to recurse for a singleton filtered instruction. 479 // See also Filter::emit(). 480 if (getNumFiltered() == 1) { 481 //Owner->SingletonExists(LastOpcFiltered); 482 assert(FilterChooserMap.size() == 1); 483 return; 484 } 485 486 // Otherwise, create sub choosers. 487 for (mapIterator = FilteredInstructions.begin(); 488 mapIterator != FilteredInstructions.end(); 489 mapIterator++) { 490 491 // Marks all the segment positions with either BIT_TRUE or BIT_FALSE. 492 for (bitIndex = 0; bitIndex < NumBits; bitIndex++) { 493 if (mapIterator->first & (1ULL << bitIndex)) 494 BitValueArray[StartBit + bitIndex] = BIT_TRUE; 495 else 496 BitValueArray[StartBit + bitIndex] = BIT_FALSE; 497 } 498 499 // Delegates to an inferior filter chooser for further processing on this 500 // category of instructions. 501 FilterChooserMap.insert(std::pair<unsigned, const FilterChooser*>( 502 mapIterator->first, 503 new FilterChooser(Owner->AllInstructions, 504 mapIterator->second, 505 Owner->Operands, 506 BitValueArray, 507 *Owner) 508 )); 509 } 510 } 511 512 // Emit code to decode instructions given a segment or segments of bits. 513 void Filter::emit(raw_ostream &o, unsigned &Indentation) const { 514 o.indent(Indentation) << "// Check Inst{"; 515 516 if (NumBits > 1) 517 o << (StartBit + NumBits - 1) << '-'; 518 519 o << StartBit << "} ...\n"; 520 521 o.indent(Indentation) << "switch (fieldFromInstruction" << Owner->BitWidth 522 << "(insn, " << StartBit << ", " 523 << NumBits << ")) {\n"; 524 525 std::map<unsigned, const FilterChooser*>::const_iterator filterIterator; 526 527 bool DefaultCase = false; 528 for (filterIterator = FilterChooserMap.begin(); 529 filterIterator != FilterChooserMap.end(); 530 filterIterator++) { 531 532 // Field value -1 implies a non-empty set of variable instructions. 533 // See also recurse(). 534 if (filterIterator->first == (unsigned)-1) { 535 DefaultCase = true; 536 537 o.indent(Indentation) << "default:\n"; 538 o.indent(Indentation) << " break; // fallthrough\n"; 539 540 // Closing curly brace for the switch statement. 541 // This is unconventional because we want the default processing to be 542 // performed for the fallthrough cases as well, i.e., when the "cases" 543 // did not prove a decoded instruction. 544 o.indent(Indentation) << "}\n"; 545 546 } else 547 o.indent(Indentation) << "case " << filterIterator->first << ":\n"; 548 549 // We arrive at a category of instructions with the same segment value. 550 // Now delegate to the sub filter chooser for further decodings. 551 // The case may fallthrough, which happens if the remaining well-known 552 // encoding bits do not match exactly. 553 if (!DefaultCase) { ++Indentation; ++Indentation; } 554 555 filterIterator->second->emit(o, Indentation); 556 // For top level default case, there's no need for a break statement. 557 if (Owner->isTopLevel() && DefaultCase) 558 break; 559 560 o.indent(Indentation) << "break;\n"; 561 562 if (!DefaultCase) { --Indentation; --Indentation; } 563 } 564 565 // If there is no default case, we still need to supply a closing brace. 566 if (!DefaultCase) { 567 // Closing curly brace for the switch statement. 568 o.indent(Indentation) << "}\n"; 569 } 570 } 571 572 // Returns the number of fanout produced by the filter. More fanout implies 573 // the filter distinguishes more categories of instructions. 574 unsigned Filter::usefulness() const { 575 if (VariableInstructions.size()) 576 return FilteredInstructions.size(); 577 else 578 return FilteredInstructions.size() + 1; 579 } 580 581 ////////////////////////////////// 582 // // 583 // Filterchooser Implementation // 584 // // 585 ////////////////////////////////// 586 587 // Emit the top level typedef and decodeInstruction() function. 588 void FilterChooser::emitTop(raw_ostream &o, unsigned Indentation, 589 const std::string &Namespace) const { 590 o.indent(Indentation) << 591 "static MCDisassembler::DecodeStatus decode" << Namespace << "Instruction" 592 << BitWidth << "(MCInst &MI, uint" << BitWidth 593 << "_t insn, uint64_t Address, " 594 << "const void *Decoder, const MCSubtargetInfo &STI) {\n"; 595 o.indent(Indentation) << " unsigned tmp = 0;\n"; 596 o.indent(Indentation) << " (void)tmp;\n"; 597 o.indent(Indentation) << Emitter->Locals << "\n"; 598 o.indent(Indentation) << " uint64_t Bits = STI.getFeatureBits();\n"; 599 o.indent(Indentation) << " (void)Bits;\n"; 600 601 ++Indentation; ++Indentation; 602 // Emits code to decode the instructions. 603 emit(o, Indentation); 604 605 o << '\n'; 606 o.indent(Indentation) << "return " << Emitter->ReturnFail << ";\n"; 607 --Indentation; --Indentation; 608 609 o.indent(Indentation) << "}\n"; 610 611 o << '\n'; 612 } 613 614 // Populates the field of the insn given the start position and the number of 615 // consecutive bits to scan for. 616 // 617 // Returns false if and on the first uninitialized bit value encountered. 618 // Returns true, otherwise. 619 bool FilterChooser::fieldFromInsn(uint64_t &Field, insn_t &Insn, 620 unsigned StartBit, unsigned NumBits) const { 621 Field = 0; 622 623 for (unsigned i = 0; i < NumBits; ++i) { 624 if (Insn[StartBit + i] == BIT_UNSET) 625 return false; 626 627 if (Insn[StartBit + i] == BIT_TRUE) 628 Field = Field | (1ULL << i); 629 } 630 631 return true; 632 } 633 634 /// dumpFilterArray - dumpFilterArray prints out debugging info for the given 635 /// filter array as a series of chars. 636 void FilterChooser::dumpFilterArray(raw_ostream &o, 637 const std::vector<bit_value_t> &filter) const { 638 unsigned bitIndex; 639 640 for (bitIndex = BitWidth; bitIndex > 0; bitIndex--) { 641 switch (filter[bitIndex - 1]) { 642 case BIT_UNFILTERED: 643 o << "."; 644 break; 645 case BIT_UNSET: 646 o << "_"; 647 break; 648 case BIT_TRUE: 649 o << "1"; 650 break; 651 case BIT_FALSE: 652 o << "0"; 653 break; 654 } 655 } 656 } 657 658 /// dumpStack - dumpStack traverses the filter chooser chain and calls 659 /// dumpFilterArray on each filter chooser up to the top level one. 660 void FilterChooser::dumpStack(raw_ostream &o, const char *prefix) const { 661 const FilterChooser *current = this; 662 663 while (current) { 664 o << prefix; 665 dumpFilterArray(o, current->FilterBitValues); 666 o << '\n'; 667 current = current->Parent; 668 } 669 } 670 671 // Called from Filter::recurse() when singleton exists. For debug purpose. 672 void FilterChooser::SingletonExists(unsigned Opc) const { 673 insn_t Insn0; 674 insnWithID(Insn0, Opc); 675 676 errs() << "Singleton exists: " << nameWithID(Opc) 677 << " with its decoding dominating "; 678 for (unsigned i = 0; i < Opcodes.size(); ++i) { 679 if (Opcodes[i] == Opc) continue; 680 errs() << nameWithID(Opcodes[i]) << ' '; 681 } 682 errs() << '\n'; 683 684 dumpStack(errs(), "\t\t"); 685 for (unsigned i = 0; i < Opcodes.size(); ++i) { 686 const std::string &Name = nameWithID(Opcodes[i]); 687 688 errs() << '\t' << Name << " "; 689 dumpBits(errs(), 690 getBitsField(*AllInstructions[Opcodes[i]]->TheDef, "Inst")); 691 errs() << '\n'; 692 } 693 } 694 695 // Calculates the island(s) needed to decode the instruction. 696 // This returns a list of undecoded bits of an instructions, for example, 697 // Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be 698 // decoded bits in order to verify that the instruction matches the Opcode. 699 unsigned FilterChooser::getIslands(std::vector<unsigned> &StartBits, 700 std::vector<unsigned> &EndBits, 701 std::vector<uint64_t> &FieldVals, 702 const insn_t &Insn) const { 703 unsigned Num, BitNo; 704 Num = BitNo = 0; 705 706 uint64_t FieldVal = 0; 707 708 // 0: Init 709 // 1: Water (the bit value does not affect decoding) 710 // 2: Island (well-known bit value needed for decoding) 711 int State = 0; 712 int Val = -1; 713 714 for (unsigned i = 0; i < BitWidth; ++i) { 715 Val = Value(Insn[i]); 716 bool Filtered = PositionFiltered(i); 717 switch (State) { 718 default: llvm_unreachable("Unreachable code!"); 719 case 0: 720 case 1: 721 if (Filtered || Val == -1) 722 State = 1; // Still in Water 723 else { 724 State = 2; // Into the Island 725 BitNo = 0; 726 StartBits.push_back(i); 727 FieldVal = Val; 728 } 729 break; 730 case 2: 731 if (Filtered || Val == -1) { 732 State = 1; // Into the Water 733 EndBits.push_back(i - 1); 734 FieldVals.push_back(FieldVal); 735 ++Num; 736 } else { 737 State = 2; // Still in Island 738 ++BitNo; 739 FieldVal = FieldVal | Val << BitNo; 740 } 741 break; 742 } 743 } 744 // If we are still in Island after the loop, do some housekeeping. 745 if (State == 2) { 746 EndBits.push_back(BitWidth - 1); 747 FieldVals.push_back(FieldVal); 748 ++Num; 749 } 750 751 assert(StartBits.size() == Num && EndBits.size() == Num && 752 FieldVals.size() == Num); 753 return Num; 754 } 755 756 void FilterChooser::emitBinaryParser(raw_ostream &o, unsigned &Indentation, 757 const OperandInfo &OpInfo) const { 758 const std::string &Decoder = OpInfo.Decoder; 759 760 if (OpInfo.numFields() == 1) { 761 OperandInfo::const_iterator OI = OpInfo.begin(); 762 o.indent(Indentation) << " tmp = fieldFromInstruction" << BitWidth 763 << "(insn, " << OI->Base << ", " << OI->Width 764 << ");\n"; 765 } else { 766 o.indent(Indentation) << " tmp = 0;\n"; 767 for (OperandInfo::const_iterator OI = OpInfo.begin(), OE = OpInfo.end(); 768 OI != OE; ++OI) { 769 o.indent(Indentation) << " tmp |= (fieldFromInstruction" << BitWidth 770 << "(insn, " << OI->Base << ", " << OI->Width 771 << ") << " << OI->Offset << ");\n"; 772 } 773 } 774 775 if (Decoder != "") 776 o.indent(Indentation) << " " << Emitter->GuardPrefix << Decoder 777 << "(MI, tmp, Address, Decoder)" 778 << Emitter->GuardPostfix << "\n"; 779 else 780 o.indent(Indentation) << " MI.addOperand(MCOperand::CreateImm(tmp));\n"; 781 782 } 783 784 static void emitSinglePredicateMatch(raw_ostream &o, StringRef str, 785 const std::string &PredicateNamespace) { 786 if (str[0] == '!') 787 o << "!(Bits & " << PredicateNamespace << "::" 788 << str.slice(1,str.size()) << ")"; 789 else 790 o << "(Bits & " << PredicateNamespace << "::" << str << ")"; 791 } 792 793 bool FilterChooser::emitPredicateMatch(raw_ostream &o, unsigned &Indentation, 794 unsigned Opc) const { 795 ListInit *Predicates = 796 AllInstructions[Opc]->TheDef->getValueAsListInit("Predicates"); 797 for (unsigned i = 0; i < Predicates->getSize(); ++i) { 798 Record *Pred = Predicates->getElementAsRecord(i); 799 if (!Pred->getValue("AssemblerMatcherPredicate")) 800 continue; 801 802 std::string P = Pred->getValueAsString("AssemblerCondString"); 803 804 if (!P.length()) 805 continue; 806 807 if (i != 0) 808 o << " && "; 809 810 StringRef SR(P); 811 std::pair<StringRef, StringRef> pairs = SR.split(','); 812 while (pairs.second.size()) { 813 emitSinglePredicateMatch(o, pairs.first, Emitter->PredicateNamespace); 814 o << " && "; 815 pairs = pairs.second.split(','); 816 } 817 emitSinglePredicateMatch(o, pairs.first, Emitter->PredicateNamespace); 818 } 819 return Predicates->getSize() > 0; 820 } 821 822 void FilterChooser::emitSoftFailCheck(raw_ostream &o, unsigned Indentation, 823 unsigned Opc) const { 824 BitsInit *SFBits = 825 AllInstructions[Opc]->TheDef->getValueAsBitsInit("SoftFail"); 826 if (!SFBits) return; 827 BitsInit *InstBits = AllInstructions[Opc]->TheDef->getValueAsBitsInit("Inst"); 828 829 APInt PositiveMask(BitWidth, 0ULL); 830 APInt NegativeMask(BitWidth, 0ULL); 831 for (unsigned i = 0; i < BitWidth; ++i) { 832 bit_value_t B = bitFromBits(*SFBits, i); 833 bit_value_t IB = bitFromBits(*InstBits, i); 834 835 if (B != BIT_TRUE) continue; 836 837 switch (IB) { 838 case BIT_FALSE: 839 // The bit is meant to be false, so emit a check to see if it is true. 840 PositiveMask.setBit(i); 841 break; 842 case BIT_TRUE: 843 // The bit is meant to be true, so emit a check to see if it is false. 844 NegativeMask.setBit(i); 845 break; 846 default: 847 // The bit is not set; this must be an error! 848 StringRef Name = AllInstructions[Opc]->TheDef->getName(); 849 errs() << "SoftFail Conflict: bit SoftFail{" << i << "} in " 850 << Name 851 << " is set but Inst{" << i <<"} is unset!\n" 852 << " - You can only mark a bit as SoftFail if it is fully defined" 853 << " (1/0 - not '?') in Inst\n"; 854 o << "#error SoftFail Conflict, " << Name << "::SoftFail{" << i 855 << "} set but Inst{" << i << "} undefined!\n"; 856 } 857 } 858 859 bool NeedPositiveMask = PositiveMask.getBoolValue(); 860 bool NeedNegativeMask = NegativeMask.getBoolValue(); 861 862 if (!NeedPositiveMask && !NeedNegativeMask) 863 return; 864 865 std::string PositiveMaskStr = PositiveMask.toString(16, /*signed=*/false); 866 std::string NegativeMaskStr = NegativeMask.toString(16, /*signed=*/false); 867 StringRef BitExt = ""; 868 if (BitWidth > 32) 869 BitExt = "ULL"; 870 871 o.indent(Indentation) << "if ("; 872 if (NeedPositiveMask) 873 o << "insn & 0x" << PositiveMaskStr << BitExt; 874 if (NeedPositiveMask && NeedNegativeMask) 875 o << " || "; 876 if (NeedNegativeMask) 877 o << "~insn & 0x" << NegativeMaskStr << BitExt; 878 o << ")\n"; 879 o.indent(Indentation+2) << "S = MCDisassembler::SoftFail;\n"; 880 } 881 882 // Emits code to decode the singleton. Return true if we have matched all the 883 // well-known bits. 884 bool FilterChooser::emitSingletonDecoder(raw_ostream &o, unsigned &Indentation, 885 unsigned Opc) const { 886 std::vector<unsigned> StartBits; 887 std::vector<unsigned> EndBits; 888 std::vector<uint64_t> FieldVals; 889 insn_t Insn; 890 insnWithID(Insn, Opc); 891 892 // Look for islands of undecoded bits of the singleton. 893 getIslands(StartBits, EndBits, FieldVals, Insn); 894 895 unsigned Size = StartBits.size(); 896 unsigned I, NumBits; 897 898 // If we have matched all the well-known bits, just issue a return. 899 if (Size == 0) { 900 o.indent(Indentation) << "if ("; 901 if (!emitPredicateMatch(o, Indentation, Opc)) 902 o << "1"; 903 o << ") {\n"; 904 emitSoftFailCheck(o, Indentation+2, Opc); 905 o.indent(Indentation) << " MI.setOpcode(" << Opc << ");\n"; 906 std::map<unsigned, std::vector<OperandInfo> >::const_iterator OpIter = 907 Operands.find(Opc); 908 const std::vector<OperandInfo>& InsnOperands = OpIter->second; 909 for (std::vector<OperandInfo>::const_iterator 910 I = InsnOperands.begin(), E = InsnOperands.end(); I != E; ++I) { 911 // If a custom instruction decoder was specified, use that. 912 if (I->numFields() == 0 && I->Decoder.size()) { 913 o.indent(Indentation) << " " << Emitter->GuardPrefix << I->Decoder 914 << "(MI, insn, Address, Decoder)" 915 << Emitter->GuardPostfix << "\n"; 916 break; 917 } 918 919 emitBinaryParser(o, Indentation, *I); 920 } 921 922 o.indent(Indentation) << " return " << Emitter->ReturnOK << "; // " 923 << nameWithID(Opc) << '\n'; 924 o.indent(Indentation) << "}\n"; // Closing predicate block. 925 return true; 926 } 927 928 // Otherwise, there are more decodings to be done! 929 930 // Emit code to match the island(s) for the singleton. 931 o.indent(Indentation) << "// Check "; 932 933 for (I = Size; I != 0; --I) { 934 o << "Inst{" << EndBits[I-1] << '-' << StartBits[I-1] << "} "; 935 if (I > 1) 936 o << " && "; 937 else 938 o << "for singleton decoding...\n"; 939 } 940 941 o.indent(Indentation) << "if ("; 942 if (emitPredicateMatch(o, Indentation, Opc)) { 943 o << " &&\n"; 944 o.indent(Indentation+4); 945 } 946 947 for (I = Size; I != 0; --I) { 948 NumBits = EndBits[I-1] - StartBits[I-1] + 1; 949 o << "fieldFromInstruction" << BitWidth << "(insn, " 950 << StartBits[I-1] << ", " << NumBits 951 << ") == " << FieldVals[I-1]; 952 if (I > 1) 953 o << " && "; 954 else 955 o << ") {\n"; 956 } 957 emitSoftFailCheck(o, Indentation+2, Opc); 958 o.indent(Indentation) << " MI.setOpcode(" << Opc << ");\n"; 959 std::map<unsigned, std::vector<OperandInfo> >::const_iterator OpIter = 960 Operands.find(Opc); 961 const std::vector<OperandInfo>& InsnOperands = OpIter->second; 962 for (std::vector<OperandInfo>::const_iterator 963 I = InsnOperands.begin(), E = InsnOperands.end(); I != E; ++I) { 964 // If a custom instruction decoder was specified, use that. 965 if (I->numFields() == 0 && I->Decoder.size()) { 966 o.indent(Indentation) << " " << Emitter->GuardPrefix << I->Decoder 967 << "(MI, insn, Address, Decoder)" 968 << Emitter->GuardPostfix << "\n"; 969 break; 970 } 971 972 emitBinaryParser(o, Indentation, *I); 973 } 974 o.indent(Indentation) << " return " << Emitter->ReturnOK << "; // " 975 << nameWithID(Opc) << '\n'; 976 o.indent(Indentation) << "}\n"; 977 978 return false; 979 } 980 981 // Emits code to decode the singleton, and then to decode the rest. 982 void FilterChooser::emitSingletonDecoder(raw_ostream &o, unsigned &Indentation, 983 const Filter &Best) const { 984 985 unsigned Opc = Best.getSingletonOpc(); 986 987 emitSingletonDecoder(o, Indentation, Opc); 988 989 // Emit code for the rest. 990 o.indent(Indentation) << "else\n"; 991 992 Indentation += 2; 993 Best.getVariableFC().emit(o, Indentation); 994 Indentation -= 2; 995 } 996 997 // Assign a single filter and run with it. Top level API client can initialize 998 // with a single filter to start the filtering process. 999 void FilterChooser::runSingleFilter(unsigned startBit, unsigned numBit, 1000 bool mixed) { 1001 Filters.clear(); 1002 Filter F(*this, startBit, numBit, true); 1003 Filters.push_back(F); 1004 BestIndex = 0; // Sole Filter instance to choose from. 1005 bestFilter().recurse(); 1006 } 1007 1008 // reportRegion is a helper function for filterProcessor to mark a region as 1009 // eligible for use as a filter region. 1010 void FilterChooser::reportRegion(bitAttr_t RA, unsigned StartBit, 1011 unsigned BitIndex, bool AllowMixed) { 1012 if (RA == ATTR_MIXED && AllowMixed) 1013 Filters.push_back(Filter(*this, StartBit, BitIndex - StartBit, true)); 1014 else if (RA == ATTR_ALL_SET && !AllowMixed) 1015 Filters.push_back(Filter(*this, StartBit, BitIndex - StartBit, false)); 1016 } 1017 1018 // FilterProcessor scans the well-known encoding bits of the instructions and 1019 // builds up a list of candidate filters. It chooses the best filter and 1020 // recursively descends down the decoding tree. 1021 bool FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { 1022 Filters.clear(); 1023 BestIndex = -1; 1024 unsigned numInstructions = Opcodes.size(); 1025 1026 assert(numInstructions && "Filter created with no instructions"); 1027 1028 // No further filtering is necessary. 1029 if (numInstructions == 1) 1030 return true; 1031 1032 // Heuristics. See also doFilter()'s "Heuristics" comment when num of 1033 // instructions is 3. 1034 if (AllowMixed && !Greedy) { 1035 assert(numInstructions == 3); 1036 1037 for (unsigned i = 0; i < Opcodes.size(); ++i) { 1038 std::vector<unsigned> StartBits; 1039 std::vector<unsigned> EndBits; 1040 std::vector<uint64_t> FieldVals; 1041 insn_t Insn; 1042 1043 insnWithID(Insn, Opcodes[i]); 1044 1045 // Look for islands of undecoded bits of any instruction. 1046 if (getIslands(StartBits, EndBits, FieldVals, Insn) > 0) { 1047 // Found an instruction with island(s). Now just assign a filter. 1048 runSingleFilter(StartBits[0], EndBits[0] - StartBits[0] + 1, true); 1049 return true; 1050 } 1051 } 1052 } 1053 1054 unsigned BitIndex, InsnIndex; 1055 1056 // We maintain BIT_WIDTH copies of the bitAttrs automaton. 1057 // The automaton consumes the corresponding bit from each 1058 // instruction. 1059 // 1060 // Input symbols: 0, 1, and _ (unset). 1061 // States: NONE, FILTERED, ALL_SET, ALL_UNSET, and MIXED. 1062 // Initial state: NONE. 1063 // 1064 // (NONE) ------- [01] -> (ALL_SET) 1065 // (NONE) ------- _ ----> (ALL_UNSET) 1066 // (ALL_SET) ---- [01] -> (ALL_SET) 1067 // (ALL_SET) ---- _ ----> (MIXED) 1068 // (ALL_UNSET) -- [01] -> (MIXED) 1069 // (ALL_UNSET) -- _ ----> (ALL_UNSET) 1070 // (MIXED) ------ . ----> (MIXED) 1071 // (FILTERED)---- . ----> (FILTERED) 1072 1073 std::vector<bitAttr_t> bitAttrs; 1074 1075 // FILTERED bit positions provide no entropy and are not worthy of pursuing. 1076 // Filter::recurse() set either BIT_TRUE or BIT_FALSE for each position. 1077 for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) 1078 if (FilterBitValues[BitIndex] == BIT_TRUE || 1079 FilterBitValues[BitIndex] == BIT_FALSE) 1080 bitAttrs.push_back(ATTR_FILTERED); 1081 else 1082 bitAttrs.push_back(ATTR_NONE); 1083 1084 for (InsnIndex = 0; InsnIndex < numInstructions; ++InsnIndex) { 1085 insn_t insn; 1086 1087 insnWithID(insn, Opcodes[InsnIndex]); 1088 1089 for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { 1090 switch (bitAttrs[BitIndex]) { 1091 case ATTR_NONE: 1092 if (insn[BitIndex] == BIT_UNSET) 1093 bitAttrs[BitIndex] = ATTR_ALL_UNSET; 1094 else 1095 bitAttrs[BitIndex] = ATTR_ALL_SET; 1096 break; 1097 case ATTR_ALL_SET: 1098 if (insn[BitIndex] == BIT_UNSET) 1099 bitAttrs[BitIndex] = ATTR_MIXED; 1100 break; 1101 case ATTR_ALL_UNSET: 1102 if (insn[BitIndex] != BIT_UNSET) 1103 bitAttrs[BitIndex] = ATTR_MIXED; 1104 break; 1105 case ATTR_MIXED: 1106 case ATTR_FILTERED: 1107 break; 1108 } 1109 } 1110 } 1111 1112 // The regionAttr automaton consumes the bitAttrs automatons' state, 1113 // lowest-to-highest. 1114 // 1115 // Input symbols: F(iltered), (all_)S(et), (all_)U(nset), M(ixed) 1116 // States: NONE, ALL_SET, MIXED 1117 // Initial state: NONE 1118 // 1119 // (NONE) ----- F --> (NONE) 1120 // (NONE) ----- S --> (ALL_SET) ; and set region start 1121 // (NONE) ----- U --> (NONE) 1122 // (NONE) ----- M --> (MIXED) ; and set region start 1123 // (ALL_SET) -- F --> (NONE) ; and report an ALL_SET region 1124 // (ALL_SET) -- S --> (ALL_SET) 1125 // (ALL_SET) -- U --> (NONE) ; and report an ALL_SET region 1126 // (ALL_SET) -- M --> (MIXED) ; and report an ALL_SET region 1127 // (MIXED) ---- F --> (NONE) ; and report a MIXED region 1128 // (MIXED) ---- S --> (ALL_SET) ; and report a MIXED region 1129 // (MIXED) ---- U --> (NONE) ; and report a MIXED region 1130 // (MIXED) ---- M --> (MIXED) 1131 1132 bitAttr_t RA = ATTR_NONE; 1133 unsigned StartBit = 0; 1134 1135 for (BitIndex = 0; BitIndex < BitWidth; BitIndex++) { 1136 bitAttr_t bitAttr = bitAttrs[BitIndex]; 1137 1138 assert(bitAttr != ATTR_NONE && "Bit without attributes"); 1139 1140 switch (RA) { 1141 case ATTR_NONE: 1142 switch (bitAttr) { 1143 case ATTR_FILTERED: 1144 break; 1145 case ATTR_ALL_SET: 1146 StartBit = BitIndex; 1147 RA = ATTR_ALL_SET; 1148 break; 1149 case ATTR_ALL_UNSET: 1150 break; 1151 case ATTR_MIXED: 1152 StartBit = BitIndex; 1153 RA = ATTR_MIXED; 1154 break; 1155 default: 1156 llvm_unreachable("Unexpected bitAttr!"); 1157 } 1158 break; 1159 case ATTR_ALL_SET: 1160 switch (bitAttr) { 1161 case ATTR_FILTERED: 1162 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1163 RA = ATTR_NONE; 1164 break; 1165 case ATTR_ALL_SET: 1166 break; 1167 case ATTR_ALL_UNSET: 1168 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1169 RA = ATTR_NONE; 1170 break; 1171 case ATTR_MIXED: 1172 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1173 StartBit = BitIndex; 1174 RA = ATTR_MIXED; 1175 break; 1176 default: 1177 llvm_unreachable("Unexpected bitAttr!"); 1178 } 1179 break; 1180 case ATTR_MIXED: 1181 switch (bitAttr) { 1182 case ATTR_FILTERED: 1183 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1184 StartBit = BitIndex; 1185 RA = ATTR_NONE; 1186 break; 1187 case ATTR_ALL_SET: 1188 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1189 StartBit = BitIndex; 1190 RA = ATTR_ALL_SET; 1191 break; 1192 case ATTR_ALL_UNSET: 1193 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1194 RA = ATTR_NONE; 1195 break; 1196 case ATTR_MIXED: 1197 break; 1198 default: 1199 llvm_unreachable("Unexpected bitAttr!"); 1200 } 1201 break; 1202 case ATTR_ALL_UNSET: 1203 llvm_unreachable("regionAttr state machine has no ATTR_UNSET state"); 1204 case ATTR_FILTERED: 1205 llvm_unreachable("regionAttr state machine has no ATTR_FILTERED state"); 1206 } 1207 } 1208 1209 // At the end, if we're still in ALL_SET or MIXED states, report a region 1210 switch (RA) { 1211 case ATTR_NONE: 1212 break; 1213 case ATTR_FILTERED: 1214 break; 1215 case ATTR_ALL_SET: 1216 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1217 break; 1218 case ATTR_ALL_UNSET: 1219 break; 1220 case ATTR_MIXED: 1221 reportRegion(RA, StartBit, BitIndex, AllowMixed); 1222 break; 1223 } 1224 1225 // We have finished with the filter processings. Now it's time to choose 1226 // the best performing filter. 1227 BestIndex = 0; 1228 bool AllUseless = true; 1229 unsigned BestScore = 0; 1230 1231 for (unsigned i = 0, e = Filters.size(); i != e; ++i) { 1232 unsigned Usefulness = Filters[i].usefulness(); 1233 1234 if (Usefulness) 1235 AllUseless = false; 1236 1237 if (Usefulness > BestScore) { 1238 BestIndex = i; 1239 BestScore = Usefulness; 1240 } 1241 } 1242 1243 if (!AllUseless) 1244 bestFilter().recurse(); 1245 1246 return !AllUseless; 1247 } // end of FilterChooser::filterProcessor(bool) 1248 1249 // Decides on the best configuration of filter(s) to use in order to decode 1250 // the instructions. A conflict of instructions may occur, in which case we 1251 // dump the conflict set to the standard error. 1252 void FilterChooser::doFilter() { 1253 unsigned Num = Opcodes.size(); 1254 assert(Num && "FilterChooser created with no instructions"); 1255 1256 // Try regions of consecutive known bit values first. 1257 if (filterProcessor(false)) 1258 return; 1259 1260 // Then regions of mixed bits (both known and unitialized bit values allowed). 1261 if (filterProcessor(true)) 1262 return; 1263 1264 // Heuristics to cope with conflict set {t2CMPrs, t2SUBSrr, t2SUBSrs} where 1265 // no single instruction for the maximum ATTR_MIXED region Inst{14-4} has a 1266 // well-known encoding pattern. In such case, we backtrack and scan for the 1267 // the very first consecutive ATTR_ALL_SET region and assign a filter to it. 1268 if (Num == 3 && filterProcessor(true, false)) 1269 return; 1270 1271 // If we come to here, the instruction decoding has failed. 1272 // Set the BestIndex to -1 to indicate so. 1273 BestIndex = -1; 1274 } 1275 1276 // Emits code to decode our share of instructions. Returns true if the 1277 // emitted code causes a return, which occurs if we know how to decode 1278 // the instruction at this level or the instruction is not decodeable. 1279 bool FilterChooser::emit(raw_ostream &o, unsigned &Indentation) const { 1280 if (Opcodes.size() == 1) 1281 // There is only one instruction in the set, which is great! 1282 // Call emitSingletonDecoder() to see whether there are any remaining 1283 // encodings bits. 1284 return emitSingletonDecoder(o, Indentation, Opcodes[0]); 1285 1286 // Choose the best filter to do the decodings! 1287 if (BestIndex != -1) { 1288 const Filter &Best = Filters[BestIndex]; 1289 if (Best.getNumFiltered() == 1) 1290 emitSingletonDecoder(o, Indentation, Best); 1291 else 1292 Best.emit(o, Indentation); 1293 return false; 1294 } 1295 1296 // We don't know how to decode these instructions! Return 0 and dump the 1297 // conflict set! 1298 o.indent(Indentation) << "return 0;" << " // Conflict set: "; 1299 for (int i = 0, N = Opcodes.size(); i < N; ++i) { 1300 o << nameWithID(Opcodes[i]); 1301 if (i < (N - 1)) 1302 o << ", "; 1303 else 1304 o << '\n'; 1305 } 1306 1307 // Print out useful conflict information for postmortem analysis. 1308 errs() << "Decoding Conflict:\n"; 1309 1310 dumpStack(errs(), "\t\t"); 1311 1312 for (unsigned i = 0; i < Opcodes.size(); ++i) { 1313 const std::string &Name = nameWithID(Opcodes[i]); 1314 1315 errs() << '\t' << Name << " "; 1316 dumpBits(errs(), 1317 getBitsField(*AllInstructions[Opcodes[i]]->TheDef, "Inst")); 1318 errs() << '\n'; 1319 } 1320 1321 return true; 1322 } 1323 1324 static bool populateInstruction(const CodeGenInstruction &CGI, unsigned Opc, 1325 std::map<unsigned, std::vector<OperandInfo> > &Operands){ 1326 const Record &Def = *CGI.TheDef; 1327 // If all the bit positions are not specified; do not decode this instruction. 1328 // We are bound to fail! For proper disassembly, the well-known encoding bits 1329 // of the instruction must be fully specified. 1330 // 1331 // This also removes pseudo instructions from considerations of disassembly, 1332 // which is a better design and less fragile than the name matchings. 1333 // Ignore "asm parser only" instructions. 1334 if (Def.getValueAsBit("isAsmParserOnly") || 1335 Def.getValueAsBit("isCodeGenOnly")) 1336 return false; 1337 1338 BitsInit &Bits = getBitsField(Def, "Inst"); 1339 if (Bits.allInComplete()) return false; 1340 1341 std::vector<OperandInfo> InsnOperands; 1342 1343 // If the instruction has specified a custom decoding hook, use that instead 1344 // of trying to auto-generate the decoder. 1345 std::string InstDecoder = Def.getValueAsString("DecoderMethod"); 1346 if (InstDecoder != "") { 1347 InsnOperands.push_back(OperandInfo(InstDecoder)); 1348 Operands[Opc] = InsnOperands; 1349 return true; 1350 } 1351 1352 // Generate a description of the operand of the instruction that we know 1353 // how to decode automatically. 1354 // FIXME: We'll need to have a way to manually override this as needed. 1355 1356 // Gather the outputs/inputs of the instruction, so we can find their 1357 // positions in the encoding. This assumes for now that they appear in the 1358 // MCInst in the order that they're listed. 1359 std::vector<std::pair<Init*, std::string> > InOutOperands; 1360 DagInit *Out = Def.getValueAsDag("OutOperandList"); 1361 DagInit *In = Def.getValueAsDag("InOperandList"); 1362 for (unsigned i = 0; i < Out->getNumArgs(); ++i) 1363 InOutOperands.push_back(std::make_pair(Out->getArg(i), Out->getArgName(i))); 1364 for (unsigned i = 0; i < In->getNumArgs(); ++i) 1365 InOutOperands.push_back(std::make_pair(In->getArg(i), In->getArgName(i))); 1366 1367 // Search for tied operands, so that we can correctly instantiate 1368 // operands that are not explicitly represented in the encoding. 1369 std::map<std::string, std::string> TiedNames; 1370 for (unsigned i = 0; i < CGI.Operands.size(); ++i) { 1371 int tiedTo = CGI.Operands[i].getTiedRegister(); 1372 if (tiedTo != -1) { 1373 TiedNames[InOutOperands[i].second] = InOutOperands[tiedTo].second; 1374 TiedNames[InOutOperands[tiedTo].second] = InOutOperands[i].second; 1375 } 1376 } 1377 1378 // For each operand, see if we can figure out where it is encoded. 1379 for (std::vector<std::pair<Init*, std::string> >::const_iterator 1380 NI = InOutOperands.begin(), NE = InOutOperands.end(); NI != NE; ++NI) { 1381 std::string Decoder = ""; 1382 1383 // At this point, we can locate the field, but we need to know how to 1384 // interpret it. As a first step, require the target to provide callbacks 1385 // for decoding register classes. 1386 // FIXME: This need to be extended to handle instructions with custom 1387 // decoder methods, and operands with (simple) MIOperandInfo's. 1388 TypedInit *TI = dynamic_cast<TypedInit*>(NI->first); 1389 RecordRecTy *Type = dynamic_cast<RecordRecTy*>(TI->getType()); 1390 Record *TypeRecord = Type->getRecord(); 1391 bool isReg = false; 1392 if (TypeRecord->isSubClassOf("RegisterOperand")) 1393 TypeRecord = TypeRecord->getValueAsDef("RegClass"); 1394 if (TypeRecord->isSubClassOf("RegisterClass")) { 1395 Decoder = "Decode" + TypeRecord->getName() + "RegisterClass"; 1396 isReg = true; 1397 } 1398 1399 RecordVal *DecoderString = TypeRecord->getValue("DecoderMethod"); 1400 StringInit *String = DecoderString ? 1401 dynamic_cast<StringInit*>(DecoderString->getValue()) : 0; 1402 if (!isReg && String && String->getValue() != "") 1403 Decoder = String->getValue(); 1404 1405 OperandInfo OpInfo(Decoder); 1406 unsigned Base = ~0U; 1407 unsigned Width = 0; 1408 unsigned Offset = 0; 1409 1410 for (unsigned bi = 0; bi < Bits.getNumBits(); ++bi) { 1411 VarInit *Var = 0; 1412 VarBitInit *BI = dynamic_cast<VarBitInit*>(Bits.getBit(bi)); 1413 if (BI) 1414 Var = dynamic_cast<VarInit*>(BI->getVariable()); 1415 else 1416 Var = dynamic_cast<VarInit*>(Bits.getBit(bi)); 1417 1418 if (!Var) { 1419 if (Base != ~0U) { 1420 OpInfo.addField(Base, Width, Offset); 1421 Base = ~0U; 1422 Width = 0; 1423 Offset = 0; 1424 } 1425 continue; 1426 } 1427 1428 if (Var->getName() != NI->second && 1429 Var->getName() != TiedNames[NI->second]) { 1430 if (Base != ~0U) { 1431 OpInfo.addField(Base, Width, Offset); 1432 Base = ~0U; 1433 Width = 0; 1434 Offset = 0; 1435 } 1436 continue; 1437 } 1438 1439 if (Base == ~0U) { 1440 Base = bi; 1441 Width = 1; 1442 Offset = BI ? BI->getBitNum() : 0; 1443 } else if (BI && BI->getBitNum() != Offset + Width) { 1444 OpInfo.addField(Base, Width, Offset); 1445 Base = bi; 1446 Width = 1; 1447 Offset = BI->getBitNum(); 1448 } else { 1449 ++Width; 1450 } 1451 } 1452 1453 if (Base != ~0U) 1454 OpInfo.addField(Base, Width, Offset); 1455 1456 if (OpInfo.numFields() > 0) 1457 InsnOperands.push_back(OpInfo); 1458 } 1459 1460 Operands[Opc] = InsnOperands; 1461 1462 1463 #if 0 1464 DEBUG({ 1465 // Dumps the instruction encoding bits. 1466 dumpBits(errs(), Bits); 1467 1468 errs() << '\n'; 1469 1470 // Dumps the list of operand info. 1471 for (unsigned i = 0, e = CGI.Operands.size(); i != e; ++i) { 1472 const CGIOperandList::OperandInfo &Info = CGI.Operands[i]; 1473 const std::string &OperandName = Info.Name; 1474 const Record &OperandDef = *Info.Rec; 1475 1476 errs() << "\t" << OperandName << " (" << OperandDef.getName() << ")\n"; 1477 } 1478 }); 1479 #endif 1480 1481 return true; 1482 } 1483 1484 static void emitHelper(llvm::raw_ostream &o, unsigned BitWidth) { 1485 unsigned Indentation = 0; 1486 std::string WidthStr = "uint" + utostr(BitWidth) + "_t"; 1487 1488 o << '\n'; 1489 1490 o.indent(Indentation) << "static " << WidthStr << 1491 " fieldFromInstruction" << BitWidth << 1492 "(" << WidthStr <<" insn, unsigned startBit, unsigned numBits)\n"; 1493 1494 o.indent(Indentation) << "{\n"; 1495 1496 ++Indentation; ++Indentation; 1497 o.indent(Indentation) << "assert(startBit + numBits <= " << BitWidth 1498 << " && \"Instruction field out of bounds!\");\n"; 1499 o << '\n'; 1500 o.indent(Indentation) << WidthStr << " fieldMask;\n"; 1501 o << '\n'; 1502 o.indent(Indentation) << "if (numBits == " << BitWidth << ")\n"; 1503 1504 ++Indentation; ++Indentation; 1505 o.indent(Indentation) << "fieldMask = (" << WidthStr << ")-1;\n"; 1506 --Indentation; --Indentation; 1507 1508 o.indent(Indentation) << "else\n"; 1509 1510 ++Indentation; ++Indentation; 1511 o.indent(Indentation) << "fieldMask = ((1 << numBits) - 1) << startBit;\n"; 1512 --Indentation; --Indentation; 1513 1514 o << '\n'; 1515 o.indent(Indentation) << "return (insn & fieldMask) >> startBit;\n"; 1516 --Indentation; --Indentation; 1517 1518 o.indent(Indentation) << "}\n"; 1519 1520 o << '\n'; 1521 } 1522 1523 // Emits disassembler code for instruction decoding. 1524 void FixedLenDecoderEmitter::run(raw_ostream &o) { 1525 o << "#include \"llvm/MC/MCInst.h\"\n"; 1526 o << "#include \"llvm/Support/DataTypes.h\"\n"; 1527 o << "#include <assert.h>\n"; 1528 o << '\n'; 1529 o << "namespace llvm {\n\n"; 1530 1531 // Parameterize the decoders based on namespace and instruction width. 1532 const std::vector<const CodeGenInstruction*> &NumberedInstructions = 1533 Target.getInstructionsByEnumValue(); 1534 std::map<std::pair<std::string, unsigned>, 1535 std::vector<unsigned> > OpcMap; 1536 std::map<unsigned, std::vector<OperandInfo> > Operands; 1537 1538 for (unsigned i = 0; i < NumberedInstructions.size(); ++i) { 1539 const CodeGenInstruction *Inst = NumberedInstructions[i]; 1540 const Record *Def = Inst->TheDef; 1541 unsigned Size = Def->getValueAsInt("Size"); 1542 if (Def->getValueAsString("Namespace") == "TargetOpcode" || 1543 Def->getValueAsBit("isPseudo") || 1544 Def->getValueAsBit("isAsmParserOnly") || 1545 Def->getValueAsBit("isCodeGenOnly")) 1546 continue; 1547 1548 std::string DecoderNamespace = Def->getValueAsString("DecoderNamespace"); 1549 1550 if (Size) { 1551 if (populateInstruction(*Inst, i, Operands)) { 1552 OpcMap[std::make_pair(DecoderNamespace, Size)].push_back(i); 1553 } 1554 } 1555 } 1556 1557 std::set<unsigned> Sizes; 1558 for (std::map<std::pair<std::string, unsigned>, 1559 std::vector<unsigned> >::const_iterator 1560 I = OpcMap.begin(), E = OpcMap.end(); I != E; ++I) { 1561 // If we haven't visited this instruction width before, emit the 1562 // helper method to extract fields. 1563 if (!Sizes.count(I->first.second)) { 1564 emitHelper(o, 8*I->first.second); 1565 Sizes.insert(I->first.second); 1566 } 1567 1568 // Emit the decoder for this namespace+width combination. 1569 FilterChooser FC(NumberedInstructions, I->second, Operands, 1570 8*I->first.second, this); 1571 FC.emitTop(o, 0, I->first.first); 1572 } 1573 1574 o << "\n} // End llvm namespace \n"; 1575 } 1576