EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient operations: insert an element into a class of its own, union two classes, and find the class for a given element. More...

#include "llvm/ADT/EquivalenceClasses.h"

Inheritance diagram for llvm::EquivalenceClasses< ElemTy >:

[legend]

Classes
class	ECValue
	ECValue - The EquivalenceClasses data structure is just a set of these. More...

class	member_iterator

Public Types
using	iterator = typename SmallVector< const ECValue * >::const_iterator
	iterator* - Provides a way to iterate over all values in the set.

Public Member Functions
	EquivalenceClasses ()=default

	EquivalenceClasses (const EquivalenceClasses &RHS)

EquivalenceClasses &	operator= (const EquivalenceClasses &RHS)

iterator	begin () const

iterator	end () const

bool	empty () const

member_iterator	member_begin (const ECValue &ECV) const

member_iterator	member_end () const

iterator_range< member_iterator >	members (const ECValue &ECV) const

iterator_range< member_iterator >	members (const ElemTy &V) const

bool	contains (const ElemTy &V) const
	Returns true if `V` is contained an equivalence class.

const ElemTy &	getLeaderValue (const ElemTy &V) const
	getLeaderValue - Return the leader for the specified value that is in the set.

const ElemTy &	getOrInsertLeaderValue (const ElemTy &V)
	getOrInsertLeaderValue - Return the leader for the specified value that is in the set.

unsigned	getNumClasses () const
	getNumClasses - Return the number of equivalence classes in this set.

const ECValue &	insert (const ElemTy &Data)
	insert - Insert a new value into the union/find set, ignoring the request if the value already exists.

bool	erase (const ElemTy &V)
	erase - Erase a value from the union/find set, return "true" if erase succeeded, or "false" when the value was not found.

member_iterator	findLeader (const ElemTy &V) const
	findLeader - Given a value in the set, return a member iterator for the equivalence class it is in.

member_iterator	findLeader (const ECValue &ECV) const

member_iterator	unionSets (const ElemTy &V1, const ElemTy &V2)
	union - Merge the two equivalence sets for the specified values, inserting them if they do not already exist in the equivalence set.

member_iterator	unionSets (member_iterator L1, member_iterator L2)

bool	isEquivalent (const ElemTy &V1, const ElemTy &V2) const

Detailed Description

template<class ElemTy>
class llvm::EquivalenceClasses< ElemTy >

EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient operations: insert an element into a class of its own, union two classes, and find the class for a given element.

In addition to these modification methods, it is possible to iterate over all of the equivalence classes and all of the elements in a class.

This implementation is an efficient implementation that only stores one copy of the element being indexed per entry in the set, and allows any arbitrary type to be indexed (as long as it can be implements DenseMapInfo).

Here is a simple example using integers:

EquivalenceClasses<int> EC;
EC.unionSets(1, 2);                // insert 1, 2 into the same set
EC.insert(4); EC.insert(5);        // insert 4, 5 into own sets
EC.unionSets(5, 1);                // merge the set for 1 with 5's set.
 
for (EquivalenceClasses<int>::iterator I = EC.begin(), E = EC.end();
     I != E; ++I) {           // Iterate over all of the equivalence sets.
  if (!I->isLeader()) continue;   // Ignore non-leader sets.
  for (EquivalenceClasses<int>::member_iterator MI = EC.member_begin(I);
       MI != EC.member_end(); ++MI)   // Loop over members in this set.
    cerr << *MI << " ";  // Print member.
  cerr << "\n";   // Finish set.
}

This example prints: 4 5 1 2

Definition at line 62 of file EquivalenceClasses.h.

Member Typedef Documentation

◆ iterator

template<class ElemTy >

using llvm::EquivalenceClasses< ElemTy >::iterator = typename SmallVector<const ECValue *>::const_iterator

iterator* - Provides a way to iterate over all values in the set.

Definition at line 158 of file EquivalenceClasses.h.

Constructor & Destructor Documentation

◆ EquivalenceClasses() [1/2]

template<class ElemTy >

llvm::EquivalenceClasses< ElemTy >::EquivalenceClasses ( )

default

◆ EquivalenceClasses() [2/2]

template<class ElemTy >

llvm::EquivalenceClasses< ElemTy >::EquivalenceClasses ( const EquivalenceClasses< ElemTy > & RHS )

inline

Definition at line 138 of file EquivalenceClasses.h.

References llvm::EquivalenceClasses< ElemTy >::operator=(), and RHS.

Member Function Documentation

◆ begin()

template<class ElemTy >

iterator llvm::EquivalenceClasses< ElemTy >::begin ( ) const

inline

Definition at line 160 of file EquivalenceClasses.h.

References llvm::SmallVectorTemplateCommon< T, typename >::begin().

◆ contains()

template<class ElemTy >

