decompiler
1.0.0
|
A description of the body of a loop. More...
#include <blockaction.hh>
Public Member Functions | |
LoopBody (FlowBlock *h) | |
Construct with a loop head. | |
FlowBlock * | getHead (void) const |
Return the head FlowBlock of the loop. | |
FlowBlock * | getCurrentBounds (FlowBlock **top, FlowBlock *graph) |
Return current loop bounds (head and bottom). More... | |
void | addTail (FlowBlock *bl) |
Add a tail to the loop. | |
FlowBlock * | getExitBlock (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 LoopBody * | find (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 | |
FlowBlock * | head |
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. | |
FlowBlock * | exitblock |
Official exit block from loop, or NULL. | |
list< FloatingEdge > | exitedges |
Edges that exit to the formal exit block. | |
LoopBody * | immed_container |
Immediately containing loop body, or NULL. | |
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.
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.
graph | is the containing control-flow structure |
References ghidra::FlowBlock::clearLoopExit().
|
static |
Clear the body marks.
body | is the list of FlowBlock nodes that have been marked |
Referenced by ghidra::CollapseStructure::clipExtraRoots(), and ghidra::CollapseStructure::orderLoopBodies().
Compare the head then tail.
Compare two loops based on the indices of the head and then the tail.
References ghidra::FlowBlock::getIndex(), head, and tails.
Referenced by ghidra::CollapseStructure::labelLoops().
Compare just the head.
Compare two loops based on the indices of the head
a | is the first LoopBody to compare |
looptop | is the second |
References ghidra::FlowBlock::getIndex(), and head.
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.
likely | will hold the exit edges in (reverse) priority order |
graph | is the containing control-flow graph |
References ghidra::FloatingEdge::FloatingEdge(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::getParent(), and ghidra::FlowBlock::sizeOut().
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.
body | contains 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().
|
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.
container | is a loop that contains this |
body | will 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.
|
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.
looptop | is the top of the loop |
looporder | is the ordered list of LoopBody records |
Referenced by labelContainments().
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.
body | will contain the body nodes |
References ghidra::FlowBlock::getIn(), ghidra::FlowBlock::isGotoIn(), ghidra::FlowBlock::isMark(), ghidra::FlowBlock::setMark(), and ghidra::FlowBlock::sizeIn().
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.
body | is 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().
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.
top | is where head is passed back |
graph | is the containing control-flow structure |
References ghidra::FloatingEdge::bottom, and ghidra::FlowBlock::getParent().
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.
body | is the set of FlowBlock nodes making up this loop |
looporder | is the list of known loops |
References depth, find(), and immed_container.
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.
body | is list of nodes in this loop body |
References ghidra::FloatingEdge::FloatingEdge(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isGotoOut(), ghidra::FlowBlock::isMark(), and ghidra::FlowBlock::sizeOut().
|
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.
looporder | is the list of LoopBody records |
References addTail(), head, and tails.
Referenced by ghidra::CollapseStructure::orderLoopBodies().
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().
void ghidra::LoopBody::setExitMarks | ( | FlowBlock * | graph | ) |
Mark all the exits to this loop.
Exit edges have their f_loop_exit_edge property set.
graph | is the containing control-flow structure |
References ghidra::FlowBlock::setLoopExit().