An inclusive interval [a, b] where a and b are arbitrary integers not necessarily bound to a given field. More...

#include <IntervalAnalysis.h>

Public Member Functions
	UnreducedInterval (llvm::APSInt x, llvm::APSInt y)

	UnreducedInterval (llvm::APInt x, llvm::APInt y)

	UnreducedInterval (uint64_t x, uint64_t y)
	This constructor is primarily for convenience for unit tests.

Interval	reduce (const Field &field) const
	Reduce the interval to an interval in the given field.

UnreducedInterval	intersect (const UnreducedInterval &rhs) const
	Compute and return the intersection of this interval and the given RHS.

UnreducedInterval	doUnion (const UnreducedInterval &rhs) const
	Compute and return the union of this interval and the given RHS.

UnreducedInterval	computeLTPart (const UnreducedInterval &rhs) const
	Return the part of the interval that is guaranteed to be less than the rhs's max value.

UnreducedInterval	computeLEPart (const UnreducedInterval &rhs) const
	Return the part of the interval that is less than or equal to the rhs's upper bound.

UnreducedInterval	computeGTPart (const UnreducedInterval &rhs) const
	Return the part of the interval that is greater than the rhs's lower bound.

UnreducedInterval	computeGEPart (const UnreducedInterval &rhs) const
	Return the part of the interval that is greater than or equal to the rhs's lower bound.

UnreducedInterval	operator- () const

bool	overlaps (const UnreducedInterval &rhs) const

llvm::APSInt	getLHS () const

llvm::APSInt	getRHS () const

llvm::APSInt	width () const
	Compute the width of this interval within a given field `f`.

bool	isEmpty () const
	Returns true iff width() is zero.

bool	isNotEmpty () const

void	print (llvm::raw_ostream &os) const

Static Public Member Functions
static size_t	getMaxBitWidth (const UnreducedInterval &lhs, const UnreducedInterval &rhs)
	A utility method to determine the largest bitwidth among arms of two UnreducedIntervals.

Friends
UnreducedInterval	operator+ (const UnreducedInterval &lhs, const UnreducedInterval &rhs)

UnreducedInterval	operator- (const UnreducedInterval &lhs, const UnreducedInterval &rhs)

UnreducedInterval	operator* (const UnreducedInterval &lhs, const UnreducedInterval &rhs)

std::strong_ordering	operator<=> (const UnreducedInterval &lhs, const UnreducedInterval &rhs)

bool	operator== (const UnreducedInterval &lhs, const UnreducedInterval &rhs)

llvm::raw_ostream &	operator<< (llvm::raw_ostream &os, const UnreducedInterval &ui)

Detailed Description

An inclusive interval [a, b] where a and b are arbitrary integers not necessarily bound to a given field.

Definition at line 102 of file IntervalAnalysis.h.

Constructor & Destructor Documentation

◆ UnreducedInterval() [1/3]

llzk::UnreducedInterval::UnreducedInterval	(	llvm::APSInt	x,
		llvm::APSInt	y )

inline

Definition at line 117 of file IntervalAnalysis.h.

◆ UnreducedInterval() [2/3]

llzk::UnreducedInterval::UnreducedInterval	(	llvm::APInt	x,
		llvm::APInt	y )

inline

Definition at line 118 of file IntervalAnalysis.h.

◆ UnreducedInterval() [3/3]

llzk::UnreducedInterval::UnreducedInterval	(	uint64_t	x,
		uint64_t	y )

inline

This constructor is primarily for convenience for unit tests.

Definition at line 120 of file IntervalAnalysis.h.

Member Function Documentation

◆ computeGEPart()

UnreducedInterval llzk::UnreducedInterval::computeGEPart ( const UnreducedInterval & rhs ) const

Return the part of the interval that is greater than or equal to the rhs's lower bound.

For example, given *this = [0, 7] and rhs = [3, 5], this function would return [3, 7], since rhs has a minimum value of 3. If this interval's upper bound is less than the rhs's lower bound, the returned interval will be "empty" (an interval where a > b). For example, if *this = [0, 6] and rhs = [7, 10], then no part of *this is greater than or equal to rhs.

Definition at line 142 of file IntervalAnalysis.cpp.

◆ computeGTPart()

UnreducedInterval llzk::UnreducedInterval::computeGTPart ( const UnreducedInterval & rhs ) const

Return the part of the interval that is greater than the rhs's lower bound.

For example, given *this = [0, 7] and rhs = [3, 5], this function would return [4, 7], since rhs has a minimum value of 3. If this interval's upper bound is less than or equal to the rhs's lower bound, the returned interval will be "empty" (an interval where a > b). For example, if *this = [0, 7] and rhs = [7, 10], then no part of *this is greater than rhs.

Definition at line 133 of file IntervalAnalysis.cpp.

◆ computeLEPart()

UnreducedInterval llzk::UnreducedInterval::computeLEPart ( const UnreducedInterval & rhs ) const

Return the part of the interval that is less than or equal to the rhs's upper bound.

For example, given *this = [0, 7] and rhs = [3, 5], this function would return [0, 5], since rhs has a max value of 5. If this interval's lower bound is greater than to the rhs's upper bound, the returned interval will be "empty" (an interval where a > b). For example, if *this = [8, 10] and rhs = [0, 7], then no part of *this is less than or equal to rhs.

Definition at line 126 of file IntervalAnalysis.cpp.

◆ computeLTPart()

