summaryrefslogtreecommitdiff
path: root/clang/lib/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'clang/lib/Analysis')
-rw-r--r--clang/lib/Analysis/Interval.cpp193
1 files changed, 162 insertions, 31 deletions
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<int64_t> ZBar;
+typedef std::map<std::string, ZBar> Vector;
+typedef std::pair<Vector, ZBar> Result; // a "slice" of an equation
-EqnExpr* fromInteger(const IntegerLiteral* expr, EqnSys& system) {
- return &system.constant(*expr->getValue().getRawData());
+template<class F, class M>
+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<class M, class F>
+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* fromDeclExpr(const DeclRefExpr* expr, EqnSys& system) {
- return &system.variable(expr->getNameInfo().getAsString());
+template<class T>
+T negate(const T& v) {
+ return -v;
+}
+template<class T>
+T addValues(const T& l, const T& r) {
+ return l + r;
+}
+template<class T>
+T subValues(const T& l, const T& r) {
+ return l - r;
}
-EqnExpr* fromUnary(const UnaryOperator* op, EqnSys& system) {
+
+Result fromStmt(const Stmt*, EqnSys&);
+
+Result fromInteger(const IntegerLiteral* expr, EqnSys& system) {
+ return Result(Vector(), *expr->getValue().getRawData());
+}
+
+Result fromDeclExpr(const DeclRefExpr* expr, EqnSys& system) {
+ Vector val;
+ val[expr->getNameInfo().getAsString()] = 1;
+ return Result(val, 0);
+}
+
+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<Complete<int> >* add = new Addition<Complete<int> >();
Subtraction<Complete<int> >* sub = new Subtraction<Complete<int> >();
Multiplication<Complete<int> >* mul = new Multiplication<Complete<int> >();
-EqnExpr* fromBinary(const BinaryOperator* op, EqnSys& system) {
- EqnExpr* left = fromStmt(op->getLHS()->IgnoreParenCasts(), system);
- EqnExpr* right = fromStmt(op->getRHS()->IgnoreParenCasts(), system);
-
- std::vector<EqnExpr*> 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<ZBar>, right.first);
+ case BO_Add:
+ {
+ Result result;
+ result.first = merge_maps_with(addValues<ZBar>,
+ 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<const VarDecl*>(*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<Complete<int> >* var = static_cast<Variable<Complete<int> >*>(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);
+ system[*var] = &system.maxExpression(args);*/
+
+ const Expr* left = op->getLHS()->IgnoreParenCasts();
+ if (left->getStmtClass() == Stmt::DeclRefExprClass) {
+ std::string name = static_cast<const DeclRefExpr*>(left)->getNameInfo().getAsString();
- return NULL;
+ 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<const IntegerLiteral*>(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<CFGStmt>();
- const Stmt* stmt = static_cast<const Stmt*>(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);
generated by cgit v1.2.3 (git 2.50.1) at 2025-10-26 20:54:17 +0000