Index: llvm/include/llvm/CodeGen/MachineScheduler.h =================================================================== --- llvm/include/llvm/CodeGen/MachineScheduler.h +++ llvm/include/llvm/CodeGen/MachineScheduler.h @@ -93,6 +93,7 @@ #include #include #include +#include #include #include @@ -673,12 +674,309 @@ // Is the scheduled region resource limited vs. latency limited. bool IsResourceLimited; - // Record the highest cycle at which each resource has been reserved by a - // scheduled instruction. - SmallVector ReservedCycles; +public: + /// ResourceSegments are a collection of intervals closed on the + /// left and opened on the right: + /// + /// list{ [a1, b1), [a2, b2), ..., [a_N, b_N) } + /// + /// The collection has the following properties: + /// + /// 1. The list is ordered: a_i < b_i and b_i < a_(i+1) + /// + /// 2. The intervals in the collection do not intersect each other. + /// + /// A \ref ResourceSegments instance represents the cycle + /// reservation history of the instance of and individual resource. + struct ResourceSegments { + public: + static bool empty_iterval(std::pair A) { + return A.first == A.second; + } + /// Adds an interval [a, b[ to the collection of the instance. + /// + /// When adding [a, b[ to the collection, the operation merges the + /// adjacent intervals. For example + /// + /// 0 1 2 3 4 5 6 7 8 9 10 + /// [-----) [--) [--) + /// + [--) + /// = [-----------) [--) + /// + /// To be able to debug duplicate resource usage, the function has + /// assertion that checks that no interval should be added if it + /// overlaps any of the intervals in the collection. We can + /// require this because by definition a \ref ResourceSegments is + /// attached only to an individual resource instance. + void add(std::pair A, const unsigned CutOff = 10) { + assert(A.first < A.second && "Cannot add empty resource usage"); + assert(CutOff > 0 && "0-size interval history has no use."); +#ifndef NDEBUG + for (auto Interval : _Intervals) + assert(!intersects(A, Interval) && "A resource is being overwritten"); +#endif + _Intervals.push_back(A); + + sort(); + merge(); + + // Do not keep the full history of the intervals, just the + // latest #CutOff. + while (_Intervals.size() > CutOff) + _Intervals.pop_front(); + } + + public: + static bool intersects(std::pair A, std::pair 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; + } + + /// These function return the interval used by a resource in bottom and top + /// scheduling. + /// + /// Consider an instruction that uses resources X0, X1 and X2 as follows: + /// + /// X0 X1 X1 X2 +--------+------------+------+ + /// |Resource|StartAtCycle|Cycles| + /// +--------+------------+------+ + /// | X0 | 0 | 1 | + /// +--------+------------+------+ + /// | X1 | 1 | 3 | + /// +--------+------------+------+ + /// | X2 | 3 | 4 | + /// +--------+------------+------+ + /// + /// If we can schedule the instruction at cycle C, we need to + /// compute the interval of the resource as follows: + /// + /// # TOP DOWN SCHEDULING + /// + /// Cycles scheduling flows to the _right_, in the same direction + /// of time. + /// + /// C 1 2 3 4 5 ... + /// ------|------|------|------|------|------|-----> + /// X0 X1 X1 X2 ---> direction of time + /// X0 [C, C+1) + /// X1 [C+1, C+3) + /// X2 [C+3, C+4) + /// + /// Therefore, the formula to compute the interval for a resource + /// of an instruction that can be scheduled at cycle C in top-down + /// scheduling is: + /// + /// [C+StartAtCycle, C+Cycles) + /// + /// + /// # BOTTOM UP SCHEDULING + /// + /// Cycles scheduling flows to the _left_, in opposite direction + /// of time. + /// + /// In bottom up scheduling, the scheduling happens in opposite + /// direction to the execution of the cycles of the + /// instruction. When the instruction is scheduled at cycle `C`, + /// the resources are allocated in the past relative to `C`: + /// + /// 2 1 C -1 -2 -3 -4 -5 ... + /// <-----|------|------|------|------|------|------|------|--- + /// X0 X1 X1 X2 ---> direction of time + /// X0 (C+1, C] + /// X1 (C, C-2] + /// X2 (C-2, C-3] + /// + /// Therefore, the formula to compute the interval for a resource + /// of an instruction that can be scheduled at cycle C in bottom-up + /// scheduling is: + /// + /// [C-Cycle+1, C-StartAtCycle+1) + static std::pair + getResourceIntervalBottom(unsigned C, unsigned StartAtCycle, + unsigned Cycle) { + return std::make_pair((long)C - (long)Cycle + 1L, + (long)C - (long)StartAtCycle + 1L); + } + static std::pair + getResourceIntervalTop(unsigned C, unsigned StartAtCycle, unsigned Cycle) { + return std::make_pair((long)C + (long)StartAtCycle, + (long)C + (long)Cycle); + } + + private: + /// Finds the first cycle in which a resource can be allocated. + /// + /// The function uses the \param IntervalBuider [*] to build a + /// resource interval [a, b[ out of the input parameters \param + /// CurrCycle, \param StartAtCycle and \param Cycle. + /// + /// The function then loops through the intervals in the ResourceSegments + /// and shifts the interval [a, b[ and the ReturnCycle to the + /// right until there is no intersection between the intervals of + /// the \ref ResourceSegments instance and the new shifted [a, b[. When + /// this condition is met, the ReturnCycle (which + /// correspond to the cycle in which the resource can be + /// allocated) is returned. + /// + /// c = CurrCycle in input + /// c 1 2 3 4 5 6 7 8 9 10 ... ---> (time + /// flow) + /// ResourceSegments... [---) [-------) [-----------) + /// c [1 3[ -> StartAtCycle=1, Cycles=3 + /// ++c [1 3) + /// ++c [1 3) + /// ++c [1 3) + /// ++c [1 3) + /// ++c [1 3) ---> returns c + /// incremented by 5 (c+5) + /// + /// + /// Notice that for bottom-up scheduling the diagram is slightly + /// different because the current cycle c is always on the right + /// of the interval [a, b) (see \ref + /// `getResourceIntervalBottom`). This is because the cycle + /// increments for bottom-up scheduling moved in the direction + /// opposite to the direction of time: + /// + /// --------> direction of time. + /// XXYZZZ (resource usage) + /// --------> direction of top-down execution cycles. + /// <-------- direction of bottom-up execution cycles. + /// + /// Even though bottom-up scheduling moves against the flow of + /// time, the algorithm used to find the first free slot in between + /// intervals is the same as for top-down scheduling. + /// + /// [*] See \ref `getResourceIntervalTop` and + /// \ref `getResourceIntervalBottom` to see how such resource intervals + /// are built. + unsigned getFirstAvailableAt( + unsigned CurrCycle, unsigned StartAtCycle, unsigned Cycle, + std::function(unsigned, unsigned, unsigned)> + IntervalBuilder) const { + assert(is_sorted() && "Cannot execute on an un-sorted set of intervals."); + unsigned RetCycle = CurrCycle; + auto 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); + RetCycle += (unsigned)Interval.second - (unsigned)NewInterval.first; + NewInterval = IntervalBuilder(RetCycle, StartAtCycle, Cycle); + } + return RetCycle; + } + + public: + /// getFirstAvailableAtFromBottom and getFirstAvailableAtFromTop + /// should be merged in a single function in which a function that + /// creates the `NewInterval` is passed as a parameter. + unsigned getFirstAvailableAtFromBottom(unsigned CurrCycle, + unsigned StartAtCycle, + unsigned Cycle) const { + return getFirstAvailableAt(CurrCycle, StartAtCycle, Cycle, + getResourceIntervalBottom); + } + unsigned getFirstAvailableAtFromTop(unsigned CurrCycle, + unsigned StartAtCycle, + unsigned Cycle) const { + return getFirstAvailableAt(CurrCycle, StartAtCycle, Cycle, + getResourceIntervalTop); + } - /// For each PIdx, stores first index into ReservedCycles that corresponds to - /// it. + private: + std::list> _Intervals; + static bool sort_predicate(const std::pair &A, + const std::pair &B) { + return A.first < B.first; + } + void sort() { _Intervals.sort(sort_predicate); } + bool is_sorted() const { + return std::is_sorted(std::begin(_Intervals), std::end(_Intervals), + sort_predicate); + } + void merge() { + if (_Intervals.size() <= 1) + return; + + // 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; + } + } + } + + public: + // constructor for empty set + explicit ResourceSegments(){}; + bool empty() const { return _Intervals.empty(); } + explicit ResourceSegments(std::list> Intervals) + : _Intervals(Intervals) { + sort(); + merge(); + } + + friend bool operator==(const ResourceSegments &c1, + const ResourceSegments &c2) { + return c1._Intervals == c2._Intervals; + } + // Needed for printing intervals in gtest. + friend std::ostream &operator<<(std::ostream &os, + const ResourceSegments &Segments) { + os << "{ "; + for (auto p : Segments._Intervals) + os << "[" << p.first << ", " << p.second << "), "; + os << "}\n"; + return os; + } +#ifndef NDEBUG + friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os, + const ResourceSegments &Segments) { + os << "{ "; + for (auto p : Segments._Intervals) + os << "[" << p.first << ", " << p.second << "), "; + os << "}\n"; + return os; + } +#endif + }; + +private: + /// Record how resources have been allocated across the cycles of + /// the execution. + std::map ReservedResourceSegments; + std::vector ReservedCycles; + /// For each PIdx, stores first index into ReservedResourceSegments that + /// corresponds to it. /// /// For example, consider the following 3 resources (ResourceCount = /// 3): @@ -694,12 +992,14 @@ /// +------------+--------+ /// /// In this case, the total number of resource instances is 6. The - /// vector \ref ReservedCycles will have a slot for each instance. The - /// vector \ref ReservedCyclesIndex will track at what index the first + /// vector \ref ReservedResourceSegments will have a slot for each instance. + /// The vector \ref ReservedCyclesIndex will track at what index the first /// instance of the resource is found in the vector of \ref - /// ReservedCycles: + /// ReservedResourceSegments: + /// + /// Indexes of instances in + /// ReservedResourceSegments /// - /// Indexes of instances in ReservedCycles /// 0 1 2 3 4 5 /// ReservedCyclesIndex[0] = 0; [X0, X1, /// ReservedCyclesIndex[1] = 2; Y0, Y1, Y2 @@ -784,11 +1084,13 @@ unsigned getLatencyStallCycles(SUnit *SU); unsigned getNextResourceCycleByInstance(unsigned InstanceIndex, - unsigned Cycles); + unsigned Cycles, + unsigned StartAtCycle); std::pair getNextResourceCycle(const MCSchedClassDesc *SC, unsigned PIdx, - unsigned Cycles); + unsigned Cycles, + unsigned StartAtCycle); bool isUnbufferedGroup(unsigned PIdx) const { return SchedModel->getProcResource(PIdx)->SubUnitsIdxBegin && @@ -817,7 +1119,8 @@ void incExecutedResources(unsigned PIdx, unsigned Count); unsigned countResource(const MCSchedClassDesc *SC, unsigned PIdx, - unsigned Cycles, unsigned ReadyCycle); + unsigned Cycles, unsigned ReadyCycle, + unsigned StartAtCycle); void bumpNode(SUnit *SU); Index: llvm/include/llvm/CodeGen/TargetSchedule.h =================================================================== --- llvm/include/llvm/CodeGen/TargetSchedule.h +++ llvm/include/llvm/CodeGen/TargetSchedule.h @@ -90,7 +90,7 @@ bool hasInstrSchedModelOrItineraries() const { return hasInstrSchedModel() || hasInstrItineraries(); } - + bool enableIntervals() const { return SchedModel.EnableIntervals; } /// Identify the processor corresponding to the current subtarget. unsigned getProcessorID() const { return SchedModel.getProcessorID(); } Index: llvm/include/llvm/MC/MCSchedule.h =================================================================== --- llvm/include/llvm/MC/MCSchedule.h +++ llvm/include/llvm/MC/MCSchedule.h @@ -303,6 +303,11 @@ bool CompleteModel; + // Mirrors the field `EnableIntervals` of the tablegen class + // `SchedMachineModel` in + // llvm/include/llvm/Target/TargetSchedule.td. + bool EnableIntervals; + unsigned ProcID; const MCProcResourceDesc *ProcResourceTable; const MCSchedClassDesc *SchedClassTable; Index: llvm/include/llvm/Target/TargetSchedule.td =================================================================== --- llvm/include/llvm/Target/TargetSchedule.td +++ llvm/include/llvm/Target/TargetSchedule.td @@ -117,6 +117,11 @@ list UnsupportedFeatures = []; bit NoModel = false; // Special tag to indicate missing machine model. + + // Tells the MachineScheduler whether or not to track resource usage + // using intervals via ResourceSegments (see + // llvm/include/llvm/CodeGen/MachineScheduler.h). + bit EnableIntervals = false; } def NoSchedModel : SchedMachineModel { Index: llvm/lib/CodeGen/MachineScheduler.cpp =================================================================== --- llvm/lib/CodeGen/MachineScheduler.cpp +++ llvm/lib/CodeGen/MachineScheduler.cpp @@ -165,6 +165,10 @@ cl::desc("Sort the resources printed in the dump trace")); #endif +static cl::opt + 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; @@ -2200,6 +2204,7 @@ ZoneCritResIdx = 0; IsResourceLimited = false; ReservedCycles.clear(); + ReservedResourceSegments.clear(); ReservedCyclesIndex.clear(); ResourceGroupSubUnitMasks.clear(); #if LLVM_ENABLE_ABI_BREAKING_CHECKS @@ -2228,7 +2233,8 @@ 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)); } } } @@ -2281,7 +2287,17 @@ /// 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] + .getFirstAvailableAtFromBottom(CurrCycle, StartAtCycle, Cycles); + else + return ReservedResourceSegments[InstanceIdx].getFirstAvailableAtFromTop( + CurrCycle, StartAtCycle, Cycles); + } + unsigned NextUnreserved = ReservedCycles[InstanceIdx]; // If this resource has never been used, always return cycle zero. if (NextUnreserved == InvalidCycle) @@ -2297,7 +2313,7 @@ /// instance in the reserved cycles vector. std::pair SchedBoundary::getNextResourceCycle(const MCSchedClassDesc *SC, unsigned PIdx, - unsigned Cycles) { + unsigned Cycles, unsigned StartAtCycle) { unsigned MinNextUnreserved = InvalidCycle; unsigned InstanceIdx = 0; @@ -2326,7 +2342,7 @@ 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; @@ -2337,7 +2353,8 @@ 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; @@ -2387,8 +2404,10 @@ 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); @@ -2539,9 +2558,10 @@ /// \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"); @@ -2561,7 +2581,8 @@ } // 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) @@ -2640,8 +2661,8 @@ 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; } @@ -2655,14 +2676,32 @@ 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( + SchedBoundary::ResourceSegments::getResourceIntervalTop( + NextCycle, PI->StartAtCycle, PI->Cycles), + MIResourceCutOff); + else + ReservedResourceSegments[InstanceIdx].add( + SchedBoundary::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; + } } } } @@ -2802,8 +2841,14 @@ 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; } Index: llvm/lib/MC/MCSchedule.cpp =================================================================== --- llvm/lib/MC/MCSchedule.cpp +++ llvm/lib/MC/MCSchedule.cpp @@ -30,6 +30,7 @@ DefaultMispredictPenalty, false, true, + false /*EnableIntervals*/, 0, nullptr, nullptr, Index: llvm/unittests/CodeGen/CMakeLists.txt =================================================================== --- llvm/unittests/CodeGen/CMakeLists.txt +++ llvm/unittests/CodeGen/CMakeLists.txt @@ -38,6 +38,7 @@ TargetOptionsTest.cpp TestAsmPrinter.cpp MLRegallocDevelopmentFeatures.cpp + SchedBoundary.cpp ) add_subdirectory(GlobalISel) Index: llvm/unittests/CodeGen/SchedBoundary.cpp =================================================================== --- /dev/null +++ llvm/unittests/CodeGen/SchedBoundary.cpp @@ -0,0 +1,401 @@ +#include "llvm/CodeGen/MachineScheduler.h" + +#include "gtest/gtest.h" + +using namespace llvm; + +using ResourceSegments = SchedBoundary::ResourceSegments; + +#ifndef NDEBUG +TEST(ResourceSegmentsDeath, OverwriteOnRight) { + auto X = ResourceSegments({{10, 20}}); + EXPECT_DEATH(X.add({15, 30}), "A resource is being overwritten"); +} + +TEST(ResourceSegmentsDeath, OverwriteOnLeft) { + auto X = ResourceSegments({{10, 20}}); + EXPECT_DEATH(X.add({5, 11}), "A resource is being overwritten"); + ; +} + +TEST(ResourceSegmentsDeath, FullOverwrite) { + auto X = ResourceSegments({{10, 20}}); + EXPECT_DEATH(X.add({15, 18}), "A resource is being overwritten"); +} + +TEST(ResourceSegmentsDeath, ZeroSizeIntervalsNotAllowed) { + auto X = ResourceSegments({{10, 20}}); + EXPECT_DEATH(X.add({20, 30}, 0), "0-size interval history has no use."); +} +#endif // NDEBUG + +TEST(ResourceSegments, ConsecutiveLeftNoOverlap) { + auto X = ResourceSegments({{10, 20}}); + X.add({7, 9}); + EXPECT_EQ(X, ResourceSegments({{7, 9}, {10, 20}})); +} + +TEST(ResourceSegments, ConsecutiveLeftWithOverlap) { + auto X = ResourceSegments({{10, 20}}); + X.add({7, 10}); + EXPECT_EQ(X, ResourceSegments({{7, 20}})); +} + +TEST(ResourceSegments, ConsecutiveRightNoOverlap) { + auto X = ResourceSegments({{10, 20}}); + X.add({21, 22}); + EXPECT_EQ(X, ResourceSegments({{10, 20}, {21, 22}})); +} + +TEST(ResourceSegments, ConsecutiveRightWithOverlap) { + auto X = ResourceSegments({{10, 20}}); + X.add({20, 22}); + EXPECT_EQ(X, ResourceSegments({{10, 22}})); +} + +TEST(ResourceSegments, Disjoint) { + auto X = ResourceSegments({{10, 20}}); + X.add({22, 23}); + EXPECT_EQ(X, ResourceSegments({{10, 20}, {22, 23}})); +} + +TEST(ResourceSegments, SortAfterAdd) { + auto X = ResourceSegments({{10, 20}, {3, 4}}); + X.add({6, 8}); + EXPECT_EQ(X, ResourceSegments({{3, 4}, {6, 8}, {10, 20}})); +} + +TEST(ResourceSegments, AddWithCutOff) { + auto X = ResourceSegments({{1, 2}, {3, 4}}); + X.add({6, 8}, 2); + EXPECT_EQ(X, ResourceSegments({{3, 4}, {6, 8}})); +} + +TEST(ResourceSegments, add_01) { + auto X = ResourceSegments({{10, 20}, {30, 40}}); + X.add({21, 29}); + EXPECT_EQ(X, ResourceSegments({{10, 20}, {21, 29}, {30, 40}})); +} + +TEST(ResourceSegments, add_02) { + auto X = ResourceSegments({{10, 20}, {30, 40}}); + X.add({22, 29}); + EXPECT_EQ(X, ResourceSegments({{10, 20}, {22, 29}, {30, 40}})); + X.add({29, 30}); + EXPECT_EQ(X, ResourceSegments({{10, 20}, {22, 40}})); +} + +#ifndef NDEBUG +TEST(ResourceSegmentsDeath, add_empty) { + auto X = ResourceSegments({{10, 20}, {30, 40}}); + EXPECT_DEATH(X.add({22, 22}), "Cannot add empty resource usage"); +} +#endif + +TEST(ResourceSegments, sort_two) { + EXPECT_EQ(ResourceSegments({{30, 40}, {10, 28}}), + ResourceSegments({{10, 28}, {30, 40}})); +} + +TEST(ResourceSegments, sort_three) { + EXPECT_EQ(ResourceSegments({{30, 40}, {71, 200}, {10, 29}}), + ResourceSegments({{10, 29}, {30, 40}, {71, 200}})); +} + +TEST(ResourceSegments, merge_two) { + EXPECT_EQ(ResourceSegments({{10, 33}, {30, 40}}), + ResourceSegments({{10, 40}})); + EXPECT_EQ(ResourceSegments({{10, 30}, {30, 40}}), + ResourceSegments({{10, 40}})); + // Cycle 29 is resource free, so the interval is disjoint. + EXPECT_EQ(ResourceSegments({{10, 29}, {30, 40}}), + ResourceSegments({{10, 29}, {30, 40}})); +} + +TEST(ResourceSegments, merge_three) { + EXPECT_EQ(ResourceSegments({{10, 29}, {30, 40}, {71, 200}}), + ResourceSegments({{10, 29}, {30, 40}, {71, 200}})); + EXPECT_EQ(ResourceSegments({{10, 29}, {30, 40}, {41, 200}}), + ResourceSegments({{10, 29}, {30, 40}, {41, 200}})); + EXPECT_EQ(ResourceSegments({{10, 30}, {30, 40}, {40, 200}}), + ResourceSegments({{10, 200}})); + EXPECT_EQ(ResourceSegments({{10, 28}, {30, 71}, {71, 200}}), + ResourceSegments({{10, 28}, {30, 200}})); +} + +//////////////////////////////////////////////////////////////////////////////// +// Intersection +TEST(ResourceSegments, intersects) { + // no intersect + EXPECT_FALSE(ResourceSegments::intersects({0, 1}, {3, 4})); + EXPECT_FALSE(ResourceSegments::intersects({3, 4}, {0, 1})); + EXPECT_FALSE(ResourceSegments::intersects({0, 3}, {3, 4})); + EXPECT_FALSE(ResourceSegments::intersects({3, 4}, {0, 3})); + + // Share one boundary + EXPECT_TRUE(ResourceSegments::intersects({5, 6}, {5, 10})); + EXPECT_TRUE(ResourceSegments::intersects({5, 10}, {5, 6})); + + // full intersect + EXPECT_TRUE(ResourceSegments::intersects({1, 2}, {0, 3})); + EXPECT_TRUE(ResourceSegments::intersects({1, 2}, {0, 2})); + EXPECT_TRUE(ResourceSegments::intersects({0, 3}, {1, 2})); + EXPECT_TRUE(ResourceSegments::intersects({0, 2}, {1, 2})); + + // right intersect + EXPECT_TRUE(ResourceSegments::intersects({2, 4}, {0, 3})); + EXPECT_TRUE(ResourceSegments::intersects({0, 3}, {2, 4})); + + // left intersect + EXPECT_TRUE(ResourceSegments::intersects({2, 4}, {3, 5})); + EXPECT_TRUE(ResourceSegments::intersects({3, 5}, {2, 4})); +} + +//////////////////////////////////////////////////////////////////////////////// +// TOP-DOWN getFirstAvailableAt +TEST(ResourceSegments, getFirstAvailableAtFromTop_oneCycle) { + auto X = ResourceSegments({{2, 5}}); + // 0 1 2 3 4 5 6 7 + // Res X X X + // ...X... + EXPECT_EQ(X.getFirstAvailableAtFromTop(0, 0, 1), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromTop(1, 0, 1), 1U); + // Skip to five when hitting cycle 2 + EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 0, 1), 5U); +} + +TEST(ResourceSegments, getFirstAvailableAtFromTop_twoCycles) { + auto X = ResourceSegments({{4, 5}}); + // 0 1 2 3 4 5 6 7 + // Res X + // ...X X.... + EXPECT_EQ(X.getFirstAvailableAtFromTop(0, 0, 2), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromTop(1, 0, 2), 1U); + EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 0, 2), 2U); + // Skip to cycle 5 + EXPECT_EQ(X.getFirstAvailableAtFromTop(3, 0, 2), 5U); +} + +TEST(ResourceSegments, getFirstAvailableAtFromTop_twoCycles_Shifted) { + auto X = ResourceSegments({{4, 5}}); + // 0 1 2 3 4 5 6 7 + // Res X + // ...c X X... + EXPECT_EQ(X.getFirstAvailableAtFromTop(0, 1, 3), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromTop(1, 1, 3), 1U); + // Skip to cycle 4 + EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 1, 3), 4U); + // Stay con cycle 4 + // 0 1 2 3 4 5 6 7 + // Res X + // ...c X X... + EXPECT_EQ(X.getFirstAvailableAtFromTop(3, 1, 3), 4U); + // + EXPECT_EQ(X.getFirstAvailableAtFromTop(4, 1, 3), 4U); + EXPECT_EQ(X.getFirstAvailableAtFromTop(5, 1, 3), 5U); +} + +TEST(ResourceSegments, getFirstAvailableAtFromTop_twoCycles_Shifted_withGap) { + auto X = ResourceSegments({{4, 5}, {7, 9}}); + // 0 1 2 3 4 5 6 7 8 9 + // Res X X X + // c X X + EXPECT_EQ(X.getFirstAvailableAtFromTop(1, 1, 3), 1U); + // 0 1 2 3 4 5 6 7 8 9 + // Res X X X + // c X X --> moves to 4 + EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 1, 3), 4U); + // 0 1 2 3 4 5 6 7 8 9 + // Res X X X + // c X X --> moves to 4 + EXPECT_EQ(X.getFirstAvailableAtFromTop(3, 1, 3), 4U); + // 0 1 2 3 4 5 6 7 8 9 + // Res X X X + // c X X --> stays on 4 + EXPECT_EQ(X.getFirstAvailableAtFromTop(4, 1, 3), 4U); + // 0 1 2 3 4 5 6 7 8 9 + // Res X X X + // c X X --> skips to 8 + EXPECT_EQ(X.getFirstAvailableAtFromTop(5, 1, 3), 8U); +} + +TEST(ResourceSegments, getFirstAvailableAtFromTop_basic) { + auto X = ResourceSegments({{5, 10}, {30, 40}}); + + EXPECT_EQ(X.getFirstAvailableAtFromTop(0, 3, 4), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromTop(1, 3, 4), 1U); + EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 3, 4), 7U); + EXPECT_EQ(X.getFirstAvailableAtFromTop(3, 3, 4), 7U); + EXPECT_EQ(X.getFirstAvailableAtFromTop(4, 3, 4), 7U); + EXPECT_EQ(X.getFirstAvailableAtFromTop(5, 3, 4), 7U); + EXPECT_EQ(X.getFirstAvailableAtFromTop(6, 3, 4), 7U); + EXPECT_EQ(X.getFirstAvailableAtFromTop(7, 3, 4), 7U); + // Check the empty range between the two intervals of X. + EXPECT_EQ(X.getFirstAvailableAtFromTop(15, 3, 4), 15U); + // Overlap the second interval. + EXPECT_EQ(X.getFirstAvailableAtFromTop(28, 3, 4), 37U); +} + +TEST(ResourceSegments, getFirstAvailableAtFromTop_advanced) { + auto X = ResourceSegments({{3, 6}, {7, 9}, {11, 14}, {30, 33}}); + + EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 4, 5), 2U); + + EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 3, 4), 3U); + // Can schedule at 7U because the interval [14, 19[ does not + // overlap any of the intervals in X. + EXPECT_EQ(X.getFirstAvailableAtFromTop(1, 7, 12), 7U); +} + +//////////////////////////////////////////////////////////////////////////////// +// BOTTOM-UP getFirstAvailableAt +TEST(ResourceSegments, getFirstAvailableAtFromBottom) { + // Scheduling cycles move to the left... + // + // 41 40 39 ... 31 30 29 ... 21 20 19 ... 11 10 9 8 7 6 ... 1 0 + // Res X X X X X X X X + // X X X X X X + // Time (relative to instruction execution) 0 1 2 3 4 5 + auto X = ResourceSegments({{10, 20}, {30, 40}}); + // .. but time (instruction cycle) moves to the right. Therefore, it + // is always possible to llocate a resource to the right of 0 if 0 + // is not taken, because the right side of the scheduling cycles is + // empty. + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 1), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 9), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 10), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 20), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 21), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 22), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 29), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 30), 0U); +} + +TEST(ResourceSegments, getFirstAvailableAtFromBottom_01) { + auto X = ResourceSegments({{3, 7}}); + // 10 9 8 7 6 5 4 3 2 1 0 + // X X X X + // ...X... <- one cycle resource placement + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 1), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(1, 0, 1), 1U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(2, 0, 1), 2U); + // Skip to 7 + EXPECT_EQ(X.getFirstAvailableAtFromBottom(3, 0, 1), 7U); +} + +TEST(ResourceSegments, getFirstAvailableAtFromBottom_02) { + auto X = ResourceSegments({{3, 7}}); + // 10 9 8 7 6 5 4 3 2 1 0 + // X X X X + // ...X X... <- two cycles resource placement + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 2), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(1, 0, 2), 1U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(2, 0, 2), 2U); + // skip to 8 + EXPECT_EQ(X.getFirstAvailableAtFromBottom(3, 0, 2), 8U); +} + +TEST(ResourceSegments, getFirstAvailableAtFromBottom_02_shifted) { + auto X = ResourceSegments({{3, 7}}); + // 10 9 8 7 6 5 4 3 2 1 0 + // X X X X + // c X X <- two cycles resource placement but shifted by 1 + // 0 1 2 <- cycles relative to the execution of the + // instruction + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 1, 3), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(1, 1, 3), 1U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(2, 1, 3), 2U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(3, 1, 3), 3U); + // 10 9 8 7 6 5 4 3 2 1 0 + // X X X X + // c X X -> skip to 9 + // 0 1 2 + EXPECT_EQ(X.getFirstAvailableAtFromBottom(4, 1, 3), 9U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(5, 1, 3), 9U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(6, 1, 3), 9U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(7, 1, 3), 9U); + // 10 9 8 7 6 5 4 3 2 1 0 + // X X X X + // c X X <- skip to 9 + // 0 1 2 + EXPECT_EQ(X.getFirstAvailableAtFromBottom(8, 1, 3), 9U); + // 10 9 8 7 6 5 4 3 2 1 0 + // X X X X + // c X X + // 0 1 2 + EXPECT_EQ(X.getFirstAvailableAtFromBottom(9, 1, 3), 9U); + // 10 9 8 7 6 5 4 3 2 1 0 + // X X X X + // c X X + // 0 1 2 + EXPECT_EQ(X.getFirstAvailableAtFromBottom(10, 1, 3), 10U); +} + +TEST(ResourceSegments, getFirstAvailableAtFromBottom_03) { + auto X = ResourceSegments({{1, 2}, {3, 7}}); + // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 + // X X X X X + // X + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 1), 0U); + // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 + // X X X X X + // X + EXPECT_EQ(X.getFirstAvailableAtFromBottom(1, 0, 1), 2U); + // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 + // X X X X X + // X + EXPECT_EQ(X.getFirstAvailableAtFromBottom(2, 0, 1), 2U); + // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 + // X X X X X + // X X X X X + EXPECT_EQ(X.getFirstAvailableAtFromBottom(2, 0, 5), 11U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(3, 0, 5), 11U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(5, 0, 5), 11U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(11, 0, 5), 11U); + // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 + // X X X X X + // X X X X X + EXPECT_EQ(X.getFirstAvailableAtFromBottom(12, 0, 5), 12U); +} + +TEST(ResourceSegments, getFirstAvailableAtFromBottom_03_shifted) { + // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 + // X X X X X X X X + auto X = ResourceSegments({{-3, -1}, {1, 2}, {3, 7}, {9, 10}}); + + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 1, 2), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 2), 0U); + + // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 + // X X X X X X X X + // X X X -> skip to cycle 12 + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 3), 12U); + // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 + // X X X X X X X X + // X X + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 1, 3), 1U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 1, 4), 13U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(12, 1, 4), 13U); + // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 + // X X X X X X X X + // c X X X + EXPECT_EQ(X.getFirstAvailableAtFromBottom(13, 1, 4), 13U); + // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 + // X X X X X X X X + // X X + EXPECT_EQ(X.getFirstAvailableAtFromBottom(1, 1, 3), 1U); + // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 + // X X X X X X X X + // C X X 0 -> skip to cycle 9 + EXPECT_EQ(X.getFirstAvailableAtFromBottom(2, 1, 3), 9U); + // 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 + // X X X X X X X X + // C C X X X X X -> skip to cycle 16 + EXPECT_EQ(X.getFirstAvailableAtFromBottom(3, 2, 7), 16U); +} +TEST(ResourceSegments, getFirstAvailableAtFromBottom_empty) { + // Empty resource usage can accept schediling at any cycle + auto X = ResourceSegments({}); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 1), 0U); + EXPECT_EQ(X.getFirstAvailableAtFromBottom(17, 1, 22), 17U); +} Index: llvm/utils/TableGen/SubtargetEmitter.cpp =================================================================== --- llvm/utils/TableGen/SubtargetEmitter.cpp +++ llvm/utils/TableGen/SubtargetEmitter.cpp @@ -1448,6 +1448,12 @@ OS << " " << (CompleteModel ? "true" : "false") << ", // " << "CompleteModel\n"; + bool EnableIntervals = + (PM.ModelDef ? PM.ModelDef->getValueAsBit("EnableIntervals") : false); + + OS << " " << (EnableIntervals ? "true" : "false") << ", // " + << "EnableIntervals\n"; + OS << " " << PM.Index << ", // Processor ID\n"; if (PM.hasInstrSchedModel()) OS << " " << PM.ModelName << "ProcResources" << ",\n"