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 "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 36 using namespace llvm; 37 38 // We use a uint64_t to represent a resource bitmask. 39 #define DFA_MAX_RESOURCES 64 40 41 namespace { 42 using ResourceVector = SmallVector<uint64_t, 4>; 43 44 struct 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. 61 class DFAPacketizerEmitter { 62 private: 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 71 public: 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 included 78 // 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 namespace 93 94 DFAPacketizerEmitter::DFAPacketizerEmitter(const RecordKeeper &R) 95 : TargetName(std::string(CodeGenTarget(R).getName())), Records(R) {} 96 97 int 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[std::string(FUs[j]->getName())] = 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 132 int 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 = 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 (const Record *K : FuncList) { 161 std::string FuncName = std::string(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(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[std::string(Unit->getName())]; 185 } 186 if (StageResources != 0) 187 Resources.push_back(StageResources); 188 } 189 return Resources; 190 } 191 192 void 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 // 209 void 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[std::string(NS)].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 232 void 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 << DFAName 251 << "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 << DFAName 261 << "ProcResourceIndexStart[] = {\n"; 262 OS << " 0, // NoSchedModel\n"; 263 for (const CodeGenProcModel *Model : ProcModels) { 264 OS << " " << ProcModelStartIdx[Model] << ", // " << Model->ModelName 265 << "\n"; 266 } 267 OS << " " << ScheduleClasses.size() << "\n};\n\n"; 268 269 // The type of a state in the nondeterministic automaton we're defining. 270 using NfaStateTy = uint64_t; 271 272 // Given a resource state, return all resource states by applying 273 // InsnClass. 274 auto ApplyInsnClass = [&](const ResourceVector &InsnClass, 275 NfaStateTy State) -> std::deque<NfaStateTy> { 276 std::deque<NfaStateTy> V(1, State); 277 // Apply every stage in the class individually. 278 for (NfaStateTy Stage : InsnClass) { 279 // Apply this stage to every existing member of V in turn. 280 size_t Sz = V.size(); 281 for (unsigned I = 0; I < Sz; ++I) { 282 NfaStateTy S = V.front(); 283 V.pop_front(); 284 285 // For this stage, state combination, try all possible resources. 286 for (unsigned J = 0; J < DFA_MAX_RESOURCES; ++J) { 287 NfaStateTy ResourceMask = 1ULL << J; 288 if ((ResourceMask & Stage) == 0) 289 // This resource isn't required by this stage. 290 continue; 291 NfaStateTy Combo = ComboBitToBitsMap[ResourceMask]; 292 if (Combo && ((~S & Combo) != Combo)) 293 // This combo units bits are not available. 294 continue; 295 NfaStateTy ResultingResourceState = S | ResourceMask | Combo; 296 if (ResultingResourceState == S) 297 continue; 298 V.push_back(ResultingResourceState); 299 } 300 } 301 } 302 return V; 303 }; 304 305 // Given a resource state, return a quick (conservative) guess as to whether 306 // InsnClass can be applied. This is a filter for the more heavyweight 307 // ApplyInsnClass. 308 auto canApplyInsnClass = [](const ResourceVector &InsnClass, 309 NfaStateTy State) -> bool { 310 for (NfaStateTy Resources : InsnClass) { 311 if ((State | Resources) == State) 312 return false; 313 } 314 return true; 315 }; 316 317 DfaEmitter Emitter; 318 std::deque<NfaStateTy> Worklist(1, 0); 319 std::set<NfaStateTy> SeenStates; 320 SeenStates.insert(Worklist.front()); 321 while (!Worklist.empty()) { 322 NfaStateTy State = Worklist.front(); 323 Worklist.pop_front(); 324 for (const ResourceVector &Resources : UniqueResources) { 325 if (!canApplyInsnClass(Resources, State)) 326 continue; 327 unsigned ResourcesID = UniqueResources.idFor(Resources); 328 for (uint64_t NewState : ApplyInsnClass(Resources, State)) { 329 if (SeenStates.emplace(NewState).second) 330 Worklist.emplace_back(NewState); 331 Emitter.addTransition(State, NewState, ResourcesID); 332 } 333 } 334 } 335 336 std::string TargetAndDFAName = TargetName + DFAName; 337 Emitter.emit(TargetAndDFAName, OS); 338 OS << "} // end anonymous namespace\n\n"; 339 340 std::string SubTargetClassName = TargetName + "GenSubtargetInfo"; 341 OS << "namespace llvm {\n"; 342 OS << "DFAPacketizer *" << SubTargetClassName << "::" 343 << "create" << DFAName 344 << "DFAPacketizer(const InstrItineraryData *IID) const {\n" 345 << " static Automaton<uint64_t> A(ArrayRef<" << TargetAndDFAName 346 << "Transition>(" << TargetAndDFAName << "Transitions), " 347 << TargetAndDFAName << "TransitionInfo);\n" 348 << " unsigned ProcResIdxStart = " << TargetAndDFAName 349 << "ProcResourceIndexStart[IID->SchedModel.ProcID];\n" 350 << " unsigned ProcResIdxNum = " << TargetAndDFAName 351 << "ProcResourceIndexStart[IID->SchedModel.ProcID + 1] - " 352 "ProcResIdxStart;\n" 353 << " return new DFAPacketizer(IID, A, {&" << TargetAndDFAName 354 << "ResourceIndices[ProcResIdxStart], ProcResIdxNum});\n" 355 << "\n}\n\n"; 356 } 357 358 static TableGen::Emitter::OptClass<DFAPacketizerEmitter> 359 X("gen-dfa-packetizer", "Generate DFA Packetizer for VLIW targets"); 360