Class for merging low-level Varnodes into high-level HighVariables. More...

#include <merge.hh>

Public Member Functions
	Merge (Funcdata &fd)
	Construct given a specific function.

bool	intersection (HighVariable a, HighVariable b)
	Test the intersection of two HighVariables and cache the result. More...

bool	inflateTest (Varnode a, HighVariable high)
	Test if we can inflate the Cover of the given Varnode without incurring intersections. More...

void	inflate (Varnode a, HighVariable high)
	Inflate the Cover of a given Varnode with a HighVariable. More...

bool	mergeTest (HighVariable high, vector< HighVariable > &tmplist)
	Test for intersections between a given HighVariable and a list of other HighVariables. More...

void	mergeOpcode (OpCode opc)
	Try to force merges of input to output for all p-code ops of a given type. More...

void	mergeByDatatype (VarnodeLocSet::const_iterator startiter, VarnodeLocSet::const_iterator enditer)
	Try to merge all HighVariables in the given range that have the same data-type. More...

void	mergeAddrTied (void)
	Force the merge of address tried Varnodes. More...

void	mergeMarker (void)
	Force the merge of input and output Varnodes to MULTIEQUAL and INDIRECT ops. More...

void	mergeAdjacent (void)
	Speculatively merge Varnodes that are input/output to the same p-code op. More...

bool	hideShadows (HighVariable *high)
	Hide shadow Varnodes related to the given HighVariable by consolidating COPY chains. More...

Private Member Functions
bool	updateHigh (HighVariable *a)
	Make sure given HighVariable's Cover is up-to-date. More...

void	purgeHigh (HighVariable *high)
	Remove cached intersection tests for a given HighVariable. More...

bool	blockIntersection (HighVariable a, HighVariable b, int4 blk)
	Test if two HighVariables intersect on a given BlockBasic. More...

void	collectCovering (vector< Varnode * > &vlist, HighVariable high, PcodeOp op)
	Collect all instances of the given HighVariable whose Cover intersects a p-code op. More...

bool	collectCorrectable (const vector< Varnode * > &vlist, list< PcodeOp * > &oplist, vector< int4 > &slotlist, PcodeOp *op)
	Check for for p-code op intersections that are correctable. More...

void	snipReads (Varnode vn, list< PcodeOp > &markedop)
	Snip off set of read p-code ops for a given Varnode. More...

void	snipIndirect (PcodeOp *indop)
	Snip instances of the input of an INDIRECT op that interfere with its output. More...

void	eliminateIntersect (Varnode *vn, const vector< BlockVarnode > &blocksort)
	Eliminate intersections of given Varnode with other Varnodes in a list. More...

void	unifyAddress (VarnodeLocSet::const_iterator startiter, VarnodeLocSet::const_iterator enditer)
	Make sure all Varnodes with the same storage address and size can be merged. More...

void	trimOpOutput (PcodeOp *op)
	Trim the output HighVariable of the given PcodeOp so that its Cover is tiny. More...

void	trimOpInput (PcodeOp *op, int4 slot)
	Trim the input HighVariable of the given PcodeOp so that its Cover is tiny. More...

void	mergeRangeMust (VarnodeLocSet::const_iterator startiter, VarnodeLocSet::const_iterator enditer)
	Force the merge of a ranges of Varnodes with the same size and storage address. More...

void	mergeOp (PcodeOp *op)
	Force the merge of all input and output Varnodes for the given PcodeOp. More...

void	mergeIndirect (PcodeOp *indop)
	Force the merge of all input and output Varnodes to a given INDIRECT op. More...

void	mergeLinear (vector< HighVariable * > &highvec)
	Speculatively merge all HighVariables in the given list as well as possible. More...

bool	merge (HighVariable high1, HighVariable high2, bool isspeculative)
	Perform low-level details of merging two HighVariables if possible. More...

Static Private Member Functions
static bool	mergeTestRequired (HighVariable high_out, HighVariable high_in)
	Required tests to merge HighVariables that are not Cover related. More...

static bool	mergeTestAdjacent (HighVariable high_out, HighVariable high_in)
	Adjacency tests for merging Varnodes that are input or output to the same p-code op. More...

static bool	mergeTestSpeculative (HighVariable high_out, HighVariable high_in)
	Speculative tests for merging HighVariables that are not Cover related. More...

static bool	mergeTestBasic (Varnode *vn)
	A test if the given Varnode can ever be merged. More...

static void	findSingleCopy (HighVariable high, vector< Varnode > &singlelist)
	Find instance Varnodes that copied to from outside the given HighVariable. More...

static bool	compareHighByBlock (const HighVariable a, const HighVariable b)
	Compare HighVariables by the blocks they cover. More...

Private Attributes
Funcdata &	data
	The function containing the Varnodes to be merged.

map< HighEdge, bool >	highedgemap
	A cache of intersection tests, sorted by HighVariable pair.

Detailed Description

Class for merging low-level Varnodes into high-level HighVariables.

As a node in Single Static Assignment (SSA) form, a Varnode has at most one defining operation. To get a suitable notion of a single high-level variable (HighVariable) that may be reassigned at multiple places in a single function, individual Varnode objects can be merged into a HighVariable object. Varnode objects may be merged in this way if there is no pairwise intersection between each Varnode's Cover, the ranges of code where the Varnode holds its value.

For a given function, this class attempts to merge Varnodes using various strategies and keeps track of Cover intersections to facilitate the process. Merge strategies break up into two general categories: forced merges, and speculative merges. Forced merges must happen, and extra Varnodes may be added to split up problematic covers to enforce it. Forced merges include:

Merging inputs and outputs of MULTIEQUAL and INDIRECT operations
Merging Varnodes at global (persistent) storage locations
Merging Varnodes at mapped stack locations

Speculative merges are attempted to reduce the overall number of variables defined by a function, but any given merge attempt is abandoned if there are Cover intersections. No modification is made to the data-flow to force the merge. Speculative merges include:

Merging an input and output Varnode of a single p-code op
Merging Varnodes that hold the same data-type

Member Function Documentation

◆ blockIntersection()

bool Merge::blockIntersection	(	HighVariable *	a,
		HighVariable *	b,
		int4	blk
	)

private

Test if two HighVariables intersect on a given BlockBasic.

Intersections are checked only on the specified block.

Parameters

a	is the first HighVariable
b	is the second HighVariable
blk	is the index of the BlockBasic on which to test intersection

Returns: true if an intersection occurs in the specified block

References Varnode::copyShadow(), Varnode::getCover(), HighVariable::getInstance(), Cover::intersectByBlock(), HighVariable::numInstances(), and HighVariable::wholecover.

Referenced by intersection().

◆ collectCorrectable()

bool Merge::collectCorrectable	(	const vector< Varnode * > &	vlist,
		list< PcodeOp * > &	oplist,
		vector< int4 > &	slotlist,
		PcodeOp *	op
	)

private

Check for for p-code op intersections that are correctable.

Given a list of Varnodes that intersect a specific PcodeOp, check that each intersection is on the boundary, and if so, pass back the read op(s) that cause the intersection.

Parameters

vlist	is the given list of intersecting Varnodes
oplist	will hold the boundary intersecting read ops
slotlist	will hold the corresponding input slots of the instance
op	is the specific intersecting PcodeOp

Returns: false if any instance in the list intersects the PcodeOp on the interior

References Varnode::beginDescend(), CoverBlock::boundary(), Varnode::endDescend(), Varnode::getCover(), Cover::getCoverBlock(), FlowBlock::getIndex(), PcodeOp::getParent(), PcodeOp::getSlot(), and CoverBlock::getUIndex().

Referenced by snipIndirect().

◆ collectCovering()

void Merge::collectCovering	(	vector< Varnode * > &	vlist,
		HighVariable *	high,
		PcodeOp *	op
	)

private

Collect all instances of the given HighVariable whose Cover intersects a p-code op.

Efficiently test if each instance Varnodes contains the specific p-code op in its Cover and return a list of the instances that do.

Parameters

vlist	will hold the resulting list of intersecting instances
high	is the given HighVariable
op	is the specific PcodeOp to test intersection with

References CoverBlock::contain(), Varnode::getCover(), Cover::getCoverBlock(), FlowBlock::getIndex(), HighVariable::getInstance(), PcodeOp::getParent(), and HighVariable::numInstances().

Referenced by snipIndirect().

◆ compareHighByBlock()

bool Merge::compareHighByBlock	(	const HighVariable *	a,
		const HighVariable *	b
	)

inlinestaticprivate

Compare HighVariables by the blocks they cover.

This comparator sorts, based on:

Index of the first block containing cover for the HighVariable
Address of the first instance
Address of the defining p-code op
Storage address

Parameters

a	is the first HighVariable to compare
b	is the second HighVariable

Returns: true if the first HighVariable should be ordered before the second

References Cover::compareTo(), PcodeOp::getAddr(), Varnode::getAddr(), Varnode::getDef(), HighVariable::getInstance(), and HighVariable::wholecover.

Referenced by mergeLinear().

◆ eliminateIntersect()

void Merge::eliminateIntersect	(	Varnode *	vn,
		const vector< BlockVarnode > &	blocksort
	)

private

Eliminate intersections of given Varnode with other Varnodes in a list.

Both the given Varnode and those in the list are assumed to be at the same storage address. For any intersection, identify the PcodeOp reading the given Varnode which causes the intersection and snip the read by inserting additional COPY ops.

Parameters

vn	is the given Varnode
blocksort	is the list of other Varnodes sorted by their defining basic block

References Cover::addDefPoint(), Cover::addRefPoint(), Cover::begin(), Varnode::beginDescend(), PcodeOp::code(), Cover::containVarnodeDef(), Varnode::copyShadow(), CPUI_INDIRECT, Cover::end(), Varnode::endDescend(), BlockVarnode::findFront(), Varnode::getAddr(), Varnode::getDef(), PcodeOp::getIn(), PcodeOp::getOpFromConst(), SeqNum::getOrder(), PcodeOp::getSeqNum(), Varnode::isAddrForce(), Varnode::isWritten(), and snipReads().

Referenced by unifyAddress().

◆ findSingleCopy()

void Merge::findSingleCopy	(	HighVariable *	high,
		vector< Varnode * > &	singlelist
	)

staticprivate

Find instance Varnodes that copied to from outside the given HighVariable.

Find all Varnodes in the HighVariable which are defined by a COPY from another Varnode which is not part of the same HighVariable.

Parameters

high	is the given HighVariable
singlelist	will hold the resulting list of copied instances

References PcodeOp::code(), CPUI_COPY, Varnode::getDef(), Varnode::getHigh(), PcodeOp::getIn(), HighVariable::getInstance(), Varnode::isWritten(), and HighVariable::numInstances().

Referenced by hideShadows().

◆ hideShadows()

bool Merge::hideShadows ( HighVariable * high )

Hide shadow Varnodes related to the given HighVariable by consolidating COPY chains.

If two Varnodes are copied from the same common ancestor then they will always contain the same value and can be considered shadows of the same variable. If the paths from the ancestor to the two Varnodes aren't properly nested, the two Varnodes will still look like distinct variables. This routine searches for this situation, relative to a single HighVariable, and alters data-flow so that copying from ancestor to first Varnode to second Varnode becomes a single path. Both Varnodes then ultimately become instances of the same HighVariable.

Parameters

high	is the given HighVariable to search near

Returns: true if a change was made to data-flow

