| //=- llvm/CodeGen/DFAPacketizer.cpp - DFA Packetizer for VLIW -*- C++ -*-=====// |
| // |
| // 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 implements a deterministic finite automaton (DFA) based |
| // packetizing mechanism for VLIW architectures. It provides APIs to |
| // determine whether there exists a legal mapping of instructions to |
| // functional unit assignments in a packet. The DFA is auto-generated from |
| // the target's Schedule.td file. |
| // |
| // A DFA consists of 3 major elements: states, inputs, and transitions. For |
| // the packetizing mechanism, the input is the set of instruction classes for |
| // a target. The state models all possible combinations of functional unit |
| // consumption for a given set of instructions in a packet. A transition |
| // models the addition of an instruction to a packet. In the DFA constructed |
| // by this class, if an instruction can be added to a packet, then a valid |
| // transition exists from the corresponding state. Invalid transitions |
| // indicate that the instruction cannot be added to the current packet. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/CodeGen/DFAPacketizer.h" |
| #include "llvm/CodeGen/MachineFunction.h" |
| #include "llvm/CodeGen/MachineInstr.h" |
| #include "llvm/CodeGen/MachineInstrBundle.h" |
| #include "llvm/CodeGen/ScheduleDAG.h" |
| #include "llvm/CodeGen/ScheduleDAGInstrs.h" |
| #include "llvm/CodeGen/TargetInstrInfo.h" |
| #include "llvm/CodeGen/TargetSubtargetInfo.h" |
| #include "llvm/MC/MCInstrDesc.h" |
| #include "llvm/MC/MCInstrItineraries.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include <algorithm> |
| #include <cassert> |
| #include <iterator> |
| #include <memory> |
| #include <vector> |
| |
| using namespace llvm; |
| |
| #define DEBUG_TYPE "packets" |
| |
| static cl::opt<unsigned> InstrLimit("dfa-instr-limit", cl::Hidden, |
| cl::init(0), cl::desc("If present, stops packetizing after N instructions")); |
| |
| static unsigned InstrCount = 0; |
| |
| // -------------------------------------------------------------------- |
| // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp |
| |
| static 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. |
| static 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; |
| } |
| |
| // -------------------------------------------------------------------- |
| |
| DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, |
| const DFAStateInput (*SIT)[2], |
| const unsigned *SET): |
| InstrItins(I), DFAStateInputTable(SIT), DFAStateEntryTable(SET) { |
| // Make sure DFA types are large enough for the number of terms & resources. |
| static_assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= |
| (8 * sizeof(DFAInput)), |
| "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAInput"); |
| static_assert( |
| (DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAStateInput)), |
| "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAStateInput"); |
| } |
| |
| // Read the DFA transition table and update CachedTable. |
| // |
| // Format of the transition tables: |
| // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid |
| // transitions |
| // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable |
| // for the ith state |
| // |
| void DFAPacketizer::ReadTable(unsigned int state) { |
| unsigned ThisState = DFAStateEntryTable[state]; |
| unsigned NextStateInTable = DFAStateEntryTable[state+1]; |
| // Early exit in case CachedTable has already contains this |
| // state's transitions. |
| if (CachedTable.count(UnsignPair(state, DFAStateInputTable[ThisState][0]))) |
| return; |
| |
| for (unsigned i = ThisState; i < NextStateInTable; i++) |
| CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] = |
| DFAStateInputTable[i][1]; |
| } |
| |
| // Return the DFAInput for an instruction class. |
| DFAInput DFAPacketizer::getInsnInput(unsigned InsnClass) { |
| // Note: this logic must match that in DFAPacketizerDefs.h for input vectors. |
| DFAInput InsnInput = 0; |
| unsigned i = 0; |
| (void)i; |
| for (const InstrStage *IS = InstrItins->beginStage(InsnClass), |
| *IE = InstrItins->endStage(InsnClass); IS != IE; ++IS) { |
| InsnInput = addDFAFuncUnits(InsnInput, IS->getUnits()); |
| assert((i++ < DFA_MAX_RESTERMS) && "Exceeded maximum number of DFA inputs"); |
| } |
| return InsnInput; |
| } |
| |
| // Return the DFAInput for an instruction class input vector. |
| DFAInput DFAPacketizer::getInsnInput(const std::vector<unsigned> &InsnClass) { |
| return getDFAInsnInput(InsnClass); |
| } |
| |
| // Check if the resources occupied by a MCInstrDesc are available in the |
| // current state. |
| bool DFAPacketizer::canReserveResources(const MCInstrDesc *MID) { |
| unsigned InsnClass = MID->getSchedClass(); |
| DFAInput InsnInput = getInsnInput(InsnClass); |
| UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput); |
| ReadTable(CurrentState); |
| return CachedTable.count(StateTrans) != 0; |
| } |
| |
| // Reserve the resources occupied by a MCInstrDesc and change the current |
| // state to reflect that change. |
| void DFAPacketizer::reserveResources(const MCInstrDesc *MID) { |
| unsigned InsnClass = MID->getSchedClass(); |
| DFAInput InsnInput = getInsnInput(InsnClass); |
| UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput); |
| ReadTable(CurrentState); |
| assert(CachedTable.count(StateTrans) != 0); |
| CurrentState = CachedTable[StateTrans]; |
| } |
| |
| // Check if the resources occupied by a machine instruction are available |
| // in the current state. |
| bool DFAPacketizer::canReserveResources(MachineInstr &MI) { |
| const MCInstrDesc &MID = MI.getDesc(); |
| return canReserveResources(&MID); |
| } |
| |
| // Reserve the resources occupied by a machine instruction and change the |
| // current state to reflect that change. |
| void DFAPacketizer::reserveResources(MachineInstr &MI) { |
| const MCInstrDesc &MID = MI.getDesc(); |
| reserveResources(&MID); |
| } |
| |
| namespace llvm { |
| |
| // This class extends ScheduleDAGInstrs and overrides the schedule method |
| // to build the dependence graph. |
| class DefaultVLIWScheduler : public ScheduleDAGInstrs { |
| private: |
| AliasAnalysis *AA; |
| /// Ordered list of DAG postprocessing steps. |
| std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations; |
| |
| public: |
| DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI, |
| AliasAnalysis *AA); |
| |
| // Actual scheduling work. |
| void schedule() override; |
| |
| /// DefaultVLIWScheduler takes ownership of the Mutation object. |
| void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) { |
| Mutations.push_back(std::move(Mutation)); |
| } |
| |
| protected: |
| void postprocessDAG(); |
| }; |
| |
| } // end namespace llvm |
| |
| DefaultVLIWScheduler::DefaultVLIWScheduler(MachineFunction &MF, |
| MachineLoopInfo &MLI, |
| AliasAnalysis *AA) |
| : ScheduleDAGInstrs(MF, &MLI), AA(AA) { |
| CanHandleTerminators = true; |
| } |
| |
| /// Apply each ScheduleDAGMutation step in order. |
| void DefaultVLIWScheduler::postprocessDAG() { |
| for (auto &M : Mutations) |
| M->apply(this); |
| } |
| |
| void DefaultVLIWScheduler::schedule() { |
| // Build the scheduling graph. |
| buildSchedGraph(AA); |
| postprocessDAG(); |
| } |
| |
| VLIWPacketizerList::VLIWPacketizerList(MachineFunction &mf, |
| MachineLoopInfo &mli, AliasAnalysis *aa) |
| : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) { |
| ResourceTracker = TII->CreateTargetScheduleState(MF.getSubtarget()); |
| VLIWScheduler = new DefaultVLIWScheduler(MF, mli, AA); |
| } |
| |
| VLIWPacketizerList::~VLIWPacketizerList() { |
| delete VLIWScheduler; |
| delete ResourceTracker; |
| } |
| |
| // End the current packet, bundle packet instructions and reset DFA state. |
| void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB, |
| MachineBasicBlock::iterator MI) { |
| LLVM_DEBUG({ |
| if (!CurrentPacketMIs.empty()) { |
| dbgs() << "Finalizing packet:\n"; |
| for (MachineInstr *MI : CurrentPacketMIs) |
| dbgs() << " * " << *MI; |
| } |
| }); |
| if (CurrentPacketMIs.size() > 1) { |
| MachineInstr &MIFirst = *CurrentPacketMIs.front(); |
| finalizeBundle(*MBB, MIFirst.getIterator(), MI.getInstrIterator()); |
| } |
| CurrentPacketMIs.clear(); |
| ResourceTracker->clearResources(); |
| LLVM_DEBUG(dbgs() << "End packet\n"); |
| } |
| |
| // Bundle machine instructions into packets. |
| void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB, |
| MachineBasicBlock::iterator BeginItr, |
| MachineBasicBlock::iterator EndItr) { |
| assert(VLIWScheduler && "VLIW Scheduler is not initialized!"); |
| VLIWScheduler->startBlock(MBB); |
| VLIWScheduler->enterRegion(MBB, BeginItr, EndItr, |
| std::distance(BeginItr, EndItr)); |
| VLIWScheduler->schedule(); |
| |
| LLVM_DEBUG({ |
| dbgs() << "Scheduling DAG of the packetize region\n"; |
| VLIWScheduler->dump(); |
| }); |
| |
| // Generate MI -> SU map. |
| MIToSUnit.clear(); |
| for (SUnit &SU : VLIWScheduler->SUnits) |
| MIToSUnit[SU.getInstr()] = &SU; |
| |
| bool LimitPresent = InstrLimit.getPosition(); |
| |
| // The main packetizer loop. |
| for (; BeginItr != EndItr; ++BeginItr) { |
| if (LimitPresent) { |
| if (InstrCount >= InstrLimit) { |
| EndItr = BeginItr; |
| break; |
| } |
| InstrCount++; |
| } |
| MachineInstr &MI = *BeginItr; |
| initPacketizerState(); |
| |
| // End the current packet if needed. |
| if (isSoloInstruction(MI)) { |
| endPacket(MBB, MI); |
| continue; |
| } |
| |
| // Ignore pseudo instructions. |
| if (ignorePseudoInstruction(MI, MBB)) |
| continue; |
| |
| SUnit *SUI = MIToSUnit[&MI]; |
| assert(SUI && "Missing SUnit Info!"); |
| |
| // Ask DFA if machine resource is available for MI. |
| LLVM_DEBUG(dbgs() << "Checking resources for adding MI to packet " << MI); |
| |
| bool ResourceAvail = ResourceTracker->canReserveResources(MI); |
| LLVM_DEBUG({ |
| if (ResourceAvail) |
| dbgs() << " Resources are available for adding MI to packet\n"; |
| else |
| dbgs() << " Resources NOT available\n"; |
| }); |
| if (ResourceAvail && shouldAddToPacket(MI)) { |
| // Dependency check for MI with instructions in CurrentPacketMIs. |
| for (auto MJ : CurrentPacketMIs) { |
| SUnit *SUJ = MIToSUnit[MJ]; |
| assert(SUJ && "Missing SUnit Info!"); |
| |
| LLVM_DEBUG(dbgs() << " Checking against MJ " << *MJ); |
| // Is it legal to packetize SUI and SUJ together. |
| if (!isLegalToPacketizeTogether(SUI, SUJ)) { |
| LLVM_DEBUG(dbgs() << " Not legal to add MI, try to prune\n"); |
| // Allow packetization if dependency can be pruned. |
| if (!isLegalToPruneDependencies(SUI, SUJ)) { |
| // End the packet if dependency cannot be pruned. |
| LLVM_DEBUG(dbgs() |
| << " Could not prune dependencies for adding MI\n"); |
| endPacket(MBB, MI); |
| break; |
| } |
| LLVM_DEBUG(dbgs() << " Pruned dependence for adding MI\n"); |
| } |
| } |
| } else { |
| LLVM_DEBUG(if (ResourceAvail) dbgs() |
| << "Resources are available, but instruction should not be " |
| "added to packet\n " |
| << MI); |
| // End the packet if resource is not available, or if the instruction |
| // shoud not be added to the current packet. |
| endPacket(MBB, MI); |
| } |
| |
| // Add MI to the current packet. |
| LLVM_DEBUG(dbgs() << "* Adding MI to packet " << MI << '\n'); |
| BeginItr = addToPacket(MI); |
| } // For all instructions in the packetization range. |
| |
| // End any packet left behind. |
| endPacket(MBB, EndItr); |
| VLIWScheduler->exitRegion(); |
| VLIWScheduler->finishBlock(); |
| } |
| |
| bool VLIWPacketizerList::alias(const MachineMemOperand &Op1, |
| const MachineMemOperand &Op2, |
| bool UseTBAA) const { |
| if (!Op1.getValue() || !Op2.getValue()) |
| return true; |
| |
| int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset()); |
| int64_t Overlapa = Op1.getSize() + Op1.getOffset() - MinOffset; |
| int64_t Overlapb = Op2.getSize() + Op2.getOffset() - MinOffset; |
| |
| AliasResult AAResult = |
| AA->alias(MemoryLocation(Op1.getValue(), Overlapa, |
| UseTBAA ? Op1.getAAInfo() : AAMDNodes()), |
| MemoryLocation(Op2.getValue(), Overlapb, |
| UseTBAA ? Op2.getAAInfo() : AAMDNodes())); |
| |
| return AAResult != NoAlias; |
| } |
| |
| bool VLIWPacketizerList::alias(const MachineInstr &MI1, |
| const MachineInstr &MI2, |
| bool UseTBAA) const { |
| if (MI1.memoperands_empty() || MI2.memoperands_empty()) |
| return true; |
| |
| for (const MachineMemOperand *Op1 : MI1.memoperands()) |
| for (const MachineMemOperand *Op2 : MI2.memoperands()) |
| if (alias(*Op1, *Op2, UseTBAA)) |
| return true; |
| return false; |
| } |
| |
| // Add a DAG mutation object to the ordered list. |
| void VLIWPacketizerList::addMutation( |
| std::unique_ptr<ScheduleDAGMutation> Mutation) { |
| VLIWScheduler->addMutation(std::move(Mutation)); |
| } |