diff options
author | Carlo Zancanaro <carlo@pc-4w14-0.cs.usyd.edu.au> | 2012-11-02 11:06:41 +1100 |
---|---|---|
committer | Carlo Zancanaro <carlo@pc-4w14-0.cs.usyd.edu.au> | 2012-11-02 11:06:41 +1100 |
commit | ea660a9528cea35b7971dfc405e464cbddb2d1d0 (patch) | |
tree | c1989f3d1bd79ac8325326f00ba3cb321f0a3911 /clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp | |
parent | a8472ef1867418b94116324531b3587e0e0e7363 (diff) | |
parent | 1c3d68659fb6341e7a72d563448380a7ffae8c2e (diff) |
Merge branch 'master' of ssh://bitbucket.org/czan/honours
Conflicts:
tex/thesis/contribution/contribution.tex
Diffstat (limited to 'clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp')
-rw-r--r-- | clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp | 146 |
1 files changed, 115 insertions, 31 deletions
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<typename Domain> struct MaxStrategy { virtual ~MaxStrategy() { } + virtual unsigned int get(const MaxExpression<Domain>& e) { + return const_cast<const MaxStrategy<Domain>*>(this)->get(e); + } virtual unsigned int get(const MaxExpression<Domain>& e) const = 0; }; @@ -37,54 +40,85 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> { _stable(system.maxExpressionCount()), _influence(system.maxExpressionCount(), IdSet<MaxExpression<Domain> >(system.maxExpressionCount())), - _var_influence(system.variableCount(), - IdSet<MaxExpression<Domain> >(system.maxExpressionCount())) + _changed(false) {} void setRho(DynamicVariableAssignment<Domain>& rho) { _rho = ρ } + void hasChanged(bool c) { + _changed = c; + } + + bool hasChanged() const { + return _changed; + } + unsigned int get(const MaxExpression<Domain>& e) const { - solve(e); + solver_log::strategy << indent() << "Look up " << e << std::endl; return _values[e]; } - void invalidate(const Variable<Domain>& v) const { - solver_log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl; - _stable.filter(_var_influence[v]); + unsigned int get(const MaxExpression<Domain>& e) { + solver_log::strategy << indent() << "Solve for " << e << std::endl; + solve(e); + return _values[e]; + } - IdSet<MaxExpression<Domain> > infl = _var_influence[v]; - _var_influence[v].clear(); + 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) { - solve(_system.maxExpression(*it)); + invalidate(_system.maxExpression(*it)); + } + } + + void invalidate(const MaxExpression<Domain>& 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<MaxExpression<Domain> > infl = _influence[v]; + for (typename IdSet<MaxExpression<Domain> >::iterator + it = infl.begin(), + end = infl.end(); + it != end; + ++it) { + invalidate(_system.maxExpression(*it)); + } } } private: - void solve(const MaxExpression<Domain>& x) const { + void solve(const MaxExpression<Domain>& 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<MaxExpression<Domain> > 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<Domain>{ - DependencyAssignment(const DynamicMaxStrategy& strat, + DependencyAssignment(DynamicMaxStrategy& strat, VariableAssignment<Domain>& rho, const MaxExpression<Domain>& expr) : _strat(strat), _rho(rho), - _expr(expr) { + _expr(expr), + _current(strat._system.variableCount()) { } - const Domain& operator[](const Variable<Domain>& var) const { - _strat._var_influence[var].insert(_expr); + const Domain operator[](const Variable<Domain>& 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<Domain>& _rho; const MaxExpression<Domain>& _expr; + IdSet<Variable<Domain> > _current; }; struct DependencyStrategy : public MaxStrategy<Domain> { - DependencyStrategy(const DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr) + DependencyStrategy(DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr) : _strat(strat), _expr(expr) { } unsigned int get(const MaxExpression<Domain>& e) const { + _strat._influence[e].insert(_expr); + return _strat._values[e]; + } + unsigned int get(const MaxExpression<Domain>& 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<Domain>& _expr; }; +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; + bool _changed; +}; + + +template<typename Domain> +struct Solver { + Solver(const EquationSystem<Domain>& system) + : _system(system), + _strategy(system), + _rho(_system, _strategy, -infinity<Domain>()) { + _strategy.setRho(_rho); + } + + 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 + + _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<Domain>& _system; - 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; + DynamicMaxStrategy<Domain> _strategy; + DynamicVariableAssignment<Domain> _rho; }; + /*template<typename Domain> std::ostream& operator<<(std::ostream& cout, const MaxStrategy<Domain>& strat) { strat.print(cout); |