decompiler  1.0.0
Public Member Functions | Static Public Member Functions | Private Member Functions | Private Attributes | List of all members
ghidra::LoopBody Class Reference

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

#include <blockaction.hh>

Public Member Functions

 LoopBody (FlowBlock *h)
 Construct with a loop head.
 
FlowBlockgetHead (void) const
 Return the head FlowBlock of the loop.
 
FlowBlockgetCurrentBounds (FlowBlock **top, FlowBlock *graph)
 Return current loop bounds (head and bottom). More...
 
void addTail (FlowBlock *bl)
 Add a tail to the loop.
 
FlowBlockgetExitBlock (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 LoopBodyfind (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

FlowBlockhead
 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.
 
FlowBlockexitblock
 Official exit block from loop, or NULL.
 
list< FloatingEdgeexitedges
 Edges that exit to the formal exit block.
 
LoopBodyimmed_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

◆ clearExitMarks()

void ghidra::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
graphis the containing control-flow structure

References ghidra::FlowBlock::clearLoopExit().

◆ clearMarks()

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

Clear the body marks.

Parameters
bodyis the list of FlowBlock nodes that have been marked

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

◆ compare_ends()

bool ghidra::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
ais the first LoopBody to compare
bis the second LoopBody to compare
Returns
true if the first LoopBody comes before the second

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

Referenced by ghidra::CollapseStructure::labelLoops().

◆ compare_head()

int4 ghidra::LoopBody::compare_head ( LoopBody a,
FlowBlock looptop 
)
static

Compare just the head.

Compare two loops based on the indices of the head

Parameters
ais the first LoopBody to compare
looptopis the second
Returns
-1,0, or 1 if the first is ordered before, the same, or after the second

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

◆ emitLikelyEdges()

void ghidra::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
likelywill hold the exit edges in (reverse) priority order
graphis the containing control-flow graph

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

◆ extend()

void ghidra::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
bodycontains the current loop body and will be extended

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

◆ extendToContainer()

void ghidra::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
containeris a loop that contains this
bodywill hold blocks in the body of the container that aren't in this

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

◆ find()

LoopBody * ghidra::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
looptopis the top of the loop
looporderis the ordered list of LoopBody records
Returns
the LoopBody or NULL if none found

Referenced by labelContainments().

◆ findBase()

void ghidra::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
bodywill contain the body nodes

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

◆ findExit()

void ghidra::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
bodyis the list FlowBlock objects in the loop body, which we assume are marked.

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

◆ getCurrentBounds()

FlowBlock * ghidra::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
topis where head is passed back
graphis the containing control-flow structure
Returns
the current loop head

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

◆ labelContainments()

void ghidra::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
bodyis the set of FlowBlock nodes making up this loop
looporderis the list of known loops

References depth, find(), and immed_container.

◆ labelExitEdges()

void ghidra::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
bodyis list of nodes in this loop body

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

◆ mergeIdenticalHeads()

void ghidra::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
looporderis the list of LoopBody records

References addTail(), head, and tails.

Referenced by ghidra::CollapseStructure::orderLoopBodies().

◆ orderTails()

void ghidra::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 ghidra::FlowBlock::getOut(), and ghidra::FlowBlock::sizeOut().

◆ setExitMarks()

void ghidra::LoopBody::setExitMarks ( FlowBlock graph)

Mark all the exits to this loop.

Exit edges have their f_loop_exit_edge property set.

Parameters
graphis the containing control-flow structure

References ghidra::FlowBlock::setLoopExit().


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