PriorityQueue Class Reference

Priority queue for the phi-node (MULTIEQUAL) placement algorithm. More...

#include <heritage.hh>

Public Member Functions
	PriorityQueue (void)
	Constructor.
void	reset (int4 maxdepth)
	Reset to an empty queue. More...
void	insert (FlowBlock *bl, int4 depth)
	Insert a block into the queue given its priority. More...
FlowBlock *	extract (void)
	Retrieve the highest priority block. More...
bool	empty (void) const
	Return true if this queue is empty.

Private Attributes
vector< vector< FlowBlock * > >	queue
	An array of stacks, indexed by priority.
int4	curdepth
	The current highest priority index with active blocks.

Detailed Description

Priority queue for the phi-node (MULTIEQUAL) placement algorithm.

A work-list for basic blocks used during phi-node placement. Implemented as a set of stacks with an associated priority. Blocks are placed in the queue with an associated priority (or depth) using the insert() method. The current highest priority block is retrieved with the extract() method.

Member Function Documentation

FlowBlock * PriorityQueue::extract

(

void

)

Retrieve the highest priority block.

The block at the top of the highest priority non-empty stack is popped and returned. This will always return a block. It shouldn't be called if the queue is empty.

Returns

the highest priority block

void PriorityQueue::insert	(	FlowBlock *	bl,
		int4	depth
	)

Insert a block into the queue given its priority.

The block is pushed onto the stack of the given priority.

Parameters

bl	is the block being added to the queue
depth	is the priority to associate with the block

void PriorityQueue::reset

(

int4

maxdepth

)

Reset to an empty queue.

Any basic blocks currently in this queue are removed. Space is reserved for a new set of prioritized stacks.

Parameters

maxdepth

is the number of stacks to allocate

---

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

• heritage.hh
• heritage.cc