llvm/llvm/utils/TableGen/CodeGenMapTable.cpp

//===- CodeGenMapTable.cpp - Instruction Mapping Table 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
//
//===----------------------------------------------------------------------===//
// CodeGenMapTable provides functionality for the TableGen to create
// relation mapping between instructions. Relation models are defined using
// InstrMapping as a base class. This file implements the functionality which
// parses these definitions and generates relation maps using the information
// specified there. These maps are emitted as tables in the XXXGenInstrInfo.inc
// file along with the functions to query them.
//
// A relationship model to relate non-predicate instructions with their
// predicated true/false forms can be defined as follows:
//
// def getPredOpcode : InstrMapping {
//  let FilterClass = "PredRel";
//  let RowFields = ["BaseOpcode"];
//  let ColFields = ["PredSense"];
//  let KeyCol = ["none"];
//  let ValueCols = [["true"], ["false"]]; }
//
// CodeGenMapTable parses this map and generates a table in XXXGenInstrInfo.inc
// file that contains the instructions modeling this relationship. This table
// is defined in the function
// "int getPredOpcode(uint16_t Opcode, enum PredSense inPredSense)"
// that can be used to retrieve the predicated form of the instruction by
// passing its opcode value and the predicate sense (true/false) of the desired
// instruction as arguments.
//
// Short description of the algorithm:
//
// 1) Iterate through all the records that derive from "InstrMapping" class.
// 2) For each record, filter out instructions based on the FilterClass value.
// 3) Iterate through this set of instructions and insert them into
// RowInstrMap map based on their RowFields values. RowInstrMap is keyed by the
// vector of RowFields values and contains vectors of Records (instructions) as
// values. RowFields is a list of fields that are required to have the same
// values for all the instructions appearing in the same row of the relation
// table. All the instructions in a given row of the relation table have some
// sort of relationship with the key instruction defined by the corresponding
// relationship model.
//
// Ex: RowInstrMap(RowVal1, RowVal2, ...) -> [Instr1, Instr2, Instr3, ... ]
// Here Instr1, Instr2, Instr3 have same values (RowVal1, RowVal2) for
// RowFields. These groups of instructions are later matched against ValueCols
// to determine the column they belong to, if any.
//
// While building the RowInstrMap map, collect all the key instructions in
// KeyInstrVec. These are the instructions having the same values as KeyCol
// for all the fields listed in ColFields.
//
// For Example:
//
// Relate non-predicate instructions with their predicated true/false forms.
//
// def getPredOpcode : InstrMapping {
//  let FilterClass = "PredRel";
//  let RowFields = ["BaseOpcode"];
//  let ColFields = ["PredSense"];
//  let KeyCol = ["none"];
//  let ValueCols = [["true"], ["false"]]; }
//
// Here, only instructions that have "none" as PredSense will be selected as key
// instructions.
//
// 4) For each key instruction, get the group of instructions that share the
// same key-value as the key instruction from RowInstrMap. Iterate over the list
// of columns in ValueCols (it is defined as a list<list<string> >. Therefore,
// it can specify multi-column relationships). For each column, find the
// instruction from the group that matches all the values for the column.
// Multiple matches are not allowed.
//
//===----------------------------------------------------------------------===//

#include "Common/CodeGenInstruction.h"
#include "Common/CodeGenTarget.h"
#include "TableGenBackends.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/TableGen/Error.h"
#include "llvm/TableGen/Record.h"

usingnamespacellvm;
InstrRelMapTy;
RowInstrMapTy;

namespace {

//===----------------------------------------------------------------------===//
// This class is used to represent InstrMapping class defined in Target.td file.
class InstrMap { … };

//===----------------------------------------------------------------------===//
// class MapTableEmitter : It builds the instruction relation maps using
// the information provided in InstrMapping records. It outputs these
// relationship maps as tables into XXXGenInstrInfo.inc file along with the
// functions to query them.

class MapTableEmitter { … };
} // end anonymous namespace

//===----------------------------------------------------------------------===//
// Process all the instructions that model this relation (alreday present in
// InstrDefs) and insert them into RowInstrMap which is keyed by the values of
// the fields listed as RowFields. It stores vectors of records as values.
// All the related instructions have the same values for the RowFields thus are
// part of the same key-value pair.
//===----------------------------------------------------------------------===//

void MapTableEmitter::buildRowInstrMap() { … }

//===----------------------------------------------------------------------===//
// Return true if an instruction is a KeyCol instruction.
//===----------------------------------------------------------------------===//

bool MapTableEmitter::isKeyColInstr(const Record *CurInstr) { … }

//===----------------------------------------------------------------------===//
// Build a map to link key instructions with the column instructions arranged
// according to their column positions.
//===----------------------------------------------------------------------===//

void MapTableEmitter::buildMapTable() { … }

//===----------------------------------------------------------------------===//
// Find column instruction based on the constraints for that column.
//===----------------------------------------------------------------------===//

const Record *MapTableEmitter::getInstrForColumn(const Record *KeyInstr,
                                                 const ListInit *CurValueCol) { … }

//===----------------------------------------------------------------------===//
// Emit one table per relation. Only instructions with a valid relation of a
// given type are included in the table sorted by their enum values (opcodes).
// Binary search is used for locating instructions in the table.
//===----------------------------------------------------------------------===//

unsigned MapTableEmitter::emitBinSearchTable(raw_ostream &OS) { … }

//===----------------------------------------------------------------------===//
// Emit binary search algorithm as part of the functions used to query
// relation tables.
//===----------------------------------------------------------------------===//

void MapTableEmitter::emitBinSearch(raw_ostream &OS, unsigned TableSize) { … }

//===----------------------------------------------------------------------===//
// Emit functions to query relation tables.
//===----------------------------------------------------------------------===//

void MapTableEmitter::emitMapFuncBody(raw_ostream &OS, unsigned TableSize) { … }

//===----------------------------------------------------------------------===//
// Emit relation tables and the functions to query them.
//===----------------------------------------------------------------------===//

void MapTableEmitter::emitTablesWithFunc(raw_ostream &OS) { … }

//===----------------------------------------------------------------------===//
// Emit enums for the column fields across all the instruction maps.
//===----------------------------------------------------------------------===//

static void emitEnums(raw_ostream &OS, const RecordKeeper &Records) { … }

//===----------------------------------------------------------------------===//
// Parse 'InstrMapping' records and use the information to form relationship
// between instructions. These relations are emitted as a tables along with the
// functions to query them.
//===----------------------------------------------------------------------===//
void llvm::EmitMapTable(const RecordKeeper &Records, raw_ostream &OS) { … }