diff options
Diffstat (limited to 'contrib/llvm-project/llvm/lib/CodeGen/DFAPacketizer.cpp')
| -rw-r--r-- | contrib/llvm-project/llvm/lib/CodeGen/DFAPacketizer.cpp | 375 |
1 files changed, 375 insertions, 0 deletions
diff --git a/contrib/llvm-project/llvm/lib/CodeGen/DFAPacketizer.cpp b/contrib/llvm-project/llvm/lib/CodeGen/DFAPacketizer.cpp new file mode 100644 index 000000000000..b99be5d7a87c --- /dev/null +++ b/contrib/llvm-project/llvm/lib/CodeGen/DFAPacketizer.cpp @@ -0,0 +1,375 @@ +//=- 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)); +} |