Structure for sorting out pointer expression trees. More...

#include <ruleaction.hh>

Public Member Functions
	AddTreeState (Funcdata &d, PcodeOp *op, int4 slot)
	Construct given root of ADD tree and pointer.

bool	apply (void)
	Attempt to transform the pointer expression. More...

Private Member Functions
uint4	findArrayHint (void) const
	Look for evidence of an array in a sub-component. More...

bool	hasMatchingSubType (uintb off, uint4 arrayHint, uintb *newoff) const
	Given an offset into the base data-type and array hints find sub-component being referenced. More...

bool	checkMultTerm (Varnode vn, PcodeOp op, uintb treeCoeff)
	Accumulate details of INT_MULT term and continue traversal if appropriate. More...

bool	checkTerm (Varnode *vn, uintb treeCoeff)
	Accumulate details of given term and continue tree traversal. More...

bool	spanAddTree (PcodeOp *op, uintb treeCoeff)
	Walk the given sub-tree accumulating details. More...

void	calcSubtype (void)
	Calculate final sub-type offset. More...

Varnode *	buildMultiples (void)
	Build part of tree that is multiple of base size. More...

Varnode *	buildExtra (void)
	Build part of tree not accounted for by multiples or offset. More...

void	buildTree (void)
	Build the transformed ADD tree. More...

void	clear (void)
	Reset for a new ADD tree traversal.

Private Attributes
Funcdata &	data
	The function containing the expression.

PcodeOp *	baseOp
	Base of the ADD tree.

Varnode *	ptr
	The pointer varnode.

const TypePointer *	ct
	The pointer data-type.

const Datatype *	baseType
	The base data-type being pointed at.

int4	ptrsize
	Size of the pointer.

int4	size
	Size of data-type being pointed to (in address units) or 0 for open ended pointer.

uintb	ptrmask
	Mask for modulo calculations in ptr space.

uintb	offset
	Number of bytes we dig into the base data-type.

uintb	correct
	Number of bytes being double counted.

vector< Varnode * >	multiple
	Varnodes which are multiples of size.

vector< intb >	coeff
	Associated constant multiple.

vector< Varnode * >	nonmult
	Varnodes which are not multiples.

PcodeOp *	distributeOp
	A CPUI_INT_MULT op that needs to be distributed.

uintb	multsum
	Sum of multiple constants.

uintb	nonmultsum
	Sum of non-multiple constants.

bool	preventDistribution
	Do not distribute "multiply by constant" operation.

bool	isDistributeUsed
	Are terms produced by distributing used.

bool	isSubtype
	Is there a sub-type (using CPUI_PTRSUB)

bool	valid
	Set to true if the whole expression can be transformed.

Detailed Description

Structure for sorting out pointer expression trees.

Given a base pointer of known data-type and an additive expression involving the pointer, group the terms of the expression into:

A constant multiple of the base data-type
Non-constant multiples of the base data-type
An constant offset to a sub-component of the base data-type
An remaining terms

The multiple terms are rewritten using a CPUI_PTRADD. The constant offset is rewritten using a CPUI_PTRSUB. Other terms are added back in. Analysis may cause multiplication (CPUI_INT_MULT) by a constant to be distributed to its CPUI_INT_ADD input.

Member Function Documentation

bool AddTreeState::apply ( void )

Attempt to transform the pointer expression.

Returns: true if a transform was applied

References baseOp, buildTree(), calcSubtype(), clear(), Funcdata::collapseIntMultMult(), data, Funcdata::distributeIntMultAdd(), distributeOp, PcodeOp::getAddr(), PcodeOp::getIn(), isDistributeUsed, preventDistribution, Address::printRaw(), spanAddTree(), valid, and Funcdata::warningHeader().

Referenced by RulePtrArith::applyOp().

Varnode * AddTreeState::buildExtra ( void )

private

Build part of tree not accounted for by multiples or offset.

Create a subtree summing all the elements that aren't multiples of the base data-type size. Correct for any double counting of non-multiple constants. Return the final Varnode holding the sum or null if there are no terms.

Returns: the final Varnode or null

References baseOp, correct, CPUI_INT_ADD, data, Varnode::getOffset(), PcodeOp::getOut(), Varnode::isConstant(), Funcdata::newConstant(), Funcdata::newOpBefore(), nonmult, offset, ptrmask, ptrsize, and uintb_negate().

Referenced by buildTree().

Varnode * AddTreeState::buildMultiples ( void )

private

Build part of tree that is multiple of base size.

Construct part of the tree that sums to a multiple of the base data-type size. This value will be added to the base pointer as a CPUI_PTRADD. The final Varnode produced by the sum is returned. If there are no multiples, null is returned.

Returns: the output Varnode of the multiple tree or null

References baseOp, coeff, CPUI_INT_ADD, CPUI_INT_MULT, data, PcodeOp::getOut(), multiple, multsum, Funcdata::newConstant(), Funcdata::newOpBefore(), ptrmask, ptrsize, sign_extend(), and size.

Referenced by buildTree().

void AddTreeState::buildTree ( void )

private

Build the transformed ADD tree.

The original ADD tree has been successfully spit into multiple and non-multiple pieces. Rewrite the tree as a pointer expression, putting any multiple pieces into a PTRADD operation, creating a PTRSUB if a sub data-type offset has been calculated, and preserving and remaining terms.

References baseOp, buildExtra(), buildMultiples(), CPUI_INT_ADD, CPUI_PTRADD, CPUI_PTRSUB, data, PcodeOp::getAddr(), PcodeOp::getOut(), isSubtype, Funcdata::newConstant(), Funcdata::newOpBefore(), offset, Funcdata::opDestroy(), Funcdata::opSetOutput(), ptr, ptrsize, size, and Funcdata::warning().