References Cover::containVarnodeDef(), Varnode::copyShadow(), data, findSingleCopy(), Varnode::getCover(), Varnode::getDef(), and Funcdata::opSetInput().

Referenced by ActionHideShadow::apply().

◆ inflate()

void Merge::inflate	(	Varnode *	a,
		HighVariable *	high
	)

Inflate the Cover of a given Varnode with a HighVariable.

An expression involving a HighVariable can be propagated to all the read sites of the output Varnode of the expression if the Varnode Cover can be inflated to include the Cover of the HighVariable, even though the Varnode is not part of the HighVariable. This routine performs the inflation, assuming an intersection test is already performed.

Parameters

a	is the given Varnode to inflate
high	is the HighVariable to inflate with

References Varnode::cover, HighVariable::coverDirty(), Varnode::getHigh(), HighVariable::getInstance(), Cover::merge(), HighVariable::numInstances(), and updateHigh().

Referenced by ActionMarkImplied::apply().

◆ inflateTest()

bool Merge::inflateTest	(	Varnode *	a,
		HighVariable *	high
	)

Test if we can inflate the Cover of the given Varnode without incurring intersections.

This routine tests whether an expression involving a HighVariable can be propagated to all the read sites of the output Varnode of the expression. This is possible only if the Varnode Cover can be inflated to include the Cover of the HighVariable, even though the Varnode is not part of the HighVariable.

Parameters

a	is the given Varnode to inflate
high	is the HighVariable being propagated

Returns: true if the Varnode can be inflated without intersection

References Varnode::copyShadow(), Varnode::getCover(), Varnode::getHigh(), HighVariable::getInstance(), Cover::intersect(), HighVariable::numInstances(), updateHigh(), and HighVariable::wholecover.

Referenced by ActionMarkImplied::checkImpliedCover().

◆ intersection()

bool Merge::intersection	(	HighVariable *	a,
		HighVariable *	b
	)

Test the intersection of two HighVariables and cache the result.

If the Covers of the two variables intersect, this routine returns true. To avoid expensive computation on the Cover objects themselves, the test result associated with the pair of HighVariables is cached.

Parameters

a	is the first HighVariable
b	is the second HighVariable

Returns: true if the variables intersect

References blockIntersection(), highedgemap, Cover::intersectList(), updateHigh(), and HighVariable::wholecover.

Referenced by merge(), mergeAdjacent(), and mergeTest().

◆ merge()

bool Merge::merge	(	HighVariable *	high1,
		HighVariable *	high2,
		bool	isspeculative
	)

private

Perform low-level details of merging two HighVariables if possible.

This routine only fails (returning false) if there is a Cover intersection between the two variables. Otherwise, all the Varnode instances from the second HighVariable are merged into the first and its Cover is updated. The cached intersection tests are also updated to reflect the merge.

Parameters

high1	is the first HighVariable being merged
high2	is the second
isspeculative	is true if the desired merge is speculative

Returns: true if the merge was successful

References highedgemap, intersection(), HighVariable::merge(), HighVariable::setMark(), and HighVariable::updateCover().

Referenced by mergeAdjacent(), mergeIndirect(), mergeLinear(), mergeOp(), mergeOpcode(), and mergeRangeMust().

◆ mergeAddrTied()

void Merge::mergeAddrTied ( void )

Force the merge of address tried Varnodes.

For each set of address tied Varnodes with the same size and storage address, merge them into a single HighVariable. The merges are forced, so any Cover intersections must be resolved by altering data-flow, which involves inserting additional COPY ops and unique Varnodes.

References Funcdata::beginLoc(), data, Funcdata::endLoc(), mergeRangeMust(), unifyAddress(), and Varnode::written.

Referenced by ActionMergeRequired::apply().

◆ mergeAdjacent()

void Merge::mergeAdjacent ( void )

Speculatively merge Varnodes that are input/output to the same p-code op.

If a single p-code op has an input and output HighVariable that share the same data-type, attempt to merge them. Each merge is speculative and is skipped if it would introduce Cover intersections.

References Funcdata::beginOpAlive(), data, Funcdata::endOpAlive(), Varnode::getDef(), Varnode::getHigh(), PcodeOp::getIn(), PcodeOp::getOut(), Varnode::getSize(), PcodeOp::inputTypeLocal(), intersection(), PcodeOp::isCall(), Varnode::isInput(), merge(), mergeTestAdjacent(), mergeTestBasic(), PcodeOp::numInput(), and PcodeOp::outputTypeLocal().

Referenced by ActionMergeAdjacent::apply().

◆ mergeByDatatype()

void Merge::mergeByDatatype	(	VarnodeLocSet::const_iterator	startiter,
		VarnodeLocSet::const_iterator	enditer
	)

Try to merge all HighVariables in the given range that have the same data-type.

HighVariables that have an instance within the given Varnode range are sorted into groups based on their data-type. Then an attempt is made to merge all the HighVariables within a group. If a particular merge causes Cover intersection, it is skipped.

Parameters

startiter	is the start of the given range of Varnodes
enditer	is the end of the given range

References HighVariable::getType(), Varnode::isFree(), HighVariable::isMark(), mergeLinear(), mergeTestBasic(), and HighVariable::setMark().

Referenced by ActionMergeType::apply().

◆ mergeIndirect()

void Merge::mergeIndirect ( PcodeOp * indop )

private

Force the merge of all input and output Varnodes to a given INDIRECT op.

Merging INDIRECTs take a little care if their output is address forced because by convention the value must be present at the address BEFORE the indirect effect operation takes place.

Parameters

indop is the given INDIRECT

References CPUI_COPY, data, PcodeOp::getAddr(), Varnode::getHigh(), PcodeOp::getIn(), PcodeOp::getOut(), Varnode::getSize(), Varnode::getType(), Varnode::isAddrForce(), merge(), mergeOp(), mergeTestRequired(), Funcdata::newOp(), Funcdata::newUnique(), Funcdata::opInsertBefore(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), Funcdata::opSetOutput(), and snipIndirect().

Referenced by mergeMarker().

◆ mergeLinear()

void Merge::mergeLinear ( vector< HighVariable * > & highvec )

private

Speculatively merge all HighVariables in the given list as well as possible.

The variables are first sorted by the index of the earliest block in their range. Then proceeding in order, an attempt is made to merge each variable with the first. The attempt fails if the speculative test doesn't pass or if there are Cover intersections, in which case that particular merge is skipped.

References compareHighByBlock(), merge(), mergeTestSpeculative(), and updateHigh().

Referenced by mergeByDatatype().

◆ mergeMarker()

void Merge::mergeMarker ( void )

Force the merge of input and output Varnodes to MULTIEQUAL and INDIRECT ops.

Run through all MULTIEQUAL and INDIRECT ops in the function. Force the merge of each input Varnode with the output Varnode, doing data-flow modification if necessary to resolve Cover intersections.

References Funcdata::beginOpAlive(), PcodeOp::code(), CPUI_INDIRECT, data, Funcdata::endOpAlive(), PcodeOp::isIndirectCreation(), PcodeOp::isMarker(), mergeIndirect(), and mergeOp().

Referenced by ActionMergeRequired::apply().

◆ mergeOp()

void Merge::mergeOp ( PcodeOp * op )

private

Force the merge of all input and output Varnodes for the given PcodeOp.

Data-flow for specific input and output Varnodes are snipped until everything can be merged.

Parameters

op	is the given PcodeOp

References PcodeOp::code(), CPUI_INDIRECT, Varnode::getHigh(), PcodeOp::getIn(), PcodeOp::getOut(), PcodeOp::getSeqNum(), merge(), mergeTest(), mergeTestRequired(), PcodeOp::numInput(), trimOpInput(), and trimOpOutput().

