LLVM 20.0.0git
Public Types | Public Member Functions | Static Public Member Functions | Friends | List of all members
llvm::ResourceSegments Class Reference

ResourceSegments are a collection of intervals closed on the left and opened on the right: More...

#include "llvm/CodeGen/MachineScheduler.h"

Public Types

typedef std::pair< int64_t, int64_t > IntervalTy
 Represents an interval of discrete integer values closed on the left and open on the right: [a, b).
 

Public Member Functions

void add (IntervalTy A, const unsigned CutOff=10)
 Adds an interval [a, b) to the collection of the instance.
 
unsigned getFirstAvailableAtFromBottom (unsigned CurrCycle, unsigned AcquireAtCycle, unsigned ReleaseAtCycle) const
 getFirstAvailableAtFromBottom and getFirstAvailableAtFromTop should be merged in a single function in which a function that creates the NewInterval is passed as a parameter.
 
unsigned getFirstAvailableAtFromTop (unsigned CurrCycle, unsigned AcquireAtCycle, unsigned ReleaseAtCycle) const
 
 ResourceSegments ()
 
bool empty () const
 
 ResourceSegments (const std::list< IntervalTy > &Intervals)
 

Static Public Member Functions

static bool intersects (IntervalTy A, IntervalTy B)
 Checks whether intervals intersect.
 
static IntervalTy getResourceIntervalBottom (unsigned C, unsigned AcquireAtCycle, unsigned ReleaseAtCycle)
 These function return the interval used by a resource in bottom and top scheduling.
 
static IntervalTy getResourceIntervalTop (unsigned C, unsigned AcquireAtCycle, unsigned ReleaseAtCycle)
 

Friends

bool operator== (const ResourceSegments &c1, const ResourceSegments &c2)
 
llvm::raw_ostreamoperator<< (llvm::raw_ostream &os, const ResourceSegments &Segments)
 

Detailed Description

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 ResourceSegments instance represents the cycle reservation history of the instance of and individual resource.

Definition at line 627 of file MachineScheduler.h.

Member Typedef Documentation

◆ IntervalTy

typedef std::pair<int64_t, int64_t> llvm::ResourceSegments::IntervalTy

Represents an interval of discrete integer values closed on the left and open on the right: [a, b).

Definition at line 631 of file MachineScheduler.h.

Constructor & Destructor Documentation

◆ ResourceSegments() [1/2]

llvm::ResourceSegments::ResourceSegments ( )
inlineexplicit

Definition at line 808 of file MachineScheduler.h.

◆ ResourceSegments() [2/2]

llvm::ResourceSegments::ResourceSegments ( const std::list< IntervalTy > &  Intervals)
inlineexplicit

Definition at line 810 of file MachineScheduler.h.

Member Function Documentation

◆ add()

void ResourceSegments::add ( ResourceSegments::IntervalTy  A,
const unsigned  CutOff = 10 
)

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 ResourceSegments is attached only to an individual resource instance.

Definition at line 4495 of file MachineScheduler.cpp.

References A, llvm::all_of(), assert(), and intersects().

◆ empty()

bool llvm::ResourceSegments::empty ( ) const
inline

Definition at line 809 of file MachineScheduler.h.

◆ getFirstAvailableAtFromBottom()

unsigned llvm::ResourceSegments::getFirstAvailableAtFromBottom ( unsigned  CurrCycle,
unsigned  AcquireAtCycle,
unsigned  ReleaseAtCycle 
) const
inline

getFirstAvailableAtFromBottom and getFirstAvailableAtFromTop should be merged in a single function in which a function that creates the NewInterval is passed as a parameter.

Definition at line 784 of file MachineScheduler.h.

References getResourceIntervalBottom().

◆ getFirstAvailableAtFromTop()

unsigned llvm::ResourceSegments::getFirstAvailableAtFromTop ( unsigned  CurrCycle,
unsigned  AcquireAtCycle,
unsigned  ReleaseAtCycle 
) const
inline

Definition at line 790 of file MachineScheduler.h.

References getResourceIntervalTop().

◆ getResourceIntervalBottom()

static IntervalTy llvm::ResourceSegments::getResourceIntervalBottom ( unsigned  C,
unsigned  AcquireAtCycle,
unsigned  ReleaseAtCycle 
)
inlinestatic

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|AcquireAtCycle|ReleaseAtCycle| +-----—+----------—+-----------—+ | 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+AcquireAtCycle, C+ReleaseAtCycle)

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-ReleaseAtCycle+1, C-AcquireAtCycle+1)

NOTE: In both cases, the number of cycles booked by a resources is the value (ReleaseAtCycle - AcquireAtCycle).

Definition at line 717 of file MachineScheduler.h.

References llvm::CallingConv::C.

Referenced by llvm::SchedBoundary::bumpNode(), and getFirstAvailableAtFromBottom().

◆ getResourceIntervalTop()

static IntervalTy llvm::ResourceSegments::getResourceIntervalTop ( unsigned  C,
unsigned  AcquireAtCycle,
unsigned  ReleaseAtCycle 
)
inlinestatic

◆ intersects()

bool ResourceSegments::intersects ( ResourceSegments::IntervalTy  A,
ResourceSegments::IntervalTy  B 
)
static

Checks whether intervals intersect.

Definition at line 4522 of file MachineScheduler.cpp.

References A, assert(), and B.

Friends And Related Function Documentation

◆ operator<<

llvm::raw_ostream & operator<< ( llvm::raw_ostream os,
const ResourceSegments Segments 
)
friend

Definition at line 819 of file MachineScheduler.h.

◆ operator==

bool operator== ( const ResourceSegments c1,
const ResourceSegments c2 
)
friend

Definition at line 815 of file MachineScheduler.h.


The documentation for this class was generated from the following files: