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

1 files changed, 163 insertions, 32 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
+
+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* fromInteger(const IntegerLiteral* expr, EqnSys& system) {
-  return &system.constant(*expr->getValue().getRawData());
+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;
+}
+
+
+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<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);
-
-  return NULL;
+    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();
+
+    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);