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

Manage the construction of Static Single Assignment (SSA) form. More...

#include <heritage.hh>

Classes

struct  StackNode
 Node for depth-first traversal of stack references. More...
 

Public Member Functions

 Heritage (Funcdata *data)
 Constructor. More...
 
int4 getPass (void) const
 Get overall count of heritage passes.
 
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 forceRestructure (void)
 Force regeneration of basic block structures.
 
void clear (void)
 Reset all analysis of heritage. More...
 
void heritage (void)
 Perform one pass of heritage. More...
 
const list< LoadGuard > & getLoadGuards (void) const
 Get list of LOAD ops that are guarded.
 
const list< LoadGuard > & getStoreGuards (void) const
 Get list of STORE ops that are guarded.
 
const LoadGuardgetStoreGuard (PcodeOp *op) const
 Get LoadGuard record associated with given PcodeOp. More...
 

Private Types

enum  heritage_flags { boundary_node = 1, mark_node = 2, merged_node = 4 }
 Extra boolean properties on basic blocks for the Augmented Dominator Tree. More...
 

Private Member Functions

void clearInfoList (void)
 Reset heritage status for all address spaces.
 
HeritageInfogetInfo (AddrSpace *spc)
 Get the heritage status for the given address space.
 
const HeritageInfogetInfo (AddrSpace *spc) const
 Get the heritage status for the given address space.
 
void clearStackPlaceholders (HeritageInfo *info)
 Clear remaining stack placeholder LOADs on any call. More...
 
void splitJoinLevel (vector< Varnode *> &lastcombo, vector< Varnode *> &nextlev, JoinRecord *joinrec)
 Perform one level of Varnode splitting to match a JoinRecord. More...
 
void splitJoinRead (Varnode *vn, JoinRecord *joinrec)
 Construct pieces for a join-space Varnode read by an operation. More...
 
void splitJoinWrite (Varnode *vn, JoinRecord *joinrec)
 Split a written join-space Varnode into specified pieces. More...
 
void floatExtensionRead (Varnode *vn, JoinRecord *joinrec)
 Create float truncation into a free lower precision join-space Varnode. More...
 
void floatExtensionWrite (Varnode *vn, JoinRecord *joinrec)
 Create float extension from a lower precision join-space Varnode. More...
 
void processJoins (void)
 Split join-space Varnodes up into their real components. More...
 
void buildADT (void)
 Build the augmented dominator tree. More...
 
void removeRevisitedMarkers (const vector< Varnode *> &remove, const Address &addr, int4 size)
 Remove deprecated CPUI_MULTIEQUAL or CPUI_INDIRECT ops, preparing to re-heritage. More...
 
int4 collect (Address addr, int4 size, vector< Varnode *> &read, vector< Varnode *> &write, vector< Varnode *> &input, vector< Varnode *> &remove) const
 Collect free reads, writes, and inputs in the given address range. More...
 
bool callOpIndirectEffect (const Address &addr, int4 size, PcodeOp *op) const
 Determine if the address range is affected by the given call p-code op. More...
 
VarnodenormalizeReadSize (Varnode *vn, const Address &addr, int4 size)
 Normalize the size of a read Varnode, prior to heritage. More...
 
VarnodenormalizeWriteSize (Varnode *vn, const Address &addr, int4 size)
 Normalize the size of a written Varnode, prior to heritage. More...
 
VarnodeconcatPieces (const vector< Varnode *> &vnlist, PcodeOp *insertop, Varnode *finalvn)
 Concatenate a list of Varnodes together at the given location. More...
 
void splitPieces (const vector< Varnode *> &vnlist, PcodeOp *insertop, const Address &addr, int4 size, Varnode *startvn)
 Build a set of Varnode piece expression at the given location. More...
 
void findAddressForces (vector< PcodeOp *> &copySinks, vector< PcodeOp *> &forces)
 Find the last PcodeOps that write to specific addresses that flow to specific sites. More...
 
void propagateCopyAway (PcodeOp *op)
 Eliminate a COPY sink preserving its data-flow. More...
 
void handleNewLoadCopies (void)
 Mark the boundary of artificial ops introduced by load guards. More...
 
void analyzeNewLoadGuards (void)
 Make final determination of what range new LoadGuards are protecting. More...
 
void generateLoadGuard (StackNode &node, PcodeOp *op, AddrSpace *spc)
 Generate a guard record given an indexed LOAD into a stack space. More...
 
void generateStoreGuard (StackNode &node, PcodeOp *op, AddrSpace *spc)
 Generate a guard record given an indexed STORE to a stack space. More...
 
bool protectFreeStores (AddrSpace *spc, vector< PcodeOp *> &freeStores)
 Identify any CPUI_STORE ops that use a free pointer from a given address space. More...
 
bool discoverIndexedStackPointers (AddrSpace *spc, vector< PcodeOp *> &freeStores, bool checkFreeStores)
 Trace input stack-pointer to any indexed loads. More...
 
void reprocessFreeStores (AddrSpace *spc, vector< PcodeOp *> &freeStores)
 Revisit STOREs with free pointers now that a heritage pass has completed. More...
 
void guard (const Address &addr, int4 size, bool guardPerformed, vector< Varnode *> &read, vector< Varnode *> &write, vector< Varnode *> &inputvars)
 Normalize p-code ops so that phi-node placement and renaming works. More...
 
void guardInput (const Address &addr, int4 size, vector< Varnode *> &input)
 Make sure existing inputs for the given range fill it entirely. More...
 
void guardCallOverlappingInput (FuncCallSpecs *fc, const Address &addr, const Address &transAddr, int4 size)
 Guard an address range that is larger than any single parameter. More...
 
bool guardCallOverlappingOutput (FuncCallSpecs *fc, const Address &addr, int4 size, vector< Varnode *> &write)
 Guard an address range that is larger than the possible output storage. More...
 
void guardCalls (uint4 fl, const Address &addr, int4 size, vector< Varnode *> &write)
 Guard CALL/CALLIND ops in preparation for renaming algorithm. More...
 
void guardStores (const Address &addr, int4 size, vector< Varnode *> &write)
 Guard STORE ops in preparation for the renaming algorithm. More...
 
void guardLoads (uint4 fl, const Address &addr, int4 size, vector< Varnode *> &write)
 Guard LOAD ops in preparation for the renaming algorithm. More...
 
void guardReturnsOverlapping (const Address &addr, int4 size)
 Guard data-flow at RETURN ops, where range properly contains potention return storage. More...
 
void guardReturns (uint4 fl, const Address &addr, int4 size, vector< Varnode *> &write)
 Guard global data-flow at RETURN ops in preparation for renaming. More...
 
void splitByRefinement (Varnode *vn, const Address &addr, const vector< int4 > &refine, vector< Varnode *> &split)
 Split up a Varnode by the given refinement. More...
 
