[MISched] Introduce and use ResourceSegments.

[fpetrogalli]

Summary

The class ResourceSegments is used to keep track of the intervals
that represent resource usage of a collection of instruction that are
being scheduled by the machine scheduler.

The collection is made of intervals that are closed on the left and
open on the right (represented by the standard notation [a, b)).

These collection of intervals can be extended by adding new
intervals accordingly while scheduling a basic block.

Unit tests are added to verify the possible configurations of
intervals, and the relative possibility of scheduling a new
instruction in these configurations. Specifically, the methods
getFirstAvailableAtFromBottom and getFirstAvailableAtFromTop are
tested to make sure that both bottom-up and top-down scheduling work
when tracking resource usage across the basic block with
ResourceSegments.

Note that the scheduler tracks resource usage with two methods:

1. counters (via std::vector<unsigned> ReservedCycles;);

2. intervals (via std::map<unsigned, ResourceSegments> ReservedResourceSegments;).

This patch can be considered a NFC test for existing scheduling models
because the tracking system that uses intervals is turned off by
default (field bit EnableIntervals = false; in the tablegen class
SchedMachineModel).

[RKSimon]

llvm/include/llvm/CodeGen/MachineScheduler.h

97

#include "llvm/Support/raw_ostream.h" ?

933

Use assert(all_of(_Intervals))

1032

typedef std::pair<long, long> ? in fact we might be better off using a std::pair<int64_t,int64_t> ?

1094

Some of these larger implementations might be better off in MachineScheduler.cpp

1097

(style) avoid auto

1104

(style) assertion message

llvm/include/llvm/MC/MCSchedule.h

318

Include the description here as well - don't just refer to TargetSchedule.td

llvm/lib/CodeGen/MachineScheduler.cpp

167

Test coverage?

llvm/unittests/CodeGen/CMakeLists.txt

44

