ROSE  0.9.9.139
Public Member Functions | Protected Member Functions | List of all members
Rose::BinaryAnalysis::SymbolicExpr::Interior Class Reference

Description

Interior node of an expression tree for instruction semantics.

Each interior node has an operator (constant for the life of the node and obtainable with get_operator()) and zero or more children. Children are added to the interior node during the construction phase. Once construction is complete, the children should only change in ways that don't affect the value of the node as a whole (since this node might be pointed to by any number of expressions).

Definition at line 715 of file BinarySymbolicExpr.h.

#include <BinarySymbolicExpr.h>

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

Public Member Functions

virtual bool mustEqual (const Ptr &other, SmtSolver *) ROSE_OVERRIDE
 Returns true if two expressions must be equal (cannot be unequal). More...
 
virtual bool mayEqual (const Ptr &other, SmtSolver *) 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) ROSE_OVERRIDE
 Substitute one value for another. More...
 
virtual bool isNumber () ROSE_OVERRIDE
 Returns true if the expression is a known numeric value. More...
 
virtual uint64_t toInt () ROSE_OVERRIDE
 Property: integer value of expression node. More...
 
virtual VisitAction depthFirstTraversal (Visitor &) ROSE_OVERRIDE
 Traverse the expression. More...
 
virtual uint64_t nNodes () ROSE_OVERRIDE
 Computes the size of an expression by counting the number of nodes. More...
 
size_t nChildren ()
 Returns the number of children. More...
 
size_t nchildren () ROSE_DEPRECATED("use nChildren instead")
 
Ptr child (size_t idx)
 Returns the specified child. More...
 
const Nodes & children ()
 Property: Children. More...
 
Nodes get_children () ROSE_DEPRECATED("use 'children' property instead")
 
Operator getOperator ()
 Returns the operator. More...
 
Operator get_operator () ROSE_DEPRECATED("use getOperator instead")
 
Ptr simplifyTop ()
 Simplifies the specified interior node. More...
 
Ptr foldConstants (const Simplifier &)
 Perform constant folding. More...
 
Ptr constant_folding (const Simplifier &simplifier) ROSE_DEPRECATED("use foldConstants instead")
 
InteriorPtr associative ()
 Simplifies non-associative operators by flattening the specified interior node with its children that are the same interior node type. More...
 
InteriorPtr nonassociative () ROSE_DEPRECATED("use 'associative' instead")
 
InteriorPtr commutative ()
 Simplifies commutative operators by sorting arguments. More...
 
Ptr involutary ()
 Simplifies involutary operators. More...
 
Ptr additiveNesting ()
 Simplifies nested shift-like operators. More...
 
Ptr additive_nesting () ROSE_DEPRECATED("use additiveNesting instead")
 
Ptr identity (uint64_t ident)
 Removes identity arguments. More...
 
Ptr unaryNoOp ()
 Replaces a binary operator with its only argument. More...
 
Ptr rewrite (const Simplifier &simplifier)
 Simplify an interior node. More...
 
virtual void print (std::ostream &, Formatter &) ROSE_OVERRIDE
 Print the expression to a stream. More...
 
- Public Member Functions inherited from Rose::BinaryAnalysis::SymbolicExpr::Node
bool must_equal (const Ptr &other, SmtSolver *solver) ROSE_DEPRECATED("use mustEqual instead")
 
bool may_equal (const Ptr &other, SmtSolver *solver) ROSE_DEPRECATED("use mayEqual instead")
 
bool equivalent_to (const Ptr &other) ROSE_DEPRECATED("use isEquivalentTo instead")
 
int structural_compare (const Ptr &other) ROSE_DEPRECATED("use compareStructure instead")
 
bool is_known () ROSE_DEPRECATED("use isNumber instead")
 
uint64_t get_value () ROSE_DEPRECATED("use toInt instead")
 
