diff options
Diffstat (limited to 'llvm/utils/TableGen/DFAPacketizerEmitter.cpp')
| -rw-r--r-- | llvm/utils/TableGen/DFAPacketizerEmitter.cpp | 555 |
1 files changed, 555 insertions, 0 deletions
diff --git a/llvm/utils/TableGen/DFAPacketizerEmitter.cpp b/llvm/utils/TableGen/DFAPacketizerEmitter.cpp new file mode 100644 index 000000000000..ccb4ef1b9678 --- /dev/null +++ b/llvm/utils/TableGen/DFAPacketizerEmitter.cpp @@ -0,0 +1,555 @@ +//===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine ----===// +// +// 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 class parses the Schedule.td file and produces an API that can be used +// to reason about whether an instruction can be added to a packet on a VLIW +// architecture. The class internally generates a deterministic finite +// automaton (DFA) that models all possible mappings of machine instructions +// to functional units as instructions are added to a packet. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "dfa-emitter" + +#include "CodeGenTarget.h" +#include "DFAEmitter.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/TableGen/Record.h" +#include "llvm/TableGen/TableGenBackend.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include <cassert> +#include <cstdint> +#include <map> +#include <set> +#include <string> +#include <unordered_map> +#include <vector> + +using namespace llvm; + +// -------------------------------------------------------------------- +// Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp + +// DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput. +// This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer. +// +// e.g. terms x resource bit combinations that fit in uint32_t: +// 4 terms x 8 bits = 32 bits +// 3 terms x 10 bits = 30 bits +// 2 terms x 16 bits = 32 bits +// +// e.g. terms x resource bit combinations that fit in uint64_t: +// 8 terms x 8 bits = 64 bits +// 7 terms x 9 bits = 63 bits +// 6 terms x 10 bits = 60 bits +// 5 terms x 12 bits = 60 bits +// 4 terms x 16 bits = 64 bits <--- current +// 3 terms x 21 bits = 63 bits +// 2 terms x 32 bits = 64 bits +// +#define DFA_MAX_RESTERMS 4 // The max # of AND'ed resource terms. +#define DFA_MAX_RESOURCES 16 // The max # of resource bits in one term. + +typedef uint64_t DFAInput; +typedef int64_t DFAStateInput; +#define DFA_TBLTYPE "int64_t" // For generating DFAStateInputTable. + +namespace { + + DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) { + return (Inp << DFA_MAX_RESOURCES) | FuncUnits; + } + + /// Return the DFAInput for an instruction class input vector. + /// This function is used in both DFAPacketizer.cpp and in + /// DFAPacketizerEmitter.cpp. + DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) { + DFAInput InsnInput = 0; + assert((InsnClass.size() <= DFA_MAX_RESTERMS) && + "Exceeded maximum number of DFA terms"); + for (auto U : InsnClass) + InsnInput = addDFAFuncUnits(InsnInput, U); + return InsnInput; + } + +} // end anonymous namespace + +// -------------------------------------------------------------------- + +#ifndef NDEBUG +// To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter". +// +// dbgsInsnClass - When debugging, print instruction class stages. +// +void dbgsInsnClass(const std::vector<unsigned> &InsnClass); +// +// dbgsStateInfo - When debugging, print the set of state info. +// +void dbgsStateInfo(const std::set<unsigned> &stateInfo); +// +// dbgsIndent - When debugging, indent by the specified amount. +// +void dbgsIndent(unsigned indent); +#endif + +// +// class DFAPacketizerEmitter: class that generates and prints out the DFA +// for resource tracking. +// +namespace { + +class DFAPacketizerEmitter { +private: + std::string TargetName; + // + // allInsnClasses is the set of all possible resources consumed by an + // InstrStage. + // + std::vector<std::vector<unsigned>> allInsnClasses; + RecordKeeper &Records; + +public: + DFAPacketizerEmitter(RecordKeeper &R); + + // + // collectAllFuncUnits - Construct a map of function unit names to bits. + // + int collectAllFuncUnits(std::vector<Record*> &ProcItinList, + std::map<std::string, unsigned> &FUNameToBitsMap, + int &maxResources, + raw_ostream &OS); + + // + // collectAllComboFuncs - Construct a map from a combo function unit bit to + // the bits of all included functional units. + // + int collectAllComboFuncs(std::vector<Record*> &ComboFuncList, + std::map<std::string, unsigned> &FUNameToBitsMap, + std::map<unsigned, unsigned> &ComboBitToBitsMap, + raw_ostream &OS); + + // + // collectOneInsnClass - Populate allInsnClasses with one instruction class. + // + int collectOneInsnClass(const std::string &ProcName, + std::vector<Record*> &ProcItinList, + std::map<std::string, unsigned> &FUNameToBitsMap, + Record *ItinData, + raw_ostream &OS); + + // + // collectAllInsnClasses - Populate allInsnClasses which is a set of units + // used in each stage. + // + int collectAllInsnClasses(const std::string &ProcName, + std::vector<Record*> &ProcItinList, + std::map<std::string, unsigned> &FUNameToBitsMap, + std::vector<Record*> &ItinDataList, + int &maxStages, + raw_ostream &OS); + + // Emit code for a subset of itineraries. + void emitForItineraries(raw_ostream &OS, + std::vector<Record *> &ProcItinList, + std::string DFAName); + + void run(raw_ostream &OS); +}; +} // end anonymous namespace + +#ifndef NDEBUG +// To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter". +// +// dbgsInsnClass - When debugging, print instruction class stages. +// +void dbgsInsnClass(const std::vector<unsigned> &InsnClass) { + LLVM_DEBUG(dbgs() << "InsnClass: "); + for (unsigned i = 0; i < InsnClass.size(); ++i) { + if (i > 0) { + LLVM_DEBUG(dbgs() << ", "); + } + LLVM_DEBUG(dbgs() << "0x" << Twine::utohexstr(InsnClass[i])); + } + DFAInput InsnInput = getDFAInsnInput(InsnClass); + LLVM_DEBUG(dbgs() << " (input: 0x" << Twine::utohexstr(InsnInput) << ")"); +} + +// +// dbgsIndent - When debugging, indent by the specified amount. +// +void dbgsIndent(unsigned indent) { + for (unsigned i = 0; i < indent; ++i) { + LLVM_DEBUG(dbgs() << " "); + } +} +#endif // NDEBUG + +DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R): + TargetName(CodeGenTarget(R).getName()), Records(R) {} + +// +// collectAllFuncUnits - Construct a map of function unit names to bits. +// +int DFAPacketizerEmitter::collectAllFuncUnits( + std::vector<Record*> &ProcItinList, + std::map<std::string, unsigned> &FUNameToBitsMap, + int &maxFUs, + raw_ostream &OS) { + LLVM_DEBUG(dbgs() << "-------------------------------------------------------" + "----------------------\n"); + LLVM_DEBUG(dbgs() << "collectAllFuncUnits"); + LLVM_DEBUG(dbgs() << " (" << ProcItinList.size() << " itineraries)\n"); + + int totalFUs = 0; + // Parse functional units for all the itineraries. + for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) { + Record *Proc = ProcItinList[i]; + std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU"); + + LLVM_DEBUG(dbgs() << " FU:" << i << " (" << FUs.size() << " FUs) " + << Proc->getName()); + + // Convert macros to bits for each stage. + unsigned numFUs = FUs.size(); + for (unsigned j = 0; j < numFUs; ++j) { + assert ((j < DFA_MAX_RESOURCES) && + "Exceeded maximum number of representable resources"); + unsigned FuncResources = (unsigned) (1U << j); + FUNameToBitsMap[FUs[j]->getName()] = FuncResources; + LLVM_DEBUG(dbgs() << " " << FUs[j]->getName() << ":0x" + << Twine::utohexstr(FuncResources)); + } + if (((int) numFUs) > maxFUs) { + maxFUs = numFUs; + } + totalFUs += numFUs; + LLVM_DEBUG(dbgs() << "\n"); + } + return totalFUs; +} + +// +// collectAllComboFuncs - Construct a map from a combo function unit bit to +// the bits of all included functional units. +// +int DFAPacketizerEmitter::collectAllComboFuncs( + std::vector<Record*> &ComboFuncList, + std::map<std::string, unsigned> &FUNameToBitsMap, + std::map<unsigned, unsigned> &ComboBitToBitsMap, + raw_ostream &OS) { + LLVM_DEBUG(dbgs() << "-------------------------------------------------------" + "----------------------\n"); + LLVM_DEBUG(dbgs() << "collectAllComboFuncs"); + LLVM_DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n"); + + int numCombos = 0; + for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) { + Record *Func = ComboFuncList[i]; + std::vector<Record*> FUs = Func->getValueAsListOfDefs("CFD"); + + LLVM_DEBUG(dbgs() << " CFD:" << i << " (" << FUs.size() << " combo FUs) " + << Func->getName() << "\n"); + + // Convert macros to bits for each stage. + for (unsigned j = 0, N = FUs.size(); j < N; ++j) { + assert ((j < DFA_MAX_RESOURCES) && + "Exceeded maximum number of DFA resources"); + Record *FuncData = FUs[j]; + Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc"); + const std::vector<Record*> &FuncList = + FuncData->getValueAsListOfDefs("FuncList"); + const std::string &ComboFuncName = ComboFunc->getName(); + unsigned ComboBit = FUNameToBitsMap[ComboFuncName]; + unsigned ComboResources = ComboBit; + LLVM_DEBUG(dbgs() << " combo: " << ComboFuncName << ":0x" + << Twine::utohexstr(ComboResources) << "\n"); + for (unsigned k = 0, M = FuncList.size(); k < M; ++k) { + std::string FuncName = FuncList[k]->getName(); + unsigned FuncResources = FUNameToBitsMap[FuncName]; + LLVM_DEBUG(dbgs() << " " << FuncName << ":0x" + << Twine::utohexstr(FuncResources) << "\n"); + ComboResources |= FuncResources; + } + ComboBitToBitsMap[ComboBit] = ComboResources; + numCombos++; + LLVM_DEBUG(dbgs() << " => combo bits: " << ComboFuncName << ":0x" + << Twine::utohexstr(ComboBit) << " = 0x" + << Twine::utohexstr(ComboResources) << "\n"); + } + } + return numCombos; +} + +// +// collectOneInsnClass - Populate allInsnClasses with one instruction class +// +int DFAPacketizerEmitter::collectOneInsnClass(const std::string &ProcName, + std::vector<Record*> &ProcItinList, + std::map<std::string, unsigned> &FUNameToBitsMap, + Record *ItinData, + raw_ostream &OS) { + const std::vector<Record*> &StageList = + ItinData->getValueAsListOfDefs("Stages"); + + // The number of stages. + unsigned NStages = StageList.size(); + + LLVM_DEBUG(dbgs() << " " << ItinData->getValueAsDef("TheClass")->getName() + << "\n"); + + std::vector<unsigned> UnitBits; + + // Compute the bitwise or of each unit used in this stage. + for (unsigned i = 0; i < NStages; ++i) { + const Record *Stage = StageList[i]; + + // Get unit list. + const std::vector<Record*> &UnitList = + Stage->getValueAsListOfDefs("Units"); + + LLVM_DEBUG(dbgs() << " stage:" << i << " [" << UnitList.size() + << " units]:"); + unsigned dbglen = 26; // cursor after stage dbgs + + // Compute the bitwise or of each unit used in this stage. + unsigned UnitBitValue = 0; + for (unsigned j = 0, M = UnitList.size(); j < M; ++j) { + // Conduct bitwise or. + std::string UnitName = UnitList[j]->getName(); + LLVM_DEBUG(dbgs() << " " << j << ":" << UnitName); + dbglen += 3 + UnitName.length(); + assert(FUNameToBitsMap.count(UnitName)); + UnitBitValue |= FUNameToBitsMap[UnitName]; + } + + if (UnitBitValue != 0) + UnitBits.push_back(UnitBitValue); + + while (dbglen <= 64) { // line up bits dbgs + dbglen += 8; + LLVM_DEBUG(dbgs() << "\t"); + } + LLVM_DEBUG(dbgs() << " (bits: 0x" << Twine::utohexstr(UnitBitValue) + << ")\n"); + } + + if (!UnitBits.empty()) + allInsnClasses.push_back(UnitBits); + + LLVM_DEBUG({ + dbgs() << " "; + dbgsInsnClass(UnitBits); + dbgs() << "\n"; + }); + + return NStages; +} + +// +// collectAllInsnClasses - Populate allInsnClasses which is a set of units +// used in each stage. +// +int DFAPacketizerEmitter::collectAllInsnClasses(const std::string &ProcName, + std::vector<Record*> &ProcItinList, + std::map<std::string, unsigned> &FUNameToBitsMap, + std::vector<Record*> &ItinDataList, + int &maxStages, + raw_ostream &OS) { + // Collect all instruction classes. + unsigned M = ItinDataList.size(); + + int numInsnClasses = 0; + LLVM_DEBUG(dbgs() << "-------------------------------------------------------" + "----------------------\n" + << "collectAllInsnClasses " << ProcName << " (" << M + << " classes)\n"); + + // Collect stages for each instruction class for all itinerary data + for (unsigned j = 0; j < M; j++) { + Record *ItinData = ItinDataList[j]; + int NStages = collectOneInsnClass(ProcName, ProcItinList, + FUNameToBitsMap, ItinData, OS); + if (NStages > maxStages) { + maxStages = NStages; + } + numInsnClasses++; + } + return numInsnClasses; +} + +// +// Run the worklist algorithm to generate the DFA. +// +void DFAPacketizerEmitter::run(raw_ostream &OS) { + OS << "\n" + << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n"; + OS << "namespace llvm {\n"; + + OS << "\n// Input format:\n"; + OS << "#define DFA_MAX_RESTERMS " << DFA_MAX_RESTERMS + << "\t// maximum AND'ed resource terms\n"; + OS << "#define DFA_MAX_RESOURCES " << DFA_MAX_RESOURCES + << "\t// maximum resource bits in one term\n"; + + // Collect processor iteraries. + std::vector<Record*> ProcItinList = + Records.getAllDerivedDefinitions("ProcessorItineraries"); + + std::unordered_map<std::string, std::vector<Record*>> ItinsByNamespace; + for (Record *R : ProcItinList) + ItinsByNamespace[R->getValueAsString("PacketizerNamespace")].push_back(R); + + for (auto &KV : ItinsByNamespace) + emitForItineraries(OS, KV.second, KV.first); + OS << "} // end namespace llvm\n"; +} + +void DFAPacketizerEmitter::emitForItineraries( + raw_ostream &OS, std::vector<Record *> &ProcItinList, + std::string DFAName) { + // + // Collect the Functional units. + // + std::map<std::string, unsigned> FUNameToBitsMap; + int maxResources = 0; + collectAllFuncUnits(ProcItinList, + FUNameToBitsMap, maxResources, OS); + + // + // Collect the Combo Functional units. + // + std::map<unsigned, unsigned> ComboBitToBitsMap; + std::vector<Record*> ComboFuncList = + Records.getAllDerivedDefinitions("ComboFuncUnits"); + collectAllComboFuncs(ComboFuncList, FUNameToBitsMap, ComboBitToBitsMap, OS); + + // + // Collect the itineraries. + // + int maxStages = 0; + int numInsnClasses = 0; + for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) { + Record *Proc = ProcItinList[i]; + + // Get processor itinerary name. + const std::string &ProcName = Proc->getName(); + + // Skip default. + if (ProcName == "NoItineraries") + continue; + + // Sanity check for at least one instruction itinerary class. + unsigned NItinClasses = + Records.getAllDerivedDefinitions("InstrItinClass").size(); + if (NItinClasses == 0) + return; + + // Get itinerary data list. + std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID"); + + // Collect all instruction classes + numInsnClasses += collectAllInsnClasses(ProcName, ProcItinList, + FUNameToBitsMap, ItinDataList, maxStages, OS); + } + + // The type of a state in the nondeterministic automaton we're defining. + using NfaStateTy = unsigned; + + // Given a resource state, return all resource states by applying + // InsnClass. + auto applyInsnClass = [&](ArrayRef<unsigned> InsnClass, + NfaStateTy State) -> std::deque<unsigned> { + std::deque<unsigned> V(1, State); + // Apply every stage in the class individually. + for (unsigned Stage : InsnClass) { + // Apply this stage to every existing member of V in turn. + size_t Sz = V.size(); + for (unsigned I = 0; I < Sz; ++I) { + unsigned S = V.front(); + V.pop_front(); + + // For this stage, state combination, try all possible resources. + for (unsigned J = 0; J < DFA_MAX_RESOURCES; ++J) { + unsigned ResourceMask = 1U << J; + if ((ResourceMask & Stage) == 0) + // This resource isn't required by this stage. + continue; + unsigned Combo = ComboBitToBitsMap[ResourceMask]; + if (Combo && ((~S & Combo) != Combo)) + // This combo units bits are not available. + continue; + unsigned ResultingResourceState = S | ResourceMask | Combo; + if (ResultingResourceState == S) + continue; + V.push_back(ResultingResourceState); + } + } + } + return V; + }; + + // Given a resource state, return a quick (conservative) guess as to whether + // InsnClass can be applied. This is a filter for the more heavyweight + // applyInsnClass. + auto canApplyInsnClass = [](ArrayRef<unsigned> InsnClass, + NfaStateTy State) -> bool { + for (unsigned Resources : InsnClass) { + if ((State | Resources) == State) + return false; + } + return true; + }; + + DfaEmitter Emitter; + std::deque<NfaStateTy> Worklist(1, 0); + std::set<NfaStateTy> SeenStates; + SeenStates.insert(Worklist.front()); + while (!Worklist.empty()) { + NfaStateTy State = Worklist.front(); + Worklist.pop_front(); + for (unsigned i = 0; i < allInsnClasses.size(); i++) { + const std::vector<unsigned> &InsnClass = allInsnClasses[i]; + if (!canApplyInsnClass(InsnClass, State)) + continue; + for (unsigned NewState : applyInsnClass(InsnClass, State)) { + if (SeenStates.emplace(NewState).second) + Worklist.emplace_back(NewState); + Emitter.addTransition(State, NewState, getDFAInsnInput(InsnClass)); + } + } + } + + OS << "} // end namespace llvm\n\n"; + OS << "namespace {\n"; + std::string TargetAndDFAName = TargetName + DFAName; + Emitter.emit(TargetAndDFAName, OS); + OS << "} // end anonymous namespace\n\n"; + + std::string SubTargetClassName = TargetName + "GenSubtargetInfo"; + OS << "namespace llvm {\n"; + OS << "DFAPacketizer *" << SubTargetClassName << "::" + << "create" << DFAName + << "DFAPacketizer(const InstrItineraryData *IID) const {\n" + << " static Automaton<uint64_t> A(ArrayRef<" << TargetAndDFAName + << "Transition>(" << TargetAndDFAName << "Transitions), " + << TargetAndDFAName << "TransitionInfo);\n" + << " return new DFAPacketizer(IID, A);\n" + << "\n}\n\n"; +} + +namespace llvm { + +void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) { + emitSourceFileHeader("Target DFA Packetizer Tables", OS); + DFAPacketizerEmitter(RK).run(OS); +} + +} // end namespace llvm |