ROSE  0.9.9.168
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 {
96  OP_BV_AND = OP_AND, // [Robb Matzke 2017-11-14]: deprecated
97  OP_BV_OR = OP_OR, // [Robb Matzke 2017-11-14]: deprecated
98  OP_BV_XOR = OP_XOR // [Robb Matzke 2017-11-14]: deprecated
99 };
100 
101 std::string toStr(Operator);
102 
103 class Node;
104 class Interior;
105 class Leaf;
106 
109 
112 
115 
116 typedef std::vector<Ptr> Nodes;
118 
120 typedef uint64_t Hash;
121 
123 struct Formatter {
128  };
129  Formatter()
131  max_depth(0), cur_depth(0), show_width(true), show_flags(true) {}
133  bool do_rename;
134  bool add_renames;
136  size_t max_depth;
137  size_t cur_depth;
138  RenameMap renames;
139  bool show_width;
140  bool show_flags;
141 };
142 
148 };
149 
154 extern const uint64_t MAX_NNODES; // defined in .C so we don't pollute user namespace with limit macros
155 
160 class Visitor {
161 public:
162  virtual ~Visitor() {}
163  virtual VisitAction preVisit(const Ptr&) = 0;
164  virtual VisitAction postVisit(const Ptr&) = 0;
165 };
166 
167 
168 
170 // Base Node Type
172 
210 class Node
211  : public Sawyer::SharedObject,
212  public Sawyer::SharedFromThis<Node>,
213  public Sawyer::SmallObject,
214  public Sawyer::Attribute::Storage<> { // Attributes are not significant for hashing or arithmetic
215 protected:
216  size_t nBits_;
217  size_t domainWidth_;
218  unsigned flags_;
219  std::string comment_;
220  Hash hashval_;
221  boost::any userData_;
223 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
224 private:
225  friend class boost::serialization::access;
226 
227  template<class S>
228  void serialize(S &s, const unsigned version) {
229  s & BOOST_SERIALIZATION_NVP(nBits_);
230  s & BOOST_SERIALIZATION_NVP(domainWidth_);
231  s & BOOST_SERIALIZATION_NVP(flags_);
232  s & BOOST_SERIALIZATION_NVP(comment_);
233  s & BOOST_SERIALIZATION_NVP(hashval_);
234  // s & userData_;
235  }
236 #endif
237 
238 public:
239  // Bit flags
240 
242  static const unsigned RESERVED_FLAGS = 0x0000ffff;
243 
245  static const unsigned INDETERMINATE = 0x00000001;
246 
251  static const unsigned UNSPECIFIED = 0x00000002;
252 
255  static const unsigned BOTTOM = 0x00000004;
256 
257 protected:
258  Node()
259  : nBits_(0), domainWidth_(0), flags_(0), hashval_(0) {}
260  explicit Node(const std::string &comment, unsigned flags=0)
261  : nBits_(0), domainWidth_(0), flags_(flags), comment_(comment), hashval_(0) {}
262 
263 public:
269  virtual bool mustEqual(const Ptr &other, SmtSolver*) = 0;
270 
271  // [Robb P. Matzke 2015-10-08]: deprecated
272  bool must_equal(const Ptr& other, SmtSolver *solver) ROSE_DEPRECATED("use mustEqual instead") {
273  return mustEqual(other, solver);
274  }
275 
277  virtual bool mayEqual(const Ptr &other, SmtSolver*) = 0;
278 
279  // [Robb P. Matzke 2015-10-08]: deprecated
280  bool may_equal(const Ptr &other, SmtSolver *solver) ROSE_DEPRECATED("use mayEqual instead") {
281  return mayEqual(other, solver);
282  }
283 
289  virtual bool isEquivalentTo(const Ptr &other) = 0;
290 
291  // [Robb P. Matzke 2015-10-08]: deprecated
292  bool equivalent_to(const Ptr& other) ROSE_DEPRECATED("use isEquivalentTo instead") {
293  return isEquivalentTo(other);
294  }
295 
301  virtual int compareStructure(const Ptr &other) = 0;
302 
303  // [Robb P. Matzke 2015-10-08]: deprecated
304  int structural_compare(const Ptr& other) ROSE_DEPRECATED("use compareStructure instead") {
305  return compareStructure(other);
306  }
307 
313  virtual Ptr substitute(const Ptr &from, const Ptr &to) = 0;
314 
318  virtual bool isNumber() = 0;
319 
320  // [Robb P. Matzke 2015-10-08]: deprecated
321  bool is_known() ROSE_DEPRECATED("use isNumber instead") {
322  return isNumber();
323  }
324 
329  virtual uint64_t toInt() = 0;
330 
331  // [Robb P. Matzke 2015-10-08]: deprecated
332  uint64_t get_value() ROSE_DEPRECATED("use toInt instead") {
333  return toInt();
334  }
335 
344  const std::string& comment() { return comment_; }
345  void comment(const std::string &s) { comment_ = s; }
348  // [Robb P. Matzke 2015-10-08]: deprecated
349  const std::string& get_comment() ROSE_DEPRECATED("use 'comment' property instead") {
350  return comment();
351  }
352 
353  // [Robb P. Matzke 2015-10-08]: deprecated
354  void set_comment(const std::string &s) ROSE_DEPRECATED("use 'comment' property instead") {
355  comment(s);
356  }
357 
365  void userData(boost::any &data) {
366  userData_ = data;
367  }
368  const boost::any& userData() {
369  return userData_;
370  }
376  size_t nBits() { return nBits_; }
377 
378  // [Robb P. Matzke 2015-10-08]: deprecated
379  size_t get_nbits() ROSE_DEPRECATED("use 'nBits' property instead") {
380  return nBits();
381  }
382 
387  unsigned flags() { return flags_; }
388 
389  unsigned get_flags() ROSE_DEPRECATED("use 'flags' property instead") {
390  return flags();
391  }
392 
396  Ptr newFlags(unsigned flags);
397 
401  size_t domainWidth() { return domainWidth_; }
402 
406  bool isScalar() { return 0 == domainWidth_; }
407 
413 
414  // [Robb P. Matzke 2015-10-08]: deprecated
415  VisitAction depth_first_traversal(Visitor &v) ROSE_DEPRECATED("use depthFirstTraversal instead") {
416  return depthFirstTraversal(v);
417  }
418 
434  virtual uint64_t nNodes() = 0;
435 
436  // [Robb P. Matzke 2015-10-08]: deprecated
437  uint64_t nnodes() ROSE_DEPRECATED("use nNodes() instead") {
438  return nNodes();
439  }
440 
442  uint64_t nNodesUnique();
443 
444  // [Robb P. Matzke 2015-10-08]: deprecated
445  uint64_t nnodesUnique() ROSE_DEPRECATED("use nNodesUnique instead") {
446  return nNodesUnique();
447  }
448 
450  std::set<LeafPtr> getVariables();
451 
452  // [Robb P. Matzke 2015-10-08]: deprecated
453  std::set<LeafPtr> get_variables() ROSE_DEPRECATED("use getVariables instead") {
454  return getVariables();
455  }
456 
460  InteriorPtr isInteriorNode() {
461  return sharedFromThis().dynamicCast<Interior>();
462  }
463 
464  // [Robb P. Matzke 2015-10-09]: deprecated
465  InteriorPtr isInternalNode() ROSE_DEPRECATED("use isInteriorNode instead") {
466  return isInteriorNode();
467  }
468 
472  LeafPtr isLeafNode() {
473  return sharedFromThis().dynamicCast<Leaf>();
474  }
475 
479  bool isHashed() { return hashval_ != 0; }
480 
481  // [Robb P. Matzke 2015-10-08]: deprecated
482  bool is_hashed() ROSE_DEPRECATED("use isHashed instead") {
483  return isHashed();
484  }
485 
488  Hash hash();
489 
490  // used internally to set the hash value
491  void hash(Hash);
492 
495  private:
496  Ptr node;
497  Formatter &formatter;
498  public:
499  WithFormatter(const Ptr &node, Formatter &formatter): node(node), formatter(formatter) {}
500  void print(std::ostream &stream) const { node->print(stream, formatter); }
501  };
502 
521  // [Robb P. Matzke 2015-10-08]: deprecated
522  WithFormatter with_format(Formatter &fmt) ROSE_DEPRECATED("use withFormat instead") {
523  return withFormat(fmt);
524  }
525 
529  virtual void print(std::ostream&, Formatter&) = 0;
530  void print(std::ostream &o) { Formatter fmt; print(o, fmt); }
534  void assertAcyclic();
535 
536  // [Robb P. Matzke 2015-10-08]: deprecated
537  void assert_acyclic() {
538  return assertAcyclic();
539  }
540 
546  std::vector<Ptr> findCommonSubexpressions();
547 
548 protected:
549  void printFlags(std::ostream &o, unsigned flags, char &bracket);
550 };
551 
553 class Simplifier {
554 public:
555  virtual ~Simplifier() {}
556 
560  virtual Ptr fold(Nodes::const_iterator begin, Nodes::const_iterator end) const {
561  return Ptr();
562  }
563 
566  virtual Ptr rewrite(Interior*) const {
567  return Ptr();
568  }
569 };
570 
571 
574 public:
575  bool operator()(const Ptr &a, const Ptr &b);
576 };
577 
580 
581 
583 // Simplification
585 
587  virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE;
588  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
589 };
591  virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE;
592  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
593 };
595  virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE;
596  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
597 };
599  virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE;
600  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
601 };
603  virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE;
604 };
606  virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE;
607 };
609  virtual Ptr fold(Nodes::const_iterator, Nodes::const_iterator) const ROSE_OVERRIDE;
610  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
611 };
613  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
614 };
616  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
617 };
619  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
620 };
622  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
623 };
625  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
626 };
628  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
629 };
631  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
632 };
634  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
635 };
637  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
638 };
640  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
641 };
643  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
644 };
646  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
647 };
649  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
650 };
652  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
653 };
655  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
656 };
658  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
659 };
661  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
662 };
664  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
665 };
667  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
668 };
670  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
671 };
673  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
674 };
676  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
677 };
679  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
680 };
682  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
683 };
685  bool newbits;
686  ShiftSimplifier(bool newbits): newbits(newbits) {}
687  Ptr combine_strengths(Ptr strength1, Ptr strength2, size_t value_width) const;
688 };
690  ShlSimplifier(bool newbits): ShiftSimplifier(newbits) {}
691  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
692 };
694  ShrSimplifier(bool newbits): ShiftSimplifier(newbits) {}
695  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
696 };
698  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
699 };
701  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
702 };
704  virtual Ptr rewrite(Interior*) const ROSE_OVERRIDE;
705 };
706 
707 
708 
710 // Interior Nodes
712 
717 class Interior: public Node {
718 private:
719  Operator op_;
720  Nodes children_;
721  uint64_t nnodes_; // total number of nodes; self + children's nnodes
722 
723  // Constructors should not be called directly. Use the create() class method instead. This is to help prevent
724  // accidently using pointers to these objects -- all access should be through shared-ownership pointers.
725  Interior(): op_(OP_ADD), nnodes_(1) {} // needed for serialization
726  Interior(size_t nbits, Operator op, const Ptr &a, const std::string &comment="", unsigned flags=0);
727  Interior(size_t nbits, Operator op, const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
728  Interior(size_t nbits, Operator op, const Ptr &a, const Ptr &b, const Ptr &c, const std::string &comment="",
729  unsigned flags=0);
730  Interior(size_t nbits, Operator op, const Nodes &children, const std::string &comment="", unsigned flags=0);
731 
732 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
733 private:
734  friend class boost::serialization::access;
735 
736  template<class S>
737  void serialize(S &s, const unsigned version) {
738  s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Node);
739  s & BOOST_SERIALIZATION_NVP(op_);
740  s & BOOST_SERIALIZATION_NVP(children_);
741  s & BOOST_SERIALIZATION_NVP(nnodes_);
742  }
743 #endif
744 
745 public:
753  static Ptr create(size_t nbits, Operator op, const Ptr &a, const std::string &comment="", unsigned flags=0) {
754  InteriorPtr retval(new Interior(nbits, op, a, comment, flags));
755  return retval->simplifyTop();
756  }
757  static Ptr create(size_t nbits, Operator op, const Ptr &a, const Ptr &b,
758  const std::string &comment="", unsigned flags=0) {
759  InteriorPtr retval(new Interior(nbits, op, a, b, comment, flags));
760  return retval->simplifyTop();
761  }
762  static Ptr create(size_t nbits, Operator op, const Ptr &a, const Ptr &b, const Ptr &c,
763  const std::string &comment="", unsigned flags=0) {
764  InteriorPtr retval(new Interior(nbits, op, a, b, c, comment, flags));
765  return retval->simplifyTop();
766  }
767  static Ptr create(size_t nbits, Operator op, const Nodes &children, const std::string &comment="",
768  unsigned flags=0) {
769  InteriorPtr retval(new Interior(nbits, op, children, comment, flags));
770  return retval->simplifyTop();
771  }
774  /* see superclass, where these are pure virtual */
775  virtual bool mustEqual(const Ptr &other, SmtSolver*) ROSE_OVERRIDE;
776  virtual bool mayEqual(const Ptr &other, SmtSolver*) ROSE_OVERRIDE;
777  virtual bool isEquivalentTo(const Ptr &other) ROSE_OVERRIDE;
778  virtual int compareStructure(const Ptr& other) ROSE_OVERRIDE;
779  virtual Ptr substitute(const Ptr &from, const Ptr &to) ROSE_OVERRIDE;
780  virtual bool isNumber() ROSE_OVERRIDE {
781  return false; /*if it's known, then it would have been folded to a leaf*/
782  }
783  virtual uint64_t toInt() ROSE_OVERRIDE { ASSERT_forbid2(true, "not a number"); return 0;}
784  virtual VisitAction depthFirstTraversal(Visitor&) ROSE_OVERRIDE;
785  virtual uint64_t nNodes() ROSE_OVERRIDE { return nnodes_; }
786 
788  size_t nChildren() { return children_.size(); }
789 
790  // [Robb P. Matzke 2015-10-09]: deprecated
791  size_t nchildren() ROSE_DEPRECATED("use nChildren instead") {
792  return nChildren();
793  }
794 
796  Ptr child(size_t idx) { ASSERT_require(idx<children_.size()); return children_[idx]; }
797 
801  const Nodes& children() { return children_; }
802 
803  // [Robb P. Matzke 2015-10-09]: deprecated
804  Nodes get_children() ROSE_DEPRECATED("use 'children' property instead") {
805  return children();
806  }
807 
809  Operator getOperator() { return op_; }
810 
811  // [Robb P. Matzke 2015-10-09]: deprecated
812  Operator get_operator() ROSE_DEPRECATED("use getOperator instead") {
813  return getOperator();
814  }
815 
817  Ptr simplifyTop();
818 
821  Ptr foldConstants(const Simplifier&);
822 
823  // [Robb P. Matzke 2015-10-09]: deprecated
824  Ptr constant_folding(const Simplifier &simplifier) ROSE_DEPRECATED("use foldConstants instead") {
825  return foldConstants(simplifier);
826  }
827 
832  InteriorPtr associative();
833 
834  // [Robb P. Matzke 2015-10-09]: deprecated
835  InteriorPtr nonassociative() ROSE_DEPRECATED("use 'associative' instead") {
836  return associative();
837  }
838 
843  InteriorPtr commutative();
844 
848  Ptr involutary();
849 
851  Ptr additiveNesting();
852 
853  Ptr additive_nesting() ROSE_DEPRECATED("use additiveNesting instead") {
854  return additiveNesting();
855  }
856 
858  Ptr identity(uint64_t ident);
859 
861  Ptr unaryNoOp();
862 
865  Ptr rewrite(const Simplifier &simplifier);
866 
867  virtual void print(std::ostream&, Formatter&) ROSE_OVERRIDE;
868 
869 protected:
871  void addChild(const Ptr &child);
872 
873  // [Robb P. Matzke 2015-10-09]: deprecated
874  void add_child(const Ptr &child) ROSE_DEPRECATED("use addChild instead") {
875  addChild(child);
876  }
877 
879  void adjustWidth();
880 
883  void adjustBitFlags(unsigned extraFlags);
884 };
885 
886 
888 // Leaf Nodes
890 
894 class Leaf: public Node {
895 private:
896  enum LeafType { CONSTANT, BITVECTOR, MEMORY };
897  LeafType leafType_;
899  uint64_t name_;
901 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
902 private:
903  friend class boost::serialization::access;
904 
905  template<class S>
906  void save(S &s, const unsigned version) const {
907  s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Node);
908  s & BOOST_SERIALIZATION_NVP(leafType_);
909  s & BOOST_SERIALIZATION_NVP(bits_);
910  s & BOOST_SERIALIZATION_NVP(name_);
911  }
912 
913  template<class S>
914  void load(S &s, const unsigned version) {
915  s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Node);
916  s & BOOST_SERIALIZATION_NVP(leafType_);
917  s & BOOST_SERIALIZATION_NVP(bits_);
918  s & BOOST_SERIALIZATION_NVP(name_);
919  nextNameCounter(name_);
920  }
921 
922  BOOST_SERIALIZATION_SPLIT_MEMBER();
923 #endif
924 
925  // Private to help prevent creating pointers to leaf nodes. See create_* methods instead.
926 private:
927  Leaf()
928  : Node(""), leafType_(CONSTANT), name_(0) {}
929  explicit Leaf(const std::string &comment, unsigned flags=0)
930  : Node(comment, flags), leafType_(CONSTANT), name_(0) {}
931 
932 public:
934  static LeafPtr createVariable(size_t nbits, const std::string &comment="", unsigned flags=0);
935 
936  // [Robb P. Matzke 2015-10-09]: deprecated
937  static LeafPtr create_variable(size_t nbits, std::string comment="", unsigned flags=0)
938  ROSE_DEPRECATED("use createVariable instead") {
939  return createVariable(nbits, comment, flags);
940  }
941 
945  static LeafPtr createExistingVariable(size_t nbits, uint64_t id, const std::string &comment="", unsigned flags=0);
946 
947  // [Robb P. Matzke 2015-10-09]: deprecated
948  static LeafPtr create_existing_variable(size_t nbits, uint64_t id, const std::string &comment="", unsigned flags=0)
949  ROSE_DEPRECATED("use createExistingVariable instead") {
950  return createExistingVariable(nbits, id, comment, flags);
951  }
952 
955  static LeafPtr createInteger(size_t nbits, uint64_t n, const std::string &comment="", unsigned flags=0);
956 
957  // [Robb P. Matzke 2015-10-09]: deprecated
958  static LeafPtr create_integer(size_t nbits, uint64_t n, std::string comment="", unsigned flags=0)
959  ROSE_DEPRECATED("use createInteger instead") {
960  return createInteger(nbits, n, comment, flags);
961  }
962 
964  static LeafPtr createConstant(const Sawyer::Container::BitVector &bits, const std::string &comment="", unsigned flags=0);
965 
966  // [Robb P. Matzke 2015-10-09]: deprecated
967  static LeafPtr create_constant(const Sawyer::Container::BitVector &bits, std::string comment="", unsigned flags=0)
968  ROSE_DEPRECATED("use createConstant instead") {
969  return createConstant(bits, comment, flags);
970  }
971 
973  static LeafPtr createBoolean(bool b, const std::string &comment="", unsigned flags=0) {
974  return createInteger(1, (uint64_t)(b?1:0), comment, flags);
975  }
976 
977  // [Robb P. Matzke 2015-10-09]: deprecated
978  static LeafPtr create_boolean(bool b, std::string comment="", unsigned flags=0)
979  ROSE_DEPRECATED("use createBoolean instead") {
980  return createBoolean(b, comment, flags);
981  }
982 
984  static LeafPtr createMemory(size_t addressWidth, size_t valueWidth, const std::string &comment="", unsigned flags=0);
985 
989  static LeafPtr createExistingMemory(size_t addressWidth, size_t valueWidth, uint64_t id, const std::string &comment="",
990  unsigned flags=0);
991 
992  // [Robb P. Matzke 2015-10-09]: deprecated
993  static LeafPtr create_memory(size_t addressWidth, size_t valueWidth, std::string comment="", unsigned flags=0)
994  ROSE_DEPRECATED("use createMemory instead") {
995  return createMemory(addressWidth, valueWidth, comment, flags);
996  }
997 
998  // from base class
999  virtual bool isNumber() ROSE_OVERRIDE;
1000  virtual uint64_t toInt() ROSE_OVERRIDE;
1001  virtual bool mustEqual(const Ptr &other, SmtSolver*) ROSE_OVERRIDE;
1002  virtual bool mayEqual(const Ptr &other, SmtSolver*) ROSE_OVERRIDE;
1003  virtual bool isEquivalentTo(const Ptr &other) ROSE_OVERRIDE;
1004  virtual int compareStructure(const Ptr& other) ROSE_OVERRIDE;
1005  virtual Ptr substitute(const Ptr &from, const Ptr &to) ROSE_OVERRIDE;
1006  virtual VisitAction depthFirstTraversal(Visitor&) ROSE_OVERRIDE;
1007  virtual uint64_t nNodes() ROSE_OVERRIDE { return 1; }
1008 
1011 
1012  // [Robb P. Matzke 2015-10-09]: deprecated
1013  const Sawyer::Container::BitVector& get_bits() ROSE_DEPRECATED("use 'bits' property instead") {
1014  return bits();
1015  }
1016 
1018  virtual bool isVariable();
1019 
1020  // [Robb P. Matzke 2015-10-09]: deprecated
1021  bool is_variable() ROSE_DEPRECATED("use isVariable instead") {
1022  return isVariable();
1023  }
1024 
1026  virtual bool isMemory();
1027 
1028  // [Robb P. Matzke 2015-10-09]: deprecated
1029  bool is_memory() ROSE_DEPRECATED("use isMemory instead") {
1030  return isMemory();
1031  }
1032 
1037  uint64_t nameId();
1038 
1039  // [Robb P. Matzke 2015-10-09]: deprecated
1040  uint64_t get_name() ROSE_DEPRECATED("use nameId instead") {
1041  return nameId();
1042  }
1043 
1048  std::string toString();
1049 
1050  // documented in super class
1051  virtual void print(std::ostream&, Formatter&) ROSE_OVERRIDE;
1052 
1054  void printAsSigned(std::ostream&, Formatter&, bool asSigned=true);
1055 
1056  // [Robb P. Matzke 2015-10-09]: deprecated
1057  void print_as_signed(std::ostream &stream, Formatter &formatter, bool as_signed=true)
1058  ROSE_DEPRECATED("use printAsSigned instead") {
1059  printAsSigned(stream, formatter, as_signed);
1060  }
1061 
1063  void printAsUnsigned(std::ostream &o, Formatter &f) {
1064  printAsSigned(o, f, false);
1065  }
1066 
1067  // [Robb P. Matzke 2015-10-09]: deprecated
1068  void print_as_unsigned(std::ostream &o, Formatter &f) ROSE_DEPRECATED("use printAsUnsigned instead") {
1069  printAsUnsigned(o, f);
1070  }
1071 
1072 private:
1073  // Obtain or register a name ID
1074  static uint64_t nextNameCounter(uint64_t useThis = (uint64_t)(-1));
1075 };
1076 
1078 // Factories
1080 
1086 Ptr makeVariable(size_t nbits, const std::string &comment="", unsigned flags=0);
1087 Ptr makeExistingVariable(size_t nbits, uint64_t id, const std::string &comment="", unsigned flags=0);
1088 Ptr makeInteger(size_t nbits, uint64_t n, const std::string &comment="", unsigned flags=0);
1089 Ptr makeConstant(const Sawyer::Container::BitVector&, const std::string &comment="", unsigned flags=0);
1090 Ptr makeBoolean(bool, const std::string &comment="", unsigned flags=0);
1091 Ptr makeMemory(size_t addressWidth, size_t valueWidth, const std::string &comment="", unsigned flags=0);
1092 Ptr makeExistingMemory(size_t addressWidth, size_t valueWidth, uint64_t id, const std::string &comment="", unsigned flags=0);
1101 Ptr makeAdd(const Ptr&a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1102 Ptr makeBooleanAnd(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
1103  ROSE_DEPRECATED("use makeAnd instead"); // [Robb Matzke 2017-11-21]: deprecated
1104 Ptr makeAsr(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0);
1105 Ptr makeAnd(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1106 Ptr makeOr(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1107 Ptr makeXor(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1108 Ptr makeConcat(const Ptr &hi, const Ptr &lo, const std::string &comment="", unsigned flags=0);
1109 Ptr makeEq(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1110 Ptr makeExtract(const Ptr &begin, const Ptr &end, const Ptr &a, const std::string &comment="", unsigned flags=0);
1111 Ptr makeInvert(const Ptr &a, const std::string &comment="", unsigned flags=0);
1112 Ptr makeIte(const Ptr &cond, const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1113 Ptr makeLssb(const Ptr &a, const std::string &comment="", unsigned flags=0);
1114 Ptr makeMssb(const Ptr &a, const std::string &comment="", unsigned flags=0);
1115 Ptr makeNe(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1116 Ptr makeNegate(const Ptr &a, const std::string &comment="", unsigned flags=0);
1117 Ptr makeBooleanOr(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0)
1118  ROSE_DEPRECATED("use makeOr instead"); // [Robb Matzke 2017-11-21]: deprecated
1119 Ptr makeRead(const Ptr &mem, const Ptr &addr, const std::string &comment="", unsigned flags=0);
1120 Ptr makeRol(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0);
1121 Ptr makeRor(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0);
1122 Ptr makeSet(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1123 Ptr makeSet(const Ptr &a, const Ptr &b, const Ptr &c, const std::string &comment="", unsigned flags=0);
1124 Ptr makeSignedDiv(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1125 Ptr makeSignExtend(const Ptr &newSize, const Ptr &a, const std::string &comment="", unsigned flags=0);
1126 Ptr makeSignedGe(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1127 Ptr makeSignedGt(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1128 Ptr makeShl0(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0);
1129 Ptr makeShl1(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0);
1130 Ptr makeShr0(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0);
1131 Ptr makeShr1(const Ptr &sa, const Ptr &a, const std::string &comment="", unsigned flags=0);
1132 Ptr makeSignedLe(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1133 Ptr makeSignedLt(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1134 Ptr makeSignedMod(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1135 Ptr makeSignedMul(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1136 Ptr makeDiv(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1137 Ptr makeExtend(const Ptr &newSize, const Ptr &a, const std::string &comment="", unsigned flags=0);
1138 Ptr makeGe(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1139 Ptr makeGt(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1140 Ptr makeLe(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1141 Ptr makeLt(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1142 Ptr makeMod(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1143 Ptr makeMul(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0);
1144 Ptr makeWrite(const Ptr &mem, const Ptr &addr, const Ptr &a, const std::string &comment="", unsigned flags=0);
1145 Ptr makeZerop(const Ptr &a, const std::string &comment="", unsigned flags=0);
1149 // Miscellaneous functions
1152 
1153 
1154 std::ostream& operator<<(std::ostream &o, Node&);
1155 std::ostream& operator<<(std::ostream &o, const Node::WithFormatter&);
1156 
1158 Ptr setToIte(const Ptr&, const LeafPtr &var = LeafPtr());
1159 
1164 template<typename InputIterator>
1165 uint64_t
1166 nNodes(InputIterator begin, InputIterator end) {
1167  uint64_t total = 0;
1168  for (InputIterator ii=begin; ii!=end; ++ii) {
1169  uint64_t n = (*ii)->nnodes();
1170  if (MAX_NNODES==n)
1171  return MAX_NNODES;
1172  if (total + n < total)
1173  return MAX_NNODES;
1174  total += n;
1175  }
1176  return total;
1177 }
1178 
1179 // [Robb P. Matzke 2015-10-08]: deprecated
1180 template<typename InputIterator>
1181 uint64_t
1182 nnodes(InputIterator begin, InputIterator end) ROSE_DEPRECATED("use nNodes instead");
1183 template<typename InputIterator>
1184 uint64_t
1185 nnodes(InputIterator begin, InputIterator end) {
1186  return nNodes(begin, end);
1187 }
1188 
1193 template<typename InputIterator>
1194 uint64_t
1195 nNodesUnique(InputIterator begin, InputIterator end)
1196 {
1197  struct T1: Visitor {
1198  typedef std::set<const Node*> SeenNodes;
1199 
1200  SeenNodes seen; // nodes that we've already seen, and the subtree size
1201  uint64_t nUnique; // number of unique nodes
1202 
1203  T1(): nUnique(0) {}
1204 
1205  VisitAction preVisit(const Ptr &node) {
1206  if (seen.insert(getRawPointer(node)).second) {
1207  ++nUnique;
1208  return CONTINUE; // this node has not been seen before; traverse into children
1209  } else {
1210  return TRUNCATE; // this node has been seen already; skip over the children
1211  }
1212  }
1213 
1214  VisitAction postVisit(const Ptr &node) {
1215  return CONTINUE;
1216  }
1217  } visitor;
1218 
1219  VisitAction status = CONTINUE;
1220  for (InputIterator ii=begin; ii!=end && TERMINATE!=status; ++ii)
1221  status = (*ii)->depthFirstTraversal(visitor);
1222  return visitor.nUnique;
1223 }
1224 
1225 // [Robb P. Matzke 2015-10-08]: deprecated
1226 template<typename InputIterator>
1227 uint64_t
1228 nnodesUnique(InputIterator begin, InputIterator end) ROSE_DEPRECATED("use nNodesUnique instead");
1229 template<typename InputIterator>
1230 uint64_t
1231 nnodesUnique(InputIterator begin, InputIterator end) {
1232  return nNodesUnique(begin, end);
1233 }
1234 
1241 std::vector<Ptr> findCommonSubexpressions(const std::vector<Ptr>&);
1242 
1243 template<typename InputIterator>
1244 std::vector<Ptr>
1245 findCommonSubexpressions(InputIterator begin, InputIterator end) {
1246  typedef Sawyer::Container::Map<Ptr, size_t> NodeCounts;
1247  struct T1: Visitor {
1248  NodeCounts nodeCounts;
1249  std::vector<Ptr> result;
1250 
1251  VisitAction preVisit(const Ptr &node) ROSE_OVERRIDE {
1252  size_t &nSeen = nodeCounts.insertMaybe(node, 0);
1253  if (2 == ++nSeen)
1254  result.push_back(node);
1255  return nSeen>1 ? TRUNCATE : CONTINUE;
1256  }
1257 
1258  VisitAction postVisit(const Ptr&) ROSE_OVERRIDE {
1259  return CONTINUE;
1260  }
1261  } visitor;
1262 
1263  for (InputIterator ii=begin; ii!=end; ++ii)
1264  (*ii)->depthFirstTraversal(visitor);
1265  return visitor.result;
1266 }
1269 } // namespace
1270 } // namespace
1271 } // namespace
1272 
1273 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
1274 BOOST_CLASS_EXPORT_KEY(Rose::BinaryAnalysis::SymbolicExpr::Interior);
1275 BOOST_CLASS_EXPORT_KEY(Rose::BinaryAnalysis::SymbolicExpr::Leaf);
1276 #endif
1277 
1278 #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?
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
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 makeBooleanAnd(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0) ROSE_DEPRECATED("use makeAnd instead")
Interior node constructor.
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.
Ptr makeBooleanOr(const Ptr &a, const Ptr &b, const std::string &comment="", unsigned flags=0) ROSE_DEPRECATED("use makeOr instead")
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.