From d55171601a0537506ddd05d37a1dabe372454a6d Mon Sep 17 00:00:00 2001 From: Daniel Dunbar Date: Wed, 3 Jun 2009 03:18:43 +0000 Subject: Remove ref<>'s constant Expr optimization. - This simplifies what users of the Expr language need to deal with, and paves the way for arbitrary bit-width constant support. - The downside is that concrete interpretation just got *way* slower (2-3x). However, I have a plan for fixing this that should give us the best of both worlds in terms of performance & simplicity. git-svn-id: https://llvm.org/svn/llvm-project/klee/trunk@72753 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/klee/Expr.h | 7 ++- include/klee/util/Ref.h | 156 ++++++++++-------------------------------------- 2 files changed, 38 insertions(+), 125 deletions(-) (limited to 'include') diff --git a/include/klee/Expr.h b/include/klee/Expr.h index 49dc65ec..5585b102 100644 --- a/include/klee/Expr.h +++ b/include/klee/Expr.h @@ -326,7 +326,9 @@ public: static ref alloc(uint64_t v, Width w) { // constructs an "optimized" ConstantExpr - return ref(v, w); + ref r(new ConstantExpr(v, w)); + r.computeHash(); + return r; } static ref create(uint64_t v, Width w) { @@ -536,7 +538,8 @@ public: ref cond, trueExpr, falseExpr; public: - static ref alloc(const ref &c, const ref &t, const ref &f) { + static ref alloc(const ref &c, const ref &t, + const ref &f) { ref r(new SelectExpr(c, t, f)); r.computeHash(); return r; diff --git a/include/klee/util/Ref.h b/include/klee/util/Ref.h index a552df39..5e6aab4b 100644 --- a/include/klee/util/Ref.h +++ b/include/klee/util/Ref.h @@ -21,46 +21,24 @@ class ObjectState; template class ref { + T *ptr; + public: // default constructor: create a NULL reference - ref() : constantWidth(Expr::InvalidWidth) { - contents.ptr = 0; - } + ref() : ptr(0) { } + ~ref () { dec (); } private: - // if NotConstant, not this ref is not a constant. - // otherwise, it's the width of the constant. - Expr::Width constantWidth; - static const Expr::Width NotConstant = (Expr::Width) 0; - - union { - T *ptr; - uint64_t val; - } contents; - void inc() { - if (constantWidth == NotConstant && - contents.ptr) { - contents.ptr->refCount++; - } + if (ptr) + ++ptr->refCount; } void dec() { - if (constantWidth == NotConstant && - contents.ptr && - --contents.ptr->refCount == 0) { - delete contents.ptr; - } + if (ptr && --ptr->refCount == 0) + delete ptr; } - friend class ExprVisitor; - friend class ConstantExpr; - - // construct from constant - ref(uint64_t val, Expr::Width w) : constantWidth(w) { - contents.val = val; - } - public: template friend class ref; template friend U* dyn_ref_cast(ref &src); @@ -69,117 +47,72 @@ public: template friend const U* static_ref_cast(const ref &src); // constructor from pointer - ref(T *p) : constantWidth(NotConstant) { - contents.ptr = p; + ref(T *p) : ptr(p) { inc(); } // normal copy constructor - ref(const ref &r) - : constantWidth(r.constantWidth), contents(r.contents) { + ref(const ref &r) : ptr(r.ptr) { inc(); } // conversion constructor template ref (const ref &r) { - constantWidth = r.constantWidth; - contents.val = r.contents.val; + ptr = r.ptr; inc(); } // pointer operations T *get () { - // demand(constantWidth == NotConstant, "deref of constant"); - - // allocate - if (constantWidth != NotConstant) { - contents.ptr = dynamic_cast(Expr::createConstant(contents.val, constantWidth)); - assert(contents.ptr && "error with lazy constant initialization"); - constantWidth = NotConstant; - - inc(); - } - return contents.ptr; + return ptr; } T *get () const { - assert(constantWidth == NotConstant && "deref of constant"); - return contents.ptr; + return ptr; } // method calls for the constant optimization bool isConstant() const { - if (constantWidth != NotConstant) { - return true; - } else if (contents.ptr) { - return contents.ptr->getKind() == Expr::Constant; - } else { - return false; // should never happen, but nice check - } + return ptr && ptr->getKind() == Expr::Constant; } uint64_t getConstantValue() const { - if (constantWidth) { - return contents.val; - } else { - return contents.ptr->getConstantValue(); - } + assert(isConstant() && "Invalid call to getConstantValue()"); + return ptr->getConstantValue(); } unsigned hash() const { - if (constantWidth) { - return contents.val ^ (constantWidth * Expr::MAGIC_HASH_CONSTANT); - } else { - return contents.ptr->hash(); - } + assert(!isNull() && "Invalid call to hash()"); + return ptr->hash(); } unsigned computeHash() const { - if (isConstant()) { - return contents.val ^ (constantWidth * Expr::MAGIC_HASH_CONSTANT); - } else { - return contents.ptr->computeHash(); - } - } - - void rehash() const { - if (!isConstant()) - contents.ptr->computeHash(); + assert(!isNull() && "Invalid call to computeHash()"); + return ptr->computeHash(); } Expr::Width getWidth() const { - if (constantWidth != NotConstant) - return constantWidth; - return contents.ptr->getWidth(); + return ptr->getWidth(); } Expr::Kind getKind() const { - if (constantWidth != NotConstant) - return Expr::Constant; - return contents.ptr->getKind(); + return ptr->getKind(); } unsigned getNumKids() const { - if (constantWidth != NotConstant) - return 0; - return contents.ptr->getNumKids(); + return ptr->getNumKids(); } ref getKid(unsigned k) { - if (constantWidth != NotConstant) - return 0; - return contents.ptr->getKid(k); + return ptr->getKid(k); } - ~ref () { dec (); } - /* The copy assignment operator must also explicitly be defined, * despite a redundant template. */ ref &operator= (const ref &r) { dec(); - constantWidth = r.constantWidth; - contents.val = r.contents.val; + ptr = r.ptr; inc(); return *this; @@ -187,35 +120,18 @@ public: template ref &operator= (const ref &r) { dec(); - constantWidth = r.constantWidth; - contents.val = r.contents.val; + ptr = r.ptr; inc(); return *this; } - bool isNull() const { return !constantWidth && !contents.ptr; } + bool isNull() const { return ptr == 0; } // assumes non-null arguments int compare(const ref &rhs) const { - Expr::Kind ak = getKind(), bk = rhs.getKind(); - if (ak!=bk) - return (ak < bk) ? -1 : 1; - if (ak==Expr::Constant) { - Expr::Width at = getWidth(), bt = rhs.getWidth(); - if (at!=bt) - return (at < bt) ? -1 : 1; - uint64_t av = getConstantValue(), bv = rhs.getConstantValue(); - if (avbv) { - return 1; - } else { - return 0; - } - } else { - return get()->compare(*rhs.get()); - } + assert(!isNull() && !rhs.isNull() && "Invalid call to compare()"); + return get()->compare(*rhs.get()); } // assumes non-null arguments @@ -237,28 +153,22 @@ inline std::ostream &operator<<(std::ostream &os, const ref &e) { template U* dyn_ref_cast(ref &src) { - if (src.constantWidth != ref::NotConstant) - return 0; - - return dynamic_cast(src.contents.ptr); + return dynamic_cast(src.ptr); } template const U* dyn_ref_cast(const ref &src) { - if (src.constantWidth != ref::NotConstant) - return 0; - - return dynamic_cast(src.contents.ptr); + return dynamic_cast(src.ptr); } template U* static_ref_cast(ref &src) { - return static_cast(src.contents.ptr); + return static_cast(src.ptr); } template const U* static_ref_cast(const ref &src) { - return static_cast(src.contents.ptr); + return static_cast(src.ptr); } #endif /* KLEE_REF_H */ -- cgit 1.4.1