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 LoadGuard *	getStoreGuard (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.

HeritageInfo *	getInfo (AddrSpace *spc)
	Get the heritage status for the given address space.

const HeritageInfo *	getInfo (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...

Varnode *	normalizeReadSize (Varnode *vn, const Address &addr, int4 size)
	Normalize the size of a read Varnode, prior to heritage. More...

Varnode *	normalizeWriteSize (Varnode *vn, const Address &addr, int4 size)
	Normalize the size of a written Varnode, prior to heritage. More...

Varnode *	concatPieces (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
Funcdata *	fd
	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< HeritageInfo >	infolist
	Heritage status for individual address spaces.

list< LoadGuard >	loadGuard
	List of LOAD operations that need to be guarded.

list< LoadGuard >	storeGuard
	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

enum ghidra::Heritage::heritage_flags

private

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

data	is 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

refine	is the refinement array
addr	is the starting address of the given range
size	is the number of bytes in the range
vnlist	is 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

spc	is 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

write is 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

addr	is the starting address of the range
size	is the number of bytes in the range
op	is 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

info	is 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

addr	is the starting address of the range
size	is the number of bytes in the range
read	will hold any read Varnodes in the range
write	will hold any written Varnodes
input	will hold any input Varnodes
remove	will 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

vnlist	is the list of Varnodes to concatenate
insertop	is the point where the expression should be inserted (before)
finalvn	is 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

spc	is 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

spc	is 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

spc	is the particular address space with a stackpointer (into it)
freeStores	will hold the list of any STOREs that need follow-up analysis
checkFreeStores	is 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

copySinks	is the list of sinks that we are trying to find flow to
forces	is 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

vn	is the lower precision join-space input Varnode
joinrec	is 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

vn	is the lower precision join-space output Varnode
joinrec	is 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

node	is the path element containing the constructed Address
op	is the LOAD PcodeOp
spc	is 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

node	is the path element containing the constructed Address
op	is the STORE PcodeOp
spc	is 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

spc	is 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

op	is 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

addr	is the starting address of the given range
size	is the number of bytes in the given range
guardPerformed	is true if a guard has been previously performed on the range
read	is the set of Varnode values reading from the range
write	is the set of written Varnodes in the range
inputvars	is 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

fc	is the call site potentially taking a parameter
addr	is the starting address of the range
transAddr	is the start of the same range from the callee's stack perspective
size	is 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

fc	is the call site potentially returning a value
addr	is the starting address of the range
size	is the size of the range in bytes
write	is 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

fl	are any boolean properties associated with the address range
addr	is the first address of given range
size	is the number of bytes in the range
write	is the list of written Varnodes in the range (may be updated)

◆ 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

addr	is the first address in the given range
size	is the number of bytes in the range
input	are 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

fl	is boolean properties associated with the address
addr	is the first address of the given range
size	is the number of bytes in the given range
write	is 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

fl	are any boolean properties associated with the address range
addr	is the first address of the given range
size	is the number of bytes in the range
write	is 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

addr	is the starting address of the range
size	is 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

addr	is the first address of the given range
size	is the number of bytes in the given range
write	is 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 )

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.

References ghidra::Varnode::beginDescend(), ghidra::HeritageInfo::deadremoved, ghidra::PcodeOp::getAddr(), ghidra::Varnode::getAddr(), ghidra::Varnode::getSize(), ghidra::Varnode::getSpace(), ghidra::HeritageInfo::hasCallPlaceholders, ghidra::Varnode::hasNoDescend(), ghidra::HeritageInfo::isHeritaged(), ghidra::Varnode::isHeritageKnown(), ghidra::Varnode::isInput(), ghidra::Varnode::isUnaffected(), ghidra::Varnode::isWriteMask(), ghidra::Varnode::isWritten(), ghidra::HeritageInfo::loadGuardSearch, ghidra::Address::printRaw(), ghidra::Varnode::printRawNoMarkup(), ghidra::HeritageInfo::space, and ghidra::HeritageInfo::warningissued.

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

◆ heritagePass()

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

inline

Get the pass number when the given address was heritaged.

Parameters

addr	is 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

vn	is the given too small Varnode
addr	is the start of the (larger) range
size	is 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

vn	is the given too small Varnode
addr	is the start of the (larger) range
size	is 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

spc	is 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

op	is 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

spc	is the given address space
freeStores	will 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

vn	is the given Varnode to split
addr	is the starting address of the address range being refined
refine	is the refinement array
newvn	is 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

addr	is the first address in the range
size	is the number of bytes in the range
readvars	is all free Varnodes overlapping the address range
writevars	is all written Varnodes overlapping the address range
inputvars	is 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

vn	is the given Varnode to split
addr	is the starting address of the address range being refined
refine	is the refinement array
newvn	is 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

vn	is the given Varnode to split
addr	is the starting address of the address range being refined
refine	is the refinement array
newvn	is 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

refine is 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

remove	is the list of Varnodes written by MULTIEQUAL or INDIRECT
addr	is the start of the larger range
size	is 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

bl	is the current basic block in the dominance tree walk
varstack	is 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

spc	is the address space being guarded
freeStores	is 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

spc	is 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

spc	is the given address space
delay	is 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

vn	is the given Varnode to split
addr	is the starting address of the range described by the refinement
refine	is the refinement array
split	will 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

lastcombo	is the list of Varnodes to split
nextlev	will hold the new split Varnodes in a 2-1 ratio
joinrec	is 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

vn	is the join-space Varnode to split
joinrec	is 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

vn	is the Varnode to split
joinrec	is 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

vnlist	is the list of piece Varnodes
insertop	is the point where the op expressions are inserted (before)
addr	is the first address of the whole range
size	is the number of bytes in the whole range
startvn	is 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

qnode	is the parent of the given block
vnode	is the given block

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

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

heritage.hh
heritage.cc

Classes

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ heritage_flags

Constructor & Destructor Documentation

◆ Heritage()

Member Function Documentation

◆ analyzeNewLoadGuards()

◆ buildADT()

◆ buildInfoList()

◆ buildRefinement()

◆ bumpDeadcodeDelay()

◆ calcMultiequals()

◆ callOpIndirectEffect()

◆ clear()

◆ clearStackPlaceholders()

◆ collect()

◆ concatPieces()

◆ deadRemovalAllowed()

◆ deadRemovalAllowedSeen()

◆ discoverIndexedStackPointers()

◆ findAddressForces()

◆ floatExtensionRead()

◆ floatExtensionWrite()

◆ generateLoadGuard()

◆ generateStoreGuard()

◆ getDeadCodeDelay()

◆ getStoreGuard()

◆ guard()

◆ guardCallOverlappingInput()

◆ guardCallOverlappingOutput()

◆ guardCalls()

◆ guardInput()

◆ guardLoads()

◆ guardReturns()

◆ guardReturnsOverlapping()

◆ guardStores()

◆ handleNewLoadCopies()

◆ heritage()

◆ heritagePass()

◆ normalizeReadSize()

◆ normalizeWriteSize()

◆ numHeritagePasses()

◆ placeMultiequals()

◆ processJoins()

◆ propagateCopyAway()

◆ protectFreeStores()

◆ refineInput()

◆ refinement()

◆ refineRead()

◆ refineWrite()

◆ remove13Refinement()

◆ removeRevisitedMarkers()

◆ rename()

◆ renameRecurse()

◆ reprocessFreeStores()

◆ seenDeadCode()

◆ setDeadCodeDelay()

◆ splitByRefinement()

◆ splitJoinLevel()

◆ splitJoinRead()

◆ splitJoinWrite()

◆ splitPieces()

◆ visitIncr()