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

#include <Worklist.hpp>

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

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

Public Member Functions
	~TwoPhaseLrfWorklist () override=default
	TwoPhaseLrfWorklist ()=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 Attributes
std::vector< std::pair< size_t, T > >	Current_
std::vector< std::pair< size_t, T > >	Next_
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::TwoPhaseLrfWorklist< T >

Worklist implementation similar to "Least Recently Fired", but using two lists. Pushed work items are added to next, and popped from current. When current is empty, next is sorted by last fired time, and becomes the new current. Pushing a work item that is already in next or current is a no-op. Two-phase LRF is presented by B. Hardekopf and C. Lin "The And and the Grasshopper: Fast and Accurate Pointer Analysis for Millions of Lines of Code" (2007)

Template Parameters

T	the type of the work items.

See also

Worklist

Definition at line 236 of file Worklist.hpp.

Constructor & Destructor Documentation

~TwoPhaseLrfWorklist()

template<typename T >

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

overridedefault

TwoPhaseLrfWorklist()

template<typename T >

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

default

Member Function Documentation

HasMoreWorkItems()

template<typename T >

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

inlineoverridevirtualnoexcept

Returns

true if there are work items left to be visited

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

Definition at line 244 of file Worklist.hpp.

PopWorkItem()

template<typename T >

T jlm::util::TwoPhaseLrfWorklist< 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 250 of file Worklist.hpp.

PushWorkItem()

template<typename T >

void jlm::util::TwoPhaseLrfWorklist< 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 267 of file Worklist.hpp.

Member Data Documentation

Current_

template<typename T >

std::vector<std::pair<size_t, T> > jlm::util::TwoPhaseLrfWorklist< T >::Current_

private

Definition at line 283 of file Worklist.hpp.

FireCounter_

template<typename T >

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

private

Definition at line 290 of file Worklist.hpp.

InQueueSentinelValue

template<typename T >

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

inlinestaticprivate

Definition at line 280 of file Worklist.hpp.

LastFire_

template<typename T >

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

private

Definition at line 294 of file Worklist.hpp.

Next_

template<typename T >

std::vector<std::pair<size_t, T> > jlm::util::TwoPhaseLrfWorklist< T >::Next_

private

Definition at line 287 of file Worklist.hpp.

---

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

• jlm/util/Worklist.hpp