aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/CodeGen/MachineScheduler.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CodeGen/MachineScheduler.cpp')
-rw-r--r--llvm/lib/CodeGen/MachineScheduler.cpp187
1 files changed, 166 insertions, 21 deletions
diff --git a/llvm/lib/CodeGen/MachineScheduler.cpp b/llvm/lib/CodeGen/MachineScheduler.cpp
index b5b9180..59248bd 100644
--- a/llvm/lib/CodeGen/MachineScheduler.cpp
+++ b/llvm/lib/CodeGen/MachineScheduler.cpp
@@ -162,6 +162,10 @@ static cl::opt<unsigned>
cl::init(5));
#endif
+static cl::opt<unsigned>
+ MIResourceCutOff("misched-resource-cutoff", cl::Hidden,
+ cl::desc("Number of intervals to track"), cl::init(10));
+
// DAG subtrees must have at least this many nodes.
static const unsigned MinSubtreeSize = 8;
@@ -2168,6 +2172,7 @@ void SchedBoundary::reset() {
ZoneCritResIdx = 0;
IsResourceLimited = false;
ReservedCycles.clear();
+ ReservedResourceSegments.clear();
ReservedCyclesIndex.clear();
ResourceGroupSubUnitMasks.clear();
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
@@ -2196,7 +2201,8 @@ init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel) {
PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
unsigned PIdx = PI->ProcResourceIdx;
unsigned Factor = SchedModel->getResourceFactor(PIdx);
- RemainingCounts[PIdx] += (Factor * PI->Cycles);
+ assert(PI->Cycles >= PI->StartAtCycle);
+ RemainingCounts[PIdx] += (Factor * (PI->Cycles - PI->StartAtCycle));
}
}
}
@@ -2249,7 +2255,17 @@ unsigned SchedBoundary::getLatencyStallCycles(SUnit *SU) {
/// Compute the next cycle at which the given processor resource unit
/// can be scheduled.
unsigned SchedBoundary::getNextResourceCycleByInstance(unsigned InstanceIdx,
- unsigned Cycles) {
+ unsigned Cycles,
+ unsigned StartAtCycle) {
+ if (SchedModel && SchedModel->enableIntervals()) {
+ if (isTop())
+ return ReservedResourceSegments[InstanceIdx].getFirstAvailableAtFromTop(
+ CurrCycle, StartAtCycle, Cycles);
+
+ return ReservedResourceSegments[InstanceIdx].getFirstAvailableAtFromBottom(
+ CurrCycle, StartAtCycle, Cycles);
+ }
+
unsigned NextUnreserved = ReservedCycles[InstanceIdx];
// If this resource has never been used, always return cycle zero.
if (NextUnreserved == InvalidCycle)
@@ -2265,7 +2281,7 @@ unsigned SchedBoundary::getNextResourceCycleByInstance(unsigned InstanceIdx,
/// instance in the reserved cycles vector.
std::pair<unsigned, unsigned>
SchedBoundary::getNextResourceCycle(const MCSchedClassDesc *SC, unsigned PIdx,
- unsigned Cycles) {
+ unsigned Cycles, unsigned StartAtCycle) {
unsigned MinNextUnreserved = InvalidCycle;
unsigned InstanceIdx = 0;
@@ -2294,7 +2310,7 @@ SchedBoundary::getNextResourceCycle(const MCSchedClassDesc *SC, unsigned PIdx,
for (unsigned I = 0, End = NumberOfInstances; I < End; ++I) {
unsigned NextUnreserved, NextInstanceIdx;
std::tie(NextUnreserved, NextInstanceIdx) =
- getNextResourceCycle(SC, SubUnits[I], Cycles);
+ getNextResourceCycle(SC, SubUnits[I], Cycles, StartAtCycle);
if (MinNextUnreserved > NextUnreserved) {
InstanceIdx = NextInstanceIdx;
MinNextUnreserved = NextUnreserved;
@@ -2305,7 +2321,8 @@ SchedBoundary::getNextResourceCycle(const MCSchedClassDesc *SC, unsigned PIdx,
for (unsigned I = StartIndex, End = StartIndex + NumberOfInstances; I < End;
++I) {
- unsigned NextUnreserved = getNextResourceCycleByInstance(I, Cycles);
+ unsigned NextUnreserved =
+ getNextResourceCycleByInstance(I, Cycles, StartAtCycle);
if (MinNextUnreserved > NextUnreserved) {
InstanceIdx = I;
MinNextUnreserved = NextUnreserved;
@@ -2355,8 +2372,10 @@ bool SchedBoundary::checkHazard(SUnit *SU) {
SchedModel->getWriteProcResEnd(SC))) {
unsigned ResIdx = PE.ProcResourceIdx;
unsigned Cycles = PE.Cycles;
+ unsigned StartAtCycle = PE.StartAtCycle;
unsigned NRCycle, InstanceIdx;
- std::tie(NRCycle, InstanceIdx) = getNextResourceCycle(SC, ResIdx, Cycles);
+ std::tie(NRCycle, InstanceIdx) =
+ getNextResourceCycle(SC, ResIdx, Cycles, StartAtCycle);
if (NRCycle > CurrCycle) {
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
MaxObservedStall = std::max(Cycles, MaxObservedStall);
@@ -2507,9 +2526,10 @@ void SchedBoundary::incExecutedResources(unsigned PIdx, unsigned Count) {
/// \return the next cycle at which the instruction may execute without
/// oversubscribing resources.
unsigned SchedBoundary::countResource(const MCSchedClassDesc *SC, unsigned PIdx,
- unsigned Cycles, unsigned NextCycle) {
+ unsigned Cycles, unsigned NextCycle,
+ unsigned StartAtCycle) {
unsigned Factor = SchedModel->getResourceFactor(PIdx);
- unsigned Count = Factor * Cycles;
+ unsigned Count = Factor * (Cycles - StartAtCycle);
LLVM_DEBUG(dbgs() << " " << SchedModel->getResourceName(PIdx) << " +"
<< Cycles << "x" << Factor << "u\n");
@@ -2529,7 +2549,8 @@ unsigned SchedBoundary::countResource(const MCSchedClassDesc *SC, unsigned PIdx,
}
// For reserved resources, record the highest cycle using the resource.
unsigned NextAvailable, InstanceIdx;
- std::tie(NextAvailable, InstanceIdx) = getNextResourceCycle(SC, PIdx, Cycles);
+ std::tie(NextAvailable, InstanceIdx) =
+ getNextResourceCycle(SC, PIdx, Cycles, StartAtCycle);
if (NextAvailable > CurrCycle) {
LLVM_DEBUG(dbgs() << " Resource conflict: "
<< SchedModel->getResourceName(PIdx)
@@ -2608,8 +2629,8 @@ void SchedBoundary::bumpNode(SUnit *SU) {
for (TargetSchedModel::ProcResIter
PI = SchedModel->getWriteProcResBegin(SC),
PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
- unsigned RCycle =
- countResource(SC, PI->ProcResourceIdx, PI->Cycles, NextCycle);
+ unsigned RCycle = countResource(SC, PI->ProcResourceIdx, PI->Cycles,
+ NextCycle, PI->StartAtCycle);
if (RCycle > NextCycle)
NextCycle = RCycle;
}
@@ -2623,14 +2644,33 @@ void SchedBoundary::bumpNode(SUnit *SU) {
PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
unsigned PIdx = PI->ProcResourceIdx;
if (SchedModel->getProcResource(PIdx)->BufferSize == 0) {
- unsigned ReservedUntil, InstanceIdx;
- std::tie(ReservedUntil, InstanceIdx) =
- getNextResourceCycle(SC, PIdx, 0);
- if (isTop()) {
- ReservedCycles[InstanceIdx] =
- std::max(ReservedUntil, NextCycle + PI->Cycles);
- } else
- ReservedCycles[InstanceIdx] = NextCycle;
+
+ if (SchedModel && SchedModel->enableIntervals()) {
+ unsigned ReservedUntil, InstanceIdx;
+ std::tie(ReservedUntil, InstanceIdx) =
+ getNextResourceCycle(SC, PIdx, PI->Cycles, PI->StartAtCycle);
+ if (isTop()) {
+ ReservedResourceSegments[InstanceIdx].add(
+ ResourceSegments::getResourceIntervalTop(
+ NextCycle, PI->StartAtCycle, PI->Cycles),
+ MIResourceCutOff);
+ } else {
+ ReservedResourceSegments[InstanceIdx].add(
+ ResourceSegments::getResourceIntervalBottom(
+ NextCycle, PI->StartAtCycle, PI->Cycles),
+ MIResourceCutOff);
+ }
+ } else {
+
+ unsigned ReservedUntil, InstanceIdx;
+ std::tie(ReservedUntil, InstanceIdx) =
+ getNextResourceCycle(SC, PIdx, 0, PI->StartAtCycle);
+ if (isTop()) {
+ ReservedCycles[InstanceIdx] =
+ std::max(ReservedUntil, NextCycle + PI->Cycles);
+ } else
+ ReservedCycles[InstanceIdx] = NextCycle;
+ }
}
}
}
@@ -2770,8 +2810,14 @@ LLVM_DUMP_METHOD void SchedBoundary::dumpReservedCycles() const {
const unsigned NumUnits = SchedModel->getProcResource(ResIdx)->NumUnits;
std::string ResName = SchedModel->getResourceName(ResIdx);
for (unsigned UnitIdx = 0; UnitIdx < NumUnits; ++UnitIdx) {
- dbgs() << ResName << "(" << UnitIdx
- << ") = " << ReservedCycles[StartIdx + UnitIdx] << "\n";
+ dbgs() << ResName << "(" << UnitIdx << ") = ";
+ if (SchedModel && SchedModel->enableIntervals()) {
+ if (ReservedResourceSegments.count(StartIdx + UnitIdx))
+ dbgs() << ReservedResourceSegments.at(StartIdx + UnitIdx);
+ else
+ dbgs() << "{ }\n";
+ } else
+ dbgs() << ReservedCycles[StartIdx + UnitIdx] << "\n";
}
StartIdx += NumUnits;
}
@@ -4138,3 +4184,102 @@ void ScheduleDAGMI::viewGraph(const Twine &Name, const Twine &Title) {
void ScheduleDAGMI::viewGraph() {
viewGraph(getDAGName(), "Scheduling-Units Graph for " + getDAGName());
}
+
+/// Sort predicate for the intervals stored in an instance of
+/// ResourceSegments. Intervals are always disjoint (no intersection
+/// for any pairs of intervals), therefore we can sort the totality of
+/// the intervals by looking only at the left boundary.
+static bool sortIntervals(const ResourceSegments::IntervalTy &A,
+ const ResourceSegments::IntervalTy &B) {
+ return A.first < B.first;
+}
+
+unsigned ResourceSegments::getFirstAvailableAt(
+ unsigned CurrCycle, unsigned StartAtCycle, unsigned Cycle,
+ std::function<ResourceSegments::IntervalTy(unsigned, unsigned, unsigned)>
+ IntervalBuilder) const {
+ assert(std::is_sorted(std::begin(_Intervals), std::end(_Intervals),
+ sortIntervals) &&
+ "Cannot execute on an un-sorted set of intervals.");
+ unsigned RetCycle = CurrCycle;
+ ResourceSegments::IntervalTy NewInterval =
+ IntervalBuilder(RetCycle, StartAtCycle, Cycle);
+ for (auto &Interval : _Intervals) {
+ if (!intersects(NewInterval, Interval))
+ continue;
+
+ // Move the interval right next to the top of the one it
+ // intersects.
+ assert(Interval.second > NewInterval.first &&
+ "Invalid intervals configuration.");
+ RetCycle += (unsigned)Interval.second - (unsigned)NewInterval.first;
+ NewInterval = IntervalBuilder(RetCycle, StartAtCycle, Cycle);
+ }
+ return RetCycle;
+}
+
+void ResourceSegments::add(ResourceSegments::IntervalTy A,
+ const unsigned CutOff) {
+ using IntervalTy = ResourceSegments::IntervalTy;
+ assert(A.first < A.second && "Cannot add empty resource usage");
+ assert(CutOff > 0 && "0-size interval history has no use.");
+ assert(all_of(_Intervals,
+ [&A](const IntervalTy &Interval) -> bool {
+ return !intersects(A, Interval);
+ }) &&
+ "A resource is being overwritten");
+ _Intervals.push_back(A);
+
+ sortAndMerge();
+
+ // Do not keep the full history of the intervals, just the
+ // latest #CutOff.
+ while (_Intervals.size() > CutOff)
+ _Intervals.pop_front();
+}
+
+bool ResourceSegments::intersects(ResourceSegments::IntervalTy A,
+ ResourceSegments::IntervalTy B) {
+ assert(A.first <= A.second && "Invalid interval");
+ assert(B.first <= B.second && "Invalid interval");
+
+ // Share one boundary.
+ if ((A.first == B.first) || (A.second == B.second))
+ return true;
+
+ // full intersersect: [ *** ) B
+ // [***) A
+ if ((A.first > B.first) && (A.second < B.second))
+ return true;
+
+ // right intersect: [ ***) B
+ // [*** ) A
+ if ((A.first > B.first) && (A.first < B.second) && (A.second > B.second))
+ return true;
+
+ // left intersect: [*** ) B
+ // [ ***) A
+ if ((A.first < B.first) && (B.first < A.second) && (B.second > B.first))
+ return true;
+
+ return false;
+}
+
+void ResourceSegments::sortAndMerge() {
+ if (_Intervals.size() <= 1)
+ return;
+
+ // First sort the collection.
+ _Intervals.sort(sortIntervals);
+
+ // can use next because I have at least 2 elements in the list
+ auto next = std::next(std::begin(_Intervals));
+ auto E = std::end(_Intervals);
+ for (; next != E; ++next) {
+ if (std::prev(next)->second >= next->first) {
+ next->first = std::prev(next)->first;
+ _Intervals.erase(std::prev(next));
+ continue;
+ }
+ }
+}
generated by cgit v1.1 at 2025-09-30 13:31:29 +0000