|
Ghidra Decompiler Analysis Engine
|
Algorithm for selecting unstructured edges based an Directed Acyclic Graphs (DAG) More...
#include <blockaction.hh>
Public Member Functions | |
| TraceDAG (list< FloatingEdge > &lg) | |
| Clear the visitcount field of any FlowBlock we have modified. More... | |
| ~TraceDAG (void) | |
| Destructor. | |
| void | initialize (void) |
| Create the initial BranchPoint and BlockTrace objects. More... | |
| void | pushBranches (void) |
| Push the trace through, removing edges as necessary. More... | |
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().
| 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 |
| 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.
| 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.
1.8.17