Intervals over a finite field. More...

#include <Intervals.h>

Classes
struct	Hash

Public Types
enum class	Type { TypeA = 0 , TypeB , TypeC , TypeF , Empty , Degenerate , Entire }

Public Member Functions
	Interval ()
	To satisfy the dataflow::ScalarLatticeValue requirements, this class must be default initializable.

UnreducedInterval	toUnreduced () const
	Convert to an UnreducedInterval.

UnreducedInterval	firstUnreduced () const
	Get the first side of the interval for TypeF intervals, otherwise just get the full interval as an UnreducedInterval (with toUnreduced).

UnreducedInterval	secondUnreduced () const
	Get the second side of the interval for TypeA, TypeB, and TypeC intervals.

Interval	join (const Interval &rhs) const
	Union.

Interval	intersect (const Interval &rhs) const
	Intersect.

Interval	difference (const Interval &other) const
	Computes and returns `this` - (`this` & `other`) if the operation produces a single interval.

Interval	operator- () const

Interval	operator~ () const

bool	isEmpty () const

bool	isNotEmpty () const

bool	isDegenerate () const

bool	isEntire () const

bool	isTypeA () const

bool	isTypeB () const

bool	isTypeC () const

bool	isTypeF () const

bool	isBoolFalse () const

bool	isBoolTrue () const

bool	isBoolEither () const

bool	isBoolean () const

template<Type... Types>
bool	is () const

bool	operator== (const Interval &rhs) const

const Field &	getField () const

llvm::APSInt	width () const

llvm::APSInt	lhs () const

llvm::APSInt	rhs () const

void	print (llvm::raw_ostream &os) const

Static Public Member Functions
static std::string_view	TypeName (Type t)

static Interval	Empty (const Field &f)

static Interval	Degenerate (const Field &f, llvm::APSInt val)

static Interval	False (const Field &f)

static Interval	True (const Field &f)

static Interval	Boolean (const Field &f)

static Interval	Entire (const Field &f)

static Interval	TypeA (const Field &f, llvm::APSInt a, llvm::APSInt b)

static Interval	TypeB (const Field &f, llvm::APSInt a, llvm::APSInt b)

static Interval	TypeC (const Field &f, llvm::APSInt a, llvm::APSInt b)

static Interval	TypeF (const Field &f, llvm::APSInt a, llvm::APSInt b)

template<std::pair< Type, Type >... Pairs>
static bool	areOneOf (const Interval &a, const Interval &b)

Static Public Attributes
static constexpr std::array< std::string_view, 7 >	TypeNames

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

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

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

Interval	operator% (const Interval &lhs, const Interval &rhs)

mlir::FailureOr< Interval >	operator/ (const Interval &lhs, const Interval &rhs)
	Returns failure if a division-by-zero is encountered.

Interval	operator& (const Interval &lhs, const Interval &rhs)

Interval	operator<< (const Interval &lhs, const Interval &rhs)

Interval	operator>> (const Interval &lhs, const Interval &rhs)

Interval	boolAnd (const Interval &lhs, const Interval &rhs)

Interval	boolOr (const Interval &lhs, const Interval &rhs)

Interval	boolXor (const Interval &lhs, const Interval &rhs)

Interval	boolNot (const Interval &iv)

llvm::raw_ostream &	operator<< (llvm::raw_ostream &os, const Interval &i)

Detailed Description

Intervals over a finite field.

Based on the Picus implementation. An interval may be:

Empty
Entire (meaning any value across the entire field)
Degenerate (meaning it contains a single value)
Or Type A–F. For these types, refer to the below notes:

A range [a, b] can be split into 2 categories:

Internal: a <= b
External: a > b – equivalent to [a, p-1] U [0, b]

Internal range can be further split into 3 categories: (A) a, b < p/2. E.g., [10, 12] (B) a, b > p/2. OR: a, b \in {-p/2, 0}. E.g., [p-4, p-2] === [-4, -2] (C) a < p/2, b > p/2. E.g., [p/2 - 5, p/2 + 5]

