1235368Sgnn//===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine ----===//
2235368Sgnn//
3235368Sgnn// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4235368Sgnn// See https://llvm.org/LICENSE.txt for license information.
5235368Sgnn// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6235368Sgnn//
7235368Sgnn//===----------------------------------------------------------------------===//
8235368Sgnn//
9235368Sgnn// This class parses the Schedule.td file and produces an API that can be used
10235368Sgnn// to reason about whether an instruction can be added to a packet on a VLIW
11235368Sgnn// architecture. The class internally generates a deterministic finite
12235368Sgnn// automaton (DFA) that models all possible mappings of machine instructions
13235368Sgnn// to functional units as instructions are added to a packet.
14235368Sgnn//
15235368Sgnn//===----------------------------------------------------------------------===//
16235368Sgnn
17235368Sgnn#define DEBUG_TYPE "dfa-emitter"
18235368Sgnn
19235368Sgnn#include "CodeGenSchedule.h"
20235368Sgnn#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
37using namespace llvm;
38
39// We use a uint64_t to represent a resource bitmask.
40#define DFA_MAX_RESOURCES 64
41
42namespace {
43using ResourceVector = SmallVector<uint64_t, 4>;
44
45struct 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.
62class DFAPacketizerEmitter {
63private:
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
72public:
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
95DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R)
96    : TargetName(CodeGenTarget(R).getName()), Records(R) {}
97
98int 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[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
133int 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 = 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 = 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
177ResourceVector
178DFAPacketizerEmitter::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[Unit->getName()];
185    }
186    if (StageResources != 0)
187      Resources.push_back(StageResources);
188  }
189  return Resources;
190}
191
192void 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//
209void 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[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
231void 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 << "unsigned " << TargetName << DFAName << "ResourceIndices[] = {";
250  for (const ScheduleClass &SC : ScheduleClasses) {
251    if (Idx++ % 32 == 0)
252      OS << "\n  ";
253    OS << SC.ResourcesIdx << ", ";
254  }
255  OS << "\n};\n\n";
256
257  // And the mapping from Itinerary index into the previous table.
258  OS << "unsigned " << TargetName << DFAName
259     << "ProcResourceIndexStart[] = {\n";
260  OS << "  0, // NoSchedModel\n";
261  for (const CodeGenProcModel *Model : ProcModels) {
262    OS << "  " << ProcModelStartIdx[Model] << ", // " << Model->ModelName
263       << "\n";
264  }
265  OS << ScheduleClasses.size() << "\n};\n\n";
266
267  // The type of a state in the nondeterministic automaton we're defining.
268  using NfaStateTy = uint64_t;
269
270  // Given a resource state, return all resource states by applying
271  // InsnClass.
272  auto applyInsnClass = [&](const ResourceVector &InsnClass,
273                            NfaStateTy State) -> std::deque<NfaStateTy> {
274    std::deque<NfaStateTy> V(1, State);
275    // Apply every stage in the class individually.
276    for (NfaStateTy Stage : InsnClass) {
277      // Apply this stage to every existing member of V in turn.
278      size_t Sz = V.size();
279      for (unsigned I = 0; I < Sz; ++I) {
280        NfaStateTy S = V.front();
281        V.pop_front();
282
283        // For this stage, state combination, try all possible resources.
284        for (unsigned J = 0; J < DFA_MAX_RESOURCES; ++J) {
285          NfaStateTy ResourceMask = 1ULL << J;
286          if ((ResourceMask & Stage) == 0)
287            // This resource isn't required by this stage.
288            continue;
289          NfaStateTy Combo = ComboBitToBitsMap[ResourceMask];
290          if (Combo && ((~S & Combo) != Combo))
291            // This combo units bits are not available.
292            continue;
293          NfaStateTy ResultingResourceState = S | ResourceMask | Combo;
294          if (ResultingResourceState == S)
295            continue;
296          V.push_back(ResultingResourceState);
297        }
298      }
299    }
300    return V;
301  };
302
303  // Given a resource state, return a quick (conservative) guess as to whether
304  // InsnClass can be applied. This is a filter for the more heavyweight
305  // applyInsnClass.
306  auto canApplyInsnClass = [](const ResourceVector &InsnClass,
307                              NfaStateTy State) -> bool {
308    for (NfaStateTy Resources : InsnClass) {
309      if ((State | Resources) == State)
310        return false;
311    }
312    return true;
313  };
314
315  DfaEmitter Emitter;
316  std::deque<NfaStateTy> Worklist(1, 0);
317  std::set<NfaStateTy> SeenStates;
318  SeenStates.insert(Worklist.front());
319  while (!Worklist.empty()) {
320    NfaStateTy State = Worklist.front();
321    Worklist.pop_front();
322    for (const ResourceVector &Resources : UniqueResources) {
323      if (!canApplyInsnClass(Resources, State))
324        continue;
325      unsigned ResourcesID = UniqueResources.idFor(Resources);
326      for (uint64_t NewState : applyInsnClass(Resources, State)) {
327        if (SeenStates.emplace(NewState).second)
328          Worklist.emplace_back(NewState);
329        Emitter.addTransition(State, NewState, ResourcesID);
330      }
331    }
332  }
333
334  std::string TargetAndDFAName = TargetName + DFAName;
335  Emitter.emit(TargetAndDFAName, OS);
336  OS << "} // end anonymous namespace\n\n";
337
338  std::string SubTargetClassName = TargetName + "GenSubtargetInfo";
339  OS << "namespace llvm {\n";
340  OS << "DFAPacketizer *" << SubTargetClassName << "::"
341     << "create" << DFAName
342     << "DFAPacketizer(const InstrItineraryData *IID) const {\n"
343     << "  static Automaton<uint64_t> A(ArrayRef<" << TargetAndDFAName
344     << "Transition>(" << TargetAndDFAName << "Transitions), "
345     << TargetAndDFAName << "TransitionInfo);\n"
346     << "  unsigned ProcResIdxStart = " << TargetAndDFAName
347     << "ProcResourceIndexStart[IID->SchedModel.ProcID];\n"
348     << "  unsigned ProcResIdxNum = " << TargetAndDFAName
349     << "ProcResourceIndexStart[IID->SchedModel.ProcID + 1] - "
350        "ProcResIdxStart;\n"
351     << "  return new DFAPacketizer(IID, A, {&" << TargetAndDFAName
352     << "ResourceIndices[ProcResIdxStart], ProcResIdxNum});\n"
353     << "\n}\n\n";
354}
355
356namespace llvm {
357
358void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) {
359  emitSourceFileHeader("Target DFA Packetizer Tables", OS);
360  DFAPacketizerEmitter(RK).run(OS);
361}
362
363} // end namespace llvm
364