bool llvm::EquivalenceClasses< ElemTy >::contains ( const ElemTy & V ) const

inline

Returns true if V is contained an equivalence class.

Definition at line 183 of file EquivalenceClasses.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find().

◆ empty()

template<class ElemTy >

bool llvm::EquivalenceClasses< ElemTy >::empty ( ) const

inline

Definition at line 163 of file EquivalenceClasses.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::empty().

◆ end()

template<class ElemTy >

iterator llvm::EquivalenceClasses< ElemTy >::end ( ) const

inline

Definition at line 161 of file EquivalenceClasses.h.

References llvm::SmallVectorTemplateCommon< T, typename >::end().

◆ erase()

template<class ElemTy >

bool llvm::EquivalenceClasses< ElemTy >::erase ( const ElemTy & V )

inline

erase - Erase a value from the union/find set, return "true" if erase succeeded, or "false" when the value was not found.

Definition at line 233 of file EquivalenceClasses.h.

References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase(), llvm::SmallVectorImpl< T >::erase(), llvm::find(), llvm::EquivalenceClasses< ElemTy >::findLeader(), llvm::EquivalenceClasses< ElemTy >::ECValue::getNext(), I, and llvm::EquivalenceClasses< ElemTy >::ECValue::isLeader().

◆ findLeader() [1/2]

template<class ElemTy >

member_iterator llvm::EquivalenceClasses< ElemTy >::findLeader ( const ECValue & ECV ) const

inline

Definition at line 292 of file EquivalenceClasses.h.

◆ findLeader() [2/2]

template<class ElemTy >

member_iterator llvm::EquivalenceClasses< ElemTy >::findLeader ( const ElemTy & V ) const

inline

findLeader - Given a value in the set, return a member iterator for the equivalence class it is in.

This does the path-compression part that makes union-find "union findy". This returns an end iterator if the value is not in the equivalence class.

Definition at line 286 of file EquivalenceClasses.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::EquivalenceClasses< ElemTy >::findLeader(), and I.

Referenced by llvm::MemoryDepChecker::areDepsSafe(), llvm::EquivalenceClasses< ElemTy >::erase(), llvm::EquivalenceClasses< ElemTy >::findLeader(), llvm::EquivalenceClasses< ElemTy >::getLeaderValue(), llvm::EquivalenceClasses< ElemTy >::getOrInsertLeaderValue(), llvm::EquivalenceClasses< ElemTy >::isEquivalent(), llvm::EquivalenceClasses< ElemTy >::members(), and llvm::EquivalenceClasses< ElemTy >::unionSets().

◆ getLeaderValue()

template<class ElemTy >

const ElemTy & llvm::EquivalenceClasses< ElemTy >::getLeaderValue ( const ElemTy & V ) const

inline

getLeaderValue - Return the leader for the specified value that is in the set.

It is an error to call this method for a value that is not yet in the set. For that, call getOrInsertLeaderValue(V).

Definition at line 190 of file EquivalenceClasses.h.

References assert(), llvm::EquivalenceClasses< ElemTy >::findLeader(), llvm::EquivalenceClasses< ElemTy >::member_end(), and MI.

◆ getNumClasses()

template<class ElemTy >

unsigned llvm::EquivalenceClasses< ElemTy >::getNumClasses ( ) const

inline

getNumClasses - Return the number of equivalence classes in this set.

Note that this is a linear time operation.

Definition at line 207 of file EquivalenceClasses.h.

References E, and NC.

◆ getOrInsertLeaderValue()

template<class ElemTy >

const ElemTy & llvm::EquivalenceClasses< ElemTy >::getOrInsertLeaderValue ( const ElemTy & V )

inline

getOrInsertLeaderValue - Return the leader for the specified value that is in the set.

If the member is not in the set, it is inserted, then returned.

Definition at line 199 of file EquivalenceClasses.h.

References assert(), llvm::EquivalenceClasses< ElemTy >::findLeader(), llvm::EquivalenceClasses< ElemTy >::insert(), llvm::EquivalenceClasses< ElemTy >::member_end(), and MI.

Referenced by llvm::computeMinimumValueSizes().

◆ insert()

template<class ElemTy >

const ECValue & llvm::EquivalenceClasses< ElemTy >::insert ( const ElemTy & Data )

inline

insert - Insert a new value into the union/find set, ignoring the request if the value already exists.

Definition at line 220 of file EquivalenceClasses.h.

References llvm::Data, I, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().

Referenced by llvm::EquivalenceClasses< ElemTy >::getOrInsertLeaderValue(), llvm::EquivalenceClasses< ElemTy >::operator=(), and llvm::EquivalenceClasses< ElemTy >::unionSets().

◆ isEquivalent()

template<class ElemTy >

bool llvm::EquivalenceClasses< ElemTy >::isEquivalent	(	const ElemTy &	V1,
		const ElemTy &	V2
	)		const