External range can be further split into 3 categories: (D) a, b < p/2. OR: a \in {-p, -p/2}, b \in {0, p/2}. E.g., [12, 10] === [-p+12, 10] (E) a, b > p/2. OR: a \in {-p/2, 0} , b \in {p/2, p}. E.g., [p-2, p-4] === [-2, p-4] (F) a > p/2, b < p/2. OR: a \in {-p/2, 0} , b \in {0, p/2}. E.g., [p/2 + 5, p/2 - 5] === [-p/2 + 5, p/2 - 5]

<-------------------------------------------------------------> -p -p/2 0 p/2 p [ A ] [ A ] [ B ] [ B ] [ C ] [ C ] F ] [ F ] [ F <------------------------------------------------------------->

D ] [ D ] [ D E ] [ E ] [ E

For the sake of simplicity, let's just not care about D and E, which covers at least half of the field, and potentially more.

Now, there are 4 choose 2 possible non-self interactions:

A acts on B:

intersection: impossible
union: C or F

A acts on C:

intersection: A
union: C

A acts on F:

intersection: A
union: F

B acts on C

intersection: B
union: C

B acts on F:

intersection: B
union: F

C acts on F:

intersection: A, B, C, F

E.g. [p/2 - 10, p/2 + 10] intersects [-p/2 + 2, p/2 - 2]

= ((-p/2 - 10, -p/2 + 10) intersects (-p/2 + 2, p/2 - 2)) union (( p/2 - 10, p/2 + 10) intersects (-p/2 + 2, p/2 - 2))

= (-p/2 + 2, -p/2 + 10) union (p/2 - 10, p/2 - 2)
union: don't care for now, we can revisit this later.

Definition at line 214 of file Intervals.h.

Member Enumeration Documentation

◆ Type

enum class llzk::Interval::Type

strong

Enumerator
TypeA
TypeB
TypeC
TypeF
Empty
Degenerate
Entire

Definition at line 216 of file Intervals.h.

Constructor & Destructor Documentation

◆ Interval()

llzk::Interval::Interval ( )

inline

To satisfy the dataflow::ScalarLatticeValue requirements, this class must be default initializable.

The default interval is the full range of values.

Definition at line 257 of file Intervals.h.

Member Function Documentation

◆ areOneOf()

template<std::pair< Type, Type >... Pairs>

static bool llzk::Interval::areOneOf	(	const Interval &	a,
		const Interval &	b )

inlinestatic

Definition at line 271 of file Intervals.h.

◆ Boolean()

static Interval llzk::Interval::Boolean ( const Field & f )

inlinestatic

Definition at line 235 of file Intervals.h.

◆ Degenerate()

static Interval llzk::Interval::Degenerate	(	const Field &	f,
		llvm::APSInt	val )

inlinestatic

Definition at line 227 of file Intervals.h.

◆ difference()

Interval llzk::Interval::difference ( const Interval & other ) const

Computes and returns this - (this & other) if the operation produces a single interval.

Note that this is an interval difference, not a subtraction operation like the operator- below.

For example, given *this = [1, 10] and other = [5, 11], this function would return [1, 4], as this & other (the intersection) = [5, 10], so [1, 10] - [5, 10] = [1, 4].

For example, given *this = [1, 10] and other = [5, 6], this function should return [1, 4] and [7, 10], but we don't support having multiple disjoint intervals, so this is returned as-is.

Definition at line 298 of file Intervals.cpp.

◆ Empty()

static Interval llzk::Interval::Empty ( const Field & f )

inlinestatic

Definition at line 225 of file Intervals.h.

◆ Entire()

static Interval llzk::Interval::Entire ( const Field & f )

inlinestatic

Definition at line 237 of file Intervals.h.

◆ False()

static Interval llzk::Interval::False ( const Field & f )

inlinestatic

Definition at line 231 of file Intervals.h.

◆ firstUnreduced()

UnreducedInterval llzk::Interval::firstUnreduced ( ) const

Get the first side of the interval for TypeF intervals, otherwise just get the full interval as an UnreducedInterval (with toUnreduced).

Definition at line 172 of file Intervals.cpp.

◆ getField()

const Field & llzk::Interval::getField ( ) const

inline

Definition at line 338 of file Intervals.h.

◆ intersect()

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

Intersect.

Definition at line 237 of file Intervals.cpp.

◆ is()

template<Type... Types>

bool llzk::Interval::is ( ) const

inline

Definition at line 332 of file Intervals.h.

◆ isBoolean()

bool llzk::Interval::isBoolean ( ) const

inline

Definition at line 330 of file Intervals.h.

◆ isBoolEither()

bool llzk::Interval::isBoolEither ( ) const

inline

Definition at line 329 of file Intervals.h.

◆ isBoolFalse()

bool llzk::Interval::isBoolFalse ( ) const

inline

Definition at line 327 of file Intervals.h.

◆ isBoolTrue()

bool llzk::Interval::isBoolTrue ( ) const

inline

Definition at line 328 of file Intervals.h.

◆ isDegenerate()

bool llzk::Interval::isDegenerate ( ) const

inline

Definition at line 320 of file Intervals.h.

◆ isEmpty()

bool llzk::Interval::isEmpty ( ) const

inline

Definition at line 318 of file Intervals.h.

◆ isEntire()

bool llzk::Interval::isEntire ( ) const

inline

Definition at line 321 of file Intervals.h.

◆ isNotEmpty()

bool llzk::Interval::isNotEmpty ( ) const

inline

Definition at line 319 of file Intervals.h.

◆ isTypeA()

bool llzk::Interval::isTypeA ( ) const

inline

Definition at line 322 of file Intervals.h.

◆ isTypeB()

bool llzk::Interval::isTypeB ( ) const

inline

Definition at line 323 of file Intervals.h.

◆ isTypeC()

bool llzk::Interval::isTypeC ( ) const

inline

Definition at line 324 of file Intervals.h.

◆ isTypeF()

bool llzk::Interval::isTypeF ( ) const

inline

Definition at line 325 of file Intervals.h.

◆ join()

Interval llzk::Interval::join ( const Interval & rhs ) const

Union.

Definition at line 184 of file Intervals.cpp.

◆ lhs()

llvm::APSInt llzk::Interval::lhs ( ) const

inline

Definition at line 342 of file Intervals.h.

◆ operator-()

Interval llzk::Interval::operator- ( ) const

Definition at line 360 of file Intervals.cpp.

◆ operator==()

bool llzk::Interval::operator== ( const Interval & rhs ) const

inline

Definition at line 334 of file Intervals.h.

◆ operator~()

Interval llzk::Interval::operator~ ( ) const

Definition at line 362 of file Intervals.cpp.

◆ print()

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

Definition at line 549 of file Intervals.cpp.

◆ rhs()

llvm::APSInt llzk::Interval::rhs ( ) const

inline

Definition at line 343 of file Intervals.h.

◆ secondUnreduced()

UnreducedInterval llzk::Interval::secondUnreduced ( ) const

Get the second side of the interval for TypeA, TypeB, and TypeC intervals.

Using this function is an error for all other interval types.

Definition at line 179 of file Intervals.cpp.

◆ toUnreduced()

UnreducedInterval llzk::Interval::toUnreduced ( ) const

Convert to an UnreducedInterval.

Definition at line 160 of file Intervals.cpp.

◆ True()

static Interval llzk::Interval::True ( const Field & f )

inlinestatic

Definition at line 233 of file Intervals.h.

◆ TypeA()

static Interval llzk::Interval::TypeA	(	const Field &	f,
		llvm::APSInt	a,
		llvm::APSInt	b )

inlinestatic

Definition at line 239 of file Intervals.h.

◆ TypeB()

static Interval llzk::Interval::TypeB	(	const Field &	f,
		llvm::APSInt	a,
		llvm::APSInt	b )

inlinestatic

Definition at line 243 of file Intervals.h.

◆ TypeC()

static Interval llzk::Interval::TypeC	(	const Field &	f,
		llvm::APSInt	a,
		llvm::APSInt	b )

inlinestatic

Definition at line 247 of file Intervals.h.

◆ TypeF()

static Interval llzk::Interval::TypeF	(	const Field &	f,
		llvm::APSInt	a,
		llvm::APSInt	b )

inlinestatic

Definition at line 251 of file Intervals.h.

◆ TypeName()

static std::string_view llzk::Interval::TypeName ( Type t )

inlinestatic

Definition at line 221 of file Intervals.h.

◆ width()

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

Definition at line 462 of file Intervals.cpp.

Friends And Related Symbol Documentation

◆ boolAnd

Interval boolAnd	(	const Interval &	lhs,
		const Interval &	rhs )

friend

Definition at line 475 of file Intervals.cpp.

◆ boolNot

Interval boolNot ( const Interval & iv )

friend

Definition at line 535 of file Intervals.cpp.

◆ boolOr

Interval boolOr	(	const Interval &	lhs,
		const Interval &	rhs )

friend

Definition at line 492 of file Intervals.cpp.

◆ boolXor

Interval boolXor	(	const Interval &	lhs,
		const Interval &	rhs )

friend

Definition at line 509 of file Intervals.cpp.

◆ operator%

Interval operator%	(	const Interval &	lhs,
		const Interval &	rhs )

friend

Definition at line 409 of file Intervals.cpp.

◆ operator&

Interval operator&	(	const Interval &	lhs,
		const Interval &	rhs )

friend

Definition at line 414 of file Intervals.cpp.

◆ operator*

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

friend

Definition at line 379 of file Intervals.cpp.

◆ operator+

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

friend

Definition at line 366 of file Intervals.cpp.

◆ operator-

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

friend

Definition at line 377 of file Intervals.cpp.

◆ operator/

mlir::FailureOr< Interval > operator/	(	const Interval &	lhs,
		const Interval &	rhs )

friend

Returns failure if a division-by-zero is encountered.

Definition at line 398 of file Intervals.cpp.

◆ operator<< [1/2]

Interval operator<<	(	const Interval &	lhs,
		const Interval &	rhs )

friend

Definition at line 429 of file Intervals.cpp.

◆ operator<< [2/2]

llvm::raw_ostream & operator<<	(	llvm::raw_ostream &	os,
		const Interval &	i )

friend

Definition at line 355 of file Intervals.h.

◆ operator>>

Interval operator>>	(	const Interval &	lhs,
		const Interval &	rhs )

friend

Definition at line 446 of file Intervals.cpp.

Member Data Documentation

◆ TypeNames

std::array<std::string_view, 7> llzk::Interval::TypeNames

staticconstexpr

Initial value:

= {"TypeA", "TypeB", "TypeC",
                                                                "TypeF", "Empty", "Degenerate",
                                                                "Entire"}

Definition at line 217 of file Intervals.h.

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

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

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Friends

Detailed Description

Member Enumeration Documentation

◆ Type

Constructor & Destructor Documentation

◆ Interval()

Member Function Documentation

◆ areOneOf()

◆ Boolean()

◆ Degenerate()

◆ difference()

◆ Empty()

◆ Entire()

◆ False()

◆ firstUnreduced()

◆ getField()

◆ intersect()

◆ is()

◆ isBoolean()

◆ isBoolEither()

◆ isBoolFalse()

◆ isBoolTrue()

◆ isDegenerate()

◆ isEmpty()

◆ isEntire()

◆ isNotEmpty()

◆ isTypeA()

◆ isTypeB()

◆ isTypeC()

◆ isTypeF()

◆ join()

◆ lhs()

◆ operator-()

◆ operator==()

◆ operator~()

◆ print()

◆ rhs()

◆ secondUnreduced()

◆ toUnreduced()

◆ True()

◆ TypeA()

◆ TypeB()

◆ TypeC()

◆ TypeF()

◆ TypeName()

◆ width()

Friends And Related Symbol Documentation

◆ boolAnd

◆ boolNot

◆ boolOr

◆ boolXor

◆ operator%

◆ operator&

◆ operator*

◆ operator+

◆ operator-

◆ operator/

◆ operator<< [1/2]

◆ operator<< [2/2]

◆ operator>>

Member Data Documentation

◆ TypeNames