From 92e1bf7b665a7f5ec682becb78e014e62d10beec Mon Sep 17 00:00:00 2001 From: Daniel Dunbar Date: Sun, 14 Jun 2009 03:33:15 +0000 Subject: Add constant folding operations to ConstantExpr. - No (intended) functionality change. git-svn-id: https://llvm.org/svn/llvm-project/klee/trunk@73322 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Expr/Expr.cpp | 272 +++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 200 insertions(+), 72 deletions(-) (limited to 'lib/Expr/Expr.cpp') diff --git a/lib/Expr/Expr.cpp b/lib/Expr/Expr.cpp index 7b680567..597d1e08 100644 --- a/lib/Expr/Expr.cpp +++ b/lib/Expr/Expr.cpp @@ -345,6 +345,166 @@ void ConstantExpr::toMemory(void *address) { } } +ref ConstantExpr::Concat(const ref &RHS) { + Expr::Width W = getWidth() + RHS->getWidth(); + assert(W <= 64 && "FIXME: Support arbitrary bit-widths!"); + + uint64_t res = (getConstantValue() << RHS->getWidth()) + + RHS->getConstantValue(); + return ConstantExpr::create(res, W); +} + +ref ConstantExpr::Extract(unsigned Offset, Width W) { + return ConstantExpr::create(ints::trunc(getConstantValue() >> Offset, W, + getWidth()), W); +} + +ref ConstantExpr::ZExt(Width W) { + return ConstantExpr::create(ints::zext(getConstantValue(), W, getWidth()), W); +} + +ref ConstantExpr::SExt(Width W) { + return ConstantExpr::create(ints::sext(getConstantValue(), W, getWidth()), W); +} + +ref ConstantExpr::Add(const ref &RHS) { + return ConstantExpr::create(ints::add(getConstantValue(), + RHS->getConstantValue(), getWidth()), + getWidth()); +} + +ref ConstantExpr::Sub(const ref &RHS) { + return ConstantExpr::create(ints::sub(getConstantValue(), + RHS->getConstantValue(), getWidth()), + getWidth()); +} + +ref ConstantExpr::Mul(const ref &RHS) { + return ConstantExpr::create(ints::mul(getConstantValue(), + RHS->getConstantValue(), getWidth()), + getWidth()); +} + +ref ConstantExpr::UDiv(const ref &RHS) { + return ConstantExpr::create(ints::udiv(getConstantValue(), + RHS->getConstantValue(), getWidth()), + getWidth()); +} + +ref ConstantExpr::SDiv(const ref &RHS) { + return ConstantExpr::create(ints::sdiv(getConstantValue(), + RHS->getConstantValue(), getWidth()), + getWidth()); +} + +ref ConstantExpr::URem(const ref &RHS) { + return ConstantExpr::create(ints::urem(getConstantValue(), + RHS->getConstantValue(), getWidth()), + getWidth()); +} + +ref ConstantExpr::SRem(const ref &RHS) { + return ConstantExpr::create(ints::srem(getConstantValue(), + RHS->getConstantValue(), getWidth()), + getWidth()); +} + +ref ConstantExpr::And(const ref &RHS) { + return ConstantExpr::create(ints::land(getConstantValue(), + RHS->getConstantValue(), getWidth()), + getWidth()); +} + +ref ConstantExpr::Or(const ref &RHS) { + return ConstantExpr::create(ints::lor(getConstantValue(), + RHS->getConstantValue(), getWidth()), + getWidth()); +} + +ref ConstantExpr::Xor(const ref &RHS) { + return ConstantExpr::create(ints::lxor(getConstantValue(), + RHS->getConstantValue(), getWidth()), + getWidth()); +} + +ref ConstantExpr::Shl(const ref &RHS) { + return ConstantExpr::create(ints::shl(getConstantValue(), + RHS->getConstantValue(), getWidth()), + getWidth()); +} + +ref ConstantExpr::LShr(const ref &RHS) { + return ConstantExpr::create(ints::lshr(getConstantValue(), + RHS->getConstantValue(), getWidth()), + getWidth()); +} + +ref ConstantExpr::AShr(const ref &RHS) { + return ConstantExpr::create(ints::ashr(getConstantValue(), + RHS->getConstantValue(), getWidth()), + getWidth()); +} + +ref ConstantExpr::Eq(const ref &RHS) { + return ConstantExpr::create(ints::eq(getConstantValue(), + RHS->getConstantValue(), getWidth()), + Expr::Bool); +} + +ref ConstantExpr::Ne(const ref &RHS) { + return ConstantExpr::create(ints::ne(getConstantValue(), + RHS->getConstantValue(), getWidth()), + Expr::Bool); +} + +ref ConstantExpr::Ult(const ref &RHS) { + return ConstantExpr::create(ints::ult(getConstantValue(), + RHS->getConstantValue(), getWidth()), + Expr::Bool); +} + +ref ConstantExpr::Ule(const ref &RHS) { + return ConstantExpr::create(ints::ule(getConstantValue(), + RHS->getConstantValue(), getWidth()), + Expr::Bool); +} + +ref ConstantExpr::Ugt(const ref &RHS) { + return ConstantExpr::create(ints::ugt(getConstantValue(), + RHS->getConstantValue(), getWidth()), + Expr::Bool); +} + +ref ConstantExpr::Uge(const ref &RHS) { + return ConstantExpr::create(ints::uge(getConstantValue(), + RHS->getConstantValue(), getWidth()), + Expr::Bool); +} + +ref ConstantExpr::Slt(const ref &RHS) { + return ConstantExpr::create(ints::slt(getConstantValue(), + RHS->getConstantValue(), getWidth()), + Expr::Bool); +} + +ref ConstantExpr::Sle(const ref &RHS) { + return ConstantExpr::create(ints::sle(getConstantValue(), + RHS->getConstantValue(), getWidth()), + Expr::Bool); +} + +ref ConstantExpr::Sgt(const ref &RHS) { + return ConstantExpr::create(ints::sgt(getConstantValue(), + RHS->getConstantValue(), getWidth()), + Expr::Bool); +} + +ref ConstantExpr::Sge(const ref &RHS) { + return ConstantExpr::create(ints::sge(getConstantValue(), + RHS->getConstantValue(), getWidth()), + Expr::Bool); +} + /***/ ref NotOptimizedExpr::create(ref src) { @@ -424,22 +584,15 @@ ref SelectExpr::create(ref c, ref t, ref f) { /***/ - ref ConcatExpr::create(const ref &l, const ref &r) { Expr::Width w = l->getWidth() + r->getWidth(); // Fold concatenation of constants. // // FIXME: concat 0 x -> zext x ? - if (ConstantExpr *lCE = dyn_cast(l)) { - if (ConstantExpr *rCE = dyn_cast(r)) { - assert(w <= 64 && "ConcatExpr::create(): don't support concats describing constants greater than 64 bits yet"); - - uint64_t res = (lCE->getConstantValue() << rCE->getWidth()) + - rCE->getConstantValue(); - return ConstantExpr::create(res, w); - } - } + if (ConstantExpr *lCE = dyn_cast(l)) + if (ConstantExpr *rCE = dyn_cast(r)) + return lCE->Concat(rCE); // Merge contiguous Extracts if (ExtractExpr *ee_left = dyn_cast(l)) { @@ -468,7 +621,7 @@ ref ConcatExpr::createN(unsigned n_kids, const ref kids[]) { /// Shortcut to concat 4 kids. The chain returned is unbalanced to the right ref ConcatExpr::create4(const ref &kid1, const ref &kid2, - const ref &kid3, const ref &kid4) { + const ref &kid3, const ref &kid4) { return ConcatExpr::create(kid1, ConcatExpr::create(kid2, ConcatExpr::create(kid3, kid4))); } @@ -490,8 +643,7 @@ ref ExtractExpr::create(ref expr, unsigned off, Width w) { if (w == kw) { return expr; } else if (ConstantExpr *CE = dyn_cast(expr)) { - return ConstantExpr::create(ints::trunc(CE->getConstantValue() >> off, w, - kw), w); + return CE->Extract(off, w); } else { // Extract(Concat) if (ConcatExpr *ce = dyn_cast(expr)) { @@ -525,11 +677,9 @@ ref ZExtExpr::create(const ref &e, Width w) { return e; } else if (w < kBits) { // trunc return ExtractExpr::createByteOff(e, 0, w); + } else if (ConstantExpr *CE = dyn_cast(e)) { + return CE->ZExt(w); } else { - if (ConstantExpr *CE = dyn_cast(e)) - return ConstantExpr::create(ints::zext(CE->getConstantValue(), w, kBits), - w); - return ZExtExpr::alloc(e, w); } } @@ -540,11 +690,9 @@ ref SExtExpr::create(const ref &e, Width w) { return e; } else if (w < kBits) { // trunc return ExtractExpr::createByteOff(e, 0, w); - } else { - if (ConstantExpr *CE = dyn_cast(e)) - return ConstantExpr::create(ints::sext(CE->getConstantValue(), w, kBits), - w); - + } else if (ConstantExpr *CE = dyn_cast(e)) { + return CE->SExt(w); + } else { return SExtExpr::alloc(e, w); } } @@ -809,14 +957,9 @@ static ref AShrExpr_create(const ref &l, const ref &r) { ref _e_op ::create(const ref &l, const ref &r) { \ assert(l->getWidth()==r->getWidth() && "type mismatch"); \ if (ConstantExpr *cl = dyn_cast(l)) { \ - if (ConstantExpr *cr = dyn_cast(r)) { \ - Expr::Width width = l->getWidth(); \ - uint64_t val = ints::_op(cl->getConstantValue(), \ - cr->getConstantValue(), width); \ - return ConstantExpr::create(val, width); \ - } else { \ - return _e_op ## _createPartialR(cl, r.get()); \ - } \ + if (ConstantExpr *cr = dyn_cast(r)) \ + return cl->_op(cr); \ + return _e_op ## _createPartialR(cl, r.get()); \ } else if (ConstantExpr *cr = dyn_cast(r)) { \ return _e_op ## _createPartial(l.get(), cr); \ } \ @@ -826,42 +969,32 @@ ref _e_op ::create(const ref &l, const ref &r) { \ #define BCREATE(_e_op, _op) \ ref _e_op ::create(const ref &l, const ref &r) { \ assert(l->getWidth()==r->getWidth() && "type mismatch"); \ - if (ConstantExpr *cl = dyn_cast(l)) { \ - if (ConstantExpr *cr = dyn_cast(r)) { \ - Expr::Width width = l->getWidth(); \ - uint64_t val = ints::_op(cl->getConstantValue(), \ - cr->getConstantValue(), width); \ - return ConstantExpr::create(val, width); \ - } \ - } \ + if (ConstantExpr *cl = dyn_cast(l)) \ + if (ConstantExpr *cr = dyn_cast(r)) \ + return cl->_op(cr); \ return _e_op ## _create(l, r); \ } -BCREATE_R(AddExpr, add, AddExpr_createPartial, AddExpr_createPartialR) -BCREATE_R(SubExpr, sub, SubExpr_createPartial, SubExpr_createPartialR) -BCREATE_R(MulExpr, mul, MulExpr_createPartial, MulExpr_createPartialR) -BCREATE_R(AndExpr, land, AndExpr_createPartial, AndExpr_createPartialR) -BCREATE_R(OrExpr, lor, OrExpr_createPartial, OrExpr_createPartialR) -BCREATE_R(XorExpr, lxor, XorExpr_createPartial, XorExpr_createPartialR) -BCREATE(UDivExpr, udiv) -BCREATE(SDivExpr, sdiv) -BCREATE(URemExpr, urem) -BCREATE(SRemExpr, srem) -BCREATE(ShlExpr, shl) -BCREATE(LShrExpr, lshr) -BCREATE(AShrExpr, ashr) +BCREATE_R(AddExpr, Add, AddExpr_createPartial, AddExpr_createPartialR) +BCREATE_R(SubExpr, Sub, SubExpr_createPartial, SubExpr_createPartialR) +BCREATE_R(MulExpr, Mul, MulExpr_createPartial, MulExpr_createPartialR) +BCREATE_R(AndExpr, And, AndExpr_createPartial, AndExpr_createPartialR) +BCREATE_R(OrExpr, Or, OrExpr_createPartial, OrExpr_createPartialR) +BCREATE_R(XorExpr, Xor, XorExpr_createPartial, XorExpr_createPartialR) +BCREATE(UDivExpr, UDiv) +BCREATE(SDivExpr, SDiv) +BCREATE(URemExpr, URem) +BCREATE(SRemExpr, SRem) +BCREATE(ShlExpr, Shl) +BCREATE(LShrExpr, LShr) +BCREATE(AShrExpr, AShr) #define CMPCREATE(_e_op, _op) \ ref _e_op ::create(const ref &l, const ref &r) { \ assert(l->getWidth()==r->getWidth() && "type mismatch"); \ - if (ConstantExpr *cl = dyn_cast(l)) { \ - if (ConstantExpr *cr = dyn_cast(r)) { \ - Expr::Width width = cl->getWidth(); \ - uint64_t val = ints::_op(cl->getConstantValue(), \ - cr->getConstantValue(), width); \ - return ConstantExpr::create(val, Expr::Bool); \ - } \ - } \ + if (ConstantExpr *cl = dyn_cast(l)) \ + if (ConstantExpr *cr = dyn_cast(r)) \ + return cl->_op(cr); \ return _e_op ## _create(l, r); \ } @@ -869,14 +1002,9 @@ ref _e_op ::create(const ref &l, const ref &r) { \ ref _e_op ::create(const ref &l, const ref &r) { \ assert(l->getWidth()==r->getWidth() && "type mismatch"); \ if (ConstantExpr *cl = dyn_cast(l)) { \ - if (ConstantExpr *cr = dyn_cast(r)) { \ - Expr::Width width = cl->getWidth(); \ - uint64_t val = ints::_op(cl->getConstantValue(), \ - cr->getConstantValue(), width); \ - return ConstantExpr::create(val, Expr::Bool); \ - } else { \ - return partialR(cl, r.get()); \ - } \ + if (ConstantExpr *cr = dyn_cast(r)) \ + return cl->_op(cr); \ + return partialR(cl, r.get()); \ } else if (ConstantExpr *cr = dyn_cast(r)) { \ return partialL(l.get(), cr); \ } else { \ @@ -1072,8 +1200,8 @@ static ref SleExpr_create(const ref &l, const ref &r) { } } -CMPCREATE_T(EqExpr, eq, EqExpr, EqExpr_createPartial, EqExpr_createPartialR) -CMPCREATE(UltExpr, ult) -CMPCREATE(UleExpr, ule) -CMPCREATE(SltExpr, slt) -CMPCREATE(SleExpr, sle) +CMPCREATE_T(EqExpr, Eq, EqExpr, EqExpr_createPartial, EqExpr_createPartialR) +CMPCREATE(UltExpr, Ult) +CMPCREATE(UleExpr, Ule) +CMPCREATE(SltExpr, Slt) +CMPCREATE(SleExpr, Sle) -- cgit 1.4.1