#define DEBUG_TYPE "misched"
-#include "RegisterClassInfo.h"
-#include "RegisterPressure.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineScheduler.h"
#include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/RegisterClassInfo.h"
+#include "llvm/CodeGen/RegisterPressure.h"
#include "llvm/CodeGen/ScheduleDAGInstrs.h"
#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
-#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/MC/MCInstrItineraries.h"
+#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
Scheduler->startBlock(MBB);
// Break the block into scheduling regions [I, RegionEnd), and schedule each
- // region as soon as it is discovered. RegionEnd points the the scheduling
+ // region as soon as it is discovered. RegionEnd points the scheduling
// boundary at the bottom of the region. The DAG does not include RegionEnd,
// but the region does (i.e. the next RegionEnd is above the previous
// RegionBegin). If the current block has no terminator then RegionEnd ==
IntervalPressure BotPressure;
RegPressureTracker BotRPTracker;
+#ifndef NDEBUG
/// The number of instructions scheduled so far. Used to cut off the
/// scheduler at the point determined by misched-cutoff.
unsigned NumInstrsScheduled;
+#endif
public:
ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S):
ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS),
AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S),
RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure),
- CurrentBottom(), BotRPTracker(BotPressure), NumInstrsScheduled(0) {}
+ CurrentBottom(), BotRPTracker(BotPressure) {
+#ifndef NDEBUG
+ NumInstrsScheduled = 0;
+#endif
+ }
~ScheduleDAGMI() {
delete SchedImpl;
return RegionCriticalPSets;
}
+ /// getIssueWidth - Return the max instructions per scheduling group.
+ unsigned getIssueWidth() const {
+ return (InstrItins && InstrItins->SchedModel)
+ ? InstrItins->SchedModel->IssueWidth : 1;
+ }
+
+ /// getNumMicroOps - Return the number of issue slots required for this MI.
+ unsigned getNumMicroOps(MachineInstr *MI) const {
+ if (!InstrItins) return 1;
+ int UOps = InstrItins->getNumMicroOps(MI->getDesc().getSchedClass());
+ return (UOps >= 0) ? UOps : TII->getNumMicroOps(InstrItins, MI);
+ }
+
protected:
void initRegPressure();
void updateScheduledPressure(std::vector<unsigned> NewMaxPressure);
//===----------------------------------------------------------------------===//
namespace {
-/// ReadyQ encapsulates vector of "ready" SUnits with basic convenience methods
-/// for pushing and removing nodes. ReadyQ's are uniquely identified by an
-/// ID. SUnit::NodeQueueId us a mask of the ReadyQs that the SUnit is in.
+/// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience
+/// methods for pushing and removing nodes. ReadyQueue's are uniquely identified
+/// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in.
class ReadyQueue {
unsigned ID;
std::string Name;
/// current cycle in whichever direction at has moved, and maintains the state
/// of "hazards" and other interlocks at the current cycle.
struct SchedBoundary {
+ ScheduleDAGMI *DAG;
+
ReadyQueue Available;
ReadyQueue Pending;
bool CheckPending;
/// MinReadyCycle - Cycle of the soonest available instruction.
unsigned MinReadyCycle;
+ // Remember the greatest min operand latency.
+ unsigned MaxMinLatency;
+
/// Pending queues extend the ready queues with the same ID and the
/// PendingFlag set.
SchedBoundary(unsigned ID, const Twine &Name):
- Available(ID, Name+".A"),
+ DAG(0), Available(ID, Name+".A"),
Pending(ID << ConvergingScheduler::LogMaxQID, Name+".P"),
CheckPending(false), HazardRec(0), CurrCycle(0), IssueCount(0),
- MinReadyCycle(UINT_MAX) {}
+ MinReadyCycle(UINT_MAX), MaxMinLatency(0) {}
~SchedBoundary() { delete HazardRec; }
return Available.getID() == ConvergingScheduler::TopQID;
}
+ bool checkHazard(SUnit *SU);
+
void releaseNode(SUnit *SU, unsigned ReadyCycle);
void bumpCycle();
+ void bumpNode(SUnit *SU);
+
void releasePending();
void removeReady(SUnit *SU);
void ConvergingScheduler::initialize(ScheduleDAGMI *dag) {
DAG = dag;
TRI = DAG->TRI;
+ Top.DAG = dag;
+ Bot.DAG = dag;
// Initialize the HazardRecognizers.
const TargetMachine &TM = DAG->MF.getTarget();
}
void ConvergingScheduler::releaseTopNode(SUnit *SU) {
- Top.releaseNode(SU, SU->getDepth());
+ if (SU->isScheduled)
+ return;
+
+ for (SUnit::succ_iterator I = SU->Preds.begin(), E = SU->Preds.end();
+ I != E; ++I) {
+ unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle;
+ unsigned Latency =
+ DAG->computeOperandLatency(I->getSUnit(), SU, *I, /*FindMin=*/true);
+#ifndef NDEBUG
+ Top.MaxMinLatency = std::max(Latency, Top.MaxMinLatency);
+#endif
+ if (SU->TopReadyCycle < PredReadyCycle + Latency)
+ SU->TopReadyCycle = PredReadyCycle + Latency;
+ }
+ Top.releaseNode(SU, SU->TopReadyCycle);
}
void ConvergingScheduler::releaseBottomNode(SUnit *SU) {
- Bot.releaseNode(SU, SU->getHeight());
+ if (SU->isScheduled)
+ return;
+
+ assert(SU->getInstr() && "Scheduled SUnit must have instr");
+
+ for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
+ I != E; ++I) {
+ unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle;
+ unsigned Latency =
+ DAG->computeOperandLatency(SU, I->getSUnit(), *I, /*FindMin=*/true);
+#ifndef NDEBUG
+ Bot.MaxMinLatency = std::max(Latency, Bot.MaxMinLatency);
+#endif
+ if (SU->BotReadyCycle < SuccReadyCycle + Latency)
+ SU->BotReadyCycle = SuccReadyCycle + Latency;
+ }
+ Bot.releaseNode(SU, SU->BotReadyCycle);
+}
+
+/// Does this SU have a hazard within the current instruction group.
+///
+/// The scheduler supports two modes of hazard recognition. The first is the
+/// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
+/// supports highly complicated in-order reservation tables
+/// (ScoreboardHazardRecognizer) and arbitraty target-specific logic.
+///
+/// The second is a streamlined mechanism that checks for hazards based on
+/// simple counters that the scheduler itself maintains. It explicitly checks
+/// for instruction dispatch limitations, including the number of micro-ops that
+/// can dispatch per cycle.
+///
+/// TODO: Also check whether the SU must start a new group.
+bool ConvergingScheduler::SchedBoundary::checkHazard(SUnit *SU) {
+ if (HazardRec->isEnabled())
+ return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard;
+
+ if (IssueCount + DAG->getNumMicroOps(SU->getInstr()) > DAG->getIssueWidth())
+ return true;
+
+ return false;
}
void ConvergingScheduler::SchedBoundary::releaseNode(SUnit *SU,
unsigned ReadyCycle) {
- if (SU->isScheduled)
- return;
-
if (ReadyCycle < MinReadyCycle)
MinReadyCycle = ReadyCycle;
// Check for interlocks first. For the purpose of other heuristics, an
// instruction that cannot issue appears as if it's not in the ReadyQueue.
- if (HazardRec->isEnabled()
- && HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard)
+ if (ReadyCycle > CurrCycle || checkHazard(SU))
Pending.push(SU);
else
Available.push(SU);
/// Move the boundary of scheduled code by one cycle.
void ConvergingScheduler::SchedBoundary::bumpCycle() {
- IssueCount = 0;
+ unsigned Width = DAG->getIssueWidth();
+ IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width;
assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized");
unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle);
if (!HazardRec->isEnabled()) {
- // Bypass lots of virtual calls in case of long latency.
+ // Bypass HazardRec virtual calls.
CurrCycle = NextCycle;
}
else {
+ // Bypass getHazardType calls in case of long latency.
for (; CurrCycle != NextCycle; ++CurrCycle) {
if (isTop())
HazardRec->AdvanceCycle();
<< CurrCycle << '\n');
}
+/// Move the boundary of scheduled code by one SUnit.
+void ConvergingScheduler::SchedBoundary::bumpNode(SUnit *SU) {
+ // Update the reservation table.
+ if (HazardRec->isEnabled()) {
+ if (!isTop() && SU->isCall) {
+ // Calls are scheduled with their preceding instructions. For bottom-up
+ // scheduling, clear the pipeline state before emitting.
+ HazardRec->Reset();
+ }
+ HazardRec->EmitInstruction(SU);
+ }
+ // Check the instruction group dispatch limit.
+ // TODO: Check if this SU must end a dispatch group.
+ IssueCount += DAG->getNumMicroOps(SU->getInstr());
+ if (IssueCount >= DAG->getIssueWidth()) {
+ DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n');
+ bumpCycle();
+ }
+}
+
/// Release pending ready nodes in to the available queue. This makes them
/// visible to heuristics.
void ConvergingScheduler::SchedBoundary::releasePending() {
// so, add them to the available queue.
for (unsigned i = 0, e = Pending.size(); i != e; ++i) {
SUnit *SU = *(Pending.begin()+i);
- unsigned ReadyCycle = isTop() ? SU->getHeight() : SU->getDepth();
+ unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
if (ReadyCycle < MinReadyCycle)
MinReadyCycle = ReadyCycle;
if (ReadyCycle > CurrCycle)
continue;
- if (HazardRec->isEnabled()
- && HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard)
+ if (checkHazard(SU))
continue;
Available.push(SU);
releasePending();
for (unsigned i = 0; Available.empty(); ++i) {
- assert(i <= HazardRec->getMaxLookAhead() && "permanent hazard"); (void)i;
+ assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
+ "permanent hazard"); (void)i;
bumpCycle();
releasePending();
}
/// Update the scheduler's state after scheduling a node. This is the same node
/// that was just returned by pickNode(). However, ScheduleDAGMI needs to update
-/// it's state based on the current cycle before MachineSchedStrategy.
+/// it's state based on the current cycle before MachineSchedStrategy does.
void ConvergingScheduler::schedNode(SUnit *SU, bool IsTopNode) {
- // Update the reservation table.
- if (IsTopNode && Top.HazardRec->isEnabled()) {
- Top.HazardRec->EmitInstruction(SU);
- if (Top.HazardRec->atIssueLimit()) {
- DEBUG(dbgs() << "*** Max instrs at cycle " << Top.CurrCycle << '\n');
- Top.bumpCycle();
- }
+ if (IsTopNode) {
+ SU->TopReadyCycle = Top.CurrCycle;
+ Top.bumpNode(SU);
}
- else if (Bot.HazardRec->isEnabled()) {
- if (SU->isCall) {
- // Calls are scheduled with their preceding instructions. For bottom-up
- // scheduling, clear the pipeline state before emitting.
- Bot.HazardRec->Reset();
- }
- Bot.HazardRec->EmitInstruction(SU);
- if (Bot.HazardRec->atIssueLimit()) {
- DEBUG(dbgs() << "*** Max instrs at cycle " << Bot.CurrCycle << '\n');
- Bot.bumpCycle();
- }
+ else {
+ SU->BotReadyCycle = Bot.CurrCycle;
+ Bot.bumpNode(SU);
}
}
projects / oota-llvm.git / blobdiff