void refineRead (Varnode *vn, const Address &addr, const vector< int4 > &refine, vector< Varnode *> &newvn)
 Split up a free Varnode based on the given refinement. More...
 
void refineWrite (Varnode *vn, const Address &addr, const vector< int4 > &refine, vector< Varnode *> &newvn)
 Split up an output Varnode based on the given refinement. More...
 
void refineInput (Varnode *vn, const Address &addr, const vector< int4 > &refine, vector< Varnode *> &newvn)
 Split up a known input Varnode based on the given refinement. More...
 
void remove13Refinement (vector< int4 > &refine)
 If we see 1-3 or 3-1 pieces in the partition, replace with a 4. More...
 
bool refinement (const Address &addr, int4 size, const vector< Varnode *> &readvars, const vector< Varnode *> &writevars, const vector< Varnode *> &inputvars)
 Find the common refinement of all reads and writes in the address range. More...
 
void visitIncr (FlowBlock *qnode, FlowBlock *vnode)
 The heart of the phi-node placement algorithm. More...
 
void calcMultiequals (const vector< Varnode *> &write)
 Calculate blocks that should contain MULTIEQUALs for one address range. More...
 
void renameRecurse (BlockBasic *bl, VariableStack &varstack)
 The heart of the renaming algorithm. More...
 
void bumpDeadcodeDelay (AddrSpace *spc)
 Increase the heritage delay for the given AddrSpace and request a restart. More...
 
void placeMultiequals (void)
 Perform phi-node placement for the current set of address ranges. More...
 
void rename (void)
 Perform the renaming algorithm for the current set of address ranges. More...
 

Static Private Member Functions

static void buildRefinement (vector< int4 > &refine, const Address &addr, int4 size, const vector< Varnode *> &vnlist)
 Build a refinement array given an address range and a list of Varnodes. More...
 

Private Attributes

Funcdatafd
 The function this is controlling SSA construction.
 
LocationMap globaldisjoint
 Disjoint cover of every heritaged memory location.
 
LocationMap disjoint
 Disjoint cover of memory locations currently being heritaged.
 
vector< vector< FlowBlock * > > domchild
 Parent->child edges in dominator tree.
 
vector< vector< FlowBlock * > > augment
 Augmented edges.
 
vector< uint4 > flags
 Block properties for phi-node placement algorithm.
 
vector< int4 > depth
 Dominator depth of individual blocks.
 
int4 maxdepth
 Maximum depth of the dominator tree.
 
int4 pass
 Current pass being executed.
 
PriorityQueue pq
 Priority queue for phi-node placement.
 
vector< FlowBlock * > merge
 Calculate merge points (blocks containing phi-nodes)
 
vector< HeritageInfoinfolist
 Heritage status for individual address spaces.
 
list< LoadGuardloadGuard
 List of LOAD operations that need to be guarded.
 
list< LoadGuardstoreGuard
 List of STORE operations taking an indexed pointer to the stack.
 
vector< PcodeOp * > loadCopyOps
 List of COPY ops generated by load guards.
 

Detailed Description

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

Member Enumeration Documentation

◆ heritage_flags

Extra boolean properties on basic blocks for the Augmented Dominator Tree.

Enumerator
boundary_node 

Augmented Dominator Tree boundary node.

mark_node 

Node has already been in queue.

merged_node 

Node has already been merged.

Constructor & Destructor Documentation

◆ Heritage()

ghidra::Heritage::Heritage ( Funcdata data)

Constructor.

Instantiate the heritage manager for a particular function.

Parameters
datais the function

Member Function Documentation

◆ analyzeNewLoadGuards()

void ghidra::Heritage::analyzeNewLoadGuards ( void  )
private

Make final determination of what range new LoadGuards are protecting.

Actual LOAD operations are guarded with an initial version of the LoadGuard record. Now that heritage has completed, a full analysis of each LOAD is conducted, using value set analysis, to reach a conclusion about what range of stack values the LOAD might actually alias. All new LoadGuard records are updated with the analysis, which then informs handling of LOAD COPYs and possible later heritage passes.

