ROSE  0.10.0.0
Public Member Functions | Static Public Member Functions | Public Attributes | List of all members
Rose::BinaryAnalysis::SymbolicExpr::Leaf Class Reference

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 1250 of file BinarySymbolicExpr.h.

#include <BinarySymbolicExpr.h>

Inheritance diagram for Rose::BinaryAnalysis::SymbolicExpr::Leaf:
Inheritance graph
[legend]
Collaboration diagram for Rose::BinaryAnalysis::SymbolicExpr::Leaf:
Collaboration graph
[legend]

Public Member Functions

virtual size_t nChildren () const ROSE_OVERRIDE
 Number of arguments. More...
 
virtual Ptr child (size_t idx) const ROSE_OVERRIDE
 Argument. More...
 
virtual const Nodes & children () const ROSE_OVERRIDE
 Arguments. More...
 
virtual Operator getOperator () const ROSE_OVERRIDE
 Operator for interior nodes. More...
 
virtual bool mustEqual (const Ptr &other, const SmtSolverPtr &solver=SmtSolverPtr()) ROSE_OVERRIDE
 Returns true if two expressions must be equal (cannot be unequal). More...
 
virtual bool mayEqual (const Ptr &other, const SmtSolverPtr &solver=SmtSolverPtr()) ROSE_OVERRIDE
 Returns true if two expressions might be equal, but not necessarily be equal. More...
 
virtual bool isEquivalentTo (const Ptr &other) ROSE_OVERRIDE
 Tests two expressions for structural equivalence. More...
 
virtual int compareStructure (const Ptr &other) ROSE_OVERRIDE
 Compare two expressions structurally for sorting. More...
 
virtual Ptr substitute (const Ptr &from, const Ptr &to, const SmtSolverPtr &solver=SmtSolverPtr()) ROSE_OVERRIDE
 Substitute one value for another. More...
 
virtual VisitAction depthFirstTraversal (Visitor &) const ROSE_OVERRIDE
 Traverse the expression. More...
 
virtual uint64_t nNodes () const ROSE_OVERRIDE
 Computes the size of an expression by counting the number of nodes. More...
 
virtual Sawyer::Optional< uint64_t > toUnsigned () const ROSE_OVERRIDE
 The unsigned integer value of the expression. More...
 
virtual Sawyer::Optional< int64_t > toSigned () const ROSE_OVERRIDE
 The signed integer value of the expression. More...
 
virtual bool isConstant () const ROSE_OVERRIDE
 True if this expression is a constant. More...
 
virtual bool isVariable2 () const ROSE_OVERRIDE
 True if this expression is a variable. More...
 
virtual void print (std::ostream &, Formatter &) const ROSE_OVERRIDE
 Print the expression to a stream. More...
 
const Sawyer::Container::BitVectorbits () const
 Property: Bits stored for numeric constants. More...
 
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. More...
 
std::string toString () const
 Returns a string for the leaf. More...
 
void printAsSigned (std::ostream &, Formatter &, bool asSigned=true) const
 Prints an integer constant interpreted as a signed value. More...
 
void printAsUnsigned (std::ostream &o, Formatter &f) const
 Prints an integer constant interpreted as an unsigned value. More...
 
bool isVariable () const ROSE_DEPRECATED("use isIntegerVariable or isVariable2 instead")
 
virtual bool isMemory () ROSE_DEPRECATED("use isMemoryVariable or isMemoryExpr instead")
 
- Public Member Functions inherited from Rose::BinaryAnalysis::SymbolicExpr::Node
Type type () const
 Type of value. More...
 
Ptr substituteMultiple (const ExprExprHashMap &substitutions, const SmtSolverPtr &solver=SmtSolverPtr())
 Rewrite expression by substituting subexpressions. More...
 
Ptr renameVariables (ExprExprHashMap &index, size_t &nextVariableId, const SmtSolverPtr &solver=SmtSolverPtr())
 Rewrite using lowest numbered variable names. More...
 
bool isIntegerExpr () const
 True if this expression is of an integer type. More...
 
bool isFloatingPointExpr () const
 True if this expression is of a floating-point type. More...
 
bool isMemoryExpr () const
 True if this expression is of a memory type. More...
 
bool isScalarExpr () const
 True if the expression is a scalar type. More...
 
bool isIntegerConstant () const
 True if this expression is an integer constant. More...
 
bool isFloatingPointConstant () const
 True if this epxression is a floating-point constant. More...
 
bool isScalarConstant () const
 True if this expression is a scalar constant. More...
 
bool isFloatingPointNan () const
 True if this expression is a floating-point NaN constant. More...
 
Sawyer::Optional< uint64_t > variableId () const
 Variable ID number. More...
 
bool isIntegerVariable () const
 True if this expression is an integer variable. More...
 
bool isFloatingPointVariable () const
 True if this expression is a floating-point variable. More...
 
bool isMemoryVariable () const
 True if this expression is a memory state variable. More...
 
bool isScalarVariable () const
 True if this expression is a scalar variable. More...
 
size_t nBits () const
 Property: Number of significant bits. More...
 
unsigned flags () const
 Property: User-defined bit flags. More...
 
Ptr newFlags (unsigned flags) const
 Sets flags. More...
 
size_t domainWidth () const
 Property: Width for memory expressions. More...
 
bool isScalar () const
 Check whether expression is scalar. More...
 
uint64_t nNodesUnique () const
 Number of unique nodes in expression. More...
 
std::set< LeafPtrgetVariables () const
 Returns the variables appearing in the expression. More...
 
InteriorPtr isInteriorNode () const
 Dynamic cast of this object to an interior node. More...
 
LeafPtr isLeafNode () const
 Dynamic cast of this object to a leaf node. More...
 
bool isHashed () const
 Returns true if this node has a hash value computed and cached. More...
 
Hash hash () const
 Returns (and caches) the hash value for this node. More...
 
void hash (Hash)
 
void assertAcyclic () const
 Asserts that expressions are acyclic. More...
 
std::vector< PtrfindCommonSubexpressions () const
 Find common subexpressions. More...
 
bool matchAddVariableConstant (LeafPtr &variable, LeafPtr &constant) const
 Determine whether an expression is a variable plus a constant. More...
 
InteriorPtr isOperator (Operator) const
 True (non-null) if this node is the specified operator. More...
 
bool isNumber () const ROSE_DEPRECATED("use isIntegerConstant instead")
 
uint64_t toInt () ROSE_DEPRECATED("use toUnsigned() instead")
 
const std::string & comment () const
 Property: Comment. More...
 
void comment (const std::string &s)
 Property: Comment. More...
 
void userData (boost::any &data)
 Property: User-defined data. More...
 
const boost::any & userData () const
 Property: User-defined data. More...
 
WithFormatter withFormat (Formatter &fmt)
 Combines a node with a formatter for printing. More...
 
WithFormatter operator+ (Formatter &fmt)
 Combines a node with a formatter for printing. More...
 
void print (std::ostream &o) const
 Print the expression to a stream. More...
 
- Public Member Functions inherited from Sawyer::SharedObject
 SharedObject ()
 Default constructor. More...
 
 SharedObject (const SharedObject &)
 Copy constructor. More...
 
virtual ~SharedObject ()
 Virtual destructor. More...
 
SharedObjectoperator= (const SharedObject &)
 Assignment. More...
 
- Public Member Functions inherited from Sawyer::SharedFromThis< Node >
SharedPointer< Node > sharedFromThis ()
 Create a shared pointer from this. More...
 
SharedPointer< const Node > sharedFromThis () const
 Create a shared pointer from this. More...
 
- Public Member Functions inherited from Sawyer::Attribute::Storage<>
 Storage ()
 Default constructor. More...
 
 Storage (const Storage &other)
 Copy constructor. More...
 
Storageoperator= (const Storage &other)
 Assignment operator. More...
 
bool attributeExists (Id id) const
 Check attribute existence. More...
 
void eraseAttribute (Id id)
 Erase an attribute. More...
 
void clearAttributes ()
 Erase all attributes. More...
 
void setAttribute (Id id, const T &value)
 Store an attribute. More...
 
bool setAttributeMaybe (Id id, const T &value)
 Store an attribute if not already present. More...
 
getAttribute (Id id) const
 Get an attribute that is known to exist. More...
 
attributeOrElse (Id id, const T &dflt) const
 Return an attribute or a specified value. More...
 
attributeOrDefault (Id id) const
 Return an attribute or a default-constructed value. More...
 
Sawyer::Optional< T > optionalAttribute (Id id) const
 Return the attribute as an optional value. More...
 
size_t nAttributes () const
 Number of attributes stored. More...
 
std::vector< IdattributeIds () const
 Returns ID numbers for all IDs stored in this container. More...
 

Static Public Member Functions

static LeafPtr createVariable (const Type &, const std::string &comment="", unsigned flags=0)
 Create a new variable. More...
 
static LeafPtr createVariable (const Type &, const uint64_t id, const std::string &comment="", unsigned flags=0)
 Create an existing variable. More...
 
static LeafPtr createConstant (const Type &, const Sawyer::Container::BitVector &, const std::string &comment="", unsigned flags=0)
 Create a constant. More...
 
static LeafPtr createVariable (size_t nBits, const std::string &comment="", unsigned flags=0) ROSE_DEPRECATED("use createVariable with type or makeIntegerVariable
 
static LeafPtr createExistingVariable (size_t nBits, uint64_t id, const std::string &comment="", unsigned flags=0) ROSE_DEPRECATED("use createVariable or makeIntegerVariable
 
static LeafPtr createInteger (size_t nBits, uint64_t value, const std::string &comment="", unsigned flags=0) ROSE_DEPRECATED("use createConstant or makeIntegerConstant
 
static LeafPtr createConstant (const Sawyer::Container::BitVector &bits, const std::string &comment="", unsigned flags=0) ROSE_DEPRECATED("use createConstant with type or makeIntegerConstant
 
static LeafPtr createBoolean (bool b, const std::string &comment="", unsigned flags=0) ROSE_DEPRECATED("use createConstant or makeBooleanConstant")
 
static LeafPtr createMemory (size_t addressWidth, size_t valueWidth, const std::string &comment="", unsigned flags=0) ROSE_DEPRECATED("use createVariable with type or makeMemoryVariable")
 
static LeafPtr createExistingMemory (size_t addressWidth, size_t valueWidth, uint64_t id, const std::string &comment="", unsigned flags=0) ROSE_DEPRECATED("use createVariable with type or makeMemoryVariable")
 
- Static Public Member Functions inherited from Sawyer::SmallObject
static SynchronizedPoolAllocatorpoolAllocator ()
 Return the pool allocator for this class. More...
 
static void * operator new (size_t size)
 
static void operator delete (void *ptr, size_t size)
 

Public Attributes

static LeafPtr etc
 

Additional Inherited Members

- Public Types inherited from Sawyer::Attribute::Storage<>
typedef SynchronizationTraits< Sawyer::SingleThreadedTagSync
 
- Static Public Attributes inherited from Rose::BinaryAnalysis::SymbolicExpr::Node
static const unsigned RESERVED_FLAGS = 0x0000ffff
 These flags are reserved for use within ROSE. More...
 
static const unsigned INDETERMINATE = 0x00000001
 Value is somehow indeterminate. More...
 
static const unsigned UNSPECIFIED = 0x00000002
 Value is somehow unspecified. More...
 
static const unsigned BOTTOM = 0x00000004
 Value represents bottom in dataflow analysis. More...
 
static boost::logic::tribool(* mayEqualCallback )(const Ptr &a, const Ptr &b, const SmtSolverPtr &)
 User-supplied predicate to augment alias checking. More...
 
- Protected Member Functions inherited from Rose::BinaryAnalysis::SymbolicExpr::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::SymbolicExpr::Node
Type type_
 
unsigned flags_
 Bit flags. More...
 
std::string comment_
 Optional comment. More...
 
Hash hashval_
 Optional hash used as a quick way to indicate that two expressions are different. More...
 
boost::any userData_
 Additional user-specified data. More...
 

Member Function Documentation

static LeafPtr Rose::BinaryAnalysis::SymbolicExpr::Leaf::createVariable ( const Type ,
const std::string &  comment = "",
unsigned  flags = 0 
)
static

Create a new variable.

static LeafPtr Rose::BinaryAnalysis::SymbolicExpr::Leaf::createVariable ( const Type ,
const uint64_t  id,
const std::string &  comment = "",
unsigned  flags = 0 
)
static

Create an existing variable.

static LeafPtr Rose::BinaryAnalysis::SymbolicExpr::Leaf::createConstant ( const Type ,
const Sawyer::Container::BitVector ,
const std::string &  comment = "",
unsigned  flags = 0 
)
static

Create a constant.

virtual size_t Rose::BinaryAnalysis::SymbolicExpr::Leaf::nChildren ( ) const
inlinevirtual

Number of arguments.

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

Implements Rose::BinaryAnalysis::SymbolicExpr::Node.

Definition at line 1307 of file BinarySymbolicExpr.h.

virtual Ptr Rose::BinaryAnalysis::SymbolicExpr::Leaf::child ( size_t  idx) const
inlinevirtual

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::SymbolicExpr::Node.

Definition at line 1308 of file BinarySymbolicExpr.h.

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

Arguments.

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

Implements Rose::BinaryAnalysis::SymbolicExpr::Node.

virtual Operator Rose::BinaryAnalysis::SymbolicExpr::Leaf::getOperator ( ) const
inlinevirtual

Operator for interior nodes.

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

Implements Rose::BinaryAnalysis::SymbolicExpr::Node.

Definition at line 1310 of file BinarySymbolicExpr.h.

References Rose::BinaryAnalysis::SymbolicExpr::OP_NONE.

virtual bool Rose::BinaryAnalysis::SymbolicExpr::Leaf::mustEqual ( const Ptr other,
const SmtSolverPtr solver = SmtSolverPtr() 
)
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).

Implements Rose::BinaryAnalysis::SymbolicExpr::Node.

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

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

Implements Rose::BinaryAnalysis::SymbolicExpr::Node.

virtual bool Rose::BinaryAnalysis::SymbolicExpr::Leaf::isEquivalentTo ( const Ptr other)
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.

Implements Rose::BinaryAnalysis::SymbolicExpr::Node.

virtual int Rose::BinaryAnalysis::SymbolicExpr::Leaf::compareStructure ( const Ptr other)
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.

Implements Rose::BinaryAnalysis::SymbolicExpr::Node.

virtual Ptr Rose::BinaryAnalysis::SymbolicExpr::Leaf::substitute ( const Ptr from,
const Ptr to,
const SmtSolverPtr solver = SmtSolverPtr() 
)
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.

Implements Rose::BinaryAnalysis::SymbolicExpr::Node.

virtual VisitAction Rose::BinaryAnalysis::SymbolicExpr::Leaf::depthFirstTraversal ( Visitor ) const
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.

Implements Rose::BinaryAnalysis::SymbolicExpr::Node.

virtual uint64_t Rose::BinaryAnalysis::SymbolicExpr::Leaf::nNodes ( ) const
inlinevirtual

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:

SymbolicExpr 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::SymbolicExpr::Node.

Definition at line 1317 of file BinarySymbolicExpr.h.

virtual Sawyer::Optional<uint64_t> Rose::BinaryAnalysis::SymbolicExpr::Leaf::toUnsigned ( ) const
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.

Implements Rose::BinaryAnalysis::SymbolicExpr::Node.

virtual Sawyer::Optional<int64_t> Rose::BinaryAnalysis::SymbolicExpr::Leaf::toSigned ( ) const
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.

Implements Rose::BinaryAnalysis::SymbolicExpr::Node.

virtual bool Rose::BinaryAnalysis::SymbolicExpr::Leaf::isConstant ( ) const
inlinevirtual

True if this expression is a constant.

Implements Rose::BinaryAnalysis::SymbolicExpr::Node.

Definition at line 1320 of file BinarySymbolicExpr.h.

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

virtual bool Rose::BinaryAnalysis::SymbolicExpr::Leaf::isVariable2 ( ) const
inlinevirtual

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::SymbolicExpr::Node.

Definition at line 1321 of file BinarySymbolicExpr.h.

References Rose::BinaryAnalysis::SymbolicExpr::Interior::isConstant().

virtual void Rose::BinaryAnalysis::SymbolicExpr::Leaf::print ( std::ostream &  ,
Formatter  
) const
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.

Implements Rose::BinaryAnalysis::SymbolicExpr::Node.

const Sawyer::Container::BitVector& Rose::BinaryAnalysis::SymbolicExpr::Leaf::bits ( ) const

Property: Bits stored for numeric constants.

uint64_t Rose::BinaryAnalysis::SymbolicExpr::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.

std::string Rose::BinaryAnalysis::SymbolicExpr::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.

void Rose::BinaryAnalysis::SymbolicExpr::Leaf::printAsSigned ( std::ostream &  ,
Formatter ,
bool  asSigned = true 
) const

Prints an integer constant interpreted as a signed value.

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

Prints an integer constant interpreted as an unsigned value.

Definition at line 1365 of file BinarySymbolicExpr.h.

Member Data Documentation

static LeafPtr Rose::BinaryAnalysis::SymbolicExpr::Leaf::etc
Initial value:

Definition at line 1377 of file BinarySymbolicExpr.h.


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