inline

Definition at line 325 of file EquivalenceClasses.h.

References llvm::EquivalenceClasses< ElemTy >::findLeader(), and llvm::EquivalenceClasses< ElemTy >::member_end().

◆ member_begin()

template<class ElemTy >

member_iterator llvm::EquivalenceClasses< ElemTy >::member_begin ( const ECValue & ECV ) const

inline

Definition at line 167 of file EquivalenceClasses.h.

References llvm::EquivalenceClasses< ElemTy >::ECValue::isLeader().

Referenced by llvm::EquivalenceClasses< ElemTy >::members(), and llvm::EquivalenceClasses< ElemTy >::operator=().

◆ member_end()

template<class ElemTy >

member_iterator llvm::EquivalenceClasses< ElemTy >::member_end ( ) const

inline

Definition at line 172 of file EquivalenceClasses.h.

Referenced by llvm::MemoryDepChecker::areDepsSafe(), llvm::EquivalenceClasses< ElemTy >::getLeaderValue(), llvm::EquivalenceClasses< ElemTy >::getOrInsertLeaderValue(), llvm::EquivalenceClasses< ElemTy >::isEquivalent(), llvm::EquivalenceClasses< ElemTy >::members(), llvm::EquivalenceClasses< ElemTy >::operator=(), and llvm::EquivalenceClasses< ElemTy >::unionSets().

◆ members() [1/2]

template<class ElemTy >

iterator_range< member_iterator > llvm::EquivalenceClasses< ElemTy >::members ( const ECValue & ECV ) const

inline

Definition at line 174 of file EquivalenceClasses.h.

References llvm::make_range(), llvm::EquivalenceClasses< ElemTy >::member_begin(), and llvm::EquivalenceClasses< ElemTy >::member_end().

Referenced by llvm::computeMinimumValueSizes().

◆ members() [2/2]

template<class ElemTy >

iterator_range< member_iterator > llvm::EquivalenceClasses< ElemTy >::members ( const ElemTy & V ) const

inline

Definition at line 178 of file EquivalenceClasses.h.

References llvm::EquivalenceClasses< ElemTy >::findLeader(), llvm::make_range(), and llvm::EquivalenceClasses< ElemTy >::member_end().

◆ operator=()

template<class ElemTy >

EquivalenceClasses & llvm::EquivalenceClasses< ElemTy >::operator= ( const EquivalenceClasses< ElemTy > & RHS )

inline

Definition at line 140 of file EquivalenceClasses.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear(), llvm::SmallVectorImpl< T >::clear(), E, llvm::EquivalenceClasses< ElemTy >::insert(), llvm::EquivalenceClasses< ElemTy >::member_begin(), llvm::EquivalenceClasses< ElemTy >::member_end(), MI, RHS, and llvm::EquivalenceClasses< ElemTy >::unionSets().

Referenced by llvm::EquivalenceClasses< ElemTy >::EquivalenceClasses().

◆ unionSets() [1/2]

template<class ElemTy >

member_iterator llvm::EquivalenceClasses< ElemTy >::unionSets	(	const ElemTy &	V1,
		const ElemTy &	V2
	)

inline

union - Merge the two equivalence sets for the specified values, inserting them if they do not already exist in the equivalence set.

Definition at line 298 of file EquivalenceClasses.h.

References llvm::EquivalenceClasses< ElemTy >::findLeader(), llvm::EquivalenceClasses< ElemTy >::insert(), and llvm::EquivalenceClasses< ElemTy >::unionSets().

Referenced by llvm::computeMinimumValueSizes(), llvm::EquivalenceClasses< ElemTy >::operator=(), and llvm::EquivalenceClasses< ElemTy >::unionSets().

◆ unionSets() [2/2]

template<class ElemTy >

member_iterator llvm::EquivalenceClasses< ElemTy >::unionSets	(	member_iterator	L1,
		member_iterator	L2
	)

inline

Definition at line 302 of file EquivalenceClasses.h.

References assert(), llvm::EquivalenceClasses< ElemTy >::ECValue::getNext(), and llvm::EquivalenceClasses< ElemTy >::member_end().

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

include/llvm/ADT/EquivalenceClasses.h

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ iterator

Constructor & Destructor Documentation

◆ EquivalenceClasses() [1/2]

◆ EquivalenceClasses() [2/2]

Member Function Documentation

◆ begin()

◆ contains()

◆ empty()

◆ end()

◆ erase()

◆ findLeader() [1/2]

◆ findLeader() [2/2]

◆ getLeaderValue()

◆ getNumClasses()

◆ getOrInsertLeaderValue()

◆ insert()

◆ isEquivalent()

◆ member_begin()

◆ member_end()

◆ members() [1/2]

◆ members() [2/2]

◆ operator=()

◆ unionSets() [1/2]

◆ unionSets() [2/2]