diff options
Diffstat (limited to 'clang')
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 = ρ } 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"; - } - */ + } } |