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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This class parses the Schedule.td file and produces an API that can be used 10 // to reason about whether an instruction can be added to a packet on a VLIW 11 // architecture. The class internally generates a deterministic finite 12 // automaton (DFA) that models all possible mappings of machine instructions 13 // to functional units as instructions are added to a packet. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #define DEBUG_TYPE "dfa-emitter" 18 19 #include "CodeGenSchedule.h" 20 #include "CodeGenTarget.h" 21 #include "DFAEmitter.h" 22 #include "llvm/ADT/DenseSet.h" 23 #include "llvm/ADT/SmallVector.h" 24 #include "llvm/ADT/StringExtras.h" 25 #include "llvm/Support/Debug.h" 26 #include "llvm/Support/raw_ostream.h" 27 #include "llvm/TableGen/Record.h" 28 #include "llvm/TableGen/TableGenBackend.h" 29 #include <cassert> 30 #include <cstdint> 31 #include <map> 32 #include <set> 33 #include <string> 34 #include <unordered_map> 35 #include <vector> 36 37 using namespace llvm; 38 39 // We use a uint64_t to represent a resource bitmask. 40 #define DFA_MAX_RESOURCES 64 41 42 namespace { 43 using ResourceVector = SmallVector<uint64_t, 4>; 44 45 struct ScheduleClass { 46 /// The parent itinerary index (processor model ID). 47 unsigned ItineraryID; 48 49 /// Index within this itinerary of the schedule class. 50 unsigned Idx; 51 52 /// The index within the uniqued set of required resources of Resources. 53 unsigned ResourcesIdx; 54 55 /// Conjunctive list of resource requirements: 56 /// {a|b, b|c} => (a OR b) AND (b or c). 57 /// Resources are unique across all itineraries. 58 ResourceVector Resources; 59 }; 60 61 // Generates and prints out the DFA for resource tracking. 62 class DFAPacketizerEmitter { 63 private: 64 std::string TargetName; 65 RecordKeeper &Records; 66 67 UniqueVector<ResourceVector> UniqueResources; 68 std::vector<ScheduleClass> ScheduleClasses; 69 std::map<std::string, uint64_t> FUNameToBitsMap; 70 std::map<unsigned, uint64_t> ComboBitToBitsMap; 71 72 public: 73 DFAPacketizerEmitter(RecordKeeper &R); 74 75 // Construct a map of function unit names to bits. 76 int collectAllFuncUnits( 77 ArrayRef<const CodeGenProcModel *> ProcModels); 78 79 // Construct a map from a combo function unit bit to the bits of all included 80 // functional units. 81 int collectAllComboFuncs(ArrayRef<Record *> ComboFuncList); 82 83 ResourceVector getResourcesForItinerary(Record *Itinerary); 84 void createScheduleClasses(unsigned ItineraryIdx, const RecVec &Itineraries); 85 86 // Emit code for a subset of itineraries. 87 void emitForItineraries(raw_ostream &OS, 88 std::vector<const CodeGenProcModel *> &ProcItinList, 89 std::string DFAName); 90 91 void run(raw_ostream &OS); 92 }; 93 } // end anonymous namespace 94 95 DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R) 96 : TargetName(std::string(CodeGenTarget(R).getName())), Records(R) {} 97 98 int DFAPacketizerEmitter::collectAllFuncUnits( 99 ArrayRef<const CodeGenProcModel *> ProcModels) { 100 LLVM_DEBUG(dbgs() << "-------------------------------------------------------" 101 "----------------------\n"); 102 LLVM_DEBUG(dbgs() << "collectAllFuncUnits"); 103 LLVM_DEBUG(dbgs() << " (" << ProcModels.size() << " itineraries)\n"); 104 105 std::set<Record *> ProcItinList; 106 for (const CodeGenProcModel *Model : ProcModels) 107 ProcItinList.insert(Model->ItinsDef); 108 109 int totalFUs = 0; 110 // Parse functional units for all the itineraries. 111 for (Record *Proc : ProcItinList) { 112 std::vector<Record *> FUs = Proc->getValueAsListOfDefs("FU"); 113 114 LLVM_DEBUG(dbgs() << " FU:" 115 << " (" << FUs.size() << " FUs) " << Proc->getName()); 116 117 // Convert macros to bits for each stage. 118 unsigned numFUs = FUs.size(); 119 for (unsigned j = 0; j < numFUs; ++j) { 120 assert((j < DFA_MAX_RESOURCES) && 121 "Exceeded maximum number of representable resources"); 122 uint64_t FuncResources = 1ULL << j; 123 FUNameToBitsMap[std::string(FUs[j]->getName())] = FuncResources; 124 LLVM_DEBUG(dbgs() << " " << FUs[j]->getName() << ":0x" 125 << Twine::utohexstr(FuncResources)); 126 } 127 totalFUs += numFUs; 128 LLVM_DEBUG(dbgs() << "\n"); 129 } 130 return totalFUs; 131 } 132 133 int DFAPacketizerEmitter::collectAllComboFuncs(ArrayRef<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 Record *Func = ComboFuncList[i]; 142 std::vector<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 Record *FuncData = FUs[j]; 152 Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc"); 153 const std::vector<Record *> &FuncList = 154 FuncData->getValueAsListOfDefs("FuncList"); 155 const std::string &ComboFuncName = std::string(ComboFunc->getName()); 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 (unsigned k = 0, M = FuncList.size(); k < M; ++k) { 161 std::string FuncName = std::string(FuncList[k]->getName()); 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 177 ResourceVector 178 DFAPacketizerEmitter::getResourcesForItinerary(Record *Itinerary) { 179 ResourceVector Resources; 180 assert(Itinerary); 181 for (Record *StageDef : Itinerary->getValueAsListOfDefs("Stages")) { 182 uint64_t StageResources = 0; 183 for (Record *Unit : StageDef->getValueAsListOfDefs("Units")) { 184 StageResources |= FUNameToBitsMap[std::string(Unit->getName())]; 185 } 186 if (StageResources != 0) 187 Resources.push_back(StageResources); 188 } 189 return Resources; 190 } 191 192 void DFAPacketizerEmitter::createScheduleClasses(unsigned ItineraryIdx, 193 const RecVec &Itineraries) { 194 unsigned Idx = 0; 195 for (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 // 209 void DFAPacketizerEmitter::run(raw_ostream &OS) { 210 OS << "\n" 211 << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n"; 212 OS << "namespace llvm {\n"; 213 214 CodeGenTarget CGT(Records); 215 CodeGenSchedModels CGS(Records, CGT); 216 217 std::unordered_map<std::string, std::vector<const CodeGenProcModel *>> 218 ItinsByNamespace; 219 for (const CodeGenProcModel &ProcModel : CGS.procModels()) { 220 if (ProcModel.hasItineraries()) { 221 auto NS = ProcModel.ItinsDef->getValueAsString("PacketizerNamespace"); 222 ItinsByNamespace[std::string(NS)].push_back(&ProcModel); 223 } 224 } 225 226 for (auto &KV : ItinsByNamespace) 227 emitForItineraries(OS, KV.second, KV.first); 228 OS << "} // end namespace llvm\n"; 229 } 230 231 void DFAPacketizerEmitter::emitForItineraries( 232 raw_ostream &OS, std::vector<const CodeGenProcModel *> &ProcModels, 233 std::string DFAName) { 234 OS << "} // end namespace llvm\n\n"; 235 OS << "namespace {\n"; 236 collectAllFuncUnits(ProcModels); 237 collectAllComboFuncs(Records.getAllDerivedDefinitions("ComboFuncUnits")); 238 239 // Collect the itineraries. 240 DenseMap<const CodeGenProcModel *, unsigned> ProcModelStartIdx; 241 for (const CodeGenProcModel *Model : ProcModels) { 242 assert(Model->hasItineraries()); 243 ProcModelStartIdx[Model] = ScheduleClasses.size(); 244 createScheduleClasses(Model->Index, Model->ItinDefList); 245 } 246 247 // Output the mapping from ScheduleClass to ResourcesIdx. 248 unsigned Idx = 0; 249 OS << "constexpr unsigned " << TargetName << DFAName 250 << "ResourceIndices[] = {"; 251 for (const ScheduleClass &SC : ScheduleClasses) { 252 if (Idx++ % 32 == 0) 253 OS << "\n "; 254 OS << SC.ResourcesIdx << ", "; 255 } 256 OS << "\n};\n\n"; 257 258 // And the mapping from Itinerary index into the previous table. 259 OS << "constexpr unsigned " << TargetName << DFAName 260 << "ProcResourceIndexStart[] = {\n"; 261 OS << " 0, // NoSchedModel\n"; 262 for (const CodeGenProcModel *Model : ProcModels) { 263 OS << " " << ProcModelStartIdx[Model] << ", // " << Model->ModelName 264 << "\n"; 265 } 266 OS << " " << ScheduleClasses.size() << "\n};\n\n"; 267 268 // The type of a state in the nondeterministic automaton we're defining. 269 using NfaStateTy = uint64_t; 270 271 // Given a resource state, return all resource states by applying 272 // InsnClass. 273 auto applyInsnClass = [&](const ResourceVector &InsnClass, 274 NfaStateTy State) -> std::deque<NfaStateTy> { 275 std::deque<NfaStateTy> V(1, State); 276 // Apply every stage in the class individually. 277 for (NfaStateTy Stage : InsnClass) { 278 // Apply this stage to every existing member of V in turn. 279 size_t Sz = V.size(); 280 for (unsigned I = 0; I < Sz; ++I) { 281 NfaStateTy S = V.front(); 282 V.pop_front(); 283 284 // For this stage, state combination, try all possible resources. 285 for (unsigned J = 0; J < DFA_MAX_RESOURCES; ++J) { 286 NfaStateTy ResourceMask = 1ULL << J; 287 if ((ResourceMask & Stage) == 0) 288 // This resource isn't required by this stage. 289 continue; 290 NfaStateTy Combo = ComboBitToBitsMap[ResourceMask]; 291 if (Combo && ((~S & Combo) != Combo)) 292 // This combo units bits are not available. 293 continue; 294 NfaStateTy ResultingResourceState = S | ResourceMask | Combo; 295 if (ResultingResourceState == S) 296 continue; 297 V.push_back(ResultingResourceState); 298 } 299 } 300 } 301 return V; 302 }; 303 304 // Given a resource state, return a quick (conservative) guess as to whether 305 // InsnClass can be applied. This is a filter for the more heavyweight 306 // applyInsnClass. 307 auto canApplyInsnClass = [](const ResourceVector &InsnClass, 308 NfaStateTy State) -> bool { 309 for (NfaStateTy Resources : InsnClass) { 310 if ((State | Resources) == State) 311 return false; 312 } 313 return true; 314 }; 315 316 DfaEmitter Emitter; 317 std::deque<NfaStateTy> Worklist(1, 0); 318 std::set<NfaStateTy> SeenStates; 319 SeenStates.insert(Worklist.front()); 320 while (!Worklist.empty()) { 321 NfaStateTy State = Worklist.front(); 322 Worklist.pop_front(); 323 for (const ResourceVector &Resources : UniqueResources) { 324 if (!canApplyInsnClass(Resources, State)) 325 continue; 326 unsigned ResourcesID = UniqueResources.idFor(Resources); 327 for (uint64_t NewState : applyInsnClass(Resources, State)) { 328 if (SeenStates.emplace(NewState).second) 329 Worklist.emplace_back(NewState); 330 Emitter.addTransition(State, NewState, ResourcesID); 331 } 332 } 333 } 334 335 std::string TargetAndDFAName = TargetName + DFAName; 336 Emitter.emit(TargetAndDFAName, OS); 337 OS << "} // end anonymous namespace\n\n"; 338 339 std::string SubTargetClassName = TargetName + "GenSubtargetInfo"; 340 OS << "namespace llvm {\n"; 341 OS << "DFAPacketizer *" << SubTargetClassName << "::" 342 << "create" << DFAName 343 << "DFAPacketizer(const InstrItineraryData *IID) const {\n" 344 << " static Automaton<uint64_t> A(ArrayRef<" << TargetAndDFAName 345 << "Transition>(" << TargetAndDFAName << "Transitions), " 346 << TargetAndDFAName << "TransitionInfo);\n" 347 << " unsigned ProcResIdxStart = " << TargetAndDFAName 348 << "ProcResourceIndexStart[IID->SchedModel.ProcID];\n" 349 << " unsigned ProcResIdxNum = " << TargetAndDFAName 350 << "ProcResourceIndexStart[IID->SchedModel.ProcID + 1] - " 351 "ProcResIdxStart;\n" 352 << " return new DFAPacketizer(IID, A, {&" << TargetAndDFAName 353 << "ResourceIndices[ProcResIdxStart], ProcResIdxNum});\n" 354 << "\n}\n\n"; 355 } 356 357 namespace llvm { 358 359 void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) { 360 emitSourceFileHeader("Target DFA Packetizer Tables", OS); 361 DFAPacketizerEmitter(RK).run(OS); 362 } 363 364 } // end namespace llvm 365