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

#include <blockaction.hh>

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

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...

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...

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

◆ clearExitMarks()

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

◆ clearMarks()

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

static

Clear the body marks.

Parameters

body	is the list of FlowBlock nodes that have been marked

◆ compare_ends()

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

◆ compare_head()

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

◆ emitLikelyEdges()

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

◆ extend()

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

◆ find()

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

◆ findBase()

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

◆ findExit()

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.

◆ getCurrentBounds()

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

◆ labelContainments()

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

◆ labelExitEdges()

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

◆ mergeIdenticalHeads()

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

◆ orderTails()

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.

◆ setExitMarks()

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

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

blockaction.hh
blockaction.cc

Public Member Functions

Static Public Member Functions

Detailed Description

Member Function Documentation

◆ clearExitMarks()

◆ clearMarks()

◆ compare_ends()

◆ compare_head()

◆ emitLikelyEdges()

◆ extend()

◆ find()

◆ findBase()

◆ findExit()

◆ getCurrentBounds()

◆ labelContainments()

◆ labelExitEdges()

◆ mergeIdenticalHeads()

◆ orderTails()

◆ setExitMarks()