From b7eaa99578037789a337c5061c0ea8ee3150b63c Mon Sep 17 00:00:00 2001 From: "Zancanaro; Carlo" Date: Thu, 1 Nov 2012 18:06:13 +1100 Subject: A bunch of fixes to the solver, and moving it in to clang. Also some contribution writing stuff. Basically: lots of work. --- .../Analyses/IntervalSolver/MaxStrategy.hpp | 146 ++++++++++++++++----- 1 file changed, 115 insertions(+), 31 deletions(-) (limited to 'clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp') diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp index 57dcdeb..9ae7394 100644 --- a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp @@ -9,6 +9,9 @@ template struct MaxStrategy { virtual ~MaxStrategy() { } + virtual unsigned int get(const MaxExpression& e) { + return const_cast*>(this)->get(e); + } virtual unsigned int get(const MaxExpression& e) const = 0; }; @@ -37,54 +40,85 @@ struct DynamicMaxStrategy : public MaxStrategy { _stable(system.maxExpressionCount()), _influence(system.maxExpressionCount(), IdSet >(system.maxExpressionCount())), - _var_influence(system.variableCount(), - IdSet >(system.maxExpressionCount())) + _changed(false) {} void setRho(DynamicVariableAssignment& rho) { _rho = ρ } + void hasChanged(bool c) { + _changed = c; + } + + bool hasChanged() const { + return _changed; + } + unsigned int get(const MaxExpression& e) const { - solve(e); + solver_log::strategy << indent() << "Look up " << e << std::endl; return _values[e]; } - void invalidate(const Variable& v) const { - solver_log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl; - _stable.filter(_var_influence[v]); + unsigned int get(const MaxExpression& e) { + solver_log::strategy << indent() << "Solve for " << e << std::endl; + solve(e); + return _values[e]; + } - IdSet > infl = _var_influence[v]; - _var_influence[v].clear(); + void invalidate(const Variable& v) { + solver_log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl; + IdSet > infl = _influence[*_system[v]]; for (typename IdSet >::iterator it = infl.begin(), end = infl.end(); it != end; ++it) { - solve(_system.maxExpression(*it)); + invalidate(_system.maxExpression(*it)); + } + } + + void invalidate(const MaxExpression& v) { + if (_stable.contains(v)) { + solver_log::strategy << indent() << "Invalidating " << v << std::endl; + //solver_log::debug << indent() << " influence sets " << _influence << std::endl; + _stable.remove(v); + + IdSet > infl = _influence[v]; + for (typename IdSet >::iterator + it = infl.begin(), + end = infl.end(); + it != end; + ++it) { + invalidate(_system.maxExpression(*it)); + } } } private: - void solve(const MaxExpression& x) const { + void solve(const MaxExpression& x) { if (!_stable.contains(x)) { _stable.insert(x); solver_log::strategy << indent() << "Stabilise " << x << std::endl; - stack_depth++; - unsigned int val = x.bestStrategy(DependencyAssignment(*this, *_rho, x), - DependencyStrategy(*this, x)); + stack_depth++; + DependencyAssignment assignment(*this, *_rho, x); + DependencyStrategy depStrat(*this, x); + unsigned int val = x.bestStrategy(assignment, depStrat, _values[x]); stack_depth--; if (val != _values[x]) { solver_log::strategy << x << " => " << *x.arguments()[val] << std::endl; IdSet > oldInfluence = _influence[x]; - _influence[x].clear(); + //_influence[x].clear(); _values[x] = val; + _changed = true; _rho->invalidate(*_system.varFromExpr(x)); + + //_rho->stabilise(); _stable.filter(oldInfluence); @@ -96,57 +130,107 @@ private: solve(_system.maxExpression(*it)); } } else { - solver_log::strategy << indent() << x << " did not change" << std::endl; + solver_log::strategy << indent() << x << " did not change: " + << x << " => " << *x.arguments()[val] << std::endl; } } else { - solver_log::strategy << indent() << x << " is stable" << std::endl; + solver_log::strategy << indent() << x << " is stable: " + << x << " => " << *x.arguments()[_values[x]] << std::endl; } } struct DependencyAssignment : public VariableAssignment{ - DependencyAssignment(const DynamicMaxStrategy& strat, + DependencyAssignment(DynamicMaxStrategy& strat, VariableAssignment& rho, const MaxExpression& expr) : _strat(strat), _rho(rho), - _expr(expr) { + _expr(expr), + _current(strat._system.variableCount()) { } - const Domain& operator[](const Variable& var) const { - _strat._var_influence[var].insert(_expr); + const Domain operator[](const Variable& var) { + // solve the strategy for this variable, too + _strat.solve(*_strat._system[var]); + _strat._influence[*_strat._system[var]].insert(_expr); return _rho[var]; } private: - const DynamicMaxStrategy& _strat; + DynamicMaxStrategy& _strat; VariableAssignment& _rho; const MaxExpression& _expr; + IdSet > _current; }; struct DependencyStrategy : public MaxStrategy { - DependencyStrategy(const DynamicMaxStrategy& strat, const MaxExpression& expr) + DependencyStrategy(DynamicMaxStrategy& strat, const MaxExpression& expr) : _strat(strat), _expr(expr) { } unsigned int get(const MaxExpression& e) const { + _strat._influence[e].insert(_expr); + return _strat._values[e]; + } + unsigned int get(const MaxExpression& e) { _strat.solve(e); - if (&_expr != &e) { - _strat._influence[e].insert(_expr); - } + _strat._influence[e].insert(_expr); return _strat._values[e]; } private: - const DynamicMaxStrategy& _strat; + DynamicMaxStrategy& _strat; const MaxExpression& _expr; }; +private: + const EquationSystem& _system; + DynamicVariableAssignment* _rho; + IdMap,unsigned int> _values; + IdSet > _stable; + IdMap,IdSet > > _influence; + bool _changed; +}; + + +template +struct Solver { + Solver(const EquationSystem& system) + : _system(system), + _strategy(system), + _rho(_system, _strategy, -infinity()) { + _strategy.setRho(_rho); + } + + Domain solve(Variable& var) { + MaxExpression& rhs = *_system[var]; + + // _rho automatically keeps up to date with changes made to the + // strategy, so you don't need to stabilise it + + _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()); + */ + + return _rho[var]; + } private: const EquationSystem& _system; - mutable DynamicVariableAssignment* _rho; - mutable IdMap,unsigned int> _values; - mutable IdSet > _stable; - mutable IdMap,IdSet > > _influence; - mutable IdMap,IdSet > > _var_influence; + DynamicMaxStrategy _strategy; + DynamicVariableAssignment _rho; }; + /*template std::ostream& operator<<(std::ostream& cout, const MaxStrategy& strat) { strat.print(cout); -- cgit v1.2.3