const std::string & get_comment () ROSE_DEPRECATED("use 'comment' property instead")
 
void set_comment (const std::string &s) ROSE_DEPRECATED("use 'comment' property instead")
 
size_t nBits ()
 Property: Number of significant bits. More...
 
size_t get_nbits () ROSE_DEPRECATED("use 'nBits' property instead")
 
unsigned flags ()
 Property: User-defined bit flags. More...
 
unsigned get_flags () ROSE_DEPRECATED("use 'flags' property instead")
 
Ptr newFlags (unsigned flags)
 Sets flags. More...
 
size_t domainWidth ()
 Property: Width for memory expressions. More...
 
bool isScalar ()
 Check whether expression is scalar. More...
 
VisitAction depth_first_traversal (Visitor &v) ROSE_DEPRECATED("use depthFirstTraversal instead")
 
uint64_t nnodes () ROSE_DEPRECATED("use nNodes() instead")
 
uint64_t nNodesUnique ()
 Number of unique nodes in expression. More...
 
uint64_t nnodesUnique () ROSE_DEPRECATED("use nNodesUnique instead")
 
std::set< LeafPtrgetVariables ()
 Returns the variables appearing in the expression. More...
 
std::set< LeafPtrget_variables () ROSE_DEPRECATED("use getVariables instead")
 
InteriorPtr isInteriorNode ()
 Dynamic cast of this object to an interior node. More...
 
InteriorPtr isInternalNode () ROSE_DEPRECATED("use isInteriorNode instead")
 
LeafPtr isLeafNode ()
 Dynamic cast of this object to a leaf node. More...
 
bool isHashed ()
 Returns true if this node has a hash value computed and cached. More...
 
bool is_hashed () ROSE_DEPRECATED("use isHashed instead")
 
Hash hash ()
 Returns (and caches) the hash value for this node. More...
 
void hash (Hash)
 
WithFormatter with_format (Formatter &fmt) ROSE_DEPRECATED("use withFormat instead")
 
void assertAcyclic ()
 Asserts that expressions are acyclic. More...
 
void assert_acyclic ()
 
std::vector< PtrfindCommonSubexpressions ()
 Find common subexpressions. More...
 
const std::string & comment ()
 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 ()
 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)
 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 Ptr create (size_t nbits, Operator op, const Ptr &a, const std::string &comment="", unsigned flags=0)
 Create a new expression node. More...
 
static Ptr create (size_t nbits, Operator op, const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
 Create a new expression node. More...
 
static Ptr create (size_t nbits, Operator op, const Ptr &a, const Ptr &b, const Ptr &c, const std::string &comment="", unsigned flags=0)
 Create a new expression node. More...
 
static Ptr create (size_t nbits, Operator op, const Nodes &children, const std::string &comment="", unsigned flags=0)
 Create a new expression node. More...
 
- 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)
 

Protected Member Functions

void addChild (const Ptr &child)
 Appends child as a new child of this node. More...
 
void add_child (const Ptr &child) ROSE_DEPRECATED("use addChild instead")
 
void adjustWidth ()
 Adjust width based on operands. More...
 
void adjustBitFlags (unsigned extraFlags)
 Adjust user-defined bit flags. 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)
 

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...
 
- Protected Attributes inherited from Rose::BinaryAnalysis::SymbolicExpr::Node
size_t nBits_
 Number of significant bits. More...
 
size_t domainWidth_
 Width of domain for unary functions. More...
 
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 Ptr Rose::BinaryAnalysis::SymbolicExpr::Interior::create ( size_t  nbits,
Operator  op,
const Ptr a,
const std::string &  comment = "",
unsigned  flags = 0 
)
inlinestatic

Create a new expression node.

Although we're creating interior nodes, the simplification process might replace it with a leaf node. Use these class methods instead of c'tors.

Flags are normally initialized as the union of the flags of the operator arguments subject to various rules in the expression simplifiers. Flags specified in the constructor are set in addition to those that would normally be set.

