Revert "[MISched] Introduce and use ResourceSegments."

Reverted because it produces the following builbot failure at https://lab.llvm.org/buildbot#builders/9/builds/27319:

/b/ml-opt-rel-x86-64-b1/llvm-project/llvm/unittests/CodeGen/SchedBoundary.cpp: In member function ‘virtual void ResourceSegments_getFirstAvailableAtFromBottom_empty_Test::TestBody()’:
/b/ml-opt-rel-x86-64-b1/llvm-project/llvm/unittests/CodeGen/SchedBoundary.cpp:395:31: error: call of overloaded ‘ResourceSegments(<brace-enclosed initializer list>)’ is ambiguous
 395 |   auto X = ResourceSegments({});
     |                               ^

This reverts commit dc312f0331309692e8d6e06e93b3492b6a40989f.

1 files changed, 21 insertions, 166 deletions

diff --git a/llvm/lib/CodeGen/MachineScheduler.cpp b/llvm/lib/CodeGen/MachineScheduler.cpp
index 59248bd..b5b9180 100644
--- a/llvm/lib/CodeGen/MachineScheduler.cpp
+++ b/llvm/lib/CodeGen/MachineScheduler.cpp
@@ -162,10 +162,6 @@ 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;
 
@@ -2172,7 +2168,6 @@ void SchedBoundary::reset() {
   ZoneCritResIdx = 0;
   IsResourceLimited = false;
   ReservedCycles.clear();
-  ReservedResourceSegments.clear();
   ReservedCyclesIndex.clear();
   ResourceGroupSubUnitMasks.clear();
 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
@@ -2201,8 +2196,7 @@ init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel) {
            PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
       unsigned PIdx = PI->ProcResourceIdx;
       unsigned Factor = SchedModel->getResourceFactor(PIdx);
-      assert(PI->Cycles >= PI->StartAtCycle);
-      RemainingCounts[PIdx] += (Factor * (PI->Cycles - PI->StartAtCycle));
+      RemainingCounts[PIdx] += (Factor * PI->Cycles);
     }
   }
 }
@@ -2255,17 +2249,7 @@ 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 StartAtCycle) {
-  if (SchedModel && SchedModel->enableIntervals()) {
-    if (isTop())
-      return ReservedResourceSegments[InstanceIdx].getFirstAvailableAtFromTop(
-          CurrCycle, StartAtCycle, Cycles);
-
-    return ReservedResourceSegments[InstanceIdx].getFirstAvailableAtFromBottom(
-        CurrCycle, StartAtCycle, Cycles);
-  }
-
+                                                       unsigned Cycles) {
   unsigned NextUnreserved = ReservedCycles[InstanceIdx];
   // If this resource has never been used, always return cycle zero.
   if (NextUnreserved == InvalidCycle)
@@ -2281,7 +2265,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 StartAtCycle) {
+                                    unsigned Cycles) {
 
   unsigned MinNextUnreserved = InvalidCycle;
   unsigned InstanceIdx = 0;
@@ -2310,7 +2294,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, StartAtCycle);
+          getNextResourceCycle(SC, SubUnits[I], Cycles);
       if (MinNextUnreserved > NextUnreserved) {
         InstanceIdx = NextInstanceIdx;
         MinNextUnreserved = NextUnreserved;
@@ -2321,8 +2305,7 @@ SchedBoundary::getNextResourceCycle(const MCSchedClassDesc *SC, unsigned PIdx,
 
   for (unsigned I = StartIndex, End = StartIndex + NumberOfInstances; I < End;
        ++I) {
-    unsigned NextUnreserved =
-        getNextResourceCycleByInstance(I, Cycles, StartAtCycle);
+    unsigned NextUnreserved = getNextResourceCycleByInstance(I, Cycles);
     if (MinNextUnreserved > NextUnreserved) {
       InstanceIdx = I;
       MinNextUnreserved = NextUnreserved;
@@ -2372,10 +2355,8 @@ 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, StartAtCycle);
+      std::tie(NRCycle, InstanceIdx) = getNextResourceCycle(SC, ResIdx, Cycles);
       if (NRCycle > CurrCycle) {
 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
         MaxObservedStall = std::max(Cycles, MaxObservedStall);
@@ -2526,10 +2507,9 @@ 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 StartAtCycle) {
+                                      unsigned Cycles, unsigned NextCycle) {
   unsigned Factor = SchedModel->getResourceFactor(PIdx);
-  unsigned Count = Factor * (Cycles - StartAtCycle);
+  unsigned Count = Factor * Cycles;
   LLVM_DEBUG(dbgs() << "  " << SchedModel->getResourceName(PIdx) << " +"
                     << Cycles << "x" << Factor << "u\n");
 
@@ -2549,8 +2529,7 @@ 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, StartAtCycle);
+  std::tie(NextAvailable, InstanceIdx) = getNextResourceCycle(SC, PIdx, Cycles);
   if (NextAvailable > CurrCycle) {
     LLVM_DEBUG(dbgs() << "  Resource conflict: "
                       << SchedModel->getResourceName(PIdx)
@@ -2629,8 +2608,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, PI->StartAtCycle);
+      unsigned RCycle =
+        countResource(SC, PI->ProcResourceIdx, PI->Cycles, NextCycle);
       if (RCycle > NextCycle)
         NextCycle = RCycle;
     }
@@ -2644,33 +2623,14 @@ void SchedBoundary::bumpNode(SUnit *SU) {
              PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
         unsigned PIdx = PI->ProcResourceIdx;
         if (SchedModel->getProcResource(PIdx)->BufferSize == 0) {
-
-          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;
-          }
+          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;
         }
       }
     }
@@ -2810,14 +2770,8 @@ 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 << ") = ";
-      if (SchedModel && SchedModel->enableIntervals()) {
-        if (ReservedResourceSegments.count(StartIdx + UnitIdx))
-          dbgs() << ReservedResourceSegments.at(StartIdx + UnitIdx);
-        else
-          dbgs() << "{ }\n";
-      } else
-        dbgs() << ReservedCycles[StartIdx + UnitIdx] << "\n";
+      dbgs() << ResName << "(" << UnitIdx
+             << ") = " << ReservedCycles[StartIdx + UnitIdx] << "\n";
     }
     StartIdx += NumUnits;
   }
@@ -4184,102 +4138,3 @@ 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;
-    }
-  }
-}