A basic jump-table model with an added default address path. More...

#include <jumptable.hh>

Inheritance diagram for JumpBasic2:

Public Member Functions
	JumpBasic2 (JumpTable *jt)
	Constructor.

void	initializeStart (const PathMeld &pathMeld)
	Pass in the prior PathMeld calculation.

virtual bool	recoverModel (Funcdata fd, PcodeOp indop, uint4 matchsize, uint4 maxtablesize)
	Attempt to recover details of the model, given a specific BRANCHIND. More...

virtual void	findUnnormalized (uint4 maxaddsub, uint4 maxleftright, uint4 maxext)
	Recover the unnormalized switch variable. More...

virtual JumpModel *	clone (JumpTable *jt) const
	Clone this model.

virtual void	clear (void)
	Clear any non-permanent aspects of the model.

Public Member Functions inherited from JumpBasic
	JumpBasic (JumpTable *jt)
	Construct given a parent JumpTable.

const PathMeld &	getPathMeld (void) const
	Get the possible of paths to the switch.

const JumpValuesRange *	getValueRange (void) const
	Get the normalized value iterator.

virtual bool	isOverride (void) const
	Return true if this model was manually overridden.

virtual int4	getTableSize (void) const
	Return the number of entries in the address table.

virtual void	buildAddresses (Funcdata fd, PcodeOp indop, vector< Address > &addresstable, vector< LoadTable > *loadpoints) const
	Construct the explicit list of target addresses (the Address Table) from this model. More...

virtual void	buildLabels (Funcdata fd, vector< Address > &addresstable, vector< uintb > &label, const JumpModel orig) const
	Recover case labels associated with the Address table. More...

virtual Varnode *	foldInNormalization (Funcdata fd, PcodeOp indop)
	Do normalization of the given switch specific to this model. More...

virtual bool	foldInGuards (Funcdata fd, JumpTable jump)
	Eliminate any guard code involved in computing the switch destination. More...

virtual bool	sanityCheck (Funcdata fd, PcodeOp indop, vector< Address > &addresstable)
	Perform a sanity check on recovered addresses. More...

Public Member Functions inherited from JumpModel
	JumpModel (JumpTable *jt)
	Construct given a parent jump-table.

virtual	~JumpModel (void)
	Destructor.

virtual void	saveXml (ostream &s) const
	Save this model as an XML tag.

virtual void	restoreXml (const Element el, Architecture glb)
	Restore this model from an XML tag.

Private Member Functions
bool	checkNormalDominance (void) const
	Check if the block that defines the normalized switch variable dominates the block containing the switch. More...

virtual bool	foldInOneGuard (Funcdata fd, GuardRecord &guard, JumpTable jump)
	Eliminate the given guard to this switch. More...

Private Attributes
Varnode *	extravn
	The extra Varnode holding the default value.

PathMeld	origPathMeld
	The set of paths that produce non-default addresses.

Additional Inherited Members
Protected Member Functions inherited from JumpBasic
void	findDeterminingVarnodes (PcodeOp *op, int4 slot)
	Calculate the initial set of Varnodes that might be switch variables. More...

void	analyzeGuards (BlockBasic *bl, int4 pathout)
	Analyze CBRANCHs leading up to the given basic-block as a potential switch guard. More...

void	calcRange (Varnode *vn, CircleRange &rng) const
	Calculate the range of values in the given Varnode that direct control-flow to the switch. More...

void	findSmallestNormal (uint4 matchsize)
	Find the putative switch variable with the smallest range of values reaching the switch. More...

void	findNormalized (Funcdata fd, BlockBasic rootbl, int4 pathout, uint4 matchsize, uint4 maxtablesize)
	Do all the work necessary to recover the normalized switch variable. More...

void	markFoldableGuards ()
	Mark the guard CBRANCHs that are truly part of the model. More...

void	markModel (bool val)
	Mark (or unmark) all PcodeOps involved in the model. More...

bool	flowsOnlyToModel (Varnode vn, PcodeOp trailOp)
	Check if the given Varnode flows to anything other than this model. More...

Static Protected Member Functions inherited from JumpBasic
static bool	isprune (Varnode *vn)
	Do we prune in here in our depth-first search for the normalized switch variable. More...

static bool	ispoint (Varnode *vn)
	Is it possible for the given Varnode to be a switch variable? More...

static int4	getStride (Varnode *vn)
	Get the step/stride associated with the Varnode. More...

static uintb	backup2Switch (Funcdata fd, uintb output, Varnode outvn, Varnode *invn)
	Back up the constant value in the output Varnode to the value in the input Varnode. More...

Protected Attributes inherited from JumpBasic
JumpValuesRange *	jrange
	Range of values for the (normalized) switch variable.

PathMeld	pathMeld
	Set of PcodeOps and Varnodes producing the final target addresses.

vector< GuardRecord >	selectguards
	Any guards associated with model.

int4	varnodeIndex
	Position of the normalized switch Varnode within PathMeld.

Varnode *	normalvn
	Normalized switch Varnode.

Varnode *	switchvn
	Unnormalized switch Varnode.

Protected Attributes inherited from JumpModel
JumpTable *	jumptable
	The jump-table that is building this model.

Detailed Description

A basic jump-table model with an added default address path.

This model expects two paths to the switch, 1 from a default value, 1 from the other values that hit the switch If A is the guarding control-flow block, C is the block setting the default value, and S the switch block itself, We expect one of the following situations:

A -> C or S and C -> S
A -> C or D and C -> S D -> S
C -> S and S -> A A -> S or "out of loop", i.e. S is in a loop, and the guard block doubles as the loop condition

This builds on the analysis performed for JumpBasic, which fails because there are too many paths to the BRANCHIND, preventing the guards from being interpreted properly. This class expects to reuse the PathMeld calculation from JumpBasic.

Member Function Documentation

bool JumpBasic2::checkNormalDominance ( void ) const

private

Check if the block that defines the normalized switch variable dominates the block containing the switch.

Returns: true if the switch block is dominated

References FlowBlock::getImmedDom(), and FlowBlock::getParent().

void JumpBasic2::findUnnormalized	(	uint4	maxaddsub,
		uint4	maxleftright,
		uint4	maxext
	)

virtual

Recover the unnormalized switch variable.

The normalized switch variable must already be recovered. The amount of normalization between the two switch variables can be restricted.

Parameters

maxaddsub	is a restriction on arithmetic operations
maxleftright	is a restriction on shift operations
maxext	is a restriction on extension operations

Reimplemented from JumpBasic.

References JumpBasic::findUnnormalized(), and PcodeOp::getIn().

bool JumpBasic2::foldInOneGuard	(	Funcdata *	fd,
		GuardRecord &	guard,
		JumpTable *	jump
	)

privatevirtual

Eliminate the given guard to this switch.

We disarm the guard instructions by making the guard condition always false. If the simplification removes the unusable branches, we are left with only one path through the switch.

Parameters

fd	is the function containing the switch
guard	is a description of the particular guard mechanism
jump	is the JumpTable owning this model

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

Reimplemented from JumpBasic.

References GuardRecord::clear(), and JumpTable::setLastAsMostCommon().

bool JumpBasic2::recoverModel	(	Funcdata *	fd,
		PcodeOp *	indop,
		uint4	matchsize,
		uint4	maxtablesize
	)

virtual

Attempt to recover details of the model, given a specific BRANCHIND.

This generally recovers the normalized switch variable and any guards.

Parameters

fd	is the function containing the switch
indop	is the given BRANCHIND
matchsize	is the expected number of address table entries to recover, or 0 for no expectation
maxtablesize	is maximum number of address table entries to allow in the model

Returns: true if details of the model were successfully recovered

Reimplemented from JumpBasic.

References PcodeOp::code(), CPUI_COPY, CPUI_MULTIEQUAL, Varnode::getDef(), PcodeOp::getIn(), FlowBlock::getIn(), FlowBlock::getInRevIndex(), Varnode::getOffset(), PcodeOp::getParent(), Varnode::isConstant(), Varnode::isWritten(), PcodeOp::numInput(), JumpValuesRangeDefault::setDefaultOp(), JumpValuesRangeDefault::setDefaultVn(), and JumpValuesRangeDefault::setExtraValue().

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

jumptable.hh
jumptable.cc

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation