Dead code removal. Eliminate dead p-code ops. More...

#include <coreaction.hh>

Inheritance diagram for ActionDeadCode:

Public Member Functions
	ActionDeadCode (const string &g)
	Constructor.

virtual Action *	clone (const ActionGroupList &grouplist) const
	Clone the Action. More...

virtual int4	apply (Funcdata &data)
	Make a single attempt to apply this Action. More...

Public Member Functions inherited from Action
	Action (uint4 f, const string &nm, const string &g)
	Base constructor for an Action. More...

virtual	~Action (void)
	Destructor.

virtual void	printStatistics (ostream &s) const
	Dump statistics to stream. More...

int4	perform (Funcdata &data)
	Perform this action (if necessary) More...

bool	setBreakPoint (uint4 tp, const string &specify)
	Set a breakpoint on this action. More...

virtual void	clearBreakPoints (void)
	Clear all breakpoints set on this Action.

bool	setWarning (bool val, const string &specify)
	Set a warning on this action. More...

bool	disableRule (const string &specify)
	Disable a specific Rule within this. More...

bool	enableRule (const string &specify)
	Enable a specific Rule within this. More...

const string &	getName (void) const
	Get the Action's name.

const string &	getGroup (void) const
	Get the Action's group.

uint4	getStatus (void) const
	Get the current status of this Action.

uint4	getNumTests (void)
	Get the number of times apply() was invoked.

uint4	getNumApply (void)

virtual void	reset (Funcdata &data)
	Reset the Action for a new function. More...

virtual void	resetStats (void)
	Reset all the counts to zero. More...

virtual int4	print (ostream &s, int4 num, int4 depth) const
	Print a description of this Action to stream. More...

virtual void	printState (ostream &s) const
	Print status to stream. More...

virtual void	saveXml (ostream &s) const
	Save specifics of this action to stream.

virtual void	restoreXml (const Element el, Funcdata fd)
	Load specifics of action from XML.

virtual Action *	getSubAction (const string &specify)
	Retrieve a specific sub-action by name. More...

virtual Rule *	getSubRule (const string &specify)
	Retrieve a specific sub-rule by name. More...

Static Private Member Functions
static void	pushConsumed (uintb val, Varnode vn, vector< Varnode > &worklist)

static void	propagateConsumed (vector< Varnode * > &worklist)
	Propagate the consumed value for one Varnode. More...

static bool	neverConsumed (Varnode *vn, Funcdata &data)
	Deal with unconsumed Varnodes. More...

static void	markConsumedParameters (FuncCallSpecs fc, vector< Varnode > &worklist)
	Determine how the given sub-function parameters are consumed. More...

static uintb	gatherConsumedReturn (Funcdata &data)
	Determine how the return values for the given function are consumed. More...

static bool	isEventualConstant (Varnode *vn, int4 addCount, int4 loadCount)
	Determine if the given Varnode may eventually collapse to a constant. More...

static bool	lastChanceLoad (Funcdata &data, vector< Varnode * > &worklist)
	Check if there are any unconsumed LOADs that may be from volatile addresses. More...

Additional Inherited Members
Public Types inherited from Action
enum	ruleflags { rule_repeatapply = 4, rule_onceperfunc = 8, rule_oneactperfunc = 16, rule_debug = 32, rule_warnings_on = 64, rule_warnings_given = 128 }
	Boolean behavior properties governing this particular Action. More...

enum	statusflags { status_start =1, status_breakstarthit =2, status_repeat =4, status_mid =8, status_end =16, status_actionbreak =32 }
	Boolean properties describing the status of an action. More...

enum	breakflags { break_start = 1, tmpbreak_start = 2, break_action = 4, tmpbreak_action = 8 }
	Break points associated with an Action. More...

Protected Member Functions inherited from Action
void	issueWarning (Architecture *glb)
	Warn that this Action has applied. More...

bool	checkStartBreak (void)
	Check start breakpoint. More...

bool	checkActionBreak (void)
	Check action breakpoint. More...

void	turnOnWarnings (void)
	Enable warnings for this Action.

void	turnOffWarnings (void)
	Disable warnings for this Action.

Protected Attributes inherited from Action
int4	lcount
	Changes not including last call to apply()

int4	count
	Number of changes made by this action so far.

uint4	status
	Current status.

uint4	breakpoint
	Breakpoint properties.

uint4	flags
	Behavior properties.

uint4	count_tests
	Number of times apply() has been called.

uint4	count_apply
	Number of times apply() made changes.

string	name
	Name of the action.

string	basegroup
	Base group this action belongs to.

Detailed Description

Dead code removal. Eliminate dead p-code ops.

This is a very fine grained algorithm, it detects usage of individual bits within the Varnode, not just use of the Varnode itself. Each Varnode has a consumed word, which indicates if a bit in the Varnode is being used, and it has two flags layed out as follows:

Varnode::lisconsume = varnode is in the working list
Varnode::vacconsume = vacuously used bit there is a path from the varnode through assignment op outputs down to a varnode that is used

The algorithm works by back propagating the consumed value up from the output of the op to its inputs, starting with a set of seed Varnodes which are marked as completely used (function inputs, branch conditions, ...) For each propagation the particular op being passed through can transform the "bit usage" vector of the output to obtain the input.

Member Function Documentation

int4 ActionDeadCode::apply ( Funcdata & data )

virtual

Make a single attempt to apply this Action.

This is the main entry point for applying changes to a function that are specific to this Action. The method can inspect whatever it wants to decide if the Action does or does not apply. Changes are indicated by incrementing the count field.

Parameters

data	is the function to inspect/modify

Returns: 0 for a complete application, -1 for a partial completion (due to breakpoint)

Implements Action.

References Funcdata::beginLoc(), Funcdata::beginOpAlive(), Varnode::clearAddrForce(), Varnode::clearConsumeList(), Varnode::clearConsumeVacuous(), Funcdata::clearDeadOps(), Funcdata::clearDeadVarnodes(), PcodeOp::clearIndirectSource(), PcodeOp::code(), CPUI_BRANCHIND, CPUI_RETURN, Funcdata::deadRemovalAllowed(), AddrSpace::doesDeadcode(), Funcdata::endLoc(), Funcdata::endOpAlive(), Funcdata::findJumpTable(), Funcdata::getArch(), Funcdata::getCallSpecs(), Varnode::getConsume(), Varnode::getDef(), PcodeOp::getIn(), PcodeOp::getOut(), AddrSpaceManager::getSpace(), JumpTable::getSwitchVarConsume(), Varnode::isAddrForce(), PcodeOp::isAssignment(), Varnode::isAutoLive(), PcodeOp::isCall(), PcodeOp::isCallWithoutSpec(), Varnode::isConsumeVacuous(), Varnode::isDirectWrite(), Varnode::isWritten(), Funcdata::numCalls(), PcodeOp::numInput(), AddrSpaceManager::numSpaces(), Funcdata::opDestroy(), Funcdata::opUnsetOutput(), Funcdata::seenDeadcode(), and Varnode::setConsume().

virtual Action* ActionDeadCode::clone ( const ActionGroupList & grouplist ) const

inlinevirtual

Clone the Action.

If this Action is a member of one of the groups in the grouplist, this returns a clone of the Action, otherwise NULL is returned.

Parameters

grouplist is the list of groups being cloned

Returns: the cloned Action or NULL

Implements Action.

References ActionStart::apply(), ActionGroupList::contains(), and Action::getGroup().

uintb ActionDeadCode::gatherConsumedReturn ( Funcdata & data )

staticprivate

Determine how the return values for the given function are consumed.

Examine each CPUI_RETURN to see how the Varnode input is consumed. If the function's prototype is locked, assume the Varnode is entirely consumed. If there are no CPUI_RETURN ops, return 0

Parameters

data	is the given function

Returns: the bit mask of what is consumed

References Funcdata::beginOp(), calc_mask(), CPUI_RETURN, Funcdata::endOp(), Funcdata::getActiveOutput(), Funcdata::getFuncProto(), PcodeOp::getIn(), Varnode::getNZMask(), FuncProto::getReturnBytesConsumed(), PcodeOp::isDead(), FuncProto::isOutputLocked(), minimalmask(), and PcodeOp::numInput().

bool ActionDeadCode::isEventualConstant	(	Varnode *	vn,
		int4	addCount,
		int4	loadCount
	)

staticprivate

Determine if the given Varnode may eventually collapse to a constant.

Recursively check if the Varnode is either:

Copied from a constant
The result of adding constants
Loaded from a pointer that is a constant

Parameters

vn	is the given Varnode
addCount	is the number of CPUI_INT_ADD operations seen so far
loadCount	is the number of CPUI_LOAD operations seen so far

Returns: true if the Varnode (might) collapse to a constant

References PcodeOp::code(), CPUI_COPY, CPUI_INT_ADD, CPUI_INT_LEFT, CPUI_INT_MULT, CPUI_INT_RIGHT, CPUI_INT_SEXT, CPUI_INT_SRIGHT, CPUI_INT_ZEXT, CPUI_LOAD, Varnode::getDef(), PcodeOp::getIn(), Varnode::isConstant(), and Varnode::isWritten().

bool ActionDeadCode::lastChanceLoad	(	Funcdata &	data,
		vector< Varnode * > &	worklist
	)

staticprivate

Check if there are any unconsumed LOADs that may be from volatile addresses.

It may be too early to remove certain LOAD operations even though their result isn't consumed because it be of a volatile address with side effects. If a LOAD meets this criteria, it is added to the worklist and true is returned.

Parameters

data	is the function being analyzed

Returns: true if there was at least one LOAD added to the worklist

References Funcdata::beginOp(), CPUI_LOAD, Funcdata::endOp(), Funcdata::getHeritagePass(), PcodeOp::getIn(), PcodeOp::getOut(), Varnode::isConsumeVacuous(), PcodeOp::isDead(), Funcdata::isJumptableRecoveryOn(), and Varnode::setAutoLiveHold().

void ActionDeadCode::markConsumedParameters	(	FuncCallSpecs *	fc,
		vector< Varnode * > &	worklist
	)

staticprivate

Determine how the given sub-function parameters are consumed.

Set the consume property for each input Varnode of a CPUI_CALL or CPUI_CALLIND. If the prototype is locked, assume parameters are entirely consumed.

Parameters

fc	is the call specification for the given sub-function
worklist	will hold input Varnodes that can propagate their consume property

References calc_mask(), PcodeOp::getIn(), FuncCallSpecs::getInputBytesConsumed(), Varnode::getNZMask(), FuncCallSpecs::getOp(), Varnode::isAutoLive(), FuncCallSpecs::isInputActive(), FuncProto::isInputLocked(), minimalmask(), and PcodeOp::numInput().

bool ActionDeadCode::neverConsumed	(	Varnode *	vn,
		Funcdata &	data
	)

staticprivate

Deal with unconsumed Varnodes.

For a Varnode, none of whose bits are consumed, eliminate the PcodeOp defining it and replace Varnode inputs to ops that officially read it with zero constants.

Parameters

vn	is the Varnode
data	is the function being analyzed

Returns: true if the Varnode was eliminated

References Varnode::beginDescend(), Varnode::endDescend(), Varnode::getDef(), Varnode::getSize(), PcodeOp::getSlot(), PcodeOp::isCall(), Funcdata::newConstant(), Funcdata::opDestroy(), Funcdata::opSetInput(), and Funcdata::opUnsetOutput().

void ActionDeadCode::propagateConsumed ( vector< Varnode * > & worklist )

staticprivate

Propagate the consumed value for one Varnode.

The Varnode at the top of the stack is popped off, and its current consumed value is propagated backward to the inputs of the op that produced it.

Parameters

worklist is the current stack of dirty Varnodes

References calc_mask(), Varnode::characterizeOverlap(), Varnode::clearConsumeList(), PcodeOp::code(), coveringmask(), CPUI_CALL, CPUI_CALLIND, CPUI_COPY, CPUI_EXTRACT, CPUI_INDIRECT, CPUI_INSERT, CPUI_INT_ADD, CPUI_INT_AND, CPUI_INT_EQUAL, CPUI_INT_LEFT, CPUI_INT_LESS, CPUI_INT_LESSEQUAL, CPUI_INT_MULT, CPUI_INT_NEGATE, CPUI_INT_NOTEQUAL, CPUI_INT_OR, CPUI_INT_RIGHT, CPUI_INT_SEXT, CPUI_INT_SUB, CPUI_INT_XOR, CPUI_INT_ZEXT, CPUI_MULTIEQUAL, CPUI_PIECE, CPUI_POPCOUNT, CPUI_SUBPIECE, Varnode::getAddr(), Varnode::getConsume(), Varnode::getDef(), PcodeOp::getIn(), Varnode::getNZMask(), Varnode::getOffset(), PcodeOp::getOpFromConst(), PcodeOp::getOut(), Varnode::getSize(), Varnode::getSpace(), AddrSpace::getType(), IPTR_IOP, Varnode::isConstant(), PcodeOp::isDead(), leastsigbit_set(), PcodeOp::numInput(), and PcodeOp::setIndirectSource().

void ActionDeadCode::pushConsumed	(	uintb	val,
		Varnode *	vn,
		vector< Varnode * > &	worklist
	)

inlinestaticprivate

Given a new consume value to push to a Varnode, determine if this changes the Varnodes consume value and whether to push the Varnode onto the work-list.

Parameters

val	is the new consume value
vn	is the Varnode to push to
worklist	is the current work-list

References calc_mask(), Varnode::getConsume(), Varnode::getSize(), Varnode::isConsumeList(), Varnode::isConsumeVacuous(), Varnode::isWritten(), Varnode::setConsume(), Varnode::setConsumeList(), and Varnode::setConsumeVacuous().

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

coreaction.hh
coreaction.cc

Public Member Functions

Static Private Member Functions

Additional Inherited Members

Detailed Description

Member Function Documentation