Algorithm for selecting unstructured edges based an Directed Acyclic Graphs (DAG) More...

#include <blockaction.hh>

Classes
struct	BadEdgeScore
	Record for scoring a BlockTrace for suitability as an unstructured branch. More...

struct	BlockTrace
	A trace of a single path out of a BranchPoint. More...

struct	BranchPoint

Public Member Functions
	TraceDAG (list< FloatingEdge > &lg)
	Clear the visitcount field of any FlowBlock we have modified. More...

	~TraceDAG (void)
	Destructor.

void	addRoot (FlowBlock *root)
	Add a root FlowBlock to the trace.

void	initialize (void)
	Create the initial BranchPoint and BlockTrace objects. More...

void	pushBranches (void)
	Push the trace through, removing edges as necessary. More...

void	setFinishBlock (FlowBlock *bl)
	Mark an exit point not to trace beyond.

Private Member Functions
void	removeTrace (BlockTrace *trace)
	Remove the indicated BlockTrace. More...

void	processExitConflict (list< BadEdgeScore >::iterator start, list< BadEdgeScore >::iterator end)
	Process a set of conflicting BlockTrace objects that go to the same exit point. More...

BlockTrace *	selectBadEdge (void)
	Select the the most likely unstructured edge from active BlockTraces. More...

void	insertActive (BlockTrace *trace)
	Move a BlockTrace into the active category. More...

void	removeActive (BlockTrace *trace)
	Remove a BlockTrace from the active category. More...

bool	checkOpen (BlockTrace *trace)
	Check if we can push the given BlockTrace into its next node. More...

list< BlockTrace * >::iterator	openBranch (BlockTrace *parent)
	Open a new BranchPoint along a given BlockTrace. More...

bool	checkRetirement (BlockTrace trace, FlowBlock &exitblock)
	Check if a given BlockTrace can be retired. More...

list< BlockTrace * >::iterator	retireBranch (BranchPoint bp, FlowBlock exitblock)
	Retire a BranchPoint, updating its parent BlockTrace. More...

void	clearVisitCount (void)

Private Attributes
list< FloatingEdge > &	likelygoto
	A reference to the list of likely goto edges being produced.

vector< FlowBlock * >	rootlist
	List of root FlowBlocks to trace from.

vector< BranchPoint * >	branchlist
	Current set of BranchPoints that have been traced.

int4	activecount
	Number of active BlockTrace objects.

int4	missedactivecount
	Current number of active BlockTraces that can't be pushed further.

list< BlockTrace * >	activetrace
	The list of active BlockTrace objects.

list< BlockTrace * >::iterator	current_activeiter
	The current active BlockTrace being pushed.

FlowBlock *	finishblock
	Designated exit block for the DAG (or null)

Detailed Description

Algorithm for selecting unstructured edges based an Directed Acyclic Graphs (DAG)

With the exception of the back edges in loops, structured code tends to form a DAG. Within the DAG, all building blocks of structured code have a single node entry point and (at most) one exit block. Given root points, this class traces edges with this kind of structure. Paths can recursively split at any point, starting a new active BranchPoint, but the BranchPoint can't be retired until all paths emanating from its start either terminate or come back together at the same FlowBlock node. Once a BranchPoint is retired, all the edges traversed from the start FlowBlock to the end FlowBlock are likely structurable. After pushing the traces as far as possible and retiring as much as possible, any active edge left is a candidate for an unstructured branch.

Ultimately this produces a list of likely gotos, which is used whenever the structuring algorithm (ActionBlockStructure) gets stuck.

The tracing can be restricted to a loopbody by setting the top FlowBlock of the loop as the root, and the loop exit block as the finish block. Additionally, any edges that exit the loop should be marked using LoopBody::setExitMarks().

Constructor & Destructor Documentation

TraceDAG::TraceDAG ( list< FloatingEdge > & lg )

Clear the visitcount field of any FlowBlock we have modified.

Construct given the container for likely unstructured edges

Prepare for a new trace using the provided storage for the likely unstructured edges that will be discovered.

Parameters

lg	is the container for likely unstructured edges

References activecount, and finishblock.

Member Function Documentation

bool TraceDAG::checkOpen ( BlockTrace * trace )

private

Check if we can push the given BlockTrace into its next node.

Verify the given BlockTrace can push into the next FlowBlock (destnode). A FlowBlock node can only be opened if all the incoming edges have been traced.

Parameters

trace is the given BlockTrace to push

Returns: true is the new node can be opened

References TraceDAG::BlockTrace::bottom, TraceDAG::BranchPoint::depth, TraceDAG::BlockTrace::destnode, TraceDAG::BlockTrace::edgelump, FlowBlock::getVisitCount(), FlowBlock::isLoopDAGIn(), TraceDAG::BlockTrace::isTerminal(), FlowBlock::sizeIn(), and TraceDAG::BlockTrace::top.

Referenced by pushBranches().

bool TraceDAG::checkRetirement	(	BlockTrace *	trace,
		FlowBlock *&	exitblock
	)

private

Check if a given BlockTrace can be retired.

For the given BlockTrace, make sure all other sibling BlockTraces from its BranchPoint parent either terminate or flow to the same FlowBlock node. If so, return true and pass back that node as the exitblock.

Parameters

trace	is the given BlockTrace
exitblock	will hold the passed back exit block

Returns: true is the BlockTrace can be retired

References TraceDAG::BranchPoint::depth, TraceDAG::BlockTrace::destnode, TraceDAG::BlockTrace::isActive(), TraceDAG::BlockTrace::isTerminal(), TraceDAG::BlockTrace::pathout, TraceDAG::BranchPoint::paths, and TraceDAG::BlockTrace::top.

Referenced by pushBranches().

void TraceDAG::clearVisitCount ( void )

private

The visitcount field is only modified in removeTrace() whenever we put an edge in the likelygoto list.

Referenced by pushBranches().

void TraceDAG::initialize ( void )

Create the initial BranchPoint and BlockTrace objects.

Given the registered root FlowBlocks, create the initial (virtual) BranchPoint and an associated BlockTrace for each root FlowBlock.

References branchlist, insertActive(), TraceDAG::BranchPoint::paths, and rootlist.

Referenced by CollapseStructure::updateLoopBody().

void TraceDAG::insertActive ( BlockTrace * trace )

private

Move a BlockTrace into the active category.

Parameters

trace is the BlockTrace to mark as active

References TraceDAG::BlockTrace::activeiter, and TraceDAG::BlockTrace::flags.

Referenced by initialize().

list< TraceDAG::BlockTrace * >::iterator TraceDAG::openBranch ( BlockTrace * parent )

private

Open a new BranchPoint along a given BlockTrace.

Given that a BlockTrace can be opened into its next FlowBlock node, create a new BranchPoint at that node, and set up new sub-traces.

Parameters

parent is the given BlockTrace to split

Returns: an iterator (within the active list) to the new BlockTrace objects

References TraceDAG::BlockTrace::activeiter, TraceDAG::BlockTrace::bottom, TraceDAG::BlockTrace::derivedbp, TraceDAG::BlockTrace::destnode, TraceDAG::BlockTrace::edgelump, TraceDAG::BlockTrace::flags, and TraceDAG::BranchPoint::paths.

Referenced by pushBranches().

void TraceDAG::processExitConflict	(	list< BadEdgeScore >::iterator	start,
		list< BadEdgeScore >::iterator	end
	)

private

Process a set of conflicting BlockTrace objects that go to the same exit point.

For each conflicting BlockTrace, calculate the minimum distance between it and any other BlockTrace.

Parameters

start	is the beginning of the list of conflicting BlockTraces (annotated as BadEdgeScore)
end	is the end of the list of conflicting BlockTraces

References TraceDAG::BranchPoint::distance(), TraceDAG::BranchPoint::markPath(), and TraceDAG::BranchPoint::top.

void TraceDAG::pushBranches ( void )

Push the trace through, removing edges as necessary.

From the root BranchPoint, recursively push the trace. At any point where pushing is no longer possible, select an appropriate edge to remove and add it to the list of likely unstructured edges. Then continue pushing the trace.

References activecount, activetrace, checkOpen(), checkRetirement(), clearVisitCount(), current_activeiter, missedactivecount, openBranch(), removeTrace(), retireBranch(), selectBadEdge(), and TraceDAG::BlockTrace::top.

Referenced by CollapseStructure::updateLoopBody().

void TraceDAG::removeActive ( BlockTrace * trace )

private

Remove a BlockTrace from the active category.

Parameters

trace is the BlockTrace to be unmarked

References TraceDAG::BlockTrace::activeiter, and TraceDAG::BlockTrace::flags.

void TraceDAG::removeTrace ( BlockTrace * trace )

private

Remove the indicated BlockTrace.

This adds the BlockTrace to the list of potential unstructured edges. Then patch up the BranchPoint/BlockTrace/pathout hierarchy.

Parameters

trace is the indicated BlockTrace to remove

References TraceDAG::BlockTrace::bottom, TraceDAG::BlockTrace::derivedbp, TraceDAG::BlockTrace::destnode, TraceDAG::BlockTrace::edgelump, TraceDAG::BlockTrace::flags, FloatingEdge::FloatingEdge(), FlowBlock::getVisitCount(), TraceDAG::BranchPoint::pathout, TraceDAG::BlockTrace::pathout, TraceDAG::BranchPoint::paths, FlowBlock::setVisitCount(), TraceDAG::BranchPoint::top, and TraceDAG::BlockTrace::top.

Referenced by pushBranches().

list< TraceDAG::BlockTrace * >::iterator TraceDAG::retireBranch	(	BranchPoint *	bp,
		FlowBlock *	exitblock
	)

private

Retire a BranchPoint, updating its parent BlockTrace.

Knowing a given BranchPoint can be retired, remove all its BlockTraces from the active list, and update the BranchPoint's parent BlockTrace as having reached the BlockTrace exit point.

Parameters

bp	is the given BranchPoint
exitblock	is unique exit FlowBlock (calculated by checkRetirement())

Returns: an iterator to the next active BlockTrace to examine

References TraceDAG::BlockTrace::activeiter, TraceDAG::BlockTrace::bottom, TraceDAG::BranchPoint::depth, TraceDAG::BlockTrace::derivedbp, TraceDAG::BlockTrace::destnode, TraceDAG::BlockTrace::edgelump, TraceDAG::BlockTrace::flags, TraceDAG::BlockTrace::isTerminal(), TraceDAG::BranchPoint::parent, TraceDAG::BranchPoint::pathout, and TraceDAG::BranchPoint::paths.

Referenced by pushBranches().

TraceDAG::BlockTrace * TraceDAG::selectBadEdge ( void )

private

Select the the most likely unstructured edge from active BlockTraces.

Run through the list of active BlockTrace objects, annotate them using the BadEdgeScore class, then select the BlockTrace which is the most likely candidate for an unstructured edge.

Returns: the BlockTrace corresponding to the unstructured edge

References TraceDAG::BadEdgeScore::exitproto, and TraceDAG::BadEdgeScore::trace.

Referenced by pushBranches().

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

blockaction.hh
blockaction.cc

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation