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 <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 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(RecordKeeper &R); 73 74 // Construct a map of function unit names to bits. 75 int collectAllFuncUnits( 76 ArrayRef<const CodeGenProcModel *> ProcModels); 77 78 // Construct a map from a combo function unit bit to the bits of all included 79 // functional units. 80 int collectAllComboFuncs(ArrayRef<Record *> ComboFuncList); 81 82 ResourceVector getResourcesForItinerary(Record *Itinerary); 83 void createScheduleClasses(unsigned ItineraryIdx, const RecVec &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(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<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 (Record *Proc : ProcItinList) { 111 std::vector<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(ArrayRef<Record *> ComboFuncList) { 133 LLVM_DEBUG(dbgs() << "-------------------------------------------------------" 134 "----------------------\n"); 135 LLVM_DEBUG(dbgs() << "collectAllComboFuncs"); 136 LLVM_DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n"); 137 138 int numCombos = 0; 139 for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) { 140 Record *Func = ComboFuncList[i]; 141 std::vector<Record *> FUs = Func->getValueAsListOfDefs("CFD"); 142 143 LLVM_DEBUG(dbgs() << " CFD:" << i << " (" << FUs.size() << " combo FUs) " 144 << Func->getName() << "\n"); 145 146 // Convert macros to bits for each stage. 147 for (unsigned j = 0, N = FUs.size(); j < N; ++j) { 148 assert((j < DFA_MAX_RESOURCES) && 149 "Exceeded maximum number of DFA resources"); 150 Record *FuncData = FUs[j]; 151 Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc"); 152 const std::vector<Record *> &FuncList = 153 FuncData->getValueAsListOfDefs("FuncList"); 154 const std::string &ComboFuncName = std::string(ComboFunc->getName()); 155 uint64_t ComboBit = FUNameToBitsMap[ComboFuncName]; 156 uint64_t ComboResources = ComboBit; 157 LLVM_DEBUG(dbgs() << " combo: " << ComboFuncName << ":0x" 158 << Twine::utohexstr(ComboResources) << "\n"); 159 for (auto *K : FuncList) { 160 std::string FuncName = std::string(K->getName()); 161 uint64_t FuncResources = FUNameToBitsMap[FuncName]; 162 LLVM_DEBUG(dbgs() << " " << FuncName << ":0x" 163 << Twine::utohexstr(FuncResources) << "\n"); 164 ComboResources |= FuncResources; 165 } 166 ComboBitToBitsMap[ComboBit] = ComboResources; 167 numCombos++; 168 LLVM_DEBUG(dbgs() << " => combo bits: " << ComboFuncName << ":0x" 169 << Twine::utohexstr(ComboBit) << " = 0x" 170 << Twine::utohexstr(ComboResources) << "\n"); 171 } 172 } 173 return numCombos; 174 } 175 176 ResourceVector 177 DFAPacketizerEmitter::getResourcesForItinerary(Record *Itinerary) { 178 ResourceVector Resources; 179 assert(Itinerary); 180 for (Record *StageDef : Itinerary->getValueAsListOfDefs("Stages")) { 181 uint64_t StageResources = 0; 182 for (Record *Unit : StageDef->getValueAsListOfDefs("Units")) { 183 StageResources |= FUNameToBitsMap[std::string(Unit->getName())]; 184 } 185 if (StageResources != 0) 186 Resources.push_back(StageResources); 187 } 188 return Resources; 189 } 190 191 void DFAPacketizerEmitter::createScheduleClasses(unsigned ItineraryIdx, 192 const RecVec &Itineraries) { 193 unsigned Idx = 0; 194 for (Record *Itinerary : Itineraries) { 195 if (!Itinerary) { 196 ScheduleClasses.push_back({ItineraryIdx, Idx++, 0, ResourceVector{}}); 197 continue; 198 } 199 ResourceVector Resources = getResourcesForItinerary(Itinerary); 200 ScheduleClasses.push_back( 201 {ItineraryIdx, Idx++, UniqueResources.insert(Resources), Resources}); 202 } 203 } 204 205 // 206 // Run the worklist algorithm to generate the DFA. 207 // 208 void DFAPacketizerEmitter::run(raw_ostream &OS) { 209 emitSourceFileHeader("Target DFA Packetizer Tables", 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 static TableGen::Emitter::OptClass<DFAPacketizerEmitter> 358 X("gen-dfa-packetizer", "Generate DFA Packetizer for VLIW targets"); 359