//===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine ----===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This class parses the Schedule.td file and produces an API that can be used
// to reason about whether an instruction can be added to a packet on a VLIW
// architecture. The class internally generates a deterministic finite
// automaton (DFA) that models all possible mappings of machine instructions
// to functional units as instructions are added to a packet.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "dfa-emitter"

#include "CodeGenTarget.h"
#include "DFAEmitter.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/TableGen/Record.h"
#include "llvm/TableGen/TableGenBackend.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstdint>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

using namespace llvm;

// --------------------------------------------------------------------
// Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp

// DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
// This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
//
// e.g. terms x resource bit combinations that fit in uint32_t:
//      4 terms x 8  bits = 32 bits
//      3 terms x 10 bits = 30 bits
//      2 terms x 16 bits = 32 bits
//
// e.g. terms x resource bit combinations that fit in uint64_t:
//      8 terms x 8  bits = 64 bits
//      7 terms x 9  bits = 63 bits
//      6 terms x 10 bits = 60 bits
//      5 terms x 12 bits = 60 bits
//      4 terms x 16 bits = 64 bits <--- current
//      3 terms x 21 bits = 63 bits
//      2 terms x 32 bits = 64 bits
//
#define DFA_MAX_RESTERMS        4   // The max # of AND'ed resource terms.
#define DFA_MAX_RESOURCES       16  // The max # of resource bits in one term.

typedef uint64_t                DFAInput;
typedef int64_t                 DFAStateInput;
#define DFA_TBLTYPE             "int64_t" // For generating DFAStateInputTable.

namespace {

  DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) {
    return (Inp << DFA_MAX_RESOURCES) | FuncUnits;
  }

  /// Return the DFAInput for an instruction class input vector.
  /// This function is used in both DFAPacketizer.cpp and in
  /// DFAPacketizerEmitter.cpp.
  DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) {
    DFAInput InsnInput = 0;
    assert((InsnClass.size() <= DFA_MAX_RESTERMS) &&
           "Exceeded maximum number of DFA terms");
    for (auto U : InsnClass)
      InsnInput = addDFAFuncUnits(InsnInput, U);
    return InsnInput;
  }

} // end anonymous namespace

// --------------------------------------------------------------------

#ifndef NDEBUG
// To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
//
// dbgsInsnClass - When debugging, print instruction class stages.
//
void dbgsInsnClass(const std::vector<unsigned> &InsnClass);
//
// dbgsStateInfo - When debugging, print the set of state info.
//
void dbgsStateInfo(const std::set<unsigned> &stateInfo);
//
// dbgsIndent - When debugging, indent by the specified amount.
//
void dbgsIndent(unsigned indent);
#endif

//
// class DFAPacketizerEmitter: class that generates and prints out the DFA
// for resource tracking.
//
namespace {

class DFAPacketizerEmitter {
private:
  std::string TargetName;
  //
  // allInsnClasses is the set of all possible resources consumed by an
  // InstrStage.
  //
  std::vector<std::vector<unsigned>> allInsnClasses;
  RecordKeeper &Records;

public:
  DFAPacketizerEmitter(RecordKeeper &R);

  //
  // collectAllFuncUnits - Construct a map of function unit names to bits.
  //
  int collectAllFuncUnits(std::vector<Record*> &ProcItinList,
                           std::map<std::string, unsigned> &FUNameToBitsMap,
                           int &maxResources,
                           raw_ostream &OS);

  //
  // collectAllComboFuncs - Construct a map from a combo function unit bit to
  //                        the bits of all included functional units.
  //
  int collectAllComboFuncs(std::vector<Record*> &ComboFuncList,
                           std::map<std::string, unsigned> &FUNameToBitsMap,
                           std::map<unsigned, unsigned> &ComboBitToBitsMap,
                           raw_ostream &OS);

