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. --- .../Analysis/Analyses/IntervalSolver/Complete.hpp | 7 +- .../Analyses/IntervalSolver/EquationSystem.hpp | 12 +- .../Analyses/IntervalSolver/Expression.hpp | 82 +++++++++--- .../Analysis/Analyses/IntervalSolver/IdMap.hpp | 13 +- .../Analysis/Analyses/IntervalSolver/IdSet.hpp | 4 + .../clang/Analysis/Analyses/IntervalSolver/Log.hpp | 18 +-- .../Analyses/IntervalSolver/MaxStrategy.hpp | 146 ++++++++++++++++----- .../Analysis/Analyses/IntervalSolver/Operator.hpp | 11 +- .../Analyses/IntervalSolver/VariableAssignment.hpp | 83 +++++++----- 9 files changed, 258 insertions(+), 118 deletions(-) (limited to 'clang/include') diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp index 9acb9d0..e3ec15a 100644 --- a/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp @@ -1,6 +1,7 @@ #ifndef COMPLETE_HPP #define COMPLETE_HPP +#include #include #include @@ -39,7 +40,11 @@ struct Complete { return Complete(- _value, _infinity); } Complete operator+(const Complete& other) const { - if (_infinity) { + if (_infinity && other._infinity) { + if (_value > 0 || other._value > 0) + return Complete(1, true); + return Complete(-1, true); + } else if (_infinity) { return *this; } else if (other._infinity) { return other; diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp index d95366d..3342cc7 100644 --- a/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp @@ -91,13 +91,12 @@ struct EquationSystem { void indexMaxExpressions() { _expr_to_var = new IdMap,Variable*>(maxExpressionCount(), NULL); for (unsigned int i = 0, length = _right_sides.size(); i < length; ++i) { - if (_right_sides[i]) - _right_sides[i]->mapTo(*_variables[i], *_expr_to_var); + _right_sides[i]->mapTo(*_variables[i], *_expr_to_var); } } Variable* varFromExpr(const Expression& expr) const { - assert(_expr_to_var != NULL); // ensure we've indexed + assert(_expr_to_var); // make sure we've indexed const MaxExpression* maxExpr = expr.toMaxExpression();//dynamic_cast*>(&expr); if (maxExpr) { return (*_expr_to_var)[*maxExpr]; @@ -106,7 +105,7 @@ struct EquationSystem { } } - virtual bool equalAssignments(const VariableAssignment& l, const VariableAssignment& r) const { + virtual bool equalAssignments(VariableAssignment& l, VariableAssignment& r) const { for (unsigned int i = 0, length = _variables.size(); i < length; ++i) { @@ -121,10 +120,7 @@ struct EquationSystem { for (unsigned int i = 0, length = _variables.size(); i < length; ++i) { - if (_right_sides[i]) - cout << *_variables[i] << " = " << *_right_sides[i] << std::endl; - else - cout << *_variables[i] << " = NULL" << std::endl; + cout << *_variables[i] << " = " << *_right_sides[i] << std::endl; } } diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Expression.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Expression.hpp index ac9b052..b59c7a2 100644 --- a/clang/include/clang/Analysis/Analyses/IntervalSolver/Expression.hpp +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Expression.hpp @@ -4,6 +4,7 @@ #include #include #include +#include #include "IdMap.hpp" #include "Operator.hpp" @@ -27,15 +28,26 @@ struct Expression { return NULL; } - virtual Domain eval(const VariableAssignment&) const = 0; - virtual Domain evalWithStrat(const VariableAssignment& rho, + virtual MaxExpression* toMaxExpression() { + return NULL; + } + + virtual Domain eval(VariableAssignment&) const = 0; + virtual Domain eval(VariableAssignment& rho, const MaxStrategy&) const { return eval(rho); } + virtual Domain eval(VariableAssignment& rho, + MaxStrategy&) const { + return eval(rho); + } virtual void mapTo(Variable&, IdMap, Variable*>&) const { } + virtual void subMaxExprs(std::set*>&) const { + } + virtual void print(std::ostream&) const = 0; }; @@ -44,7 +56,7 @@ struct Constant : public Expression { Constant(const Domain& value) : _value(value) { } - virtual Domain eval(const VariableAssignment&) const { + virtual Domain eval(VariableAssignment&) const { return _value; } @@ -68,7 +80,7 @@ struct Variable : public Expression { return _name; } - virtual Domain eval(const VariableAssignment& rho) const { + virtual Domain eval(VariableAssignment& rho) const { return rho[*this]; } @@ -84,11 +96,9 @@ struct Variable : public Expression { template struct OperatorExpression : public Expression { OperatorExpression(const Operator& op, const std::vector*>& arguments) - : _operator(op), _arguments(arguments) { - assert(!arguments.empty()); - } + : _operator(op), _arguments(arguments) { } - virtual Domain eval(const VariableAssignment& rho) const { + virtual Domain eval(VariableAssignment& rho) const { std::vector argumentValues; for (typename std::vector*>::const_iterator it = _arguments.begin(); it != _arguments.end(); @@ -98,12 +108,22 @@ struct OperatorExpression : public Expression { return _operator.eval(argumentValues); } - virtual Domain evalWithStrat(const VariableAssignment& rho, const MaxStrategy& strat) const { + virtual Domain eval(VariableAssignment& rho, const MaxStrategy& strat) const { + std::vector argumentValues; + for (typename std::vector*>::const_iterator it = _arguments.begin(); + it != _arguments.end(); + ++it) { + argumentValues.push_back((*it)->eval(rho, strat)); + } + return _operator.eval(argumentValues); + } + + virtual Domain eval(VariableAssignment& rho, MaxStrategy& strat) const { std::vector argumentValues; for (typename std::vector*>::const_iterator it = _arguments.begin(); it != _arguments.end(); ++it) { - argumentValues.push_back((*it)->evalWithStrat(rho, strat)); + argumentValues.push_back((*it)->eval(rho, strat)); } return _operator.eval(argumentValues); } @@ -128,6 +148,14 @@ struct OperatorExpression : public Expression { } } + virtual void subMaxExprs(std::set*>& exprs) const { + for (unsigned int i = 0, length = _arguments.size(); + i < length; + ++i) { + _arguments[i]->subMaxExprs(exprs); + } + } + void print(std::ostream& cout) const { cout << _operator << "("; for (unsigned int i = 0, length = _arguments.size(); @@ -151,31 +179,40 @@ struct MaxExpression : public OperatorExpression { MaxExpression(const unsigned int& id, const Maximum& op, const std::vector*>& arguments) : OperatorExpression(op, arguments), _id(id) { } + MaxExpression* toMaxExpression() { + return this; + } + const MaxExpression* toMaxExpression() const { return this; } - virtual Domain evalWithStrat(const VariableAssignment& rho, const MaxStrategy& strat) const { - return this->_arguments[strat.get(*this)]->evalWithStrat(rho, strat); + virtual Domain eval(VariableAssignment& rho, const MaxStrategy& strat) const { + solver_log::fixpoint << "const MaxExpression eval" << std::endl; + return this->_arguments[strat.get(*this)]->eval(rho, strat); + } + + virtual Domain eval(VariableAssignment& rho, MaxStrategy& strat) const { + solver_log::strategy << "const MaxExpression eval" << std::endl; + return this->_arguments[strat.get(*this)]->eval(rho, strat); } - unsigned int bestStrategy(const VariableAssignment& rho, const MaxStrategy& strat) const { - Domain bestValue = this->evalWithStrat(rho, strat); - unsigned int bestIndex = strat.get(*this); + unsigned int bestStrategy(VariableAssignment& rho, MaxStrategy& strat, unsigned int bestIndex) const { + Domain bestValue = this->_arguments[bestIndex]->eval(rho, strat); for (unsigned int i = 0, length = this->_arguments.size(); i < length; ++i) { - const Domain value = this->_arguments[i]->evalWithStrat(rho, strat); + const Domain value = this->_arguments[i]->eval(rho, strat); if (bestValue < value) { - bestValue = value; bestIndex = i; + bestValue = value; } } return bestIndex; } - virtual void mapTo(Variable& v, IdMap, Variable*>& m) const { + virtual void mapTo(Variable& v, IdMap,Variable*>& m) const { m[*this] = &v; for (unsigned int i = 0, length = this->_arguments.size(); i < length; @@ -184,6 +221,15 @@ struct MaxExpression : public OperatorExpression { } } + virtual void subMaxExprs(std::set*>& exprs) const { + exprs.insert(this); + for (unsigned int i = 0, length = this->_arguments.size(); + i < length; + ++i) { + this->_arguments[i]->subMaxExprs(exprs); + } + } + unsigned int id() const { return _id; } diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/IdMap.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/IdMap.hpp index 5e3aa3b..8cb25f8 100644 --- a/clang/include/clang/Analysis/Analyses/IntervalSolver/IdMap.hpp +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/IdMap.hpp @@ -1,13 +1,14 @@ #ifndef ID_MAP_HPP #define ID_MAP_HPP +#include #include template struct IdMap { IdMap(unsigned int length, V initial) : _length(length), _assignment(new V[length]) { - for (unsigned int i = 0; i < length; ++i) { + for (unsigned int i = 0; i < _length; ++i) { _assignment[i] = initial; } } @@ -32,17 +33,11 @@ struct IdMap { return *this; } virtual const V& operator[] (const T& x) const { - if (x.id() >= _length) { - std::cout << "throw exception" << *(char*)NULL; - //throw "Array out of bounds"; - } + assert(x.id() < _length); return _assignment[x.id()]; } virtual V& operator[] (const T& x) { - if (x.id() >= _length) { - std::cout << "throw exception" << *(char*)NULL; - //throw "Array out of bounds"; - } + assert(x.id() < _length); return _assignment[x.id()]; } diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/IdSet.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/IdSet.hpp index 950b1e1..bf98502 100644 --- a/clang/include/clang/Analysis/Analyses/IntervalSolver/IdSet.hpp +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/IdSet.hpp @@ -96,6 +96,10 @@ class IdSet { return _set.size(); } + bool empty() const { + return _set.empty(); + } + private: unsigned int _range; std::set _set; diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp index f9af7f2..90ab7e5 100644 --- a/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp @@ -1,26 +1,20 @@ #ifndef LOG_HPP #define LOG_HPP +// could not be hackier, but C++ is annoying +#define protected public +#include +#undef protected + #include #include #include #include namespace solver_log { - struct Logger : public std::ostream { - Logger(std::streambuf*, const std::string&) + Logger(std::streambuf* buffer, const std::string& name) : std::ostream(NULL) { } - - bool enabled() const { - return false; - } - - bool enabled(bool) { - return false; - } - - private: }; Logger strategy(std::cerr.rdbuf(), "strategy"); 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); diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp index 08c66ff..64ef096 100644 --- a/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp @@ -1,6 +1,7 @@ #ifndef OPERATOR_HPP #define OPERATOR_HPP +#include #include template @@ -28,11 +29,6 @@ struct Maximum : public Operator { } }; - -template -T minimum(const T& l, const T& r) { - return (l < r ? l : r); -} template struct Minimum : public Operator { virtual Domain eval(const std::vector& arguments) const { @@ -40,7 +36,7 @@ struct Minimum : public Operator { for (typename std::vector::const_iterator it = arguments.begin(); it != arguments.end(); ++it) { - result = minimum(*it, result); //*it < result ? *it : result); + result = (*it < result ? *it : result); } return result; } @@ -52,8 +48,7 @@ struct Minimum : public Operator { template struct Negation : public Operator { virtual Domain eval(const std::vector& arguments) const { - if (arguments.size() > 1) - throw "Too many arguments to a negation."; + assert(arguments.size() == 1); return -arguments[0]; } void print(std::ostream& cout) const { diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp index ba5f650..746e5ef 100644 --- a/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp @@ -7,7 +7,7 @@ template struct VariableAssignment { virtual ~VariableAssignment() { } - virtual const Domain& operator[](const Variable&) const = 0; + virtual const Domain operator[](const Variable& x) = 0; }; #include "EquationSystem.hpp" @@ -19,54 +19,73 @@ template struct DynamicVariableAssignment : public VariableAssignment { DynamicVariableAssignment( const EquationSystem& system, - const DynamicMaxStrategy& strat + DynamicMaxStrategy& strat, + const Domain& value=infinity() ) : _system(system), _strategy(strat), - _values(system.variableCount(), infinity()), - _stable(system.variableCount()), + _values(system.variableCount(), value), + _unstable(system.variableCount()), _influence(system.variableCount(), IdSet >(system.variableCount())) { } - const Domain& operator[](const Variable& var) const { + const Domain operator[](const Variable& var) { solve(var); return _values[var]; } - void invalidate(const Variable& x) const { - solver_log::fixpoint << indent() << "Invalidating " << x << std::endl; - if (_stable.contains(x)) { - _stable.remove(x); + /*void stabilise() { + if (!_unstable.empty()) { + Variable& var = _system.variable(*_unstable.begin()); + solve(var); + } + }*/ + + void invalidate(const Variable& x) { + if (!_unstable.contains(x)) { + solver_log::fixpoint << indent() << "Invalidating " << x << std::endl; + + _unstable.insert(x); _values[x] = infinity(); - - solve(x); + + IdSet > infl = _influence[x]; + _influence[x].clear(); + + for (typename IdSet >::iterator + it = infl.begin(), + ei = infl.end(); + it != ei; + ++it) { + invalidate(_system.variable(*it)); + } } } private: - void solve(const Variable& x) const { - if (!_stable.contains(x)) { - _stable.insert(x); + void solve(const Variable& x) { + if (_unstable.contains(x)) { + _unstable.remove(x); solver_log::fixpoint << indent() << "Stabilise " << x << std::endl; stack_depth++; - if (!_system[x]) - return; - Domain val = _system[x]->evalWithStrat(DependencyAssignment(*this, x), - _strategy); + // we don't want the assignment to affect the strategy, so we're + // going to use a const reference here + const DynamicMaxStrategy& const_strat = _strategy; + DependencyAssignment assignment(*this, x); + Domain val = _system[x]->eval(assignment, const_strat); stack_depth--; if (val != _values[x]) { solver_log::fixpoint << x << " = " << val << std::endl; + + _strategy.invalidate(x); IdSet > oldInfluence = _influence[x]; _influence[x].clear(); _values[x] = val; - _strategy.invalidate(x); - - _stable.filter(oldInfluence); + _unstable.absorb(oldInfluence); for (typename IdSet >::iterator it = oldInfluence.begin(); it != oldInfluence.end(); @@ -74,31 +93,33 @@ private: solve(_system.variable(*it)); } } else { - solver_log::fixpoint << indent() << x << " did not change" << std::endl; + solver_log::fixpoint << indent() << x << " did not change: " + << x << " = " << val << std::endl; } } else { - solver_log::fixpoint << indent() << x << " is stable" << std::endl; + solver_log::fixpoint << indent() << x << " is stable: " + << x << " = " << _values[x] << std::endl; } } struct DependencyAssignment : public VariableAssignment { - DependencyAssignment(const DynamicVariableAssignment& assignment, const Variable& var) + DependencyAssignment(DynamicVariableAssignment& assignment, const Variable& var) : _assignment(assignment), _var(var) { } - const Domain& operator[](const Variable& x) const { - const Domain& result = _assignment[x]; + const Domain operator[](const Variable& x) { + const Domain result = _assignment[x]; _assignment._influence[x].insert(_var); return result; } private: - const DynamicVariableAssignment& _assignment; + DynamicVariableAssignment& _assignment; const Variable& _var; }; const EquationSystem& _system; - const DynamicMaxStrategy& _strategy; - mutable IdMap, Domain> _values; - mutable IdSet > _stable; - mutable IdMap,IdSet > > _influence; + DynamicMaxStrategy& _strategy; + IdMap, Domain> _values; + IdSet > _unstable; + IdMap,IdSet > > _influence; }; #endif -- cgit v1.2.3 From ff5ec13849a69ef4a53bab009eed880456931a14 Mon Sep 17 00:00:00 2001 From: "Zancanaro; Carlo" Date: Thu, 1 Nov 2012 20:02:14 +1100 Subject: Fixing up some equation system stuff. Adding function arguments to the system, as well as making it slightly easier to read. --- clang/include/clang/Analysis/Analyses/.#Interval.h | 1 - .../clang/Analysis/Analyses/.#Interval_flymake.h | 1 - clang/include/clang/Analysis/Analyses/Interval.h | 2 +- clang/lib/Analysis/Interval.cpp | 34 ++++++++++++++++++---- .../lib/StaticAnalyzer/Checkers/.#IntervalTest.cpp | 1 - clang/lib/StaticAnalyzer/Checkers/IntervalTest.cpp | 2 +- impl/test/14.eqns | 3 ++ impl/test/14.soln | 3 ++ 8 files changed, 36 insertions(+), 11 deletions(-) delete mode 120000 clang/include/clang/Analysis/Analyses/.#Interval.h delete mode 120000 clang/include/clang/Analysis/Analyses/.#Interval_flymake.h delete mode 120000 clang/lib/StaticAnalyzer/Checkers/.#IntervalTest.cpp create mode 100644 impl/test/14.eqns create mode 100644 impl/test/14.soln (limited to 'clang/include') diff --git a/clang/include/clang/Analysis/Analyses/.#Interval.h b/clang/include/clang/Analysis/Analyses/.#Interval.h deleted file mode 120000 index 235903b..0000000 --- a/clang/include/clang/Analysis/Analyses/.#Interval.h +++ /dev/null @@ -1 +0,0 @@ -carlo@pc-4w14-0.cs.usyd.edu.au.1585:1347012043 \ No newline at end of file diff --git a/clang/include/clang/Analysis/Analyses/.#Interval_flymake.h b/clang/include/clang/Analysis/Analyses/.#Interval_flymake.h deleted file mode 120000 index 235903b..0000000 --- a/clang/include/clang/Analysis/Analyses/.#Interval_flymake.h +++ /dev/null @@ -1 +0,0 @@ -carlo@pc-4w14-0.cs.usyd.edu.au.1585:1347012043 \ No newline at end of file diff --git a/clang/include/clang/Analysis/Analyses/Interval.h b/clang/include/clang/Analysis/Analyses/Interval.h index 6c0d5cf..8bb8d0f 100644 --- a/clang/include/clang/Analysis/Analyses/Interval.h +++ b/clang/include/clang/Analysis/Analyses/Interval.h @@ -33,7 +33,7 @@ public: IntervalAnalysis(AnalysisDeclContext &analysisContext); virtual ~IntervalAnalysis(); - void runOnAllBlocks(); + void runOnAllBlocks(const Decl&); static IntervalAnalysis *create(AnalysisDeclContext &analysisContext) { return new IntervalAnalysis(analysisContext); diff --git a/clang/lib/Analysis/Interval.cpp b/clang/lib/Analysis/Interval.cpp index 3a82344..7096d75 100644 --- a/clang/lib/Analysis/Interval.cpp +++ b/clang/lib/Analysis/Interval.cpp @@ -637,10 +637,16 @@ void runOnBlock(const CFGBlock* block, EqnSys& system, BlockVars& block_vars) { std::vector plusArgs; for (int negate = 0; negate < 2; ++negate) { std::string var_name = negate ? negate_string(variables->first) : variables->first; - std::vector minArgs; - minArgs.push_back(vars[var_name]); - minArgs.push_back(&system.constant(cond[var_name])); - plusArgs.push_back(&system.expression(new Minimum(), minArgs)); + if (cond[var_name] == infinity()) { + plusArgs.push_back(vars[var_name]); + } else if (cond[var_name] == -infinity()) { + plusArgs.push_back(&system.constant(-infinity())); + } else { + std::vector minArgs; + minArgs.push_back(vars[var_name]); + minArgs.push_back(&system.constant(cond[var_name])); + plusArgs.push_back(&system.expression(new Minimum(), minArgs)); + } } std::vector guard_args; @@ -667,15 +673,31 @@ IntervalAnalysis :: IntervalAnalysis(AnalysisDeclContext &context) IntervalAnalysis :: ~IntervalAnalysis() { } -void IntervalAnalysis::runOnAllBlocks() { +void IntervalAnalysis::runOnAllBlocks(const Decl& decl) { const CFG *cfg = this->context->getCFG(); cfg->dump(context->getASTContext().getLangOpts(), llvm::sys::Process::StandardErrHasColors()); - EqnSys system; + EqnSys system; BlockVars block_vars; + std::vector infArg; + infArg.push_back(&system.constant(infinity())); + std::set& function_arguments = block_vars[&cfg->getEntry()]; + std::string block_id = toString(cfg->getEntry().getBlockID()); + if (const FunctionDecl* func = dyn_cast(&decl)) { + for (unsigned int i = func->getNumParams(); i > 0; i--) { + std::string name = func->getParamDecl(i-1)->getNameAsString(); + + function_arguments.insert(name); // add it to the first block's vars + function_arguments.insert(negate_string(name)); // add it to the first block's vars + + system[system.variable(name + '-' + block_id + "-pre")] = &system.maxExpression(infArg); // set the vars to infinity in the system here + system[system.variable(negate_string(name) + '-' + block_id + "-pre")] = &system.maxExpression(infArg); // set the vars to infinity in the system here + } + } + std::set seen; std::deque todo; todo.push_back(&cfg->getEntry()); diff --git a/clang/lib/StaticAnalyzer/Checkers/.#IntervalTest.cpp b/clang/lib/StaticAnalyzer/Checkers/.#IntervalTest.cpp deleted file mode 120000 index 235903b..0000000 --- a/clang/lib/StaticAnalyzer/Checkers/.#IntervalTest.cpp +++ /dev/null @@ -1 +0,0 @@ -carlo@pc-4w14-0.cs.usyd.edu.au.1585:1347012043 \ No newline at end of file diff --git a/clang/lib/StaticAnalyzer/Checkers/IntervalTest.cpp b/clang/lib/StaticAnalyzer/Checkers/IntervalTest.cpp index 2f3e155..badb671 100644 --- a/clang/lib/StaticAnalyzer/Checkers/IntervalTest.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/IntervalTest.cpp @@ -14,7 +14,7 @@ public: void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, BugReporter &BR) const { if (IntervalAnalysis *a = mgr.getAnalysis(D)) { - a->runOnAllBlocks(); + a->runOnAllBlocks(*D); } } }; diff --git a/impl/test/14.eqns b/impl/test/14.eqns new file mode 100644 index 0000000..6c28481 --- /dev/null +++ b/impl/test/14.eqns @@ -0,0 +1,3 @@ +x = 0 +y = max(x, z) +z = y + 1 diff --git a/impl/test/14.soln b/impl/test/14.soln new file mode 100644 index 0000000..c0301bb --- /dev/null +++ b/impl/test/14.soln @@ -0,0 +1,3 @@ +x = 0 +y = inf +z = inf -- cgit v1.2.3