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

#include <merge.hh>

Public Member Functions
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...

void	mergeMultiEntry (void)
	Merge together Varnodes mapped to SymbolEntrys from the same Symbol. More...

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

void	processCopyTrims (void)
	Try to reduce/eliminate COPYs produced by the merge trimming process. More...

void	markInternalCopies (void)
	Mark redundant/internal COPY PcodeOps. More...

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

◆ 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

◆ 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

◆ 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

◆ 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

◆ markInternalCopies()

void Merge::markInternalCopies ( void )

Mark redundant/internal COPY PcodeOps.

Run through all COPY, SUBPIECE, and PIECE operations (PcodeOps that copy data) and characterize those that are internal (copy data between storage locations representing the same variable) or redundant (perform the same copy as an earlier operation). These, as a result, are not printed in the final source code representation.

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

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

◆ 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

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

◆ mergeMultiEntry()

void Merge::mergeMultiEntry ( void )

Merge together Varnodes mapped to SymbolEntrys from the same Symbol.

Symbols that have more than one SymbolEntry may attach to more than one Varnode. These Varnodes need to be merged to properly represent a single variable.

◆ 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

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

◆ processCopyTrims()

void Merge::processCopyTrims ( void )

Try to reduce/eliminate COPYs produced by the merge trimming process.

In order to force merging of certain Varnodes, extra COPY operations may be inserted to reduce their Cover ranges, and multiple COPYs from the same Varnode can be created this way. This method collects sets of COPYs generated in this way that have the same input Varnode and then tries to replace the COPYs with fewer or a single COPY.

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

merge.hh
merge.cc

Public Member Functions

Detailed Description

Member Function Documentation

◆ hideShadows()

◆ inflate()

◆ inflateTest()

◆ intersection()

◆ markInternalCopies()

◆ mergeAddrTied()

◆ mergeAdjacent()

◆ mergeByDatatype()

◆ mergeMarker()

◆ mergeMultiEntry()

◆ mergeOpcode()

◆ mergeTest()

◆ processCopyTrims()