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