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 1076 of file SymbolicExpression.h.
#include <Rose/BinaryAnalysis/SymbolicExpression.h>
Public Member Functions | |
| virtual bool | mustEqual (const Ptr &other, const SmtSolverPtr &solver=SmtSolverPtr()) override |
| Returns true if two expressions must be equal (cannot be unequal). More... | |
| virtual bool | mayEqual (const Ptr &other, const SmtSolverPtr &solver=SmtSolverPtr()) override |
| Returns true if two expressions might be equal, but not necessarily be equal. More... | |
| virtual bool | isEquivalentTo (const Ptr &other) override |
| Tests two expressions for structural equivalence. More... | |
| virtual bool | isEquivalentHelper (Node *, EquivPairs &) override |
| virtual int | compareStructure (const Ptr &other) override |
| Compare two expressions structurally for sorting. More... | |
| virtual Ptr | substitute (const Ptr &from, const Ptr &to, const SmtSolverPtr &solver=SmtSolverPtr()) override |
| Substitute one value for another. More... | |
| virtual VisitAction | depthFirstTraversal (Visitor &) const override |
| Traverse the expression. More... | |
| virtual uint64_t | nNodes () const override |
| Computes the size of an expression by counting the number of nodes. More... | |
| virtual const Nodes & | children () const override |
| Arguments. More... | |
| virtual Operator | getOperator () const override |
| Operator for interior nodes. More... | |
| virtual size_t | nChildren () const override |
| Number of arguments. More... | |
| virtual const Ptr & | child (size_t idx) const override |
| Argument. More... | |
| virtual Node * | childRaw (size_t idx) const override |
| Argument. More... | |
| virtual Sawyer::Optional< uint64_t > | toUnsigned () const override |
| The unsigned integer value of the expression. More... | |
| virtual Sawyer::Optional< int64_t > | toSigned () const override |
| The signed integer value of the expression. More... | |
| virtual bool | isConstant () const override |
| True if this expression is a constant. More... | |
| virtual bool | isVariable2 () const override |
| True if this expression is a variable. More... | |
| Ptr | simplifyTop (const SmtSolverPtr &solver=SmtSolverPtr()) |
| Simplifies the specified interior node. More... | |
| Ptr | foldConstants (const Simplifier &) |
| Perform constant folding. More... | |
| InteriorPtr | associative () |
| Simplifies non-associative operators by flattening the specified interior node with its children that are the same interior node type. More... | |
| InteriorPtr | commutative () |
| Simplifies commutative operators by sorting arguments. More... | |
| InteriorPtr | idempotent (const SmtSolverPtr &solver=SmtSolverPtr()) |
| Simplifies idempotent operators. More... | |
| Ptr | involutary () |
| Simplifies involutary operators. More... | |
| Ptr | additiveNesting (const SmtSolverPtr &solver=SmtSolverPtr()) |
| Simplifies nested shift-like operators. More... | |
| Ptr | identity (uint64_t ident, const SmtSolverPtr &solver=SmtSolverPtr()) |
| Removes identity arguments. More... | |
| Ptr | poisonNan (const SmtSolverPtr &solver=SmtSolverPtr()) |
| Returns NaN if any argument is NaN. More... | |
| Ptr | unaryNoOp () |
| Replaces a binary operator with its only argument. More... | |
| Ptr | rewrite (const Simplifier &simplifier, const SmtSolverPtr &solver=SmtSolverPtr()) |
| Simplify an interior node. More... | |
| virtual void | print (std::ostream &, Formatter &) const override |
| Print the expression to a stream. More... | |
 Public Member Functions inherited from Rose::BinaryAnalysis::SymbolicExpression::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< LeafPtr > | getVariables () const |
