Description

Leaf node of an expression tree for instruction semantics.

A leaf node is either a known bit vector value, a free bit vector variable, or a memory state.

Definition at line 1240 of file SymbolicExpression.h.

#include <Rose/BinaryAnalysis/SymbolicExpression.h>

Inheritance diagram for Rose::BinaryAnalysis::SymbolicExpression::Leaf:

[legend]

Collaboration diagram for Rose::BinaryAnalysis::SymbolicExpression::Leaf:

[legend]

Public Member Functions
virtual size_t	nChildren () const override
	Number of arguments.

virtual const Ptr &	child (size_t idx) const override
	Argument.

virtual const Node *	childRaw (size_t) const override
	Argument.

virtual const Nodes &	children () const override
	Arguments.

virtual Operator	getOperator () const override
	Operator for interior nodes.

virtual bool	mustEqual (const Ptr &other, const SmtSolverPtr &solver=SmtSolverPtr()) override
	Returns true if two expressions must be equal (cannot be unequal).

virtual bool	mayEqual (const Ptr &other, const SmtSolverPtr &solver=SmtSolverPtr()) override
	Returns true if two expressions might be equal, but not necessarily be equal.

virtual bool	isEquivalentTo (const Ptr &other) override
	Tests two expressions for structural equivalence.

virtual bool	isEquivalentHelper (Node *, EquivPairs &) override

virtual int	compareStructure (const Ptr &other) override
	Compare two expressions structurally for sorting.

virtual Ptr	substitute (const Ptr &from, const Ptr &to, const SmtSolverPtr &solver=SmtSolverPtr()) override
	Substitute one value for another.

virtual VisitAction	depthFirstTraversal (Visitor &) const override
	Traverse the expression.

virtual uint64_t	nNodes () const override
	Computes the size of an expression by counting the number of nodes.

virtual Sawyer::Optional< uint64_t >	toUnsigned () const override
	The unsigned integer value of the expression.

virtual Sawyer::Optional< int64_t >	toSigned () const override
	The signed integer value of the expression.

virtual bool	isConstant () const override
	True if this expression is a constant.

virtual bool	isVariable2 () const override
	True if this expression is a variable.

virtual void	print (std::ostream &, Formatter &) const override
	Print the expression to a stream.

const Sawyer::Container::BitVector &	bits () const
	Property: Bits stored for numeric constants.

bool	isIntegerVariable () const
	Is this node an integer variable?

bool	isFloatingPointVariable () const
	Is this node a floating-point variable?

bool	isFloatingPointNan () const
	Is this node a floating-point NaN constant?

bool	isMemoryVariable () const
	Is this node a memory variable?

uint64_t	nameId () const
	Returns the name ID of a free variable.

std::string	toString () const
	Returns a string for the leaf.

void	printAsSigned (std::ostream &, Formatter &, bool asSigned=true) const
	Prints an integer constant interpreted as a signed value.

void	printAsUnsigned (std::ostream &o, Formatter &f) const
	Prints an integer constant interpreted as an unsigned value.

Public Member Functions inherited from Rose::BinaryAnalysis::SymbolicExpression::Node
Type	type () const
	Type of value.

Ptr	substituteMultiple (const ExprExprHashMap &substitutions, const SmtSolverPtr &solver=SmtSolverPtr())
	Rewrite expression by substituting subexpressions.

Ptr	renameVariables (ExprExprHashMap &index, size_t &nextVariableId, const SmtSolverPtr &solver=SmtSolverPtr())
	Rewrite using lowest numbered variable names.

bool	isIntegerExpr () const
	True if this expression is of an integer type.

bool	isFloatingPointExpr () const
	True if this expression is of a floating-point type.

bool	isMemoryExpr () const
	True if this expression is of a memory type.

bool	isScalarExpr () const
	True if the expression is a scalar type.

bool	isIntegerConstant () const
	True if this expression is an integer constant.

bool	isFloatingPointConstant () const
	True if this epxression is a floating-point constant.

bool	isScalarConstant () const
	True if this expression is a scalar constant.

bool	isFloatingPointNan () const
	True if this expression is a floating-point NaN constant.

Sawyer::Optional< uint64_t >	variableId () const
	Variable ID number.

bool	isIntegerVariable () const
	True if this expression is an integer variable.

bool	isFloatingPointVariable () const
	True if this expression is a floating-point variable.

bool	isMemoryVariable () const
	True if this expression is a memory state variable.

bool	isScalarVariable () const
	True if this expression is a scalar variable.

size_t	nBits () const
	Property: Number of significant bits.

unsigned	flags () const
	Property: User-defined bit flags.

Ptr	newFlags (unsigned flags) const
	Sets flags.

size_t	domainWidth () const
	Property: Width for memory expressions.

bool	isScalar () const
	Check whether expression is scalar.

uint64_t	nNodesUnique () const
	Number of unique nodes in expression.

std::set< LeafPtr >	getVariables () const
	Returns the variables appearing in the expression.

bool	isHashed () const
	Returns true if this node has a hash value computed and cached.

Hash	hash () const
	Returns (and caches) the hash value for this node.

void	hash (Hash) const

std::string	toString () const
	Convert expression to string.

void	assertAcyclic () const
	Asserts that expressions are acyclic.

std::vector< Ptr >	findCommonSubexpressions () const
	Find common subexpressions.

bool	matchAddVariableConstant (LeafPtr &variable, LeafPtr &constant) const
	Determine whether an expression is a variable plus a constant.

InteriorPtr	isOperator (Operator) const
	True (non-null) if this node is the specified operator.

const std::string &	comment () const
	Property: Comment.

void	comment (const std::string &s)
	Property: Comment.

void	userData (boost::any &data)
	Property: User-defined data.

const boost::any &	userData () const
	Property: User-defined data.

InteriorPtr	isInteriorNode () const
	Dynamic cast of this object to an interior node.

Interior *	isInteriorNodeRaw () const
	Dynamic cast of this object to an interior node.

LeafPtr	isLeafNode () const
	Dynamic cast of this object to a leaf node.

Leaf *	isLeafNodeRaw () const
	Dynamic cast of this object to a leaf node.

WithFormatter	withFormat (Formatter &fmt)
	Combines a node with a formatter for printing.

WithFormatter	operator+ (Formatter &fmt)
	Combines a node with a formatter for printing.

void	print (std::ostream &o) const
	Print the expression to a stream.

Public Member Functions inherited from Sawyer::SharedObject
	SharedObject ()
	Default constructor.

	SharedObject (const SharedObject &)
	Copy constructor.

virtual	~SharedObject ()
	Virtual destructor.

SharedObject &	operator= (const SharedObject &)
	Assignment.

Public Member Functions inherited from Sawyer::SharedFromThis< Node >
SharedPointer< Node >	sharedFromThis ()
	Create a shared pointer from `this`.

SharedPointer< const Node >	sharedFromThis () const
	Create a shared pointer from `this`.

Public Member Functions inherited from Sawyer::Attribute::Storage< SyncTag >
	Storage ()
	Default constructor.

	Storage (const Storage &other)
	Copy constructor.

Storage &	operator= (const Storage &other)
	Assignment operator.

bool	attributeExists (Id id) const
	Check attribute existence.

void	eraseAttribute (Id id)
	Erase an attribute.

void	clearAttributes ()
	Erase all attributes.

template<typename T >
void	setAttribute (Id id, const T &value)
	Store an attribute.

template<typename T >
bool	setAttributeMaybe (Id id, const T &value)
	Store an attribute if not already present.

template<typename T >
T	getAttribute (Id id) const
	Get an attribute that is known to exist.

template<typename T >
Sawyer::Optional< T >	getAttributeMaybe (const Id id) const
	Return an attribute if it exists, or else nothing.

template<typename T >
T	attributeOrElse (Id id, const T &dflt) const
	Return an attribute or a specified value.

template<typename T >
T	attributeOrDefault (Id id) const
	Return an attribute or a default-constructed value.

template<typename T >
Sawyer::Optional< T >	optionalAttribute (Id id) const
	Return the attribute as an optional value.

size_t	nAttributes () const
	Number of attributes stored.

std::vector< Id >	attributeIds () const
	Returns ID numbers for all IDs stored in this container.

Static Public Member Functions
static LeafPtr	createVariable (const Type &, const std::string &comment="", unsigned flags=0)
	Create a new variable.

static LeafPtr	createVariable (const Type &, const uint64_t id, const std::string &comment="", unsigned flags=0)
	Create an existing variable.

static LeafPtr	createConstant (const Type &, const Sawyer::Container::BitVector &, const std::string &comment="", unsigned flags=0)
	Create a constant.

Static Public Member Functions inherited from Sawyer::SmallObject
static SynchronizedPoolAllocator &	poolAllocator ()
	Return the pool allocator for this class.

static void *	operator new (size_t size)

static void	operator delete (void *ptr, size_t size)

Additional Inherited Members
Public Types inherited from Rose::BinaryAnalysis::SymbolicExpression::Node
using	EquivPairs = std::map< Node , std::vector< std::pair< Node , bool > > >

Public Types inherited from Sawyer::Attribute::Storage< SyncTag >
typedef SynchronizationTraits< SyncTag >	Sync

Static Public Attributes inherited from Rose::BinaryAnalysis::SymbolicExpression::Node
static const unsigned	RESERVED_FLAGS = 0x0000ffff
	These flags are reserved for use within ROSE.

static const unsigned	INDETERMINATE = 0x00000001
	Value is somehow indeterminate.

static const unsigned	UNSPECIFIED = 0x00000002
	Value is somehow unspecified.

static const unsigned	BOTTOM = 0x00000004
	Value represents bottom in dataflow analysis.

static boost::logic::tribool(*	mayEqualCallback )(const Ptr &a, const Ptr &b, const SmtSolverPtr &)
	User-supplied predicate to augment alias checking.

Protected Member Functions inherited from Rose::BinaryAnalysis::SymbolicExpression::Node
	Node (const std::string &comment, unsigned flags=0)

void	printFlags (std::ostream &o, unsigned flags, char &bracket) const

Protected Attributes inherited from Rose::BinaryAnalysis::SymbolicExpression::Node
Type	type_

unsigned	flags_
	Bit flags.

std::string	comment_
	Optional comment.

Hash	hashval_
	Optional hash used as a quick way to indicate that two expressions are different.

boost::any	userData_
	Additional user-specified data.

Member Function Documentation

◆ nChildren()

virtual size_t Rose::BinaryAnalysis::SymbolicExpression::Leaf::nChildren ( ) const

inlineoverridevirtual

Number of arguments.

Returns the number of children for an interior node, zero for leaf nodes.

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

Definition at line 1297 of file SymbolicExpression.h.

◆ child()

virtual const Ptr & Rose::BinaryAnalysis::SymbolicExpression::Leaf::child ( size_t idx ) const

overridevirtual

Argument.

Returns the specified argument by index. If the index is out of range, then returns null. A leaf node always returns null since it never has children.

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

◆ childRaw()

virtual const Node * Rose::BinaryAnalysis::SymbolicExpression::Leaf::childRaw ( size_t idx ) const

inlineoverridevirtual

Argument.

Returns the specified argument by index. If the index is out of range, then returns null. A leaf node always returns null since it never has children.

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

Definition at line 1299 of file SymbolicExpression.h.

◆ children()

virtual const Nodes & Rose::BinaryAnalysis::SymbolicExpression::Leaf::children ( ) const

overridevirtual

Arguments.

Returns the arguments of an operation for an interior node, or an empty list for a leaf node.

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

◆ getOperator()

virtual Operator Rose::BinaryAnalysis::SymbolicExpression::Leaf::getOperator ( ) const

inlineoverridevirtual

Operator for interior nodes.

Return the operator for interior nodes, or OP_NONE for leaf nodes that have no operator.

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

Definition at line 1301 of file SymbolicExpression.h.

References Rose::BinaryAnalysis::SymbolicExpression::OP_NONE.

◆ mustEqual()

virtual bool Rose::BinaryAnalysis::SymbolicExpression::Leaf::mustEqual	(	const Ptr &	other,
		const SmtSolverPtr &	solver = `SmtSolverPtr()`
	)

overridevirtual

Returns true if two expressions must be equal (cannot be unequal).

If an SMT solver is specified then that solver is used to answer this question, otherwise equality is established by looking only at the structure of the two expressions. Two expressions can be equal without being the same width (e.g., a 32-bit constant zero is equal to a 16-bit constant zero).

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

◆ mayEqual()

virtual bool Rose::BinaryAnalysis::SymbolicExpression::Leaf::mayEqual	(	const Ptr &	other,
		const SmtSolverPtr &	solver = `SmtSolverPtr()`
	)

overridevirtual

Returns true if two expressions might be equal, but not necessarily be equal.

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

◆ isEquivalentTo()

virtual bool Rose::BinaryAnalysis::SymbolicExpression::Leaf::isEquivalentTo ( const Ptr & other )

overridevirtual

Tests two expressions for structural equivalence.

Two leaf nodes are equivalent if they are the same width and have equal values or are the same variable. Two interior nodes are equivalent if they are the same width, the same operation, have the same number of children, and those children are all pairwise equivalent.

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

◆ isEquivalentHelper()

virtual bool Rose::BinaryAnalysis::SymbolicExpression::Leaf::isEquivalentHelper	(	Node *	,
		EquivPairs &
	)

overridevirtual

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

◆ compareStructure()

virtual int Rose::BinaryAnalysis::SymbolicExpression::Leaf::compareStructure ( const Ptr & other )

overridevirtual

Compare two expressions structurally for sorting.

Returns -1 if this is less than other, 0 if they are structurally equal, and 1 if this is greater than other. This function returns zero when an only when isEquivalentTo returns zero, but isEquivalentTo can be much faster since it uses hashing.

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

◆ substitute()

virtual Ptr Rose::BinaryAnalysis::SymbolicExpression::Leaf::substitute	(	const Ptr &	from,
		const Ptr &	to,
		const SmtSolverPtr &	solver = `SmtSolverPtr()`
	)

overridevirtual

Substitute one value for another.

Finds all occurrances of from in this expression and replace them with to. If a substitution occurs, then a new expression is returned. The matching of from to sub-parts of this expression uses structural equivalence, the isEquivalentTo predicate. The from and to expressions must have the same width.

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

◆ depthFirstTraversal()

virtual VisitAction Rose::BinaryAnalysis::SymbolicExpression::Leaf::depthFirstTraversal ( Visitor & ) const

overridevirtual

Traverse the expression.

The expression is traversed in a depth-first visit. The final return value is the final return value of the last call to the visitor.

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

◆ nNodes()

virtual uint64_t Rose::BinaryAnalysis::SymbolicExpression::Leaf::nNodes ( ) const

inlineoverridevirtual

Computes the size of an expression by counting the number of nodes.

Operates in constant time. Note that it is possible (even likely) for the 64-bit return value to overflow in expressions when many nodes are shared. For instance, the following loop will create an expression that contains more than 2^64 nodes:

SymbolicExpression expr = Leaf::createVariable(32);
for(size_t i=0; i<64; ++i)
    expr = makeAdd(expr, expr)

When an overflow occurs the result is meaningless.

See also: nNodesUnique

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

Definition at line 1309 of file SymbolicExpression.h.

◆ toUnsigned()

virtual Sawyer::Optional< uint64_t > Rose::BinaryAnalysis::SymbolicExpression::Leaf::toUnsigned ( ) const

overridevirtual

The unsigned integer value of the expression.

Returns nothing if the expression is not a concrete integer value or the value is too wide to be represented by the return type.

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

◆ toSigned()

virtual Sawyer::Optional< int64_t > Rose::BinaryAnalysis::SymbolicExpression::Leaf::toSigned ( ) const

overridevirtual

The signed integer value of the expression.

Returns nothing if the expression is not a concrete integer value or the value doesn't fit in the return type.

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

◆ isConstant()

virtual bool Rose::BinaryAnalysis::SymbolicExpression::Leaf::isConstant ( ) const

inlineoverridevirtual

True if this expression is a constant.

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

Definition at line 1312 of file SymbolicExpression.h.

References Sawyer::Container::BitVector::isEmpty().

Referenced by isFloatingPointVariable(), isIntegerVariable(), isMemoryVariable(), and isVariable2().

◆ isVariable2()

virtual bool Rose::BinaryAnalysis::SymbolicExpression::Leaf::isVariable2 ( ) const

inlineoverridevirtual

True if this expression is a variable.

Warning: Leaf nodes have a deprecated isVariable method that returns false for memory state variables, thus this method has a "2" appended to its name. After a suitable period of deprecation for Leaf::isVariable, a new isVariable will be added to this class hiearchy and will have the same semantics as isVariable2, which will become deprecated.

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

Definition at line 1313 of file SymbolicExpression.h.

References isConstant().

◆ print()

virtual void Rose::BinaryAnalysis::SymbolicExpression::Leaf::print	(	std::ostream &	,
		Formatter &
	)		const

overridevirtual

Print the expression to a stream.

The output is an S-expression with no line-feeds. The format of the output is controlled by the mutable Formatter argument.

Implements Rose::BinaryAnalysis::SymbolicExpression::Node.

◆ isIntegerVariable()

bool Rose::BinaryAnalysis::SymbolicExpression::Leaf::isIntegerVariable ( ) const

inline

Is this node an integer variable?

Definition at line 1324 of file SymbolicExpression.h.

References Rose::BinaryAnalysis::SymbolicExpression::Type::INTEGER, isConstant(), Rose::BinaryAnalysis::SymbolicExpression::Node::type(), and Rose::BinaryAnalysis::SymbolicExpression::Type::typeClass().

◆ isFloatingPointVariable()

bool Rose::BinaryAnalysis::SymbolicExpression::Leaf::isFloatingPointVariable ( ) const

inline

Is this node a floating-point variable?

Definition at line 1329 of file SymbolicExpression.h.

References Rose::BinaryAnalysis::SymbolicExpression::Type::FP, isConstant(), Rose::BinaryAnalysis::SymbolicExpression::Node::type(), and Rose::BinaryAnalysis::SymbolicExpression::Type::typeClass().

◆ isMemoryVariable()

bool Rose::BinaryAnalysis::SymbolicExpression::Leaf::isMemoryVariable ( ) const

inline

Is this node a memory variable?

Definition at line 1337 of file SymbolicExpression.h.

References isConstant(), Rose::BinaryAnalysis::SymbolicExpression::Type::MEMORY, Rose::BinaryAnalysis::SymbolicExpression::Node::type(), and Rose::BinaryAnalysis::SymbolicExpression::Type::typeClass().

◆ nameId()

uint64_t Rose::BinaryAnalysis::SymbolicExpression::Leaf::nameId ( ) const

Returns the name ID of a free variable.

The output functions print variables as "vN" where N is an integer. It is this N that this method returns. It should only be invoked on leaf nodes for which isConstant returns false.

◆ toString()

std::string Rose::BinaryAnalysis::SymbolicExpression::Leaf::toString ( ) const

Returns a string for the leaf.

Integer and floating-point variables are returned as "vN", memory variables are returned as "mN", and constants are returned as a hexadecimal string, where N is a variable identification number.

◆ printAsUnsigned()

void Rose::BinaryAnalysis::SymbolicExpression::Leaf::printAsUnsigned	(	std::ostream &	o,
		Formatter &	f
	)		const

inline

Prints an integer constant interpreted as an unsigned value.

Definition at line 1357 of file SymbolicExpression.h.

References printAsSigned().

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

SymbolicExpression.h

Description

Public Member Functions

Static Public Member Functions

Additional Inherited Members

Member Function Documentation

◆ nChildren()

◆ child()

◆ childRaw()

◆ children()

◆ getOperator()

◆ mustEqual()

◆ mayEqual()

◆ isEquivalentTo()

◆ isEquivalentHelper()

◆ compareStructure()

◆ substitute()

◆ depthFirstTraversal()

◆ nNodes()

◆ toUnsigned()

◆ toSigned()

◆ isConstant()

◆ isVariable2()

◆ print()

◆ isIntegerVariable()

◆ isFloatingPointVariable()

◆ isMemoryVariable()

◆ nameId()

◆ toString()

◆ printAsUnsigned()