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