|
Ghidra Decompiler Analysis Engine
|
Manage the construction of Static Single Assignment (SSA) form. More...
#include <heritage.hh>
Public Member Functions | |
| Heritage (Funcdata *data) | |
| Constructor. More... | |
| int4 | heritagePass (const Address &addr) const |
| Get the pass number when the given address was heritaged. More... | |
| int4 | numHeritagePasses (AddrSpace *spc) const |
| Get the number times heritage was performed for the given address space. More... | |
| void | seenDeadCode (AddrSpace *spc) |
| Inform system of dead code removal in given space. More... | |
| int4 | getDeadCodeDelay (AddrSpace *spc) const |
| Get pass delay for heritaging the given space. More... | |
| void | setDeadCodeDelay (AddrSpace *spc, int4 delay) |
| Set delay for a specific space. More... | |
| bool | deadRemovalAllowed (AddrSpace *spc) const |
| Return true if it is safe to remove dead code. More... | |
| bool | deadRemovalAllowedSeen (AddrSpace *spc) |
| Check if dead code removal is safe and mark that removal has happened. More... | |
| void | buildInfoList (void) |
| Initialize information for each space. More... | |
| void | clear (void) |
| Reset all analysis of heritage. More... | |
| void | heritage (void) |
| Perform one pass of heritage. More... | |
| const LoadGuard * | getStoreGuard (PcodeOp *op) const |
| Get LoadGuard record associated with given PcodeOp. More... | |
Manage the construction of Static Single Assignment (SSA) form.
With a specific function (Funcdata), this class links the Varnode and PcodeOp objects into the formal data-flow graph structure, SSA form. The full structure can be built over multiple passes. In particular, this allows register data-flow to be analyzed first, and then stack locations can be discovered and promoted to first-class Varnodes in a second pass.
Varnodes for which it is not known whether they are written to by a PcodeOp are referred to as free. The method heritage() performs a single pass of constructing SSA form, collecting any eligible free Varnodes for the pass and linking them in to the data-flow. A Varnode is considered eligible for a given pass generally based on its address space (see HeritageInfo), which is the main method for delaying linking for stack locations until they are all discovered. In principle a Varnode can be discovered very late and still get linked in on a subsequent pass. Linking causes Varnodes to gain new descendant PcodeOps, which has impact on dead code elimination (see LocationMap).
The two big aspects of SSA construction are phi-node placement, performed by placeMultiequals(), and the renaming algorithm, performed by rename(). The various guard* methods are concerned with labeling analyzing data-flow across function calls, STORE, and LOAD operations.
The phi-node placement algorithm is from (preprint?) "The Static Single Assignment Form and its Computation" by Gianfranco Bilardi and Keshav Pingali, July 22, 1999
The renaming algorithm taken from "Efficiently computing static single assignment form and the control dependence graph." R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck ACM Transactions on Programming Languages and Systems, 13(4):451-490, October 1991
| Heritage::Heritage | ( | Funcdata * | data | ) |
Instantiate the heritage manager for a particular function.
| data | is the function |
| void Heritage::buildInfoList | ( | void | ) |
Initialize information for each space.
This is called once to initialize this class in preparation for doing the heritage passes. An information structure is allocated and mapped to each address space.
| void Heritage::clear | ( | void | ) |
Reset all analysis of heritage.
Reset all analysis as if no heritage passes have yet taken place for the function. This does not directly affect Varnodes and PcodeOps in the underlying Funcdata.
| bool Heritage::deadRemovalAllowed | ( | AddrSpace * | spc | ) | const |
Return true if it is safe to remove dead code.
Check if the required number of passes have transpired to allow removal of dead Varnodes in the given address space. If allowed, presumably no new Varnodes will be generated for the space.
| spc | is the given address space |
| bool Heritage::deadRemovalAllowedSeen | ( | AddrSpace * | spc | ) |
Check if dead code removal is safe and mark that removal has happened.
A convenience function combining deadRemovalAllowed() and seenDeadCode(). Return true if it is safe to remove dead code, and, if so, also inform the system that dead code has happened for the given space.
| spc | is the given address space |
| int4 Heritage::getDeadCodeDelay | ( | AddrSpace * | spc | ) | const |
Get pass delay for heritaging the given space.
Linking in Varnodes can be delayed for specific address spaces (to make sure all Varnodes for the space have been generated. Return the number of passes to delay for the given space. 0 means no delay.
| spc | is the given address space |
| void Heritage::heritage | ( | void | ) |
Perform one pass of heritage.
From any address space that is active for this pass, free Varnodes are collected and then fully integrated into SSA form. Reads are connected to writes, inputs are identified, and phi-nodes are placed.
|
inline |
Get the pass number when the given address was heritaged.
| addr | is the given address |
| int4 Heritage::numHeritagePasses | ( | AddrSpace * | spc | ) | const |
Get the number times heritage was performed for the given address space.
A negative number indicates the number of passes to wait before the first heritage will occur.
| spc | is the given address space |
| void Heritage::seenDeadCode | ( | AddrSpace * | spc | ) |
Inform system of dead code removal in given space.
Record that Varnodes have been removed from the given space so that we can tell if there is any new heritage after the dead code removal.
| spc | is the given address space |
| void Heritage::setDeadCodeDelay | ( | AddrSpace * | spc, |
| int4 | delay | ||
| ) |
Set delay for a specific space.
Set the number of heritage passes that are skipped before allowing dead code removal for Varnodes in the given address space (to make sure all Varnodes have been linked in before deciding what is dead).
| spc | is the given address space |
| delay | is the number of passes to delay |
1.8.17