From 8d4abb2446f80986ad5136bbec30c5da18cd6f4b Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Tue, 6 Nov 2012 07:10:38 +0000 Subject: [PATCH] misched: TargetSchedule interface for machine resources. Expose the processor resources defined by the machine model to the scheduler and other clients through the TargetSchedule interface. Normalize each resource count with respect to other kinds of resources. This allows scheduling heuristics to balance resources against other kinds of resources and latency. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167444 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/ScheduleDAG.h | 9 ++-- include/llvm/CodeGen/ScheduleDAGInstrs.h | 7 +++ include/llvm/CodeGen/TargetSchedule.h | 56 +++++++++++++++++++++--- include/llvm/MC/MCSchedule.h | 4 ++ lib/CodeGen/TargetSchedule.cpp | 39 +++++++++++++++-- 5 files changed, 103 insertions(+), 12 deletions(-) diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 658a35699e8..7e0ca1478e5 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -31,6 +31,7 @@ namespace llvm { class MachineFunction; class MachineRegisterInfo; class MachineInstr; + struct MCSchedClassDesc; class TargetRegisterInfo; class ScheduleDAG; class SDNode; @@ -249,6 +250,8 @@ namespace llvm { // this node was cloned. // (SD scheduling only) + const MCSchedClassDesc *SchedClass; // NULL or resolved SchedClass. + // Preds/Succs - The SUnits before/after us in the graph. SmallVector Preds; // All sunit predecessors. SmallVector Succs; // All sunit successors. @@ -296,7 +299,7 @@ namespace llvm { /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent /// an SDNode and any nodes flagged to it. SUnit(SDNode *node, unsigned nodenum) - : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), + : Node(node), Instr(0), OrigNode(0), SchedClass(0), NodeNum(nodenum), NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), @@ -310,7 +313,7 @@ namespace llvm { /// SUnit - Construct an SUnit for post-regalloc scheduling to represent /// a MachineInstr. SUnit(MachineInstr *instr, unsigned nodenum) - : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum), + : Node(0), Instr(instr), OrigNode(0), SchedClass(0), NodeNum(nodenum), NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), @@ -323,7 +326,7 @@ namespace llvm { /// SUnit - Construct a placeholder SUnit. SUnit() - : Node(0), Instr(0), OrigNode(0), NodeNum(~0u), + : Node(0), Instr(0), OrigNode(0), SchedClass(0), NodeNum(~0u), NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), diff --git a/include/llvm/CodeGen/ScheduleDAGInstrs.h b/include/llvm/CodeGen/ScheduleDAGInstrs.h index b4496a0515e..4bcd35a834c 100644 --- a/include/llvm/CodeGen/ScheduleDAGInstrs.h +++ b/include/llvm/CodeGen/ScheduleDAGInstrs.h @@ -189,6 +189,13 @@ namespace llvm { /// \brief Get the machine model for instruction scheduling. const TargetSchedModel *getSchedModel() const { return &SchedModel; } + /// \brief Resolve and cache a resolved scheduling class for an SUnit. + const MCSchedClassDesc *getSchedClass(SUnit *SU) const { + if (!SU->SchedClass) + SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr()); + return SU->SchedClass; + } + /// begin - Return an iterator to the top of the current scheduling region. MachineBasicBlock::iterator begin() const { return RegionBegin; } diff --git a/include/llvm/CodeGen/TargetSchedule.h b/include/llvm/CodeGen/TargetSchedule.h index 3c55f1cbc58..88e6105a7de 100644 --- a/include/llvm/CodeGen/TargetSchedule.h +++ b/include/llvm/CodeGen/TargetSchedule.h @@ -16,8 +16,10 @@ #ifndef LLVM_TARGET_TARGETSCHEDMODEL_H #define LLVM_TARGET_TARGETSCHEDMODEL_H +#include "llvm/Target/TargetSubtargetInfo.h" #include "llvm/MC/MCSchedule.h" #include "llvm/MC/MCInstrItineraries.h" +#include "llvm/ADT/SmallVector.h" namespace llvm { @@ -34,6 +36,10 @@ class TargetSchedModel { InstrItineraryData InstrItins; const TargetSubtargetInfo *STI; const TargetInstrInfo *TII; + + SmallVector ResourceFactors; + unsigned MicroOpFactor; // Multiply to normalize microops to resource units. + unsigned ResourceLCM; // Resource units per cycle. Latency normalization factor. public: TargetSchedModel(): STI(0), TII(0) {} @@ -45,6 +51,9 @@ public: void init(const MCSchedModel &sm, const TargetSubtargetInfo *sti, const TargetInstrInfo *tii); + /// Return the MCSchedClassDesc for this instruction. + const MCSchedClassDesc *resolveSchedClass(const MachineInstr *MI) const; + /// \brief TargetInstrInfo getter. const TargetInstrInfo *getInstrInfo() const { return TII; } @@ -76,7 +85,48 @@ public: unsigned getIssueWidth() const { return SchedModel.IssueWidth; } /// \brief Return the number of issue slots required for this MI. - unsigned getNumMicroOps(MachineInstr *MI) const; + unsigned getNumMicroOps(const MachineInstr *MI, + const MCSchedClassDesc *SC = 0) const; + + /// \brief Get the number of kinds of resources for this target. + unsigned getNumProcResourceKinds() const { + return SchedModel.getNumProcResourceKinds(); + } + + /// \brief Get a processor resource by ID for convenience. + const MCProcResourceDesc *getProcResource(unsigned PIdx) const { + return SchedModel.getProcResource(PIdx); + } + + typedef const MCWriteProcResEntry *ProcResIter; + + // \brief Get an iterator into the processor resources consumed by this + // scheduling class. + ProcResIter getWriteProcResBegin(const MCSchedClassDesc *SC) const { + // The subtarget holds a single resource table for all processors. + return STI->getWriteProcResBegin(SC); + } + ProcResIter getWriteProcResEnd(const MCSchedClassDesc *SC) const { + return STI->getWriteProcResEnd(SC); + } + + /// \brief Multiply the number of units consumed for a resource by this factor + /// to normalize it relative to other resources. + unsigned getResourceFactor(unsigned ResIdx) const { + return ResourceFactors[ResIdx]; + } + + /// \brief Multiply number of micro-ops by this factor to normalize it + /// relative to other resources. + unsigned getMicroOpFactor() const { + return MicroOpFactor; + } + + /// \brief Multiply cycle count by this factor to normalize it relative to + /// other resources. This is the number of resource units per cycle. + unsigned getLatencyFactor() const { + return ResourceLCM; + } /// \brief Compute operand latency based on the available machine model. /// @@ -105,15 +155,11 @@ public: unsigned computeOutputLatency(const MachineInstr *DefMI, unsigned DefIdx, const MachineInstr *DepMI) const; - private: /// getDefLatency is a helper for computeOperandLatency. Return the /// instruction's latency if operand lookup is not required. /// Otherwise return -1. int getDefLatency(const MachineInstr *DefMI, bool FindMin) const; - - /// Return the MCSchedClassDesc for this instruction. - const MCSchedClassDesc *resolveSchedClass(const MachineInstr *MI) const; }; } // namespace llvm diff --git a/include/llvm/MC/MCSchedule.h b/include/llvm/MC/MCSchedule.h index c9a060c79b1..0c71ee51350 100644 --- a/include/llvm/MC/MCSchedule.h +++ b/include/llvm/MC/MCSchedule.h @@ -219,6 +219,10 @@ public: /// Does this machine model include instruction-level scheduling. bool hasInstrSchedModel() const { return SchedClassTable; } + unsigned getNumProcResourceKinds() const { + return NumProcResourceKinds; + } + const MCProcResourceDesc *getProcResource(unsigned ProcResourceIdx) const { assert(hasInstrSchedModel() && "No scheduling machine model"); diff --git a/lib/CodeGen/TargetSchedule.cpp b/lib/CodeGen/TargetSchedule.cpp index 6a096a16c4e..ca3b0e0b117 100644 --- a/lib/CodeGen/TargetSchedule.cpp +++ b/lib/CodeGen/TargetSchedule.cpp @@ -36,6 +36,21 @@ bool TargetSchedModel::hasInstrItineraries() const { return EnableSchedItins && !InstrItins.isEmpty(); } +static unsigned gcd(unsigned Dividend, unsigned Divisor) { + // Dividend and Divisor will be naturally swapped as needed. + while(Divisor) { + unsigned Rem = Dividend % Divisor; + Dividend = Divisor; + Divisor = Rem; + }; + return Dividend; +} +static unsigned lcm(unsigned A, unsigned B) { + unsigned LCM = (uint64_t(A) * B) / gcd(A, B); + assert((LCM >= A && LCM >= B) && "LCM overflow"); + return LCM; +} + void TargetSchedModel::init(const MCSchedModel &sm, const TargetSubtargetInfo *sti, const TargetInstrInfo *tii) { @@ -43,17 +58,33 @@ void TargetSchedModel::init(const MCSchedModel &sm, STI = sti; TII = tii; STI->initInstrItins(InstrItins); + + unsigned NumRes = SchedModel.getNumProcResourceKinds(); + ResourceFactors.resize(NumRes); + ResourceLCM = SchedModel.IssueWidth; + for (unsigned Idx = 0; Idx < NumRes; ++Idx) { + unsigned NumUnits = SchedModel.getProcResource(Idx)->NumUnits; + if (NumUnits > 0) + ResourceLCM = lcm(ResourceLCM, NumUnits); + } + MicroOpFactor = ResourceLCM / SchedModel.IssueWidth; + for (unsigned Idx = 0; Idx < NumRes; ++Idx) { + unsigned NumUnits = SchedModel.getProcResource(Idx)->NumUnits; + ResourceFactors[Idx] = NumUnits ? (ResourceLCM / NumUnits) : 0; + } } -unsigned TargetSchedModel::getNumMicroOps(MachineInstr *MI) const { +unsigned TargetSchedModel::getNumMicroOps(const MachineInstr *MI, + const MCSchedClassDesc *SC) const { if (hasInstrItineraries()) { int UOps = InstrItins.getNumMicroOps(MI->getDesc().getSchedClass()); return (UOps >= 0) ? UOps : TII->getNumMicroOps(&InstrItins, MI); } if (hasInstrSchedModel()) { - const MCSchedClassDesc *SCDesc = resolveSchedClass(MI); - if (SCDesc->isValid()) - return SCDesc->NumMicroOps; + if (!SC) + SC = resolveSchedClass(MI); + if (SC->isValid()) + return SC->NumMicroOps; } return MI->isTransient() ? 0 : 1; } -- 2.40.0