UnreducedInterval llzk::UnreducedInterval::computeLTPart ( const UnreducedInterval & rhs ) const

Return the part of the interval that is guaranteed to be less than the rhs's max value.

For example, given *this = [0, 7] and rhs = [3, 5], this function would return [0, 4], since rhs has a max value of 5. If this interval's lower bound is greater than or equal to the rhs's upper bound, the returned interval will be "empty" (an interval where a > b). For example, if *this = [7, 10] and rhs = [0, 7], then no part of *this is less than rhs.

Definition at line 117 of file IntervalAnalysis.cpp.

◆ doUnion()

UnreducedInterval llzk::UnreducedInterval::doUnion ( const UnreducedInterval & rhs ) const

Compute and return the union of this interval and the given RHS.

Parameters

rhs

Returns

Definition at line 112 of file IntervalAnalysis.cpp.

◆ getLHS()

llvm::APSInt llzk::UnreducedInterval::getLHS ( ) const

inline

Definition at line 196 of file IntervalAnalysis.h.

◆ getMaxBitWidth()

static size_t llzk::UnreducedInterval::getMaxBitWidth	(	const UnreducedInterval &	lhs,
		const UnreducedInterval &	rhs )

inlinestatic

A utility method to determine the largest bitwidth among arms of two UnreducedIntervals.

Useful for widening integers for comparisons between APInts. TODO: When we upgrade to LLVM 19/20, we can instead use DynamicAPInts to avoid the messy widening/narrowing logic.

Parameters

lhs
rhs

Returns

Definition at line 111 of file IntervalAnalysis.h.

◆ getRHS()

llvm::APSInt llzk::UnreducedInterval::getRHS ( ) const

inline

Definition at line 197 of file IntervalAnalysis.h.

◆ intersect()

UnreducedInterval llzk::UnreducedInterval::intersect ( const UnreducedInterval & rhs ) const

Compute and return the intersection of this interval and the given RHS.

Parameters

rhs

Returns

Definition at line 107 of file IntervalAnalysis.cpp.

◆ isEmpty()

bool llzk::UnreducedInterval::isEmpty ( ) const

Returns true iff width() is zero.

Definition at line 199 of file IntervalAnalysis.cpp.

◆ isNotEmpty()

bool llzk::UnreducedInterval::isNotEmpty ( ) const

inline

Definition at line 206 of file IntervalAnalysis.h.

◆ operator-()

UnreducedInterval llzk::UnreducedInterval::operator- ( ) const

Definition at line 149 of file IntervalAnalysis.cpp.

◆ overlaps()

bool llzk::UnreducedInterval::overlaps ( const UnreducedInterval & rhs ) const

Definition at line 172 of file IntervalAnalysis.cpp.

◆ print()

void llzk::UnreducedInterval::print ( llvm::raw_ostream & os ) const

inline

Definition at line 208 of file IntervalAnalysis.h.

◆ reduce()

Interval llzk::UnreducedInterval::reduce ( const Field & field ) const

Reduce the interval to an interval in the given field.

Parameters

field

Returns

Definition at line 75 of file IntervalAnalysis.cpp.

◆ width()

llvm::APSInt llzk::UnreducedInterval::width ( ) const

Compute the width of this interval within a given field f.

If a > b, returns 0. Otherwise, returns b - a + 1.

Since the range is inclusive, we add one to the difference to get the true width.

Definition at line 186 of file IntervalAnalysis.cpp.

Friends And Related Symbol Documentation

◆ operator*

UnreducedInterval operator*	(	const UnreducedInterval &	lhs,
		const UnreducedInterval &	rhs )

friend

Definition at line 160 of file IntervalAnalysis.cpp.

◆ operator+

UnreducedInterval operator+	(	const UnreducedInterval &	lhs,
		const UnreducedInterval &	rhs )

friend

Definition at line 151 of file IntervalAnalysis.cpp.

◆ operator-

UnreducedInterval operator-	(	const UnreducedInterval &	lhs,
		const UnreducedInterval &	rhs )

friend

Definition at line 156 of file IntervalAnalysis.cpp.

◆ operator<<

llvm::raw_ostream & operator<<	(	llvm::raw_ostream &	os,
		const UnreducedInterval &	ui )

friend

Definition at line 210 of file IntervalAnalysis.h.

◆ operator<=>

std::strong_ordering operator<=>	(	const UnreducedInterval &	lhs,
		const UnreducedInterval &	rhs )

friend

Definition at line 176 of file IntervalAnalysis.cpp.

◆ operator==

bool operator==	(	const UnreducedInterval &	lhs,
		const UnreducedInterval &	rhs )

friend

Definition at line 191 of file IntervalAnalysis.h.

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

include/llzk/Analysis/IntervalAnalysis.h
lib/Analysis/IntervalAnalysis.cpp

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

◆ UnreducedInterval() [1/3]

◆ UnreducedInterval() [2/3]

◆ UnreducedInterval() [3/3]

Member Function Documentation

◆ computeGEPart()

◆ computeGTPart()

◆ computeLEPart()

◆ computeLTPart()

◆ doUnion()

◆ getLHS()

◆ getMaxBitWidth()

◆ getRHS()

◆ intersect()

◆ isEmpty()

◆ isNotEmpty()

◆ operator-()

◆ overlaps()

◆ print()

◆ reduce()

◆ width()

Friends And Related Symbol Documentation

◆ operator*

◆ operator+

◆ operator-

◆ operator<<

◆ operator<=>

◆ operator==