Definition at line 751 of file BinarySymbolicExpr.h.

References Rose::BinaryAnalysis::SymbolicExpr::Node::comment(), and Rose::BinaryAnalysis::SymbolicExpr::Node::flags().

static Ptr Rose::BinaryAnalysis::SymbolicExpr::Interior::create ( size_t  nbits,
Operator  op,
const Ptr a,
const Ptr b,
const std::string &  comment = "",
unsigned  flags = 0 
)
inlinestatic

Create a new expression node.

Although we're creating interior nodes, the simplification process might replace it with a leaf node. Use these class methods instead of c'tors.

Flags are normally initialized as the union of the flags of the operator arguments subject to various rules in the expression simplifiers. Flags specified in the constructor are set in addition to those that would normally be set.

Definition at line 755 of file BinarySymbolicExpr.h.

References Rose::BinaryAnalysis::SymbolicExpr::Node::comment(), and Rose::BinaryAnalysis::SymbolicExpr::Node::flags().

static Ptr Rose::BinaryAnalysis::SymbolicExpr::Interior::create ( size_t  nbits,
Operator  op,
const Ptr a,
const Ptr b,
const Ptr c,
const std::string &  comment = "",
unsigned  flags = 0 
)
inlinestatic

Create a new expression node.

Although we're creating interior nodes, the simplification process might replace it with a leaf node. Use these class methods instead of c'tors.

Flags are normally initialized as the union of the flags of the operator arguments subject to various rules in the expression simplifiers. Flags specified in the constructor are set in addition to those that would normally be set.

Definition at line 760 of file BinarySymbolicExpr.h.

References Rose::BinaryAnalysis::SymbolicExpr::Node::comment(), and Rose::BinaryAnalysis::SymbolicExpr::Node::flags().

static Ptr Rose::BinaryAnalysis::SymbolicExpr::Interior::create ( size_t  nbits,
Operator  op,
const Nodes &  children,
const std::string &  comment = "",
unsigned  flags = 0 
)
inlinestatic

Create a new expression node.

Although we're creating interior nodes, the simplification process might replace it with a leaf node. Use these class methods instead of c'tors.

Flags are normally initialized as the union of the flags of the operator arguments subject to various rules in the expression simplifiers. Flags specified in the constructor are set in addition to those that would normally be set.

Definition at line 765 of file BinarySymbolicExpr.h.

References Rose::BinaryAnalysis::SymbolicExpr::Node::comment(), and Rose::BinaryAnalysis::SymbolicExpr::Node::flags().

virtual bool Rose::BinaryAnalysis::SymbolicExpr::Interior::mustEqual ( const Ptr other,
SmtSolver  
)
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::Interior::mayEqual ( const Ptr other,
SmtSolver  
)
virtual

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

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

virtual bool Rose::BinaryAnalysis::SymbolicExpr::Interior::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::Interior::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::Interior::substitute ( const Ptr from,
const Ptr to 
)
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 bool Rose::BinaryAnalysis::SymbolicExpr::Interior::isNumber ( )
inlinevirtual

Returns true if the expression is a known numeric value.

The value itself is stored in the number property.

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

Definition at line 778 of file BinarySymbolicExpr.h.

virtual uint64_t Rose::BinaryAnalysis::SymbolicExpr::Interior::toInt ( )
inlinevirtual

Property: integer value of expression node.

Returns the integer value of a node for which isKnown returns true. The high-order bits, those beyond the number of significant bits returned by the nBits propert, are guaranteed to be zero.

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

Definition at line 781 of file BinarySymbolicExpr.h.

virtual VisitAction Rose::BinaryAnalysis::SymbolicExpr::Interior::depthFirstTraversal ( Visitor )
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::Interior::nNodes ( )
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 = Interior::create(32, OP_ADD, expr, expr)

When an overflow occurs the result is meaningless.