These are supposed to be kept sorted :(

[RKSimon]

Also - please add a summary to the patch

[fpetrogalli]

Address code review.

llvm/lib/CodeGen/MachineScheduler.cpp

167

The test would just let the command line option, because we do not have any SchedModel upstream that use StartAtCycle.

Are you saying that I should add an llc invocation that uses this command line option, independently whether or not I can test the codegen changes caused by the value change?

[fpetrogalli]

llvm/lib/CodeGen/MachineScheduler.cpp

167

FWIW, the behaviour of changing the cutoff value is tested in the unit test TEST(ResourceSegments, AddWithCutOff)

[fpetrogalli]

@RKSimon - thank you for looking into this!

[fpetrogalli]

The sort() and merge() operations were always invoked in pair, therefore I merged them together in the method mergeAndSort().

[fpetrogalli]

gentle ping

[andreadb]

Hi Francesco,

Apologies for the very late reply. I have been quite busy these days, and I am still trying to figure out mentally how well this new framework works in practice.

I am thinking about edge cases where writes of a same instruction somehow conflict in terms of resource cycles and/or StartAtCycle quantities.

If I understand it correctly, StartAtCycle forces the scheduling algorithm to find valid segments after that relative cycle. Scheduling won't fail if no segment can be allocated exactly at that cycle.
Basically, resource consumption is requested to start not before StartAtCycle. However, it is OK to start after StartAtCycle if slot allocation is unsuccessful.
Is that correct?

If so, then what happens if I declare the following write:

Write W = [ A (cycles=1, start_at=0), B (cycles=1, start_at=0), AB (cycles=3, start_at=1) ].

Where:
A and B are simple resource units (one unit each).
AB is a resource group containing A and B.

I want AB to be consumed after the first A and after the first B.

Ideally, I expect either this:

///       C      1      2      3      4      5  ...
/// ------|------|------|------|------|------|----->
/// 
/// A    [C,                       C+4)  -- includes the extra cycle from AB.
/// B    [C, C+1)

or

///       C      1      2      3      4      5  ...
/// ------|------|------|------|------|------|----->
/// 
/// A    [C, C+1)
/// B    [C,                       C+4)  -- includes the extra cycle from AB.

However, if resouce A is unavailable until cycle 2. Then what happens to the schedule?

///       C      1      2      3      4      5  ...
/// ------|------|------|------|------|------|----->
/// 
/// A     X      X      X        [C+3, C+4)
/// B    [C,  C+1)

At this point, when would AB be allocated? Could it be allocated to B from relative cycle 2?

I am asking this question because StartAtCycle could be used to describe unmodeled dependencies between multiple micro opcodes of a same instruction.
In that example, the user might have wanted to suggest that the consumption of group AB must start after A and B have been consumed for one cycle.

For example, an instruction may decode into 3 micro opcodes:

• opcode #1 consumes one cycle of resource A
• opcode #2 consumes one cycle of resource B
• opcode #3 waits for opcode #1 and #2 to complete, and then consumes three cycles of A or B.

If we use StartAtCycle, I am not sure if we can guarantee that consumption of "A or B" would always start at the right time.

NOTE: On x86, a similar pattern could be used to implement horizontal operations which are often microcoded and expanded into a pair of independent shuffle operations, followed by an ADD/SUB.

I wonder if there is a way to delay the start cycle until both A and B have been consumed.
Again, apologies if I misunderstood all of this behaviour.
In retrospect, I wonder whether we need something more than StartAtCycle to properly describe these dependencies. I fear that this won't be expressive enough otherwise.
I should have raised this concern on the other patch. However, I only ended up thinking about this potential issue now. Sorry.

I also wonder about what happens to those cases where a write triggers the consumption of extra cycles of so-called "super" resources. I suspect that "super" resources must be treated specially, and they should inherit the same StartAtCycle?

I have only suggested some minor changes (see my comments below).
I am curious to see how much scheduling improves if we start using StartAtCycle in our scheduling models. Do you have some perf numbers to share?

On x86 (SimonP can correct me on this) I believe that x86 still uses the old latency-based post-ra scheduling algorithm, which doesn't do any bookkeeping on hw resources.
I think that using StartAtCycle can significantly improve the quality of most x86 models (horizontal operations would benefit from it a lot). However, it would be nicer if it was possible to express a StartAfter resource consumption.

llvm/include/llvm/CodeGen/MachineScheduler.h

897–899

Can this be an inline lambda used by the std::is_sorted at line 868?

908

I'd be tempted to just move your new ResourceSegments struct outside of SchedBoundary. Not sure what other reviewers think about it.
I feel like it would be slightly more readable all this part.
It was also suggested by Simon before. You might have missed his comment before.
Basically, this struct is big enough to be promoted to top level (mainly for readability reasons).

909

Was this meant to be public? If so, then it is redundant.

llvm/lib/CodeGen/MachineScheduler.cpp

2264

You don't need else after return.

2652–2661

Not entirely sure about the coding style. However, I suggest to use braces for those blocks because statements are particularly long and use four lines...

4216

Don't need to check NDEBUG

[fpetrogalli]

Thank you for the feedback @andreadb

I need some time to digest it to be able to give you an answer. I have however inlined a clarification of how I have interpreted StartAtCycle and ResourceCycle. (I'd be of course happy to revisit my interpretation if it makes things more clear)

In D150312#4371743, @andreadb wrote:

Hi Francesco,

Apologies for the very late reply. I have been quite busy these days, and I am still trying to figure out mentally how well this new framework works in practice.

I am thinking about edge cases where writes of a same instruction somehow conflict in terms of resource cycles and/or StartAtCycle quantities.

If I understand it correctly, StartAtCycle forces the scheduling algorithm to find valid segments after that relative cycle. Scheduling won't fail if no segment can be allocated exactly at that cycle.
Basically, resource consumption is requested to start not before StartAtCycle. However, it is OK to start after StartAtCycle if slot allocation is unsuccessful.
Is that correct?

If so, then what happens if I declare the following write:

Write W = [ A (cycles=1, start_at=0), B (cycles=1, start_at=0), AB (cycles=3, start_at=1) ].

I do not have an answer (yet!) on the question following this set up, however I wanted to clarify that the way I have intended StartAtCycle and ResourceCycle in the tablegen description is as follows.

For a resource RES used in a WriteRes, that is used for 3 cycles starting at cycle 2, the tablegen description I expect to use is the following:

def : WriteRes<..., [RES]> {
  let ResourceCycles = [5];
  let StartAtCycle = [2];
}

This mens that the total number of cycle for resource RES is given by the difference between the corresponding values in ResourceCycles and StartAtCycle respectively, which results in 5 - 2 = 3.

The reason for this choice is the following. In the current code resource usage is always considered booked from 0 (resulting in overbooking). For example, given ResourceCycle = [1,3] for resources A, B, I assumed the meaning being A for 1 cycle, followed by B for 2 cycles (cycle 0, overlapping the use of A , is overbooked for B).

cycle 0 | 1 | 2 | 3 | 4 | 5
A     X
B     X   X   X

I decided to reinterpret the ResourceCycles as "ReleaseAtCyc;e" because I did not want to mess with the values of the current scheduling models in case people wanted to optimise the existing one with similar situation by just adding StartAtCycle = [0,1], without the need of changing any of the values in resourceCycles. By setting StartAtCYcle = [1,2] for the example, we would get the real resource usage without having to change ResourceCYcle from [1,3] to [1,2]:

cycle 0 | 1 | 2 | 3 | 4 | 5
A     X
B         X   X

Essentially to me resource usage is from StartAtCycle to resourceCycles , while I *think* that you intend resource being booked from StartAtCycle to StartAtCycle + ResourceCycles.

If we proceed with my interpretation, I think it will be easier to mass rename ResourceCycles to ReleaseAtCycle, instead of having to manually figure out the math that is needed to optimise the existing scheduling models.

Of course, this is my person preference, and I am totally fine in changing the code to your interpretation.

Having said that, I'll take a look into the issue you are reporting. It would really help if you could point me at some scheduling models in the sources that use the resource groups mechanism you describe, because I could use it as a starting point to play with it and see what happens.

Thanks!

[andreadb]

In D150312#4375654, @fpetrogalli wrote:

Thank you for the feedback @andreadb

I need some time to digest it to be able to give you an answer. I have however inlined a clarification of how I have interpreted StartAtCycle and ResourceCycle. (I'd be of course happy to revisit my interpretation if it makes things more clear)

In D150312#4371743, @andreadb wrote:

Hi Francesco,

Apologies for the very late reply. I have been quite busy these days, and I am still trying to figure out mentally how well this new framework works in practice.

I am thinking about edge cases where writes of a same instruction somehow conflict in terms of resource cycles and/or StartAtCycle quantities.

If I understand it correctly, StartAtCycle forces the scheduling algorithm to find valid segments after that relative cycle. Scheduling won't fail if no segment can be allocated exactly at that cycle.
Basically, resource consumption is requested to start not before StartAtCycle. However, it is OK to start after StartAtCycle if slot allocation is unsuccessful.
Is that correct?

If so, then what happens if I declare the following write:

Write W = [ A (cycles=1, start_at=0), B (cycles=1, start_at=0), AB (cycles=3, start_at=1) ].

I do not have an answer (yet!) on the question following this set up, however I wanted to clarify that the way I have intended StartAtCycle and ResourceCycle in the tablegen description is as follows.

For a resource RES used in a WriteRes, that is used for 3 cycles starting at cycle 2, the tablegen description I expect to use is the following:

def : WriteRes<..., [RES]> {
  let ResourceCycles = [5];
  let StartAtCycle = [2];
}

This mens that the total number of cycle for resource RES is given by the difference between the corresponding values in ResourceCycles and StartAtCycle respectively, which results in 5 - 2 = 3.

The reason for this choice is the following. In the current code resource usage is always considered booked from 0 (resulting in overbooking). For example, given ResourceCycle = [1,3] for resources A, B, I assumed the meaning being A for 1 cycle, followed by B for 2 cycles (cycle 0, overlapping the use of A , is overbooked for B).

cycle 0 | 1 | 2 | 3 | 4 | 5
A     X
B     X   X   X

I decided to reinterpret the ResourceCycles as "ReleaseAtCyc;e" because I did not want to mess with the values of the current scheduling models in case people wanted to optimise the existing one with similar situation by just adding StartAtCycle = [0,1], without the need of changing any of the values in resourceCycles. By setting StartAtCYcle = [1,2] for the example, we would get the real resource usage without having to change ResourceCYcle from [1,3] to [1,2].

Thanks, that makes sense.

For most devs, ResourceCycles is just a measure of latency; it declares for how many cycles a resource becomes unavailable after "instruction issue".
To avoid confusion, I suggest to add a code comment that further emphasizes how ResourceCycle actually means StopAtCycle. Otherwise, some people may wrongly assume that ResourceCycles is relative to StartAtCycle.

cycle 0 | 1 | 2 | 3 | 4 | 5
A     X
B         X   X

Essentially to me resource usage is from StartAtCycle to resourceCycles , while I *think* that you intend resource being booked from StartAtCycle to StartAtCycle + ResourceCycles.

If we proceed with my interpretation, I think it will be easier to mass rename ResourceCycles to ReleaseAtCycle, instead of having to manually figure out the math that is needed to optimise the existing scheduling models.

Of course, this is my person preference, and I am totally fine in changing the code to your interpretation.

I was essentially asking whether instruction issue still works the same way or not.

Is it required that ALL resource segments are reserved/allocated at issue cycle?
To put it in another way: Is the StartAtCycle a hard requirement for resource allocation? Would it prevent instruction issue if some but not all resources are available at their StartAtCycle?

Example:

A write W declaring the following:
 - 3 micro-opcodes
 - Resource consumption :
     A - 1cy
     B - 1cy
     C - 2cy   -- StartAtCycle=1

Given the following scenario:

cycle 0 | 1 | 2 | 3 |
A     -
B     -  
C     X   X

In this scenario, not all resources are available at their relative StartAtCycle. In particular, resource C cannot be allocated at relative cycle 1. If we interpret StartAtCycle as a hard constraint, then instruction issue will have to stall for one cycle.
C is busy for two more cycles, so issue of write W must be delayed for 1 extra cycle (even though A and B are already available).

The reason why I am asking these questions is because I want to fully understand how flexible is this new model in practice. In future, it would be nice if we could model resource consumption on a per-micro-opcode basis.

As you know, writes may declare multiple "micro-opcodes". However, there is no way currently to describe which micro-opcodes consume which hardware resources.
For that reason, scheduling algorithms don't track the lifetime of individual micro-opcodes; instead, instructions are essentially treated like atomic entities.
So, "issue event" - as a concept - can only apply to instructions as a whole and not individual micro-opcodes.

This obviously would have complicated the model, and it would have required per-micro-opcode knowledge which we don't have at the moment.
So, this is not feasible now, but it could be a future development (although unlikely).

I was wondering whether your StartAtCycle could have simplified that future development or not. I think your design is completely orthogonal, and it shouldn't prevent any further development in the area of modelling micro-opcode scheduling.

So, overall I think that your StartAtCycle is a nice and useful addition.

Having said that, I'll take a look into the issue you are reporting. It would really help if you could point me at some scheduling models in the sources that use the resource groups mechanism you describe, because I could use it as a starting point to play with it and see what happens.

Thanks!

Have a look at the Haswell model on x86.

defm : HWWriteResPair<WriteFHAdd,   [HWPort1, HWPort5], 5, [1,2], 3, 6>;

It describes the latency/throughput profile of an horizontal add.
An horizontal add is composed of 3 micro-opcodes:

• 2 shuffles (can only execute on HWPort5).
• 1 ADD (can only execute on HWPort1).

Shuffle opcodes are independent from each-other and can start execution immediately. The ADD opcode will have to wait for the shuffles to complete. The ADD could be marked as StartAtCycle=2.
HWPort5 is a bottleneck for shuffle opcodes; the 2 shuffle micro-opcodes must be serialised. That explains why it has a resource consumption of 2cy.

I am sure that there are several other (bad and good) examples in that file which also involve group resources.
On AMD platforms, shuffle opcodes can be issued to multiple pipes, so that bottleneck would not exist. For those models, the tablegen definition would be similar except that it would use a resource group instead of a unit for the two shuffles.

-Andrea

[fpetrogalli]

In D150312#4380570, @andreadb wrote:

[...]
I was essentially asking whether instruction issue still works the same way or not.

Yes, indeed, it works the same as before - it issues an instruction only if all the resources used by the instruction are available.

Is it required that ALL resource segments are reserved/allocated at issue cycle?

Yep - no changes w.r.t. the requirements for issuing.

I will update the patch according to the comments inline.

[fpetrogalli]

In D150312#4337840, @RKSimon wrote:

Also - please add a summary to the patch

Done

llvm/include/llvm/CodeGen/MachineScheduler.h

897–899

Done, if not for the fact that I have moved the static method in MachineScheduler.cpp because I need it in two places (one of which is an assertion).

[andreadb]

Thanks,

I don't have any other questions about this patch. It looks good to me.

[fpetrogalli]

Address comments from @andreadb and @RKSimon.

Thank you both!

[fpetrogalli]

@RKSimon - any other concerns?

Thanks,

Francesco

[sylvestre.ledru]

This patch doesn't build on some OS:
https://github.com/llvm/llvm-project/issues/63225

llvm/include/llvm/CodeGen/MachineScheduler.h

 #include "llvm/CodeGen/ScheduleDAG.h"
 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
 #include "llvm/CodeGen/ScheduleDAGMutation.h"
 #include "llvm/CodeGen/TargetSchedule.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <algorithm>
 #include <cassert>
+#include <llvm/Support/raw_ostream.h>
 #include <memory>
 #include <string>
 #include <vector>
 
 namespace llvm {
 
 extern cl::opt<bool> ForceTopDown;
 extern cl::opt<bool> ForceBottomUp;
 extern cl::opt<bool> VerifyScheduling;
 #ifndef NDEBUG
void reset() {
     RemIssueCount = 0;
     IsAcyclicLatencyLimited = false;
     RemainingCounts.clear();
   }
 
   void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel);
 };
 
+/// 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.
+class ResourceSegments {
+public:
+  /// Represents an interval of discrete integer values closed on
+  /// the left and open on the right: [a, b).
+  typedef std::pair<int64_t, int64_t> IntervalTy;
+
+  /// 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(IntervalTy A, const unsigned CutOff = 10);
+
+public:
+  /// Checks whether intervals intersect.
+  static bool intersects(IntervalTy A, IntervalTy B);
+
+  /// 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)
+  ///
+  ///
+  /// NOTE: In both cases, the number of cycles booked by a
+  /// resources is the value (Cycle - StartAtCycles).
+  static IntervalTy getResourceIntervalBottom(unsigned C, unsigned StartAtCycle,
+                                              unsigned Cycle) {
+    return std::make_pair<long, long>((long)C - (long)Cycle + 1L,
+                                      (long)C - (long)StartAtCycle + 1L);
+  }
+  static IntervalTy getResourceIntervalTop(unsigned C, unsigned StartAtCycle,
+                                           unsigned Cycle) {
+    return std::make_pair<long, long>((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<IntervalTy(unsigned, unsigned, unsigned)>
+                          IntervalBuilder) const;
+
+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);
+  }
+
+private:
+  std::list<IntervalTy> _Intervals;
+  /// Merge all adjacent intervals in the collection. For all pairs
+  /// of adjacient intervals, it performs [a, b) + [b, c) -> [a, c).
+  ///
+  /// Before performing the merge operation, the intervals are
+  /// sorted with \ref sort_predicate.
+  void sortAndMerge();
+
+public:
+  // constructor for empty set
+  explicit ResourceSegments(){};
+  bool empty() const { return _Intervals.empty(); }
+  explicit ResourceSegments(std::list<IntervalTy> Intervals)
+      : _Intervals(Intervals) {
+    sortAndMerge();
+  }
+
+  friend bool operator==(const ResourceSegments &c1,
+                         const ResourceSegments &c2) {
+    return c1._Intervals == c2._Intervals;
+  }
+#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
+};
+
 /// Each Scheduling boundary is associated with ready queues. It tracks the
 /// current cycle in the direction of movement, and maintains the state
 /// of "hazards" and other interlocks at the current cycle.
 class SchedBoundary {
 public:
   /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
   enum {
     TopQID = 1,
private:
   unsigned MaxExecutedResCount;
 
   // Cache the critical resources ID in this scheduled zone.
   unsigned ZoneCritResIdx;
 
   // 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<unsigned, 16> ReservedCycles;
-
-  /// For each PIdx, stores first index into ReservedCycles that corresponds to
-  /// it.
+public:
+private:
+  /// Record how resources have been allocated across the cycles of
+  /// the execution.
+  std::map<unsigned, ResourceSegments> ReservedResourceSegments;
+  std::vector<unsigned> ReservedCycles;
+  /// For each PIdx, stores first index into ReservedResourceSegments that
+  /// corresponds to it.
   ///
   /// For example, consider the following 3 resources (ResourceCount =
   /// 3):
   ///
   ///   +------------+--------+
   ///   |ResourceName|NumUnits|
   ///   +------------+--------+
   ///   |     X      |    2   |
   ///   +------------+--------+
   ///   |     Y      |    3   |
   ///   +------------+--------+
   ///   |     Z      |    1   |
   ///   +------------+--------+
   ///
   /// 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
   /// ReservedCyclesIndex[2] = 5;                     Z
   SmallVector<unsigned, 16> ReservedCyclesIndex;
 
   // For each PIdx, stores the resource group IDs of its subunits
   SmallVector<APInt, 16> ResourceGroupSubUnitMasks;
 
 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
   // Remember the greatest possible stall as an upper bound on the number of
   // times we should retry the pending queue because of a hazard.
   unsigned MaxObservedStall;
 #endif
 
 public:
public:
   // Is the scheduled region resource limited vs. latency limited.
   bool isResourceLimited() const { return IsResourceLimited; }
 
   /// Get the difference between the given SUnit's ready time and the current
   /// cycle.
   unsigned getLatencyStallCycles(SUnit *SU);
 
   unsigned getNextResourceCycleByInstance(unsigned InstanceIndex,
-                                          unsigned Cycles);
+                                          unsigned Cycles,
+                                          unsigned StartAtCycle);
 
   std::pair<unsigned, unsigned> getNextResourceCycle(const MCSchedClassDesc *SC,
                                                      unsigned PIdx,
-                                                     unsigned Cycles);
+                                                     unsigned Cycles,
+                                                     unsigned StartAtCycle);
 
   bool isUnbufferedGroup(unsigned PIdx) const {
     return SchedModel->getProcResource(PIdx)->SubUnitsIdxBegin &&
            !SchedModel->getProcResource(PIdx)->BufferSize;
   }
 
   bool checkHazard(SUnit *SU);
 
   unsigned findMaxLatency(ArrayRef<SUnit*> ReadySUs);
 
   unsigned getOtherResourceCount(unsigned &OtherCritIdx);
 
   /// Release SU to make it ready. If it's not in hazard, remove it from
   /// pending queue (if already in) and push into available queue.
   /// Otherwise, push the SU into pending queue.
   ///
   /// @param SU The unit to be released.
   /// @param ReadyCycle Until which cycle the unit is ready.
   /// @param InPQueue Whether SU is already in pending queue.
   /// @param Idx Position offset in pending queue (if in it).
   void releaseNode(SUnit *SU, unsigned ReadyCycle, bool InPQueue,
                    unsigned Idx = 0);
 
   void bumpCycle(unsigned NextCycle);
 
   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);
 
   void releasePending();
 
   void removeReady(SUnit *SU);
 
   /// Call this before applying any other heuristics to the Available queue.
struct CandPolicy {
 
     CandPolicy() = default;
 
     bool operator==(const CandPolicy &RHS) const {
       return ReduceLatency == RHS.ReduceLatency &&
              ReduceResIdx == RHS.ReduceResIdx &&
              DemandResIdx == RHS.DemandResIdx;
     }
     bool operator!=(const CandPolicy &RHS) const {
       return !(*this == RHS);
     }
   };
 
   /// Status of an instruction's critical resource consumption.
   struct SchedResourceDelta {
     // Count critical resources in the scheduled region required by SU.
     unsigned CritResources = 0;
 
     // Count critical resources from another region consumed by SU.
     unsigned DemandedResources = 0;
 
     SchedResourceDelta() = default;
 
     bool operator==(const SchedResourceDelta &RHS) const {
       return CritResources == RHS.CritResources
         && DemandedResources == RHS.DemandedResources;
     }

llvm/include/llvm/CodeGen/TargetSchedule.h

const InstrItineraryData *getInstrItineraries() const {
     return nullptr;
   }
 
   /// Return true if this machine model includes an instruction-level
   /// scheduling model or cycle-to-cycle itinerary data.
   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(); }
 
   /// Maximum number of micro-ops that may be scheduled per cycle.
   unsigned getIssueWidth() const { return SchedModel.IssueWidth; }
 
   /// Return true if new group must begin.
   bool mustBeginGroup(const MachineInstr *MI,

llvm/include/llvm/MC/MCSchedule.h

struct MCProcResourceDesc {
   const unsigned *SubUnitsIdxBegin;
 
   bool operator==(const MCProcResourceDesc &Other) const {
     return NumUnits == Other.NumUnits && SuperIdx == Other.SuperIdx
       && BufferSize == Other.BufferSize;
   }
 };
 
-/// Identify one of the processor resource kinds consumed by a particular
-/// scheduling class for the specified number of cycles.
+/// Identify one of the processor resource kinds consumed by a
+/// particular scheduling class for the specified number of cycles.
+/// TODO: consider renaming the field `StartAtCycle` and `Cycles` to
+/// `AcquireAtCycle` and `ReleaseAtCycle` respectively, to stress the
+/// fact that resource allocation is now represented as an interval,
+/// relatively to the issue cycle of the instruction.
 struct MCWriteProcResEntry {
   uint16_t ProcResourceIdx;
+  /// Cycle at which the resource will be released by an instruction,
+  /// relatively to the cycle in which the instruction is issued
+  /// (assuming no stalls inbetween).
   uint16_t Cycles;
   /// Cycle at which the resource will be grabbed by an instruction,
   /// relatively to the cycle in which the instruction is issued
   /// (assuming no stalls inbetween).
   uint16_t StartAtCycle;
 
   bool operator==(const MCWriteProcResEntry &Other) const {
     return ProcResourceIdx == Other.ProcResourceIdx && Cycles == Other.Cycles &&
struct MCSchedModel {
   // takes to recover from a branch misprediction.
   unsigned MispredictPenalty;
   static const unsigned DefaultMispredictPenalty = 10;
 
   bool PostRAScheduler; // default value is false
 
   bool CompleteModel;
 
+  // Tells the MachineScheduler whether or not to track resource usage
+  // using intervals via ResourceSegments (see
+  // llvm/include/llvm/CodeGen/MachineScheduler.h).
+  bool EnableIntervals;
+
   unsigned ProcID;
   const MCProcResourceDesc *ProcResourceTable;
   const MCSchedClassDesc *SchedClassTable;
   unsigned NumProcResourceKinds;
   unsigned NumSchedClasses;
   // Instruction itinerary tables used by InstrItineraryData.
   friend class InstrItineraryData;
   const InstrItinerary *InstrItineraries;

llvm/include/llvm/Target/TargetSchedule.td

class SchedMachineModel {
   // let<Predicate> UnsupportedFeatures = [HaveA,..,HaveY];
   //
   // to skip the checks for scheduling information when building LLVM for
   // instructions which have any of the listed predicates in their Predicates
   // field.
   list<Predicate> 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 {
   let NoModel = true;
   let CompleteModel = false;
 }
 
 // Define a kind of processor resource that may be common across

llvm/lib/CodeGen/MachineScheduler.cpp

HeaderColWidth("misched-dump-schedule-trace-col-header-width", cl::Hidden,
                             "the resources and schedule units"),
                    cl::init(19));
 static cl::opt<unsigned>
     ColWidth("misched-dump-schedule-trace-col-width", cl::Hidden,
              cl::desc("Set width of the columns showing resource booking."),
              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;
 
 // Pin the vtables to this file.
 void MachineSchedStrategy::anchor() {}
 
 void ScheduleDAGMutation::anchor() {}
 
void SchedBoundary::reset() {
   MinReadyCycle = std::numeric_limits<unsigned>::max();
   ExpectedLatency = 0;
   DependentLatency = 0;
   RetiredMOps = 0;
   MaxExecutedResCount = 0;
   ZoneCritResIdx = 0;
   IsResourceLimited = false;
   ReservedCycles.clear();
+  ReservedResourceSegments.clear();
   ReservedCyclesIndex.clear();
   ResourceGroupSubUnitMasks.clear();
 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
   // Track the maximum number of stall cycles that could arise either from the
   // latency of a DAG edge or the number of cycles that a processor resource is
   // reserved (SchedBoundary::ReservedCycles).
   MaxObservedStall = 0;
 #endif
for (SUnit &SU : DAG->SUnits) {
     const MCSchedClassDesc *SC = DAG->getSchedClass(&SU);
     RemIssueCount += SchedModel->getNumMicroOps(SU.getInstr(), SC)
       * SchedModel->getMicroOpFactor();
     for (TargetSchedModel::ProcResIter
            PI = SchedModel->getWriteProcResBegin(SC),
            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));
     }
   }
 }
 
 void SchedBoundary::
 init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem) {
   reset();
   DAG = dag;
unsigned SchedBoundary::getLatencyStallCycles(SUnit *SU) {
   if (ReadyCycle > CurrCycle)
     return ReadyCycle - CurrCycle;
   return 0;
 }
 
 /// 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)
     return 0;
   // For bottom-up scheduling add the cycles needed for the current operation.
   if (!isTop())
     NextUnreserved += Cycles;
   return NextUnreserved;
 }
 
 /// Compute the next cycle at which the given processor resource can be
 /// scheduled.  Returns the next cycle and the index of the processor resource
 /// 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;
   unsigned StartIndex = ReservedCyclesIndex[PIdx];
   unsigned NumberOfInstances = SchedModel->getProcResource(PIdx)->NumUnits;
   assert(NumberOfInstances > 0 &&
          "Cannot have zero instances of a ProcResource");
 
for (const MCWriteProcResEntry &PE :
                     SchedModel->getWriteProcResEnd(SC)))
       if (ResourceGroupSubUnitMasks[PIdx][PE.ProcResourceIdx])
         return std::make_pair(0u, StartIndex);
 
     auto SubUnits = SchedModel->getProcResource(PIdx)->SubUnitsIdxBegin;
     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;
       }
     }
     return std::make_pair(MinNextUnreserved, InstanceIdx);
   }
 
   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;
     }
   }
   return std::make_pair(MinNextUnreserved, InstanceIdx);
 }
 
bool SchedBoundary::checkHazard(SUnit *SU) {
 
   if (SchedModel->hasInstrSchedModel() && SU->hasReservedResource) {
     const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
     for (const MCWriteProcResEntry &PE :
           make_range(SchedModel->getWriteProcResBegin(SC),
                      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);
 #endif
         LLVM_DEBUG(dbgs() << "  SU(" << SU->NodeNum << ") "
                           << SchedModel->getResourceName(ResIdx)
                           << '[' << InstanceIdx - ReservedCyclesIndex[ResIdx]  << ']'
                           << "=" << NRCycle << "c\n");

 /// Add the given processor resource to this scheduled zone.
 ///
 /// \param Cycles indicates the number of consecutive (non-pipelined) cycles
 /// during which this resource is consumed.
 ///
 /// \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");
 
   // Update Executed resources counts.
   incExecutedResources(PIdx, Count);
   assert(Rem->RemainingCounts[PIdx] >= Count && "resource double counted");
   Rem->RemainingCounts[PIdx] -= Count;
 
   // Check if this resource exceeds the current critical resource. If so, it
   // becomes the critical resource.
   if (ZoneCritResIdx != PIdx && (getResourceCount(PIdx) > getCriticalCount())) {
     ZoneCritResIdx = PIdx;
     LLVM_DEBUG(dbgs() << "  *** Critical resource "
                       << SchedModel->getResourceName(PIdx) << ": "
                       << getResourceCount(PIdx) / SchedModel->getLatencyFactor()
                       << "c\n");
   }
   // 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)
                       << '[' << InstanceIdx - ReservedCyclesIndex[PIdx]  << ']'
                       << " reserved until @" << NextAvailable << "\n");
   }
   return NextAvailable;
 }
