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

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...
 
BlockTraceselectBadEdge (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.
 
FlowBlockfinishblock
 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()

ghidra::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
lgis the container for likely unstructured edges

References activecount, and finishblock.

Member Function Documentation

◆ checkOpen()

bool ghidra::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
traceis the given BlockTrace to push
Returns
true is the new node can be opened

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

Referenced by pushBranches().

◆ checkRetirement()

bool ghidra::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
traceis the given BlockTrace
exitblockwill hold the passed back exit block
Returns
true is the BlockTrace can be retired

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

Referenced by pushBranches().

◆ clearVisitCount()

void ghidra::TraceDAG::clearVisitCount ( void  )
private

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

Referenced by pushBranches().

◆ initialize()

void ghidra::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(), ghidra::TraceDAG::BranchPoint::paths, and rootlist.

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

◆ insertActive()

void ghidra::TraceDAG::insertActive ( BlockTrace trace)
private

Move a BlockTrace into the active category.

Parameters
traceis the BlockTrace to mark as active

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

Referenced by initialize().

◆ openBranch()

list< TraceDAG::BlockTrace * >::iterator ghidra::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
parentis the given BlockTrace to split
Returns
an iterator (within the active list) to the new BlockTrace objects

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

Referenced by pushBranches().

◆ processExitConflict()

void ghidra::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
startis the beginning of the list of conflicting BlockTraces (annotated as BadEdgeScore)
endis the end of the list of conflicting BlockTraces

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

◆ pushBranches()

void ghidra::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 ghidra::TraceDAG::BlockTrace::top.

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

◆ removeActive()

void ghidra::TraceDAG::removeActive ( BlockTrace trace)
private

Remove a BlockTrace from the active category.

Parameters
traceis the BlockTrace to be unmarked

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

◆ removeTrace()

void ghidra::TraceDAG::removeTrace ( BlockTrace trace)
private

◆ retireBranch()

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

◆ selectBadEdge()

TraceDAG::BlockTrace * ghidra::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 ghidra::TraceDAG::BadEdgeScore::exitproto, and ghidra::TraceDAG::BadEdgeScore::trace.

Referenced by pushBranches().


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