380 lines · cpp
1//===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine ----===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This class parses the Schedule.td file and produces an API that can be used10// to reason about whether an instruction can be added to a packet on a VLIW11// architecture. The class internally generates a deterministic finite12// automaton (DFA) that models all possible mappings of machine instructions13// to functional units as instructions are added to a packet.14//15//===----------------------------------------------------------------------===//16 17#include "Common/CodeGenSchedule.h"18#include "Common/CodeGenTarget.h"19#include "DFAEmitter.h"20#include "llvm/ADT/SmallVector.h"21#include "llvm/Support/Debug.h"22#include "llvm/Support/raw_ostream.h"23#include "llvm/TableGen/Record.h"24#include "llvm/TableGen/TableGenBackend.h"25#include <cassert>26#include <cstdint>27#include <deque>28#include <map>29#include <set>30#include <string>31#include <unordered_map>32#include <vector>33 34#define DEBUG_TYPE "dfa-emitter"35 36using namespace llvm;37 38// We use a uint64_t to represent a resource bitmask.39#define DFA_MAX_RESOURCES 6440 41namespace {42using ResourceVector = SmallVector<uint64_t, 4>;43 44struct ScheduleClass {45 /// The parent itinerary index (processor model ID).46 unsigned ItineraryID;47 48 /// Index within this itinerary of the schedule class.49 unsigned Idx;50 51 /// The index within the uniqued set of required resources of Resources.52 unsigned ResourcesIdx;53 54 /// Conjunctive list of resource requirements:55 /// {a|b, b|c} => (a OR b) AND (b or c).56 /// Resources are unique across all itineraries.57 ResourceVector Resources;58};59 60// Generates and prints out the DFA for resource tracking.61class DFAPacketizerEmitter {62private:63 std::string TargetName;64 const RecordKeeper &Records;65 66 UniqueVector<ResourceVector> UniqueResources;67 std::vector<ScheduleClass> ScheduleClasses;68 std::map<std::string, uint64_t> FUNameToBitsMap;69 std::map<unsigned, uint64_t> ComboBitToBitsMap;70 71public:72 DFAPacketizerEmitter(const RecordKeeper &R);73 74 // Construct a map of function unit names to bits.75 int collectAllFuncUnits(ArrayRef<const CodeGenProcModel *> ProcModels);76 77 // Construct a map from a combo function unit bit to the bits of all included78 // functional units.79 int collectAllComboFuncs(ArrayRef<const Record *> ComboFuncList);80 81 ResourceVector getResourcesForItinerary(const Record *Itinerary);82 void createScheduleClasses(unsigned ItineraryIdx,83 ArrayRef<const Record *> Itineraries);84 85 // Emit code for a subset of itineraries.86 void emitForItineraries(raw_ostream &OS,87 std::vector<const CodeGenProcModel *> &ProcItinList,88 std::string DFAName);89 90 void run(raw_ostream &OS);91};92} // end anonymous namespace93 94DFAPacketizerEmitter::DFAPacketizerEmitter(const RecordKeeper &R)95 : TargetName(CodeGenTarget(R).getName().str()), Records(R) {}96 97int DFAPacketizerEmitter::collectAllFuncUnits(98 ArrayRef<const CodeGenProcModel *> ProcModels) {99 LLVM_DEBUG(dbgs() << "-------------------------------------------------------"100 "----------------------\n");101 LLVM_DEBUG(dbgs() << "collectAllFuncUnits");102 LLVM_DEBUG(dbgs() << " (" << ProcModels.size() << " itineraries)\n");103 104 std::set<const Record *> ProcItinList;105 for (const CodeGenProcModel *Model : ProcModels)106 ProcItinList.insert(Model->ItinsDef);107 108 int TotalFUs = 0;109 // Parse functional units for all the itineraries.110 for (const Record *Proc : ProcItinList) {111 std::vector<const Record *> FUs = Proc->getValueAsListOfDefs("FU");112 113 LLVM_DEBUG(dbgs() << " FU:"114 << " (" << FUs.size() << " FUs) " << Proc->getName());115 116 // Convert macros to bits for each stage.117 unsigned numFUs = FUs.size();118 for (unsigned j = 0; j < numFUs; ++j) {119 assert((j < DFA_MAX_RESOURCES) &&120 "Exceeded maximum number of representable resources");121 uint64_t FuncResources = 1ULL << j;122 FUNameToBitsMap[FUs[j]->getName().str()] = FuncResources;123 LLVM_DEBUG(dbgs() << " " << FUs[j]->getName() << ":0x"124 << Twine::utohexstr(FuncResources));125 }126 TotalFUs += numFUs;127 LLVM_DEBUG(dbgs() << "\n");128 }129 return TotalFUs;130}131 132int DFAPacketizerEmitter::collectAllComboFuncs(133 ArrayRef<const Record *> ComboFuncList) {134 LLVM_DEBUG(dbgs() << "-------------------------------------------------------"135 "----------------------\n");136 LLVM_DEBUG(dbgs() << "collectAllComboFuncs");137 LLVM_DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n");138 139 int NumCombos = 0;140 for (unsigned I = 0, N = ComboFuncList.size(); I < N; ++I) {141 const Record *Func = ComboFuncList[I];142 std::vector<const Record *> FUs = Func->getValueAsListOfDefs("CFD");143 144 LLVM_DEBUG(dbgs() << " CFD:" << I << " (" << FUs.size() << " combo FUs) "145 << Func->getName() << "\n");146 147 // Convert macros to bits for each stage.148 for (unsigned J = 0, N = FUs.size(); J < N; ++J) {149 assert((J < DFA_MAX_RESOURCES) &&150 "Exceeded maximum number of DFA resources");151 const Record *FuncData = FUs[J];152 const Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc");153 const std::vector<const Record *> FuncList =154 FuncData->getValueAsListOfDefs("FuncList");155 const std::string &ComboFuncName = ComboFunc->getName().str();156 uint64_t ComboBit = FUNameToBitsMap[ComboFuncName];157 uint64_t ComboResources = ComboBit;158 LLVM_DEBUG(dbgs() << " combo: " << ComboFuncName << ":0x"159 << Twine::utohexstr(ComboResources) << "\n");160 for (const Record *K : FuncList) {161 std::string FuncName = K->getName().str();162 uint64_t FuncResources = FUNameToBitsMap[FuncName];163 LLVM_DEBUG(dbgs() << " " << FuncName << ":0x"164 << Twine::utohexstr(FuncResources) << "\n");165 ComboResources |= FuncResources;166 }167 ComboBitToBitsMap[ComboBit] = ComboResources;168 NumCombos++;169 LLVM_DEBUG(dbgs() << " => combo bits: " << ComboFuncName << ":0x"170 << Twine::utohexstr(ComboBit) << " = 0x"171 << Twine::utohexstr(ComboResources) << "\n");172 }173 }174 return NumCombos;175}176 177ResourceVector178DFAPacketizerEmitter::getResourcesForItinerary(const Record *Itinerary) {179 ResourceVector Resources;180 assert(Itinerary);181 for (const Record *StageDef : Itinerary->getValueAsListOfDefs("Stages")) {182 uint64_t StageResources = 0;183 for (const Record *Unit : StageDef->getValueAsListOfDefs("Units")) {184 StageResources |= FUNameToBitsMap[Unit->getName().str()];185 }186 if (StageResources != 0)187 Resources.push_back(StageResources);188 }189 return Resources;190}191 192void DFAPacketizerEmitter::createScheduleClasses(193 unsigned ItineraryIdx, ArrayRef<const Record *> Itineraries) {194 unsigned Idx = 0;195 for (const Record *Itinerary : Itineraries) {196 if (!Itinerary) {197 ScheduleClasses.push_back({ItineraryIdx, Idx++, 0, ResourceVector{}});198 continue;199 }200 ResourceVector Resources = getResourcesForItinerary(Itinerary);201 ScheduleClasses.push_back(202 {ItineraryIdx, Idx++, UniqueResources.insert(Resources), Resources});203 }204}205 206//207// Run the worklist algorithm to generate the DFA.208//209void DFAPacketizerEmitter::run(raw_ostream &OS) {210 emitSourceFileHeader("Target DFA Packetizer Tables", OS);211 OS << "\n"212 << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n";213 OS << "namespace llvm {\n";214 215 CodeGenTarget CGT(Records);216 CodeGenSchedModels CGS(Records, CGT);217 218 std::unordered_map<std::string, std::vector<const CodeGenProcModel *>>219 ItinsByNamespace;220 for (const CodeGenProcModel &ProcModel : CGS.procModels()) {221 if (ProcModel.hasItineraries()) {222 auto NS = ProcModel.ItinsDef->getValueAsString("PacketizerNamespace");223 ItinsByNamespace[NS.str()].push_back(&ProcModel);224 }225 }226 227 for (auto &KV : ItinsByNamespace)228 emitForItineraries(OS, KV.second, KV.first);229 OS << "} // end namespace llvm\n";230}231 232void DFAPacketizerEmitter::emitForItineraries(233 raw_ostream &OS, std::vector<const CodeGenProcModel *> &ProcModels,234 std::string DFAName) {235 OS << "} // end namespace llvm\n\n";236 OS << "namespace {\n";237 collectAllFuncUnits(ProcModels);238 collectAllComboFuncs(Records.getAllDerivedDefinitions("ComboFuncUnits"));239 240 // Collect the itineraries.241 DenseMap<const CodeGenProcModel *, unsigned> ProcModelStartIdx;242 for (const CodeGenProcModel *Model : ProcModels) {243 assert(Model->hasItineraries());244 ProcModelStartIdx[Model] = ScheduleClasses.size();245 createScheduleClasses(Model->Index, Model->ItinDefList);246 }247 248 // Output the mapping from ScheduleClass to ResourcesIdx.249 unsigned Idx = 0;250 OS << "constexpr unsigned " << TargetName << DFAName251 << "ResourceIndices[] = {";252 for (const ScheduleClass &SC : ScheduleClasses) {253 if (Idx++ % 32 == 0)254 OS << "\n ";255 OS << SC.ResourcesIdx << ", ";256 }257 OS << "\n};\n\n";258 259 // And the mapping from Itinerary index into the previous table.260 OS << "constexpr unsigned " << TargetName << DFAName261 << "ProcResourceIndexStart[] = {\n";262 OS << " 0, // NoSchedModel\n";263 for (const CodeGenProcModel *Model : ProcModels) {264 OS << " " << ProcModelStartIdx[Model] << ", // " << Model->ModelName265 << "\n";266 }267 OS << " " << ScheduleClasses.size() << "\n};\n\n";268 269 // Output the mapping from proc ID to ResourceIndexStart270 Idx = 1;271 OS << "int " << TargetName << DFAName272 << "GetResourceIndex(unsigned ProcID) { \n"273 << " static const unsigned " << TargetName << DFAName274 << "ProcIdToProcResourceIdxTable[][2] = {\n";275 for (const CodeGenProcModel *Model : ProcModels) {276 OS << " { " << Model->Index << ", " << Idx++ << " }, // "277 << Model->ModelName << "\n";278 }279 OS << " };\n"280 << " auto It = llvm::lower_bound(" << TargetName << DFAName281 << "ProcIdToProcResourceIdxTable, ProcID,\n"282 << " [](const unsigned LHS[], unsigned Val) { return LHS[0] < Val; "283 "});\n"284 << " assert(*It[0] == ProcID);\n"285 << " return (*It)[1];\n"286 << "}\n\n";287 288 // The type of a state in the nondeterministic automaton we're defining.289 using NfaStateTy = uint64_t;290 291 // Given a resource state, return all resource states by applying292 // InsnClass.293 auto ApplyInsnClass = [&](const ResourceVector &InsnClass,294 NfaStateTy State) -> std::deque<NfaStateTy> {295 std::deque<NfaStateTy> V(1, State);296 // Apply every stage in the class individually.297 for (NfaStateTy Stage : InsnClass) {298 // Apply this stage to every existing member of V in turn.299 size_t Sz = V.size();300 for (unsigned I = 0; I < Sz; ++I) {301 NfaStateTy S = V.front();302 V.pop_front();303 304 // For this stage, state combination, try all possible resources.305 for (unsigned J = 0; J < DFA_MAX_RESOURCES; ++J) {306 NfaStateTy ResourceMask = 1ULL << J;307 if ((ResourceMask & Stage) == 0)308 // This resource isn't required by this stage.309 continue;310 NfaStateTy Combo = ComboBitToBitsMap[ResourceMask];311 if (Combo && ((~S & Combo) != Combo))312 // This combo units bits are not available.313 continue;314 NfaStateTy ResultingResourceState = S | ResourceMask | Combo;315 if (ResultingResourceState == S)316 continue;317 V.push_back(ResultingResourceState);318 }319 }320 }321 return V;322 };323 324 // Given a resource state, return a quick (conservative) guess as to whether325 // InsnClass can be applied. This is a filter for the more heavyweight326 // ApplyInsnClass.327 auto canApplyInsnClass = [](const ResourceVector &InsnClass,328 NfaStateTy State) -> bool {329 for (NfaStateTy Resources : InsnClass) {330 if ((State | Resources) == State)331 return false;332 }333 return true;334 };335 336 DfaEmitter Emitter;337 std::deque<NfaStateTy> Worklist(1, 0);338 std::set<NfaStateTy> SeenStates;339 SeenStates.insert(Worklist.front());340 while (!Worklist.empty()) {341 NfaStateTy State = Worklist.front();342 Worklist.pop_front();343 for (const ResourceVector &Resources : UniqueResources) {344 if (!canApplyInsnClass(Resources, State))345 continue;346 unsigned ResourcesID = UniqueResources.idFor(Resources);347 for (uint64_t NewState : ApplyInsnClass(Resources, State)) {348 if (SeenStates.emplace(NewState).second)349 Worklist.emplace_back(NewState);350 Emitter.addTransition(State, NewState, ResourcesID);351 }352 }353 }354 355 std::string TargetAndDFAName = TargetName + DFAName;356 Emitter.emit(TargetAndDFAName, OS);357 OS << "} // end anonymous namespace\n\n";358 359 std::string SubTargetClassName = TargetName + "GenSubtargetInfo";360 OS << "namespace llvm {\n";361 OS << "DFAPacketizer *" << SubTargetClassName << "::" << "create" << DFAName362 << "DFAPacketizer(const InstrItineraryData *IID) const {\n"363 << " static Automaton<uint64_t> A(ArrayRef<" << TargetAndDFAName364 << "Transition>(" << TargetAndDFAName << "Transitions), "365 << TargetAndDFAName << "TransitionInfo);\n"366 << " unsigned Index = " << TargetName << DFAName367 << "GetResourceIndex(IID->SchedModel.ProcID);\n"368 << " unsigned ProcResIdxStart = " << TargetAndDFAName369 << "ProcResourceIndexStart[Index];\n"370 << " unsigned ProcResIdxNum = " << TargetAndDFAName371 << "ProcResourceIndexStart[Index + 1] - "372 "ProcResIdxStart;\n"373 << " return new DFAPacketizer(IID, A, {&" << TargetAndDFAName374 << "ResourceIndices[ProcResIdxStart], ProcResIdxNum});\n"375 << "\n}\n\n";376}377 378static TableGen::Emitter::OptClass<DFAPacketizerEmitter>379 X("gen-dfa-packetizer", "Generate DFA Packetizer for VLIW targets");380