DecoderEmitter.cpp | Explore in Territory

//===---------------- DecoderEmitter.cpp - Decoder Generator --------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// It contains the tablegen backend that emits the decoder functions for
// targets with fixed/variable length instruction set.
//
//===----------------------------------------------------------------------===//

#include "Common/CodeGenHwModes.h"
#include "Common/CodeGenInstruction.h"
#include "Common/CodeGenTarget.h"
#include "Common/InfoByHwMode.h"
#include "Common/VarLenCodeEmitterGen.h"
#include "TableGenBackends.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/CachedHashString.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/MC/MCDecoderOps.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/LEB128.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/TableGen/Error.h"
#include "llvm/TableGen/Record.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <map>
#include <memory>
#include <set>
#include <string>
#include <utility>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

extern cl::OptionCategory DisassemblerEmitterCat;

enum SuppressLevel { … };

cl::opt<SuppressLevel> DecoderEmitterSuppressDuplicates(
    "suppress-per-hwmode-duplicates",
    cl::desc("Suppress duplication of instrs into per-HwMode decoder tables"),
    cl::values(
        clEnumValN(
            SUPPRESSION_DISABLE, "O0",
            "Do not prevent DecoderTable duplications caused by HwModes"),
        clEnumValN(
            SUPPRESSION_LEVEL1, "O1",
            "Remove duplicate DecoderTable entries generated due to HwModes"),
        clEnumValN(
            SUPPRESSION_LEVEL2, "O2",
            "Extract HwModes-specific instructions into new DecoderTables, "
            "significantly reducing Table Duplications")),
    cl::init(SUPPRESSION_DISABLE), cl::cat(DisassemblerEmitterCat));

namespace … // end anonymous namespace

// 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.
bit_value_t;

static bool ValueSet(bit_value_t V) { … }

static bool ValueNotSet(bit_value_t V) { … }

static int Value(bit_value_t V) { … }

static bit_value_t bitFromBits(const BitsInit &bits, unsigned index) { … }

// Prints the bit value for each position.
static void dumpBits(raw_ostream &o, const BitsInit &bits) { … }

static BitsInit &getBitsField(const Record &def, StringRef str) { … }

// Representation of the instruction to work on.
insn_t;

namespace {

static const uint64_t NO_FIXED_SEGMENTS_SENTINEL = …;

class FilterChooser;

/// 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 conflict 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 registers.
///
/// 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 { … }; // end class Filter

} // end anonymous namespace

// These are states of our finite state machines used in FilterChooser's
// filterProcessor() which produces the filter candidates to use.
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.
namespace {

class FilterChooser { … };

} // end anonymous namespace

///////////////////////////
//                       //
// Filter Implementation //
//                       //
///////////////////////////

Filter::Filter(Filter &&f)
    : … { … }

Filter::Filter(FilterChooser &owner, unsigned startBit, unsigned numBits,
               bool mixed)
    : … { … }

// 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() { … }

static void resolveTableFixups(DecoderTable &Table, const FixupList &Fixups,
                               uint32_t DestIdx) { … }

// Emit table entries to decode instructions given a segment or segments
// of bits.
void Filter::emitTableEntry(DecoderTableInfo &TableInfo) const { … }

// Returns the number of fanout produced by the filter.  More fanout implies
// the filter distinguishes more categories of instructions.
unsigned Filter::usefulness() const { … }

//////////////////////////////////
//                              //
// Filterchooser Implementation //
//                              //
//////////////////////////////////

// Emit the decoder state machine table.
void DecoderEmitter::emitTable(formatted_raw_ostream &OS, DecoderTable &Table,
                               unsigned Indentation, unsigned BitWidth,
                               StringRef Namespace,
                               const EncodingIDsVec &EncodingIDs) const { … }

void DecoderEmitter::emitInstrLenTable(formatted_raw_ostream &OS,
                                       std::vector<unsigned> &InstrLen) const { … }

void DecoderEmitter::emitPredicateFunction(formatted_raw_ostream &OS,
                                           PredicateSet &Predicates,
                                           unsigned Indentation) const { … }

void DecoderEmitter::emitDecoderFunction(formatted_raw_ostream &OS,
                                         DecoderSet &Decoders,
                                         unsigned Indentation) const { … }

// Populates the field of the insn given the start position and the number of
// consecutive bits to scan for.
//
// Returns a pair of values (indicator, field), where the indicator is false
// if there exists any uninitialized bit value in the range and true if all
// bits are well-known. The second value is the potentially populated field.
std::pair<bool, uint64_t> FilterChooser::fieldFromInsn(const 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 FilterChooser::dumpFilterArray(
    raw_ostream &o, const std::vector<bit_value_t> &filter) const { … }

/// 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) const { … }

// 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,
                                   const insn_t &Insn) const { … }

void FilterChooser::emitBinaryParser(raw_ostream &o, unsigned &Indentation,
                                     const OperandInfo &OpInfo,
                                     bool &OpHasCompleteDecoder) const { … }

