Implementation stuff.

6 files changed, 143 insertions, 81 deletions

diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp
index 664d71f..73c8f23 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp
@@ -4,9 +4,15 @@
 #include <cassert>
 #include <ostream>
 #include <istream>
+#include <limits>
 
 template<typename T>
-T infinity() { }
+T infinity();
+
+template<>
+double infinity() {
+  return std::numeric_limits<double>::infinity();
+}
 
 template<typename T>
 struct Complete {
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp
index 5ee5405..3342cc7 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp
@@ -76,14 +76,9 @@ struct EquationSystem {
   }
 
   Constant<Domain>& constant(const Domain& value) {
-    if (_constants.find(value) == _constants.end()) {
-      Constant<Domain>* constant = new Constant<Domain>(value);
-      _expressions.insert(constant);
-      _constants[value] = constant;
-      return *constant;
-    } else {
-      return *_constants[value];
-    }
+    Constant<Domain>* constant = new Constant<Domain>(value);
+    _expressions.insert(constant);
+    return *constant;
   }
 
   MaxExpression<Domain>* operator[](const Variable<Domain>& var) const {
@@ -132,7 +127,6 @@ struct EquationSystem {
   private:
   std::set<Operator<Domain>*> _operators;
   std::set<Expression<Domain>*> _expressions;
-  std::map<Domain,Constant<Domain>*> _constants;
   std::vector<Variable<Domain>*> _variables;
   std::map<std::string, Variable<Domain>*> _variable_names;
   IdMap<MaxExpression<Domain>, Variable<Domain>*>* _expr_to_var;
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp
index 90ab7e5..7502ac8 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp
@@ -1,17 +1,13 @@
 #ifndef LOG_HPP
 #define LOG_HPP
 
-// could not be hackier, but C++ is annoying
-#define protected public
-#include <streambuf>
-#undef protected
-
 #include <string>
 #include <iostream>
 #include <map>
 #include <cstdio>
 
 namespace solver_log {
+
   struct Logger : public std::ostream {
     Logger(std::streambuf* buffer, const std::string& name)
       : std::ostream(NULL) { }
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
index 9ae7394..da05dd8 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
@@ -39,22 +39,13 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> {
       _values(system.maxExpressionCount(), 0),
       _stable(system.maxExpressionCount()),
       _influence(system.maxExpressionCount(),
-                 IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
-      _changed(false)
+                 IdSet<MaxExpression<Domain> >(system.maxExpressionCount()))
   {}
 
   void setRho(DynamicVariableAssignment<Domain>& rho) {
     _rho = &rho;
   }
 
-  void hasChanged(bool c) {
-    _changed = c;
-  }
-
-  bool hasChanged() const {
-    return _changed;
-  }
-
   unsigned int get(const MaxExpression<Domain>& e) const {
     solver_log::strategy << indent() << "Look up " << e << std::endl;
     return _values[e];
@@ -66,19 +57,6 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> {
     return _values[e];
   }
 
-  void invalidate(const Variable<Domain>& v) {
-    solver_log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl; 
-
-    IdSet<MaxExpression<Domain> > infl = _influence[*_system[v]];
-    for (typename IdSet<MaxExpression<Domain> >::iterator
-           it = infl.begin(),
-           end = infl.end();
-         it != end;
-         ++it) {
-      invalidate(_system.maxExpression(*it));
-    }
-  }
-
   void invalidate(const MaxExpression<Domain>& v) {
     if (_stable.contains(v)) {
       solver_log::strategy << indent() << "Invalidating " << v << std::endl; 
@@ -111,20 +89,18 @@ private:
       if (val != _values[x]) {
         solver_log::strategy << x << " => " << *x.arguments()[val] << std::endl;
 
-        IdSet<MaxExpression<Domain> > oldInfluence = _influence[x];
-        //_influence[x].clear();
         _values[x] = val;
-        _changed = true;
 
         _rho->invalidate(*_system.varFromExpr(x));
         
 	//_rho->stabilise();
 
-        _stable.filter(oldInfluence);
-
+        IdSet<MaxExpression<Domain> > infl = _influence[x];
+        _stable.filter(infl); 
+        
         for (typename IdSet<MaxExpression<Domain> >::iterator
-               it = oldInfluence.begin(),
-               end = oldInfluence.end();
+               it = infl.begin(),
+               end = infl.end();
              it != end;
              ++it) {
           solve(_system.maxExpression(*it));
@@ -141,7 +117,7 @@ private:
 
   struct DependencyAssignment : public VariableAssignment<Domain>{
     DependencyAssignment(DynamicMaxStrategy& strat,
-                         VariableAssignment<Domain>& rho,
+                         DynamicVariableAssignment<Domain>& rho,
                          const MaxExpression<Domain>& expr)
       : _strat(strat),
         _rho(rho),
@@ -149,14 +125,25 @@ private:
 	_current(strat._system.variableCount()) {
     }
     const Domain operator[](const Variable<Domain>& var) {
-      // solve the strategy for this variable, too
-      _strat.solve(*_strat._system[var]);
+      // force evaluation to get touched variables
+      Domain value = _rho[var];
+
       _strat._influence[*_strat._system[var]].insert(_expr);
-      return _rho[var];
+
+      // invalidate touched variables
+      IdSet<Variable<Domain> > changed = _rho.get_changed();
+      for (typename IdSet<Variable<Domain> >::iterator
+             it = changed.begin(),
+             ei = changed.end();
+           it != ei;
+           ++it) {
+        _strat.invalidate(*_strat._system[_strat._system.variable(*it)]);
+      }
+      return value;
     }
   private:
     DynamicMaxStrategy& _strat;
-    VariableAssignment<Domain>& _rho;
+    DynamicVariableAssignment<Domain>& _rho;
     const MaxExpression<Domain>& _expr;
     IdSet<Variable<Domain> > _current;
   };
@@ -186,7 +173,6 @@ private:
   IdMap<MaxExpression<Domain>,unsigned int> _values;
   IdSet<MaxExpression<Domain> > _stable;
   IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence;
-  bool _changed;
 };
 
 
@@ -200,28 +186,12 @@ struct Solver {
   }
 
   Domain solve(Variable<Domain>& var) {
-    MaxExpression<Domain>& rhs = *_system[var];
-
-    // _rho automatically keeps up to date with changes made to the
-    // strategy, so you don't need to stabilise it
-
+      MaxExpression<Domain>& rhs = *_system[var];
+    // this will automatically work sufficiently to get the final
+    // strategy for this variable's RHS
     _strategy.get(rhs);
 
-
-    /*
-    do {
-      _strategy.hasChanged(false);
-      
-      solver_log::debug << "Stabilise assignment (toplevel)" << std::endl;
-      _rho.stabilise();
-      
-      solver_log::debug << "Improve strategy (toplevel)" << std::endl;
-      // improve strategy
-      _strategy.get(rhs);
-      solver_log::debug << (_strategy.hasChanged() ? "Strategy has changed - loop again" : "Strategy has not changed - terminate") << std::endl;
-    } while (_strategy.hasChanged());
-    */
-
+    // this will automatically solve for the value of the RHS, if required
     return _rho[var];
   }
 private:
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp
index 64ef096..0b08866 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp
@@ -135,6 +135,88 @@ struct Guard : public Operator<Domain> {
   }
 };
 
+#include "MCFSimplex.h"
+
+template<typename Domain>
+struct MinCostFlow : public Operator<Domain> {
+  MinCostFlow(const std::vector<Domain>& supplies, const std::vector<std::pair<int,int> > arcs)
+    : _supplies(supplies), _arcs(arcs), _solver(0,0) {
+    MCFClass::FNumber* deficits = new MCFClass::FNumber[supplies.size()];
+    MCFClass::Index* starts = new MCFClass::Index[arcs.size()];
+    MCFClass::Index* ends = new MCFClass::Index[arcs.size()];
+
+    for (int i = 0, size = supplies.size(); i < size; ++i) {
+      deficits[i] = -supplies[i].template as<MCFClass::FNumber>();
+    }
+    for (int i = 0, size = arcs.size(); i < size; ++i) {
+      starts[i] = arcs[i].first;
+      ends[i] = arcs[i].second;
+    }
+
+    _solver.LoadNet(supplies.size(), arcs.size(), // max nodes/arcs
+                    supplies.size(), arcs.size(), // current nodes/arcs
+                    NULL, NULL, // arcs have inf cap, zero cost (to begin)
+                    deficits, // deficits for each node
+                    starts, ends); // start/end of each edge
+
+    delete[] deficits;
+    delete[] starts;
+    delete[] ends;
+  }
+  Domain eval (const std::vector<Domain>& costs) const {
+    assert(costs.size() == _arcs.size());
+    if (costs.size() == 0)
+      return 0;
+    for (int i = 0, size = costs.size(); i < size; ++i) {
+      _solver.ChgCost(i, costs[i].template as<MCFClass::CNumber>());
+    }
+    _solver.SolveMCF();
+    if (_solver.MCFGetStatus() == MCFClass::kUnfeasible){
+      return -infinity<Domain>();
+    } else if (_solver.MCFGetFO() == MCFClass::Inf<MCFClass::FONumber>()) {
+      return infinity<Domain>();
+    } else if (_solver.MCFGetFO() == -MCFClass::Inf<MCFClass::FONumber>()) {
+      return -infinity<Domain>();        
+    } else {
+      return _solver.MCFGetFO();
+    }
+  }
+  void print(std::ostream& cout) const {
+    std::string supplyString = "[";
+    for (int i = 0, size = _supplies.size(); i < size; ++i) {
+      if (i > 0)
+        supplyString += ",";
+      std::stringstream stream;
+      stream << _supplies[i];
+      supplyString += stream.str();
+    }
+    supplyString += ']';
+
+    std::string arcString = "[";
+    for (int i = 0, size = _arcs.size(); i < size; ++i) {
+      if (i > 0)
+        arcString += ",";
+      {
+        std::stringstream stream;
+        stream << _arcs[i].first;
+        arcString += stream.str() + ":";
+      }
+      {
+        std::stringstream stream;
+        stream << _arcs[i].second;
+        arcString += stream.str();
+      }
+    }
+    arcString += ']';
+
+    cout << "MCF<" << supplyString << "," << arcString << ">";
+  }
+private:
+  std::vector<Domain> _supplies;
+  std::vector<std::pair<int,int> > _arcs;
+  mutable MCFSimplex _solver;
+};
+
 /*#include "TemplateConstraintMatrix.hpp"
 
 template<typename Domain>
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
index 746e5ef..4c4519a 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
@@ -24,9 +24,11 @@ struct DynamicVariableAssignment : public VariableAssignment<Domain> {
   ) : _system(system),
       _strategy(strat),
       _values(system.variableCount(), value),
+      _old_values(system.variableCount(), value),
       _unstable(system.variableCount()),
       _influence(system.variableCount(),
-                 IdSet<Variable<Domain> >(system.variableCount()))
+                 IdSet<Variable<Domain> >(system.variableCount())),
+      _touched(system.variableCount())
   { }
 
   const Domain operator[](const Variable<Domain>& var) {
@@ -34,18 +36,13 @@ struct DynamicVariableAssignment : public VariableAssignment<Domain> {
     return _values[var];
   }
 
-  /*void stabilise() {
-    if (!_unstable.empty()) {
-      Variable<Domain>& var = _system.variable(*_unstable.begin());
-      solve(var);
-    }
-    }*/
-
   void invalidate(const Variable<Domain>& x) {
     if (!_unstable.contains(x)) {
       solver_log::fixpoint << indent() << "Invalidating " << x << std::endl;
  
       _unstable.insert(x);
+      _touched.insert(x);
+      _old_values[x] = _values[x];
       _values[x] = infinity<Domain>();
 
       IdSet<Variable<Domain> > infl = _influence[x];
@@ -61,6 +58,23 @@ struct DynamicVariableAssignment : public VariableAssignment<Domain> {
     }
   }
 
+  IdSet<Variable<Domain> > get_changed() {
+    IdSet<Variable<Domain> > changed;
+    for (typename IdSet<Variable<Domain> >::iterator
+           it = _touched.begin(),
+           ei = _touched.end();
+         it != ei;
+         ++it) {
+      Variable<Domain>& var = _system.variable(*it);
+      if (!_unstable.contains(var) && _old_values[var] != _values[var]) {
+        changed.insert(var);
+        _touched.remove(var);
+      }
+    }
+    //_touched.clear();
+    return changed;
+  }
+
 private:
 
   void solve(const Variable<Domain>& x) {
@@ -79,8 +93,6 @@ private:
       if (val != _values[x]) {
         solver_log::fixpoint << x << " = " << val << std::endl;
  
-        _strategy.invalidate(x);
-
         IdSet<Variable<Domain> > oldInfluence = _influence[x];
         _influence[x].clear();
         _values[x] = val;
@@ -118,8 +130,10 @@ private:
   const EquationSystem<Domain>& _system;
   DynamicMaxStrategy<Domain>& _strategy;
   IdMap<Variable<Domain>, Domain> _values;
+  IdMap<Variable<Domain>, Domain> _old_values;
   IdSet<Variable<Domain> > _unstable;
   IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
+  IdSet<Variable<Domain> > _touched;
 };
 
 #endif