References ghidra::LoadGuard::analysisState, ghidra::LoadGuard::establishRange(), ghidra::ValueSetSolver::establishValueSets(), ghidra::LoadGuard::finalizeRange(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getSeqNum(), ghidra::ValueSetSolver::getValueSetRead(), ghidra::AddrSpace::numSpacebase(), ghidra::LoadGuard::op, and ghidra::ValueSetSolver::solve().

◆ buildADT()

void ghidra::Heritage::buildADT ( void  )
private

Build the augmented dominator tree.

Assume the dominator tree is already built. Assume nodes are in dfs order.

References ghidra::FlowBlock::getImmedDom(), ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getIndex(), ghidra::BlockGraph::getSize(), and ghidra::FlowBlock::sizeIn().

◆ buildInfoList()

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

References ghidra::AddrSpaceManager::getSpace(), and ghidra::AddrSpaceManager::numSpaces().

Referenced by ghidra::Funcdata::startProcessing().

◆ buildRefinement()

void ghidra::Heritage::buildRefinement ( vector< int4 > &  refine,
const Address addr,
int4  size,
const vector< Varnode *> &  vnlist 
)
staticprivate

Build a refinement array given an address range and a list of Varnodes.

The array is a preallocated array of ints, one for each byte in the address range. Each Varnode in the given list has a 1 entered in the refinement array, at the position corresponding to the starting address of the Varnode and at the position corresponding to the address immediately following the Varnode.

Parameters
refineis the refinement array
addris the starting address of the given range
sizeis the number of bytes in the range
vnlistis the list of Varnodes to add to the array

References ghidra::Address::getOffset().

◆ bumpDeadcodeDelay()

void ghidra::Heritage::bumpDeadcodeDelay ( AddrSpace spc)
private

Increase the heritage delay for the given AddrSpace and request a restart.

If applicable, look up the heritage stats for the address space and increment the delay. The address space must allow an additional delay and can only be incremented once. If the increment succeeds, the function is marked as having a restart pending.

Parameters
spcis the given AddrSpace

References ghidra::AddrSpace::getDeadcodeDelay(), ghidra::AddrSpace::getDelay(), ghidra::AddrSpace::getType(), ghidra::IPTR_PROCESSOR, and ghidra::IPTR_SPACEBASE.

◆ calcMultiequals()

void ghidra::Heritage::calcMultiequals ( const vector< Varnode *> &  write)
private

Calculate blocks that should contain MULTIEQUALs for one address range.

This is the main entry point for the phi-node placement algorithm. It is provided the normalized list of written Varnodes in this range. All refinement and guarding must already be performed for the Varnodes, and the dominance tree and its augmentation must already be computed. After this executes, the merge array holds blocks that should contain a MULTIEQUAL.

Parameters
writeis the list of written Varnodes

References ghidra::FlowBlock::getIndex().

◆ callOpIndirectEffect()

bool ghidra::Heritage::callOpIndirectEffect ( const Address addr,
int4  size,
PcodeOp op 
) const
private

Determine if the address range is affected by the given call p-code op.

We assume the op is CALL, CALLIND, CALLOTHER, or NEW and that its output overlaps the given address range. We look up any effect the op might have on the address range.

Parameters
addris the starting address of the range
sizeis the number of bytes in the range
opis the given call p-code op
Returns
true, unless the range is unaffected by the op

References ghidra::PcodeOp::code(), ghidra::CPUI_CALL, ghidra::CPUI_CALLIND, ghidra::FuncCallSpecs::hasEffectTranslate(), and ghidra::EffectRecord::unaffected.

◆ clear()

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

Referenced by ghidra::Funcdata::clear().

◆ clearStackPlaceholders()

void ghidra::Heritage::clearStackPlaceholders ( HeritageInfo info)
private

Clear remaining stack placeholder LOADs on any call.

Assuming we are just about to do heritage on an address space, clear any placeholder LOADs associated with it on CALLs.

Parameters
infois state for the specific address space

References ghidra::HeritageInfo::hasCallPlaceholders.

◆ collect()

int4 ghidra::Heritage::collect ( Address  addr,
int4  size,
vector< Varnode *> &  read,
vector< Varnode *> &  write,
vector< Varnode *> &  input,
vector< Varnode *> &  remove 
) const
private

Collect free reads, writes, and inputs in the given address range.

Parameters
addris the starting address of the range
sizeis the number of bytes in the range
readwill hold any read Varnodes in the range
writewill hold any written Varnodes
inputwill hold any input Varnodes
removewill hold any PcodeOps that need to be removed
Returns
the maximum size of a write

References ghidra::Varnode::getDef(), ghidra::AddrSpace::getHighest(), ghidra::Address::getOffset(), ghidra::Varnode::getSize(), ghidra::Address::getSpace(), ghidra::Varnode::hasNoDescend(), ghidra::Varnode::isHeritageKnown(), ghidra::Varnode::isInput(), ghidra::PcodeOp::isMarker(), ghidra::Varnode::isWriteMask(), and ghidra::Varnode::isWritten().

◆ concatPieces()

Varnode * ghidra::Heritage::concatPieces ( const vector< Varnode *> &  vnlist,
PcodeOp insertop,
Varnode finalvn 
)
private

Concatenate a list of Varnodes together at the given location.

There must be at least 2 Varnodes in list, they must be in order from most to least significant. The Varnodes in the list become inputs to a single expression of PIECE ops resulting in a final specified Varnode

Parameters
vnlistis the list of Varnodes to concatenate
insertopis the point where the expression should be inserted (before)
finalvnis the final specified output Varnode of the expression
Returns
the final unified Varnode

References ghidra::BlockBasic::beginOp(), ghidra::CPUI_PIECE, ghidra::PcodeOp::getAddr(), ghidra::Varnode::getAddr(), ghidra::PcodeOp::getBasicIter(), ghidra::PcodeOp::getParent(), ghidra::Varnode::getSize(), and ghidra::Address::isBigEndian().

◆ deadRemovalAllowed()

bool ghidra::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.

Parameters
spcis the given address space
Returns
true if dead code removal is allowed

References ghidra::HeritageInfo::deadcodedelay.

Referenced by ghidra::Funcdata::deadRemovalAllowed().

◆ deadRemovalAllowedSeen()

bool ghidra::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.

Parameters
spcis the given address space
Returns
true if dead code removal is allowed

References ghidra::HeritageInfo::deadcodedelay, and ghidra::HeritageInfo::deadremoved.

Referenced by ghidra::Funcdata::deadRemovalAllowedSeen().

◆ discoverIndexedStackPointers()

bool ghidra::Heritage::discoverIndexedStackPointers ( AddrSpace spc,
vector< PcodeOp *> &  freeStores,
bool  checkFreeStores 
)
private

Trace input stack-pointer to any indexed loads.

Look for expressions of the form val = *(SP(i) + vn + #c), where the base stack pointer has an (optional) constant added to it and a non-constant index, then a value is loaded from the resulting address. The LOAD operations are added to the list of ops that potentially need to be guarded during a heritage pass. The routine can checks for STOREs where the data-flow path hasn't been completed yet and returns true if they exist, passing back a list of those that might use a pointer to the stack.

Parameters
spcis the particular address space with a stackpointer (into it)
freeStoreswill hold the list of any STOREs that need follow-up analysis
checkFreeStoresis true if the routine should check for free STOREs
Returns
true if there are incomplete STOREs

References ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_INDIRECT, ghidra::CPUI_INT_ADD, ghidra::CPUI_LOAD, ghidra::CPUI_MULTIEQUAL, ghidra::CPUI_SEGMENTOP, ghidra::CPUI_STORE, ghidra::Varnode::endDescend(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getOffset(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::getSlot(), ghidra::Varnode::getSpace(), ghidra::AddrSpace::getSpacebase(), ghidra::AddrSpace::getType(), ghidra::IPTR_SPACEBASE, ghidra::Varnode::isConstant(), ghidra::Varnode::isMark(), ghidra::Heritage::StackNode::iter, ghidra::AddrSpace::numSpacebase(), ghidra::Varnode::setMark(), ghidra::Heritage::StackNode::vn, and ghidra::AddrSpace::wrapOffset().

◆ findAddressForces()

void ghidra::Heritage::findAddressForces ( vector< PcodeOp *> &  copySinks,
vector< PcodeOp *> &  forces 
)
private

Find the last PcodeOps that write to specific addresses that flow to specific sites.

Given a set of sites for which data-flow needs to be preserved at a specific address, find the last ops that write to the address such that data flows to the site only through artificial COPYs and MULTIEQUALs. A COPY/MULTIEQUAL is artificial if all of its input and output Varnodes have the same storage address. The specific sites are presented as artificial COPY ops. The final set of ops that are not artificial will all have an output Varnode that matches the specific address of a COPY sink and will need to be marked address forcing. The original set of COPY sinks will be extended to all artificial COPY/MULTIEQUALs encountered. Every PcodeOp encountered will have its mark set.

Parameters
copySinksis the list of sinks that we are trying to find flow to
forcesis the final list of address forcing PcodeOps

References ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_INDIRECT, ghidra::CPUI_MULTIEQUAL, ghidra::Varnode::getAddr(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOut(), ghidra::Varnode::isAddrForce(), ghidra::PcodeOp::isIndirectStore(), ghidra::PcodeOp::isMark(), ghidra::Varnode::isWritten(), ghidra::PcodeOp::numInput(), and ghidra::PcodeOp::setMark().

◆ floatExtensionRead()

void ghidra::Heritage::floatExtensionRead ( Varnode vn,
JoinRecord joinrec 
)
private

Create float truncation into a free lower precision join-space Varnode.

Given a Varnode with logically lower precision, as given by a float extension record (JoinRecord), create the real full-precision Varnode and define the lower precision Varnode as a truncation (FLOAT2FLOAT)

Parameters
vnis the lower precision join-space input Varnode
joinrecis the float extension record

References ghidra::CPUI_FLOAT_FLOAT2FLOAT, ghidra::PcodeOp::getAddr(), ghidra::JoinRecord::getPiece(), and ghidra::Varnode::loneDescend().

◆ floatExtensionWrite()

void ghidra::Heritage::floatExtensionWrite ( Varnode vn,
JoinRecord joinrec 
)
private

Create float extension from a lower precision join-space Varnode.

Given a Varnode with logically lower precision, as given by a float extension record (JoinRecord), create the full precision Varnode specified by the record, making it defined by an extension (FLOAT2FLOAT).

Parameters
vnis the lower precision join-space output Varnode
joinrecis the float extension record

References ghidra::CPUI_FLOAT_FLOAT2FLOAT, ghidra::PcodeOp::getAddr(), ghidra::Varnode::getDef(), ghidra::JoinRecord::getPiece(), ghidra::BlockBasic::getStart(), and ghidra::Varnode::isInput().

◆ generateLoadGuard()

void ghidra::Heritage::generateLoadGuard ( StackNode node,
PcodeOp op,
AddrSpace spc 
)
private

Generate a guard record given an indexed LOAD into a stack space.

Record the LOAD op and the (likely) range of addresses in the stack space that might be loaded from.

Parameters
nodeis the path element containing the constructed Address
opis the LOAD PcodeOp
spcis the stack space

References ghidra::Heritage::StackNode::offset, and ghidra::PcodeOp::usesSpacebasePtr().

◆ generateStoreGuard()

void ghidra::Heritage::generateStoreGuard ( StackNode node,
PcodeOp op,
AddrSpace spc 
)
private

Generate a guard record given an indexed STORE to a stack space.

Record the STORE op and the (likely) range of addresses in the stack space that might be stored to.

Parameters
nodeis the path element containing the constructed Address
opis the STORE PcodeOp
spcis the stack space

References ghidra::Heritage::StackNode::offset, and ghidra::PcodeOp::usesSpacebasePtr().

◆ getDeadCodeDelay()

int4 ghidra::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.

Parameters
spcis the given address space
Returns
the number of passes heritage is delayed

References ghidra::HeritageInfo::deadcodedelay.

◆ getStoreGuard()

const LoadGuard * ghidra::Heritage::getStoreGuard ( PcodeOp op) const

Get LoadGuard record associated with given PcodeOp.

Parameters
opis the given PcodeOp
Returns
the associated LoadGuard or NULL

Referenced by ghidra::Funcdata::getStoreGuard().

◆ guard()

void ghidra::Heritage::guard ( const Address addr,
int4  size,
bool  guardPerformed,
vector< Varnode *> &  read,
vector< Varnode *> &  write,
vector< Varnode *> &  inputvars 
)
private

Normalize p-code ops so that phi-node placement and renaming works.

The traditional phi-node placement and renaming algorithms don't expect variable pairs where there is partial overlap. For the given address range, we make all the free Varnode sizes look uniform by adding PIECE and SUBPIECE ops. We also add INDIRECT ops, so that we can ignore indirect effects of LOAD/STORE/CALL ops.

Parameters
addris the starting address of the given range
sizeis the number of bytes in the given range
guardPerformedis true if a guard has been previously performed on the range
readis the set of Varnode values reading from the range
writeis the set of written Varnodes in the range
inputvarsis the set of Varnodes in the range already marked as input

References ghidra::Varnode::getSize(), and ghidra::Varnode::setActiveHeritage().

◆ guardCallOverlappingInput()

void ghidra::Heritage::guardCallOverlappingInput ( FuncCallSpecs fc,
const Address addr,
const Address transAddr,
int4  size 
)
private

Guard an address range that is larger than any single parameter.

In this situation, an address range is being heritaged, but only a piece of it can be a parameter for a given call. We have to construct a SUBPIECE that pulls out the potential parameter.

Parameters
fcis the call site potentially taking a parameter
addris the starting address of the range
transAddris the start of the same range from the callee's stack perspective
sizeis the size of the range in bytes

References ghidra::CPUI_SUBPIECE, ghidra::FuncCallSpecs::getActiveInput(), ghidra::PcodeOp::getAddr(), ghidra::FuncProto::getBiggestContainedInputParam(), ghidra::Address::getOffset(), ghidra::FuncCallSpecs::getOp(), ghidra::Address::justifiedContain(), ghidra::PcodeOp::numInput(), ghidra::VarnodeData::offset, ghidra::ParamActive::registerTrial(), ghidra::Varnode::setActiveHeritage(), ghidra::VarnodeData::size, ghidra::VarnodeData::space, and ghidra::ParamActive::whichTrial().

◆ guardCallOverlappingOutput()

bool ghidra::Heritage::guardCallOverlappingOutput ( FuncCallSpecs fc,
const Address addr,
int4  size,
vector< Varnode *> &  write 
)
private

Guard an address range that is larger than the possible output storage.

A potential return value should look like an indirect creation at this stage, but the range is even bigger. We split it up into 2 or 3 Varnodes, and make each one via an INDIRECT. The piece corresponding to the potential return value is registered, and all the pieces are concatenated to form a Varnode of the whole range.

Parameters
fcis the call site potentially returning a value
addris the starting address of the range
sizeis the size of the range in bytes
writeis the set of new written Varnodes
Returns
true if the INDIRECTs were created

References ghidra::CPUI_PIECE, ghidra::FuncCallSpecs::getActiveOutput(), ghidra::PcodeOp::getAddr(), ghidra::FuncProto::getBiggestContainedOutput(), ghidra::Address::getOffset(), ghidra::FuncCallSpecs::getOp(), ghidra::PcodeOp::getOut(), ghidra::AddrSpace::isBigEndian(), ghidra::VarnodeData::offset, ghidra::ParamActive::registerTrial(), ghidra::Varnode::setActiveHeritage(), ghidra::VarnodeData::size, ghidra::VarnodeData::space, and ghidra::ParamActive::whichTrial().

◆ guardCalls()

void ghidra::Heritage::guardCalls ( uint4  fl,
const Address addr,
int4  size,
vector< Varnode *> &  write 
)
private

Guard CALL/CALLIND ops in preparation for renaming algorithm.

For the given address range, we decide what the data-flow effect is across each call site in the function. If an effect is unknown, an INDIRECT op is added, prepopulating data-flow through the call. Any new INDIRECT causes a new Varnode to be added to the write list.

Parameters
flare any boolean properties associated with the address range
addris the first address of given range
sizeis the number of bytes in the range
writeis the list of written Varnodes in the range (may be updated)

References ghidra::Varnode::addrtied, ghidra::FuncProto::characterizeAsInputParam(), ghidra::FuncProto::characterizeAsOutput(), ghidra::ParamEntry::contained_by, ghidra::ParamEntry::contains_justified, ghidra::FuncCallSpecs::getActiveInput(), ghidra::FuncCallSpecs::getActiveOutput(), ghidra::Varnode::getAddr(), ghidra::PcodeOp::getIn(), ghidra::Address::getOffset(), ghidra::FuncCallSpecs::getOp(), ghidra::PcodeOp::getOut(), ghidra::Varnode::getSize(), ghidra::Address::getSpace(), ghidra::FuncCallSpecs::getSpacebaseOffset(), ghidra::AddrSpace::getType(), ghidra::FuncCallSpecs::hasEffectTranslate(), ghidra::IPTR_SPACEBASE, ghidra::PcodeOp::isAssignment(), ghidra::FuncCallSpecs::isInputActive(), ghidra::FuncCallSpecs::isOutputActive(), ghidra::EffectRecord::killedbycall, ghidra::ParamEntry::no_containment, ghidra::PcodeOp::numInput(), ghidra::FuncCallSpecs::offset_unknown, ghidra::ParamActive::registerTrial(), ghidra::EffectRecord::return_address, ghidra::Varnode::setActiveHeritage(), ghidra::Varnode::setAddrForce(), ghidra::Varnode::setReturnAddress(), ghidra::EffectRecord::unaffected, ghidra::EffectRecord::unknown_effect, ghidra::ParamActive::whichTrial(), and ghidra::AddrSpace::wrapOffset().

◆ guardInput()

void ghidra::Heritage::guardInput ( const Address addr,
int4  size,
vector< Varnode *> &  input 
)
private

Make sure existing inputs for the given range fill it entirely.

The method is provided any Varnodes that overlap the range and are already marked as input. If there are any holes in coverage, new input Varnodes are created to cover them. A final unified Varnode covering the whole range is built out of the pieces. In any event, things are set up so the renaming algorithm sees only a single Varnode.

Parameters
addris the first address in the given range
sizeis the number of bytes in the range
inputare the pre-existing inputs, given in address order

References ghidra::LocationMap::end(), ghidra::FlowBlock::getIndex(), ghidra::Address::getOffset(), ghidra::Varnode::getOffset(), ghidra::Varnode::getSize(), ghidra::Address::getSpace(), and ghidra::Varnode::setActiveHeritage().

◆ guardLoads()

void ghidra::Heritage::guardLoads ( uint4  fl,
const Address addr,
int4  size,
vector< Varnode *> &  write 
)
private

Guard LOAD ops in preparation for the renaming algorithm.

The op must be in the loadGuard list, which means it may pull values from an indexed range on the stack. A COPY guard is placed for the given range on any LOAD op whose indexed range it intersects.

Parameters
flis boolean properties associated with the address
addris the first address of the given range
sizeis the number of bytes in the given range
writeis the list of written Varnodes in the range (may be updated)

References ghidra::Varnode::addrtied, ghidra::CPUI_COPY, ghidra::CPUI_LOAD, ghidra::PcodeOp::getAddr(), ghidra::Address::getOffset(), ghidra::Address::getSpace(), ghidra::LoadGuard::isValid(), ghidra::LoadGuard::maximumOffset, ghidra::LoadGuard::minimumOffset, ghidra::LoadGuard::op, ghidra::Varnode::setActiveHeritage(), ghidra::Varnode::setAddrForce(), and ghidra::LoadGuard::spc.

◆ guardReturns()

void ghidra::Heritage::guardReturns ( uint4  fl,
const Address addr,
int4  size,
vector< Varnode *> &  write 
)
private

Guard global data-flow at RETURN ops in preparation for renaming.

For the given global (persistent) address range, data-flow must persist up to (beyond) the end of the function. This method prepopulates data-flow for the range at all the RETURN ops, in order to enforce this. Either a Varnode is added as input to the RETURN (for possible return values), or a COPY is inserted right before the RETURN with its output marked as address forced.

Parameters
flare any boolean properties associated with the address range
addris the first address of the given range
sizeis the number of bytes in the range
writeis the list of written Varnodes in the range (unused)

References ghidra::ParamEntry::contained_by, ghidra::CPUI_COPY, ghidra::CPUI_RETURN, ghidra::PcodeOp::getAddr(), ghidra::PcodeOp::getHaltType(), ghidra::PcodeOp::isDead(), ghidra::ParamEntry::no_containment, ghidra::PcodeOp::numInput(), ghidra::Varnode::persist, ghidra::ParamActive::registerTrial(), ghidra::Varnode::setActiveHeritage(), ghidra::Varnode::setAddrForce(), and ghidra::PcodeOp::setStopCopyPropagation().

◆ guardReturnsOverlapping()

void ghidra::Heritage::guardReturnsOverlapping ( const Address addr,
int4  size 
)
private

Guard data-flow at RETURN ops, where range properly contains potention return storage.

The RETURN ops need to take a new input because of the potential of a return value, but the range is too big so it must be truncated to fit.

Parameters
addris the starting address of the range
sizeis the size of the range in bytes

References ghidra::CPUI_RETURN, ghidra::CPUI_SUBPIECE, ghidra::PcodeOp::getAddr(), ghidra::PcodeOp::getHaltType(), ghidra::Address::getOffset(), ghidra::AddrSpace::isBigEndian(), ghidra::PcodeOp::isDead(), ghidra::PcodeOp::numInput(), ghidra::VarnodeData::offset, ghidra::ParamActive::registerTrial(), ghidra::Varnode::setActiveHeritage(), ghidra::VarnodeData::size, and ghidra::VarnodeData::space.

◆ guardStores()

void ghidra::Heritage::guardStores ( const Address addr,
int4  size,
vector< Varnode *> &  write 
)
private

Guard STORE ops in preparation for the renaming algorithm.

Depending on the pointer, a STORE operation may affect data-flow across the given address range. This method adds an INDIRECT op, prepopulating data-flow across the STORE. Any new INDIRECT causes a new Varnode to be added to the write list.

Parameters
addris the first address of the given range
sizeis the number of bytes in the given range
writeis the list of written Varnodes in the range (may be updated)

References ghidra::CPUI_STORE, ghidra::AddrSpace::getContain(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOut(), ghidra::Address::getSpace(), ghidra::Varnode::getSpaceFromConst(), ghidra::PcodeOp::indirect_store, ghidra::PcodeOp::isDead(), ghidra::Varnode::setActiveHeritage(), and ghidra::PcodeOp::usesSpacebasePtr().

◆ handleNewLoadCopies()

void ghidra::Heritage::handleNewLoadCopies ( void  )
private

Mark the boundary of artificial ops introduced by load guards.

Having just completed renaming, run through all new COPY sinks from load guards and mark boundary Varnodes (Varnodes whose data-flow along all paths traverses only COPY/INDIRECT/MULTIEQUAL ops and hits a load guard). This lets dead code removal run forward from the boundary while still preserving the address force on the load guard.

References ghidra::PcodeOp::clearMark(), ghidra::Varnode::getAddr(), ghidra::PcodeOp::getOut(), ghidra::RangeList::inRange(), ghidra::RangeList::insertRange(), ghidra::LoadGuard::maximumOffset, ghidra::LoadGuard::minimumOffset, ghidra::Varnode::setAddrForce(), and ghidra::LoadGuard::spc.

◆ heritage()

void ghidra::Heritage::heritage ( void  )

◆ heritagePass()

int4 ghidra::Heritage::heritagePass ( const Address addr) const
inline

Get the pass number when the given address was heritaged.

Parameters
addris the given address
Returns
the pass number or -1 if the address has not been heritaged

References ghidra::LocationMap::findPass().

Referenced by ghidra::Funcdata::isHeritaged().

◆ normalizeReadSize()

Varnode * ghidra::Heritage::normalizeReadSize ( Varnode vn,
const Address addr,
int4  size 
)
private

Normalize the size of a read Varnode, prior to heritage.

Given a Varnode being read that does not match the (larger) size of the address range currently being linked, create a Varnode of the correct size and define the original Varnode as a SUBPIECE.

Parameters
vnis the given too small Varnode
addris the start of the (larger) range
sizeis the number of bytes in the range
Returns
the new larger Varnode

References ghidra::Varnode::beginDescend(), ghidra::CPUI_SUBPIECE, ghidra::Varnode::endDescend(), ghidra::PcodeOp::getAddr(), ghidra::Address::getAddrSize(), ghidra::PcodeOp::getOut(), ghidra::Varnode::overlap(), and ghidra::Varnode::setWriteMask().

◆ normalizeWriteSize()

Varnode * ghidra::Heritage::normalizeWriteSize ( Varnode vn,
const Address addr,
int4  size 
)
private

Normalize the size of a written Varnode, prior to heritage.

Given a Varnode that is written that does not match the (larger) size of the address range currently being linked, create the missing pieces in the range and concatenate everything into a new Varnode of the correct size.

One or more Varnode pieces are created depending on how the original Varnode overlaps the given range. An expression is created using PIECE ops resulting in a final Varnode.

Parameters
vnis the given too small Varnode
addris the start of the (larger) range
sizeis the number of bytes in the range
Returns
the newly created final Varnode

References ghidra::CPUI_PIECE, ghidra::CPUI_SUBPIECE, ghidra::PcodeOp::getAddr(), ghidra::Varnode::getAddr(), ghidra::Address::getAddrSize(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getOut(), ghidra::Varnode::getSize(), ghidra::Address::isBigEndian(), ghidra::PcodeOp::isCall(), ghidra::Varnode::overlap(), ghidra::Varnode::setActiveHeritage(), and ghidra::Varnode::setWriteMask().

◆ numHeritagePasses()

int4 ghidra::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.

Parameters
spcis the given address space
Returns
the number of heritage passes performed

References ghidra::HeritageInfo::delay, and ghidra::HeritageInfo::isHeritaged().

Referenced by ghidra::Funcdata::numHeritagePasses().

◆ placeMultiequals()

void ghidra::Heritage::placeMultiequals ( void  )
private

Perform phi-node placement for the current set of address ranges.

Main entry point for performing the phi-node placement algorithm. Assume disjoint is filled with all the free Varnodes to be heritaged

References ghidra::CPUI_MULTIEQUAL, ghidra::Address::getSpace(), ghidra::BlockBasic::getStart(), ghidra::AddrSpace::getType(), ghidra::IPTR_INTERNAL, ghidra::Varnode::setActiveHeritage(), and ghidra::FlowBlock::sizeIn().

◆ processJoins()

void ghidra::Heritage::processJoins ( void  )
private

Split join-space Varnodes up into their real components.

For any Varnode in the join-space, look up its JoinRecord and split it up into the specified real components so that join-space addresses play no role in the heritage process, i.e. there should be no free Varnodes in the join-space.

References ghidra::HeritageInfo::delay, ghidra::Varnode::getOffset(), ghidra::JoinRecord::getPiece(), ghidra::Varnode::getSize(), ghidra::Varnode::getSpace(), ghidra::JoinRecord::getUnified(), ghidra::JoinRecord::isFloatExtension(), ghidra::Varnode::isFree(), ghidra::VarnodeData::size, and ghidra::VarnodeData::space.

◆ propagateCopyAway()

void ghidra::Heritage::propagateCopyAway ( PcodeOp op)
private

Eliminate a COPY sink preserving its data-flow.

Given a COPY from a storage location to itself, propagate the input Varnode version of the storage location to all the ops reading the output Varnode, so the output no longer has any descendants. Then eliminate the COPY.

Parameters
opis the given COPY sink

References ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::Varnode::getAddr(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOut(), and ghidra::Varnode::isWritten().

◆ protectFreeStores()

bool ghidra::Heritage::protectFreeStores ( AddrSpace spc,
vector< PcodeOp *> &  freeStores 
)
private

Identify any CPUI_STORE ops that use a free pointer from a given address space.

When performing heritage for stack Varnodes, data-flow around a STORE with a free pointer must be guarded (with an INDIRECT) to be safe. This routine collects and marks the STORE ops that trigger this guard.

Parameters
spcis the given address space
freeStoreswill hold the list of STOREs if any
Returns
true if there are any new STOREs needing a guard

References ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_INT_ADD, ghidra::CPUI_STORE, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getSpace(), ghidra::Varnode::isConstant(), ghidra::PcodeOp::isDead(), ghidra::Varnode::isFree(), and ghidra::Varnode::isWritten().

◆ refineInput()

void ghidra::Heritage::refineInput ( Varnode vn,
const Address addr,
const vector< int4 > &  refine,
vector< Varnode *> &  newvn 
)
private

Split up a known input Varnode based on the given refinement.

The refinement array is an array of integers, one for each byte in the given range. Any non-zero entry is the size of a particular element of the refinement starting at that corresponding byte in the range. I.e. the array [4,0,0,0,4,0,0,0] indicates the address range is 8-bytes long covered by two elements of length 4, starting at offsets 0 and 4 respectively.

If the Varnode overlaps the refinement, it is replaced with 2 or more covering Varnodes with boundaries that are on the refinement. These pieces may be supplemented with additional pieces to obtain a disjoint cover of the entire address range. A defining SUBPIECE op is generated for each piece.

Parameters
vnis the given Varnode to split
addris the starting address of the address range being refined
refineis the refinement array
newvnis preallocated space for the holding the array of Varnode pieces

References ghidra::Varnode::getAddr(), ghidra::Varnode::getSize(), and ghidra::Varnode::setWriteMask().

◆ refinement()

bool ghidra::Heritage::refinement ( const Address addr,
int4  size,
const vector< Varnode *> &  readvars,
const vector< Varnode *> &  writevars,
const vector< Varnode *> &  inputvars 
)
private

Find the common refinement of all reads and writes in the address range.

Split the reads and writes so they match the refinement.

Parameters
addris the first address in the range
sizeis the number of bytes in the range
readvarsis all free Varnodes overlapping the address range
writevarsis all written Varnodes overlapping the address range
inputvarsis all known input Varnodes overlapping the address range
Returns
true if there is a non-trivial refinement

◆ refineRead()

void ghidra::Heritage::refineRead ( Varnode vn,
const Address addr,
const vector< int4 > &  refine,
vector< Varnode *> &  newvn 
)
private

Split up a free Varnode based on the given refinement.

The refinement array is an array of integers, one for each byte in the given range. Any non-zero entry is the size of a particular element of the refinement starting at that corresponding byte in the range. I.e. the array [4,0,0,0,4,0,0,0] indicates the address range is 8-bytes long covered by two elements of length 4, starting at offsets 0 and 4 respectively.

If the Varnode overlaps the refinement, it is replaced with 2 or more covering Varnodes with boundaries that are on the refinement. A concatenation expression is formed reconstructing the original value from the pieces. The original Varnode is replaced, in its p-code op, with a temporary Varnode that is the final output of the concatenation expression.

Parameters
vnis the given Varnode to split
addris the starting address of the address range being refined
refineis the refinement array
newvnis preallocated space for the holding the array of Varnode pieces

References ghidra::Varnode::getSize(), ghidra::PcodeOp::getSlot(), ghidra::Varnode::hasNoDescend(), and ghidra::Varnode::loneDescend().

◆ refineWrite()

void ghidra::Heritage::refineWrite ( Varnode vn,
const Address addr,
const vector< int4 > &  refine,
vector< Varnode *> &  newvn 
)
private

Split up an output Varnode based on the given refinement.

The refinement array is an array of integers, one for each byte in the given range. Any non-zero entry is the size of a particular element of the refinement starting at that corresponding byte in the range. I.e. the array [4,0,0,0,4,0,0,0] indicates the address range is 8-bytes long covered by two elements of length 4, starting at offsets 0 and 4 respectively.

If the Varnode overlaps the refinement, it is replaced with 2 or more covering Varnodes with boundaries that are on the refinement. These pieces may be supplemented with additional pieces to obtain a disjoint cover of the entire address range. A defining SUBPIECE op is generated for each piece. The original Varnode is replaced with a temporary Varnode.

Parameters
vnis the given Varnode to split
addris the starting address of the address range being refined
refineis the refinement array
newvnis preallocated space for the holding the array of Varnode pieces

References ghidra::Varnode::getAddr(), ghidra::Varnode::getDef(), and ghidra::Varnode::getSize().

◆ remove13Refinement()

void ghidra::Heritage::remove13Refinement ( vector< int4 > &  refine)
private

If we see 1-3 or 3-1 pieces in the partition, replace with a 4.

A refinement of a 4-byte range into a 1-byte and 3-byte cover is highly likely to be artificial, so we eliminate this configuration.

The refinement array is an array of integers, one for each byte in the given range. Any non-zero entry is the size of a particular element of the refinement starting at that corresponding byte in the range. I.e. the array [4,0,0,0,4,0,0,0] indicates the address range is 8-bytes long covered by two elements of length 4, starting at offsets 0 and 4 respectively.

Parameters
refineis the refinement array

◆ removeRevisitedMarkers()

void ghidra::Heritage::removeRevisitedMarkers ( const vector< Varnode *> &  remove,
const Address addr,
int4  size 
)
private

Remove deprecated CPUI_MULTIEQUAL or CPUI_INDIRECT ops, preparing to re-heritage.

If a previous Varnode was heritaged through a MULTIEQUAL or INDIRECT op, but now a larger range containing the Varnode is being heritaged, we throw away the op, letting the data-flow for the new larger range determine the data-flow for the old Varnode. The original Varnode is redefined as the output of a SUBPIECE of a larger free Varnode.

Parameters
removeis the list of Varnodes written by MULTIEQUAL or INDIRECT
addris the start of the larger range
sizeis the size of the range

References ghidra::PcodeOp::code(), ghidra::CPUI_INDIRECT, ghidra::CPUI_MULTIEQUAL, ghidra::CPUI_SUBPIECE, ghidra::HeritageInfo::deadremoved, ghidra::BlockBasic::endOp(), ghidra::Varnode::getAddr(), ghidra::PcodeOp::getBasicIter(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOpFromConst(), ghidra::PcodeOp::getParent(), ghidra::Address::getSpace(), ghidra::PcodeOp::isDead(), ghidra::Varnode::overlap(), ghidra::Address::printRaw(), ghidra::Varnode::setActiveHeritage(), ghidra::Varnode::setWriteMask(), and ghidra::HeritageInfo::warningissued.

◆ rename()

void ghidra::Heritage::rename ( void  )
private

Perform the renaming algorithm for the current set of address ranges.

Phi-node placement must already have happened.

◆ renameRecurse()

void ghidra::Heritage::renameRecurse ( BlockBasic bl,
VariableStack varstack 
)
private

The heart of the renaming algorithm.

From the given block, recursively walk the dominance tree. At each block, visit the PcodeOps in execution order looking for Varnodes that need to be renamed. As write Varnodes are encountered, a set of stack containers, differentiated by the Varnode's address, are updated so the so the current active Varnode is always ready for any free Varnode that is encountered. In this was all free Varnodes are replaced with the appropriate write Varnode or are promoted to a formal input Varnode.

Parameters
blis the current basic block in the dominance tree walk
varstackis the system of stacks, organized by address

References ghidra::BlockBasic::beginOp(), ghidra::Varnode::clearActiveHeritage(), ghidra::PcodeOp::code(), ghidra::CPUI_INDIRECT, ghidra::CPUI_MULTIEQUAL, ghidra::BlockBasic::endOp(), ghidra::Varnode::getAddr(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::FlowBlock::getIndex(), ghidra::PcodeOp::getOpFromConst(), ghidra::PcodeOp::getOut(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::getOutRevIndex(), ghidra::Varnode::getSize(), ghidra::Varnode::hasNoDescend(), ghidra::Varnode::insert, ghidra::Varnode::isActiveHeritage(), ghidra::Varnode::isHeritageKnown(), ghidra::Varnode::isWritten(), ghidra::PcodeOp::numInput(), and ghidra::FlowBlock::sizeOut().

◆ reprocessFreeStores()

void ghidra::Heritage::reprocessFreeStores ( AddrSpace spc,
vector< PcodeOp *> &  freeStores 
)
private

Revisit STOREs with free pointers now that a heritage pass has completed.

We regenerate STORE LoadGuard records then cross-reference with STOREs that were originally free to see if they actually needed a LoadGaurd. If not, the STORE is unmarked and INDIRECTs it has caused are removed.

Parameters
spcis the address space being guarded
freeStoresis the list of STOREs that were marked as free

References ghidra::PcodeOp::code(), ghidra::CPUI_INDIRECT, ghidra::Varnode::getAddr(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOpFromConst(), ghidra::PcodeOp::getOut(), ghidra::Varnode::getSpace(), ghidra::AddrSpace::getType(), ghidra::IPTR_IOP, ghidra::PcodeOp::previousOp(), and ghidra::PcodeOp::usesSpacebasePtr().

◆ seenDeadCode()

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

Parameters
spcis the given address space

References ghidra::HeritageInfo::deadremoved.

Referenced by ghidra::Funcdata::seenDeadcode().

◆ setDeadCodeDelay()

void ghidra::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).

Parameters
spcis the given address space
delayis the number of passes to delay

References ghidra::HeritageInfo::deadcodedelay.

Referenced by ghidra::Funcdata::setDeadCodeDelay().

◆ splitByRefinement()

void ghidra::Heritage::splitByRefinement ( Varnode vn,
const Address addr,
const vector< int4 > &  refine,
vector< Varnode *> &  split 
)
private

Split up a Varnode by the given refinement.

The refinement array is an array of integers, one for each byte in the given range. Any non-zero entry is the size of a particular element of the refinement starting at that corresponding byte in the range. I.e. the array [4,0,0,0,4,0,0,0] indicates the address range is 8-bytes long covered by two elements of length 4, starting at offsets 0 and 4 respectively. The given Varnode must be contained in the address range that the refinement array describes.

A new set of Varnode pieces are returned in the split container, where the pieces form a disjoint cover of the original Varnode, and where the piece boundaries match the refinement.

Parameters
vnis the given Varnode to split
addris the starting address of the range described by the refinement
refineis the refinement array
splitwill hold the new Varnode pieces

References ghidra::Varnode::getAddr(), ghidra::Address::getOffset(), ghidra::Varnode::getSize(), ghidra::Address::getSpace(), and ghidra::AddrSpace::wrapOffset().

◆ splitJoinLevel()

void ghidra::Heritage::splitJoinLevel ( vector< Varnode *> &  lastcombo,
vector< Varnode *> &  nextlev,
JoinRecord joinrec 
)
private

Perform one level of Varnode splitting to match a JoinRecord.

Split all the pieces in lastcombo, putting them into nextlev in order, to get closer to the representation described by the given JoinRecord. nextlev contains the two split pieces for each Varnode in lastcombo. If a Varnode is not split this level, an extra null is put into nextlev to maintain the 2-1 mapping.

Parameters
lastcombois the list of Varnodes to split
nextlevwill hold the new split Varnodes in a 2-1 ratio
joinrecis the splitting specification we are trying to match

References ghidra::JoinRecord::getPiece(), ghidra::Varnode::getSize(), ghidra::JoinRecord::numPieces(), ghidra::VarnodeData::offset, ghidra::VarnodeData::size, and ghidra::VarnodeData::space.

◆ splitJoinRead()

void ghidra::Heritage::splitJoinRead ( Varnode vn,
JoinRecord joinrec 
)
private

Construct pieces for a join-space Varnode read by an operation.

Given a splitting specification (JoinRecord) and a Varnode, build a concatenation expression (out of PIECE operations) that constructs the the Varnode out of the specified Varnode pieces.

Parameters
vnis the join-space Varnode to split
joinrecis the splitting specification

References ghidra::CPUI_PIECE, ghidra::PcodeOp::getAddr(), ghidra::Datatype::getMetatype(), ghidra::Varnode::getType(), ghidra::Varnode::isTypeLock(), ghidra::Varnode::loneDescend(), ghidra::JoinRecord::numPieces(), ghidra::Varnode::setPrecisHi(), ghidra::Varnode::setPrecisLo(), ghidra::TYPE_ARRAY, and ghidra::TYPE_STRUCT.

◆ splitJoinWrite()

void ghidra::Heritage::splitJoinWrite ( Varnode vn,
JoinRecord joinrec 
)
private

Split a written join-space Varnode into specified pieces.

Given a splitting specification (JoinRecord) and a Varnode, build a series of expressions that construct the specified Varnode pieces using SUBPIECE ops.

Parameters
vnis the Varnode to split
joinrecis the splitting specification

References ghidra::CPUI_SUBPIECE, ghidra::PcodeOp::getAddr(), ghidra::Varnode::getDef(), ghidra::Varnode::getSize(), ghidra::BlockBasic::getStart(), ghidra::Varnode::isInput(), ghidra::JoinRecord::numPieces(), ghidra::Varnode::setPrecisHi(), and ghidra::Varnode::setPrecisLo().

◆ splitPieces()

void ghidra::Heritage::splitPieces ( const vector< Varnode *> &  vnlist,
PcodeOp insertop,
const Address addr,
int4  size,
Varnode startvn 
)
private

Build a set of Varnode piece expression at the given location.

Given a list of small Varnodes and the address range they are a piece of, construct a SUBPIECE op that defines each piece. The truncation parameters are calculated based on the overlap of the piece with the whole range, and a single input Varnode is used for all SUBPIECE ops.

Parameters
vnlistis the list of piece Varnodes
insertopis the point where the op expressions are inserted (before)
addris the first address of the whole range
sizeis the number of bytes in the whole range
startvnis designated input Varnode

References ghidra::BlockBasic::beginOp(), ghidra::CPUI_SUBPIECE, ghidra::PcodeOp::getAddr(), ghidra::PcodeOp::getBasicIter(), ghidra::Address::getOffset(), ghidra::Varnode::getOffset(), ghidra::PcodeOp::getParent(), ghidra::Varnode::getSize(), and ghidra::Address::isBigEndian().

◆ visitIncr()

void ghidra::Heritage::visitIncr ( FlowBlock qnode,
FlowBlock vnode 
)
private

The heart of the phi-node placement algorithm.

Recursively walk the dominance tree starting from a given block. Calculate any children that are in the dominance frontier and add them to the merge array.

Parameters
qnodeis the parent of the given block
vnodeis the given block

References ghidra::FlowBlock::getImmedDom(), and ghidra::FlowBlock::getIndex().


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