Referenced by apply().

void AddTreeState::calcSubtype ( void )

private

Calculate final sub-type offset.

Make final calcultions to determine if a pointer to a sub data-type of the base data-type is being calculated, which will result in a CPUI_PTRSUB being generated.

References AddrSpace::addressToByte(), baseType, AddrSpace::byteToAddress(), correct, ct, findArrayHint(), Datatype::getMetatype(), Datatype::getSize(), TypePointer::getWordSize(), hasMatchingSubType(), isSubtype, multiple, multsum, nonmult, nonmultsum, offset, ptrmask, ptrsize, sign_extend(), size, TYPE_ARRAY, TYPE_SPACEBASE, TYPE_STRUCT, and valid.

Referenced by apply().

bool AddTreeState::checkMultTerm	(	Varnode *	vn,
		PcodeOp *	op,
		uintb	treeCoeff
	)

private

Accumulate details of INT_MULT term and continue traversal if appropriate.

Examine a CPUI_INT_MULT element in the middle of the add tree. Determine if we treat the output simply as a leaf, or if the multiply needs to be distributed to an additive subtree. If the Varnode is a leaf of the tree, return true if it is considered a multiple of the base data-type size. If the Varnode is the root of another additive sub-tree, return true if no sub-node is a multiple.

Parameters

vn	is the output Varnode of the operation
op	is the CPUI_INT_MULT operation
treeCoeff	is constant multiple being applied to the node

Returns: true if there are no multiples of the base data-type size discovered

References PcodeOp::code(), coeff, CPUI_INT_ADD, distributeOp, Varnode::getDef(), PcodeOp::getIn(), Varnode::getOffset(), Varnode::getSize(), Varnode::isConstant(), isDistributeUsed, Varnode::isFree(), Varnode::isWritten(), multiple, preventDistribution, ptrmask, sign_extend(), size, spanAddTree(), and valid.

Referenced by checkTerm().

bool AddTreeState::checkTerm	(	Varnode *	vn,
		uintb	treeCoeff
	)

private

Accumulate details of given term and continue tree traversal.

If the given Varnode is a constant or multiplicative term, update totals. If the Varnode is additive, traverse its sub-terms.

Parameters

vn	is the given Varnode term
treeCoeff	is a constant multiple applied to the entire sub-tree

Returns: true if the sub-tree rooted at the given Varnode contains no multiples

References baseType, checkMultTerm(), PcodeOp::code(), CPUI_COPY, CPUI_INT_ADD, CPUI_INT_MULT, Varnode::getDef(), Datatype::getMetatype(), Varnode::getOffset(), Varnode::getSize(), Varnode::isConstant(), isDistributeUsed, Varnode::isFree(), Varnode::isWritten(), multsum, nonmultsum, ptr, sign_extend(), size, spanAddTree(), TYPE_ARRAY, TYPE_STRUCT, and valid.

Referenced by spanAddTree().

uint4 AddTreeState::findArrayHint ( void ) const

private

Look for evidence of an array in a sub-component.

Even if the current base data-type is not an array, the pointer expression may incorporate an array access for a sub component. This manifests as a non-constant non-multiple terms in the tree. If this term is itself defined by a CPUI_INT_MULT with a constant, the constant indicates a likely element size. Return a non-zero value, the likely element size, if there is evidence of a non-constant non-multiple term. Return zero otherwise.

Returns: a non-zero value indicating likely element size, or zero

References PcodeOp::code(), CPUI_INT_MULT, Varnode::getDef(), PcodeOp::getIn(), Varnode::getOffset(), Varnode::getSize(), Varnode::isConstant(), Varnode::isWritten(), nonmult, and sign_extend().

Referenced by calcSubtype().

bool AddTreeState::hasMatchingSubType	(	uintb	off,
		uint4	arrayHint,
		uintb *	newoff
	)		const

private

Given an offset into the base data-type and array hints find sub-component being referenced.

An explicit offset should target a specific sub data-type, but array indexing may confuse things. This method passes back the offset of the best matching component, searching among components that are nearby the given offset, preferring a matching array element size and a component start that is nearer to the offset.

Parameters

off	is the given offset into the data-type
arrayHint	if non-zero indicates array access, where the value is the element size
newoff	is used to pass back the actual offset of the selected component

Returns: true if a good component match was found

References baseType, AddrSpace::byteToAddressInt(), ct, Datatype::getSize(), Datatype::getSubType(), TypePointer::getWordSize(), Datatype::nearestArrayedComponentBackward(), and Datatype::nearestArrayedComponentForward().

Referenced by calcSubtype().

bool AddTreeState::spanAddTree	(	PcodeOp *	op,
		uintb	treeCoeff
	)

private

Walk the given sub-tree accumulating details.

Recursively walk the sub-tree from the given root. Terms that are a multiple of the base data-type size are accumulated either in the the sum of constant multiples or the container of non-constant multiples. Terms that are a non-multiple are accumulated either in the sum of constant non-multiples or the container of non-constant non-multiples. The constant non-multiples are counted twice, once in the sum, and once in the container. This routine returns true if no node of the sub-tree is considered a multiple of the base data-type size (or false if any node is considered a multiple).

Parameters

op	is the root of the sub-expression to traverse
treeCoeff	is a constant multiple applied to the entire additive tree

Returns: true if the given sub-tree contains no multiple nodes

References checkTerm(), PcodeOp::getIn(), nonmult, and valid.

Referenced by apply(), checkMultTerm(), and checkTerm().

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

ruleaction.hh
ruleaction.cc

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Function Documentation