From f168645671e31b5d2e7fb134b9d9f8750aebb872 Mon Sep 17 00:00:00 2001 From: "Zancanaro; Carlo" Date: Mon, 24 Sep 2012 14:28:32 +1000 Subject: Fix up some of the interval solving stuff. Still missing: - Guards - Actual construction of the EquationSystem - Necessary operators for a Vector EquationSystem - Splitting blocks on multiple-assignment - Solving/linking with Checkers --- clang/lib/Analysis/Interval.cpp | 195 +++++++++++++++++++++++++++++++++------- 1 file changed, 163 insertions(+), 32 deletions(-) (limited to 'clang/lib/Analysis/Interval.cpp') diff --git a/clang/lib/Analysis/Interval.cpp b/clang/lib/Analysis/Interval.cpp index bfa1ccf..726c6de 100644 --- a/clang/lib/Analysis/Interval.cpp +++ b/clang/lib/Analysis/Interval.cpp @@ -47,24 +47,83 @@ IntervalAnalysis :: ~IntervalAnalysis() { // // Hooray! -EqnExpr* fromStmt(const Stmt*, EqnSys&); +typedef Complete ZBar; +typedef std::map Vector; +typedef std::pair Result; // a "slice" of an equation + +template +void transform_values(const F& f, M& map) { + for (typename M::iterator it = map.begin(), + ei = map.end(); + it != ei; + ++it) { + it->second = f(it->second); + } +} + +template +M merge_maps_with(const F& f, const M& left, const M& right) { + M result; + typename M::const_iterator first1 = left.begin(), last1 = left.end(), + first2 = right.begin(), last2 = right.end(); + for (; first1 != last1 && first2 != last2;) { + if (first2->first < first1->first) { + result[first2->first] = first2->second; + ++first2; + } else if (first1->first == first2->first) { + result[first1->first] = f(first1->second, first2->second); + ++first1; + ++first2; + } else { + result[first1->first] = first1->second; + ++first1; + } + } + while (first1 != last1) { + result[first1->first] = first1->second; + ++first1; + } + while (first2 != last2) { + result[first2->first] = first2->second; + ++first2; + } + return result; +} -EqnExpr* fromInteger(const IntegerLiteral* expr, EqnSys& system) { - return &system.constant(*expr->getValue().getRawData()); +template +T negate(const T& v) { + return -v; +} +template +T addValues(const T& l, const T& r) { + return l + r; +} +template +T subValues(const T& l, const T& r) { + return l - r; +} + + +Result fromStmt(const Stmt*, EqnSys&); + +Result fromInteger(const IntegerLiteral* expr, EqnSys& system) { + return Result(Vector(), *expr->getValue().getRawData()); } -EqnExpr* fromDeclExpr(const DeclRefExpr* expr, EqnSys& system) { - return &system.variable(expr->getNameInfo().getAsString()); +Result fromDeclExpr(const DeclRefExpr* expr, EqnSys& system) { + Vector val; + val[expr->getNameInfo().getAsString()] = 1; + return Result(val, 0); } -EqnExpr* fromUnary(const UnaryOperator* op, EqnSys& system) { +Result fromUnary(const UnaryOperator* op, EqnSys& system) { switch (op->getOpcode()) { case UO_PreInc: break; case UO_PostInc: break; } - return NULL; + return Result(Vector(), 0); } @@ -72,32 +131,55 @@ Addition >* add = new Addition >(); Subtraction >* sub = new Subtraction >(); Multiplication >* mul = new Multiplication >(); -EqnExpr* fromBinary(const BinaryOperator* op, EqnSys& system) { - EqnExpr* left = fromStmt(op->getLHS()->IgnoreParenCasts(), system); - EqnExpr* right = fromStmt(op->getRHS()->IgnoreParenCasts(), system); - - std::vector args; - args.push_back(left); - args.push_back(right); +Result fromBinary(const BinaryOperator* op, EqnSys& system) { + Result left = fromStmt(op->getLHS()->IgnoreParenCasts(), system); + Result right = fromStmt(op->getRHS()->IgnoreParenCasts(), system); switch (op->getOpcode()) { - case BO_Add: - return &system.expression(add, args); case BO_Sub: - return &system.expression(sub, args); + transform_values(negate, right.first); + case BO_Add: + { + Result result; + result.first = merge_maps_with(addValues, + left.first, right.first); + result.second = left.second + right.second; + return result; + } case BO_Mul: - return &system.expression(mul, args); + { + if (!left.first.empty() && !right.first.empty()) { + return Result(Vector(), 0); + } + ZBar scalar = 0; + Result value; + if (left.first.empty()) { + scalar = left.second; + value = right; + } else { + scalar = right.second; + value = left; + } + for (Vector::iterator it = value.first.begin(), + ei = value.first.end(); + it != ei; + ++it) { + it->second *= scalar; + } + right.second *= scalar; + return value; + } case BO_LT: case BO_LE: case BO_GT: case BO_GE: break; } - return NULL; + return Result(); } -EqnExpr* fromDeclStmt(const DeclStmt* stmt, EqnSys& system) { - for (DeclStmt::const_decl_iterator it = stmt->decl_begin(), +Result fromDeclStmt(const DeclStmt* stmt, EqnSys& system) { + /*for (DeclStmt::const_decl_iterator it = stmt->decl_begin(), ei = stmt->decl_end(); it != ei; ++it) { @@ -109,12 +191,35 @@ EqnExpr* fromDeclStmt(const DeclStmt* stmt, EqnSys& system) { args.push_back(fromStmt(decl->getInit(), system)); system[var] = &system.maxExpression(args); } + }*/ + + for (DeclStmt::const_decl_iterator it = stmt->decl_begin(), + ei = stmt->decl_end(); + it != ei; + ++it) { + if ((*it)->getKind() == Decl::Var) { + const VarDecl* decl = static_cast(*it); + llvm::errs() << decl->getNameAsString() << " = "; + + Result expr = fromStmt(decl->getInit(), system); + llvm::errs() << "<{ "; + for (Vector::iterator it = expr.first.begin(), + ei = expr.first.end(); + it != ei; + ++it) { + if (it != expr.first.begin()) + llvm::errs() << ", "; + llvm::errs() << toString(it->first) << " = " << toString(it->second); + } + llvm::errs() << " }, " << toString(expr.second) << ">\n"; + } } - return NULL; + + return Result(); } -EqnExpr* fromAssignment(const BinaryOperator* op, EqnSys& system) { - EqnExpr* left = fromStmt(op->getLHS()->IgnoreParenCasts(), system); +Result fromAssignment(const BinaryOperator* op, EqnSys& system) { + /*EqnExpr* left = fromStmt(op->getLHS()->IgnoreParenCasts(), system); EqnExpr* right = fromStmt(op->getRHS()->IgnoreParenCasts(), system); Variable >* var = static_cast >*>(left); @@ -123,14 +228,31 @@ EqnExpr* fromAssignment(const BinaryOperator* op, EqnSys& system) { args.push_back(right); if (system[*var] != NULL) args.push_back(system[*var]); - system[*var] = &system.maxExpression(args); - - return NULL; + system[*var] = &system.maxExpression(args);*/ + + const Expr* left = op->getLHS()->IgnoreParenCasts(); + if (left->getStmtClass() == Stmt::DeclRefExprClass) { + std::string name = static_cast(left)->getNameInfo().getAsString(); + + Result expr = fromStmt(op->getRHS()->IgnoreParenCasts(), system); + llvm::errs() << name << " = <{ "; + for (Vector::iterator it = expr.first.begin(), + ei = expr.first.end(); + it != ei; + ++it) { + if (it != expr.first.begin()) + llvm::errs() << ", "; + llvm::errs() << toString(it->first) << " = " << toString(it->second); + } + llvm::errs() << " }, " << toString(expr.second) << ">\n"; + return expr; + } + return Result(); } -EqnExpr* fromStmt(const Stmt* stmt, EqnSys& system) { +Result fromStmt(const Stmt* stmt, EqnSys& system) { if (!stmt) - return NULL; + return Result(); switch (stmt->getStmtClass()) { case Stmt::IntegerLiteralClass: return fromInteger(static_cast(stmt), system); @@ -149,7 +271,7 @@ EqnExpr* fromStmt(const Stmt* stmt, EqnSys& system) { return fromBinary(binop, system); } } - return NULL; + return Result(); } void runOnBlock(std::string id, const CFGBlock* block, EqnSys& system) { @@ -158,8 +280,17 @@ void runOnBlock(std::string id, const CFGBlock* block, EqnSys& system) { it != ei; ++it) { const CFGStmt* cfg_stmt = it->getAs(); - const Stmt* stmt = static_cast(cfg_stmt->getStmt()); - EqnExpr* expr = fromStmt(stmt, system); + Result expr = fromStmt(cfg_stmt->getStmt(), system); + /*llvm::errs() << "<{ "; + for (Vector::iterator it = expr.first.begin(), + ei = expr.first.end(); + it != ei; + ++it) { + if (it != expr.first.begin()) + llvm::errs() << ", "; + llvm::errs() << toString(it->first) << " = " << toString(it->second); + } + llvm::errs() << "}, " << toString(expr.second) << ">\n";*/ } fromStmt(block->getTerminatorCondition(), system); -- cgit v1.2.3