CodeGenSchedule.cpp | Explore in Territory

//===- CodeGenSchedule.cpp - Scheduling MachineModels ---------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This file defines structures to encapsulate the machine model as described in
// the target description.
//
//===----------------------------------------------------------------------===//

#include "CodeGenSchedule.h"
#include "CodeGenInstruction.h"
#include "CodeGenTarget.h"
#include "Utils.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Regex.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/TableGen/Error.h"
#include <algorithm>
#include <iterator>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

#ifndef NDEBUG
static void dumpIdxVec(ArrayRef<unsigned> V) {
  for (unsigned Idx : V)
    dbgs() << Idx << ", ";
}
#endif

namespace {

// (instrs a, b, ...) Evaluate and union all arguments. Identical to AddOp.
struct InstrsOp : public SetTheory::Operator { … };

// (instregex "OpcPat",...) Find all instructions matching an opcode pattern.
struct InstRegexOp : public SetTheory::Operator { … };

} // end anonymous namespace

/// CodeGenModels ctor interprets machine model records and populates maps.
CodeGenSchedModels::CodeGenSchedModels(RecordKeeper &RK,
                                       const CodeGenTarget &TGT)
    : … { … }

void CodeGenSchedModels::checkSTIPredicates() const { … }

// Used by function `processSTIPredicate` to construct a mask of machine
// instruction operands.
static APInt constructOperandMask(ArrayRef<int64_t> Indices) { … }

static void processSTIPredicate(STIPredicateFunction &Fn,
                                const ProcModelMapTy &ProcModelMap) { … }

void CodeGenSchedModels::collectSTIPredicates() { … }

void OpcodeInfo::addPredicateForProcModel(const llvm::APInt &CpuMask,
                                          const llvm::APInt &OperandMask,
                                          const Record *Predicate) { … }

void CodeGenSchedModels::checkMCInstPredicates() const { … }

void CodeGenSchedModels::collectRetireControlUnits() { … }

void CodeGenSchedModels::collectLoadStoreQueueInfo() { … }

/// Collect optional processor information.
void CodeGenSchedModels::collectOptionalProcessorInfo() { … }

/// Gather all processor models.
void CodeGenSchedModels::collectProcModels() { … }

/// Get a unique processor model based on the defined MachineModel and
/// ProcessorItineraries.
void CodeGenSchedModels::addProcModel(Record *ProcDef) { … }

// Recursively find all reachable SchedReadWrite records.
static void scanSchedRW(Record *RWDef, RecVec &RWDefs,
                        SmallPtrSet<Record *, 16> &RWSet) { … }

// Collect and sort all SchedReadWrites reachable via tablegen records.
// More may be inferred later when inferring new SchedClasses from variants.
void CodeGenSchedModels::collectSchedRW() { … }

/// Compute a SchedWrite name from a sequence of writes.
std::string CodeGenSchedModels::genRWName(ArrayRef<unsigned> Seq, bool IsRead) { … }

unsigned CodeGenSchedModels::getSchedRWIdx(const Record *Def,
                                           bool IsRead) const { … }

static void splitSchedReadWrites(const RecVec &RWDefs, RecVec &WriteDefs,
                                 RecVec &ReadDefs) { … }

// Split the SchedReadWrites defs and call findRWs for each list.
void CodeGenSchedModels::findRWs(const RecVec &RWDefs, IdxVec &Writes,
                                 IdxVec &Reads) const { … }

// Call getSchedRWIdx for all elements in a sequence of SchedRW defs.
void CodeGenSchedModels::findRWs(const RecVec &RWDefs, IdxVec &RWs,
                                 bool IsRead) const { … }

void CodeGenSchedModels::expandRWSequence(unsigned RWIdx, IdxVec &RWSeq,
                                          bool IsRead) const { … }

// Expand a SchedWrite as a sequence following any aliases that coincide with
// the given processor model.
void CodeGenSchedModels::expandRWSeqForProc(
    unsigned RWIdx, IdxVec &RWSeq, bool IsRead,
    const CodeGenProcModel &ProcModel) const { … }

// Find the existing SchedWrite that models this sequence of writes.
unsigned CodeGenSchedModels::findRWForSequence(ArrayRef<unsigned> Seq,
                                               bool IsRead) { … }

/// Add this ReadWrite if it doesn't already exist.
unsigned CodeGenSchedModels::findOrInsertRW(ArrayRef<unsigned> Seq,
                                            bool IsRead) { … }

/// Visit all the instruction definitions for this target to gather and
/// enumerate the itinerary classes. These are the explicitly specified
/// SchedClasses. More SchedClasses may be inferred.
void CodeGenSchedModels::collectSchedClasses() { … }

// Get the SchedClass index for an instruction.
unsigned
CodeGenSchedModels::getSchedClassIdx(const CodeGenInstruction &Inst) const { … }

std::string
CodeGenSchedModels::createSchedClassName(Record *ItinClassDef,
                                         ArrayRef<unsigned> OperWrites,
                                         ArrayRef<unsigned> OperReads) { … }

std::string CodeGenSchedModels::createSchedClassName(const RecVec &InstDefs) { … }

/// Add an inferred sched class from an itinerary class and per-operand list of
/// SchedWrites and SchedReads. ProcIndices contains the set of IDs of
/// processors that may utilize this class.
unsigned CodeGenSchedModels::addSchedClass(Record *ItinClassDef,
                                           ArrayRef<unsigned> OperWrites,
                                           ArrayRef<unsigned> OperReads,
                                           ArrayRef<unsigned> ProcIndices) { … }

// Create classes for each set of opcodes that are in the same InstReadWrite
// definition across all processors.
void CodeGenSchedModels::createInstRWClass(Record *InstRWDef) { … }

// True if collectProcItins found anything.
bool CodeGenSchedModels::hasItineraries() const { … }

// Gather the processor itineraries.
void CodeGenSchedModels::collectProcItins() { … }

// Gather the read/write types for each itinerary class.
void CodeGenSchedModels::collectProcItinRW() { … }

// Gather the unsupported features for processor models.
void CodeGenSchedModels::collectProcUnsupportedFeatures() { … }

/// Infer new classes from existing classes. In the process, this may create new
/// SchedWrites from sequences of existing SchedWrites.
void CodeGenSchedModels::inferSchedClasses() { … }

/// Infer classes from per-processor itinerary resources.
void CodeGenSchedModels::inferFromItinClass(Record *ItinClassDef,
                                            unsigned FromClassIdx) { … }

/// Infer classes from per-processor InstReadWrite definitions.
void CodeGenSchedModels::inferFromInstRWs(unsigned SCIdx) { … }

namespace {

// Helper for substituteVariantOperand.
struct TransVariant { … };

// Associate a predicate with the SchedReadWrite that it guards.
// RWIdx is the index of the read/write variant.
struct PredCheck { … };

// A Predicate transition is a list of RW sequences guarded by a PredTerm.
struct PredTransition { … };

// Encapsulate a set of partially constructed transitions.
// The results are built by repeated calls to substituteVariants.
class PredTransitions { … };

} // end anonymous namespace

// Return true if this predicate is mutually exclusive with a PredTerm. This
// degenerates into checking if the predicate is mutually exclusive with any
// predicate in the Term's conjunction.
//
// All predicates associated with a given SchedRW are considered mutually
// exclusive. This should work even if the conditions expressed by the
// predicates are not exclusive because the predicates for a given SchedWrite
// are always checked in the order they are defined in the .td file. Later
// conditions implicitly negate any prior condition.
bool PredTransitions::mutuallyExclusive(Record *PredDef,
                                        ArrayRef<Record *> Preds,
                                        ArrayRef<PredCheck> Term) { … }

static std::vector<Record *> getAllPredicates(ArrayRef<TransVariant> Variants,
                                              unsigned ProcId) { … }

// Populate IntersectingVariants with any variants or aliased sequences of the
// given SchedRW whose processor indices and predicates are not mutually
// exclusive with the given transition.
void PredTransitions::getIntersectingVariants(
    const CodeGenSchedRW &SchedRW, unsigned TransIdx,
    std::vector<TransVariant> &IntersectingVariants) { … }

// Push the Reads/Writes selected by this variant onto the PredTransition
// specified by VInfo.
void PredTransitions::pushVariant(const TransVariant &VInfo, bool IsRead) { … }

// RWSeq is a sequence of all Reads or all Writes for the next read or write
// operand. StartIdx is an index into TransVec where partial results
// starts. RWSeq must be applied to all transitions between StartIdx and the end
// of TransVec.
bool PredTransitions::substituteVariantOperand(
    const SmallVectorImpl<unsigned> &RWSeq, bool IsRead, unsigned StartIdx) { … }

// For each variant of a Read/Write in Trans, substitute the sequence of
// Read/Writes guarded by the variant. This is exponential in the number of
// variant Read/Writes, but in practice detection of mutually exclusive
// predicates should result in linear growth in the total number variants.
//
// This is one step in a breadth-first search of nested variants.
bool PredTransitions::substituteVariants(const PredTransition &Trans) { … }

static void addSequences(CodeGenSchedModels &SchedModels,
                         const SmallVectorImpl<SmallVector<unsigned, 4>> &Seqs,
                         IdxVec &Result, bool IsRead) { … }

#ifndef NDEBUG
static void dumpRecVec(const RecVec &RV) {
  for (const Record *R : RV)
    dbgs() << R->getName() << ", ";
}
#endif

static void dumpTransition(const CodeGenSchedModels &SchedModels,
                           const CodeGenSchedClass &FromSC,
                           const CodeGenSchedTransition &SCTrans,
                           const RecVec &Preds) { … }
// Create a new SchedClass for each variant found by inferFromRW. Pass
static void inferFromTransitions(ArrayRef<PredTransition> LastTransitions,
                                 unsigned FromClassIdx,
                                 CodeGenSchedModels &SchedModels) { … }

std::vector<unsigned> CodeGenSchedModels::getAllProcIndices() const { … }

static std::vector<PredTransition>
makePerProcessorTransitions(const PredTransition &Trans,
                            ArrayRef<unsigned> ProcIndices) { … }

// Create new SchedClasses for the given ReadWrite list. If any of the
// ReadWrites refers to a SchedVariant, create a new SchedClass for each variant
// of the ReadWrite list, following Aliases if necessary.
void CodeGenSchedModels::inferFromRW(ArrayRef<unsigned> OperWrites,
                                     ArrayRef<unsigned> OperReads,
                                     unsigned FromClassIdx,
                                     ArrayRef<unsigned> ProcIndices) { … }

// Check if any processor resource group contains all resource records in
// SubUnits.
bool CodeGenSchedModels::hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM) { … }

// Verify that overlapping groups have a common supergroup.
void CodeGenSchedModels::verifyProcResourceGroups(CodeGenProcModel &PM) { … }

// Collect all the RegisterFile definitions available in this target.
void CodeGenSchedModels::collectRegisterFiles() { … }

// Collect and sort WriteRes, ReadAdvance, and ProcResources.
void CodeGenSchedModels::collectProcResources() { … }

void CodeGenSchedModels::checkCompleteness() { … }

// Collect itinerary class resources for each processor.
void CodeGenSchedModels::collectItinProcResources(Record *ItinClassDef) { … }

void CodeGenSchedModels::collectRWResources(unsigned RWIdx, bool IsRead,
                                            ArrayRef<unsigned> ProcIndices) { … }

// Collect resources for a set of read/write types and processor indices.
void CodeGenSchedModels::collectRWResources(ArrayRef<unsigned> Writes,
                                            ArrayRef<unsigned> Reads,
                                            ArrayRef<unsigned> ProcIndices) { … }

// Find the processor's resource units for this kind of resource.
Record *CodeGenSchedModels::findProcResUnits(Record *ProcResKind,
                                             const CodeGenProcModel &PM,
                                             ArrayRef<SMLoc> Loc) const { … }

// Iteratively add a resource and its super resources.
void CodeGenSchedModels::addProcResource(Record *ProcResKind,
                                         CodeGenProcModel &PM,
                                         ArrayRef<SMLoc> Loc) { … }

// Add resources for a SchedWrite to this processor if they don't exist.
void CodeGenSchedModels::addWriteRes(Record *ProcWriteResDef, unsigned PIdx) { … }

// Add resources for a ReadAdvance to this processor if they don't exist.
void CodeGenSchedModels::addReadAdvance(Record *ProcReadAdvanceDef,
                                        unsigned PIdx) { … }

unsigned CodeGenProcModel::getProcResourceIdx(Record *PRDef) const { … }

bool CodeGenProcModel::isUnsupported(const CodeGenInstruction &Inst) const { … }

bool CodeGenProcModel::hasReadOfWrite(Record *WriteDef) const { … }

#ifndef NDEBUG
void CodeGenProcModel::dump() const {
  dbgs() << Index << ": " << ModelName << " "
         << (ModelDef ? ModelDef->getName() : "inferred") << " "
         << (ItinsDef ? ItinsDef->getName() : "no itinerary") << '\n';
}

void CodeGenSchedRW::dump() const {
  dbgs() << Name << (IsVariadic ? " (V) " : " ");
  if (IsSequence) {
    dbgs() << "(";
    dumpIdxVec(Sequence);
    dbgs() << ")";
  }
}

void CodeGenSchedClass::dump(const CodeGenSchedModels *SchedModels) const {
  dbgs() << "SCHEDCLASS " << Index << ":" << Name << '\n' << "  Writes: ";
  for (unsigned i = 0, N = Writes.size(); i < N; ++i) {
    SchedModels->getSchedWrite(Writes[i]).dump();
    if (i < N - 1) {
      dbgs() << '\n';
      dbgs().indent(10);
    }
  }
  dbgs() << "\n  Reads: ";
  for (unsigned i = 0, N = Reads.size(); i < N; ++i) {
    SchedModels->getSchedRead(Reads[i]).dump();
    if (i < N - 1) {
      dbgs() << '\n';
      dbgs().indent(10);
    }
  }
  dbgs() << "\n  ProcIdx: ";
  dumpIdxVec(ProcIndices);
  if (!Transitions.empty()) {
    dbgs() << "\n Transitions for Proc ";
    for (const CodeGenSchedTransition &Transition : Transitions) {
      dbgs() << Transition.ProcIndex << ", ";
    }
  }
  dbgs() << '\n';
}

void PredTransitions::dump() const {
  dbgs() << "Expanded Variants:\n";
  for (const auto &TI : TransVec) {
    dbgs() << "{";
    ListSeparator LS;
    for (const PredCheck &PC : TI.PredTerm)
      dbgs() << LS << SchedModels.getSchedRW(PC.RWIdx, PC.IsRead).Name << ":"
             << PC.Predicate->getName();
    dbgs() << "},\n  => {";
    for (SmallVectorImpl<SmallVector<unsigned, 4>>::const_iterator
             WSI = TI.WriteSequences.begin(),
             WSE = TI.WriteSequences.end();
         WSI != WSE; ++WSI) {
      dbgs() << "(";
      ListSeparator LS;
      for (unsigned N : *WSI)
        dbgs() << LS << SchedModels.getSchedWrite(N).Name;
      dbgs() << "),";
    }
    dbgs() << "}\n";
  }
}
#endif // NDEBUG
llvm/llvm/utils/TableGen/Common/CodeGenSchedule.cpp