void FilterChooser::emitDecoder(raw_ostream &OS, unsigned Indentation,
                                unsigned Opc, bool &HasCompleteDecoder) const { … }

unsigned FilterChooser::getDecoderIndex(DecoderSet &Decoders, unsigned Opc,
                                        bool &HasCompleteDecoder) const { … }

// If ParenIfBinOp is true, print a surrounding () if Val uses && or ||.
bool FilterChooser::emitPredicateMatchAux(const Init &Val, bool ParenIfBinOp,
                                          raw_ostream &OS) const { … }

bool FilterChooser::emitPredicateMatch(raw_ostream &o, unsigned &Indentation,
                                       unsigned Opc) const { … }

bool FilterChooser::doesOpcodeNeedPredicate(unsigned Opc) const { … }

unsigned FilterChooser::getPredicateIndex(DecoderTableInfo &TableInfo,
                                          StringRef Predicate) const { … }

void FilterChooser::emitPredicateTableEntry(DecoderTableInfo &TableInfo,
                                            unsigned Opc) const { … }

void FilterChooser::emitSoftFailTableEntry(DecoderTableInfo &TableInfo,
                                           unsigned Opc) const { … }

// Emits table entries to decode the singleton.
void FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo,
                                            EncodingIDAndOpcode Opc) const { … }

// Emits table entries to decode the singleton, and then to decode the rest.
void FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo,
                                            const Filter &Best) const { … }

// Assign a single filter and run with it.  Top level API client can initialize
// with a single filter to start the filtering process.
void FilterChooser::runSingleFilter(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 FilterChooser::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 FilterChooser::filterProcessor(bool AllowMixed, bool Greedy) { … } // end of FilterChooser::filterProcessor(bool)

// 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 FilterChooser::doFilter() { … }

// emitTableEntries - Emit state machine entries to decode our share of
// instructions.
void FilterChooser::emitTableEntries(DecoderTableInfo &TableInfo) const { … }

static std::string findOperandDecoderMethod(Record *Record) { … }

OperandInfo getOpInfo(Record *TypeRecord) { … }

void parseVarLenInstOperand(const Record &Def,
                            std::vector<OperandInfo> &Operands,
                            const CodeGenInstruction &CGI) { … }

static void debugDumpRecord(const Record &Rec) { … }

/// For an operand field named OpName: populate OpInfo.InitValue with the
/// constant-valued bit values, and OpInfo.Fields with the ranges of bits to
/// insert from the decoded instruction.
static void addOneOperandFields(const Record &EncodingDef, const BitsInit &Bits,
                                std::map<std::string, std::string> &TiedNames,
                                StringRef OpName, OperandInfo &OpInfo) { … }

static unsigned
populateInstruction(CodeGenTarget &Target, const Record &EncodingDef,
                    const CodeGenInstruction &CGI, unsigned Opc,
                    std::map<unsigned, std::vector<OperandInfo>> &Operands,
                    bool IsVarLenInst) { … }

// emitFieldFromInstruction - Emit the templated helper function
// fieldFromInstruction().
// On Windows we make sure that this function is not inlined when
// using the VS compiler. It has a bug which causes the function
// to be optimized out in some circumstances. See llvm.org/pr38292
static void emitFieldFromInstruction(formatted_raw_ostream &OS) { … }

// emitInsertBits - Emit the templated helper function insertBits().
static void emitInsertBits(formatted_raw_ostream &OS) { … }

// emitDecodeInstruction - Emit the templated helper function
// decodeInstruction().
static void emitDecodeInstruction(formatted_raw_ostream &OS,
                                  bool IsVarLenInst) { … }

// Helper to propagate SoftFail status. Returns false if the status is Fail;
// callers are expected to early-exit in that condition. (Note, the '&' operator
// is correct to propagate the values of this enum; see comment on 'enum
// DecodeStatus'.)
static void emitCheck(formatted_raw_ostream &OS) { … }

// Collect all HwModes referenced by the target for encoding purposes,
// returning a vector of corresponding names.
static void collectHwModesReferencedForEncodings(
    const CodeGenHwModes &HWM, std::vector<StringRef> &Names,
    NamespacesHwModesMap &NamespacesWithHwModes) { … }

static void
handleHwModesUnrelatedEncodings(const CodeGenInstruction *Instr,
                                const std::vector<StringRef> &HwModeNames,
                                NamespacesHwModesMap &NamespacesWithHwModes,
                                std::vector<EncodingAndInst> &GlobalEncodings) { … }

// Emits disassembler code for instruction decoding.
void DecoderEmitter::run(raw_ostream &o) { … }

namespace llvm {

void EmitDecoder(RecordKeeper &RK, raw_ostream &OS,
                 const std::string &PredicateNamespace) { … }

} // end namespace llvm
llvm/llvm/utils/TableGen/DecoderEmitter.cpp