  //
  // collectOneInsnClass - Populate allInsnClasses with one instruction class.
  //
  int collectOneInsnClass(const std::string &ProcName,
                           std::vector<Record*> &ProcItinList,
                           std::map<std::string, unsigned> &FUNameToBitsMap,
                           Record *ItinData,
                           raw_ostream &OS);

  //
  // collectAllInsnClasses - Populate allInsnClasses which is a set of units
  // used in each stage.
  //
  int collectAllInsnClasses(const std::string &ProcName,
                           std::vector<Record*> &ProcItinList,
                           std::map<std::string, unsigned> &FUNameToBitsMap,
                           std::vector<Record*> &ItinDataList,
                           int &maxStages,
                           raw_ostream &OS);

  // Emit code for a subset of itineraries.
  void emitForItineraries(raw_ostream &OS,
                          std::vector<Record *> &ProcItinList,
                          std::string DFAName);

  void run(raw_ostream &OS);
};
} // end anonymous namespace

#ifndef NDEBUG
// To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
//
// dbgsInsnClass - When debugging, print instruction class stages.
//
void dbgsInsnClass(const std::vector<unsigned> &InsnClass) {
  LLVM_DEBUG(dbgs() << "InsnClass: ");
  for (unsigned i = 0; i < InsnClass.size(); ++i) {
    if (i > 0) {
      LLVM_DEBUG(dbgs() << ", ");
    }
    LLVM_DEBUG(dbgs() << "0x" << Twine::utohexstr(InsnClass[i]));
  }
  DFAInput InsnInput = getDFAInsnInput(InsnClass);
  LLVM_DEBUG(dbgs() << " (input: 0x" << Twine::utohexstr(InsnInput) << ")");
}

//
// dbgsIndent - When debugging, indent by the specified amount.
//
void dbgsIndent(unsigned indent) {
  for (unsigned i = 0; i < indent; ++i) {
    LLVM_DEBUG(dbgs() << " ");
  }
}
#endif // NDEBUG

DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R):
  TargetName(CodeGenTarget(R).getName()), Records(R) {}

//
// collectAllFuncUnits - Construct a map of function unit names to bits.
//
int DFAPacketizerEmitter::collectAllFuncUnits(
                            std::vector<Record*> &ProcItinList,
                            std::map<std::string, unsigned> &FUNameToBitsMap,
                            int &maxFUs,
                            raw_ostream &OS) {
  LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
                       "----------------------\n");
  LLVM_DEBUG(dbgs() << "collectAllFuncUnits");
  LLVM_DEBUG(dbgs() << " (" << ProcItinList.size() << " itineraries)\n");

  int totalFUs = 0;
  // Parse functional units for all the itineraries.
  for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) {
    Record *Proc = ProcItinList[i];
    std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU");

    LLVM_DEBUG(dbgs() << "    FU:" << i << " (" << FUs.size() << " FUs) "
                      << Proc->getName());

    // Convert macros to bits for each stage.
    unsigned numFUs = FUs.size();
    for (unsigned j = 0; j < numFUs; ++j) {
      assert ((j < DFA_MAX_RESOURCES) &&
                      "Exceeded maximum number of representable resources");
      unsigned FuncResources = (unsigned) (1U << j);
      FUNameToBitsMap[FUs[j]->getName()] = FuncResources;
      LLVM_DEBUG(dbgs() << " " << FUs[j]->getName() << ":0x"
                        << Twine::utohexstr(FuncResources));
    }
    if (((int) numFUs) > maxFUs) {
      maxFUs = numFUs;
    }
    totalFUs += numFUs;
    LLVM_DEBUG(dbgs() << "\n");
  }
  return totalFUs;
}