| Returns the variables appearing in the expression. 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) const |
| std::string | toString () const |
| Convert expression to string. More... | |
| void | assertAcyclic () const |
| Asserts that expressions are acyclic. More... | |
| std::vector< Ptr > | findCommonSubexpressions () 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... | |
| 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... | |
| InteriorPtr | isInteriorNode () const |
| Dynamic cast of this object to an interior node. More... | |
| Interior * | isInteriorNodeRaw () const |
| Dynamic cast of this object to an interior node. More... | |
| LeafPtr | isLeafNode () const |
| Dynamic cast of this object to a leaf node. More... | |
| Leaf * | isLeafNodeRaw () const |
| Dynamic cast of this object to a leaf node. 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... | |
| SharedObject & | operator= (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... | |
| Storage & | operator= (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... | |
| T | getAttribute (Id id) const |
| Get an attribute that is known to exist. More... | |
| T | attributeOrElse (Id id, const T &dflt) const |
| Return an attribute or a specified value. More... | |
| T | 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< Id > | attributeIds () const |
| Returns ID numbers for all IDs stored in this container. More... | |
Static Public Member Functions | |
| static Ptr | instance (Operator op, const Ptr &a, const SmtSolverPtr &solver=SmtSolverPtr(), const std::string &comment="", unsigned flags=0) |
| Create a new expression node. | |
| static Ptr | instance (const Type &type, Operator op, const Ptr &a, const SmtSolverPtr &solver=SmtSolverPtr(), const std::string &comment="", unsigned flags=0) |
| Create a new expression node. | |
| static Ptr | instance (Operator op, const Ptr &a, const Ptr &b, const SmtSolverPtr &solver=SmtSolverPtr(), const std::string &comment="", unsigned flags=0) |
| Create a new expression node. | |
| static Ptr | instance (const Type &type, Operator op, const Ptr &a, const Ptr &b, const SmtSolverPtr &solver=SmtSolverPtr(), const std::string &comment="", unsigned flags=0) |
| Create a new expression node. | |
| static Ptr | instance (Operator op, const Ptr &a, const Ptr &b, const Ptr &c, const SmtSolverPtr &solver=SmtSolverPtr(), const std::string &comment="", unsigned flags=0) |
| Create a new expression node. | |
| static Ptr | instance (const Type &type, Operator op, const Ptr &a, const Ptr &b, const Ptr &c, const SmtSolverPtr &solver=SmtSolverPtr(), const std::string &comment="", unsigned flags=0) |
| Create a new expression node. | |
| static Ptr | instance (Operator op, const Nodes &arguments, const SmtSolverPtr &solver=SmtSolverPtr(), const std::string &comment="", unsigned flags=0) |
| Create a new expression node. | |
| static Ptr | instance (const Type &type, Operator op, const Nodes &arguments, const SmtSolverPtr &solver=SmtSolverPtr(), const std::string &comment="", unsigned flags=0) |
| Create a new expression node. | |
| Static Public Member Functions inherited from Sawyer::SmallObject | |
| static SynchronizedPoolAllocator & | poolAllocator () |
| 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 | adjustWidth (const Type &) |
| Adjust width based on operands. More... | |
| void | adjustBitFlags (unsigned extraFlags) |
| Adjust user-defined bit flags. More... | |
| 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 |
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<> | |
| typedef SynchronizationTraits< Sawyer::SingleThreadedTag > | Sync |
| Static Public Attributes inherited from Rose::BinaryAnalysis::SymbolicExpression::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 Attributes inherited from Rose::BinaryAnalysis::SymbolicExpression::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
|
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.
|
overridevirtual |
Returns true if two expressions might be equal, but not necessarily be equal.
Implements Rose::BinaryAnalysis::SymbolicExpression::Node.
|
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.
|
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.
|
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.
|
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.
|
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:
When an overflow occurs the result is meaningless.
- See also
- nNodesUnique
Implements Rose::BinaryAnalysis::SymbolicExpression::Node.
Definition at line 1142 of file SymbolicExpression.h.
|
inlineoverridevirtual |
Arguments.
Returns the arguments of an operation for an interior node, or an empty list for a leaf node.
Implements Rose::BinaryAnalysis::SymbolicExpression::Node.
Definition at line 1143 of file SymbolicExpression.h.
Referenced by Rose::BinaryAnalysis::SymbolicExpression::substitute().
|
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 1144 of file SymbolicExpression.h.
Referenced by Rose::BinaryAnalysis::SymbolicExpression::substitute().
|
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 1145 of file SymbolicExpression.h.
Referenced by Rose::BinaryAnalysis::SymbolicExpression::substitute().
|
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.
|
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.
|
inlineoverridevirtual |
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.
Definition at line 1148 of file SymbolicExpression.h.
|
inlineoverridevirtual |
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.
Definition at line 1149 of file SymbolicExpression.h.
|
inlineoverridevirtual |
True if this expression is a constant.
Implements Rose::BinaryAnalysis::SymbolicExpression::Node.
Definition at line 1150 of file SymbolicExpression.h.
|
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 1151 of file SymbolicExpression.h.
| Ptr Rose::BinaryAnalysis::SymbolicExpression::Interior::simplifyTop | ( | const SmtSolverPtr & | solver = SmtSolverPtr() | ) |
Simplifies the specified interior node.
Returns a new node if necessary, otherwise returns this. The SMT solver is optional and my be the null pointer.
| Ptr Rose::BinaryAnalysis::SymbolicExpression::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::SymbolicExpression::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::SymbolicExpression::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.
| InteriorPtr Rose::BinaryAnalysis::SymbolicExpression::Interior::idempotent | ( | const SmtSolverPtr & | solver = SmtSolverPtr() | ) |
Simplifies idempotent operators.
An idempotent operator I is one such that X I X = X. For operators that have more than two operands, only those repeated neighboring operands are reduced to a single operand. Therefore, if the operator is commutative, then do the commutative simplification before the idempotent simplification. Returns either a new, simplified expression or the original unmodified expression.
| Ptr Rose::BinaryAnalysis::SymbolicExpression::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::SymbolicExpression::Interior::additiveNesting | ( | const SmtSolverPtr & | solver = SmtSolverPtr() | ) |
Simplifies nested shift-like operators.
Simplifies (shift AMT1 (shift AMT2 X)) to (shift (add AMT1 AMT2) X). The SMT solver may be null.
| Ptr Rose::BinaryAnalysis::SymbolicExpression::Interior::identity | ( | uint64_t | ident, |
| const SmtSolverPtr & | solver = SmtSolverPtr() |
||
| ) |
Removes identity arguments.
Returns either a new expression or the original expression. The solver may be a null pointer.
| Ptr Rose::BinaryAnalysis::SymbolicExpression::Interior::poisonNan | ( | const SmtSolverPtr & | solver = SmtSolverPtr() | ) |
Returns NaN if any argument is NaN.
If any argument is NaN then a new NaN constant expression is returned, otherwise the original expression is returned. The solver may be a null pointer.
| Ptr Rose::BinaryAnalysis::SymbolicExpression::Interior::unaryNoOp | ( | ) |
Replaces a binary operator with its only argument.
Returns either a new expression or the original expression.
| Ptr Rose::BinaryAnalysis::SymbolicExpression::Interior::rewrite | ( | const Simplifier & | simplifier, |
| const SmtSolverPtr & | solver = SmtSolverPtr() |
||
| ) |
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. The SMT solver is optional and may be the null pointer.
|
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.
|
protected |
Appends child as a new child of this node.
This must only be called from constructors.
|
protected |
Adjust width based on operands.
This must only be called from constructors. The type is needed for certain operations such as convert.
|
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:
