Second try of initial ARM/Thumb disassembler check-in. It consists of a tablgen

backend (ARMDecoderEmitter) which emits the decoder functions for ARM and Thumb,
and the disassembler core which invokes the decoder function and builds up the
MCInst based on the decoded Opcode.

Reviewed by Chris Latter and Bob Wilson.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@100233 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 1861 insertions, 0 deletions

diff --git a/utils/TableGen/ARMDecoderEmitter.cpp b/utils/TableGen/ARMDecoderEmitter.cpp
new file mode 100644
index 0000000000..0c9ef44596
--- /dev/null
+++ b/utils/TableGen/ARMDecoderEmitter.cpp
@@ -0,0 +1,1861 @@
+//===------------ ARMDecoderEmitter.cpp - Decoder Generator ---------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is part of the ARM Disassembler.
+// It contains the tablegen backend that emits the decoder functions for ARM and
+// Thumb.  The disassembler core includes the auto-generated file, invokes the
+// decoder functions, and builds up the MCInst based on the decoded Opcode.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "arm-decoder-emitter"
+
+#include "ARMDecoderEmitter.h"
+#include "CodeGenTarget.h"
+#include "Record.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <vector>
+#include <map>
+#include <string>
+
+using namespace llvm;
+
+/////////////////////////////////////////////////////
+//                                                 //
+//  Enums and Utilities for ARM Instruction Format //
+//                                                 //
+/////////////////////////////////////////////////////
+
+#define ARM_FORMATS                   \
+  ENTRY(ARM_FORMAT_PSEUDO,         0) \
+  ENTRY(ARM_FORMAT_MULFRM,         1) \
+  ENTRY(ARM_FORMAT_BRFRM,          2) \
+  ENTRY(ARM_FORMAT_BRMISCFRM,      3) \
+  ENTRY(ARM_FORMAT_DPFRM,          4) \
+  ENTRY(ARM_FORMAT_DPSOREGFRM,     5) \
+  ENTRY(ARM_FORMAT_LDFRM,          6) \
+  ENTRY(ARM_FORMAT_STFRM,          7) \
+  ENTRY(ARM_FORMAT_LDMISCFRM,      8) \
+  ENTRY(ARM_FORMAT_STMISCFRM,      9) \
+  ENTRY(ARM_FORMAT_LDSTMULFRM,    10) \
+  ENTRY(ARM_FORMAT_LDSTEXFRM,     11) \
+  ENTRY(ARM_FORMAT_ARITHMISCFRM,  12) \
+  ENTRY(ARM_FORMAT_EXTFRM,        13) \
+  ENTRY(ARM_FORMAT_VFPUNARYFRM,   14) \
+  ENTRY(ARM_FORMAT_VFPBINARYFRM,  15) \
+  ENTRY(ARM_FORMAT_VFPCONV1FRM,   16) \
+  ENTRY(ARM_FORMAT_VFPCONV2FRM,   17) \
+  ENTRY(ARM_FORMAT_VFPCONV3FRM,   18) \
+  ENTRY(ARM_FORMAT_VFPCONV4FRM,   19) \
+  ENTRY(ARM_FORMAT_VFPCONV5FRM,   20) \
+  ENTRY(ARM_FORMAT_VFPLDSTFRM,    21) \
+  ENTRY(ARM_FORMAT_VFPLDSTMULFRM, 22) \
+  ENTRY(ARM_FORMAT_VFPMISCFRM,    23) \
+  ENTRY(ARM_FORMAT_THUMBFRM,      24) \
+  ENTRY(ARM_FORMAT_NEONFRM,       25) \
+  ENTRY(ARM_FORMAT_NEONGETLNFRM,  26) \
+  ENTRY(ARM_FORMAT_NEONSETLNFRM,  27) \
+  ENTRY(ARM_FORMAT_NEONDUPFRM,    28) \
+  ENTRY(ARM_FORMAT_MISCFRM,       29) \
+  ENTRY(ARM_FORMAT_THUMBMISCFRM,  30) \
+  ENTRY(ARM_FORMAT_NLdSt,         31) \
+  ENTRY(ARM_FORMAT_N1RegModImm,   32) \
+  ENTRY(ARM_FORMAT_N2Reg,         33) \
+  ENTRY(ARM_FORMAT_NVCVT,         34) \
+  ENTRY(ARM_FORMAT_NVecDupLn,     35) \
+  ENTRY(ARM_FORMAT_N2RegVecShL,   36) \
+  ENTRY(ARM_FORMAT_N2RegVecShR,   37) \
+  ENTRY(ARM_FORMAT_N3Reg,         38) \
+  ENTRY(ARM_FORMAT_N3RegVecSh,    39) \
+  ENTRY(ARM_FORMAT_NVecExtract,   40) \
+  ENTRY(ARM_FORMAT_NVecMulScalar, 41) \
+  ENTRY(ARM_FORMAT_NVTBL,         42)
+
+// ARM instruction format specifies the encoding used by the instruction.
+#define ENTRY(n, v) n = v,
+typedef enum {
+  ARM_FORMATS
+  ARM_FORMAT_NA
+} ARMFormat;
+#undef ENTRY
+
+// Converts enum to const char*.
+static const char *stringForARMFormat(ARMFormat form) {
+#define ENTRY(n, v) case n: return #n;
+  switch(form) {
+    ARM_FORMATS
+  case ARM_FORMAT_NA:
+  default:
+    return "";
+  }
+#undef ENTRY
+}
+
+typedef enum {
+  IndexModeNone = 0,
+  IndexModePre  = 1,
+  IndexModePost = 2,
+  IndexModeUpd  = 3
+};
+
+/////////////////////////
+//                     //
+//  Utility functions  //
+//                     //
+/////////////////////////
+
+/// byteFromBitsInit - Return the byte value from a BitsInit.
+/// Called from getByteField().
+static uint8_t byteFromBitsInit(BitsInit &init) {
+  int width = init.getNumBits();
+
+  assert(width <= 8 && "Field is too large for uint8_t!");
+
+  int index;
+  uint8_t mask = 0x01;
+
+  uint8_t ret = 0;
+
+  for (index = 0; index < width; index++) {
+    if (static_cast<BitInit*>(init.getBit(index))->getValue())
+      ret |= mask;
+
+    mask <<= 1;
+  }
+
+  return ret;
+}
+
+static uint8_t getByteField(const Record &def, const char *str) {
+  BitsInit *bits = def.getValueAsBitsInit(str);
+  return byteFromBitsInit(*bits);
+}
+
+static BitsInit &getBitsField(const Record &def, const char *str) {
+  BitsInit *bits = def.getValueAsBitsInit(str);
+  return *bits;
+}
+
+/// sameStringExceptSuffix - Return true if the two strings differ only in RHS's
+/// suffix.  ("VST4d8", "VST4d8_UPD", "_UPD") as input returns true.
+static
+bool sameStringExceptSuffix(const StringRef LHS, const StringRef RHS,
+                            const StringRef Suffix) {
+
+  if (RHS.startswith(LHS) && RHS.endswith(Suffix))
+    return RHS.size() == LHS.size() + Suffix.size();
+
+  return false;
+}
+
+/// thumbInstruction - Determine whether we have a Thumb instruction.
+/// See also ARMInstrFormats.td.
+static bool thumbInstruction(uint8_t Form) {
+  return Form == ARM_FORMAT_THUMBFRM;
+}
+
+// The set (BIT_TRUE, BIT_FALSE, BIT_UNSET) represents a ternary logic system
+// for a bit value.
+//
+// BIT_UNFILTERED is used as the init value for a filter position.  It is used
+// only for filter processings.
+typedef enum {
+  BIT_TRUE,      // '1'
+  BIT_FALSE,     // '0'
+  BIT_UNSET,     // '?'
+  BIT_UNFILTERED // unfiltered
+} bit_value_t;
+
+static bool ValueSet(bit_value_t V) {
+  return (V == BIT_TRUE || V == BIT_FALSE);
+}
+static bool ValueNotSet(bit_value_t V) {
+  return (V == BIT_UNSET);
+}
+static int Value(bit_value_t V) {
+  return ValueNotSet(V) ? -1 : (V == BIT_FALSE ? 0 : 1);
+}
+static bit_value_t bitFromBits(BitsInit &bits, unsigned index) {
+  if (BitInit *bit = dynamic_cast<BitInit*>(bits.getBit(index)))
+    return bit->getValue() ? BIT_TRUE : BIT_FALSE;
+
+  // The bit is uninitialized.
+  return BIT_UNSET;
+}
+// Prints the bit value for each position.
+static void dumpBits(raw_ostream &o, BitsInit &bits) {
+  unsigned index;
+
+  for (index = bits.getNumBits(); index > 0; index--) {
+    switch (bitFromBits(bits, index - 1)) {
+    case BIT_TRUE:
+      o << "1";
+      break;
+    case BIT_FALSE:
+      o << "0";
+      break;
+    case BIT_UNSET:
+      o << "_";
+      break;
+    default:
+      assert(0 && "unexpected return value from bitFromBits");
+    }
+  }
+}
+
+// Enums for the available target names.
+typedef enum {
+  TARGET_ARM = 0,
+  TARGET_THUMB
+} TARGET_NAME_t;
+
+// FIXME: Possibly auto-detected?
+#define BIT_WIDTH 32
+
+// Forward declaration.
+class FilterChooser;
+
+// Representation of the instruction to work on.
+typedef bit_value_t insn_t[BIT_WIDTH];
+
+/// Filter - Filter works with FilterChooser to produce the decoding tree for
+/// the ISA.
+///
+/// It is useful to think of a Filter as governing the switch stmts of the
+/// decoding tree in a certain level.  Each case stmt delegates to an inferior
+/// FilterChooser to decide what further decoding logic to employ, or in another
+/// words, what other remaining bits to look at.  The FilterChooser eventually
+/// chooses a best Filter to do its job.
+///
+/// This recursive scheme ends when the number of Opcodes assigned to the
+/// FilterChooser becomes 1 or if there is a conflict.  A conflict happens when
+/// the Filter/FilterChooser combo does not know how to distinguish among the
+/// Opcodes assigned.
+///
+/// An example of a conflcit is 
+///
+/// Conflict:
+///                     111101000.00........00010000....
+///                     111101000.00........0001........
+///                     1111010...00........0001........
+///                     1111010...00....................
+///                     1111010.........................
+///                     1111............................
+///                     ................................
+///     VST4q8a         111101000_00________00010000____
+///     VST4q8b         111101000_00________00010000____
+///
+/// The Debug output shows the path that the decoding tree follows to reach the
+/// the conclusion that there is a conflict.  VST4q8a is a vst4 to double-spaced
+/// even registers, while VST4q8b is a vst4 to double-spaced odd regsisters.
+///
+/// The encoding info in the .td files does not specify this meta information,
+/// which could have been used by the decoder to resolve the conflict.  The
+/// decoder could try to decode the even/odd register numbering and assign to
+/// VST4q8a or VST4q8b, but for the time being, the decoder chooses the "a"
+/// version and return the Opcode since the two have the same Asm format string.
+class Filter {
+protected:
+  FilterChooser *Owner; // points to the FilterChooser who owns this filter
+  unsigned StartBit; // the starting bit position
+  unsigned NumBits; // number of bits to filter
+  bool Mixed; // a mixed region contains both set and unset bits
+
+  // Map of well-known segment value to the set of uid's with that value. 
+  std::map<uint64_t, std::vector<unsigned> > FilteredInstructions;
+
+  // Set of uid's with non-constant segment values.
+  std::vector<unsigned> VariableInstructions;
+
+  // Map of well-known segment value to its delegate.
+  std::map<unsigned, FilterChooser*> FilterChooserMap;
+
+  // Number of instructions which fall under FilteredInstructions category.
+  unsigned NumFiltered;
+
+  // Keeps track of the last opcode in the filtered bucket.
+  unsigned LastOpcFiltered;
+
+  // Number of instructions which fall under VariableInstructions category.
+  unsigned NumVariable;
+
+public:
+  unsigned getNumFiltered() { return NumFiltered; }
+  unsigned getNumVariable() { return NumVariable; }
+  unsigned getSingletonOpc() {
+    assert(NumFiltered == 1);
+    return LastOpcFiltered;
+  }
+  // Return the filter chooser for the group of instructions without constant
+  // segment values.
+  FilterChooser &getVariableFC() {
+    assert(NumFiltered == 1);
+    assert(FilterChooserMap.size() == 1);
+    return *(FilterChooserMap.find(-1)->second);
+  }
+
+  Filter(const Filter &f);
+  Filter(FilterChooser &owner, unsigned startBit, unsigned numBits, bool mixed);
+
+  ~Filter();
+
+  // Divides the decoding task into sub tasks and delegates them to the
+  // inferior FilterChooser's.
+  //
+  // A special case arises when there's only one entry in the filtered
+  // instructions.  In order to unambiguously decode the singleton, we need to
+  // match the remaining undecoded encoding bits against the singleton.
+  void recurse();
+
+  // Emit code to decode instructions given a segment or segments of bits.
+  void emit(raw_ostream &o, unsigned &Indentation);
+
+  // Returns the number of fanout produced by the filter.  More fanout implies
+  // the filter distinguishes more categories of instructions.
+  unsigned usefulness() const;
+}; // End of class Filter
+
+// These are states of our finite state machines used in FilterChooser's
+// filterProcessor() which produces the filter candidates to use.
+typedef enum {
+  ATTR_NONE,
+  ATTR_FILTERED,
+  ATTR_ALL_SET,
+  ATTR_ALL_UNSET,
+  ATTR_MIXED
+} bitAttr_t;
+
+/// FilterChooser - FilterChooser chooses the best filter among a set of Filters
+/// in order to perform the decoding of instructions at the current level.
+///
+/// Decoding proceeds from the top down.  Based on the well-known encoding bits
+/// of instructions available, FilterChooser builds up the possible Filters that
+/// can further the task of decoding by distinguishing among the remaining
+/// candidate instructions.
+///
+/// Once a filter has been chosen, it is called upon to divide the decoding task
+/// into sub-tasks and delegates them to its inferior FilterChoosers for further
+/// processings.
+///
+/// It is useful to think of a Filter as governing the switch stmts of the
+/// decoding tree.  And each case is delegated to an inferior FilterChooser to
+/// decide what further remaining bits to look at.
+class FilterChooser {
+  static TARGET_NAME_t TargetName;
+
+protected:
+  friend class Filter;
+
+  // Vector of codegen instructions to choose our filter.
+  const std::vector<const CodeGenInstruction*> &AllInstructions;
+
+  // Vector of uid's for this filter chooser to work on.
+  const std::vector<unsigned> Opcodes;
+
+  // Vector of candidate filters.
+  std::vector<Filter> Filters;
+
+  // Array of bit values passed down from our parent.
+  // Set to all BIT_UNFILTERED's for Parent == NULL.
+  bit_value_t FilterBitValues[BIT_WIDTH];
+
+  // Links to the FilterChooser above us in the decoding tree.
+  FilterChooser *Parent;
+  
+  // Index of the best filter from Filters.
+  int BestIndex;
+
+public:
+  static void setTargetName(TARGET_NAME_t tn) { TargetName = tn; }
+
+  FilterChooser(const FilterChooser &FC) :
+      AllInstructions(FC.AllInstructions), Opcodes(FC.Opcodes),
+      Filters(FC.Filters), Parent(FC.Parent), BestIndex(FC.BestIndex) {
+    memcpy(FilterBitValues, FC.FilterBitValues, sizeof(FilterBitValues));
+  }
+
+  FilterChooser(const std::vector<const CodeGenInstruction*> &Insts,
+                const std::vector<unsigned> &IDs) :
+      AllInstructions(Insts), Opcodes(IDs), Filters(), Parent(NULL),
+      BestIndex(-1) {
+    for (unsigned i = 0; i < BIT_WIDTH; ++i)
+      FilterBitValues[i] = BIT_UNFILTERED;
+
+    doFilter();
+  }
+
+  FilterChooser(const std::vector<const CodeGenInstruction*> &Insts,
+                const std::vector<unsigned> &IDs,
+                bit_value_t (&ParentFilterBitValues)[BIT_WIDTH],
+                FilterChooser &parent) :
+      AllInstructions(Insts), Opcodes(IDs), Filters(), Parent(&parent),
+      BestIndex(-1) {
+    for (unsigned i = 0; i < BIT_WIDTH; ++i)
+      FilterBitValues[i] = ParentFilterBitValues[i];
+
+    doFilter();
+  }
+
+  // The top level filter chooser has NULL as its parent.
+  bool isTopLevel() { return Parent == NULL; }
+
+  // This provides an opportunity for target specific code emission.
+  void emitTopHook(raw_ostream &o);
+
+  // Emit the top level typedef and decodeInstruction() function.
+  void emitTop(raw_ostream &o, unsigned &Indentation);
+
+  // This provides an opportunity for target specific code emission after
+  // emitTop().
+  void emitBot(raw_ostream &o, unsigned &Indentation);
+
+protected:
+  // Populates the insn given the uid.
+  void insnWithID(insn_t &Insn, unsigned Opcode) const {
+    BitsInit &Bits = getBitsField(*AllInstructions[Opcode]->TheDef, "Inst");
+
+    for (unsigned i = 0; i < BIT_WIDTH; ++i)
+      Insn[i] = bitFromBits(Bits, i);
+
+    // Set Inst{21} to 1 (wback) when IndexModeBits == IndexModeUpd.
+    if (getByteField(*AllInstructions[Opcode]->TheDef, "IndexModeBits")
+        == IndexModeUpd)
+      Insn[21] = BIT_TRUE;
+  }
+
+  // Returns the record name.
+  const std::string &nameWithID(unsigned Opcode) const {
+    return AllInstructions[Opcode]->TheDef->getName();
+  }
+
+  // Populates the field of the insn given the start position and the number of
+  // consecutive bits to scan for.
+  //
+  // Returns false if there exists any uninitialized bit value in the range.
+  // Returns true, otherwise.
+  bool fieldFromInsn(uint64_t &Field, insn_t &Insn, unsigned StartBit,
+      unsigned NumBits) const;
+
+  /// dumpFilterArray - dumpFilterArray prints out debugging info for the given
+  /// filter array as a series of chars.
+  void dumpFilterArray(raw_ostream &o, bit_value_t (&filter)[BIT_WIDTH]);
+
+  /// dumpStack - dumpStack traverses the filter chooser chain and calls
+  /// dumpFilterArray on each filter chooser up to the top level one.
+  void dumpStack(raw_ostream &o, const char *prefix);
+
+  Filter &bestFilter() {
+    assert(BestIndex != -1 && "BestIndex not set");
+    return Filters[BestIndex];
+  }
+
+  // Called from Filter::recurse() when singleton exists.  For debug purpose.
+  void SingletonExists(unsigned Opc);
+
+  bool PositionFiltered(unsigned i) {
+    return ValueSet(FilterBitValues[i]);
+  }
+
+  // Calculates the island(s) needed to decode the instruction.
+  // This returns a lit of undecoded bits of an instructions, for example,
+  // Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be
+  // decoded bits in order to verify that the instruction matches the Opcode.
+  unsigned getIslands(std::vector<unsigned> &StartBits,
+      std::vector<unsigned> &EndBits, std::vector<uint64_t> &FieldVals,
+      insn_t &Insn);
+
+  // The purpose of this function is for the API client to detect possible
+  // Load/Store Coprocessor instructions.  If the coprocessor number is of
+  // the instruction is either 10 or 11, the decoder should not report the
+  // instruction as LDC/LDC2/STC/STC2, but should match against Advanced SIMD or
+  // VFP instructions.
+  bool LdStCopEncoding1(unsigned Opc) {
+    const std::string &Name = nameWithID(Opc);
+    if (Name == "LDC_OFFSET" || Name == "LDC_OPTION" ||
+        Name == "LDC_POST" || Name == "LDC_PRE" ||
+        Name == "LDCL_OFFSET" || Name == "LDCL_OPTION" ||
+        Name == "LDCL_POST" || Name == "LDCL_PRE" ||
+        Name == "STC_OFFSET" || Name == "STC_OPTION" ||
+        Name == "STC_POST" || Name == "STC_PRE" ||
+        Name == "STCL_OFFSET" || Name == "STCL_OPTION" ||
+        Name == "STCL_POST" || Name == "STCL_PRE")
+      return true;
+    else
+      return false;
+  }
+
+  // Emits code to decode the singleton.  Return true if we have matched all the
+  // well-known bits.
+  bool emitSingletonDecoder(raw_ostream &o, unsigned &Indentation,unsigned Opc);
+
+  // Emits code to decode the singleton, and then to decode the rest.
+  void emitSingletonDecoder(raw_ostream &o, unsigned &Indentation,Filter &Best);
+
+  // Assign a single filter and run with it.
+  void runSingleFilter(FilterChooser &owner, unsigned startBit, unsigned numBit,
+      bool mixed);
+
+  // reportRegion is a helper function for filterProcessor to mark a region as
+  // eligible for use as a filter region.
+  void reportRegion(bitAttr_t RA, unsigned StartBit, unsigned BitIndex,
+      bool AllowMixed);
+
+  // FilterProcessor scans the well-known encoding bits of the instructions and
+  // builds up a list of candidate filters.  It chooses the best filter and
+  // recursively descends down the decoding tree.
+  bool filterProcessor(bool AllowMixed, bool Greedy = true);
+
+  // Decides on the best configuration of filter(s) to use in order to decode
+  // the instructions.  A conflict of instructions may occur, in which case we
+  // dump the conflict set to the standard error.
+  void doFilter();
+
+  // Emits code to decode our share of instructions.  Returns true if the
+  // emitted code causes a return, which occurs if we know how to decode
+  // the instruction at this level or the instruction is not decodeable.
+  bool emit(raw_ostream &o, unsigned &Indentation);
+};
+
+///////////////////////////
+//                       //
+// Filter Implmenetation //
+//                       //
+///////////////////////////
+
+Filter::Filter(const Filter &f) :
+  Owner(f.Owner), StartBit(f.StartBit), NumBits(f.NumBits), Mixed(f.Mixed),
+  FilteredInstructions(f.FilteredInstructions),
+  VariableInstructions(f.VariableInstructions),
+  FilterChooserMap(f.FilterChooserMap), NumFiltered(f.NumFiltered),
+  LastOpcFiltered(f.LastOpcFiltered), NumVariable(f.NumVariable) {
+}
+
+Filter::Filter(FilterChooser &owner, unsigned startBit, unsigned numBits,
+    bool mixed) : Owner(&owner), StartBit(startBit), NumBits(numBits),
+                  Mixed(mixed) {
+  assert(StartBit + NumBits - 1 < BIT_WIDTH);
+
+  NumFiltered = 0;
+  LastOpcFiltered = 0;
+  NumVariable = 0;
+
+  for (unsigned i = 0, e = Owner->Opcodes.size(); i != e; ++i) {
+    insn_t Insn;
+
+    // Populates the insn given the uid.
+    Owner->insnWithID(Insn, Owner->Opcodes[i]);
+
+    uint64_t Field;
+    // Scans the segment for possibly well-specified encoding bits.
+    bool ok = Owner->fieldFromInsn(Field, Insn, StartBit, NumBits);
+
+    if (ok) {
+      // The encoding bits are well-known.  Lets add the uid of the
+      // instruction into the bucket keyed off the constant field value.
+      LastOpcFiltered = Owner->Opcodes[i];
+      FilteredInstructions[Field].push_back(LastOpcFiltered);
+      ++NumFiltered;
+    } else {
+      // Some of the encoding bit(s) are unspecfied.  This contributes to
+      // one additional member of "Variable" instructions.
+      VariableInstructions.push_back(Owner->Opcodes[i]);
+      ++NumVariable;
+    }
+  }
+
+  assert((FilteredInstructions.size() + VariableInstructions.size() > 0)
+         && "Filter returns no instruction categories");
+}
+
+Filter::~Filter() {
+  std::map<unsigned, FilterChooser*>::iterator filterIterator;
+  for (filterIterator = FilterChooserMap.begin();
+       filterIterator != FilterChooserMap.end();
+       filterIterator++) {
+    delete filterIterator->second;
+  }
+}
+
+// Divides the decoding task into sub tasks and delegates them to the
+// inferior FilterChooser's.
+//
+// A special case arises when there's only one entry in the filtered
+// instructions.  In order to unambiguously decode the singleton, we need to
+// match the remaining undecoded encoding bits against the singleton.
+void Filter::recurse() {
+  std::map<uint64_t, std::vector<unsigned> >::const_iterator mapIterator;
+
+  bit_value_t BitValueArray[BIT_WIDTH];
+  // Starts by inheriting our parent filter chooser's filter bit values.
+  memcpy(BitValueArray, Owner->FilterBitValues, sizeof(BitValueArray));
+
+  unsigned bitIndex;
+
+  if (VariableInstructions.size()) {
+    // Conservatively marks each segment position as BIT_UNSET.
+    for (bitIndex = 0; bitIndex < NumBits; bitIndex++)
+      BitValueArray[StartBit + bitIndex] = BIT_UNSET;
+
+    // Delegates to an inferior filter chooser for futher processing on this
+    // group of instructions whose segment values are variable.
+    FilterChooserMap.insert(std::pair<unsigned, FilterChooser*>(
+                              (unsigned)-1,
+                              new FilterChooser(Owner->AllInstructions,
+                                                VariableInstructions,
+                                                BitValueArray,
+                                                *Owner)
+                              ));
+  }
+
+  // No need to recurse for a singleton filtered instruction.
+  // See also Filter::emit().
+  if (getNumFiltered() == 1) {
+    //Owner->SingletonExists(LastOpcFiltered);
+    assert(FilterChooserMap.size() == 1);
+    return;
+  }
+        
+  // Otherwise, create sub choosers.
+  for (mapIterator = FilteredInstructions.begin();
+       mapIterator != FilteredInstructions.end();
+       mapIterator++) {
+
+    // Marks all the segment positions with either BIT_TRUE or BIT_FALSE.
+    for (bitIndex = 0; bitIndex < NumBits; bitIndex++) {
+      if (mapIterator->first & (1 << bitIndex))
+        BitValueArray[StartBit + bitIndex] = BIT_TRUE;
+      else
+        BitValueArray[StartBit + bitIndex] = BIT_FALSE;
+    }
+
+    // Delegates to an inferior filter chooser for futher processing on this
+    // category of instructions.
+    FilterChooserMap.insert(std::pair<unsigned, FilterChooser*>(
+                              mapIterator->first,
+                              new FilterChooser(Owner->AllInstructions,
+                                                mapIterator->second,
+                                                BitValueArray,
+                                                *Owner)
+                              ));
+  }
+}
+
+// Emit code to decode instructions given a segment or segments of bits.
+void Filter::emit(raw_ostream &o, unsigned &Indentation) {
+  o.indent(Indentation) << "// Check Inst{";
+
+  if (NumBits > 1)
+    o << (StartBit + NumBits - 1) << '-';
+
+  o << StartBit << "} ...\n";
+
+  o.indent(Indentation) << "switch (fieldFromInstruction(insn, "
+                        << StartBit << ", " << NumBits << ")) {\n";
+
+  std::map<unsigned, FilterChooser*>::iterator filterIterator;
+
+  bool DefaultCase = false;
+  for (filterIterator = FilterChooserMap.begin();
+       filterIterator != FilterChooserMap.end();
+       filterIterator++) {
+
+    // Field value -1 implies a non-empty set of variable instructions.
+    // See also recurse().
+    if (filterIterator->first == (unsigned)-1) {
+      DefaultCase = true;
+
+      o.indent(Indentation) << "default:\n";
+      o.indent(Indentation) << "  break; // fallthrough\n";
+
+      // Closing curly brace for the switch statement.
+      // This is unconventional because we want the default processing to be
+      // performed for the fallthrough cases as well, i.e., when the "cases"
+      // did not prove a decoded instruction.
+      o.indent(Indentation) << "}\n";
+
+    } else
+      o.indent(Indentation) << "case " << filterIterator->first << ":\n";
+
+    // We arrive at a category of instructions with the same segment value.
+    // Now delegate to the sub filter chooser for further decodings.
+    // The case may fallthrough, which happens if the remaining well-known
+    // encoding bits do not match exactly.
+    if (!DefaultCase) { ++Indentation; ++Indentation; }
+
+    bool finished = filterIterator->second->emit(o, Indentation);
+    // For top level default case, there's no need for a break statement.
+    if (Owner->isTopLevel() && DefaultCase)
+      break;
+    if (!finished)
+      o.indent(Indentation) << "break;\n";
+
+    if (!DefaultCase) { --Indentation; --Indentation; }
+  }
+
+  // If there is no default case, we still need to supply a closing brace.
+  if (!DefaultCase) {
+    // Closing curly brace for the switch statement.
+    o.indent(Indentation) << "}\n";
+  }
+}
+
+// Returns the number of fanout produced by the filter.  More fanout implies
+// the filter distinguishes more categories of instructions.
+unsigned Filter::usefulness() const {
+  if (VariableInstructions.size())
+    return FilteredInstructions.size();
+  else
+    return FilteredInstructions.size() + 1;
+}
+
+//////////////////////////////////
+//                              //
+// Filterchooser Implementation //
+//                              //
+//////////////////////////////////
+
+// Define the symbol here.
+TARGET_NAME_t FilterChooser::TargetName;
+
+// This provides an opportunity for target specific code emission.
+void FilterChooser::emitTopHook(raw_ostream &o) {
+  if (TargetName == TARGET_ARM) {
+    // Emit code that references the ARMFormat data type.
+    o << "static const ARMFormat ARMFormats[] = {\n";
+    for (unsigned i = 0, e = AllInstructions.size(); i != e; ++i) {
+      const Record &Def = *(AllInstructions[i]->TheDef);
+      const std::string &Name = Def.getName();
+      if (Def.isSubClassOf("InstARM") || Def.isSubClassOf("InstThumb"))
+        o.indent(2) << 
+          stringForARMFormat((ARMFormat)getByteField(Def, "Form"));
+      else
+        o << "  ARM_FORMAT_NA";
+
+      o << ",\t// Inst #" << i << " = " << Name << '\n';
+    }
+    o << "  ARM_FORMAT_NA\t// Unreachable.\n";
+    o << "};\n\n";
+  }
+}
+
+// Emit the top level typedef and decodeInstruction() function.
+void FilterChooser::emitTop(raw_ostream &o, unsigned &Indentation) {
+  // Run the target specific emit hook.
+  emitTopHook(o);
+
+  switch (BIT_WIDTH) {
+  case 8:
+    o.indent(Indentation) << "typedef uint8_t field_t;\n";
+    break;
+  case 16:
+    o.indent(Indentation) << "typedef uint16_t field_t;\n";
+    break;
+  case 32:
+    o.indent(Indentation) << "typedef uint32_t field_t;\n";
+    break;
+  case 64:
+    o.indent(Indentation) << "typedef uint64_t field_t;\n";
+    break;
+  default:
+    assert(0 && "Unexpected instruction size!");
+  }
+
+  o << '\n';
+
+  o.indent(Indentation) << "static field_t " <<
+    "fieldFromInstruction(field_t insn, unsigned startBit, unsigned numBits)\n";
+
+  o.indent(Indentation) << "{\n";
+
+  ++Indentation; ++Indentation;
+  o.indent(Indentation) << "assert(startBit + numBits <= " << BIT_WIDTH
+                        << " && \"Instruction field out of bounds!\");\n";
+  o << '\n';
+  o.indent(Indentation) << "field_t fieldMask;\n";
+  o << '\n';
+  o.indent(Indentation) << "if (numBits == " << BIT_WIDTH << ")\n";
+
+  ++Indentation; ++Indentation;
+  o.indent(Indentation) << "fieldMask = (field_t)-1;\n";
+  --Indentation; --Indentation;
+
+  o.indent(Indentation) << "else\n";
+
+  ++Indentation; ++Indentation;
+  o.indent(Indentation) << "fieldMask = ((1 << numBits) - 1) << startBit;\n";
+  --Indentation; --Indentation;
+
+  o << '\n';
+  o.indent(Indentation) << "return (insn & fieldMask) >> startBit;\n";
+  --Indentation; --Indentation;
+
+  o.indent(Indentation) << "}\n";
+
+  o << '\n';
+
+  o.indent(Indentation) << "static uint16_t decodeInstruction(field_t insn) {\n";
+
+  ++Indentation; ++Indentation;
+  // Emits code to decode the instructions.
+  emit(o, Indentation);
+
+  o << '\n';
+  o.indent(Indentation) << "return 0;\n";
+  --Indentation; --Indentation;
+
+  o.indent(Indentation) << "}\n";
+
+  o << '\n';
+}
+
+// This provides an opportunity for target specific code emission after
+// emitTop().
+void FilterChooser::emitBot(raw_ostream &o, unsigned &Indentation) {
+  if (TargetName != TARGET_THUMB) return;
+
+  // Emit code that decodes the Thumb ISA.
+  o.indent(Indentation)
+    << "static uint16_t decodeThumbInstruction(field_t insn) {\n";
+
+  ++Indentation; ++Indentation;
+
+  // Emits code to decode the instructions.
+  emit(o, Indentation);
+
+  o << '\n';
+  o.indent(Indentation) << "return 0;\n";
+
+  --Indentation; --Indentation;
+
+  o.indent(Indentation) << "}\n";
+}
+
+// Populates the field of the insn given the start position and the number of
+// consecutive bits to scan for.
+//
+// Returns false if and on the first uninitialized bit value encountered.
+// Returns true, otherwise.
+bool FilterChooser::fieldFromInsn(uint64_t &Field, insn_t &Insn,
+    unsigned StartBit, unsigned NumBits) const {
+  Field = 0;
+
+  for (unsigned i = 0; i < NumBits; ++i) {
+    if (Insn[StartBit + i] == BIT_UNSET)
+      return false;
+
+    if (Insn[StartBit + i] == BIT_TRUE)
+      Field = Field | (1 << i);
+  }
+
+  return true;
+}
+
+/// dumpFilterArray - dumpFilterArray prints out debugging info for the given
+/// filter array as a series of chars.
+void FilterChooser::dumpFilterArray(raw_ostream &o,
+    bit_value_t (&filter)[BIT_WIDTH]) {
+  unsigned bitIndex;
+
+  for (bitIndex = BIT_WIDTH; bitIndex > 0; bitIndex--) {
+    switch (filter[bitIndex - 1]) {
+    case BIT_UNFILTERED:
+      o << ".";
+      break;
+    case BIT_UNSET:
+      o << "_";
+      break;
+    case BIT_TRUE:
+      o << "1";
+      break;
+    case BIT_FALSE:
+      o << "0";
+      break;
+    }
+  }
+}
+
+/// dumpStack - dumpStack traverses the filter chooser chain and calls
+/// dumpFilterArray on each filter chooser up to the top level one.
+void FilterChooser::dumpStack(raw_ostream &o, const char *prefix) {
+  FilterChooser *current = this;
+
+  while (current) {
+    o << prefix;
+    dumpFilterArray(o, current->FilterBitValues);
+    o << '\n';
+    current = current->Parent;
+  }
+}
+
+// Called from Filter::recurse() when singleton exists.  For debug purpose.
+void FilterChooser::SingletonExists(unsigned Opc) {
+  insn_t Insn0;
+  insnWithID(Insn0, Opc);
+
+  errs() << "Singleton exists: " << nameWithID(Opc)
+         << " with its decoding dominating ";
+  for (unsigned i = 0; i < Opcodes.size(); ++i) {
+    if (Opcodes[i] == Opc) continue;
+    errs() << nameWithID(Opcodes[i]) << ' ';
+  }
+  errs() << '\n';
+
+  dumpStack(errs(), "\t\t");
+  for (unsigned i = 0; i < Opcodes.size(); i++) {
+    const std::string &Name = nameWithID(Opcodes[i]);
+
+    errs() << '\t' << Name << " ";
+    dumpBits(errs(),
+             getBitsField(*AllInstructions[Opcodes[i]]->TheDef, "Inst"));
+    errs() << '\n';
+  }
+}
+
+// Calculates the island(s) needed to decode the instruction.
+// This returns a list of undecoded bits of an instructions, for example,
+// Inst{20} = 1 && Inst{3-0} == 0b1111 represents two islands of yet-to-be
+// decoded bits in order to verify that the instruction matches the Opcode.
+unsigned FilterChooser::getIslands(std::vector<unsigned> &StartBits,
+    std::vector<unsigned> &EndBits, std::vector<uint64_t> &FieldVals,
+    insn_t &Insn) {
+  unsigned Num, BitNo;
+  Num = BitNo = 0;
+
+  uint64_t FieldVal = 0;
+
+  // 0: Init
+  // 1: Water (the bit value does not affect decoding)
+  // 2: Island (well-known bit value needed for decoding)
+  int State = 0;
+  int Val = -1;
+
+  for (unsigned i = 0; i < BIT_WIDTH; ++i) {
+    Val = Value(Insn[i]);
+    bool Filtered = PositionFiltered(i);
+    switch (State) {
+    default:
+      assert(0 && "Unreachable code!");
+      break;
+    case 0:
+    case 1:
+      if (Filtered || Val == -1)
+        State = 1; // Still in Water
+      else {
+        State = 2; // Into the Island
+        BitNo = 0;
+        StartBits.push_back(i);
+        FieldVal = Val;
+      }
+      break;
+    case 2:
+      if (Filtered || Val == -1) {
+        State = 1; // Into the Water
+        EndBits.push_back(i - 1);
+        FieldVals.push_back(FieldVal);
+        ++Num;
+      } else {
+        State = 2; // Still in Island
+        ++BitNo;
+        FieldVal = FieldVal | Val << BitNo;
+      }
+      break;
+    }
+  }
+  // If we are still in Island after the loop, do some housekeeping.
+  if (State == 2) {
+    EndBits.push_back(BIT_WIDTH - 1);
+    FieldVals.push_back(FieldVal);
+    ++Num;
+  }
+
+  assert(StartBits.size() == Num && EndBits.size() == Num &&
+         FieldVals.size() == Num);
+  return Num;
+}
+
+// Emits code to decode the singleton.  Return true if we have matched all the
+// well-known bits.
+bool FilterChooser::emitSingletonDecoder(raw_ostream &o, unsigned &Indentation,
+                                         unsigned Opc) {
+  std::vector<unsigned> StartBits;
+  std::vector<unsigned> EndBits;
+  std::vector<uint64_t> FieldVals;
+  insn_t Insn;
+  insnWithID(Insn, Opc);
+
+  // This provides a good opportunity to check for possible Ld/St Coprocessor
+  // Opcode and escapes if the coproc # is either 10 or 11.  It is a NEON/VFP
+  // instruction is disguise.
+  if (TargetName == TARGET_ARM && LdStCopEncoding1(Opc)) {
+    o.indent(Indentation);
+    // A8.6.51 & A8.6.188
+    // If coproc = 0b101?, i.e, slice(insn, 11, 8) = 10 or 11, escape.
+