Description

Base class for symbolic expression nodes.

Every node has a specified width measured in bits that is constant over the life of the node. The width is always a concrete, positive value stored in a 64-bit field. The corollary of this invariant is that if an expression's result width depends on the values of some of its arguments, those arguments must be concrete and not wider than 64 bits. Only a few operators fall into this category since most expressions depend on the widths of their arguments rather than the values of their arguments.

In order that subtrees can be freely assigned as children of other nodes (provided the structure as a whole remains a lattice and not a graph with cycles), two things are required: First, expression tree nodes are always referenced through shared-ownership pointers that collectively own the expression node (expressions are never explicitly deleted). Second, expression nodes are immutable once they're instantiated. There are a handful of exceptions to the immutable rule: comments and attributes are allowed to change freely since they're not significant to hashing or arithmetic operations.

Each node has a bit flags property, the bits of which are defined by the user. New nodes are created having all bits cleared unless the user specifies a value in the constructor. Bits are significant for hashing. Simplifiers produce result expressions whose bits are set in a predictable manner with the following rules:

Interior Node Rule: The flags for an interior node are the union of the flags of its subtrees.

Simplification Discard Rule: If a simplification discards a subtree then that subtree does not contribute flags to the result. E.g., cancellation of terms in an add operation.

Simplification Create Rule: If a simplification creates a new leaf node that doesn't depend on the input expression that new leaf node will have zero flags. E.g., XOR of an expression with itself; an add operation where all the terms cancel each other resulting in zero.

Simplification Folding Rule: If a simplification creates a new expression from some combination of incoming expressions then the flags of the new expression are the union of the flags from the expressions on which it depends. E.g., constant folding, which is therefore consistent with the Interior Node Rule.

Hashing Rule: User-defined flags are significant for hashing. E.g., structural equivalence will return false if the two expressions have different flags since structural equivalence uses hashes.

Relational Operator Rule: Simplification of relational operators to produce a Boolean constant will act as if they are performing constant folding even if the simplification is on variables. E.g., (ule v1 v1) results in true with flags the same as v1.

Definition at line 455 of file SymbolicExpression.h.

#include <Rose/BinaryAnalysis/SymbolicExpression.h>

Inheritance diagram for Rose::BinaryAnalysis::SymbolicExpression::Node:

[legend]

Collaboration diagram for Rose::BinaryAnalysis::SymbolicExpression::Node:

[legend]

Classes
class	WithFormatter
	A node with formatter. More...

Public Types
using	EquivPairs = std::map< Node , std::vector< std::pair< Node , bool > > >

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

Public Member Functions
Type	type () const
	Type of value.

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

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

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

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

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

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.

virtual Operator	getOperator () const =0
	Operator for interior nodes.

virtual size_t	nChildren () const =0
	Number of arguments.

virtual const Nodes &	children () const =0
	Arguments.

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

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

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.

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

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.

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

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.

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

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

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.

virtual bool	isEquivalentHelper (Node *, EquivPairs &)=0


virtual const Ptr &	child (size_t idx) const =0
	Argument.

virtual const Node *	childRaw (size_t idx) const =0
	Argument.


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.


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

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 >
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 Attributes
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
	Node (const std::string &comment, unsigned flags=0)

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

Protected Attributes
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.

Additional Inherited Members
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)

Member Typedef Documentation

◆ EquivPairs

using Rose::BinaryAnalysis::SymbolicExpression::Node::EquivPairs = std::map<Node*, std::vector<std::pair<Node*, bool> >>

Definition at line 878 of file SymbolicExpression.h.

Constructor & Destructor Documentation

◆ ~Node()

virtual Rose::BinaryAnalysis::SymbolicExpression::Node::~Node ( )

inlinevirtual

Definition at line 503 of file SymbolicExpression.h.

◆ Node() [1/2]

Rose::BinaryAnalysis::SymbolicExpression::Node::Node ( )

inlineprotected

Definition at line 506 of file SymbolicExpression.h.

◆ Node() [2/2]

