ROSE  0.9.9.139
BinarySymbolicExpr.h
1 #ifndef ROSE_BinaryAnalysis_SymbolicExpr_H
2 #define ROSE_BinaryAnalysis_SymbolicExpr_H
3 
4 #ifndef __STDC_FORMAT_MACROS
5 #define __STDC_FORMAT_MACROS
6 #endif
7 
8 #include "Map.h"
9 
10 #include <boost/any.hpp>
11 #include <boost/serialization/access.hpp>
12 #include <boost/serialization/base_object.hpp>
13 #include <boost/serialization/export.hpp>
14 #include <boost/serialization/split_member.hpp>
15 #include <boost/serialization/string.hpp>
16 #include <boost/serialization/vector.hpp>
17 #include <cassert>
18 #include <inttypes.h>
19 #include <Sawyer/Attribute.h>
20 #include <Sawyer/BitVector.h>
21 #include <Sawyer/Set.h>
22 #include <Sawyer/SharedPointer.h>
23 #include <Sawyer/SmallObject.h>
24 #include <set>
25 
26 namespace Rose {
27 namespace BinaryAnalysis {
28 
29 class SmtSolver;
30 
36 namespace SymbolicExpr {
37 
39 // Basic Types
41 
43 class Exception: public std::runtime_error {
44 public:
45  explicit Exception(const std::string &mesg): std::runtime_error(mesg) {}
46 };
47 
53 enum Operator {
97 };
98 
99 std::string toStr(Operator);
100 
101 class Node;
102 class Interior;
103 class Leaf;
104 
107 
110 
113 
114 typedef std::vector<Ptr> Nodes;
116 
118 typedef uint64_t Hash;
119 
121 struct Formatter {
126  };
127  Formatter()
129  max_depth(0), cur_depth(0), show_width(true), show_flags(true) {}
131  bool do_rename;
132  bool add_renames;
134  size_t max_depth;
135  size_t cur_depth;
136  RenameMap renames;
137  bool show_width;
138  bool show_flags;
139 };
140 
146 };
147 
152 extern const uint64_t MAX_NNODES; // defined in .C so we don't pollute user namespace with limit macros
153 
158 class Visitor {
159 public:
160  virtual ~Visitor() {}
161  virtual VisitAction preVisit(const Ptr&) = 0;
162  virtual VisitAction postVisit(const Ptr&) = 0;
163 };
164 
165 
166 
168 // Base Node Type
170 
208 class Node
209  : public Sawyer::SharedObject,
210  public Sawyer::SharedFromThis<Node>,
211  public Sawyer::SmallObject,
212  public Sawyer::Attribute::Storage<> { // Attributes are not significant for hashing or arithmetic
213 protected:
214  size_t nBits_;
215  size_t domainWidth_;
216  unsigned flags_;
217  std::string comment_;
218  Hash hashval_;
219  boost::any userData_;
221 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
222 private:
223  friend class boost::serialization::access;
224 
225  template<class S>
226  void serialize(S &s, const unsigned version) {
227  s & BOOST_SERIALIZATION_NVP(nBits_);
228  s & BOOST_SERIALIZATION_NVP(domainWidth_);
229  s & BOOST_SERIALIZATION_NVP(flags_);
230  s & BOOST_SERIALIZATION_NVP(comment_);
231  s & BOOST_SERIALIZATION_NVP(hashval_);
232  // s & userData_;
233  }
234 #endif
235 
236 public:
237  // Bit flags
238 
240  static const unsigned RESERVED_FLAGS = 0x0000ffff;
241 
243  static const unsigned INDETERMINATE = 0x00000001;
244 
249  static const unsigned UNSPECIFIED = 0x00000002;
250 
253  static const unsigned BOTTOM = 0x00000004;
254 
255 protected:
256  Node()
257  : nBits_(0), domainWidth_(0), flags_(0), hashval_(0) {}
258  explicit Node(const std::string &comment, unsigned flags=0)
259  : nBits_(0), domainWidth_(0), flags_(flags), comment_(comment), hashval_(0) {}
260 
261 public:
267  virtual bool mustEqual(const Ptr &other, SmtSolver*) = 0;
268 
269  // [Robb P. Matzke 2015-10-08]: deprecated
270  bool must_equal(const Ptr& other, SmtSolver *solver) ROSE_DEPRECATED("use mustEqual instead") {
271  return mustEqual(other, solver);
272  }
273 
275  virtual bool mayEqual(const Ptr &other, SmtSolver*) = 0;
276 
277  // [Robb P. Matzke 2015-10-08]: deprecated
278  bool may_equal(const Ptr &other, SmtSolver *solver) ROSE_DEPRECATED("use mayEqual instead") {
279  return mayEqual(other, solver);
280  }
281 
287  virtual bool isEquivalentTo(const Ptr &other) = 0;
288 
289  // [Robb P. Matzke 2015-10-08]: deprecated
290  bool equivalent_to(const Ptr& other) ROSE_DEPRECATED("use isEquivalentTo instead") {
291  return isEquivalentTo(other);
292  }
293 
299  virtual int compareStructure(const Ptr &other) = 0;
300 
301  // [Robb P. Matzke 2015-10-08]: deprecated
302  int structural_compare(const Ptr& other) ROSE_DEPRECATED("use compareStructure instead") {
303  return compareStructure(other);
304  }
305 
311  virtual Ptr substitute(const Ptr &from, const Ptr &to) = 0;
312 
316  virtual bool isNumber() = 0;
317 
318  // [Robb P. Matzke 2015-10-08]: deprecated
319  bool is_known() ROSE_DEPRECATED("use isNumber instead") {
320  return isNumber();
321  }
322 
327  virtual uint64_t toInt() = 0;
328 
329  // [Robb P. Matzke 2015-10-08]: deprecated
330  uint64_t get_value() ROSE_DEPRECATED("use toInt instead") {
331  return toInt();
332  }
333 
342  const std::string& comment() { return comment_; }
343  void comment(const std::string &s) { comment_ = s; }
346  // [Robb P. Matzke 2015-10-08]: deprecated
347  const std::string& get_comment() ROSE_DEPRECATED("use 'comment' property instead") {
348  return comment();
349  }
350 
351  // [Robb P. Matzke 2015-10-08]: deprecated
352  void set_comment(const std::string &s) ROSE_DEPRECATED("use 'comment' property instead") {
353  comment(s);
354  }
355 
363  void userData(boost::any &data) {
364  userData_ = data;
365  }
366  const boost::any& userData() {
367  return userData_;
368  }
374  size_t nBits() { return nBits_; }
375 
376  // [Robb P. Matzke 2015-10-08]: deprecated
377  size_t get_nbits() ROSE_DEPRECATED("use 'nBits' property instead") {
378  return nBits();
379  }
380 
385  unsigned flags() { return flags_; }
386 
387  unsigned get_flags() ROSE_DEPRECATED("use 'flags' property instead") {
388  return flags();
389  }
390 
394  Ptr newFlags(unsigned flags);
395 
399  size_t domainWidth() { return domainWidth_; }
400 
404  bool isScalar() { return 0 == domainWidth_; }
405 
411 
412  // [Robb P. Matzke 2015-10-08]: deprecated
413  VisitAction depth_first_traversal(Visitor &v) ROSE_DEPRECATED("use depthFirstTraversal instead") {
414  return depthFirstTraversal(v);
415  }
416 
432  virtual uint64_t nNodes() = 0;
433 
434  // [Robb P. Matzke 2015-10-08]: deprecated
435  uint64_t nnodes() ROSE_DEPRECATED("use nNodes() instead") {
436  return nNodes();
437  }
438 
440  uint64_t nNodesUnique();
441 
442  // [Robb P. Matzke 2015-10-08]: deprecated
443  uint64_t nnodesUnique() ROSE_DEPRECATED("use nNodesUnique instead") {
444  return nNodesUnique();
445  }
446 
448  std::set<LeafPtr> getVariables();
449 
450  // [Robb P. Matzke 2015-10-08]: deprecated
451  std::set<LeafPtr> get_variables() ROSE_DEPRECATED("use getVariables instead") {
452  return getVariables();
453  }
454 
458  InteriorPtr isInteriorNode() {
459  return sharedFromThis().dynamicCast<Interior>();
460  }
461 
462  // [Robb P. Matzke 2015-10-09]: deprecated
463  InteriorPtr isInternalNode() ROSE_DEPRECATED("use isInteriorNode instead") {
464  return isInteriorNode();
465  }
466 
470  LeafPtr isLeafNode() {
471  return sharedFromThis().dynamicCast<Leaf>();
472  }
473 
477  bool isHashed() { return hashval_ != 0; }
478 
479  // [Robb P. Matzke 2015-10-08]: deprecated
480  bool is_hashed() ROSE_DEPRECATED("use isHashed instead") {
481  return isHashed();
482  }
483 
486  Hash hash();
487 
488  // used internally to set the hash value
489  void hash(Hash);
490 
493  private:
494  Ptr node;
495  Formatter &formatter;
496  public:
497  WithFormatter(const Ptr &node, Formatter &formatter): node(node), formatter(formatter) {}
498  void print(std::ostream &stream) const { node->print(stream, formatter); }
499  };
500 
519  // [Robb P. Matzke 2015-10-08]: deprecated
520  WithFormatter with_format(Formatter &fmt) ROSE_DEPRECATED("use withFormat instead") {
521  return withFormat(fmt);
522  }
523 
527  virtual void print(std::ostream&, Formatter&) = 0;
528  void print(std::ostream &o) { Formatter fmt; print(o, fmt); }
532  void assertAcyclic();
533 
534  // [Robb P. Matzke 2015-10-08]: deprecated
535  void assert_acyclic() {
536  return assertAcyclic();
537  }
538 
544  std::vector<Ptr> findCommonSubexpressions();
545 
546 protected:
547  void printFlags(std::ostream &o, unsigned flags, char &bracket);
548 };
549 
551 class Simplifier {
552 public:
553  virtual ~Simplifier() {}
554 
558  virtual Ptr fold(Nodes::const_iterator begin, Nodes::const_iterator end) const {
559  return Ptr();
560  }
561 
564  virtual Ptr rewrite(Interior*) const {
565  return Ptr();
566  }
567 };
568 
569 
572 public:
573  bool operator()(const Ptr &a, const Ptr &b);
574 };
575 
578 
579 
581 // Simplification
583 
585  virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE;
586  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
587 };
589  virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE;
590  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
591 };
593  virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE;
594  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
595 };
597  virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE;
598  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
599 };
601  virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE;
602 };
604  virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE;
605 };
607  virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE;
608  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
609 };
611  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
612 };
614  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
615 };
617  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
618 };
620  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
621 };
623  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
624 };
626  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
627 };
629  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
630 };
632  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
633 };
635  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
636 };
638  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
639 };
641  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
642 };
644  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
645 };
647  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
648 };
650  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
651 };
653  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
654 };
656  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
657 };
659  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
660 };
662  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
663 };
665  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
666 };
668  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
669 };
671  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
672 };
674  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
675 };
677  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
678 };
680  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
681 };
683  bool newbits;
684  ShiftSimplifier(bool newbits): newbits(newbits) {}
685  Ptr combine_strengths(Ptr strength1, Ptr strength2, size_t value_width) const;
686 };
688  ShlSimplifier(bool newbits): ShiftSimplifier(newbits) {}
689  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
690 };
692  ShrSimplifier(bool newbits): ShiftSimplifier(newbits) {}
693  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
694 };
696  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
697 };
699  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
700 };
702  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
703 };
704 
705 
706 
708 // Interior Nodes
710 
715 class Interior: public Node {
716 private:
717  Operator op_;
718  Nodes children_;
719  uint64_t nnodes_; // total number of nodes; self + children's nnodes
720 
721  // Constructors should not be called directly. Use the create() class method instead. This is to help prevent
722  // accidently using pointers to these objects -- all access should be through shared-ownership pointers.
723  Interior(): op_(OP_ADD), nnodes_(1) {} // needed for serialization
724  Interior(size_t nbits, Operator op, const Ptr &a, const std::string &comment="", unsigned flags=0);
725  Interior(size_t nbits, Operator op, const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
726  Interior(size_t nbits, Operator op, const Ptr &a, const Ptr &b, const Ptr &c, const std::string &comment="",
727  unsigned flags=0);
728  Interior(size_t nbits, Operator op, const Nodes &children, const std::string &comment="", unsigned flags=0);
729 
730 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
731 private:
732  friend class boost::serialization::access;
733 
734  template<class S>
735  void serialize(S &s, const unsigned version) {
736  s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Node);
737  s & BOOST_SERIALIZATION_NVP(op_);
738  s & BOOST_SERIALIZATION_NVP(children_);
739  s & BOOST_SERIALIZATION_NVP(nnodes_);
740  }
741 #endif
742 
743 public:
751  static Ptr create(size_t nbits, Operator op, const Ptr &a, const std::string &comment="", unsigned flags=0) {
752  InteriorPtr retval(new Interior(nbits, op, a, comment, flags));
753  return retval->simplifyTop();
754  }
755  static Ptr create(size_t nbits, Operator op, const Ptr &a, const Ptr &b,
756  const std::string &comment="", unsigned flags=0) {
757  InteriorPtr retval(new Interior(nbits, op, a, b, comment, flags));
758  return retval->simplifyTop();
759  }
760  static Ptr create(size_t nbits, Operator op, const Ptr &a, const Ptr &b, const Ptr &c,
761  const std::string &comment="", unsigned flags=0) {
762  InteriorPtr retval(new Interior(nbits, op, a, b, c, comment, flags));
763  return retval->simplifyTop();
764  }
765  static Ptr create(size_t nbits, Operator op, const Nodes &children, const std::string &comment="",
766  unsigned flags=0) {
767  InteriorPtr retval(new Interior(nbits, op, children, comment, flags));
768  return retval->simplifyTop();
769  }
772  /* see superclass, where these are pure virtual */
773  virtual bool mustEqual(const Ptr &other, SmtSolver*) ROSE_OVERRIDE;
774  virtual bool mayEqual(const Ptr &other, SmtSolver*) ROSE_OVERRIDE;
775  virtual bool isEquivalentTo(const Ptr &other) ROSE_OVERRIDE;
776  virtual int compareStructure(const Ptr& other) ROSE_OVERRIDE;
777  virtual Ptr substitute(const Ptr &from, const Ptr &to) ROSE_OVERRIDE;
778  virtual bool isNumber() ROSE_OVERRIDE {
779  return false; /*if it's known, then it would have been folded to a leaf*/
780  }
781  virtual uint64_t toInt() ROSE_OVERRIDE { ASSERT_forbid2(true, "not a number"); return 0;}
782  virtual VisitAction depthFirstTraversal(Visitor&) ROSE_OVERRIDE;
783  virtual uint64_t nNodes() ROSE_OVERRIDE { return nnodes_; }
784 
786  size_t nChildren() { return children_.size(); }
787 
788  // [Robb P. Matzke 2015-10-09]: deprecated
789  size_t nchildren() ROSE_DEPRECATED("use nChildren instead") {
790  return nChildren();
791  }
792 
794  Ptr child(size_t idx) { ASSERT_require(idx<children_.size()); return children_[idx]; }
795 
799  const Nodes& children() { return children_; }
800 
801  // [Robb P. Matzke 2015-10-09]: deprecated
802  Nodes get_children() ROSE_DEPRECATED("use 'children' property instead") {
803  return children();
804  }
805 
807  Operator getOperator() { return op_; }
808 
809  // [Robb P. Matzke 2015-10-09]: deprecated
810  Operator get_operator() ROSE_DEPRECATED("use getOperator instead") {
811  return getOperator();
812  }
813 
815  Ptr simplifyTop();
816 
819  Ptr foldConstants(const Simplifier&);
820 
821  // [Robb P. Matzke 2015-10-09]: deprecated
822  Ptr constant_folding(const Simplifier &simplifier) ROSE_DEPRECATED("use foldConstants instead") {
823  return foldConstants(simplifier);
824  }
825 
830  InteriorPtr associative();
831 
832  // [Robb P. Matzke 2015-10-09]: deprecated
833  InteriorPtr nonassociative() ROSE_DEPRECATED("use 'associative' instead") {
834  return associative();
835  }
836 
841  InteriorPtr commutative();
842 
846  Ptr involutary();
847 
849  Ptr additiveNesting();
850 
851  Ptr additive_nesting() ROSE_DEPRECATED("use additiveNesting instead") {
852  return additiveNesting();
853  }
854 
856  Ptr identity(uint64_t ident);
857 
859  Ptr unaryNoOp();
860 
863  Ptr rewrite(const Simplifier &simplifier);
864 
865  virtual void print(std::ostream&, Formatter&) ROSE_OVERRIDE;
866 
867 protected:
869  void addChild(const Ptr &child);
870 
871  // [Robb P. Matzke 2015-10-09]: deprecated
872  void add_child(const Ptr &child) ROSE_DEPRECATED("use addChild instead") {
873  addChild(child);
874  }
875 
877  void adjustWidth();
878 
881  void adjustBitFlags(unsigned extraFlags);
882 };
883 
884 
886 // Leaf Nodes
888 
892 class Leaf: public Node {
893 private:
894  enum LeafType { CONSTANT, BITVECTOR, MEMORY };
895  LeafType leafType_;
897  uint64_t name_;
899 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
900 private:
901  friend class boost::serialization::access;
902 
903  template<class S>
904  void save(S &s, const unsigned version) const {
905  s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Node);
906  s & BOOST_SERIALIZATION_NVP(leafType_);
907  s & BOOST_SERIALIZATION_NVP(bits_);
908  s & BOOST_SERIALIZATION_NVP(name_);
909  }
910 
911  template<class S>
912  void load(S &s, const unsigned version) {
913  s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Node);
914  s & BOOST_SERIALIZATION_NVP(leafType_);
915  s & BOOST_SERIALIZATION_NVP(bits_);
916  s & BOOST_SERIALIZATION_NVP(name_);
917  nextNameCounter(name_);
918  }
919 
920  BOOST_SERIALIZATION_SPLIT_MEMBER();
921 #endif
922 
923  // Private to help prevent creating pointers to leaf nodes. See create_* methods instead.
924 private:
925  Leaf()
926  : Node(""), leafType_(CONSTANT), name_(0) {}
927  explicit Leaf(const std::string &comment, unsigned flags=0)
928  : Node(comment, flags), leafType_(CONSTANT), name_(0) {}
929 
930 public:
932  static LeafPtr createVariable(size_t nbits, const std::string &comment="", unsigned flags=0);
933 
934  // [Robb P. Matzke 2015-10-09]: deprecated
935  static LeafPtr create_variable(size_t nbits, std::string comment="", unsigned flags=0)
936  ROSE_DEPRECATED("use createVariable instead") {
937  return createVariable(nbits, comment, flags);
938  }
939 
943  static LeafPtr createExistingVariable(size_t nbits, uint64_t id, const std::string &comment="", unsigned flags=0);
944 
945  // [Robb P. Matzke 2015-10-09]: deprecated
946  static LeafPtr create_existing_variable(size_t nbits, uint64_t id, const std::string &comment="", unsigned flags=0)
947  ROSE_DEPRECATED("use createExistingVariable instead") {
948  return createExistingVariable(nbits, id, comment, flags);
949  }
950 
953  static LeafPtr createInteger(size_t nbits, uint64_t n, const std::string &comment="", unsigned flags=0);
954 
955  // [Robb P. Matzke 2015-10-09]: deprecated
956  static LeafPtr create_integer(size_t nbits, uint64_t n, std::string comment="", unsigned flags=0)
957  ROSE_DEPRECATED("use createInteger instead") {
958  return createInteger(nbits, n, comment, flags);
959  }
960 
962  static LeafPtr createConstant(const Sawyer::Container::BitVector &bits, const std::string &comment="", unsigned flags=0);
963 
964  // [Robb P. Matzke 2015-10-09]: deprecated
965  static LeafPtr create_constant(const Sawyer::Container::BitVector &bits, std::string comment="", unsigned flags=0)
966  ROSE_DEPRECATED("use createConstant instead") {
967  return createConstant(bits, comment, flags);
968  }
969 
971  static LeafPtr createBoolean(bool b, const std::string &comment="", unsigned flags=0) {
972  return createInteger(1, (uint64_t)(b?1:0), comment, flags);
973  }
974 
975  // [Robb P. Matzke 2015-10-09]: deprecated
976  static LeafPtr create_boolean(bool b, std::string comment="", unsigned flags=0)
977  ROSE_DEPRECATED("use createBoolean instead") {
978  return createBoolean(b, comment, flags);
979  }
980 
982  static LeafPtr createMemory(size_t addressWidth, size_t valueWidth, const std::string &comment="", unsigned flags=0);
983 
987  static LeafPtr createExistingMemory(size_t addressWidth, size_t valueWidth, uint64_t id, const std::string &comment="",
988  unsigned flags=0);
989 
990  // [Robb P. Matzke 2015-10-09]: deprecated
991  static LeafPtr create_memory(size_t addressWidth, size_t valueWidth, std::string comment="", unsigned flags=0)
992  ROSE_DEPRECATED("use createMemory instead") {
993  return createMemory(addressWidth, valueWidth, comment, flags);
994  }
995 
996  // from base class
997  virtual bool isNumber() ROSE_OVERRIDE;
998  virtual uint64_t toInt() ROSE_OVERRIDE;
999  virtual bool mustEqual(const Ptr &other, SmtSolver*) ROSE_OVERRIDE;
1000  virtual bool mayEqual(const Ptr &other, SmtSolver*) ROSE_OVERRIDE;
1001  virtual bool isEquivalentTo(const Ptr &other) ROSE_OVERRIDE;
1002  virtual int compareStructure(const Ptr& other) ROSE_OVERRIDE;
1003  virtual Ptr substitute(const Ptr &from, const Ptr &to) ROSE_OVERRIDE;
1004  virtual VisitAction depthFirstTraversal(Visitor&) ROSE_OVERRIDE;
1005  virtual uint64_t nNodes() ROSE_OVERRIDE { return 1; }
1006 
1009 
1010  // [Robb P. Matzke 2015-10-09]: deprecated
1011  const Sawyer::Container::BitVector& get_bits() ROSE_DEPRECATED("use 'bits' property instead") {
1012  return bits();
1013  }
1014 
1016  virtual bool isVariable();
1017 
1018  // [Robb P. Matzke 2015-10-09]: deprecated
1019  bool is_variable() ROSE_DEPRECATED("use isVariable instead") {
1020  return isVariable();
1021  }
1022 
1024  virtual bool isMemory();
1025 
1026  // [Robb P. Matzke 2015-10-09]: deprecated
1027  bool is_memory() ROSE_DEPRECATED("use isMemory instead") {
1028  return isMemory();
1029  }
1030 
1035  uint64_t nameId();
1036 
1037  // [Robb P. Matzke 2015-10-09]: deprecated
1038  uint64_t get_name() ROSE_DEPRECATED("use nameId instead") {
1039  return nameId();
1040  }
1041 
1046  std::string toString();
1047 
1048  // documented in super class
1049  virtual void print(std::ostream&, Formatter&) ROSE_OVERRIDE;
1050 
1052  void printAsSigned(std::ostream&, Formatter&, bool asSigned=true);
1053 
1054  // [Robb P. Matzke 2015-10-09]: deprecated
1055  void print_as_signed(std::ostream &stream, Formatter &formatter, bool as_signed=true)
1056  ROSE_DEPRECATED("use printAsSigned instead") {
1057  printAsSigned(stream, formatter, as_signed);
1058  }
1059 
1061  void printAsUnsigned(std::ostream &o, Formatter &f) {
1062  printAsSigned(o, f, false);
1063  }
1064 
1065  // [Robb P. Matzke 2015-10-09]: deprecated
1066  void print_as_unsigned(std::ostream &o, Formatter &f) ROSE_DEPRECATED("use printAsUnsigned instead") {
1067  printAsUnsigned(o, f);
1068  }
1069 
1070 private:
1071  // Obtain or register a name ID
1072  static uint64_t nextNameCounter(uint64_t useThis = (uint64_t)(-1));
1073 };
1074 
1076 // Factories
1078 
1084 Ptr makeVariable(size_t nbits, const std::string &comment="", unsigned flags=0);
1085 Ptr makeExistingVariable(size_t nbits, uint64_t id, const std::string &comment="", unsigned flags=0);
1086 Ptr makeInteger(size_t nbits, uint64_t n, const std::string &comment="", unsigned flags=0);
1087 Ptr makeConstant(const Sawyer::Container::BitVector&, const std::string &comment="", unsigned flags=0);
1088 Ptr makeBoolean(bool, const std::string &comment="", unsigned flags=0);
1089 Ptr makeMemory(size_t addressWidth, size_t valueWidth, const std::string &comment="", unsigned flags=0);
1090 Ptr makeExistingMemory(size_t addressWidth, size_t valueWidth, uint64_t id, const std::string &comment="", unsigned flags=0);
1099 Ptr makeAdd(const Ptr&a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1100 Ptr makeBooleanAnd(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1101 Ptr makeAsr(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0);
1102 Ptr makeAnd(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1103 Ptr makeOr(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1104 Ptr makeXor(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1105 Ptr makeConcat(const Ptr &hi, const Ptr &lo, const std::string &comment="", unsigned flags=0);
1106 Ptr makeEq(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1107 Ptr makeExtract(const Ptr &begin, const Ptr &end, const Ptr &a, const std::string &comment="", unsigned flags=0);
1108 Ptr makeInvert(const Ptr &a, const std::string &comment="", unsigned flags=0);
1109 Ptr makeIte(const Ptr &cond, const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1110 Ptr makeLssb(const Ptr &a, const std::string &comment="", unsigned flags=0);
1111 Ptr makeMssb(const Ptr &a, const std::string &comment="", unsigned flags=0);
1112 Ptr makeNe(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1113 Ptr makeNegate(const Ptr &a, const std::string &comment="", unsigned flags=0);
1114 Ptr makeBooleanOr(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1115 Ptr makeRead(const Ptr &mem, const Ptr &addr, const std::string &comment="", unsigned flags=0);
1116 Ptr makeRol(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0);
1117 Ptr makeRor(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0);
1118 Ptr makeSet(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1119 Ptr makeSet(const Ptr &a, const Ptr &b, const Ptr &c, const std::string &comment="", unsigned flags=0);
1120 Ptr makeSignedDiv(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1121 Ptr makeSignExtend(const Ptr &newSize, const Ptr &a, const std::string &comment="", unsigned flags=0);
1122 Ptr makeSignedGe(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1123 Ptr makeSignedGt(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1124 Ptr makeShl0(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0);
1125 Ptr makeShl1(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0);
1126 Ptr makeShr0(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0);
1127 Ptr makeShr1(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0);
1128 Ptr makeSignedLe(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1129 Ptr makeSignedLt(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1130 Ptr makeSignedMod(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1131 Ptr makeSignedMul(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1132 Ptr makeDiv(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1133 Ptr makeExtend(const Ptr &newSize, const Ptr &a, const std::string &comment="", unsigned flags=0);
1134 Ptr makeGe(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1135 Ptr makeGt(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1136 Ptr makeLe(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1137 Ptr makeLt(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1138 Ptr makeMod(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1139 Ptr makeMul(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1140 Ptr makeWrite(const Ptr &mem, const Ptr &addr, const Ptr &a, const std::string &comment="", unsigned flags=0);
1141 Ptr makeZerop(const Ptr &a, const std::string &comment="", unsigned flags=0);
1145 // Miscellaneous functions
1148 
1149 
1150 std::ostream& operator<<(std::ostream &o, Node&);
1151 std::ostream& operator<<(std::ostream &o, const Node::WithFormatter&);
1152 
1154 Ptr setToIte(const Ptr&, const LeafPtr &var = LeafPtr());
1155 
1160 template<typename InputIterator>
1161 uint64_t
1162 nNodes(InputIterator begin, InputIterator end) {
1163  uint64_t total = 0;
1164  for (InputIterator ii=begin; ii!=end; ++ii) {
1165  uint64_t n = (*ii)->nnodes();
1166  if (MAX_NNODES==n)
1167  return MAX_NNODES;
1168  if (total + n < total)
1169  return MAX_NNODES;
1170  total += n;
1171  }
1172  return total;
1173 }
1174 
1175 // [Robb P. Matzke 2015-10-08]: deprecated
1176 template<typename InputIterator>
1177 uint64_t
1178 nnodes(InputIterator begin, InputIterator end) ROSE_DEPRECATED("use nNodes instead");
1179 template<typename InputIterator>
1180 uint64_t
1181 nnodes(InputIterator begin, InputIterator end) {
1182  return nNodes(begin, end);
1183 }
1184 
1189 template<typename InputIterator>
1190 uint64_t
1191 nNodesUnique(InputIterator begin, InputIterator end)
1192 {
1193  struct T1: Visitor {
1194  typedef std::set<const Node*> SeenNodes;
1195 
1196  SeenNodes seen; // nodes that we've already seen, and the subtree size
1197  uint64_t nUnique; // number of unique nodes
1198 
1199  T1(): nUnique(0) {}
1200 
1201  VisitAction preVisit(const Ptr &node) {
1202  if (seen.insert(getRawPointer(node)).second) {
1203  ++nUnique;
1204  return CONTINUE; // this node has not been seen before; traverse into children
1205  } else {
1206  return TRUNCATE; // this node has been seen already; skip over the children
1207  }
1208  }
1209 
1210  VisitAction postVisit(const Ptr &node) {
1211  return CONTINUE;
1212  }
1213  } visitor;
1214 
1215  VisitAction status = CONTINUE;
1216  for (InputIterator ii=begin; ii!=end && TERMINATE!=status; ++ii)
1217  status = (*ii)->depthFirstTraversal(visitor);
1218  return visitor.nUnique;
1219 }
1220 
1221 // [Robb P. Matzke 2015-10-08]: deprecated
1222 template<typename InputIterator>
1223 uint64_t
1224 nnodesUnique(InputIterator begin, InputIterator end) ROSE_DEPRECATED("use nNodesUnique instead");
1225 template<typename InputIterator>
1226 uint64_t
1227 nnodesUnique(InputIterator begin, InputIterator end) {
1228  return nNodesUnique(begin, end);
1229 }
1230 
1237 std::vector<Ptr> findCommonSubexpressions(const std::vector<Ptr>&);
1238 
1239 template<typename InputIterator>
1240 std::vector<Ptr>
1241 findCommonSubexpressions(InputIterator begin, InputIterator end) {
1242  typedef Sawyer::Container::Map<Ptr, size_t> NodeCounts;
1243  struct T1: Visitor {
1244  NodeCounts nodeCounts;
1245  std::vector<Ptr> result;
1246 
1247  VisitAction preVisit(const Ptr &node) ROSE_OVERRIDE {
1248  size_t &nSeen = nodeCounts.insertMaybe(node, 0);
1249  if (2 == ++nSeen)
1250  result.push_back(node);
1251  return nSeen>1 ? TRUNCATE : CONTINUE;
1252  }
1253 
1254  VisitAction postVisit(const Ptr&) ROSE_OVERRIDE {
1255  return CONTINUE;
1256  }
1257  } visitor;
1258 
1259  for (InputIterator ii=begin; ii!=end; ++ii)
1260  (*ii)->depthFirstTraversal(visitor);
1261  return visitor.result;
1262 }
1265 } // namespace
1266 } // namespace
1267 } // namespace
1268 
1269 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
1270 BOOST_CLASS_EXPORT_KEY(Rose::BinaryAnalysis::SymbolicExpr::Interior);
1271 BOOST_CLASS_EXPORT_KEY(Rose::BinaryAnalysis::SymbolicExpr::Leaf);
1272 #endif
1273 
1274 #endif
Operator-specific simplification methods.
virtual int compareStructure(const Ptr &other) ROSE_OVERRIDE
Compare two expressions structurally for sorting.
bool add_renames
Add additional entries to the renames as variables are encountered?
Ptr makeSignedGt(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
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.
virtual uint64_t toInt() ROSE_OVERRIDE
Property: integer value of expression node.
ShowComments show_comments
Show node comments when printing?
Ordered set of values.
Definition: Set.h:46
Sawyer::SharedPointer< Node > Ptr
Shared-ownership pointer to an expression Node.
virtual bool isMemory()
Does the node represent memory?
std::string comment_
Optional comment.
Ptr makeGe(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual bool mayEqual(const Ptr &other, SmtSolver *) ROSE_OVERRIDE
Returns true if two expressions might be equal, but not necessarily be equal.
RenameMap renames
Map for renaming variables to use smaller integers.
virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE
Constant folding.
Ptr makeExistingVariable(size_t nbits, uint64_t id, const std::string &comment="", unsigned flags=0)
Leaf constructor.
size_t max_depth
If non-zero, then replace deep parts of expressions with "...".
uint64_t Hash
Hash of symbolic expression.
Leaf node of an expression tree for instruction semantics.
Ptr makeInteger(size_t nbits, uint64_t n, const std::string &comment="", unsigned flags=0)
Leaf constructor.
const Sawyer::Container::BitVector & bits()
Property: Bits stored for numeric values.
Operator getOperator()
Returns the operator.
virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE
Constant folding.
virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE
Constant folding.
virtual Ptr rewrite(Interior *) const
Rewrite the entire expression to something simpler.
static LeafPtr createMemory(size_t addressWidth, size_t valueWidth, const std::string &comment="", unsigned flags=0)
Construct a new memory state.
virtual bool isEquivalentTo(const Ptr &other)=0
Tests two expressions for structural equivalence.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Ptr makeRor(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE
Constant folding.
Continue the traversal as normal.
Interior node of an expression tree for instruction semantics.
boost::any userData_
Additional user-specified data.
Hash hashval_
Optional hash used as a quick way to indicate that two expressions are different. ...
virtual bool isNumber() ROSE_OVERRIDE
Returns true if the expression is a known numeric value.
uint64_t nNodesUnique(InputIterator begin, InputIterator end)
Counts the number of unique nodes.
virtual bool mayEqual(const Ptr &other, SmtSolver *) ROSE_OVERRIDE
Returns true if two expressions might be equal, but not necessarily be equal.
Ptr makeShl0(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual bool isVariable()
Is the node a bitvector variable?
Ptr makeBooleanAnd(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual bool mustEqual(const Ptr &other, SmtSolver *) ROSE_OVERRIDE
Returns true if two expressions must be equal (cannot be unequal).
static LeafPtr createVariable(size_t nbits, const std::string &comment="", unsigned flags=0)
Construct a new free variable with a specified number of significant bits.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
void adjustWidth()
Adjust width based on operands.
Ptr makeMul(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
virtual bool isEquivalentTo(const Ptr &other) ROSE_OVERRIDE
Tests two expressions for structural equivalence.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
bool isScalar()
Check whether expression is scalar.
static LeafPtr createBoolean(bool b, const std::string &comment="", unsigned flags=0)
Create a new Boolean, a single-bit integer.
InteriorPtr isInteriorNode()
Dynamic cast of this object to an interior node.
Ptr makeVariable(size_t nbits, const std::string &comment="", unsigned flags=0)
Leaf constructor.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Shift left, introducing zeros at lsb.
virtual uint64_t nNodes() ROSE_OVERRIDE
Computes the size of an expression by counting the number of nodes.
virtual bool mustEqual(const Ptr &other, SmtSolver *)=0
Returns true if two expressions must be equal (cannot be unequal).
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.
VisitAction
Return type for visitors.
virtual VisitAction depthFirstTraversal(Visitor &)=0
Traverse the expression.
void userData(boost::any &data)
Property: User-defined data.
virtual bool mayEqual(const Ptr &other, SmtSolver *)=0
Returns true if two expressions might be equal, but not necessarily be equal.
bool do_rename
Use the renames map to rename variables to shorter names?
Ptr makeRol(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Most significant set bit or zero.
static LeafPtr createExistingVariable(size_t nbits, uint64_t id, const std::string &comment="", unsigned flags=0)
Construct another reference to an existing variable.
Ptr makeEq(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Ptr makeLssb(const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
STL namespace.
Sawyer::Container::Set< Ptr, ExpressionLessp > ExpressionSet
Set of expressions.
static const unsigned UNSPECIFIED
Value is somehow unspecified.
Ptr makeShr0(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual Ptr substitute(const Ptr &from, const Ptr &to)=0
Substitute one value for another.
virtual Ptr substitute(const Ptr &from, const Ptr &to) ROSE_OVERRIDE
Substitute one value for another.
Small object support.
Definition: SmallObject.h:19
Ptr makeBooleanOr(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Shift right, introducing ones at msb.
size_t domainWidth()
Property: Width for memory expressions.
virtual uint64_t toInt()=0
Property: integer value of expression node.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Ptr additiveNesting()
Simplifies nested shift-like operators.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Ptr makeConstant(const Sawyer::Container::BitVector &, const std::string &comment="", unsigned flags=0)
Leaf constructor.
Ptr involutary()
Simplifies involutary operators.
virtual int compareStructure(const Ptr &other) ROSE_OVERRIDE
Compare two expressions structurally for sorting.
Main namespace for the ROSE library.
Controls formatting of expression trees when printing.
static Ptr create(size_t nbits, Operator op, const Nodes &children, const std::string &comment="", unsigned flags=0)
Create a new expression node.
Shift right, introducing zeros at msb.
Ptr makeInvert(const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual Ptr fold(Nodes::const_iterator begin, Nodes::const_iterator end) const
Constant folding.
size_t nBits_
Number of significant bits.
Ptr makeSet(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
Ptr makeDiv(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
void adjustBitFlags(unsigned extraFlags)
Adjust user-defined bit flags.
void printAsSigned(std::ostream &, Formatter &, bool asSigned=true)
Prints an integer interpreted as a signed value.
static LeafPtr createInteger(size_t nbits, uint64_t n, const std::string &comment="", unsigned flags=0)
Construct a new integer with the specified number of significant bits.
virtual void print(std::ostream &, Formatter &) ROSE_OVERRIDE
Print the expression to a stream.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Hash hash()
Returns (and caches) the hash value for this node.
Least significant set bit or zero.
std::string toString()
Returns a string for the leaf.
Ptr makeZerop(const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
Ptr makeSignedGe(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual uint64_t toInt() ROSE_OVERRIDE
Property: integer value of expression node.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
virtual bool mustEqual(const Ptr &other, SmtSolver *) ROSE_OVERRIDE
Returns true if two expressions must be equal (cannot be unequal).
Shift left, introducing ones at lsb.
Unsigned greater-than-or-equal.
SharedPointer< Node > sharedFromThis()
Create a shared pointer from this.
size_t domainWidth_
Width of domain for unary functions.
Like CMT_AFTER, but show comments instead of variable names.
Ptr makeXor(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual VisitAction depthFirstTraversal(Visitor &) ROSE_OVERRIDE
Traverse the expression.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
const boost::any & userData()
Property: User-defined data.
InteriorPtr associative()
Simplifies non-associative operators by flattening the specified interior node with its children that...
uint64_t nNodesUnique()
Number of unique nodes in expression.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
static const unsigned INDETERMINATE
Value is somehow indeterminate.
static const unsigned BOTTOM
Value represents bottom in dataflow analysis.
Ptr simplifyTop()
Simplifies the specified interior node.
void print(std::ostream &o)
Print the expression to a stream.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Ptr makeShl1(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
std::vector< Ptr > findCommonSubexpressions()
Find common subexpressions.
Ptr makeOr(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Ptr makeSignedLe(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
unsigned flags()
Property: User-defined bit flags.
Ptr makeGt(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
bool show_width
Show width in bits inside square brackets.
virtual void print(std::ostream &, Formatter &)=0
Print the expression to a stream.
Creates SharedPointer from this.
std::set< LeafPtr > getVariables()
Returns the variables appearing in the expression.
Ptr makeMod(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Ptr makeExistingMemory(size_t addressWidth, size_t valueWidth, uint64_t id, const std::string &comment="", unsigned flags=0)
Leaf constructor.
uint64_t nNodes(InputIterator begin, InputIterator end)
Counts the number of nodes.
virtual int compareStructure(const Ptr &other)=0
Compare two expressions structurally for sorting.
Ptr makeExtract(const Ptr &begin, const Ptr &end, const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Ptr makeConcat(const Ptr &hi, const Ptr &lo, const std::string &comment="", unsigned flags=0)
Interior node constructor.
SharedPointer< U > dynamicCast() const
Dynamic cast.
InteriorPtr commutative()
Simplifies commutative operators by sorting arguments.
Ptr makeLe(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
void comment(const std::string &s)
Property: Comment.
static const unsigned RESERVED_FLAGS
These flags are reserved for use within ROSE.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
uint64_t nameId()
Returns the name ID of a free variable.
Ptr makeLt(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
virtual bool isNumber()=0
Returns true if the expression is a known numeric value.
Ptr child(size_t idx)
Returns the specified child.
virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE
Constant folding.
Ptr makeAdd(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
size_t nBits()
Property: Number of significant bits.
Ptr newFlags(unsigned flags)
Sets flags.
Sawyer::SharedPointer< Leaf > LeafPtr
Shared-ownership pointer to an expression Leaf node.
Base class for reference counted objects.
Definition: SharedObject.h:22
virtual bool isEquivalentTo(const Ptr &other) ROSE_OVERRIDE
Tests two expressions for structural equivalence.
Ptr makeNegate(const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
Ptr rewrite(const Simplifier &simplifier)
Simplify an interior node.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Sawyer::SharedPointer< Interior > InteriorPtr
Shared-ownership pointer to an expression Interior node.
virtual void print(std::ostream &, Formatter &) ROSE_OVERRIDE
Print the expression to a stream.
Ptr makeMemory(size_t addressWidth, size_t valueWidth, const std::string &comment="", unsigned flags=0)
Leaf constructor.
virtual Ptr substitute(const Ptr &from, const Ptr &to) ROSE_OVERRIDE
Substitute one value for another.
Ptr setToIte(const Ptr &, const LeafPtr &var=LeafPtr())
Convert a set to an ite expression.
Ptr makeIte(const Ptr &cond, const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
Ptr makeBoolean(bool, const std::string &comment="", unsigned flags=0)
Leaf constructor.
Ptr makeExtend(const Ptr &newSize, const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
Exceptions for symbolic expressions.
virtual bool isNumber() ROSE_OVERRIDE
Returns true if the expression is a known numeric value.
static LeafPtr createConstant(const Sawyer::Container::BitVector &bits, const std::string &comment="", unsigned flags=0)
Construct a new known value with the specified bits.
bool use_hexadecimal
Show values in hexadecimal and decimal rather than just decimal.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
size_t nChildren()
Returns the number of children.
Base class for symbolic expression nodes.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
static Ptr create(size_t nbits, Operator op, const Ptr &a, const std::string &comment="", unsigned flags=0)
Create a new expression node.
bool isHashed()
Returns true if this node has a hash value computed and cached.
static LeafPtr createExistingMemory(size_t addressWidth, size_t valueWidth, uint64_t id, const std::string &comment="", unsigned flags=0)
Construct another reference to an existing variable.
Ptr makeMssb(const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
Operator
Operators for interior nodes of the expression tree.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Ptr makeAnd(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Ptr unaryNoOp()
Replaces a binary operator with its only argument.
bool show_flags
Show user-defined flags inside square brackets.
virtual uint64_t nNodes() ROSE_OVERRIDE
Computes the size of an expression by counting the number of nodes.
API and storage for attributes.
Definition: Attribute.h:208
Compare two expressions for STL containers.
void addChild(const Ptr &child)
Appends child as a new child of this node.
const uint64_t MAX_NNODES
Maximum number of nodes that can be reported.
Interface to Satisfiability Modulo Theory (SMT) solvers.
WithFormatter withFormat(Formatter &fmt)
Combines a node with a formatter for printing.
Ptr identity(uint64_t ident)
Removes identity arguments.
WithFormatter operator+(Formatter &fmt)
Combines a node with a formatter for printing.
const Nodes & children()
Property: Children.
virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE
Constant folding.
Ptr makeSignedMod(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
Ptr makeNe(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
Ptr makeWrite(const Ptr &mem, const Ptr &addr, const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
void printAsUnsigned(std::ostream &o, Formatter &f)
Prints an integer interpreted as an unsigned value.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Ptr makeSignedMul(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
Base class for visiting nodes during expression traversal.
Ptr makeSignExtend(const Ptr &newSize, const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
Ptr makeAsr(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
const std::string & comment()
Property: Comment.
void assertAcyclic()
Asserts that expressions are acyclic.
Write (update) memory with a new value.
Ptr makeRead(const Ptr &mem, const Ptr &addr, const std::string &comment="", unsigned flags=0)
Interior node constructor.
LeafPtr isLeafNode()
Dynamic cast of this object to a leaf node.
Ptr makeShr1(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0)
Interior node constructor.
std::vector< Ptr > findCommonSubexpressions(const std::vector< Ptr > &)
Find common subexpressions.
virtual uint64_t nNodes()=0
Computes the size of an expression by counting the number of nodes.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Container associating values with keys.
Definition: Sawyer/Map.h:64
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
Ptr foldConstants(const Simplifier &)
Perform constant folding.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE
Constant folding.
Ptr makeSignedLt(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
Ptr makeSignedDiv(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
Interior node constructor.
virtual Ptr rewrite(Interior *) const ROSE_OVERRIDE
Rewrite the entire expression to something simpler.
virtual VisitAction depthFirstTraversal(Visitor &) ROSE_OVERRIDE
Traverse the expression.
For a pre-order depth-first visit, do not descend into children.