Referenced by mergeIndirect(), and mergeMarker().

◆ mergeOpcode()

void Merge::mergeOpcode ( OpCode opc )

Try to force merges of input to output for all p-code ops of a given type.

For a given opcode, run through all ops in the function in block/address order and try to merge each input HighVariable with the output HighVariable. If this would introduce Cover intersections, the merge is skipped. This is generally used to try to merge the input and output of COPY ops if possible.

Parameters

opc	is the op-code type to merge

References BlockBasic::beginOp(), PcodeOp::code(), data, BlockBasic::endOp(), Funcdata::getBasicBlocks(), Varnode::getHigh(), PcodeOp::getIn(), PcodeOp::getOut(), merge(), mergeTestBasic(), mergeTestRequired(), and PcodeOp::numInput().

Referenced by ActionMergeCopy::apply().

◆ mergeRangeMust()

void Merge::mergeRangeMust	(	VarnodeLocSet::const_iterator	startiter,
		VarnodeLocSet::const_iterator	enditer
	)

private

Force the merge of a ranges of Varnodes with the same size and storage address.

The list of Varnodes to be merged is provided as a range in the main location sorted container. Any Cover intersection is assumed to already be snipped, so any problems with merging cause an exception to be thrown.

Parameters

startiter	is the beginning of the range of Varnodes with the same storage address
enditer	is the end of the range

References Varnode::getHigh(), Varnode::isSpacebase(), merge(), and mergeTestBasic().

Referenced by mergeAddrTied().

◆ mergeTest()

bool Merge::mergeTest	(	HighVariable *	high,
		vector< HighVariable * > &	tmplist
	)

Test for intersections between a given HighVariable and a list of other HighVariables.

If there is any Cover intersection between the given HighVariable and one in the list, this routine returns false. Otherwise, the given HighVariable is added to the end of the list and true is returned.

Parameters

high	is the given HighVariable
tmplist	is the list of HighVariables to test against

Returns: true if there are no pairwise intersections.

References HighVariable::hasCover(), and intersection().

Referenced by mergeOp().

◆ mergeTestAdjacent()

bool Merge::mergeTestAdjacent	(	HighVariable *	high_out,
		HighVariable *	high_in
	)

staticprivate

Adjacency tests for merging Varnodes that are input or output to the same p-code op.

All the required tests (mergeTestRequired()) are performed, and then some additional tests are performed. This does not perform any Cover tests.

Parameters

high_out	is the output HighVariable to test
high_in	is the input HighVariable to test

Returns: true if tests pass and the HighVariables are not forbidden to merge

References HighVariable::getInputVarnode(), HighVariable::getType(), Varnode::isIllegalInput(), Varnode::isIndirectOnly(), HighVariable::isInput(), HighVariable::isNameLock(), and mergeTestRequired().

Referenced by mergeAdjacent(), and mergeTestSpeculative().

◆ mergeTestBasic()

bool Merge::mergeTestBasic ( Varnode * vn )

staticprivate

A test if the given Varnode can ever be merged.

Some Varnodes (constants, annotations, implied, spacebase) are never merged with another Varnode.

Parameters

vn	is the Varnode to test

Returns: true if the Varnode is not forbidden from ever merging

References Varnode::hasCover(), Varnode::isImplied(), and Varnode::isSpacebase().

Referenced by mergeAdjacent(), mergeByDatatype(), mergeOpcode(), and mergeRangeMust().

◆ mergeTestRequired()

bool Merge::mergeTestRequired	(	HighVariable *	high_out,
		HighVariable *	high_in
	)

staticprivate

Required tests to merge HighVariables that are not Cover related.

This is designed to short circuit merge tests, when we know properties of the two HighVariables preclude merging. For example, you can't merge HighVariables if:

They are locked to different data-types
They are both mapped to different address ranges
One is a parameter one is a global

Parameters

high_out	is the first HighVariable to test
high_in	is the second HighVariable to test

Returns: true if tests pass and the HighVariables are not forbidden to merge

References Varnode::getAddr(), HighVariable::getTiedVarnode(), HighVariable::getType(), HighVariable::isAddrTied(), HighVariable::isExtraOut(), HighVariable::isInput(), HighVariable::isPersist(), and HighVariable::isTypeLock().

Referenced by mergeIndirect(), mergeOp(), mergeOpcode(), and mergeTestAdjacent().

◆ mergeTestSpeculative()

bool Merge::mergeTestSpeculative	(	HighVariable *	high_out,
		HighVariable *	high_in
	)

staticprivate

Speculative tests for merging HighVariables that are not Cover related.

This does all the required and adjacency merge tests and then performs additional tests required for speculative merges.

Parameters

high_out	is the first HighVariable to test
high_in	is the second HighVariable to test

Returns: true if tests pass and the HighVariables are not forbidden to merge

References HighVariable::isAddrTied(), HighVariable::isInput(), HighVariable::isMapped(), HighVariable::isPersist(), and mergeTestAdjacent().

Referenced by mergeLinear().

◆ purgeHigh()

void Merge::purgeHigh ( HighVariable * high )

private

Remove cached intersection tests for a given HighVariable.

All tests for pairs where either the first or second HighVariable matches the given one are removed.

Parameters

high	is the given HighVariable to purge

References highedgemap.

Referenced by updateHigh().

◆ snipIndirect()

void Merge::snipIndirect ( PcodeOp * indop )

private

Snip instances of the input of an INDIRECT op that interfere with its output.

Examine the input and output HighVariable for the given INDIRECT op. Varnode instances of the input that intersect the output Cover are snipped by creating a new COPY op from the input to a new temporary and then replacing the Varnode reads with the temporary.

Parameters

indop is the given INDIRECT op

References collectCorrectable(), collectCovering(), CPUI_COPY, data, PcodeOp::getAddr(), Varnode::getAddr(), Varnode::getHigh(), PcodeOp::getIn(), PcodeOp::getOpFromConst(), PcodeOp::getOut(), Varnode::getSize(), Varnode::getType(), Funcdata::newOp(), Funcdata::newUnique(), Funcdata::opInsertBefore(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), and Funcdata::opSetOutput().

Referenced by mergeIndirect().

◆ snipReads()

void Merge::snipReads	(	Varnode *	vn,
		list< PcodeOp * > &	markedop
	)

private

Snip off set of read p-code ops for a given Varnode.

The data-flow for the given Varnode is truncated by creating a COPY p-code from the Varnode into a new temporary Varnode, then replacing the Varnode reads for a specific set of p-code ops with the temporary.

Parameters

vn	is the given Varnode
markedop	is the specific set of PcodeOps reading the Varnode

References PcodeOp::code(), CPUI_COPY, CPUI_INDIRECT, data, PcodeOp::getAddr(), Varnode::getAddr(), Funcdata::getBasicBlocks(), BlockGraph::getBlock(), Varnode::getDef(), PcodeOp::getIn(), PcodeOp::getOpFromConst(), PcodeOp::getParent(), Varnode::getSize(), BlockBasic::getStart(), Varnode::getType(), Varnode::isInput(), Funcdata::newOp(), Funcdata::newUnique(), PcodeOp::numInput(), Funcdata::opInsertAfter(), Funcdata::opInsertBegin(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), and Funcdata::opSetOutput().

Referenced by eliminateIntersect().

◆ trimOpInput()

void Merge::trimOpInput	(	PcodeOp *	op,
		int4	slot
	)

private

Trim the input HighVariable of the given PcodeOp so that its Cover is tiny.

The given PcodeOp is assumed to force merging so that input and output Covers shouldn't intersect. A new COPY is inserted right before the given PcodeOp with a new unique output that replaces the specified input, disassociating it from the other original inputs and output.

Parameters

op	is the given PcodeOp
slot	is the specified slot of the input Varnode to be trimmed

References PcodeOp::code(), CPUI_COPY, CPUI_MULTIEQUAL, data, PcodeOp::getAddr(), PcodeOp::getIn(), FlowBlock::getIn(), PcodeOp::getParent(), Varnode::getSize(), BlockBasic::getStop(), Varnode::getType(), Funcdata::newOp(), Funcdata::newUnique(), Funcdata::opInsertBefore(), Funcdata::opInsertEnd(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), and Funcdata::opSetOutput().

Referenced by mergeOp().

◆ trimOpOutput()

void Merge::trimOpOutput ( PcodeOp * op )

private

Trim the output HighVariable of the given PcodeOp so that its Cover is tiny.

The given PcodeOp is assumed to force merging so that input and output Covers shouldn't intersect. The original PcodeOp output is moved so that it becomes the output of a new COPY, disassociating the original output Varnode from the inputs.

Parameters

op	is the given PcodeOp

References PcodeOp::code(), CPUI_COPY, CPUI_INDIRECT, data, PcodeOp::getAddr(), Varnode::getAddr(), PcodeOp::getIn(), PcodeOp::getOpFromConst(), PcodeOp::getOut(), Varnode::getSize(), Varnode::getType(), Funcdata::newOp(), Funcdata::newUnique(), Funcdata::opInsertAfter(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), and Funcdata::opSetOutput().

Referenced by mergeOp().

◆ unifyAddress()

void Merge::unifyAddress	(	VarnodeLocSet::const_iterator	startiter,
		VarnodeLocSet::const_iterator	enditer
	)

private

Make sure all Varnodes with the same storage address and size can be merged.

The list of Varnodes to be merged is provided as a range in the main location sorted container. Any discovered intersection is snipped by splitting data-flow for one of the Varnodes into two or more flows, which involves insert new COPY ops and temporaries.

Parameters

startiter	is the beginning of the range of Varnodes with the same storage address
enditer	is the end of the range

References eliminateIntersect().

Referenced by mergeAddrTied().

◆ updateHigh()

bool Merge::updateHigh ( HighVariable * a )

private

Make sure given HighVariable's Cover is up-to-date.

As manipulations are made, Cover information gets out of date. A dirty flag is used to indicate a particular HighVariable Cover is out-of-date. This routine checks the dirty flag and updates the Cover information if it is set.

Parameters

a	is the HighVariable to update

Returns: true if the HighVariable was not originally dirty

References HighVariable::coverdirty, HighVariable::getInstance(), HighVariable::highflags, HighVariable::numInstances(), purgeHigh(), HighVariable::updateCover(), and Varnode::updateCover().

Referenced by inflate(), inflateTest(), intersection(), and mergeLinear().

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

merge.hh
merge.cc

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Function Documentation

◆ blockIntersection()

◆ collectCorrectable()

◆ collectCovering()

◆ compareHighByBlock()

◆ eliminateIntersect()

◆ findSingleCopy()

◆ hideShadows()

◆ inflate()

◆ inflateTest()

◆ intersection()

◆ merge()

◆ mergeAddrTied()

◆ mergeAdjacent()

◆ mergeByDatatype()

◆ mergeIndirect()

◆ mergeLinear()

◆ mergeMarker()

◆ mergeOp()

◆ mergeOpcode()

◆ mergeRangeMust()

◆ mergeTest()

◆ mergeTestAdjacent()

◆ mergeTestBasic()

◆ mergeTestRequired()

◆ mergeTestSpeculative()

◆ purgeHigh()

◆ snipIndirect()

◆ snipReads()

◆ trimOpInput()

◆ trimOpOutput()

◆ unifyAddress()

◆ updateHigh()