See also
nNodesUnique

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

Definition at line 783 of file BinarySymbolicExpr.h.

size_t Rose::BinaryAnalysis::SymbolicExpr::Interior::nChildren ( )
inline

Returns the number of children.

Definition at line 786 of file BinarySymbolicExpr.h.

Ptr Rose::BinaryAnalysis::SymbolicExpr::Interior::child ( size_t  idx)
inline

Returns the specified child.

Definition at line 794 of file BinarySymbolicExpr.h.

const Nodes& Rose::BinaryAnalysis::SymbolicExpr::Interior::children ( )
inline

Property: Children.

The children are the operands for an operator expression.

Definition at line 799 of file BinarySymbolicExpr.h.

Operator Rose::BinaryAnalysis::SymbolicExpr::Interior::getOperator ( )
inline

Returns the operator.

Definition at line 807 of file BinarySymbolicExpr.h.

Ptr Rose::BinaryAnalysis::SymbolicExpr::Interior::simplifyTop ( )

Simplifies the specified interior node.

Returns a new node if necessary, otherwise returns this.

Ptr Rose::BinaryAnalysis::SymbolicExpr::Interior::foldConstants ( const Simplifier )

Perform constant folding.

This method returns either a new expression (if changes were mde) or the original expression. The simplifier is specific to the kind of operation at the node being simplified.

InteriorPtr Rose::BinaryAnalysis::SymbolicExpr::Interior::associative ( )

Simplifies non-associative operators by flattening the specified interior node with its children that are the same interior node type.

Call this only if the top node is a truly non-associative. A new node is returned only if changed. When calling both nonassociative and commutative, it's usually more appropriate to call nonassociative first.

InteriorPtr Rose::BinaryAnalysis::SymbolicExpr::Interior::commutative ( )

Simplifies commutative operators by sorting arguments.

The arguments are sorted so that all the interior nodes come before the leaf nodes. Call this only if the top node is truly commutative. A new node is returned only if changed. When calling both nonassociative and commutative, it's usually more appropriate to call nonassociative first.

Ptr Rose::BinaryAnalysis::SymbolicExpr::Interior::involutary ( )

Simplifies involutary operators.

An involutary operator is one that is its own inverse. This method should only be called if this node is an interior node whose operator has the involutary property (such as invert or negate). Returns either a new expression that is simplified, or the original expression.

Ptr Rose::BinaryAnalysis::SymbolicExpr::Interior::additiveNesting ( )

Simplifies nested shift-like operators.

Simplifies (shift AMT1 (shift AMT2 X)) to (shift (add AMT1 AMT2) X).

Ptr Rose::BinaryAnalysis::SymbolicExpr::Interior::identity ( uint64_t  ident)

Removes identity arguments.

Returns either a new expression or the original expression.

Ptr Rose::BinaryAnalysis::SymbolicExpr::Interior::unaryNoOp ( )

Replaces a binary operator with its only argument.

Returns either a new expression or the original expression.

Ptr Rose::BinaryAnalysis::SymbolicExpr::Interior::rewrite ( const Simplifier simplifier)

Simplify an interior node.

Returns a new node if this node could be simplified, otherwise returns this node. When the simplification could result in a leaf node, we return an OP_NOOP interior node instead.

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

void Rose::BinaryAnalysis::SymbolicExpr::Interior::addChild ( const Ptr child)
protected

Appends child as a new child of this node.

This must only be called from constructors.

void Rose::BinaryAnalysis::SymbolicExpr::Interior::adjustWidth ( )
protected

Adjust width based on operands.

This must only be called from constructors.

void Rose::BinaryAnalysis::SymbolicExpr::Interior::adjustBitFlags ( unsigned  extraFlags)
protected

Adjust user-defined bit flags.

This must only be called from constructors. Flags are the union of the operand flags subject to simplification rules, unioned with the specified flags.


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