decompiler
1.0.0
|
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) | |
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().
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.
lg | is the container for likely unstructured edges |
References activecount, and finishblock.
|
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.
trace | is the given BlockTrace to push |
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().
|
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.
trace | is the given BlockTrace |
exitblock | will hold the passed back exit block |
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().
|
private |
The visitcount field is only modified in removeTrace() whenever we put an edge in the likelygoto list.
Referenced by pushBranches().
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().
|
private |
Move a BlockTrace into the active category.
trace | is the BlockTrace to mark as active |
References ghidra::TraceDAG::BlockTrace::activeiter, and ghidra::TraceDAG::BlockTrace::flags.
Referenced by initialize().
|
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.
parent | is the given BlockTrace to split |
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().
|
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.
start | is the beginning of the list of conflicting BlockTraces (annotated as BadEdgeScore) |
end | is the end of the list of conflicting BlockTraces |
References ghidra::TraceDAG::BranchPoint::distance(), ghidra::TraceDAG::BranchPoint::markPath(), and ghidra::TraceDAG::BranchPoint::top.
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().
|
private |
Remove a BlockTrace from the active category.
trace | is the BlockTrace to be unmarked |
References ghidra::TraceDAG::BlockTrace::activeiter, and ghidra::TraceDAG::BlockTrace::flags.
|
private |
Remove the indicated BlockTrace.
This adds the BlockTrace to the list of potential unstructured edges. Then patch up the BranchPoint/BlockTrace/pathout hierarchy.
trace | is the indicated BlockTrace to remove |
References ghidra::TraceDAG::BlockTrace::bottom, ghidra::TraceDAG::BlockTrace::derivedbp, ghidra::TraceDAG::BlockTrace::destnode, ghidra::TraceDAG::BlockTrace::edgelump, ghidra::TraceDAG::BlockTrace::flags, ghidra::FloatingEdge::FloatingEdge(), ghidra::FlowBlock::getVisitCount(), ghidra::TraceDAG::BranchPoint::pathout, ghidra::TraceDAG::BlockTrace::pathout, ghidra::TraceDAG::BranchPoint::paths, ghidra::FlowBlock::setVisitCount(), ghidra::TraceDAG::BranchPoint::top, and ghidra::TraceDAG::BlockTrace::top.
Referenced by pushBranches().
|
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.
bp | is the given BranchPoint |
exitblock | is unique exit FlowBlock (calculated by checkRetirement()) |
References ghidra::TraceDAG::BlockTrace::activeiter, ghidra::TraceDAG::BlockTrace::bottom, ghidra::TraceDAG::BranchPoint::depth, ghidra::TraceDAG::BlockTrace::derivedbp, ghidra::TraceDAG::BlockTrace::destnode, ghidra::TraceDAG::BlockTrace::edgelump, ghidra::TraceDAG::BlockTrace::flags, ghidra::TraceDAG::BlockTrace::isTerminal(), ghidra::TraceDAG::BranchPoint::parent, ghidra::TraceDAG::BranchPoint::pathout, and ghidra::TraceDAG::BranchPoint::paths.
Referenced by pushBranches().
|
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.
References ghidra::TraceDAG::BadEdgeScore::exitproto, and ghidra::TraceDAG::BadEdgeScore::trace.
Referenced by pushBranches().