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 (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_ostream &	operator<< (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:

The list is ordered: a_i < b_i and b_i < a_(i+1)
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 ( 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 4478 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

Definition at line 722 of file MachineScheduler.h.

References llvm::CallingConv::C.

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

◆ intersects()

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

static

Checks whether intervals intersect.

Definition at line 4505 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:

include/llvm/CodeGen/MachineScheduler.h
lib/CodeGen/MachineScheduler.cpp

Public Types

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ IntervalTy

Constructor & Destructor Documentation

◆ ResourceSegments() [1/2]

◆ ResourceSegments() [2/2]

Member Function Documentation

◆ add()

◆ empty()

◆ getFirstAvailableAtFromBottom()

◆ getFirstAvailableAtFromTop()

◆ getResourceIntervalBottom()

TOP DOWN SCHEDULING

BOTTOM UP SCHEDULING

◆ getResourceIntervalTop()

◆ intersects()

Friends And Related Function Documentation

◆ operator<<

◆ operator==