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

#include <heritage.hh>

Public Member Functions
	Heritage (Funcdata *data)
	Constructor. More...

int4	heritagePass (const Address &addr) const
	Get the pass number when the given address was heritaged. More...

int4	numHeritagePasses (AddrSpace *spc) const
	Get the number times heritage was performed for the given address space. More...

void	seenDeadCode (AddrSpace *spc)
	Inform system of dead code removal in given space. More...

int4	getDeadCodeDelay (AddrSpace *spc) const
	Get pass delay for heritaging the given space. More...

void	setDeadCodeDelay (AddrSpace *spc, int4 delay)
	Set delay for a specific space. More...

bool	deadRemovalAllowed (AddrSpace *spc) const
	Return true if it is safe to remove dead code. More...

bool	deadRemovalAllowedSeen (AddrSpace *spc)
	Check if dead code removal is safe and mark that removal has happened. More...

void	buildInfoList (void)
	Initialize information for each space. More...

void	forceRestructure (void)
	Force regeneration of basic block structures.

void	clear (void)
	Reset all analysis of heritage. 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...

void	heritage (void)
	Perform one pass of heritage. 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 heriage status for the given address space.

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...

int4	collect (Address addr, int4 size, vector< Varnode * > &read, vector< Varnode * > &write, vector< Varnode * > &input) 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	guard (const Address &addr, int4 size, 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	guardCalls (uint4 flags, 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	guardReturns (uint4 flags, 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 (Varnode *vn)
	Increase the heritage delay for the given Varnode and request a restart. 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.

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 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()

Heritage::Heritage ( Funcdata * data )

Constructor.

Instantiate the heritage manager for a particular function.

Parameters

data	is the function

References fd, maxdepth, and pass.

Member Function Documentation

◆ buildADT()

void Heritage::buildADT ( void )

private

Build the augmented dominator tree.

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

References augment, boundary_node, depth, domchild, fd, flags, Funcdata::getBasicBlocks(), FlowBlock::getImmedDom(), FlowBlock::getIn(), FlowBlock::getIndex(), BlockGraph::getSize(), maxdepth, and FlowBlock::sizeIn().

Referenced by heritage().

◆ buildInfoList()

void Heritage::buildInfoList ( void )

Initialize information for each space.

This is called once to initialize this class in preparation for doing the heritage passes. An information structure is allocated and mapped to each address space.

References fd, Funcdata::getArch(), AddrSpace::getDeadcodeDelay(), AddrSpace::getDelay(), AddrSpaceManager::getSpace(), infolist, and AddrSpaceManager::numSpaces().

Referenced by Funcdata::startProcessing().

◆ buildRefinement()

void 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 Address::getOffset().

Referenced by refinement().

◆ bumpDeadcodeDelay()

void Heritage::bumpDeadcodeDelay ( Varnode * vn )

private

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

If applicable, look up the heritage stats for the address space for the given Varnode 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

vn	is the given Varnode

References fd, AddrSpace::getDeadcodeDelay(), AddrSpace::getDelay(), Funcdata::getOverride(), Varnode::getSpace(), AddrSpace::getType(), Override::hasDeadcodeDelay(), Override::insertDeadcodeDelay(), IPTR_PROCESSOR, IPTR_SPACEBASE, and Funcdata::setRestartPending().

Referenced by heritage().

◆ calcMultiequals()

void 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 depth, PriorityQueue::empty(), PriorityQueue::extract(), fd, flags, Funcdata::getBasicBlocks(), BlockGraph::getBlock(), FlowBlock::getIndex(), PriorityQueue::insert(), mark_node, maxdepth, merge, merged_node, pq, PriorityQueue::reset(), and visitIncr().

Referenced by placeMultiequals().

◆ callOpIndirectEffect()

bool 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 PcodeOp::code(), CPUI_CALL, CPUI_CALLIND, fd, Funcdata::getCallSpecs(), FuncCallSpecs::hasEffectTranslate(), and EffectRecord::unaffected.

Referenced by normalizeWriteSize().

◆ clear()

void Heritage::clear ( void )

Reset all analysis of heritage.

Reset all analysis as if no heritage passes have yet taken place for the function. This does not directly affect Varnodes and PcodeOps in the underlying Funcdata.

References augment, LocationMap::clear(), clearInfoList(), depth, disjoint, domchild, flags, globaldisjoint, maxdepth, merge, and pass.

Referenced by Funcdata::clear().

◆ collect()

int4 Heritage::collect	(	Address	addr,
		int4	size,
		vector< Varnode * > &	read,
		vector< Varnode * > &	write,
		vector< Varnode * > &	input
	)		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

Returns: the maximum size of a write

References Funcdata::beginLoc(), Funcdata::endLoc(), fd, AddrSpace::getHighest(), Address::getOffset(), Varnode::getSize(), Address::getSpace(), Varnode::hasNoDescend(), Varnode::isHeritageKnown(), Varnode::isInput(), Varnode::isWriteMask(), and Varnode::isWritten().

Referenced by placeMultiequals().

◆ concatPieces()

Varnode * 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 BlockBasic::beginOp(), CPUI_PIECE, fd, PcodeOp::getAddr(), Varnode::getAddr(), Funcdata::getAddress(), Funcdata::getBasicBlocks(), PcodeOp::getBasicIter(), PcodeOp::getParent(), Varnode::getSize(), BlockGraph::getStartBlock(), Address::isBigEndian(), Funcdata::newOp(), Funcdata::newUniqueOut(), Funcdata::opInsert(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), and Funcdata::opSetOutput().

Referenced by guardInput(), and refineRead().

◆ deadRemovalAllowed()

bool Heritage::deadRemovalAllowed ( AddrSpace * spc ) const

Return true if it is safe to remove dead code.

Check if the required number of passes have transpired to allow removal of dead Varnodes in the given address space. If allowed, presumably no new Varnodes will be generated for the space.

Parameters

spc	is the given address space

Returns: true if dead code removal is allowed

References HeritageInfo::deadcodedelay, getInfo(), and pass.

Referenced by Funcdata::deadRemovalAllowed().

◆ deadRemovalAllowedSeen()

bool Heritage::deadRemovalAllowedSeen ( AddrSpace * spc )

Check if dead code removal is safe and mark that removal has happened.

A convenience function combining deadRemovalAllowed() and seenDeadCode(). Return true if it is safe to remove dead code, and, if so, also inform the system that dead code has happened for the given space.

Parameters

spc	is the given address space

Returns: true if dead code removal is allowed

References HeritageInfo::deadcodedelay, HeritageInfo::deadremoved, getInfo(), and pass.

Referenced by Funcdata::deadRemovalAllowedSeen().

◆ floatExtensionRead()

void 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 CPUI_FLOAT_FLOAT2FLOAT, fd, PcodeOp::getAddr(), JoinRecord::getPiece(), Varnode::loneDescend(), Funcdata::newOp(), Funcdata::newVarnode(), Funcdata::opInsertBefore(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), and Funcdata::opSetOutput().

Referenced by processJoins().

◆ floatExtensionWrite()

void 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 CPUI_FLOAT_FLOAT2FLOAT, fd, PcodeOp::getAddr(), Funcdata::getBasicBlocks(), BlockGraph::getBlock(), Varnode::getDef(), JoinRecord::getPiece(), BlockBasic::getStart(), Varnode::isInput(), Funcdata::newOp(), Funcdata::newVarnodeOut(), Funcdata::opInsertAfter(), Funcdata::opInsertBegin(), Funcdata::opSetInput(), and Funcdata::opSetOpcode().

Referenced by processJoins().

◆ getDeadCodeDelay()

int4 Heritage::getDeadCodeDelay ( AddrSpace * spc ) const

Get pass delay for heritaging the given space.

Linking in Varnodes can be delayed for specific address spaces (to make sure all Varnodes for the space have been generated. Return the number of passes to delay for the given space. 0 means no delay.

Parameters

spc	is the given address space

Returns: the number of passes heritage is delayed

References HeritageInfo::deadcodedelay, getInfo(), and AddrSpace::getName().

◆ guard()

void Heritage::guard	(	const Address &	addr,
		int4	size,
		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
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 PcodeOp::code(), CPUI_INDIRECT, fd, flags, Funcdata::getArch(), Varnode::getDef(), Funcdata::getScopeLocal(), Varnode::getSize(), guardCalls(), guardReturns(), guardStores(), Architecture::highPtrPossible(), Varnode::isAddrForce(), Varnode::isWritten(), normalizeReadSize(), normalizeWriteSize(), Scope::queryProperties(), and Varnode::setActiveHeritage().

Referenced by placeMultiequals().

◆ guardCalls()

void Heritage::guardCalls	(	uint4	flags,
		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

flags	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)

References FuncCallSpecs::abortSpacebaseRelative(), Varnode::addrtied, fd, flags, FuncCallSpecs::getActiveInput(), FuncCallSpecs::getActiveOutput(), Varnode::getAddr(), Funcdata::getCallSpecs(), PcodeOp::getIn(), Address::getOffset(), FuncCallSpecs::getOp(), PcodeOp::getOut(), Varnode::getSize(), Address::getSpace(), FuncCallSpecs::getSpacebaseOffset(), FuncCallSpecs::getStackPlaceholderSlot(), AddrSpace::getType(), FuncCallSpecs::hasEffectTranslate(), IPTR_SPACEBASE, PcodeOp::isAssignment(), FuncCallSpecs::isInputActive(), FuncCallSpecs::isOutputActive(), EffectRecord::killedbycall, Funcdata::newIndirectCreation(), Funcdata::newIndirectOp(), Funcdata::newVarnode(), Funcdata::numCalls(), PcodeOp::numInput(), FuncCallSpecs::offset_unknown, Funcdata::opInsertInput(), FuncProto::possibleInputParam(), FuncProto::possibleOutputParam(), ParamActive::registerTrial(), EffectRecord::return_address, Varnode::setActiveHeritage(), Varnode::setAddrForce(), Varnode::setReturnAddress(), EffectRecord::unknown_effect, ParamActive::whichTrial(), and AddrSpace::wrapOffset().

Referenced by guard().

◆ guardInput()

void 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 concatPieces(), fd, Address::getOffset(), Varnode::getOffset(), Varnode::getSize(), Address::getSpace(), Funcdata::newVarnode(), Varnode::setActiveHeritage(), and Funcdata::setInputVarnode().

Referenced by placeMultiequals().

◆ guardReturns()

void Heritage::guardReturns	(	uint4	flags,
		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

flags	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 Funcdata::beginOp(), CPUI_COPY, CPUI_RETURN, Funcdata::endOp(), fd, flags, Funcdata::getActiveOutput(), PcodeOp::getAddr(), Funcdata::getFuncProto(), PcodeOp::getHaltType(), PcodeOp::isDead(), Funcdata::newOp(), Funcdata::newVarnode(), Funcdata::newVarnodeOut(), PcodeOp::numInput(), Funcdata::opInsertBefore(), Funcdata::opInsertInput(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), Varnode::persist, FuncProto::possibleOutputParam(), ParamActive::registerTrial(), Varnode::setActiveHeritage(), and Varnode::setAddrForce().

Referenced by guard().

◆ guardStores()

void 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 Funcdata::beginOp(), AddrSpace::contain(), CPUI_STORE, Funcdata::endOp(), fd, Varnode::getAddr(), PcodeOp::getIn(), PcodeOp::getOut(), Address::getSpace(), Address::getSpaceFromConst(), PcodeOp::isDead(), Funcdata::newIndirectOp(), and Varnode::setActiveHeritage().

Referenced by guard().

◆ heritage()

void Heritage::heritage ( void )

Perform one pass of heritage.

From any address space that is active for this pass, free Varnodes are collected and then fully integrated into SSA form. Reads are connected to writes, inputs are identified, and phi-nodes are placed.

References LocationMap::add(), Varnode::beginDescend(), Funcdata::beginLoc(), buildADT(), bumpDeadcodeDelay(), HeritageInfo::deadremoved, disjoint, Funcdata::endLoc(), fd, PcodeOp::getAddr(), Varnode::getAddr(), Funcdata::getArch(), getInfo(), Varnode::getSize(), AddrSpaceManager::getSpace(), globaldisjoint, Varnode::hasNoDescend(), AddrSpace::isHeritaged(), Varnode::isHeritageKnown(), Varnode::isInput(), Varnode::isUnaffected(), Varnode::isWriteMask(), Varnode::isWritten(), maxdepth, AddrSpaceManager::numSpaces(), pass, placeMultiequals(), Address::printRaw(), Varnode::printRawNoMarkup(), processJoins(), rename(), Architecture::splitrecords, Funcdata::warningHeader(), and HeritageInfo::warningissued.

Referenced by Funcdata::opHeritage().

◆ heritagePass()

int4 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 LocationMap::findPass(), and globaldisjoint.

Referenced by Funcdata::isHeritaged().

◆ normalizeReadSize()

Varnode * 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 Varnode::beginDescend(), CPUI_SUBPIECE, Varnode::endDescend(), fd, PcodeOp::getAddr(), Address::getAddrSize(), PcodeOp::getOut(), Funcdata::newConstant(), Funcdata::newOp(), Funcdata::newVarnode(), Funcdata::opInsertBefore(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), Funcdata::opSetOutput(), Varnode::overlap(), and Varnode::setWriteMask().

Referenced by guard().

◆ normalizeWriteSize()

Varnode * 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 callOpIndirectEffect(), CPUI_PIECE, CPUI_SUBPIECE, fd, PcodeOp::getAddr(), Varnode::getAddr(), Address::getAddrSize(), Varnode::getDef(), PcodeOp::getOut(), Varnode::getSize(), Address::isBigEndian(), PcodeOp::isCall(), Funcdata::newConstant(), Funcdata::newIndirectCreation(), Funcdata::newOp(), Funcdata::newVarnode(), Funcdata::newVarnodeOut(), Funcdata::opInsertAfter(), Funcdata::opInsertBefore(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), Varnode::overlap(), Varnode::setActiveHeritage(), and Varnode::setWriteMask().

Referenced by guard().

◆ numHeritagePasses()

int4 Heritage::numHeritagePasses ( AddrSpace * spc ) const

Get the number times heritage was performed for the given address space.

A negative number indicates the number of passes to be wait before the first heritage will occur.

Parameters

spc	is the given address space

Returns: the number of heritage passes performed

References HeritageInfo::delay, getInfo(), and pass.

Referenced by Funcdata::numHeritagePasses().

◆ placeMultiequals()

void Heritage::placeMultiequals ( void )

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 LocationMap::begin(), calcMultiequals(), collect(), CPUI_MULTIEQUAL, disjoint, LocationMap::end(), fd, LocationMap::find(), Address::getSpace(), BlockBasic::getStart(), AddrSpace::getType(), guard(), guardInput(), IPTR_INTERNAL, merge, Funcdata::newOp(), Funcdata::newVarnode(), Funcdata::newVarnodeOut(), Funcdata::opInsertBegin(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), refinement(), Varnode::setActiveHeritage(), and FlowBlock::sizeIn().

Referenced by heritage().

◆ processJoins()

void 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 Funcdata::beginLoc(), HeritageInfo::delay, Funcdata::endLoc(), fd, AddrSpaceManager::findJoin(), floatExtensionRead(), floatExtensionWrite(), Funcdata::getArch(), getInfo(), AddrSpaceManager::getJoinSpace(), Varnode::getOffset(), JoinRecord::getPiece(), Varnode::getSize(), Varnode::getSpace(), JoinRecord::getUnified(), JoinRecord::isFloatExtension(), Varnode::isFree(), pass, VarnodeData::size, VarnodeData::space, splitJoinRead(), and splitJoinWrite().

Referenced by heritage().

◆ refineInput()

void 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 Varnode::getAddr(), Varnode::getSize(), Varnode::setWriteMask(), splitByRefinement(), and splitPieces().

Referenced by refinement().

◆ refinement()

bool 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

References LocationMap::add(), buildRefinement(), disjoint, LocationMap::erase(), LocationMap::find(), globaldisjoint, pass, refineInput(), refineRead(), refineWrite(), and remove13Refinement().

Referenced by placeMultiequals().

◆ refineRead()

void 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 concatPieces(), Funcdata::deleteVarnode(), fd, Varnode::getSize(), PcodeOp::getSlot(), Varnode::hasNoDescend(), Varnode::loneDescend(), Funcdata::newUnique(), Funcdata::opSetInput(), and splitByRefinement().

Referenced by refinement().

◆ refineWrite()

void 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 Funcdata::deleteVarnode(), fd, Varnode::getAddr(), Varnode::getDef(), Varnode::getSize(), Funcdata::newUnique(), Funcdata::opSetOutput(), splitByRefinement(), splitPieces(), and Funcdata::totalReplace().

Referenced by refinement().

◆ remove13Refinement()

void 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

Referenced by refinement().

◆ rename()

void Heritage::rename ( void )

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

Phi-node placement must already have happened.

References LocationMap::clear(), disjoint, fd, Funcdata::getBasicBlocks(), BlockGraph::getBlock(), and renameRecurse().

Referenced by heritage().

◆ renameRecurse()

void 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 BlockBasic::beginOp(), Varnode::clearActiveHeritage(), PcodeOp::code(), CPUI_INDIRECT, CPUI_MULTIEQUAL, Funcdata::deleteVarnode(), domchild, BlockBasic::endOp(), fd, Varnode::getAddr(), Varnode::getDef(), PcodeOp::getIn(), FlowBlock::getIndex(), PcodeOp::getOpFromConst(), PcodeOp::getOut(), FlowBlock::getOut(), FlowBlock::getOutRevIndex(), Varnode::getSize(), Varnode::hasNoDescend(), Varnode::insert, Varnode::isActiveHeritage(), Varnode::isHeritageKnown(), Varnode::isWritten(), Funcdata::newVarnode(), PcodeOp::numInput(), Funcdata::opSetInput(), Funcdata::setInputVarnode(), and FlowBlock::sizeOut().

Referenced by rename().

◆ seenDeadCode()

void Heritage::seenDeadCode ( AddrSpace * spc )

Inform system of dead code removal in given space.

Record that Varnodes have been removed from the given space so that we can tell if there is any new heritage after the dead code removal.

Parameters

spc	is the given address space

References HeritageInfo::deadremoved, and getInfo().

Referenced by Funcdata::seenDeadcode().

◆ setDeadCodeDelay()

void Heritage::setDeadCodeDelay	(	AddrSpace *	spc,
		int4	delay
	)

Set delay for a specific space.

Set the number of heritage passes that are skipped before allowing dead code removal for Varnodes in the given address space (to make sure all Varnodes have been linked in before deciding what is dead).

Parameters

spc	is the given address space
delay	is the number of passes to delay

References HeritageInfo::deadcodedelay, and getInfo().

Referenced by Funcdata::setDeadCodeDelay().

◆ splitByRefinement()

void 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 fd, Varnode::getAddr(), Address::getOffset(), Varnode::getSize(), Address::getSpace(), Funcdata::newVarnode(), and AddrSpace::wrapOffset().

Referenced by refineInput(), refineRead(), and refineWrite().

◆ splitJoinLevel()

void 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 fd, JoinRecord::getPiece(), Varnode::getSize(), Funcdata::newUnique(), Funcdata::newVarnode(), JoinRecord::numPieces(), VarnodeData::offset, VarnodeData::size, and VarnodeData::space.

Referenced by splitJoinRead(), and splitJoinWrite().

◆ splitJoinRead()

void 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 CPUI_PIECE, fd, PcodeOp::getAddr(), Varnode::loneDescend(), Funcdata::newOp(), JoinRecord::numPieces(), Funcdata::opInsertBefore(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), Funcdata::opSetOutput(), Varnode::setPrecisHi(), Varnode::setPrecisLo(), and splitJoinLevel().

Referenced by processJoins().

◆ splitJoinWrite()

void 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 CPUI_SUBPIECE, fd, PcodeOp::getAddr(), Funcdata::getBasicBlocks(), BlockGraph::getBlock(), Varnode::getDef(), Varnode::getSize(), BlockBasic::getStart(), Varnode::isInput(), Funcdata::newConstant(), Funcdata::newOp(), JoinRecord::numPieces(), Funcdata::opInsertAfter(), Funcdata::opInsertBegin(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), Funcdata::opSetOutput(), Varnode::setPrecisHi(), Varnode::setPrecisLo(), and splitJoinLevel().

Referenced by processJoins().

◆ splitPieces()

void 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 BlockBasic::beginOp(), CPUI_SUBPIECE, fd, PcodeOp::getAddr(), Funcdata::getAddress(), Funcdata::getBasicBlocks(), PcodeOp::getBasicIter(), Address::getOffset(), Varnode::getOffset(), PcodeOp::getParent(), Varnode::getSize(), BlockGraph::getStartBlock(), Address::isBigEndian(), Funcdata::newConstant(), Funcdata::newOp(), Funcdata::opInsert(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), and Funcdata::opSetOutput().

Referenced by refineInput(), and refineWrite().

◆ visitIncr()

void 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 augment, boundary_node, depth, domchild, flags, FlowBlock::getImmedDom(), FlowBlock::getIndex(), PriorityQueue::insert(), mark_node, merge, merged_node, and pq.

Referenced by calcMultiequals().

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

heritage.hh
heritage.cc

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

◆ buildADT()

◆ buildInfoList()

◆ buildRefinement()

◆ bumpDeadcodeDelay()

◆ calcMultiequals()

◆ callOpIndirectEffect()

◆ clear()

◆ collect()

◆ concatPieces()

◆ deadRemovalAllowed()

◆ deadRemovalAllowedSeen()

◆ floatExtensionRead()

◆ floatExtensionWrite()

◆ getDeadCodeDelay()

◆ guard()

◆ guardCalls()

◆ guardInput()

◆ guardReturns()

◆ guardStores()

◆ heritage()

◆ heritagePass()

◆ normalizeReadSize()

◆ normalizeWriteSize()

◆ numHeritagePasses()

◆ placeMultiequals()

◆ processJoins()

◆ refineInput()

◆ refinement()

◆ refineRead()

◆ refineWrite()

◆ remove13Refinement()

◆ rename()

◆ renameRecurse()

◆ seenDeadCode()

◆ setDeadCodeDelay()

◆ splitByRefinement()

◆ splitJoinLevel()

◆ splitJoinRead()

◆ splitJoinWrite()

◆ splitPieces()

◆ visitIncr()