//
// collectAllComboFuncs - Construct a map from a combo function unit bit to
//                        the bits of all included functional units.
//
int DFAPacketizerEmitter::collectAllComboFuncs(
                            std::vector<Record*> &ComboFuncList,
                            std::map<std::string, unsigned> &FUNameToBitsMap,
                            std::map<unsigned, unsigned> &ComboBitToBitsMap,
                            raw_ostream &OS) {
  LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
                       "----------------------\n");
  LLVM_DEBUG(dbgs() << "collectAllComboFuncs");
  LLVM_DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n");

  int numCombos = 0;
  for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) {
    Record *Func = ComboFuncList[i];
    std::vector<Record*> FUs = Func->getValueAsListOfDefs("CFD");

    LLVM_DEBUG(dbgs() << "    CFD:" << i << " (" << FUs.size() << " combo FUs) "
                      << Func->getName() << "\n");

    // Convert macros to bits for each stage.
    for (unsigned j = 0, N = FUs.size(); j < N; ++j) {
      assert ((j < DFA_MAX_RESOURCES) &&
                      "Exceeded maximum number of DFA resources");
      Record *FuncData = FUs[j];
      Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc");
      const std::vector<Record*> &FuncList =
                                   FuncData->getValueAsListOfDefs("FuncList");
      const std::string &ComboFuncName = ComboFunc->getName();
      unsigned ComboBit = FUNameToBitsMap[ComboFuncName];
      unsigned ComboResources = ComboBit;
      LLVM_DEBUG(dbgs() << "      combo: " << ComboFuncName << ":0x"
                        << Twine::utohexstr(ComboResources) << "\n");
      for (unsigned k = 0, M = FuncList.size(); k < M; ++k) {
        std::string FuncName = FuncList[k]->getName();
        unsigned FuncResources = FUNameToBitsMap[FuncName];
        LLVM_DEBUG(dbgs() << "        " << FuncName << ":0x"
                          << Twine::utohexstr(FuncResources) << "\n");
        ComboResources |= FuncResources;
      }
      ComboBitToBitsMap[ComboBit] = ComboResources;
      numCombos++;
      LLVM_DEBUG(dbgs() << "          => combo bits: " << ComboFuncName << ":0x"
                        << Twine::utohexstr(ComboBit) << " = 0x"
                        << Twine::utohexstr(ComboResources) << "\n");
    }
  }
  return numCombos;
}

//
// collectOneInsnClass - Populate allInsnClasses with one instruction class
//
int DFAPacketizerEmitter::collectOneInsnClass(const std::string &ProcName,
                        std::vector<Record*> &ProcItinList,
                        std::map<std::string, unsigned> &FUNameToBitsMap,
                        Record *ItinData,
                        raw_ostream &OS) {
  const std::vector<Record*> &StageList =
    ItinData->getValueAsListOfDefs("Stages");

  // The number of stages.
  unsigned NStages = StageList.size();

  LLVM_DEBUG(dbgs() << "    " << ItinData->getValueAsDef("TheClass")->getName()
                    << "\n");

  std::vector<unsigned> UnitBits;

  // Compute the bitwise or of each unit used in this stage.
  for (unsigned i = 0; i < NStages; ++i) {
    const Record *Stage = StageList[i];

    // Get unit list.
    const std::vector<Record*> &UnitList =
      Stage->getValueAsListOfDefs("Units");

    LLVM_DEBUG(dbgs() << "        stage:" << i << " [" << UnitList.size()
                      << " units]:");
    unsigned dbglen = 26;  // cursor after stage dbgs

    // Compute the bitwise or of each unit used in this stage.
    unsigned UnitBitValue = 0;
    for (unsigned j = 0, M = UnitList.size(); j < M; ++j) {
      // Conduct bitwise or.
      std::string UnitName = UnitList[j]->getName();
      LLVM_DEBUG(dbgs() << " " << j << ":" << UnitName);
      dbglen += 3 + UnitName.length();
      assert(FUNameToBitsMap.count(UnitName));
      UnitBitValue |= FUNameToBitsMap[UnitName];
    }

    if (UnitBitValue != 0)
      UnitBits.push_back(UnitBitValue);

    while (dbglen <= 64) {   // line up bits dbgs
        dbglen += 8;
        LLVM_DEBUG(dbgs() << "\t");
    }
    LLVM_DEBUG(dbgs() << " (bits: 0x" << Twine::utohexstr(UnitBitValue)
                      << ")\n");
  }

  if (!UnitBits.empty())
    allInsnClasses.push_back(UnitBits);

  LLVM_DEBUG({
    dbgs() << "        ";
    dbgsInsnClass(UnitBits);
    dbgs() << "\n";
  });

  return NStages;
}

