diff options
3 files changed, 147 insertions, 71 deletions
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp index 57dcdeb..f4026dd 100644 --- a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp @@ -10,6 +10,9 @@ 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; @@ -38,20 +41,38 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> { _influence(system.maxExpressionCount(), IdSet<MaxExpression<Domain> >(system.maxExpressionCount())), _var_influence(system.variableCount(), - IdSet<MaxExpression<Domain> >(system.maxExpressionCount())) + IdSet<MaxExpression<Domain> >(system.maxExpressionCount())), + _frozen(false) {} + void freeze() { + _frozen = true; + } + + void thaw() { + _frozen = false; + } + + bool is_frozen() { + return _frozen; + } + void setRho(DynamicVariableAssignment<Domain>& rho) { _rho = ρ } unsigned int get(const MaxExpression<Domain>& e) const { - solve(e); return _values[e]; } - void invalidate(const Variable<Domain>& v) const { - solver_log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl; + 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; _stable.filter(_var_influence[v]); IdSet<MaxExpression<Domain> > infl = _var_influence[v]; @@ -67,10 +88,10 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> { } 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; + log::strategy << indent() << "Stabilise " << x << std::endl; stack_depth++; unsigned int val = x.bestStrategy(DependencyAssignment(*this, *_rho, x), @@ -78,7 +99,7 @@ private: stack_depth--; if (val != _values[x]) { - solver_log::strategy << x << " => " << *x.arguments()[val] << std::endl; + log::strategy << x << " => " << *x.arguments()[val] << std::endl; IdSet<MaxExpression<Domain> > oldInfluence = _influence[x]; _influence[x].clear(); @@ -96,15 +117,17 @@ private: solve(_system.maxExpression(*it)); } } else { - solver_log::strategy << indent() << x << " did not change" << std::endl; + log::strategy << indent() << x << " did not change: " + << x << " => " << *x.arguments()[val] << std::endl; } } else { - solver_log::strategy << indent() << x << " is stable" << std::endl; + 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), @@ -116,13 +139,13 @@ private: return _rho[var]; } private: - const DynamicMaxStrategy& _strat; + DynamicMaxStrategy& _strat; VariableAssignment<Domain>& _rho; const MaxExpression<Domain>& _expr; }; struct DependencyStrategy : public MaxStrategy<Domain> { - DependencyStrategy(const DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr) + DependencyStrategy(DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr) : _strat(strat), _expr(expr) { } @@ -134,19 +157,57 @@ private: return _strat._values[e]; } private: - const DynamicMaxStrategy& _strat; + DynamicMaxStrategy& _strat; const MaxExpression<Domain>& _expr; }; -private: +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; + 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; }; + +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 ba5f650..2a63756 100644 --- a/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp @@ -8,6 +8,9 @@ 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" @@ -19,46 +22,71 @@ template<typename Domain> struct DynamicVariableAssignment : public VariableAssignment<Domain> { DynamicVariableAssignment( const EquationSystem<Domain>& system, - const DynamicMaxStrategy<Domain>& strat + DynamicMaxStrategy<Domain>& strat, + const Domain& value=infinity<Domain>() ) : _system(system), _strategy(strat), - _values(system.variableCount(), infinity<Domain>()), + _values(system.variableCount(), value), _stable(system.variableCount()), _influence(system.variableCount(), - IdSet<Variable<Domain> >(system.variableCount())) + IdSet<Variable<Domain> >(system.variableCount())), + _frozen(false) { } + 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]; } - void invalidate(const Variable<Domain>& x) const { - solver_log::fixpoint << indent() << "Invalidating " << x << std::endl; + 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; if (_stable.contains(x)) { _stable.remove(x); _values[x] = infinity<Domain>(); - - solve(x); + + 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)); + } } } private: - void solve(const Variable<Domain>& x) const { + void solve(const Variable<Domain>& x) { if (!_stable.contains(x)) { _stable.insert(x); - solver_log::fixpoint << indent() << "Stabilise " << x << std::endl; + log::fixpoint << indent() << "Stabilise " << x << std::endl; stack_depth++; - if (!_system[x]) - return; - Domain val = _system[x]->evalWithStrat(DependencyAssignment(*this, x), - _strategy); + Domain val = _system[x]->eval(DependencyAssignment(*this, x), + _strategy); stack_depth--; if (val != _values[x]) { - solver_log::fixpoint << x << " = " << val << std::endl; + log::fixpoint << x << " = " << val << std::endl; IdSet<Variable<Domain> > oldInfluence = _influence[x]; _influence[x].clear(); @@ -74,15 +102,17 @@ private: solve(_system.variable(*it)); } } else { - solver_log::fixpoint << indent() << x << " did not change" << std::endl; + log::fixpoint << indent() << x << " did not change: " + << x << " = " << val << std::endl; } } else { - solver_log::fixpoint << indent() << x << " is stable" << std::endl; + log::fixpoint << indent() << x << " is stable: " + << x << " = " << _values[x] << std::endl; } } struct DependencyAssignment : public VariableAssignment<Domain> { - DependencyAssignment(const DynamicVariableAssignment& assignment, const Variable<Domain>& var) + DependencyAssignment(DynamicVariableAssignment& assignment, const Variable<Domain>& var) : _assignment(assignment), _var(var) { } const Domain& operator[](const Variable<Domain>& x) const { const Domain& result = _assignment[x]; @@ -90,15 +120,16 @@ private: return result; } private: - const DynamicVariableAssignment& _assignment; + DynamicVariableAssignment& _assignment; const Variable<Domain>& _var; }; const EquationSystem<Domain>& _system; - const DynamicMaxStrategy<Domain>& _strategy; - mutable IdMap<Variable<Domain>, Domain> _values; - mutable IdSet<Variable<Domain> > _stable; - mutable IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence; + DynamicMaxStrategy<Domain>& _strategy; + IdMap<Variable<Domain>, Domain> _values; + IdSet<Variable<Domain> > _stable; + IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence; + bool _frozen; }; #endif diff --git a/clang/lib/Analysis/Interval.cpp b/clang/lib/Analysis/Interval.cpp index ac96107..d005048 100644 --- a/clang/lib/Analysis/Interval.cpp +++ b/clang/lib/Analysis/Interval.cpp @@ -702,40 +702,24 @@ 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"; - } + } + */ } |