if (ZoneCritResIdx) {
         LLVM_DEBUG(dbgs() << "  *** Critical resource NumMicroOps: "
                           << ScaledMOps / SchedModel->getLatencyFactor()
                           << "c\n");
       }
     }
     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;
     }
     if (SU->hasReservedResource) {
       // For reserved resources, record the highest cycle using the resource.
       // For top-down scheduling, this is the cycle in which we schedule this
       // instruction plus the number of cycles the operations reserves the
       // resource. For bottom-up is it simply the instruction's cycle.
       for (TargetSchedModel::ProcResIter
              PI = SchedModel->getWriteProcResBegin(SC),
              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);
+                getNextResourceCycle(SC, PIdx, 0, PI->StartAtCycle);
             if (isTop()) {
               ReservedCycles[InstanceIdx] =
                   std::max(ReservedUntil, NextCycle + PI->Cycles);
             } else
               ReservedCycles[InstanceIdx] = NextCycle;
           }
         }
       }
     }
+  }
   // Update ExpectedLatency and DependentLatency.
   unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency;
   unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency;
   if (SU->getDepth() > TopLatency) {
     TopLatency = SU->getDepth();
     LLVM_DEBUG(dbgs() << "  " << Available.getName() << " TopLatency SU("
                       << SU->NodeNum << ") " << TopLatency << "c\n");
   }
