Derive Varnode sizes and optimize p-code in SLEIGH Constructors. More...

#include <slgh_compile.hh>

Classes
struct	OptimizeRecord
	Description of how a temporary register is being used within a Constructor. More...

Public Member Functions
	ConsistencyChecker (SleighCompile sleigh, SubtableSymbol rt, bool unnecessary, bool warndead, bool warnlargetemp)
	Construct the consistency checker and optimizer. More...

bool	testSizeRestrictions (void)
	Test size consistency of all p-code. More...

bool	testTruncations (void)
	Test truncation validity of all p-code. More...

void	testLargeTemporary (void)
	Test for temporary Varnodes that are too large. More...

void	optimizeAll (void)
	Do COPY propagation optimization on all p-code.

int4	getNumUnnecessaryPcode (void) const
	Return the number of unnecessary extensions and truncations.

int4	getNumReadNoWrite (void) const
	Return the number of temporaries read but not written.

int4	getNumWriteNoRead (void) const
	Return the number of temporaries written but not read.

int4	getNumLargeTemporaries (void) const
	Return the number of too large temporaries.

Private Member Functions
OperandSymbol *	getOperandSymbol (int4 slot, OpTpl op, Constructor ct)
	Get the OperandSymbol associated with an input/output Varnode of the given p-code operator. More...

void	printOpName (ostream &s, OpTpl *op)
	Print the name of a p-code operator (for warning and error messages) More...

void	printOpError (OpTpl op, Constructor ct, int4 err1, int4 err2, const string &message)
	Print an error message describing a size restriction violation. More...

int4	recoverSize (const ConstTpl &sizeconst, Constructor *ct)
	Recover a specific value for the size associated with a Varnode template. More...

bool	checkOpMisuse (OpTpl op, Constructor ct)
	Check for misuse of the given operator and print a warning. More...

bool	sizeRestriction (OpTpl op, Constructor ct)
	Make sure the given operator meets size restrictions. More...

bool	checkConstructorSection (Constructor ct, ConstructTpl cttpl)
	Check all p-code operators within a given Constructor section for misuse and size consistency. More...

bool	hasLargeTemporary (OpTpl *op)
	Check the given p-code operator for too large temporary registers. More...

bool	isTemporaryAndTooBig (VarnodeTpl *vn)
	Check if the given Varnode is a too large temporary register. More...

bool	checkVarnodeTruncation (Constructor ct, int4 slot, OpTpl op, VarnodeTpl *vn, bool isbigendian)
	Resolve the offset of the given truncated Varnode. More...

bool	checkSectionTruncations (Constructor ct, ConstructTpl cttpl, bool isbigendian)
	Check and adjust truncated Varnodes in the given Constructor p-code section. More...

bool	checkSubtable (SubtableSymbol *sym)
	Check all Constructors within the given subtable for operator misuse and size consistency. More...

void	dealWithUnnecessaryExt (OpTpl op, Constructor ct)
	Convert an unnecessary CPUI_INT_ZEXT and CPUI_INT_SEXT into a COPY. More...

void	dealWithUnnecessaryTrunc (OpTpl op, Constructor ct)
	Convert an unnecessary CPUI_SUBPIECE into a COPY. More...

void	setPostOrder (SubtableSymbol *root)
	Establish ordering on subtables so that more dependent tables come first. More...

bool	readWriteInterference (const VarnodeTpl vn, const OpTpl op, bool checkread) const
	Check if a p-code operator reads from or writes to a given Varnode. More...

void	optimizeGather1 (Constructor *ct, map< uintb, OptimizeRecord > &recs, int4 secnum) const
	Gather statistics about read and writes to temporary Varnodes within a given p-code section. More...

void	optimizeGather2 (Constructor *ct, map< uintb, OptimizeRecord > &recs, int4 secnum) const
	Mark Varnodes in the export of the given p-code section as read and written. More...

const OptimizeRecord *	findValidRule (Constructor *ct, const map< uintb, OptimizeRecord > &recs) const
	Search for an OptimizeRecord indicating a temporary Varnode that can be optimized away. More...

void	applyOptimization (Constructor *ct, const OptimizeRecord &rec)
	Remove an extraneous COPY going through a temporary Varnode. More...

void	checkUnusedTemps (Constructor *ct, const map< uintb, OptimizeRecord > &recs)
	Issue error/warning messages for unused temporary Varnodes. More...

void	checkLargeTemporaries (Constructor ct, ConstructTpl ctpl)
	In the given Constructor p-code section, check for temporary Varnodes that are too large. More...

void	optimize (Constructor *ct)
	Do p-code optimization on each section of the given Constructor. More...

Static Private Member Functions
static void	examineVn (map< uintb, OptimizeRecord > &recs, const VarnodeTpl *vn, uint4 i, int4 inslot, int4 secnum)
	Accumulate read/write info if the given Varnode is temporary. More...

static bool	possibleIntersection (const VarnodeTpl vn1, const VarnodeTpl vn2)
	Test whether two given Varnodes intersect. More...

Private Attributes
SleighCompile *	compiler
	Parsed form of the SLEIGH file being examined.

int4	unnecessarypcode
	Count of unnecessary extension/truncation operations.

int4	readnowrite
	Count of temporary registers that are read but not written.

int4	writenoread
	Count of temporary registers that are written but not read.

int4	largetemp
	Count of temporary registers that are too large.

bool	printextwarning
	Set to true if warning emitted for each unnecessary truncation/extension.

bool	printdeadwarning
	Set to true if warning emitted for each written but not read temporary.

bool	printlargetempwarning
	Set to true if warning emitted for each too large temporary.

SubtableSymbol *	root_symbol
	The root symbol table for the parsed SLEIGH file.

vector< SubtableSymbol * >	postorder
	Subtables sorted into post order (dependent tables listed earlier)

map< SubtableSymbol *, int4 >	sizemap
	Sizes associated with table exports.

Detailed Description

Derive Varnode sizes and optimize p-code in SLEIGH Constructors.

This class examines p-code parsed from a SLEIGH file and performs three main tasks:

Enforcing size rules in Constructor p-code,
Optimizing p-code within a Constructor, and
Searching for other p-code validity violations

Many p-code operators require that their input and/or output operands are all the same size or have other specific size restrictions on their operands. This class enforces those requirements.

This class performs limited optimization of p-code within a Constructor by performing COPY propagation through temporary registers.

This class searches for unnecessary truncations and extensions, temporary varnodes that are either dead, read before written, or that exceed the standard allocation size.

Constructor & Destructor Documentation

◆ ConsistencyChecker()

ghidra::ConsistencyChecker::ConsistencyChecker	(	SleighCompile *	sleigh,
		SubtableSymbol *	rt,
		bool	un,
		bool	warndead,
		bool	warnlargetemp
	)

Construct the consistency checker and optimizer.

Parameters

sleigh	is the parsed SLEIGH spec
rt	is the root subtable of the SLEIGH spec
un	is true to request "Unnecessary extension" warnings
warndead	is true to request warnings for written but not read temporaries
warnlargetemp	is true to request warnings for temporaries that are too large

<Number of constructors using at least one temporary varnode larger than SleighBase::MAX_UNIQUE_SIZE

< If true, prints a warning about each constructor using a temporary varnode larger than SleighBase::MAX_UNIQUE_SIZE

Member Function Documentation

◆ applyOptimization()

void ghidra::ConsistencyChecker::applyOptimization	(	Constructor *	ct,
		const OptimizeRecord &	rec
	)

private

Remove an extraneous COPY going through a temporary Varnode.

If an OptimizeRecord has determined that a temporary Varnode is read once, written once, and goes through a COPY operator, remove the COPY operator. If the Varnode is an input to the COPY, the operator writing the Varnode is changed to write to the output of the COPY instead. If the Varnode is an output of the COPY, the operator reading the Varnode is changed to read the input of the COPY instead. In either case, the COPY operator is removed.

Parameters

ct	is the Constructor
rec	is record describing the temporary and its read/write operators

References ghidra::ConsistencyChecker::OptimizeRecord::inslot, ghidra::ConsistencyChecker::OptimizeRecord::opttype, ghidra::ConsistencyChecker::OptimizeRecord::readop, ghidra::ConsistencyChecker::OptimizeRecord::readsection, and ghidra::ConsistencyChecker::OptimizeRecord::writeop.

◆ checkConstructorSection()

bool ghidra::ConsistencyChecker::checkConstructorSection	(	Constructor *	ct,
		ConstructTpl *	cttpl
	)

private

Check all p-code operators within a given Constructor section for misuse and size consistency.

Each operator within the section is checked in turn, and warning and error messages are emitted if necessary. The method returns false if there is a fatal error associated with any operator.

Parameters

ct	is the Constructor to check
cttpl	is the specific p-code section to check

Returns: true if there are no fatal errors in the section

◆ checkLargeTemporaries()

void ghidra::ConsistencyChecker::checkLargeTemporaries	(	Constructor *	ct,
		ConstructTpl *	ctpl
	)

private

In the given Constructor p-code section, check for temporary Varnodes that are too large.

Run through all Varnodes in the constructor, if a Varnode is in the unique space and its size exceeds the threshold SleighBase::MAX_UNIQUE_SIZE, issue a warning. Note that this method returns after the first large Varnode is found.

Parameters

ct	is the given Constructor
ctpl	is the specific p-code section

References ghidra::SleighBase::MAX_UNIQUE_SIZE.

◆ checkOpMisuse()

bool ghidra::ConsistencyChecker::checkOpMisuse	(	OpTpl *	op,
		Constructor *	ct
	)

private

Check for misuse of the given operator and print a warning.

This method currently checks for:

Unsigned less-than comparison with zero

Parameters

op	is the given operator
ct	is the Constructor owning the operator

Returns: false if the operator is fatally misused

References ghidra::CPUI_INT_LESS.

◆ checkSectionTruncations()

bool ghidra::ConsistencyChecker::checkSectionTruncations	(	Constructor *	ct,
		ConstructTpl *	cttpl,
		bool	isbigendian
	)

private

Check and adjust truncated Varnodes in the given Constructor p-code section.

Run through all Varnodes looking for offset templates marked as ConstTpl::v_offset_plus, which indicates they were constructed using truncation notation. These truncation expressions are checked for validity and adjusted depending on the endianess of the address space.

Parameters

ct	is the Constructor
cttpl	is the given p-code section
isbigendian	is set to true if the SLEIGH specification is big endian

Returns: true if all truncation expressions were valid

◆ checkSubtable()

bool ghidra::ConsistencyChecker::checkSubtable ( SubtableSymbol * sym )

private

Check all Constructors within the given subtable for operator misuse and size consistency.

Each Constructor and section is checked in turn. Additionally, the size of Constructor exports is checked for consistency across the subtable. Constructors within one subtable must all export the same size Varnode if the export at all.

Parameters

sym	is the given subtable to check

Returns: true if there are no fatal misuse or consistency violations

◆ checkUnusedTemps()

void ghidra::ConsistencyChecker::checkUnusedTemps	(	Constructor *	ct,
		const map< uintb, OptimizeRecord > &	recs
	)

private

Issue error/warning messages for unused temporary Varnodes.

An error message is issued if a temporary is read but not written. A warning may be issued if a temporary is written but not read.

Parameters

ct	is the Constructor
recs	is the collection of records associated with each temporary Varnode

References ghidra::ConsistencyChecker::OptimizeRecord::readcount, and ghidra::ConsistencyChecker::OptimizeRecord::writecount.

◆ checkVarnodeTruncation()

bool ghidra::ConsistencyChecker::checkVarnodeTruncation	(	Constructor *	ct,
		int4	slot,
		OpTpl *	op,
		VarnodeTpl *	vn,
		bool	isbigendian
	)

private

Resolve the offset of the given truncated Varnode.

SLEIGH allows a Varnode to be derived from another larger Varnode using truncation or bit range notation. The final offset of the truncated Varnode may not be calculable immediately during parsing, especially if the address space is big endian and the size of the containing Varnode is not immediately known. This method recovers the final offset of the truncated Varnode now that all sizes are known and otherwise checks that the truncation expression is valid.

Parameters

ct	is the Constructor containing the Varnode
slot	is the slot index of the truncated Varnode (for error messages)
op	is the operator using the truncated Varnode (for error messages)
vn	is the given truncated Varnode
isbigendian	is true if the Varnode is in a big endian address space

Returns: true if the truncation expression was valid

◆ dealWithUnnecessaryExt()

void ghidra::ConsistencyChecker::dealWithUnnecessaryExt	(	OpTpl *	op,
		Constructor *	ct
	)

private

Convert an unnecessary CPUI_INT_ZEXT and CPUI_INT_SEXT into a COPY.

SLEIGH allows zext and sext notation even if the input and output Varnodes are ultimately the same size. In this case, a warning may be issued and the operator is converted to a CPUI_COPY.

Parameters

op	is the given CPUI_INT_ZEXT or CPUI_INT_SEXT operator to check
ct	is the Constructor containing the operator

References ghidra::CPUI_COPY.

◆ dealWithUnnecessaryTrunc()

void ghidra::ConsistencyChecker::dealWithUnnecessaryTrunc	(	OpTpl *	op,
		Constructor *	ct
	)

private

Convert an unnecessary CPUI_SUBPIECE into a COPY.

SLEIGH allows truncation notation even if the input and output Varnodes are ultimately the same size. In this case, a warning may be issued and the operator is converted to a CPUI_COPY.

Parameters

op	is the given CPUI_SUBPIECE operator
ct	is the containing Constructor

References ghidra::CPUI_COPY.

◆ examineVn()

void ghidra::ConsistencyChecker::examineVn	(	map< uintb, OptimizeRecord > &	recs,
		const VarnodeTpl *	vn,
		uint4	i,
		int4	inslot,
		int4	secnum
	)

staticprivate

Accumulate read/write info if the given Varnode is temporary.

If the Varnode is in the unique space, an OptimizationRecord for it is looked up based on its offset. Information about how a p-code operator uses the Varnode is accumulated in the record.

Parameters

recs	is collection of OptimizationRecords associated with temporary Varnodes
vn	is the given Varnode to check (which may or may not be temporary)
i	is the index of the operator using the Varnode (within its p-code section)
inslot	is the slot index of the Varnode within its operator
secnum	is the section number containing the operator

◆ findValidRule()

const ConsistencyChecker::OptimizeRecord * ghidra::ConsistencyChecker::findValidRule	(	Constructor *	ct,
		const map< uintb, OptimizeRecord > &	recs
	)		const

private

Search for an OptimizeRecord indicating a temporary Varnode that can be optimized away.

OptimizeRecords for all temporary Varnodes must already be calculated. Find a record indicating a temporary Varnode that is written once and read once through a COPY. Test propagation of the other Varnode associated with the COPY, making sure: if propagation is backward, the Varnode must not cross another read or write, and if propagation is forward, the Varnode must not cross another write. If all the requirements pass, return the record indicating that the COPY can be removed.

Parameters

ct	is the Constructor owning the p-code
recs	is the collection of OptimizeRecords to search

Returns: a passing OptimizeRecord or null

References ghidra::CPUI_COPY, ghidra::ConsistencyChecker::OptimizeRecord::opttype, ghidra::ConsistencyChecker::OptimizeRecord::readcount, ghidra::ConsistencyChecker::OptimizeRecord::readop, ghidra::ConsistencyChecker::OptimizeRecord::readsection, ghidra::ConsistencyChecker::OptimizeRecord::writecount, ghidra::ConsistencyChecker::OptimizeRecord::writeop, and ghidra::ConsistencyChecker::OptimizeRecord::writesection.

◆ getOperandSymbol()

OperandSymbol * ghidra::ConsistencyChecker::getOperandSymbol	(	int4	slot,
		OpTpl *	op,
		Constructor *	ct
	)

private

Get the OperandSymbol associated with an input/output Varnode of the given p-code operator.

Find the Constructor operand associated with a specified Varnode, if it exists. The Varnode is specified by the p-code operator using it and the input slot index, with -1 indicating the operator's output Varnode. Not all Varnode's are associated with a Constructor operand, in which case null is returned.

Parameters

slot	is the input slot index, or -1 for an output Varnode
op	is the p-code operator using the Varnode
ct	is the Constructor containing the p-code and operands

Returns: the associated operand or null

◆ hasLargeTemporary()

bool ghidra::ConsistencyChecker::hasLargeTemporary ( OpTpl * op )

private

Check the given p-code operator for too large temporary registers.

Return true if the output or one of the inputs to the operator is in the unique space and larger than SleighBase::MAX_UNIQUE_SIZE

Parameters

op	is the given operator

Returns: true if the operator has a too large temporary parameter

◆ isTemporaryAndTooBig()

bool ghidra::ConsistencyChecker::isTemporaryAndTooBig ( VarnodeTpl * vn )

private

Check if the given Varnode is a too large temporary register.

Return true precisely when the Varnode is in the unique space and has size larger than SleighBase::MAX_UNIQUE_SIZE

Parameters

vn	is the given Varnode

Returns: true if the Varnode is a too large temporary register

References ghidra::SleighBase::MAX_UNIQUE_SIZE.

◆ optimize()

void ghidra::ConsistencyChecker::optimize ( Constructor * ct )

private

Do p-code optimization on each section of the given Constructor.

For p-code section, statistics on temporary Varnode usage is collected, and unnecessary COPY operators are removed.

Parameters

ct	is the given Constructor

◆ optimizeGather1()

void ghidra::ConsistencyChecker::optimizeGather1	(	Constructor *	ct,
		map< uintb, OptimizeRecord > &	recs,
		int4	secnum
	)		const

private

Gather statistics about read and writes to temporary Varnodes within a given p-code section.

For each temporary Varnode, count how many times it is read from or written to in the given section of p-code operators.

Parameters

ct	is the given Constructor
recs	is the (initially empty) collection of count records
secnum	is the given p-code section number

◆ optimizeGather2()

void ghidra::ConsistencyChecker::optimizeGather2	(	Constructor *	ct,
		map< uintb, OptimizeRecord > &	recs,
		int4	secnum
	)		const

private

Mark Varnodes in the export of the given p-code section as read and written.

As part of accumulating read/write info for temporary Varnodes, examine the export Varnode for the section, and if it involves a temporary, mark it as both read and written, guaranteeing that the Varnode is not optimized away.

Parameters

ct	is the given Constructor
recs	is the collection of count records
secnum	is the given p-code section number

◆ possibleIntersection()

bool ghidra::ConsistencyChecker::possibleIntersection	(	const VarnodeTpl *	vn1,
		const VarnodeTpl *	vn2
	)

staticprivate

Test whether two given Varnodes intersect.

This test must be conservative. If it can't explicitly prove that the Varnodes don't intersect, it returns true (a possible intersection).

Parameters

vn1	is the first Varnode to check
vn2	is the second Varnode to check

Returns: true if there is a possible intersection of the Varnodes' storage

◆ printOpError()

void ghidra::ConsistencyChecker::printOpError	(	OpTpl *	op,
		Constructor *	ct,
		int4	err1,
		int4	err2,
		const string &	msg
	)

private

Print an error message describing a size restriction violation.

The given p-code operator is assumed to violate the Varnode size rules for its opcode. If the violation is for two Varnodes that should be the same size, each Varnode is indicated as an input slot index, where -1 indicates the operator's output Varnode. If the violation is for a single Varnode, its slot index is passed in twice.

Parameters

op	is the given p-code operator
ct	is the containing Constructor
err1	is the slot of the first violating Varnode
err2	is the slot of the second violating Varnode (or equal to err1)
msg	is additional description that is appended to the error message

◆ printOpName()

void ghidra::ConsistencyChecker::printOpName	(	ostream &	s,
		OpTpl *	op
	)

private

Print the name of a p-code operator (for warning and error messages)

Print the full name of the operator with its syntax token in parentheses.

Parameters

s	is the output stream to write to
op	is the operator to print

◆ readWriteInterference()

bool ghidra::ConsistencyChecker::readWriteInterference	(	const VarnodeTpl *	vn,
		const OpTpl *	op,
		bool	checkread
	)		const

private

Check if a p-code operator reads from or writes to a given Varnode.

A write check is always performed. A read check is performed only if requested. Return true if there is a possible write (or read) of the Varnode. The checks need to be extremely conservative. If it can't be determined what exactly is being read or written, true (possible interference) is returned.

Parameters

vn	is the given Varnode
op	is p-code operator to test for interference
checkread	is true if read interference should be checked

Returns: true if there is write (or read) interference

References ghidra::CPUI_BRANCH, ghidra::CPUI_BRANCHIND, ghidra::CPUI_CALL, ghidra::CPUI_CALLIND, ghidra::CPUI_CALLOTHER, ghidra::CPUI_CBRANCH, ghidra::CPUI_LOAD, ghidra::CPUI_RETURN, and ghidra::CPUI_STORE.

◆ recoverSize()

int4 ghidra::ConsistencyChecker::recoverSize	(	const ConstTpl &	sizeconst,
		Constructor *	ct
	)

private

Recover a specific value for the size associated with a Varnode template.

This method is passed a ConstTpl that is assumed to be the size attribute of a VarnodeTpl (as returned by getSize()). This method recovers the specific integer value for this constant template or throws an exception. The integer value can either be immediately available from parsing, derived from a Constructor operand symbol whose size is known, or taken from the calculated export size of a subtable symbol.

Parameters

sizeconst	is the Varnode size template
ct	is the Constructor containing the Varnode

Returns: the integer value

◆ setPostOrder()

void ghidra::ConsistencyChecker::setPostOrder ( SubtableSymbol * root )

private

Establish ordering on subtables so that more dependent tables come first.

Do a depth first traversal of SubtableSymbols starting at the root table going through Constructors and then through their operands, establishing a post-order on the subtables. This allows the size restriction checks to recursively calculate sizes of dependent subtables first and propagate their values into more global Varnodes (as Constructor operands)

Parameters

root	is the root subtable

◆ sizeRestriction()

bool ghidra::ConsistencyChecker::sizeRestriction	(	OpTpl *	op,
		Constructor *	ct
	)

private

Make sure the given operator meets size restrictions.

Many SLEIGH operators require that inputs and/or outputs are the same size, or they have other specific size requirement. Print an error and return false for any violations.

Parameters

op	is the given p-code operator
ct	is the Constructor owning the operator

Returns: true if there are no size restriction violations

◆ testLargeTemporary()

void ghidra::ConsistencyChecker::testLargeTemporary ( void )

Test for temporary Varnodes that are too large.

This counts Constructors that contain temporary Varnodes that are too large. If requested, an individual warning is printed for each Constructor.

Referenced by ghidra::SleighCompile::checkConsistency().

◆ testSizeRestrictions()

bool ghidra::ConsistencyChecker::testSizeRestrictions ( void )

Test size consistency of all p-code.

Warnings or errors for individual violations may be printed, depending on settings.

Returns: true if all size consistency checks pass

Referenced by ghidra::SleighCompile::checkConsistency().

◆ testTruncations()

bool ghidra::ConsistencyChecker::testTruncations ( void )

Test truncation validity of all p-code.

Update truncated Varnodes given complete size information. Print errors for any invalid truncation constructions.

Returns: true if there are no invalid truncations

Referenced by ghidra::SleighCompile::checkConsistency().

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

slgh_compile.hh
slgh_compile.cc

Classes

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ ConsistencyChecker()

Member Function Documentation

◆ applyOptimization()

◆ checkConstructorSection()

◆ checkLargeTemporaries()

◆ checkOpMisuse()

◆ checkSectionTruncations()

◆ checkSubtable()

◆ checkUnusedTemps()

◆ checkVarnodeTruncation()

◆ dealWithUnnecessaryExt()

◆ dealWithUnnecessaryTrunc()

◆ examineVn()

◆ findValidRule()

◆ getOperandSymbol()

◆ hasLargeTemporary()

◆ isTemporaryAndTooBig()

◆ optimize()

◆ optimizeGather1()

◆ optimizeGather2()

◆ possibleIntersection()

◆ printOpError()

◆ printOpName()

◆ readWriteInterference()

◆ recoverSize()

◆ setPostOrder()

◆ sizeRestriction()

◆ testLargeTemporary()

◆ testSizeRestrictions()

◆ testTruncations()