Rose::BinaryAnalysis::SymbolicExpression::Node::Node	(	const std::string &	comment,
		unsigned	flags = `0`
	)

inlineexplicitprotected

Definition at line 508 of file SymbolicExpression.h.

Member Function Documentation

◆ type()

Type Rose::BinaryAnalysis::SymbolicExpression::Node::type ( ) const

inline

Type of value.

Definition at line 513 of file SymbolicExpression.h.

Referenced by Rose::BinaryAnalysis::SymbolicExpression::Leaf::isFloatingPointVariable(), Rose::BinaryAnalysis::SymbolicExpression::Leaf::isIntegerVariable(), and Rose::BinaryAnalysis::SymbolicExpression::Leaf::isMemoryVariable().

◆ mustEqual()

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

pure virtual

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).

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

◆ mayEqual()

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

pure virtual

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

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

◆ isEquivalentTo()

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

pure virtual

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.

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

◆ compareStructure()

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

pure virtual

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.

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

◆ substitute()

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

pure virtual

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.

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

◆ substituteMultiple()

Ptr Rose::BinaryAnalysis::SymbolicExpression::Node::substituteMultiple	(	const ExprExprHashMap &	substitutions,
		const SmtSolverPtr &	solver = `SmtSolverPtr()`
	)

Rewrite expression by substituting subexpressions.

This expression is rewritten by doing a depth-first traversal. At each step of the traversal, the subexpression is looked up by hash in the supplied substitutions table. If found, a new expression is created using the value found in the table and the traversal does not descend into the new expression. If no substitutions were performed then this expression is returned, otherwise a new expression is returned. An optional solver, which may be null, is used during the simplification step.

◆ renameVariables()

Ptr Rose::BinaryAnalysis::SymbolicExpression::Node::renameVariables	(	ExprExprHashMap &	index,
		size_t &	nextVariableId,
		const SmtSolverPtr &	solver = `SmtSolverPtr()`
	)

Rewrite using lowest numbered variable names.

Given an expression, use the specified index to rewrite variables. The index uses expression hashes to look up the replacement expression. If the traversal finds a variable which is not in the index then a new variable is created. The new variable has the same type as the original variable, but it's name is generated starting at nextVariableId and incrementing after each replacement is generated. The optional solver is used during the simplification process and may be null.

◆ getOperator()

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

pure virtual

Operator for interior nodes.

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

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

◆ nChildren()

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

pure virtual

Number of arguments.

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

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

◆ child()

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

pure virtual

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.

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

◆ childRaw()

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

pure virtual

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.

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

◆ children()

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

pure virtual

Arguments.

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

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

◆ toUnsigned()

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

pure virtual

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.

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

◆ toSigned()

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

pure virtual

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.

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

◆ isIntegerExpr()

bool Rose::BinaryAnalysis::SymbolicExpression::Node::isIntegerExpr ( ) const

inline

True if this expression is of an integer type.

Definition at line 612 of file SymbolicExpression.h.

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

Referenced by isIntegerConstant(), isIntegerVariable(), and isScalarExpr().

◆ isFloatingPointExpr()

bool Rose::BinaryAnalysis::SymbolicExpression::Node::isFloatingPointExpr ( ) const

inline

True if this expression is of a floating-point type.

Definition at line 617 of file SymbolicExpression.h.

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

Referenced by isFloatingPointConstant(), isFloatingPointVariable(), and isScalarExpr().

◆ isMemoryExpr()

bool Rose::BinaryAnalysis::SymbolicExpression::Node::isMemoryExpr ( ) const

inline

True if this expression is of a memory type.

Definition at line 622 of file SymbolicExpression.h.

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

Referenced by isMemoryVariable().

◆ isScalarExpr()

bool Rose::BinaryAnalysis::SymbolicExpression::Node::isScalarExpr ( ) const

inline

True if the expression is a scalar type.

Integers and floating-point expressions are scalar, memory is not.

Definition at line 629 of file SymbolicExpression.h.

References isFloatingPointExpr(), and isIntegerExpr().

◆ isConstant()

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

pure virtual

True if this expression is a constant.

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

Referenced by isFloatingPointConstant(), and isIntegerConstant().

◆ isIntegerConstant()

bool Rose::BinaryAnalysis::SymbolicExpression::Node::isIntegerConstant ( ) const

inline

True if this expression is an integer constant.

Definition at line 637 of file SymbolicExpression.h.

References isConstant(), and isIntegerExpr().

Referenced by isScalarConstant().

◆ isFloatingPointConstant()

bool Rose::BinaryAnalysis::SymbolicExpression::Node::isFloatingPointConstant ( ) const

inline

True if this epxression is a floating-point constant.

Definition at line 642 of file SymbolicExpression.h.

References isConstant(), and isFloatingPointExpr().

Referenced by isScalarConstant().

◆ isScalarConstant()

bool Rose::BinaryAnalysis::SymbolicExpression::Node::isScalarConstant ( ) const

inline

True if this expression is a scalar constant.

Integer and floating-point constants are scalar.

Definition at line 649 of file SymbolicExpression.h.

References isFloatingPointConstant(), and isIntegerConstant().

◆ isVariable2()

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

pure virtual

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.

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

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

◆ variableId()

Sawyer::Optional< uint64_t > Rose::BinaryAnalysis::SymbolicExpression::Node::variableId ( ) const

Variable ID number.

If this expression is a variable then returns the variable ID number, otherwise nothing.

◆ isIntegerVariable()

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

inline

True if this expression is an integer variable.

Definition at line 669 of file SymbolicExpression.h.

References isIntegerExpr(), and isVariable2().

Referenced by isScalarVariable().

◆ isFloatingPointVariable()

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

inline

True if this expression is a floating-point variable.

Definition at line 674 of file SymbolicExpression.h.

References isFloatingPointExpr(), and isVariable2().

Referenced by isScalarVariable().

◆ isMemoryVariable()

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

inline

True if this expression is a memory state variable.

Definition at line 679 of file SymbolicExpression.h.

References isMemoryExpr(), and isVariable2().

◆ isScalarVariable()

bool Rose::BinaryAnalysis::SymbolicExpression::Node::isScalarVariable ( ) const

inline

True if this expression is a scalar variable.

Integer and floating-point variables are scalar, memory variables are not.

Definition at line 686 of file SymbolicExpression.h.

References isFloatingPointVariable(), and isIntegerVariable().

◆ comment() [1/2]

const std::string & Rose::BinaryAnalysis::SymbolicExpression::Node::comment ( ) const

inline

Property: Comment.

Comments can be changed after a node has been created since the comment is not intended to be used for anything but annotation and/or debugging. If many expressions are sharing the same node, then the comment is changed in all those expressions. Changing the comment property is allowed even though nodes are generally immutable because comments are not considered significant for comparisons, computing hash values, etc.

Definition at line 698 of file SymbolicExpression.h.

References comment_.

Referenced by Rose::BinaryAnalysis::SymbolicExpression::substitute().

◆ comment() [2/2]

void Rose::BinaryAnalysis::SymbolicExpression::Node::comment ( const std::string & s )

inline

Property: Comment.

Comments can be changed after a node has been created since the comment is not intended to be used for anything but annotation and/or debugging. If many expressions are sharing the same node, then the comment is changed in all those expressions. Changing the comment property is allowed even though nodes are generally immutable because comments are not considered significant for comparisons, computing hash values, etc.

Definition at line 701 of file SymbolicExpression.h.

References comment_.

◆ userData() [1/2]

void Rose::BinaryAnalysis::SymbolicExpression::Node::userData ( boost::any & data )

inline

Property: User-defined data.

User defined data is always optional and does not contribute to the hash value of an expression. The user-defined data can be changed at any time by the user even if the expression node to which it is attached is shared between many expressions.

Definition at line 713 of file SymbolicExpression.h.

References userData_.

◆ userData() [2/2]

const boost::any & Rose::BinaryAnalysis::SymbolicExpression::Node::userData ( ) const

inline

Property: User-defined data.

User defined data is always optional and does not contribute to the hash value of an expression. The user-defined data can be changed at any time by the user even if the expression node to which it is attached is shared between many expressions.

Definition at line 716 of file SymbolicExpression.h.

References userData_.

◆ nBits()

size_t Rose::BinaryAnalysis::SymbolicExpression::Node::nBits ( ) const

inline

Property: Number of significant bits.

An expression with a known value is guaranteed to have all higher-order bits cleared.

Definition at line 724 of file SymbolicExpression.h.

References Rose::BinaryAnalysis::SymbolicExpression::Type::nBits().

◆ flags()

unsigned Rose::BinaryAnalysis::SymbolicExpression::Node::flags ( ) const

inline

Property: User-defined bit flags.

This property is significant for hashing, comparisons, and possibly other operations, therefore it is immutable. To change the flags one must create a new expression; see newFlags.

Definition at line 732 of file SymbolicExpression.h.

References flags_.

Referenced by Rose::BinaryAnalysis::SymbolicExpression::substitute().

◆ newFlags()

Ptr Rose::BinaryAnalysis::SymbolicExpression::Node::newFlags ( unsigned flags ) const

Sets flags.

Since symbolic expressions are immutable it is not possible to change the flags directly. Therefore if the desired flags are different than the current flags a new expression is created that is the same in every other respect. If the flags are not changed then the original expression is returned.

◆ domainWidth()

size_t Rose::BinaryAnalysis::SymbolicExpression::Node::domainWidth ( ) const

inline

Property: Width for memory expressions.

The return value is non-zero if and only if this tree node is a memory expression.

Definition at line 744 of file SymbolicExpression.h.

References Rose::BinaryAnalysis::SymbolicExpression::Type::addressWidth().

◆ isScalar()

bool Rose::BinaryAnalysis::SymbolicExpression::Node::isScalar ( ) const

inline

Check whether expression is scalar.

Everything is scalar except for memory.

Definition at line 751 of file SymbolicExpression.h.

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

◆ depthFirstTraversal()

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

pure virtual

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.

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

◆ nNodes()

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

pure virtual

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

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

◆ isInteriorNode()

InteriorPtr Rose::BinaryAnalysis::SymbolicExpression::Node::isInteriorNode ( ) const

Dynamic cast of this object to an interior node.

Returns null if the cast is not valid.

◆ isInteriorNodeRaw()

Interior * Rose::BinaryAnalysis::SymbolicExpression::Node::isInteriorNodeRaw ( ) const

Dynamic cast of this object to an interior node.

Returns null if the cast is not valid.

Referenced by Rose::BinaryAnalysis::SymbolicExpression::substitute().

◆ isLeafNode()

LeafPtr Rose::BinaryAnalysis::SymbolicExpression::Node::isLeafNode ( ) const

Dynamic cast of this object to a leaf node.

Returns null if the cast is not valid.

◆ isLeafNodeRaw()

Leaf * Rose::BinaryAnalysis::SymbolicExpression::Node::isLeafNodeRaw ( ) const

Dynamic cast of this object to a leaf node.

Returns null if the cast is not valid.

◆ isHashed()

bool Rose::BinaryAnalysis::SymbolicExpression::Node::isHashed ( ) const

inline

Returns true if this node has a hash value computed and cached.

The hash value zero is reserved to indicate that no hash has been computed; if a node happens to actually hash to zero, it will not be cached and will be recomputed for every call to hash().

Definition at line 805 of file SymbolicExpression.h.

References hashval_.

◆ hash()

Hash Rose::BinaryAnalysis::SymbolicExpression::Node::hash ( ) const

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

If a hash value is not cached in this node, then a new hash value is computed and cached.

◆ withFormat()

WithFormatter Rose::BinaryAnalysis::SymbolicExpression::Node::withFormat ( Formatter & fmt )

inline

Combines a node with a formatter for printing.

This is used for convenient printing with the "<<" operator. For instance:

Formatter fmt;
fmt.show_comments = Formatter::CMT_AFTER; //show comments after the variable
Ptr expression = ...;
std::cout <<"method 1: "; expression->print(std::cout, fmt); std::cout <<"\n";
std::cout <<"method 2: " <<expression->withFormat(fmt) <<"\n";
std::cout <<"method 3: " <<*expression+fmt <<"\n";

Definition at line 839 of file SymbolicExpression.h.

References Sawyer::SharedFromThis< Node >::sharedFromThis().

Referenced by operator+().

◆ operator+()

WithFormatter Rose::BinaryAnalysis::SymbolicExpression::Node::operator+ ( Formatter & fmt )

inline

Combines a node with a formatter for printing.

This is used for convenient printing with the "<<" operator. For instance:

Formatter fmt;
fmt.show_comments = Formatter::CMT_AFTER; //show comments after the variable
Ptr expression = ...;
std::cout <<"method 1: "; expression->print(std::cout, fmt); std::cout <<"\n";
std::cout <<"method 2: " <<expression->withFormat(fmt) <<"\n";
std::cout <<"method 3: " <<*expression+fmt <<"\n";

Definition at line 840 of file SymbolicExpression.h.

References withFormat().

◆ print() [1/2]

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

pure virtual

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.

Implemented in Rose::BinaryAnalysis::SymbolicExpression::Interior, and Rose::BinaryAnalysis::SymbolicExpression::Leaf.

◆ print() [2/2]

void Rose::BinaryAnalysis::SymbolicExpression::Node::print ( std::ostream & o ) const

inline

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.

Definition at line 848 of file SymbolicExpression.h.

References print().

Referenced by print().

◆ assertAcyclic()

void Rose::BinaryAnalysis::SymbolicExpression::Node::assertAcyclic ( ) const

Asserts that expressions are acyclic.

This is intended only for debugging.

◆ findCommonSubexpressions()

std::vector< Ptr > Rose::BinaryAnalysis::SymbolicExpression::Node::findCommonSubexpressions ( ) const

Find common subexpressions.

Returns a vector of the largest common subexpressions. The list is computed by performing a depth-first search on this expression and adding expressions to the return vector whenever a subtree is encountered a second time. Therefore the if a common subexpression A contains another common subexpression B then B will appear earlier in the list than A.

◆ matchAddVariableConstant()

bool Rose::BinaryAnalysis::SymbolicExpression::Node::matchAddVariableConstant	(	LeafPtr &	variable,
		LeafPtr &	constant
	)		const

Determine whether an expression is a variable plus a constant.

If this expression is of the form V + X or X + V where V is an integer variable and X is an integer constant, return true and make variable point to the variable and constant point to the constant. If the expression is not one of these forms, then return false without modifying the arguments.

Member Data Documentation

◆ type_

Type Rose::BinaryAnalysis::SymbolicExpression::Node::type_

protected

Definition at line 461 of file SymbolicExpression.h.

◆ flags_

unsigned Rose::BinaryAnalysis::SymbolicExpression::Node::flags_

protected

Bit flags.

Meaning of flags is up to the user. Low-order 16 bits are reserved.

Definition at line 462 of file SymbolicExpression.h.

Referenced by flags().

◆ comment_

std::string Rose::BinaryAnalysis::SymbolicExpression::Node::comment_

protected

Optional comment.

Only for debugging; not significant for any calculation.

Definition at line 463 of file SymbolicExpression.h.

Referenced by comment(), and comment().

◆ hashval_

Hash Rose::BinaryAnalysis::SymbolicExpression::Node::hashval_

mutableprotected

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

Definition at line 464 of file SymbolicExpression.h.

Referenced by isHashed().

◆ userData_

boost::any Rose::BinaryAnalysis::SymbolicExpression::Node::userData_

protected

Additional user-specified data.

This is not part of the hash.

Definition at line 465 of file SymbolicExpression.h.

Referenced by userData(), and userData().

◆ RESERVED_FLAGS

const unsigned Rose::BinaryAnalysis::SymbolicExpression::Node::RESERVED_FLAGS = 0x0000ffff

static

These flags are reserved for use within ROSE.

Definition at line 487 of file SymbolicExpression.h.

◆ INDETERMINATE

const unsigned Rose::BinaryAnalysis::SymbolicExpression::Node::INDETERMINATE = 0x00000001

static

Value is somehow indeterminate.

E.g., read from writable memory.

Definition at line 490 of file SymbolicExpression.h.

◆ UNSPECIFIED

const unsigned Rose::BinaryAnalysis::SymbolicExpression::Node::UNSPECIFIED = 0x00000002

static

Value is somehow unspecified.

A value that is intantiated as part of processing a machine instruction where the ISA documentation is incomplete or says that some result is unspecified or undefined. Intel documentation for the x86 shift and rotate instructions, for example, states that certain status bits have "undefined" values after the instruction executes.

Definition at line 496 of file SymbolicExpression.h.

Referenced by Rose::BinaryAnalysis::InstructionSemantics::TaintSemantics::SValue::instance_unspecified().

◆ BOTTOM

const unsigned Rose::BinaryAnalysis::SymbolicExpression::Node::BOTTOM = 0x00000004

static

Value represents bottom in dataflow analysis.

If this flag is used by ROSE's dataflow engine to represent a bottom value in a lattice.

Definition at line 500 of file SymbolicExpression.h.

Referenced by Rose::BinaryAnalysis::InstructionSemantics::TaintSemantics::SValue::instance_bottom().

◆ mayEqualCallback

boost::logic::tribool(* Rose::BinaryAnalysis::SymbolicExpression::Node::mayEqualCallback) (const Ptr &a, const Ptr &b, const SmtSolverPtr &)

static

User-supplied predicate to augment alias checking.

If this pointer is non-null, then the mayEqual methods invoke this function. If this function returns true or false, then its return value becomes the return value of mayEqual, otherwise mayEqual continues as it normally would. This user-defined function is invoked by mayEqual after trivial situations are checked and before any calls to an SMT solver. The SMT solver argument is optional (may be null).

Definition at line 523 of file SymbolicExpression.h.

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

SymbolicExpression.h

Description

Classes

Public Types

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Additional Inherited Members

Member Typedef Documentation

◆ EquivPairs

Constructor & Destructor Documentation

◆ ~Node()

◆ Node() [1/2]

◆ Node() [2/2]

Member Function Documentation

◆ type()

◆ mustEqual()

◆ mayEqual()

◆ isEquivalentTo()

◆ compareStructure()

◆ substitute()

◆ substituteMultiple()

◆ renameVariables()

◆ getOperator()

◆ nChildren()

◆ child()

◆ childRaw()

◆ children()

◆ toUnsigned()

◆ toSigned()

◆ isIntegerExpr()

◆ isFloatingPointExpr()

◆ isMemoryExpr()

◆ isScalarExpr()

◆ isConstant()

◆ isIntegerConstant()

◆ isFloatingPointConstant()

◆ isScalarConstant()

◆ isVariable2()

◆ variableId()

◆ isIntegerVariable()

◆ isFloatingPointVariable()

◆ isMemoryVariable()

◆ isScalarVariable()

◆ comment() [1/2]

◆ comment() [2/2]

◆ userData() [1/2]

◆ userData() [2/2]

◆ nBits()

◆ flags()

◆ newFlags()

◆ domainWidth()

◆ isScalar()

◆ depthFirstTraversal()

◆ nNodes()

◆ isInteriorNode()

◆ isInteriorNodeRaw()

◆ isLeafNode()

◆ isLeafNodeRaw()

◆ isHashed()

◆ hash()

◆ withFormat()

◆ operator+()

◆ print() [1/2]

◆ print() [2/2]

◆ assertAcyclic()

◆ findCommonSubexpressions()

◆ matchAddVariableConstant()

Member Data Documentation

◆ type_

◆ flags_

◆ comment_

◆ hashval_

◆ userData_

◆ RESERVED_FLAGS

◆ INDETERMINATE

◆ UNSPECIFIED

◆ BOTTOM

◆ mayEqualCallback