LLVM_DUMP_METHOD void SchedBoundary::dumpReservedCycles() const {
 
   unsigned ResourceCount = SchedModel->getNumProcResourceKinds();
   unsigned StartIdx = 0;
 
   for (unsigned ResIdx = 0; ResIdx < ResourceCount; ++ResIdx) {
     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;
   }
 }
 
 // This is useful information to dump after bumpNode.
 // Note that the Queue contents are more useful before pickNodeFromQueue.
 LLVM_DUMP_METHOD void SchedBoundary::dumpScheduledState() const {
errs() << "ScheduleDAGMI::viewGraph is only available in debug builds on "
          << "systems with Graphviz or gv!\n";
 #endif  // NDEBUG
 }
 
 /// Out-of-line implementation with no arguments is handy for gdb.
 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;
+    }
+  }
+}

llvm/lib/MC/MCSchedule.cpp

 const MCSchedModel MCSchedModel::Default = {DefaultIssueWidth,
                                             DefaultMicroOpBufferSize,
                                             DefaultLoopMicroOpBufferSize,
                                             DefaultLoadLatency,
                                             DefaultHighLatency,
                                             DefaultMispredictPenalty,
                                             false,
                                             true,
+                                            false /*EnableIntervals*/,
                                             0,
                                             nullptr,
                                             nullptr,
                                             0,
                                             0,
                                             nullptr,
                                             nullptr};
 