//
// collectAllInsnClasses - Populate allInsnClasses which is a set of units
// used in each stage.
//
int DFAPacketizerEmitter::collectAllInsnClasses(const std::string &ProcName,
                            std::vector<Record*> &ProcItinList,
                            std::map<std::string, unsigned> &FUNameToBitsMap,
                            std::vector<Record*> &ItinDataList,
                            int &maxStages,
                            raw_ostream &OS) {
  // Collect all instruction classes.
  unsigned M = ItinDataList.size();

  int numInsnClasses = 0;
  LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
                       "----------------------\n"
                    << "collectAllInsnClasses " << ProcName << " (" << M
                    << " classes)\n");

  // Collect stages for each instruction class for all itinerary data
  for (unsigned j = 0; j < M; j++) {
    Record *ItinData = ItinDataList[j];
    int NStages = collectOneInsnClass(ProcName, ProcItinList,
                                      FUNameToBitsMap, ItinData, OS);
    if (NStages > maxStages) {
      maxStages = NStages;
    }
    numInsnClasses++;
  }
  return numInsnClasses;
}

//
// Run the worklist algorithm to generate the DFA.
//
void DFAPacketizerEmitter::run(raw_ostream &OS) {
  OS << "\n"
     << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n";
  OS << "namespace llvm {\n";

  OS << "\n// Input format:\n";
  OS << "#define DFA_MAX_RESTERMS        " << DFA_MAX_RESTERMS
     << "\t// maximum AND'ed resource terms\n";
  OS << "#define DFA_MAX_RESOURCES       " << DFA_MAX_RESOURCES
     << "\t// maximum resource bits in one term\n";

  // Collect processor iteraries.
  std::vector<Record*> ProcItinList =
    Records.getAllDerivedDefinitions("ProcessorItineraries");

  std::unordered_map<std::string, std::vector<Record*>> ItinsByNamespace;
  for (Record *R : ProcItinList)
    ItinsByNamespace[R->getValueAsString("PacketizerNamespace")].push_back(R);

  for (auto &KV : ItinsByNamespace)
    emitForItineraries(OS, KV.second, KV.first);
  OS << "} // end namespace llvm\n";
}

