13c827367444ee418f129b2c238299f49d3264554Jarkko Poyry//===------------ FixedLenDecoderEmitter.cpp - Decoder Generator ----------===// 23c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// 33c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// The LLVM Compiler Infrastructure 43c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// 53c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// This file is distributed under the University of Illinois Open Source 63c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// License. See LICENSE.TXT for details. 73c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// 83c827367444ee418f129b2c238299f49d3264554Jarkko Poyry//===----------------------------------------------------------------------===// 93c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// 103c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// It contains the tablegen backend that emits the decoder functions for 113c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// targets with fixed length instruction set. 123c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// 133c827367444ee418f129b2c238299f49d3264554Jarkko Poyry//===----------------------------------------------------------------------===// 143c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 153c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#define DEBUG_TYPE "decoder-emitter" 163c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 173c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include "FixedLenDecoderEmitter.h" 183c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include "CodeGenTarget.h" 193c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include "llvm/TableGen/Record.h" 203c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include "llvm/ADT/StringExtras.h" 213c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include "llvm/Support/Debug.h" 223c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include "llvm/Support/raw_ostream.h" 233c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 243c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include <vector> 253c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include <map> 263c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include <string> 273c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 283c827367444ee418f129b2c238299f49d3264554Jarkko Poyryusing namespace llvm; 293c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 303c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// The set (BIT_TRUE, BIT_FALSE, BIT_UNSET) represents a ternary logic system 313c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// for a bit value. 323c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// 333c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// BIT_UNFILTERED is used as the init value for a filter position. It is used 343c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// only for filter processings. 353c827367444ee418f129b2c238299f49d3264554Jarkko Poyrytypedef enum { 363c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BIT_TRUE, // '1' 373c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BIT_FALSE, // '0' 383c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BIT_UNSET, // '?' 393c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BIT_UNFILTERED // unfiltered 403c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} bit_value_t; 413c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 423c827367444ee418f129b2c238299f49d3264554Jarkko Poyrystatic bool ValueSet(bit_value_t V) { 433c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return (V == BIT_TRUE || V == BIT_FALSE); 443c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 453c827367444ee418f129b2c238299f49d3264554Jarkko Poyrystatic bool ValueNotSet(bit_value_t V) { 463c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return (V == BIT_UNSET); 473c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 483c827367444ee418f129b2c238299f49d3264554Jarkko Poyrystatic int Value(bit_value_t V) { 493c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return ValueNotSet(V) ? -1 : (V == BIT_FALSE ? 0 : 1); 503c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 513c827367444ee418f129b2c238299f49d3264554Jarkko Poyrystatic bit_value_t bitFromBits(BitsInit &bits, unsigned index) { 523c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (BitInit *bit = dynamic_cast<BitInit*>(bits.getBit(index))) 533c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return bit->getValue() ? BIT_TRUE : BIT_FALSE; 543c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 553c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // The bit is uninitialized. 563c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return BIT_UNSET; 573c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 583c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Prints the bit value for each position. 593c827367444ee418f129b2c238299f49d3264554Jarkko Poyrystatic void dumpBits(raw_ostream &o, BitsInit &bits) { 603c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned index; 613c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 623c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (index = bits.getNumBits(); index > 0; index--) { 633c827367444ee418f129b2c238299f49d3264554Jarkko Poyry switch (bitFromBits(bits, index - 1)) { 643c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case BIT_TRUE: 653c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << "1"; 663c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 673c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case BIT_FALSE: 683c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << "0"; 693c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 703c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case BIT_UNSET: 713c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << "_"; 723c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 7307104dfa13013a73a59a93cbd8d132254a5a171dJarkko Pöyry default: 743c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(0 && "unexpected return value from bitFromBits"); 753c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 763c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 773c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 783c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 793c827367444ee418f129b2c238299f49d3264554Jarkko Poyrystatic BitsInit &getBitsField(const Record &def, const char *str) { 803c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BitsInit *bits = def.getValueAsBitsInit(str); 813c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return *bits; 823c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 833c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 843c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Forward declaration. 853c827367444ee418f129b2c238299f49d3264554Jarkko Poyryclass FilterChooser; 863c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 873c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Representation of the instruction to work on. 883c827367444ee418f129b2c238299f49d3264554Jarkko Poyrytypedef std::vector<bit_value_t> insn_t; 893c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 903c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// Filter - Filter works with FilterChooser to produce the decoding tree for 913c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// the ISA. 923c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// 933c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// It is useful to think of a Filter as governing the switch stmts of the 943c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// decoding tree in a certain level. Each case stmt delegates to an inferior 953c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// FilterChooser to decide what further decoding logic to employ, or in another 963c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// words, what other remaining bits to look at. The FilterChooser eventually 973c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// chooses a best Filter to do its job. 983c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// 993c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// This recursive scheme ends when the number of Opcodes assigned to the 1003c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// FilterChooser becomes 1 or if there is a conflict. A conflict happens when 1013c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// the Filter/FilterChooser combo does not know how to distinguish among the 1023c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// Opcodes assigned. 1033c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// 1043c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// An example of a conflict is 1053c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// 1063c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// Conflict: 1073c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// 111101000.00........00010000.... 1083c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// 111101000.00........0001........ 1093c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// 1111010...00........0001........ 1103c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// 1111010...00.................... 1113c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// 1111010......................... 1123c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// 1111............................ 1133c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// ................................ 1143c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// VST4q8a 111101000_00________00010000____ 1153c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// VST4q8b 111101000_00________00010000____ 1163c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// 1173c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// The Debug output shows the path that the decoding tree follows to reach the 1183c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// the conclusion that there is a conflict. VST4q8a is a vst4 to double-spaced 1193c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// even registers, while VST4q8b is a vst4 to double-spaced odd regsisters. 12093df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry/// 1213c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// The encoding info in the .td files does not specify this meta information, 1223c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// which could have been used by the decoder to resolve the conflict. The 1236d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry/// decoder could try to decode the even/odd register numbering and assign to 1246d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry/// VST4q8a or VST4q8b, but for the time being, the decoder chooses the "a" 1256d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry/// version and return the Opcode since the two have the same Asm format string. 1266d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyryclass Filter { 1276d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyryprotected: 1286d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry FilterChooser *Owner; // points to the FilterChooser who owns this filter 1296d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry unsigned StartBit; // the starting bit position 1306d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry unsigned NumBits; // number of bits to filter 1316d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry bool Mixed; // a mixed region contains both set and unset bits 1326d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry 1336d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry // Map of well-known segment value to the set of uid's with that value. 1346d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry std::map<uint64_t, std::vector<unsigned> > FilteredInstructions; 1356d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry 1366d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry // Set of uid's with non-constant segment values. 1376d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry std::vector<unsigned> VariableInstructions; 1386d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry 1396d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry // Map of well-known segment value to its delegate. 1406d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry std::map<unsigned, FilterChooser*> FilterChooserMap; 1416d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry 1426d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry // Number of instructions which fall under FilteredInstructions category. 1436d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry unsigned NumFiltered; 1446d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry 1456d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry // Keeps track of the last opcode in the filtered bucket. 1466d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry unsigned LastOpcFiltered; 1476d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry 1486d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry // Number of instructions which fall under VariableInstructions category. 1496d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry unsigned NumVariable; 1506d31105cb879614b2cf87193ea90215efd13bcceJarkko Pöyry 1513c827367444ee418f129b2c238299f49d3264554Jarkko Poyrypublic: 1523c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned getNumFiltered() { return NumFiltered; } 1533c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned getNumVariable() { return NumVariable; } 1543c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned getSingletonOpc() { 1553c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(NumFiltered == 1); 1563c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return LastOpcFiltered; 1573c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 1583c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Return the filter chooser for the group of instructions without constant 1593c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // segment values. 1603c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FilterChooser &getVariableFC() { 1613c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(NumFiltered == 1); 1623c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(FilterChooserMap.size() == 1); 1633c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return *(FilterChooserMap.find((unsigned)-1)->second); 1643c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 1653c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1663c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Filter(const Filter &f); 1673c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, bool mixed); 1683c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1693c827367444ee418f129b2c238299f49d3264554Jarkko Poyry ~Filter(); 1703c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1713c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Divides the decoding task into sub tasks and delegates them to the 1723c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // inferior FilterChooser's. 1733c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // 1743c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // A special case arises when there's only one entry in the filtered 1753c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // instructions. In order to unambiguously decode the singleton, we need to 1763c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // match the remaining undecoded encoding bits against the singleton. 1773c827367444ee418f129b2c238299f49d3264554Jarkko Poyry void recurse(); 1783c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1793c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Emit code to decode instructions given a segment or segments of bits. 1803c827367444ee418f129b2c238299f49d3264554Jarkko Poyry void emit(raw_ostream &o, unsigned &Indentation); 1813c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1823c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Returns the number of fanout produced by the filter. More fanout implies 1833c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // the filter distinguishes more categories of instructions. 1843c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned usefulness() const; 1853c827367444ee418f129b2c238299f49d3264554Jarkko Poyry}; // End of class Filter 1863c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1873c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// These are states of our finite state machines used in FilterChooser's 1883c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// filterProcessor() which produces the filter candidates to use. 1893c827367444ee418f129b2c238299f49d3264554Jarkko Poyrytypedef enum { 1903c827367444ee418f129b2c238299f49d3264554Jarkko Poyry ATTR_NONE, 1913c827367444ee418f129b2c238299f49d3264554Jarkko Poyry ATTR_FILTERED, 1923c827367444ee418f129b2c238299f49d3264554Jarkko Poyry ATTR_ALL_SET, 1933c827367444ee418f129b2c238299f49d3264554Jarkko Poyry ATTR_ALL_UNSET, 1943c827367444ee418f129b2c238299f49d3264554Jarkko Poyry ATTR_MIXED 1953c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} bitAttr_t; 1963c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1973c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// FilterChooser - FilterChooser chooses the best filter among a set of Filters 1983c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// in order to perform the decoding of instructions at the current level. 1993c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// 2003c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// Decoding proceeds from the top down. Based on the well-known encoding bits 2013c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// of instructions available, FilterChooser builds up the possible Filters that 2023c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// can further the task of decoding by distinguishing among the remaining 2033c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// candidate instructions. 2043c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// 2053c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// Once a filter has been chosen, it is called upon to divide the decoding task 2063c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// into sub-tasks and delegates them to its inferior FilterChoosers for further 2073c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// processings. 2083c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// 2093c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// It is useful to think of a Filter as governing the switch stmts of the 2103c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// decoding tree. And each case is delegated to an inferior FilterChooser to 2113c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// decide what further remaining bits to look at. 2123c827367444ee418f129b2c238299f49d3264554Jarkko Poyryclass FilterChooser { 2133c827367444ee418f129b2c238299f49d3264554Jarkko Poyryprotected: 2143c827367444ee418f129b2c238299f49d3264554Jarkko Poyry friend class Filter; 2153c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 2163c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Vector of codegen instructions to choose our filter. 2173c827367444ee418f129b2c238299f49d3264554Jarkko Poyry const std::vector<const CodeGenInstruction*> &AllInstructions; 2183c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 2193c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Vector of uid's for this filter chooser to work on. 2203c827367444ee418f129b2c238299f49d3264554Jarkko Poyry const std::vector<unsigned> Opcodes; 2213c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 2223c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Lookup table for the operand decoding of instructions. 2233c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::map<unsigned, std::vector<OperandInfo> > &Operands; 2243c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 2253c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Vector of candidate filters. 2263c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<Filter> Filters; 2273c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 2283c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Array of bit values passed down from our parent. 2293c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Set to all BIT_UNFILTERED's for Parent == NULL. 2303c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<bit_value_t> FilterBitValues; 2313c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 2323c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Links to the FilterChooser above us in the decoding tree. 2333c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FilterChooser *Parent; 2343c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 2353c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Index of the best filter from Filters. 2363c827367444ee418f129b2c238299f49d3264554Jarkko Poyry int BestIndex; 2373c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 2383c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Width of instructions 2393c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned BitWidth; 2403c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 2413c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Parent emitter 2423c827367444ee418f129b2c238299f49d3264554Jarkko Poyry const FixedLenDecoderEmitter *Emitter; 2433c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 2443c827367444ee418f129b2c238299f49d3264554Jarkko Poyrypublic: 2453c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FilterChooser(const FilterChooser &FC) : 2463c827367444ee418f129b2c238299f49d3264554Jarkko Poyry AllInstructions(FC.AllInstructions), Opcodes(FC.Opcodes), 2473c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Operands(FC.Operands), Filters(FC.Filters), 2483c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FilterBitValues(FC.FilterBitValues), Parent(FC.Parent), 2493c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BestIndex(FC.BestIndex), BitWidth(FC.BitWidth), 2503c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Emitter(FC.Emitter) { } 2513c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 2523c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FilterChooser(const std::vector<const CodeGenInstruction*> &Insts, 2533c827367444ee418f129b2c238299f49d3264554Jarkko Poyry const std::vector<unsigned> &IDs, 2543c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::map<unsigned, std::vector<OperandInfo> > &Ops, 2553c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned BW, 2563c827367444ee418f129b2c238299f49d3264554Jarkko Poyry const FixedLenDecoderEmitter *E) : 2573c827367444ee418f129b2c238299f49d3264554Jarkko Poyry AllInstructions(Insts), Opcodes(IDs), Operands(Ops), Filters(), 25893df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry Parent(NULL), BestIndex(-1), BitWidth(BW), Emitter(E) { 2593c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (unsigned i = 0; i < BitWidth; ++i) 26029340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi FilterBitValues.push_back(BIT_UNFILTERED); 26129340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi 26229340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi doFilter(); 2633c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 2643c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 2653c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FilterChooser(const std::vector<const CodeGenInstruction*> &Insts, 2663c827367444ee418f129b2c238299f49d3264554Jarkko Poyry const std::vector<unsigned> &IDs, 2673c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::map<unsigned, std::vector<OperandInfo> > &Ops, 2683c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<bit_value_t> &ParentFilterBitValues, 2693c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FilterChooser &parent) : 2703c827367444ee418f129b2c238299f49d3264554Jarkko Poyry AllInstructions(Insts), Opcodes(IDs), Operands(Ops), 2713c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Filters(), FilterBitValues(ParentFilterBitValues), 2723c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Parent(&parent), BestIndex(-1), BitWidth(parent.BitWidth), 2733c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Emitter(parent.Emitter) { 2743c827367444ee418f129b2c238299f49d3264554Jarkko Poyry doFilter(); 2753c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 2763c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 2773c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // The top level filter chooser has NULL as its parent. 2783c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bool isTopLevel() { return Parent == NULL; } 2793c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 2803c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Emit the top level typedef and decodeInstruction() function. 28129340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi void emitTop(raw_ostream &o, unsigned Indentation, std::string Namespace); 2823c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 28329340067e919854db7d50bb8c0b666117b229f5eMika Isojärviprotected: 2843c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Populates the insn given the uid. 28529340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi void insnWithID(insn_t &Insn, unsigned Opcode) const { 28629340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi BitsInit &Bits = getBitsField(*AllInstructions[Opcode]->TheDef, "Inst"); 28729340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi 28829340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi for (unsigned i = 0; i < BitWidth; ++i) 28929340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi Insn.push_back(bitFromBits(Bits, i)); 29029340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi } 29129340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi 2923c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Returns the record name. 29329340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi const std::string &nameWithID(unsigned Opcode) const { 29429340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi return AllInstructions[Opcode]->TheDef->getName(); 2953c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 2963c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 2973c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Populates the field of the insn given the start position and the number of 2983c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // consecutive bits to scan for. 2993c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // 3003c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Returns false if there exists any uninitialized bit value in the range. 3013c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Returns true, otherwise. 3023c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bool fieldFromInsn(uint64_t &Field, insn_t &Insn, unsigned StartBit, 3033c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned NumBits) const; 3043c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 3053c827367444ee418f129b2c238299f49d3264554Jarkko Poyry /// dumpFilterArray - dumpFilterArray prints out debugging info for the given 3063c827367444ee418f129b2c238299f49d3264554Jarkko Poyry /// filter array as a series of chars. 3073c827367444ee418f129b2c238299f49d3264554Jarkko Poyry void dumpFilterArray(raw_ostream &o, std::vector<bit_value_t> & filter); 3083c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 3093c827367444ee418f129b2c238299f49d3264554Jarkko Poyry /// dumpStack - dumpStack traverses the filter chooser chain and calls 3103c827367444ee418f129b2c238299f49d3264554Jarkko Poyry /// dumpFilterArray on each filter chooser up to the top level one. 3113c827367444ee418f129b2c238299f49d3264554Jarkko Poyry void dumpStack(raw_ostream &o, const char *prefix); 3123c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 3133c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Filter &bestFilter() { 3143c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(BestIndex != -1 && "BestIndex not set"); 3153c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return Filters[BestIndex]; 3163c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 3173c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 3183c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Called from Filter::recurse() when singleton exists. For debug purpose. 31929340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi void SingletonExists(unsigned Opc); 32029340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi 3213c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bool PositionFiltered(unsigned i) { 32293df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry return ValueSet(FilterBitValues[i]); 3233c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 3243c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 3253c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Calculates the island(s) needed to decode the instruction. 3263c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // This returns a lit of undecoded bits of an instructions, for example, 3273c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be 3283c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // decoded bits in order to verify that the instruction matches the Opcode. 3293c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned getIslands(std::vector<unsigned> &StartBits, 3303c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<unsigned> &EndBits, std::vector<uint64_t> &FieldVals, 3313c827367444ee418f129b2c238299f49d3264554Jarkko Poyry insn_t &Insn); 3323c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 3333c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Emits code to check the Predicates member of an instruction are true. 3343c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Returns true if predicate matches were emitted, false otherwise. 3353c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bool emitPredicateMatch(raw_ostream &o, unsigned &Indentation,unsigned Opc); 336becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi 337becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi // Emits code to decode the singleton. Return true if we have matched all the 338becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi // well-known bits. 33929340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi bool emitSingletonDecoder(raw_ostream &o, unsigned &Indentation,unsigned Opc); 340becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi 34129340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi // Emits code to decode the singleton, and then to decode the rest. 3423c827367444ee418f129b2c238299f49d3264554Jarkko Poyry void emitSingletonDecoder(raw_ostream &o, unsigned &Indentation,Filter &Best); 343becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi 3443c827367444ee418f129b2c238299f49d3264554Jarkko Poyry void emitBinaryParser(raw_ostream &o , unsigned &Indentation, 345becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi OperandInfo &OpInfo); 346becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi 347becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi // Assign a single filter and run with it. 348becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi void runSingleFilter(FilterChooser &owner, unsigned startBit, unsigned numBit, 3493c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bool mixed); 350becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi 351becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi // reportRegion is a helper function for filterProcessor to mark a region as 35293df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry // eligible for use as a filter region. 3533c827367444ee418f129b2c238299f49d3264554Jarkko Poyry void reportRegion(bitAttr_t RA, unsigned StartBit, unsigned BitIndex, 3543c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bool AllowMixed); 3553c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 3563c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // FilterProcessor scans the well-known encoding bits of the instructions and 3573c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // builds up a list of candidate filters. It chooses the best filter and 3583c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // recursively descends down the decoding tree. 3593c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bool filterProcessor(bool AllowMixed, bool Greedy = true); 3603c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 3613c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Decides on the best configuration of filter(s) to use in order to decode 3623c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // the instructions. A conflict of instructions may occur, in which case we 3633c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // dump the conflict set to the standard error. 364becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi void doFilter(); 365becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi 366becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi // Emits code to decode our share of instructions. Returns true if the 367becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi // emitted code causes a return, which occurs if we know how to decode 3683c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // the instruction at this level or the instruction is not decodeable. 36929340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi bool emit(raw_ostream &o, unsigned &Indentation); 37029340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi}; 37129340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi 37229340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi/////////////////////////// 37329340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi// // 374becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi// Filter Implmenetation // 3753c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// // 376becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi/////////////////////////// 377becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi 3783c827367444ee418f129b2c238299f49d3264554Jarkko PoyryFilter::Filter(const Filter &f) : 37929340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi Owner(f.Owner), StartBit(f.StartBit), NumBits(f.NumBits), Mixed(f.Mixed), 38029340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi FilteredInstructions(f.FilteredInstructions), 3813c827367444ee418f129b2c238299f49d3264554Jarkko Poyry VariableInstructions(f.VariableInstructions), 3823c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FilterChooserMap(f.FilterChooserMap), NumFiltered(f.NumFiltered), 383becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi LastOpcFiltered(f.LastOpcFiltered), NumVariable(f.NumVariable) { 384becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi} 385becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi 386becd5d53015521acf7536ba754de326d8b1da2f3Mika IsojärviFilter::Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, 38729340067e919854db7d50bb8c0b666117b229f5eMika Isojärvi bool mixed) : Owner(&owner), StartBit(startBit), NumBits(numBits), 388becd5d53015521acf7536ba754de326d8b1da2f3Mika Isojärvi Mixed(mixed) { 3893c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(StartBit + NumBits - 1 < Owner->BitWidth); 3903c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 39193df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry NumFiltered = 0; 3923c827367444ee418f129b2c238299f49d3264554Jarkko Poyry LastOpcFiltered = 0; 3933c827367444ee418f129b2c238299f49d3264554Jarkko Poyry NumVariable = 0; 3943c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 3953c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (unsigned i = 0, e = Owner->Opcodes.size(); i != e; ++i) { 3963c827367444ee418f129b2c238299f49d3264554Jarkko Poyry insn_t Insn; 3973c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 3983c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Populates the insn given the uid. 3993c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Owner->insnWithID(Insn, Owner->Opcodes[i]); 4003c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 4013c827367444ee418f129b2c238299f49d3264554Jarkko Poyry uint64_t Field; 4023c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Scans the segment for possibly well-specified encoding bits. 4033c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bool ok = Owner->fieldFromInsn(Field, Insn, StartBit, NumBits); 4043c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 4053c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (ok) { 4063c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // The encoding bits are well-known. Lets add the uid of the 4073c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // instruction into the bucket keyed off the constant field value. 4083c827367444ee418f129b2c238299f49d3264554Jarkko Poyry LastOpcFiltered = Owner->Opcodes[i]; 4093c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FilteredInstructions[Field].push_back(LastOpcFiltered); 4103c827367444ee418f129b2c238299f49d3264554Jarkko Poyry ++NumFiltered; 4113c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } else { 4123c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Some of the encoding bit(s) are unspecfied. This contributes to 4133c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // one additional member of "Variable" instructions. 4143c827367444ee418f129b2c238299f49d3264554Jarkko Poyry VariableInstructions.push_back(Owner->Opcodes[i]); 4153c827367444ee418f129b2c238299f49d3264554Jarkko Poyry ++NumVariable; 4163c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 4173c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 4183c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 4193c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert((FilteredInstructions.size() + VariableInstructions.size() > 0) 4203c827367444ee418f129b2c238299f49d3264554Jarkko Poyry && "Filter returns no instruction categories"); 4213c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 4223c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 4233c827367444ee418f129b2c238299f49d3264554Jarkko PoyryFilter::~Filter() { 4243c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::map<unsigned, FilterChooser*>::iterator filterIterator; 4253c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (filterIterator = FilterChooserMap.begin(); 4263c827367444ee418f129b2c238299f49d3264554Jarkko Poyry filterIterator != FilterChooserMap.end(); 4273c827367444ee418f129b2c238299f49d3264554Jarkko Poyry filterIterator++) { 4283c827367444ee418f129b2c238299f49d3264554Jarkko Poyry delete filterIterator->second; 4293c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 4303c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 43193df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry 4323c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Divides the decoding task into sub tasks and delegates them to the 4333c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// inferior FilterChooser's. 4343c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// 4353c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// A special case arises when there's only one entry in the filtered 4363c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// instructions. In order to unambiguously decode the singleton, we need to 4373c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// match the remaining undecoded encoding bits against the singleton. 4383c827367444ee418f129b2c238299f49d3264554Jarkko Poyryvoid Filter::recurse() { 4393c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::map<uint64_t, std::vector<unsigned> >::const_iterator mapIterator; 4403c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 4413c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Starts by inheriting our parent filter chooser's filter bit values. 4423c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<bit_value_t> BitValueArray(Owner->FilterBitValues); 4433c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 4443c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned bitIndex; 4453c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 4463c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (VariableInstructions.size()) { 4473c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Conservatively marks each segment position as BIT_UNSET. 4483c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (bitIndex = 0; bitIndex < NumBits; bitIndex++) 4493c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BitValueArray[StartBit + bitIndex] = BIT_UNSET; 4503c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 4513c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Delegates to an inferior filter chooser for further processing on this 4523c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // group of instructions whose segment values are variable. 4533c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FilterChooserMap.insert(std::pair<unsigned, FilterChooser*>( 4543c827367444ee418f129b2c238299f49d3264554Jarkko Poyry (unsigned)-1, 4553c827367444ee418f129b2c238299f49d3264554Jarkko Poyry new FilterChooser(Owner->AllInstructions, 4563c827367444ee418f129b2c238299f49d3264554Jarkko Poyry VariableInstructions, 4573c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Owner->Operands, 4583c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BitValueArray, 4593c827367444ee418f129b2c238299f49d3264554Jarkko Poyry *Owner) 4603c827367444ee418f129b2c238299f49d3264554Jarkko Poyry )); 4613c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 46293df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry 4633c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // No need to recurse for a singleton filtered instruction. 4643c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // See also Filter::emit(). 4653c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (getNumFiltered() == 1) { 4663c827367444ee418f129b2c238299f49d3264554Jarkko Poyry //Owner->SingletonExists(LastOpcFiltered); 4673c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(FilterChooserMap.size() == 1); 4683c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return; 4693c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 4703c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 4713c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Otherwise, create sub choosers. 4723c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (mapIterator = FilteredInstructions.begin(); 4733c827367444ee418f129b2c238299f49d3264554Jarkko Poyry mapIterator != FilteredInstructions.end(); 4743c827367444ee418f129b2c238299f49d3264554Jarkko Poyry mapIterator++) { 4753c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 4763c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Marks all the segment positions with either BIT_TRUE or BIT_FALSE. 4773c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (bitIndex = 0; bitIndex < NumBits; bitIndex++) { 4783c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (mapIterator->first & (1ULL << bitIndex)) 4793c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BitValueArray[StartBit + bitIndex] = BIT_TRUE; 4803c827367444ee418f129b2c238299f49d3264554Jarkko Poyry else 4813c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BitValueArray[StartBit + bitIndex] = BIT_FALSE; 4823c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 4833c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 4843c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Delegates to an inferior filter chooser for further processing on this 4853c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // category of instructions. 4863c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FilterChooserMap.insert(std::pair<unsigned, FilterChooser*>( 4873c827367444ee418f129b2c238299f49d3264554Jarkko Poyry mapIterator->first, 4883c827367444ee418f129b2c238299f49d3264554Jarkko Poyry new FilterChooser(Owner->AllInstructions, 4893c827367444ee418f129b2c238299f49d3264554Jarkko Poyry mapIterator->second, 4903c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Owner->Operands, 4913c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BitValueArray, 4923c827367444ee418f129b2c238299f49d3264554Jarkko Poyry *Owner) 4933c827367444ee418f129b2c238299f49d3264554Jarkko Poyry )); 4943c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 4953c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 4963c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 4973c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Emit code to decode instructions given a segment or segments of bits. 4983c827367444ee418f129b2c238299f49d3264554Jarkko Poyryvoid Filter::emit(raw_ostream &o, unsigned &Indentation) { 4993c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << "// Check Inst{"; 5003c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5013c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (NumBits > 1) 5023c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << (StartBit + NumBits - 1) << '-'; 5033c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5043c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << StartBit << "} ...\n"; 5053c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5063c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << "switch (fieldFromInstruction" << Owner->BitWidth 5073c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << "(insn, " << StartBit << ", " 5083c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << NumBits << ")) {\n"; 5093c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5103c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::map<unsigned, FilterChooser*>::iterator filterIterator; 5113c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5123c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bool DefaultCase = false; 5133c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (filterIterator = FilterChooserMap.begin(); 5143c827367444ee418f129b2c238299f49d3264554Jarkko Poyry filterIterator != FilterChooserMap.end(); 5153c827367444ee418f129b2c238299f49d3264554Jarkko Poyry filterIterator++) { 51693df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry 5173c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Field value -1 implies a non-empty set of variable instructions. 5183c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // See also recurse(). 5193c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (filterIterator->first == (unsigned)-1) { 5203c827367444ee418f129b2c238299f49d3264554Jarkko Poyry DefaultCase = true; 5213c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5223c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << "default:\n"; 5233c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << " break; // fallthrough\n"; 5243c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5253c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Closing curly brace for the switch statement. 5263c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // This is unconventional because we want the default processing to be 5273c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // performed for the fallthrough cases as well, i.e., when the "cases" 5283c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // did not prove a decoded instruction. 5293c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << "}\n"; 5303c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5313c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } else 5323c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << "case " << filterIterator->first << ":\n"; 5333c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5343c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // We arrive at a category of instructions with the same segment value. 5353c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Now delegate to the sub filter chooser for further decodings. 5363c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // The case may fallthrough, which happens if the remaining well-known 5373c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // encoding bits do not match exactly. 5383c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (!DefaultCase) { ++Indentation; ++Indentation; } 5393c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5403c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bool finished = filterIterator->second->emit(o, Indentation); 5413c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // For top level default case, there's no need for a break statement. 5423c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (Owner->isTopLevel() && DefaultCase) 5433c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 5443c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (!finished) 5453c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << "break;\n"; 5463c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5473c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (!DefaultCase) { --Indentation; --Indentation; } 5483c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 5493c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5503c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // If there is no default case, we still need to supply a closing brace. 5513c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (!DefaultCase) { 5523c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Closing curly brace for the switch statement. 5533c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << "}\n"; 5543c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 5553c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 5563c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5573c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Returns the number of fanout produced by the filter. More fanout implies 5583c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// the filter distinguishes more categories of instructions. 5593c827367444ee418f129b2c238299f49d3264554Jarkko Poyryunsigned Filter::usefulness() const { 5603c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (VariableInstructions.size()) 5613c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return FilteredInstructions.size(); 5623c827367444ee418f129b2c238299f49d3264554Jarkko Poyry else 5633c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return FilteredInstructions.size() + 1; 5643c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 5653c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5663c827367444ee418f129b2c238299f49d3264554Jarkko Poyry////////////////////////////////// 5673c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// // 5683c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Filterchooser Implementation // 5693c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// // 5703c827367444ee418f129b2c238299f49d3264554Jarkko Poyry////////////////////////////////// 5713c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5723c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Emit the top level typedef and decodeInstruction() function. 5733c827367444ee418f129b2c238299f49d3264554Jarkko Poyryvoid FilterChooser::emitTop(raw_ostream &o, unsigned Indentation, 5743c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::string Namespace) { 5753c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << 5763c827367444ee418f129b2c238299f49d3264554Jarkko Poyry "static MCDisassembler::DecodeStatus decode" << Namespace << "Instruction" << BitWidth 5773c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << "(MCInst &MI, uint" << BitWidth << "_t insn, uint64_t Address, " 5783c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << "const void *Decoder, const MCSubtargetInfo &STI) {\n"; 5793c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << " unsigned tmp = 0;\n (void)tmp;\n" << Emitter->Locals << "\n"; 5803c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << " uint64_t Bits = STI.getFeatureBits();\n"; 5813c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5823c827367444ee418f129b2c238299f49d3264554Jarkko Poyry ++Indentation; ++Indentation; 5833c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Emits code to decode the instructions. 5843c827367444ee418f129b2c238299f49d3264554Jarkko Poyry emit(o, Indentation); 5853c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 58693df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry o << '\n'; 5873c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << "return " << Emitter->ReturnFail << ";\n"; 5883c827367444ee418f129b2c238299f49d3264554Jarkko Poyry --Indentation; --Indentation; 5893c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5903c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << "}\n"; 5913c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5923c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << '\n'; 5933c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 5943c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 5953c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Populates the field of the insn given the start position and the number of 5963c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// consecutive bits to scan for. 5973c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// 5983c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Returns false if and on the first uninitialized bit value encountered. 5993c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Returns true, otherwise. 6003c827367444ee418f129b2c238299f49d3264554Jarkko Poyrybool FilterChooser::fieldFromInsn(uint64_t &Field, insn_t &Insn, 6013c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned StartBit, unsigned NumBits) const { 6023c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Field = 0; 6033c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 6043c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (unsigned i = 0; i < NumBits; ++i) { 6053c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (Insn[StartBit + i] == BIT_UNSET) 6063c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return false; 6073c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 6083c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (Insn[StartBit + i] == BIT_TRUE) 6093c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Field = Field | (1ULL << i); 6103c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 6113c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 6123c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return true; 6133c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 6143c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 6153c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// dumpFilterArray - dumpFilterArray prints out debugging info for the given 6163c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// filter array as a series of chars. 6173c827367444ee418f129b2c238299f49d3264554Jarkko Poyryvoid FilterChooser::dumpFilterArray(raw_ostream &o, 6183c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<bit_value_t> &filter) { 6193c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned bitIndex; 62093df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry 6213c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (bitIndex = BitWidth; bitIndex > 0; bitIndex--) { 6223c827367444ee418f129b2c238299f49d3264554Jarkko Poyry switch (filter[bitIndex - 1]) { 6233c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case BIT_UNFILTERED: 6243c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << "."; 6253c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 6263c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case BIT_UNSET: 6273c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << "_"; 6283c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 6293c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case BIT_TRUE: 6303c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << "1"; 6313c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 6323c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case BIT_FALSE: 6333c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << "0"; 6343c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 6353c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 6363c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 6373c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 6383c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 6393c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// dumpStack - dumpStack traverses the filter chooser chain and calls 6403c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/// dumpFilterArray on each filter chooser up to the top level one. 6413c827367444ee418f129b2c238299f49d3264554Jarkko Poyryvoid FilterChooser::dumpStack(raw_ostream &o, const char *prefix) { 6423c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FilterChooser *current = this; 6433c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 6443c827367444ee418f129b2c238299f49d3264554Jarkko Poyry while (current) { 6453c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << prefix; 6463c827367444ee418f129b2c238299f49d3264554Jarkko Poyry dumpFilterArray(o, current->FilterBitValues); 6473c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << '\n'; 6483c827367444ee418f129b2c238299f49d3264554Jarkko Poyry current = current->Parent; 6493c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 6503c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 6513c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 6523c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Called from Filter::recurse() when singleton exists. For debug purpose. 6533c827367444ee418f129b2c238299f49d3264554Jarkko Poyryvoid FilterChooser::SingletonExists(unsigned Opc) { 6543c827367444ee418f129b2c238299f49d3264554Jarkko Poyry insn_t Insn0; 6553c827367444ee418f129b2c238299f49d3264554Jarkko Poyry insnWithID(Insn0, Opc); 6563c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 6573c827367444ee418f129b2c238299f49d3264554Jarkko Poyry errs() << "Singleton exists: " << nameWithID(Opc) 6583c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << " with its decoding dominating "; 6593c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (unsigned i = 0; i < Opcodes.size(); ++i) { 6603c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (Opcodes[i] == Opc) continue; 6613c827367444ee418f129b2c238299f49d3264554Jarkko Poyry errs() << nameWithID(Opcodes[i]) << ' '; 6623c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 6633c827367444ee418f129b2c238299f49d3264554Jarkko Poyry errs() << '\n'; 6643c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 6653c827367444ee418f129b2c238299f49d3264554Jarkko Poyry dumpStack(errs(), "\t\t"); 6663c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (unsigned i = 0; i < Opcodes.size(); i++) { 6673c827367444ee418f129b2c238299f49d3264554Jarkko Poyry const std::string &Name = nameWithID(Opcodes[i]); 6683c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 6693c827367444ee418f129b2c238299f49d3264554Jarkko Poyry errs() << '\t' << Name << " "; 6703c827367444ee418f129b2c238299f49d3264554Jarkko Poyry dumpBits(errs(), 67193df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry getBitsField(*AllInstructions[Opcodes[i]]->TheDef, "Inst")); 6723c827367444ee418f129b2c238299f49d3264554Jarkko Poyry errs() << '\n'; 6733c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 6743c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 6753c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 6763c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Calculates the island(s) needed to decode the instruction. 6773c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// This returns a list of undecoded bits of an instructions, for example, 6783c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be 6793c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// decoded bits in order to verify that the instruction matches the Opcode. 6803c827367444ee418f129b2c238299f49d3264554Jarkko Poyryunsigned FilterChooser::getIslands(std::vector<unsigned> &StartBits, 6813c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<unsigned> &EndBits, std::vector<uint64_t> &FieldVals, 6823c827367444ee418f129b2c238299f49d3264554Jarkko Poyry insn_t &Insn) { 6833c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned Num, BitNo; 6843c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Num = BitNo = 0; 6853c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 6863c827367444ee418f129b2c238299f49d3264554Jarkko Poyry uint64_t FieldVal = 0; 6873c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 6883c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // 0: Init 6893c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // 1: Water (the bit value does not affect decoding) 6903c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // 2: Island (well-known bit value needed for decoding) 6913c827367444ee418f129b2c238299f49d3264554Jarkko Poyry int State = 0; 6923c827367444ee418f129b2c238299f49d3264554Jarkko Poyry int Val = -1; 6933c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 6943c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (unsigned i = 0; i < BitWidth; ++i) { 6953c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Val = Value(Insn[i]); 6963c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bool Filtered = PositionFiltered(i); 6973c827367444ee418f129b2c238299f49d3264554Jarkko Poyry switch (State) { 6983c827367444ee418f129b2c238299f49d3264554Jarkko Poyry default: 6993c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(0 && "Unreachable code!"); 7003c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 7013c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case 0: 7023c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case 1: 7033c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (Filtered || Val == -1) 7043c827367444ee418f129b2c238299f49d3264554Jarkko Poyry State = 1; // Still in Water 7053c827367444ee418f129b2c238299f49d3264554Jarkko Poyry else { 7063c827367444ee418f129b2c238299f49d3264554Jarkko Poyry State = 2; // Into the Island 7073c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BitNo = 0; 7083c827367444ee418f129b2c238299f49d3264554Jarkko Poyry StartBits.push_back(i); 7093c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FieldVal = Val; 7103c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 7113c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 7123c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case 2: 7133c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (Filtered || Val == -1) { 7143c827367444ee418f129b2c238299f49d3264554Jarkko Poyry State = 1; // Into the Water 7153c827367444ee418f129b2c238299f49d3264554Jarkko Poyry EndBits.push_back(i - 1); 7163c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FieldVals.push_back(FieldVal); 7173c827367444ee418f129b2c238299f49d3264554Jarkko Poyry ++Num; 7183c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } else { 7193c827367444ee418f129b2c238299f49d3264554Jarkko Poyry State = 2; // Still in Island 7203c827367444ee418f129b2c238299f49d3264554Jarkko Poyry ++BitNo; 7213c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FieldVal = FieldVal | Val << BitNo; 7223c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 7233c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 7243c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 7253c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 72693df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry // If we are still in Island after the loop, do some housekeeping. 7273c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (State == 2) { 7283c827367444ee418f129b2c238299f49d3264554Jarkko Poyry EndBits.push_back(BitWidth - 1); 7293c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FieldVals.push_back(FieldVal); 7303c827367444ee418f129b2c238299f49d3264554Jarkko Poyry ++Num; 7313c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 7323c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 7333c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(StartBits.size() == Num && EndBits.size() == Num && 7343c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FieldVals.size() == Num); 7353c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return Num; 7363c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 7373c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 7383c827367444ee418f129b2c238299f49d3264554Jarkko Poyryvoid FilterChooser::emitBinaryParser(raw_ostream &o, unsigned &Indentation, 7393c827367444ee418f129b2c238299f49d3264554Jarkko Poyry OperandInfo &OpInfo) { 7403c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::string &Decoder = OpInfo.Decoder; 7413c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 7423c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (OpInfo.numFields() == 1) { 7433c827367444ee418f129b2c238299f49d3264554Jarkko Poyry OperandInfo::iterator OI = OpInfo.begin(); 7443c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << " tmp = fieldFromInstruction" << BitWidth 7453c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << "(insn, " << OI->Base << ", " << OI->Width 7463c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << ");\n"; 7473c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } else { 7483c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << " tmp = 0;\n"; 7493c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (OperandInfo::iterator OI = OpInfo.begin(), OE = OpInfo.end(); 7503c827367444ee418f129b2c238299f49d3264554Jarkko Poyry OI != OE; ++OI) { 7513c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << " tmp |= (fieldFromInstruction" << BitWidth 7523c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << "(insn, " << OI->Base << ", " << OI->Width 7533c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << ") << " << OI->Offset << ");\n"; 7543c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 7553c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 7563c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 7573c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (Decoder != "") 7583c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << " " << Emitter->GuardPrefix << Decoder 7593c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << "(MI, tmp, Address, Decoder)" << Emitter->GuardPostfix << "\n"; 7603c827367444ee418f129b2c238299f49d3264554Jarkko Poyry else 7613c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << " MI.addOperand(MCOperand::CreateImm(tmp));\n"; 7623c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 7633c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 7643c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 7653c827367444ee418f129b2c238299f49d3264554Jarkko Poyrystatic void emitSinglePredicateMatch(raw_ostream &o, StringRef str, 7663c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::string PredicateNamespace) { 76793df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry if (str[0] == '!') 7683c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << "!(Bits & " << PredicateNamespace << "::" 7693c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << str.slice(1,str.size()) << ")"; 7703c827367444ee418f129b2c238299f49d3264554Jarkko Poyry else 7713c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << "(Bits & " << PredicateNamespace << "::" << str << ")"; 7723c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 7733c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 7743c827367444ee418f129b2c238299f49d3264554Jarkko Poyrybool FilterChooser::emitPredicateMatch(raw_ostream &o, unsigned &Indentation, 7753c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned Opc) { 7763c827367444ee418f129b2c238299f49d3264554Jarkko Poyry ListInit *Predicates = AllInstructions[Opc]->TheDef->getValueAsListInit("Predicates"); 7773c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (unsigned i = 0; i < Predicates->getSize(); ++i) { 7783c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Record *Pred = Predicates->getElementAsRecord(i); 7793c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (!Pred->getValue("AssemblerMatcherPredicate")) 7803c827367444ee418f129b2c238299f49d3264554Jarkko Poyry continue; 7813c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 7823c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::string P = Pred->getValueAsString("AssemblerCondString"); 7833c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 7843c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (!P.length()) 7853c827367444ee418f129b2c238299f49d3264554Jarkko Poyry continue; 7863c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 7873c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (i != 0) 7883c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << " && "; 7893c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 7903c827367444ee418f129b2c238299f49d3264554Jarkko Poyry StringRef SR(P); 7913c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::pair<StringRef, StringRef> pairs = SR.split(','); 7923c827367444ee418f129b2c238299f49d3264554Jarkko Poyry while (pairs.second.size()) { 7933c827367444ee418f129b2c238299f49d3264554Jarkko Poyry emitSinglePredicateMatch(o, pairs.first, Emitter->PredicateNamespace); 7943c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << " && "; 7953c827367444ee418f129b2c238299f49d3264554Jarkko Poyry pairs = pairs.second.split(','); 7963c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 7973c827367444ee418f129b2c238299f49d3264554Jarkko Poyry emitSinglePredicateMatch(o, pairs.first, Emitter->PredicateNamespace); 7983c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 7993c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return Predicates->getSize() > 0; 8003c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 8013c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 8023c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Emits code to decode the singleton. Return true if we have matched all the 8033c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// well-known bits. 8043c827367444ee418f129b2c238299f49d3264554Jarkko Poyrybool FilterChooser::emitSingletonDecoder(raw_ostream &o, unsigned &Indentation, 8053c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned Opc) { 8063c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<unsigned> StartBits; 8073c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<unsigned> EndBits; 8083c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<uint64_t> FieldVals; 8093c827367444ee418f129b2c238299f49d3264554Jarkko Poyry insn_t Insn; 8103c827367444ee418f129b2c238299f49d3264554Jarkko Poyry insnWithID(Insn, Opc); 8113c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 8123c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Look for islands of undecoded bits of the singleton. 81393df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry getIslands(StartBits, EndBits, FieldVals, Insn); 8143c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 8153c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned Size = StartBits.size(); 8163c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned I, NumBits; 8173c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 8183c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // If we have matched all the well-known bits, just issue a return. 8193c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (Size == 0) { 8203c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << "if ("; 8213c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (!emitPredicateMatch(o, Indentation, Opc)) 8223c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << "1"; 8233c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << ") {\n"; 8243c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << " MI.setOpcode(" << Opc << ");\n"; 8253c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<OperandInfo>& InsnOperands = Operands[Opc]; 8263c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (std::vector<OperandInfo>::iterator 8273c827367444ee418f129b2c238299f49d3264554Jarkko Poyry I = InsnOperands.begin(), E = InsnOperands.end(); I != E; ++I) { 8283c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // If a custom instruction decoder was specified, use that. 8293c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (I->numFields() == 0 && I->Decoder.size()) { 8303c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << " " << Emitter->GuardPrefix << I->Decoder 8313c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << "(MI, insn, Address, Decoder)" << Emitter->GuardPostfix << "\n"; 8323c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 8333c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 8343c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 8353c827367444ee418f129b2c238299f49d3264554Jarkko Poyry emitBinaryParser(o, Indentation, *I); 8363c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 8373c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 8383c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << " return " << Emitter->ReturnOK << "; // " << nameWithID(Opc) 8393c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << '\n'; 8403c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << "}\n"; // Closing predicate block. 8413c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return true; 8423c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 84393df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry 8443c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Otherwise, there are more decodings to be done! 8453c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 8463c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Emit code to match the island(s) for the singleton. 8473c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << "// Check "; 8483c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 8493c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (I = Size; I != 0; --I) { 8503c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << "Inst{" << EndBits[I-1] << '-' << StartBits[I-1] << "} "; 8513c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (I > 1) 8523c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << " && "; 8533c827367444ee418f129b2c238299f49d3264554Jarkko Poyry else 8543c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << "for singleton decoding...\n"; 8553c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 8563c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 8573c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << "if ("; 8583c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (emitPredicateMatch(o, Indentation, Opc)) { 8593c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << " &&\n"; 8603c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation+4); 8613c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 8623c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 8633c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (I = Size; I != 0; --I) { 8643c827367444ee418f129b2c238299f49d3264554Jarkko Poyry NumBits = EndBits[I-1] - StartBits[I-1] + 1; 8653c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << "fieldFromInstruction" << BitWidth << "(insn, " 8663c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << StartBits[I-1] << ", " << NumBits 8673c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << ") == " << FieldVals[I-1]; 8683c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (I > 1) 8693c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << " && "; 8703c827367444ee418f129b2c238299f49d3264554Jarkko Poyry else 8713c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o << ") {\n"; 8723c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 8733c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << " MI.setOpcode(" << Opc << ");\n"; 8743c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<OperandInfo>& InsnOperands = Operands[Opc]; 8753c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (std::vector<OperandInfo>::iterator 8763c827367444ee418f129b2c238299f49d3264554Jarkko Poyry I = InsnOperands.begin(), E = InsnOperands.end(); I != E; ++I) { 8773c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // If a custom instruction decoder was specified, use that. 8783c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (I->numFields() == 0 && I->Decoder.size()) { 87993df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry o.indent(Indentation) << " " << Emitter->GuardPrefix << I->Decoder 8803c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << "(MI, insn, Address, Decoder)" << Emitter->GuardPostfix << "\n"; 8813c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 8823c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 8833c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 8843c827367444ee418f129b2c238299f49d3264554Jarkko Poyry emitBinaryParser(o, Indentation, *I); 8853c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 8863c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << " return " << Emitter->ReturnOK << "; // " << nameWithID(Opc) 8873c827367444ee418f129b2c238299f49d3264554Jarkko Poyry << '\n'; 8883c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << "}\n"; 8893c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 8903c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return false; 8913c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 8923c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 8933c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Emits code to decode the singleton, and then to decode the rest. 8943c827367444ee418f129b2c238299f49d3264554Jarkko Poyryvoid FilterChooser::emitSingletonDecoder(raw_ostream &o, unsigned &Indentation, 8953c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Filter &Best) { 8963c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 8973c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned Opc = Best.getSingletonOpc(); 8983c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 8993c827367444ee418f129b2c238299f49d3264554Jarkko Poyry emitSingletonDecoder(o, Indentation, Opc); 9003c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 9013c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Emit code for the rest. 9023c827367444ee418f129b2c238299f49d3264554Jarkko Poyry o.indent(Indentation) << "else\n"; 9033c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 9043c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Indentation += 2; 9053c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Best.getVariableFC().emit(o, Indentation); 9063c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Indentation -= 2; 9073c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 9083c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 9093c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Assign a single filter and run with it. Top level API client can initialize 9103c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// with a single filter to start the filtering process. 9113c827367444ee418f129b2c238299f49d3264554Jarkko Poyryvoid FilterChooser::runSingleFilter(FilterChooser &owner, unsigned startBit, 9123c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned numBit, bool mixed) { 9133c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Filters.clear(); 9143c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Filter F(*this, startBit, numBit, true); 9153c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Filters.push_back(F); 9163c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BestIndex = 0; // Sole Filter instance to choose from. 9173c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bestFilter().recurse(); 9183c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 9193c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 9203c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// reportRegion is a helper function for filterProcessor to mark a region as 9213c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// eligible for use as a filter region. 9223c827367444ee418f129b2c238299f49d3264554Jarkko Poyryvoid FilterChooser::reportRegion(bitAttr_t RA, unsigned StartBit, 9233c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned BitIndex, bool AllowMixed) { 9243c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (RA == ATTR_MIXED && AllowMixed) 9253c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Filters.push_back(Filter(*this, StartBit, BitIndex - StartBit, true)); 9263c827367444ee418f129b2c238299f49d3264554Jarkko Poyry else if (RA == ATTR_ALL_SET && !AllowMixed) 9273c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Filters.push_back(Filter(*this, StartBit, BitIndex - StartBit, false)); 9283c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 9293c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 9303c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// FilterProcessor scans the well-known encoding bits of the instructions and 9313c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// builds up a list of candidate filters. It chooses the best filter and 9323c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// recursively descends down the decoding tree. 9333c827367444ee418f129b2c238299f49d3264554Jarkko Poyrybool FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { 9343c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Filters.clear(); 9353c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BestIndex = -1; 9363c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned numInstructions = Opcodes.size(); 9373c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 9383c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(numInstructions && "Filter created with no instructions"); 9393c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 94093df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry // No further filtering is necessary. 9413c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (numInstructions == 1) 9423c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return true; 9433c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 9443c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Heuristics. See also doFilter()'s "Heuristics" comment when num of 9453c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // instructions is 3. 9463c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (AllowMixed && !Greedy) { 9473c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(numInstructions == 3); 9483c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 9493c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (unsigned i = 0; i < Opcodes.size(); ++i) { 9503c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<unsigned> StartBits; 9513c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<unsigned> EndBits; 9523c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<uint64_t> FieldVals; 9533c827367444ee418f129b2c238299f49d3264554Jarkko Poyry insn_t Insn; 9543c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 9553c827367444ee418f129b2c238299f49d3264554Jarkko Poyry insnWithID(Insn, Opcodes[i]); 9563c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 9573c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Look for islands of undecoded bits of any instruction. 9583c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (getIslands(StartBits, EndBits, FieldVals, Insn) > 0) { 9593c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Found an instruction with island(s). Now just assign a filter. 9603c827367444ee418f129b2c238299f49d3264554Jarkko Poyry runSingleFilter(*this, StartBits[0], EndBits[0] - StartBits[0] + 1, 9613c827367444ee418f129b2c238299f49d3264554Jarkko Poyry true); 9623c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return true; 9633c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 9643c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 9653c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 9663c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 9673c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned BitIndex, InsnIndex; 9683c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 9693c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // We maintain BIT_WIDTH copies of the bitAttrs automaton. 9703c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // The automaton consumes the corresponding bit from each 9713c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // instruction. 9723c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // 9733c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Input symbols: 0, 1, and _ (unset). 9743c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // States: NONE, FILTERED, ALL_SET, ALL_UNSET, and MIXED. 9753c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Initial state: NONE. 9763c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // 9773c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (NONE) ------- [01] -> (ALL_SET) 9783c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (NONE) ------- _ ----> (ALL_UNSET) 9793c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (ALL_SET) ---- [01] -> (ALL_SET) 9803c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (ALL_SET) ---- _ ----> (MIXED) 9813c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (ALL_UNSET) -- [01] -> (MIXED) 9823c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (ALL_UNSET) -- _ ----> (ALL_UNSET) 9833c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (MIXED) ------ . ----> (MIXED) 9843c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (FILTERED)---- . ----> (FILTERED) 9853c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 9863c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::vector<bitAttr_t> bitAttrs; 9873c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 9883c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // FILTERED bit positions provide no entropy and are not worthy of pursuing. 9893c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Filter::recurse() set either BIT_TRUE or BIT_FALSE for each position. 9903c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) 9913c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (FilterBitValues[BitIndex] == BIT_TRUE || 9923c827367444ee418f129b2c238299f49d3264554Jarkko Poyry FilterBitValues[BitIndex] == BIT_FALSE) 99393df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry bitAttrs.push_back(ATTR_FILTERED); 9943c827367444ee418f129b2c238299f49d3264554Jarkko Poyry else 9953c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bitAttrs.push_back(ATTR_NONE); 9963c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 9973c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (InsnIndex = 0; InsnIndex < numInstructions; ++InsnIndex) { 9983c827367444ee418f129b2c238299f49d3264554Jarkko Poyry insn_t insn; 9993c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 10003c827367444ee418f129b2c238299f49d3264554Jarkko Poyry insnWithID(insn, Opcodes[InsnIndex]); 10013c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 10023c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (BitIndex = 0; BitIndex < BitWidth; ++BitIndex) { 10033c827367444ee418f129b2c238299f49d3264554Jarkko Poyry switch (bitAttrs[BitIndex]) { 10043c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_NONE: 10053c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (insn[BitIndex] == BIT_UNSET) 10063c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bitAttrs[BitIndex] = ATTR_ALL_UNSET; 10073c827367444ee418f129b2c238299f49d3264554Jarkko Poyry else 10083c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bitAttrs[BitIndex] = ATTR_ALL_SET; 10093c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 10103c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_ALL_SET: 10113c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (insn[BitIndex] == BIT_UNSET) 10123c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bitAttrs[BitIndex] = ATTR_MIXED; 10133c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 10143c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_ALL_UNSET: 10153c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (insn[BitIndex] != BIT_UNSET) 10163c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bitAttrs[BitIndex] = ATTR_MIXED; 10173c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 10183c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_MIXED: 10193c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_FILTERED: 10203c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 10213c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 10223c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 10233c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 10243c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 10253c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // The regionAttr automaton consumes the bitAttrs automatons' state, 10263c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // lowest-to-highest. 10273c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // 10283c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Input symbols: F(iltered), (all_)S(et), (all_)U(nset), M(ixed) 10293c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // States: NONE, ALL_SET, MIXED 10303c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Initial state: NONE 10313c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // 10323c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (NONE) ----- F --> (NONE) 10333c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (NONE) ----- S --> (ALL_SET) ; and set region start 10343c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (NONE) ----- U --> (NONE) 10353c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (NONE) ----- M --> (MIXED) ; and set region start 10363c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (ALL_SET) -- F --> (NONE) ; and report an ALL_SET region 10373c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (ALL_SET) -- S --> (ALL_SET) 10383c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (ALL_SET) -- U --> (NONE) ; and report an ALL_SET region 103993df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry // (ALL_SET) -- M --> (MIXED) ; and report an ALL_SET region 10403c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (MIXED) ---- F --> (NONE) ; and report a MIXED region 10413c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (MIXED) ---- S --> (ALL_SET) ; and report a MIXED region 10423c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (MIXED) ---- U --> (NONE) ; and report a MIXED region 10433c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // (MIXED) ---- M --> (MIXED) 10443c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 10453c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bitAttr_t RA = ATTR_NONE; 10463c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned StartBit = 0; 10473c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 10483c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (BitIndex = 0; BitIndex < BitWidth; BitIndex++) { 10493c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bitAttr_t bitAttr = bitAttrs[BitIndex]; 10503c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 10513c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(bitAttr != ATTR_NONE && "Bit without attributes"); 10523c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 10533c827367444ee418f129b2c238299f49d3264554Jarkko Poyry switch (RA) { 10543c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_NONE: 10553c827367444ee418f129b2c238299f49d3264554Jarkko Poyry switch (bitAttr) { 10563c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_FILTERED: 10573c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 10583c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_ALL_SET: 10598852c82a1ffa4760985c17cc6875d5d521daf343Jarkko Poyry StartBit = BitIndex; 10608852c82a1ffa4760985c17cc6875d5d521daf343Jarkko Poyry RA = ATTR_ALL_SET; 10618852c82a1ffa4760985c17cc6875d5d521daf343Jarkko Poyry break; 10623c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_ALL_UNSET: 10633c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 10643c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_MIXED: 10653c827367444ee418f129b2c238299f49d3264554Jarkko Poyry StartBit = BitIndex; 10663c827367444ee418f129b2c238299f49d3264554Jarkko Poyry RA = ATTR_MIXED; 10673c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 10683c827367444ee418f129b2c238299f49d3264554Jarkko Poyry default: 10693c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(0 && "Unexpected bitAttr!"); 10703c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 10713c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 10728852c82a1ffa4760985c17cc6875d5d521daf343Jarkko Poyry case ATTR_ALL_SET: 10733c827367444ee418f129b2c238299f49d3264554Jarkko Poyry switch (bitAttr) { 10743c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_FILTERED: 10753c827367444ee418f129b2c238299f49d3264554Jarkko Poyry reportRegion(RA, StartBit, BitIndex, AllowMixed); 107693df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry RA = ATTR_NONE; 10773c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 10783c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_ALL_SET: 10793c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 10803c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_ALL_UNSET: 10813c827367444ee418f129b2c238299f49d3264554Jarkko Poyry reportRegion(RA, StartBit, BitIndex, AllowMixed); 10823c827367444ee418f129b2c238299f49d3264554Jarkko Poyry RA = ATTR_NONE; 10833c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 10848852c82a1ffa4760985c17cc6875d5d521daf343Jarkko Poyry case ATTR_MIXED: 10853c827367444ee418f129b2c238299f49d3264554Jarkko Poyry reportRegion(RA, StartBit, BitIndex, AllowMixed); 10863c827367444ee418f129b2c238299f49d3264554Jarkko Poyry StartBit = BitIndex; 10873c827367444ee418f129b2c238299f49d3264554Jarkko Poyry RA = ATTR_MIXED; 10888852c82a1ffa4760985c17cc6875d5d521daf343Jarkko Poyry break; 10898852c82a1ffa4760985c17cc6875d5d521daf343Jarkko Poyry default: 10903c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(0 && "Unexpected bitAttr!"); 10913c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 10923c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 10933c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_MIXED: 10943c827367444ee418f129b2c238299f49d3264554Jarkko Poyry switch (bitAttr) { 10953c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_FILTERED: 10963c827367444ee418f129b2c238299f49d3264554Jarkko Poyry reportRegion(RA, StartBit, BitIndex, AllowMixed); 10973c827367444ee418f129b2c238299f49d3264554Jarkko Poyry StartBit = BitIndex; 10983c827367444ee418f129b2c238299f49d3264554Jarkko Poyry RA = ATTR_NONE; 10993c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 11003c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_ALL_SET: 11013c827367444ee418f129b2c238299f49d3264554Jarkko Poyry reportRegion(RA, StartBit, BitIndex, AllowMixed); 11023c827367444ee418f129b2c238299f49d3264554Jarkko Poyry StartBit = BitIndex; 11033c827367444ee418f129b2c238299f49d3264554Jarkko Poyry RA = ATTR_ALL_SET; 11043c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 11053c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_ALL_UNSET: 11063c827367444ee418f129b2c238299f49d3264554Jarkko Poyry reportRegion(RA, StartBit, BitIndex, AllowMixed); 11073c827367444ee418f129b2c238299f49d3264554Jarkko Poyry RA = ATTR_NONE; 11083c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 11093c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_MIXED: 11108852c82a1ffa4760985c17cc6875d5d521daf343Jarkko Poyry break; 11113c827367444ee418f129b2c238299f49d3264554Jarkko Poyry default: 111293df37596ea66700965094b3aa2830cf4f2ca5aaJarkko Pöyry assert(0 && "Unexpected bitAttr!"); 11133c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 11143c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 11153c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_ALL_UNSET: 11163c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(0 && "regionAttr state machine has no ATTR_UNSET state"); 11173c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_FILTERED: 11183c827367444ee418f129b2c238299f49d3264554Jarkko Poyry assert(0 && "regionAttr state machine has no ATTR_FILTERED state"); 11193c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 11203c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 11213c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 11223c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // At the end, if we're still in ALL_SET or MIXED states, report a region 11233c827367444ee418f129b2c238299f49d3264554Jarkko Poyry switch (RA) { 11243c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_NONE: 11253c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 11263c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_FILTERED: 11273c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 11283c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_ALL_SET: 11293c827367444ee418f129b2c238299f49d3264554Jarkko Poyry reportRegion(RA, StartBit, BitIndex, AllowMixed); 11303c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 11313c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_ALL_UNSET: 11323c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 11333c827367444ee418f129b2c238299f49d3264554Jarkko Poyry case ATTR_MIXED: 11343c827367444ee418f129b2c238299f49d3264554Jarkko Poyry reportRegion(RA, StartBit, BitIndex, AllowMixed); 11353c827367444ee418f129b2c238299f49d3264554Jarkko Poyry break; 11363c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 11373c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 11383c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // We have finished with the filter processings. Now it's time to choose 11393c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // the best performing filter. 11403c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BestIndex = 0; 11413c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bool AllUseless = true; 11423c827367444ee418f129b2c238299f49d3264554Jarkko Poyry unsigned BestScore = 0; 11433c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1144 for (unsigned i = 0, e = Filters.size(); i != e; ++i) { 1145 unsigned Usefulness = Filters[i].usefulness(); 1146 1147 if (Usefulness) 1148 AllUseless = false; 1149 1150 if (Usefulness > BestScore) { 1151 BestIndex = i; 1152 BestScore = Usefulness; 1153 } 1154 } 1155 1156 if (!AllUseless) 1157 bestFilter().recurse(); 1158 1159 return !AllUseless; 1160} // end of FilterChooser::filterProcessor(bool) 1161 1162// Decides on the best configuration of filter(s) to use in order to decode 1163// the instructions. A conflict of instructions may occur, in which case we 1164// dump the conflict set to the standard error. 1165void FilterChooser::doFilter() { 1166 unsigned Num = Opcodes.size(); 1167 assert(Num && "FilterChooser created with no instructions"); 1168 1169 // Try regions of consecutive known bit values first. 1170 if (filterProcessor(false)) 1171 return; 1172 1173 // Then regions of mixed bits (both known and unitialized bit values allowed). 1174 if (filterProcessor(true)) 1175 return; 1176 1177 // Heuristics to cope with conflict set {t2CMPrs, t2SUBSrr, t2SUBSrs} where 1178 // no single instruction for the maximum ATTR_MIXED region Inst{14-4} has a 1179 // well-known encoding pattern. In such case, we backtrack and scan for the 1180 // the very first consecutive ATTR_ALL_SET region and assign a filter to it. 1181 if (Num == 3 && filterProcessor(true, false)) 1182 return; 1183 1184 // If we come to here, the instruction decoding has failed. 1185 // Set the BestIndex to -1 to indicate so. 1186 BestIndex = -1; 1187} 1188 1189// Emits code to decode our share of instructions. Returns true if the 1190// emitted code causes a return, which occurs if we know how to decode 1191// the instruction at this level or the instruction is not decodeable. 1192bool FilterChooser::emit(raw_ostream &o, unsigned &Indentation) { 1193 if (Opcodes.size() == 1) 1194 // There is only one instruction in the set, which is great! 1195 // Call emitSingletonDecoder() to see whether there are any remaining 1196 // encodings bits. 1197 return emitSingletonDecoder(o, Indentation, Opcodes[0]); 1198 1199 // Choose the best filter to do the decodings! 1200 if (BestIndex != -1) { 1201 Filter &Best = bestFilter(); 1202 if (Best.getNumFiltered() == 1) 1203 emitSingletonDecoder(o, Indentation, Best); 1204 else 1205 bestFilter().emit(o, Indentation); 1206 return false; 1207 } 1208 1209 // We don't know how to decode these instructions! Return 0 and dump the 1210 // conflict set! 1211 o.indent(Indentation) << "return 0;" << " // Conflict set: "; 1212 for (int i = 0, N = Opcodes.size(); i < N; ++i) { 1213 o << nameWithID(Opcodes[i]); 1214 if (i < (N - 1)) 1215 o << ", "; 1216 else 1217 o << '\n'; 1218 } 1219 1220 // Print out useful conflict information for postmortem analysis. 1221 errs() << "Decoding Conflict:\n"; 1222 1223 dumpStack(errs(), "\t\t"); 1224 1225 for (unsigned i = 0; i < Opcodes.size(); i++) { 1226 const std::string &Name = nameWithID(Opcodes[i]); 1227 1228 errs() << '\t' << Name << " "; 1229 dumpBits(errs(), 1230 getBitsField(*AllInstructions[Opcodes[i]]->TheDef, "Inst")); 1231 errs() << '\n'; 1232 } 1233 1234 return true; 1235} 1236 1237static bool populateInstruction(const CodeGenInstruction &CGI, 1238 unsigned Opc, 1239 std::map<unsigned, std::vector<OperandInfo> >& Operands){ 1240 const Record &Def = *CGI.TheDef; 1241 // If all the bit positions are not specified; do not decode this instruction. 1242 // We are bound to fail! For proper disassembly, the well-known encoding bits 1243 // of the instruction must be fully specified. 1244 // 1245 // This also removes pseudo instructions from considerations of disassembly, 1246 // which is a better design and less fragile than the name matchings. 1247 // Ignore "asm parser only" instructions. 1248 if (Def.getValueAsBit("isAsmParserOnly") || 1249 Def.getValueAsBit("isCodeGenOnly")) 1250 return false; 1251 1252 BitsInit &Bits = getBitsField(Def, "Inst"); 1253 if (Bits.allInComplete()) return false; 1254 1255 std::vector<OperandInfo> InsnOperands; 1256 1257 // If the instruction has specified a custom decoding hook, use that instead 1258 // of trying to auto-generate the decoder. 1259 std::string InstDecoder = Def.getValueAsString("DecoderMethod"); 1260 if (InstDecoder != "") { 1261 InsnOperands.push_back(OperandInfo(InstDecoder)); 1262 Operands[Opc] = InsnOperands; 1263 return true; 1264 } 1265 1266 // Generate a description of the operand of the instruction that we know 1267 // how to decode automatically. 1268 // FIXME: We'll need to have a way to manually override this as needed. 1269 1270 // Gather the outputs/inputs of the instruction, so we can find their 1271 // positions in the encoding. This assumes for now that they appear in the 1272 // MCInst in the order that they're listed. 1273 std::vector<std::pair<Init*, std::string> > InOutOperands; 1274 DagInit *Out = Def.getValueAsDag("OutOperandList"); 1275 DagInit *In = Def.getValueAsDag("InOperandList"); 1276 for (unsigned i = 0; i < Out->getNumArgs(); ++i) 1277 InOutOperands.push_back(std::make_pair(Out->getArg(i), Out->getArgName(i))); 1278 for (unsigned i = 0; i < In->getNumArgs(); ++i) 1279 InOutOperands.push_back(std::make_pair(In->getArg(i), In->getArgName(i))); 1280 1281 // Search for tied operands, so that we can correctly instantiate 1282 // operands that are not explicitly represented in the encoding. 1283 std::map<std::string, std::string> TiedNames; 1284 for (unsigned i = 0; i < CGI.Operands.size(); ++i) { 1285 int tiedTo = CGI.Operands[i].getTiedRegister(); 1286 if (tiedTo != -1) { 1287 TiedNames[InOutOperands[i].second] = InOutOperands[tiedTo].second; 1288 TiedNames[InOutOperands[tiedTo].second] = InOutOperands[i].second; 1289 } 1290 } 1291 1292 // For each operand, see if we can figure out where it is encoded. 1293 for (std::vector<std::pair<Init*, std::string> >::iterator 1294 NI = InOutOperands.begin(), NE = InOutOperands.end(); NI != NE; ++NI) { 1295 std::string Decoder = ""; 1296 1297 // At this point, we can locate the field, but we need to know how to 1298 // interpret it. As a first step, require the target to provide callbacks 1299 // for decoding register classes. 1300 // FIXME: This need to be extended to handle instructions with custom 1301 // decoder methods, and operands with (simple) MIOperandInfo's. 1302 TypedInit *TI = dynamic_cast<TypedInit*>(NI->first); 1303 RecordRecTy *Type = dynamic_cast<RecordRecTy*>(TI->getType()); 1304 Record *TypeRecord = Type->getRecord(); 1305 bool isReg = false; 1306 if (TypeRecord->isSubClassOf("RegisterOperand")) 1307 TypeRecord = TypeRecord->getValueAsDef("RegClass"); 1308 if (TypeRecord->isSubClassOf("RegisterClass")) { 1309 Decoder = "Decode" + TypeRecord->getName() + "RegisterClass"; 1310 isReg = true; 1311 } 1312 1313 RecordVal *DecoderString = TypeRecord->getValue("DecoderMethod"); 1314 StringInit *String = DecoderString ? 1315 dynamic_cast<StringInit*>(DecoderString->getValue()) : 0; 1316 if (!isReg && String && String->getValue() != "") 1317 Decoder = String->getValue(); 1318 1319 OperandInfo OpInfo(Decoder); 1320 unsigned Base = ~0U; 1321 unsigned Width = 0; 1322 unsigned Offset = 0; 1323 1324 for (unsigned bi = 0; bi < Bits.getNumBits(); ++bi) { 1325 VarInit *Var = 0; 1326 VarBitInit *BI = dynamic_cast<VarBitInit*>(Bits.getBit(bi)); 1327 if (BI) 1328 Var = dynamic_cast<VarInit*>(BI->getVariable()); 1329 else 1330 Var = dynamic_cast<VarInit*>(Bits.getBit(bi)); 1331 1332 if (!Var) { 1333 if (Base != ~0U) { 1334 OpInfo.addField(Base, Width, Offset); 1335 Base = ~0U; 1336 Width = 0; 1337 Offset = 0; 1338 } 1339 continue; 1340 } 1341 1342 if (Var->getName() != NI->second && 1343 Var->getName() != TiedNames[NI->second]) { 1344 if (Base != ~0U) { 1345 OpInfo.addField(Base, Width, Offset); 1346 Base = ~0U; 1347 Width = 0; 1348 Offset = 0; 1349 } 1350 continue; 1351 } 1352 1353 if (Base == ~0U) { 1354 Base = bi; 1355 Width = 1; 1356 Offset = BI ? BI->getBitNum() : 0; 1357 } else if (BI && BI->getBitNum() != Offset + Width) { 1358 OpInfo.addField(Base, Width, Offset); 1359 Base = bi; 1360 Width = 1; 1361 Offset = BI->getBitNum(); 1362 } else { 1363 ++Width; 1364 } 1365 } 1366 1367 if (Base != ~0U) 1368 OpInfo.addField(Base, Width, Offset); 1369 1370 if (OpInfo.numFields() > 0) 1371 InsnOperands.push_back(OpInfo); 1372 } 1373 1374 Operands[Opc] = InsnOperands; 1375 1376 1377#if 0 1378 DEBUG({ 1379 // Dumps the instruction encoding bits. 1380 dumpBits(errs(), Bits); 1381 1382 errs() << '\n'; 1383 1384 // Dumps the list of operand info. 1385 for (unsigned i = 0, e = CGI.Operands.size(); i != e; ++i) { 1386 const CGIOperandList::OperandInfo &Info = CGI.Operands[i]; 1387 const std::string &OperandName = Info.Name; 1388 const Record &OperandDef = *Info.Rec; 1389 1390 errs() << "\t" << OperandName << " (" << OperandDef.getName() << ")\n"; 1391 } 1392 }); 1393#endif 1394 1395 return true; 1396} 1397 1398static void emitHelper(llvm::raw_ostream &o, unsigned BitWidth) { 1399 unsigned Indentation = 0; 1400 std::string WidthStr = "uint" + utostr(BitWidth) + "_t"; 1401 1402 o << '\n'; 1403 1404 o.indent(Indentation) << "static " << WidthStr << 1405 " fieldFromInstruction" << BitWidth << 1406 "(" << WidthStr <<" insn, unsigned startBit, unsigned numBits)\n"; 1407 1408 o.indent(Indentation) << "{\n"; 1409 1410 ++Indentation; ++Indentation; 1411 o.indent(Indentation) << "assert(startBit + numBits <= " << BitWidth 1412 << " && \"Instruction field out of bounds!\");\n"; 1413 o << '\n'; 1414 o.indent(Indentation) << WidthStr << " fieldMask;\n"; 1415 o << '\n'; 1416 o.indent(Indentation) << "if (numBits == " << BitWidth << ")\n"; 1417 1418 ++Indentation; ++Indentation; 1419 o.indent(Indentation) << "fieldMask = (" << WidthStr << ")-1;\n"; 1420 --Indentation; --Indentation; 1421 1422 o.indent(Indentation) << "else\n"; 1423 1424 ++Indentation; ++Indentation; 1425 o.indent(Indentation) << "fieldMask = ((1 << numBits) - 1) << startBit;\n"; 1426 --Indentation; --Indentation; 1427 1428 o << '\n'; 1429 o.indent(Indentation) << "return (insn & fieldMask) >> startBit;\n"; 1430 --Indentation; --Indentation; 1431 1432 o.indent(Indentation) << "}\n"; 1433 1434 o << '\n'; 1435} 1436 1437// Emits disassembler code for instruction decoding. 1438void FixedLenDecoderEmitter::run(raw_ostream &o) 1439{ 1440 o << "#include \"llvm/MC/MCInst.h\"\n"; 1441 o << "#include \"llvm/Support/DataTypes.h\"\n"; 1442 o << "#include <assert.h>\n"; 1443 o << '\n'; 1444 o << "namespace llvm {\n\n"; 1445 1446 // Parameterize the decoders based on namespace and instruction width. 1447 NumberedInstructions = Target.getInstructionsByEnumValue(); 1448 std::map<std::pair<std::string, unsigned>, 1449 std::vector<unsigned> > OpcMap; 1450 std::map<unsigned, std::vector<OperandInfo> > Operands; 1451 1452 for (unsigned i = 0; i < NumberedInstructions.size(); ++i) { 1453 const CodeGenInstruction *Inst = NumberedInstructions[i]; 1454 Record *Def = Inst->TheDef; 1455 unsigned Size = Def->getValueAsInt("Size"); 1456 if (Def->getValueAsString("Namespace") == "TargetOpcode" || 1457 Def->getValueAsBit("isPseudo") || 1458 Def->getValueAsBit("isAsmParserOnly") || 1459 Def->getValueAsBit("isCodeGenOnly")) 1460 continue; 1461 1462 std::string DecoderNamespace = Def->getValueAsString("DecoderNamespace"); 1463 1464 if (Size) { 1465 if (populateInstruction(*Inst, i, Operands)) { 1466 OpcMap[std::make_pair(DecoderNamespace, Size)].push_back(i); 1467 } 1468 } 1469 } 1470 1471 std::set<unsigned> Sizes; 1472 for (std::map<std::pair<std::string, unsigned>, 1473 std::vector<unsigned> >::iterator 1474 I = OpcMap.begin(), E = OpcMap.end(); I != E; ++I) { 1475 // If we haven't visited this instruction width before, emit the 1476 // helper method to extract fields. 1477 if (!Sizes.count(I->first.second)) { 1478 emitHelper(o, 8*I->first.second); 1479 Sizes.insert(I->first.second); 1480 } 1481 1482 // Emit the decoder for this namespace+width combination. 1483 FilterChooser FC(NumberedInstructions, I->second, Operands, 1484 8*I->first.second, this); 1485 FC.emitTop(o, 0, I->first.first); 1486 } 1487 1488 o << "\n} // End llvm namespace \n"; 1489} 1490