Merge branch 'master' of ssh://bitbucket.org/czan/honours

Conflicts:
	impl/test/run

3 files changed, 71 insertions, 147 deletions

diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
index f4026dd..57dcdeb 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
@@ -10,9 +10,6 @@ template<typename Domain>
 struct MaxStrategy {
   virtual ~MaxStrategy() { }
   virtual unsigned int get(const MaxExpression<Domain>& e) const = 0;
-  virtual unsigned int get(const MaxExpression<Domain>& e) {
-    return const_cast<const MaxStrategy*>(this)->get(e);
-  }
 };
 
 unsigned int stack_depth = 1;
@@ -41,38 +38,20 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> {
       _influence(system.maxExpressionCount(),
                  IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
       _var_influence(system.variableCount(),
-                     IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
-      _frozen(false)
+                     IdSet<MaxExpression<Domain> >(system.maxExpressionCount()))
   {}
 
-  void freeze() {
-    _frozen = true;
-  }
-
-  void thaw() {
-    _frozen = false;
-  }
-
-  bool is_frozen() {
-    return _frozen;
-  }
-
   void setRho(DynamicVariableAssignment<Domain>& rho) {
     _rho = &rho;
   }
 
   unsigned int get(const MaxExpression<Domain>& e) const {
+    solve(e);
     return _values[e];
   }
 
-  unsigned int get(const MaxExpression<Domain>& e) {
-    if (!_frozen)
-      solve(e);
-    return _values[e];
-  }
-
-  void invalidate(const Variable<Domain>& v) {
-    log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl; 
+  void invalidate(const Variable<Domain>& v) const {
+    solver_log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl;
     _stable.filter(_var_influence[v]);
 
     IdSet<MaxExpression<Domain> > infl = _var_influence[v];
@@ -88,10 +67,10 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> {
   }
 
 private:
-  void solve(const MaxExpression<Domain>& x) {
+  void solve(const MaxExpression<Domain>& x) const {
     if (!_stable.contains(x)) {
       _stable.insert(x);
-      log::strategy << indent() << "Stabilise " << x << std::endl;
+      solver_log::strategy << indent() << "Stabilise " << x << std::endl;
 
       stack_depth++;
       unsigned int val = x.bestStrategy(DependencyAssignment(*this, *_rho, x),
@@ -99,7 +78,7 @@ private:
       stack_depth--;
 
       if (val != _values[x]) {
-        log::strategy << x << " => " << *x.arguments()[val] << std::endl;
+        solver_log::strategy << x << " => " << *x.arguments()[val] << std::endl;
 
         IdSet<MaxExpression<Domain> > oldInfluence = _influence[x];
         _influence[x].clear();
@@ -117,17 +96,15 @@ private:
           solve(_system.maxExpression(*it));
         }
       } else {
-        log::strategy << indent() << x << " did not change: "
-		      << x << " => " << *x.arguments()[val] << std::endl;
+        solver_log::strategy << indent() << x << " did not change" << std::endl;
       }
     } else {
-      log::strategy << indent() << x << " is stable: "
-		    << x << " => " << *x.arguments()[_values[x]] << std::endl;
+      solver_log::strategy << indent() << x << " is stable" << std::endl;
     }
   }
 
   struct DependencyAssignment : public VariableAssignment<Domain>{
-    DependencyAssignment(DynamicMaxStrategy& strat,
+    DependencyAssignment(const DynamicMaxStrategy& strat,
                          VariableAssignment<Domain>& rho,
                          const MaxExpression<Domain>& expr)
       : _strat(strat),
@@ -139,13 +116,13 @@ private:
       return _rho[var];
     }
   private:
-    DynamicMaxStrategy& _strat;
+    const DynamicMaxStrategy& _strat;
     VariableAssignment<Domain>& _rho;
     const MaxExpression<Domain>& _expr;
   };
 
   struct DependencyStrategy : public MaxStrategy<Domain> {
-    DependencyStrategy(DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr)
+    DependencyStrategy(const DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr)
       : _strat(strat),
         _expr(expr) {
     }
@@ -157,57 +134,19 @@ private:
       return _strat._values[e];
     }
   private:
-    DynamicMaxStrategy& _strat;
+    const DynamicMaxStrategy& _strat;
     const MaxExpression<Domain>& _expr;
   };
 
-private: 
+private:
   const EquationSystem<Domain>& _system;
-  DynamicVariableAssignment<Domain>* _rho;
-  IdMap<MaxExpression<Domain>,unsigned int> _values;
-  IdSet<MaxExpression<Domain> > _stable;
-  IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence;
-  IdMap<Variable<Domain>,IdSet<MaxExpression<Domain> > > _var_influence;
-  bool _frozen;
+  mutable DynamicVariableAssignment<Domain>* _rho;
+  mutable IdMap<MaxExpression<Domain>,unsigned int> _values;
+  mutable IdSet<MaxExpression<Domain> > _stable;
+  mutable IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence;
+  mutable IdMap<Variable<Domain>,IdSet<MaxExpression<Domain> > > _var_influence;
 };
 
-
-template<typename T>
-IdMap<Variable<T>,T> solve_for(const EquationSystem<T>& system) {
-  IdMap<Variable<T>,T> result(system.variableCount(), infinity<T>());
-
-  DynamicMaxStrategy<T> strategy(system);
-  DynamicVariableAssignment<T> rho(system, strategy, -infinity<T>());
-  strategy.setRho(rho);
-
-  bool changed;
-  do {
-    changed = false;
-
-    // improve strategy
-    rho.freeze();
-    strategy.thaw();
-    for (unsigned int i = 0; i < system.variableCount(); ++i) {
-      strategy.get(*system[system.variable(i)]);
-    }
-
-    // iterate fixpoint
-    strategy.freeze();
-    rho.thaw();
-    for (unsigned int i = 0; i < system.variableCount(); ++i) {
-      Variable<T>& var = system.variable(i);
-      T val = rho[var];
-      if (result[var] != val) {
-	result[var] = val;
-	changed = true;
-      }
-    }
-  } while(changed);
-
-  return result;
-}
-
-
 /*template<typename Domain>
 std::ostream& operator<<(std::ostream& cout, const MaxStrategy<Domain>& strat) {
   strat.print(cout);
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
index 2a63756..ba5f650 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
@@ -8,9 +8,6 @@ template<typename Domain>
 struct VariableAssignment {
   virtual ~VariableAssignment() { }
   virtual const Domain& operator[](const Variable<Domain>&) const = 0;
-  virtual const Domain& operator[](const Variable<Domain>& x) {
-    return (*const_cast<const VariableAssignment*>(this))[x];
-  }
 };
 
 #include "EquationSystem.hpp"
@@ -22,71 +19,46 @@ template<typename Domain>
 struct DynamicVariableAssignment : public VariableAssignment<Domain> {
   DynamicVariableAssignment(
     const EquationSystem<Domain>& system,
-    DynamicMaxStrategy<Domain>& strat,
-    const Domain& value=infinity<Domain>()
+    const DynamicMaxStrategy<Domain>& strat
   ) : _system(system),
       _strategy(strat),
-      _values(system.variableCount(), value),
+      _values(system.variableCount(), infinity<Domain>()),
       _stable(system.variableCount()),
       _influence(system.variableCount(),
-                 IdSet<Variable<Domain> >(system.variableCount())),
-      _frozen(false)
+                 IdSet<Variable<Domain> >(system.variableCount()))
   { }
 
-  void freeze() {
-    _frozen = true;
-  }
-
-  void thaw() {
-    _frozen = false;
-  }
-
-  bool is_frozen() {
-    return _frozen;
-  }
-
   const Domain& operator[](const Variable<Domain>& var) const {
+    solve(var);
     return _values[var];
   }
 
-  const Domain& operator[](const Variable<Domain>& var) {
-    if (!_frozen)
-      solve(var);
-    return _values[var];
-  }
-
-  void invalidate(const Variable<Domain>& x) {
-    log::fixpoint << indent() << "Invalidating " << x << std::endl;
+  void invalidate(const Variable<Domain>& x) const {
+    solver_log::fixpoint << indent() << "Invalidating " << x << std::endl;
     if (_stable.contains(x)) {
       _stable.remove(x);
       _values[x] = infinity<Domain>();
-     
-      IdSet<Variable<Domain> > infl = _influence[x];
-      _influence[x].clear();
-      for (typename IdSet<Variable<Domain> >::iterator
-	     it = infl.begin(),
-	     ei = infl.end();
-	   it != ei;
-	   ++it) {
-	invalidate(_system.variable(*it));
-      }
+      
+      solve(x);
     }
   }
 
 private:
 
-  void solve(const Variable<Domain>& x) {
+  void solve(const Variable<Domain>& x) const {
     if (!_stable.contains(x)) {
       _stable.insert(x);
-      log::fixpoint << indent() << "Stabilise " << x << std::endl;
+      solver_log::fixpoint << indent() << "Stabilise " << x << std::endl;
 
       stack_depth++;
-      Domain val = _system[x]->eval(DependencyAssignment(*this, x),
-                                    _strategy);
+      if (!_system[x])
+        return;
+      Domain val = _system[x]->evalWithStrat(DependencyAssignment(*this, x),
+					     _strategy);
       stack_depth--;
 
       if (val != _values[x]) {
-        log::fixpoint << x << " = " << val << std::endl;
+        solver_log::fixpoint << x << " = " << val << std::endl;
 
         IdSet<Variable<Domain> > oldInfluence = _influence[x];
         _influence[x].clear();
@@ -102,17 +74,15 @@ private:
           solve(_system.variable(*it));
         }
       } else {
-        log::fixpoint << indent() << x << " did not change: "
-		      << x << " = " << val << std::endl;
+        solver_log::fixpoint << indent() << x << " did not change" << std::endl;
       }
     } else {
-      log::fixpoint << indent() << x << " is stable: "
-		    << x << " = " << _values[x] << std::endl;
+      solver_log::fixpoint << indent() << x << " is stable" << std::endl;
     }
   }
 
   struct DependencyAssignment : public VariableAssignment<Domain> {
-    DependencyAssignment(DynamicVariableAssignment& assignment, const Variable<Domain>& var)
+    DependencyAssignment(const DynamicVariableAssignment& assignment, const Variable<Domain>& var)
       : _assignment(assignment), _var(var) { }
     const Domain& operator[](const Variable<Domain>& x) const {
       const Domain& result = _assignment[x];
@@ -120,16 +90,15 @@ private:
       return result;
     }
   private:
-    DynamicVariableAssignment& _assignment;
+    const DynamicVariableAssignment& _assignment;
     const Variable<Domain>& _var;
   };
 
   const EquationSystem<Domain>& _system;
-  DynamicMaxStrategy<Domain>& _strategy;
-  IdMap<Variable<Domain>, Domain> _values;
-  IdSet<Variable<Domain> > _stable;
-  IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
-  bool _frozen;
+  const DynamicMaxStrategy<Domain>& _strategy;
+  mutable IdMap<Variable<Domain>, Domain> _values;
+  mutable IdSet<Variable<Domain> > _stable;
+  mutable IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
 };
 
 #endif
diff --git a/clang/lib/Analysis/Interval.cpp b/clang/lib/Analysis/Interval.cpp
index d005048..ac96107 100644
--- a/clang/lib/Analysis/Interval.cpp
+++ b/clang/lib/Analysis/Interval.cpp
@@ -702,24 +702,40 @@ void IntervalAnalysis::runOnAllBlocks() {
     }
   }
 
+  std::vector<EqnExpr*> a;
+
+  a.push_back(&system.constant(-infinity<ZBar>()));
+  a.push_back(&system.constant(0));
+  system[system.variable("x")] = &system.maxExpression(a);
+  a.clear();
+  
+  system.variable("y");
+
+  a.push_back(&system.variable("x"));
+  a.push_back(&system.variable("z"));
+  EqnExpr* minExpr = &system.expression(new Maximum<ZBar>(), a);
+  a.clear();
+
+  a.push_back(&system.constant(-infinity<ZBar>()));
+  a.push_back(minExpr);
+  system[system.variable("y")] = &system.maxExpression(a);
+  a.clear();
+
+  a.push_back(&system.constant(-infinity<ZBar>()));
+  a.push_back(&system.variable("y"));
+  system[system.variable("z")] = &system.maxExpression(a);
+
+  llvm::errs() << toString(system) << "\n";
+
   system.indexMaxExpressions();
+  DynamicMaxStrategy<ZBar> strategy(system);
+  DynamicVariableAssignment<ZBar> rho(system, strategy);
+  strategy.setRho(rho);
 
-  IdMap<EqnVar,ZBar> result = solve_for(system);
   for (unsigned int i = 0, size = system.variableCount(); i < size; ++i) {
-    EqnVar& var = system.variable(i);
-    cout << var.name() << " = " << result[var] << endl;
-  }
-
-  /*
-    DynamicMaxStrategy<ZBar> strategy(system);
-    DynamicVariableAssignment<ZBar> rho(system, strategy);
-    strategy.setRho(rho);
-    
-    for (unsigned int i = 0, size = system.variableCount(); i < size; ++i) {
     EqnVar& var = system.variable(size - i - 1);
     llvm::errs() << toString(var.name()) << " = " << toString(rho[var]) << "\n";
-    }
-  */
+  }
 }