A description of the body of a loop. More...

#include <blockaction.hh>

Public Member Functions
	LoopBody (FlowBlock *h)
	Construct with a loop head.

FlowBlock *	getHead (void) const
	Return the head FlowBlock of the loop.

FlowBlock *	getCurrentBounds (FlowBlock *top, FlowBlock graph)
	Return current loop bounds (head and bottom). More...

void	addTail (FlowBlock *bl)
	Add a tail to the loop.

FlowBlock *	getExitBlock (void) const
	Get the exit FlowBlock or NULL.

void	findBase (vector< FlowBlock * > &body)
	Mark the body FlowBlocks of this loop. More...

void	extend (vector< FlowBlock * > &body) const
	Extend body (to blocks that never exit) More...

void	findExit (const vector< FlowBlock * > &body)
	Choose the exit block for this loop. More...

void	orderTails (void)
	Find preferred tail. More...

void	labelExitEdges (const vector< FlowBlock * > &body)
	Label edges that exit the loop. More...

void	labelContainments (const vector< FlowBlock * > &body, const vector< LoopBody * > &looporder)
	Record any loops that body contains. More...

void	emitLikelyEdges (list< FloatingEdge > &likely, FlowBlock *graph)
	Collect likely unstructured edges. More...

void	setExitMarks (FlowBlock *graph)
	Mark all the exits to this loop. More...

void	clearExitMarks (FlowBlock *graph)
	Clear the mark on all the exits to this loop. More...

bool	operator< (const LoopBody &op2) const
	Order loop bodies by depth.

Static Public Member Functions
static void	mergeIdenticalHeads (vector< LoopBody * > &looporder)
	Merge loop bodies that share the same head. More...

static bool	compare_ends (LoopBody a, LoopBody b)
	Compare the head then tail. More...

static int4	compare_head (LoopBody a, FlowBlock looptop)
	Compare just the head. More...

static LoopBody *	find (FlowBlock looptop, const vector< LoopBody > &looporder)
	Find a LoopBody. More...

static void	clearMarks (vector< FlowBlock * > &body)
	Clear the body marks. More...

Private Member Functions
void	extendToContainer (const LoopBody &container, vector< FlowBlock * > &body) const
	Find blocks in containing loop that aren't in this. More...

Private Attributes
FlowBlock *	head
	head of the loop

vector< FlowBlock * >	tails
	(Possibly multiple) nodes with back edge returning to the head

int4	depth
	Nested depth of this loop.

int4	uniquecount
	Total number of unique head and tail nodes.

FlowBlock *	exitblock
	Official exit block from loop, or NULL.

list< FloatingEdge >	exitedges
	Edges that exit to the formal exit block.

LoopBody *	immed_container
	Immediately containing loop body, or NULL.

Detailed Description

A description of the body of a loop.

Following Tarjan, assuming there are no irreducible edges, a loop body is defined by the head (or entry-point) and 1 or more tails, which each have a back edge into the head.

Member Function Documentation

void LoopBody::clearExitMarks ( FlowBlock * graph )

Clear the mark on all the exits to this loop.

This clears the f_loop_exit_edge on any edge exiting this loop.

Parameters

graph is the containing control-flow structure

References FlowBlock::clearLoopExit().

void LoopBody::clearMarks ( vector< FlowBlock * > & body )

static

Clear the body marks.

Parameters

body	is the list of FlowBlock nodes that have been marked

Referenced by CollapseStructure::clipExtraRoots(), and CollapseStructure::orderLoopBodies().

bool LoopBody::compare_ends	(	LoopBody *	a,
		LoopBody *	b
	)

static

Compare the head then tail.

Compare two loops based on the indices of the head and then the tail.

Parameters

a	is the first LoopBody to compare
b	is the second LoopBody to compare

Returns: true if the first LoopBody comes before the second

References FlowBlock::getIndex(), head, and tails.

Referenced by CollapseStructure::labelLoops().

int4 LoopBody::compare_head	(	LoopBody *	a,
		FlowBlock *	looptop
	)

static

Compare just the head.

Compare two loops based on the indices of the head

Parameters

a	is the first LoopBody to compare
looptop	is the second

Returns: -1,0, or 1 if the first is ordered before, the same, or after the second

References FlowBlock::getIndex(), and head.

void LoopBody::emitLikelyEdges	(	list< FloatingEdge > &	likely,
		FlowBlock *	graph
	)

Collect likely unstructured edges.

Add edges that exit from this loop body to the list of likely gotos, giving them the proper priority.

Parameters

likely	will hold the exit edges in (reverse) priority order
graph	is the containing control-flow graph

References FloatingEdge::FloatingEdge(), FlowBlock::getOut(), FlowBlock::getParent(), and FlowBlock::sizeOut().

void LoopBody::extend ( vector< FlowBlock * > & body ) const

Extend body (to blocks that never exit)

Extend the body of this loop to every FlowBlock that can be reached only from head without hitting the exitblock. Assume body has been filled out by findBase() and that all these blocks have their mark set.

Parameters

body	contains the current loop body and will be extended

References FlowBlock::getOut(), FlowBlock::getVisitCount(), FlowBlock::isGotoOut(), FlowBlock::isMark(), FlowBlock::setMark(), FlowBlock::setVisitCount(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

void LoopBody::extendToContainer	(	const LoopBody &	container,
		vector< FlowBlock * > &	body
	)		const

private

Find blocks in containing loop that aren't in this.

Assuming this has all of its nodes marked, find all additional nodes that create the body of the container loop. Mark these and put them in body list.

Parameters

container	is a loop that contains this
body	will hold blocks in the body of the container that aren't in this

References FlowBlock::getIn(), head, FlowBlock::isGotoIn(), FlowBlock::isMark(), FlowBlock::setMark(), FlowBlock::sizeIn(), and tails.

LoopBody * LoopBody::find	(	FlowBlock *	looptop,
		const vector< LoopBody * > &	looporder
	)

static

Find a LoopBody.

Given the top FlowBlock of a loop, find corresponding LoopBody record from an ordered list. This assumes mergeIdenticalHeads() has been run so that the head is uniquely identifying.

Parameters

looptop	is the top of the loop
looporder	is the ordered list of LoopBody records

Returns: the LoopBody or NULL if none found

Referenced by labelContainments().

void LoopBody::findBase ( vector< FlowBlock * > & body )

Mark the body FlowBlocks of this loop.

Collect all FlowBlock nodes that reach a tail of the loop without going through head. Put them in a list and mark them.

Parameters

body	will contain the body nodes

References FlowBlock::getIn(), FlowBlock::isGotoIn(), FlowBlock::isMark(), FlowBlock::setMark(), and FlowBlock::sizeIn().

void LoopBody::findExit ( const vector< FlowBlock * > & body )

Choose the exit block for this loop.

A structured loop is allowed at most one exit block: pick this block. First build a set of trial exits, preferring from a tail, then from head, then from the middle. If there is no containing loop, just return the first such exit we find.

Parameters

body	is the list FlowBlock objects in the loop body, which we assume are marked.

References FlowBlock::getOut(), FlowBlock::isGotoOut(), FlowBlock::isMark(), and FlowBlock::sizeOut().

FlowBlock * LoopBody::getCurrentBounds	(	FlowBlock **	top,
		FlowBlock *	graph
	)

Return current loop bounds (head and bottom).

This updates the head and tail nodes to FlowBlock in the current collapsed graph. This returns the first tail and passes back the head.

Parameters

top	is where head is passed back
graph	is the containing control-flow structure

Returns: the current loop head

References FloatingEdge::bottom, and FlowBlock::getParent().

void LoopBody::labelContainments	(	const vector< FlowBlock * > &	body,
		const vector< LoopBody * > &	looporder
	)

Record any loops that body contains.

Search for any loop contained by this and update is depth and immed_container field.

Parameters

body	is the set of FlowBlock nodes making up this loop
looporder	is the list of known loops

References depth, find(), and immed_container.

void LoopBody::labelExitEdges ( const vector< FlowBlock * > & body )

Label edges that exit the loop.

Label any edge that leaves the set of nodes in body. Put the edges in priority for removal, middle exit at front, head exit, then tail exit. We assume all the FlowBlock nodes in body have been marked.

Parameters

body	is list of nodes in this loop body

References FloatingEdge::FloatingEdge(), FlowBlock::getOut(), FlowBlock::isGotoOut(), FlowBlock::isMark(), and FlowBlock::sizeOut().

void LoopBody::mergeIdenticalHeads ( vector< LoopBody * > & looporder )

static

Merge loop bodies that share the same head.

Look for LoopBody records that share a head. Merge each tail from one into the other. Set the merged LoopBody head to NULL, for later clean up.

Parameters

looporder is the list of LoopBody records

References addTail(), head, and tails.

Referenced by CollapseStructure::orderLoopBodies().

void LoopBody::orderTails ( void )

Find preferred tail.

The idea is if there is more than one tail for a loop, some tails are more "preferred" than others and should have their exit edges preserved longer and be the target of the DAG path. Currently we look for a single tail that has an outgoing edge to the exitblock and make sure it is the first tail.

References FlowBlock::getOut(), and FlowBlock::sizeOut().

void LoopBody::setExitMarks ( FlowBlock * graph )

Mark all the exits to this loop.

Exit edges have their f_loop_exit_edge property set.

Parameters

graph is the containing control-flow structure

References FlowBlock::setLoopExit().

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

blockaction.hh
blockaction.cc

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Function Documentation