llvm/unittests/CodeGen/CMakeLists.txt

add_llvm_unittest(CodeGenTests
   LexicalScopesTest.cpp
   MachineBasicBlockTest.cpp
   MachineInstrBundleIteratorTest.cpp
   MachineInstrTest.cpp
   MachineOperandTest.cpp
   RegAllocScoreTest.cpp
   PassManagerTest.cpp
   ScalableVectorMVTsTest.cpp
+  SchedBoundary.cpp
   SelectionDAGAddressAnalysisTest.cpp
   TypeTraitsTest.cpp
   TargetOptionsTest.cpp
   TestAsmPrinter.cpp
   MLRegallocDevelopmentFeatures.cpp
   )
 
 add_subdirectory(GlobalISel)
 
 target_link_libraries(CodeGenTests PRIVATE LLVMTestingSupport)

llvm/unittests/CodeGen/SchedBoundary.cpp

+#include "llvm/CodeGen/MachineScheduler.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+#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);
+}

llvm/utils/TableGen/SubtargetEmitter.cpp

OS << "  " << (PostRAScheduler ? "true" : "false")  << ", // "
        << "PostRAScheduler\n";
 
     bool CompleteModel =
       (PM.ModelDef ? PM.ModelDef->getValueAsBit("CompleteModel") : false);
 
     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"
          << "  " << PM.ModelName << "SchedClasses" << ",\n"
          << "  " << PM.ProcResourceDefs.size()+1 << ",\n"
          << "  " << (SchedModels.schedClassEnd()
                      - SchedModels.schedClassBegin()) << ",\n";
     else