jlm::util::LrfWorklist< T > Class Template Reference

#include <Worklist.hpp>

Inheritance diagram for jlm::util::LrfWorklist< T >:

Collaboration diagram for jlm::util::LrfWorklist< T >:

Public Member Functions
	~LrfWorklist () override=default
	LrfWorklist ()=default
bool	HasMoreWorkItems () const noexcept override
T	PopWorkItem () override
void	PushWorkItem (T item) override
Public Member Functions inherited from jlm::util::Worklist< T >
virtual	~Worklist ()=default
	Worklist ()=default
	Worklist (const Worklist &other)=delete
	Worklist (Worklist &&other)=default
Worklist &	operator= (const Worklist &other)=delete
Worklist &	operator= (Worklist &&other)=default

Private Types
template<typename U >
using	MinPriorityQueue = std::priority_queue< U, std::vector< U >, std::greater< U > >

Private Attributes
MinPriorityQueue< std::pair< size_t, T > >	WorkItems_
size_t	FireCounter_ = 0
std::unordered_map< T, size_t >	LastFire_

Static Private Attributes
static const size_t	InQueueSentinelValue = std::numeric_limits<size_t>::max()

Detailed Description

template<typename T>
class jlm::util::LrfWorklist< T >

Worklist implementation using a priority queue, ordering work items by "Least Recently Fired". Each work item is time stamped when it leaves the work list. When selecting a work item from the list, the item with the oldest time stemp (or no time stamp, if any) is chosen. LRF is presented in A. Kanamori and D. Weise "Worklist management strategies for Dataflow Analysis" (1994), and used in Pierce's "Online cycle detection and difference propagation for pointer analysis" (2003).

Template Parameters

T	the type of the work items.

See also

Worklist

Definition at line 169 of file Worklist.hpp.

Member Typedef Documentation

MinPriorityQueue

template<typename T >

template<typename U >

using jlm::util::LrfWorklist< T >::MinPriorityQueue = std::priority_queue<U, std::vector<U>, std::greater<U> >

private

Definition at line 211 of file Worklist.hpp.

Constructor & Destructor Documentation

~LrfWorklist()

template<typename T >

jlm::util::LrfWorklist< T >::~LrfWorklist ( )

overridedefault

LrfWorklist()

template<typename T >

jlm::util::LrfWorklist< T >::LrfWorklist ( )

default

Member Function Documentation

HasMoreWorkItems()

template<typename T >

bool jlm::util::LrfWorklist< T >::HasMoreWorkItems ( ) const

inlineoverridevirtualnoexcept

Returns

true if there are work items left to be visited

Implements jlm::util::Worklist< T >.

Definition at line 177 of file Worklist.hpp.

PopWorkItem()

template<typename T >

T jlm::util::LrfWorklist< T >::PopWorkItem ( )

inlineoverridevirtual

Removes one work item from the worklist. Requires there to be at least one work item left.

Returns

the removed work item.

Implements jlm::util::Worklist< T >.

Definition at line 183 of file Worklist.hpp.

PushWorkItem()

template<typename T >

void jlm::util::LrfWorklist< T >::PushWorkItem ( T  item )

inlineoverridevirtual

Adds a work item to the worklist. If the item is already present, the item is not added again, but its position may be changed.

Parameters

item	the work item to be added.

Implements jlm::util::Worklist< T >.

Definition at line 194 of file Worklist.hpp.

Member Data Documentation

FireCounter_

template<typename T >

size_t jlm::util::LrfWorklist< T >::FireCounter_ = 0

private

Definition at line 217 of file Worklist.hpp.

InQueueSentinelValue

template<typename T >

const size_t jlm::util::LrfWorklist< T >::InQueueSentinelValue = std::numeric_limits<size_t>::max()

inlinestaticprivate

Definition at line 207 of file Worklist.hpp.

LastFire_

template<typename T >

std::unordered_map<T, size_t> jlm::util::LrfWorklist< T >::LastFire_

private

Definition at line 221 of file Worklist.hpp.

WorkItems_

template<typename T >

MinPriorityQueue<std::pair<size_t, T> > jlm::util::LrfWorklist< T >::WorkItems_

private

Definition at line 214 of file Worklist.hpp.

---

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

• jlm/util/Worklist.hpp