void DFAPacketizerEmitter::emitForItineraries(
    raw_ostream &OS, std::vector<Record *> &ProcItinList,
    std::string DFAName) {
  //
  // Collect the Functional units.
  //
  std::map<std::string, unsigned> FUNameToBitsMap;
  int maxResources = 0;
  collectAllFuncUnits(ProcItinList,
                              FUNameToBitsMap, maxResources, OS);

  //
  // Collect the Combo Functional units.
  //
  std::map<unsigned, unsigned> ComboBitToBitsMap;
  std::vector<Record*> ComboFuncList =
    Records.getAllDerivedDefinitions("ComboFuncUnits");
  collectAllComboFuncs(ComboFuncList, FUNameToBitsMap, ComboBitToBitsMap, OS);

  //
  // Collect the itineraries.
  //
  int maxStages = 0;
  int numInsnClasses = 0;
  for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) {
    Record *Proc = ProcItinList[i];

    // Get processor itinerary name.
    const std::string &ProcName = Proc->getName();

    // Skip default.
    if (ProcName == "NoItineraries")
      continue;

    // Sanity check for at least one instruction itinerary class.
    unsigned NItinClasses =
      Records.getAllDerivedDefinitions("InstrItinClass").size();
    if (NItinClasses == 0)
      return;

    // Get itinerary data list.
    std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID");

    // Collect all instruction classes
    numInsnClasses += collectAllInsnClasses(ProcName, ProcItinList,
                          FUNameToBitsMap, ItinDataList, maxStages, OS);
  }

  // The type of a state in the nondeterministic automaton we're defining.
  using NfaStateTy = unsigned;

  // Given a resource state, return all resource states by applying
  // InsnClass.
  auto applyInsnClass = [&](ArrayRef<unsigned> InsnClass,
                            NfaStateTy State) -> std::deque<unsigned> {
    std::deque<unsigned> V(1, State);
    // Apply every stage in the class individually.
    for (unsigned Stage : InsnClass) {
      // Apply this stage to every existing member of V in turn.
      size_t Sz = V.size();
      for (unsigned I = 0; I < Sz; ++I) {
        unsigned S = V.front();
        V.pop_front();

        // For this stage, state combination, try all possible resources.
        for (unsigned J = 0; J < DFA_MAX_RESOURCES; ++J) {
          unsigned ResourceMask = 1U << J;
          if ((ResourceMask & Stage) == 0)
            // This resource isn't required by this stage.
            continue;
          unsigned Combo = ComboBitToBitsMap[ResourceMask];
          if (Combo && ((~S & Combo) != Combo))
            // This combo units bits are not available.
            continue;
          unsigned ResultingResourceState = S | ResourceMask | Combo;
          if (ResultingResourceState == S)
            continue;
          V.push_back(ResultingResourceState);
        }
      }
    }
    return V;
  };

  // Given a resource state, return a quick (conservative) guess as to whether
  // InsnClass can be applied. This is a filter for the more heavyweight
  // applyInsnClass.
  auto canApplyInsnClass = [](ArrayRef<unsigned> InsnClass,
                              NfaStateTy State) -> bool {
    for (unsigned Resources : InsnClass) {
      if ((State | Resources) == State)
        return false;
    }
    return true;
  };

  DfaEmitter Emitter;
  std::deque<NfaStateTy> Worklist(1, 0);
  std::set<NfaStateTy> SeenStates;
  SeenStates.insert(Worklist.front());
  while (!Worklist.empty()) {
    NfaStateTy State = Worklist.front();
    Worklist.pop_front();
    for (unsigned i = 0; i < allInsnClasses.size(); i++) {
      const std::vector<unsigned> &InsnClass = allInsnClasses[i];
      if (!canApplyInsnClass(InsnClass, State))
        continue;
      for (unsigned NewState : applyInsnClass(InsnClass, State)) {
        if (SeenStates.emplace(NewState).second)
          Worklist.emplace_back(NewState);
        Emitter.addTransition(State, NewState, getDFAInsnInput(InsnClass));
      }
    }
  }

  OS << "} // end namespace llvm\n\n";
  OS << "namespace {\n";
  std::string TargetAndDFAName = TargetName + DFAName;
  Emitter.emit(TargetAndDFAName, OS);
  OS << "} // end anonymous namespace\n\n";

  std::string SubTargetClassName = TargetName + "GenSubtargetInfo";
  OS << "namespace llvm {\n";
  OS << "DFAPacketizer *" << SubTargetClassName << "::"
     << "create" << DFAName
     << "DFAPacketizer(const InstrItineraryData *IID) const {\n"
     << "  static Automaton<uint64_t> A(ArrayRef<" << TargetAndDFAName
     << "Transition>(" << TargetAndDFAName << "Transitions), "
     << TargetAndDFAName << "TransitionInfo);\n"
     << "  return new DFAPacketizer(IID, A);\n"
     << "\n}\n\n";
}

namespace llvm {

void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) {
  emitSourceFileHeader("Target DFA Packetizer Tables", OS);
  DFAPacketizerEmitter(RK).run(OS);
}

} // end namespace llvm